(57)【要約】【課題】本発明は時系列相関抽出装置に関し、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止する。【解決手段】複数の属性からなるレコードの集合からレコードの組み合わせを検索する場合、レコード内の所定属性が特定の値をとることをそれぞれ定義する複数のイベントと、その属性値の順序に基づいて定義された該複数のイベントの間の順序関係とを用いて検索パターンを指定する指定手段と、レコードの集合から指定された検索パターンに対応するレコードの組み合わせを検索する検索手段と、検索結果を出力する出力手段とを有する時系列フィルタ部４を備えると共に、時系列相関エンジン部５により時系列相関ルールを抽出する機能を有する。【選択図】　　　　図１
2004110327.tif 000002
【特許請求の範囲】
【請求項１】
時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては該シーケンスにおける順序を維持した形式で、与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めて時系列相関ルールを抽出する時系列相関抽出装置において、
入力データをフィルタリングして必要なデータを残す時系列フィルタ部と、入力データから時系列相関ルールを抽出する時系列相関エンジン部とを備えると共に、
前記時系列フィルタ部は、
複数の属性からなるレコードの集合からレコードの組み合わせを検索する際、レコード内の所定属性が特定の値をとることをそれぞれ定義する複数のイベントと、
その属性値の順序に基づいて定義された該複数のイベントの間の順序関係とを用いて、検索パターンを指定する指定手段と、
前記レコードの集合から、指定された検索パターンに対応するレコードの組み合わせを検索する検索手段と、
検索結果を出力する出力手段とを備えていることを特徴とする時系列相関抽出装置。
【請求項２】
前記時系列相関エンジン部の前段に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする請求項１記載の時系列相関抽出装置。
【請求項３】
前記時系列相関エンジン部の後段に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする請求項１記載の時系列相関抽出装置。
【請求項４】
前記時系列相関エンジンの前段と後段の両方に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする請求項１記載の時系列相関抽出装置。
【請求項５】
前記時系列フィルタ部を前記時系列相関エンジン部の外部に配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする請求項１乃至４のいずれかに記載の時系列相関抽出装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、大量のトランザクションデータから時系列相関ルールを抽出する時系列相関抽出装置に関する。
【０００２】
更に詳しくは、データベースに記録されたデータの間の関連規則を発見するデータベースマイニングに関連し、データベースの中の膨大なデータのうちで相関のあるデータの組み合わせの出現回数を数え上げる技術に関連する。そして、この技術を用いて数え上げられた結果から、与えられた条件に適合する組み合わせとその出現回数を用いて、データマイニング手法の中の１つである相関ルールの生成処理（相関ルールの抽出処理）が行われる。相関ルールを用いた相関分析は、近年、米国を中心として広く注目されている。
【０００３】
【従来の技術】以下、従来例について説明する。
【０００４】
§１：従来例１の説明
図４３は従来例１の説明図であり、Ａ図は時系列相関抽出装置の説明図、Ｂ図は処理フローチャートである。なお、図４３において、Ｓ１〜Ｓ６は各処理ステップを示す。
【０００５】
従来の時系列相関抽出装置は、図４３のＡ図のように、時系列相関抽出装置の内部に時系列相関エンジン部５を備え、前記時系列相関エンジン部５が入力データを取り込んで処理を行い相関ルールを抽出していた。この場合、一般に、時系列相関ルールの抽出では、生のトランザクションルールを使うか、期間、店舗等、ある部分に限定したトランザクションデータを使って処理を行っていた。
【０００６】
前記時系列相関エンジン部５が処理を行う場合、図４３のＢ図に示した処理フローチャートに従って処理を行っていた。この処理では、先ず、時系列相関エンジン部５はトランザクションデータを読み出し（Ｓ１）、空か否かを判断する（Ｓ２）。その結果、空ならば処理を終了するが、空でなければ、アイテムの組み合わせを生成し（Ｓ３）、組み合わせの数え上げを行う（Ｓ４）。
【０００７】
そして、時系列相関エンジン部５は、時系列相関ルール生成処理（又は抽出処理）を行い（Ｓ５）、生成した時系列相関ルールを出力し（Ｓ６）、Ｓ１の処理へ移行する。
【０００８】
§２：従来例２の説明
また、従来、時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては該シーケンスにおける順序を維持した形式で与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めて、時系列相関ルールを抽出する装置（本願の請求項１に記載された前提技術「時間的に・・・において」までの技術に相当する）が知られていた（特許文献１参照）。以下、特許文献１の内、本発明に特に関連する部分を、従来例２として詳細に説明する。
【０００９】
（１）　：構成の説明
従来例２では、以下の構成を含む情報を開示する。
【００１０】
▲１▼：それぞれ１個以上のアイテムをデータとして含む多数のトランザクションからアイテム１個ずつまたは２個以上のアイテムの組み合わせのうちで、前記トランザクションの中での出現回数が与えられた条件に適合するアイテム１個ずつまたは２個以上のアイテムの組み合わせとその出現回数とを求めるデータ組み合わせの数え上げ方法において、各トランザクションに含まれるアイテムを１個ずつカウントして、該１個ずつのアイテムの全トランザクションでの出現回数をカウントし、該カウント回数が与えられた条件に適合するアイテムを選択して、該アイテムと該カウント回数との組を数え上げ結果として出力し、該選択されたアイテムに対応したビットに“１”をセットしたビットマップを作成し、組み合わせ内のアイテムの個数を示すｉの値をｉ＝２とし、該ビットマップに“１”が立っている位置に対応するアイテムを用いて、各トランザクションに含まれるｉ個のアイテムの組み合わせを生成し、該生成されたアイテムの組み合わせの全トランザクションでの出現回数をカウントし、該カウント回数が与えられた条件に適合するアイテムの組み合わせを選択して、該アイテムの組み合わせと該カウント回数との組を数え上げ結果として出力し、該選択されたアイテムの組み合わせあるいは部分的組み合わせ、または該組み合わせに含まれるアイテム１個ずつに対応したビット位置に“１”をセットしたビットマップを作成し、ｉの値をインクリメントして前記ｉ個のアイテムの組み合わせの生成以降の処理を繰り返すことを特徴とする相関のあるデータ組み合わせの数え上げ方法。
【００１１】
▲２▼：前記▲１▼のデータ組み合わせの数え上げ方法において、前記多数のトランザクションのうちで、時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては、該シーケンスにおける順序を維持した形式で、前記与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めることを特徴とする相関のあるデータ組み合わせの数え上げ方法。
【００１２】
（２）　：属する技術分野
データベースに記録されたデータ間の関連規則を発見するデータマイニングに関し、更に詳しくは、データベース中の膨大なデータの内で相関のあるデータの組み合わせの出現回数を数え上げる方式に関し、この方式を用いて数え上げられた結果から、与えられた条件に適合する組み合わせとその出現回数を用いて、データマイニング手法の中の１つである相関ルールの生成処理（抽出処理）が行われる。
【００１３】
（３）　：従来の技術
▲１▼：データ組み合わせの数え上げ方式に関する従来技術
このデータ組み合わせの数え上げ方式は、データベースマイニングにおける相関ルール生成処理の一部を成すものであるため、まず相関ルールについて説明する。なお、後述するように本発明におけるデータ組み合わせの数え上げでは、その処理の一部として本発明のグループバイ処理方式が用いられている。
【００１４】
例として小売業においてＰＯＳ（Ｐｏｉｎｔ−ｏｆ　Ｓａｌｅｓ）で収集した１００人の顧客のレシートのうち、２０人の顧客が商品Ａを購入し、また、１２人の顧客が商品Ａと商品Ｂの両方を購入しているとする。１つの商品をアイテムと呼び、また、１枚のレシートをトランザクションと呼ぶ。
【００１５】
１つのトランザクションには、通常、複数のアイテムが含まれる。このとき、以下の定義式
アイテムのサポート＝アイテムを含むトランザクションの数／全トランザクション数
に基づいて商品Ａの「サポート」＝２０％、商品Ａと商品Ｂの「サポート」＝１２％となる。さらに、単純な条件付き確率計算により、「Ａを購入する顧客の６０％（１２％／２０％）がＢも購入する」と結論できる。これを「Ａ→Ｂ　確信度６０％、サポート１２％」と表し、相関ルールと定義する。つまり、相関ルール「Ａ→Ｂ」における確信度は、
「Ａ→Ｂ」の確信度＝Ａ∧Ｂ（ＡとＢの両方購入）のサポート／Ａのサポートである。更に、Ａ→Ｂといった単純なルールだけでなく、（Ａ∧Ｂ→Ｃ∧Ｄ∧Ｅ（「ＡとＢを購入する顧客がＣとＤとＥを購入する」）の様な複雑なルールも用いる。この場合の確信度は、
「Ａ∧Ｂ→Ｃ∧Ｄ∧Ｅ」の確信度＝Ａ∧Ｂ∧Ｃ∧Ｄ∧Ｅのサポート／Ａ∧Ｂのサポート
である。
【００１６】
相関ルールは、目玉商品がどの商品群の売り上げに貢献したかの評価、棚割り（どの商品とどの商品を近くに並べるべきか）の最適化や、クレジットカードのデータからダイレクトメールのヒット率を高めるといった、様々な局面に有効な情報である。
【００１７】
相関ルール生成処理は、（１）　：トランザクションの中から、与えられたサポートの条件を満たすアイテムの組み合わせの出現回数を数え上げる処理と、（２）　：前記（１）　で求められた組み合わせ群とその出現回数を基に、ルールとそのサポートおよび確信度の計算を行うという２つの段階からなる処理からなる。
【００１８】
前記（１）　において、与えられたサポートの条件を満たすアイテムの組み合わせ群を「ラージアイテムセット」と呼ぶ。サポートの条件としては、最小値（０％〔＝全ての組み合わせを数える〕〜１００％〔＝全部のトランザクションで購入されたアイテムを数える〕）から、最大値（最小値＜＝最大値＜＝１００％）の範囲であたえる。従来では、多くの場合、最大値を１００％に固定する手法が用いられている。
【００１９】
前記（１）　のラージアイテムセットの数え上げ処理は非常に時間のかかる処理であるため、各種の高速化手法が提案されている。中でも、ＳＱＬに基づくＳＥＴＭアルゴリズムと、ＩＢＭ（登録商標）が提案するいくつかのアルゴリズムの中のＡＰＲＩＯＲＩが代表的なものとして知られている。
【００２０】
ＳＥＴＭに基づく相関ルールの生成処理は、関係データベース問い合わせ言語であるＳＱＬ言語をベースとしており、実装が容易である特徴を持つ。処理に当たっては、ＳＱＬの結合演算（Ｊｏｉｎ　Ｏｐｅｒａｔｉｏｎ）とグループバイ演算（ＧｒｏｕｐＢｙ　Ｏｐｅｒａｔｉｏｎ　）を用いる。サポートの最小値の条件を満たす長さｋ−１のアイテムの組み合わせを含むトランザクションのテーブルを用いた自己結合演算を行い、長さｋのアイテムの組み合わせ候補を生成する。
【００２１】
次に、グループバイ演算を用いて、長さｋのラージアイテムセットを数え上げる。さらに、結合演算を用いてサポートの最小値を満足するトランザクション群を生成し、次の長さｋ＋１のアイテムの組み合わせ生成に利用する。
【００２２】
図４４は、ＳＥＴＭアルゴリズムにおける具体的な処理の流れを説明する図であり、図４５はＳＥＴＭアルゴリズムの処理における各機能ブロックの処理内容を示す図である。これらの図を用いて、従来技術としてのＳＥＴＭの処理について詳細に説明する。
【００２３】
図４４において、テーブルＲ１′は各トランザクションｔ　ｘに含まれるアイテムを示している。例えばトランザクション１にはアイテム１，２および３が含まれていることを示している。ＧＢ（１）　は１個ずつのアイテムの出現回数（グループバイ処理）を行うものであり、テーブルＬ１はそのカウント結果を、カウント数が２以上のアイテムに対して示したものである。
【００２４】
テーブルＲ１は、ジョインの処理（結合処理）Ｊ（１）　によって、テーブルＲ１′に含まれるデータのうちでテーブルＬ１に存在するアイテムだけを抜き出して結果を示す。
【００２５】
ＳＪ（１）　は、テーブルＲ１に対するセルフジョインの処理を示し、その結果テーブルＲ２′として、各トランザクションに対して２つのアイテムの可能な組み合わせが生成される。
【００２６】
グループバイ処理ＧＢ（２）　によって、２つのアイテムの組み合わせの出現回数がテーブルＲ２′の組み合わせに対してカウントされ、そのカウント結果のうちでカウント数が２以上のものがテーブルＬ２として作成される。
【００２７】
以下同様にして、３つのアイテムの組み合わせのうちでカウント数が２以上のもののテーブルＬ３が作られ、またアイテムが４個の組み合わせのうちでカウント数が２以上のものがテーブルＬ４として作られるが、テーブルＬ４の内容は空となる。
【００２８】
アプリオリ（Ａｐｒｉｏｒｉ）・アルゴリズムでは、サポートの最小値の条件を満たす長さｋ−１のラージアイテムセットを用いて長さｋのアイテムの組み合わせの候補を生成する。その際に、ｋ−１のラージアイテムセットがすべてメモリにのる場合、長さｋのアイテムの組み合わせの中の、長さｋ−１のすべての組み合わせがラージアイテムセットに含まれているかをチェックし、含まれている場合のみ、長さｋのアイテムの組み合わせの候補とみなす。
【００２９】
長さｋ−１のすべての組み合わせをメモリ上のハッシュ表（Ｈａｓｈ　Ｔａｂｌｅ）に登録しておくことにより、不必要な候補をプルーニング（Ｐｒｕｎｉｎｇ　）する。さらに、候補であるアイテムの組み合わせ群をハッシュ木（Ｈａｓｈ　Ｔｒｅｅ　）に保持し、各トランザクション毎にトランザクション中に含まれるアイテムの組み合わせがハッシュ木に登録されている場合、そのカウント値を増やすことにより、長さｋのアイテムの組み合わせの候補の出現回数を数え上げる。ハッシュ木に登録されている組み合わせのみを対象とすることにより、不必要な組み合わせの数え上げをしない工夫がなされている。
【００３０】
図４６は、アプリオリ（Ａｐｒｉｏｒｉ）・アルゴリズムにおける具体的な処理の流れを説明する図、図４７はアプリオリ（Ａｐｒｉｏｒｉ）・アルゴリズムにおける各機能ブロックの内容を説明する図である。これらの図に基づいて、Ａｐｒｉｏｒｉアルゴリズムによるラージアイテムセットの数え上げ処理の具体例について説明する。
【００３１】
図４６において、８つのトランザクションのリストＴＬの内容は実質的に図４４と同じである。まず最初にこれらのトランザクションに含まれるアイテムが１つずつＳｕｂｓｅｔ（１）　に入力され、１つ１つのアイテムの出現回数がＣ１としてカウントされる。そのカウント結果はＦに入力され、出現回数が２回以上のものがフィルタリングによって選択され、フィルタリング結果がＬ１として作成される。
【００３２】
Ｌ１の中に含まれるアイテムから２個の組み合わせが選択され、Ｃ２としてハッシュ木に登録される。そして各トランザクションの中のハッシュ木に登録された２個のアイテムの組み合わせが含まれている場合、Ｓｕｂｓｅｔ（２）　によってその出現回数をカウントすることによって、２個のアイテムの組み合わせの出現回数が求められ、その結果がＦによってフィルタリングされることにより、２個のアイテムの組み合わせのうちで出現回数が２回以上のものがＬ２として得られる。
【００３３】
以下同様の処理を実行することによって、３個のアイテムの組み合わせのうちで出現回数が２回以上のものがＬ３として得られ、また４個の組み合わせのうちで出現回数が２回以上のものが、図４４と同様に、存在しないことが判明した時点で処理を終了する。
【００３４】
（４）　：組み合わせ数え上げ方式の説明
図９６において、数え上げ方式は相関があると考えられるアイテムの組み合わせ候補を生成する組み合わせ生成部Ｃ（ｉ）　１、グループバイ処理によって組み合わせ候補のトランザクション内部での出現回数をカウントする出現回数数え上げ部Ｇ（ｉ）　２、出現回数のカウント値が例えばある指定された範囲にある場合にその組み合わせ相関のある組み合わせとして、ラージアイテムセットＬ（ｉ）　の要素として選択する組み合わせ選択部Ｆ３、および組み合わせ選択部Ｆ３の出力するラージアイテムセットから、組み合わせ生成部Ｃ（ｉ）　１によって組み合わせのプルーニングのために使用されるビットマップｂ１５，ｂ（ｉ−１）６を生成し、Ｃ（ｉ＋１）によって使用されるビットマップｂｉ７を追加するビットマップＢ（ｉ）　４から構成されている。
【００３５】
図９６の各部は以下のような処理を実行する。
Ｃ（ｉ）
・ｉ＝１の時：同一トランザクションに含まれるアイテムを１つづつＧ（ｉ）　へ送る。
・ｉ＞２の時：同一トランザクションに含まれるｉ個のアイテムの組み合わせの内、ビットマップフィルタｂ１，ｂ２，・・・ｂ（ｉ−１）により除外されないものをＧ（ｉ）　へ送る。ここで、フィルタｂ１，ｂ２，・・・ｂ（ｉ−１）は、図９６のｂ１，ｂ２，・・・ｂ（ｉ−１）に相当する。
Ｇ（ｉ）
・ｉ個のアイテムが並んだレコードを受け取り、そのレコード全体をキーとして後述のグループバイ処理を行い、各グループに含まれるレコードの個数を計算し、レコードにその個数を付け加えたものを出力する。
Ｆ
Ｇ（ｉ）　の出力を受け取り、個数が与えられた条件に合うものを長さｉのラージアイテムセットＬ（ｉ）　として出力する。
Ｂ（ｉ）
Ｆの出力［アイテム１・・・アイテムｉ，個数］を受け取り、ビットマップフィルタｂｊ（１≦ｊ≦ｉ）に対して、［アイテム１・・・アイテムｉ］の中から、全てのｊ個のアイテムの組み合わせを取り出し、それぞれの組み合わせに対して、Ｈｊ（ｊ個のアイテムの組み合わせ）で計算されるビット位置に“１”を立てる操作を行う。この時、ｂ１，ｂ２，・・・ｂ（ｉ−１）は既に存在するので、これらを更新する。ｂｉはまだ存在しないので、これを新規に作成し、更新を行う。
【００３６】
図９７は、組み合わせの数え上げ方式の全体処理フローチャートである。同図において処理が開始されると、まずステップＳ５０１でアイテムの組み合わせの個数としてのｉが１とされた後に、ステップＳ５０２でＬ（１）　が生成される。このＬ（１）　は１個のアイテムのみからなるラージアイテムセットである。
【００３７】
その後ステップＳ５０３でＬ（ｉ）　の要素数、すなわち組み合わせの数がｉ＋１以上あるか否かが判定される。ここでは、Ｌ（１）　のラージアイテムセットの要素数が２個以上であるか否かが判定され、この判定がＹｅｓの場合にはステップＳ５０４でｉの値がインクリメントされた後に、ステップＳ５０２以降の処理が繰り返される。
【００３８】
すなわち、ここでは２個のアイテムの組み合わせのうちで出現回数が指定された範囲にあるものの集合としてのラージアイテムセットＬ（２）　の生成がＳ５０２で行われ、続いてＳ５０３以降の処理が実行される。そしてステップＳ５０３でラージアイテムセットＬ（ｉ）　に含まれる要素の数がｉ＋１個以上でないと判定された時点で、処理を終了する。
【００３９】
図９８は、ラージアイテムセット生成処理のフローチャートである。同図において処理が開始されると、まずステップＳ５１０でトランザクションリストＴＬの先頭のトランザクションが読み出され、ステップＳ５１１でｉ個のアイテムの組み合わせ候補が生成され、その組み合わせ候補、すなわちアイテム１からアイテムｉまでの組み合わせが出現回数数え上げ部Ｇ（ｉ）　に送り込まれ、ステップＳ５１２でトランザクションリストが空か否かが判定され、空でない時にはステップＳ５１０以降の処理が繰り返され、トランザクションリストの内部から組み合わせ候補の生成とＧ（ｉ）　への送り込みが実行される。
【００４０】
ステップＳ５１２でトランザクションリストが空になったと判定されると、ステップＳ５１３で数え上げ部Ｇ（ｉ）　から、アイテムの組み合わせ候補とそのトランザクション内での出現回数、すなわち個数が組み合わせ選択部Ｆに送られ、組み合わせ選択処理が行われる。そしてステップＳ５１４で組み合わせ選択結果がラージアイテムセットＬ（ｉ）　として格納され、同時にラージアイテムセットにおけるアイテムの組み合わせ部分がビットマップ生成部Ｂ（ｉ）　に送られる。ステップＳ５１５でビットマップ生成処理が行われ、ステップＳ５１６で数え上げ部Ｇ（ｉ）　にまだレコードが存在するか否かが判定され、存在する場合にはステップＳ５１３以降の処理が繰り返され、存在しない場合には処理を終了する。
【００４１】
次に具体例を用いて、組み合わせの数え上げ方式の処理について更に詳細に説明する。ここでは具体例として、以下の４つのトランザクションＴ１〜Ｔ４からなるトランザクションリストＴＬを対象とする。
【００４２】
Ｔ１＝［１，２，４］、Ｔ２＝［２，３，６］
Ｔ３＝［１，４，５，６］、Ｔ４＝［１，２，４，５］
各トランザクション内部のアイテムは、その番号順にソートされているものとする。ここではラージアイテムセットとして選択される組み合わせ候補の出現回数、すなわち個数のサポートの最小値として５０％以上の条件を満たす個数、すなわち全トランザクションの数の４に対して個数が２以上となる条件を満たすものを組み合わせ選択部Ｆにおける選択条件とする。
【００４３】
まず長さ１のアイテムセットＬ（１）　の生成について説明する。図９９〜図１０２は長さ１のアイテムの組み合わせ候補の生成とその出現回数数え上げの説明図である。
【００４４】
はじめに、図９９でトランザクションＴ１［１，２，４］を読み込んで、Ｃ（１）　に入力する。Ｃ（１）　では、同一トランザクション中に含まれるアイテムを１つづつ、すなわち［１］，［２］，［４］の３個を出現回数数え上げ部Ｇ（１）　に入力する。Ｇ（１）　では、Ｃ（１）　から入力されたアイテム、［１］，［２］，［４］の出現回数を数え上げ、アイテムと個数をペアとして保持する。ここでは、アイテム［１］，［２］，［４］がそれぞれ１回づつ入力されたので、［アイテム，個数］の形式で、［１，１］，［２，１］，［４，１］を保持する。以上で、Ｔ１についての処理が終わる。
【００４５】
１つのトランザクションについてのＧ（１）　への入力処理が終了したら、Ｃ（１）　にもどって、次のトランザクションの処理を行う。図１００では、Ｔ２＝［２，３，６］について、［２］，［３］，［６］の３個のアイテムとしてのＧ（１）　に入力する。Ｇ（１）　では、それまでのトランザクションの処理で数え上げた個数に、入力されたアイテムと個数を追加していく。
【００４６】
アイテム［２］はＴＱとＴ２の両方で入力されるので、Ｔ２の処理が終了した段階では、［アイテム，個数］の形式で［２，２］と保持される。
【００４７】
以下同様に全てのトランザクションについて、Ｃ（１）　でアイテムを１つづつＧ（１）　に入力して、Ｇ（１）　で数え上げを行う。Ｔ４までのトランザクションを全て処理した結果、［アイテム，個数］の組は、［１，３］，［２，３］，［４，３］、［３，１］，［６，２］，［５，２］となる。この結果が図１０３である。
【００４８】
全てのトランザクションについてＧ（１）　への入力処理が終了したら、Ｇ（１）　から［アイテム，個数］の組を取り出し、Ｆにおいてサポートの最小値を満たすアイテムを選ぶ。図１０４〜図１０９は、この処理の説明図である。図１０４では、［１，３］の個数３がサポートの最小値５０％を満たしているので、これをラージアイテムセットＬ（１）　に登録する。と同時に、Ｂ（１）　では、アイテム［１］をビットマップｂ１に登録する。ここではアイテムに対応するビット位置（０〜５）は以下のハッシュ関数Ｈ１によって得られる。
Ｈ１（アイテム１）＝アイテム１の番号ｍｏｄ６．
この場合、トランザクション中のユニークなアイテムの総個数が６個であるから、ビットマップのビット数はそれにあわせて６とした。もし、ビットマップがメモリに入らない、あるいは他の処理のためにメモリを予約したいのであれば、ユニークなアイテムの総個数６より小さい値を取ることも可能である。ビットマップのすべてのビットは、最初は“０”である。アイテム［１］にハッシュ関数を適用すると、１ｍｏｄ６＝１を得るので、ｂ１の１に対応する上から２番目のビットに“１”を立てる。
【００４９】
次に、図１０５で、Ｇ（１）　から［２，３］を取り出し、アイテム［２］の個数３がサポートの最小値である５０％以上の条件を満たすのでラージアイテムセットとして登録する。同時に、２ｍｏｄ６＝２であるから、Ｂ（１）　ではビットマップｂ１の３番目のビットに“１”を立てる。
【００５０】
図１０６、図１０８、図１０９ではアイテムと個数のペアのうち［４，３］、［６，２］、［５，２］についてサポートの最小値の条件を満たしているので、［４］、［６］、［５］と個数の組をラージアイテムセットＬ（１）　に登録し、同時にビットマップｂ１のハッシュ関数値に“１”をセットする。
【００５１】
しかし、図１０７では、［３，１］について個数１がサポートの最小値の条件を満たしていないので、ラージアイテムセットＬ（１）　およびビットマップｂ１への登録は行わない。処理の結果、ビットマップｂ１＝｛１，１，１，０，１，１｝となり、長さ１のラージアイテムセットＬ（１）　＝｛［１，３］、［２，３］、［４，３］，［６，２］、［５，２］｝が生成される。
【００５２】
次に長さ２のラージアイテムセットＬ（２）　の生成について説明する。図１１０〜図１１３はアイテムの組み合わせ候補の数え上げまでの説明図である。長さ２のアイテムの組み合わせ生成では、既に作成されたビットマップｂ１を利用する。はじめに、図１１０でトランザクションＴ１＝［１，２，４］を読み込んで、ビットマップｂ１でセットされたアイテムだけを使って長さ２のアイテムの組み合わせの候補を生成する。ここでは、ｂ１に３つのアイテムが登録されているので、［１］，［２］，［４］の３つのアイテムから［１２］，［１４］，［２４］の３つのアイテムの組み合わせの候補を生成し、数え上げ部であるＧ（２）　では、Ｃ（２）　から入力されたアイテムの組み合わせ［１２］，［１４］，［２４］の出現回数を数え上げ、アイテムと個数を組として保持する。［１２］，［１４］，［２４］がそれぞれ１回づつ入力されたので、［アイテム１アイテム２，個数］の形式で、［１２，１］，［１４，１］，［２４，１］を保持する。以上で、Ｔ１についての処理が終わる。
【００５３】
次のトランザクションＴ２＝［２，３，６］のアイテムをビットマップｂ１でフィルタリングすると、アイテム［３］が落とされるので、その結果アイテムの組み合わせの候補として［２６］１つだけを図１１でＧ（２）　に入力する。Ｔ３、Ｔ４についても同様の処理を行うが、Ｔ３とＴ４にはビットマップｂ１でふるいにかけられて落とされるアイテムがないので、トランザクションから生成される全ての長さ２のアイテムの組み合わせを図１１２、図１１３でＧ（２）　に入力する。
【００５４】
全てのトランザクションについてＧ（２）　への入力処理が終了したら、Ｇ（２）　から、［アイテム１アイテム２，個数］を取り出し、Ｆで個数がサポートの最小値の条件を満たすものを選ぶ。この処理を図１１４〜図１２３に示す。［１２，２］の個数２がサポートの最小値５０％以上の条件を満たしているので、アイテムの組み合わせ候補［１２］と出現回数を図１１４でラージアイテムセットＬ（２）　に登録する。同時に、Ｂ（２）　では、アイテムの組み合わせ［１２］の各アイテム［１］，［２］をビットマップｂ１に登録する。この場合、ｂ１のビット位置１と２に“１”を立てる。更に、［１２］については以下のハッシュ関数Ｈ２で計算されるビットマップｂ２（ビット位置０〜４）のビット位置３に“１”を立てる。
【００５５】
Ｈ２（アイテム１，アイテム２）＝（アイテム１の番号＋アイテム２の番号）ｍｏｄ５．
このハッシュ関数Ｈ２ではアイテム１アイテム２の番号の和のｍｏｄ５を取るものを用いたので、ビットマップのビット数はこれに合わせて５とした。最初は、ｂ２の全ての５つのビットは“０”である。なお、ここでのハッシュ関数は例として設定したもので、実際にはハッシュ関数の効率を考慮して任意に設定できる。また、ビットマップのメモリの大きさを考慮に入れて任意に設定できる。ｂ１では常に１つのアイテムで“１”を立てるビット位置を決めるが、ｂ２は２個のアイテムを引数としたハッシュ関数によりビット位置を決定する。
【００５６】
図１１５、図１１６、図１１８、図１２０に示したように、［１４，３］，［２４，２］，［１５，２］，［４５，２］についてサポートの最小値を満たすので、アイテムをラージアイテムセットＬ（２）　に登録し、同時にビットマップｂ１とｂ２を更新する。これに対して図１１７、図１１９、図１２１〜図１２３では、サポートの最小値が満たされていないためアイテムセットへの登録とビットマップの更新は行われない。以上の結果、長さ２のラージアイテムセットＬ（２）　＝｛［１２，２］，［１４，３］，［２４，２］，［１５，２］，［４５，２］｝および、ｂ１＝｛０，１，１，０，１，１｝，ｂ２＝｛１，１，０，１，１｝が生成される。この結果を図１２３に示す。
【００５７】
次にＬ（３）　の生成について説明する。図１２４〜図１２７は組み合わせ候補数え上げまでの説明図である。長さ３のアイテムの組み合わせの生成では長さ２のラージアイテムセットを作成した際に生成したビットマップｂ１およびｂ２を利用する。まず、トランザクションＴ１＝［１，２，４］を読み込んで、ビットマップｂ１でセットされたアイテムだけを使って長さ３のアイテムの組み合わせを生成する。ここでは、［１］，［２］，［４］の３つのアイテムがｂ１にセットされている。次に長さ２のアイテムの組み合わせ［１２］，［１４］，［２，４］がビットマップｂ２でセットされているかどうかを調べる。この場合、ｂ２［Ｈ２（１，２）］＝ｂ２［Ｈ２（１，４）］＝ｂ２［Ｈ２（２，４）］＝１とすべてセットされていることから［１２４］を組み合わせ候補としてＧ（３）　に入力する。この処理を図１２４に示す。
【００５８】
図１２５に示すように、Ｔ２＝［２，３，６］の場合、ｂ１に［３］がセットされていないためふるい落とされて、トランザクションの長さが２となってしまうため、長さ３のアイテムの組み合わせ候補が生成できずＧ（３）　への入力は行わない。
【００５９】
Ｔ３＝［１，４，５，６］の場合、［１］，［４］，［５］，［６］に対応するｂ１のビットがセットされているので、４つの長さ３のアイテムの組み合わせ［１４５］，［１４６］，［１５６］，［４５６］が考えられるが、まず、それぞれについて、ビットマップｂ２のチェックを行う。［１４５］の場合、［１４］，［１５］，［４５］の全てについて、対応するｂ２のビットがセットされているので、組み合わせの候補として図１２６でＧ（３）　に入力する。
【００６０】
しかし、［１４６］の場合、［１４］，［４６］に対応するｂ２のビットはセットされているが、［１６］のビットはセットされていないため、［１４６］を組み合わせ候補としてＧ（３）　に入力しない。同様に、［４５６］の全ての２個のアイテムの組み合わせ［４５］，［４６］，［５６］に対応するｂ２のビットはセットされているので、［４５６］は組み合わせの候補としてＧ（３）　に入力されるが、［１５６］の中の［１６］のｂ２のビットはセットされていないためＧ（３）　に入力しない。
【００６１】
Ｔ４＝［１，２，４，５］についても同様なｂ１とｂ２のチェックを行い、組み合わせの候補として［１２４］と［１４５］をＧ（３）　に入力する。この結果を図１２７に示す。
【００６２】
この例では、不要な候補の生成を防ぐため、長さ３のアイテムの組み合わせ候補を生成する際に、全ての長さ２のアイテムの組み合わせに対応するビットマップｂ２のビットをチェックした。この手法は、不要な数え上げを防止するプルーニングとして有効であるが、例えば、処理に使用できるメモリの量が十分でない場合には各アイテムのチェック、あるいは２の長さのアイテムの組み合わせのチェックを行わない方法、すなわちｂ１あるいはｂ２を使用しない方法を取ることもできる。また、ｂ１とｂ２を使うがチェックする長さ２の組み合わせを少なくする方式もあり得る。
【００６３】
例えば、長さ３のアイテムの組み合わせを生成する際に、先頭の長さ２の組み合わせ１つだけをチェックするやり方を考えることができる。
【００６４】
Ｇ（３）　への入力処理が終了したら、図１２８〜図１３０に示すように、Ｇ（３）　から［アイテム１アイテム２アイテム３，個数］の組を取り出し、Ｆで個数がサポートの最小値の条件を満たすアイテムを選ぶ。図１２８では、［１２４，２］の個数２がサポートの最小値５０％以上という条件を満たしているので、これを長さ３のラージアイテムセットＬ（３）　に登録する。同様に、Ｂ（３）　では、［１２４］のアイテム［１］，［２］，［４］それぞれに対応するビットマップｂ１のビット位置に“１”を立てる。また、ハッシュ関数Ｈ３を用いて、すべての３つのアイテムの組み合わせ［１２４］に対応するビットマップｂ３のビット位置に“１”を立てる。
【００６５】
Ｈ３（アイテム１，アイテム２，アイテム３）＝（アイテム１の番号＋アイテム２の番号＋アイテム３の番号）ｍｏｄ５．
同時に、［１２４］の中から、２個のアイテムの組み合わせを取り出し、ビットマップｂ２を生成することもできるが、ここではｂ１とｂ３のみ生成する。
【００６６】
続いて行われる図１２９、図１３０の処理の結果、長さ３のラージアイテムセットＬ（３）　＝｛［１２４，２］，［１４５，２］｝，ビットマップｂ１＝｛０，１，１，０，１，１｝，ｂ３＝｛１，０，１，０，０｝が生成される。
【００６７】
図１３０では、長さ３のラージアイテムセットＬ（３）　の個数が２個であり、図９７のステップＳ５０３における終了条件の４個以下となったので処理を終了する。以上で、ラージアイテムセットの数え上げ処理が終了し、この結果を用いて相関ルールを生成することができる。
【００６８】
以上に述べた例では、ｉ＞１の場合のＣ（ｉ）　では、各トランザクションに対し、ビットマップｂ１，ｂ（ｉ−１）により除外されない長さｉのアイテムの組み合わせ候補が生成される。それと同時に、各トランザクションに対し、ビットマップｂ１、ｂ（ｉ−１）により除外されないアイテムのみを新たなトランザクションとして格納することもできる。これにより、ｉ＞２の場合、基のトランザクション群ＴＬではなく、Ｃ（ｉ−１）で生成されたリダクションされたトランザクション群からアイテムの組み合わせの候補を生成することができる。以上において相関ルール生成のために使用されるデータ組み合わせの数え上げ方式について詳細に説明した。
【００６９】
（５）　：相関分析の手法としての時系列分析への応用
この時系列分析は、長期間に渡る顧客の商品購入パターンの分析に利用される。顧客が第１のアイテムを購入した後に、所定の期間内に第２のアイテムを購入する確率を相関ルールとして知ることができれば、例えば小売業者はより効果的に在庫管理を行うことができる。
【００７０】
図４８は、顧客の長期間に渡る商品購入パターンとしてのシーケンスリストの説明図である。この図で第１のシーケンスは、ある顧客がアイテム３を１個だけ購入した後に、例えば次の日にアイテム８だけを購入し、更に、その１週間後にアイテム３と８を１づつ購入したというような、商品購入の時系列パターンを示している。
【００７１】
図４８の説明において１つのエレメントは前述のトランザクション、すなわち１枚のレシートに対応し、例えばアイテム３と８が同じエレメントに属するということは、アイテム３と８とが同一のレシートに記録されていることを示す。
【００７２】
以下に説明する時系列分析においてはサポートの最小値を４０％とする。図４８のシーケンスリストは５つのシーケンスによって構成されているために、４０％のサポートはアイテムの組み合わせの出現回数が２以上であることを示す。　時系列分析における組み合わせ生成部Ｃ（ｉ）　、数え上げ部Ｇ（ｉ）　、組み合わせ選択部Ｆ、およびビットマップＢ（ｉ）　の動作を以下に説明する。
Ｃ（ｉ）
・ｉ＝１の時：同一シーケンスに含まれるアイテムを１つづつＧ（ｉ）　へ送る。
・ｉ＞２の時：同一シーケンスに含まれるｉ個のアイテムの順列の内、ビットマップフィルタｂ１，ｂ２，・・・ｂ（ｉ−１）により除外されないものをＧ（ｉ）　へ送る。
Ｇ（ｉ）
ｉ個のアイテムの順列を受け取り、後述するグループバイ処理を行い、その個数を付け加えたものを出力する。
Ｆ
Ｇ（ｉ）　の出力を受け取り、個数が与えられた条件に合うものを長さｉのラージシーケンスＬ（ｉ）　として出力する。
Ｂ（ｉ）
Ｆの出力を受け取り、ビットマップフィルタｂｊ（１≦ｊ≦ｉ）に対して、ｉ個のアイテムの順列の中から、全てのｊ個のアイテムの順列を取り出し、それぞれの順列に対して、Ｈｊ（ｊ個のアイテムの順列）で計算されるビット位置に“１”を立てる操作を行う。
【００７３】
ｊ個のアイテムの順列の内部表現は［アイテム１，・・・アイテムｊ，セパレータ（ｊ−１）］、セパレータｋ（１≦ｋ≦ｊ−１）はアイテムｋとアイテム（ｋ＋１）が同じエレメントに属する場合は０、異なるエレメントに属する場合は１となる。
【００７４】
ハッシュ関数Ｈｊは、Ｈｊ（アイテム１，・・・アイテムｊ，セパレータ１，セパレータ（ｊ−１）＝（アイテム１の番号＋，・・・，＋アイテムｊの番号＋セパレータ１＋・・・，＋セパレータ（ｊ−１）ｍｏｄＮとする。Ｎはビットマップのビット数を示す。
【００７５】
図４９〜図５３はシーケンスリストに属する１個ずつの出現回数の数え上げ処理としてのＧ（１）　までの処理の説明図である。図４９〜図５３において、それぞれのシーケンスリストに含まれるアイテムが１個ずつＧ（１）　によってカウントされ、最終結果として図５３が得られる。
【００７６】
図５４〜図６１は、図４９〜図５３で得られたアイテム１個ずつの出現回数のカウント値に対応して、サポート値が４０％以上のアイテムを選択してラージシーケンスＬ（１）　を作成する処理と、同時にビットマップｂ１を作成する処理の説明図である。
【００７７】
例えば図５４において入力されるアイテム３はその個数が４であり、サポートの最小値を満たしているためラージシーケンスＬ（１）　の要素とされ、同時にそのアイテム３はビットマップ生成部Ｂ（１）　に与えられ、ビットマップｂ１へのビット設定が行われる。ここでビットマップｂ１のビット数は８である。
【００７８】
図５５〜図５８においては、組み合わせ選択部Ｆに入力されるアイテムの出現回数がサポート値を満たしているため、それらのアイテムはラージシーケンスＬ（１）　に追加されるが、図５９〜図６１で入力されるアイテムの出現回数はサポート値以下であるためラージシーケンスＬ（１）　への登録は行われず、この処理の最終結果は図６１となる。
【００７９】
図６２〜図６６は２個のアイテムの組み合わせ候補の数え上げ処理の説明図である。図６２において、Ｃ（２）　によって、ビットマップｂ１を用いたフィルタリングによって落とされないアイテムを用いて２つのアイテムの組み合わせ候補が生成され、その出現回数がＧ（２）　によってカウントされる。この組み合わせにおいては、シーケンスにおける順序があるため、また同じエレメントに属するか否かによって、次の３つの組み合わせ候補は別々のものとしてカウントされる。＜（３）　（８）　＞，＜（８）　（３）　＞，＜（３，８）＞
図６３〜図６６において、同様にして２つのアイテムの組み合わせ候補の数え上げが行われるが、例えば図６３においてアイテム１，２および６はビットマップｂ１によってフィルタリングされ、組み合わせ候補の生成には使用されない。また、図６６においてシーケンスに含まれるアイテムは１個のみであるため、２個のアイテムの組み合わせ候補は生成されず、図６５が最終結果となる。
【００８０】
図６７〜図７７は、図６２〜図６６において作成された２個のアイテムの組み合わせ候補のうち、サポート値を満たすものによるラージシーケンスＬ（２）　の作成と、ビットマップ作成部Ｂ（２）　によるビットマップｂ１、およびｂ２生成の処理の説明図である。図６７において、組み合わせ選択部Ｆに入力される２個のアイテムの組み合わせ候補はサポート値を満たしているため、ラージシーケンスＬ（２）　の要素とされ、２つのアイテム３，８に対してハッシュ関数Ｈ１、およびＨ２を用いてビットマップｂ１、およびｂ２のビット設定処理が行われる。
【００８１】
図６８〜図７１、図７５〜図７７において入力される組み合わせ候補はサポート値を満たしていないため、ラージシーケンスへの登録、およびビットマップのビット設定は行われない。
【００８２】
これに対して、図７２〜図７４において組み合わせ生成部Ｆに入力される組み合わせ候補はサポート値を満たしているため、ラージシーケンスリ（２）　への登録と、ビットマップのビット設定処理が行われ、この処理の最終結果は図７７となる。
【００８３】
図７８〜図８２は、３個のアイテムの組み合わせ候補のＧ（３）　によるカウント処理などの説明図である。図７８において最初のシーケンスが組み合わせ生成部Ｃ（３）　に入力されるが、このシーケンスから生成される３個のアイテムの組み合わせ候補はいずれもビットマップｂ２によってフィルタリングされ、Ｇ（３）　には入力されない。
【００８４】
図７９、および図８１において、組み合わせ生成部Ｃ（３）　によって生成される３個のアイテムの組み合わせ候補１種類だけがそれぞれＧ（３）　によってカウントされる。図８０および図８２においては、Ｇ（３）　に入力される組み合わせ候補は存在せず、この処理の最終結果は図８２となる。
【００８５】
図８３は、図７８〜図８２において作成された３個のアイテムの組み合わせ候補のうちサポート値を満足するものをラージシーケンスＬ（３）　に登録し、同時にビットマップｂ１、およびｂ３へビット設定を行う処理の説明図である。３個のアイテムの組み合わせ候補は１種類のみであり、組み合わせ生成部Ｆによってこの組み合わせ候補がラージシーケンスＬ（３）　とされ、またこの組み合わせ候補の中のアイテムを用いてビットマップｂ１、およびｂ３の設定が行われる。ラージシーケンスＬ（３）　の要素数は１個のみとなるため、組み合わせの数え上げ処理はここで終了する。
【００８６】
図８４は、従来技術の図４４および図４６におけると同じトランザクションリストを用いて、本発明における基本相関分析のためのアイテム組み合わせの数え上げ処理の流れを説明したものである。図８４においては、例えばラージアイテムセットＬ１に対応して作成されるビットマップｂ１を用いて、トランザクションリストから組み合わせ生成部Ｃ（２）　によってフィルタリングされないアイテム２個の組み合わせ候補が生成され、数え上げ部Ｇ（２）　に与えられる点に本発明の基本的な特徴がある。
【００８７】
このビットマップを生成する処理は簡単なものであり、またビットマップの容量は利用できるメモリ量にフィットするサイズにすることが常に可能であるため、図４４における結合処理量が大きいという問題点や、図４６におけるハッシュ木の容量が利用できるメモリ量よりも大きくなる場合があるというような問題点を解決することが可能である。
【００８８】
（６）　：組み合わせの出現回数数え上げ部Ｇ（ｉ）　において実行されるグループバイ処理
以上において本発明のデータの組み合わせ数え上げ方式の全体処理の説明を終了し、次に組み合わせの出現回数数え上げ部Ｇ（ｉ）　において実行されるグループバイ処理について説明する。
【００８９】
アイテムの組み合わせ候補の数え上げには本発明におけるグループバイ処理方式が用いられるが、その処理について具体例を用いて説明する。アイテムが１個のみのときにその出現回数を数え上げる場合には、アイテム番号をレコード値と考えることによって、前述のグループバイ処理方式をそのまま用いることができるため、ここでは２個のアイテムの組み合わせ候補の数え上げを具体例として説明する。
【００９０】
また、グループバイ処理方式としては、前述の第１の実施例と同様にハッシュ処理によってハッシュ済みリストと補助情報リストを作成した後に、グループバイ関数処理として同じキーの値を持つレコードの数え上げを行う場合を説明する。
【００９１】
入力レコードは次の１６件であり、それぞれのレコードはアイテムの番号を２つ持っており、その２つのアイテム番号によってハッシュ処理、およびソート処理におけるキーが決定されるものとする。
【００９２】
［１２］［１４］［２４］［２６］［１４］［１５］［１６］［４５］［４６］［５６］［１２］［１４］［１５］［２４］［２５］［４５］
このような場合のキーの比較方法として種々考えられるが、ここでは一例として辞書順を用いることにする。すなわち、２つのレコードを比較する時、まず１番目のアイテム番号で比較して大小がつけばそのままレコードのキーの大小関係とし、一番目のアイテム番号が等しければ２番目のアイテム番号を比較して、大小がつけばそのままキーの大小関係とし、２番目のアイテム番号も等しければ更に３番目のアイテム番号を比較するというような比較を続け、最後のアイテム番号まで等しければ２つのレコードのキーの値は等しいとする。
【００９３】
そこで例えば［１２］と［１４］とは、１番目のアイテム番号は等しいが、２番目のアイテム番号で比較することにより、［１２］より［１４］の方がキーの値が大きいとすることができる。
【００９４】
ハッシュ関数として適当なものを選んで使用することができるが、ここではハッシュ関数の一例として、次式のようにアイテム番号の総和に対して、３で割った時の余剰をとることにする。つまり［１２］のハッシュ値は（１＋２）ｍｏｄ３＝０で０となり、［１４］のハッシュ値は（１＋４）ｍｏｄ３＝２で２となる。
【００９５】
【数１】
2004110327.tif 000003
【００９６】
前述のグループバイ処理方式の第１の実施例と同様に、１６件の入力レコードからまずハッシュ済みリストが生成される。この時図９２のハッシュ表１５の大きさは３、レコードバッファ１４は４つ分のレコードの格納領域を持ち、ハッシュ済みリスト用出力バッファ１８は３つのレコードを格納できるものとする。　図８５はハッシュ済みリスト生成処理の経過の説明図である。同図においては、図９２の入力バッファ１３からレコードバッファ１４へのレコードの入力と、レコードバッファ１４からハッシュ済みリスト用出力バッファ１８へのレコードの出力の経過が示されている。図９３におけると同様に、１つのレコードが入力される時、すでに同じハッシュ値を持つレコードがハッシュ表のそのハッシュ値の領域からポイントされている時には、新しく入力されるレコードがハッシュ表からポイントされ、すでに入力されているレコードはリンク管理表によって管理される。
【００９７】
図８６は、図８５の処理結果としてのハッシュ済みリストである。図８５と比較することにより、ランとしてはブロック番号０〜２のランと、ブロック番号３〜５の２本のランが得られることが分かる。
【００９８】
次に補助情報リストとしては［ブロック番号、先頭レコードのハッシュ値、末尾レコードのハッシュ値］の形を用いるものとすると、次のような補助情報リストが得られる。この補助リストの形式はｉの値によっては変化しない。
【００９９】
［０，０，０］［１，１，２］［２，２，２］［３，０，０］［４，０，１］［５，１，１］
補助情報リストのソートによって、例えば次のようにソートされた補助情報リストが得られる。このソートの方式もｉの値によって変化しないものとする。
【０１００】
［０，０，０］［３，０，０］［４，０，１］［５，１，１］［１，１，２］［２，２，２］
このソートされた補助情報リストをもとに、図９４のグループバイ関数処理が行われるが、まず図９５における最小ハッシュ値レコード取り出し装置３３による処理を図８７に示す。ここではラン数分のハッシュ済みリスト用入力バッファは２個であり、２個のバッファにソートされた補助情報リスト３０の順番に従って入力されたレコードから最小ハッシュ値のレコードが１つずつ取り出され、最終的な結果は次のようになる。
【０１０１】
［２４］［１２］［１５］［４５］［４５］［４５］［１５］［２４］［１２］［２５］［１６］［４６］［１４］［２６］［５６］［１４］［１４］
この最小ハッシュ値レコード取り出し装置３３による処理結果を、ハッシュ値毎に分けると次のようになる。
【０１０２】
ハッシュ値０：［２４］［１２］［１５］［４５］［４５］［１５］［２４］［１２］
ハッシュ値１：［２５］［１６］［４６］
ハッシュ値２：［１４］［２６］［５６］［１４］［１４］
このようにハッシュ値が等しいレコードに対しては、図９５のソート装置３４によるソート処理が行われ、その結果がグループバイ関数演算処理装置３５に送られ、数え上げが実行される。このソートでは、前述した辞書式順序を用いることにする。図９４では、ハッシュ値０のレコードが取り出されなくなった時点でハッシュ値０のレコードのソートが行われ、ハッシュ値１のレコードが取り出されなくなった時点でハッシュ値１のレコードのソートが行われる。
【０１０３】
このような動作が最後まで繰り返され、出力されるレコードは［キー値，個数］の形式で表される。キー値はここでは２つのアイテム番号からなる。
【０１０４】
先ずハッシュ値（）のレコードのソートが行われ、［１２］［１２］［１５］［１５］［２４］［２４］［４５］［４５］
というソート結果が得られ、次にグループバイ関数演算処理装置３５にソート結果が送られ、
［１２，２］［１５，２］［２４，２］［４５，２］が得られる。次にハッシュ値１のレコードのソートが行われ、
［１６］［２５］［４６］
というソート結果が得られ、次にグループバイ関数演算処理装置３５にソート結果が送られ、
［１６，１］［２５，１］［４６，１］
が得られる。最後にハッシュ値２のレコードのソートが行われ、
［１４］［１４］［２６］［５６］
というソート結果が得られ、次にグループバイ関数演算処理装置３５にソート結果が送られ、
［１４，３］［２６，１］［５６，１］
という結果が得られる。
【０１０５】
全体では、
［１２，２］［１５，２］［２４，２］［４５，２］［１６，１］［２５，１］［４６，１］［１４，３］［２６，１］［５６，１］
という結果がえられる。
【０１０６】
以上詳細に説明したように、本発明のグループバイ処理方式においては、二次記憶装置に対するアクセスをできるだけ連続的にするために、比較的大きなブロック単位でのデータの逐次読み出しと逐次書き込みを行うことによってハッシュ処理を高速化し、そのハッシュ処理の結果を用いたグループバイ処理を実行することにより、全体としての高速化が可能になる。
【０１０７】
次に、本発明のデータ数え上げ組み合わせ方式においては、不必要なアイテムの組み合わせ候補のプルーニングのためにメモリ使用量を小さくできるビットマップを用いることにより、利用可能なメモリ量が小さい場合にもプルーニングが効率よく行え、更にアイテムセットを数え上げるグループバイ処理を高速化することによって、組み合わせの数え上げを効率的に実行することが可能になる。本発明のデータ組み合わせ数え上げ方式を、データベースのマイニング手法としての相関ルールの生成処理に応用することによって、データマイニングの効率化に寄与するところが大きい。
【０１０８】
【特許文献１】
特開平１１−３３４２号公報（特許請求の範囲の請求項４７〜５０、段落番号［０００１］〜［０００４］、［００２０］〜［００３７］、［０１７０］〜［０２０９］、［０２３９］〜［０２７９］、図３、８、９、１８、１９、４６、図４７〜７９、図１２４〜１７１）
（特許文献２）
特願２００１−３４０８１７（第２−１９頁、図１〜図３４）
【０１０９】
【発明が解決しようとする課題】前記のような従来のものにおいては、次のような課題があった。
【０１１０】
一般に、従来の時系列相関ルールの抽出では、生のトランザクションデータを使うか、期間、店舗等、ある部分に限定したトランザクションデータを使って処理を行う。こうした方法では、トランザクションの数が増えると組み合わせの数が増大し、処理に多大の時間を要することとなる。
【０１１１】
本発明は、このような従来の課題を解決し、前記のようなトランザクションの数が増えても、処理に多大の時間が掛かるのを防止することを目的とする。
【０１１２】
【課題を解決するための手段】本発明は前記の目的を達成するため、次のように構成した。
【０１１３】
（１）　：時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては該シーケンスにおける順序を維持した形式で、与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めて時系列相関ルールを抽出する時系列相関抽出装置において、入力データをフィルタリングして必要なデータを残す時系列フィルタ部と、入力データから時系列相関ルールを抽出する時系列相関エンジン部とを備えると共に、前記時系列フィルタ部は、複数の属性からなるレコードの集合からレコードの組み合わせを検索する際、レコード内の所定属性が特定の値をとることをそれぞれ定義する複数のイベントと、その属性値の順序に基づいて定義された該複数のイベントの間の順序関係とを用いて、検索パターンを指定する指定手段と、前記レコードの集合から、指定された検索パターンに対応するレコードの組み合わせを検索する検索手段と、検索結果を出力する出力手段とを備えていることを特徴とする。
【０１１４】
（２）　：前記（１）　の時系列相関抽出装置において、前記時系列相関エンジン部の前段に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする。
【０１１５】
（３）　：前記（１）　の時系列相関抽出装置において、前記時系列相関エンジン部の後段に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする。
【０１１６】
（４）　：前記（１）　の時系列相関抽出装置において、前記時系列相関エンジンの前段と後段の両方に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする。
【０１１７】
（５）　：前記（１）　乃至（４）　の何れかの時系列相関抽出装置において、前記時系列フィルタ部を前記時系列相関エンジン部の外部に配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする。
【０１１８】
（作用）
前記構成に基づく本発明の作用を、図１に基づいて説明する。
【０１１９】
（ａ）　：前記（１）　の時系列相関抽出装置では、時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては該シーケンスにおける順序を維持した形式で、前記与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めて、時系列と相関データを抽出する。
【０１２０】
この場合、時系列フィルタ部４は、入力データをフィルタリングして必要なデータを残す処理を行い、時系列相関エンジン部５は、入力データから時系列相関ルールを生成して抽出する処理を行うが、特に、前記時系列フィルタ部４は、次のような処理を行う。
【０１２１】
すなわち、時系列フィルタ部４は、前記指定手段、検索手段、出力手段を備え、複数の属性からなるレコードの集合からレコードの組み合わせを検索する。この時、前記指定手段は、レコード内の所定属性が特定の値をとることをそれぞれ定義する複数イベントと、属性の順序に基づいて定義されたそれらのイベントの間の順序関係とを用いて、検索パターン（イベントパターン）を指定する。
【０１２２】
前記検索手段は、レコードの集合から、指定された検索パターンに対応するレコードの組み合わせを検索し、出力手段は、検索結果を出力する。イベントは、レコード内の所定属性が特定の値をとる状態として定義され、複数のイベントの間の順序関係は、それらのイベントに対応するレコードの間において、１つ以上の属性の値の順序関係に基づいて定義される。
【０１２３】
ユーザは、指定手段を用いて、これらのイベントとイベント間の順序関係により決められる検索パターンを指定する。指定手段は、検索パターンを検索手段に渡し、検索手段は、受け取った検索パターンを解釈して、検索パターンに対応するレコードの組み合わせを抽出する。そして、出力手段は、抽出されたレコード等の情報を検索結果として出力する。
【０１２４】
このような装置によれば、２つ以上のイベントが同じ順序に存在する場合や、複数のイベントの順序関係が任意の間隔で記述される場合を含めて、様々な検索パターンを容易に指定することが可能となり、順序を考慮した汎用的な時系列フィルタリング処理を行うことができる。このようにして、前記のようなトランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０１２５】
（ｂ）　：前記（２）　では、時系列フィルタ部４を時系列相関エンジン部５の前段に配置し、時系列フィルタ部４と時系列相関エンジン部５を１つのプログラムで構成した例である。この場合、入力データは時系列フィルタ部４でフィルタリング処理を行うことで、組み合わせを減少させ、処理の時間短縮を行う。
【０１２６】
次に、時系列相関エンジン部５で時系列相関ルールを生成して抽出し、出力する。このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０１２７】
（ｃ）　：前記（３）　では、時系列相関エンジン部５を時系列フィルタ部４の前段に配置し、時系列相関エンジン部５と時系列フィルタ部４を１つのプログラムとして構成した例である。この場合、入力データは時系列相関エンジン部５で時系列相関ルールを生成し抽出し、その後、時系列フィルタ部４でフィルタリング処理を行い、時系列相関ルールを抽出して出力する。このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０１２８】
（ｄ）　：前記（４）　では、時系列相関エンジン部５の前後両方に時系列フィルタ部４を配置し、２つの時系列フィルタ部４と１つの時系列相関エンジン部５を１つのプログラムで構成した例である。この場合、入力データは時系列フィルタ部４でフィルタリング処理を行い、その後、時系列相関エンジン部５で時系列相関ルールを生成して抽出し、更に、別の時系列フィルタ部４でフィルタリングを行うことで相関ルールを出力する。
【０１２９】
この例では、前段の時系列フィルタ部４で組み合わせを減少させ、後段の時系列フィルタ部４で無駄なものを除外する機能がある。このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０１３０】
（ｅ）　：前記（５）　では、時系列フィルタ部４と時系列相関エンジン部５とをそれぞれ別の１つのプログラム部で構成した例である。すなわち、時系列フィルタ部４を１つのプログラムで構成し、時系列相関エンジン部５を別の１つのプログラムで構成する。
【０１３１】
このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。また、時系列フィルタ部４と時系列相関エンジン部５が別のプログラムで構成されているので、並列処理が可能であり、更に、時系列フィルタ部４の取り換えが可能である。
【０１３２】
【発明の実施の形態】以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【０１３３】
§１：時系列相関抽出装置の説明
（１）　：時系列相関抽出装置の構成の説明
図２は時系列相関抽出装置の説明図である。以下、図２に基づいて、時系列相関抽出装置の構成を説明する。
【０１３４】
図２に示したように、時系列相関抽出装置１には、入力装置２と出力装置３が接続されている。また、時系列相関抽出装置１の内部には、時系列フィルタ部４と、時系列相関エンジン部５等を備えている。
【０１３５】
前記入力装置２は、相関ルールを求めるべき入力データや他のデータを入力するものである。時系列フィルタ部４は、入力データをフィルタリングして必要なデータを残すものである。時系列相関エンジン部５は、入力データから時系列相関ルールを生成して抽出するものである。出力装置３は、抽出された相関ルールを出力するものである。
【０１３６】
（２）　：時系列相関抽出装置のプログラムの説明
図３は時系列相関抽出装置のプログラムの説明図（その１）であり、Ａ図は例１、Ｂ図は例２、Ｃ図は例３、Ｄ図は例４を示す。また、図４は時系列相関抽出装置のプログラムの説明図（その２）であり、Ｅ図は例５、Ｆ図は例６、Ｇ図は例７、Ｈ図は例８を示す。
【０１３７】
前記時系列フィルタ部４と時系列相関エンジン部５は、それぞれプログラムにより構成されており、これらの各プログラムの関係は次のようになっている。なお、図３、図４において、Ｐ部は１つの１つのプログラム部（１つのプログラムと同じ）で構成されていることを示している。また、Ｐ１、Ｐ２もそれぞれ１つのプログラム部（１つのプログラム）で構成されていることを示している。
【０１３８】
▲１▼：例１（図３のＡ図参照）は、時系列フィルタ部４を時系列相関エンジン部５の前段に置いた例であり、時系列フィルタ部４と時系列相関エンジン部５をＰ部（１つのプログラム）で構成した例である。この場合、入力データは時系列フィルタ部４でフィルタリング処理を行い、その後、時系列相関エンジン部５で時系列相関ルールを抽出して出力する。
【０１３９】
このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０１４０】
▲２▼：例２（図３のＢ図参照）は、例１と逆に、時系列相関エンジン部５を時系列フィルタ部４の前段に置いた例であり、時系列相関エンジン部５と時系列フィルタ部４をＰ部（１つのプログラム）として構成した例である。この場合、入力データは時系列相関エンジン部５で時系列相関ルールを生成して抽出し、その後、時系列フィルタ部４でフィルタリング処理を行い、時系列相関ルールを抽出して出力する。
【０１４１】
このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０１４２】
▲３▼：例３（図３のＣ図参照）は、時系列相関エンジン部５の前後両方に時系列フィルタ部４を設け、２つの時系列フィルタ部４と１つの時系列相関エンジン部５をＰ部（１つのプログラム）で構成した例である。この場合、入力データは時系列フィルタ部４でフィルタリング処理を行い、その後、時系列相関エンジン部５で時系列相関ルールを生成して抽出し、更に、別の時系列フィルタ部４でフィルタリングを行うことで相関ルールを出力する。
【０１４３】
この例では、前段の時系列フィルタ部４で組み合わせを減少させ、後段の時系列フィルタ部４で無駄なものを除外する機能がある。このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０１４４】
▲４▼：例４（図３のＤ図参照）は、時系列フィルタ部４と時系列相関エンジン部５とをそれぞれ別の１つのプログラム部で構成した例である。すなわち、時系列フィルタ部４をＰ１部（１つのプログラム）で構成し、時系列相関エンジン部５を別のＰ２部（１つのプログラム）で構成する。
【０１４５】
このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。また、時系列フィルタ部４と時系列相関エンジン部５が別のプログラムで構成されているので、並列処理が可能であり、更に、時系列フィルタ部４の取り換えが可能である。
【０１４６】
▲５▼：例５（図４のＥ図参照）は、時系列フィルタ部４と時系列相関エンジン部５とをそれぞれ別の１つのプログラム部で構成した例であり、時系列相関エンジン部５と時系列フィルタ部４の配列は例４と逆である。すなわち、前段に時系列相関エンジン部５をＰ１部（１つのプログラム）で構成し、後段に、時系列フィルタ部４を別のＰ２部（１つのプログラム）で構成する。
【０１４７】
▲６▼：例６（図４のＦ図参照）は、前段に、時系列フィルタ部４をＰ１部（１つのプログラム）で構成し、後段に、時系列相関エンジン部５と時系列フィルタ部４をＰ２部（１つのプログラム）で構成した例である。この場合、Ｐ１部とＰ２部は別のプログラムである。
【０１４８】
▲７▼：例７（図４のＧ図参照）は、前段に、時系列フィルタ部４と時系列相関エンジン部５をＰ１部（１つのプログラム）で構成し、後段に、時系列フィルタ部４をＰ２部（１つのプログラム）で構成した例である。この場合、Ｐ１部とＰ２部は別のプログラムである。
【０１４９】
▲８▼：例８（図４のＨ図参照）は、時系列相関エンジン部５の前後両方に時系列フィルタ部４を設け、２つの時系列フィルタ部４と１つの時系列相関エンジン部５を、それぞれ別々のプログラムで構成した例である（例３の２つの時系列フィルタ部４と１つの時系列相関エンジン部５をそれぞ別々のプログラムで構成した例である）。
【０１５０】
すなわち、最前段には時系列フィルタ部４をＰ１部（１つのプログラム）で構成し、その後段に、時系列相関エンジン部５をＰ２部（１つのプログラム）で構成し、更に、その後段に、時系列フィルタ部４をＰ３部（１つのプログラム）で構成したものである。
【０１５１】
（３）　：入力データ形式の説明
図５は入力データ形式を示す図であり、Ａ図は入力データ（テキスト形式）、Ｂ図は形式の説明図である。すなわち、図５のＡ図は、入力データをテキスト表現したもの、図５のＢ図は形式の説明図である。また、図６は処理の説明図であり、Ａ図は組み合わせ（長さ２）、Ｂ図はＣＩＤ＝１，４を削除した組み合わせ、Ｃ図は単純なフィルタでは効果がない入力を示す。
【０１５２】
図５において、「ＣＩＤ」は顧客ＩＤ等の識別番号を表す。「数」はアイテムの数を表す。アイテムの数は区切り文字「｜」も含める。「Ｉｔｅｍコート゛　」はアイテムの識別番号を表す。入力は、ＣＩＤ毎に一連の時系列データとなる。Ｉｔｅｍコート゛　は古い時間から新しい時間の順に、図の左から右に並べられる。区切り文字「｜」の間のアイテム（「，」で区切られたアイテム）には順序関係はない。
【０１５３】
ここで、最後にアイテム「６」というイベントが発生した相関ルール（「Ｘ→６」という表現となる）を見つけたいものとする。従来の相関エンジンでは、図５のＡ図の入力データから図６のＡ図のような組み合わせを生成する。長さ２の場合、一意の組み合わせは図６のＡ図のように２９通りとなる。
【０１５４】
ここで、入力データを時系列フィルタ部４によってフィルタリングして、最後に「６」というイベントが発生していないＣＩＤ（ＣＩＤ＝１，４）のデータを削除する。この場合の組み合わせは、図６のＢ図のように４通りまで削減される。
【０１５５】
一般に、時系列相関ルールの抽出処理では、組み合わせの生成に大部分の時間を要する。また、組み合わせはデータの期間（長さ）が長くなれば、爆発的に多くなる。このため、予め不要なデータを削除することは、処理時間の短縮のために極めて有効な手段となる。ただし、最後に「６」というイベントが発生した相関ルールを見つけたいような場合、入力データに６が含まれないＣＩＤのデータを単純に削除するだけではうまくいかない。２個以上の長さのイベントがあり、かつ２個目以降にイベント「６」が発生しているもの、以外のデータを削除できる時系列フィルタ部４をここでは用いる必要がある。図６のＣ図のような入力の場合、イベント「６」を含まないデータを削除する単純なフィルタの場合は全く効果がない。
【０１５６】
（４）　：フローチャートによる処理の説明
▲１▼：例１の説明
図７は例１の処理フローチャートである。以下、図７に基づいて、例１の処理を説明する。なお、Ｓ１１〜Ｓ１５は各処理ステップを示す。
【０１５７】
例１は、図３のＡ図に示した例１の処理であり、Ｓ１１〜Ｓ１４が時系列フィルタ部４の処理、Ｓ１５が時系列相関エンジン部５の処理である。この処理では、先ず、時系列フィルタ部４はデータ有りか否かを調べ（Ｓ１１）、データがなければそのまま処理を終了するが、データが有れば、データを入力し（Ｓ１２）、時系列フィルタ部４の処理を行う（Ｓ１３）。
【０１５８】
そして、時系列フィルタ部４は、フィルタ条件を満たしているか否かを調べ（Ｓ１４）、前記条件に不適合であれば、Ｓ１１の処理へ移行する。しかし、フィルタ条件に適合していれば、時系列相関エンジン部５による処理へ移行する（Ｓ１５）。このようにして前記Ｐ部での時系列フィルタ部４と時系列相関エンジン部５の処理を終了する。
【０１５９】
▲２▼：例２の説明
図８は例２の処理フローチャートである。以下、図８に基づいて、例２の処理を説明する。なお、Ｓ２１〜Ｓ２６は各処理ステップを示す。
【０１６０】
例２は、図３のＢ図に示した例２の処理であり、Ｓ２１〜Ｓ２３が時系列相関エンジン部５の処理、Ｓ２４〜Ｓ２６が時系列フィルタ部４の処理である。この処理では、時系列相関エンジン部５は、データ有りか否かを調べ（Ｓ２１）、データがなければそのまま処理を終了するが、データが有れば、データを入力する（Ｓ２２）。そして、時系列相関エンジン部５による処理を行う（Ｓ２３）。
【０１６１】
次に、時系列フィルタ部４は、時系列フィルタ部４の処理を行い（Ｓ２４）、フィルタ条件を満たしているか否かを調べ（Ｓ２５）、フィルタ条件に不適合であれば、Ｓ２１の処理へ移行する。しかし、フィルタ条件に適合していれば、データの出力を行う（Ｓ２６）。
【０１６２】
▲３▼：例３の説明
図９は例３の処理フローチャートである。以下、図９に基づいて、例３の処理を説明する。なお、Ｓ３１〜Ｓ３９は各処理ステップを示す。
【０１６３】
例３は、図３のＣ図に示した例３の処理であり、Ｓ３１〜Ｓ３４が時系列フィルタ部４の処理、Ｓ３５は時系列相関エンジン部５の処理、Ｓ３６〜Ｓ３９が時系列フィルタ部４の処理である。
【０１６４】
この処理では、先ず、時系列フィルタ部４はデータ有りか否かを調べ（Ｓ３１）、データがなければそのまま処理を終了するが、データが有れば、データを入力し（Ｓ３２）、時系列フィルタ部４の処理を行う（Ｓ３３）。そして、時系列フィルタ部４は、フィルタ条件を満たしているか否かを調べ（Ｓ１４）、前記条件に不適合であれば、Ｓ３１の処理へ移行する。
【０１６５】
しかし、フィルタ条件に適合していれば、時系列相関エンジン部５による処理を行う（Ｓ３５）。その後、再び、時系列フィルタ部４はデータ有りか否かを調べ（Ｓ３６）、データがなければそのまま処理を終了するが、データが有れば、時系列フィルタ部４の処理を行う（Ｓ３７）。そして、時系列フィルタ部４は、フィルタ条件を満たしているか否かを調べ（Ｓ３８）、前記条件に不適合であれば、Ｓ３６の処理へ移行する。しかし、フィルタ条件に適合していれば、データの出力を行い（Ｓ３９）、Ｓ３１の処理へ移行する。
【０１６６】
（５）　：具体的な装置例の説明
図１０は具体的な装置の構成図である。前記時系列相関抽出装置は、は、ワークステーション、パーソナルコンピュータ等の任意のコンピュータにより実現することができる。この装置は、コンピュータ本体１０と、該コンピュータ本体１０に接続されたディスプレイ装置１１、入力装置（キーボード／マウス等）１２、リムーバブルディスクドライブ（「ＲＤＤ」という）１３、ハードディスク装置（「ＨＤＤ」という）１４等で構成されている。
【０１６７】
そして、コンピュータ本体１０には、内部の各種制御や処理を行うＣＰＵ１５と、プログラムや各種データを格納しておくためのＲＯＭ１６（不揮発性メモリ）と、メモリ１７と、インタフェース制御部（「Ｉ／Ｆ制御部」という）１８と、通信制御部１９等が設けてある。なお、前記ＲＤＤ１３には、フレキシブルディスクドライブや光ディスクドライブ等が含まれる。
【０１６８】
前記構成の装置において、例えば、ＨＤＤ１４の磁気ディスク（記録媒体）に、前記時系列相関抽出装置の処理を実現するためのプログラムを格納しておき、このプログラムをＣＰＵ１５が読み出して実行することにより、前記時系列相関抽出装置が行う処理を実行する。
【０１６９】
しかし、本発明は、このような例に限らず、例えば、ＨＤＤ１４の磁気ディスクに、次のようにしてプログラムを格納し、このプログラムをＣＰＵ１５が実行することで前記処理を行うことも可能である。
【０１７０】
▲１▼：他の装置で作成されたリムーバブルディスクに格納されているプログラム（他の装置で作成したプログラムデータ）を、ＲＤＤ１３により読み取り、ＨＤＤ１４の記録媒体に格納する。
【０１７１】
▲２▼：通信回線を介して他の装置から伝送されたプログラム等のデータを、通信制御部１９を介して受信し、そのデータをＨＤＤ１４の記録媒体（磁気ディスク）に格納する。
【０１７２】
§２：時系列フィルタ部の説明
（１）　：概要
前記時系列フィルタ部４（図１〜図４参照）は、特許文献２の明細書及び図面に記載されており、以下、詳細に説明する。この時系列フィルタ部は、「順序を考慮したパターンを用いた検索装置および方法」と題する発明であり、以下、これを、本発明の「時系列フィルタ部」と呼んで説明する。
【０１７３】
Ａ：順序に基づいてデータを扱うために従来から利用されてきた技術には、関係データベースや、文字列の出現順序に対する正規表現によるパターンマッチングがあり、株価のような時系列データに対しては、専用のアプリケーションが用いられてきた。以下では、従来の技術について、その特徴及び利用分野について述べる。
【０１７４】
Ｂ：関係データベース
大量のデータを格納するために、関係データベースが広く利用されている。関係データベースでは、考案者であるＥ．Ｆ．Ｃｏｄｄによる論文（１９７０年）に明記されているように、データ集合に順序の概念がない。但し、日付型や時間型といったデータ型が用意されていることや、レコードを値にしたがって並び替える（ソーティング）機能が提供されており、順序を持つデータを格納するのに利用される。
【０１７５】
このデータベースでは、データ型として日付を扱うことはできるが、順序の概念がないため、時系列のように順序を意識したデータのパターンを探し出す問い合わせは、ＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ　Ｑｕｅｒｙ　Ｌａｎｇｕａｇｅ　）で全て処理することはできない。
【０１７６】
そこで、データベースと外部プログラムを組み合わせて処理を行っており、順序を考慮したパターンを取り出す毎にプログラムが必要になる。
【０１７７】
Ｃ：正規表現によるパターンマッチング
文字列検索の分野では、文字列が出現する順序に着目して、正規表現によるパターンマッチングが利用されてきた。先ず、文字列検索とパターンマッチングの相違について明確にしておく。文字列検索とは、「文章中からパターンａｂｃを探せ」のように、探索すべきパターンが完全に確定しているものを言う。一方、パターンマッチングとは、不確定のパターンを探す操作のことで、パターン照合とも呼ばれている。パターンマッチングでは、パターンを指定するのに正規表現が用いられる。
【０１７８】
図１１は、文字列データと正規表現ａ（ａ｜ｂ）＊ａのパターンマッチングの例を示している。ここで、（ａ｜ｂ）＊は、ａまたはｂが０回以上繰り返し出現することを意味している。文字列検索とパターンマッチングは、一見似たように見えるが、異なるカテゴリに属する問題で、それぞれに対して別のアルゴリズムを適用しなければならない。
【０１７９】
正規表現によるパターンマッチングを実現するには、有限オートマトン（ｆｉｎｉｔｅ　ａｕｔｏｍａｔｏｎ）を利用する。正規表現をオートマトンに変換するには、２段階のアプローチをとる。まず、正規表現を非決定性有限オートマトン（ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ｆｉｎｉｔｅ　ａｕｔｏｍａｔｏｎ，　ＮＦＡ　）に変換する。正規表現からＮＦＡへの変換は容易である。ＮＦＡ単体でパターンマッチングを行うことも可能であるが、得られたＮＦＡを等価である決定性有限オートマトン（ｄｅｔｅｒｍｉｎｉｓｔｉｃｆｉｎｉｔｅ　ａｕｔｏｍａｔｏｎ，ＤＦＡ　）に変換し、ＤＦＡを使ってパターンマッチングを行う方法が多く用いられる。
【０１８０】
ＤＦＡでは、決定性という言葉が示すように、ある状態において入力が決まれば遷移先が１つだけに定まるが、ＮＦＡでは、非決定性という言葉が示すように、ある状態において入力に対する遷移性が複数存在する場合がある。
【０１８１】
図１２は、正規表現ａ（ａ｜ｂ）＊ａに対応するＮＦＡを示している。このＮＦＡにａａａという文字列を与えた場合を考える。１文字目のａを入力すると、初期状態０から１に遷移する。２文字目もａであるが、状態１には文字ａに対する遷移先として、状態１と状態２の２種類の状態がある。結論から言えば、２文字目のａでは状態１から状態１へと遷移し、３文字目のａでは状態２に遷移するのが正解なのであるが、２文字目のａを読み込んだ時点では、どちらへ進めばよいかわからない。
【０１８２】
この問題を解決するためには、バックトラックを利用し、とりあえずどちらかの状態に遷移して処理を勧め、失敗したらもう１つの状態に遷移するという処理が必要になる。しかし、バックトラックを用いると、後戻りのための処理時間がかかる。
【０１８３】
そこで、正規表現を変換して得られたＮＦＡをそのまま使うのではなく、ＮＦＡをさらにＤＦＡに変換してから、パターンマッチング処理を行う。ＤＦＡの場合には、ＮＦＡと違って、状態と入力が決まれば遷移先が必ず１つだけに決まるので、ＮＦＡのようなバックトラックは必要なく、処理を高速に実行することが可能になる。
【０１８４】
例えば、図１２のＮＦＡは、図１３に示すようなＤＦＡに変換される。もちろん、ＮＦＡをＤＦＡに変換するのに時間がかかるが、大量のデータに対してパターンマッチングを行う場合、バックトラックがないＤＦＡの高速性により、全体としては十分に処理が高速化される。
【０１８５】
ところで、正規表現は、図１４に示すような連結（ｃｏｎｃａｔｅｎａｔｉｏｎ　）、選択（ｕｎｉｏｎ　）、および繰り返し（閉包：ｃｌｏｓｕｒｅ　）の３つの基本操作（演算子）によって、再帰的に定義される。これらの操作の間には、普通の数式と同様に、優先順位があり、最も強く結合するのが繰り返し“＊”であり、次に強く結合するのが連結であり、最後が選択“｜”という順番になる。ただし、文字や記号を括弧で囲むことによって、優先順位を変えることもできる。
【０１８６】
ＰＯＳＩＸ｛Ｐｏｒｔａｂｌｅ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍ　Ｉｎｔｅｒｆａｃｅｆｏｒ　ＵＮＩＸ　（登録商標）｝１００３．２では、Ｂａｓｉｃ　Ｒｅｇｕｌａｒ　Ｅｘｐｒｅｓｓｉｏｎ（ＢＲＥ）　と、Ｅｘｔｅｎｄｅｄ　Ｒｅｇｕｌａｒ　Ｅｘｐｒｅｓｓｉｏｎ（ＥＲＥ）の２種類の正規表現が定められている。ＢＲＥを使用するＵＮＩＸ上のソフトウェア・ユーティリティには、ｅｄ、ｅｘ、ｖｉ、ｍｏｒｅ、ｓｅｄ、ｇｒｅｐ等があり、ＥＲＥを使用するソフトウェア・ユーティリティには、ａｗｋや、−Ｅオプション指定時のｇｒｅｐがある。
【０１８７】
Ｄ：時系列アプリケーション
順序を持つデータに対しては、株価の相場予想や、データマイニングにおけるシーケンシャルパターンのように、専用のアプリケーションを用いて処理が行われる場合がある。専用のアプリケーションを利用すれば、時系列のパターン検索を高速に処理することが可能であるが、専用のアプリケーションは、汎用的なさまざまな問い合わせにおいて必ず利用できるとは限らない。
【０１８８】
Ｅ：課題
ところで、前記の処理には、次のような課題がある。
【０１８９】
▲１▼：文字列における正規表現と、それによるパターンマッチングは、あらゆるクラスの文字列に対する検索方法を提供する一般的なフレームワークである。しかし、順序を持つデータは、以下のＡ、Ｂ、Ｃのように、データの特性が文字列データとは異なるため、正規表現とそのパターンマッチングを適用することができない。
【０１９０】
Ａ：文字列においては、項間隔で隣あった文字しか存在しないが、順序を持つデータの場合には、ある位置に複数のイベントが存在する場合がある。例えば、同じ日に複数回の買い物を行った場合がそれにあたり、「顧客１０００１は、３月２１日に牛乳とパンの２つの商品を購入」といった表現が必要となる。しかし、文字列では、同じ位置に２つの文字が出現することがないので、正規表現では同時に発現するイベントを表現できない。
【０１９１】
Ｂ：文字列では、値と記号（リテラル）とが等しい。つまり、文字列として“Ａ”が与えられた時、“Ａ”は値であり、記号としてのＡでもある。しかし、複数の属性からなるデータでは、「２００円以上のパンを購入した顧客を‘顧客グループＡ’と呼ぶ」というように、複数フィールド（この場合、商品と価格）の条件の組み合わせを１つの記号として扱う必要がある。このような複数フィールドの条件の組み合わせを、正規表現で表すことはできない。
【０１９２】
Ｃ：順序を持ったデータの場合、「パンを購入してから２日以内にチーズを購入」というように、順序に間隔の概念が必要となる。しかし、文字列の正規表現では、間隔を指定することはできない。
【０１９３】
図１５は、順序を持つデータの例として、小売り業売上データを示している。この例では、顧客毎に商品を購入した日付が順序にあたる。３月２１日（０３．２１）に顧客１０００１は、牛乳とパンを同時に購入しているが、同時に出現する事象を正規表現で記述することはできない。また、小売店の売上データでは、休業日にあたる３月２２日のデータは存在しないが、文字列では特定の順序の文字が存在しないという状況はあり得ない。さらに、ある商品を購入して次の来店までの間隔が３日以内であるといったように、順序間にまたがる関係を考慮した記述は、正規表現では困難である。
【０１９４】
以上説明したように、順序を持つレコード群の中から、順序を考慮したパターンを一般的に指定することは、従来の正規表現とオートマトン理論では不可能である。
【０１９５】
また、関係データベースでは、順序関係については限定された形でしかサポートされていない。したがって、順序を持つデータから、指定したパターンを発見しようとする場合、データベースと外部プログラムの組み合わせで処理する必要がある。
【０１９６】
しかし、問い合わせ毎にプログラムを作成する方法では、正規表現によるパターンマッチングのように、指定するパターンを変更するだけでパターンマッチングを実行することはできない。
【０１９７】
更に、株価の予測のように、順序を持ったデータを解析するために、専用のアプリケーションを用いることも考えられる。専用のアプリケーションは、ある目的のためにデータを準備すれば特定の結果を返すので、その目的に限定すれば、高速な処理を行うことは可能である。しかし、専用のアプリケーションでは、専用であるがゆえに、正規表現によるパターンマッチングのように幅広い問題に対処することは困難である。そこで、以下では、データ間の順序関係のための汎用的な表現を用いて、順序に基づくデータのパターンを検索する装置および方法について説明する。
【０１９８】
図１６は、時系列フィルタ部の原理的な説明図である。図１６の検索装置は、指定手段１０１、検索手段１０２、および出力手段１０３を備え、複数の属性からなるレコードの集合１０４からレコードの組み合わせを検索する。
【０１９９】
指定手段１０１は、レコード内の所定属性が特定の値をとることをそれぞれ定義する複数イベントと、属性値の順序に基づいて定義されたそれらのイベントの間の順序関係とを用いて、検索パターン（イベントパターン）１０５を指定する。検索手段１０２は、レコードの集合１０４から、指定された検索パターン１０５に対応するレコードの組み合わせを検索し、出力手段１０３は、検索結果を出力する。
【０２００】
イベントは、レコード内の所定属性が特定の値をとる状態として定義され、複数のイベントの間の順序関係は、それらのイベントに対応するレコードの間において、１つ以上の属性の値の順序関係に基づいて定義される。ユーザは、指定手段１０１を用いて、これらのイベントとイベント間の順序関係により決められる検索パターン１０５指定する。指定手段１０１は、検索パターン１０５を検索手段１０２に渡し、検索手段１０２は、受け取った検索パターン１０５を解釈して、検索パターン１０５に対応するレコードの組み合わせを抽出する。そして、出力手段１０３は、抽出されたレコード等の情報を検索結果として出力する。
【０２０１】
このような検索装置によれば、２つ以上のイベントが同じ順序に存在する場合や、複数のイベントの順序関係が任意の間隔で記述される場合を含めて、様々な検索パターンを容易に指定することが可能となり、順序を考慮した汎用的なデータ検索が実現される。
【０２０２】
Ｆ：検索装置の説明
以下、図面を参照しながら、詳細な装置について説明する。対象とするデータは、図１５に示したような、複数のフィールド（属性）を持つレコードの集合からなるデータである。各レコードは決まった数のフィールドを持ち、あるレコードのみが異なった数のフィールドを持つことはないものとする。更に、データ中には、順序を持ったフィールドが１つ以上含まれているものとする。
【０２０３】
順序を持ったフィールドとは、日付や時刻といった順序関係をあらかじめ持っているフィールドか、顧客ＩＤ（顧客識別子）フィールドのように、データを並べ替えることで順序が生じるものである。また、日付フィールドと時刻フィールドを合わせて１つの順序フィールドと考えることができるように、複数のフィールドを複合して順序を持たせる場合もある。
【０２０４】
このような対象データの中から順序を持つパターンを検索する際に、イベント定義とイベント間定義による汎用的なパターン指定を行い、指定されたパターンを解釈して検索を実行する、汎用的な処理系を用いる。イベント定義とは、１つあるいは複数のフィールドについて指定した条件に、一意に名前を付けたものである。１つのフィールドについて条件を指定する場合は、例えば、「商品としてＰＣを購入した顧客を‘顧客グループＡ’と呼ぶ」というように定義できる。
【０２０５】
また、複数のフィールドについて条件を指定する場合には、例えば、「商品＝ＰＣで価格＝２５万円の商品を購入した顧客を‘顧客グループＡ’と呼ぶ」というように、複数フィールドの条件の組み合わせを１つの記号（リテラル）として扱う。つまり、イベントとは、１つあるいは複数のフィールドについて条件を満たしたレコードに関するラベルであると定義する。さらに、正規表現におけるワイルドカードのように、何でもマッチするような条件を指定することも可能とする。
【０２０６】
図１７は、「商品＝ＰＣで価格＝２５万円の商品を購入した顧客を‘顧客グループＡ’と呼ぶ」で定義されるイベント定義例を示している。既に説明したように、複数フィールドの条件の組み合わせを文字列の正規表現で表すことは不可能である。
【０２０７】
次に、イベント間定義とは、イベント定義を利用して、イベントとイベントの間にまたがる関係を記述したものである。イベント間定義においては、同じ順序に複数のイベントが存在する場合や、順序の間隔が一定でない場合（任意の間隔で順序が記述される場合）も考慮される。
【０２０８】
具体的な例としては、２５万円のＰＣを購入した顧客のイベントを‘Ａ’と呼び、１０万円のＴＶを購入した顧客のイベントを‘Ｂ’と呼ぶことにすると、「‘Ａ’から‘Ｂ’までの間隔が３来店以内」というようなイベント間定義が考えられる。また、「‘Ａ’から‘Ｂ’までの間隔が３日以内（‘Ａ’の日付フィールドと‘Ｂ’の日付フィールドの差が３日以内）」といった定義も考えられる。
【０２０９】
また、順序を持つフィールド以外でも、イベントとイベントにまたがる制約を記述することができる。例えば、「‘Ａ’における価格が‘Ｂ’における価格より大きい」といった定義が可能である。さらに、イベント定義がどのようなパターンにもマッチするワイルドカードで指定されている場合でも、イベント間定義によって条件を指定することが可能である。
【０２１０】
図１８は、イベント間定義の例を示している。この例においては、イベント‘Ａ’とイベント‘Ｂ’の間隔が３日以内であり、イベント‘Ｂ’とイベント‘Ｃ’の間隔が２日以内であり、イベント‘Ａ’とイベント‘Ｃ’の間隔が５日以内であることが定義されている。
【０２１１】
正規表現において、全ての文字にマッチする‘・’を利用してａ・・ｂと表記するのは、あくまでもリテラル‘ａ’の３文字後に‘ｂ’が出現するという意味であり、１つ以上のフィールドについて条件が指定されたイベント定義とは異なる。
【０２１２】
また、任意のイベント間の関係が定義できるということは、検索すべきマッチングパターンがクラフ構造で表現されることを意味する。図１８の例でも、イベント定義１とイベント定義２の間と、イベント定義２とイベント定義３の間と、イベント定義１とイベント定義３の間にそれぞれイベント間定義が存在する。
【０２１３】
本発明で扱われる順序パターンは、このようなグラフ構造を持ち得ることや、イベント定義とイベント間定義の組み合わせによって指定されるという点で、正規表現におけるパターンとは明確に異なる。イベント定義とイベント間定義を用いれば、従来の正規表現では記述が不可能な検索パターンを指定することが可能となる。
【０２１４】
本検索装置は、このようなイベント定義とイベント間定義によって与えられる順序に基づいたパターンが汎用的に指定し、それを解釈して実行する。順序に基づいてパターンを解釈する際には、インタープリタのように実行時に動的に解釈する方法と、コンパイラのように実行前にパターンを計算機で実行可能な命令に置き換えてしまう方法とがある。
【０２１５】
図１９は、本検索装置の基本構成を示している。図１９の検索装置は、検索対象となるデータ１１１と、イベント定義とイベント間定義によって指定された検索パターン１１２と、検索パターン１１２を解釈して実行する検索処理部１１３とからなり、検索処理部１１３は、検索結果１１４を出力する。検索パターン１１２の定義を変えるだけで、様々な種類の検索に対応することができる。
【０２１６】
図２０は、検索処理部１１３による全体処理のフローチャートである。検索処理部１１３は、まず、データ１１１（ステップＳ１）と検索パターン１１２（ステップＳ２）を入力として受け取る。そして、検索パターン１１２を解釈して（ステップＳ３）、指定されたパターンを検索し（ステップＳ４）、検索結果１１４を出力する（ステップＳ５）。以下では、検索パターン１１２をイベントパターンと呼ぶことにする。
【０２１７】
図２１は、図２０のステップＳ４において検索処理部１１３が保持しているデータ構造を示している。検索処理部１１３は、データを指すポインタＰ１と、イベント定義とイベント間定義を指すポインタＰ２を備える。通常の文字列データとは違って、例えば、同じ日に発生したデータは同じ順序を持つ。したがって、ポインタＰ１が指すデータは、１つのレコードとは限らず、複数のレコードである場合もある。
【０２１８】
イベント定義については、先に出現するイベントから順番に並べて記述され、イベント間定義については、１つのイベント間定義に含まれるイベントのうち最も最後のイベントの欄に記述される。
【０２１９】
図２２は、図２０のステップＳ４における検索処理のフローチャートである。検索処理部１１３は、まず、ポインタＰ１に対応するデータを読み込み（ステップＳ１１）、ポインタＰ１が最後に指しているかどうかを調べる（ステップＳ１２）。ポインタＰ１が最後を指していなければ、そのデータがポインタＰ２に対応するイベント定義を満たすかどうか調べる（ステップＳ１３）。そして、そのデータがイベント定義を満たしていなければ、ポインタＰ１に１を加算して（ステップＳ１７）、ステップＳ１１以降の処理を繰り返す。
【０２２０】
データがイベント定義を満たしている場合は、さらに、そのデータがＰ２に対応するイベント間定義を満たしているかどうかを調べる（ステップＳ１４）。データがイベント間定義を満たしていなければ、ステップＳ１７以降の処理を繰り返す。
【０２２１】
データがイベント定義を満たしている場合には、次に、ポインタＰ２が最後を指しているかどうかを調べる（ステップＳ１５）。そして、ポインタＰ２が最後を指していなければ、Ｐ２に１を加算して（ステップＳ１８）、ステップＳ１７以降の処理を繰り返す。
【０２２２】
ポインタＰ２が最後を指していれば、すべてのイベント定義及びイベント間定義を満たすデータの組み合わせが見つかったことになるので、それらのデータを検索結果として登録し（ステップＳ１６）、ステップＳ１７以降の処理を繰り返す。
【０２２３】
そして、ステップＳ１２においてポインタＰ１が最後を指していれば、全てのデータについての検索処理が終了したことになるので、登録された検索結果を出力する。ステップＳ１６において、検索結果を登録する代わりに、直ちに出力することも可能である。また、図２２に示しフローチャートは検索処理の一例に過ぎず、検索処理には任意のパターンマッチング方法を用いることができる。
【０２２４】
次に、図２３から図３６までを参照しながら、検索装置の付加的な機能について説明する。
【０２２５】
検索装置は、多数のファイルに記録された複数の入力データ（ログ）をまとめることにより、検索対象である複数の属性からなる入力データを生成することができる。例えば、関係データベースの結合（ＪＯＩＮ）演算や、外部プログラムを利用することで、複数のファイル（データ）から検索対象データを生成する。
【０２２６】
図２３に示すテーブルと図２４に示すテーブルから検索対象データを生成する場合、検索装置は、これら２つのテーブルに対して図２５のようなＳＱＬ文を適用し、結合演算処理（Ｊｏｉｎ　Ｏｐｅｒａｔｉｏｎ）を実行する。これにより、図１５に示したデータが生成される。この場合、２つのテーブルには、それぞれ異なるフィールドが含まれているが、これらを結合することにより、両方のテーブルのフィールドを含むテーブルが生成される。
【０２２７】
また、複数の属性からなるレコードの集合に関して、各属性を整数化等の処理によって圧縮することで、検索対象データを生成することも可能である。例えば、図１５における顧客ＩＤを４バイト整数化により整数化した後、２ビットに圧縮すると、次のようになる。
【０２２８】
整数　　　　　　　　　２ビット
“１０００１”　　　−　　　００
“１０００２”　　　−　　　０１
“１０００３”　　　−　　　１０
圧縮された顧客ＩＤを用いれば、図１５のデータは図２６のように書き換えられる。圧縮されたデータは、出力時に元の文字列に戻して表示すればよいので、内部的には２ビットのままで処理することが可能である。これにより、処理に必要となるメモリ量を削減することができ、処理が高速化される。
【０２２９】
また、検索対象である複数の属性からなるレコードの集合に関して、発見すべきパターンで不要なレコードを使わないことで、必要となるメモリ量を削減し、入出力のコストを減らすことができる。つまり、発見すべきパターンとして必要のないレコードについては、始めから処理の対象にしない。例えば、次のようなイベントパターンが定義されているとする。
【０２３０】
イベント定義
イベント１：商品＝牛乳
イベント２：商品＝パン
イベント間定義
イベント１．日付＝イベント２．日付
この例では、同じ日に牛乳とパンが購入されたイベントパターンが指定されており、牛乳とパン以外の商品についてのデータは必要がないことがわかる。したがって、データをファイルから読み込む際に、商品のフィールドが牛乳とパン以外の必要のないレコードについては、メモリに読み込まないようにする。
【０２３１】
図２７は、このようなレコードの削減処理を示している。ファイル１２１に記録されたデータは、一旦読み込みバッファ１２２に入力され、データから不要なレコードが削除される。そして、必要なレコードのみが、検索対象データとしてメモリ１２３上に読み込まれ、検索処理が行われる。これにより、メモリ量を削減することができるとともに、処理の高速化も期待できる。
【０２３２】
ところで、商品に大分類と小分類の２種類のクラス階層がある場合のように、データが階層構造を持っている場合、階層に基づいた値の書き換えを行うことで、階層を意識した処理が可能となる。以下に、商品の階層に基づく値の書き換えの例を示す。
【０２３３】
大分類　大分類コード　小分類　小分類コード　大分類コード＋小分類コード
生鮮　１００００　　　キュウリ　　　１　　　　　　　１０００１
生鮮　１００００　　　白菜　　　　２　　　　　　　１０００２
魚介　２００００　　　アジ　　　　１　　　　　　　２０００１
魚介　２００００　　　カレイ　　　２　　　　　　　２０００２
精肉　３００００　　　牛　　　　　１　　　　　　　３０００１
この例では、大分類に５桁コード（１００００，２００００，・・・）を割り当て、小分類に４桁コード（０００１〜９９９９）を割り当て、大分類コードと小分類コードを足すことで、全体として商品を一意に識別可能なコードを割り当てる。このようにして値を書き換えれば、処理の途中で、コードに基づいてそれがどの分類項目に対応するかが容易に判定でき、ある特定の分類項目のみを検索対象とすることが容易になる。
【０２３４】
例えば、イベント定義で、２００００＜＝商品コード＜＝２９９９９と指定すれば、それは魚介類という分類を指定したことになる。また、イベント定義で、商品コード＝１０００２のように、大分類と小分類の両方で指定すれば、特定の商品を指定することが可能である。
【０２３５】
次に、検索処理におけるパターンマッチングの指定方法について説明する。正規表現におけるパターンマッチングでは、与えられた文字列パターンにマッチする最も長い文字列を返す「最長マッチ」が基本である。しかし、ｐｅｒｌ（Ｐｒａｃｔｉｃａｌ　Ｅｘｔｒａｃｔｉｏｎ　ａｎｄ　Ｒｅｐｏｒｔ　　Ｌａｎｇｕａｇｅ　）処理系では、与えられた文字パターンにマッチする最も短い文字列を返す「最短マッチ」を指定することができる。
【０２３６】
本例の順序に基づいたパターンマッチングについては、正規表現で用いられるマッチング指定に加えて、さらに別のマッチング指定が可能である。これらのマッチング指定について、図２８の検索対象データを用いて説明する。説明のため、図２８のデータには、各レコードを一意に識別するためのレコード番号が付加されている。イベントパターンとしては、以下のようなパターンを用いることにする。
【０２３７】
イベント定義
イベント１：商品＝牛乳
イベント２：商品＝パン
イベント間定義
イベント１．日付＜イベント２．日付
ここで、“イベント１．日付＜イベント２．日付”という条件は、イベント１の日付がイベント２の日付より前であることを示している。まず、与えられたイベントパターンにマッチする最初のパターンを返す「最初マッチ」においては、レコード番号１と４のレコードが抽出される。
【０２３８】
このレコードは、出現する最初の牛乳レコードと、そのレコードより日付が後のレコードの中で最初に出現したパンのレコードである。この場合、抽出されたパターンは、レコード番号の組み合わせを用いて、（１，４）のように表される。
【０２３９】
次に、与えられたイベントパターンにマッチするパターンの中で間隔が最短のものを返す「最短マッチ」においても、レコード番号（１，４）が抽出される。図２８のデータにおいては、イベントパターンにマッチするレコードの組み合わせのうち、レコード１とレコード４の間で間隔が最も短くなるからである。
【０２４０】
また、データの先頭から「最短マッチ」を繰り返すことによって、イベントパターンにマッチする複数のレコードの組み合わせを抽出することも可能である。この場合、検索対象データから、１回の最短マッチによりイベントパターンにマッチした部分を取り除き、残りのデータを新たに検索対象として最短マッチに適用する処理が繰り返される。
【０２４１】
次に、与えられたイベントパターンにマッチするパターンの中で間隔が最長のものを返す「最長マッチ」では、レコード番号（１，７）が抽出される。図２８のデータにおいては、イベントパターンにマッチするレコードの組み合わせのうち、レコード１とレコード７の間で間隔が最も長くなるからである。また、与えられたイベントパターンにマッチする全てのパターンを返す「全部マッチ」では、レコード番号（１，４）、（１，７）、および（３，７）という３つの組み合わせが抽出される。
【０２４２】
さらに、データの先頭からの順方向のマッチングだけでなく、データの末尾からの逆方向のマッチングを指定することもできる。このようにマッチング指定を説明するため、上述のイベントパターンのイベント間定義を変更した、以下のようにイベントパターンを用いることにする。
【０２４３】
イベント定義
イベント１：商品＝牛乳
イベント２：商品＝パン
イベント間定義
イベント１．日付＞イベント２．日付
まず、「データの末尾から逆向きの最初マッチ」では、与えられたイベントパターンに逆向きにマッチする最初のパターンが返される。図２８のデータでは、レコード番号（６，４）がこれに該当する。
【０２４４】
次に、「データの末尾から逆向きの最短マッチ」では、与えられたイベントパターンに逆向きにマッチするパターンの中で間隔が最短のものが返される。図２８のデータでは、レコード番号（３，２）がこれに該当する。同様に、「データの末尾から逆向きの最長マッチ」では、与えられたイベントパターンに逆向きにマッチするパターンの中で間隔が最長のものが返される。図２８のデータでは、レコード番号（６，２）がこれに該当する。
【０２４５】
このように、イベントパターンを用いれば、様々なマッチング指定が可能であり、これらの指定方法を目的に合わせて使い分けることができる。
【０２４６】
検索装置がグラフィック・ユーザ・インタフェース（ＧＵＩ）を備えている場合、ユーザは、ＧＵＩを用いてイベントパターンを指定することができる。この場合、イベント定義とイベント間定義の２つをそれぞれＧＵＩで指定すればよい。
【０２４７】
図２９は、このようなＧＵＩの画面例を示している。イベント定義のボックス１３１にはイベント名が入力され、ボックス１３２にはイベントの条件が入力される。そして、ユーザがＯＫボタンをクリックすると、イベント定義の指定が完了する。ここでは、商品としてＰＣを購入したイベントが‘Ａ’と定義されている。同様にして、商品としてＴＶを購入したイベントは‘Ｂ’と定義されている。
【０２４８】
また、イベント間定義のボックス１３４および１３６には、定義されたイベント名が入力され、ボックス１３５には、ボックス１３４および１３６に入力されたイベント間の関係が入力される。そして、ユーザがＯＫボタン１３７をクリックすると、イベント間定義の指定が完了する。ここでは、イベントＡとイベントＢの間の関係について、イベントＡの後でイベントＢが起こるという条件が指定されている。これ以外にも、例えば、２つのイベントの間隔が所定日数以内であるといった指定が可能である。
【０２４９】
また、イベントパターンは、正規表現の拡張によって指定することもできる。正規表現では、複数イベントの同時発生とイベント間の間隔の記述がサポートされていないが、これらの記述を追加することによって、順序を考慮したイベントパターンが指定できる。例えば、同時発生を‘＝’で表現するとすれば、イベントＡ：“商品＝ＰＣ，価格＝１０万円”とイベントＢ：“商品＝ＴＶ，価格＝５万円”が同時に発生することを、以下のように表現することができる。
【０２５０】
イベントパターン
イベント定義
イベントＡ：商品＝ＰＣ，価格＝１０万円
イベントＢ：商品＝ＴＶ，価格＝５万円
イベント間定義
イベントＡ．日付＝イベントＢ．日付
また、イベントＡとイベントＢが同時に発生した後で、イベントＣ：“商品＝ＶＴＲ，価格＝３万円”が発生するパターンについては、以下のように記述することができる。
【０２５１】
イベントパターン
イベント定義
イベントＡ：商品＝ＰＣ，価格＝１０万円
イベントＢ：商品＝ＴＶ，価格＝５万円
イベントＣ：商品＝ＶＴＲ，価格＝３万円
イベント間定義
イベントＡ．日付＝イベントＢ．日付＜イベントＣ．日付
このように、同時発生と間隔の記述を導入することで、正規表現では表すことのできないイベントパターンを容易に指定することができる。
【０２５２】
前述のように、検索処理部が与えられたイベントパターンを解釈して処理を行うとき、インタープリタのように動的に解釈する方法と、コンパイラのように、パターンを計算機で実行可能な命令に置き換えてしまう方法とがある。検索処理部は、与えられたデータの中からイベントパターンにマッチするパターンを発見すると、発見したパターンについてあらかじめ決められた情報を出力する。例えば、図１５のデータについて、以下のような問い合わせを行った場合を説明する。
【０２５３】
イベントパターン
イベント定義
イベントＡ：商品＝牛乳
イベントＢ：商品＝パン
イベント間定義
イベントＡ．日付＝イベントＢ．日付
検索装置がパターンを発見する度に、発見されたパターンを構成するレコード群の情報をそのまま出力する場合、以下の２つのレコードの情報が出力される。
【０２５４】
１０００１　０３／２１　牛乳　１８９　（イベントＡに対応するレコード）
１０００１　０３／２１　パン　３００　（イベントＢに対応するレコード）
また、発見されたパターンの出力フォーマットをユーザが指定可能にすることもできる。この場合、発見されたパターンを構成するレコード群の情報が、指定されたフォーマットにコンパイルされて出力される。例えば、上記の問い合わせにおいて、出力の形式を、
イベントＡ．商品，　イベントＢ．商品
と指定すれば、
牛乳，パン
のような検索結果が出力される。さらに、“イベントＢ．日付−イベントＡ．日付”のように、特定のフィールドの値を用いた演算を指定することも可能である。この場合、発見されたパターンに含まれるレコードの指定されたフィールドの値に関して、指定された演算の結果が出力される。
【０２５５】
また、パターンをすべて発見した後に、レコード群の集約演算（ａｇｇｒｅｇａｔｅ　ｆｕｎｃｔｉｏｎ）を実行することも可能である。集約演算としては、最小値（ＭＩＮ）、最大値（ＭＡＸ）、平均（ＡＶＧ）、総和（ＳＵＭ）といった一般的な関数が用いられる。これらの集約演算を処理する際には、１つ１つのパターンを発見したら、それらをバッファに保存しておき、処理の区切りがついたところで、保存されたパターンすべてを対象として演算を実行する。例えば、上記の問い合わせに対して、ユーザは、ＡＶＧ（イベントＢ．日付−イベントＡ．日付）のような集約演算を指定することができる。
【０２５６】
イベントパターンにマッチするパターンが見つからない場合には、なんらかの形でユーザにその旨を通知する必要がある。例えば、マッチするパターンがないことを示すレコードをあらかじめ用意しておき、それを用いてメッセージを画面上に表示することで、ユーザにこれを通知することができる。図１５のデータの場合、以下の問い合わせを行うと、マッチするパターンは存在しない。
【０２５７】
イベントパターン
イベント定義
イベントＡ：商品＝牛乳
イベントＢ：商品＝パン
イベント間定義
イベントＡ．日付＝イベントＢ．日付
複数のフィールドからなるレコードの集合がデータとして与えられた際に、レコードのグループバイ（グループ化）を行って、処理を高速化することもできる。このとき、どのフィールドでグループ化し、各グループのレコード群をどのフィールドで整列（ソート）するかを指定して、あらかじめレコードを並べ替えておく。グループ化に用いるフィールドとしては、複数のフィールドを指定することができる。
【０２５８】
例えば、図３０のようなデータを検索対象として、顧客ＩＤフィールドでグループ化し、各グループのレコードを購入日で整列するものとする。この場合、グループ化と整列により、検索対象データは図３１のように並べ替えられる。顧客ＩＤが１１０００１００１の顧客は、２００１／０１／１３に１回目の来店を行い、商品ＡとＮの２点を購入した。また、同じ顧客が２００１／０１／２８に２回目の来店を行い、別の商品Ｂを購入している。こうして、並べ替えられたデータを対象として、イベントパターンが指定される。
【０２５９】
イベントパターンの定義とは、前述したように、あるフィールドがどのような値を取るかを１つあるいは複数のフィールドについて定義し、それらの条件全体に１つの名前を付けたものである。また、イベント間定義とは、複数のイベントに跨がる制約のことである。
【０２６０】
図３１のデータについて、図３２に示すように、商品のフィールドが“Ａ”であるレコードをＥｖｅｎｔ１と定義し、商品のフィールドが“Ｂ”であるレコードをＥｖｅｎｔ２と定義したとする。さらに、Ｅｖｅｎｔ１とＥｖｅｎｔ２についてＥｖｅｎｔ１とＥｖｅｎｔ２が発生した日（購入日）の間隔が３０日以内であり、Ｅｖｅｎｔ１とＥｖｅｎｔ２の価格が等しいと指定すると、図３３に示すようなイベントパターンが得られる。
【０２６１】
この例では、データがグループ化して整列されているので、検索処理部は、各グループについて整列されたデータを順番に取り出すだけで、マッチングを行うことができる。もし、グループ化と整列が行われておらず、データがメモリ上に乗り切らない場合には、何度もデータを読み込む必要が生じるため、処理の効率が悪くなる。したがって、グループ化と整列による高速化のメリットは明らかである。
【０２６２】
上述の例では、データをグループ化して、各グループ内で整列を行っているが、検索対象データ全体を１つのグループと見なした場合も、同様にして、データを順序に従って整列することで、処理を高速化できる。図３４は、ある店舗の売り上げデータを日付順に整列した例を示している。このようにデータ全体を日付順に整列することで、ｍ個のデータ項目からｎ個のイベントを検索する処理が、Ｏ（ｍｎ）のオーダからＯ（ｍ＋ｎ）のオーダに効率化される。
【０２６３】
また、インデクスを用いれば、データのグループ化と整列を行うことなく、同等の高速化を達成することができる。この方法では、レコードの集合は、グループ軸と順序軸でインデクス付けして処理され、レコードへのアクセスをグループ毎に順番に行うことができる。
【０２６４】
図３５は、このようなインデクスによるデータアクセスを示している。この例では、グループ情報保持部１４１と複数のインデクス１４２を介して、データ１４３がアクセスされる。グループ情報保持部１４１は、複数のグループに対応する複数の顧客識別子（ＣＩＤ１〜ＣＩＤ４）と、各顧客識別子に対応するインデクス１４２へのポインタを保持している。また、各インデクス１４２は、複数の日付データと各日付データに対応するレコードへのポインタを保持している。検索処理部は、グループ情報保持部１４１とインデクス１４２を用いることで、グループ毎に日付順にレコードにアクセスすることができる。
【０２６５】
また、データ全体を１つのグループとみなした場合でも、インデクスを利用すれば、整列を行うことなく、同等の高速化を達成することができる。この場合、図３５のグループ情報保持部１４１が不要となるため、図３６のような構成が用いられる。検索処理部は、インデクス１４２を用いることで、日付順にレコードにアクセスすることができる。
【０２６６】
次に、図３７から図４２までを参照しながら、検索処理の具体例として、例１、例２、および例３について説明する。
【０２６７】
図３７は、検索対象となる売上データを示している。図３７において、各レコードは、ＲＩＤ（レコード識別子）、顧客ＩＤ、購入日、商品、および価格の５つのフィールドからなる。データは、顧客ＩＤフィールドでグループ化され、さらに、グループ内でのレコードの順序は、購入日フィールドに従って並び替えられているものとする。
【０２６８】
図３７では、スペースの都合上、顧客ＩＤが１１０００１００１のグループに関するレコードのみが示されている。また、以下では、主として、このグループに関する処理についてのみ説明するが、実際には、他の顧客ＩＤのグループについても同様の処理が行われる。
【０２６９】
（例１）
以下のように指定されるイベントパターンを考える。
【０２７０】
イベントパターン
イベント定義
Ｅｖｅｎｔ１：商品＝Ａ
Ｅｖｅｎｔ２：価格＜＝８３８
イベント間定義
Ｅｖｅｎｔ２：Ｅｖｅｎｔ１から３日以内
（Ｅｖｅｎｔ２．購入日＜＝Ｅｖｅｎｔ１．購入日＋３日）
このように問い合わせが与えられると、検索処理部は、問い合わせを解釈して図３８に示すようなパターン構造（問い合わせパターン）を内部的に生成する。パターンマッチングの実効には、様々な実現方法が考えられるが、図２１に示　たポインタＰ２を利用することが可能である。処理の開始には、このポインタが問い合わせパターンマッチングの先頭を指すように、初期化しておく。
【０２７１】
パターンマッチングは、グループ毎に行われる。検索処理部は、各グループについて、レコードを先頭から順番に取り出し、あらかじめ解釈しておいたイベント定義にマッチするかどうかを調べていく。レコードがイベント定義にマッチすれば、さらに、レコードがイベント間定義にマッチするかどうかをしらべる。レコードがイベント間定義にマッチすれば、ポインタＰ２を１つ進める。
【０２７２】
図３８の問い合わせパターンでは、図３７の先頭のレコードＲ１が、ポインタＰ２が指しているＥｖｅｎｔ１のイベント定義にマッチする。そこで、次に、イベント間定義の条件が満たされるかどうかがチェックされる。ところが、Ｅｖｅｎｔ１についてはイベント間定義が定義されていないため、レコードＲ１はイベント定義がマッチしただけで、Ｅｖｅｎｔ１とマッチしたことになる。したがって、図３９に示すように、ポインタＰ２はＥｖｅｎｔ２を指すように変更される。　次に、レコードＲ２が読み込まれ、レコードＲ２がＥｖｅｎｔ２のイベント定義である“価格＜＝８３８”を満たすかどうかがチェックされる。しかし、Ｒ２の価格は１８００円で、Ｅｖｅｎｔ２のイベント定義を満たさないので、次のレコードＲ３の処理に移る。Ｒ３の価格は８３８円なので、Ｅｖｅｎｔ２のイベント定義についての条件が満たされる。そこで、Ｒ３がＥｖｅｎｔ２のイベント間定義を満たすかどうかがチェックされる。
【０２７３】
この場合、イベント間定義は、Ｅｖｅｎｔ２すなわちＲ３が生起したのがＥｖｅｎｔ１から３日以内であるという条件を表す。Ｒ３とＲ１の間隔は１５日であるので、イベント間定義の条件を満たしていない。また、レコードは購入日の早い順に並んでいるため、Ｒ３以降のレコードについては、Ｅｖｅｎｔ１を満たしているレコードＲ１との間隔が１５日以上になることがわかる。したがって、現時点でＥｖｅｎｔ２のイベント間定義を満たすレコードが存在しないことがわかるので、このグループの処理は中止される。
【０２７４】
このようにして、各グループのデータについてマッチング処理が行われ、問い合わせパターンのすべての条件が満たされた場合に、マッチングが成功する。上述した例では、顧客ＩＤが１１０００１００１のグループでは、問い合わせパターンにマッチするパターンがデータ中に存在しない。そこで、「指定されたパターンは存在しない」という結果が出力される。
【０２７５】
（例２）
以下のように指定されるイベントパターンを考える。マッチング方法としては、最初マッチと全部マッチの２通りを指定するものとする。
【０２７６】
イベントパターン
イベント定義
Ｅｖｅｎｔ１：商品＝Ａ
Ｅｖｅｎｔ２：価格＜＝８３８
イベント間定義
Ｅｖｅｎｔ２：Ｅｖｅｎｔ１から３来店以内
（Ｅｖｅｎｔ２．順序＜＝Ｅｖｅｎｔ１．順序＋３）
この例のイベント定義は、例１のものと同じである。しかし、イベント間定義としては、例１で用いた制約に代わって、Ｅｖｅｎｔ２がＥｖｅｎｔ１から３来店以内であるという制約が用いられる。この場合、各レコードには、購入日フィールドの順番に従って、１から始まる数字が順序番号として付加され、図３７の検索対象データは、図４０に示すような内容形式に変換される。
【０２７７】
図４０において、レコードＲ１とＲ２には、同じ順序１が割り当てられている。この順序は、顧客ＩＤが１１０００１００１の顧客が最初に来店した日を意味している。同様に、レコードＲ３とＲ４に順序２が割り当てられており、２回目の来店を意味している。以下、レコードＲ５、Ｒ６、Ｒ７には、それぞれ順序３、４、５が割り当てられており、それぞれ３回目、４回目、５回目の来店を意味している。なお、ここで示した順序は論理的な概念であり、図４０のような順序フィールドを物理的に設けるかどうかは、システムの実装に依存する。
【０２７８】
検索時には、例１と同様に、問い合わせを解釈して、図４１に示すような問い合わせパターンが内部的に生成される。まず、例１と同様に、最初のレコードＲ１がＥｖｅｎｔ１のイベント定義にマッチし、ポインタＰ２は、Ｅｖｅｎｔ２を指すように変更される。
【０２７９】
次に、レコードＲ２が読み込まれるが、Ｒ２の価格は８３８円より高価であるため、次のレコードＲ３が、Ｅｖｅｎｔ２のイベント定義を満たすがどうかがチェックされる。Ｒ３の価格はＥｖｅｎｔ２のイベント定義を満たしているので、次に、Ｒ３がＥｖｅｎｔ２のイベント間定義を満たすかどうかがチェックされる。　この例では、イベント間定義は、Ｅｖｅｎｔ２が正起したのがＥｖｅｎｔ１から３来店以内であるという条件を表す。言い換えれば、Ｅｖｅｎｔ２の順序は、Ｅｖｅｎｔ１すなわち、Ｒ１の順序である３を足して得られる４以下であるという条件である。Ｒ３の順序は４以下の２であり、Ｒ１の次の来店に対応するので、イベント間定義の制約を満たしている。
【０２８０】
Ｒ３まで検索した時点で、Ｅｖｅｎｔ１とＥｖｅｎｔ２からなるパターン指定を満たしているので、マッチした最初のパターンとして（Ｒ１，Ｒ３）が出力される。次に、Ｒ３と同じ来店日のレコードであるＲ４についても、Ｅｖｅｎｔ１をＲ１とした場合に、Ｅｖｅｎｔ２の条件を満たしているかどうかがチェックされる。その結果、Ｒ４についても、Ｅｖｅｎｔ２のイベント定義とイベント間定義の双方が満たされていることがわかり、パターン（Ｒ１，Ｒ４）が出力される。
【０２８１】
２つのパターン（Ｒ１，Ｒ３）と（Ｒ１，Ｒ４）は、まったく同じ来店日で問い合わせパターンを満たすものであり、どちらかが先であるとは言えない。このように、同じ位置（日付や時刻）に複数のデータが存在する場合には、従来の正規表現のデータと異なり、答えも複数存在する場合がある。
【０２８２】
次のレコードＲ５は、Ｒ３、Ｒ４と同じ来店日ではないので、最初マッチが指定された場合には、ここで処理が中止される。これに対して、全部マッチが指定された場合には、Ｒ５以降のレコードの処理が同様に続けられる。その結果、（Ｒ１，Ｒ３）、（Ｒ１，Ｒ４）に加えて、（Ｒ１，Ｒ６）も検索結果のパターンとして出力される。Ｒ６の価格は５８１円で８３８円より低く、また順序は４であるため、（Ｒ１，Ｒ６）のパターンの間隔は３来店となる。したがって、（Ｒ１，Ｒ６）は与えられたパターン指定を満たしている。
【０２８３】
検索結果を（Ｅｖｅｎｔ１．ＲＩＤ，Ｅｖｅｎｔ２．ＲＩＤ）のように表すことにすると、最初マッチ及び全部マッチの場合の出力は、それぞれ以下のようになる。
【０２８４】
最初マッチ：（Ｒ１，Ｒ３）、（Ｒ１，Ｒ４）
全部マッチ：（Ｒ１，Ｒ３）、（Ｒ１，Ｒ４）、（Ｒ１，Ｒ６）
（例３）
以下のように指定されるイベントパターンを考える。マッチング方法としては、最初マッチと全部マッチの２通りを指定するものとする。
【０２８５】
2004110327.tif 000004
この例のイベント定義は、例１および例２のものとは異なり、Ｅｖｅｎｔ２はワイルドカードとして何にでもマッチできると定義されている。イベント間定義において、例２で用いたＥｖｅｎｔ１とＥｖｅｎｔ２が３来店以内という制約に加えて、Ｅｖｅｎｔ２の価格がＥｖｅｎｔ１の価格と同じかそれより低いという制約が与えられている。例２の場合と同様に、各レコードには、購入日フィールドの順番に従って、１から始まる数字が順序番号として付加され、図４０の内部形式が検索対象データとして用いられる。
【０２８６】
検索時には、例１および例２と同様に、問い合わせを解釈して、図４２に示すような問い合わせパターンが内部的に生成される。まず、最初のレコードＲ１が、Ｅｖｅｎｔ１のイベント定義にマッチし、ポインタＰ２は、Ｅｖｅｎｔ２を指すように変更される。
【０２８７】
次に、レコードＲ２が読み込まれるが、Ｅｖｅｎｔ２のイベント定義は、ワイルドカードであり、何にでもマッチする。そこで、Ｅｖｅｎｔ２のイベント間定義が満たされるかどうかがチェックされる。イベント間定義は、Ｅｖｅｎｔ２が生起したのがＥｖｅｎｔ１から３来店以内であるという条件と、価格についての条件である。Ｒ２は、Ｅｖｅｎｔ１から３来店以内という１番目の条件は満たしているが、Ｒ２の価格はＲ１の価格より高価であるため２番目の条件が成立しない。
【０２８８】
次に、レコードＲ３が読み込まれる。Ｒ３についても、Ｅｖｅｎｔ２のイベント定義は無条件に満たしている。そこで、Ｒ３がＥｖｅｎｔ２のイベント間定義を満たしているかどうかがチェックされる。Ｒ３の順序は４以下の２であり、Ｒ１の次の来店である。また、Ｒ３の価格８３８円はＥｖｅｎｔ１の価格より低い。したがって、２つの条件の両方を満たしているので、イベント間定義の制約は満たされる。
【０２８９】
Ｒ３まで検索した時点で、Ｅｖｅｎｔ１とＥｖｅｎｔ２からなるパターン指定を満たしているので、マッチした最初のパターンとして（Ｒ１，Ｒ３）が出力される。次に、レコードＲ４についても、Ｅｖｅｎｔ２の条件を満たしているかどうかがチェックされ、イベント定義とイベント間定義の双方が満たされていることがわかるので、パターン（Ｒ１，Ｒ４）が出力される。
【０２９０】
次のレコードＲ５は、Ｒ３。Ｒ４と同じ来店日ではないので、最初マッチが指定された場合には、ここで処理が中止される。これに対して、全部マッチが指定された場合には、Ｒ５以降のレコードの処理が同様に続けられる。その結果、（Ｒ１，Ｒ３）、（Ｒ１，Ｒ４）に加えて、（Ｒ１，Ｒ６）も検索結果のパターンとして出力される。Ｒ６の順序は４であるため、（Ｒ１，Ｒ６）のパターンの間隔は３来店となる。さらに、Ｒ６の価格は５８１円でＲ１の価格８３８円より低いので、（Ｒ１，Ｒ６）は与えられたパターン指定を満たしている。こうして、最初マッチおよび全部マッチの場合の出力は、それぞれ、以下のようになる。　最初マッチ：（Ｒ１，Ｒ３），（Ｒ１，Ｒ４）
全部マッチ：（Ｒ１，Ｒ３），（Ｒ１，Ｒ４），（Ｒ１，Ｒ６）
以上説明した３つの例のイベントパターンでは、簡単のため、Ｅｖｅｎｔ１とＥｖｅｎｔ２の２つのイベントのみが用いられている。また、イベント定義とイベント間定義としては、１つあるいは２つの条件のみが用いられている。しかし、実際には、イベントパターンをより多くの数のイベントによって指定することが可能であり、イベント定義およびイベント間定義においても、より多くの条件を指定することが可能である。
【０２９１】
以上の検索装置及び検索方法によれば、データ間の順序を考慮したパターンを容易に指定して、指定されたパターンを検索することが可能になる。また、パターンの定義を変えるだけで様々な種類の検索に対応することができる。
【０２９２】
（２）　：時系列フィルタ部の構成の説明
前記時系列フィルタ部は次のように構成されている。
【０２９３】
Ａ：複数の属性からなるレコードの集合からレコードの組み合わせを検索する装置であって、レコード内の所定属性が特定の値をとることでそれぞれ定義する複数のイベントと、属性値の順序に基づいて定義された該複数のイベントの間の順序関係とを用いて、検索パターンを指定する指定手段と、前記レコードの集合から、指定された検索パターンに対応するレコードの組み合わせを検索する検索手段と、検索結果を出力する出力手段とを備えていることを特徴とする検索装置（本発明の時系列フィルタ部４に相当）。
【０２９４】
Ｂ：前記Ａの検索装置において、前記指定手段は、２つ以上のイベントが同じ順序に存在するような検索パターンを指定することを特徴とした検索装置（本発明の時系列フィルタ部４に相当）。
【０２９５】
Ｃ：前記Ａの検索装置において、前記指定手段は、前記複数のイベントの順序関係を任意の間隔で記述した検索パターンを指定することを特徴とする検索装置（本発明の時系列フィルタ部４に相当）。
【０２９６】
Ｄ：前記Ａの検索装置において、前記複数の属性のうち少なくとも１つの値のデータを圧縮することで、前記レコードの集合のデータを圧縮する手段をさらに備え、前記検索手段は、圧縮されたデータを検索することを特徴とする検索装置（本発明の時系列フィルタ部４に相当）。
【０２９７】
Ｅ：前記Ａの検索装置において、前記指定手段は、前記検索パターンとレコードの組み合わせの中でイベント間の間隔が最長の組み合わせを返す最長マッチと、該検索パターンにマッチスルイベントの組み合わせの中でイベント間の間隔が最短の組み合わせを返す最短マッチと、該最短マッチの繰り返しと、該検索パターンにマッチする全てのイベントの組み合わせを返す全部マッチと、該検索パターンに逆向きにマッチするイベントの組み合わせの中で間隔が最長の組み合わせを返す逆向きの最長マッチと、該検索パターンに逆向きにマッチするイベントの組み合わせの中で間隔が最短の組み合わせを返す逆向きのマッチのうちの１つの方法を指定し、前記検索手段は、指定された方法でパターンマッチングを行うことを特徴とする検索装置。
【０２９８】
Ｆ：前記Ａの検索装置において、前記出力手段は、前記検索パターンに対応するレコードの組み合わせに関する集約演算を行って、演算結果を出力することを特徴とする検索装置。
【０２９９】
Ｇ：前記Ａの検索装置において、前記指定手段は、レコードの整列に用いる属性を指定し、前記検索手段は、指定された属性の値に基づいて前記レコードの集合を整列し、整列したレコードの集合を検索することを特徴とする検索装置。
【０３００】
Ｈ：前記Ａの検索装置において、前記レコードの集合を前記属性値の順序に従ってアクセスするためのインデクス手段を更に備えることを特徴とする検索装置。
前記の説明に対し、次の構成を付記する。
【０３０１】
（付記１）
時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては該シーケンスにおける順序を維持した形式で、与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めて時系列相関ルールを抽出する時系列相関抽出装置において、
入力データをフィルタリングして必要なデータを残す時系列フィルタ部と、入力データから時系列相関ルールを抽出する時系列相関エンジン部とを備えると共に、
前記時系列フィルタ部は、
複数の属性からなるレコードの集合からレコードの組み合わせを検索する際、レコード内の所定属性が特定の値をとることをそれぞれ定義する複数のイベントと、
その属性値の順序に基づいて定義された該複数のイベントの間の順序関係とを用いて、検索パターンを指定する指定手段と、
前記レコードの集合から、指定された検索パターンに対応するレコードの組み合わせを検索する検索手段と、
検索結果を出力する出力手段とを備えていることを特徴とする時系列相関抽出装置。
【０３０２】
（付記２）
前記時系列相関エンジン部の前段に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする（付記１）記載の時系列相関抽出装置。
【０３０３】
（付記３）
前記時系列相関エンジン部の後段に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする（付記１）記載の時系列相関抽出装置。
【０３０４】
（付記４）
前記時系列相関エンジンの前段と後段の両方に前記時系列フィルタ部を配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする（付記１）記載の時系列相関抽出装置。
【０３０５】
（付記５）
前記時系列フィルタ部を前記時系列相関エンジン部の外部に配置することで、時系列相関ルールを抽出する機能を備えていることを特徴とする（付記１）乃至（付記４）の何れかに記載の時系列相関抽出装置。
【０３０６】
（付記６）
前記時系列相関エンジンの前段と後段の両方に前記時系列フィルタ部を配置すると共に、
前段の時系列フィルタ部と時系列相関エンジン部を１つのプログラムで構成し、後段の時系列フィルタ部を別の１つのプログラムで構成したことを特徴とする（付記１）記載の時系列相関抽出装置。
【０３０７】
（付記７）
前記時系列相関エンジンの前段と後段の両方に前記時系列フィルタ部を配置すると共に、
前段の時系列フィルタ部を１つのプログラムで構成し、時系列相関エンジン部と後段の時系列フィルタ部を別の１つのプログラムで構成したことを特徴とする（付記１）記載の時系列相関抽出装置。
【０３０８】
（付記８）
前記時系列相関エンジンの前段と後段の両方に前記時系列フィルタ部を配置すると共に、
前段の時系列フィルタ部と、時系列相関エンジン部と、後段の時系列フィルタ部を、それぞれ別々の１つのプログラムで構成したことを特徴とする（付記１）記載の時系列相関抽出装置。
【０３０９】
【発明の効果】以上説明したように、本発明によれば次のような効果がある。
【０３１０】
（１）　：請求項１では、時系列相関抽出装置は、時間的に連続するトランザクションに含まれるアイテムのシーケンスデータから、ｉ＝２個以上のアイテムの組み合わせに対しては該シーケンスにおける順序を維持した形式で、前記与えられた条件に適合するアイテム１個ずつまたは２個以上の組み合わせとその出現回数とを求めて、時系列相関データを抽出する。
【０３１１】
この場合、時系列フィルタ部は、入力データをフィルタリングして必要なデータを残す処理を行い、時系列相関エンジン部は、入力データから時系列相関ルールを生成して抽出する処理を行うが、特に、前記時系列フィルタ部は、次のような処理を行う。
【０３１２】
すなわち、時系列フィルタ部は、前記指定手段、検索手段、出力手段を備え、複数の属性からなるレコードの集合からレコードの組み合わせを検索する。この時、前記指定手段は、レコード内の所定属性が特定の値をとることをそれぞれ定義する複数イベントと、属性の順序に基づいて定義されたそれらのイベントの間の順序関係とを用いて、検索パターン（イベントパターン）を指定する。
【０３１３】
前記検索手段は、レコードの集合から、指定された検索パターンに対応するレコードの組み合わせを検索し、出力手段は、検索結果を出力する。イベントは、レコード内の所定属性が特定の値をとる状態として定義され、複数のイベントの間の順序関係は、それらのイベントに対応するレコードの間において、１つ以上の属性の値の順序関係に基づいて定義される。
【０３１４】
ユーザは、指定手段を用いて、これらのイベントとイベント間の順序関係により決められる検索パターンを指定する。指定手段は、検索パターンを検索手段に渡し、検索手段は、受け取った検索パターンを解釈して、検索パターンに対応するレコードの組み合わせを抽出する。そして、出力手段は、抽出されたレコード等の情報を検索結果として出力する。
【０３１５】
このような装置によれば、２つ以上のイベントが同じ順序に存在する場合や、複数のイベントの順序関係が任意の間隔で記述される場合を含めて、様々な検索パターンを容易に指定することが可能となり、順序を考慮した汎用的な時系列フィルタリング処理を行うことができる。このようにして、前記のようなトランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０３１６】
（２）　：請求項２では、時系列フィルタ部を時系列相関エンジン部の前段に置いた例であり、時系列フィルタ部と時系列相関エンジン部を１つのプログラムで構成した例である。この場合、入力データは時系列フィルタ部でフィルタリング処理を行うことで、組み合わせを減少させ、処理の時間短縮を行う。
【０３１７】
次に、時系列相関エンジン部で時系列相関ルールを抽出して出力する。このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０３１８】
（３）　：請求項３では、時系列相関エンジン部を時系列フィルタ部の前段に置いた例であり、時系列相関エンジン部と時系列フィルタ部を１つのプログラムとして構成した例である。この場合、入力データは時系列相関エンジン部で時系列相関ルールを抽出し、その後、時系列フィルタ部でフィルタリング処理を行い、時系列相関ルールを抽出して出力する。このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０３１９】
（４）　：請求項４では、時系列相関エンジン部の前後両方に時系列フィルタ部を設け、２つの時系列フィルタ部と１つの時系列相関エンジン部を１つのプログラムで構成した例である。この場合、入力データは時系列フィルタ部でフィルタリング処理を行い、その後、時系列相関エンジン部で時系列相関ルールを抽出し、更に、別の時系列フィルタ部でフィルタリングを行うことで相関ルールを出力する。
【０３２０】
この例では、前段の時系列フィルタ部で組み合わせを減少させ、後段の時系列フィルタ部で無駄なものを除外する機能がある。このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。
【０３２１】
（５）　：請求項５では、時系列フィルタ部と時系列相関エンジン部とをそれぞれ別の１つのプログラム部で構成した例である。すなわち、時系列フィルタ部を１つのプログラムで構成し、時系列相関エンジン部５を別の１つのプログラムで構成する。
【０３２２】
このようにすれば、トランザクションの数が増えても、処理に多大の時間が掛かるのを防止し、高速に時系列相関ルールを抽出することが可能になる。また、時系列フィルタ部と時系列相関エンジン部が別のプログラムで構成されているので、並列処理が可能であり、更に、時系列フィルタ部４の取り換えが可能である。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】本発明の実施の形態における時系列相関抽出装置の説明図である。
【図３】本発明の実施の形態における時系列相関抽出装置のプログラムの説明図（その１）であり、Ａ図は例１、Ｂ図は例２、Ｃ図は例３、Ｄ図は例４である。
【図４】本発明の実施の形態における時系列相関抽出装置のプログラムの説明図（その２）であり、Ｅ図は例５、Ｆ図は例６、Ｇ図は例７、Ｈ図は例８である。
【図５】本発明の実施の形態における入力データ形式であり、Ａ図は入力データ（テキスト表現）、Ｂ図は形式の説明図である。
【図６】本発明の実施の形態における処理の説明図であり、Ａ図は組み合わせ（長さ２）、Ｂ図はＣＩＤ＝１，４を削除した組み合わせ、Ｃ図は単純なフィルタでは効果がない入力である。
【図７】本発明の実施の形態における例１の処理フローチャートである。
【図８】本発明の実施の形態における例２の処理フローチャートである。
【図９】本発明の実施の形態における例３の処理フローチャートである。
【図１０】本発明の実施の形態における具体的な装置の構成図である。
【図１１】本発明の実施の形態における正規表現によるパターンマッチングを示す図である。
【図１２】本発明の実施の形態におけるＮＦＡを示す図である。
【図１３】本発明の実施の形態におけるＤＦＡを示す図である。
【図１４】本発明の実施の形態における正規表現の演算子を示す図である。
【図１５】本発明の実施の形態における小売り業売上データを示す図である。
【図１６】本発明の実施の形態における時系列フィルタ部の原理的な説明図である。
【図１７】本発明の実施の形態におけるイベント定義を示す図である。
【図１８】本発明の実施の形態におけるイベント間定義を示す図である。
【図１９】本発明の実施の形態における検索装置の構成図である。
【図２０】本発明の実施の形態における全体処理のフローチャートである。
【図２１】本発明の実施の形態における検索時のデータ構造を示す図である。
【図２２】本発明の実施の形態における検索処理のフローチャートである。
【図２３】本発明の実施の形態における第１のテーブルを示す図である。
【図２４】本発明の実施の形態における第２のテーブルを示す図である。
【図２５】本発明の実施の形態におけるＳＱＬ文を示す図である。
【図２６】本発明の実施の形態における圧縮されたデータを示す図である。
【図２７】本発明の実施の形態におけるレコードの削減処理を示す図である。
【図２８】本発明の実施の形態における第１の検索対象データを示す図である。
【図２９】本発明の実施の形態におけるＧＵＩの画面を示す図である。
【図３０】本発明の実施の形態における第２の検索対象データを示す図である。
【図３１】本発明の実施の形態における並べ替えられたデータを示す図である。
【図３２】本発明の実施の形態におけるイベント定義に対応するレコードを示す図である。
【図３３】本発明の実施の形態におけるイベントパターンに対応するレコードを示す図である。
【図３４】本発明の実施の形態における整列されたデータを示す図である。
【図３５】本発明の実施の形態における第１のインデクスを示す図である。
【図３６】本発明の実施の形態における第２のインデクスを示す図である。
【図３７】本発明の実施の形態における第３の検索対象データを示す図である。
【図３８】本発明の実施の形態における第１の問い合わせパターンを示す図である。
【図３９】本発明の実施の形態におけるポインタの移動を示す図である。
【図４０】本発明の実施の形態における検索対象データの内部形式を示す図である。
【図４１】本発明の実施の形態における第２の問い合わせパターンを示す図である。
【図４２】本発明の実施の形態における第３の問い合わせパターンを示す図である。
【図４３】従来例１の説明図であり、Ａ図は時系列相関抽出装置の説明図、Ｂ図は処理フローチャートである。
【図４４】従来例におけるＳＥＴＭアルゴリズムにおける具体的な処理の流れを説明する図である。
【図４５】従来例におけるＳＥＴＭアルゴリズムの処理における各機能ブロックの処理内容を示す図である。
【図４６】従来例におけるアプリオリ・アルゴリズムにおける具体的な処理の流れを説明する図である。
【図４７】従来例におけるアプリオリ・アルゴリズムにおける各機能ブロックの内容を説明する図である。
【図４８】従来例における時系列分析におけるシーケンスリストの例を説明する図である。
【図４９】従来例における時系列分析におけるＧ（１）　までの処理を説明する図（その１）である。
【図５０】従来例における時系列分析におけるシーケンスリストの例を説明する図（その２）である。
【図５１】従来例における時系列分析におけるＧ（１）　までの処理を説明する図（その３）である。
【図５２】従来例における時系列分析におけるＧ（１）　までの処理を説明する図（その４）である。
【図５３】従来例における時系列分析におけるＧ（１）　までの処理を説明する図（その５）である。
【図５４】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その１）である。
【図５５】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その２）である。
【図５６】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その３）である。
【図５７】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その４）である。
【図５８】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その５）である。
【図５９】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その６）である。
【図６０】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その７）である。
【図６１】従来例における時系列分析におけるＬ（１）　の選択を説明する図（その８）である。
【図６２】従来例における時系列分析におけるＧ（２）　までの処理を説明する図（その１）である。
【図６３】従来例における時系列分析におけるＧ（２）　までの処理を説明する図（その２）である。
【図６４】従来例における時系列分析におけるＧ（２）　までの処理を説明する図（その３）である。
【図６５】従来例における時系列分析におけるＧ（２）　までの処理を説明する図（その４）である。
【図６６】従来例における時系列分析におけるＧ（２）　までの処理を説明する図（その５）である。
【図６７】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その１）である。
【図６８】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その２）である。
【図６９】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その３）である。
【図７０】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その４）である。
【図７１】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その５）である。
【図７２】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その６）である。
【図７３】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その７）である。
【図７４】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その８）である。
【図７５】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その９）である。
【図７６】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その１０）である。
【図７７】従来例における時系列分析におけるＬ（２）　の選択を説明する図（その１１）である。
【図７８】従来例における時系列分析におけるＧ（３）　までの処理を説明する図（その１）である。
【図７９】従来例における時系列分析におけるＧ（３）　までの処理を説明する図（その２）である。
【図８０】従来例における時系列分析におけるＧ（３）　までの処理を説明する図（その３）である。
【図８１】従来例における時系列分析におけるＧ（３）　までの処理を説明する図（その４）である。
【図８２】従来例における時系列分析におけるＧ（３）　までの処理を説明する図（その５）である。
【図８３】従来例における時系列分析におけるＬ（３）　の選択を説明する図である。
【図８４】従来例における基本相関分析における処理の流れを説明する図である。
【図８５】従来例におけるアイテム組み合わせ数数え上げ処理におけるハッシュ済みリスト生成処理の経過を説明する図である。
【図８６】図８５の処理結果としてのハッシュ済みリストを示す図である。
【図８７】図８６のハッシュ済みリストに対する最小ハッシュ値レコード取り出し処理の経過を示す図である。
【図８８】ソート処理に基づくグループバイ処理の従来例のフローチャートである。
【図８９】図８８のフローチャートを用いた具体的な処理経過の説明図である。
【図９０】ハッシュ処理に基づくグループバイ処理の従来例のフローチャートである。
【図９１】図９０のフローチャートを用いた具体的な処理経過の説明図である。
【図９２】グループバイ処理方式の第１の実施例におけるハッシュ処理を説明する図である。
【図９３】グループバイ処理方式の第１の実施例におけるハッシュ処理の経過を示す図である。
【図９４】グループバイ処理方式の第１および第２の実施例におけるグループバイ関数処理の全体フローチャートである。
【図９５】グループバイ処理方式の第１および第２の実施例におけるグループバイ関数処理の全体説明図である。
【図９６】本発明のデータ組み合わせ数え上げ方式の実施例の構成を説明する図である。
【図９７】本発明のデータ組み合わせ数え上げ方式の全体処理フローチャートである。
【図９８】ラージアイテムセット生成処理のフローチャートである。
【図９９】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）　とその数え上げＧ（１）　を説明する図（その１）である。
【図１００】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）　とその数え上げＧ（１）　を説明する図（その２）である。
【図１０１】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）　とその数え上げＧ（１）　を説明する図（その３）である。
【図１０２】長さ１のアイテムの組み合わせ候補の生成Ｃ（１）　とその数え上げＧ（１）　を説明する図（その４）である。
【図１０３】グループバイ処理の第１の実施例におけるハッシュ処理の結果として得られるハッシュ済みリストを示す図である。
【図１０４】長さ１のラージアイテムセットＬ（１）　の選択を説明する図（その１）である。
【図１０５】長さ１のラージアイテムセットＬ（１）　の選択を説明する図（その２）である。
【図１０６】長さ１のラージアイテムセットＬ（１）　の選択を説明する図（その３）である。
【図１０７】長さ１のラージアイテムセットＬ（１）　の選択を説明する図（その４）である。
【図１０８】長さ１のラージアイテムセットＬ（１）　の選択を説明する図（その５）である。
【図１０９】長さ１のラージアイテムセットＬ（１）　の選択を説明する図（その６）である。
【図１１０】長さ２のアイテムの組み合わせ候補数え上げＧ（２）　までの処理を説明する図（その１）である。
【図１１１】長さ２のアイテムの組み合わせ候補数え上げＧ（２）　までの処理を説明する図（その２）である。
【図１１２】長さ２のアイテムの組み合わせ候補数え上げＧ（２）　までの処理を説明する図（その３）である。
【図１１３】長さ２のアイテムの組み合わせ候補数え上げＧ（２）　までの処理を説明する図（その４）である。
【図１１４】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その１）である。
【図１１５】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その２）である。
【図１１６】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その３）である。
【図１１７】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その４）である。
【図１１８】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その５）である。
【図１１９】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その６）である。
【図１２０】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その７）である。
【図１２１】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その８）である。
【図１２２】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その９）である。
【図１２３】長さ２のアイテムのラージアイテムセットＬ（２）　の選択を説明する図（その１０）である。
【図１２４】長さ３のアイテムの組み合わせ候補数え上げＧ（３）　までの処理を説明する図（その１）である。
【図１２５】長さ３のアイテムの組み合わせ候補数え上げＧ（３）　までの処理を説明する図（その２）である。
【図１２６】長さ３のアイテムの組み合わせ候補数え上げＧ（３）　までの処理を説明する図（その３）である。
【図１２７】長さ３のアイテムの組み合わせ候補数え上げＧ（３）　までの処理を説明する図（その４）である。
【図１２８】長さ３のラージアイテムセットＬ（３）　の選択を説明する図（その１）である。
【図１２９】長さ３のラージアイテムセットＬ（３）　の選択を説明する図（その２）である。
【図１３０】長さ３のラージアイテムセットＬ（３）　の選択を説明する図（その３）である。
【符号の説明】
１　時系列相関抽出装置
２　入力装置
３　出力装置
４　時系列フィルタ部
５　時系列相関エンジン部
１０　コンピュータ本体
１１　ディスプレイ装置（表示装置）
１２　入力装置
１３　リムーバブルディスクドライブ（ＲＤＤ）
１４　ハードディスク装置（ＨＤＤ）
１５　ＣＰＵ（中央演算処理装置）
１６　ＲＯＭ（リード・オンリ・メモリ）
１７　メモリ
１８　インタフェース制御部（Ｉ／Ｆ制御部）
１９　通信制御部
【図１】
2004110327.tif 000005
【図２】
2004110327.tif 000006
【図３】
2004110327.tif 000007
【図４】
2004110327.tif 000008
【図５】
2004110327.tif 000009
【図６】
2004110327.tif 000010
【図７】
2004110327.tif 000011
【図８】
2004110327.tif 000012
【図９】
2004110327.tif 000013
【図１０】
2004110327.tif 000014
【図１１】
2004110327.tif 000015
【図１２】
2004110327.tif 000016
【図１３】
2004110327.tif 000017
【図１４】
2004110327.tif 000018
【図１５】
2004110327.tif 000019
【図１６】
2004110327.tif 000020
【図１７】
2004110327.tif 000021
【図１８】
2004110327.tif 000022
【図１９】
2004110327.tif 000023
【図２０】
2004110327.tif 000024
【図２１】
2004110327.tif 000025
【図２２】
2004110327.tif 000026
【図２３】
2004110327.tif 000027
【図２４】
2004110327.tif 000028
【図２５】
2004110327.tif 000029
【図２６】
2004110327.tif 000030
【図２７】
2004110327.tif 000031
【図２８】
2004110327.tif 000032
【図２９】
2004110327.tif 000033
【図３０】
2004110327.tif 000034
【図３１】
2004110327.tif 000035
【図３２】
2004110327.tif 000036
【図３３】
2004110327.tif 000037
【図３４】
2004110327.tif 000038
【図３５】
2004110327.tif 000039
【図３６】
2004110327.tif 000040
【図３７】
2004110327.tif 000041
【図３８】
2004110327.tif 000042
【図３９】
2004110327.tif 000043
【図４０】
2004110327.tif 000044
【図４１】
2004110327.tif 000045
【図４２】
2004110327.tif 000046
【図４３】
2004110327.tif 000047
【図４４】
2004110327.tif 000048
【図４５】
2004110327.tif 000049
【図４６】
2004110327.tif 000050
【図４７】
2004110327.tif 000051
【図４８】
2004110327.tif 000052
【図４９】
2004110327.tif 000053
【図５０】
2004110327.tif 000054
【図５１】
2004110327.tif 000055
【図５２】
2004110327.tif 000056
【図５３】
2004110327.tif 000057
【図５４】
2004110327.tif 000058
【図５５】
2004110327.tif 000059
【図５６】
2004110327.tif 000060
【図５７】
2004110327.tif 000061
【図５８】
2004110327.tif 000062
【図５９】
2004110327.tif 000063
【図６０】
2004110327.tif 000064
【図６１】
2004110327.tif 000065
【図６２】
2004110327.tif 000066
【図６３】
2004110327.tif 000067
【図６４】
2004110327.tif 000068
【図６５】
2004110327.tif 000069
【図６６】
2004110327.tif 000070
【図６７】
2004110327.tif 000071
【図６８】
2004110327.tif 000072
【図６９】
2004110327.tif 000073
【図７０】
2004110327.tif 000074
【図７１】
2004110327.tif 000075
【図７２】
2004110327.tif 000076
【図７３】
2004110327.tif 000077
【図７４】
2004110327.tif 000078
【図７５】
2004110327.tif 000079
【図７６】
2004110327.tif 000080
【図７７】
2004110327.tif 000081
【図７８】
2004110327.tif 000082
【図７９】
2004110327.tif 000083
【図８０】
2004110327.tif 000084
【図８１】
2004110327.tif 000085
【図８２】
2004110327.tif 000086
【図８３】
2004110327.tif 000087
【図８４】
2004110327.tif 000088
【図８５】
2004110327.tif 000089
【図８６】
2004110327.tif 000090
【図８７】
2004110327.tif 000091
【図８８】
2004110327.tif 000092
【図８９】
2004110327.tif 000093
【図９０】
2004110327.tif 000094
【図９１】
2004110327.tif 000095
【図９２】
2004110327.tif 000096
【図９３】
2004110327.tif 000097
【図９４】
2004110327.tif 000098
【図９５】
2004110327.tif 000099
【図９６】
2004110327.tif 000100
【図９７】
2004110327.tif 000101
【図９８】
2004110327.tif 000102
【図９９】
2004110327.tif 000103
【図１００】
2004110327.tif 000104
【図１０１】
2004110327.tif 000105
【図１０２】
2004110327.tif 000106
【図１０３】
2004110327.tif 000107
【図１０４】
2004110327.tif 000108
【図１０５】
2004110327.tif 000109
【図１０６】
2004110327.tif 000110
【図１０７】
2004110327.tif 000111
【図１０８】
2004110327.tif 000112
【図１０９】
2004110327.tif 000113
【図１１０】
2004110327.tif 000114
【図１１１】
2004110327.tif 000115
【図１１２】
2004110327.tif 000116
【図１１３】
2004110327.tif 000117
【図１１４】
2004110327.tif 000118
【図１１５】
2004110327.tif 000119
【図１１６】
2004110327.tif 000120
【図１１７】
2004110327.tif 000121
【図１１８】
2004110327.tif 000122
【図１１９】
2004110327.tif 000123
【図１２０】
2004110327.tif 000124
【図１２１】
2004110327.tif 000125
【図１２２】
2004110327.tif 000126
【図１２３】
2004110327.tif 000127
【図１２４】
2004110327.tif 000128
【図１２５】
2004110327.tif 000129
【図１２６】
2004110327.tif 000130
【図１２７】
2004110327.tif 000131
【図１２８】
2004110327.tif 000132
【図１２９】
2004110327.tif 000133
【図１３０】
2004110327.tif 000134