Michele di Nuzzo

Data Science and Machine Learning

Immagine che contiene grafico Descrizione generata automaticamente

Clustering con algoritmo K-means

Estratto dal libro Data Science e Machine Learning: dai dati alla conoscenza

Il K-means è un algoritmo di clustering partizionale in cui ogni cluster è associato ad un centroide ed ogni punto è associato al cluster col centroide più vicino. Il funzionamento di questo algoritmo richiede che il parametro k, indicante il numero di cluster da assegnare, sia da noi specificato. L’algoritmo funziona seguendo questi steps:

  • Si selezionano k punti casuali come centroidi iniziali.
  • Formiamo i k clusters assegnando tutti i punti al centroide più vicino.
  • Ricalcoliamo i centroidi di ogni cluster.
    • Se il centroide è cambiato ripetiamo l’assegnazione di tutti i punti al centroide più vicino.
    • Se il centroide non è cambiato abbiamo individuato il cluster.

Le distanze possono essere calcolate con una qualsiasi delle misure che abbiamo già visto nei capitoli precedenti. Tipicamente l’algoritmo converge alle prime iterazioni, ma possono essere specificati criteri di stop in base al numero di iterazioni, o in base a un valore minimo dell’errore totale o ancora fino a che gli elementi di ogni cluster non si stabilizzano (non passano più da un cluster all’altro).

L’algoritmo è sensibile ai minimi locali, in quanto la scelta dei punti casuali di partenza potrebbe portare a risultati diversi nelle varie esecuzioni dell’algoritmo. Una soluzione può essere quella di eseguire l’algoritmo diverse volte scegliendo diversi punti di partenza fino ad ottenere una soluzione che minimizza l’errore, o in alternativa si possono utilizzare altri algoritmi (come il clustering gerarchico) per determinare i punti di partenza. Inoltre, esso risente fortemente della presenza di outliers, che tendono a “spostare” il centroide del cluster aumentando l’errore totale. La soluzione in questo caso consiste nell’identificazione ed eliminazione degli outliers in fase di preparazione dei dati.

Tabella 1 – K-Means

Vantaggi Svantaggi
  • Semplice da interpretare e spiegare
  • Flessibile e facile da regolare
  • È efficiente e restituisce un buon clustering
  • Non è sofisticato come gli algoritmi recenti di clustering
  • Non garantisce di trovare il numero ottimale di cluster
  • Necessita di un’ipotesi sul numero di cluster

Per fare un esempio di clustering con K-means in R utilizzeremo il dataset USArrests, che contiene 50 osservazioni con gli arresti ogni 100.000 residenti per aggressione, omicidio e stupro in ciascuno dei 50 stati degli Stati Uniti nel 1973.

> library(tidyverse)
> library(cluster) # algoritmi di clustering
> library(factoextra) # algoritmi di clustering & visualization

> mydata <- USArrests
> head(mydata)

           Murder  Assault UrbanPop Rape
Alabama      13.2      236       58 21.2
Alaska       10.0      263       48 44.5
Arizona       8.1      294       80 31.0
Arkansas      8.8      190       50 19.5
California    9.0      276       91 40.6
Colorado      7.9      204       78 38.7

Ripuliamo le righe con valori missing e scaliamo le variabili:

> mydata <- na.omit(mydata)
> mydata <- scale(mydata)
> head(mydata)

                Murder   Assault   UrbanPop         Rape
Alabama     1.24256408 0.7828393 -0.5209066 -0.003416473
Alaska      0.50786248 1.1068225 -1.2117642  2.484202941
Arizona     0.07163341 1.4788032  0.9989801  1.042878388
Arkansas    0.23234938 0.2308680 -1.0735927 -0.184916602
California  0.27826823 1.2628144  1.7589234  2.067820292
Colorado    0.02571456 0.3988593  0.8608085  1.864967207

Utilizziamo ora la funzione get_dist() per calcolare una matrice delle distanze (la distanza predefinita è quella euclidea, ma se ne possono utilizzare molte altre) e la funzione fviz_dist() per visualizzarla:

> # get_dist: calcola la matrice delle distanze
> # fviz_dist: visualizza la matrice

> distance <- get_dist(mydata)
> fviz_dist(distance, gradient = list(low = "#00AFBB", 
  mid = "white", high = "#FC4E07"))

Immagine che contiene grafico Descrizione generata automaticamente

Figura 1 – La matrice delle distanze

In R l’algoritmo K-means è implementato con la funzione kmeans(). Passeremo alla funzione il numero di centri (due) ed un parametro che prova diverse configurazioni iniziali e seleziona la migliore (in genere si prova su 25 configurazioni):

> k2 <- kmeans(mydata, centers = 2, nstart = 25)
> str(k2)

List of 9
$ cluster : Named int [1:50] 1 1 1 2 1 1 2 2 1 1 ...
..- attr(*, "names")= chr [1:50] "Alabama" "Alaska" "Arizona" "Arkansas" ...
$ centers : num [1:2, 1:4] 1.005 -0.67 1.014 -0.676 0.198 ...
..- attr(*, "dimnames")=List of 2
.. ..$ : chr [1:2] "1" "2"
.. ..$ : chr [1:4] "Murder" "Assault" "UrbanPop" "Rape"
$ totss       : num 196
$ withinss    : num [1:2] 46.7 56.1
$ tot.withinss: num 103
$ betweenss   : num 93.1
$ size        : int [1:2] 20 30
$ iter        : int 1
$ ifault      : int 0
- attr(*, "class")= chr "kmeans"

Visualizziamo il modello:

> # visualizzo i dettagli
> k2
K-means clustering with 2 clusters of sizes 20, 30

Cluster means:
Murder Assault UrbanPop Rape
1 1.004934 1.0138274 0.1975853 0.8469650
2 -0.669956 -0.6758849 -0.1317235 -0.5646433

Clustering vector:
     Alabama    Alaska     Arizona       Arkansas
           1         1           1              2
  California  Colorado Connecticut       Delaware
           1         1           2              2
     Florida   Georgia      Hawaii          Idaho
           1         1           2              2
…
South Dakota Tennessee       Texas           Utah
           2         1           1              2
     Vermont  Virginia  Washington  West Virginia
           2         2           2              2
   Wisconsin   Wyoming
           2         2

Within cluster sum of squares by cluster:

[1] 46.74796 56.11445
(between_SS / total_SS = 47.5 %)

Available components:

[1] "cluster" "centers" "totss" "withinss" "tot.withinss" "betweenss" "size" "iter"
[9] "ifault"

Cluster è un vettore di numeri interi (da 1: k) che indica il cluster a cui è allocato ogni punto. Centers è una matrice di centri di cluster, totss è la somma totale dei quadrati degli errori, mentre withinss è il vettore della somma dei quadrati all’interno del cluster, un componente per cluster. Tot.withinss è la somma totale dei quadrati all’interno del cluster, mentre betweenss è la somma dei quadrati tra i gruppi, ovvero totss tot.withinss. Size è il numero di punti in ogni cluster. Utilizziamo ora la funzione fviz_cluster(), molto comoda, che effettua una PCA tra le componenti e traccia un grafico dei cluster rispetto alle due componenti principali:

> # grafico rispetto alle componenti principali
> fviz_cluster(k2, data = mydata)

Immagine che contiene mappa Descrizione generata automaticamente

Figura 2 – Grafico con k = 2

Dobbiamo ora decidere il valore ottimale di k, cioè il numero ideale dei cluster. Proviamo prima a farlo manualmente, utilizzando diversi valori di k:

> # diversi valori di K
> k3 <- kmeans(mydata, centers = 3, nstart = 25)
> k4 <- kmeans(mydata, centers = 4, nstart = 25)
> k5 <- kmeans(mydata, centers = 5, nstart = 25)

> # creo diversi grafici per valori di k
> p1 <- fviz_cluster(k2, geom = "point", data = mydata) + ggtitle("k = 2")
> p2 <- fviz_cluster(k3, geom = "point", data = mydata) + ggtitle("k = 3")
> p3 <- fviz_cluster(k4, geom = "point", data = mydata) + ggtitle("k = 4")
> p4 <- fviz_cluster(k5, geom = "point", data = mydata) + ggtitle("k = 5")

> install.packages("gridExtra")
> library(gridExtra)
> grid.arrange(p1, p2, p3, p4, nrow = 2)

Figura 3 – K-means per diversi valori di k

Andiamo ora a determinare il numero ottimale di cluster coi diversi metodi a nostra disposizione. Innanzitutto, proviamo il metodo Elbow:

> # metodo Elbow
> set.seed(123)
> fviz_nbclust(mydata, kmeans, method = "wss")

Immagine che contiene grafico Descrizione generata automaticamente

Figura 4 – Numero ottimale di cluster col metodo Elbow

Proviamo ora col metodo silouhette:

> # metodo silouhette
> fviz_nbclust(mydata, kmeans, method = "silhouette")

Immagine che contiene grafico Descrizione generata automaticamente

Figura 5 – Numero ottimale di cluster col metodo silouhette

Ed infine col gap statistics:

> # metodo gap statistics
> gap_stat <- clusGap(mydata, FUN = kmeans, nstart = 25, K.max = 10, B = 50)

Clustering k = 1,2,..., K.max (= 10): .. done
Bootstrapping, b = 1,2,..., B (= 50) [one "." per sample]:

.................................................. 50

> print(gap_stat, method = "firstmax")

Clustering Gap statistic ["clusGap"] from call:
clusGap(x = mydata, FUNcluster = kmeans, K.max = 10, B = 50, nstart = 25)
B=50 simulated reference sets, k = 1..10; spaceH0="scaledPCA"

--> Number of clusters (method 'firstmax'): 4
logW E.logW gap SE.sim
[1,] 3.458369 3.640156 0.1817869 0.04422756
[2,] 3.135112 3.372380 0.2372687 0.03558739
[3,] 2.977727 3.233913 0.2561861 0.03747805
[4,] 2.826221 3.118924 0.2927035 0.04061157
[5,] 2.738868 3.019640 0.2807720 0.04173697
[6,] 2.666967 2.929928 0.2629603 0.04102800
[7,] 2.609895 2.851923 0.2420281 0.04183308
[8,] 2.537521 2.778291 0.2407703 0.04289286
[9,] 2.468162 2.711324 0.2431612 0.04340014
[10,] 2.400620 2.647381 0.2467610 0.04546883

> fviz_gap_stat(gap_stat)

Immagine che contiene grafico Descrizione generata automaticamente

Figura 6 – Numero ottimale di cluster col metodo gap statistics

Decidiamo di utilizzare k = 4 come numero di cluster ottimale e implementiamo il modello definitivo:

> # k-means clustering con k = 4
> set.seed(123)
> final_model <- kmeans(mydata, 4, nstart = 25)
> print(final_model)

K-means clustering with 4 clusters of sizes 8, 13, 16, 13

Cluster means:
      Murder    Assault   UrbanPop        Rape
1  1.4118898  0.8743346 -0.8145211  0.01927104
2 -0.9615407 -1.1066010 -0.9301069 -0.96676331
3 -0.4894375 -0.3826001  0.5758298 -0.26165379
4  0.6950701  1.0394414  0.7226370  1.27693964

Clustering vector:
       Alabama Alaska Arizona Arkansas
             1      4       4        1
             …

Within cluster sum of squares by cluster:
[1] 8.316061 11.952463 16.212213 19.922437
(between_SS / total_SS = 71.2 %)

Available components:
[1] "cluster" "centers" "totss" "withinss"
    "tot.withinss" "betweenss" "size" "iter"
[9] "ifault"

Visualizziamo i cluster:

> fviz_cluster(final_model, data = mydata)

Figura 7 – Clustering con k = 4

Una variante del K-means è il Partitioning Around Medoids (PAM o K-medoids) che, invece di utilizzare la media per determinare il centroide del cluster, impiega il punto più centrale (medoid). L’algoritmo PAM ha meno sensibilità agli outliers rispetto al K-means, ma il calcolo del punto centrale richiede molta attività di elaborazione. Il PAM in R è disponibile tramite la funzione pam():

> #k-mediods
> model_medoids <- pam(mydata, 4)
> print(model_medoids)

Medoids:
              ID     Murder    Assault   UrbanPop         Rape
Alabama        1  1.2425641  0.7828393 -0.5209066 -0.003416473
Michigan      22  0.9900104  1.0108275  0.5844655  1.480613993
Oklahoma      36 -0.2727580 -0.2371077  0.1699510 -0.131534211
New Hampshire 29 -1.3059321 -1.3650491 -0.6590781 -1.252564419

Clustering vector:
      Alabama Alaska Arizona Arkansas
            1      2       2        1      …

Objective function:
build swap
1.035116 1.027102

Available components:
[1] "medoids" "id.med" "clustering" "objective" "isolation"
    "clusinfo" "silinfo" "diss" "call"
[10] "data"

Osserviamo i risultati, che differiscono leggermente dal metodo k-means:

> fviz_cluster(model_medoids, data = mydata)

Immagine che contiene grafico Descrizione generata automaticamente

Figura 8 – Clustering con PAM

 

Vuoi saperne di più? Acquista il libro Data Science e Machine Learning: dai dati alla conoscenza su Amazon:

Leave a Reply