K-meansクラスタリング入門から実務活用まで：アルゴリズムの基本、初期化、評価指標、k の決定法を詳解
エバープレイ編集部概要：K平均法（k-means）とは何か
K平均法（k-means）は、代表的な非階層的クラスタリング手法の一つで、与えられたデータ集合をあらかじめ決めたクラスタ数 k に分割し、各クラスタ内のデータ点とクラスタ中心（セントロイド）との二乗距離の総和を最小化することを目的とします。数値データに対する素早く実用的なクラスタリング手法として広く使われ、機械学習やデータ分析の教科書・ライブラリに必ず登場します。
歴史的背景
K平均法の起源は1950年代にさかのぼり、Steinhaus（1956）らの研究や、Forgy（1965）、Lloyd（1957の社内報告、1982で公開）、MacQueen（1967）が行った分類手法の議論が基礎となっています。現在標準的に用いられる反復更新アルゴリズム（Lloyd の手法）は「k-means」や「Lloyd's algorithm」として知られています。
アルゴリズムの基本原理
典型的な k 平均法（Lloyd's algorithm）の手順は次の通りです。
- 1. 初期化：クラスタ数 k を決め、k 個の初期セントロイドを設定する（ランダムにデータ点を選ぶなど）。
- 2. 割り当てステップ：各データ点を、最も近い（通常はユークリッド距離で）セントロイドに割り当てる。
- 3. 更新ステップ：各クラスタのセントロイドを、そのクラスタに属するデータ点の平均（ベクトル平均）に更新する。
- 4. 収束判定：セントロイドの移動が小さい、あるいは割り当てが変わらないなどの条件を満たせば終了。満たさなければ 2 に戻る。
この反復により、目的関数（各点とその割当てられたセントロイドとの二乗距離和、within-cluster sum of squares: WCSS）が単調減少し、最終的に局所最適解に収束します。
数学的定式化
データ点 x_i (i=1,...,n)、クラスタ中心 μ_j (j=1,...,k) に対して、k 平均法は次の目的関数を最小化する問題と等価です。
min_{C, μ} sum_{j=1}^{k} sum_{x_i in C_j} ||x_i - μ_j||^2
ここで C_j は j 番目のクラスタのデータ集合。μ_j は C_j の平均であることが最適解の条件から導かれます（ユークリッド距離の下での最小分散性）。
初期化と k-means++
初期セントロイドの選び方は結果に大きく影響します。代表的な方法は以下の通りです。
- Forgy（ランダムに k 個のデータ点を選ぶ）
- ランダムパーティション（ランダムにラベルを与える）
- k-means++（Arthur & Vassilvitskii, 2007）：初期化を工夫して初期クラスタを分散させ、より良い初期解と高速な収束を得る）
k-means++ は、最初のセントロイドをランダムに選び、残りは既存セントロイドからの距離に比例した確率で選ぶことで、期待値での性能保証を持ちます。実務では k-means++ がデフォルトで用いられることが多いです。
収束性と計算量
Lloyd のアルゴリズムは反復ごとに目的関数を減少させるため有限ステップで収束しますが、それは局所最適解への収束であり、必ずしもグローバル最適ではありません。理論的には最悪ケースで反復回数が指数的になることが知られており（Vattani による負例など）、しかし実務上は通常数十〜数百回で収束します。
計算量は1反復あたり O(n k d)（n: データ数、k: クラスタ数、d: 次元数）が目安です。大規模データでは計算コストが問題となるため、Mini-Batch k-means などの近似手法が利用されます。
クラスタ数 k の決め方
k を事前に決める必要がある点は k 平均法の大きな課題です。代表的な選定手法は次の通りです。
- エルボー法：WCSS の k に対するプロットで「ひじ」ができる点を選ぶ。
- シルエットスコア：各点のクラスタ内距離と最短の他クラスタ距離の比からクラスタ分離度を評価。
- ギャップ統計量（Tibshirani et al., 2001）：無構造データと比較して得られる差分で最適 k を推定。
- Calinski-Harabasz 指数、Davies-Bouldin 指数などの内部評価指標。
評価指標
クラスタリングの妥当性は教師なしで評価するため難しいですが、以下の指標がよく用いられます。
- Within-Cluster Sum of Squares（inertia）: 小さいほど密集している。
- シルエットスコア: [-1,1] の範囲、高いほど良好。
- Calinski-Harabasz、Davies-Bouldin: クラスタ間分離とクラスタ内一貫性を数値化。
問題点・注意点
k 平均法にはいくつかの前提・欠点があり、適用時に注意が必要です。
- 数値データ・ユークリッド距離前提：カテゴリ変数や非線形距離にはそのままは不向き。カテゴリデータには k-modes や混合手法を検討する。
- 球状クラスタ仮定：各クラスタが近似的に球状で、似た分散を持つ場合によく機能する。細長いクラスタや密度差がある場合は誤った分割をする。
- 局所最適解：初期化により結果が変わるため、複数回の初期化（n_init）や k-means++ の利用が推奨される。
- スケーリングの影響：各特徴量のスケール差が結果に影響するため標準化（z-score）や正規化が重要。
- 高次元問題（次元の呪い）：距離が希薄になり意味を失う場合がある。次元削減（PCA 等）を検討する。
- 空クラスタの発生：割り当て後にクラスタが空になる場合の対処（再初期化、最遠点を割り当てる等）が必要。
実務での使い方とコツ
- 前処理：欠損値処理、標準化、外れ値の確認を行う。
- 初期化は k-means++ を使い、複数回ランダムシードで実行して最良解を採用する（scikit-learn では n_init パラメータ）。
- 次元削減（PCA, t-SNE, UMAP）は可視化やノイズ低減に有効。ただしクラスタ構造を変える可能性があるので注意。
- 大規模データでは Mini-Batch k-means を検討する。高速だが解の品質は若干劣る場合がある。
- 解釈性のためにクラスタごとの代表値や分布、重要変数を確認する。
派生アルゴリズム・関連手法
- k-medoids（PAM 等）：代表点をデータ点から選ぶため外れ値に強い。
- Fuzzy c-means（曖昧クラスタリング）：各点が複数クラスタに属する確率（重み）を持つ。
- Gaussian Mixture Model（GMM）：確率モデルに基づきクラスタを連続的に表現、楕円形のクラスタを扱える。
- Spectral Clustering、DBSCAN：非球状クラスタや密度ベースの分離に有効。
まとめ
K平均法はシンプルで実装が容易、計算効率も良いため広く使われますが、前提条件や限界（ユークリッド距離仮定、球状クラスタ、k の指定が必要等）を理解した上で利用することが重要です。実務では初期化（k-means++）、スケーリング、複数回実行、適切な k の選定、場合によっては代替アルゴリズムの検討といった実践的な工夫が求められます。
参考文献
- K-means clustering — Wikipedia
- Lloyd's algorithm — Wikipedia
- Arthur, D. and Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding (SODA paper)
- MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations (original k-means reference)
- Vattani, A. (2011). k-means requires exponentially many iterations (arXiv/preprint)
- scikit-learn: KMeans — Implementation notes and practical tips
- Tibshirani, R., Walther, G., & Hastie, T. (2001). Estimating the number of clusters via the gap statistic (説明: ギャップ統計量の起源; 関連文献はESL等で参照可能)
投稿者プロフィール
