情報利得値の上界を枝刈り基準とした特徴的部分グラフの探索

全文

(1)人工知能学会研究会資料 SIG-DMSM-A603-13 (2/28). 情報利得値の上界を枝刈り基準とした特徴的部分グラフの探索.

(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)

(36)

(37)

(38) ! #

(39)

(40)

(41)

(42)

(43) "

(44)

(45) . ! $ " " . %

(46) ! はじめに. 近年，大量に蓄積された電子化データから有用な知識を発掘するデータマイニングにおいて，複雑なデータをより柔軟に表現できるグラフ構造データを対象としたグラフマイニングが注目され，多くの手法が提案されている &'" (" )" *" +" ," -(" -./．グラフ構造とはいくつかの頂点とそれらを結ぶ辺で構成されるデータ表現形式であり，グラフ構造データの代表例としては 000 などのネットワーク構造，化学構造式，回路図等が挙げられる．そのようなグラフマイニングの一手法である

(47) （）法 &,/ は，従来手法である

(48) （）法 &-./ と同様に，隣接する頂点対を逐次拡張（チャンク）することにより，グラフ中に頻繁に現れる典型的な部分グラフを発見することができる．ただし，チャンキングの際に頂点対を新たな - つの頂点に置き換えグラフ全体を書き換える法とは異なり，法は頂点連絡先：大阪大学産業科学研究所鷲尾研究室〒大阪府茨木市美穂ヶ丘

(49) . 対に新たなラベルを割り当てて新たな頂点として扱いつつもグラフ自体は書き換えない擬似チャンキングという方法を採用している．これにより，法は法やその拡張である（）法 &+/ では同時に抽出することが困難であった部分的に重複する部分グラフを抽出することが可能である．その一方で，擬似ノードの導入により，法の時間計算量，空間計算量は急激に増加する傾向にあり，対象データによっては限られた計算時間，及び計算資源の下では，対象データの特徴を十分に表す部分グラフを抽出できない場合があった．そこで本稿では，クラスが割り当てられた複数のグラフからクラス分類性能の高い部分グラフを抽出する問題に法を適用する場合を考え，その場合における法の探索を効率化するために情報利得値（）の上界を用いた枝刈り手法を提案する．情報利得値は，法において部分グラフのクラス分類性能の評価指標として用いられており，その上界を求めることが可能である &1/．提案手法では，探索過程において生成する部分グラフについて，その部分グラフを含むグラフ（の拡大グラフ）が取り得る情報利得値の上界を求めることで，を擬似チャ. - 97 -.

(50) 1 3 2. 3 2. 7. 5. 擬似ノード. 8 5. 3 2 6. 11. 9. 入力グラフ. チャンキング過程擬似ノード 10. 1. 1 3. 2. 図. 2. 10. グラフのデータベース. 10. 1. 7. 1. 4. 擬似ノード. 4. 1. 11 10 3. 11 10. 2. 3. 2 7. 5. 1 11. 4. . 4. 1. 特徴的な部分グラフの集合. 8. 7 10. 3. 11 10. （最初は空集合） . 9. 出力グラフ擬似ノード 10. 個の頻度の高いペアをで抽出されたペアの中から選ぶ．個の選ばれたペアをそれぞれ抽出部分グラフとしてに加える．この時，ペアを構成するノードが擬似ノードであれば元の部分グラフに復元してからに加える．この際，擬似チャンクすべきペアがなければ終了する．また，レベルがの場合もここで終了する．. 1. 3. ，頻度の閾値. のグラフ中の隣接するつのノードから成る全てのペアを抽出し，それらの頻度を数える．レベル以降については，つのノードのうち少なくとも片方は新しく登録された擬似ノードからなる全てのペアを抽出し，頻度を数える．ここで，よりも低い頻度のペアは擬似チャンクすべきペアとして数えることに意味を持たないので削除する．. 5. 2 6. . ，ビーム幅，最大レベル. . 3. 2. 擬似ノード11. -2 法における擬似チャンキングの例.

(51) で選ばれたペアにそれぞれ新しいラベルを割り当てるが，グラフは書き換えない．そして，に戻る．. ンキングにより拡張する価値があるかどうかを判定する．さらに本稿では，情報利得値の上界による枝刈りを導入した法を人工データセット，および実データセットに適用し，その実行時間，得られた部分グラフのクラス分類性能などを従来の法と比較することで，提案手法の有効性を実験的に示す．なお，本稿では，擬似チャンキングの対象をノード，ノードの対をノードペア，もしくは単にペアと呼ぶ．つまり，ノードはグラフ本来の頂点，もしくは擬似チャンキングにより生成された部分グラフを表す擬似ノードのいずれかを意味し，擬似チャンキングは，ノードペアから新たな - つの擬似ノードを生成することになる．. 図. '2 法のアルゴリズム E. B. E. A. B. A. B. D. C. D. C. (a). 図. (b). (2 重複する部分グラフの問題. . に出力される &,/．なお，におけるペアの評価指標としては，法と同様に単純なペアの出現頻度の他に対象ドメインに応じて情報利得値法 &--/，情報利得値の上界， 4 &-3/， &-/ など頻度に基づいた様々な評価関数を用いる法の概要ことができる．法の動作を図 - を用いて説明する．図 - は，法は，法では抽出が困難であった部分的入力グラフ中のノード -，'，及び ( からなる典型的なに重複する複数の部分グラフも同時に抽出できる．た部分グラフが擬似チャンキングにより抽出される過程とえば，図 ( において円で囲まれたノードペアがを示している．まず，入力グラフ中のノード - と ( か最初のチャンキング対象となった場合を考える．このらなるペアが擬似チャンクされ，擬似ノード -3 として場合，チャンキングするごとにグラフを書き換えてし登録される．その後，擬似ノード -3 とノード ' からなまう法では，両方のグラフ中に 5 というるペアが擬似チャンクされることで，擬似ノード -- が共通する部分グラフが存在するにもかかわらず，図 ( 生成される．この擬似ノード -- が，前述の典型的な部（）のグラフでは左上のノードペアが先にチャン分グラフに相当する．キングされ異なるノードに置き換えられてしまうため，法の擬似チャンキングアルゴリズムを図 ' に当該部分グラフを発見することができない．これに対示す．法では，ビーム幅の他に，繰り返しして法では，ノードペアは擬似ノードとの最大数，およびペアが満たす最小支持度をパラして扱われるが，頂点は他の擬似チャンキングでもメータとして与え，これらにより探索空間が制御され利用可能であるため，5 という部分グラフを抽る．また，アルゴリズムの ∼ までの一出することが可能である．連の流れを一つの段階と考え，これをレベルと呼び，レベルは擬似チャンクすべきペアがある限り，3∼ まで繰り返される．理論的には，最低支持度を 3 にし，法の問題点とを十分に大きく設定することで，法は可法は擬似チャンキングを導入することによっ能な全ての部分グラフを抽出できる．また，特徴的な部て，部分的に重複する部分グラフも抽出可能になった分グラフは各グラフ中における存在位置の情報ととも. .

(52) . - 98 -.

(53) -2 レベルごとのノードペア数の違い. 表レベル. チャンキング. 3 '. 5 4 5. 6. 擬似チャンキング. -'" -(" -." -)" .) -'" -(" -." -)" .) '*" (*" )*" (+" .)" .+" )+ -'" -(" -." -)" .)" '-6." (-6." )-6." (-6'" )-6' '1" )1" (+" +, -'" -(" -." -)" .)" '-6." (-6." )-6." (-6'" )-6'" '-6(6." )-6(6." '6-.6) 2 3. 5. 8. 6 4. 2. 5. 2. 1. 4. 3. 5. 1. 1. 2. 8 4. 3. 5. 5. 7. 9 3. 7. (a). 図. 3. 3 4. 3. される．直感的には，グラフ集合内のクラスのあいまいさが分割によりどれだけ減少したかを数値化したものであり，あるクラスに特徴的な部分グラフを用いるほど，その数値は高くなる．' つのクラス，のいずれかに属するグラフの集合を部分グラフを含むか否かで分割した場合の情報利得値は以下の式で定義される．なお，とはそれぞれ，部分グラフを含む，または含まないグラフの集合を表す．. 2. 2 7. 4. 1. 5. 1. 2 3. 9 5. 7 4. 1. 2 3. (b). .2 擬似チャンキングによる計算量の増加.

(54) - ここで，

(55) ，

(56) （ 9）はそれぞれグ 7

(57) . . が，その反面，考慮すべきノード数が増加することにともなって，法や法にビーム探索を導入した法ではチャンクする度に減少していたペアが指数的に増加し，その結果，空間計算量と時間計算量が増加している．例として図 . を考える．図 .（）は法の 7 '， 7 ( のチャンキング過程を，図 .（）は法の 7 '， 7 ( の擬似チャンキング過程を示している．両者を比較すると，法ではノード数が減少しているのに対して法ではノード数が擬似ノードの分だけ増加していることがわかる．また，この場合の法におけるチャンキング候補と法における擬似チャンキング候補は表 - に示すとおりであり，法では状態を増やした直後に一旦増加したチャンキング候補のペアが次の時点では減少しているのに対し，法ではレベルが進むにつれて擬似チャンキングの候補ペアが単調に，かつ大幅に増加していることがわかる．このように，法のほうが法よりも探索空間は広いが，計算量がはるかに多くなる．. !. . 情報利得値の上界に基づく枝刈り情報利得値. 情報利得値は，グラフ集合をある部分グラフを含むものと含まないものに分割した際に，その分割前後のグラフ集合の情報量，つまり 8 の差として計算 ½ 法では，個のペアを選択するとともに状態を個に分割し，各状態で各ペアをチャンキングすることを回繰り返す．ただし，各状態で個のペアを選択するのではなく，全体で個のペアを選択する．. . ラフ集合，のエントロピーであり，次式により求められる．.

(58) 7

(59) 7. . . . . . . . ' (. ここで，，はそれぞれ中のグラフのうちクラスに属するグラフの集合と中のグラフのうちクラスに属するグラフの集合であり，，はそれぞれ中のグラフのうちクラスに属するグラフの集合と中のグラフのうちクラスに属するグラフの集合である．上記のように定義される情報利得は凸関数であり，の任意の拡大グラフに関して，その上界を計算できることが知られている &1/．具体的には，を含むクラス ¼ ，に属するグラフの集合をを含むクラスに属 ¼ ¼ するグラフの集合をとしたとき， 7 か ¼ 7 3，もしくは ¼ 7 3 かつ ¼ 7 つのいずれかのときに，は最大値を取る．すなわち，この最大値が部分グラフを拡張した際の情報利得値の上界となる．なお，はの拡大グラフで ¼ ¼ あるので，であり，同様にである．図 ) に情報利得値の上界の計算の例を示す．部分グラフを含むグラフ数が 7 (， 7 ' であると ¼ き， 7 3，¼ 7 '，もしくは ¼ 7 (，¼ 7 3 のときのいずれかでの拡大グラフの情報利得は最大となり，実際には前者の場合に 7 3-31. - 99 -. . . . . . . . .

(60) クラス Gのグラフ数. A. B. 15. 15. Ggのグラフ数. 3. 2. Gg’ のグラフ数. 0. 2. Gg’ のグラフ数. 3. 0. 図. クラス A どちらかで情報利得値が最大. クラス Gのグラフ数. Gain( g ' , G ) = 0.070 Gain( g ' , G ) = 0.108 → u ( g ). クラス A. クラス Gのグラフ数. A. u(g) = 0.108. 図. クラス B. 4. 図. g を含むグラフ. +2 事後枝刈りの例. . 3. 特徴的な部分グラフの集合. 情報利得値の上界を計算 u'(g) = 0.148. 1. . グラフ構造のデータベース，ビーム幅，最大レベル閾値，情報利得値の上界の閾値. B. 15 15. GGのグラフ数の最大値. 3. 情報利得値の上界を計算. )2 情報利得値の上界の計算の例 P2. B. 15 15. 実際のGGのグラフ数. P1を含むグラフ. g P1. A. クラス B.

(61). ，頻度の. （最初は空集合）. のグラフ中の隣接する二つのノードから成る全てのペアを抽出し，レベル以降については，二つのノードのうち少なくとも片方は新しく登録された擬似ノードからなるペアの全てを抽出する．. g を含む可能性 P2を含むグラフのあるグラフ. （事前枝刈り）ノードペアの頻度計算前にペアを構成する各ノードを共に含むグラフ数からノードペアの可能な最大の頻度を計算し，それに基づき情報利得値の上界を計算する．その値がより小さいペアは削除する．. *2 事前枝刈りの例.

(62). . という最大値を取る．以下では，部分グラフの拡大グラフが取り得る情報利得値の上界をとする．.

(63) 抽出されたペアの頻度を数え，よりも低い頻度のペアは擬似チャンクすべきペアとして数えることに意味を持たないので削除する．また，抽出されたペアの情報利得値を計算し，これまでに抽出した情報利得値の中で最大なものがあればを更新する．. . （事後枝刈り）実際に計算されたノードペアの頻度を用いて情報利得値の上界を計算し，その値がより小さいペアは削除する．. 法への枝刈りの導入.

(64).

(65). 個の頻度の高いペアをで抽出されたペアの中から選ぶ．本節では，本稿で提案する法における情報個の選ばれたペアをそれぞれ抽出部分グラフとしてに加える．こ利得値の上界を用いた枝刈りについて述べる．の時，ペアを構成するノードが擬似ノードであれば元の部分グラフに復元してからに加える．この際，擬似チャンクすべきペアがなけ法のアルゴリズムのにおいて，頻度を数えるれば終了する．また，レベルがの場合もここで終了する．という過程が特に計算量がかかる．そこで，その前後で選ばれたペアをそれぞれ新しいラベルを割り当てるが，で情報利得値の上界を用いた枝刈りを行い，それぞれグラフは書き換えない．そして，に戻る．「事前枝刈り」「事後枝刈り」と呼ぶ．「事前枝刈り」により頻度計算の負荷が軽減され，「事後枝刈り」により図 12 情報利得値の上界を用いた枝刈りを取り入れた次の擬似チャンキングステップにおける頻度計算の負法のアルゴリズム荷とメモリ使用量が軽減されることが期待できる．事前枝刈りは，ノードペアの頻度計算前にペアを構いては - であり，それから得られる情報利得値の上界成する各ノードを共に含むグラフ数からノードペアのは 3!-31 となる．したがって，3-31 であれ可能な最大の頻度を計算し，それに基づき情報利得値ば部分グラフは破棄される．これら ' つの枝刈りをの上界を計算する．図 * に事前枝刈りの例を示す．ペ取り入れた法のアルゴリズムを図 1 に示す．アの ' つの親ノード - ' を共に含むグラフの数は，図中に示されるようにクラスについては . 個，クラスについて ( 個である．そしてその値から計算した情報利得値の上界は 3!-.1 となる．したがっ評価実験て，それまでに抽出した部分グラフの情報利得の最大本実験では，擬似チャンクするペアの選定基準に，グ値をとしたとき，3-.1 であれば部分グラフをラフ中の部分グラフの出現頻度，または情報利得値を拡張しても情報利得値がを超えることがないので部用い，それぞれを用いた情報利得値の上界を用いた枝分グラフは破棄することができる．このように，事刈りを行わないもの，事前枝刈りのみ行うもの，事後前枝刈りは，対象となるペアの頻度計算をする必要が枝刈りのみ行うもの，両方の枝刈りを行うものの合計ない． 1 種類のアルゴリズムが利用可能な法を計算機これに対して事後枝刈りは，実際に計算されたノー（:;2 <: '-33=，> 2 ( " ?@2 4 ドペアの頻度を用いて情報利得値の上界を計算 A B 1!3）上に ==を用いて実装し，慢性肝炎し，であれば部分グラフを破棄する．図 + データセットおよび人工データセットに適用した．具に事後枝刈りの例を示す．実際に計算されたノードペ体的には，法のパラメータのうち，ビーム幅アの頻度は，クラスについては (，クラスにつ.

(66) . ". - 100 -.

(67) 表. '2 慢性肝炎データセットのグラフのサイズ. 表. (2 人工データセットのグラフのサイズ. . . .

(68). グラフ数. . . . 平均頂点数. . . . 平均頂点数. 最多頂点数. . . . 頂点数の合計頂点ラベル数. 最少頂点数. . . . 頂点数の合計. . . . グラフ数. 平均辺数. . 頂点ラベル数. . . 辺数の合計. . . . . . . . . . . . . . . . . 辺ラベル数. 最多辺数. . . . 基本部分グラフの種類. . . . 最少辺数. . . . 基本部分グラフの平均頂点数. . . . 辺数の合計. . . . 基本部分グラフの頂点ラベル数. . 基本部分グラフの平均辺数. . を ) に，頻度の閾値を 3 に固定し，繰り返し回数を )，-3，-) に変化させ，各アルゴリズムに関して，計算時間，抽出された部分グラフの種類，抽出された部分グラフの情報利得の最大値を観測した．. データの仕様. 本実験では，千葉大学医学部付属病院からご提供頂いた慢性肝炎データ &-'/，および特定の条件を満たすように作成した人工データを用いて実験を行った．以下に各データセットの仕様をまとめる．. 慢性肝炎データセットの仕様. 本実験ではインターフェロン（肝炎ウィルスを駆除する薬品）投与の効果の有無をデータセット中の患者を分類するクラスラベルとして用いた．その場合，インターフェロン投与の効果のあった患者のクラス（4 ）と，効果のなかった患者のクラス（C ）のデータ数はそれぞれ，(1 個と )* 個であり，これらのデータを，属性選択，検査値の揺らぎを表現する属性の追加（本実験では揺らぎに対する期間は ,3 日間とした），データ値の平均化・離散化を通して各患者ごとの表形式データに変換した後，さらに各表形式データをグラフ構造データに変換して用いた．グラフの変換においては，各検査項目（属性）をグラフの辺ラベル，その検査値（属性値）を対応する辺に接続される頂点のラベルとした．グラフ変換後のグラフサイズを表 ' にまとめる．なお，グラフ構造データへの変換の詳細は，&./ を参照されたい．.

(69) . 人工データセットの仕様. 本実験で用いた人工データセットは，ある一方のクラスにのみ情報利得値が最大となるような特. . . 基本部分グラフの辺ラベル数.

(70)

(71). . 平均辺数. 辺ラベル数. .

(72). . ノイズの種類. . . . ノイズの平均頂点数. . . . ノイズ頂点ラベル数ノイズの平均辺数ノイズの辺ラベル数. . 徴的な部分グラフ（以下，基本部分グラフと呼ぶ）をいくつか埋め込んだものである．さらに，ノイズとして両クラスに頻出な部分グラフを埋め込み，基本部分グラフの情報利得値が最大になるようにもう一方のクラスに基本部分グラフの頂点数を一つ減らした部分グラフを埋め込んでいる．作成した人工データセットのグラフサイズを表 ( にまとめる．. . 実験結果と考察. 慢性肝炎データセットに対する結果を図 ,，-3 に示す．図 , は，チャンキング指標を頻度にした場合の計算時間と抽出した部分グラフ中の情報利得の最大値の関係を，図 -3 は，チャンキング指標を情報利得値にした場合の計算時間と抽出した部分グラフ中の情報利得の最大値の関係を示している．両方の枝刈りを行うものは枝刈りを行わないものに比べて，同じ情報利得値を得るまでの計算時間が，チャンキング指標に頻度を用いた場合にはいずれのにおいても約 '3D減少し，チャンキング指標に情報利得値を用いた場合には 7 ) のときに約 )3D， 7 -3 のときに約 +)D， 7 -) のときに約 13D減少しており，大幅な時間計算量の削減が見られた．次に，人工データセットの結果を図 --，-' に示す．図 -- は，チャンキング指標を頻度にした場合の計算時間と抽出した部分グラフ中の情報利得の最大値の関係を，図 -' は，チャンキング指標を情報利得値にした場合の計算時間と抽出した部分グラフ中の情報利得の最大値の関係を示している．両方の枝刈りを行うものは枝刈りを行わないものに比べて，同じ情報利得値を得. - 101 -.

(73) 慢性肝炎データ（頻度）枝刈りなし. 事前枝刈り. 人工データ（頻度）. 事後枝刈り. 両方の枝刈り. 枝刈りなし. 0.116. 両方の枝刈り. 0.2. 0.112 N10. 情報利得の最大値. 情報利得の最大値. 事後枝刈り. 0.25. 0.114. N15. 0.11 0.108 N5. 0.106. N10. 0.15 N15. 0.1 0.05. 0.104 0.102. 事前枝刈り. 100. 1000. 10000. 0 1000. 100000. N5. 10000 計算時間（秒）. 計算時間（秒）. 図 ,2 肝炎データにおける計算時間と情報利得の最大値の関係（擬似チャンキング指標：頻度）. 図 --2 人工データにおける計算時間と情報利得の最大値の関係（擬似チャンキング指標：頻度）人工データ（情報利得値）. 慢性肝炎データ（情報利得値）枝刈りなし. 事前枝刈り. 100000. 事後枝刈り. 枝刈りなし. 両方の枝刈り. 事前枝刈り. 事後枝刈り. 両方の枝刈り. 0.25. 0.2 0.18. 0.2 情報利得の最大値. 情報利得の最大値. 0.16 0.14 N10. N5. 0.12 0.1. N15. 0.08 0.06. N5. 0.15. N10 N15. 0.1 0.05. 0.04 0.02. 0. 0 10. 100. 1000. 10000. 計算時間（秒）. 図 -32 肝炎データにおける計算時間と情報利得の最大値の関係（擬似チャンキング指標：情報利得値）るまでの計算時間が，チャンキング指標に頻度を用いた場合には 7 ) のときに約 +3D， 7 -3 のときに約 1)D， 7 -) のときに約 ,3D減少し，チャンキング指標に情報利得値を用いた場合には 7 ) のときに約 ))D， 7 -3 と 7 -) のときに約 +)D減少しており，同様に大幅な時間計算量の削減が見られた．特に，チャンキング指標に頻度を用いた場合には，慢性肝炎データセットよりも大幅に計算時間が短縮される結果となった．チャンキング指標に頻度を用いた場合，事前枝刈りの効果は薄く，慢性肝炎データセットに対しては事前枝刈りの効果がまったくなく，逆に条件判定のコストのために計算時間が長くなってしまっている．この原因として，事前枝刈りは（擬似ノードを含む）ノードの頻度が低くなければ効果が出にくい点が上げられる．単一ノードは元々頻度が高い上に，頻度の高い順に擬似チャンキングされるため擬似ノードの頻度も高くなり，このような結果となったと考えられる．事前枝刈りの効果が，慢性肝炎データセットよりも人工データセットの方が高かったのは，人工データセットの頂点. 100. 1000 計算時間（秒）. 10000. 図 -'2 人工データにおける計算時間と情報利得の最大値の関係（擬似チャンキング指標：情報利得値）ラベル数と辺ラベル数がグラフ - 枚あたりの平均頂点数と平均辺数に比べて大きいため，単一ノード，および擬似ノードの頻度が低くなったためと考えられる．事後枝刈りの効果の差に関しても同様の原因が考えられる．しかし，事前枝刈りが頂点ラベル数のグラフ - 枚あたりの平均頂点数に対する比率が重要だったのに対し，ノードペアを構成する各ノードに比べてノードペアの頻度が低くなると事後枝刈りされやすいという観点から，辺ラベル数のグラフ - 枚あたりの平均辺数に対する比率が重要であると思われる．これらの考察をまとめると，チャンキング指標に関しては頻度より情報利得値の方が安定して枝刈りの効果を得ることができ，グラフの構造に関しては頂点ラベル数と辺ラベル数がグラフ - 枚あたりの平均頂点数と平均辺数に比べて大きい方が枝刈りの効果が大きくなるといえる．. - 102 -.

(74) #. まとめ. 5. .

(75) . .

(76) . .

(77) . . .

(78) . 1. C :

(79)

(80)

(81) . (.

(82) . ," -

(83) .

(84) " " /. ! . 4$-

(85) "

(86) " %*556) ( 7 8 9 : ; < . . " !# $ :

(87) ; 9 = 4 . 8

(88)

(89) -

(90) # " - > /66 ?$* 001265%*553). " % & ' " !( ! . 3 -

(91) 8" 9

(92) < . < "

(93)

(94)

(95) . / 35 ? 1 00. 1*$13( %*551). $ )Æ $# " % & * +))) < ;8 "

(96) 7 ; 40 . ;

(97) .

(98) + @

(99) .

(100)

(101) . / 6. ? & 00 51'$53 %*55() 9 < 8 < 9 :

(102) 9 . ' " # !# + . >" + *55* 00 (**$(*&. %*55*) '. + ' . <

(103) . <. -

(104) >" # &. -79$-7<+$-79. 4 0 8.

(105). >

(106) " 0 # + = 4 00**62*16 %*555) &. >. . ，;. ?.84

(107). . ，. ，

(108) . <. (!# >". #. *

(109) -@@@. -

(110) $. 00'(52'(A %*55*). 00*12*33 %&&(). A. -

(111) D.

(112)

(113)

(114) #

(115) "

(116) + <

(117)

(118) .%-+<*55*). . . ' . * +

(119) . 6. < "

(120) . 山口高平慢性肝炎データセットのクレンジングとマイニングの試み平成 1 年度科学研究費補助金特定領域 %) 研究成果報告書，情報洪水時代におけるアクティブマイニングの実現，00 *532** %*55*). %&'(). '256 %&'6). *.

(121) . 1 +

(122) . + " . ，/ ，00. !

(123) " #$. B8

(124)

(125)

(126)

(127) .. 参考文献 . <.

(128) ; 8#

(129)

(130) >8= %&&1). 本稿では，ある部分グラフの拡大グラフが取る情報利得値の上界が計算可能な点に着目し，法の探索を効率化するためにその上界を利用した枝刈り手法を提案した．提案手法は，法の部分グラフ抽出過程における頻度計算の負荷を軽減するとともに，不要な部分グラフを探索過程で破棄することでメモリ消費量も大幅に軽減できる．今後の課題としては，枝刈りの効果がデータに依存するため，多様な人工データを用いたより詳細な特性解析が必要である．また，実データにおいてより高い情報利得値をもつ部分グラフを効率的に探索するためには，今後，擬似チャンキングするペアの選定基準に関しても検討を重ねる必要がある．. . ./0(' % . B8

(131)

(132) . 9. #!+( $ , $ " )- ' " !# . >". # >;++ *553 0061&26(& %*553). - 103 -. ; :

(133) < . " + " ' . +'( # ," -

(134) .

(135) ". / A3 ? 00 612&* %&&3).

(136)