大規模データストリームの劣線形要約とリアルタイム異常検知への応用
静岡大学

情報学部 情報科学科
准教授 山本 泰生
2024年2月8日
1

発表の概要• 背景
ストリームデータ処理
データ要約• 技術: 時系列データの要約
PSS-TS• 応用: エビデンスに基づく異常検知
センシングデータを用いた行動認証
データ駆動の科学発見

2

ストリームデータの研究• ストリームデータとは？
高速に流れ続ける無限長のデータ列
センサーノードから常時到着する観測データ
観測対象のリアルタイム分析 (傾向の変化や異常の検出)
リアルタイム監視オンライン処理

観測対象
観測データ

ストリームデータ3

IoTとリアルタイム分析• 2025年予想

ストリームデータが全体に占める割合: 25% [IDC, 2018]
経済効果予測: 270～620兆円 [McKinsey, 2013]
ヘルスケア (41%), 製造 (33%), エネルギー (7%),
交通・インフラ・農業・小売 (15%)• データ分析の3層構造 [M. Mohammadi et al., 2018]
レイテンシ 高クラウド

リアルタイム性 低
DNN学習

永続化

data flow

DNN推論

特徴抽出

センシング

レイテンシ 低デバイス

Analysis flow

エッジ

知識獲得

リアルタイム性 高4

IoTとリアルタイム分析• 2025年予想
ストリームデータが全体に占める割合: 25% [IDC, 2018]
経済効果予測: 270～620兆円 [McKinsey, 2013]
ヘルスケア, 製造, エネルギー, 交通, インフラ, 農業, 小売• データ分析の3層構造 [M. Mohammadi et al., 2018]
田舎 (山岳地帯), 極地 (宇宙, 人体)

ネットワーク帯域 弱

エッジ

クラウド
閉システム
エッジ

レイテンシ 低センシング

data flow

データ要約

リアルタイム性 高データ検索
デバイス
異常検知

5

エッジ上のストリームデータ分析• ビッグデータ分野の重要課題 [IDC, 2015; 2018]
ハードディスク (+SSD) スキャンは原理的に困難
到着データを ``On-the-fly’’ でインメモリ処理する
省メモリなインメモリ管理技術の開発が必要不可欠！
知的価値の発掘10 ~ 100万倍高速

オンライン処理

ストリームデータ管理

Keyvalue

DocumentWidecolumns

RDBMS

データベース管理6

データ要約とは？
• インメモリ処理を可能にする革新的なデータ管理技術• サマリ: 特殊な関係クエリ (質問) に応答するデータ構造
管理対象のデータ列: S = e , e , … , e , n はデータ総数
関係: R

問題に応じて設定

クエリ: q

何でもOK• 2種類のクエリ
メンバーシップクエリ: q と関係 R を満たす ei が S 中に存在した?
サポートクエリ: q と関係 R を満たす ei が S 中に何回出現した？
ストリームビッグデータ

S
オンライン構築

関係クエリ

サマリ

(R, q)
リアルタイム応答

7

関係データの例「からから」 関係
任意の2日,に対しを次のように想定
定義

より の方が「からから」(

気象データ列,≤

気温が高く)

S

気温a1

降水量
a2

風速
a3

風向a4

日照
a5e1

1453010e21110105e31952114e41332114

かつ≥降水量が低い以下の2つのうち成り立つものはどちら?

R(e2, e4)?
R(e4, e1)?
8

関係データの例 cont.
クエリ q = (12, 5, -, -, -) のとき (ただし- は空)メンバーシップクエリの意味

R(ei, q) となる ei が S に存在するか?

S

気温
a1

降水量
a2

風速
a3

風向
a4

日照
a5

e1

1453010e2

1110

105e3

1952114e4

1332114

気温 12 ℃ 以上 & 降水量 5 mm以下となる日は過去にあった?

Yes9関係データの例 cont.
クエリ q = (12, 5, -, -, -) のとき (ただし- は空)
サポートクエリの意味R(ei, q) となる ei が S に何回存在した?

S

気温a1

降水量
a2

風速
a3

風向a4

日照
a5e11453010e21110105e31952114e41332114

気温 12 ℃ 以上 & 降水量 5 mm以下だった過去の日数?

3日
10サマリに関する研究動向 (1/2)• 推定値に誤差を許容する近似サマリの研究が進む: クエリ,
右式を満たす::の真値, ( ):Pr−

出力誤差の推定値とすると

≤≥1−

許容誤差

誤り発生確率• メンバーシップサマリ: 空間計算量の下界は Ω
データサイズ未満の近似サマリは存在しない• サポートサマリ: 多くの劣線形近似サマリが発見されている関係 R のタイプに応じてサポートサマリ (SS) を3つに分類
等価関係を扱う Equivalence SS (ESS)
クエリの出現頻度を答えるサマリ
全順序関係を扱う Linear order SS (LSS)
クエリのランキングを答えるサマリ
半順序関係を扱う Partial order SS (PSS)
クエリを含意するデータ数を答えるサマリ

サマリに関する研究動向 (2/2)• サマリ全体とサポートサマリの各クラスの現状
ESS と LSS: 確率的/決定性双方の優れたアルゴリズムが発見．
機械学習やプライバシー保護の課題で多くの活用事例あり
PSS: 劣線形サマリを構築する決定性アルゴリズムは未探索．
活用事例も少ない
応用領域はフロンティア
サマリ

アプローチ

確率的ESS
決定性
確率的LSS
決定性

手法

Count-min sketch(G.Cormode,2003)

Space-Saving(A.Metwally etal,2005)

Mergeable sketch(P.K.Agrawal etal,2013)

GK sketch(M.Greenwald&S.Khanna,2001)

確率的K-Minimal Value

決定性

PARASOL

PSS

関係 R(G.Wang et al,2021)(Yamamoto et al, 2020)

等価 ≡(Equivalence)

全順序 ≤関係クエリ q

メンバーシップ

サポート

Ext. of e in S
s.t. R(e, q) ?

Num. of e in S
s.t. R(e, q)?

Bloom filter
空間
計算量

O( )

(Linear order)

半順序 ≺(Partial order)

Bloom matrixO( )劣線形化困難Space-Saving(heavy hitters問題) O(ε-1)

GK sketch(分位数サマリ)O(log ε )フロンティア(頻度サマリ)

劣線形化可能PSSのインパクト• データ量によらずストリーム全体をインメモリ管理する
超軽量なデータ構造を用いたリアルタイム検索• 任意のクエリと関係を結ぶデータの発生頻度に応答する関係表現を用いたリッチなクエリ設定
エビデンスを伴うクエリの異常度判定

Ｘ

Y

関係クエリ: 属性 X, Y, Z の条件の連言Z

走査

例. (天候=晴)⋀(気温≥ 38°)⋀(湿度≤ 20%)
クエリが異常のとき発生頻度は少用途に応じて許容誤差εと誤り確率δ
設定すれば異常検知に利用できる
13

時系列データの場合• これまでに見たことのない新種パタンをリアルタイム検知する問題
実データ (時系列データ)

実データ+矩形波 (変動パタン)

センサー

アラート

変動区間

時間

劣線形化 (超軽量)時系列データ

要約変動パタン

PSS

観測系

検索スライディングウィンドウ

検知min
測定誤差

確率不等式
制御モデル

max

アラート

学習モデル

東京大学 天文チームとの共同研究 (基盤研究A, 分担 2021~2024)

過去事例を照会なし
新種パタン 14

当研究室の取り組み (コア技術)• 劣線形な頻度サマリ (PSS) アルゴリズムの開発• PSSを用いた時系列データ要約 (PSS-TS)• 時系列データの時空間分解アルゴリズムの開発
・・・

5

1

10・・・

013

属性値の種類数: m (m = 5)

1

各属性のとり得る値{1, 2, 3, 4, 5}

1次要素の最大値は3以下・・・

1 1 1 0 0 ・・・ 1KMV

クエリ

検索03 最小値

2ℎℎ

次元数 d (d = 2)

4

登録

PSS

4 最大値4

順序変換
1

順序変換

系列長 L (L = 4)

・・・

1100

順序変換

・・・

0

ハッシュ関数 ℎℎ( ) が最小

3

ベクトル長 ∆(∆ = 2×4×5)

KMV スケッチ・・・

9ℎ( ) が下位 k 番

ハッシュ関数 ℎ( )の値が下位 k 個の ID リストを管理

15

時系列データ要約の応用可能性
1. 高速 & 超軽量なリアルタイム処理
2. オンライン解析
HDD
エビデンスに基づくオンライン異常検知法
現時刻の時系列が過去に出現したかどうかを判定
出現していなければ 異常 (新種) パターン
ゼロトラスト認証の要素技術 Sketch as FingerPrint
問い合わせ (クエリ) 時系列 q

時系列データストリーム S = <e1, e2, e3>
最大 (測定誤差)
系列 e1

DPU

最小 (測定誤差)

観測値

q に含まれる系列は S に

系列 e2

PSS何回出現?

系列 e3

1回
時刻 1

時刻 2

Memory

時刻 3

時刻 4

レアな時系列定義: q と ei の含意関係 R(ei, q)∀. min ≥. min ∧(∀. max ≤. max)

既存技術と新技術の違い• モデルに基づく異常検知（learning-model-based anomaly detection）- 事前の学習モデルが必要
適切なモデル設計にコストがかかる (問題依存性が高い) 【問題点】- モデルのダイナミクスが時間変化すると対応できない【問題点】- 学習モデルは高速・軽量【ビッグデータ対応】• エビデンスに基づく異常検知（instance-based anomaly detection）- 事前の学習モデルを必要としない- 解析対象データに一切の分布を仮定しないノンパラメトリックな確率モデル
現象の発生メカニズムがわからないデータに利用可能- データセットシフト, ダイナミクスが時間変化する概念遷移に対応可- 既存サマリは一般にO(n)で肥大化する【問題点】【ビッグデータ非対応】
新技術により O(log n) に抑制可能

17

例. 地震データの異常イベント検知• 以前に出現したことのありそうな時系列データかどうかで異常イベント(火山性噴火) をリアルタイム検知する• 高感度地震観測網 開田観測点の地震計 (Hinet U成分) 60Hz データ- 2014年9月27日10:00AM – 13:00PM までの分単位の時系列データ- 2012年, 2013年それぞれの同時間帯の時系列パターンとの比較
出現感度

2014年9月27日 10:00AM~13:00PM

2012年との比較
2013年との比較

御嶽山 噴火

1000
1005
1010
1015
1020
1025
1030
1035
1040
1045
1050
1055
1100
1105
1110
1115
1120
1125
1130
1135
1140
1145
1150
1155
1200
1205
1210
1215
1220
1225
123012351240
12451250
1255
1300

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

時系列パターンの出現感度の変化

18時刻例. 測光データの突発イベント検出• データ要約 & 確率不等式に基づく検知
同分布の時系列区間を一つのビン (bin) にまとめる
各ビンの発生確率をもとに異常スコアを算出する
入力ストリーム

検出器(Detector)

要約器(Sketcher)

上位3件

要約データ
bin1

bin2

bin3

突発リスト

11/22.05
bin4

11/23.10
11/24.03

11/22.05

11/23.10

11/24.3

統計サマリ
Thanapol Phungua-eng, Shigeyuki Sako, Yushi Nishikawa and Yoshitaka Yamamoto: “Elastic Data Binning: Time-Series
Sketching for Time-Domain Astrophysics Analysis”, ACM SIGAPP Applied Computing Review, Volume 23, pp. 5-22, 2023.7
19

M dwarf データ上のフレア検出例

51856511715955968_date20191130

20

例. センシングデータを用いた行動認証• スマートデバイスの各種センサーを利用
加速度, 角速度, 心拍, 皮膚温度, etc• センシングデータを保存した PSS-TS
個人の``行動指紋’’ とみなせる
PSS-TSを用いたゼロトラスト認証の可能性
いつもと異なる非定常行動の識別• 見守り・盗難防止といったセキュリティ分野へ利用
加速度データの例

ウォーキング

ジョギング

ランニング
21

発表のまとめ• ストリームデータ処理とデータ要約 (サマリ)• 時系列データ要約の説明
PSS-TS: 高速・超軽量なデータ構造• PSS-TSの応用可能性
インメモリ処理によるリアルタイム検索
エビデンスに基づく異常検知
自然科学データを用いた科学発見
センシングデータを用いた行動認証の例

22

企業への期待• アプリケーションを探索したい。
• リアルタイム解析を扱う領域での可用性検証を実施することで明確になると考えている。
• エッジ側でのデータ管理やリアルタイム分析に従事する企業との共同研究を希望。
• スマートデバイスのアプリ開発等でセキュリティ分野への展開を考えている企業には、本技術の導入は有効と思われる。

本技術に関する知的財産権• 発明の名称：データ操作プログラム、データ操作システム、およびデータ操作方法• 出願番号• 出願人• 発明者：特願2022-17871：静岡大学：山本泰生、山本裕介

産学連携の経歴
期間 (年度)• 2014-2017 JSTさきがけに採択• 2017-2020 科研基盤研究(C)に採択• 2020-2023 科研基盤研究(C)に採択• 2023-2025 JST可能性検証に採択【共同研究】• 2020-2024 ヤマハ発動機• 2021-2022 メンテック• 2022-2023 デンソー
• 2023-2024 サッポロビール

お問い合わせ先
国立大学法人静岡大学
イノベーション社会連携推進機構
ＴＥＬ ０５３－４７８ － １７１０
ＦＡＸ ０５３－４７８ － １７１１
e-mail sangakucd＠adb.shizuoka.ac.jp