Klastrowanie z matrycą odległościową

Question

Mam (symetryczną) macierz M, która reprezentuje odległość między każdą parą węzłów. Na przykład,

 
    A B C D E F G H I J K L 
A 0 20 20 20 40 60 60 60 100 120 120 120 
B 20 0 20 20 60 80 80 80 120 140 140 140 
C 20 20 0 20 60 80 80 80 120 140 140 140 
D 20 20 20 0 60 80 80 80 120 140 140 140 
E 40 60 60 60 0 20 20 20 60 80 80 80 
F 60 80 80 80 20 0 20 20 40 60 60 60 
G 60 80 80 80 20 20 0 20 60 80 80 80 
H 60 80 80 80 20 20 20 0 60 80 80 80 
I 100 120 120 120 60 40 60 60 0 20 20 20 
J 120 140 140 140 80 60 80 80 20 0 20 20 
K 120 140 140 140 80 60 80 80 20 20 0 20 
L 120 140 140 140 80 60 80 80 20 20 20 0 

jest jakiś sposób wyodrębnić klastry M (jeżeli jest to konieczne, liczba klastrów może być stała) tak, że każdy klaster zawiera węzły z niewielkich odległościach między nimi. W tym przykładzie klastry będą następujące: (A, B, C, D), (E, F, G, H) i (I, J, K, L).

Thanks a lot :)

Answer 1

Hierarchical clustering współpracuje bezpośrednio z macierzy odległości zamiast rzeczywistych obserwacjach. Jeśli znasz liczbę klastrów, już znasz swoje kryterium zatrzymania (zatrzymaj się, gdy jest k klastrów). Główną opcją tutaj będzie wybranie odpowiedniego linkage method. Ponadto, this paper (pdf) daje doskonały przegląd wszystkich rodzajów metod grupowania.

Answer 2

Jeszcze jednym sposobem jest użycie Partitioning Around Medoids, który często nazywa się K-Medoidami. Jeśli spojrzysz na pakiet R-clustering, zobaczysz funkcję pam, która otrzyma matrycę odległości jako dane wejściowe.

Answer 3

Cóż, możliwe jest przeprowadzenie grupowania K-średnich na danej macierzy podobieństwa, najpierw trzeba wyśrodkować macierz, a następnie pobrać wartości własne macierzy. Ostatnim i najważniejszym krokiem jest przemnożenie pierwszych dwóch zestawów wektorów własnych do pierwiastka kwadratowego z przekątnych wartości własnych, aby uzyskać wektory, a następnie przejść za pomocą K-średnich. Poniżej kodu pokazano, jak to zrobić. Możesz zmienić macierz podobieństwa. fpdist jest macierzą podobieństwa.

mds.tau <- function(H) 
{ 
    n <- nrow(H) 
    P <- diag(n) - 1/n 
    return(-0.5 * P %*% H %*% P) 
    } 
    B<-mds.tau(fpdist) 
    eig <- eigen(B, symmetric = TRUE) 
    v <- eig$values[1:2] 
    #convert negative values to 0. 
v[v < 0] <- 0 
X <- eig$vectors[, 1:2] %*% diag(sqrt(v)) 
library(vegan) 
km <- kmeans(X,centers= 5, iter.max=1000, nstart=10000) . 
#embedding using MDS 
cmd<-cmdscale(fpdist)