テキストデータベースからの 構文構造のマイニング

Presentation on theme: "テキストデータベースからの 構文構造のマイニング"— Presentation transcript:

1 テキストデータベースからの 構文構造のマイニング
奈良先端科学技術大学院大学情報科学研究科* 理化学研究所ゲノム科学総合研究センター** 日本 IBM 東京基礎研究所# *工藤　拓 **山本　薫 #坪井祐太 *松本　裕治

2 テキストマイニング 大量のテキスト情報から新奇性のある事実傾向の発見 文書分類，クラスタリング，単語共起の抽出… テキストを単語の
・元のテキストが再現できない ・意味のある構造が捉えられない ・新規性のある事実が抽出できるのか? 太郎は釜山に旅立つ花子に別れを告げた 花子は釜山に旅立つ太郎に別れを告げた 太郎は花子に別れを告げ，釜山に旅立った. 太郎と花子は釜山に別れを告げ，旅立った … 太郎 花子　釜山　 旅立つ　別れ 告げる テキストを単語の 集合として表現　 (Bag of Words)

3 テキストマイニングと自然言語処理 構造化されたテキストからの マイニング 重要! 単語の集合(Bag of Words)
構文解析 90% 構造化されたテキストからの マイニング 重要! 太郎/ は 釜山/に 旅立つ 花子/ に 別れ/ を 告げ/ た/. 太郎/ は /釜山/に /旅立つ/ 花子/ に/ 別れ/ を /告げ/ た/. 固有名詞抽出 85-95% 人名 地名 人名 太郎/ は /釜山/に /旅立つ/ 花子/ に/ 別れ/ を /告げ/ た/. 単語の集合(Bag of Words) を前提とするマイニング 　形態素解析 98% 名詞 助詞 名詞 助詞 動詞 名詞 助詞 名詞　助詞 動詞 助動詞 記号 太郎は釜山に旅立つ花子に別れを告げた． 生テキスト

4 関連研究 松澤00 安部ら01 企業のコールセンターにおけるテキストを対象 用言とそれに係る体言のタプルの集合で表現 Apriori の拡張
順序木の集合から頻出する部分木の抽出 最右拡張 深さ優先探索 映像は悪いが 　　音声は良い (悪い, {映像}) (良い, {音声})

5 概要 自然言語処理を適用した後のテキストデータの多くは木構造で表現される
構造化されたテキストデータのマイニングを「順序木の集合から頻出する部分木を抽出する問題」と定式化 シーケンシャルパターンマイニング手法の１つであるPrefixSpan [Peiら00]　を拡張し，この問題のための効率的手法を提案

6 シーケンシャルパターンマイニング [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 アイテム 系列データベースＳ 系列データベースＳで　 (最小サポート値)　回以上の系列に出現する部分系列を完全に列挙

7 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 結果

8 順序木データベース ラベル付き順序木 順序木データベース: 順序木: 各接点の兄弟間に順序が定義された木
ラベル付き木: 各節点にラベルが付与された木 ラベル: 単語, 文節, HTML XMLのタグなど 順序木データベース: 順序木 id(tid) と順序木 t のタプルの集合 1 d 2 a 3 d 4 d c b c b … a a a c a a c

9 パターンの出現 ある順序木 A が 順序木 B を含む マッチング関数 φが存在 順序木 A 順序木 B e f φは単射
φは親子関係を保持 φは兄弟関係を保持 φはラベルを保存 c d e d c a d c c b c

10 順序木マイニングの定式化 入力 出力 中の各順序木に対し, 回(最小サポート値)以上の順序木に含まれるすべての部分順序木α
順序木データベース: 最小サポート値: 出力 　 中の各順序木に対し, 　回(最小サポート値)以上の順序木に含まれるすべての部分順序木α となるすべての部分木

11 順序木の系列表現への変換 木の右から左に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

12 これらを区別するためのなんらかの情報が必要
基本的アイデア 系列表現を系列とみなしてPrefixSpan を動作させる 2つの木構造の区別ができない これらを区別するためのなんらかの情報が必要 順序木 系列表現 c 抽出されるパターン b a b c a a b c c a b c a b

13 節点間の関係 ψ: 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

14 順序木マイニングアルゴリズム(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

15 順序木マイニングアルゴリズム(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

16 順序木マイニングアルゴリズム(3/3) アイテムを節点名と関係のタプル<i,r>で表現
<i,r1>で射影する場合, <i,r1>の右側にある全アイテム<j,r2>に対し r3=ψ:i→j を算出 射影データベース中のアイテム<j,r2>を<j,r3>に置換 同一アイテムが複数ある場合，すべて射影 頻度(support)は系列単位で算出 <i,ε>のように関係がεのものは数え上げない

17 動作例 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

18 実験 新聞記事 小説 文節単位の依存構造木 京都大学コーパス3.0 約 38,000文 形態素,係り受け解析(構文解析)済み
「我輩は猫である」 約 9,000文 ChaSen,CaboChaを用いて　　　　　形態素，係り受け解析 文節単位の依存構造木 XEON2.2GHz 3.5GB Linux Perlを用いて実装 渡した． * 太郎は 本を 次郎に 持っている 花子が *

19 実験結果～規模耐性 新聞記事，最小サポート=3 アルゴリズムは充分な規模耐性を持つ

20 実験結果～最小サポート値 v.s. 動作時間

21 実験結果～安部らの手法との比較 安部らの順序木マイニング手法 新聞記事に対し，最小サポート値=2で実行半日たっても終了せず
部分木を最右拡張を使い広げていく 幅優先探索 新聞記事に対し，最小サポート値=2で実行半日たっても終了せず 実装や実験環境がことなるため厳密な比較はできないが，最小サポート値が小さいとき本手法は有効と思われる

22 実験結果～抽出された頻出パターン ・新聞記事 ・小説 文として成立するパターンが抽出される 明らかにした 薄れている 述べ 記者会見で
果たしておらず 存在感すら ついて 機能を 文として成立するパターンが抽出される ・小説 する 要する 声が また 我輩は また 休養を いう

23 改良の可能性 非連結部分木の枝狩り 関係値の算出・格納方法 c-0 b-2 c-0 という系列 パターンは非連結部分木となる
非連結部分木を早期に発見し枝狩り 関係値の算出・格納方法 O(n^2) の記憶容量 (nは節点の数) 高効率なアルゴリズムの提案 * c c b

24 まとめ 自然言語処理ツールを利用し，その結果得られた半構造化テキストデータに対するマイニング手法を提案
PrefixSpanを拡張し，深さ優先探索で頻出するパターンを列挙するアルゴリズムを提案 充分な規模耐性 最小サポート値が小さいときに有効

25 今後の課題 人工データ，構文木以外の木を用いた実験 抽出されたパターンの客観的有効性の評価 グラフ構造といった一般的なデータ構造に対する拡張
完全性，健全性の議論