K-Means Clustering

k-meansクラスタリングは、データをk個のグループに分割する教師なし学習アルゴリズムです。各グループは、割り当てられた点の平均である重心によって表されます。クラスタ内の距離の二乗和が最小になる分割を探します。この量は慣性と呼ばれ、各クラスタの点が重心の近くに集まることを示します。標準的な手順はLloydのアルゴリズムです。Stuart Lloydが1957年にBell Labsで信号の量子化を目的に開発し、「k-means」という名前はJames MacQueenの1967年の論文に由来します。単純で高速であり、数百万点に拡張できるため、k-meansはデータマイニング、圧縮、ラベルのないデータの構造の探索に標準的に使われています。

アルゴリズムの仕組み#

初期重心を選んだ後、クラスタが変化しなくなるまで、Lloydのアルゴリズムは割り当てステップと更新ステップを交互に繰り返します。

1. 初期化: 初期重心をk個選びます。Scikit-learnのデフォルトであるk-means++では、最初の重心をランダムに選びます。それ以降の重心は、すでに選んだ最も近い重心からの距離の二乗に比例する確率で選ぶため、シード同士が離れます。
2. 割り当て: 通常はユークリッド距離を使い、各点を最も近い重心に割り当てます。
3. 更新: 各重心を、現在割り当てられている点の平均に移動します。
4. 反復: 点のクラスタが変わらなくなるか、重心の移動量が許容値を下回るまで、割り当てステップに戻ります。

どちらのステップも慣性を増加させないため、ループは必ず収束します。ただし、収束先は初期重心に依存する局所最小値です。大域最適解を見つける問題はNP困難であるため、実装では複数の初期化を実行し、慣性が最も低いものを採用します。 scikit-learnのKMeansでは、k-means++で初期化する場合、デフォルトのn_init="auto"は1回実行され、ランダムに初期化する場合は10回実行されます。

クラスタ数の選択#

k-meansでは、事前にkを指定する必要があります。kを増やすと重心が点に近づくため、慣性は必ず低下します。そのため、エルボー法ではkに対する慣性のグラフを描き、低下の度合いが緩やかになる点を探します。シルエットスコアは、各点について、自身のクラスタ内の平均距離と最も近い別クラスタまでの平均距離を比較します。スコアは-1から1の範囲をとり、コンパクトで明確に分離されたクラスタほど高くなります。この例では、4つの中心の周辺から生成したデータについて、kを2から6まで評価します。

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

k=2で18,363だった慣性は、k=3で5,241、k=4で1,127に低下します。その後はk=5で1,039、k=6で922に下がるだけなので、エルボーはk=4にあります。シルエットスコアもこれを裏付けています。k=4で0.811となり、最大値を記録した後、k=5で0.687に下がるため、データの生成元となった4つの中心を特定できます。

前提とバリエーション#

k-meansは、クラスタがほぼ球状で、サイズが似ており、ユークリッド空間で分離されている場合に最もよく機能します。スケールの大きい特徴量は距離への影響が大きいため、通常は事前にデータを標準化します。すべての点がいずれかのクラスタに割り当てられ、極端な外れ値が少数あるだけでも、重心がそのグループから引き離されることがあります。いくつかのバリエーションでは、こうした制約を緩和します。

• ミニバッチk-means: 小さなランダムバッチを使って重心を更新します。大規模なデータセットでの学習を大幅に高速化する代わりに、精度が少し低下します。
• k-medoids: 実際のデータ点をクラスタ中心として使うため、外れ値に対してより頑健であり、任意の距離尺度に対応します。
• ファジーc-means: ファジー論理の考え方に基づき、各点を1つのクラスタに明確に割り当てるのではなく、すべてのクラスタに対する所属度を与えます。
• ガウス混合モデル: クラスタごとに確率分布を当てはめるため、サイズの異なる楕円形のクラスタを扱え、確率に基づく柔軟な割り当てを返します。

AIとコンピュータービジョンでの応用#

• 色の量子化: 画像のピクセル色をクラスタリングし、各ピクセルを重心に置き換えると、数千色を含む写真を k 色のパレットに圧縮できます。画像を圧縮できるだけでなく、簡易的で高速な画像セグメンテーションにもなります。
• コードブックとベクトル量子化: 重心がコードブックを形成し、各ベクトルは最も近い重心のインデックスとして保存されます。古典的な bag-of-visual-words 画像検索では、ローカル画像記述子からこの方法で語彙を構築していました。
• アンカーボックスの設計: YOLOv2 は、学習用ボックスの幅と高さに対して、距離を 1 から IoU を引いた値として k-means を実行し、アンカーボックスを選択しました。
• 重みのパレット化: quantize=8 を使って YOLO26 を Core ML にエクスポートすると、各大規模重みテンソルの値が k-means によって 256 個の重心にクラスタリングされます。そのため、エクスポートされたモデルは各重みにつき 8 ビットのインデックスと、小さなルックアップテーブルを保存します。
• 顧客セグメンテーション: 小売業者は、購入頻度、買い物かごの大きさ、最終購入時期に基づいて顧客をグループ分けし、各セグメントに合わせた特典を提供します。

K-Means と関連アルゴリズムの比較#

• k 近傍法（KNN）: 共通する「k」が混同の原因になります。KNN は教師ありアルゴリズムで、最も近い k 個のラベル付きサンプルに基づいて新しい点にラベルを付けます。一方、k-means は教師なしで、作成するクラスタの数を k で指定します。
• DBSCAN: 密度に基づいて点をグループ化し、クラスタ数を自動で見つけ、あらゆる形状のクラスタに対応します。また、疎な点を無理にクラスタに割り当てず、ノイズとしてラベル付けします。
• 階層クラスタリング: 最も近いグループを繰り返し統合して入れ子状のクラスタの木を構築します。そのため、木を任意の段階で切ることで後から k を選べますが、点の数に対して少なくとも二次的に増加するコストがかかります。