The 26th Annual Conference of the Japanese Society for Artificial Intelligence, 2012

4F1-OS-5-1

ブースティングに基づく制約付き K-means アルゴリズム
Boosted Constrained K-means Algorithm∗1

豊橋技術科学大学

岡部正幸∗1

山田誠二∗2

Masayuki OKABE

Seiji YAMADA∗2

国立情報学研究所／総合研究大学院大学／東京工業大学

Toyohashi University of Technology

National Institute of Informatics

COP-KMEANS is a light weight constrained clustering algorithm in terms of computational cost, which isdesirable for interactive data mining systems that potentially require responce performance. However, COPKMEANS has several problems caused by the order of the data assignment in the clustering procedure. This paper
proposes a method to avoid such problems and improve the performance of COP-KMEANS by using boosting
technique. Based on the boosting framework, we control the data assignment order using weights that are given
to must/cannot-link constraints in the process of boosting. Experimental results show that our proposed method
eﬀectively improves the performance of COP-KMEANS.

1.

はじめに

本研究では，COP-KMEANS が持つこれらの問題点を補う方法としてブースティングの適用を試みる．ブースティングでは，訓練データの重みを適応的に変化させながら生成した複数の弱学習器を統合することで，単独の弱学習器よりも精度の高い判別を行うことができるとされている．我々は，COPKMEANS をブースティングにおける弱学習器に見立て，弱学習器が生成した複数のクラスタリング結果を統合することで最終的に精度の高いクラスタ集合を得ることを目指す．また，同時にブースティングによって与えられた制約に対する重みを，COP-KMEANS におけるクラスタ中心へのデータ割当順序の決定に用いるなどの修正を COP-KMEANS に対して行う．

クラスタリングはデータマイニングにおける基礎的なデータ分析手法として広く利用されているが，近年，データペアに対し制約情報を与えることでクラスタリング性能の向上を目指す制約付きクラスタリングに関する研究が進んでいる．
制約付きクラスタリングは，制約情報を予め用意しておくことで従来のクラスタリングのようにバッチ処理的に計算を行うこともできるが，タスクによっては制約情報がシステム利用者から逐次的に与えられるといった状況も想定される．このようなタスクでは，クラスタリング処理およびその結果の分析に基づく制約情報の付与というサイクルが生じ，システム利用者のフィードバックを反映させたデータ分析が可能となることが期待される．例えば，ある特定の対象の抽出を目的とした画像のセグメンテーション作業では，抽出に失敗したデータをシステム利用者が確認して初めて制約情報を与えるといった作業スタイルも考えられ，この場合，システムは利用者の制約情報の付与に応じてクラスタリングを逐次的に実行する必要がある．
このように，制約付きクラスタリングは対話的にデータ分析を行うシステムの要素技術として役立つ可能性を持っているが，実際の利用を考えた場合，その応答性能が重要となる．制約付きクラスタリングアルゴリズムは，これまでにいくつか提案されているが，その多くは距離学習 [Davis 07] やカーネル
行列学習 [Hoi 07] をベースにしたものが多く，対話的なシステムへの適用を考えた場合，その多大な計算量に起因する応答性能の低さが問題となることが予想される．
そこで本研究では，制約付きクラスタリングアルゴリズムの中で計算量が比較的少ない COP-KMEANS[Wagstaﬀ 01] に着目する．COP-KMEANS の計算量は，k-means と同じくクラスタリング対象となるデータ数の線形オーダーであるため，応答性能を考えた場合に有利である反面，距離学習などをベースとしたものに比べクラスタリング性能の面では不利であり，また，クラスタ中心へのデータの割当順序によっては，クラスタ集合が生成されず停止してしまうというアルゴリズム的な欠点が存在する．

2.

COP-KMEANS

COP-KMEANS は分割型クラスタリングの代表的アルゴリズムである k-means をベースとしており，その基本アルゴリズムは，1) 初期クラスタ中心の選択，2) 各データのクラスタ中心への割当，3) クラスタ中心の更新という主に 3 つの処理からなる．この内の 2) の処理について，通常の k-means では，データを割り当てるべきクラスタ中心は，データとの距離が最も近いものが選択されるが，COP-KMEANS の場合は，その他に，“与えられたすべての制約に違反しないもの” という条件も合わせて考慮される．つまり，データとの距離が最も近いクラスタ中心であっても，そのクラスタ中心に既に割り当てられているデータとの間に制約違反が確認された場合は，別のクラスタ中心に割り当てられる．また，候補となるクラスタ中心すべてに制約違反が確認された場合は，割り当て可能なクラスタ中心がないことからアルゴリズムが停止する．
COP-KMEANS では，このような状況が発生した場合への対処は特に規定されておらず，クラスタリングが成功に終わるか失敗に終わるかは，クラスタ中心へのデータの割り当て順序に大きく依存するという特徴をもつ．本研究では，COPKMEANS が持つこのような問題に対処するため，以下のアプローチを取る．
1. 制約をすべて充足させることを諦める．データ数に対する制約数の割合が増加するにつれ，制約を完全に充足させることが困難になるため，部分的な充足しか行えない場合でもクラスタリング処理を完了させる．

連絡先: 岡部正幸，豊橋技術科学大学情報メディア基盤センター〒 441-8580 豊橋市天伯町雲雀ヶ丘 1-1
okabe@imc.tut.ac.jp1

The 26th Annual Conference of the Japanese Society for Artificial Intelligence, 2012
2. ブースティングを利用することにより，制約集合が部分的にしか充足されないクラスタリングアルゴリズムを用いた場合でも，精度の高いクラスタリングが行えることを目指す．

Algorithm 1 Boosted Constrained Kernel K-means= {x1 , ..., x|X| }，制約集合 S ={(i1 , j1 , y1 ), ..., (i|S| , j|S| , y|S| )}2: 出力：クラスタ集合 C
1: 入力：データ集合 X

次章では，このアプローチに基づくブースティングベースの制約付きクラスタリングアルゴリズムとブースティングにおける弱学習器として利用するために修正した COP-KMEANS アルゴリズムの詳細について説明する．

3: wi ← |S|
0

4: for t = 1 to T do
5:3.

ブースティングに基づく制約付きクラスタリング

Modiﬁed COP-KMEANS アルゴリズムを実行し，その結果に基づき，カーネル行列 K t を生成する．

{
kt (i, j) =前章における議論に基づき，本章ではブースティングベースの制約付きクラスタリングアルゴリズムと修正版 COP-KMEANSを提案する．提案方法の特徴は主に以下の 2 つである．

6:

1. ブースティングを導入することにより，制約集合が部分的にしか充足されていない複数のクラスタリング結果を統合して，精度の高いクラスタリング結果を生成する．

1−1(xi , xj ) が同じクラスタに属する場合(xi , xj ) が異なるクラスタに属する場合充足に失敗した制約の重みの割合 t を計算する．

t =

1
2

∑|S|
n=1

wnt I(k t (in , jn ), yn )∑Nn=1(1)

wnt

I(a, b) は，a 6= b のとき 1，a = b のとき 0 を返す関数．
(in , jn ) は，n 番目の制約におけるデータペアのインデックス，yn はその制約の種類を示す値（must-link の場合は 1，cannot-link の場合は-1 の値を取る）

2. ブースティングにおける弱学習器として修正版 COPKMEANS を利用している．修正版 COP-KMEANS では，ブースティング過程において制約に与えられる重みを利用して，クラスタ中心へのデータ割当順序を決定する．また，制約の充足に失敗してもアルゴリズムは停止しない．

7:

t を用いて，K t の重み αt を計算する．

{
αt = ln

ブースティングは，ランダム推定に対しある程度の優位度をもつ弱学習器が生成する弱仮説を統合することにより，精度の高い判定を行うアンサンブル学習方法の一つである．本研究では，ブースティングの適用対象となる学習問題を制約付きクラスタリングとし，制約集合を訓練データ，修正版 COP-KMEANSを弱学習器と対応づける．これにより，各制約には充足回数に基づく重みが計算されるが，修正版 COP-KMEANS ではこの重みを利用してクラスタ中心へのデータ割当順序を決定する．
以下では，提案方法の本体となるブースティングベースの制約付きカーネル K-means（Boosted Constrained Kernel Kmeans）とブースティングにおける弱学習器として利用するために修正した COP-KMEANS アルゴリズム（Modiﬁed COPKMEANS）について説明する．

3.1(i = 1 ∼ |S|)

18:

1 − tt}(2)

t+1
各制約の重み係数 wnを更新する．

{wnt+1 = wnt exp αt I(kt (in , jn ), yn )}(3)

9: end for
10: 以下の式を用いて最終的なカーネル行列 K を求める．

K=T∑

αt K t(4)

t=1

11: K を用いてカーネル K-means を実行し，最終的なクラスタリング集合 C を得る．

Boosted Constrained Kernel K-means

Algorithm 1 に Boosted Constrained Kernel K-means ア
ルゴリズムの概要を示す．このアルゴリズムは，代表的ブースティングアルゴリズムである AdaBoost[Freund 97] をベースとしている．弱学習器として，後述する修正版 COP-KMEANS を利用することを想定しており，訓練データである各制約（mustlink: 同じクラスタに属さなければならないデータペア，cannotlink: 異なるクラスタに属さなければならないデータペア）の重み計算と，修正版 COP-KMEANS が生成したクラスタリング結果を統合してカーネル行列を生成する．このカーネル行列を用いたカーネル k-means を実行することにより，最終的なクラスタリング結果が出力される．
このアルゴリズムにおいて．修正版 COP-KMEANS が行うのは制約付きクラスタリングであるが，ブースティング的な解釈では，任意のデータペアが must/cannot-link のどちらであるかを推定していると捉えることもできる．ブースティング自体はクラスタリングを直接的に行うわけではないが，質の良いカーネル行列を生成することで，クラスタリング精度を向上させることに間接的に寄与しているといえる．

3.2

Modified COP-KMEANS

Algorithm 2（本稿末尾に掲載）に，ブースティングにおける弱学習器として利用する修正版 COP-KMEANS アルゴリズムの概要を示す．このアルゴリズムは，ブースティングによって与えられた各制約の重みを利用してクラスタ中心へのデータ割当順序を決定している．一般的に割当順序が早ければ制約が充足される確率も上がるが，重みの大きな制約は充足に失敗している回数の多いものであり，そのような制約の割当を優先的に行うことで充足の成功確率を高めている．
また，割当順序が与えられるのは個々のデータではなく制約であるため，クラスタ中心へのデータ割当は制約対象となっている 2 つのデータについて同時に行う．このため，データペアがそれぞれ既に割当済みかどうか，また制約が must/cannotlink のどちらであるかによって適宜対応する処理を行う必要がある．このアルゴリズムにおいて制約の充足に失敗するのは，データペアがともに既に割当済みの場合であり，must-link であるにもかかわらず異なるクラスタ中心へ割り当てられてい2

The 26th Annual Conference of the Japanese Society for Artificial Intelligence, 2012!")$)$!"($!"($!"'$!"'$!"($!"'$-.//0$!"&$1.//0$!"&$!"&$,-../$-.//0$0-../$!"%$!"%$!"%$
1.//0$!"#$!"#$!$*!!$+!!$,!!$#!!$!"#$!$%!!$)!!$*!!$+!!$,!!$#!!$!$)!!$(b) Wine(a) Iris*!!$+!!$#!!$%!!$(c) Glass

図 1: ブースティングステップ数 T = 10 の場合の結果（グラフの縦軸は NMI，横軸は制約数を表す）*$!")$)$!")$!"($!"($!"($!"'$!"'$-.//0$!"'$
1.//0$!"&$!"&$!"&$-.//0$-.//0$!"%$!"%$!"%$1.//0$

1.//0$!"#$!"#$!$*!!$+!!$,!!$#!!$(a) Iris%!!$!"#$!$)!!$*!!$+!!$,!!$#!!$(b) Wine!$

*!!$

+!!$

,!!$

#!!$%!!$(c) Glass

図 2: ブースティングステップ数 T = 100 の場合の結果（グラフの縦軸は NMI，横軸は制約数を表す）ラベルを与えた．クラスタリング結果の評価には，正規化相互情報量 (Normalized Mutual Information, NMI) [Tang 07]を用いた．

る，または cannot-link にもかかわらず同じクラスタ中心へ割り当てられている場合である．このように，各データのクラスタ中心への割当は必ず行われ，オリジナルの COP-KMEANSのようにアルゴリズムが停止することはない．
クラスタ割当の優先順序を変えただけでは，制約充足数の増加はそれほど期待できないが，充足される制約の部分集合が変化するため，異なるクラスタリング結果を生成することができ，アンサンブル学習としての効果が期待できる．

4.

4.2

実験

本章では，提案手法の効果を調べるために行った実験結果について述べる．

4.1

実験結果

図 1 は，ブースティングステップ数を 10 とした場合の 2 つの手法の結果を示したものである．縦軸は NMI の値，横軸は制約数を表している．NMI の値は各制約数につき用意した異なる 10 セットの制約集合に対する平均値である．
提案手法（BCKKM）は，3 つのデータセット全てにおいて比較手法（RCKKM）の性能を上回る結果となった．Iris デー
タセットについて，制約数が 100 のときに，2 つの手法に差はほとんど見られなかったが，制約数が 200 以降になると，2つの手法の差は制約数が増えるにつれて大きくなった．これはBCKKM の性能が向上する一方，RCKKM は制約の効果があまり見られなかったためである．Wine データセットについて
は，制約数の増加とともに BCKKM の性能が向上することが確認されたが，RCKKM との差はそれほど拡がらないという結果になった．Glass データセットについては，Iris と傾向が似ており，制約数 300 以降で 2 手法の差が顕著になるという結果になった．
次に，ブースティングステップ数を 100 とした場合の 2 つの手法の結果を図 2 に示す．いずれのデータセットにおいても，ステップ数 10 の場合と同様の傾向が見られるが，ステップ数を増やすことによって，制約数 200 以降における BCKKM とRCKKM との差がステップ数 10 の場合よりも拡がったことが分かる．特に Wine については，2 手法の差が顕著になった．
また，Iris では制約数 200 以降において性能が急激に上昇する結果となり，Glass についても制約数 400 以降における性能の向上が確認された．
以上より，提案手法の特徴であるブースティングに基づく

実験設定

実験データには UCI レポジトリ∗1 から，3 つのデータセット
Iris (150,3)，Wine (178,3)，Glass(214,6) を使用した．カッコ内の数値は順にデータ数，クラス数を表す．各データセットは，前処理として特徴ベクトルのスケーリング（属性毎にその属性の最大値で割る操作）と正規化 (単位ベクトル化) を行った．
提案手法（以下，BCKKM と呼ぶ）の実験結果のほか，ブースティングによるデータ割当順序決定の効果を調べるため，比較手法としてデータの割当順序をランダムに決定する方法（以下，RCKKM と呼ぶ）との比較を行った．RCKKM は，制約tの重み（wn）をランダムに決定し，学習結果の重み（α）をすべて同じ値とすること以外は提案手法と同じ処理を行う．両手法とも，データとクラスタ中心との距離尺度としてユークリッド距離を用いた．
制約の生成については，ランダムにデータペアを選択し，各データセットのクラスラベルに基づいて must/cannot-link の∗1 http://archive.ics.uci.edu/ml/

3

The 26th Annual Conference of the Japanese Society for Artificial Intelligence, 2012データ割当順序の決定の効果が確認されたが，いくつか注意すべき点がある．まず，充足に失敗する制約が少ない場合（今回の実験においては各データセットでの制約数 100 の場合が該当する），各制約の重みが変化しないため，データの割当順序はランダムに生成された順序と等しくなり，ブースティングの効果が発揮されない．また，ブースティングステップ数の増加とともに性能が向上する傾向が見られたが，その分計算量も増加するため，性能と計算コストのトレードオフを探る必要がある．

5.

Algorithm 2 Modiﬁed COP-KMEANS
1: 入力：データ集合 X ，制約集合 S ，ブースティングステッt
プ t における各制約の重み wn(n = 1 ∼ |S|)
2: 出力：クラスタ集合 C

3: 初期クラスタ中心を選択する．
4: 初期クラスタ集合 C0 ← φ
5: for r = 1 to R do
6:
7:

まとめ

本研究では，制約付きクラスタリングを対話的なデータマ
イニングシステムにおいて利用することを想定し，計算量が少なくかつ精度の高いアルゴリズムの開発を目的として，ブースティングをベースとし，弱学習器に修正版 COP-KMEANS を用いる方法を提案した．提案手法は，AdaBoost アルゴリズムがベースとなっており，各制約の重みを適応的に変化させることにより，弱学習器としての修正版 COP-KMEANS から得られる複数のクラスタリング結果をカーネル行列として統合し，カーネル K-means を実行することで最終的なクラスタリング結果を出力する．修正版 COP-KMEANS はブースティングによって各制約に与えられた重みを利用してデータ割当順序を変化させることにより，充足された制約の部分集合が異なる複数のクラスタリング結果を出力することができる．
実験結果では，提案手法の特徴であるブースティングによるデータ割当順序の決定の効果が確認された．また，その効果は制約数およびブースティングステップ数の増加と比例することが分かった．
今後，より多くのデータセットにおける実験を行い，提案手法の効果についてより詳細な分析を行っていく予定である．

8:
9:

10:
11:

12:
13:
14:
15:
16:17:
18:
19:

20:

参考文献

21:
22:

[Davis 07] Davis, J. V., Kulis, B., Jain, P., Sra, S., andDhillon, I. S.: Information-Theoretic Metric Learning,in Proceedings of the 24th International Conference on
Machine Learning, ICML ’07, pp. 209–216 (2007)

23:
24:

25:

[Freund 97] Freund, Y. and Schapire, R. E.: A DecisionTheoretic Generalization of On-Line Learning and an
Application to Boosting, J. Comput. Syst. Sci., Vol. 55,
No. 1, pp. 119–139 (1997)

26:

27:
28:

[Hoi 07] Hoi, S. C. H., Jin, R., and Lyu, M. R.: Learning Nonparametric Kernel Matrices from Pairwise Constraints, in Proceedings of the 24th international conference on Machine learning, pp. 361–368, ACM (2007)

29:
30:
31:

32:

[Tang 07] Tang, W., Xiong, H., Zhong, S., and Wu, J.:
Enhancing Semi-Supervised Clustering: A Feature Projection Perspective, in Proceedings of the 13th ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 707–716 (2007)

33:
34:

t
制約を重み wnの値に基づいて，降順にソートする
ソートした順に制約データペア (xi , xj ) をクラスタ中心に割り当てる．(xi , xj ) がそれぞれ既に割り当てられているか，そうでないかによって場合分けする

if (xi , xj ) がともにまだ割り当てられていない場合 then(xi , xj ) に最も近いクラスタ中心をそれぞれ ci ，cj とし，そのクラスタ中心との距離をそれぞれ d(xi , ci )，d(xj , cj ) とする
if (xi , xj ) が must-link の場合 thend(xi , ci ) < d(xj , cj ) の場合は ci へ，それ以外の場
合は cj へ (xi , xj ) を割り当てる．
else if (xi , xj ) が cannot-link の場合 thenif ci 6= cj の場合 thenxi を ci へ，xj を cj へそれぞれ割り当てる
elsed(xi , ci ) < d(xj , cj ) の場合は xi を ci へ，xj をcj の次に近いクラスタ中心へ割り当てる．
end ifend ifelse if xi が既に割り当てられており，かつ xj がまだ割り当てられていない場合 thenxi が割り当てられているクラスタ中心を ci とする
if (xi , xj ) が must-link の場合 then
xj を ci へ割り当てる．
else if (xi , xj ) が cannot-link の場合 thenci と異なり，かつ xj に最も近いクラスタ中心に xjを割り当てる．
end ifelse if xi がまだ割り当てられておらず，かつ xj が既に割り当てられている場合 thenxj が割り当てられているクラスタ中心を cj とする
if (xi , xj ) が must-link の場合 thenxi を cj へ割り当てる．
else if (xi , xj ) が cannot-link の場合 thencj と異なり，かつ xi に最も近いクラスタ中心に xiを割り当てる．
end ifend if制約に関連しない残りのデータをそれぞれ最も距離の近いクラスタ中心へ割り当てる．

if 前回生成したクラスタ集合から変動がない場合 then
現在のクラスタ集合を出力して，終了．
37:
else
38:
クラスタ中心を更新して，次のステップへ．
39:
end if
40: end for
35:[Wagstaﬀ 01] Wagstaﬀ, K. and Roger, S.: Constrained Kmeans Clustering with Background Knowledge, in Proceedings of the 18th International Conference on Machine
Learning, pp. 577–584 (2001)

36:

4