K-Means Clustering

K-MeansはデータをK個のクラスタに分割し、クラスタ内二乗距離（慣性）を最小化します。

$$ J = \sum_{i=1}^{N} \min_{1 \leq j \leq K} \left\lVert x_i - \mu_j \right\rVert^2 $$

各サンプルは最も近い重心に割り当てられ、重心は割り当てられたサンプルの平均として再計算されます。

アルゴリズムは2つの決定的ステップを交互に行います:

$$ c_i \leftarrow \arg\min_j \lVert x_i - \mu_j \rVert^2 $$

$$ \mu_j \leftarrow \frac{1}{|C_j|}\sum_{x_i \in C_j} x_i $$

慣性は単調に減少し、局所最適に収束します。

ランダム初期化は簡単ですが、悪いシードから始まる可能性があります。

k-means++は初期重心を分散させ、多くの場合より速い収束と低い最終慣性をもたらします。

本番では異なるシードで複数回実行し、局所最小への感度を下げます。