(57)【要約】  データベースの内容に対応したルールを効率よく発見可能とする装置、方法、プログラムを提供する。データベースからルール候補を生成するルール候補生成部（２１）と、ルール候補の１つを選択するルール選択部（２２）と、選択されたルールがデータベースの内容に対して妥当であるか判定するルールの妥当性判定部（２３）と、ルールの妥当性判定部（２３）で妥当と判定されたルールを受け取り、これまでに得られたルールの集合によるデータベースの各タプルのカバー度を更新し、カバー度が所定のパラメータで定義される計算の打ち切り条件を満たした場合、その時点でのルールの集合を出力し、ルール発見の計算を終了する、タプルのカバー度更新・判定部（２４）を備える（図１)。
2013105636.tif 000002
【特許請求の範囲】
【請求項１】
複数の属性と複数のタプルの表を有するデータベースと、
前記データベースにアクセスして前記データベースの前記属性間の値に関するルールの候補を生成して第１の記憶部に記憶するルール候補生成部と、
前記ルールの候補から１つのルールを選択するルール選択部と、
前記ルール選択部で選択された前記１つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記１つのルールが妥当性の条件が成り立つ場合、前記１つのルールを第２の記憶部に記憶する、ルールの妥当性判定部と、
前記ルールの妥当性判定部によって前記第２の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定部と、
を含む、ことを特徴とするルール発見装置。
【請求項２】
前記ルール候補生成部は、
前記データベースと、
入力装置から入力されたパラメータ、及び／又は、すでに生成され前記第１の記憶部に保持されているルール候補と、
に基づき、前記ルールの候補を生成する、ことを特徴とする請求項１記載のルール発見装置。
【請求項３】
前記タプルのカバー度定部は、前記第２の記憶部に記憶されている前記ルールの集合による前記データベースのカバー度が、予め定められた所定の条件を満たしたときに、ルール発見処理を打ち切り、前記第２の記憶装置に記憶されているルールの集合を出力する、ことを特徴とする請求項２記載のルール発見装置。
【請求項４】
前記打ち切り条件として、前記ルールの妥当性判定部で前記妥当性の条件が成り立つと判定された前記ルールに応じて更新されるカバー度と、前記入力装置から入力された１つ又は複数のパラメータを用いた所定の基準により判定を行う、ことを特徴とする請求項３記載のルール発見装置。
【請求項５】
前記１つ又は複数のパラメータが、第１のパラメータｓ（０＜ｓ≦１００）と、第２のパラメータＮ（所定の正整数）を含み、
前記データベース中のｓ％以上のタプルが、Ｎ個以上のルールとマッチしているという基準を前記打ち切り条件とする、ことを特徴とする請求項４記載のルール発見装置。
【請求項６】
データ処理装置が、
データベースから初期ルール候補を生成し、
前記生成したルール候補が妥当であるかチェックし、
妥当であれば、前記ルールをリストに追加し、
前記リストに保存されたルールの集合により、前記データベースのカバー度が予め定められた所定の打ち切り条件を満たした時、前記リスト内のルール集合を、出力装置に出力する、ことを特徴とするルール発見方法。
【請求項７】
前記データ処理装置でルール候補生成処理、ルール選択処理、ルールの妥当性判定処理、タプルのカバー度判定処理を実行し、
前記ルール候補生成処理は、複数の属性と複数のタプルの表を有する前記データベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成して第１の記憶部に記憶し、
前記ルール選択処理は、前記ルールの候補から１つのルールを選択し、
前記ルールの妥当性判定処理は、前記選択された前記１つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記１つのルールが妥当性の条件が成り立つ場合、前記１つのルールを第２の記憶部に記憶し、
前記タプルのカバー度判定処理は、前記ルールの妥当性判定処理によって前記第２の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックする、ことを特徴とする請求項６記載のルール発見方法。
【請求項８】
前記タプルのカバー度判定処理では、前記データベース中の予め定められた値ｓ％（０＜ｓ≦１００）以上のタプルが、予め定められた個数Ｎ個以上のルールとマッチしているという基準を満たしたときに、ルール発見処理を打ち切る、ことを特徴とする請求項７記載のルール発見方法。
【請求項９】
複数の属性と複数のタプルの表を有するデータベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成し第１の記憶部に記憶するルール候補生成処理と、
前記ルールの候補から１つのルールを選択するルール選択処理と、
前記ルール選択処理で選択された前記１つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記１つのルールが妥当性の条件が成り立つ場合、前記１つのルールを第２の記憶部に記憶する、ルールの妥当性判定処理と、
前記ルールの妥当性判定処理によって前記第２の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定処理と、
をコンピュータに実行させるプログラム。
【請求項１０】
前記タプルのカバー度判定処理が、前記データベース中の予め定められた値ｓ％以上のタプルが、予め定められた個数Ｎ個以上のルールとマッチしているという基準を満たしたときに、ルール発見処理を打ち切る、請求項９記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１２−００４４１４号（２０１２年１月１２日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、ルールを発見する装置と方法並びにプログラムに関する。
【背景技術】
【０００２】
関数従属性（Functional Dependency：ＦＤ）は、複数の属性間において、一方の値集合によって他方の値集合が決定される制約をいう。例えば［郵便番号］→［住所］：郵便番号が決まれば住所が決まる。これに対して、条件付関数従属性（Conditional Functional Dependency：ＣＦＤ）は、一方の値集合が特定の条件を満たすときに限り、他方の値集合が決定される制約をいう。例えば、［商品種別、国＝日本］→［税率］：国と商品種別によって税率が決まる（ただし、国が日本の場合のみ）。ＣＦＤは、例えば（Ｘ→Ａ，ｔｐ）の形式としても表わされる。Ｘ→Ａは、ＦＤである。ｔｐはＸとＹの属性値からなるパタンタプルである。パタンタプルは定数又は‘＿’（‘＿’は任意の値ともマッチする名前無し変数）からなる。ＣＦＤの発見は、ＦＤ  Ｘ→Ａだけでなく、パタンタプルｔｐを発見する必要がある。同一のＦＤ  Ｘ→Ａに対して、異なったパタンタプルで定義される複数のＣＦＤが存在する可能性がある。タプル（tuple:組）とは、関係（relation）を表(table)で表したときの行と同義であり、属性は表の列である。【０００３】
データベース（リレーショナルデータベース）の属性間で成り立つルールの発見において、該ルールをＣＦＤとして表現する場合、生成されたＣＦＤの候補からデータベースの内容に合致したＣＦＤを出力することになる。この場合、関連技術のＣＦＤ発見の典型的な構成としては、例えば以下のような構成とされる。ＣＦＤを保存する記憶装置と、データベースからＣＦＤの候補を生成し、該ＣＦＤ候補がデータベースの内容に合致しているか判定する計算手段と、当該データベースの内容に合致していると判定されたＣＦＤを記憶装置に保存する保存手段から構成される。計算手段は、所定のルール（ＣＦＤ）発見アルゴリズムを用いてＣＦＤを生成し、次にチェックの対象とするＣＦＤを候補の中から選び、それがデータベースの内容に合致しているかどうか調べ、合致していると判定された場合、妥当なＣＦＤとして出力する。保存手段は、妥当なＣＦＤを記憶装置に保存する。【０００４】
データベースからのＦＤやＣＦＤの候補の生成として、例えば非特許文献１、２の記載が参照される。非特許文献１は、既知の属性のリスト、または属性と値のペアのリストを合成し、そのうちの１つの項を従属項（Ａとする）、残りを条件項（Ｘとする）に置き、式：Ｘ→Ａを得る。ＣＦＤの候補の生成の順序は、幅優先（breadth-first）または深さ優先（depth-first）によって与えられる。非特許文献２には、ユーザによって与えられるＦＤから、一部の項に値を代入することでＣＦＤを得る構成が開示されている。なお、条件項をＬＨＳ（Left Hand Side）、従属項（帰結部）をＲＨＳ（Right Hand Side）ともいう。【０００５】
ルールの妥当性のチェックとして、例えば特許文献１には、条件部と結論部（帰結部）からなるルールを格納するルールベースと、ルールの適用結果に関する事例情報を格納する事例情報データベースと、ルールと該ルールを満たす事例情報を関係付ける関係付け部と、妥当性チェック対象のルールの条件部をキーとして事例情報データベースから事例情報集合を事例検索部に検索させ、事例情報集合において該ルールの結論部を満たす事例情報の割合を算出し、該割合に基づき、ルールの妥当性をチェックする妥当性チェック部と、を備えたルールベース管理装置が開示されている。【０００６】
また、特許文献２には、リレーションの属性間の関数従属性（ＦＤ）を見つけ出し、リレーション分割による正規化を行う構成が開示されている。特許文献２の実施形態によれば、属性組み合せ情報の先頭の組み合せに対して関数従属性が存在するか調べるために（属性Ｄは属性Ａに関数従属であるかを調べる）、関数従属性判定プロセスを呼び出し、ＳＱＬ（Structured Query Language）文を実行し１つもタプルを検索できなければ、属性Ｄは属性Ａの関数従属であると判断し、タプルが検索できれば、属性Ｄは属性Ａの関数従属ではないと判断し、関数従属である場合、Ａ→Ｄを従属性情報として格納する構成が開示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】国際公開第２００４／３６４９６号公報
【特許文献２】特開平６−１１０７４９号公報
【非特許文献】
【０００８】
【非特許文献１】Wenfei Fan et al., “Discovering Conditional Functional Dependencies,” pp.1231-1234, IEEE International Conference on Data Engineering, 2009  ［2011年12月21日検索］インターネットURL＜:http://homepages.inf.ed.ac.uk/fgeerts/pdf/icde09.pdf＞
【非特許文献２】Lukasz Golab et al., “On Generating Near-Optimal Tableaux for Conditional Functional Dependencies,”pp376-390 VLDB Endowment, 2008 ［2011年12月21日検索］インターネットURL＜http://www.vldb.org/pvldb/1/1453900.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明者による分析によれば、関連技術には、代表的には、以下のような問題点（Ａ）、（Ｂ）がある。【００１０】
（Ａ）関連技術のＣＦＤ発見アルゴリズムにより得られるＣＦＤとして、データベースの内容と合致し、且つ、サポート値が予め定められた閾値以上である、という条件を満たすＣＦＤは、一般に、多量に存在する。しかも、前記多量のＣＦＤのうち、データベースの内容の把握のために必ずしも有用とはいえないＣＦＤも多数存在する。【００１１】
これは、関連技術のＣＦＤ発見アルゴリズムにより生成されるＣＦＤのほとんどは、条件節（ＬＨＳ）のサイズが大きなものであり、当該ＣＦＤの意味を、人手で把握することが困難であるためである。【００１２】
また、ＣＦＤにおいて、条件節（ＬＨＳ）のサイズが大きくなるほど、該条件節中の定数項も増加し、データベースにおいて、限定された一部のタプルとしかマッチせず、他の大部分のタプルとは関係の無いルールとなる。サポート値について、以下に概説しておく。【００１３】
2013105636.tif 000003
【００１４】
上記表１の関係のデータセットにおいて、例えばＣＦＤ
φ１：（［Ａ，Ｂ］→［Ｃ］、（１，＿‖＿））
（属性Ａの値が１の場合、属性Ｂによって、属性Ｃの値が決定される）が抽出される。なお、上記ＣＦＤ  φ１において、パタンタプルｔｐ＝（１，＿‖＿）の‘‖’の左側（１，＿）は条件節（ＬＨＳ）Ａ、Ｂの属性値、‘‖’の右側（＿）は、従属節（ＲＨＳ）Ｃの属性値である。表１において、上記φ１の条件節が成り立つのは、ＩＤが１、２、３と、８、９、１０のタプルであり、１０件中６件存在する。したがって、例えばサポート値（support）＝６／１０＝０．６となる（サポート値を、条件節（前提）と従属節（帰結）が成り立つタプルの割合とする場合もある。この場合、φ１のサポート値は０．６）。このサポート値が予め定められた閾値以上のＣＦＤが生成される。【００１５】
（Ｂ）関連技術のＣＦＤ発見アルゴリズムは多量の計算時間を要する。例えば非特許文献１では、ＣＦＤの候補の生成を、ＦＤの各項に、データベース中に出現している値を代入することで行っている。また非特許文献２では、２つのＣＦＤの候補を合成することで、ＣＦＤの候補の生成を行っている。いずれの場合も、生成されるＣＦＤの候補が莫大な個数となる。そのため、多量の時間、演算量を要する。【００１６】
したがって、本発明は上記問題点に鑑みて創案されたものであって、その目的は、データベースの内容に対応したルールを効率よく発見することを可能とする装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１７】
本発明によれば、複数の属性と複数のタプルの表を有するデータベースと、
前記データベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成して第１の記憶部に記憶するルール候補生成部と、
前記ルールの候補から１つのルールを選択するルール選択部と、
前記ルール選択部で選択された前記１つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、前記１つのルールが妥当性の条件が成り立つ場合、前記１つのルールを第２の記憶部に記憶する、ルールの妥当性判定部と、
前記ルールの妥当性判定部によって前記第２の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定部と、
を含むルール発見装置が提供される。【００１８】
本発明によれば、データ処理装置でルール候補生成処理、ルール選択処理、ルールの妥当性判定処理、タプルのカバー度判定処理を実行し、
前記ルール候補生成処理は、複数の属性と複数のタプルの表を有するデータベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成して第１の記憶部に記憶し、
前記ルール選択処理は、前記ルールの候補から１つのルールを選択し、
前記ルールの妥当性判定処理は、前記選択された前記１つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記１つのルールが妥当性の条件が成り立つ場合、前記１つのルールを第２の記憶部に記憶し、
前記タプルのカバー度判定処理は、前記ルールの妥当性判定処理によって前記第２の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックする、ルール発見方法が提供される。【００１９】
本発明によれば、複数の属性と複数のタプルの表を有するデータベースにアクセスして前記データベースの属性間の値に関するルールの候補を生成し第１の記憶部に記憶するルール候補生成処理と、
前記ルールの候補から１つのルールを選択するルール選択処理と、
前記ルール選択処理で選択された前記１つのルールの条件節と従属節を抽出し、前記ルールの条件節がマッチする前記データベースのタプルに対して、前記ルールの従属節と前記タプルの内容がマッチしており、且つ、前記ルールに反するタプルが存在しないという妥当性の条件が成り立つか否かをチェックし、
前記１つのルールが妥当性の条件が成り立つ場合、前記１つのルールを第２の記憶部に記憶する、ルールの妥当性判定処理と、
前記ルールの妥当性判定処理によって前記第２の記憶部に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた割合でマッチしているか否かをチェックするタプルのカバー度判定処理と、
をコンピュータに実行させるプログラムが提供される。
【発明の効果】
【００２０】
本発明によれば、データベースの内容に対応したルールを効率よく発見することを可能としている。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施の形態の構成を示す図である。
【図２】本発明の第１の実施の形態の動作を示す流れ図である。
【図３】本発明の第１の実施の形態の動作を説明するための図である。
【図４】本発明の第２の実施の形態の構成を示す図である。
【発明を実施するための形態】
【００２２】
本発明の概要を説明する。本発明の好ましい形態によれば、ＣＦＤの候補（ルール候補）の一部を生成し（初期ＣＦＤ候補として、例えば条件節を空とし従属節のみのルールを生成する）、該ＣＦＤ候補（ルール候補）が、データベースと合致するかチェックを行う。そして、これまでに得られたＣＦＤのみでは、データベースの内容の把握のために不十分であると判定されたときに、次のＣＦＤ候補（ルール候補）を逐次的に生成し、生成したＣＦＤ候補（ルール候補）に対して、データベースと合致するかのチェックを行う。このような構成（逐次的な反復構成）としたことで、データベースの内容把握のために有用と考えられるＣＦＤ（ルール）から逐次的に順次に発見されることになる。すなわち、本発明の好ましい形態によれば、データベースの内容を把握するのに有用なＣＦＤ（ルール）の集合を優先して（データベースの内容把握に有用でないＣＦＤ（ルール）に対して優先して）得ることができる。
【００２３】
本発明の好ましい形態によれば、「これまでに得られたＣＦＤ（ルール）の集合により、ユーザがデータベースの内容を十分把握できる」という条件を定式化して表し、当該条件が満たされたときに、計算（ＣＦＤ発見処理）を打ち切り、それ以上のＣＦＤの発見処理を行わない（データベースの内容を把握するのに有用でないＣＦＤの発見処理は行われない）。このため、本発明の好ましい形態によれば、ユーザが例えばデータベースの修正や要約を行うために有用なＣＦＤ（ルール）、すなわち、データベースの内容の把握に十分なＣＦＤ（ルール）の集合を、効率的に導出することができる。
【００２４】
本発明の好ましい形態の１つの方法によれば、データ処理装置が、
データベースから初期ルール候補を生成し、
前記生成したルール候補が妥当であるかチェックし、
妥当であれば、前記ルールをリストに追加し、
前記リストに保存されたルールの集合により、前記データベースのカバー度が予め定められた所定の打ち切り条件を満たした時、前記リスト内のルール集合を、出力装置に出力する、上記各ステップを含む。
【００２５】
本発明の好ましい形態の１つによれば、複数の属性(attributes)と複数のタプル(tuples)の表（table）を有するデータベースからルールの候補を生成して第１の記憶部（例えば内部メモリ）に記憶するルール候補生成部（図１の２１）と、前記ルール候補の中から、妥当性判定対象のルールを１つ選ぶルール選択部（図１の２２）と、前記ルール選択部（図１の２２）で選択された前記１つのルールの候補が、前記データベースの内容に対して妥当であるかチェックし、前記１つのルールが妥当性の条件が成り立つ場合、前記１つのルールを第２の記憶部（リストＬ：内部メモリ）に記憶するルールの妥当性判定部（図１の２３）と、前記ルールの妥当性判定部（図１の２３）で前記妥当性の条件が成り立つとされ前記第２の記憶部（リストＬ：内部メモリ）に記憶された前記ルールの集合が、前記データベースの各タプルと予め定められた程度でマッチしているか否かをチェックする（前記データベースのカバー度を更新し、打ち切り条件を満たすか否かをチェックする）、タプルのカバー度更新・判定部（図１の２４）と、を含む。
【００２６】
本発明の好ましい形態の１つによれば、ルール候補生成部（図１の２１）は、前記データベースと、入力装置から入力されたパラメータ、及び／又は、すでに生成したルール候補に基づき、ルールの候補を生成するようにしてもよい。
【００２７】
本発明の好ましい形態の１つによれば、ルール生成のための打ち切り条件を導入し、データベースのルールの発見の高速化を図っている。タプルのカバー度更新・判定部（図１の２４）は、これまでに得られた前記ルールの集合による前記データベースのカバー度が、予め定められた所定の条件を満たしたときに、計算（ルール発見アリゴリスムの計算）を打ち切る。
【００２８】
本発明の好ましい形態の１つによれば、前記打ち切り条件として、ルールを発見するごとに更新される、前記データベースのカバー度と、少なくとも１つのパラメータを用いた、所定の基準により判定を行うようにしてもよい。
【００２９】
本発明の好ましい形態の１つによれば、前記データベースの前記カバー度として、前記データベース中の各タプルのＩＤをキーとし、前記タプルが、今までに発見されたルール（ＣＦＤ）のうちいくつとマッチしているかの個数を値（バリュー）として記憶するキー・バリュー・ストア（ハッシュマップ）として保持し、ルールが発見された場合、当該ルールとマッチするタプル（ＩＤ：キー）のバリューを１増やす構成としてもよい。また、前記パラメータの例として、例えば、パラメータｓ、Ｎ（ただし、０＜ｓ≦１００、Ｎは所定の正整数）を用い、
「データベース中のｓ％以上のタプルが、Ｎ個以上のＣＦＤとマッチしている」
という基準を用いてもよい。
【００３０】
本発明の好ましい形態の１つによれば、ルール候補生成部（図１の２１）において、過去に生成されたルール候補に基づき、新たなルールの候補を生成するにあたり（後述する図３のステップＡ８）、例えば条件節（ＣＦＤのＬＨＳ）のサイズがｋであり（ｋは所定の正整数）、そのうちの１つの部分のみが異なる２つのルール候補を合成することで、条件節のサイズがｋ＋１であるルール候補を生成するようにしてもよい。
【００３１】
本発明の好ましい各形態によれば、データベースの内容の把握に有用なＣＦＤ（ルール）の集合を、効率的に導出することができる。以下、本発明の例示的な実施の形態について図面を参照して詳細に説明する。
【００３２】
＜実施形態１＞
図１を参照すると、本発明の例示的な第１の実施の形態は、キーボード、タッチパネル等の入力装置１と、プログラム制御により動作するデータ処理装置２と、情報を記憶する記憶装置３と、表示（ディスプレイ）装置や印刷（プリンタ）装置などの出力装置４を含む。
【００３３】
記憶装置３は、データベース記憶部３１を備えている。データベース記憶部３１は、データベースを記憶している。データベースはリレーショナルデータベース（複数の属性と複数のタプルで構成される）からなり、当該リレーショナルデータベースから、属性間のルールとしてＣＦＤが抽出される。
【００３４】
データ処理装置２は、ルール候補生成部２１と、ルール選択部２２と、ルールの妥当性判定部２３と、タプルのカバー度更新・判定部２４とを備える。
【００３５】
ルール候補生成部２１は、データベース記憶部３１に記憶されたデータベースからルール候補を生成し、データ処理装置２の内部メモリ（不図示）に記憶する。なお、ルール候補生成部２１は、入力装置１から入力されたパラメータや、これまでに生成されたルール候補を、データ処理装置２の内部のメモリ（不図示）に保持する。これらを用いて、ルール候補生成部２１は、データベースからルール候補を生成する。ルール候補生成部２１で生成されたルール（ＣＦＤ）は初期ＣＦＤ候補として、例えば内部のメモリ（不図示）に保持される。
【００３６】
ルール選択部２２は、ルール候補生成部２１によって生成され不図示の内部メモリに記憶されたルール候補を参照して、ルールの妥当性判定部２３で妥当性のチェックを行うルールを１つ選択する。
【００３７】
ルールの妥当性判定部２３は、ルール選択部２２によって選択された１つのルールを参照し、これが妥当なルールであるかチェックし、妥当なものである場合、不図示の内部メモリに記憶されるリストＬ（ＣＦＤのリスト）に加えて保存する。例えば（Ｘ→Ａ、ｔｐ１）、（Ｘ→Ｂ、ｔｐ１）等の複数のＣＦＤを連結したリスト構造（（Ｘ→Ａ、ｔｐ１）、（Ｘ→Ｂ、ｔｐ１））として記憶する。ただし、ＣＦＤを記憶するデータ構造は連結リスト（線形リスト）（Linked-List）に制限されるものでなく、任意のデータ構造であってよいことは勿論である。なお、リストＬは、データ処理装置２の内部メモリ（不図示）において、初期ＣＦＤ候補を記憶する領域と別の記憶領域に格納してもよい。
【００３８】
また、本願において、「妥当である」とは、
・ルールの条件節（ＬＨＳ）がマッチする、データベースの全てのタプルに対して、ルールの従属節（ＲＨＳ）とタプルの内容がマッチしており、且つ、
・当該ルールに反するタプルが存在しない、
ことをいう。
【００３９】
タプルのカバー度更新・判定部２４は、ルールの妥当性判定部２３で得られたルールを入力として受け、データベースのカバー度の更新を行う。タプルのカバー度更新・判定部２４は、更新したカバー度が予め定められた打ち切り条件を満たした場合、ルール発見処理の繰り返しを終了し、出力装置４に、処理結果（リストにつながれたルール）を出力する。
【００４０】
図２は、第１の実施形態の処理手順を説明する流れ図である。図１および図２を参照して、第１の実施形態の動作について詳細に説明する。
【００４１】
入力装置１から与えられたパラメータ、およびデータベース記憶部３１から与えられたデータベースの内容は、ルール候補生成部２１に供給される。
【００４２】
＜ステップＡ１＞
ルール候補生成部２１は、データベース中に出現している属性と値のペアからその頻度が、予め設定されたパラメータｋ（ｋは所定の正整数）以上であるものを全て抽出し、条件節（LＨＳ）が空、抽出されたペアが従属節（ＲＨＳ）となるルール（ＣＦＤ）を生成し、これをルール（ＣＦＤ）の候補（初期ＣＦＤ候補）とする。条件節（ＬＨＳ）が空で従属節（ＲＨＳ）のみのＣＦＤは常に成立する。これらのＣＦＤをＣＦＤ候補の一部として上記初期ＣＦＤ候補とし、以下のステップを繰り返すことでＣＦＤの発見を行う。
【００４３】
＜ステップＡ２＞
次に、ルール選択部２２は、ルール候補生成部２１により生成されたルールの候補から、次に妥当性のチェックを行うルールを１つ選択する。具体的には、選択されたルールが妥当なものである場合、予め定めた打ち切り条件に最も近づくようなルール（ＣＦＤ  φ）を選択する。
【００４４】
＜ステップＡ３＞
ルールの妥当性判定部２３は、選択されたルール（ＣＦＤ  φ）がデータベースの内容と整合しているかチェックする。すなわち、ルールの妥当性判定部２３は、ルール選択部２２により選択されたルールを、データベース記憶部３１に保存されているデータベースと照合し、ルールが妥当なものであるかチェックを行う。具体的には、ルールの妥当性判定部２３は、ルール（ＣＦＤ  φ）の条件節（ＬＨＳ）がマッチするデータベースの全てのタプルに対して、ルールの従属節（ＲＨＳ）と、タプルの内容（各属性の値）がマッチしており、ルールに反するタプルが存在しない場合、妥当なものであると判定する。
【００４５】
＜ステップＡ４＞
選択されたルール（ＣＦＤ  φ）がデータベースの内容と整合している場合、ルールの妥当性判定部２３は、ＣＦＤ  φをリストＬに入れて保存する。ステップＡ３で、妥当なルールと判定されない場合、ステップＡ６に移行する。
【００４６】
このステップＡ４において、次に、タプルのカバー度更新・判定部２４は、データベースのカバー度の更新を行う。具体的には、ステップＡ３にて整合していると判定されたルール（ＣＦＤ  φ）と、条件節（ＲＨＳ）がマッチするデータベースの全てのタプルの各々に対して、該マッチしているルールの個数を１つ増やす。前記データベース中の各タプルのＩＤをキーとし、タプルが、これまで発見されたルール（ＣＦＤ）のうちのいくつとマッチしているかの個数を、バリューとしたハッシュマップとして保持するようにしてもよい。ルール（ＣＦＤ）が発見された直後に、当該ルール（ＣＦＤ）とマッチするタプル（ＩＤをキーとする）のバリューを１増やす。
【００４７】
＜ステップＡ５＞
タプルのカバー度更新・判定部２４は、ステップＡ４で更新されたカバー度が、入力装置１から与えられたパラメータによって決定される計算の打ち切り条件を満たしているかチェックする。タプルのカバー度更新・判定部２４は、更新されたカバー度が打ち切り条件を満たしている場合、処理を終了し、ステップＡ１０に移行し、現在のリストＬの内容を出力装置４に表示する。
【００４８】
＜ステップＡ６＞
更新されたカバー度が打ち切り条件を満たしていない場合、タプルのカバー度更新・判定部２４は、選択されたルール（ＣＦＤ  φ）と不要となったルールを候補から削除する。
【００４９】
＜ステップＡ７＞
タプルのカバー度更新・判定部２４は、ルール（ＣＦＤ）の候補が空かチェックを行う。ルール（ＣＦＤ）の候補が空でない場合、ステップＡ２に戻り、ルール選択部２２は、残りのルールから１つ選択し、ルールの妥当性判定部２３は、当該ルールが妥当なものであるかチェックを行う。
【００５０】
＜ステップＡ８＞
ステップＡ７の判定でルール（ＣＦＤ）の候補が空の場合、ルール候補生成部２１は、新たなルール候補を生成する。ルール候補生成部２１が、ルール候補に基づき新たなルールの候補を生成する場合、条件節のサイズがｋ（ｋは所定の正整数）であり、サイズｋのうち１つの部分のみが異なる２つのルール候補を合成することで、条件節のサイズが、（ｋ＋１）のルール候補を生成する。
【００５１】
＜ステップＡ９＞
ステップＡ８で１つ以上のルールが生成された場合、ステップＡ２に移行する。ステップＡ９で何もルールが生成されない場合、ステップＡ１０に移行する。ステップＡ１において、ルール候補生成部２１で生成された全てのルール候補が妥当なものでないと判定された場合には、たとえ、カバー度が計算の打ち切り条件を満たしていなかったとしても、繰り返し処理を終了し、現在のリストＬの内容を、出力装置４に表示する。
【００５２】
次に、本実施の形態の作用効果について説明する。
【００５３】
本実施の形態では、それまでに得られたルール（ＣＦＤ）によってデータベースのカバー度が打ち切り条件を満たした時に計算を終了し、それ以上のルールを計算しない。このため、ユーザにとって有用でないルールの発見を抑えつつ、限られた時間で有用なルールを重点的に収集することが可能となる。
【００５４】
次に、具体的な実施例を用いて説明する。図３に示すように、例えば、データベース記憶部３１には以下の属性・タプルからなるデータ集合が登録されている。
【００５５】
2013105636.tif 000004
【００５６】
ルール候補生成部２１は、上記の表２およびパラメータとして、ｋ＝２、ｓ＝７５％、Ｎ＝２を受け取る。
ここで、
ｋは、妥当なルールと判定するためのサポート値の下限、
ｓとＮは「データベース中のｓ以上のタプルがＮ個以上のルールによってカバーされている場合、計算を終了する」という終了条件を定義するためのパラメータである。
【００５７】
そして、データベース中の出現頻度（タプル数）がｋ以上である、全ての属性と値のペア｛属性Ａ＝＿，属性Ｂ＝＿，属性Ｃ＝＿，属性Ａ＝１，属性Ｂ＝Ｐ，属性Ｃ＝Ｓ，属性Ｃ＝Ｔ｝を抽出し、（記号＿は任意の値にマッチする変数である）、条件節（ＬＨＳ）が空、抽出された各々のペアが従属節（ＲＨＳ）となる７つのルールを生成し、これをルールの候補とする（ステップＡ１）。条件節が空のルールは常に成り立つ。
【００５８】
この７つのルールは、いずれもデータベースの内容に対して妥当ではないため（前記妥当性の条件を満たさない）、属性と値のペアの集合から、新たなルールの生成を行う。具体的には、集合から互いに矛盾しない２つの要素を選び合成し、要素のうち１つを従属節、残りを条件節としたルールを生成する（例えば図２のステップＡ８）。
【００５９】
ステップＡ８で新たに生成されたルールのうち、
ＣＦＤ  φ１（Ａ→Ｂ，（＿‖＿））（属性Ａ＝＿→属性Ｂ＝＿）
というルール（属性Ａの値が、属性Ｂの値を一意に決定する）は妥当なものであると、ルールの妥当性判定部２３は判定し、このφ１をリストＬに加える。次に、タプルのカバー度更新・判定部２４は、全てのタプル１〜４（タプルID=1〜４）に対するカバー値を１つ増やす更新を行う（図２のステップＡ４）。
【００６０】
この時点で、計算の打ち切り条件は満たしていないため（図２のＡ５のＮｏ分岐）、続いて、ステップＡ８で新たに生成された別のルール
ＣＦＤ  φ２  （Ａ→Ｂ，（１‖Ｐ））  （属性Ａ＝１→属性Ｂ＝Ｐ）
を妥当なルールであるとルールの妥当性判定部２３で検出し、このφ２をリストＬに加える。次にタプルのカバー度更新・判定部２４は「属性Ａ＝１」という条件にマッチするタプル１、２のカバー値を１つ増やす更新を行う（図２のステップＡ４）。
【００６１】
続いて、
ＣＦＤ  φ３  （Ｃ→Ｂ，（Ｔ‖Ｐ））、（属性Ｃ＝Ｔ  →  属性Ｂ＝Ｐ）
というルールを、ルールの妥当性判定部２３で妥当なものと判定し、φ３をリストＬに加える。タプルのカバー度更新・判定部２４は、カバー度の更新として、「属性Ｃ＝Ｔ」という条件にマッチするタプル２、３の値を１つ増やす更新を行う。
【００６２】
この時点で、各タプル１、２、３、４のカバー値は、それぞれ２、３、２、１となり、打ち切り条件である「データベース中の７５％以上のタプルが２個以上のルールによってカバーされている場合、計算を終了する」を満たすため、得られたルール（ＣＦＤ）として、
φ１  （Ａ→Ｂ，（＿‖＿））、
φ２  （Ａ→Ｂ，（１‖Ｐ））、
φ３  （Ｃ→Ｂ，（Ｔ‖Ｐ））、
の３つを出力し、処理を終了する（図２のステップＡ１０）。
【００６３】
ここで、打ち切り条件を設けない場合、例えば、
φ４  （［Ｃ，Ｂ］→Ａ，（Ｑ，＿‖＿））、（属性Ｃ＝Ｑ、属性Ｂ＝＿→属性Ａ＝＿）というルールが続いて生成されることになる。
【００６４】
これに対して、本実施形態によれば、上記打ち切り条件を設けることで、このルールを生成する前に、ＣＦＤ発見アルゴリズムを終了する。
【００６５】
＜実施形態２＞
次に、本発明の第２の実施の形態について説明する。図４を参照すると、本発明第２の実施の形態は、ルール発見用プログラム５を備える。
【００６６】
ルール発見用プログラム５は、所定の記憶媒体に記憶保持されるか、図示されないネットワークを介して他のノードからデータ処理装置６にダウンロードしてもよい。ルール発見用プログラム５は、データ処理装置６に読み込まれて図示されないＣＰＵ（Central Processing Unit）で実行され、データ処理装置６の動作を制御する。データ処理装置６は、ルール発見用プログラム５の制御により、図１の各部２１〜２４の処理（図２の処理ステップ）を実行する。すなわち、ルール発見用プログラム５は、入力装置１からの設定にしたがい、記憶装置３内のデータベース記憶部３１に記憶されているデータベースから初期ルール候補の生成を行い、生成されたルール候補が妥当であるかチェックし、妥当であれば、当該ルールをリストに追加する。リストに保存されたルールの集合により、データベースのカバー度が打ち切り条件を満たした時、リスト内のルール集合を、出力装置４に表示させる。
【００６７】
なお、上記の特許文献、非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【００６８】
１  入力装置
２  データ処理装置
３  記憶装置
４  出力装置
５  ルール発見用プログラム
６  データ処理装置
２１  ルール候補生成部
２２  ルール選択部
２３  ルールの妥当性判定部
２４  タプルのカバー度更新・判定部
３１  データベース記憶部
【図１】
2013105636.tif 000005
【図２】
2013105636.tif 000006
【図３】
2013105636.tif 000007
【図４】
2013105636.tif 000008
【国際調査報告】
2013105636.tif 000009
2013105636.tif 000010
2013105636.tif 000011
2013105636.tif 000012