(57)【要約】【課題】距離計算の回数減少を図った類似時系列データ検出装置を提供する。【解決手段】  計算判断部１２は、事象ｉ，ｊについて新たに時系列データが受信され圧縮済時系列データＸｉ，Ｘｊに次元圧縮されたときに、事象ｉの過去の時期τの圧縮済時系列データＸｉτと圧縮済時系列データＸｉとの間の変化量の最大値max（ΔＳｉ）および最小値min（ΔＳｊ）を計算するとともに、事象ｊの過去の時期τの圧縮済時系列データＸｊτと圧縮済時系列データＸｊとの間の変化量の最大値max（ΔＳｊ）および最小値min（ΔＳｊ）を計算し、これらと、圧縮済時系列データＸｉτ，Ｘｊτ間の距離ｄτ（ｉ，ｊ）および閾値εとを用いた所定の条件が成立したときに距離計算を省略させる。【選択図】図１
2006119742.tif 000002
【特許請求の範囲】
【請求項１】
時系列的に採取された複数のデータからなる時系列データを受信した後に該時系列データに含まれるデータよりも新しいデータを含む時系列データを受信するようにして時系列データを逐次に受信するとともに当該時系列データにより表される事象ｉとは異なる事象ｊについての時系列データを逐次に受信し、受信した時系列データを逐次に次元圧縮し、事象ｉの時系列データから次元圧縮された圧縮済時系列データと、当該時系列データと同一時期の時系列データであって事象ｊの時系列データである時系列データから次元圧縮された圧縮済時系列データとの間の距離を計算し、当該距離が所定の閾値以下であるか否かを判定し、当該距離が当該閾値以下であると判定された場合は当該圧縮済時系列データに次元圧縮される前の時系列データとの間の距離を計算し、当該距離が所定の閥値以下である場合は時系列データ同士が類似していることとして所定の動作を行う類似時系列データ検出装置において、
過去に計算された圧縮済時系列データ間の距離が記憶される圧縮済時系列データ間距離保存手段と、
新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データが保存される圧縮済時系列データ保存手段と、
事象ｉ，ｊについて新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データと過去の所定の時期τの圧縮済時系列データとの間の変化量の最大値および最小値が保存される変化量保存手段と、
事象ｉ，ｊについて新たに時系列データが受信され圧縮済時系列データＸｉ，Ｘｊに次元圧縮されたときに、前記圧縮済時系列データ保存手段から事象ｉ，ｊの時期τの圧縮済時系列データＸｉτ，Ｘｊτを読み出し、前記変化量保存手段から事象ｉ，ｊの最大値および最小値を読み出し、これらを用いて、圧縮済時系列データＸｉτと圧縮済時系列データＸｉとの間の変化量の最大値max（ΔＳｉ）および最小値min（ΔＳｊ）を計算するとともに、圧縮済時系列データＸｊτと圧縮済時系列データＸｊとの間の変化量の最大値max（ΔＳｊ）および最小値min（ΔＳｊ）を計算する変化量計算手段と、
前記圧縮済時系列データ間距離保存手段から前記圧縮済時系列データＸｉτ，Ｘｊτ間の距離ｄτ（ｉ，ｊ）を読み出すとともに予め記憶された閾値εを読み出し、
条件１：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）−max（unmatch）
条件２：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＞ｄτ（ｉ，ｊ）＋max（unmatch）
条件３：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋min（unmatch）
条件４：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋max（unmatch）
ただし、条件１，２，３および４では、
max（unmatch）＝max（ΔＳｊ）＋ε
min（unmatch）＝max（０，min（ΔＳｊ）−ε）
条件５：ｄτ（ｉ，ｊ）≧εかつmax（ΔＳｉ）≦ −ｄτ（ｉ，ｊ）＋max（match）
ただし、条件５では、
max（match）＝max（０，ε−max（ΔＳｊ））
min（unmatch）＝０ 
ただし、各条件では、max（ａ，ｂ）はａとｂの内の大きい方
のいずれかの条件が満たされるか否かを判定し、いずれかの条件が満たされたときは、当該圧縮済時系列データＸｉ，Ｘｊに圧縮される前の各時系列データについて圧縮済時系列データ間の距離が閾値以下であるか否かの判定以降の処理を省略させる処理省略制御手段と
を備えることを特徴とする類似時系列データ検出装置。
【請求項２】
前記圧縮済時系列データ保存手段は、過去に次元圧縮された各圧縮済時系列データが逐次に保存されるものであり、
前記変化量保存手段を要せずかつ前記変化量計算手段に代えて、事象ｉ，ｊについて新たに各時系列データが受信および次元圧縮されたときに、前記圧縮済時系列データ保存手段から過去の同一時期の事象ｉ，ｊについての各圧縮済時系列データを読み出し、当該各次元圧縮された圧縮済時系列データと当該読み出された各圧縮済時系列データとの間の各変化量ΔＳｉ，ΔＳｊを計算する変化量計算手段を備え、
前記処理省略制御手段に代えて、当該処理省略制御手段が行う処理において、前記最大値max（ΔＳｉ）および最小値min（ΔＳｊ）に当該変化量ΔＳｉを用い、前記最大値max（ΔＳｊ）および最小値min（ΔＳｊ）に当該変化量ΔＳｊを用いる処理省略制御手段
を備えることを特徴とする請求項１記載の類似時系列データ検出装置。
【請求項３】
受信した各時系列データに対し該時系列データにより表される事象に関わる他のデータに応じたインデクスを付与し、前記圧縮済時系列データＸｉに次元圧縮される時系列データに付与されたインデクスと前記圧縮済時系列データＸｊに次元圧縮される時系列データに付与されたインデクスとが類似しているときは当該各時系列データについて次元圧縮以降の処理を省略することを特徴とする請求項１または２記載の類似時系列データ検出装置。
【請求項４】
時系列的に採取された複数のデータからなる時系列データを受信した後に該時系列データに含まれるデータよりも新しいデータを含む時系列データを受信するようにして時系列データを逐次に受信するとともに当該時系列データにより表される事象ｉとは異なる事象ｊについての時系列データを逐次に受信し、受信した時系列データを逐次に次元圧縮し、事象ｉの時系列データから次元圧縮された圧縮済時系列データと、当該時系列データと同一時期の時系列データであって事象ｊの時系列データである時系列データから次元圧縮された圧縮済時系列データとの間の距離を計算し、当該距離が所定の閾値以下であるか否かを判定し、当該距離が当該閾値以下であると判定された場合は当該圧縮済時系列データに次元圧縮される前の時系列データとの間の距離を計算し、当該距離が所定の閥値以下である場合は時系列データ同士が類似していることとして所定の動作を行う類似時系列データ検出装置における処理方法において、
前記類似時系列データ検出装置が、過去に計算された圧縮済時系列データ間の距離が記憶される圧縮済時系列データ間距離保存手段と、新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データが保存される圧縮済時系列データ保存手段と、事象ｉ，ｊについて新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データと過去の所定の時期τの圧縮済時系列データとの間の変化量の最大値および最小値が保存される変化量保存手段とを備え、
前記処理方法が、
事象ｉ，ｊについて新たに時系列データが受信され圧縮済時系列データＸｉ，Ｘｊに次元圧縮されたときに、前記圧縮済時系列データ保存手段から事象ｉ，ｊの時期τの圧縮済時系列データＸｉτ，Ｘｊτを読み出し、前記変化量保存手段から事象ｉ，ｊの最大値および最小値を読み出し、これらを用いて、圧縮済時系列データＸｉτと圧縮済時系列データＸｉとの間の変化量の最大値max（ΔＳｉ）および最小値min（ΔＳｊ）を計算するとともに、圧縮済時系列データＸｊτと圧縮済時系列データＸｊとの間の変化量の最大値max（ΔＳｊ）および最小値min（ΔＳｊ）を計算し、
前記圧縮済時系列データ間距離保存手段から前記圧縮済時系列データＸｉτ，Ｘｊτ間の距離ｄτ（ｉ，ｊ）を読み出すとともに予め記憶された閾値εを読み出し、
条件１：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）−max（unmatch）
条件２：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＞ｄτ（ｉ，ｊ）＋max（unmatch）
条件３：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋min（unmatch）
条件４：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋max（unmatch）
ただし、条件１，２，３および４では、
max（unmatch）＝max（ΔＳｊ）＋ε
min（unmatch）＝max（０，min（ΔＳｊ）−ε）
条件５：ｄτ（ｉ，ｊ）≧εかつmax（ΔＳｉ）≦ −ｄτ（ｉ，ｊ）＋max（match）
ただし、条件５では、
max（match）＝max（０，ε−max（ΔＳｊ））
min（unmatch）＝０ 
ただし、各条件では、max（ａ，ｂ）はａとｂの内の大きい方
のいずれかの条件が満たされるか否かを判定し、いずれかの条件が満たされたときは、当該圧縮済時系列データＸｉ，Ｘｊに圧縮される前の各時系列データについて圧縮済時系列データ間の距離が閾値以下であるか否かの判定以降の処理を省略させる
ことを特徴とする類似時系列データ検出装置における処理方法。
【請求項５】
前記圧縮済時系列データ保存手段は、過去に次元圧縮された各圧縮済時系列データが逐次に保存されるものであり、
前記処理方法が、
事象ｉ，ｊについて新たに各時系列データが受信および次元圧縮されたときに、前記圧縮済時系列データ保存手段から過去の同一時期の事象ｉ，ｊについての各圧縮済時系列データを読み出し、当該各次元圧縮された圧縮済時系列データと当該読み出された各圧縮済時系列データとの間の各変化量ΔＳｉ，ΔＳｊを計算し、
前記最大値max（ΔＳｉ）および最小値min（ΔＳｊ）に当該変化量ΔＳｉを用い、前記最大値max（ΔＳｊ）および最小値min（ΔＳｊ）に当該変化量ΔＳｊを用いる
ことを特徴とする請求項４記載の類似時系列データ検出装置における処理方法。
【請求項６】
受信した各時系列データに対し該時系列データにより表される事象に関わる他のデータに応じたインデクスを付与し、前記圧縮済時系列データＸｉに次元圧縮される時系列データに付与されたインデクスと前記圧縮済時系列データＸｊに次元圧縮される時系列データに付与されたインデクスとが類似しているときは当該各時系列データについて次元圧縮以降の処理を省略することを特徴とする請求項４または５記載の類似時系列データ検出装置における処理方法。
【請求項７】
請求項１ないし３のいずれかに記載の類似時系列データ検出装置としてコンピュータを機能させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、距離計算の回数減少を図った類似時系列データ検出装置に関する。
【背景技術】
【０００２】
移動体位置管理システムやスペースシャトルのエンジンの制御システム等においては、複数のセンサから出力される時系列データが、一つのサーバやコントロールセンタへ送られ高速に処理される。また株のオンライントレイディングでは、複数の株価の情報をリアルタイム処理し、処理結果は株の売買に用いられる。これらの例で行われる処理の一つに、図２６に示すような複数の時系列データのうち、過去の一定期間内に閾値内の距離にある時系列データの組み合わせをリアルタイムに求める処理がある。
【０００３】
なお、ここで扱う時系列データには、株価のような離散値とエンジンの出力値のような連続値がある。時系列データが離散値である場合、時系列データが過去の一定期間内に閾値内の距離にあるかは、過去の一定の数の離散値に対して距離が閾値内になるか調べればよい。また、時系列データが連続値である場合は、時系列データはセンサなどでサンプリングされ離散値になるため、結局は離散値の処理手法を用いる。
【０００４】
時系列データの距離を求める処理においては、時系列データの数が多くなると距離計算を行う組み合わせの数が膨大となる。また時系列データ間の距離計算は、単位時間ごとに行われる。そのためリアルタイム処理のためには距離計算の計算コストを低減することが求められる。
【０００５】
計算コストを低減するための良く用いられる処理は、以下の通りである。
【０００６】
（１）時系列データを離散フーリエ変換などで次元圧縮
（２）次元圧縮した時系列データ同士の距離を計算
（３）計算結果が閾値より近い場合は元の時系列データ同士の距離を計算
【０００７】
（１）で時系列データの次元圧縮を行うのは（２）における距離計算の計算コストを以下のように低減するためである。距離を計算する時系列データをＸ（ｘＴ−Ｎ＋１…ｘｉ…ｘT），Ｙ（ｙＴ−Ｎ＋１…ｙｉ…ｙＴ）（Ｔは現在の時刻、Ｎは距離を計算する離散値の数、ｘｉとｙｉは時刻ｉにおけるデータ・図２６参照）とした場合、時系列データＸ，ＹはＮ次元空間内の一つの点として考えることができる。そのためユークリッド距離Ｄｅｕｃｌｉｄを計算する場合の計算量は式（１）のようにＯ（Ｎ）となる。
【数１】
2006119742.tif 000003
【０００８】
Ｎは一般に大きな数になることが多い。そのためすべての時系列データ間において上に示したような距離計算を行うことはリアルタイムに処理を行う上で問題がある。そのため時系列データの次元圧縮を行い時系列データＸ，Ｙをｎ次元空間内の点（ｎ＜Ｎ）に置き換えることが良く行われる。時系列データ処理においてよく用いられる次元圧縮方法として、離散フーリエ変換（ＤＦＴ）や（ハール基底の）離散ウェブレット変数（ＤＷＴ）やPiecewise Aggregate Approximation（ＰＡＡ）がある。次元圧縮を行った結果（２）における距離計算の計算コストはＯ（Ｎ）からＯ（ｎ）へ低減する。
【０００９】
上記の次元圧縮手法後の時系列データ間の距離Ｄｄｉｇｅｓｔは、もとの時系列データ間の距離Ｄｅｕｃｌｉｄと比較して、Ｄｄｉｇｓｅｔ≦Ｄｅｕｃｌｉｄとなることが知られている。よって（２）においてＤｄｉｇｓｅｔ≦εとなった時系列データの組み合わせに対して、（３）において改めてＤｅｕｃｌｉｄを計算しなおしてＤｅｕｃｌｉｄ≦εとなるか計算を行う。
【００１０】
ある閾値内の距離である複数の時系列データの組み合わせをリアルタイムに求める処理の従来手法に、Yunyue Zhuらが提案した手法がある。Yunyue Zhuらの手法は（２）の処理の高速化手法である。Yunyue Zhuらの手法では次元圧縮の係数を用いて時系列データをセルに配置し、不要な距離計算を行う時系列データの組み合わせを削減する。
【００１１】
次元圧縮後の距離計算を行うのは、１回の距離計算あたりの計算コストを低減するアプローチであるが、Yunyue Zhuらの手法は、距離計算を行う回数を減らして計算コストを低減するアプローチである。
【００１２】
Yunyue Zhuらの手法の手順は、以下の通りである（図２４参照）。
【００１３】
１．ｎ次元のうち初めの
2006119742.tif 000004
に対して原点Ｏから各軸を閾値で区切り、全部で
2006119742.tif 000005
のセルに分割する（rangeは係数がとりうる係数の最大値、εは閾値）、
２．時系列データが属する空間（１個）とその隣の空間（３Ａ−１個）のみを対象に距離計算する。
【００１４】
（２）においては、基本的に全ての時系列データの組み合わせに対して距離の計算が必要であるため、捜索する領域は多次元空間の全域になる。しかし、Yunyue Zhuらの手法を用いれば、捜索する領域は、図２４のように、多次元空間内の隣接するセルの領域に限定できるため、距離計算の回数を減らすことができる。
【００１５】
なお、本発明の背景となる事項を記載した文献として以下のようなものがある。
【非特許文献１】Eamon Keogh,Kaushik Chakrabarti,Michael Pazzani,Sharad Mehrotra,“Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases”,Journal of Knowledge and Information Systems,2000,pp263-286
【非特許文献２】Yunyue Zhu,Dennis Shasha,“StatStream:Statistical Monitoring of Thousands of Data Streams in Real Time”,Proceedings of 28th International Cnferencs on Very Large Data Bases,2002,pp358-369
【発明の開示】
【発明が解決しようとする課題】
【００１６】
Yunyue Zhuらの手法の問題点として、複数の時系列データが、図２７に示すように近い距離にある場合は、効果が期待できないことが挙げられる。
【００１７】
図２７に示すように、複数の時系列データが近い距離にある場合は、図２８のように多次元空間内であっても、近い場所に時系列データがマッピングされる。この場合は、Yunyue Zhuらの手法を用いて距離計算を行う時系列データの対象を隣接するセルに限定しても、隣接するセルの中に多くの時系列データが存在するため、距離計算の回数を減らすことはできない。
【００１８】
つまり、従来手法は１つの軸を閾値で区切り、次元圧縮の係数を用いて時系列データをセルに配置し不要な距離計算を行う時系列データの組み合わせを削減する手法であった。そのため、時系列データが多次元空間内の特定の場所に集中した場合、距離計算の回数を減らすことができない問題があった。
【００１９】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、距離計算の回数減少を図った類似時系列データ検出装置を提供することにある。
【課題を解決するための手段】
【００２０】
上記課題を解決するために、請求項１の本発明は、時系列的に採取された複数のデータからなる時系列データを受信した後に該時系列データに含まれるデータよりも新しいデータを含む時系列データを受信するようにして時系列データを逐次に受信するとともに当該時系列データにより表される事象ｉとは異なる事象ｊについての時系列データを逐次に受信し、受信した時系列データを逐次に次元圧縮し、事象ｉの時系列データから次元圧縮された圧縮済時系列データと、当該時系列データと同一時期の時系列データであって事象ｊの時系列データである時系列データから次元圧縮された圧縮済時系列データとの間の距離を計算し、当該距離が所定の閾値以下であるか否かを判定し、当該距離が当該閾値以下であると判定された場合は当該圧縮済時系列データに次元圧縮される前の時系列データとの間の距離を計算し、当該距離が所定の閥値以下である場合は時系列データ同士が類似していることとして所定の動作を行う類似時系列データ検出装置において、過去に計算された圧縮済時系列データ間の距離が記憶される圧縮済時系列データ間距離保存手段と、新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データが保存される圧縮済時系列データ保存手段と、事象ｉ，ｊについて新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データと過去の所定の時期τの圧縮済時系列データとの間の変化量の最大値および最小値が保存される変化量保存手段と、事象ｉ，ｊについて新たに時系列データが受信され圧縮済時系列データＸｉ，Ｘｊに次元圧縮されたときに、前記圧縮済時系列データ保存手段から事象ｉ，ｊの時期τの圧縮済時系列データＸｉτ，Ｘｊτを読み出し、前記変化量保存手段から事象ｉ，ｊの最大値および最小値を読み出し、これらを用いて、圧縮済時系列データＸｉτと圧縮済時系列データＸｉとの間の変化量の最大値max（ΔＳｉ）および最小値min（ΔＳｊ）を計算するとともに、圧縮済時系列データＸｊτと圧縮済時系列データＸｊとの間の変化量の最大値max（ΔＳｊ）および最小値min（ΔＳｊ）を計算する変化量計算手段と、前記圧縮済時系列データ間距離保存手段から前記圧縮済時系列データＸｉτ，Ｘｊτ間の距離ｄτ（ｉ，ｊ）を読み出すとともに予め記憶された閾値εを読み出し、
条件１：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）−max（unmatch）
条件２：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＞ｄτ（ｉ，ｊ）＋max（unmatch）
条件３：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋min（unmatch）
条件４：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋max（unmatch）
ただし、条件１，２，３および４では、
max（unmatch）＝max（ΔＳｊ）＋ε
min（unmatch）＝max（０，min（ΔＳｊ）−ε）
条件５：ｄτ（ｉ，ｊ）≧εかつmax（ΔＳｉ）≦ −ｄτ（ｉ，ｊ）＋max（match）
ただし、条件５では、
max（match）＝max（０，ε−max（ΔＳｊ））
min（unmatch）＝０ 
ただし、各条件では、max（ａ，ｂ）はａとｂの内の大きい方
のいずれかの条件が満たされるか否かを判定し、いずれかの条件が満たされたときは、当該圧縮済時系列データＸｉ，Ｘｊに圧縮される前の各時系列データについて圧縮済時系列データ間の距離が閾値以下であるか否かの判定以降の処理を省略させる処理省略制御手段とを備えることを特徴とする類似時系列データ検出装置をもって解決手段とする。
【００２１】
請求項２の本発明は、前記圧縮済時系列データ保存手段は、過去に次元圧縮された各圧縮済時系列データが逐次に保存されるものであり、前記変化量保存手段を要せずかつ前記変化量計算手段に代えて、事象ｉ，ｊについて新たに各時系列データが受信および次元圧縮されたときに、前記圧縮済時系列データ保存手段から過去の同一時期の事象ｉ，ｊについての各圧縮済時系列データを読み出し、当該各次元圧縮された圧縮済時系列データと当該読み出された各圧縮済時系列データとの間の各変化量ΔＳｉ，ΔＳｊを計算する変化量計算手段を備え、前記処理省略制御手段に代えて、当該処理省略制御手段が行う処理において、前記最大値max（ΔＳｉ）および最小値min（ΔＳｊ）に当該変化量ΔＳｉを用い、前記最大値max（ΔＳｊ）および最小値min（ΔＳｊ）に当該変化量ΔＳｊを用いる処理省略制御手段を備えることを特徴とする請求項１記載の類似時系列データ検出装置をもって解決手段とする。
【００２２】
請求項３の本発明は、受信した各時系列データに対し該時系列データにより表される事象に関わる他のデータに応じたインデクスを付与し、前記圧縮済時系列データＸｉに次元圧縮される時系列データに付与されたインデクスと前記圧縮済時系列データＸｊに次元圧縮される時系列データに付与されたインデクスとが類似しているときは当該各時系列データについて次元圧縮以降の処理を省略することを特徴とする請求項１または２記載の類似時系列データ検出装置をもって解決手段とする。
【００２３】
請求項４の本発明は、時系列的に採取された複数のデータからなる時系列データを受信した後に該時系列データに含まれるデータよりも新しいデータを含む時系列データを受信するようにして時系列データを逐次に受信するとともに当該時系列データにより表される事象ｉとは異なる事象ｊについての時系列データを逐次に受信し、受信した時系列データを逐次に次元圧縮し、事象ｉの時系列データから次元圧縮された圧縮済時系列データと、当該時系列データと同一時期の時系列データであって事象ｊの時系列データである時系列データから次元圧縮された圧縮済時系列データとの間の距離を計算し、当該距離が所定の閾値以下であるか否かを判定し、当該距離が当該閾値以下であると判定された場合は当該圧縮済時系列データに次元圧縮される前の時系列データとの間の距離を計算し、当該距離が所定の閥値以下である場合は時系列データ同士が類似していることとして所定の動作を行う類似時系列データ検出装置における処理方法において、前記類似時系列データ検出装置が、過去に計算された圧縮済時系列データ間の距離が記憶される圧縮済時系列データ間距離保存手段と、新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データが保存される圧縮済時系列データ保存手段と、事象ｉ，ｊについて新たに時系列データが受信および次元圧縮されるまでの最も新しい圧縮済時系列データと過去の所定の時期τの圧縮済時系列データとの間の変化量の最大値および最小値が保存される変化量保存手段とを備え、前記処理方法が、事象ｉ，ｊについて新たに時系列データが受信され圧縮済時系列データＸｉ，Ｘｊに次元圧縮されたときに、前記圧縮済時系列データ保存手段から事象ｉ，ｊの時期τの圧縮済時系列データＸｉτ，Ｘｊτを読み出し、前記変化量保存手段から事象ｉ，ｊの最大値および最小値を読み出し、これらを用いて、圧縮済時系列データＸｉτと圧縮済時系列データＸｉとの間の変化量の最大値max（ΔＳｉ）および最小値min（ΔＳｊ）を計算するとともに、圧縮済時系列データＸｊτと圧縮済時系列データＸｊとの間の変化量の最大値max（ΔＳｊ）および最小値min（ΔＳｊ）を計算し、前記圧縮済時系列データ間距離保存手段から前記圧縮済時系列データＸｉτ，Ｘｊτ間の距離ｄτ（ｉ，ｊ）を読み出すとともに予め記憶された閾値εを読み出し、
条件１：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）−max（unmatch）
条件２：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＞ｄτ（ｉ，ｊ）＋max（unmatch）
条件３：ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋min（unmatch）
条件４：ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋max（unmatch）
ただし、条件１，２，３および４では、
max（unmatch）＝max（ΔＳｊ）＋ε
min（unmatch）＝max（０，min（ΔＳｊ）−ε）
条件５：ｄτ（ｉ，ｊ）≧εかつmax（ΔＳｉ）≦ −ｄτ（ｉ，ｊ）＋max（match）
ただし、条件５では、
max（match）＝max（０，ε−max（ΔＳｊ））
min（unmatch）＝０ 
ただし、各条件では、max（ａ，ｂ）はａとｂの内の大きい方
のいずれかの条件が満たされるか否かを判定し、いずれかの条件が満たされたときは、当該圧縮済時系列データＸｉ，Ｘｊに圧縮される前の各時系列データについて圧縮済時系列データ間の距離が閾値以下であるか否かの判定以降の処理を省略させることを特徴とする類似時系列データ検出装置における処理方法をもって解決手段とする。
【００２４】
請求項５の本発明は、前記圧縮済時系列データ保存手段は、過去に次元圧縮された各圧縮済時系列データが逐次に保存されるものであり、前記処理方法が、事象ｉ，ｊについて新たに各時系列データが受信および次元圧縮されたときに、前記圧縮済時系列データ保存手段から過去の同一時期の事象ｉ，ｊについての各圧縮済時系列データを読み出し、当該各次元圧縮された圧縮済時系列データと当該読み出された各圧縮済時系列データとの間の各変化量ΔＳｉ，ΔＳｊを計算し、前記最大値max（ΔＳｉ）および最小値min（ΔＳｊ）に当該変化量ΔＳｉを用い、前記最大値max（ΔＳｊ）および最小値min（ΔＳｊ）に当該変化量ΔＳｊを用いることを特徴とする請求項４記載の類似時系列データ検出装置における処理方法をもって解決手段とする。
【００２５】
請求項６の本発明は、受信した各時系列データに対し該時系列データにより表される事象に関わる他のデータに応じたインデクスを付与し、前記圧縮済時系列データＸｉに次元圧縮される時系列データに付与されたインデクスと前記圧縮済時系列データＸｊに次元圧縮される時系列データに付与されたインデクスとが類似しているときは当該各時系列データについて次元圧縮以降の処理を省略することを特徴とする請求項４または５記載の類似時系列データ検出装置における処理方法をもって解決手段とする。
【００２６】
請求項７の本発明は、請求項１ないし３のいずれかに記載の類似時系列データ検出装置としてコンピュータを機能させるコンピュータプログラムをもって解決手段とする。
【発明の効果】
【００２７】
本発明によれば、時系列データ間の距離を計算することにより類似した時系列データを検出する類似時系列データ検出装置における距離計算の回数を減少させることができる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施の形態を図面を参照して説明する。  
図１は、本発明の実施の形態に係る類似時系列データ検出装置１の構成図である。  
類似時系列データ検出装置１は、複数の事象のそれぞれについて時系列的に採取された複数のデータからなる時系列データを受信した後に該時系列データに含まれるデータよりも新しいデータを含む時系列データを受信するようにして時系列データを逐次に受信する時系列データ受信部１０と、受信された時系列データを逐次に次元圧縮する次元圧縮部１１と、互いに異なる事象についての同一時期の時系列データ間の距離を計算するか否かを判断する計算判断部１２と、時系列データ間の距離を計算する距離計算部１３と、時系列データ間の距離が閾値以下であった場合はその旨を通知する計算結果送信部１４を備える。
【００２９】
ここで、上記した事象は、時間経過に伴う変化が見込まれる同一の事象、例えばある会社の株価変動をいう。また、上記のように、時系列データ間の距離は、互いに異なる事象についての同一時期の時系列データ間の距離、例えば、Ｉ社の１月の各日の株価（データ）からなる時系列データとＪ社の１月の各日の株価（データ）からなる時系列データとの間の距離をいう。また、時系列データを逐次に受信するという受信形態は、例えば、１月の各日の株価からなる時系列データを１月の最終日の株取引終了後に受信し、１月の初日を除き且つ２月の初日を加えた１ヶ月分の時系列データを２月の初日の株取引終了後に受信するというような形態をいう。
【００３０】
図２は、時系列データ受信部１０の構成図である。  
時系列データ受信部１０は、時系列データを受信するデータ受信部１００と、受信したデータを一時的に保存する時系列データ保存部１０１と、受信や保存された時系列データを読み出して次元圧縮部１１や距離計算部１３へ送信するデータ送信部１０２とを備える。
【００３１】
図３は、次元圧縮部１１の構成図である。  
次元圧縮部１１は、時系列データ受信部１０から時系列データを受信するデータ受信部１１０と、時系列データの次元圧縮を行う次元圧縮部１１１と、次元圧縮後の圧縮済時系列データを計算判断部１２へ送信するデータ送信部１１２とを備える。
【００３２】
図４は、計算判断部１２の構成図である。  
計算判断部１２は、次元圧縮部１１から圧縮済時系列データを受信するデータ受信部１２０と、同一事象についての過去の圧縮済時系列データとそれより新しい圧縮済時系列データと間の変化量の最大値と最小値を計算する変化量計算部１２１と、時系列データ間の距離を計算するか否かの判断基準を変化量の計算に必要なデータとともに保存する判断基準保存部１２２と、時系列データ間の距離を計算するか否かを判断する計算判断部１２３と、データ受信部１２０で受信された圧縮済時系列データを距離計算部１３へ送信するデータ送信部１２４とを備える。上記のように、圧縮済時系列データ間の変化量または変化量は、同一事象についての過去の圧縮済時系列データとそれより新しい圧縮済時系列データと間の変化量をいう。また、変化量計算部１２１は、本発明の変化量計算手段を構成する主要素であり、計算判断部１２３は、本発明の処理省略手段を構成する主要素である。
【００３３】
図５は、距離計算部１３の構成図である。  
距離計算部１３は、時系列データ受信部１０からの時系列データや計算判断部１２から圧縮済時系列データを受信するデータ受信部１３０と、圧縮済時系列データ間の距離を計算する距離計算部１３１と、距離の閾値を保存する閾値保存部１３２と、時系列データ間の距離を計算するか否かを判断する再計算判断部１３３と、時系列データ間の距離を計算する距離再計算部１３４と、距離再計算部１３４で計算された時系列データ間の距離が閾値保存部１３２に保存されている閾値以下か否か判断する計算結果判断部１３５と、距離が閾値以下である時系列データを計算結果送信部１４へ送信するとともに圧縮済時系列データ間の距離を計算判断部１２へ通知するデータ送信部１３６とを備える。
【００３４】
図６は、計算結果送信部１４の構成図である。  
計算結果送信部１４は、距離計算部１３から距離が閾値以下である時系列データを受信するデータ受信部１４０と、類似している時系列データを必要とする図示しないサーバなどに対し距離が閾値以下である当該時系列データを当該類似している時系列データとして送信するデータ送信部１４１とを備える。
【００３５】
図７は、判断基準保存部１２２の構成図である。  
判断基準保存部１２２は、データ受信部１２０と変化量計算部１２１からデータを受信するデータ受信部１２２０と、圧縮済時系列データを構成する次元係数を保存する次元係数保存部１２２１と、圧縮済時系列データ間の変化量の最大値と最小値を保存する変化量保存部１２２２（変化量記憶手段）と、圧縮済時系列データ間の距離を保存する距離保存部１２２３と、閾値を保存する閾値保存部１２２４と、変化量計算部１２１と計算判断部１２３へデータを送信するデータ送信部１２２５とを備える。次元係数保存部１２２１は、本発明の圧縮済時系列データ保存手段に相当し、変化量保存部１２２２は、本発明の変化量保存手段に相当し、距離保存部１２２３は、本発明の圧縮済時系列データ間距離保存手段に相当する。
【００３６】
図８は、計算判断部１２３の構成図である。  
計算判断部１２３は、変化量計算部１２１と判断基準保存部１２２からのデータを受信するデータ受信部１２３０と、このデータを用いて距離計算部１３が時系列データ間の距離を計算するか否かを判断する計算判断部１２３１と、この判断結果を距離計算部１３へ送信するデータ送信部１２３２とを備える。
【００３７】
次に、類似時系列データ検出装置１の動作を説明する。  
図１の類似時系列データ検出装置１の時系列データ受信部１０では、図２の時系列データが、時系列データを採取する図示しない装置などから送信された時系列データを逐次に受信し、この受信した時系列データを、後に距離計算部１３から要求された場合に備えて時系列データ保存部１０１が保存し、データ送信部１０２が受信された時系列データを図１の次元圧縮部１１へ送信する。なお、類似時系列データ検出装置１は、時系列データを一定時間ごとに受信しても良いし、不定期に受信してもよい。
【００３８】
図１の次元圧縮部１１では、図３のデータ受信部１１０が時系列データを受信し、これを次元圧縮部１１１がＤＦＴやＤＷＴやＰＡＡなどの方法で次元圧縮し、この圧縮済時系列データをデータ送信部１１２が図１の計算判断部１２へ送信する。
【００３９】
図１の計算判断部１２では、図４のデータ受信部１２０が圧縮済時系列データを受信し、変化量計算部１２１が当該圧縮済時系列データ、判断基準保存部１２２に保存された圧縮済時系列データならびに変化量の最大値および最小値を用いて、圧縮済時系列データ間の変化量の最大値および最小値を計算し、計算判断部１２３がこの最大値および最小値と判断基準保存部１２２に保存された判断基準とを用いて時系列データ間の距離を計算するか否かを判断し、データ送信部１２４が当該判断の判断結果と当該圧縮済時系列データを図１の距離計算部１３へ送信する。
【００４０】
なお、変化量の最大値および最小値の計算と時系列データ間の距離を計算するか否かの判断についての処理は後に述べる。
【００４１】
さて、図１の距離計算部１３では、図５のデータ受信部１３０が判断結果と圧縮済時系列データを受信し、この圧縮済時系列データを距離計算部１３１へ与え、この圧縮済時系列データ間の距離を距離計算部１３１が計算してデータ送信部１３６へ通知し、この距離をデータ送信部１３６が図１の計算判断部１２に通知する。
【００４２】
図１の計算判断部１２では、図４のデータ受信部１２０が通知された距離を判断基準保存部１２２に通知する。この判断基準保存部１２２では、図７のデータ受信部１２２０が通知された距離を距離保存部１２２３に保存する。
【００４３】
上記のように、図５のデータ受信部１３０が判断結果と圧縮済時系列データを受信し、この判断結果が、時系列データ間の距離を計算しない旨の判断結果であった場合は、類似時系列データ検出装置１が次に時系列データを受信するまで処理がなされない。つまり、距離計算を行う旨の判断結果が得られた場合の処理が省略される。
【００４４】
以下、当該処理を説明する。  
この場合は、図５の距離計算部１３１が、計算した距離を再計算判断部１３３に通知し、再計算判断部１３３が、閾値保存部１３２から距離の閾値を読み出し、通知された距離が当該閾値以下であるか否かを判定する。ここで、当該距離が当該閾値以下でない場合は、類似時系列データ検出装置１が次に時系列データを受信するまで処理がなされない。つまり、当該距離が当該閾値以下である場合の処理が省略される。
【００４５】
以下、当該処理を説明する。  
この場合は、図５の再計算判断部１３３が距離再計算部１３４に時系列データ間の距離を計算するように指示する。データ受信部１３０は、この距離が計算される時系列データを図１の時系列データ受信部１０に要求する。
【００４６】
図１の時系列データ受信部１０では、図２のデータ送信部１０２が、要求された時系列データを時系列データ保存部１０１から読み出して、図５のデータ受信部１３０へ送信する。
【００４７】
図５のデータ受信部１３０は、データ送信部１０２からの時系列データを受信し、これを距離再計算部１３４へ与え、距離再計算部１３４がこの時系列データを計算結果判断部１３５へ与えるとともに、この時系列データ間の距離を距離再計算部１３４が計算して計算結果判断部１３５へ通知する。そして、計算結果判断部１３５が、閾値保存部１３２から距離の閾値を読み出し、通知された距離が当該閾値以下であるか否かを判定する。ここで、当該距離が当該閾値以下でない場合は、類似時系列データ検出装置１が次に時系列データを受信するまで処理がなされない。つまり、当該距離が当該閾値以下である場合の処理が省略される。
【００４８】
以下、当該処理を説明する。  
この場合は、図５の計算結果判断部１３５が時系列データをデータ送信部１３６に与え、これをデータ送信部１３６が図１の計算結果送信部１４へ送信する。
【００４９】
図１の計算結果送信部１４では、図６のデータ受信部１４０が時系列データを受信し、データ送信部１４１が、類似している時系列データを必要とする図示しないサーバなどに対し当該受信された時系列データを当該類似している時系列データとして送信する。
【００５０】
次に、図４の変化量計算部１２１が行う変化量の計算を説明する。ここでは、事象を特定することなく、つまり事象が同一であることを前提として説明するが、当該計算は各事象についてなされるものである。
【００５１】
また、ここでは、図９に示す時刻Ｔ−１に受信された時系列データから次元圧縮された圧縮済時系列データを構成する次元係数が次元係数保存部１２２１に保存されていることとする。なお、以下、圧縮済時系列データを、その構成要素である次元係数には言及せずに、単に圧縮済時系列データという。また、上記の圧縮済時系列データを時刻Ｔ−１の圧縮済時系列データというように説明する。なお、本実施の形態では、時刻τではない過去の時刻の圧縮済時系列データは次元係数保存部１２２１にしなくて良いので、メモリ消費量を節約することができる。
【００５２】
また、ここでは、図９に示す時刻Ｔ−１よりも過去の時刻τの圧縮済時系列データと時刻Ｔ−１の圧縮済時系列データとの間の変化量の最大値max（ΔＳ）および最小値min（ΔＳ）が変化量保存部１２２２に保存されていることとする。
【００５３】
まず、変化量計算部１２１は、データ受信部１２０が時刻Ｔ−１より未来の時刻Ｔの圧縮済時系列データを受信すると、判断基準保存部１２２に対し時刻Ｔ−１の圧縮済時系列データを要求し、この要求を図７のデータ受信部１２２０が受信し、データ送信部１２２５が次元係数保存部１２２１から時刻Ｔ−１の圧縮済時系列データを読み出し送信するので、変化量計算部１２１はこれを受信する。そして、図９に示すように時刻Ｔの圧縮済時系列データと時刻Ｔ−１の圧縮済時系列データとの間の変化量Δｓ１を計算する。
【００５４】
ここでの計算を一般化して、例えば、時刻Ｔ−ｔの圧縮済時系列データをＸＴ−ｔ（ｘＴ−ｔ，１…ｘＴ−ｔ＋１，ｎ）とし、時刻Ｔ−ｔよりも未来の時刻Ｔ−ｔ＋１の圧縮済時系列データをＸＴ−ｔ＋１（ｘＴ−ｔ＋１，１…ｘＴ−ｔ＋１，ｎ）とすると、当該圧縮済時系列データ間の変化量Δｓｔは、式（２）により計算される。なお、ｎは圧縮済時系列データを構成する次元係数の総数であり、以下においても同様である。
【数２】
2006119742.tif 000006
【００５５】
ここで、上記の最大値max（ΔＳ）および最小値min（ΔＳ）は、例えば、図９において、時刻Ｔ−３を時刻τとすると、データ受信部１２０が時刻Ｔ−３と時刻Ｔ−１の間の時刻Ｔ−２の圧縮済時系列データを受信したときに変化量計算部１２１が上記のように計算した変化量Δｓ３と、データ受信部１２０が時刻Ｔ−１の圧縮済時系列データを受信したときに変化量計算部１２１が上記のように計算した変化量Δｓ２とを用いて計算されたものである。例えば、図１０のように、Δｓ３＝２、Δｓ２＝１とすると、このときの最大値max（ΔＳ）である最大値max（ΔＳＴ−１，Ｔ−３）＝２＋１＝３となり、このときの最小値min（ΔＳ）である最小値min（ΔＳＴ−１，Ｔ−３）＝２＋１＝１となる。
【００５６】
次に、図４の変化量計算部１２１は、判断基準保存部１２２に対し最大値max（ΔＳ）および最小値min（ΔＳ）を要求し、この要求を図７のデータ受信部１２２０が受信し、データ送信部１２２５が変化量保存部１２２２から最大値max（ΔＳ）および最小値min（ΔＳ）を読み出し送信するので、変化量計算部１２１はこれを受信する。
【００５７】
そして、変化量計算部１２１は、時刻τの圧縮済時系列データと時刻Ｔの圧縮済時系列データとの間の変化量の最大値および最小値を計算し、これを判断基準保存部１２２に送信する。
【００５８】
判断基準保存部１２２では、データ受信部１２２０が変化量の最大値および最小値を受信し、変化量保存部１２２２に保存する。この最大値および最小値は、時刻Ｔより未来の時刻Ｔ＋１において新たに時系列データが受信され次元圧縮されるまでの最も新しい圧縮済時系列データと時期τの圧縮済時系列データとの間の変化量の最大値および最小値として保存される。
【００５９】
ここで、最大値と最小値の計算を個別に説明する。  
先ず、時刻Ｔの圧縮済時系列データと時刻Ｔ−ｔの圧縮済時系列データとの間の変化量の最大値max（ΔＳＴ，Ｔ−ｔ）の計算方法を説明する。
【００６０】
図１１に示すように、時刻Ｔ−１の圧縮済時系列データと時刻Ｔ−ｔの圧縮済時系列データとの間の変化量の最大値max（ΔＳＴ−１，Ｔ−ｔ）を半径とする円を描くと、最大値max（ΔＳＴ，Ｔ−ｔ）を半径とする円は、当該円の半径を変化量Δｓ１に相当する長さだけ長くした円である。よって変化量計算部１２１は、最大値max（ΔＳＴ，Ｔ−ｔ）を式（３）または式（４）により計算する。
【００６１】
ｔ＝１の場合は、max（ΔＳＴ，Ｔ−ｔ）＝Δｓ1                 …（３）
ｔ＞１の場合は、max（ΔＳＴ，Ｔ−ｔ）＝max（ΔＳＴ−１，Ｔ−ｔ）＋Δｓ１
…（４）
【００６２】
次に、時刻Ｔの圧縮済時系列データと時刻Ｔ−ｔの圧縮済時系列データとの間の変化量の最小値min（ΔＳＴ，Ｔ−ｔ）の計算方法を説明する。
【００６３】
まず、ｔ＝１の場合は、最小値min（ΔＳＴ，Ｔ−ｔ）＝ΔＳ１と計算する。
【００６４】
次に、ｔ＞１での場合を説明する。
【００６５】
ここで、図１２に示すように、時刻Ｔ−１の圧縮済時系列データと時刻Ｔ−ｔの圧縮済時系列データとの間の変化量の最大値max（ΔＳＴ−１，Ｔ−ｔ）および最小値min（ΔＳＴ−１，Ｔ−ｔ）と変化量Δｓ１の比較結果について３つの場合で処理を異ならせる。
【００６６】
（１）Δｓ１＜min（ΔＳＴ−１，Ｔ−ｔ）の場合、図１３に示すように、最小値min（ΔＳＴ，Ｔ−ｔ）を半径とする円は、最小値min（ΔＳＴ−１，Ｔ−ｔ）を半径とする円の半径を変化量Δｓ１だけ短くしたものである。よって変化量計算部１２１は、最小値min（ΔＳＴ，Ｔ−ｔ）を式（５）により計算する。
【００６７】
min（ΔＳＴ，Ｔ−ｔ）＝（ΔＳＴ−１，Ｔ−ｔ）−Δｓ１      …（５）
【００６８】
（２）min（ΔＳＴ−１，Ｔ−ｔ）＜＝Δｓ1 ＜＝ max（ΔＳＴ−１，Ｔ−ｔ）の場合、図１４に示すように、最小値min（ΔＳＴ，Ｔ−ｔ）を半径とする円は、最小値min（ΔＳＴ−１，Ｔ−ｔ）を半径とする円の半径を変化量Δｓ１だけ短くしたものである。よって、変化量計算部１２１は、最小値min（ΔＳＴ，Ｔ−ｔ）を式（６）により計算する。
【００６９】
min（ΔＳＴ，Ｔ−ｔ）＝０                                    …（６）
【００７０】
（３）max（ΔＳＴ−１，Ｔ−ｔ）＜Δｓ１  の場合、図１５に示すように、最小値min（ΔＳＴ，Ｔ−ｔ）を半径とする円は、最大値max（ΔＳＴ−１，Ｔ−ｔ）を半径とする円の半径を変化量Δｓ１だけ短くしたものである。よって、変化量計算部１２１は、最小値min（ΔＳＴ，Ｔ−ｔ）を式（７）により計算する。
【００７１】
min（ΔＳＴ，Ｔ−ｔ）＝Δｓ１−max（ΔＳＴ−１，Ｔ−ｔ）   …（７）
【００７２】
例えば、図９において、時刻τが時刻Ｔ−４でΔｓ４＝２の場合は、
max（ΔＳＴ−３，Ｔ−４）＝２、min（ΔＳＴ−３，Ｔ−４）＝２となる。  
さらに、Δｓ３＝１の場合は、
max（ΔＳＴ−２，Ｔ−４）＝３、min（ΔＳＴ−２，Ｔ−４）＝１となる。  
さらに、Δｓ２＝７の場合は、
max（ΔＳＴ−１，Ｔ−４）＝１０、min（ΔＳＴ−１，Ｔ−４）＝４となる。  
さらに、Δｓ１＝５の場合は、
max（ΔＳＴ，Ｔ−４）＝１５、min（ΔＳＴ−１，Ｔ−４）＝０となる。
【００７３】
上記のように、変化量計算部１２１は、変化量をインクリメンタルに計算するので、計算の負荷の集中を防止することができる。
【００７４】
次に、図４の計算判断部１２３が行う判断を説明する。  
計算判断部１２３では、変化量計算部１２１が、例えば、事象ｉについての時刻τの圧縮済時系列データと時刻Ｔの圧縮済時系列データとの間の変化量の最大値max（ΔＳｉ）および最小値min（ΔＳｉ）ならびに事象ｊについての時刻τの圧縮済時系列データと時刻Ｔの圧縮済時系列データとの間の変化量の最大値max（ΔＳｊ）および最小値min（ΔＳｊ）を計算すると、判断基準保存部１２２に対し、事象ｉについての時刻τの圧縮済時系列データＸｉτと事象ｊについての時刻τの圧縮済時系列データＸｊτとの間の距離ｄτ（ｉ，ｊ）ならびに距離の閾値εを要求し、この要求を図７のデータ受信部１２２０が受信し、データ送信部１２２５が距離保存部１２２３から距離ｄτ（ｉ，ｊ）を読み出し、また、閾値εを閾値保存部１２２４から読み出し、これらを送信するので、計算判断部１２３は距離ｄτ（ｉ，ｊ）と閾値εを受信する。
【００７５】
計算判断部１２３は、以下に示す条件Ｉまたは条件ＩＩが成立するときは、事象ｉについての時刻Ｔの時系列データと事象ｊについての時刻Ｔの時系列データとの間の距離を計算しないと判断する。
【００７６】
条件Ｉ．距離ｄτ（ｉ，ｊ）＞閾値ε（この状態を時刻τでmatchしているという）でありかつ、事象ｉについての時刻Ｔの圧縮済時系列データＸｉと事象ｊについての時刻Ｔの圧縮済時系列データＸｊとの間の距離ｄ（ｉ，ｊ）＞閾値ε（時刻Ｔでmatch）である。
【００７７】
条件ＩＩ．距離ｄτ（ｉ，ｊ）＜＝閾値ε（時刻τでunmatchしているという）でありかつ、事象ｉについての時刻Ｔの圧縮済時系列データＸｉと事象ｊについての時刻Ｔの圧縮済時系列データＸｊとの間の距離ｄ（ｉ，ｊ）＜＝閾値ε（時刻Ｔでunmatch）である。
【００７８】
上記のように判断するのは、図１６に示すように、事象ｉ，ｊの時系列データ間でmatchまたはunmatchの関係が時間的に連続することが多いためである。
【００７９】
条件Ｉが成立するのは、圧縮済時系列データＸｊのとりうる範囲が、図１７のハッチングの領域（外側：max（unmatch），内側：min（unmatch））になければよい。なお、max（ａ，ｂ）はａとｂの内の大きい方とすると、max（unmatch）とmin（unmatch）は、式（８）と式（９）に示すようになる。
【００８０】
max（unmatch）＝max（ΔＳｊ）＋ε                          …（８）
min（unmatch）＝max（０，min（ΔＳｊ）−ε）               …（９）
【００８１】
条件Ｉでは、距離ｄ（ｉ，ｊ）が未知であるため、実際には、以下の条件１，２，３および４の内のいずれかが成立したときに時系列データ間の計算をしないと判断する。
【００８２】
式（１０）に示す条件１は、ｄ（ｉ，ｊ）＞max（unmatch）のときのものであり、図１８では条件１を図形的に示している。
【００８３】
条件１：
ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）−max（unmatch）…（１０）
【００８４】
式（１１）に示す条件２は、ｄ（ｉ，ｊ）＞max（unmatch）のときのものであり、図１９では条件２を図形的に示している。
【００８５】
条件２：
ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＞ｄτ（ｉ，ｊ）＋max（unmatch）…（１１）
【００８６】
式（１２）に示す条件３は、ｄ（ｉ，ｊ）＜min（unmatch）のときのものであり、図２０では条件３を図形的に示している。
【００８７】
条件３：
ｄτ（ｉ，ｊ）＞εかつmax（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋min（unmatch）…（１２）
【００８８】
式（１３）に示す条件４は、ｄ（ｉ，ｊ）＜min（unmatch）のときのものであり、図２１では条件４を図形的に示している。
【００８９】
条件４：
ｄτ（ｉ，ｊ）＞εかつmin（ΔＳｉ）＜ｄτ（ｉ，ｊ）＋max（unmatch）…（１３）
【００９０】
条件ＩＩが成立するのは、圧縮済時系列データＸｊのとりうる範囲が、図２２のハッチングの領域（外側：max（match），内側：min（match））にあればよい。なお、max（ａ，ｂ）はａとｂの内の大きい方とすると、max（unmatch）とmin（unmatch）は、式（１４）および式（１５）に示すようになる。
【００９１】
max（match）＝max（０，ε−max（ΔＳｉ））                 …（１４）
min（unmatch）＝０                                         …（１５）
【００９２】
条件ＩＩでは、距離ｄ（ｉ，ｊ）が未知であるため、実際には、以下の条件４が成立したときに時系列データ間の計算をしないと判断する。
【００９３】
式（１６）に示す条件５は、max（match）≧のときのものであり、図２３では条件５を図形的に示している。
【００９４】
条件５：
ｄτ（ｉ，ｊ）≧εかつmax（ΔＳｉ）≦ −ｄτ（ｉ，ｊ）＋max（match）
…（１６）
【００９５】
上記したように、計算判断部１２３は、条件Ｉまたは条件ＩＩが成立したときに、時系列データ間の計算をしないと判断するのであるから、実際には、条件１，２，３，４および５のいずれかが成立したときに、時系列データ間の計算をしないと判断する。
【００９６】
他の実施の形態として、以下のように処理してもよい。
【００９７】
類似時系列データ検出装置１は、受信した各時系列データに対し該時系列データにより表される事象に関わる他のデータに応じたインデクスを付与し、圧縮済時系列データＸｉに次元圧縮される時系列データに付与されたインデクスと圧縮済時系列データＸｊに次元圧縮される時系列データに付与されたインデクスとが類似しているときは当該各時系列データについて次元圧縮以降の処理を省略するようにしてもよい。
【００９８】
例えば、事象が株価変動であれば、上記他のデータは会社の利益率などとすることができる。
【００９９】
Yunyue Zhu らの手法は、上記した技術と相殺する技術ではないため、計算判断部１２３が判断を行う前にこの手法を用いる。Yunyue Zhuらの手法では、図２４に示すようにｎ次元空間を初めの
2006119742.tif 000007
を用いて複数のセルに分割し、事象ｉの時系列データと該時系列データが属するセルならびにそれに隣接するセルに属する時系列データとの間の距離のみを計算することとする。こうして、距離計算を行う時系列データの組み合わせの数を減らした後に、計算判断部１２３が、さらに距離計算を行う時系列データの組み合わせを減らす。
【０１００】
また、他の実施の形態として、以下の点だけを変えて処理を行ってもよい。
【０１０１】
計算判断部１２３は、max（ΔＳｉ）とmin（ΔＳｉ）の両方にmax（ΔＳｉ）またはmin（ΔＳｉ）またはmax（ΔＳｉ）とmin（ΔＳｉ）の間の値を用い、max（ΔＳｊ）とmin（ΔＳｊ）の両方にmax（ΔＳｊ）またはmin（ΔＳｊ）またはmax（ΔＳｊ）とmin（ΔＳｉ）の間の値を用いる。
【０１０２】
なお、これらデータの保存場所、保存方法、読み出し方法は、上記説明したものと同様なので、その説明は省略する。以下に説明する他の実施の形態でも同様である。
【０１０３】
さて、類似時系列データ検出装置１では、他の実施の形態として、以下の点だけを変えて処理を行ってもよい。
【０１０４】
次元係数保存部１２２１には、過去に次元圧縮された各圧縮済時系列データを逐次に保存しておく。変化量計算部１２１は、各事象について、時刻τの圧縮済時系列データＸτ（ｘτ，１…ｘＴ，ｎ）とし、時刻Ｔの圧縮済時系列データをＸＴ（ｘＴ，１…ｘＴ，ｎ）とすると、変化量ΔＳを式（１７）により計算する。
【数３】
2006119742.tif 000008
【０１０５】
例えば、図２５の時刻Ｔ−４、Ｔ−３、Ｔ−２、Ｔ−１の圧縮済時系列データを保存しておいた場合、図２５のΔＳ３は、時刻Ｔ−３の圧縮済時系列データと時刻Ｔの圧縮済時系列データを用いて計算する。
【０１０６】
そして、計算判断部１２３は、事象ｉについて計算された変化量ΔＳである変化量ΔＳｉをmax（ΔＳｉ）とmin（ΔＳｉ）の両方に用い、事象ｊについて計算された変化量ΔＳである変化量ΔＳｉをmax（ΔＳｉ）とmin（ΔＳｉ）の両方に用いる。
【０１０７】
この実施の形態では、変化量を一意に計算することができる、つまり誤差のない変化量を求めることができる。また、この実施の形態では、変化量保存部１２２２が不要となる。
【０１０８】
また、他の実施の形態として、以下の点だけを変えて処理を行ってもよい。
【０１０９】
計算判断部１２３は、時刻τの圧縮済時系列データ間の距離ｄτ（ｉ，ｊ）が閾値θ以上のときは、時刻Ｔの時系列データ間の距離を計算しないと判断する。ここで、θは単調増加関数であり、例えばθ＝αｔ＋β（ｔ＝Ｔ−τ，αとβは定数）となる。
【０１１０】
また、他の実施の形態として、以下の点だけを変えて処理を行ってもよい。
【０１１１】
事象ｉの圧縮済時系列データの変化量ΔＳｉと、事象ｊの圧縮済時系列データの変化量ΔＳの和から距離ｄ（ｉ，ｊ）を減算した結果、つまりΔＳｉ＋ΔＳｊ−ｄ（ｉ，ｊ）＜＝λであれば時刻Ｔの時系列データ間の距離を計算しないと判断する。ここで時刻τは変化量計算を行った時刻の中で最も時刻Ｔに近い時刻である。また、λは、上記のθと同様の単調増加関数である。
【０１１２】
以上のように、本実施の形態では、複数の時系列データが近い距離にあっても効果が期待できる。また、本実施の形態では、時系列データの集中の具合と無関係な、圧縮済時系列データ間の距離と圧縮済時系列データの変化量に基づいて、距離計算を行うかの判断をするので、時系列データが多次元空間内の特定の場所に集中しても距離計算の回数を減らす効果が期待できる。
【０１１３】
なお、類似時系列データ検出装置１としてコンピュータを機能させるコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に格納したり、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【図面の簡単な説明】
【０１１４】
【図１】類似時系列データ検出装置１の構成図である。
【図２】時系列データ受信部１０の構成図である。
【図３】次元圧縮部１１の構成図である。
【図４】計算判断部１２の構成図である。
【図５】距離計算部１３の構成図である。
【図６】計算結果送信部１４の構成図である。
【図７】判断基準保存部１２２の構成図である。
【図８】計算判断部１２３の構成図である。
【図９】変化量の最大値および最小値の計算を説明するときの説明図である。
【図１０】変化量の最大値および最小値の具体例を説明するときの説明図である。
【図１１】変化量の最大値を説明するときの説明図である。
【図１２】変化量の最小値を計算する際の場合分けを説明するときの説明図である。
【図１３】図１２に示す（１）の場合を説明するときの説明図である。
【図１４】図１２に示す（２）の場合を説明するときの説明図である。
【図１５】図１２に示す（３）の場合を説明するときの説明図である。
【図１６】各事象ｉ，ｊの時系列データでmatchまたはunmatchが連続することを示す図である。
【図１７】条件Ｉを示す図である。
【図１８】条件１を示す図である。
【図１９】条件２を示す図である。
【図２０】条件３を示す図である。
【図２１】条件４を示す図である。
【図２２】条件ＩＩを示す図である。
【図２３】条件５を示す図である。
【図２４】Yunyue Zhu らの手法を示す図である。
【図２５】他の変化量の計算方法を説明するときの説明図である。
【図２６】過去の一定期間内に閾値内の距離にある時系列データの組み合わせを求めるときの当該時系列データを示す図である。
【図２７】互いに近い時系列データを示す図である。
【図２８】Yunyue Zhu らの手法の問題点を示す図である。
【符号の説明】
【０１１５】
１…類似時系列データ検出装置
１０…時系列データ受信部
１１…次元圧縮部
１２…計算判断部
１３…距離計算部
１４…計算結果送信部
１００…データ受信部
１０１…時系列データ保存部
１０２…データ送信部
１１０…データ受信部
１１１…次元圧縮部
１１２…データ送信部
１２０…データ受信部
１２１…変化量計算部
１２２…判断基準保存部
１２３…計算判断部
１２４…データ送信部
１３０…データ受信部
１３１…距離計算部
１３２…閾値保存部
１３３…再計算判断部
１３４…距離再計算部
１３５…計算結果判断部
１３６…データ送信部
１４０…データ受信部
１４１…データ送信部
１２２０…データ受信部
１２２１…次元係数保存部
１２２２…変化量保存部
１２２３…距離保存部
１２２４…閾値保存部
１２２５…データ送信部
１２３０…データ受信部
１２３１…計算判断部
１２３２…データ送信部
【図１】
2006119742.tif 000009
【図２】
2006119742.tif 000010
【図３】
2006119742.tif 000011
【図４】
2006119742.tif 000012
【図５】
2006119742.tif 000013
【図６】
2006119742.tif 000014
【図７】
2006119742.tif 000015
【図８】
2006119742.tif 000016
【図９】
2006119742.tif 000017
【図１０】
2006119742.tif 000018
【図１１】
2006119742.tif 000019
【図１２】
2006119742.tif 000020
【図１３】
2006119742.tif 000021
【図１４】
2006119742.tif 000022
【図１５】
2006119742.tif 000023
【図１６】
2006119742.tif 000024
【図１７】
2006119742.tif 000025
【図１８】
2006119742.tif 000026
【図１９】
2006119742.tif 000027
【図２０】
2006119742.tif 000028
【図２１】
2006119742.tif 000029
【図２２】
2006119742.tif 000030
【図２３】
2006119742.tif 000031
【図２４】
2006119742.tif 000032
【図２５】
2006119742.tif 000033
【図２６】
2006119742.tif 000034
【図２７】
2006119742.tif 000035
【図２８】
2006119742.tif 000036