(57)【特許請求の範囲】
【請求項１】
第１系列データに繰り返し出現する標準パターンを第２系列データから抽出するパターン抽出装置であって、
前記第２系列データの指定区間のデータであるサンプルパターンに類似するパターンを前記第１系列データから抽出する抽出部と、
前記抽出部により抽出されたパターンが前記第１系列データに頻出する度合いを表す第１評価値と、前記抽出部により抽出されたパターンが前記第１系列データの系列方向において伸縮する度合いを表す第２評価値とを算出し、前記第１評価値および前記第２評価値から、前記標準パターンに対する前記サンプルパターンの適合度を算出する評価部と、
前記評価部により算出された適合度が閾値を超えていなければ、前記指定区間を変更して前記抽出部および前記評価部を再び動作させ、前記評価部により算出された適合度が前記閾値を超えていれば、前記指定区間を前記標準パターンに対応する区間として示す情報を出力する制御部と
を備えるパターン抽出装置。
【請求項２】
前記評価部は、前記第１評価値によって表される頻出の度合いが低いほど小さい値を前記標準パターンに対する前記サンプルパターンの適合度として算出する請求項１に記載のパターン抽出装置。
【請求項３】
前記評価部は、前記第２評価値によって表される伸縮の度合いが小さいほど大きい値を前記標準パターンに対する前記サンプルパターンの適合度として算出する請求項１または２に記載のパターン抽出装置。
【請求項４】
前記第１系列データおよび前記第２系列データをそれぞれ固定長のフレームに分割し、前記第１系列データのフレームと前記第２系列データのフレームとの組み合わせごとにフレーム間の類似度を表す行列である類似度行列を計算する計算部と、
前記計算部により計算された類似度行列から、前記指定区間に対応する部分行列を選択する選択部と
をさらに備え、
前記抽出部は、前記選択部により選択された部分行列において、前記第２系列データのフレームと前記第２系列データのフレームに類似する前記第１系列データのフレームとの組み合わせに対応する要素を辿る経路を計算し、
前記評価部は、前記抽出部により計算された経路から、前記第１評価値および前記第２評価値を算出する請求項１から３のいずれか１項に記載のパターン抽出装置。
【請求項５】
前記評価部は、前記抽出部により計算された経路が存在する前記第１系列データの区間同士の間隔が大きいほど低い度合いを表す値を前記第１評価値として算出する請求項４に記載のパターン抽出装置。
【請求項６】
前記評価部は、前記抽出部により計算された経路が存在する前記第１系列データの区間同士の重なりが大きいほど低い度合いを表す値を前記第１評価値として算出する請求項４または５に記載のパターン抽出装置。
【請求項７】
前記評価部は、前記抽出部により計算された経路が直線に近いほど小さい度合いを表す値を前記第２評価値として算出する請求項４から６のいずれか１項に記載のパターン抽出装置。
【請求項８】
第１系列データに繰り返し出現する標準パターンを第２系列データから抽出するパターン抽出方法であって、
抽出部が、前記第２系列データの指定区間のデータであるサンプルパターンに類似するパターンを前記第１系列データから抽出し、
評価部が、前記抽出部により抽出されたパターンが前記第１系列データに頻出する度合いを表す第１評価値と、前記抽出部により抽出されたパターンが前記第１系列データの系列方向において伸縮する度合いを表す第２評価値とを算出し、前記第１評価値および前記第２評価値から、前記標準パターンに対する前記サンプルパターンの適合度を算出し、
制御部が、前記評価部により算出された適合度が閾値を超えていなければ、前記指定区間を変更して前記抽出部および前記評価部を再び動作させ、前記評価部により算出された適合度が前記閾値を超えていれば、前記指定区間を前記標準パターンに対応する区間として示す情報を出力するパターン抽出方法。
【請求項９】
第１系列データに繰り返し出現する標準パターンを第２系列データから抽出するパターン抽出プログラムであって、
コンピュータに、
前記第２系列データの指定区間のデータであるサンプルパターンに類似するパターンを前記第１系列データから抽出する抽出処理と、
前記抽出処理により抽出されたパターンが前記第１系列データに頻出する度合いを表す第１評価値と、前記抽出処理により抽出されたパターンが前記第１系列データの系列方向において伸縮する度合いを表す第２評価値とを算出し、前記第１評価値および前記第２評価値から、前記標準パターンに対する前記サンプルパターンの適合度を算出する評価処理と、
前記評価処理により算出された適合度が閾値を超えていなければ、前記指定区間を変更して前記抽出処理および前記評価処理を再び実行し、前記評価処理により算出された適合度が前記閾値を超えていれば、前記指定区間を前記標準パターンに対応する区間として示す情報を出力する制御処理と
を実行させるパターン抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン抽出装置、パターン抽出方法およびパターン抽出プログラムに関するものである。
【背景技術】
【０００２】
特許文献１には、時系列データを特徴区間に分割し、特徴区間の類似度に応じて、特徴区間を階層的にクラスタリングする技術が記載されている。この技術では、「区間Ａ」と「区間Ｂ」との間の類似度を算出する際、ＤＴＷを用いることで、「区間Ａ」のパターンを「区間Ｂ」のパターンに重ねる際に発生する部分的伸縮の大きさによらない計算を行っている。「ＤＴＷ」は、Ｄｙｎａｍｉｃ  Ｔｉｍｅ  Ｗａｒｐｉｎｇの略語である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開第２０１３／０５１１０１号
【特許文献２】特開２００８−１３４７０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１に記載の技術では、時系列データの系列方向における部分的伸縮の大小を考慮した適合度計算ができない。これは、特定パターンの繰り返しとして表現される入力系列データから、標準的な頻出区間を選出できないことを意味する。ここで、標準的な頻出区間とは、入力系列データを頻出パターンの繰り返しとして表現するとき、系列方向の部分的伸縮がより小さくて済む区間を意味する。すなわち、標準的な頻出区間とは、系列データにおいて、あるパターンが系列方向の伸縮によらず多数の区間に出現しているとき、それら多数の区間のうち、そのパターンの伸縮が小さい区間のことである。【０００５】
本発明は、系列データからの標準的な頻出区間の選出を可能にすることを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一態様に係るパターン抽出装置は、
第１系列データに繰り返し出現する標準パターンを第２系列データから抽出するパターン抽出装置であって、
前記第２系列データの指定区間のデータであるサンプルパターンに類似するパターンを前記第１系列データから抽出する抽出部と、
前記抽出部により抽出されたパターンが前記第１系列データに頻出する度合いを表す第１評価値と、前記抽出部により抽出されたパターンが前記第１系列データの系列方向において伸縮する度合いを表す第２評価値とを算出し、前記第１評価値および前記第２評価値から、前記標準パターンに対する前記サンプルパターンの適合度を算出する評価部と、
前記評価部により算出された適合度が閾値を超えていなければ、前記指定区間を変更して前記抽出部および前記評価部を再び動作させ、前記評価部により算出された適合度が前記閾値を超えていれば、前記指定区間を前記標準パターンに対応する区間として示す情報を出力する制御部とを備える。
【発明の効果】
【０００７】
本発明では、系列データの１つ以上の区間について、各区間のデータに類似するパターンが系列データに頻出する度合いと、そのパターンが系列データの系列方向において伸縮する度合いとが評価される。そして、両方の評価の結果から、各区間が標準的な頻出区間であるかどうかが判定される。このような判定の手順によって、系列データからの標準的な頻出区間の選出が可能になる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１に係るパターン抽出装置の構成を示すブロック図。
【図２】実施の形態１に係るパターン抽出装置の計算部の動作を示すフローチャート。
【図３】実施の形態１に係る類似度行列の例を示す図。
【図４】実施の形態１に係るパターン抽出装置の解析部の動作を示すフローチャート。
【図５】実施の形態１に係る部分類似度行列の例を示す図。
【図６】実施の形態１に係る経路の例を示す図。
【図７】実施の形態１に係る第１評価値の算出の例を示す図。
【図８】実施の形態１に係る第２評価値の算出の例を示す図。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態について、図を用いて説明する。各図中、同一または相当する部分には、同一符号を付している。実施の形態の説明において、同一または相当する部分については、説明を適宜省略または簡略化する。なお、本発明は、以下に説明する実施の形態に限定されるものではなく、必要に応じて種々の変更が可能である。例えば、以下に説明する実施の形態は、部分的に実施されても構わない。
【００１０】
実施の形態１．
本実施の形態について、図１から図８を用いて説明する。
【００１１】
＊＊＊構成の説明＊＊＊
図１を参照して、本実施の形態に係るパターン抽出装置１０の構成を説明する。
【００１２】
パターン抽出装置１０は、コンピュータである。パターン抽出装置１０は、プロセッサ１１を備えるとともに、メモリ１２、入力インタフェース１３および出力インタフェース１４といった他のハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１３】
パターン抽出装置１０は、機能要素として、計算部２１と、選択部２２と、抽出部２３と、評価部２４と、制御部２５とを備える。選択部２２、抽出部２３、評価部２４および制御部２５は、解析部２６を構成する。計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の機能は、ソフトウェアにより実現される。
【００１４】
プロセッサ１１は、各種処理を行うＩＣである。「ＩＣ」は、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略語である。プロセッサ１１は、例えば、ＣＰＵである。「ＣＰＵ」は、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略語である。
【００１５】
メモリ１２は、例えば、フラッシュメモリまたはＲＡＭである。「ＲＡＭ」は、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略語である。
【００１６】
入力インタフェース１３は、例えば、一定のサンプリング周期で計測を行うセンサからの系列データの出力を受け付けるインタフェースである。
【００１７】
出力インタフェース１４は、例えば、解析結果をファイルへ書き出すインタフェース、または、解析結果を画面に表示するインタフェースである。
【００１８】
メモリ１２には、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の機能を実現するプログラムであるパターン抽出プログラムが記憶されている。パターン抽出プログラムは、プロセッサ１１に読み込まれ、プロセッサ１１によって実行される。メモリ１２には、ＯＳも記憶されている。「ＯＳ」は、Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍの略語である。プロセッサ１１は、ＯＳを実行しながら、パターン抽出プログラムを実行する。なお、パターン抽出プログラムの一部または全部がＯＳに組み込まれていてもよい。
【００１９】
パターン抽出プログラムおよびＯＳは、補助記憶装置に記憶されていてもよい。補助記憶装置は、例えば、フラッシュメモリまたはＨＤＤである。「ＨＤＤ」は、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略語である。補助記憶装置に記憶されているパターン抽出プログラムおよびＯＳは、メモリ１２にロードされ、プロセッサ１１によって実行される。
【００２０】
パターン抽出装置１０は、プロセッサ１１を代替する複数のプロセッサを備えていてもよい。これら複数のプロセッサは、パターン抽出プログラムの実行を分担する。それぞれのプロセッサは、プロセッサ１１と同じように、各種処理を行うＩＣである。
【００２１】
計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の処理の結果を示す情報、データ、信号値および変数値は、メモリ１２、補助記憶装置、または、プロセッサ１１内のレジスタまたはキャッシュメモリに記憶される。
【００２２】
パターン抽出プログラムは、磁気ディスクおよび光ディスクといった可搬記録媒体に記憶されてもよい。
【００２３】
＊＊＊動作の説明＊＊＊
図１から図８を参照して、本実施の形態に係るパターン抽出装置１０の動作を説明する。パターン抽出装置１０の動作は、本実施の形態に係るパターン抽出方法に相当する。
【００２４】
パターン抽出装置１０は、以下に説明する動作によって、第１系列データ３１ａに繰り返し出現する標準パターンを第２系列データ３１ｂから抽出する。本実施の形態では、パターン抽出装置１０に入力される系列データ３１が、第１系列データ３１ａおよび第２系列データ３１ｂの両方として扱われる。すなわち、第１系列データ３１ａおよび第２系列データ３１ｂは、同一の系列データ３１である。なお、第１系列データ３１ａおよび第２系列データ３１ｂが同一の系列データ３１であることは必須ではない。第１系列データ３１ａおよび第２系列データ３１ｂは、別時刻に取得された系列データ３１のように、生じるパターンが同質の系列データ３１であればよい。
【００２５】
図１、図２および図３を参照して、計算部２１の動作を説明する。
【００２６】
ステップＳ１０１において、計算部２１は、入力インタフェース１３を介して系列データ３１を受け取る。
【００２７】
ステップＳ１０２において、計算部２１は、第１系列データ３１ａおよび第２系列データ３１ｂをそれぞれ固定長のフレームに分割する。計算部２１は、第１系列データ３１ａのフレームと第２系列データ３１ｂのフレームとの組み合わせごとにフレーム間の類似度ＳＩＭｉｊを表す行列である類似度行列３２を計算する。
【００２８】
具体的には、計算部２１は、第１系列データ３１ａおよび第２系列データ３１ｂの全フレーム組み合わせに関する類似度ＳＩＭｉｊを計算し、類似度行列３２を生成する。比較する第１系列データ３１ａおよび第２系列データ３１ｂは、ステップＳ１０１で受け取った、同一の系列データ３１である。図３では、具体例として、類似度行列３２を、類似度ＳＩＭｉｊの高低に基づいたコントラストを付けて表現している。図中、Ｔは、系列データ３１の系列方向を意味している。Ｔは、系列データ３１が時系列データである場合の時刻に相当する。
【００２９】
比較する２フレームの値ＦｉおよびＦｊに関する類似度ＳＩＭｉｊの計算方法としては、任意の方法を用いてよいが、本実施の形態では次式のようなコサイン類似度を取る方法が用いられる。
【数１】
0006556397.tif 000002
【００３０】
Ｆｉは、第２系列データ３１ｂのｉ番目のフレームが持つ値を意味する。Ｆｊは、第１系列データ３１ａのｊ番目のフレームが持つ値を意味する。ＦｉおよびＦｊとしては、１次元もしくは多次元のデータを許容する。
【００３１】
ステップＳ１０３において、計算部２１は、ステップＳ１０２で計算した類似度行列３２をメモリ１２に書き出す。
【００３２】
図１および図４から図８を参照して、解析部２６の動作を説明する。
【００３３】
ステップＳ２０１において、選択部２２は、類似度行列３２をメモリ１２から読み込む。
【００３４】
ステップＳ２０２において、選択部２２は、ステップＳ２０１で読み込んだ類似度行列３２に対して、制御部２５より出力された区間パラメータ３６が示す区間（Ｔｓｔａｒｔ，Ｔｅｎｄ）を設定する。区間パラメータ３６は、標準的な頻出区間の候補を指定するパラメータである。
【００３５】
ステップＳ２０３において、選択部２２は、計算部２１により計算された類似度行列３２から、指定区間に対応する部分行列である部分類似度行列３３を選択する。
【００３６】
具体的には、選択部２２は、ステップＳ２０１で読み込んだ類似度行列３２から、ステップＳ２０２で設定した区間（Ｔｓｔａｒｔ，Ｔｅｎｄ）に対応する部分行列を部分類似度行列３３として抽出する。選択部２２は、抽出した部分類似度行列３３をメモリ１２に書き出す。図５では、具体例として、類似度行列３２から区間パラメータ３６に基づいて部分類似度行列３３を抽出する処理を視覚的に表現している。
【００３７】
ステップＳ２０４において、抽出部２３は、第２系列データ３１ｂの指定区間のデータであるサンプルパターンに類似するパターンを第１系列データ３１ａから抽出する。サンプルパターンに類似するパターンを抽出する方法としては、第１系列データ３１ａの系列方向における伸縮を考慮した方法であれば、任意の方法を用いることができるが、本実施の形態では、部分類似度行列３３から経路３４を計算する方法が用いられる。すなわち、抽出部２３は、選択部２２により選択された部分類似度行列３３において、第２系列データ３１ｂのフレームと第２系列データ３１ｂのフレームに類似する第１系列データ３１ａのフレームとの組み合わせに対応する要素を辿る経路３４を計算する。経路３４は、第２系列データ３１ｂの指定区間のデータであるサンプルパターンと、第１系列データ３１ａとの間で類似フレームの対応関係を表す情報に相当する。ある経路３４について、始点と終点とで挟まれた、第１系列データ３１ａの系列方向に延びる区間を「類似区間」と呼ぶ。
【００３８】
具体的には、抽出部２３は、部分類似度行列３３をメモリ１２から読み出す。抽出部２３は、特許文献２に記載された「データストリーム監視方法」の部分シーケンスマッチング技術を適用した処理を実施することで、図６の例のような経路３４を抽出する。抽出部２３は、抽出した経路３４をメモリ１２に書き出す。
【００３９】
ここで、第１系列データ３１ａを長さｎの系列データＸ＝（ｘ１，ｘ２，・・・，ｘｎ）とする。第２系列データ３１ｂの指定区間のデータであるサンプルパターンを長さｍの系列データＹ＝（ｙ１，ｙ２，・・・，ｙｎ）とする。１≦ｓ＜ｅ≦ｎとする。抽出部２３は、系列データＸから系列データＹと類似する部分系列データを抽出する場合、系列データＸから取り得るすべての部分系列データＸ［ｓ：ｅ］＝（ｘｓ，ｘｓ＋１，・・・，ｘｅ）に対して系列データＹとのＤＴＷマッチングを適用することで、最適経路の候補を抽出する。抽出部２３は、候補抽出後、系列データＸの系列方向において近傍の経路が複数存在する場合は、各経路に付随する経路距離情報に基づいた選別を行い、より確からしい経路のみを抽出する。抽出部２３は、これを経路３４としてメモリ１２に書き出す。
【００４０】
ステップＳ２０５において、評価部２４は、抽出部２３により抽出されたパターンが第１系列データ３１ａに頻出する度合いを表す第１評価値Ｅ１を算出する。本実施の形態では、評価部２４は、抽出部２３により計算された経路３４から、第１評価値Ｅ１を算出する。
【００４１】
具体的には、評価部２４は、経路３４をメモリ１２から読み出し、次式を用いて第１評価値Ｅ１を計算する。
【数２】
0006556397.tif 000003
【００４２】
第１評価値Ｅ１は、図７に示すように、隣接した経路３４間の空隙、もしくは、重複区間の平均長さを表す評価値である。すなわち、第１評価値Ｅ１は、隣接した類似区間同士の平均間隔、もしくは、類似区間同士の重なりの平均幅を表す評価値である。第１評価値Ｅ１は、区間パラメータ３６で定まる指定区間が頻出区間に近いほど、小さな値を取る。これは、類似区間同士の空隙および重複についてペナルティが課されることを意味する。
【００４３】
このように、評価部２４は、抽出部２３により計算された経路３４が存在する第１系列データ３１ａの区間同士の間隔が大きいほど低い度合いを表す値を第１評価値Ｅ１として算出する。また、評価部２４は、抽出部２３により計算された経路３４が存在する第１系列データ３１ａの区間同士の重なりが大きいほど低い度合いを表す値を第１評価値Ｅ１として算出する。
【００４４】
ステップＳ２０６において、評価部２４は、抽出部２３により抽出されたパターンが第１系列データ３１ａの系列方向において伸縮する度合いを表す第２評価値Ｅ２を算出する。本実施の形態では、評価部２４は、抽出部２３により計算された経路３４から、第２評価値Ｅ２を算出する。
【００４５】
具体的には、評価部２４は、次式を用いて第２評価値Ｅ２を計算する。
【数３】
0006556397.tif 000004
【００４６】
第２評価値Ｅ２は、図８に示すように、各経路３４の始点および終点で定まる矩形領域の対角線と、経路３４そのものとで作られる領域の面積の平均を表す評価値である。すなわち、第１評価値Ｅ１は、各類似区間における対角線と経路３４とで挟まれた領域の平均面積を表す評価値である。第２評価値Ｅ２は、区間パラメータ３６で定まる指定区間が標準的であるほど、小さな値を取る。これは、経路３４の平滑度に応じて報酬が与えられることを意味する。
【００４７】
このように、評価部２４は、抽出部２３により計算された経路３４が直線に近いほど小さい度合いを表す値を第２評価値Ｅ２として算出する。
【００４８】
ステップＳ２０７において、評価部２４は、第１評価値Ｅ１および第２評価値Ｅ２から、標準パターンに対するサンプルパターンの適合度３５を算出する。
【００４９】
具体的には、評価部２４は、次式を用いてＳｃｏｒｅ（Ｔｓｔａｒｔ，Ｔｅｎｄ）を計算し、制御部２５に適合度として出力する。
【数４】
0006556397.tif 000005
【００５０】
αは、第１評価値Ｅ１に対してあらかじめ設定されたパラメータである。βは、第２評価値Ｅ２に対してあらかじめ設定されたパラメータである。δは、ゼロ除算防止用の定数である。
【００５１】
このように、評価部２４は、第１評価値Ｅ１によって表される頻出の度合いが低いほど小さい値を標準パターンに対するサンプルパターンの適合度３５として算出する。また、評価部２４は、第２評価値Ｅ２によって表される伸縮の度合いが小さいほど大きい値を標準パターンに対するサンプルパターンの適合度３５として算出する。
【００５２】
ステップＳ２０８において、制御部２５は、ステップＳ２０７で評価部２４から受け取った適合度３５を最大適合度と比較する。最大適合度の初期値は、最小値である。適合度３５のほうが大きい場合、制御部２５は、ステップＳ２０９の更新処理を行う。適合度３５が最大適合度と同じであるか、最大適合度よりも小さい場合、制御部２５は、ステップＳ２１１の判定処理を行う。
【００５３】
ステップＳ２０９において、制御部２５は、最大適合度を、ステップＳ２０７で評価部２４から受け取った適合度３５で更新する。また、制御部２５は、最適区間パラメータ３７を、ステップＳ２０２で使用した区間パラメータ３６で更新する。最適区間パラメータ３７の初期値は、意味のない値である。
【００５４】
ステップＳ２１０において、制御部２５は、最大適合度を既定の閾値と比較する。最大適合度が閾値を上回っていれば、制御部２５は、ステップＳ２１２の出力処理を行う。最大適合度が閾値と同じであるか、閾値を下回っていれば、制御部２５は、ステップＳ２１１の判定処理を行う。
【００５５】
ステップＳ２１１において、制御部２５は、試行回数を既定の最大試行回数と比較する。試行回数とは、その時点までにステップＳ２０１からステップＳ２０７の処理が繰り返された回数のことである。解析部２６は、試行回数が最大試行回数を下回る場合に限り、ステップＳ２０１以降の処理を再び行う。この場合、制御部２５は、その時点までに未使用のパラメータを、次のステップＳ２０２で使用する区間パラメータ３６として設定する。すなわち、制御部２５は、区間パラメータ３６を変更する。なお、最初に設定される区間パラメータ３６は、任意のパラメータでよい。区間パラメータ３６を変更する方法も、任意の方法でよい。具体例として、最初に設定される区間パラメータ３６では、先頭の区間を指定し、その後、区間パラメータ３６の変更が必要になる度に、直前に指定した区間の次の区間を指定することができる。試行回数が最大試行回数と同じ場合、制御部２５は、ステップＳ２１２の出力処理を行う。
【００５６】
ステップＳ２１２において、制御部２５は、その時点での最適区間パラメータ３７を、解析結果を示す情報として出力インタフェース１４に出力する。
【００５７】
このように、制御部２５は、評価部２４により算出された適合度３５が閾値を超えていなければ、ステップＳ２０２で適用される指定区間を変更して抽出部２３および評価部２４を再び動作させる。一方、制御部２５は、評価部２４により算出された適合度３５が閾値を超えていれば、ステップＳ２０２で適用された指定区間を標準パターンに対応する区間として示す情報を出力する。
【００５８】
＊＊＊実施の形態の効果の説明＊＊＊
本実施の形態では、系列データ３１の１つ以上の区間について、各区間のデータに類似するパターンが系列データ３１に頻出する度合いと、そのパターンが系列データ３１の系列方向において伸縮する度合いとが評価される。そして、両方の評価の結果から、各区間が標準的な頻出区間であるかどうかが判定される。このような判定の手順によって、系列データ３１からの標準的な頻出区間の選出が可能になる。選出された区間のデータは、標準パターンに相当する。
【００５９】
本実施の形態によれば、入力された系列データ３１に含まれる他の同様なパターンを、系列方向においてより少ない部分的伸縮で近似表現できるパターンである標準パターンを、その系列データ３１の中から抽出することが可能になる。
【００６０】
本実施の形態では、頻出区間が抽出される際に、標準的でないことにペナルティを課すよう設計された適合度３５の計算が行われ、区間候補の選別が行われる。ここで、頻出区間が標準的でないということは、入力された系列データ３１に含まれる他の類似パターンを表現する際、系列データ３１の系列方向について大きな部分的伸縮を要することを意味する。
【００６１】
本実施の形態によれば、特定パターンの繰り返しとして表現可能な系列データ３１を、より少ない部分的伸縮で表現できる頻出区間の選定が可能となる。
【００６２】
＊＊＊他の構成＊＊＊
本実施の形態では、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の機能がソフトウェアにより実現されるが、変形例として、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の機能がソフトウェアとハードウェアとの組み合わせにより実現されてもよい。すなわち、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の機能の一部が専用の電子回路により実現され、残りがソフトウェアにより実現されてもよい。
【００６３】
専用の電子回路は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ、ＦＰＧＡまたはＡＳＩＣである。「ＧＡ」は、Ｇａｔｅ  Ａｒｒａｙの略語である。「ＦＰＧＡ」は、Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙの略語である。「ＡＳＩＣ」は、Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略語である。
【００６４】
プロセッサ１１、メモリ１２および専用の電子回路を、総称して「プロセッシングサーキットリ」という。つまり、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の機能がソフトウェアにより実現されるか、ソフトウェアとハードウェアとの組み合わせにより実現されるかに関わらず、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の機能は、プロセッシングサーキットリにより実現される。
【００６５】
パターン抽出装置１０の「装置」を「方法」に読み替え、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の「部」を「工程」に読み替えてもよい。あるいは、パターン抽出装置１０の「装置」を「プログラム」、「プログラムプロダクト」または「プログラムを記録したコンピュータ読取可能な媒体」に読み替え、計算部２１、選択部２２、抽出部２３、評価部２４および制御部２５の「部」を「手順」または「処理」に読み替えてもよい。
【符号の説明】
【００６６】
１０  パターン抽出装置、１１  プロセッサ、１２  メモリ、１３  入力インタフェース、１４  出力インタフェース、２１  計算部、２２  選択部、２３  抽出部、２４  評価部、２５  制御部、２６  解析部、３１  系列データ、３１ａ  第１系列データ、３１ｂ  第２系列データ、３２  類似度行列、３３  部分類似度行列、３４  経路、３５  適合度、３６  区間パラメータ、３７  最適区間パラメータ。
【図１】
0006556397.tif 000006
【図２】
0006556397.tif 000007
【図３】
0006556397.tif 000008
【図４】
0006556397.tif 000009
【図５】
0006556397.tif 000010
【図６】
0006556397.tif 000011
【図７】
0006556397.tif 000012
【図８】
0006556397.tif 000013