Clustering mit einer Abstandsmatrix - Algorithmus, Matrix, Clusteranalyse, Abstand

Ich habe eine (symmetrische) Matrix M das repräsentiert den Abstand zwischen jedem Knotenpaar. Beispielsweise,

A B C D E F G H I J K L EIN0 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

Gibt es eine Methode zum Extrahieren von Clustern? M (Bei Bedarf kann die Anzahl der Cluster festgelegt werden), so dass jeder Cluster Knoten mit kleinen Abständen zwischen ihnen enthält. In dem Beispiel wären die Cluster (A, B, C, D), (E, F, G, H) und (I, J, K, L).

Danke vielmals :)

Antworten:

Hierarchisches Clustering arbeitet stattdessen direkt mit der Entfernungsmatrixder tatsächlichen Beobachtungen. Wenn Sie die Anzahl der Cluster kennen, kennen Sie bereits Ihr Stoppkriterium (Stopp bei k-Clustern). Der Haupttrick hier wird sein, ein passendes zu wählen Verknüpfungsmethode. Ebenfalls, dieses Papier(pdf) gibt einen ausgezeichneten Überblick über alle Arten von Clustering-Methoden.

Ein weiterer möglicher Weg ist die Verwendung Partitionierung um Medoids die oft K-Medoids genannt werden. Wenn Sie sich das R-Clustering-Paket ansehen, werden Sie sehen Pam Funktion, die die Entfernungsmatrix als Eingabedaten erhält.

Nun, es ist möglich, K-Mittel durchzuführenClustering auf einer gegebenen Ähnlichkeitsmatrix, zuerst müssen Sie die Matrix zentrieren und dann die Eigenwerte der Matrix nehmen. Der letzte und der wichtigste Schritt ist die Multiplikation der ersten beiden Eigenvektoren mit der Quadratwurzel der Diagonalen der Eigenwerte, um die Vektoren zu erhalten, und dann weiter mit K-Mitteln. Unter dem Code zeigt, wie es geht. Sie können die Ähnlichkeitsmatrix ändern. fpdist ist die Ähnlichkeitsmatrix.

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)