グラフ構造を有するデータから頻度の高い部分構造を抽出する方法、その装置およびプログラム
【課題】データベース中のグラフにおける互いに非連結な連結部分グラフ同士の関係を区別して頻度の高い組合せを抽出すること。
【解決手段】グラフデータベース中のグラフから同型性判定による頻度の高い部分構造をサブパターン候補として抽出してサブパターン記憶手段に保存し(s1)、サブパターン記憶手段2が保持するサブパターン候補の中からサブパターンを選択してサブパターン記憶手段2に保存し(s2)、グラフデータベース中のグラフにおいてサブパターン記憶手段が保持するサブパターンに該当しない箇所を匿名化および統合して縮約済グラフ記憶手段に保存し(s3)、縮約済グラフ記憶手段が保持するグラフから同型性判定による頻度の高い部分構造を連結グラフとして抽出して頻出部分構造記憶手段に保存し(s4)、頻出部分構造記憶手段が保持する連結グラフをその頻度とともに表示する(s5)。
【解決手段】グラフデータベース中のグラフから同型性判定による頻度の高い部分構造をサブパターン候補として抽出してサブパターン記憶手段に保存し(s1)、サブパターン記憶手段2が保持するサブパターン候補の中からサブパターンを選択してサブパターン記憶手段2に保存し(s2)、グラフデータベース中のグラフにおいてサブパターン記憶手段が保持するサブパターンに該当しない箇所を匿名化および統合して縮約済グラフ記憶手段に保存し(s3)、縮約済グラフ記憶手段が保持するグラフから同型性判定による頻度の高い部分構造を連結グラフとして抽出して頻出部分構造記憶手段に保存し(s4)、頻出部分構造記憶手段が保持する連結グラフをその頻度とともに表示する(s5)。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、大量のデータ、特にグラフ構造のデータを、計算機により分析する技術に関する。
【背景技術】
【0002】
大量のデータを計算機により分析し、そこに含まれる規則や例外を抽出・利用するための技術が広く提案され、利用されている。
【0003】
近年では特に、有機化合物やDNA、XML文書、HTML文書、ウェブサイトやソーシャルネットワークにおけるリンク関係、ソフトウェア開発におけるコンポーネントの依存関係など、ベクトルでは十分に表現しきれず、ツリーやグラフなどのより複雑なデータ構造が必要となるデータを対象とした分析も行われている。
【0004】
例えば、組織における顧客からの受注や社内での決裁、他企業への発注といった業務において、案件に対する見積書の作成や在庫の確認、納品日の通知などの様々な処理や、その処理で利用される業務システムに対するデータの入力や選択、ボタンのクリックといった操作の手順も、複数の利用者が連携し、並行して処理や操作を進める場合にはグラフとして表現される。
【0005】
図11に業務における処理や操作の手順を表現するグラフの一例を示す。この例は、ある受注案件に関して製品の見積書を発行する処理や操作の手順をグラフで表現したものである。図11では、操作1を実行し、その後、操作2〜5をこの順に実行し、操作2〜5の実行と並行して操作7〜8をこの順に実行し、操作8の完了後、操作9と操作10〜11を並行して実行し、操作5と操作9の完了を待って操作12を実行し、さらに操作11と操作12の完了を待って操作13〜14をこの順に実行し、操作14の完了後、操作3〜4を再度この順に実行し、操作4の完了後、操作6を実行したことが表現されている。
【0006】
このように処理や操作の手順はグラフとして表現されるため、処理や操作の手順を分析し、業務効率改善や業務監査を行う場合にも、グラフを対象とする分析が必要になる。
【0007】
[従来技術]
データに含まれる規則は、頻度の高いデータやデータ同士の関係と考えられ、また、データに含まれる例外はその規則から逸脱したデータやデータ同士の関係と考えられる。そのため、頻度の高いデータやデータ同士の関係を抽出することが必要であり、これは、特に分析対象のデータがツリーやグラフなどの複雑なデータ構造で表現される場合には、頻度の高い部分構造を抽出することに相当する。
【0008】
頻度の高い部分構造を抽出する手法の基本的な考え方は、
(1) 以下の(2)(3)においてパターンとして使用する着目する部分構造を決める、
(2) データベース中のデータ構造において、パターンに該当する部分構造の出現箇所を特定し、出現回数を数え、それをもとに頻度を算出する、
(3) 頻度の低いパターンを破棄し、頻度の高いパターンを残す。手法ごとに用意された何らかの終了条件を満たすまで、(1) に戻って処理を繰り返し、終了条件を満たした時点で残ったパターンを結果とする、
というものである。なお、適用領域によって、分析対象が多数のツリーやグラフの集合である場合も、1個の大規模なツリーやグラフである場合もあり得るが、特に限定せず、以下ではどちらも単にデータベースと呼ぶ。
【0009】
これまでに、小さなパターンから始め、頻度がなるべく高くなるようにパターンを連続的に拡大する処理を繰り返すことで、データベース中のグラフから頻度の高い連結部分グラフを抽出する手法が提案されている(非特許文献1〜5参照)。また、もとのグラフにおいて、複数の連結部分グラフが同じ組合せで多数出現するが、それら連結部分グラフ同士は互いに非連結で、その間の部分はグラフ中の出現箇所により異なり、そのためその間の部分も含めた大きな連結部分グラフの頻度が低い場合には、
互いに非連結な連結部分グラフの頻度の高い組合せを抽出すること…(※1)
が求められる。
【0010】
これを実現するため、頻度の高い連結した部分構造を連結グラフとして抽出するだけでなく、互いに非連結な連結部分グラフの頻度の高い組合せを、非連結部分グラフとして抽出する手法も提案されている(非特許文献6参照)。この手法では、例えば図3に示すノードと各ノード間を結ぶ有向リンクとからなる構成要素によってデータを図的に表現したグラフG0〜G4の中から、頻度の高い非連結部分グラフの一つとして図12に示すものが抽出される。この非連結部分グラフは、ノードa0〜a4で構成される頻度の高い連結部分グラフと、ノードa5〜a6で構成される頻度の高い連結部分グラフとの組合せである。
【0011】
なお、以下の説明では、図12の非連結グラフにおいてノードa0〜a4からなる連結グラフ、あるいはノードa5〜a6からなる連結グラフを、それぞれ「非連結(部分)グラフ中の連結(部分)グラフ」と呼ぶことにする。
【発明の概要】
【発明が解決しようとする課題】
【0012】
例えば業務における処理や操作は、実行順序が異なれば実行結果が異なるだけでなく、処理や操作の実行可否も変わってくる。そのためデータベース中の各グラフが、各案件に対する処理や操作の手順を表現していて、業務効率改善や業務監査の目的でこれらのグラフを分析する場合、途中に他の処理や操作を挟んで行われた、処理や操作あるいはそのまとまり(非連結部分グラフ中の連結部分グラフに相当)の組合せの頻度だけでなく、それらの順序関係を区別した頻度を知ることが重要である。
【0013】
例えば受注した製品の見積書を発行する業務において、図11のように製品価格の参照(操作9)を見積書の作成および送付(操作13〜14)の前に実行する手順の頻度が高い場合には問題ない。しかし、迅速性を重視するあまり、記憶を頼りに先に見積書を作成・送付してしまい、後で製品価格を参照して確認する手順の頻度が高い場合には、製品価格の更改時に誤った見積書を多数発行する危険性がある。そのため、これらの手順は区別して頻度を算出すべきである。
【0014】
あるいはソフトウェア開発において、コンポーネント間の依存関係の向きが異なれば、あるコンポーネントの変更に起因する他のコンポーネントの変更や再試験の要否が異なる。そのためデータベース中の各グラフが、各ソフトウェア開発プロジェクトにおけるコンポーネントの依存関係を表現していて、複数のプロジェクトで利用されているコンポーネントの変更が全プロジェクトに与える影響を分析する場合、他のコンポーネントを介して依存関係にある、コンポーネントあるいはそのまとまり(非連結部分グラフ中の連結部分グラフに相当)の組合せの頻度だけでなく、それらの間接的な依存関係の向きを区別した頻度を知ることが重要である。
【0015】
一方、従来の手法では(※1)を実現する上で、パターンおよびそれに該当するデータベース中のグラフの部分構造を、着目する部分構造だけからなる非連結グラフとして扱っている。そのため、パターンの出現回数を数える際、非連結部分グラフ中の連結部分グラフ同士がデータベース中のグラフにおいてどのような関係にあるかを区別できない。その結果、データベース中のグラフの異なる箇所に出現する非連結部分グラフがパターンと同型であれば、たとえ非連結部分グラフ中の連結部分グラフ同士の関係が異なっていても同じパターンとみなされ、全てそのパターンの出現回数として数えられる。
【0016】
例えばデータベース中のグラフが図3であるとき、図12に示す非連結グラフがグラフG0〜G4にそれぞれ1回ずつ、合計5回出現していることになる。しかし、図12の非連結グラフ中のノードa0〜a4からなる連結グラフとノードa5〜a6からなる連結グラフとの関係を区別して出現回数やそれをもとに算出される頻度を知ることはできない。そのため、ノードa0〜a4からなる連結グラフとノードa5〜a6からなる連結グラフとがどのような関係になっている場合が多いのかを知ることはできない。また、実際にはそれらの関係がまちまちで、それらの関係を区別するとそれぞれの頻度は低い可能性すらある。
【0017】
本発明では、以上の問題を解決するため、
データベース中のグラフにおける互いに非連結な連結部分グラフ同士の関係を区別して頻度の高い組合せを抽出すること…(※2)
を目的とする。
【0018】
例えばデータベース中のグラフが図3であるとき、図12のノードa0〜a4で構成される連結グラフとノードa5〜a6で構成される連結グラフとの関係には、図13の(a)に示すようにノードa4がノードa5の間接的な遷移元である場合(グラフG0〜G2の3回)、図13の(b)に示すようにノードa3がノードa5の間接的な遷移元である場合(グラフG3の1回)、図13の(c)に示すようにノードa6がノードa0の間接的な遷移元である場合(グラフG4の1回)、の3通りが存在する。従来の手法ではこれらを区別しないが、本発明ではこれらを区別する。
【0019】
なお、本発明は非循環有向グラフを分析対象とする。この場合、(※2)における「互いに非連結な連結部分グラフ同士の関係」とは、互いに非連結な連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性、つまり他のノードを経由しての遷移が可能かどうか、を意味する。また、ノードにはノードの種類や種別を表すラベルが付与されており、グラフの同型性判定時には、ノードと有向リンクからなる純粋なグラフ構造だけでなく、ノードに付与されているラベルも考慮するものとする。
【課題を解決するための手段】
【0020】
<概要>
頻度の高い部分構造を抽出する際、データベース中のグラフにおける互いに非連結な連結部分グラフ同士の関係を区別するためには、着目する部分構造だけでなく、それらを連結している、着目しない部分構造も考慮してパターンに該当するかどうかを判定する必要がある。
【0021】
そのため、本発明ではまず、背景技術の[従来技術]においてパターンを着目する部分構造とする代わりに、パターンおよびそれに該当するデータベース中のグラフの部分構造を、1個以上の下記(a)とこれらを連結する0個以上の下記(b)によって構成される連結グラフとして扱う。
(a) 着目する部分構造(以下、サブパターン)に相当する連結グラフ
(b) 着目しない部分構造に相当する連結グラフ
また、データベース中のグラフの部分構造がパターンに該当するかどうかを判定する際には、サブパターンが同型であり、かつサブパターンに含まれるノード間における到達可能性、つまり着目しない部分構造を経由して遷移が可能かどうか、が一致している場合に「該当する」とみなし、そうでない場合には「該当しない」とみなす。なお、ここではこの基準による判定を該当判定と呼ぶ。
【0022】
しかし、データベース中のグラフの部分構造がパターンに該当するかどうかを判定する際に、パターンと部分構造の同型性をそのまま判定すると、たとえサブパターンが同型であり、かつサブパターンに含まれるノード間における到達可能性が一致していたとしても、着目しない部分構造の差異により同型ではないと判定されてしまう。従って、サブパターン同士を連結する着目しない部分構造を、ノードのラベルだけでなく構造的にもワイルドカードとして置換しておくことで、その差異が同型性の判定に影響しないようにする必要がある。
【0023】
本発明では、サブパターン同士の関係を区別しつつ、それらを連結する着目しない部分構造の差異を区別しないようにするため、最初にデータベース中のグラフにおいてサブパターンに該当しない箇所を特許文献1におけるノードの匿名化および統合とほぼ同じ手法(相違点については後述)により縮約する。その上で同型の部分構造の出現回数が多く、それをもとに算出される頻度が高い部分構造を抽出する従来の手法を利用することで、結果的に該当判定による頻度の高い部分構造を抽出する。
【0024】
次に、サブパターンを決める方法について述べる。何らかの方法により(※2)を実現し、該当判定による頻度の高いパターンが抽出され、データベース中のグラフにおいてそれらのパターンに該当する部分構造の出現箇所が特定されているとすると、
・パターンに該当するデータベース中のグラフの部分構造は、1個以上の、下記(A) とこれらを連結する0個以上の下記(B)とによって構成される連結グラフになっている。
【0025】
(A) 同型の部分構造の出現回数が多く、それをもとに算出される頻度が高い(以下、同型性判定による頻度が高い)連結グラフ
(B) 同型の部分構造の出現回数が少なく、それをもとに算出される頻度が低い(以下、同型性判定による頻度が低い)連結グラフ
・データベース中のグラフにおける部分構造が、該当判定による頻度の高いパターンに該当するかどうかは、その部分構造に含まれる連結グラフのうち、同型性判定による頻度の高い連結グラフのみによって決まり、同型性判定による頻度の低い連結グラフにはよらない。
と考えられる。
【0026】
従って、本発明では、従来の手法などで抽出可能な、同型性判定による頻度の高い連結部分グラフをサブパターンとする。つまり上述の(A)を(a)とする。
【0027】
但し、実際には同型性判定による頻度の高い連結部分グラフが全て、該当判定による頻度の高い部分構造を抽出する上で着目すべき部分構造であるとは限らない。例えば、データベース中のグラフが、様々な案件に対する業務を行う際に、業務システムの端末に対して利用者が行った操作の手順を表現していて、その中から頻度の高い手順を知ろうとする場合において、端末に表示された業務システムのウィンドウの位置や大きさを変えるための一連の操作(マウスのクリックボタンを押下し、マウスの位置を移動し、マウスのクリックボタンを離す、など)の頻度が高いことがある。しかし、この一連の操作は、業務を遂行するためにどのような処理や操作をどのような手順で行っている場合が多いのかを知る上では重要ではなく、この一連の操作を表す部分構造は、サブパターンとしては不適切である。
【0028】
従って、本発明では、同型性判定による頻度の高い連結部分グラフの中から、サブパターンとして使用するものを利用者が繰り返し選択することもできるものとする。
【0029】
本発明では以下の手順により、サブパターンに該当しない箇所の縮約を挟んで同型性判定による頻度の高い部分構造の抽出を多段階で行うことで、互いに非連結な連結部分グラフの頻度の高い組合せを抽出する場合には、その関係を区別して頻度の高い部分構造を抽出する。
【0030】
(i) サブパターン候補の抽出
データベース中のグラフにおいて、同型性判定による頻度の高い連結グラフをサブパターン候補として、従来の手法などを利用して抽出する。
【0031】
(ii) サブパターンの選択
(i) の結果得られるサブパターン候補の連結グラフの中から、サブパターンとして使用するものを自動的または利用者からの指示により選択する。
【0032】
(iii) 着目しない部分構造の縮約
データベース中のグラフにおいて、サブパターンとして(ii)で選択された連結グラフに該当しない箇所を、特許文献1におけるノードの匿名化処理および統合処理とほぼ同じ方法により縮約する(但し、本発明におけるノードが特許文献1におけるアクティビティインスタンスに相当。詳細は後述する。)。
【0033】
(iv) 頻度の高い部分構造の抽出
(iii) の結果の得られるグラフにおいて、同型性判定による頻度の高い連結グラフを、従来の手法などを利用して抽出し、利用者に提示する。
【0034】
また、利用者の要望に応じて(ii)〜(iv) を繰り返し行うこともできる。
【発明の効果】
【0035】
本発明によれば、多数の、あるいは大規模な、ノードにラベルの付与された非循環有向グラフを対象として、頻度の高い部分構造を抽出できる。特に、頻度の高い連結した部分構造を連結グラフとして抽出するだけでなく、互いに非連結な連結部分グラフの頻度の高い組合せをそれらの関係、つまり連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性を区別して抽出できるようになる。
【0036】
さらに本発明を、業務効率改善や業務監査を目的とした、処理や操作の手順の分析に適用する場合には、途中に他の処理や操作を挟んで行われた、処理や操作あるいはそのまとまりの組合せの頻度を、それらの順序関係を区別して算出し、頻度の高い操作手順を抽出できる。これにより効果の高い業務効率改善や、精度の高い業務監査につながる。
【0037】
あるいは本発明を、例えばソフトウェア開発におけるコンポーネント変更の影響評価を目的とした、コンポーネント間の依存関係の分析に適用する場合には、他のコンポーネントを介して依存関係にある、コンポーネントあるいはそのまとまりの組合せの頻度を、それらの依存関係の向きを区別して算出し、頻度の高い依存関係を抽出できる。これによりコンポーネントを変更した場合の影響を高い精度で把握でき、変更するコンポーネントの選択や変更内容を適切に決定することで、開発コストの低減につながる。
【図面の簡単な説明】
【0038】
【図1】本発明の部分構造抽出装置の実施の形態の一例を示す構成図
【図2】本発明の部分構造抽出方法の実施の形態の一例を示すフローチャート
【図3】グラフデータベースが保持するデータの一例を示す図
【図4】サブパターン記憶手段が保持する内容(選択状態未設定)の一例を示す図
【図5】サブパターン記憶手段が保持する内容(選択状態設定済)の一例を示す図
【図6】サブパターン記憶手段が保持する内容(選択状態設定済)の一例を示す図
【図7】縮約済グラフ記憶手段が保持する内容の一例を示す図
【図8】縮約済グラフ記憶手段が保持する内容の一例を示す図
【図9】頻出部分構造記憶手段が保持する内容の一例を示す図
【図10】頻出部分構造記憶手段が保持する内容の一例を示す図
【図11】業務における処理や操作の手順を表現するグラフの一例を示す図
【図12】頻度の高い非連結部分グラフの一例を示す図
【図13】非連結な連結部分グラフ同士の関係の一例を示す図
【図14】着目する部分構造の候補の分割の一例を示す図
【図15】グラフG0における開始ノードから終了ノードまでの全ての経路を示す図
【図16】グラフG1における開始ノードから終了ノードまでの全ての経路を示す図
【図17】グラフG2における開始ノードから終了ノードまでの全ての経路を示す図
【図18】グラフG3における開始ノードから終了ノードまでの全ての経路を示す図
【図19】グラフG4における開始ノードから終了ノードまでの全ての経路を示す図
【図20】ノード列L0を処理した段階での擬似的な接尾辞木を示す図
【図21】全ノード列を処理した段階での擬似的な接尾辞木(その1)を示す図
【図22】全ノード列を処理した段階での擬似的な接尾辞木(その2)を示す図
【図23】部分ノード列の出現回数の一例を示す図
【図24】グラフ該当部分ノード列の再帰的な調査の一例を示す図
【図25】グラフデータベースが保持するグラフにおける経路を列挙する手順の一例を表すリスト1を示す図
【図26】擬似的な接尾辞木を作成する手順の一例を表すリスト2を示す図
【図27】中間頂点umの一意なグラフ該当部分ノード列を求める手順の一例を表すリスト3を示す図
【図28】全ての中間頂点に対するグラフ該当部分ノード列の数を再帰的に求める手順の一例を表すリスト4を示す図
【図29】中間頂点um<r>に対応するラベル列を保存する手順の一例を表すリスト5を示す図
【図30】頻度の高いラベル列に対応する全ての中間頂点のグラフ該当部分ノード列を保存する手順の一例を表すリスト6を示す図
【発明を実施するための形態】
【0039】
以下、前述した手順(i)〜(iv) を含む、本発明の構成要素およびその処理の詳細について説明する。
【0040】
<発明装置の構成および発明方法の処理手順>
図1は本発明の、グラフ構造を有するデータから頻度の高い部分構造を抽出する装置の構成の一例、ここでは周知のコンピュータ(計算機)上に実現された例を示すもので、図中、1はグラフデータベース、2はサブパターン記憶手段、3は縮約済グラフ記憶手段、4は頻出部分構造記憶手段、5は実行制御部、6はサブパターン候補抽出部、7はサブパターン選択部、8はグラフ縮約部、9は頻出部分構造抽出部、10は頻出部分構造表示部である。
【0041】
グラフデータベース1は、永続的にデータを保持する計算機内のハードディスクに記憶されているファイルまたはそのファイルからの読み書きを制御するデータベースマネジメントシステムである。また、サブパターン記憶手段2、縮約済グラフ記憶手段3および頻出部分構造記憶手段4は、計算機内のメモリ、あるいは計算機のハードディスクに記憶されているファイルまたはそのファイルからの読み書きを制御するデータベースマネジメントシステムである。なお、グラフデータベース1、並びに各記憶手段2〜4では、グラフ構造のデータを保持するが、グラフをどのようなデータ形式(図、XML文書などの構造データ、リレーションテーブルなど)で保持するのかについては限定しない。
【0042】
また、実行制御部5、サブパターン候補抽出部6、サブパターン選択部7、グラフ縮約部8、頻出部分構造抽出部9および頻出部分構造表示部10は、計算機内の演算装置で実行されるプログラムである。これらが全て一緒になった単一のプログラムなのか、全て別々のプログラムなのか、あるいはいくつかが1つのプログラムとなっているのかは、本発明では限定しない。さらにまた、以上の構成要素が同じ計算機内にあるか、あるいはネットワークを介して複数の計算機内にあるかについては、本発明では限定しない。
【0043】
本発明では、本発明装置の利用者が頻度の高い部分構造の抽出を指示する前に、グラフデータベース1にグラフ構造のデータが登録されているものとする。頻度の高い部分構造を抽出する際には、利用者が実行制御部5より分析の開始を指示し、サブパターン候補の抽出、サブパターンの選択、グラフの縮約、頻度の高い部分構造の抽出、頻度の高い部分構造の表示を、この順で実行する。また、利用者が実行制御部5より分析の再実行を指示した場合には、サブパターンの選択、グラフの縮約、頻度の高い部分構造の再抽出、頻度の高い部分構造の表示を、再度この順で実行する。利用者が実行制御部5より分析の終了を指示した場合には、処理を終了する。本発明の全体の処理フローを図2に示す。
【0044】
以下、各構成要素が保持する内容や、処理の手順の詳細、およびそれに従って本発明装置が利用されるときの例を説明する。
【0045】
〔発明装置の構成要素およびその処理の詳細〕
以下、各構成要素が保持する内容や、処理の詳細について説明する。
【0046】
≪グラフデータベース≫
グラフデータベース1は、分析対象となる多数のツリーやグラフの集合または1個の大規模なツリーやグラフ(以下、単にグラフ)を保持する。
【0047】
なお、本発明で対象とするグラフは、ノードにラベルの付与された、非循環有向グラフとする。またデータベース1中のグラフのノードには一意な識別子(0以上のノード番号)が付与されているものとし、本明細書ではノード番号iのノードをniと表す。さらに説明の都合上、ラベルには一意な識別子(0以上のラベル番号)が付与されているものとし、ラベル番号lのラベルをalと表し、ノード番号iのノードniに付与されたラベルのラベル番号はノード番号iの関数l(i)として表す。つまりノードniのラベルはal(i)と表現される。
【0048】
図3は、グラフデータベース1が保持する内容の一例である。
【0049】
≪サブパターン記憶手段≫
サブパターン記憶手段2は、サブパターン候補抽出部6により抽出される、同型性判定による頻度の高い連結グラフ(サブパターン候補)、グラフデータベース1が保持するグラフにおけるその連結グラフの該当箇所を特定する情報(以下、グラフ該当箇所情報)、並びに同じくサブパターン候補抽出部6により算出される、それぞれの連結グラフの出現回数および頻度を保持する。また、これらの連結グラフのうち、どれをサブパターンとして使用するかを、サブパターン選択部7により選択した結果も併せて保持する。
【0050】
グラフ該当箇所情報は、例えばノード番号の集合として保持することが考えられる。但し、他にも擬似的な接尾辞木(サブパターン候補抽出部6の実現手法の一例として後述)の中間頂点の番号のように、その情報からノード番号の集合を容易に得られるものであっても良く、限定しない。また、それぞれの連結グラフの頻度としては、サブパターン候補抽出部6を実現する、同型性判定による頻度の高い部分構造を抽出する手法により、出現回数をグラフデータベース1が保持するグラフの数で除した値を算出する場合、その代わりに部分構造の情報量などを算出する場合、あるいはそれらを含めた複数の値を算出する場合などが存在する。従って、頻度として複数の値を保持できるものとする。
【0051】
図4、図5、図6は、サブパターン記憶手段2が保持する内容の一例である。
【0052】
≪縮約済グラフ記憶手段≫
縮約済グラフ記憶手段3は、グラフデータベース1が保持するグラフにおいて、サブパターンとしてサブパターン記憶手段2が保持する連結グラフに該当しない箇所を、グラフ縮約部8により縮約した結果を保持する。
【0053】
図7、図8は、縮約済グラフ記憶手段3が保持する内容の一例である。
【0054】
≪頻出部分構造記憶手段≫
頻出部分構造記憶手段4は、頻出部分構造抽出部9により抽出される、縮約済グラフ記憶手段3が保持するグラフにおいて同型性判定による頻度の高い連結グラフ、並びに同じく頻出部分構造抽出部9により算出される、それぞれの連結グラフの出現回数および頻度を保持する。なお、サブパターン記憶手段2同様、それぞれの連結グラフの頻度として、複数の値を保持できるものとする。
【0055】
図9、図10は、頻出部分構造記憶手段4が保持する内容の一例である。
【0056】
≪実行制御部≫
実行制御部5は、利用者に分析の開始や再実行を、本発明装置を実現する計算機の入出力装置を介して指示させる。利用者から分析の開始が指示された場合(図2−s0)には、サブパターン候補抽出部6を呼び出し、その後、サブパターン選択部7、グラフ縮約部8、頻出部分構造抽出部9、頻出部分構造表示部10をこの順に、前の処理の完了を待って呼び出し、実行させる。また、利用者から分析の再実行が指示された場合(図2−s6)には、サブパターン選択部7を呼び出し、その後、グラフ縮約部8、頻出部分構造抽出部9、頻出部分構造表示部10をこの順に、前の処理の完了を待って呼び出し、実行させる。
【0057】
≪サブパターン候補抽出部≫
サブパターン候補抽出部6は、グラフデータベース1が保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその連結グラフの出現回数および頻度を算出し、その結果をグラフ該当箇所情報とともにサブパターン記憶手段2に保存する(図2−s1)。
【0058】
ここで、サブパターンの候補としては、頻度が高い、なるべく大きな(ノードを多数含む)連結グラフをそのまま抽出できることが望ましく、グラフを対象とした従来の抽出手法(例えば非特許文献1〜6参照)を利用することが考えられる。一方、サブパターン候補抽出部6では、グラフデータベース1が保持するグラフの中で、グラフ縮約部8において匿名化および統合しない部分構造の候補を抽出できれば良く、例えば図14の連結グラフG0を抽出する代わりに、ツリー構造でなるべく大きなグラフG0の部分構造T0とT1、あるいはリスト構造でなるべく大きなグラフG0の部分構造L0とL1、というように分割して抽出しても良い。従って、同型性判定に多くの計算量を要するグラフを対象とした抽出手法の代わりに、相対的に少ない計算量で処理可能な、ツリーを対象とした抽出手法、リスト(列)を対象とした抽出手法を利用することも考えられる。
【0059】
なお、抽出処理を調整するための、各抽出手法固有のパラメータについては、プログラムのパラメータとして予めコーディングされた値を用いる、本発明装置を実現する計算機のハードディスクに保存されたファイルで設定された値を用いる、サブパターン候補抽出部6の実行開始時に同計算機の入出力装置を介して利用者により設定された値を用いる、などが想定できるが、特に限定しない。
【0060】
本発明では、サブパターン候補抽出部6の処理を行う手法を特に限定しないが、同型性判定による頻度の高い部分構造を抽出する従来の手法をどのように利用できるかを示すため、リスト(列)を対象とした抽出手法の一例として、接尾辞木を利用する場合について具体的に説明する。
【0061】
なお、以下では‖N‖はグラフデータベース1が保持するグラフの全ノード数とする。またlist ← (x,list)、list ← (list,x) はリストlistのそれぞれ先頭、最後に要素xを追加する操作を、‖list‖はリストlistに含まれる要素の数を、list[pos]はリストlistのpos番目(最小は0)の要素を、list[startPos,endPos]はリストlistにおいてstartPos番目の要素からendPos番目の要素までの部分リストを表すものとする。さらにset0∪set1はセット(重複を許さない要素の集合)set0とset1の和集合を、set0∩set1はセットset0とset1の積集合を、
【0062】
【数1】
【0063】
はセットset0からset1に含まれる要素を除いた集合を、‖set‖はセットsetに含まれる要素の数を、set[pos]はセットsetのpos番目(最小は0)の要素を表すものとする。
【0064】
【数2】
【0065】
は空のリストまたはセットを表す。但し、リストにおける要素の並び順は要素の追加方法に従うが、セットにおける要素の並び順は必ずしも要素の追加順などになっていなくても良い。
【0066】
−グラフ中の経路の列挙−
グラフデータベース1が保持するグラフにおいて、親ノードを持たないノード(開始ノード)から子ノードを持たないノード(終了ノード)までの全ての経路をノード列(経路中のノードのノード番号のリスト)として列挙する。
【0067】
グラフ中の開始ノードを見つけ、そこからグラフの有向リンクに沿って終了ノードまでたどっていき、終了ノードが見つかったら直前の複数の子ノードを有するノードまで戻り、別の終了ノードまでたどることを繰り返すことで、ノード列を列挙する手順の一例を図25のリスト1に示す。
【0068】
例えば図3におけるグラフG0,G1,G2,G3,G4に対してノード列を列挙した結果は、それぞれ図15、図16、図17、図18、図19となる。
【0069】
−接尾辞木の作成−
列挙した全てのノード列を対象として、同型の部分構造、つまりノードのラベルを順に並べてできるラベル列が一致する部分ノード列の出現回数と出現箇所を特定できるようにするため、擬似的な接尾辞木を作成する。
【0070】
ここで、擬似的な接尾辞木は、全てのノード列の全ての接尾辞(ノード列の先頭から0個以上のノードを削除して得られる部分ノード列)のラベル列を木構造で表現したものである。但し、グラフデータベース1が保持するグラフの構成要素であるノードやリンクと、擬似的な接尾辞木の構成要素であるノードやリンクを区別するため、接尾辞木の構成要素であるノードを「頂点」、有向リンクを「枝」と呼ぶ。また説明の都合上、親の頂点と子の頂点の両方を有する頂点(中間頂点)には一意な識別子(0以上の頂点番号)が、子の頂点を持たない頂点(末端頂点)にはそれとは別の一意な識別子(0以上の頂点番号)が付与されるものとし、頂点番号がmの中間頂点をum、頂点番号がnの末端頂点をvnで表す。便宜上、親の頂点を持たない頂点(根頂点)は、頂点番号が−1の中間頂点u-1として扱う。さらに根頂点から各中間頂点までの経路中にある中間頂点の数(根頂点と自身を含めない)を、その中間頂点の階層数とする。便宜上、根頂点の階層数は−1とする。
【0071】
擬似的な接尾辞木の中間頂点はノードのラベルを保持する。これにより、任意のr階層目(但し、r≧0)の中間頂点um<r>について、根頂点から中間頂点um<r>までの経路中の中間頂点を階層数の小さい順にum<0>,um<1>,…,um<r-1>,um<r>、それぞれの中間頂点が保持するラベルをal<0>,al<1>,…,al<r-1>,al<r>とすると、根頂点から中間頂点um<r>までの経路、つまり頂点列(um<0>,um<1>,…,um<r-1>,um<r>)あるいは中間頂点um<r>自身は、ラベル列(al<0>,al<1>,…,al<r-1>,al<r>)と一対一に対応する。また末端頂点は、その末端頂点へ延びる枝を有する中間頂点に対応するラベル列が、どのノード列の何番目のノードから開始するのかを特定する情報(ノード列該当箇所情報)を保持する。具体的には、ノード列該当箇所情報は、ノード列の識別番号(0以上のノード列番号)と、そのノード列における接尾辞の開始位置(0以上の開始位置)の組である。
【0072】
列挙した全てのノード列についてノードを順に走査しながら、並行して接尾辞木の枝に沿ってノードのラベルを保持する頂点をたどり、あるいはそのような頂点がなければ作成することで、この擬似的な接尾辞木を作成する手順の一例を図26のリスト2に示す。
【0073】
例えば図15、図16、図17、図18、図19におけるノード列において、ノード列L0のみに対して擬似的な接尾辞木を作成した結果は図20、その後、引き続き残りのノード列に対して接尾辞木を作成した結果は図21、図22となる(図中の出現回数については後述)。但し、全てのノード列に対して作成した接尾辞木は紙面に比べて大きくなるため、図21、図22には、図20で図示した部分と0階層目の中間頂点u47を根とする部分木以外は、グラフデータベース1が保持するグラフにおいて該当箇所が2箇所以上あるラベル列に対応する中間頂点とその末端頂点に限り図示してある。
【0074】
−出現回数の算出−
接尾辞木の性質上、任意のr階層目(但し、r≧0)の中間頂点um<r>に対応するラベル列(al<0>,al<1>,…,al<r-1>,al<r>)は、中間頂点um<r>を根とする部分木の末端頂点が保持している、ノード列該当箇所情報によって示されるノード列およびその開始位置からr+1個の箇所に出現する。従って、中間頂点um<r>を根とする部分木の全ての末端頂点が保持するノード列該当箇所情報の数の合計が、ノード列におけるラベル列の出現回数となる。
【0075】
例えば図22において2階層目の中間頂点u185は、ラベル列(a8,a7,a5)に対応し、またu185を根とする部分木の末端頂点はv43,v49の2個であり、末端頂点v43にはノード列該当箇所情報(5,4)と(8,1)が、末端頂点v49にはノード列該当箇所情報(6,4)と(9,1)がそれぞれ保持されている。このことからラベル列(a8,a7,a5)は、5番目のノード列L5の4番目から3個の箇所、8番目のノード列L8の1番目から3個の箇所、6番目のノード列L6の4番目から3個の箇所、9番目のノード列L9の1番目から3個の箇所に出現していることがわかり(但し、開始位置はいずれも0番目始まりであることに注意)、ノード列におけるラベル列(a8,a7,a5)の出現回数は4回となる。
【0076】
しかし、ノード列はもともとグラフデータベース1が保持するグラフの開始ノードから終了ノードまでの経路を列挙して得たものであり、もとのグラフにおいて同一のノードや部分ノード列が異なるノード列に含まれる場合がある。そのため、ラベル列が一致する部分ノード列の出現回数をノード列ごとに別々に数え、足し合わせたのでは、別のノード列に含まれる共通の部分ノード列を重複して数えることになり、実際のグラフにおいてラベル列に該当する部分ノード列の出現回数よりも多くなってしまう。上述の例でも、5番目のノード列L5の4番目から3個の箇所、8番目のノード列L8の1番目から3個の箇所、6番目のノード列L6の4番目から3個の箇所、9番目のノード列L9の1番目から3個の箇所は、いずれもグラフG0中の部分ノード列(n17,n18,n14)であり、グラフデータベース1が保持するグラフにおいてラベル列(a8,a7,a5)が出現するのはこの1回だけある。
【0077】
このため、グラフデータベース1が保持するグラフにおいて各中間頂点に対応するラベル列に該当する部分ノード列(以下、単に中間頂点のグラフ該当部分ノード列と呼ぶ。)として一意なものを列挙し、その数によって各ラベル列の出現回数を求める必要がある。任意の中間頂点umについて、全ての枝の先にある中間頂点のグラフ該当部分ノード列を再帰的に調べ、また末端頂点が保持するノード列該当箇所情報から中間頂点umのグラフ該当部分ノード列を調べ、それらを合わせて一意な部分ノード列を求める手順の一例を図27のリスト3に示す。また0階層目の全ての中間頂点に対してリスト3を実行することで、1階層目以降も含めた全ての中間頂点についてグラフ該当部分ノード列の数を再帰的に求める手順の一例を図28のリスト4に示す。
【0078】
例えば、図22において0階層目の中間頂点u47に対してリスト3を実行した場合に、各中間頂点のグラフ該当部分ノード列は図24のようになり、これにより対応するラベル列の出現回数が求まる。また各中間頂点のグラフ該当部分ノード列の数を求めた結果を図21、図22中の各ノードの出現回数として、その階層別の和および総和を求めた結果を図23に示す。
【0079】
−頻度の算出と頻度の高いラベル列の判定−
ラベル列が一致する部分ノード列の出現回数をもとにラベル列の頻度を算出し、抽出手法固有のパラメータである頻度の閾値と比較して大きいラベル列を頻度の高いラベル列と判定して、算出した出現回数および頻度とともにサブパターン記憶手段2に保存する。
【0080】
ここで、ラベル列の単純な頻度としては、
(a) ラベル列が一致する部分ノード列の出現回数を、全部分ノード列の出現回数で除した値
(b) ラベル列が一致する部分ノード列の出現回数を、含まれるノード数が同じ部分ノード列の出現回数で除した値
が考えられる。
【0081】
また一般に、含まれるノード数が多くなるほど可能なラベル列の数が大きくなるため、この方法で算出した頻度では、含まれるノード数が多いラベル列の頻度は小さくなる傾向がある。そのため、
(c) (b)で求まる頻度を、ノードのラベルが無作為に付与されることを仮定した場合の想定の頻度で除した値(あるいはその対数値)
により、ノードのラベルが無作為に付与されることを仮定した場合に比べ、実際の単純な頻度がどの程度大きいのか、あるいは対数値をとった場合には、ラベル列が出現することの情報量がどの程度減少するのかを定量化し、それを頻度の値とすることなども考えられる。あるいは、これらの値のいくつかをそれぞれ算出し、抽出手法固有のパラメータであるそれぞれの対応する閾値と比較して大きいラベル列を頻度の高いラベル列だと判定することも考えられる。
【0082】
任意の中間頂点umに対応するラベル列について、上記(a)〜(c)の値はr=vertexRank[m]として以下により算出できる(但し、ノードのラベルの数を‖A‖とする)。なお、vertexRankは、図26のリスト2で使用されている各中間頂点の階層数のリストである。
【0083】
【数3】
【0084】
【数4】
【0085】
【数5】
【0086】
なお、vertexCount、rankCount、totalCountはそれぞれ、図28のリスト4で使用されている、各中間頂点のグラフ該当部分ノード列の数のリスト、長さ別の部分ノード列の数のリスト、全ての部分ノード列の数である。
【0087】
擬似的な接尾辞木の全ての中間頂点について、これらの値を算出し、抽出手法固有のパラメータとしてプログラム中にコーディング、または設定されたそれぞれの対応する閾値と比較することで、頻度の高いラベル列に対応する中間頂点が求まる。
【0088】
例えば図21の3階層目の中間頂点u12に対応するラベル列(a0,a1,a2,a3)の出現回数は5回であり、図23に示されているように全部分ノード列の出現回数は582回、3階層目の中間頂点のグラフ該当部分ノード列の出現回数の和は84回であり、ラベルはa0〜a9の10種類であるため、(a)の値は5/582、(b)の値は5/84、(c)の値(自然対数値)は4log10+log(5/84)≒6.39と算出される。
【0089】
なお、このようにして任意のr階層目(但し、r≧0)の中間頂点um<r>に対応するラベル列の頻度が高いと判定された際、実際にそのラベル列を求め、サブパターン記憶手段2に保存する手順については、その一例を図29のリスト5に示す。また上記(a)により算出した頻度の閾値を1/1000として、それを上回るラベル列とその出現回数、頻度をサブパターン記憶手段2に保存した例を図4の「候補番号」「連結グラフ」「出現回数」「頻度」欄に示す。
【0090】
−グラフデータベースが保持するグラフにおける該当箇所の保存−
頻度が高いと判定されたラベル列に対し、グラフデータベース1が保持するグラフにおいてそのラベル列に該当する部分ノード列を特定し、先に保存されているラベル列と対応付けてサブパターン記憶手段2に保存する。
【0091】
任意の中間頂点のグラフ該当部分ノード列を列挙する手順は既に述べたとおりであり、頻度が高いと判定されたラベル列に対応する中間頂点に対してこの手順を行う。ここでは、リスト5のように、頻度が高いと判定されたラベル列とその出現回数および頻度をサブパターン記憶手段2に保存する際に、そのラベル列に対応する中間頂点の頂点番号がセットfreqVertexSetに追加されているものとし、それに含まれる中間頂点に対してリスト3を実行することで、中間頂点のグラフ該当部分ノード列をグラフ該当箇所情報としてサブパターン記憶手段2に保存する手順の一例を図30のリスト6に示す。但し、freqVertexSetは階層数の小さい順に中間頂点の頂点番号を保持しているものとする。
【0092】
例えば、図22において0階層目の中間頂点u47を根とする部分木に含まれる任意の中間頂点が、仮に頻度が高いと判定されたラベル列に対応するとして、グラフ該当部分ノード列を列挙した結果を図24に示す。また頻度が高いと判定され、サブパターン記憶手段2に保存された図4のラベル列に対し、グラフにおける該当箇所を保存した結果を当該図4の「該当箇所(情報)」欄に示す。
【0093】
≪サブパターン選択部≫
サブパターン選択部7では、サブパターン記憶手段2が保持する連結グラフのうちサブパターンとして使用するものを選択し、その選択結果をサブパターン記憶手段2に保存する(図2−s2)。サブパターンの選択は、サブパターン記憶手段2が保持する内容を入力とし、選択結果を出力する、本発明装置を実現する計算機上で動作するプログラム中の関数(以下、サブパターン選択関数)により行う。
【0094】
本発明ではサブパターン選択関数の実現方法を特に限定しないが、その例としては、
・サブパターン候補抽出部6により算出される各連結グラフの出現回数cと各種頻度p0,p1,…に対し、プログラム中の別の関数(ここではφc,φ0,φ1,…とする)を適用して得られる評価値φc(c),φ0(p0),φ1(p1),…と、プログラムのパラメータとして予めコーディングされた、それぞれの閾値の値
【0095】
【数6】
【0096】
を比較し、例えば全ての評価値が閾値より大きい連結グラフのみ、サブパターンとして選択する、
・サブパターン候補抽出部6により算出される各連結グラフの出現回数cと各種頻度p0,p1,…に対し、プログラム中の別の関数(ここではψc,ψ0,ψ1,…とする)を適用して得られる評価値ψc(c),ψ0(p0),ψ1(p1),…の和ψc(c)+ψ0(p0)+ψ1(p1)+…を算出し、この値と、プログラムのパラメータとして予めコーディングされた閾値の値
【0097】
【数7】
【0098】
を比較し、例えば評価値の和が閾値より大きい連結グラフのみ、サブパターンとして選択する、
・上記関数において選択された連結グラフの中で、他の連結グラフの部分構造となっていない連結グラフのみ、サブパターンとして選択する。
【0099】
・上記関数を組合せ、どの関数においても選択される連結グラフのみ、サブパターンとして選択する、
などが考えられる。
【0100】
なお、上述の関数φc,φ0,φ1,…およびψc,ψ0,ψ1,…の例としては、
・プログラムのパラメータとして予めコーディングされた重みの値と、入力である出現回数あるいは頻度の値との積を算出する、
・サブパターン記憶手段2が保持する連結グラフ内における、出現回数あるいは頻度に関する順位(小さい順)を求め、それを連結グラフの数で除した値を算出する、
などが考えられる。
【0101】
この他、サブパターン選択関数としては、
・上述の各関数において、プログラムのパラメータとして予めコーディングされた値を用いる代わりに、本発明装置を実現する計算機のハードディスクに保存されたファイルで設定された値、あるいはサブパターン選択部7の実行開始時に同計算機の入出力装置を介して利用者により設定された値を用いる、
・本発明装置を実現する計算機の入出力装置を介して連結グラフを表現した図、その連結グラフの出現回数および頻度の値、並びに現在の選択状態を一覧として利用者に表示し、選択状態をトグルにより切り替えさせる、
なども考えられる。
【0102】
これらの関数で使用される閾値や重みなどのパラメータの値を変更する、あるいは適用する関数の組合せを変更することにより、サブパターン選択関数が変更される。
【0103】
例えば図4のサブパターン候補の連結グラフにおいて、プログラムあるいはファイルで頻度(a)の閾値が5/1000、頻度(c)の閾値が1.5、出現回数および頻度(b)の閾値が0と設定されている場合、候補番号10,22,23,24,30が選択され、さらにこれらの中で、他の連結グラフの部分構造となっていない連結グラフを選択すると、候補番号10の連結グラフは候補番号23の部分構造であり、候補番号23の連結グラフは候補番号30の連結グラフであるため、最終的に候補番号22,24,30の連結グラフが選択され、この選択結果が「選択状態」欄に反映される(図5)。
【0104】
≪グラフ縮約部≫
グラフ縮約部8では、グラフデータベース1が保持しているグラフと、サブパターン記憶手段2がサブパターンとして保持している連結グラフを読み込み、グラフデータベース1が保持するグラフにおいて、サブパターンの連結グラフに該当しない箇所を、特許文献1における匿名化処理により匿名化し、その後、特許文献1における統合処理により統合し、縮約済グラフ記憶手段3に保存する(図2−s3)。
【0105】
なお、特許文献1では、非循環有向グラフ(特許文献1における業務プロセスインスタンス)を分類する際に着目する部分としてノード(特許文献1におけるアクティビティインスタンス)に付与されたラベル(特許文献1における処理名)を利用者が指定し、指定されたラベルとは異なるラベルが付与されたノードのラベルを一律に匿名化する、つまり既存のラベルとは異なる同一のラベル(例えば
【0106】
【数8】
【0107】
)に変更している。
【0108】
一方、本発明では、サブパターン選択部7において1個のノードだけから構成される連結グラフがサブパターンとして選択されない限り、グラフデータベース1が保持しているグラフにおいてそのラベルが付与されたノードを一律に匿名化および統合の対象から除外することはしない。つまり、例えば図5において、候補番号22,24,30の連結グラフのみがサブパターンとして選択されていて、a0だけ、あるいはa1だけから構成される候補番号0,1の連結グラフがサブパターンとして選択されていない場合、図3のグラフのa0またはa1のラベルが付与されたノードのうち、匿名化および統合が除外されるのは候補番号22,24,30の連結グラフと同型の部分構造を構成するn1,n2,n22,n23,n37,n38,n48,n49,n63,n64のみで、それ以外のn0,n8,n25,n29,n41,n44,n52,n57,n62,n68は匿名化および統合の対象になる。
【0109】
また本発明では、グラフ縮約部8の前に実行されるサブパターン候補抽出部6およびサブパターン選択部7により、着目する部分構造が(半)自動的に決定される。
【0110】
例えばグラフデータベース1が保持するグラフが図3であり、サブパターン記憶手段2が保持しているサブパターンの選択結果が図5である(サブパターンとして選択されている連結グラフは候補番号22,24,30のみとする)場合、候補番号22,24,30の連結グラフに該当しないノードを匿名化し、その後、統合した結果は図7となる。ここで、例えば候補番号22の連結グラフに該当する箇所は、サブパターン記憶手段2が保持するグラフ該当箇所情報(図5の「該当箇所」欄)により、n14,n15,n31,n32,n45,n46,n53,n54,n60,n61であることがわかる。同様に、候補番号24,30の連結グラフに該当する箇所もわかる。これにより、サブパターンとして選択されたどの連結グラフにも該当しなかったノードが特定され、それらを対象に匿名化および統合が行われる。
【0111】
≪頻出部分構造抽出部≫
頻出部分構造抽出部9は、縮約済グラフ記憶手段3が保持するグラフを読み込み、グラフを対象とした、頻度の高い部分構造を抽出する従来の手法(例えば非特許文献1〜6)により、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に保存する(図2−s4)。
【0112】
なお、この抽出処理を調整する、各抽出手法固有のパラメータについては、プログラムのパラメータとして予めコーディングされた値を用いる、本発明装置を実現する計算機のハードディスクに保存されたファイルで設定された値を用いる、サブパターン候補抽出部6の実行開始時に同計算機の入出力装置を介して利用者により設定された値を用いる、などを想定するが、特に限定しない。
【0113】
例えば縮約済グラフ記憶手段3が保持しているグラフが図7である場合、これらに対して頻度の高い連結部分グラフを抽出する従来の手法を適用した結果は図9となる。但し、この例では頻度として、出現回数をグラフデータベース1中のグラフの数で除した値を用いている。
【0114】
≪頻出部分構造表示部≫
頻出部分構造表示部10は、利用者に、頻出部分構造記憶手段4が保持する連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する(図2−s5)。連結グラフとその出現回数および頻度を表示する方法としては、連結グラフを表示した図と、その連結グラフの出現回数および頻度の値とを一覧として表示することを想定しているが、特に限定しない。
【0115】
〔発明装置の利用例〕
以下、先に記載した本発明装置の構成要素の処理の詳細および具体的実現例に従って本発明装置が利用されるときの例を記載する。なお、いずれの場合も、本発明装置を用いて利用者が頻度の高い部分構造の抽出を指示する前にグラフデータベース1に図3で示されるグラフが保存されているものとする。
【0116】
≪利用例1≫
ステップs0:実行制御部5において利用者により分析の開始が指示される。
【0117】
ステップs1:実行制御部5からサブパターン候補抽出部6が呼び出される。サブパターン候補抽出部6では、図3に示したグラフデータベース1内の全ての部分ノード列について、同型の部分ノード列の出現回数を調べ、その値をもとに以下の値を算出する。
【0118】
(a) 同型の部分ノード列の出現回数を、全部分ノード列の出現回数で除した値
(b) 同型の部分ノード列の出現回数を、含まれるノード数が同じ部分ノード列の出現回数で除した値
(c) (b)で求まる頻度を、ノードのラベルが無作為に付与されることを仮定した場合の想定の頻度で除した値の自然対数値
その結果、(a)の値が1/1000を超える部分ノード列を、出現回数、頻度、グラフ該当箇所情報とともにサブパターン記憶手段2に図4の内容で保存する。
【0119】
ステップs2:実行制御部5からサブパターン選択部7が呼び出される。サブパターン選択部7では、プログラムあるいはファイルで頻度(a)の閾値が5/1000、頻度(c)の閾値が1.5、出現回数および頻度(b)の閾値が0と設定されている場合、図4の連結グラフの中から候補番号10,22,23,24,30が選択され、さらにこれらの中で他の連結グラフの部分構造となっていない連結グラフを選択すると、最終的に候補番号22,24,30の連結グラフが選択され、この選択結果がサブパターン記憶手段2の「選択状態」欄に反映される(図5)。
【0120】
ステップs3:実行制御部5からグラフ縮約部8が呼び出される。グラフ縮約部8では、グラフデータベース1が保持する図3のグラフについて、図5で選択されているサブパターンに該当しない箇所を縮約し、その結果を縮約済グラフ記憶手段3に図7の内容で保存する。
【0121】
ステップs4:実行制御部5から頻出部分構造抽出部9が呼び出される。頻出部分構造抽出部9では、縮約済グラフ記憶手段3が保持する図7の縮約済グラフに対して、頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に図9の内容で保存する。
【0122】
ステップs5:実行制御部5から頻出部分構造表示部10が呼び出される。頻出部分構造表示部10では、頻出部分構造記憶手段4が保持する図9の連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する。
【0123】
≪利用例2≫
あるいは、利用例1のステップs2以降について以下のようにする場合もある。
【0124】
ステップs2:実行制御部5からサブパターン選択部7が呼び出される。サブパターン選択部7において、(c)の閾値が2.0、それ以外の閾値は利用例1と同じ場合、図4の連結グラフの中から候補番号23,24,30が選択され(候補番号10,22は選択されない)、さらにこれらの中で他の連結グラフの部分構造となっていない連結グラフを選択すると、最終的に候補番号24,30の連結グラフのみが選択され、この選択結果がサブパターン記憶手段2の「選択状態」欄に反映される(図6)。
【0125】
ステップs3:実行制御部5からグラフ縮約部8が呼び出される。グラフ縮約部8では、グラフデータベース1が保持する図3のグラフについて、図6で選択されているサブパターンに該当しない箇所を縮約し、その結果を縮約済グラフ記憶手段3に図8の内容で保存する。
【0126】
ステップs4:実行制御部5から頻出部分構造抽出部9が呼び出される。頻出部分構造抽出部9では、縮約済グラフ記憶手段3が保持する図8の縮約済グラフに対して、頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に図10の内容で保存する。
【0127】
ステップs5:実行制御部5から頻出部分構造表示部10が呼び出される。頻出部分構造表示部10では、頻出部分構造記憶手段4が保持する図10の連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する。
【0128】
ステップs6:この例ではステップs5で利用者に表示されるのはいずれもa0〜a4からなる連結グラフであり、互いに非連結な連結部分グラフ同士がどのような組合せおよび順序で出現する頻度が高いのかを知ることはできない。そのため、実行制御部5において利用者により分析の再実行が指示される。
【0129】
ステップs2’:実行制御部5からサブパターン選択部7が呼び出される。サブパターン選択部7では、サブパターン記憶手段2が保持する図6の連結グラフ、出現回数、頻度および選択状態が、本計算機を実現する計算機の出力装置を介して表示される。候補番号22の連結グラフがサブパターンとして利用者に追加で選択されると、その結果をサブパターン記憶手段2に図5の内容で保存する。
【0130】
ステップs3’:実行制御部5からグラフ縮約部8が呼び出される。グラフ縮約部8では、グラフデータベース1が保持する図3のグラフについて、図5で選択されているサブパターンに該当しない箇所を縮約し、その結果を縮約済グラフ記憶手段3に図7の内容で保存する。
【0131】
ステップs4’:実行制御部5から頻出部分構造抽出部9が呼び出される。頻出部分構造抽出部9では、縮約済グラフ記憶手段3が保持する図7の縮約済グラフに対して、頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に図9の内容で保存する。
【0132】
ステップs5’:実行制御部5から頻出部分構造表示部10が呼び出される。頻出部分構造表示部10では、頻出部分構造記憶手段4が保持する図9の連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する。
【符号の説明】
【0133】
1:グラフデータベース、2:サブパターン記憶手段、3:縮約済グラフ記憶手段、4:頻出部分構造記憶手段、5:実行制御部、6:サブパターン候補抽出部、7:サブパターン選択部、8:グラフ縮約部、9:頻出部分構造抽出部、10:頻出部分構造表示部。
【先行技術文献】
【特許文献】
【0134】
【特許文献1】特開2010−55381号公報(「業務または作業における着目する処理の進め方に応じて案件を分類する方法、その装置およびプログラム」)
【非特許文献】
【0135】
【非特許文献1】吉田健一、元田浩、「推論過程からの概念学習(1)−類型的推論過程の抽出−」、人工知能学会誌、Vol.7、No.4、pp.675-685、1992.
【非特許文献2】L. B. Holder, D. J. Cook, S. Djoko, "Structure Discovery in the SUBDUE System", Proceedings of the 4th ACM SIGKDD Workshop on Knowledge Discovery and Data Mining (KDD) 1994, pp.169-180, 1994.
【非特許文献3】N. Vanetik, E. gudes, S. E. Shimony, "Computing Frequent Graph Patterns from Semistructured Data", Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM), pp.458-465, 2002.
【非特許文献4】X. Yan, J. Han, "gSpan: Graph-Based Substructure Pattern Mining", Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM), pp.721-724, 2002.
【非特許文献5】M. Kuramochi, G. Karypis, "An Efficient Algorithm for Discovering Frequent Subgraphs", IEEE Transactions on Knowledge and Data Engineering, Volume 16, Issue 9, pp.1038-1051, 2004.
【非特許文献6】A. Inokuchi, T. Wahio, H. Motoda, "Complete Mining of Frequent Patterns from Graphs: Mining Graph Data", Machine Learning, Volume 50, pp.321-354, 2003.
【技術分野】
【0001】
本発明は、大量のデータ、特にグラフ構造のデータを、計算機により分析する技術に関する。
【背景技術】
【0002】
大量のデータを計算機により分析し、そこに含まれる規則や例外を抽出・利用するための技術が広く提案され、利用されている。
【0003】
近年では特に、有機化合物やDNA、XML文書、HTML文書、ウェブサイトやソーシャルネットワークにおけるリンク関係、ソフトウェア開発におけるコンポーネントの依存関係など、ベクトルでは十分に表現しきれず、ツリーやグラフなどのより複雑なデータ構造が必要となるデータを対象とした分析も行われている。
【0004】
例えば、組織における顧客からの受注や社内での決裁、他企業への発注といった業務において、案件に対する見積書の作成や在庫の確認、納品日の通知などの様々な処理や、その処理で利用される業務システムに対するデータの入力や選択、ボタンのクリックといった操作の手順も、複数の利用者が連携し、並行して処理や操作を進める場合にはグラフとして表現される。
【0005】
図11に業務における処理や操作の手順を表現するグラフの一例を示す。この例は、ある受注案件に関して製品の見積書を発行する処理や操作の手順をグラフで表現したものである。図11では、操作1を実行し、その後、操作2〜5をこの順に実行し、操作2〜5の実行と並行して操作7〜8をこの順に実行し、操作8の完了後、操作9と操作10〜11を並行して実行し、操作5と操作9の完了を待って操作12を実行し、さらに操作11と操作12の完了を待って操作13〜14をこの順に実行し、操作14の完了後、操作3〜4を再度この順に実行し、操作4の完了後、操作6を実行したことが表現されている。
【0006】
このように処理や操作の手順はグラフとして表現されるため、処理や操作の手順を分析し、業務効率改善や業務監査を行う場合にも、グラフを対象とする分析が必要になる。
【0007】
[従来技術]
データに含まれる規則は、頻度の高いデータやデータ同士の関係と考えられ、また、データに含まれる例外はその規則から逸脱したデータやデータ同士の関係と考えられる。そのため、頻度の高いデータやデータ同士の関係を抽出することが必要であり、これは、特に分析対象のデータがツリーやグラフなどの複雑なデータ構造で表現される場合には、頻度の高い部分構造を抽出することに相当する。
【0008】
頻度の高い部分構造を抽出する手法の基本的な考え方は、
(1) 以下の(2)(3)においてパターンとして使用する着目する部分構造を決める、
(2) データベース中のデータ構造において、パターンに該当する部分構造の出現箇所を特定し、出現回数を数え、それをもとに頻度を算出する、
(3) 頻度の低いパターンを破棄し、頻度の高いパターンを残す。手法ごとに用意された何らかの終了条件を満たすまで、(1) に戻って処理を繰り返し、終了条件を満たした時点で残ったパターンを結果とする、
というものである。なお、適用領域によって、分析対象が多数のツリーやグラフの集合である場合も、1個の大規模なツリーやグラフである場合もあり得るが、特に限定せず、以下ではどちらも単にデータベースと呼ぶ。
【0009】
これまでに、小さなパターンから始め、頻度がなるべく高くなるようにパターンを連続的に拡大する処理を繰り返すことで、データベース中のグラフから頻度の高い連結部分グラフを抽出する手法が提案されている(非特許文献1〜5参照)。また、もとのグラフにおいて、複数の連結部分グラフが同じ組合せで多数出現するが、それら連結部分グラフ同士は互いに非連結で、その間の部分はグラフ中の出現箇所により異なり、そのためその間の部分も含めた大きな連結部分グラフの頻度が低い場合には、
互いに非連結な連結部分グラフの頻度の高い組合せを抽出すること…(※1)
が求められる。
【0010】
これを実現するため、頻度の高い連結した部分構造を連結グラフとして抽出するだけでなく、互いに非連結な連結部分グラフの頻度の高い組合せを、非連結部分グラフとして抽出する手法も提案されている(非特許文献6参照)。この手法では、例えば図3に示すノードと各ノード間を結ぶ有向リンクとからなる構成要素によってデータを図的に表現したグラフG0〜G4の中から、頻度の高い非連結部分グラフの一つとして図12に示すものが抽出される。この非連結部分グラフは、ノードa0〜a4で構成される頻度の高い連結部分グラフと、ノードa5〜a6で構成される頻度の高い連結部分グラフとの組合せである。
【0011】
なお、以下の説明では、図12の非連結グラフにおいてノードa0〜a4からなる連結グラフ、あるいはノードa5〜a6からなる連結グラフを、それぞれ「非連結(部分)グラフ中の連結(部分)グラフ」と呼ぶことにする。
【発明の概要】
【発明が解決しようとする課題】
【0012】
例えば業務における処理や操作は、実行順序が異なれば実行結果が異なるだけでなく、処理や操作の実行可否も変わってくる。そのためデータベース中の各グラフが、各案件に対する処理や操作の手順を表現していて、業務効率改善や業務監査の目的でこれらのグラフを分析する場合、途中に他の処理や操作を挟んで行われた、処理や操作あるいはそのまとまり(非連結部分グラフ中の連結部分グラフに相当)の組合せの頻度だけでなく、それらの順序関係を区別した頻度を知ることが重要である。
【0013】
例えば受注した製品の見積書を発行する業務において、図11のように製品価格の参照(操作9)を見積書の作成および送付(操作13〜14)の前に実行する手順の頻度が高い場合には問題ない。しかし、迅速性を重視するあまり、記憶を頼りに先に見積書を作成・送付してしまい、後で製品価格を参照して確認する手順の頻度が高い場合には、製品価格の更改時に誤った見積書を多数発行する危険性がある。そのため、これらの手順は区別して頻度を算出すべきである。
【0014】
あるいはソフトウェア開発において、コンポーネント間の依存関係の向きが異なれば、あるコンポーネントの変更に起因する他のコンポーネントの変更や再試験の要否が異なる。そのためデータベース中の各グラフが、各ソフトウェア開発プロジェクトにおけるコンポーネントの依存関係を表現していて、複数のプロジェクトで利用されているコンポーネントの変更が全プロジェクトに与える影響を分析する場合、他のコンポーネントを介して依存関係にある、コンポーネントあるいはそのまとまり(非連結部分グラフ中の連結部分グラフに相当)の組合せの頻度だけでなく、それらの間接的な依存関係の向きを区別した頻度を知ることが重要である。
【0015】
一方、従来の手法では(※1)を実現する上で、パターンおよびそれに該当するデータベース中のグラフの部分構造を、着目する部分構造だけからなる非連結グラフとして扱っている。そのため、パターンの出現回数を数える際、非連結部分グラフ中の連結部分グラフ同士がデータベース中のグラフにおいてどのような関係にあるかを区別できない。その結果、データベース中のグラフの異なる箇所に出現する非連結部分グラフがパターンと同型であれば、たとえ非連結部分グラフ中の連結部分グラフ同士の関係が異なっていても同じパターンとみなされ、全てそのパターンの出現回数として数えられる。
【0016】
例えばデータベース中のグラフが図3であるとき、図12に示す非連結グラフがグラフG0〜G4にそれぞれ1回ずつ、合計5回出現していることになる。しかし、図12の非連結グラフ中のノードa0〜a4からなる連結グラフとノードa5〜a6からなる連結グラフとの関係を区別して出現回数やそれをもとに算出される頻度を知ることはできない。そのため、ノードa0〜a4からなる連結グラフとノードa5〜a6からなる連結グラフとがどのような関係になっている場合が多いのかを知ることはできない。また、実際にはそれらの関係がまちまちで、それらの関係を区別するとそれぞれの頻度は低い可能性すらある。
【0017】
本発明では、以上の問題を解決するため、
データベース中のグラフにおける互いに非連結な連結部分グラフ同士の関係を区別して頻度の高い組合せを抽出すること…(※2)
を目的とする。
【0018】
例えばデータベース中のグラフが図3であるとき、図12のノードa0〜a4で構成される連結グラフとノードa5〜a6で構成される連結グラフとの関係には、図13の(a)に示すようにノードa4がノードa5の間接的な遷移元である場合(グラフG0〜G2の3回)、図13の(b)に示すようにノードa3がノードa5の間接的な遷移元である場合(グラフG3の1回)、図13の(c)に示すようにノードa6がノードa0の間接的な遷移元である場合(グラフG4の1回)、の3通りが存在する。従来の手法ではこれらを区別しないが、本発明ではこれらを区別する。
【0019】
なお、本発明は非循環有向グラフを分析対象とする。この場合、(※2)における「互いに非連結な連結部分グラフ同士の関係」とは、互いに非連結な連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性、つまり他のノードを経由しての遷移が可能かどうか、を意味する。また、ノードにはノードの種類や種別を表すラベルが付与されており、グラフの同型性判定時には、ノードと有向リンクからなる純粋なグラフ構造だけでなく、ノードに付与されているラベルも考慮するものとする。
【課題を解決するための手段】
【0020】
<概要>
頻度の高い部分構造を抽出する際、データベース中のグラフにおける互いに非連結な連結部分グラフ同士の関係を区別するためには、着目する部分構造だけでなく、それらを連結している、着目しない部分構造も考慮してパターンに該当するかどうかを判定する必要がある。
【0021】
そのため、本発明ではまず、背景技術の[従来技術]においてパターンを着目する部分構造とする代わりに、パターンおよびそれに該当するデータベース中のグラフの部分構造を、1個以上の下記(a)とこれらを連結する0個以上の下記(b)によって構成される連結グラフとして扱う。
(a) 着目する部分構造(以下、サブパターン)に相当する連結グラフ
(b) 着目しない部分構造に相当する連結グラフ
また、データベース中のグラフの部分構造がパターンに該当するかどうかを判定する際には、サブパターンが同型であり、かつサブパターンに含まれるノード間における到達可能性、つまり着目しない部分構造を経由して遷移が可能かどうか、が一致している場合に「該当する」とみなし、そうでない場合には「該当しない」とみなす。なお、ここではこの基準による判定を該当判定と呼ぶ。
【0022】
しかし、データベース中のグラフの部分構造がパターンに該当するかどうかを判定する際に、パターンと部分構造の同型性をそのまま判定すると、たとえサブパターンが同型であり、かつサブパターンに含まれるノード間における到達可能性が一致していたとしても、着目しない部分構造の差異により同型ではないと判定されてしまう。従って、サブパターン同士を連結する着目しない部分構造を、ノードのラベルだけでなく構造的にもワイルドカードとして置換しておくことで、その差異が同型性の判定に影響しないようにする必要がある。
【0023】
本発明では、サブパターン同士の関係を区別しつつ、それらを連結する着目しない部分構造の差異を区別しないようにするため、最初にデータベース中のグラフにおいてサブパターンに該当しない箇所を特許文献1におけるノードの匿名化および統合とほぼ同じ手法(相違点については後述)により縮約する。その上で同型の部分構造の出現回数が多く、それをもとに算出される頻度が高い部分構造を抽出する従来の手法を利用することで、結果的に該当判定による頻度の高い部分構造を抽出する。
【0024】
次に、サブパターンを決める方法について述べる。何らかの方法により(※2)を実現し、該当判定による頻度の高いパターンが抽出され、データベース中のグラフにおいてそれらのパターンに該当する部分構造の出現箇所が特定されているとすると、
・パターンに該当するデータベース中のグラフの部分構造は、1個以上の、下記(A) とこれらを連結する0個以上の下記(B)とによって構成される連結グラフになっている。
【0025】
(A) 同型の部分構造の出現回数が多く、それをもとに算出される頻度が高い(以下、同型性判定による頻度が高い)連結グラフ
(B) 同型の部分構造の出現回数が少なく、それをもとに算出される頻度が低い(以下、同型性判定による頻度が低い)連結グラフ
・データベース中のグラフにおける部分構造が、該当判定による頻度の高いパターンに該当するかどうかは、その部分構造に含まれる連結グラフのうち、同型性判定による頻度の高い連結グラフのみによって決まり、同型性判定による頻度の低い連結グラフにはよらない。
と考えられる。
【0026】
従って、本発明では、従来の手法などで抽出可能な、同型性判定による頻度の高い連結部分グラフをサブパターンとする。つまり上述の(A)を(a)とする。
【0027】
但し、実際には同型性判定による頻度の高い連結部分グラフが全て、該当判定による頻度の高い部分構造を抽出する上で着目すべき部分構造であるとは限らない。例えば、データベース中のグラフが、様々な案件に対する業務を行う際に、業務システムの端末に対して利用者が行った操作の手順を表現していて、その中から頻度の高い手順を知ろうとする場合において、端末に表示された業務システムのウィンドウの位置や大きさを変えるための一連の操作(マウスのクリックボタンを押下し、マウスの位置を移動し、マウスのクリックボタンを離す、など)の頻度が高いことがある。しかし、この一連の操作は、業務を遂行するためにどのような処理や操作をどのような手順で行っている場合が多いのかを知る上では重要ではなく、この一連の操作を表す部分構造は、サブパターンとしては不適切である。
【0028】
従って、本発明では、同型性判定による頻度の高い連結部分グラフの中から、サブパターンとして使用するものを利用者が繰り返し選択することもできるものとする。
【0029】
本発明では以下の手順により、サブパターンに該当しない箇所の縮約を挟んで同型性判定による頻度の高い部分構造の抽出を多段階で行うことで、互いに非連結な連結部分グラフの頻度の高い組合せを抽出する場合には、その関係を区別して頻度の高い部分構造を抽出する。
【0030】
(i) サブパターン候補の抽出
データベース中のグラフにおいて、同型性判定による頻度の高い連結グラフをサブパターン候補として、従来の手法などを利用して抽出する。
【0031】
(ii) サブパターンの選択
(i) の結果得られるサブパターン候補の連結グラフの中から、サブパターンとして使用するものを自動的または利用者からの指示により選択する。
【0032】
(iii) 着目しない部分構造の縮約
データベース中のグラフにおいて、サブパターンとして(ii)で選択された連結グラフに該当しない箇所を、特許文献1におけるノードの匿名化処理および統合処理とほぼ同じ方法により縮約する(但し、本発明におけるノードが特許文献1におけるアクティビティインスタンスに相当。詳細は後述する。)。
【0033】
(iv) 頻度の高い部分構造の抽出
(iii) の結果の得られるグラフにおいて、同型性判定による頻度の高い連結グラフを、従来の手法などを利用して抽出し、利用者に提示する。
【0034】
また、利用者の要望に応じて(ii)〜(iv) を繰り返し行うこともできる。
【発明の効果】
【0035】
本発明によれば、多数の、あるいは大規模な、ノードにラベルの付与された非循環有向グラフを対象として、頻度の高い部分構造を抽出できる。特に、頻度の高い連結した部分構造を連結グラフとして抽出するだけでなく、互いに非連結な連結部分グラフの頻度の高い組合せをそれらの関係、つまり連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性を区別して抽出できるようになる。
【0036】
さらに本発明を、業務効率改善や業務監査を目的とした、処理や操作の手順の分析に適用する場合には、途中に他の処理や操作を挟んで行われた、処理や操作あるいはそのまとまりの組合せの頻度を、それらの順序関係を区別して算出し、頻度の高い操作手順を抽出できる。これにより効果の高い業務効率改善や、精度の高い業務監査につながる。
【0037】
あるいは本発明を、例えばソフトウェア開発におけるコンポーネント変更の影響評価を目的とした、コンポーネント間の依存関係の分析に適用する場合には、他のコンポーネントを介して依存関係にある、コンポーネントあるいはそのまとまりの組合せの頻度を、それらの依存関係の向きを区別して算出し、頻度の高い依存関係を抽出できる。これによりコンポーネントを変更した場合の影響を高い精度で把握でき、変更するコンポーネントの選択や変更内容を適切に決定することで、開発コストの低減につながる。
【図面の簡単な説明】
【0038】
【図1】本発明の部分構造抽出装置の実施の形態の一例を示す構成図
【図2】本発明の部分構造抽出方法の実施の形態の一例を示すフローチャート
【図3】グラフデータベースが保持するデータの一例を示す図
【図4】サブパターン記憶手段が保持する内容(選択状態未設定)の一例を示す図
【図5】サブパターン記憶手段が保持する内容(選択状態設定済)の一例を示す図
【図6】サブパターン記憶手段が保持する内容(選択状態設定済)の一例を示す図
【図7】縮約済グラフ記憶手段が保持する内容の一例を示す図
【図8】縮約済グラフ記憶手段が保持する内容の一例を示す図
【図9】頻出部分構造記憶手段が保持する内容の一例を示す図
【図10】頻出部分構造記憶手段が保持する内容の一例を示す図
【図11】業務における処理や操作の手順を表現するグラフの一例を示す図
【図12】頻度の高い非連結部分グラフの一例を示す図
【図13】非連結な連結部分グラフ同士の関係の一例を示す図
【図14】着目する部分構造の候補の分割の一例を示す図
【図15】グラフG0における開始ノードから終了ノードまでの全ての経路を示す図
【図16】グラフG1における開始ノードから終了ノードまでの全ての経路を示す図
【図17】グラフG2における開始ノードから終了ノードまでの全ての経路を示す図
【図18】グラフG3における開始ノードから終了ノードまでの全ての経路を示す図
【図19】グラフG4における開始ノードから終了ノードまでの全ての経路を示す図
【図20】ノード列L0を処理した段階での擬似的な接尾辞木を示す図
【図21】全ノード列を処理した段階での擬似的な接尾辞木(その1)を示す図
【図22】全ノード列を処理した段階での擬似的な接尾辞木(その2)を示す図
【図23】部分ノード列の出現回数の一例を示す図
【図24】グラフ該当部分ノード列の再帰的な調査の一例を示す図
【図25】グラフデータベースが保持するグラフにおける経路を列挙する手順の一例を表すリスト1を示す図
【図26】擬似的な接尾辞木を作成する手順の一例を表すリスト2を示す図
【図27】中間頂点umの一意なグラフ該当部分ノード列を求める手順の一例を表すリスト3を示す図
【図28】全ての中間頂点に対するグラフ該当部分ノード列の数を再帰的に求める手順の一例を表すリスト4を示す図
【図29】中間頂点um<r>に対応するラベル列を保存する手順の一例を表すリスト5を示す図
【図30】頻度の高いラベル列に対応する全ての中間頂点のグラフ該当部分ノード列を保存する手順の一例を表すリスト6を示す図
【発明を実施するための形態】
【0039】
以下、前述した手順(i)〜(iv) を含む、本発明の構成要素およびその処理の詳細について説明する。
【0040】
<発明装置の構成および発明方法の処理手順>
図1は本発明の、グラフ構造を有するデータから頻度の高い部分構造を抽出する装置の構成の一例、ここでは周知のコンピュータ(計算機)上に実現された例を示すもので、図中、1はグラフデータベース、2はサブパターン記憶手段、3は縮約済グラフ記憶手段、4は頻出部分構造記憶手段、5は実行制御部、6はサブパターン候補抽出部、7はサブパターン選択部、8はグラフ縮約部、9は頻出部分構造抽出部、10は頻出部分構造表示部である。
【0041】
グラフデータベース1は、永続的にデータを保持する計算機内のハードディスクに記憶されているファイルまたはそのファイルからの読み書きを制御するデータベースマネジメントシステムである。また、サブパターン記憶手段2、縮約済グラフ記憶手段3および頻出部分構造記憶手段4は、計算機内のメモリ、あるいは計算機のハードディスクに記憶されているファイルまたはそのファイルからの読み書きを制御するデータベースマネジメントシステムである。なお、グラフデータベース1、並びに各記憶手段2〜4では、グラフ構造のデータを保持するが、グラフをどのようなデータ形式(図、XML文書などの構造データ、リレーションテーブルなど)で保持するのかについては限定しない。
【0042】
また、実行制御部5、サブパターン候補抽出部6、サブパターン選択部7、グラフ縮約部8、頻出部分構造抽出部9および頻出部分構造表示部10は、計算機内の演算装置で実行されるプログラムである。これらが全て一緒になった単一のプログラムなのか、全て別々のプログラムなのか、あるいはいくつかが1つのプログラムとなっているのかは、本発明では限定しない。さらにまた、以上の構成要素が同じ計算機内にあるか、あるいはネットワークを介して複数の計算機内にあるかについては、本発明では限定しない。
【0043】
本発明では、本発明装置の利用者が頻度の高い部分構造の抽出を指示する前に、グラフデータベース1にグラフ構造のデータが登録されているものとする。頻度の高い部分構造を抽出する際には、利用者が実行制御部5より分析の開始を指示し、サブパターン候補の抽出、サブパターンの選択、グラフの縮約、頻度の高い部分構造の抽出、頻度の高い部分構造の表示を、この順で実行する。また、利用者が実行制御部5より分析の再実行を指示した場合には、サブパターンの選択、グラフの縮約、頻度の高い部分構造の再抽出、頻度の高い部分構造の表示を、再度この順で実行する。利用者が実行制御部5より分析の終了を指示した場合には、処理を終了する。本発明の全体の処理フローを図2に示す。
【0044】
以下、各構成要素が保持する内容や、処理の手順の詳細、およびそれに従って本発明装置が利用されるときの例を説明する。
【0045】
〔発明装置の構成要素およびその処理の詳細〕
以下、各構成要素が保持する内容や、処理の詳細について説明する。
【0046】
≪グラフデータベース≫
グラフデータベース1は、分析対象となる多数のツリーやグラフの集合または1個の大規模なツリーやグラフ(以下、単にグラフ)を保持する。
【0047】
なお、本発明で対象とするグラフは、ノードにラベルの付与された、非循環有向グラフとする。またデータベース1中のグラフのノードには一意な識別子(0以上のノード番号)が付与されているものとし、本明細書ではノード番号iのノードをniと表す。さらに説明の都合上、ラベルには一意な識別子(0以上のラベル番号)が付与されているものとし、ラベル番号lのラベルをalと表し、ノード番号iのノードniに付与されたラベルのラベル番号はノード番号iの関数l(i)として表す。つまりノードniのラベルはal(i)と表現される。
【0048】
図3は、グラフデータベース1が保持する内容の一例である。
【0049】
≪サブパターン記憶手段≫
サブパターン記憶手段2は、サブパターン候補抽出部6により抽出される、同型性判定による頻度の高い連結グラフ(サブパターン候補)、グラフデータベース1が保持するグラフにおけるその連結グラフの該当箇所を特定する情報(以下、グラフ該当箇所情報)、並びに同じくサブパターン候補抽出部6により算出される、それぞれの連結グラフの出現回数および頻度を保持する。また、これらの連結グラフのうち、どれをサブパターンとして使用するかを、サブパターン選択部7により選択した結果も併せて保持する。
【0050】
グラフ該当箇所情報は、例えばノード番号の集合として保持することが考えられる。但し、他にも擬似的な接尾辞木(サブパターン候補抽出部6の実現手法の一例として後述)の中間頂点の番号のように、その情報からノード番号の集合を容易に得られるものであっても良く、限定しない。また、それぞれの連結グラフの頻度としては、サブパターン候補抽出部6を実現する、同型性判定による頻度の高い部分構造を抽出する手法により、出現回数をグラフデータベース1が保持するグラフの数で除した値を算出する場合、その代わりに部分構造の情報量などを算出する場合、あるいはそれらを含めた複数の値を算出する場合などが存在する。従って、頻度として複数の値を保持できるものとする。
【0051】
図4、図5、図6は、サブパターン記憶手段2が保持する内容の一例である。
【0052】
≪縮約済グラフ記憶手段≫
縮約済グラフ記憶手段3は、グラフデータベース1が保持するグラフにおいて、サブパターンとしてサブパターン記憶手段2が保持する連結グラフに該当しない箇所を、グラフ縮約部8により縮約した結果を保持する。
【0053】
図7、図8は、縮約済グラフ記憶手段3が保持する内容の一例である。
【0054】
≪頻出部分構造記憶手段≫
頻出部分構造記憶手段4は、頻出部分構造抽出部9により抽出される、縮約済グラフ記憶手段3が保持するグラフにおいて同型性判定による頻度の高い連結グラフ、並びに同じく頻出部分構造抽出部9により算出される、それぞれの連結グラフの出現回数および頻度を保持する。なお、サブパターン記憶手段2同様、それぞれの連結グラフの頻度として、複数の値を保持できるものとする。
【0055】
図9、図10は、頻出部分構造記憶手段4が保持する内容の一例である。
【0056】
≪実行制御部≫
実行制御部5は、利用者に分析の開始や再実行を、本発明装置を実現する計算機の入出力装置を介して指示させる。利用者から分析の開始が指示された場合(図2−s0)には、サブパターン候補抽出部6を呼び出し、その後、サブパターン選択部7、グラフ縮約部8、頻出部分構造抽出部9、頻出部分構造表示部10をこの順に、前の処理の完了を待って呼び出し、実行させる。また、利用者から分析の再実行が指示された場合(図2−s6)には、サブパターン選択部7を呼び出し、その後、グラフ縮約部8、頻出部分構造抽出部9、頻出部分構造表示部10をこの順に、前の処理の完了を待って呼び出し、実行させる。
【0057】
≪サブパターン候補抽出部≫
サブパターン候補抽出部6は、グラフデータベース1が保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその連結グラフの出現回数および頻度を算出し、その結果をグラフ該当箇所情報とともにサブパターン記憶手段2に保存する(図2−s1)。
【0058】
ここで、サブパターンの候補としては、頻度が高い、なるべく大きな(ノードを多数含む)連結グラフをそのまま抽出できることが望ましく、グラフを対象とした従来の抽出手法(例えば非特許文献1〜6参照)を利用することが考えられる。一方、サブパターン候補抽出部6では、グラフデータベース1が保持するグラフの中で、グラフ縮約部8において匿名化および統合しない部分構造の候補を抽出できれば良く、例えば図14の連結グラフG0を抽出する代わりに、ツリー構造でなるべく大きなグラフG0の部分構造T0とT1、あるいはリスト構造でなるべく大きなグラフG0の部分構造L0とL1、というように分割して抽出しても良い。従って、同型性判定に多くの計算量を要するグラフを対象とした抽出手法の代わりに、相対的に少ない計算量で処理可能な、ツリーを対象とした抽出手法、リスト(列)を対象とした抽出手法を利用することも考えられる。
【0059】
なお、抽出処理を調整するための、各抽出手法固有のパラメータについては、プログラムのパラメータとして予めコーディングされた値を用いる、本発明装置を実現する計算機のハードディスクに保存されたファイルで設定された値を用いる、サブパターン候補抽出部6の実行開始時に同計算機の入出力装置を介して利用者により設定された値を用いる、などが想定できるが、特に限定しない。
【0060】
本発明では、サブパターン候補抽出部6の処理を行う手法を特に限定しないが、同型性判定による頻度の高い部分構造を抽出する従来の手法をどのように利用できるかを示すため、リスト(列)を対象とした抽出手法の一例として、接尾辞木を利用する場合について具体的に説明する。
【0061】
なお、以下では‖N‖はグラフデータベース1が保持するグラフの全ノード数とする。またlist ← (x,list)、list ← (list,x) はリストlistのそれぞれ先頭、最後に要素xを追加する操作を、‖list‖はリストlistに含まれる要素の数を、list[pos]はリストlistのpos番目(最小は0)の要素を、list[startPos,endPos]はリストlistにおいてstartPos番目の要素からendPos番目の要素までの部分リストを表すものとする。さらにset0∪set1はセット(重複を許さない要素の集合)set0とset1の和集合を、set0∩set1はセットset0とset1の積集合を、
【0062】
【数1】
【0063】
はセットset0からset1に含まれる要素を除いた集合を、‖set‖はセットsetに含まれる要素の数を、set[pos]はセットsetのpos番目(最小は0)の要素を表すものとする。
【0064】
【数2】
【0065】
は空のリストまたはセットを表す。但し、リストにおける要素の並び順は要素の追加方法に従うが、セットにおける要素の並び順は必ずしも要素の追加順などになっていなくても良い。
【0066】
−グラフ中の経路の列挙−
グラフデータベース1が保持するグラフにおいて、親ノードを持たないノード(開始ノード)から子ノードを持たないノード(終了ノード)までの全ての経路をノード列(経路中のノードのノード番号のリスト)として列挙する。
【0067】
グラフ中の開始ノードを見つけ、そこからグラフの有向リンクに沿って終了ノードまでたどっていき、終了ノードが見つかったら直前の複数の子ノードを有するノードまで戻り、別の終了ノードまでたどることを繰り返すことで、ノード列を列挙する手順の一例を図25のリスト1に示す。
【0068】
例えば図3におけるグラフG0,G1,G2,G3,G4に対してノード列を列挙した結果は、それぞれ図15、図16、図17、図18、図19となる。
【0069】
−接尾辞木の作成−
列挙した全てのノード列を対象として、同型の部分構造、つまりノードのラベルを順に並べてできるラベル列が一致する部分ノード列の出現回数と出現箇所を特定できるようにするため、擬似的な接尾辞木を作成する。
【0070】
ここで、擬似的な接尾辞木は、全てのノード列の全ての接尾辞(ノード列の先頭から0個以上のノードを削除して得られる部分ノード列)のラベル列を木構造で表現したものである。但し、グラフデータベース1が保持するグラフの構成要素であるノードやリンクと、擬似的な接尾辞木の構成要素であるノードやリンクを区別するため、接尾辞木の構成要素であるノードを「頂点」、有向リンクを「枝」と呼ぶ。また説明の都合上、親の頂点と子の頂点の両方を有する頂点(中間頂点)には一意な識別子(0以上の頂点番号)が、子の頂点を持たない頂点(末端頂点)にはそれとは別の一意な識別子(0以上の頂点番号)が付与されるものとし、頂点番号がmの中間頂点をum、頂点番号がnの末端頂点をvnで表す。便宜上、親の頂点を持たない頂点(根頂点)は、頂点番号が−1の中間頂点u-1として扱う。さらに根頂点から各中間頂点までの経路中にある中間頂点の数(根頂点と自身を含めない)を、その中間頂点の階層数とする。便宜上、根頂点の階層数は−1とする。
【0071】
擬似的な接尾辞木の中間頂点はノードのラベルを保持する。これにより、任意のr階層目(但し、r≧0)の中間頂点um<r>について、根頂点から中間頂点um<r>までの経路中の中間頂点を階層数の小さい順にum<0>,um<1>,…,um<r-1>,um<r>、それぞれの中間頂点が保持するラベルをal<0>,al<1>,…,al<r-1>,al<r>とすると、根頂点から中間頂点um<r>までの経路、つまり頂点列(um<0>,um<1>,…,um<r-1>,um<r>)あるいは中間頂点um<r>自身は、ラベル列(al<0>,al<1>,…,al<r-1>,al<r>)と一対一に対応する。また末端頂点は、その末端頂点へ延びる枝を有する中間頂点に対応するラベル列が、どのノード列の何番目のノードから開始するのかを特定する情報(ノード列該当箇所情報)を保持する。具体的には、ノード列該当箇所情報は、ノード列の識別番号(0以上のノード列番号)と、そのノード列における接尾辞の開始位置(0以上の開始位置)の組である。
【0072】
列挙した全てのノード列についてノードを順に走査しながら、並行して接尾辞木の枝に沿ってノードのラベルを保持する頂点をたどり、あるいはそのような頂点がなければ作成することで、この擬似的な接尾辞木を作成する手順の一例を図26のリスト2に示す。
【0073】
例えば図15、図16、図17、図18、図19におけるノード列において、ノード列L0のみに対して擬似的な接尾辞木を作成した結果は図20、その後、引き続き残りのノード列に対して接尾辞木を作成した結果は図21、図22となる(図中の出現回数については後述)。但し、全てのノード列に対して作成した接尾辞木は紙面に比べて大きくなるため、図21、図22には、図20で図示した部分と0階層目の中間頂点u47を根とする部分木以外は、グラフデータベース1が保持するグラフにおいて該当箇所が2箇所以上あるラベル列に対応する中間頂点とその末端頂点に限り図示してある。
【0074】
−出現回数の算出−
接尾辞木の性質上、任意のr階層目(但し、r≧0)の中間頂点um<r>に対応するラベル列(al<0>,al<1>,…,al<r-1>,al<r>)は、中間頂点um<r>を根とする部分木の末端頂点が保持している、ノード列該当箇所情報によって示されるノード列およびその開始位置からr+1個の箇所に出現する。従って、中間頂点um<r>を根とする部分木の全ての末端頂点が保持するノード列該当箇所情報の数の合計が、ノード列におけるラベル列の出現回数となる。
【0075】
例えば図22において2階層目の中間頂点u185は、ラベル列(a8,a7,a5)に対応し、またu185を根とする部分木の末端頂点はv43,v49の2個であり、末端頂点v43にはノード列該当箇所情報(5,4)と(8,1)が、末端頂点v49にはノード列該当箇所情報(6,4)と(9,1)がそれぞれ保持されている。このことからラベル列(a8,a7,a5)は、5番目のノード列L5の4番目から3個の箇所、8番目のノード列L8の1番目から3個の箇所、6番目のノード列L6の4番目から3個の箇所、9番目のノード列L9の1番目から3個の箇所に出現していることがわかり(但し、開始位置はいずれも0番目始まりであることに注意)、ノード列におけるラベル列(a8,a7,a5)の出現回数は4回となる。
【0076】
しかし、ノード列はもともとグラフデータベース1が保持するグラフの開始ノードから終了ノードまでの経路を列挙して得たものであり、もとのグラフにおいて同一のノードや部分ノード列が異なるノード列に含まれる場合がある。そのため、ラベル列が一致する部分ノード列の出現回数をノード列ごとに別々に数え、足し合わせたのでは、別のノード列に含まれる共通の部分ノード列を重複して数えることになり、実際のグラフにおいてラベル列に該当する部分ノード列の出現回数よりも多くなってしまう。上述の例でも、5番目のノード列L5の4番目から3個の箇所、8番目のノード列L8の1番目から3個の箇所、6番目のノード列L6の4番目から3個の箇所、9番目のノード列L9の1番目から3個の箇所は、いずれもグラフG0中の部分ノード列(n17,n18,n14)であり、グラフデータベース1が保持するグラフにおいてラベル列(a8,a7,a5)が出現するのはこの1回だけある。
【0077】
このため、グラフデータベース1が保持するグラフにおいて各中間頂点に対応するラベル列に該当する部分ノード列(以下、単に中間頂点のグラフ該当部分ノード列と呼ぶ。)として一意なものを列挙し、その数によって各ラベル列の出現回数を求める必要がある。任意の中間頂点umについて、全ての枝の先にある中間頂点のグラフ該当部分ノード列を再帰的に調べ、また末端頂点が保持するノード列該当箇所情報から中間頂点umのグラフ該当部分ノード列を調べ、それらを合わせて一意な部分ノード列を求める手順の一例を図27のリスト3に示す。また0階層目の全ての中間頂点に対してリスト3を実行することで、1階層目以降も含めた全ての中間頂点についてグラフ該当部分ノード列の数を再帰的に求める手順の一例を図28のリスト4に示す。
【0078】
例えば、図22において0階層目の中間頂点u47に対してリスト3を実行した場合に、各中間頂点のグラフ該当部分ノード列は図24のようになり、これにより対応するラベル列の出現回数が求まる。また各中間頂点のグラフ該当部分ノード列の数を求めた結果を図21、図22中の各ノードの出現回数として、その階層別の和および総和を求めた結果を図23に示す。
【0079】
−頻度の算出と頻度の高いラベル列の判定−
ラベル列が一致する部分ノード列の出現回数をもとにラベル列の頻度を算出し、抽出手法固有のパラメータである頻度の閾値と比較して大きいラベル列を頻度の高いラベル列と判定して、算出した出現回数および頻度とともにサブパターン記憶手段2に保存する。
【0080】
ここで、ラベル列の単純な頻度としては、
(a) ラベル列が一致する部分ノード列の出現回数を、全部分ノード列の出現回数で除した値
(b) ラベル列が一致する部分ノード列の出現回数を、含まれるノード数が同じ部分ノード列の出現回数で除した値
が考えられる。
【0081】
また一般に、含まれるノード数が多くなるほど可能なラベル列の数が大きくなるため、この方法で算出した頻度では、含まれるノード数が多いラベル列の頻度は小さくなる傾向がある。そのため、
(c) (b)で求まる頻度を、ノードのラベルが無作為に付与されることを仮定した場合の想定の頻度で除した値(あるいはその対数値)
により、ノードのラベルが無作為に付与されることを仮定した場合に比べ、実際の単純な頻度がどの程度大きいのか、あるいは対数値をとった場合には、ラベル列が出現することの情報量がどの程度減少するのかを定量化し、それを頻度の値とすることなども考えられる。あるいは、これらの値のいくつかをそれぞれ算出し、抽出手法固有のパラメータであるそれぞれの対応する閾値と比較して大きいラベル列を頻度の高いラベル列だと判定することも考えられる。
【0082】
任意の中間頂点umに対応するラベル列について、上記(a)〜(c)の値はr=vertexRank[m]として以下により算出できる(但し、ノードのラベルの数を‖A‖とする)。なお、vertexRankは、図26のリスト2で使用されている各中間頂点の階層数のリストである。
【0083】
【数3】
【0084】
【数4】
【0085】
【数5】
【0086】
なお、vertexCount、rankCount、totalCountはそれぞれ、図28のリスト4で使用されている、各中間頂点のグラフ該当部分ノード列の数のリスト、長さ別の部分ノード列の数のリスト、全ての部分ノード列の数である。
【0087】
擬似的な接尾辞木の全ての中間頂点について、これらの値を算出し、抽出手法固有のパラメータとしてプログラム中にコーディング、または設定されたそれぞれの対応する閾値と比較することで、頻度の高いラベル列に対応する中間頂点が求まる。
【0088】
例えば図21の3階層目の中間頂点u12に対応するラベル列(a0,a1,a2,a3)の出現回数は5回であり、図23に示されているように全部分ノード列の出現回数は582回、3階層目の中間頂点のグラフ該当部分ノード列の出現回数の和は84回であり、ラベルはa0〜a9の10種類であるため、(a)の値は5/582、(b)の値は5/84、(c)の値(自然対数値)は4log10+log(5/84)≒6.39と算出される。
【0089】
なお、このようにして任意のr階層目(但し、r≧0)の中間頂点um<r>に対応するラベル列の頻度が高いと判定された際、実際にそのラベル列を求め、サブパターン記憶手段2に保存する手順については、その一例を図29のリスト5に示す。また上記(a)により算出した頻度の閾値を1/1000として、それを上回るラベル列とその出現回数、頻度をサブパターン記憶手段2に保存した例を図4の「候補番号」「連結グラフ」「出現回数」「頻度」欄に示す。
【0090】
−グラフデータベースが保持するグラフにおける該当箇所の保存−
頻度が高いと判定されたラベル列に対し、グラフデータベース1が保持するグラフにおいてそのラベル列に該当する部分ノード列を特定し、先に保存されているラベル列と対応付けてサブパターン記憶手段2に保存する。
【0091】
任意の中間頂点のグラフ該当部分ノード列を列挙する手順は既に述べたとおりであり、頻度が高いと判定されたラベル列に対応する中間頂点に対してこの手順を行う。ここでは、リスト5のように、頻度が高いと判定されたラベル列とその出現回数および頻度をサブパターン記憶手段2に保存する際に、そのラベル列に対応する中間頂点の頂点番号がセットfreqVertexSetに追加されているものとし、それに含まれる中間頂点に対してリスト3を実行することで、中間頂点のグラフ該当部分ノード列をグラフ該当箇所情報としてサブパターン記憶手段2に保存する手順の一例を図30のリスト6に示す。但し、freqVertexSetは階層数の小さい順に中間頂点の頂点番号を保持しているものとする。
【0092】
例えば、図22において0階層目の中間頂点u47を根とする部分木に含まれる任意の中間頂点が、仮に頻度が高いと判定されたラベル列に対応するとして、グラフ該当部分ノード列を列挙した結果を図24に示す。また頻度が高いと判定され、サブパターン記憶手段2に保存された図4のラベル列に対し、グラフにおける該当箇所を保存した結果を当該図4の「該当箇所(情報)」欄に示す。
【0093】
≪サブパターン選択部≫
サブパターン選択部7では、サブパターン記憶手段2が保持する連結グラフのうちサブパターンとして使用するものを選択し、その選択結果をサブパターン記憶手段2に保存する(図2−s2)。サブパターンの選択は、サブパターン記憶手段2が保持する内容を入力とし、選択結果を出力する、本発明装置を実現する計算機上で動作するプログラム中の関数(以下、サブパターン選択関数)により行う。
【0094】
本発明ではサブパターン選択関数の実現方法を特に限定しないが、その例としては、
・サブパターン候補抽出部6により算出される各連結グラフの出現回数cと各種頻度p0,p1,…に対し、プログラム中の別の関数(ここではφc,φ0,φ1,…とする)を適用して得られる評価値φc(c),φ0(p0),φ1(p1),…と、プログラムのパラメータとして予めコーディングされた、それぞれの閾値の値
【0095】
【数6】
【0096】
を比較し、例えば全ての評価値が閾値より大きい連結グラフのみ、サブパターンとして選択する、
・サブパターン候補抽出部6により算出される各連結グラフの出現回数cと各種頻度p0,p1,…に対し、プログラム中の別の関数(ここではψc,ψ0,ψ1,…とする)を適用して得られる評価値ψc(c),ψ0(p0),ψ1(p1),…の和ψc(c)+ψ0(p0)+ψ1(p1)+…を算出し、この値と、プログラムのパラメータとして予めコーディングされた閾値の値
【0097】
【数7】
【0098】
を比較し、例えば評価値の和が閾値より大きい連結グラフのみ、サブパターンとして選択する、
・上記関数において選択された連結グラフの中で、他の連結グラフの部分構造となっていない連結グラフのみ、サブパターンとして選択する。
【0099】
・上記関数を組合せ、どの関数においても選択される連結グラフのみ、サブパターンとして選択する、
などが考えられる。
【0100】
なお、上述の関数φc,φ0,φ1,…およびψc,ψ0,ψ1,…の例としては、
・プログラムのパラメータとして予めコーディングされた重みの値と、入力である出現回数あるいは頻度の値との積を算出する、
・サブパターン記憶手段2が保持する連結グラフ内における、出現回数あるいは頻度に関する順位(小さい順)を求め、それを連結グラフの数で除した値を算出する、
などが考えられる。
【0101】
この他、サブパターン選択関数としては、
・上述の各関数において、プログラムのパラメータとして予めコーディングされた値を用いる代わりに、本発明装置を実現する計算機のハードディスクに保存されたファイルで設定された値、あるいはサブパターン選択部7の実行開始時に同計算機の入出力装置を介して利用者により設定された値を用いる、
・本発明装置を実現する計算機の入出力装置を介して連結グラフを表現した図、その連結グラフの出現回数および頻度の値、並びに現在の選択状態を一覧として利用者に表示し、選択状態をトグルにより切り替えさせる、
なども考えられる。
【0102】
これらの関数で使用される閾値や重みなどのパラメータの値を変更する、あるいは適用する関数の組合せを変更することにより、サブパターン選択関数が変更される。
【0103】
例えば図4のサブパターン候補の連結グラフにおいて、プログラムあるいはファイルで頻度(a)の閾値が5/1000、頻度(c)の閾値が1.5、出現回数および頻度(b)の閾値が0と設定されている場合、候補番号10,22,23,24,30が選択され、さらにこれらの中で、他の連結グラフの部分構造となっていない連結グラフを選択すると、候補番号10の連結グラフは候補番号23の部分構造であり、候補番号23の連結グラフは候補番号30の連結グラフであるため、最終的に候補番号22,24,30の連結グラフが選択され、この選択結果が「選択状態」欄に反映される(図5)。
【0104】
≪グラフ縮約部≫
グラフ縮約部8では、グラフデータベース1が保持しているグラフと、サブパターン記憶手段2がサブパターンとして保持している連結グラフを読み込み、グラフデータベース1が保持するグラフにおいて、サブパターンの連結グラフに該当しない箇所を、特許文献1における匿名化処理により匿名化し、その後、特許文献1における統合処理により統合し、縮約済グラフ記憶手段3に保存する(図2−s3)。
【0105】
なお、特許文献1では、非循環有向グラフ(特許文献1における業務プロセスインスタンス)を分類する際に着目する部分としてノード(特許文献1におけるアクティビティインスタンス)に付与されたラベル(特許文献1における処理名)を利用者が指定し、指定されたラベルとは異なるラベルが付与されたノードのラベルを一律に匿名化する、つまり既存のラベルとは異なる同一のラベル(例えば
【0106】
【数8】
【0107】
)に変更している。
【0108】
一方、本発明では、サブパターン選択部7において1個のノードだけから構成される連結グラフがサブパターンとして選択されない限り、グラフデータベース1が保持しているグラフにおいてそのラベルが付与されたノードを一律に匿名化および統合の対象から除外することはしない。つまり、例えば図5において、候補番号22,24,30の連結グラフのみがサブパターンとして選択されていて、a0だけ、あるいはa1だけから構成される候補番号0,1の連結グラフがサブパターンとして選択されていない場合、図3のグラフのa0またはa1のラベルが付与されたノードのうち、匿名化および統合が除外されるのは候補番号22,24,30の連結グラフと同型の部分構造を構成するn1,n2,n22,n23,n37,n38,n48,n49,n63,n64のみで、それ以外のn0,n8,n25,n29,n41,n44,n52,n57,n62,n68は匿名化および統合の対象になる。
【0109】
また本発明では、グラフ縮約部8の前に実行されるサブパターン候補抽出部6およびサブパターン選択部7により、着目する部分構造が(半)自動的に決定される。
【0110】
例えばグラフデータベース1が保持するグラフが図3であり、サブパターン記憶手段2が保持しているサブパターンの選択結果が図5である(サブパターンとして選択されている連結グラフは候補番号22,24,30のみとする)場合、候補番号22,24,30の連結グラフに該当しないノードを匿名化し、その後、統合した結果は図7となる。ここで、例えば候補番号22の連結グラフに該当する箇所は、サブパターン記憶手段2が保持するグラフ該当箇所情報(図5の「該当箇所」欄)により、n14,n15,n31,n32,n45,n46,n53,n54,n60,n61であることがわかる。同様に、候補番号24,30の連結グラフに該当する箇所もわかる。これにより、サブパターンとして選択されたどの連結グラフにも該当しなかったノードが特定され、それらを対象に匿名化および統合が行われる。
【0111】
≪頻出部分構造抽出部≫
頻出部分構造抽出部9は、縮約済グラフ記憶手段3が保持するグラフを読み込み、グラフを対象とした、頻度の高い部分構造を抽出する従来の手法(例えば非特許文献1〜6)により、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に保存する(図2−s4)。
【0112】
なお、この抽出処理を調整する、各抽出手法固有のパラメータについては、プログラムのパラメータとして予めコーディングされた値を用いる、本発明装置を実現する計算機のハードディスクに保存されたファイルで設定された値を用いる、サブパターン候補抽出部6の実行開始時に同計算機の入出力装置を介して利用者により設定された値を用いる、などを想定するが、特に限定しない。
【0113】
例えば縮約済グラフ記憶手段3が保持しているグラフが図7である場合、これらに対して頻度の高い連結部分グラフを抽出する従来の手法を適用した結果は図9となる。但し、この例では頻度として、出現回数をグラフデータベース1中のグラフの数で除した値を用いている。
【0114】
≪頻出部分構造表示部≫
頻出部分構造表示部10は、利用者に、頻出部分構造記憶手段4が保持する連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する(図2−s5)。連結グラフとその出現回数および頻度を表示する方法としては、連結グラフを表示した図と、その連結グラフの出現回数および頻度の値とを一覧として表示することを想定しているが、特に限定しない。
【0115】
〔発明装置の利用例〕
以下、先に記載した本発明装置の構成要素の処理の詳細および具体的実現例に従って本発明装置が利用されるときの例を記載する。なお、いずれの場合も、本発明装置を用いて利用者が頻度の高い部分構造の抽出を指示する前にグラフデータベース1に図3で示されるグラフが保存されているものとする。
【0116】
≪利用例1≫
ステップs0:実行制御部5において利用者により分析の開始が指示される。
【0117】
ステップs1:実行制御部5からサブパターン候補抽出部6が呼び出される。サブパターン候補抽出部6では、図3に示したグラフデータベース1内の全ての部分ノード列について、同型の部分ノード列の出現回数を調べ、その値をもとに以下の値を算出する。
【0118】
(a) 同型の部分ノード列の出現回数を、全部分ノード列の出現回数で除した値
(b) 同型の部分ノード列の出現回数を、含まれるノード数が同じ部分ノード列の出現回数で除した値
(c) (b)で求まる頻度を、ノードのラベルが無作為に付与されることを仮定した場合の想定の頻度で除した値の自然対数値
その結果、(a)の値が1/1000を超える部分ノード列を、出現回数、頻度、グラフ該当箇所情報とともにサブパターン記憶手段2に図4の内容で保存する。
【0119】
ステップs2:実行制御部5からサブパターン選択部7が呼び出される。サブパターン選択部7では、プログラムあるいはファイルで頻度(a)の閾値が5/1000、頻度(c)の閾値が1.5、出現回数および頻度(b)の閾値が0と設定されている場合、図4の連結グラフの中から候補番号10,22,23,24,30が選択され、さらにこれらの中で他の連結グラフの部分構造となっていない連結グラフを選択すると、最終的に候補番号22,24,30の連結グラフが選択され、この選択結果がサブパターン記憶手段2の「選択状態」欄に反映される(図5)。
【0120】
ステップs3:実行制御部5からグラフ縮約部8が呼び出される。グラフ縮約部8では、グラフデータベース1が保持する図3のグラフについて、図5で選択されているサブパターンに該当しない箇所を縮約し、その結果を縮約済グラフ記憶手段3に図7の内容で保存する。
【0121】
ステップs4:実行制御部5から頻出部分構造抽出部9が呼び出される。頻出部分構造抽出部9では、縮約済グラフ記憶手段3が保持する図7の縮約済グラフに対して、頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に図9の内容で保存する。
【0122】
ステップs5:実行制御部5から頻出部分構造表示部10が呼び出される。頻出部分構造表示部10では、頻出部分構造記憶手段4が保持する図9の連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する。
【0123】
≪利用例2≫
あるいは、利用例1のステップs2以降について以下のようにする場合もある。
【0124】
ステップs2:実行制御部5からサブパターン選択部7が呼び出される。サブパターン選択部7において、(c)の閾値が2.0、それ以外の閾値は利用例1と同じ場合、図4の連結グラフの中から候補番号23,24,30が選択され(候補番号10,22は選択されない)、さらにこれらの中で他の連結グラフの部分構造となっていない連結グラフを選択すると、最終的に候補番号24,30の連結グラフのみが選択され、この選択結果がサブパターン記憶手段2の「選択状態」欄に反映される(図6)。
【0125】
ステップs3:実行制御部5からグラフ縮約部8が呼び出される。グラフ縮約部8では、グラフデータベース1が保持する図3のグラフについて、図6で選択されているサブパターンに該当しない箇所を縮約し、その結果を縮約済グラフ記憶手段3に図8の内容で保存する。
【0126】
ステップs4:実行制御部5から頻出部分構造抽出部9が呼び出される。頻出部分構造抽出部9では、縮約済グラフ記憶手段3が保持する図8の縮約済グラフに対して、頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に図10の内容で保存する。
【0127】
ステップs5:実行制御部5から頻出部分構造表示部10が呼び出される。頻出部分構造表示部10では、頻出部分構造記憶手段4が保持する図10の連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する。
【0128】
ステップs6:この例ではステップs5で利用者に表示されるのはいずれもa0〜a4からなる連結グラフであり、互いに非連結な連結部分グラフ同士がどのような組合せおよび順序で出現する頻度が高いのかを知ることはできない。そのため、実行制御部5において利用者により分析の再実行が指示される。
【0129】
ステップs2’:実行制御部5からサブパターン選択部7が呼び出される。サブパターン選択部7では、サブパターン記憶手段2が保持する図6の連結グラフ、出現回数、頻度および選択状態が、本計算機を実現する計算機の出力装置を介して表示される。候補番号22の連結グラフがサブパターンとして利用者に追加で選択されると、その結果をサブパターン記憶手段2に図5の内容で保存する。
【0130】
ステップs3’:実行制御部5からグラフ縮約部8が呼び出される。グラフ縮約部8では、グラフデータベース1が保持する図3のグラフについて、図5で選択されているサブパターンに該当しない箇所を縮約し、その結果を縮約済グラフ記憶手段3に図7の内容で保存する。
【0131】
ステップs4’:実行制御部5から頻出部分構造抽出部9が呼び出される。頻出部分構造抽出部9では、縮約済グラフ記憶手段3が保持する図7の縮約済グラフに対して、頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段4に図9の内容で保存する。
【0132】
ステップs5’:実行制御部5から頻出部分構造表示部10が呼び出される。頻出部分構造表示部10では、頻出部分構造記憶手段4が保持する図9の連結グラフとその出現回数および頻度を、本発明装置を実現する計算機の出力装置を介して表示する。
【符号の説明】
【0133】
1:グラフデータベース、2:サブパターン記憶手段、3:縮約済グラフ記憶手段、4:頻出部分構造記憶手段、5:実行制御部、6:サブパターン候補抽出部、7:サブパターン選択部、8:グラフ縮約部、9:頻出部分構造抽出部、10:頻出部分構造表示部。
【先行技術文献】
【特許文献】
【0134】
【特許文献1】特開2010−55381号公報(「業務または作業における着目する処理の進め方に応じて案件を分類する方法、その装置およびプログラム」)
【非特許文献】
【0135】
【非特許文献1】吉田健一、元田浩、「推論過程からの概念学習(1)−類型的推論過程の抽出−」、人工知能学会誌、Vol.7、No.4、pp.675-685、1992.
【非特許文献2】L. B. Holder, D. J. Cook, S. Djoko, "Structure Discovery in the SUBDUE System", Proceedings of the 4th ACM SIGKDD Workshop on Knowledge Discovery and Data Mining (KDD) 1994, pp.169-180, 1994.
【非特許文献3】N. Vanetik, E. gudes, S. E. Shimony, "Computing Frequent Graph Patterns from Semistructured Data", Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM), pp.458-465, 2002.
【非特許文献4】X. Yan, J. Han, "gSpan: Graph-Based Substructure Pattern Mining", Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM), pp.721-724, 2002.
【非特許文献5】M. Kuramochi, G. Karypis, "An Efficient Algorithm for Discovering Frequent Subgraphs", IEEE Transactions on Knowledge and Data Engineering, Volume 16, Issue 9, pp.1038-1051, 2004.
【非特許文献6】A. Inokuchi, T. Wahio, H. Motoda, "Complete Mining of Frequent Patterns from Graphs: Mining Graph Data", Machine Learning, Volume 50, pp.321-354, 2003.
【特許請求の範囲】
【請求項1】
グラフ構造を有するデータから頻度の高い部分構造を抽出する方法であって、
グラフデータベース、サブパターン記憶手段、縮約済グラフ記憶手段、頻出部分構造記憶手段、サブパターン候補抽出部、サブパターン選択部、グラフ縮約部、頻出部分構造抽出部および頻出部分構造表示部を用い、
サブパターン候補抽出部が、グラフデータベースが保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその連結グラフの出現回数および頻度を算出し、その結果を連結グラフの該当箇所を特定する情報であるグラフ該当箇所情報とともにサブパターン記憶手段に保存する第1のステップと、
サブパターン選択部が、サブパターン記憶手段が保持する連結グラフのうち着目する部分構造であるサブパターンとして使用するものを選択し、その選択結果をサブパターン記憶手段に保存する第2のステップと、
グラフ縮約部が、グラフデータベースが保持しているグラフと、サブパターン記憶手段がサブパターンとして保持している連結グラフを読み込み、グラフデータベースが保持するグラフにおいて、サブパターンの連結グラフに該当しない箇所を匿名化するとともに統合し、縮約済グラフ記憶手段に保存する第3のステップと、
頻出部分構造抽出部が、縮約済グラフ記憶手段が保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段に保存する第4のステップと、
頻出部分構造表示部が、頻出部分構造記憶手段が保持する連結グラフとその出現回数および頻度を表示する第5のステップとを含む、
ことを特徴とする部分構造抽出方法。
【請求項2】
第2のステップにおけるサブパターンの選択は、所定のサブパターン選択関数に従って自動的に行う、または利用者からの指示に従って行う
ことを特徴とする請求項1に記載の部分構造抽出方法。
【請求項3】
利用者から分析の開始が指示された場合は第1乃至第5のステップを実行させ、利用者から分析の再実行が指示された場合には第2乃至第5のステップを実行させる
ことを特徴とする請求項1または2に記載の部分構造抽出方法。
【請求項4】
計算機を用いてグラフ構造を有するデータから頻度の高い部分構造を抽出する方法であって、
計算機が、
パターンおよびデータベース中のグラフを、1個以上の(a)着目する部分構造に相当する連結グラフと、これらを連結する0個以上の(b)着目しない部分構造に相当する連結グラフとによって構成される連結グラフとして扱うとともに、
計算機が、
(b)に対する匿名化および統合からなるグラフの縮約を行った上で、同型性判定によりデータベース中の部分構造がパターンに該当するかどうかを判定し、その判定結果に基づきパターンの出現回数および頻度を求めることで、互いに非連結な連結部分グラフの頻度の高い組合せを抽出する場合に、前記連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性を区別して出現回数および頻度を算出し、該当判定による頻度の高い部分構造を抽出する
ことを特徴とする部分構造抽出方法。
【請求項5】
縮約を行う前のグラフにおいて、同型性判定による頻度の高い連結部分グラフを、(a)着目する部分構造に相当する連結グラフの候補とする
ことを特徴とする請求項4に記載の部分構造抽出方法。
【請求項6】
同型性判定による頻度の高い連結部分グラフを、(a)着目する部分構造に相当する連結グラフの候補とし、それに該当しない部分を、(b)着目しない部分構造に相当する連結グラフとし、(b)に対するグラフの縮約を挟んで、同型性判定による頻度の高い部分構造の抽出を多段階で行う
ことを特徴とする請求項4または5に記載の部分構造抽出方法。
【請求項7】
グラフ構造を有するデータから頻度の高い部分構造を抽出する装置であって、
分析対象となるグラフを保持するグラフデータベースと、
同型性判定による頻度の高い連結グラフ、当該連結グラフの該当箇所を特定する情報であるグラフ該当箇所情報、各連結グラフの出現回数および頻度、並びに各連結グラフのうちサブパターンとして使用することが選択された結果を保持するサブパターン記憶手段と、
グラフデータベースが保持するグラフのうち、サブパターン記憶手段が保持するサブパターンとしての連結グラフに該当しない箇所を縮約した結果を保持する縮約済グラフ記憶手段と、
縮約済グラフ記憶手段が保持するグラフのうち、同型性判定による頻度の高い連結グラフ、並びに当該各連結グラフの出現回数および頻度を保持する頻出部分構造記憶手段と、
グラフデータベースからグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその連結グラフの出現回数および頻度を算出し、その結果をグラフ該当箇所情報とともにサブパターン記憶手段に保存するサブパターン候補抽出部と、
サブパターン記憶手段が保持する連結グラフのうち部分構造であるサブパターンとして使用するものを選択し、その選択結果をサブパターン記憶手段に保存するサブパターン選択部と、
グラフデータベースが保持しているグラフと、サブパターン記憶手段がサブパターンとして保持している連結グラフを読み込み、グラフデータベースが保持するグラフにおいて、サブパターンの連結グラフに該当しない箇所を匿名化するとともに統合し、縮約済グラフ記憶手段に保存するグラフ縮約部と、
縮約済グラフ記憶手段が保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段に保存する頻出部分構造抽出部と、
頻出部分構造記憶手段が保持する連結グラフとその出現回数および頻度を表示する頻出部分構造表示部とを少なくとも備えた
ことを特徴とする部分構造抽出装置。
【請求項8】
サブパターン記憶手段が保持する連結グラフのうち、部分構造であるサブパターンとして使用するものを、所定のサブパターン選択関数に従って自動的に選択し、または利用者からの指示に従って選択し、その選択結果をサブパターン記憶手段に保存するサブパターン選択部を備えた
ことを特徴とする請求項7に記載の部分構造抽出装置。
【請求項9】
利用者から分析の開始が指示された場合はサブパターン候補抽出部、サブパターン選択部、グラフ縮約部、頻出部分構造抽出部、頻出部分構造表示部をこの順に、前の処理の完了を待って呼び出し、実行させ、利用者から分析の再実行が指示された場合には、サブパターン選択部、グラフ縮約部、頻出部分構造抽出部、頻出部分構造表示部をこの順に、前の処理の完了を待って呼び出し、実行させる実行制御部を備えた
ことを特徴とする請求項7または8に記載の部分構造抽出装置。
【請求項10】
グラフ構造を有するデータから頻度の高い部分構造を抽出する装置であって、
(a)着目する部分構造に相当する連結グラフの候補を抽出および選択するサブパターン候補抽出部およびサブパターン選択部と、
(b)着目しない部分構造に相当する連結グラフに対する匿名化および統合からなるグラフの縮約を行うグラフ縮約部と、
縮約されたグラフを対象として、同型性判定によりデータベース中の部分構造がパターンに該当するかどうかを判定し、その判定結果に基づきパターンの出現回数および頻度を求める頻出部分構造抽出部とを併せて備えることにより、
パターンおよびデータベース中のグラフを、1個以上の(a)着目する部分構造に相当する連結グラフと、これらを連結する0個以上の(b)着目しない部分構造に相当する連結グラフとによって構成される連結グラフとして扱い、互いに非連結な連結部分グラフの頻度の高い組合せを抽出する場合に、前記連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性を区別して出現回数および頻度を算出し、該当判定による頻度の高い部分構造を抽出する
ことを特徴とする部分構造抽出装置。
【請求項11】
縮約を行う前のグラフにおいて、同型性判定による頻度の高い連結部分グラフを、(a)着目する部分構造に相当する連結グラフの候補とするサブパターン候補抽出部を備えた
ことを特徴とする請求項10に記載の部分構造抽出装置。
【請求項12】
(b)着目しない部分構造に相当する連結グラフに対するグラフの縮約を行うグラフ縮約部を挟み、サブパターン候補抽出部および頻出部分構造抽出部において同型性判定による頻度の高い連結部分グラフを多段で抽出する構成を備えた
ことを特徴とする請求項10または11に記載の部分構造抽出装置。
【請求項13】
コンピュータを、請求項7乃至12のいずれかに記載の部分構造抽出装置の各手段として機能させるためのプログラム。
【請求項1】
グラフ構造を有するデータから頻度の高い部分構造を抽出する方法であって、
グラフデータベース、サブパターン記憶手段、縮約済グラフ記憶手段、頻出部分構造記憶手段、サブパターン候補抽出部、サブパターン選択部、グラフ縮約部、頻出部分構造抽出部および頻出部分構造表示部を用い、
サブパターン候補抽出部が、グラフデータベースが保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその連結グラフの出現回数および頻度を算出し、その結果を連結グラフの該当箇所を特定する情報であるグラフ該当箇所情報とともにサブパターン記憶手段に保存する第1のステップと、
サブパターン選択部が、サブパターン記憶手段が保持する連結グラフのうち着目する部分構造であるサブパターンとして使用するものを選択し、その選択結果をサブパターン記憶手段に保存する第2のステップと、
グラフ縮約部が、グラフデータベースが保持しているグラフと、サブパターン記憶手段がサブパターンとして保持している連結グラフを読み込み、グラフデータベースが保持するグラフにおいて、サブパターンの連結グラフに該当しない箇所を匿名化するとともに統合し、縮約済グラフ記憶手段に保存する第3のステップと、
頻出部分構造抽出部が、縮約済グラフ記憶手段が保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段に保存する第4のステップと、
頻出部分構造表示部が、頻出部分構造記憶手段が保持する連結グラフとその出現回数および頻度を表示する第5のステップとを含む、
ことを特徴とする部分構造抽出方法。
【請求項2】
第2のステップにおけるサブパターンの選択は、所定のサブパターン選択関数に従って自動的に行う、または利用者からの指示に従って行う
ことを特徴とする請求項1に記載の部分構造抽出方法。
【請求項3】
利用者から分析の開始が指示された場合は第1乃至第5のステップを実行させ、利用者から分析の再実行が指示された場合には第2乃至第5のステップを実行させる
ことを特徴とする請求項1または2に記載の部分構造抽出方法。
【請求項4】
計算機を用いてグラフ構造を有するデータから頻度の高い部分構造を抽出する方法であって、
計算機が、
パターンおよびデータベース中のグラフを、1個以上の(a)着目する部分構造に相当する連結グラフと、これらを連結する0個以上の(b)着目しない部分構造に相当する連結グラフとによって構成される連結グラフとして扱うとともに、
計算機が、
(b)に対する匿名化および統合からなるグラフの縮約を行った上で、同型性判定によりデータベース中の部分構造がパターンに該当するかどうかを判定し、その判定結果に基づきパターンの出現回数および頻度を求めることで、互いに非連結な連結部分グラフの頻度の高い組合せを抽出する場合に、前記連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性を区別して出現回数および頻度を算出し、該当判定による頻度の高い部分構造を抽出する
ことを特徴とする部分構造抽出方法。
【請求項5】
縮約を行う前のグラフにおいて、同型性判定による頻度の高い連結部分グラフを、(a)着目する部分構造に相当する連結グラフの候補とする
ことを特徴とする請求項4に記載の部分構造抽出方法。
【請求項6】
同型性判定による頻度の高い連結部分グラフを、(a)着目する部分構造に相当する連結グラフの候補とし、それに該当しない部分を、(b)着目しない部分構造に相当する連結グラフとし、(b)に対するグラフの縮約を挟んで、同型性判定による頻度の高い部分構造の抽出を多段階で行う
ことを特徴とする請求項4または5に記載の部分構造抽出方法。
【請求項7】
グラフ構造を有するデータから頻度の高い部分構造を抽出する装置であって、
分析対象となるグラフを保持するグラフデータベースと、
同型性判定による頻度の高い連結グラフ、当該連結グラフの該当箇所を特定する情報であるグラフ該当箇所情報、各連結グラフの出現回数および頻度、並びに各連結グラフのうちサブパターンとして使用することが選択された結果を保持するサブパターン記憶手段と、
グラフデータベースが保持するグラフのうち、サブパターン記憶手段が保持するサブパターンとしての連結グラフに該当しない箇所を縮約した結果を保持する縮約済グラフ記憶手段と、
縮約済グラフ記憶手段が保持するグラフのうち、同型性判定による頻度の高い連結グラフ、並びに当該各連結グラフの出現回数および頻度を保持する頻出部分構造記憶手段と、
グラフデータベースからグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその連結グラフの出現回数および頻度を算出し、その結果をグラフ該当箇所情報とともにサブパターン記憶手段に保存するサブパターン候補抽出部と、
サブパターン記憶手段が保持する連結グラフのうち部分構造であるサブパターンとして使用するものを選択し、その選択結果をサブパターン記憶手段に保存するサブパターン選択部と、
グラフデータベースが保持しているグラフと、サブパターン記憶手段がサブパターンとして保持している連結グラフを読み込み、グラフデータベースが保持するグラフにおいて、サブパターンの連結グラフに該当しない箇所を匿名化するとともに統合し、縮約済グラフ記憶手段に保存するグラフ縮約部と、
縮約済グラフ記憶手段が保持するグラフを読み込み、同型性判定による頻度の高い部分構造を連結グラフとして抽出し、またその出現回数および頻度を算出し、頻出部分構造記憶手段に保存する頻出部分構造抽出部と、
頻出部分構造記憶手段が保持する連結グラフとその出現回数および頻度を表示する頻出部分構造表示部とを少なくとも備えた
ことを特徴とする部分構造抽出装置。
【請求項8】
サブパターン記憶手段が保持する連結グラフのうち、部分構造であるサブパターンとして使用するものを、所定のサブパターン選択関数に従って自動的に選択し、または利用者からの指示に従って選択し、その選択結果をサブパターン記憶手段に保存するサブパターン選択部を備えた
ことを特徴とする請求項7に記載の部分構造抽出装置。
【請求項9】
利用者から分析の開始が指示された場合はサブパターン候補抽出部、サブパターン選択部、グラフ縮約部、頻出部分構造抽出部、頻出部分構造表示部をこの順に、前の処理の完了を待って呼び出し、実行させ、利用者から分析の再実行が指示された場合には、サブパターン選択部、グラフ縮約部、頻出部分構造抽出部、頻出部分構造表示部をこの順に、前の処理の完了を待って呼び出し、実行させる実行制御部を備えた
ことを特徴とする請求項7または8に記載の部分構造抽出装置。
【請求項10】
グラフ構造を有するデータから頻度の高い部分構造を抽出する装置であって、
(a)着目する部分構造に相当する連結グラフの候補を抽出および選択するサブパターン候補抽出部およびサブパターン選択部と、
(b)着目しない部分構造に相当する連結グラフに対する匿名化および統合からなるグラフの縮約を行うグラフ縮約部と、
縮約されたグラフを対象として、同型性判定によりデータベース中の部分構造がパターンに該当するかどうかを判定し、その判定結果に基づきパターンの出現回数および頻度を求める頻出部分構造抽出部とを併せて備えることにより、
パターンおよびデータベース中のグラフを、1個以上の(a)着目する部分構造に相当する連結グラフと、これらを連結する0個以上の(b)着目しない部分構造に相当する連結グラフとによって構成される連結グラフとして扱い、互いに非連結な連結部分グラフの頻度の高い組合せを抽出する場合に、前記連結部分グラフに含まれるノード間の、データベース中のグラフにおける到達可能性を区別して出現回数および頻度を算出し、該当判定による頻度の高い部分構造を抽出する
ことを特徴とする部分構造抽出装置。
【請求項11】
縮約を行う前のグラフにおいて、同型性判定による頻度の高い連結部分グラフを、(a)着目する部分構造に相当する連結グラフの候補とするサブパターン候補抽出部を備えた
ことを特徴とする請求項10に記載の部分構造抽出装置。
【請求項12】
(b)着目しない部分構造に相当する連結グラフに対するグラフの縮約を行うグラフ縮約部を挟み、サブパターン候補抽出部および頻出部分構造抽出部において同型性判定による頻度の高い連結部分グラフを多段で抽出する構成を備えた
ことを特徴とする請求項10または11に記載の部分構造抽出装置。
【請求項13】
コンピュータを、請求項7乃至12のいずれかに記載の部分構造抽出装置の各手段として機能させるためのプログラム。
【図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】
【図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】
【公開番号】特開2013−3669(P2013−3669A)
【公開日】平成25年1月7日(2013.1.7)
【国際特許分類】
【出願番号】特願2011−131389(P2011−131389)
【出願日】平成23年6月13日(2011.6.13)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成25年1月7日(2013.1.7)
【国際特許分類】
【出願日】平成23年6月13日(2011.6.13)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]