K-meansクラスタリングとは？原理・アルゴリズム・初期化・K選定・実務上の注意点を一挙解説

K-meansクラスタリングとは何か

K-meansクラスタリングは、与えられたデータ集合をあらかじめ指定したクラスタ数 K に分割し、同じクラスタ内のデータが互いに似ている（近い）ようにする代表的な分割型クラスタリング手法です。目的は「各クラスタ内部の分散（または二乗距離和）を最小化する」ことにあり、しばしば「最小二乗誤差（Within-Cluster Sum of Squares, WCSS）」を最小化する問題として定式化されます。

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

K-means の代表的な実装は Lloyd の反復法で、以下の2つのステップを交互に繰り返します。

• 割当（Assignment）ステップ：各データ点を、現在のクラスタ中心（重心、centroid）に最も近いクラスタに割り当てる。
• 更新（Update）ステップ：各クラスタに割り当てられた点の平均を計算し、それを新しいクラスタ中心とする。

この処理を WCSS が収束するか、最大反復回数に達するまで繰り返します。Lloyd のアルゴリズムは逐次的に目的関数を減少させるため有限回で停止し、局所最適解に収束しますが、必ずしも大域最適解を保証するわけではありません。

目的関数（定式化）

データ点 x_i（i=1...n）とクラスタ中心 μ_j（j=1...K）を用いると、K-means の目的は次を最小化することです（Euclid 距離の二乗）:

J = Σ_{i=1}^n || x_i − μ_{c(i)} ||^2

ここで c(i) は点 i の割当クラスタインデックスです。

計算量と理論的性質

• 1反復あたりの計算量は O(n · K · d)（n: データ数, K: クラスタ数, d: 次元数）です。反復回数 t を含めると O(n K d t) となります。
• Lloyd のアルゴリズムは局所最適解に収束しますが、一般次元での大域最適化は NP-困難であることが知られています。

初期化方法とその重要性

K-means は初期クラスタ中心に敏感で、悪い初期化により不適切な局所解に収束することがあります。代表的な初期化手法：

• ランダム初期化：データ点からランダムに K 個選ぶ（単純だが不安定）。
• K-means++：Arthur & Vassilvitskii (2007) により提案。初期中心を確率的に離れて選ぶことで、良い初期化と理論的保証（期待値での性能向上）を提供する。
• 階層クラスタリングや分割型手法による事前クラスタリングを初期値に使う。
• 複数回の実行（複数の初期化 n_init）を行い、最も良い目的関数値の結果を採用する。

クラスタ数 K の決め方

K の選択はユーザの目的とデータに依存します。代表的な方法：

• エルボー法（Elbow）：WCSS を K に対してプロットし、減少が緩やかになる「肘」の位置を探す。
• シルエット係数：各点の内集団凝集度と他クラスタへの分離度を計測し、平均シルエットが最大になる K を探す。
• ギャップ統計量（Gap Statistic）：参照分布との誤差差を評価する方法。
• 指数基準（BIC/AIC）や外部指標、ドメイン知識、業務的要件に基づく選択。

前処理と実務上の注意点

• スケーリング：K-means は距離（通常はユークリッド距離）に基づくため、特徴量のスケールが異なる場合は標準化（zスコア）や正規化が必要です。
• 外れ値の影響：K-means は外れ値に弱く、重心が引っ張られることがある。外れ値除去やロバストな初期化（trimmed k-means 等）を検討する。
• 次元削減：高次元データでは距離の意味が薄れる（次元の呪い）。PCA などで次元圧縮してからクラスタリングを行うのが一般的。
• カテゴリカルデータ：K-means は連続値に適する。カテゴリデータには k-modes、k-prototypes、距離定義を工夫した手法がある。

評価指標（クラスタ品質の定量評価）

• 内部評価：WCSS（inertia）、シルエット係数、Davies–Bouldin 指数、Calinski–Harabasz 指数など。
• 外部評価：もし真のラベルがあれば、正解ラベルとの一致を ARI（Adjusted Rand Index）やNMI（Normalized Mutual Information）で評価できる。

拡張・派生アルゴリズム

• Mini-Batch K-means：大規模データ向けにミニバッチを用いて高速化した手法（オンライン更新で計算量とメモリを削減）。
• Fuzzy C-means（ファジィクラスタリング）：データ点が複数クラスタに所属し得る確率的・連続的重みで割り当てる。
• Spherical K-means：コサイン類似度に基づくクラスタリングで、テキスト（正規化ベクトル）に適する。
• K-modes / K-prototypes：カテゴリカルデータまたは混合データのための手法。

適用例（ユースケース）

• 顧客セグメンテーション：購買履歴や行動に基づいたグループ化。
• 画像圧縮：色空間をクラスタリングして代表色に置き換える（ベクトル量子化）。
• 異常検知の前処理：クラスタ中心からの距離を用いて異常スコアを算出する。
• 市場バスケット分析や特徴空間の把握など探索的分析全般。

K-means の限界と落とし穴

• 非球状（非凸）なクラスタや密度差の大きいクラスタには不向き。
• クラスタ数を事前に指定する必要がある（自動で適切な K を決める機構は標準ではない）。
• 外れ値やスケールに敏感である。
• 初期値依存：複数回実行して安定解を選ぶ必要がある。

実装上の実践的アドバイス

• 前処理：欠損値処理、スケーリング、外れ値検出を必ず行う。
• 可視化：2次元または 3次元に落として（PCA、t-SNE、UMAP）クラスタの形状を確認する。
• 複数指標の併用：エルボー法だけでなく、シルエットや業務要件を組み合わせて K を決める。
• 複数初期化（n_init）と k-means++ を用いる。大規模データでは Mini-Batch を検討。
• 結果の解釈：クラスタ中心だけ見るのではなく、クラスタ内分布や代表的なサンプルを確認する。

関連理論・背景

K-means は古典的な手法で、Lloyd（1957 の技術報告、後に 1982 に広く引用）や MacQueen（1967）に起源があり、Arthur & Vassilvitskii (2007) による k-means++ は実用的な初期化として広く採用されています。また、等分散で共分散行列がスカラー倍のガウス混合モデル（GMM）の最尤推定の極限として K-means が関係する、という確率的解釈もあります（EM アルゴリズムとの関係）。

まとめ

K-means はシンプルで計算効率が良く、探索的分析や大規模データの初期クラスタリングに非常に有効です。一方で、クラスタの形状や外れ値、スケール感に弱く、初期化と K の選択が結果に大きく影響します。実務では事前処理、複数回試行、評価指標の併用、可視化をセットで行うことで信頼できるクラスタ分析が可能になります。

参考文献

• K-means clustering — Wikipedia
• D. Arthur and S. Vassilvitskii, "k-means++: The Advantages of Careful Seeding" (2007)
• scikit-learn: KMeans（ドキュメント）
• J. MacQueen, "Some Methods for Classification and Analysis of Multivariate Observations" (1967)
• Lloyd's algorithm — Wikipedia
• A. K. Jain, "Data Clustering: 50 years beyond K-means"（総説、参考用）