(57)【要約】【課題】時系列データの類否判定における探索漏れを防ぐとともに過剰探索を防ぐ。また、任意の長さのクエリの時系列データにも対応可能とする。【解決手段】距離計算部４において、距離の下限値が閾値以下の場合に類似として判断することで探索漏れの発生を防ぐとともに、距離の上限値が閾値以下の場合に類似として判断することで過剰探索の発生を防ぐ。また、次元圧縮部３におけるセグメント管理部３２により、時系列データを指数的に長さの異なる複数のセグメントに分割して、次元圧縮係数計算部３３により各セグメントにおける平均値と標準偏差を求めることで、任意の長さのクエリの時系列データにも対応可能とする。【選択図】図１
2007072752.tif 000002
【特許請求の範囲】
【請求項１】
次元圧縮係数計算手段により、類否判断の対象となる一対の時系列データをメモリから読み出し、それぞれについて次元圧縮係数として平均値と標準偏差を求めてメモリに格納するステップと、
上限値・下限値計算手段により、平均値と標準偏差をメモリから読み出し、これらを用いて時系列データの距離の上限値および下限値を求めてメモリに格納するステップと、
類否判断手段により、上限値、下限値、閾値をメモリから読み出し、下限値が閾値以下でかつ上限値が閾値以下の場合に一対の時系列データは類似であると判断するステップと、
を有することを特徴とする類似時系列データ計算方法。
【請求項２】
前記類否判断手段により、下限値が閾値以下でかつ上限値が閾値よりも大きいと判断された場合に、厳密距離計算手段により、次元圧縮前の一対の時系列データをメモリから読み出し、両者の距離を求めてメモリに格納するステップと、
類否判断手段により、次元圧縮前の一対の時系列データの距離、閾値をメモリから読み出し、当該距離が閾値以下の場合に一対の時系列データは類似であると判断するステップと、
を有することを特徴とする請求項１記載の類似時系列データ計算方法。
【請求項３】
セグメント管理手段により、時系列データを指数的に長さの異なる複数のセグメントに分割するステップと、
前記次元圧縮係数計算手段により、時系列データの各セグメントにおける平均値と標準偏差を求めるステップと、
を有することを特徴とする請求項１又は２記載の類似時系列データ計算方法。
【請求項４】
セグメント計数手段により、特定の長さのセグメントの個数を計数するステップと、
セグメント統合手段により、計数した個数が一定値より大きくなった場合にその長さのセグメントを２つ統合するステップと、
前記次元圧縮係数計算手段により、統合後のセグメントにおける平均値と標準偏差を求めるステップと、
を有することを特徴とする請求項３記載の類似時系列データ計算方法。
【請求項５】
セグメント管理手段により、時系列データを均等的な長さの複数のセグメントに分割するステップと、
前記次元圧縮係数計算手段により、時系列データの各セグメントにおける平均値と標準偏差を求めるステップと、
を有することを特徴とする請求項１又は２記載の類似時系列データ計算方法。
【請求項６】
類否判断の対象となる一対の時系列データをメモリから読み出し、それぞれについて次元圧縮係数として平均値と標準偏差を求めてメモリに格納する次元圧縮係数計算手段と、
平均値と標準偏差をメモリから読み出し、これらを用いて時系列データの距離の上限値および下限値を求めてメモリに格納する上限値・下限値計算手段と、
上限値、下限値、閾値をメモリから読み出し、下限値が閾値以下でかつ上限値が閾値以下の場合に一対の時系列データは類似であると判断する類否判断手段と、
を有することを特徴とする類似時系列データ計算装置。
【請求項７】
類否判断の対象となる一対の時系列データをメモリから読み出し、それぞれについて次元圧縮係数として平均値と標準偏差を求めてメモリに格納する処理と、
平均値と標準偏差をメモリから読み出し、これらを用いて時系列データの距離の上限値および下限値を求めてメモリに格納する処理と、
上限値、下限値、閾値をメモリから読み出し、下限値が閾値以下でかつ上限値が閾値以下の場合に一対の時系列データは類似であると判断する処理と、
をコンピュータに実行させることを特徴とする類似時系列データ計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の時系列データの中で類似したものを求める方法、装置、プログラムに関する。
【背景技術】
【０００２】
類似した時系列データを高速に求める処理は様々な分野で利用される。例えば株のオンライントレーディングシステムは大量の株価を監視して、値動きが類似した会社を高速に検索する。移動体位置管理システムは走行している大量の車をセンシングして、似た移動軌跡をしているものを高速に検知する。地震監視システムは大量に配置された地震計からの情報をもとに地震発生時の揺れ方が類似した地点を高速に見つける。
【０００３】
本願では、複数の時系列データのうち、探索時刻から所定の長さのクエリに対して類似した時系列データの組み合わせを探索する問題を扱う。この問題は、時系列データのデータポイント数をｎ、クエリの長さをｌ、閾値をε、時系列データＸ＝（ｘ1，ｘ2，...，ｘn）と時系列データＹ＝（ｙ1，ｙ2，...，ｙn）のユークリッド距離をＤ（Ｘ，Ｙ）とすると以下の条件を満たす時系列データの組み合わせの集合として表現できる。
【数１】
2007072752.tif 000003
【０００４】
一般に、Ｄ（Ｘ，Ｙ）を求めるには高い計算コストがかかる。これは、時系列データが多数のデータポイントを有するためである。このため、時系列データの距離を計算する際には次元圧縮手法が用いられてきた。代表的な次元圧縮手法として、離散フーリエ変換（非特許文献１参照）、離散ウェブレット変換（非特許文献２参照）、特異値分解（非特許文献３参照）などがある。これらの次元圧縮手法は、探索漏れ（類似している時系列データを類似していないと判定すること）がない特徴がある。この探索漏れがない性質はlower bounding lemmaより保証される。lower bounding lemmaとは、次元圧縮後の時系列データをＬ（Ｘ’，Ｙ’）としたときに、Ｌ（Ｘ’，Ｙ’）≦Ｄ（Ｘ，Ｙ）が成り立てば探索漏れが発生しないという補助定理である。すなわち、次元圧縮後の距離が次元圧縮前の距離の下限値であれば探索漏れは発生しないことになる。
【０００５】
なお、ここで扱う時系列データは株価のような離散値と、移動軌跡のような連続値がある。時系列データが離散値である場合、時系列データが類似しているか否かは離散値を用いて時系列データ間の距離が閾値内になるか否かを調べればよい。また、時系列データが連続値である場合は、時系列データは処理する際にサンプリングされ離散値になるため、結局は離散値の処理手法を用いることになる。
【非特許文献１】R.Agrawl, C.Faloutsos, and A.N.Swami. Efficient Similarity Search In Sequence Databases. In Proc. FODO, 1993
【非特許文献２】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
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来の次元圧縮手法は以下の２つの点で問題がある。
【０００７】
１つ目は探索漏れがない性質しか有しないことである。時系列データの類似探索の応用を考えれば、過剰探索（類似していないシーケンスを類似していると判定すること）が発生しない性質も必要である。
【０００８】
２つ目は特定の長さのクエリの時系列データにしか対応できないことである。時系列データの類似探索の応用を考えれば、任意の長さのクエリの時系列データにも対応できる必要がある。
【０００９】
本発明は、上記に鑑みてなされたものであり、その課題とするところは、第１に、探索漏れを防ぐとともに過剰探索を防ぐことにある。第２に、任意の長さのクエリの時系列データにも対応可能とすることにある。
【課題を解決するための手段】
【００１０】
第１の本発明に係る類似時系列データ計算方法は、次元圧縮係数計算手段により、類否判断の対象となる一対の時系列データをメモリから読み出し、それぞれについて次元圧縮係数として平均値と標準偏差を求めてメモリに格納するステップと、上限値・下限値計算手段により、平均値と標準偏差をメモリから読み出し、これらを用いて時系列データの距離の上限値および下限値を求めてメモリに格納するステップと、類否判断手段により、上限値、下限値、閾値をメモリから読み出し、下限値が閾値以下でかつ上限値が閾値以下の場合に一対の時系列データは類似であると判断するステップと、を有することを特徴とする。
【００１１】
本発明にあっては、距離の下限値が閾値以下の場合に類似として判断することで、lower bounding lemmaの補助定理により探索漏れがない性質を保証するとともに、距離の上限値が閾値以下の場合に類似として判断することで、upper bounding lemmaの補助定理により過剰探索がない性質を保証する。
【００１２】
上記類似時系列データ計算方法は、前記類否判断手段により、下限値が閾値以下でかつ上限値が閾値よりも大きいと判断された場合に、厳密距離計算手段により、次元圧縮前の一対の時系列データをメモリから読み出し、両者の距離を求めてメモリに格納するステップと、類否判断手段により、次元圧縮前の一対の時系列データの距離、閾値をメモリから読み出し、当該距離が閾値以下の場合に一対の時系列データを類似であると判断するステップと、を有することを特徴とする。
【００１３】
本発明にあっては、下限値との関係で類似と判断された場合であっても上限値との関係で非類似と判断された場合には、次元圧縮後の時系列データからでは正確な類否判断ができなかったものとして、次元圧縮前の一対の時系列データを用いて両者の距離を求め、この距離と閾値とを比較することで、より厳密な類否判断を行う。
【００１４】
上記類似時系列データ計算方法は、セグメント管理手段により、時系列データを指数的に長さの異なる複数のセグメントに分割するステップと、前記次元圧縮係数計算手段により、時系列データの各セグメントにおける平均値と標準偏差を求めるステップと、を有することを特徴とする。
【００１５】
本発明にあっては、時系列データを指数的に長さの異なる複数のセグメントに分割して、各セグメントにおける平均値と標準偏差を求めることで、任意の長さのクエリの時系列データにも対応可能とする。
【００１６】
上記類似時系列データ計算方法は、セグメント計数手段により、特定の長さのセグメントの個数を計数するステップと、セグメント統合手段により、計数した個数が一定値より大きくなった場合にその長さのセグメントを２つ統合するステップと、前記次元圧縮係数計算手段により、統合後のセグメントにおける平均値と標準偏差を求めるステップと、を有することを特徴とする。
【００１７】
本発明にあっては、計数した特定の長さのセグメントの個数が一定値より大きい場合にその長さのセグメントを２つ統合し、統合後のセグメントにおける平均値と標準偏差を求めることで、次元圧縮の特徴量の更新を可能とする。
【００１８】
上記類似時系列データ計算方法は、セグメント管理手段により、時系列データを均等的な長さの複数のセグメントに分割するステップと、前記次元圧縮係数計算手段により、時系列データの各セグメントにおける平均値と標準偏差を求めるステップと、を有することを特徴とする。
【００１９】
本発明にあっては、時系列データを均等的な長さの複数のセグメントに分割して、各セグメントにおける平均値と標準偏差を求めることで、特定の長さのクエリの時系列データに対応可能とする。
【００２０】
第２の本発明に係る類似時系列データ計算装置は、類否判断の対象となる一対の時系列データをメモリから読み出し、それぞれについて次元圧縮係数として平均値と標準偏差を求めてメモリに格納する次元圧縮係数計算手段と、平均値と標準偏差をメモリから読み出し、これらを用いて時系列データの距離の上限値および下限値を求めてメモリに格納する上限値・下限値計算手段と、上限値、下限値、閾値をメモリから読み出し、下限値が閾値以下でかつ上限値が閾値以下の場合に一対の時系列データは類似であると判断する類否判断手段と、を有することを特徴とする。
【００２１】
第３の本発明に係る類似時系列データ計算プログラムは、類否判断の対象となる一対の時系列データをメモリから読み出し、それぞれについて次元圧縮係数として平均値と標準偏差を求めてメモリに格納する処理と、平均値と標準偏差をメモリから読み出し、これらを用いて時系列データの距離の上限値および下限値を求めてメモリに格納する処理と、上限値、下限値、閾値をメモリから読み出し、下限値が閾値以下でかつ上限値が閾値以下の場合に一対の時系列データは類似であると判断する処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２２】
本発明によれば、距離の上限値と下限値を用いて類否判定を行うことにより、探索漏れや過剰探索の発生を防止することができる。また、時系列データを指数的な長さのセグメントに分割することで、任意の長さのクエリの時系列データにも対応することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施形態について図面を用いて説明する。
【００２４】
図１のブロック図に示すように、本実施の形態における類似時系列データ計算装置１は、データ受信部２、次元圧縮部３、距離計算部４、計算結果送信部５を有する構成である。類似時系列データ計算装置１は、演算処理装置、メモリ、記憶装置等のハードウェアを備えたコンピュータであり、各部の処理は、これらのハードウェアと協働して動作するプログラムによって実行される。各部の処理について概要から説明する。
【００２５】
データ受信部２は、外部から類似か否かの判断対象となる２つの時系列データと各時系列データのクエリの長さとを受信してメモリに記憶させる。次元圧縮部３は、メモリから各時系列データを読み出し、次元圧縮してメモリに記憶させる。距離計算部４は、メモリから次元圧縮後の各時系列データを読み出し、時系列データ間の距離を計算し、その距離に基づいて両者の類否を判断する。この判断が困難な場合には、メモリから次元圧縮前の各時系列データを読み出し、この時系列データ間の距離を計算し、この距離に基づいて類否を判断する。計算結果送信部５は類否判断の結果を外部へ送信する。
【００２６】
図２のブロック図に示すように、次元圧縮部３は、データ受信部３１、セグメント管理部３２、次元圧縮係数計算部３３、計算結果送信部３４を有する。
【００２７】
データ受信部３１は、次元圧縮前の時系列データを受信する。セグメント管理部３２は、各セグメントの長さを管理し、時系列データを指数的に長さの異なる複数のセグメント、あるいは均等的な長さの複数のセグメントに分割する。次元圧縮係数計算部３３は、時系列データの各セグメントにおける平均値と標準偏差を次元圧縮の係数として求めることで、次元圧縮を行う。計算結果送信部は次元圧縮後の時系列データを距離計算部４へ送信する。
【００２８】
図３のブロック図に示すように、セグメント管理部３２は、データ受信部３２１、セグメント計数部３２２、セグメント統合部３２３、データ送信部３２４を有する。データ受信部３２１は、次元圧縮前の時系列データを受信する。セグメント計数部３２２は特定の長さのセグメントの個数を計数する。セグメント統合部３２３は、計数した個数が一定値より大きい場合に、その長さのセグメントを２つ統合する。データ送信部３２４は、統合後のセグメントの組み合わせを次元圧縮係数計算部３３に送信する。
【００２９】
図４のブロック図に示すように、距離計算部４は、データ受信部４１、利用セグメント決定部４２、距離係数計算部４３、上限値計算部４４、下限値計算部４５、類否判定部４６、厳密距離計算部４７、判定結果送信部４８を有する。
【００３０】
データ受信部４１は、次元圧縮前の時系列データ、クエリの長さ、次元圧縮後の時系列データ（すなわち次元圧縮計数）を受信する。利用セグメント決定部４２は、次元圧縮後の距離を計算するときに用いるセグメントを決定する。距離係数計算部４３は、次元圧縮係数を用いて時系列データ間の距離係数を計算する。上限値計算部４４は、距離係数を用いて距離の上限値を求めてメモリに格納する。下限値計算部４５は、距離係数を用いて距離の下限値を求めてメモリに格納する。類否判定部４６は、上限値、下限値、閾値をメモリから読み出し、下限値が閾値以下でかつ上限値が閾値以下の場合に一対の時系列データを類似であると判断する。
【００３１】
厳密距離計算部４７は、類否判定部４６により下限値が閾値以下であるが上限値が閾値よりも大きいと判断された場合に、次元圧縮前の一対の時系列データをメモリから読み出し、この時系列データ間の距離を求めてメモリに格納する。この場合、類否判定部４６は、この距離と閾値とをメモリから読み出し、この距離が閾値以下の場合に時系列データを類似と判断する。このように厳密な距離を用いることで正確な判断を行う。判定結果送信部４８は類否判断の結果を計算結果送信部５へ送信する。
【００３２】
次元圧縮部３で時系列データを次元圧縮しても過剰探索が発生しないことはupper bounding lemmaにより保証される。upper bounding lemmaとは、次元圧縮後のシーケンスの距離をＵ（Ｘ’，Ｙ’）としたときにＤ（Ｘ，Ｙ）≦Ｕ（Ｘ’，Ｙ’）が成立すれば過剰探索が発生しないとする補助定理である。すなわち、次元圧縮後の距離が次元圧縮前の距離の上限値であれば過剰探索は発生しないことになる。
【００３３】
また、探索漏れが発生しないことはlower bounding lemmaより保証される。lower bounding lemmaとは、次元圧縮後の時系列データをＬ（Ｘ’，Ｙ’）としたときに、Ｌ（Ｘ’，Ｙ’）≦Ｄ（Ｘ，Ｙ）が成り立てば探索漏れが発生しないという補助定理である。すなわち、次元圧縮後の距離が次元圧縮前の距離の下限値であれば探索漏れは発生しないことになる。
【００３４】
次に、類似時系列データ計算装置１における各部の処理について詳細に説明する。
【００３５】
まず、次元圧縮部３では、セグメント管理部３２により、シーケンスＸ（ｎデータポイント）をＮ個の特定の長さのセグメントに分割してｉ番目のセグメントをσiとしたとき、次元圧縮係数計算部３３では、σiの長さをｌ（σi）、平均をａｖ（σi）、標準偏差をｓｄ（σi）として次元圧縮後のシーケンスＸ’を次のように３つの係数のタプルで表現する。
【数２】
2007072752.tif 000004
【００３６】
ここでｌ（σi）については以下の式が成り立つ。
【数３】
2007072752.tif 000005
【００３７】
またｘi:jをσiのｊ番目のデータポイントとすると、次元圧縮係数計算部３３は、ａｖ（σi）とｓｄ（σi）を次のように計算する。
【数４】
2007072752.tif 000006
【数５】
2007072752.tif 000007
【００３８】
続いて、距離計算部４での処理について図５のフローチャートを参照しながら説明する。この処理では、任意の長さのクエリに対して、距離の下限値を計算するのか、上限値を計算するのかにより、次元圧縮後の距離計算に用いるセグメントが異なる。すなわち、ステップ１（図５において「Ｓ１」と示す。以下同じ）において、利用セグメント決定部４２は、図６に示すように、下限値を求めるときにはクエリより短いシーケンスの中で最も長いシーケンスにおけるセグメントを利用セグメントとして決定し、上限値を求めるときにはクエリより長いシーケンスの中で最も短いシーケンスにおけるセグメントを利用セグメントとして決定する。各シーケンスは、複数のセグメントを集約して構成される。下限値の計算に用いるセグメントの中で最も番号の小さいものをＮl、上限値の計算に用いるセグメントの中で最も番号の小さいものをＮuとすると、ＮlとＮuは以下の式を満たすセグメントのうちそれぞれ最大のものと最小のものである。
【数６】
2007072752.tif 000008
【００３９】
ステップ２において、距離係数計算部４３は、次式により距離係数Ｄ１，Ｄ２，Ｄ３を計算する。
【数７】
2007072752.tif 000009
【数８】
2007072752.tif 000010
【数９】
2007072752.tif 000011
【００４０】
ステップ３において、下限値計算部４５は、次式により距離の下限値Ｌ（Ｘ’，Ｙ’）を計算する。
【数１０】
2007072752.tif 000012
【００４１】
ここでＬ（Ｘ’，Ｙ’）は以下のように書き換えることができ、Ｄ１，Ｄ２，Ｄ３を予め計算しておくことで、それらをＬ（Ｘ’，Ｙ’）の計算に利用できる。
【数１１】
2007072752.tif 000013
【００４２】
ステップ４において、類否判定部４６は、下限値と閾値を比較し、下限値が閾値より大きい場合には、時系列データは類似ではないと判断して処理を終了する（ステップ５）。一方、下限値が閾値以下の場合には、ステップ６へ進む。
【００４３】
ステップ６では、上限値計算部４４が、次式により距離の上限値Ｕ（Ｘ’，Ｙ’）を計算する。
【数１２】
2007072752.tif 000014
【００４４】
ここで、Ｎu≦ＮlなのでＵ（Ｘ’，Ｙ’）は以下のように書き換えることができ、Ｄ１，Ｄ２，Ｄ３を予め計算しておくことで、それらをＵ（Ｘ’，Ｙ’）の計算にも利用できる。
【数１３】
2007072752.tif 000015
【００４５】
ステップ７において、類否判定部４６は、上限値と閾値を比較し、上限値が閾値以下の場合には、時系列データは類似と判断して処理を終了する（ステップ８）。一方、上限値が閾値よりも大きい場合には、時系列データは類似ではないと判断してステップ９へ進む。
【００４６】
ステップ９では、厳密距離計算部４７により、次元圧縮前の時系列データを用いて両者のユークリッド距離を求め、その距離を類否判定部４６へ送る。
【００４７】
ステップ１０において、類否判定部４６は、厳密距離計算部４７が計算した距離と閾値とを比較し、その距離が閾値以下の場合には時系列データは類似と判断し（ステップ１１）、それ以外の場合には非類似と判断して処理を終了する（ステップ１２）。
【００４８】
次に、上記のように求めた下限値Ｌ（Ｘ’，Ｙ’）、上限値Ｕ（Ｘ’，Ｙ’）を用いることで、Ｌ（Ｘ’，Ｙ’）≦Ｄ（Ｘ，Ｙ）≦Ｕ（Ｘ’，Ｙ’）となることを証明する。まずＬ（Ｘ’，Ｙ’）≦Ｄ（Ｘ，Ｙ）となることを示す。
【００４９】
Ｄ（Ｘ，Ｙ）はユークリッド距離なのでｋ≧ｌとすると明らかに以下のことが成り立つ。
【数１４】
2007072752.tif 000016
【００５０】
ｋにおいては以下の式が成り立つとする。
【数１５】
2007072752.tif 000017
【００５１】
ここでΔｘi:j＝ａｖ（σi）−ｘi:jとすると
【数１６】
2007072752.tif 000018
【００５２】
ここで
【数１７】
2007072752.tif 000019
【００５３】
であるため
【数１８】
2007072752.tif 000020
【００５４】
となる。ここでΔｘi:jをベクトルとみなしたとき、‖Δｘi:j‖をベクトルΔｘi:jの大きさとする。すると内積の定義式より
【数１９】
2007072752.tif 000021
【００５５】
となる。なお、ここでθiはベクトルΔｘi:jとベクトルΔｙi:jのなす角とする。cosθi≦１であるので、
【数２０】
2007072752.tif 000022
【００５６】
となる。また同様に、ｋ≦１、cosθi≧１とすれば、Ｄ（Ｘ，Ｙ）≦Ｕ（Ｘ’，Ｙ’）となることも示せる。
【００５７】
次に、セグメント管理部３２において指数的に長さの異なるセグメントを管理する処理について詳細に説明する。セグメント管理部３２は、レベルｈのセグメントの長さを２hとし、図７の模式図に示すように、処理時間によってレベルｈを引き上げることで、セグメントの長さが指数的に大きくなるようにセグメント分割を行う。このようにするのは、任意の長さのクエリに対応するためである。これにより、クエリが短い場合も長い場合も、下限値と上限値を計算したときの相対的な誤差は同等になる。
【００５８】
セグメント統合部３２３は、各レベルにおいてセグメントの個数がキャパシティｃより大きくなった場合に、そのレベルにおける２つのセグメントを統合し、次元圧縮の特徴量の更新をインクリメンタル的に行う。
【００５９】
例えばｃ＝２としたときの具体的な更新処理について図８の模式図および図９のフローチャートを用いて説明する。
【００６０】
ステップ２１（図９で「Ｓ２１」と示す。以下同じ）で、セグメント計数部３２２は、レベルｈを初期値０に設定する。そして、ステップ２２で、レベルｈ＝０におけるセグメントの個数を計数する。ここでは、セグメントの個数を、レベルｈ＝０で２、ｈ＝１で２、ｈ＝２で１とする。ここでシーケンスデータが流入してくるとｈ＝０のセグメントは３個になる。セグメントの個数がｃ（＝２）よりも大きくなったので（ステップ２４）、ステップ２５で、セグメント統合部３２３は、セグメントを統合してｈ＝１のセグメントを作成する。するとレベルｈ＝１のセグメントも３個になるので、ステップ２６でレベルｈを１インクリメントして同様に処理する。この処理をレベルｈが時系列データの最大のレベルとなるまで繰り返す（ステップ２３）。結果として、更新後のセグメントの個数はレベルｈ＝０で１、レベルｈ＝１で１、レベルｈ＝２で２となる。
【００６１】
セグメントσiとσi+1を統合して新たなセグメントσ′iとするときの次元圧縮の特徴量については、以下のように更新する。
【数２１】
2007072752.tif 000023
【００６２】
次に、セグメント管理部３２において均等的な長さのセグメントを管理する処理について詳細に説明する。ここでは、任意の長さのクエリではなく、固定長のクエリに対して類似時系列データを探索することを想定する。この場合は一番前のセグメントは逐次更新し、一番後のセグメントはキャパシティｃ毎に更新する。次元圧縮係数計算部３３は、キャパシティｃの値ごとにまとめた均等的な長さの各セグメントにおける時系列データの平均値と標準偏差を求めてメモリに保持する。
【００６３】
ｃ＝２であるときの具体的な更新処理について図１０の模式図を用いて説明する。次元圧縮の特徴量は４つであり、更新前（ｔ＝１）においてセグメントの長さは１番目が４、２番目が４、３番目が４、４番目が０である。ここでシーケンスデータが流入してくると（ｔ＝２）、セグメントの長さは１番目が４、２番目が４、３番目が４、４番目が１となる。次のシーケンスデータが流入してくると（ｔ＝３）、セグメントの長さは１番目が２、２番目が４、３番目が４、４番目が２となる。
【００６４】
セグメントは逐次またはキャパシティｃごとに更新するが、このときの次元圧縮の係数は長さｌi＋ｌi+1のセグメントをσ’iとし、長さｌiのセグメントをσiとし、長さｌi+1のセグメントをσi+1としたとき以下の式を用いて更新する。
【数２２】
2007072752.tif 000024
【００６５】
以上、説明したように、本実施の形態によれば、距離計算部４において、距離の下限値が閾値以下の場合に類似として判断することで、lower bounding lemmaの補助定理により探索漏れがない性質を保証するとともに、距離の上限値が閾値以下の場合に類似として判断することで、upper bounding lemmaの補助定理により過剰探索がない性質を保証する。これにより、探索漏れの発生および過剰探索の発生を防ぐことができる。
【００６６】
本実施の形態によれば、セグメント管理部３２により、時系列データを指数的に長さの異なる複数のセグメントに分割して、次元圧縮係数計算部３３が各セグメントにおける平均値と標準偏差を求めることで、任意の長さのクエリの時系列データにも対応することができる。
【００６７】
本実施の形態によれば、類否判定部４６により、下限値との関係で類似と判断された場合であっても上限値との関係で非類似と判断された場合には、次元圧縮後の時系列データからでは正確な類否判断ができなかったものとして、厳密距離計算部４７により、次元圧縮前の一対の時系列データを用いて両者のユークリッド距離を求め、再度類否判定部４６によりユークリッド距離と閾値との比較を行うことで、より厳密な類否判断を行うことができる。
【００６８】
本実施の形態によれば、セグメント計数部３２２により計数した特定の長さのセグメントの個数が一定値より大きくなった場合に、セグメント統合部３２３により、その長さのセグメントを２つ統合し、次元圧縮係数計算部３３により、統合後のセグメントにおける平均値と標準偏差を求めることで、次元圧縮の特徴量の更新を可能にすることができる。
【００６９】
本実施の形態によれば、セグメント管理部３２により、時系列データを均等的な長さの複数のセグメントに分割して、次元圧縮係数計算部３３により、各セグメントにおける平均値と標準偏差を求めることで、特定の長さのクエリの時系列データに対応することができる。
【００７０】
本実施の形態によれば、時系列データを指数的または均等的な長さのセグメントに分割することにより、相対的に小さい誤差で時系列データの類否判断を行うことができる。
【図面の簡単な説明】
【００７１】
【図１】一実施の形態における類似時系列データ計算装置の構成を示すブロック図である。
【図２】上記類似時系列データ計算装置における次元圧縮部の構成を示すブロック図である。
【図３】上記次元圧縮部におけるセグメント管理部の構成を示すブロック図である。
【図４】上記類似時系列データ計算装置における距離計算部の構成を示すブロック図である。
【図５】距離計算部における処理を示すフローチャートである。
【図６】下限値の計算に用いるセグメントと上限値の計算に用いるセグメントを説明するための模式図である。
【図７】任意の長さのクエリに対して相対的な誤差は変わらないことを説明するための模式図である。
【図８】特徴量を更新するときの処理を説明するための模式図である。
【図９】特徴量の更新の処理を示すフローチャートである。
【図１０】クエリが固定長の場合における特徴量を更新するときの処理を説明するための模式図である。
【符号の説明】
【００７２】
１…類似時系列データ計算装置
２…データ受信部
３…次元圧縮部
４…距離計算部
５…計算結果送信部
３１…データ受信部
３２…セグメント管理部
３３…次元圧縮係数計算部
３４…計算結果送信部
４１…データ受信部
４２…利用セグメント決定部
４３…距離係数計算部
４４…上限値計算部
４５…下限値計算部
４６…類否判定部
４７…厳密距離計算部
４８…判定結果送信部
３２１…データ受信部
３２２…セグメント計数部
３２３…セグメント統合部
３２４…データ送信部
【図１】
2007072752.tif 000025
【図２】
2007072752.tif 000026
【図３】
2007072752.tif 000027
【図４】
2007072752.tif 000028
【図５】
2007072752.tif 000029
【図６】
2007072752.tif 000030
【図７】
2007072752.tif 000031
【図８】
2007072752.tif 000032
【図９】
2007072752.tif 000033
【図１０】
2007072752.tif 000034