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つの重要なアイディアについてご説明します.

  1. 多階層連鎖モデル (MLCM: multi-level chain model)
  2. モデル表現コストとデータ圧縮

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 つの部分問題に分割されます.

  1. CutPointSearch: レジームの個数 (r = 2) とモデルパ ラメータが与えられたときに,X を 2 つのレジームに分割し, それぞれのセグメントの分割位置を検出する.
  2. RegimeSplit: レジームの個数 r = 2 が与えられたとき に,2 つのレジームを表現するモデルパラメータ (θ1, θ2, ∆) を 推定する.
  3. 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]

関連文献

国内論文誌
  • 松原 靖子, 櫻井 保志, 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]