(57)【要約】  初期セグメント集合生成部（１２０）は訓練時系列データ（Ｓ）から初期セグメント集合（Ｆ）を生成する。初期セグメント集合ソート部（１３０）は初期セグメント集合に含まれる初期セグメントを特徴量の順にソートする。標本セグメント集合生成部（１４０）は初期セグメント集合から標本セグメント集合（Ｅ）を生成する。標本セグメント集合ソート部（１５０）は標本セグメント集合に含まれる標本セグメントを特徴量の順にソートする。検索結果距離算出部（１６０）は標本セグメント集合を用いてテストセグメント毎の検索結果距離（Ｚ）を算出する。
2016117086.tif 000002
【特許請求の範囲】
【請求項１】
時系列に並んだ複数のデータ値から成る訓練時系列データからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントから成る訓練一時セグメント集合を複数生成し、訓練一時セグメント集合のそれぞれの訓練セグメントに含まれるＷ個のデータ値がＷ次元の座標系の座標値として扱われた場合の訓練一時セグメント集合の重心の座標値、を表すＷ個のデータ値を初期セグメントとして訓練一時セグメント集合毎に算出し、訓練一時セグメント集合毎の初期セグメントから成る初期セグメント集合を生成する初期セグメント集合生成部と、
前記初期セグメント集合を、半径の条件である条件半径を有するＷ次元の図形毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される初期一時セグメント集合に分割し、初期一時セグメント集合の図形の重心の座標値を表すＷ個のデータ値から成る標本セグメントを初期一時セグメント集合毎に含む標本セグメント集合を生成する標本セグメント集合生成部と、
を備える時系列データ検索装置。
【請求項２】
前記時系列データ検索装置は、前記初期セグメント集合に含まれる初期セグメント毎に初期セグメントに含まれるデータ値を用いて初期セグメントの特徴量を算出し、前記初期セグメント集合に含まれる初期セグメントを特徴量の順にソートする初期セグメント集合ソート部を備え、
第１の初期一時セグメント集合は、ソート後の前記初期セグメント集合のうちの先頭の初期セグメントが表す座標値を含む図形である第１の図形に含まれる１つ以上の初期セグメントから成り、
前記先頭の初期セグメントを除いて前記第１の初期一時セグメント集合に含まれる初期セグメントは、前記先頭の初期セグメントの次の初期セグメントから順に、初期セグメントが前記第１の図形に含まれるか判定する初期セグメント判定によって判定される
請求項１に記載の時系列データ検索装置。
【請求項３】
前記次の初期セグメントから順に選択された初期セグメントの特徴量と、前記第１の図形の重心である第１の重心の座標値から算出される前記第１の重心の特徴量との差である特徴量差が特徴量差の条件である特徴量差範囲に含まれる場合、選択された初期セグメントに対する前記初期セグメント判定が行われて、
前記特徴量差が前記特徴量差範囲に含まれない場合、選択された初期セグメント以降の初期セグメントに対する前記初期セグメント判定が行われない
請求項２に記載の時系列データ検索装置。
【請求項４】
選択された初期セグメントに対する前記初期セグメント判定において、選択された初期セグメントが表す座標値の座標と前記第１の重心の座標との距離が前記条件半径以下である場合に、選択された初期セグメントが前記第１の図形に含まれると判定される
請求項３に記載の時系列データ検索装置。
【請求項５】
前記初期セグメントの特徴量は前記初期セグメントに含まれるデータ値の平均値であり、
前記第１の重心の特徴量は前記第１の図形の重心の座標値がＷ個のデータ値として扱われた場合のデータ値の平均値である
請求項４に記載の時系列データ検索装置。
【請求項６】
前記初期セグメントの特徴量は前記初期セグメントが表す座標値の座標と基準点との距離であり、
前記第１の重心の特徴量は前記第１の重心と前記基準点との距離である
請求項４に記載の時系列データ検索装置。
【請求項７】
前記初期セグメントの特徴量は、前記初期セグメントに含まれるデータ値を平均した全体平均値と、前記初期セグメントから抽出される初期部分セグメントに含まれるデータ値を平均した部分平均値とであり、
前記第１の重心の特徴量は前記第１の重心の座標値がＷ個のデータ値として扱われた場合のデータ値を平均した重心平均値であり、
前記初期セグメント集合に含まれる初期セグメントが部分平均値の順にソートされて、
前記特徴量差が前記全体平均値と前記重心平均値との差である
請求項４に記載の時系列データ検索装置。
【請求項８】
前記初期セグメントの特徴量は前記初期セグメントに連続して含まれる２つのデータ値毎のデータ値の差から算出される前記初期セグメントの複雑度であり、
前記第１の重心の特徴量は前記第１の重心の座標値がＷ個のデータ値から成る第１の重心セグメントとして扱われた場合の前記第１の重心セグメントに連続して含まれる２つのデータ値毎のデータ値の差から算出される前記第１の重心セグメントの複雑度である
請求項４に記載の時系列データ検索装置。
【請求項９】
前記初期セグメントの特徴量は、前記初期セグメントが表す座標値の座標と前記初期セグメント用の基準平面との最短距離である初期最短距離と、前記初期セグメントの座標軸毎の座標値と前記初期セグメント用の基準平面の座標軸毎の座標値との差から算出される初期指標値とであり、
前記第１の重心の特徴量は、前記第１の重心の座標と前記第１の重心用の基準平面との重心最短距離である重心最短距離と、前記第１の重心の座標軸毎の座標値と前記第１の重心用の基準平面の座標軸毎の座標値との差から算出される重心指標値であり、
前記初期セグメント集合に含まれる初期セグメントが初期最短距離の順にソートされて、
前記特徴量差が、前記初期最短距離と前記重心最短距離との差と、前記初期指標値と前記重心指標値との差の合計である
請求項４に記載の時系列データ検索装置。
【請求項１０】
正のデータ値と負のデータ値とのいずれかだけが前記訓練時系列データに含まれる場合と、正のデータ値と負のデータ値との両方が前記訓練時系列データに含まれる場合で、前記初期セグメントの特徴量の種類が異なる
請求項４に記載の時系列データ検索装置。
【請求項１１】
訓練セグメント毎の指標値から算出される分散値が分散値の条件である分散値範囲に含まれる場合と、前記分散値が前記分散値範囲に含まれない場合で、前記初期セグメントの特徴量の種類が異なり、
訓練セグメントの指標値が、前記訓練セグメントの座標軸毎の座標値と前記訓練セグメント用の基準平面の座標軸毎の座標値との座標軸毎の差から算出される値と、前記訓練セグメントの座標値を表すベクトルの偏角の大きさを示す値とのいずれかである
請求項４に記載の時系列データ検索装置。
【請求項１２】
訓練セグメント毎の指標値のうちの最大値が最大値の条件である最大値範囲に含まれる場合と、前記最大値が前記最大値範囲に含まれない場合で、前記初期セグメントの特徴量の種類が異なり、
訓練セグメントの指標値が、前記訓練セグメントの座標軸毎の座標値と前記訓練セグメント用の基準平面の座標軸毎の座標値との座標軸毎の差から算出される値と、前記訓練セグメントの座標値を表すベクトルの偏角の大きさを示す値とのいずれかである
請求項４に記載の時系列データ検索装置。
【請求項１３】
時系列に並んだ複数のデータ値から成る訓練時系列データからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントを示す訓練一時セグメント集合を複数生成し、訓練一時セグメント集合毎に訓練一時セグメント集合を初期セグメントとして示す初期セグメント集合を生成する初期セグメント集合生成部と、
前記初期セグメント集合を、半径の条件である条件半径を有するＷ次元の図形毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される初期一時セグメント集合に分割し、前記初期一時セグメント集合の図形の重心の座標値に基づいて前記初期一時セグメント集合から訓練セグメントを標本セグメントとして選択し、初期一時セグメント集合毎の標本セグメントを示す標本セグメント集合を生成する標本セグメント集合生成部と、
を備える時系列データ検索装置。
【請求項１４】
時系列に並んだ複数のデータ値から成る訓練時系列データからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントから成る訓練一時セグメント集合を複数生成し、訓練一時セグメント集合のそれぞれの訓練セグメントに含まれるＷ個のデータ値がＷ次元の座標系の座標値として扱われた場合の訓練一時セグメント集合の重心の座標値、を表すＷ個のデータ値を初期セグメントとして訓練一時セグメント集合毎に算出し、訓練一時セグメント集合毎の初期セグメントから成る初期セグメント集合を生成する初期セグメント集合生成処理と、
前記初期セグメント集合を、半径の条件である条件半径を有するＷ次元の図形毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される初期一時セグメント集合に分割し、初期一時セグメント集合の図形の重心の座標値を表すＷ個のデータ値から成る標本セグメントを初期一時セグメント集合毎に含む標本セグメント集合を生成する標本セグメント集合生成処理と、
をコンピュータに実行させる時系列データ検索プログラム。
【請求項１５】
時系列に並んだ複数のデータ値から成る訓練時系列データからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントを示す訓練一時セグメント集合を複数生成し、訓練一時セグメント集合毎に訓練一時セグメント集合を初期セグメントとして示す初期セグメント集合を生成する初期セグメント集合生成処理と、
前記初期セグメント集合を、半径の条件である条件半径を有するＷ次元の図形毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される初期一時セグメント集合に分割し、前記初期一時セグメント集合の図形の重心の座標値に基づいて前記初期一時セグメント集合から訓練セグメントを標本セグメントとして選択し、初期一時セグメント集合毎の標本セグメントを示す標本セグメント集合を生成する標本セグメント集合生成処理と、
をコンピュータに実行させる時系列データ検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列データを検索する技術に関するものである。
【背景技術】
【０００２】
発電プラント、化学プラント、鉄鋼プラント、上下水道プラント等では、プラントのプロセスを制御するための制御システムが導入されている。ビルまたは工場等の設備でも、空調、電気、照明および給排水等を制御するための制御システムが導入されている。また、工場のラインの機器、自動車および鉄道車両には、機器の状態を把握するために、機器の状態を記録するロギングシステムが搭載されている。
これらのシステムでは、機器に取り付けられたセンサによって、時間の経過に従い得られた種々の時系列データが蓄積される。【０００３】
時系列データは以下のように分析される。
最近の時系列データであるテスト時系列データから抽出した部分時系列データが過去の時系列データである訓練時系列データから抽出した部分時系列データと比較されて、訓練時系列データの部分時系列データと類似したテスト時系列データの部分時系列データが検索される。そして、この類似したテスト時系列データの部分時系列データの中でも、訓練時系列データの部分時系列データと最も類似しないテスト時系列データの部分時系列データが、特異点と検出される。そして、特異点の検出によって機器の異常が検出される。【０００４】
部分時系列データは、時系列データからスライド時間窓幅の長さで抽出したデータであり、セグメントと呼ばれる。
テスト時系列データのセグメント毎に距離が最も近い訓練時系列データのセグメントを抽出し、訓練時系列データのセグメントとの距離が最も遠いテスト時系列データのセグメントが特異点である。セグメント間の距離の種類として、ユークリッド距離およびＤＴＷ距離が広く利用されている。ＤＴＷはＤｙｎａｍｉｃ  Ｔｉｍｅ  Ｗａｒｐｉｎｇの略称である。【０００５】
ここで、上記の特異点検出方式を素朴な方式と呼ぶ。
素朴な方式では、訓練時系列データのセグメントとテスト時系列データのセグメントとの全ての組み合わせで距離を求めるため、計算量が大幅に増加する。【０００６】
非特許文献１は、セグメント間の距離の計算よりも計算量が少ない指標を用いて距離の計算を打ち切ることによって、計算量を削減する方式を提案している。
非特許文献２は、テスト時系列データのセグメントと標本セグメントとを比較することによって、計算量を削減する方式を提案している。標本セグメントは、Ｅｘｅｍｐｌａｒと呼ばれ、訓練時系列データから類似したセグメントを集約して生成される。【０００７】
非特許文献２の方式は、標本セグメントの数を十分に絞り込むことができれば、素朴な方式および非特許文献１の方式と比較して大幅に計算量を削減することができる。
しかし、非特許文献２の方式は、訓練時系列データを標本化することによって近似解を求める方式であるため、その誤差である近似誤差に注意する必要がある。【０００８】
非特許文献２の方式において、標本セグメントとの距離が閾値以下のテストセグメントが存在する限り、そのテストセグメントと標本セグメントとの結合が繰り返される。その結果、近似誤差が増加し、近似誤差が許容範囲に収まることを保証できない。
また、標本セグメントに含まれる近似誤差を定量的に求めることもできないため、検索結果に含まれる誤差を評価することもできない。【０００９】
非特許文献３は、セグメント間距離の閾値判定に用いる特徴量として複雑度を開示している。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Ｒａｋｔｈａｎｍａｎｏｎ，  ｅｔ  ａｌ．，  Ｓｅａｒｃｈｉｎｇ  ａｎｄ  ｍｉｎｉｎｇ  ｔｒｉｌｌｉｏｎｓ  ｏｆ  ｔｉｍｅ  ｓｅｒｉｅｓ  ｓｕｂｓｅｑｕｅｎｃｅｓ  ｕｎｄｅｒ  ｄｙｎａｍｉｃ  ｔｉｍｅ  ｗａｒｐｉｎｇ，  ＫＤＤ  ’１２  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １８ｔｈ  ＡＣＭ  ＳＩＧＫＤＤ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｋｎｏｗｌｅｄｇｅ  ｄｉｓｃｏｖｅｒｙ  ａｎｄ  ｄａｔａ  ｍｉｎｉｎｇ  Ｐａｇｅｓ  ２６２−２７０．
【非特許文献２】Ｍ  Ｊｏｎｅｓ，  ｅｔ  ａｌ．，  Ａｎｏｍａｌｙ  Ｄｅｔｅｃｔｉｏｎ  ｉｎ  Ｒｅａｌ−Ｖａｌｕｅｄ  Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  Ｔｉｍｅ  Ｓｅｒｉｅｓ，  ＡＳＥ  Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ  Ｃｏｎｆｅｒｅｎｃｅ，  Ｍａｙ  ２０１４；Ｐａｐｅｒ  Ｎｏ．  ０２７．
【非特許文献３】Ｊｅｓｉｎ  Ｚａｋａｒｉａ，  Ｄｅｖｅｌｏｐｉｎｇ  Ｅｆｆｉｃｉｅｎｔ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｄａｔａ  Ｍｉｎｉｎｇ  Ｌａｒｇｅ  Ｓｃａｌｅ  Ｈｉｇｈ  Ｄｉｍｅｎｓｉｏｎａｌ  Ｄａｔａ，  ＵＣ  Ｒｉｖｅｒｓｉｄｅ  Ｅｌｅｃｔｒｏｎｉｃ  Ｔｈｅｓｅｓ  ａｎｄ  Ｄｉｓｓｅｒｔａｔｉｏｎｓ，  ２０１３．，ｈｔｔｐｓ：／／ｅｓｃｈｏｌａｒｓｈｉｐ．ｏｒｇ／ｕｃ／ｉｔｅｍ／６６０３１６ｚｐ
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、時系列データの検索に用いる標本セグメント集合を、近似誤差が許容範囲に収まることを保証した上で、高速に生成できるようにすることを目的とする。
【課題を解決するための手段】
【００１２】
本発明の時系列データ検索装置は、
時系列に並んだ複数のデータ値から成る訓練時系列データからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントから成る訓練一時セグメント集合を複数生成し、訓練一時セグメント集合のそれぞれの訓練セグメントに含まれるＷ個のデータ値がＷ次元の座標系の座標値として扱われた場合の訓練一時セグメント集合の重心の座標値、を表すＷ個のデータ値を初期セグメントとして訓練一時セグメント集合毎に算出し、訓練一時セグメント集合毎の初期セグメントから成る初期セグメント集合を生成する初期セグメント集合生成部と、
前記初期セグメント集合を、半径の条件である条件半径を有するＷ次元の図形毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される初期一時セグメント集合に分割し、初期一時セグメント集合の図形の重心の座標値を表すＷ個のデータ値から成る標本セグメントを初期一時セグメント集合毎に含む標本セグメント集合を生成する標本セグメント集合生成部と、を備える。
【発明の効果】
【００１３】
本発明によれば、時系列データの検索に用いる標本セグメント集合を高速に生成することができる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態１における時系列データ検索装置１００の機能構成図。
【図２】実施の形態１における時系列データ検索装置１００のハードウェア構成図。
【図３】実施の形態１における時系列データ検索方法のフローチャート。
【図４】実施の形態１における初期セグメント集合生成処理（Ｓ１１０）のフローチャート。
【図５】実施の形態１における標本セグメント集合生成処理（Ｓ１３０）のフローチャート。
【図６】実施の形態１における標本セグメント集合生成処理（Ｓ１３０）の第２ループ処理（Ｓ１３２）のフローチャート。
【図７】実施の形態１における検索結果距離算出処理（Ｓ１５０）のフローチャート。
【図８】実施の形態７における初期セグメント集合生成処理（Ｓ１１０）のフローチャート。
【図９】実施の形態７における標本セグメント集合生成処理（Ｓ１３０）のフローチャート。
【図１０】実施の形態７における標本セグメント集合生成処理（Ｓ１３０）の第２ループ処理（Ｓ１３２）のフローチャート。
【図１１】各実施の形態における標本セグメントに関する概念図。
【図１２】各実施の形態における標本セグメントに関する概念図。
【図１３】各実施の形態における標本セグメントに関する概念図。
【図１４】各実施の形態における標本セグメントに関する概念図。
【図１５】各実施の形態における標本セグメントに関する概念図。
【図１６】各実施の形態における標本セグメントに関する概念図。
【発明を実施するための形態】
【００１５】
実施の形態１．
時系列データの検索に用いる標本セグメント集合を高速に生成する形態について、図１から図７に基づいて説明する。
【００１６】
時系列データの類似検索の考え方について説明する。
時系列データから幅Ｗの窓によって切り出された部分時系列データは、Ｗ次元のベクトルとみなすことができる。よって、訓練時系列データの部分時系列データである訓練セグメントと、テスト時系列データの部分時系列データであるテストセグメントとの距離を求める処理は、Ｗ次元空間の２点の座標間の距離を求める処理とみなすことができる。
また、テスト時系列データの特異点検出は、訓練セグメントの集合から最も離れたテストセグメントを見つける処理とみなすことができる。
そして、時系列データの類似検索はＷ次元空間の近傍検索とみなすことができる。
【００１７】
時系列データが有する第１から第３の特性について説明する。
第１の特性はデータ値の連続性である。温度などの物理現象の計測値の多くは連続的に変化する。また、機械的に制御された機器の計測値は急激に変化しない。例えば、急な電圧の変化は機器の故障の原因になるため、機器にかける電圧は徐々に変化される。
第２の特性はデータ値の周期性である。機器の動作は人間の活動または気象現象に強い相関を持つ。そのような機器の時系列データは、１日、１週間または１年など単位で周期性を持つ。また、プログラムに従って反復動作する機器の時系列データにも、同じようなパターンが繰り返して現れる。
第３の特性はデータ値の局在性である。制御された機器の時系列データに含まれる計測値は所定範囲の値である。そのような時系列データのセグメントは、多次元空間の限られた領域に集中する。例えば、計測値が正の値になるように制御される機器の時系列データのセグメントは、多次元空間の全ての次元における正の領域に含まれる。
【００１８】
＊＊＊構成の説明＊＊＊
図１に基づいて、時系列データ検索装置１００の機能構成について説明する。
時系列データ検索装置１００は、時系列データ取得部１１０と、パラメータ取得部１１１と、初期セグメント集合生成部１２０と、初期セグメント集合ソート部１３０と、標本セグメント集合生成部１４０とを備える。さらに、時系列データ検索装置１００は、標本セグメント集合ソート部１５０と、検索結果距離算出部１６０と、検索結果距離出力部１６１と、データ記憶部１９０とを備える。
【００１９】
時系列データ取得部１１０は、時系列データ検索装置１００に入力される訓練時系列データＳおよびテスト時系列データＴを取得する。
訓練時系列データＳおよびテスト時系列データＴは、時系列に並んだ複数のデータ値から成る時系列データである。
【００２０】
パラメータ取得部１１１は、時系列データ検索装置１００に入力されるスライド幅Ｗおよび近似誤差εを入力する。
スライド幅Ｗは、訓練時系列データＳから抽出される訓練セグメントおよびテスト時系列データＴから抽出されるテストセグメントに含まれるデータ値の個数である。スライド幅Ｗはスライド時間窓幅とも呼ばれる。
近似誤差εは許容される誤差の大きさである。パラメータ取得部１１１は近似誤差εを算出するためのパラメータを用いて近似誤差εを算出してもよい。
【００２１】
初期セグメント集合生成部１２０は、訓練時系列データＳからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントから成る訓練一時セグメント集合を複数生成する。初期セグメント集合生成部１２０は、訓練一時セグメント集合毎に初期セグメントを算出する。初期セグメントは、訓練一時セグメント集合のそれぞれの訓練セグメントに含まれるＷ個のデータ値がＷ次元の座標系の座標値として扱われた場合の訓練一時セグメント集合の重心の座標値、を表すＷ個のデータ値である。そして、初期セグメント集合生成部１２０は、訓練一時セグメント集合毎の初期セグメントから成る初期セグメント集合Ｆを生成する。
訓練一時セグメント集合に複数の訓練セグメントが含まれる場合、複数の訓練セグメントのうちの時系列の順の先頭の訓練セグメントと残りの訓練セグメントとの距離は条件半径ε／２以下である。
【００２２】
初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメント毎に、初期セグメントに含まれるデータ値を用いて、初期セグメントの特徴量を算出する。そして、初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメントを特徴量の順にソートする。
【００２３】
標本セグメント集合生成部１４０は、初期セグメント集合Ｆを１つ以上の初期一時セグメント集合に分割する。初期一時セグメント集合は、半径の条件である条件半径ε／２を有するＷ次元の図形（後述する球Ｂ）毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される。そして、標本セグメント集合生成部１４０は、初期一時セグメント集合毎の標本セグメントを含む標本セグメント集合Ｅを生成する。標本セグメントは、初期一時セグメント集合の図形の重心の座標値を表すＷ個のデータ値から成る。図形の重心は図形の中心と言い換えることもできる。
【００２４】
初期一時セグメント集合は第１の図形に含まれる１つ以上の初期セグメントから成る。第１の図形はソート後の初期セグメント集合Ｆのうちの先頭の初期セグメントが表す座標値を含む図形である。
先頭の初期セグメントを除いて第１の初期一時セグメント集合に含まれる初期セグメントは初期セグメント判定によって判定される。初期セグメント判定は、先頭の初期セグメントの次の初期セグメントから順に、初期セグメントが第１の図形に含まれるか判定する処理である。
【００２５】
特徴量差が特徴量差の条件である特徴量差範囲に含まれる場合、選択された初期セグメントに対する初期セグメント判定が行われる。この特徴量差は、次の初期セグメントから順に選択された初期セグメントの特徴量と、第１の図形の重心である第１の重心の座標値から算出される第１の重心の特徴量との差である。
特徴量差が特徴量差範囲に含まれない場合、選択された初期セグメント以降の初期セグメントに対する初期セグメント判定が行われない。
選択された初期セグメントに対する初期セグメント判定において、選択された初期セグメントが表す座標値の座標と第１の重心の座標との距離が条件半径ε／２以下である場合に、選択された初期セグメントが第１の図形に含まれると判定される。
【００２６】
初期セグメントの特徴量は初期セグメントに含まれるデータ値の平均値である。
第１の重心の特徴量は第１の図形の重心の座標値がＷ個のデータ値として扱われた場合のデータ値の平均値である。
【００２７】
標本セグメント集合ソート部１５０は、標本セグメント集合Ｅに含まれる標本セグメント毎に、標本セグメントに含まれるデータ値を用いて、標本セグメントの特徴量を算出する。そして、標本セグメント集合ソート部１５０は、標本セグメント集合Ｅに含まれる標本セグメントを特徴量の順にソートする。
【００２８】
検索結果距離算出部１６０は、テスト時系列データＴからＷ個のデータ値を時系列の順に抽出して得られるテストセグメントを複数生成する。検索結果距離算出部１６０は、テストセグメントと標本セグメント集合Ｅに含まれる標本セグメントとの組み合わせ毎にテストセグメントと標本セグメントとのセグメント間距離を算出する。そして、検索結果距離算出部１６０は、テストセグメント毎にテストセグメントといずれかの標本セグメントとのセグメント間距離を検索結果距離Ｚとして選択する。
検索結果距離Ｚは最小のセグメント間距離である。
【００２９】
検索結果距離出力部１６１は、テストセグメント毎の検索結果距離を出力する。
【００３０】
データ記憶部１９０は、時系列データ検索装置１００が使用、生成または入出力するデータを記憶する。
【００３１】
図２に基づいて、時系列データ検索装置１００のハードウェア構成例について説明する。
時系列データ検索装置１００は、プロセッサ９０１、補助記憶装置９０２、メモリ９０３、通信装置９０４、入力インタフェース９０５、ディスプレイインタフェース９０６といったハードウェアを備えるコンピュータである。
プロセッサ９０１は信号線９１０を介して他のハードウェアと接続されている。入力インタフェース９０５はケーブル９１１を介して入力装置９０７に接続されている。ディスプレイインタフェース９０６はケーブル９１２を介してディスプレイ９０８に接続されている。
【００３２】
プロセッサ９０１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）であり、他のハードウェアを制御する。例えば、プロセッサ９０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
補助記憶装置９０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。
メモリ９０３は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
通信装置９０４は、データを受信するレシーバ９０４１と、データを送信するトランスミッタ９０４２とを備える。例えば、通信装置９０４は通信チップまたはＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
入力インタフェース９０５はケーブル９１１が接続されるポートであり、ポートの一例はＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）端子である。
ディスプレイインタフェース９０６はケーブル９１２が接続されるポートであり、ポートの一例はＵＳＢ端子またはＨＤＭＩ（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）端子である。ＨＤＭＩは登録商標である。
入力装置９０７は、例えば、マウス、キーボードまたはタッチパネルである。
ディスプレイ９０８は、例えば、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）である。
【００３３】
補助記憶装置９０２には、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）が記憶されている。また、補助記憶装置９０２には、時系列データ検索装置１００に備わる時系列データ取得部１１０、パラメータ取得部１１１、初期セグメント集合生成部１２０、初期セグメント集合ソート部１３０、標本セグメント集合生成部１４０、標本セグメント集合ソート部１５０、検索結果距離算出部１６０、検索結果距離出力部１６１といった「部」の機能を実現するプログラムが記憶されている。
ＯＳの少なくとも一部はメモリ９０３にロードされ、プロセッサ９０１はＯＳを実行しながら「部」の機能を実現するプログラムを実行する。「部」の機能を実現するプログラムは、メモリ９０３にロードされ、プロセッサ９０１に読み込まれ、プロセッサ９０１によって実行される。
なお、時系列データ検索装置１００が複数のプロセッサ９０１を備えて、複数のプロセッサ９０１が「部」の機能を実現するプログラムを連携して実行してもよい。
【００３４】
「部」の処理の結果を示すデータ、情報、信号値および変数値などは、メモリ９０３、補助記憶装置９０２、プロセッサ９０１内のレジスタ、または、プロセッサ９０１内のキャッシュメモリに記憶される。
【００３５】
「部」は「サーキットリ」で実装してもよい。「部」は「回路」、「工程」、「手順」または「処理」に読み替えてもよい。
「回路」及び「サーキットリ」は、プロセッサ９０１、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）といった処理回路を包含する概念である。
【００３６】
＊＊＊動作の説明＊＊＊
図３に基づいて、時系列データ検索装置１００の時系列データ検索方法を構成する各処理の概要を説明する。その後、各処理の詳細について説明する。
【００３７】
Ｓ１１０は初期セグメント集合生成処理である。
Ｓ１１０において、初期セグメント集合生成部１２０は、訓練時系列データＳから初期セグメント集合Ｆを生成する。
【００３８】
Ｓ１２０は初期セグメント集合ソート処理である。
Ｓ１２０において、初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメント毎に特徴量を算出し、初期セグメント集合Ｆに含まれる初期セグメントを特徴量の昇順にソートする。
【００３９】
Ｓ１３０は標本セグメント集合生成処理である。
Ｓ１３０において、標本セグメント集合生成部１４０は、ソート後の初期セグメント集合Ｆから標本セグメント集合Ｅを生成する。
【００４０】
Ｓ１４０は標本セグメントソート処理である。
Ｓ１４０において、標本セグメント集合ソート部１５０は、標本セグメント集合Ｅに含まれる標本セグメント毎に特徴量を算出し、標本セグメント集合Ｅに含まれる標本セグメントを特徴量の昇順にソートする。
【００４１】
Ｓ１５０は検索結果距離算出処理である。
Ｓ１５０において、検索結果距離算出部１６０は、標本セグメント集合Ｅを用いて、テスト時系列データＴに含まれるテストセグメント毎の検索結果距離Ｚを算出する。
【００４２】
Ｓ１６０は検索結果距離出力処理である。
Ｓ１６０において、検索結果距離出力部１６１は、テストセグメント毎の検索結果距離Ｚを出力する。
【００４３】
以降の説明に用いる表記について説明する。
訓練時系列データＳは、データ長Ｍを用いて、Ｓ＝｛Ｓ［０］，Ｓ［１］，・・・，Ｓ［Ｍ−１］｝で表される。つまり、訓練時系列データＳはＳ［０］からＳ［Ｍ−１］までのＭ個のデータ値から成る。
ｉ番目の訓練セグメントＳｉは、スライド幅Ｗを用いて、Ｓｉ＝Ｓ［ｉ：ｉ＋Ｗ−１］で表される。つまり、ｉ番目の訓練セグメントＳｉは、Ｓ［ｉ］からＳ［ｉ＋Ｗ−１］までのＷ個のデータ値から成る。
テスト時系列データＴは、データ長Ｎを用いて、Ｔ＝｛Ｔ［０］，Ｔ［１］，・・・，Ｔ［Ｎ−１］｝で表される。つまり、テスト時系列データＴはＴ［０］からＴ［Ｎ−１］までのＮ個のデータ値から成る。
ｉ番目のテストセグメントＴｉは、スライド幅Ｗを用いて、Ｔｉ＝Ｔ［ｉ：ｉ＋Ｗ−１］で表される。つまり、ｉ番目のテストセグメントＴｉは、Ｔ［ｉ］からＴ［ｉ＋Ｗ−１］までのＷ個のデータ値から成る。
【００４４】
図４に基づいて、初期セグメント集合生成処理（Ｓ１１０）について説明する。
Ｓ１１１において、初期セグメント集合生成部１２０は、初期セグメント集合Ｆを初期化する。初期化された初期セグメント集合Ｆは初期セグメントを含まない。
【００４５】
Ｓ１１２からＳ１１６までの処理は、変数ｉの値が０からインクリメントされてＭ−Ｗ＋１になるまで繰り返し実行される。訓練セグメントＳｉは変数ｉの値が示す番号の訓練セグメントである。Ｍ−Ｗ＋１は最終の訓練セグメントの番号である。図４において、Ｓ１１２からＳ１１７までの処理のループを第１ループとする。
【００４６】
Ｓ１１２において、初期セグメント集合生成部１２０は、訓練一時セグメント集合Ｕｓを初期化し、訓練一時セグメント集合Ｕｓに訓練セグメントＳｉを追加する。このとき、訓練一時セグメント集合Ｕｓは訓練セグメントＳｉだけを含む。
【００４７】
Ｓ１１３からＳ１１５までの処理は、変数ｊの値がｉ＋１からインクリメントされてＭ−Ｗ＋１になるまで繰り返し実行される。訓練セグメントＳｊは変数ｊの値が示す番号の訓練セグメントである。図４において、Ｓ１１３からＳ１１５までの処理のループを第２ループという。
【００４８】
Ｓ１１３において、初期セグメント集合生成部１２０は、訓練セグメントＳｉと訓練セグメントＳｊとのセグメント間距離ｄを算出する。このセグメント間距離ｄの種類はユークリッド距離である。
【００４９】
Ｓ１１４において、初期セグメント集合生成部１２０は、セグメント間距離ｄがε／２以下であるか判定する。
セグメント間距離ｄがε／２以下である場合（ＹＥＳ）、処理はＳ１１５に進む。
セグメント間距離ｄがε／２より大きい場合（ＮＯ）、処理はＳ１１６に進む。
【００５０】
Ｓ１１５において、初期セグメント集合生成部１２０は、訓練一時セグメント集合Ｕｓに訓練セグメントＳｊを追加する。
【００５１】
Ｓ１１６において、初期セグメント集合生成部１２０は、訓練一時セグメント集合Ｕｓに含まれるそれぞれの訓練セグメントが表す座標の重心を算出する。この重心の座標を表すＷ個のデータ値が初期セグメントである。
【００５２】
訓練一時セグメント集合Ｕｓの重心Ｃｅｎｔ（Ｕｓ）は以下の式＜１＞で求められる。
式＜１＞において、ＵＳは｛Ｓ０，Ｓ１，・・・，Ｓｈ｝であり、｜ＵＳ｜はデータ長（ｈ＋１）である。また、Ｆｎ［ｊ］は初期セグメントＦｎのｊ番目の要素である。
【００５３】
【数１】
2016117086.tif 000003
【００５４】
そして、初期セグメント集合生成部１２０は、初期セグメントを初期セグメント集合Ｆに追加する。
Ｓ１１６の後、処理は第２ループを抜けてＳ１１７に進む。
【００５５】
Ｓ１１７において、初期セグメント集合生成部１２０は変数ｉの値を変数ｊの値に更新する。
【００５６】
図４の処理によって、訓練時系列データＳを先頭から末尾に向かって一方向に走査するだけで、初期セグメント集合Ｆを生成することができる。
【００５７】
初期セグメント集合生成処理（Ｓ１１０）は時系列データの第１の特性であるデータ値の連続性を利用した処理であり、連続するセグメント同士の座標の距離は近いと仮定される。よって、連続するセグメントを探索するだけでも、類似したセグメントを見つけることができる。
そして、訓練時系列データＳが先頭から走査されて、半径がε／２である球に含まれる訓練セグメントの集合である訓練一時セグメント集合Ｕｓが抽出されて、訓練一時セグメント集合Ｕｓの重心が初期セグメントとして算出される。
【００５８】
初期セグメント集合ソート処理（Ｓ１２０）について説明する。
初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメント毎に特徴量を算出し、初期セグメント集合Ｆに含まれる初期セグメントを特徴量の昇順にソートする。
初期セグメントの特徴量は初期セグメントに含まれるＷ個のデータ値の平均値である。
【００５９】
初期セグメントＦｎがＦｎ＝｛Ｆｎ［０］，Ｆｎ［１］，・・・，Ｆｎ［Ｗ−１］｝で表される場合、初期セグメントＦｎの平均値Ｍｅａｎ（Ｆｎ）は以下の式＜２＞で表すことができる。
初期セグメントＦｎの平均値Ｍｅａｎ（Ｆｎ）は、初期セグメントＦｎの座標が以下の式＜３＞によって定義されるＷ次元空間の平面に位置することを意味する。式＜３＞において、Ｘｉはｉ番目の座標軸における座標値である。このＷ次元空間の平面は、Ｗ個の座標｛（Ｗ＊Ｍｅａｎ（Ｆｎ），０，・・・，０）、（０，Ｗ＊Ｍｅａｎ（Ｆｎ），・・・，０）、・・・、（０，０，・・・，Ｗ＊Ｍｅａｎ（Ｆｎ））｝を通る平面である。
【００６０】
【数２】
2016117086.tif 000004
【００６１】
ｘ０＋ｘ１＋・・・＋ｘＷ−１＝Ｗ＊Ｍｅａｎ（Ｆｎ）    ・・・＜３＞
【００６２】
初期セグメント集合ソート処理（Ｓ１２０）は、時系列データの第２の特性であるデータ値の周期性を利用するための処理である。
初期セグメント集合Ｆに含まれる初期セグメントを平均値の昇順にソートすることによって、時間的には近くないが距離的には近い初期セグメント同士を近くに並べることができる。
【００６３】
図５に基づいて、標本セグメント集合生成処理（Ｓ１３０）について説明する。
Ｓ１３０−１において、標本セグメント集合生成部１４０は、標本セグメント集合Ｅを初期化する。初期化された標本セグメント集合Ｅは標本セグメントを含まない。
【００６４】
Ｓ１３１−１からＳ１３１−６までの処理は、変数ｉの値が０からインクリメントされて値ｒになるまで繰り返し実行される。値ｒは初期セグメント集合Ｆに含まれる最終の初期セグメントの番号である。但し、変数ｉの値が初期セグメント集合Ｆから除去された初期セグメントの番号である場合、除去された初期セグメントに対する処理はスキップされて、変数ｉの値はインクリメントされる。
初期セグメントＦｉは変数ｉの値が示す番号の初期セグメントである。図５において、Ｓ１３１−１からＳ１３１−６までの処理のループを第１のループとする。
【００６５】
Ｓ１３１−１において、標本セグメント集合生成部１４０は、初期セグメントＦｉを含む球Ｂの重心Ｃを決定する。球Ｂの半径はε／２である。
【００６６】
球Ｂの重心Ｃとして、以下の（１）から（３）に示す重心Ｃが挙げられる。
（１）初期セグメントＦｉが表す座標値が重心Ｃである。
（２）初期セグメントＦｉの座標値と初期セグメントＦｋの座標値とのセグメント間距離ｄがε以下である場合、初期セグメントＦｉの座標値と初期セグメントＦｋの座標値との中間の座標値が重心Ｃである。初期セグメントＦｋは、後述するセグメント間距離の条件を満たす最初の初期セグメントまたは最後の初期セグメントである。初期セグメントＦｋは、セグメント間距離の条件を満たす初期セグメントのうち、最大のセグメント間距離の初期セグメントであってもよい。なお、初期セグメントＦｋは初期セグメントＦｉより後の初期セグメントである。
（３）時系列データは上記第３の特性であるデータ値の局在性を有する。そのため、Ｗ次元空間において、セグメントの座標は原点と座標（１，１，・・・，１）とを通る基本ベクトルＶの周辺に分布すると考えられる。この場合、初期セグメントＦｉの座標を通って基本ベクトルＶと平行なベクトルに沿って、初期セグメントＦｉの座標から正の方向にε／２だけ進んだ座標の座標値が重心Ｃである。この重心Ｃは初期セグメントＦｉ［ｌ］（０≦ｌ＜Ｗ）にε／（２＊√Ｗ）を加えた値である。
【００６７】
Ｓ１３１−１において、球Ｂの重心Ｃを決定すると、標本セグメント集合生成部１４０は重心Ｃの特徴量Ｄ（Ｃ）を算出する。
重心Ｃの特徴量Ｄ（Ｃ）を算出する方法は、Ｓ１２０において初期セグメントＦｎの特徴量を算出する方法と同じである。但し、上記の式＜２＞において、ＦｎはＣに置き換えられる。
【００６８】
Ｓ１３１−２において、標本セグメント集合生成部１４０は、初期一時セグメント集合Ｕｆを初期化し、初期一時セグメント集合Ｕｆに初期セグメントＦｉを追加する。このとき、初期一時セグメント集合Ｕｆは初期セグメントＦｉだけを含む。
【００６９】
Ｓ１３１−３において、標本セグメント集合生成部１４０は、初期セグメントＦｉを初期セグメント集合Ｆから除去する。
【００７０】
Ｓ１３１−４において、標本セグメント集合生成部１４０は、変数Ｓｋｉｐに−１を設定する。変数Ｓｋｉｐは、球Ｂに含まれなかった最初の初期セグメントＦｉの番号を示す変数である。
【００７１】
Ｓ１３２において、標本セグメント集合生成部１４０は第２ループ処理を行う。第２ループ処理（Ｓ１３２）については後述する。
【００７２】
Ｓ１３１−５において、標本セグメント集合生成部１４０は、標本セグメント集合Ｅに重心Ｃを追加する。
【００７３】
Ｓ１３１−６において、標本セグメント集合生成部１４０は変数ｉの値を更新する。
変数Ｓｋｉｐの値が正の値である場合、変数ｉの値は変数Ｓｋｉｐの値に更新される。
変数Ｓｋｉｐの値が負の値（−１）である場合、変数ｉの値は、第２ループ処理（Ｓ１３２）で設定される変数ｊの値に更新される。
【００７４】
図６に基づいて、第２ループ処理（Ｓ１３２）について説明する。
Ｓ１３２−１からＳ１３２−７までの処理は、変数ｊの値がｉ＋１からインクリメントされて値ｒになるまで繰り返し実行される。但し、変数ｊの値が初期セグメント集合Ｆから除去された初期セグメントの番号である場合、除去された初期セグメントに対する処理はスキップされて、変数ｊの値はインクリメントされる。
初期セグメントＦｊは変数ｊの値が示す番号の初期セグメントである。図６において、Ｓ１３２−１からＳ１３２−６までの処理のループを第２のループとする。
【００７５】
Ｓ１３２−１において、標本セグメント集合生成部１４０は、初期セグメントＦｊの特徴量Ｄ（Ｆｊ）と重心Ｃの特徴量Ｄ（Ｃ）との特徴量差がε／（２＊√Ｗ）より大きいか判定する（セグメント間距離の条件）。初期セグメントＦｊの特徴量Ｄ（Ｆｊ）は初期セグメント集合ソート処理（Ｓ１２０）で算出された値である。
【００７６】
特徴量差がε／（２＊√Ｗ）より大きい場合、初期セグメントＦｊの座標を含む平面と重心Ｃの座標を含む平面との距離はε／２を超えるため、初期セグメントＦｊの座標は球Ｂの外側に位置する。したがって、初期セグメントＦｊの座標と重心Ｃの座標との距離を直接計算しなくても、球Ｂの外側に位置する座標の初期セグメントＦｊを判定することができる。
【００７７】
Ｓ１３２−１における条件式｜Ｄ（Ｆｉ）−Ｄ（Ｃ）｜＞ε／（２＊√Ｗ）は、以下の式＜４＞および式＜５＞に基づいて得られる。
式＜４＞は、Ｗ次元空間において、平均値がＤ１である第１の座標を含む平面と平均値がＤ２である第２の座標を含む平面との距離を求める式である。
したがって、第１の座標と第２の座標との距離がｄε以下であるためには、式＜５＞を満たす必要がある。
【００７８】
【数３】
2016117086.tif 000005
【００７９】
特徴量差がε／（２＊√Ｗ）より大きい場合（ＹＥＳ）、処理は第２ループを抜けてＳ１３１−５（図５参照）に進む。
特徴量差がε／（２＊√Ｗ）以下である場合（ＮＯ）、処理はＳ１３２−２に進む。
【００８０】
Ｓ１３２−２において、標本セグメント集合生成部１４０は、重心Ｃの座標と初期セグメントＦｊの座標との距離であるセグメント間距離ｄを算出する。このセグメント間距離ｄの種類はユークリッド距離である。
【００８１】
Ｓ１３２−３において、標本セグメント集合生成部１４０は、セグメント間距離ｄがε／２以下であるか判定する。
セグメント間距離ｄがε／２以下である場合（ＹＥＳ）、処理はＳ１３２−４に進む。
セグメント間距離ｄがε／２より大きい場合（ＮＯ）、処理はＳ１３２−６に進む。
【００８２】
Ｓ１３２−４において、標本セグメント集合生成部１４０は、初期一時セグメント集合Ｕｆに初期セグメントＦｊを追加する。
【００８３】
Ｓ１３２−５において、標本セグメント集合生成部１４０は、初期セグメント集合Ｆから初期セグメントＦｊを除去する。
【００８４】
Ｓ１３２−６において、変数Ｓｋｉｐが負の値（−１）である場合、標本セグメント集合生成部１４０は変数Ｓｋｉｐに変数ｊの値を設定する。負の値以外の場合は、何もしない。
【００８５】
図５および図６の処理によって、初期セグメント集合Ｆを先頭から末尾に向かって一方向に走査するだけで、標本セグメント集合Ｅを生成することができる。
【００８６】
標本セグメントソート処理（Ｓ１４０）について説明する。
標本セグメント集合ソート部１５０は、標本セグメント集合Ｅに含まれる標本セグメント毎に特徴量を算出し、標本セグメント集合Ｅに含まれる標本セグメントを特徴量の昇順にソートする。
標本セグメントＥｎの特徴量を算出する方法は、Ｓ１２０において初期セグメントＦｎの特徴量を算出する方法と同じである。但し、上記の式＜２＞において、ＦｎはＥｎに置き換えられる。
【００８７】
図７に基づいて、検索結果距離算出処理（Ｓ１５０）について説明する。
Ｓ１５１からＳ１５４の処理は、変数ｉの値が０からインクリメントされてＮ−Ｗ＋１になるまで繰り返し実行される。テストセグメントＴｉは変数ｉの値が示す番号のテストセグメントである。Ｎ−Ｗ＋１は最終のテストセグメントの番号である。検索結果距離Ｚ［ｉ］はテストセグメントＴｉの検索結果距離Ｚである。図７において、Ｓ１５１からＳ１５４までの処理のループを第１ループとする。
【００８８】
Ｓ１５１において、検索結果距離算出部１６０は、検索結果距離Ｚ［ｉ］に無限大を設定する。
【００８９】
Ｓ１５２からＳ１５４までの処理は、変数ｊの値が０からインクリメントされて値ｅになるまで繰り返し実行される。値ｅは標本セグメント集合Ｅに含まれる最終の標本セグメントの番号である。図７において、Ｓ１５２からＳ１５４までの処理のループを第２ループとする。
【００９０】
Ｓ１５２において、検索結果距離算出部１６０は、テストセグメントＴｉと標本セグメントＥｊとのセグメント間距離ｄを算出する。このセグメント間距離ｄの種類はユークリッド距離である。但し、このセグメント間距離ｄの種類はＤＴＷ距離または他の種類の距離であってもよい。
【００９１】
Ｓ１５３において、検索結果距離算出部１６０は、セグメント間距離ｄが検索結果距離Ｚ［ｉ］より小さいか判定する。
セグメント間距離ｄが検索結果距離Ｚ［ｉ］より小さい場合（ＹＥＳ）、処理はＳ１５４に進む。
セグメント間距離ｄが検索結果距離Ｚ［ｉ］以上である場合（ＮＯ）、Ｓ１５４の処理は行われない。
【００９２】
Ｓ１５４において、検索結果距離算出部１６０は、検索結果距離Ｚ［ｉ］をセグメント間距離ｄで更新する。
【００９３】
検索結果距離出力処理（Ｓ１６０）について説明する。
検索結果距離出力部１６１は、テストセグメント毎の検索結果距離Ｚを出力する。
テストセグメントの検索結果距離Ｚが大きい場合、そのテストセグメントはいずれの標本セグメントとも類似しない。言い換えると、そのテストセグメントはいずれの訓練セグメントとも類似しない。
したがって、テストセグメントの検索結果距離Ｚが他のセグメントと比べて相対的に大きい場合、そのテストセグメントはテスト時系列データＴの特異点とみなすことができる。
【００９４】
時系列データ検索方法において、近似誤差εを半径として有する球に含まれる座標のセグメントを代表する標本セグメントは、初期セグメントとして半径がε／２である球を求める初期セグメント集合生成処理（Ｓ１１０）と、半径がε／２である同一の球に含まれる初期セグメントを結合して標本セグメントを求める標本セグメント集合生成処理（Ｓ１３０）との２段階の処理によって求められた。
Ｗ次元空間において、標本セグメントは、近似誤差εを半径として有する多次元超球の重心であり、その球に含まれる座標を表す訓練セグメントを代表する。つまり、テストセグメントと標本セグメントとのセグメント間距離ｄは、テストセグメントと訓練セグメントとのセグメント距離がｄ±εの範囲に含まれることを意味する。
【００９５】
一方、テストセグメントと訓練セグメントとのセグメント間距離を標本セグメントを用いずに算出する場合、多くの計算量が必要になる。例えば、テストセグメントと訓練セグメントとのそれぞれの個数がＮである場合、Ｎ２個のセグメント間距離を計算する必要がある。そのため、標本セグメントの数が最小となるように、標本セグメントを選択するのが理想である。言い換えると、最適な半径を有する最適な球を選択するのが理想であるが、最適な半径を有する最適な球を多次元空間から選択するためには、セグメントの密度分布を調べるなど、多くの計算量が必要になる。最適な球の選択は、最終的な標本セグメントの数が最小になる球の選択の他に、球に含まれる標本セグメントの数が最大になる球の選択も意味する。
実施の形態では、最適な球の選択よりも、計算量の削減を優先した。
【００９６】
＊＊＊効果の説明＊＊＊
時系列データ検索装置１００は、近似誤差εを厳密に半径として有する球に含まれる訓練セグメントの集合の代表として、標本セグメントを生成することができる。これにより、類似検索における近似誤差εを保証することができる。
また、時系列データ検索装置１００は、訓練時系列データＳを先頭から１回走査するだけで初期セグメント集合Ｆを生成して、初期セグメント集合Ｆを先頭から１回走査するだけで標本セグメント集合Ｅを生成することができる。
したがって、近似誤差εが保証された標本セグメントを訓練時系列データＳから高速に抽出することができる。
【００９７】
実施の形態２．
平均値とは異なる特徴量を用いる形態について説明する。但し、実施の形態１と重複する説明は省略する。
【００９８】
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
【００９９】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０は実施の形態１と以下のように異なる。
【０１００】
Ｓ１２０において、初期セグメントＦｉの特徴量Ｄ（Ｆｉ）は、初期セグメントＦｉが表すが座標値の座標と基準点との距離である。
基準点はＷ次元空間の原点０＝｛０，０，・・・，０｝である。その場合、初期セグメントＦｉはＤ（Ｆｉ）を半径として有する球面に位置する。但し、基準点は原点０以外の座標であってもよい。
【０１０１】
Ｓ１３０において、重心Ｃの特徴量Ｄ（Ｃ）は重心Ｃと基準点との距離である。
Ｓ１３２−１（図６参照）において、特徴量Ｄ（Ｆｉ）と特徴量Ｄ（Ｃ）との特徴量差がε／２より大きいか判定される。この条件式｜Ｄ（Ｆｉ）−Ｄ（Ｃ）｜＞ε／２は、以下の式＜６＞および式＜７＞に基づいて得られる。
式＜６＞は、Ｗ次元空間において、基準点からの距離がＤ１である第１の座標と基準点からの距離がＤ２である第２の座標との距離の最小値を求める式である。
したがって、第１の座標と第２の座標との距離がｄε以下であるためには、式＜７＞を満たす必要がある。
【０１０２】
【数４】
2016117086.tif 000006
【０１０３】
基準点が原点０である場合、初期セグメントＦｉの座標と重心Ｃの座標との距離の範囲は、以下の式＜８＞で表すことができる。
式＜８＞は、初期セグメントＦｉが分散しているため初期セグメントＦｉと基準点との距離が｜Ｄ（Ｆｉ）＋Ｄ（Ｃ）｜を超えることが多い場合、Ｓ１３２−１において探索をより早く打ち切ることができることを意味する。
【０１０４】
【数５】
2016117086.tif 000007
【０１０５】
Ｓ１４０において、標本セグメントＥｉの特徴量Ｄ（Ｅｉ）は、標本セグメントＥｉが表す座標値の座標と基準点との距離である。
【０１０６】
＊＊＊効果の説明＊＊＊
初期セグメントが分散している場合、時系列データ検索装置１００は、標本セグメントを生成するための探索を早く打ち切り、標本セグメント集合を高速に生成することができる。
【０１０７】
実施の形態３．
平均値とは異なる特徴量を用いる形態について説明する。但し、実施の形態１と重複する説明は省略する。
【０１０８】
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
【０１０９】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０およびＳ１４０は実施の形態１と以下のように異なる。
【０１１０】
Ｓ１２０において、初期セグメントの特徴量は、初期セグメントから抽出される初期部分セグメントに含まれるデータ値を平均した部分平均値である。つまり、初期セグメント集合Ｆに含まれる初期セグメントは部分平均値の順にソートされる。
初期部分セグメントを抽出する方法として、以下の（１）および（２）の方法が挙げられる。
（１）初期セグメントＦｉ［ｉ：ｉ＋Ｗ−１］の前半部分Ｆｉ（ｆ）［ｉ：（ｉ＋Ｗ−１）／２］または後半部分Ｆｉ（ｂ）［（ｉ＋Ｗ−１）／２：ｉ＋Ｗ−１］が初期部分セグメントとして抽出される。
（２）初期セグメントＦｉ［ｉ：ｉ＋Ｗ−１］を４等分して得られる第１部分Ｆｉ（１）［ｉ：（ｉ＋Ｗ−１）／４］および第３部分Ｆｉ（３）［（ｉ＋Ｗ−１）／２：（ｉ＋Ｗ−１）＊３／４］が初期部分セグメントとして抽出される。または、第２部分Ｆｉ（２）［（ｉ＋Ｗ−１）／４：（ｉ＋Ｗ−１）／２］および第４部分Ｆｉ（４）［（ｉ＋Ｗ−１）＊３／４：ｉ＋Ｗ−１］が初期部分セグメントとして抽出される。
【０１１１】
Ｓ１４０において、標本セグメントの特徴量は、標本セグメントから抽出される標本部分セグメントに含まれるデータ値を平均した部分平均値である。つまり、標本セグメント集合Ｅに含まれる標本セグメントは部分平均値の順にソートされる。
【０１１２】
Ｓ１３０における初期セグメントの特徴量Ｄ（Ｆｉ）および重心の特徴量Ｄ（Ｃ）は、実施の形態１と同じである。
つまり、初期セグメントの特徴量Ｄ（Ｆｉ）は初期セグメントに含まれるデータ値を平均した全体平均値であり、重心の特徴量Ｄ（Ｃ）は重心の座標値がＷ個のデータ値として扱われた場合のデータ値を平均した重心平均値である。また、初期セグメントの特徴量Ｄ（Ｆｉ）と重心特徴量Ｄ（Ｃ）との特徴量差は全体平均値と重心平均値との差である。
Ｓ１３２−１（図６参照）における条件式は、実施の形態１と同じく、｜Ｄ（Ｆｉ）−Ｄ（Ｃ）｜＞ε／（２＊√Ｗ）である。
【０１１３】
＊＊＊効果の説明＊＊＊
全体平均値が近い初期セグメントが多数存在する場合であっても、初期セグメント集合を部分平均値の順にソートすることによって、初期セグメントの探索範囲の拡大を抑止して、標本セグメント集合を高速に生成することができる。
【０１１４】
実施の形態４．
平均値とは異なる特徴量を用いる形態について説明する。但し、実施の形態１と重複する説明は省略する。
【０１１５】
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
【０１１６】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０の内容は実施の形態１と以下のように異なる。
【０１１７】
Ｓ１２０において、初期セグメントＦｉの特徴量Ｄ（Ｆｉ）は初期セグメントＦｉの複雑度である。この複雑度は、初期セグメントＦｉに連続して含まれる２つのデータ値毎のデータ値の差から算出される。
初期セグメントＦｉの複雑度ｃｏｍｐ（Ｆｉ）は、以下の式＜９＞で算出される。
【０１１８】
【数６】
2016117086.tif 000008
【０１１９】
Ｓ１３０において、重心Ｃの特徴量Ｄ（Ｃ）は重心セグメントの複雑度である。この複雑度は、重心Ｃの座標値がＷ個のデータ値から成る重心セグメントとして扱われた場合の重心セグメントに連続して含まれる２つのデータ値毎のデータ値の差から算出される。
重心セグメントの複雑度ｃｏｍｐ（Ｃ）を算出する方法は、Ｓ１２０において初期セグメントＦｉの複雑度ｃｏｍｐ（Ｆｉ）を算出する方法と同じである。但し、上記の式＜９＞において、ＦｉはＣに置き換えられる。
【０１２０】
Ｓ１３２−１（図６参照）において、特徴量Ｄ（Ｆｉ）と特徴量Ｄ（Ｃ）との特徴量差がεより大きいか判定される。この条件式｜Ｄ（Ｆｉ）−Ｄ（Ｃ）｜＞εは、以下の式＜１０＞および式＜１１＞に基づいて得られる。
第１の標本セグメントＥ１の座標と第２の標本セグメントＥ２の座標とのユークリッド距離ｄｉｓｔ（Ｅ１，Ｅ２）は、式＜１０＞の範囲を満たす。
したがって、第１の標本セグメントＥ１の座標と第２の標本セグメントＥ２の座標との距離がｄε以下であるためには、式＜１１＞を満たす必要がある。
【０１２１】
【数７】
2016117086.tif 000009
【０１２２】
Ｓ１４０において、標本セグメントＥｉの特徴量Ｄ（Ｅｉ）は標本セグメントＥｉの複雑度である。
標本セグメントＥｉの複雑度ｃｏｍｐ（Ｅｉ）を算出する方法は、Ｓ１２０において初期セグメントＦｉの複雑度ｃｏｍｐ（Ｆｉ）を算出する方法と同じである。但し、上記の式＜９＞において、ＦｉはＥｉに置き換えられる。
【０１２３】
＊＊＊効果の説明＊＊＊
実施の形態１と同じく、近似誤差εが保証された標本セグメントを訓練時系列データＳから高速に抽出することができる。
【０１２４】
実施の形態５．
平均値とは異なる特徴量を用いる形態について説明する。但し、実施の形態１と重複する説明は省略する。
【０１２５】
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
【０１２６】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０は実施の形態１と以下のように異なる。
【０１２７】
Ｓ１２０において、初期セグメントの特徴量は初期最短距離である。つまり、初期セグメント集合Ｆに含まれる初期セグメントは初期最短距離の順にソートされる。
初期最短距離は初期セグメント用の基準平面と、Ｗ次元空間の原点Ｏとの最短距離である。
初期セグメント用の基準平面は、実施の形態１の式＜３＞で表される平面である。
初期セグメントＦｉの初期最短距離ＦｅａｔＭ（Ｆｉ）は、以下の式＜１２＞で算出される。
【０１２８】
【数８】
2016117086.tif 000010
【０１２９】
Ｓ１３０において、初期セグメントＦｉの特徴量Ｄ（Ｆｉ）は初期最短距離および初期指標値である。初期指標値は、初期セグメントの座標軸毎の座標値と初期セグメント用の基準平面の座標軸毎の座標値との差から算出される値である。
初期セグメントＦｉの初期指標値ＦｅａｔＲ（Ｆｉ）は、以下の式＜１３＞で算出される。
【０１３０】
【数９】
2016117086.tif 000011
【０１３１】
初期最短距離は、Ｗ次元空間の原点から初期セグメント用の基準平面まで降ろした垂線の足までの距離である。初期指標値は、Ｗ次元空間の原点から初期セグメント用の基準平面まで降ろした垂線の足から初期セグメントが表す座標値までの距離である。直感的には、初期指標値は、基準平面上の初期セグメントが表す座標値のずれを表している。
【０１３２】
また、重心Ｃの特徴量Ｄ（Ｃ）は重心最短距離および重心指標値である。
重心最短距離はＷ次元空間の原点Ｏと重心用の基準平面との最短距離である。重心用の基準平面は実施の形態１の式＜３＞で表される平面である。但し、式＜３＞において、ＦｎはＣに置き換えられる。重心Ｃの重心最短距離ＦｅａｔＭ（Ｃ）は上記の式＜１２＞で算出される。但し、式＜１２＞において、ＦｉはＣに置き換えられる。
重心指標値は重心の座標軸毎の座標値と重心用の基準平面の座標軸毎の座標値との差から算出される値である。重心Ｃの重心指標値ＦｅａｔＲ（Ｃ）は上記の式＜１３＞で算出される。但し、式＜１３＞において、ＦｉはＣに置き換えられる。
【０１３３】
Ｓ１３２−１（図６参照）において、特徴量Ｄ（Ｆｉ）と特徴量Ｄ（Ｃ）との特徴量差がε／２より大きいか判定される。この特徴量差は、初期最短距離と重心最短距離との差と、初期指標値と重心指標値との差の合計である。Ｓ１３２−１における条件式｜Ｄ（Ｆｉ）−Ｄ（Ｃ）｜＞ε／２は、以下の式＜１４＞および式＜１５＞に基づいて得られる。
第１の標本セグメントＥ１の座標と第２の標本セグメントＥ２の座標とのユークリッド距離ｄｉｓｔ（Ｅ１，Ｅ２）は、式＜１４＞の範囲を満たす。
したがって、第１の標本セグメントＥ１の座標と第２の標本セグメントＥ２の座標との距離がｄε以下であるためには、式＜１５＞を満たす必要がある。
【０１３４】
【数１０】
2016117086.tif 000012
【０１３５】
Ｓ１４０において、標本セグメントの特徴量は標本最短距離である。つまり、標本セグメント集合Ｅに含まれる標本セグメントは標本最短距離の順にソートされる。
標本最短距離は標本セグメントが表す座標値の座標と初期セグメント用の基準平面との最短距離である。標本セグメント用の基準平面は実施の形態１の式＜３＞で表される平面である。但し、式＜３＞において、ＦｎはＥｎに置き換えられる。標本セグメントＥｉの標本最短距離ＦｅａｔＭ（Ｅｉ）は上記の式＜１２＞で算出される。但し、式＜１２＞において、ＦｉはＥｉに置き換えられる。
【０１３６】
なお、実施の形態１で説明した平均値による判定方法は、２平面間の距離に基づく判定と言い換えることができる。すなわち、実施の形態１において｜Ｄ（Ｆｉ）−Ｄ（Ｃ）｜は以下の式＜１６＞に置き換えることができる。
【０１３７】
【数１１】
2016117086.tif 000013
【０１３８】
＊＊＊効果の説明＊＊＊
２平面間の最短距離を取る点からのずれを考慮することによって、距離を厳しく判定することができる。そして、初期セグメントの探索を早く打ち切って、標本セグメントを高速に抽出することができる。
【０１３９】
実施の形態６．
条件によって特徴量の種類を選択する形態について説明する。但し、実施の形態１から実施の形態５と重複する説明は省略する。
【０１４０】
＜実施例１＞
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
但し、正のデータ値と負のデータ値とのいずれかだけが訓練時系列データＳに含まれる場合と、正のデータ値と負のデータ値との両方が訓練時系列データＳに含まれる場合で、初期セグメントの特徴量の種類が異なる。
【０１４１】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０は実施の形態１と以下のように異なる。
【０１４２】
Ｓ１２０において、初期セグメント集合ソート部１３０は、実施の形態１から実施の形態５のそれぞれで説明した種類の特徴量を算出する。
また、初期セグメント集合ソート部１３０は、正負両方のデータ値が訓練時系列データＳに含まれるか判定する。この判定を特徴量の算出と同時に行うことにより、判定のオーバーヘッドを小さくすることができる。
正負両方のデータ値が訓練時系列データＳに含まれる場合、初期セグメント集合ソート部１３０は、実施の形態１、実施の形態３、実施の形態４または実施の形態５で説明した種類の特徴量を選択する。
正負いずれかのデータ値が訓練時系列データＳに含まれる場合、初期セグメント集合ソート部１３０は、実施の形態２または実施の形態４で説明した種類の特徴量を選択する。
そして、初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメントを選択した特徴量の順にソートする。
【０１４３】
Ｓ１３０およびＳ１４０は、選択された種類の特徴量について説明した実施の形態と同じである。
【０１４４】
＜実施例２＞
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
但し、訓練セグメント毎の指標値から算出される分散値が分散値の条件である分散値範囲に含まれる場合と、分散値が分散値範囲に含まれない場合で、初期セグメントの特徴量の種類が異なる。
訓練セグメントの指標値は、訓練セグメントの座標軸毎の座標値と訓練セグメント用の基準平面の座標軸毎の座標値との差から算出される値である。
【０１４５】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０は実施の形態１と以下のように異なる。
【０１４６】
Ｓ１２０において、初期セグメント集合ソート部１３０は、実施の形態１から実施の形態５のそれぞれで説明した種類の特徴量を算出する。
また、初期セグメント集合ソート部１３０は訓練セグメントＳｉ毎に特徴量としてＦｅａｔＲ（Ｓｉ）を算出する。この特徴量は実施の形態５で説明した指標値である。
さらに、初期セグメント集合ソート部１３０は訓練セグメント毎の特徴量の分散値を算出し、分散値が分散値範囲に含まれるか否かを閾値を用いて判定する。
分散値が閾値以下である場合、初期セグメント集合ソート部１３０は、実施の形態１、実施の形態３または実施の形態４で説明した種類の特徴量を選択する。
分散値が閾値より大きい場合、初期セグメント集合ソート部１３０は、実施の形態２、実施の形態４または実施の形態５で説明した種類の特徴量を選択する。
そして、初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメントを選択した特徴量の順にソートする。
【０１４７】
Ｓ１３０およびＳ１４０は、選択された種類の特徴量について説明した実施の形態と同じである。
【０１４８】
この実施例２は、実施の形態５で説明したＦｅａｔＲ（Ｅｉ）用いる方法である。
時系列データの第３の特性によって、データ値の変化が緩やかな時系列データのセグメントはＷ次元空間の基本ベクトルの周辺に分布すると考えられる。基本ベクトルＶは原点０と点（１，１，・・・，１）とを通るベクトルである。このＦｅａｔＲ（Ｅｉ）は標本セグメントＥｉが表す標本ベクトルＥｌと基本ベクトルＶとのずれを表す指標になる。そして、実施例２が導き出される。
【０１４９】
＜実施例３＞
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
但し、訓練セグメント毎の指標値から算出される最大値が最大値の条件である最大値範囲に含まれる場合と、最大値が最大値範囲に含まれない場合で、初期セグメントの特徴量の種類が異なる。
訓練セグメントの指標値は、訓練セグメントの座標軸毎の座標値と訓練セグメント用の基準平面の座標軸毎の座標値との差から算出される値である。
【０１５０】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０は、＜実施例２＞のＳ１２０からＳ１４０において分散値を最大値に置き換えた処理である。
【０１５１】
＜実施例４＞
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
但し、訓練セグメント毎の指標値から算出される分散値が分散値の条件である分散値範囲に含まれる場合と、分散値が分散値範囲に含まれない場合で、初期セグメントの特徴量の種類が異なる。
訓練セグメントの指標値は、訓練セグメントの座標値を表すベクトルの偏角の大きさを示す値である。
【０１５２】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０は実施の形態１と以下のように異なる。
【０１５３】
Ｓ１２０において、初期セグメント集合ソート部１３０は、実施の形態１から実施の形態５のそれぞれで説明した種類の特徴量を算出する。
また、初期セグメント集合ソート部１３０は訓練セグメントＳｉ毎に特徴量として偏角φを算出する。偏角φは訓練ベクトルＳｌと基本ベクトルＶとの内積から求まる値である。訓練ベクトルＳｌは原点０と訓練セグメントＳｉの座標とを通るベクトルである。
偏角φは以下の式＜１７＞および式＜１８＞で算出される。ベクトルを表す符号には上部に矢印を付記している。
【０１５４】
【数１２】
2016117086.tif 000014
【０１５５】
さらに、初期セグメント集合ソート部１３０は訓練セグメント毎の特徴量の分散値を算出し、分散値が分散値範囲に含まれるか否かを閾値を用いて判定する。
分散値が閾値以下である場合、初期セグメント集合ソート部１３０は、実施の形態１、実施の形態３または実施の形態４で説明した種類の特徴量を選択する。
分散値が閾値より大きい場合、初期セグメント集合ソート部１３０は、実施の形態２、実施の形態４または実施の形態５で説明した種類の特徴量を選択する。
そして、初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメントを選択した特徴量の順にソートする。
【０１５６】
Ｓ１３０およびＳ１４０は、選択された種類の特徴量について説明した実施の形態と同じである。
【０１５７】
＜実施例５＞
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
但し、訓練セグメント毎の指標値から算出される最大値が最大値の条件である最大値範囲に含まれる場合と、最大値が最大値範囲に含まれない場合で、初期セグメントの特徴量の種類が異なる。
訓練セグメントの指標値は、訓練セグメントの座標値を表すベクトルの偏角の大きさを示す値である。
【０１５８】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１２０からＳ１４０は、＜実施例４＞のＳ１２０からＳ１４０において分散値を最大値に置き換えた処理である。
【０１５９】
＊＊＊効果の説明＊＊＊ 
初期セグメントの距離判定において、実施の形態１から実施の形態４では１個の特徴量を用いて、実施の形態５では２個の特徴量を用いた。一般的に、特徴量の数が増えると、厳密な判定が可能になる一方で、計算量が増加する。
そこで、実施の形態６では、計算量の増加量よりも厳密な判定による探索範囲の削減量の方が大きいと考えられる場合に２個の特徴量を用いる。
つまり、実施の形態６は、時系列データの特性に応じて特徴量を選択し、標本セグメントを生成するための初期セグメントの探索を効率的に実行することができる。
【０１６０】
実施の形態７．
初期一時セグメント集合Ｕｆに含まれる初期セグメントから標本セグメントを選択する形態について、図８から図１０に基づいて説明する。但し、実施の形態１と重複する説明は省略する。
【０１６１】
＊＊＊構成の説明＊＊＊
時系列データ検索装置１００の機能構成は実施の形態１の図１と同じである。
但し、初期セグメント集合生成部１２０は以下のように機能する。
初期セグメント集合生成部１２０は、訓練時系列データＳからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントを示す訓練一時セグメント集合を複数生成する。そして、初期セグメント集合生成部１２０は、訓練一時セグメント集合毎に訓練一時セグメント集合を初期セグメントとして示す初期セグメント集合Ｆを生成する。
訓練一時セグメント集合に複数の訓練セグメントが含まれる場合、複数の訓練セグメントのうちの時系列の順の先頭の訓練セグメントと残りの訓練セグメントとの距離は条件半径ε／２以下である。
【０１６２】
また、標本セグメント集合生成部１４０は以下のように機能する。
標本セグメント集合生成部１４０は、初期セグメント集合Ｆを１つ以上の初期一時セグメント集合に分割する。初期一時セグメント集合は、半径の条件である条件半径ε／２を有するＷ次元の図形（球Ｂ）毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される。そして、標本セグメント集合生成部１４０は、初期一時セグメント集合の図形の重心の座標値に基づいて初期一時セグメント集合から訓練セグメントを標本セグメントとして選択し、初期一時セグメント集合毎の標本セグメントを示す標本セグメント集合Ｅを生成する。
【０１６３】
＊＊＊動作の説明＊＊＊
時系列データ検索方法の処理の流れは実施の形態１の図３と同じである。
但し、Ｓ１１０からＳ１３０は実施の形態１と以下のように異なる。
【０１６４】
図８に基づいて、初期セグメント集合生成処理（Ｓ１１０）について説明する。実施の形態１と異なる処理のステップ番号には符号Ｂを付ける。
Ｓ１１１において、初期セグメント集合生成部１２０は初期セグメント集合Ｆを初期化する。
【０１６５】
Ｓ１１２Ｂにおいて、初期セグメント集合生成部１２０は、訓練一時セグメント集合Ｕｓを初期化し、訓練セグメントＳｉそのものではなく、訓練セグメントＳｉを識別するインデックスｉを訓練一時セグメント集合Ｕｓに追加する。インデックスｉは変数ｉの値である。以降、訓練セグメントＳｉが必要な場合、インデックスｉと訓練時系列データから、訓練セグメントＳｉを復元することができることは明らかである。
【０１６６】
Ｓ１１３において、初期セグメント集合生成部１２０は、訓練セグメントＳｉと訓練セグメントＳｊとのセグメント間距離ｄを算出する。
【０１６７】
Ｓ１１４において、初期セグメント集合生成部１２０は、セグメント間距離ｄがε／２以下であるか判定する。
【０１６８】
Ｓ１１５Ｂにおいて、初期セグメント集合生成部１２０は、インデックスｊを訓練一時セグメント集合Ｕｓに追加する。インデックスｊは変数ｊの値である。
【０１６９】
Ｓ１１６Ｂにおいて、初期セグメント集合生成部１２０は、訓練一時セグメント集合Ｕｓを初期セグメント集合Ｆに追加する。
【０１７０】
Ｓ１１７において、初期セグメント集合生成部１２０は変数ｉの値を変数ｊの値に更新する。
【０１７１】
図８の処理によって、初期セグメントのインデックスから成る初期セグメント集合Ｆを生成することができる。初期セグメント集合Ｆはインデックスによって初期セグメントを識別する。
【０１７２】
Ｓ１２０において、初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメント毎に初期セグメントに含まれるインデックスによって識別されるそれぞれの訓練セグメントが表す座標の重心を算出する。
初期セグメント集合ソート部１３０は初期セグメント毎に重心の特徴量を算出する。初期セグメント毎の特徴量が算出された後、初期セグメント毎の重心はメモリから破棄する。
そして、初期セグメント集合ソート部１３０は、初期セグメント集合Ｆに含まれる初期セグメントを特徴量の昇順にソートする。
【０１７３】
図９に基づいて、標本セグメント集合生成処理（Ｓ１３０）について説明する。実施の形態１と異なる処理のステップ番号には符号Ｂを付ける。
Ｓ１３０−１において、標本セグメント集合生成部１４０は、標本セグメント集合Ｅを初期化する。
【０１７４】
Ｓ１３１Ｂ−１において、標本セグメント集合生成部１４０は、初期セグメントＦｉの重心を含む球Ｂの重心Ｃを決定する。球Ｂの半径はε／２である。
【０１７５】
Ｓ１３１Ｂ−２において、標本セグメント集合生成部１４０は、初期一時セグメント集合Ｕｆを初期化し、初期セグメント［Ｆｉ］を初期一時セグメント集合Ｕｆに追加する。
初期セグメント［Ｆｉ］は初期セグメントＦｉに含まれるインデックスによって識別される訓練セグメントを意味する。
【０１７６】
Ｓ１３１−３において、標本セグメント集合生成部１４０は、初期セグメントＦｉを初期セグメント集合Ｆから除去する。
【０１７７】
Ｓ１３１−４において、標本セグメント集合生成部１４０は、変数Ｓｋｉｐに−１を設定する。
【０１７８】
Ｓ１３１Ｂ−５において、標本セグメント集合生成部１４０は、初期一時セグメント集合Ｕｆの重心Ｃｔｒｕｅを算出する。Ｃｔｒｕｅは、Ｕｆに含まれる訓練セグメントをインデックスによって呼び出し、式＜１＞と同様に計算することによって算出することができる。
標本セグメント集合生成部１４０は、初期一時セグメント集合Ｕｆに含まれる訓練セグメント毎に、訓練セグメントの座標と重心Ｃｔｒｕｅの座標との距離σを算出する。
そして、標本セグメント集合生成部１４０は、距離σが最も小さい訓練セグメントのインデックスを標本セグメントの重心Ｃｐｓｅｕｄｏとして標本セグメント集合Ｅに追加する。
【０１７９】
訓練セグメントが標本セグメントになるため、Ｗ次元のベクトルではなく、訓練セグメントのインデックスを記憶すればよい。
また、重心Ｃｔｒｕｅと標本セグメントとの距離σを記憶しておくことにより、最終的な距離の誤差がε＋σ以内であることを示すことができる。
【０１８０】
図１０に基づいて、標本セグメント集合生成処理（Ｓ１３０）の第２ループ処理（Ｓ１３２）について説明する。実施の形態１と異なる処理のステップ番号には符号Ｂを付ける。
【０１８１】
Ｓ１３２−１において、標本セグメント集合生成部１４０は、初期セグメントＦｊの特徴量Ｄ（Ｆｊ）と重心Ｃの特徴量Ｄ（Ｃ）との特徴量差がε／（２＊√Ｗ）より大きいか判定する。
【０１８２】
Ｓ１３２Ｂ−２において、標本セグメント集合生成部１４０は、初期セグメントＦｊの重心Ｃｊを算出する。
そして、標本セグメント集合生成部１４０は、重心Ｃの座標と重心Ｃｊの座標との距離であるセグメント間距離ｄを算出する。
【０１８３】
Ｓ１３２−３において、標本セグメント集合生成部１４０は、セグメント間距離ｄがε／２以下であるか判定する。
【０１８４】
Ｓ１３２Ｂ−４において、標本セグメント集合生成部１４０は、初期セグメント［Ｆｊ］を初期一時セグメント集合Ｕｆに追加する。
【０１８５】
Ｓ１３２−５において、標本セグメント集合生成部１４０は、初期セグメント集合Ｆから初期セグメントＦｊを除去する。
【０１８６】
Ｓ１３２−６において、変数Ｓｋｉｐが負の値（−１）である場合、標本セグメント集合生成部１４０は変数Ｓｋｉｐに変数ｊの値を設定する。
【０１８７】
標本セグメントになる訓練セグメントのインデックスをＷ次元のセグメントの代わりに用いることにより、標本セグメントの記憶に必要な記憶容量を約１／Ｗに削減することができる。つまり、記憶効率を向上させることができる。
【０１８８】
＊＊＊補足説明＊＊＊
図１１から図１６に基づいて、標本セグメントに関する補足説明を行う。
図１１において、時系列データから抽出された長さＷのセグメントは、Ｗ次元空間上の座標に対応する。図中のＷは２である。
【０１８９】
図１２において、Ｗ次元空間上の座標の平均値Ａを用いて、その座標がｘ１＋Ｘ２＋・・・＋ＸＷ＝Ａ＊Ｗで表される基準平面に位置するということが言える。Ｗ＝２の場合、基準平面は直線に相当する。
【０１９０】
図１３において、座標ｐの基準平面とｘ１軸との交点ｐ’の距離はＷ＊Ａである。原点Ｏから座標ｐの基準平面までの距離はＡ＊√Ｗである。すなわち、Ａが大きい程、原点Ｏから遠い平面上に座標があることを意味する。
座標ｐと座標ｑとの距離（ｄｉｓｔ（ｐ，ｑ））は、座標ｐの基準平面と座標ｑの基準平面との距離以上になるため、ｄｉｓｔ（ｐ，ｑ）≧｜Ｍｅａｎ（ｐ）＊√Ｗ−Ｍｅａｎ（ｑ）＊√Ｗ｜が成り立つ。
よって、ｄｉｓｔ（ｐ，ｑ）≦ε／２となるためには、｜Ｍｅａｎ（ｐ）＊√Ｗ−Ｍｅａｎ（ｑ）＊√Ｗ｜≦ε／２、すなわち、｜Ｍｅａｎ（ｐ）−Ｍｅａｎ（ｑ）｜≦ε／（２＊√Ｗ）を満たす必要がある。
【０１９１】
図１４において、初期セグメント集合は半径がε／２である球に含まれる。初期セグメント集合は先頭の訓練セグメントからの距離がε／２以下である訓練セグメントの集合である。
【０１９２】
図１５において、重心Ｃを中心として半径がε／２である球に含まれる初期セグメント集合の重心を集めると、集められた訓練セグメントは、全てＣを中心として半径がεである球に含まれる。
よって、あるテストセグメントと重心Ｃとの距離がｄである場合、そのテストセグメントと重心Ｃを中心とする球内の訓練セグメントとの距離はｄ±εの範囲に含まれる。
図中の（１）〜（６）はそれぞれ重心であり、平均値がＣの平均値に近い重心（１）→（２）→（３）の順に距離を調べる。その後、Ｃとの平均値の差がε／２である重心（４）までが標本セグメントとしてマージする対象の候補になる。しかし、Ｃとの平均値の差がε／２より大きい重心（５）はマージの対象にならない。そして、重心（５）で閾値を超えたため、（６）以降の重心は調べる必要がない。
【０１９３】
図１６において、ＦｅａｔＭは座標系の原点から基準平面までの距離に対応する。ＦｅａｔＲは垂線の足（Ａ，・・・，Ａ）から実際の重心までのずれ幅に対応する。垂線の足は原点から基準平面に下した垂線の端点である。
ｄｉｓｔ（ｐ，ｑ）は図中の（１）の距離よりも長い。これは、式＜１４＞の前半部分に相当する。また、ｄｉｓｔ（ｐ，ｑ）は図中の（２）の距離よりも短い。これは、式＜１４＞の後半部分に相当する。
【０１９４】
各実施の形態は、好ましい形態の例示であり、本発明の技術的範囲を制限することを意図するものではない。各実施の形態は、部分的に実施してもよいし、他の実施の形態と組み合わせて実施してもよい。
フローチャート等を用いて説明した処理手順は、時系列データ検索装置、時系列データ検索方法および時系列データ検索プログラムの処理手順の一例である。
【符号の説明】
【０１９５】
１００  時系列データ検索装置、１１０  時系列データ取得部、１１１  パラメータ取得部、１２０  初期セグメント集合生成部、１３０  初期セグメント集合ソート部、１４０  標本セグメント集合生成部、１５０  標本セグメント集合ソート部、１６０  検索結果距離算出部、１６１  検索結果距離出力部、１９０  データ記憶部、９０１  プロセッサ、９０２  補助記憶装置、９０３  メモリ、９０４  通信装置、９０４１  レシーバ、９０４２  トランスミッタ、９０５  入力インタフェース、９０６  ディスプレイインタフェース、９０７  入力装置、９０８  ディスプレイ、９１０  信号線、９１１  ケーブル、９１２  ケーブル、Ｓ  訓練時系列データ、Ｔ  テスト時系列データ、Ｗ  スライド幅、ε  近似誤差、Ｆ  初期セグメント集合、Ｅ  標本セグメント集合、Ｚ  検索結果距離。
【図１】
2016117086.tif 000015
【図２】
2016117086.tif 000016
【図３】
2016117086.tif 000017
【図４】
2016117086.tif 000018
【図５】
2016117086.tif 000019
【図６】
2016117086.tif 000020
【図７】
2016117086.tif 000021
【図８】
2016117086.tif 000022
【図９】
2016117086.tif 000023
【図１０】
2016117086.tif 000024
【図１１】
2016117086.tif 000025
【図１２】
2016117086.tif 000026
【図１３】
2016117086.tif 000027
【図１４】
2016117086.tif 000028
【図１５】
2016117086.tif 000029
【図１６】
2016117086.tif 000030
【手続補正書】
【提出日】平成28年10月12日(2016.10.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
時系列に並んだ複数のデータ値から成る訓練時系列データからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントから成る訓練一時セグメント集合を複数生成し、訓練一時セグメント集合のそれぞれの訓練セグメントに含まれるＷ個のデータ値がＷ次元の座標系の座標値として扱われた場合の訓練一時セグメント集合の重心の座標値、を表すＷ個のデータ値を初期セグメントとして訓練一時セグメント集合毎に算出し、訓練一時セグメント集合毎の初期セグメントから成る初期セグメント集合を生成する初期セグメント集合生成部と、
前記初期セグメント集合を、半径の条件である条件半径を有するＷ次元の図形毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される初期一時セグメント集合に分割し、初期一時セグメント集合の図形の重心の座標値を表すＷ個のデータ値から成る標本セグメントを初期一時セグメント集合毎に含む標本セグメント集合を生成する標本セグメント集合生成部と、
前記初期セグメント集合に含まれる初期セグメント毎に初期セグメントに含まれるデータ値を用いて初期セグメントの特徴量を算出し、前記初期セグメント集合に含まれる初期セグメントを特徴量の順にソートする初期セグメント集合ソート部とを備え、
第１の初期一時セグメント集合は、ソート後の前記初期セグメント集合のうちの先頭の初期セグメントが表す座標値を含む図形である第１の図形に含まれる１つ以上の初期セグメントから成り、
前記先頭の初期セグメントを除いて前記第１の初期一時セグメント集合に含まれる初期セグメントは、前記先頭の初期セグメントの次の初期セグメントから順に、初期セグメントが前記第１の図形に含まれるか判定する初期セグメント判定によって判定される
時系列データ検索装置。
【請求項２】
前記次の初期セグメントから順に選択された初期セグメントの特徴量と、前記第１の図形の重心である第１の重心の座標値から算出される前記第１の重心の特徴量との差である特徴量差が特徴量差の条件である特徴量差範囲に含まれる場合、選択された初期セグメントに対する前記初期セグメント判定が行われて、
前記特徴量差が前記特徴量差範囲に含まれない場合、選択された初期セグメント以降の初期セグメントに対する前記初期セグメント判定が行われない
請求項１に記載の時系列データ検索装置。
【請求項３】
選択された初期セグメントに対する前記初期セグメント判定において、選択された初期セグメントが表す座標値の座標と前記第１の重心の座標との距離が前記条件半径以下である場合に、選択された初期セグメントが前記第１の図形に含まれると判定される
請求項２に記載の時系列データ検索装置。
【請求項４】
前記初期セグメントの特徴量は前記初期セグメントに含まれるデータ値の平均値であり、
前記第１の重心の特徴量は前記第１の図形の重心の座標値がＷ個のデータ値として扱われた場合のデータ値の平均値である
請求項３に記載の時系列データ検索装置。
【請求項５】
前記初期セグメントの特徴量は前記初期セグメントが表す座標値の座標と基準点との距離であり、
前記第１の重心の特徴量は前記第１の重心と前記基準点との距離である
請求項３に記載の時系列データ検索装置。
【請求項６】
前記初期セグメントの特徴量は、前記初期セグメントに含まれるデータ値を平均した全体平均値と、前記初期セグメントから抽出される初期部分セグメントに含まれるデータ値を平均した部分平均値とであり、
前記第１の重心の特徴量は前記第１の重心の座標値がＷ個のデータ値として扱われた場合のデータ値を平均した重心平均値であり、
前記初期セグメント集合に含まれる初期セグメントが部分平均値の順にソートされて、
前記特徴量差が前記全体平均値と前記重心平均値との差である
請求項３に記載の時系列データ検索装置。
【請求項７】
前記初期セグメントの特徴量は前記初期セグメントに連続して含まれる２つのデータ値毎のデータ値の差から算出される前記初期セグメントの複雑度であり、
前記第１の重心の特徴量は前記第１の重心の座標値がＷ個のデータ値から成る第１の重心セグメントとして扱われた場合の前記第１の重心セグメントに連続して含まれる２つのデータ値毎のデータ値の差から算出される前記第１の重心セグメントの複雑度である
請求項３に記載の時系列データ検索装置。
【請求項８】
前記初期セグメントの特徴量は、前記初期セグメントが表す座標値の座標と前記初期セグメント用の基準平面との最短距離である初期最短距離と、前記初期セグメントの座標軸毎の座標値と前記初期セグメント用の基準平面の座標軸毎の座標値との差から算出される初期指標値とであり、
前記第１の重心の特徴量は、前記第１の重心の座標と前記第１の重心用の基準平面との重心最短距離である重心最短距離と、前記第１の重心の座標軸毎の座標値と前記第１の重心用の基準平面の座標軸毎の座標値との差から算出される重心指標値であり、
前記初期セグメント集合に含まれる初期セグメントが初期最短距離の順にソートされて、
前記特徴量差が、前記初期最短距離と前記重心最短距離との差と、前記初期指標値と前記重心指標値との差の合計である
請求項３に記載の時系列データ検索装置。
【請求項９】
正のデータ値と負のデータ値とのいずれかだけが前記訓練時系列データに含まれる場合と、正のデータ値と負のデータ値との両方が前記訓練時系列データに含まれる場合で、前記初期セグメントの特徴量の種類が異なる
請求項３に記載の時系列データ検索装置。
【請求項１０】
訓練セグメント毎の指標値から算出される分散値が分散値の条件である分散値範囲に含まれる場合と、前記分散値が前記分散値範囲に含まれない場合で、前記初期セグメントの特徴量の種類が異なり、
訓練セグメントの指標値が、前記訓練セグメントの座標軸毎の座標値と前記訓練セグメント用の基準平面の座標軸毎の座標値との座標軸毎の差から算出される値と、前記訓練セグメントの座標値を表すベクトルの偏角の大きさを示す値とのいずれかである
請求項３に記載の時系列データ検索装置。
【請求項１１】
訓練セグメント毎の指標値のうちの最大値が最大値の条件である最大値範囲に含まれる場合と、前記最大値が前記最大値範囲に含まれない場合で、前記初期セグメントの特徴量の種類が異なり、
訓練セグメントの指標値が、前記訓練セグメントの座標軸毎の座標値と前記訓練セグメント用の基準平面の座標軸毎の座標値との座標軸毎の差から算出される値と、前記訓練セグメントの座標値を表すベクトルの偏角の大きさを示す値とのいずれかである
請求項３に記載の時系列データ検索装置。
【請求項１２】
時系列に並んだ複数のデータ値から成る訓練時系列データからＷ個のデータ値を時系列の順に抽出して得られる訓練セグメントを複数生成し、時系列の順に並んだ１つ以上の訓練セグメントから成る訓練一時セグメント集合を複数生成し、訓練一時セグメント集合のそれぞれの訓練セグメントに含まれるＷ個のデータ値がＷ次元の座標系の座標値として扱われた場合の訓練一時セグメント集合の重心の座標値、を表すＷ個のデータ値を初期セグメントとして訓練一時セグメント集合毎に算出し、訓練一時セグメント集合毎の初期セグメントから成る初期セグメント集合を生成する初期セグメント集合生成処理と、
前記初期セグメント集合を、半径の条件である条件半径を有するＷ次元の図形毎に図形に含まれる座標値を表すデータ値から成る初期セグメントで構成される初期一時セグメント集合に分割し、初期一時セグメント集合の図形の重心の座標値を表すＷ個のデータ値から成る標本セグメントを初期一時セグメント集合毎に含む標本セグメント集合を生成する標本セグメント集合生成処理と、
前記初期セグメント集合に含まれる初期セグメント毎に初期セグメントに含まれるデータ値を用いて初期セグメントの特徴量を算出し、前記初期セグメント集合に含まれる初期セグメントを特徴量の順にソートする初期セグメント集合ソート処理と
をコンピュータに実行させる時系列データ検索プログラムであって、
第１の初期一時セグメント集合は、ソート後の前記初期セグメント集合のうちの先頭の初期セグメントが表す座標値を含む図形である第１の図形に含まれる１つ以上の初期セグメントから成り、
前記先頭の初期セグメントを除いて前記第１の初期一時セグメント集合に含まれる初期セグメントは、前記先頭の初期セグメントの次の初期セグメントから順に、初期セグメントが前記第１の図形に含まれるか判定する初期セグメント判定によって判定される
時系列データ検索プログラム。
【国際調査報告】
2016117086.tif 000031
2016117086.tif 000032
2016117086.tif 000033
2016117086.tif 000034