制約伝播による制約クラスタリングの効率化

岡部 正幸（豊橋技術科学大学）
山田 誠二（国立情報学研究所／総研大／東工大）

ユーザフィードバックにより与えられる制約が少数である場合に，効率的に実行可能である制約クラスタリングを開発している．基本的な戦略は，ペアワイズ制約を周辺のデータへ伝播させることにより，少数の制約を拡張して，それを用いて類似度行列の学習を行う．クラスタリング自体は，通常のk-means法により，学習された類似度行列をもちいて実行される．

通常よく用いられるMust/Cannotリンクによるペアワイズ制約をベースに，k個の近傍データにも同様の制約を伝播することで少数制約を拡張し，少数制約による制約クラスタリングを実現する．制約を充足する類似度の学習を行うため，制約の伝播および充足が半正定値計画による最適化問題に帰着される．そして，提案手法の有効性がいくつかのクラスタリングタスクで実験的に示される．

文献

• Masayuki Okabe and Seiji Yamada: Learning Similarity Matrix from Constraints of Relational Neighbors, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.14, No.4, pp. 402-407 (May. 2010)
• Masayuki Okabe and Seiji Yamada: Clustering with Constrained Similarity Learning, In Proceedings of the International Workshop on Intelligent Web Interaction 2009 (IWI 2009), Milan, Italy, pp.30-33 (Sep. 2009)