K-bedeutet: Wie viele Iterationen in praktischen Situationen?

10

Ich habe keine Branchenerfahrung im Bereich Data Mining oder Big Data und würde mich freuen, wenn Sie Erfahrungen austauschen.

Führen die Leute tatsächlich k-means, PAM, CLARA usw. für einen wirklich großen Datensatz aus? Oder wählen sie einfach zufällig eine Probe aus? Wenn sie nur eine Stichprobe des Datensatzes entnehmen, wäre das Ergebnis dann zuverlässig, wenn der Datensatz nicht normal verteilt ist?

Können wir in praktischen Situationen beim Ausführen dieser Algorithmen feststellen, wie viele Iterationen normalerweise dauern würden, bis Konvergenz auftritt? Oder wächst die Anzahl der Iterationen immer mit der Datengröße?

Ich frage dies, weil ich darüber nachdenke, einen Ansatz zu entwickeln, um die iterativen Algorithmen vor der Konvergenz zu beenden, und die Ergebnisse dennoch akzeptabel sind. Ich denke, es lohnt sich zu versuchen, wenn die Anzahl der Iterationen mehr als 1.000 beträgt, damit wir Rechenaufwand und Zeit sparen können. Was denkst du?

clustering data-mining k-means convergence large-data foo
quelle
number of iterations always grow with the data sizeNicht unbedingt.
ttnphns
Es gibt verschiedene Kriterien, um Iterationen in K-Mitteln zu stoppen. Interessanterweise gehört es zu den vernünftigen Möglichkeiten, einfach die Anzahl der Iterationen auf einen festen Wert (z. B. 10 oder 20) festzulegen. K-means ist eine schnelle Methode. Wenn Sie also möchten, dass ein Konvergenzkriterium nach jeder Iteration überprüft wird, muss dieses Kriterium einfach / schnell zu berechnen sein.
ttnphns
1
Gibt es eine "wissenschaftliche" Möglichkeit, die maximale Anzahl der auszuführenden Iterationen zu bestimmen?
foo
Ihr letzter Kommentar ist eine gute Frage. Ehrlich gesagt, ich weiß es nicht. Vielleicht antworten andere Leute darauf.
ttnphns

Antworten:

6

  1. K-Mittel ist billig. Sie können es sich leisten, es für viele Iterationen auszuführen .

  2. Es gibt schlechte Algorithmen (die Standardalgorithmen) und gute Algorithmen. Für gute Algorithmen kosten spätere Iterationen oft viel weniger als 1% der ersten Iteration.

  3. Es gibt sehr langsame Implementierungen. Benutze sie nicht.

  4. K-Mittel für "große" Daten gibt es nicht. Weil es nur mit niedrigdimensionalen Vektordaten funktioniert. Sie werden den Speicher eines modernen Servers mit solchen Daten nicht überschreiten. Ja, es gibt größere Daten - aber Sie können k-means nicht für beispielsweise einen Monat Twitter-Daten verwenden, da Sie dadurch nichts Nützliches erhalten.

Bei einer guten Implementierung auf einem modernen Server benötigt der größte Datensatz, den Sie finden können, bei dem k-means noch ein nützliches Ergebnis liefert, wahrscheinlich weniger als 1 Minute, um bis zur Konvergenz zu berechnen. Warum also über eine Iterationsgrenze nachdenken?

Hat aufgehört - Anony-Mousse
quelle
1
Zustimmen. In diesem Artikel ( Skalierbare K-Mittelwerte nach Rangabruf ) stellten die Autoren fest, dass K-Mittelwerte nach 20-50 Iterationen in allen praktischen Situationen konvergieren, selbst bei hochdimensionalen Datensätzen, wie sie getestet wurden. Kennen Sie außer K-means einen Algorithmus, der eine große Anzahl von Iterationen bis zur Konvergenz benötigt?
foo
Vielleicht eine SVM trainieren? Ich glaube, es ist iterativ und versucht, den besten (und kleinsten, da die Vorhersage davon abhängt!) Satz von Unterstützungsvektoren zu finden.
Hat aufgehört - Anony-Mousse
Die naheliegende Lösung zum Ausführen von k-means für hochdimensionale Datensätze besteht darin, zuerst PCA oder eine andere Methode zur Reduzierung der Dimensionalität auszuführen und dann k-means
auszuführen