言語情報を利用したテキストマイニング奈良先端科学技術大学院大学情報科学研究科工藤拓山本薫坪井裕太松本裕治データマイニング     膨大なデータから有益，興味のある，思いがけないデータを明示的な知識として発見膨大なデータから頻出する部分パターンの発見膨大なデータに対してスケーラブルである必要性バスケット分析 – 顧客の購買分析（ソーセージを買う人はロールパンを買いやすい）テキストマイニング(1/2)   文書分類，クラスタリング，単語共起の抽出これまでのテキストマイニングの多くは… 映像は良いが音声は悪い映像良い音声悪いテキストを単語の集合として表現 (Bag of Words) ？映像は悪いが音声は良いテキストが持つ意味のある構造が捉えられないテキストマイニング(2/2)  松澤00 – – – 企業のコールセンターにおけるテキストを対象単語間の係り受け関係を考慮したマイニング手法用言とそれに係る体言のタプルの集合で表現映像は悪いが音声は良い (悪い, {映像}) (良い, {音声}) 目標テキスト形態素解析単語同定単語の集合マイニングアルゴリズム知識 (頻出する単語の共起) 形態素解析単語同定チャンキング係り受け解析構造化されたテキストマイニングアルゴリズム詳細化された知識 (頻出する部分構造) シーケンシャルパターンマイニング(Agrawal94) sid 1 2 3 4 系列 a a c a c b b a d c a b 系列データベースＳ最小サポート値 = 2 アイテム a:4 b:3 c:3 a b:2 a c:2 マイニング結果 系列データベースＳで  (最小サポート値) 回以上の系列に出現する部分系列を完全に列挙 自然言語処理: アイテムを単語，系列を文，テキスト中の  回以上の文に出現する単語の列を列挙マイニングの手法  幅優先 (Apriori) – –  候補生成-テストデーターベースを何回も捜査する必要がある深さ優先 (FP-Tree, PrefixSpan) – – 分割統治法並列性，メモリの使用量が少ない PrefixSpan (Peiら 00) 系列 1 2 3 4 a a c a c b b a d c a b 射影 a:4 b:3 c:3 d:1 最小サポート値=2 a:4 a b:2 a c:2 b:2 c:3 結果 1 2 4 c d b c a b a:1 b:2 c:2 2 3 c a a:1 c:1 1 3 d ba a:1 b:1 d:1 2 c c:1 1 d d:1 集合を単位とするPrefixSpan (Peiら 00) アイテムの集合を考慮 単語（単語,品詞,活用) 等 同じ集合のアイテムに _ を付与して射影系列 1 2 3 4 a(abc)(ac)d(cf) (ad)c(bc)(ae) (ef)(ab)(df)b e(af)c 系列射影 a:4 b:3 c:3 d:1 1 2 3 4 (abc)(ac)d(cf) (_d)c(bc)(ae) a a:2 aa (_b)(df)cb a _b c:2 (a b)c (_f)cbc …. PrefixSpan の拡張(1/2) a 射影? 射影の制約 隣接するアイテムのみ射影（N-gram) 係り関係のみ 言語制約（機能語の連続は考慮しない 頻度以外の制約の導入 b b-r1 b-r2 b-r3 a b は r1 の関係 a b は r2 の関係 a b は r3 の関係射影の詳細化  a b が構造的に関係 r を持つ  b で射影せず， b-r (アイテム名-関係名で射影) PrefixSpan の拡張(3/3) 関係関数 Relation(S , sid , i, j ) S 中の系列 sid の i番目と j番目のアイテムの関係を返す (アイテム)＋(関係関数の返り値) で射影 返り値がεの場合は射影を行わないと定義 関係関数の実装により半構造化データ，言語的制約を表現 具体例 (集合,N-Gram,チャンク,係り受け) 集合, N-gram  集合 –  2つのアイテムが同一集合内だと IN, 異なる集合の場合は OUT を返す N-gram – ２つのアイテムが連続するときに定数，それ以外はεを返すチャンクチャンク名 A X { { { アイテム名 a b c P pqr xyz <a b c A p q r P x y z X> チャンク名を擬似的なアイテムとして追加 アイテムのタイプ  NT→チャンク名のアイテム(A,P,X)  T→通常のアイテム(a,b,c,p,q,r,z,y,z) 異なるチャンク間のT→Tの射影は許可しない係り受け(1/2)    日本語は比較的語順が自由係り受けを考慮することで，意味的に同一で語順の異なる文を同一視係り関係木の正規化 f f e e d c a b a d b c 係り受け(2/2)   係り先からみて k(k>=0)代目の子孫であるとき関係名を k と定義, それ以外はε 係り受け木→系列 fε a e0 a c d e ((a ((b c) d) e) f) d 1 b 2 b c 2 f 係り受け(3/3) 系列 1 2 3 4 ((a c) d)) (a (b c)) ((c b) a) ((b a) c) a:4 b:3 c:3 d:1 最小サポート値=2 a:4 a c-0 :3 b:3 b a-0 :2 c:3 1 2 4 c-0 d-ε b-1 c-0 c-0 b-1:1 c-0:3 2 3 4 c-0 a-0 a-0 c-ε a-0:2 c-0:1 1 結果 3 d-0 b-0 a-ε b-0:1 d-0:1 1 d-0 d-0:1 1 c-0 c-0:1 実験   新聞記事 (京都大学コーパス3.0 約38,000文) 小説 (「我輩は猫である」約 9,000文) –  ChaSen,CaboChaを用いて形態素，係り受け解析構造 – – N-gram (アイテムは単語) チャンク (アイテムは文節)   – すべての文節をチャンク名，アイテムはチャンク名に係る文節チャンク名，チャンクの中身は辞書式にソート係り受け (アイテムは文節) 実験結果(1/2) 最小サポート抽出時間秒（新聞 / 小説) N-gram チャンク係り受け 2 2.2 / 0.46 N/A / 0.74 355.6 / 7.8 5 2.0 / 0.43 3.2 / 0.60 26.7 / 5.8 10 1.9 / 0.41 3.0 / 0.57 24.0 / 5.2 15 1.9 / 0.41 2.8 / 0.55 22.9 / 4.8 20 1.9 / 0.41 2.9 / 0.55 22.1 / 4.6 実験結果(2/2)  N-gram – –  チャンク – –  ロシア南部チェチェン共和国の首都グロズヌイこれが鈴木君の心の平均を破る第（震度は，{各地の}), (通り, {次の，震度は}) （ないから， {我輩は,仕方が}) 係り受け – – ((ついて述べ,) (記者会見で明らかにした)) (休養を (また (我輩は要する))) 応用例1: 機械学習の素性抽出 +1 -1 +1 +1 -1 .. ((a b) (c d)) (c (b (e f))) (a (c (d e))) ((a c)(d e)) (c (a (b e))) 半構造化データに対し，クラスラベル(+1,-1)が付与 半構造化データの部分パターンを素性として選択 単純にクラスとデータを連結 クラスラベルと部分パターンの共起度（相互情報量，dice係数)の高いパターンを素性として選択応用例2: 対訳パターン抽出(1/2) 日本語単純に連結 J1 J2 J3 ….. Jn 単言語間はその言語の構造で規定される関係関数英語 E1 E2 E3 ….. Em 二言語間はすべての射影を許可 共起する構造化パターンの抽出 Dice 係数,相互情報量等で順位付け応用例2: 対訳パターン抽出(2/2)  実験 – –   系列 52分, N-gram 7秒で全候補パターンを生成系列にて発見されたパターン – – –  日英対訳コーパス 9268文構造: 系列, N-gram (機能語相当は考慮しない) earliest convenience 都合つき次第 let …..know お知らせ thank ….letter 手紙ありがとう連続しない単語の翻訳パターンが抽出まとめ    自然言語処理ツールを利用し，その結果得られた半構造化テキストデータに対するマイニング手法を提案 PrefixSpanに対し，「関係関数」を導入, 種々の言語的な情報を反映した半構造化データに対するマイニング手法の提案機械学習の素性選択，対訳パターンの抽出に利用できる可能性を提示今後の課題     抽出されたパターンの客観的有効性の評価対象とする構造，関係関数の違いにより，具体的な応用でどういった差があるか評価木構造，グラフ構造といった一般的なデータ構造に対する関係関数の記述方法完全性，健全性の議論ご静聴ありがとうございました PrefixSpanの C++ による実装は http://cl.aist-nara.ac.jp/~taku-ku/software/prefixspan/ にて入手可能ですチャンク(2/3) 友達と京都に行って，ラーメンを食べた行く食べる { { {友達, 京都} {ラーメン} それぞれ辞書式にソート実験結果最小サポート抽出パターン数（新聞 / 小説) N-gram チャンク係り受け 2 320428/65803 N/A / NA 1028534/10253 5 62226/14736 7490 / 1310 10478/2217 10 26095/6031 2538 / 470 4149/919 15 16109/3866 21389 / 282 2433/554 20 11430/2781 849 / 195 1622/376