(57)【特許請求の範囲】
【請求項１】
定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングの方法であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、及び前記定量項目及び／又はカテゴリ項目で表現される前件属性および後件属性を含む利用者問合せとを受け取るステップと、
ｂ）前記前件属性を複数の索引ノードを含む索引木内に階層的に事前格納することによって前記前件属性と後件属性との間の関係を編成するステップであって、各索引ノードは実サポートと各利用者問合せの後件属性の信頼度とを表す第１及び第２の値を有する、前記編成するステップと
ｃ）前記索引木の全ての索引ノードを検索して、その前件属性の範囲が前記利用者問合せの前件属性範囲に対応し且つそれが最小信頼度の前記利用者定義値に少なくとも等しい信頼値と最小サポートの利用者定義値に少なくとも等しいサポート値を有するところの索引ノードを分離することによって、前記利用者問合せに応じて前記事前格納されたデータから応答を導出するステップと
を含む方法。
【請求項２】
前記応答が、１つまたはそれ以上の定量的連想規則、各規則に関連付けられた実信頼度値、各規則に関連付けられた実サポート値を含む、請求項１に記載の方法。
【請求項３】
利用者定義された関心レベルが前記受け取るステップにおいて提供され、前記応答が各規則に関連付けられた関心レベルを含み、それによって前記１つまたはそれ以上の定量的連想規則が、計算された関心レベルが前記利用者定義された関心レベルに少なくとも等しい規則のみで構成される、請求項１又は２のいずれかに記載の方法。
【請求項４】
前記関心レベルが第１および第２比率の計算値のうち最小のものと定義され、前記第１比率は実信頼度を予想信頼度で割ったものと定義され、第２比率は実サポートを予想サポートで割ったものと定義され、前記予想信頼度およびサポートは統計的独立性の推定に基づく計算値である、請求項３に記載の方法。
【請求項５】
前記前件属性がカテゴリ属性および定量属性を含む、請求項１ないし４のいずれか一項に記載の方法。
【請求項６】
前記定量属性が下限および上限から成る範囲によってさらに定義される、請求項５に記載の方法。
【請求項７】
前記導出するステップが、無意味なノードを削除し、他のノードを組み合わせることによって併合木を形成するステップを含み、無意味なノードとは、最小信頼度の前記利用者定義値に少なくとも等しい信頼度の対応する計算値を有しないノードである、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記併合木を単一の後件属性または複数の後件属性のいずれかのために作成することができる、請求項７に記載の方法。
【請求項９】
前記受け取るステップが、最小サポートの利用者定義値と、最小信頼度の利用者定義値と、利用者定義された関心値と、ならびに前件属性および後件属性を含む利用者問合せを含むデータとをコンピュータに入力することを含み、前記前件属性および後件属性が複数の定量属性およびカテゴリ属性をさらに含み、
前記編成するステップは、１つまたはそれ以上の次元で構成される索引木をメモリ内に構築するステップを含み、各次元は前記前件属性に含まれる利用者供給定量属性の１つによって定義され、前記索引木は複数の索引ノードを含み、該索引ノードは複数のデータ・レコードを含み、
前記導出するステップは、前記索引木から非併合規則木をメモリ内に構築し及び前記非併合規則木から併合規則木をメモリ内に構築するステップと、前記利用者問合せを満足する索引ノードであって、そのサポートが少なくとも前記最小サポートに等しくかつその信頼度が前記最小信頼度に少なくとも等しいところの索引ノードから、１つまたはそれ以上の定量的連想規則を生成するステップとを含み、
前記方法は、前記生成ステップからの前記定量的連想規則と、生成された各々の定量的連想規則に関連付けられた実信頼度の値と、生成された各々の定量的連想規則に関連付けられたサポートの値と、生成された各々の定量的連想規則に関連付けられた関心レベルの値とを含む出力データを利用者に表示するステップとを含む、
請求項１に記載の方法。
【請求項１０】
定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングの方法であって、
ａ）最小サポートの利用者定義値と、最小信頼度の利用者定義値と、利用者定義された関心レベルと、並びに前件属性および後件属性を含む利用者問合せとを受け取るステップであって、前記前件属性および後件属性は複数の定量属性及びカテゴリ属性をさらに含む、前記受け取るステップと、
ｂ）１つまたはそれ以上の次元で構成される索引木をメモリ内に構築するステップであって、各次元が定量属性の一つによって定義され、前記索引木は複数の索引ノードを含み、該索引ノードは複数のデータ・レコードを含む、前記構築するステップと、
ｃ）前記索引木から非併合規則木をメモリ内に構築するステップと、
ｄ）前記非併合規則木から平衡規則木をメモリ内に構築するステップと、
ｅ）前記利用者問合せを満足する索引ノードであって、そのサポートが少なくとも前記最小サポートに等しくかつその信頼度が前記最小信頼度に少なくとも等しいところの索引ノードから、一つまたはそれ以上の定量的連想規則を生成するステップと、
ｆ）前記生成ステップからの前記定量的連想規則と、生成された各々の定量的連想規則に関連付けられた実信頼度の値と、生成された各々の定量的連想規則に関連付けられたサポートの値と、生成された各々の定量的連想規則に関連付けられた関心レベルの値とを含む出力データを利用者に表示するステップと
を含む方法。
【請求項１１】
前記利用者問合せを対話的に修正して前記連想規則をさらに定義するように、１つまたはそれ以上の定量的連想規則を生成するステップを繰り返す、請求項９又は１０のいずれかに記載の方法。
【請求項１２】
請求項９又は１０のいずれかに記載の索引木をメモリ内に構築するステップが、
１つまたはそれ以上の次元の２分索引木を構築するステップであって、各次元が前記利用者供給定量前件属性の１つによって定義される、前記２分索引木を構築するステップと、
前記サポート・レベルおよび信頼度レベルを各索引ノードに格納するステップと
を含む、請求項９〜１１のいずれか一項に記載の方法。
【請求項１３】
請求項９又は１０のいずれかに記載の前記非併合規則木を構築するステップが、
前記索引木の各ノードを探索するステップと、
利用者指定後件属性を満足し且つ最小信頼度の前記利用者定義値に少なくとも等しい信頼度を有するところの規則と、最小サポートの前記利用者定義値に少なくとも等しいサポート値とを有するノードを選択するステップと
を含む、請求項９〜１２のいずれか一項に記載の方法。
【請求項１４】
利用者指定後件属性を満たす規則を含むノードを選択する前記ステップが、
ポインタを構築するステップと、
前記ポインタを前記索引木のルート・ノードに設定するステップと、
前記ポインタに関連付けられた前記ノードをリストに追加するステップと、
前件属性が前記利用者指定前件属性のパラメータ内に完全に含まれ且つ最小サポート値が前記利用者定義最小サポートに少なくとも等しいところの前記ポインタによって指定されたノードの全ての子をリストに追加するステップと、
前記ポインタによって指定されたノードに格納されたデータ・レコードが利用者指定後件属性に少なくとも等しく且つ前記利用者定義最小信頼度に少なくとも等しい信頼度を有しているかどうかを決定するステップと、
前記後件属性に関連付けられた定量的連想規則を生成するステップと、
直上の生成するステップの条件が満たされない場合、前記リストから前記ノードを削除するステップと、
前記リストが空かどうかを決定するステップと、
前記リストが空の場合には終了するステップと、そうでない場合には前記ポインタを前記索引木の次のノードに設定し、前記ポインタに関連付けられたノードをリストに追加するステップからそれ以降の上記ステップを繰り返すステップと
を含む、請求項１３に記載の方法。
【請求項１５】
請求項９又は１０のいずれかに記載の前記併合規則木を構築するステップが、
ａ）非併合規則木の各ノードをポスト順に走査することと、
ｂ）ｉ）各前記利用者定義後件属性値が前記ノードに格納された後件属性値より大きいかどうかを決定し、
ｉｉ）（ｉ）の条件が満たされた場合、前記併合規則木に前記ノードを保存し、
ｉｉｉ）（ｉ）の条件が満たされず且つ前記ノードに関連付けられた子ノードが無い場合、前記併合規則木から前記ノードを削除し、
ｉｖ）（ｉ）の条件が満たされず且つ前記ノードに１つの子ノードがある場合、前記併合規則木から前記ノードを削除し、先祖ノードと前記削除されたノードの子ノードとを直接関連付け、
ｖ）（ｉ）の条件が満たされない場合、前記後件属性の範囲を調整することによって、
走査された各ノードを非併合規則木に含めるか除外するかを評価するステップと
を含み、
全てのノードがポスト順に走査し終わるまで前記評価ステップを繰り返す、請求項９〜１４のいずれか一項に記載の方法。
【請求項１６】
定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する多数のレコードを有する大規模データベースのオンライン・マイニングのための装置であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、及び前記定量項目及び／又はカテゴリ項目で表現される前件属性および後件属性を含む利用者問合せとを受け取るための手段と、
ｂ）前記前件属性を複数の索引ノードを含む索引木内に階層的に事前格納することによって前記前件属性と後件属性との間の関係を編成する手段であって、各索引ノードは実サポートと各利用者問合せの後件属性の信頼度とを表す第１及び第２の値を有する、前記編成する手段と
ｃ）前記索引木の全ての索引ノードを検索して、その前件属性の範囲が前記利用者問合せの前件属性範囲に対応し且つそれが最小信頼度の前記利用者定義値に少なくとも等しい信頼値と最小サポートの利用者定義値に少なくとも等しいサポート値を有するところの索引ノードを分離することによって、前記利用者問合せに応じて前記事前格納されたデータから応答を導出する手段と
を含む装置。
【請求項１７】
定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングの方法であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、並びに前件属性および後件属性を含む利用者問合せとを受け取るステップと、
ｂ）前記前件属性と後件属性との間の関係を編成するステップであって、前記編成するステップは前記前件属性を階層的に索引木に分割することを含み、前記索引木は複数の索引ノードを含み、前記分割は、ａ）前記索引木の各索引ノードに実サポートを含む第１の値を格納し、ｂ）各利用者問い合わせの後件属性の信頼度を表す第２の値を格納する、前記編成するステップと、
ｃ）前記前件属性と前記後件属性との間の関係を定義するデータを事前格納するステップと、
ｄ）前記利用者問合せに応じて前記事前格納されたデータから応答を導出するステップと
を含む方法。
【請求項１８】
定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングのための装置であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、並びに前件属性および後件属性を含む利用者問合せとを受け取る手段と、
ｂ）前記前件属性と後件属性との間の関係を編成する手段であって、前記編成するステップは前記前件属性を階層的に索引木に分割することを含み、前記索引木は複数の索引ノードを含み、前記分割は、ａ）前記索引木の各索引ノードに実サポートを含む第１の値を格納し、ｂ）各利用者問い合わせの後件属性の信頼度を表す第２の値を格納する、前記編成する手段と、
ｃ）前記前件属性と前記後件属性との間の関係を定義するデータを事前格納する手段と、
ｄ）前記利用者問合せに応じて前記事前格納されたデータから応答を導出する手段と
を含む装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般に、大規模データベースにおけるデータ従属性のオンライン探索に関する。
【０００２】
【従来の技術】
データベースにおける知識発見とも呼ばれるデータ・マイニングは、データベース研究の新しい領域と認識されてきた。電子形式で格納されるデータの量は、過去２０年の間に劇的に増加した。ＰＯＳ装置またはリモート・センシング装置などの電子データ収集装置の使用の増加が、利用可能なデータのこの急増の一因になった。大量の計算能力資源およびデータ記憶資源の利用可能性がどんどん低下するコストで利用できるようになっているので、データの格納はますます簡単に、かつ産業界にとってますます魅力的になってきている。
【０００３】
データの蓄積に高い関心が集まるにつれて、この貴重な資源をどのように利用できるかに重点を置く補完的な必要性が生じてきた。業界は、格納されたデータを利用できる意思決定者が貴重な洞察を得ることができることを認識してきた。バーコード会社のデータまたはカタログ販売会社の販売データを使用することによって、顧客購買動向に関する貴重な情報を得ることができる。導き出された情報は、例えば小売業者が、なかんずく、どの品目をスーパーマーケットの棚に載せるべきかを決定する際に、あるいは目標をしっかり定めたマーケティング・プログラムを設計するために使用することができよう。適切な分析技術を利用して、データから多数の有意義な洞察を発掘することができる。最も一般的な意味で、データ・マイニングは、データの集合におけるパターンおよび規則性を発見するためのデータ分析およびソフトウェア技術の使用に関係する。データ・マイニングの目的は、データ内の識別可能なパターンおよび傾向を選別すること、およびこれらのパターンから連想規則を推論することである。
【０００４】
データ・マイニング技術は、大量のデータに対する集中的な計算によって特徴付けられる。大規模データベースとは、１００万以上のレコードから成るものと定義できる。一般的な適用例では、最終利用者は、「コーラを買う客の７５％はコーン・チップも買う」などの連想規則を試験する。ここで７５％は規則の信頼度係数を指す。規則のサポートが、コーラおよびコーン・チップの両方を含むトランザクションのこの百分率である。
【０００５】
【発明が解決しようとする課題】
今まで、従来技術はオンライン・マイニングの問題を取り扱ってきておらず、その代わりにアイテムセット手法（itemset approach）に重点を置いてきた。アイテムセット手法の重大な欠点は、利用者が様々な値のサポートおよび信頼度で連想規則についてデータベースを試験するときに、およそ数ギガバイトになることもあるデータベースに対し、マルチパスを行わなければならないことである。超大規模データベースの場合、これはかなりの量のＩ／Ｏを伴うことがあり、場合によっては、オンライン問合せに対する容認できない応答時間をもたらすことがある。所定のレベルのサポートおよび信頼度を満たす規則が幾つあるかを先験的に推測することは難しいので、利用者はデータベースに多数の問合せを行わなければならない。一般に人は、少数の規則に関心を持つだけである。これは問題をますます困難にする。というのは、利用者が、規則を引き出すために適切なレベルの最小サポートおよび最小信頼度を見つけるために、何回も問合せを実行する必要があるからである。言い換えると、連想規則を引き出す問題は、有用な事業情報をトランザクション・データベースから集めることができるようになる前に、問合せを繰り返すことによって、かなりの手動パラメータ調整を行うことが必要になる。したがって、今まで記載されたマイニングの処理方法は、大量のディスクＩ／Ｏまたは計算が容認できない応答時間につながるので結果的に、繰返しオンライン問合せには適さない。データ・マイニングの能力をインターネットに拡張するには、バッチ指向の方法であるアイテムセット手法ではなく、動的オンライン方法が必要である。
【０００６】
【課題を解決するための手段】
したがって、本発明は、定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングの方法であって、
ａ）最小信頼度の利用者定義値、最小サポートの利用者定義値、関心レベルの利用者定義値、および前件属性と後件属性とを含む利用者問合せを受け取るステップと、
ｂ）前記前件属性と前記後件属性との間の関係を編成するステップと、
ｃ）前記前件属性と前記後件属性に関連するデータとの間の関係を定義するデータを事前格納するステップと、
ｄ）前記利用者問合せに応じて前記事前格納されたデータから応答を導出するステップと
を含む方法を提供する。
【０００７】
好適な実施形態では、前記応答は１つまたはそれ以上の定量的連想規則、各規則に関連付けられる実信頼度値、各規則に関連付けられる実サポート値、および各規則に関連付けられる関心レベルを含み、前記１つまたはそれ以上の定量的連想規則は、関心を引く規則のみで構成される（例えば、それらの関心レベルの計算値は、前記関心レベルの利用者定義値に少なくとも等しい）。
【０００８】
関心レベルの便利かつ効果的な定義は（例えば）第１および第２比率計算値のうち最小のものであり、ここで前記第１比率は実信頼度を予想信頼度で割ったものと定義され、第２比率は実サポートを予想サポートで割ったものと定義され、ここで前記予想信頼度およびサポートは統計的独立性の推定に基づく計算値である。
【０００９】
好適な実施形態では、前記前件属性はカテゴリ的属性および定量属性を含み、定量属性は下限および上限で構成される範囲によって定義される。
【００１０】
好ましくは、前記編成するステップは、前記前件属性を階層的に索引木に分割することを含み、ここで前記索引木は多数の索引ノードを含み、前記分割は、
ａ）前記索引木の各索引ノードに実サポートを表す第１の値を格納するステップと、
ｂ）前記索引木の各索引ノードに、各利用者問合せの後件属性の発生の頻度を表す第２の値を格納するステップと
によって行われる。
【００１１】
そのような実施形態では、前記導出ステップは、
ｉ）前記索引木の全ての索引ノードを探索して、前件属性の範囲が前記利用者問合せの前件属性範囲に対応するノードを分離し、
ｉｉ）ステップｉで突き止められたノードから、後件属性が前記最小信頼度の利用者定義値に少なくとも等しいノードを選択し、
ｉｉｉ）ステップｉｉで突き止められたノードから、併合木を作成する
ことによって、効果的に実現することができる。
【００１２】
好ましくは、前記作成ステップはさらに、無意味なノードを削除し、かつ他のノードを組み合わせて前記併合木を形成することを含み、ここで無意味なノードとは、最小信頼度の前記利用者定義値に少なくとも等しい、対応する信頼度の計算値を有しないノードである。併合木は、単一または複数の後件属性のどちらにも作成することができる。
【００１３】
１つの好適な実施形態では、前記受取りステップは、最小サポートの利用者定義値、最小信頼度の利用者定義値、関心の利用者定義値、ならびに前件条件および後件条件を含む利用者問合せを含むデータをコンピュータに入力することを含み、前記前件条件および後件条件はさらに複数の定量属性およびカテゴリ属性を含み、
前記編成するステップおよび事前格納ステップは、メモリ内に１つまたはそれ以上の次元で構成される索引木を構築すること、ならびにメモリ内に前記索引木から非併合規則木を、かつ前記非併合規則木から併合規則木を構築することを含み、ここで各次元は前記前件条件に含まれる利用者供給定量属性の１つによって定義され、前記索引木は複数の索引ノードから成り、前記索引ノードは複数のデータ・レコードから成り、
前記導出ステップは、
前記利用者問合せを満足する索引ノードであって、そのサポートが少なくとも前記最小サポートに等しく、かつその信頼度が少なくとも前記最小信頼度に等しい索引ノードから、１つまたはそれ以上の定量的連想規則を生成すること、ならびに、
前記生成ステップからの前記定量的連想規則と、生成された各々の定量的連想規則に関連付けられた実信頼度の値と、生成された各々の定量的連想規則に関連付けられたサポートの値と、生成された各々の定量的連想規則に関連付けられた関心レベルの値とから成る出力データを利用者に表示すること
を含む。
【００１４】
前記利用者問合せを対話的に修正して前記連想規則をさらに定義するように、１つ以上の定量的連想規則を生成するステップを繰り返すことができる。
【００１５】
好ましくは、索引木を構築するステップは、１つまたはそれ以上の次元の２分索引木を構築するステップと、前記サポート・レベルおよび信頼度レベルを各索引ノードに格納するステップとを含み、ここで各次元は前記利用者供給定量前件属性の１つによって定義される。
【００１６】
また、非併合規則木を構築するステップは、前記索引木の各ノードを探索するステップと、利用者指定後件条件を満足する規則を含み、かつ最低信頼度の前記利用者定義値に少なくとも等しい信頼度および最低サポートの前記利用者定義値に少なくとも等しいサポートの値を有するノードを選択するステップとを含むことが好ましい。この後者の選択ステップは、
ポインタを構築するステップと、
前記ポインタを前記索引木のルート・ノードに設定するステップと、
前記ポインタに関連付けられる前記ノードをリストに追加するステップと、
前件属性が前記利用者指定前件属性のパラメータ内に完全に含まれ、最小サポート値が前記利用者定義最小サポートに少なくとも等しい、前記ポインタによって指定されたノードの全ての子をリストに追加するステップと、
前記ポインタによって指定されたノードに格納されたデータ・レコードが利用者指定後件条件に少なくとも等しく、かつ前記利用者定義最小信頼度に少なくとも等しい信頼度を有しているかどうかを決定するステップと、
前記後件条件に関連付けられる定量的連想規則を生成するステップと、
前ステップの条件が満たされない場合、前記リストから前記ノードを削除するステップと、
前記リストが空かどうかを決定するステップと、
前記リストが空の場合には終了し、そうでない場合には前記ポインタを前記索引木の次のノードに設定し、前記ポインタに関連付けられるノードをリストに追加するステップからそれ以降の上記ステップを繰り返すステップと
によって実行することができる。
【００１７】
さらに好ましくは、併合規則木を構築するステップは、
ａ）非併合規則木の各ノードをポスト順に走査することと、
ｂ）ｉ）各前記利用者定義後件属性値が前記ノードに格納された後件属性値より大きいかどうかを決定し、
ｉｉ）（ｉ）の条件が満たされた場合、前記併合規則木に前記ノードを保存し、
ｉｉｉ）（ｉ）の条件が満たされず、かつ前記ノードに関連付けられる子ノードが無い場合、前記併合規則木から前記ノードを削除し、
ｉｖ）（ｉ）の条件が満たされず、前記ノードに１つの子ノードがある場合、前記併合規則木から前記ノードを削除し、先祖ノードと前記削除されたノードの子ノードとを直接関連付け、
ｖ）（ｉ）の条件が満たされない場合、前記後件属性の範囲を調整する
ことによって、
走査された各ノードを非併合規則木に含めるか除外するかを評価すること
を含み、
全てのノードがポスト順に走査し終わるまで、前記評価ステップを繰り返す。
【００１８】
本発明はさらに、定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する多数のレコードを有する大規模データベースのオンライン・マイニングのための装置であって、
ａ）最小信頼度の利用者定義値、最小サポートの利用者定義値、関心レベルの利用者定義値、および前件属性と後件属性とを含む利用者問合せを受け取るための手段と、
ｂ）前記前件属性と後件属性との間の関係を編成するための手段と、
ｃ）前記前件属性と前記後件属性に関連するデータとの間の関係を定義するデータを事前格納するためのメモリと、
ｄ）前記利用者問合せに応じて前記事前格納されたデータから応答を導出するための手段と
を含む装置を提供する。
【００１９】
別の側面から見ると、本発明はまた、定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングのコンピュータ実行プロセスであって、
最小サポートの利用者定義値、最小信頼度の利用者定義値、関心の利用者定義値、ならびに前件条件および後件条件を含む利用者問合せを含むデータをコンピュータに入力するステップであって、前記前件条件および後件条件がさらに複数の定量属性およびカテゴリ属性を含む前記入力ステップと、
メモリ内に１つまたはそれ以上の次元で構成される索引木を構築するステップであって、前記各次元が前記前件条件に含まれる利用者供給定量属性の１つによって定義され、前記索引木が複数の索引ノードから成り、前記索引ノードがさらに複数のデータ・レコードから成る前記構築ステップと、
複数の索引ノードから成る前記索引木から非併合規則木をメモリ内に構築するステップであって、前記索引ノードがさらに複数のデータ・レコードから成る前記構築ステップと、
複数の索引ノードから成る前記非併合規則木から併合規則木をメモリ内に構築するステップであって、前記索引ノードがさらに複数のデータ・レコードから成る前記構築ステップと、
前記利用者問合せを満足し、かつそのサポートが少なくとも前記最小サポートに等しく、その信頼度が少なくとも前記最小信頼度に等しい索引ノードから、１つまたはそれ以上の定量的連想規則を生成するステップと、
前記生成ステップからの前記定量的連想規則と、生成された各々の定量的連想規則に関連付けられた実信頼度の値と、生成された各々の定量的連想規則に関連付けられたサポートの値と、生成された各々の定量的連想規則に関連付けられた関心レベルの値とから成る利用者出力データを表示するステップと
を含む前記コンピュータ実行プロセスをも提供する。
【００２０】
好ましくは、非併合規則木を構築するステップは、索引木の各ノードを探索することと、
ｉ）ポインタを構築するステップと、
ｉｉ）前記ポインタを前記索引木のルート・ノードに設定するステップと、
ｉｉｉ）前記ポインタに関連付けられた前記ノードをリストに追加するステップと、
ｉｖ）前件属性が前記利用者指定前件属性のパラメータ内に完全に含まれ且つ最小サポート値が前記利用者定義最小サポートに少なくとも等しいところの前記ポインタによって指定されたノードの全ての子をリストに追加するステップと、
ｖ）前記ポインタによって指定されたノードに格納されたデータ・レコードが利用者指定後件条件に少なくとも等しく且つ前記ポインタによって指定されたノードの前記利用者定義最小信頼度に少なくとも等しい信頼度を有しているかどうかを決定するステップと、
ｖｉ）前記後件条件に関連付けられる定量的連想規則を生成するステップと、
ｖｉｉ）直上の生成するステップの条件が満たされない場合、前記リストから前記ノードを削除するステップと、
ｖｉｉｉ）前記リストが空かどうかを決定するステップと、
ｉｘ）前記リストが空の場合には終了するステップと、
ｘ）ステップｉｘの条件が満たされない場合には、前記ポインタを前記索引木の次のノードに設定するステップと、
ｘｉ）ステップｉｘが満たされない場合には、ステップｉｉｉ〜ｘを繰り返すステップとによって適切なノードを選択することを含む。
【００２１】
好ましくは、併合規則木を構築するステップは、
ａ）非併合規則木の各ノードをポスト順に走査するステップと、
ｂ）ｉ）各々の前記利用者定義後件属性値が前記ノードに格納された後件属性値より大きいかどうかを決定するステップと、
ｉｉ）ステップｉの条件が満たされた場合、前記併合規則木に前記ノードを保存するステップと、
ｉｉｉ）ステップｉの条件が満たされず、かつ前記ノードに関連付けられる子ノードが無い場合、前記併合規則木から前記ノードを削除するステップと、
ｉｖ）ステップｉの条件が満たされず、かつ前記ノードに１つの子ノードがある場合、前記併合規則木から前記ノードを削除するステップと、
ｖ）ステップｉの条件が満たされない場合、前記後件属性の範囲を調整するステップと、
ｖｉ）ステップｉｖの条件が満たされる場合、先祖ノードと前記削除されたノードの子ノードとを直接関連付けるステップと、
ｖｉｉ）全てのノードがポスト順に走査されるまでステップｉ〜ｖｉを繰り返すステップとをさらに含む、走査された各ノードを非併合規則木に含めるか除外するかを評価するステップと
を含む。
【００２２】
ここに記載する計算上効率的な手法は、データベースのオンライン問合せにより、利用者が供給するレベルのサポートおよび信頼度を予測子として利用して、連想規則の強度を評価し、かつ定量的連想規則のオンライン・マイニングの効率的な実行のため、新しい定量的連想規則を発見することを可能にする。連想規則は一般に、その２つの構成部分つまり前件と後件との間に何らかの相関関係が存在することを示唆する条件文と定義することができる。定量的連想規則における前件および後件は両方とも、利用者が指定する定量属性とカテゴリ属性の何らかの組合せから構成される。規則の提案と共に、利用者は、利用者にとって関心のある信頼度およびサポート・レベルならびに関心レベルと呼ばれる値を表す３つの追加入力を提供する。これらの入力は、利用者（利用者問合せ）によって提案される規則の強度の指標を、言い換えると、利用者問合せによって定義される前件と後件との間の示唆される相関関係の強度を提供する。
【００２３】
この手法を実行するために、オンライン規則生成ステップの前に、多次元索引構造を形成するように前件属性を利用してデータを分割することによって、生データを前処理するための方法を記載する。データを効果的に前処理して索引構造にすることによって、データは繰返しオンライン問合せにほぼ瞬時の応答時間で応答するのに適した形になる。索引構造がひとたび形成されると、データベースで多重パスを行う必要が無くなる。索引構造は、従前の技術に比べて格段の性能上の利点をもたらす。索引構造（前処理されたデータ）は、複雑さが出力のサイズに比例するグラフ理論探索アルゴリズムを適用することによってオンライン処理を行うことができるように、格納される。この結果、応答時間に関してはほとんど瞬時であるオンライン・アルゴリズムが得られ、Ｉ／Ｏまたは計算の過剰な量が最小化される。
【００２４】
【発明の実施の形態】
従来のデータベース問合せは、「ロングアイランド地域の１９９５年１月のオレンジ・ジュースの売上げはどれだけあったか」などの簡単な質問を含む。対照的に、データ・マイニングはデータにおける認識可能なパターンおよび傾向を見つけ出そうとし、これらのパターンから規則を推測するものである。これらの規則を基にユーザは関連事業または科学分野における決定を支持、再検討、考察することが可能である。例えば、大量の商品があるスーパーマーケットについて考察する。運営に関連する一般的な事業決定は、利益を最大にする等のために何を特売するか、クーポン券をどのように計画するか、および商品をどのように棚に配置するかに関する。過去のトランザクション・データの分析は、そのような決定の質を改善するために一般に使用される手法である。最新の技術は、トランザクションごとに購入される品目を格納するいわゆるバスケット・データを格納することを可能にした。組織は、大量のそうしたデータを収集する。問題は、大量のバスケット・データ型トランザクションからある最小指定信頼度を有する品目の集合間の連想規則を「発掘」することである。各トランザクションが１組の品目である場合、１組のトランザクションが与えられると仮定すると、連想規則はＸ＝＞Ｙの形の式であり、ここでＸおよびＹは品目の組である。連想規則の一例は、「ビールを含むトランザクションの３０％はおむつをも含み、全トランザクションの２％はこれらの品目を両方とも含む」というものである。ここで、３０％は規則の信頼度と呼ばれ、２％は規則のサポートと呼ばれる。
【００２５】
そのような連想規則の別の例として、パンとバターを購入する顧客トランザクションの９０％は牛乳も購入するという文がある。この規則の前件Ｘはパンとバターで構成され、後件Ｙは牛乳だけで構成される。９０％はこの規則の信頼係数である。例えば、前件に「ベーグル（ドーナツ型の堅ロールパン）」を有する全ての規則を見つけることが望ましいかもしれず、これは、もし店がベーグルの販売を中止すれば、どんな製品（後件）に影響が出るかを判断するのに役立つであろう。
【００２６】
１組の生トランザクションＤが与えられたと仮定して、連想規則を発掘する問題は、利用者が指定する最小サポート（minsupport s）および最小信頼度（minconfidence c）より大きいサポートおよび信頼度を有する全ての規則を見つけることである。一般に、規則Ｘ＝＞Ｙのサポートは、ＸおよびＹの両方の品目集合（itemset）を含む顧客トランザクションまたは汎用データベースにおける組の百分率である。より形式的数学用語では、Ｄにおけるトランザクションのｓ％がＸとＹの和集合すなわちＸＶＹを含むならば、規則ｘ＝＞Ｙはトランザクション集合Ｄにおけるサポートｓを有する。規則Ｘ＝＞Ｙの信頼度は、Ｘを含み、Ｙをも含むトランザクションの百分率として定義される。より形式的には、Ｘを含むＤにおけるトランザクションのｃ％がＹをも含むならば、規則Ｘ＝＞Ｙはトランザクション集合Ｄにおける信頼度Ｃを有する。したがって、規則が９０％の信頼度を有する場合、それはＸを含むトランザクションの９０％がＹをも含むことを意味する。
【００２７】
前述の通り、連想規則は形式Ｘ＝＞Ｙの式である。例えば、品目集合ＸおよびＹをそれぞれ、
Ｘ＝［牛乳＆チーズ＆バター］
Ｙ＝［卵＆ハム］
と定義する。
【００２８】
規則は、次のように解釈することができる。
規則：Ｘ＝＞Ｙとは、トランザクションに牛乳、チーズ、およびバターが発生した場合、定義されたサポートおよび信頼度レベル内で卵とハムがその同じトランザクションに現れる頻度がどれだけかを暗示する。
【００２９】
規則のサポートおよび信頼度は集合的に、規則の強度を定義する。利用者が、その強度を試験するために、そのようなシステムに規則を提起することができるいくつかの方法がある。そのようなシステムがサポートできる種類のオンライン問合せの包括的ではないが代表的なリストとして、次のようなものがある。
（１）特定レベルのminsupportおよびminconfidenceより上の全ての連想規則を見つける。
（２）特定レベルのminsupportおよびminconfidenceで、前件に品目の集合Ｘを有する全ての連想規則を見つける。
（３）特定レベルのminsupportおよびminconfidenceで、後件に品目の集合Ｙを有する全ての連想規則を見つける。
（４）特定レベルのminsupportおよびminconfidenceで、前件または後件のいずれかに、もしくは前件と後件の間に分配して、品目の集合Ｙを有する全ての連想規則を見つける。
（５）上記事例（１）、（２）、（３）、（４）のいずれかの連想規則／品目集合の数を見つける。
（６）どのレベルのminsupportで、品目の集合Ｚを含む品目集合の数がちょうどｋ個になるか。
【００３０】
この方法は、一般的連想規則の方法を、様々な定量属性およびカテゴリ属性によって定義される１組の未処理（raw）トランザクションＤで構成される大規模データベースから定量規則を見つけることに特定化する。
【００３１】
例えば、一般的マーケティング調査用の典型的な定量／カテゴリ・データベースは、一連のレコードで構成され、各レコードは次のように消費者の特徴および好みの何らかの組合せを反映する。
レコード（１）＝年齢＝２１、性別＝男、住宅所有者＝いいえ
レコード（２）＝年齢＝４３、性別＝男、住宅所有者＝はい
レコード（３）＝年齢＝５５、性別＝女、住宅所有者＝いいえ
【００３２】
一般に、定量的連想規則は、次のような形式の条件である。
一般規則：
Ｘ１［ｌ１．．ｕ１］，Ｘ２［ｌ２．．ｕ２］．．．Ｘｋ［ｌｋ．．ｕｋ］Ｙ１＝ｃ１，Ｙ２＝ｃ２．．Ｙｒ＝ｃｒ＝＞Ｚ１＝ｚ１，Ｚ２＝ｚ２
ここでＸ１、Ｘ２、．．Ｘｋは定量前件属性に対応し、Ｙ１、Ｙ２、．．ＹｋおよびＣはカテゴリ前件属性に対応する。ここで［ｌ１．．ｕ１］、［ｌ２．．ｕ２］、．．．［ｌｋ．．ｕｋ］は様々な定量属性の範囲に対応する。Ｚ１およびＺ２は複数の後件条件に対応する。
【００３３】
この方法は、利用者が、前件／後件の対の形で、提案規則さもなくば利用者問合せと呼ばれるものと共に、３つの入力を供給する必要がある。提案規則に加えて、利用者は提案規則（利用者問合せ）の強度を試験するために、最小要求信頼度（minconfidence=c）および最小要求サポート（minsupport＝ｓ）の値を供給する。
【００３４】
最小信頼度および最小サポートは両方とも、一般連想規則の発見の場合と同様に、定量的連想規則の発見に関連する。典型的な利用者入力の一例を示す。
【００３５】
【実施例】
実施例Ａ：典型的利用者入力
１．利用者は試験すべき提案規則（問合せ）を供給する。
【数１】
0003575602.tif 000002
２．利用者は、Minconfidence cと呼ばれる提案規則の信頼度値を供給する。
Minconfidence = 50%
３．利用者は、Minsupport sと呼ばれる提案規則のサポート値を供給する。
Minsupport = 10%
【００３６】
図１は、この方法のアーキテクチャの全体的略図である。前処理されたデータにネットワーク３５を介してアクセスできる複数のクライアント４０があることを想定している。前処理されたデータはサーバ５に常駐する。サーバ端に、前処理されたデータ２０と共にキャッシュ２５がある。前処理およびオンライン処理はＣＰＵ１０で行われる。さらに、データをディスクに格納する場合に備えて、ディスク１５が存在する。
【００３７】
この方法は、前処理段階の後にオンライン処理段階が続く２段階を含む。図２は、前処理段階の全体的概要およびアルゴリズムのオンライン処理（規則生成ステップ）を示す。前処理段階は、２分索引木構造の構築を含む。図２ａのステップ７５、および図４の関連詳細図を参照されたい。索引木構造は、当技術分野でよく知られた空間データ構造であり、多次元データの索引付けの手段として使用される。先行技術の関連研究は、ガットマン（Guttman, A.）の「A dynamic Index Structure for Spatial Searching. Proceedings of the ACM SIGMOD Conference」に見ることができる。本発明の方法では、オンライン問合せを実行するために、この索引木構造の変形を採用する。前件属性は、多次元索引構造を形成するようにデータを分割するために利用する。索引構造は２レベル構造であり、上位レベルのノードは多くとも２つの後続ノードに関連付けられ、下位レベルのノードは３つ以上の後続ノードに関連付けられる。索引構造の構築は、効果的なオンライン・データ・マイニングの実行のために非常に重要である。鍵となる利点は、利用者問合せに応答するために必要なディスクＩ／Ｏの量を最小にすることに存在する。
【００３８】
コンピュータ・メモリに格納される索引構造の図形的類似物を、索引木の形で図５に示す。索引木は、多次元データに索引を付けるために使用される、よく知られた空間データ構造である。別個の索引構造が、オンライン問合せで利用者によって指定された特定の定量属性によって定義される各次元について、コンピュータ・メモリ内に形成される。図５は、前件条件「年齢」およびそれに関連付けられる後件条件「初回買物客（FirstTimeBuyer）」を表す特定例の索引木構造である。索引木の概念をさらに明瞭にするために、図５は、下の例の「年齢」次元を表すことができた。
【００３９】
実施例Ｂ：サンプル利用者問合せ
【数２】
0003575602.tif 000003
【００４０】
一般に、前件条件および後件条件を含む数量または定量属性とカテゴリ属性の組合せに関する制約は無い。
【００４１】
図５で、索引木構造のルート・ノードは、利用者が指定する定量属性である年齢［０〜１００］を定義する。木の各後続ノードも定量属性である年齢を表し、木構造の最上部から最下部に向かって範囲がだんだん狭くなる。例えば、年齢［０〜１００］のルート・ノードの２分後続ノードは年齢［０〜４５］および年齢［４５〜１００］である。この方法は、索引木の各ノードに、対象となる信頼度およびサポート・レベルを表す２片のデータを格納する。例えば、図５を参照すると、
１．信頼度レベル＝５０％
２．サポート・レベル＝生データベースに入力されるデータの関数
から成る２片のデータがルート・ノードに格納されている。
【００４２】
これらは、ルート・ノードでの利用者問合せ、すなわち（前件／後件の対）、
年齢［０〜１００］  =>  初回買物客
の信頼度およびサポートを定義する。
【００４３】
図４は、図２に要素７５として示すアルゴリズムの前処理段階の詳細流れ図である。この段階のプロセス・ステップは、２分索引木構造を生成し、かつ構造の各ノードに後件属性のサポートおよび信頼度レベルを格納することを含み、その後に構造の下位レベルで圧縮アルゴリズムを使用して索引木が使用可能メモリに収まるのを確実にする。ステップ３００は前処理段階の入口点である。ステップ３１０は、２分化アルゴリズムを使用して２分索引木を生成するプロセス・ステップを実現するためのソフトウェアを表す。２分化ステップは、先行技術である、アクラウル（Aqqarwal C.C.）、ウルフ（Wolf J.）、ユー（Yu P.S.）、エプルマン（Epelman M.A.）の「The S-Tree: An efficient index tree for multidimensional index trees, Symposium of Spatial Databases, 1997」で考察されている。しかし、本発明の方法は、少なくとも１つの側面でこの先行技術とは異なる。ステップ３１５で、索引ノードの項目を編成する方法は、後件属性の各値のサポート・レベルおよび信頼度レベルの両方を構造の各ノードに格納するという点で、独自である。ステップ３２０は、ソフトウェア圧縮アルゴリズムを利用して、下位レベルの索引ノードを単一ノードに圧縮するプロセス・ステップを表す。
【００４４】
図６は、図３に要素１００として示す、索引木から非併合規則木を生成するために使用する主探索アルゴリズムの詳細流れ図である。このアルゴリズムは入力として、minconfidence cおよびminsupport sの利用者指定値ならびにQuerybox Qおよび１つまたはそれ以上の右辺項値Ｚ１＝ｚ１、Ｚ２＝ｚ２で構成される利用者問合せを必要とする。Queryboxは、利用者問合せの左辺または前件部を表す単なる記述項である。Queryboxの意味をさらに明瞭にするために、下の実施例Ｃで、この方法における入力としてオンライン利用者に何が要求されるかを説明する。
【００４５】
実施例Ｃ：典型的利用者入力
利用者は、次のものを指定する。
（１．）最小信頼度値［minconfidence, c］
（２．）最小サポート値［minsupport, s］
さらに、オンライン利用者は、項目３および４の（前件／後件）対の形で利用者問合せ（提案規則）を入力する必要がある。
（３．）Querybox, ”Q”［前件］
（４．）Ｚ１＝ｚ１、Ｚ２＝ｚ２等．．［後件］
【００４６】
項目３のQueryboxについては以下の実施例でさらに説明するが、一般に定量属性とカテゴリ属性の任意の組合せで構成することができる。項目４の後件属性は、１つまたはそれ以上のカテゴリ属性で構成することができる。
【００４７】
［実施例１］：この利用者指定問合せは、年齢と左利きの２つの次元を含む前件条件すなわちqueryboxと、単一のカテゴリ後件条件の喫煙者（a smoker）とで構成される。
【数３】
0003575602.tif 000004
【００４８】
［実施例２］：この利用者指定問合せは、身長と収入の２つの次元を含む前件条件すなわちqueryboxと、多重後件条件とで構成される。
【数４】
0003575602.tif 000005
【００４９】
［実施例３］：この利用者指定問合せは、１次元すなわち年齢を含む前件条件であるqueryboxと、単一の後件条件とで構成される。
【数５】
0003575602.tif 000006
【００５０】
上記の実施例Ｃは、利用者がこの方法の入力として供給する物を一般に説明している。下の実施例Ｄは、上記の実施例２の利用者問合せを使用して、典型的な入力／出力結果がどのように見えるかの代表的な例を提供する。
【００５１】
実施例Ｄ：典型的利用者入力
利用者は入力として次の物を指定する。
１．minconfidence = 0.50
２．minsupport = 0.4
３．querybox（前件条件）＝身長［５〜７］，収入［１０ｋ〜４０ｋ］
４．対象とする後件条件＝住宅所有者＝１，車所有者＝１
項目（３および４）から形成される利用者問合せ：
身長［５〜７］、収入［１０ｋ〜４０ｋ］==>住宅所有者，車所有者
結果的に得られる出力：生成される規則
身長［５．５〜６．２］、収入［１３ｋ〜２７．４ｋ］==>住宅所有者＝１、車所有者＝１
【００５２】
一般に、出力は規則を１つも生成しないか、１つの規則または複数の規則を生成することができると考えられる。上の例では単一の規則が生成された。生成された規則は、利用者が指定したそれぞれ０．５および０．４の信頼度およびサポート・レベルで利用者問合せ（前件／後件の対）を満足すると言われる。
【００５３】
図６によって定義される、索引木から非併合規則木を生成するためのアルゴリズムは、索引木の全てのノードを１つずつ探索することによって進められる。ステップ４００は、主探索アルゴリズムへの入口点である。ステップ４１０は、索引木のルート・ノードを指すようにCurrentNodeポインタを設定するプロセス・ステップを表す。CurrentNodeポインタは常に、アルゴリズムが現在探索している索引木の特定のノードを指す。ステップ４２０は、探索アルゴリズムによって走査される資格のあるノードと考えられるノードの集合としてＬＩＳＴを定義する。ＬＩＳＴは、ステップ４２０でルート・ノードだけを含むように初期化される。ステップ４３０は、Currentnodeによって指定されたノードの子ノードのうち、Querybox Qと相交わり、かつ利用者指定入力値minsupport sに少なくとも等しいサポートを有する全ての子ノードをＬＩＳＴに追加するプロセス・ステップを表す。子ノードは、子ノードに関連付けられる前件条件の全てがQueryboxによって定義された前件条件内に完全に含まれるときに、Querybox Qと相交わると言われる。ステップ４４０は、CurrentNodeに含まれる個々のデータ・レコードが後件条件であるＺ１＝ｚ１およびＺ２＝ｚ２を少なくともｃパーセントの時間満たすかどうかを決定する決定ステップである。ステップ４４０の条件が満たされた場合には、アルゴリズムはステップ４４５に進む。ステップ４４５は、右辺に属性の集合に対応する規則、つまり後件条件を生成する。ステップ４４０および４４５の後にステップ４５０が続き、これは、Currentnodeによって現在指定されているノードをＬＩＳＴから削除し、かつCurrentnodeポインタをＬＩＳＴに含まれる次のノードに設定するプロセス・ステップを表す。ステップ４６０は、ＬＩＳＴが空であるかどうかを決定し、条件が満たされるときは、アルゴリズムを終了する。ステップ４７０を参照されたい。そうでなければ、アルゴリズムはステップ４３０に戻り、CurrentNodeポインタによって現在指定されているノードに対してステップを繰り返す。アルゴリズムの終了後、利用者指定の最小サポートminsupport sを満たす入力索引木の全てのノードで構成される非併合規則木が出力される。
【００５４】
図８は、非併合規則木から併合規則木を構築するプロセスを記載する詳細流れ図である。この流れ図によって記載されるアルゴリズムは、非併合規則木を圧縮して規則の階層表現を得る。非併合規則木を縦型探索順（in depth first search order）に走査して、各ノードでそのノードに意味があるかどうかの決定を下す。意味のあるノードは、それに関連付けられる規則を有するノードであると定義される。規則は、非併合木が形成されたときにノードに関連付けられていることもあり、関連付けられていないこともある。意味のあるノードと意味の無いノードの区別をさらに明瞭にするために、図７の非併合規則木を再び参照すると、ここで意味のあるノードはノード１、２、および４に対応する。意味のあるノードは全て、併合規則木に保存される。ノードが意味を有さないと決定されると、アルゴリズムはそのノードを除去するか、または特定の条件が満たされるときには複数の子ノードを併合して単一ノードにする。
【００５５】
ステップ５００は、アルゴリズムの入口点を表す。ステップ５１０は、非併合規則木を縦型探索順に走査することを確実にするプロセス・ステップを実現するソフトウェアを表す。ステップ５１５は、縦型走査で非併合規則木の次のノードに進むステップを表す。ステップ５２０は、現在の規則ノードが意味のあるノードであるかどうかを決定する決定ステップを表す。現在のノードに意味があると決定された場合、ステップ５３０に分岐が行われる。そうでない場合には、アルゴリズムはステップ５４０に分岐し、それによってそのノードは無意味と分類される。ステップ５４０は、無意味ノードが子ノードを有するかどうかを決定する決定ステップである。無意味ノードに子ノードが無ければ、ステップ５５０に分岐する。ステップ５５０は、現在の無意味ノードを削除するプロセス・ステップを表す。そうではなく、ステップ５４０で現在のノードに子ノードがあると決定された場合、ステップ５６０に分岐される。ステップ５６０は、現在の無意味ノードが１つの子ノードを有するか、それともそれ以上の子ノードを有するかを決定するための決定ステップである。現在のノードが単一の子ノードしか有さない場合には、ステップ５７０に分岐される。ステップ５７０は、現在のノードを削除し、削除された無意味なノードの親ノードと子ノードを索引木の中で直接一つに接続するプロセス・ステップを実現するソフトウェアを表す。そうでなく、現在のノードが複数の子ノードを有することが明らかになった場合には、ステップ５８０に分岐される。ステップ５８０は、２つの子ノードの最小外接長方形が無意味な親ノードのそれより大きいかどうかを決定する決定ステップである。最小外接長方形は、各子ノードの定量属性の上限および下限（範囲）によって定義される。子ノードの範囲を組み合わせて、親ノードの範囲より広くなることが分かった場合、併合が発生する。例えば、子ノードが
子ノード１−年齢［１０〜２０］
子ノード２−年齢［３０〜４０］
と定義され、対応する親ノードが
親ノード−年齢［１０〜３０］
と定義された場合、この例では、子属性範囲の組合せにより［１０〜４０］の複合範囲が生じ、これは親ノード［１０〜３０］によって指定される範囲より広いので、併合が発生する。
【００５６】
２つの子ノードの最小外接長方形が親ノードのそれを超える場合、ステップ５９０への分岐が行われる。ステップ５９０は、親の最小外接長方形を２つの子ノードの最小外接長方形となるように調整するプロセス・ステップを実行するソフトウェアを表す。決定ステップ６００への分岐は、木にさらに走査すべきノードがあるかどうかを決定する。走査すべきノードがもう残っていなければ、終了ステップ６１０に分岐し、そうでない場合には、残りの索引ノードに対してプロセス・ステップ４９０〜５１５が繰り返される。
【００５７】
図１０は、併合規則木を入力として使用して、利用者指定関心レベルｒの規則を定義するするプロセスを記載する詳細流れ図である。併合規則木は縦型探索順に走査される。ステップ６１６は、流れ図の入口点である。利用者は、関心レベルを表すｒの入力値を指定する。ステップ６１８は、縦型探索順で併合規則木における次のノードを選択することを表す。ステップ６２０は、関心対象の現在のノードの全ての先祖ノードを見て、それらの中に信頼度値が現在のノードの１／ｒに少なくとも等しいものがあるかどうかを決定する決定ステップである。条件が真である場合には、ステップ６３０に分岐する。ステップ６３０は、現在のノードに関連付けられる規則の刈込み（prunning）を表す。条件が満たされなければ、ステップ６４０に分岐する。ステップ６４０は、併合規則木に評価すべきノードが残っているかどうかを決定する決定ステップである。評価すべき追加ノードがある場合には、プロセス・ステップが繰り返され、そうでない場合には、プロセスはこの時点で終了する。
【００５８】
したがって要約すると、定量的連想規則を見つけるためのデータ項目のデータ・マイニングのオンライン方法を提供することができ、データ項目は様々な種類の定量属性およびカテゴリ属性を含む。
【００５９】
以下に本発明の内容をまとめて記載する。
（１）  定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングの方法であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、及び前記定量項目及び／又はカテゴリ項目で表現される前件属性および後件属性を含む利用者問合せとを受け取るステップと、
ｂ）前記前件属性を複数の索引ノードを含む索引木内に階層的に事前格納することによって前記前件属性と後件属性との間の関係を編成するステップであって、各索引ノードは実サポートと各利用者問合せの後件属性の信頼度とを表す第１及び第２の値を有する、前記編成するステップと
ｃ）前記索引木の全ての索引ノードを検索して、その前件属性の範囲が前記利用者問合せの前件属性範囲に対応し且つそれが最小信頼度の前記利用者定義値に少なくとも等しい信頼値と最小サポートの利用者定義値に少なくとも等しいサポート値を有するところの索引ノードを分離することによって、前記利用者問合せに応じて前記事前格納されたデータから応答を導出するステップと
を含む方法。
（２）  前記応答が、１つまたはそれ以上の定量的連想規則、各規則に関連付けられた実信頼度値、各規則に関連付けられた実サポート値を含む、（１）に記載の方法。
（３）  利用者定義された関心レベルが前記受け取るステップにおいて提供され、前記応答が各規則に関連付けられた関心レベルを含み、それによって前記１つまたはそれ以上の定量的連想規則が、計算された関心レベルが前記利用者定義された関心レベルに少なくとも等しい規則のみで構成される、（１）又は（２）のいずれかに記載の方法。
（４）  前記関心レベルが第１および第２比率の計算値のうち最小のものと定義され、前記第１比率は実信頼度を予想信頼度で割ったものと定義され、第２比率は実サポートを予想サポートで割ったものと定義され、前記予想信頼度およびサポートは統計的独立性の推定に基づく計算値である、（３）に記載の方法。
（５）  前記前件属性がカテゴリ属性および定量属性を含む、（１）ないし（４）のいずれか一項に記載の方法。
（６）  前記定量属性が下限および上限から成る範囲によってさらに定義される、（５）に記載の方法。
（７）  前記導出するステップが、無意味なノードを削除し、他のノードを組み合わせることによって併合木を形成するステップを含み、無意味なノードとは、最小信頼度の前記利用者定義値に少なくとも等しい信頼度の対応する計算値を有しないノードである、（１）〜（６）のいずれか一項に記載の方法。
（８）  前記併合木を単一の後件属性または複数の後件属性のいずれかのために作成することができる、（７）に記載の方法。
（９）  前記受け取るステップが、最小サポートの利用者定義値と、最小信頼度の利用者定義値と、利用者定義された関心値と、ならびに前件属性および後件属性を含む利用者問合せを含むデータとをコンピュータに入力することを含み、前記前件属性および後件属性が複数の定量属性およびカテゴリ属性をさらに含み、
前記編成するステップは、１つまたはそれ以上の次元で構成される索引木をメモリ内に構築するステップを含み、各次元は前記前件属性に含まれる利用者供給定量属性の１つによって定義され、前記索引木は複数の索引ノードを含み、該索引ノードは複数のデータ・レコードを含み、
前記導出するステップは、前記索引木から非併合規則木をメモリ内に構築し及び前記非併合規則木から併合規則木をメモリ内に構築するステップと、前記利用者問合せを満足する索引ノードであって、そのサポートが少なくとも前記最小サポートに等しくかつその信頼度が前記最小信頼度に少なくとも等しいところの索引ノードから、１つまたはそれ以上の定量的連想規則を生成するステップとを含み、
前記方法は、前記生成ステップからの前記定量的連想規則と、生成された各々の定量的連想規則に関連付けられた実信頼度の値と、生成された各々の定量的連想規則に関連付けられたサポートの値と、生成された各々の定量的連想規則に関連付けられた関心レベルの値とを含む出力データを利用者に表示するステップとを含む、
（１）に記載の方法。
（１０）  定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングの方法であって、
ａ）最小サポートの利用者定義値と、最小信頼度の利用者定義値と、利用者定義された関心レベルと、並びに前件属性および後件属性を含む利用者問合せとを受け取るステップであって、前記前件属性および後件属性は複数の定量属性及びカテゴリ属性をさらに含む、前記受け取るステップと、
ｂ）１つまたはそれ以上の次元で構成される索引木をメモリ内に構築するステップであって、各次元が定量属性の一つによって定義され、前記索引木は複数の索引ノードを含み、該索引ノードは複数のデータ・レコードを含む、前記構築するステップと、
ｃ）前記索引木から非併合規則木をメモリ内に構築するステップと、
ｄ）前記非併合規則木から平衡規則木をメモリ内に構築するステップと、
ｅ）前記利用者問合せを満足する索引ノードであって、そのサポートが少なくとも前記最小サポートに等しくかつその信頼度が前記最小信頼度に少なくとも等しいところの索引ノードから、一つまたはそれ以上の定量的連想規則を生成するステップと、
ｆ）前記生成ステップからの前記定量的連想規則と、生成された各々の定量的連想規則に関連付けられた実信頼度の値と、生成された各々の定量的連想規則に関連付けられたサポートの値と、生成された各々の定量的連想規則に関連付けられた関心レベルの値とを含む出力データを利用者に表示するステップと
を含む方法。
（１１）  前記利用者問合せを対話的に修正して前記連想規則をさらに定義するように、１つまたはそれ以上の定量的連想規則を生成するステップを繰り返す、（９）又は（１０）のいずれかに記載の方法。
（１２）  （９）又は（１０）のいずれかに記載の索引木をメモリ内に構築するステップが、
１つまたはそれ以上の次元の２分索引木を構築するステップであって、各次元が前記利用者供給定量前件属性の１つによって定義される、前記２分索引木を構築するステップと、
前記サポート・レベルおよび信頼度レベルを各索引ノードに格納するステップと
を含む、（９）〜（１１）のいずれか一項に記載の方法。
（１３）  （９）又は（１０）のいずれかに記載の前記非併合規則木を構築するステップが、
前記索引木の各ノードを探索するステップと、
利用者指定後件属性を満足し且つ最小信頼度の前記利用者定義値に少なくとも等しい信頼度を有するところの規則と、最小サポートの前記利用者定義値に少なくとも等しいサポート値とを有するノードを選択するステップと
を含む、（９）〜（１２）のいずれか一項に記載の方法。
（１４）  利用者指定後件属性を満たす規則を含むノードを選択する前記ステップが、
ポインタを構築するステップと、
前記ポインタを前記索引木のルート・ノードに設定するステップと、
前記ポインタに関連付けられた前記ノードをリストに追加するステップと、
前件属性が前記利用者指定前件属性のパラメータ内に完全に含まれ且つ最小サポート値が前記利用者定義最小サポートに少なくとも等しいところの前記ポインタによって指定されたノードの全ての子をリストに追加するステップと、
前記ポインタによって指定されたノードに格納されたデータ・レコードが利用者指定後件属性に少なくとも等しく且つ前記利用者定義最小信頼度に少なくとも等しい信頼度を有しているかどうかを決定するステップと、
前記後件属性に関連付けられた定量的連想規則を生成するステップと、
直上の生成するステップの条件が満たされない場合、前記リストから前記ノードを削除するステップと、
前記リストが空かどうかを決定するステップと、
前記リストが空の場合には終了するステップと、そうでない場合には前記ポインタを前記索引木の次のノードに設定し、前記ポインタに関連付けられたノードをリストに追加するステップからそれ以降の上記ステップを繰り返すステップと
を含む、（１３）に記載の方法。
（１５）  （９）又は（１０）のいずれかに記載の前記併合規則木を構築するステップが、
ａ）非併合規則木の各ノードをポスト順に走査することと、
ｂ）ｉ）各前記利用者定義後件属性値が前記ノードに格納された後件属性値より大きいかどうかを決定し、
ｉｉ）（ｉ）の条件が満たされた場合、前記併合規則木に前記ノードを保存し、
ｉｉｉ）（ｉ）の条件が満たされず且つ前記ノードに関連付けられた子ノードが無い場合、前記併合規則木から前記ノードを削除し、
ｉｖ）（ｉ）の条件が満たされず且つ前記ノードに１つの子ノードがある場合、前記併合規則木から前記ノードを削除し、先祖ノードと前記削除されたノードの子ノードとを直接関連付け、
ｖ）（ｉ）の条件が満たされない場合、前記後件属性の範囲を調整することによって、
走査された各ノードを非併合規則木に含めるか除外するかを評価するステップと
を含み、
全てのノードがポスト順に走査し終わるまで前記評価ステップを繰り返す、（９）〜（１４）のいずれか一項に記載の方法。
（１６）  定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する多数のレコードを有する大規模データベースのオンライン・マイニングのための装置であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、及び前記定量項目及び／又はカテゴリ項目で表現される前件属性および後件属性を含む利用者問合せとを受け取るための手段と、
ｂ）前記前件属性を複数の索引ノードを含む索引木内に階層的に事前格納することによって前記前件属性と後件属性との間の関係を編成する手段であって、各索引ノードは実サポートと各利用者問合せの後件属性の信頼度とを表す第１及び第２の値を有する、前記編成する手段と
ｃ）前記索引木の全ての索引ノードを検索して、その前件属性の範囲が前記利用者問合せの前件属性範囲に対応し且つそれが最小信頼度の前記利用者定義値に少なくとも等しい信頼値と最小サポートの利用者定義値に少なくとも等しいサポート値を有するところの索引ノードを分離することによって、前記利用者問合せに応じて前記事前格納されたデータから応答を導出する手段と
を含む装置。
（１７）  定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングの方法であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、並びに前件属性および後件属性を含む利用者問合せとを受け取るステップと、
ｂ）前記前件属性と後件属性との間の関係を編成するステップであって、前記編成するステップは前記前件属性を階層的に索引木に分割することを含み、前記索引木は複数の索引ノードを含み、前記分割は、ａ）前記索引木の各索引ノードに実サポートを含む第１の値を格納し、ｂ）各利用者問い合わせの後件属性の信頼度を表す第２の値を格納する、前記編成するステップと、
ｃ）前記前件属性と前記後件属性との間の関係を定義するデータを事前格納するステップと、
ｄ）前記利用者問合せに応じて前記事前格納されたデータから応答を導出するステップと
を含む方法。
（１８）  定量的連想規則を提供するために各々が複数の定量項目およびカテゴリ項目を有する複数のレコードを有する大規模データベースのオンライン・マイニングのための装置であって、
ａ）最小信頼度の利用者定義値と、最小サポートの利用者定義値と、並びに前件属性および後件属性を含む利用者問合せとを受け取る手段と、
ｂ）前記前件属性と後件属性との間の関係を編成する手段であって、前記編成するステップは前記前件属性を階層的に索引木に分割することを含み、前記索引木は複数の索引ノードを含み、前記分割は、ａ）前記索引木の各索引ノードに実サポートを含む第１の値を格納し、ｂ）各利用者問い合わせの後件属性の信頼度を表す第２の値を格納する、前記編成する手段と、
ｃ）前記前件属性と前記後件属性との間の関係を定義するデータを事前格納する手段と、
ｄ）前記利用者問合せに応じて前記事前格納されたデータから応答を導出する手段と
を含む装置。
【図面の簡単な説明】
【図１】コンピュータ・ネットワークの全体的な概要を示す略図である。
【図２】２段階で構成されるデータ・マイニング法の全体的概要を示す流れ図のうち、前処理段階の流れ図である。
【図３】アルゴリズムのオンライン段階の流れ図である。
【図４】索引木が前件集合を用いてどのように構築されるかを詳細に示す流れ図である。これは図２のステップ７５の拡張と考えることができる。
【図５】索引木が前件集合を用いてどのように構築されるかを詳細に示す流れ図である。これは図２のステップ７５の拡張と考えることができる。
【図６】索引木から非併合規則木がどのように構築されるかを詳細に示す流れ図である。これは図３のステップ１００の拡張と考えることができる。
【図７】索引木から非併合規則木がどのように構築されるかを詳細に示す流れ図である。これは図３のステップ１００の拡張と考えることができる。
【図８】非併合規則木から併合規則木がどのように構築されるかを示す流れ図である。
【図９】非併合規則木から併合規則木がどのように構築されるかを示す流れ図である。
【図１０】ある利用者指定関心レベルｒで併合規則木から定量的連想規則がどのように生成されるかを示す流れ図である。
【図１】
0003575602.tif 000007
【図２】
0003575602.tif 000008
【図３】
0003575602.tif 000009
【図４】
0003575602.tif 000010
【図５】
0003575602.tif 000011
【図６】
0003575602.tif 000012
【図７】
0003575602.tif 000013
【図８】
0003575602.tif 000014
【図９】
0003575602.tif 000015
【図１０】
0003575602.tif 000016