K-Meansクラスタリングは、元々は信号処理に由来するベクトル量子化の手法であり、観測値の集合をk個のクラスタに分割する。各観測値は、クラスタ重心として知られる最も近い平均値を持つクラスタに属する。これにより、データ空間はボロノイ細胞に分割される。このアルゴリズムは、機械学習において顧客セグメンテーション、画像圧縮、パターン認識などのタスクで広く使用されており、人工知能やデータ分析における基礎的な手法である。
k-meansの目的は、クラスタ内平方和（WCSS）を最小化することである。これは、各点とそのクラスタ重心との間のユークリッド距離の二乗和である。これは、同じクラスタ内の点のペアごとの二乗偏差を最小化することと等価である。しかし、k-meansはユークリッド距離の二乗を最小化するのであり、通常のユークリッド距離ではない。後者を最小化するには、より困難なウェーバー問題を解く必要がある。ユークリッド距離の最小化には、k-mediansやk-medoidsのような代替手法がより適切である。
最適なk-meansクラスタリングを見つける問題は計算的に困難（NP困難）であるが、効率的なヒューリスティックアルゴリズムは局所最適解に迅速に収束する。最も一般的なアプローチはロイドのアルゴリズムであり、これは点を最も近い重心に割り当て、その後、割り当てられた点の平均に重心を更新することを反復する。この反復的洗練は、ガウス混合モデルに使用される期待値最大化アルゴリズムに類似しているが、k-meansは同等の空間的広がりを持つクラスタを見つける傾向があり、ガウス混合は異なる形状を許容する。
アルゴリズムと実装
標準的なk-meansアルゴリズムは、k個の重心の初期集合から始まる。これはランダムに選択されるか、収束を改善するためにk-means++のような方法を使用して選択される。アルゴリズムは収束するまで2つのステップを繰り返す。割り当てでは、各観測値が最も近い重心を持つクラスタに割り当てられ、更新では、各重心がそのクラスタ内のすべての点の平均として再計算される。収束は通常、割り当てが変化しなくなったとき、またはWCSSの改善がしきい値を下回ったときに検出される。
大規模データセット用のミニバッチk-meansやテキストデータ用の球面k-meansなど、いくつかの変種が存在する。kの選択は、エルボー法、シルエット分析、ギャップ統計量を使用して決定されることが多い。アルゴリズムの時間計算量はおおよそO(nkd*i)であり、ここでnは観測値の数、dは次元数、iは反復回数である。
他の手法との関係
K-meansは教師なしアルゴリズムであり、ラベル付きデータを必要としない。これは、教師あり手法であるk近傍法（k-NN）分類器と緩い関係がある。k-meansによって得られたクラスタ重心に1近傍分類器を適用すると、新しいデータが既存のクラスタに分類される。これは、最近傍重心分類器またはロッチオアルゴリズムとして知られている。この関連性は、教師なしクラスタリングが教師ありタスクをサポートできることを強調している。
K-meansはガウス混合モデル（GMM）にも関連している。両方ともクラスタ重心を使用してデータをモデル化するが、GMMはクラスタが異なる形状とサイズを持つことを許容する一方、k-meansは類似した分散を持つ球状クラスタを仮定する。その結果、k-meansはより単純で高速であるが、柔軟性に欠ける。
応用と限界
K-meansは多くの分野で使用されている。Amazon Web ServicesやGoogle Cloudでは、ユーザー行動の分析やリソース割り当ての最適化のための一般的なツールである。コンピュータビジョンでは、画像セグメンテーションや色量子化に使用される。マーケティングでは、購買パターンに基づいて顧客をセグメント化する。このアルゴリズムは、深層学習の特徴抽出や生成AIのデータ前処理など、より複雑な手法の構成要素でもある。
しかし、k-meansには限界がある。クラスタ数kを事前に指定する必要があり、これは常に既知であるとは限らない。初期重心の選択に敏感であるが、k-means++はこれを軽減する。クラスタが凸で等方的であることを仮定しており、これは実世界のデータには当てはまらない場合がある。外れ値は重心を歪める可能性があり、アルゴリズムは局所最適解に収束する可能性がある。これらの問題にもかかわらず、その単純さと効率性から、人気のある選択肢である。
歴史的背景と発展
K-meansアルゴリズムは、1956年にヒューゴ・シュタインハウスによって最初に提案され、後に1957年にベル研究所のスチュアート・ロイドによって洗練された（ただし、1982年まで公開されなかった）。「k-means」という名前は、1967年にジェームズ・マックイーンによって造られた。それ以来、より良い初期化のためのk-means++やスケーラビリティのためのミニバッチ変種など、多くの改良が開発されてきた。このアルゴリズムは、機械学習のカリキュラムの定番であり、scikit-learnやTensorFlowなどの主要なライブラリに実装されている。