シーケンスを節点とする木構造データマイニングのための半構造マイニング手法の改良

全文

(1)シーケンスを節点とする木構造データマイニングのための半構造マイニング手法の改良.

(2)

(3)

(4) 佐藤一誠 . . 中川裕志 .

(5) . 東京大学大学院情報理工学系研究科.

(6)

(7)

(8) . 東京大学情報基盤センター. . .

(9)

(10) .

(11)

(12)

(13)

(14) .

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23) .

(24) .

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34) . . はじめに. 近年，大規模なテキストデータが， !" や企業に蓄積されている．今後ますます増え続けるテキストデータに対し，有用なパターンを抽出するテキストマイニングという分野が注目を集めている．テキストマイニングの研究において、単語の出現頻度は重要な要素を占めている。また、単なる共起関係だけではなく、係り受け関係のような単語間の関係性を考慮することで，文が持つ意味構造を含めたマイニングの重要性が高まっている．これまで，係り受け関係は木構造で表現されてきた．しかし，係り受け関係を木構造で表す場合，以下のような問題が生じる．例えば，「ルーブル美術館に小泉首相が訪れた」という文を係り受け解析したとする．図 #$ % は，文節を # つの節点として木構造で表した場合である．図 #$% は，単語を # つの節点とした木構造で表した場合である．このように木構造で係り受け関係を表現し，図 & 図 ' にある $ %$%& つの木構造に共通する部分木を抽出する場合，$% のような部分木が抽出される．係り受け関係を単に木構造として表現したのでは，助詞や表記上のぶれなどによって，抽出できない単語間の関係が存在する．本研究では、係り受け関係をシーケンスを節点とす連絡先：〒東京都文京区本郷東京大学総合図書館内情報基盤センター図書館電子化研究部門.

(35) . 文節中の単語を直後の単語に係けることで作成することができ. る. る木構造として表現し、そのマイニング手法を提案することで，上記の問題を解決する。図 ( に具体例を示す．木の各節点はシーケンスとして扱われ，シーケンス内での共通部分が抽出される．本研究では，ラベル付き順序木マイニングアルゴリズム )*!+ を改良し，シーケンスを節点とする木構造のマイニングを行えるようにした．具体的には，)*!+ のアルゴリズムをシーケンシャルパターンマイニングアルゴリズム , - の視点で解釈することで改良した．以下，第 & 節で，シーケンシャルパターンマイニング，第 ' 節で，ラベル付き順序木マイニング $)*!+% について説明する．第 ( 節で，提案手法について説明し，第 . 節で，抽出例を紹介し，第 / 節で，提案手法の評価を行う．第 0 節で，関連研究について述べる．第 1 節で，まとめと今後の課題を述べる． ߚ ⸰ࠇ ⸰ࠇߚ ࡞࡯ࡉ࡞⟤ⴚ㙚ߦ. ߦ. ߇. ዊᴰ㚂⋧߇. 㚂⋧. ࡞࡯ࡉ࡞⟤ⴚ㙚. ዊᴰ. C. 図. #2. D. 係り受け関係の木構造表現例.

(36) ⸰ࠇߚ. ⸰ࠇߚ ࡞࡯ࡉ࡞⟤ⴚ㙚ߦ. ࡞࡯ࡉ࡞⟤ⴚ㙚ࠍ. ዊᴰ㚂⋧߇. ዊᴰ✚ℂ߇. ⸰ࠇ ߚ. ⸰ࠇ ߚ. ࡞࡯ࡉ࡞⟤ⴚ㙚 ߦ ዊᴰ 㚂⋧ ߇. ࡞࡯ࡉ࡞⟤ⴚ㙚 ࠍ ዊᴰ ✚ℂ ߇. D. C. D. C. ౒ㅢㇱಽࠍ᛽಴. ౒ㅢㇱಽࠍ᛽಴ ⸰ࠇ ߚ. ⸰ࠇߚ. ࡞࡯ࡉ࡞⟤ⴚ㙚. E. ዊᴰ ߇. E. 図. &2. 共通部分木の抽出例 #. ߚ. 図 (2 シーケンスを節点とする木構造による共通部分木の抽出例. ߚ. ⸰ࠇ. ⸰ࠇ. ߦ. ߇. ࠍ 㚂⋧. ࡞࡯ࡉ࡞⟤ⴚ㙚. ߇ 㚂⋧. ࡞࡯ࡉ࡞⟤ⴚ㙚. ዊᴰ. D. C. シーケンスデータベース. ዊᴰ. ౒ㅢㇱಽࠍ᛽಴. シーケンスデータベース - とは，シーケンス 4$% とシーケンスのタプル $ % の集合である．. ߚ.

(37) 3 $ % $ % $ %. ⸰ࠇ ߇. E. 図. . '2. 共通部分木の抽出例 &. シーケンシャルパターンマイニング . 提案手法の説明の準備として，シーケンシャルパターンマイニングについて説明する．. . 用語定義シーケンス. 3 をアイテム集合とする．シーケン. スとは，順序を持つアイテムの列である．シーケンスを 3 と表記する． $ 3 # & % は任意のアイテムである．シーケンス中のアイテムの個数をシーケンスの長さとする．シーケンス 3 の長さはであり，長さのシーケンスをシーケンスとする．あるシーケンス中のすべてのアイテムが，別のシーケンス中に存在し，その順序も保持している場合，をのサブシーケンスと呼び，をのスーパーシーケンスと呼ぶ．との関係をと表記する．.

(38). サポート値. シーケンスのシーケンスデータベース

(39) におけるサポート値とは，

(40) 中のすべてのシーケンスのうち，シーケンスを含むタプルの数である． $ % 3 $ % $ %

(41) . シーケンシャルパターンマイニングの問題定義. シーケンシャルパターンマイニングとは，シーケンスデータベース - から，最小サポート値と呼ばれる任意の正の整数に対し， $ % となるようなシーケンスを全て抽出する問題である． $ % を満たすシーケンスを頻出シーケンシャルパターンと呼び，長さの頻出シーケンシャルパターンを頻出シーケンシャルパターンと呼ぶ． .

(42) , - は，&55# 年に , らによって提案されたシーケンシャルパターンマイニングのアルゴリズムである 6&7．, - は，,

(43) 8

(44) という射影方法とその射影によって生成される射影データベースを用いて深さ優先的にマイニングを行うアルゴリズムである．.

(45) . と . &. あるシーケンス 3 アイテムに対し， 3 3 3 3 となるような正の整数 $

(46) % が存在すると仮定する．このとき，シーケンスをのに対する , とする．また，シーケンスをのに対する ,

(47) とする．もし，が存在しないときは，, ,

(48) は未定義とする．. 射影. . あるシーケンスデータベース - に対し，アイテム. によって射影するとは，シーケンスデータベース - 中の各毎に，シーケンスに対するの ,

(49) を作成し，その ,

(50) を改めてシーケンスデータベースとする操作である．また，このようにして作成されたシーケンスデータベースを射影データベースと呼ぶ．アイテムでシーケンスデータベース - を射影して作成された射影データベースを射影データベースと呼び，

(51) と表記する．射影と射影データベースの例を図 . に示す．図 . 中のシーケンスデータベース - をで射影すると，各の ,

(52) は， 3 #5 では， 3 &5 では， 3 '5 では無し， 3 (5 ではとなる．よって，これらが射影データベース

(53) となる． C ኿ᓇ࠺࡯࠲ࡌ࡯ࠬ 5C. ࠪ࡯ࠤࡦࠬ࠺࡯࠲ࡌ࡯ࠬ 5 5+&. 5GSWGPEG. . C FE EC D. . C ED. 2TGHKZ2TQLGEVKQP. C D E. C. 5+& 5GSWGPEG. . FE. . D ED. D /KPAUWR. 図. CD CE . E. .2 , - . D E. の動作例.

(54) のアルゴリズム , - はシーケンスデータベースに対し，深さ優先探索で射影を繰り返し，頻出シーケンシャルパターンを抽出する手法である．基本的な流れを以下示す． #. 長さ # の頻出シーケンシャルパターンをシーケンスデータベースから抽出する．すべての頻出シーケンシャルパターンは，この長さ # の頻出シーケンシャルパターンを , とするシーケンシャルパターン $部分シーケンシャルパターン% から成る．. 各々の部分シーケンシャルパターンを深さ優先で再帰的に抽出する．$#% で抽出した長さ # の頻出シーケンシャルパターンで射影した射影データベースを改めてシーケンスデータベースとみなす．このシーケンスデータベースから $#% と同様に部分シーケンシャルパターンを抽出する．抽出される部分シーケンシャルパターンが無い場合，射影は終了する．. 動作例を図 . に示す．最小サポート値 3& とすると，シーケンスデータベース - から抽出された長さ # の頻出シーケンシャルパターンは，，，となる．すべての頻出シーケンシャルパターンは，，，を , とする部分シーケンシャルパターンから成る．. を , とする部分シーケンシャルパターンは，シーケンスデータベース - をで射影した射影データベース

(55) から抽出される．この場合，射影データベース

(56) から，最小サポート以上のアイテムとして，，が抽出されるので，を , とする部分シーケンシャルパターンは，，，，となる．，を , とする部分シーケンシャルパターンは，射影データベース

(57) をで射影した射影データベース

(58) から同様にして抽出される．以下このように深さ優先で再帰的に繰り返される．. エレメントを単位とする. . エレメントとは，アイテムの集合である．エレメントは，アイテムを9$%9 で囲むことで表現する．図 / 中の $ % などがエレメントである．エレメントは集合であるので，エレメント中のアイテムの順番は考慮しない．このため，エレメント中では，アイテムを辞書順にソートしておく必要がある．逆に言えば，エレメント中のアイテムを辞書順にソートしなければ，エレメント中のアイテムの順番を考慮することができる．エレメントを単位とする , - は，射影するアイテムと同じエレメント中にあるアイテムに対して， 9 ＿9 という , を付ける．この , により，エレメントの外にあるアイテムと中にあるアイテムを区別をする．図 / を用いて動作例を示す．. で射影した場合を示す．で射影した射影データベースから，最小サポート以上のアイテムとして，＿，，が抽出される．＿は同一のエレメント内にあることを示すので，抽出される部分シーケンシャルパターンは， $，% ， $%，$% ， $%，$% となる．以下前節の , - と同様に深さ優先で再帰的に抽出される．.

(59) ࠪ࡯ࠤࡦࠬ࠺࡯࠲ࡌ࡯ࠬ 5 5+&. 5GSWGPEG. C ኿ᓇ࠺࡯࠲ࡌ࡯ࠬ 5 C. 2TGHKZ2TQLGEVKQP. CD DE C EC D E D CD DE E. C. 5+&. 5GSWGPEG. . AD DE. . D E. AD DE. /KPAUWR. CD C D C E . AD D E. &. ! は親子関係，兄弟関係を保持する．ただし，. 中で隣接する兄弟は，中で隣接する必要はない．.

(60). 順序木データベース. 順序木データベースとは，順序木 4$% と順序木のタプル $ % の集合である． 3 $ % $ % $ %. 図. /2. . エレメントを単位とする , - の動作例. 制約ベースのシーケンシャルパターンマイニング. , らは，シーケンシャルパターンマイニングにおいて，最小サポート値以外の制約を付加する必要性を提案している 6'7．例えば，平手らは，それぞれのアイテムがタイムスタンプを持つような時系列データに対して，時間制約を導入して，特定の時間間隔をもつアイテムのみ射影し，アイテム間の時間間隔を含めた形でパターンを抽出する手法を提案している 6(7．本提案手法も，この制約ベースのシーケンシャルパターンマイニングとして位置づけられる．. . ラベル付き順序木のマイニング. .

(61). 用語定義ラベル付き順序木. 3 をラベルの有限集合とする．ラ. ベル付き順序木とは，ラベルを節点とし，兄弟間には全順序が定義される木構造のことを言う．上のラベル付き順序木を， 3 として表現する．は節点の集合である．は親節点と子節点の接続を表す二項関係であり枝と呼ぶ．は，隣接兄弟節点間の順序を保持している．：は，節点に対応するラベルを求める射影である．は，親を持たない根節点である．子を持たない節点は葉節点と呼ぶ．節点列 3 において，任意の 5

(62) に対してが成立する場合，をからへの経路 $ % という．節点の深さ $ % をからまでの経路の節点数とする．以下ラベル付き順序木を単に順序木と呼ぶ．ある順序木が，別の順序木の部分木である時，はを「含む」と定義し，と表記する．具体的には，以下の条件を満たすような射影! 2 → が存在する必要がある． #. ! は単射である．.

(63).

(64). サポート値. 順序木の順序木データベースにおけるサポート値とは，中のすべての順序木のうち，順序木を含むタプルの数とする．

(65) $ % 3 $ % $ % .

(66). 順序木マイニングの問題定義. 順序木マイニングとは，順序木データベースから，最小サポート値と呼ばれる任意の正の整数に対し，

(67) $ % となるような順序木を全て抽出する問題である．

(68) $ % を満たす順序木を頻出順序木と呼ぶ．を順序木の節点数とし，順序木のサイズと呼ぶ．サイズの頻出順序木を頻出順序木と呼ぶ． . )*!+ は，&55& 年に : : : らによって提案された順序木マイニングのアルゴリズムである 6.76/7607．)*!+ は，順序木からその部分順序木を重複無く列挙するアルゴリズム $最右拡張% によって，頻出順序木を抽出するマイニング手法である．最右拡張は，同時期に ; < らによっても提案されており，部分集合を列挙するアルゴリズム - !

(69) 617 の部分木への自然な拡張となっている．.

(70). のアルゴリズム基本的なアルゴリズムは，以下の通りである． #. サイズ # の頻出順序木を抽出する．<3& とする．. &. サイズ <# の頻出順序木に，# つのノードを追加することで，サイズ < の候補順序木を構築する．.

(71) サイズ < の候補順序木が，最小サポート値以上の頻出順序木であるかを検査し，サイズ < の頻出順序木を抽出する．. '. の手続きを再帰的に適用することで全ての部分順序木を抽出する．$&% において，任意の位置にノードを追加すると重複する木を生成してしまうため，ノードの追加に制約を設ける．この制約を最右拡張と呼ぶ． $&%$'%.

(72). 提案手法の概要. 最右拡張. 順序木において，根節点から深さ優先で木を左回りに走査したときに最後に到達する葉節点を，最右葉と呼ぶ．根節点から，最右葉に至る経路を最右枝とする．最右拡張とは，任意の順序木において，最右枝上の節点に対し，新たな節点を最右葉となるように追加する手続きである．図 0 に，新たに節点を追加する場合の具体例を示す．. C ᦨฝ᜛ᒛ. D. E. C. F. G. ᦨฝ⪲. G. ᦨฝ⪲. G. ᦨฝ⪲. C. C. まず，順序木マイニングに対し，アイテムを単位とする , - を適用させる手法を提案する．これにより，シーケンスを節点とする順序木のマイニングは，エレメントを単位とする , - を適用させることで解決できる．本提案手法は，射影ベースの深さ優先探索版 )*!+ と解釈できるので，以下，)*!+$

(73) 8

(74) )*!+% と呼ぶことにする．. ᦨฝᨑ. D. E. D. E. C. F. C. F C. ᦨฝ⪲. D. E. C. F. )*!+ は，ラベルを節点とする順序木には，アイテムを単位とする , - として動作する．これが， )*!+ を , - の視点で捉えることに相当する．そして，シーケンスを節点とする順序木には，エレメントを単位とする , - として動作する．これが，)*!+ の改良に相当する．具体的には，ラベルを節点とする順序木に対しては，ラベルを節点とする順序木を，アイテムを単位とするシーケンスとみなして , - を適用させる．シーケンスを節点とする順序木に対しては，シーケンスを節点とする順序木を，エレメントを単位とするシーケンスとみなして , - を適用させる．ここで，単に，, - を適用させたのでは，抽出されるパターンは，木構造以外に，非連結なパターンも抽出されてしまうため，厳密な意味での部分木は抽出できない． )*!+ では，連結した部分木のみ抽出するために， , - で行う射影は， ,

(75) 8

(76) と呼ぶ射影を行う． ,

(77) 8

(78) は，抽出されるパターンが木となるような制約を射影対象に付加した射影である．. ラベルを節点とする順序木のシーケン図. . 02. 最右拡張の例. 提案手法. 係り受け関係をラベルを節点とする順序木として表したのでは，図 & 図 ' のように，節点数が少ない部分木が抽出されてしまう．本研究では，係り受け関係を，シーケンスを節点とする順序木として表現し，そのマイニング手法を提案することで，上記の問題を解決する．本節では，シーケンスを節点とする順序木のマイニング手法を説明する．本提案手法は，)*!+ のアルゴリズムをシーケンシャルパターンマイニングアルゴリズム , - の視点で捉え，改良することで実現できる．. スへの変換順序木マイニングにシーケンシャルパターンマイニング手法を適用させるために，ラベルを節点とする順序木を，アイテムを単位とするシーケンスへ変換する方法について説明する．ラベルを節点とする順序木を，根節点から深さ優先で順序木を左回りに前順走査 $

(79) % で節点のラベルを列挙する．列挙された順に 5 からを割り当て，これらをアイテムとする．列挙されたアイテム列をシーケンスとする．列挙しただけでは，順序木の情報が失われてしまうので，各アイテムは，次の情報を保持する．$ ，， % は，節点の親を指すである．は，節点の最左の子を指すである．この最左の子を長兄と呼ぶ．は，節点のすぐ右に位置する次弟を指すである．何れも存在しない場合は 3#.

(80) とする．このような情報を保持するアイテムの列を，順序木シーケンスと呼ぶ．図 1 に変換例を示す． . E . . C. C. . E. E. . . D. . . . . . . E. C. E. C. E. D. ⷫ. 㐳ఱ. ᰴᒉ. 図 12 ラベルを節点とする順序木のアイテムを単位とするシーケンスへの変換例. .

(81). 用語定義射影スタック. 射影スタックとは，射影したアイテムを積んでいくスタックである．あるアイテムで射影したとすると，アイテムは射影スタックに積まれる．アイテムでの射影が終了すると射影スタックから削除される．射影スタック中のアイテム集合を ,

(82) 8 と表現する．この ,

(83) 8 が抽出される頻出順序木パターンとなる． ,

(84) 8

(85) は，,

(86) 8 に連結するアイテムでのみ射影するように制約されている．.

(87) 代前の祖先アイテムの < 代前の祖先とは，アイテムと. の間に経路が存在し，その間のアイテム数 $節点数% が <# のアイテムである．アイテムの親は，# 代前の祖先となる．アイテムの 5 代前の祖先をアイテムそのものとする．.

(88)

(89). 弟. アイテムのを，$% と表現する．アイテム 8 がアイテムの弟であるとは，アイテムと 8 が共通の親を持ち，$8%$% を満たすことである．アイテムの直接に隣接する弟を次弟と呼ぶ．.

(90) 順序木シーケンス - のアイテムによる ,

(91) 8

(92) とは，以下の制約を満たす射影である．制約：射影データベース

(93) となるアイテムは，アイテムの ,

(94) の中で， ,

(95) 8 との間に枝を持つアイテムのみである．これは，アイテム，または ,

(96) 8 中のアイテムとの間に枝を持つ，つまり，連結するアイテムのみ射影データベースとすることを意味する． ,

(97) 8

(98) は，以下の & つの射影からなる．. .

(99) 8

(100) . . = <

(101) 8

(102) . 順序木シーケンス - のアイテムによる

(103) 8

(104) とは，アイテムの子となるアイテムのみ射影データベースとなる射影である．具体的には，まず，アイテムの長兄である子のを取得する．次に，長兄の次弟のを取得する．順次，次弟のを取得していけば，アイテムの子となるアイテムのを得ることができる．これらののみ射影データベースとなる．動作例を，図 > に示す．35 ので射影することを考える．,

(105) は，3# 以上のアイテムであるので，, ,

(106) 8

(107) では，3# 以上のアイテムはすべて射影データベースとなる．しかし，

(108) 8

(109) では，射影するアイテムの子となるアイテムのみ射影データベースとなるような制約を持つ射影であるので，この場合，3#，3( のアイテムのみ射影データベースとなる．これらのは以下のようにして求まる． 35 ので

(110) 8

(111) する場合を考える．まず，35 のの長兄である子の $3#% は 35 の自体が保持しているのですぐに取得できる．次に，3# のアイテムの次弟の $3(% は， 3# の自体が保持しているので取得できる． 3( のアイテムの次弟の $3#% は，3( の自体が保持しているので取得できる． 3( のアイテムの次弟のは# なので，これ以上は探索しない．これで，35 のの子のは，# ( と取得できる．順序木シーケンス - のアイテムによる = < とは，アイテムの < 代前の祖先の弟となるアイテムのみ射影データベースにとなる射影である．具体的には，まず，< 代前の祖先のを取得する．次に，< 代前の祖先の次弟のを取得する．順次，次弟のを取得していけば，アイテムの < 代前の祖先の弟となるアイテムのを得ることができる．これらののみ射影データベースとなる．

(112) 8

(113) .

(114) . C. いないので探索をやめる．. E . . C. . . E. D. E. Eߩ2QUVHKZ ,

(115) 8. . . D. ある．以上により，は，# ( と取得できる．. EJKNF RTQLGEVKQP . . . . . . . E. C. E. D. C. E. D. ኿ᓇ࠺࡯࠲ࡌ࡯ࠬ . C. . 図. >2 35. 中のアイテムの中で深さが最小のものはのの深さが & なので，< は，& までで. 5 で，3&. . C. . のでの

(116) 8

(117) の例. 動作例を，図 #5 に示す．3& ので射影することを考える．,

(118) 8335 の，3# のとする．つまり，35 の，3# のと射影されてきて，次に，3& ので射影することを考える．,

(119) は，3' 以上のアイテムであるので，, ,

(120) 8

(121) では，3' 以上のアイテムはすべて射影データベースとなる．しかし，= <

(122) 8

(123) は，射影するアイテムの < 代前の祖先の弟となるアイテムのみ射影データベースとなるような制約を持つ射影である．よって，この場合，3'， 3( のアイテムのみ射影データベースとなる．これらのは以下のようにして求まる． 3& ので

(124) 8

(125) する場合を考える． <35 の場合を考える．これは 3& の自身の弟となるようなを取得すればよい． 3& のの次弟の $3'% は 3& の自体が保持しているのですぐに取得できる．次に，3' のアイテムの次弟のを取得する． 3' のアイテムの次弟の $3#% は 3' のアイテム自体が保持しているので取得できる． 3' のアイテムの次弟のは，# なので，これ以上次弟はいないので探索をやめる． <3# の場合を考える．これは 3& のの親の弟となるようなを取得すればよい． 3& のの親の $3#% は 3& の自体が保持しているのですぐに取得できる．次に，3# のアイテムの次弟のを取得する． 3# のの次弟の $3(% は 3# のアイテム自体が保持しているので取得できる． 3( のアイテムの次弟のを取得する． 3( の次弟の $3#% は 3( のアイテム自体が保持しているので取得できる． 3( の次弟のは# なので，これ以上次弟は. 以下， ,

(126) 8

(127) の擬似コードを示す．.

(128)

(129)

(130)

(131) 8

(132) ，= <

(133) 8

(134) . 各々関数内部で ,

(135) 8

(136) を呼び出す．よって，上記の順で射影が行われる． ,

(137) 8

(138) は，)*!+ における最右拡張に相当する． . C. E . . . C . E. D. E. . Eߩ2QUVHKZ. . D. .GXGNUKDNKPI RTQLGEVKQP .GXGNUKDNKPI RTQLGEVKQP . . . . . . . E. C. E. D. C. E. D. ኿ᓇ࠺࡯࠲ࡌ࡯ࠬ . . D. C. . 図. #52 3&. のでの

(139) 8

(140) の例. シーケンスを節点とするラベルを節点とする順序木は，アイテムを単位とするシーケンスに対応している．そこで，シーケンスを節点とする順序木は，エレメントを単位とするシーケンスに対応させる．具体例を図 ## に示す．射影時に，同一エレメント中にあるアイテムに対して， 9 ＿9 を , としてつけることで，シーケンスを節点とする )*!+ は実現できる．ただし，今回は，エレメント中にあるアイテムのみを射影データベースに残す

(141) 8

(142) を

(143) 8

(144) より先に行うことで実現した．.

(145) . . FC. C. . ED. . . EH. . . . DF. . . . CDE FE ED C EH DF. . 図 ##2 シーケンスを節点とする順序木のシーケンスへの変換例以下，シーケンスを接点とする順序木に対するの擬似コードを示す．. ,

(146) 8

(147) .

(148)

(149)

(150)

(151)

(152)

(153) 8

(154) ，

(155) 8

(156) ，= <

(157) 8

(158) 各々関数内部で ,

(159) 8

(160) を呼び出す．. よって，上記の順で射影が行われる．. . 抽出例. データセットは，$株% 日本航空インターナショナルで収集されている航空安全レポートを用いた．# 文を単位として ?

(161) ? を用いて係り受け解析を行った．ラベルを節点とする順序木は，文節を節点とした係り受け木とし，シーケンスを節点とする順序木は，文節をシーケンスとし，単語 $形態素% をアイテムとした．紙面の都合上すべての抽出例を紹介することができないが，ランダムに取り出した # 555 センテンスからの抽出例を以下いくつか示す。最小サポート値は & とした。抽出例は - 式で表現している．従来手法では、「再出発」と「ＧＴＢ」を含むパターンは以下のものしか抽出されなかった。事前に名前等の個人情報は削除して、個人が特定できないようにしてある「。」で区切られた文を文とする.

(162) ! " 図 # $ 参照図 % 参照節点がシーケンスの場合は，「，」で区切られた単語列となってい. る. 再出発した $ＧＴＢし %$１０分遅れで % % 本提案手法では，$再出発した $ＧＴＢし $ため%%$１０分遅れで%% の他に $再出発た $ＧＴＢし $ため $た $が%%%%$遅れ $１時間%%% と従来手法では抽出されなかったパターンを抽出することができた。ＧＴＢを含む他のパターンとしては，以下のような従来手法では抽出されなかったパターンを抽出することができた． $ＧＴＢした $ため $た $ＦＬＴ＿ＣＯＮＴＲＯＬ＿Ｃ ’Ｋ中 $ＰＵＳＨ＿ＢＡＣＫ%%$が%%%% $ＧＴＢ $ため $ＡＰＰＥＡＲし $ＳＴＡＲＴ%$が%%%% 「ＦＬＴ＿ＣＯＮＴＲＯＬ＿Ｃ ’Ｋ」，「ＰＵＳＨ＿ＢＡＣＫ」，「ＡＰＰＥＡＲ」，「ＳＴＡＲＴ」などの単語がＧＴＢと共に現れるパターンは，従来手法では抽出されなかった．このように本提案手法では，従来手法では抽出できないパターンの抽出が可能である． $. CDE. . 評価. 本提案手法の評価として，抽出時間，節点数の統計量の評価結果を示す．特に，本提案手法は，シーケンスを節点とする順序木として係り受け構造を表現することで，ラベルを節点とする場合よりも大きいサイズの順序木パターンを抽出できることを示す．データセットは，前節と同様に，航空安全レポートを用いて作成した．実験環境は，以下の通りである． ?,@： , ##55AB，=& キャッシュ：#5&( C"，物理メモリ：0./"，プログラム言語：?DD，コンパイラ：E?? ''' 図 #& は，ラベルを節点とする順序木に対し，)*!+ ， )*!+ を適用させた場合の速度の比較を示したグラフである．)*!+ では，ラベルを節点とする順序木は，シーケンス中のアイテムが # つの順序木として扱われる．つまり，抽出されるパターン数は同じである．最小サポート値を & とした．図 #& からもわかるように， )*!+ は，)*!+ よりも抽出時間が早い．これは，射影を節点間の関係によって分けているためメモリ使用量が )*!+ は )*!+ よりも少なくて済むからであると考えられる．図 #' に，)*!+ と )*!+ の最大メモリ使用量の差を示す．図 #( は，抽出されたパターンの節点数の統計量である．最小サポート値を ' とし，節点が & 以上のパター節点数が大きい

(163) ! &のものを評価に使用. した横軸は，データセットの順序木の数.

(164) (4'36. . ᐔဋ୯ (4'36. . ᐔဋ୯ R(4'36. . ▵ὐᢙ. ▵ὐᢙ. . R(4'36. . . . . . ਛᄩ୯ (4'36 ਛᄩ୯ R(4'36. . . . . . 㗅ᐨᧁߩᢙ. . ᦨᄢ୯ R(4'36. . . . ᦨᄢ୯ (4'36. . . . ࠺࡯࠲࠮࠶࠻. ࠺࡯࠲࠮࠶࠻. ▵ὐᢙ. ᛽಴ᤨ㑆=OU?. . . . . . . ࠺࡯࠲࠮࠶࠻. 図. #&2. 抽出時間の比較. ᦨᄢࡔࡕ࡝૶↪㊂ߩᏅ=-$?. ンを抽出した．データセットを . つ作成して評価を行った．ラベルを節点として )*!+ を適用させた場合とシーケンスを節点として )*!+ を適用させた場合に抽出されたパターンの節点数の平均値，中央値，最大値の比較を行った．横軸は，各データセットであり，縦軸は，各々の節点数の統計量である．図 #( により，本提案手法は，従来手法に比べて，抽出される部分木は，平均値，中央値，最大値すべてにおいて大きいサイズの木である．これは，図 & と図 ( の違いを見ればわかる．図 & の抽出された部分木の節点数が # なのに対し，図 ( の抽出された部分木の節点数は ' である．より節点数の大きい部分木が抽出できれば，それだけ係り受け関係を持つ単語の関係を多く抽出できる．このように本提案手法は，従来手法よりも多くの節点数をもつパターンを抽出できる．よって，本提案手法は，従来手法では抽出できないパターンを抽出できると言える．. 図. . ᦨᄢࡔࡕ࡝૶↪㊂ߩᏅ (4'36㧙R(4'36. . . . 㗅ᐨᧁߩᢙ. . 工藤らによって，, - を，順序木のマイニングへ拡張する研究が行われている 6>76#57．工藤らの手法は，関係関数を導入して，, - を順序木のマイニングに拡張している．しかし，抽出されるパターンに，連結された部分木以外に，非連結の部分木が抽出されてしまう．よって，順序木のマイニングとは言い切れない．また，射影時に，各アイテム毎に関係値という値を算出し付加するため，節点数の & 乗に比例したメモリ容量を必要とする．本提案手法は，節点同士の関係に応じて分けて射影をしているため，このような関係値の付加は必要ない．また，本提案手法の最大のポイントは，シーケンスを節点とする順序木を定義し，そのマイニング手法を提案したことであるため，工藤らの研究とは大きく異なる．. おわりに. 係り受け関係をシーケンスを節点とする順序木で表現し，そのマイニング手法を提案した．これにより，従来手法では抽出できなかったパターンの抽出が可能であることを示した．今後の課題を以下示す．. パッケージのの公開 . 図. #'2. 最大メモリ使用量の差. 抽出した節点の統計量. 関連研究. . . #(2. )*!+. の速度向上. シーケンスを節点とする順序木の他分野への適用名詞のサポート値は & 倍にするといったような，単語の品詞などの情報の使用特に，シーケンスを節点とする順序木の他分野への適用としては，F= や A= のマイニングへの応用が. つのデータセットは個の順序木を持つ.

(165) !!! で公開予定.

(166) 考えられる．F= や A= は，タグの名前のほかに，属性を持つ．例えば，以下のようなＸＭＬは，「 #. #3G G &3GG」などをラベルとする木構造として表すことができる．.

(167)

(168)

(169)

(170)

(171) !

(172)

(173)

(174)

(175) "! !

(176) しかし，$ # #3G G &3GG% のようにそれぞれの要素をアイテムとしたシーケンスを節点にもつ木構造として表すこともできる．これにより，ＸＭＬデータからより柔軟なパターンの抽出ができると考えられる．. 謝辞本研究を進めるにあたり， $株% 日本航空インターナショナル運行本部から提供していただいたデータを利用しました．同社の齋藤隆氏，寺田昭氏に深く感謝いたします．. 参考文献

(177)

(178)

(179) .

(180) . .

(181)

(182)

(183) . !""#. !!! . . $$%. &'""#( ) * 1. *+

(184) . , - . . 2

(185) + . +

(186) /0

(187) . 34$

(188)

(189)

(190)

(191) .

(192) !Æ

(193) 2 52 346

(194) 7 0

(195) . !)88 !!! $$)#. ))&')88( % *$ *+

(196)

(197) 99

(198)

(199)

(200)

(201) $

(202) 0

(203)

(204)

(205) 5

(206) :)88) $$;)# ')88)( & < +

(207) + 2 < =

(208)

(209)

(210)

(211)

(212) 0 >=

(213) . : # :

(214) 6. 5. 0

(215) 6 : . > 2. . )88? +. = @$=- 5 .2 =. :. )88) ? > 2 . :

(216) 6 5. 0

(217) 6 : . +. = +0 = !Æ

(218) 5. .2 = A =. B. )88). 浅井達哉有村博紀半構造データマイニングにおけるパターン発見技法電子情報通信学会論文誌 . *;

(219) ) $$B""? ')88&(. ;. 5 * , 2 * !Æ

(220) 2 =

(221)

(222)

(223) $

(224) = 5 7@. ". "";. 工藤拓山本薫坪井祐太松本裕治言語情報を利用したテキストマイニング情報研報 'CA( D )88) C8)8 $$?#B) ')88)(. 8. 工藤拓山本薫坪井祐太松本裕治テキストデータベースからの構文構造のマイニング情報研報 '( D )88)C8&# $$%"&')88)(.

(225)