Platzsparendes Clustering

Die meisten Clustering-Algorithmen, die ich gesehen habe, beginnen mit der Erstellung von Abständen zwischen allen Punkten, was bei größeren Datensätzen problematisch wird. Gibt es einen, der das nicht tut? Oder ist es eine Art partieller / ungefährer / gestaffelter Ansatz?

Welcher Clustering-Algorithmus / welche Implementierung benötigt weniger als O (n ^ 2) Speicherplatz?

Gibt es irgendwo eine Liste von Algorithmen und deren Zeit- und Raumanforderungen?

K-Means und Mean-Shift verwenden die Rohstichproben-Deskriptoren (keine Vorberechnung einer Affinitätsmatrix erforderlich).

Andernfalls können Sie für spektrales Clustering oder Power-Iterations-Clustering eine spärliche Matrixdarstellung (z. B. komprimierte spärliche Zeilen) der k-nächsten Nachbarn-Affinitätsmatrix (für einige Entfernungs- oder Affinitätsmetriken) verwenden. Wenn k klein ist (sagen wir 5 oder 10). Sie erhalten eine sehr platzsparende Darstellung (2 * n_samples * k * 8 Bytes für Gleitkommawerte mit doppelter Genauigkeit).

Einige Clustering-Algorithmen können räumliche Indexstrukturen verwenden. Dies ermöglicht beispielsweise, dass DBSCAN und OPTICS in -Zeit ausgeführt werden (solange der Index O ( log n ) -Abfragen zulässt ).$O(n\log n)$$O(\log n)$

Offensichtlich baut ein Algorithmus, der in dieser Komplexität läuft, keine -Distanzmatrix auf.$O(n^2)$

Für einige Algorithmen, wie z. B. hierarchisches Clustering mit einfacher Verknüpfung und vollständiger Verknüpfung, stehen optimierte Algorithmen zur Verfügung (SLINK, CLINK). Es ist nur so, dass die meisten Leute alles verwenden, was sie bekommen können und was einfach zu implementieren ist. Und hierarchisches Clustering ist einfach naiv zu implementieren, indem Iterationen über eine n 2 -Distanzmatrix verwendet werden (was zu einem O ( n 3 ) -Algorithmus führt ...).$n$$n^2$$O(n^3)$

Mir ist keine vollständige Liste bekannt, in der Clustering-Algorithmen verglichen werden. Schließlich gibt es wahrscheinlich mehr als 100 Clustering-Algorithmen. Es gibt zum Beispiel mindestens ein Dutzend k-means-Varianten. Außerdem gibt es sowohl Laufzeitkomplexität als auch Speicherkomplexität. Es gibt Durchschnitts- und Worst-Case-Fälle. Es gibt enorme Implementierungsunterschiede (z. B. oben erwähnte Single-Link- und DBSCAN-Implementierungen, die keinen Index verwenden und sich daher in und nicht die vollständige Distanzmatrix speichern müssen müssen sie dann noch alle paarweisen Abstände berechnen). Außerdem gibt es jede Menge Parameter. Für k-bedeutetn × n k O ( n 2 ) O ( n ) O ( n log n ) O ( n $O(n^2)$$n\times n$$k$ist kritisch. Für so ziemlich jeden Algorithmus macht die Distanzfunktion einen großen Unterschied (viele Implementierungen erlauben nur die euklidische Distanz ...). Und sobald Sie zu teuren Entfernungsfunktionen kommen (über triviale Dinge wie Euklidisch hinaus), kann die Anzahl der Entfernungsberechnungen schnell der Hauptteil sein. Sie müssten dann zwischen der Anzahl der Operationen insgesamt und der Anzahl der erforderlichen Entfernungsberechnungen unterscheiden. Ein Algorithmus, der sich in -Operationen befindet, aber nur -Distanzberechnungen, kann einen Algorithmus, der in beiden ist, leicht übertreffen , wenn die Distanzfunktionen wirklich teuer sind (z. B. die Distanz) Funktion selbst ist ).$O(n^2)$$O(n)$$O(n \log n)$$O(n)$

Gute Frage. Eine Strohmann-Methode für beispielsweise 3 nächste Nachbarn besteht darin, Nsample-Nachbarn jedes Datenpunkts abzutasten, wobei die nächsten 3 beibehalten werden. Wenn Sie dies für einige Werte von Nsample trivial ausführen, erhalten Sie eine Vorstellung vom Signal / Rausch-Verhältnis, Nah- / Hintergrundrauschen , leicht für Ihre Daten geplottet . Ein zusätzlicher Trick besteht darin, die Nachbarn der Nachbarn zu überprüfen, um festzustellen, ob diese näher als die direkten Nachbarn sind. Wenn die Eingabedaten bereits gut gemischt sind, werden sie in Blöcken abgetastet, da sonst der Cache kaputt geht.

(Hinzugefügt): Siehe Fastcluster in R und ich glaube an SciPy v0.11.
Text finden Sie unter Google-All-Pair-Ähnlichkeitssuche .

Wiederholen Sie: "Ein geeignetes Unähnlichkeitsmaß ist für den Erfolg beim Clustering weitaus wichtiger als die Auswahl des Clustering-Algorithmus" - Auswahl der Clustering-Methode .