k-means ++アルゴリズムは、元のk-meansアルゴリズムの次の2つの点で役立ちます。
- 元のk-meansアルゴリズムは、入力サイズで超多項式の実行時間が最悪の場合ですが、k-means ++はO（log k）であると主張しています。
- 見つかった近似は、最適なクラスタリングと比較して、目的関数に関してそれほど満足のいく結果をもたらさない可能性があります。
しかし、k-means ++の欠点はありますか？これからは、k-meansの代わりに常にそれを使用する必要がありますか？
4157 次
2 に答える
17
k -means ++がO（lg k）時間で実行されるとは誰も主張していません。ソリューションの品質はO（lg k）であり、最適なソリューションと競合します。k -means ++と、ロイドのアルゴリズムと呼ばれる一般的な方法はどちらも、NP困難な最適化問題の近似です。
k -means++の最悪の実行時間が何であるかわかりません。Arthur＆Vassilvitskiiの元の説明では、アルゴリズムのステップ2〜4がロイドのアルゴリズムを参照していることに注意してください。彼らは、それがより良い位置から始まるので、実際にはより良くそしてより速く働くと主張します。
したがって、 k -means++の欠点は次のとおりです。
- それも次善の解決策を見つけることができます（それはまだ近似です）。
- ロイドのアルゴリズムよりも一貫して高速ではありません（Arthur＆Vassilvitskiiの表を参照）。
- ロイドのアルゴよりも複雑です。
- それは比較的新しいものですが、ロイドは50年以上にわたって価値があることを証明しています。
- 特定の距離空間には、より優れたアルゴリズムが存在する可能性があります。
そうは言っても、k -meansライブラリがk -means ++をサポートしている場合は、ぜひ試してみてください。
于 2011-01-16T19:30:33.567 に答える
7
あなたの質問ではありませんが、大きなNの任意のkmeans法への簡単なスピードアップ：
1）最初にポイントのsqrt（N）などのランダムサンプルで
k-meansを実行し、次にそれらの中心から完全なk-meansを実行します。
これは、N 10000、k20のkmeans++よりも5〜10倍高速であり、同様の結果が得られています。
それがどれだけうまく機能するかは、sqrt（N）サンプルが全体をどれだけうまく近似するか、およびN、dim、k、ninit、delta...に依存します。
N（データポイントの数）、dim（特徴の数）、およびkは何ですか？
ユーザーのN、dim、k、データノイズ、メトリックの膨大な範囲...公開ベンチマークの欠如は言うまでもなく、メソッドの比較を困難にします。
追加：kmeans（）およびkmeanssample（）のPythonコードは SOにあります。コメントは大歓迎です。
于 2011-01-25T17:12:23.960 に答える