(57)【要約】【課題】時系列データの類似判断における計算コストを低く抑える。【解決手段】絞込部３により、多次元インデクス構造を用いて時系列データを絞り込み、類似判断部４により、次元圧縮した後の時系列データ間の距離を求め、この距離が所定の閾値以下の場合に類似と判定する。このように、次元圧縮後の時系列データを用いて類似判断することで、計算コストを低く抑える。また、次元圧縮前の時系列データ間の距離が次元圧縮後の距離以下となるように次元圧縮することで、全て正しい類似判断の結果を得る。さらに、次元圧縮後の時系列データを用いた類似判断が難しい場合には、次元圧縮前の時系列データを用いて類似判断を行うことで、全て正しくかつ見過ごしのない類似判断の結果を得る。【選択図】図１
2006227835.tif 000002
【特許請求の範囲】
【請求項１】
時系列データを受信して第１メモリに記憶させる受信手段と、
第１メモリから読み出された時系列データについて、多次元インデクス構造を用いて類似判定の対象を絞り込んで第２メモリに記憶させる絞込手段と、
第２メモリから読み出された時系列データを次元圧縮して第３メモリに記憶させる次元圧縮手段と、
第３メモリから読み出された次元圧縮後の時系列データ間の距離を計算して第４メモリに記憶させる次元圧縮後距離計算手段と、
第４メモリから読み出された距離が所定の閾値以下の場合に類似と判定する第１判定手段と、
を有することを特徴とする類似時系列データ計算装置。
【請求項２】
前記次元圧縮手段は、次元圧縮前の時系列データ間の距離が次元圧縮後の距離以下となるように次元圧縮することを特徴とする請求項１記載の類似時系列データ計算装置。
【請求項３】
第４メモリから読み出された距離が前記閾値よりも大きい場合に、第２メモリから読み出された次元圧縮前の時系列データ間の距離を計算して第５メモリに記憶させる次元圧縮前距離計算手段と、
第５メモリから読み出された距離が所定の閾値以下の場合に類似と判定する第２判定手段と、
を有することを特徴とする請求項１又は２記載の類似時系列データ計算装置。  
【請求項４】
前記次元圧縮手段は、第２メモリから読み出された時系列データを一定のフレームで分割したときの時系列データのレンジをフレーム毎に計算して第６メモリに記憶させるレンジ計算手段と、
前記レンジの中央を示すミッド・レンジをフレーム毎に計算して第７メモリに記憶させるミッド・レンジ計算手段と、を有し、
前記レンジと前記ミッド・レンジをもって次元圧縮の結果とすることを特徴とする請求項１乃至３のいずれかに記載の類似時系列データ計算装置。
【請求項５】
前記次元圧縮手段は、
前記レンジ計算手段により計算されたレンジおよび前記ミッド・レンジ計算手段により計算されたミッドレンジを保存する保存手段と、
現在のフレームについて次元圧縮する際に、前のフレームで用いたレンジおよびミッド・レンジの使用だけで済むか否かの可否を判断する計算判断手段と、
前記計算判断手段が可と判断した場合に、保存手段から前のフレームのレンジおよびミッド・レンジを読み出してこれらを用いて次元圧縮し、前記計算判断手段が否と判断した場合に、保存手段から現在のフレームについて前記レンジ計算手段が計算したレンジおよび前記ミッド・レンジ計算手段が計算したミッド・レンジを読み出してこれらを用いて次元圧縮する逐次計算手段と、
を有することを特徴とする請求項４記載の類似時系列データ計算装置。
【請求項６】
受信手段により時系列データを受信して第１メモリに記憶させるステップと、
絞込手段により第１メモリから読み出された時系列データについて多次元インデクス構造を用いて類似判定の対象を絞り込むステップと、
次元圧縮手段により第２メモリから読み出された時系列データを次元圧縮して第３メモリに記憶させるステップと、
次元圧縮後距離計算手段により第３メモリから読み出された次元圧縮後の時系列データ間の距離を計算して第４メモリに記憶させるステップと、
第１判定手段により第４メモリから読み出された距離が所定の閾値以下の場合に類似と判定するステップと、
を有することを特徴とする類似時系列データ計算方法。
【請求項７】
前記次元圧縮手段は、次元圧縮前の時系列データ間の距離が次元圧縮後の距離以下となるように次元圧縮することを特徴とする請求項６記載の類似時系列データ計算方法。
【請求項８】
次元圧縮前距離計算手段により、第４メモリから読み出された距離が前記閾値よりも大きい場合に、第２メモリから読み出された次元圧縮前の時系列データ間の距離を計算して第５メモリに記憶させるステップと、
第２判定手段により第５メモリから読み出された距離が所定の閾値以下の場合に類似と判定するステップと、
を有することを特徴とする請求項６又は７記載の類似時系列データ計算方法。  
【請求項９】
レンジ計算手段により、第２メモリから読み出された時系列データを一定のフレームで分割したときの時系列データのレンジをフレーム毎に計算して第６メモリに記憶させるステップと、
前記レンジの中央を示すミッド・レンジをフレーム毎に計算して第７メモリに記憶させるステップと、を有し、
前記レンジと前記ミッド・レンジをもって次元圧縮の結果とすることを特徴とする請求項６乃至８のいずれかに記載の類似時系列データ計算方法。
【請求項１０】
保存手段により、前記レンジ計算手段により計算されたレンジおよび前記ミッド・レンジ計算手段により計算されたミッドレンジを保存するステップと、
計算判断手段により、現在のフレームについて次元圧縮する際に、前のフレームで用いたレンジおよびミッド・レンジの使用だけで済むか否かの可否を判断するステップと、
逐次計算手段により、前記計算判断手段が可と判断した場合に、保存手段から前のフレームのレンジおよびミッド・レンジを読み出してこれらを用いて次元圧縮し、前記計算判断手段が否と判断した場合に、保存手段から現在のフレームについて前記レンジ計算手段が計算したレンジおよび前記ミッド・レンジ計算手段が計算したミッド・レンジを読み出してこれらを用いて次元圧縮するステップと、
を有することを特徴とする請求項９記載の類似時系列データ計算方法。
【請求項１１】
計算機に対して、
時系列データを受信して第１メモリに記憶させるステップと、
第１メモリから読み出された時系列データについて多次元インデクス構造を用いて類似判定の対象を絞り込むステップと、
第２メモリから読み出された時系列データを次元圧縮して第３メモリに記憶させるステップと、
第３メモリから読み出された次元圧縮後の時系列データ間の距離を計算して第４メモリに記憶させるステップと、
第４メモリから読み出された距離が所定の閾値以下の場合に類似と判定するステップと、
を実行させることを特徴とする類似時系列データ計算プログラム。
【請求項１２】
前記次元圧縮は、次元圧縮前の時系列データ間の距離が次元圧縮後の距離以下となるように次元圧縮することを特徴とする請求項１１記載の類似時系列データ計算プログラム。
【請求項１３】
第４メモリから読み出された距離が前記閾値よりも大きい場合に、第２メモリから読み出された次元圧縮前の時系列データ間の距離を計算して第５メモリに記憶させるステップと、
第５メモリから読み出された距離が所定の閾値以下の場合に類似と判定するステップと、
を実行させることを特徴とする請求項１１又は１２記載の類似時系列データ計算プログラム。  
【請求項１４】
第２メモリから読み出された時系列データを一定のフレームで分割したときの時系列データのレンジをフレーム毎に計算して第６メモリに記憶させるステップと、
前記レンジの中央を示すミッド・レンジをフレーム毎に計算して第７メモリに記憶させるステップと、を実行させ、
前記レンジと前記ミッド・レンジをもって次元圧縮の結果とすることを特徴とする請求項１１乃至１３のいずれかに記載の類似時系列データ計算プログラム。
【請求項１５】
計算されたレンジおよびミッド・レンジを保存手段に保存するステップと、
現在のフレームについて次元圧縮する際に、前のフレームで用いたレンジおよびミッド・レンジの使用だけで済むか否かの可否を判断するステップと、
可と判断した場合に、保存手段から前のフレームのレンジおよびミッド・レンジを読み出してこれらを用いて次元圧縮し、否と判断した場合に、保存手段から現在のフレームについて計算したレンジおよびミッド・レンジを読み出してこれらを用いて次元圧縮するステップと、
を有することを特徴とする請求項１４記載の類似時系列データ計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の時系列データの中で類似したものを求める装置、方法、プログラムに関する。
【背景技術】
【０００２】
類似した時系列データを高速に求める処理は様々な分野で利用される。例えば株のオンライントレーディングシステムは、大量の株価を監視して、値動きが類似した銘柄を高速に検索する。移動体位置管理システムは、走行している大量の車をセンシングして、似た移動軌跡しているものを高速に検知する。地震監視システムは、大数配置された地震計からの情報をもとに地震発生時の揺れ方が類似した地点を高速に見つける。
【０００３】
時系列データが類似しているかは、時系列データ間の距離があらかじめ決められた閾値ε以下になるかどうかで判断される。しかし、類似した時系列データを求める際に、総当りで距離を求めたのでは計算コストが高い。よって、高速に類似時系列データを求めるには計算コストの低い方法が必要である。
【０００４】
なお、ここで扱う時系列データは株価のような離散値と移動軌跡のような連続値がある。時系列データが離散値である場合、時系列データが類似しているかは離散値を用いて時系列データ間の距離が閾値内になるか調べればよい。また時系列データが連続値である場合は、時系列データは処理する際にサンプリングされ離散値になるので、結局は離散値の処理手法を用いる。
【０００５】
時系列データ間の距離関数としてはユークリッド距離を用いる。２つの時系列データをＳ（ｓ1，ｓ2，・・・，ｓn）とＳ′＝（ｓ′1，ｓ′2，・・・，ｓ′n）とし、ｎ＝ｎ′であるときユークリッド距離Ｄ（Ｓ，Ｓ′）は次式で計算される。
【数１】
2006227835.tif 000003
【０００６】
類似した時系列データを求める問題は、Whole MatchingとSubsequence Matchingの２つのタイプに分けられる。Whole Matchingは、等しい長さの時系列データから類似したものを求める問題である。またSubsequence Matchingは、問い合わせ時系列データＳとそれより長い時系列データＳ′を比較し、時系列データＳ′の中で時系列データＳと類似した部分を求める問題である。
【０００７】
Subseqquence MatchingはWhole Matchingへと置き換えることができる。これは、図６に示すように、時系列データＳ′に長さがｎのｌ個の窓を逐次的に重ねて部分的な時系列データのコピーを作成すると、時系列データＳ′の部分的なコピーと時系列データＳは等しい長さとなるからである。
【０００８】
類似した時系列データを求めるのに良く用いられるフレームワークとしてＧＥＭＩＮＩ(GEneric Multimedia INdexIng method）がある（非特許文献１）。ＧＥＭＩＮＩは、Ｒ*-tree（非特許文献２）やＳＲ-tree（非特許文献３）等を用いて時系列データを多次元のインデクス構造に索引付け、類似時系列データを求める。時系列データを索引付けするのは、時系列データはｎ次元空間（ｎはある程度大きな数となることが多い）の１つのポイントとして捉えられるからである。
【０００９】
しかし、時系列データをｎ次元のまま索引付けしても計算コストを下げる効果は期待できない。多次元インデクス構造は次元数が１０前後より多くなると性能が劣化するからである。そのため、ＧＥＭＩＮＩでは時系列データをＮ次元に次元圧縮して索引付けしている。
【００１０】
次元圧縮して類似時系列データを求める場合、誤差の発生に留意しなければならない。ここで誤差とは、false negativeとfalse positiveの２通りが考えられる。false negativeとは類似している時系列データを類似していないと判断することであり、false positiveとは類似していない時系列データを類似していると判断することである。２つの誤差のうちfalse negativeが発生しないことがより重要である。false negativeの発生は結果の正確性に影響するからである。
【００１１】
次元圧縮して類似時系列データを求めてもfalse negativeが発生しないことを保証する定理としてlower bounding lemmaが知られている。これは、次式(lower bounding condition）が成り立てばfalse negativeが発生しないという定理である。
【数２】
2006227835.tif 000004
【００１２】
なお、lower bounding conditionが成り立つ次元圧縮手法として離散フーリエ変換（非特許文献１）、離散ウェブレット変換（非特許文献４）、特異値分解（非特許文献５）などが知られている。
【００１３】
ＧＥＭＩＮＩでは、search processとpost processの２つの処理を行って類似時系列データを求める。search processではlower bounding conditionが成り立つ次元圧縮手法によって構築した多次元インデクス構造を用いて類似時系列データを求める。search processの結果には多少のfalse positiveが含まれる。そのため、post processではsearch processの結果に対して次元圧縮前の時系列データ間の距離を計算して、false positiveを取り除く。
【００１４】
なお、ここで示した類似時系列データの計算方法は蓄積された時系列データが対象であったが、逐次流入してくる時系列データを対象にした計算方法としてStat Stream（非特許文献６）が挙げられる。Stat Streamで用いる多次元インデクス構造はgrid structureである。grid structureはＲ*-tree等と比較して高速に構築できる特徴がある。なおStat StreamではＧＥＭＩＮＩにおけるpost processを行わないため結果に多少のfalse positiveが含まれる。
【非特許文献１】R.Agrawl, C.Faloutsos, and A.N.Swami. Efficient Similarity Search In Sequence Databases. In Proc. FODO, 1993
【非特許文献２】N.Beckmann, H.P.Kriegel, R.Schneider, B.Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In Proc. SIGMOD, 1990
【非特許文献３】片山紀生，佐藤真、ＳＲ-tree：高次元点データに対する最近接検索のためのインデックス構造の提案、電子情報通信学会論文誌、1997
【非特許文献４】K.Chan, A.W.Fu. Efficient Time Series Matching by Wavelets. In Proc. ICDE, 1999
【非特許文献５】F.Korn, H.V.Jagadish, C.Faloutsos. Efficient Supporting Ad Hoc Queries in Large Datasets of Time Sequences. In Proc. SIGMOD, 1997
【非特許文献６】Y.zhu, D.Shasha. StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time. In Proc, VLDB, 2002
【発明の開示】
【発明が解決しようとする課題】
【００１５】
post processは、search processの結果からfalse positiveを取り除くために行うが、問題点として計算コストが高いことが挙げられる。
【００１６】
post processの計算コストはｍ×ｎ（「Ｏ（ｍｎ）」と称す。以下同じ）となる。ここで、ｍはsearch processにおいて類似候補とされた時系列データの組み合わせの数、ｎは時系列データが含むデータポイントの数である。計算コストがＯ（ｍｎ）となるのはsearch processにおいて類似候補とされた時系列データの組み合わせすべてに対して次元圧縮前の距離を計算するためである。
【００１７】
多くの長い時系列データの類似性を調べようとするとpost processにおける計算コストは高くなる。類似しているかを計算する時系列データの数が多くなるとｍは結果的に大きな値となり、また類似しているかを計算する時系列データが長くなるとｎは大きな値になるからである。
【００１８】
本発明は、上記に鑑みてなされたものであり、その課題とするところは、類似している時系列データを算出する際の計算コストを低く抑えることにある。
【課題を解決するための手段】
【００１９】
第１の本発明に係る類似時系列データ計算装置は、時系列データを受信して第１メモリに記憶させる受信手段と、第１メモリから読み出された時系列データについて、多次元インデクス構造を用いて類似判定の対象を絞り込んで第２メモリに記憶させる絞込手段と、第２メモリから読み出された時系列データを次元圧縮して第３メモリに記憶させる次元圧縮手段と、第３メモリから読み出された次元圧縮後の時系列データ間の距離を計算して第４メモリに記憶させる次元圧縮後距離計算手段と、第４メモリから読み出された距離が所定の閾値以下の場合に類似と判定する第１判定手段と、を有することを特徴とする。
【００２０】
本発明にあっては、多次元インデクス構造を用いて絞り込まれた時系列データを次元圧縮し、次元圧縮後の時系列データ間の距離が所定の閾値以下の場合に類似と判定することで、次元圧縮後の時系列データを用いて類似判断するので、計算コストを低く抑えることができる。
【００２１】
本類似時系列データ計算装置において、前記次元圧縮手段は、次元圧縮前の時系列データ間の距離が次元圧縮後の距離以下となるように次元圧縮することを特徴とする。
【００２２】
本発明にあっては、次元圧縮前の時系列データ間の距離が次元圧縮後の距離以下となるように次元圧縮することで、upper bounding conditionを満たす次元圧縮を行うことになるので、全て正しい類似判断の結果を得ることができる。
【００２３】
本類似時系列データ計算装置は、さらに第４メモリから読み出された距離が前記閾値よりも大きい場合に、第２メモリから読み出された次元圧縮前の時系列データ間の距離を計算して第５メモリに記憶させる次元圧縮前距離計算手段と、第５メモリから読み出された距離が所定の閾値以下の場合に類似と判定する第２判定手段と、を有することを特徴とする。
【００２４】
本発明にあっては、次元圧縮後の時系列データを用いた類似判断が難しい場合に、次元圧縮前の時系列データを用いて類似判断を行うことで、全て正しくかつ見過ごしのない類似判断の結果を得ることができる。
【００２５】
本類似時系列データ計算装置において、前記次元圧縮手段は、第２メモリから読み出された時系列データを一定のフレームで分割したときの時系列データのレンジをフレーム毎に計算して第６メモリに記憶させるレンジ計算手段と、第２メモリから読み出された時系列データを一定のフレームで分割したときのレンジの中央を示すミッド・レンジをフレーム毎に計算して第７メモリに記憶させるミッド・レンジ計算手段と、を有し、前記レンジと前記ミッド・レンジをもって次元圧縮の結果とすることを特徴とする。
【００２６】
本発明にあっては、フレーム毎にレンジとミッド・レンジを計算することで、次元圧縮を実現している。
【００２７】
本類似時系列データ計算装置において、前記次元圧縮手段は、前記レンジ計算手段により計算されたレンジおよび前記ミッド・レンジ計算手段により計算されたミッドレンジを保存しておく保存手段と、現在のフレームについて次元圧縮する際に、前のフレームで用いたレンジおよびミッド・レンジの使用だけで済むか否かの可否を判断する計算判断手段と、前記計算判断手段が可と判断した場合に、保存手段から前のフレームのレンジおよびミッド・レンジを読み出してこれらを用いて次元圧縮し、前記計算判断手段が否と判断した場合に、保存手段から現在のフレームについて前記レンジ計算手段が計算したレンジおよび前記ミッド・レンジ計算手段が計算したミッド・レンジを読み出してこれらを用いて次元圧縮する逐次計算手段と、を有することを特徴とする。
【００２８】
本発明にあっては、前のフレームで使用したレンジおよびミッド・レンジを現在のフレームにおける次元圧縮にも利用することで、同じレンジおよびミッド・レンジを繰り返し計算することがないので、計算コストを更に低く抑えることができる。
【００２９】
第２の本発明に係る類似時系列データ計算方法は、受信手段により時系列データを受信して第１メモリに記憶させるステップと、絞込手段により第１メモリから読み出された時系列データについて多次元インデクス構造を用いて類似判定の対象を絞り込むステップと、次元圧縮手段により第２メモリから読み出された時系列データを次元圧縮して第３メモリに記憶させるステップと、次元圧縮後距離計算手段により第３メモリから読み出された次元圧縮後の時系列データ間の距離を計算して第４メモリに記憶させるステップと、第１判定手段により第４メモリから読み出された距離が所定の閾値以下の場合に類似と判定するステップと、を有することを特徴とする。
【００３０】
第３の本発明に係る本類似時系列データ計算プログラムは、計算機に対して、時系列データを受信して第１メモリに記憶させるステップと、第１メモリから読み出された時系列データについて多次元インデクス構造を用いて類似判定の対象を絞り込むステップと、第２メモリから読み出された時系列データを次元圧縮して第３メモリに記憶させるステップと、第３メモリから読み出された次元圧縮後の時系列データ間の距離を計算して第４メモリに記憶させるステップと、第４メモリから読み出された距離が所定の閾値以下の場合に類似と判定するステップと、を実行させることを特徴とする。
【発明の効果】
【００３１】
本発明によれば、類似している時系列データを算出する際の計算コストを低く抑えることができる。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の実施形態について図面を用いて説明する。
【００３３】
図１に示すように、本実施形態における類似時系列データ計算装置１は、データ受信部２、絞込部３、類似判断部４、計算結果送信部５を有する。
【００３４】
データ受信部２は、外部のセンサなどから時系列データを受信して、内蔵の第１メモリに記憶させる。絞込部３は、第１メモリから時系列データを読み出し、多次元インデクス構造などを用いて類似する時系列データの絞込みを行い、内蔵の第２メモリに記憶させる。この絞込部３の処理は、従来技術のsearch processに相当するものとしてもよい。類似判断部４は、絞込部３で絞り込まれた時系列データを精査し、類似する時系列データを正確に判断する。計算結果送信部５は、類似する時系列データの組み合わせを外部へ送信する。これらの各部の処理は、類似時系列データ計算装置にインストールされたプログラムによって実行される。
【００３５】
図２に示すように、類似判断部４は、データ受信部１１、次元圧縮部１２、第１距離計算部１３、第２距離計算部１４、計算結果送信部１５を有する。これら各部の処理は、プログラムによって実行される。
【００３６】
データ受信部１１は、絞込部３により第２メモリから読み出された時系列データの組み合わせを受信するとともに、データ受信部２により第１メモリから読み出された次元圧縮前の時系列データを受信する。
【００３７】
次元圧縮部１２は、絞込部３から受信した時系列データを次元圧縮して内蔵の第３メモリに記憶させる。
【００３８】
第１距離計算部１３では、後述するように次元圧縮後距離計算部により、次元圧縮後の時系列データを第３メモリから読み出し、この時系列データ間の距離を計算して第４メモリに記憶させる。詳細な処理については後述する。
【００３９】
第２距離計算部１４では、後述するように次元圧縮前距離計算部により、第２メモリから読み出された次元圧縮前の時系列データ間の距離を計算して内蔵の第５メモリに格納する。詳細な処理については後述する。
【００４０】
計算結果送信部１５は、第１距離計算部１３、第２距離計算１４により類似と判定された時系列データの組み合わせを出力する。
【００４１】
図３に示すように、次元圧縮部１２は、データ受信部２１、計算判断部２２、レンジ計算部２３、ミッド・レンジ計算部２４、保存部２５、逐次計算部２６、データ送信部２７を有する。各部の処理は、プログラムによって実行される。
【００４２】
データ受信部２１は、第２メモリから読み出された次元圧縮前の時系列データをデータ受信部１１から受け取る。
【００４３】
レンジ計算部２３は、時系列データを一定のフレームで分割したときの時系列データのレンジをフレーム毎に計算して内蔵の第６メモリに記憶させる。レンジとは、データ値の範囲をいう。
【００４４】
ミッド・レンジ計算部２４は、時系列データを一定のフレームで分割したときのレンジの中心を示すミッド・レンジをフレーム毎に計算して内蔵の第７メモリに記憶させる。次元圧縮とは、フレーム毎にレンジおよびミッド・レンジを計算することをいう。
【００４５】
保存部２５は、レンジ計算部２３により計算されたレンジ、ミッド・レンジ計算部２４により計算されたミッド・レンジを保存する。
【００４６】
計算判断部２２は、現在のフレームについて次元圧縮する際に、前のフレームで用いたレンジおよびミッド・レンジを使用するだけで済むか否かの可否を判断する。
【００４７】
逐次計算部２６は、計算判断部２２が可と判断した場合に、保存部２５から前のフレームのレンジおよびミッド・レンジを読み出し、これらを新たなレンジ、ミッド・レンジとすることで次元圧縮の結果とする。また、計算判断部２２が否と判断した場合には、現在のフレームについてレンジ計算部２３が計算したレンジおよびミッド・レンジ計算部２４が計算したミッド・レンジをもって次元圧縮の結果とする。このようにして次元圧縮の計算を逐次的に行う。逐次計算部２６は、レンジとミッド・レンジで次元圧縮された時系列データを第３メモリに記憶する。
【００４８】
データ送信部２７は、第３メモリから次元圧縮後の時系列データを読み出して出力する。
【００４９】
図４に示すように、第１距離計算部１３は、データ受信部３１、次元圧縮後距離計算部３２、第１判定部３３、データ送信部３４を有する。各部の処理は、プログラムで実行される。
【００５０】
データ受信部３１は、第３メモリから読み出された次元圧縮後の時系列データを受け取る。
【００５１】
次元圧縮後距離計算部３２は、次元圧縮後の時系列データ間の距離を計算して内蔵の第４メモリに記憶させる。
【００５２】
第１判定部３３は、第４メモリから距離を読み出すとともに別のメモリから所定の閾値を読み出し、この距離が閾値以下の場合に類似と判定する。
【００５３】
データ送信部３４は、類似と判定された時系列データの組み合わせを計算結果送信部１５に出力するとともに、距離が閾値よりも大きい時系列データの組み合わせを第２距離計算部１４に出力する。
【００５４】
図５に示すように、第２距離計算部１４は、データ受信部４１、次元圧縮前距離計算部４２、第２判定部４３、データ送信部４４を有する。各部の処理は、プログラムによって実行される。
【００５５】
データ受信部４１は、第１距離計算部１３から距離を計算すべき時系列データの組み合わせを受信するとともに、第２メモリから読み出された次元圧縮前の時系列データをデータ受信部１１から受信する。
【００５６】
次元圧縮前距離計算部４２は、受信した組み合わせについての次元圧縮前の時系列データ間の距離を計算して第５メモリに記憶させる。この距離は、例えばユークリッド距離とする。
【００５７】
第２判定部４３は、第５メモリから距離を読み出すとともに、別のメモリから所定の閾値を読み出し、この距離が閾値以下の場合に類似と判定する。
【００５８】
データ送信部４４は、類似と判断された時系列データの組み合わせを出力する。
【００５９】
次に、次元圧縮部１２での処理について詳細に説明する。まず、次元圧縮部１２で用いる次元圧縮手法が満たされなければならない条件upper bounding conditionについて説明する。
【００６０】
絞込部３が、類似していない時系列データを求め、これを除外することで絞り込みを行うのに対して、次元圧縮部１２は類似している時系列データを求める。次元圧縮後距離計算部３２が次元圧縮後の距離を用いて類似する時系列データを求めてもfalse positiveが発生しないことを保証する補助定理として新たにupper bounding lemmaを導入する。
【００６１】
upper bounding lemmaは、次式（upper bounding condition）が成立すればfalse positiveが発生しないという定理である。
【数３】
2006227835.tif 000005
【００６２】
upper bounding lemmaは以下のように証明できる。upper bounding lemmaにおいてfalse positiveが発生しないことを保証するためには、Ｄreal（Ｓ，Ｓ′）＞εであれば次式が成り立つ必要がある。
【数４】
2006227835.tif 000006
【００６３】
ここでupper bounding conditionより次式が成り立つ。
【数５】
2006227835.tif 000007
【００６４】
このようにupper bounding lemmaは証明できる。よって、false positiveの発生を防ぐためには、次元圧縮部１２で用いる次元圧縮手法がupper bounding conditionを満たしていなければならない。このことから、次元圧縮部１２は、次元圧縮前の時系列データ間の距離が次元圧縮後の時系列データ間の距離以下となるように次元圧縮する。
【００６５】
次に、次元圧縮部１２で用いる次元圧縮手法ＰＲＡ（Piecewise Range Approximation）について説明する。
【００６６】
図７に示すように、ＰＲＡではｎデータポイントを有する時系列データをＮ個の等しいサイズのフレーム（データポイント）に分割し、各フレームのレンジとミッド・レンジを次元圧縮の結果とする。レンジはフレーム内に存在するデータ値の範囲であり、ミッド・レンジはレンジの中心値である。ＰＲＡにおける距離は、各フレームにおける時系列データ間の最も遠い最大値と最小値の差を用いて計算される。
【００６７】
次元圧縮後の時系列データは、次式のように計数のタプルとなる。
【数６】
2006227835.tif 000008
【００６８】
ここで、ｊ番目の係数のｒsjは、ｊ番目のフレームのレンジであり、レンジ計算部２３により次のように計算される。
【数７】
2006227835.tif 000009
【００６９】
ここでｍａｘsjはフレームにおける最大値を、ｍｉｎsjはフレームにおける最小値を表している。
【００７０】
また、ｊ番目の係数のｍsjは、ｊ番目のフレームのミッド・レンジであり、ミッド・レンジ計算部２４により次のように計算される。
【数８】
2006227835.tif 000010
【００７１】
次に計算コストについて説明する。
【００７２】
Subsequence MatchingにおいてＰＲＡによる次元圧縮計算コストは、一度計算したレンジ、ミッド・レンジを繰り返し使用しない場合には、Ｏ（ｌｎ）となる。これはｌ個の窓に対してＮ回レンジとミッド・レンジを求めるときの時系列データの長さがｎ／Ｎだからである。
【００７３】
これに対し、レンジ、ミッド・レンジを繰り返し使用する場合には、計算コストをＯ((ｌＮ−ｈ）ｎ／Ｎ＋ｈ）と低くすることができる。ここで、ｈは一度算出したレンジ、ミッド・レンジを使用して次元圧縮を計算できる回数である。計算コストがこのようになるのは、ｌ個の窓に対してＮ回のレンジとミッド・レンジを求める総数ｌ・Ｎ回の計算において、レンジ、ミッド・レンジを繰り返し使用できない場合は計算コストがｎ／Ｎであるのに対して、繰り返し使用できる場合は計算コストがｌであるからである。このような計算ができるのは、窓を逐次的に重ねていくので、フレームの最大値と最小値も逐次的に変化するためである。以下では、この点について説明するため、計算判断部２２、逐次計算部２６での処理について詳細に説明する。
【００７４】
窓を逐次的に重ねていく場合、フレームにおける最大値を以下のように更新する。なおここでは、ｒk・sjをｋ番目の窓のｊ番目のレンジとし、ｍk・sjをｋ番目の窓のｊ番目のミッド・レンジとし、ｍａｘk・sjをｋ番目の窓のｊ番目のフレームの最大値とし、ｍｉｎk・sjをｋ番目の窓のｊ番目のフレームの最小値とする。
【数９】
2006227835.tif 000011
【００７５】
ｉ−ｉ）は、図８に示すように、フレームに入る時系列データが１つ前のフレームの最大値より大きくなる場合に、フレームに入る時系列データを新しい最大値とすることを表している。
【００７６】
ｉ−ii）は、図９に示すように、フレームから出る時系列データがフレームの最大値での場合に、フレームから出る時系列データにより最大値は小さくなるため、新たにフレームの最大値を求めることを表している。
【００７７】
ｉ−iii）は、図１０に示すように、フレームにおける最大値が変化しない場合に、１つ前のフレームの計算結果を利用して最大値を計算することを表している。
【００７８】
また、フレームにおける最小値を以下のように更新する。
【数１０】
2006227835.tif 000012
【００７９】
ii−ｉ）は、図１１に示すように、フレームに入る時系列データが１つ前のフレームの最小値より小さい場合に、フレームに入る時系列データを新しい最小値とすることを表している。
【００８０】
ii−ii）は、図１２に示すように、フレームから出る時系列データがフレームの最小値の場合に、フレームから出る時系列データにより最小値は大きくなるため、新たにフレームの最小値を求めることを表している。
【００８１】
ii−iii）は、図１０に示すように、フレームにおける最小値が変化しない場合に、１つ前のフレームの計算結果を利用して最小値を計算することを表している。
【００８２】
次元圧縮を行う際に、ｉ−ii）またはii−ii）の条件に当てはまらなければ、既に計算したレンジ、ミッド・レンジを利用することができる。
【００８３】
次に、次元圧縮後距離計算部３２における次元圧縮後の時系列データ間の距離の計算方法について説明する。
【００８４】
ＰＲＡで次元圧縮した後の時系列データ間の距離を以下のように定める。
【数１１】
2006227835.tif 000013
【００８５】
ここで定めた距離がupper bounding conditionを満たすことを以下説明する。
【００８６】
ユークリッド距離は次のように書き換えることができる。
【数１２】
2006227835.tif 000014
【００８７】
ここで次式のようになる。
【数１３】
2006227835.tif 000015
【００８８】
ユークリッド距離においては三角不等式が成り立つため、Ｄ（ｓjk，ｓ′jk）は以下のようになる。
【数１４】
2006227835.tif 000016
【００８９】
よって、次式のようになる。
【数１５】
2006227835.tif 000017
【００９０】
上記の式により、ＰＲＡがupper bounding conditionを満たすことがわかる。
【００９１】
したがって、本実施の形態によれば、多次元インデクス構造を用いて絞り込まれた時系列データを次元圧縮し、次元圧縮後の時系列データ間の距離が所定の閾値以下の場合に類似と判定することで、次元圧縮後の時系列データを用いて類似判断するので、計算コストを低く抑えることができる。
【００９２】
本実施の形態によれば、次元圧縮前の時系列データ間の距離が次元圧縮後の距離以下となるように次元圧縮することで、upper bounding conditionを満たす次元圧縮を行うことになるので、全て正しい類似判断の結果を得ることができる。
【００９３】
本実施の形態によれば、次元圧縮後の時系列データを用いた類似判断が難しい場合に、次元圧縮前の時系列データを用いて類似判断を行うことで、全て正しくかつ見過ごしのない類似判断の結果を得ることができる。
【００９４】
本実施の形態によれば、前のフレームで使用したレンジおよびミッド・レンジを現在のフレームにおける次元圧縮にも利用することで、同じレンジおよびミッド・レンジを繰り返し計算することがないので、計算コストを更に低く抑えることができる。
【００９５】
ここで、類似判断の精度および計算コストについて説明する。例えば、実施例１として、次元圧縮後距離計算部３２で次元圧縮した後の時系列データを用いて距離を算出するものとし、次元圧縮部１２でupper bounding conditionやlower bounding conditionを満たす必要がないものとする。この場合、例えば１００個の類似時系列データがあった場合には、９０個の正解と２０個の不正解が求められる。計算コストは、従来のＯ（ｍｎ）からＯ（ｍＮ）に低くなる（∵Ｎ≪ｎ）。
【００９６】
実施例２として、実施例１においてupper bounding conditionを満たす次元圧縮を行うものとする。この場合、類似と判断する計算の結果は全て正しいが、全ての類似した時系列データは求められない。例えば、１００個の類似時系列データがあった場合、９０個の正解と０個の不正解が得られる。計算コストは、従来のＯ（ｍｎ）からＯ（ｍＮ）に低くなる。
【００９７】
実施例３として、実施例２において、類似判断が難しい場合に次元圧縮前の時系列データを用いて距離を算出するものとする。この場合、類似の判断は全て正しく、かつ類似データの見落としはない。例えば、１００個の類似時系列データがあった場合、１００個の正解と０個の不正解が求められる。計算コストは、従来のＯ（ｍｎ）からＯ（ｍＮ＋（ｍ−Ｍ）ｎ）に低くなる。
【図面の簡単な説明】
【００９８】
【図１】一実施の形態における類似時系列データ計算装置の構成を示すブロック図である。
【図２】上記類似時系列データ計算装置における類似判断部の構成を示すブロック図である。
【図３】上記類似判断部における次元圧縮部の構成を示すブロック図である。
【図４】上記類似判断部における第１距離計算部の構成を示すブロック図である。
【図５】上記類似判断部における第２距離計算部の構成を示すブロック図である。
【図６】Subsequence MatchingをWhole Matchingに置き換えることができることを説明するための図である。
【図７】次元圧縮を説明するための図である。
【図８】フレームに入る時系列データが最大値になる場合を説明するための図である。
【図９】フレームから出る時系列データが最大値になる場合を説明するための図である。
【図１０】フレームにおける最大値が変化しない場合を説明するための図である。
【図１１】フレームに入る時系列データが最小値になる場合を説明するための図である。
【図１２】フレームから出る時系列データが最小値になる場合を説明するための図である。
【符号の説明】
【００９９】
１…類似時系列データ計算装置
２…データ受信部，３…絞込部
４…類似判断部，５…計算結果送信部
１１…データ受信部，１２…次元圧縮部
１３…第１距離計算部
１４…第２距離計算部
１５…計算結果送信部
２１…データ受信部，２２…計算判断部
２３…レンジ計算部
２４…ミッド・レンジ計算部
２５…保存部，２６…逐次計算部
２７…データ送信部
３１…データ受信部
３２…次元圧縮後距離計算部
３３…第１判定部
３４…データ送信部，４１…データ受信部
４２…次元圧縮前距離計算部
４３…第２判定部，４４…データ送信部
【図１】
2006227835.tif 000018
【図２】
2006227835.tif 000019
【図３】
2006227835.tif 000020
【図４】
2006227835.tif 000021
【図５】
2006227835.tif 000022
【図６】
2006227835.tif 000023
【図７】
2006227835.tif 000024
【図８】
2006227835.tif 000025
【図９】
2006227835.tif 000026
【図１０】
2006227835.tif 000027
【図１１】
2006227835.tif 000028
【図１２】
2006227835.tif 000029