データ分析関連のまとめ

データ分析・機械学習周りのもくもく会LTやイベント参加をまとめていきます

Ultrafast Local Outlier Detection from a Data Stream with Stationary Region Skipping

Ultrafast Local Outlier Detection from a Data Stream with Stationary Region Skipping(KDD2020 Accepted Papers)を読んでまとめました。
長いので、背景と概要に中身を少しまとめています。 解釈間違い等ある時がありますので、その場合指摘いただけると助かります。

目次

背景と概要

  • datastreamからのリアルタイムの外れ値検出がIoTの普及等により今後ますます重要な課題となっている。
    • これに対処するため、いくつかの密度ベースのアルゴリズムが提案されているが、アプリケーションの性能要求を満たすのに十分な速度のものが無い実情がある。
  • 本論文ではデータの分布がwindow slideを挟んでほとんど変化しない観測に基づいたアルゴリズムを採用。
    • window:時系列のdatastreamを区切る単位
    • データ分布がほどんど変化しない局所領域を特定し、その領域の密度更新をスキップするアルゴリズムSTAREを提案
    • 以下の2つのテクニックを使っている
      • data distribution approximation:カーネル密度分布をベースとしてカーネルの中心を固定する
      • cumulative net-change-based skip:密度分布の変化を時系列の累積で測る
  • アルゴリズム概要
    • 以下3フェイズで構成
      • Data distribution update
        • データ空間を分割したグリッドセルにおいてデータ点の数を分布の重みとする。
        • window間の各グリッドセルにおいてその重みの差(変化)を計算。
      • Stationary region skip
        • 上記の重み変化を調べ、その累積変化が閾値を超えない領域を定常領域として密度更新をスキップする。
        • 閾値を超えた部分において局所密度の更新を行う。
      • Top-𝑛 outlier detection
        • 局所密度からlocal outlier scoreを計算、これに基づきlocal outlierの検出を行う。

データポイントの偏り

実データはデータ空間内のいくつかの局所領域に偏っており、以下の図の様にデータ分布がある時間内でほぼ定常的となる場合がある。

f:id:yhiss:20201017155946p:plain
2次元のHTTP data set例(点線の中が定常的と取れる箇所)

Main idea

密度更新のスキップ

datastreamから局所的な外れ値検出を行うためにいくつかの密度ベースアルゴリズム(データポイントの密度を推定)があるが、既存のアルゴリズムでは密度の定常性を 無視しwindowがスライドする度にwindow内の全データ点の密度を更新している。
本論文では定常領域の密度更新をスキップしている。

  • 以下の図においてa:前のwindow、b:密度のアップデート、c:現在のwindowを示している
    • 前のwindowでは、x1・x3が外れ値となっている。
    • 現在のwindowではx2が新しい外れ値となり、x3も外れ値となっている。
  • 前と現在のwindow間でデータポイントの密度が変化するのは右側のみだが、既存アルゴリズムはbの上の様にglobalに更新する。
  • 新しいアルゴリズムではbの下の様に左の静止領域をスキップし、残りの局所領域の密度のみを更新する。

f:id:yhiss:20201017181815p:plain
2種類の密度更新アプローチ

スキップにおける課題

  • 定常領域スキップの概念実装には以下2つの大きな課題がある。

    • 1.データ点の密度変化を追跡することはデータ空間での度を実際に計算せず行う必要があり、コストがかかる。
    • 2.定常領域をスキップしても、外れ値検出の精度が損なわれない必要がある。

  • 本論文ではSTARE(local outlier detection by STAtionary REgion skipping)というアルゴリズムを提案。

    • カーネル密度推定(KDE)をベースとして以下2技術を採用している。
      • Data distribution approximation:
      • Cumulative net-change-based skip:STAREはカーネル中心分布の累積の変化が有意になる領域のみで密度更新を行う。

STAREアルゴリズム

問題設定

  • windowで分割されるdatstreamから密度ベースでtop-nのlocal outlier detactionを行う。
    • windowがスライドするたびに、最も高いlocal outlier scoresを持つn個のlocal outliersを検出する。

アルゴリズム概要

  • STAREアルゴリズムは、以下の図で示されているように3つのフェイズで構成されており、各windowでこれらを実行する。
    • Data distribution update
    • Stationary region skip
    • Top-𝑛 outlier detection

f:id:yhiss:20201107150223p:plain
アルゴリズム概要図

f:id:yhiss:20201107150603p:plain
本論文で使われている表記

f:id:yhiss:20201107150711p:plain
STAREの手順

フェイズ1:Data distribution update:

  • 小領域を定義し、その中のデータ点の数をカウント。そのカウントを小領域のカーネル中心の重みとする。カーネル中心はデータ点の位置とは無関係に小領域の中心となる。
  • データ空間を分割したグリッドセルを小領域とする。
  • 前のwindowと新しいwindow間の各小領域のカウントの正味変化を前のwindowの重み分布に反映し効率的な重みの更新を行う。
    • STAREでは \Delta \mathbb{G} としてカウントの重み分布グリッドの正味変化を管理し、以下のアルゴリズムに示すようにwindowスライド間において \Delta \mathbb{G} を計算する事で、更新を効率的に行う。

f:id:yhiss:20201107153039p:plain
分布更新のアルゴリズム

フェイズ2:Stationary region skip

  • 連続したwindow間の各小領域における重みの変化 \Delta \mathbb{G} を調べ、近傍のカーネル中心の累積変化が有意でない領域を定常領域とする。 これら定常領域での局所密度更新をスキップし、以下式で表される \Delta \mathbb{G} 付近のカーネル中心に属するデータポイントセット X_{affected}のみで局所密度を更新する。
 局所密度D(x)は以下のレンジとなる
 D_{low}(c) \leq D(x) \leq D_{up}(c)
 D_{low}(c) = \sum_{i=1}^{{\theta}_K} \cfrac{w_i} {\sum_{j=1}^{{\theta}_K} w_j } \prod_{l=1}^{d} K_{hl} (dist(kc^l, kc_i^l) + \cfrac{{\theta}_R}{2 \sqrt{d}})  
 D_{up}(c) = \sum_{i=1}^{{\theta}_K} \cfrac{w_i} {\sum_{j=1}^{{\theta}_K} w_j } \prod_{l=1}^{d} K_{hl} (dist(kc^l, kc_i^l) - \cfrac{{\theta}_R}{2 \sqrt{d}})  
 X_{affected} = \{ x | {\exists} (< kc_i, {\Delta} w_i  \in \Delta \mathbb{G}>)   \land (dist(x, kc_i)  \leq (dist(x, kc_{\theta K}))  \}
  • 更に以下で表されるwindowに蓄積された誤差Eがある閾値 \gammaに達するまで局所密度の更新をスキップする。
    • これにより、密度自身の定常性だけでなく(時系列での)近接的な定常性の利用が可能となっている。
    • \gamma=0とすると、密度変化が全くない箇所だけスキップする。
    • この閾値のトレードオフのバランスを取る最適値はアプリケーションに依存するが、実際のデータをつかった実験では \gamma=0.1が最適だと論文内で書かれている。
 E(x;t_c , t_l) = \sum_{t=t_l, ..., t_c} \cfrac{\sum_{\Delta w_j \in W_t(s;t_l)  } |\Delta w_j| }{\sum_{w_i \in KC(x;t_l) } w_i }

本フェイズのアルゴリズム概要は以下で表されている。

f:id:yhiss:20201107164558p:plain
Stationary Region Skipのアルゴリズム概要

フェイズ3:Top-𝑛 outlier detection

  • データ点のlocal outlier scoresに基づいてn個のlocal outliersを検出する。
  • 工程
    • 全てのグリッドセルにおいて、local outlier scoreを更新
    • スコアに基づいて候補グリッドセルを検出
    • n個のlocal outliersを検出
      以下式定義
 local \ outlier \ scoreS(x)は以下のレンジとなる
 S_{low}(c) = \cfrac{\mu - D_{up}(c)}{\sigma} \leq S(x) \leq S_up(c) = \cfrac{\mu - D_{low}(c)}{\sigma} 
 x \in X^d

 候補グリッドセルC_{cand}の決定式
 argmin_{C_{cand} \subseteq C } \{ | C_{cand} | \ such \ that | C_{cand} | \geq n \ \land \ min( \{ S_{low}(c) | c \in C_{cand} \} ) > max( \{ S_{up}(c) | c \in C- C_{cand} \} )   \}

f:id:yhiss:20201107181526p:plain
Outlier Detectionのアルゴリズム

結果

データセット

  • 以下1つの合成データと5つのリアルデータで検証(データ詳細は論文参照ください)
    • 合成データ
      • YahooA2
    • リアルデータ
      • YahooA1:人がラベルを付けた外れ値をもつYahooサービスのメトリクス
      • HTTP:外れ値としてラベル付けされたネットワーク攻撃を含むネットワークトラフィック
      • DLR:人に取り付けられたセンサーからの測定値
      • ECG:心電図信号から抽出された特徴量(異常な心拍信号は外れ値としてラベル付けされている)
      • FDC:半導体工場で収集されたセンサーの読み取った値

f:id:yhiss:20201107185332p:plain
データセットのパラメータ

アルゴリズム

f:id:yhiss:20201107185436p:plain

  • STAREにおけるskip有無や閾値の設定を変更した場合に、適切な閾値設定を行う事で精度を維持したまま計算時間を短縮できる結果を示している。

f:id:yhiss:20201107185704p:plain

参考文献

www.kdd.org