Schneller Algorithmus für 10 ^ 10 Punkte?

14

Ich versuche k-means Clustering auf einer Menge von 10-dimensionalen Punkten durchzuführen. Der Haken: Es gibt 10 ^ 10 Punkte .

Ich suche nur die Mitte und Größe der größten Cluster (sagen wir 10 bis 100 Cluster); Es ist mir egal, in welchem ​​Cluster jeder Punkt endet. Die Verwendung von k-means ist nicht wichtig. Ich suche nur nach einem ähnlichen Effekt, jeder ungefähre k-Mittelwert oder verwandte Algorithmus wäre großartig (Minibatch-SGD bedeutet, ...). Da GMM in gewisser Weise das gleiche Problem wie k-means ist, ist es auch interessant, GMM mit Daten gleicher Größe durchzuführen.

In dieser Größenordnung ändert die Unterabtastung der Daten das Ergebnis wahrscheinlich nicht wesentlich: Die Wahrscheinlichkeit, unter Verwendung einer 1/10000-Stichprobe der Daten die gleichen Top-10-Cluster zu finden, ist sehr gut. Aber selbst dann ist das ein 10 ^ 6-Punkte-Problem, das an / jenseits der Grenze von tractable liegt.

Alex ich
quelle
1
In dem Buch "Mining of Massive Datasets", das Sie hier kostenlos herunterladen können, sind mehrere Algorithmen beschrieben . Lesen Sie Kapitel 7 "Clustering".
Lanenok

Antworten:

12

k-means basiert auf Durchschnittswerten .

Es modelliert Cluster mithilfe von Mitteln, und daher ist die Verbesserung durch Hinzufügen von mehr Daten marginal. Der Fehler der Durchschnittsschätzung verringert sich mit 1 / sqrt (n); Das Hinzufügen von mehr Daten zahlt sich immer weniger aus.

Strategien für solch große Datenmengen drehen sich immer um Stichproben:

Wenn Sie eine sublineare Laufzeit wünschen, müssen Sie Sampling durchführen!

Tatsächlich tun Mini-Batch-Kmeans usw. genau das: Mehrmals aus dem Datensatz abtasten.

Das Sampling (insbesondere das unverzerrte Sampling) ist jedoch auch nicht gerade kostenlos. In der Regel müssen Sie Ihre Daten linear lesen, um das Sampling durchzuführen, da Sie keinen zufälligen Zugriff auf einzelne Datensätze erhalten.

Ich würde mit MacQueens Algorithmus gehen. Es ist online; Standardmäßig werden Ihre Daten nur einmal durchlaufen (obwohl dies häufig wiederholt wird). Es ist nicht einfach zu verteilen, aber ich vermute, Sie können es sich leisten, Ihre Daten etwa zehnmal linear von einer SSD zu lesen?

Anony-Mousse - Setzen Sie Monica wieder ein
quelle
Ich wusste nichts über den Online-Algorithmus von MacQueen! Erhält es normalerweise die gleichen Ergebnisse wie "klassische" K-Mittel? Wie wäre es stattdessen mit der Probenahme aus dem Reservoir? Auf diese Weise verfügt OP über eine Stichprobe, auf der K-means erneut ausgeführt werden kann, falls mehrere Werte von K getestet werden sollen.
Victor Ma
6

Als Neben Kommentar zur Kenntnis , dass mit K-Mitteln für 10D Daten könnte nirgends nach dem Fluch der Dimensionalität in bis beenden. Natürlich variiert es ein bisschen je nach Art der Daten, aber als ich versuchte, die Schwelle zu bestimmen, bei der sich K-Means in Bezug auf die Dimension merkwürdig verhält, bekam ich so etwas wie 7D. Nach 7 Dimensionen fing es an, korrekte Cluster zu übersehen (meine Daten wurden manuell anhand von 4 gut getrennten Gauß-Verteilungen generiert und ich verwendete die MATLAB- kmeans- Funktion für mein kleines Experiment).

Kasra Manshaei
quelle
Dies ist möglich und natürlich immer abhängig von den Daten. Angesichts der Tatsache, dass das Poster 10 ^ 10 (vermutlich unabhängige) Samples enthält, scheinen 10 Dimensionen hier kein allzu großes Problem zu sein.
Ryan J. Smith
2
Vielen Dank für Ihren Kommentar @ RyanJ.Smith. Ihr Kommentar ist genau in die gleiche Richtung von mir. Ich habe einfach nichts in Bezug auf dieses Problem in der Post gesehen. Und über die Anzahl der Proben; Er hat jedoch viele Stichprobenpunkte, bei denen er sich möglicherweise immer noch mit dem Problem der Dimensionalität beschäftigt. Ich denke, Sie argumentieren die Gegenseite des Problems der geringen Stichprobengröße, die meiner Meinung nach nicht gültig ist. Wenn er hochdimensionale Daten hat, wird eine niedrige Stichprobengröße ein Problem sein, aber ich denke, eine große Datenmenge bedeutet nicht unbedingt etwas.
Kasra Manshaei
10 Dimensionen sind noch nicht viel.
Anony-Mousse
1
Wie bestimmst du meinen Freund? Was ich sagte, war das Ergebnis eines Experiments, das entwickelt wurde, um eine solche Frage zu beantworten, aber es kann NICHT allgemein beantwortet werden! Was ist "viel" in Ihrem Kommentar genau? es hängt von vielen Umständen ab, wie ich in meiner Antwort erwähnt habe. In einigen Situationen kann 10D problematisch sein.
Kasra Manshaei