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