Jak obliczyć odległość między centroidami a matrycą danych (dla algorytmu kmeans)

Question

Jestem studentem klastrowania i R. Aby uzyskać lepszą przyczepność obu, chciałbym obliczyć odległość między centroidami a moją matrycą xy dla każdej iteracji, aż "zbierze się". Jak mogę rozwiązać etapy 2 i 3, używając 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 

Oto, co chcę zrobić:

1. I0 < - T (rdist (DF, DF1)) # po zerowej iteracji
2. obiekty klastrowe oparte na minimalnej odległości
3. Ustalenie centroidy oparte na średniej klastra
4. Powtórzenie z I1

Próbowałem funkcji kmeans. Ale z pewnych powodów produkuje centroidy, które muszą pojawić się na końcu. Tak zdefiniowałem początek:

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

Kmeans nie pozwala mi śledzić ruchu centroidów. Dlatego chciałbym zrobić to "ręcznie", stosując krok 2 & 3 używając R.

Answer 1

Twoje główne pytanie wydaje się być jak obliczyć odległości między matrycą danych i niektórych zestaw punktów ("centra").

W tym celu można napisać funkcję, która pobiera jako dane wejściową macierz danych i zestaw punktów oraz zwraca odległości dla każdego wiersza (punktu) w macierzy danych do wszystkich "centrów".

tutaj jest taka funkcja:

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 macierz danych z punktów jak wierszy i wymiary jak kolumny. points2 to macierz centrów (punkty ponownie jako wiersze). Pierwszy wiersz kodu definiuje właśnie matrycę odpowiedzi (która będzie miała tyle wierszy, ile jest wierszy w macierzy danych i tyle kolumn, ile jest centrów). Tak więc punkt i,j w macierzy wyników będzie odległością od centrum z do centrum j..

Następnie pętla for iteruje po wszystkich centrach. Dla każdego centrum oblicza odległość euklidesową z każdego punktu do bieżącego centrum i zwraca wynik. Ta linia tutaj: sqrt(rowSums(t(t(points1)-points2[i,])^2)) jest odległością euklidesową. Sprawdź go bliżej i sprawdź wzór, jeśli masz z tym jakieś kłopoty. (transpozycje są wykonywane głównie w celu upewnienia się, że odejmowanie odbywa się wierszowo).

Teraz można również realizować metodą k-średnich algorytmu:

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) 
} 

Jak widać jest to również bardzo prosta czynność - to trwa macierz danych, centra, swoją funkcję odległości (zdefiniowany powyżej) i numer pożądanych iteracji.

Klastry definiowane są przez przypisanie najbliższego środka dla każdego punktu. Centra są aktualizowane jako średnia punktów przypisanych do tego centrum. Który jest podstawowym algorytmem k-średnich).

Spróbujmy.Zdefiniować kilka losowo punktów (2D, więc liczba kolumn = 2)

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

Przypisanie 5 losowo punktów z tej matrycy jako początkowych punktów:

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

już uruchomić algorytmu:

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

Oto centra w 10. iteracji:

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 

Porównaj to z realizowanego kmeans funkcję:

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 

działa dobrze. Nasza funkcja śledzi jednak iteracje. Możemy wykreślić postępy w ciągu pierwszych 4 iteracjach jak ten:

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]])) 
} 

Nicea.

Jednak ta prosta konstrukcja pozwala na znacznie więcej. Na przykład, jeśli chcemy użyć innego rodzaju odległości (nie euklidesowej), możemy po prostu użyć dowolnej funkcji, która pobiera dane i centra jako dane wejściowe. Oto jeden dla odległości korelacji:

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

I wtedy można zrobić Kmeans na podstawie tych:

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

Uzyskany obraz na 4 iteracjach wówczas wygląda następująco:

Nawet ty podałeś 5 klastrów - na końcu pozostały 2. Dzieje się tak dlatego, że dla 2 wymiarów korelacja może mieć wartości - +1 lub -1. Następnie, szukając klastrów, każdy punkt dostaje przypisany do jednego centrum, nawet jeśli ma on ten sam dystans do wielu centrów - pierwszy zostaje wybrany.

W każdym razie jest to obecnie poza zakresem. Najważniejsze jest to, że istnieje wiele możliwych metryk odległości, a jedna prosta funkcja pozwala na użycie dowolnej odległości i śledzenie wyników w kolejnych iteracjach.