Come calcolare le distanze tra centroidi e matrice di dati (per algoritmo kmeans)

Question

Sono uno studente di clustering e R. Per ottenere una migliore presa di entrambi mi piacerebbe calcolare la distanza tra centroidi e la mia matrice xy per ogni iterazione finché "converge". Come posso risolvere i passaggi 2 e 3 usando R?

library(fields) 
x<-c(3,6,8,1,2,2,6,6,7,7,8,8) 
y<-c(5,2,3,5,4,6,1,8,3,6,1,7) 

df<-data.frame(x,y) initial matrix 
a<-c(3,6,8) 
b<-c(5,2,3) 

df1<-data.frame(a,b)# initial centroids 

Ecco cosa voglio fare:

1. I0 < - t (rdist (df, DF1)) # dopo lo zero iterazione
2. oggetti cluster basato su distanza minima
3. Determinazione i centroidi basati sulla media del cluster
4. Ripetizione con I1

Ho provato la funzione kmea. Ma per alcuni motivi produce quei centroidi che devono venire alla fine. Cioè ho definito l'inizio:

start <- matrix(c(3,5,6,2,8,3), 3, byrow = TRUE) 
cluster <- kmeans(df,centers = start, iter.max = 1)# one iteration 

Kmeans non mi permette di seguire i movimenti dei centroidi. Quindi mi piacerebbe farlo "manualmente" applicando il passaggio 2 & 3 usando R.

Answer 1

La tua domanda principale sembra essere come calcolare le distanze tra una matrice di dati e qualche insieme di punti ("centri").

Per questo è possibile scrivere una funzione che prende come input una matrice di dati e il set di punti e restituisce le distanze per ogni riga (punto) nella matrice di dati per tutti i "centri".

Ecco una tale funzione:

myEuclid <- function(points1, points2) { 
    distanceMatrix <- matrix(NA, nrow=dim(points1)[1], ncol=dim(points2)[1]) 
    for(i in 1:nrow(points2)) { 
     distanceMatrix[,i] <- sqrt(rowSums(t(t(points1)-points2[i,])^2)) 
    } 
    distanceMatrix 
} 

points1 è la matrice di dati con i punti come righe e dimensioni come colonne. points2 è la matrice dei centri (punti come di nuovo le righe). La prima riga di codice definisce semplicemente la matrice di risposte (che avrà tante righe quante sono le righe nella matrice di dati e tutte le colonne quanti sono i centri). Quindi il punto i,j nella matrice dei risultati sarà la distanza dallo con il punto al centro .

Quindi il ciclo for scorre su tutti i centri. Per ogni centro calcola la distanza euclidea da ciascun punto al centro corrente e restituisce il risultato. Questa riga qui: sqrt(rowSums(t(t(points1)-points2[i,])^2)) è la distanza euclidea. Ispezionala più vicino e consulta la formula se hai problemi con quello. (le trasposizioni sono fatte principalmente per assicurarsi che la sottrazione venga eseguita in senso decrescente).

Ora è possibile anche implementare algoritmo k-means:

myKmeans <- function(x, centers, distFun, nItter=10) { 
    clusterHistory <- vector(nItter, mode="list") 
    centerHistory <- vector(nItter, mode="list") 

    for(i in 1:nItter) { 
     distsToCenters <- distFun(x, centers) 
     clusters <- apply(distsToCenters, 1, which.min) 
     centers <- apply(x, 2, tapply, clusters, mean) 
     # Saving history 
     clusterHistory[[i]] <- clusters 
     centerHistory[[i]] <- centers 
    } 

    list(clusters=clusterHistory, centers=centerHistory) 
} 

Come si può vedere è anche una funzione molto semplice - ci vuole matrice di dati, centri, la vostra funzione di distanza (quello definito sopra) e il numero di delle iterazioni desiderate

I cluster sono definiti assegnando il centro più vicino per ciascun punto. E i centri vengono aggiornati come media dei punti assegnati a quel centro. Che è un algoritmo di base k-means).

Proviamo.Definire alcuni punti casuali (in 2d, quindi il numero di colonne = 2)

mat <- matrix(rnorm(100), ncol=2) 

Assegnare 5 punti casuali da quella matrice come centri iniziali:

centers <- mat[sample(nrow(mat), 5),] 

Ora eseguire l'algoritmo:

theResult <- myKmeans(mat, centers, myEuclid, 10) 

Ecco i centri nella decima iterazione:

theResult$centers[[10]] 
     [,1]  [,2] 
1 -0.1343239 1.27925285 
2 -0.8004432 -0.77838017 
3 0.1956119 -0.19193849 
4 0.3886721 -1.80298698 
5 1.3640693 -0.04091114 

Confronti che, con implementata la funzione kmeans:

theResult2 <- kmeans(mat, centers, 10, algorithm="Forgy") 

theResult2$centers 
     [,1]  [,2] 
1 -0.1343239 1.27925285 
2 -0.8004432 -0.77838017 
3 0.1956119 -0.19193849 
4 0.3886721 -1.80298698 
5 1.3640693 -0.04091114 

funziona bene. La nostra funzione traccia comunque le iterazioni. Siamo in grado di tracciare i progressi nel corso dei primi 4 iterazioni come questo:

par(mfrow=c(2,2)) 
for(i in 1:4) { 
    plot(mat, col=theResult$clusters[[i]], main=paste("itteration:", i), xlab="x", ylab="y") 
    points(theResult$centers[[i]], cex=3, pch=19, col=1:nrow(theResult$centers[[i]])) 
} 

Nizza.

Tuttavia questo semplice design consente molto di più. Ad esempio, se vogliamo utilizzare un altro tipo di distanza (non euclidea), possiamo semplicemente utilizzare qualsiasi funzione che consideri i dati e i centri come input. Ecco uno per le distanze di correlazione:

myCor <- function(points1, points2) { 
    return(1 - ((cor(t(points1), t(points2))+1)/2)) 
} 

E noi poi possiamo fare Kmeans sulla base di quelli:

theResult <- myKmeans(mat, centers, myCor, 10) 

L'immagine risultante per 4 iterazioni sembra poi così:

Anche tu hai specificato 5 cluster - ce ne sono rimasti 2 alla fine. Questo perché per le 2 dimensioni la correlazione può avere valori - +1 o -1. Quindi, quando si cercano i cluster, ogni punto viene assegnato a un centro, anche se ha la stessa distanza da più centri: il primo viene scelto.

Ad ogni modo questo è ora fuori portata. La linea di fondo è che ci sono molte metriche di distanza possibili e una semplice funzione consente di utilizzare qualsiasi distanza desiderata e tracciare i risultati su iterazioni.