概要
時系列シーケンスは,センサデータや Web アクセス履歴等, 様々なアプリケーションにおいて大量に生成されています.これらの大規模な時系列シーケンスの中から,典型的なパターンや 異常値を発見することは非常に重要な課題です.本研究の目的は,大規模時系列データを対象とし,重要な時系列パターンの 抽出を自動的に行なうことです.より具体的には,大規模時系 列データの中から,異なるトレンドを発見し,すべての時系列 パターンを表現する手法として,AutoPlait を提案しました.
提案手法とその特徴
図 1 は,MoCap データにおける「チキンダンス (chicken dance)」の時系列シーケンスデータと,AutoPlait の出力結果例です.このモーションは,4 次元のシーケンス で構成され,それぞれの次元が,左右の腕と足の加速度を表現 しています.チキンダンスは,beaks, wings, tail feathers, claps の 4 つの代表的なステップ から構成されており, 図 1 の下の段は,AutoPlait が自動抽出した 4 つのレジー ムを示しています.提案手法は,ダンスに含まれる 4 つのステッ プを抽出し,そして各ステップの切れ目も正しく発見することができます.AutoPlait は,こ れらの 4 つのステップに関する事前知識を必要とせず,適切な数のレジームとその位置を自動的に把握することができます.
提案手法は次の挙げられるコンセプトで構成されます.入力データ(Bundle)が与えられたとき,AutoPlaitは,3つの重要な情報を自動的に抽出します.
名称 | 入出力 | 定義 | |
X | Bundle (バンドル) | input | 入力データ (d x n の行列) |
S | Segment (セグメント) | output | m個の部分シーケンス群 |
Θ | Regime (レジーム) | output | r個の類似セグメントのグループ |
F | セグメントメンバシップ | output | 各セグメントが所属するレジー ムのID |
AutoPlaitの目的は,与えられた時系列シーケンス群, i.e., Bundle X の特徴を抽出し,すべての時系列パターンを表現するパラメータ集合 C = {m, r, S, Θ, F} を発見することです.
以下では,AutoPlaitの2つの重要なアイディアについてご説明します.
- 多階層連鎖モデル (MLCM: multi-level chain model)
- モデル表現コストとデータ圧縮
1. 多階層連鎖モデル (MLCM: multi-level chain model)
複数のレジーム間の時系列パターンとその遷移を表現するため に,多層的な連鎖モデル (MLCM) を提案します.図 2 は提案モデルの概念図です.提案モデルであるMLCMは隠れマルコフモデル(HMM: Hidden Markov Model)を拡張しており,従来の HMM の遷移確率に加え,上位層の状態 (super-state) の概念を導入することによって,パターンのグルー プ化を行ないます.ここで,このグループを「レジーム (regimes)」と呼びます.
2. モデル表現コストとデータ圧縮
適切なセグメントとレジームの発見のために,最小記述長 (MDL: minimum description length) の概念を用います (図3参照).MDL は情報理論に基づくモデル選択基準のひとつで,可逆圧縮を行なうことができます.本研究では,与えられたバンドル X を適切に表現するモデルを見つけるために,新しい符号体系を定義しました.具体的には,(a) 最適なパラメータ集合 Cを推定するためのコスト関数を定義し,(b) 最適解を発見するための効果的なアルゴリズムを提案します.
アルゴリズム
図4は,AutoPlaitの最適化アルゴリズムの概要を示しています.アルゴリズムは,次に挙げる 3 つの部分問題に分割されます.
- CutPointSearch: レジームの個数 (r = 2) とモデルパ ラメータが与えられたときに,X を 2 つのレジームに分割し, それぞれのセグメントの分割位置を検出する.
- RegimeSplit: レジームの個数 r = 2 が与えられたとき に,2 つのレジームを表現するモデルパラメータ (θ1, θ2, ∆) を 推定する.
- AutoPlait: 最適なレジームの個数 (r = 2, 3, 4, . . .) を 求める.
実験結果
図5は実際のデータに対してAutoPlaitを用いてパターン発見を行なった結果を示しています.図のように,AutoPlaitは,Mocap等のセンサデータから,GoogleTrendデータのクエリ頻度の推移のようなWebデータまで,幅広い時系列データの中から,重要な情報を完全自動で抽出することができます.
参考文献
- Yasuko Matsubara, Yasushi Sakurai, Christos Faloutsos, “AutoPlait: Automatic Mining of Co-evolving Time Sequences”, ACM SIGMOD Conference, pp. 193-204, Snowbird, Utah, June 2014. [pdf] [ppt] [code]
関連文献
国内論文誌
- 松原 靖子, 櫻井 保志, Christos Faloutsos: “大規模時系列データの特徴自動抽出”, 情報処理学会論文誌:データベース, Vol. 7, No. 2, pp. 37-50, 2014, 6月.
受賞,講演等
- Yasushi Sakurai, Yasuko Matsubara, Christos Faloutsos: “Mining and Forecasting of Big Time-series data“, ACM SIGMOD Conference, tutorial, Melbourne, VIC, Australia, May/June 2015. [pdf]
- 松原靖子,“大規模時系列データのための特徴自動抽出と将来予測”, 電気情報通信学会総合大会 (2015年3月12日). [link]
- 櫻井保志,“時系列ビッグデータからの特徴自動抽出”, 人工知能学会 第95回人工知能基本問題研究会(SIG-FPAI), 2014年10月10日. [link]
- 松原 靖子, 櫻井 保志, Christos Faloutsos, “大規模時系列データからの特徴自動抽出”, 第6回データ工学と情報マネジメントに関するフォーラム (DEIM2014) 最優秀論文賞, 山下記念賞受賞 (2014年3月). [pdf]