クラスタリングクラスタリングとはクラスタの良さを類似度目的関数で定義困難教師ありクラスタリング類似度目的関数ではなく教師情報制約を導入教師情報制約に一致するクラスタが良いクラスタリング問題を絶対クラスタリングと相対クラスタリングに分けて考える必要 2

Size: px

Start display at page:

Download "クラスタリングクラスタリングとはクラスタの良さを類似度目的関数で定義困難教師ありクラスタリング類似度目的関数ではなく教師情報制約を導入教師情報制約に一致するクラスタが良いクラスタリング問題を絶対クラスタリングと相対クラスタリングに分けて考える必要 2"

ひろきさかわ
5 years ago
Views:

1 教師ありクラスタリングと絶対/相対クラスタリング神嶌敏弘産業技術総合研究所 2006年情報論的学習理論ワークショップ(IBIS2006) 2006/10/31-11/2 1

2 クラスタリングクラスタリングとはクラスタの良さを類似度目的関数で定義困難教師ありクラスタリング類似度目的関数ではなく教師情報制約を導入教師情報制約に一致するクラスタが良いクラスタリング問題を絶対クラスタリングと相対クラスタリングに分けて考える必要 2

3 絶対/相対クラスタリング x と δ({xi, xj }, π(x)) は分割中で対象 π(x) i x が同じクラスタなら1 違うなら0 j π(x)は対象集合 X をクラスタリングして分割を出力クラスタリング関数対象全集合 X は未知のものを含めた全ての対象の集合教師ありクラスタリングとは対象集合と教示情報から適切なクラスタリング関数を獲得する問題獲得すべき真のクラスタリング関数が次の性質をもつなら絶対クラスタリングでなければ相対クラスタリング! δ({xi, xj }, π(x)) = δ({xi, xj }, π(x )), " " xj, xi X X, xi #=xj, X, X X 一対の対象が同じクラスタに分類されるかはクラスタリングする分類対象集合中の他の対象とは独立 3

4 絶対クラスタリングの特徴 δ({xi, xj }, π(x)) = δ({xi, xj }, π(x )), " " xj, xi X X, xi #=xj, X, X X! 一対の対象が同じクラスタに分類されるかはクラスタリングする分類対象集合中の他の対象とは独立絶対クラスタリングでのクラスタリング関数の性質 1 2 絶対クラスタの存在 δ({x i, xj }, π(x)) = δ({xi, xj }, π(x )) なので対象全集合の不変なクラスタ(絶対クラスタ C π(x ))が存在異なる対象集合間の推移性! xiと xj が同じクラスタ xj, xk X について xi, xj X と xi xk も同じであれば xj と xkは分類対象集合は異なってでといてもも同じクラスタ 4

5 reference matching 論文の参考文献を示す文字列の集合を同じ文献を引用している文字列ごとにまとめる問題表記の違い神嶌敏弘と T.Kamishima ICML と Int l Conf. on Machine Learning 表記順の違い著者題名や著者年の順ある文字列集合中の文字列1と文字列2は同じ文献を表している文字列3が加わっても文字列1や2が表す文献は不変文字列が同じクラスタに分類されるかどうかは分類する文字列集合には依存しないので reference matching は絶対クラスタリング問題 5

6 名詞句のcoreference 文書中の同じ実体を指し示す名詞句をまとめる問題安倍総理 = 安倍晋三 = 首相 = 彼 A: 親亀がいる B: この亀に子亀が乗っている C: この亀に孫亀がいる文Aの親亀と文Cのこの亀は違うクラスタここで文Bをこの文書から取り除くと 6

7 名詞句のcoreference 文書中の同じ実体を指し示す名詞句をまとめる問題安倍総理 = 安倍晋三 = 首相 = 彼 A: 親亀がいる C: この亀に孫亀が乗っている文Aの親亀と文Cのこの亀は同じクラスタ文書に含まれる名詞句の構成が変化すると指し示す実体は変化する名詞句の coreference は相対クラスタリング問題 7

8 準教師ありクラス分類クラス分類対象が分類されるクラスのラベルを予測準教師ありクラス分類 (ラベルありなし混在データからの学習) ラベルあり事例に加えてラベルなしの事例も用いるとより予測精度の高い分類器が獲得できるラベルなしデータを扱う点でクラスタリングと似ているが次のいずれかの条件を満たさない問題はクラスタリングとするクラス分類問題の条件有限個のラベルの集合が事前に分かっている対象と対応付けたラベルが教師情報 8

9 制約付クラスタリング [Wagstaﬀ 01]のCOP-KMEANS法 mustリンク結ばれたデータの対は同じクラスタに分類される cannotリンク結ばれたデータの対は違うクラスタに分類される制約付と教師ありクラスタリングの相違点制約のあるデータ以外にも制約が一般化されて適用されるなら教師ありクラスタリングそうでないなら制約付クラスタリング COP-KMEANSは制約付クラスタリング 9

10 完全教師ありクラスタリング完全教師ありクラスタリングの訓練事例集合 N 個の対象集合それぞれに教師情報を与える (X1, Y1), (X2, Y2), (XN, YN) Xi 対象集合 Yi Xi についての教師情報任意の Xnew をクラスタリングする関数を求める [神嶌 95] [神嶌 03a] [Daumé III 05] [Finley 05] など教師情報の例 must/cannotリンク Xi のクラスタリング結果同じクラスタになるべき対象の集合データ点の相対的な類似性の大小関係クラスタ間の類似度の最大値クラスタ内類似度の最小値 10

11 準教師ありクラスタリング準教師ありクラスタリング一個の対象集合 X に教師情報 Y を与える (X, Y ) 学習後は X に含まれない未知の事例も分類可能制約のない対象の属性値などは参照しない [Xing 03] [Klein 02] [Bar-Hillel 03] など事例集合 X 任意の対象集合 Xnew クラスタリング関数教師情報 Y 適切な分割 π(xnew) 11

12 transductiveクラスタリング transductiveクラスタリング準教師ありクラスタリングと同じ教師情報の形式 X 中の対象だけを分類することが目的で X に含まれない対象の分類は考慮しない制約教師情報のない対象の属性値位置情報も参照事例集合 X 教師情報 Y [Kulis 05] [Yu 04] [McCallum 05] など事例集合 X 適切な分割 π(x) 12

13 教師ありクラスタリングの分類クラス分類ラベル情報が既知でラベル付けによる教師情報クラスタリングラベル情報が未知制約付クラスタリング制約を使うがその一般化はしない教師ありクラスタリング教師情報は他の対象にも一般化される完全教師ありクラスタリング複数の対象集合に教師情報準教師ありクラスタリング一個の対象集合に教師情報 transductiveクラスタリング新たな対象の分類はしない 13

14 例題の提示方法 (1) 絶対/相対クラスタリングの区別は分割する対象集合が変化する場合にのみ生じる transductiveクラスタリング未知の対象の分類はしない対象集合の変化を考えないtransductiveクラスタリングは無関係相対クラスタリング問題対象のクラスタへの帰属は分類する対象集合に依存教師情報はそれが付加されている対象集合に依存しているので対象集合を一つにまとめたり変えたりすると教師情報は無効完全教師ありクラスタリング複数の対象集合に教師情報相対クラスタリング問題は完全教師ありクラスタリングの枠組みで解かなければならない 14

15 例題の提示方法 (2) 絶対クラスタリング問題対象のクラスタへの帰属は分類する対象集合とは独立対象集合を一つにまとめることで推移性からより多くの教師情報を利用できる X X X! xi must xj must xk X must 準教師ありクラスタリング一個の対象集合に教師情報絶対クラスタリング問題は準教師ありクラスタリングの枠組みで解く 15

16 必要な特徴量絶対クラスタリング問題絶対クラスタが存在対象を絶対クラスタと対応付け各対象を記述する属性があれば十分相対クラスタリング問題対象集合中の他の対象との関連を考慮して対象を分類対象間の関連を示した特徴が必要例名詞句のcoreference問題での名詞句対の属性受けることのできる代名詞か (人をこれで受けるのは不正) 同義語かどうか 16

17 まとめまとめ教師ありクラスタリング手法を整理分類絶対/相対クラスタリングの概念の提案絶対クラスタリング問題は各対象を属性で記述し完全教師ありクラスタリングの枠組みで解く相対クラスタリング問題は各対象に加えて対象の間の関係を記述する属性も必要で準教師ありクラスタリングの枠組みで解く追加情報ホームページおまけ朱鷺の杜Wiki (機械学習について書き込んでください) 17

18 参考文献 A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning distance functions using equivalence relations. ICML2003, pp (2003) H. Daumé III and D. Marcu. A Bayesian model for supervised clustering with the dirichlet process prior. JMLR, Vol.6, pp (2005) T. Finley and T. Joachims. Supervised clustering with support vector machines. ICML2005, pp (2005) 神嶌敏弘, 美濃導彦, 池田克夫, "帰納学習を用いた図面部品の抽出と分類のための規則の形成", 情報処理学会論文誌, vol.36, no.3, pp (1995) T. Kamishima and F. Motoyoshi, "Learning from Cluster Examples", Machine Learning, vol.53, pp (2003) D. Klein, S. D. Kamvar, and C. D. Manning. From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering. ICML2002, pp (2002) B. Kulis, S. Basu, I. Dhillon, and R. Mooney. Semi-supervised graph clustering: A kernel approach. ICML2005, pp (2005) A. McCallum and B. Wellner. Conditional models of identity uncertainty with application to noun coreference. NIPS 17, pp (2005) E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. NIPS 15, pp (2003) S. X. Yu and J. Shi. Segmentation given partial grouping constraints. IEEE Trans. on PAMI, Vol.26, No.2, pp (2004) 18

(Microsoft PowerPoint - \203|\203X\203^\201[\224\255\225\\\227p\216\221\227\ ppt)

$(Microsoft PowerPoint - \203|\203X\203^\201[\224\255\225\\\227p\216\221\227\ ppt)$ Web ページタイプによるクラスタリングを用いた検索支援システム折原大内海彰電気通信大学システム工学専攻はじめに背景文書クラスタリングを用いた検索支援システム Clusty(http://clusty.jp/) KartOO(http://www.kartoo.com/) Carrot(http://www.carrot-search.com/) これらはすべてトピックによる分類を行っている