(57)【要約】【課題】時系列データのすべてのデータを用いることなく、少ないデータであっても、高い精度で類似部分シーケンスを検出することができるようにする。【解決手段】サンプリングした時系列データの１つの要素ｘを受信したとき（Ｓ２０１）、当該要素を含む時系列データの部分シーケンスと、他方の時系列データの部分シーケンスとの類似度スコアを、サンプリング周期を用いて算出する（Ｓ１０３）。類似度スコアが所定の閾値以上である部分シーケンスのペアを類似する部分シーケンスのペアと判定し、この類似する部分シーケンスのペアを適合する部分シーケンスのペアとして検出する（Ｓ１０４）。【選択図】図６
2013257712.tif 000002
【特許請求の範囲】
【請求項１】
第１時系列データを第１サンプリング周期でサンプリングした第１時系列データ及び第２時系列データを第２サンプリング周期でサンプリングした第２時系列データから、類似する部分シーケンスのペアを、２つの前記部分シーケンス同士のＤＴＷ(Dynamic Time Warping）距離と相互変換可能な類似度スコアを行列要素とする単一のスコア行列、及び前記部分シーケンスの開始位置を行列要素とする位置行列を用いて検出する類似部分シーケンス検出装置であって、
前記スコア行列及び前記位置行列を記憶する記憶部と、
前記サンプリングした第１時系列データ及び第２時系列データのいずれかのデータの１つの要素を受信したとき、当該要素を含む第１時系列データ及び第２時系列データの何れか一方中の部分シーケンスと、第１時系列データ及び第２時系列データの何れか他方中の部分シーケンスと、の類似度スコアを算出し、
前記算出した類似度スコアを、前記類似度スコアの算出に用いた２つの前記部分シーケンスの終了位置に対応する、前記記憶部のスコア行列の行列要素として記憶すると共に、前記類似度スコアの算出に用いた２つの前記部分シーケンスの開始位置を、前記終了位置に対応する、前記記憶部の位置行列の行列要素として記憶し、
前記記憶部のスコア行列に記憶された前記類似度スコアが所定の閾値以上である部分シーケンスのペアを類似する部分シーケンスのペアと判定し、この類似する部分シーケンスのペアを適合する部分シーケンスのペアとして検出する処理部と、を備え、
前記処理部は、
前記類似度スコアのいずれかを算出するとき、
前記スコア行列において当該類似度スコアと隣接し前記第１時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期を乗算した値を減算するとともに、予め定められた係数に第１サンプリング周期に応じた数値を乗算した値を加算して、第１スコアを算出し、
前記スコア行列において当該類似度スコアと隣接し前記第２時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第２サンプリング周期を乗算した値を減算するとともに、前記予め定められた係数に第２サンプリング周期に応じた数値を乗算した値を加算して、第２スコアを算出し、
前記スコア行列において当該類似度スコアと隣接し前記第１時系列データ及び前記第２時系列データの両方に関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期及び第２サンプリング周波数の何れか大きい方を乗算した値を減算するとともに、前記予め定められた係数に第１サンプリング周期及び第２サンプリング周期の和に応じた数値を乗算した値を加算して、第３スコアを算出し、
前記第１スコア、前記第２スコア、及び前記第３スコアのうちの最大のスコアを、当該類似度スコアとする
類似部分シーケンス検出装置。
【請求項２】
前記所定の閾値は、前記適合する部分シーケンスのペアの２つの部分シーケンスの長さの下限値として予め設定された値に、前記予め定められた係数を乗算した値であり、
前記処理部は、
前記適合する部分シーケンスのペアを検出するとき、当該所定の閾値を用いることで、前記下限値以上の長さの適合する部分シーケンスのペアを検出する請求項１に記載の類似部分シーケンス検出装置。
【請求項３】
前記処理部は、
前記検出された前記適合する部分シーケンスのペアを前記記憶部に記憶し、
前記検出された前記適合する部分シーケンスのペアを前記記憶部に記憶するときに、前記記憶部に記憶された前記適合する部分シーケンスのペアのうち、算出に使用した前記位置行列における行列要素が一致しているものがある場合、前記位置行列における行列要素が一致している複数の適合する部分シーケンスのペアのうち、前記類似度スコアが最大の適合する部分シーケンスのペアのみを、前記記憶部に記憶する請求項２に記載の類似部分シーケンス検出装置。
【請求項４】
前記処理部は、
前記類似度スコアの算出に用いた２つの前記部分シーケンスの開始位置を前記記憶部の位置行列に記憶するとき、前記取得した最大の類似度スコアの算出に用いた２つの前記部分シーケンスの開始位置を、前記類似度スコアの算出に用いた２つの前記部分シーケンスの開始位置として前記記憶部の位置行列に記憶し、
前記適合する部分シーケンスのペアを検出するとき、前記記憶部の位置行列を参照して、前記所定の閾値以上の前記類似度スコアに対応する開始位置を特定する請求項１〜請求項３の何れか１項に記載の類似部分シーケンス検出装置。
【請求項５】
第１時系列データを第１サンプリング周期でサンプリングした第１時系列データ及び第２時系列データを第２サンプリング周期でサンプリングした第２時系列データから、類似する部分シーケンスのペアを、２つの前記部分シーケンス同士のＤＴＷ(Dynamic Time Warping）距離と相互変換可能な類似度スコアを行列要素とする単一のスコア行列、及び前記部分シーケンスの開始位置を行列要素とする位置行列を用いて検出する、前記スコア行列及び前記位置行列を記憶する記憶部を備えた類似部分シーケンス検出装置における類似部分シーケンス検出方法であって、
処理部によって、
前記サンプリングした第１時系列データ及び第２時系列データのいずれかのデータの１つの要素を受信したとき、当該要素を含む第１時系列データ及び第２時系列データの何れか一方中の部分シーケンスと、第１時系列データ及び第２時系列データの何れか他方中の部分シーケンスと、の類似度スコアを算出し、
前記算出した類似度スコアを、前記類似度スコアの算出に用いた２つの前記部分シーケンスの終了位置に対応する、前記記憶部のスコア行列の行列要素として記憶すると共に、前記類似度スコアの算出に用いた２つの前記部分シーケンスの開始位置を、前記終了位置に対応する、前記記憶部の位置行列の行列要素として記憶し、
前記記憶部のスコア行列に記憶された前記類似度スコアが所定の閾値以上である部分シーケンスのペアを類似する部分シーケンスのペアと判定し、この類似する部分シーケンスのペアを適合する部分シーケンスのペアとして検出することを含み、
前記処理部によって前記類似度スコアのいずれかを算出するとき、
前記スコア行列において当該類似度スコアと隣接し前記第１時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期を乗算した値を減算するとともに、予め定められた係数に第１サンプリング周期に応じた数値を乗算した値を加算して、第１スコアを算出し、
前記スコア行列において当該類似度スコアと隣接し前記第２時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第２サンプリング周期を乗算した値を減算するとともに、前記予め定められた係数に第２サンプリング周期に応じた数値を乗算した値を加算して、第２スコアを算出し、
前記スコア行列において当該類似度スコアと隣接し前記第１時系列データ及び前記第２時系列データの両方に関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期及び第２サンプリング周波数の何れか大きい方を乗算した値を減算するとともに、前記予め定められた係数に第１サンプリング周期及び第２サンプリング周期の和に応じた数値を乗算した値を加算して、第３スコアを算出し、
前記第１スコア、前記第２スコア、及び前記第３スコアのうちの最大のスコアを、当該類似度スコアとする
類似部分シーケンス検出方法。
【請求項６】
前記所定の閾値は、前記適合する部分シーケンスのペアの２つの部分シーケンスの長さの下限値として予め設定された値に、前記予め定められた係数を乗算した値であり、
前記処理部によって、
前記適合する部分シーケンスのペアを検出するとき、当該所定の閾値を用いることで、前記下限値以上の長さの適合する部分シーケンスのペアを検出する請求項５に記載の類似部分シーケンス検出方法。
【請求項７】
前記処理部によって、
前記検出された前記適合する部分シーケンスのペアを前記記憶部に記憶し、
前記検出された前記適合する部分シーケンスのペアを前記記憶部に記憶するときに、前記記憶部に記憶された前記適合する部分シーケンスのペアのうち、算出に使用した前記位置行列における行列要素が一致しているものがある場合、前記位置行列における行列要素が一致している複数の適合する部分シーケンスのペアのうち、前記類似度スコアが最大の適合する部分シーケンスのペアのみを、前記記憶部に記憶する請求項６に記載の類似部分シーケンス検出方法。
【請求項８】
コンピュータを、請求項１〜請求項４の何れか１項記載の類似部分シーケンス検出装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似部分シーケンス検出装置、方法、及びプログラムに係り、特に、２つの時系列データから、類似する部分シーケンスのペアを検出する類似部分シーケンス検出装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
センサネットワークの普及に伴い、センサノードから収集されるセンサデータを効率的に処理・分析する技術が求められるようになった。特に、センサデータは、近年のBig data に代表されるように、データを蓄積してから分析するのではなく、リアルタイムに瞬時に分析を行い、結果を提示することが重要とされている。従来から検討されてきたセンサデータの平均値や最大・最小値を求めるといった統計情報の処理のみではなく、有益な情報を自動抽出する高度なマイニング技術が必要となる。このマイニング技術の1つとして、類似探索が挙げられる。センサデータの類似探索とは、センサデータ間の類似部分を特定する技術であり、相関検出(例えば、特許文献１)や問合せパターンに類似する部分パターンの特定(例えば、特許文献２)などもこれに該当する。特許文献３では、データ間に共通する部分的なパターンを特定する技術が示されている。パターン検出のための距離関数として、ダイナミックタイムワーピング距離(DTW)を利用し、純粋にDTWを用いた場合と同等の精度を保証しつつも、高速かつ省メモリに動作する。これは、センサデータをサーバなどでモニタリングし、2つのセンサ間に共通するパターンがあればリアルタイムに検出することを指す。図１７、図１８に具体的な類似パターンの検出を例示する。図１７は、2つの異なるセンサによって取得された湿度データである。各センサは約1分間隔でデータを取得しており、横軸は取得したデータのシーケンス番号であり、縦軸がその値である。これら2つのセンサデータは、一部異なる区間が存在するものの、よく似たパターンを示している。具体的には、Subseqによって記される2つのパターンが、これらのセンサにおける類似パターンである。図１８は、これらのデータに対し、特許文献３の技術を適用した場合の類似パターン検出結果を示している。横軸が図１７における1つ目のセンサデータのシーケンス番号を、縦軸が2つ目のセンサデータのシーケンス番号を表している。図における太線が、2つのデータ間でどの要素同士が対応付いているかを意味し、2つの類似パターンを特定する様子を示している。このように、2つのセンサデータを比べ、類似パターンがあればその位置(開始位置と終了位置)と類似度をリアルタイムに報告する。この技術は時系列データに適用する汎用的なものであるが、センサデータに適用する場合、次の2点に注目する必要がある。1点目は、データ通信量の考慮である。類似パターン検出のためには、各センサノードが取得したデータをサーバに送信する必要がある。この時、データが短い間隔で取得されている場合、そのデータ量は膨大になる。各センサノードがこれらをすべて送信することで、ネットワーク全体の通信量が増大してしまう。2点目は、センサノードの電源制約である。各センサノードは、主に電池駆動であり、データ収集やデータ送信時に電力を消費する。この電力量は、データ送信時が一番高いことが知られており、必要以上のデータを送信することで、電池の消耗を速めてしまう可能性がある。以上のことから、センサデータからリアルタイムに類似パターン検出を行う場合、パターン検出に必要な最低限のデータを保持しつつも、効率的にデータを送信する必要がある。
【０００３】
そこで、効率的なデータ送信方法として、特許文献４のようにデータの変化率(速度や位置などを基に算出) に応じてデータを選択して送信したり、特許文献５のように、複数のセンサデータを圧縮して送信する方法が挙げられる。
【０００４】
また、非特許文献1では、時系列データに対し、オリジナルデータを縮約した概要情報のみにリアルタイムに変換する技術が提案されている。概要情報の一部を送信することで、データ量は大幅に削減される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第4452234号公報
【特許文献２】特許第4801566号公報
【特許文献３】特開2010-198227号公報
【特許文献４】特開2011-192198号公報
【特許文献５】特開2012-44449号公報
【非特許文献】
【０００６】
【非特許文献１】Umit Y. Ogras, and Hakan Ferhatosmanoglu: “Online summarizationof dynamic time series data, ” VLDB journal, vol.15, num.1, pp.84-98,2006.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の特許文献３において利用しているDTWは、データの形状(時間ドメインの情報) を利用して類似パターンを検出する。そのため、オリジナルデータに近い検出精度を保証するためには、データ削減を実現しつつも、データの形状は保持するようにデータを選択する必要がある。これに対し、上記で述べた技術はデータの形状に関係なく、または、データの形状を壊した状態でデータが選択されるため、適切に類似パターン検出を行うことが困難である。
【０００８】
本発明は、上記の事情を鑑みてなされたもので、時系列データのすべてのデータ(オリジナルデータ)を用いることなく、少ないデータであっても、高い精度で類似部分シーケンスを検出することができる類似部分シーケンス検出装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために本発明に係る類似部分シーケンス検出装置は、第１時系列データを第１サンプリング周期でサンプリングした第１時系列データ及び第２時系列データを第２サンプリング周期でサンプリングした第２時系列データから、類似する部分シーケンスのペアを、２つの前記部分シーケンス同士のＤＴＷ(Dynamic Time Warping）距離と相互変換可能な類似度スコアを行列要素とする単一のスコア行列、及び前記部分シーケンスの開始位置を行列要素とする位置行列を用いて検出する類似部分シーケンス検出装置であって、前記スコア行列及び前記位置行列を記憶する記憶部と、前記サンプリングした第１時系列データ及び第２時系列データのいずれかのデータの１つの要素を受信したとき、当該要素を含む第１時系列データ及び第２時系列データの何れか一方中の部分シーケンスと、第１時系列データ及び第２時系列データの何れか他方中の部分シーケンスと、の類似度スコアを算出し、前記算出した類似度スコアを、前記類似度スコアの算出に用いた２つの前記部分シーケンスの終了位置に対応する、前記記憶部のスコア行列の行列要素として記憶すると共に、前記類似度スコアの算出に用いた２つの前記部分シーケンスの開始位置を、前記終了位置に対応する、前記記憶部の位置行列の行列要素として記憶し、前記記憶部のスコア行列に記憶された前記類似度スコアが所定の閾値以上である部分シーケンスのペアを類似する部分シーケンスのペアと判定し、この類似する部分シーケンスのペアを適合する部分シーケンスのペアとして検出する処理部と、を備え、前記処理部は、前記類似度スコアのいずれかを算出するとき、前記スコア行列において当該類似度スコアと隣接し前記第１時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期を乗算した値を減算するとともに、予め定められた係数に第１サンプリング周期に応じた数値を乗算した値を加算して、第１スコアを算出し、前記スコア行列において当該類似度スコアと隣接し前記第２時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第２サンプリング周期を乗算した値を減算するとともに、前記予め定められた係数に第２サンプリング周期に応じた数値を乗算した値を加算して、第２スコアを算出し、前記スコア行列において当該類似度スコアと隣接し前記第１時系列データ及び前記第２時系列データの両方に関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期及び第２サンプリング周波数の何れか大きい方を乗算した値を減算するとともに、前記予め定められた係数に第１サンプリング周期及び第２サンプリング周期の和に応じた数値を乗算した値を加算して、第３スコアを算出し、前記第１スコア、前記第２スコア、及び前記第３スコアのうちの最大のスコアを、当該類似度スコアとする。
【００１０】
本発明に係る類似部分シーケンス検出方法は、第１時系列データを第１サンプリング周期でサンプリングした第１時系列データ及び第２時系列データを第２サンプリング周期でサンプリングした第２時系列データから、類似する部分シーケンスのペアを、２つの前記部分シーケンス同士のＤＴＷ(Dynamic Time Warping）距離と相互変換可能な類似度スコアを行列要素とする単一のスコア行列、及び前記部分シーケンスの開始位置を行列要素とする位置行列を用いて検出する、前記スコア行列及び前記位置行列を記憶する記憶部を備えた類似部分シーケンス検出装置における類似部分シーケンス検出方法であって、処理部によって、前記サンプリングした第１時系列データ及び第２時系列データのいずれかのデータの１つの要素を受信したとき、当該要素を含む第１時系列データ及び第２時系列データの何れか一方中の部分シーケンスと、第１時系列データ及び第２時系列データの何れか他方中の部分シーケンスと、の類似度スコアを算出し、前記算出した類似度スコアを、前記類似度スコアの算出に用いた２つの前記部分シーケンスの終了位置に対応する、前記記憶部のスコア行列の行列要素として記憶すると共に、前記類似度スコアの算出に用いた２つの前記部分シーケンスの開始位置を、前記終了位置に対応する、前記記憶部の位置行列の行列要素として記憶し、前記記憶部のスコア行列に記憶された前記類似度スコアが所定の閾値以上である部分シーケンスのペアを類似する部分シーケンスのペアと判定し、この類似する部分シーケンスのペアを適合する部分シーケンスのペアとして検出することを含み、前記処理部によって前記類似度スコアのいずれかを算出するとき、前記スコア行列において当該類似度スコアと隣接し前記第１時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期を乗算した値を減算するとともに、予め定められた係数に第１サンプリング周期に応じた数値を乗算した値を加算して、第１スコアを算出し、前記スコア行列において当該類似度スコアと隣接し前記第２時系列データに関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第２サンプリング周期を乗算した値を減算するとともに、前記予め定められた係数に第２サンプリング周期に応じた数値を乗算した値を加算して、第２スコアを算出し、前記スコア行列において当該類似度スコアと隣接し前記第１時系列データ及び前記第２時系列データの両方に関して１つ前の時刻に対応する前記類似度スコアを取得し、当該取得した類似度スコアに対して、対象の２つの前記部分シーケンスにおける対応するデータの要素同士の差の大きさに、第１サンプリング周期及び第２サンプリング周波数の何れか大きい方を乗算した値を減算するとともに、前記予め定められた係数に第１サンプリング周期及び第２サンプリング周期の和に応じた数値を乗算した値を加算して、第３スコアを算出し、前記第１スコア、前記第２スコア、及び前記第３スコアのうちの最大のスコアを、当該類似度スコアとする。
【００１１】
本発明に係るプログラムは、コンピュータを、上記の類似部分シーケンス検出装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１２】
以上説明したように、本発明の類似部分シーケンス検出装置、方法、及びプログラムによれば、それぞれの時系列データのサンプリング周期を用いて、類似度スコアを算出することにより、時系列データのすべてのデータを用いることなく、少ないデータであっても、高い精度で類似部分シーケンスを検出することができる、という効果が得られる。
【図面の簡単な説明】
【００１３】
【図１】湿度データのパワースペクトルを示すグラフである。
【図２】サンプリング後の湿度データを示すグラフである。
【図３】本発明の第１の実施の形態に係るセンサノードの構成を示す概略図である。
【図４】本発明の第１の実施の形態に係る類似パターン検出装置の構成を示す概略図である。
【図５】ＤＴＷを説明するための図である。
【図６】本発明の第１の実施の形態に係る類似パターン検出装置における類似部分シーケンスペア検出処理の処理ルーチンの内容を示すフローチャートである。
【図７】本発明の第１の実施の形態に係る類似パターン検出装置におけるＬｉｓｔ配列への格納処理の処理ルーチンの内容を示すフローチャートである。
【図８】本発明の第１の実施の形態に係る類似パターン検出装置におけるＬｉｓｔ配列への格納処理の処理ルーチンの内容を示すフローチャートである。
【図９】本発明の第２の実施の形態に係るセンサノードの構成を示す概略図である。
【図１０】本発明の第２の実施の形態に係るセンサノードにおけるサンプリング周期決定処理の処理ルーチンの内容を示すフローチャートである。
【図１１】温度センサのデータを示すグラフである。
【図１２】温度センサのデータを用いた類似パターン検出結果を示す図である。
【図１３】太陽黒点のデータを示すグラフである。
【図１４】太陽黒点のデータを用いた類似パターン検出結果を示す図である。
【図１５】温度センサのデータを用いた類似パターン検出結果を示す図である。
【図１６】太陽黒点のデータを用いた類似パターン検出結果を示す図である。
【図１７】湿度データと共通する部分パターンを説明するための図である。
【図１８】従来技術を用いた類似パターンの検出例を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１５】
〔第１の実施の形態〕
＜発明の概要＞
本発明では、センサデータ間の類似パターンを検出において、センサネットワークに対して効率的なデータ送信を実現しつつ、従来手法(特許文献３)と近い精度を保つシステムを提供する。すなわち、本発明の目的は、センサノードで収集されたすべてのデータ(オリジナルデータ)を用いることなく、少ないデータであっても高い精度で類似パターンを検出することである。センサノードでは、収集されるすべてのデータを送信するのではなく、類似パターン検出に必要なデータのみを選択して送信する。一方サーバでは、送信されたデータから、オリジナルデータを用いた類似パターン検出に近い精度を維持する検出を行う。
【００１６】
オリジナルデータと同等の精度を達成するためには、データの形状を維持するようにデータを選択(サンプリング)する必要がある。そこで、本発明では、サンプリング定理に基づいてオリジナルデータをサンプリングし、サンプリング後のデータを送信することで類似パターン検出を行う。サンプリング定理とは、アナログ信号をデジタル信号に変換する際に、どの程度の間隔でサンプリングすればよいかを定量的に示した定理であり、元の信号に含まれる最大周波数成分をfとすると、2fよりも高い周波数fNqでサンプリングした信号は、元の信号を完全に復号することができるというものである。このfNqはナイキスト周波数と呼ばれている。サンプリング周期を決定するためには、データに離散フーリエ変換(FFT)を行い、パワースペクトルを算出する。これは、データの中に各周波数成分がどの程度の割合で含まれているかを表している。図１はHumidity #1のパワースペクトルを図示したものである。上記図１におけるパワーは、合計が１になるように正規化されている。上記図１では60までの周波数成分を示したが、もっと高周波の成分にもパワーが割り当てられており、さまざまな周波数成分から構成されていることがわかる。このようなデータの最大周波数成分fを決定するために、パワーの割合が低い高周波成分はノイズであるとみなし、閾値を用いて決定するのが一般的である(例えば、信号処理やネットワーク分析など)。閾値による決定方法は主に2通りあり、全パワーに対する割合を閾値として指定し、低周波成分からのパワーの合計が閾値を超える周波数をfとする場合と、パワーの値を閾値として指定し、閾値以上のパワーを持つ周波数成分のうち、最大となるものをfとする場合がある。しかしながら、最大周波数成分の決定方法はこれだけには限定されず、どの方法を用いてもかまわない。次にfを基に、以下の（１）式によりナイキスト周波数fNqを求め、以下の（２）式に従って、サンプリング周期Tを決定する。
【００１７】
【数１】
2013257712.tif 000003
【００１８】
ここで、nはデータの長さを表す。サンプリング周期は、すべてのセンサノードに対して共通で用いても構わないし、個々のセンサノードで個別に設定してもかまわない。しかし、サンプリング周期はデータに依存する値であるため、個別に設定するのが望ましい。
【００１９】
各センサノードでは、設定されたサンプリング周期に従い、オリジナルデータをサンプリングする。そして、サンプリングされたデータのみを、サーバである類似パターン検出装置に送信する。図２は、サンプリング後のHumidity #1データを表している。データの形状は維持しているにも関わらず、そのデータサイズは大幅に削減されている。
【００２０】
一方、類似パターン検出装置における類似パターン検出時に、サンプリング周期の情報を利用する。すなわち、サンプリングされたシーケンスを純粋に用いるのではなく、サンプリングにより送信されなかったデータの情報を近似的に利用し、類似度を計算する。これにより、オリジナルシーケンスを用いた場合に近い結果を得ることが可能となる。
【００２１】
＜システム構成＞
図３に示すように、本発明の第１の実施の形態に係るセンサノード１００は、データセンシング部１０、データ取得部１２、サンプリング部１４、周期記憶部１６、及び無線通信部１８から構成される。各データは、データセンシング部１０で検知され、データ取得部１２に送られる。周期記憶部１６は、データをサンプリングためのする情報(サンプリング周期)を記憶しており、その情報に基づき、サンプリング部１４がデータをサンプリングする。センサノード１００は、後述する類似パターン検出装置１５０から、データを選択するサンプリング周期の情報を得る。
【００２２】
サンプリング部１４によってサンプリングされた時系列データが、無線通信部１８から類似パターン検出装置１５０へ送信される。
【００２３】
図４に示すように、類似パターン検出装置１５０は、２つのセンサノード１００から送信された、サンプリングされた時系列データを受信し、類似する部分シーケンスを検出する。この類似パターン検出装置１５０は、ＣＰＵと、ＲＡＭと、後述する各種処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたサーバで構成され、機能的には次に示すように構成されている。図４に示すように、類似パターン検出装置１５０は、データ入力部６０と、処理部７０と、データ出力部８０とを備えている。
【００２４】
データ入力部６０は、無線通信装置で受信した複数の時系列データの入力を受け付ける。また、データ入力部６０は、キーボードなどの入力装置から、類似部分シーケンスペア（以下、単に「類似部分シーケンス」ともいう。）の検出のための類似部分シーケンス検出条件の入力を受け付ける。この類似部分シーケンス検出条件は、例えば、適合する部分シーケンスペアの長さの下限値ｌｍｉｎ（ユーザによって予め設定。つまり、Ｌ（ｌｘ，ｌｙ）がｌｍｉｎ以上であるペアを検出する。）、時系列データの種類に応じて予め設定された所定の係数ε等である。なお、データ入力部６０は、ネットワーク等を介して外部から入力されたものを受け付けるようにしてもよい。
【００２５】
処理部７０は、データ取得部７２、検出条件記憶部７４、パターン検出部７６、周期計算部７８、周期記憶部８２、及び行列情報記憶部８４から構成される。
【００２６】
データ取得部７２は、データ入力部６０により受け付けた時系列データのデータを取得する。検出条件記憶部７４は、データ入力部６０による受け付けた類似部分シーケンス検出条件を記憶する。
【００２７】
周期計算部７８は、２つのセンサノード１００から取得した２つの時系列データの各々に対して、離散フーリエ変換(FFT)を行い、パワースペクトルを算出して、周波数ｆを決定し、上記（１）式、（２）式に従って、サンプリング周期をそれぞれ算出する。２つのセンサノード１００に対して算出されたサンプリング周期は、周期記憶部８２に記憶されると共に、データ出力部８０により、無線通信で、２つのセンサノード１００のそれぞれに、算出されたサンプリング周期を送信する。
【００２８】
パターン検出部７６は、２つのセンサノード１００から取得した２つの時系列データに対して、類似する部分シーケンスを検出する。類似部分シーケンスの検出に必要な計算データ（スコア行列、位置行列、Ｌｉｓｔ配列）は行列情報記憶部８４に記憶される。最終的に類似部分シーケンス検出条件に該当する類似部分シーケンスのみがデータ出力部８０により出力される。
【００２９】
次に、類似部分シーケンスを検出する原理について説明する。
【００３０】
本発明は、センサデータのシーケンス間の部分的な類似パターンを見つけるためのものである。シーケンス間の類似度判定には、ダイナミックタイムワーピング距離（DTW）を利用する。DTWは時間スケールを考慮した有用な距離尺度の1つである。シーケンス間の距離を最小化するように時間軸方向にシーケンス長を調整する性質を持っているため、シーケンス長やサンプリングレートが異なるシーケンス間の類似度を計算することができる。
【００３１】
2つのシーケンス間のDTW距離は動的計画法によって計算され、2つのシーケンスを最適に調節した後の距離の合計となる。図５（Ａ）〜（Ｃ）はDTWの計算方法を例示したものである。図５（Ａ）は、距離計算のためのDTWによる最適なシーケンスの対応付けを表している。距離計算には図５（Ｂ）で示されるようなタイムワーピング行列が用いられる。距離値を計算するために対応付けられた要素同士の並びはワーピングパスと呼ばれ、図５（Ｂ）では濃く色付けされたセルの集合として示されている。
【００３２】
長さnのシーケンスX=(x1，x2,...,xn)と長さmのシーケンスY=(y1，y2,...,ym)を考える。これらのDTW距離D(X，Y)は以下の（３）式のように定義される。
【００３３】
【数２】
2013257712.tif 000004
【００３４】
ここで、||xi−yj||=(xi−yj)2は2つの数値の距離を表す。L1距離(||xi−yj||=|xi−yj|)など、他の選択でもかまわない。図５（Ｃ）は具体的なDTW距離計算を例示したものである。各セルにおいて上記（３）式に従い距離を計算し、2つのシーケンス間のDTW 距離は右上のセルにより獲得する。一方のシーケンスの小さな範囲と、もう一方のシーケンスの大きな範囲が対応することによるマッチングの精度低下を避けるため、ワーピング制約が導入される。これは、不要なワーピングパスを取り除き、ワーピングの範囲を制限するものであり、Sakoe-Chiba bandが代表的なワーピング制約の1つである。図５（Ｂ）のグレーに色付けられたセルは、Sakoe-Chibabandにおけるワーピングの範囲wを表しており、具体的には|i−j|≦wという制限の基で計算される。これは、類似パターン検出における計算量の抑制にも役に立つ。センサデータは、各センサノードから連続的に送信されるデータであるため、半無限長のストリームデータであると言える。このようなデータの分析においては、過去に受け取った古いデータより、現在に受け取った新しいデータの方がより重要であるとされる。そのため、ワーピングの範囲を設定することにより、比較的新しいデータの類似パターン検出に焦点をあてることができる。さらに、計算量も1つの行列に対して一定に抑えられるため、効率的な処理につながる。本発明の実施例においても、ワーピングの範囲を設定した例を示す。
【００３５】
センサデータXは、x1，x2,...,...の値からなる半無限長のデータシーケンスである。xnは最新の値であり、時間が進むごとにnは増加する。X[is:ie]は時刻isから始まりieで終わるXの部分シーケンス(パターン) であり、X[is:ie]の長さはlx=ie−is+1となる。同様に、Y[js:je]は時刻jsから始まりjeで終わるYの部分シーケンスであり、その長さはly=je−js+1となる。
【００３６】
本発明で検出するセンサデータシーケンス間の部分的な類似パターンとは、以下の（４）式に示す条件を満たす部分シーケンスペアを検出することである。
【００３７】
【数３】
2013257712.tif 000005
【００３８】
D(X[is:ie],Y[js:je])は部分シーケンスペアX[is:ie]とY[js:je]間のDTW距離であり、Lは部分シーケンスペアの長さを表す関数である。以下、上記（４）式の条件を満たす部分シーケンスを、適合する部分シーケンスとも称する。本発明では、2つの部分シーケンスの平均長であるL(lx,ly)=(lx+ly)=2を用いるが、L(lx,ly)=max(lx,ly)やL(lx,ly)=min(lx,ly)を用いてもかまわない。εは類似判定の閾値を指す。DTW距離は、対応付けられた要素の距離の合計で表されるため、部分シーケンスの長さが長くなるにつれてその値は増加する。そのため、類似判定の閾値も部分シーケンス長に比例することが望ましく、ε(L(lx,ly)−lmin)を用いて判定を行なう。適合する部分シーケンスの長さの閾値lminは、ユーザによって与えられる値であり、部分シーケンスペアの長さLがlmin以上となる部分シーケンスペアを検出することが保証される。
【００３９】
部分シーケンスペアX[is:ie]とY[js:je]が適合する時、距離値が極小値をとる部分シーケンスペアに重複(overlap)する多くの部分シーケンスペアも適合してしまう。重複とは部分シーケンスペア間のワーピングパスが交わることであり、2つのワーピングパスにおいて少なくとも1つの要素が共有されることを指す。重複する部分シーケンスペアは冗長な情報であり、ほぼ同区間から複数の類似パターンが検出されることになる。また、不必要な結果についても報告することでアルゴリズムの処理速度が低下する可能性もある。そのため、重複する部分シーケンスペアの中から距離値が極小値をとる部分シーケンスペアを検出する。具体的には、以下の（１）、（２）の条件を満たす部分シーケンスペアを類似パターンとして検出する。
【００４０】
（問題1）  2つのシーケンスXとY、閾値ε、適合する部分シーケンスの長さの閾値lminが与えられた時、次の（１）、（２）の条件を満たす部分シーケンスペアX[is:ie]とY[js:je]を検出する。
【００４１】
（１） X[is:ie]とY[js:je]は上記（４）式を満たす。
（２）重複する部分シーケンスペアのグループの中で、D(X[is:ie];Y[js:je])−ε(L(lx;ly)−lmin)が最小値をとる。
【００４２】
また、第１の実施の形態では、固定のサンプリング周期に基づいて各センサノード１００がデータを送信し、削減された（サンプリングされた）データを使って類似パターン検出を行う。各センサノード１００のサンプリング周期は、類似パターン検出装置１５０上で決定する。類似パターン検出装置１５０でサンプリング周期を決定するため、サンプリング周期を決定するまでのデータは一度すべて受信する必要がある。その後、各センサノード１００は決定したサンプリング周期に基づいて、サンプリングしたデータを類似パターン検出装置１５０に送信する。サンプリング後のデータに対し、上記特許文献３の技術をそのまま用いて類似パターン検出を行うことも可能である。しかしながら、センサノード１００で収集されたオリジナルデータとは異なるため、オリジナルデータを利用した類似パターン検出と結果が大きく異なる可能性がある。そこで、オリジナルデータにより近い検出結果を得るため、上記特許文献３における検出方法を改良する。具体的には、サンプリングによって送信されなかったデータの情報を、近似的に組み込むことでパターン検出を行うというものである。これにより、データ送信の効率化を実現しつつも、オリジナルデータに近い精度を達成することが可能となる。上記特許文献３では、DTWに基づく類似パターン検出を実現するため、DTWと同等の精度を達成するスコアリング関数と位置行列を用いて類似度の計算を行う。スコアリング関数は、2つのシーケンス間の部分シーケンスペアの類似度をスコアとして出力する関数である。スコアは動的計画法に基づき、スコア行列を用いて計算される。具体的には、2つのシーケンスX=(x1,...,xi,...,xn)とY=(y1,...,yj,...,...,ym)が与えられた時、X[is:ie]とY[js:je]のスコア値V(X[is:ie];Y[js:je])は、以下の（５）式のように計算される。
【００４３】
【数４】
2013257712.tif 000006
【００４４】
スコア値を計算するために対応付けられた要素同士の並びが、スコア行列におけるワーピングパスである。スコア値は距離の閾値εと各要素の距離値の差を累積することにより決定されるため、部分シーケンスペアが条件を満たさない場合には、スコア値は負の値を示す。そのため、不適合な部分シーケンスペアをスコアの値から判断することが可能となる。また、負の値となった要素のスコアをゼロでリセットすることで、その要素から新たにスコア計算を開始する。この性質を利用して、不適合な部分シーケンスペアを枝刈りし、適合する可能性が高い部分シーケンスペアのみを1つの行列で効率的に計算することができる。また、上記（５）式において、bv,bh,bdはLによって決定される重みである。例えば、L(lx,ly)=(lx+ly)=2において、bv=bh=1/2、bd=1となる。これは、垂直または水平方向の要素が引き継がれた場合、シーケンス長は1/2増加し、対角方向の要素が引き継がれた場合は1 増加するためである。また、L(lx,ly)=max(lx,ly)において、lx>lyの場合、bd=bh=1,bv=０,lx<lyの場合、bd=bv=1,bh=0、lx=lyの場合、bd=1,bv=bh=0となる。L(lx,ly)=min(lx,ly)についても同様に決定される。
【００４５】
スコア行列の中での各ワーピングパス上の重み(bv,bh,bd)の合計は、L(lx;ly)と等しくなるように設計されており、DTW距離とスコアが変換可能であることが保証される。部分シーケンスペアのDTW距離は、次の（６）式により計算される。
【００４６】
【数５】
2013257712.tif 000007
【００４７】
スコア行列では、類似する部分シーケンスペアのスコアと終了点の情報が保持される。どこから始まる部分シーケンスペアが類似していたのかという開始点の情報は、位置行列により保持される。開始点は座標値として表され、以下の（７）式のように求められる。
【００４８】
【数６】
2013257712.tif 000008
【００４９】
s(ie,je)は、X[is:ie]とY[js:je]のマッチングの開始点(is,js)を指し示す。スコア行列を位置行列の2つを用いることで、効率的に類似パターンを検出する。
【００５０】
本発明では、サンプリングされたシーケンスを用いて類似パターンを検出する。オリジナルデータに近い精度を達成するため、上記スコアリング関数と位置行列の改良を行う。直感的なアイディアは、スコアの計算において垂直方向、水平方向、対角方向のいずれかの要素を選択する場合、オリジナルのシーケンスから削除された要素によって与えられる距離値を補完することである。サンプリング周期をTとすると、サンプリングされたシーケンス間のスコアを計算するとき、現在のセルと隣接するセルとの間にはT−1個の隠れたセルが存在する。この隠れたセルにおける距離値を、現在のセルの距離値を用いて近似する。長さn のシーケンスXと長さmのシーケンスYのサンプリング周期をTxとTy、オリジナルシーケンスXとYのサンプリングされたシーケンスをX’=(x1,...,xi,...,x|_n/Tx」)、Y’=(y1,...,yj,...,y|_ｍ/Ty」)とする時、X’とY’の部分シーケンスのスコアは、以下の（８）式のように計算される。
【００５１】
【数７】
2013257712.tif 000009
【００５２】
ただし、|_Ｍ」は、Ｍの小数点以下を切り捨てた値を表わす。
【００５３】
検出エラーを最小化するため、各方向のスコアを選択した場合にTxまたはTy個の距離値を補完する。上記（８）式において、bv,bh,bdの重みも更新される。L(lx,ly)=(lx+ly)=2の時、垂直方向または水平方向のセルのスコアが選択された場合、Lの値はTx/2またはTy/2増加する。同様に、対角方向のセルのスコアが選択された場合、Lの値は(Tx+Ty)/2増加する。そのため、bv＝Ty/2、bh＝Tx/2、bd＝(Tx+Ty)/2となる。
【００５４】
上記（８）式の改良に合わせて、位置行列も改良される。しかし、その操作は上記（７）式とほぼ同様である。もし、3つのセル(垂直、水平、対角方向のセル) のいずれかが選択される場合は、そのセルの開始点を引き継ぐ。そうでなければ、サンプリング周期Tx,Tyに応じて開始点が設定される。すなわち、開始点s(i,j)は以下の（９）式のように決定される。
【００５５】
【数８】
2013257712.tif 000010
【００５６】
次に、スコアリング関数、スコア行列、位置行列を用い、サンプリングされたシーケンス間の類似部分シーケンスペアをどのように検出か述べる。パターン検出対象となるセンサノードからデータを受信した時、検出処理を開始する。ここで、2つのセンサノード１００のオリジナルのデータシーケンスをXとY(最新の要素はそれぞれnとm)、サンプリングされたシーケンスをX’=(x1,...,xi,...,xLn/Tx」)、Y’=(y1,...,yj,...,yLm/Ty」)とする。何れかのセンサノード１００から最新のデータを受信すると、そのデータに対応するスコア行列、位置行列の要素を更新する。そして、条件を満たすスコアを示す部分シーケンスペアが存在するかどうかをチェックし(問題1の条件（1）)、存在する場合にはそのペアが最適なペアであるかの確認を行う(問題1の条件（2）)。最適なペアを検出するために、List配列を利用する。List配列が空の場合、条件を満たした類似部分シーケンスペアのスコアvmax、開始点(is,js)、終了点(js,je)が保持される。List配列が空でない場合には、新たに検出された部分シーケンスペアがList配列に格納されている部分シーケンスペアと重複するかどうかのチェックが行われ、もし重複する場合にはスコアが大きい方の部分シーケンスペアのみの情報がＬｉｓｔ配列に保持される。重複する部分シーケンスペアが存在しない場合には、新たにList配列に追加される。そして、現在の最適な部分シーケンスペアが今後出現する部分シーケンスペアによって置き換わることがないことを確認した後、すなわち、以下の（１０）式に示す条件を満たす時、類似部分シーケンスペアとして報告する。
【００５７】
【数９】
2013257712.tif 000011
【００５８】
受信した最新のデータに対応するスコア行列、位置行列の各要素が計算される時、List配列の中の部分シーケンスペアが上記（１０）式に示す条件を満たすかどうかが調べられる。受信した最新のデータに対応するスコア行列、位置行列の各要素を計算し終えた時点で、上記（１０）式の条件を満たす部分シーケンスペアは報告され、その後List 配列から削除される。
【００５９】
＜類似パターン検出装置の作用＞
次に、類似パターン検出装置１５０の具体的な処理について説明する。ここでは、２つの時系列データX’=(x1,...,xi,...,xLn/Tx」)と、時系列データY’=(y1,...,yj,...,yLm/Ty」)とにおける各要素が、順次与えられるものとする。このとき、図６に示す類似部分シーケンスペア検出処理ルーチンが、類似パターン検出装置１５０において実行される。
【００６０】
まず、ステップＳ１０１において、データ取得部７２は、データ入力部６０経由で、最新のデータxLn/Tx」を受信する。次に、ステップＳ１０２において、処理部７０は、ｊの値を「|_（ｍ−ｗ）／Ｔy」」にリセットする。
【００６１】
その後、パターン検出部７６は、ｊの値をインクリメント（「１」増加）させながら、ｊの値が|_（ｍ−ｗ）／Ｔy」になるまで、ステップＳ１０３〜Ｓ１０５の処理を繰り返す。
【００６２】
ステップＳ１０３において、パターン検出部７６は、ｘn/Txとｙjの類似度スコアｖ（ｎ/Ｔｘ,ｊ）、開始点ｓ（ｎ/Ｔx,ｊ）を、（８）式、（９）式を用いて計算する。
【００６３】
ステップＳ１０４において、パターン検出部７６は、ｖ（ｎ/Ｔｘ,ｊ）−εｌｍｉｎ≧０の条件を満たすか否かを判断し、この条件を満たす場合（Ｙｅｓ）、ステップＳ１０５に進み、この条件を満たさない場合（Ｎｏ）、上記ステップＳ１０３へ戻るか、ステップＳ１１１に進む。
【００６４】
ステップＳ１０５では、Ｌｉｓｔ配列格納処理を行う。Ｌｉｓｔ配列格納処理は、図７に示す処理ルーチンによって実現される。
【００６５】
ステップＳ１２０において、パターン検出部７６は、行列情報記憶部８４に記憶されているＬｉｓｔ配列が空であるか否かを判定する。Ｌｉｓｔ配列が空である場合には、ステップＳ１２１において、パターン検出部７６は、Ｌｉｓｔ配列のＬｉｓｔ[１].ｖmaxに、スコアｖ（ｎ/Ｔｘ,ｊ）を格納し、Ｌｉｓｔ配列の（Ｌｉｓｔ[１].ｉs、Ｌｉｓｔ[１].ｊs）に、ｓ（ｎ/Ｔｘ,ｊ）を格納し、Ｌｉｓｔ配列の（Ｌｉｓｔ[１].ｉe、Ｌｉｓｔ[１].ｊe）に、（ｎ,ｊ・Ｔy）を格納する。そして、当該処理ルーチンを終了する。
【００６６】
一方、Ｌｉｓｔ配列が空でない場合には、パターン検出部７６は、Ｌｉｓｔ配列内の各要素ｌ（ｌ＝１,...,Ｌ）について、ステップＳ１２２の処理を繰り返す。
【００６７】
ステップＳ１２２において、パターン検出部７６は、開始点ｓ（ｎ/Ｔx,ｊ）が、Ｌｉｓｔ配列の（Ｌｉｓｔ[ｌ].ｉs、Ｌｉｓｔ[ｌ].ｊs）と一致するか否かを判定し、一致しない場合には、ステップＳ１２２を繰り返すか、ステップＳ１２３へ進む。
【００６８】
ステップＳ１２３において、パターン検出部７６は、Ｌｉｓｔ配列の全ての要素と重複しないか否かを判定する。上記ステップＳ１２２の判定の結果、全ての要素と開始点が一致しない場合には、重複しないと判断し、ステップＳ１２４において、
【００６９】
Ｌｉｓｔ配列のＬｉｓｔ[Ｌ＋１].ｖmaxに、スコアｖ（ｎ/Ｔｘ,ｊ）を格納し、Ｌｉｓｔ配列の（Ｌｉｓｔ[Ｌ＋１].ｉs、Ｌｉｓｔ[Ｌ＋１].ｊs）に、ｓ（ｎ/Ｔｘ,ｊ）を格納し、Ｌｉｓｔ配列の（Ｌｉｓｔ[Ｌ＋１].ｉe、Ｌｉｓｔ[Ｌ＋１].ｊe）に、（ｎ,ｊ・Ｔy）を格納し、当該処理ルーチンを終了する。
【００７０】
一方、上記ステップＳ１２２において、開始点ｓ（ｎ/Ｔx,ｊ）が、Ｌｉｓｔ配列の（Ｌｉｓｔ[ｌ].ｉs、Ｌｉｓｔ[ｌ].ｊs）と一致すると判定された場合、Ｌｉｓｔ配列の当該要素と重複すると判断し、ステップＳ１２５において、パターン検出部７６は、
【００７１】
スコアｖ（ｎ/Ｔｘ,ｊ）が、Ｌｉｓｔ配列の当該要素のスコアＬｉｓｔ[ｌ].ｖmax以上であるか否かを判定する。スコアｖ（ｎ/Ｔｘ,ｊ）が、Ｌｉｓｔ配列の当該要素のスコアＬｉｓｔ[ｌ].ｖmax以上である場合には、ステップＳ１２６において、パターン検出部７６は、Ｌｉｓｔ配列のＬｉｓｔ[ｌ].ｖmaxに、スコアｖ（ｎ/Ｔｘ,ｊ）を上書きし、Ｌｉｓｔ配列の（Ｌｉｓｔ[ｌ].ｉs、Ｌｉｓｔ[ｌ].ｊs）に、ｓ（ｎ/Ｔｘ,ｊ）を上書きし、Ｌｉｓｔ配列の（Ｌｉｓｔ[ｌ].ｉe、Ｌｉｓｔ[ｌ].ｊe）に、（ｎ,ｊ・Ｔy）を上書きし、当該処理ルーチンを終了する。一方、スコアｖ（ｎ/Ｔｘ,ｊ）が、Ｌｉｓｔ配列の当該要素のスコアＬｉｓｔ[ｌ].ｖmax未満である場合には、当該処理ルーチンを終了する。
【００７２】
また、ステップＳ１０６において、データ取得部７２は、データ入力部６０経由で、最新のデータｙLn/Ty」を受信すると、パターン検出部７６は、ステップＳ１０２〜ステップＳ１０５の処理と同様にして、ステップＳ１０７〜ステップＳ１１０の処理を行う。
【００７３】
上記ステップＳ１１０は、図８に示す処理ルーチンによって実現され、ステップＳ１２０〜ステップＳ１２６の処理と同様にして、ステップＳ１３０〜ステップＳ１３６の処理を行う。
【００７４】
そして、ステップＳ１１１において、パターン検出部７６は、Ｌｉｓｔ配列に格納されている部分シーケンスペアの各々が、上記（１０）式に示す条件を満たすか否かを判定し上記（１０）式に示す条件を満たす部分シーケンスペアが存在する場合には、当該要素について、その後出現する部分シーケンスペアによって置き換わることがないと判断し、それに対応するスコア、開始点、および終了点を、データ出力部８０経由でユーザに報知し、当該部分シーケンスペアを、Ｌｉｓｔ配列から削除する。
【００７５】
そして、ステップＳ１１２において、パターン検出部７６は、２つの時系列データの受信が終了したか否か判断し、終了していなければ（Ｎｏ）、ステップＳ１０１あるいはステップＳ１０６に戻り、終了していれば（Ｙｅｓ）、処理を終了する。
【００７６】
以上説明したように、本発明の第１の実施の形態によれば、それぞれの時系列データのサンプリング周期を用いて、類似度スコアを算出することにより、時系列データのすべてのデータを用いることなく、少ないデータであっても、高い精度で類似部分シーケンスを検出することができる。
【００７７】
また、センサなどのデバイスにより取得されるデータからの類似パターンの検出において、センサノードで送信するデータを制限しつつも、オリジナルのデータを用いた場合に近い精度で類似パターンを検出することが可能となる。また、センサネットワークに限らず、時系列データからの類似パターン検出を高速に検出する場合においても適用することが可能である。
【００７８】
〔第２の実施の形態〕
＜システム構成＞
次に、第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【００７９】
第２の実施の形態では、サンプリング周期を、センサノード側で計算している点と、定期的にサンプリング周期を計算している点とが第１の実施の形態と異なっている。
【００８０】
図９に示すように、第２の実施の形態に係るセンサノード２００は、データセンシング部１０、データ取得部１２、サンプリング部１４、周期記憶部１６、無線通信部１８、及び周期計算部２２０から構成される。
【００８１】
周期計算部２２０は、データ取得部１２から得た情報を用いて、サンプリング周期を敵的に計算する。サンプリング周期の計算方法は、周期計算部７８と同様である。
【００８２】
周期計算部２２０で計算されたサンプリング周期は、無線通信部１８により、類似パターン検出装置１５０へ送信される。
【００８３】
第２の実施の形態における類似部分シーケンスを検出する原理について説明する。
【００８４】
第２の実施の形態では、サンプリング周期を随時更新し、類似パターン検出を行う。上記の第1の実施の形態では、固定のサンプリング周期を用いたが、サンプリング周期は既に取得したデータを用いて決定されたものであるため、それ以降に取得したデータに対して有効であるかどうかは保証されない。例えば、温度センサから取得されるデータを考える。サンプリング周期を決定したデータシーケンスは温度変化があまり見られないデータであり、その後天候や環境変化により定期的に温度変化が生じた場合、温度変化前のサンプリング周期を用いてサンプリングを行うと、細かな変化の情報を落としたデータシーケンスが、サーバである類似パターン検出装置１５０に送信される。このような変化に対応するためには、その都度サンプリング周期を決定し、データをサンプリングすることが望ましい。
【００８５】
そこで、本実施の形態では、センサノード２００において定期的にサンプリング周期を計算し直すことで、サンプリング周期を適切に調節する。センサノード２００で取得されたオリジナルシーケンスをX=(x1,...,xi,...,xn)、調整されたサンプリング周期でサンプリングされたシーケンスをX’=(x1,...,xi,...,xn′)、サンプリング周期をTx=(tx1,...,txi,...,txn′)とする。センサノード２００は、現在取得した最新のデータxnと、センサノード２００から類似パターン検出装置１５０に送信された最後のデータxn′−1間のデータ数がtxn′−1である場合、センサノード２００は、xnをxn′として無線通信部１８により類似パターン検出装置１５０に送信する。同時に、xnまでのオリジナルデータを用いて、次に送信するデータのためのサンプリング周期txn′を決定する。決定したサンプリング周期は、類似パターン検出のために類似パターン検出装置１５０に送られる。
【００８６】
この時、センサノード２００において取得したすべてのデータを保持することは不可能であるため、過去のデータを捨てて、最新のデータのみをサンプリング周期の計算のために保持することが望ましい。例えば、スライディングウィンドウを使って、常に一定のデータ数を保持するなどが考えられる。また、蓄積したデータに対してバッチ的にサンプリング周期を計算するのではなく、取得したデータに対してインクリメンタルにサンプリング周期を計算するアルゴリズムも提案されている(http://dl.acm.org/citation.cfm?id=1146470)。これらのアルゴリズムを利用することで、センサノード２００にデータを蓄積することなく、サンプリング周期を計算することも可能である。
【００８７】
類似パターン検出装置１５０は、各センサノード２００からのデータとサンプリング周期の情報を受信し、類似パターンを検出する。最新の要素がn′であるサンプリングされたシーケンスX’=(x1,.., xi,...,xn′)と、最新の要素がm′であるサンプリングされたシーケンスY’=(y1,...,yj,...,ym′)を考える。また、XのオリジナルシーケンスXのサンプリング周期をTx=(tx1,...,txi,...,txn′)、YのオリジナルシーケンスYのサンプリング周期をTy=(ty1,...,tyj,...,tym′)とする。サンプリングされたシーケンスにおける部分シーケンスペアのスコアは、以下の（１１）式に従って計算される。
【００８８】
【数１０】
2013257712.tif 000012
【００８９】
サンプリング周期がスコア計算の都度変わることにより、シーケンス長が変化するため、各方向の重み(Bv,Bh,Bd)も随時更新される。一方、位置行列については、サンプリング周期の変化を開始点情報に組み込み、以下の（１２）式に従って計算される。
【００９０】
【数１１】
2013257712.tif 000013
【００９１】
＜センサノードの作用＞
次に、第２の実施の形態に係るセンサノード２００の作用について説明する。
【００９２】
センサノード２００によって、図１０に示す処理ルーチンが実行される。
【００９３】
まず、ステップＳ２０１において、データ取得部１２から、データセンシング部１０からの現時点ｎのデータｘnを取得する。ステップＳ２０２では、サンプリング部１４が、前回のサンプルの要素ｎ’−１と、現時点ｎとの間隔が、前回計算されたサンプリング周期Ｔxn'-1に到達したか否かを判定する。前回のサンプルの要素ｎ’−１と、現時点ｎとの間隔が、前回計算されたサンプリング周期Ｔxn'-1に到達した場合には、ステップＳ２０３において、周期計算部２２０によって、ｘnまでのデータを用いて、サンプリング周期を計算し、周期記憶部１６に格納する。そして、ステップＳ２０４において、上記ステップＳ２０１で取得したデータｘn（すなわち、サンプリングされたデータxn′）と、上記ステップＳ２０３で計算されたサンプリング周期とを、無線通信部１８により、類似パターン検出装置１５０へ送信する。
【００９４】
一方、前回のサンプルの要素ｎ’−１と、現時点ｎとの間隔が、前回計算されたサンプリング周期Ｔxn'-1に到達していない場合には、ステップＳ２０５へ移行する。
【００９５】
ステップＳ２０５では、データセンシング部１０からのデータの受信が終了したか否か判断し、終了していなければ（Ｎｏ）、ステップＳ２０１に戻り、終了していれば（Ｙｅｓ）、処理を終了する。
【００９６】
＜類似パターン検出装置の作用＞
類似パターン検出装置１５０は、上記の第１の実施の形態で説明した類似部分シーケンスペア検出処理ルーチンを実行する。ここで、上記ステップＳ１０３では、パターン検出部７６は、ｘn/Txとｙjの類似度スコアｖ（ｎ/Ｔｘ,ｊ）、開始点ｓ（ｎ/Ｔx,ｊ）を、上記（１１）式、（１２）式を用いて計算する。また、サンプリング周期Ｔｘとして、データ入力部６０によりセンサノード２００から受信したサンプリング周期を用いる。
【００９７】
また、上記ステップＳ１０８も同様に、上記（１１）式、（１２）式と同様の式を用いて計算する。
【００９８】
以上説明したように、第２の実施の形態によれば、それぞれの時系列データについて随時計算されるサンプリング周期を用いて、類似度スコアを算出することにより、時系列データのすべてのデータを用いることなく、少ないデータであっても、高い精度で類似部分シーケンスを検出することができる。
【００９９】
＜実施例＞
本発明の有効性を検証するため、実データを用いた実験を行った。実験には、4GBのメモリとIntel（Ｒ） Core2 2.4GHzのCPUを搭載したLinux（登録商標）マシンを用いた。実験結果を視覚的に把握するため、ここでは散布図を用いる。散布図は、データシーケンスXとYにおける類似部分シーケンスペアであるX[is:ie]とY[js:je]のワーピングパスを描画している。すなわち、類似部分シーケンスペアのどの要素同士が対応して検出されたかという要素の対応付けが示される。散布図における横軸はXの要素を、縦軸はYの要素を表す。
【０１００】
図１１は温度センサから取得されたデータを示している。およそ1分間隔で取得されたデータに対し、18度から32度の間で大きく変化する類似パターンが確認される。図１２が、上記特許文献３を用いたオリジナルの類似パターン検出に対し、実施例1と2を用いた場合の検出結果を示している。図から確認される通り、どちらの実施例においても、オリジナルの検出と非常に近い結果を示している。
【０１０１】
図１３は、太陽の黒点数を記録したデータである。太陽の黒点には周期性があることがよく知られており、太陽の活動とも密接に関連している。太陽活動が活発な時は黒点が多く出現し、逆に太陽活動が不活発な時は黒点が減少する。この変化は約11年の周期で増減する。図１４に検出したパターンの結果を示す。こちらのデータにおいても、オリジナルの類似パターン検出と同等の結果が確認される。
【０１０２】
図１５、１６は、温度センサから取得されたデータセットにおける類似パターン検出結果を詳細に示すものであり、図１６は、太陽の黒点数を記録したセットにおける類似パターン検出結果を詳細に示すものである。本発明は近似手法であり、サンプリングによりサーバに送信されなかったデータの情報を送信されたデータの情報で補完するものであるため、その値の違いにより、検出された類似パターンのDTW距離は少し異なる結果となった。しかしながら、図１２、１４で確認された通り、類似パターンの位置は高い精度で検出可能であることが確認される。
【０１０３】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１０４】
例えば、‖ｘｉ−ｙｊ‖として、ユークリッド距離の二乗の値を使用したが、ユークリッド距離などの他の距離を使用してもかまわない。
【０１０５】
その他、ハードウェア、ソフトウェアの具体的な構成について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【０１０６】
また、時系列データは、映像やセンサネットワーク、金融など様々な分野で発生する。本発明はこれらのすべての分野に適用可能である。
【０１０７】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１０８】
１０   データセンシング部
１２、７２    データ取得部
１４   サンプリング部
１６、８２    周期記憶部
１８   無線通信部
６０   データ入力部
７０   処理部
７４   検出条件記憶部
７６   パターン検出部
７８、２２０  周期計算部
８０   データ出力部
８４   行列情報記憶部
１００、２００センサノード
１５０ 類似パターン検出装置
【図３】
2013257712.tif 000014
【図４】
2013257712.tif 000015
【図９】
2013257712.tif 000016
【図１５】
2013257712.tif 000017
【図１６】
2013257712.tif 000018
【図１】
2013257712.tif 000019
【図２】
2013257712.tif 000020
【図５】
2013257712.tif 000021
【図６】
2013257712.tif 000022
【図７】
2013257712.tif 000023
【図８】
2013257712.tif 000024
【図１０】
2013257712.tif 000025
【図１１】
2013257712.tif 000026
【図１２】
2013257712.tif 000027
【図１３】
2013257712.tif 000028
【図１４】
2013257712.tif 000029
【図１７】
2013257712.tif 000030
【図１８】
2013257712.tif 000031