のんびり読書日記

日々の記録をつらつらと

COP-KMEANS(Constrained K-means)を試してみた

制約付きクラスタリング・半教師ありクラスタリングは、クラスタリングをする際に制約を与えることで精度を向上させる手法です。制約は2つのデータ間の関係を定義した、以下がよく使われるようです。

  • must-link
  • cannot-link

今回はとりあえず制約付きクラスタリングの論文で多く引用されていて、以下の論文を参考に実装してみました。手法がK-meansを少し改良しただけで一番簡単そうだったのと、最新の動向まで調べきれなかったので、まずはとっかかりとして。

  • "Constrained K-means Clustering with Background Knowledge", by Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schroedl. ICML 2001
  • Java Appletのデモ

上記の論文ではCOP-KMEANS(Costrained K-means)という手法を提案しています。手法はK-meansを改良したもので、各データとクラスタ中心との距離を測定して一番中心が近いクラスタに割り当てるときにmust-link, cannot-link制約をチェックして、制約を満たすものの内で一番近いクラスタに割り当てるようにしています。制約を満たすクラスタが存在しなかった場合は、クラスタリングを中止します。

作成したソースコードgithubに置いてあります。いい加減ブログにべた貼りは止めていこうかなと^^;

実際に使用するときは以下のようにしてください。

% cat /path/data.tsv  # 入力データ
1       a       2       b       2       c       2       d       -1      e       -1      f       -1
2       a       2       b       -1      c       2       d       -1      e       -1      f       -1
3       a       2       b       2       c       -1      d       -1      e       -1      f       -1
4       a       -1      b       -1      c       -1      d       2       e       2       f       2
5       a       -1      b       -1      c       -1      d       2       e       -1      f       2
6       a       -1      b       -1      c       -1      d       2       e       2       f       -1

% cat /path/constraint.tsv  # 制約データ
1       4       m           # ID1  ID2  m(ust),c(annot)
2       3       c

% g++ cop_kmeans.cc -O3 -o cop_kmeans
% cop_kmeans 2 /path/data.tsv
kmeans loop No.0 ...
kmeans loop No.1 ...
1       0
2       0
3       0
4       1
5       1
6       1
% cop_kmeans 2 /path/data.tsv /path/constraint.tsv
kmeans loop No.0 ...
kmeans loop No.1 ...
1       1
2       1
3       0
4       1
5       0
6       1

(見やすいように出力結果を一部並べ替えてます)

制約として、{1, 4}は同じクラスタ(must-link)、{2, 3}は違うクラスタ(cannot-link)を指定しました。その結果、 制約なしでは{1, 2, 3}, {4, 5, 6}とクラスタリングされていたのが、{1, 2, 4, 6}, {3, 5}とクラスタリング結果が変化しました。一応制約は効いてるみたいですね。

ただ論文通りの手法だと、制約が満たされなかった時点ですぐにクラスタリングを中止してしまうので、データを見る順番によってクラスタリングがすぐに止まってしまう可能性が高そうです。データの順番をランダムに見るようにして、制約を満たさなかった場合は違う順番で何回か試行するようにすればいいのかな?またcannot-linkを重視した方が精度がよくなる、と他の論文にありましたので、その点を考慮してアルゴリズムを改良した方がよさそう。って、そんなことはとっくにやられてそうですけど。

また前回の記事ではOpenMPを使いましたが、今回はOpenMPは使用していません。制約を満たすように一つ一つデータを見ていくインクリメンタルなアルゴリズムなので、このままだと並列化が難しそうです。制約を毎回チェックするのではなく、すべてクラスタに割り当てた後で制約を満たすように修正するように変更すれば、クラスタに割り当てる部分は並列化できるかな。

でもまずはもっと最近の論文も読むのが先ですかね^^; これが定番、みたいな論文ないのかなぁ。