JPH11328186A - 相関ルール生成方法および相関ルール生成装置 - Google Patents

Abstract

(57)【要約】 【課題】 データベースからの相関ルール抽出におい
て、統計的に意味のある相関ルールを、負の相関も含め
て効率的に抽出することを可能にする。 【解決手段】 候補品目セット生成部２２が、相関ルー
ルの左辺または右辺の候補である１以上の品目からなる
候補品目セットを生成し、候補品目セット検証部２１が
候補品目セットからデータベース１内での出現数が最小
支持度以上のものを大品目セット２として選択する。ル
ール候補生成部４１が長さＫ−１の大品目セットと長さ
１の大品目セットから相関ルール候補を生成し、χ² 検
定部４３が相関ルール候補からχ² 値と有意水準を指標
としたχ² 検定により、相関ルール集合３を生成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はデータ処理システム
に関し、特にデータベース中の未発見の規則性を発見す
るデータマイニング及びそのアルゴリズムにおける、ハ
ッシュ木操作に関するものである。

【０００２】

【従来の技術】大規模データベースから知識発見を行う
データマイニングで抽出される知識については、相関ル
ールと呼ばれる、同一レコード中に現れ易い品目の集合
に関する知識がよく知られている。代表的な応用例では
小売業における顧客の購買記録、あるいはレシート等の
集積から相関ルールを抽出して同時購買の傾向を調べ、
ある商品の売り上げを伸ばすために、これと同時に買わ
れ易い商品を特売品にする等の戦略立案に役立てること
が挙げられる。ここでのレコードとは各顧客毎の購買品
目のリストである。

【０００３】このような一つのレコードに品目の集合が
並ぶデータベースからの相関ルール抽出の手法として
は、R.Agrawalらによる“Apriori”と呼ばれるものがあ
り、文献「Fast Algorithms for Mining Association R
ules」（Proc. of 20th VLDB，1994）、特開平８−２８
７１０６に詳述されている。ここでは相関ルール抽出は
支持度と確信度の２つの指標を基準としていた。例え
ば、 Ａ，Ｂ，・・・，Ｘ→Ｙ という相関ルール、すなわち品目Ａ，Ｂ，・・・，Ｘを
含むレコードと、さらに品目Ｙも含むレコードの間には
相関があるというルールの場合、Ａ，Ｂ，・・，Ｘ，Ｙ
の全てを含むレコードの数がこの相関ルールの支持度、
Ａ，Ｂ，・・，Ｘを含むレコードの中での、さらにＹも
含むレコードの割合を確信度と呼ぶ。この手法では二つ
の指標があらかじめ設定された各々の下限値（最小支持
度、最小確信度）を超える相関ルールを抽出していた。

【０００４】このApriori は、図３０に示すシステム
図、図３１に示すブロック図によって実現することがで
きる。以下図３１に従ってこの手法の手順を説明する。
なお、以下の説明では問題を単純化するために、図３３
に示す様なデータベースからの相関ルール抽出を想定す
る。すなわち、各レコードがレコードＩＤと、１以上の
任意の整数によって表現された品目の集まりとからなる
データベースである。

【０００５】以後、ｋ個の品目の集まりをｋ項組と呼
び、最小支持度以上のｋ項組を要素とする集合を長さｋ
の大品目セットＬｋと呼ぶ。また、大品目セットＬｋの
要素の候補であるｋ項組を要素とする集合を長さｋの候
補品目セットＣｋと呼び、Ｃｋの要素中、最小支持度以
上のｋ項組がＬｋの要素として選択される。ただし、ｋ
は２以上の整数である。

【０００６】図３１において、最初のステップ１００、
ユーザ入力では、ユーザ入力部１０がユーザから最小支
持度、最小確信度を獲得する。次のステップ１１０、Ｌ
１生成では、候補品目セット検証部２１が、データベー
ス中のレコードを一つずつ取り出して、そのレコード中
に出現する各品目について、出現する回数をカウント
し、そのカウント数（支持度）を増やす。初めて出現す
る品目については、そのカウントの領域を新たに設け
る。そして、全てのレコードについて数え上げが終了す
ると、最終的な支持度が最小支持度を超えた品目につい
て、ハッシュ木に登録を行う。１，２，３，４，５の５
つの品目の支持度が最小支持度を超えた場合について、
これらを登録した状態のハッシュ木を図３４に示す。ハ
ッシュ木の各枝の両端はノードと呼ばれ、一般に品目番
号が対応付けられるが、ハッシュ木の始点のみは品目が
対応付けられないノードで、ｒｏｏｔと呼ばれる。また
ｒｏｏｔからハッシュ木の末端のノードまでの枝の数を
枝の長さと呼ぶ。図３４のハッシュ木の各枝の長さは１
である。

【０００７】次のステップ１２０、Ｃｋ生成では候補品
目セット生成部２２が長さｋ−１の大品目セットＬｋ−
１から候補品目セットＣｋを生成する。図３４に示した
初期状態ではｋ＝２であり、Ｌ１からＣ２が生成され
る。ここではＬ２からＣ３が生成される場合の例を説明
する。図３５にＬ２まで作成された状態のハッシュ木の
例を示す。このＣｋ生成のステップの内部は図３２のブ
ロック図の様な２段階になっており、各々はｊｏｉｎス
テップ、ｐｒｕｎｅステップと呼ばれる。

【０００８】まず、ステップ１２１のｊｏｉｎステップ
について説明する。ここでは、長さｋ−１まで伸びた枝
の１つのノードについて、同じ親ノードを持ち、かつ末
端のノードの品目番号がそのノードの品目番号より大き
い他のノードの末端の品目をそのノードの子ノードとし
て追加して、枝を伸ばす。図３５のｒｏｏｔ→１→３で
示されるノード（これを［１，３］と表記することに
し、以降の説明では、ハッシュ木のノードを同様な記述
で表す）には、同じ親ノードを持ちかつ末端のノードの
品目番号が３より大きい［１，４］と［１，５］と結合
し、それぞれ［１，３，４］と［１，３，５］を設け
る。［１，４］についても［１，５］と結合し、［１，
４，５］が設けられる。［１，５］については５より大
きな品目番号を持つノードが［１］より下にないので、
枝は伸ばされない。この状態を図３６（１）ｐｒｕｎｅ
前の図に示す。

【０００９】次のステップ１２２のｐｒｕｎｅステップ
について説明する。ここでは、前のｊｏｉｎステップで
長さｋまで伸ばされた枝の該当する品目セットに関し
て、それから一つの品目を除いてできるｋ−１項組み全
てについて、それがＬｋ−１に属するかの検査を行い、
全てのｋ−１項組がＬｋ−１に属する場合のみ採用し、
１つでもＬｋ−１に属さないｋ−１項組がある場合は削
除する。例えば［１，３，４］の検査を行う場合では、
［１，３］、［１，４］、［３，４］のつの項組みがＬ
に存在するか調べられる。図３６の例ではいずれもＬに
含まれるのでこの項組みは残される。［１，３，５］の
検査を行う場合では、［１，３］、［３，５］、［１，
５］がＬに存在するかどうか調べられるが、［３，５］
は存在しないので、この項組みは削除される。以上の様
にして、このｐｒｕｎｅステップではｊｏｉｎによって
できた全てのｋ項組みが検査される。ｐｒｕｎｅ後のハ
ッシュ木を図３６（２）ｐｒｕｎｅ後の図に示す。

【００１０】Ｃｋ生成ステップの後は、ステップ１３０
のＬｋ生成のステップが候補品目セット検証部２１によ
って行われる。ここではデータベースのレコードが一件
ずつ取り出され、その中に存在するＣｋ中のｋ項組みの
カウントを増やす操作が行われ、最終的に最小支持度を
超えたｋ項組みのみをＬｋの要素として残す。このｋ項
組のカウントのためにレコードとハッシュ木の照合（マ
ッチング）が行われる。このマッチングは、まず、ハッ
シュ木のｒｏｏｔにおいてデータベースのレコードが一
件ずつ取り出され、各レコード中にｒｏｏｔの子ノード
の品目が存在するかどうか検査する。存在しなければそ
のレコードについてのマッチングは終了し、次のレコー
ドを検査する。存在すれば、その品目が対応付けられて
いる子ノードにおいて、さらに次の子ノード（ｒｏｏｔ
から見ると“孫”）に対応付けられている品目がこのレ
コード中に存在するかどうかを検査する。以後この操作
を繰り返すが、適用されるノードの子ノードがそれ以下
に枝を持たないノード、すなわち葉であり、なおかつそ
のレコード中に葉であるその子ノードに対応している品
目が存在する場合はこの葉ノードの支持度集計用カウン
トを増やす操作を行い、このレコードについてのマッチ
ングを終了する。すべてのレコードについてマッチング
が終了したときの各葉ノードの支持度集計用カウントの
値が、各ｋ項組（ｒｏｏｔからその葉ノードにいたるま
での品目の組）の支持度である。このようにして各ｋ項
組の支持度をカウントし、最小支持度以上の支持度をも
つｋ項組をすべて要素として選択した大品目セットＬｋ
を生成する。

【００１１】Ｌｋ生成のステップでＬｋの要素となるｋ
項組みが一つも生成されなかった場合はステップ１５０
のルール候補生成に進み、そうでない場合はｋの値を一
つ増やし、Ｃｋ生成のステップに戻る。

【００１２】ステップ１５０のルール候補生成ではルー
ル候補生成部４１により、それまでのステップで作成さ
れた大品目セットよりルールの候補が作られる。Ｌｋ中
のあるｋ項組みからは、右辺にその中の一つの品目、左
辺に残りのｋ−１個の品目がくる計ｋ個のルール候補が
生成される。これが、ｋ＝２以上の全てのＬｋのｋ項組
みについて成される。この例では、右辺は、相関ルール
の結果となる品目のセットを意味し、左辺は、相関ルー
ルの条件となる品目のセットを意味している。尚、相関
ルール候補の場合にも同様に、右辺は、結果となる品目
のセットを意味し、左辺は、条件となる品目のセットを
意味している。

【００１３】ステップ１６０のルール検証では、確信度
計算部４２により各ルール候補の確信度が計算され、そ
れが最小確信度を上回る場合には相関ルール集合に追加
される。ここで、すでに述べたように、ルール候補のＡ
１，Ａ２，・・・Ａｋ→Ｂの確信度（ｃｏｎｆｉｄｅｎ
ｃｅ）は、品目セットθの支持度をｓ（θ）とすると、
confidence=s(A1,A2,・・・Ak,B)/s(A1,A2,・・・Ak)と計算さ
れる。

【００１４】以上説明したApriori を改良した従来技術
としてR.Srikant 他の提案があり、文献「Mining Gener
alized Association Rules」（Proc. of 21th VLDB，19
95）に記述されている。この方法は、（１）Apriori に
よる相関ルールの抽出、（２）（１）で得られた相関ル
ールよりχ² 検定により統計的に意味のないルールを除
去という手順で、確信度が最小確信度を超えているだけ
でなく、さらに統計的に意味のあるルールを抽出する。

【００１５】また、以上の説明で分かる様に、このアル
ゴリズムでは品目セットを格納するハッシュ木の操作が
極めて重要である。品目の種類が多い場合には全体の品
目セットの数は膨大なものとなり、ハッシュ木が計算機
のメモリの領域に収まりきらなくなる。この様な状況で
はレコードとハッシュ木のマッチングを行う際に頻繁に
ハッシュ木のノードのデータのページングが起こり、処
理速度が大幅に落ちるという問題があった。

【００１６】さらに、Ｌｋ生成ステップにおける支持度
の集計では、データベースのレコードを一つずつ取り出
し、各々のレコードに対してハッシュ木とのマッチング
をとる処理を適用していた。一つのレコードとハッシュ
木のマッチング処理は、マッチング関数を再帰的に呼ぶ
ことによって実現する。図５６に示すようにマッチング
関数には、ハッシュ木のノード（ｎｏｄｅ）とレコード
の部分列（ｐ）を引数として入力する。第２の引数であ
る部分列は、レコード上のある位置以降の品目の集合で
ある。例えば、｛１，２，３｝からなるレコードの２番
目の位置以降の部分列は｛２，３｝と表す。

【００１７】図５６に従来のマッチング関数のブロック
図を示す。ステップ２１００で入力されたハッシュ木の
ノード（ｎｏｄｅ）が葉ノードの一つ上であるか否か判
断する。葉ノードの一つ上でない場合は、ステップ２１
１０で部分列の最初の品目（ｉ）にハッシュ関数を適用
して該当するノード（ｎｏｄｅｉ）が下に存在するか調
べる。ステップ２１１０で該当するノード（ｎｏｄｅ
ｉ）が下に存在した場合は、ステップ２１２０でそのノ
ード（ｎｏｄｅｉ）と部分列（ｐ）からそのノードの品
目（ｉ）を除いた部分列を入力としてマッチング関数を
再帰的に呼び出す。そしてステップ２１３０で元の部分
列（ｐ）からも該当ノードの品目（ｉ）を除くことによ
り、部分列（ｐ）を更新する。ステップ２１１０で該当
するノード（ｎｏｄｅｉ）が下に存在しない場合には、
マッチング関数を再帰的に呼び出すことなく、ステップ
２１３０で部分列の更新のみを行なう。ステップ２１４
０で部分列（ｐ）に品目がないと判断するまで、つまり
元の部分列の品目がなくなるまで、ステップ２１１０か
らステップ２１３０の処理を繰り返す。ステップ２１０
０で入力されたハッシュ木のノード（ｎｏｄｅ）が葉ノ
ードの一つ上であると判断する場合は、ステップ２１５
０で引数の部分列（ｐ）中の各品目（ｉ）についてハッ
シュ関数を適用する。該当する葉ノード（ｎｏｄｅｉ）
が存在すれば、そのノードの支持度を一つ増やす。

【００１８】図５７の例で、ハッシュ木のｒｏｏｔ、レ
コード｛１，２，３｝の部分列｛１，２，３｝にマッチ
ング関数が適用する場合について説明する。ハッシュ木
の高さは２であるので、マッチング関数を再帰的に呼び
出す。ｒｏｏｔの下には［１］が存在するので、ステッ
プ２１００、２１１０を経て、ステップ２１２０で最初
にノード［１］、部分列｛２，３｝を入力とするマッチ
ング関数を再帰的に呼び出す。ステップ２１３０で部分
列は｛２，３｝に更新する。同じくステップ２１００、
２１１０を経て、ステップ２１２０でノード［２］、部
分列｛３｝を入力とするマッチング関数を再帰的に呼び
出す。ステップ２１３０で部分列は｛３｝に更新する。
同じくステップ２１００、２１１０を経て、ステップ２
１２０でノード［３］、部分列｛｝を入力としたマッチ
ング関数を再帰的に呼び出す。ステップ２１３０で部分
列は｛｝となる。ステップ２１４０で部分列に品目はな
いので、処理のループはここで終了する。次に、再帰的
に呼び出されたノード［１］と部分列｛２，３｝を入力
としたマッチング関数の動作について説明する。ステッ
プ２１００で、このノードは葉の一つ上のノードである
と判断し、ステップ２１５０で部分列中の品目２，３の
各々についてハッシュ関数を適用する。ステップ２１６
０で該当するノード［１，２］と［１，３］への枝を確
認し、ステップ２１７０でそれぞれのノードの支持度を
一つ増やす。同様に再帰的に呼び出されたノード［２］
と部分列｛３｝を入力としたマッチング関数では、
［２，３］のノードの支持度を一つ増やす。再帰的に呼
び出されたノード［３］と部分列｛｝を入力としたマッ
チング関数では、支持度を増やすこと無く終了し、一連
の処理を終了する。

【００１９】

【発明が解決しようとする課題】また従来技術では、最
小支持度を満たす大品目セットを基にして相関ルールの
候補を生成していたため、ルールの両辺の全ての品目か
らなる大品目セットの支持度が小さいルールの抽出はで
きない。従って「ある品目とある品目は同一レコード中
に現れにくい」という傾向を示す負の相関ルールを抽出
することができなかった。この負の相関ルールはデータ
ベースによっては正の相関と同じ位重要な情報を示すこ
とがある。例えばある機器のメンテナンスデータからの
「処置Ａを施した機器は、故障Ｂが起こりにくい」とい
った知識、ある生産物の製造データからの「材料Ｃを使
った製品は、不良Ｄが出にくい」といった知識は負の相
関ルール抽出によって得られる。負の相関ルールは両辺
の品目セットの支持度が非常に低いので、大品目セット
のみからでは得られない。つまり、従来技術ではルール
の右辺、左辺は最小支持度を満たすが両辺はそうでな
い、統計的に意味のあるルールを抽出することができな
かった。

【００２０】従来技術であるApriori は最小確信度を基
準とした相関ルールの抽出を行っており、得られるルー
ルは統計的に意味のないものも多く含まれており、従っ
てルールの品質が良くなかった。また、もう一つのSrik
ant による従来技術はApriori によって得られた結果か
ら、χ² 検定によって統計的に意味のないルールを除去
しているので、Apriori に比べて処理負荷が大きかっ
た。そして、統計的に意味があり、χ² 検定では意味の
あるルールと判定されるはずであるが、確信度が最小確
信度より小さいために抽出されないルールも存在した。

【００２１】また従来技術では、効率的に正の相関ルー
ルと負の相関ルールを分けて抽出することができなかっ
た。

【００２２】また従来技術では、ユーザが最小支持度を
入力する必要が有り、また不要な支持度をもつルール候
補に関して検定を行うことが有ったので効率的に相関ル
ールを抽出することができなかった。

【００２３】また従来技術では、例えば「右辺に２また
は４を含み、左辺に１または３を含むルール」の様な左
辺、右辺に出てくる品目の候補を指定して、右辺、左辺
の各々で候補の内どれかを含む相関ルール抽出を効率的
に行う手段がないため、全ステップが終わってから該当
する相関ルールを抜き出すしかなく、無駄な処理を多く
含むことになった。

【００２４】また従来技術では、例えば「右辺が１と４
を含み、左辺に必ず２を含むルール」の様な左辺、右辺
に必ず出てくる品目を指定して、それらの品目を右辺、
左辺の各々で全ての必須品目を含む相関ルールの抽出を
効率的に行う段がないため、全ステップが終わってから
該当する相関ルールを抜き出すしかなく、無駄な処理を
多く含むことになった。

【００２５】また従来技術では、「品目３を含むレコー
ドのみに限定した相関ルール抽出」といった、データベ
ース中で対象のドメインを限定した相関ルール抽出を行
うことができなかった。

【００２６】また従来技術では、各品目に対応する整数
等の番号の付与はデータベース中のその品目の支持度に
関係なく行われていたため、ハッシュ木上の各ノードに
おけるハッシュテーブルの大きさが不定で、ハッシュ関
数も煩雑にならざるを得なかった。

【００２７】また従来技術では、各レコードとハッシュ
木のマッチングを、レコード中の品目による全ての組み
合わせとハッシュ木を突き合わせて行っていいたため、
レコード長が長い場合にはその効率が大幅に低下すると
いう問題があった。

【００２８】また従来技術では、例えば「相関ルール中
に、２と４が同時に出ないで欲しい」といった、要求が
あった場合には全ステップが終わってから該当する相関
ルール（例の場合は２と４を同時に含む相関ルール）を
削除するしかなく、無駄な処理を多く含むことになっ
た。この様な要求が発生する理由としては、例えばある
小売店の顧客の購買記録データにおいて、性別の「男」
と「女」を品目として含んでいるとすると、「男ならば
女ではない」という意味のない負の相関ルールが抽出さ
れてしまうこと等が挙げられる。また正の相関ルール抽
出においても、男と女による２項組みを候補品目セット
に入れて、データベースの検索によって検証するという
無駄な動作を実行することになる。

【００２９】また従来技術では、ハッシュ木が大きくな
りメモリにおさまりきらなくなると、レコードとハッシ
ュ木のマッチングを行う際に頻繁にハッシュ木のノード
データのページングが起こり、処理速度が大幅に落ちる
という問題があった。特に、木に偏りがある場合には木
を分割しても分割後の木がメモリの容量を超え、ページ
ングを起こす可能性があった。

【００３０】また従来技術では、ルール生成ステップに
おいて、データベース検索を行なう必要であり、処理が
遅かった。

【００３１】また従来技術では、候補品目セットの数が
多く、処理が遅かった。

【００３２】また従来技術では、Ｌｋ生成ステップにお
ける支持度の集計では、データベースのレコードを一つ
ずつ取り出し、各々のレコードに対してハッシュ木との
マッチングをとる処理を適用していたため、マッチング
関数の再帰的呼び出しの処理回数が多く、マッチング処
理が遅かった。

【００３３】

【課題を解決するための手段】本発明の相関ルール生成
方法は、１以上の品目からなる複数のレコードを記憶し
たデータベース内から、１以上の品目からなる品目集合
間の相関ルールを抽出する相関ルール生成方法であり、
ｋを２以上の整数とし、品目数Ｎからなる集合であっ
て、このＮ個の品目をすべて含むレコードの数である支
持度が未確認である集合を候補品目セットＣ（Ｎ）と
し、該候補品目セットＣ（Ｎ）の中で支持度が所定の下
限値Ｓｍｉｎ以上のものを大品目セットＬ（Ｎ）とし
て、下記（ａ）（ｂ）（ｃ）のステップを含むことを特
徴とする相関ルール生成方法である。 （ａ）相関ルールの抽出に必要なパラメータを入力する
ユーザ入力ステップ； （ｂ）下記（ｂ１）（ｂ２）（ｂ３）のステップからな
る大品目セット生成ステップ； （ｂ１）各個別の品目を含むレコードの数である支持度
をカウントし、この支持度が上記下限値Ｓｍｉｎ以上で
ある品目の集合を大品目セットＬ（１）と設定するＬ１
生成ステップ； （ｂ２）大品目セットＬ（ｋ−１）と上記大品目セット
Ｌ（１）から候補品目セットＣ（ｋ）を生成するＣｋ生
成ステップ； （ｂ３）上記候補品目セットＣ（ｋ）から大品目セット
Ｌ（ｋ）を選択するＬｋ生成ステップ； （ｃ）下記（ｃ１）（ｃ２）のステップからなる仮説生
成検証ステップ； （ｃ１）大品目セットＬ（ｋ−１）と上記大品目セット
Ｌ（１）から、大品目セットＬ（ｋ−１）を条件となる
品目セット、大品目セットＬ（１）を結果となる品目セ
ットとする相関ルール候補を生成するルール候補生成ス
テップ； （ｃ２）上記相関ルール候補について、相関ルールとし
て採用するか棄却するかを判定するルール検定ステッ
プ。

【００３４】本発明の相関ルール生成方法は、上記ユー
ザ入力ステップは、ユーザが少なくとも上記χ² 検定に
おける有意水準を入力し、上記ルール検定ステップは、
左辺の支持度、右辺の支持度、左辺と右辺の両方に含ま
れる品目からなる品目セットの支持度、およびレコード
総数からχ² 値を算出し、このχ² 値と上記有意水準を
指標としてχ² 検定を行うことを特徴とする相関ルール
生成方法である。

【００３５】本発明の相関ルール生成方法は、上記仮説
生成検証ステップで、相関ルールが正の相関ルールか負
の相関ルールかを判定する正負判定ステップを備えたこ
とを特徴とする相関ルール生成方法である。

【００３６】本発明の相関ルール生成方法は、上記大品
目セット生成ステップが、個別の品目の支持度から上記
支持度の下限値Ｓｍｉｎを算出する相関用限界支持度決
定ステップを備えたことを特徴とする相関ルール生成方
法である。

【００３７】本発明の相関ルール生成方法は、上記大品
目セット生成ステップが、支持度の最も小さな個別の品
目の支持度を上記支持度の下限値Ｓｍｉｎと設定する最
小支持度決定ステップを備えたことを特徴とする相関ル
ール生成方法である。

【００３８】本発明の相関ルール生成方法は、上記仮説
生成検証ステップが、ルール候補生成ステップで相関ル
ール候補を生成する際に使用した大品目セットＬ（ｋ−
１）と大品目セットＬ（１）の対に対して、該大品目セ
ットＬ（ｋ−１）の支持度から該大品目セットＬ（１）
の支持度の限界値を算出する境界決定ステップを備え、
上記ルール検定ステップが、支持度が境界以内である大
品目セットＬ（１）とこれと対の大品目セットＬ（ｋ−
１）から生成された相関ルール候補のみのχ²検定を行
うことを特徴とする相関ルール生成方法である。

【００３９】本発明の相関ルール生成方法は、上記ユー
ザ入力ステップが、ユーザが少なくとも相関ルールの左
辺または右辺の品目に関する条件を入力することを特徴
とする相関ルール生成方法である。

【００４０】本発明の相関ルール生成方法は、上記ユー
ザ入力ステップで、ユーザが相関ルール中の左辺にその
中の１個以上が必ず含まれる１個以上の品目と相関ルー
ル中の右辺にその中の１個以上が必ず含まれる１個以上
の品目を条件として入力することを特徴とする相関ルー
ル生成方法である。

【００４１】本発明の相関ルール生成方法は、上記ユー
ザ入力ステップで、ユーザが相関ルール中の左辺にすべ
てが必ず含まれる１個以上の品目と相関ルール中の右辺
にすべてが必ず含まれる１個以上の品目を条件として入
力することを特徴とする相関ルール生成方法である。

【００４２】本発明の相関ルール生成方法は、上記ユー
ザ入力ステップで、ユーザがデータベース中のレコード
の中から、特定の１以上の品目を持つレコードの集合で
あるドメインを指定するために上記１以上の品目を入力
し、大品目セット生成ステップが、データベースから指
定された上記ドメインに含まれるレコードのみを取り出
し、以後データベース中のレコード総数の代わりにこの
ドメインに含まれるレコードの総数を使用するようにす
るドメイン限定ステップを備えたことを特徴とする相関
ルール生成方法である。

【００４３】本発明の相関ルール生成方法は、上記大品
目セット生成ステップが、各品目の支持度の順に各個別
の品目に対し品目番号を付ける品目番号再配置ステップ
を備えたことを特徴とする相関ルール生成方法である。

【００４４】本発明の相関ルール生成方法は、上記大品
目セット生成ステップが、上記候補品目セットＣ（ｋ）
を格納するハッシュ木中のｋ項組みを一つずつ取り出し
て、レコードとのマッチングを行う逆方向レコードマッ
チングステップを備えることを特徴とする相関ルール生
成方法である。

【００４５】本発明の相関ルール生成方法は、上記ユー
ザ入力ステップで、ユーザが相関ルール中に同時に現れ
てはならない２個以上の品目からなる組を指定し、Ｌｋ
生成ステップが、この指定された組に含まれる複数の品
目を同時には含まない大品目セットＬ（ｋ）のみを生成
することを特徴とする相関ルール生成方法である。

【００４６】本発明の相関ルール生成方法は、１以上の
品目からなる複数のレコードを記憶したデータベース内
から、１以上の品目からなる品目集合間の相関ルールを
抽出する相関ルール生成方法であり、ｋを２以上の整数
とし、品目数Ｎからなる集合であって、このＮ個の品目
をすべて含むレコードの数である支持度が未確認である
集合を候補品目セットＣ（Ｎ）とし、該候補品目セット
Ｃ（Ｎ）の中で支持度が所定の下限値Ｓｍｉｎ以上のも
のを大品目セットＬ（Ｎ）として、下記（ａ）から
（ｆ）のステップを含むことを特徴とする相関ルール生
成方法である。 （ａ）各個別の品目を含むレコードの数である支持度を
カウントし、この支持度が上記下限値Ｓｍｉｎ以上であ
る品目の集合を大品目セットＬ（１）と設定するＬ１生
成ステップ； （ｂ）大品目セットＬ（ｋ−１）を格納しているハッシ
ュ木の枝を伸ばし、候補品目セットＣ（ｋ）を生成する
Ｃｋ生成ステップ； （ｃ）ハッシュ木を、所定の容量以内の部分木に分割す
るハッシュ木分割ステップ； （ｄ）上記分割された部分木毎にデータベースとのマッ
チングを行い、大品目セットＬ（ｋ）を選択するＬｋ生
成ステップ； （ｅ）相関ルール候補を生成するルール候補生成ステッ
プ； （ｆ）上記相関ルール候補について相関ルールとして採
用するか棄却するかを判定するルール検定ステップ。

【００４７】本発明の相関ルール生成方法は、上記Ｌ１
生成ステップが、上記下限値Ｓｍｉｎ以上である品目に
任意の連続番号を割り当て、Ｃｋ生成ステップとＬｋ生
成ステップとルール候補生成ステップとルール検定ステ
ップは、各ステップの処理を上記分割された部分木毎に
実行することを特徴とする相関ルール生成方法である。

【００４８】本発明の相関ルール生成方法は、１以上の
品目からなる複数のレコードを記憶したデータベース内
から、１以上の品目からなる品目集合間の相関ルールを
抽出する相関ルール生成方法であり、ｋを２以上の整数
とし、品目数Ｎからなる集合であって、このＮ個の品目
をすべて含むレコードの数である支持度が未確認である
集合を候補品目セットＣ（Ｎ）とし、該候補品目セット
Ｃ（Ｎ）の中で支持度が所定の下限値Ｓｍｉｎ以上のも
のを大品目セットＬ（Ｎ）とし、計算機上の相関ルール
生成のために使用可能なメモリ容量を使用許容容量と
し、上記大品目セットＬ（Ｎ）の情報を保存する大品目
セットファイルを使用して、下記（ａ）から（ｆ）のス
テップを含むことを特徴とする相関ルール生成方法であ
る。 （ａ）各個別の品目を含むレコードの数である支持度を
カウントし、この支持度が上記下限値Ｓｍｉｎ以上であ
る品目の集合を大品目セットＬ（１）と設定し、該各品
目に任意の連続番号を割り当てた後、大品目セットＬ
（１）の情報を大品目セットファイルに保存するＬ１生
成ステップ； （ｂ）大品目セットファイルから大品目セットＬ（ｋ−
１）中のｋ−１項組の情報を読み込み、ハッシュ木に格
納する、大品目セットファイル読み込みステップ； （ｃ）上記ハッシュ木の枝を伸ばして、候補品目セット
Ｃ（ｋ）を生成するＣｋ生成ステップ； （ｄ）候補品目セットＣ（ｋ）を格納しているハッシュ
木の容量を使用許容容量を超えない所定の容量と比較し
て、ハッシュ木の容量の方が小さい場合は上記大品目セ
ットファイル読み込みステップに戻り、そうでない場合
は次ステップに進む容量判定ステップ； （ｅ）上記候補品目セットＣ（ｋ）とデータベースとの
マッチングを行い、大品目セットＬ（ｋ）を選択するＬ
ｋ生成ステップ； （ｆ）相関ルール候補を生成し、相関ルールとして採用
するか棄却するかを判定するルール生成ステップ。

【００４９】本発明の相関ルール生成方法は、上記ルー
ル生成ステップが、ｋ−１項組の支持度を大品目セット
ファイルから読み出すことを特徴とする相関ルール生成
方法である。

【００５０】本発明の相関ルール生成方法は、上記大品
目セットファイル読み込みステップが、ｋ−１項組中の
最後尾の品目以外の品目が全て共通する品目セットを同
時に読み込み、それらを同一のハッシュ木に格納するこ
とを特徴とする相関ルール生成方法である。

【００５１】本発明の相関ルール生成方法は、１以上の
品目からなる複数のレコードを記憶したデータベース内
から、１以上の品目からなる品目集合間の相関ルールを
抽出する相関ルール生成方法であり、ｋを２以上の整数
とし、品目数Ｎからなる集合であって、このＮ個の品目
をすべて含むレコードの数である支持度が未確認である
集合を候補品目セットＣ（Ｎ）とし、該候補品目セット
Ｃ（Ｎ）の中で支持度が所定の下限値Ｓｍｉｎ以上のも
のを大品目セットＬ（Ｎ）として、下記（ａ）から
（ｅ）のステップを含むことを特徴とする相関ルール生
成方法である。 （ａ）各個別の品目を含むレコードの数である支持度を
カウントし、この支持度が上記下限値Ｓｍｉｎ以上であ
る品目の集合を大品目セットＬ（１）と設定するＬ１生
成ステップ； （ｂ）候補品目セットＣ（ｋ）を生成するＣｋ生成ステ
ップ； （ｃ）データベースのレコードの集合と候補品目セット
Ｃ（ｋ）を格納するハッシュ木を入力としてマッチング
を実行し、大品目セットＬ（ｋ）を選択するＬｋ生成ス
テップ； （ｄ）相関ルール候補を生成するルール候補生成ステッ
プ； （ｅ）上記相関ルール候補について相関ルールとして採
用するか棄却するかを判定するルール検定ステップ。

【００５２】本発明の相関ルール生成装置は、以下の要
素を備えることを特徴とする１以上の品目からなる品目
集合間の相関ルールを抽出する相関ルール生成装置であ
る。 （ａ）１以上の品目からなる複数のレコードを記憶した
データベース、（ｂ）相関ルールの抽出に必要なパラメ
ータを入力するユーザ入力部、（ｃ）品目数Ｎからなる
集合であって、このＮ個の品目をすべて含むレコードの
数である支持度が未確認である集合を候補品目セットＣ
（Ｎ）とし、該候補品目セットＣ（Ｎ）の中で支持度が
所定の下限値Ｓｍｉｎ以上のものである大品目セットＬ
（Ｎ）を記憶する領域、（ｄ）以下の処理部を有する大
品目セット生成部、（ｄ１）各個別の品目を含むレコー
ドの数である支持度をカウントし、この支持度が上記下
限値Ｓｍｉｎ以上である品目の集合を大品目セットＬ
（１）と設定する候補品目セット検証部、（ｄ２）ｋを
２以上の整数とし、大品目セットＬ（ｋ−１）と上記大
品目セットＬ（１）から候補品目セットＣ（ｋ）を生成
する候補品目セット生成部、（ｄ３）上記候補品目セッ
トＣ（ｋ）から大品目セットＬ（ｋ）を選択する候補品
目セット検証部、（ｅ）以下の処理部を有する仮説生成
検証部、（ｅ１）大品目セットＬ（ｋ−１）と上記大品
目セットＬ（１）から、大品目セットＬ（ｋ−１）を条
件となる品目セット、大品目セットＬ（１）を結果とな
る品目セットとする相関ルール候補を生成するルール候
補生成部、（ｅ２）上記相関ルール候補について、相関
ルールとして採用するか棄却するかを判定するルール検
定部。

【００５３】本発明の相関ルール生成装置は、以下の要
素を備えることを特徴とする１以上の品目からなる品目
集合間の相関ルールを抽出する相関ルール生成装置であ
る。 （ａ）１以上の品目からなる複数のレコードを記憶した
データベース、（ｂ）品目数Ｎからなる集合であって、
このＮ個の品目をすべて含むレコードの数である支持度
が未確認である集合を候補品目セットＣ（Ｎ）とし、該
候補品目セットＣ（Ｎ）の中で支持度が所定の下限値Ｓ
ｍｉｎ以上のものである大品目セットＬ（Ｎ）を記憶す
る領域、（ｃ）以下の処理部を有する大品目セット生成
部、（ｃ１）各個別の品目を含むレコードの数である支
持度をカウントし、この支持度が上記下限値Ｓｍｉｎ以
上である品目の集合を大品目セットＬ（１）と設定する
候補品目セット検証部、（ｃ２）ｋを２以上の整数と
し、大品目セットＬ（ｋ−１）を格納しているハッシュ
木の枝を伸ばし、候補品目セットＣ（ｋ）を生成する候
補品目セット生成部、（ｃ３）ハッシュ木を、所定の容
量以内の部分木に分割するハッシュ木操作部、（ｃ４）
上記分割された部分木毎にデータベースとのマッチング
を行い、大品目セットＬ（ｋ）を選択する候補品目セッ
ト検証部、（ｄ）以下の処理部を有する仮説生成検証
部、（ｄ１）相関ルール候補を生成するルール候補生成
部、（ｄ２）上記相関ルール候補について相関ルールと
して採用するか棄却するかを判定するルール検定部。

【００５４】本発明の相関ルール生成装置は、以下の要
素を備えることを特徴とする１以上の品目からなる品目
集合間の相関ルールを抽出する相関ルール生成装置であ
る。 （ａ）１以上の品目からなる複数のレコードを記憶した
データベース、（ｂ）品目数Ｎからなる集合であって、
このＮ個の品目をすべて含むレコードの数である支持度
が未確認である集合を候補品目セットＣ（Ｎ）とし、該
候補品目セットＣ（Ｎ）の中で支持度が所定の下限値Ｓ
ｍｉｎ以上のものである大品目セットＬ（Ｎ）とし、該
大品目セットＬ（Ｎ）の情報を保存する大品目セットフ
ァイル、（ｃ）以下の処理部を有する大品目セット生成
部、（ｃ１）各個別の品目を含むレコードの数である支
持度をカウントし、この支持度が上記下限値Ｓｍｉｎ以
上である品目の集合を大品目セットＬ（１）と設定する
候補品目セット検証部、（ｃ２）該各品目に任意の連続
番号を割り当てた後、大品目セットＬ（１）の情報を大
品目セットファイルに保存するハッシュ木操作部、（ｃ
３）ｋを２以上の整数とし、大品目セットファイルから
大品目セットＬ（ｋ−１）中のｋ−１項組の情報を読み
込み、ハッシュ木に格納するハッシュ木操作部、（ｃ
４）上記ハッシュ木の枝を伸ばして、候補品目セットＣ
（ｋ）を生成する候補品目セット生成部、（ｃ５）計算
機上の相関ルール生成のために使用可能なメモリ容量を
使用許容容量とし、候補品目セットＣ（ｋ）を格納して
いるハッシュ木の容量を使用許容容量を超えない所定の
容量と比較して、ハッシュ木の容量の方が小さい場合は
上記大品目セットファイル読み込みステップに戻り、そ
うでない場合は次ステップに進めるハッシュ木操作部、
（ｃ６）上記候補品目セットＣ（ｋ）とデータベースと
のマッチングを行い、大品目セットＬ（ｋ）を選択する
候補品目セット検証部、（ｄ）相関ルール候補を生成
し、相関ルールとして採用するか棄却するかを判定する
仮説生成検証部。

【００５５】本発明の相関ルール生成装置は、以下の要
素を備えることを特徴とする１以上の品目からなる品目
集合間の相関ルールを抽出する相関ルール生成装置であ
る。 （ａ）１以上の品目からなる複数のレコードを記憶した
データベース、（ｂ）品目数Ｎからなる集合であって、
このＮ個の品目をすべて含むレコードの数である支持度
が未確認である集合を候補品目セットＣ（Ｎ）とし、該
候補品目セットＣ（Ｎ）の中で支持度が所定の下限値Ｓ
ｍｉｎ以上のものである大品目セットＬ（Ｎ）を記憶す
る領域、（ｃ）以下の処理部を有する大品目セット生成
部、（ｃ１）各個別の品目を含むレコードの数である支
持度をカウントし、この支持度が上記下限値Ｓｍｉｎ以
上である品目の集合を大品目セットＬ（１）と設定する
候補品目セット検証部、（ｃ２）候補品目セットＣ
（ｋ）を生成する候補品目セット生成部、（ｃ３）デー
タベースのレコードの集合と候補品目セットＣ（ｋ）を
格納するハッシュ木を入力としてマッチングを実行し、
大品目セットＬ（ｋ）を選択する候補品目セット検証
部、（ｄ）以下の処理を行なう仮説生成検証部、（ｄ
１）相関ルール候補を生成するルール候補生成部、（ｄ
２）上記相関ルール候補について相関ルールとして採用
するか棄却するかを判定するルール検定部。

【００５６】

【発明の実施の形態】以下、本発明の実施の形態につい
て説明するが、各実施の形態に共通な項目について説明
しておく。まず、本発明の実施の形態おいて使用するデ
ータベースの形式は、図５１に示すように、各レコード
はレコードを識別するためのレコードＩＤと１以上の任
意の整数で表現された品目の集まりとからなっているも
のとする。ここでは、ｋ個の品目の集まりをｋ項組と呼
び、このｋ項組を含むレコードの数をそのｋ項組の支持
度と呼ぶ。

【００５７】また、例えば、 Ａ，Ｂ，・・・，Ｘ→Ｙ という相関ルール、すなわち品目Ａ，Ｂ，・・・，Ｘを
含むレコードと、さらに品目Ｙも含むレコードの間には
相関があるというルールの場合、Ａ，Ｂ，・・，Ｘ，Ｙ
の全てを含むレコードの数をこの相関ルールの支持度、
Ａ，Ｂ，・・，Ｘを含むレコードの中でさらにＹも含む
レコードの割合を確信度と呼ぶ。この例では、右辺は、
相関ルールの結果となる品目のセットを意味し、左辺
は、相関ルールの条件となる品目のセットを意味してい
る。尚、相関ルール候補の場合にも同様に、右辺は、結
果となる品目のセットを意味し、左辺は、条件となる品
目のセットを意味している。

【００５８】上記の様な相関ルールにおいて、Ａ，Ｂ，
・・・，Ｘを含むレコードの数を左辺の支持度、Ｙを含
むレコードの数を右辺の支持度、Ａ，Ｂ，・・・，Ｘ，
Ｙを含むレコードの数を両辺の支持度と呼ぶ。また、こ
のような支持度および確信度について、ユーザによって
その最小値が指示されたものをそれぞれ最小支持度、最
小確信度と呼ぶ。

【００５９】さらに、本発明の実施の形態の説明におい
ては、最小支持度以上のｋ項組を要素とする集合を長さ
ｋの大品目セットＬｋと呼ぶ。また、大品目セットＬｋ
の要素の候補であるｋ項組を要素とする集合を長さｋの
候補品目セットＣｋと呼び、Ｃｋの要素中、最小支持度
以上のｋ項組がＬｋの要素として選択される。ただし、
ｋは１以上の整数である。

【００６０】また、本発明の実施の形態において、長さ
が同じ二つの品目セットの昇順の大小は、ハッシュ木上
の同じ高さのノード番号をｒｏｏｔから出発して並べて
比較し、初めて異なる番号の高さが出現した時、その番
号が小さい方の品目セットが、もう一方の品目セットよ
り昇順が小さいと決定する。

【００６１】実施の形態１．以下、この発明の実施の形
態１に係る相関ルール生成装置を図１、図２および図３
２から図３６に基づいて説明する。図について説明する
と、図１は本実施形態による相関ルール生成装置のシス
テム図、図２は本実施形態による相関ルール生成装置の
ブロック図、図３２は本実施形態における候補品目セッ
トＣｋ生成の詳細ブロック図、図３３本実施形態におけ
るデータベース、図３４から図３６は本実施形態におけ
る候補品目セットＣｋ生成の過程を示した図である。

【００６２】まず、本実施形態のシステムの構成を説明
する。図１において、１は蓄積されたデータベースであ
り、すでに説明したように図３３に示した構成を持つ。
２は上記データベース１から生成された大品目セット、
３は上記大品目セット２から生成され検証された相関ル
ールの集合である相関ルール集合、１０はユーザが所定
のパラメータを入力するユーザ入力部、２０は上記デー
タベース１から大品目セットを生成する大品目セット生
成部であり、この大品目セット生成部２０は候補品目セ
ットを検証して大品目セットを選択する候補品目セット
検証部２１と候補品目セットを生成する候補品目セット
生成部２２とから構成される。さらに４０は相関ルール
生成のためにまず仮説を生成し、さらにそれを検証する
仮説生成検証部であり、この仮説生成部は相関ルールの
候補を生成するルール候補生成部４１と、このルール候
補をχ² 検定によって検定し相関ルール集合に格納する
か否かを判定するχ² 検定部４３とから構成される。χ
² 検定については後述する。

【００６３】以下、図２のブロック図に従って本実施形
態における相関ルール生成の手順を説明する。まず最初
のステップ１０１で、ユーザ入力でユーザ入力部１０に
より、ユーザから最小支持度と有意水準を取得する。次
のステップ１１０、Ｌ１生成では、候補品目セット検証
部２１が、データベース中のレコードを一つずつ取り出
して、そのレコード中に出現する各品目について、出現
する回数をカウントし、そのカウント数である支持度を
増やす。初めて出現する品目については、そのカウント
の領域を新たに設ける。そして、全てのレコードについ
て数え上げが終了すると、最終的な支持度が最小支持度
を超えた品目について、大品目セットＬ１としてハッシ
ュ木に登録を行う。１，２，３，４，５の５つの品目の
支持度が最小支持度を超えた場合について、これらを登
録した状態のハッシュ木を図３４に示す。

【００６４】ハッシュ木の各枝の両端はノードと呼ば
れ、一般に品目番号が対応付けられるが、ハッシュ木の
始点のみは品目が対応付けられないノードで、ｒｏｏｔ
と呼ばれる。またｒｏｏｔからハッシュ木の末端のノー
ドまでの枝の数を枝の長さと呼ぶ。図３４のハッシュ木
の各枝の長さは１である。さらに、各枝のｒｏｏｔに近
い側のノードを親ノード、ｒｏｏｔから遠い側のノード
を子ノードと呼ぶ。

【００６５】ステップ１１０、Ｌ１生成に続いて、ステ
ップ１２０のＣｋ生成が行われる。Ｃｋ生成では候補品
目セット生成部２２が長さｋ−１の大品目セットＬｋ−
１から候補品目セットＣｋを生成する。ここではＬ２か
らＣ３が生成される場合の例を説明する。図３５にＬ２
まで作成された状態のハッシュ木の例を示す。このＣｋ
生成のステップの内部は図３２ブロック図の様な２段階
になっており、各々はｊｏｉｎステップ、ｐｒｕｎｅス
テップと呼ばれる。まず、ステップ１２１のｊｏｉｎス
テップについて説明する。ここでは、長さｋ−１まで伸
びた枝の１つのノードについて、同じ親ノードを持ち、
かつ末端のノードの品目番号がそのノードの品目番号よ
り大きい他のノードの末端の品目をそのノードの子ノー
ドとして追加して、枝を伸ばす。図３５のｒｏｏｔ→１
→３で示されるノード（これを［１，３］と表記するこ
とにし、以降の説明では、ハッシュ木のノードを同様な
記述で表す）には、同じ親ノードを持ち、かつ末端のノ
ードの品目番号が３より大きい［１，４］と［１，５］
と結合し、それぞれ［１，３，４］と［１，３，５］を
設ける。［１，４］についても［１，５］と結合し、
［１，４，５］が設けられる。［１，５］については５
より大きな品目番号を持つノードが［１］より下にない
ので、枝は伸ばされない。このようにしてＣｋ生成のた
めの３品目からなる本発明における候補品目予備セット
を形成する。この状態を図３６（１）ｐｒｕｎｅ前の図
に示す。

【００６６】次のステップ１２２のｐｒｕｎｅステップ
について説明する。ここでは、前のｊｏｉｎステップで
長さｋまで伸ばされた枝の該当する品目セットに関し
て、それから一つの品目を除いてできるｋ−１項組み全
てについて、それがＬｋ−１に属するかの検査を行い、
全てのｋ−１項組がＬｋ−１に属する場合のみ採用し、
１つでＬｋ−１に属さないｋ−１項組がある場合は削除
する。例えば［１，３，４］の検査を行う場合では、
［１，３］、［１，４］、［３，４］の３つの２項組み
がＬ２に存在するか調べられる。図３６の例ではいずれ
もＬ２に含まれるのでこの３項組みは残される。［１，
３，５］の検査を行う場合では、［１，３］、［３，
５］、［１，５］がＬ２に存在するかどうか調べられる
が、［３，５］は存在しないので、この３項組みは削除
される。以上の様にして、このｐｒｕｎｅステップでは
ｊｏｉｎによってできた全てのｋ項組みが検査される。
ｐｒｕｎｅ後のハッシュ木を図３６（２）ｐｒｕｎｅ後
の図に示す。図３４に示した初期状態ではｋ＝２であ
り、大品目セットＬ１から候補品目予備セットを経て、
候補品目セットＣ２が生成される。

【００６７】次にステップ１３０のＬｋ生成のステップ
が候補品目セット検証部２１によって行われる。ここで
はデータベースのレコードが一件ずつ取り出され、その
中に存在するＣｋの要素であるｋ項組みの数をカウント
し、最終的に最小支持度を超えたｋ項組みのみをＬｋの
要素として残す。このｋ項組のカウントのためにレコー
ドとハッシュ木の照合（マッチング）が行われる。この
マッチングは、まず、ハッシュ木のｒｏｏｔにおいてデ
ータベースのレコードが一件ずつ取り出され、各レコー
ド中にｒｏｏｔの子ノードの品目が存在するかどうか検
査する。存在しなければそのレコードについてのマッチ
ングは終了し、次のレコードを検査する。存在すれば、
その品目が対応付けられている子ノードにおいて、さら
に次の子ノード（ｒｏｏｔから見ると“孫”）に対応付
けられている品目がこのレコード中に存在するかどうか
を検査する。以後この操作を繰り返すが、適用されるノ
ードの子ノードがそれ以下に枝を持たないノード、すな
わち葉であり、なおかつそのレコード中に葉であるその
子ノードに対応している品目が存在する場合はこの葉ノ
ードの支持度集計用カウントを増やす操作を行い、この
レコードについてのマッチングを終了する。すべてのレ
コードについてマッチングが終了したときの各葉ノード
の支持度集計用カウントの値が、各ｋ項組（ｒｏｏｔか
らその葉ノードにいたるまでの品目の組）の支持度であ
る。このようにして各ｋ項組の支持度をカウントし、最
小支持度以上の支持度をもつｋ項組をすべて要素として
選択した大品目セットＬｋを生成する。

【００６８】Ｌｋ生成のステップでＬｋの要素となるｋ
項組みが一つも生成されなかった場合はステップ１５０
のルール候補生成に進み、そうでない場合はｋの値を一
つ増やし、Ｃｋ生成のステップに戻る。

【００６９】ステップ１５０のルール候補生成ではルー
ル候補生成部４１により、それまでのステップで作成さ
れた大品目セットよりルールの候補が作られる。Ｌｋ中
のあるｋ項組みからは、右辺にその中の一つの品目、左
辺に残りのｋ−１個の品目がくる計ｋ個のルール候補が
生成される。これが、ｋ＝２以上の全てのＬｋのｋ項組
みについて成される。

【００７０】最後のステップ１７０であるルール検定で
は、χ² 検定部４３によって、ルール候補生成部４１が
生成したルール候補の各々について、相関ルール集合に
格納するかどうかを決定する。各ルール候補の右辺、左
辺各々と両方の品目セットの支持度よりχ² 値を計算す
る。例えば、 Ａ１，Ａ２→Ｂ という候補ルールの検定を行う場合、Ａ１，Ａ２の支持
度すなわちＡ１，Ａ２を共に含むレコードの数をａ、Ｂ
の支持度すなわちＢを含むレコードの数をｂ、Ａ１，Ａ
２，Ｂの支持度すなわちＡ１，Ａ２，Ｂをすべて含むレ
コードの数をｃ、データベース中のレコードの総数をｎ
とすると、χ² 値は、

【００７１】

【数１】

【００７２】と計算される。この値は右辺と左辺が独立
な事象であると仮定したときの、自由度１のχ² 分布に
従う確率変数である。統計学によれば、この値が有意水
準から定まる一定の値を超えるとき、「右辺と左辺が独
立である」という仮説を棄却することができ、従って右
辺と左辺の間に何らかの関係が存在すると言うことがで
きる。（１）式で算出したχ² 値がユーザの指定した有
意水準から計算されるχ² 値の下限を超えているか判定
し、超えていれば相関ルール集合にルール候補を格納す
る。

【００７３】また、ｎｃ−ａｂが正のときはＡ１，Ａ２
とＢは正の相関を持つといい、同一レコードに同時に現
れ易い傾向にあることを示すし、負のときはＡ１，Ａ２
とＢとは負の相関を持つといい、同一レコードに同時に
現れにくいことを示す。本実施形態では、Ｌｋ生成のス
テップで、ｃ≧最小支持度を満足するＬｋを選択し、ま
たａ≧ｃ、ｂ≧ｃであるので、右辺と左辺および両辺の
支持度が最小支持度を超え、χ² 値が有意水準から計算
される下限を超えるルールを全て抽出することができ
る。

【００７４】以上のように、本実施の形態では、主に、
ユーザが少なくともχ² 検定における有意水準を入力す
るユーザ入力ステップと、相関ルール候補について、左
辺の支持度、右辺の支持度、左辺と右辺の両方に含まれ
る品目からなる品目セットの支持度、およびレコード総
数からχ² 値を算出し、このχ² 値と上記有意水準を指
標としてχ² 検定を行い、相関ルールとして採用するか
棄却するかを判定するルール検定ステップを有する相関
ルール生成方法および各ステップの処理を行なう相関ル
ール生成装置について説明した。

【００７５】従って、相関ルールをχ² 値という統計量
によって評価し抽出を行うので、統計的に意味のある相
関ルールのみを得ることができるという効果がある。

【００７６】実施の形態２．以下、この発明の実施の形
態２に係る相関ルール生成装置を図１から図５に基づい
て説明する。上記実施の形態１は候補品目セットＣｋ生
成のステップは、ｊｏｉｎステップおよびｐｒｕｎｅス
テップの２つのステップからなっていたが、本実施形態
はＣｋ生成のステップがｊｏｉｎステップのみからなる
ようにしたものである。

【００７７】図について説明すると、図１は本実施形態
における相関ルール生成装置のシステム図、図２は本実
施形態における相関ルール生成装置のブロック図、図３
は本実施形態における候補品目セットＣｋ生成の詳細ブ
ロック図、図４および図５は本実施形態における候補品
目セットＣｋ生成と実施の形態１における候補品目セッ
トＣｋ生成の比較を示した図である。

【００７８】図１のシステム図および図２のブロック図
は実施の形態１と同様の構成であり、動作については、
図１中の候補品目セット生成部２２による図２中のステ
ップ１２０Ｃｋ生成の動作が実施の形態１と相違してい
る以外は、実施の形態１と同様である。そこで、以下、
図１の候補品目セット生成部２２による図２のステップ
１２０Ｃｋ生成の動作を説明する。

【００７９】図２において、Ｃｋ生成のステップ１２０
では、候補品目セット生成部２２により、図３の詳細ブ
ロック図の様に、ｊｏｉｎステップのみでｐｒｕｎｅス
テップによる候補の絞り込みを行わない候補品目セット
生成を実行する。

【００８０】この方法はｐｒｕｎｅステップを含む従来
技術に比べて、処理時間が短くなる。その理由を以下に
説明する。図５に図４のＬ２まで作成されたハッシュ木
をｊｏｉｎステップによって伸ばして、本発明における
候補品目予備セットを生成した状態（１）と、それにさ
らにｐｒｕｎｅ操作を行った状態（２）を示す。例え
ば、各々のハッシュ木について、レコード＝｛１，２，
３，５｝とのマッチングを考えてみると、ヒットしたノ
ードは、（１）におけるｐｒｕｎｅによって削除された
［１，３，５］のノード以外は全て同じである。しかも
この［１，３，５］についても［１，３］までハッシュ
でヒットして次の［１，３，５］を探す操作までは同一
で，手間の違いは［１，３，５］のノードのカウントを
増やす操作のみである。これに対して、ｐｒｕｎｅを行
う場合では、そのｐｒｕｎｅステップにおいて［１，
３，５］による３項組みから一つの品目を除いた［１，
３］、［１，５］、［３，５］の３つのノードの検索を
行わなければならない。これは［１，３，５］のノード
のカウントを増やすことと比べて大きな負荷となる。

【００８１】以上のように、本実施の形態では、主に、
Ｃｋ生成ステップにおいて、全ての候補品目予備セット
Ｄ（ｋ）を候補品目セットＣ（ｋ）として選択する相関
ルール生成方法及び各ステップの処理を行なう相関ルー
ル作成装置について説明した。

【００８２】従って、候補品目セット生成の際にｐｒｕ
ｎｅ操作を行わないので、処理時間を短縮することがで
きる。

【００８３】実施の形態３．以下、この発明の実施の形
態３に係る相関ルール生成装置を図２および図６に基づ
いて説明する。上記実施の形態１は相関ルールが正の相
関か負の相関かを判別せずに相関ルール集合に格納して
いたが、本実施形態は正の相関ルールのみを選択して格
納するようにしたものである。

【００８４】図について説明すると、図２は本実施形態
における相関ルール生成装置のブロック図、図６は本実
施形態のシステム図である。

【００８５】システムの構成を説明すると、図６におい
て正相関選択部４４以外は実施の形態１で説明したシス
テム図１と同様である。正相関選択部４４では、χ² 値
が有意水準から計算される下限値を満たしたルールが正
の相関であるかどうかを判定する。また、図２のブロッ
ク図においては、上記正相関選択部４４によるステップ
１７０ルール検定の動作のみが実施の形態１と異なり、
他の動作は実施の形態１と同様である。

【００８６】以下、図２のブロック図に従って本実施形
態における相関ルール生成の手順を説明するが、ユーザ
入力１００からルール候補生成１５０のステップまでは
実施の形態１と同じ動作である。ルール検定のステップ
１７０では、ルール候補のχ² 値を計算し、その値が有
意水準から計算される下限値を満たした候補について
は、正相関選択部４４がそのルールが正負のどちらの相
関に相当するかを計算し、本実施例では正の場合のみ、
相関ルール集合３に格納する。ルール候補の正負判定方
法については、例えば、 Ａ１，Ａ２→Ｂ という候補ルールの検定を行う場合、Ａ１，Ａ２の支持
度をａ、Ｂの支持度をｂ、Ａ１，Ａ２，Ｂの支持度を
ｃ、データベース中のレコードの総数をｎとすると、 ｎｃ−ａｂ の値を計算し、これが正ならば正の相関と判定される。
このように構成すれば、相関ルールのなかから正の相関
ルールのみを選択的に抽出することが可能である。

【００８７】また、以上では正相関選択部４４を設けて
正の相関ルールを相関ルール集合３に格納したが、正相
関選択部の代わりに負相関選択部を設け、 ｎｃ−ａｂ＜０ を満たす負の相関ルールのみを相関ルール集合に格納す
るようにしてもよい。このように構成すれば、相関ルー
ルのなかから負の相関ルールのみを選択的に抽出するこ
とが可能である。

【００８８】以上のように、本実施の形態では、主に、
仮説生成検証ステップが正相関選択ステップを有し、正
の相関ルールを選択的に採用する相関ルール生成方法お
よび各ステップの処理を行なう相関ルール生成装置につ
いて説明した。

【００８９】従って、統計的に意味のある正相関ルール
のみを得ることができるという効果がある。

【００９０】実施の形態４．以下、この発明の実施の形
態４に係る相関ルール生成装置を図７から図９に基づい
て説明する。これまでの実施の形態は長さｋ−１の大品
目セットから長さｋの候補品目セットを生成し、さらに
ルール候補を生成していたが、本実施形態は、長さ１の
大品目セットＬ１と長さｋ−１の大品目セットＬｋ−１
からルール候補を生成するようにしたものである。

【００９１】図について説明すると、図７は本実施形態
における相関ルール生成装置のシステム図、図８は本実
施形態における相関ルール生成装置のブロック図、図９
は本実施形態における候補品目セットＣｋ生成の過程を
示した図である。

【００９２】図７のシステム図は、図１に示した実施の
形態１のシステム図と同様の構成であるが、図７の候補
品目セット生成部２４、ルール候補生成部４６の動作が
図１の同名のものと異なる為、この部分の動作について
説明する。これ以外の動作については実施の形態１と同
様である。図７において、候補品目セット生成部２４
は、長さ１の大品目セットと長さｋ−１の大品目セット
より長さｋの候補品目セットＣｋを生成する役割を持
つ。また、ルール候補生成部４６は、長さ１の大品目セ
ットと長さｋ−１の大品目セット、長さｋの候補品目セ
ットからルールの候補を生成する。

【００９３】以下、図８のブロック図に従って本実施例
における相関ルール生成の手順を説明する。まず最初の
ステップ、ユーザ入力４００でユーザ入力部１０によ
り、ユーザから最小支持度と有意水準を取得する。次の
ステップ４１０、Ｌ１生成で長さ１の大品目セットＬ１
が作成される。これは実施の形態１と同様に、候補品目
セット検証部２４が、データベース中のレコードを一つ
ずつ取り出して、そのレコード中に出現する各品目につ
いて、出現する回数をカウントし、そのカウント数であ
る支持度を増やす。初めて出現する品目については、そ
のカウントの領域を新たに設ける。そして、全てのレコ
ードについて数え上げが終了すると、最終的な支持度が
最小支持度を超えた品目について、ハッシュ木に登録を
行う。

【００９４】次に、ステップ４２０でＬｋ−１の集合が
空であるかどうかの判定が行われる。初期状態ではｋ＝
２であり、判定の対象となるのはＬ１である。もしＬｋ
−１が空であれば本装置は終了状態となり、そうでなけ
れば次のステップ４３０のＣｋ生成が行われる。

【００９５】ステップ４３０のＣｋ生成では候補品目セ
ット生成部２４により、Ｌ１とＬｋ−１から候補品目セ
ットＣｋが生成される。このステップでは、まずＬｋ−
１まで作成されたハッシュ木の葉に、Ｌ１中の各品目が
追加され、さらに重複を除き、ハッシュ木の下方の品目
番号が上方よりも大きくなる様に再構成される。これを
図９の様な、ｋ＝３の場合の例で説明する。Ｌ２に属す
る［１，３］の葉３に、Ｌ１に属する品目、１、２、
３、４、５が追加される。この追加された品目の内、１
と３は２項組みの品目集合中に含まれるため除かれる。
そして２については葉の３より番号が小さいので、
［１，２，３］を木に含めるため、［１］の下に２、そ
の下に３が再構成される。これがＬ２の葉の全てについ
て行われる。

【００９６】そして、生成されたＣｋ（例ではＣ３）の
各候補品目セットについて、データベースを検索してそ
の支持度が集計される。そのためにレコードとハッシュ
木のマッチングが実施の形態１と同様に行われる。

【００９７】次のステップ４４０のルール候補生成では
ルール候補生成部４６によりルールの候補が生成され
る。このステップでは、まずＬｋ−１中の各品目セット
と、Ｌ１中の各品目がひとつずつ抽出される。ｋ＝３の
場合、Ａ１，Ａ２がＬ２から、ＢがＬ１から抽出された
とすると、ＢがＡ１，Ａ２に含まれず（Ａ１，Ａ２のど
ちらでもなく）、かつ生成中のルールの候補集合にＡ
１，Ａ２→Ｂが含まれなければ、Ａ１，Ａ２→Ｂをルー
ルの候補集合に追加する。これをＬ２とＬ１の全ての品
目セットの組み合わせについて行う。

【００９８】次のステップであるルール検定４５０で
は、χ² 検定部４３によりルール候補生成部４１が生成
したルール候補の各々について、相関ルール集合に格納
するかどうかを決定する。このために、各ルール候補の
右辺および左辺の支持度を調べ、両方とも最小支持度以
上であるルール候補について、右辺、左辺各々と両方の
品目セットの支持度よりχ² 値を計算する。これが有意
水準から計算される下限値を超えているか判定し、超え
ていれば相関ルール集合にルール候補を格納する。

【００９９】次にステップ４６０のＬｋ生成が行われ
る。これにはステップ４３０で求めたＣｋ中のｋ項組み
の支持度を利用し、最小支持度を超えたｋ項組みのみを
Ｌｋの要素として残す。この後はステップ４７０でｋの
値を一つ増やし、ステップ４２０に戻る。

【０１００】本実施形態では、右辺と左辺の全ての品目
の支持度は使用せず、右辺の支持度と左辺の支持度が共
に最小支持度を超え、さらにχ² 検定の有意水準から計
算される下限値を超えるルールが全て抽出される。ま
た、これによりこれまで両辺全ての品目による品目セッ
トの支持度が低いために抽出不可能であった多くの負の
相関関係を示す相関ルールを抽出することが可能とな
る。

【０１０１】以上のように、本実施の形態では、主に、
大品目セットＬ（ｋ−１）と大品目セットＬ（１）か
ら、大品目セットＬ（ｋ−１）を条件となる品目セッ
ト、大品目セットＬ（１）を結果となる品目セットとす
る相関ルール候補を生成するルール候補生成ステップを
有する相関ルール生成方法と各ステップの処理を行なう
相関ルール作成装置について説明した。

【０１０２】従って、相関ルールの両辺全ての品目から
なる品目セットの支持度がいかなる値であっても、相関
ルールを得ることができ、負の相関ルールを抽出できる
という効果がある。

【０１０３】実施の形態５．以下、この発明の実施の形
態５に係る相関ルール生成装置を図８および図１０に基
づいて説明する。上記実施の形態４は相関ルールが正の
相関か負の相関かを判別せずに相関ルール集合に格納し
ていたが、本実施形態は正の相関ルールのみまたは負の
相関ルールのみを選択して格納するようにしたものであ
る。

【０１０４】図について説明すると、図８は本実施形態
における相関ルール生成装置のブロック図、図１０は本
実施形態における相関ルール生成装置のシステム図であ
る。

【０１０５】システムについて説明すると、図１０にお
ける正負判定部４５以外は上記実施の形態４で説明した
システム図７と同様である。正負判定部４５では、χ²
値が有意水準から計算される下限値を満たしたルールが
正の相関なのか、負の相関なのかを判定する。また、図
８のブロック図においては、上記正負判定部４５による
ステップ４５０ルール検定の動作のみが実施の形態４と
異なり、他の動作は実施の形態４と同様である。

【０１０６】以下、図８のブロック図に従って本実施例
における相関ルール生成の手順を説明するが、上述のよ
うにステップ４５０のルール検定のステップ以外は実施
の形態４と同じ動作である。このルール検定のステップ
４５０では、ルール候補のχ² 値を計算し、その値が有
意水準から計算される下限値を満たした候補について
は、正負判定部４５がそのルールが正負のどちらの相関
に相当するかを計算し、正または負の場合のみ、相関ル
ール集合に格納する。ルール候補の正負判定について
は、例えば、 Ａ１，Ａ２→Ｂ という候補ルールの検定を行う場合、Ａ１，Ａ２の支持
度をａ、Ｂの支持度をｂ、Ａ１，Ａ２，Ｂの支持度を
ｃ、データベース中のレコードの総数をｎとすると、 ｎｃ−ａｂ （２） の値を計算し、これが正ならば正の相関ルール、負なら
ば負の相関ルールと判定され、相関ルール集合３に格納
される。

【０１０７】左辺の品目セットのレコード全体に対する
比率はａ／ｎ、右辺の品目のレコード全体に対する比率
はｂ／ｎであるので、右辺および左辺すべての品目のレ
コード全体に対する比率の期待値はａｂ／ｎ² となり、
実際の比率ｃ／ｎとの差は、 （ｎｃ−ａｂ）／ｎ² （３） となる。上記の（２）式はこの（３）式の分子であり、
相関ルールの正負の判定をルールの両辺の全ての品目セ
ットの支持度の期待値と実際の値との差の正負によって
行っていることを意味する。

【０１０８】ここで、正の相関ルールを格納するか負の
相関ルールを格納するかはユーザ入力部１０によりユー
ザが指定してもよく、またシステムで予め固定されてい
てもよい。

【０１０９】以上のように、本実施の形態では、主に、
仮説生成検証ステップに、相関ルールが正の相関ルール
か負の相関ルールかを判定する正負判定ステップを設
け、負の相関ルールのみを採用する相関ルール生成方法
および各ステップの処理を行なう相関ルール生成装置
と、同様に仮説生成検証ステップに、上記正負判定ステ
ップを設け、正の相関ルールのみを採用する相関ルール
生成方法および各ステップの処理を行なう相関ルール生
成装置について説明した。

【０１１０】従って、効率的に負の相関ルールを抽出す
ることができるという効果と、効率的に正の相関ルール
を抽出することができるという効果がある。

【０１１１】実施の形態６．以下、この発明の実施の形
態６に係る相関ルール生成装置を図１１、図１２、図１
３に基づいて説明する。これまでに説明した実施の形態
では、ユーザが最小支持度および有意水準を入力してい
たが、本実施形態はユーザによる最小支持度の入力を不
要にし、負の相関ルールを抽出するシステムにおいて、
最小支持度と同じ役割を持つ限界支持度というパラメー
タをシステムが自動的に設定するようにしたものであ
る。

【０１１２】図について説明すると、図１１は本実施形
態における相関ルール生成装置のシステム図、図１２は
本実施形態における相関ルール生成装置のブロック図、
図１３は本実施形態における相関ルール生成装置の限界
支持度の決定法を説明する図である。

【０１１３】システムの構成を説明すると、図１１にお
いてユーザ入力部１０と本実施形態における新規な要素
である負の相関用限界支持度決定部２６以外は、実施の
形態５で説明したシステム図１０と同様の機能を有す
る。ユーザ入力部１０は本実施形態においてはユーザか
ら有意水準のみを獲得し、負の相関用限界支持度決定部
２６は、全ての品目の支持度の内最も大きな支持度を使
用して、実施の形態５における最小支持度と同じ役割を
持つ限界支持度を決定する役割を持つ。

【０１１４】以下、図１２のブロック図に従って本実施
形態における相関ルール生成の手順を説明する。最初の
ステップ７００、ユーザ入力ではユーザ入力部１０によ
って、ユーザから有意水準を取得する。次のステップ７
１０、各品目支持度集計では、候補品目セット検証部２
１がデータベースを検索し、データベース中のレコード
に現れる全ての品目の支持度を集計する。

【０１１５】次のステップ７２０、限界支持度計算で
は、実施の形態５における最小支持度に代わる役割をす
る限界支持度の決定が、負の相関用限界支持度決定部２
６によって行われる。ここで行われる計算の式は、前ス
テップで集計された支持度の内最大のものをＬ１ｍａ
ｘ、有意水準から計算されるχ² 値の下限値をα、デー
タベース中のレコードの件数をｎとすると、

【０１１６】

【数２】

【０１１７】となる。

【０１１８】このことを図１３で説明すると、ａはある
ｂの値に対してｆ（ｂ）以上である斜線部の値を取らな
ければならないことを意味し、このためにはａがｆ（Ｌ
１ｍａｘ）以上であることが必要条件である。以上の計
算式はａとｂについて対称であるので、図１３中のａと
ｂを入れ替えて読んで、ｂはあるａの値に対してｆ
（ａ）以上の値、すなわち斜線部の値を取らなければな
らない。またａの値もＬ１ｍａｘ以下であるから、ｂが
斜線部の値をとるためにはｂがｆ（Ｌ１ｍａｘ）以上で
あることが必要条件である。このように、χ² が有意水
準から計算された下限値以上となる相関ルールの両辺の
品目セットは、どちらもその支持度は限界支持度を上回
ることが必要条件である。

【０１１９】次のステップ７３０、Ｌ１生成では、候補
品目セット検証部が各品目支持度集計のステップで集計
した支持度が限界支持度を上回る品目について、これを
１項組みとして品目セットＬ１に追加する。以降のステ
ップは、実施の形態５のブロック図８の同名のステップ
以下と同様の動作を行う。ただし、ステップ７７０のル
ール検定では、右辺の支持度と左辺の支持度の両方が上
記限界支持度以上であるルール候補について、χ² 値を
算出する。また同時に、 ｎｃ−ａｂ を計算してこの値の正負を正負判定部４５により判定
し、この値が負になる負の相関ルールが選択される。

【０１２０】本実施形態では、ユーザが最小支持度を指
定する必要がなく、有意水準から計算される下限値によ
って計算された限界支持度によって大品目セットを生成
していくため、相関ルールの両辺の品目による品目セッ
トの支持度がいかなる値であってもχ² 値という統計量
によって相関ルールの評価・抽出を行うので、効率的に
統計的な相関関係を有する負の相関ルールを得ることが
できる。

【０１２１】以上のように、本実施の形態では、主に、
大品目セット生成ステップに、支持度の最も大きな個別
の品目の支持度から上記支持度の下限値Ｓｍｉｎを算出
する負の相関用限界支持度決定ステップを備えた相関ル
ール生成方法および各ステップの処理を行なう相関ルー
ル生成装置について説明した。

【０１２２】従って、ユーザが最小支持度を入力する必
要が無く、また不要な支持度をもつルール候補に関して
検定を行うことが無いので効率的に負の相関ルールを抽
出することができるという効果がある。

【０１２３】実施の形態７．以下、この発明の実施の形
態７に係る相関ルール生成装置を図１３、図１４、図１
５に基づいて説明する。上記実施の形態６は、負の相関
ルールを抽出するシステムにおいて、最小支持度に相当
する限界支持度というパラメータを自動的に設定するも
のであったが、本実施形態は支持度の最も小さい１項組
の支持度を最小支持度とするものである。

【０１２４】図について説明すると、図１３は上記実施
の形態６で説明した限界支持度を説明する図、図１４は
本実施形態における相関ルール生成装置のシステム図、
図１５は本実施形態における相関ルール生成装置のブロ
ック図である。

【０１２５】システムの構成を説明すると、図１４にお
いてユーザ入力部１０と本実施形態における新規な要素
である最小支持度決定部２５以外は、実施の形態５で説
明したシステム図１０と同様の機能を有する。ユーザ入
力部１０は本実施形態においてはユーザから有意水準の
みを獲得し、最小支持度決定計算部２５では、全ての品
目中最も支持度の小さい品目の支持度を最小支持度と決
定する。

【０１２６】以下、図１５のブロック図に従って本実施
形態における相関ルール生成の手順を説明する。最初の
ステップ６００、ユーザ入力ではユーザ入力部１０によ
って、ユーザから有意水準を取得する。次のステップ６
１０、各品目支持度集計では、候補品目セット検証部２
１がデータベースを検索し、データベース中のレコード
に現れる全ての品目の支持度を集計する。次のステップ
６２０、最小支持度決定では、最小支持度決定部２５が
前ステップで集計された支持度の内最も値の小さいもの
最小支持度と決定する。そしてステップ６３０のＬ１生
成では全ての品目の１項組みをＬ１に登録する。以降の
ステップは、実施の形態４のブロック図８の同名のステ
ップと同様の動作を行う。ただし、ステップ６７０、ル
ール検定では、正負判定部４５により負の相関ルールが
選択され、相関ルール集合３に格納される。

【０１２７】本実施形態は、一般のデータベースにおい
て、最も支持度の小さい品目の支持度は上記実施の形態
６で説明したｆ（Ｌ１ｍａｘ）よりも小さいことを利用
しており、これは図１３から明らかなように、χ² 値が
有意水準から計算された下限値以上となる相関ルールの
両辺の各品目セットは、どちらもその支持度は本実施形
態における最小支持度を上回ることが必要条件であるこ
とによる。

【０１２８】本実施形態によれば、ユーザが最小支持度
を指定する必要がなく、最小支持度決定部が自動的に決
定した全品目中最小の支持度によって大品目セットを生
成し、相関ルールの両辺の品目による品目セットの支持
度の値に関係なくχ² 値という統計量によって相関ルー
ルの評価・抽出を行うので、統計的に相関関係を有する
負の相関ルールを得ることができる。

【０１２９】以上のように、本実施の形態では、主に、
大品目セット生成ステップに、支持度の最も小さな個別
の品目の支持度を支持度の下限値Ｓｍｉｎと設定する最
小支持度決定ステップを備えた相関ルール生成方法およ
び各ステップの処理を行なう相関ルール生成装置につい
て説明した。

【０１３０】従って、ユーザが最小支持度を入力する必
要がないという効果がある。

【０１３１】実施の形態８．以下、この発明の実施の形
態８に係る相関ルール生成装置を図１２、図１６に基づ
いて説明する。上記実施の形態６は、負の相関ルールを
抽出するシステムにおいて最小支持度に相当する限界支
持度を算出していたが、本実施形態は、正の相関ルール
を抽出するシステムにおいて、この限界支持度を算出す
るものである。

【０１３２】図について説明すると、図１２は本実施形
態における相関ルール生成装置のブロック図、図１６は
本実施形態における相関ルール生成装置のシステム図で
ある。

【０１３３】システムの構成を説明すると、図１６にお
いてユーザ入力部１０と本実施形態における新規な要素
である正の相関用限界支持度決定部２７以外は、実施の
形態５で説明したシステム図１０と同様の機能を有す
る。ユーザ入力部１０は本実施形態においてはユーザか
ら有意水準のみを獲得し、正の相関用限界支持度決定部
２７は、全ての品目の支持度の内最も小さな支持度を使
用して、実施の形態５における最小支持度と同じ役割を
持つ限界支持度を決定する役割を持つ。

【０１３４】以下、図１２のブロック図に従って本実施
例における相関ルール生成の手順を説明する。最初のス
テップ７００、ユーザ入力ではユーザ入力部１０によっ
て、ユーザから有意水準を取得する。次のステップ７１
０、各品目支持度集計では、候補品目セット検証部２１
がデータベースを検索し、データベース中のレコードに
現れる全ての品目の支持度を集計する。次のステップ７
２０、限界支持度計算では実施の形態５における最小支
持度と同様の役割をする限界支持度の決定が、正の相関
用限界支持度決定部２７によって行われる。限界支持度
の計算式は、前ステップで集計された支持度の内最小の
ものをＬ１ｍｉｎ、有意水準から計算されるχ² 値の下
限値をα、データベース中のレコードの件数をｎとする
と、

【０１３５】

【数３】

【０１３６】となる。この不等式はｂをａに置き換えて
も成立する。従って、χ² 値が有意水準から計算される
下限値以上となる相関ルールの両辺の品目セットは、ど
ちらもその支持度は限界支持度を上回ることが必要条件
である。

【０１３７】次のステップ７３０のＬ１生成では、候補
品目セット検証部２１が各品目支持度集計のステップ７
１０で集計した支持度が限界支持度を上回る品目につい
て、これを１項組みとして品目セットＬ１に追加する。
以降のステップは、実施の形態５のブロック図８の同名
のステップ以下と同様の動作を行う。ただし、ステップ
７７０のルール検定では、右辺および左辺の両方の支持
度が上記限界支持度以上であるルール候補について、χ
² 値を算出する。また同時に、 ｎｃ−ａｂ を計算してこの値の正負を正負判定部４５により判定
し、この値が正になる正の相関ルールが選択される。

【０１３８】本実施形態ではユーザが最小支持度を指定
する必要がなく、有意水準から計算される下限値によっ
て計算された限界支持度によって大品目セットを生成
し、相関ルールの両辺の品目による品目セットの支持度
がいかなる値であってもχ² 値という統計量によって評
価・抽出を行うので、効率的に統計的な相関関係を有す
る正の相関ルールを得ることができる。

【０１３９】以上のように、本実施の形態では、主に、
大品目セット生成ステップに、支持度の最も小さな個別
の品目の支持度から支持度の下限値Ｓｍｉｎを算出する
正の相関用限界支持度決定ステップを備えた相関ルール
生成方法および各ステップの処理を行なう相関ルール生
成装置について説明した。

【０１４０】従って、ユーザが最小支持度を入力するこ
と無く、また不要な支持度をもつルール候補に関して検
定を行うことが無いので効率的に正の相関ルールを抽出
することができるという効果がある。

【０１４１】実施の形態９．以下、この発明の実施の形
態９に係る相関ルール生成装置を図１７、図１８に基づ
いて説明する。上記実施の形態６は、負の相関ルールを
抽出するシステムにおいて、全ての品目の支持度の内最
も大きな支持度を使用して限界支持度を算出し、両辺と
もこの限界支持度をこえるルール候補をχ² 検定してい
たが、本実施形態では、左辺の支持度から右辺が上回る
べき支持度を境界値として算出し、これを満足するルー
ル候補のみをχ² 検定するものである。

【０１４２】図について説明すると、図１７は本実施形
態における相関ルール生成装置のシステム図、図１８は
本実施形態における相関ルール生成装置のブロック図で
ある。

【０１４３】システムの構成を説明すると、図１７にお
いて本実施形態における新規な要素である負の境界決定
部２８以外は実施の形態６で説明したシステム図１１と
同様の機能を有する。負の境界決定部２８では、左辺の
品目セットの支持度より右辺の品目が満たさなければな
らない最小の支持度を計算する役割を持つ。

【０１４４】以下、図１８のブロック図に従って本実施
形態における相関ルール生成の手順を説明する。このブ
ロック図におけるルール候補生成・検証のステップ９６
０以外のステップは実施の形態６のブロック図１２の同
名のステップと同様な動作を行う。

【０１４５】ステップ９６０、ルール候補生成・検証で
はルール候補生成部４７によりルールの候補が生成され
る。このステップでは、Ｌｋ−１中の各品目セットがひ
とつずつ抽出され、その品目セットの支持度毎にルール
の右辺の品目の満たすべき支持度の下限の計算が負の境
界決定部８によって行われる。例えば、Ａ１，Ａ２，・
・・Ａｋ−１がＬｋ−１から抽出されたとし、その支持
度（Ｌｋ−１中に書いてある）をａとする。下限値の計
算式は、有意水準から計算されるχ² 値の下限値をα、
データベース中のレコードの件数をｎとすると、

【０１４６】

【数４】

【０１４７】が成立することが必要となる。従って、Ａ
１，Ａ２，・・・Ａｋ−１が左辺にきたときのルールの
右辺の品目の支持度は上記の境界値を上回らなければな
らない。この境界値が決定されると、その境界値を上回
る支持度を持つＬ１中の１項組みの各々について、それ
を右辺とするルールの検証がルール検定のステップ９６
２で行われる。

【０１４８】ＢがＬ１から抽出された場合のルール検証
ステップでの動作を説明する。ＢがＡ１，Ａ２，・・・
Ａｋ−１に含まれないか（Ａ１，Ａ２，・・・Ａｋ−１
のいずれでもないか）、の検証がルール候補生成部４７
によって行われる。含まれていなければ、ルールＡ１，
Ａ２，・・・Ａｋ−１→¬Ｂ（「Ａ１，Ａ２，・・・Ａ
ｋ−１ならばＢではない。」の意味である。）のχ² 値
がχ² 検定部４３によって各ルール候補の右辺、左辺各
々と両方の品目セットの支持度から計算される。これが
有意水準から計算される下限値を超えているか判定し、
超えていれば相関ルール集合３にルール候補を格納す
る。

【０１４９】このように、本実施形態によれば、ルール
の左辺にくる大品目セットの各組について、右辺の品目
の支持度の下限値を計算してχ² 値を計算する候補を絞
るため、効率的に負の相関ルールを得ることができる。

【０１５０】以上のように、本実施の形態では、主に、
仮説生成検証ステップにおいて、ルール候補生成ステッ
プで相関ルール候補を生成する際に使用した大品目セッ
トＬ（ｋ−１）と大品目セットＬ（１）の対に対して、
該大品目セットＬ（ｋ−１）の支持度から該大品目セッ
トＬ（１）の支持度の下限値Ｔｍｉｎを算出する負の境
界決定ステップを備え、支持度が下限値Ｔｍｉｎ以上で
ある大品目セットＬ（１）とこれと対の大品目セットＬ
（ｋ−１）から生成された相関ルール候補のみをルール
検定ステップでχ² 検定を行う相関ルール生成方法およ
び各ステップの処理を行なう相関ルール生成装置につい
て説明した。

【０１５１】従って、ユーザが最小支持度を入力する必
要が無く、また不要な支持度をもつルール候補に関して
検定を行うことが無いので効率的に負の相関ルールを抽
出することができるという効果がある。

【０１５２】実施の形態１０．以下、この発明の実施の
形態１０に係る相関ルール生成装置を図１８、図１９に
基づいて説明する。上記実施の形態８は、正の相関ルー
ルを抽出するシステムにおいて、全ての品目の支持度の
内最も小さな支持度を使用して限界支持度を算出し、両
辺ともこの限界支持度以上のルール候補をχ² 検定して
いたが、本実施形態では、左辺の支持度から右辺の支持
度がとるべき範囲の支持度を境界値として算出し、これ
を満足するルール候補のみをχ² 検定するものである。

【０１５３】図について説明すると、図１８は本実施形
態における相関ルール生成装置のブロック図、図１９は
本実施形態における相関ルール生成装置のシステム図で
ある。

【０１５４】システムの構成を説明すると、図１９にお
いて本実施形態における新規な要素である正の境界決定
部２９以外は実施の形態６で説明したシステム図１１と
同様の機能を有する。正の境界決定部２９では、左辺の
品目セットの支持度より右辺の品目が満たさなければな
らない最小の支持度を決定する役割を持つ。

【０１５５】以下、図１８のブロック図に従って本実施
例における相関ルール生成の手順を説明する。このブロ
ック図におけるルール候補生成・検証のステップ９６０
以外のステップは実施の形態６のブロック図１２の同名
のステップと同様な動作を行う。ステップ９６０のルー
ル候補生成・検証ではルール候補生成部４７によりルー
ルの候補が生成される。このステップでは、Ｌｋ−１中
の各品目セットがひとつずつ抽出され、その品目セット
の支持度毎にルールの右辺の品目の満たすべき支持度の
上限と下限の計算が正の境界決定部２９によって行われ
る。例えば、Ａ１，・・・，Ａｋ−１がＬｋ−１から抽
出されたとし、その支持度（Ｌｋ−１中に書いてある）
をａとする。上限値と下限値の計算式は、有意水準から
計算されるχ² 値の下限値をα、データベース中のレコ
ードの件数をｎとすると、

【０１５６】

【数５】

【０１５７】が成立することが必要となる。従って、Ａ
１，・・・，Ａｋ−１が左辺にきたときのルールの右辺
の品目の支持度は上記の境界内に入らなければならな
い。この境界が決定されると、その境界内の支持度を持
つＬ１中の１項組みの各々について、それを右辺とする
ルールの検証がルール検定のステップ９６２で行われ
る。ＢがＬ１から抽出された場合のルール検定ステップ
９６２での動作を説明する。ＢがＡ１，・・・，Ａｋ−
１に含まれないか（Ａ１，・・・，Ａｋ−１のいずれで
もないか）、の検証がルール候補生成部４７によって行
われる。含まれていなければ、ルールＡ１，・・・，Ａ
ｋ−１→Ｂのχ² 値がχ² 検定部４３によって各ルール
候補の右辺、左辺各々と両方の品目セットの支持度から
計算される。これが有意水準から計算されるχ² 値の下
限値を超えているかどうかを判定し、超えていれば相関
ルール集合３にルール候補を格納する。

【０１５８】本実施形態によれば、ルールの左辺にくる
大品目セットの各組について、右辺の品目の支持度の範
囲を計算してχ² 値を計算する候補を絞るため、効率的
に正の相関ルールを得ることができる。

【０１５９】以上のように、本実施の形態では、主に、
仮説生成検証ステップにおいて、ルール候補生成ステッ
プで相関ルール候補を生成する際に使用した大品目セッ
トＬ（ｋ−１）と大品目セットＬ（１）の対に対して、
該大品目セットＬ（ｋ−１）の支持度から該大品目セッ
トＬ（１）の支持度の下限値Ｕｍｉｎと上限値Ｕｍａｘ
を算出する正の境界決定ステップを備え、支持度が下限
値Ｕｍｉｎ以上で上限値Ｕｍａｘ以下である大品目セッ
トＬ（１）とこれと対の大品目セットＬ（ｋ−１）から
生成された相関ルール候補のみをルール検定ステップで
χ² 検定を行う相関ルール生成方法および各ステップの
処理を行なう相関ルール生成装置について説明した。

【０１６０】従って、ユーザが最小支持度を入力する必
要が無く、また不要な支持度をもつルール候補に関して
検定を行うことが無いので効率的に正の相関ルールを抽
出することができるという効果がある。

【０１６１】実施の形態１１．以下、この発明の実施の
形態１１に係る相関ルール生成装置を図７、図８、図２
０に基づいて説明する。これまで説明してきた実施の形
態においては、抽出される相関ルールの右辺または左辺
に含まれる品目を指定することはできなかったが、本実
施形態は左辺として指定された品目は抽出される相関ル
ールの左辺に必ず一つ以上含まれ、また右辺として指定
された品目は抽出される相関ルールの右辺に必ず１個以
上含まれるようにしたものである。

【０１６２】図について説明すると、図７は本実施形態
における相関ルール生成装置のシステム図、図８は本実
施形態における相関ルール生成装置のブロック図、図２
０は本実施形態における相関ルール生成装置の候補品目
セット生成を説明する図である。

【０１６３】システムの説明をすると、図７はすでに実
施の形態４で説明に使用したが、本実施形態においては
ユーザ入力部１０、候補品目セット生成部２４、ルール
候補生成部４６の動作が詳細において実施の形態４と異
なり、それ以外は実施の形態４と同様である。図７にお
いて、候補品目セット生成部２４では、長さ１の大品目
セットと長さｋ−１の大品目セットより長さｋの候補集
合を生成する役割を持つ。ルール候補生成部２４は、長
さ１の大品目セットと長さｋ−１の大品目セット、長さ
ｋの候補集合からルールの候補を生成する。図７におい
て、ユーザ入力部１０はユーザから最小支持度と有意水
準および相関ルールの左辺、右辺に現れる品目名を取得
する。また候補品目セット生成部２４では、長さ１の大
品目セットと長さｋ−１の大品目セットより長さｋの候
補品目セットを生成する役割を持つが、この過程におい
てハッシュ木の指定されていない品目のノードは枝を伸
ばさない。またルール候補生成部４６は、長さ１の大品
目セットと長さｋ−１の大品目セットからルールの候補
を生成するが、この長さ１の大品目セットとしては右辺
候補中の最小支持度を超える品目セットが使用される。

【０１６４】以下、図８のブロック図に従って本実施例
における相関ルール生成の手順を説明する。まず最初の
ステップ４００、ユーザ入力でユーザ入力部１０によ
り、ユーザから最小支持度と有意水準および相関ルール
の左辺、右辺に現れる品目名を取得する。次のステップ
４１０、Ｌ１生成で長さ１の大品目セットＬ１が作成さ
れる。これは実施の形態４と同様に候補品目セット検証
部２４が、データベース中のレコードを一つずつ取り出
して、そのレコード中に出現する各品目について、出現
する回数をカウントし、そのカウント数である支持度を
増やす。初めて出現する品目については、そのカウント
の領域を新たに設ける。そして、全てのレコードについ
て数え上げが終了すると、最終的な支持度が最小支持度
を超えた品目について、ハッシュ木に登録を行う。ただ
し、ここでは左辺の候補として指定された品目がそれ以
外の品目よりも小さな整数となる様に番号が各品目に再
付与され、また右辺の候補として指定された品目の番号
がどちらにも指定されていない品目の番号よりも小さな
整数となる様に、番号が各品目に再付与される。この再
付与による番号と元の番号との対応データは、メモリ上
で対応表として管理する。

【０１６５】次に、ステップ４２０でＬｋ−１の集合が
空であるかどうかの判定が行われる。初期状態ではｋ＝
２であり、判定の対象となるのはＬ１である。もしＬｋ
−１が空であれば本装置は終了状態となり、そうでなけ
れば次のステップ４３０のＣｋ生成が行われる。

【０１６６】ステップ４３０のＣｋ生成では候補品目セ
ット生成部２４により、実施の形態４のＣｋ生成ステッ
プと同様の方法でＬ１とＬｋ−１から候補集合Ｃｋが生
成される。ただし本ステップでは、Ｌ１からＣ２を作る
とき、ハッシュ木上で左辺または右辺の品目として指定
されていない品目のノードは枝を伸ばさないことを特徴
としてる。例えば、図２０の様なハッシュ木があり、品
目１，２，３が左辺または右辺として指定されていたと
すると、Ｌ１からＣ２へと枝を伸ばす段階では［１］、
［２］、［３］以外は枝は伸ばさない。これは、右辺ま
たは左辺の候補品目を全く含まない大品目セットは必要
ないからである。

【０１６７】次のステップ４４０のルール候補生成では
ルール候補生成部４６によりルールの候補が生成され
る。このステップでは、まずＬｋ−１中の各品目セット
と、右辺候補中の最小支持度を超える品目セット（これ
をＳ１とする）からの品目がひとつずつ抽出される。ｋ
＝３の場合、Ａ１，Ａ２がＬ２から、ＢがＳ１から抽出
されたとすると、ＢがＡ１，Ａ２に含まれず（Ａ１，Ａ
２のどちらでもなく）、かつ生成中のルールの候補集合
にＡ１，Ａ２→Ｂが含まれなければ、Ａ１，Ａ２→Ｂを
ルールの候補集合に追加する。これをＬ２とＳ１の全て
の品目セットの組み合わせについて行う。上で説明した
ステップ以後のステップは実施の形態４と同様の動作を
行う。

【０１６８】本実施形態によれば、ルールの右辺にくる
品目と左辺にくる品目の条件によりハッシュ木の枝刈り
を行っているため、指定された品目がそれぞれ条件どお
りに右辺と左辺にくるルールを効率的に得ることができ
る。

【０１６９】以上のように、本実施の形態では、主に、
ユーザ入力ステップで、ユーザが少なくとも相関ルール
の左辺または右辺の品目に関する条件を入力する相関ル
ール生成方法および各ステップの処理を行なう相関ルー
ル生成装置について説明した。

【０１７０】具体的には、ユーザ入力ステップで、ユー
ザが相関ルール中の左辺にその中の１個以上が必ず含ま
れる１個以上の品目と相関ルール中の右辺にその中の１
個以上が必ず含まれる１個以上の品目を条件として入力
する相関ルール生成方法および各ステップの処理を行な
う相関ルール生成装置について説明した。

【０１７１】従って、特定の品目に関する相関ルールが
効率的に抽出できるという効果がある。

【０１７２】実施の形態１２．以下、この発明の実施の
形態１２に係る相関ルール生成装置を図７、図８、図２
１に基づいて説明する。実施の形態１１は、左辺として
指定された品目は抽出される相関ルールの左辺に必ず一
つ以上含まれ、また右辺として指定された品目は必ず右
辺に含まれるようにしたものであったが、本実施形態で
は、左辺として指定された品目は抽出される相関ルール
の左辺に必ず全て含まれ、右辺として指定された品目は
抽出される相関ルールの右辺に必ず全て含まれているよ
うにしたものである。

【０１７３】図について説明すると、図７は本実施形態
における相関ルール生成装置のシステム図、図８は本実
施形態における相関ルール生成装置のブロック図、図２
１は本実施形態における相関ルール生成装置の候補品目
セット生成を説明する図である。

【０１７４】システムの説明をすると、図７はすでに実
施の形態４で説明に使用したが、本実施形態においては
ユーザ入力部１０、候補品目セット生成部２４、ルール
候補生成部４６の動作が詳細において実施の形態４と異
なる以外は、実施の形態４と同様である。候補品目セッ
ト生成部２４では、長さ１の大品目セットと長さｋ−１
の大品目セットより長さｋの候補集合を生成する役割を
持つ。ルール候補生成部４６は、長さ１の大品目セット
と長さｋ−１の大品目セット、長さｋの候補集合からル
ールの候補を生成する。

【０１７５】以下、図８のブロック図に従って本実施例
における相関ルール生成の手順を説明する。まず最初の
ステップ４００、ユーザ入力でユーザ入力部１０によ
り、ユーザから最小支持度と有意水準、および相関ルー
ルの左辺、右辺に現れる品目名を取得する。次のステッ
プ４１０、Ｌ１生成で長さ１の大品目セットＬ１が作成
される。これは実施の形態４と同様に候補品目セット検
証部２４が、データベース中のレコードを一つずつ取り
出して、そのレコード中に出現する各品目について、出
現する回数をカウントし、そのカウント数である支持度
を増やす。初めて出現する品目については、そのカウン
トの領域を新たに設ける。そして、全てのレコードにつ
いて数え上げが終了すると、最終的な支持度が最小支持
度を超えた品目について、ハッシュ木に登録を行う。た
だし、ここでは左辺の候補として指定された品目がそれ
以外の品目よりも小さな整数となる様に番号が各品目に
再付与され、また右辺の候補として指定された品目の番
号がどちらにも指定されていない品目の番号よりも小さ
な整数となる様に、番号が各品目に再付与される。この
再付与による番号と元の番号との対応データは、メモリ
上で対応表として管理する。

【０１７６】次に、ステップ４２０でＬｋ−１の集合が
空であるかどうかの判定が行われる。初期状態ではｋ＝
２であり、判定の対象となるのはＬ１である。もしＬｋ
−１が空であれば本装置は終了状態となり、そうでなけ
れば次のステップ４３０のＣｋ生成が行われる。

【０１７７】ステップ４３０のＣｋ生成では候補品目セ
ット生成部２４により、実施の形態４のＣｋ生成ステッ
プと同様の方法でＬ１とＬｋ−１から候補集合Ｃｋが生
成される。ただし本ステップでは、左辺として指定した
品目をＡ１，Ａ２・・，Ａｎとすると、［Ａ１］，［Ａ
１，Ａ２］，・・，［Ａ１，Ａ２，・・，Ａｎ］のｎ個
の枝以外の枝以下は伸ばさないことを特徴としている。
例えば、図２１の様なハッシュ木があり、品目１，２が
左辺、として指定されていたとすると、［１］、［１，
２］以外は枝は伸ばさない。これは、右辺、左辺の候補
品目を全く含まない大品目セットは必要ないからであ
る。

【０１７８】次のステップ４４０のルール候補生成では
ルール候補生成部４６によりルールの候補が生成され
る。このステップでは、まずＬｋ−１中の各品目セット
と、右辺候補中の最小支持度を超える品目セット（これ
をＳ１とする）からの品目がひとつずつ抽出される。左
辺として指定された品目の数をｎ個とすると、ｋ＜ｎ＋
１の場合についてはルール候補は生成しない。ｋ＝３の
場合、Ａ１，Ａ２がＬ２から、ＢがＳ１から抽出された
とすると、ＢがＡ１，Ａ２に含まれず（Ａ１，Ａ２のど
ちらでもなく）、かつ生成中のルールの候補集合にＡ
１，Ａ２→Ｂが含まれなければ、Ａ１，Ａ２→Ｂをルー
ルの候補集合に追加する。これをＬ２とＳ１の全ての品
目セットの組み合わせについて行う。上で説明したステ
ップ以後のステップは実施の形態４と同様の動作を行
う。

【０１７９】本実施形態によれば、ルールの右辺にくる
品目と左辺にくる品目の条件によりハッシュ木の枝刈り
を行っているため、指定された品目がそれぞれ条件どお
りに右辺と左辺にくるルールを効率的に得ることができ
る。

【０１８０】以上のように、本実施の形態では、主に、
ユーザ入力ステップで、ユーザが少なくとも相関ルール
の左辺または右辺の品目に関する条件を入力する相関ル
ール生成方法および各ステップの処理を行なう相関ルー
ル生成装置について説明した。

【０１８１】具体的には、ユーザ入力ステップで、ユー
ザが相関ルール中の左辺にすべてが必ず含まれる１個以
上の品目と相関ルール中の右辺にすべてが必ず含まれる
１個以上の品目を条件として入力する相関ルール生成方
法および各ステップの処理を行なう相関ルール生成装置
について説明した。

【０１８２】従って、特定の品目に関する相関ルールが
効率的に抽出できるという効果がある。

【０１８３】実施の形態１３．以下、この発明の実施の
形態１３に係る相関ルール生成装置を図２２、図２３に
基づいて説明する。これまでに説明してきた実施の形態
では、相関ルール抽出用のレコードのドメインを指定す
ることはできなかったが、本実施形態ではドメインの指
定を可能にしたものである。

【０１８４】図について説明すると、図２２は本実施形
態における相関ルール生成装置のシステム図、図２３は
本実施形態における相関ルール生成装置のブロック図で
ある。

【０１８５】システムについて説明をすると、図２２に
おいて、ユーザ入力部１０と図２２のシステムにおける
新規な要素であるドメイン限定部３２以外はすでに実施
の形態１で説明した図１のシステム図と同様の機能を持
つ。ユーザ入力部１０はユーザから獲得するパラメータ
が実施の形態１と異なる。また、ドメイン限定部３２
は、ユーザが指定したドメインに属するレコードのみを
抽出して、相関ルール抽出用のデータファイルを新たに
作成する役割を果たす。

【０１８６】以下、図２３のブロック図に従って本実施
形態における相関ルール生成の手順を説明する。まず最
初のステップ３００、ユーザ入力でユーザ入力部１０に
より、ユーザから最小支持度と有意水準、およびドメイ
ン指定のための、レコードが含まなければならない品目
名を取得する。次のステップ３１０、ドメイン限定ファ
イル生成で、ドメイン限定部３２が指定されたユーザの
指定したドメイン限定条件により、データベースを検索
し、検索条件に合致したレコードを抽出し、相関ルール
抽出用ファイルに格納する。以下のステップでは実施の
形態１のブロック図２の同名のステップと同様の動作を
行う。以上の説明ではステップ３１０において一括して
ドメイン限定の処理を行ったが、ステップ３２０、３４
０においてデータベースを検索する際に、ドメインに入
らないレコードのハッシュ木とのマッチングを避ける様
にしても同様の効果が得られる。

【０１８７】また、Ｃｋ生成ステップ３３０において、
実施の形態２の説明において図３で示したように、ｊｏ
ｉｎステップのみを行い、ｐｒｕｎｅステップを行なわ
ないようにしてもよい。

【０１８８】本実施形態によれば、ドメインとして指定
された条件に合致したレコードのみによる相関ルール抽
出用ファイルを作成するため、ドメインを限定した場合
の相関ルール抽出を効率的に実行できる。

【０１８９】以上のように、本実施の形態では、主に、
ユーザ入力ステップは、ユーザがデータベース中のレコ
ードの中から、特定の１以上の品目を持つレコードの集
合であるドメインを指定するために上記１以上の品目を
入力し、大品目セット生成ステップは、データベースか
ら指定された上記ドメインに含まれるレコードのみを取
り出し、以後データベース中のレコード総数の代わりに
このドメインに含まれるレコードの総数を使用するよう
にするドメイン限定ステップを備えた相関ルール生成方
法および各ステップの処理を行なう相関ルール生成装置
について説明した。

【０１９０】従って、ドメインを限定した場合の相関ル
ールを効率的に抽出できるという効果がある。

【０１９１】実施の形態１４．以下、この発明の実施の
形態１４に係る相関ルール生成装置を図２、図２４に基
づいて説明する。これまでに説明して来た実施の形態で
は、各品目に付される品目番号とその支持度とは無関係
であったが、本実施形態では支持度の大きい順に品目番
号を付け直すものである。

【０１９２】図について説明すると、図２は本実施形態
における相関ルール生成装置のブロック図、図２４は本
実施形態における相関ルール生成装置のシステム図であ
る。

【０１９３】システムについて説明をすると、図２４に
おいて、ユーザ入力部１０と図２４のシステムにおける
新規な要素である品目番号再配置部３３以外はすでに実
施の形態１で説明した図１のシステム図と同様の機能を
持つ。品目番号再配置部３３は、長さ１の大品目セット
を生成するステップにおいて、支持度の大きい順に品目
番号を割り振り直す役割を持つ。

【０１９４】以下、図２のブロック図に従って本実施形
態における相関ルール生成の手順を説明する。まず最初
のステップ１０１、ユーザ入力でユーザ入力部１０によ
り、ユーザから最小支持度と有意水準を取得する。次の
ステップ１１０、Ｌ１生成で長さ１の大品目セットが作
成される。ここではＬ１の１項組みはその支持度の大き
さ順にソートされて計算機の記憶装置に格納される。そ
して、再配置部３３によって、支持度が大きい順に各品
目に整数が割り当てられ、新たに割り当てられた整数値
による新たなデータファイルが作成され、割り当て前と
の対応表も作成される。以下のステップではデータベー
ス検索の対象はこのデータファイルとなる。ルール検定
のステップ１７０では、相関ルール集合に格納すると決
定されたルール中の各品目の番号を再配置部３３がもつ
対応表から再割り当て前の番号にふり直す操作も行われ
る。他のステップでは実施の形態１のブロック図２の同
名のステップと同様の動作を行う。

【０１９５】また、Ｃｋ生成ステップ１２０において、
実施の形態２の説明において図３で示したように、ｊｏ
ｉｎステップのみを行い、ｐｒｕｎｅステップを行なわ
ないようにしてもよい。

【０１９６】このように、本実施形態によれば、最小支
持度以上の品目の品目番号が順にならび、番号に抜けが
ないためハッシュ木上の各ハッシュテーブルにおけるメ
モリ領域が効率良く管理できる。品目番号が１から自然
数ｍまで抜けがなくハッシュのキーとして存在する場
合、ハッシュ関数は、キーの値をｍで割った余りとすれ
ばよく、しかもテーブル中の全てのバケットにデータを
収めることができる。

【０１９７】以上のように、本実施の形態では、主に、
大品目セット生成ステップは、各品目の支持度の順に各
個別の品目に対し品目番号を付ける品目番号再配置ステ
ップを備えた相関ルール生成方法および各ステップの処
理を行なう相関ルール生成装置について説明した。

【０１９８】従って、効率的に相関ルールを抽出できる
という効果がある。

【０１９９】実施の形態１５．以下、この発明の実施の
形態１５に係る相関ルール生成装置を図２および図２５
〜図２７に基づいて説明する。これまでに説明して来た
実施の形態では、一度形成されたハッシュ木は分割され
ることはなかったが、本実施形態ではハッシュ木が大き
い場合には分割するようにしたものである。

【０２００】図について説明すると、図２は本実施形態
における相関ルール生成装置のブロック図、図２５は本
実施形態における相関ルール生成装置のシステム図、図
２６は本実施形態における相関ルール生成装置の候補品
目セット生成ステップの詳細図、図２７は本実施形態に
おける相関ルール生成装置のハッシュ木分割を説明する
図である。

【０２０１】システムについて説明すると、図２５のシ
ステム図における新規な構成要素であるハッシュ木分割
部３４以外は、すでに実施の形態２で説明して図１のシ
ステムと同様の機能を持つ。ハッシュ木分割部３４は、
必要に応じてハッシュ木を分割する機能を持つ。

【０２０２】以下、本実施形態における相関ルール生成
の手順を説明するが、この手順は図２に示したブロック
図と同様であり、この図２のＣｋ生成ステップ１２０と
Ｌｋ生成ステップ１３０が異なるのみであるので、この
Ｃｋステップ生成およびＬｋ生成ステップについて説明
を行う。

【０２０３】図２６に、Ｃｋ生成ステップ１２０の詳細
ブロック図を示す。Ｃｋ生成のステップにおいて、ｊｏ
ｉｎステップ５２１が終わり候補のｋ項組み全てを作成
した段階でハッシュ木分割部３４によるハッシュ木分割
が行われる。ここではまず、現段階までで各ハッシュ木
のノード数が一定値を超えていないかどうか検査する。
この一定値はメモリ上に格納可能なノード数の上限付近
を目安とする。そして、超えている木については、ステ
ップ５２３で木のルートのハッシュテーブルを再構成
し、ノード数がなるべく等しくなる様に２分割する。例
えば図２７（１）のハッシュ木を分割する場合は、ｒｏ
ｏｔの下の１と２の間で点線の様に分割すれば各ノード
数は６個と７個で当分割に最も近くなる。分割後の２つ
のハッシュ木を図２７（２）に示す。

【０２０４】そしてＬｋ生成ステップ１３０において
は、実施の形態１のようなＬｋ生成を各木について行
う。ハッシュ木がＡ、Ｂ、Ｃと３つあった場合には、ま
ずＡについて実施の形態１のようなＬｋ生成を行い、次
にＢについて行い、最後にＣについて行う。各ハッシュ
木は常にメモリに入りきるだけの大きさが維持されてい
るため、レコードとハッシュ木のマッチングの際におこ
るページングによるディスクとメモリ間でのデータのや
り取りを最小限に押さえることができる。

【０２０５】また、ハッシュ木が非常に大きい場合は、
本分割処理を繰り返し適用して部分木を小さくしてもよ
い。また、実施の形態１のようにｊｏｉｎステップの後
にｐｒｕｎｅステップを実行してからハッシュ木を分割
してもよい。

【０２０６】本実施形態によれば、ハッシュ木を常にメ
モリに入りきる様に、ノード数が大きくなるとハッシュ
木を分割するしてハッシュ木とレコードのマッチングの
際に起こるページングを抑止するため、高速にマッチン
グを行うことができる。

【０２０７】以上のように、本実施の形態では、主に、
大品目セット生成ステップには、ハッシュ木が一定の大
きさを超えると分割して複数のハッシュ木にするハッシ
ュ木分割ステップを備え、レコードとのマッチングの際
には各ハッシュ木について全レコードとのマッチングを
とる相関ルール生成装置および各ステップの処理を行な
う相関ルール生成装置について説明した。

【０２０８】従って、高速にマッチング処理を行なえる
という効果がある。

【０２０９】実施の形態１６．以下、この発明の実施の
形態１６に係る相関ルール生成装置を図２、図２８に基
づいて説明する。これまでに説明して来た実施の形態で
は、レコード中の全ての組合わせをハッシュ木と突き合
わせていたが、本実施形態ではハッシュ木中のｋ項組を
一つずつ取り出すようにしたものである。

【０２１０】図について説明すると、図２は本実施形態
における相関ルール生成装置のブロック図、図２８は本
実施形態における相関ルール生成装置のシステム図であ
る。

【０２１１】システムについて説明すると、図２８のシ
ステム図における新規な構成要素である逆方向レコード
マッチング部３５以外は、すでに実施の形態２で説明し
て図１のシステムと同様の機能を持つ。

【０２１２】以下、本実施形態における相関ルール生成
の手順を説明するが、この手順は図２に示したブロック
図と同様であり、この図２のＬｋ生成ステップ１３０が
異なるのみであるので、このＬｋ生成ステップについて
説明を行う。Ｌｋ生成のステップ１３０において、レコ
ードとハッシュ木のマッチングは以下の様にして行われ
る。まず、カウントを行うレコードを一つ抽出する。次
にハッシュ木からｋ項組みを一つずつ抽出し、各々をレ
コードと比較してカウントする。この比較の方法である
が、ｋ項組みとレコードの各々の中で、品目は品目番号
順にソートされているとする。まず、ｋ項組みの品目を
先頭から一つ取り出し、レコード中にそれがあるかどう
か、レコードの先頭から検索する。もしなければこのｋ
項組みについての処理を止める。あればｋ項組みの次の
品目を一つ取り出し、これをレコード中の前の合致した
品目の位置から検索をかける。途中で中止されなけれ
ば、これをｋ個の品目全てについて行う。そしてこのマ
ッチング処理をハッシュ木中の全てのｋ項組みについて
行う。そしてこのレコードのマッチング処理を、全レコ
ードについて繰り返す。

【０２１３】本実施形態によれば、レコード中の全ての
組み合わせをハッシュ木と突き合わせるのではなく、ハ
ッシュ木中の各大品目セットをレコードと突き合わせる
ので、ハッシュ木が小さくかつレコード長が長い場合、
効率的にレコードと大品目セットとのマッチングを行う
ことができる。

【０２１４】以上のように、本実施の形態では、主に、
大品目セット生成ステップに、候補品目セットＣ（ｋ）
を格納するハッシュ木中のｋ項組みを一つずつ取り出し
て、レコードとのマッチングを行う逆方向レコードマッ
チングステップを備える相関ルール生成方法および各ス
テップの処理を行なう相関ルール生成装置について説明
した。

【０２１５】従って、高速にマッチング処理が行なえる
という効果がある。

【０２１６】実施の形態１７．以下、この発明の実施の
形態１７に係る相関ルール生成装置を図７、図８、図２
９に基づいて説明する。これまでに説明して来た実施の
形態では、相関ルール中に同時に現れることが許されな
い品目は指定できなかったが、本実施形態では相関ルー
ル中に同時に現れることが許されない品目を指定できる
ようにしたものである。

【０２１７】図について説明すると、図７は本実施形態
における相関ルール生成装置のシステム図、図８は本実
施形態における相関ルール生成装置のブロック図、図２
９は本実施形態における候補品目セット生成を説明する
図である。

【０２１８】システムについて説明をすると、図７はす
でに実施の形態４で説明に使用したが、本実施形態にお
いては、ユーザ入力部１０と候補品目セット生成部２４
およびルール候補生成部４６以外は実施の形態４と同様
の機能を持つ。

【０２１９】ユーザ入力部１０では最小支持度、有意水
準の他、相関ルール中に同時に現れることが許されない
品目の組がユーザより入力される。候補品目セット生成
部２４では、長さ１の大品目セットと長さｋ−１の大品
目セットより長さｋの候補集合を生成する役割を持つ。
ルール候補生成部４６は、長さ１の大品目セットと長さ
ｋ−１の大品目セット、長さｋの候補集合からルールの
候補を生成する。

【０２２０】以下、図８のブロック図に従って、本実施
形態における相関ルール生成の手順を説明する。まず最
初のステップ４００、ユーザ入力でユーザ入力部１０に
より、ユーザから最小支持度と有意水準、および相関ル
ール中に同時に現れることが許されない品目の組を取得
する。次のステップ４１０、Ｌ１生成で長さ１の大品目
セットＬ１が作成される。これは実施の形態４と同様に
候補品目セット検証部２４が、データベース中のレコー
ドを一つずつ取り出して、そのレコード中に出現する各
品目について、出現する回数をカウントし、そのカウン
ト数である支持度を増やす。初めて出現する品目につい
ては、そのカウントの領域を新たに設ける。そして、全
てのレコードについて数え上げが終了すると、最終的な
支持度が最小支持度を超えた品目について、ハッシュ木
に登録を行う。次に、ステップ４２０でＬｋ−１の集合
が空であるかどうかの判定が行われる。初期状態ではｋ
＝２であり、判定の対象となるのはＬ１である。もしＬ
ｋ−１が空であれば本装置は終了状態となり、そうでな
ければ次のステップ４３０のＣｋ生成が行われる。

【０２２１】ステップ４３０のＣｋ生成では候補品目セ
ット生成部２４により、実施の形態４のＣｋ生成ステッ
プと同様の方法でＬ１とＬｋ−１から候補集合Ｃｋが生
成される。ただし本ステップでは、相関ルール中に同時
に現れることが許されない品目の組の中の品目を複数含
むｋ項組みはこの時点でハッシュ木から削除される。例
えば、図２９の様なハッシュ木があり、品目の組｛１，
２，５｝が同時に現れることが許されない品目の集合と
して指定されているとすると、［１，５］は削除され
る。次のステップ４４０のルール候補生成ではルール候
補生成部４６によりルールの候補が生成される。このス
テップの動作は実施の形態４におけるルール生成のステ
ップの動作とほぼ同一であるが、ここでは同時に現れる
ことが許されない品目の組中の品目を複数（ここでは２
個）含むルールは、ルール候補に追加しない。ｋ＝３の
場合、Ａ１，Ａ２がＬ２から、ＢがＬ１から抽出された
とすると、ＢとＡ１、またはＢとＡ２のどちらの２つ組
も、同時に現れることが許されない品目の組に入ってい
ない場合のみに、 Ａ１， Ａ２→Ｂをルールの候補集合
に追加する。上で説明したステップ以後のステップは実
施の形態４と同様の動作を行う。

【０２２２】本実施形態によれば、候補品目セット生成
の段階から同時に現れてはならない品目の組を含む候補
を除外するので、相関ルール中に同時に発生しない品目
の組を指定した相関ルール抽出を、効率的に行うことが
できる。

【０２２３】以上のように、本実施の形態では、主に、
ユーザ入力ステップは、ユーザが相関ルール中に同時に
現れてはならない２個以上の品目からなる組を指定し、
Ｌｋ生成ステップは、この指定された組に含まれる複数
の品目を同時には含まない大品目セットＬ（ｋ）のみを
生成する相関ルール生成方法および各ステップの処理を
行なう相関ルール生成装置について説明した。

【０２２４】従って、相関ルール中に同時に現れてはな
らない品目の組を含まない相関ルールを効率的に抽出で
きるという効果がある。

【０２２５】実施の形態１８．実施の形態１５の手法で
はｒｏｏｔの直下で木を分割するため、同じＬ１の品目
を含む品目セットは、分割後もすべて同じ木に含まれ
る。例えば図２７（１）のハッシュ木で、［１］以下の
部分は分割後もすべて同じ木に含まれ、この木がメモリ
の容量を超えてしまう場合には対処できない。この様な
場合、木の分割後も［１］を含む木のマッチング操作で
ページングを起こしてしまうという欠点がある。この発
明は上記のような問題点を解決するためになされたもの
であり、ハッシュ木に偏りがある場合でもページングを
抑止し、高速に相関ルール生成を実行する相関ルール生
成装置を得ることを目的とする。

【０２２６】以下、この発明の実施の形態１８に係る相
関ルール生成装置を図３７から図３９および図５１から
図５５に基づいて説明する。図について説明すると、図
３７は本実施形態による相関ルール生成装置のシステム
図、図３８は本実施形態による相関ルール生成装置のブ
ロック図、図３９は本実施形態におけるハッシュ木分割
の説明図、図５１は本実施形態におけるデータベース、
図５２から図５４は本実施形態における候補品目セット
Ｃｋ生成の過程を示した図、図５５は本実施形態におけ
る候補品目セットＣｋ生成の詳細ブロック図である。

【０２２７】まず、本実施形態のシステムの構成を説明
する。図３７において、１００１は蓄積されたデータベ
ースであり、すでに説明したように図５１に示した構成
を持つ。１００２は上記データベース１から生成された
大品目セット、１００３は上記大品目セット１００２か
ら生成され検証された相関ルールの集合である相関ルー
ル集合、１０１０はユーザが所定のパラメータを入力す
るユーザ入力部、１０２０は上記データベース１から大
品目セットを生成する大品目セット生成部であり、この
大品目セット生成部１０２０は候補品目セットを検証し
て大品目セットを選択する候補品目セット検証部１０２
１と候補品目セットを生成する候補品目セット生成部１
０２２およびハッシュ木をハッシュ木のために用意され
たメモリ領域に収まる部分木に分割する役割を持つハッ
シュ木操作部１０２３とから構成される。さらに１０４
０は相関ルール生成のためにまず仮説を生成し、さらに
それを検証する仮説生成検証部であり、この仮説生成検
証部１０４０は相関ルールの候補を生成するルール候補
生成部１０４１と、各ルール候補の確信度を計算する確
信度計算部とから構成される。

【０２２８】以下、図３８のブロック図に従って本実施
形態における相関ルール生成の手順を説明する。まず最
初のステップ１２００で、ユーザ入力でユーザ入力部１
０１０により、ユーザから最小支持度と最小確信度を取
得する。

【０２２９】次のステップ１２１０、Ｌ１生成では、候
補品目セット検証部１０２１が、データベース中のレコ
ードを一つずつ取り出して、そのレコード中に出現する
各品目について、出現する回数をカウントし、そのカウ
ント数である支持度を増やす。初めて出現する品目につ
いては、そのカウントの領域を新たに設ける。そして、
全てのレコードについて数え上げが終了すると、最終的
な支持度が最小支持度を超えた品目について、大品目セ
ットＬ１としてハッシュ木に登録を行う。１，２，３，
４，５の５つの品目の支持度が最小支持度を超えた場合
について、これらを登録した状態のハッシュ木を図５２
に示す。

【０２３０】ハッシュ木の各枝の両端はノードと呼ば
れ、一般に品目番号が対応付けられるが、ハッシュ木の
始点のみは品目が対応付けられないノードで、ｒｏｏｔ
と呼ばれる。またｒｏｏｔからハッシュ木の末端のノー
ドまでの枝の数を枝の長さと呼ぶ。図５２のハッシュ木
の各枝の長さは１である。さらに、各枝のｒｏｏｔに近
い側のノードを親ノード、ｒｏｏｔから遠い側のノード
を子ノードと呼ぶ。

【０２３１】ステップ１２１０、Ｌ１生成に続いて、ス
テップ１２２０のＣｋ生成が行われる。Ｃｋ生成では候
補品目セット生成部１０２２が長さｋ−１の大品目セッ
トＬｋ−１から候補品目セットＣｋを生成する。当初ｋ
＝２である。ここではＬ２からＣ３が生成される場合の
例を説明する。図５３にＬ２まで作成された状態のハッ
シュ木の例を示す。このＣｋ生成のステップの内部は図
５５のブロック図の様な２段階になっており、各々はｊ
ｏｉｎステップ、ｐｒｕｎｅステップと呼ばれる。

【０２３２】まず、ステップ１１２１のｊｏｉｎステッ
プについて説明する。ここでは、長さｋ−１まで伸びた
枝の１つのノードについて、同じ親ノードを持ち、かつ
末端のノードの品目番号がそのノードの品目番号より大
きい他のノードの末端の品目をそのノードの子ノードと
して追加して、枝を伸ばす。図５３のｒｏｏｔ→１→３
で示されるノード（これを［１，３］と表記することに
し、以降の説明では、ハッシュ木のノードを同様な記述
で表す）には、同じ親ノードを持ち、かつ末端のノード
の品目番号が３より大きい［１，４］と［１，５］と結
合し、それぞれ［１，３，４］と［１，３，５］を設け
る。［１，４］についても［１，５］と結合し、［１，
４，５］が設けられる。［１，５］については５より大
きな品目番号を持つノードが［１］より下にないので、
枝は伸ばされない。このようにしてＣｋ生成のための３
品目からなる候補品目予備セットを形成する。この状態
を図５４（１）ｐｒｕｎｅ前の図に示す。

【０２３３】次のステップ１１２２のｐｒｕｎｅステッ
プについて説明する。ここでは、前のｊｏｉｎステップ
で長さｋまで伸ばされた枝の該当する品目セットに関し
て、それから一つの品目を除いてできるｋ−１項組み全
てについて、それがＬｋ−１に属するかの検査を行い、
全てのｋ−１項組がＬｋ−１に属する場合のみ採用し、
１つでもＬｋ−１に属さないｋ−１項組がある場合は削
除する。例えば［１，３，４］の検査を行う場合では、
［１，３］、［１，４］、［３，４］の３つの２項組み
がＬ２に存在するか調べられる。図５４の例ではいずれ
もＬ２に含まれるのでこの３項組みは残される。［１，
３，５］の検査を行う場合では、［１，３］、［３，
５］、［１，５］がＬ２に存在するかどうか調べられる
が、［３，５］は存在しないので、この３項組みは削除
される。以上の様にして、このｐｒｕｎｅステップでは
ｊｏｉｎによってできた全てのｋ項組みが検査される。
ｐｒｕｎｅ後のハッシュ木を図５４（２）ｐｒｕｎｅ後
の図に示す。図５２に示した初期状態ではｋ＝２であ
り、大品目セットＬ１から候補品目予備セットを経て、
候補品目セットＣ２が生成される。生成された候補品目
セットＣｋは候補品目セット生成部１０２２内に記憶さ
れる。

【０２３４】次に、ステップ１２３０のハッシュ木分割
ステップが実行される。Ｃｋ生成のステップ１２２０が
終わり長さｋの候補品目セットが格納された状態のハッ
シュ木は、ハッシュ木操作部１０２３により、用意され
たメモリ領域の量（ハッシュ木用許容メモリ量）以内に
収まる部分木に分割される。そのため、まず、ハッシュ
木容量確認用集合が形成される。当初空集合であるこの
ハッシュ木容量確認用集合に、候補品目セット生成部１
０２２から候補品目セットＣｋを読出して順次品目セッ
トを追加し、その度にそのハッシュ木容量確認用集合の
要素の品目セット全てを構成するのに必要なノードの容
量の合計を調べ、容量がハッシュ木用許容メモリ量を超
える一つ前の品目セットをハッシュ木操作部１０２３に
記憶し、ハッシュ木容量確認用集合をリセット、すなわ
ち空集合に戻す。このハッシュ木用許容メモリ量は計算
機ハードウェアが実装しているメモリの数分の１（例え
ば１０分の１）とすればよい。最初の品目セットからハ
ッシュ木用許容メモリ量を超える前の品目セットまでで
構成されるのが第１の部分木である。

【０２３５】次に、空集合のハッシュ木容量確認用集合
に対して、第１の部分木形成時、ハッシュ木用許容メモ
リ量を超えた時最後に追加した品目セットから順に、容
量がハッシュ木用許容メモリ量をこえるまで候補品目セ
ットを追加していく。そして必要なメモリ量がハッシュ
木用許容メモリ量を超える一つ前の品目セットをハッシ
ュ木操作部１０２３に記憶し、それまでのハッシュ木容
量確認用集合をリセットする。このハッシュ木用許容メ
モリ量を超える一つ前の品目セットを追加した段階の集
合によって出来る木が第２の部分木である。この様にし
て、第３、４、・・・の部分木を作り、全ての候補品目
セットがいずれかの部分木に割り当てられるまで操作を
繰り返す。図３９の（１）のハッシュ木を部分木に分割
した例を、図３９の（２）に示す。この時、項数がｋ未
満の候補品目セットは部分木に含まないように操作す
る。ハッシュ木操作部１０２３には、各部分木の最後の
品目セットが記憶される。

【０２３６】次にＬｋ生成のステップ１２４０の詳細を
説明する。まず、ハッシュ木中の第１の部分木に存在す
る候補品目セットについて、データベース中のレコード
を一件ずつ取り出してｋ項組の候補品目セットの支持度
を集計し、最終的に最小支持度を超えたｋ項組のみを大
品目セットＬｋの要素として残す。このｋ項組のカウン
トのためにレコードとハッシュ木の照合（マッチング）
が行われる。

【０２３７】このマッチングは、まず、第１のハッシュ
木のｒｏｏｔにおいてデータベースのレコードが一件ず
つ取り出され、各レコード中にｒｏｏｔの子ノードの品
目が存在するかどうか検査する。存在しなければそのレ
コードについてのマッチングは終了し、次のレコードを
検査する。存在すれば、その品目が対応付けられている
子ノードにおいて、さらに次の子ノード（ｒｏｏｔから
見ると“孫”）に対応付けられている品目がこのレコー
ド中に存在するかどうかを検査する。以後この操作を繰
り返すが、適用されるノードの子ノードがそれ以下に枝
を持たないノード、すなわち葉であり、なおかつそのレ
コード中に葉であるその子ノードに対応している品目が
存在する場合はこの葉ノードの支持度集計用カウントを
増やす操作を行い、このレコードについてのマッチング
を終了する。すべてのレコードについてマッチングが終
了したときの各葉ノードの支持度集計用カウントの値
が、各ｋ項組（ｒｏｏｔからその葉ノードにいたるまで
の品目の組）の支持度である。このようにして各ｋ項組
の支持度をカウントし、最小支持度以上の支持度をもつ
ｋ項組をすべて要素として選択した大品目セットＬｋを
生成し、大品目セット１００２に保存する。

【０２３８】次に、第２の部分木についても第１の部分
木と同様にレコードとハッシュ木の照合（マッチング）
が行われ、最終的に最小支持度を超えたｋ項組のみをＬ
ｋの要素として残す。以後同様に、全ての部分木につい
て支持度を集計し、大品目セットを抽出し、大品目セッ
ト１００２に保存する。

【０２３９】Ｌｋ生成のステップでＬｋの要素となるｋ
項組みが一つも生成されなかった場合はステップ１２６
０のルール候補生成に進み、そうでない場合はｋの値を
一つ増やし、Ｃｋ生成のステップに戻る。

【０２４０】ステップ１２６０のルール候補生成ではル
ール候補生成部１０４１により、それまでのステップで
作成された大品目セット１００２よりルールの候補が作
られる。Ｌｋ中のあるｋ項組みからは、右辺にその中の
一つの品目、左辺に残りのｋ−１個の品目がくる計ｋ個
のルール候補が生成される。これが、ｋ＝２以上の全て
のＬｋのｋ項組みについて成される。

【０２４１】ステップ１２７０のルール検証では、確信
度計算部１０４２により各ルール候補の確信度が計算さ
れ、それが最小確信度を上回る場合には相関ルール集合
に追加される。ここで、すでに述べたように、ルール候
補のＡ１，Ａ２，・・・Ａｋ→Ｂの確信度（ｃｏｎｆｉ
ｄｅｎｃｅ）は、品目セットθの支持度をｓ（θ）とす
ると、 confidence=s(A1,A2,・・・Ak,B)/s(A1,A2,・・・Ak) と計算される。

【０２４２】この時点では、各左辺は大品目セットに相
当するため、その支持度はすでに求められている。

【０２４３】以上のように、本実施の形態では、主に、
ハッシュ木を所定の容量以内の部分木に分割するハッシ
ュ木分割ステップと、上記分割された部分木毎にデータ
ベースとのマッチングを行い、大品目セットＬ（ｋ）を
選択するＬｋ生成ステップを備えた相関ルール生成方法
および各ステップの処理を行なう相関ルール生成装置に
ついて説明した。

【０２４４】従って、ハッシュ木のページングが起こり
にくくなり、処理時間が短縮されるという効果がある。

【０２４５】実施の形態１９．以下、本発明における実
施の形態１９の説明を図３７、図４０、図４１を用いて
行う。図について説明すると、図３７は本実施形態のシ
ステム図、図４０は本実施形態のブロック図、図４１は
本実施形態における大品目セットファイル読み込みから
ルール生成までを示す図である。図３７における候補品
目セット検証部１０２１とハッシュ木操作部１０２３以
外は実施の形態１８における同じ名前の部と同様の役割
を果たす。

【０２４６】実施の形態１８においては、Ｌ１の要素と
して抽出された品目の番号は当初の番号のままであった
が、本実施形態はＬ１で抽出された品目の番号を支持度
の大きい順に振り直すものである。

【０２４７】以下、図４０のブロック図に従って本実施
例における相関ルール生成の手順を説明する。まず最初
のステップ１３００で、ユーザ入力でユーザ入力部１０
１０により、ユーザから最小支持度と最小確信度を取得
する。

【０２４８】次にステップ１３１０のＬ１生成は、実施
の形態１８のステップ１２１０、Ｌ１生成と同じ動作を
行った後、支持度の大きい順に各品目に割り当てられる
番号を振り直す作業を行う。すなわち、ステップ１３１
０においては、候補品目セット検証部１０２１が、デー
タベース中のレコードを一つずつ取り出して、そのレコ
ード中に出現する各品目について、出現する回数をカウ
ントし、そのカウント数である支持度を増やす。初めて
出現する品目については、そのカウントの領域を新たに
設ける。そして、全てのレコードについて数え上げが終
了すると、最終的な支持度が最小支持度を超えた品目に
ついて、支持度の大きい順に各品目に割り当てられる番
号を降り直す作業を行い、大品目セットＬ１としてハッ
シュ木に登録を行う。これにより、ハッシュ木は１から
ｎ（最小支持度を超える品目の数）までの数により構成
され、かつその範囲の任意の番号はハッシュ木中のいず
れかのノード番号として割り当てられる。

【０２４９】ステップ１３２０のハッシュ木分割では、
ハッシュ木操作部１０２３が長さｋ−１の大品目セット
の集合Ｌｋ−１を格納するハッシュ木の分割を行う。そ
のために、まず、ハッシュ木容量確認用集合が形成され
る。当初空集合であるこのハッシュ木容量確認用集合
に、昇順が最小の品目セットから昇順に品目セットを追
加し、その度にその集合の要素の品目セット全てを構成
するのに必要なノードの容量の合計を調べ、容量が所定
の値（初期ハッシュ木用許容メモリ量）を超える一つ前
の品目セットをハッシュ木操作部１０２３に記憶し、ハ
ッシュ木容量確認用集合をリセット、すなわち空集合に
戻す。

【０２５０】この初期ハッシュ木用許容メモリ量はハッ
シュ木用許容メモリ量の数分の１とすればよい。ハッシ
ュ木用許容メモリ量については、実施の形態１８と同
様、計算機ハードウェアが実装しているメモリの量の数
分の１とすればよい。次に前回追加されなかった品目セ
ット中最小のものから順番に、必要なメモリ量が初期ハ
ッシュ木用許容メモリ量の限界にくるまでハッシュ木容
量確認用集合に入れていく。これを繰り返し、Ｌｋ−１
を必要なメモリ量が初期ハッシュ木用許容メモリ量の範
囲に収まる、連続した大品目セットのいくつかの集合に
分割し、部分木を作る。

【０２５１】次のステップ１３３０のＣｋ生成からステ
ップ１３５０のルール生成までは各部分木について行わ
れる。ステップ１３３０のＣｋ生成は候補品目セット生
成部１０２２が実行するが、部分木のノードのみでは実
施の形態１８のｊｏｉｎステップの様な木の枝伸ばしが
出来ないため、ある末端のノードについては、そのノー
ドに割り当てられた番号より大きくかつｎ以下の番号の
ノードが機械的に新たに作成され、それらへのリンクが
設定される。実施の形態１８におけるＣｋ生成のｊｏｉ
ｎステップにおいては、ある末端のノードについては、
同じ親ノードを持ち、かつ末端のノードの品目番号がそ
のノードの品目番号より大きい他のノードの末端の品目
をそのノードの子ノードとして追加して、枝を伸ばして
いるが、ここでは親ノードに無関係に新たな番号を付加
する。品目番号を１からｎまでの連続した番号に振りな
おしてあるため、この操作は容易である。例えば図４１
の（１）の部分木において、支持度を超える品目の数が
５だとすると、大品目セット［１，２］の下には３、
４、５の３つのノードが設定され、［１，２，３］、
［１，２，４］、［１，２，５］の３つの候補品目セッ
トが生成されることになる。［１，３］についても同様
の方法で枝を伸ばし、このステップでは最終的には図４
１（２）の様な木となる。以上の様に、ここでは実施の
形態１８のようなｐｒｕｎｅステップは行わない。

【０２５２】Ｌｋ生成のステップ１３４０の動作は実施
の形態１８におけるＬｋ生成のステップと同様であり、
各ｋ項組のカウントのためにレコードとハッシュ木のマ
ッチングを行い、最小支持度を超えたｋ項組のみをＬｋ
の要素として残す。図４１の部分木においては（３）の
様に二つの大品目セットが残ったとする。

【０２５３】ルール生成のステップ１３５０では部分木
中の長さｋの大品目セットの各々を基にしたｋ個のルー
ルの検証を行う。例えば、大品目セット［１，２，３］
については、１，２→３、１，３→２、２，３→１の３
個のルールの検証が行われる。これらのルールの検証に
はｋ個の長さｋ−１の大品目セットの支持度が必要なの
であるが、これらは注目している長さｋの大品目セット
が存在する部分木に含まれているとは限らないので、部
分木に含まれないノードを部分木に追加することにな
る。従って部分木に含まれていない長さｋ−１の大品目
セットの分も含めてメモリに入り切る必要があり、ハッ
シュ木分割の段階で使うメモリ量の限界である初期ハッ
シュ木許容メモリ量を実際に使えるメモリ量であるハッ
シュ木用許容メモリ量よりも少なく設定するのはそのた
めである。図４１においては、ルール生成のためにノー
ドを追加した部分木は（４）の様になる。追加したノー
ドに至る枝は破線で示してある。実施の形態１８と同様
に、この時点では、各左辺は大品目セットに相当するた
め、その支持度は、すでに求められている。

【０２５４】このＣｋ生成からルール生成までのステッ
プが全ての部分木について行われ、各部分木で作成され
た長さｋの大品目セットの合計が０であれば、プログラ
ムは終了する。そうでなければｋの値を一つ増やしてハ
ッシュ木分割のステップに戻る。

【０２５５】以上のように、本実施の形態では、主に、
Ｌ１生成ステップは、下限値Ｓｍｉｎ以上である品目に
任意の連続番号を割り当て、Ｃｋ生成ステップとＬｋ生
成ステップとルール候補生成ステップとルール検定ステ
ップは、各ステップの処理を上記分割された部分木毎に
実行する相関ルール生成方法および各ステップの処理を
行なう相関ルール生成装置について説明した。

【０２５６】従って、ハッシュ木のページングが起こり
にくくなり、処理時間が短縮されるという効果がある。

【０２５７】また、本実施の形態では、Ｌ１生成ステッ
プは、支持度が下限値Ｓｍｉｎ以上である品目に、その
支持度が大きい順に１からの連続番号を割り当てる相関
ルール生成方法および各ステップの処理を行なう相関ル
ール生成装置について説明した。

【０２５８】従って、部分木においても候補品目セット
Ｃ（ｋ）の生成が容易であるという効果がある。

【０２５９】実施の形態２０．以下、実施の形態２０の
説明を図４２〜図４５を用いて行う。まず、図について
説明すると、図４２は本実施形態におけるシステム図、
図４３は本実施形態のブロック図、図４４は本実施形態
における大品目セットの図、図４５は本実施形態におけ
る大品目セットファイル読み込みからルール生成までを
示す図である。

【０２６０】図４２における候補品目セット検証部１０
２１、ハッシュ木操作部１０２３、ルール候補生成部１
０４１以外は実施の形態１９の図３７における同じ名前
の部と同様の役割を果たす。ハッシュ木操作部１０２３
は大品目セットファイル１００４により大品目セットを
管理し、ハッシュ木を生成したり、破棄したりする役割
を持つ。

【０２６１】以下、図４３のブロック図に従って本実施
例における相関ルール生成の手順を説明する。ステップ
１８００のＬ１生成では、実施の形態１８のステップ１
２１０、Ｌ１生成と同じ動作を行った後、支持度の大き
い順に各品目に割り当てられる番号を降り直す作業を行
う。すなわち、ステップ１８００においては、候補品目
セット検証部１０２１が、データベース中のレコードを
一つずつ取り出して、そのレコード中に出現する各品目
について、出現する回数をカウントし、そのカウント数
である支持度を増やす。初めて出現する品目について
は、そのカウントの領域を新たに設ける。そして、全て
のレコードについて数え上げが終了すると、最終的な支
持度が最小支持度を超えた品目について、支持度の大き
い順に各品目に割り当てられる番号を降り直す作業を行
い、大品目セットＬ１としてハッシュ木に登録を行う。

【０２６２】これにより、ハッシュ木は１からｎ（最小
支持度を超える品目の数）までの数により構成され、か
つその範囲の任意の番号はハッシュ木中のいずれかのノ
ード番号として割り当てられる。

【０２６３】そして、生成されたＬ１がハッシュ木操作
部１０２３により大品目セットファイル１００４に格納
される。大品目セットファイル１００４は図４４の様
に、大品目セットを構成する品目とその支持度を格納し
たファイルである。図４４の例では長さ２の大品目セッ
トが格納されているが、その１行目については、［１，
２］なる大品目セットがあり、その支持度が１０である
ことを示す。このステップ１８００で出来る大品目セッ
トファイル１００４は長さ１の大品目セットを格納して
いる。

【０２６４】ステップ１８１０の大品目セットファイル
読み込みでは長さｋ−１の大品目セットを大品目セット
ファイルの読み込み位置から一つ読み出し、ハッシュ木
に追加する。そして、大品目セットファイルの読み込み
位置を大品目セットの一つ分だけ進める。この読み込み
位置は、Ｌ１生成直後は、大品目セットファイルの先頭
であり、ハッシュ木は大品目セットを全く含まない状態
である。以降の説明の例示のため、このステップ実行前
の時点で、［１，２］がハッシュ木に登録されていて、
このステップでは図４４の大品目セットファイルから
［１，３］が抽出され、ハッシュ木に追加されたとす
る。その時のハッシュ木を図４５の（１）に示す。

【０２６５】ステップ１８２０のＣｋ生成は候補品目セ
ット生成部１０２２が実行するが、部分木のノードのみ
では実施の形態１８のｊｏｉｎステップの様な木の枝伸
ばしが出来ないため、実施の形態１９と同様に、ある末
端のノードについては、そのノードに割り当てられた番
号より大きくかつｎ以下の番号のノードが新たに作成さ
れ、それらへのリンクが設定される。品目番号を連続し
た１からｎまでの連続した番号に振りなおしてあるた
め、この操作は容易である。例えば、支持度を超える品
目の数が５だとすると、大品目セット［１，２］の下に
は３、４、５の３つのノードが設定され、［１，２，
３］、［１，２，４］、［１，２，５］の３つの候補品
目セットが生成されることになる。図４５の例では、こ
の段階でのハッシュ木の状態は図４５の（２）である。
以上の様に、ここでは実施の形態１８のようなｐｒｕｎ
ｅステップは行わない。

【０２６６】このＣｋ生成のステップの後、ステップ１
８３０でハッシュ木の容量の検査が行われる。この容量
が初期ハッシュ木用許容メモリ量に達していれば、Ｌｋ
生成のステップ１８４０に進み、そうでなければ大品目
セットファイル読み込みステップ１８１０に戻る。この
初期ハッシュ木用許容メモリ量はハッシュ木用許容メモ
リ量の数分の１とすればよく、また、ハッシュ木用許容
メモリ量については、実施の形態１８と同様、計算機ハ
ードウェアが実装しているメモリの量の数分の１とすれ
ばよい。ただし、大品目セットファイル読み込みステッ
プ１８１０に戻っても、すべての大品目セットを読み込
み終っている場合はステップ１８４０に進む。

【０２６７】Ｌｋ生成のステップ１８４０は候補品目セ
ット検証部１０２１によって実行されるが、その動作は
実施形態１におけるＬｋ生成のステップと同様であり、
各ｋ項組のカウントのためにレコードとハッシュ木のマ
ッチングを行い、最小支持度を超えたｋ項組のみをＬｋ
の要素として残す。そして、生成された長さｋの大品目
セットを大品目セットファイル１００４内に構成される
仮大品目セットファイルに格納する。図４５の例では、
最小支持度を超える大品目セットが［１，２，３］と
［１，３，４］である場合、この段階でのハッシュ木の
状態は（３）である。

【０２６８】ルール生成のステップ１８５０ではハッシ
ュ木中の長さｋの大品目セットの各々を基にしたｋ個の
ルールの検証を行う。例えば、大品目セット［１，２，
３］については、１，２→３、１，３→２、２，３→１
の３個のルールの検証が行われる。これらのルールの検
証にはｋ個の長さｋ−１の大品目セットの支持度が必要
なのであるが、これらはこの段階で存在するハッシュ木
に含まれているとは限らない。従ってルール候補生成部
１０４１はハッシュ木に含まれていない長さｋ−１の大
品目セットをハッシュ木操作部１０２３を通じて大品目
セットファイル１００４から読み込むことになる。長さ
ｋの大品目セットの支持度が最小支持度を超えているの
で、これから１つの品目を除いた長さｋ−１の大品目セ
ットの支持度は長さｋの大品目セットの支持度以上であ
り、長さｋ−１の大品目セットは大品目セットファイル
１００４に格納されている。従って部分木に含まれてい
ない長さｋ−１の大品目セットの分も含めてメモリに入
り切る必要があり、ハッシュ木分割の段階で使うメモリ
量の限界である初期ハッシュ木許容メモリ量を実際に使
えるメモリ量であるハッシュ木用許容メモリ量よりも少
なく設定するのはそのためである。図４５の例では、こ
の段階でのハッシュ木の状態は（４）である。追加した
ノードに至る枝は破線で示してある。

【０２６９】このＣｋ生成からルール生成までのステッ
プが終了すると、もし最近実行したステップ１８１０の
大品目セットファイル読み込みで大品目セットファイル
中の全ての大品目セットの読み込みが終了していなけれ
ば、そのまま大品目セットファイル読み込みのステップ
１８１０に戻る。大品目セットの読み込みが終了してい
て、さらに仮大品目セットファイル中の長さｋの大品目
セットの数が０であれば、プログラムは終了する。仮大
品目セットファイル中の長さｋの大品目セットの数が０
でなければ、ｋの値を一つ増やして、それまでに生成さ
れた仮大品目セットファイルをファイル名変更等によっ
て大品目セットファイルとし、その読み込み位置をファ
イルの先頭にして大品目セットファイル読み込みのステ
ップに戻る。

【０２７０】図４５の例では、ルール生成のステップ１
８５０が終った時に（４）の木は破棄され、図４４の大
品目セットファイルの前回の読み込み位置である［１，
３］の次の、［１，４］が読み込まれ、図４５の（５）
の様なハッシュ木が構成される。

【０２７１】また、本実施形態において、初期ハッシュ
木用許容メモリ量をＷｉとすると、ハッシュ木用許容メ
モリ量がＷの時、Ｗｉ＝Ｗ／ｋと見積もるようにしても
よい。これは、ルール生成の段階で必要となる長さｋ−
１の大品目セットの個数が大品目セット生成のステップ
で生成された大品目セットのｋ倍以下であることによ
る。

【０２７２】この値については、ｋの値が前回実行され
たこのステップと同様の場合、前回作成されたハッシュ
木のルール生成のステップでの最終容量がＷを下回る場
合、その差の数分の１を上の式に追加して初期ハッシュ
木用メモリ量の値とする等の修正を行ってもよい。

【０２７３】以上のように、本実施の形態では、主に、
各品目に任意の連続番号を割り当てた後、大品目セット
Ｌ（１）の情報を大品目セットファイルに保存するＬ１
生成ステップと、大品目セットファイルから大品目セッ
トＬ（ｋ−１）中のｋ−１項組の情報を読み込み、ハッ
シュ木に格納する、大品目セットファイル読み込みステ
ップと、候補品目セットＣ（ｋ）を格納しているハッシ
ュ木の容量を使用許容容量を超えない所定の容量と比較
して、ハッシュ木の容量の方が小さい場合は上記大品目
セットファイル読み込みステップに戻り、そうでない場
合は次ステップに進む容量判定ステップを有する相関ル
ール生成方法および各ステップの処理を行なう相関ルー
ル生成装置について説明した。

【０２７４】従って、ページングが起こらず、処理時間
が短縮されるという効果がある。

【０２７５】また、本実施の形態では、ルール生成ステ
ップにおいて、ｋ−１項組の支持度を大品目セットファ
イルから読み出す相関ルール生成方法および各ステップ
の処理を行なう相関ルール生成装置について説明した。

【０２７６】従って、データベース検索が不要になり、
処理時間が短縮されるという効果がある。

【０２７７】また、本実施の形態では、大品目セットフ
ァイル読み込みステップでは、品目セットを１個ずつ読
み込む相関ルール生成方法および各ステップの処理を行
なう相関ルール生成装置について説明した。

【０２７８】従って、品目セットの容量の確認が容易で
あるという効果がある。

【０２７９】また、本実施の形態では、所定の容量は、
使用許容容量のｋ分の１である相関ルール生成方法およ
び各ステップの処理を行なう相関ルール生成装置につい
て説明した。

【０２８０】従って、必要以上のメモリを確保すること
がなくなり効率的にメモリを利用することができるとい
う効果がある。

【０２８１】実施の形態２１．以下、本発明における実
施の形態２１の説明を図４２〜図４４を用いて説明す
る。図について説明すると、図４２は本実施形態におけ
るシステム図、図４３は本実施形態のブロック図、図４
４は本実施形態における大品目セットファイルの図であ
る。

【０２８２】実施の形態２０においては、大品目セット
Ｌ１を大品目セットに格納する順については特に制限し
なかったが、本実施形態は、長さ１の大品目セットＬ１
を、大品目セットファイルに昇順に、すなわち番号１か
ら順にｎまで格納するものである。

【０２８３】図４３のステップ１８００のＬ１生成は実
施の形態２０と同様の動作を行うのであるが、大品目セ
ットファイル１００４には、長さ１の大品目セットを昇
順に格納していく。すなわち、候補品目セット検証部１
０２１が、データベース中のレコードを一つずつ取り出
して、そのレコード中に出現する各品目について、出現
する回数をカウントし、そのカウント数である支持度を
増やす。初めて出現する品目については、そのカウント
の領域を新たに設ける。そして、全てのレコードについ
て数え上げが終了すると、最終的な支持度が最小支持度
を超えた品目について、支持度の大きい順に各品目に割
り当てられる番号を振り直す作業を行い、大品目セット
Ｌ１としてハッシュ木に登録を行う。この時、大品目セ
ットファイルには各品目を昇順に格納する。また、これ
により、ハッシュ木は１からｎ（最小支持度を超える品
目の数）までの数により構成され、かつその範囲の任意
の番号はハッシュ木中のいずれかのノード番号として割
り当てられる。したがって、以降大品目セットファイル
中の大品目セットの長さ（ｋ−１）が増えていっても、
その中の大品目セットは昇順にソートされて格納される
ことになる。この後の動作は実施の形態２０と同様であ
る。

【０２８４】こうすれば、ルール生成のステップ１８５
０において、ハッシュ木に含まれていない長さｋ−１の
大品目セットの読み込みは、大品目セットファイル中の
前回の大品目セットファイル読み込みのステップでの読
み込み位置から以降を読み込む事になり、処理速度が向
上する。

【０２８５】また、本実施形態において、大品目セット
ファイルが各大品目セットの支持度の情報を持っていな
いくてもよい。この場合、ルール検証において、ルール
候補生成部１０４１はハッシュ木に含まれていない長さ
ｋ−１の大品目セットのためのノードを追加し、その支
持度についてはデータベースの集計を新たに実行して求
める。

【０２８６】また、本実施形態におけるルール検証にお
いて、データベースのデータファイルの大きさと、大品
目セットファイルの大きさの比較を行い、前者の方が小
さい場合はデータベースの集計を新たに実行して支持度
を求め、後者の方が小さい場合は、該当する大品目セッ
トを大品目セットファイルから検索して支持度を求める
ようにしてもよい。この場合処理速度が向上する。

【０２８７】以上のように、本実施の形態では、主に、
大品目セットファイル中の大品目セットが昇順にソート
されている相関ルール生成方法および各ステップの処理
を行なう相関ルール生成装置について説明した。

【０２８８】従って、ルール生成のステップで新たに読
み込む大品目セットの大品目セットファイル上の位置が
限定されるので、処理時間が短縮されるという効果があ
る。

【０２８９】また、本実施の形態では、ルール生成ステ
ップにおいて、ｋ−１項組の支持度をデータベースとの
マッチングにより求める相関ルール生成方法および各ス
テップの処理を行なう相関ルール生成装置について説明
した。

【０２９０】従って、大品目セットに支持度を書き込む
必要がないので、処理時間が短縮されるという効果があ
る。

【０２９１】また、本実施の形態では、ルール生成ステ
ップにおいて、大品目セットファイルとデータベースの
サイズを比較し、小さい方からｋ−１項組の支持度を求
める相関ルール生成方法および各ステップの処理を行な
う相関ルール生成装置について説明した。

【０２９２】従って、不要なレコードの探索が少なくな
り、効率的な支持度獲得が行え、処理時間が短縮される
という効果がある。

【０２９３】実施の形態２２．以下、本発明における実
施の形態２２の説明を図４２、図４３、図４６を用いて
行う。図について説明すると、図４２は本実施形態にお
けるシステム図、図４３は本実施形態のブロック図、図
４６は本実施形態におけるルール候補生成の過程を示す
図である。図４２における候補品目セット生成部１０２
２とハッシュ木操作部１０２３以外は実施の形態２１に
おける同じ名前の部と同様の役割を果たす。

【０２９４】実施の形態２１では、大品目セットファイ
ル読み込みの際には、そのハッシュ木の容量にのみ着目
し、枝を構成する品目には着目していなかったが、本実
施形態では、大品目セットファイル読み込みに際して、
大品目セットの最後の品目以外の品目が共通するものを
一挙に読み出すようにしたものである。

【０２９５】以下、図４３のブロック図に従って本実施
例における相関ルール生成の手順を説明する。本実施例
ではブロック図４３中の大品目セットファイル読み込み
のステップ１８１０とＣｋ生成のステップ１８２０以外
は第２の発明の実施例と同様の動作であるため、この２
つステップのみの説明を行う。

【０２９６】ハッシュ木操作部１０２３によって実行さ
れる大品目セットファイル読み込みのステップ１８１０
では、大品目セットファイル中の読み込み位置から、大
品目セットの最後の品目以外の品目が共通するものを一
挙に読み出す。すなわち、大品目セットの最後の品目以
外の品目が共通するものは必ず同じハッシュ木に入る様
にする。最小支持度を超える品目の数を５とし、図４６
の（１）の様な長さ２の大品目セットを格納したハッシ
ュ木を例に、説明する。

【０２９７】実施の形態２１の方法では、図４６の
（２）の様に一回目のループでのハッシュ木、２回目の
ループでのハッシュ木が構成される可能性がある。ここ
では［２，３］と［２，４］が別のハッシュ木に割り当
てられている。［２，３］の末端のノード３からは、そ
の親ノードである２を共通の親ノードとする他のノード
（この場合は４）の存在が見えないため、実施の形態１
８で説明した図５５のｊｏｉｎステップのような枝伸ば
しができない。そこで、３の下には、３を超え５以下で
あるすべてのノード、すなわち４と５を設け、同様に
［２，４］の末端のノード４の下には４を超え５以下で
ある５のノードを設ける必要がある。

【０２９８】これに対して本実施形態では図４６（３）
の様に［２，３］と［２，４］は同じハッシュ木に割り
当てられる。この状態では、実施の形態１８で図５３〜
図５４に示したｊｏｉｎステップの手順により、枝伸ば
しが可能である。従って、［２，３］の末端のノード３
の下には、共通の親ノード２を持ち、自分より大きな品
目番号である４を設け、［２，４］の末端のノード４の
下には、共通の親ノード２を持ち、自分より大きな品目
番号が存在しないので、ノード追加を行わなくてよい。
この方法によれば、候補品目セットＣｋの数が少なくな
るので、大品目セットＬｋ生成のための処理が速くなる
という効果がある。

【０２９９】また、本実施形態においては、大品目セッ
トの最後の品目以外の品目が共通するものを一挙に読み
出すが、この読み出しの際に、ステップ１８１０で一挙
に読み出した品目セットの容量を、ステップ１８１０内
で初期ハッシュ木許容メモリ量と比較して、初期ハッシ
ュ木許容メモリ量を超えている場合は、この品目セット
を特殊木として処理するようにしてもよい。この場合、
Ｃｋステップ１８２０では、特殊木でない品目セットか
らなるハッシュ木について、図５３〜図５４に示した実
施の形態１８と同様のｊｏｉｎステップの手順により、
枝伸ばしを行う。また、特殊木の場合は、順次初期ハッ
シュ木許容メモリ量に収まる大きさの部分木に分割し、
それぞれの部分木について、実施の形態２０におけるＣ
ｋ生成ステップと同様に、ある末端のノードについて、
そのノードに割り当てられた番号より大きくかつｎ以下
の番号のノードを新たに作成し、それらへのリンクを設
定する。

【０３００】以上のように、本実施の形態では、主に、
大品目セットファイル読み込みステップは、ｋ−１項組
中の最後尾の品目以外の品目が全て共通する品目セット
を同時に読み込み、それらを同一のハッシュ木に格納す
る相関ルール生成方法および各ステップの処理を行なう
相関ルール生成装置について説明した。

【０３０１】従って、候補品目セットの数が少なくな
り、処理時間が短縮されるという効果がある。

【０３０２】また、本実施の形態では、最後尾の品目以
外の品目が全て共通する品目セットの容量が所定の容量
をこえる場合、この大品目セットを該所定の容量以内の
容量の複数のハッシュ木に分割する相関ルール生成方法
および各ステップの処理を行なう相関ルール生成装置に
ついて説明した。

【０３０３】従って、ページングが起きる可能性が少な
くなり、処理時間が短縮されるという効果がある。

【０３０４】また、本実施の形態では、Ｃｋステップに
おいて、ハッシュ木の先端ノードに、その先端ノードに
対応する品目番号より大きな品目番号すべてを付加し
て、ハッシュ木を伸ばす相関ルール生成方法および各ス
テップの処理を行なう相関ルール生成装置について説明
した。

【０３０５】従って、部分木においても候補品目セット
Ｃ（ｋ）の生成が容易であるという効果がある。

【０３０６】実施の形態２３．以下、本発明における実
施の形態２３の説明を図４７および図４８を用いて行
う。図について説明すると、図４７は本実施形態におけ
るシステム図である。図４７における許容メモリ量獲得
部１０１１以外は第３の発明の実施例における図４２の
同じ名前の部と同様の役割を果たす。

【０３０７】これまでに説明した実施の形態では、ハッ
シュ木用許容メモリ量は予めシステムで設定されていた
が、本実施形態では、ユーザが指定するものである。

【０３０８】以下、図４８のブロック図に従って本実施
例における相関ルール生成の手順を説明する。本実施例
ではブロック図４８中の許容メモリ量取得のステップ１
８０１以外は第３の実施例におけるブロック図４３の同
名のブロックと同様の動作であるため、このステップの
みの説明を行う。

【０３０９】許容メモリ量獲得のステップ１８０１で
は、初期の部分木およびその後の枝伸ばしとルール検証
で使用可能なメモリ量であるハッシュ木用許容メモリ量
をユーザが入力して指定する。Ｃｋ生成のステップ終了
後の容量の検査で用いるハッシュ木の初期ハッシュ木用
許容メモリ量はその数分の１として計算される。ユーザ
は過去のプログラムの実行履歴等を基にして自由にこの
メモリ量を設定する。その入力形式については、ダイア
ログボックスを出して入力させてもよいし、コマンドラ
インからのプログラムの起動の場合は引数として指定す
る様にしてもよい。

【０３１０】また、ハッシュ木用許容メモリ量獲得のス
テップ１８０１では、ハッシュ木のために使用可能なメ
モリ量であるハッシュ木用許容メモリ量を決定するため
に、システムコール等の手段によって本ステップの実行
時点で空いているメモリ量をオペレーティングシステム
から取得するようにしてもよい。ハッシュ木用許容メモ
リ量はその数分の１とする。Ｃｋ生成のステップ終了後
の容量の検査で用いるハッシュ木の初期ハッシュ木用許
容メモリ量はその数分の１として計算される。

【０３１１】また、本実施形態において、図４９のよう
にメモリ開放部を設け、ハッシュ木用許容メモリ量を確
保してもよい。すなわち、許容メモリ量獲得のステップ
１８０１では、ハッシュ木のために使用可能なメモリ量
をシステムコール等の手段によってオペレーティングシ
ステムから取得する前に、メモリを大量に確保するプロ
セスを発生させ、そのメモリを解放して終了するプログ
ラムを実行させるようにしてもよい。これにより、本ス
テップ実行前の段階ではオペレーティングシステムが占
有していたが、実際には使っていなかったメモリ領域が
開放され、相関ルール生成プログラムはより多くのハッ
シュ木用許容メモリ量を確保できることになる。

【０３１２】以上のように、本実施の形態では、主に、
使用許容容量をユーザが決定するステップを備えている
相関ルール生成方法および各ステップの処理を行なう相
関ルール生成装置について説明した。

【０３１３】従って、ユーザの過去の経験等を生かした
メモリ設定が可能となるという効果がある。

【０３１４】また、本実施の形態では、使用許容容量を
オペレーティングシステムから取得する相関ルール生成
方法および各ステップの処理を行なう相関ルール生成装
置について説明した。

【０３１５】従って、確実なメモリ量の確保が可能とな
るという効果がある。

【０３１６】また、本実施の形態では、メモリ領域を確
保して解放するプログラムを実行するステップを有する
相関ルール生成方法および各ステップの処理を行なう相
関ルール生成装置について説明した。

【０３１７】従って、それまでオペレーティングシステ
ムに占有されていた領域を使うことができ、ハッシュ木
のために多くのメモリ領域を確保することができるとい
う効果がある。

【０３１８】実施の形態２４．以下、本発明における実
施の形態２４の説明を図４２、図５０を用いて行う。図
について説明すると、図４２は本実施形態におけるシス
テム図、図５０は本実施形態におけるブロック図であ
る。図４２における候補品目セット検証部１０２１と候
補品目セット生成部１０２２、ハッシュ木操作部１０２
３以外は実施の形態２０における図４２における同じ名
前の部と同様の役割を果たす。

【０３１９】実施の形態２０においては、Ｃｋ生成後そ
の容量が初期ハッシュ木用許容容量を超えたか否かを確
認し、その後、ルール形成のステップにおいてｋ−１項
組をハッシュ木に追加していたが、本実施形態では、Ｃ
ｋ生成後すぐにｋ−１項をハッシュ木に追加し、そのハ
ッシュ木の容量がハッシュ木用許容メモリ量を超えたか
否か確認するものである。

【０３２０】以下、図５０のブロック図に従って本実施
形態における相関ルール生成の手順を説明する。

【０３２１】ステップ１９００のＬ１生成は実施の形態
２０の同名のステップと同じ動作を行うのであるが、実
施の形態２０の場合と異なるのは、大品目セットファイ
ルが各大品目セットの支持度の情報を持っていないとい
う点である。

【０３２２】ステップ１９１０の大品目セットファイル
読み込みでは長さｋ−１の大品目セットを大品目セット
ファイルの読み込み位置から一つ読み出し、ハッシュ木
に追加する。そして、大品目セットファイルの読み込み
位置を大品目セットの一つ分だけ進める。この読み込み
位置は、このプログラム実行開始時は、大品目セットフ
ァイルの先頭であり、ハッシュ木は大品目セットを全く
含まない状態である。

【０３２３】ステップ１９２０のＣｋ生成では、ある末
端のノードからは、そのノードに割り当てられた番号よ
り大きくかつｎ以下の番号の新たに作成されるノードへ
の枝が設定される。例えば、支持度を超える品目の数が
５だとすると、大品目セット［１，３］の下には４、５
の２つのノードが設定され、［１，３，４］、［１，
３，５］の２つの候補品目セットが生成されることにな
る。

【０３２４】次にステップ１９３０のルール検証用品目
セット生成が行われる。ここでは、前ステップで追加さ
れた品目セットからルールを生成する場合に支持度が必
要となる品目セットが追加される。前ステップでは
［１，３，４］、［１，３，５］の２つの候補品目セッ
トが生成されたとすると、これらの品目セットからルー
ルを生成する場合は［１，３］、［３，４］、［１，
４］、［１，５］、［３，５］の５つの品目セットの支
持度が必要となる。これらのうちハッシュ木上に存在し
ないものがハッシュ木に追加されるが、これが本発明に
おける候補品目補助セットである。このステップの後、
ハッシュ木の容量の検査が行われる。この容量がハッシ
ュ木用許容メモリ量に達していれば、Ｌｋ生成のステッ
プに進み、そうでなければ大品目セットファイル読み込
みのステップに戻る。このハッシュ木用許容メモリ量は
計算機ハードウェアが実装しているメモリの量の数分の
１（例えば１０分の１）とすればよい。

【０３２５】候補品目セット検証部１０２１によるＬｋ
生成のステップ１９５０の動作ではハッシュ木上の長さ
ｋ−１の候補品目セットと長さｋの候補品目セットの支
持度がデータベースの検索を通じて集計され、生成され
た長さｋの大品目セットについては仮大品目セットファ
イルに追加される。この長さｋ−１の候補品目セット
が、本発明における候補品目補助セットである。実施の
形態２０におけるＬｋ生成のステップと異なるのは、こ
の候補品目補助セットである長さｋ−１の候補品目セッ
トの支持度の集計も同時に行う点と、仮大品目セットフ
ァイルに書き込む情報として、各大品目セットの支持度
は含まれないという点である。

【０３２６】ルール生成のステップ１９６０ではハッシ
ュ木中の長さｋの大品目セットの各々を基にしたｋ個の
ルールの検証を行う。例えば、大品目セット［１，２，
４］については、１，２→４、１，４→２、２，４→１
の３個のルールの検証が行われる。これらのルールの検
証に必要なｋ個の長さｋ−１の大品目セットはこの段階
では既にハッシュ木に含まれているため（長さｋ−１の
大品目セットは前のステップ１９５０の実行直前では長
さｋ−１の候補品目補助セットであったため）、実施の
形態２０の場合の様に大品目セットファイルから読み込
む必要はない。

【０３２７】このルール生成までのステップが終了する
と、もし最近のステップ１９１０の大品目セットファイ
ル読み込みで大品目セットファイル中の全ての大品目セ
ットの読み込みが終了していなければ、それまでのハッ
シュ木を破棄して大品目セットファイル読み込みのステ
ップ１９１０に戻る。そうでない場合、もし仮大品目セ
ットファイル中の長さｋの大品目セットの数が０であれ
ば、プログラムは終了する。そうでなければｋの値を一
つ増やして、それまで生成された仮大品目セットファイ
ルをファイル名変更等によって大品目セットファイルに
し、ハッシュ木を破棄して大品目セットファイル読み込
みのステップに戻る。この部分は実施の形態２０におけ
る図４３の同名のブロックと同様である。

【０３２８】以上のように、本実施の形態では、主に、
Ｃｋ生成ステップの後、容量判定ステップの前に、Ｃｋ
生成ステップで生成された候補品目セットＣ（ｋ）から
１品目を除いた候補品目補助セットを生成して、ハッシ
ュ木に格納するルール検証用品目セット生成ステップを
設け、Ｌｋ生成ステップでは上記候補品目セットＣ
（ｋ）中のｋ項組と候補品目補助セットの支持度をデー
タベースとのマッチングにより求める相関ルール生成方
法および各ステップの処理を行なう相関ルール生成装置
について説明した。

【０３２９】従って、ルール生成の速度が向上するとい
う効果がある。

【０３３０】実施の形態２５．本発明における大品目セ
ット生成の処理では、レコードの集合のためのメモリを
確保し、そこに入るだけのレコードをデータベース、あ
るいはデータファイルから読み込む。そして、読み込ま
れたレコード集合に対してマッチング処理を適用する。

【０３３１】マッチング関数は従来技術と同様に再帰的
に呼び出されるが、入力はハッシュ木のノード（ｎｏｄ
ｅ）と部分列集合（Ｐ）である。部分列集合（Ｐ）はレ
コード集合中の各レコードにおける部分列を指定したも
のである。図５９の例のようにレコード集合｛１，２，
３｝｛１，２，４｝｛１、３、４｝をメモリに読み込む
場合には、｛３｝｛２，４｝｛１，３，４｝は第１のレ
コードの３番目、第２のレコードの２番目、第３のレコ
ードの先頭以降の部分列からなる部分列集合である。レ
コード集合とハッシュ木のマッチングは、このマッチン
グ処理の入力をハッシュ木のｒｏｏｔ、レコード集合中
の各レコードの先頭以降の部分列集合に適用することに
よって実現される。

【０３３２】図５８に本実施の形態におけるマッチング
関数のブロック図を示す。ステップ２２００で入力され
たハッシュ木のノード（ｎｏｄｅ）が葉ノードの一つ上
であるか否か判断する。

【０３３３】入力されたハッシュ木のノード（ｎｏｄ
ｅ）が葉ノードの一つ上ではない場合は、ステップ２２
１０の処理を行なう。ステップ２２１０では、まず部分
列集合（Ｐ）中の品目の最小値（ｉ）を取得する。そし
て、その最小値（ｉ）の品目を含むレコードについて
は、その品目を除いた部分列を、最小値（ｉ）の品目を
含まないレコードについては、部分列｛｝をそれぞれ指
定した部分列集合を新たに作る。更に、その最小値
（ｉ）でハッシュ関数を適用して該当するノード（ｎｏ
ｄｅｉ）がその下に存在するか調べる。ステップ２２１
０で該当するノード（ｎｏｄｅｉ）がその下に存在する
場合は、そのノード（ｎｏｄｅｉ）と新たに作成した部
分列集合を入力としたマッチング関数を再帰的に呼び出
す。ステップ２２３０で元の部分列集合については、そ
のうち最小値（ｉ）の品目を含む部分列からその品目を
除き、部分列集合（Ｐ）を更新する。ステップ２２４０
で部分列集合（Ｐ）中の全ての部分列が｛｝となるまで
ステップ２２１０、２２２０、２２３０の処理を繰り返
す。

【０３３４】ステップ２２００で入力されたノードが葉
ノードの一つ上であると判断する場合は、ステップ２２
５０で部分列集合（Ｐ）中の各部分列について繰り返
し、ステップ２２６０で部分列中の各品目（ｉ）につい
てハッシュ関数を適用する。ステップ２２７０で該当す
る葉ノード（ｎｏｄｅｉ）が存在すれば、ステップ２２
８０でそのノードの支持度を一つ増やす。

【０３３５】図５９の例でハッシュ木のｒｏｏｔ、レコ
ード集合｛１，２，３｝｛１，２，４｝｛１、３、４｝
の各レコードの先頭以降の部分列の集合｛１，２，３｝
｛１，２，４｝｛１、３、４｝を入力としてマッチング
関数を適用する場合について説明する。ハッシュ木の高
さは２であるで、部分列集合生成の処理が行われる。

【０３３６】ステップ２２１０では、まず、部分列集合
の最小品目１である１を除いた部分列集合｛２，３｝
｛２，４｝｛３，４｝が作られる。そしてｒｏｏｔの下
にはノード［１］が存在すると判断する。ステップ２２
２０ではノード［１］と部分列集合｛２，３｝｛２，
４｝｛３，４｝を入力としたマッチング関数を再帰的に
呼び出す。ステップ２２３０では部分列集合を｛２，
３｝｛２，４｝｛３，４｝に更新する。ステップ２２４
０で部分列集合中の部分列のすべてが｛｝ではないの
で、ステップ２２１０の処理に戻る。

【０３３７】次のステップ２２１０で、更新された部分
列集合中の最小値の品目は２であり、ｒｏｏｔの下には
ノード［２］が存在すると判断する。ステップ２２２０
でノード［２］と部分列集合｛３｝｛４｝｛｝を入力と
したマッチング関数を再帰的に呼び出す。ステップ２２
３０で元の部分列集合を｛３｝｛４｝｛３，４｝に更新
する。

【０３３８】同様にループし、ステップ２２２０でノー
ド［３］と部分列集合｛｝｛｝｛４｝を入力としたマッ
チング関数を再帰的に呼び出す。ステップ２２３０で元
の部分列集合は｛｝｛４｝｛４｝となる。

【０３３９】４を除いた部分列集合は｛｝｛｝｛｝とな
るので処理のループはここで終了する。

【０３４０】次に、ノード［１］と部分列集合｛２，
３｝｛２，４｝｛３，４｝を入力としたマッチング関数
の動作についても説明する。ステップ２２００でこのノ
ードは葉の一つ上のノードであると判断する。ステップ
２２５０で各部分列集合中の品目２，３，２，４，３，
４の各々についてハッシュ関数を適用し、ステップ２２
８０で該当するノードの支持度を増やす。

【０３４１】ノード［２］と部分列集合｛３｝
｛４｝｛｝を入力としたマッチング関数、ノード［３］
と部分列集合｛｝｛｝｛４｝を入力としたマッチング関
数についても同様に処理する。

【０３４２】以上のように、本実施の形態では、主に、
データベースのレコードの集合と候補品目セットＣ
（ｋ）を格納するハッシュ木とを入力としてマッチング
を実行し、大品目セットＬ（ｋ）を選択するＬｋ生成ス
テップを有する相関ルール生成方法および各ステップの
処理を行なう相関ルール生成装置について説明した。

【０３４３】従って、複数のレコード中の共通する品目
の部分を一括してハッシュ関数に適用するため、再帰的
呼び出しの処理回数が減り、高速なマッチングが可能と
なるという効果がある。

【０３４４】実施の形態１から本実施の形態まで説明し
た相関ルール生成方法は、その方法の手順をコンピュー
タに課題解決のための機能を付与し得るプログラムとし
て、コンピュータ読み取り可能な形態で記憶媒体に記録
することができる。

【０３４５】

【発明の効果】第１の発明に係る相関ルール生成方法
は、大品目セットＬ（ｋ−１）を条件となる品目セッ
ト、大品目セットＬ（１）を結果となる品目セットとす
る相関ルール候補を生成するので、相関ルールの両辺全
ての品目からなる品目セットの支持度がいかなる値であ
っても、相関ルールを得ることができ、負の相関ルール
を抽出できるという効果がある。

【０３４６】また、第２の発明に係る相関ルール生成方
法は、相関ルールをχ² 値という統計量によって評価し
抽出を行うので、統計的に意味のある相関ルールのみを
得ることができるという効果がある。

【０３４７】また、第３の発明に係る相関ルール生成方
法は、仮説生成検証ステップに、相関ルールが正の相関
ルールか負の相関ルールかを判定する正負判定ステップ
を設けたので、効率的に正の相関ルールと負の相関ルー
ルを分けて抽出することができるという効果がある。

【０３４８】また、第４の発明に係る相関ルール生成方
法は、大品目セット生成ステップに、個別の品目の支持
度から支持度の下限値Ｓｍｉｎを算出する相関用限界支
持度決定ステップを備えたので、ユーザが最小支持度を
入力する必要が無く、また不要な支持度をもつルール候
補に関して検定を行うことが無いので効率的に相関ルー
ルを抽出することができるという効果がある。

【０３４９】また、第５の発明に係る相関ルール生成方
法は、大品目セット生成ステップに、支持度の最も小さ
な個別の品目の支持度を支持度の下限値Ｓｍｉｎと設定
する最小支持度決定ステップを備えたので、ユーザが最
小支持度を入力する必要がないという効果がある。

【０３５０】また、第６の発明に係る相関ルール生成方
法は、仮説生成検証ステップにおいて、ルール候補生成
ステップで相関ルール候補を生成する際に使用した大品
目セットＬ（ｋ−１）と大品目セットＬ（１）の対に対
して、該大品目セットＬ（ｋ−１）の支持度から該大品
目セットＬ（１）の支持度の限界値を算出する境界決定
ステップを備え、支持度が境界以内である大品目セット
Ｌ（１）とこれと対の大品目セットＬ（ｋ−１）から生
成された相関ルール候補のみをルール検定ステップでχ
² 検定を行うようにしたので、ユーザが最小支持度を入
力する必要が無く、また不要な支持度をもつルール候補
に関して検定を行うことが無いので効率的に相関ルール
を抽出することができるという効果がある。

【０３５１】また、第７の発明に係る相関ルール生成方
法は、ユーザが相関ルールの左辺または右辺の品目に関
する条件を入力するようにしたので、特定の品目に関す
る相関ルールを抽出できるという効果がある。

【０３５２】また、第８の発明に係る相関ルール生成方
法は、ユーザ入力ステップにおいて、ユーザは相関ルー
ル中の左辺にその中の１個以上が必ず含まれる１個以上
の品目と相関ルールの右辺にその中の１個以上が必ず含
まれる１個以上の品目を指定するようにしたので、特定
の品目に関する相関ルールが効率的に抽出できるという
効果がある。

【０３５３】また、第９の発明に係る相関ルール生成方
法は、ユーザ入力ステップにおいて、ユーザは相関ルー
ル中の左辺にすべてが必ず含まれる１個以上の品目と相
関ルールの右辺にすべてが必ず含まれる１個以上の品目
を指定するようにしたので、特定の品目に関する相関ル
ールが効率的に抽出できるという効果がある。

【０３５４】また、第１０の発明に係る相関ルール生成
方法は、ユーザ入力ステップにおいて、ユーザはデータ
ベース中のレコードの中から、特定の１以上の品目を持
つレコードの集合であるドメインを指定するために上記
１以上の品目を入力し、大品目セット生成ステップに
は、データベースから指定された上記ドメインに含まれ
るレコードのみを取り出し、以後データベース中のレコ
ード総数の代わりにこのドメインに含まれるレコードの
総数を使用するようにするドメイン限定ステップを設け
たので、ドメインを限定した場合の相関ルールを効率的
に抽出できるという効果がある。

【０３５５】また、第１１の発明に係る相関ルール生成
方法は、各個別の品目を品目番号によって表現し、上記
大品目セット生成ステップには、各品目の支持度の順に
品目番号を付ける品目番号再配置ステップを備えたの
で、効率的に相関ルールを抽出できるという効果があ
る。

【０３５６】また、第１２の発明に係る相関ルール生成
方法は、上記大品目セット生成ステップに、候補品目セ
ットＣ（ｋ）を格納するハッシュ木中のｋ項組みを一つ
ずつ取り出して、レコードとのマッチングを行う逆方向
レコードマッチングステップを備えたので、高速に処理
が行なえるという効果がある。

【０３５７】また、第１３の発明に係る相関ルール生成
方法は、ユーザ入力ステップにおいて、ユーザは相関ル
ール中に同時に現れてはならない２個以上の品目からな
る組を指定し、Ｌｋ生成ステップにおいてはこの指定さ
れた組に含まれる複数の品目を含まない大品目セットＬ
（ｋ）のみを生成するようにしたので、相関ルール中に
同時に現れてはならない品目の組を含まない相関ルール
を効率的に抽出できるという効果がある。

【０３５８】また、第１４の発明に係る相関ルール生成
方法は、ハッシュ木を分割し、大品目セットを生成する
段階でデータベースとハッシュ木のマッチングを分割さ
れた部分木毎に行うため、ハッシュ木のページングが起
こりにくくなり、処理時間が短縮されるという効果があ
る。

【０３５９】また、第１５の発明に係る相関ルール生成
方法は、ハッシュ木を分割し、候補品目セット生成、大
品目セット生成、ルール生成のステップの各処理を分割
された部分木毎に行うため、ハッシュ木のページングが
起こりにくくなり、処理時間が短縮されるという効果が
ある。

【０３６０】また、第１６の発明に係る相関ルール生成
方法は、大品目セットを大品目セットファイルに格納
し、大品目セットファイルから順番に読み出してメモリ
領域が限界に達するまでハッシュ木に追加し、そのハッ
シュ木毎に候補品目セット生成、大品目セット生成、ル
ール生成を実行していくので、ページングが起こらず、
処理時間が短縮されるという効果がある。

【０３６１】また、第１７の発明に係る相関ルール生成
方法は、ルール生成ステップにおいて、大品目セットＬ
（ｋ−１）の支持度を大品目セットファイルから読み出
すようにしたので、データベース検索が不要になり、処
理時間が短縮されるという効果がある。

【０３６２】また、第１８の発明に係る相関ルール生成
方法は、大品目セットファイル読み込みステップにおい
て、長さ（ｋ−１）の品目セット中の最後尾の品目以外
の品目が全て共通する品目セットを同時に読み込み、そ
れらを同一のハッシュ木に格納するので、候補品目セッ
トの数が少なくなり、処理時間が短縮されるという効果
がある。

【０３６３】また、第１９の発明に係る相関ルール生成
方法は、Ｌｋ生成ステップで、データベースのレコード
の集合と候補品目セットＣ（ｋ）を格納するハッシュ木
を入力としてマッチングを実行し、大品目セットＬ
（ｋ）を選択するので、複数のレコード中の共通する品
目の部分を一括してハッシュ関数に適用するため、再帰
的呼び出しの処理回数が減り、高速なマッチングが可能
となるという効果がある。

【０３６４】また、第２０の発明に係る相関ルール生成
装置は、大品目セットＬ（ｋ−１）を条件となる品目セ
ット、大品目セットＬ（１）を結果となる品目セットと
する相関ルール候補を生成するルール候補生成部を備え
るので、相関ルールの両辺全ての品目からなる品目セッ
トの支持度がいかなる値であっても、相関ルールを得る
ことができ、負の相関ルールを抽出できるという効果が
ある。

【０３６５】また、第２１の発明に係る相関ルール生成
装置は、ハッシュ木を分割するハッシュ木操作部と、デ
ータベースとハッシュ木のマッチングを分割された部分
木毎に行う候補品目セット検証部を備えるため、ハッシ
ュ木のページングが起こりにくくなり、処理時間が短縮
されるという効果がある。

【０３６６】また、第２２の発明に係る相関ルール生成
装置は、大品目セットの情報を保存する大品目セットフ
ァイルと、大品目セットファイルから順番に読み出して
メモリ領域が限界に達するまでハッシュ木に追加するハ
ッシュ木操作部と、そのハッシュ木毎に処理する候補品
目セット生成部、候補品目セット検証部、仮説生成検証
部を有するので、ページングが起こらず、処理時間が短
縮されるという効果がある。

【０３６７】また、第２３の発明に係る相関ルール生成
装置は、データベースのレコードの集合と候補品目セッ
トＣ（ｋ）を格納するハッシュ木を入力としてマッチン
グを実行し、大品目セットＬ（ｋ）を選択する候補品目
セット検証部を備えるので、複数のレコード中の共通す
る品目の部分を一括してハッシュ関数に適用するため、
再帰的呼び出しの処理回数が減り、高速なマッチングが
可能となるという効果がある。

【図面の簡単な説明】

【図１】 本発明の実施の形態１および実施の形態３の
システム図である。

【図２】 本発明の実施の形態１、２、３および実施の
形態１４、１５、１６のブロック図である。

【図３】 本発明の実施の形態２におけるＣｋ生成ステ
ップの詳細を示すブロック図である。

【図４】 本発明の実施の形態２の説明で用いるハッシ
ュ木の一例である。

【図５】 本発明の実施の形態２の説明で用いるｐｒｕ
ｎｅ操作前とｐｒｕｎｅ操作後のハッシュ木の一例であ
る。

【図６】 本発明の実施の形態３のシステム図である。

【図７】 本発明の実施の形態４、１１、１２、１７の
システム図である。

【図８】 本発明の実施の形態４、５、１１、１２、１
７のブロック図である。

【図９】 本発明の実施の形態４のＣｋ生成ステップの
説明で用いるＣ３生成前と生成後のハッシュ木の一例で
ある。

【図１０】 本発明の実施の形態５のシステム図であ
る。

【図１１】 本発明の実施の形態６のシステム図であ
る。

【図１２】 本発明の実施の形態６のブロック図であ
る。

【図１３】 本発明の実施の形態６の右辺と左辺の支持
度の関係の図である。

【図１４】 本発明の実施の形態７のシステム図であ
る。

【図１５】 本発明の実施の形態７、８のブロック図で
ある。

【図１６】 本発明の実施の形態８のシステム図であ
る。

【図１７】 本発明の実施の形態９のシステム図であ
る。

【図１８】 本発明の実施の形態９、１０のブロック図
である。

【図１９】 本発明の実施の形態１０のシステム図であ
る。

【図２０】 本発明の実施の形態１１の説明で用いるハ
ッシュ木の一例である。

【図２１】 本発明の実施の形態１２の説明で用いるハ
ッシュ木の一例である。

【図２２】 本発明の実施の形態１３のシステム図であ
る。

【図２３】 本発明の実施の形態１３のブロック図であ
る。

【図２４】 本発明の実施の形態１４のシステム図であ
る。

【図２５】 本発明の実施の形態１５のシステム図であ
る。

【図２６】 本発明の実施の形態１５のＣｋ生成ステッ
プの詳細を示すブロック図である。

【図２７】 本発明の実施の形態１５のの説明で用いる
ハッシュ木分割操作の一例である。

【図２８】 本発明の実施の形態１６ののシステム図で
ある。

【図２９】 本発明の実施の形態１７の説明で用いるハ
ッシュ木の一例である。

【図３０】 従来の相関ルール生成方法のシステム図で
ある。

【図３１】 従来の相関ルール生成方法のブロック図で
ある。

【図３２】 従来の相関ルール生成方法および本発明の
実施の形態１のＣｋ生成ステップの詳細を示すブロック
図である。

【図３３】 従来の相関ルール生成方法および本発明の
実施の形態１で想定するデータベースの内容例である。

【図３４】 従来の相関ルール生成方法および本発明の
実施の形態１で用いるハッシュ木の一例である。

【図３５】 従来の相関ルール生成方法および本発明の
実施の形態１の説明で用いるハッシュ木の一例である。

【図３６】 従来の相関ルール生成方法および本発明の
実施の形態１の説明で用いる、Ｃｋ生成ステップ中のｐ
ｒｕｎｅ操作前とｐｒｕｎｅ操作後のハッシュ木の一例
である。

【図３７】 本発明の実施の形態１８および実施の形態
１９のシステム図である。

【図３８】 本発明の実施の形態１８のブロック図であ
る。

【図３９】 本発明の実施の形態１８におけるハッシュ
木の状態変化の説明図である。

【図４０】 本発明の実施の形態１９にのブロック図で
ある。

【図４１】 本発明の実施の形態１９におけるハッシュ
木の状態変化の説明図である。

【図４２】 本発明の実施の形態２０、２１、２２、２
４のシステム図である。

【図４３】 本発明の実施の形態２０、２１、２２のブ
ロック図である。

【図４４】 本発明の実施の形態２０、２１の説明で用
いる大品目セットファイルの一例である。

【図４５】 本発明の実施の形態２０におけるハッシュ
木の状態変化の説明図である。

【図４６】 本発明実施の形態２２で使用したハッシュ
木の状態変化の説明図である。

【図４７】 本発明の実施の形態２３のシステム図であ
る。

【図４８】 本発明の実施の形態２３のブロック図であ
る。

【図４９】 本発明の実施の形態２３の他の実施形態の
システム図である。

【図５０】 本発明の実施の形態２４のブロック図であ
る。

【図５１】 本発明の実施の形態１８の説明に用いるデ
ータベースの一例である。

【図５２】 本発明の実施の形態１８の説明に用いるハ
ッシュ木の図である。

【図５３】 本発明の実施の形態１８の説明に用いるハ
ッシュ木の図である。

【図５４】 本発明の実施の形態１８の説明に用いるハ
ッシュ木の図である。

【図５５】 本発明の実施の形態１８のＣｋ生成の詳細
ブロック図である。

【図５６】 従来のマッチング関数のブロック図であ
る。

【図５７】 従来のマッチング関数適用の系統図であ
る。

【図５８】 本発明の実施の形態２５のマッチング関数
のブロック図である。

【図５９】 本発明の実施の形態２５のマッチング関数
適用の系統図である。

【符号の説明】

１ データベース、２ 大品目セット、３ 相関ルール
集合、１０ ユーザ入力部、２０ 大品目セット生成
部、２１ 候補品目セット検証部、２２ 候補品目セッ
ト生成部、２３ 候補品目セット生成部、２４ 候補品
目セット生成部、２５ 最小支持度決定部、２６ 負の
相関用限界支持度決定部、２７ 正の相関用限界支持度
決定部、２８ 負の境界決定部、２９ 正の境界決定
部、３２ ドメイン限定部、３３ 品目番号再配置部、
３４ ハッシュ木分割部、３５ 逆方向レコードマッチ
ング部、４０ 仮説生成検証部、４１ ルール候補生成
部、４２ 確信度計算部、４３ χ² 検定部、４４ 正
相関選択部、４５ 正負判定部、４６ ルール候補生成
部、４７ ルール候補生成部、１００１ データベー
ス、１００２ 大品目セット、１００３ 相関ルール集
合、１００４ 大品目セットファイル、１０１０ ユー
ザ入力部、１０１１ 許容メモリ量獲得部、１０１２
メモリ解放部、１０２０ 大品目セット生成部、１０２
１ 候補品目セット検証部、１０２２ 候補品目セット
生成部、１０２３ ハッシュ木操作部、１０４０ 仮説
生成検証部、１０４１ ルール候補生成部、１０４２
確信度計算部。

Claims (23)

【特許請求の範囲】
1. 【請求項１】 １以上の品目からなる複数のレコードを
   記憶したデータベース内から、１以上の品目からなる品
   目集合間の相関ルールを抽出する相関ルール生成方法で
   あり、ｋを２以上の整数とし、品目数Ｎからなる集合で
   あって、このＮ個の品目をすべて含むレコードの数であ
   る支持度が未確認である集合を候補品目セットＣ（Ｎ）
   とし、該候補品目セットＣ（Ｎ）の中で支持度が所定の
   下限値Ｓｍｉｎ以上のものを大品目セットＬ（Ｎ）とし
   て、下記（ａ）（ｂ）（ｃ）のステップを含むことを特
   徴とする相関ルール生成方法 （ａ）相関ルールの抽出に必要なパラメータを入力する
   ユーザ入力ステップ； （ｂ）下記（ｂ１）（ｂ２）（ｂ３）のステップからな
   る大品目セット生成ステップ； （ｂ１）各個別の品目を含むレコードの数である支持度
   をカウントし、この支持度が上記下限値Ｓｍｉｎ以上で
   ある品目の集合を大品目セットＬ（１）と設定するＬ１
   生成ステップ； （ｂ２）大品目セットＬ（ｋ−１）と上記大品目セット
   Ｌ（１）から候補品目セットＣ（ｋ）を生成するＣｋ生
   成ステップ； （ｂ３）上記候補品目セットＣ（ｋ）から大品目セット
   Ｌ（ｋ）を選択するＬｋ生成ステップ； （ｃ）下記（ｃ１）（ｃ２）のステップからなる仮説生
   成検証ステップ； （ｃ１）大品目セットＬ（ｋ−１）と上記大品目セット
   Ｌ（１）から、大品目セットＬ（ｋ−１）を条件となる
   品目セット（以下「左辺」という。）、大品目セットＬ
   （１）を結果となる品目セット（以下「右辺」とい
   う。）とする相関ルール候補を生成するルール候補生成
   ステップ； （ｃ２）上記相関ルール候補について、相関ルールとし
   て採用するか棄却するかを判定するルール検定ステッ
   プ。
2. 【請求項２】 上記ユーザ入力ステップは、ユーザが少
   なくともχ² 検定における有意水準を入力し、上記ルー
   ル検定ステップは、左辺の支持度、右辺の支持度、左辺
   と右辺の両方に含まれる品目からなる品目セットの支持
   度、およびレコード総数からχ² 値を算出し、このχ²
   値と上記有意水準を指標としてχ² 検定を行うことを特
   徴とする請求項１に記載の相関ルール生成方法。
3. 【請求項３】 上記仮説生成検証ステップは、相関ルー
   ルが正の相関ルールか負の相関ルールかを判定する正負
   判定ステップを備えたことを特徴とする請求項１に記載
   の相関ルール生成方法。
4. 【請求項４】 上記大品目セット生成ステップは、個別
   の品目の支持度から上記支持度の下限値Ｓｍｉｎを算出
   する相関用限界支持度決定ステップを備えたことを特徴
   とする請求項１に記載の相関ルール生成方法。
5. 【請求項５】 上記大品目セット生成ステップは、支持
   度の最も小さな個別の品目の支持度を上記支持度の下限
   値Ｓｍｉｎと設定する最小支持度決定ステップを備えた
   ことを特徴とする請求項１に記載の相関ルール生成方
   法。
6. 【請求項６】 上記仮説生成検証ステップは、ルール候
   補生成ステップで相関ルール候補を生成する際に使用し
   た大品目セットＬ（ｋ−１）と大品目セットＬ（１）の
   対に対して、該大品目セットＬ（ｋ−１）の支持度から
   該大品目セットＬ（１）の支持度の限界値を算出する境
   界決定ステップを備え、上記ルール検定ステップは、支
   持度が境界以内である大品目セットＬ（１）とこれと対
   の大品目セットＬ（ｋ−１）から生成された相関ルール
   候補のみのχ² 検定を行うことを特徴とする請求項２に
   記載の相関ルール生成方法。
7. 【請求項７】 上記ユーザ入力ステップは、ユーザが少
   なくとも相関ルールの左辺または右辺の品目に関する条
   件を入力することを特徴とする請求項１に記載の相関ル
   ール生成方法。
8. 【請求項８】 上記ユーザ入力ステップは、ユーザが相
   関ルール中の左辺にその中の１個以上が必ず含まれる１
   個以上の品目と相関ルール中の右辺にその中の１個以上
   が必ず含まれる１個以上の品目を条件として入力するこ
   とを特徴とする請求項７に記載の相関ルール生成方法。
9. 【請求項９】 上記ユーザ入力ステップは、ユーザが相
   関ルール中の左辺にすべてが必ず含まれる１個以上の品
   目と相関ルール中の右辺にすべてが必ず含まれる１個以
   上の品目を条件として入力することを特徴とする請求項
   ７に記載の相関ルール生成方法。
10. 【請求項１０】 上記ユーザ入力ステップは、ユーザが
    データベース中のレコードの中から、特定の１以上の品
    目を持つレコードの集合であるドメインを指定するため
    に上記１以上の品目を入力し、大品目セット生成ステッ
    プは、データベースから指定された上記ドメインに含ま
    れるレコードのみを取り出し、以後データベース中のレ
    コード総数の代わりにこのドメインに含まれるレコード
    の総数を使用するようにするドメイン限定ステップを備
    えたことを特徴とする請求項１に記載の相関ルール生成
    方法。
11. 【請求項１１】 上記大品目セット生成ステップは、各
    品目の支持度の順に各個別の品目に対し品目番号を付け
    る品目番号再配置ステップを備えたことを特徴とする請
    求項１に記載の相関ルール生成方法。
12. 【請求項１２】 上記大品目セット生成ステップは、上
    記候補品目セットＣ（ｋ）を格納するハッシュ木中のｋ
    項組みを一つずつ取り出して、レコードとのマッチング
    を行う逆方向レコードマッチングステップを備えること
    を特徴とする請求項１に記載の相関ルール生成方法。
13. 【請求項１３】 上記ユーザ入力ステップは、ユーザが
    相関ルール中に同時に現れてはならない２個以上の品目
    からなる組を指定し、Ｌｋ生成ステップは、この指定さ
    れた組に含まれる複数の品目を同時には含まない大品目
    セットＬ（ｋ）のみを生成することを特徴とする請求項
    １に記載の相関ルール生成方法。
14. 【請求項１４】 １以上の品目からなる複数のレコード
    を記憶したデータベース内から、１以上の品目からなる
    品目集合間の相関ルールを抽出する相関ルール生成方法
    であり、ｋを２以上の整数とし、品目数Ｎからなる集合
    であって、このＮ個の品目をすべて含むレコードの数で
    ある支持度が未確認である集合を候補品目セットＣ
    （Ｎ）とし、該候補品目セットＣ（Ｎ）の中で支持度が
    所定の下限値Ｓｍｉｎ以上のものを大品目セットＬ
    （Ｎ）として、下記（ａ）から（ｆ）のステップを含む
    ことを特徴とする相関ルール生成方法 （ａ）各個別の品目を含むレコードの数である支持度を
    カウントし、この支持度が上記下限値Ｓｍｉｎ以上であ
    る品目の集合を大品目セットＬ（１）と設定するＬ１生
    成ステップ； （ｂ）大品目セットＬ（ｋ−１）を格納しているハッシ
    ュ木の枝を伸ばし、候補品目セットＣ（ｋ）を生成する
    Ｃｋ生成ステップ； （ｃ）ハッシュ木を、所定の容量以内の部分木に分割す
    るハッシュ木分割ステップ； （ｄ）上記分割された部分木毎にデータベースとのマッ
    チングを行い、大品目セットＬ（ｋ）を選択するＬｋ生
    成ステップ； （ｅ）相関ルール候補を生成するルール候補生成ステッ
    プ； （ｆ）上記相関ルール候補について相関ルールとして採
    用するか棄却するかを判定するルール検定ステップ。
15. 【請求項１５】 上記Ｌ１生成ステップは、上記下限値
    Ｓｍｉｎ以上である品目に任意の連続番号を割り当て、
    Ｃｋ生成ステップとＬｋ生成ステップとルール候補生成
    ステップとルール検定ステップは、各ステップの処理を
    上記分割された部分木毎に実行することを特徴とする請
    求項１４に記載の相関ルール生成方法。
16. 【請求項１６】 １以上の品目からなる複数のレコード
    を記憶したデータベース内から、１以上の品目からなる
    品目集合間の相関ルールを抽出する相関ルール生成方法
    であり、ｋを２以上の整数とし、品目数Ｎからなる集合
    であって、このＮ個の品目をすべて含むレコードの数で
    ある支持度が未確認である集合を候補品目セットＣ
    （Ｎ）とし、該候補品目セットＣ（Ｎ）の中で支持度が
    所定の下限値Ｓｍｉｎ以上のものを大品目セットＬ
    （Ｎ）とし、計算機上の相関ルール生成のために使用可
    能なメモリ容量を使用許容容量とし、上記大品目セット
    Ｌ（Ｎ）の情報を保存する大品目セットファイルを使用
    して、下記（ａ）から（ｆ）のステップを含むことを特
    徴とする相関ルール生成方法 （ａ）各個別の品目を含むレコードの数である支持度を
    カウントし、この支持度が上記下限値Ｓｍｉｎ以上であ
    る品目の集合を大品目セットＬ（１）と設定し、該各品
    目に任意の連続番号を割り当てた後、大品目セットＬ
    （１）の情報を大品目セットファイルに保存するＬ１生
    成ステップ； （ｂ）大品目セットファイルから大品目セットＬ（ｋ−
    １）中のｋ−１項組の情報を読み込み、ハッシュ木に格
    納する、大品目セットファイル読み込みステップ； （ｃ）上記ハッシュ木の枝を伸ばして、候補品目セット
    Ｃ（ｋ）を生成するＣｋ生成ステップ； （ｄ）候補品目セットＣ（ｋ）を格納しているハッシュ
    木の容量を使用許容容量を超えない所定の容量と比較し
    て、ハッシュ木の容量の方が小さい場合は上記大品目セ
    ットファイル読み込みステップに戻り、そうでない場合
    は次ステップに進む容量判定ステップ； （ｅ）上記候補品目セットＣ（ｋ）とデータベースとの
    マッチングを行い、大品目セットＬ（ｋ）を選択するＬ
    ｋ生成ステップ； （ｆ）相関ルール候補を生成し、相関ルールとして採用
    するか棄却するかを判定するルール生成ステップ。
17. 【請求項１７】 上記ルール生成ステップは、ｋ−１項
    組の支持度を大品目セットファイルから読み出すことを
    特徴とする請求項１６に記載の相関ルール生成方法。
18. 【請求項１８】 上記大品目セットファイル読み込みス
    テップは、ｋ−１項組中の最後尾の品目以外の品目が全
    て共通する品目セットを同時に読み込み、それらを同一
    のハッシュ木に格納することを特徴とする請求項１６に
    記載の相関ルール生成方法。
19. 【請求項１９】 １以上の品目からなる複数のレコード
    を記憶したデータベース内から、１以上の品目からなる
    品目集合間の相関ルールを抽出する相関ルール生成方法
    であり、ｋを２以上の整数とし、品目数Ｎからなる集合
    であって、このＮ個の品目をすべて含むレコードの数で
    ある支持度が未確認である集合を候補品目セットＣ
    （Ｎ）とし、該候補品目セットＣ（Ｎ）の中で支持度が
    所定の下限値Ｓｍｉｎ以上のものを大品目セットＬ
    （Ｎ）として、下記（ａ）から（ｅ）のステップを含む
    ことを特徴とする相関ルール生成方法 （ａ）各個別の品目を含むレコードの数である支持度を
    カウントし、この支持度が上記下限値Ｓｍｉｎ以上であ
    る品目の集合を大品目セットＬ（１）と設定するＬ１生
    成ステップ； （ｂ）候補品目セットＣ（ｋ）を生成するＣｋ生成ステ
    ップ； （ｃ）データベースのレコードの集合と候補品目セット
    Ｃ（ｋ）を格納するハッシュ木を入力としてマッチング
    を実行し、大品目セットＬ（ｋ）を選択するＬｋ生成ス
    テップ； （ｄ）相関ルール候補を生成するルール候補生成ステッ
    プ； （ｅ）上記相関ルール候補について相関ルールとして採
    用するか棄却するかを判定するルール検定ステップ。
20. 【請求項２０】 以下の要素を備えることを特徴とする
    １以上の品目からなる品目集合間の相関ルールを抽出す
    る相関ルール生成装置 （ａ）１以上の品目からなる複数のレコードを記憶した
    データベース、 （ｂ）相関ルールの抽出に必要なパラメータを入力する
    ユーザ入力部、 （ｃ）品目数Ｎからなる集合であって、このＮ個の品目
    をすべて含むレコードの数である支持度が未確認である
    集合を候補品目セットＣ（Ｎ）とし、該候補品目セット
    Ｃ（Ｎ）の中で支持度が所定の下限値Ｓｍｉｎ以上のも
    のである大品目セットＬ（Ｎ）を記憶する領域、 （ｄ）以下の処理部を有する大品目セット生成部、 （ｄ１）各個別の品目を含むレコードの数である支持度
    をカウントし、この支持度が上記下限値Ｓｍｉｎ以上で
    ある品目の集合を大品目セットＬ（１）と設定する候補
    品目セット検証部、 （ｄ２）ｋを２以上の整数とし、大品目セットＬ（ｋ−
    １）と上記大品目セットＬ（１）から候補品目セットＣ
    （ｋ）を生成する候補品目セット生成部、 （ｄ３）上記候補品目セットＣ（ｋ）から大品目セット
    Ｌ（ｋ）を選択する候補品目セット検証部、 （ｅ）以下の処理部を有する仮説生成検証部、 （ｅ１）大品目セットＬ（ｋ−１）と上記大品目セット
    Ｌ（１）から、大品目セットＬ（ｋ−１）を条件となる
    品目セット（以下「左辺」という。）、大品目セットＬ
    （１）を結果となる品目セット（以下「右辺」とい
    う。）とする相関ルール候補を生成するルール候補生成
    部、 （ｅ２）上記相関ルール候補について、相関ルールとし
    て採用するか棄却するかを判定するルール検定部。
21. 【請求項２１】 以下の要素を備えることを特徴とする
    １以上の品目からなる品目集合間の相関ルールを抽出す
    る相関ルール生成装置 （ａ）１以上の品目からなる複数のレコードを記憶した
    データベース、 （ｂ）品目数Ｎからなる集合であって、このＮ個の品目
    をすべて含むレコードの数である支持度が未確認である
    集合を候補品目セットＣ（Ｎ）とし、該候補品目セット
    Ｃ（Ｎ）の中で支持度が所定の下限値Ｓｍｉｎ以上のも
    のである大品目セットＬ（Ｎ）を記憶する領域、 （ｃ）以下の処理部を有する大品目セット生成部、 （ｃ１）各個別の品目を含むレコードの数である支持度
    をカウントし、この支持度が上記下限値Ｓｍｉｎ以上で
    ある品目の集合を大品目セットＬ（１）と設定する候補
    品目セット検証部、 （ｃ２）ｋを２以上の整数とし、大品目セットＬ（ｋ−
    １）を格納しているハッシュ木の枝を伸ばし、候補品目
    セットＣ（ｋ）を生成する候補品目セット生成部、 （ｃ３）ハッシュ木を、所定の容量以内の部分木に分割
    するハッシュ木操作部、 （ｃ４）上記分割された部分木毎にデータベースとのマ
    ッチングを行い、大品目セットＬ（ｋ）を選択する候補
    品目セット検証部、 （ｄ）以下の処理部を有する仮説生成検証部、 （ｄ１）相関ルール候補を生成するルール候補生成部、 （ｄ２）上記相関ルール候補について相関ルールとして
    採用するか棄却するかを判定するルール検定部。
22. 【請求項２２】 以下の要素を備えることを特徴とする
    １以上の品目からなる品目集合間の相関ルールを抽出す
    る相関ルール生成装置 （ａ）１以上の品目からなる複数のレコードを記憶した
    データベース、 （ｂ）品目数Ｎからなる集合であって、このＮ個の品目
    をすべて含むレコードの数である支持度が未確認である
    集合を候補品目セットＣ（Ｎ）とし、該候補品目セット
    Ｃ（Ｎ）の中で支持度が所定の下限値Ｓｍｉｎ以上のも
    のである大品目セットＬ（Ｎ）とし、該大品目セットＬ
    （Ｎ）の情報を保存する大品目セットファイル、 （ｃ）以下の処理部を有する大品目セット生成部、 （ｃ１）各個別の品目を含むレコードの数である支持度
    をカウントし、この支持度が上記下限値Ｓｍｉｎ以上で
    ある品目の集合を大品目セットＬ（１）と設定する候補
    品目セット検証部、 （ｃ２）該各品目に任意の連続番号を割り当てた後、大
    品目セットＬ（１）の情報を大品目セットファイルに保
    存するハッシュ木操作部、 （ｃ３）ｋを２以上の整数とし、大品目セットファイル
    から大品目セットＬ（ｋ−１）中のｋ−１項組の情報を
    読み込み、ハッシュ木に格納するハッシュ木操作部、 （ｃ４）上記ハッシュ木の枝を伸ばして、候補品目セッ
    トＣ（ｋ）を生成する候補品目セット生成部、 （ｃ５）計算機上の相関ルール生成のために使用可能な
    メモリ容量を使用許容容量とし、候補品目セットＣ
    （ｋ）を格納しているハッシュ木の容量を使用許容容量
    を超えない所定の容量と比較して、ハッシュ木の容量の
    方が小さい場合は上記大品目セットファイル読み込みス
    テップに戻り、そうでない場合は次ステップに進めるハ
    ッシュ木操作部、 （ｃ６）上記候補品目セットＣ（ｋ）とデータベースと
    のマッチングを行い、大品目セットＬ（ｋ）を選択する
    候補品目セット検証部、 （ｄ）相関ルール候補を生成し、相関ルールとして採用
    するか棄却するかを判定する仮説生成検証部。
23. 【請求項２３】 以下の要素を備えることを特徴とする
    １以上の品目からなる品目集合間の相関ルールを抽出す
    る相関ルール生成装置 （ａ）１以上の品目からなる複数のレコードを記憶した
    データベース、 （ｂ）品目数Ｎからなる集合であって、このＮ個の品目
    をすべて含むレコードの数である支持度が未確認である
    集合を候補品目セットＣ（Ｎ）とし、該候補品目セット
    Ｃ（Ｎ）の中で支持度が所定の下限値Ｓｍｉｎ以上のも
    のである大品目セットＬ（Ｎ）を記憶する領域、 （ｃ）以下の処理部を有する大品目セット生成部、 （ｃ１）各個別の品目を含むレコードの数である支持度
    をカウントし、この支持度が上記下限値Ｓｍｉｎ以上で
    ある品目の集合を大品目セットＬ（１）と設定する候補
    品目セット検証部、 （ｃ２）候補品目セットＣ（ｋ）を生成する候補品目セ
    ット生成部、 （ｃ３）データベースのレコードの集合と候補品目セッ
    トＣ（ｋ）を格納するハッシュ木を入力としてマッチン
    グを実行し、大品目セットＬ（ｋ）を選択する候補品目
    セット検証部、 （ｄ）以下の処理を行なう仮説生成検証部、 （ｄ１）相関ルール候補を生成するルール候補生成部、 （ｄ２）上記相関ルール候補について相関ルールとして
    採用するか棄却するかを判定するルール検定部。