k-means++とは何か？初期化の重要性と実務での利点を解説する完全ガイド
エバープレイ編集部k-means++とは何か — 概要と背景
k-means++は、クラスタリング手法であるk-means（Lloyd法）の初期中心点（セントロイド）を賢く初期化するためのアルゴリズムです。従来のk-meansは初期中心の選び方に敏感で、ランダム初期化では収束先が悪かったり、収束に時間がかかったりすることが多くありました。k-means++はその問題を緩和し、k-meansの目的関数（点と割り当てられたクラスタ中心との二乗距離和）を期待値の意味で良好にする確率的初期化手法として2007年に提案されました。
なぜ初期化が重要か
k-meansの目的関数は非凸で局所最適解が多数存在する。
初期中心により、最終的なクラスタ割当てが大きく変わる。ランダム初期化だと悪い局所最適に陥る確率が高い。
初期化が悪いと収束までに反復回数が増え、計算コストが増大する。
k-means++のアルゴリズム手順（基本形）
以下がk-means++で中心を選ぶ標準的な手順です。
1点目の中心をデータ点から一様ランダムに選ぶ。
各データ点xについて、すでに選ばれた最近接中心までの距離の二乗D(x)^2を計算する。ここでD(x)は点xと最も近い選択済み中心との距離である。
次の中心を、点xを確率P(x) ∝ D(x)^2に従って確率的に選ぶ。
これをk個の中心が選ばれるまで繰り返す。
初期中心が決まったら通常のk-means（Lloydの反復：割当て→再計算）を行う。
なぜ二乗距離を使うのか（D(x)^2の理由）
k-meansの目的は各クラスタ内の二乗距離和を最小化することです。したがって、中心の選択に際して「二乗距離」を重みとして用いるのは目的関数と整合します。D(x)^2を重みとすることで、既存中心から遠い点（潜在的に過小評価されがちなクラスタの代表点）が選ばれる確率が高まり、初期中心がデータ全体に分散するよう促されます。
理論的保証
k-means++を提案したArthur & Vassilvitskii (2007) の結果では、k-means++で初期化した場合の期待される最終コスト（k-means目的関数の値）は、最適解のO(log k)倍である、という期待値の近似保証が示されています。つまり、極端に悪いケース（ランダム初期化で起こり得る）を避ける確率的な保証が与えられます。ただしこれは期待値に関する保証であり、単一実行で必ず最適近くになることを保証するわけではありません。
計算量・オーバーヘッド
初期化段階では各中心選択ごとに全データ点の最近接距離D(x)を更新する必要があるため、単純実装ではO(k n d)（n: データ点数、k: クラスタ数、d: 次元数）の計算コストがかかる。kが大きい・次元が高い場合は初期化コストが無視できない。
しかしその初期化コストは、改善された収束速度やより良い解によって後の反復回数を減らしトータルで有利になることが多い。
実務での利点と注意点
利点：
- ランダム初期化に比べて、平均的に良い初期中心を与えやすく、目的関数の値が低くなる傾向がある。
- 収束までの反復回数が減ることが多い。
- Scikit-learnなど主要ライブラリで標準実装され、使いやすい。
注意点：
- 依然として局所最適に陥る可能性があるため、複数回の初期化（n_init）を行うことが推奨される。
- 外れ値に敏感：遠く離れた外れ値が高い確率で中心に選ばれる可能性がある。外れ値の除去やロバストな前処理が必要な場合がある。
- 特徴量のスケールに敏感：標準化（zスコアや最小–最大スケーリング等）を先に行うべき。
- kの選定問題は残る：どのkが適切かは別途決定する必要がある（エルボー法、シルエット等）。
大規模データや並列化の工夫
巨大データセットに対してk-means++の逐次的な選択は遅くなるため、並列化・近似手法が提案されています。代表例はk-means||（k-means-parallel）で、複数の候補点を並列でサンプリングし、その後重み付きサンプリングで中心を絞る方法です。これにより分散環境（MapReduce等）でのスケーラブルな初期化が可能になります。
実践的な推奨設定
ライブラリでの利用：多くのライブラリ（例: scikit-learn）はk-means++をデフォルトの初期化としている。scikit-learnではinit='k-means++'。
複数回の初期化（n_init）を指定して最良結果を採用する。典型的には10回以上。
データは標準化（Feature scaling）しておく。カテゴリ変数や混合データの場合は前処理を工夫する。
外れ値の検出・除去やロバストな距離尺度（必要なら）を検討する。
大規模データではmini-batch k-meansやk-means||を検討する。
k-means++でも解決できない問題
クラスタの形が球状でない（非線形分離）場合、k-means系の手法自体が不適切である。
適切なkの自動選択は依然として難しい。
カテゴリ変数を含むデータや混合距離尺度ではそのまま使えない場合がある。
まとめ
k-means++は、単純なランダム初期化に比べてk-meansの初期中心を賢く選ぶことで平均的な性能を大きく向上させる実用的かつ理論的保証のある手法です。計算コストは若干増えるものの、実務では多くの場合メリットが上回ります。極端なケースや大規模データではk-means||やmini-batch k-meansなどの派生手法を検討するのが良いでしょう。
参考文献
- David Arthur and Sergei Vassilvitskii, "k-means++: The Advantages of Careful Seeding" (2007)
- Wikipedia: k-means++
- Scikit-learn: sklearn.cluster.KMeans (init='k-means++' の説明)
- Bahmani et al., "Scalable k-means++" (k-means||、2012)
- Wikipedia: k-means clustering（背景とLloyd法について）
投稿者プロフィール
