k-means法

機械学習

k-means法はプロトタイプベース(prototype-based)クラスタリングというカテゴリに属している.
アルゴリズムは以下の通りである.

1.クラスタの中心の初期値として,サンプル点からk個のセントロイドをランダムに選びだす.
2.各サンプルを最も近いセントロイドに割り当てる.
3.セントロイドに割り当てられたサンプルの中心にセントロイドを移動する.
4.サンプル点へのクラスタの割当が変化しなくなるか,ユーザー定義の許容値またはイテレーションの最大回数に達するまでステップ2-3を繰り返す.

ステップ4について,オブジェクトの類似度を測定するにはm次元空間にある2つの点
xベクトルとyベクトルのユークリッド距離の2乗は
d(x,y)^2=\sum_{j=1}^{m}(x_{j}-y_{j})^{2} = |x-y|_{2}^{2}