言語情報を利用したテキストマイニ ング 奈良先端科学技術大学院大学 情報科学研究科 工藤 拓 山本 薫 坪井 裕太 松本 裕治

本発表の目標 構文解析された文の集合から頻出する部分木を抽出 部分木のサイズに制限を設けない 巨大なコーパスに対し，高効率, スケーラブルである必要 a c a d a b c d d a b c c a c d 構文木の集合 a c a c d a b c a d 頻出する部分木の抽出 ( 頻度 2 回以上 )

テキストマイニング (1/2) 文書分類，クラスタリング，単語共起の抽出 これまでのテキストマイニングの多くは … 映像 良い 音声 悪い テキストを単語の 集合として表現 (Bag of Words) 映像は良いが 音声は悪い 映像は悪いが 音声は良い ？ テキストが持つ意味のある構造 が捉えられない

半構造テキストマイニング テキス ト 形態素解析 単語同定 単語の集合 マイニング アルゴリズム 知識 ( 頻出する単語の共起 ) マイニング アルゴリズム 形態素解析 単語同定 チャンキング 係り受け解析 構文解析済みテキスト 構造化された知識 ( 頻出する部分構文木 )

シーケンシャルパターンマイニング (Agrawal ら 94) sid 系列 a c d a b c c b a a a b 最小サポート値 = 2 系列データベースＳ a:4 b:3 c:3 a b:2 a c:2 マイニング結果 系列データベースＳで ( 最小サポート値 ) 回以上の 系列 に出現する部分系列を完全に列挙 自然言語処理 : アイテムを単語，系列を文，テキスト 中の 回以上の文に出現する単語の列を列挙 アイテム

PrefixSpan (Pei ら 00) 系列 a c d a b c c b a a a b a:4 b:3 c:3 d:1 射影 c d b c a b a:1 b:2 c:2 2 c c:1 1 d d:1 2 3 c a a:1 c:1 1 3 d b a a:1 b:1 d:1 a:4 a b:2 a c:2 b:2 c:3 結果 最小サポート値 =2 sid

PrefixSpan の拡張 (1/2) ab 射影 ? 射影の制約 隣接するアイテムのみ 射影（ N-gram) 係り関係のみ 言語制約（機能語の連 続は考慮しない 頻度以外の制約の導入 射影の詳細化 a b が構造的に 関係 r を 持つ b で 射影せず， b-r ( ア イテム名 - 関係名で射影 ) b-r1 b-r2 b-r3 a b は r1 の関係 a b は r2 の関係 a b は r3 の関係

PrefixSpan の拡張 (3/3) 関係関数 S 中の 系列 sid の i 番目と j 番目のアイテムの関係 (rel) を返 す アイテム - 関係関数の返り値 (rel) で射影 返り値が ε の場合は射影を行わないと定義 関係関数の実装により半構造化データ，言語的制約を表現 具体例 (N-Gram, チャンク, 係り受け ) a c d a b a c b b c b a b a c d S sid 系列

係り受け (1/2) 日本語は比較的語順が自由 係り受けを考慮することで，意味的に同一で語 順の異なる文を同一視 係り関係木の正規化 f e a d b c f e d c b a

係り受け (2/2) 係り元 (i) の係り先 (j) からみて k(k>=0) 代目の子 孫であるとき (i,j) の関係名を k と定義, それ以外 は ε 係り受け木 → 系列 f e a d b c 0 ε 1 22 a b c d e f ((a (b (c d)) e) f) ε i

係り受け (3/3) 系列 ((a c) d)) (a (b c)) ((c b) a) ((b a) c) a:4 b:3 c:4 d:1 b-1:1 c-0:3 1 3 d-0 b-0 a-ε b-0:1 d-0:1 a:4 a c-0 :3 b:3 b a-0 :2 c:4 結果 c-0 a-0 a-0:2 c-0:1 a-0 c-ε 1 d-0 d-0:1 1 c-0 c-0:1 最小サポート値 = c-0 d-ε b-1 c-0 c-0 0 ε 1 0 0

実験 新聞記事 ( 京都大学コーパス 3.0 約 38,000 文 ) 小説 ( 「我輩は猫である」 全文 約 9,000 文 ) – ChaSen,CaboCha を用いて形態素，係り受け解析 構造 – 文節をアイテムとする係り受け構造

実験結果 最小サポート値抽出時間 (sec.) 新聞 / 小説 / / / / / (( ついて 述べ,) ( 記者会見で 明らかにした )) (( 各地の 震度は ) ( 次の 通り )) ( ことが ( 調べで 分かった )) ( 休養を ( また ( 我輩は 要する ))) 新聞記事に頻出する定型表現が抽出でき た

応用例 : 対訳パターン抽出 日本語 英語 J1 J2 J3 ….. Jn E1 E2 E3 ….. Em 単純に連結 単言語間は その言語の構造で 規定される関係関数 二言語間は すべての射影を許可 共起する構造化パターンの抽出 Dice 係数, 相互情報量等で順位付け

まとめ 自然言語処理ツールを利用し，その結果得られ た半構造化テキストデータに対するマイニング 手法を提案 PrefixSpan に対し，「関係関数」を導入, 種々 の言語的な情報を反映した半構造化データに対 するマイニング手法の提案 対訳パターンの抽出に利用できる可能性を提示

今後の課題 抽出されたパターンの客観的有効性の評価 対象とする構造，関係関数の違いにより，具体 的な応用でどういった差があるか評価 グラフ構造に対する関係関数の記述方法 完全性，健全性の議論

ご静聴ありがとうございました PrefixSpan の C++ による実装は にて入手可能です

チャンク (2/3) 友達と京都に行って，ラーメンを食べた 行く { 友達, 京都 } { 食べる { ラーメン } { それぞれ 辞書式に ソート

実験結果 最小サ ポート 抽出パターン数 （新聞 / 小説 ) N-gram チャンク係り受け /65803N/A / NA / / / / / / / / / / / / /376

データマイニング 膨大なデータから有益，興味のある，思いがけ ないデータを明示的な知識として発見 膨大なデータから頻出する部分パターンの発見 膨大なデータに対してスケーラブルである必要 性 バスケット分析 – 顧客の購買分析 （ ソーセージを買う人はロールパンを買いやすい）

応用例 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) 実験 – 日英対訳コーパス 9268 文 – 構造 : 系列, N-gram ( 機能語相当は考慮しない ) 系列 52 分, N-gram 7 秒で全候補パターンを生 成 系列にて発見されたパターン – earliest convenience 都合 つき 次第 – let …..know お知らせ – thank ….letter 手紙 ありがとう 連続しない単語の翻訳パターンが抽出