JP4451332B2 - 類似時系列データ計算装置、および類似時系列データ計算プログラム - Google Patents

Description

本発明は、複数の時系列データの中で類似したものを求める類似時系列データ計算装置、および類似時系列データ計算プログラムに関する。

これまで、時系列データストリームは、株取引、気候観測、メディア処理、医療等の様々な分野のサービスに応用されてきた。時系列データ処理の分野で多く研究されている問題の１つとして、蓄積された時系列データの中から類似したものを求めることがある。この技術のアプリケーションとしては以下のような例が挙げられる。

・過去の株価の推移が同じ銘柄を見つける。

・過去に同じような気温のパターンを示した年を見つける。

・蓄積された動画から類似したものを見つける。

近年、時系列データを検知するセンサの小型化・低価格化が進んだことから、大量の時系列センサデータストリームを利用したサービスが可能になりつつある。そのため、今後はセンサから出力された時系列データの処理技術の重要性が高まることが考えられる。センサデータストリームの特徴の１つに大量の時系列データが逐次流入してくることが挙げられる。

逐次流入してくる時系列データの中から類似したものを求める技術のアプリケーションとしては以下の例が挙げられる。

・リアルタイムに売り上げパターンが同じ商品を見つける。

・地震発生時に揺れ方が同じ地点を見つける。

・現時刻において同じ移動をしている人物を見つける。

本願では、類似している時系列データを求める問題を次のように定める。「ｍ個の時系列データのうち、現在時刻Ｔから過去の一定期間内（ｎデータポイント）における距離が閾値ε内の時系列データの組み合わせを求める」
なお、ここで扱う時系列データには、株価のような離散値と移動軌跡のような連続値がある。離散値の場合、時系列データが類似しているか否かは、離散値を用いて時系列データ間の距離が閾値内にあるか否かを調べればよい。また連続値の場合、時系列データは処理する際にサンプリングされ離散値になるので、結局は離散値の処理手法を用いることになる。

２つの時系列データＳ^ｕ，Ｓ^ｖ間の距離関数として次のようなユークリッド距離を用いる。

ユークリッド距離を用いて時系列データ間の距離を定義することによって、図１５に示すように、類似する時系列データを求める問題は多次元空間内で近い点を求める問題に置き換えることができる。

また、時系列データ間の距離をユークリッド距離を用いて定めることにより、本願における問題は、閾値をεとしたとき次の条件を満たす時系列データの組み合わせの集合を求める問題となる。

類似した時系列データを高速に求めるフレームワークとしてＧＥＭＩＮＩ（GEneric Multimedia INdexIng method）がある（非特許文献１参照）。ＧＥＭＩＮＩでは、まず時系列データを次元圧縮し、この次元圧縮後の時系列データの特徴量を用いてＲ^＊−ｔｒｅｅ（非特許文献２参照）等の空間インデクスを構築し、空間インデクスを用いて類似した時系列データの距離を絞り込む。そして絞り込まれた候補について、次元圧縮前の時系列データの距離を計算して、類似した時系列データを正確に求める。

従来ＧＥＭＩＮＩは、蓄積された時系列データを対象に多く用いられてきた。この場合は、空間インデクスの構築に時間をかけることができる。しかし、逐次流入してくる時系列データを対象にする場合には、空間インデクスを高速に構築する必要がある。

また空間インデクスを利用して類似時系列データを求める場合、誤差の発生に留意しなければならない。ここで誤差とは、false negativeとfalse positiveの２通りが考えられる。false negativeとは、類似している時系列データを類似していないと判断してしまうことであり、false positiveとは、類似していない時系列データを類似していると判断してしまうことである。この２つの誤差のうち、false negativeが発生しないことがより重要である。false positiveの方は、類似判断の結果を精査することによって取り除くことが可能であり、またfalse negativeの発生は結果の正確性に影響するからである。

false negativeが発生せず、かつ逐次流入してくる時系列データを対象とした空間インデクス手法としてgrid structureがある（非特許文献３参照）。grid structureは、図１６に示すように、時系列データが存在する多次元空間をグリッド構造により複数の領域に分割し、見過ごしなく類似する時系列データの組み合わせを絞り込む手法である。grid structureは、離散フーリエ変換によってＮ次元に次元圧縮された多次元空間を、離散フーリエ変換の係数のはじめの数個を利用して、幅が一定の範囲のグリッド構造に分割する。すると、ある時系列データに類似する組み合わせの候補は、その時系列データが属する領域とそれに隣接する領域に限定される。これにより、全ての時系列データの組み合わせを計算する必要がないため、計算回数を削減できる。なお、図１６では、３次元空間を２次元のグリッド構造に分割した例を示している。
R.Agrawl, C.Faloutsos, and A.N.Swami, "Efficient Similarity Search In Sequence Databases", In Proc. FODO, 1993 N.Bechmann, H.P.Kriegel, R.Schneider, B.Seeger, "R*-tree:An Efficient and Robust Access Method for Points and Rectangles", In Proc. SIGMOD, 1990 Y.zhu, D.Shasha, "State Stream:Statistical Monitoring of Thousands of Data Streams in Real Time", In Proc. VLDB, 2002

ところで、grid structureの問題点として、多次元空間を有効に分割できないことが挙げられる。これは、grid structureでは単一の軸を基準に多次元空間を分割するからである。時系列データ間の距離は多次元空間内の距離でもあるので、単一の軸を基準に多次元空間を分割しても精度が低い。また、grid structureは、離散フーリエ変換のように係数のはじめの数個に多くのエネルギーが集まる次元圧縮法を用いないと大きな効果がない。また、grid structureは、候補領域に存在する時系列データ全てに対して次元圧縮後の距離を計算し、類似する候補であるかを計算しなければならない。

本発明は、上記に鑑みてなされたものであり、その課題とするところは、逐次流入してくる時系列データの類似候補を求めるに際し、多次元空間をより効率的に分割することにある。

第１の本発明に係る類似時系列データ計算装置は、ｎ個のデータからなるｎ次元の時系列データを受信して第１メモリに記憶させるデータ受信手段と、第１メモリから読み出された時系列データを次元圧縮して第２メモリに記憶させる次元圧縮手段と、多次元空間における同心超球の中心点を決定して第３メモリに記憶させる中心点決定手段と、第３メモリから読み出された中心点を中心とする同心超球構造に多次元空間を分割して、第２メモリから読み出された時系列データの類似の組み合わせの候補を絞り込んで第４メモリに記憶させる候補検索手段と、を有し、前記中心点決定手段は、次元圧縮後の時系列データの中からランダムにサンプルを選択するサンプル手段と、前記サンプル手段によりサンプリングされた次元圧縮後の時系列データを、多次元空間を均一に分割させるクラスタリング手法によりクラスタリングして第５メモリに記憶させるクラスタリング手段と、第５メモリから読み出されたクラスタリングの中心を多次元空間における中心点の位置として決定して第３メモリに記憶させる中心点位置計算手段と、を具備し、前記候補検索手段は、時系列データの類似を判断するための閾値を定数で除した値を刻み幅とし、多次元空間を前記中心点から前記刻み幅で同心超球構造に分割し、分割領域に番号を与える空間分割手段と、前記中心点と時系列データとの距離により、第２メモリから読み出された時系列データが属する分割領域の番号を求める手段と、第２メモリから読み出された２つの時系列データに対して、それぞれの時系列データが属する分割領域の番号の差と、前記定数との関係から次元圧縮後の時系列データの類似候補を絞り込み、その類似候補の組み合わせを第４メモリに記憶させる候補決定手段と、を具備することを特徴とする。

本発明にあっては、多次元空間における同心超球の中心点を決定し、この中心点を中心とする同心超球構造に多次元空間を分割することで、全ての軸を用いた多次元空間の分割が可能となるので、より効率的である。

本発明にあっては、すべての時系列データについてクラスタリングを行い、クラスタリングの結果を用いて中心点を決定することで、適切に中心点を配置することが可能となる。

本発明にあっては、ランダムにサンプリングされた時系列データを対象にクラスタリングを行い、このクラスタリングの結果を用いて中心点を決定することで、中心点を高速に計算することが可能となる。

本発明にあっては、多次元空間を中心点から時系列データの類似を判断するための閾値の刻みで同心超球構造に分割することで、類似する時系列データが存在する候補領域を、時系列データが属する領域およびこの領域に直接的に隣接する領域のみに限定することができ、候補領域の数を減少させることが可能となる。

本発明にあっては、前記の閾値εよりも小さい値ε／ｃ（ｃ＞１）の刻みで多次元空間を分割することで、領域が細かく分割されるので候補領域を小さくすることが可能となる。これにより、中心点Ｏ_ｉからそれぞれＲ^Ｏｉ _ｕ，Ｒ^Ｏｉ _ｖ個の領域に属する時系列データ同士は、Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ≦ｃの関係にあれば次元圧縮後の距離を計算しなくとも類似する時系列データの候補とすることができる。

第２の本発明に係る類似時系列データ計算プログラムは、上記類似系列データ計算装置を構成する各手段としてコンピュータを機能させることを特徴とする。

本発明によれば、類似する時系列データを求める際に多次元空間をより効率的に分割することができる。

以下、本発明の最良の形態について図面を用いて説明する。

図１のブロック図に示すように、本実施形態における類似時系列データ計算装置１は、データ受信部２、空間インデクス部３、類似判断部４、計算結果送信部５を有する。各部における処理は、本類似時系列データ計算装置１にインストールされたコンピュータプログラムによって実行される。各部の処理の詳細な説明は後述するが、その概要は次のとおりである。

データ受信部２は、逐次流入してくる時系列データを受信して内部のメモリに記憶させる。

空間インデクス部３は、データ受信部２のメモリから読み出された時系列データを受け取り、この時系列データについて空間インデクスを用いて類似する時系列データの候補を絞り込んで内部のメモリに記憶させる。

類似判断部４は、空間インデクス部３のメモリから読み出された類似時系列データの候補に対応する絞り込み前の時系列データをデータ受信部２のメモリから読み出し、この絞り込み前の時系列データ間の距離を求めて内部のメモリに記憶させるとともに、この距離が一定範囲内にある時系列データを類似と判断する。

計算結果送信部５は、類似と判断された時系列データの組み合わせを外部へ送信する。

空間インデクス部３では、CS structure(Concentric hyper Sphere structure)法を採用する。この手法は、多次元空間を同心超球構造に分割して、類似する時系列データの組み合わせを絞り込むものである。具体的には、図２に示すように、多次元空間上に複数の中心点を設定し、中心点からの距離に応じて所定の閾値ε以下の幅で多次元空間を分割する。この敷値εは、時系列データ間の類似性判断に用いる閾値である。このように閾値ε以下の幅で分割した場合、ある時系列データに類似する候補領域は、その時系列データが属する領域およびこの領域に一定の範囲で隣接する複数の領域に限定される。なお、図２では、３次元空間に対して２つの同心球を重ねて多次元空間を閾値εの幅で分割した場合に、類似する時系列データの候補領域は、その時系列データが属する領域およびこの領域に２つまでの範囲で隣接する複数の領域に限定される例を示している。以下、空間インデクス部３の構成について説明する。

図３のブロック図に示すように、空間インデクス部３は、データ受信部３１、次元圧縮部３２、中心点決定部３３、候補検索部３４、データ送信部３５を有する。各部における処理は、コンピュータプログラムによって実行される。

データ受信部３１は、データ受信部２のメモリから読み出された時系列データを受け取る。

次元圧縮部３２は、受け取った時系列データを次元圧縮して内部のメモリに記憶させる。この次元圧縮の手法には、例えば、離散フーリエ変換を用い、その係数をもって次元圧縮の結果とする。もちろん、他の次元圧縮法を用いても良い。

中心点決定部３３は、多次元空間における同心超球の中心点を決定して内部のメモリに記憶させる。この処理の詳細については後述する。

候補検索部３４は、中心点決定部３３のメモリから読み出された中心点を中心とする同心超球構造に多次元空間を分割し、類似する時系列データの組み合わせの候補を絞り込んで内部のメモリに記憶させる。この処理の詳細についても後述する。

データ送信部３５は、類似する時系列データの組み合わせの候補を類似判断部４に出力する。

図４のブロック図に示すように、中心点決定部３３は、データ受信部３３１、サンプル部３３２、クラスタリング部３３３、中心点計算部３３４、データ送信部３３５を有する。各部における処理は、コンピュータプログラムによって実行される。

データ受信部３３１は、次元圧縮部３２のメモリから読み出された次元圧縮後の時系列データを受け取って内部のメモリに記憶させる。

サンプル部３３２は、データ受信部３３１のメモリに格納された次元圧縮後の時系列データの中からランダムにサンプルを選択して内部のメモリに格納する。

クラスタリング部３３３は、サンプル部３３２のメモリからサンプルとして選択された次元圧縮後の時系列データを読み出し、これをクラスタリングして内部のメモリに記憶させる。

中心点計算部３３４は、クラスタリング部３３３のメモリから読み出されたクラスタリングの結果を用いて多次元空間における中心点の位置を決定して内部のメモリに記憶させる。

データ送信部３３５は、メモリから読み出された中心点の位置とサンプルとして選択された次元圧縮後の時系列データとを空間インデクス部３の候補検索部３４へ出力する。

図５のブロック図に示すように、候補検索部３４は、データ受信部３４１、空間分割部３４２、候補領域決定部３４３、候補決定部３４４、データ送信部３４５を有する。各部における処理は、コンピュータプログラムによって実行される。

データ受信部３４１は、送信されてきた中心点の位置と次元圧縮後の時系列データを受け取って内部のメモリに記憶させる。

空間分割部３４２は、データ受信部３４１のメモリから読み出された中心点を中心とする所定の閾値の刻みの同心超球構造に多次元空間を分割する。この閾値としては、時系列データが類似しているかを判断するための閾値εよりも小さい値ε／ｃ（ｃ＞１）とする。

候補領域決定部３４３は、分割された多次元空間内における類似する時系列データの候補を選択するための候補領域を決定する。この決定に際しては、分割の結果あるいは次元圧縮後の時系列データが属する領域を用いる。

候補決定部３４４は、決定された候補領域から次元圧縮後の時系列データの類似候補を絞り込み、その類似候補の組み合わせを内部のメモリに記憶させる。

データ送信部３４５は、候補決定部３４４のメモリから読み出された時系列データの類似候補の組み合わせを空間インデクス部３のデータ送信部３５へ出力する。

次に、空間インデクス部３の次元圧縮部３２で用いる次元圧縮法が満たさなければならない条件について説明する。

次元圧縮部３２では、次元圧縮を行ってもfalse negativeが発生してはならない。このことを保証する定理としてlower bounding lemmaが知られている。これは、次式（lower bounding condition）が成り立てばfalse negativeは発生しないという定理である。

Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)≦Ｄreal(Ｓ^ｕ，Ｓ^ｖ) （３）
ここで、各関数の定義は次の通りである。

Ｄreal(Ｓ^ｕ，Ｓ^ｖ)：次元圧縮前の時系列データＳ^ｕ，Ｓ^ｖの距離
Ｄdigest（Ｓ'^ｕ，Ｓ'^ｖ）：次元圧縮後の時系列データＳ'^ｕ，Ｓ'^ｖの距離
よって、次元圧縮部３２では、このlower bounding conditionが成り立つ離散フーリエ変換法、離散ウェブレット変換法、特異値分解法などの手法を用いる。なお、ここでは、次元圧縮前の時系列データ間の距離をユークリッド距離とするが、これに限られるものではない。

次に、中心点決定部３３における同心超球の中心点を決定する手法について説明する。

CS structureでは、多次元空間において複数の中心点が近い位置に集まっていると、図６に示すように、複数の中心点による候補領域の広くが重複してしまう。しかし、効率的な絞り込みを行うためには、中心点は、多次元空間内で均一に分散していた方が望ましい。そこで、多次元空間内に中心点を均一に分散させるために、ここではクラスタリング部３３３を設けてK-means法によるクラスタリング手法を用いる。K-means法のアルゴリズムは以下の通りである。

Ｓｔｅｐ１（初期値の決定）：Ｋ個（Ｋは任意の正整数）のクラスタの初期分割をランダムに設定する。

Ｓｔｅｐ２（個体の割り当て）：それぞれの個体を最も近い代表点に割り当てる。

Ｓｔｅｐ３（代表点の更新）：すべてのクラスタの中心が変化しなければ終了し、終了しない場合には各クラスタの代表点を計算してＳｔｅｐ２へ戻る。

なお、ここでは、時系列データを個体、各クラスタの中心（各クラスタの要素の平均）を超球の中心点と置き換えるものとする。

本実施の形態では、逐次流入してくる時系列データが対象であるので、中心点を高速に計算できることが望ましい。そのため、K-means法における計算コストを低く抑える必要がある。K-means法の計算コストは、Ｓ×Ｍ×ｒ×ｄとなることが知られている。ここで、Ｓはクラスタ（中心点）の数、Ｍは個体（時系列データ）の数、ｒはK-means法の計算が収束するまでの繰り返し回数、ｄは距離を計算する際の次元数である。本実施の形態では、個体の数Ｍを次のように削減する。

Ｍ＝ｍ×ｋ （４）
ここで、ｍは時系列データの総数、ｋはすべての時系列データの中からどの程度の数を用いてK-means法を行うかを決定するサンプル率（０〜１）である。ｋの値が小さい程、少ないデータポイントから中心点を決定するので、高速に多次元空間を分割できる一方、適切でない位置が中心点となることもある。

次に、候補検索部３４における類似時系列データの候補の決定手法について説明する。 本実施の形態では、多次元空間をε／ｃ（ｃ＞１）の幅で分割するが、時系列データが非類似であるか否かを時系列データが属する領域をもとに判断する。図７に例示するように、中心点Ｏ_ｉから次元圧縮後の時系列データＳ'^ｕ がＲ^Ｏｉ _ｕ（＞０）個目の領域にあり、時系列データＳ'^ｖがＲ^Ｏｉ _ｖ（＞０）個目の領域にあるとき、次式（５）となる領域に属する時系列データは類似している可能性があると判断し、次式（６）となる領域に属する時系列データは非類似と判断する。

|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|＜ｃ＋１ （５）
|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|≧ｃ＋１ （６）
類似の可能性がある時系列データについては、次元圧縮後の距離を計算し、この距離が一定の範囲内にあるか否かで類似する時系列データの候補であるか否かを判断する。なお、図７の例では、ｃ＝１．５、Ｒ^Ｏｉ _ｕ＝２、Ｒ^Ｏｉ _ｖ＝４またはＲ^Ｏｉ _ｖ＝５である。Ｒ^Ｏｉ _ｖ＝４であれば類似する可能性がある時系列データとなり、Ｒ^Ｏｉ _ｖ＝５であれば非類似の時系列データとなる。

空間インデクスを用いる場合、false negativeが発生しないことが必要である。そこで、候補検索部３４では、このことを保証する定理contractive transform lemmaを新たに導入する。

contractive transform lemmaとは、次式（contractive transform condition）が成立すればfalse negativeは発生しないというものである。

Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)≦Ｄreal(Ｓ^ｕ，Ｓ^ｖ) （７）
ここで、各関数の定義は次の通りである。

Ｄreal(Ｓ^ｕ，Ｓ^ｖ)：次元圧縮前の時系列データＳ^ｕ，Ｓ^ｖの距離
Ｄdigest（Ｓ'^ｕ，Ｓ'^ｖ）：次元圧縮後の時系列データＳ'^ｕ，Ｓ'^ｖの距離
Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)：多次元空間を分割し新たな距離空間を設定した後の時系列データＳ'^ｕ，Ｓ'^ｖの距離
contractive transform lemmaは、以下のように証明できる。false negativeが発生しないことを保証するためには、Ｄreal(Ｓ^ｕ，Ｓ^ｖ)≦εであればＤcontractive(Ｓ'^ｕ，Ｓ'^ｖ)≦εでなければならない。ここで、contractive transform conditionより、次式が成り立つのでcontractive transform lemmaは証明できる。

Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)≦Ｄreal(Ｓ^ｕ，Ｓ^ｖ)≦ε （８）
ここでＤcontractive(Ｓ'^ｕ，Ｓ'^ｖ)は中心点をＯｉとしたとき(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)とする。

次に、Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)がcontractive transform conditionを満たすことを説明する。まずlower bounding conditionにより次式が成り立つ。

Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)≦Ｄreal(Ｓ^ｕ，Ｓ^ｖ) （９）
続いて、次式が成り立つことを示す。

Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ) （１０）
［ｉ］:Ｓ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にない場合
平面Ｓ'^ｕＳ'^ｖＯ_ｉは図８に示すように三角形となる。同図において、三角形Ｓ'^ｕＳ'^ｖＯ_ｉの成立条件より、次式が成り立つ。

Ｓ'^ｕＯ_ｉ＋Ｓ'^ｖＯ_ｉ＞Ｓ'^ｕＳ'^ｖ かつ
Ｓ'^ｖＯ_ｉ＋Ｓ'^ｕＳ'^ｖ＞Ｓ'^ｕＯ_ｉ かつ
Ｓ'^ｕＳ'^ｖ＋Ｓ'^ｕＯ_ｉ＞Ｓ'^ｖＯ_ｉ （１１）
この式より、Ｓ'^ｕＳ'^ｖ＞|Ｓ'^ｕＯ_ｉ−Ｓ'^ｖＯ_ｉ|となる。また、|Ｓ'^ｕＯ_ｉ−Ｓ'^ｖＯ_ｉ|＞(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)である。ここで、Ｓ'^ｕＳ'^ｖ＝Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)であり、(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)＝Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)であるので、式（１０）が成り立つ。

［ii−１］:Ｓ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にある場合
図９に示すように、この場合は、|Ｓ'^ｕＯ_ｉ−Ｓ'^ｖＯ_ｉ|＜Ｓ'^ｕＳ'^ｖとなる。また、|Ｓ'^ｕＯ_ｉ−Ｓ'^ｖＯ_ｉ|＞(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)である。ここで、Ｓ'^ｕＳ'^ｖ＝Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)であり、(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)＝Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)であるので、式（１０）が成り立つ。

［ii−２］:Ｓ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にない場合
図１０に示すように、この場合は、|Ｓ'^ｕＯ_ｉ−Ｓ'^ｖＯ_ｉ|＝Ｓ'^ｕＳ'^ｖとなる。また、|Ｓ'^ｕＯ_ｉ−Ｓ'^ｖＯ_ｉ|＞(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)である。ここで、Ｓ'^ｕＳ'^ｖ＝Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)であり、(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)＝Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)であるので、式（１０）が成り立つ。

よって、[ｉ]，[ii−１]，[ii−２]のいずれの場合であってもＤcontractive(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)が成り立つ。

ここで、Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)＝(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)＜εとなるが、この式は、|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|＜ｃ＋１となる。よって、|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|＜ｃ＋１の関係を満たす時系列データは類似する可能性がある。また、ε≦Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)＝(|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|−１)・(ε/ｃ)（＜Ｄreal(Ｓ^ｕ，Ｓ^ｖ)）であれば非類似の時系列データとなるが、この式は|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|≧ｃ＋１となる。よって、|Ｒ^Ｏｉ _ｕ−Ｒ^Ｏｉ _ｖ|≧ｃ＋１である時系列データは非類似となる。

候補検索部３４の候補決定部３４４では、類似する可能性がある時系列データに対して次元圧縮後の時系列データ間の距離を計算し、この距離が一定範囲内にあるものを類似の候補として絞り込む。しかし、次元圧縮後の距離を計算しないでも類似する候補とすることができる場合がある。例えば図１１に示すように、時系列データＳ'^ｕが中心点Ｏ_ｉからＲ^Ｏｉ _ｕ個目の領域にあり、Ｓ'^ｖが中心点Ｏ_ｉからＲ^Ｏｉ _ｖ個目の領域にあるとき、Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ≦ｃとなる領域に属する時系列データは、距離を計算するまでもなく類似の候補として絞り込むことができる。一方、Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ＞ｃとなる領域に属する時系列データについては、次元圧縮後の距離を計算し、この距離に基づいて類否を判断する。なお、図１１の例では、ｃ＝５．５、Ｒ^Ｏｉ _ｕ＝２、Ｒ^Ｏｉ _ｖ＝３またはＲ^Ｏｉ _ｖ＝４である。Ｒ^Ｏｉ _ｖ＝３であれば類似候補であり、Ｒ^Ｏｉ _ｖ＝４であれば次元圧縮後の距離を計算する。以下、このときの処理について詳細に説明する。

候補決定部３４４では、次式が成り立つ時系列データを類似の候補として求める。

Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)≦ε （１２）
ここで、Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)は（Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)とする。以下では、次式が成り立つことを示す。

Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ) （１３）
［ｉ］:Ｓ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にない場合
平面Ｓ'^ｕＳ'^ｖＯ_ｉは図１２に示すように三角形となる。同図において、三角形Ｓ'^ｕＳ'^ｖＯ_ｉの成立条件より、Ｓ'^ｕＯ_ｉ＋Ｓ'^ｖＯ_ｉ＞Ｓ'^ｕＳ'^ｖが成り立つ。また、Ｓ'^ｕＯ_ｉ＋Ｓ'^ｖＯ_ｉ＜(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)である。ここで、Ｓ'^ｕＳ'^ｖ＝Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)であり、(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)＝Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)であるので、式（１３）が成り立つ。

［ii−１］:Ｓ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にある場合
図１３に示すように、この場合は、Ｓ'^ｕＳ'^ｖ＝Ｓ'^ｕＯ_ｉ＋Ｓ'^ｖＯ_ｉとなる。また、Ｓ'^ｕＯ_ｉ＋Ｓ'^ｖＯ_ｉ＜(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)である。ここで、Ｓ'^ｕＳ'^ｖ＝Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)であり、(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)＝Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)であるので、式（１３）が成り立つ。

［ii−２］:Ｓ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にない場合
図１４に示すように、この場合は、Ｓ'^ｕＯ_ｉ＋Ｓ'^ｖＯ_ｉ＞Ｓ'^ｕＳ'^ｖとなる。また、Ｓ'^ｕＯ_ｉ＋Ｓ'^ｖＯ_ｉ＜(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)である。ここで、Ｓ'^ｕＳ'^ｖ＝Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)であり、(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)＝Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)であるので、式（１３）が成り立つ。

よって、[ｉ]，[ii−１]，[ii−２]のいずれの場合であってもＤdigest(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)が成り立つ。Ｄdigest(Ｓ'^ｕ，Ｓ'^ｖ)＜Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)＝(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)≦εであれば類似する候補となる。この式はＲ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ≦ｃとなるので、Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ≦ｃの関係を満たす時系列データを類似する候補として判断する。

一方、ε＜Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)＝(Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ)・(ε/ｃ)であれば直ちに類似の候補とはならない。この式はＲ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ＞ｃとなるので、Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ＞ｃの関係を満たす時系列データについては距離を計算し、この距離が一定範囲内にあるものを類似の候補として判断する。この距離には、例えばユークリッド距離を用いる。

したがって、本実施の形態によれば、空間インデクス部３内部の中心点決定部３３により多次元空間における同心超球の中心点を決定し、候補検索部３４によりこの中心点を中心とする同心超球構造に多次元空間を分割することで、全ての軸を用いた多次元空間の分割が可能となるので、より効率的な分割を実現することができる。

本実施の形態によれば、クラスタリング部３３３により、時系列データのクラスタリングを行い、中心点計算部３３４により、このクラスタリングの結果を用いて中心点を決定することで、適切に中心点を配置することができる。

本実施の形態によれば、サンプル部３３２により、ランダムにサンプリングされた時系列データを対象に、クラスタリング部３３３がクラスタリングを行い、中心点計算部３３４がクラスタリングの結果を用いて中心点を決定することで、中心点を高速に計算することができる。

本実施の形態によれば、空間分割部３４２により、時系列データの類似を判断するための閾値εよりも小さい値ε／ｃ（ｃ＞１）の刻みで多次元空間を分割することで、領域が細かく分割されるので候補領域を小さくすることが可能となる。これにより、中心点Ｏ_ｉからそれぞれＲ^Ｏｉ _ｕ，Ｒ^Ｏｉ _ｖ個の領域に属する時系列データ同士は、Ｒ^Ｏｉ _ｕ＋Ｒ^Ｏｉ _ｖ≦ｃの関係にあれば次元圧縮後の距離を計算しなくとも類似する時系列データの候補とすることができる。

なお、本実施の形態においては、距離関数としてユークリッド距離を用いた。しかし、これに限られるものではなく、次の４つの性質が成り立つ距離関数であれば適用することができる。

１．ｄ(ｘ，ｙ)≧０ （反射則）
２．ｄ(ｘ，ｙ)＝０⇔ｘ＝ｙ （分離則）
３．ｄ(ｘ，ｙ)＝ｄ(ｙ，ｘ) （対称則）
４．ｄ(ｘ，ｙ)＋ｄ(ｙ，ｚ)≧ｄ(ｘ，ｚ) （三角則）
また、本実施の形態については、様々な変形が考えられるので、その変形例について以下説明する。

［実施例１］
中心点決定部３３は、多次元空間における同心超球の中心点をランダムに決定して内部のメモリに記憶させる。中心点をランダムに決定するので、高速に計算できるメリットがある。一方で、中心点を不適切な位置に配置してしまう可能性があるデメリットもある。

［実施例２］
サンプル部３３２を採用せず、クラスタリング部３３３は、多次元空間にあるすべての時系列データを対象にクラスタリングを行う。これにより、中心点計算部３３４で中心点をさらに適切に配置できるメリットがある。一方で、すべての時系列データを対象にクラスタリングを行うため計算に時間を要するデメリットがある。

［実施例３］
空間分割部３４２は、多次元空間を中心点から閾値εの刻みで分割する。閾値ε／ｃを用いた場合と比較して、類似する時系列データが存在する候補領域は時系列データが属する領域とこの領域に直接的に隣接する領域だけに限定されるので、候補領域の数が少なくなるメリットがある。一方で、候補領域に存在する時系列データのすべてに対して次元圧縮後の距離を計算する必要があるデメリットがある。

一実施の形態における類似時系列データ計算装置の構成を示すブロック図である。 CS strucutreについて説明するための図である。 上記類似時系列データ計算装置における空間インデクス部の構成を示すブロック図である。 上記空間インデクス部における中心点決定部の構成を示すブロック図である。 上記空間インデクス部における候補検索部の構成を示すブロック図である。 CS strucutreの多次元空間において複数の中心点が近い位置に集まっている状態を示す図である。 非類似時系列データを判断する領域を説明するための図である。 Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)においてＳ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にない場合について説明するための図である。 Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)においてＳ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にある場合について説明するための図である。 Ｄcontractive(Ｓ'^ｕ，Ｓ'^ｖ)においてＳ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にない場合について説明するための図である。 類似時系列データを判断する領域を説明するための図である。 Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)においてＳ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にない場合について説明するための図である。 Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)においてＳ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にある場合について説明するための図である。 Ｄexpanded(Ｓ'^ｕ，Ｓ'^ｖ)においてＳ'^ｕ，Ｓ'^ｖ，Ｏ_ｉが同一直線上にありかつＯ_ｉが線分Ｓ'^ｕＳ'^ｖの内部にない場合について説明するための図である。 左側の図は２つの時系列データを示し、右側の図はユークリッド距離を用いたときの時系列データ間の距離を示す図である。 grid structureを説明するための図である。

符号の説明

１…類似時系列データ計算装置
２…データ受信部
３…空間インデクス部
４…類似判断部
５…計算結果送信部
３１…データ受信部
３２…次元圧縮部
３３…中心点決定部
３４…候補検索部
３５…データ送信部
３３１…データ受信部
３３２…サンプル部
３３３…クラスタリング部
３３４…中心点計算部
３３５…データ送信部
３４１…データ受信部
３４２…空間分割部
３４３…候補領域決定部
３４４…候補決定部
３４５…データ送信部

Claims (2)

1. ｎ個のデータからなるｎ次元の時系列データを受信して第１メモリに記憶させるデータ受信手段と、
   第１メモリから読み出された時系列データを次元圧縮して第２メモリに記憶させる次元圧縮手段と、
   多次元空間における同心超球の中心点を決定して第３メモリに記憶させる中心点決定手段と、
   第３メモリから読み出された中心点を中心とする同心超球構造に多次元空間を分割して、第２メモリから読み出された時系列データの類似の組み合わせの候補を絞り込んで第４メモリに記憶させる候補検索手段と、を有し、
   前記中心点決定手段は、
   次元圧縮後の時系列データの中からランダムにサンプルを選択するサンプル手段と、
   前記サンプル手段によりサンプリングされた次元圧縮後の時系列データを、多次元空間を均一に分割させるクラスタリング手法によりクラスタリングして第５メモリに記憶させるクラスタリング手段と、
   第５メモリから読み出されたクラスタリングの中心を多次元空間における中心点の位置として決定して第３メモリに記憶させる中心点位置計算手段と、を具備し、
   前記候補検索手段は、
   時系列データの類似を判断するための閾値を定数で除した値を刻み幅とし、多次元空間を前記中心点から前記刻み幅で同心超球構造に分割し、分割領域に番号を与える空間分割手段と、
   前記中心点と時系列データとの距離により、第２メモリから読み出された時系列データが属する分割領域の番号を求める手段と、
   第２メモリから読み出された２つの時系列データに対して、それぞれの時系列データが属する分割領域の番号の差と、前記定数との関係から次元圧縮後の時系列データの類似候補を絞り込み、その類似候補の組み合わせを第４メモリに記憶させる候補決定手段と、を具備する
   ことを特徴とする類似時系列データ計算装置。
2. 請求項１に記載の類似時系列データ計算装置を構成する各手段としてコンピュータを機能させるための類似時系列データ計算プログラム。