高次元データ ポイント (約 50 次元) のセットに k-means を適用しようとしていますが、最適な数のクラスターを見つける実装があるかどうか疑問に思っていました。
アルゴリズムが一般的にこれを行う方法は、クラスター間距離が最大化され、クラスター内距離が最小化されるということをどこかで読んだことを覚えていますが、どこで見たのか覚えていません。誰かがこれについて議論しているリソースを教えてくれれば幸いです. 現在、k-means に SciPy を使用していますが、関連するライブラリも問題ありません。
同じアルゴリズムまたはより優れたアルゴリズムを実現する別の方法がある場合は、お知らせください。
1 つのアプローチはクロス検証です。
本質的には、データのサブセットを選択し、それをk 個のクラスターにクラスター化して、残りのデータと比較してクラスター化がどの程度うまく行われているかを尋ねます。クラスター？
メンバーシップがほぼ同じである場合、データはk 個のクラスターにうまく適合します。それ以外の場合は、別のkを試します。
また、PCA (主成分分析) を実行して、50 次元をより扱いやすい数に減らすこともできます。PCA の実行により、分散のほとんどが 50 次元のうちの 4 次元に由来することが示唆された場合、それに基づいてkを選択し、4 つのクラスター メンバーシップがどのように割り当てられているかを調べることができます。
データセット内のクラスター数の決定については、このウィキペディアのページをご覧ください。
また、凝集型階層クラスタリングを試してみることもできます。このアプローチでは、クラスターの数を知る必要はありません。1 つだけが存在するまで、クラスターのクラスターを段階的に形成します。この手法は SciPy ( scipy.cluster.hierarchy ) にも存在します。
興味深いアプローチの 1 つは、Fred と Jain による証拠の蓄積です。これは、k-means の複数の実行を多数のクラスターと組み合わせて、それらを全体的なソリューションに集約することに基づいています。このアプローチの優れた点は、クラスタの数がプロセスで決定されること、および最終的なクラスタが球形である必要がないことです。
また、各次元が実際に独立していることも確認する必要があります。多くのいわゆる多次元データセットには、同じものの複数の表現があります。
これらをデータに含めることは間違いではありません。クラスタ引数のサポートとして、同じものの複数のバージョンを使用するのは間違っています。
それを行う 1 つの方法は、k-means を大きな k (正しいと思われる数よりもはるかに大きい)、たとえば 1000 で実行することです。次に、これらの 1000 ポイントで平均シフト アルゴリズムを実行します (平均シフトはデータ全体を使用しますが、これらの 1000 ポイントのみを「移動」します)。平均シフトは、クラスターの量を見つけます。前に k-means なしで平均シフトを実行することは可能ですが、通常は O(N^2*#steps) 遅すぎるため、前に k-means を実行すると速度が向上します: O(N K #steps)
クラスター番号がわからない場合は、代わりに階層型クラスタリングを使用してみませんか?
最初は、孤立したすべてのクラスターがクラスターであり、距離がしきい値よりも小さい場合、2 つのクラスターごとにマージされます。アルゴリズムは、マージが行われなくなると終了します。
階層クラスタリング アルゴリズムは、データに対して適切な "K" を実行できます。