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