言語情報を利用したテキストマイニング
工藤 拓

山本 薫

坪井 祐太

松本 裕治

奈良先端科学技術大学院大学情報科学研究科{taku-ku,kaoru-ya,yuuta-t,matsu}@is.aist-nara.ac.jp1

はじめにい, α v β と表記する. 系列データベース S とは , 系
列 id sid と系列 s のタプル hsid, si の集合である. さらに , 系列 α の系列データベース S におけるサポート
supportS (α) とは , S 中のすべての系列のうち, 系列 αを含むタプルの数と定義される.
シーケンシャルパターンマイニングとは , 系列データ
ベース S と 任意の整数 (最小サポート 値 (minimumsupport) ξ) に対し , supportS (α) ≥ ξ となるような系
列 α を全て列挙するタスクの事を指す.

データマイニングとは , 膨大なデータの中から有用,あるいは興味のあるパターンを明示的な知識として発掘する方法についての科学的研究である.
その対象をテキストデータとしたテキストマイニン
グの分野は , 決して目新しいものではない. 例えば , 語と語の共起関係や相関関係を調べたり, 語のクラスタリングといった処理は , 古くから研究されてきている. これらの研究の多くは , 形態素解析といった比較的「浅い」
言語処理技術のみを利用し , テキスト全体を単語の「集3 PrefixSpan合」とみなして処理を行っている. しかし , このような
Pei[2] らは , シーケンシャルパターンマイニングに対データ構造は , 機械処理に向いているといはいえ , 各単語のテキスト中の役割, 単語間の係り受け関係などを考 する効率的な手法 PrefixSpan を提案している.
PrefixSpan を説明する前に , そのアルゴ リズムの慮に入れないため, 文がもつ本当に意味のある構造をう核となる射影という操作を説明する. ある系列 s =まくとらえらないという問題がある.
その一方で , Text Chunking, 係り受け解析 (構文解 ha1 , a2 , . . . am i, ア イテム a に対し , a1 6= a, a2 6=析), 固有名詞抽出といった高度な自然言語処理ツール a, . . . , aj−1 6= a, aj = a となるような整数 j(1 ≤が近年利用できるようになってきた . これらのツール j ≤ m) が 存在する場合, 系列 ha1 , a2 , . . . aj i を s
により, テキスト中の単語の役割がより明確になり, テ の a に対する prefix (pref ix(s, a)) と定義する. まキストの具体的な内容をよりよく反映したデータ構造 た, 系列 haj+1 , . . . , am i を s の a に対する postfixに変換することができる. しかし , 自然言語処理ツール (postf ix(s, a)) と定義する. もし j が存在しない場合を利用することで , 生のテキストは , ある構造を持った は , prefix,postfix は未定義 (ε) となる. ある系列データデータ (半構造テキストデータ) に変換される. 複雑な ベース S に対し , アイテム a によって 射影 (project)データ構造になればなるほど , 単純に単語の集合を前提 し , 射影データベース S|a を作成するとは , S 中のそれとしていたようなアプローチは有効に機能しなくなっ ぞれ系列 s に対し , postf ix(s, a) を作成し , それらを改てくる. 今後, このような半構造化されたテキストデー めて系列データベースとする操作と定義される.
図 1 に , ξ = 2 とした場合の PrefixSpan の動作過程
タからいかに有用なパターンを発見するかが大きな課を示す. まず , アイテム数 1 の多頻度系列 a, b, c を抽出題となってくるであろう.
本稿では , このような流れを受け , 種々の自然言語処 する. d は , サポートが 1 であるため, 多頻度系列では理ツールの結果から得られた半構造化されたテキスト ない. 多頻度系列は , これら 3 種類あるが , そのうち aデータに対するマイニング手法提案する. 具体的には , について考え , S の a による 射影データベース S|a を
まず , 半構造テキスマイニングを与えられた半構造テキ 作成する (図 1 中央上). この データベースから , 多頻度ストデータから頻出する部分構造を発見する問題と定 系列 b, c を生成する. 以下再帰的にこれらの作業を繰式化する. さらに , シーケンシャルパターンのマイニン り返すことで , すべての多頻度系列を抽出することがでグ手法である PrefixSpan アルゴリズム [2] を拡張し , こ きる. PrefixSpan の擬似コード を 図 3 に示す. 実際には , 系列データベース S が , メモリに納まる場合は , 系の問題を効率よく解決するアルゴ リズムを提案する.
列へのポインタと postfix の先頭位置を使って射影 (擬2 シーケンシャルパターンマイニング 似射影) を行う.

Agrawal[1] らは , シーケンシャルパターンマイニン
グを以下のように定式化している 1 .
I = {i1 , i2 , . . . in } を , アイテム 集合とする. 系列 とは , アイテムの列であり, hs1 , s2 , . . . , sn i, と表記する.
sk は任意のアイテムである. ある系列 α 中のすべてのアイテムが , 別の系列 β の中にに存在し , その順番が保持されている場合, 系列 β は系列 α を「含む」と言

3.1

集合を単位とする PrefixSpan

部分的に集合を考慮するような系列データベースに対しても, PrefixSpan は適用可能である. 具体的には ,まず , エレ メント という単位を導入する. エレ メントは , アイテムの集合である. エレ メント中のアイテムは集合となるため, それらの順番は考慮せず , あらかじめ
辞書順にソートしておく. 図 2 にエレ メントが含まれ
1 この定式化は , エレ メントという単位が無いため厳密ではない. る系列データベースの例を示す. ’()’ で囲まれるアイテ
エレ メントについては , 次節で扱う
ムがエレ メントである.

1
24minsup = 2
project

sid sequence
1acd
2
abc
3
cba
4
aabc db ca ba:1
b:2
c:2

projected
database

a:4
b:3
c:3
d:1

23caa:1
c:1

13db aa:1
b:1
d:1

sequence databasecount sup. of 1 item

2

c c:1

S = {hsid1 , s1 i, hsid2 , s2 i, . . . , hsidn , sn i}
P = {hsid1 , −1i, hsid2 , −1i, . . . , hsidn , −1i}function Relation(S, sid, i, j)

1d d:1

call P ref ixSpan(ε, P )

a:4
b:2
c:2
a b:2
a c:2
results

図 1: PrefixSpan の動作過程

minsup = 2

sidsequence1234a(abc)(ac)d(cf)(ad)c(bc)(ae)(ef)(ab)(df)cb
e(af)cbc

sequence databaseproject

a:4
b:4
c:4
d:2
...

1
2
3
4(abc)(ac)d(cf)(_d)c(bc)(ae)(_b)(df)cb(_f)cbc_d,_b,_f
item  

aa :2(a) (a)a _b c : 2 (a b) (c)...
results

図 2: PrefixSpan + エレ メント
call P ref ixSpan(ε, S)
procedure P ref ixSpan (α, S|α )begin
B ← {b|(s ∈ S|α , b ∈ s) ∧ (supportS |α (hbi) ≥ ξ)}

procedure P ref ixSpan (α, P |α)begin# B は , タプルをキー,# タプルの集合を値とするマップ
foreach hsid, li ∈ P |α
begin
# C は , タプル の集合
C ← {}
foreach i ← l + 1 to |seq(S, sid)|
beginb ← item(S, sid, i)r ← Relation(S, sid, l, i)if (r 6= ε and C ∈/ hb, ri)
B[hb, ri] ← B[hb, ri] ∪ hsid, ii
C ← C ∪ hb, ri
end
end
foreach hb, ri ∈ keys of B
begin
# ξ 未満のものは考慮しない
if (|B[hb, ri]| < ξ) continue# パターンとその頻度を出力
print α hb, ri, |B[hb, ri]|call P ref ixSpan (αhb, ri, B[hb, ri])endend

図 4: 拡張 PrefixSpan の擬似コード

この関係関数を用い, PrefixSpan の擬似コード (擬似射影版) を , 図 4 のように改める. ただし , S 中の sid kforeach b ∈ Bに対応する系列を seq(S, k) と表記し , seq(S, k) の 先begin# パターンとその頻度を出力
頭から i 番目 のアイテムを ,item(S, k, i) と表記する.
print αb, supportS |α (hbi)
通常の PrefixSpan では , 各アイテムが射影の対象とな# 射影データベースの作成
るが, 拡張後は , 関係関数が返す値とアイテムのタプル(S|α)|b ← {hsid, s0 i|(hsid, si ∈ S|α)が射影の対象となる. また, 関係関数が ε を返す場合∧ (s0 = postf ix(s, b)) ∧ (s0 6= ε)}は , それ以上の射影を行わないと定義する.
call P ref ixSpan (αb, (S|α )|b )end
関係関数は , それぞれの目的に従って設計されるが ,end
個々のデータ構造に対し , 関係関数をいかなる方法で一般的な形で与えるかが大きな問題となる. 与えられた任図 3: PrefixSpan の擬似コード
意の構造に対し一般的な形で関係関数を与える事は , 今後の課題とし , 本稿では , 自然言語で頻繁に使用される
図 2 を例に , 実際の PrefixSpan の動作過程を説明す データ構造のうち, エレ メント , N-gram, チャンク, そる. まず , アイテム数 1 の多頻度系列 a, b, c, d, e, f が抽 して係り受け関係に対する具体的な関係関数の実装方出される. 次に , 前節と同様にアイテム a の 射影デー 法についての議論を行う.
タベースを作成する. その際, a と同じエレ メントにあるアイテムに対し , ’ ’ という prefix を付け , 別のアイ 4.2 エレ メントテムに変換し , 射影データベースを作成する. 同一エレ集合を単位とする PrefixSpan の拡張は , 関係関数をメントにエレ メントが存在するかど うかは , ‘ によって 用いても実現可能である. 具体的な関係関数は , 図 5区別される.
中 ElementRelation のようになる. 前節では , エレ メ
ント内のアイテムを , ‘ ‘ という prefix を付けることで4 PrefixSpan の拡張
区別していたが , エレ メント内と外に対し , 別の関係名
4.1 関係関数(IN/OUT) を返すことで実現できる.
ここで , 関係関数 という関数を用い, PrefixSpan を拡張する. 関係関数とは , 系列デ ータベース S, 系 4.3 N-gramN-gram のマイニングは , シーケンシャルパターンマ
列 id sid, 整数 i, j(i < j) を引数とするような関数
Relation(S, sid, i, j) と定義され , seq(S, sid) 中のアイ イニングに含まれるため, N-gram をパターンとするようなマイニングの実現は極めて容易である. 具体的なテム item(S, sid, i), item(S, sid, j) の関係を返す.

関係関数は , 図 5 中の N GramRelation のようになる.

4.4

チャンク

チャンク構造は , 図 6 上のように , チャンク名とそのチャンクの中に含まれるアイテムから構成される. チャ
ンク構造に対しては , まず , 図 6 下のように , アイテムの列に続いて, チャンク名を別のアイテムとして挿入する. この時, 各アイテムの タイプ (type) を以下のように定義する. type(a) = N T (a がチャンク名の場合), type(a) = T (それ以外). チャンク構造に対する関係関数は , 図 5 の ChunkRelation ようになる. この関数
により, 基本的には , チャンク名の単位でマイニングが行われるが , 個々のチャンクがど うのようなアイテムから構成されるか同時に考慮することができる.

4.5

係り受け

語順が比較的自由である日本語のような言語では , 係り受け解析の結果を利用することで , 意味的に同じ文だが語順の違う場合, それらの違いを吸収できる可能性がある. まず , 語順を正規化する目的で , 係り受け解析の結果を , 以下の手続きで正規化された係り受け系列に変換する (図 7).
1. 文の head となる文節を配列に追加 する.
2. head 係る文節を辞書の降順に列挙する.
3. それら一つ一つに対し , 配列に追加し , その文節を headとみなし (2) へ戻り再帰的に繰り返す.
4. 配列を逆順にし , 出力する.

係 り 受け 構 造に つ い て の 関 係 関 数 を , 図 5 中の DepRelation のよ うに 定義する.
この 関数は ,item(S, sid, i) の係り先が , item(S, sid, j) の k − 1(k ≥ 1) 代目の祖先である場合, 関係名が k となる.
それ以外は , 未定義 (ε) となる. 図 8 にアイテム a から見た, 他のアイテムの関係名を示す.

5実験

5.1

実験設定

以下の 2 つの実データを用い実験を行った.
• 新聞記事 (京都大学コーパス 3.0 全文, 約 38,000 文)• 小説 (夏目漱石の「我輩は猫である」, 約 9,300 文 2 )ChaSen3 及び CaboCha4 を用いて形態素解析 (文/単語認定), 構文解析を実施した.

function ElementRelation(S, sid, i, j)
begin
x ← item(S, sid, i)y ← item(S, sid, j)
if (x, y が同一 element 内に存在) return IN
else return OU Tendfunction N GramRelation(S, sid, i, j)
begin
if (i + 1 = j) return NGRAMelse return εendfunction ChunkRelation(S, sid, i, j)
begin
x ← item(S, sid, i)y ← item(S, sid, j)
if (type(x) = NT) return CHUNK
if (type(x) = T and type(y) = T andx, y が同一 チャンク 内にある) return CHUNK
if (type(x) = T and type(y) = NT andチャンク y の中に x が含まれる ) return CHUNK
return εendfunction DepRelation(S, sid, i, j)
begin
x = item(S, sid, i)
y = item(S, sid, j)
if (x の係り先位置 < j) return εr←0while (x の係り先 6= y)beginr ← r+1y ← y の係り先
end
return rend

図 5: 関係関数の具体例

A
a b c ..

実験には , Linux (XEON 2.2 GHz のプロセッサ, 3.5GBの主記憶) の WS 使用した. 係り受けは Perl を , それ以
外は C++ を用いて実装した5 .
2 http://www.aozora.gr.jp/
3 http://chasen.aist-nara.ac.jp/
4 http://cl.aist-nara.ac.jp/˜ taku-ku/software/cabocha/
5 http://cl.aist-nara.ac.jp/˜ taku-ku/software/prefixspan/y a e c ..

Bz

b d e ..

xb d e ..
yAa  ec .. zC <a b c ..

テキストの構造として以下の 3 つの実験を行った.
• N-gram (アイテムは , 単語の表層)• チャンク (2 段階のみの係り受け )文節の表層をチャンク名, チャンクの中にあるアイテムをチャンク名に係る文節の表層とする. チャンク名とチャンク中のアイテムは集合とみなし 辞書順にソートする.
松澤 [3] と同一の構造である.
• 係り受け (アイテムは文節の表層)

Cx B>

図 6: チャンク の表現

bedc

acdbe

図 7: 係り受けの正規化

abcde

2

2

10f

図 8: アイテム a から見た関係名a表 1: 実験結果
minsup
2
5
10
15
20

5.2

抽出時間 新聞記事/小説 (秒)N-gramチャンク
係り受け
2.2/0.46 N/A/0.74 355.6/7.8
2.0/0.43
3.2/0.60
26.7/5.8
1.9/0.41
3.0/0.57
24.0/5.2
1.9/0.41
2.8/0.55
22.9/4.8
1.9/0.41
2.9/0.55
22.1/4.6

実験結果

表 1 に最小サポート値 (minsup.) と実行時間 (秒) の関係を示す. 新聞記事に対しチャンクの構造を適用した時以外は , どれも現実的な時間で終了している. ただ
し , 新聞記事に関しては , 最小サポート値が小さくなるにつれ実行時間が大きく増加している. この理由としては , 新聞記事では言い回しが小説に比べ固定されており, それらが頻出するためであると考えられる.
以下に , それぞれの構造において抽出された頻出パターンのいくつかを紹介する. これらがどれだけ有用か客観的な評価は行えないが , 文としての構造を崩していないため, それ自身で何かしらの意味を持つようなパターンが抽出されている.
・N-gram (上:新聞, 下:小説)
ロシア 南部 チェチェン 共和国 の 首都 グロズヌイ
これ が 鈴木 君 の 心 の 平均 を 破る 第・チャンク (上:新聞, 下:小説)(震度は {各地の}) (通り {次の, 震度は })(ないから、{吾輩は , 仕方が })・係り受け (上:新聞, 下:小説)((ついて 述べ、) (記者会見で、 明らかにした。))(休養を (また (吾輩は 要する。)))

6

応用例

6.1

機械学習の素性抽出

各々の言語を Chunker や係り受け解析器を用い, 半構造化テキストデータに変換する. 次に , それぞれのデータを単純に連結し , 1 つの系列を作成する. 単言語間では , その言語を表現するための関係関数をそのまま使用
し , 2 言語間のアイテムをまたぐ 射影では , 任意の射影が許可されるように関係関数を設計する.
このような系列データベースを用い, PrefixSpan を実行することで , 頻出する共起部分パターン及び , 単言語のみから構成されるパターンが抽出される. それらの頻度も抽出されるため, 共起頻度と独立頻度のみで計算を行う dice 係数や, 相互情報量の算出は容易に行える.
簡単な例として , 日英の対訳コーパス 9268 文を用い,対訳表現抽出を行った. 構造として , 系列及び N-gramを対象とした. ただし , あらかじめ機能語相当の単語はアイテムから取り除いている. 最小サポート値を 2 とした設定で PrefixSpan を実行した結果, 候補生成に要した時間は , 系列 52 分, N-gram 7 秒となり, 十分実用的な時間で終了した. 抽出された翻訳パターンの良し悪しを評価する事は , 本稿の主旨では無いので , 詳細な評価は行わないが , 系列に基づく手法において , 以下のような不連続な翻訳パターンが抽出されたことは大変興味深い.
earliest convenience
let ... know
thank ... letter7

都合 つき 次第
お知らせ
手紙 ありがとう

まとめと今後の課題

本稿では , 種々の自然言語処理ツールの結果から得られた半構造化されたテキストに対するマイニング手法提案した. 具体的には , シーケンシャルパターンのマイニング手法である PrefixSpan アルゴ リズムに対し , 関係関数を導入することで , チャンクや係り受けといったデータ構造を考慮できるように拡張した .
本稿では , 抽出されたパターンの客観的な有効性に関する評価は行っていない. 今後は , 対象とする構造, 関係関数の違いにより, 抽出されるパターンにどのような違いが現われ , それらが具体的な応用においてどれほどの有意差を生じるか評価を行いたいと考える. さらに ,木構造, グラフ構造といった一般的な構造が関係関数で記述できるか , また, それらの完全性や健全性についても議論していきたいと考える.

機械学習を運用する際, 相互情報量など の基準を用
い, ど ういった素性が分類に有効か , 素性の選別を行う事で精度向上に繋がる場合がある. もし , 素性の組み合わせや, 素性ど うしの関係を新な素性 (パターン ) して定義すれば , 同様な方法でそらの新しい素性を選別することが可能であろう.
ここで , 本稿で提案した マイニングの手法が適用可 参考文献
能ではないかと考える. 具体的には , クラス yi と 素性の系列 xi を単純に連結し , 新たな系列を作成する. 関 [1] Rakesh Agrawal and Ramakrishnan Srikant. Mining
sequential patterns. In Philip S. Yu and Arbee L. P.
係関数としては , アイテム yi からは , xi の任意のアイ
Chen, editors, Proc. 11th Int. Conf. Data Engineering,テムに射影可能な関数を , また, xi 内のアイテムど うしICDE, pp. 3–14. IEEE Press, 6–10 1995.の関係は , 半構造化データ xi を記述するための 関係関数を用いる. これにより, クラスの独立頻度, パターン [2] Jian Pei, Jiawei Han, and et al. Prefixspan: Mining sequential patterns by prefix-projected growth. In Proc.とクラスの共起頻度, パターンの独立頻度を算出し , 相of International Conference of Data Engineering, pp.
互情報量などを計算することができる.

6.2

215–224, 2001.

対訳パターンの抽出

対訳コーパスから , 対訳パターンを抽出するタスクにおいても, PrefixSpan は有効であると考える. まず ,[3] 松澤裕史. 大規模データベースからの頻出構造化パターンの抽出. 情報処理学会論文誌, Vol. 42, No. 8, 2001.