k-meansの代わりにk-means ++を使用する必要がありますか？

Question

k-means ++ アルゴリズムは、元のk-meansアルゴリズムの次の2つのポイントに役立ちます。

1. 元のk-meansアルゴリズムは、入力サイズが超大腸の最悪のケースの実行時間を持ち、k-means ++はO（log k）であると主張しています。
2. 見つかった近似は、最適なクラスタリングと比較して、目的関数に関してそれほど満足のない結果をもたらすことができます。

しかし、k-means ++の欠点はありますか？これからはK-meansの代わりに常に使用する必要がありますか？

Answer 1

誰も主張しません k-means ++ o（lg k） 時間;ソリューションの品質はO（LGです k） - 最適なソリューションとの互換性。両方 k-Means ++およびLloydのアルゴリズムと呼ばれる共通の方法は、NPハード最適化問題の近似です。

最悪のケースの実行時間はわかりません k-means ++ is;で注意してください アーサー＆ヴァシルヴィッツキー オリジナルの説明、アルゴリズムの手順2〜4は、Lloydのアルゴリズムを参照しています。彼らは、それがより良い位置から始まるので、実際にはより良く、より速く機能すると主張しています。

の欠点 k-means ++は次のとおりです。

1. それも最適ではないソリューションを見つけることができます（まだ近似です）。
2. ロイドのアルゴリズムよりも一貫して高速ではありません（Arthur＆Vassilvitskiiのテーブルを参照）。
3. ロイドのアルゴよりも複雑です。
4. それは比較的新しいものですが、ロイドは50年以上の価値があることを証明しています。
5. 特定のメトリックスペースに対してより良いアルゴリズムが存在する可能性があります。

そうは言っても、あなたの場合 k-Means Libraryサポート k-means ++、そして必ず試してみてください。

Answer 2

あなたの質問ではなく、大きなnのkmeansメソッドの簡単なスピードアップ：

1）ポイントのSQRT（n）のランダムサンプルで最初にK-meansを行う
2）次に、それらのセンターからフルKマーンを実行します。

これは、N 10000、K 20のKmeans ++よりも5〜10倍速く、同様の結果を発見しました。
それがあなたのためにどれだけうまく機能するかは、SQRT（n）サンプルが全体にどれだけうまく近いか、およびn、dim、k、ninit、delta ...

N（データポイントの数）、DIM（機能の数）、K、Kは何ですか？
ユーザー 'N、DIM、K、データノイズ、メトリックの大きな範囲...パブリックベンチマークの欠如は言うまでもなく、メソッドを比較するのが難しくなります。

追加：kmeans（）およびkmeanssample（）のpythonコードはここ SO;コメントは大歓迎です。