(57)【要約】      （修正有）【課題】トレーニング時系列データから学習されたモデルを用いて、１次元時系列データ内の異常を効率的、かつ、正確に検出する方法を提供する。【解決手段】分割統治手順を用いてトレーニング時系列データ１０１を集約し最終的な標本の集合を学習する１１０ことで、時系列データ内の異常を検出する。次に、テスト時系列データ１０２のウィンドウごとに、最終的な標本１１１の集合内の最も近い標本までの距離である異常スコア１２１を求める１２０。最後に、ウィンドウの異常スコアが閾値よりも大きいとき、異常１３１を信号で通知する１３０。【選択図】図１
2015230727.tif 000002
【特許請求の範囲】
【請求項１】
時系列データ内の異常を検出する方法であって、
分割統治手順を用いてトレーニング時系列データを集約することによって、最終的な標本の集合を学習するステップと、
テスト時系列データの各ウィンドウについて、前記最終的な標本の集合内で最も近い標本までの距離を求めるステップであって、前記距離は、異常スコアである、ステップと、
ウィンドウの前記異常スコアが閾値よりも大きいとき、異常を信号で通知するステップと、
を含み、前記ステップは、プロセッサにおいて実行される、時系列データ内の異常を検出する方法。
【請求項２】
各標本は、前記時系列データの類似のウィンドウの集合を表す、請求項１に記載の方法。
【請求項３】
前記分割統治手順は、
前記トレーニング時系列データ内の初期の標本の集合をチャンクに分割するステップと、
１つのチャンクのみが残るまで、選択手順および組み合わせ手順のシーケンスを前記チャンクに適用するステップと、
前記残りのチャンクの前記標本に最後の選択手順を適用するステップであって、前記最終的な標本の集合を生成するステップと
をさらに含む、請求項１に記載の方法。
【請求項４】
前記時系列データの各ウィンドウは、該ウィンドウ内の前記時系列データの形状を特徴付ける軌道成分および確率的成分を特徴付ける統計成分として表され、前記軌道成分および前記統計成分を含む特徴ベクトルは、統計平滑化軌道（ＳＳＴ）特徴であり、前記ウィンドウは、時間的にスライドおよび重複している、請求項３に記載の方法。
【請求項５】
前記トレーニング時系列データ内の各ウィンドウについて前記ＳＳＴ特徴を求めるステップと、全てのＳＳＴ特徴の集合に等しい前記初期の標本の集合を定義するステップと
をさらに含む、請求項４に記載の方法。
【請求項６】
前記時系列データを平滑化するステップ
をさらに含む、請求項１に記載の方法。
【請求項７】
前記統計成分は、平均、標準偏差、絶対差の平均、平均交差の数をウィンドウサイズで除算したもの、正の差分のパーセンテージ、０の差分のパーセンテージ、および一連の正の差分を前記ウィンドウのサイズによって除算した平均サイズを含む、請求項５に記載の方法。
【請求項８】
前記選択手順は、最近傍標本を反復的にマージし、前記標本のマージは、前記ＳＳＴ特徴の平均を計算することによって行われる、請求項５に記載の方法。
【請求項９】
前記距離は、
【数１】
2015230727.tif 000004
であり、ここで、ｖ１およびｖ２は、２つの特徴ベクトルであり、ｖｊ・ｔは、ｖｊの前記軌道成分であり、ｖｊ・ｓは、ｖｊの前記統計成分である、請求項７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、信号処理に関し、より詳細には、実数値時系列データ内の異常を検出することに関する。
【背景技術】
【０００２】
時系列データは、多くの用途について生成および解析することができる。例えば、自動機器監視は、産業機器の多くのコストを要する修理を回避することができる。これは、機器上にあるセンサーまたは機器の近くにあるセンサーによって取得された時系列データを解析して、機器の保守または修理が必要とされることを示す場合がある異常を検出することによって行うことができる。
【０００３】
したがって、１次元時系列データのモデルを効率的に学習することが所望されている。この場合、このモデルは、同じソースからのその後のテスト時系列データ内の異常を検出するのに用いることができる。通常、このモデルは、異常を有しないトレーニング時系列から学習される。
【０００４】
時系列データのモデルを学習するための多くの方法が知られている。単純かつ効果的な方法は、トレーニング時系列データ全体をモデルとして用いる。換言すれば、トレーニング時系列全体が、モデルとして記憶される。したがって、トレーニングする時間は、無視することができる。異常を検出するために、テスト時系列の各ウィンドウが、トレーニング時系列のあらゆるウィンドウと比較され、最も近くの一致するウィンドウまでの距離が、異常スコアとして用いられる。この異常スコアが閾値よりも大きい場合、異常が信号で通知される。これについては、非特許文献１を参照されたい。その手法の主な欠点は、非常に大きくなるおそれのある、トレーニング時系列全体を記憶することを要し、また、異常スコアの計算が遅く、これは、実時間の用途に対して、広範囲の異なるタイプの時系列データとともにその方法を用いることを妨げる場合があるということである。
【０００５】
時系列データをモデル化するための別の部類の方法は、予測技法を用いるものである。そのような方法は、時系列データの多くの以前の値を用いて、現在の値を予測する。これについては、非特許文献２および非特許文献３を参照されたい。それらの予測モデルは、コンパクトにすることができるが、いくつかの時系列データを正確に予測しない場合がある。
【０００６】
時系列データをモデル化するための別の方法は、ｄ次元特徴空間を通る軌道としてのものである。ｄ次元空間における区分的に線形なパスまたはボックスが、トレーニング時系列データ内の有効なパスを効率的に表すのに用いられてきた。これについては、非特許文献４を参照されたい。その学習する方法は、Ｏ（ｎｌｏｇｎ）の複雑度を有する。
【０００７】
僅かに異なる手法が、時系列データの短いウィンドウを表すための部分空間を求め、次いで、自己回帰モデルまたは密度推定を用いて、その部分空間において軌道をモデル化する。これについては、非特許文献５を参照されたい。
【０００８】
２０１３年７月１日にJones他によって出願された「Method for Detecting Anomalies in a Time Series Data with Trajectory and Stochastic Components」という発明の名称の特許文献１は、テスト時系列データから抽出された普遍的な特徴を、トレーニング時系列データから取得された普遍的な特徴と比較してスコアを求めることによって、時系列データ内の異常を検出する方法を記載している。これらの普遍的な特徴は、時系列データの軌道成分および時系列データの確率的成分を特徴付ける。次に、異常スコアが閾値よりも大きい場合に、異常が検出される。トレーニング時系列から普遍的な特徴（標本のタイプである）の集合を効率的に学習する方法は、その特許文献１には開示されていない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許出願第１３／９３２，２３８号
【非特許文献】
【００１０】
【非特許文献１】Keogh他「HOT SAX: Finding the Model Unusual Time Series Subsequence: Algorithms and Applications」ICDM 2005
【非特許文献２】Ma他「Online Novelty Detection on Temporal Sequences」SIGKDD 2003
【非特許文献３】Koskivaara「Artificial Neural Networks for Predicting Patterns in Auditing Monthly Balances」J. of the Operational Research Society, 1996
【非特許文献４】Mahoney他「Trajectory Boundary Modeling of Time Series for Anomaly Detection」Workshop on Data Mining Methods for Anomaly Detection at KDD, 2005
【非特許文献５】Liu他「Modeling Heterogeneous Time Series Dynamics to Profile Big Sensor Data in Complex Physical Systems」IEEE Conf. on Big Data, 2013
【発明の概要】
【発明が解決しようとする課題】
【００１１】
したがって、多くの異なるタイプの時系列データに適用することができる時系列のための正確でコンパクトなモデルを効率的に学習することが必要とされている。
【課題を解決するための手段】
【００１２】
本発明の実施の形態は、トレーニング時系列データから学習されたモデルを用いて、１次元時系列データ内の異常を効率的、かつ正確に検出する方法を提供する。
【００１３】
本発明の主なアイデアは、トレーニング時系列データを標本の集合としてモデル化することである。これらの標本は、時系列データ内の様々な異なるウィンドウまたは部分シーケンスを表す。最終的な標本の集合は、トレーニング時系列データ内の重複するウィンドウの全体集合よりも大幅に小さい。
【００１４】
この標本学習手順は、分割統治のアイデアを用いて、時系列データをそれよりも小さなチャンクに分割し、チャンクごとに標本の集合を学習し、その後、それらの結果を組み合わせる。結果として得られた標本学習手順は、Ｏ（ｎｗ）時間（平均の場合）の複雑度を有する。ここで、ｎは、トレーニング時系列データのサイズであり、ｗは、ウィンドウのサイズである。
【発明の効果】
【００１５】
結果として得られた標本の集合は、異常検出を非常に高速にする。なぜならば、トレーニング時系列データは、相対的に少ない数の標本によって効率的に集約されているからである。さらに、この学習されたモデルによって、多種多様な時系列データのための非常に正確な異常検出方法が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態による時系列データ内の異常を検出する方法の流れ図である。
【図２】本発明の実施の形態による異常の集合を学習するための分割統治手順の概略図である。
【発明を実施するための形態】
【００１７】
異常検出方法
図１は、時系列データ内の異常を検出する方法を示している。この方法のステップは、当該技術分野において知られているように、バスによってメモリおよび入力／出力インターフェースに接続されたプロセッサ１００において実行することができる。
【００１８】
標本の集合１１１が、分割統治手順２００を用いてトレーニング時系列データ１０１を集約することによって学習される。標本は、時系列データの類似のウィンドウの集合を表したものである。分割統治手順の詳細は、図２に示されている。
【００１９】
テスト時系列データ１０２のウィンドウごとに、最も近い標本までの距離が求められる（１２０）。この距離は、異常スコア１２１として用いられる。
【００２０】
次に、ウィンドウの異常スコアが閾値Ｔよりも大きいとき、異常１３１が信号で通知される（１３０）。
【００２１】
分割統治手順
図２に示すように、分割統治手順は、初期の標本の集合２０１をチャンク２０２に分割する。次に、選択手順および組み合わせ手順２２０および２３０、２４０および２５０のシーケンス２０５がチャンクに適用される。選択手順は、所与の標本の集合から、より小さな標本の集合を選択する。このより小さな標本の集合は、所与の集合を十分に表すように選ばれる。単純な選択手順の一例は、チャンク内の標本間の最小の最近傍距離が閾値Ｔよりも大きくなるまで、チャンク内の２つの最も近い標本を反復的にマージすることである。
【００２２】
組み合わせ手順は、２つのチャンクからの標本の全てを単純に１つのチャンクにするものである。選択および組み合わせのこのプロセス２０５は、単一のチャンクが残るまで継続される。その後、最後の選択動作２６０が、最終的な標本の集合２０３を生成する。
【００２３】
統計平滑化軌道（ＳＳＴ：Statistical and Smoothed Trajectory）特徴
時系列データのウィンドウは、当該ウィンドウ内の時系列データの形状を特徴付ける軌道成分および確率的成分を特徴付ける統計成分として表される。これらのウィンドウは、時間的にスライドするとともに重複する。軌道成分および統計成分を含む特徴ベクトルは、統計平滑化軌道（ＳＳＴ）特徴と呼ばれる。
【００２４】
時系列データの類似のウィンドウの集合を表すＳＳＴ特徴の集合が与えられると、この集合の標本が、軌道成分および統計成分の各要素の標準偏差とともに平均軌道成分および平均統計成分によって求められる。
【００２５】
トレーニング時系列データを集約する標本の集合を学習するための本発明者らの手順は、次のステップを含む。
【００２６】
トレーニング時系列データ内の重複するウィンドウごとにＳＳＴ特徴ベクトルを求め、全てのＳＳＴ特徴ベクトルの集合に等しい初期の標本の集合２０１を定義する。
【００２７】
類似の重複するウィンドウの標本の初期マージ２２０を行う。
【００２８】
分割統治学習手順２００を用いて初期の標本の集合をさらに圧縮する。
【００２９】
これらのステップのそれぞれを、以下でより詳細に説明する。
【００３０】
特徴ベクトル
初期のＳＳＴ特徴の集合に等しい初期の標本の集合の計算は、簡単である。スライディングウィンドウ１０５が用いられ、各ウィンドウ内で、軌道成分および統計成分が求められる。軌道成分は、ウィンドウ内の時系列値の単純な固定ウィンドウ移動平均値を用いて求められ、ウィンドウの平均を減算した後、平滑化時系列データが得られる。
【００３１】
平滑化に起因して、平滑化時系列データ内の値の半分は、重要な情報を失うことなく廃棄することができる。これによって、ｗ／２個の要素を有する軌道成分が得られる。統計成分は、初期の時系列ウィンドウ内の確率的情報を特徴付けるように設計されたウィンドウ内の時系列データ値にわたって求められる統計の小さな集合である。
【００３２】
統計成分は、平均、標準偏差、絶対差の平均、平均交差の数をウィンドウサイズで除算したもの、正の差分のパーセンテージ、０の差分のパーセンテージ、および一連の正の差分をウィンドウサイズによって除算した平均サイズを含む。
【００３３】
軌道成分および統計成分を単一の特徴ベクトルに組み合わせることによって、ｗ／２＋７個の実数値からなるベクトルが得られる。初期の標本の集合は、標準偏差成分が全て０に設定された初期のＳＳＴ特徴ベクトルの集合に等しい集合である。
【００３４】
重複する部分シーケンスは、多くの場合、シーケンス間の距離が小さいので、類似の重複するシーケンスのＳＳＴ特徴ベクトルをマージすることによって、初期標本集合のサイズが削減される。２つのＳＳＴ特徴ベクトルをマージするために、これらの２つのベクトルの加重平均がとられる。各特徴ベクトルの重みは、その特徴ベクトルに既に平均されている特徴ベクトルの数である。
【００３５】
初期マージ２１０の後、分割統治手順２００を用いて、最終的な標本の集合２０３が効率的に選択される。この分割統治手順は、初期の標本の集合２０１をサイズＣのチャンクに分割する（２１０）。ここで、Ｃは、この手順のパラメーターである。チャンクごとに、選択手順が実行される。１つの実施の形態では、各チャンクに対して実行されるこの選択手順は、反復的なマージ手順である。この反復的なマージ手順は、まず、チャンク内の標本ごとに、チャンク内の最近傍標本を見つける。この手順は、以下の距離関数を用いる。
【００３６】
【数１】
2015230727.tif 000003
【００３７】
ここで、ｖ１およびｖ２は、２つの特徴ベクトルであり、ｖｊ・ｔは、ｖｊの軌道成分であり、ｖｊ・ｓは、ｖｊの統計成分である。距離関数の計算は、部分和がそれまで最近傍の距離よりも既に大きい場合には早期に計算を終了することを意味する早期放棄を用いる。標本間の距離が最小の２つの標本は、マージされる。２つの標本をマージすることは、それらの２つの標本の加重平均を計算することからなる。ここで、標本の重みは、その標本に既に平均されている標本の数に等しい。チャンク内のマージされた標本の最近傍が決定され、上記２つの標本のうちの一方を最近傍として有する他のいずれの標本も、それらの最近傍が再計算される。
【００３８】
２つの最も近い標本をマージするこのプロセスは、チャンク内の残りの全ての標本の最小の最近傍距離が閾値Ｔよりも大きくなるまで継続される。その時点で、選択手順は、終了し、残りの標本の集合をチャンクにするために返す。
【００３９】
別の実施の形態では、各チャンクに対して実行される選択手順は、ｋ平均クラスタリング等の従来のクラスタリングアルゴリズムである。
【００４０】
選択手順が各チャンクに適用された後、チャンクのペアが、それらの２つのチャンクからの全ての標本を単純に１つの新たなチャンクにすることによって、１つの新たなチャンクに組み合わされる。次に、選択手順は、それらの新たなチャンクのそれぞれに対して実行され、次いで、これらのチャンクは、組み合わされ、残りのチャンクが１つだけになるまで、以下同様に行われる。最終的な選択手順が、残りの１つのチャンクに対して実行され、全体のトレーニング集合のための最終的な標本の集合が得られる。これは、図２に示すような階層的な標本学習手順によって返される最終的な標本の集合である。
【図１】
2015230727.tif 000005
【図２】
2015230727.tif 000006
【外国語明細書】
2015230727.tif 000007
2015230727.tif 000008
2015230727.tif 000009
2015230727.tif 000010
2015230727.tif 000011
2015230727.tif 000012
2015230727.tif 000013
2015230727.tif 000014
2015230727.tif 000015
2015230727.tif 000016
2015230727.tif 000017
2015230727.tif 000018
2015230727.tif 000019
2015230727.tif 000020