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