Never Stop Questioning

k-means

最終更新:

t-style

- view
メンバー限定 登録/ログイン

工事中

k-means

 k-meansはもっともよく知られているだろうクラスタリングの手法。基本的には(1)距離が近いデータが同じクラスタになるように振り分ける処理と、(2)同じクラスタ内のデータの平均からクラスタの中心を求める処理を繰り返すことでクラスタリングを行う。
 この手法は、使いどころを押さえれば非常に有用。逆にいうと、利用上かなり厳しい前提を要求するので、データの特徴がよくわからない状況で下手に使うのはとても危険。

k-meansのよく機能する状況

  • 超球面的
 2次元で考えるなら、クラスタは円状となる。さらに円の中止から離れたときのデータの所属に対する影響はクラスタによらず一定である。したがって、ドーナッツ型やナマコ型?や星形?などになっていると、おそらく期待したクラスタに分割されない。
  • クラスタ数固定
 とにかく決められたクラスタ数に分割してしまう。1つの円を取り合ったような微妙なクラスタを作っていることを判断するのも厄介。しかも初期値設定で結果が変わる。したがって、アルゴリズムを弄らないで使う場合には、初期値とクラスタ数に幅を持たせて試す必要がある。

混合正規分布のEMアルゴリズムによる推定との関係

  • データセットへの仮定
 EMアルゴリズムは、k-means同様有限のクラスタ数を対象とする。しかし、円(分布)の位置だけでなく、データへの影響具合を分散と混合率によって制御する。また、データの所属が確率的(ソフト)であるため、重なりに対応できる。
  • アルゴリズムの流れ
 理論的な話はPRML本に書いているが、かなりわかりやすく対応づく。簡単に言えば、Eステップはデータの所属(負担率)の最適化、Mステップは円(混合分布のパラメータ)の最適化なので、EMアルゴリズムと比較すると、Eでは所属をハードに分割をしている点、Mでは円を位置だけ修正している点が違う。