Clustering mit einer Distanzmatrix

52

Ich habe eine (symmetrische) Matrix M, die den Abstand zwischen jedem Knotenpaar darstellt. Zum Beispiel,

    ABCDEFGHIJKL
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

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

Ich habe bereits UPGMA und k-means ausprobiert, aber die resultierenden Cluster sind sehr schlecht.

Die Entfernungen sind die durchschnittlichen Schritte, die ein Zufallsläufer unternehmen würde, um von Knoten Azu Knoten B( != A) und zurück zu Knoten zu gelangen A. Es ist garantiert, dass M^1/2es sich um eine Metrik handelt. Um k-means auszuführen, benutze ich den Schwerpunkt nicht. Ich definiere die Entfernung zwischen nKnotencluster cals die durchschnittliche Entfernung zwischen nund allen Knoten in c.

Danke vielmals :)

clustering Yassin
quelle

1

Sie sollten erwägen, die Informationen, die Sie bereits versucht haben, UPGMA (und andere, die Sie möglicherweise versucht haben) hinzuzufügen :)

Björn Pollex

1

Ich habe eine Frage. Warum sagten Sie, dass die k-means schlecht abschnitten? Ich habe Ihre Matrix an k-means übergeben und sie hat perfekt geclustert. Haben Sie den Wert von k (Anzahl der Cluster) nicht an k-means übergeben?

3

@ user12023 Ich denke du hast die Frage falsch verstanden. Die Matrix ist keine Reihe von Punkten - es sind die paarweisen Abstände zwischen ihnen. Sie können den Schwerpunkt einer Punktsammlung nicht berechnen, wenn Sie nur die Abstände zwischen ihnen (und nicht ihre tatsächlichen Koordinaten) angeben, zumindest nicht auf offensichtliche Weise.

Stumpy Joe Pete

7

k-means unterstützt keine Distanzmatrizen . Es werden niemals Punkt-zu-Punkt-Entfernungen verwendet. Ich kann also nur davon ausgehen , dass Ihre Matrix als Vektoren neu interpretiert und auf diesen Vektoren ausgeführt wurde. Vielleicht geschah das Gleiche für die anderen Algorithmen, die Sie ausprobiert haben: Sie haben Rohdaten erwartet , und Sie haben eine Distanzmatrix übergeben.

Anony-Mousse

38

Es gibt eine Reihe von Optionen.

k-medoids Clustering

Erstens könnten Sie versuchen, die Partitionierung um Medoids (Pam) herum vorzunehmen, anstatt k-means Clustering zu verwenden. Dieser ist robuster und könnte bessere Ergebnisse liefern. Van der Laan überarbeitete den Algorithmus. Wenn Sie es selbst implementieren wollen, ist sein Artikel eine Lektüre wert.

Es gibt einen speziellen k-medoids-Clustering-Algorithmus für große Datensätze. Der Algorithmus heißt in R Clara und wird in Kapitel 3 unter Suchen von Gruppen in Daten: Eine Einführung in die Clusteranalyse beschrieben. von Kaufman, L und Rousseeuw, PJ (1990).

hierarchisches Clustering

Anstelle von UPGMA können Sie auch andere hierarchische Clusteroptionen ausprobieren. Stellen Sie zunächst sicher, dass Sie die Partitionierungsmethode richtig definieren, wenn Sie hierarchisches Clustering verwenden. Bei dieser Aufteilungsmethode werden im Wesentlichen die Abstände zwischen Beobachtungen und Clustern berechnet. Ich verwende meistens die Methode von Ward oder die vollständige Verknüpfung, aber andere Optionen könnten die Wahl für Sie sein.

Ich weiß nicht, ob Sie es bereits ausprobiert haben, aber in phylogenetischen Anwendungen wird häufig die Einzelverbindungsmethode oder der Nachbarbeitritt der UPGMA vorgezogen. Wenn Sie es noch nicht probiert haben, können Sie es auch ausprobieren, da es oft bemerkenswert gute Ergebnisse liefert.

In R können Sie einen Blick auf das Paket- Cluster werfen . Dort sind alle beschriebenen Algorithmen implementiert. Siehe? Pam,? Clara,? Hclust, ... Überprüfen Sie auch die unterschiedliche Implementierung des Algorithmus in? Kmeans. Manchmal kann die Auswahl eines anderen Algorithmus die Clusterbildung erheblich verbessern.

EDIT: Nur eine Überlegung: Wenn Sie mit Graphen und Knoten und dergleichen arbeiten, sollten Sie sich auch den Markov-Clustering-Algorithmus ansehen. Diese wird zum Beispiel zum Gruppieren von Sequenzen verwendet, die auf Explosionsähnlichkeiten basieren, und funktioniert unglaublich gut. Es kann das Clustering für Sie übernehmen oder Ihnen einige Ideen zur Lösung des Forschungsproblems geben, auf das Sie sich konzentrieren. Ohne etwas darüber zu wissen, denke ich, dass seine Ergebnisse definitiv einen Blick wert sind. Wenn ich so sagen darf, halte ich diese Methode von Stijn van Dongen immer noch für eines der schönsten Ergebnisse bei der Clusterbildung, die mir je begegnet sind.

http://www.micans.org/mcl/

Joris Meys
quelle

22

Eine Möglichkeit, Cluster auf Ihrer Distanzmatrix hervorzuheben, ist die mehrdimensionale Skalierung . Bei der Projektion von Personen (hier, wie Sie Ihre Knoten nennen) in einem 2D-Raum bietet es eine mit PCA vergleichbare Lösung. Da dies nicht überwacht wird, können Sie die Anzahl der Cluster nicht von vornherein angeben, aber ich denke, es kann hilfreich sein, eine bestimmte Distanz- oder Ähnlichkeitsmatrix schnell zusammenzufassen.

Folgendes würden Sie mit Ihren Daten erhalten:

tmp <- matrix(c(0,20,20,20,40,60,60,60,100,120,120,120,
                20,0,20,20,60,80,80,80,120,140,140,140,
                20,20,0,20,60,80,80,80,120,140,140,140,
                20,20,20,0,60,80,80,80,120,140,140,140,
                40,60,60,60,0,20,20,20,60,80,80,80,
                60,80,80,80,20,0,20,20,40,60,60,60,
                60,80,80,80,20,20,0,20,60,80,80,80,
                60,80,80,80,20,20,20,0,60,80,80,80,
                100,120,120,120,60,40,60,60,0,20,20,20,
                120,140,140,140,80,60,80,80,20,0,20,20,
                120,140,140,140,80,60,80,80,20,20,0,20,
                120,140,140,140,80,60,80,80,20,20,20,0),
              nr=12, dimnames=list(LETTERS[1:12], LETTERS[1:12]))
d <- as.dist(tmp)
mds.coor <- cmdscale(d)
plot(mds.coor[,1], mds.coor[,2], type="n", xlab="", ylab="")
text(jitter(mds.coor[,1]), jitter(mds.coor[,2]),
     rownames(mds.coor), cex=0.8)
abline(h=0,v=0,col="gray75")

mds

Ich habe ein kleines Jittering an den x- und y-Koordinaten hinzugefügt, um Fälle unterscheiden zu können. Ersetzen Sie diese tmpdurch, 1-tmpwenn Sie lieber mit Unähnlichkeiten arbeiten möchten, dies ergibt jedoch im Wesentlichen dasselbe Bild. Hier ist jedoch die hierarchische Clustering-Lösung mit einzelnen Agglomerationskriterien:

plot(hclust(dist(1-tmp), method="single"))

Sie können die Auswahl von Clustern auf der Grundlage des Dendrogramms oder robusterer Methoden weiter verfeinern, siehe z. B. diese verwandte Frage: Welche Stoppkriterien für agglomeratives hierarchisches Clustering werden in der Praxis verwendet?

chl
quelle

2

Spektrale Clusterung [1] erfordert eine Affinitätsmatrix, wobei die Clusterung durch die ersten Eigenfunktionen der Zerlegung von definiert wird $K$

L = D^{- 1 / 2} A D^{- 1 / 2}

$\textbf{L} = \textbf{D}^{-1/2} \textbf{A} \textbf{D}^{-1/2}$

Mit ist die Affinitätsmatrix der Daten und ist die Diagonalmatrix definiert als (edit: Entschuldigung, aber Sie können eine Affinitätsmatrix aus einer Distanzmatrix erstellen, vorausgesetzt, Sie wissen, dass das Maximum möglich ist / angemessener Abstand als , obwohl auch andere Schemata existieren) $\textbf{A}$ $\textbf{D}$ $A_{ij}=1-d_{ij}/\max(d)$

{\begin{matrix} \begin{aligned} D_{i, i} = \sum_{j} A_{i, j} \\ D_{i \neq j} = 0 \end{aligned} \end{matrix}

$\left\{\begin{matrix}\begin{align}&\textbf{D}_{i,i}=\sum_{j}{\textbf{A}_{i,j}}\\ &\textbf{D}_{i \neq j}=0\end{align}\end{matrix}\right.$

Mit als eigendekomposition von , wobei Eigenfunktionen als Spalten gestapelt sind und nur die größten Eigenvektoren in , definieren wir die zeilennormalisierte Matrix $\textbf{X}$ $\textbf{L}$ $K$ $\textbf{X}$

Y_{i j} = \frac{X_{i j}}{{(\sum_{j} {(X_{i j})}^{2})}^{1 / 2}}

$\textbf{Y}_{ij}=\frac{\textbf{X}_{ij}}{\left(\sum_{j}{\left( \textbf{X}_{ij} \right)^{2}}\right)^{1/2}}$

Jede Zeile von ist ein Punkt in und kann mit einem gewöhnlichen Clustering-Algorithmus (wie K-means) geclustert werden. $\textbf{Y}$ $\mathbb{R}^{k}$

Schauen Sie sich meine Antwort hier an, um ein Beispiel zu sehen: https://stackoverflow.com/a/37933688/2874779

_{[1] Ng, AY, Jordan, MI & Weiss, Y. (2002). Zum spektralen Clustering: Analyse und ein Algorithmus. Fortschritte in neuronalen Informationsverarbeitungssystemen, 2, 849-856. S. 2}

Firebug
quelle

2

Sie versuchen, Knoten eines Graphen oder Netzwerks zu gruppieren, die nahe beieinander liegen. Diesem Problem widmet sich ein ganzes Forschungsgebiet, das manchmal als Community Detection in Netzwerken bezeichnet wird . Wenn Sie Ihr Problem von diesem Standpunkt aus betrachten, können Sie wahrscheinlich die Dinge klarstellen.

Sie werden viele Algorithmen finden, die diesem Problem gewidmet sind, und in der Tat basieren einige von ihnen auf der gleichen Idee, die Sie hatten, nämlich Abstände zwischen Knoten mit zufälligen Schritten zu messen.

Das Problem wird häufig als Modularitätsoptimierung [1] formuliert, bei der die Modularität eines Clusters misst, wie gut das Clustering das Netzwerk in dicht verbundenen Clustern trennt (dh Cluster, in denen Knoten nahe beieinander liegen).

Tatsächlich können Sie zeigen, dass die Modularität der Wahrscheinlichkeit entspricht, dass ein Zufallsläufer nach einem Schritt in denselben Clustern bleibt als ursprünglich abzüglich der gleichen Wahrscheinlichkeit für zwei unabhängige Zufallsläufer [2].

Wenn Sie mehr Schritte für die Zufallsläufer zulassen, suchen Sie nach einer gröberen Gruppierung des Netzwerks. Die Anzahl der Schritte des Random Walks spielt daher die Rolle eines Auflösungsparameters, der es ermöglicht, eine Hierarchie von Clustern wiederherzustellen. In diesem Fall wird die Größe, die die Tendenz von Random Walkern zum Ausdruck bringt, nach t Schritten in ihrem ursprünglichen Cluster zu bleiben, als Markov-Stabilität einer Partition zum Zeitpunkt t [2] bezeichnet und entspricht der Modularität bei t = 1 .

Sie können daher Ihr Problem lösen, indem Sie die Clusterbildung Ihres Diagramms finden, die die Stabilität zu einem bestimmten Zeitpunkt t optimiert , wobei t der Auflösungsparameter ist (ein größeres t ergibt größere Cluster). Eine der am häufigsten verwendeten Methoden zur Optimierung der Stabilität (oder Modularität mit einem Auflösungsparameter) ist der Louvain-Algorithmus [3]. Eine Implementierung finden Sie hier: https://github.com/michaelschaub/generalizedLouvain .

[1] Newman, MEJ & Girvan, M. Ermittlung und Bewertung der Gemeinschaftsstruktur in Netzwerken. Phys. Rev. E 69, 026113 (2004).

[2] Delvenne, J.-C., Yaliraki, SN & Barahona, M. Stabilität von Graphengemeinschaften über Zeitskalen. Proc. Natl. Acad. Sci. 107, 12755–12760 (2010).

[3] Blondel, VD, Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Schnelle Entfaltung von Gemeinschaften in großen Netzwerken. J. Stat. Mech. Theorie-Exp. 2008, P10008 (2008).

Alex B
quelle

1

Nun, es ist möglich, ein K-Mittelwert-Clustering für eine gegebene Ähnlichkeitsmatrix durchzuführen. Zuerst müssen Sie die Matrix zentrieren und dann die Eigenwerte der Matrix nehmen. Der letzte und wichtigste Schritt ist das Multiplizieren der ersten beiden Eigenvektorsätze mit der Quadratwurzel der Diagonalen der Eigenwerte, um die Vektoren zu erhalten und dann mit K-Mitteln fortzufahren. Der folgende 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)

user4959
quelle

0

Bevor Sie versuchen, das Clustering für die Matrix auszuführen, können Sie versuchen, eine der Faktorenanalysetechniken auszuführen und nur die wichtigsten Variablen für die Berechnung der Distanzmatrix beizubehalten. Sie können auch versuchen, Fuzzy-Methoden zu verwenden, die (zumindest nach meiner Erfahrung) in solchen Fällen besser funktionieren. Versuchen Sie zuerst Cmeans, Fuzzy K-medoids und Specially GKCmeans.

mariana weicher
quelle

0

Co-Clustering ist eine der Antworten, die ich denke. Aber ich bin hier kein Experte. Co-clustring ist keine neugeborene Methode, deshalb finden Sie einige Algen in R, Wiki zeigt, dass Konzepte in guter Weise. Eine andere Methode, die nicht erwähnt wird, ist die Graphpartitionierung (aber ich sehe, dass Graph nicht spärlich wäre, die Graphpartitionierung wäre nützlich, wenn Ihre Matrix von Werten dominiert würde, die = maximaler Abstand = keine Ähnlichkeit zwischen den Knoten bedeuten).

Qbik
quelle

0

Sehen Sie sich AFFINITY PROPAGATION an. Diese Technik verwendet die Ähnlichkeitsmatrix als Eingabe und erzeugt eine optimale Anzahl von Clustern zusammen mit einem repräsentativen Beispiel für jeden Cluster.

Jawad Tayyub
quelle

2

Könnten Sie dies erläutern und erläutern, wie diese Methode in diesem Fall hilft?

Andy

0

Konvertieren Sie zuerst die Distanzmatrix über https://math.stackexchange.com/a/423898 in eine Koordinatenmatrix. Anschließend können Sie problemlos jeden vorhandenen Clustering-Algorithmus effektiv verwenden.

Micheal Avery
quelle

0

Sie können auch den Kruskal-Algorithmus verwenden, um minimale Spannweiten zu finden, die jedoch enden, sobald Sie die drei Cluster erhalten. Ich habe es auf diese Weise versucht und es entstehen die von Ihnen erwähnten Cluster: {ABCD}, {EFGH} und {IJKL}.

Luis Pargas Carmona
quelle

Clustering mit einer Distanzmatrix

Antworten:

k-medoids Clustering

hierarchisches Clustering