K-means法

$K$-means法は非階層型クラスタリングの一種である．非階層クラスタリングとは、与えられたデータを決められたクラスタ数で分割し，各クラスタが互いに似た性質を持つ分割方法を探索する手法である．階層クラスタリングと異なり、階層的な構造を持たず、サンプル数が大きいビッグデータを分析するときに適している。

$K$-means法は与えられたデータとクラスタの中心との距離を測定して使ってデータを$K$個のクラスタに分割する手法である．$c_j$をクラスタ$C_j$の重心点，すなわち，クラスタ$C_j$内の粒子の平均$c_j=\sum_{x∈C_j}\frac{x}{|C_j|}$とし，以下の評価関数を最小化するように$K$個のクラスタに分割する．

$$c_i=\sum_{i=1}^K\sum_{x∈C_i}(x-c_j)^2$$

1. ランダムにデータ$X(x_i,x_2,…,x_n)$を$K$個のクラスタに割り振る
2. クラスタの重心点$c_j(j=1,2,…,K)$を計算する
3. データ$X(x_i,x_2,…,x_n)$最も近いクラスタの重心点$c_j(j=1,2,…,K)$にクラスタを割り当て直す．
4. クラスタの重心点が移動しなくなるまで，もしくは既定回数になるまでStep2とStep3を繰り返す．

• アルゴリズム