文献

J-GLOBAL ID：201202258382860017   整理番号：12A0617102

制約付きグラフカットによる逐次クラスタリング

Iterative Clustering with Constrained Graph Cut

著者 (4件)： 岡部正幸 (豊橋技術科学大学 情報メディア基盤センター) ,  山田誠二 (国立情報学研究所) ,  山田誠二 (総合研究大学院大学) ,  山田誠二 (東京工業大学)
資料名： 人工知能学会論文誌(Web)  (TJSAI (Web))
巻： 27  号： 3  ページ： 193-203 (J-STAGE)  発行年： 2012年 
JST資料番号： U0128A  ISSN： 1346-8030  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフカットに基づくクラスタリングではデータ対に与えられる制約をエッジの切断に関する教師情報と解釈できる。本論文では,グラフのカット容量が最大になるようにデータ集合を分割する最大カット問題を制約付きで解くために,半正定値計画(SDP)による緩和問題として定式化した。一般に制約クラスタリングでは同一クラスタに属すべきデータ対(mustリンク)と,同一クラスタに属すべきでないデータ対(cannnotリンク)を利用するが,制約付きグラフカットによる2分割クラスタリングを逐次的に実行する本方法ではcannnotリンクを扱わない。具体的に,mustリンク制約を組み込んだSDPを解くことで得られた解行列を利用し,発見的手法に基づいて短時間で精度のよいクラスタ分割が行える実際的手続きを示した。ベンチマークデータとしてUCIレポジトリデータ及びCLUTOデータを用いた実験では,1)カーネル行列学習,2)距離学習,3)制約付きK-Meansと制約数を変化させた場合の比較を行った。その結果,本手法は少なくとも1)~3)と同等以上のクラスタリング性能を持ち,データ数が大きくなるとSDPソルバーの実行に時間を要するが,生成すべきクラスタ数が多くても1)よりも計算時間が不利にならないことを示した。

シソーラス用語： *クラスタ化 ,  画像処理 ,  *カットセット ,  リンク ,  制約条件 ,  クラスタ分析 ,  クラスタ分割 ,  *性能評価 ,  CPU時間
準シソーラス用語： *クラスタリング ,  *グラフカット ,  カーネル行列 ,  計算時間

分類 (3件)： システム・制御理論一般  (IA02010H) ,  グラフ理論基礎  (IA02020S) ,  計算機システム開発  (JD02010R)

引用文献 (24件)：

• [Basu 08] Basu, S., Davidson, I., and Wagstaff, K. eds.: Clustering: Advances in Algorithms, Theory, and Applications, Chapman & Hall (2008)
• [Carpineto 09] Carpineto, C., Osinski, S., Romano, G., and Weiss, D.: A Survey of Web Clustering Engines, ACM Computing Surveys (CSUR), Vol. 41, No. 3, p. 17 (2009)
• [Davis 07] Davis, J. V., Kulis, B., Jain, P., Sra, S., and Dhillon, I. S.: Information-theoretic metric learning, in Proceedings of the 24th International Conference on Machine Learning, ICML '07, pp. 209-216 (2007)
• [De Bie 04] De Bie, T., Suykens, J., and De Moor, B.: Learning from General Label Constraints, Structural, Syntactic, and Statistical Pattern Recognition, pp. 671-679 (2004)
• [藤沢 97] 藤沢 克樹: 半正定値計画 (SDP) に対する内点法プログラムの数値実験, 京都大学数理解析研究所 数理解析研究所講究録, Vol. 1004, pp. 190-199 (1997)

タイトルに関連する用語 (4件)： 制約 ,  グラフカット ,  逐次 ,  クラスタリング