Warum ist Spark MLLib KMeans Algorithmus extrem langsam?

Question

Ich habe das gleiche Problem wie in diesem post, aber ich habe nicht genug Punkte, um einen Kommentar dort hinzuzufügen. Mein Datensatz hat 1 Million Zeilen, 100 Spalten. Ich benutze auch MLLib KMeans und es ist extrem langsam. Der Job endet nie wirklich und ich muss ihn töten. Ich führe dies auf Google Cloud (Dataproc). Es läuft, wenn ich nach einer kleineren Anzahl von Clustern (k = 1000) frage, aber immer noch mehr als 35 Minuten brauche. Ich brauche es für k ~ 5000 laufen. Ich habe keine Ahnung warum es so langsam ist. Die Daten werden bei der Anzahl der Worker/Nodes richtig partitioniert und SVD auf einer 1 Million x ~ 300.000 Col-Matrix dauert ~ 3 Minuten, aber wenn es um KMeans geht, geht es einfach in ein schwarzes Loch. Ich versuche jetzt eine geringere Anzahl von Iterationen (2 statt 100), aber ich fühle, dass irgendwo etwas nicht stimmt.

KMeansModel Cs = KMeans.train(datamatrix, k, 100);//100 iteration, changed to 2 now. # of clusters k=1000 or 5000 

Answer 1

Es sieht so aus, als ob der Grund relativ einfach ist. Sie verwenden ziemlich großes k und kombinieren es mit einem teuren Initialisierungsalgorithmus.

Standardmäßig verwendet Spark als verteilte Variante von K-means++ namens K-means || (siehe What exactly is the initializationSteps parameter in Kmeans++ in Spark MLLib?). Verteilte Version ist ungefähr O (k) so mit größeren k erwarten Sie langsamer Start. Dies sollte erklären, warum Sie keine Verbesserung feststellen, wenn Sie die Anzahl der Iterationen reduzieren.

Die Verwendung von großen K ist auch teuer, wenn das Modell trainiert wird. Spark verwendet eine Variante von Lloyds, die ungefähr O (nkdi) ist.

Wenn Sie eine komplexe Struktur der Daten erwarten, gibt es wahrscheinlich eine bessere Algorithmen als K-Means, aber wenn Sie wirklich dabei bleiben wollen, beginnen Sie mit der zufälligen Initialisierung.

Answer 2

Bitte versuchen Sie andere Implementierungen von K-Means. Einige mögen die Varianten in ELKI sind Weg besser als Spark, sogar auf nur einer einzigen CPU. Sie werden überrascht sein, wie viel Leistung Sie aus einem einzigen Knoten herausholen können, ohne zu einem Cluster zu gehen! Von meinen Experimenten würden Sie bedauerlicherweise mindestens einen Cluster mit 100 Knoten benötigen, um gute lokale Implementierungen zu übertreffen.

Ich habe gelesen, dass these C++ versions sind Multi-Core (aber Single-Node) und wahrscheinlich die schnellste K-Mittel, die Sie jetzt finden können, aber ich habe das noch nicht selbst ausprobiert (für alle meine Bedürfnisse waren die ELKI-Versionen) bazingly schnell, in wenigen Sekunden auf meinen größten Datensätzen fertig).