AutoPlait : 大規模時系列データからの特徴自動抽出

概要

時系列シーケンスは，センサデータや Web アクセス履歴等，様々なアプリケーションにおいて大量に生成されています．これらの大規模な時系列シーケンスの中から，典型的なパターンや異常値を発見することは非常に重要な課題です．本研究の目的は，大規模時系列データを対象とし，重要な時系列パターンの抽出を自動的に行なうことです．より具体的には，大規模時系列データの中から，異なるトレンドを発見し，すべての時系列パターンを表現する手法として，AutoPlait を提案しました．

autoplait_1_dfn — 図1: MoCap データ（加速度センサ）「チキンダンス (chicken dance)」における AutoPlait の入力・出力の例．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)」と呼びます．

autoplait_2_idea1 — 図2: 多階層連鎖モデル (MLCM: multi-level chain model)の様子．複数のレジーム間の時系列パターンとその遷移を表現するために，多層的な連鎖モデル (MLCM) を提案する．

2. モデル表現コストとデータ圧縮

適切なセグメントとレジームの発見のために，最小記述長 (MDL: minimum description length) の概念を用います (図3参照)．MDL は情報理論に基づくモデル選択基準のひとつで，可逆圧縮を行なうことができます．本研究では，与えられたバンドル X を適切に表現するモデルを見つけるために，新しい符号体系を定義しました．具体的には，(a) 最適なパラメータ集合 Cを推定するためのコスト関数を定義し，(b) 最適解を発見するための効果的なアルゴリズムを提案します．

autoplait_3_idea2 — 図3: モデル表現コスト: セグメントとレジームの発見のために，最小記述長 (MDL: minimum description length) の概念を用いる．

アルゴリズム

図4は，AutoPlaitの最適化アルゴリズムの概要を示しています．アルゴリズムは，次に挙げる 3 つの部分問題に分割されます．

CutPointSearch: レジームの個数 (r = 2) とモデルパラメータが与えられたときに，X を 2 つのレジームに分割し，それぞれのセグメントの分割位置を検出する．
RegimeSplit: レジームの個数 r = 2 が与えられたときに，2 つのレジームを表現するモデルパラメータ (θ1, θ2, ∆) を推定する．
AutoPlait: 最適なレジームの個数 (r = 2, 3, 4, . . .) を求める．

autoplait_4_alg — 図4: 提案アルゴリズムの概要図．AutoPlait はバンドルX が与えられたとき，反復処理により適切なセグメント/レジームの個数を求めます．

実験結果

図5は実際のデータに対してAutoPlaitを用いてパターン発見を行なった結果を示しています．図のように，AutoPlaitは，Mocap等のセンサデータから，GoogleTrendデータのクエリ頻度の推移のようなWebデータまで，幅広い時系列データの中から，重要な情報を完全自動で抽出することができます．

autoplait_5_exp — 図5: Mocapデータにおける AutoPlaitの出力結果のようす(左図), Google Trendデータにおけるトレンドの変化点抽出例（ゲーム関連ワード，右図）．

参考文献

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]