(57)【特許請求の範囲】
【請求項１】
変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見プログラムであって、
系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶手順と、
任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶手順により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数手順と、
前記系列パターン計数手順により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶手順により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見手順と、
前記系列パターン発見手順により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力手順と、
をコンピュータに実行させることを特徴とする系列パターン発見プログラム。
【請求項２】
前記系列パターン計数手順は、
前記系列パターンを一意に識別する一般化パターン番号と、該一般化パターンの出現数を計数するための一般化パターンカウンタとを対応付けた一般化パターンテーブルを備え、
前記系列データから前記一般化パターン番号を導出するための写像である一般化写像を生成する一般化写像生成手順と、
前記系列データ記憶手順により記憶された系列データを順次読み出すとともに、該読み出した系列データから前記一般化写像を用いて前記一般化パターン番号を導出し、前記一般化パターンテーブルの、該導出した一般化パターン番号に対応する一般化パターンカウンタをカウントアップする一般化パターンカウンタ計数手順と、
をコンピュータに実行させることを特徴とする請求項１に記載の系列パターン発見プログラム。
【請求項３】
前記系列パターン発見手順は、
前記系列パターン計数手順により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値の一つに選択項目値を設定することによって系列パターンを逐次生成し、
該逐次生成した系列パターンと、前記系列データ記憶手順により記憶された系列データとを照合することにより、該系列データがマッチする系列パターンの出現数を計数し、
該計数した出現数が所定の閾値以上である系列パターンを抽出し、該抽出した系列パターンに含まれる任意項目値の一つに選択項目値を設定することによってさらに系列パターンを詳細化し、
該詳細化した系列パターンと、前記系列データ記憶手順により記憶された系列データとを照合することにより、該系列データがマッチする系列パターンの出現数を計数し、
該系列パターンに含まれる全ての任意項目値に選択項目値を設定するまで、前記系列パターンの詳細化と、前記系列パターンの出現数の計数とを繰り返すことを特徴とする請求項１または２に記載の系列パターン発見プログラム。
【請求項４】
前記系列パターン計数手順は、
許容する値を選択した選択項目値と項目値のみを含んだ系列パターンを詳細化パターンとして定義し、
前記詳細化パターンを一意に識別する詳細化パターン番号と、該詳細化パターンの出現数を計数するための詳細化パターンカウンタとを対応付けた詳細化パターンテーブルを備え、
前記系列データに含まれる項目値から前記詳細化パターン番号を導出するための写像である詳細化写像を生成する詳細化写像生成手順と、
前記系列データ記憶手順により記憶された系列データを順次読み出すとともに、該読み出した系列データから前記詳細化写像を用いて前記詳細化パターン番号を導出し、前記詳細化パターンテーブルの、該導出した詳細化パターン番号に対応する詳細化パターンカウンタをカウントアップする詳細化パターンカウンタ計数手順と、
をコンピュータに実行させることを特徴とする請求項１または２に記載の系列パターン発見プログラム。
【請求項５】
前記系列データ記憶手順は、連続して変化する値を離散化し、該離散化した間隔ごとの値を項目値として順番に並べた系列データをパターン抽出の対照として記憶することを特徴とする請求項１〜４のいずれか一つに記載の系列パターン発見プログラム。
【請求項６】
変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見方法であって、
系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶工程と、
任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶工程により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数工程と、
前記系列パターン計数工程により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶工程により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見工程と、
前記系列パターン発見工程により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力工程と、
を含んだことを特徴とする系列パターン発見方法。
【請求項７】
変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見装置であって、
系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶手段と、
任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶手段により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数手段と、
前記系列パターン計数手段により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶手段により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見手段と、
前記系列パターン発見手段により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力手段と、
を備えたことを特徴とする系列パターン発見装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見プログラム、系列パターン発見方法および系列パターン発見装置に関し、特に、系列パターンの出現数を効率良く計数することによって系列パターンの抽出にかかる処理時間を短縮することができる系列パターン発見プログラム、系列パターン発見方法および系列パターン発見装置に関するものである。
【背景技術】
【０００２】
近年、販売、流通、株式売買等の幅広い分野で、コンピュータなどに蓄積された過去のデータを解析し、そのデータに含まれる項目値間の相関関係やパターンなどを探索するデータマイニングと呼ばれる技術によって意思決定を支援することが行われている。例えば、株式売買の分野においては、過去の株価データから、株価の変動を表す系列パターンを予測し、予測したパターンを株売買のタイミングを決定するための指標として利用している。
【０００３】
このようなパターン予測の技術として、例えば、特許文献１においては、出現した事象を項目値として時系列に並べた時系列データから、各事象が出現する順序を示す時系列パターンを抽出する技術が示されている。この技術では、あらかじめ、出現し得る事象を分類した概念を階層構造で記憶しておき、最下層の概念から順番に時系列データを参照して、それぞれの概念（事象）が出現した頻度を集計する。
【０００４】
さらに、概念を時系列に順序だてて組み合わせた時系列パターンについて、組み合わせる概念の個数を増やしながら、時系列データを参照することによってそれぞれの時系列パターンが出現した頻度を集計してゆく。組み合わせる概念の個数を増やす際には、すでに頻度を集計している時系列パターンのうち、頻度が所定の閾値以上であるものに対して新たな概念を１つずつ加えてゆく。こうして、最終的に、所定の閾値以上の頻度で発生した概念（事象）の時系列パターンを抽出する。
【０００５】
【特許文献１】特開２００５−８４９１９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の技術においては、それぞれの時系列パターンが出現した頻度を集計する際には、時系列パターンごとに、その都度全ての時系列データを参照するため集計処理に時間がかかり、特に、抽出対象の時系列データの量が膨大である場合や、所定の閾値を小さく設定した場合、概念の階層を深く設定した場合には、業務時間内に処理が終了しないことも発生し得るという問題がある。
【０００７】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、系列パターンの出現数を効率良く計数することによって系列パターンの抽出にかかる処理時間を短縮することができる系列パターン発見プログラム、系列パターン発見方法および系列パターン発見装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するため、請求項１の発明に係る系列パターン発見プログラムは、変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見プログラムであって、系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶手順と、任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶手順により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数手順と、前記系列パターン計数手順により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶手順により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見手順と、前記系列パターン発見手順により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力手順と、をコンピュータに実行させることを特徴とする。
【０００９】
また、請求項２の発明に係る系列パターン発見プログラムは、請求項１の発明において、前記系列パターン計数手順は、前記一般化パターンを一意に識別する一般化パターン番号と、該一般化パターンの出現数を計数するための一般化パターンカウンタとを対応付けた一般化パターンテーブルを備え、前記系列データから前記一般化パターン番号を導出するための写像である一般化写像を生成する一般化写像生成手順と、前記系列データ記憶手順により記憶された系列データを順次読み出すとともに、該読み出した系列データから前記一般化写像を用いて前記一般化パターン番号を導出し、前記一般化パターンテーブルの、該導出した一般化パターン番号に対応する一般化パターンカウンタをカウントアップする一般化パターンカウンタ計数手順と、をコンピュータに実行させることを特徴とする。
【００１０】
また、請求項３の発明に係る系列パターン発見プログラムは、請求項１または２の発明において、前記系列パターン発見手順は、前記系列パターン計数手順により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値の一つに選択項目値を設定することによって系列パターンを逐次生成し、該逐次生成した系列パターンと、前記系列データ記憶手順により記憶された系列データとを照合することにより、該系列データがマッチする系列パターンの出現数を計数し、該計数した出現数が所定の閾値以上である系列パターンを抽出し、該抽出した系列パターンに含まれる任意項目値の一つに選択項目値を設定することによってさらに系列パターンを詳細化し、該詳細化した系列パターンと、前記系列データ記憶手順により記憶された系列データとを照合することにより、該系列データがマッチする系列パターンの出現数を計数し、該系列パターンに含まれる全ての任意項目値に選択項目値を設定するまで、前記系列パターンの詳細化と、前記系列パターンの出現数の計数とを繰り返すことを特徴とする。
【００１１】
また、請求項４の発明に係る系列パターン発見プログラムは、請求項１または２の発明において、前記系列パターン計数手順は、許容する値を選択した選択項目値と項目値のみを含んだ系列パターンを詳細化パターンとして定義し、前記詳細化パターンを一意に識別する詳細化パターン番号と、該詳細化パターンの出現数を計数するための詳細化パターンカウンタとを対応付けた詳細化パターンテーブルを備え、前記系列データから前記詳細化パターン番号を導出するための写像である詳細化写像を生成する詳細化写像生成手順と、前記系列データ記憶手順により記憶された系列データを順次読み出すとともに、該読み出した系列データから前記詳細化写像を用いて前記詳細化パターン番号を導出し、前記詳細化パターンテーブルの、該導出した詳細化パターン番号に対応する詳細化パターンカウンタをカウントアップする詳細化パターンカウンタ計数手順と、をコンピュータに実行させることを特徴とする。
【００１２】
また、請求項５の発明に係る系列パターン発見プログラムは、請求項１〜４の発明において、前記系列データ記憶手順は、連続して変化する値を離散化し、該離散化した間隔ごとの値を項目値として順番に並べた系列データをパターン抽出の対照として記憶することを特徴とする。
【００１３】
また、請求項６の発明に係る系列パターン発見方法は、変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見方法であって、系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶工程と、任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶工程により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数工程と、前記系列パターン計数工程により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶工程により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見工程と、前記系列パターン発見工程により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力工程と、を含んだことを特徴とする。
【００１４】
また、請求項７の発明に係る系列パターン発見装置は、変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見装置であって、系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶手段と、任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶手段により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数手段と、前記系列パターン計数手段により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶手段により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見手段と、前記系列パターン発見手段により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力手段と、を備えたことを特徴とする。
【発明の効果】
【００１５】
請求項１、６および７の発明によれば、系列パターン抽出の対象となる系列データを記憶し、任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、記憶している系列データを順次読み出して、系列データがマッチする一般化パターンの出現数を計数し、計数した出現数が所定の閾値以上である一般化パターンを抽出し、抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、さらに、記憶している系列データを順次読み出して系列パターンと照合することにより、系列データがマッチする系列パターンの出現数を計数し、計数した出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力するよう構成したので、まずは大まかな条件で系列パターンの出現数を計数し、所定の閾値で絞り込んだ上で、さらに詳細な条件で系列パターンの出現数を計数することが可能となり、系列パターンの出現数を効率良く計数することによって、系列パターンの抽出にかかる処理時間を短縮することができるという効果を奏する。
【００１６】
また、請求項２の発明によれば、一般化パターンを一意に識別する一般化パターン番号と、一般化パターンの出現数を計数するための一般化パターンカウンタとを対応付けた一般化パターンテーブルを備え、また、系列データから一般化パターン番号を導出するための写像である一般化写像を生成し、記憶している系列データを順次読み出すとともに、読み出した系列データから一般化写像を用いて一般化パターン番号を導出し、一般化パターンテーブルの、導出した一般化パターン番号に対応する一般化パターンカウンタをカウントアップするよう構成したので、頻出する可能性のある系列パターン群を生成するたびに系列データを全て読み出して当該系列パターンの出現数を計数するのではなく、一般化写像を生成するたびに系列データを全て読み出すことによって、同じ写像で表される全ての一般化パターンの出現数が一括して計数される。この結果、候補パターン数の爆発に影響されず、決まった回数だけ系列データを走査すれば頻出する一般化パターン発見が完了するので、処理時間が閾値に影響されないという効果を奏する。
【００１７】
また、請求項３の発明によれば、計数された出現数が所定の閾値以上である一般化パターンを抽出し、抽出した一般化パターンに含まれる任意項目値の一つに選択項目値を設定することによって系列パターンを逐次生成し、逐次生成した系列パターンと、記憶している系列データとを照合することにより、系列データがマッチする系列パターンの出現数を計数し、計数した出現数が所定の閾値以上である系列パターンを抽出し、抽出した系列パターンに含まれる任意項目値の一つに選択項目値を設定することによってさらに系列パターンを詳細化し、詳細化した系列パターンと系列データとを照合することにより、系列データがマッチする系列パターンの出現数を計数し、系列パターンに含まれる全ての任意項目値に選択項目値を設定するまで、かかる系列パターンの詳細化と、系列パターンの出現数の計数とを繰り返すよう構成したので、まずは一般化パターンの出現数を計数し、所定の閾値を用いて一般化パターンを絞り込んだ後に、絞り込んだ一般化パターンに含まれる任意項目値の一つを選択項目値に置き換えて系列パターンを逐次生成し、さらに、一つずつ任意項目値を選択項目値に置き換えることによって系列パターンを段階的に詳細化し、その都度、所定の閾値を用いて、計数する必要のない系列パターンを排除してゆくことが可能となり、系列パターンの出現数を効率良く計数して系列パターンの抽出にかかる処理時間を短縮することができるという効果を奏する。
【００１８】
また、請求項４の発明によれば、詳細化パターンを一意に識別する詳細化パターン番号と、詳細化パターンの出現数を計数するための詳細化パターンカウンタとを対応付けた詳細化パターンテーブルを備え、また、系列データから詳細化パターン番号を導出するための写像である詳細化写像を生成し、記憶している系列データを順次読み出すとともに、まず一般化写像を適用して一般化パターン番号を得て、一般化パターンテーブルを参照することにより、この一般化パターン番号に対応する詳細化パターンテーブルを得る。続いて系列データに詳細化写像を適用して詳細化パターン番号を得て、詳細化パターンテーブルを参照することにより、この詳細化パターン番号に対応する詳細化パターンカウンタを得て、これを計数するよう構成したので、頻出する可能性のある系列パターン群を生成するたびに系列データを全て読み出して当該系列パターンの出現数を計数するのではなく、一般化写像および詳細化写像を生成するたびに系列データを全て読み出すことによって、同じ写像の組で表される全ての詳細化パターンの出現数が一括して計数される。この結果、候補パターン数の爆発に影響されず、決まった回数だけ系列データを走査すれば頻出する一般化パターン発見が完了するので、処理時間が閾値に影響されないという効果を奏する。
【００１９】
また、請求項５の発明によれば、連続して変化する値を離散化し、離散化した間隔ごとの値を項目値として順番に並べた系列データをパターン抽出の対照として記憶するよう構成したので、例えば株価や商品の売上額などのように、連続して変化する項目値についても、所定の間隔で離散化することによって値をサンプリングし、サンプリングした値を系列データとして、その変動において頻繁に出現する系列パターンを抽出することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２０】
以下に添付図面を参照して、この発明に係る系列パターン発見プログラム、系列パターン発見方法および系列パターン発見装置の好適な実施例を詳細に説明する。なお、本実施例では、株価の時系列データから株価の系列パターンを発見する場合について説明する。
【実施例１】
【００２１】
まず、本実施例１に係る系列パターン発見装置の概念について説明する。図１は、系列パターンの抽出対象となる系列データの一例を示す図である。同図は、ある証券の１週間の日々の株価の終値を日ごとに並べた時系列データを示している。同図に示す「数値データ」は、日々の株価の終値であり、「前日との増減」は、前日との株価の終値の差額である。また、「離散化データ」は、前日との株価の終値の差額を５段階に離散化した数値であり、差額が−１００以上である場合には「０（大幅安）」を、−９９から−２０の間である場合には「１（小幅安）」を、−１９から＋１９の間である場合には「２（変動なし）」を、２０から９９の間である場合には「３（小幅高）」を、１００以上である場合には「４（大幅高）」を設定している。この「離散化データ」を項目値とする系列データを、例えば、＜３  １  ３  １  ４  ０＞と表す。
【００２２】
本実施例１においては、上述した「離散化データ」を項目値とした系列データが証券ごとに蓄積されている系列データベースから系列パターンを抽出する場合を説明する。
【００２３】
まず、抽出する系列パターンを定義する。例えば、系列パターン＜３  ｛０，１，２，３，４｝  ３  １  ｛０，１，２，３，４｝  ０＞であるが、２番目の項目と５番目の項目値に設定されている｛０，１，２，３，４｝は、任意の項目値を許容する任意項目値を表しており、この系列パターンと系列データとを照合する際に、系列データの２番目の項目値と５番目の項目が「０」，「１」，「２」，「３」，「４」のいずれであってもよいことを示している。このような、所定の数の任意項目値と、所定の数の項目値のみを含んだ系列パターンを一般化パターンと呼ぶ。
【００２４】
ここで、抽出する系列パターンの長さをｌ、抽出する系列パターンに含まれる任意項目値の数をｋとすると、上述した一般化パターンＴM（ｌ，ｋ）は、以下に示す数式（１）で表される。
【００２５】
【数１】
0004711863.tif 000002
【００２６】
上記の数式（１）において、Σは、抽出対象の系列データに設定され得る項目値（ここでは、「離散化データ」に設定され得る項目値であり、すなわち、「０」，「１」，「２」，「３」，「４」。）を表しており、ΠMは、任意項目値を示している。
【００２７】
例えば、系列パターン＜３  ｛０，１｝  ３  １  ｛３，４｝  ０＞であるが、２番目の項目と５番目の項目値に設定されている｛０，１｝や｛３，４｝は、｛２｝も含め、許容する項目値を選択する選択項目値を表しており、この系列パターンと系列データを照合する際に、系列データの２番目の項目値が「０」、「１」いずれかであってよく、系列データの５番目の項目値が「３」、「４」のいずれかであってよいことを示している。このような、所定の数の選択項目値と、所定の数の項目値のみを含んだ系列データを詳細化パターンと呼ぶ。
【００２８】
詳細化パターンＴm（ｌ，ｋ）は、以下に示す数式（２）で表される。
【００２９】
【数２】
0004711863.tif 000003
【００３０】
上記の数式（２）において、Πmは、選択項目値を示している。選択項目値の役割は、任意項目値よりも詳細に変動の幅に制限を加えることである。例えば、｛０，１｝を設定することによって、大小を問わず株価の終値が安値に変動したパターンを指定することができ、｛２｝を指定することによって、株価の終値が変動しなかったパターンを指定することができ、｛３，４｝を指定することによって、大小を問わず株価の終値が高値に変動したパターンを指定することができる。
【００３１】
一般化パターンに含まれる任意項目値のうち、一つ以上の任意項目値を選択項目値に置き換えることによって逐次生成される系列パターンを定義する。例えば、詳細化した系列パターン＜３  ｛０，１｝  ３  １  ｛０，１，２，３，４｝  ０＞であるが、このような所定の数の任意項目巷は選択項目値と、所定の数の項目値を含んだ系列パターンを単に系列パターンと呼ぶ。
【００３２】
本実施例１に係る系列パターン発見装置が発見する系列パターンは、以下に示す数式（３）で表される。
【００３３】
【数３】
0004711863.tif 000004
【００３４】
なお、上記した、抽出する系列パターンの長さｌ、抽出する系列パターンに含まれる任意項目値の数ｋ、抽出対象の系列データに設定され得る項目値Σ、任意項目値ΠM、選択項目値の集合Πm、および、所定の閾値は、それぞれ、利用者によってあらかじめ設定されるものとする。
【００３５】
また、本実施例１においては、抽出対象の系列データの項目値に設定される値が「０」〜「４」である場合を説明したが、本発明はこれに限定されるものではない。例えば、抽出対象の系列データの項目値集合をΣで表すと、系列パターン発見装置が発見する一般化パターン、詳細化パターンおよび系列パターンは、以下に示す数式（４）、（５）および（６）で定義される。
【００３６】
【数４】
0004711863.tif 000005
【００３７】
【数５】
0004711863.tif 000006
【００３８】
【数６】
0004711863.tif 000007
【００３９】
次に、本実施例１に係る系列パターン発見装置の構成について説明する。図２は、本実施例１に係る系列パターン発見装置の構成を示す機能ブロック図である。同図に示すように、この系列パターン発見装置１００は、系列データ記憶部１１０と、テンプレート生成部１２０と、写像生成部１３０と、系列パターン計数部１４０と、系列パターン発見部１５０と、系列パターン出力部１６０とを有する。
【００４０】
系列データ記憶部１１０は、系列パターンの抽出対象となる系列データを記憶する記憶部である。本実施例１においては、この系列データ記憶部１１０は、図１で示した「離散化データ」を、証券ごとに記憶する。
【００４１】
ここで、系列データ記憶部１１０により記憶される系列データＤEの６日前，５日前，４日前，３日前，２日前，１日前の「離散化データ」の値を、それぞれ、ｄ5，ｄ4，ｄ3，ｄ2，ｄ1，ｄ0とし、系列データＤEを、以下の式で表す。
【００４２】
ＤE＝＜ｄ5  ｄ4  ｄ3  ｄ2  ｄ1  ｄ0＞
【００４３】
例えば、図１に示した「離散化データ」の系列データは、以下の式で表される。
【００４４】
ＤE＝＜３  １  ３  １  ４  ０＞
【００４５】
なお、ここでは、株価の終値の前日と当日との差額を５段階に離散化する例を説明したが、離散化する段階を５段階以上に設定することによって、より細かい差幅の変化を示す系列データから系列パターンを発見するようにしてもよいし、離散化する段階を５段階以下に設定することによって、粗い差幅の変化を示す系列データから系列パターンを発見するようにしてもよい。
【００４６】
このように、系列データ記憶部１１０が、連続して変化する変動要素を離散化し、離散化した単位ごとの変動幅を示す値を並べた系列データを系列パターン抽出の対象として記憶することによって、株価や商品の売上額などの連続して変化する変動要素に頻出する系列パターンを抽出することができる。
【００４７】
テンプレート生成部１２０は、利用者によって指定される系列パターンの長さｌおよび抽出する系列パターンに含まれる任意項目値または選択項目値の数ｋとに基づいて、系列パターンを定義するためのテンプレートを生成する処理部である。ここで、テンプレートとは、任意項目値または選択項目値を所定の数だけ含んだ系列パターンの項目構成を表す定義であり、任意項目値または選択項目値と、具体的な項目値（以下、単に項目値）とを所定の数だけ順序だてて組み合わせることによって生成される。以下に、テンプレート生成部１２０によるテンプレートの生成方法を説明する。
【００４８】
テンプレート生成部１２０は、利用者によって指定される抽出する系列パターンの長さをｌ、抽出する系列パターンに含まれる任意項目値または選択項目値の数をｋとした場合、ｋ個の任意項目値または選択項目値とｌ−ｋ個の項目値とを順序だてて組み合わせることにより、lＣk通りのパターンテンプレートＸを生成する。
【００４９】
例えば、前述した「離散化データ」の系列データ
【００５０】
ＤE＝＜ｄ5  ｄ4  ｄ3  ｄ2  ｄ1  ｄ0＞
【００５１】
を系列パターン抽出の対象とし、抽出する系列パターンの長さｌを「６」、抽出する系列パターンに含まれる任意項目値または選択項目値の数ｋを「２」と設定した場合は、パターンテンプレートＸは6Ｃ2（＝１５）通り生成される。
【００５２】
ここで生成される１５通りのテンプレートＸのうちの一つであるテンプレートＸEを、例えば、以下に示す式で表す。
【００５３】
ＸE＝＜ｘ5  ＊  ｘ3  ｘ2  ＊  ｘ0＞
【００５４】
上記の式において、「＊」は任意項目値または選択項目値を表している。
【００５５】
なお、ここでは、抽出する系列パターンの長さｌが「６」、抽出する系列パターンに含まれる任意項目値または選択項目値の数ｋが「２」である場合のテンプレートの生成について説明したが、本発明はこれに限定されるものではなく、上述したように、テンプレートは、ｌおよびｋに設定される値に応じて、適宜生成されるものである。
【００５６】
写像生成部１３０は、テンプレート生成部１２０によって生成されたテンプレートに基づいて、テンプレートごとに、系列データから一般化パターン番号を導出するための写像（以下、一般化写像と呼ぶ）を生成する処理部である。ここで、一般化パターン番号とは、パターンテンプレートによって定義される一般化パターンを一意に識別する識別番号である。以下に、写像生成部１３０による一般化写像の生成方法について説明する。
【００５７】
写像生成部１３０は、まずテンプレート生成部１２０により生成されたテンプレートＸを取得し、取得したテンプレートＸに基づいて一般化写像ｆX（Ｄ）を生成する。
【００５８】
例えば、以下に示すテンプレートＸEに基づいて生成する一般化写像ｆXEを、以下の式で定義する。
【００５９】
【数７】
0004711863.tif 000008
【００６０】
上記の式において、（３），（２），（１），（０）は、任意項目値または選択項目値を表す記号「＊」を無視して右から左へ順番に付与した通番であり、ｄ(3)，ｄ(2)，ｄ(1)，ｄ(0)は、それぞれ、テンプレートＸEで定義されたｘ(3)，ｘ(2)，ｘ(1)，ｘ(0)と同じ位置にある系列データＤEの項目値、すなわち、ｄ5，ｄ3，ｄ2，ｄ0を示している。また、上記の式において、各項目値ｄ5，ｄ3，ｄ2，ｄ0に乗じている５j（ｊ＝３，２，１，０）は、「５」が、抽出対象の系列データに設定され得る項目値Σの数（ここでは、「０」，「１」，「２」，「３」，「４」の５つ）で決められ、指数ｊが、テンプレートＸEにおける具体的な項目値に付与した通番（（３），（２），（１），（０））で決められる。
【００６１】
この一般化写像ｆXE（ＤE）により、例えば、系列データが
【００６２】
ＤE＝＜３  １  ３  １  ４  ０＞
【００６３】
であった場合は、
【００６４】
ｆXE（ＤE）＝３×５3＋３×５2＋１×５1＋０×５0
＝４５５
【００６５】
となり、一般化パターン番号は「４５５」となる。
【００６６】
なお、ここでは、抽出する系列パターンの長さｌが「６」、抽出する系列パターンに含まれる任意項目値または選択項目値の数ｋが「２」、抽出対象の系列データに設定され得る項目値Σの数が「５」である場合の一般化写像の生成について説明したが、本発明はこれに限定されるものではなく、上述したように、一般化写像は、ｌ、ｋおよびΣに設定される値に応じて、適宜生成されるものである。
【００６７】
系列パターン計数部１４０は、系列データ記憶部１１０に記憶された系列データを読み出し、写像生成部１３０により生成された一般化写像を用いて、読み出した系列データがマッチする一般化パターンの出現数を計数する処理部である。具体的には、この系列パターン計数部１４０は、テンプレート生成部１２０により生成されたテンプレートＸに対して、一般化パターン番号とパターンカウンタとを対応付けたパターンテーブルを備える。ここで、一般化パターン番号とは、前述した一般化写像ｆX（Ｄ）によって導出される一般化パターン番号に対応するものであり、０から始まる通番となる。また、パターンカウンタは、一般化パターン番号ごとに、系列データ記憶部１１０に記憶された系列データがマッチする一般化パターンの出現数を計数するためのカウンタである。
【００６８】
図３は、本実施例１に係るパターン計数部１４０によって用いられるパターンテーブルの一例を示す図である。例えば、同図に示すように、前述したテンプレート
【００６９】
ＸE＝＜ｘ5  ＊  ｘ3  ｘ2  ＊  ｘ0＞
【００７０】
に対するパターンテーブルでは、５4（＝６２５）個のパターン番号、すなわち「０」〜「６２４」のパターン番号と、パターンカウンタとが対応付けられている。そして、かかるパターン番号およびパターンカウンタの数は、テンプレートＸＥから生成される一般化パターンのパターン数と同数となる。
【００７１】
系列パターン計数部１４０は、パターンテーブルのパターンカウンタを初期化（「０」を設定）した後に、系列データ記憶部１１０により記憶された系列データＤを順次読み出し、写像生成部１３０により生成された一般化写像ｆX（Ｄ）を用いて一般化パターン番号を導出し、導出した一般化パターン番号に対応するパターンテーブルのパターンカウンタに「１」を加算する。
【００７２】
例えば、前述した系列データ
【００７３】
ＤE＝＜３  １  ３  １  ４  ０＞
【００７４】
を読み出した場合は、
【００７５】
ｆXE（ＤE）＝４５５
【００７６】
となることより、系列パターン計数部１４０は、パターンテーブルの、一般化パターン番号「４５５」に対応するパターンカウンタに「１」を加算する（図３に示すカウント１）。
【００７７】
こうして、系列パターン計数部１４０は、テンプレート生成部１２０により生成された全てのテンプレートに対して、写像を用いたパターンカウンタの加算とを行う。
【００７８】
なお、かかる系列パターン計数部１４０による一般化パターン計数処理の詳細については、図５を用いて後に説明する。
【００７９】
系列パターン発見部１５０は、系列パターン計数部１４０により計数されたパターンカウンタが所定の閾値以上である一般化パターンを抽出し、抽出した一般化パターンに含まれる任意項目値の一つを選択項目値に置き換えて系列パターンを生成し、さらに、一つずつ任意項目値を選択項目値に置き換えることによって系列パターンを段階的に詳細化し、その都度、計数する必要のない系列パターンを排除しながら、系列パターンの出現数を計数する処理部である。
【００８０】
例えば、一般化パターン＜３  ＊  ３  １  ＊  ０＞について、選択項目値｛０，１｝、｛２｝および｛３，４｝を用いて詳細化を行う場合は、系列パターン発見部１５０は、以下に示す６つの系列パターンを生成する。
【００８１】
＜３  ｛０，１｝  ３  １  ＊  ０＞  ，
＜３    ｛２｝    ３  １  ＊  ０＞  ，
＜３  ｛３，４｝  ３  １  ＊  ０＞  ，
＜３  ＊  ３  １  ｛０，１｝  ０＞  ，
＜３  ＊  ３  １    ｛２｝    ０＞  ，
＜３  ＊  ３  １  ｛３，４｝  ０＞
【００８２】
そして、系列パターン発見部１５０は、生成した系列パターンと、系列データ記憶部１１０に記憶された系列データとを、例えば、複数パターンとの照合を可能とする拡張を施したＳｈｉｆｔ−ＡＮＤ法などの文字列照合アルゴリズムを用いて照合することにより、系列データがマッチする系列パターンの出現数を計数する。
【００８３】
なお、ここでは、文字列照合アルゴリズムとしてＳｈｉｆｔ−ＡＮＤ法を用いた場合を説明したが、ここで行う文字列照合は、Ｓｈｉｆｔ−ＡＮＤ法に限らず、任意項目値や選択項目値を含んだ複数の系列パターンと系列データとの照合を行うことが可能な他の公知の文字照合アルゴリズムを用いてもよいものである。
【００８４】
図４は、系列パターン発見部１５０による系列パターン発見処理の一例を示す図である。例えば、同図に示すように、＜３  ｛０，１｝  ３  １  ＊  ０＞の出現数が「５０」、＜３  ｛２｝  ３  １  ＊  ０＞の出現数が「１０」、＜３  ｛３，４｝  ３  １  ＊  ０＞の出現数が「２０」、＜３  ＊  ３  １  ｛０，１｝  ０＞の出現数が「３０」、＜３  ＊  ３  １  ｛２｝  ０＞の出現数が「１０」、＜３  ＊  ３  １  ｛３，４｝  ０＞の出現数が「１０」であり、また、利用者によって指定された所定の閾値が「２０」であったとする。
【００８５】
この場合、系列パターン発見部１５０は、図４に示すように、＜３  ｛０，１｝  ３  １  ＊  ０＞と、＜３  ｛３，４｝  ３  １  ＊  ０＞と、＜３  ＊  ３  １  ｛０，１｝  ０＞とを抽出し、＜３  ｛０，１｝  ３  １  ＊  ０＞と＜３  ＊  ３  １  ｛０，１｝  ０＞とを掛け合わせることによって（図４に示すペア１）、さらに詳細化された詳細化パターン＜３  ｛０，１｝  ３  １  ｛０，１｝  ０＞を定義し、また、＜３  ｛３，４｝  ３  １  ＊  ０＞と＜３  ＊  ３  １  ｛０，１｝  ０＞とを掛け合わせることによって（図４に示すペア２）、さらに詳細化した詳細化パターン＜３  ｛３，４｝  ３  １  ｛０，１｝  ０＞を定義する。系列パターンの出現数は、任意項目値を選択項目値に置き換える手続きによって単調に減少するため、これ以外の選択項目値への置き換えによって得られる系列パターンの出現数は閾値未満であるから、文字列照合により出現数を計数するまでもなく除外することが可能である。
【００８６】
そして、系列パターン発見部１５０は、生成した系列パターン（＜３  ｛０，１｝  ３  １  ｛０，１｝  ０＞および＜３  ｛３，４｝  ３  １  ｛０，１｝  ０＞）と、系列データ記憶部１１０に記憶された系列データとを、例えば、拡張Ｓｈｉｆｔ−ＡＮＤ法などの文字列照合アルゴリズムを用いて再度照合し、系列パターンがマッチする系列パターンの出現数をまとめて計数する。
【００８７】
なお、かかる系列パターン発見部１５０による系列パターン発見処理の詳細については、図６を用いて後に説明する。
【００８８】
このように、系列パターン発見部１５０が、系列データ記憶部１１０により記憶された系列データを読み出すとともに、拡張Ｓｈｉｆｔ−Ａｎｄ法による文字列照合アルゴリズムを用いて、系列データがマッチする系列パターンの出現数を計数するので、まずは一般化パターンの出現数を計数し、所定の閾値を用いて一般化パターンを絞り込んだ後に、絞り込んだ一般化パターンに含まれる任意項目値の一つを選択項目値に置き換えて系列パターンを逐次生成し、さらに、一つずつ任意項目値を選択項目値に置き換えることによって系列パターンを段階的に詳細化し、その都度、所定の閾値を用いて、計数する必要のない系列パターンを排除してゆくことが可能となり、系列パターンの出現数を効率良く計数して系列パターンの抽出にかかる処理時間を短縮することができる。
【００８９】
パターン出力部１６０は、系列パターン発見部１５０によって計数された出現数が所定の閾値以上である系列パターンを抽出し、抽出した系列パターンを抽出結果の系列パターンとして、例えばディスプレイ装置などの出力装置に出力する処理部である。
【００９０】
次に、本実施例１に係る系列パターン計数部１４０による一般化パターン計数処理の処理手順について説明する。図５は、本実施例１に係る系列パターン計数部１４０による一般化パターン計数処理の処理手順を示すフローチャートである。同図に示すように、まず、テンプレート生成部１２０が、テンプレートＸを１つ生成する（ステップＳ１０１）。
【００９１】
テンプレートＸが生成された場合（ステップＳ１０２，Ｙｅｓ）は、写像生成部１３０が、テンプレートＸに基づいて、系列データＤから一般化パターン番号を算出するための写像ｆX（Ｄ）を生成する（ステップＳ１０３）。
【００９２】
そして、系列パターン計数部１４０が、パターンテーブルのパターンカウンタを全てクリアする（ステップＳ１０４）。パターンテーブルをクリアした後、系列パターン計数部１４０は、系列データ記憶部１１０から系列データＤを１つ取り出す（ステップＳ１０５）。
【００９３】
系列データＤが取り出せた場合は（ステップＳ１０６，Ｎｏ）、系列パターン計数部１４０は、写像生成部１３０によって生成された写像ｆX（Ｄ）を用いて、取り出した系列データＤから一般化パターン番号を算出し（ステップＳ１０７）、さらに、算出した一般化パターン番号に対応するパターンカウンタをインクリメントする（ステップＳ１０８）。その後、系列パターン計数部１４０は、ステップＳ１０５に戻って、系列データ記憶部１１０から次の系列データＤを取り出し、ステップＳ１０７およびＳ１０８の処理を行う。系列パターン計数部１４０は、系列データ記憶部１１０から系列データＤが取り出せなくなるまで、これらの処理を繰り返す。
【００９４】
そして、系列データ記憶部１１０から系列データＤが取り出せなかった場合、すなわち、系列データ記憶部１１０に記憶されている全ての系列データＤの取出しがすでに完了している場合、系列パターン計数部１４０は、ステップＳ１０１に戻って、次のテンプレートＸを生成し、全てのテンプレートＸを生成するまで、ステップＳ１０２以降の処理を繰り返す。
【００９５】
そして、全てのテンプレートＸを生成した後、系列パターン計数部１４０は、この一般化パターン計数処理を終了する（ステップＳ１０２，Ｎｏ）。
【００９６】
このように、系列データから一般化パターン番号を算出するための一般化写像を写像生成部１３０があらかじめ生成し、系列パターン計数部１４０が、系列データ記憶部１１０に記憶された系列データを順次読み出すとともに一般化写像を用いて一般化パターン番号を算出することによって、効率良く系列パターン（一般化パターン）の出現数を計数することができる。
【００９７】
このように、系列パターン計数部１４０が、一般化パターンを一意に識別する一般化パターン番号と、一般化パターンの出現数を計数するためのパターンカウンタとを対応付けた一般化パターンテーブルを備え、写像生成部１３０が、系列データから一般化パターン番号を導出するための写像である一般化写像を生成し、系列パターン計数部１４０が、系列データ記憶部１１０により記憶されている系列データを順次読み出すとともに、読み出した系列データから一般化写像を用いて一般化パターン番号を導出し、一般化パターンテーブルの、導出した一般化パターン番号に対応する一般化パターンカウンタをカウントアップするので、頻出する可能性のある系列パターン群を生成するたびに系列データを全て読み出して当該一般化パターンの出現数を計数するのではなく、一般化写像を生成するたびに系列データを全て読み出すことによって、同じ写像で表される全ての系列パターンの出現数が一括して計数される。この結果、候補パターン数の爆発に影響されず、決まった回数だけ系列データを走査すれば頻出する一般化パターン発見が完了するので、処理時間が閾値に影響されないという効果を奏する。
【００９８】
次に、系列パターン発見部部１５０による系列パターン発見処理の処理手順について説明する。図６は、系列パターン発見部１５０による系列パターン発見処理の処理手順を示すフローチャートである。同図に示すように、系列パターン発見部１５０は、まず、系列パターン計数部１４０により計数されたパターンカウンタが所定の閾値以上である一般化パターンＰを取得する（ステップＳ２０１）。
【００９９】
そして、系列パターン発見部１５０は、一般化パターンＰが取得できた場合は（ステップＳ２０２，Ｙｅｓ）、変数ｉに「０」を設定し（ステップＳ２０３）、取得した一般化パターンＰ１つだけを含む集合を系列パターン集合Ｌ0として保持し（ステップＳ２０４）、さらに、一般化パターンＰにマッチする全ての系列データ（以降、系列データＤPとする）を系列データ記憶部１１０から抽出する（ステップＳ２０５）。
【０１００】
その後、系列パターン発見部１５０は、変数ｉに「１」を加算し（ステップＳ２０６）、変数ｉが一般化パターンに含まれる任意項目値または選択項目値の数ｋより小さかった場合は（ステップＳ２０７，Ｙｅｓ）、保持している系列パターン集合Ｌi-1に含まれる任意項目値のいずれか一つに選択項目値を設定することによって、系列パターンを生成する（ステップＳ２０８）。ここで、例えば、選択項目値が３種類である場合は、集合Ｌｉ−１に属する系列パターンひとつあたり｜Πm｜×（ｋ−ｉ＋１）通りの系列パターンが生成される。
【０１０１】
そして、系列パターン発見部１５０は、生成した系列パターンと、系列データＤPとを、例えば、拡張Ｓｈｉｆｔ−ＡＮＤ法などの文字列照合アルゴリズムを用いて照合することにより、その出現数をまとめて計数する（ステップＳ２０９）。
【０１０２】
そして、系列パターン発見部１５０は、計数した出現数が所定の閾値を超える系列パターンを抽出し、抽出した頻出系列パターンを系列パターン集合Ｌiとして保持する（ステップＳ２１０）。
【０１０３】
この後、系列パターン発見部１５０は、変数ｉが一般化パターンに含まれる任意項目値または選択項目値の数ｋ以上となるまで（ステップＳ２０７，Ｎｏ）、変数ｉをカウントアップしながら、系列パターン集合Ｌiの抽出を繰り返す。
【０１０４】
変数ｉが一般化パターンに含まれる任意項目値または選択項目値の数ｋ以上となった場合は、系列パターン発見部１５０は、それまでに抽出していた系列パターン集合Ｌ0〜Ｌk-1をまとめ、集合Ｌ（Ｐ）として保持する（ステップＳ２１１）。
【０１０５】
そして、系列パターン発見部１５０は、ステップＳ２０１に戻って、出現数が所定の閾値以上である一般化パターンをさらに取得し、出現数が所定の閾値以上である全ての一般化パターンを取得し終わるまで、ステップＳ２０１以降の処理を繰り返し行う。
【０１０６】
そして、全ての一般化パターンについて処理を行った後、系列パターン発見部１５０は、この系列パターン発見処理を終了し、保存している全ての系列パターン集合Ｌ（Ｐ）を抽出結果として、パターン出力部１６０を介して出力する（ステップＳ２１２）。
【０１０７】
上述してきたように、本実施例１では、系列データ記憶部１１０が、系列パターン抽出の対象となる系列データを記憶し、テンプレート生成部１２０が、任意の値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、系列パターン計数部１４０が、記憶している系列データを順次読み出すとともに、各一般化パターンにマッチする系列データの数を一般化パターン出現数として計数し、その上で、系列パターン発見部１５０が、計数した一般化パターン出現数が所定の閾値以上である一般化パターンを抽出し、抽出した一般化パターンに含まれる任意項目値に選択項目値を設定した系列パターンを定義し、記憶している系列データを順次読み出すとともに、各系列パターンにマッチする系列データの数を系列パターン出現数として計数し、系列パターン出力部１６０が、系列パターン発見部１５０により計数した系列パターン出現数が所定の閾値以上である系列パターンを抽出結果として出力することとしたので、まずは大まかな条件で一般化パターンの出現数を計数し、所定の閾値で絞り込んだ上で、さらに詳細な条件で系列パターンの出現数を計数することが可能となる。このように、一般化パターンの出現数を効率良く計数することによって、系列パターンの抽出にかかる処理時間を短縮することができる。
【０１０８】
また、写像生成部１３０が、系列データに含まれる項目値を変換することによって一般化パターンを一意に識別する一般化パターン番号を導出する一般化写像を生成し、系列パターン計数部１４０が、一般化パターンと、一般化写像を用いて導出される一般化パターン番号と、一般化パターンにマッチする系列データの数を計数するパターンカウンタとを一般化パターンごとに対応付けたパターンテーブルを生成し、系列パターン計数部１４０が、系列データを順次読み出すとともに、一般化写像を用いて一般化パターン番号を導出し、導出した一般化パターン番号に基づいてパターンテーブルのパターンカウンタを計数することとしたので、読み出した系列データがマッチする一般化パターンを容易に判別することが可能となり、この結果、一般化パターンの出現数を効率良く計数することによって、一般化パターンの抽出にかかる処理時間を短縮することができる。
【実施例２】
【０１０９】
ところで、上記実施例１では、系列データを読み込み、所定の設定値に基づいて一般化パターンごとに生成した一般化写像を用いて各一般化パターンの出現数を計数し、出現数が所定の閾値以上である一般化パターンを抽出した後に、任意項目値に選択項目値を設定することによって一般化パターンを詳細化した系列パターンを生成し、再度系列データを読み込んで、系列パターンの出現数を計数し、所定の閾値によって系列パターンを絞り込むことによって、頻出する系列パターンを発見する場合を説明したが、一般化写像を生成するのと同時に詳細化パターンの写像を生成し、これら２つの写像を組み合わせて用いることによって、詳細化パターンの出現数のみを計数し、頻出の詳細化パターンのみを発見するようにしてもよい。
【０１１０】
そこで、本実施例２では、２つの写像を組み合わせて用いることによって、詳細化パターンの出現数のみを計数する場合について説明する。
【０１１１】
まず、本実施例２に係る系列パターン発見装置の構成について説明する。なお、ここでは説明の便宜上、図１に示した各部と同様の役割を果たす機能部については同一符号を付すこととしてその詳細な説明を省略する。図７は、本実施例２に係る系列パターン発見装置の構成を示す機能ブロック図である。同図に示すように、この系列パターン発見装置２００は、系列データ記憶部１１０と、テンプレート生成部１２０と、写像生成部２３０と、系列パターン計数部２４０と、系列パターン出力部１６０とを有する。
【０１１２】
写像生成部２３０は、テンプレート生成部１２０によって生成されたテンプレートに基づいて、系列データから一般化パターン番号を算出するための写像（以下、一般化写像）を生成し、また、所定の選択項目値から詳細化パターン番号を算出するための写像（以下、詳細化写像）を生成する処理部である。ここで、一般化パターン番号とは、テンプレートによって定義される一般化パターンを一意に識別するための識別番号であり、詳細化パターン番号とは、所定の選択項目値に基づいて一般化パターンを詳細化して得られる詳細化パターンを一意に識別するための識別番号である。なお、ここで生成する一般化写像については、実施例１で示した写像生成部１３０において説明した一般化写像と同様であるため説明を省略し、ここでは、詳細化写像の生成方法について説明する。
【０１１３】
写像生成部２３０は、まず、テンプレート生成部１２０により生成されたテンプレートＸを取得し、取得したテンプレートＸに基づいて一般化写像ｆX（Ｄ）を生成した後に、詳細化写像ｇX（Ｄ）を生成する。
【０１１４】
例えば、以下に示すテンプレートＸEに基づいて生成する詳細化写像ｇXE（Ｄ）を、以下の式で定義する。
【０１１５】
【数８】
0004711863.tif 000009
【０１１６】
上記の式（ＸEの式）において、Σは、「０」，「１」，「２」，「３」，「４」のいずれかが設定されることを表している（数式（２）のΣを参照）。また、［１］，［０］は、任意項目値または選択項目値を表す記号「＊」に対して、右から左へ順番に付与した０から始まる通番であり、上記ｇXE（ＤE）の式のｄ[1]，ｄ[0]は、それぞれ、テンプレートＸEで定義された＊[1]，＊[0]と同じ位置にある系列データＤEの項目値、すなわち、ｄ4，ｄ1を示している。
【０１１７】
また、上記ｍ（ｘ）の式は、項目値ｘに対して、選択項目値の集合Πmに含まれる選択項目値（数式（２）を参照）に応じて０から始まる通番を割り当てるための式であり、項目値ｘが選択項目値｛０，１｝に含まれる場合はｍ（ｘ）＝「０」となり、ｘが｛２｝に含まれる場合はｍ（ｘ）＝「１」となり、ｘが｛３，４｝に含まれる場合はｍ（ｘ）＝「２」となることを示している。例えば、ｘ＝ｄ4＝１であった場合は、ｍ（ｄ4）＝０となり、ｘ＝ｄ1＝４であった場合は、ｍ（ｄ1）＝２となる。
【０１１８】
また、上記ｇXE（ＤE）の式において、各項目値ｍ（ｄ4），ｍ（ｄ1）に乗じている３j（ｊ＝１，０）は、「３」が、選択項目値の集合Πmに含まれる選択項目値の数（｛０，１｝，｛２｝，｛３，４｝の３つ）で決められ（数式（２）のΠmを参照）、指数ｊが、テンプレートＸEにおいて任意項目値または選択項目値を表す記号「＊」に付与した通番（［１］，［０］）で決められる。
【０１１９】
この写像例ｇXE（ＤE）により、例えば、系列データが
【０１２０】
ＤE＝＜３  １  ３  １  ４  ０＞
【０１２１】
であった場合は、
【０１２２】
ｇXE（ＤE）＝０×３1＋２×３0
＝２
【０１２３】
となり、詳細化パターン番号は「２」となる。
【０１２４】
なお、ここでは、抽出する系列パターンの長さｌが「６」、抽出する系列パターンに含まれる任意項目値または選択項目値の数ｋが「２」、選択項目値の集合Πmに含まれる選択項目値の数が「３」である場合の詳細化写像の生成について説明したが、本発明はこれに限定されるものではなく、上述したように、詳細化写像は、ｌ、ｋおよびΠmに設定される値に応じて、適宜生成されるものである。
【０１２５】
系列パターン計数部２４０は、系列データ記憶部１１０に記憶された系列データを読み出し、写像生成部２３０により生成された一般化写像および詳細化写像を用いて、読み出した系列データがマッチする詳細化パターンの出現数を計数する処理部である。具体的には、この系列パターン計数部２４０は、テンプレート生成部１２０で生成されたテンプレートＸごとに、一般化パターン番号と詳細化パターン参照ポインタとを対応付けたパターンテーブルを生成する。ここで、詳細化パターン参照ポインタとは、一般化パターン番号と、後述する詳細化パターンテーブルとを対応付けるためのポインタである。ここで、一般化パターン番号とは、前述した一般化写像ｆX（Ｄ）によって導出される一般化パターン番号に対応するものであり、０から始まる通番となる。また、パターンカウンタは、一般化パターン番号と詳細化パターン番号の組ごとに、系列データ記憶部１１０に記憶された系列データにおける、詳細化パターンの出現数を計数するためのカウンタである。
【０１２６】
例えば、前述したテンプレート
【０１２７】
ＸE＝＜ｘ5  ＊  ｘ3  ｘ2  ＊  ｘ0＞
【０１２８】
に対するパターンテーブルでは、５4（＝６２５）個のパターン番号、すなわち「０」〜「６２４」のパターン番号と、パターンカウンタとが対応付けられている。そして、かかるパターン番号およびパターンカウンタの数は、テンプレートＸEから生成される一般化パターンのパターン数と同数となる。
【０１２９】
さらに、系列パターン計数部２４０は、パターンテーブルに設定した一般化パターン番号ごとに、詳細化パターン番号と詳細化パターンカウンタとを対応付けた詳細化パターンテーブルを備える。詳細化パターンテーブルは、前述した詳細化パターン参照ポインタによって、パターンテーブルの一般化パターン番号ごとに対応付けられる。
【０１３０】
ここで、詳細化パターン番号とは、前述した詳細化写像ｇXE（ＤE）によって導出される詳細化パターン番号に対応するものであり、０から始まる通番となる。また、詳細化パターンカウンタは、詳細化パターン番号ごとに、系列データ記憶部１１０に記憶された系列データにおける、詳細化パターンの出現数を計数するためのカウンタである。
【０１３１】
図８は、本実施例２に係る系列パターン計数部２４０によって用いられる詳細化パターンテーブルの一例を示す図である。例えば、同図に示すように、前述したパターンテンプレート
【０１３２】
ＸE＝＜ｘ5  ＊  ｘ3  ｘ2  ＊  ｘ0＞
【０１３３】
に対するパターンテーブルに含まれるパターン場の具４５５に対する詳細化パターンテーブルでは、３2（＝９）個の詳細化パターン番号、すなわち「０」〜「８」の詳細化パターン番号と、詳細化パターンカウンタとが対応付けられている。そして、かかる詳細化パターン番号および詳細化パターンカウンタの数は、テンプレートＸEから生成される詳細化パターンのパターン数と同数となる。
【０１３４】
系列パターン計数部２４０は、詳細化パターンテーブルの詳細化パターンカウンタを初期化（「０」を設定）した後に、系列データ記憶部１１０により記憶された系列データＤを順次読み出し、写像生成部２３０により生成された一般化写像ｆX（Ｄ）および詳細化写像ｇX（Ｄ）を用いて詳細化パターン番号を導出し、導出した詳細化パターン番号に対応する詳細化パターンテーブルの詳細化パターンカウンタに「１」を加算する。
【０１３５】
例えば、前述した系列データ
【０１３６】
ＤE＝＜３  １  ３  １  ４  ０＞
【０１３７】
を読み出した場合は、
【０１３８】
ｆXE（ＤE）＝４５５  ，  ｇXE（ＤE）＝２
【０１３９】
となることより、系列パターン計数部２４０は、パターンテーブルの、一般化パターン番号「４５５」に対応する詳細化パターン参照ポインタを参照し、そのポインタで対応付けられた詳細化パターンテーブルの、詳細化パターン番号「２」に対応する詳細化パターンカウンタに「１」を加算する（図３に示すカウント２）。
【０１４０】
こうして、パターン計数部２４０は、テンプレート生成部１２０により生成された全てのテンプレートに対して、上述したパターンテーブルおよび詳細化パターンテーブルの生成と、一般化写像および詳細化写像を用いた詳細化パターンカウンタの加算とを行う。
【０１４１】
系列パターン出力部１６０は、系列パターン計数部２４０によって生成された詳細化パターンテーブルから、詳細化パターンカウンタが所定の閾値以上である詳細化パターンを抽出し、抽出した詳細化パターンを抽出結果として、例えばディスプレイ装置などの出力装置に出力する処理部である。
【０１４２】
上述してきたように、本実施例２では、写像生成部２３０が、系列データに含まれる項目値から詳細化パターンを一意に識別する詳細化パターン番号を導出する詳細化写像を生成し、系列パターン計数部２４０が、詳細化パターンと、詳細化写像を用いて導出される詳細化パターン番号と、詳細化パターンにマッチする系列データの数を計数する詳細化パターンカウンタとを詳細化パターンごとに対応付けた詳細化パターンテーブルをクリアし、記憶している系列データを順次読み出すとともに、詳細化写像を用いて詳細化パターン番号を導出し、導出した詳細化パターン番号に基づいて詳細化パターンテーブルの詳細化パターンカウンタを計数することとしたので、頻出する可能性のある系列パターン群を生成するたびに系列データを全て読み出して当該系列パターンの出現数を計数するのではなく、一般化写像および詳細化写像を生成するたびに系列データを全て読み出すことによって、同じ写像の組で表される全ての詳細化パターンの出現数が一括して計数される。この結果、候補パターン数の爆発に影響されず、決まった回数だけ系列データを走査すれば頻出する一般化パターン発見が完了するので、処理時間が閾値に影響されないという効果を奏する。
【０１４３】
なお、本実施例１および２において図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１４４】
また、本実施例１および２では、系列パターン発見装置１００および２００について説明したが、系列パターン発見装置１００および２００が有する構成をソフトウェアによって実現することで、同様の機能を有する系列パターン発見プログラムを得ることができる。そこで、この系列パターン発見プログラムを実行するコンピュータについて説明する。
【０１４５】
図９は、本実施例１および２に係る系列パターン発見プログラムを実行するコンピュータの構成を示す機能ブロック図である。同図に示すように、このコンピュータ３００は、ＲＡＭ３１０と、ＣＰＵ３２０と、ＨＤＤ３３０と、ＬＡＮインタフェース３４０と、入出力インタフェース３５０と、ＤＶＤドライブ３６０とを有する。
【０１４６】
ＲＡＭ３１０は、プログラムやプログラムの実行途中結果などを記憶するメモリであり、ＣＰＵ３２０は、ＲＡＭ３１０からプログラムを読み出して実行する中央処理装置である。
【０１４７】
ＨＤＤ３３０は、プログラムやデータを格納するディスク装置であり、ＬＡＮインタフェース３４０は、コンピュータ３００をＬＡＮ経由で他のコンピュータに接続するためのインタフェースである。
【０１４８】
入出力インタフェース３５０は、マウスやキーボードなどの入力装置および表示装置を接続するためのインタフェースであり、ＤＶＤドライブ３６０は、ＤＶＤの読み書きを行う装置である。
【０１４９】
そして、このコンピュータ３００において実行される系列パターン発見プログラム３１１は、ＤＶＤに記憶され、ＤＶＤドライブ３６０によってＤＶＤから読み出されてコンピュータ３００にインストールされる。
【０１５０】
あるいは、この系列パターン発見プログラム３１１は、ＬＡＮインタフェース３４０を介して接続された他のコンピュータシステムのデータベースなどに記憶され、これらのデータベースから読み出されてコンピュータ３００にインストールされる。
【０１５１】
そして、インストールされた系列パターン発見プログラム３１１は、ＨＤＤ３３０に記憶され、ＲＡＭ３１０に読み出されてＣＰＵ３２０によって系列パターン発見プロセス３２１として実行される。
【０１５２】
また、本実施例１および２では、日々の株価の終値を蓄積した時系列データから、その系列パターンを抽出する場合について説明したが、本発明はこれに限定されるものではなく、例えば小売店の売上データや、クレジットカードの利用履歴などの系列データから、その系列パターンを抽出する場合にも同様に適用することができる。
【０１５３】
（付記１）変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見プログラムであって、
系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶手順と、
任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶手順により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数手順と、
前記系列パターン計数手順により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶手順により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見手順と、
前記系列パターン発見手順により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力手順と、
をコンピュータに実行させることを特徴とする系列パターン発見プログラム。
【０１５４】
（付記２）前記系列パターン計数手順は、
前記系列パターンを一意に識別する一般化パターン番号と、該一般化パターンの出現数を計数するための一般化パターンカウンタとを対応付けた一般化パターンテーブルを備え、
前記系列データから前記一般化パターン番号を導出するための写像である一般化写像を生成する一般化写像生成手順と、
前記系列データ記憶手順により記憶された系列データを順次読み出すとともに、該読み出した系列データから前記一般化写像を用いて前記一般化パターン番号を導出し、前記一般化パターンテーブルの、該導出した一般化パターン番号に対応する一般化パターンカウンタをカウントアップする一般化パターンカウンタ計数手順と、
をコンピュータに実行させることを特徴とする付記１に記載の系列パターン発見プログラム。
【０１５５】
（付記３）前記系列パターン発見手順は、
前記系列パターン計数手順により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値の一つに選択項目値を設定することによって系列パターンを逐次生成し、
該逐次生成した系列パターンと、前記系列データ記憶手順により記憶された系列データとを照合することにより、該系列データがマッチする系列パターンの出現数を計数し、
該計数した出現数が所定の閾値以上である系列パターンを抽出し、該抽出した系列パターンに含まれる任意項目値の一つに選択項目値を設定することによってさらに系列パターンを詳細化し、
該詳細化した系列パターンと、前記系列データ記憶手順により記憶された系列データとを照合することにより、該系列データがマッチする系列パターンの出現数を計数し、
該系列パターンに含まれる全ての任意項目値に選択項目値を設定するまで、前記系列パターンの詳細化と、前記系列パターンの出現数の計数とを繰り返すことを特徴とする付記１または２に記載の系列パターン発見プログラム。
【０１５６】
（付記４）前記系列パターン計数手順は、
許容する値を選択した選択項目値と項目値のみを含んだ系列パターンを詳細化パターンとして定義し、
前記詳細化パターンを一意に識別する詳細化パターン番号と、該詳細化パターンの出現数を計数するための詳細化パターンカウンタとを対応付けた詳細化パターンテーブルを備え、
前記系列データに含まれる項目値から前記詳細化パターン番号を導出するための写像である詳細化写像を生成する詳細化写像生成手順と、
前記系列データ記憶手順により記憶された系列データを順次読み出すとともに、該読み出した系列データから前記詳細化写像を用いて前記詳細化パターン番号を導出し、前記詳細化パターンテーブルの、該導出した詳細化パターン番号に対応する詳細化パターンカウンタをカウントアップする詳細化パターンカウンタ計数手順と、
をコンピュータに実行させることを特徴とする付記１または２に記載の系列パターン発見プログラム。
【０１５７】
（付記５）前記系列データ記憶手順は、連続して変化する値を離散化し、該離散化した間隔ごとの値を項目値として順番に並べた系列データをパターン抽出の対照として記憶することを特徴とする付記１〜４のいずれか一つに記載の系列パターン発見プログラム。
【０１５８】
（付記６）前記系列パターン発見手順は、前記系列データ記憶手順により記憶された系列データを読み出すとともに、拡張Ｓｈｉｆｔ−Ａｎｄ法による文字列照合アルゴリズムを用いて、該系列データがマッチする前記詳細化パターンの出現数を計数することを特徴とする付記１、２または３に記載の系列パターン発見プログラム。
【０１５９】
（付記７）変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見方法であって、
系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶工程と、
任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶工程により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数工程と、
前記系列パターン計数工程により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶工程により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見工程と、
前記系列パターン発見工程により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力工程と、
を含んだことを特徴とする系列パターン発見方法。
【０１６０】
（付記８）変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出する系列パターン発見装置であって、
系列パターン抽出の対象となる系列データを記憶装置に記憶する系列データ記憶手段と、
任意の項目値を許容する任意項目値と項目値のみを含んだ系列パターンを一般化パターンとして定義し、前記系列データ記憶手段により記憶された系列データを順次読み出して、該系列データがマッチする一般化パターンの出現数を計数する系列パターン計数手段と、
前記系列パターン計数手段により計数された出現数が所定の閾値以上である一般化パターンを抽出し、該抽出した一般化パターンに含まれる任意項目値に、許容する値を選択した選択項目値を設定して系列パターンを逐次生成し、前記系列データ記憶手段により記憶された系列データを順次読み出して該系列パターンと照合することにより、該系列データがマッチする系列パターンの出現数を計数する系列パターン発見手段と、
前記系列パターン発見手段により計数された出現数が所定の閾値以上である系列パターンを抽出結果の系列パターンとして出力する系列パターン出力手段と、
を備えたことを特徴とする系列パターン発見装置。
【産業上の利用可能性】
【０１６１】
以上のように、本発明に係る系列パターン発見プログラム、系列パターン発見方法および系列パターン発見装置は、変動する項目値を順番に並べた系列データから、該系列データに頻繁に出現している系列パターンを抽出するに有用であり、特に、抽出対象のデータ量が膨大である場合に適している。
【図面の簡単な説明】
【０１６２】
【図１】系列パターンの抽出対象となる系列データの一例を示す図である。
【図２】本実施例１に係る系列パターン発見装置の構成を示す機能ブロック図である。
【図３】本実施例１に係るパターン計数部によって用いられるパターンテーブルの一例を示す図である。
【図４】本実施例１に係る詳細化パターン計数部による詳細化パターン計数処理の一例を示す図である。
【図５】本実施例１に係るパターン計数部による一般化パターン計数処理の処理手順を示すフローチャートである。
【図６】本実施例１に係る詳細化パターン計数部による詳細化パターン計数処理の処理手順を示すフローチャートである。
【図７】本実施例２に係る系列パターン発見装置の構成を示す機能ブロック図である。
【図８】本実施例２に係るパターン計数部によって用いられる詳細化パターンテーブルの一例を示す図である。
【図９】本実施例１および２に係る系列パターン発見プログラムを実行するコンピュータの構成を示す機能ブロック図である。
【符号の説明】
【０１６３】
１００、２００    系列パターン発見装置
１１０    系列データ記憶部
１２０    パターンテンプレート生成部
１３０、２３０    写像生成部
１４０、２４０    パターン計数部
１５０    詳細化パターン計数部
１６０、２６０    パターン出力部
３００    コンピュータ
３１０    ＲＡＭ
３１１    系列パターン発見プログラム
３２０    ＣＰＵ
３２１    系列パターン発見プロセス
３３０    ＨＤＤ
３４０    ＬＡＮインタフェース
３５０    入出力インタフェース
３６０    ＤＶＤドライブ
【図１】
0004711863.tif 000010
【図２】
0004711863.tif 000011
【図３】
0004711863.tif 000012
【図４】
0004711863.tif 000013
【図５】
0004711863.tif 000014
【図６】
0004711863.tif 000015
【図７】
0004711863.tif 000016
【図８】
0004711863.tif 000017
【図９】
0004711863.tif 000018