(57)【特許請求の範囲】
【請求項１】
データベースに記録された複数のレコードから、そのデータベースの品目セット間の相関ルールを抽出する相関ルール抽出装置において、
各品目をノードとするハッシュ木として複数の品目セットを記憶する記憶手段と、
大品目セットを保存する保存手段と、
前記保存手段から前記大品目セットを、最後の品目以外の品目が共通するもの毎に読み出し、その共通部分である品目セットを前記ハッシュ木に追加する共通品目セット追加手段と、
読み出された前記大品目セットの最後の品目の集合のうちのいずれか２つを順番に選択し、その２つの品目をそれぞれ前記共通部分に追加して前記大品目セットより１だけ品目数の多い候補品目セットを生成する候補品目セット生成手段と、
各候補品目セットの一部であってその候補品目セットより品目数が１だけ少ない品目セットをルール検証用品目セットとして前記ハッシュ木に追加するルール検証用品目セット生成手段と、
前記大品目セットの共通部分、前記候補品目セットおよび前記ルール検証用品目セットの追加後の前記ハッシュ木のための記憶容量を計算する記憶容量計算手段と、
前記記憶容量計算手段により計算された前記ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、各候補品目セットおよび各ルール検証用品目セットの支持度を計算し、前記候補品目セットのうち、前記支持度が所定の基準値より大きいものを大品目セットとして前記保存手段に保存する支持度計算手段と、
前記記憶容量計算手段により計算された前記ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、前記ルール検証用品目セットおよび前記大品目セットの支持度より計算される確信度またはχ２乗値に基づいて前記大品目セットから相関ルールを生成し、その後に前記ハッシュ木を前記記憶手段から消去する相関ルール生成手段と
を備えることを特徴とする相関ルール抽出装置。
【請求項２】
支持度計算手段は、大品目セットとともにその支持度を保存手段に保存し、各ルール検証用品目セットと同一の大品目セットが前記保存手段に保存されている場合には、その大品目セットの支持度をそのルール検証用品目セットの支持度とする
ことを特徴とする請求項１記載の相関ルール抽出装置。
【請求項３】
支持度計算手段は、データベースからレコードを読み出し、候補品目セットの出現数およびルール検証用品目セットの出現数を並行してカウントして前記候補品目セットの支持度および前記ルール検証用品目セットの支持度を計算する
ことを特徴とする請求項１記載の相関ルール抽出装置。
【請求項４】
支持度計算手段は、ハッシュ木からルール検証用品目セットに対応する部分木を切り離した後、各候補品目セットの支持度を計算し、前記支持度の計算後、前記ルール検証用品目セットに対応する部分木を前記ハッシュ木の元の位置に戻す
ことを特徴とする請求項１記載の相関ルール抽出装置。
【請求項５】
支持度計算手段は、切り離した部分木が接続されていたハッシュ木の接続ノードと前記部分木のルートとの対応関係を示すデータをスタックによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木を前記ハッシュ木の元の位置に戻す
ことを特徴とする請求項４記載の相関ルール抽出装置。
【請求項６】
支持度計算手段は、切り離した部分木が接続されていたハッシュ木の接続ノードと前記部分木のルートとの対応関係を示すデータをリストによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木を前記ハッシュ木の元の位置に戻す
ことを特徴とする請求項４記載の相関ルール抽出装置。
【請求項７】
記憶容量計算手段は、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、直前に追加された大品目セットの共通部分、候補品目セットおよびルール検証用品目セットを前記ハッシュ木から削除する
ことを特徴とする請求項１記載の相関ルール抽出装置。
【請求項８】
支持度計算手段および相関ルール生成手段は、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合の代わりに、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加による前記ハッシュ木のための記憶容量の増加量のうちの最大値が、所定の基準値と前記ハッシュ木のための記憶容量との差より大きくなった場合に、支持度を計算し、相関ルールを生成し、その後にハッシュ木を消去する
ことを特徴とする請求項１記載の相関ルール抽出装置。
【請求項９】
支持度計算手段および相関ルール生成手段は、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合の代わりに、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加による前記ハッシュ木のための記憶容量の増加量の平均値が、所定の基準値と前記ハッシュ木のための記憶容量との差より大きくなった場合に、支持度を計算し、相関ルールを生成し、その後にハッシュ木を消去する
ことを特徴とする請求項１記載の相関ルール抽出装置。
【請求項１０】
コンピュータに、データベースに記録された複数のレコードから、そのデータベースの品目セット間の相関ルールを抽出させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータに、
所定の保存手段から大品目セットを、最後の品目以外の品目が共通するもの毎に読み出し、所定の記憶手段に記憶され各品目をノードとした品目セットのハッシュ木に、前記大品目セットの共通部分である品目セットを追加する手順、
読み出した前記大品目セットの最後の品目の集合のうちのいずれか２つを順番に選択し、その２つの品目をそれぞれ前記共通部分に追加して、前記大品目セットより品目数が１だけ多い候補品目セットを生成する手順、
各候補品目セットの一部であって前記候補品目セットより品目数が１だけ少ない品目セットをルール検証用品目セットとして前記ハッシュ木に追加する手順、
前記大品目セットの共通部分、前記候補品目セットおよび前記ルール検証用品目セットの追加後の前記ハッシュ木のための記憶容量を計算する手順、
前記ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、各候補品目セットおよび各ルール検証用品目セットの支持度を計算し、前記候補品目セットのうち、前記支持度が所定の基準値より大きいものを大品目セットとして前記所定の保存手段に保存する手順、
前記ルール検証用品目セットおよび前記大品目セットの支持度より計算される確信度またはχ２乗値に基づいて前記大品目セットから相関ルールを生成し、その後に前記ハッシュ木を前記所定の記憶手段から消去する手順
を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
データベースの各属性に対応する各品目をノードとするハッシュ木として品目セットを記憶し、そのデータベースに記録された複数のレコードから所定の規則に従ってハッシュ木に品目に対応するノードを追加して大品目セットを生成していくとともに前記データベースの属性間の相関ルールを抽出する相関ルール抽出装置において、
属性番号と属性値で構成される２次元インデックスとして各品目を保存するデータベースと、
前記ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出する相関ルール抽出部と
を備えることを特徴とする相関ルール抽出装置。
【請求項１２】
データベースは、各品目の値を、属性番号と属性値で構成される２次元インデックスとして、または、そのデータベースの複数の属性で構成される属性グループについての属性グループ番号とそれらのうちのいずれかの属性値で構成される２次元インデックスとして保存し、
相関ルール抽出部は、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号または属性グループ番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出する
ことを特徴とする請求項１１記載の相関ルール抽出装置。
【請求項１３】
所定の表形式でデータベースに予め保存されたレコードの各属性値を２次元インデックスに変換し、その２次元インデックスを前記データベースに保存するデータ変換手段を備える
ことを特徴とする請求項１１記載の相関ルール抽出装置。
【請求項１４】
コンピュータに、データベースの各属性に対応する各品目をノードとするハッシュ木として品目セットを記憶し、そのデータベースに記録された複数のレコードから所定の規則に従って前記ハッシュ木に品目に対応するノードを追加して大品目セットを生成していくとともに前記データベースの属性間の相関ルールを抽出させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータに、
属性番号と属性値で構成される２次元インデックスとして各品目を保存する前記データベースから品目を読み出す手順、
前記ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出する手順
を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１５】
データベースに記録された複数のレコードから、そのデータベースの品目セット間の相関ルールを抽出する相関ルール抽出装置において、
大品目セットを保存する保存手段と、
前記保存手段に保存された大品目セットのうち、最後の品目以外の品目が共通する前記大品目セットから、その大品目セットより品目数が１だけ多い候補品目セットを生成する候補品目セット生成手段と、
前記候補品目セットの支持度を計算し、その支持度に基づいて前記候補品目セットと同一品目数の大品目セットを生成して前記保存手段に保存する支持度計算手段と、
前記大品目セットの品目数をｋとして、前記大品目セットを、品目数が１から（ｋ−１）までの条件部と品目数が（ｋ−１）から１までの帰結部とに分割してそれぞれ生成されるルールのうち、確信度またはχ２乗値が所定の基準値より大きいものを相関ルールとする相関ルール生成手段と
を備えることを特徴とする相関ルール抽出装置。
【請求項１６】
保存手段は、大品目セットとともにその支持度を保存し、
支持度計算手段は、大品目セットを前記保存手段に保存する際に、その大品目セットの支持度も保存し、ルールの条件部と同一の大品目セットが前記保存手段に保存されている場合には、その大品目セットの支持度をそのルールの条件部の支持度として前記ルールの確信度またはχ２乗値を計算する
ことを特徴とする請求項１５記載の相関ルール抽出装置。
【請求項１７】
コンピュータに、データベースに記録された複数のレコードから、そのデータベースの品目セット間の相関ルールを抽出させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータに、
所定の保存手段に保存された大品目セットのうち、最後の品目以外の品目が共通する大品目セットから、その大品目セットより品目数が１だけ多い候補品目セットを生成する手順、
前記候補品目セットの支持度を計算し、その支持度に基づいて前記候補品目セットと同一品目数の大品目セットを生成して前記所定の保存手段に保存する手順、
前記大品目セットの品目数をｋとして、前記大品目セットを、品目数が１から（ｋ−１）までの条件部と品目数が（ｋ−１）から１までの帰結部とに分割してそれぞれ生成されるルールのうち、確信度またはχ２乗値が所定の基準値より大きいものを相関ルールとする手順
を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、データベースに記録された複数のレコードから、そのデータベースの品目セット間の相関ルールを抽出するための相関ルール抽出装置、相関ルール抽出方法および記録媒体に関するものである。
【０００２】
【従来の技術】
図１８は従来の相関ルール抽出装置の構成例を示すブロック図である。この従来の相関ルール抽出装置では、例えば「Fast Algorithms for Mining Association Rules」（Ａｇｒａｗａｌら著、Proc. of the 20th VLDB Conference, Santiago, Chile、１９９４年）や特開平８−２８７１０６号公報に記載のアプリオリ（Apriori）法に基づいて、データベースに記録された複数のレコードから、そのデータベースの品目セット間の相関ルールが抽出される。アプリオリ法では、すべてのレコードのうち品目セット「Ａ，Ｂ，・・・，Ｘ，Ｙ」の含まれるレコードの割合を支持度とし、ルール「Ａ，Ｂ，・・・，Ｘ→Ｙ」の条件部の品目セット「Ａ，Ｂ，・・・，Ｘ」の含まれるレコードのうち帰結部の品目「Ｙ」の含まれるレコードの割合を確信度として、これらの支持度および確信度がそれぞれ所定の基準値より高い場合に、ルール「Ａ，Ｂ，・・・，Ｘ→Ｙ」が相関ルールとして抽出される。
【０００３】
図１８において、１は所定の対象についてのデータを、複数のレコードとして保持するデータベースである。５は生成された相関ルールを保持する相関ルール集合ファイルである。１０２はデータベース１のレコードを参照して、品目数がｋの大品目セットから品目数が（ｋ＋１）の大品目セットを生成する大品目セット生成手段である。なお、大品目セットとは、所定の基準値より高い支持度を有する品目セットをいう。１０４は各大品目セットからルール（すなわち相関ルールの候補）を生成し、そのルールの確信度に基づいて相関ルールを抽出する仮説生成検証手段である。
【０００４】
大品目セット生成手段１０２において、１２１はデータベース１のレコードを参照して、候補品目セット生成手段１２２により生成された候補品目セットの支持度を計算し、所定の基準値より高い支持度を有する候補品目セットを大品目セットとする候補品目セット検証手段であり、１２２は（ｋ−２）個の品目が同一であり、かつ品目数が（ｋ−１）である複数の大品目セットのうちの各々２つの大品目セットから、（ｋ−２）個の同一の品目、およびその大品目セットにおけるそれぞれ異なる２個の品目で構成される品目数がｋである候補品目セットを生成する候補品目セット生成手段である。
【０００５】
仮説生成検証手段１０４において、３１は品目数がｋである大品目セットから、（ｋ−１）個の品目の条件部と１個の品目の帰結部で構成されるすべてのルールを生成するルール候補生成手段であり、３３はルール候補生成手段３１により生成されたルールの確信度を、大品目セットを参照して計算する確信度計算手段である。
【０００６】
次に動作について説明する。
まず、候補品目セット検証手段１２１は、品目数が１である大品目セットを、データベース１の各レコードの品目を参照して生成する。候補品目セット生成手段１２２は、品目数が１である複数の大品目セットのうちの各々２つの大品目セットから、およびその大品目セットにおけるそれぞれ異なる２個の品目で構成される品目数が２である候補品目セットを生成する。
【０００７】
次に、候補品目セット検証手段１２１は、データベース１のレコードを参照して、候補品目セット生成手段１２２により生成された候補品目セットの支持度を計算し、所定の基準値より高い支持度を有する候補品目セットを大品目セットとする。
【０００８】
そして、候補品目セット生成手段１２２は、（ｋ−２）個の品目が共通し、かつ品目数が（ｋ−１）である複数の大品目セットのうちの各々２つの大品目セットから、（ｋ−２）個の共通の品目、およびその大品目セットにおけるそれぞれ異なる２個の品目で構成される品目数がｋである候補品目セットを生成する。以下同様に、大品目セット生成手段１０２は、候補品目セットがなくなるまで品目数を１ずつ増加させながら、大品目セットを生成していく。
【０００９】
一方、仮説生成検証手段１０４においては、ルール候補生成手段３１が、候補品目セット検証手段１２１による品目数がｋである大品目セットから、（ｋ−１）個の品目の条件部と１個の品目の帰結部で構成されるすべてのルールを生成する。そして、確信度計算手段３３が、大品目セットを参照して、ルール候補生成手段３１により生成されたルールの確信度を計算し、所定の基準値より高い確信度を有するルールを相関ルールとして相関ルール集合ファイル５に保存する。
【００１０】
このようにして、各品目数についての大品目セットが生成され、その大品目セットに基づいて相関ルールが抽出される。
【００１１】
なお、大品目セットを保持する場合、データ構造をハッシュ木としてメモリなどに保持することが多い。図１９は大品目セットを示すハッシュ木の一例を示す図である。このハッシュ木においては、各品目がノードを構成し、１つの品目セットが、ルート（ｒｏｏｔ）から下位の所定のノードまでの１つの枝を構成する。例えば図１９において、ルートからノード１およびノード３を経てノード５までの枝は、品目１，３，５により構成される品目セット［１，３，５］により構成されている。なお、以下、品目ｘ１，ｘ２，・・・，ｘｎにより構成される品目セットを［ｘ１，ｘ２，・・・，ｘｎ］と表記する。
【００１２】
すなわち、上述の大品目セットの生成の繰り返しにより、大品目セットが増加する毎にハッシュ木に枝が追加されていき、品目数が増加する毎に枝を構成するノードを増加して枝伸ばしをしていく。ハッシュ木において、すべての枝はいずれかの大品目セットを構成する。
【００１３】
このようにして木構造で複数の品目数の異なる大品目セットを表現することができるのは、大品目セットにおける部分集合は、必ず大品目セットになるという性質を利用したものである。なお、大品目セットにおける部分集合とは、大品目セットを構成するｋ個の品目のうちの（ｋ−１）個以下の品目で構成される品目セットのことである。
【００１４】
このように、ハッシュ木として複数の大品目セットを保持することにより、大品目セットを単に順次記憶していく場合に比較して、大品目セットの保持に必要な記憶容量を低減させている。
【００１５】
しかしながら、ハッシュ木を利用しても品目数が多い場合には、ハッシュ木自体が大きくなってしまい、大品目セットを生成するために、多くの記憶容量を有するメモリが必要になる。また、メモリの記憶容量が小さく仮想記憶方式を採用している場合には、ページングが頻繁に発生し、処理に要する時間が長くなってしまうなどの課題があった。
【００１６】
上述のものの他の従来の技術としては、特開平８−１６１２８７号公報、特開平８−２６３３４６号公報、特開平８−２７２８２５号公報、特開平８−３１４９８１号公報、特開平９−３４７２１号公報、特開平１０−２６９２４８号公報にそれぞれ記載のものなどがある。
【００１７】
そこで、本出願人は、このような課題を解決するために、ページングを抑制するための手法を特願平１０−１８２４１６号において先に提案した。図２０は先に提案した第１の手法について説明する図であり、図２１は先に提案した第２の手法について説明する図である。
【００１８】
先に提案した第１の手法においては、大品目セットがファイルに格納され、そのファイルから１つずつ大品目セットが読み出されてハッシュ木に追加され、さらにその追加された大品目セットおよび既に追加されている大品目セットから生成されるすべての候補品目セットがハッシュ木に追加される。
【００１９】
ここで、大品目セットに対応して候補品目セットを生成する際には、その大品目セットの最後の品目より大きな番号の品目のノードを、大品目セットの下位にそれぞれ並行して追加して候補品目セットの枝が生成される。例えば、１から１０までの１０種類の品目が存在し、大品目セット［１，３，５］に対応して候補品目セットを生成する場合、大品目セット［１，３，５］の枝の下位に、ノード６，７，８，９，１０がそれぞれ追加され、候補品目セット［１，３，５，６］，［１，３，５，７］，［１，３，５，８］，［１，３，５，９］，［１，３，５，１０］が生成される。
【００２０】
上述の一連の処理が品目数の同一な大品目セットのそれぞれについて順番に実行されていく。そして、この一連の処理毎に、ハッシュ木により占有されている記憶容量が計算され、その値が所定の基準値を超えた場合に、ハッシュ木に追加された候補品目セットについてレコードとのマッチングにより支持度が計算され、ファイルに保存された大品目セットより品目数が１だけ大きい大品目セットが図２０に示すように生成され、すべての大品目セットが生成された後に一括して更新される。従ってファイルには同一の品目数の大品目セットが常に保存されていることになる。なお、大品目セットとならなかった候補品目セットは削除される。
【００２１】
そして、ルールの検証のために必要な品目セット（ルール検証用品目セット）、すなわち大品目セットより１だけ品目数が少ない、その大品目セットの部分集合である品目セットもハッシュ木に追加される。これらの部分木に基づいて相関ルールを生成した後、追加された大品目セットおよびそれに関して追加された部分木が削除される。そして、次の大品目セットが同様にして追加され同様に処理される。
【００２２】
先に提案した第２の手法においては、アプリオリ法と同様の枝伸ばしが実行される。この手法においては、ハッシュ木のために予め割り当てられた記憶容量の数分の１である所定の記憶容量に、ハッシュ木のデータ量が達するまで、最後の品目以外の品目がすべて同一である大品目セットが一括してファイルから読み出されてハッシュ木に順次追加される。ここで、予め割り当てられた記憶容量の数分の１である所定の記憶容量分だけ大品目セットを読み込むのは、その後に、候補品目セットやルール検証用品目セットの追加に必要な記憶容量を残しておくためである。
【００２３】
そして、最後の品目以外の品目がすべて同一である大品目セットから候補品目セットが生成される。例えば大品目セット［２，３，５］，［２，３，７］がファイルに保存されている場合、図２１に示すように、これらの大品目セット［２，３，５］，［２，３，７］は一括して読み出され、ハッシュ木に追加される。そして、互いの異なる最後の品目「５」，「７」に基づいて、大品目セット［２，３，５］に品目「７」を追加して候補品目セット「２，３，５，７」が追加される。
【００２４】
以上のように、先に提案した第１および第２の手法によれば、予め割り当てられた記憶容量の範囲内で効率良く大品目セットの生成ができ、ひいては相関ルールを効率良く抽出することができる。
【００２５】
【発明が解決しようとする課題】
先に提案した手法は以上のように構成されており、上記の課題を解決することはできるものの第１の手法においては候補品目セットの生成の際にアプリオリ法と同様の枝伸ばしとは異なり多くの枝を生成するため、支持度を計算する候補品目セットの数が多くなり、処理時間がその分だけ長くなるという課題があった。また、第２の手法においては、予め割り当てられた記憶容量の数分の１に、大品目セットのデータ量が達した場合に、残りの記憶容量を使用して、それらの大品目セットについての候補品目セットなどをハッシュ木に追加するようにしているため、予め割り当てられた記憶容量がすべて有効に使用されない可能性があるという課題があった。
【００２６】
また、上述の従来の技術においては、表形式のデータから相関ルールを抽出する場合、前処理として、表における各属性値に番号１，２，３などを割り当て、属性値をその番号（品目）に変換した後に、上述の処理を実行するようにしているため、自明な、同じ属性における属性値の相関ルール（例えば属性「性別」における属性値「男」，「女」に対する「性別が『男』であるならば性別は『女』ではない」といういわゆる負の相関を有するルール）も抽出され、後処理として、そのような自明な相関ルールを除去する必要があるという課題があった。
【００２７】
さらに、上述の従来の技術においては、帰結部の品目数が１である相関ルールのみが抽出されているため、帰結部の品目数が２以上である相関ルールを抽出することが困難であるという課題があった。
【００２８】
この発明は上記のような課題を解決するためになされたもので、大品目セットを、最後の品目以外の品目が共通するもの毎に読み出し、ハッシュ木に大品目セットの共通部分である品目セットを追加し、その大品目セットの最後の品目の集合のうちのいずれか２つを順番に選択し、その２つの品目をそれぞれ共通部分に追加して候補品目セットを生成するとともに、ルール検証用品目セットを生成してハッシュ木に追加した後にハッシュ木のための記憶容量を計算し、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、各候補品目セットおよび各ルール検証用品目セットの支持度を計算し、候補品目セットのうち、支持度が所定の基準値より大きいものを大品目セットとして保存し、ルール検証用品目セットおよび大品目セットの支持度より計算される確信度またはχ２乗値に基づいて大品目セットから相関ルールを生成し、その後にハッシュ木を消去するようにして、予め割り当てられた記憶容量を有効に使用するようにする相関ルール抽出装置、相関ルール抽出方法および記録媒体を得ることを目的とする。
【００２９】
また、各品目を、属性番号と属性値で構成される２次元インデックスとしてデータベースに保存し、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号を有しない品目だけに制限して大品目セットを生成するようにして、同じ属性における属性値の相関ルールの生成を抑制するための相関ルール抽出装置、相関ルール抽出方法および記録媒体を得ることを目的とする。
【００３０】
さらに、品目数がｋである大品目セットから相関ルールの候補を作成する際に、条件部の品目数が１〜（ｋ−１）であり、帰結部の品目数が（ｋ−１）〜１であるルールをそれぞれ生成するようにして、帰結部が２以上の相関ルールを生成するための相関ルール抽出装置、相関ルール抽出方法および記録媒体を得ることを目的とする。
【００３１】
【課題を解決するための手段】
この発明に係る相関ルール抽出装置は、ハッシュ木として複数の品目セットを記憶する記憶手段と、大品目セットを保存する保存手段と、保存手段から大品目セットを、最後の品目以外の品目が共通するもの毎に読み出し、その共通部分である品目セットをハッシュ木に追加する共通品目セット追加手段と、読み出された大品目セットの最後の品目の集合のうちのいずれか２つを順番に選択し、その２つの品目をそれぞれ共通部分に追加して候補品目セットを生成する候補品目セット生成手段と、各候補品目セットの一部であってその候補品目セットより品目数が１だけ少ない品目セットをルール検証用品目セットとしてハッシュ木に追加するルール検証用品目セット生成手段と、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加後のハッシュ木のための記憶容量を計算する記憶容量計算手段と、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、各候補品目セットおよび各ルール検証用品目セットの支持度を計算し、候補品目セットのうち、支持度が所定の基準値より大きいものを大品目セットとして保存手段に保存する支持度計算手段と、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、ルール検証用品目セットおよび大品目セットの支持度より計算される確信度またはχ２乗値に基づいて大品目セットから相関ルールを生成し、その後にハッシュ木を記憶手段から消去する相関ルール生成手段とを備えるものである。
【００３２】
この発明に係る相関ルール抽出装置は、大品目セットとともにその支持度を保存手段に保存し、各ルール検証用品目セットと同一の大品目セットが保存手段に保存されている場合には、その大品目セットの支持度をそのルール検証用品目セットの支持度とするようにしたものである。
【００３３】
この発明に係る相関ルール抽出装置は、データベースからレコードを読み出し、候補品目セットの出現数およびルール検証用品目セットの出現数を並行してカウントして候補品目セットの支持度およびルール検証用品目セットの支持度を計算するようにしたものである。
【００３４】
この発明に係る相関ルール抽出装置は、ハッシュ木からルール検証用品目セットに対応する部分木を切り離した後、各候補品目セットの支持度を計算し、支持度の計算後、ルール検証用品目セットに対応する部分木をハッシュ木の元の位置に戻すようにしたものである。
【００３５】
この発明に係る相関ルール抽出装置は、切り離した部分木が接続されていたハッシュ木の接続ノードとその部分木のルートとの対応関係を示すデータをスタックによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木をハッシュ木の元の位置に戻すようにしたものである。
【００３６】
この発明に係る相関ルール抽出装置は、切り離した部分木が接続されていたハッシュ木の接続ノードとその部分木のルートとの対応関係を示すデータをリストによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木をハッシュ木の元の位置に戻すようにしたものである。
【００３７】
この発明に係る相関ルール抽出装置は、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、直前に追加された大品目セットの共通部分、候補品目セットおよびルール検証用品目セットをハッシュ木から削除するようにしたものである。
【００３８】
この発明に係る相関ルール抽出装置は、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量のうちの最大値が、所定の基準値とハッシュ木のための記憶容量との差より大きくなった場合に、支持度を計算し、相関ルールを生成し、その後にハッシュ木を消去するようにしたものである。
【００３９】
この発明に係る相関ルール抽出装置は、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量の平均値が、所定の基準値とハッシュ木のための記憶容量との差より大きくなった場合に、支持度を計算し、相関ルールを生成し、その後にハッシュ木を消去するようにしたものである。
【００４１】
この発明に係る記録媒体は、コンピュータに、所定の保存手段から大品目セットを、最後の品目以外の品目が共通するもの毎に読み出し、所定の記憶手段に記憶されたハッシュ木に、その大品目セットの共通部分である品目セットを追加する手順、読み出した大品目セットの最後の品目の集合のうちのいずれか２つを順番に選択し、その２つの品目をそれぞれ共通部分に追加して候補品目セットを生成する手順、各候補品目セットの一部であって候補品目セットより品目数が１だけ少ない品目セットをルール検証用品目セットとしてハッシュ木に追加する手順、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加後のハッシュ木のための記憶容量を計算する手順、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、各候補品目セットおよび各ルール検証用品目セットの支持度を計算し、候補品目セットのうち、支持度が所定の基準値より大きいものを大品目セットとして所定の保存手段に保存する手順、ルール検証用品目セットおよび大品目セットの支持度より計算される確信度またはχ２乗値に基づいて大品目セットから相関ルールを生成し、その後にハッシュ木を所定の記憶手段から消去する手順を実行させるためのプログラムを記録したものである。
【００４２】
この発明に係る相関ルール抽出装置は、属性番号と属性値で構成される２次元インデックスとして各品目を保存するデータベースと、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出する相関ルール抽出部とを備えるものである。
【００４３】
この発明に係る相関ルール抽出装置は、データベースに、各品目の値を、属性番号と属性値で構成される２次元インデックスとして、または、そのデータベースの複数の属性で構成される属性グループについての属性グループ番号とそれらのうちのいずれかの属性値で構成される２次元インデックスとして保存し、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号または属性グループ番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出するようにしたものである。
【００４４】
この発明に係る相関ルール抽出装置は、所定の表形式でデータベースに予め保存されたレコードの各属性値を２次元インデックスに変換し、その２次元インデックスをデータベースに保存するデータ変換手段を備えるものである。
【００４６】
この発明に係る記録媒体は、コンピュータに、属性番号と属性値で構成される２次元インデックスとして各品目を保存するデータベースから品目を読み出す手順、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出する手順を実行させるためのプログラムを記録したものである。
【００４７】
この発明に係る相関ルール抽出装置は、大品目セットを保存する保存手段と、保存手段に保存された大品目セットのうち、最後の品目以外の品目が共通する大品目セットから候補品目セットを生成する候補品目セット生成手段と、候補品目セットの支持度を計算し、その支持度に基づいて候補品目セットと同一品目数の大品目セットを生成して保存手段に保存する支持度計算手段と、大品目セットの品目数をｋとして、大品目セットを、品目数が１から（ｋ−１）までの条件部と品目数が（ｋ−１）から１までの帰結部とに分割してそれぞれ生成されるルールのうち、確信度またはχ２乗値が所定の基準値より大きいものを相関ルールとする相関ルール生成手段とを備えるものである。
【００４８】
この発明に係る相関ルール抽出装置は、大品目セットを保存手段に保存する際に、その大品目セットの支持度も保存し、ルールの条件部と同一の大品目セットが保存手段に保存されている場合には、その大品目セットの支持度をそのルールの条件部の支持度としてルールの確信度またはχ２乗値を計算するようにしたものである。
【００５０】
この発明に係る記録媒体は、コンピュータに、所定の保存手段に保存された大品目セットのうち、最後の品目以外の品目が共通する大品目セットから、その大品目セットより品目数が１だけ多い候補品目セットを生成する手順、候補品目セットの支持度を計算し、その支持度に基づいて候補品目セットと同一品目数の大品目セットを生成して所定の保存手段に保存する手順、大品目セットの品目数をｋとして、大品目セットを、品目数が１から（ｋ−１）までの条件部と品目数が（ｋ−１）から１までの帰結部とに分割してそれぞれ生成されるルールのうち、確信度またはχ２乗値が所定の基準値より大きいものを相関ルールとする手順を実行させるためのプログラムを記録したものである。
【００５１】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１はこの発明の実施の形態１による相関ルール抽出装置の構成を示すブロック図である。図において、１は所定の対象についてのデータを、複数のレコードとして保持するデータベースである。２はメモリ６にハッシュ木として大品目セットを記憶させ、そのハッシュ木を操作して、品目数がｋの大品目セットから品目数が（ｋ＋１）の大品目セットを生成し、大品目セットファイル（保存手段）３に保存する大品目セット生成手段である。４は各大品目セットからルール（すなわち相関ルールの候補）を生成し、そのルールの確信度またはχ２乗値に基づいて相関ルールを抽出する仮説生成検証手段（相関ルール生成手段）である。５は生成された相関ルールを保持する相関ルール集合ファイルである。６は大品目セット、候補品目セットおよびルール検証用品目セットをハッシュ木として記憶するメモリ（記憶手段）である。なお、ハッシュ木を構成する品目はルートに近い程、その番号が低くなるように配置される。
【００５２】
なお、以下、品目数がｋである大品目セットをＬ（ｋ）と、品目数がｋである候補品目セットをＣ（ｋ）と、品目数がｋであるルール検証用品目セットをＬＬ（ｋ）と表記する。
【００５３】
大品目セット生成手段２において、２１はデータベース１のレコードを参照して、候補品目セット生成手段２２により生成された候補品目セットＣ（ｋ）の支持度を計算し、所定の基準値（最小支持度）より高い支持度を有する候補品目セットＣ（ｋ）を大品目セットＬ（ｋ）とする候補品目セット検証手段（支持度計算手段）である。
【００５４】
２２は最後の品目以外が共通な大品目セットＬ（ｋ−１）のうちの各々２つの大品目セットＬ（ｋ−１）から、それらの共通部分（第１品目〜第（ｋ−２）品目）、および、残り２個の最後の品目（各大品目セットの第（ｋ−１）品目）で構成される候補品目セットＣ（ｋ）を生成し、メモリ６のハッシュ木に追加する候補品目セット生成手段（候補品目セット生成手段、ルール検証用品目セット生成手段）である。
【００５５】
２３は最後の品目以外が共通な大品目セットＬ（ｋ）を大品目セットファイル３から読み出し、その共通部分である品目数（ｋ−１）の品目セットをハッシュ木に追加するとともに、メモリ６にハッシュ木として記憶されている品目セット（大品目セット、候補品目セットなど）の占有する記憶容量を調べるハッシュ木操作手段（共通品目セット追加手段、記憶容量計算手段）である。
【００５６】
仮説生成検証手段４において、３１は大品目セットＬ（ｋ）から、（ｋ−１）個の品目の条件部と１個の品目の帰結部で構成されるすべてのルールを生成するルール候補生成手段であり、３２はルール候補生成手段３１により生成されたルールの確信度またはχ２乗値を計算する検証値計算手段である。
【００５７】
なお、χ２乗値はχ２乗検定のためのもので、ここでは、ルールの条件部と帰結部との関連する度合を示すものとして次式で計算される。
【数１】
0003810575.tif 000002
ここでｎはデータベース１におけるレコードの総数であり、Ａはルールの条件部の支持度であり、Ｂはルールの帰結部の支持度であり、Ｃはルール全体の支持度である。
【００５８】
次に動作について説明する。
図２は実施の形態１による相関ルール抽出装置の動作について説明するフローチャートである。図３は大品目セットファイル３の内容の一例を示す図であり、図４は、図３の大品目セット［１，２，３］，［１，２，４］，［１，３，５］，［１，４，５］で構成されるハッシュ木を示す図である。図５は、図２のステップＳＴ３における動作の一例について説明する図であり、図６は、図２のステップＳＴ４における動作の一例について説明する図であり、図７は、図２のステップＳＴ５における動作の一例について説明する図である。
【００５９】
まず図２のステップＳＴ１において、大品目セット生成手段２の候補品目セット検証手段２１がデータベース１のレコードに出現する各品目の支持度を計算し、所定の基準値より高い支持度を有する品目を大品目セットＬ（１）として大品目セットファイル３に、その支持度とともに保存する。
【００６０】
次に、品目数の指標ｋの初期値を２として（ステップＳＴ２）、以下、大品目セットＬ（ｋ−１）から大品目セットＬ（ｋ）を生成する処理、および生成した大品目セットＬ（ｋ）から相関ルールを生成する処理について説明する。
【００６１】
最初にステップＳＴ３において、ハッシュ木操作手段２３が大品目セットファイル３から大品目セットＬ（ｋ−１）を、最後の品目以外の品目が共通する大品目セット毎に一括して読み込み、その共通部分である品目セットをハッシュ木に追加し、各大品目セットＬ（ｋ−１）の最後の品目を、その共通部分に関連づけてハッシュ木とは別にメモリ６に記憶させる。
【００６２】
例えば大品目セットＬ（３）について（すなわちｋ＝４である場合）、図３に示す大品目セットファイル３の［１，２，３］，［１，２，４］，［１，３，５］，［１，４，５］についてステップＳＴ３〜ステップＳＴ５の処理が終了した状態のハッシュ木は図４に示すようになるが、この次、ステップＳＴ３においてこの大品目セットファイル３から大品目セット［２，４，５］，［２，４，６］，［２，４，７］が一括して読み込まれる。そして、図４に示すハッシュ木に、それらの共通部分である品目セット［２，４］で構成される枝が追加される。なお、このとき、読み込まれた各大品目セットの残りの品目「５」，「６」，「７」が例えば１つの配列としてハッシュ木とは別にメモリ６に記憶され、図５に示すように、ポインタなどによる、その配列と共通部分の枝との対応関係も合わせて記憶される。
【００６３】
次にステップＳＴ４において、候補品目セット生成手段２２は、大品目セットＬ（ｋ−１）の最後の品目の集合の各品目について、その品目と、その集合内でその品目より番号の大きい各品目により、上述の共通部分の枝をそれぞれ伸ばし、候補品目セットＣ（ｋ）を生成する。
【００６４】
例えば大品目セットＬ（３）を読み込んだ後、図５に示す状態になった場合では、まず、配列「５，６，７」のうちの品目５が読み出され、図６に示すように、その品目「５」およびその品目より番号の大きい品目「６」，「７」により、共通部分「２，４」の下位に「５，６」，「５，７」が追加され、候補品目セット［２，４，５，６］，［２，４，５，７］が生成される。なお、候補品目セット［２，４，５，６］，［２，４，５，７］について「２，４，５」は共通しているので、このときのハッシュ木は図６に示すように「２，４，５」から「６」と「７」が派生する形態になっている。
【００６５】
そして候補品目セットＣ（ｋ）の生成が終了すると、ステップＳＴ５において仮説生成検証手段４のルール候補生成手段３１が、生成された候補品目セットＣ（ｋ）の一部であって品目数が１だけ少ない品目セットをルール検証用品目セットＬＬ（ｋ−１）としてハッシュ木に追加する。なお、ルール検証用品目セットＬＬ（ｋ−１）に対応する枝が既に存在している場合には、そのルール検証用品目セットＬＬ（ｋ−１）については特に何も追加しない。
【００６６】
ここでルール検証用品目セットＬＬ（ｋ−１）は、候補品目セットＣ（ｋ）が大品目セットＬ（ｋ）になった場合に生成される候補ルールの条件部に対応するものである。例えば図６に示すように候補品目セットＣ（４）が［２，４，５，６］，［２，４，５，７］の２つである場合には、ルール検証用品目セットＬＬ（３）は、［２，４，５］，［２，４，６］，［２，５，６］，［４，５，６］，［２，４，７］，［２，５，７］，［４，５，７］の７つになる。なお、［２，４，５］は重複している。すなわち候補品目セット［２，４，５，６］が大品目セットになった場合には、ルール「２，４，５→６」，「２，４，６→５」，「２，５，６→４」，「４，５，６→２」が生成され、候補品目セット［２，４，５，７］が大品目セットになった場合には、ルール「２，４，５→７」，「２，４，７→５」，「２，５，７→４」，「４，５，７→２」が生成されるため、その条件部であるルール検証用品目セットが予め生成される。
【００６７】
そして、図６に示すハッシュ木に、これらのルール検証用品目セットＬＬ（３）のうち、ハッシュ木に存在しない枝「２，４，６」，「２，５，６」，「４，５，６」，「２，４，７」，「２，５，７」，「４，５，７」が図７に示すように追加される。
【００６８】
以上のステップＳＴ３〜ステップＳＴ５の処理が終了した時点でステップＳＴ６において、ハッシュ木操作手段２３は、メモリ６においてハッシュ木が占有する記憶容量を調べ、その記憶容量が所定の基準値より大きいか否かを判断する。そして、ハッシュ木が占有する記憶容量が所定の基準値以下である場合には、ハッシュ木操作手段２３は、候補品目セット生成手段２２に、ステップＳＴ３で読み込んだすべての大品目セットＬ（ｋ−１）の最後の品目について候補品目セットＣ（ｋ）の生成が終了しているか否かを問い合わせる。
【００６９】
そして、すべての大品目セットＬ（ｋ−１）の最後の品目について候補品目セットＣ（ｋ）の生成が終了していない場合には、ステップＳＴ４に戻り、次の、大品目セットＬ（ｋ−１）の最後の品目についての処理が同様に実行される。例えば、図７に示すハッシュ木が占有する記憶容量が所定の基準値以下である場合には、次にステップＳＴ４において、配列「５，６，７」のうちの品目「６」について候補品目セットＣ（ｋ）の生成およびルール検証用品目セットＬＬ（ｋ−１）の生成が実行される。
【００７０】
一方、すべての大品目セットＬ（ｋ−１）の最後の品目について候補品目セットＣ（ｋ）の生成が終了している場合、ハッシュ木操作手段２３は、ステップＳＴ８において、すべての大品目セットＬ（ｋ−１）が読み込まれて処理されたか否かを判断する。そして、すべての大品目セットＬ（ｋ−１）が処理されていないと判断された場合には、ステップＳＴ３に戻り、次の一群の大品目セットＬ（ｋ−１）が読み込まれ、同様の処理が実行される。一方、すべての大品目セットＬ（ｋ−１）が処理されたと判断された場合、ステップＳＴ９に進み、大品目セットＬ（ｋ）の生成などが実行される。
【００７１】
また、ステップＳＴ６においてハッシュ木が占有する記憶容量が所定の基準値より高い場合には、ステップＳＴ９に進み、その時点までにメモリ６のハッシュ木に追加された各候補品目セットＣ（ｋ）の支持度が候補品目セット検証手段２１によりデータベース１のレコードを参照して計算され、候補品目セットＣ（ｋ）のうち、所定の基準値より高い支持度を有する候補品目セットＣ（ｋ）が大品目セットＬ（ｋ）とされ、その大品目セットＬ（ｋ）はその支持度とともに大品目セットファイル３に保存される。なお、大品目セットファイル３において、大品目セットがその品目数毎に保存される。すなわち、生成された大品目セットＬ（ｋ）は大品目セットＬ（ｋ−１）とは別に保存される。
【００７２】
そして大品目セットＬ（ｋ）が生成されると、次にステップＳＴ１０において、ハッシュ木操作手段２３が、その時点までにメモリ６のハッシュ木に追加された各ルール検証用品目セットＬＬ（ｋ−１）と同一の大品目セットＬ（ｋ−１）を大品目セットファイル３で検索し、該当する大品目セットＬ（ｋ−１）を発見した場合には、その大品目セットＬ（ｋ−１）の支持度を読み出し、そのルール検証用品目セットＬＬ（ｋ−１）の支持度として、そのルール検証用品目セットＬＬ（ｋ−１）に関連づけてメモリ６に記憶させる。該当する大品目セットＬ（ｋ−１）が発見されなかった場合、特に何もしない。そのルール検証用品目セットＬＬ（ｋ−１）を包含する品目セットの支持度は所定の基準値以下であり、そのような品目セットは大品目セットＬ（ｋ）にならず、そのルール検証用品目セットＬＬ（ｋ−１）の支持度は特に必要ないからである。
【００７３】
次に、ステップＳＴ１１において、まずルール候補生成手段３１は、大品目セットＬ（ｋ）のうちの各（ｋ−１）の品目を条件部とし、残りの１品目を帰結部としたルールを生成する。そして、検証値計算手段３２は、各ルールについて、条件部の支持度（すなわちルール検証用品目セットＬＬ（ｋ−１）の支持度）および大品目セットＬ（ｋ）の支持度から確信度を計算するか、あるいは、条件部の支持度、帰結部の支持度、大品目セットＬ（ｋ）の支持度およびデータベースのレコード数からχ２乗値を計算し、所定の基準値より確信度またはχ２乗値が高いルールを相関ルールとして相関ルール集合ファイル５に保存する。
【００７４】
このように相関ルールを生成し保存した後、ステップＳＴ１２において、仮説生成検証手段４は、メモリ６のハッシュ木を消去して、ハッシュ木に占有された記憶領域を解放する。
【００７５】
そしてステップＳＴ１３において、ハッシュ木操作手段２３は、大品目セットファイル３における大品目セットＬ（ｋ−１）をすべて読み込み、かつ、読み込んだ大品目セットＬ（ｋ−１）からすべての候補品目セットＣ（ｋ）が生成されているか否かを判断する。読み込んだ大品目セットＬ（ｋ−１）からすべての候補品目セットＣ（ｋ）が生成されていない場合には、ステップＳＴ７を介してステップＳＴ４に戻り、残りの候補品目セットＣ（ｋ）の生成が実行され、読み込んだ大品目セットＬ（ｋ−１）からすべての候補品目セットＣ（ｋ）が生成されているが、読み込んでいない大品目セットＬ（ｋ−１）がある場合には、ステップＳＴ７およびステップＳＴ８を介してステップＳＴ３に戻り、残りの大品目セットＬ（ｋ−１）が読み込まれる。
【００７６】
一方、大品目セットファイル３における大品目セットＬ（ｋ−１）をすべて読み込み、かつ、読み込んだ大品目セットＬ（ｋ−１）からすべての候補品目セットＣ（ｋ）が生成されていると判断された場合には、ステップＳＴ１４に進み、ハッシュ木操作手段２３は、大品目セットＬ（ｋ）が少なくとも１つは生成されたか否かを判断する。大品目セットＬ（ｋ）が少なくとも１つは生成されている場合には、品目数の指標ｋの値を１だけ増加して（ステップＳＴ１５）、ステップＳＴ３に戻り、品目数ｋが１だけ多い大品目セットＬ（ｋ＋１）の生成が実行される。一方、大品目セットＬ（ｋ）が１つも生成されなかった場合には、処理を終了する。
【００７７】
以上のように、この実施の形態１によれば、大品目セットＬ（ｋ−１）を最後の品目以外の品目が共通するもの毎に読み出し、ハッシュ木に大品目セットＬ（ｋ−１）の共通部分である品目セットを追加し、その大品目セットＬ（ｋ−１）の最後の品目の集合のうちのいずれか２つを順番に選択し、その２つの品目をそれぞれ共通部分に追加して候補品目セットＣ（ｋ）を生成するとともに、ルール検証用品目セットＬＬ（ｋ−１）を生成してハッシュ木に追加した後にハッシュ木のための記憶容量を計算し、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、各候補品目セットＣ（ｋ）および各ルール検証用品目セットＬＬ（ｋ−１）の支持度を計算し、候補品目セットＣ（ｋ）のうち、支持度が所定の基準値より大きいものを大品目セットＬ（ｋ）として保存し、ルール検証用品目セットＬＬ（ｋ−１）および大品目セットＬ（ｋ）の支持度より計算される確信度またはχ２乗値に基づいて大品目セットＬ（ｋ）から相関ルールを生成し、その後にハッシュ木を消去するようにしたので、各大品目セットの処理毎にハッシュ木の使用する記憶容量を調べることになり、予め割り当てられた記憶容量を有効に使用することができるという効果が得られる。
【００７８】
実施の形態２．
この発明の実施の形態２による相関ルール抽出装置は、ルール検証用品目セットの支持度の計算についての処理を実施の形態１のものから変更したものである。ここでは、実施の形態２におけるルール検証用品目セットの支持度の計算についてのみ説明し、その他の処理については実施の形態１と同様であるのでその説明を省略する。
【００７９】
実施の形態２による相関ルール抽出装置においては、ルール検証用品目セットの支持度は、候補品目セット検証手段２１によりデータベース１のレコードを参照して行われる。そのとき候補品目セット検証手段２１は、データベース１からレコードを順次読み出し、各レコードと候補品目セットとのマッチングをするとともに、各レコードとルール検証用品目セットとのマッチングも並行して行う。
【００８０】
そして、候補品目セット検証手段２１は、データベース１のレコードにおける各候補品目セットの出現数および各ルール検証用品目セットの出現数をカウントして支持度を計算する。
【００８１】
以上のように、この実施の形態２によれば、データベース１から読み出したレコードに対して、候補品目セットおよびルール検証用品目セットのマッチングを並行して実行するようにしたので、大品目セットが多い場合には、大品目セットファイル３に保存された大品目セットを検索するより短い時間で各ルール検証用品目セットの支持度を計算することができるという効果が得られる。
【００８２】
実施の形態３．
この発明の実施の形態３による相関ルール抽出装置は、候補品目セットの支持度の計算についての処理を実施の形態１によるものから変更したものである。ここでは、実施の形態１における候補品目セットの支持度の計算についてのみ説明し、その他の処理については実施の形態１と同様であるのでその説明を省略する。
【００８３】
実施の形態３においては、候補品目セット検証手段２１は、候補品目セットの支持度を計算する際に、この計算とは関係ないルール検証用品目セットの部分木をハッシュ木から一時的に切り離し、この計算の終了後にその部分木をハッシュ木の元の位置に戻す。このとき候補品目セット検証手段２１は、ハッシュ木の切り離し位置に隣接する接続ノードと、その部分木のルートであるノードとの対応関係を記憶しておき、支持度の計算終了後に、その対応関係に基づいて、その部分木をハッシュ木の元の位置に戻す。
【００８４】
図８はハッシュ木から部分木を切り離す位置の一例を示す図である。図９はハッシュ木と、切り離した部分木との対応関係の一例を示す図である。例えば、図８に示すハッシュ木においては、候補品目セットが［２，４，５，６］，［２，４，５，７］であり、その他の枝がすべてルール検証用セットの枝である。したがって○印を付されたノードがハッシュ木から切り離されるが、このとき、切り離し位置を可能な限り少なく設定する。例えばルートから順番に下位へノードを探索していき、ノードの品目が、いずれの候補品目セットの対応する位置にも出現しない場合にそのノードへのリンクが切り離し位置に設定される。
【００８５】
すなわち、図８のハッシュ木においては、品目「４」が候補品目セットの第１品目に出現しないので、ルートから品目「４」のノードへのリンクが切り離し位置とされる。同様に、品目「５」が候補品目セットの第２品目に出現しないので、品目「２」のノードから品目「５」のノードへのリンクが切り離し位置とされ、品目「６」，「７」が候補品目セットの第３品目に出現しないので、品目「４」のノードから品目「６」，「７」のノードへのリンクがそれぞれ切り離し位置とされる。
【００８６】
そして、図９（ａ）に示すように切り離し位置に隣接するルートおよび品目「４」のノードへのポインタがａ，ｄ、品目「２」のノードおよび品目「５」のノードへのポインタがｂ，ｃ、品目「４」のノードおよび品目「６」，「７」のノードへのポインタがｅ，ｆ，ｇである場合には、図９（ｂ）に示すように、切り離し位置に隣接する２つのノードへのポインタが関連づけられて記憶される。このように、ハッシュ木の切り離し位置に隣接する接続ノードと、部分木のルートであるノードとの対応関係を記憶した後、ルートおよび品目「２」，「４」，「５」ノードの下位ノードへのリンク情報を書き換えて部分木を切り離し、支持度の計算終了後に、その対応関係（図９（ｂ））に基づいて、ルートおよび品目「２」，「４」，「５」ノードの下位ノードへのリンク情報を元に戻してその部分木をハッシュ木の元の位置に戻す。
【００８７】
以上のように、この実施の形態３によれば、候補品目セットの支持度の計算に関係のないルール検証用品目セットの部分木をハッシュ木から切り離すようにしたので、候補品目セットの支持度の計算に関係のないルール検証用品目セットについてのマッチングが行われず、効率的に候補品目セットのマッチングを実行することができるという効果が得られる。
【００８８】
実施の形態４．
この発明の実施の形態４による相関ルール抽出装置は、ハッシュ木の接続ノードと、ルール検証用品目セットの部分木のルートとの対応関係を示すデータをスタックによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木をハッシュ木の元の位置に戻すようにしたものである。その他の処理については実施の形態３と同様であるのでその説明を省略する。
【００８９】
実施の形態４においては、候補品目セット検証手段２１は、ハッシュ木の切り離し位置に隣接する接続ノードと、その部分木のルートであるノードとの対応関係を、一定の記憶容量のスタック領域において、スタックによるデータ構造に従って順次記憶していき、支持度の計算終了後に、その対応関係をスタックから順次読み出して、その部分木をハッシュ木の元の位置に戻す。
【００９０】
図１０はハッシュ木と、切り離した部分木との対応関係を記憶するスタックの一例を示す図である。例えば図８のハッシュ木からルール検証用品目セットの部分木を切り離す場合、図１０に示すように、切り離し位置に隣接する２つのノードへのポインタが関連づけられてスタックに記憶されていき、支持度の計算終了後に、逆順にスタックから読み出され、部分木が元の位置に戻される。
【００９１】
以上のように、この実施の形態４によれば、実施の形態３による効果の他、ハッシュ木の接続ノードと、ルール検証用品目セットの部分木のルートとの対応関係を示すデータをスタックによるデータ構造に従って記憶するようにしたので、メモリ管理を簡単化することができるという効果が得られる。
【００９２】
実施の形態５．
この発明の実施の形態５による相関ルール抽出装置は、ハッシュ木の接続ノードと、ルール検証用品目セットの部分木のルートとの対応関係を示すデータをリストによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木をハッシュ木の元の位置に戻すようにしたものである。その他の処理については実施の形態３と同様であるのでその説明を省略する。
【００９３】
実施の形態５においては、候補品目セット検証手段２１は、ハッシュ木の切り離し位置に隣接する接続ノードと、その部分木のルートであるノードとの対応関係をリストによるデータ構造に従って順次記憶していき、支持度の計算終了後に、その対応関係をリストから順次読み出して、その部分木をハッシュ木の元の位置に戻す。
【００９４】
図１１はハッシュ木と、切り離した部分木との対応関係を記憶するリストの一例を示す図である。例えば図８のハッシュ木からルール検証用品目セットの部分木を切り離す場合、図１１（ａ）に示すように、切り離された部分木のルートを一連のリストとして、図１１（ｂ）に示すように、切り離し位置に隣接する２つのノードへのポインタが関連づけられたレコードがリストとして記憶されていき、支持度の計算終了後に、各レコードがリストから順次読み出され、部分木が元の位置に戻される。
【００９５】
以上のように、この実施の形態５によれば、実施の形態３による効果の他、ハッシュ木の接続ノードと、ルール検証用品目セットの部分木のルートとの対応関係を示すデータをリストによるデータ構造に従って記憶するようにしたので、切り離し位置の数がいくつでもよく、また不要な記憶領域を予め確保する必要がなくメモリを効率良く使用することができるという効果が得られる。
【００９６】
実施の形態６．
この発明の実施の形態６による相関ルール抽出装置は、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、直前に追加された大品目セットの共通部分、候補品目セットおよびルール検証用品目セットをハッシュ木から削除するようにしたものである。その他の処理については実施の形態１と同様であるのでその説明を省略する。
【００９７】
実施の形態６においては、ハッシュ木操作手段２３は、読み出した大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加後のハッシュ木のための記憶容量を計算するが、ハッシュ木のための記憶容量が所定の基準値より大きい場合には、ハッシュ木から、これらの大品目セットの共通部分、候補品目セットおよびルール検証用品目セットに対応する部分木を削除する。
【００９８】
この後に候補品目セット検証手段２１は残りの候補品目セットおよびルール検証用品目セットの支持度を計算する。なお、このとき削除された大品目セットは、ハッシュ木が消去された後に、再度読み込まれて処理される。
【００９９】
以上のように、この実施の形態６によれば、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、直前に追加した大品目セットの共通部分、候補品目セットおよびルール検証用品目セットをハッシュ木から削除し、ハッシュ木のための記憶容量が所定の基準値以下である状態に戻した後、支持度の計算などを実行するようにしたので、使用記憶容量をより正確に制限することができるという効果が得られる。
【０１００】
実施の形態７．
この発明の実施の形態７による相関ルール抽出装置は、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量のうちの最大値が所定の記憶領域の残量より大きくなった場合に、大品目セットおよび相関ルールを生成し、その後にハッシュ木を消去する処理を実行するようにしたものである。その他の処理については実施の形態１と同様であるのでその説明を省略する。
【０１０１】
実施の形態７においては、ハッシュ木操作手段２３は、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットＬＬ（ｋ−１）がハッシュ木に追加された後に、ハッシュ木のための記憶容量を計算し、その計算結果と前回の計算結果との差を計算してハッシュ木のための記憶容量の増加量を計算する。次にハッシュ木操作手段２３は、その増加量と、前回までの増加量の最大値とを比較し、その増加量の値がその最大値より大きい場合には、その増加量の値でその最大値を更新する。そしてハッシュ木操作手段２３は、所定の基準値と今回計算したハッシュ木のための記憶容量との差である記憶容量の残量を計算し、その残量より上述の最大値が大きい場合には、大品目セットおよび相関ルールを生成し、その後にハッシュ木を消去する処理を実行させ、そうでない場合には、次の大品目セットを読み込み処理する。
【０１０２】
以上のように、この実施の形態７によれば、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量のうちの最大値が所定の記憶領域の残量より大きくなった場合に、大品目セットおよび相関ルールを生成し、その後にハッシュ木を消去する処理を実行するようにしたので、ハッシュ木のための記憶容量が所定の基準値を超える手前まで有効にメモリが使用されるという効果が得られる。
【０１０３】
実施の形態８．
この発明の実施の形態８による相関ルール抽出装置は、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量の平均値が所定の記憶領域の残量より大きくなった場合に、大品目セットおよび相関ルールを生成し、その後にハッシュ木を消去する処理を実行するようにしたものである。その他の処理については実施の形態１と同様であるのでその説明を省略する。
【０１０４】
実施の形態８においては、ハッシュ木操作手段２３は、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットＬＬ（ｋ−１）がハッシュ木に追加された後に、ハッシュ木のための記憶容量を計算し、その計算結果と前回の計算結果との差を計算してハッシュ木のための記憶容量の増加量を計算する。次にハッシュ木操作手段２３は、その増加量、前回までの増加量の平均値および追加の回数に基づいて今回までの増加量の平均値を計算する。そしてハッシュ木操作手段２３は、所定の基準値と今回計算したハッシュ木のための記憶容量との差である記憶容量の残量を計算し、その残量より上述の平均値が大きい場合には、大品目セットおよび相関ルールを生成し、その後にハッシュ木を消去する処理を実行させ、そうでない場合には、次の大品目セットを読み込み処理する。
【０１０５】
以上のように、この実施の形態８によれば、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量の平均値が所定の記憶領域の残量より大きくなった場合に、大品目セットおよび相関ルールを生成し、その後にハッシュ木を消去する処理を実行するようにしたので、ハッシュ木のための記憶容量が所定の基準値を超える手前まで有効にメモリが使用されるという効果が得られる。
【０１０６】
実施の形態９．
図１２はこの発明の実施の形態９による相関ルール抽出装置の構成を示すブロック図である。図において、１Ａは複数のレコードを表形式で保存し、レシート形式のデータを保存するデータベースである。ここでレシート形式とは、データベース１Ａのレコードにおける各属性の値に対する品目を連続させて表したものである。なお、このときの品目は例えば（属性番号｜属性値）なる２次元インデックスとされる。この場合、属性「性別」の値として「男」，「女」があり、属性「身長」の値として「大」，「中」，「小」があった場合、これらの属性の値は（１｜１），（１｜２）および（２｜１），（２｜２），（２｜３）なる２次元インデックスの品目でそれぞれ表される。
【０１０７】
５１はデータベース１Ａのレシート形式のレコードを読み出し、レコードに含まれる品目に基づいて各品目数の大品目セットをハッシュ木として展開していくとともに、その大品目セットから、確信度またはχ２乗値に基づいて相関ルールを生成する相関ルール抽出部である。５２はデータベース１Ａの表形式のレコードを読み出してレシート形式に変換して、変換後のレコードをデータベース１Ａに保存するレシートファイル生成手段（データ変換手段）である。
【０１０８】
相関ルール抽出部５１において、２Ａはデータベース１Ａに保存された２次元インデックス形式の品目に対応して処理を実行する候補品目セット検証手段２１Ａ、候補品目セット生成手段２２Ａおよびハッシュ木操作手段２３Ａを有する大品目セット生成手段である。
【０１０９】
なお、相関ルール抽出部５１におけるその他の構成要素については、実施の形態１（図１）におけるものと同様であるのでその説明を省略する。
【０１１０】
次に動作について説明する。
図１３は表形式の一例を示す図であり、図１４はレシート形式でデータベース１Ａに保存されたレコードの一例を示す図であり、図１５はレシート形式の品目により構成されるハッシュ木の一例を示す図である。
【０１１１】
まず、レシートファイル生成手段５２は、例えば図１３に示すような表形式で保存されたレコードを読み出し、表の各属性に対応して付される属性番号と、読み出したレコードにおけるその属性番号に対応する属性に対応して付される番号（属性値）とで構成される２次元インデックス形式（属性番号｜属性値）のデータをレコードの各属性値毎に生成してデータベース１Ａに保存させる。
【０１１２】
次に、相関ルール抽出部５１の大品目セット生成手段２Ａは、データベース１Ａからレシート形式のデータを適宜読み出して、メモリ６にハッシュ木を展開していき、実施の形態１と同様に各品目数の大品目セットを順次生成していく。
【０１１３】
ただし、ハッシュ木操作手段２３Ａおよび候補品目セット生成手段２２Ａがハッシュ木の枝伸ばしを実行する際に下記の規則に従って実行し、下記の規則に従わない品目はハッシュ木に追加されない。
規則１．属性番号が大きい品目ほど、その品目は「大」であるとする。例えば（４｜１）＞（２｜３）である。
規則２．属性番号が同じ場合、属性値が大きいほど、その品目は「大」であるとする。例えば（３｜５）＞（３｜２）である。
規則３．あるノードの品目の属性番号は、その上位のノードの品目の属性番号よりも大きくなければならない。例えば図１５のハッシュ木において、枝「（１｜１），（２｜１）」の下位に、品目「（２｜３）」のノードは追加されない。
【０１１４】
このようにすることにより、ハッシュ木のノードである品目の下位に追加できる品目が、同一の属性番号を有しない品目だけに制限されるため、同じ属性における属性値で構成される品目セットは生成されない。
【０１１５】
そして、相関ルール抽出部５１の仮説生成検証手段４は実施の形態１と同様にして相関ルールを生成する。
【０１１６】
以上のように、この実施の形態９によれば、属性番号と属性値で構成される２次元インデックスとしてデータベースに各品目を保存し、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号を有しない品目だけに制限して大品目セットを生成するようにしたので、同じ属性における属性値の相関ルールの生成を抑制することができ、負の相関ルールの生成を抑制することができるという効果が得られる。
【０１１７】
なお、上記実施の形態９においては、レシートファイル生成手段５２によりデータベース１Ａに記録されているデータの形式をレシート形式に変換するようにしているが、最初からレシート形式のデータをデータベース１Ａに記録するようにしてもよい。その場合には、レシートファイル生成手段５２は特に必要ない。
【０１１８】
また、上記実施の形態９においては、相関ルール抽出部５１が実施の形態１によるものとほぼ同様に構成されているが、相関ルール抽出部５１はこのように限定されるものではなく、ハッシュ木に品目セットを展開しながら大品目セットを生成していくものであれば他のものでもよい。
【０１１９】
実施の形態１０．
この発明の実施の形態１０による相関ルール抽出装置は、実施の形態９による相関ルール抽出装置において互いに相関ルールを生成しない複数の属性を指定可能にしたものである。その他の処理については実施の形態９と同様であるのでその説明を省略する。
【０１２０】
実施の形態１０においては、互いに相関ルールを生成しない複数の属性を属性グループとし、その属性グループの属性の値は、（属性グループ番号｜属性値）なる品目に変換される。例えば、属性「問診１」および属性「問診２」を属性グループと設定し、属性「問診１」の値が「ａ」，「ｂ」であり、属性「問診２」の値が「ａ」，「ｂ」，「ｃ」である場合には、これらの属性の値は、（１｜１），（１｜２），（１｜３）および（１｜４），（１｜５）なる品目に変換される。
【０１２１】
そしてハッシュ木の枝伸ばしを実行する際に実施の形態９と同様に下記の規則に従い、下記の規則に従わない品目はハッシュ木に追加されない。
規則１．属性グループ番号が大きい品目ほど、その品目は「大」であるとする。例えば（４｜１）＞（２｜３）である。
規則２．属性グループ番号が同じ場合、属性値が大きいほど、その品目は「大」であるとする。例えば（３｜５）＞（３｜２）である。
規則３．あるノードの品目の属性グループ番号は、その上位のノードの品目の属性グループ番号よりも大きくなければならない。例えば図１５のハッシュ木において、枝「（１｜１），（２｜１）」の下位に、品目「（２｜３）」のノードは追加されない。
【０１２２】
以上のように、この実施の形態１０によれば、実施の形態９による効果の他、互いに相関ルールを生成しない属性に対応する品目については同一の属性グループ番号を使用するようにしたので、不要な相関ルールの生成を抑制することができ、そのような相関ルールを除去する後処理を省略することができるという効果が得られる。
【０１２３】
実施の形態１１．
この発明の実施の形態１１による相関ルール抽出装置は、大品目セットの品目数がｋであるとき、大品目セットを品目数が１から（ｋ−１）までの条件部と品目数が（ｋ−１）から１までの帰結部とに分割してそれぞれ生成されるルールのうち、確信度またはχ２乗値が所定の基準値より大きいものを相関ルールとするものである。
【０１２４】
実施の形態１１においては、（ｋ−１）≧Ｎｃ≧１であるすべての整数Ｎｃについて、条件部の品目数がＮｃであり、帰結部の品目数が（ｋ−Ｎｃ）であるルールが大品目セットＬ（ｋ）から生成される。
【０１２５】
例えば、大品目セット「２，４，５，６」から、ルール「２，４，５→６」，「２，４，６→５」，「２，５，６→４」，「４，５，６→２」、ルール「２，４→５，６」，「２，５→４，６」，「２，６→４，５」，「４，５→２，６」、「４，６→２，５」，「５，６→２，４」およびルール「２→４，５，６」，「４→２，５，６」，「５→２，４，６」，「６→２，４，５」が生成される。同様に、大品目セット「２，４，５，７」から、ルール「２，４，５→７」，「２，４，７→５」，「２，５，７→４」，「４，５，７→２」、ルール「２，４→５，７」，「２，５→４，７」，「２，７→４，５」，「４，５→２，７」、「４，７→２，５」，「５，７→２，４」およびルール「２→４，５，７」，「４→２，５，７」，「５→２，４，７」，「７→２，４，５」が生成される。
【０１２６】
図１６はルールの条件部の品目数が１〜（ｋ−１）である場合に生成されるルール検証用品目セットＬＬ（１）〜ＬＬ（ｋ−１）を追加したハッシュ木の値例を示す図である。例えば実施の形態１のように大品目セットを生成する場合においては、このルールの条件部に相当するルール検証用品目セットＬＬ（１）〜ＬＬ（ｋ−１）が図１６に示すようにハッシュ木に追加される。
【０１２７】
そして、生成された各ルールについて、確信度またはχ２乗値が計算され、所定の基準値より高い確信度またはχ２乗値を有するルールが相関ルールとして保存される。
【０１２８】
なお、確信度またはχ２乗値を計算する際、品目数が１〜（ｋ−１）であるルールの条件部の支持度が必要になるが、例えば実施の形態１のように大品目セットを生成する場合においては、生成した大品目セットＬ（１）〜Ｌ（ｋ−１）を大品目セットファイル３から削除せずに保存しておくことにより、品目数が１〜（ｋ−１）であるルールの条件部と同一の大品目セットを大品目ファイル３で検索してルールの条件部の支持度を取得することができる。
【０１２９】
そして例えば図１６に示すハッシュ木においてそのルールの条件部に相当するルール検証用品目セットＬＬ（ｉ）（ｉ＝１〜（ｋ−１））に関連づけて記憶される。
【０１３０】
以上のように、この実施の形態１１によれば、品目数がｋである大品目セットから相関ルールの候補を作成する際に、条件部の品目数が１〜（ｋ−１）であり、帰結部の品目数が（ｋ−１）〜１である候補のルールをそれぞれ生成するようにしたので、帰結部が２以上の相関ルールを生成することができるという効果が得られる。
【０１３１】
さらに、生成した大品目セットＬ（１）〜Ｌ（ｋ−１）を保存しておき、ルールの条件部の支持度として使用するようにしたので、帰結部が２以上の相関ルールを生成する際にも、簡単に確信度またはχ２乗値を計算することができるという効果が得られる。
【０１３２】
なお、この実施の形態１１による相関ルール抽出装置における大品目セットの生成手順は、上記実施の形態１〜実施の形態１０によるものに限定されるものではなく、大品目セットをファイルに格納して管理する任意のアルゴリズムで有効である。
【０１３３】
実施の形態１２．
図１７はこの発明の実施の形態１２による相関ルール抽出装置の構成を示すブロック図である。実施の形態１２による相関ルール抽出装置は、上述の実施の形態１〜実施の形態１１による処理手順を記述したプログラムに従って動作するいわゆるコンピュータによるものである。
【０１３４】
図において、７１はＲＯＭ７２、ハードディスクドライブ装置７４、記録媒体９１などに予め記録されたプログラム８１，８１Ａに従って各種処理を実行するＣＰＵ（相関ルール生成手段、支持度計算手段、候補品目セット生成手段、ルール検証用品目セット生成手段、共通品目セット追加手段、記憶容量計算手段、相関ルール抽出部、データ変換手段）であり、７２は起動時に実行されるプログラムや各種処理に必要なデータなどを予め記憶するＲＯＭであり、７３はハードディスクドライブ装置７４や記録媒体９１に予め記録されたプログラム８１，８１Ａをロードされるとともに、各種処理において各種データを一時的に記憶するＲＡＭ（記憶手段）である。
【０１３５】
７４は上述の処理を記述したプログラム８１、データベース１，１Ａ、大品目セットファイル３、相関ルール集合ファイル５などを保存するハードディスクドライブ装置であり、７５は記録媒体９１に対してデータの読み書きを実行する記録媒体駆動装置である。なお、ＣＰＵ７１、ＲＯＭ７２、ＲＡＭ７３、ハードディスクドライブ装置７４および記録媒体駆動装置７５は互いにデータバスやアドレスバスで接続されている。なお、このバス構成は一例であり他の構成でもよい。９１は上述の処理を記述したプログラム８１Ａを記録されたフレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）などのコンピュータ読み取り可能な記録媒体である。
【０１３６】
次に動作について説明する。
まず、ユーザによる操作などに対応してＣＰＵ７１が、ハードディスクドライブ装置７４に記録されたプログラム８１または記録媒体９１に記憶されたプログラム８１ＡをＲＡＭ７３にロードして、そのプログラムに従って上述の実施の形態１〜実施の形態１１に記載の各種処理を実行する。すなわち、ＣＰＵ７１が上述の大品目セット生成手段２，２Ａおよび仮説生成検証手段４として動作し、ＲＡＭ７３がメモリ６として機能する。
【０１３７】
以上のように、この実施の形態１２によれば、上述の実施の形態１〜実施の形態１１による処理手順を記述したプログラムをコンピュータで実行して上述の各種処理を実行するようにしたので、上述の実施の形態１〜実施の形態１１による効果と同様の効果が得られる。
【０１３８】
【発明の効果】
以上のように、この発明によれば、所定の保存手段から大品目セットを最後の品目以外の品目が共通するもの毎に読み出し、所定の記憶手段に記憶されたハッシュ木に、大品目セットの共通部分である品目セットを追加し、読み出した大品目セットの最後の品目の集合のうちのいずれか２つを順番に選択し、その２つの品目をそれぞれ共通部分に追加して候補品目セットを生成し、各候補品目セットの一部であって候補品目セットより品目数が１だけ少ない品目セットをルール検証用品目セットとしてハッシュ木に追加し、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加後のハッシュ木のための記憶容量を計算し、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、各候補品目セットおよび各ルール検証用品目セットの支持度を計算し、候補品目セットのうち、支持度が所定の基準値より大きいものを大品目セットとして所定の保存手段に保存し、ルール検証用品目セットおよび大品目セットの支持度より計算される確信度またはχ２乗値に基づいて大品目セットから相関ルールを生成し、その後にハッシュ木を所定の記憶手段から消去するように構成したので、各大品目セットの処理毎にハッシュ木の使用する記憶容量を調べることになり、予め割り当てられた記憶容量を有効に使用することができるという効果がある。
【０１３９】
この発明によれば、大品目セットとともにその支持度を保存手段に保存し、各ルール検証用品目セットと同一の大品目セットが保存手段に保存されている場合には、その大品目セットの支持度をそのルール検証用品目セットの支持度とするように構成したので、大品目セットが少ない場合には、短い時間で各ルール検証用品目セットの支持度を取得することができるという効果がある。
【０１４０】
この発明によれば、データベースからレコードを読み出し、候補品目セットの出現数およびルール検証用品目セットの出現数を並行してカウントして候補品目セットの支持度およびルール検証用品目セットの支持度を計算するように構成したので、大品目セットが多い場合には、保存手段に保存された大品目セットを検索するより短い時間で各ルール検証用品目セットの支持度を計算することができるという効果がある。
【０１４１】
この発明によれば、ハッシュ木からルール検証用品目セットに対応する部分木を切り離した後、各候補品目セットの支持度を計算し、支持度の計算後、ルール検証用品目セットに対応する部分木をハッシュ木の元の位置に戻すように構成したので、候補品目セットの支持度の計算に関係のないルール検証用品目セットについてのマッチングが行われず、効率的に候補品目セットのマッチングを実行することができるという効果がある。
【０１４２】
この発明によれば、切り離した部分木が接続されていたハッシュ木の接続ノードとその部分木のルートとの対応関係を示すデータをスタックによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木をハッシュ木の元の位置に戻すように構成したので、メモリ管理を簡単化することができるという効果がある。
【０１４３】
この発明によれば、切り離した部分木が接続されていたハッシュ木の接続ノードとその部分木のルートとの対応関係を示すデータをリストによるデータ構造に従って記憶し、そのデータに基づいて、切り離した部分木をハッシュ木の元の位置に戻すように構成したので、切り離し位置の数がいくつでもよく、また不要な記憶領域を予め確保する必要がなくメモリを効率良く使用することができるという効果がある。
【０１４４】
この発明によれば、ハッシュ木のための記憶容量が所定の基準値より大きくなった場合に、直前に追加された大品目セットの共通部分、候補品目セットおよびルール検証用品目セットをハッシュ木から削除するように構成したので、使用記憶容量をより正確に制限することができるという効果がある。
【０１４５】
この発明によれば、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量のうちの最大値が、所定の基準値とハッシュ木のための記憶容量との差より大きくなった場合に、支持度を計算し、相関ルールを生成し、その後にハッシュ木を消去するように構成したので、ハッシュ木のための記憶容量が所定の基準値を超える手前まで有効にメモリが使用されるという効果がある。
【０１４６】
この発明によれば、大品目セットの共通部分、候補品目セットおよびルール検証用品目セットの追加によるハッシュ木のための記憶容量の増加量の平均値が、所定の基準値とハッシュ木のための記憶容量との差より大きくなった場合に、支持度を計算し、相関ルールを生成し、その後にハッシュ木を消去するように構成したので、ハッシュ木のための記憶容量が所定の基準値を超える手前まで有効にメモリが使用されるという効果がある。
【０１４７】
この発明によれば、属性番号と属性値で構成される２次元インデックスとして各品目をデータベースに保存し、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出するように構成したので、同じ属性における属性値の相関ルールの生成を抑制することができ、負の相関ルールの生成を抑制することができるという効果がある。
【０１４８】
この発明によれば、データベースに、各品目の値を、属性番号と属性値で構成される２次元インデックスとして、または、そのデータベースの複数の属性で構成される属性グループについての属性グループ番号とそれらのうちのいずれかの属性値で構成される２次元インデックスとして保存し、ハッシュ木のノードである品目の下位に追加できる品目を、同一の属性番号または属性グループ番号を有しない品目だけに制限して大品目セットを生成し、その大品目セットから相関ルールを抽出するように構成したので、不要な相関ルールの生成を抑制することができ、そのような相関ルールを除去する後処理を省略することができるという効果がある。
【０１４９】
この発明によれば、所定の表形式でデータベースに予め保存されたレコードの各属性値を２次元インデックスに変換し、その２次元インデックスをデータベースに保存するデータ変換手段を備えるようにしたので、データベースに表形式でレコードが記録されていても２次元インデックスに変換され、同様に、同じ属性における属性値の相関ルールの生成を抑制することができ、負の相関ルールの生成を抑制することができるという効果がある。
【０１５０】
この発明によれば、所定の保存手段に保存された大品目セットのうち、最後の品目以外の品目が共通する大品目セットから、その大品目セットより品目数が１だけ多い候補品目セットを生成し、候補品目セットの支持度を計算し、その支持度に基づいて候補品目セットと同一品目数の大品目セットを生成して保存手段に保存するステップと、大品目セットの品目数をｋとして、大品目セットを、品目数が１から（ｋ−１）までの条件部と品目数が（ｋ−１）から１までの帰結部とに分割してそれぞれ生成されるルールのうち、確信度またはχ２乗値が所定の基準値より大きいものを相関ルールとするように構成したので、帰結部が２以上の相関ルールを生成することができるという効果がある。
【０１５１】
この発明によれば、大品目セットを保存手段に保存する際に、その大品目セットの支持度も保存し、ルールの条件部と同一の大品目セットが保存手段に保存されている場合には、その大品目セットの支持度をそのルールの条件部の支持度としてルールの確信度またはχ２乗値を計算するように構成したので、帰結部が２以上の相関ルールを生成する際に、簡単に確信度またはχ２乗値を計算することができるという効果がある。
【図面の簡単な説明】
【図１】  この発明の実施の形態１による相関ルール抽出装置の構成を示すブロック図である。
【図２】  実施の形態１による相関ルール抽出装置の動作について説明するフローチャートである。
【図３】  大品目セットファイルの内容の一例を示す図である。
【図４】  図３の大品目セット［１，２，３］，［１，２，４］，［１，３，５］，［１，４，５］で構成されるハッシュ木を示す図である。
【図５】  図２のステップＳＴ３における動作の一例について説明する図である。
【図６】  図２のステップＳＴ４における動作の一例について説明する図である。
【図７】  図２のステップＳＴ５における動作の一例について説明する図である。
【図８】  ハッシュ木から部分木を切り離す位置の一例を示す図である。
【図９】  ハッシュ木と、切り離した部分木との対応関係の一例を示す図である。
【図１０】  ハッシュ木と、切り離した部分木との対応関係を記憶するスタックの一例を示す図である。
【図１１】  ハッシュ木と、切り離した部分木との対応関係を記憶するリストの一例を示す図である。
【図１２】  この発明の実施の形態９による相関ルール抽出装置の構成を示すブロック図である。
【図１３】  表形式の一例を示す図である。
【図１４】  レシート形式でデータベースに保存されたレコードの一例を示す図である。
【図１５】  レシート形式の品目により構成されるハッシュ木の一例を示す図である。
【図１６】  ルールの条件部の品目数が１〜（ｋ−１）である場合に生成されるルール検証用品目セットＬＬ（１）〜ＬＬ（ｋ−１）を追加したハッシュ木の値例を示す図である。
【図１７】  この発明の実施の形態１２による相関ルール抽出装置の構成を示すブロック図である。
【図１８】  従来の相関ルール抽出装置の構成例を示すブロック図である。
【図１９】  大品目セットを示すハッシュ木の一例を示す図である。
【図２０】  先に提案した第１の手法について説明する図である。
【図２１】  先に提案した第２の手法について説明する図である。
【符号の説明】
１，１Ａ  データベース、３  大品目セットファイル（保存手段）、４  仮説生成検証手段（相関ルール生成手段）、６  メモリ（記憶手段）、２１  候補品目セット検証手段（支持度計算手段）、２２  候補品目セット生成手段（候補品目セット生成手段、ルール検証用品目セット生成手段）、２３  ハッシュ木操作手段（共通品目セット追加手段、記憶容量計算手段）、５１  相関ルール抽出部、５２  レシートファイル生成手段（データ変換手段）、７１  ＣＰＵ（相関ルール生成手段、支持度計算手段、候補品目セット生成手段、ルール検証用品目セット生成手段、共通品目セット追加手段、記憶容量計算手段、相関ルール抽出部、データ変換手段）、７３  ＲＡＭ（記憶手段）、８１Ａ  プログラム、９１  記録媒体。
【図１】
0003810575.tif 000003
【図２】
0003810575.tif 000004
【図３】
0003810575.tif 000005
【図４】
0003810575.tif 000006
【図５】
0003810575.tif 000007
【図６】
0003810575.tif 000008
【図７】
0003810575.tif 000009
【図８】
0003810575.tif 000010
【図９】
0003810575.tif 000011
【図１０】
0003810575.tif 000012
【図１１】
0003810575.tif 000013
【図１２】
0003810575.tif 000014
【図１３】
0003810575.tif 000015
【図１４】
0003810575.tif 000016
【図１５】
0003810575.tif 000017
【図１６】
0003810575.tif 000018
【図１７】
0003810575.tif 000019
【図１８】
0003810575.tif 000020
【図１９】
0003810575.tif 000021
【図２０】
0003810575.tif 000022
【図２１】
0003810575.tif 000023