Clustering basierend auf Ähnlichkeitswerten

17

Es sei angenommen , dass wir eine Reihe von Elementen haben E und eine Ähnlichkeit ( nicht Abstand ) Funktion sim (ei, ej) zwischen zwei Elementen ei, ej ∈ E .

Wie können wir die Elemente von E mit sim (effizient) clustern ?

k - bedeutet zum Beispiel, dass ein gegebenes k erforderlich ist, für das Canopy Clustering sind zwei Schwellenwerte erforderlich. Was ist, wenn wir solche vordefinierten Parameter nicht wollen?

Beachten Sie, dass sim nicht unbedingt eine Metrik ist (dh die Dreiecksungleichung kann gelten oder auch nicht). Außerdem spielt es keine Rolle, ob die Cluster disjunkt sind (Partitionen von E ).

clustering algorithms similarity vefthym
quelle
2
Ich frage mich , warum Sie betont , dass Sie nicht einen Abstand haben. Ich bin hier kein Experte, aber ich frage mich, ob es nicht möglich sein sollte, eine solche Ähnlichkeit in eine Entfernung umzuwandeln, wenn dies erforderlich ist, im Grunde genommen unter Berücksichtigung ihrer Umkehrung. Ungeachtet dessen bezweifle ich, dass es Cluster-Algorithmen gibt, die völlig frei von Parametern sind, so dass höchstwahrscheinlich in allen Fällen eine gewisse Optimierung erforderlich sein wird. Wenn Sie k-Means betrachtet, kann man davon ausgehen , dass Sie reellwertige Eigenschaften (insbesondere, dass Sie können die „mittlere“ nehmen mehrere Elemente)?
Marco13
4
Sie müssen k nicht kennen, um k-Mittel auszuführen. Sie können Cluster mit variierendem k bilden und die Clustervarianz prüfen, um das Optimum zu finden. Alternativ könnten Sie überlegen, ob Sie sich für Gaußsche Mischungsmodelle oder andere Restaraunt-Prozesse entscheiden, um Clustering zu unterstützen.
Cwharland
2
Ich habe die Fragen aus einem bestimmten Grund gestellt: Wenn Sie k-Means anwenden konnten, aber das einzige Problem darin bestand, das anfängliche "k" zu finden, könnten Sie eine en.wikipedia.org/wiki/Self-organizing_map als Alternative in Betracht ziehen . Es hat einige nette Eigenschaften und verhält sich grundsätzlich "ähnlich" zu k-Means, erfordert jedoch nicht, dass das anfängliche "k" gesetzt wird. Es ist wahrscheinlich keine sofort einsatzbereite Lösung, da sie zusätzliche Optimierungsparameter enthält (und das Training möglicherweise rechenintensiv ist), aber dennoch einen Blick wert.
Marco13
2
Die anfängliche Auswahl von k beeinflusst die Clusterergebnisse, aber Sie können eine Verlustfunktion oder wahrscheinlicher eine Genauigkeitsfunktion definieren, die Ihnen für jeden Wert von k, den Sie für die Clusterbildung verwenden, die relative Ähnlichkeit aller Subjekte in diesem Cluster angibt. Sie wählen das k, das die Varianz dieser Ähnlichkeit minimiert. GMM und andere Dirichlet-Prozesse kümmern sich recht gut um das Nicht-Wissen-K-Problem. Eine der besten Quellen, die ich je gesehen habe, ist das Tutorial von Edwin Chen .
Cwharland
4
Nur ein Gedanke: Wenn Ihr Ähnlichkeitswert auf 1 normalisiert ist , dann 1-sim(ei, ej) = Distance. Mit der Distanzmetrik können Sie beispielsweise hierarchische Clustering anwenden. Wenn Sie von der Wurzel aus nach unten gehen, werden Sie sehen, auf welcher Ebene der Granularitätscluster für Ihr spezielles Problem Sinn macht.
Olexandr Isayev

Antworten:

8

  1. Ich denke, eine Reihe von Clustering-Algorithmen, die normalerweise eine Metrik verwenden, stützen sich nicht auf die Metrikeigenschaften (abgesehen von der Kommutativität, aber ich denke, das hätten Sie hier). DBSCAN verwendet beispielsweise Epsilon-Nachbarschaften um einen Punkt. Es gibt nichts, was speziell besagt, dass die Dreiecksungleichheit von Bedeutung ist. Daher können Sie wahrscheinlich DBSCAN verwenden, obwohl Sie möglicherweise einen nicht standardmäßigen räumlichen Index ausführen müssen, um in Ihrem Fall eine effiziente Suche durchzuführen. Ihre Version von epsilon-neighbourhood ist wahrscheinlich eher sim> 1 / epsilon als umgekehrt. Gleiche Geschichte mit k-means und verwandten Algorithmen.

  2. Können Sie eine Metrik aus Ihrer Ähnlichkeit konstruieren? Eine Möglichkeit: dist (ei, ej) = min (sim (ei, ek) + sim (ek, ej)) für alle k ... Alternativ können Sie eine Obergrenze angeben, so dass sim (ei, ej) <sim (ei, ek) + sim (ek, ej) + d, für alle k und eine positive Konstante d? Intuitiv bedeuten große sim-Werte, dass sie näher beieinander liegen: ist 1 / sim metrisch? Was ist mit 1 / (sim + Konstante)? Was ist mit min (1 / sim (ei, ek) + 1 / sim (ek, ej)) für alle k? (das letzte ist garantiert eine Metrik, übrigens)

  3. Eine alternative Konstruktion einer Metrik ist das Einbetten. In einem ersten Schritt können Sie versuchen, Ihre Punkte ei -> xi so abzubilden, dass xi die Summe (abs (sim (ei, ej) - f (dist (xi, xj))) für eine geeignete Funktion f und Metrik minimiert dist. Die Funktion f wandelt die Distanz in der Einbettung in einen ähnlichen Wert um, Sie müssten ein wenig experimentieren, aber 1 / dist oder exp ^ -dist sind gute Ausgangspunkte. Sie müssten auch am besten experimentieren Dimension für xi. Von dort aus können Sie konventionelles Clustering für xi verwenden. Die Idee hier ist, dass Sie Ihre Abstände in der Einbettung fast (im besten Sinne) in Ähnlichkeitswerte umwandeln können, damit sie korrekt geclustert werden.

  4. Bei Verwendung vordefinierter Parameter können alle Algorithmen optimiert werden. DBSCAN kann die Anzahl der Cluster ermitteln, Sie müssen ihm jedoch noch einige Parameter zuweisen. Im Allgemeinen erfordert die Optimierung mehrere Durchläufe des Algorithmus mit unterschiedlichen Werten für die einstellbaren Parameter, zusammen mit einer Funktion, die die Güte des Clusterings bewertet (entweder separat berechnet, vom Clustering-Algorithmus selbst bereitgestellt oder nur mit einem Augenzwinkern versehen :) Wenn das Zeichen von Ihre Daten ändern sich nicht, Sie können sie einmal einstellen und dann diese festen Parameter verwenden. Wenn es sich ändert, müssen Sie für jeden Lauf abstimmen. Sie können das herausfinden, indem Sie für jeden Lauf abstimmen und dann vergleichen, wie gut die Parameter von einem Lauf auf einen anderen wirken, verglichen mit den speziell dafür abgestimmten Parametern.

Alex ich
quelle
7

Alex machte eine Reihe von guten Punkten, obwohl ich vielleicht etwas auf seine Implikation zurückschieben muss, dass DBSCAN der beste Clustering-Algorithmus ist, der hier verwendet werden kann. Abhängig von Ihrer Implementierung und davon, ob Sie beschleunigte Indizes verwenden oder nicht (viele Implementierungen tun dies nicht), ist Ihre zeitliche und räumliche Komplexität alles O(n2)andere als ideal.

Persönlich sind meine Go-to-Clustering-Algorithmen OpenOrd für Winner-Takes-All-Clustering und FLAME für Fuzzy-Clustering. Beiden Methoden ist es gleichgültig, ob es sich bei den verwendeten Metriken um Ähnlichkeit oder Distanz handelt (insbesondere FLAME ist in beiden Konstruktionen nahezu identisch). Die Implementierung von OpenOrd in Gephi ist O(nlogn)und ist bekanntermaßen skalierbarer als alle anderen im Gephi-Paket enthaltenen Clustering-Algorithmen.

FLAME hingegen ist großartig, wenn Sie nach einer Fuzzy-Clustering-Methode suchen. Während die Komplexität von FLAME etwas schwieriger zu bestimmen ist, da es sich um einen iterativen Prozess handelt, hat sich gezeigt, dass es subquadratisch ist und eine ähnliche Laufgeschwindigkeit wie knn aufweist.

indico
quelle
4

DBSCAN (siehe auch: Generalized DBSCAN) benötigt keinen Abstand. Alles was es braucht ist eine binäre Entscheidung . Im Allgemeinen würde man "distance <epsilon" verwenden, aber nichts sagt, dass Sie stattdessen "similarity> epsilon" nicht verwenden können. Dreiecksungleichungen usw. sind nicht erforderlich.

Die Affinitätsausbreitung verwendet, wie der Name schon sagt, Ähnlichkeiten.

Hierarchisches Clustering, mit Ausnahme von Ward-Verknüpfungen, lässt keine Vermutung zu. In vielen Implementierungen können Sie nur negative Abstände verwenden, wenn Sie Ähnlichkeiten haben, und es wird gut funktionieren. Weil nur min, max und <benötigt werden.

Kernel k-means könnte funktionieren, wenn Ihre Ähnlichkeit eine gute Kernelfunktion ist. Stellen Sie sich vor, Sie berechnen k-means in einem anderen Vektorraum, in dem der euklidische Abstand Ihrer Ähnlichkeitsfunktion entspricht. Aber dann musst du wissen, k.

PAM (K-medoids) sollte funktionieren. Ordnen Sie jedes Objekt dem ähnlichsten Medoid zu, und wählen Sie dann das Objekt mit der höchsten durchschnittlichen Ähnlichkeit als neues Medoid aus. Es ist keine Dreieckungleichung erforderlich.

... und wahrscheinlich viele, viele mehr. Es gibt buchstäblich Hunderte von Clustering-Algorithmen. Die meisten sollten meiner Meinung nach funktionieren . Sehr wenige scheinen tatsächlich metrische Eigenschaften zu erfordern. K-means hat wahrscheinlich die höchsten Anforderungen: Es minimiert die Varianz (nicht den Abstand oder die Ähnlichkeit) und Sie müssen in der Lage sein, die Mittelwerte zu berechnen.

Anony-Mousse - Setzen Sie Monica wieder ein
quelle