ｋ平均法とは - 理数の散策路

ｋ平均法

ｋ平均法（k-means method）とは、クラスタ分析の手法の１つで、クラスタの重心との距離を最も小さくする基準でクラスタを形成していく方法です。クラスタの数（$k$）は固定とするため、この名前が付いています。

尚、クラスタ分析とは、対象（サンプル）間の距離を定義し、距離の近さによって対象を分類する分析方法の総称です。

ｋ平均法の目的関数 $J$ を以下で定義します。ここで、$x$ はサンプル（総数 $n$ 個）です。$r_{ij}$ は、クラスタ $j$ にサンプル $x_i$ が含まれれば “１”、含まれなければ “０” の２値をとります。

$$J=\sum_{i=1}^n\sum_{j=1}^kr_{ij}(x_i-z_j)^2　　-①$$

ｋ平均法では、この $J$ を最小にする $r_{ij}$ を求めます。

尚 $z$ は、与えられた $r_{ij}$ の下、$J$ が最小値（停留値）をもつ条件として求められます。

$$\frac{\partial J}{\partial z_j}=-\sum_{i=1}^n2r_{ij}(x_i-z_j)=0$$$$z_j=\frac{\sum_{i=1}^nr_{ij}x_i}{\sum_{i=1}^nr_{ij}}　　-②$$

このように、$z_j$ は各クラスタの重心を表すことが分かります。

ｋ平均法のアルゴリズムは以下になります。

初期のクラスタ分けはランダムに行い、この｛$r_{ij}$｝を $R_0$ とする。
$R_0$ でのクラスタ重心を計算する。
$$z_j=\frac{\sum_{i=1}^nr_{ij}x_i}{\sum_{i=1}^nr_{ij}}　　-②$$
目的関数（①）を小さくする $R_1$ を求める。
つまり、各サンプルから最も近い重心のクラスタに移動させます。
$$m=\mathrm{arg}\Big(\mathrm{min}|x_i-z_m|\Big)$$$$r_{ij}=\left\{\begin{array}{ll}
1 & (j=m) \\
0 & (j\ne m)\end{array} \right.$$例えば、サンプル $x_1$ をクラスタ２に移動する場合は、$r_{12}=1$ とし、それ以外を $r_{ij}=0$ とします。
収束条件は $R_l=R_{l+1}$（クラスタを移動させるサンプルがない）とする。収束していなければ、ステップ２から繰り返す。

サンプル数を５、クラスタ数を２の例を考えます。

サンプル	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
値	$3$	$7$	$1$	$6$	$2$