K-meansとK-means++

K-meansとは

大変単純なアルゴリズム。
まず、クラスターの中心を初期化して適当に置きます

\mu^{(0)} = [\mu_1^{(0)}, ...., \mu_k^{(0)}]

そして、収束するまで、
- 各サンプルから一番近い中心を選ぶ

z_i \leftarrow arg \min_{j \in {1,...,k}} || x_i - \mu_j^{(t-1)}||_2^2

-割り当てられたデータサンプルの中で平均をとり、クラスタの中心を更新する

\mu_j^{(t)} \leftarrow \frac{1}{n_j}\sum_{i:z_i = j} x_i

の2つを繰り返します。一番簡単なやつ。

KKZ法

次に、KKZ法は少しk-meansを改良したやつになります。「クラスタの中心同士は離れているべきでしょ」という考え方に基づいています。

$Step1$ ランダムにクラスタの中心の初期値を1つ選びます。
$Step2$ それぞれの点から一番近いクラスタの中心との距離を取ります。
$Step3$ $Step2$でとった距離の中で一番最大なサンプルを新しいクラスタの中心とします。

($Step2$から$Step4$をクラスタの中心の数がk個になるまで続けます。)
ただ、このアルゴリズムは外れ値があるとうまく動きません。

K-means++法

今回は、「一番距離が大きいもの」が次の点に選ばれるのではなくて、「距離が大きいものが確率的に選ばれるようにする」というのがポイントです。

$Step1$ ランダムにクラスタの中心の初期値を1つ選びます。
$Step2$ それぞれの点から一番近いクラスタの中心との距離$D(x)$を取ります。
$Step3$ 重み付き確率分布を$\phi(x) = \frac{D(x_i)}{\sum_k D(x_k)}$とし、代表ベクトルをランダムに選ぶ。
($Step2$から$Step4$をクラスタの中心の数がk個になるまで続けます。)