多次元ストリーミング時系列データの効率的なモチーフモニタリングアルゴリズム / Monitoring Motif on Multi-dimensional Streaming Time-series, presented at DPSWS 2019

Transcript

1. 多次元ストリーミング時系列データの 効率的なモチーフモニタリングアルゴリズム 加藤 慎也，天方 大地，原 隆浩 大阪大学 大学院情報科学研究科 マルチメディア工学専攻 原研究室
2. 研究背景（1/3） ⚫近年，多くのストリーミング時系列データが生成 1 家電の消費電力 温室効果ガスの排出量 心電図 異常検知 環境モニタリング 不整脈の発見 分析
3. 研究背景（2/3） ⚫モチーフ - 時系列データを分析する最も重要な技術の一つ - 時系列データの中に繰り返し現れるパターン 2 温室効果ガスの排出量の時系列データ 時系列データの特徴がわかり，予測やイベント検知などに応用可能
4. 研究背景（3/3） ⚫近年，多くの多次元ストリーミング時系列データが生成 3 加速度センサ（3軸），ジャイロセンサ（3軸） の時系列データ データセンタのCPU使用率，メモリ使用率， ディスクI/Oの時系列データ モチーフのみを保存・送信することで 時系列データの特徴を保持したまま， ストレージや通信量を削減 過去のモチーフと現在のモチーフを 比較することで，故障予測や異常検知に活用
5. 問題定義 ⚫多次元ストリーミング時系列データのモチーフモニタリング - 時々刻々と新しい値が追加 - 新しい値が追加されるたびモチーフを更新 4 ⋮ ⋮ モチーフ 𝑡(1) 𝑡(2) 𝑡(𝑑) ⋮ 値が時々刻々と追加 モチーフを常に更新
6. 予備知識（1/3） ⚫1次元 - 時系列データ 𝑡 = 𝑡 1 , 𝑡 2 , ⋯ - サブシーケンス 𝑠𝑝 = 𝑡 𝑝 , 𝑡 𝑝 + 1 , ⋯ , 𝑡 𝑝 + 𝑙 − 1 ⚫多次元 - 多次元時系列データ 𝒕 = 𝑡(1) 𝑡(2) ⋮ 𝑡(𝑑) - 多次元サブシーケンス𝒔𝒑 = 𝑠𝑝 (1) 𝑠𝑝 (2) ⋮ 𝑠𝑝 (𝑑) 5 時間 𝑡 𝑝 𝑙 𝑠𝑝 時間 𝑡(1) 𝑝 𝑙 𝑡(2) 𝑡(𝑑) 𝒔𝒑 ⋮ ⋮
7. 予備知識（2/3） ⚫1次元サブシーケンス間の距離 - 𝑧正規化ユークリッド距離（正規化したサブシーケンス間のユークリッド距離） ⚫𝑘次元におけるサブシーケンス間の距離𝑑 𝑘 (𝒔𝒑 , 𝒔𝒒 ) - 𝑑次元のサブシーケンス𝒔𝒑 ，𝒔𝒒 ，および𝑘 (< 𝑑)が与えられたとき， 各次元のサブシーケンス間の距離が𝑘番目に小さい距離 6 正規化 ユークリッド 距離 𝑠𝑝 (1) 𝑠𝑝 (2) 𝑠𝑝 (3) 𝑠𝑞 (1) 𝑠𝑞 (2) 𝑠𝑞 (3) 1.3 8.4 2.1 𝑠𝑝 (4) 𝑠𝑞 (4) 3.3 𝑑 3 𝒔𝒑 , 𝒔𝒒 = 3.3 𝑘番目に 小さい距離
8. 予備知識（3/3） ⚫類似サブシーケンス - 𝑑 𝑘 𝒔𝒑 , 𝒔𝒒 ≤ 2𝑙 1 − 𝜃 ⟺ 𝒔𝒑 と𝒔𝒒 は類似サブシーケンス • 𝜃 ：類似度の閾値 • 𝑙 ：モチーフ長 ⚫スコア - 類似サブシーケンスの数 ⚫モチーフ - スコアが最大のサブシーケンス 7 𝒔𝒑 𝒔𝒒 𝒔𝒓 ≤ 2𝑙 1 − 𝜃 ≤ 2𝑙 1 − 𝜃 𝑠𝑐𝑜𝑟𝑒 𝒔𝒑 = 2
9. ベースラインアルゴリズム ⚫生成されるサブシーケンスと過去の全サブシーケンスと距離計算 - 例）3次元時系列データから長さ5のモチーフをモニタリング 8 新しい値を 取得 多大な時間がかかりリアルタイム性を保証できない．→高速化が必要 生成されるサブシーケンス 距離計算
10. 𝑙 提案アルゴリズム：概要 ⚫アイデア - 𝑘次元におけるサブシーケンス間の距離計算を高速化するには， 各次元における距離計算回数を削減すれば良い． - モチーフ（最大スコアのサブシーケンス）をモニタリングするため， 新たに生成される𝒔𝒏 のスコアがモチーフのスコアを下回れば，𝒔𝒏 はモチーフにならない． ⚫提案アルゴリズムの流れ 9 次元1 ⋯ 𝑙次元空間 次元𝑑 𝑙次元空間 ⋮ 次元1 次元𝑑 各次元ごとにクラスタリング 三角不等式により距離の下界値を計算 𝑠𝑛 (𝑖)
11. 提案アルゴリズム：クラスタリング ⚫中心のサブシーケンスを設定 ⚫それ以外のサブシーケンスは最も近い中心のクラスタに所属 ⚫クラスタ内の点は中心との距離の降順にソート 10
12. 提案アルゴリズム：三角不等式による距離の下界値の取得 ⚫新しいサブシーケンス𝑠𝑛 (𝑖)と中心サブシーケンス𝑠𝑝 (𝑖)と距離計算 ⚫クラスタ内のサブシーケンス𝑠𝑞 (𝑖)と𝑠𝑛 (𝑖)と𝑠𝑝 (𝑖)に三角不等式を適用すると， 𝑑(𝑠𝑛 (𝑖), 𝑠𝑞 (𝑖))の下界値が𝑂(1)で計算可能 ⚫下界値が閾値 2𝑙 1 − 𝜃 を超えた時点で計算を打ち切り 11 𝑠∙ 𝑖 下界値 𝑠 𝑏 𝑖 𝑠𝑐 𝑖 𝑠𝑎 𝑖 𝑠 𝑑 𝑖 𝑠𝑒 𝑖 𝑠𝑝 (𝑖) 𝑠 𝑏 (𝑖) 𝑠𝑎 (𝑖) 𝑠 𝑑 (𝑖) 𝑠𝑐 (𝑖) 𝑠𝑒 (𝑖) 𝑠𝑛 (𝑖) |𝑑(𝑠𝑛 𝑖 , 𝑠𝑝 𝑖 ) − 𝑑(𝑠𝑝 𝑖 , 𝑠 𝑏 (𝑖))| ≤ 2𝑙 1 − 𝜃 |𝑑(𝑠𝑛 𝑖 , 𝑠𝑝 𝑖 ) − 𝑑(𝑠𝑝 𝑖 , 𝑠𝑐 (𝑖))| > 2𝑙 1 − 𝜃 × × ×
13. 提案アルゴリズム：スコアの上界値の取得 ⚫各次元に対して三角不等式による下界値の計算を行った後， 𝑘個以上共通するサブシーケンスの数がスコアの上界値 12 𝑠𝑛 (𝑖)と類似する可能性のあるサブシーケンス 次元1 𝑠𝑎 (1), 𝑠 𝑏 (1), 𝑠𝑐 (1), 𝑠 𝑑 (1), 𝑠𝑒 (1), 𝑠 𝑓 (1), 𝑠𝑔 (1) 次元2 𝑠𝑎 (2), 𝑠𝑒 (2), 𝑠 𝑓 (2), 𝑠𝑔 (2), 𝑠 ℎ (2), 𝑠 𝑖 (2) ⋮ ⋮ 次元𝑑 𝑠𝑎 (𝑑), 𝑠 𝑓 (𝑑), 𝑠𝑔 (𝑑), 𝑠 ℎ (𝑑), 𝑠 𝑖 (𝑑) 𝑘個以上共通 𝒔𝒂 , 𝒔𝒇 , 𝒔𝒈 , 𝒔𝒉 , 𝒔𝒊 𝒔𝒏 のスコアの 上界値は5 𝒔𝒏 のスコアの上界値<モチーフのスコア⇒ 𝒔𝒏 はモチーフにならない．
14. 評価実験 ⚫データセット - Cricket ：加速度センサの多次元時系列データ（6次元） - EigenWorms ：線虫の動きの多次元時系列データ（6次元） ⚫パラメータ - 𝒕 （時刻） ：1,000~100,000 - 𝑙 （モチーフ長） ：50, 100, 150, 200 - 𝜃 （閾値） ：0.75, 0.8, 0.85, 0.9, 0.95 - 𝑘 （次元数） ：2, 3, 4 ⚫評価手法 - ベースラインアルゴリズム - 提案アルゴリズム 13
15. 評価結果：時刻 𝒕 の影響 14 0 2000 4000 6000 8000 10000 0 25000 50000 75000 100000 更新時間 [msec] |𝒕| baseline MMM 0 2000 4000 6000 8000 10000 0 25000 50000 75000 100000 更新時間 [msec] |𝒕| baseline MMM EigenWorms Cricket proposed proposed 提案アルゴリズムは距離計算回数が少ないため高速
16. 0 20000 40000 60000 80000 50 100 150 200 合計更新時間 [sec] 𝑙 baseline MMM 0 20000 40000 60000 80000 50 100 150 200 合計更新時間 [sec] 𝑙 baseline MMM 評価結果：モチーフ長𝒍の影響 15 EigenWorms Cricket proposed proposed 𝒍の増加によって距離計算時間が増加するため，更新時間も増加
17. 評価結果：閾値𝜽の影響 16 0 2000 4000 6000 8000 10000 0 25000 50000 75000 100000 更新時間 [msec] |𝒕| baseline MMM 0 2000 4000 6000 8000 10000 0 25000 50000 75000 100000 更新時間 [msec] |𝒕| baseline MMM EigenWorms Cricket 0 10000 20000 30000 40000 50000 0.75 0.8 0.85 0.9 0.95 合計更新時間 [sec] 𝜃 baseline MMM 0 10000 20000 30000 40000 50000 0.75 0.8 0.85 0.9 0.95 合計更新時間 [sec] 𝜃 baseline MMM proposed proposed 𝜽の増加によって距離の閾値が小さくなり，早期に距離計算の打ち切りが可能
18. 評価結果：次元数𝒌の影響 17 0 2000 4000 6000 8000 10000 0 25000 50000 75000 100000 更新時間 [msec] |𝒕| baseline MMM 0 2000 4000 6000 8000 10000 0 25000 50000 75000 100000 更新時間 [msec] |𝒕| baseline MMM EigenWorms Cricket 0 10000 20000 30000 40000 50000 2 3 4 合計更新時間 [sec] 𝑘 baseline MMM 0 10000 20000 30000 40000 50000 2 3 4 合計更新時間 [sec] 𝑘 baseline MMM proposed proposed 𝒌の増加によって，𝒌次元におけるサブシーケンス間の距離が大きくなり， 全体的にスコアが小さくなり正確な距離計算回数が減少
19. まとめ ⚫多次元ストリーミング時系列データのモチーフモニタリング - 距離の小さいサブシーケンス同士をクラスタリング - 三角不等式による距離の下界値の取得 - 評価実験から提案アルゴリズムの有効性を確認 18