(57)【要約】【課題】逐次流入してくる時系列データの類似候補を求めるに際し、多次元空間をより効率的に分割する。【解決手段】空間インデクス部３内部の中心点決定部３３により多次元空間における同心超球の中心点を決定し、候補検索部３４によりこの中心点を中心とする同心超球構造に多次元空間を分割する。これにより、全ての軸を用いた多次元空間の分割を可能とし、より効率的な分割を実現する。【選択図】図３
2006244389.tif 000002
【特許請求の範囲】
【請求項１】
逐次流入してくる時系列データを受信して第１メモリに記憶させるデータ受信手段と、
第１メモリから読み出された時系列データを次元圧縮して第２メモリに記憶させる次元圧縮手段と、
多次元空間における同心超球の中心点を決定して第３メモリに記憶させる中心点決定手段と、
第３メモリから読み出された中心点を中心とする同心超球構造に多次元空間を分割して、第２メモリから読み出された時系列データの類似の組み合わせの候補を絞り込んで第４メモリに記憶させる候補検索手段と、
を有することを特徴とする類似時系列データ計算装置。
【請求項２】
前記中心点決定手段は、
次元圧縮後の時系列データをクラスタリングして第５メモリに記憶させるクラスタリング手段と、
第５メモリから読み出されたクラスタリングの結果を用いて多次元空間における中心点の位置を決定して第３メモリに記憶させる中心点位置計算手段と、
を有することを特徴とする請求項１記載の類似時系列データ計算装置。
【請求項３】
前記中心点決定手段は、
前記クラスタリングの前に、次元圧縮後の時系列データの中からランダムにサンプルを選択するサンプル手段を有することを特徴とする請求項２記載の類似時系列データ計算装置。
【請求項４】
前記中心点決定手段は、多次元空間における中心点の位置をランダムに決定して第３メモリに記憶させる中心点位置計算手段を有することを特徴とする請求項１記載の類似時系列データ計算装置。
【請求項５】
前記候補検索手段は、
多次元空間を前記中心点から時系列データの類似を判断するための閾値の刻みで同心超球構造に分割する空間分割手段と、
分割の結果から類似する時系列データが存在する候補領域を決定する候補領域決定手段と、
決定された候補領域から次元圧縮後の時系列データの類似候補を絞り込み、その類似候補の組み合わせを第４メモリに記憶させる候補決定手段と、
を有することを特徴とする請求項１乃至４のいずれかに記載の類似時系列データ計算装置。
【請求項６】
前記空間分割手段は、前記閾値に代えて当該閾値よりも小さい閾値の刻みで多次元空間を分割することを特徴とする請求項５記載の類似時系列データ計算装置。
【請求項７】
逐次流入してくる時系列データを受信して第１メモリに記憶させるステップと、
第１メモリから読み出された時系列データを次元圧縮して第２メモリに記憶させるステップと、
多次元空間における同心超球の中心点を決定して第３メモリに記憶させるステップと、
第３メモリから読み出された中心点を中心とする同心超球構造に多次元空間を分割して、第２メモリから読み出された時系列データの類似の組み合わせの候補を絞り込んで第４メモリに記憶させるステップと、
を有することを特徴とする類似時系列データ計算方法。
【請求項８】
前記中心点を決定するステップは、
次元圧縮後の時系列データをクラスタリングして第５メモリに記憶させるステップと、
第５メモリから読み出されたクラスタリングの結果を用いて多次元空間における中心点の位置を決定して第３メモリに記憶させるステップと、
を有することを特徴とする請求項７記載の類似時系列データ計算方法。
【請求項９】
前記中心点を決定するステップは、
前記クラスタリングの前に、次元圧縮後の時系列データの中からランダムにサンプルを選択するステップを有することを特徴とする請求項８記載の類似時系列データ計算方法。
【請求項１０】
前記中心点を決定するステップは、多次元空間における中心点の位置をランダムに決定して第３メモリに記憶させるステップを有することを特徴とする請求項７記載の類似時系列データ計算方法。
【請求項１１】
前記候補を絞り込むステップは、
多次元空間を前記中心点から時系列データの類似を判断するための閾値の刻みで同心超球構造に分割するステップと、
分割の結果から類似する時系列データが存在する候補領域を決定するステップと、
決定された候補領域から次元圧縮後の時系列データの類似候補を絞り込み、その類似候補の組み合わせを第４メモリに記憶させるステップと、
を有することを特徴とする請求項７乃至１０のいずれかに記載の類似時系列データ計算方法。
【請求項１２】
逐次流入してくる時系列データを受信して第１メモリに記憶させる処理と、
第１メモリから読み出された時系列データを次元圧縮して第２メモリに記憶させる処理と、
多次元空間における同心超球の中心点を決定して第３メモリに記憶させる処理と、
第３メモリから読み出された中心点を中心とする同心超球構造に多次元空間を分割して、第２メモリから読み出された時系列データの類似の組み合わせの候補を絞り込んで第４メモリに記憶させる処理と、
をコンピュータに実行させることを特徴とする類似時系列データ計算プログラム。
【請求項１３】
前記中心点を決定する処理は、
次元圧縮後の時系列データをクラスタリングして第５メモリに記憶させる処理と、
第５メモリから読み出されたクラスタリングの結果を用いて多次元空間における中心点の位置を決定して第３メモリに記憶させる処理と、
を実行させることを特徴とする請求項１２記載の類似時系列データ計算プログラム。
【請求項１４】
前記中心点を決定する処理は、
前記クラスタリングの前に、次元圧縮後の時系列データの中からランダムにサンプルを選択する処理を実行させることを特徴とする請求項１３記載の類似時系列データ計算プログラム。
【請求項１５】
前記中心点を決定する処理は、次元圧縮後の時系列データについて多次元空間における中心点の位置をランダムに決定して第３メモリに記憶させる処理を実行させることを特徴とする請求項１４記載の類似時系列データ計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の時系列データの中で類似したものを求める類似時系列データ計算装置、類似時系列データ計算方法、および類似時系列データ計算プログラムに関する。
【背景技術】
【０００２】
これまで、時系列データストリームは、株取引、気候観測、メディア処理、医療等の様々な分野のサービスに応用されてきた。時系列データ処理の分野で多く研究されている問題の１つとして、蓄積された時系列データの中から類似したものを求めることがある。この技術のアプリケーションとしては以下のような例が挙げられる。
【０００３】
・過去の株価の推移が同じ銘柄を見つける。
【０００４】
・過去に同じような気温のパターンを示した年を見つける。
【０００５】
・蓄積された動画から類似したものを見つける。
【０００６】
近年、時系列データを検知するセンサの小型化・低価格化が進んだことから、大量の時系列センサデータストリームを利用したサービスが可能になりつつある。そのため、今後はセンサから出力された時系列データの処理技術の重要性が高まることが考えられる。センサデータストリームの特徴の１つに大量の時系列データが逐次流入してくることが挙げられる。
【０００７】
逐次流入してくる時系列データの中から類似したものを求める技術のアプリケーションとしては以下の例が挙げられる。
【０００８】
・リアルタイムに売り上げパターンが同じ商品を見つける。
【０００９】
・地震発生時に揺れ方が同じ地点を見つける。
【００１０】
・現時刻において同じ移動をしている人物を見つける。
【００１１】
本願では、類似している時系列データを求める問題を次のように定める。「ｍ個の時系列データのうち、現在時刻Ｔから過去の一定期間内（ｎデータポイント）における距離が閾値ε内の時系列データの組み合わせを求める」
なお、ここで扱う時系列データには、株価のような離散値と移動軌跡のような連続値がある。離散値の場合、時系列データが類似しているか否かは、離散値を用いて時系列データ間の距離が閾値内にあるか否かを調べればよい。また連続値の場合、時系列データは処理する際にサンプリングされ離散値になるので、結局は離散値の処理手法を用いることになる。
【００１２】
２つの時系列データＳｕ，Ｓｖ間の距離関数として次のようなユークリッド距離を用いる。
【数１】
2006244389.tif 000003
【００１３】
ユークリッド距離を用いて時系列データ間の距離を定義することによって、図１５に示すように、類似する時系列データを求める問題は多次元空間内で近い点を求める問題に置き換えることができる。
【００１４】
また、時系列データ間の距離をユークリッド距離を用いて定めることにより、本願における問題は、閾値をεとしたとき次の条件を満たす時系列データの組み合わせの集合を求める問題となる。
【数２】
2006244389.tif 000004
【００１５】
類似した時系列データを高速に求めるフレームワークとしてＧＥＭＩＮＩ（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を説明するための図である。
【符号の説明】
【０１０６】
１…類似時系列データ計算装置
２…データ受信部
３…空間インデクス部
４…類似判断部
５…計算結果送信部
３１…データ受信部
３２…次元圧縮部
３３…中心点決定部
３４…候補検索部
３５…データ送信部
３３１…データ受信部
３３２…サンプル部
３３３…クラスタリング部
３３４…中心点計算部
３３５…データ送信部
３４１…データ受信部
３４２…空間分割部
３４３…候補領域決定部
３４４…候補決定部
３４５…データ送信部
【図１】
2006244389.tif 000005
【図２】
2006244389.tif 000006
【図３】
2006244389.tif 000007
【図４】
2006244389.tif 000008
【図５】
2006244389.tif 000009
【図６】
2006244389.tif 000010
【図７】
2006244389.tif 000011
【図８】
2006244389.tif 000012
【図９】
2006244389.tif 000013
【図１０】
2006244389.tif 000014
【図１１】
2006244389.tif 000015
【図１２】
2006244389.tif 000016
【図１３】
2006244389.tif 000017
【図１４】
2006244389.tif 000018
【図１５】
2006244389.tif 000019
【図１６】
2006244389.tif 000020