K 平均法のメリットとデメリット

K 平均法は多くの ML コンテキストで有用で効率的ですが、いくつかの明確な弱点があります。

K 平均法の利点

実装が比較的簡単。

大規模なデータセットにスケーリングできます。

常に収束する。

重心の位置をウォームスタートできます。

新しい例にスムーズに適応します。

楕円形のクラスタなど、さまざまな形状とサイズのクラスタに一般化できます。

K 平均法の一般化

K 平均法の単純な実装では、密度とサイズが異なるクラスタで問題が発生する可能性があります。図 1 の左側は、想定されるクラスタを示しています。右側は、k 平均法によって提案されたクラスタを示しています。

図 1: 一般化されていない K 平均法の例。

図 1 のような不均衡なクラスタでパフォーマンスを向上させるには、k 平均法を一般化（適応）します。図 2 は、2 つの異なる一般化でクラスタ化された 3 つの異なるデータセットを示しています。最初のデータセットは一般化なしの K 平均法を示していますが、2 つ目と 3 つ目ではクラスタの幅を変更できます。

図 2: 一般化ありと一般化なしの K 平均法クラスタリング。

このコースでは、k 平均法の一般化方法については説明しません。興味がある場合は、カーネギー メロン大学の Carlos Guestrin による Clustering – k-means Gaussian mixture models をご覧ください。

K 平均法のデメリット

\(k\) は手動で選択する必要があります。

結果は初期値によって異なります。

\(k\)が低い場合は、異なる初期値で k 平均法を複数回実行し、最良の結果を選択することで、この依存関係を軽減できます。 \(k\)が増加すると、より優れた初期重心を選択するためにk 平均法シードが必要になります。k 平均法シードについて詳しくは、M.Emre Celebi、Hassan A. Kingravi、Patricio A. Vela。

一般化なしで、サイズや密度が異なるデータをクラスタリングするのは困難です。

外れ値のクラスタリングが難しい。

外れ値によって重心が引きずられることがあります。また、外れ値が無視されるのではなく、独自のクラスタが作成されることもあります。クラスタリングする前に、外れ値を削除またはクリップすることを検討してください。

ディメンション数に応じたスケーリングの難しさ。

データの次元数が増えると、距離ベースの類似度測定値は、任意のサンプル間で一定の値に収束します。特徴データに PCA を使用するか、スペクトル クラスタリングを使用してクラスタリング アルゴリズムを変更することで、次元を削減します。

次元の呪いとスペクトル クラスタリング

これらの 3 つのグラフでは、ディメンションが増加するにつれて、サンプル間の距離の標準偏差がサンプル間の平均距離に比べて小さくなる様子を確認できます。この収束とは、データの次元数が増加するにつれて、k 平均法が例を区別する効果が低下することを意味します。これは「次元の呪い」と呼ばれます。

図 3: 次元の呪いのデモ。各プロットには、200 個のランダムなポイント間のペアワイズ距離が表示されます。

このパフォーマンスの低下を回避するには、スペクトル クラスタリングを使用します。このクラスタリングでは、クラスタリング前のステップがアルゴリズムに追加されます。スペクトル クラスタリングを実行するには:

1. PCA を使用して特徴データの次元を減らします。
2. すべてのデータポイントを低次元のサブスペースに射影します。
3. 選択したアルゴリズムを使用して、このサブスペース内のデータをクラスタリングします。

スペクトル クラスタリングの詳細については、Ulrike von Luxburg による A Tutorial on Spectral Clustering をご覧ください。

主な用語:

• スペクトル クラスタリング