一些經典的

基于統計的時序異常檢測

3σ檢測

該算法假設資料符合正态分布，根據3σ準則，數值分布在（μ-3σ,μ+3σ)中的機率為99.73%。

則認為在該範圍之外的均為異常點。

箱形圖

簡單來說，該算法不假設資料的分布，根據資料的1/4（假設為q1）和3/4分位點（假設為q2），設計正常資料的上下限：

無監督異常檢測算法

無監督的異常檢測又名為 Outlier Detection，即離群點檢測。

基于密度的方法

Local Outlier Factor 局部異常因子

SIGMOD 2000 引用量 7800+

該算法的主要思想在于根據局部密度（local density）來判斷樣本是否異常：一個正常樣本的局部密度應當與相鄰樣本的局部密度相似，而異常樣本的局部密度則會小很多。

該算法最核心的部分是關于資料點密度的刻畫。

該算法中有幾個關鍵的概念：

k-距離：某一點和距離該點第k近的點之間距離（不包括該點）；

k-距離鄰域：某一點的直線距離不超過該點的k-距離的所有點的集合（該集合中至少應有k個元素）；

可達距離：

即點j和i之間的距離和點j的k-距離的較大值；

如下圖所示：

局部可達密度（local reachablity density）：

直覺地說，某一點的局部可達密度是該點的的k近鄰點的平均可達距離的倒數。顯然，距離越短，密度越大，可達距離起到了平滑的作用。

局部異常因子（local outlier factor）：

局部異常因子反映了某點為異常值的程度。它是 該點的k近鄰點的平均局部可達密度 與 該點的平均可達密度 的比值。LOF算法衡量一個資料點的異常程度，并不是看它的絕對局部密度，而是看它跟周圍鄰近的資料點的相對密度。這樣做的好處是可以允許資料分布不均勻、密度不同的情況。

有關LOF有效性的證明，可以參考原文：LOF.pdf

DAGMM ：Deep Autoencoding Gaussian Mixture Model for Unsupervised Anomaly Detection

2018年ICLR 引用量1000+

基于密度的異常檢測存在的問題：Especially, when the dimensionality of input data becomes higher, it is more difficult to perform density estimation in the original feature space, as any input sample could be a rare event with low probability to observe。

簡單來說，就是在高維空間中，整體的密度分布都會比較低，難以有效地通過密度來區分異常點。為了解決該問題，現有方法通過降維+密度估計的二階段形式來進行異常檢測，這樣做的問題在于第一步的降維對于後續行為并不感覺，可能會導緻異常的資訊被舍棄了。

為了解決這一問題，該方法提出了Deep Autoencoding Gaussian Mixture Model（DAGMM，深度自編碼高斯混合模型）

首先，DAGMM提出了一個Compression Network，通過一個自編碼器同時得到降維結果和重構誤差，作者認為這兩部分特征可以更為充分地表示異常點；

其次，DAGMM使用一個Gaussian Mixture Model（GMM，高斯混合模型）來進行密度估計。GMM通常利用EM算法進行求解（為什麼不用梯度下降呢？可以參考https://spaces.ac.cn/archives/4277），但EM算法無法與前面的降維過程進行聯合優化。為了解決該問題，DAGMM提出了一個Estimation Network，該網絡以Compression Network的結果作為輸入，輸出每一個樣本的Mixture Membership Prediction，即将EM算法的E步驟中的樣本屬于各子分布的機率替換為端到端架構中子Estimation network的輸出。

E步（根據現有MLN的參數，得到z的分布，也就是樣本隸屬于不同高斯分布的機率分布）：

正常來說，這一部分應該是根據GMM的參數來算的，但是為了聯合優化，改用了一個MLN用來代替。

M步（根據z的分布，估計高斯分布的參數，并對E步中的參數進行更新）：

這三項分别表示第k個高斯分布的混合機率、均值和協方差。

Loss函數：

Loss分為三個部分，分别是：

1. 自編碼網絡的重構誤差；
2. 高斯混合模型的似然函數；

1. 正則化，防止 GMM 中的協方差矩陣的對角線上的值變為0 并最終導緻矩陣不可逆。

基于聚類的方法

SVDD：Support Vector Domain Description

SVDD屬于是One Class SVM問題的一種解決方法。One Class SVM問題是指在僅有一類資料的情況下進行分類，比方說，有一個小和尚，他從小在寺廟長大，從來都隻見過男生，沒見過女生，那麼對于一個男性，他能很快地基于這個男性與他之前接觸的男性有類似的特征，給出這個人是男性的答案。但如果是一個女性，他會發現，這個女性與他之前所認知的男性的特征差異很大，進而會得出她不是男性的判斷。這類方法主要應用于新值檢測（novelty detection），要求資料中不含有異常點。但在實際場景中，由于樣本空間并不會找得特别好，也可以嘗試用于異常值檢測。

SVDD的主要思想在于，找一個采用一個超球體來對空間進行劃分。該算法在特征空間中獲得資料周圍的球形邊界，期望最小化這個超球體的體積，進而最小化異常點資料的影響。

其中，R是超球體半徑，a是超球體的球心，具體的求解過程不在此闡述。

Deep SVDD：Deep One-Class Classification

ICML 2018 引用量1000+

在SVDD的基礎上，通過一個神經網絡來進行點的映射：

問題來了：如何去優化這個神經網絡呢？參考上面的優化目标設計loss即可。

優化目标如下：

該優化目标分别三項：

1. 第一項跟SVDD一樣，希望以一個最小的超球體來對空間進行劃分；
2. 第二項是一個懲罰項，要求資料盡可能落在超球體内靠近邊緣的位置；其中v是一個用于進行trade-off的超參數，允許部分的點落在超球體外；
3. 第三項是一個權重衰減的正則化項。

基于重構的方法

Variational Autoencoder based Anomaly Detection using Reconstruction Probability

首爾大學 2015 引用量1000+

前面的異常檢測方法會首先對高維的資料特征進行降維來更好地區分出異常資料，重新将這些低維特征映射回高維空間的行為叫做重構（reconstruction），重構後的結果與原始資料的差異叫做重構誤差（reconstruction error），重構誤差越大，則為異常點的機率越高。

本文提出了一個基于變分自編碼器（variational autoencoders， VAE）的異常檢測算法。

一句話概括VAE：希望建構一個從隐變量z生成目标資料x的模型g，其中z提前假設服從某種分布。

從神經網絡的視角來看，VAE的優化loss如下所示：

其中第一項是重構誤差（reconstruction loss），即極大化樣本的似然；第二項通過一個KL散度來控制z的分布近似于一個标準的正态分布，避免模型對于類似的輸入所得到的q差别過大。

該圖來自：https://spaces.ac.cn/archives/5253

上圖展示了VAE作用的全過程，可以看出來，在推理階段，使用VAE的步驟如下：

基于VAE的異常檢測：

簡單來說，由于我們的最終目标是異常檢測，并不是真的要去生成資料，是以将原本的資料x從decoder中重新生成的機率的作為資料x是否為異常的評價名額，稱之為重構機率（reconstruction probability）。如果重構機率低于所設定的門檻值，則認為是異常點。

值得注意的是，訓練的時候需要用不含有異常點的資料來訓練。

Dount ：Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications

WWW 2018 清華&阿裡出品 引用量500+

該算法同樣是基于變分自編碼器（VAE，Variational AutoEncoder）的：通過VAE來重構時間序列，并根據重構誤差來判斷異常點：

不同的地方在于，該方法針對的是時序的KPIs(key performance indicators)資料，相比較于上文主要有以下兩點不同：

1. 在原始VAE上做了一些改進，針對KPI異常檢測這個場景增加了一些細節上的優化，如missing data injection、MCMC等等；
2. 打破了VAE必須在不含有異常點的資料上進行訓練的限制；

Unsupervised Anomaly Detection with Generative Adversarial Networks to Guide Marker Discovery

IPMI 2017 引用量 1500+

利用強化學習來進行異常檢測。

基于時間序列預測的異常檢測

時序資料是存在前後關系的，可以根據過往資料對未來的資料進行拟合，然後根據預測出來的資料與實際資料的誤內插補點，通過3sigma來判斷誤內插補點是否正常（假設曆史資料的誤內插補點服從正态分布），進而判斷資料點是否異常。時序預測模型通常是通過尋找曆史資料之間的自相關性，來預測未來（假設未來将重複曆史的走勢），要求序列必須是平穩的，平穩性是時間序列分析的基礎。

一般來說，會首先想辦法讓資料變得平穩（例如STL算法、一階差分），再采用時序預測方法（例如ARMA 、Holt-Winter模型）來進行拟合。

什麼是平穩性？

通常情況下時間序列分析讨論的是弱平穩序列。弱平穩性的定義：

1. 均值 u 是與時間 t 無關的常數；
2. 對于任意時刻 t 和任意時間間隔 k，時間序列 z_t 與 z_{t−k} 的自協方差 r_k 隻與 k 有關，與 t 無關。

對于一個時間序列，通常采用 ADF 檢驗（機關根檢驗）的方式來判斷其是否平穩。

如何讓資料變平穩？

STL算法

STL（Seasonal and Trend decomposition using Loess）是一個非常通用和穩健強硬的分解時間序列的方法，其中Loess是一種估算非線性關系的方法。這裡不展開進行介紹。

STL的分解結果如下圖所示：

一階差分、二階差分

• 一階差分就是連續相鄰兩項之差。當自變量從x變到x+1時，函數y=y(x)的改變量∆yx=y(x+1)-y(x)，(x=0，1，2，......)稱為函數 y(x)在點x的一階差分，記為∆y_x=y_(x+1)-y_x，(x=0，1，2，......)。
• 重複上述動作，做兩次相同的動作，即再在一階差分的基礎上用後一個數值再減上一個數值一次，就叫“二階差分"。

時序預測算法

https://zhuanlan.zhihu.com/p/421710621

ARIMA模型

ARIMA(p, d, q)由三個部分組成：

• AR(p)：AR是autoregressive的縮寫，表示自回歸模型，含義是目前時間點的值等于過去若幹個時間點的值的回歸——因為不依賴于别的解釋變量，隻依賴于自己過去的曆史值，故稱為自回歸；如果依賴過去最近的p個曆史值，稱階數為p，記為AR(p)模型。
• I(d)：I是integrated的縮寫，含義是模型對時間序列進行了差分；因為時間序列分析要求平穩性，不平穩的序列需要通過一定手段轉化為平穩序列，一般采用的手段是差分；另外，還有一種特殊的差分是季節性差分S，即一些時間序列反應出一定的周期T，讓t時刻的值減去t-T時刻的值得到季節性差分序列。
• MA(q)：MA是moving average的縮寫，表示移動平均模型，含義是目前時間點的值等于過去若幹個時間點的預測誤差的回歸；預測誤差=模型預測值-真實值；如果序列依賴過去最近的q個曆史預測誤內插補點，稱階數為q，記為MA(q)模型。

值得注意的是，ARMA模型是針對平穩時間序列建立的模型，而ARIMA模型是針對非平穩時間序列模組化，不需要提前額外做差分。

首先在訓練集上确定參數(p, d, q)，然後即可在測試集上進行預測。

Holt-Winters 模型

Holt-Winters的主要思想在于認為離預測點越近的點，并且随着時間變化權重以指數方式下降，最終年代久遠的資料權重将接近于0。

Holt-Winters通常特指三次指數平滑法。

一次指數平滑：權值呈指數級遞減的移動平均法

其中

就表示經過平滑的值，為什麼叫指數平滑呢？

可以看到，所有先前的觀測值都對目前的平滑值産生了影響，但它們所起的作用随着參數 α 的幂的增大而逐漸減小。

二次指數平滑：額外考慮“趨勢”資訊

所謂趨勢，其實就是目前值相比較于上一個值增加或者減少的量。引入了一個變量t，其形式同于一階指數平滑，考慮到了s的變化情況。

三次指數平滑： 額外考慮季節性特征

在二次指數平滑的基礎上，又引入了一個變量p，形式也同于一階指數平滑，考慮到了周期性資訊。

Isolation Forest 孤立森林

周志華出品 引用量3000+

該方法的思想在于使用随機森林（random forest），“孤立”的思想展現在，首先随機選擇一個特征，然後随機地從最大值和最小值之間選擇一個數來“孤立”出一些樣本。

這樣不斷的分割可以看作是樹結構的，是以對于一個樣本來說，孤立出該樣本的次數等同于包含該樣本的葉子結點到跟結點的距離。

随機構造很多樹形成一個森林，這樣一來，每個樣本的平均距離可以用來度量該樣本的離群程度。這個距離越短，則說明該樣本越容易被孤立出來，也就更像一個異常點。

SR(Spectral Residual)算法:Time-Series Anomaly Detection Service at Microsof

該算法的思想來自于計算機視覺中的顯著性檢驗，簡單來說，大量圖檔做均值之後的log頻譜趨近于一條直線：

那麼一張圖檔的log頻譜減去平均圖檔的log頻譜就是其顯著部分，做差之後進行反傅立葉變換複原圖檔得到顯著區域。

對應到時間序列資料，以一定長度的滑動視窗序列作為輸入，分别計算其振幅頻譜和相位頻譜，然後對振幅頻譜取log，再對log後的結果做卷積來近似出平均log頻譜，并将log振幅頻譜減去平均log頻譜（這個值就是sepctral residual，譜殘差），最後通過exp和反傅立葉變化得到saliency map（顯著性圖）。在顯著性圖中比較特别的點可能對應着異常點。

得到顯著性圖之後，就可以通過一些簡單的政策來找到其中比較特别的點，例如：

另外，由于SR算法在異常點處于序列中間時效果較好，是以可以在執行SR算法之前簡單地對曲線進行延長：

Anomaly Transformer：Time Series Anomaly Detection with Association Discrepancy

ICLR 2022 Spotlight 清華大學 引用量 30+

首先，Transformers通過自注意力（self-attention）機制模組化了時間序列上不同時間點之間的關聯關系，這種關聯關系給我們提供了時序上下文的資訊，例如趨勢、周期等。但是由于在實際場景中，異常點的數量往往遠小于正常點的數量，是以很難将異常點與整個序列關聯起來；由于時間序列的連續性，往往異常點會與其相鄰的點又比較強的關聯性。與此相反，正常點則會與整個序列都會有較強的關聯性。這種整個序列和鄰近先驗之間的關聯差異為時序異常檢測提供了天然的、強區分度的判據。

針對這一直覺，本文提出了Anomaly Transformer模型用于模組化時序關聯，同時利用極小極大（Minimax）關聯學習政策進一步突出正常、異常點之間差别，實作了基于關聯差異（Association Discrepancy）的時序異常檢測。

可以看到，Series-Association就是正常的attention，而Prior-Association是一個帶參數的、可學習的高斯核函數，其中心在對應時間點的索引上。這種設計可以利用高斯分布的單峰特點，使資料更加關注鄰近的點。

為了量化正常點和異常點的差別，定義了如下的關聯差異：

最終優化的目标如下，利用重建誤差來進行模型優化的同時，使用了一個額外關聯差異損失來增大關聯差異，這樣可以使得異常點的重建更加的艱難，進而更加可辨識：

然而直接最小化關聯差異将使得高斯核的尺度參數σ急劇變小，結果就會導緻先驗分布無意義。是以，為了更好的控制關聯學習的過程，本文采用了一種Minimax政策。在最小化階段，我們讓先驗關聯P近似從原始時序中學得的序列關聯S，該過程将使得先驗關聯适應不同的時序模式。在最大化階段，我們優化序列關聯S來最大化關聯之間的差異，該過程将使得序列關聯更加注意非臨接的點，使得異常點的重建更加困難。

最終，異常檢測的依據如下：

一句話總結：重構誤差越大，關聯差異越小，則該點為異常點的可能性就越大。

時序異常檢測開源算法庫

TODS：https://tods-doc.github.io/

pyod：https://pyod.readthedocs.io/en/latest/

配套的有一個benchmark：https://github.com/Minqi824/ADBench，可以一起使用。

異常檢測的資源整合：https://github.com/yzhao062/anomaly-detection-resources

Reference

綜述、benchmark：

1. 隻針對時間序列的OD

Revisiting Time Series Outlier Detection: Definitions and Benchmarks ：

Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection

1. 針對廣義的OD

ADBench: Anomaly Detection Benchmark

sklearn異常檢測算法庫：https://scikit-learn.org/stable/modules/outlier_detection.html?highlight=outli

https://zhuanlan.zhihu.com/p/142320349

作者:故黎

來源:微信公衆号:螞蟻品質AnTest

出處:https://mp.weixin.qq.com/s/wndsBX8p13gUVvf7gQu9tA