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

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

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

テキストマイニング (2/2) 松澤 00 – 企業のコールセンターにおけるテキストを対象 – 単語間の係り受け関係を考慮したマイニング手法 – 用言とそれに係る体言のタプルの集合で表現 映像は悪いが 音声は良い ( 悪い, { 映像 }) ( 良い, { 音声 })

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

シーケンシャルパターンマイニング (Agrawal94) 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 マイニング結果 系列データベースＳで ( 最小サポート値 ) 回以上の 系列 に出現する部分系列を完全に列挙 自然言語処理 : アイテムを単語，系列を文，テキスト 中の 回以上の文に出現する単語の列を列挙 アイテム

マイニングの手法 幅優先 (Apriori) – 候補生成 - テスト – データーベースを何回も捜査する必要がある 深さ優先 (FP-Tree, PrefixSpan) – 分割統治法 – 並列性，メモリの使用量が少ない

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

集合を単位とする PrefixSpan (Pei ら 00) 系列 a(abc)(ac)d(cf) (ad)c(bc)(ae) (ef)(ab)(df)b e(af)c a:4 b:3 c:3 d:1 a a:2 a a a _b c:2 (a b)c …. 系列 (abc)(ac)d(cf) (_d)c(bc)(ae) (_b)(df)cb (_f)cbc アイテムの集合を考慮 単語 （単語, 品詞, 活用 ) 等 同じ集合のアイテムに _ を付与して射影 射影

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 番目のアイテムの関係を返す ( アイテム ) ＋ ( 関係関数の返り値 ) で射影 返り値が ε の場合は射影を行わないと定義 関係関数の実装により半構造化データ，言語的制約を表 現 具体例 ( 集合,N-Gram, チャンク, 係り受け )

集合, N-gram 集合 – 2 つのアイテムが同一集合内だと IN, 異なる集合の 場合は OUT を返す N-gram – ２つのアイテムが連続するときに定数，それ以外は ε を返す

チャンク a b c p q r x y z チャンク名を擬似的なアイテムとして追加 アイテムのタイプ NT→ チャンク名のアイテム (A,P,X) T→ 通常のアイテム (a,b,c,p,q,r,z,y,z) 異なるチャンク間の T→T の射影は許可しない APX {{{ チャンク名 アイテム名

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

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

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

実験 新聞記事 ( 京都大学コーパス 3.0 約 38,000 文 ) 小説 ( 「我輩は猫である」 約 9,000 文 ) – ChaSen,CaboCha を用いて形態素，係り受け解析 構造 – N-gram ( アイテムは単語 ) – チャンク ( アイテムは文節 ) すべての文節をチャンク名，アイテムはチャンク名に係る 文節 チャンク名，チャンクの中身は辞書式にソート – 係り受け ( アイテムは文節 )

実験結果 (1/2) 最小サ ポート 抽出時間 秒 （新聞 / 小説 ) N-gram チャンク係り受け 22.2 / 0.46N/A / / / / / / / / / / / / / / 4.6

実験結果 (2/2) N-gram – ロシア 南部 チェチェン 共和国 の 首都 グロ ズヌイ – これ が 鈴木 君 の 心 の 平均 を 破る 第 チャンク – （震度は， { 各地の }), ( 通り, { 次の，震度は }) – （ないから， { 我輩は, 仕方が }) 係り受け – (( ついて 述べ,) ( 記者会見で 明らかにした )) – ( 休養を ( また ( 我輩は 要する )))

応用例 1: 機械学習の素性抽出 ((a b) (c d)) (c (b (e f))) (a (c (d e))) ((a c)(d e)) (c (a (b e))) 半構造化データに対し，クラス ラベル (+1,-1) が付与 半構造化データの部分パターン を 素性として選択 単純にクラスとデータを連結 クラスラベルと部分パターンの 共起度（相互情報量， dice 係数 ) の 高いパターンを素性として選択

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

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

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

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

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

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

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