K-meansとは｜アルゴリズム・初期化・kの決め方まで解説する実務向け完全ガイド
エバープレイ編集部K-means とは — 概要
K-means（ケイミーンズ）は、与えられたデータ集合をあらかじめ指定したクラスタ数 k に分割するための代表的なクラスタリング手法です。各クラスタは「重心（centroid）」で表現され、アルゴリズムは各点と所属クラスタ重心との二乗ユークリッド距離の和（SSE: sum of squared errors／inertia）を最小化することを目的として反復的に重心と割り当てを更新します。簡潔で計算効率が高く、多くの実務・研究領域で利用されています。
基本アルゴリズム（Lloyd のアルゴリズム）
典型的な手順は以下のとおりです。
- 初期化: k 個の重心 μ1,…,μk を初期化する（ランダム選択や k-means++ など）。
- 割り当てステップ: 各データ点 x_i を最も近い重心に割り当てる（最近傍）。
- 更新ステップ: 各クラスタの重心 μ_j を、そのクラスタに属する点の平均に更新する。
- 収束判定: 割り当てが変わらない、または目的関数の減少が小さい場合に終了。
目的関数（最小化対象）は典型的に
J = Σ_{i=1}^n ||x_i - μ_{c(i)}||^2
です。Lloyd のアルゴリズムは各反復で J を減少させ、有限回で停止しますが、局所最小に陥る可能性があるため複数回の再実行や良い初期化が重要です。
初期化と改善手法
初期化は結果に大きく影響するため、代表的な方法を押さえておきます。
- Forgy（ランダムな k 点を選ぶ）: 単純だがばらつきが大きい。
- k-means++（Arthur & Vassilvitskii, 2007）: 初期シードを確率的に選び、期待誤差を改善する。実装上のデフォルトとして広く使われる。
- 階層クラスタや密度ベースの手法で初期クラスタを与える: 状況によって有効。
- 複数回ランダム再実行（restarts）: 最良解を選ぶ。
計算量と収束特性
1 イテレーションの計算量は O(n k d)（n: データ数, k: クラスタ数, d: 次元数）程度です。イテレーション回数は経験的には少ないことが多いですが、最悪ケースでは多くの反復を要する可能性があります（Lloyd のアルゴリズムは理論的に局所最小に収束するのみ）。また、k を含めた一般的な k-means の最適化問題（グローバル最小化）は NP-困難であることが知られています（実務ではヒューリスティックで対処）。
実務上の注意点
- スケーリング: 特徴量は標準化（平均0・分散1）や正規化が必須。スケールの異なる変数があると距離計算で不利になる。
- 次元の呪い: 高次元では距離が均一化しやすく、次元削減（PCA 等）や特徴選択が有効。
- 外れ値: 重心は平均に敏感。外れ値の影響を減らすには k-medoids（代表点を実データにする）やロバストな前処理が有効。
- カテゴリカル変数: そのまま距離を取るのは不適。k-modes や適切な埋め込みを用いる。
- 空クラスタの扱い: 更新でクラスタが空になることがある。典型的には最も分散の大きいクラスタを分割するか、ランダム点を割り当てる。
クラスタ数 k の決め方
k は通常事前に与える必要があり、選定には以下のような手法が使われます。
- Elbow（ひじ）法: SSE（inertia）が急激に減少しなくなる点を探す。
- シルエットスコア: クラスタ分離度と一貫性を評価。-1〜1 の値で高いほど良好。
- Gap 統計量（Tibshirani et al., 2001）: ランダム参照分布との差を用いて k を選ぶ。
- 外部知識: ドメイン知識や目的（マーケティングでのセグメント数など）に基づく決定。
派生手法・代替手法
- k-medoids / PAM: 中心として実データ点（メドイド）を使い、外れ値に強い。
- Gaussian Mixture Models（GMM）: ソフトクラスタリングを行う確率モデル（EMアルゴリズム）。クラスタの形状が球状でない場合に有利。
- Kernel k-means: カーネルを使って非線形分離のクラスタを扱う。
- Spherical k-means: テキストのような角度（コサイン類似度）で扱うデータに適する。
- Mini-batch K-means（Sculley, 2010）: 大規模データ向けに確率的更新を用いて高速化。
- 加速アルゴリズム（Elkan 等）: 三角不等式を利用して距離計算を削減する工夫。
評価指標と可視化
内部評価指標としてはシルエット、Calinski-Harabasz、Davies-Bouldin などがあり、外部に正解ラベルがある場合は ARI（Adjusted Rand Index）や NMI（Normalized Mutual Information）を使います。可視化には 2D/3D に投影した散布図（PCA, t-SNE, UMAP）や各クラスタの重心・サイズ・代表例を示すのが有効です。
代表的な適用例
- 画像圧縮（色空間の量子化）
- 顧客セグメンテーション
- 異常検知（小さなクラスタを異常とみなす）
- ドキュメント分類・トピックの前処理（Spherical k-means）
実装上のチェックリスト
- 入力データを確認：欠損・スケール・外れ値の扱いを決める。
- 初期化方法を選択（k-means++ を推奨）。
- 複数回のランダムシードで安定性を確認。
- k の候補を複数評価して最適化（Elbow・シルエット等）。
- 収束基準（最大反復数・許容誤差）を設定。
- 結果を可視化し、ドメイン知識で妥当性を確認。
まとめ
K-means は実装が容易で計算も速く、多くの実務で第一選択となるクラスタリング法ですが、球状クラスタやスケールの整った数値データに強い一方、初期値依存性、外れ値への脆弱性、高次元データでの性能低下などの制約があります。実運用では前処理（スケーリング、次元削減）、k の選定、初期化改善（k-means++、再実行）を組み合わせることで実用的な結果を得られます。また、必要に応じて GMM・k-medoids・スペクトラルクラスタリングなど代替手法を検討してください。
参考文献
- K-means clustering — Wikipedia
- MacQueen, J. (1967). Some Methods for classification and Analysis of Multivariate Observations.
- Arthur, D. & Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding.
- Scikit-learn: KMeans — ドキュメント
- Sculley, D. (2010). Web-scale k-means clustering (Mini-Batch K-means).
- Tibshirani, R., Walther, G., Hastie, T. (2001). Estimating the number of clusters via the gap statistic.
- Aloise, D. et al. (2009). NP-hardness of k-means (論文概要・複雑性に関する議論).
