言語情報を利用したテキストマイニング奈良先端科学技術大学院大学情報科学研究科工藤拓山本薫坪井裕太松本裕治本発表の目標 構文解析された文の集合から頻出する部分木を抽出 部分木のサイズに制限を設けない 巨大なコーパスに対し，高効率,スケーラブルである必要 a a b c d c d a d c a a a d c a b a c c 構文木の集合 d b a c c d 頻出する部分木の抽出 (頻度2回以上) テキストマイニング(1/2)   文書分類，クラスタリング，単語共起の抽出これまでのテキストマイニングの多くは… 映像は良いが音声は悪い映像良い音声悪いテキストを単語の集合として表現 (Bag of Words) ？映像は悪いが音声は良いテキストが持つ意味のある構造が捉えられない半構造テキストマイニングテキスト形態素解析単語同定単語の集合マイニングアルゴリズム知識 (頻出する単語の共起) 形態素解析単語同定チャンキング係り受け解析構文解析済みテキストマイニングアルゴリズム構造化された知識 (頻出する部分構文木) シーケンシャルパターンマイニング(Agrawalら94) 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 マイニング結果 系列データベースＳで  (最小サポート値) 回以上の系列に出現する部分系列を完全に列挙 自然言語処理: アイテムを単語，系列を文，テキスト中の  回以上の文に出現する単語の列を列挙 PrefixSpan (Peiら 00) sid 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 の拡張(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) 関係関数系列 sid 1 2 3 4 a b b b c a c a d a c b rel  Relation(S, sid, i, j) b a c d S S 中の系列 sid の i番目と j番目のアイテムの関係(rel)を返す アイテム-関係関数の返り値(rel) で射影 返り値がεの場合は射影を行わないと定義 関係関数の実装により半構造化データ，言語的制約を表現 具体例 (N-Gram,チャンク,係り受け) 係り受け(1/2)    日本語は比較的語順が自由係り受けを考慮することで，意味的に同一で語順の異なる文を同一視係り関係木の正規化 f f e e d c a b a d b c 係り受け(2/2)   係り元(i)の係り先(j)からみて k(k>=0)代目の子孫であるとき(i,j)の関係名を k と定義, それ以外はε 係り受け木→系列 fε e0 a i a d 1 b 2 b c d e ((a (b (c d)) e) f) 2 2 1 0 ε c 2 f 係り受け(3/3) 系列 1 2 3 4 ((a c) d)) 0 ε (a (b c)) 1 0 ((c b) a) ((b a) c) 0 a:4 b:3 c:4 d:1 最小サポート値=2 a:4 a c-0 :3 b:3 b a-0 :2 c:4 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を用いて形態素，係り受け解析構造 – 文節をアイテムとする係り受け構造実験結果最小サポート値 2 5 10 15 20 抽出時間 (sec.) 新聞/小説 355.6 / 7.8 26.7 / 5.8 24.0 / 5.2 22.9 / 4.8 22.1 / 4.6 ((ついて述べ,) (記者会見で明らかにした)) ((各地の震度は) (次の通り)) (ことが (調べで分かった)) (休養を (また (我輩は要する))) 新聞記事に頻出する定型表現が抽出できた応用例: 対訳パターン抽出日本語単純に連結 J1 J2 J3 ….. Jn 単言語間はその言語の構造で規定される関係関数英語 E1 E2 E3 ….. Em 二言語間はすべての射影を許可 共起する構造化パターンの抽出 Dice 係数,相互情報量等で順位付けまとめ    自然言語処理ツールを利用し，その結果得られた半構造化テキストデータに対するマイニング手法を提案 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 データマイニング     膨大なデータから有益，興味のある，思いがけないデータを明示的な知識として発見膨大なデータから頻出する部分パターンの発見膨大なデータに対してスケーラブルである必要性バスケット分析 – 顧客の購買分析（ソーセージを買う人はロールパンを買いやすい）応用例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係数)の高いパターンを素性として選択マイニングの手法  幅優先 (Apriori) – –  候補生成-テストデーターベースを何回も捜査する必要がある深さ優先 (FP-Tree, PrefixSpan) – – 分割統治法並列性，メモリの使用量が少ない応用例: 対訳パターン抽出(2/2)  実験 – –   系列 52分, N-gram 7秒で全候補パターンを生成系列にて発見されたパターン – – –  日英対訳コーパス 9268文構造: 系列, N-gram (機能語相当は考慮しない) earliest convenience 都合つき次第 let …..know お知らせ thank ….letter 手紙ありがとう連続しない単語の翻訳パターンが抽出