Mode-seeking by Medoidshifts

CV 文献

クラスタ数がはっきりしない状態でクラスタリングを行う手法として
MeanshiftやMedoidshiftがあるが、Medoidshiftがあまり分かっていなかったので

Mode-seeking by Medoidshifts
Yaser Ajmal Sheikh, E.Khan, and Takeo Kanade
Eleventh IEEE International Conference on Computer Vision (ICCV 2007), October, 2007.

を読んでみました.
どうもComplexityがO(N^2.38)で済むらしく速いらしい。

meanshift・・・

  • N点との距離計算をシフトする毎に計算

medoidshift・・・

  • NxNの距離行列を作ってしまえば以後シフト時の距離比較は行列を参照すればok

これが一番の理由のようです。

具体的な手順は以下の通り

  1. 距離行列Dと重み行列Kを計算し、その積の行列S＝DKを計算
  2. Sのi列目に注目し、最小となる要素jを探す
  3. j列目に移動
  4. 移動しなくなるまで手順2，3を繰り返す。この時のiから最後のjまでの集合が１つのクラスタとなる。medoidは最後のインデックス番目の要素
  5. 全ての要素を属するクラスタのmedoidに置換

案外簡単そうなので明日にでも実装してみよう。