k-meansアルゴリズムの仕組みを徹底解説！クラスタ分割の基本から収束条件まで

k-meansアルゴリズムとは？

k-means（k平均法）は、データマイニングや機械学習で広く利用されている代表的な非階層型クラスタリング手法です。このアルゴリズムは、入力パラメータとして指定された k をもとに、n個のオブジェクトをk個のクラスタへ分割します。その目標は、「同じクラスタ内のオブジェクト同士はできるだけ似通っている（クラスタ内類似度が高い）一方で、異なるクラスタ間のオブジェクトはできるだけ似ていない（クラスタ間類似度が低い）」という状態を実現することです。

クラスタの類似度は、そのクラスタに含まれるオブジェクト群の平均値（平均ベクトル）を基準にして計算されます。この平均値は、クラスタの「重心」あるいは「中心（セントロイド）」と見なすことができます。

k-meansの基本的な処理の流れ

k-meansアルゴリズムは、おおむね以下のステップで進行します。

1. 初期化： オブジェクトの中からランダムにk個を選び、それぞれを初期のクラスタ中心（平均）とします。
2. 割り当て： 残りの各オブジェクトについて、オブジェクトと各クラスタ中心との距離を測定し、最も近い（最も類似している）クラスタに割り当てます。
3. 更新： 各クラスタの新しい平均値（重心）を計算します。
4. 反復： 割り当てと更新を繰り返し、基準関数が収束するまで続けます。

平方誤差基準（Square-Error Criterion）

収束の判定には、一般に平方誤差基準が用いられます。これは次の式で表されます。

E = Σ_i=1^k Σ_{p∈Ci |p − mi|²}

• E：データセット内の全オブジェクトに対する平方誤差の総和
• p：対象オブジェクトを表す空間上の点（多次元）
• m_i：クラスタ C_i の平均値（多次元）

この基準では、各クラスタに属するすべてのオブジェクトについて「オブジェクトからクラスタ中心までの距離の二乗」を求め、それらを合計します。つまり、結果として得られるk個のクラスタを可能な限りコンパクトで、かつ相互に独立なものにすることを目指しています。

アルゴリズム：k-means

概要： 分割型クラスタリングのためのk-meansアルゴリズム。各クラスタの中心は、そのクラスタに属するオブジェクトの平均値によって定義されます。

入力

k：クラスタの数
D：n個のオブジェクトを含むデータセット

出力

k個のクラスタの集合

手順

1. Dの中から任意にk個のオブジェクトを選択し、初期クラスタ中心とする。
2. 以下を繰り返す（repeat）：
   ・各クラスタ内のオブジェクトの平均値に基づき、各オブジェクトを最も類似しているクラスタに（再）割り当てる。
   ・クラスタの平均値を更新する（各クラスタのオブジェクトの平均値を再計算する）。
3. 変化がなくなるまで続ける（until no change）。

動作例と「反復再配置」

たとえば、3つのオブジェクトを任意に選んで3つの初期クラスタ中心とします（図ではクラスタ中心を「+」で示すのが一般的です）。その後、各オブジェクトは最も近いクラスタ中心に基づいてクラスタへ割り振られます。

次に、クラスタ中心を更新します。各クラスタの現在のオブジェクト群に基づいて平均値を再計算し、新しいクラスタ中心を求めます。この新しい中心を用いて、オブジェクトを再度最寄りのクラスタに割り当て直します。この再割り当てによって、破線で囲まれるような新しいクラスタの輪郭が形成されていきます。

このようにオブジェクトのクラスタへの割り当てを繰り返し改善していくプロセスは「反復再配置（iterative relocation）」と呼ばれます。どのクラスタでもオブジェクトの再配置が発生しなくなった時点でプロセスは終了し、その時点でのクラスタ構成が最終的なクラスタリング結果として確定します。

まとめ

k-meansはシンプルでありながら強力なクラスタリング手法です。ただし、初期中心の選び方によって結果が左右されやすいこと、あらかじめクラスタ数kを決めておく必要があることには留意が必要です。それでも大規模データに対しても比較的高速に動作するため、顧客セグメンテーションや画像圧縮など、実務のさまざまな場面で広く活用されています。