venerdì 2 luglio 2010

Cluster Analysis in R #2: Partitional Clustering

Questo è il secondo post sull'argomento della cluster analysis in R, scritto con la preziosa collaborazione di Mirko Modenese (www.eurac.edu). Nel primo è stata presentata la tecnica del hierarchical clustering, mentre qui verrà discussa la tecnica del Partitional Clustering, con particolare attenzione all'algoritmo Kmeans.


Introduzione alla Cluster Analysis \
Hierarchical clustering |
Esempio 1. |
Esempio 1.R | CA in R #1
Esempio 2.R |
Varianti |
Il taglio del dendrogramma /

Partitional clustering \
Definizione di distanza |
Distanza di Minkowski |
Distanza euclidea |
Algoritmo K-means |
Esempio 1 | CA in R #2
Esempio 2 |
Esempio 1.R |
Esempio 2.R |
Varianti /





Partitional clustering

Definizione di distanza

La distanza di Minkowski

Il concetto di "distanza", in ambito di cluster analysis, è fondamentale essenzialmente in due punti:
1) Valutazione della dissimilarità tra due punti;
2) Valutazione della dissimilarità tra cluster.
Chiariamo innanzitutto la differenza semantica tra distanza e dissimilarità. La distanza rispetta le seguenti proprietà:
  1. la distanza tra due punti non coincidenti deve essere positiva (distinction or separation)

  2. la distanza tra due punti che coincidono è nulla (co-location or equivalence)

  3. la distanza tra due punti deve essere simmetrica, nel senso che se i due punti sono A e B, la distanza tra A e B deve essere uguale alla distanza tra B ed A (symmetry)

  4. se i punti sono 3 - nel caso A, B e C - deve valere la cosiddetta proprietà triangolare (triangle inequality)

[il caso di coincidenza si ha solo nel momento in cui il punto B appartenga al segmento rettilineo che separa A e C.]

Con il termine distanza tutti e 4 i punti sopra elencati sono rispettati, mentre nel caso di dissimilarità non è garantita la disuguaglianza triangolare (punto IV). Tale differenza amplia le possibilità di applicazione del concetto di misurazione della differenza metrica tra oggetti.
Nell’analisi dei gruppi non ci si basa sul solo concetto di distanza euclidea ma si utilizzano diversi concetti di distanza in base allo scopo del clustering e alla tipologia dei dati.
Un modello riassuntivo delle diverse dissimilarità (utilizziamo questo termine al fine di racchiudere tutte le tipologie, compresa quella euclidea) è quello di Minkowski:


Sostituendo k = 1,2,... otteniamo diverse distanze:
  • : distanza di Manhattan (o distanza della città a blocchi, taxi cab,...)

  • : distanza Euclidea

  • ...

  • : distanza del massimo (o distanza di Chebyshev).


Distanza euclidea

Definiamo la distanza euclidea tra 2 punti p e q come il segmento pq. Siano p=(p1, p2, ..., pn) e q=(q1, q2, ..., qn) le coordinate dei due punti considerati in uno spazio euclideo a n-dimensioni. Il segmento pq sarà:



Esempio:
Calcolare la distanza euclidea in un piano a 2-dimensioni tra i punti A(4,5) e B(12,7).



Calcolare la distanza euclidea in un piano a 3-dimensioni tra i punti p(1,4,12) e q(3,5,23).



In R possiamo calcolare la distanza euclidea tra 2 punti in n-dimensioni con questa funzione:


eucl.dist <- function(point1,point2)
{
diff <- point1 - point2
distance <- sqrt(sum(diff^2))
distance
}


Proviamo a risolvere i 2 esempi precedenti in R:


A <- c(4,5)
B <- c(12,7)
eucl.dist(A,B)
[1] 8.246211

p <- c(1,4,12)
q <- c(3,5,23)
eucl.dist(p,q)
[1] 11.22497


Oppure con la funzione dist, che calcola una matrice di dissimilarità di elementi (n numero di unità statistiche nel dataset).


dist(rbind(A,B))
A
B 8.246211






Algoritmo K-means

L'algoritmo K-means è un algoritmo ricorsivo per la clusterizzazione che si fonda sul principio di minimizzare la distanza euclidea (o di altra funzione) tra i punti assegnati e i centroidi (il centro di ogni cluster).
In altre parole, dati n punti (di p coordinate), e fissato il numero di cluster k (con k < n), assegneremo ciascun punto ad un determinato cluster in modo che la distanza tra il punto e il centroide del cluster sia minimo.
I problemi quindi da risolvere per utilizzare l'algoritmo K-means sono:
  1. determinare il numero di clusters

  2. determinare le coordinate del centroide

  3. scegliere la funzione distanza


Il punto 1 può essere risolto con una semplice formula empirica:

con k = numero di clusters, ed n = numero degli elementi da clusterizzare. Esistono algoritmi più precisi e formalmente corretti di questa regola, come ad esempio il metodo Elbow e l'utilizzo dell'Aikake Information Criterion. Con il metodo Elbow in sostanza si crea una funzione della percentuale di varianza spiegata dal modello in funzione del numero di clusters. Si individua quindi sul grafico quel numero di clusters cui corrisponde una sufficiente percentuale di varianza spiegata dal modello, e per il quale anche aumentando il numero di clusters non si apportano significative modificazioni del modello. Rimando a questo link per una soluzione del problema in R.
Il punto 2 invece può essere risolto con il metodo che vedremo nei due esempi che seguono, in cui svilupperemo la clusterizzazione in due gruppi dapprima di 6 punti monodimensionali, e quindi di 6 punti bidimensionali. Oppure è possibile generare dei numeri pseudo-casuali per le coordinate iniziali dei centroidi (tante coordinate quanti sono i g gruppi definiti con il clustering gerarchico).
Per il punto 3, useremo inizialmente la funzione di distanza euclidea che abbiamo spiegato all’inizio dell’articolo. Al termine, introdurremo la definizione di altre possibili funzioni.




Esempio 1.

Supponiamo di avere i seguenti valori:
a={1,0}
b={2,0}
c={3,0}
d={7,0}
e={8,0}
f={9,0}
e di voler dividere l'insieme in due clusters. Essendo un esempio didattico, la soluzione balza subito agli occhi.



Step 1.
Per prima cosa determiniamo i valori iniziali dei due centroidi C1 e C2. Possiamo iniziare assegnando i valori dei primi 2 punti come centroidi iniziali, quindi e .
A questo punto calcoliamo la distanza euclidea tra tutti gli n valori, e tra questi e i due centroidi, e sistemiamoli in una matrice delle distanze D al cui apice segneremo un numero relativo al passaggio che stiamo effettuando:



La penultima riga indica le distanze tra i 6 punti e il centroide C1, mentre l’ultima riga indica le distanze tra i 6 punti e il centroide C2.



Step 2.
Definiamo la matrice G come la matrice di clustering: assegniamo ciascun punto al gruppo 1 (centroide C1) se la distanza tra il punto e C1 è inferiore alla distanza tra il punto e C2. In tal caso assegniamo valore 1, altrimenti valore 0:



Ad esempio la distanza tra il punto 4 e C1 è 6, mentre la distanza tra il punto 4 e C2 è 5. Quindi assegnamo valore 0 alla riga relativa a C1 e valore 1 alla riga relativa a C2.

Step 3.
Calcoliamo ora i nuovi centroidi. Per trovare le coordinate è sufficiente calcolare la media aritmetica delle coordinate dei punti assegnati ai due gruppi. Quindi:



Step 4.
Calcoliamo ora le distanze tra i punti e i nuovi centroidi così calcolati:





Step 5.
Calcoliamo la matrice di clustering:



Step 6.
Calcoliamo i nuovi centroidi:



Step 7.
Calcoliamo la matrice delle distanze:





Step 8.
Calcoliamo la matrice di clustering:



Poichè la matrice di clustering G2 è uguale a quella precedentemente calcolata (G1), il processo si arresta.
Abbiamo così calcolato i due clusters in cui volevamo dividere i 6 elementi di partenza, e i relativi centroidi:


Cluster 1:
Centroide: C1(2), elementi={1,2,3)
Cluster 2:
Centroide: C2(8), elementi={7,8,9}







Esempio 2.

Cerchiamo ora di eseguire la clusterizzazione in 2 gruppi, di 6 elementi definiti in un piano a 2 dimensioni. I punti sono:
a(1,2)
b(2,4)
c(3,2)
d(10,8)
e(10,10)
f(12,9)




I passaggi sono analoghi, l'unica differenza è anche adesso si calcolano le coordinate in due dimensioni.

Step 1.
Definiamo, per cominciare, i centroidi C1 e C2 come sovrapposti ai punti a e b. Quindi e .
Calcoliamo la matrice delle distanze, e qui possiamo aiutarci con la funzione eucl.dist scritta prima in R. Otterremo:



Calcoliamo ora la matrice di clustering:





Step 2.
Calcoliamo i nuovi centroidi (media aritmetica delle coordinate dei punti con valore 1 nella matrice di clustering):



Ora la matrice delle distanze euclidee tra i 6 punti e i nuovi centroidi:



La matrice di clustering è:





Step 3.
Calcoliamo i nuovi centroidi:



La matrice delle distanze è:



E la matrice di clustering è:



Poichè G2 coincide con G1, l'algoritmo si ferma.
Abbiamo così calcolato i centroidi, e l'appartenenza dei punti ai due clusters:


Cluster 1:
Centroide: C1(2, 8/3), elementi={a,b,c)
Cluster 2:
Centroide: C2(32/3, 9), elementi={d,e,f}







E' finalmente giunto il momento di passare alla cluster analysis in R. Utilizziamo la funzione kmeans, presente nel pacchetto di base stats. In alternativa possiamo utilizzare la funzione Kmeans, presente nel pacchetto amap, che offre maggiori opzioni.
Risolviamo i due esercizi svolti precedentemente.

Esempio 1.R

Innanzitutto creiamo un vettore contenente i valori da clusterizzare. In questo caso vogliamo clusterizzare in base ad un'unica coordinata, ma la funzione ne richiede come minimo 2. E' sufficiente pertanto creare un vettore di 0:


x <- c(1,2,3,7,8,9)
y <- rep(0,6)


A questo punto creiamo una matrice verticale con le coordinate dei 6 punti:


mydata <- cbind(x,y)
mydata
x y
[1,] 1 0
[2,] 2 0
[3,] 3 0
[4,] 7 0
[5,] 8 0
[6,] 9 0


Possiamo ora utilizzare la funzione kmeans, supponendo di voler creare 2 cluster:


clusters <- kmeans(mydata, 2)
clusters
K-means clustering with 2 clusters of sizes 3, 3

Cluster means:
x y
1 2 0
2 8 0

Clustering vector:
[1] 1 1 1 2 2 2

Within cluster sum of squares by cluster:
[1] 2 2

Available components:
[1] "cluster" "centers" "withinss" "size"


Nell'output della funzione possiamo leggere che sono stati creati 2 clusters, di dimensioni 3 e 3. Viene calcolata la media dei valori per ogni cluster e il vettore di clustering.
Se vogliamo conoscere le coordinate dei centroidi, digitiamo:


clusters$center
x y
1 2 0
2 8 0


E questi valori coincidono con quelli calcolati by-hand. Se vogliamo plottare il risultato, usiamo il seguente codice:


plot(mydata, col = clusters$cluster, pch=15)
points(clusters$centers, col = 1:2, pch = 8, cex=2)


Il risultato è identico a quello dell'ultimo grafico dell'esercizio 1, visto sopra.




Esempio 2.R

Il codice è:


x <- c(1,2,3,10,10,12)
y <- c(2,4,2,8,10,9)
mydata <- cbind(x,y)
clust <- kmeans(mydata, 2)
clust
K-means clustering with 2 clusters of sizes 3, 3

Cluster means:
x y
1 2.00000 2.666667
2 10.66667 9.000000

Clustering vector:
[1] 1 1 1 2 2 2

Within cluster sum of squares by cluster:
[1] 4.666667 4.666667

Available components:
[1] "cluster" "centers" "withinss" "size"

plot(mydata, col = clust$cluster, pch=15)
points(clust$centers, col = 1:2, pch = 8, cex=2)





Alcune varianti.
Finora abbiamo applicato la funzione l'algoritmo K-means, utilizzando per la distanza dewi punti dal centroide la funzione euclidea. Esistono alcune varianti, che utilizzano altre funzioni di distanza (disponibili anche in R), come ad esempio:

Manhattan distance:


Canberra dissimilarity:


Spearman dissimilarity:


Queste ed altre funzioni di dissimilarità possono essere utilizzate per il clustering con l'algoritmo K-means, e sono disponibili nella funzione Kmeans del pacchetto amap, specificando il method=c("euclidean", "maximum", "manhattan", "canberra", "binary", "pearson" , "correlation", "spearman", "kendall").

9 commenti:

  1. Credo sia la prima volta che lo capisco appieno...ti ringrazio!!!
    ch3o

    RispondiElimina
  2. Non vedo l'ora di giocare un po' coi i miei dati. Grazie.

    gunzapper

    RispondiElimina
  3. per caso sapete come si faccia ad implementare un K-nn stimatore?
    Dopo aver fatto x<-rnorm(100) voglio stimare la densità con il kth Nearest Neighbor..

    Grazie

    RispondiElimina
  4. Complimenti per l'ottimo lavoro innanzitutto! Sono un completo neofita di R, sto cercando di riprodurre un codice di pattern recognition che avevo scritto in Matlab ma che devo trasferire per vari motivi su un software libero...il primo passo sarebbe proprio attuare una classificazione mediante k-means, ma ottengo questo errore:
    Errore in do_one(nmeth) :
    NA/NaN/Inf in chiamata a funzione esterna (arg 1)
    Inoltre: Warning messages:
    1: In do_one(nmeth) : si è prodotto un NA per coercizione
    2: In do_one(nmeth) : si è prodotto un NA per coercizione

    Ho cercato ovunque ma onestamente non riesco proprio a capire quale sia il problema..

    RispondiElimina
  5. Ce l'ho fatta...grazie mille comunque per il bellissimo blog, grazie ai tuoi esempi sto riuscendo a fare operazioni relativamente avanzate con R dopo un giorno che ho iniziato ad usarlo!

    RispondiElimina
  6. salve a tutti...premetto che non sono molto pratica di R e ho trovato il sito davvero interessante..vorrei sapere come si fa a fare dei cluster basandomi su più attributi? ad esempio: ho un insieme di persone caratterizzate da età e sesso e vorrei raggrupparli in base ad entrambi gli attributi..grazie

    RispondiElimina
  7. Grazie per l'ottimo lavoro. Vorrei chiederle gentilmente come disegnare il grafico del dendogramma utilizzando la distanza euclidea AL QUADRATO ed il metodo di Ward (ward.D2).

    RispondiElimina
  8. Non riesco a far uscire l'agglomerazione con il metodo ward. Le mie variabili sono già standardizzate, ma non riconosce la formula agglo(). Qualcuno può aiutarmi?

    RispondiElimina
  9. Non riesco a far uscire l'agglomerazione con il metodo ward. Le mie variabili sono già standardizzate, ma non riconosce la formula agglo(). Qualcuno può aiutarmi?

    RispondiElimina