Welche Methoden zur Entfernungsberechnung gibt es beim Clustering? wann sollten wir jeden von ihnen verwenden?

7

Welche Methoden zur Entfernungsberechnung gibt es beim Clustering? wie Manhattan, Euklidisch usw.? Außerdem weiß ich nicht, wann ich sie verwenden soll. Ich benutze immer euklidische Distanz.

parvij
quelle

Antworten:

8

Nun, es gibt ein Buch namens

Deza, Michel Marie und Elena Deza.
Enzyklopädie der Entfernungen .
Springer Berlin Heidelberg, 2009. ISBN 978-3-642-00233-5

Ich denke, dieses Buch beantwortet Ihre Frage besser als ich ...

Wählen Sie die für Ihre Daten am besten geeignete Entfernungsfunktion.

Verwenden Sie beispielsweise für Breiten- und Längengrade eine Entfernung wie Haversine. Wenn Sie über genügend CPU verfügen, können Sie bessere Näherungswerte wie Vincenty verwenden.

Verwenden Sie für Histogramme einen Verteilungsabstand. Erdbewegungsmaschinen (EMD), Divergenzen, Histogrammschnittpunkte, quadratische Formabstände usw.

Bei Binärdaten wie Jaccard, Dice oder Hamming ist dies sehr sinnvoll.

Bei nicht-binären, spärlichen Daten wie Text sind verschiedene Varianten von tf-idf-Gewichten und Cosinus beliebt.

Das wahrscheinlich beste Werkzeug, um mit verschiedenen Distanzfunktionen und Clustering zu experimentieren, ist ELKI. Es hat viele, viele Entfernungen und viele Clustering-Algorithmen, die mit all diesen Entfernungen verwendet werden können (z. B. OPTICS). Zum Beispiel hat Canberra Distanz für mich sehr gut funktioniert. Das würde ich wahrscheinlich als "Standard" wählen.

Hat aufgehört - Anony-Mousse
quelle
1

Es gibt zwei Methoden, die häufig zur Berechnung der Entfernung im Bereich der Clusterbildung verwendet werden. Sie sind:

  • Manhattan Entfernung
  • Euklidische Entfernung

Es gibt jedoch keine klare Anweisung, welche der oben genannten Optionen auszuwählen ist. Daher kann dieser Beitrag für Sie in Bezug auf diese hilfreich sein. Im Allgemeinen hängt die Entfernungsmetrik von der Problemstellung und der Art der Daten ab.

Beispielsweise werden der euklidische und der Kosinusabstand verwendet, wenn die Daten dicht bzw. dünn sind.

Ich benutze immer euklidische Distanz.

Ich würde dich nicht dafür verantwortlich machen. Bei der Berechnung der kartesischen Entfernung (wie im Fall von Empfehlungssystemen) wird jedoch die euklidische Entfernung bevorzugt.

Dawny33
quelle
0

Ich möchte das zusätzlich zu den bekannten Entfernungen hervorheben: Manhattan Distance Euclidean Distance

Symmetrisches kl-d kann verwendet werden, wenn Sie Verteilungen gruppieren.

Bashar Haddad
quelle
0

Welche Abstandsfunktion verwendet werden soll, hängt von der Datengeometrie selbst ab. In einigen Fällen können Sie Ihre Daten zeichnen und visualisieren und dann Entscheidungen treffen, aber in realen Problemen ist dies meistens nicht möglich.

Für die meisten Clustering-Algorithmen wie Kmeans können Sie sie verwenden, solange eine Distanzfunktion eine Metrik ist. Es gibt Methoden zum Erlernen einer Metrik gemäß der Datengeometrie, mit der Sie die Daten gruppieren können.

Metrisches Lernen ist eng mit der Reduzierung der Dimensionalität verbunden.

Wenn Sie MATLAB verwenden, überprüfen Sie dieses Toolkit .

pj
quelle
k-means funktioniert nur mit Bregman-Divergenzen, nicht mit beliebigen Metriken. Wegen des Mittelwerts werden beliebige Metriken nicht optimiert.
Hat aufgehört - Anony-Mousse
Was bedeutet es, wenn Sie sagen - nicht optimieren? Fügen Sie bitte eine Quelle hinzu.
pj
Suche nach "warum k-means nur mit euklidischer Distanz funktioniert".
Hat aufgehört - Anony-Mousse