備忘録とか日常とか

学んだこととかを書きます。

k-Medoids Clusteringを実装した【python】

教師なし学習の非階層的クラスタリング手法としてk-Meansが一般的であるが、その拡張であるk-Medoidsを実装した。

動機

SIFT, SURFを使ったBOVWで何かできないかなーと考えていたが、特許の問題でSIFT, SURFが使えないと知った。(python2なら使えるのかも?)

[追記 2019/9/11]----------------------
python3 にてSIFTが使用可能なopencv-contrib もあった

pip install opencv-contrib-python==3.4.2.17

これ以降のverでは以下のエラーが出て使用できない。オプション設定してビルドし直せば使えるらしい。

error: OpenCV(4.1.0) /io/opencv_contrib/modules/xfeatures2d/src/sift.cpp:1207: error: (-213:The function/feature is not implemented) This algorithm is patented and is excluded in this configuration; Set OPENCV_ENABLE_NONFREE CMake option and rebuild the library in function 'create'

以下参考。
opencv - sift = cv2.xfeatures2d.SIFT_create() not working even though have contrib installed - Stack Overflow
pythonからopencvを使うときは大抵ビルド済みバイナリを取ってくるが、このページで履歴を追える。
あくまでビルド済みバイナリは有志によって提供されているため、non-free-algorithm使いたきゃ自分でビルドしろ、というスタンス↓
Include non-free algorithms · Issue #126 · skvark/opencv-python · GitHub

[追記終わり]-------------------------


じゃあopencvでタダで使える特徴量はあるのか調べたところ

  • BRISK
  • ORB
  • KAZE
  • AKAZE

あたりが候補らしい。KAZE以外はバイナリ特徴量ということで、何も考えずユークリッド距離によるk-meansに突っ込むと望まない結果になりそう。
対策としては以下二つくらい。

  • ユークリッド距離以外の基準を使用できるk-meansを実装する
  • k-Medoidsを実装する

距離の基準を変更したk-meansは探すといくつか実装が出てきたが、k-Medoidsを初めて聞いたのもあり、せっかくなので実装してみた。

k-Medoidsとは

k-means, k-Medoidsの考え方の発展は以下のページがわかりやすかった。
(実装もかなり参考にした)
www.dskomei.com

簡単にいうと、k-meansではサンプルの重心をクラスタ中心とするのに対し、k-Medoidsではサンプル自身をクラスタ中心とする。
k-Medoidsではクラスタ中心をcentroidではなくmedoidと呼ぶ。

1. ランダムにk個のサンプルを選択し、medoidとする
2. 全てのサンプルを最近傍のmedoidのクラスタに割り当てる
3. 各クラスタ内で、二点間の距離の総和が最小となるようにmedoidを割り当てる
4. 2, 3を、一定回数medoidを更新する or medoidの変化量が一定値以下になる まで繰り返す

というのがざっくりした流れ。

利点

  • 外れ値に強い
  • 重心を定義する必要がない

ということが挙げられる。
特に二つ目は、k-meansでは距離尺度に応じて逐一重心(平均)を定めてやる必要があるが、k-Medoidsではその必要がなくなる。

欠点

  • k-meansより計算量が多い(k-meansはO(Nk), k-MedoidsはO(N^2 k) )
  • k-means同様、初期値の影響を強く受ける

クラスタ内の平均を求めるには単純計算でrange(0, N)のループで済むのに対し、距離の総和が最小となるmedoidを選ぼうとすると二乗オーダの計算量となる。
下記の実装では行列演算で単純なループを回避することもできるようにしたが、メモリの使用量がバカにならないのでN, kが大きくなると使えない。

初期値に関してはk-meansも同じ問題を抱えており、最初に選択されたクラスタセンタが近い距離にあるとうまくいかない。
これの対策として、初期値のクラスタ中心がなるべく固まらないように選択するk-means++という方法が広く使われている。(詳細は上記サイトを参考に)
scikit-learnのk-meansはこれに加え、初期値を複数計算してその中でもっともクラスタ中心の偏りがない(=クラスタ中心とサンプルの距離の総和が最小となる)初期値を選択する、という処理が行われている。小さいデータで何回か試して見たところ、この「最も良さげな初期値を選択する」という操作でクラスタリング結果がかなり向上することがわかった。大規模な実データではどうなるか不明だが、k-means++に加えて実用上では必須テクな気がする。


そんなわけで、k-means++の初期化と初期値選択も実装した。
初期値選択は並列演算で実施できるようにしたが、言うまでもなくメモリをバカ喰いするので実際に使う際はn_jobs=1にするしかない。アーメン。
(もっと工夫すれば省メモリでうまいことできるのかもしれないが力尽きた)



k-medoids

初期化による違いやk-Medoidsの検証はこのサイトが詳しいので割愛・・・
自分で何回か試したところ、k-means++でも初期値選択を行わなければ良い結果にならないことが確認できた。
あくまで確率分布にしたがって初期化しているため、一回の初期化だけでは十分に良い結果が得られない。

BOW用ラッパーも書いたので、そちら方面で検証したいところである。