(57)【要約】  データベースの内容を把握し、あるいは修正を行うために有用なルールの集合を効率よく得ることができる装置、方法、プログラムの提供。データベースの内容と、設定パラメータ、または、生成済みルールの候補に基づき、新たなルールの候補を生成するルール候補生成手段（図１の２１）と、前記ルールの候補がデータベースの内容に対して妥当であるかチェックするルールの妥当性判定手段（図１の２２）とを有する。
2013172308.tif 000002
【特許請求の範囲】
【請求項１】
データベースを記憶する記憶装置と、
データ処理装置と、
出力装置と、
を備え、
前記データ処理装置は、
前記データベースからルール候補を生成するルール候補生成手段と、
前記ルール候補が前記データベースの内容に対して妥当であるか否か判定するルールの妥当性判定手段と、
を備え、
前記ルール候補生成手段は、
前記データベースにおける属性と値のペアからなるアイテムであって、前記データベースでの頻度が、予め定められた所定の閾値以上のアイテムの集合を生成し、
ルール候補の初期値として、条件部・前提部を空、帰結部を前記アイテムとするルール集合を生成して記憶部に記憶し、
前記ルールの妥当性判定手段は、
前記ルール候補生成手段で生成された前記ルール候補の各ルールに対して、
前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合、前記ルールを妥当と判定して前記出力装置に出力し、
妥当性判定対象の前記ルール候補が空となると、前記ルール候補生成手段では、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成して記憶部に記憶し、
前記ルール候補生成手段で生成された前記新たなルール候補に対する、前記ルールの妥当性判定手段による、妥当性の判定と、
前記ルール候補生成手段による、条件部・前提部のサイズを前回生成した前記ルール候補よりも１つ増やした、新たなルール候補の生成と、
を、前記ルール候補生成手段にて、条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成することができず前記新たなルール候補が空となるまで、繰り返す、ことを特徴とするルール発見システム。
【請求項２】
前記ルールの妥当性判定手段で妥当と判断されたルールの前記帰結部を、前記ルール候補生成手段によるルール候補の探索において、帰結部の候補から除外し、
前記妥当と判断されたルールの前記帰結部を帰結部に含む冗長なルールは、前記ルール候補生成手段において前記新たなルール候補として生成されないようにした、ことを特徴とする請求項１記載のルール発見システム。
【請求項３】
前記頻度の閾値と前記確信度の閾値を設定パラメータとして入力する入力装置を備えている、ことを特徴とする請求項１記載のルール発見システム。
【請求項４】
前記ルールは、ＣＦＤ（Conditional Functional Dependency）で表現されたルールである、ことを特徴とする請求項１乃至３のいずれか１項に記載のルール発見システム。
【請求項５】
ルール候補生成手段とルールの妥当性判定手段を備えたデータ処理装置によりデータベースからルールを発見するにあたり、
（ａ）前記ルール候補生成手段が、前記データベースを読み出し、前記データベースの属性と値のペアからなり頻度が予め定められた所定の閾値以上のアイテムを生成し、
ルール候補の初期値として、条件部・前提部を空、帰結部を前記アイテムとするルール集合を生成して記憶部に記憶し、
（ｂ）前記ルールの妥当性判定手段は、前記生成されたルール候補のルールに対して、前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合には、前記ルールを妥当と判定して出力装置より出力し、
（ｃ）妥当性判定対象の前記ルール候補が空か否かチェックし、妥当性判定対象の前記ルール候補が空でない場合、前記ルールの妥当性判定手段は、前記ステップ（ｂ）に戻り、
（ｄ）妥当性判定対象の前記ルール候補が空の場合、前記ルール候補生成手段は、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした、新たなルール候補を生成して記憶部に記憶し、
（ｅ）前記ステップ（ｄ）で生成された前記新たなルール候補が空か否かチェックし、前記新たなルール候補が空の場合、ルールの発見を終了し、
前記新たなルール候補が空でない場合、前記ステップ（ｂ）に戻る、ことを特徴とするルール発見方法。
【請求項６】
前記ルールの妥当性判定手段で前記ルールが妥当と判断された場合、前記妥当と判断されたルールの前記帰結部を、ルール候補の探索において、帰結部の候補から除外し、前記妥当と判断されたルールの前記帰結部を、帰結部に含む冗長なルールは、前記ルール候補生成手段により前記新たなルール候補として生成されないようにした、ことを特徴とする請求項５記載のルール発見方法。
【請求項７】
前記ルールは、ＣＦＤ（Conditional Functional Dependency）で表現されたルールである、ことを特徴とする請求項５又は６記載のルール発見方法。
【請求項８】
（ａ）データベースを読み出し、前記データベースの属性と値のペアからなり頻度が予め定められた所定の閾値以上のアイテムを生成し、ルール候補の初期値として、条件部・前提部が空、帰結部が、前記アイテムであるルールを生成して記憶部に記憶する処理と、
（ｂ）前記生成されたルール候補のルールに対して、前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合には、前記ルールを妥当と判断して出力装置より出力する処理と、
（ｃ）妥当性判定対象の前記ルール候補が空であるか否かチェックし、妥当性を判定する前記ルール候補が空でない場合、前記（ｂ）に戻る処理と、
（ｄ）妥当性判定対象の前記ルール候補が空の場合、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成して記憶部に記憶する処理と、
（ｅ）前記（ｄ）の処理で生成された前記新たなルール候補が空か否かチェックし、前記新たなルール候補が空の場合、ルール発見処理を終了し、
前記新たなルール候補が空でない場合、前記（ｂ）に戻る処理と、
をコンピュータに実行させるプログラム。
【請求項９】
前記（ｂ）の処理で、前記ルール候補が妥当と判断された場合、前記（ｄ）の処理では、前記妥当と判断されたルールの前記帰結部を、ルール候補の探索において、帰結部の候補から除外し、前記妥当と判断されたルールの前記帰結部を、帰結部に含む冗長なルールは、前記（ｄ）の処理により、新たに生成されるルール候補として生成されないようにした、ことを特徴とする請求項８記載のプログラム。
【請求項１０】
データベースの内容と、入力装置から設定された頻度の閾値、又は、生成済みルール候補に基づき、新たなルール候補を生成するルール候補生成手段と、
前記ルール候補が前記データベースの内容に対して妥当であるか否か判定するルールの妥当性判定手段と、
を含み、
前記ルール候補生成手段は、前記データベースを読み出し、前記データベースの属性と値のペアからなるアイテムであって、頻度が前記閾値以上のアイテムを生成し、ルール候補の初期値として、条件部・前提部が空、帰結部が、前記アイテムであるルールを生成し、
幅優先探索に基づき、条件部・前提部のサイズの小さなルール候補から順に生成し、
前記生成されたルール候補の各ルールに対して、前記ルールの妥当性判定手段では、前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、前記入力装置から入力された確信度の閾値以上でマッチしている場合、前記ルールを妥当と判断して出力装置に出力し、
妥当性判定対象の前記ルール候補が空となると、前記ルール候補生成手段では、前記妥当なルールに対して冗長なルールを、ルール候補の探索から除外して、前記アイテムを条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成し、
前記ルール候補生成手段で生成された前記新たなルール候補に対する前記ルールの妥当性判定手段による妥当性の判定と、
前記ルール候補生成手段による条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補の生成と、
を、前記ルール候補生成手段にて、条件部・前提部のサイズを前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成できず前記新たなルール候補が空となるまで、繰り返す、ことを特徴とするルール発見装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１２−１１０９２１号（２０１２年  ５月１４日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、ルールの発見を行う技術に関し、特にデータベースのルールの発見を行うシステムと方法と装置並びにプログラムに関する。
【背景技術】
【０００２】
データベースのルールの発見は、例えばルールをＣＦＤ（Conditional Function Dependency：条件付関数帰結部）として表現するものとし、生成されたＣＦＤルールの候補から、データベースの内容に合致したＣＦＤルールを出力する。以下では、発明の理解の前提となるＣＦＤについて概説する。【０００３】
ＣＦＤは、データ属性間の帰結部を表す関数帰結部（Functional Dependency：「ＦＤ」と略記される）が、条件によって指定されたタプル集合について成立することを表すルールである。ルールの左辺（ＬＨＳ：Left Hand Side）である条件部、前提部と、ルールの右辺（ＲＨＳ：Right Hand Side）の帰結部における属性値の指定からなる。なお、条件部、帰結部は、それぞれ条件節、従属節ともいう。【０００４】
条件部は、データの部分集合（タプル集合）を指定し、属性Ｘが属性値ｘであるということを「Ｘ＝ｘ」と表す。ここで、「ｘ」は属性値がある特定の値であることを意味する。このような、属性値の表現を「Ｃｏｎｓｔａｎｔである」という（なお、「Ｃｏｎｓｔａｎｔ」は例えば「定数」を意味する）。【０００５】
また、前提部は、属性のみの指定からなり、属性値は特定の値をとらない（すなわち、任意の値とマッチすることを表すワイルドカード）ことを「Ｘ＝ _ 」と表す。このような属性値の表現を「バリアブル（Variable）である」という（なお、「Variable」は例えば「変数」を意味する）。ここで、‘＿’は「unnamed variable」（無名変数）ともいう。【０００６】
帰結部には、２種類ある。
（Ａ）属性と属性値の指定からなるもの（例えば、以下のルール１）と、
（Ｂ）属性のみを指定するもの（例えば、以下のルール２）
である。【０００７】
（Ａ）の場合、例えば「Ａ＝ａ」、
（Ｂ）の場合、例えば「Ａ＝＿」等と表される。なお、帰結部に、属性値の指定がある場合には、前提部は省略することができる。また、前提部、帰結部は、複数の属性とそれぞれの属性値の指定からなることもある。以下にルールの例を示す。【０００８】
ルール１：Ｘ１ → Ａ（ｘ１ || ａ）
ルール２：Ｘ１, Ｘ２ → Ａ（ｘ１, _ || _ ）【０００９】
ルール１は、「属性Ｘ１が属性値ｘ１のとき、属性Ａは属性値ａである」という意味のルールである。ルール１が成り立つとき、条件部に当てはまるタプル集合において、帰結部が指定された値であることを表す。つまり、条件Ｘ１＝ｘ１を満たすタプル集合の全てのタプルにおいて、ｔ［Ａ］＝ａである（なお、ｔ［Ａ］は、属性Ａのタプルを表している）。このように、帰結部が指定された値に決まるルールを「コンスタントＣＦＤ（Constant CFD）」という。【００１０】
ルール２は、「属性Ｘ１が属性値ｘ１のとき、属性Ｘ２によって属性Ａが決まる」という意味のルールである。ルール２が成り立つとき、条件部に当てはまるタプル集合において、前提部と帰結部で指定された属性間に帰結部があることを表す。つまり、条件「Ｘ１＝ｘ１」を満たすタプル集合の中の任意のタプルペアｔ１、ｔ２について、ｔ１［Ｘ２］＝ｔ２［Ｘ２］であれば、ｔ１［Ａ］＝ｔ２［Ａ］となる。このように帰結部が指定された値に決まらないが、属性間に帰結部を持つようなルールを「バリアブルＣＦＤ（Variable CFD）」という。すなわち、パタンタプルの||の右側がunnamed variable‘＿’の場合（ｔｐ［Ａ］＝＿）、バリアブルＣＦＤ（Variable CFD）という。【００１１】
ルール１のパタンタプル（ｘ1 || ａ）における記号‘||’は、左辺のＸ１と右辺のＡの属性値を分離する。なお、ルール１の“Ｘ１→Ａ（ｘ１ || ａ）”を、“（Ｘ→Ａ，（ｘ || ａ））”と表記する例もあるが、外側の括弧とカンマの有無が相違するだけであり、同一のルールを表すものであることは自明である。同様に、ルール２の“Ｘ１，Ｘ２→Ａ（ｘ１，_|| _ )”を“（［Ｘ１，Ｘ２］→Ａ，（ｘ１，_|| _ )）”とも表記する。【００１２】
与えられたデータに対してＣＦＤがどれだけ有効なルールであるかを示す指標として、例えば支持度（Support）や確信度（Confidence）が用いられている。支持度（Support）は、ＣＦＤの条件部と前提部がマッチするタプル数である。【００１３】
確信度（Confidence）は、条件部と前提部がマッチするタプル数の中で、ＣＦＤのルールが成立するタプル数の割合である。【００１４】
複数のＣＦＤが与えられた時、「left-reduced」（レフト・レデュースト）、且つ、「most-general」（モストジェネラル）の２つの条件を満たすＣＦＤを、「minimal」（ミニマル）であるという。「left-reduced」について説明する。複数のＣＦＤが与えられた時、いかなるＣＦＤの左辺（ＬＨＳ）の属性セットも、他のＣＦＤの左辺の属性セットを包含しないＣＦＤを「left-reduced」であるという。【００１５】
例えば、以下のルール３、ルール４が与えられた時、ルール４の左辺は、ルール３の左辺を包含している（Ｘ１⊂Ｘ１，Ｘ２）ことから、ルール４は、「left-reduced」ではない。逆に、ルール３の左辺は、ルール４の左辺を包含しないので、ルール３は「left-reduced」であるという。この場合、ルール４は、ルール３に対して、冗長なＣＦＤとして削除することができる。【００１６】
ルール３：  Ｘ１，Ｙ→Ａ（ｘ１，＿ || ＿）
ルール４：  Ｘ１，Ｘ２，Ｙ→Ａ（ｘ１，ｘ２ || ＿）【００１７】
次に、「most-general」について説明する。複数のＣＦＤが与えられた時、いかなるＣＦＤの左辺に含まれる属性値の定数も‘＿’（Variable）に更新できない場合、「most-general」であるという。【００１８】
例えば、以下のルール５、ルール６が与えられた時、ルール６の属性値ｘ２をＶａｒｉａｂｌｅに置き換えることで、ルール５を得ることができる。このため、ルール６は「most-general」でない。逆に、ルール５は「most-general」であるという。この場合、ルール６は、ルール５に対して冗長なＣＦＤとして削除することができる。【００１９】
ルール５：  Ｘ１，Ｘ２→Ａ（ｘ１，＿ || ａ）
ルール６：  Ｘ１，Ｘ２→Ａ（ｘ１，ｘ２ || ａ）【００２０】
以上でＣＦＤの概説を終える。【００２１】
データベースからルールを発見する装置は、ＣＦＤを保存する磁気ディスク等の記憶手段（記憶部）と、ＣＦＤの候補を生成し、ＣＦＤ候補がデータベースの内容に合致しているか判定する演算手段（演算部）と、内容に合致していると判定されたＣＦＤを記憶装置に保存する保存手段（保存部）から構成される。記憶手段は、ルール発見アルゴリズムで得られたＣＦＤを保存する。演算手段は、チェックの対象とするＣＦＤの候補を生成し、それがデータベースの内容に合致しているかどうか調べ、合致している場合、妥当なＣＦＤとして出力する。保存手段は、得られた妥当なＣＦＤを、記憶装置に保存する。【００２２】
データベースのルールの発見手法として、例えば非特許文献１に記載されているように、
（１）フリー・アイテムセット（free  itemset）と、それに対応するクローズド・アイテムセット（closed  itemset）からコンスタントＣＦＤ（constant CFD）の候補を生成する手法、
（２）属性と値のペアのリストを、幅優先探索（breadth first search）により生成し、そのうちの１つの項を従属項（Ａとする）、残りを条件部（Ｘとする）に置き、
式：Ｘ→Ａ
を得ることによって、ＣＦＤの候補を生成する手法、
（３）フリー・アイテムセット（free  itemset）を条件項、フリー・アイテムセット（free  itemset）に含まれない１つの属性を従属項（帰結部）に置き、それ以外に条件項に加える属性を、深さ優先探索（depth first search）することで、ＣＦＤの候補を生成する手法、
等がある。【００２３】
前述したように、データベースの内容とＣＦＤがどの程度一致しているかを表す指標として、確信度がある。【００２４】
データベースの内容と完全には一致していないが、高い確信度（Confidence）を持つルール（ＣＦＤ）の発見手法として、非特許文献２には、幅優先探索（breadth first search）を用いて、確信度（Confidence）が閾値以上のＣＦＤ（以下、「approximate CFD」という）（「ほぼ成り立つ」ＣＦＤ）を発見する、手法が開示されている。【００２５】
なお、ルールの妥当性のチェックとして、例えば特許文献１には、条件部と結論部からなるルールを格納するルールベースと、ルールの適用結果に関する事例情報を格納する事例情報データベースと、ルールとルールを満たす事例情報を関係付ける関係付け部と、妥当性チェック対象のルールの条件部をキーとして事例情報データベースから事例情報集合を事例検索部に検索させ、事例情報集合において該ルールの結論部を満たす事例情報の割合を算出し、該割合に基づき、ルールの妥当性をチェックする妥当性チェック部と、を備えたルールベース管理装置が開示されている。また、特許文献２には、リレーションの属性間の関数帰結部（ＦＤ）を見つけ出し、リレーション分割による正規化を行う構成が開示されている。
【先行技術文献】
【特許文献】
【００２６】
【特許文献１】国際公開第２００４／３６４９６号公報
【特許文献２】特開平６−１１０７４９号公報
【非特許文献】
【００２７】
【非特許文献１】Wenfei Fan et al., “Discovering Conditional Functional Dependencies,” pp.1231-1234, IEEE International Conference on Data Engineering, 2009  ［2012年4月9日検索］インターネットURL＜http://homepages.inf.ed.ac.uk/fgeerts/pdf/icde09.pdf＞
【非特許文献２】Chiang et al., “Discovering Data Quality Rules,” in VLDB, 2008、［2012年4月9日検索］インターネットURL＜http://dblab.cs.toronto.edu/~fchiang/docs/vldb08.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【００２８】
以下に、本発明者によって為された関連技術の分析を記載する。【００２９】
第１の問題点は、非特許文献１に開示されているＣＦＤ発見アルゴリズムにより得られるＣＦＤは、データベースに対して完全に成り立つ、つまり確信度が１のもののみであり、データベースに対して「ほぼ成り立つ」ものを列挙できない、ということである。【００３０】
第２の問題点は、非特許文献２に開示されているapproximate CFD発見アルゴリズムは、計算時間が極端に長くなる、ということである。その理由は、大規模な、特に、属性数の大きいデータベースに対しては生成されるＣＦＤの候補の個数が、組合せ爆発（combinational explosion）を起こしてしまうためである。【００３１】
本発明は、上記問題点に鑑みて創案されたものであって、その目的は、データベースの内容を把握し、あるいは修正を行うために有用なルールの集合を効率よく得ることができるシステム、装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００３２】
本発明によれば、データベースを記憶する記憶装置と、
データ処理装置と、
出力装置と、
を備え、
前記データ処理装置は、
前記データベースからルール候補を生成するルール候補生成手段と、
前記ルール候補が前記データベースの内容に対して妥当であるか否か判定するルールの妥当性判定手段と、
を備え、
前記ルール候補生成手段は、
前記データベースにおける属性と値のペアからなるアイテムであって、前記データベースでの頻度が、予め定められた所定の閾値以上のアイテムの集合を生成し、
ルール候補の初期値として、条件部・前提部（LHS）を空、帰結部（RHS）を前記アイテムとするルール集合を生成して記憶部に記憶し、
前記ルールの妥当性判定手段は、
前記ルール候補生成手段で生成された前記ルール候補の各ルールに対して、
前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合、前記ルールを妥当と判断して前記出力装置に出力し、
妥当性判定対象の前記ルール候補が空となると、前記ルール候補生成手段では、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成して記憶部に記憶し、
前記ルール候補生成手段で生成された前記新たなルール候補に対する前記ルールの妥当性判定手段による妥当性の判定と、
前記ルール候補生成手段による条件部・前提部のサイズを前回生成した前記ルール候補よりも１つ増やした新たなルール候補の生成と、
を、前記ルール候補生成手段にて、条件部・前提部のサイズを前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成できず前記新たなルール候補が空となるまで、繰り返すルール発見システムが提供される。【００３３】
本発明によれば、ルール候補生成手段とルールの妥当性判定手段を備えたデータ処理装置によりデータベースからルールを発見するにあたり、
（ａ）前記ルール候補生成手段が、前記データベースを読み出し、前記データベースの属性と値のペアからなり頻度が予め定められた所定の閾値以上のアイテムを生成し、
ルール候補の初期値として、条件部・前提部（LHS）を空、帰結部（RHS）を前記アイテムとするルール集合を生成して記憶部に記憶するステップと、
（ｂ）前記ルールの妥当性判定手段は、前記生成されたルール候補のルールに対して、前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合には、前記ルールを妥当と判断して出力装置より出力し、
（ｃ）妥当性判定対象の前記ルール候補が空であるか否かチェックし、妥当性判定対象の前記ルール候補が空でない場合、前記ルールの妥当性判定手段は、前記ステップ（ｂ）に戻り、
（ｄ）妥当性判定対象の前記ルール候補が空の場合、前記ルール候補生成手段は、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成して記憶部に記憶し、
（ｅ）前記ステップ（ｄ）で生成された前記新たなルール候補が空か否かチェックし、前記新たなルール候補が空の場合、ルールの発見を終了し、前記新たなルール候補が空でない場合、前記ステップ（ｂ）に戻る、前記各ステップを含むルール発見方法が提供される。【００３４】
本発明によれば、（ａ）データベースを読み出し、前記データベースの属性と値のペアからなり頻度が予め定められた所定の閾値以上のアイテムを生成し、ルール候補の初期値として、条件部・前提部（LHS）が空、帰結部（RHS）が、前記アイテムであるルールを生成して記憶部に記憶する処理と、
（ｂ）前記生成されたルール候補のルールに対して、前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合には、前記ルールを妥当と判断して出力装置より出力する処理と、
（ｃ）妥当性判定対象の前記ルール候補が空か否かチェックし、妥当性判定対象の前記ルール候補が空でない場合、前記（ｂ）に戻る処理と、
（ｄ）妥当性判定対象の前記ルール候補が空の場合、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成して記憶部に記憶する処理と、
（ｅ）前記（ｄ）の処理で生成された前記新たなルール候補が空か否かチェックし、
前記新たなルール候補が空の場合、ルール発見処理を終了し、
前記新たなルール候補が空でない場合、前記（ｂ）に戻る処理と、
をコンピュータに実行させるプログラムが提供される。本発明によれば、該プログラムを記憶したコンピュータで読み出し可能なメモリ装置、あるいは、磁気・光ディスク媒体／装置が提供される。【００３５】
本発明によれば、データベースの内容と、入力装置から設定された頻度の閾値、又は、生成済みルール候補に基づき、新たなルール候補を生成するルール候補生成手段と、
前記ルール候補が前記データベースの内容に対して妥当であるか否か判定するルールの妥当性判定手段と、を有し、
前記ルール候補生成手段は、前記データベースを読み出し、前記データベースの属性と値のペアからなるアイテムであって、頻度が前記閾値以上のアイテムを生成し、ルール候補の初期値として、条件部・前提部（LHS）が空、帰結部（RHS）が、前記アイテムであるルールを生成し、
幅優先探索に基づき、条件部・前提部のサイズの小さなルール候補から順に生成し、
前記生成されたルール候補の各ルールに対して、前記ルールの妥当性判定手段では、前記ルールの条件部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、前記入力装置から入力された確信度の閾値以上でマッチしている場合、前記ルールを妥当と判断して出力装置に出力し、
妥当性判対象の前記ルール候補が空となると、前記ルール候補生成手段では、前記妥当なルールに対して冗長なルールを、ルール候補の探索から除外して、前記アイテムを条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成し、
前記ルール候補生成手段で生成された前記新たなルール候補に対する前記ルールの妥当性判定手段による妥当性の判定と、
前記ルール候補生成手段による条件部・前提部のサイズを前回生成した前記ルール候補よりも１つ増やした新たなルール候補の生成を、
前記ルール候補生成手段にて、条件部・前提部のサイズを前回生成した前記ルール候補よりも１つ増やした新たなルール候補を生成できず前記新たなルール候補が空となるまで、繰り返すルール発見装置が提供される。
【発明の効果】
【００３６】
本発明によれば、データベースの内容を把握し、あるいは修正を行うために有用なルールの集合を、効率よく得ることができる。
【図面の簡単な説明】
【００３７】
【図１】本発明の例示的な第１の実施の形態の構成を示す図である。
【図２】本発明の例示的な第１の実施の形態の動作を示す流れ図である。
【図３】本発明の例示的な第１の実施の形態の動作の具体例を説明するための図である。
【図４】本発明の例示的な第２の実施の形態の構成を示す図である。
【発明を実施するための形態】
【００３８】
次に、本発明の実施の形態について図面を参照して詳細に説明する。本発明によれば、幅優先探索に基づき、条件部・前提部のサイズの小さなルール（ＣＦＤ）の候補から順に生成し、妥当なルールが発見された時点で、当該ルールに対して、冗長となるルールを、以降に行われるルール候補の探索から、除外するように枝刈り（Pruning）を行うことで、ほぼ成り立つルール（approximate CFD）を効率よく列挙することができる。
【００３９】
データベースと、設定パラメータとに基づき、データベースの内容に合致した、ほぼ成り立つルール（approximate CFD）の集合を計算する。より具体的には、データベースの内容と、設定パラメータまたは生成済みルールの候補に基づき、新たなルールの候補を生成するルール候補生成手段（装置）（図１の２１）と、前記ルールの候補がデータベースの内容に対して妥当であるかチェックするルールの妥当性判定手段（装置）（図１の２２）とを有する。
【００４０】
ルール候補生成手段（装置）（図１の２１）はデータベースの内容、または以前のステップで得られたアイテムセット（itemset）から、ルール（ＣＦＤ）の候補を生成し、該ルールが妥当である場合に、冗長なルールを出力しないように、枝刈りを行う。最終的に、ルール候補生成手段（装置）（図１の２１）で生成されるルール（ＣＦＤ）候補が空になったとき（ルール（ＣＦＤ）の候補の生成ができなくなったとき）、ルール発見の計算を終了する。
【００４１】
一つの側面のシステムの実施形態によれば、データベースを記憶する記憶装置（図１の３）と、データ処理装置（図１の２）と、出力装置（図１の４）と、を備えたシステムにおいて、前記データ処理装置（２）は、前記データベースからルール候補を生成するルール候補生成手段（図１の２１）と、前記ルール候補が前記データベースの内容に対して妥当であるか否か判定するルールの妥当性判定手段（図１の２２）と、を備えている。
【００４２】
前記ルール候補生成手段（図１の２１）は、前記データベースにおける属性と値のペアからなるアイテムであって、前記データベースでの頻度が、予め定められた所定の閾値以上のアイテムの集合を生成し、ルール候補の初期値として、条件部・前提部を空、帰結部を前記アイテムとするルール集合を生成して記憶部に記憶する。
【００４３】
前記ルールの妥当性判定手段（図１の２２）は、前記ルール候補生成手段で生成された前記ルール候補の各ルールに対して、前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合、前記ルールを妥当と判定して前記出力装置（図１の４）に出力する。妥当性を判定する前記ルール候補が空となると、前記ルール候補生成手段（図１の２１）では、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも、１つ増やした新たなルール候補を生成して記憶部に記憶する。前記ルール候補生成手段（図１の２１）で生成された前記新たなルール候補に対する前記ルールの妥当性判定手段（図１の２２）による妥当性のチェック（図２のＡ３、Ａ４、Ａ５）と、
前記ルール候補生成手段（図１の２１）による条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした新たなルール候補の生成（図２のＡ６）と、
を、前記ルール候補生成手段（図１の２１）にて、条件部・前提部のサイズを、前回生成した前記ルール候補よりも１つ増やした、新たなルール候補を生成することができず、このため、前記新たなルール候補が空となる、まで、繰り返す（図２のＡ３〜Ａ７）。
【００４４】
別の側面のルール発見方法の実施形態によれば、以下のステップを含む。
（ａ）ルール候補生成手段（図１の２１）が、データベースを読み出し、前記データベースの属性と値のペアからなり頻度が予め定められた所定の閾値以上のアイテムを生成し（図２のステップＡ１）、ルール候補の初期値として、条件部・前提部を空、帰結部を前記アイテムとするルール集合を生成して記憶部に記憶し（図２のステップＡ２）、
（ｂ）ルールの妥当性判定手段（図１の２２）は、前記生成されたルール候補のルールに対して、前記ルールの条件部・前提部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合には、前記ルールを妥当と判定して出力装置より出力し（図２のステップＡ３、Ａ４）、
（ｃ）妥当性判定対象の前記ルール候補が空か否か（まだ残っているか否か）チェックし、妥当性判定対象の前記ルール候補が空でない場合、前記ルールの妥当性判定手段は、前記ステップ（ｂ）に戻り（図２のステップＡ５）、
（ｄ）妥当性判定対象の前記ルール候補が空の場合（妥当性判定を全てのルール候補について行ってしまった場合）、前記ルール候補生成手段は、前記アイテムを新たな条件部・前提部とし、前記条件部・前提部のサイズを、前回生成した前記ルール候補よりも、１つ増やした、新たなルール候補を生成して記憶部に記憶し（図２のステップＡ６）、
（ｅ）前記ステップ（ｄ）で新たなルール候補が生成されず、前記新たなルール候補が空か否か判定し（図２のステップＡ７）、前記新たなルール候補が空の場合、ルールの発見を終了し、前記新たなルール候補が空でない場合、前記ステップ（ｂ）に戻る。
【００４５】
本発明によれば、データベースのデータのルールの発見において、ほぼ成り立つルール（approximate CFD）発見の高速化を実現し、データベースの内容把握、修正のために有用なルールの発見に好適とされる。以下、実施形態に即して詳細に説明する。
【００４６】
＜実施形態１＞
図１を参照すると、本発明の例示的な第１の実施の形態は、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置２と、記憶装置３と、ディスプレイ装置や印刷装置等の出力装置４を含む。
【００４７】
記憶装置３は、磁気ディスク装置等で構成されるデータベース記憶部３１を備えている。データベース記憶部３１は、データベースを記憶している。このデータベースのデータをデータ処理装置２で読み出してＣＦＤのルールが抽出される。
【００４８】
データ処理装置２は、ルール候補生成手段２１と、ルールの妥当性判定手段２２とを備える。
【００４９】
ルール候補生成手段２１は、データベース記憶部３１に記憶されたデータベースのルール候補を生成する。ルール候補の生成にあたり、ルール候補生成手段２１は、入力装置１から与えられたパラメータや、以前のステップで生成されたルール候補（生成済みルール候補）を用いてルール候補を生成し、生成したルール候補を記憶部に記憶する。記憶部は、データ処理装置２内の不図示の記憶部（メモリ装置）であってもよいし、ルール候補生成手段２１内の不図示の記憶部、あるいは、記憶装置３内の所定の記憶領域であってもよい。
【００５０】
ルールの妥当性判定手段２２は、ルール候補生成手段２１によって生成されたルールに対して、それが妥当なルールであるか否かをチェックし、妥当なルールである場合、出力装置４にそのルールを出力する。
【００５１】
ここで、「妥当である」とは、
・ルールとマッチするデータベース中のタプルの個数が、予め定められた頻度の閾値以上であり、且つ、
・ルールの帰結部とタプルの内容が、確信度の閾値以上で合致している、
ことを意味している。入力装置１から与えられた前記パラメータは、頻度の閾値や確信度の閾値を含み、該パラメータは、ルール候補生成手段２１で参照される。
【００５２】
図２は、本実施の形態の動作を説明する流れ図である。図１及び図２を参照して、本実施の形態の動作について詳細に説明する。
【００５３】
入力装置１から与えられたパラメータ、及び、データベース記憶部３１から与えられたデータベースの内容は、ルール候補生成手段２１に供給される。ルール候補生成手段２１は、データベース中に出現している属性と値のペア（これを「アイテム」（item）と呼ぶ）を生成する（ステップＡ１）。ルール候補生成手段２１は、生成したアイテム集合を、データ処理装置２内の不図示の記憶部又はルール候補生成手段２１内の不図示の記憶部、又は記憶装置３の所定の記憶領域に記憶される。
【００５４】
ルール候補生成手段２１は、
・生成したアイテムの集合の中から、頻度（frequency）が、パラメータ（頻度閾値）ｋ以上であるものすべてを抽出し、
・条件部（条件部・前提部）が空、抽出されたアイテムが帰結部となるルールを生成し、
・これをルールの初期候補（ＣＦＤ候補）とする（ステップＡ２）。ルール候補生成手段２１は、生成したルールの初期候補（ＣＦＤ候補）を、データ処理装置２内の不図示の記憶部、又はルール候補生成手段２１内の不図示の記憶部、又は記憶装置３の所定の記憶領域に記憶する。なお、図２では、ルールの条件部・前提部（ＬＨＳ）を、条件部として示している。
【００５５】
ルールの妥当性判定手段２２は、ルール候補生成手段２１で生成されたルールの候補（ＣＦＤ候補）を、データベース記憶部３１に保存されているデータベースと照合し、ルールが妥当なものであるかチェックを行う。具体的には、ルールの妥当性判定手段２２は、
ルールの条件部がマッチするデータベースのタプルに対して、ルールの帰結部とタプルの内容が、パラメータ（確信度の閾値）ｐ以上でマッチしている場合、
妥当なものであると判定する（ステップＡ３のＹｅｓ）。
【００５６】
ルールの妥当性判定手段２２は、ルール候補から妥当なルールが得られたとき、該妥当なルール（ＣＦＤ）を出力装置４に出力する（ステップＡ４）。ルールが妥当でない場合、出力装置４には出力されない。
【００５７】
ルールの妥当性判定手段２２によりルールが妥当と判定された場合、ルール候補生成手段２１では、よりサイズの大きいルール候補の生成にあたり、前記妥当と判定されたルールの帰結部となるアイテムを、帰結部に含むルールは、ルール候補として生成しない。すなわち、よりサイズの大きいルール候補の枝刈り（Pruning）を行う。
【００５８】
ステップＡ３、Ａ４を繰り返し、妥当性判定対象のルールの候補（ＣＦＤ候補）が無くなったとき（すなわち、ルール候補が空になったとき）（ステップＡ５のＹｅｓ）、ルール候補生成手段２１は、前記アイテムを新たな条件部とし、条件部のサイズを、前回よりも１つ増やした新たなルール候補（ＣＦＤ候補）を生成する（ステップＡ６）。
【００５９】
ルール候補生成手段２１は、ステップＡ６で生成した新たなルール候補が空か否か判定する（ステップＡ７）。
【００６０】
ステップＡ６で生成した新たなルール候補が空の場合、ルール発見の計算処理を終了する（ステップＡ７のＹｅｓ）。
【００６１】
ステップＡ６で生成した新たなルール候補（ＣＦＤ候補）が空でない場合、ステップＡ３に戻り、ルールの妥当性判定手段２２により妥当なルールであるか判定し、妥当なルールを出力する。
【００６２】
ステップＡ３〜Ａ７の一連の処理を、ステップＡ７の判定の結果、ルール候補生成手段２１において、ルール候補（ＣＦＤ候補）をそれ以上生成されなくなるまで、繰り返す。
【００６３】
このように、本実施の形態においては、
頻度の所定値以上のアイテム（item）の列挙から始まり、それらを組み合わせることで、小さなサイズのルール候補（ＣＦＤ候補）から開始し、徐々に、サイズの大きいルール候補（ＣＦＤ候補）を生成していく。妥当なルール（確信度が閾値以上のルール）が得られた時点で、当該ルールを出力し、当該ルールに対して冗長なルールの生成を抑制することで、ルールを効率よく発見することが可能となる。
【００６４】
次に、具体的な実施例を用いて本実施の形態の動作を説明する。図３（Ｂ）（以下の表１）に示すように、例えば、データベース記憶部３１には、以下の表１の属性・タプルからなるデータ集合が登録されている。なお、データベースの例は、あくまで説明のために簡易化した例である。図３（Ａ）は、図２のステップに対応して、アイテム集合、初期ルール（ＣＦＤ）の候補、新たなルール（ＣＦＤ）候補の具体例を例示したものである。図３（Ｃ）は、図２の計算の結果、出力装置４から出力されたルール（approximate CFD）の一例を示す図である。なお、図３において、“属性１：＿”等における記号‘：’は、“属性１＝＿”における記号‘＝’と同義（同一）である。
【００６５】
＜表１＞
2013172308.tif 000003
【００６６】
ルール候補生成手段２１は、上記の表１、及びパラメータとして、
ｋ＝２、ｐ＝０．６６
を受け取る。
ここで、
ｋは妥当なルールと判定するための頻度の閾値（下限）、
ｐは確信度の閾値（下限）である。
【００６７】
ルール候補生成手段２１は、データベース中の出現頻度がｋ＝２以上であるすべてのアイテム（item）のリスト（アイテムの集合）：｛
“属性１＝＿”（４），
“属性２＝＿”（４），
“属性３＝＿”（４），
“属性１＝１”（２），
“属性２＝Ｐ”（３），
“属性３＝Ｓ”（２），
“属性３＝Ｔ”（２）｝を抽出する。ここで、記号＿は、任意の値にマッチする変数である。括弧の中の数値は、そのアイテム（item）の頻度である。“属性１＝＿”の‘＿’は「unnamed variable」（無名変数）であり、任意の属性値とマッチするワイルドカードである。
【００６８】
ルール候補生成手段２１は、上記抽出されたリスト内の各アイテム（item）に対し、条件部・前提部（ＬＨＳ）を空（empty）とし、抽出された各々のアイテム（item）を帰結部（ＲＨＳ）とするＣＦＤルールを生成し、これをルール（ＣＦＤ）の初期候補として、不図示の記憶部に一時的に記憶する（図２、図３（Ａ）のステップＡ１）。
【００６９】
この場合、ルール（ＣＦＤ）の初期候補は以下の通りである。
ψ１：empty →“属性１＝＿”、
ψ２：empty →“属性２＝＿”、
ψ３：empty →“属性３＝＿”、
ψ４：empty →“属性１＝１”、
ψ５：empty →“属性２＝Ｐ”、
ψ６：empty →“属性３＝Ｓ”、
ψ７：empty →“属性３＝Ｔ”
【００７０】
ルールψ５において、空（empty）の頻度は、（タプルの全個数と同じ）４、“属性２＝Ｐ”の頻度は、３である。
したがって、“属性２＝Ｐ”の頻度（＝３）と、空（empty）の頻度（＝４）との割合（確信度）＝３／４＝０．７５である。これは、確信度の閾値（下限）ｐ＝０．６６を上回っている。
【００７１】
そこで、ルールの妥当性判定手段２２は、
ψ５：  empty→“属性２＝Ｐ”  
を妥当なものであることを発見し（図２、図３（Ａ）のステップＡ３）、これを出力装置４に出力する（図２、図３（Ａ）のステップＡ４）。
【００７２】
それとともに、このψ５に対して冗長なルールを、以後のルール候補の探索の対象から除外する。具体的には、後のステップ（図２、図３（Ａ）のステップＡ６）にて、ルール候補生成手段２１では、
アイテム（item）“属性２＝Ｐ”
を含むアイテムセット（itemset）が生成されたとき、それに対する帰結部（ＲＨＳ）の候補から、“属性２＝Ｐ”を除去する。
【００７３】
残りの６つのルール（ψ１〜ψ４、ψ６、ψ７）は、データベースの内容に対して妥当ではない。この結果、ルール（ＣＦＤ）の候補は空となる（図２のステップＡ５のＹｅｓ）。
【００７４】
ルールの候補（｛ψ１、ψ２、・・・、ψ７｝）のうち、ルールの妥当性判定手段２２によって、データベースの内容に対して妥当と判定されたルール（ＣＦＤ）ψ５は、出力装置４に出力される。なお、ルールの候補のうち、妥当性の判定が行われたルールは、ルールの候補から削除される。すなわち、ルールの候補（｛ψ１、ψ２、・・・、ψ７｝）のうち、ルールの妥当性判定手段２２によって妥当性の判定が行われ、妥当と判定されたルール（ＣＦＤ）ψ５、及び、妥当でないと判断されたルール（ψ１〜ψ４、ψ６、ψ７）は、ルールの候補から削除され、その結果、妥当性がチェックされるルールの候補は、空（残りは零）となる。なお、ルールのルール候補からの削除等は、メモリからの削除以外に、例えば１ビット等の削除フラグを、ルール候補の各ルールに対して用意する構成としてもよい。この場合、ルール候補の複数のルールの削除ビット（複数のビット）が全てオンのとき、ルール候補は、空と判断される。
【００７５】
妥当性判定対象のルールの候補(ＣＦＤ候補)が空であるため（図２のステップＡ５のＹｅｓ）、ルール候補生成手段２１は、新たなルールの生成を行う（図２、図３（Ａ）のステップＡ６）。具体的には、アイテム（item）の上記集合から、互いに矛盾せず（同一の属性が異なる値をとらない）、合成後の集合のサイズが、合成前のものよりも、１だけ大きく、また、頻度が閾値ｋ以上となる２つの要素を選んで合成し（合成したものをアイテムセット（itemset）という）、要素のうち１つを帰結部、残りを条件部・前提部とした、ルールを生成する（図２、図３（Ａ）のステップＡ６）。
【００７６】
ここで先に述べた通り、２つのアイテム（item）：
“属性２＝Ｐ”、
“属性３＝Ｔ”
を合成して得られるアイテムセット
｛“属性２＝Ｐ”、“属性３＝Ｔ”｝
からは、帰結部の候補として、“属性２＝Ｐ”が除外される。
【００７７】
したがって、ルール候補生成手段２１において、
ルール：“属性３＝Ｔ”→“属性２＝Ｐ”
は生成されない。
【００７８】
ルール候補生成手段２１で新たに生成されたルール候補（図２、図３（Ａ）のステップＡ６）のうち、
ＣＦＤ  ψ’１：“属性１＝＿”→”属性３＝＿”
（属性１の値が、属性３の値を一意に決定する）
は妥当なものである（頻度＝４、確信度＝１）と、ルールの妥当性判定手段２２によって判定され（図２、図３（Ａ）のステップＡ３）、ψ’が出力装置４から出力される（ステップ４）。また、これとともに、ψ’に対して冗長なルールは、以後のルール候補の探索の対象から除外される。
【００７９】
同様に、ルールの妥当性判定手段２２によって、条件部・前提部のサイズが１である妥当なルール（頻度がｋ＝２以上、且つ、確信度がｐ＝０．６６以上）として
ψ’２：“属性３＝＿”→”属性１＝＿”、
ψ’３：“属性２＝＿”→”属性３＝＿”、
ψ’４：“属性３＝Ｓ”→”属性１＝１”、
ψ’５：“属性１＝１”→”属性３＝Ｓ”、
ψ’６：“属性２＝Ｐ”→”属性３＝Ｔ”
が発見され（図２、図３（Ａ）のステップＡ３、Ａ４）、これらのルールが、出力装置４に出力される（図２のステップ４）とともに、これらのルールに対し、冗長なルールをそれぞれ除外する。
【００８０】
ルールの妥当性判定手段２２によって、条件部・前提部がサイズ１の６個のルール（ＣＦＤ）候補のうち、６個のルール候補の妥当性の判定が行われたため（妥当性有りと判定）、妥当性のチェックが行われるルール（ＣＦＤ）候補は空となる（図２のステップＡ５のＹｅｓ）。
【００８１】
そこで、ルール候補生成手段２１において、条件部・前提部のサイズを１つ増やしたルール（ＣＦＤ）の候補を生成しようとするが、条件部・前提部のサイズ＝２のルール候補は何も生成されず、条件部・前提部のサイズ＝２のルール（ＣＦＤ）の候補は空であるため、ルール発見アルゴリズムが終了する（ステップＡ７のＹｅｓ）。
【００８２】
得られるＣＦＤは、図３（Ｃ）に示すように、
empty →“属性２＝Ｐ”          ：頻度＝３  確信度＝０．７５
“属性１＝＿”→“属性３＝＿”  ：頻度＝４  確信度＝１
“属性３＝＿”→“属性１＝＿”  ：頻度＝４  確信度＝０．７５
“属性２＝＿”→“属性３＝＿”  ：頻度＝４  確信度＝０．７５
“属性３＝Ｓ”→“属性１＝１”  ：頻度＝２  確信度＝１
“属性１＝１”→“属性３＝Ｓ”  ：頻度＝２  確信度＝１
“属性２＝Ｐ”→“属性３＝Ｔ”  ：頻度＝２  確信度＝０．６６
【００８３】
なお、図３（Ｃ）に示す出力例では、妥当と判定されたルールの頻度、確信度が出力されているが、ルールの頻度、確信度のうちの一方を出力するか、あるいはともに出力しなくてもよい。また、妥当と判定されたルールが多量である場合、例えば確信度の順にルールをソートして出力するようにしてもよい。妥当と判定されたルールの出力形態自体は任意である。
【００８４】
ここで、枝刈り（Pruning）を行わない場合、図２の計算処理の途中で、アイテムセット（itemset）
｛“属性２＝Ｐ”，“属性３＝Ｔ”｝から
ＣＦＤ  ψ：“属性３＝Ｔ”→”属性２＝Ｐ”
等の冗長なルール（ＣＦＤ）が生成される。
【００８５】
これに対して、本実施形態によれば、枝刈りを行うことにより、上記のような冗長なルールの生成を防ぐことができる。
【００８６】
＜実施の形態２＞
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。図４を参照すると、本発明の第２の実施の形態は、ルール発見用プログラム５を備える。
【００８７】
ルール発見用プログラム５は、データ処理装置６に読み込まれ、データ処理装置６の動作を制御する。データ処理装置６はルール発見用プログラム５の制御により以下の処理、すなわち第１の実施の形態におけるデータ処理装置２による処理と同一の処理、を実行する。ルール発見用プログラム５は、
（ａ）データベースを読み出し、前記データベースの属性と値のペアからなり頻度が予め定められた所定の閾値以上のアイテムを生成し、ルール候補の初期値として、条件部が空、帰結部が、前記アイテムであるルール（ＣＦＤ）を生成して記憶部に記憶する処理と、
（ｂ）前記生成されたルール候補のルール（ＣＦＤ）に対して、前記ルールの条件部とマッチする前記データベースのタプルに対して、前記ルールの帰結部が、予め定められた所定の確信度の閾値以上でマッチしている場合には、前記ルールを妥当（approximate CFD）と判断し、出力装置に出力する処理と、
（ｃ）妥当性を判定する前記ルール候補（ＣＦＤ候補）が空でない場合、前記（ｂ）に戻る処理と、
（ｄ）妥当性を判定する前記ルール候補（ＣＦＤ候補）が空の場合、前記アイテムを新たな条件部とし、前記条件部のサイズを、前回生成した前記ルール候補よりも、１つ増やした新たなルール候補（新たなＣＦＤ候補）を生成して記憶部に記憶する処理と、
（ｅ）前記（ｄ）の処理で生成される前記新たなルール候補が空か否か判定し、前記新たなルール候補（新たなＣＦＤ候補）が空の場合、ルール発見処理を終了し、前記新たなルール候補（新たなＣＦＤ候補）が空でない場合、前記（ｂ）に戻る処理と、
を含む。
【００８８】
なお、前記（ｂ）の妥当と判定したルール（approximate CFD）を出力装置に出力する処理において、該ルール（approximate CFD）を直ちに出力装置に出力するかわりに、当該ルールを一旦、リスト（線形リスト等）に加え、妥当性を判定する前記ルール候補（ＣＦＤ候補）が空となったときに、該リストを出力するようにしてもよい。なお、リストは、記憶装置バッファ等に記憶される。妥当と判定したルールを出力する出力制御としては、任意の方式を用いられる。
【００８９】
入力装置１から、コマンド（ルール発見プログラムの実行コマンド等）、設定パラメータが入力され、記憶装置３内のデータベース記憶部３１に記憶されているデータベースを用い、初期ルール候補の生成を行う。次に、生成されたルール候補が妥当であるか否か判定し、妥当である場合、当該ルールをリストに追加する。リストに保存されたルールの集合により、データベースのカバー度が打ち切り条件を満たした時、リスト内のルール集合を、出力装置４に表示させる。
【００９０】
なお、上記の特許文献、非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【００９１】
１  入力装置
２、６  データ処理装置
３  記憶装置
４  出力装置
５  ルール発見用プログラム
２１  ルール候補生成手段
２２  ルールの妥当性判定手段
３１  データベース記憶部
【図１】
2013172308.tif 000004
【図２】
2013172308.tif 000005
【図３】
2013172308.tif 000006
【図４】
2013172308.tif 000007
【国際調査報告】
2013172308.tif 000008
2013172308.tif 000009