Ist es in Ordnung, Manhattan-Distanz mit der Cluster-Verknüpfung von Ward in hierarchischen Clustern zu verwenden?

15

Ich verwende hierarchisches Clustering, um Zeitreihendaten zu analysieren. Mein Code wird mit der Mathematica- Funktion implementiert DirectAgglomerate[...], die unter Berücksichtigung der folgenden Eingaben hierarchische Cluster generiert:

eine Distanzmatrix D
Der Name der Methode, die zur Bestimmung der Cluster-Verknüpfung verwendet wird.

Ich habe die Distanzmatrix D mit Manhattan-Distanz berechnet:

d (x, y) = \sum_{i} | x_{i} - y_{i} |

$d(x,y) = \sum_i|x_i - y_i|$

Dabei ist und die Anzahl der Datenpunkte in meiner Zeitreihe. $i = 1,\cdots, n$ $n \approx 150$

Meine Frage ist, ist es in Ordnung, die Inter-Cluster-Verknüpfung von Ward mit einer Manhattan-Distanzmatrix zu verwenden? Einige Quellen schlagen vor, dass die Verknüpfung von Ward nur mit euklidischer Distanz verwendet werden sollte.

Beachten Sie, dass DirectAgglomerate[...]die Verknüpfung von Ward nur anhand der Entfernungsmatrix berechnet wird, nicht anhand der ursprünglichen Beobachtungen. Leider bin ich mir nicht sicher, wie Mathematica den ursprünglichen Algorithmus von Ward modifiziert, der (nach meinem Verständnis) durch Minimierung der Fehlersumme der Quadrate der Beobachtungen, berechnet in Bezug auf den Clustermittelwert, funktioniert. Für einen Cluster , der aus einem Vektor univariater Beobachtungen besteht, formulierte Ward beispielsweise die Fehlersumme der Quadrate wie folgt: $c$

(\sum_{j} | | c_{j} - m e ein n (c) | |_{2})^{2}

$(\sum_j||c_j - mean(c)||_2)^2$

(Andere Software - Tools wie Matlab und R auch Wards Clustering implementieren nur eine Entfernung Matrix , so dass die Frage nicht spezifisch für Mathematica ist.)

clustering distance-functions ward Rachel
quelle

Ich habe kürzlich einen ziemlich großen Datensatz mit der Ward-Methode analysiert. In meinem speziellen Fall ergab die Entfernung von Manatthan im Wesentlichen die gleiche Häufung wie die euklidische Entfernung. Ich kann Ihnen keinen mathematischen Beweis für eine Kombination von Methoden liefern, aber - zumindest in meinem Fall - das Clustering wurde von der Distanzmethode nicht beeinflusst

nico

Alle R-Funktionen warten nicht unbedingt auf eine Distanzmatrix. Siehe z. B. die Online-Hilfe agnesim Cluster- Paket.

Chl

Es ist eigentlich in Ordnung, jede Entfernung zu verwenden. Check vlado.fmf.uni-lj.si/pub/preprint/ward.pdf Der einzige Haken ist, dass der Mittelwert, von dem wir sprechen, nicht mehr der arithmetische Mittelwert ist, sondern der Mittelwert von Frechet.

Randy Lai

Aber können wir Manhattan Distance für die vollständige Verknüpfung verwenden?

Payel Banerjee

8

Der Ward-Clustering-Algorithmus ist eine hierarchische Clustering-Methode, die bei jedem Schritt ein Trägheitskriterium minimiert. Diese Trägheit quantifiziert die Summe der quadrierten Residuen zwischen dem reduzierten Signal und dem Anfangssignal: Sie ist ein Maß für die Varianz des Fehlers in einem 12 (euklidischen) Sinn. Eigentlich erwähnen Sie es sogar in Ihrer Frage. Aus diesem Grund ist es meines Erachtens sinnlos, sie auf eine Distanzmatrix anzuwenden, die keine 12-euklidische Distanz ist.

Andererseits wäre eine durchschnittliche Verknüpfung oder eine hierarchische Clusterbildung mit einer einzelnen Verknüpfung für andere Entfernungen perfekt geeignet.

Gael Varoquaux
quelle

2

Vielen Dank für Ihren Kommentar; Ich denke du hast recht. In der Praxis scheint es jedoch, dass die Verknüpfung von Ward häufig mit nicht-euklidischen Abständen verwendet wird. Ich bin mir immer noch nicht sicher, welche Auswirkungen dies haben könnte.

Rachel

Es kommt wahrscheinlich von Leuten, die Ward benutzen, nur weil es bekannt ist. Ich würde sagen, dass Ward im Vergleich zu einer durchschnittlichen Verknüpfung in diesen Einstellungen keinen Gewinn bringt. Dies ist jedoch rechenintensiver (Sie müssen die ersten beiden Momente für jede Zusammenführung berechnen oder vorberechnen). Aus pragmatischer Sicht würde ich mich also einfach für eine durchschnittliche Verknüpfung entscheiden.

Gael Varoquaux

1

Tatsächlich würde die Trägheit mit der Summe der quadratischen Abstände definiert (nicht erforderlich, um euklidisch zu sein), siehe vlado.fmf.uni-lj.si/pub/preprint/ward.pdf

Randy Lai,

5

Ich kann mir keinen Grund vorstellen, warum Ward eine Metrik bevorzugen sollte. Die Methode von Ward ist nur eine weitere Option, um zu entscheiden, welche Cluster während der Agglomeration als nächstes fusioniert werden sollen. Dies wird erreicht, indem zwei Cluster gefunden werden, deren Fusion einen bestimmten Fehler minimiert (Beispielquelle für die Formel ).

Daher stützt es sich auf zwei Konzepte:

Der Mittelwert der Vektoren, die (für numerische Vektoren) im Allgemeinen durch Mittelung über jede Dimension separat berechnet werden.
Die Distanzmetrik selbst, dh das Konzept der Ähnlichkeit, das durch diese Metrik ausgedrückt wird.

Also: Solange die Eigenschaften der ausgewählten Metrik (wie z. B. Drehung, Verschiebung oder Skalierungsinvarianz) Ihren Anforderungen entsprechen (und die Metrik der Art und Weise entspricht, wie der Clustermittelwert berechnet wird), sehe ich keinen Grund, sie nicht zu verwenden .

Ich vermute, dass die meisten Leute die euklidische Metrik vorschlagen, weil sie

das Gewicht der Differenzen zwischen einem Cluster-Mittelwert und einem einzelnen Beobachtungsvektor erhöhen möchten (dies erfolgt durch Quadration)
oder weil es sich aufgrund seiner Daten als beste Metrik bei der Validierung herausstellte
oder weil es allgemein verwendet wird.

steffen
quelle

Vielen Dank für Ihre Antwort. Ich habe meine Frage ein wenig geklärt, um hervorzuheben, dass der DirectAgglomerate-Algorithmus [...] nur eine Distanzmatrix verwendet. Würde die modifizierte Implementierung von Wards Verknüpfung auf der Annahme basieren, dass die Distanzmatrix euklidisch ist? Die Implementierung der Ward-Verknüpfung durch Matlab stellt beispielsweise fest, dass sie nur für euklidische Entfernungen geeignet ist ( mathworks.com/help/toolbox/stats/linkage.html ).

Rachel

1

@ Rachel: aaah, ich verstehe. Jede Stationsimplementierung muss den Abstand zwischen Clustermitgliedern und dem Schwerpunkt berechnen. Intuitiv ist klar, dass die verwendete Metrik der Metrik zur Berechnung der Entfernungen zwischen Beobachtungen entsprechen sollte. Daher benötigt matlab eine euklidische Distmatrix. Nun stellt sich jedoch die Frage, warum Implementierungen keine Funktion anstelle einer Distanzmatrix anfordern. Wie viel Schaden wird angerichtet, wenn für beide Aufgaben unterschiedliche Metriken verwendet werden? Ich gebe zu, ich weiß es nicht richtig.

Steffen

Hallo Beispiel entfernt. irgendeine andere Website?

MonsterMMORPG

2

$\ell_1$ $\ell_1$ $\ell_1$

Suresh Venkatasubramanian
quelle

Ist es in Ordnung, Manhattan-Distanz mit der Cluster-Verknüpfung von Ward in hierarchischen Clustern zu verwenden?

Antworten: