(57)【特許請求の範囲】
【請求項１】
タプル・リストの集合から重み付き相関ルールを生成する方法であって、各タプルが項目および関連する重みを含み、各タプル・リストが複数のタプルを含み、前記方法が、前記タプル・リストの集合を保持し、重み付き相関ルールを生成するコードを記憶し、前記コードを実行するマイニング・システムによって実行され、
前記システムが前記タプル・リストの集合から複数の頻出項目セットを生成するステップと、
前記システムが、事前に指定されるサポート・レベルを超えることを要件とするサポート要件、事前に指定される確信度レベルを超えることを要件とする確信度要件、および事前に指定される密度レベルを超えることを要件とする密度要件が満たされるように、各ルールが前件部分および後件部分を有し、ルールの前記後件部分がタプル・リストからの項目の第１部分集合によって形成され、前記ルールの前記前件部分が前記タプル・リストの項目のオーバーラップしない第２部分集合によって形成される該ルール内で各項目の重みの値の範囲を指定して、各頻出項目セットから重み付き相関ルールを生成するステップとを含み、
各頻出項目セットから重み付き相関ルールを生成する前記ステップが、
各頻出項目セット内の各項目の重みの範囲を区間に分割することによってグリッドを生成するステップと、
各グリッド内のタプル・リストの数として各グリッドの密度を定義し、グリッドが前記密度レベルを超える密グリッドであるか否かを判定し、前記密グリッドを保持するステップと、
隣接する前記密グリッドの集合である密領域に基づいて生成され、各次元上の座標が前記ルールの前記前件部分の対応する項目の前記重みの範囲を与える密ボックスを、前記密ボックスの確信度要件およびサポート要件を検証して識別するステップと
を含む、方法。
【請求項２】
グリッドを生成する前記ステップが、項目セットのサイズに無関係に、各項目セットのグリッドの個数を一定に維持する、請求項１に記載の方法。
【請求項３】
グリッドを生成する前記ステップが、密度に関して評価しなければならないグリッドの数を減らすために、前記密度レベルを超えない疎グリッドを除去するステップをさらに含む、請求項１に記載の方法。
【請求項４】
密ボックスを識別する前記ステップが、
最大の前記密領域を識別するステップと、
前記最大の密領域を最大の密ボックスに縮小するステップと
を含む、請求項１に記載の方法。
【請求項５】
縮小する前記ステップが、縮小動作を実行するために、前記次元の下限を増加または上限を減少させる、請求項４に記載の方法。
【請求項６】
前記最大の前記密領域を識別するステップが、最大の体積を有する前記密ボックスの候補がヒープの最上部に置かれるようにするヒープ方法を使用して、追加の縮小された密ボックスの候補を追跡するステップをさらに含む、請求項４に記載の方法。
【請求項７】
前記ヒープ方法が、
前記ヒープから最上部のボックスを除去するステップと、
前記除去されたボックスのすべての正当な縮小を生成するステップと、
確信度要件およびサポート要件の両方が満たされる場合に、新たに生成された縮小ボックスを重み付き相関ルールとして出力するステップと、
そうではなく、サポートが満たされない場合に、新たに生成されたボックスを破棄するステップと、
サポートが満たされる場合に、新たに生成されたボックスをヒープに戻すステップと
を含む、請求項６に記載の方法。
【請求項８】
前記最大の前記密領域を識別するステップは、キュー方法を使用して前記追加の縮小された密ボックスの候補を追跡するステップをさらに含む、請求項４に記載の方法。
【請求項９】
前記密グリッドを保持するステップは、グリッド上で各ｎ項目集合のカウンタの２つの集合を維持するステップをさらに含み、第１集合が、前記グリッドのサポートを記録する主カウンタであり、第２集合が、それぞれが各（ｎ−１）次元空間へのグリッド投影のサポートを記録する投影カウンタの集合であり、
さらに、前記カウンタ集合を除去するステップを含み、前記除去するステップが、サポート・レベル単位に、
ｎ項目セットから（ｎ−１）項目セットへの投影カウンタを判定するステップと、
評価が必要なｎ項目セットの前記主カウンタを除去するために、ｎ項目セットから（ｎ−１）項目セットへの前記投影カウンタを使用するステップと、
ｎ項目セットの残りの主カウンタを判定するステップと、
評価が必要なｎ項目セットへの（ｎ＋１）項目セットの投影カウンタを除去するために、ｎ項目セットの前記主カウンタを使用するステップと
を含む請求項１に記載の方法。
【請求項１０】
頻出項目セットを生成するステップが、反復方法を使用する、請求項１に記載の方法。
【請求項１１】
マイニング・システムが実行するタプル・リストの集合から重み付き相関ルールを生成するコードを記録したコンピュータ可読な記録媒体であって、各タプルが項目および関連する重みを含み、各タプル・リストが複数のタプルを含み、前記マイニング・システムが、
前記タプル・リストの集合から複数の頻出項目セットを生成するステップと、
事前に指定されるサポート・レベルを超えることを要件とするサポート要件、事前に指定される確信度レベルを超えることを要件とする確信度要件、および事前に指定される密度レベルを超えることを要件とする密度要件が満たされるように、各頻出項目セット内の各項目の重みの範囲を区間に分割することによってグリッドを生成し、各グリッド内のタプル・リストの数として各グリッドの密度を定義し、グリッドが前記密度レベルを超える密グリッドであるか否かを判定し、前記密グリッドを保持し、隣接する前記密グリッドの集合である密領域に基づいて生成され、各次元上の座標が前記ルールの前件部分の対応する項目の前記重みの範囲を与える密ボックスを、前記密ボックスの確信度要件およびサポート要件を検証して識別することにより、各ルールが前件部分および後件部分を有し、ルールの前記後件部分がタプル・リストからの項目の第１部分集合によって形成され、前記ルールの前記前件部分が前記タプル・リストの項目のオーバーラップしない第２部分集合によって形成される該ルール内で各項目の重みの値の範囲を指定して、各頻出項目セットから、重み付き相関ルールを生成するステップと
を実行する、記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全般的にはデータ・マイニングに関し、具体的には、数値的な重みを付けられた属性値を用いる相関ルールのマイニングに関する。
【０００２】
【従来の技術】
データ・マイニングは、データ内に明示的に提示されていない、暗黙の知識の抽出と、興味深い特性およびパターンの発見である。これらの技法は、簡潔な形でデータを提示し、データ・セマンティクスを適合させる際に重要な役割を演じることができる。近年、この分野で活動的なトピックの１つが、Ｒ．アグラワル（Agrawal）、Ｔ．イミーリンスキ（Imielinski）、およびＡ．スワミ（Swami）著、「Mining association rules between set of items in large databases」、Proceedings of the 1993 ACM SIGMOD Conference on Management of Data、１９９３年で導入された相関ルール発見である。一般に、この問題は、次の形でモデル化することができる。Ｉが、項目の集合であり、Ｔが、トランザクションの集合であり、トランザクションのそれぞれが、Ｉに含まれる項目の部分集合からなると仮定する。相関ルールは、「Ｘ→Ｙ」の形の含意（implication）であり、ここで、ＸおよびＹは、互いに疎な（disjoint）項目セットの集合である。「Ｘ→Ｙ」は、ｓ％のトランザクションに、集合「Ｘ∪Ｙ」のすべての項目が含まれ、Ｘのすべての項目を含むｃ％のトランザクションに、Ｙのすべての項目も含まれる場合に、Ｔにおいてサポートｓおよび確信度（confidence）ｃで成り立つ。相関ルール・マイニング・プロセスの目標は、ある最小のｓおよびｃに関して、これらのルールのすべてを見つけることである。項目（または項目セット）は、そのサポートが少なくともｓである場合に、「頻出（frequent）」項目（または項目セット）と呼ばれる。
【０００３】
これらの従来の相関ルールは、多くの応用分野領域で幅広く使用されてきた。マーケット・バスケット問題では、スーパーマーケットの商品のそれぞれを、項目とみなすことができ、顧客が１つの時間期間に購入する項目の集合を、トランザクションと見なすことができる。相関ルールは、項目が顧客によって一緒に購入される確度を表す。したがって、この知識を使用して、販売促進を案内することができる。たとえば、ソーダとスナックの間に高い確信度がある場合に、スーパーマーケットは、スナックの売上を増やすためにソーダの値段を下げることができる。
【０００４】
しかし、従来の相関ルールは、２進属性（binary attributes）に焦点を合わせている。言い換えると、この手法は、項目がトランザクションに存在するかどうかを考慮するだけで、トランザクション内の項目の重み／強さ（weight／intensity）を考慮に入れていない。たとえば、ある顧客が、１０本のソーダと５袋のスナックを購入するが、別の顧客が、４本のソーダと１袋のスナックを同時に購入する可能性がある。しかし、この２つのトランザクションは、従来の相関ルール手法では同一である。これは、いくつかのきわめて重要な情報すなわち、トランザクションの各項目の強さまたは重みの消失につながる可能性がある。たとえば、ある顧客が、７本を超えるソーダを購入する場合に、その顧客は、３袋以上のスナックを購入する可能性が高く、そうでない場合には、ソーダの購入傾向は強くない。従来の相関ルールでは、この種の関係を表現することができない。この知識があれば、スーパーマーケットの支配人が、「ソーダ６本お買い上げのお客様にスナック２袋をプレゼントする」などの促進を設定することができる。
【０００５】
相関ルールの新しい変形が、Ｒ．スリカント（Srikant）およびＲ．アグラワル（Agrawal）著、「Mining quantitative association rules in large relational tables」、Proceedings of the 1996 ACM SIGMOD Conference on Management of Data Montreal、Canada、１９９６年６月で提案された。各定量的属性の定義域が、等深区分を介して区間（すなわち、バスケット、範囲）の集合に分割される、すなわち、各区間は類似した個数の属性値を有する。区間は、そのサポートがユーザ指定の最大サポートより小さい限り、組み合わせられる。元の区間のそれぞれおよび組み合わされた区間は、異なる項目として扱われる。したがって、新たに「生成される」項目の属性値は、２進であり、「１」が、元の属性値が指定された区間内にあることを表し、「０」が、元の属性値が指定された区間内にないことを表す。従来の相関ルールをマイニングするためのアルゴリズムを、これらの新たに生成された２進項目に適用することができる。
【０００６】
写像処理中に、１つの数値属性が、Ｏ（ｋ2）個の２進属性に写像され、このｋは、１つの属性定義域の区間数である。数値属性の数が多くなった時に、写像される２進属性の数が、御しがたくなる可能性がある。
【０００７】
【発明が解決しようとする課題】
したがって、本発明の目的は、特定のタイプの相関ルールすなわち重み付き相関ルール（weighted association rule）をマイニングするための効率的な方法を提供することである。
【０００８】
【課題を解決するための手段】
本発明によれば、トランザクションの各項目に重みを関連付けられるようにして、トランザクション内での各項目の関心／強さを反映できるようにすることによって、従来の相関ルール問題が拡張される。これによって、重みパラメータを各項目に関連付ける機会が与えられ、重み付き相関ルール（ＷＡＲ）と称する相関ルールがもたらされる。たとえば、「ｓｏｄａ［４、６］→ｓｎａｃｋ［３、５］」は、顧客が４本と６本の間の量のソーダを購入する場合に、その顧客が３ないし５袋のスナックを購入する可能性が高いことを示す重み付き相関ルールである。したがって、ＷＡＲは、ルールの確信度を改善できるだけではなく、潜在的なロイヤルティの度合または購入量に基づいて顧客を識別またはセグメント化することによるより効率的なターゲット・マーケティングを行う機構も提供することができる。
【０００９】
項目のわずかな部分だけがトランザクションに存在する場合であっても、所与の問題に非常に多数の項目が存在し、すべての項目が多数の属性を有する可能性がある。したがって、本発明の好ましい方法によれば、頻出項目セットが、まず生成される（重みを考慮せずに）。この方法は、従来技術と異なる。各頻出項目セット内の各項目の重みの範囲が、「ベース区間」と称する一連の区間に分割される。その後、各頻出項目セットの重み定義域空間が、微細なグリッドに区分される。グリッドとは、各次元でのスパンが正確に１ベース区間である多次元キューブである。グリッドの密度は、ランダムな一様分布を前提として、それに含まれるトランザクションの期待される数に対する、それに属するトランザクションの実際の数の比率として定義される。密度閾値を使用して、トランザクション集中領域をそれ以外の領域から分離する。グリッドは、その密度が事前に指定された閾値を超える場合に、「密グリッド（dense grid）」と呼ばれる。そうでない場合には、「疎グリッド（sparse grid）」と呼ばれる。「密領域」は、隣接する密グリッドの集合の和集合である。ＷＡＲを、これらの「密」領域に基づいて識別することができる。
【００１０】
実際には、有効な重み付き相関ルール（ＷＡＲ）の数は、非常に多くなる可能性があり、ユーザが、すべてのＷＡＲではなく、その小さい部分集合に関心を持つ可能性がある。たとえば、あるスーパーマーケットでソーダの在庫が多くなりすぎた場合、支配人は、ソーダにかかわるＷＡＲだけに関心を持つ可能性がある。ユーザが、マイニング・システムと対話して、パラメータ値を変更することによって興味深いＷＡＲの集合を得ることができるならば望ましい。これに鼓舞されて、本発明の方法は、バッチ・モードと対話モードの両方をサポートする。バッチ・モードでは、すべての有資格のＷＡＲが返される。その一方で、対話モードでは、ユーザが、さらに調査するために興味深い頻出項目セットの集合を選択できるだけではなく、サポート、関心、および密度の閾値を変更し、その結果、関心のある項目セットに関する有資格のＷＡＲだけが返されるようにすることもできる。
【００１１】
本発明は、次のように要約することができる。
１）新しいクラスの相関ルール問題であるＷＡＲを提案する。
２）この問題の性質に起因して、マイニング処理が、３部分の手法によって達成される。
ａ）まず、頻出項目セットを生成し、各頻出項目セットからＷＡＲを導出する。
ｂ）頻出項目セット生成処理中には、関連する重みが無視される。項目セットが頻出項目セットになるのは、この項目セットが、トランザクションの少なくともある比率に現れる場合である。
ｃ）ＷＡＲ導出処理中に、重み定義域空間が、グリッドの総数があるパラメータＮによって制限され、その結果、使用可能なメモリ／記憶域空間を完全に利用できるようになる形で区分される。密度の概念を使用して、トランザクション集中のまたは密な領域を、残りの部分から分離する。収縮を介して高密度領域からＷＡＲを導出するために、効率的な順序付き収縮アルゴリズムを提案する。
【００１２】
【発明の実施の形態】
ここで図面、具体的には図１を参照すると、本発明の、重み付き相関ルール（ＷＡＲ）をマイニングする全体的な処理が示されている。まず、機能ブロック１０１で、トランザクションの所与の集合から、すべての頻出項目セットを生成する。ここで図９を参照すると、頻出項目セット・マイニング処理が示されている。この処理は、上記のＲ．アグラワル（Agrawal）、Ｔ．イミーリンスキ（Imielinski）、およびＡ．スワミ（Swami）著、「Mining association rules between set of items in large databases」によって最初に導入された。機能ブロック９０１で、Ｃ1が、単一の項目だけを含む１項目セットの候補集合であるものとする。また、ｊを１に初期化する。判断ブロック９０２での判定で、Ｃjが空でない場合、機能ブロック９０３で、Ｃjの項目セットごとにサポートを収集する。サポートがサポート閾値より大きい項目セットがある場合、機能ブロック９０４で、これらの項目セットをＬjに入れる。Ｌjに基づいて、機能ブロック９０５で次の形でＣj+1を構成する。Ｌjに含まれる、ｊ＋１個の別個の項目セットがある場合に、ｊ＋１項目を有する項目セットをＣj+1に加える。
【００１３】
もう一度図１を参照すると、これらの頻出項目セットが、そのカーディナリティの昇順で順次検査される。項目セットのカーディナリティは、項目セット内の項目の数として定義される。２項目セットがまず検査される。この処理は、処理の二重ループに入る。外側のループは、未検査のまま残っている頻出項目セットがあるかどうかを判定する判断ブロック１０３のテストから始まる。そうである場合には、内側のループが、未検査のまま残っている頻出ｎ項目セットがあるかどうかを判定する判断ブロック１０４のテストから始まる。そうである場合には、機能ブロック１０５で、未検査の頻出ｎ項目セットを選出し、機能ブロック１０６で、重み付き相関ルールを生成する。内側の処理は、すべての頻出ｎ項目セットが検査されるまで、判断ブロック１０４にループ・バックする。処理が内側のループから抜けるたびに、機能ブロック１０７で、検査される項目セットのカーディナリティを１つ増分する。全体処理は、すべての頻出項目セットが検査されるまで、判断ブロック１０３にループ・バックする。
【００１４】
図２は、機能ブロック１０６で示された、所与の頻出項目セットＦについてＷＡＲを生成する処理を示す図である。機能ブロック２０１で、Ｆの重み定義域空間を、グリッドに区分し、各グリッドのサポートをカウントする。グリッドに十分なトランザクションが含まれる場合、これを密グリッドと呼ぶ。機能ブロック２０２で、すべての疎（すなわち非密）グリッドを除去し、密グリッドだけを、次の検査のために保持する。機能ブロック２０３で、密グリッドに基づいて、密領域を構成する。各密領域は、連結された密グリッドの集合である。機能ブロック２０４で、密領域ごとに、その領域の最小境界ボックスを構成する。その後、機能ブロック２０５で、順序付き縮小ルーチンを使用して、有資格のＷＡＲを見つける。
【００１５】
図３は、所与の頻出ｎ項目セットＦに関する、機能ブロック２０１に示されたカウンタ生成処理を示す図である。機能ブロック３０１で、ｎ個の異なる（ｎ−１）項目部分集合のそれぞれに対するＦの投影カウンタの集合を生成する。判断ブロック３０２でテストを行って、このカウンタ集合が空であるかどうかを判定する。そうでない場合には、機能ブロック３０３でデータを走査して、これらの投影カウンタの値を得る。機能ブロック３０４で、投影カウンタの値に基づいて、Ｆの主カウンタを生成する。判断ブロック３０５のテストで、このカウンタ集合が空であるかどうかを判定する。そうでない場合には、機能ブロック３０６で、データを検査して、この主カウンタの値を得る。
【００１６】
図４は、機能ブロック３０４に示された、主カウンタ生成処理を示す図である。まず、Ｆの重み定義域空間をグリッドに分割する。機能ブロック４０１で、各次元をＮ1/n個の区間に区分するが、このｎは、次元の数であり、Ｎは、所望のグリッドの数である。その後、処理はループに入り、このループで、グリッドｇごとに、判断ブロック４０３でテストを行って、必要な密度が満たされない、Ｆの（ｎ−１）項目部分集合の重み定義域空間に対するｇの投影が存在するかどうかを判定する。そうでない場合には、機能ブロック４０４で、ｇのカウンタを確立し、０に初期化する。
【００１７】
図５は、機能ブロック３０１に示された、ｎ項目セットＦに関する投影カウンタを生成する処理を示す図である。ｎ個の可能な（ｎ−１）項目部分集合のそれぞれを、順次検査する。処理ループに入る前に、機能ブロック５０１でインデックスｊに１をセットする。処理ループ内の最初のステップは、判断ブロック５０２で、Ｆにｎ項目が含まれると仮定して、インデックスｊがｎに等しいかどうかを判定することである。Ｆの項目ｉのそれぞれについて、機能ブロック５０３でｉをＦから除去し、ｎ−１項目を含む新しい集合Ｆ'を生成する。次に、機能ブロック５０４で、Ｆ'の重み定義域空間の各次元を、Ｎ1/n個の区間に区分する。Ｆ'のグリッドの総数は、Ｎ(n-1)/nになる。判断ブロック５０５のテストで、Ｆが２項目セットであるかどうかを判定する。そうである場合には、各グリッドのカウンタを確立し、０に初期化する。そうでない場合には、機能ブロック５０７で、Ｆ'の主カウンタの値を使用して、投影カウンタをセット・アップするための候補グリッドを生成する。その後、機能ブロック５０８で、各候補グリッドのみに対してカウンタを確立し、０に初期化する。その後、処理が判断ブロック５０２にループ・バックする前に、機能ブロック５０９で、インデックスｊを１つ増分する。
【００１８】
図６は、機能ブロック２０３に示された、主カウンタの集合から密領域を生成する処理を示す図である。この処理では、幅優先アルゴリズムを使用する。判断ブロック６０１で、処理ループに入り、未訪問のグリッドがあるかどうかを判定する。そうである場合には、機能ブロック６０２で、未訪問のグリッドをランダムに選出する。その後、機能ブロック６０３で、グリッドを空の領域集合ｒに入れる。判断ブロック６０４でテストを行って、未訪問の隣接グリッドｇ'があるかどうかを判定する。そうでない場合には、処理は判断ブロック６０１にループ・バックし、そうである場合には、機能ブロック６０５で、領域集合ｒに含まれるグリッドに隣接するすべてのグリッドを、ｒに追加する。その後、処理は判断ブロック６０４にループ・バックして、未訪問の隣接グリッドの処理を継続する。
【００１９】
図７は、機能ブロック２０４に示された、密領域ｒごとに最小境界ボックスを見つける処理を示す図である。まず、機能ブロック７０１で、密領域ｒごとの外側処理ループに入る。機能ブロック７０２で、ｒのグリッドをランダムに選出し、最小境界ボックスを、そのグリッドとしてセットする。判断ブロック７０３で、処理ループに入り、まだｂ（ｒ）によって囲まれていないグリッドｇがｒに含まれるかどうかを判定する。最小境界ボックスがｒを囲んでいない場合には、機能ブロック７０４でボックスを拡大する。ボックスがｒを囲んだ時に、この処理は終了する。
【００２０】
図８は、機能ブロック２０５に示された、最小境界ボックスｂからのＷＡＲ生成処理を示す図である。まず、機能ブロック８０１で、ボックスｂだけを含むように候補集合を初期化する。次に、判断ブロック８０２で、候補集合が空であるかどうかに関する判定を行う。候補集合が空でない場合には、機能ブロック８０３で、候補集合からのボックスを採用する。判断ブロック８０４で、対応するＷＡＲのサポートが要件を満足すると判定される場合には、判断ブロック８０５でＷＡＲを検査して、それが確信度要件を満足するかどうかを判定する。そうである場合には、出力ブロック８０６でＷＡＲを出力する。そうでない場合には、機能ブロック８０７で、下で説明する順序付き縮小を実行し、機能ブロック８０８で、結果の新しいグリッドを候補集合に追加する。ＷＡＲ生成処理全体は、候補集合が空になるまで継続される。
【００２１】
機能ブロック８０７の順序付き縮小は、次の形で実行される。ｎ次元を有するグリッドの場合、合計２ｎ個の縮小オプションがある、すなわち、次元１の下限を増やす、次元２の上限を減らすなどである。縮小オプションは、順序付きである。ｊが、ボックスｂに対して実行された最大のオプションであるものとする。その場合、ボックスｂは、縮小オプションｊ、ｊ＋１、…、２ｎを介して、２ｎ−ｊ＋１個のボックスに縮小される。候補セットは、ヒープ・データ構造またはキュー・データ構造のいずれかによって編成することができる。
【００２２】
ヒープは、本質的に、２進木とみなすことができる配列オブジェクトである。この木の各ノードは、ノード内の値を格納した配列の要素に対応する。木は、おそらく最下位以外のすべてのレベルで完全に満たされ、最下位レベルは、左からある点まで満たされる。木のルートは、配列の第１要素に格納される。第ｉ要素に格納されるノードの場合、その２つの直接の子が適用可能であるならば、それらの子は、配列の第（２ｉ）要素および第（２ｉ＋１）要素に格納される。ヒープは、ヒープ・プロパティも満足する、すなわち、ルート以外のすべてのノードについて、ノードの値は、多くともその親の値である。したがって、ヒープ内の最大の要素は、ルートに格納され、あるノードをルートとする部分木には、そのノード自体より小さい値が格納される。候補集合の各ボックスの体積を、メトリックとして使用して、ヒープ内の要素に順序を付ける。ボックスが追加または削除されるたびに、ヒープは、ヒープ・プロパティを維持するように再編成される。
【００２３】
図１０は、機能ブロック５０７に示された、所与のｎ項目セットＦの、その（ｎ−１）項目部分集合Ｆ'の１つへの投影カウンタの候補グリッドを決定する処理を示す図である。この処理は、ループに入り、各グリッドを順次検査する。グリッドｇのそれぞれについて、機能ブロック１００２で、対応するグリッドがｇとオーバーラップするＦ'のすべての主カウンタの総計をとる。判断ブロック１００３でテストを行って、この総計された値が、必要な密度未満であるかどうかを判定する。そうでない場合には、機能ブロック１００４で、ｇを候補グリッドとしてマークする。
【００２４】
図１１は、機能ブロック８０３に示された、ヒープＡに格納される候補集合内で最大の体積を有する候補ボックスｂを抽出する処理を示す図である。機能ブロック１１０１で、候補ボックスｂをヒープＡの最上部のヒープ要素にする。その後、Ａは、ヒープ・プロパティを維持するために再編成される。機能ブロック１１０２で、Ａの最後の要素を最上位スロットに移動し、機能ブロック１１０３で、ヒープ・サイズを１つ減らす。処理がループに入る前に、機能ブロック１１０４で、インデックスｉに１をセットする。判断ブロック１１０５のテストで、第ｉ要素の体積が、その子のいずれかより小さいかどうかを判定する。そうである場合には、機能ブロック１１０６で、第ｉ要素をそのより大きい子と交換する。機能ブロック１１０７で、インデックスｉに、この子のインデックスをセットする。この処理は、両方の子がより小さい体積を有する点に達した時に終了する。
【００２５】
図１２は、ヒープＡに格納される候補集合に新たに生成された候補ボックスの集合を挿入する処理を示す図である。この処理は、新しいボックスのそれぞれが順次挿入されるループ処理である。新しいボックスｘのそれぞれについて、機能ブロック１２０２で、ヒープ・サイズを１つ増分し、機能ブロック１２０３で、インデックスｉがヒープの最後の要素を指すようにする。処理は、判断ブロック１２０４のテスト判断から始まるループに入って、ｘの体積がヒープ内の第ｉ要素の親の体積より大きいかどうかを判定する。そうである場合には、機能ブロック１２０５で、第ｉ要素の親を第ｉ要素に移動し、機能ブロック１２０６で、インデックスｉに親要素をセットする。この処理は、その後、判断ブロック１２０４にループ・バックする。そうでない場合には、ｘを第ｉ要素に格納する。この処理全体は、すべてのボックスが挿入された後に終了する。
【００２６】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００２７】
（１）タプル・リストの集合から、各ルールが前件部分および後件部分を有する重み付き相関ルールを生成する方法であって、各タプルが、項目および関連する重みを含み、各タプル・リストが、複数のタプルを含み、前記方法が、重み付き相関ルールを生成するステップであって、ルールの後件部分が項目の第１部分集合を含み、前記ルールの前件部分が項目の第２のオーバーラップしない部分集合を含み、前記ルール内で、前記ルールの前記後件部分および前記前件部分の両方を満たすタプルの数が、サポート要件と称する事前に指定されるサポート・レベルを超え、タプルのうちで前記前件部分を満たし前記後件部分も満たす部分が、確信度要件と称する事前に指定される確信度レベルを超え、前記ルールの前記後件部分および前記前件部分の両方を満たすタプル密度が、所望の密度レベルを超えるように各項目の重みの値の範囲が前記ルール内で指定される、ステップを含む、重み付き相関ルールを生成する方法。
（２）タプル・リストの集合から重み付き相関ルールを生成する方法であって、各タプルが項目および関連する重みを含み、各タプル・リストが複数のタプルを含み、前記方法が、
複数の頻出項目セットを生成するステップと、
各頻出項目セットから、重み付き相関ルールを生成するステップであって、各ルールが、前件部分および後件部分を有し、ルールの前記後件部分が、タプル・リストからの項目の第１部分集合によって形成され、前記タプル・リストの残りのすべての項目が、前記ルールの前記前件部分を形成し、各項目の重みの値の範囲が、サポート要件、確信度要件、および密度要件が満たされるように前記ルール内で指定される、ステップと
を含む方法。
（３）すべての有資格の重み付き相関ルールが、重み付き相関ルールを生成する前記ステップで生成される、上記（２）に記載の方法。
（４）すべての有資格の重み付き相関ルールの選択された部分集合が、重み付き相関ルールを生成する前記ステップで生成される、上記（２）に記載の方法。
（５）重み付き相関ルール生成のために、所望の頻出項目セットの集合を選択するステップと、
サポート、関心、および密度を含む閾値のグループからの少なくとも１つの閾値の所望の値を選択するステップと
をさらに含む、上記（４）に記載の方法。
（６）各頻出項目セットから重み付き相関ルールを生成する前記ステップが、
各項目の重みの範囲を区間に分割することによってグリッドを生成するステップと、
各グリッド内の複数のタプルとして各グリッドの密度を判定するステップと、
密ボックスを識別するステップであって、ある密ボックスの各次元上の座標が、前記ルールの前記前件部分の対応する項目の前記重みの範囲を与える、ステップと、
前記密ボックスの確信度要件およびサポート要件を検証するステップと
を含む、上記（２）に記載の方法。
（７）グリッドを作成する前記ステップが、項目セットのサイズに無関係に、各項目セットのグリッドの一定の個数を維持する、上記（６）に記載の方法。
（８）密度に関して評価しなければならないグリッドの数を減らすために、疎グリッドを枝刈りするステップをさらに含む、上記（６）に記載の方法。
（９）密ボックスを識別する前記ステップが、
最大密度領域を識別するステップと、
前記最大密度領域を最大密度ボックスに縮小するステップと
を含む、上記（６）に記載の方法。
（１０）縮小する前記ステップが、縮小動作を実行するために、前記次元に対する特定の順序を使用する、上記（９）に記載の方法。
（１１）最大の体積を有する候補がヒープの最上部に置かれるようにするヒープ方法を使用して、追加の縮小の候補を追跡するステップをさらに含む、上記（１０）に記載の方法。
（１２）前記ヒープ方法が、
前記ヒープから最上部のボックスを除去するステップと、
前記除去されたボックスのすべての正当な縮小を生成するステップと、
確信度要件およびサポート要件の両方が満たされる場合に、新たに生成された縮小ボックスを重み付き相関ルールとして出力するステップと、
そうでない場合に、サポートが満たされない場合に、新たに生成されたボックスを破棄するステップと、
サポートが満たされる場合に、新たに生成されたボックスをヒープに戻すステップと
を含む、上記（１１）に記載の方法。
（１３）キュー方法を使用して追加の縮小の候補を追跡するステップをさらに含む、上記（１０）に記載の方法。
（１４）グリッド上で各ｎ項目集合のカウンタの２つの集合を維持するステップをさらに含み、第１集合が、前記グリッドのサポートを記録する主カウンタであり、第２集合が、それぞれが各（ｎ−１）次元空間へのグリッド投影のサポートを記録する投影カウンタの集合である、上記（６）に記載の方法。
（１５）候補カウンタ集合を枝刈りするためのレベル単位の枝刈り方法であって、
ｎ項目セットから（ｎ−１）項目セットへの投影カウンタを判定するステップと、
評価が必要なｎ項目セットの前記主カウンタを枝刈りするために、ｎ項目セットから（ｎ−１）項目セットへの前記投影カウンタを使用するステップと、
ｎ項目セットの残りの主カウンタを判定するステップと、
評価が必要なｎ項目セットへの（ｎ＋１）項目セットの投影カウンタを枝刈りするために、ｎ項目セットの前記主カウンタを使用するステップと
を含む、レベル単位の枝刈り方法が設けられる、上記（１４）に記載の方法。
（１６）頻出項目セットを生成するステップが、反復方法を使用する、上記（２）に記載の方法。
（１７）タプル・リストの集合から、各ルールが前件部分および後件部分を有する重み付き相関ルールを生成するコードを含むコンピュータ可読媒体であって、各タプルが、項目および関連する重みを含み、各タプル・リストが、複数のタプルを含み、前記コードが、重み付き相関ルールを生成するステップであって、ルールの後件部分が項目の第１部分集合を含み、前記ルールの前件部分が項目の第２のオーバーラップしない部分集合を含み、前記ルール内で、前記ルールの前記後件部分および前記前件部分の両方を満たすタプルの数が、サポート要件と称する事前に指定されるサポート・レベルを超え、タプルのうちで前記前件部分を満たし前記後件部分も満たす部分が、確信度要件と称する事前に指定される確信度レベルを超え、前記ルールの前記後件部分および前記前件部分の両方を満たすタプル密度が、所望の密度レベルを超えるように各項目の重みの値の範囲が前記ルール内で指定される、ステップを実施する、コンピュータ可読媒体。
（１８）タプル・リストの集合から重み付き相関ルールを生成するコードを含むコンピュータ可読媒体であって、各タプルが項目および関連する重みを含み、各タプル・リストが複数のタプルを含み、前記コードが、
複数の頻出項目セットを生成するステップと、
各頻出項目セットから、重み付き相関ルールを生成するステップであって、各ルールが、前件部分および後件部分を有し、ルールの前記後件部分が、タプル・リストからの項目の第１部分集合によって形成され、前記タプル・リストの残りのすべての項目が、前記ルールの前記前件部分を形成し、各項目の重みの値の範囲が、サポート要件、確信度要件、および密度要件が満たされるように前記ルール内で指定される、ステップと
を実施する、コンピュータ可読媒体。
（１９）すべての有資格の重み付き相関ルールが、重み付き相関ルールを生成する前記ステップで生成される、上記（１８）に記載のコンピュータ可読媒体。
（２０）すべての有資格の重み付き相関ルールの選択された部分集合が、重み付き相関ルールを生成する前記ステップで生成される、上記（１８）に記載のコンピュータ可読媒体。
【図面の簡単な説明】
【図１】本発明の、所与のデータ・セットからＷＡＲをマイニングする全体的な処理を示す流れ図である。
【図２】所与の項目セットについてＷＡＲを生成する処理を示す流れ図である。
【図３】所与の項目セットに関するカウンタ生成の処理を示す流れ図である。
【図４】所与の項目セットに関する主カウンタを生成する処理を示す流れ図である。
【図５】所与の項目セットに関する投影カウンタを生成する処理を示す流れ図である。
【図６】カウンタに基づいて密領域を構成する処理を示す流れ図である。
【図７】最小境界ボックス発見の処理を示す流れ図である。
【図８】最小境界ボックスからのＷＡＲ生成処理を示す流れ図である。
【図９】頻出項目セット生成処理を示す流れ図である。
【図１０】所与の項目セットの投影カウンタの候補グリッドを決定する処理を示す流れ図である。
【図１１】ヒープ構造を介して維持される候補集合から最大の体積を有する候補ボックスを抽出する処理を示す流れ図である。
【図１２】ヒープ構造を介して維持される候補集合に新しいボックスを挿入する処理を示す流れ図である。
【符号の説明】
１０１  機能ブロック
１０３  判断ブロック
１０４  判断ブロック
１０５  機能ブロック
１０６  機能ブロック
１０７  機能ブロック
２０１  機能ブロック
２０２  機能ブロック
２０３  機能ブロック
２０４  機能ブロック
２０５  機能ブロック
３０１  機能ブロック
３０２  判断ブロック
３０３  機能ブロック
３０４  機能ブロック
３０５  判断ブロック
３０６  機能ブロック
４０１  機能ブロック
４０３  判断ブロック
４０４  機能ブロック
５０１  機能ブロック
５０２  判断ブロック
５０３  機能ブロック
５０４  機能ブロック
５０５  判断ブロック
５０７  機能ブロック
５０８  機能ブロック
５０９  機能ブロック
６０１  判断ブロック
６０２  機能ブロック
６０３  機能ブロック
６０４  判断ブロック
６０５  機能ブロック
７０１  機能ブロック
７０２  機能ブロック
７０３  判断ブロック
７０４  機能ブロック
８０１  機能ブロック
８０２  判断ブロック
８０３  機能ブロック
８０４  判断ブロック
８０５  判断ブロック
８０６  出力ブロック
８０７  機能ブロック
８０８  機能ブロック
９０１  機能ブロック
９０２  判断ブロック
９０３  機能ブロック
９０４  機能ブロック
９０５  機能ブロック
１００２  機能ブロック
１００３  判断ブロック
１００４  機能ブロック
１１０１  機能ブロック
１１０２  機能ブロック
１１０３  機能ブロック
１１０４  機能ブロック
１１０５  判断ブロック
１１０６  機能ブロック
１１０７  機能ブロック
１２０２  機能ブロック
１２０３  機能ブロック
１２０４  判断ブロック
１２０５  機能ブロック
１２０６  機能ブロック
【図１】
0004056223.tif 000002
【図２】
0004056223.tif 000003
【図３】
0004056223.tif 000004
【図４】
0004056223.tif 000005
【図５】
0004056223.tif 000006
【図６】
0004056223.tif 000007
【図７】
0004056223.tif 000008
【図８】
0004056223.tif 000009
【図９】
0004056223.tif 000010
【図１０】
0004056223.tif 000011
【図１１】
0004056223.tif 000012
【図１２】
0004056223.tif 000013