(57)【要約】【課題】従来の深さ優先探索によるルール発見方法では、親ルールよりも評価値が大きくない冗長なルールを排除できない場合がある。【解決手段】条件項目の順序に従って、子ルール（下位階層のルール）、および兄弟ルール（同一階層のルール）を配置した互いに木構造関係（階層関係）がある複数のルールから、木構造を構成する時の条件項目の順序とは逆の順序で候補ルールを検索し、検索された順にルールの評価値を比較し、評価値の高いルールを出力する。【選択図】  図２
2005038073.tif 000002
【特許請求の範囲】
【請求項１】
複数のフィールドからなるレコードの集合を対象データとし、１個以上の条件節を持つルールを検索する方法であって、
前記対象データ中の条件項目の順序を記憶手段に記憶する第１のステップと、
評価すべき候補ルールを前記記憶手段に記憶する第２のステップと、
候補ルールが採用基準を満足する場合に、前記候補ルールを採用ルールとして前記記憶手段に記憶する第３のステップと、
次に評価すべきルールを決定する第４のステップとを有し、
前記第２のステップは、前記第４のステップで決定された前記次に評価すべきルールを、新たな候補ルールとして前記記憶手段に記憶し、
前記第４のステップは、前記条件項目の順序に従って親ルールの下に子ルールを配置したルールの親子関係を表すルール木において、ルールの配置とは逆方向に前記条件項目の順序に従ってルール木を深さ優先探索することによって前記次に評価すべきルールを決定することを特徴とする方法。
【請求項２】
複数のフィールドからなるレコードの集合を対象データとし、１個以上の条件節を持つルールを検索する方法であって、
前記対象データ中の条件項目の順序を記憶手段に記憶する第１のステップと、
候補ルールを前記記憶手段に記憶する第２のステップと、
前記候補ルールが採用基準を満足する場合に、前記候補ルールを採用ルールとして前記記憶手段に記憶する第３のステップと、
次に評価すべきルールを決定する第４のステップとを有し、
前記第２のステップは、前記第４のステップで決定された前記次に評価すべきルールを、新たな候補ルールとして前記記憶手段に記憶し、
前記第４のステップは、１個の条件節からなる任意のルールについてはルートノードを親ルールとし、２個以上の条件節からなる任意のルールについては、その条件節を１個取り除いてできるルールのうち、順序がより前の、もしくは、順序がより後の条件項目を持つルールを親ルールとして構成したルール木において、前記ルール木の構成における親ルールの決め方とは逆に、条件項目の順序がより後のルールから前のルールへ向かって、もしくは、より前のルールから後のルールへ向かって、ルール木を深さ優先探索することによって前記次に評価すべきルールを決定することを特徴とする方法。
【請求項３】
複数のフィールドからなるレコードの集合を対象データとし、１個以上の条件節を持つルールを検索する方法であって、
前記対象データ中の条件項目の順序を記憶手段に記憶する第１のステップと、
候補ルールを前記記憶手段に記憶する第２のステップと、
前記候補ルールが採用基準を満足する場合には、前記候補ルールを採用ルールとして前記記憶手段に記憶する第３のステップと、
次に評価すべきルールを決定する第４のステップとを有し、
前記第２のステップは、前記第４のステップで決定された前記次に評価すべきルールを、新たな候補ルールとして前記記憶手段に記憶し、
前記第４のステップは、１個の条件節からなる任意のルールについてはルートノードを親ルールとし、２個以上の条件節からなる任意のルールについては、その条件節を１個取り除いてできるルールのうち、順序がより前の、もしくは、順序がより後の条件項目を持つルールを親ルールとして構成したルール木において、現在の候補ルールが子ルールを持つ場合は、前記ルール木の構成における親ルールの決め方とは逆に、順序が最も後の、もしくは最も前の条件項目を持つ子ルールを前記次に評価すべきルールに決定する第５のステップと、現在の候補ルールが子ルールを持たない場合は、現在の候補ルールの兄弟ルールで、未評価のものが存在するならば、未評価の兄弟ルールのうち、前記ルール木の構成における親ルールの決め方とは逆に、順序が最も後の、もしくは最も前の条件項目を持つものを前記次に評価すべきルールに決定する第６のステップと、未評価の兄弟ルールが存在しない場合は、現在の候補ルールの親ルールがルートノードでないならば、親ルールを現在の候補ルールと見なし、前記第６のステップを繰り返す第７のステップと、現在の候補ルールの親ルールがルートノードならば、前記次に評価すべきルールはないと結論づける第８のステップを有することを特徴とする方法。
【請求項４】
複数のフィールドからなるレコードの集合を対象データとし、１個以上の条件節を持つルールを検索する方法であって、
対象データ中の条件項目の順序を記憶手段に記憶する第１のステップと、
候補ルールを前記記憶手段に記憶する第２のステップと、
候補ルールが採用基準を満足する場合に、前記候補ルールを採用ルールとして前記記憶手段に記憶する第３のステップと、
次に評価すべきルールを決定する第４のステップとを有し、
前記第２のステップは、前記第４のステップで決定された前記次に評価すべきルールを、新たな候補ルールとして前記記憶手段に記憶し、
前記第４のステップは、１個の条件節からなる任意のルールについてはルートノードを親ルールとし、２個以上の条件節からなる任意のルールについては、その条件節を１個取り除いてできるルールのうち、順序がより前の、もしくは、順序がより後の条件項目を持つルールを親ルールとして構成したルール木において、現在の候補ルールが子ルールを持ち、かつ、枝刈り条件を満足しない場合は、前記ルール木の構成における親ルールの決め方とは逆に、順序が最も後の、もしくは最も前の条件項目を持つ子ルールを前記次に評価すべきルールに決定する第５のステップと、現在の候補ルールが子ルールを持たないか、または枝刈り条件を満足した場合は、現在の候補ルールの兄弟ルールで、未評価のものが存在するならば、未評価の兄弟ルールのうち、前記ルール木の構成における親ルールの決め方とは逆に、順序が最も後の、もしくは最も前の条件項目を持つものを前記次に評価すべきルールに決定する第６のステップと、未評価の兄弟ルールが存在しない場合は、現在の候補ルールの親ルールがルートノードでないならば、親ルールを現在の候補ルールと見なし、前記第６のステップを繰り返す第７のステップと、現在の候補ルールの親ルールがルートノードならば、前記次に評価すべきルールはないと結論づける第８のステップを有することを特徴とする方法。
【請求項５】
請求項１ないし４の何れかに記載の方法であって、
前記第３のステップは、前記候補ルールの親ルールの条件節を満足するレコードの番号が記録された表を前記記憶手段から読み出し、読み出された前記表を参照し、前記表に番号が記録されたレコードが前記候補ルールの条件節を満足するかを調べるステップと、該候補ルールの条件節を満足するレコードの番号を前記記憶手段に記憶するステップを有することを特徴とする方法。
【請求項６】
コンピュータに、請求項１ないし５の何れかに記載の方法を実行させるためのプログラム。
【請求項７】
コンピュータに、請求項１ないし５の何れかに記載の方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項８】
ルールを検索する装置において、
互いに階層関係にある複数のルールであって、上位階層から下位階層へ向かって前記ルールの構成要素が付加される関係にある前記複数のルールを記憶する記憶装置と、
上位階層から下位階層へ向かって、かつ、同一階層で下位に含まれるルールの数が少ない方から多い方へ向かって前記記憶装置から前記ルールを検索する検索手段と、
前記検索手段の検索順序に従って先に検索されたルールの評価値と後に検索されたルールの評価値を比較し、その比較結果に応じて前記後に検索されたルールを採用するか否かを決定する比較手段とを有することを特徴とする装置。
【請求項９】
請求項８に記載の装置であって、
前記ルールは、ｉｆ−ｔｈｅｎ形式のルールであり、
前記ルールのｉｆ節が、互いに階層関係にあり、かつ、上位階層から下位階層へ向かって前記ｉｆ節の構成要素が付加される関係にあることを特徴とする装置。
【請求項１０】
請求項８又は９に記載の装置であって、
前記検索手段は、下位階層に子ルールが含まれているか否かを判定し、前記下位階層に子ルールが含まれている場合に、前記子ルールを検索結果として出力し、前記下位階層に子ルールが含まれていない場合に、同一階層に未出力の兄弟ルールが含まれているか否かを判定し、同一階層に前記未出力の兄弟ルールが含まれている場合に、前記未出力の兄弟ルールを検索結果として出力し、同一階層に前記未出力の兄弟ルールが含まれていない場合に、上位階層の親ルールが空ルールであるか否かを判定し、前記上位階層の親ルールが空ルールでない場合に、前記親ルールを検索結果として出力することを特徴とする装置。
【請求項１１】
請求項８ないし１０の何れかに記載の装置であって、
前記比較手段は、前記後に検索されたルールの評価値が前記先に検索されたルールの評価値よりも大きい場合に、前記後に検索されたルールを採用することを特徴とする装置。
【請求項１２】
請求項１１に記載の装置であって、
前記比較手段は、前記先に検索されたルールの数が所定数に達している場合に、前記先に検索されたルールのうち評価値の低いルールの評価値と前記後に検索されたルールの評価値を比較することを特徴とする装置。
【請求項１３】
ルールを検索する方法において、
互いに階層関係にある複数のルールであって、上位階層から下位階層へ向かって前記ルールの構成要素が付加される関係にある前記複数のルールを記憶する記憶装置に記憶しておく第１のステップ
上位階層から下位階層へ向かって、かつ、同一階層で下位に含まれるルールの数が少ない方から多い方へ向かって前記記憶装置から前記ルールを検索する第２のステップと、
前記検索手段の検索順序に従って先に検索されたルールの評価値と後に検索されたルールの評価値を比較する第３のステップ
前記第３のステップの比較結果に応じて前記後に検索されたルールを採用するか否かを決定する第４のステップとを有することを特徴とする方法。
【請求項１４】
互いに階層関係にある複数のルールであって、上位階層から下位階層へ向かって前記ルールの構成要素が付加される関係にある前記複数のルールを記憶する記憶装置に記憶しておく第１のステップ
上位階層から下位階層へ向かって、かつ、同一階層で下位に含まれるルールの数が少ない方から多い方へ向かって前記記憶装置から前記ルールを検索する第２のステップと、
前記検索手段の検索順序に従って先に検索されたルールの評価値と後に検索されたルールの評価値を比較する第３のステップ
前記第３のステップの比較結果に応じて前記後に検索されたルールを採用するか否かを決定する第４のステップとを、コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、階層関係になる複数のルールのなかから所定のルールを検索する方法、装置、プログラム及び記録媒体に係り、特に、深さ優先検索により評価値の高い（又は評価値の低い）ルールを検索するための方法、装置、プログラム及び記録媒体に関する。
【０００２】
【従来の技術】
従来のデータ解析技術の中には、大量データの解析を指向した技術分野があり、これは「データマイニング」と呼ばれている。データマイニングの一手法として、分析対象データに内在する規則性を「ｉｆ  Ａ  ｔｈｅｎ  Ｂ」というｉｆ−ｔｈｅｎルールの形式で表現し、また、個々のルールについて評価値を算出し、評価値の大きい上位のルールを、あらかじめ設定された数だけ発見するというルール探索方法がある（例えば、特許文献１参照）。この特許文献１に示されたルール探索方法では、深さ優先探索の手法を用いることが示されている。
【０００３】
また、ルール探索における「冗長なルール」を排除する方法がある（例えば、特許文献１及び非特許文献１参照）。例として、「（１）  ｉｆ  Ａ  ｔｈｅｎ  Ｘ」と「（２）  ｉｆ  Ａ  ａｎｄ  Ｂ  ｔｈｅｎ  Ｘ」という２つのｉｆ−ｔｈｅｎルールを考える。ルール（２）のｉｆ条件「Ａ  ａｎｄ  Ｂ」は、ルール（１）のｉｆ条件「Ａ」に条件を付け加えたものである。また、ｔｈｅｎ部「Ｘ」は両方のルールで同一である。この時、条件の少ない方のルール、つまり（１）を「親ルール」（上位階層のルール）とし、親ルールに条件を付け加えたルール、つまり（２）の方を「子ルール」（下位階層のルール）とする。そして、子ルールの評価値が親ルールの評価値を越えない時、この子ルールは「冗長である」とする。
【０００４】
【特許文献１】
特開平８−７７０１０号公報
【非特許文献１】
鈴木著「データベースからの特徴的ルール発見のための一般性と正確性の信頼性同時評価手法」人工知能学会誌、Ｖｏｌ．１４  Ｎｏ．１、１９９９年１月、ｐ．１３９−１４７
【０００５】
【発明が解決しようとする課題】
ルール探索に基づくデータマイニングにおいては、有用なルールをいかに見やすく使用者に提示するかが重要であり、そのための方針の１つとして、冗長なルールの排除は有効である。特許文献１及び非特許文献１には、深さ優先のルール探索における冗長ルールの排除について記述がある。
【０００６】
しかし、特許文献１及び非特許文献１にはアルゴリズムの簡単な記述があるものの、具体的な手順が十分詳細には示されておらず、冗長ルールを完全に排除することができない場合がある。例えば、以下のようなケースでは冗長ルールが排除されない。次の３つのルールを考える。「（１）ｉｆ  Ａ  ｔｈｅｎ  Ｘ：評価値  ｃ１」、「（２）ｉｆ  Ｂ  ｔｈｅｎ  Ｘ：評価値  ｃ２」、「（３）ｉｆ  Ａ  ａｎｄ  Ｂ  ｔｈｅｎ  Ｘ：評価値  ｃ３」。これら３つのルールの評価値には、ｃ１＜ｃ３＜ｃ２  という関係があるものとする。このとき、ルール（３）は、親であるルール（２）よりも評価値が小さいので、冗長なルールであり、排除されるべきである。深さ優先探索では、まずルール（１）を評価し、次に、これの子ルールであるルール（３）を評価し、その後でルール（２）を評価するという順序をとる場合がある。ルール（３）を評価する時点で、その親ルールであるルール（１）の評価は済んでおり、ｃ１＜ｃ３であることがわかるが、ルール（２）の評価はまだ行われていないので、ルール（２）に対してルール（３）が冗長であることがわからない。ゆえに、ルール（３）は排除されず、残ってしまうことになる。
【０００７】
本発明の目的は、評価の低い（又は評価値の高い）冗長ルールを効果的に排除することができる方法、装置、プログラム及び記録媒体を提供することである。
【０００８】
【課題を解決するための手段】
本発明は、上位階層から下位階層へ向かって、かつ、同一階層で下位に含まれるルールの数が少ない方から多い方へ向かってルールを検索することを特徴とする。そして、好ましくは、先に検索されたルールの評価値と後に検索されたルールの評価値を比較し、その比較結果に応じて後に検索されたルールを採用するか否かを決定する。
【０００９】
具体的には、対象データの一部、または全部を読み込み、条件項目として用いる項目に順序付けを行い、順序を記憶しておく。順序の決め方は任意だが、例えば、対象データ中での項目の並び順をそのまま項目の順序とする。
【００１０】
候補ルールは、１個以上の条件節からなるルールである。本発明のルール発見方法では、条件項目の組み合わせによって生成し得る候補ルールを探索し、採用基準を満足するルールを発見する。ルール探索は、最初の候補ルールを決めるステップと、候補ルールの採否を判定するステップと、採用と判定されたルールを採用ルールに追加するステップと、現在の候補ルールを元に次の候補ルールを決めるステップからなり、次に生成すべき候補ルールがなくなるまで、上記のルール採否判定ステップ、採用ルール追加ステップ、次候補ルール決定ステップを繰り返す。
【００１１】
候補ルールを決める手順を以下に説明する。一般に、任意のルールの条件節に、条件節を１個付け加えてできるルールを、元のルールの子ルールと呼び、子ルールに対し、元のルールを親ルールと呼ぶ。この時、２個以上の条件節を持つルールは、複数の親ルールを持つことになる。しかし、ここではより限定的に、複数の親ルールのうち、順序が最も前の条件項目を持つものを親ルールとする。また、同じ親ルールを持つ子ルール同士を兄弟ルールと呼ぶことにする。この定義に従い、親ルールの下に子ルールを結び付け、兄弟ルールについては、条件節が持つ条件項目の順序に従い、順序がより前のものから順に並べる。また、条件節を持たない空ルールを考え、これを１個の条件節からなるルールの親ルールとする。これにより、全ての候補ルールの関係を、空ルールをルートとする１つの木構造に表すことができる。ただし、ルールの持つ条件節数の上限はあらかじめ定められているとする。なお、条件項目の順序を逆にし、順序が最も後の条件項目を持つものを親ルールとし、兄弟ルールについては、順序がより後のものから順に並べることも可能である。
【００１２】
こうして構成された木構造の上のルールを順に探索することにより、次の候補ルールを決めるのだが、この時、親ルールおよび兄弟ルールの並べ方とは逆方向にルールを探索する。つまり、順序が最も前の条件項目を持つものを親ルールとし、順序がより前の兄弟ルールから順に並べた木構造においては、順序がより後の条件項目を持つルールから、順序がより前の条件項目へ向かって、深さ優先でルールを探索する。逆に、順序が最も後の条件項目を持つものを親ルールとし、順序がより後の兄弟ルールから順に並べた木構造においては、順序がより前の条件項目を持つルールから、順序がより後の条件項目へ向かって、深さ優先でルールを探索する。
【００１３】
深さ優先の探索方法をより詳しく説明すると、順序が最も前の条件項目を持つものを親ルールとし、順序がより前の兄弟ルールから順に並べた木構造においては、まず、条件節数が１で、順序が最も後の条件項目をもつルールを最初の候補ルールとし、このルールを現在の候補ルールとして探索を始める。現在の候補ルールが子ルールを持つ場合は、順序が最も後の子ルールを次の候補ルールとする。現在の候補ルールが子ルールを持たない場合は、現在の候補ルールから、順序がより前の方向へ兄弟ルールを探索し、未評価の兄弟ルールがあれば、これを次の候補ルールとする。順序がより前の兄弟ルールがない場合は、現在の候補ルールの親ルールを現在の候補ルールと見なし、より順序が前の方向へ兄弟ルールを探索し、より順序が前の兄弟ルールあれば、これを次の候補ルールとする。なければ、さらに、その親ルールを現在の候補ルールと見なす、というように、順序がより前の兄弟ルールが見つかるまで親ルールへさかのぼる。そして、順序がより前の兄弟ルールが見つからずにルートノードまでたどり着いた場合は、ルール探索を終了する。
【００１４】
順序が最も後の条件項目を持つものを親ルールとし、順序がより後の兄弟ルールから順に並べた木構造においては、上記のルール探索の手順において、条件項目の順序を逆にする。すなわち、まず、条件節数が１で、順序が最も前の条件項目をもつルールを最初の候補ルールとする。また、子ルールを次の候補ルールとする場合は、順序が最も前の子ルールを次の候補ルールとする。また、兄弟ルールを探索する場合は、順序がより後の方向へ探索する。
【００１５】
探索の枝刈りによって、実際に評価する候補ルールの数を減らし、ルール発見方法の効率を向上させるには、上記のルール探索手順において、現在の候補ルールの子ルールを次の候補ルールとする際に枝刈り判定を行い、枝刈り条件を満足した場合には、現在の候補ルールには子ルールは存在しないものと見なし、兄弟ルールの探索に進むようにする。
【００１６】
【発明の実施の形態】
本発明の実施の第一の形態を説明する。以下の説明では、分析対象データを元に、
「ｉｆ  （１個以上の条件節）  ｔｈｅｎ  （１個の結論節）」
という形式のルールを対象とするが、本発明はこれに限定されるものではない。
【００１７】
図１に分析対象データの例を示す。これは複数のフィールドから構成されるレコードの集合であり、リレーショナルデータベースの検索結果として得られるレコード集合や、ＣＳＶファイル等がその典型である。図１では、横１行が１個のレコードであり、各レコードは「顧客＃」などの７個のフィールドからなっている。通常、これらのフィールドはそれぞれ何らかの値を持っているが、本実施形態では、何の値も持っていないフィールドが存在する場合も想定している。図１の例は、ある商店における顧客データであり、各レコードが１人の顧客に対応し、それぞれのレコードにおける各フィールドが個々の顧客に関する種々の情報を表す値を持っている。なお、最初の行に書かれている「顧客＃」、「住所」などは、それぞれのフィールドに付与された名前であり、これらはフィールドが持つ値ではない。つまり、最初の行は顧客に対応するレコードではなく、フィールド名を表す「見出し」行である。
【００１８】
ルール発見方法では、これらのフィールドのうちの１個を「結論項目」、結論項目以外のフィールドのうちの１個以上を「条件項目」として用いる。例えば図１において、「購入総額」を結論項目、「住所」「年齢」「性別」「職業」を条件項目とする。
【００１９】
ルールを構成する「条件節」、「結論節」は、これら「項目」と、その項目に該当するフィールドが持つ値の組であり、「（項目名）＝（値）」という形式で記述する。項目名とは、すなわち、その項目に該当するフィールドの名前である。図１において「住所＝横浜市」などが条件節、結論節の例である。ここで、１個の条件節もしくは結論節「Ａ＝ａ」を考え、任意のレコードにおいて、項目「Ａ」に該当するフィールドが値「ａ」を持つとき、このレコードは、『「Ａ＝ａ」を満足する』ということにする。
【００２０】
個々のルールは、評価尺度によって算出される評価値を持つ。種々の評価尺度が考えられるが、一例として、「ｉｆ  Ａ  ｔｈｅｎ  Ｘ」というルールの評価値μ（Ａ，Ｘ）を下記の数１で算出する。
【００２１】
【数１】
μ（Ａ，Ｘ）＝Ｐ（Ａ）＾α・Ｐ（Ｘ｜Ａ）・ｌｏｇ｛Ｐ（Ｘ｜Ａ）／Ｐ（Ｘ）｝
ここで、Ｐ（Ａ）＾α  は  Ｐ（Ａ）のα乗を表し、αは  ０≦α≦１  の実数とする。また、ｌｏｇ  の底は任意とするが、通常は、自然対数か常用対数、または底２の対数を用いる。Ｐ（Ａ）、Ｐ（Ｘ）はそれぞれ、分析対象データにおいて条件節Ａ、結論節Ｘを満足するレコードの割合であり、Ｐ（Ｘ｜Ａ）はＡを満足するレコードのうちで、Ｘをも満足するレコードの割合である。なお、Ａが２個以上の条件節からなる場合は、Ｐ（Ａ）はＡを構成する条件節を全て満足するレコードの割合であり、Ｐ（Ｘ｜Ａ）はＡを構成する条件節を全て満足するレコードのうちで、Ｘをも満足するレコードの割合である。なお、数１の右辺のうち、
Ｐ（Ａ）＾α
をルールの「一般性」、
Ｐ（Ｘ｜Ａ）・ｌｏｇ｛Ｐ（Ｘ｜Ａ）／Ｐ（Ｘ）｝
をルールの「精度」と呼ぶ。
【００２２】
評価値の大きい、上位のルールを発見することがルール発見の目的であるが、さらに、評価値の大小に加え、ルールが冗長であるかどうかを含めてルールを評価する。例として、「（１）ｉｆ  Ａ  ｔｈｅｎ  Ｘ」と「（２）ｉｆ  Ａ  ａｎｄ  Ｂ  ｔｈｅｎ  Ｘ」という２個のルールを考える。（１）と（２）は結論節「Ｘ」が同一で、かつ、（２）のｉｆ部「Ａ  ａｎｄ  Ｂ」は、（１）のｉｆ部「Ａ」に条件節「Ｂ」を付け加えたものになっている。このように、「結論節が同一」で、かつ、「一方のｉｆ部に条件節を１個以上付け加えたものが、もう一方のｉｆ部である」場合、条件節の少ない方を先祖ルール、条件節の多い方を子孫ルールと呼ぶことにする。先の例では、（１）が先祖ルール、（２）が子孫ルールである。そして、子孫ルールが先祖ルールの評価値を越えない（評価値が小さい）場合、この子孫ルールは先祖ルールに対して「冗長である」と見なす。なお、一般に、１つの子孫ルールについて先祖ルールは複数ある。上述の（２）のルールの場合、（１）の他に「ｉｆ  Ｂ  ｔｈｅｎ  Ｘ」も先祖ルールである。このような場合、子孫ルールが少なくとも１つの先祖ルールの評価値を越えない場合、その子孫ルールは冗長であると見なす。この「冗長」の概念に従い、冗長でなく、かつ、評価値が大きい上位のルールを発見することをルール発見の目的とする。なお、別の考え方として、評価値ではなく、子孫ルールが先祖ルールの精度を越えない場合に冗長と見なすという方法も考えられる。尚、評価値の大きいルールとは逆に、評価値の小さいルールを発見することを目的としてもよい。
【００２３】
本発明では、複数のルールのｉｆ節が互いに階層関係にある。つまり、上位階層から下位階層へ向かってルールのｉｆ節の構成要素が付加される。よって、上位階層に比較して下位階層のルールのｉｆ節の構成要素の数が多い。
【００２４】
本実施形態のルール発見では、条件項目と値の組み合わせによって生成され得るルールを全て探索し、その中から冗長でなく、かつ、評価値が大きい上位のルールを発見する。ただし、結論節はあらかじめ固定されているものとする。ルール探索の手順を以下に説明する。ルール探索に先立って、条件項目の候補、各条件項目が取り得る値の集合、結論節、最大条件節数（ｉｆ部に含まれる条件節数の上限）、出力ルール数が設定されていることとする。
【００２５】
図２を用いて、ルールを探索する順序を示す。この例では、ａ１、ａ２、ａ３を条件項目の候補とし、各条件項目はそれぞれ｛０，１｝の二値を取り得るとし、最大条件節数を３としている。また、これらの条件項目は、ａ１、ａ２、ａ３の順に順序付けされており、ａ１が最初、ａ３が最後であるものとする。図２の場合、条件項目と値の組み合わせによって生成され得るルールは、条件節数が１のものが６個、条件節数が２のものが１２個、条件節数が３のものが８個の、合計２６個である。それぞれのルールは、図２では四角形で表されている。なお、結論節は固定されており、全てのルールで同一なので、省略している。ここで、前述の先祖ルール、子孫ルールの関係の特別な場合として、「一方のｉｆ部に条件節を１個だけ付け加えたものが、もう一方のｉｆ部である」場合、条件節の少ない方を親ルール、条件節の多い方を子ルールと呼ぶことにする。図２において、四角形を結ぶ点線はルール間の親子関係を表し、点線で結ばれたルールのうち、上側が親ルール、下側が子ルールである。例えば、図中の点線２０１は、ルール「ａ１＝０」が、ルール「ａ１＝０  ａｎｄ  ａ２＝０」の親ルールであることを表している。ここで、「ａ２＝０」もルール「ａ１＝０  ａｎｄ  ａ２＝０」の親ルールであるが、図中では点線で結ばれていないことに注意が必要である。一般に、条件節を２個以上持つルールは、複数の親ルールを持つが、この図においては、順序がより前の条件項目を持つ親ルール１個とだけ結び付けることにする。先のルール「ａ１＝０  ａｎｄ  ａ２＝０」の例では、「ａ１＝０」、「ａ２＝０」の２個の親ルールを持つが、このうち条件項目ａ１の方がａ２よりも順序が前なので、ルール「ａ１＝０  ａｎｄ  ａ２＝０」は、「ａ１＝０」と結び付けられている。また、図２では形式上、条件節が１個のルールは、条件節が０個のルール（空ルール）２０４の子ルールと考える。このようにして親ルールと子ルールを結び付けることにより、任意の親ルールについて、その下に結びつけられる子ルールは、親ルールの持つ条件項目よりも順序が後の条件項目を１つ持つことになる。ゆえに、最後の条件項目（図２では、ａ３）を持つルールについては、それよりも順序が後の条件項目が存在しないので、その下に子ルールも存在しない。また、図２では、同じ親ルールと結び付けられた子ルール同士について、順序がより前の条件項目を持つルールを左側に置くことにしている。また、条件項目のそれぞれにおいて、取り得る値にも順序付けがされていることとし、条件項目が同じで値が異なるルールについては、値の順序がより前のルールを左側に置くことにしている。このようにルールを配置することにより、条件項目の組み合わせによって生成され得るルールは全て、図２に示す木構造の中の１つのノードとして配置される。
【００２６】
これら２６個のルールを、図２の矢印で示された順に探索する。探索の開始点は、条件節が１個で、最後の条件項目を持つルールである。図２の例では、最後の条件項目はａ３であり、したがって、開始点はルール２０２となっている。なお、条件節が１個で、条件項目ａ３を持つルールはもう１つある。ルール２０３がそれだが、これらのうち、値の順序がより後である、ルール２０２の方を開始点とする。すなわち、図２において、より右側にあるルールである。つまり、上位階層から下位階層へ向かって、かつ、同一階層で下位に含まれるルールの数が少ない方から多い方へ向かってルールを検索する。
【００２７】
図２の矢印で表された探索の手順を図３に示す。ステップ３０１では、開始点のルールを現在の候補ルールとする。ステップ３０２では、現在の候補ルールの評価値を算出し、以下の３つの条件を全て満足していれば、このルールを採用ルールに加える。
【００２８】
（１）現在の候補ルールの評価値が０より大きいこと。
【００２９】
（２）その時点までに採用されたルールの中に、現在の候補ルールの先祖ルールで、かつ、現在の候補ルールの評価値以上の評価値を持つルールが存在しないこと。
【００３０】
（３）現在の候補ルールの評価値の順位が、その時点までに採用されたルールの評価値の上位から数えて、あらかじめ定められた出力ルール数までに入っていること。
【００３１】
なお、現在の候補ルールを採用した結果、その時点までに採用したルールの数が、あらかじめ定められた出力ルール数を越えた場合は、採用したルールのうちで最も評価値の小さいルールの１個を採用ルールから削除する。
【００３２】
ステップ３０３では、現在の候補ルールの下に子ルールが結び付いているのならば、それらのうちの最も右側のルール（条件項目の順序が最も後で、かつ、値の順序が最も後のルール）を新たに現在の候補ルールとし、ステップ３０２へ戻る。そうでなければステップ３０４へ進む。ステップ３０４では、現在の候補ルールと同じ親ルールに結び付けられたルールが現在の候補ルールの左隣（値の順序が１つだけ前、または、条件項目の順序が１つだけ前）にあれば、それを新たに現在の候補ルールとし、ステップ３０２へ戻る。そうでなければステップ３０５へ進む。ステップ３０５では、現在の候補ルールの親ルールが空ルールであれば、ルール探索を終了する。そうでなければ、現在の候補ルールの親ルールを新たに現在の候補ルールとして、ステップ３０４へ戻る。以上の処理によって採用されたルールの集合が、ルール発見方法の結果となる。
【００３３】
上記で説明したルール発見方法を実施する装置の構成を図４に示す。コンピュータがこの装置の典型的な例である。装置は、表示装置４０１、入力装置４０２、演算装置４０３、主記憶装置４０４、二次記憶装置４０５が、互いにバス４０７で接続されて構成される。表示装置４０１は、使用者に対して情報を提示する機能を持つ。典型例として、ディスプレイモニタやプリンタなどが該当する。入力装置４０２は、使用者から情報を受け取る機能を持つ。典型例として、キーボード、マウスなどが該当する。主記憶装置４０４は二次記憶装置４０５に比べて、データの読み出し、書き込みを高速に行えるが、記憶容量は小さい。主記憶装置の典型例は半導体メモリである。また、二次記憶の典型例は磁気ディスクである。演算装置４０３は、これらの装置間のデータ転送の制御や、データに対する演算処理を行う。また、分析対象データ４０６は、二次記憶に保持される。
【００３４】
この装置を用いたルール発見の処理の流れを図５に示す。
【００３５】
まず、ステップ５０１において、分析対象データを二次記憶装置から主記憶装置に読み込む。なお、この時、分析対象データに含まれる全レコード数を数え、その値を主記憶装置に格納しておく。
【００３６】
ステップ５０２では、ルール発見の処理に必要なパラメータを入力する。ここで入力されるパラメータは、条件項目として用いる１個以上の項目名、結論項目として用いる１個の項目名、結論値として用いる値（結論項目のフィールドに現れる値でなければならない）、最大条件節数（１以上の整数）、出力ルール数（１以上の整数）、評価尺度パラメータ（数１におけるα）である。これらのパラメータの値は使用者が決定し、入力装置を介して入力する。入力された値は主記憶装置に格納する。
【００３７】
ステップ５０３では、ステップ５０２のパラメータ入力で条件項目、結論項目として入力された個々の項目ごとに、分析対象データのフィールドが持つ値に対して１から始まる連続した整数を値番号として付与する。そして、フィールドの持つ値をこの値番号に置き換えたデータを作成する。値の置き換えの例を図６に示す。この例では、「住所」、「年齢」、「性別」、「職業」、「来店回数」を条件項目、「購入総額」を結論項目として用いることとしている。どの値にどの値番号を対応づけるかは任意であるが、それぞれの項目において、同じ値には同じ値番号が対応している必要がある。例えば、分析対象データに現れた順に、すなわち上に現れた値から順に、番号を付与する。また、フィールドの持つ値が数値である場合は、値の大きさの順に番号を付与しても良い。図６で、例えば、項目「性別」において、「男」は値番号「１」、「女」は値番号「２」に置き換えられている。また、元の分析対象データにおいて値を持たないフィールドに対しては、欠損を表す特別な値番号として０が置かれる。このようにして、各フィールドの値を値番号に置き換えてできたデータを主記憶装置に格納し、以後は、これをルール発見処理の対象とする。なお、このとき、それぞれの項目ごとの値番号の最大値を主記憶装置に格納しておく。
【００３８】
また、条件項目には、分析対象データにおける項目の並びにしたがって、左から順に、１から始まる連続した整数を項目番号として付与する。
【００３９】
上記のフィールドの持つ値と値番号との対応、および、条件項目と項目番号の対応がわかるように、図７に示すような対応表を主記憶装置に格納しておく。
【００４０】
ステップ５０４では、採用ルールリストの作成と初期化を行う。採用ルールリストは、図８に示すように、ステップ５０２で入力された出力ルール数だけの要素（８０１）をリストにしたものである。単方向リスト、双方向リストのいずれでも可能だが、ここでは双方向リストにしている。それぞれの要素は、ルール構造体８０２と、前後の要素を参照する２つのポインタｐｒｅｖ８０３、ｎｅｘｔ８０４からなっている。なお、先頭の要素においては、その前の要素は存在しないので、ポインタｐｒｅｖには無効値（どの要素をも参照しないことが保証されている値）を保持する。同様に、末尾の要素において、ポインタｎｅｘｔには無効値を保持する。
【００４１】
ルール構造体８０２は、１個のｉｆ−ｔｈｅｎ  ルールを表すためのデータ構造で、以下のデータの集まりである。
【００４２】
・条件節数
・条件項目［１］、条件項目［２］、…、条件項目［ｎ］
・値［１］、値［２］、…、値［ｎ］
・評価値
ここで、ｎはステップ５０２で入力された「最大条件節数」である。例として、
ｉｆ  Ａ＝ａ１  ａｎｄ  Ｂ＝ｂ２  ｔｈｅｎ  Ｘ＝ｘ１
というルールを考える。データ項目「条件節数」には、ルールが持つ条件節の数を格納する。このルールの例では、「Ａ＝ａ１」、「Ｂ＝ｂ２」の２個の条件節を持つので、「条件節数」の値は２である。データ項目「条件項目［ｉ］」（ただし、ｉ＝１，２，…，ｎ）には、ルールが持つ条件節のそれぞれについて、その条件項目に対応する項目番号を格納する。上記ルールの例では、データ項目「条件項目［１］」には条件項目「Ａ」に対応する項目番号を、データ項目「条件項目［２］」には条件項目「Ｂ」に対応する項目番号を格納する。なお、
ｉ＞条件節数
となる「条件項目［ｉ］」に格納される値は不定で良い。データ項目「値［ｉ］」（ただし、ｉ＝１，２，…，ｎ）には、ルールが持つ条件節のそれぞれについて、その値に対応する値番号を格納する。上記ルールの例では、「値［１］」には値「ａ１」に対応する値番号を、「値［２］」には値「ｂ２」に対応する値番号を格納する。なお、
ｉ＞条件節数
となる「値［ｉ］」に格納される値は不定で良い。データ項目「評価値」には、数１で算出される、このルールの評価値を格納する。
【００４３】
採用ルールリストの作成、初期化処理では、上記の採用ルールリストを主記憶装置に作成する。また、採用ルールリストの先頭の要素を参照するポインタｈｅａｄ８０５と末尾の要素を参照するポインタｔａｉｌ８０６を、やはり、主記憶装置に格納しておく。次に、この採用ルールリストの各要素において、ルール構造体の「条件節数」と「評価値」の値を０に初期化する。
【００４４】
ステップ５０５では、上記の採用ルールリストとは別に、ルール構造体を１個、主記憶装置に確保し、これをカレントルールのための領域とする。そして、第１の候補ルールの条件節数、条件項目の項目番号、値番号をカレントルールに設定する。この第１の候補ルールとは、図２で示した開始点のルール、すなわち、条件節数が１で、順序が最も後の条件項目と、その条件項目の取り得る値のうちで順序が最も後の値番号の組を条件節として持つルールである。したがって、カレントルールのルール構造体の「条件節数」には１を、「条件項目［１］」には条件項目の項目番号のうち最も大きい番号を、「値［１］」にはその条件項目が取り得る値番号のうちで最も大きい番号をセットする。
【００４５】
ステップ５０６では、カレントルールの評価値を、数１によって算出する。この手順は次のようになる。
【００４６】
（１）カレントルールの全ての条件節を満足するレコードの数を数え、これを「ｉｆカウント」とする。
【００４７】
（２）ステップ５０２で入力された結論項目と結論値を満足するレコードの数を数え、これを「ｔｈｅｎカウント」とする。
【００４８】
（３）カレントルールの条件節の全てを満足し、かつ、ステップ５０２で入力された結論項目と結論値を満足するレコードの数を数え、これを「ｈｉｔカウント」とする。
【００４９】
（４）上記の「ｉｆカウント」、「ｔｈｅｎカウント」、「ｈｉｔカウント」から、数１により評価値を算出し、カレントルールのルール構造体のデータ項目「評価値」に格納する。
【００５０】
上記ステップ（１）（２）（３）では、主記憶装置に格納された、値番号へ置換済みの分析対象データのレコードを１個ずつ順に参照しながら、そのレコードが条件節、および結論項目と結論値を満足するか調べ、これらを満足するレコード数を数える。上記ステップ（４）では、数１のＰ（Ａ）、Ｐ（Ｘ）、Ｐ（Ｘ｜Ａ）をそれぞれ、
Ｐ（Ａ）←  ｉｆカウンタ／全レコード数
Ｐ（Ｘ）←  ｔｈｅｎカウンタ／全レコード数
Ｐ（Ｘ｜Ａ）←  ｈｉｔカウンタ／ｉｆカウンタ
によって算出する。なお、「全レコード数」は、ステップ５０１において数えてある。これらを用いて、数１に基づいて評価値を算出する。なお、数１中のαはステップ５０２において、使用者が入力している。こうして算出した評価値は、カレントルールのルール構造体のデータ項目「評価値」に格納する。
【００５１】
ステップ５０７では、カレントルールの採用判定を行う。この処理の詳細を図９に示す。
【００５２】
ステップ９０１では、カレントルールの評価値が０より大きければステップ９０２へ進む。そうでなければ、カレントルールを不採用とし、採用判定処理を終了する。
【００５３】
ステップ９０２では、採用ルールリストの先頭の要素を比較ルールとする。この先頭の要素は、ポインタｈｅａｄで参照できる。
【００５４】
ステップ９０３では、カレントルールの評価値と比較ルールの評価値を比較し、カレントルールの評価値の方が大きければステップ９０４へ進む。そうでなければステップ９０５へ進む。
【００５５】
ステップ９０４は、カレントルールを採用し、採用ルールリストへ挿入する処理である。この手順は次のようになる。
【００５６】
（１）採用ルールリストの末尾の要素を、比較ルールの前に挿入する。末尾の要素は、ポインタｔａｉｌで参照できる。比較ルールが先頭のルールであった場合は、ここで挿入した要素が新たに先頭の要素となるので、この新たな先頭の要素を参照するようにポインタｈｅａｄを更新する。また、これまで末尾から２番目だった要素が、新たに末尾の要素となるので、この新たな末尾の要素を参照するようにポインタｔａｉｌを更新する。
【００５７】
（２）挿入した要素のルール構造体へ、カレントルールのルール構造体の内容を上書きコピーする。
【００５８】
このようにして、採用ルールリストの要素数は変わらず、カレントルールの内容が採用ルールリストに挿入される。その後、採用判定処理を終了する。
【００５９】
ステップ９０５では、比較ルールがカレントルールの先祖ルールであるかを調べる。比較ルールがカレントルールの先祖ルールならば、カレントルールは冗長ルールなので、不採用とし、採用判定処理を終了する。そうでなければ、ステップ９０６へ進む。
【００６０】
ステップ９０６では、比較ルールが採用ルールリストの末尾のルールであるかを調べる。これは、ポインタｔａｉｌが参照している要素が、比較ルールであるかどうかを調べればわかる。そして、末尾のルールならば、カレントルールは、採用ルールリストの末尾のルールよりも評価値が大きくないので、不採用とし、採用判定処理を終了する。そうでなければ、ステップ９０７へ進む。
【００６１】
ステップ９０７では、採用ルールリストにおける、比較ルールの次の要素、すなわち、比較ルールのポインタｎｅｘｔが参照している要素を新たに比較ルールとし、ステップ９０３へ戻る。
【００６２】
以上がカレントルールの採用判定処理である。
【００６３】
ステップ５０８では、次の候補ルールを新たにカレントルールとする。これは、図３のステップ３０３から３０５の処理に相当する。この、カレントルールの更新処理の詳細を図１０に示す。ここで、ステップ５０２で入力された最大条件節数をＬとし、条件項目の数をＭ、カレントルールのルール構造体のデータ項目「条件節数」をｃとする。条件項目の数をＭとしたので、条件項目の項目番号は１から始まり、Ｍで終わることになる。
【００６４】
ステップ１００１は、図３のステップ３０３に相当する。ここでは、カレントルールの子ルールが次の候補ルールとなるかを判定する。まず、最大条件節数Ｌとカレントルールの条件節数ｃが、Ｌ＞ｃでなければ、カレントルールの条件節数は既に最大条件節数に達しているということなので、その子ルールは次候補ルールにならない。Ｌ＞ｃであれば、次に、カレントルールの条件節のうちで、順序が最も後のもの、すなわち、ｃ番目の条件節の項目番号である「条件項目［ｃ］」を調べる。これが、
条件項目［ｃ］＜Ｍ
でなければ、カレントルールはＭ番目の条件項目、すなわち、最後の条件項目を条件節に持っているということなので、図２のルール木の構造上の制約（子ルールは、親ルールよりも順序が後の条件項目を持つ）から、カレントルールに条件節を付け加えて子ルールを作ることはできない。したがって、子ルールは次の候補ルールとはならない。以上から、
Ｌ＞ｃ  かつ  条件項目［ｃ］＜Ｍ
ならば、ステップ１００２に進み、カレントルールの子ルールを新たにカレントルールとする。そうでなければ、ステップ１００３へ進む。
【００６５】
ステップ１００２では、カレントルールの条件節数、すなわち、ｃの値を１増やす。そして、条件項目［ｃ］に、最後の条件項目の項目番号であるＭをセットする。また、値［ｃ］には、Ｍ番目の条件項目の取り得る値番号のうち最大の番号をセットする。こうすることにより、カレントルールの子ルールのうちで右端のもの、すなわち、最も大きい項目番号を持ち、かつ、その条件項目において最も大きい値番号を持つルールが新たにカレントルールのルール構造体にセットされる。そして、カレントルールの更新処理を終了する。
【００６６】
ステップ１００３では、値［ｃ］に格納されている値番号を調べる。値［ｃ］＞１であれば、条件項目［ｃ］を変更せず、値番号を１だけ小さくしたルールがカレントルールの左隣のルールとなるので、ステップ１００４へ進む。そうでなければ、条件項目［ｃ］を変更するため、ステップ１００５へ進む。
【００６７】
ステップ１００４では、カレントルールのｃ番目の条件節の値である、値［ｃ］を１だけ小さくする。これにより、カレントルールの左隣のルールがカレントルールのルール構造体にセットされる。そして、カレントルールの更新処理を終了する。
【００６８】
ステップ１００５、１００６は、カレントルールのｃ番目の条件節の項目番号を１だけ小さくできるかを判定する処理だが、カレントルールの条件節数が１の場合と、１より大きい場合で判定方法が異なる。ステップ１００５は、カレントルールの条件節数が１の場合である。この場合、条件項目［ｃ］に格納されている項目番号が１よりも大きいならば、この項目番号を１だけ小さくできるとして、ステップ１００７へ進む。ステップ１００６は、カレントルールの条件節数が１より大きい場合である。この場合、条件項目［ｃ］に格納されている項目番号が、（ｃ−１）番目の条件節、すなわち、カレントルールの親ルールの最後の条件節の項目番号である、条件項目［ｃ−１］に１を足した値より大きければ、条件項目［ｃ］の項目番号を１だけ小さくできるとして、ステップ１００７へ進む。そうでなければ、項目番号を小さくすることはできない。これは、ステップ１００１と同様に図２のルール木の構造上の制約（子ルールは、親ルールよりも順序が後の条件項目を持つ）からである。ステップ１００５、１００６において、条件項目［ｃ］の項目番号を１だけ小さくできない場合は、ステップ１００８へ進む。
【００６９】
ステップ１００７では、カレントルールのｃ番目の条件節の項目番号である、条件項目［ｃ］を１だけ小さくし、この条件項目が取り得る値番号のうち最大の番号を値［ｃ］にセットする。これにより、カレントルールの左隣のルールがカレントルールのルール構造体にセットされる。そして、カレントルールの更新処理を終了する。上記、ステップ１００３から１００７（図１０で破線で囲んだ部分）が図３のステップ３０４に相当する。
【００７０】
ステップ１００８は、図３のステップ３０５に相当する。ここでは、カレントルールの親ルールが図２における空ルール２０４であるかを判定する。これは、カレントルールの条件節数ｃが１であるか、と同値であり、ｃ＝１ならば、親ルールは空ルールである。ここでは、ｃ＝１でなければ（親ルールが空ルールでなければ）、ステップ１００９へ進み、ｃ＝１ならば（親ルールが空ルールであれば）、ステップ１０１０へ進む。
【００７１】
ステップ１００９では、カレントルールの条件節数を１だけ小さくする。これは、カレントルールの条件節のうち、最後の条件節を取り除くのと同じことになり、これにより、カレントルールの親ルールがカレントルールのルール構造体にセットされる。そして、ステップ１００３へ戻る。
【００７２】
ステップ１０１０では、次の候補ルールがないので、カレントルールのルール構造体の条件節数に０をセット（無効なルールであることを意味する）し、カレントルールの更新処理を終了する。
【００７３】
以上が、カレントルールの更新処理である。
【００７４】
ステップ５０９では、ステップ５０８でカレントルールの条件節数に０がセットされているならば、これを無効なルールと見なし、ステップ５１０へ進む。これは、ルール探索が終了したことを意味する。カレントルールの条件節数が０でなければ、有効なルールとみなし、ステップ５０６へ戻る。
【００７５】
ステップ５１０では、その時点での採用ルールリストの内容をルール発見処理の結果とし、採用ルールリストの先頭から順に、ルール構造体の内容を出力装置へ出力する。ただし、ルールの評価値が０より大きくない場合は、そのルールは出力しない。ルール構造体の、条件項目［ｉ］、値［ｉ］にはそれぞれ項目番号、値番号が格納されているが、出力装置へルールを出力する場合は、これらの番号を、対応する項目名、フィールドの持つ値に置き換える。これらの項目番号、値番号を、どの項目名、値に置き換えるかは、図７に示した対応表を参照すればわかる。ルールの出力例を図１１に示す。これは、出力ルール数を５、最大条件節数を２として、本実施形態で示したルール発見を行った結果である。一方、図１２は、従来の深さ探索による特徴ルール発見結果の出力例である。図１２におけるルール［４］は、ルール［３］の子ルールであり、かつ、ルール［３］よりも評価値が低いので、冗長ルールである。しかし、順序がより前の条件項目から探索する深さ優先探索では、「年齢＝３０代  ａｎｄ  職業＝会社員」というルールは「年齢＝３０代」の子ルールとして、「職業＝会社員」よりも先に評価されてしまうので、「職業＝会社員」よりも評価値が小さいにもかかわらず採用されてしまう。この冗長ルールがあるせいで、図１１のルール［５］が、図１２では６番目以降となってしまい、出力されていない。一方、本実施形態のルール発見方法では、「年齢＝３０代  ａｎｄ職業＝会社員」というルールは「年齢＝３０代」、「職業＝会社員」の両方よりも後に評価されるので、これを評価するの時点で「職業＝会社員」よりも評価値が小さいことがわかり、冗長ルールが採用されることを避けることができる。
【００７６】
本発明の実施の第二の形態を説明する。
【００７７】
条件項目数、最大条件節数が多くなると、探索すべきルールの総数は非常に大きくなり、これら全てを評価するのに時間がかかる。そこで、探索の枝刈り手法によって実際に評価するルールの数を減らすことで、ルール発見処理の効率を向上させることを考える。この枝刈りの基本的な考え方は、特許文献１に示されている。枝刈り処理を含んだルール発見の実施形態は第一の実施形態とほとんど同じだが、図１０に示した、カレントルールの子ルールが次の候補ルールとなるかを判定する処理（ステップ１００１）を以下のように変更する。
【００７８】
図１０のステップ１００１では、
（１）  Ｌ  ＞  ｃ
（２）  条件項目［ｃ］  ＜  Ｍ
という２つの条件が満たされればステップ１００２へ進むが、本実施形態では、上記の２条件に、
（３）  子ルールの評価値上界  ＞  カレントルールの評価値
（４）  子ルールの評価値上界  ≧  採用しきい値
という２つの条件を加え、これら４つの条件が全て満たされたときに、ステップ１００２へ進み、そうでなければステップ１００３へ進む。ここで、子ルールの評価値上界は、
【００７９】
【数２】
（ｈｉｔカウント／全レコード数）＾α・ｌｏｇ｛全レコード数／ｔｈｅｎカウント｝
で計算される。この計算式は、特許文献１に示されている。数２の、全レコード数、ｈｉｔカウント、ｔｈｅｎカウントは、図５のステップ５０６で用いたものである。また、αは、数１のαであり、ステップ５０２で使用者が入力した値である。これらは、いずれもステップ５０６で使用したものなので、その値を主記憶装置に保存しておき、数２で用いる。また、「採用しきい値」とは、その時点における採用ルールリストの末尾の要素のルール構造体に格納されている評価値である。ステップ１００１を上記のように変更することにより、条件（３）（４）の一方でも満たされない時にはカレントルールの子ルールは探索されず、第一の実施形態の場合と比べて、評価するルールの数を減らすことができる。
【００８０】
上記で追加した条件（３）（４）は、カレントルールの評価値算出に用いた値と、採用ルールリストの末尾の要素を参照するだけで評価できるため、第一の実施形態の場合と比べて、枝刈りの処理のために特別の記憶領域を必要とせず、また、多くのデータ参照、計算量も必要としない。
【００８１】
本発明の実施の第三の形態を説明する。
【００８２】
これは、深さ優先探索の特徴を利用し、第一および第二の実施形態におけるカレントルールの  ｉｆカウント、ｈｉｔカウントを得る処理を効率化したものである。その仕組みを図１３に示す。図の上部の木構造１３０３は、図２と同様のルール木である。図左部の表１３０２は、分析対象データであるレコードの集合を表している。レコードには、上から順に、１から始まる番号が付与されている。レコード数をＮ個とすれば、最後のレコード番号はＮである。図右部の表１３０３は、レコードとルールの対応を表すインデックスであり、表の各行は各レコードに、表の各列は、カレントルールと、その先祖ルール、および空ルール（条件節数が０のルール）に対応している。表に格納されている数字は、各列が対応するルールの条件節を満足するレコードのレコード番号であり、「０」は、インデックスの終わりを意味する。ただし、ここで先祖ルールとは、ルール木１３０１において、ルートノードからカレントルールへ至る経路上にあるルールのことである。
【００８３】
図１３において、２個以上の条件節を持つ任意のルールをＡ、ルール木におけるルールＡの親ルールをＰとし、ルールＡについて、ｉｆカウント、ｈｉｔカウントを得る処理を考える。ｉｆカウント、ｈｉｔカウントを得るためには、各レコードについて、ルールＡの条件節を満足するかどうかをチェックする。ここで、ルールＡはルールＰに条件節を１個付け加えてできるルールなので、ルールＰの条件節を満足しないレコードは、ルールＡの条件節も満足しない。したがって、ルールＡのｉｆカウント、ｈｉｔカウントを得る処理において、ルールＰの条件節を満足するレコードのみをチェックすれば良い。そして、深さ優先探索の特徴により、ルールＡを評価する時点では、ルールＰの評価は終わっているので、どのレコードがルールＰの条件節を満足するかがわかっている。図１３のインデックス１３０３には、ルールＡの親ルールＰについて、ルールＰを満足するレコードの番号が記録されている。ルールＡのｉｆカウント、ｈｉｔカウントを得る際には、インデックス１３０３の中の、ルールＰのレコードインデックスに記録された番号のレコードを上から順にチェックすれば良い。そして、インデックスの中で「０」に出会ったら、チェックするべきレコードは終了となる。また、チェックの結果、ルールＡの条件節を満足したレコードについては、インデックス１３０３の中の、ルールＡのレコードインデックスにそのレコード番号を記録しておく。そして、次に、ルールＡの子ルールを評価する時には、このルールＡのレコードインデックスを参照して、レコードのチェックを行う。
【００８４】
なお、１個の条件節を持つルールを評価する場合は、空ルールを親ルールと見なし、空ルールに対応するレコードインデックスを参照する。空ルールについては、全てのレコードは空ルールを満足すると考える。したがって、インデックス１３０３の中の、空ルールに対応するレコードインデックスには、全てのレコードの番号（すなわち、１からＮまで）が格納されている。この、空ルールに対応するレコードインデックスは、ルールの探索を始める前に、あらかじめ作成しておく。
【００８５】
【発明の効果】
本発明によれば、評価の低い（又は評価値の高い）冗長ルールを効果的に排除することができる。
【００８６】
また、本発明によれば、多くの記憶領域を必要とせずに、枝刈りによるルール発見方法の処理効率を向上することができる。
【図面の簡単な説明】
【図１】分析対象データの例。
【図２】ルール探索の順序を示す図。
【図３】ルール探索の手順を示す図。
【図４】ルール発見方法を実施する装置の構成の例。
【図５】ルール発見方法の処理を表すフローチャート。
【図６】番号に置き換えられた分析対象データの例。
【図７】番号と値、および、番号と条件項目の対応表。
【図８】採用ルールリストの構造。
【図９】カレントルールの採用判定の処理を表すフローチャート。
【図１０】次の候補ルールをカレントルールとする処理を表すフローチャート。
【図１１】冗長ルールを排除したルール発見の結果の例。
【図１２】冗長ルールを含むルール発見の結果の例。
【図１３】レコードインデックスとルールの関係を表す図。
【符号の説明】
２０１…親ルールと子ルールを結ぶ点線、２０２…最後の条件項目を持つ、１個の条件節からなるルール、２０３…最後の条件項目を持つ、１個の条件節からなる別のルール、２０４…空ルール。
【図１】
2005038073.tif 000003
【図２】
2005038073.tif 000004
【図３】
2005038073.tif 000005
【図４】
2005038073.tif 000006
【図５】
2005038073.tif 000007
【図６】
2005038073.tif 000008
【図７】
2005038073.tif 000009
【図８】
2005038073.tif 000010
【図９】
2005038073.tif 000011
【図１０】
2005038073.tif 000012
【図１１】
2005038073.tif 000013
【図１２】
2005038073.tif 000014
【図１３】
2005038073.tif 000015