グラフ系列からの頻出変化パターンの高速列挙法

全文

(1)人工知能学会研究会資料 SIG-DMSM-A703-05 (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) . 27.

(30) C A. g (1). g ( 2). g ( 3). 図. "'. g ( 4). g (5). g (6). B. A. g s(1). 図. 28. A. g s( 2 ). グラフ変化系列の例. 人間関係ネットワーク，ホームページのネットワーク，遺伝子ネットワークなどの対象では，我々がそれらの時間変化を観測する時間分解能が高い．従って，隣接するグラフとでその構造が大きく変化することはなく，ごく一部の構造が変化すると考える．また，データから人にとって有用な知識を発見するデータマイニングの立場からは，計算機の出力が人にとって理解可能であることが重要である．理解可能な出力として何を重視するかは適用問題にも依存するが，一般に頂点間の関連性を見出せるグラフは人にとって理解し易いと考える．本稿が対象とする問題を解決するための " 点目の課題は，グラフ変化系列を如何に簡潔に表現し，同時に可能な表現の多様性を小さくすることで探索すべき空間を小さくするかである．図 " のとは，( 頂点からなる部分構造が共通であるので，各において全ての頂点，辺の情報の保持は簡潔な表現であるとはいえない．そこで本稿では，との差分に注目した記述によってグラフ変化系列を表すことを考える． ) 点目の課題は，どのような特徴をもつパターンを探索するかである．ここでパターンはからなるグラフの系列であり，各は入力グラフ系列を構成するの部分グラフとする．例えば，探索するグラフ系列の各グラフを制約のないグラフとした場合，探索すべきパターン数が膨大になり，さらに出力されたパターンを理解可能であるとは限らない．例えば，に非連結グラフを認めると図 ) のようなパターンが出力される可能性がある．図 ) をホームページのネットワーク構造だとした場合，頂点のとは鷲尾研究室のページ，はブラジルのある組織のホームページなど，至る所に存在しうる部分系列であるので，頻出パターンとして取り出される可能性が大きいが，とには何の関連もないために，このようなパターンの意味を理解することは一般には困難であり，人間の興味から外れる場合が多い．一方，各に於けるグラフが連結であると制約を課すと，図 ( のような系列はパターンをして探索の対象とならない．水色の頂点と黄色の頂点は各に於けるグラフ内で繋がっていないが，それらは緑色の頂点を介して何らかの関係があると理解でき，このようなパターンは探索の対象としたい．汎用性の観点からは，探索対象とするパターンはより制約が少ないパターンであるほうがよいと考えられる．このように，本稿が対象とする問題で探索すべきパターンも自明ではないために，パターンの定義についても議論を行う．ラベル付きグラフは * + , で定義され. C B. )'. 1. A. A. g s(1). ('. g s( 4 ). 理解困難なパターン 2. 2. B 1. A. g s(3). 2. 図. C B. B. B 3. 3. C. C. g s( 2 ). g. ( 3) s. グラフ系列パターン. る．ここで *

(31)

(32)

(33) は頂点集合， * +

(34)

(35) ,+

(36)

(37) , は辺集合，はラベル集合であり， ' + , である．本稿では無向グラフについて議論するが，提案手法は有向グラフにも適用可能である．グラフと * + , がを満たすような関数が存在するとき，をの部分グラフと呼び，と表す．頂点

(38) から

(39) に至る辺の集合をパスという．グラフの任意の ) 頂点間にパスがあるとき，そのグラフを連結グラフという．グラフ系列を * と表す．グラフの各頂点

(40) はユニーク - +

(41) , を持ち，ユニーク - は時間が経過しても変わらないものとする．本稿の目的は入力としてグラフの系列の集合が与えられたときに，頻出系列 * を探索・発見する手法を提案することである．ここで，"

(42)

(43) に対して， ½ ¾ であり，この時，と書く．. ホームページのネットワークは，各ページが頂点，例ハイパーリンクを辺とするグラフ構造である．グラフの構造は，編集されるたびに構造が変化する．例えば，はあるサイトにおける第期目のグラフ構造であり，がユニークに相当する．また，各ページはラベルを持たない頂点として扱ってもよいが，『大学のページ』，『金融系企業ページ』，『製造業企業ページ』などのようなラベルをもつ頂点として扱ってもよい．ラベルは分析の意図に応じて設定されるものであり，本稿では具体的に特定はしない．. ¾º¾ 和グラフどのようなパターンを探索するかについて議論するために和グラフ（. / ）を定義する．グラフ集合に対し * ¡¡¡ を. Ë. Ë. ¡¡¡ Ë ¡¡¡ . Ë. と定義する．ここで + ,， + , はそれぞれ，グラフの頂点集合，辺集合である． ¡¡¡ の頂点数はの頂点のユニーク - の異なり数になる．以上より本稿が対象とするパターンを以下のように定義する．パターンを * とすると .

(44) Ë. . ス中のグラフに誘導部分グラフとして含まれるという制約を課すと %/3)! が対象とした問題と同一である．. き， ¡¡¡ が連結であるグラフ系列を探索する．また，この条件を満たすグラフ系列に含まれる頂点は，0互いに関連している1 という．パターンに現れる各グラフは非連結かもしれないが，パターンに現れる任意の ) 頂点は，対象とする期間で互いに関連しているので，出力されるパターン全てが可読（理解可能）であり，先に述べた目的に反しない．本稿ではパターン列挙法に主眼をおき，その効率の良い列挙法について提案する．入力データベースはグラフ系列とデータ識別子の集合として， * とする．このよう + , * なデータベースに対し，支持度を +, * + , ¼ と定義する．指定された閾値以上の支持度をもつパターンを頻出パターンと呼ぶ．. ¾º¿ グラフ変更操作オペレータ.

(45) . パターン列挙問題グラフ系列 ¼ 集合 * + , * とが入力として与えられた時，¡¡¡ が連結な頻出パターン * を全て列挙することである． . グラフの変化を表現するために，グラフの編集距離を決める手法の " つを用いてとの差分のみを保持する．具体的には，) グラフの類似度は頂点，辺の追加，削除，ラベルの変更を ) グラフが同一なるまで繰り返し適用した最短数により決められる．表 " の 5 種の操作を変更操作オペレータと呼ぶ．とその後の差分を保持するのも１つの手ではあるが，を頂点数がゼロのグラフだと考え，との差分を含め，データを保持することで，データを統一的にあつかう．以後，をと表す．各グラフが比較的大きな場合でも，その変更箇所が少なければ，簡潔にデータを保持できる 2. 2. B A (0) [ vi ,1, A ]. OP. 2. B A. g. (1) [ vi , 3,C ]. (1) s. OP. g. A. B. 3. 1. C ( 2) s. 2. B. 3. 1. 1. C. ( 2) [ ed ,(1, 2 ), − ]. 2. B. 3. C. OP. 3. C. ( 2) [ vd ,1, A ]. ( 2) [ ei , ( 2 , 3), − ]. OP. OP. g. ( 3) s. OP[ vi( 0,)2, B ]. . パターンであるグラフの系列を構成する各グラフは必ずしも連結であるとは限らない．パターン列挙アルゴリズムとして最も単純な方法は，非連結グラフも出力する頻出部分グラフ列挙アルゴリズムを動かし，各頻出部分グラフをアイテムとして既存の系列パターンマイニングを動作させ，和グラフが連結でないパターンを後処理で除く手法である．しかし，この方法では後処理の直前の段階で，和グラフが連結でないパターンが大量に得られるので非効率である．また，従来の系列パターンマイニング 2! のように時間順にアイテムを " つずつ追加して拡張する方法を考える．取り出したいパターンが + , だとすると，，， + ,， + ,， + , と順にパターンを拡張していく．新たに追加されるアイテムは時間順にみて，最後に発生したアイテムが追加される．しかし，分析の対象がグラフの場合，頻出パターンの " つが図 ( であると事前に分かっていれば，図のに黄色の頂点を追加してを生成できる．一方， * が頻出で，を部分系列として含むパターンが全て非頻出の場合，黄色の頂点を加えたことで生成されるは和グラフが非連結でないので，この頂点を付け加えたことが無駄な処理となる．事前にどのようなパターンが頻出であるか分からない状態で探索するので，上記の目的を達成するには効率の良い探索手法が必要となる．既存の頻出部分グラフマイニング問題との関連を述べると，パターン列挙問題 " における系列長が全て " であれば，%/3(!，4#! などが対象とした問題と同一となる．また，系列長が " でかつ，和グラフが連結であるという制約を除き，パターンがデータベー. 29. OP[ ei( 0,)(1, 2), − ]. 図. . $'. グラフ変更操作オペレータによる系列表現. 例図のような系列を考える．図は図のように，頂点，辺の追加，削除の系列によって表すことができる．各頂点の右肩の数字は頂点のユニークを表している．このとき，グラフの変化を以下のように表すことができる．. . . . . . .

(46)

(47)

(48)

(49) .

(50)

(51)

(52) . データベース中のデータを *. で表すことをグラフ系列表記と呼び，. . . * . . . . . £ . . £ ½ ½ . . £ ¼ ¼ . £ ¼ ¼ で表すことを変更操作表記， £ を変更操作系列表記と呼ぶ．変更操作系列表記に，ある操作オペレータ £ が含まれるとき， £ と書き，グラフ系列表記 . に対する変更操作系列表記を +, と書く．変更操作系列表記 £ ¼ ¼ £ ½ ½ から幾つかのオペレータを除いて生成される系列 ¼ をの部分系列であると呼び，¼ で表す．¼ がの部分系列であり，そ ¼ の対応関係をで表す． £ と £ ¼ ¼ ¼ . が対応するとき， £ . *. ¼. + £ ¼ ¼ , である．. 変更操作オペレータは仮定編集距離から生成される．. . と . . の最短の . ½ ¾ と

(53) 従って，" つの変更操作表記中の ½ . ¾ . に対して，頂点を追加し，即座に削除というような * かつ * という値の組み合わせはないものとする． £ が変更操作系列表記 * £ ½ ½ 与えられたとき，に対する和グラフ * + , を.

(54)

(55) .

(56) . 頂点の追加.

(57) . 頂点の削除.

(58)

(59) . 頂点ラベルの変更辺の追加辺の削除辺ラベルの変更. . .

(60) .

(61)

(62)

(63)

(64)

(65)

(66)

(67)

(68)

(69)

(70)

(71)

(72) . 表. "'. グラフ変更操作オペレータ. 頂点ラベルをもつ頂点を

(73) に追加．追加された頂点のユニークはとする．追加された頂点は辺を持たない頂点となる．ユニークがである頂点を

(74) から削除．孤立した頂点のみを対象とする．.

(75) . 孤立していない頂点を削除する場合は，

(76) . を事前に数回適用する．. . ユニークがである頂点のラベルをに変更する．. ユニークがとである頂点間にラベルを持つ辺を

(77) に追加する．. ユニークがとである頂点間の辺を

(78) から削除．は削除される辺のラベル．ユニークがとである頂点間の辺のラベルをに変更する．. ¼¼.

(79)

(80) . の頂点を追加してグラフが生成されるとき，その追加の順序を以下のように入れ替えても同型のグラ ¼¼ フが生成される．.

(81)

(82) . . . と定義する．また， * + , * に対し，変更操作系列表記のパターンの支持度を +, * + , + , とする．.

(83) ¼ . ¼¼ .

(84)

(85)

(86) ½ ¼¼

(87)

(88) ¼ .

(89)

(90) ½

(91) ¾

(92) .

(93).

(94) . ¾. 頂点の追加頂点の削除ユニーク - がである頂点を追加し，続いてである頂点を削除する場合を考える． * の場合，この操作 ¼¼ が生成されるとき，その追加の順序を以下のよで ¼¼ うに入れ替えても同型のグラフが生成される．一方， * の場合は，追加した頂点を削除する操作であるので，順序を入れ替えることはできない． * +すなわち，追加した頂点を削除しない場合,. . パターン列挙問題グラフ系列の集合 * + , * と ¼ が入力として与えられた時，和グラフが連結であるグラフ変更操作系列表記の頻出パターン £ ½ ½ . £ を全て列挙することである．. . 定理グラフデータの系列の集合 * + , ¼ * とが与えられた時，パターン列挙問題，およびで出力される全パターンの集合をそれぞれ，とすると，である．.

(95) ¼ . ¼¼ .

(96). 定理支持度はパターンの系列長に対し，逆単調性の性質を持つ．.

(97) .

(98) ¼

(99)

(100)

(101) ½

(102) ¾

(103) .

(104) ¾

(105) .

(106) ¼¼ . ½. 不可頂点の削除頂点の追加ユニーク - がである頂点を削除し，次にである頂点を追加する．削除される頂点はユニーク - がでない頂点から選ばれるので，順序を入れ替え可能である．. 前述のように，本稿では可読なパターンでかつ，制約が少ない +汎用的な, パターンをマイニングすることを目的としている．変更操作系列表記の和グラフの定義より，変更操作系列表記の和グラフが連結であれば，変更操作系列表記中の ) 頂点

(107) と

(108) は関連しているといえる．従って，パターン列挙問題 ) で出力されるパターンは可読性がある．紙面の都合上証明は省略するが，定理 ) より，パターン列挙問題 " で出力されるパターンは，パターン列挙問題 ) で出力されるパターンに制約を課す（増やす）ことで出力可能である．よって，以降ではパターン列挙問題 ) について議論する．操作オペレータを定義した際，その適用順序の詳細までは議論しなかった．以下では，操作オペレータの可換性について述べる．ラベルの変更を含む性質は紙面の都合上省略するが同様に定義可能である．以下の説明で，

(109) ¼

(110) ¼¼ を前提とする．頂点の追加頂点の追加ユニーク - がとの頂点を追加する場合を考える．グラフにユニーク - がの頂点を追加し，続いて. 30. ¼. ¼¼ .

(111)

(112)

(113)

(114)

(115) ½ ¾.

(116). ¼¼ .

(117). ¼.

(118)

(119)

(120)

(121) ¾

(122) ½ . 頂点の追加辺の追加・削除辺の追加は，辺の削除は

(123) . で表. . . . されるが，ここでは辺の追加，及び削除をと表す． * かつ， * +すなわち，追加した頂点の辺を追加または削除しない場合,.

(124). ¼¼ . ¼.

(125)

(126) ¾

(127)

(128) ½

(129) . ¼¼ .

(130). ¼.

(131)

(132) ½

(133)

(134) ¾

(135) . 不可辺の追加・削除頂点の追加. ¼¼ .

(136).

(137) ¼ .

(138)

(139)

(140) ½ ¼ ¼¼

(141)

(142) .

(143)

(144) ½

(145) ¾

(146)

(147) . ¾.

(148) 1. 3. 1. 3. 2. 2. 4. g s(1). g s( 2 ). 図. '. 3. 2. 表. 3. 2. 4. g s(3). )'. 4. g s( 4 ). 出力パターンの一例. 頂点の削除頂点の削除. ¼¼ .

(149). ¼.

(150)

(151)

(152) ½

(153)

(154) ¾.

(155). ¼¼ .

(156) . .

(157) ¼ .

(158) ½

(159) ¾

(160) . 頂点の削除辺の追加・削除. ¼¼

(161) ¼

(162) .

(163)

(164) ¾

(165) ½

(166) ¼¼

(167)

(168) ¼ .

(169)

(170) ½

(171) ¾

(172) . 辺の追加，削除頂点の削除 * かつ * +追加した頂点の辺を追加，及び削除しない場合,. 表. ('. ¼¼

(173) ¼

(174) .

(175)

(176) ¾

(177) ½

(178) . ¼¼

(179)

(180) ¼ .

(181)

(182) ½

(183) ¾

(184) . 辺の追加・削除 . .

(185) .

(186) .

(187) .

(188) . .

(189)

(190) . .

(191)

(192) .

(193) . .

(194) .

(195) .

(196) .

(197) .

(198) . ¼¼

(199) ¼

(200) .

(201)

(202) ¾

(203) ½

(204) ¼¼

(205)

(206) ¼ .

(207)

(208) ½

(209) ¾

(210) .

(211). . . パターン列挙アルゴリズム. 前節で示したようにグラフの変化は操作オペレータによって表すことができる．またそれら操作の可換性について示した．パターン列挙アルゴリズムに関して，その詳細を示す前に具体例でイメージを示す．図を出力されるパターンの " つとすると，. . ｓ . . . . . . . .

(212)

(213)

(214)

(215) .

(216)

(217)

(218)

(219)

(220) .

(221)

(222)

(223) . . ，は

(224) 法ではなく，. #. . である．また異なるオペレータ順序によって / 5! のように，パス，根無し木，グラフの順にパターンを成長させることも可能である．以上のように提案手法はオペレータの入れ替えにより様々な既存の頻出グラフマイニング法を統合可能な非常に汎用的な手法である．変更操作系列表記の骨格 + 6, 系列 ¼ を . で表される．各オペレータの適用毎に分けて表したのが表 ) である．可換な範囲でこれらのオペレータの順序を入れ替えることを考える．入れ替えの " 例が表 ( であり，それを図示したのが図 5 である．これは " つの頂点の追加とそれに付随する幾つかの辺を " つのまとまりとしてグラフを徐々に拡張させる方法である．各オペレータの適用順に再度並び替えることで，元のグラフ変化系列パターン +", が得られる．一方，表 $，及び図 2 は " つの辺の追加，あるいは " つの辺の追加と頂点の追加を " つのまとまりとしてグラフを拡張させる方法である．適用順序などを無視した構造のみの成長のみに着目すると，前者は %/3(! のパターン成長であり，後者は 4#! のパターン成長法. の変更操作表記. 表 ) の変更操作オペレータの入れ替え +", . 不可辺の追加・削除. 図. .

(225) .

(226) .

(227) .

(228) . ｓ

(229) . .

(230) .

(231) .

(232) .

(233) .

(234) .

(235) .

(236) . . . ½ ¾ £ £ ½ ½ ¾ ¾ . . に対し，かつ . ½ * であるとき，は £ によって構 ½ ½ 成される ¼. の部分系列であると定義する．表 ( のから

(237) までで形成される操作オペレータ，及び表 $ のから

(238) までで形成される操作オペレータが，それぞれの系列の骨格である． 1. 4. g1 = OP[ vi(1,)4,red ] ⊥. 2. 4. g 2 = OP[ vi( 0,)2,blue ] g1 g 3 = OP[ ei( 2,)( 2, 4), − ] g 2. !! ". 図. 法であるが，ここではどちらもパターン成長という言葉を使う．. 31. 5'. 2. 1 4. 2. g 4 = OP[ vi( 0,)1,red ] g 3 g 6 = OP[ vi( 0,)3,blue ] g 5 ( 0) g 5 = OP[ ei( 0,)(1, 2 ), − ] g 4 g 7 = OP[ ei ,( 2,3), − ] g 6 g 8 = OP[ ei(1,)( 3, 4 ), − ] g 7. 表 ( のグラフ表記. 3. 4 (1) g 9 = OP[ ed ,( 2 , 3), − ] g 8 ( 2) g10 = OP[ ed ,(1, 2 ), − ] g 9 ( 2) g11 = OP[ vd ,1, red ] g10 g s( 4 ) = OP[ ei(3,)( 2,3), − ] g11.

(239) 3. 3. 3. 1. g1 = OP[ vi( 0,)3,blue ] ⊥. g 6 = OP[ vi(1,)4,red ] g 5. g 3 = OP[ ei( 0,)( 2,3), − ] g 2. g 5 = OP[ ei( 0,)(1, 2 ), − ] g 4. g 7 = OP[ ei( 2,)( 2, 4 ), − ] g 6. 2'. 4. 4. 1. 1. g 4 = OP[ vi( 0,)1,red ] g 3. ⊥. 2. 2. g 2 = OP[ vi( 0,)2,blue ] g1. 図. 3. 3. 2. 2. 表 $ のグラフ表記. ( 2) g11 = OP[ vd ,1, red ] g10. g1 = OP[ vi( 0,)1, A] ⊥ g1 = OP[ vi( 0,)1, A] ⊥ g1 = OP[ vi( 0,)1, A] ⊥. g s( 4 ) = OP[ ei( 3,)( 2,3), − ] g11 g = OP ( 0) g g = OP ( 0 ) g g = OP (1) g 2 [ vi , 2 , A ] 1 2 [ vi , 2 , A ] 1 2 [ vi , 2 , A ] 1 OP[ ei( 0,)(1, 2 ), − ] g 2. OP[ ei(1,)(1, 2 ), − ] g 2. . 定理変更操作系列表記であるパターンの和グラフとの骨格系列から得られる和グラフは同型である．以上より，変更操作系列表記で表される頻出パターンを得るための " つの手段として，の骨格系列 ¼ を生成し，¼ の和グラフを変えない範囲で ¼ に変更操作オペレータを加えて拡張していく方法が考えられる．実際，表 ( の以降，及び表 $ の以降の操作オペレータは，骨格の和グラフを変えない範囲でパターンを拡張していることが分かる．従って，はじめに取り出すべき全パターンの骨格系列を全列挙すること，. (0) OP[ ed ,1, B ] ⊥. g1 = OP[ vi(1,)1, A] ⊥. ... g. 2. = OP[ vi( 0,)2 , A] g1. OP[ ei( 2,)(1, 2 ), − ] g 2. 探索木の例. 間を示しているが，紙面の都合上省略する．頂点ラベルの種類はとの ) 種，辺ラベルの種類はの " 種とし，ラベル変更はないものとする．はじめに " 頂点のパターンから探索する．このとき，探索木のルートノードの子ノードとして，" 頂点で存在可能な全骨格パターン，

(240) ，，

(241) に相当するノードが生成される．パターン内の頂点のユニーク - は " からはじまる整数値とする．続いて，を拡張して，その子ノードを生成する．パターン拡張は，変更操作オペレータの適用順序が増えるように拡張するのではなく，骨格パターンの和グラフが連結であるように拡張する．拡張法が %/3 であれば，" つの頂点とそれに付随する辺を追加する．拡張法が，74/，4，/ のいずれかであれば，" つの辺とそれに付随する頂点で拡張する．骨格に既に含まれるをもつ変更操作オペレータでは拡張しない．注意すべきパターンとしては，.

(242)

(243)

(244)

(245) . 表 ) の変更操作オペレータの入れ替え +),. . . . である．パターン +), は， * 8 でラベルが，ユニーク - が " である頂点を追加し，同時に頂点対 +" ), に辺を追加する．続いて， * " でラベルが，ユニーク - が ) である頂点を追加するというパターンである．この情報だけをみると，ユニーク - が ) である頂点を追加する前に，辺 +" ), を追加しているため，辺の追加が不可能のように思える．しかし. .

(246) .

(247) .

(248) .

(249) .

(250)

(251) . .

(252)

(253)

(254)

(255) .

(256) .

(257)

(258) .

(259) . 骨格系列の拡張.

(260) .

(261) . ¿º½. &'. . 骨格系列の和グラフを変えない範囲で，骨格系列に含まれない操作オペレータを付け加えてパターンを順次拡張していくこと. $'. = OP[ vi( 0,)2 , A] g1.

(262)

(263) . の ) 点からなるアルゴリズムが考えられる．上記のステップ " で骨格系列の拡張操作を +, と書く．表. 2. OP[ ei(1,)(1, 2 ), − ] g 2. 図.

(264)

(265) ¼ ¼

(266) £

(267) £¼ ¼

(268)

(269) ¼

(270) £

(271) £¼ ¼ ¼ ¼

(272) £

(273) ¼ ¼ ¼ . g1 = OP[ vi( 0,)1, A] ⊥. ... g. OP[ ei( 0,)(1, 2 ), − ] g 2. . ). OP[ ei( 0,)1, B ] ⊥. ( 2) g10 = OP[ ed ,(1, 2 ), − ] g 9. 変更操作系列表記パターンとその骨格系列を定理 ¼ とし，その対応関係をとする．以下が満たされる．. ". (0) OP[ vd ,1, A ] ⊥. OP[ vi( 0,)1, A] ⊥. (1) g 8 = OP[ ei(1,)( 3, 4 ), − ] g 7 g 9 = OP[ ed ,( 2 , 3 ), − ] g 8.

(274)

(275)

(276)

(277)

(278) . . という部分系列が頻出であれば，支持度の逆単調性より，その部分系列であるパターン +), も頻出であるので，パターン +), も列挙する必要がある．また，パターン +(, はを拡張することで生成されたパターンであるが，ユニーク - が " である頂点の追加順序が変更されている．パターンの操作オペレータ £ のは，) つの操作オペレターの適用順序の情報を示すものであるので，このようにパターン中の操作オペレータの適用順序はパターンを拡張するに従って変更されうることに注意されたい．探索木の中で，同型のパターンが唯一現れるとは限らない．例えば，) つの系列. . .

(279)

(280)

(281)

(282)

(283)

(284) . 図 & は和グラフの頂点数が ) までの骨格系列を探索した探索木の一部を表している．図の三角形も探索空. 32. .

(285) は同型である．同型のパターンであるが表記が異なるパターンが何度も生成されると効率が悪くなる．この場合は，骨格パターンの和グラフとその頂点のユニーク - から生成されるグラフコードが正準形 + , であるときに，そのパターンを探索空間に残す．グラフコードは，骨格パターン拡張に %/3，4， 74/，/ などいずれの手法を使うかに依存する．. ¿º¾. となり，オペレータをアイテムとする系列パターンマイニングの系列表記と見なすことができる．入力データ集合と骨格パターンより ¼+, * + ¼ ,+ , + ¼ , !++ , , を生成し，系列パターンマイニングの入力とすることで，骨格系列の和グラフを変えない範囲で，パターンを順次拡張することができる．. ¿º¿ 擬似コード. 射影データからのパターン拡張. 前節で述べた手法を用いて骨格系列を生成し，続いて本節で述べるようにの和グラフを変えない範囲で，骨格系列に含まれない操作オペレータを加えて拡張していく．図 ( の

(286) まで，及び図 $ の

(287) までがパターンの骨格であり，本節では，以降の手続きについて説明する．ある骨格系列とそれを含むデータ + ,，その対応関係をとする．このとき，射影関数 ! を ¼ + , * !++ , , と定義する．ここで， ¼ は以下を満たす． ¼ はの部分系列である．. ¼

(288)

(289)

(290) £

(291) ¼ ¼ ¼ である ¼ は，

(292) £

(293) £

(294)

(295) に含まれる．

(296) £

(297) £ . 図 # に提案手法の擬似コードを示す．入力として，系列データの集合と支持度の閾値 ¼ を与える．2 行目で骨格系列を拡張する．# 行目で，骨格系列が正準形であるかをチェックする．これは 4 の擬似コードの「 * "+,」に相当する手続きである #!．列挙された骨格系列を用いて，" 行目で射影データを生成し，系列パターンマイニング手法を用いて，骨格系列の和グラフと同型な和グラフをもつ全パターンを列挙する．図 # は，幅優先探索でパターンを列挙する手法であるが，同様に深さ優先探索で列挙する手法も設計可能である．.

(298)

(299) である

(300)

(301) ，

(302) £

(303) £ £

(304) に対し， ¼ であるような

(305)

(306) ¼

(307) £ £¼ ¼ ¼ が存在するとき，

(308) ¼ である．. ¼ は上記を満たす上で，その系列長が極大である．. . 例ある骨格系列と系列データの変更操作系列表記が，それぞれ以下の式であるとする．. .

(309) . .

(310) . . . . . .

(311) . . . . .

(312) .

(313) .

(314)

(315)

(316)

(317)

(318)

(319)

(320)

(321)

(322)

(323)

(324)

(325)

(326)

(327) . .

(328) ¼ ¼ ¼. . .

(329)

(330)

(331)

(332)

(333)

(334)

(335)

(336) .

(337) . ¼ ¼ . . このとき !++ , , は，以下で表される．.

(338) ¼. .

(339) .

(340) .

(341) . ¼ Ｆ ¼ ¼ .

(342) . 図. . . #'. 幅優先探索による手法の擬似コード. 評価実験，考察前節までに述べた手法を. 9::で実装し，9;.. が. 9 - "55 /<，メモリが " /= の ;9 を用いて評. 操作オペレータの適用順序が同じ操作オペレータを括弧で括り，を除いて系列 +$, を記すと. 価実験を行った．系列パターンマイニングには ;42! を用いた．表は本実験で用いた人工データのパラメータの意味とその基本設定値を要約したものである．はじめに平均個の頂点をもつラベル付きグラフを.

(343)

(344)

(345)

(346)

(347)

(348)

(349)

(350)

(351) . 33.

(352) 90. '. 80. 実験データ作成用の基本設定値. パラメータ基本パターン選択確率データ選択確率基本パターンの平均ユニーク数データの平均ユニーク数頂点ラベル数辺ラベル数基本パターン数のデータ数辺の存在確率支持度の閾値. 70. デフォルト値

(353) ! ¼ !

(354) ¼ !

(355) ! " ! ¼ !. 計算時間[秒]. 表. 60 50 40 30 20 10 0. 10. 図. 15. ""'. 20 25 データの平均オペレータ数. 30. 35. ¼ の変化に対する計算時間の変化. 45 40. # 個生成する．頂点ラベルは個のラベルから等確率で，) 頂点間の辺存在確率はで決められる．これが基本パターンの和グラフとなる．各基本パターンについて，からはじめて，操作系列の和グラフが先に生成した和グラフと同型になるまで，変更操作オペレータを " つずつ加えていき，基本パターンの操作系列を生成する．オペレータは，頂点，辺の追加，削除のみとし，操作する頂点，辺をランダムに選択し，確率 ¼ で追加か，削除を決定する．の代わりに ¼ ，の ¼ 代わりにを用い，同様にして，個のグラフ系列を生成し，各 + , に対して基本パターンの " つを上書きする．結果の一部を図 "8，""，") に示す．図 "8 は，の変化に対する計算時間の変化である．データ数が増加すると計算時間はそれに比例することが分かる．図 "" は，¼ を変化させたときの計算時間の変化である．ただし，横軸は，系列中の平均オペレータ数を表している．¼ を減少させると，平均オペレータ数は増加し，計算時間は指数関数的に増加する．図 ") は， ¼ の変化に対する計算時間の変化である． ¼ を減少させると，計算時間は増加する．. . 計算時間[秒]. 35. 15. 0. 図. 0. ")'. 2. 4. 6. 8 10 支持度の閾値[%]. 12. 14. 16. ¼ の変化に対する計算時間の変化. タ特性の違いによる計算時間の変化を示した．. 参考文献 " # $ %&' $ () * %&+, -& % $ .& / .

(356) 0 "# % )+ % %1/ %&+, -& *2 (/ , 3+ .

(357)

(358) 0 . " # % )+ 4 5+ 6 7+, 8 9 -1 % * %&+, -& *2 :1 (/&+ $4 */ . 80 70. " # - ;,+ 8 3 ;< *2 (/&+ =< !

(359) . 0 "

(360) # 元田浩．明示的理解に魅せられて人工知能学会学会誌

(361) 0

(362) " # ( 7> 8 ? ;) % ) *2 (1 -& -) @ !

(363)

(364) 1

(365) "# ? A ABC(D -& (2 A /< ABC1A> 3'+ !

(366)

(367)

(368) 1 . 60 計算時間[秒]. 20. 5. 本稿は，ラベル付きグラフ系列に含まれる，可読な頻出変化グラフ系列パターン列挙法を提案した．グラフ変更操作オペレーションを定義し，その適用順序を入れ替えることで，効率良く列挙することを可能にした．人工データを用いて提案方法の評価実験を行い，デー. 50 40. "# 4 5+ 8 9 - ( + % 3+1 / -& "# $ E

(369) 7

(370) 0 . 30 20 10. 図. 25. 10. まとめ. 0. 30. 0. "8'. 10000. 20000 30000 データベース中のデータ数. 40000. "# F 6 8 ? 9 &(D 3+1G (/ A -& !

(371) 0 . 50000. の変化に対する計算時間の変化. . 34.

(372)