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

山本 薫 ‡坪井 祐太 ††松本 裕治 †† 奈良先端科学技術大学院大学 情報科学研究科‡ 理化学研究所ゲノム科学総合研究センター†† 日本 IBM 東京基礎研究所†{taku-ku,matsu}@is.aist-nara.ac.jp, ‡kaorux@gsc.riken.go.jp, ††yuutat@jp.ibm.com

テキストマイニングの分野は決して新しいものではなく, 単語の共起やクラスタリングといった多くの手法が現在まで提案されている. しかし , それらの多くは , テキストを単語の集合や 1 次元的な列という簡単な構造で表現しており, 単語間の関係や構文的な係り受け関係を無視してしまっている. テキストに対して ,平坦な構造しか仮定していない場合には , 文がもつ本当に意味のある構造をうまくとらえらない. 本稿では ,チャンキングや係り受け解析といった自然言語処理ツールを使用し , テキストデータを具体的な内容をよりよく反映した半構造化データに変換し , そこから有益なパターンを抽出する手法を提案する. 具体的には ,テキストマイニングを半構造化されたデータから頻出する部分構造の抽出ととらえ , シーケンシャルパターンのマイニング手法である PrefixSpan アルゴ リズムを拡張し , この問題を効率よく解決するアルゴ リズムを提案する.
キーワード : テキストマイニング , シーケンシャルパターンマイニング , 半構造化データ, PrefixSpan

Mining Syntactic Structures from Text Database
Taku Kudo†

Kaoru Yamamoto‡Yuta Tsuboi††

Yuji Matsumoto††Graduate School of Information Science, Nara Institute Science and Technology‡RIKEN Genomic Sciences Center††IBM Research, Tokyo Research Laboratory, IBM Japan, Ltd.
†{taku-ku,matsu}@is.aist-nara.ac.jp, ‡kaorux@gsc.riken.go.jp, ††yuutat@jp.ibm.com
Text mining has gained the focus of attention recently, in particular, the success in word clustering havebeen reported. However, many of these bag-of-word or sequence-of-word approaches ignore the implicit
dependency relations between words which are critical to understanding of the original text. In thispaper, we apply syntactic parser to convert a raw text into a semi-structured text from which usefulpatterns are extracted. We extend the PrefixSpan algorithm, one of an efficient algorithms for sequential
pattern mining, to efficiently extract sub-structures from a text data annotated by syntactic parser.
Keywords : Text Mining, Sequential Pattern Mining, Semi-structured Data, PrefixSpan

1

はじめに2

シーケンシャルパターン

データマイニングとは , 膨大なデータの中から有マイニングと PrefixSpan
用, あるいは興味のあるパターンを明示的な知識としAgrawal[1] らは , シーケンシャルパターンマイニて発掘する方法についての科学的研究である.
1
ングを以下のように定式化している
その対象をテキストデータとしたテキストマイニ
I = {i1 , i2 , . . . in } を , アイテム 集合とする. 系列
ングの分野は , 決して目新しいものではない. 例えば ,とは, アイテムの列であり, hu1 , u2 , . . . , un i, と表記
語と語の共起関係や相関関係を調べたり, 語のクラスする.
uk は任意のアイテムである. ある系列 α 中のタリングといった処理は , 古くから研究されてきていすべてのアイテムが , 別の系列 β 中に存在し , そのる [2, 3]. これらの研究の多くは , 形態素解析といっ順番が保持されている場合, 系列 β は系列 α を「含た比較的「浅い」言語処理技術のみを利用し , テキスむ」と言い,αvβと表記する. 系列データベース S
ト全体を単語の集合や一次元的な列とみなして処理を行っている. しかし , このようなデータ構造は , 機 とは , 系列 id sid と系列 s のタプル hsid, si の集合で械処理に向いているといはいえ , 各単語のテキスト中 ある. S = {hsid1 , s1 i, hsid2 , s2 i, . . . , hsid2 , sn i} . さの役割, 単語間の係り受け関係などを考慮に入れない らに , 系列 α の系列データベース S におけるサポーため, 文がもつ本当に意味のある構造をうまくとらえ ト supportS (α) とは , S 中のすべての系列のうち, 系列 α を含むタプルの数と定義される.
らないという問題がある.
シーケンシャルパターンマイニングとは , 系列デー
その一方で , Text Chunking, 係り受け解析 (構文解析), 固有名詞抽出といった高度な自然言語処理ツー タベース S と 任意の整数 (最小サポート 値 (miniルが近年利用できるようになってきた. これらのツー mum support) ξ) に対し , supportS (α) ≥ ξ となルにより, テキスト中の単語の役割がより明確になり, るような系列 α を全て列挙するタスクの事を指す.
この問題に対し , Pei ら [4] は , 深さ優先探索で多頻テキストの具体的な内容をよりよく反映したデータ度パターンを抽出する手法
PrefixSpan を提案してい構造に変換することができる. 自然言語処理ツールる.
PrefixSpanを説明する前に, そのアルゴリズムのを利用することで , 生のテキストは , ある構造を持ったデータ (半構造テキストデータ) に変換される. し 核となる射影 (project) という操作を説明する. あかし , 複雑なデータ構造になればなるほど , 単純に単 る系列 s = 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 が存在しない場研究が行われている. 安部ら [5] は , 半構造データと 合は , prefix,postfix は未定義 (ε) となる. ある系列
して, 木構造のデータをとりあげ , その集積から頻出 データベース S に対し , アイテム a によって 射影し ,する部分構造を効率良く発見する手法を提案してい 射影データベース S|a を作成するとは , S 中のそれる. 松澤 [6] は , 構文解析済みのテキストデータから ぞれの系列 s に対し , postf ix(s, a) を作成し , それら頻出する部分構造を効率良く発見する手法を提案し を改めて系列データベースとする操作と定義される.ている.
S|a = {hsid, s0 i|(hsid, si ∈ S) ∧本稿では , このような流れを受け , 自然言語処理(s0 = postf ix(s, a)) ∧ (s0 6= ε)}
ツールの結果から得られた半構造化されたテキストデータに対するマイニング手法提案する. 具体的に
図 1 に , ξ = 2 とした場合の PrefixSpan の動作過は , まず , 半構造データマイニングを与えられた半構程を示す. まず , アイテム数 1 の多頻度系列 a, b, c を造データから頻出する部分構造を発見する問題と定抽出する. d は , サポートが 1 であるため, 多頻度系式化する. さらに , シーケンシャルパターンのマイニ列ではない. 多頻度系列は , これら 3 種類あるが , そング手法である PrefixSpan アルゴ リズム [4] を拡張のうち a について考え , S の a による 射影データ
し , 構文解析済みの大量のテキストデータから , 頻出ベース S|a を作成する (図 1 中央上). この データする部分構文木 (部分構文構造) を高速に発見するアベースから , 多頻度系列 b, c を生成する. 以下再帰的
ルゴ リズムを提案する. さらに , 実際のテキストデーにこれらの作業を繰り返すことで , すべての多頻度系タを用いた実験結果を示し , 提案手法の有効性につい列を抽出することができる. PrefixSpan の擬似コーて議論する.
ド を 図 2 に示す.
1 この定式化は , エレ メントが無いため厳密ではない. 簡略化のためにエレ メントは省いている.

minsup = 2
project

sid sequence
12
34

acd
abc
cba
aab

a:4
b:2
c:2
d:1

124c db ca b

projected
database
23ca

sequence database13

count sup. of 1 item

a:1
b:2
c:2

db a2cec c:1b 01d d:1dba:1c:1a:1b:1d:1aee

ca:4
b:2c:2a b:2a c:2ada 1e1bebec2b2d23

図 3: 節点 a から見た他の節点との関係

results

図 1: PrefixSpan の動作過程

cbcall P ref ixSpan(ε, S)
procedure P ref ixSpan (α, S|α )begin
B ← {b|(s ∈ S|α , b ∈ s) ∧ (supportS |α (hbi) ≥ ξ)}

bforeach b ∈ B
begin(S|α)|b ← {hsid, s0 i|(hsid, si ∈ S|α)
∧ (s0 = postf ix(s, b)) ∧ (s0 6= ε)}3PrefixSpan の木構造への拡張

daebdec((b ((e a) ((b d) (((c d) (e a)) b)))) c)

call P ref ixSpan (αb, (S|α )|b )endend

図 2: PrefixSpan の擬似コードa

図 4: 系列表現への変換

3.2

節点間の関係順序木 t 中の任意の節点 i と i とは異なる別の節
点 j の 2 つの引数を取る関数 ψ : i → j を以下のよ
3.1 定式化
うに定義する. ψ は , 一般に非対称の関数となる.
(1) j は i の親: ψ = 0
シーケンシャルパターンマイニングと対比させな
がら , 順序木のマイニング問題を定式化する. I =(2) j の k − 1(k ≥ 1) 代目の祖先は , i の右側の兄{i1 , i2 , . . . in } を , アイテム 集合とする. 順序木 とは ,弟: ψ = k
アイテムを節点とし , 兄弟間には全順序が定義される(3) (1),(2) 以外: ψ = ε
木構造の事を言う.
図 3 に , 関係関数 ψ : i → j の例を示す.
ある順序木 α が , 別の順序木 β の部分木である時,β は α を「含む」と定義し , α v β と表記する. 具3.3 木構造の系列表現
体的には以下の条件を満たすような射影 φ : α → βが存在する必要がある.
順序木 t をそれと等価な系列表現に変換することを考える. 系列として表現することで , PrefixSpan が(1) φ は単射である.
(2) φ は親子関係, 兄弟関係を保持する. ただし α 中 適用可能となる. ただし , 系列に変換しても, 前節でで隣接する兄弟は , β 中で隣接する必要はない. 定義した節点間の関係はそのまま保持されているこ
順序木データベース T とは , 順序木 id tid とそれ ととする. つまり, 順序木としての性質はこの変換でに対応する順序木 t のタプル htid, ti の集合である. 失われることはない. 具体的には , 木の右から左へ,
T = {htid1 , t1 i, htid2 , t2 i, . . . , htid2 , tn i} . さらに , 部 前順操作 (pre-order traverse) で節点を列挙した結果
分順序木 α の順序木データベース T におけるサポー を反転する. この変換により, 順序木中の任意の節点
トとは , T 中のすべての順序木のうち, 部分順序木 α の左隅の部分構造が , 系列中では , 節点に対応するアイテムの左側にある系列として表現される.
を含むタプルの数と定義される.
図 4 に , 順序木を系列表現に変換した例を示す. た¯¯supportT (α) = ¯{htid, ti|(htid, ti ∈ T ) ∧ (α v t)}¯ だし , 木構造の関係を明確にするため, 系列は S 式として表現している. 順序木中の太丸で囲んだ節点 d
順序木のマイニングとは , 順序木データベース T と の左隅の構造が , 系列中のアイテム d の左側の系列任意の整数 (最小サポート値 (minimum support) ξ) に対応する.
に対し , supportT (α) ≥ ξ となるような部分順序木 αを全て列挙するタスクの事を指す.

3.4

アルゴリズム順序木データベース T は , 順序木 id tid と順序木 tのタプル htid, ti の集合であった. ここでは , PrefixSpan を適用するために , 順序木データベースを tid と ,系列表現 t0 とのタプルの集合 htid, t0 i として取り扱う. この操作は , 問題の定式化自身を変えない.
順序木マイニングアルゴ リズムの基本的なアイデ
アは , 系列表現を , 単純な系列データとみなして PrefixSpan を動作させることにある. しかし , このままでは , 木構造の情報が欠落してしまい, 本来の目的が達成されない. そこで , 前々節で説明した関係関数 ψを使用する. 具体的には , PrefixSpan に対し 次の変更を加える.
(1) 通常のアイテムを , 節点名と関係のタプル hi, riという形で表現する.

(2) アルゴリズムを動作させる前に , 系列データベースの全アイテムを hi, 0i (i は各節点名) に初期化しておく.
(3) アイテム hi, r1 i で射影をする場合, 各系列中のアイテム hi, r1 i の右側にある 全アイテム hj, r2 i
に対し , r3 = ψ(i, j) を求める. 射影データベー
ス中のアイテム hj, r2 i を , hj, r3 i に置きかえる.
(4) 1 つの系列に , 同一アイテムが複数存在する場
合は , 最左のアイテムだけでなく, すべてのアイテムに対し射影を行う2 .
(5) (4) より, 同一の系列から , 複数の系列が生成されるが , 各アイテムの support は , 系列単位で算出する.
(6) hi, εi (i は任意の節点) のように , 関係が ε となる場合は , 数え上げの対象に含めない.
系列表現での prefix は , 順序木では , 左隅部分構造に対応する. つまり, このアリゴ リズムは , 木の左隅から部分木パターンを深さ優先で広げていき, 頻出パターンを抽出していく. 結果として得られるパターンは , 節点名と関係のタプルの系列である. この系列を ,順序木に戻せば , 最終的な結果を得ることができる.
図 6 に , 実際の動作例を示す. ただし図 6 中では ,タプル ha, bi を 便宜的に a-b と表記している.
実際にアルゴ リズムを動作させるにあたり, 射影時に毎回タプルを作成していたのでは効率が悪い. そのため, 実際には , 系列データの id と prefix の開始位置を記憶しておき, それらの情報を用いて射影を行う. 図 5 に , 実際のアルゴ リズムの擬似コードを示す.

4

実験

func seq(T, tid) := T 中の 系列 id tid に対応する系列表現
func node(T, tid, p) := seq(T, tid) の p 番目の節点
func ψ(T, tid, p, q) := node(T, tid, p),node(T, tid, q) の関係
ただし , ψ(T, tid, 0, q) := 0

# 順序木の系列表現データT = {htid1 , t01 i, htid2 , t02 i, . . . , htidn , t0n i}# tid と 位置情報のポインタ
P = {htid1 , 0i, htid2 , 0i, . . . , htidn , 0i}
call P ref ixSpan(ε, P )proc P ref ixSpan (α, P |α)begin# B は , タプルをキー,# タプルの集合を値とするマップ
B ← {}
foreach htid, li ∈ P |α
beginforeach k ← l + 1 to |seq(T, tid)|
beginb ← node(T, tid, k)r ← ψ(T, tid, l, k)
B[hb, ri] ← B[hb, ri] ∪ htid, ki
end
endforeach hb, ri ∈ keys of B
begin
if (support|Pα (hb, ri) < ξ) continue
call P ref ixSpan (αhb, ri, B[hb, ri])endend

図 5: 順序木に対する PrefixSpan の擬似コード• 新聞記事京都大学コーパス 3.0 全文, 38,383 文. この
コーパスは , 95 年 1 月の毎日新聞記事に対し ,形態素解析, 構文解析 (文節係り受け解析) が施されたものである.
• 小説
夏目漱石の「我輩は猫である」全文 9,298 文3 .
形態素解析 (文/単語認定), 構文解析 (文節係り受け解析) には , ChaSen4 及び CaboCha5 を使用した.
構文木としては , 文節の表層を単位とする依存構造木を考える. また, 単純な順序木の場合, 「 (本を (太郎に あげる)) 」と「 ((太郎に (本をあげる)) 」の 2 つの構文木は , 別の木となってしまうため, 兄弟関係にある節点をソートし非順序木に変換した . 実験は , PC(XEON 2.2 GHz, RAM 3.5GB, Linux) 上で行った.
実装には Perl を使用した.

4.1

実験結果

図 7 に 新聞記事を用い, 最小サポート値を 3 としアルゴ リズムの性能を評価するために , 以下の 2 つ た場合のデータサイズの増加に対するアルゴ リズムの実テキストデータを用いて実験を行った .
3 http://www.aozora.gr.jp/
4 http://chasen.aist-nara.ac.jp/
2 通常の PrefixSpan は最左のアイテムのみ考慮する.

5 http://cl.aist-nara.ac.jp/˜ taku-ku/software/cabocha/

tid

1cac2

34baaccabacbc-0 a-0 c-0 b-0 a-0 c-0

234

c-0 a-0 c-0 b-0 c-0 b-0
b-0 c-0 b-0 a-0 b-0 a-0
a-0 c-0 c-0 b-0 c-0 a-0
a-0: 4

Count Supports b-0: 4

2
4

112
3
4

c-2 b-2 a-1 c-0
c-0: 3c-0
c-0 b-e c-e b-e
b-1 a-0c-1 c-0 b-e c-e a-e

accb(((a c) c) ((b c) a))

12
3
3
4

a-0 c-ea-0: 2c-0 b-ec-0: 3c-0 b-e a-e b-e a-e
a-0
c-0 a-eb-2 c-1 b-0 b-2: 2b-2 c-1 a-0 c-1: 2

224c-0 b-e
c-0 a-e

tid

tid

24c-0

234c-0: 4

tid
b-0a-02
4b-0a-0b-0b-2 a-1 b-1 a-0a-0: 2a-0
tid
112tid1
1222
344tidtid

tidc-0: 4

Projectbctid

tid

1bb

((b c) ((b a) (b a)))minsup. = 2

Initial Databaseac((c a) (((c (b a)) c)) (((c a) c) ((b c) b))tid

ca-0 c-e b-e b-e c-e
b-1 a-0 c-ea-0 c-e b-e c-e b-eb-2 c-1 b-0
b-0
b-2 a-1 b-1 a-0
c-0 b-e c-e a-eb-2 c-1 a-0

tid

c-2 b-2 a-1 c-0
c-0
c-0: 2c-0 b-e c-e b-e2

tida-0: 3b-1: 2b-2: 2c-1: 213

tid

a-0 c-ea-0

a-0: 2

1

tid
2
3
4

2
4

2
4

b-0
a-0
Frequent Sub-Tree Patterns

c-0
a-0
b-0
c-0 a-0a-0 c-0b-0 a-0
c-0 a-0 c-0
a-0 c-0 b-2
b-0 c-0a-0 c-0 b-2 c-0 b-0 c-0 a-0 c-0 b-1c-0 b-1 a-0
a-0 c-0 c-1
c-0 b-2
c-0 b-2 c-0
c-0 c-1abc

図 6: マイニングの動作例

caabcabccacc-0
tid

c-0 b-ea-0 b-e a-e c-0: 2c-0 a-e

tid

Frequent Sequential Patterns

b-e c-1 b-0acbb-0a-0• 関係の算出/格納方法
実験では , すべての関係をデータの読み込み時に計算し , メモリに格納した状態でアルゴ リズ
ムを動作させた. しかし , 関係値は , 各系列の節点の数の二乗に比例した記憶容量が必要なため, 大規模なデータでは , メモリに納まらない可能性がある. 速度を落とすことなく, 規模耐性を上げ るためには , 効率の良い関係算出/格
納アルゴ リズムを採用する必要がある.

3530

CPU time (sec)

2520

15

10

500

5000

10000

15000

20000

25000

30000

35000

40000

# of transactions

図 7: データサイズと計算時間6

表 1: 最小サポート値 vs. 実行時間
minsup
新聞記事 (秒)
小説 (秒)

2434.0
7.4

3
31.3
6.3

526.7
5.5

10
23.7
4.8

20
21.4
4.3

まとめと今後の課題

本稿では , 構文解析済みのテキストに対するマイニング手法提案した. 具体的には , シーケンシャルパターンのマイニング手法である PrefixSpan アルゴ リ
ズムを拡張し , 順序木の集合から , 頻出する部分木をマイニングできるよう拡張した . 実際のテキストデータを用いた実験を行い, 提案アルゴ リズムが十分な規模耐性を持ち, 最小サポートが小さい時でも現実的な時間で終了することが分かった.
本稿では , 実際のテキストデータから頻出するパターンを抽出する実験のみに留まり, 抽出されたパターンの客観的な有効性に関する評価は行っていない. 今後は , 構文木 (係り受け構造) に対する本マイニ
ング手法と従来の単語の集合による手法を比較し , 抽
出されるパターンにどのような違いが現われ , それらが具体的な応用においてどれほど の有意差を生じるか評価を行いたいと考える. また, グラフ構造といった一般的な構造に対する拡張や , それらの完全性や健全性についても議論していきたいと考える.の計算時間の増加を示す. この図から , 提案アルゴ リズムは充分な規模耐性を持つことが分かる.
表 1 に , 最小サポート値を変化させた時の, アルゴリズムの計算時間の増減を示す. 最小サポートを 2(0.01%) にした時でさえ , 本手法が , 全パターンを発見するのに要した時間は 7 分程度であった.
比較として , 安部ら [5] の順序木のマイニング手法を , 同一の新聞データで実験したところ, 最小サポー
ト値が 2 の場合は , 半日たっても終了しなかった. 実
験環境や実装に用いた言語が異なるため , 厳密な比較はできないが , 提案手法は最小サポート値が小さい時に有効な手法と言える.
以下に , 抽出された頻出パターンのいくつかを紹介する. これらがどれだけ有用で興味深いかの客観的な評価は行えないが , 文としての構造を崩していない
参考文献
ため, それ自身で何かしらの意味を持つようなパターンが抽出されている.
[1] Rakesh Agrawal and Ramakrishnan Srikant. Mining
・新聞((ついて 述べ、) (記者会見で、 明らかにした。))
2回((機能を 果たしておらず、 ) (存在感すら 薄れている)) 3 回
・小説(休養を (また (吾輩は 要する。))) 2 回((云う 声が ) (また する。)) 2 回

sequential patterns. In Philip S. Yu and Arbee L. P.
Chen, editors, Proc. 11th Int. Conf. Data Engineering, ICDE, pp. 3–14. IEEE Press, 6–10 1995.
[2] Robert Dale, Hermann Moisl, and Harold Somers.
Handbook of Natural Language Processing. Marcel
Dekker, 2000.

[3] Christopher D. Manning and Hinrich Schütze. Foundations of Statistical Natural Language Processing.
The MIT Press, 1999.
実験により, 本アルゴ リズムは , 充分な規模耐性を[4]JianPei, Jiawei Han, and et al. Prefixspan: Min持つことが分かったが , まだ改善の余地がある. ここ
ingsequential
patterns by prefix-projected growth.
では , それらのいくつかを挙げる.
In Proc. of International Conference of Data Engi• 非連結部分木の枝刈り
neering, pp. 215–224, 2001.

5アルゴリズムの改良の可能性

図 6 の例には , c-0 b-2 c-0 のように , 連結して
[5] 安部賢治, 川副真治, 浅井達哉, 有村博紀, 坂本比呂志,いない部分木パターンが抽出されている6 . 非有川節夫. 頻出順序木パターン発見に基づくウェブマイ
連結パターンのうち, これ以上サイズが大きく
ニング . 人工知能学会研究会資料 SIG-FA/KBS-J22,ならないものを何らかの方法で検出し , それら
pp. 133–139, 2001.
を早期に枝刈りすることで , 高速化が見込める. [6] 松澤裕史. 大規模データベースからの頻出構造化パター

6 逆に言えば , 提案手法は , 兄弟関係のみのパターンを抽出できるアルゴ リズムと言え , マイニングの対象によっては利点となる.

ンの抽出. 情報処理学会論文誌, Vol. 42, No. 8, 2001.