(57)【要約】【課題】効率よく類似時系列データを検索することができるようにすること。【解決手段】時系列データを部分区間に分割する時系列分割部３０１と、時系列分割部３０１が分割した後の時系列データの近似多項式を生成する近似多項式生成部３０２と、近似多項式生成部３０２が生成した近似多項式の係数ベクトルをインデックスの作成が容易な空間上のベクトルに変換する係数変換部３０３と、係数変換部３０３が変換したベクトルを利用し近似多項式を保持する近似多項式記憶部５０とを備える。【選択図】図１
2013246729.tif 000002
【特許請求の範囲】
【請求項１】
クエリとして与えられた時系列に類似する部分時系列を、時系列データから検索するための類似時系列データ検索システムであって、
時系列データを部分区間に分割する時系列分割部と、
前記時系列分割部が分割した後の時系列データの近似多項式を生成する近似多項式生成部と、
前記近似多項式生成部が生成した近似多項式の係数ベクトルを空間上のベクトルに変換する係数変換部と、
前記係数変換部が変換したベクトルを利用し近似多項式を保持する近似多項式記憶部と
を備える類似時系列データ検索システム。
【請求項２】
前記係数変換部は、係数ベクトルをユークリッド空間上のベクトルに変換し、
前記係数変換部は、距離計算に用いる行列をコレスキー分解して得られる行列と係数ベクトルの積により係数の変換を行う
請求項１に記載の類似時系列データ検索システム。
【請求項３】
前記近似多項式記憶部は、Ｒ木、ｋｄ木、ＬＳＨのいずれかを利用して近似多項式を保持する
請求項１又は２に記載の類似時系列データ検索システム。
【請求項４】
前記近似多項式記憶部は、システム内の複数の記憶装置にデータを分散して保持し、各記憶装置には時間区分毎のデータを保持する
請求項１から３のいずれか一項に記載の類似時系列データ検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似時系列データ検索システムに関する。特に本発明は、クエリとして与えられた時系列に類似する部分時系列を、時系列データから検索するための類似時系列データ検索システムに関する。
【背景技術】
【０００２】
Ｍ２Ｍ（Ｍａｃｈｉｎｅ  ｔｏ  Ｍａｃｈｉｎｅ）は、機械と機械が通信ネットワークを介して互いに情報をやり取りすることにより、自律的に高度な制御や動作を行うものである。特に、Ｍ２Ｍは、コンピュータや通信装置等の情報機器以外の機械にセンサーや処理装置、通信装置等を組み込んで、データ収集や遠隔監視、制御等を行う。
【０００３】
Ｍ２Ｍシステムの例としては、工作機械の集中制御や、自動販売機の在庫状況の遠隔監視、様々な建物に設置されたエレベーターの稼働状況の監視、配電盤等にセンサーやコンピュータを導入して電力使用量の監視や供給制御を行うスマートグリッド等が挙げられる。
【０００４】
機器から送信されるデータは、収集・解析され、機器の制御や新たなサービスの実現に活用される。機器から送信されるデータの中で、特に、時系列データの分析は時間的な変化による異常や特徴を抽出するために非常に重要である。時系列データの分析では、データが定期的に送信されるため、蓄積されるデータの量が膨大になる。そのため、効率的なデータ解析を実現する必要がある。
【０００５】
時系列データの分析手法の一つとして、部分時系列をクエリとして過去の時系列データから類似した部分時系列を検索する類似検索がある。非特許文献１では、時系列データを複数の区間に分割した上で、分割区間を近似多項式として表現し、近似多項式間の距離によって時系列データ間の類似性を評価することにより、類似判定の高速化を実現している。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】藤野  友也、外３名、”時系列データ類似検索方式ＤＩＡＳＴＲＡの提案と評価”、［ｏｎｌｉｎｅ］、平成２３年３月１日、ＤＥＩＭ  Ｆｏｒｕｍ  ２０１１、［平成２４年４月２７日検索］、インターネット＜ｈｔｔｐ：／／ｄｂ−ｅｖｅｎｔ．ｊｐｎ．ｏｒｇ／ｄｅｉｍ２０１１／ｐｒｏｃｅｅｄｉｎｇｓ／ｐｄｆ／ｄ９−４．ｐｄｆ＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に記載の方法は、類似時系列を検索するために、動的計画法を用いたマッチング処理を行うものである。そのため、非特許文献１に記載の方法は、蓄積されている時系列データが膨大になった場合に、全ての分割区間を起点としたマッチング処理を行うことになり、必ずしも高速な類似検索を実現できない。
【０００８】
本発明の目的は、上述した課題を解決する類似時系列データ検索システムを提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明の第１の形態によると、クエリとして与えられた時系列に類似する部分時系列を、時系列データから検索する類似時系列データ検索システムであって、時系列データを部分区間に分割する時系列分割部と、時系列分割部が分割した後の時系列データの近似多項式を生成する近似多項式生成部と、近似多項式生成部が生成した近似多項式の係数ベクトルをインデックスの作成が容易な空間上のベクトルに変換する係数変換部と、係数変換部が変換したベクトルを利用し近似多項式を保持する近似多項式記憶部とを備える。
【００１０】
なおまた、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となり得る。
【発明の効果】
【００１１】
以上の説明から明らかなように、この発明によっては、効率よく類似時系列データを検索することができるようになる。
【図面の簡単な説明】
【００１２】
【図１】一実施形態に係る類似時系列データ検索システムのブロック構成の一例を示す図である。
【図２】本実施形態における時系列データの挿入処理の流れの一例を示すフローチャートである。
【図３】本実施形態における近似時系列データの検索処理の流れの一例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１４】
図１は、一実施形態に係る類似時系列データ検索システムのブロック構成の一例を示す。本実施形態の類似時系列データ検索システムは、クエリとして与えられた時系列に類似する部分時系列を、時系列データから検索するためのシステムである。
【００１５】
本実施形態の類似時系列データ検索システムは、時系列データ記憶部１０、時系列データ挿入部２０、時系列変換部３０、類似時系列検索部４０、及び近似多項式記憶部５０を備える。
【００１６】
時系列データ記憶部１０には、入力された時系列データが記憶される。時系列データは、データの発生時刻と値の組で表わされるデータである。
【００１７】
時系列データ挿入部２０は、図示されない時系列データの発生元からの入力時系列データを受け取り、時系列データ記憶部１０に記録するとともに、入力時系列データを時系列変換部３０によって変換した座標を近似多項式記憶部５０に追加する。
【００１８】
時系列変換部３０は、時系列データを近似多項式記憶部５０での保存・検索に適した形式に変換する処理を行う。時系列変換部３０は、時系列分割部３０１と、近似多項式生成部３０２と、係数変換部３０３を備える。
【００１９】
時系列分割部３０１は、入力時系列を適切な長さに分割する処理を行う。分割処理は例えば、予め指定された長さごとに入力時系列を分割してもよいし、近似多項式生成部３０２の生成する近似多項式の誤差がある閾値を超えないように分割してもよい。
【００２０】
近似多項式生成部３０２は、時系列分割部３０１によって分割された分割時系列を近似する近似多項式を求める。近似多項式を求めるには、最小二乗法等の手法を利用することができる。近似多項式生成部３０２は定義域の時間区間を０から１に正規化した近似多項式を生成する。
【００２１】
係数変換部３０３は、近似多項式生成部３０２から得られる近似多項式の係数のベクトルをユークリッド空間上のベクトルへと変換する。変換の詳細については、後述する。
【００２２】
類似時系列検索部４０は、ユーザから入力されたクエリ時系列に類似した時系列データを検索する。類似時系列検索部４０は、クエリ時系列に対して、時系列変換部３０の変換結果をもとに近似多項式記憶部５０から類似した時系列を検索する。
【００２３】
近似多項式記憶部５０は、近似多項式の係数を係数変換部３０３により変換して得られる座標を保持することで近似多項式を記憶する。
【００２４】
次に、本実施形態における動作について詳細に説明する。本実施形態における主な動作は、入力時系列データの記録処理と、クエリ時系列データが与えられたときの検索処理の２つがあり、それぞれについて説明する。
【００２５】
図２は、入力時系列データの記録処理における動作の流れを示すシーケンス図である。図２に示すように、時系列データが外部から時系列データ挿入部２０に入力されると（Ｓ１１）、入力された時系列データは、時系列データ記憶部１０に記録される（Ｓ１２）。次に、時系列データは時系列変換部３０によって近似多項式記憶部５０での保存・検索に適した形式に変換される。この変換の処理は以下のように行われる。まず、時系列分割部３０１によって、時系列データを部分区間に分割する（Ｓ１３）。分割は、固定幅で行ってもよいし、次のステップで生成される近似多項式の誤差が小さくなるような分割を行ってもよい。分割が終わると、分割された時系列データのそれぞれに対して、近似多項式生成部３０２は、近似多項式を生成する（Ｓ１４）。生成される近似多項式は、定義域を０〜１に正規化したものである。つまり、分割時系列データがＴ１〜Ｔ２の時刻範囲のデータを含む時、Ｔ１とＴ２がそれぞれ近似多項式での０と１に対応するように時間軸での正規化が行われる。近似多項式ＰＡ及びＰＢがあるとき、２つの近似多項式の距離Ｄは数１で定義できる。
【００２６】
【数１】
2013246729.tif 000003
【００２７】
ＰＡとＰＢがそれぞれ数２であるとき、数１の距離は次の数３により計算できる。
【００２８】
【数２】
2013246729.tif 000004
【００２９】
【数３】
2013246729.tif 000005
【００３０】
近似多項式が生成されると、次に係数変換部３０３により、近似多項式の係数からなるベクトルを検索が容易な空間上のベクトルに変換する（Ｓ１５）。具体的には、数３における行列Ｍのコレスキー分解（Ｍ＝ＬＵ，ＵはＬの転置行列）を求め、係数のベクトルｃに対して、ベクトルｅ＝Ｕｃを求める。このベクトルｅが近似多項式の係数ベクトルの変換結果となる。数１で定義される距離Ｄは、変換後のベクトル間のユークリッド距離として求めることができる。係数変換部３０３によって変換されたベクトルは、近似多項式記憶部５０へと記憶される（Ｓ１６）。近似多項式記憶部５０は、例えば、Ｒ木やｋｄ木のようなユークリッド空間における多次元データの近傍探索が高速なデータ構造を利用して変換後のベクトルを記憶する。また、近傍探索に適したＬＳＨを利用してデータを保持してもよい。近似多項式記憶部５０へは、変換後のベクトルに加えて、その近似多項式と対応する時系列データの開始位置・終了位置の情報が保持される。
【００３１】
図３は、類似時系列データの検索処理の動作の流れを示すシーケンス図である。図３に示すように、ユーザからクエリ時系列データが類似時系列検索部４０に与えられると（Ｓ２１）、クエリ時系列データは検索に適したデータに変換される。この処理は、上述の挿入処理における入力時系列データの変換処理と同様に行われる。つまり、まず時系列分割部３０１によって時系列データを部分区間に分割し（Ｓ２２）、分割された区間毎に近似多項式生成部３０２によって近似多項式を求める（Ｓ２３）。さらに、係数変換部３０３によって、近似多項式の係数ベクトルをユークリッド空間上のベクトルへと変換する（Ｓ２４）。類似時系列検索部４０は、この変換後のベクトルを用いて類似した時系列の検索を行う（Ｓ２５）。
【００３２】
Ｓ２５の検索は具体的には次のように行われる。例として、あるクエリ時系列データがｎ個の部分区間に分割され、係数変換部３０３の変換によって時刻順にｅ１，…，ｅｎのｎ個のベクトルが生成されたものとする。このとき、ｅ１からｅｎのそれぞれのベクトルに対して、近似多項式記憶部５０からユークリッド距離の近い近似多項式を検索する。距離の近い近似多項式としては、ユークリッド距離がある閾値以下のものまたは、距離が近いものから一定数を抽出する。ベクトルｅｉに対して、検索結果として近似多項式の集合Ｓｉが得られたとき、Ｓ１，…，Ｓｎからそれぞれ１つずつ要素を選ぶことで得られる系列のうち、時間的に連続した部分時系列を列挙する。この処理は、近似多項式記憶部５０に保持される開始位置及び終了位置を利用することで容易に実現できる。最終的に、類似時系列検索部４０は、列挙された部分時系列のうち、クエリ時系列データの近似多項式と距離が近いものを検索結果として出力する。なお、出力結果の出力順は、時系列データ記憶部１０に記憶される時系列データとクエリ時系列データとの距離を計算して得られる距離の近い順に出力してもよい。
【００３３】
本実施形態は、そのままでは類似検索が容易には行えない部分時系列データの近似多項式の係数ベクトルをユークリッド空間での検索が可能な形式に変換し、Ｒ木やｋｄ木等の多次元ユークリッド空間での探索を効率的に実現可能なデータベースに保存する。したがって、距離の近い近似多項式の検索が高速に行えるため、効率的に類似時系列データの検索が可能である。
【００３４】
図１では、類似時系列検索部４０と近似多項式記憶部５０をシステム内に１つずつ配置されているが、これらの両要素は分散して配置することが可能であり、分散によって更なる効率化を実現できる。分散配置を実現するためには、近似多項式記憶部５０を、ある時間区間毎に分割してデータを保持すればよい。
【００３５】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は、上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更、又は改良を加えることが可能であることが当業者に明らかである。そのような変更、又は改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００３６】
特許請求の範囲、明細書、及び図面中において示した動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示していない。また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現し得ることに留意すべきである。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。
【符号の説明】
【００３７】
１０  時系列データ記憶部
２０  時系列データ挿入部
３０  時系列変換部
４０  類似時系列検索部
５０  近似多項式記憶部
３０１  時系列分割部
３０２  近似多項式生成部
３０３  係数変換部
【図１】
2013246729.tif 000006
【図２】
2013246729.tif 000007
【図３】
2013246729.tif 000008