K-meansクラスタリング徹底解説：基本原理・初期化・収束と実務のベストプラクティス

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

K-means法とは

K-means法は、観測データをあらかじめ指定したクラスタ数 k に分割する代表的な非階層的クラスタリング手法です。各クラスタは重心（平均ベクトル、centroid）で代表され、アルゴリズムはデータ点とそのクラスタ重心との二乗ユークリッド距離の総和（SSE: sum of squared errors、別名 inertia）を最小化することを目的に反復的に割り当てと重心の更新を行います。実務・研究の両面で広く使われており、実装も単純で計算量も比較的扱いやすいという特徴があります。

基本的なアルゴリズム（Lloydのアルゴリズム）

代表的な手順は次の通りです。

  • 初期化：k 個の初期重心を選ぶ（ランダムにデータ点を選択する方法が一般的）。
  • 割り当てステップ（Assignment）：各データ点を、最も近い重心のクラスタに割り当てる（通常はユークリッド距離を用いる）。
  • 更新ステップ（Update）：各クラスタの重心を、当該クラスタに属する点の平均で再計算する。
  • 収束判定：重心が変化しなくなるか、割り当てが安定するか、あるいは所定の最大反復回数に到達したら終了。

目的関数（最小化対象）は通常次のように書けます：J = sum_{i=1..k} sum_{x in C_i} ||x - mu_i||^2 。ここで mu_i はクラスタ i の重心、C_i はクラスタ i に属する点の集合です。

初期化とその影響

初期重心の選び方は結果に大きく影響します。代表的な方法：

  • ランダム選択（Forgy法など）：データ点から k 個を無作為に選ぶ。
  • k-means++：Arthur & Vassilvitskii (2007) により提案。初期化の分散を抑え、期待値で O(log k) の近似保証があることで広く使われます。最初の点をランダムに選び、以降は既存の重心からの距離に比例した確率で点を選ぶ。
  • その他：階層的クラスタリングで初期中心を得る、複数回実行して最良の結果を採る、k-means||（大規模データ向け）など。

収束性と理論的性質

Lloyd のアルゴリズムは各ステップで目的関数を単調減少させるため有限回で収束しますが、局所最小値に収束する可能性があり、大域最適を保証しません。一般の次元 d とクラスタ数 k に対して、最適な k-means 分割を求める問題は NP-困難であることが示されています（Aloise et al., 2009）。そのため実務では複数初期化や k-means++ などの工夫で良好な局所解を得る運用が一般的です。

距離尺度と前提

K-means は二乗ユークリッド距離（L2 ノルム）に基づく分割を前提としています。したがってクラスタが球状で、各変数が同じスケールを持つことが望ましいです。変数のスケーリング（標準化や正規化）は必須の場合が多いです。ユークリッド距離以外の距離を使うと、重心が意味を持たなくなったり、最小二乗の解釈が崩れます。この場合は k-medoids（PAM）や階層的クラスタリング、スペクトral クラスタリングなど別手法の検討が必要です。

派生手法・拡張

  • Mini-batch K-means：大規模データ向けにミニバッチで更新を行い高速化。Scikit-learn に実装あり。
  • K-modes / K-prototypes：カテゴリカルデータや混合データに対応するための拡張（代表点をモードや混合の代表にする）。
  • Spherical K-means：ベクトルを正規化しコサイン距離（内積）に基づいてクラスタリング。文章ベクトルのクラスタリングで有効。
  • Bregman 族に基づく一般化（Banerjee et al.）：平方距離以外の Bregman 発散に対する k-means の類似手法が存在。
  • K-means||：分散環境での初期化を効率化する手法（Spark 等での利用を想定）。

k の決め方（クラスタ数の選択）

k を決めるのに自動的で絶対的に正しい方法はなく、複数指標やドメイン知識を組み合わせるのが現実的です。代表的な方法：

  • エルボー法（Elbow）：SSE（inertia）を k の関数でプロットし、減少率が鈍る点を選ぶ。主観的判断が入る。
  • シルエット係数（Silhouette）：クラスタ内凝集度と最近接クラスタとの分離度を統合した尺度。-1〜1 で値が大きいほど良好。
  • ギャップ統計量（Gap Statistic）：参照分布と比較して得られる「ギャップ」を元に k を選ぶ（Tibshirani et al., 2001）。
  • Calinski-Harabasz 指標、Davies-Bouldin 指標などのクラスタ評価指標。

実務上の注意点とベストプラクティス

  • 前処理：変数のスケーリング（標準化）、外れ値の確認、不要次元の削減（PCA など）を検討する。
  • 初期化の複数試行：ランダムシードを変えて複数回実行し、最小の SSE / inertia を選ぶ。k-means++ を使うだけでも安定性が向上する。
  • 空クラスタの処理：クラスタが空になることがある。一般的な扱いはランダムに新しい重心を振るか、最も大きなクラスタから分割するなど。
  • アウトライヤの影響：k-means は平均に敏感なため外れ値に弱い。外れ値除去やロバスト手法（k-medoids）を検討する。
  • 距離の妥当性：カテゴリ変数や非等方分散なデータでは k-means は不適切な場合がある。
  • 可視化での解釈：高次元データは PCA や t-SNE, UMAP で可視化してクラスタの分離を目視確認する。

計算量と大規模データでの対策

Lloyd アルゴリズムの各反復の計算量は O(n k d)（n: データ点数、k: クラスタ数、d: 次元）です。反復回数が多くなると重くなるため、次の工夫が使われます：

  • k-means++ による良い初期化で反復回数減少。
  • ミニバッチ（MiniBatchKMeans）での確率的更新。
  • KD-tree や Ball-tree を用いた近傍探索による加速（次元が低い場合に有効）。
  • 分散実装（Spark MLlib など）やストリーミング手法。

評価と解釈の落とし穴

k-means の安易な適用は誤解を招きます。主な注意点：

  • 球状クラスタを仮定しているため、楕円状・非凸な分布やサイズの異なるクラスタには弱い。
  • スケールの違う特徴量が混在する場合、スケーリングしないと片方の変数が支配的になる。
  • クラスタの数 k を固定する必要があり、真のクラスタ数が不明だと誤った分割を生む可能性がある。
  • 結果はラベルに意味がない（ラベルは任意の順序）。ラベルの解釈はドメイン知識に基づいて行う。

他手法との比較

用途に応じて使い分けが必要です。

  • Gaussian Mixture Model（GMM）：確率的・ソフト割り当てが欲しい場合、共分散行列を考慮できるため形状の異なるクラスタにも対応可能。EM アルゴリズムで学習。
  • k-medoids（PAM）：代表点を実データから選ぶため外れ値耐性が高く、任意の距離を使える。
  • スペクトral クラスタリング：非球状クラスタやグラフ構造に適する。

まとめ（実装上のチェックリスト）

  • 目的に k-means が適しているか確認（球状、連続値、スケール統一等）。
  • データの前処理（欠損・外れ値・スケーリング・次元削減）。
  • k の候補を複数試す（エルボー、シルエット、ギャップ統計など）。
  • 初期化は k-means++、複数回実行で安定化。
  • 大規模データは Mini-batch や分散処理を検討。
  • 結果は定量評価（SSE、シルエット等）と可視化で確認し、ドメイン知識で解釈する。

参考文献

カテゴリー
IT
前の記事
Gabby Pahinuiとは—スラック・キーの革新とハワイアン・ルネサンスを牽引した伝説のミュージシャンNew!!
2025年11月20日
次の記事
k-means++とは何か？初期化の重要性と実務での利点を解説する完全ガイドNew!!
2025年11月20日