/ / Klastrowanie z macierzą odległościową - algorytm, macierz, analiza skupień, odległość

Grupowanie za pomocą macierzy odległości - algorytm, macierz, analiza skupień, odległość

Mam macierz (symetryczną) M który 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 ZA0 20 20 20 40 60 60 60 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

Czy istnieje metoda wyodrębniania klastrów z M (w razie potrzeby można ustalić liczbę klastrów), tak aby każdy klaster zawierał węzły o niewielkich odległościach między nimi. W tym przykładzie będą to klastry (A, B, C, D), (E, F, G, H) i (I, J, K, L).

Wielkie dzięki :)

Odpowiedzi:

7 dla odpowiedzi № 1

Hierarchiczne grupowanie działa bezpośrednio z matrycą odległościz faktycznych obserwacji. Jeśli znasz liczbę klastrów, już znasz swoje kryterium zatrzymania (zatrzymaj się, gdy jest k klastrów). Główną opcją tutaj będzie wybór odpowiedniego metoda łączenia. Również, ten papier(pdf) daje doskonały przegląd wszystkich rodzajów metod grupowania.


2 dla odpowiedzi nr 2

Wykorzystywany jest jeszcze jeden możliwy sposób Partycjonowanie wokół medoidów który często nazywał się K-Medoidami. Jeśli spojrzysz na pakiet R-clustering, zobaczysz pam funkcja, która otrzymuje matrycę odległości jako dane wejściowe.


0 dla odpowiedzi № 3

Cóż, możliwe jest wykonanie K-średnichklastrowanie na podanej macierzy podobieństwa, najpierw musisz 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)