(57)【要約】  データベースの内容を把握し、あるいは修正を行うために、有用なルールの集合を効率よく得ることを可能とする。システムは、データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットの集合を生成するフリーアイテムセット生成手段２１と、前記生成されたフリーアイテムセットを、条件部に、前記フリーアイテムセットと属性を共有しないアイテムを帰結部に置き、確信度が予め定められた確信度閾値以上のルール候補を生成して保存する妥当なルール候補生成手段２２と、生成されたルール候補に対して極小性のチェックを行い、極小である場合に出力装置４に出力するルールの極小性判定手段２３を備える（図１)。
2013172309.tif 000002
【特許請求の範囲】
【請求項１】
データベースを記憶する記憶装置と、
データ処理装置と、
出力装置と、
を備え、
前記データ処理装置は、
前記データベースにおける属性と値のペアのアイテムの集合からなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットを生成するフリーアイテムセット生成手段と、
前記生成されたフリーアイテムセットを、条件部に置き、且つ、前記フリーアイテムセットと属性を共有しないアイテムを、帰結部に置いたルール候補であって、その確信度が予め定められた確信度閾値以上のルール候補を生成して記憶部に保存する妥当なルール候補生成手段と、
前記妥当なルール候補生成手段によって生成された前記ルール候補に対して、極小性のチェックを行い、前記ルール候補が極小である場合、前記出力装置に出力する、ルールの極小性判定手段と、
を備えた、ことを特徴とするルール発見システム。
【請求項２】
前記ルールの極小性判定手段は、前記妥当なルール候補生成手段によって生成された複数の前記ルール候補からなるルール候補群のリストに対し、前記ルール候補のサイズの昇順にソートし、
前記リストの先頭から順に、極小な前記ルール候補を取り出して前記出力装置に出力し、
前記リスト中の残りの前記ルール候補のうち、前記出力した極小な前記ルール候補に対して、冗長なルール候補を、前記リストから除去する、ことを特徴とする請求項１記載のルール発見システム。
【請求項３】
前記妥当なルール候補生成手段は、各フリーアイテムセットαに対して、１つのアイテムｘを追加したアイテムセットの頻度を計算し、
前記フリーアイテムセットαに対して１つのアイテムｘを追加した前記アイテムセットの頻度の、前記フリーアイテムセットαの頻度に対する割合が、前記確信度閾値以上の場合、
前記フリーアイテムセットαを条件部とし、
前記１つのアイテムｘを帰結部とするルールを、ルール候補として、前記リストに追加する処理を、
前記フリーアイテムセット生成手段で生成された、全てのフリーアイテムセットα、アイテムｘに対するチェックが終了するまで、繰り返して行う、ことを特徴とする請求項１又は２記載のルール発見システム。
【請求項４】
前記頻度の閾値と前記確信度の閾値を設定パラメータとして入力する入力装置を備えている、ことを特徴とする請求項１乃至３のいずれか１項に記載のルール発見システム。
【請求項５】
前記ルールは、ＣＦＤ（Ｃｏｎｄｉｔｉｏｎａｌ  Ｆｕｎｃｔｉｏｎａｌ  Ｄｅｐｅｎｄｅｎｃｙ）で表現されたルールである、ことを特徴とする請求項１乃至４のいずれか１項に記載のルール発見システム。
【請求項６】
フリーアイテムセット生成手段と、妥当なルール候補生成手段と、ルールの極小性判定手段とを備えたデータ処理装置によりデータベースからルールを発見するにあたり、
（ａ）前記フリーアイテムセット生成手段が、前記データベースを読み込み、前記データベースにおける属性と値のペアのアイテムの集合からなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットの集合を生成して記憶部に記憶し、
（ｂ）前記妥当なルール候補生成手段は、前記フリーアイテムセットを条件部に置き、且つ、前記フリーアイテムセットと属性を共有しないアイテムを帰結部に置いたルール候補であって、その確信度が予め定められた閾値以上のルール候補を生成して記憶部に保存し、
（ｃ）前記ルールの極小性判定手段は、前記妥当なルール候補生成手段によって生成された前記ルール候補に対して極小性のチェックを行い、前記ルール候補が極小である場合、出力装置に出力する、ことを特徴とするルール発見方法。
【請求項７】
前記ルールの極小性判定手段は、前記生成された複数の前記ルール候補からなるルール候補群のリストに対して、前記ルール候補のサイズの昇順にソートし、
前記リストの先頭から順に、極小な前記ルール候補を取り出して前記出力装置に出力し、
前記リスト中の残りの前記ルール候補のうち、前記出力した極小な前記ルール候補に対して冗長なルール候補を、前記リストから除去する、ことを特徴とする請求項６記載のルール発見方法。
【請求項８】
（ａ）データベースを読み込み、前記データベースにおける属性と値のペアのアイテムの集合からなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットの集合を生成して記憶部に記憶する処理と、
（ｂ）前記生成されたフリーアイテムセットを、条件部に置き、且つ、前記フリーアイテムセットと属性を共有しないアイテムを、帰結部に置いたルール候補であって、その確信度が予め定められた閾値以上のルール候補を生成して記憶部に保存する処理と、
（ｃ）前記生成された前記ルール候補に対して極小性のチェックを行い、前記ルール候補が極小である場合、出力装置に出力する処理と、
をコンピュータに実行させるプログラム。
【請求項９】
前記（ｃ）の前記ルール候補が極小である場合、出力装置に出力する処理は、
前記生成された複数の前記ルール候補からなるルール候補群のリストに対し、前記ルール候補のサイズの昇順にソートし、
前記リストの先頭から順に極小な前記ルール候補を取り出して前記出力装置に出力し、前記リスト中の残りの前記ルール候補のうち、前記出力した極小な前記ルール候補に対して冗長なルール候補を、前記リストから除去する、ことを特徴とする請求項８記載のプログラム。
【請求項１０】
データベースを読み込み、前記データベースにおける属性と値のペアからなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットの集合を生成するフリーアイテムセット生成手段と、
前記生成された各フリーアイテムセットαを条件部に置き、前記フリーアイテムセットと属性を共有しない１つのアイテムｘを帰結部に置いたアイテムセットの頻度を計算し、
前記フリーアイテムセットαに対して１つのアイテムｘを追加した前記アイテムセットの頻度に対する、前記フリーアイテムセットαの頻度の割合が、予め定められた所定の確信度閾値以上の場合、前記フリーアイテムセットαを条件部とし、前記１つのアイテムｘを帰結部とするルールをルール候補として、リストに追加する妥当なルール候補生成手段と、
前記妥当なルール候補生成手段によって生成された複数のルールからなるルール候補群の前記リストに対し、前記ルール候補のサイズの昇順にソートし、
前記リストの先頭から順に、極小な前記ルール候補を取り出して前記出力装置に出力し、前記リスト中の残りの前記ルール候補のうち、前記出力した極小な前記ルール候補に対して冗長なルール候補を、前記リストから除去することで、極小でないルール候補の除去を行う、ルールの極小性判定手段と、
を備えた、ことを特徴とするルール発見装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１２−１１０９２２号（２０１２年  ５月１４日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、ルールの発見を行う技術に関し、特にデータベースのルールの発見を行うシステムと方法と装置並びにプログラムに関する。
【背景技術】
【０００２】
データベースのルールの発見は、例えばルールをＣＦＤ（Conditional Function Dependency：条件付関数帰結部）として表現するものとし、生成されたＣＦＤルールの候補から、データベースの内容に合致したＣＦＤルールを出力する。以下では、発明の理解の前提となるＣＦＤについて概説する。【０００３】
ＣＦＤは、データ属性間の帰結部を表す関数帰結部（Functional Dependency：「ＦＤ」と略記される）が、条件によって指定されたタプル集合について成立することを表すルールである。ルールの左辺（ＬＨＳ：Left Hand Side）である条件部、前提部と、ルールの右辺（ＲＨＳ：Right Hand Side）の帰結部における属性値の指定からなる。なお、条件部、帰結部は、それぞれ条件節、従属節ともいう。【０００４】
条件部は、データの部分集合（タプル集合）を指定し、属性Ｘが属性値ｘであるということを「Ｘ＝ｘ」と表す。ここで、「ｘ」は属性値がある特定の値であることを意味する。このような、属性値の表現を「コンスタント（Constant）である」という（なお、「Constant」は例えば「定数」を意味する）。【０００５】
また、前提部は、属性のみの指定からなり、属性値は特定の値をとらない（すなわち、任意の値とマッチすることを表すワイルドカード）ことを「Ｘ＝ _ 」と表す。このような属性値の表現を「バリアブル（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」であるという。【００１８】
例えば、以下のルール５、ルール６が与えられた時、ルール６の属性値ｘ２をバリアブル（Variable）に置き換えることで、ルール５を得ることができる。このため、ルール６は「most-general」でない。逆に、ルール５は「most-general」であるという。この場合、ルール６は、ルール５に対して冗長なＣＦＤとして削除することができる。【００１９】
ルール５：  Ｘ１，Ｘ２→Ａ（ｘ１，＿ || ａ）
ルール６：  Ｘ１，Ｘ２→Ａ（ｘ１，ｘ２ || ａ）【００２０】
以上でＣＦＤの概説を終える。【００２１】
データベースからルールを発見する装置は、ＣＦＤを保存する磁気ディスク等の記憶手段（記憶部）と、ＣＦＤの候補を生成し、ＣＦＤ候補がデータベースの内容に合致しているか判定する演算手段（演算部）と、内容に合致していると判定されたＣＦＤを記憶装置に保存する保存手段（保存部）から構成される。記憶手段は、ルール発見アルゴリズムで得られたＣＦＤを保存する。演算手段は、チェックの対象とするＣＦＤの候補を生成し、それがデータベースの内容に合致しているかどうか調べ、合致している場合、妥当（valid）なＣＦＤとして出力する。保存手段は、得られた妥当なＣＦＤを、記憶装置に保存する。【００２２】
データベースのルールの発見手法として、例えば非特許文献１に記載されているように、
（１）フリーアイテムセット（free itemset）と、それに対応するクローズド・アイテムセット（closed itemset）からコンスタントＣＦＤ（constant CFD）の候補を生成する手法、
（２）属性と値のペアのリストを、幅優先探索（breadth first search）により生成し、そのうちの１つの項を従属項（Ａとする）、残りを条件部（Ｘとする）に置き、
式：Ｘ→Ａ
を得ることによって、ＣＦＤの候補を生成する手法、
（３）フリーアイテムセット（free itemset）を条件項、フリーアイテムセット（free itemset）に含まれない１つの属性を従属項（帰結部）に置き、それ以外に条件項に加える属性を、深さ優先探索（depth first search）することで、ＣＦＤの候補を生成する手法、
等がある。【００２３】
フリーアイテムセット（free itemset）とは、アイテム（item）の集合であり、任意の１つ以上のアイテム（item）を除去することで、頻度が真に増加してしまうものである。データベース中に出現している属性と値のペアを「アイテム」（item）と呼び、アイテムの集合をアイテムセット（itemset）という。【００２４】
前述したように、データベースの内容とＣＦＤがどの程度一致しているかを表す指標として、確信度がある。【００２５】
データベースの内容と完全には一致していないが、高い確信度（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）を発見するアルゴリズムは、計算時間が極端に長くなる、ということである。その理由は、大規模な、特に、属性数の大きいデータベースに対して、生成されるＣＦＤ（approximate CFD）の候補の個数が組合せ爆発（combinational explosion）を起こしてしまうためである。【００３２】
本発明は、上記問題点に鑑みて創案されたものであって、その目的は、データベースの内容を把握し、あるいは修正を行うために有用なルールの集合を効率よく得ることができるシステム、装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００３３】
本発明によれば、データベースを記憶する記憶装置と、データ処理装置と、出力装置と、を備え、前記データ処理装置は、
前記データベースにおける属性と値のペアのアイテムの集合からなるフリーアイテムセット（free itemset）であって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセット（frequent  free itemset）を生成するフリーアイテムセット生成手段と、
前記生成されたフリーアイテムセットを条件部に、前記フリーアイテムセットと属性を共有しないアイテムを帰結部に置き、確信度が予め定められた確信度閾値以上のルール候補を生成して記憶部に保存する妥当なルール候補生成手段と、
前記妥当なルール候補生成手段によって生成されたルール候補に対して極小性のチェックを行い、前記ルール候補が極小である場合、前記出力装置に出力するルールの極小性判定手段と、を備えたルール発見システムが提供される。【００３４】
本発明の別の側面によれば、フリーアイテムセット生成手段と、妥当なルール候補生成手段と、ルールの極小性判定手段とを備えたデータ処理装置によりデータベースからルールを発見するにあたり、
（ａ）前記フリーアイテムセット生成手段が、前記データベースを読み込み、前記データベースにおける属性と値のペアのアイテムの集合からなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットの集合を生成して記憶部に記憶し、
（ｂ）前記妥当なルール候補生成手段は、前記フリーアイテムセットを条件部に、前記フリーアイテムセットと属性を共有しないアイテムを帰結部に置き、確信度が予め定められた閾値以上のルール候補を生成して記憶部に保存し、
（ｃ）前記ルールの極小性判定手段は、前記妥当なルール候補生成手段によって生成されたルール候補に対して極小性のチェックを行い、前記ルール候補が極小である場合、出力装置に出力する、ルール発見方法が提供される。【００３５】
本発明のさらに別の側面によれば、
（ａ）データベースを読み込み、前記データベースにおける属性と値のペアのアイテムの集合からなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットの集合を生成して記憶部に記憶する処理と、
（ｂ）各フリーアイテムセットを条件部に、前記フリーアイテムセットと属性を共有しないアイテムを帰結部に置き、確信度が予め定められた閾値以上のルール候補を生成して記憶部に保存する処理と、
（ｃ）前記生成されたルール候補に対して極小性のチェックを行い、前記ルール候補が極小である場合、出力装置に出力する処理と、
をコンピュータに実行させるルール発見プログラムが提供される。本発明によれば、該ルール発見プログラムを記録したメモリデバイス、磁気／光ディスク等のストレージ媒体／デバイスが提供される。【００３６】
本発明のさらに別の側面によれば、データベースを読み込み、前記データベースにおける属性と値のペアからなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットの集合を生成するフリーアイテムセット生成手段と、
前記生成された各フリーアイテムセットαを条件部に置き、前記フリーアイテムセットと属性を共有しない１つのアイテムｘを帰結部に置いたアイテムセットの頻度を計算し、
前記フリーアイテムセットαに対して１つのアイテムｘを追加した前記アイテムセットの頻度に対する、前記フリーアイテムセットαの頻度の割合が、予め定められた所定の確信度閾値以上の場合、前記フリーアイテムセットαを条件部とし、前記１つのアイテムｘを帰結部とするルールをルール候補として、リストに追加する妥当なルール候補生成手段と、
前記妥当なルール候補生成手段によって生成された複数のルールからなるルール候補群の前記リストに対し、前記ルール候補のサイズの昇順にソートし、
前記リストの先頭から順に、極小な前記ルール候補を取り出して前記出力装置に出力し、前記リスト中の残りの前記ルール候補のうち、前記出力した極小な前記ルール候補に対して冗長なルール候補を、前記リストから除去することで、極小でないルール候補の除去を行う、ルールの極小性判定手段と、
を備えたルール発見装置が提供される。
【発明の効果】
【００３７】
本発明によれば、データベースの内容を把握し、あるいは修正を行うために有用なルールの集合を効率よく得ることができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の例示的な第１の実施の形態の構成を示す図である。
【図２】本発明の例示的な第１の実施の形態の動作を示す流れ図である。
【図３】本発明の例示的な第１の実施の形態の動作の具体例を説明するための図である。
【図４】本発明の例示的な第２の実施の形態の構成を示す図である。
【発明を実施するための形態】
【００３９】
次に、本発明の実施の形態について図面を参照して詳細に説明する。データベースのルールの発見は、データベースと、ユーザが入力したパラメータ（頻度、確信度閾値情報）に基づき、データベースの内容に合致した、approximate constant CFD（確信度が所定値以上のコンスタントＣＦＤ）の集合を計算する。より具体的には、
データベースの内容とユーザが与えるパラメータに基づきフリーアイテムセット（free itemset）を計算するフリーアイテムセット（free itemset）生成手段（図１の２１）と、
得られたフリーアイテムセット（free itemset）から、妥当なルール候補を生成するルール候補生成手段（図１の２２）と、
生成された妥当なルール候補が、既に得られたルールに対して、冗長なものであるか否かチェックするルールの極小性判定手段（図１の２３）と、
を有する。
【００４０】
実施形態によれば、データ処理装置（２）は、データベースにおける属性と値のペアからなるフリーアイテムセットであって、前記データベースでの頻度が、予め定められた所定の閾値以上のフリーアイテムセットを生成するフリーアイテムセット生成手段（図１の２１）と、
前記生成されたフリーアイテムセットを、ルールの条件部に置き、且つ、前記フリーアイテムセットと属性を共有しないアイテムを、ルールの帰結部に置いたルール候補であって、その確信度が予め定められた確信度閾値以上であるルール候補を生成して保存する妥当なルール候補生成手段（図１の２２）と、
前記妥当なルール候補生成手段によって生成された前記ルール候補に対して、極小性のチェックを行い、前記ルール候補が極小（minimal）である場合に、前記ルール候補を出力装置（４）に出力するルールの極小性判定手段（図１の２３）と、
を備えている。
【００４１】
前記ルールの極小性判定手段（図１の２３）は、前記妥当なルール候補生成手段によって生成された複数のルール候補からなるルール候補群のリストに対し、前記ルール候補のサイズの昇順にソートし、前記リストの先頭から順に極小（minimal）な前記ルール候補を取り出して前記出力装置（４）に出力し、前記出力した極小なルール候補に対して冗長なルール候補を前記リストから除去することで、極小でないルールの除去を行う。
【００４２】
前記ルール候補生成手段（図１の２２）は、
前記フリーアイテムセットαに対して、前記フリーアイテムセットαと属性を共有しない１つのアイテムｘを追加したアイテムセットの頻度を計算し、
前記フリーアイテムセットに対して１つのアイテムを追加したアイテムセットの頻度の前記フリーアイテムセットの頻度に対する割合が、前記確信度閾値以上の場合、
前記フリーアイテムセットαを、条件部とし、１つのアイテムｘを、帰結部とするルールを、前記リストに追加する処理を、全ての前記フリーアイテムセットα、前記アイテムｘに対するチェックが終了するまで行う。
【００４３】
本発明によれば、最初に、フリーアイテムセット（free itemset）を計算することにより、approximate constant CFDの条件部に当たる部分を効率よく列挙することができる。また、本発明によれば、条件部のサイズの昇順に、approximate constant CFDの候補を並べ替え、先頭から候補を取り出すとともに、当該approximate constant CFDに対して、冗長な項を含むapproximate constant CFDを除去する。このため、極小な、approximate constant CFDのみを、効率よく得ることができる。その結果、ユーザがデータベースの内容を把握し、または修正を行うために有用なapproximate constant CFDの集合を効率よく得ることができる。以下、実施形態に即して説明する。
【００４４】
＜実施形態１＞
図１を参照すると、本発明の例示的な第１の実施の形態は、キーボード等の入力装置１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、ディスプレイ装置や印刷装置等の出力装置４を含む。
【００４５】
記憶装置３は、データベース記憶部３１を備えている。データベース記憶部３１は、それ自体からルールを抽出するためのデータベースを予め記憶している。
【００４６】
データ処理装置２は、フリーアイテムセット（free itemset）生成手段２１と、妥当なルール候補生成手段２２と、ルールの極小性判定手段２３とを備える。
【００４７】
フリーアイテムセット（free itemset）生成手段２１は、入力装置１から与えられたパラメータ（例えば、頻度の閾値ｋ）を用い、データベース記憶部３１に記憶されたデータベースのフリーアイテムセット（free itemset）を生成する。
フリーアイテムセット（free itemset）生成手段２１は、生成したフリーアイテムセット（free itemset）を、データ処理装置２内の不図示の記憶部又はフリーアイテムセット（free itemset）生成手段２１内の不図示の記憶部、又は記憶装置３の所定の記憶領域に記憶する。データベース中に出現している属性と値のペアを「アイテム」（item）と呼び、アイテムの集合をアイテムセット（itemset）という。
【００４８】
妥当なルール候補生成手段２２は、フリーアイテムセット（free itemset）生成手段２１によって生成されたフリーアイテムセット（free itemset）を、ルールの条件部に置き、
該フリーアイテムセット（free itemset）と属性を共有しないアイテムを、当該ルールの帰結部に置くことで、妥当なルール（確信度が閾値ｐ以上）を生成し、リストＬに加えて保存する。
妥当なルール候補生成手段２２は、妥当なルールを加えたリストＬを、データ処理装置２内の不図示の記憶部（例えばＤＲＡＭ（ダイナミックランダムアクセスメモリ）等のメモリ、又は磁気ディスク等）、又は、妥当なルール候補生成手段２２内の不図示の記憶部、又は記憶装置３の所定の記憶領域に記憶する。
【００４９】
ルールの極小性判定手段２３は、妥当なルール候補生成手段２２によって生成されたルール（妥当なルール）に対し、それが極小である場合、出力装置４に出力する。ここで、「極小である」（minimal）とは、条件部から、任意の１つ以上のアイテムを除去することで得られるルールが、どれも妥当ではない、という意味である。
具体的には、妥当なルール候補生成手段２２で得られた妥当なルールを、例えばサイズの昇順にソートして、リストＬ中に格納しておき、その先頭から順にルールの候補を取り出して出力し、リストＬの中に含まれ、今取り出したルールに対して冗長なルールを除去することで、極小でないルールの除去を行う。
【００５０】
次に、図１及び図２を参照して本実施の形態の動作について詳細に説明する。
【００５１】
入力装置１から与えられたパラメータ、及び、データベース記憶部３１から与えられたデータベースの内容は、フリーアイテムセット（free itemset）生成手段２１に供給される。
フリーアイテムセット（free itemset）生成手段２１は、データベース中に出現している属性と値のペア（これをアイテム（item）と呼ぶ）から、その頻度が閾値ｋ以上であるすべてのフリーアイテムセット（free itemsets）（「frequent free itemsets」という）を抽出する（ステップＡ１）。フリーアイテムセット（free itemset）とは、前述したように、アイテム（item）の集合であり、任意の１つ以上のアイテム（item）を除去することで、頻度が真に増加してしまうものである。
【００５２】
次に、妥当なルール候補生成手段２２は、フリーアイテムセット（free itemset）生成手段２１により生成された各フリーアイテムセット（free itemsets）から、妥当なルール候補を生成する。具体的には、
フリーアイテムセット（free itemset）αと属性を共有しないアイテム（item）をｘとし、αの頻度と、αに１つのアイテムｘを加えたアイテムセット（itemset）（α＋｛ｘ｝）の頻度を計算する（ステップＡ２）。
【００５３】
妥当なルール候補生成手段２２は、αに１つのアイテムｘを加えたアイテムセット（itemset）（α＋｛ｘ｝）の頻度と、フリーアイテムセット（free itemset）αの頻度の比：
（α＋｛ｘ｝の頻度）／（αの頻度）
が、確信度の閾値ｐ以上であるか否かをチェックする（ステップＡ３）。
【００５４】
妥当なルール候補生成手段２２は、
（α＋｛ｘ｝の頻度）／（αの頻度）≧ｐ
であるとき、コンスタントＣＦＤ
ψ：  α→ｘ
を、妥当なルール候補（approximate constant CFD）としてリストＬに追加する（ステップＡ４）。
【００５５】
妥当なルール候補生成手段２２は、全てのα、ｘに対して、ステップＡ３のチェック（（α＋｛ｘ｝の頻度）／（αの頻度）が確信度の閾値ｐ以上であるか否かのチェック）が終了したか否か判定する（ステップＡ５）。妥当なルール候補生成手段２２において、全てのα、ｘに対して、ステップＡ３のチェックが終了していない場合、ステップＡ２に戻り、全てのα、ｘの組み合わせに対して、ステップＡ３のチェックを行う。
【００５６】
妥当なルール候補生成手段２２において、全てのα、ｘに対してステップＡ３のチェックが終了した場合、ルールの極小性判定手段２３は、妥当なルールの候補生成手段２２によって生成されたリストＬの各ルール候補（approximate constant CFD）について、ルールが極小なものであるか否かのチェックを行う。
【００５７】
具体的には、ルールの極小性判定手段２３は、リストＬの要素を、サイズ（ＣＦＤの条件部のアイテムの個数）の昇順にソートする（ステップＡ６）。
【００５８】
ルールの極小性判定手段２３は、昇順にソートされたリストＬの先頭から、要素（ルールψ：approximate constant CFD）を順に取り出し、取り出したルール（ψ）を出力装置４に出力する（ステップＡ７）。
【００５９】
ルールの極小性判定手段２３は、リストＬに含まれているルール候補の中で、今リストＬから取り出して出力したルール（ψ）に対して、冗長なものを除去する（ステップＡ８）。
【００６０】
ルールの極小性判定手段２３は、リストＬが空か否か判定し（ステップＡ９）、空でない場合（ステップＡ９のNo分岐）、ステップＡ７の処理に戻る。リストＬが空の場合（ステップＡ９のYes分岐）、ルール発見計算を終了する。
【００６１】
次に、本実施の形態の作用効果について説明する。
【００６２】
本実施の形態では、発見するルールを、ほぼ成り立つコンスタントＣＦＤ（approximate constant CFD）に限定し、最初に、フリーアイテムセット（free itemset）を列挙することで、全てのapproximate constant CFDの条件部の候補を列挙する。このため、ほぼ成り立つコンスタントＣＦＤ（approximate constant CFD）候補の生成を最小限に抑えることができる。
【００６３】
その条件部のサイズの昇順にルールの極小性のチェックを行うため、極小性の判定に要する時間の増大を抑えることができる。この結果、ルールを効率よく発見することが可能となる。
【００６４】
次に、具体的な実施例を用いて本実施の形態の動作を説明する。図３（Ｂ）（以下の表１）に示すように、例えば、データベース記憶部３１には、以下の表１の属性・タプルからなるデータ集合が登録されている。なお、データベースの例は、あくまで説明のために簡易化した例である。図３（Ａ）は、図２のステップに対応して、フリーアイテムセット、リストＬ、ルールの極小性判定手段２３での極小性の判定処理の具体例を例示したものである。図３（Ｃ）は、図２の計算の結果、出力装置４から出力されたルール（approximate constant CFD）の一例を示す図である。なお、図３において、“属性１：＿”等の記号：は、“属性１＝＿”の記号＝と同義（同一）である。
【００６５】
＜表１＞
2013172309.tif 000003
【００６６】
フリーアイテムセット（free itemset）生成手段２１は、上記の表１、パラメータとしてｋ＝２、ｐ＝０．６６を受け取る。ここで、ｋは妥当なルールと判定するための頻度の下限（閾値）、ｐは確信度の下限（閾値）である。
【００６７】
フリーアイテムセット（free itemset）生成手段２１は、データベース中の出現頻度がｋ＝２以上である、すべてのフリーアイテムセット（free itemset）の集合
｛ｅｍｐｔｙ（４），“属性１＝１”（２），“属性２＝Ｐ”（３），“属性３＝Ｓ”（２），“属性３＝Ｔ”（２）｝（括弧の中の数値はそのitemsetの頻度）を抽出する（図２、図３（Ａ）のステップＡ１）。
【００６８】
この５つのフリーアイテムセット（free itemset）に対し、これらをＣＦＤの条件部に置く妥当なＣＦＤルールとして、以下のものが得られる。
【００６９】
まず、
α＝ｅｍｐｔｙに対しては、
ｘ＝“属性２＝Ｐ”
とすると、
ｅｍｐｔｙの頻度が（タプルの全個数と同じ）４、
“属性２＝Ｐ”の頻度が３である。
【００７０】
（“属性２＝Ｐ”の頻度）と（ｅｍｐｔｙの頻度）の割合（確信度）は、
（“属性２＝Ｐ”の頻度）／（ｅｍｐｔｙの頻度）＝３／４＝０．７５
である。この値０．７５は、確信度の閾値ｐ＝０．６６を上回っている。
【００７１】
このため、  妥当なルール候補生成手段２２は、
ＣＦＤ  ψ：  ｅｍｐｔｙ→”属性２＝Ｐ”  （頻度＝３、確信度＝０．７５）  
を、妥当なルール候補として、リストＬに加える。
【００７２】
同様にして、妥当なルール候補生成手段２２は、
“属性１＝１”→“属性３＝Ｓ”  （頻度＝２、確信度＝１）、
“属性２＝Ｐ”→“属性３＝Ｔ”  （頻度＝２、確信度＝２／３＝０．６６７）、
“属性３＝Ｓ→属性１＝１”  （頻度＝２、確信度＝１）
“属性３＝Ｔ→属性２＝Ｐ”  （頻度＝２、確信度＝１）
の４つのほぼ成り立つＣＦＤ（approximate constant CFD）も、妥当なルール候補として、リストＬに加える（ステップＡ２〜Ａ４）。
【００７３】
ルールの極小性判定手段２３は、リストＬ中の要素（ルール候補）を、サイズの昇順にソートする（並べ替える）（図２のステップＡ６）。この結果、
ｅｍｐｔｙ→“属性２＝Ｐ”
というルールがＬの先頭に現れる（図３（Ａ）の（ステップＡ２〜Ａ６）のＣＤＦ候補のリストＬ参照）。
【００７４】
ルールの極小性判定手段２３は、リストＬの先頭からこのルール  
ｅｍｐｔｙ→”属性２＝Ｐ”
を取り出す。これは、極小なルールであるため、出力装置４に出力する。このとき、リストＬ中に存在するルール候補のうち、
ルール候補
“属性３＝Ｔ”→“属性２＝Ｐ”  
は、今取り出したルール候補
ｅｍｐｔｙ→“属性２＝Ｐ”  
に対して、冗長であるため、ルールの極小性判定手段２３は、“属性３＝Ｔ”→“属性２＝Ｐ”をリストＬから除去する。
【００７５】
続いて、ルールの極小性判定手段２３は、リストＬ中に存在する残りのルール候補
“属性１＝１”→“属性３＝Ｓ”  （頻度＝２、確信度＝１）、
“属性２＝Ｐ”→“属性３＝Ｔ”  （頻度＝２、確信度＝０．６６７）、
“属性３＝Ｓ→属性１＝１”  （頻度＝２、確信度＝１）
をリストＬから順次取り出して順に出力装置４に出力する。上記ルール候補を個々にリストＬから取り出した際、これらのルール候補に対して、冗長なルールは、リストＬ中に存在しない。
【００７６】
このため、ルールの極小性判定手段２３は、以上の４個のapproximate constant CFDを出力する。その結果、リストＬは空となり、ルール発見アルゴリズムが終了する（ステップＡ７〜Ａ９）。
【００７７】
＜実施形態２＞
次に、本発明の例示的な第２の実施の形態について図面を参照して詳細に説明する。図４を参照すると、本発明の第２の実施の形態は、ルール発見用プログラム５を備える。ルール発見用プログラム５は、データ処理装置６に読み込まれ、データ処理装置６の動作を制御する。データ処理装置６は、ルール発見用プログラム５の制御により以下の処理、すなわち、図１乃至図３を参照して説明した前記第１の実施の形態におけるデータ処理装置２による処理と同一の処理、を実行する。
【００７８】
入力装置１からパラメータが与えられると、まず、記憶装置３内のデータベース記憶部３１に記憶されているデータベースを用い、フリーアイテムセット（free itemset）の生成を行う。
【００７９】
次に、生成されたフリーアイテムセット（free itemset）から、妥当なルール候補を生成し、リストＬに追加する。
【００８０】
リストＬに保存された妥当なルール候補の集合のうち、極小なものを、出力装置４に表示させる。
【００８１】
なお、上記実施形態において、ルール候補が追加されるリストＬは、線形リスト、キュー（Ｑｕｅｕｅ）等のデータ構造にのみ制限されるものでなく、例えば要素のサイズの順等で順番にソートした結果を記憶できるものであれば、配列等のほか任意の記憶形態（データ構造）、記憶領域であってよいことは勿論である。
【００８２】
なお、上記の特許文献、非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【００８３】
１  入力装置
２、６  データ処理装置
３  記憶装置
４  出力装置
５  ルール発見用プログラム
２１  フリーアイテムセット（free itemset）生成手段
２２  妥当なルール候補生成手段
２３  ルールの極小性判定手段
３１  データベース記憶部
【図１】
2013172309.tif 000004
【図２】
2013172309.tif 000005
【図３】
2013172309.tif 000006
【図４】
2013172309.tif 000007
【国際調査報告】
2013172309.tif 000008
2013172309.tif 000009