Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
ストリーミング時系列データの効率的なモチーフモニタリングアルゴリズム / Monitoring...
Search
Shinya Kato
July 06, 2018
Research
0
140
ストリーミング時系列データの効率的なモチーフモニタリングアルゴリズム / Monitoring Range Motif on Streaming Time-Series, presented at DICOMO 2018
Shinya Kato
July 06, 2018
Tweet
Share
More Decks by Shinya Kato
See All by Shinya Kato
PostgreSQLのVisibilityの仕組み
shinyakato_
2
450
pg_bigmをRustで実装する(第50回PostgreSQLアンカンファレンス@オンライン 発表資料)
shinyakato_
0
230
多次元ストリーミング時系列データの効率的なモチーフモニタリングアルゴリズム / Monitoring Motif on Multi-dimensional Streaming Time-series, presented at DPSWS 2019
shinyakato_
0
28
Discord Monitoring for Streaming Time-series, presented at DEXA 2019
shinyakato_
0
27
ストリーミング時系列データの効率的なディスコードモニタリングアルゴリズム / Discord Monitoringfor Streaming Time-series, presented at DEIM 2019
shinyakato_
0
25
Monitoring Range Motif on Streaming Time-Series, presented at DEXA 2018
shinyakato_
0
17
Other Decks in Research
See All in Research
線形判別分析のPU学習による朝日歌壇短歌の分析
masakat0
0
130
データサイエンティストの採用に関するアンケート
datascientistsociety
PRO
0
970
さくらインターネット研究所 アップデート2025年
matsumoto_r
PRO
0
640
Cross-Media Information Spaces and Architectures
signer
PRO
0
220
SSII2025 [SS1] レンズレスカメラ
ssii
PRO
2
940
EOGS: Gaussian Splatting for Efficient Satellite Image Photogrammetry
satai
4
240
なめらかなシステムと運用維持の終わらぬ未来 / dicomo2025_coherently_fittable_system
monochromegane
0
250
Sosiaalisen median katsaus 03/2025 + tekoäly
hponka
0
1.3k
20250502_ABEJA_論文読み会_スライド
flatton
0
170
Pix2Poly: A Sequence Prediction Method for End-to-end Polygonal Building Footprint Extraction from Remote Sensing Imagery
satai
3
480
NLP2025参加報告会 LT資料
hargon24
1
320
学生向けアンケート<データサイエンティストについて>
datascientistsociety
PRO
0
2.9k
Featured
See All Featured
KATA
mclloyd
29
14k
Visualization
eitanlees
146
16k
Why You Should Never Use an ORM
jnunemaker
PRO
56
9.4k
Building Better People: How to give real-time feedback that sticks.
wjessup
367
19k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
161
15k
The World Runs on Bad Software
bkeepers
PRO
69
11k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
26k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
331
22k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.8k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
657
60k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
20
1.3k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
31
1.2k
Transcript
ストリーミング時系列データの 効率的なモチーフモニタリングアルゴリズム 加藤 慎也,天方 大地,西尾 俊哉,原 隆浩 大阪大学 大学院情報科学研究科
研究背景(1/2) ◼近年,多くの時系列データが収集 1 家電の消費電力 温室効果ガスの排出量 心電図 異常検知 環境モニタリング 不整脈の発見 分析
研究背景(2/2) ◼モチーフ 時系列データの中に繰り返し現れるパターン 2 予測 異常 モチーフを用いて時系列データを分析
予備知識 ◼類似サブシーケンス 𝑑(𝑠𝑖 , 𝑠𝑗 ) ≤ 𝑅 ⇔ 𝑠𝑖
と𝑠𝑗 は類似サブシーケンス ◼スコア 類似サブシーケンスの数 ◼モチーフ スコアが最大のサブシーケンス[1] 3 ≤ 𝑅 ≤ 𝑅 ≤ 𝑅 スコア = 𝟑 [1] Patel, P., Keogh, E., Lin, J. and Lonardi, S.: Mining motifs in massive time series databases (2002)
問題定義 ◼スライディングウィンドウ上で ストリーミング時系列データのモチーフをモニタリング データが発生するたびウィンドウをスライド 最新の𝑤個の値のみを考慮 4 ウィンドウ 古い値は 考慮しない. ウィンドウ
ウィンドウ ウィンドウ データ発生 データ発生 データ発生 ウィンドウ
◼ウィンドウのスライドにより 削除されるサブシーケンス 挿入されるサブシーケンス と 全サブシーケンスとの距離計算することによりスコア更新 ベースラインアルゴリズム 5 ウィンドウ データ発生 データ削除
⋯ 削除される サブシーケンス 挿入される サブシーケンス 距離計算 距離計算 ⋯ 【研究目的】 ウィンドウがスライドした際の スコアの更新を高速化し, モチーフを効率的にモニタリングする.
提案アルゴリズムSRMM(Streaming Range Motif Monitoring) つまり,挿入されるサブシーケンスを𝑠𝑛 とすると 𝒔𝒏 のスコア<モチーフのスコア がわかれば,モチーフが更新されないことがわかる. ◼SRMMの流れ
6 モチーフ(スコア最大のサブシーケンス)をモニタリングが 問題定義 PAA 𝒌𝒅木に 挿入 ⋮ 距離𝑅以上のサブシーケンス を高速に特定 スコアの上界値を高速に計算
SRMM - PAA ◼PAA[2]によりサブシーケンスを長さ𝑙から𝜙に圧縮 7 𝑙 𝜙 𝑠𝑖 𝑠 𝑖
𝜙 𝑠𝑗 𝑠 𝑗 𝜙 𝑑(𝑠𝑖 , 𝑠𝑗 ) 𝑑(𝑠 𝑖 𝜙, 𝑠 𝑗 𝜙) PAA ≥ ≥ 𝑅 𝒔𝒊 と𝒔𝒋 は類似サブシーケンスでない! 𝑂(𝑙) 𝑂(𝜙) [2] Keogh, E.: Dimensionality reduction for fast similarity search in large time series databases (2001)
SRMM – 範囲検索 ◼𝑠 𝑖 𝜙 = (𝑡 𝑖 𝜙,
𝑡 𝑖+1 𝜙 , ⋯ , 𝑡 𝑖+𝜙−1 𝜙 )は𝜙次元上の点として表現 ◼距離𝑅以内のサブシーケンスの数=スコアの上界値 8 𝜙次元 𝑠𝑛 𝜙 全計算 𝑂(𝜙) × 𝑤 = 𝑂(𝜙𝑤) 𝒌𝒅木による範囲検索 𝑶 𝝓 𝐥𝐨𝐠 𝒘 𝜙次元 𝑠𝑛 𝜙 スコアの上界値5
SRMM – モチーフ更新の例 ◼𝑠𝑛 のスコアの上界値2 < モチーフのスコア3 𝑠𝑛 はモチーフにならない. ◼𝑠𝑛
のスコアの上界値5 > モチーフのスコア3 𝑠𝑛 はモチーフになり得るため,正確なスコアの計算を行う. 9 𝑠𝑛 𝜙 𝑠𝑎 𝜙 𝑠𝑐 𝜙 𝑠 𝑑 𝜙 𝑠𝑒 𝜙 𝑠 𝑏 𝜙 𝑑(𝑠𝑛 , 𝑠𝑎 ) 𝑑(𝑠𝑛 , 𝑠𝑑 ) 𝑑(𝑠𝑛 , 𝑠𝑒 ) 𝑑(𝑠𝑛 , 𝑠𝑏 ) 𝑑(𝑠𝑛 , 𝑠𝑐 ) < 𝑅 > 𝑅 𝑑(𝑠𝑛 , 𝑠𝑒 ) 𝑑(𝑠𝑛 , 𝑠𝑎 ) 𝑑(𝑠𝑛 , 𝑠𝑑 ) 𝑑(𝑠𝑛 , 𝑠𝑏 ) 𝑑(𝑠𝑛 , 𝑠𝑐 ) 𝒔𝒏 のスコアは1 ⇒モチーフは更新されない.
SRMM – サブシーケンスの削除 ◼削除されるサブシーケンス𝑠𝑒 と 類似するサブシーケンスのスコアの上界値が1減少 ◼各サブシーケンスが類似サブシーケンスのリストを保持 サブシーケンス挿入時に作成 10 𝑠𝑒
𝜙 𝑠𝑝 𝜙 𝑠𝑞 𝜙 𝑠𝑟 𝜙 𝑠𝑒 : 𝑠𝑝 , 𝑠𝑞 , 𝑠𝑟 𝑠𝑝 : 𝑠𝑒 , ⋯ 𝑠𝑞 : 𝑠𝑒 , ⋯ 𝑠𝑟 : 𝑠𝑒 , ⋯ 𝒔𝒆 を𝒔𝒑 , 𝒔𝒒 , 𝒔𝒓 のリストから削除し スコアの上界値を1減少 削除 削除 削除
評価 ◼データセット GreenHouseGas, RefrigerationDevices ◼パラメータ ◼比較手法 ベースラインアルゴリズム ◼評価指標 更新時間 11
ウィンドウサイズ𝑤 [× 103] 5, 10, 15, 20 モチーフ長𝑙 50, 100, 150, 200 ピアソン相関の閾値𝜃 0.75, 0.8, 0.85, 0.9, 0.95 Rは以下の式で計算 𝑅 = 2𝑙(1 − 𝜃)
ウィンドウサイズ𝑤の影響 12 0 20 40 60 80 5 10 15
20 更新時間[msec] ウィンドウサイズ[×103] ベースライン SRMM 0 20 40 60 80 5 10 15 20 更新時間[msec] ウィンドウサイズ[×103] ベースライン SRMM SRMMはベースラインよりも高速 GreenHouseGas RefrigerationDevices
0 20 40 60 80 50 100 150 200 更新時間[msec]
モチーフ長 ベースライン SRMM 0 20 40 60 80 50 100 150 200 更新時間[msec] モチーフ長 ベースライン SRMM モチーフ長𝑙の影響 13 SRMMはモチーフ長によらず高速 GreenHouseGas RefrigerationDevices
0 20 40 60 0.75 0.8 0.85 0.9 0.95 更新時間[msec]
閾値θ ベースライン SRMM 0 20 40 0.75 0.8 0.85 0.9 0.95 更新時間[msec] 閾値θ ベースライン SRMM 閾値𝜃の影響 14 SRMMは閾値が大きいほど高速 GreenHouseGas RefrigerationDevices Rは以下の式で計算 𝑅 = 2𝑙(1 − 𝜃)
まとめ ◼ストリーミング時系列データの 効率的なモチーフモニタリングアルゴリズムSRMMの提案 PAAおよび範囲検索を用いることにより, 不要なスコアの計算を削減 類似サブシーケンスのリストを保持することにより, スコアの減少するサブシーケンスを高速に特定 ◼評価実験からSRMMの有効性を確認 ◼今後の課題 多次元時系列データへの対応
15