テキストデータベースからの構文構造のマイニング奈良先端科学技術大学院大学情報科学研究科* 理化学研究所ゲノム科学総合研究センター** 日本 IBM 東京基礎研究所# *工藤拓 **山本薫 #坪井祐太 *松本裕治テキストマイニング   大量のテキスト情報から新奇性のある事実傾向の発見文書分類，クラスタリング，単語共起の抽出… 太郎花子釜山旅立つ別れ告げるテキストを単語の集合として表現 (Bag of Words) 太郎は釜山に旅立つ花子に別れを告げた花子は釜山に旅立つ太郎に別れを告げた太郎は花子に別れを告げ，釜山に旅立った. 太郎と花子は釜山に別れを告げ，旅立った … ・元のテキストが再現できない・意味のある構造が捉えられない・新規性のある事実が抽出できるのか? テキストマイニングと自然言語処理構文解析 90% 構造化されたテキストからの太郎/ は釜山/に旅立つ花子/ に別れ/ を告げ/ た/. マイニング重要! 太郎/ は /釜山/に /旅立つ/ 花子/ に/ 別れ/ を /告げ/ た/.固有名詞抽出人名地名人名 85-95% 太郎/ は /釜山/に /旅立つ/ 花子/ に/ 別れ/ を /告げ/ た/. 形態素解析 98% (Bag Words) 名詞助詞名詞単語の集合助詞動詞名詞助詞 of 名詞助詞動詞助動詞記号を前提とするマイニング太郎は釜山に旅立つ花子に別れを告げた．生テキスト関連研究  松澤00     企業のコールセンターにおけるテキストを対象用言とそれに係る体言のタプルの集合で表現 Apriori の拡張安部ら01    順序木の集合から頻出する部分木の抽出最右拡張深さ優先探索映像は悪いが音声は良い F1 F2 F3 (悪い, {映像}) (良い, {音声}) F4 概要自然言語処理を適用した後のテキストデータの多くは木構造で表現される  構造化されたテキストデータのマイニングを「順序木の集合から頻出する部分木を抽出する問題」と定式化  シーケンシャルパターンマイニング手法の１つであるPrefixSpan [Peiら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 マイニング結果系列データベースＳで  (最小サポート値) 回以上の系列に出現する部分系列を完全に列挙 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 順序木データベース  ラベル付き順序木順序木: 各接点の兄弟間に順序が定義された木  ラベル付き木: 各節点にラベルが付与された木  ラベル: 単語, 文節, HTML XMLのタグなど   順序木データベース: T  順序木 id(tid) と順序木 t のタプルの集合 T  { tid1, t1 ,  tid2 , t2 ,,  tidn , tn } 1 c a d a 2 b c a 3 c a d a 4 b c d a … パターンの出現 A B ある順序木 A が順序木 B を含む順序木 A 順序木 B e f c d e c c a b d d c c マッチング関数 φが存在     φは単射 φは親子関係を保持 φは兄弟関係を保持 φはラベルを保存順序木マイニングの定式化  入力    順序木データベース: 最小サポート値:  T  { tid1, t1 ,,  tidn , tn } 出力  T 中の各順序木に対し,  回(最小サポート値) 以上の順序木に含まれるすべての部分順序木α supportT () | { tid, t | ( tid, t T )  (  t)}| supportT ( )   となるすべての部分木  順序木の系列表現への変換木の右から左にpre-orderで節点を列挙し，その結果を反転する  木の左隅が系列の prefix に対応  f 順序木 t 系列表現 t’ d e c a a d b acabcdecdf c c 基本的アイデア  系列表現を系列とみなしてPrefixSpan を動作させる 2つの木構造の区別ができない順序木系列表現これらを区別するためのなんらかの情報が必要 c 抽出されるパターン b a b c a a b c c a b a b c 節点間の関係 ψ: i→j 節点 j は節点 iの親: ψ=0  節点 j のk-1(k>0)代目の祖先は,節点iの右側の兄弟: ψ=k fε  それ以外: ψ=ε  e ε0 ε c ε c aε d εε d 01 b 2 c ε1 c 12 b 23 c ε b ε2 e 23 順序木マイニングアルゴリズム (1/3) i から j に射影するとき，ψ:i→j を同時に考慮する順序木 εε0 ε0 e 0 c 0 c 0 a 0 dε01 c 1 1 2 1ε 0 b 2 1 1 cε 2 b 2 ε 2 bε 3 2 eε 3 系列表現 c c a b b e c d b c e 0 2 1 e c c d b 0 0 節点の系列関係のアーク ↓ 部分木を表現 c 順序木マイニングアルゴリズム (2/3) c c a b b e c d b c e e c a d c b c b c b e 初期化 0 2 1 0 0 アイテムを節点名-関係ψ (タプル) で表現 c-0 c-0 a-0 b-0 b-0 e-0 c-0 d-0 b-0 c-0 e-0 a-εb-εb-εe-εc-εd-εb-εc-εe-ε c-0 a-0 b-0 b-0 e-0 c-0 d-0 b-0 c-0 e-0 a-εb-εb-εe-εc-εd-εb-εc-εe-ε a-1 b-2 b-3 e-3 c-2 d-1 b-2 c-1 e-0 b-2 b-3 e-2 e-3 c-1 c-2 d-0 d-1 b-εc-εe-ε b-2 c-1 e-0 d-0 b-εc-εe-ε c-0 c-0 b-2 c-1 d-0 e-0 順序木マイニングアルゴリズム (3/3)        アイテムを節点名と関係のタプル<i,r>で表現まず，全アイテムを<i,0>に初期化 <i,r1>で射影する場合, <i,r1>の右側にある全アイテム<j,r2>に対し r3=ψ:i→j を算出射影データベース中のアイテム<j,r2>を<j,r3> に置換同一アイテムが複数ある場合，すべて射影頻度(support)は系列単位で算出 <i,ε>のように関係がεのものは数え上げない動作例 1 c d a 2 b a c 4 c a 3 b a c b 系列 1 2 3 4 a-0 c-0 d-0 a-0 b-0 c-0 c-0 b-0 a-0 b-0 a-0 c-0 a-0:4 b-0:3 c-0:3 d-0:1 最小サポート値=2 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 a-0 : 4 a-0 c-0 :3 b-0 :3 b-0 a-0 :2 c-0 :3 c a abc a b 実験  新聞記事    京都大学コーパス3.0 約 38,000文形態素,係り受け解析(構文解析)済み小説「我輩は猫である」約 9,000文渡した． *  ChaSen,CaboChaを用いて形態素，係り受け解析太郎は本を次郎に  文節単位の依存構造木  XEON2.2GHz 3.5GB Linux 持っている Perlを用いて実装花子が * http://chasen.org/  実験結果～規模耐性新聞記事，最小サポート=3 35 実行時間(秒) 30 25 アルゴリズムは充分な規模耐性を持つ 20 15 10 5 0 0 10000 20000 文数 30000 40000 実験結果～最小サポート値 v.s. 動作時間新聞記事小説 500 8 450 7 400 6 実行時間(秒) 実行時間(秒) 350 300 250 200 150 5 4 3 2 100 50 1 0 0 0 5 10 最小サポート 15 20 0 5 10 最小サポート 15 20 実験結果～安部らの手法との比較  安部らの順序木マイニング手法部分木を最右拡張を使い広げていく  幅優先探索  新聞記事に対し，最小サポート値=2で実行半日たっても終了せず  実装や実験環境がことなるため厳密な比較はできないが，最小サポート値が小さいとき本手法は有効と思われる  実験結果～抽出された頻出パターン・新聞記事明らかにした述べ記者会見でついて薄れている果たしておらず存在感すら機能を文として成立するパターンが抽出される・小説する要する我輩はまた休養を声がいうまた改良の可能性  非連結部分木の枝狩り * c c-0 b-2 c-0 という系列パターンは非連結部分木となる  非連結部分木を早期に発見し枝狩り   関係値の算出・格納方法 O(n^2) の記憶容量 (nは節点の数)  高効率なアルゴリズムの提案  c b まとめ自然言語処理ツールを利用し，その結果得られた半構造化テキストデータに対するマイニング手法を提案  PrefixSpanを拡張し，深さ優先探索で頻出するパターンを列挙するアルゴリズムを提案  充分な規模耐性  最小サポート値が小さいときに有効  今後の課題人工データ，構文木以外の木を用いた実験  抽出されたパターンの客観的有効性の評価  グラフ構造といった一般的なデータ構造に対する拡張  完全性，健全性の議論 