X-means とコサイン距離によるクラスタリング

X-means にコサイン距離を組み込みたくて,D.Pelleg and A.Moore の論文 "X-means: Extending K-means with Efficient Estimation of the Number of Cluster" と Weka のソースを参考にプログラムを書いた(チェックは不十分だし,エラーハンドリングもいい加減だが,概ね出来たつもり).

早速,単位円上にサンプルを分布させてクラスタリングを試みた.

準備したデータは2次元かつ3クラスを想定して,以下のとおり.サンプル数は全て50個/クラス.

  • theta=[0, PI/10]の一様分布に対して x=(cos theta, sin theta)
  • theta=[PI*2/10, PI*3/10]の一様分布に対して x=(cos theta, sin theta)
  • theta=[PI*4/10, PI*5/10]の一様分布に対して x=(cos theta, sin theta)

X-means において minNumCluster=2, maxNumCluster=20 を設定して,得られたクラスタは下図のように12個(図はクラスタ中心をプロットしている).
f:id:ymuto109:20110119003656g:image

見てのとおり,過剰に分けている.X-means により得られるクラスタ数は under-estimate だったはずなのに・・・.
cutoff value を導入するか.