Pat
J-GLOBAL ID：200903010172145206
頻出部分グラフ抽出装置、頻出部分グラフ抽出方法、ならびに、プログラム
Inventor：
Applicant, Patent owner：
Agent (2)：
木村 満
, 石井 裕一郎
Gazette classification：公開公報
Application number (International application number)：2003062954
Publication number (International publication number)：2004272627
Application date： Mar. 10, 2003
Publication date： Sep. 30, 2004
Summary：
【課題】頻出部分グラフ抽出装置等を提供する。【解決手段】頻出部分グラフ抽出装置201において、入力受付部202は、親子枝と兄弟枝がノードの間に張られるDAGの入力を受け付け、横方向枝選択部203は、DAG内の親兄弟グラフに含まれる兄弟枝を横方向枝として抽出し、その始点と終点の組合せの出現頻度が所定の横方向閾値以上のものを頻出横方向枝として選択し、縦方向枝選択部204は、当該有向非循環グラフ内の親子枝を縦方向枝として抽出し、その始点と終点の組合せの出現頻度が所定の縦方向閾値以上のものを頻出縦方向枝として選択し、部分グラフ選択部205は、頻出横方向枝を含む親兄弟グラフを頻出縦方向枝で連結したものを頻出部分グラフとして選択し、出力部206は、選択された頻出部分グラフを、抽出の結果として出力する。【選択図】 図2
Claim (excerpt)：
入力受付部と、横方向枝選択部と、縦方向枝選択部と、部分グラフ選択部と、出力部と、を備える頻出部分グラフ抽出装置であって、
前記入力受付部は、複数のノードと、これらのノード間に張られる2種類の有向枝(以下、一方を「親子枝」、他方を「兄弟枝」という。)と、からなる有向非循環グラフの情報の入力を受け付け、
前記横方向枝選択部は、当該有向非循環グラフ内の「部分グラフであって、2つの親子枝と、1つの兄弟枝とを有し、当該2つの親子枝の始点は一致し、当該2つの親子枝の一方の終点は当該1つの兄弟枝の始点に、当該2つの親子枝の他方の終点は当該1つの兄弟枝の終点に、それぞれ一致するもの(以下、「親兄弟グラフ」という。)」に含まれる兄弟枝を横方向枝として抽出し、当該抽出された横方向枝から、その始点と終点の組合せの出現頻度が所定の横方向閾値以上のものを頻出横方向枝として選択し、
前記縦方向枝選択部は、当該有向非循環グラフ内の親子枝を縦方向枝として抽出し、当該抽出された縦方向枝から、その始点と終点の組合せの出現頻度が所定の縦方向閾値以上のものを頻出縦方向枝として選択し、
前記部分グラフ選択部は、
「当該有向非循環グラフ内の部分グラフであって、
0個以上の親兄弟グラフであって頻出横方向枝を含むものと、0個以上の頻出縦方向枝であって当該親兄弟グラフに含まれないものとからなり、それぞれの個数の和は1以上であり、
当該頻出縦方向枝が1個以上であり、かつ、当該親兄弟グラフが1個以上である場合、当該頻出縦方向枝のそれぞれの始点もしくは終点は、当該親兄弟グラフに含まれるいずれかのノードである
もの」を頻出部分グラフとして選択し、
前記出力部は、前記選択された頻出部分グラフを、抽出の結果として出力する
ことを特徴とするもの。
IPC (2)：
FI (2)：
G06F17/21 501T
, G06F17/30 419B
5B009QA06
, 5B009SA06
, 5B009VA02
, 5B075ND03
, 5B075ND36
, 5B075NR02
, 5B075NR20
, 5B075UU06
