K-meansクラスタリングは、もともと信号処理に由来するベクトル量子化の手法であり、n個の観測データをk個のクラスタに分割する。各観測データは、最も近い平均値（クラスタ中心またはセントロイド）を持つクラスタに属する。これにより、データ空間はボロノイ細胞に分割される。このアルゴリズムは、顧客セグメンテーション、画像圧縮、パターン認識など、教師なしデータ分析で広く使用されている。
K-meansは、クラスタ内の分散を最小化する。これは2乗ユークリッド距離によって測定されるが、通常のユークリッド距離ではない。通常のユークリッド距離はより困難なウェーバー問題になる。平均二乗誤りを最適化し、一方で幾何学的中央値のみがユークリッド距離を最小化する。たとえば、k-メディアンやk-メドイドを使用することで、より良いユークリッド解が見つかる可能性がある。
この問題は計算上困難（NP困難）である。ただし、効率的なヒューリスティックアルゴリズムは局所最適解にすばやく収束する。これらは通常、ガウス分布の混合の期待値最大化アルゴリズムとそれに類似し、k-meansとガウス混合モデルの両方が使用する反復改良アプローチに基づいている。どちらもデータをモデル化するためにクラス中心を使用するが、k-meansクラスタリングは同等の空間的範囲を持つクラスタを見つける傾向があり、一方ガウス混合モデルはクラスタが異なる形状を持つことを許容する。
教師なしのk-meansアルゴリズムは、k近傍分類器と緩い関係にある。k近傍分類器は一般的な教師ありマシン・ラーニングの分類技術であり、名前が似ているためにk-meansと混同されることが多い。k-meansによって得られたクラス中心に1近傍分類器を適用すると、既存のクラスに新しいデータを分類する。となり、これは最近セントロイド分類器またはロキオのアルゴリズムとして知られる。
正式な定義
観測データの集合（x1, x2, ..., xn）が与えられ、各観測データがd次元の実ベクトルであるとき、k-meansクラスタリングはn個の観測データをk（≤ n）の集合S = {S1, S2, ..., Sk}に分割し、クラス内の平方和（WCSS）、つまり分散を最小化することを目的とする。形式的には、目的は次のようなものとなる。
minimize over S of Σ from i=1 to k Σ from x in Si of ||x - μi||^2
ここで、μiはSiの点の平均（セントロイドとも呼ぶ）であり、||·||は通常のL2ノルムである。これは、平均からの平方距離の合計が平均対の平方距離の平均に等しいという同一性によって示されるように、同じクラス内の点間のペアごとの平方偏差を最小化することと同等である。
アルゴリズム
最も一般的なアルゴリズムはしばしば作ロイドのアルゴリズムと呼ばれ、反復的な未知改善アプローチを使用する。最初にk個のセントロイドの初期集合から始まり、割り当て手順と更新手順の2つの手順を交互に繰り返す。割り当て手順では、各観測データが、通常はコーヒー距離を使用して、最も近いセントロイドを持つクラスに割り当てられる。更新手順では、各クラスタのセントロイドが、割り当てられた点の平均として再計算される。割り当てが変更されなくなるまでこれらの手順が繰り返され、局所最適解への収束を示すとなる。
初期化は重要であり、初期セントロイドを広く分散させるk-means++法は、最終的なクラスタリングの質を向上させる人気のヒューリスティックである。このアルゴリズムはkの選択に敏感であり、エルボー法などの手法は適切なクラス数の見積りに使用されるされる。
特性と制限
k-meansは、球形で類似した大きさのクラスタを仮定しており、複雑な形状のクラスを持つデータには適用性が制限される。また、クラスタの中心になる平均が極端な値に影響されやすいため、外れ値にも敏感である。このアルゴリズムは局所的最適解に収束し、必ずしも大局的最適解には収束せず、異なる初期化では異なる結果が得られる。これらの制限にもかかわらず、その単純性とスケーラビリティのおかげで、特にデータ補強や前処理のパイプラインで大規模データセットに人気のある選択肢となっている。
応用
k-meansは様々な領域で使用されている。人工知能では、クラスタリングタスクのベースラインとして機能する。コンピューサービジョンでは、画像張り抜きや色量子化に使用される。マーケティングにおいては、購買行動に基づく顧客セグメンテーションの助けとなる。自然言語処理では、文書やワードの埋め込みをクラスタリングできる。このアルゴリズムはまた、ディープラーニングの特徴学習やGenerative AIなど、より高度な技術の基盤としてある。
他の手法との関係
k-meansは、反復的な帰属とクラスタ中心を使用するため、ガウスの混合モデルと関連している。しかし、ガウスの混合モデルはクラスタの異なる形状や共分散を許容する一方、k-meansは等方的なクラスタを仮定する。k-means由来の最近セントロイド分類器は、単純な教師あり分類手法である。k-meansはk近傍（k-NN）と混同されがちだが、両者は明確に異なり、k-meansは教師なしであり、k-NNは教師ありである。
歴史と発展
k-meansの概念は1956年にステインハウスのよって初めて提案され、1967年にジェームズ・Ｒ・マックウィーンによって「k-means」という用語が造られた。はりのアルゴリズムは、1957年に発表されたものの1982年まで広く知られなかったため、標準な実装とされている。長年にわたり、大規模データ向けのミニバッチk-meansなどのさまざまな変形版や、ソフタークラスリング用のファジーc-meansが開発されている。