Muss eine Entfernung eine „Metrik“ sein, damit ein hierarchisches Clustering darauf gültig ist?

9

Nehmen wir an, wir definieren einen Abstand zwischen N Elementen , der keine Metrik ist.

Basierend auf dieser Entfernung verwenden wir dann ein agglomeratives hierarchisches Clustering .

Können wir jeden der bekannten Algorithmen (Einzel- / Maximal- / Durchschnittsverknüpfung usw.) verwenden, um aussagekräftige Ergebnisse zu erzielen? Oder anders ausgedrückt, was ist das Problem bei der Verwendung, wenn der Abstand keine Metrik ist?

clustering multilevel-analysis metric hierarchical-clustering Tal Galili
quelle
Was sind "Gegenstände" in Ihrem Fall? (Ich frage, ob es irgendetwas mit Psychometrie zu tun hat, denn wenn dies der Fall ist, würde ich empfehlen, einen Blick auf das Clustering von Elementen zu werfen , oder auf Revelle, W. Hierarchische Clusteranalyse und die interne Struktur von Tests , MBR (1979) 14 : 57.)
chl

Antworten:

7

Die Anforderungen an Entfernungen hängen von der Methode der hierarchischen Clusterbildung ab. Einzelne, vollständige, durchschnittliche Methoden benötigen Abstände, die nicht negativ und symmetrisch sind. Ward-, Centroid- und Median-Methoden benötigen (quadratische) euklidische Abstände (die noch enger definiert sind als metrische Abstände), um geometrisch aussagekräftige Ergebnisse zu erzielen.

(Man kann überprüfen, ob seine Distanzmatrix euklidisch ist, indem man sie doppelt zentriert [siehe meine Antwort hier ] und die Eigenwerte betrachtet. Wenn keine negativen Eigenwerte gefunden werden, konvergieren die Entfernungen im euklidischen Raum.)

ttnphns
quelle
Vielen Dank. Weitere Frage: Muss die Dreiecksungleichung für einzelne, vollständige, durchschnittliche Methoden gelten? und wenn ein gewisser Abstand (zum Beispiel) nicht symmetrisch ist, welches Problem stellt er diese Methoden dar? (Danke!)
Tal Galili
1
Klassische hierarchische Clustering-Methoden können nur eine symmetrische Matrix enthalten: einen Abstand von A nach B = von B nach A. Es gibt spezielle andere Methoden für den Umgang mit asymmetrischen (Sie können googeln). Die dreieckige Ungleichung ist für die von Ihnen genannten Methoden keine notwendige Bedingung. (Die allgemeine Weisheit betrachtet "Entfernung" jedoch als etwas mit der Ungleichung, daher lohnt es sich, sie aufzuerlegen, wenn sie fehlt. Fügen Sie dazu iterativ eine kleine Konstante zu den Entfernungen hinzu und überprüfen Sie sie. Und wenn Sie beim Erreichen weiter hinzufügen es wird dann bald zu euklidischen Entfernungen kommen)
ttnphns
5

Nein, die Entfernung muss keine Metrik sein. Es kann zum Beispiel eine Ultrametrie sein:

d(A,B)≤max(d(A,C),d(B,C))

Ultrametrische Abstände, die aus aufeinanderfolgenden Schritten im Clustering-Algorithmus erhalten wurden, können mithilfe von Dendrogrammen dargestellt werden, die Sie möglicherweise in diesem Zusammenhang gesehen haben.

Hong Ooi
quelle
Vielen Dank, Hong. Ich erinnere mich, dass Methoden zur Transformation einiger Objekte in hclust erfordern, dass das Dendrogramm ultrametrisch ist - ich wundere mich, wenn dies mit dem zu tun hat, was Sie geschrieben haben. Auf jeden Fall danke für die Antwort.
Tal Galili