k-means++法

機械学習

k-means法ではセントロイドの初期値が不適切である場合, クラスタリングが上手く行かなかったり収束に時間がかかる場合がある.
この問題の対策としては

  • k-meansアルゴリズムを一つのデータセットで複数回実行し,誤差平方和から最も性能が良いモデルを選択する.
  • 初期のセントロイドを互いに離れた位置に置くこと(k-means++法)

k-means++法での初期化

  1. 選択の対象となるk個のセントロイドを格納するために空のデータセットMを初期化する
  2. 入力サンプルから初期のセントロイド \muをランダムに選択しMに割り当てる
  3. Mに含まれていないサンプル x^{i}ごとにMのセントロイドに対して距離の2乗が最小となるセントロイドを求める
  4. 次のセントロイド \mu をランダムに選択するには各サンプルの距離の重みを等しく以下の確立分布を使用する

\frac{d(\mu^{p},M)^{2}}{\sum_{i}d(x^{i},M)^{2}}

  1. k個のセントロイドが選択されるまでステップ3-4を繰り返す
  2. 従来のk-means法を使って引き続き処理を行う