Clustering mit Kosinusähnlichkeit

Question

Ich habe einen großen Datensatz, den ich gerne Cluster würde. Meine Probelaufgröße beträgt 2.500 Objekte; Wenn ich es mit dem "echten Deal" betreibe, muss ich mindestens 20.000 Objekte bearbeiten.

Diese Objekte haben eine Kosinusähnlichkeit zwischen ihnen. Diese Kosinusähnlichkeit erfüllt nicht die Anforderungen einer mathematischen Abstandsmetrik; es erfüllt nicht die Dreiecksungleichheit.

Ich möchte sie auf eine "natürliche" Art und Weise gruppieren, die ähnliche Objekte zusammenbringt, ohne vorher die Anzahl der erwarteten Cluster angeben zu müssen.

Kennt jemand einen Algorithmus, der das tun würde? Wirklich, ich suche nur nach einem Algorithmus, der a) eine Entfernungsmetrik und b) eine vorher festgelegte Anzahl von Clustern nicht benötigt.

Vielen Dank!

Diese Frage vor hier gefragt wurde: Clustering from the cosine similarity values (aber diese Lösung nur bietet K-Means-Clustering) und hier: Effective clustering of a similarity matrix (aber diese Lösung eher vage war)

Answer 1

Apache Mahout eine Nummer von Clustering-Algorithmen, einschließlich einiger, für die Sie N nicht angeben müssen, und mit denen Sie die Entfernungsmetrik angeben können.

Das Mean Shift-Clustering ist ähnlich zu k-means, aber ohne eine vorher festgelegte Anzahl von Clustern https://cwiki.apache.org/confluence/display/MAHOUT/Mean+Shift+Clustering.

Wenn Sie generell eine Vielzahl von Algorithmen ausprobieren möchten, gibt es eine Fülle von anspruchsvollen Paketen für R (einschließlich einiger Bayes-Implementierungen von EM, die die beste Anzahl von Clustern auswählen) erwies sich für einige meiner Forschungsarbeiten in der Vergangenheit als sehr nützlich: http://cran.r-project.org/web/views/Cluster.html.

Answer 2

Tatsächlich haben die meisten Algorithmen, die eine "Abstandsfunktion" benötigen, nicht die Anforderung, dass sie metrisch ist.

DBSCAN (siehe Wikipedia) auf eine Version, wo es auch abstrahiert aus der Distanz verallgemeinert werden, es braucht nur eine Art von „dicht“ Vorstellung haben. (DBSCAN braucht auch vorher die Anzahl der Cluster nicht zu kennen)

Aber selbst für k-means - die ziemlich strenge Anforderungen an die Entfernung haben, sogar jenseits der metrischen - gibt es eine Variante, die sphärische k-means genannt wird.

Wie auch immer, in einem Datenbankkontext sind die vollständigen Anforderungen von "metrisch" utopisch. In realen Daten kann es zwei Datensätze mit denselben Koordinaten geben, sodass Sie höchstens eine Pseudo-Metrik haben. Die Dreiecksungleichung spielt meistens eine Rolle für die Optimierung (z. B. durch Verwendung eines M-Baum-Index, der strenge Dreiecks-Ungleichheitsanforderungen hat) oder beschleunigte k-Mittel, die diese Eigenschaft ausnutzen.

Answer 3

Sie könnten auch versuchen, Affinity Propagation (http://www.psi.toronto.edu/index.php?q=affinity%20propagation). Der Algorithmus verwendet eine Ähnlichkeitsmatrix als Eingabe und kann, glaube ich, auch automatisch die Anzahl der Clusterschwerpunkte anpassen.