(57)【要約】      （修正有）【課題】計算コストを抑えつつ、時系列データの集合の中から注目データと類似する時系列データを検索することを可能にする。【解決手段】ユーザ端末から収集した時系列データからなる加速度データを計測期間ごとにグループ化してセンサデータ記憶部４１に記憶する。この状態で、シンボル化処理部３２により上記センサデータを低次元化されたシンボル系列に変換し、代表文字列抽出部３３により上記シンボル系列をもとにシンボルの出現傾向が最も大きくなる参照セグメント文字列を求めてこれを代表文字列とする。そして、検索データ設定部３４の制御の下でユーザが選択したグループの代表文字列に対する他の各グループの代表文字列の類似度を類似度算出部３５により計算し、類似度がしきい値以下となるグループに含まれるセンサデータを検索結果出力部３６により表示デバイス２２に表示させる。【選択図】図２
2012083960.tif 000002
【特許請求の範囲】
【請求項１】
予め定められた周期で所定の計測期間に渡り計測された時系列データを計測期間ごとにグループ化して記憶媒体に記憶する手段と、
前記グループごとに、前記記憶媒体に記憶された時系列データを低次元化されたシンボル系列に変換するシンボル化手段と、
前記グループごとに、前記シンボル系列におけるシンボルの出現傾向をもとにグループを代表する代表文字列を生成する代表文字列生成手段と
検索すべき時系列データを含むグループを設定する検索データ設定手段と、
前記設定されたグループに対応する代表文字列と他の各グループに対応する代表文字列との間の類似度をそれぞれ計算する類似度計算手段と、
前記類似度計算手段により計算された各類似度が予め設定したしきい値以上のグループに含まれる時系列データを前記記憶媒体から読み出し、この読み出された時系列データを検索結果として出力する検索結果出力手段と
を具備することを特徴とする時系列データ検索装置。
【請求項２】
前記シンボル化手段は、
前記グループごとに、前記記憶された時系列データに含まれる計測値及び計測時刻の平均及び標準偏差を算出する手段と、
前記算出された平均及び標準偏差をもとに、ノーマライズされた時系列データを算出する手段と、
前記ノーマライズ処理された時系列データをもとに、低次元化された計測値及び計測時刻をシンボルに変換してシンボル系列を生成する手段と
を備えることを特徴とする請求項１記載の時系列データ検索装置。
【請求項３】
前記代表文字列生成手段は、
前記シンボル系列を予め設定した文字列長ごとに複数の文字列に分割する第１の手段と、
前記分割された文字列ごとに参照セグメント文字列及び比較セグメント文字列を生成する第２の手段と、
前記参照セグメント文字列を１つ選択するごとに、当該選択された参照セグメント文字列と前記生成されたすべての比較セグメント文字列との間の距離をそれぞれ算出して、この算出された各距離のうち予め定めたしきい値以下の距離を有する比較セグメント文字列を抽出し、この抽出された比較セグメント文字列をもとに前記選択された参照セグメント文字列と類似しかつ連続して出現している箇所の文字の数を連続類似文字数として算出する第３の手段と、
前記文字列長を予め設定した範囲で可変するごとに前記第１乃至第３の手段を繰り返し実行させ、この繰り返し処理により得られた連続類似文字数の中の最大値を選択して、この選択した最大の連続類似文字数が算出されたときの参照セグメント文字列を当該参照セグメント文字列が含まれるグループの代表文字列とする第４の手段と
を備えることを特徴とする請求項１記載の時系列データ検索装置。
【請求項４】
予め定められた周期で所定の計測期間に渡り計測された時系列データを計測期間ごとにグループ化して記憶媒体に記憶する過程と、
前記グループごとに、前記記憶媒体に記憶された時系列データを低次元化されたシンボル系列に変換する過程と、
前記グループごとに、前記シンボル系列におけるシンボルの出現傾向をもとにグループを代表する代表文字列を生成する過程と
検索すべき時系列データを含むグループを設定する過程と、
前記設定されたグループに対応する代表文字列と他の各グループに対応する代表文字列との間の類似度をそれぞれ計算する過程と、
前記計算された各類似度が予め設定したしきい値以上のグループに含まれる時系列データを前記記憶媒体から読み出し、この読み出された時系列データを検索結果として出力する過程と
を具備することを特徴とする時系列データ検索方法。
【請求項５】
前記シンボル系列に変換する過程は、
前記グループごとに、前記記憶された時系列データに含まれる計測値及び計測時刻の平均及び標準偏差を算出する過程と、
前記算出された平均及び標準偏差をもとに、ノーマライズされた時系列データを算出する過程と、
前記ノーマライズ処理された時系列データをもとに、低次元化された計測値及び計測時刻をシンボルに変換してシンボル系列を生成する過程と
を備えることを特徴とする請求項４記載の時系列データ検索方法。
【請求項６】
前記代表文字列を生成する過程は、
前記シンボル系列を予め設定した文字列長ごとに複数の文字列に分割する第１の過程と、
前記分割された文字列ごとに参照セグメント文字列及び比較セグメント文字列を生成する第２の過程と、
前記参照セグメント文字列を１つ選択するごとに、当該選択された参照セグメント文字列と前記生成されたすべての比較セグメント文字列との間の距離をそれぞれ算出して、この算出された各距離のうち予め定めたしきい値以下の距離を有する比較セグメント文字列を抽出し、この抽出された比較セグメント文字列をもとに前記選択された参照セグメント文字列と類似しかつ連続して出現している箇所の文字の数を連続類似文字数として算出する第３の過程と、
前記文字列長を予め設定した範囲で可変するごとに前記第１乃至第３の過程を繰り返し実行させ、この繰り返し処理により得られた連続類似文字数の中の最大値を選択して、この選択した最大の連続類似文字数が算出されたときの参照セグメント文字列を当該参照セグメント文字列が含まれるグループの代表文字列とする第４の過程と
を備えることを特徴とする請求項４記載の時系列データ検索方法。
【請求項７】
請求項１乃至３のいずれかに記載の時系列データ検索装置が備える各手段の処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えばセンサ等により計測された時系列データから、注目するデータと類似するデータを検索する時系列データ検索装置、方法及びプログラムに関する。
【背景技術】
【０００２】
ハードウエアの実装技術の高度化によってセンサや携帯端末の小型化が進み、加速度センサ等のセンサを具備した携帯端末が普及し始めている。この種のセンサにより得られた時系列データを利用することで、さまざまなサービスへの展開が期待できる。  
例えば、ユーザの走行時又は歩行時等の各シーンにおいて得られた加速度データから標準偏差等の特徴量を抽出し、この特徴量を学習することで、新たに得られた加速度データからシーンを推定する技術が提案されている（例えば非特許文献１を参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】池谷直紀ほか、「３軸加速度センサに基づく６種移動状態識別方式」DEIM Forum 2010 F10-4
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところが、一般に加速度データ等の時系列データは高いサンプリングレートで計測されるため次元数が高い。このため、非特許文献１により提案されている従来の技術を用いて特徴量の学習及びシーンの推定処理を行うには多大な計算コストを必要とし、実用に適さない。
【０００５】
この発明は上記事情に着目してなされたもので、その目的とするところは、計算コストを抑えつつ、時系列データの集合の中から注目するデータと類似する時系列データを検索することを可能にした時系列データ検索装置、方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
上記目的を達成するためにこの発明の１つの観点は、以下のような構成要素を備えている。すなわち、予め定められた周期で所定の計測期間に渡り計測された時系列データを計測期間ごとにグループ化して記憶媒体に記憶する。この状態で、上記グループごとに上記記憶媒体に記憶された時系列データを低次元化されたシンボル系列に変換し、このシンボル系列におけるシンボルの出現傾向をもとにグループを代表する代表文字列を生成する。そして、検索対象として設定されたグループに対応する代表文字列とその他の各グループに対応する代表文字列との間の類似度をそれぞれ計算し、この計算された各類似度が予め設定したしきい値以上のグループに含まれる時系列データを上記記憶媒体から読み出し、この読み出された時系列データを検索結果として出力するように構成したものである。
【０００７】
したがって、時系列データが高サンプリングレートで計測されたデータであっても、グループごとに低次元化されたシンボル系列に変換され、このシンボル系列がさらに低次元化された代表文字列に変換されて、この代表文字列間で類似度が計算される。このため、類似度の計算処理に要するコストが大幅に低減され、これにより装置の処理負荷を軽減することが可能となる。
【０００８】
また、この発明の１つの観点は以下のような態様を備えることも特徴とする。  
第１の態様は、時系列データをシンボル系列に変換する際に、先ず上記グループごとに時系列データに含まれる計測値及び計測時刻の平均及び標準偏差を算出する。次に、この算出された平均及び標準偏差をもとにノーマライズされた時系列データを算出し、このノーマライズ処理された時系列データをもとに、低次元化された計測値及び計測時刻をシンボルに変換してシンボル系列を生成するものである。
【０００９】
第２の態様は、代表文字列を生成する際に、先ず上記生成されたシンボル系列を予め設定した文字列長ごとに複数の文字列に分割し、この分割された文字列ごとに参照セグメント文字列及び比較セグメント文字列を生成する。次に、生成された参照セグメント文字列を１つ選択するごとに、当該選択された参照セグメント文字列と上記生成されたすべての比較セグメント文字列との間の距離をそれぞれ算出して、この算出された各距離のうち予め定めたしきい値以下の距離を有する比較セグメント文字列を抽出し、この抽出された比較セグメント文字列をもとに上記選択された参照セグメント文字列と類似しかつ連続して出現している箇所の文字の数を連続類似文字数として算出する。そして、上記文字列長を予め設定した範囲で可変するごとに上記第１乃至第３の手段を繰り返し実行させ、この繰り返し処理により得られた連続類似文字数の中の最大値を選択して、この選択した最大の連続類似文字数が算出されたときの参照セグメント文字列を当該参照セグメント文字列が含まれるグループの代表文字列とするようにしたものである。
【発明の効果】
【００１０】
すなわちこの発明によれば、計算コストを抑えつつ、時系列データの中から注目するデータと類似したデータを検索することを可能にした時系列データ検索装置、方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１１】
【図１】この発明の一実施形態に係わる時系列データ検索装置をサービスサーバに備えたシステムの概略構成図。
【図２】図１に示したサービスサーバの構成を示すブロック図。
【図３】図２に示したサービスサーバに設けられるセンサデータ記憶部に記憶されるデータの一例を示す図。
【図４】図２に示したサービスサーバによるシンボル化処理の手順と内容を示すフローチャート。
【図５】図２に示したサービスサーバによる代表文字列抽出処理の手順と内容を示すフローチャート。
【図６】図２に示したサービスサーバによる検索データ設定処理の手順と内容を示すフローチャート。
【図７】図６に示した検索データ設定処理の過程で表示デバイスに表示される検索候補データの一例を示す図。
【図８】図２に示したサービスサーバによる類似度算出処理の手順と内容を示すフローチャート。
【発明を実施するための形態】
【００１２】
以下、図面を参照してこの発明に係わる実施形態を説明する。  
図１は、この発明の一実施形態に係わる時系列データ検索装置を備えたユーザ行動推定システムの概略構成図である。このシステムは、それぞれユーザが所持する複数のユーザ端末ＭＳ１〜ＭＳｎを、通信ネットワークＮＷを介して、時系列データ検索装置としてのサービスサーバＳＶに接続可能としたものである。
【００１３】
通信ネットワークＮＷは、ＩＰ（Internet Protocol）網と、このＩＰ網にアクセスするためのアクセス網とから構成される。アクセス網としては、光公衆通信網、携帯電話網、ＬＡＮ（Local Area Network）、無線ＬＡＮ、ＣＡＴＶ（Cable Television）網等が用いられる。
【００１４】
ユーザ端末ＭＳ１〜ＭＳｎは、携帯電話機やスマートホン、ＰＤＡ（Personal Digital Assistant）、携帯型パーソナル・コンピュータ等からなる携帯端末からなり、いずれもＧＰＳ（Global Positioning Sensor ）センサに加えて加速度センサを備えている。なお、脈拍や血圧等を計測するバイタルセンサや歩数センサ等を備えるようにしてもよい。
【００１５】
ユーザ端末ＭＳ１〜ＭＳｎは、当該端末を所持するユーザの動きの加速度を加速度センサにより定期的に一定期間計測し、この計測されたセンサデータを端末内の記憶部に格納する。そして、この蓄積された一定期間分のセンサデータを、後述するサービスサーバＳＶから送られるデータ送信要求に応じて読み出して、通信ネットワークＮＷを介してサービスサーバＳＶへ送信する。  
なお、加速度センサには、１軸の加速度を計測するセンサと、３軸の加速度を計測するセンサとがある。１軸加速度センサを用いた場合には、計測された１軸の加速度値をそのままセンサデータとし、３軸の加速度センサを用いた場合には計測された３軸の加速度の絶対値をセンサデータとする。
【００１６】
サービスサーバＳＶは、例えば通信事業者又はサービス提供事業者が運用するサーバコンピュータからなり、以下のように構成される。図２はその構成を示す機能ブロック図である。  
すなわち、サービスサーバＳＶは、通信インタフェース１０と、入出力インタフェース２０と、制御ユニット３０と、記憶ユニット４０を備えている。通信インタフェース１０は、制御ユニット３０の制御の下で、通信ネットワークＮＷを介してユーザ端末ＭＳ１〜ＭＳｎとの間でセンサデータを収集するためのデータ通信を行う。
【００１７】
入出力インタフェース２０には、入力デバイス２１及び表示デバイス２２が接続されている。入出力インタフェース２０は、入力デバイス２１から操作データを取り込んで制御ユニット３０へ出力すると共に、制御ユニット３０から出力された表示データを表示デバイス２２に表示させる。
【００１８】
記憶ユニット４０には、この発明を実施するために必要な記憶部として、センサデータ記憶部４１と、代表文字列記憶部４２が設けられている。センサデータ記憶部４１は、制御ユニット３０により携帯端末ＭＳ１〜ＭＳｎから収集されたセンサデータの集合を記憶するために用いられる。代表文字列記憶部４２は、制御ユニット３０によりセンサデータの集合から抽出された代表文字列のデータを記憶するために用いられる。
【００１９】
図３は、センサデータ記憶部４１に記憶されるセンサデータの集合の一例を示すものである。同図に示すように個々のセンサデータは、加速度値とその計測タイミングを示すタイムスタンプとから構成され、これらが計測期間を識別するためにユニークに定められたグループ識別情報（グループＩＤ）に関連付けられて記憶される。
【００２０】
制御ユニット３０は、中央処理ユニット（ＣＰＵ；Central Processing Unit）を中核とするもので、この発明を実施するために必要な処理機能として、センサデータ受信記憶制御部３１と、シンボル化処理部３２と、代表文字列抽出部３３と、検索データ設定部３４と、類似度算出部３５と、検索結果出力部３６とを備えている。これらの処理機能はいずれもアプリケーション・プログラムを上記ＣＰＵに実行させることにより実現される。
【００２１】
センサデータ受信記憶制御部３１は、ユーザ端末ＭＳ１〜ＭＳｎに対しそれぞれ予め決められた一定の周期で通信インタフェースユニット１０からデータ送信要求を送信する。そして、この送信要求に応答してユーザ端末ＭＳ１〜ＭＳｎから送信されるセンサデータの集合を通信インタフェースユニット１０により受信し、この受信されたセンサデータを記憶ユニット４０内のセンサデータ記憶部４１に記憶させる処理を実行する。
【００２２】
シンボル化処理部３２は以下の処理機能を有する。  
(1) 先ず上記センサデータ記憶部４１に記憶されたセンサデータの集合について、その計測期間（グループ）ごとに加速度値の平均及び標準偏差を算出する処理。  
(2) 上記算出された平均及び標準偏差を用いて、上記センサデータ記憶部４１に記憶された各センサデータに対しノーマライズする処理。  
(3) 上記ノーマライズ処理されたセンサデータを用いて、低次元化された加速度値及びタイムスタンプ値を算出し、この算出された低次元化された加速度値及びタイムスタンプ値をシンボルに変換してシンボル系列を生成する処理。
【００２３】
代表文字列抽出部３３は以下の処理機能を有する。  
(1) グループごとに、上記シンボル化処理部３２により生成されたシンボル系列を一定の文字列長で分割し、参照セグメント文字列を生成する処理。  
(2) 同様に、上記低次元化された加速度値に対するシンボル系列を一定の文字列長で分割し、比較セグメント文字列を生成する処理。  
(3) 上記生成された参照セグメント文字列ごとに、当該参照セグメント文字列とすべての比較セグメント文字列との間の距離を算出して、しきい値以下の距離となる比較セグメント文字列を抽出する。そして、この抽出された比較セグメント文字列から上記参照セグメント文字列と類似しかつ連続して出現する箇所の文字列の数（連続類似文字数）を算出する処理。  
(4) グループごとに、上記参照セグメント文字列ごとに得られた連続類似文字数の最大値を求め、この最大となる連続類似文字数が得られた参照セグメント文字列を１つ選択する。そして、この選択された参照セグメント文字列を、代表文字列として記憶ユニット４０内の代表文字列記憶部４２に記憶させる処理。
【００２４】
検索データ設定部３４は以下の処理機能を有する。  
(1) 上記センサデータ記憶部４１からセンサデータのグループＩＤとタイムスタンプを読み出してこれらに選択ボタンを付加した検索候補データ選択画面の表示データを生成する。そして、この検索候補データ選択画面の表示データを入出力インタフェースユニット２０へ出力して表示デバイス２２に表示させる処理。  
(2) 上記表示された検索候補データ選択画面の選択ボタンが入力デバイス２１により選択操作された場合に、その選択操作情報を入出力インタフェースユニット２０から受け取る。そして、この選択操作されたデータが含まれるグループＩＤをセンサデータ記憶部４１から取得し、類似度算出部３５に渡す処理。
【００２５】
類似度算出部３５は、上記代表文字列記憶部４２から各グループの代表文字列を読み出し、上記検索データ設定部３４から渡されたグループＩＤにより指定されるグループの代表文字列に対する、他の各グループの代表文字列の類似度を計算する処理を行う。
【００２６】
検索結果出力部３６は、上記類似度算出部３５により算出された類似度がしきい値以下となるグループを選択し、このグループに含まれるセンサデータをセンサデータ記憶部４１から読み出してその表示データを生成する。そして、この生成された表示データを入出力インタフェースユニット２０へ出力して表示デバイス２２に表示させる処理。
【００２７】
次に、以上のように構成されたサービスサーバＳＶによるデータ検索処理動作を説明する。  
（１）センサデータの収集と記憶
サービスサーバＳＶの制御ユニット３０は、センサデータ受信記憶制御部３１の制御の下で、ユーザ端末ＭＳ１〜ＭＳｎに対しそれぞれ一定の周期で通信インタフェースユニット１０からデータ送信要求を送信する。このデータ送信要求の送信周期は、例えば１日に１回に設定される。なお、送信周期は１日に限るものではなく、それよりも短い時間に設定してもよく、また１週間や１ヶ月等のように長い時間に設定してもよい。
【００２８】
これに対しユーザ端末ＭＳ１〜ＭＳｎは、定常状態において当該端末を所持するユーザの動きの加速度を加速度センサにより定期的に一定期間計測し、この計測されたセンサデータを端末内の記憶部に格納している。計測周期は例えば１秒間隔に設定され、また１回の計測期間は１時間に設定される。そして、この状態でサービスサーバＳＶからデータ送信要求が送られると、上記記憶部から未送信のセンサデータの集合を読み出して、このセンサデータの集合を通信ネットワークＮＷを介してサービスサーバＳＶへ送信する。
【００２９】
サービスサーバＳＶの制御ユニット３０は、上記データ送信要求に応答してユーザ端末ＭＳ１〜ＭＳｎから送信されたセンサデータの集合が通信インタフェースユニット１０により受信されると、この受信されたセンサデータを記憶ユニット４０内のセンサデータ記憶部４１に記憶させる。このとき、各センサデータには、図３に例示したように計測期間ごとにユニークに設定したグループＩＤが関連付けられる。
【００３０】
（２）センサデータのシンボル化処理
上記センサデータ記憶部４１に新たなセンサデータの集合が記憶されると、制御ユニット３０はシンボル化処理部３２の制御の下で、上記新たなセンサデータに対し以下のようにシンボル化処理を行う。図４はその処理手順と処理内容を示すフローチャートである。
【００３１】
（２−１）加速度値の平均及び標準偏差の算出
シンボル化処理部３２は、先ずステップＳ１１においてセンサデータ記憶部４１からグループＩＤごとにセンサデータの集合を読み出し、この読み出されたセンサデータの集合について加速度値の平均及び標準偏差を算出する。
【００３２】
具体的には、センサデータをＣg ＝［ｔg,i ，ｃg,i］tで表したとき、平均ａｖ及び標準偏差ｓｄは以下の式で計算される。  
【数１】
2012083960.tif 000003
【００３３】
ただし、ｇはグループＩＤであり、１≦ｇ≦Ｇ（ＧはグループＩＤの最大値）を満たすものとする。また、ｔg,iはグループＩＤ＝ｇのｉ番目のタイムスタンプであり、ｃg,iはグループＩＤ＝ｇのｉ番目の加速度値を示す。また、ｉはグループＩＤ＝ｇの加速度の要素番号であり、１≦ｉ≦Ｍg （Ｍg はグループＩＤ＝ｇの加速度の総要素数）を満たすものとする。
【００３４】
（２−２）ノーマライズ処理
シンボル化処理部３２は、次にステップＳ１２において、上記算出された平均ａｖ及び標準偏差ｓｄを用い、上記センサデータ記憶部４１に記憶された各センサデータＣg ＝［ｔg,i ，ｃg,i］tの加速度値ｃg,iに対し、以下の式
【数２】
2012083960.tif 000004
に基づいてノーマライズ処理されたセンサデータＣ’g ＝［ｔg,i ，ｃ’g,i］tを算出する。
【００３５】
（２−３）シンボル系列の生成処理
シンボル化処理部３２は、続いてステップＳ１３において、上記ノーマライズ処理されたセンサデータＣ’g ＝［ｔg,i ，ｃ’g,i］tを用いて、低次元化された加速度値及びタイムスタンプ値を算出し、この算出された低次元化された加速度値及びタイムスタンプ値をシンボルに変換してシンボル系列を生成する。
【００３６】
具体的には、先ず以下の式
【数３】
2012083960.tif 000005
に基づいて、低次元化されたセンサデータＣ￣g＝［ｔ￣g,j ，ｃ￣g,j］tを算出する。ここで、ｗgはグループＩＤ＝ｇごとに予め定められたＭg以下の整数である。また、ｊはグループＩＤ＝ｇの低次元化された加速度の要素番号であり、１≦ｊ≦ｗgを満たす。
【００３７】
次に、上記低次元化されたセンサデータＣ￣gの加速度値ｃ￣g,jを以下の式
【数４】
2012083960.tif 000006
に基づいてシンボルに変換し、センサデータＣ￣gに対するシンボル系列
【数５】
2012083960.tif 000007
を生成する。
【００３８】
ここで、βは予め定義された値であり、この実施形態では例えば（J.Lin, E. Keogh, S. Lonardi, B. Chiu, A Symbolic Representation of Time Series, with Implications for Streaming Algorithms, DMKD’ 03, June 13, 2003 ）において定義された値を用いた。上記生成されたシンボル系列は、記憶ユニット４０内の図示しないシンボル系列記憶部に保存される。
【００３９】
（３）代表文字列の抽出
上記シンボル系列の生成処理が終了すると、制御ユニット３０は次に代表文字列抽出部３３の制御の下で、グループごとに代表文字列を以下のように抽出する。図５はその処理手順と処理内容を示すフローチャートである。  
【００４０】
（３−１）参照セグメント文字列の抽出
代表文字列抽出部３３は、先ずステップＳ２１によりシンボル系列記憶部からシンボル系列を読込み、ステップＳ２２により上記シンボル系列を予め設定した文字列長ｍごとに分割する。そして、ステップＳ２３において、文字列長がｍで参照セグメント番号がｌの参照セグメント文字列
【数６】
2012083960.tif 000008
を生成する。ここで、ｍは（１≦ｍ≦ｗg／２）を満たす整数、ｌは（１≦ｌ≦ｗg／ｍ）を満たす参照セグメント文字列の番号である。
【００４１】
（３−２）比較セグメント文字列の抽出
代表文字列抽出部３３は、次にステップＳ２４により、文字列長がｍで比較セグメント番号がｎの比較セグメント文字列
【数７】
2012083960.tif 000009
を生成する。ここで、ｍは（１≦ｍ≦ｗg／２）を満たす整数で、ｎは（１≦ｎ≦ｗg／ｍ）を満たす比較セグメント文字列の番号である。
【００４２】
（３−３）参照セグメント文字列に対する連続類似文字列数の算出
代表文字列抽出部３３は、次にステップＳ２５において、１個の参照セグメント文字列Ref_Segment m,lに対して、すべての比較セグメント文字列Comp_Segment m,nとの間の距離Segment_Distance l,nを以下の式に基づいて算出する。  
【数８】
2012083960.tif 000010
【００４３】
ここで、dist(,)は、２つの文字間の距離を予め定義した関数であり、メモリテーブルに記憶されている。したがって、このメモリテーブルを参照することにより、上記２つの文字間の距離を得ることができる。この実施形態では、例えば（J.Lin, E. Keogh, S. Lonardi, B. Chiu, A Symbolic Representation of Time Series, with Implications for Streaming Algorithms, DMKD’ 03, June 13, 2003 ）において定義されたテーブルを用いている。
【００４４】
続いて代表文字列抽出部３３は、ステップＳ２６において、上記算出された参照セグメント文字列Ref_Segment m,lとすべての比較セグメント文字列Comp_Segment m,nとの間の距離Segment_Distance l,nの中から、予め定めたしきい値以下の距離を選択し、この選択されたしきい値以下の距離を有する比較セグメント文字列を抽出する。そして、この抽出された比較セグメント文字列をもとに、番号が連続している回数の最大値Max_repeat m,lを算出し、参照セグメント文字列Ref_Segment m,lと類似し、かつ連続して出現している箇所の文字数（連続類似文字数）Max_resemble_len m,lを以下の式により算出する。  
【数９】
2012083960.tif 000011
【００４５】
（３−４）すべての参照セグメント文字列についての繰り返し処理
代表文字列抽出部３３は、ステップＳ２７により参照セグメント文字列の現在の番号をチェックし、まだ比較セグメント文字列との間の距離計算が終了していない参照セグメント文字列が残っているか否かを判定する。この判定の結果、未選択の参照セグメント文字列が残っていれば、この未選択の参照セグメント文字列を１つ選択したのちステップＳ２３に戻り、ステップＳ２３〜ステップＳ２６による連続類似文字数Max_resemble_len m,lの算出処理を実行する。
以後同様に、すべての参照セグメント文字列について比較セグメント文字列との間の距離計算が終了するまで、上記したステップＳ２３〜ステップＳ２６による連続類似文字数Max_resemble_len m,lの算出処理を繰り返す。なお、以上の処理により抽出された連続類似文字数Max_resemble_len m,lは、記憶ユニット４０内の代表文字列記憶部４２に一時格納される。
【００４６】
（３−５）すべての文字列長についての繰り返し処理
上記（３−４）の繰り返し処理により、すべての参照セグメント文字列に対する処理が完了すると、代表文字列抽出部３３は次にステップＳ２８により現在の文字列長をチェックし、１から最大の文字列長の半分（ｗg ／２）までのすべての文字列長ｍ（１≦ｍ≦ｗg／２）について連続類似文字数Max_resemble_len m,lの算出処理が終了したか否かを判定する。この判定の結果、まだ処理を行っていない文字列長が残っていれば、未選択の文字列長を選択したのちステップＳ２２に戻り、ステップＳ２２からステップＳ２７による処理を繰り返し実行する。
以後同様に、すべての文字列長ｍ（１≦ｍ≦ｗg／２）に対する処理が終了するまで、上記ステップＳ２２〜ステップＳ２７による処理を繰り返し、各文字列長における参照セグメント文字列ごとの連続類似文字数Max_resemble_len m,lをそれぞれ算出する。
【００４７】
（３−６）代表文字列の決定
すべての文字列長ｍ（１≦ｍ≦ｗg／２）に対する連続類似文字数の算出処理が完了すると、代表文字列抽出部３３は次にステップＳ２９において、代表文字列記憶部４２に格納された各連続類似文字数Max_resemble_len m,lを読み出し、これらの連続類似文字数Max_resemble_len m,lの中から最大値を選択する。そして、この選択した最大の連続類似文字数が算出されたときの参照セグメント文字列を選択し、この選択された参照セグメント文字列を当該参照セグメント文字列が含まれるグループ（ＩＤ＝ｇ）の代表文字列
【数１０】
2012083960.tif 000012
として、グループＩＤに関連付けて代表文字列記憶部４２に記憶させる。ここで、ａは代表文字列の長さを意味する。
【００４８】
以上述べたステップＳ２１〜ステップＳ２９による代表文字列の抽出処理はセンサデータのグループＩＤ＝ｇ（１≦ｇ≦Ｇ）ごとに行われ、この結果代表文字列記憶部４２には各グループの代表文字列が記憶される。
【００４９】
（４）検索データの設定
検索データの設定処理は、オペレータ選択操作に応じて以下のように行われる。図６はその処理手順と処理内容を示すフローチャートである。  
すなわち、制御ユニット３０は検索データ設定部３４の制御の下で、先ずステップＳ３１によりセンサデータ記憶部４１からセンサデータＣg ＝［ｔg,i ，ｃg,i］tを読み出す。そしてステップＳ３２において、グループＩＤ＝ｇ（１≦ｇ≦Ｇ）とそのタイムスタンプｔg,lに選択ボタンを付加した検索候補データ選択画面の表示データを生成し、この生成された表示データを入出力インタフェースユニット２０へ出力する。
この結果、表示デバイス２２には検索候補データ選択画面が表示される。図７はこの検索候補データ選択画面の表示例を示すものである。
【００５０】
この状態で、サービスサーバＳＶのオペレータが入力デバイス２１により所望のグループの選択ボタンを選択操作したとする。検索データ設定部３４は、上記選択ボタンの操作情報をステップＳ３３により入出力インタフェースユニット２０を介して受け取ると、この操作情報をもとに選択されたグループＩＤを認識する。そして、ステップＳ３４により、この認識したグループＩＤを検索データとして類似度計算部３５に与える。
【００５１】
（５）類似度の算出
上記検索データ設定部３４によりグループＩＤが設定されると、制御ユニット３０は次に類似度算出部３５の制御の下で、上記設定されたグループＩＤの代表文字列に対する他のグループの代表文字列の類似度を以下のように計算する。図８はその処理手順と処理内容を示すフローチャートである。
【００５２】
（５−１）代表文字列の読み出し
類似度算出部３５は、先ずステップＳ４１により、上記検索データ設定部３４から検索データとして与えられたグループＩＤに対応する代表文字列（以後検索文字列と呼ぶ）
【数１１】
2012083960.tif 000013
と、他のグループに含まれるセンサデータの代表文字列（以後検索対象文字列と呼ぶ）の集合を、代表文字列記憶部４２からそれぞれ読み出す。
【００５３】
（５−２）検索対象文字列の抽出
類似度算出部３５は、次にステップＳ４２により、上記読み出された検索文字列の長さと同じ長さの検索対象文字列を上記検索対象文字列の集合の中から抽出し、検索対象ベクトルＹu ＝［グループＩＤ，Ｓu ，Comp_Dist u］を生成する。
ここで、ｕは（１≦ｕ≦Ｕg ）を満たす１から始まる番号であり、Ｕg は検索対象文字列の総数を表す。また、Ｓuは当該グループＩＤの代表文字列であり、
【数１２】
2012083960.tif 000014
を意味する。Comp_Dist uは検索文字列に対する検索対象文字列の距離であり、算出方法は後述する。
【００５４】
（５−３）比較文字列の生成
続いて類似度算出部３５は、ステップＳ４３により検索対象ベクトルＹu の代表文字列Ｓuを２個結合した比較文字列
【数１３】
2012083960.tif 000015
を生成する。
【００５５】
（５−４）検索文字列と比較文字列との間の最短距離の算出
類似度算出部３５は、次にステップＳ４４において、検索文字列Ｘと比較文字列Comp_Suとの間の距離Comp_Dist uを以下の式に基づいて算出する。そして、それまで算出された距離より短い距離が算出されるごとに、被検索ベクトルＹuのComp_Dist uをこの短い距離に更新する。  
【数１４】
2012083960.tif 000016
【００５６】
なお、dist(,) は２個の文字間の距離が予め定義された関数であり、メモリテーブルに記憶されている。本実施形態では、（J.Lin, E. Keogh, S. Lonardi, B. Chiu, A Symbolic Representation of Time Series, with Implications for Streaming Algorithms, DMKD’ 03, June 13, 2003 ）において定義されたメモリテーブルを用いた。
【００５７】
（５−５）すべての検索対象ベクトルＹuに対する繰り返し処理
１つの検索対象ベクトルＹuについて、その比較文字列と検索文字列との間の最短距離の計算が終了すると、類似度算出部３５はステップＳ４６により検索対象ベクトルの有無をチェックし、まだ選択していない検索対象ベクトルが残っている場合にはステップＳ４２に戻る。そして、ステップＳ４２により次の検索対象ベクトルを生成し、この検索対象ベクトルについて上記ステップＳ４３〜ステップＳ４５によりその比較文字列と検索文字列との間の最短距離の算出処理を行う。
以後同様に、ステップＳ４６によりすべての検索対象ベクトルが選択されたことが確認されるまで、上記ステップＳ４２〜ステップＳ４６による最短距離算出処理が繰り返し行われる。
【００５８】
（６）検索結果の表示
上記類似度算出部３５による処理が終了すると、制御ユニット３０は最後に検索結果出力部３６を起動し、この検索結果出力部３６の制御の下で、上記検索データ設定部３４により選択設定されたグループの加速度データと類似した加速度データを抽出し、表示させる処理を以下のように実行する。
【００５９】
すなわち、検索対象ベクトルＹu ＝［グループＩＤ，Ｓu ，Comp_Dist u］の中から、検索文字列Ｘと比較文字列Comp_Suとの間の距離Comp_Dist uが予め定めたしきい値以下の検索対象ベクトルを抽出する。そして、この抽出された検索対象ベクトルに対応するグループＩＤと、当該グループＩＤに関連付けられた加速度データ及びタイムスタンプを表示するための表示データを生成し、入出力インタフェースユニット２０へ出力する。この結果、表示デバイス２２には上記グループＩＤとその加速度データ及びタイムスタンプが表示される。
【００６０】
例えば、ユーザが怪我をした場合にその直後の歩行中の加速度データを検索対象データとし、その後得られる当該ユーザの加速度データの中から上記検索対象データと類似するデータを検索し、この類似データの検索件数を例えば週単位でグラフ化して表示する。このようにすると、上記ユーザの管理者である医療従事者や家族は、上記グラフ化された類似データの件数の減少の状況から、ユーザの怪我の回復具合を把握することが可能となる。
【００６１】
なお、上記表示データは、通信インタフェースユニット１０から本人ユーザの端末に送信し表示させるようにしてもよく、さらに本人ユーザとの間で予め加速度データの利用契約を結んでいる管理者（例えば医師や保健師、コンテンツ配信業者）の端末へ送信するようにしてもよい。
【００６２】
以上詳述したようにこの実施形態では、ユーザ端末ＭＳ１〜ＭＳｎから収集した時系列データからなるセンサデータを計測期間ごとにグループ化してセンサデータ記憶部４１に記憶する。この状態で、シンボル化処理部３２により上記センサデータを低次元化されたシンボル系列に変換し、代表文字列抽出部３３により上記シンボル系列をもとにシンボルの出現傾向が最も大きくなる参照セグメント文字列を求めてこれを代表文字列とする。そして、検索データ設定部３４の制御の下でユーザが選択したグループの代表文字列に対する他の各グループの代表文字列の類似度を類似度算出部３５により計算し、類似度がしきい値以下となるグループに含まれるセンサデータを検索結果出力部３６により表示デバイス２２に表示させるようにしている。
【００６３】
したがって、センサデータが高サンプリングレートで計測されたデータであっても、グループごとに低次元化されたシンボル系列に変換され、このシンボル系列がさらに低次元化された代表文字列に変換されて、この代表文字列間で類似度が計算される。このため、類似度の計算処理に要するコストが大幅に低減され、これによりサービスサーバＳＶの処理負荷を軽減することができる。
【００６４】
なお、この発明は上記実施形態に限定されるものではない。例えば、前記実施形態では時系列データ検索装置のすべての機能をサービスサーバに設けたが、そのすべての機能もしくは一部の機能を各ユーザ端末ＭＳ１〜ＭＳｎに分散して設けてもよい。その一例としては、センサデータの取得及び蓄積処理と、比較的処理負荷が小さいシンボル化処理及び代表文字列抽出処理をユーザ端末において行い、サービスサーバはユーザ端末から上記代表文字列のデータを受信して類似度算出処理を行う構成が考えられる。
【００６５】
また加速度データの他に、心拍や血圧等のバイタルデータについて注目パターンの出現数や出現周期を監視する場合に、この発明の時系列データ検索方法を適用するようにしてもよい。  
その他、時系列データ検索装置の構成や、シンボル化処理、代表文字列抽出処理、検索データ設定処理及び類似度算出処理の手順と内容、時系列データの種類及び構成等についても、この発明の要旨を逸脱しない範囲で種々変形して実施可能である。
【００６６】
要するにこの発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００６７】
ＳＶ…サービスサーバ、ＮＷ…通信ネットワーク、ＭＳ１〜ＭＳｎ…ユーザ端末、１０…通信インタフェースユニット、２０…入出力インタフェースユニット、２１…入出力デバイス、２２…表示デバイス、３０…制御ユニット、３１…センサデータ受信記憶制御部、３２…シンボル化処理部、３３…代表文字列抽出部、３４…検索データ設定部、３５…類似度算出部、３６…検索結果出力部、４０…記憶ユニット、４１…センサデータ記憶部、４２…代表文字列記憶部。
【図１】
2012083960.tif 000017
【図２】
2012083960.tif 000018
【図３】
2012083960.tif 000019
【図４】
2012083960.tif 000020
【図５】
2012083960.tif 000021
【図６】
2012083960.tif 000022
【図７】
2012083960.tif 000023
【図８】
2012083960.tif 000024