Spark Mllib KMeansのアルゴリズムが極端に遅いのはなぜですか？

Question

私はこのpostと同じ問題がありますが、そこにコメントを追加するには十分なポイントがありません。私のデータセットは100万行、100 colsです。私もMllib KMeansを使用していますが、それは非常に遅いです。仕事は決して終わらないので、私はそれを殺さなければならない。私はGoogleクラウド（dataproc）でこれを実行しています。それは私がより少ない数のクラスター（k = 1000）を求めても実行されますが、それでも35分以上かかります。私はk〜5000のためにそれを実行する必要があります。なぜそんなに遅いのか分かりません。データは適切にパーティション化されており、従業員数/ノード数は100万〜300,000の行列で約3分かかりますが、KMeansの場合はブラックホールに入ります。私は今、より少ない回数の反復（100の代わりに2つ）を試みていますが、どこかに何かが間違っていると感じています。

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

Answer 1

それは理由が比較的単純であるように見えます。かなり大きなkを使用し、高価な初期化アルゴリズムと組み合わせて使用​​します。

デフォルトでは、SparkはK-means++の分散バリアントとしてK-means ||を使用しています。 （What exactly is the initializationSteps parameter in Kmeans++ in Spark MLLib?参照）。分散バージョンはおおよそO（k）です。したがって、より大きなkでは、遅い開始を期待することができます。これは、反復回数を減らしたときに改善が見られない理由を説明します。

モデルを訓練すると大きなKを使うことも高価です。 SparkはLloydsの変形を使用しています。これはおおよそO（nkdi）です。

データの複雑な構造が予想される場合は、K-Meansよりもこれを処理するアルゴリズムが優れている可能性が高いですが、本当にそれに固執したい場合はランダム初期化を使用します。

Answer 2

k-meansの他の実装を試してください。 ELKIの亜種のようなものは、単一CPU上でさえ、方法スパークより優れています。クラスターに行くことなく、1つのノードからどれくらいのパフォーマンスを引き出すことができるかは、驚かされます。残念ながら、私の実験では、良いローカル実装を打ち破るために少なくとも100ノードのクラスタが必要になります。

these C++ versionsは、マルチコア（ただしシングルノード）であり、おそらく最も速いK-meansを今すぐ見つけることができますが、私はまだ自分自身を試していません（ELKIのバージョンはすべて驚くほど速く、私の最大のデータセットで数秒で仕上げる）。