(57)【特許請求の範囲】
【請求項１】
比較される２つの時系列データの各々について、時間経過に対する値の増加若しくは減少の傾向が変化する時刻を変化点として検出する検出部と、
前記２つの時系列データの各々で個別に設定されている、複数の同一期間幅を含む所定の期間内において、前記２つの時系列データを、前記複数の同一期間幅それぞれについて前記所定の期間内の先頭の時刻からの同一順序同士で順次対比したときに、同一順序の対応する時刻における前記傾向の変化が一致する一致数を、前記２つの時系列データに対する前記変化点の検出時刻から計数する計数部と、
前記一致数に基づいて、前記２つの時系列データの間の類似度を演算する演算部と、
を備えることを特徴とするデータ処理装置。
【請求項２】
前記検出部は、前記２つの時系列データそれぞれに含まれている各時刻の値についての、該値の時刻から所定の時間差を持つ後の時刻の値に対しての大小関係を、各時刻における前記傾向を表す情報として、前記時間差ごとに検出すると共に、検出した前記大小関係を時刻順に並べた場合に、時間経過に対して前記大小関係が変化する時刻を、前記変化点として、前記時間差ごとに検出し、
前記計数部は、前記時間差ごとに前記一致数を計数し、
前記演算部は、前記時間差ごとの前記一致数に基づいて、前記類似度を演算する、
ことを特徴とする請求項１記載のデータ処理装置。
【請求項３】
前記２つの時系列データについて設定されている前記所定の期間を時間軸上でずらし、該所定の期間がずらされた際に変化する一致数の変化量を求める差分処理部、をさらに備え、
前記計数部は、前記所定の時間がずらされる前に前記計数部が計数した一致数と前記差分処理部により求められた前記一致数の変化量とに基づいて、前記所定の期間がずらされた後の一致数を求め、
前記演算部は、前記所定の期間がずらされた後の一致数にさらに基づいて、前記類似度を演算する、
ことを特徴とする請求項２記載のデータ処理装置。
【請求項４】
前記２つの時系列データの双方について前記所定の期間が時間軸上において同一の向きに同一の時間ずらされる場合において、前記差分処理部は、前記変化点のうちから、前記所定の期間を前記時間軸上で１時刻分ずらした際に前記所定の期間に含まれることとなる、または前記所定の期間から外れることとなる変化点を選択し、該選択された変化点の前記大小関係を反転させた場合に生じる、該選択された変化点についての前記傾向の変化が一致する数の変化の変化量を、前記１時刻分ずらした際の前記一致数の変化量として求める、
ことを特徴とする請求項３記載のデータ処理装置。
【請求項５】
前記差分処理部は、前記２つの時系列データと前記時間差ごとの前記変化点を示す変化点データとに基づいて、前記所定の期間と前記変化点との時間軸上での位置関係をテーブルで管理する、
ことを特徴とする請求項３または４記載のデータ処理装置。
【請求項６】
前記２つの時系列データのうち、一方の時系列データについて前記所定の期間がずらされ、他方の時系列データについて前記所定の期間がずらされない場合には、前記差分処理部は、
前記他方の時系列データについて、前記所定の期間の後に続く最初の時刻である前端と、前記所定の期間内における最初の時刻である後端との各々が前記変化点であるどうかを前記時間差ごとに判定し、
前記前端と前記後端との各々において前記変化点ではないと判定された時刻について、該時刻を新たに前記変化点に設定すると共に、新たに設定した前記変化点である時刻について検出していた前記大小関係を反転する、
処理を行うと共に、
前記処理後の前記他方の時系列データにおける前記変化点である時刻についての前記大小関係が、ずらされる前の前記一方の時系列データにおける前記対応する時刻についての前記大小関係と一致するか否かを、前記時間差ごとに、前記前端である前記変化点と、前記後端である変化点と、前記所定の期間内の時刻のうち前記後端ではない変化点とについて判定し、
前記前端である前記変化点については、前記大小関係が一致すると判定した場合には重み「０」を該変化点に与え、前記大小関係が一致しないと判定した場合には重み「＋１」を該変化点に与え、
前記後端である前記変化点については、前記大小関係が一致すると判定した場合には重み「−１」を該変化点に与え、前記大小関係が一致しないと判定した場合には重み「０」を該変化点に与え、
前記所定の期間内の時刻のうち前記後端ではない変化点については、前記大小関係が一致すると判定した場合には重み「−１」を該変化点に与え、前記大小関係が一致しないと判定した場合には重み「＋１」を該変化点に与え、
各変化点に与えられた重みを合計した値を、前記一方の時系列データについて前記所定の期間を前記時間軸上で１時刻分ずらした際の前記一致数の変化量として求める、
ことを特徴とする請求項３記載のデータ処理装置。
【請求項７】
コンピュータが、
比較される２つの時系列データの各々について、時間経過に対する値の増加若しくは減少の傾向が変化する時刻を変化点として検出し、
前記２つの時系列データの各々で個別に設定されている、複数の同一期間幅を含む所定の期間内において、前記２つの時系列データを、前記複数の同一期間幅それぞれについて前記所定の期間内の先頭の時刻からの同一順序同士で順次対比したときに、同一順序の対応する時刻における前記傾向の変化が一致する一致数を、前記２つの時系列データに対する前記変化点の検出時刻から計数し、
前記一致数に基づいて、前記２つの時系列データの間の類似度を演算する、
ことを特徴とするデータ処理方法。
【請求項８】
コンピュータに、
比較される２つの時系列データの各々について、時間経過に対する値の増加若しくは減少の傾向が変化する時刻を変化点として検出し、
前記２つの時系列データの各々で個別に設定されている、複数の同一期間幅を含む所定の期間内において、前記２つの時系列データを、前記複数の同一期間幅それぞれについて前記所定の期間内の先頭の時刻からの同一順序同士で順次対比したときに、同一順序の対応する時刻における前記傾向の変化が一致する一致数を、前記２つの時系列データに対する前記変化点の検出時刻から計数し、
前記一致数に基づいて、前記２つの時系列データの間の類似度を演算する、
処理を実行させることを特徴とするデータ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法およびデータ処理プログラムに関する。
【背景技術】
【０００２】
複数の時系列データのうち２つの時系列データを比較することで、該２つの時系列データの類似度の演算を行う技術が用いられている。類似度の演算を行う手法の１つにケンドールの順位相関係数を用いた演算がある。
【０００３】
関連する技術として、複合ソート法による高速な全ペア類似度検索という技術が提案されている。この技術では、比較対象のデータ期間のそれぞれについて、値の大小関係を文字列として記憶する（例えば、非特許文献１を参照）。
【０００４】
また、携帯機が、認証要求信号の測定部の受信強度を測定し、受信強度の大小関係の変化が所定のパターンと一致するか否かに基づいて、認証要求信号が正規の信号であるかを判定する技術が提案されている（例えば、特許文献１を参照）。
【０００５】
また、端子電圧と所定電圧との大小関係を時系列的にサンプリングし、サンプリングした大小関係と規則的な変化に基づいて、通電制御を行う技術が提案されている（例えば、特許文献２を参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】津田宏治、「複合ソート法による高速な全ペア類似度検索」、ERATO湊離散構造処理系プロジェクト、2010年度科学技術振興機構ERATO湊離散構造処理系プロジェクト講究録. p.490-495.
【特許文献】
【０００７】
【特許文献１】特開２００５−２６９７１９号公報
【特許文献２】特開２０１４−１３９７５２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
例えば、比較対象の時系列データのデータ期間のそれぞれについて、値の大小関係を文字列として記憶する方式では、値の大小関係の情報量が多くなる。このため、時系列データの類似度の演算を行う際に使用される情報量が多くなり、演算時間が長くなる。
【０００９】
１つの側面として、本発明は、時系列データ同士を比較する際の演算時間を短くすることを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、データ処理装置は、比較される２つの時系列データの各々について、時間経過に対する値の増加若しくは減少の傾向が変化する時刻を変化点として検出する検出部と、前記２つの時系列データの各々で個別に設定されている、複数の同一期間幅を含む所定の期間内において、前記２つの時系列データを、前記複数の同一期間幅それぞれについて前記所定の期間内の先頭の時刻からの同一順序同士で順次対比したときに、同一順序の対応する時刻における前記傾向の変化が一致する一致数を、前記２つの時系列データに対する前記変化点の検出時刻から計数する計数部と、前記一致数に基づいて、前記２つの時系列データの間の類似度を演算する演算部と、を含む。
【発明の効果】
【００１１】
１つの側面によれば、時系列データ同士を比較する際の演算時間を短くすることができる。
【図面の簡単な説明】
【００１２】
【図１】ケンドールの順位相関係数を用いた演算の一例を示す図である。
【図２】データ処理装置の一例を示す機能ブロック図である。
【図３】データ処理装置のハードウェア構成の一例を示す図である。
【図４】類似度の演算の手法の一例を示す図である。
【図５】変化点検出の一例を説明する図（その１）である。
【図６】変化点検出の一例を説明する図（その２）である。
【図７】ウィンドウをずらさない場合の類似度の演算の一例を説明する図（その１）である。
【図８】ウィンドウをずらさない場合の類似度の演算の一例を説明する図（その２）である。
【図９】双方のウィンドウをずらす場合の類似度の演算の一例を示す図（その１）である。
【図１０】双方のウィンドウをずらす場合の類似度の演算の一例を示す図（その２）である。
【図１１】双方のウィンドウをずらす場合の類似度の演算の一例を示す図（その３）である。
【図１２】双方のウィンドウをずらす場合の類似度の演算の一例を示す図（その４）である。
【図１３】双方のウィンドウをずらす場合の類似度の演算の一例を示す図（その５）である。
【図１４】片方のウィンドウをずらす場合の類似度の演算の一例を示す図（その１）である。
【図１５】片方のウィンドウをずらす場合の類似度の演算の一例を示す図（その２）である。
【図１６】片方のウィンドウをずらす場合の類似度の演算の一例を示す図（その３）である。
【図１７】片方のウィンドウをずらす場合の類似度の演算の一例を示す図（その４）である。
【図１８】片方のウィンドウをずらす場合の類似度の演算の一例を示す図（その５）である。
【図１９】片方のウィンドウをずらす場合の類似度の演算の一例を示す図（その６）である。
【図２０】片方のウィンドウをずらす場合の類似度の演算の一例を示す図（その７）である。
【図２１】時系列データの類似度の演算の３つの具体例を示す図である。
【図２２】具体例１を説明する図（その１）である。
【図２３】具体例１を説明する図（その２）である。
【図２４】具体例１を説明する図（その３）である。
【図２５】具体例１を説明する図（その４）である。
【図２６】具体例１を説明する図（その５）である。
【図２７】具体例１を説明する図（その６）である。
【図２８】具体例１を説明する図（その７）である。
【図２９】具体例１を説明する図（その８）である。
【図３０】具体例１を説明する図（その９）である。
【図３１】具体例１を説明する図（その１０）である。
【図３２】具体例１を説明する図（その１１）である。
【図３３】具体例１を説明する図（その１２）である。
【図３４】具体例１を説明する図（その１３）である。
【図３５】具体例１を説明する図（その１４）である。
【図３６】具体例１を説明する図（その１５）である。
【図３７】具体例１を説明する図（その１６）である。
【図３８】具体例１を説明する図（その１７）である。
【図３９】具体例１を説明する図（その１８）である。
【図４０】具体例１を説明する図（その１９）である。
【図４１】具体例１を説明する図（その２１）である。
【図４２】具体例１を説明する図（その２２）である。
【図４３】具体例１を説明する図（その２３）である。
【図４４】具体例１を説明する図（その２４）である。
【図４５】具体例１を説明する図（その２５）である。
【図４６】具体例１を説明する図（その２６）である。
【図４７】具体例１を説明する図（その２７）である。
【図４８】具体例１を説明する図（その２８）である。
【図４９】具体例１を説明する図（その２９）である。
【図５０】具体例１を説明する図（その３０）である。
【図５１】具体例１を説明する図（その３１）である。
【図５２】具体例２を説明する図（その１）である。
【図５３】具体例２を説明する図（その２）である。
【図５４】具体例２を説明する図（その３）である。
【図５５】具体例２を説明する図（その４）である。
【図５６】具体例２を説明する図（その５）である。
【図５７】具体例２を説明する図（その６）である。
【図５８】具体例２を説明する図（その７）である。
【図５９】具体例２を説明する図（その８）である。
【図６０】具体例２を説明する図（その９）である。
【図６１】具体例２を説明する図（その１０）である。
【図６２】具体例２を説明する図（その１１）である。
【図６３】具体例２を説明する図（その１２）である。
【図６４】具体例２を説明する図（その１３）である。
【図６５】具体例２を説明する図（その１４）である。
【図６６】具体例２を説明する図（その１５）である。
【図６７】具体例３を説明する図（その１）である。
【図６８】具体例３を説明する図（その２）である。
【図６９】具体例３を説明する図（その３）である。
【図７０】具体例３を説明する図（その４）である。
【図７１】具体例３を説明する図（その５）である。
【図７２】具体例３を説明する図（その６）である。
【図７３】具体例３を説明する図（その７）である。
【図７４】具体例３を説明する図（その８）である。
【図７５】具体例３を説明する図（その９）である。
【図７６】具体例３を説明する図（その１０）である。
【図７７】具体例３を説明する図（その１１）である。
【図７８】具体例３を説明する図（その１２）である。
【図７９】具体例３を説明する図（その１３）である。
【図８０】具体例３を説明する図（その１４）である。
【図８１】具体例３を説明する図（その１５）である。
【図８２】具体例３を説明する図（その１６）である。
【図８３】具体例３を説明する図（その１７）である。
【図８４】具体例３を説明する図（その１８）である。
【図８５】他の値を用いた一致数の例（その１）である。
【図８６】他の値を用いた一致数の例（その２）である。
【図８７】他の値を用いた一致数の例（その３）である。
【図８８】他の値を用いた一致数の例（その４）である。
【図８９】他の値を用いた一致数の例（その５）である。
【図９０】他の値を用いた一致数の例（その６）である。
【図９１】実施形態の処理の流れの一例を示すフローチャート（その１）である。
【図９２】実施形態の処理の流れの一例を示すフローチャート（その２）である。
【図９３】実施形態の処理の流れの一例を示すフローチャート（その３）である。
【図９４】実施形態の処理の流れの一例を示すフローチャート（その４）である。
【図９５】実施形態の処理の流れの一例を示すフローチャート（その５）である。
【図９６】３種類の時系列データの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して、実施形態について説明する。実施形態では、ケンドールの順位相関係数を用いて、時系列データ同士の類似度が演算されるものとする。時系列データは、各時刻における値を表すデータである。図１の例では、比較対象の時系列データは、データ１とデータ２とであるものとする。
【００１４】
図１の例の場合、データ１およびデータ２のデータサイズは「４」であるものとする。以下、データサイズを項目数と称することもある。データサイズ（項目数）は、時系列データの各時刻における値の数である。
【００１５】
ケンドールの順位相関係数を用いて類似度の演算が行われる場合、比較対象の２つの時系列データの異なる時刻間の値の大小関係の一致数に基づいて、上記の類似度の演算が行われる。
【００１６】
例えば、時刻（図１では項目と表記）「Ｔ３」におけるデータ１の値は「７．２」であり、時刻「Ｔ４」における値より大きい。時刻「Ｔ３」におけるデータ２の値は「２．２」であり、時刻「Ｔ４」における値より大きい。この場合、データ１とデータ２との間の、時刻「Ｔ３」と時刻「Ｔ４」との大小関係は一致する。
【００１７】
ケンドールの順位相関係数を用いた類似度ｔは以下の式（Ａ）で表される。
ｔ＝（４×Ｐ／ｎ×（ｎ−１））−１・・・式（Ａ）
【００１８】
以下、類似度を相関値と称することもある。式（Ａ）のうち、Ｐはデータ１とデータ２との大小関係が一致する数（一致数）である。ｎは項目数である。図１の例の場合、項目数ｎは「４」である。
【００１９】
図１の例の場合、データ１とデータ２との大小関係が一致する数は「４」であるため、「Ｐ＝４」である。従って、項目数ｎおよび一致数Ｐを式（Ａ）に当て嵌めると、類似度ｔは「ｔ＝（４×４×／（４×（４−１））＝０．３３」となる。
【００２０】
＜データ処理装置の一例＞
図２は、実施形態のデータ処理装置１の一例を示す。データ処理装置１は、記憶部１１と検出部１２と計数部１３と演算部１４と差分処理部１５とを含む。データ処理装置１は、コンピュータの一例である。
【００２１】
記憶部１１は、各種の情報を記憶する。例えば、記憶部１１は、複数の時系列データを記憶する。複数の時系列データは、例えば、それぞれ異なるセンサが計測したデータであってもよいし、異なる商品の売り上げの経時的な変化を示すデータ等であってもよい。
【００２２】
検出部１２は、記憶部１１に記憶された複数の時系列データのうち、比較対象の２つの時系列データにおいて、時間差ごとに、時刻間の大小関係が変化する変化点を検出する。計数部１３は、検出部１２が検出した変化点に基づいて、２つの時系列データの大小関係が一致する数を一致数として計数する。
【００２３】
演算部１４は、計数部１３が計数した一致数Ｐおよび項目数ｎを上述した式（Ａ）に当て嵌めて、２つの時系列データの類似度ｔを演算する。差分処理部１５は、２つの時系列データのうち比較対象の期間をずらす処理や、該期間がずらされた場合における各種の処理を行う。
【００２４】
＜データ処理装置のハードウェア構成の一例＞
次に、図３の例を参照して、データ処理装置１のハードウェア構成の一例を説明する。図３の例に示すように、バス１００に対して、プロセッサ１１１とRandom Access Memory(RAM)１１２とRead Only Memory(ROM)１１３と補助記憶装置１１４と媒体接続部１１５と通信インタフェース１１６とが接続されている。
【００２５】
プロセッサ１１１は任意の処理回路である。プロセッサ１１１はＲＡＭ１１２に展開されたプログラムを実行する。実行されるプログラムとしては、実施形態の処理を行うデータ処理プログラムが適用されてもよい。ＲＯＭ１１３はＲＡＭ１１２に展開されるプログラムを記憶する不揮発性の記憶装置である。
【００２６】
補助記憶装置１１４は、種々の情報を記憶する記憶装置であり、例えばハードディスクドライブや半導体メモリ等を補助記憶装置１１４に適用してもよい。媒体接続部１１５は、可搬型記録媒体１１９と接続可能に設けられている。
【００２７】
可搬型記録媒体１１９としては、可搬型のメモリや光学式ディスク（例えば、Compact Disc(CD)やDigital Versatile Disc(DVD)等）を適用してもよい。この可搬型記録媒体１１９に実施形態の処理を行うプログラムが記録されていてもよい。
【００２８】
データ処理装置１のうち、記憶部１１は、ＲＡＭ１１２や補助記憶装置１１４等により実現されてもよい。検出部１２と計数部１３と演算部１４と差分処理部１５とは与えられたデータ処理プログラムをプロセッサ１１１が実行することにより実現されてもよい。
【００２９】
ＲＡＭ１１２、ＲＯＭ１１３、補助記憶装置１１４および可搬型記録媒体１１９は、何れもコンピュータ読み取り可能な有形の記憶媒体の一例である。これらの有形な記憶媒体は、信号搬送波のような一時的な媒体ではない。
【００３０】
＜類似度の演算の手法の一例＞
実施形態では、演算部１４は、２つの時系列データの類似度を複数種類の手法で演算する。図４は、以下の（１）〜（３）の３種類の類似度の演算の手法の例を示す。
【００３１】
（１）は、４つの時系列データの同じ期間の類似度の演算を行う例を示す。図４の例では、「４つのデータの比較」として示される。この場合、演算部１４は、４つの時系列データのうち、２つの時系列データのペアについて、各ペアの類似度の演算を行う。比較対象となる時系列データの数は４つには限定されない。
【００３２】
（２）は、２つの時系列データの双方について、比較対象の期間がずらされながら、２つの時系列データの類似度の演算が行われる例を示す。
を行う例を示す。
【００３３】
（３）は、２つの時系列データのうち一方が固定され、比較対象の片方の期間がずらされながら、２つの時系列データの類似度の演算が行われる例を示す。
【００３４】
（１）乃至（３）において、２つの時系列データの全ての時刻が、一致数の計数の対象であってもよいし、２つの時系列データのうち一部の期間が、一致数の計数の対象であってもよい。
【００３５】
以下、一致数の計数の対象となる期間をウィンドウと称する。（２）において、差分処理部１５は、２つの時系列データの双方のウィンドウを１回ずらすごとに、一致数の変化量を求める。
【００３６】
差分処理部１５がウィンドウをずらす場合、該ウィンドウは、時系列データの１つ後ろの時刻にずらされる（移動される）。ウィンドウは、比較対象の時間帯の最初の時刻を始点にセットされ、１つ後ろの時刻にずらされる。（３）の場合も同様である。
【００３７】
＜変化点の検出の一例＞
図５は、時系列データの変化点検出の一例を示す。図５の例では、時刻「１」から「１０」までの各値がデータ１の時系列データとして示される。時系列データは、記憶部１１に記憶される。
【００３８】
検出部１２は、時間差ごとに、時系列データの各時刻について前後の時刻の値の大小関係を比較し、大小関係が変化する変化点（変化する時刻）を検出する。実施形態では、時間差に応じて、次の時刻の値から見て、前の時刻の値が小さい場合、大小関係は「−」とする。
【００３９】
また、実施形態では、時間差に応じて、次の時刻の値から見て、前の時刻の値が大きい場合、大小関係は「＋」とする。例えば、図５の例において、時間差が「２」の場合、時刻「１」の値と時刻「３」の値とでは、時刻「３」の値が大きい。よって、時間差「２」における、時刻「１」の大小関係は「−」となる。
【００４０】
一方、時間差が「２」の場合、時刻「３」の値と時刻「５」の値とでは、時刻「５」の値が小さい。よって、時間差「２」における、時刻「３」の大小関係は「＋」となる。従って、図５の例の場合、時間差が「２」の場合、時刻「３」において、大小関係が変化する。
【００４１】
検出部１２は、時間差ごとに、前後の時刻の大小関係が変化する変化点を検出し、検出された変化点を示すデータを変化点データとして記憶部１１に記憶する。検出部１２は、検出された変化点を示す情報が、時刻と大小関係とで表現された形式の変化点データを記憶部１１に記憶する。
【００４２】
例えば、図５の例の場合、検出部１２は、時間差が「２」、時刻「３」において、大小関係が「＋」に変化することを検出する。検出部１２は、時間差が「２」に対応する変化点データを「３＋」の形式で記憶部１１に記憶する。
【００４３】
図５の例において、２次元のマトリクス（２次元表と称されることもある）が示される。図５以降のマトリクスでは、時系列データの各時刻における値はＸ方向およびＹ方向に展開される。該マトリクスの要素は、各時間差における時系列データの各時刻の大小関係を表す。
【００４４】
マトリクスにおいて、実線は大小関係が「＋」であることを示し、点線は大小関係が「−」であることを示す。
【００４５】
図５以降のマトリクスは、大小関係を視覚化したイメージである。該マトリクスでは、時間差ごとの各時刻における大小関係が記述される。従って、大小関係の情報量が多くなり、計数部１３が、大小関係の一致数をカウントする場合の処理時間が長くなる。
【００４６】
従って、実施形態では、計数部１３は、図５以降に例示されるマトリクスを使用することなく、大小関係の一致数をカウントする。実施形態では、計数部１３は、変化点データに基づいて、大小関係の一致数をカウントする。
【００４７】
図５以降のマトリクスにおいて、斜め方向の各要素は、１つの時間差についての大小関係を示す。斜め方向の各要素の始点がＸ方向にずれるごとに、時間差が大きくなる。図５の例の場合、Ｘ方向の時刻「３」、Ｙ方向の時刻「１」を始点とした斜め方向の各要素が時間差「２」における大小関係を表す（図５における一点鎖線）。
【００４８】
図５のマトリクスの例を参照すると、時間差が「２」の場合、Ｙ方向における時刻「１」、「３」および「７」において、大小関係が変化する。検出部１２は、時系列データを検索して、時間差「２」における変化点データを検出する。
【００４９】
図６は、時間差「２」の場合における変化点の検出の一例を示す。図６の例では、説明のため、マトリクスを用いた変化点の検出の例を示すが、検出部１２は、マトリクスを用いずに、変化点の検出を行う。
【００５０】
時間差「２」の最初の変化点（図６の例において初期値）は「１−」である。検出部１２は、最初の変化点から次の変化点までの間の区間（ブロック）が分離されているか否かを判定する。この区間は、図６の例において、Ｘ方向の時刻「３」から「５」、およびＹ方向の時刻「１」から「３」である。
【００５１】
区間が分離されているか否かは、該区間のＸ方向における値の範囲とＹ方向における値の範囲との間で値が重複するか否かにより決定される。この区間のＸ方向の値の範囲は「７．５」から「４．５」であり、且つＹ方向の値は「２．１」から「７．５」である。
【００５２】
この場合、値「４．５」から「７．５」が重複する。従って、検出部１２は、上記の区間は、「分離されていない」区間と判定し、変化点を検出する。一方、検出部１２は、「分離されている」区間、同じ単調減少区間および同じ単調増加区間については、変化点の検出を行わない。
【００５３】
単調増加区間は、時系列データの値が減少することなく増加する区間である。単調減少区間は、時系列データの値が増加することなく減少する区間である。同じ単調増加区間および同じ単調減少区間には、変化点が存在しないためである。
【００５４】
「分離されていない」区間については、区間のサイズが大きい場合、検出部１２は、該区間を複数に分割して、変化点の検出を行ってもよい。
【００５５】
＜ウィンドウをずらさない場合の類似度の演算の一例＞
データ１とデータ２との大小関係の一致数の一例について説明する。図７の例において、データ１とデータ２との２つの時系列データは記憶部１１に記憶される。計数部１３は、２つの時系列データを比較して、大小関係の一致数をカウントする。
【００５６】
図７の例の場合、データ１の比較対象の期間（ウィンドウ）は、時刻「２」から「６」であり、データ２のウィンドウは、時刻「４」から「８」である。従って、ウィンドウの範囲は「５」である。以下、ウィンドウ範囲を期間幅と称することもある。ウィンドウ範囲は、一致数を計数する期間の一例である。
【００５７】
図８は、図７の例に示した２つのデータの一致数のカウントの一例を示す。計数部１３は、データ１およびデータ２のそれぞれの期間幅（ウィンドウ）を対象として、大小関係の一致数をカウントする。
【００５８】
比較対象は、時系列データの値の大小関係であるため、計数部１３は、期間幅から「１」を減算した範囲内の大小関係を比較する。データ１とデータ２とでは、先頭の時刻が異なる。
【００５９】
計数部１３は、先頭の時刻から順に大小関係の一致数をカウントする。計数部１３は、データ１とデータ２との先頭の時刻を揃えるため、インデックスを用いる。記憶部１１には、データ１およびデータ２の時間差ごとの変化点データが記憶される。
【００６０】
計数部１３は、インデックスを揃えるため、データ１およびデータ２の変化点データの各値から、先頭の時刻から「１」を減算した値を減算する。例えば、計数部１３は、データ１の変化点データの各値から「２−１＝１」を減算する。また、計数部１３は、データ２の変化点データの各値から「４−１＝３」を減算する。
【００６１】
これにより、データ１とデータ２との始点がインデックスにより揃えられる。計数部１３は、ウィンドウ範囲「１」から「３」までの間におけるデータ１とデータ２との一致数をカウントする。
【００６２】
インデックス１における大小関係は、データ１およびデータ２の双方とも「−」である。よって、両者の大小関係は一致するため、計数部１３は、大小関係の一致数を加算（インクリメント）する。大小関係の一致数の初期値はゼロである。
【００６３】
インデックス２における大小関係は、データ１は「＋」に変化し、データ２は「−」である。インデックス３における大小関係は、データ１は「＋」であり、データ２は「−」である。これらの場合、両者の大小関係は一致しないため、大小関係の一致数は変化しない。
【００６４】
従って、計数部１３は、ウィンドウ範囲内における大小関係の一致数を「１」としてカウントする。計数部１３は、時間差「１」、「３」および「４」について、時間差「２」と同様に、データ１とデータ２との大小関係の一致数をカウントする。
【００６５】
図８の例の場合、一致数の合計は「２」である。この一致数の合計「２」が、上述した式（Ａ）における一致数Ｐである。演算部１４は、ウィンドウ範囲の項目数ｎ（ｎ＝５）および一致数Ｐ（Ｐ＝８）を上述した式（Ａ）に当て嵌めて、類似度ｔ＝「−０．６０」を得る。
【００６６】
＜双方のウィンドウをずらす場合の類似度の演算の一例＞
次に、データ１およびデータの２の双方のウィンドウをずらす場合の類似度の演算の例について説明する。上述したように、計数部１３は、図８の例で示されるウィンドウにおけるデータ１とデータ２との大小関係の一致数をカウントする。この場合、一致数Ｐは「２」である。
【００６７】
差分処理部１５は、データ１とデータ２とのそれぞれのウィンドウを時間軸方向に１つだけ後ろにずらす。計数部１３は、ウィンドウの範囲内に変化点が入ったか否か、および該ウィンドウの範囲内から変化点が出たか否かに基づいて、データ１とデータ２との大小関係の一致数をカウントする。
【００６８】
図９以降、実線で囲まれたウィンドウ範囲はウィンドウがずらされる前の範囲を示し、点線で囲まれたウィンドウ範囲はウィンドウがずらされた後の範囲を示す。
【００６９】
図９の例の場合、差分処理部１５がウィンドウをずらすことにより、一致数が２つ増え、且つ２つ減る。従って、一致数の変化量は「０＝２−２」である。ウィンドウがずらされる前の一致数Ｐは「２」であったため、計数部１３は、一致数Ｐが「２＝２＋０」としてカウントする。
【００７０】
図１０の例は、マトリクスにおいて、ウィンドウの位置が変化した場合、変化点がウィンドウから出る場合と、ウィンドウに入る場合とを示す。上述したように、マトリクスは、時系列データの大小関係のイメージである。
【００７１】
図１０以降、基準のウィンドウは、差分処理部１５によりずらされる前のウィンドウを示す。更新後のウィンドウは、差分処理部１５によりずらされた後のウィンドウを示す。
【００７２】
図１１の例において、データ１における基準ウィンドウ内の前端（Ｘ方向の時刻「６」、Ｙ方向の時刻「２」から「６」）の大小関係は全て「＋」である。データ２における基準ウィンドウ内の先端（Ｘ方向の時刻「８」、Ｙ方向の時刻「４」から「８」）の大小関係は全て「−」である。
【００７３】
従って、ウィンドウがずらされる前における該ウィンドウ内の先端における大小関係の一致数はゼロである。
【００７４】
データ１における基準ウィンドウ外の後端（Ｙ方向の時刻「１」、Ｘ方向の時刻「２」から「６」）の大小関係は全て「−」である。データ１における基準ウィンドウ外の後端（Ｙ方向の時刻「３」、Ｘ方向の時刻「４」から「８」）の大小関係は全て「−」である。
【００７５】
従って、ウィンドウがずらされる前における該ウィンドウ外の後端における大小関係の一致数は「４」である。一致数の変化量は、「−４＝０−４」となる。
【００７６】
ウィンドウがずらされた際に、変化点がウィンドウに出入りしなければ、一致数の変化量は一定である。一方、ウィンドウがずらされた際に、変化点がウィンドウに出入りする場合、一致数の変化量は変化する。
【００７７】
図１１の例の場合、ウィンドウがずらされた後（更新後）の一致数は「２」になる。図１２の例を参照して、ウィンドウがずらされる際に、該ウィンドウに変化点が含まれる場合の例について説明する。
【００７８】
差分処理部１５は、データ１およびデータ２のウィンドウをずらす。差分処理部１５は、変化点データを参照して、ウィンドウがずらされたことにより、変化点が該ウィンドウに出入りするかを判定する。
【００７９】
差分処理部１５は、データ１とデータ２との時系列データのウィンドウをずらした際に、変化点データで特定される変化点が該ウィンドウに出入りする場合、該変化点の大小関係を反転させる。
【００８０】
図１２の例の場合、ウィンドウがずらされる前、時間差「１」および「２」のウィンドウ内前端の大小関係は「×」であった。ウィンドウがずらされることにより、時間差「１」および「２」のウィンドウ内前端に変化点が入る。従って、差分処理部１５は、時間差「１」および「２」における変化点の大小関係を反転させる。
【００８１】
また、ウィンドウがずらされる前、時間差「３」および「４」のウィンドウ外後端の大小関係は「○」であった。ウィンドウがずらされることにより、時間差「３」および「４」のウィンドウ外後端から変化点が出る。従って、差分処理部１５は、時間差「３」および「４」における変化点の大小関係を反転させる。
【００８２】
その結果、データ１とデータ２とのウィンドウ内前端の一致数は「２」になり、ウィンドウ外後端の一致数は「２」になる。従って、差分処理部１５は、一致数の変化量「０＝２−２」を得る。ウィンドウがずらされる前の一致数は「２」であったため、差分処理部１５は、一致数「２＝２＋０」を得る。
【００８３】
次に、図１３の例を参照して、ウィンドウに対する変化点の位置関係を示す管理テーブルの一例について説明する。検出部１２は、データ１およびデータ２の大小関係が変化する変化点を検出する。実施形態では、管理テーブルは記憶部１１に記憶される。
【００８４】
また、上述したように、データ１およびデータ２の双方のウィンドウがずれる場合、ウィンドウに入る変化点、およびウィンドウから出る変化点に基づいて、ウィンドウの範囲内の大小関係の一致数が得られる。
【００８５】
そして、得られた一致数Ｐに基づいて、演算部１４が上述した式（Ａ）に基づいて演算を行うことにより、ウィンドウがずれるごとに、２つの時系列データの類似度が演算される。
【００８６】
検出部１２は大小関係の変化点を検出する。計数部１３は、ウィンドウと変化点との位置関係を管理する。実施形態では、図１３の例に示す管理テーブルにより、差分処理部１５は、ウィンドウと変化点との位置関係を管理する。
【００８７】
例えば、データ２において、ウィンドウがずれる前（更新前）は、変化点９番および１０番は、ウィンドウの範囲内に入っていない。ただし、次の時間でウィンドウがずれることにより（更新後）、変化点９番および１０番は、ウィンドウの範囲内に入る。
【００８８】
ウィンドウの移動方向前端および移動方後端のそれぞれについて、変化点がウィンドウに入るか、または変化点がウィンドウから出るかが管理される。計数部１３は、この管理テーブルに基づいて、ウィンドウに入る変化点およびウィンドウから出る変化点を認識することができる。
【００８９】
これにより、計数部３１は、管理テーブルを参照するだけで、ウィンドウの位置の変化に応じた一致数の変化量を認識でき、ウィンドウの位置が変化した後の、データ１とデータ２との大小関係の一致数を簡単に得ることができる。
【００９０】
図１３の例において、差分処理部１５は、時系列データと変化点データとに基づいて、各変化点とウィンドウとの位置関係を認識する。図１３の例では、差分処理部１５は、ウィンドウ内後端から出る変化点とウィンドウ内前端に位置する変化点とをテーブルを用いて管理する。このテーブルを管理テーブルと称する。
【００９１】
管理テーブルは、変化点ごとに、ウィンドウ内前端またはウィンドウ外後端に到達するまでの時間（到達時間）を示すテーブルである。到達時間は、ウィンドウ内前端またはウィンドウ外後端に到達するまでに、ウィンドウがずらされる回数を示す。
【００９２】
図１３の例の場合、ウィンドウがずれた後、変化点９番および１０番は、ウィンドウに入る。また、ウィンドウがずれた後、変化点１番および２番は、ウィンドウから出る。よって、差分処理部１５は、変化点１番、２番、９番および１０番を到達時間ゼロとして、管理テーブルを用いて管理する。
【００９３】
従って、差分処理部１５は、管理テーブルを用いて、ウィンドウと各変化点との位置関係を管理することで、ウィンドウに出入りする変化点を容易に認識することができる。差分処理部１５は、ウィンドウがずれた後における一致数の変化量を求める。
【００９４】
この際、差分処理部１５は、ウィンドウをずらした際に、管理テーブルを参照するだけで、ウィンドウに出入りする変化点を容易に認識することができ、一致数の変化量を迅速に求めることができる。
【００９５】
＜片方のウィンドウをずらす場合の類似度の演算の一例＞
次に、データ１とデータ２とのうち片方のウィンドウを固定し、他方のウィンドウをずらす場合における類似度の演算について説明する。上述したように、ウィンドウがずらされる前におけるデータ１とデータ２との大小関係の一致数Ｐは「２」である。
【００９６】
片方のウィンドウがずらされる場合、計数部１３は、ウィンドウの移動方向前端および移動方向後端の一致数の変化量だけでなく、ウィンドウ内での変化点の位置関係も考慮して、データ１とデータ２との大小関係をカウントする。
【００９７】
図１４の例では、データ１のウィンドウは固定され（固定ウィンドウ）、データ２のウィンドウがずらされる。ウィンドウ内の相対位置を基準に見ると、ウィンドウがずらされるごとに、データ１のウィンドウ内の変化点とデータ２のウィンドウ内の変化点との相対位置関係が変化する。
【００９８】
データ１の固定ウィンドウ内の変化点は固定されているため、データ２のウィンドウ内の変化点が、データ１の固定ウィンドウ内の変化点を追い越す場合がある。計数部１３は、この追い越しも考慮して、データ１とデータ２との大小関係をカウントする。
【００９９】
図１５の例は、データ２のウィンドウ（以下、移動ウィンドウと称することもある）がずらされた後における大小関係の一致数の変化量が「２」である場合を示している。
【０１００】
２つのデータのウィンドウのうち、片方のウィンドウを固定し、片方のウィンドウをずらす場合、大小関係の一致数をカウントするため、差分処理部１５は、固定ウィンドウに対して、変化点を追加する。
【０１０１】
図１６の例に示すように、差分処理部１５は、固定ウィンドウに対して、タイプＡとタイプＢとタイプＣとの３つのタイプを設定する。差分処理部１５は、タイプに応じて、固定ウィンドウに対して、変化点を追加する。タイプＣの場合、差分処理部１５は、変化点を追加しない。
【０１０２】
タイプＡの範囲は、固定ウィンドウ外の前端に設定され、タイプＢの範囲は、固定ウィンドウ内の後端に設定される。また、タイプＡの範囲とタイプＢの範囲とは、同じ時間差の範囲に設定される。
【０１０３】
例えば、図１６の例の場合、タイプＡの範囲は、固定ウィンドウ外の前端であるＹ方向の時刻「７」、時間差「１」から「４」に設定される。タイプＢの範囲は、固定ウィンドウ内の後端であるＸ方向の時刻「２」、時間差「１」から「４」に設定される。タイプＣは、固定ウィンドウ内のタイプＢの範囲以外に設定される。
【０１０４】
差分処理部１５は、タイプＡの範囲およびタイプＢの範囲に変化点の要素がなければ、該要素を変化点として追加する。この際、差分処理部１５は、変化点を追加する要素の大小関係を反転させて、変化点を追加する。
【０１０５】
図１６の例では、タイプＡの範囲に変化点はなく、タイプＢの範囲に２つの変化点が存在する。従って、差分処理部１５は、大小関係を反転させて、タイプＡの範囲に４つの変化点を追加し、タイプＢの範囲に２つの変化点を追加する。
【０１０６】
図１７は、片方のウィンドウをずらす場合の一致数の変化量の一例を示す。差分処理部１５は、上述したタイプごとに、変化量の重み付けを行う。図１７の例では、タイプＡの範囲の各要素において大小関係が一致する場合、重みは「０」であり、大小関係が一致しない場合、重みは「１」である。
【０１０７】
タイプＢの範囲の各要素において大小関係が一致する場合、重みは「−１」であり、大小関係が一致しない場合、重みは「０」である。タイプＣの範囲の各要素において大小関係が一致する場合、重みは「−１」であり、大小関係が一致しない場合、重みは「１」である。
【０１０８】
図１７の例において、「アンカー」は、変化点のある要素を示す。アンカーには、追加された変化点も含まれる。図１７の例において、差分処理部１５は、データ１の固定ウィンドウ内の各アンカーにおける大小関係と、データ２のウィンドウにおける対応する点の大小関係とが一致するかを検出する。
【０１０９】
図１７の例の場合、タイプＡの範囲の４つの要素は全て大小関係が一致し、タイプＢの範囲の４つの要素は全て大小関係が一致せず、タイプＣの範囲の２つの要素は全て大小関係が一致しない。計数部１３は、上記の重みに基づいて、大小関係の一致数の変化量を得る。図１７の例の場合、大小関係の一致数の変化量は「２（＝０＋０＋２）」である。
【０１１０】
次に、図１８の例を参照して、変化量の重みについて説明する。図１８の例において、薄い網掛けは大小関係が「−」である期間を示し、濃い網掛けは大小関係が「＋」であることを示す。
【０１１１】
タイプＡにおいて、アンカーの位置でデータ１とデータ２との大小関係が一致している場合、データ２のウィンドウがずらされたとしても、ウィンドウ内の一致数は増減しない。従って、この場合の変化量の重みはゼロである。
【０１１２】
タイプＡにおいて、アンカーの位置でデータ１とデータ２との大小関係が不一致の場合、データ２のウィンドウがずらされると、ウィンドウ内の一致数は１つ増える。従って、この場合の変化量の重みは「１」である。
【０１１３】
タイプＢにおいて、アンカーの位置でデータ１とデータ２との大小関係が一致している場合、データ２のウィンドウがずらされると、ウィンドウ内の一致数は１つ減る。従って、この場合の変化量の重みは「−１」である。
【０１１４】
タイプＢにおいて、アンカーの位置でデータ１とデータ２との大小関係が不一致の場合、データ２のウィンドウがずらされたとしても、ウィンドウ内の一致数は増減しない。従って、この場合の変化量の重みはゼロである。
【０１１５】
タイプＣにおいて、アンカーの位置でデータ１とデータ２との大小関係が一致している場合、データ２のウィンドウがずらされると、ウィンドウ内の一致数は１つ減る。従って、この場合の変化量の重みは「−１」である。
【０１１６】
タイプＣにおいて、アンカーの位置でデータ１とデータ２との大小関係が不一致の場合、データ２のウィンドウがずらされると、ウィンドウ内の一致数は１つ増える。従って、この場合の変化量の重みは「１」である。
【０１１７】
図１９は、データ２のウィンドウをずらした後における大小関係の一致数の変化量の一例を示す。図１９の例に示されるように、データ２のウィンドウがずらされると、タイプＢの２つのアンカーに対応するデータ２のウィンドウ内の点が変化点になる。
【０１１８】
この場合、差分処理部１５は、上記２つのアンカーを反転させる。図１９の例の場合、２つのアンカーの一致関係は不一致であった。差分処理部１５は、更新後（データのウィンドウがずらされた後）の２つのアンカーの一致関係を一致に反転させる。
【０１１９】
図１９の例では、データ２のウィンドウがずらされた結果、データ１とデータ２とで対応する点の大小関係の一致が反転された場合、タイプごとの重みに基づいて、差分処理部１５は、大小関係の一致数の変化量を得る。
【０１２０】
図１９の例に示されるように、タイプＡのアンカーが一致から不一致になった場合、重みはゼロから「１」に変化するため、変化量の差分は「１」になる。タイプＡのアンカーが一致から不一致になった場合、重みは「１」からゼロに変化するため、変化量の差分は「−１」になる。
【０１２１】
タイプＢのアンカーが一致から不一致になった場合、重みの変化に基づいて、変化量の差分は「１」になる。タイプＢのアンカーが不一致から一致になった場合、重みの変化に基づいて、変化量の差分は「−１」になる。
【０１２２】
タイプＣのアンカーが一致から不一致になった場合、重みの変化に基づいて、変化量の差分は「２」になる。タイプＣのアンカーが不一致から一致になった場合、重みの変化に基づいて、変化量の差分は「−２」になる。
【０１２３】
差分処理部１５は、各アンカーの変化量の差分を求める。図１９の例の場合、タイプＢの２つのアンカーが一致から不一致に変化したため、差分処理部１５は、大小関係の一致数の変化量から「−２（＝−１−１）」を減算する。
【０１２４】
上述したように、更新前（データ２のウィンドウをずらす前）の一致数の変化量は「２」であったため、差分処理部１５は、更新後（データ２のウィンドウをずらした後）の一致数の変化量「４（＝２−（−２））」を得る。
【０１２５】
次に、片方のウィンドウをずらす場合における管理テーブルについて説明する。上述したように、管理テーブルは、ウィンドウと変化点との位置関係を管理するテーブルである。図２０は、片方のウィンドウをずらす場合における管理テーブルの一例を示す。
【０１２６】
差分処理部１５は、データ１のアンカーの各要素およびデータ２の各変化点にアドレスを付与する。図２０の例では、差分処理部１５は、アンカーの各要素のアドレスに対してアルファベットを付与し、データ２の各変化点のアドレスに対して数字を付与する。
【０１２７】
例えば、管理テーブルの「４−ｂ」は、データ２の変化点のアドレスが「４」であり、且つアンカーのアドレスが「ｂ」であることを示す。更新前における「４−ｂ」は、データ２のウィンドウがずらされる前のアドレスを示す。
【０１２８】
データ２のウィンドウがずらされた場合、差分処理部１５は、ウィンドウに入った変化点について、アンカーの付け替えを行うか否かを判定する。差分処理部１５は、以下の２つの基準に応じて、アンカーの付け替えを行う。
（１）ウィンドウに入った変化点が１つ前のアンカーに対応する場合
（２）ウィンドウに入った変化点の１つ後ろの変化点が、該変化点のアンカーに対応する場合
【０１２９】
図２０の例の場合、アドレス「４−ｂ」のうち「ｂ」より前に対応するアンカーはない。従って、差分処理部１５は、上記（１）を満たしていないと判定する。また、ウィンドウに入った変化点のアドレス「４−ｂ」の１つ後ろの変化点は「５」である。
【０１３０】
ただし、データ２の変化点のアドレス「５」はアンカー「ｉ」に対応する。つまり、差分処理部１５は、管理テーブルでは、データ２の変化点のアドレス「５」を「５−ｉ」として管理する。
【０１３１】
従って、変化点「４」のアンカーは「ｂ」であり、１つ後ろの変化点「５」のアンカーは「ｉ」であるため、アンカーが対応していない。このため、差分処理部１５は、上記（２）の条件が満たされていないと判定する。
【０１３２】
＜各種具体例の説明＞
次に、図２１の例に示される３つの時系列データ（データ１からデータ３）について、時系列データの類似度の演算の３つの具体例を説明する。
【０１３３】
具体例１（図２１の（１））は、データ１とデータ２との間の類似度、データ１とデータ３との間の類似度、およびデータ２とデータ３との間の類似度を演算する例である。類似度の演算の対象となる期間は時刻「２」から「８」である。類似度の演算の対象となる期間は、上述したウィンドウである。
【０１３４】
具体例２（図２１の（２））は、類似度の演算の対象となる時系列データはデータ１およびデータ２の２つである。具体例２では、類似度の演算の対象となる期間は時刻「１」から「７」および時刻「４」から「１０」である。
【０１３５】
具体例２では、差分処理部１５は、データ１およびデータ２の双方のウィンドウをずらしながら、一致数の変化量を求める。そして、具体例２では、演算部１４は、合計４ペアの類似度（相関値）を演算する。
【０１３６】
具体例３（図２１の（３））は、類似度の演算の対象となる時系列データはデータ１およびデータ２の２つである。具体例３では、類似度の演算の対象となる期間は時刻「３」から「９」および時刻「４」から「１０」である。
【０１３７】
具体例３では、差分処理部１５は、データ１およびデータ２ののうち、データ１のウィンドウを固定し、データ２のウィンドウをずらしながら、一致数の変化量を求める。そして、具体例３では、演算部１４は、合計４ペアの類似度（相関値）を演算する。
【０１３８】
＜具体例１＞
図２２は、時間差が「１」の場合における変化点の検出の例を示す。図２２の例に示される時系列データにおいて、時刻「１」から「３」は値が単調増加し、時刻「３」から「７」は値が単調減少し、「７」から「１０」は値が単調減少する。
【０１３９】
従って、値の大小関係が変化する時刻は「１」、「３」、「７」および「１０」である。図２２以降の例において、実線の矢印は、単調増加区間を示し、破線の矢印は単調減少区間を示す。
【０１４０】
検出部１２は、値の大小関係が変化する時刻に加えて、該時刻の前の時刻を考慮して、変化点を検出する。検出部１２は、図２３の例のうち、区間「１」から「２」、区間「２」から「３」、区間「３」から「６」、区間「６」から「７」、および区間「７」から「９」を比較処理する対象の区間として、変化点を検出する。
【０１４１】
上記の各区間は、図２３の例において、「比較元」として表記されており、「比較元」はマトリクスのＹ方向である。「比較先」は、時間差が「１」であるため、「比較元」の時刻に「１」を加算した時刻になる。「比較先」は、マトリクスのＸ方向である。
【０１４２】
図２４は、時刻「１」と時刻「２」との間の時間差の一例を示す。時刻「１」の値は「２．１」であり、時刻「２」の値は「５．３」である。時刻「１」と時刻「２」との間の時間差は初期値である。
【０１４３】
時刻「１」の値は、時刻「２」の値より小さいため、時刻「１」と時刻「２」との大小関係は「−」になる。従って、検出部１２は、時間差「１」で「１−」を検出する。図２４の例のマトリクスでは、Ｙ方向（比較元）の時刻が「１」であり、且つＸ方向（比較先）の時刻が「２」の点が「−」の変化点となる。
【０１４４】
図２５は、時刻「１」から「２」の間を比較元とし、時刻「２」から「３」の間を比較先とした場合の変化点の検出の一例を示す。この場合、比較元の時刻「２」の値と比較先の時刻「３」の値とが同じである。
【０１４５】
ただし、検出部１２は、比較元と比較先とで一致する値が１つの場合、比較元の区間と比較先の区間とは分離されているとみなす。従って、比較元の区間と比較先の区間とは分離されているため、検出部１２は変化点を検出しない。
【０１４６】
図２６は、時刻「２」から「３」の間を比較元とし、時刻「３」から「４」の間を比較先とした場合の変化点の検出の一例を示す。この場合、比較元の区間と比較先の区間とでは、値「６．２」から値「７．５」までが重複する。よって、検出部１２は、比較元の区間と比較先の区間とが分離されていないことを検出する。
【０１４７】
従って、検出部１２は、上記の区間で、大小関係が変化する変化点があれば、該変化点を検出する。図２６の例の場合、時刻「３」において、値の大小関係が変化する。つまり、時刻「２」の値は時刻「３」の値より小さいため、大小関係は「−」である。
【０１４８】
一方、時刻「３」の値は時刻「４」の値より大きいため、大小関係は「＋」である。このため、検出部１２は、時刻「３」において、値の大小関係が変化したことを検出する。つまり、検出部１２は、時刻「３」を変化点として検出する。検出部１２は、変化点データのうち時間差「１」に「３＋」を追加する。
【０１４９】
次に、図２７の例に示されるように、検出部１２は、比較元の時刻「３」から「６」の区間および比較先の時刻「４」から「７」の区間で、大小関係が変化する変化点があれば、該変化点を検出する。
【０１５０】
比較元の時刻「３」から「６」の区間および比較先の時刻「４」から「７」の区間は、単調減少区間である。よって、この単調減少区間に変化点は存在しない。従って、検出部１２は、同じ単調減少区間における変化点の検出をスキップする。
【０１５１】
図２８は、時刻「６」から「７」の間を比較元とし、時刻「７」から「８」の間を比較先とした場合の変化点の検出の一例を示す。比較元の区間と比較先の区間とは値が重複するため、検出部１２は、比較元の区間と比較先の区間とが分離されていないことを検出する。
【０１５２】
従って、検出部１２は、上記の区間で、大小関係が変化する変化点があれば、該変化点を検出する。図２８の例の場合、時刻「７」において、値の大小関係が変化したことを検出する。検出部１７は、変化点データのうち時間差「７」に「７−」を追加する。
【０１５３】
図２９の例において、比較元の時刻「７」から「９」の区間および比較先の時刻「８」から「１０」の区間は、単調増加区間である。よって、この単調増加区間に変化点は存在しない。従って、検出部１２は、同じ単調増加区間における変化点の検出をスキップする。
【０１５４】
次に、時間差が「２」の場合における変化点の検出について説明する。図３０の例に示されるように、値の大小関係が変化する時刻は「１」、「３」、「７」および「１０」である。
【０１５５】
時間差が「２」であるため、「何れかが反転する時刻」は、上記の各時刻から「２」を減算した時刻「−１」、「１」、「５」および「８」である。従って、比較元の区間および比較先の区間は、図３０の例に示す区間になる。
【０１５６】
時間差が「２」の場合、値の大小関係を比較する対象となる時刻の時間差は「２」である。例えば、図３１の例の場合、検出部１２は、時刻「１」と時刻「３」との間の値の大小関係を比較する。
【０１５７】
この場合、時刻「１」の値は、時刻「３」の値より小さいため、大小関係は「−」になる。検出部１２は、時間差「２」の初期値に「１−」を追加する。なお、検出部１２は、時間差「１」についての処理が終了した変化点データに、時間差「２」の変化点データを追加する。
【０１５８】
図３２は、時刻「１」から「３」の間を比較元とし、時刻「３」から「５」の間を比較先とした場合の変化点の検出の一例を示す。比較元の区間と比較先の区間とで値は重複する。従って、検出部１２は、この区間で変化点があれば、該変化点を検出する。
【０１５９】
検出部１２は、変化点を検出する区間を分割してもよい。図３２の例では、検出部１２は、上記の区間を２つに分割し、それぞれの区間で変化点を検出する。区間が大きい場合、検出部１２は、１つの区間から変化点の検出を行うよりも、分割された小サイズの区間から変化点の検出を行う方が効率的な場合がある。
【０１６０】
図３２の例の場合、検出部１２は、上記の区間を２つの区間に分割する。１つ目の区間は、比較元の時刻が「１」から「２」であり、比較先の時刻が「３」から「４」の区間である。２つ目の区間は、比較元の時刻が「２」から「３」であり、比較先の時刻が「４」から「５」の区間である。
【０１６１】
１つ目の区間では、値の大小関係に変化がないため、検出部１２は、変化点を検出しない。２つ目の区間では、時刻「３」において、値の大小関係が変化する。このため、検出部１２は、２つ目の区間で変化点を検出する。従って、検出部１２は、時間差「２」の変化点データに「３＋」を追加する。
【０１６２】
図３３は、時刻「３」から「５」の間を比較元とし、時刻「５」から「７」の間を比較先とした場合の変化点の検出の一例を示す。この区間は、単調減少区間であるため、変化点は存在しない。従って、検出部１２は、同じ単調減少区間における変化点の検出をスキップする。
【０１６３】
図３４は、時刻「５」から「７」の間を比較元とし、時刻「７」から「９」の間を比較先とした場合の変化点の検出の一例を示す。この区間は、値が分離されていない。よって、検出部１２は、この区間に変化点があれば、該変化点を検出する。
【０１６４】
図３４の例では、検出部１２は、上記の区間を２つに分割する。１つ目の区間は、時刻「５」から「６」の間が比較元であり、時刻「７」から「８」の間が比較先である。２つ目の区間は、時刻「６」から「７」の間が比較元であり、時刻「８」から「９」の間が比較先である。
【０１６５】
１つ目の区間では、値の大小関係は変化しない。よって、検出部１２は、１つ目の区間から変化点を検出しない。２つ目の区間では、時刻「７」において値の大小関係が変化する。検出部１２は、時刻「７」を変化点として検出し、時間差「２」の変化点データに「７−」を追加する。
【０１６６】
図３５は、時刻「７」から「８」の間を比較元とし、時刻「９」から「１０」の間を比較先とした場合の変化点の検出の一例を示す。この区間は、同じ単調増加区間であるため、検出部１２は、変化点を検出しない。従って、変化点の検出はスキップされる。
【０１６７】
検出部１２は、時間差「３」から「９」まで上述した処理を繰り返す。これにより、検出部１２は、図３６の例に示されるような変化点データを生成する。計数部１３は、変化点データに基づいて、大小関係の一致数をカウントし、演算部１４は、２つの時系列データの類似度を演算する。
【０１６８】
例えば、比較対象の時系列データのそれぞれについて、時間差ごとの大小関係を全て記憶する場合、記憶する大小関係の情報量は多くなる。このため、大小関係の一致数をカウントする処理に長い時間がかかり、類似度の演算時間も長くなる。
【０１６９】
また、比較対象の時系列データのそれぞれについて、時間差ごとの値の大小関係を全て記憶する場合、記憶する情報量が多くなる。
【０１７０】
上述したように、検出部１２は、時系列データの変化点を記憶部１１に記憶する。計数部１３は、該変化点に基づいて、大小関係の一致数をカウントし、演算部１４は、大小関係の一致数Ｐに基づいて、時系列データ同士の類似度の演算を行う。
【０１７１】
演算部１４は、大小関係の変化点に基づいてカウントされた大小関係の一致数Ｐを用いて、時系列データ同士の類似度の演算を行うため、時間差ごとの全ての大小関係に基づいて演算を行う場合と比較して、演算する対象の情報が少なくなる。このため、類似度の演算を行うための演算時間が短くなる。
【０１７２】
また、時系列データの時間差ごとの大小関係を全て記憶する場合と比較すると、大小関係の変化点のみを示す変化点データを記憶する方が、記憶する情報量が少なくなる。さらに、検出部１２は、同じ単調増加区間や同じ単調減少区間等をスキップして変化点を検出するため、変化点を迅速に検出することができる。
【０１７３】
図３７は、データ２およびデータ３の変化点データの例を示す。検出部１２は、上述したデータ１の場合と同様に、データ２およびデータ３の変化点を検出し、変化点データを記憶部１１に記憶する。
【０１７４】
次に、時刻「２」から「８」までの間におけるデータ１とデータ２との大小関係の一致数について説明する。図３８は、データ１およびデータ２の変化点データと、それぞれのマトリクスとの一例を示す。
【０１７５】
計数部１３が、時刻「２」から「８」までの間におけるデータ１とデータ２との大小関係の一致数をカウントする場合、ウィンドウ範囲は「７」である。従って、図３９の例に示されるように、一致数をカウントする対象は、時間差「１」から「６」の間である。
【０１７６】
データ１は「Ｄ１」と表記され、データ２は「Ｄ２」と表記される。計数部１３は、データ１とデータ２との間の大小関係の一致数をカウントするため、ウィンドウの端が「１」になるようにオフセットを求める。
【０１７７】
データ１およびデータ２のウィンドウは、時刻「２」から始まるため、データ１のオフセットも、データ２のオフセットも「１（＝２−１）」になる。上述したように、時間差が「１」の場合、ウィンドウ範囲は、時刻「１」から「６（＝７−１）」になる。
【０１７８】
図４０の例に示されるように、類似度の演算の対象となる２つの時系列データのそれぞれについて、変化点を示すテーブルを変化点テーブルと称する。変化点テーブルの各項目には、変化点の情報が格納される。各項目の括弧には、変化点の値からオフセットの値を減じた値が格納されてもよい。
【０１７９】
図４０の例には、データ１およびデータ２のマトリクスが示される。図４０の例において、２つのマトリクスの間には、時間差に応じた変化点のＹ方向に対応する位置が示される。一点鎖線は、ウィンドウ範囲を示す。
【０１８０】
図４１は、データ１の変化点「１−」とデータ２の変化点「１−」との比較の例を示す。データ１およびデータ２の変化点「１−」は、ウィンドウ範囲から外れている。図４１の例において、２つのマトリクスの間の点線で囲まれた２つの変化点が、データ１の変化点「１−」およびデータ２の変化点「１−」である。
【０１８１】
これら２つの変化点は、大小関係の一致数をカウントする対象となるウィンドウ範囲から外れている。よって、計数部１３は、これら２つの変化点については、大小関係が一致するかを判定しない。つまり、図４１の例の時点での一致数は「０」である。
【０１８２】
また、計数部１３は、変化点テーブルのうち、データ１の変化点「１−」の項目およびデータ２の変化点「１−」の項目の括弧に、変化点の値からオフセットの値を減じた値を格納する。
【０１８３】
図４１は、データ１の変化点「１−」とデータ２の変化点「１−」との比較の例を示す。データ１およびデータ２の変化点「１−」は、ウィンドウ範囲から外れている。図４１の例において、２つのマトリクスの間の点線で囲まれた２つの変化点が、データ１の変化点「１−」およびデータ２の変化点「１−」である。
【０１８４】
これら２つの変化点は、大小関係の一致数をカウントする対象となるウィンドウ範囲から外れている。よって、計数部１３は、これら２つの変化点については、大小関係が一致するかを判定しない。つまり、図４１の例の時点での一致数は「０」である。
【０１８５】
計数部１３は、大小関係の一致数についての処理が終わると、変化点テーブルの各変化点のうち、インデックスの値が最も低い変化点に、比較対象を移す。よって、次に、比較対象となる変化点は、変化点「２＋」である。
【０１８６】
図４２は、データ１の変化点「１−」とデータ２の変化点「２＋」との比較の例を示す。データ１の変化点「１−」は、ウィンドウ範囲から外れている。従って、図４２の例の時点での一致数は「０」である。
【０１８７】
次に、比較対象となる変化点はデータ１については、変化点「３＋」であり、データ２については変化点「３−」である。これら２つの変化点のインデックスは同じ値である。この場合、計数部１３は、データ１の変化点およびデータ２の変化点を共に移す。
【０１８８】
図４３は、データ１の変化点「３＋」とデータ２の変化点「３−」との比較の例を示す。計数部１３は、データ１とデータ２とのそれぞれについて、変化点における大小関係に基づいて、大小関係の一致数をカウントする。
【０１８９】
図４３の例の場合、データ１の変化点「３＋」のオフセットは「２」であり、データ２の変化点「３−」のオフセットは「２」である。両者の大小関係は一致しない。従って、図４３の例の時点での一致数は「０」である。
【０１９０】
図４４の例は、データ１の比較対象が次の変化点「７−」に移された場合を示す。データ１の変化点「７ー」のオフセットは「６」であり、ウィンドウ範囲内におけるオフセット「６」以前の大小関係は「−」である。
【０１９１】
データ２の変化点「３−」のオフセットは「２」であり、ウィンドウ範囲内におけるオフセット「２」以降の大小関係は「−」である。よって、データ１とデータ２との大小関係は、オフセット「６」において一致する。
【０１９２】
このため、計数部１３は、大小関係の一致数を加算する。大小関係の一致数の初期値はゼロであるため、この時点における大小関係の一致数は「１」である。
【０１９３】
図４５の例に示されるように、計数部１３は、データ２の比較対象を次の変化点「８＋」に移す。この時点では、ウィンドウ範囲内におけるデータ１とデータ２との大小関係の比較は終了している。従って、計数部１３は、一致数がゼロとして、時間差「１」における大小関係の一致数をカウントする処理を終了する。
【０１９４】
次に、時間差「２」の場合における大小関係の一致数について説明する。図４６の例において、時間差が「２」であるため、ウィンドウ範囲は「１」から「５」の間になる。
【０１９５】
図４７は、データ１の変化点「１−」とデータ２の変化点「１−」との比較の例を示す。これら２つの変化点は、ウィンドウ範囲から外れている。よって、計数部１３は、これら２つの変化点については、大小関係が一致するかを判定しない。つまり、図４７の例の時点での一致数は「０」である。
【０１９６】
図４８の例に示されるように、データ１の変化点「３＋」とデータ２の変化点「３−」とのオフセットは同じである。計数部１３は、データ１の変化点「３＋」とデータ２の変化点「３−」とに比較対象を移す。
【０１９７】
データ１の変化点「３＋」のオフセットは「２」であり、ウィンドウ範囲内におけるオフセット「２」以前の大小関係は「＋」である。データ２の変化点「３−」のオフセットは「２」であり、ウィンドウ範囲内におけるオフセット「２」以前の大小関係は「−」である。
【０１９８】
よって、両者の大小関係は一致しない。計数部１３は、大小関係の一致数を加算しない。時間差「２」における大小関係の一致数の初期値はゼロであるため、この時点における大小関係の一致数はゼロである。
【０１９９】
図４９の例に示されるように、データ１の変化点「７−」とデータ２の変化点「７＋」とのインデックスは同じである。計数部１３は、データ１の変化点「７−」とデータ２の変化点「７＋」とに比較対象を移す。
【０２００】
データ１の変化点「３＋」から変化点「７−」までの大小関係は「−」である。データ２の変化点「３−」から変化点「７＋」までの大小関係は「＋」である。よって、両者の大小関係は一致しないため、計数部１３は、大小関係の一致数を加算しない。
【０２０１】
従って、この時点における大小関係の一致数はゼロになるため、時間差「２」における一致数はゼロとして処理が終了する。
【０２０２】
計数部１３は、上述したように、時間差「１」および時間差「２」について、データ１とデータ２との大小関係の一致数のカウントを行う。上述したように、大小関係の一致数のカウントは、大小関係の変化点に基づいて行われる。
【０２０３】
計数部１３は、時間差「１」および「２」と同様に、時間差「３」から「７」までの大小関係の一致数のカウントを行う。上述したように、データ１とデータ２との類似度の演算を行う対象となる期間は、時刻「２」と「８」の間の期間である。
【０２０４】
計数部１３は、時間差ごとの一致数を合計する。図５０の例の場合、計数部１３は、時刻「２」と「８」との間におけるデータ１とデータ２との大小関係の一致数Ｐが「１」であることを得る。
【０２０５】
演算部１４は、計数部１３がカウントした一致数Ｐと、時系列データのデータサイズ（項目数＝ｎ）とを用いて、上述した式（Ａ）により、時刻「２」と「８」との間におけるデータ１とデータ２との類似度（相関値）を演算する。
【０２０６】
一致数Ｐは「Ｐ＝１」であり、項目数ｎは、時刻「２」から「８」までのウィンドウ範囲の時間（項目）の数であるため、「ｎ＝７」である。よって、演算部１４は、上述した式（Ａ）を用いて演算を行い、類似度「ｔ＝（４×１／７×（７−１））−１」を得る。この演算結果は、約「−０．９０」となる。
【０２０７】
従って、上記のウィンドウ範囲におけるデータ１とデータ２との類似度（相関値）は、約「−０．９０」であることが得られる。
【０２０８】
具体例１では、演算部１４は、データ１とデータ２との類似度だけでなく、データ１とデータ３との類似度、およびデータ２とデータ３との類似度の演算も行う。
【０２０９】
図５１の例に示されるように、上記のウィンドウ範囲におけるデータ１とデータ３との時間差ごとの大小関係の一致数を合計した値は「１１」である。演算部１４は、一致数Ｐ（Ｐ＝１１）および項目数ｎ（ｎ＝７）を用いて、式（Ａ）の演算を行う。演算結果（類似度ｔ）は、約「−０．０５」である。
【０２１０】
上記のウィンドウ範囲におけるデータ２とデータ３との時間差ごとの大小関係の一致数を合計した値は「９」である。演算部１４は、一致数Ｐ（Ｐ＝９）および項目数ｎ（ｎ＝７）を用いて、式（Ａ）の演算を行う。演算結果（類似度ｔ）は、約「−０．１４」である。
【０２１１】
従って、データ１とデータ２とデータ３とのうち２つの時系列データのペアの３組の類似度が得られる。
【０２１２】
＜具体例２＞
具体例２は、比較対象の２つの時系列データにおける双方のウィンドウをずらしながら、２つの時系列データの類似度を演算する例である。図５２の例において、変化点テーブルは、順番の項目を含む。順番は、比較対象の変化点の順番を示す。
【０２１３】
また、具体例２では、図５２の例に示される差分処理テーブルが用いられる。差分処理テーブルは、時間差と一致数と後端の一致と前端の一致と次の後端と次の前端との項目を含む。
【０２１４】
時間差は、差分処理の対象となる時間差を示す。一致数は、時間差に応じた２つの時系列データの一致数を示す。後端の一致は、ウィンドウ外の後端における２つの時系列データの大小関係が一致するか否かを示す。前端の一致は、ウィンドウ内の前端における２つの時系列データの大小関係が一致するか否かを示す。
【０２１５】
次の後端は、ウィンドウがずらされた後に、次にウィンドウの後端から出る変化点を示す。次の前端は、ウィンドウがずらされた後に、次にウィンドウに入る変化点を示す。
【０２１６】
図５３の例では、計数部１３は、データ１の変化点「１−」とデータ２の変化点「１−」とを対象として、大小関係の一致数をカウントする。データ１は時間「１」で大小関係が「−」に反転する。データ２も時間「１」で大小関係が「−」に反転する。
【０２１７】
よって、データ１とデータ２との大小関係は一致するため、計数部１３は、一致数を加算する。これにより、一致数は「１」になる。差分処理部１５は、差分処理テーブルの一致数を「１」にする。
【０２１８】
データ１の変化点「１−」およびデータ２の変化点「１−」は、変化点テーブルにおいて、オフセットが「１」であるため、ウィンドウ外の後端に位置する。また、２つの変化点の大小関係は「−」である。
【０２１９】
従って、差分処理部１５は、後端の一致の項目を「○」にする。また、データ１の変化点「１−」およびデータ２の変化点「１−」は、ウィンドウがずらされると、ウィンドウから出る。
【０２２０】
差分処理部１５は、上記２つの変化点を示す情報を変化点テーブルのうち、次の項目に格納する。図５３の例では、上記の変化点を示す情報は、データ番号と順番と到達時間との情報を含む。
【０２２１】
データ番号は、時系列データを特定する番号を示す。例えば、「Ｄ１」はデータ１を示す。順番は、変化点テーブルの順番を示す。
【０２２２】
括弧内の到達時間は、変化点がウィンドウから出るまでの時間を示す。ウィンドウが１回ずらされると、時刻が１つ後ろにずれる。例えば、到達時間が「１」の場合、ウィンドウが１回ずらされると、変化点はウィンドウから出ることを示す。
【０２２３】
例えば、図５３の例において、変化点を示す情報「Ｄ１−１（１）」は、該変化点はデータ１の変化点であることを示す。また、該変化点の順番は「１」であることを示し、ウィンドウが１回ずらされると、該変化点はウィンドウから出ることを示す。
【０２２４】
次に、データ２の比較の対象が変化点「２＋」に移る。ウィンドウ内の２つの時系列データの大小関係が一致するか否かを判定する処理は、具体例１と同様である。図５４の例に示されるように、一致数は変化しない。
【０２２５】
また、ウィンドウがずらされていないことから、後端の一致および次の後端についても変化はない。よって、図５４の例に示されるように、差分処理テーブルの内容に変化はない。
【０２２６】
次に、図５５の例に示されるように、データ１の比較の対象が変化点「３＋」に移り、データ２の比較の対象が変化点「３−」に移る。この場合、２つの変化点のオフセットが同じであるため、データ１の変化点とデータ２の変化点とが共に次に移る。
【０２２７】
ウィンドウはずらされておらず、一致数も変化しないことから、差分処理テーブルの内容に変化はない。
【０２２８】
次に、図５６の例に示されるように、データ１の比較の対象が変化点「７−」に移る。ウィンドウはずらされておらず、一致数も変化しないことから、差分処理テーブルのうち、時間差、一致数、後端の一致および次の後端の項目の情報は変化しない。
【０２２９】
差分処理部１５は、データ１の比較の対象の変化点「７−」がウィンドウから出たため、データ１の前端とデータ２の前端とが一致するか否かを判定する。データ２はウィンドウの前端に到達していないため、差分処理部１５は、差分処理テーブルのうち前端の一致の項目を「×」とする。
【０２３０】
また、ウィンドウがずらされた場合、データ１の変化点「７−」がウィンドウに入る。次の前端に格納される変化点を示す情報は、データ番号と順番と到達時間との情報を含む。これらの情報は、次の後端に格納される変化点を示す情報と同様である。
【０２３１】
データ１の変化点「７−」の場合、データ番号は「Ｄ１」であり、順番は「３」であり、到達時間は「１」である。従って、差分処理部１５は、差分処理テーブルのうち次の前端の項目に「Ｄ１−３（１）」という情報を格納する。
【０２３２】
次に、図５７の例に示されるように、データ２の比較の対象が変化点「８＋」に移る。ウィンドウはずらされておらず、一致数も変化しないことから、差分処理テーブルのうち、時間差、一致数、後端の一致および次の後端の項目の情報は変化しない。
【０２３３】
ウィンドウの前端におけるデータ１の大小関係は「＋」であり、データ２の大小関係は「−」である。よって、ウィンドウの前端において、データ１とデータ２とは大小関係が一致しない。差分処理部１５は、差分処理テーブルのうち前端の一致の項目を「×」とする。
【０２３４】
また、ウィンドウが２回ずらされた場合、データ２の変化点「８＋」はウィンドウに入る。よって、差分処理部１５は、差分処理テーブルのうち、次の前端の項目に「Ｄ２−４（２）」を追加する。
【０２３５】
以上により、差分処理部１５は、時間差が「１」の場合の差分処理テーブルを生成する。差分処理部１５は、時間差が「１」の場合と同様の処理を行い、時間差が「２」から「６」の場合の差分処理テーブルを生成する。
【０２３６】
図５８は、生成された差分処理テーブルの一例を示す。計数部１３は、時間差「１」から「６」までの大小関係の一致数を合計し、一致数Ｐ（Ｐ＝４）を得る。演算部１４は、上述した式（Ａ）に、「Ｐ＝４」、「ｎ＝７」を当て嵌めて演算し、類似度（相関値）ｔ（ｔ＝−０．６２）を得る。
【０２３７】
差分処理部１５は、時間差「１」から「６」の差分処理テーブルに基づいて、前端の一致の項目の「○」の数を合計する。図５８の例の場合、前端の一致の「○」の数の合計は「１」である。また、差分処理部１５は、後端の一致の項目の「○」の数を合計する。図５８の例の場合、後端の一致の「○」の数の合計は「４」である。
【０２３８】
差分処理部１５は、前端の一致の「○」の数の合計から後端の一致の「○」の数の合計を減算する。図５８の例の場合、減算結果は「−３」になる。この減算結果が、一致数の変化量（図５８以降、一致数の変化と表記することがある）である。
【０２３９】
ウィンドウがずらされた際に、大小関係の変化点がウィンドウから出入りしなければ、一致数の変化量は一定である。一方、ウィンドウがずらされた際に、大小関係の変化点がウィンドウから出入りする場合、一致数の変化量は変化する。
【０２４０】
次に、具体例２における管理テーブルの例について説明する。図５９の例に示される差分処理テーブルは、図５８の例で示した差分処理テーブルのうち、一致数と後端の一致数と前端の一致との項目を省略して表したテーブルである。
【０２４１】
管理テーブルは、到達時間と後端と前端との項目を含む。管理テーブルは、ウィンドウに対する変化点の位置関係を示すテーブルである。後端の項目には、後端に到達するまでの時間ごとに、変化点を示す情報が格納される。前端の項目には、前端に到達するまでの時間ごとに、変化点を示す情報が格納される。
【０２４２】
差分処理部１５は、差分処理テーブルの次の後端および次の前端に格納された変化点を示す情報と時間差とに基づいて、管理テーブルを生成する。管理テーブルに格納される変化点を示す情報は、時間差とデータ番号と順番との情報を含む。
【０２４３】
例えば、図５９の例では、時間差「４」における次の後端の項目の変化点を示す情報は「Ｄ１−３（３）」である。このうち、「Ｄ１」はデータ番号を示し、「３」は順番を示し、括弧内の「３」は到達時間を示す。
【０２４４】
差分処理部１５は、差分処理テーブルから各変化点を抽出し、括弧内の到達時間に応じて、各変化点を管理テーブルに格納する。例えば、次の前端の変化点を示す情報が「Ｄ１−３（３）」である場合、差分処理部１５は、管理テーブルの到達時間が「３」の前端の項目に該変化点を示す情報を格納する。
【０２４５】
図５９の例では、差分処理部１５は、変化点を示す情報を、時間差とデータ番号と順番とを含む情報に変換して、管理テーブルに格納する。例えば、上述した次の前端の変化点を示す情報が「Ｄ１−３（３）」の場合、時間差は「４」、データ番号は「Ｄ１」、順番は「３」である。
【０２４６】
差分処理部１５は、管理テーブルのうち、到達時間「３」の前端の項目に「４−Ｄ１−３」の形式で変化点を示す情報を格納する。差分処理部１５は、差分処理テーブルに格納された各変化点を示す情報について同様の処理を行い、図５９の例に示すような管理テーブルを記憶部１１に記憶する。
【０２４７】
図６０の例は、データ１およびデータ２の双方のウィンドウがずらされた場合の例を示す。この場合、差分処理部１５は、図５９の例の管理テーブルの到達時間を１つ繰り上げ、データ１およびデータ２のオフセットをインクリメントする。図６０の例の場合、データ１およびデータ２のオフセットの値は「１」になる。
【０２４８】
図６１は、差分処理部１５が管理テーブルを更新する一例を示す。データ１のウィンドウがずれることにより、時間差「１」における変化点「１−」（管理テーブルにおいては、「１−Ｄ１−１」で表される）は、ウィンドウの後端から出る。
【０２４９】
時間差「１」における変化点「１−」がウィンドウから出たため、差分処理部１５は、差分処理テーブルの時間差「１」におけるウィンドウの後端の一致を反転する。図６１の例の場合、時間差「１」におけるウィンドウの後端の一致は「○」であったため、差分処理部１５は、「○」を「×」に反転する。
【０２５０】
上述したように、一致数の変化量は、差分処理テーブルにおける前端の一致の「○」の数の合計値から後端の一致の「○」の数の合計値を減算した値である。ウィンドウがずらされる前の一致数の変化量は「−３」であった。
【０２５１】
後端の一致における「○」が「×」に反転した場合、一致数の変化量は増える。図６１の例の場合、時間差「１」における後端の一致が「×」に変化したため、一致数の変化量は１つ増える。
【０２５２】
時間差「１」における変化点「１−」の次の変化点は「３＋」である。この変化点「３＋」が次の後端になる。差分処理部１５は、この変化点「３＋」を管理テーブルに格納する。
【０２５３】
変化点「３＋」はデータ１の変化点であり、時間差は「１」であり、順番は「２」である。差分処理部１５は、変化点「３＋」を示す情報を「１−Ｄ１−２」の形式で管理テーブルの後端に格納する。
【０２５４】
図６２は、データ１の時間差「６」における変化点「２＋」に着目した場合の管理テーブルの更新の例を示す。ウィンドウがずれることにより、データ１の時間差「６」における変化点「２＋」（管理テーブルにおいては、「６−Ｄ１−２」で表される）は、ウィンドウの前端から入る。
【０２５５】
ウィンドウがずれると、時間差「６」の変化点「−１」は、ウィンドウから出る。従って、データ１の時間差「６」における次の後端は、変化点「２＋」になる。また、該変化点「２＋」がウィンドウの後端に到達するまでの時間（到達時間）は「１」である。
【０２５６】
差分処理部１５は、管理テーブルの前端から後端に「６−Ｄ１−２」を移動する。また、データ１の時間差「６」における変化点「２＋」がウィンドウに入ったため、差分処理部１５は差分処理テーブルの時間差「６」における前端の一致を反転させる。
【０２５７】
時間差「６」における前端の一致が「×」に反転されたため、一致数の変化量は１つ減る。従って、一致数の変化量は「−３（＝−３＋１−１）」になる。
【０２５８】
差分処理部１５は、管理テーブルのうち到達時間がゼロの全ての変化点について、上述した処理を行う。図６３は、到達時間がゼロの全ての変化点について処理された管理テーブルの例を示す。差分処理部１５は、処理を行った変化点を管理テーブルから削除する。
【０２５９】
差分処理部１５は、差分処理テーブルの後端の一致および前端の一致の更新を行う。図６３の例において、例えば、時間差「１」の後端の一致は、２回反転されるため、更新されない。
【０２６０】
ウィンドウがずらされることにより、データ１の時間差「１」の変化点「１−」は、ウィンドウから出る。これにより、差分処理テーブルのうち、該変化点の後端の一致は反転される。
【０２６１】
また、データ２の時間差「１」の変化点「１−」も、ウィンドウがずらされることにより、ウィンドウから出る。これにより、差分処理テーブルのうち、該変化点の後端の一致は反転される。
【０２６２】
従って、差分処理テーブルのうち、時間差「１」の後端の一致は、２回反転されることになるため、この場合、差分処理部１５は、時間差「１」の後端の一致を更新しない。
【０２６３】
図６３の例の場合、差分処理テーブルのうち、前端の一致の「○」の数の合計と後端の一致の「○」の数の合計とは変化しない。よって、ウィンドウがずらされた後（更新後）の一致数の変化量は「−３」になる。
【０２６４】
図６４の例に示されるように、差分処理部１５は、ウィンドウがずらされる前の一致数「４」に、一致数の変化量「−３」を加算する。これにより、ウィンドウがずらされた後のデータ１とデータ２との大小関係の一致数は「１（＝４−３）」になる。
【０２６５】
演算部１４は、一致数Ｐ（Ｐ＝１）、項目数（ｎ＝７）を上述した式（Ａ）に当て嵌めて演算し、演算結果として、ウィンドウがずらされた後の類似度「ｔ＝−０．９０」を得る。
【０２６６】
図６５は、次に、ウィンドウがずらされた場合における類似度（相関値）の演算の例を示す。ウィンドウがずらされたため、変化点データのオフセットは１つ増える。ウィンドウがずらされる前の一致数の変化量は「−３」である。
【０２６７】
差分処理テーブルにおいて、時間差「３」における前端の一致と、時間差「１」における前端の一致とが反転する。両者は、逆方向に反転するため、前端の一致のみに着目すると、一致数の変化量はゼロである。
【０２６８】
差分処理テーブルの後端の一致において、時間差「１」、「４」、「５」および「６」の４つが、「○」から「×」に変化する。よって、一致数の変化量は４つ増える。ウィンドウがずらされる前の一致数の変化量は「−３」であったため、ウィンドウがずらされた後の一致数の変化量は「１（＝−３＋４）」になる。
【０２６９】
差分処理部１５は、ウィンドウがずらされる前の一致数は「１」に一致数の変化量「１」を加算して、一致数Ｐ（Ｐ＝２）を得る。
【０２７０】
演算部１４は、一致数Ｐ（Ｐ＝２）、項目数ｎ（ｎ＝７）を上述した式（Ａ）に当て嵌めて類似度ｔの演算を行う。これにより、演算部１４は、類似度「ｔ＝−０．８１」を得る。
【０２７１】
図６６は、次に、ウィンドウがずらされた場合における類似度の演算の例を示す。差分処理部１５は、ウィンドウがずらされたため、データ１およびデータ２のオフセットを「３」に更新する。
【０２７２】
図６６の例において、差分処理テーブルの時間差「１」および「４」における前端の一致が「○」に反転している。
【０２７３】
よって、差分処理部１５は、ウィンドウがずらされる前の変化量「１」に「２」を加算して、一致数の変化量「３」を得る。また、ウィンドウがずらされる前の一致数は「２」であったため、差分処理部１５は、「２」に「３」を加算して、一致数Ｐ（Ｐ＝５）を得る。
【０２７４】
演算部１４は、一致数Ｐ（Ｐ＝５）、項目数ｎ（ｎ＝７）を上述した式（Ａ）に当て嵌めて類似度ｔの演算を行う。これにより、演算部１４は、類似度「ｔ＝−０．５２」を得る。ウィンドウは、データ１およびデータ２の末尾までずらされたため、処理は完了する。
【０２７５】
＜具体例３＞
次に、類似度の演算を行う対象である２つの時系列データのうち、片方の時系列データのウィンドウを固定し、他方の時系列データのウィンドウをずらす場合における類似度の演算の例について説明する。
【０２７６】
図６７の例において、データ１の変化点データのうち、時間「３」から「９」までがウィンドウ範囲であるとする。図６７の例に示されるように、差分処理部１５は、オフセット「２（＝時間「３」−時間「１」）」として、以下の処理を行う。
【０２７７】
データ１のウィンドウは固定される。時間差「１」の変化点「１−」は、ウィンドウに入っていない。変化点テーブルのうち、次の変化点「３＋」はウィンドウ内のうち後端に位置する。よって、該変化点「３＋」のアンカーは、タイプＢである。
【０２７８】
差分処理部１５は、アンカーに関するデータ（以下、アンカーデータ）に上記の変化点「３＋」の情報を追加する。差分処理部１５は、変化点「３＋」のオフセットである括弧内の「１」と、タイプＢであることを特定する情報と、大小関係が「＋」である情報とをアンカーデータに追加する。図６８の例では、この情報は「Ｂ１＋」である。
【０２７９】
図６９の例において、変化点「７−」は、ウィンドウ内のうち後端ではない場所に位置する。よって、該変化点「７−」のアンカーは、タイプＣであり、オフセットは「５」である。差分処理部１５は、アンカーデータに「Ｃ５−」を追加する。
【０２８０】
差分処理部１５は、時間差「１」について、ウィンドウの前端に変化点があるかを判定する。変化点テーブルのうち最後の変化点は「７−」である。よって、図７０の例の場合、ウィンドウの前端に変化点はない。
【０２８１】
この場合、上述したように、差分処理部１５は、変化点を追加する。ウィンドウの前端の時間は「１０」であるため、オフセットは「７」である。また、時間「１０」における大小関係は「＋」である。よって、差分処理部１５は、アンカーデータに「Ａ７＋」を追加する。
【０２８２】
図７１は、時間差「１」から「６」までのアンカーデータの例を示す。差分処理部１５は、時間差「１」の場合と同様の処理を行い、時間差「２」から「６」までのアンカーデータを生成する。時間差ごとのアンカーデータは、データ１における固定されたウィンドウの情報である。
【０２８３】
次に、データ１とデータ２との大小関係の一致数の例について説明する。具体例３では、データ１とデータ２とを比較する場合、差分処理部１５は、データ１についてはアンカーテーブルを用い、データ２については変化点テーブルを用いる。
【０２８４】
図７１の例の場合、データ２のウィンドウ範囲は、時間「１」から「７」までである。一方、データ１のウィンドウ範囲は時間「３」から「９」までである。上述したように、差分処理部１５は、オフセット「２」を考慮して、データ１のアンカーデータを生成する。
【０２８５】
図７２の例では、比較の対象は、データ１については、アンカー「Ｂ１＋」であり、データ２については、変化点「１−」である。アンカー「Ｂ１−」は、上述したように、データ１における変化点「３」に対応する。
【０２８６】
図７２の例において、差分処理部１５は、アンカーテーブルを生成する。アンカーテーブルは、時間差に応じた、一致数とアンカーの一致関係と次にアンカーに到達する変化点との情報を含む。
【０２８７】
アンカーの一致関係は、比較対象であるデータ１のアンカーとデータ２の変化点との大小関係が一致するか否かを示す。図７２の例では、アンカーの一致関係は、アンカーの順番ごとに、一致するか否かを示す。
【０２８８】
アンカー「Ｂ１＋」と変化点「１−」とは大小関係が逆である。アンカー「Ｂ１−」においてデータ１とデータ２との大小関係が一致しないため、差分処理部１５は、アンカーテーブルの１番を「×」にする。また、アンカー「Ｂ１＋」と変化点「１−」との大小関係が一致しないため、計数部１３は、大小関係の一致数を加算しない。
【０２８９】
図７３の例は、比較の対象が、データ１のアンカー「Ｂ１＋」とデータ２の変化点「２＋」とである場合を示す。データ１の変化点「１＋」からデータ２の変化点「２＋」までの大小関係は「＋」であり、データ１のアンカー「Ｂ１＋」の大小関係と一致する。よって、差分処理部１５は、大小関係の一致数を加算する。
【０２９０】
データ２の変化点「２＋」は、ウィンドウがずらされると、ウィンドウ内の後端に位置する。差分処理部１５は、アンカーテーブルのうち「次にアンカーに到達する変化点」に、データ２の変化点「２＋」の情報を格納する。
【０２９１】
差分処理部１５は、データ２の変化点の順番を示す情報と、該変化点がアンカー（この場合は、ウィンドウ内の後端）に到達するまでにウィンドウがずらされる回数（時間）の情報と、対応するアンカーの順番を示す情報とを、アンカーテーブルに格納する。
【０２９２】
図７３の例では、データの変化点「２＋」の順番を示す情報は「２」である。該変化点「２＋」はウィンドウが１回ずらされると、アンカーに到達する。対応するアンカーは「Ｂ１＋」であるため、対応するアンカーの順番を示す情報は「１」である。
【０２９３】
差分処理部１５は、アンカーテーブルのうち「次にアンカーに到達する変化点」に、変化点「２＋」を示す情報として、「２（１）−１」を格納する。括弧内の値は、上記の変化点がアンカーに到達するまでにウィンドウがずらされる回数を示す。
【０２９４】
図７４の例は、比較の対象が、データ１のアンカー「Ｂ１＋」とデータ２の変化点「３−」とである場合を示す。データ１の変化点「２＋」からデータ２の変化点「３−」までの大小関係は「−」であり、データ１のアンカー「Ｂ１＋」の大小関係と一致しない。よって、差分処理部１５は、大小関係の一致数を加算しない。
【０２９５】
図７５の例に示されるように、差分処理部１５は、比較の対象を、データ１のアンカー「Ｃ５−」とデータ２の変化点「３−」とに移す。データ１の変化点「２＋」からデータ２の変化点「３−」までの大小関係は「−」であり、データ２のアンカー「Ｃ５−」の大小関係と一致する。よって、差分処理部１５は、大小関係の一致数を加算する。
【０２９６】
また、データ１のアンカー「Ｃ５−」において、該アンカー「Ｃ５−」と変化点「３−」とは大小関係が一致する。よって、差分処理部１５は、「アンカーの一致関係」の２番目を「○」にする。
【０２９７】
図７６の例に示されるように、差分処理部１５は、比較の対象を、データ１のアンカー「Ａ７＋」とデータ２の変化点「３−」とに移す。データ１の変化点「２＋」からデータ２の変化点「３−」までの大小関係は「−」であり、データ１のアンカー「Ｂ１＋」の大小関係と一致する。よって、差分処理部１５は、大小関係の一致数を加算する。
【０２９８】
また、データ１のアンカー「Ａ７＋」において、該アンカー「Ａ７＋」と変化点「３−」とは大小関係が一致しない。よって、差分処理部１５は、「アンカーの一致関係」の３番目を「×」にする。
【０２９９】
図７７の例に示されるように、ウィンドウがずらされると、データ２の変化点「８＋」はウィンドウの前端に位置する。差分処理部１５は、アンカーテーブルのうち「次にアンカーに到達する変化点」に、データ２の変化点「８＋」の情報を格納する。
【０３００】
データ２の変化点「８＋」の順番を示す情報は「４」であり、該変化点がアンカー（この場合はウィンドウの前端）に到達するまでにウィンドウがずらされる回数は「１」であり、対応するアンカーの順番は「３」である。よって、差分処理部１５は、「次にアンカーに到達する変化点」に「４（１）−３」を追加する。
【０３０１】
以上により、時間差「１」についての処理が終了する。差分処理部１５は、時間差「１」と同様の処理を、時間差「２」から「６」について行う。図７８は、時間差ごとのアンカーテーブルの一例を示す。
【０３０２】
図７９の例において、差分処理部１５は、アンカーテーブルの「次にアンカーに到達する変化点」に格納された各変化点の情報を、アンカーに到達するまでにウィンドウがずらされる回数順（時間順）に管理する。
【０３０３】
差分処理部１５は、アンカーテーブルのうち「次にアンカーに到達する変化点」の各変化点の情報のうち、ウィンドウがずらされる回数を到達時間として、到達時間順に各変化点の情報を管理テーブルに格納する。
【０３０４】
図７９の例では、差分処理部１５は、各変化点の情報を「時間差―変化点の順番―アンカーの順番」の形式で管理テーブルに格納する。例えば、アンカーテーブルの「次にアンカーに到達する変化点」に格納された情報が「２（１）−１」の場合、差分処理部１５は、「１−２−１」の形式で該変化点の情報を管理テーブルに格納する。
【０３０５】
これにより、差分処理部１５は、管理テーブルを用いて、ウィンドウがずらされた場合における変化点の到達時間を管理する。
【０３０６】
図７９の例のアンカーテーブルにおいて、一致数の合計は「８（＝３＋３＋２）」である。演算部１４は、一致数Ｐ（Ｐ＝８）、項目数ｎ（ｎ＝７）を上述した式（Ａ）に当て嵌めて演算を行い、類似度ｔ「ｔ＝−０．２３」を得る。
【０３０７】
上述したように、類似度の演算を行う対象の２つの時系列データうち、片方の時系列データのウィンドウを固定し、他方の時系列データのウィンドウをずらす場合、アンカーのタイプごとに一致数の変化量および変化量の差分に重みが付与される。
【０３０８】
例えば、時間差「１」の「Ｂ１＋×」は、アンカー「Ｂ１＋」に対応するデータ２の変化点「１−」と大小関係が一致しないことを示す。従って、「Ｂ１＋×」は、タイプＢであり、且つ大小関係が不一致であることを示すため、重みはゼロである。
【０３０９】
また、時間差「１」の「Ｃ５−○」は、アンカー「Ｃ５−」に対応する変化点「３−」と大小関係が一致することを示す。従って、「Ｃ５−○」は、タイプＣであり、且つ大小関係が一致することを示すため、重みは「−１」である。
【０３１０】
差分処理部１５は、時間差ごとのアンカーデータに重み付けを行い、全てのアンカーの重みを合計する。図８０の例の場合、重みの合計は「−２」である。この重みの合計が一致数の変化量になる。
【０３１１】
上述したように、ウィンドウがずらされる前の大小関係の一致数は「８」である。差分処理部１５は、ウィンドウがずらされる前の大小関係の一致数に一致数の変化量を加算する。これにより、ウィンドウがずらされた後（更新後）の大小関係の一致数Ｐは、「Ｐ＝８＋（−２）＝６」となる。
【０３１２】
演算部１４は、一致数Ｐ（Ｐ＝６）、項目数ｎ（ｎ＝７）を上述した式（Ａ）に当て嵌めて演算を行い、類似度ｔ「ｔ＝−０．４２」を得る。
【０３１３】
図８１は、データ２のウィンドウがずらされた場合の一例を示す。ウィンドウがずらされたため、差分処理部１５は、データ２のオフセットを１つ増やす。ウィンドウがずらされたことにより、管理テーブルの到達時間がずらされる。
【０３１４】
例えば、ウィンドウがずらされたことにより、データ２の変化点「２＋」は、アンカーに到達する。該変化点「２＋」は、管理テーブルでは、「１−２−１」として管理される。
【０３１５】
差分処理部１５は、管理テーブルにおいて「１−２−１」が到達時間ゼロに達したため、「１−２−１」に対応するアンカー「Ｂ１−」の大小関係の一致を反転させる。これにより、時間差「１」におけるアンカー「Ｂ１−」は「○」に反転される。
【０３１６】
差分処理部１５は、アンカー「Ｂ１−」の大小関係が「×」から「○」に反転したため、一致数の変化を１つ減らす。
【０３１７】
また、データの変化点「２＋」の次の変化点「３−」は、アンカー「Ｂ１＋」からアンカー「Ｃ５−」の間に存在するため、差分処理部１５は、変化点「３−」に関する情報を管理テーブルに追加する。データ２の変化点「３−」は、管理テーブルでは、「１−３−１」として管理される。
【０３１８】
図８２の例において、管理テーブルの到達時間ゼロのうち「１−４−３」は、上述したように、データ２の変化点「８＋」であることを示す。この変化点「８＋」は、アンカー「Ａ７＋」に対応する。
【０３１９】
従って、差分処理部１５は、アンカー「Ａ７＋」の大小関係を「○」に反転する。差分処理部１５は、アンカー「Ａ７＋」の大小関係が「×」から「○」に反転したため、一致数の変化量を１つ減らす。
【０３２０】
データ２の変化点「８＋」は、ウィンドウが２回ずらされると、アンカー「Ｃ５−」に達する。アンカー「Ｃ５−」を示す順番は「２」である。よって、差分処理部１５は、データ２の変化点「８＋」を示す管理テーブルの「１−４−３」を「１−４−２」として、到達時間「２」に格納する。
【０３２１】
また、差分処理部１５は、データ２の変化点「９−」を示す「１−５−３」を管理テーブルに追加する。
【０３２２】
図８３は、全ての時間差について、差分処理部１５が処理した例を示す。差分処理部１５は、データ１の全てのアンカーについて、タイプごとの重み付けに基づいて、変化量の差分を求める処理を行い、「−２」を得る。
【０３２３】
ウィンドウがずれる前の一致数の変化量は「−２」であったため、一致数の変化量は「−４（＝（−２）＋（−２））」となる。ウィンドウがずれる前の大小関係の一致数は「６」であったため、ウィンドウがずれた後の一致数Ｐは「Ｐ＝６−４＝２」になる。
【０３２４】
演算部１４は、一致数Ｐ（Ｐ＝２）、項目数ｎ（ｎ＝７）を上述した式（Ａ）に当て嵌めて演算を行い、類似度ｔ「ｔ＝−０．８０」を得る。
【０３２５】
また、差分処理部１５は、到達時間ゼロの変化点の情報を削除し、上述した処理を行い、管理テーブルを更新する。
【０３２６】
図８４は、次にウィンドウがずれた場合の例を示す。差分処理部１５は、アンカーデータに基づいて、タイプごとの重み付けを行い、変化量の差分「５」を得る。ウィンドウがずれる前の一致数の変化量は「−４」であったため、差分処理部１５は、「−４」に「５」を加算して、一致数の変化量「１」を得る。
【０３２７】
ウィンドウがずれる前の一致数は「２」であったため、差分処理部１５は、これに一致数の変化量「１」を加算して、一致数Ｐ（Ｐ＝３）を得る。演算部１４は、一致数Ｐ（Ｐ＝３）、項目数ｎ（ｎ＝７）を上述した式（Ａ）に当て嵌めて演算を行い、類似度ｔ「ｔ＝−０．７１」を得る。
【０３２８】
図８４の例に示されるように、データ２の期間は時間「１」から「１０」までである。ウィンドウは、データ２の期間の末尾まで移動したため、具体例３の処理が終了する。
【０３２９】
＜他の値を用いた一致数の例＞
次に、上述した各例とは異なる値を用いた２つの時系列データの大小関係の一致数の例について説明する。図８５の例の変化点テーブルに示されるように、オフセットおよび変化点の値は、上述した各例とは異なる。「Ｄ１」はデータ１であり、「Ｄ２」はデータ２である。
【０３３０】
図８５の例において、２つの時系列データの期間は、時間「１」から「２０」までとする。従って、データ１およびデータ２の期間は「２０」である。また、図８５は、時間差「４」の場合の例を示す。この場合、ウィンドウ範囲は「１」から「１６」になる。
【０３３１】
図８６の例に示されるように、計数部１３は、変化点テーブルのうち、データ１の始点のオフセット補正後の位置を求める。オフセット補正後の位置は、上述したインデックスである。図８６の例の場合、オフセット補正後の位置は「−３＝４−７」である。
【０３３２】
オフセット補正後の位置が「−」であるため、データ１の変化点「４＋」はウィンドウに入っていない。従って、この時点では、計数部１３は、一致数を加算しないため、一致数はゼロである。
【０３３３】
計数部１３は、オフセットの値が小さい変化点から順番に比較の対象を移す。図８７の例に示されるように、データ１の変化点「１９−」のオフセットは「１２」であり、データ２の変化点「８−」のオフセットは「６」である。
【０３３４】
従って、計数部１３は、データ１の変化点「４＋」とデータ２の変化点「８−」とを比較の対象として、大小関係の一致数を求める。データ１におけるオフセット補正後の位置「−３」以降の大小関係は「＋」である。また、データ２におけるオフセット補正後の位置「６」以降の大小関係は「−」であり、「５」以前の大小関係は「＋」である。
【０３３５】
よって、オフセット補正後の位置「１」から「５」までの範囲の大小関係は「＋」であり、一致する。計数部１３は、大小関係が一致する数をカウントする。従って、一致数は、「５」になる。
【０３３６】
図８８の例に示されるように、次にオフセット補正後の値が最も小さい変化点は「１９−」である。データ１は、ウィンドウ範囲に対して、オフセット補正後の位置が「１１」より前の大小関係は「＋」である。データ２は、オフセット補正後の位置が「７」から「１１」までの間における大小関係は「−」である。
【０３３７】
よって、オフセット補正後の位置が「７」から「１１」までの間におけるデータ１とデータ２とは不一致である。一方、データ１は、オフセット補正後の位置「１２」以降、大小関係が「＋」になる。
【０３３８】
このため、オフセット補正後の位置「１２」において、データ１とデータ２との大小関係が一致する。計数部１３は、一致数をカウントして、一致数「１」を得る。ここまでの、一致数の合計は「６＝１＋５」である。
【０３３９】
図８９の例に示されるように、次にオフセット補正後の値が最も小さい変化点はデータ１の「２２＋」である。データ１は、オフセット補正後の位置「１３」から「１４」の大小関係は「−」であり、「１５」以降の大小関係は「＋」である。
【０３４０】
データ２は、オフセット補正後の位置「６」以降の大小関係は「−」である。よって、データ１とデータ２とは、オフセット補正後の位置「１３」から「１４」において大小関係が一致する。従って、計数部１３は、一致数をカウントして、一致数「２」を得る。ここまでの、一致数の合計は「８＝６＋２」である。
【０３４１】
図９０の例に示されるように、次にオフセット補正後の値が最も小さい変化点はデータ２の「２３＋」である。データ１は、オフセット補正後の位置「１５」以降の大小関係は「＋」である。
【０３４２】
データ２は、オフセット補正後の位置「６」から「２０」までの大小関係は「−」である。ウィンドウ範囲は「１」から「１６」であるため、この場合の比較の対象は、オフセット補正後の位置「１５」から「１６」になる。
【０３４３】
データ１のオフセット補正後の位置「１５」から「１６」の大小関係は「＋」であり、データ２のオフセット補正後の位置「１５」から「１６」の大小関係は「−」である。よって、この範囲でのデータ１とデータ２との大小関係は一致しない。
【０３４４】
従って、計数部１３がカウントする一致数はゼロである。ここまでの一致数の合計は「８＝８＋０」である。
【０３４５】
以上のようにして、計数部１３は、ウィンドウ範囲「１」から「１６」におけるデータ１とデータ２との一致数をカウントする。
【０３４６】
＜実施形態の処理の流れを示すフローチャートの一例＞
次に、実施形態の処理の流れを示すフローチャートについて説明する。図９１の例に示されるように、データ処理装置１は、類似度の演算の対象となる時系列データおよび該時系列データのうち比較対象となるウィンドウ（期間）を決定する（ステップＳ１）。以下、時系列データを系列と称することがある。
【０３４７】
実施形態では、検出部１２は、対象となる時系列データを記憶部１１から読み出す。少なくとも２つの時系列データが記憶部１１から読み出される。検出部１２は、対象となる全ての時系列データについてウィンドウの範囲内で変化点を検出する（ステップＳ２）。以下、変化点を検出する処理を処理Ａと称する。
【０３４８】
演算部１４が、対象となる全ての時系列データについて類似度の演算を行った場合（ステップＳ３でｎｏ）、処理は終了する。
【０３４９】
差分処理部１５は、比較対象の２つの時系列データに設定された双方のウィンドウが固定されるか、双方のウィンドウがずらされるか、または片方のウィンドウがずらされるかを判定する（ステップＳ４）。
【０３５０】
差分処理部１５は、双方のウィンドウをずらすことができるか、片方のウィンドウをずらすことができるか、または双方のウィンドウをずらすことができないか、の何れかに基づいて、ステップＳ４の判定を行ってもよい。
【０３５１】
双方のウィンドウが固定された場合、ウィンドウがずらされることなく、検出された変化点に基づいて、類似度が演算される（ステップＳ５）。ステップＳ５の処理は、上述した具体例１の処理（以下、処理Ｂと称する）である。
【０３５２】
双方のウィンドウがずらされる場合、差分処理部１５が双方のウィンドウをずらしながら差分処理を行い、演算部１４により類似度が演算される（ステップＳ６）。ステップＳ６の処理は、上述した具体例２の処理（以下、処理Ｃと称する）である。
【０３５３】
片方のウィンドウがずらされる場合、差分処理部１５が片方のウィンドウをずらしながら差分処理を行い、演算部１４により類似度が演算される（ステップＳ７）。ステップＳ７の処理は、上述した具体例３の処理（以下、処理Ｄと称する）である。
【０３５４】
処理Ａ（変化点を検出する処理）について、図９２のフローチャートを参照して説明する。検出部１２は、対象となる各時系列データのうち、変化点を検出する処理を行っていない時系列データがあるかを判定する（ステップＳ１１）。
【０３５５】
全ての時系列データについて変化点を検出する処理が済んでいる場合（ステップＳ１１でｎｏ）、処理は終了する。変化点を検出する処理が済んでいない時系列データが存在する場合（ステップＳ１１でｙｅｓ）、検出部１２は、該時系列データを記憶部１１から取得し、該時系列データの期間を得る（ステップＳ１２）。
【０３５６】
検出部１２は、取得された時系列データのうち単調区間（単調増加区間および単調減少区間）を検出する（ステップＳ１３）。検出部１２は、変数ｉ（ｉは整数）に「１」を代入する。変数ｉは、時間差を示す。
【０３５７】
検出部１２は、変数ｉが時系列データの期間未満であるかを判定する（ステップＳ１５）。変数ｉが時系列データの期間以上である場合（ステップＳ１５でｎｏ）、処理はステップＳ１１に戻る。
【０３５８】
変数ｉが時系列データの期間未満である場合（ステップＳ１５でｙｅｓ）、検出部１２は、上記の単調区間と変数ｉとに基づいて、上述したブロックを決定する（ステップＳ１６）。そして、検出部１２は、最初の変化点の値（初期値）を検出する（ステップＳ１７）。
【０３５９】
検出部１２は、未処理のブロックが存在するかを判定する（ステップＳ１８）。未処理のブロックが存在する場合（ステップＳ１８でｙｅｓ）、該ブロックが同じ単調区間に含まれるかを判定する（ステップＳ１９）。
【０３６０】
該ブロックが同じ単調区間に含まれない場合（ステップＳ１９でｎｏ）、検出部１２は、該ブロックが、「値の範囲が分離されているブロック」であるかを判定する（ステップＳ２０）。
【０３６１】
該ブロックが「値の範囲が分離されているブロック」でない場合（ステップＳ２０でｎｏ）、該ブロックは変化点検出の対象のブロックである。この場合、検出部１２は、ブロックの長さが長いかを判定する（ステップＳ２１）。
【０３６２】
ブロックの長さは、時系列データの範囲である。ブロックの長さが長いか否かは、任意に設定されてよい。例えば、ブロックの長さに閾値が設定され、ブロックの長さが該閾値を超えた場合に、ブロックの長さが長いと判定されてもよい。
【０３６３】
ブロックの長さが長いと判定された場合（ステップＳ２１でｙｅｓ）、検出部１２は、上述したように、ブロックを分割する（ステップＳ２２）。ブロックが分割された後、処理はステップＳ２１に戻る。従って、１つのブロックが２つのブロックに分割される場合もあり、３つ以上のブロックに分割される場合もある。
【０３６４】
検出部１２は、ブロック内（時系列データの範囲）内で大小関係が変化する変化点を探索する（ステップＳ２３）。そして、検出部１２は、変化点を探索するブロックを次のブロックに移す（ステップＳ２４）。ステップＳ１９でｙｅｓの場合、およびステップＳ２０でｙｅｓの場合、処理はステップＳ２４に移る。
【０３６５】
ステップＳ１８でｎｏの場合、つまり未処理のブロックが存在しない場合、検出部１２は、変数ｉをインクリメントする（ステップＳ２５）。検出部１２は、以上の処理を、変数ｉが時系列データの期間に達するまで行う。
【０３６６】
次に、処理Ｂについて、図９３のフローチャートを参照して、説明する。処理Ｂの場合、比較対象の２つの時系列データのウィンドウは固定される。最初に、比較期間（ウィンドウ範囲）が決定される（ステップＳ３１）。
【０３６７】
計数部１３は、変数Ｐ（Ｐは整数）にゼロを代入する（ステップＳ３２）。変数Ｐは、一致数を示す。また、計数部１３は、変数ｉに「１」を代入する（ステップＳ３３）。
【０３６８】
計数部１３は、変数ｉが時系列データの期間未満であるかを判定する（ステップＳ３４）。変数ｉが時系列データの期間未満の場合（ステップＳ３４でｙｅｓ）、検出部１２は、変数ｉの時間差の変化点データを選択する（ステップＳ３５）。
【０３６９】
計数部１３は、上述した具体例１の処理を行い、変化点データの各変化点について、時系列データのウィンドウ範囲内の一致数を求め、該一致数を変数Ｐに加算する（ステップＳ３６）。
【０３７０】
計数部１３は、変数ｉをインクリメントし（ステップＳ３７）、処理はステップＳ３４に戻る。時間差を示す変数ｉが時系列データの期間に達するまで、ステップＳ３５乃至Ｓ３７の処理が行われる。
【０３７１】
変数ｉが時系列データの期間に達した場合（ステップＳ３４でｎｏ）、計数部１３は、一致数を合計して、一致数Ｐを求める。演算部１４は、一致数Ｐおよび項目数を、上述した式（Ａ）に当て嵌めて演算を行い、時系列データ同士の類似度を得る（ステップＳ３８）。その後、処理Ｂは終了する。
【０３７２】
次に、処理Ｃについて、図９４のフローチャートを参照して、説明する。最初に、比較期間（ウィンドウ範囲）が決定される（ステップＳ４１）。計数部１３は、上述した具体例１の処理を行い、最初に設定されたウィンドウの範囲内の大小関係の一致数Ｐを求める（ステップＳ４２）。
【０３７３】
差分処理部１５は、ウィンドウの前端および後端における一致数を用いて、具体例２で説明した一致数の変化量ｄを求める（ステップＳ４３）。演算部１４は、一致数Ｐおよび項目数を、上述した式（Ａ）に当て嵌めて演算を行い、類似度を得る（ステップＳ４４）。
【０３７４】
差分処理部１５は、ウィンドウをずらすことができる次の時刻が存在するかを判定する（ステップＳ４５）。ウィンドウをずらすことができる次の時刻が存在する場合（ステップＳ４５でｙｅｓ）、差分処理部１５は、比較対象の２つの時系列データにそれぞれ設定されたウィンドウをずらす（ステップＳ４６）。
【０３７５】
差分処理部１５は、上述した具体例２の処理を行い、ウィンドウに出入りする変化点に基づいて、一致数の変化量ｄを更新する（ステップＳ４７）。差分処理部１５は、ウィンドウがずらされる前に求められた一致数Ｐに、一致数の変化量ｄを加算する（ステップＳ４８）。
【０３７６】
これにより、ウィンドウがずらされた後における大小関係の一致数Ｐが得られる。ステップＳ４４において、演算部１４は、ウィンドウがずらされた後の一致数Ｐおよびウィンドウ範囲内の項目数を、上述した式（Ａ）に当て嵌めて演算を行い、類似度を得る。
【０３７７】
ステップＳ４５において、ウィンドウをずらすことができる次の時刻が存在するかが判定される。ウィンドウをずらすことができる次の時刻が存在しないと判定された場合（ステップＳ４５でｎｏ）、処理Ｃは終了する。
【０３７８】
次に、処理Ｄについて、図９５のフローチャートを参照して、説明する。最初に、比較期間（ウィンドウ範囲）が決定される（ステップＳ５１）。計数部１３は、上述した具体例１の処理を行い、最初に設定されたウィンドウの範囲内の大小関係の一致数Ｐを求める（ステップＳ５２）。
【０３７９】
差分処理部１５は、固定された時系列データ（ずらさない系列の変化点）およびウィンドウの前端および後端のアンカーにおける一致数を用いて、一致数の変化量ｄを求める（ステップＳ５３）。
【０３８０】
演算部１４は、一致数Ｐおよびウィンドウ範囲内の項目数を上述した式（Ａ）に当て嵌めて、２つの時系列データの類似度を得る（ステップＳ５４）。
【０３８１】
差分処理部１５は、固定されない方のウィンドウをずらすことができる次の時刻が存在するかを判定する（ステップＳ５５）。ウィンドウをずらすことができる次の時刻が存在する場合（ステップＳ５５でｙｅｓ）、差分処理部１５は、固定されていない方のウィンドウをずらす（ステップＳ５６）。
【０３８２】
差分処理部１５は、上述した具体例３の処理を行い、ウィンドウがずらされる前に求められた一致数Ｐに、一致数の変化量ｄを加算する（ステップＳ５７）。これにより、ウィンドウがずらされた後における大小関係の一致数Ｐが得られる。
【０３８３】
演算部１４は、ウィンドウがずらされた後における、一致数Ｐおよびウィンドウ範囲内の項目数を上述した式（Ａ）に当て嵌めて、２つの時系列データの類似度を得る（ステップＳ５８）。
【０３８４】
差分処理部１５は、上述したアンカーに到達した変化点から一致数の変化量ｄを更新する（ステップＳ５９）。ステップＳ５５において、ウィンドウをずらすことができる次の時刻が存在しない場合（ステップＳ５５でｎｏ）、処理Ｄは終了する。
【０３８５】
＜その他＞
図９６は、３種類の時系列データ（データＡ、データＢおよびデータＣ）の例を示す。データＡは、値の変化が緩やかなデータであり、局所性が大きい時系列データである。データＡのような時系列データは、変化点が少ないため、大小関係の一致数を求める時間が短くなり、時系列データ同士の類似度の演算時間も短くなる。
【０３８６】
データＢは、細かい周期でサンプリングされたデータであり、波形全体として、時系列データの値は、小さい値から大きい値に変化する。このような時系列データも、局所性がある程度大きいため、大小関係の一致数を求める時間が短くなり、時系列データ同士の類似度の演算時間も短くなる。
【０３８７】
データＣは、値の変動が大きい時系列データである。データＣのような時系列データは、局所性が小さく、変化点が多くなるため、大小関係の一致数を求める時間が、データＡおよびデータＢよりは長くなる。
【０３８８】
従って、データＣの場合、データＡやデータＢと比較して、時系列データ同士の類似度の演算時間が長くなる。ただし、データＣの場合であっても、変化点に基づいて、大小関係の一致数を求め、該一致数に基づいて類似度の演算を行っているため、類似度の演算時間は短くなる。
【０３８９】
本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【符号の説明】
【０３９０】
１    データ処理装置
１１    記憶部
１２    検出部
１３    計数部
１４    演算部
１５    差分処理部
１１１    プロセッサ
１１２    ＲＡＭ
１１３    ＲＯＭ
【図１】
0006604212.tif 000002
【図２】
0006604212.tif 000003
【図３】
0006604212.tif 000004
【図４】
0006604212.tif 000005
【図５】
0006604212.tif 000006
【図６】
0006604212.tif 000007
【図７】
0006604212.tif 000008
【図８】
0006604212.tif 000009
【図９】
0006604212.tif 000010
【図１０】
0006604212.tif 000011
【図１１】
0006604212.tif 000012
【図１２】
0006604212.tif 000013
【図１３】
0006604212.tif 000014
【図１４】
0006604212.tif 000015
【図１５】
0006604212.tif 000016
【図１６】
0006604212.tif 000017
【図１７】
0006604212.tif 000018
【図１８】
0006604212.tif 000019
【図１９】
0006604212.tif 000020
【図２０】
0006604212.tif 000021
【図２１】
0006604212.tif 000022
【図２２】
0006604212.tif 000023
【図２３】
0006604212.tif 000024
【図２４】
0006604212.tif 000025
【図２５】
0006604212.tif 000026
【図２６】
0006604212.tif 000027
【図２７】
0006604212.tif 000028
【図２８】
0006604212.tif 000029
【図２９】
0006604212.tif 000030
【図３０】
0006604212.tif 000031
【図３１】
0006604212.tif 000032
【図３２】
0006604212.tif 000033
【図３３】
0006604212.tif 000034
【図３４】
0006604212.tif 000035
【図３５】
0006604212.tif 000036
【図３６】
0006604212.tif 000037
【図３７】
0006604212.tif 000038
【図３８】
0006604212.tif 000039
【図３９】
0006604212.tif 000040
【図４０】
0006604212.tif 000041
【図４１】
0006604212.tif 000042
【図４２】
0006604212.tif 000043
【図４３】
0006604212.tif 000044
【図４４】
0006604212.tif 000045
【図４５】
0006604212.tif 000046
【図４６】
0006604212.tif 000047
【図４７】
0006604212.tif 000048
【図４８】
0006604212.tif 000049
【図４９】
0006604212.tif 000050
【図５０】
0006604212.tif 000051
【図５１】
0006604212.tif 000052
【図５２】
0006604212.tif 000053
【図５３】
0006604212.tif 000054
【図５４】
0006604212.tif 000055
【図５５】
0006604212.tif 000056
【図５６】
0006604212.tif 000057
【図５７】
0006604212.tif 000058
【図５８】
0006604212.tif 000059
【図５９】
0006604212.tif 000060
【図６０】
0006604212.tif 000061
【図６１】
0006604212.tif 000062
【図６２】
0006604212.tif 000063
【図６３】
0006604212.tif 000064
【図６４】
0006604212.tif 000065
【図６５】
0006604212.tif 000066
【図６６】
0006604212.tif 000067
【図６７】
0006604212.tif 000068
【図６８】
0006604212.tif 000069
【図６９】
0006604212.tif 000070
【図７０】
0006604212.tif 000071
【図７１】
0006604212.tif 000072
【図７２】
0006604212.tif 000073
【図７３】
0006604212.tif 000074
【図７４】
0006604212.tif 000075
【図７５】
0006604212.tif 000076
【図７６】
0006604212.tif 000077
【図７７】
0006604212.tif 000078
【図７８】
0006604212.tif 000079
【図７９】
0006604212.tif 000080
【図８０】
0006604212.tif 000081
【図８１】
0006604212.tif 000082
【図８２】
0006604212.tif 000083
【図８３】
0006604212.tif 000084
【図８４】
0006604212.tif 000085
【図８５】
0006604212.tif 000086
【図８６】
0006604212.tif 000087
【図８７】
0006604212.tif 000088
【図８８】
0006604212.tif 000089
【図８９】
0006604212.tif 000090
【図９０】
0006604212.tif 000091
【図９１】
0006604212.tif 000092
【図９２】
0006604212.tif 000093
【図９３】
0006604212.tif 000094
【図９４】
0006604212.tif 000095
【図９５】
0006604212.tif 000096
【図９６】
0006604212.tif 000097