背景

異常點檢測(Outlier detection)，又稱為離群點檢測，是找出與預期對象的行為差異較大的對象的一個檢測過程。這些被檢測出的對象被稱為異常點或者離群點。異常點檢測在生產生活中有著廣泛應用，比如信用卡反欺詐、工業損毀檢測、廣告點擊反作弊等。

[[266003]]

異常點(outlier)是一個數據對象，它明顯不同于其他的數據對象。如下圖1所示，N1、N2區域內的點是正常數據。而離N1、N2較遠的O1、O2、O3區域內的點是異常點。

圖1.異常點示例

異常檢測的一大難點是缺少ground truth。常見的方法是先用無監督方法挖掘異常樣本，再用有監督模型融合多個特征挖掘更多作弊。

近期使用多種算法挖掘異常點，下面從不同視角介紹異常檢測算法的原理及其適用場景，考慮到業務特殊性，本文不涉及特征細節。

1.時間序列

1.1 移動平均(Moving Average，MA)

移動平均是一種分析時間序列的常用工具，它可過濾高頻噪聲和檢測異常點。根據計算方法的不同，常用的移動平均算法包括簡單移動平均、加權移動平均、指數移動平均。假設移動平均的時間窗口為T，有一個時間序列：

1.1.1 簡單移動平均(Simple Moving Average,SMA)

從上面的公式容易看出可以用歷史的值的均值作為當前值的預測值，在序列取值隨時間波動較小的場景中，上述移動均值與該時刻的真實值的差值超過一定閾值則判定該時間的值異常。

適用于：

a.對噪聲數據進行平滑處理，即用移動均值替代當前時刻取值以過濾噪聲;

b.預測未來的取值。

1.1.2 加權移動平均(Weighted Moving Average, WMA)

由于簡單移動平均對窗口內所有的數據點都給予相同的權重，對近期的***數據不夠敏感，預測值存在滯后性。按著這個思路延伸，自然的想法就是在計算移動平均時，給近期的數據更高的權重，而給窗口內較遠的數據更低的權重，以更快的捕捉近期的變化。由此便得到了加權移動平均和指數移動平均。

加權移動平均比簡單移動平均對近期的變化更加敏感，加權移動平均的滯后性小于簡單移動平均。但由于僅采用線性權重衰減，加權移動平均仍然存在一定的滯后性。

1.1.3 指數移動平均(Exponential Moving Average, EMA)

指數移動平均(Exponential Moving Average, EMA)和加權移動平均類似，但不同之處是各數值的加權按指數遞減，而非線性遞減。此外，在指數衰減中，無論往前看多遠的數據，該期數據的系數都不會衰減到 0，而僅僅是向 0 逼近。因此，指數移動平均實際上是一個無窮級數，即無論多久遠的數據都會在計算當期的指數移動平均數值時，起到一定的作用，只不過離當前太遠的數據的權重非常低。在實際應用中，可以按如下方法得到t時刻的指數移動平均： 

其中表示權重的衰減程度，取值在0和1之間。越大，過去的觀測值衰減得越快。

1.2 同比和環比 

圖2.同比和環比

同比和環比計算公式如圖2所示。適合數據呈周期性規律的場景中。如：1.監控APP的DAU的環比和同比，以及時發現DAU上漲或者下跌;2.監控實時廣告點擊、消耗的環比和同比，以及時發現變化。當上述比值超過一定閾值(閾值參考第10部分)則判定出現異常。

1.3 時序指標異常檢測(STL+GESD)

STL是一種單維度時間指標異常檢測算法。大致思路是：

(1)先將指標做STL時序分解，得到seasonal，trend，residual成分，如圖3所示;

(2)用GESD (generalized extreme studentized deviate)算法對trend+residual成分進行異常檢測;

(3)為增強對異常點的魯棒性，將GESD算法中的mean,std等統計量用median, MAD(median absolute deviation)替換;

(4)異常分輸出：abnorm_score = (value - median)/MAD, value為當前值，median為序列的中位數。負分表示異常下跌，正分表示異常上升。

圖3.STL分解示例

2.統計

2.1 單特征且符合高斯分布

如果變量x服從高斯分布：，則其概率密度函數為：

我們可以使用已有的樣本數據來預測總體中的，計方法如下：

2.2 多個不相關特征且均符合高斯分布

假設n維的數據集合形如：。

且每一個變量均符合高斯分布，那么可以計算每個維度的均值和方差，具體來說，對于，可以計算：

如果有一個新的數據，可以計算概率如下：

2.3 多個特征相關，且符合多元高斯分布

假設n維的數據集合，且每一個變量均符合高斯分布，可以計算n維的均值向量的協方差矩陣： 

如果有一個新的數據，可以計算概率： 

2.4 馬氏距離(Mahalanobis distance)

對于一個多維列向量的數據集合D，假設是均值向量，那么對于數據集D中的任意對象，從到的馬氏距離是：

其中是協方差矩陣。可以對數值進行排序，如果數值過大，那么就可以認為點是離群點。

2.5 箱線圖

箱線圖算法不需要數據服從特定分布，比如數據分布不符合高斯分布時可以使用該方法。該方法需要先計算***四分位數Q1(25%)和第三四分位數Q3(75%)。令IQR=Q3-Q1，然后算出異常值邊界點Q3+λ*IQR和Q1- λ*IQR，通常λ取1.5(類似于正態分布中的，如下圖4所示： 

圖4.箱線圖算法示意圖

3.距離

3.1、基于角度的異常點檢測 

 

圖5.點集和角度

如上圖5所示，現在有三個點X，Y，Z，和兩個向量，如果對任意不同的點Y，Z，變化都較小，則點X是異常點。通過余弦夾角公式易得角度：

 

D是點集，則對于任意不同的點，點X的所有角度的方差為：

 

異常點的上述方差較小。該算法的時間復雜度是，適合數據量N較小的場景。

3.2 基于KNN的異常點檢測

D是點集，則對于任意點，計算其K近鄰的距離之和Dist(K,X)。Dist(K,X)越大的點越異常。時間復雜度是，其中N是數據量的大小。

4.線性方法(矩陣分解和PCA降維)

基于矩陣分解的異常點檢測方法的主要思想是利用主成分分析(PCA)去尋找那些違反了數據之間相關性的異常點。為了找到這些異常點，基于主成分分析的算法會把數據從原始空間投影到主成分空間，然后再從主成分空間投影回原始空間。對于大多數的數據而言，如果只使用***主成分來進行投影和重構，重構之后的誤差是較小的;但是對于異常點而言，重構之后的誤差相對較大。這是因為***主成分反映了正常點的方差，***一個主成分反映了異常點的方差。

假設X是一個p維的數據集合，有N個樣本，它的協方差矩陣是。那么協方差矩陣就可以分解為：。

其中P是一個維正交矩陣，它的每一列都是的特征向量。D是一個維對角矩陣，包含了特征值。在圖形上，一個特征向量可以看成2維平面上的一條線，或者高維空間里面的一個平面。特征向量所對應的特征值反映了這批數據在這個方向上的拉伸程度。通常情況下，將特征值矩陣D中的特征值從大到小的排序，特征向量矩陣P的每一列也進行相應的調整。

數據集X在主成分空間的投影可以寫成Y=XP，注意可以只在部分的維度上做投影，使用top-j的主成分投影之后的矩陣為：。

其中是矩陣P的前j列，也就是說是一個維的矩陣。是矩陣Y的前j列，是一個維的矩陣。按同樣的方式從主成分空間映射到原始空間，重構之后的數據集合是。

其中是使用top-j的主成分重構之后的數據集，是一個維的矩陣。如圖6所示：

圖6.矩陣變換示意圖

定義數據的異常值分為：

其中表示的是top-j主成分占所有主成分的比例，特征值是按照從大到小的順序排列的。因此是遞增的，這就意味著j越大，越多的方差就會被算到中，因為是從 1 到 j 的求和。在這個定義下，偏差***的***個主成分獲得最小的權重，偏差最小的***一個主成分獲得了***的權重1。根據 PCA 的性質，異常點在***一個主成分上有著較大的偏差，因此會有更大的異常分。

5.分布

即對比基準流量和待檢測流量的某個特征的分布。

5.1 相對熵(KL散度)

相對熵(KL散度)可以衡量兩個隨機分布之間的距離，當兩個隨機分布相同時，它們的相對熵為零，當兩個隨機分布的差別增大時，它們的相對熵也會增大。所以相對熵可以用于比較兩個分布的相似度。設是兩個概率分布的取值，則對應相對熵為。

5.2 卡方檢驗

卡方檢驗通過檢驗統計量來比較期望結果和實際結果之間的差別，然后得出實際結果發生的概率。其中O代表觀察值，E代表期望值。這個檢驗統計量提供了一種期望值與觀察值之間差異的度量辦法。***根據設定的顯著性水平查找卡方概率表來判定。

6.樹(孤立森林)

圖7.iForest檢測結果

孤立森林(Isolation Forest)假設我們用一個隨機超平面來切割數據空間, 每切一次便可以生成兩個子空間。接著繼續用一個隨機超平面來切割每個子空間，循環下去，直到每個子空間里面只有一個數據點為止。那些密度很高的簇是需要被切很多次才能讓子空間中只有一個數據點，但是那些密度很低的點的子空間則很快就被切割成只有一個數據點。如圖7所示，黑色的點是異常點，被切幾次就停到一個子空間;白色點為正常點，白色點聚焦在一個簇中。孤立森林檢測到的異常邊界為圖7中紅色線條，它能正確地檢測到所有黑色異常點。

如圖8所示，用iForest切割4個數據，b和c的高度為3，a的高度為2，d的高度為1，d***被孤立，它最有可能異常。

 

圖8.iForest切割過程

7.圖

7.1 ***聯通圖

在無向圖G中，若從頂點A到頂點B有路徑相連，則稱A和B是連通的;在圖G中存在若干子圖，其中每個子圖中所有頂點之間都是連通的，但不同子圖間不存在頂點連通，那么稱圖G的這些子圖為***連通子圖。

如圖9所示，device是設備id，mbr是會員id，節點之間有邊表示設備上有對應的會員登錄過，容易看出device_1、device_2、device_3、device_4是同人，可以根據場景用于判斷作弊，常用于挖掘團伙作弊。

圖9.***聯通圖結果

***聯通圖的前提條件是每條邊必須置信。適用場景：找所有連通關系。當數據中存在不太置信的邊時，需要先剔除臟數據，否則會影響***聯通圖的效果。

7.2 標簽傳播聚類

標簽傳播圖聚類算法是根據圖的拓撲結構，進行子圖的劃分，使得子圖內部節點的連接較多，子圖之間的連接較少。標簽傳播算法的基本思路是節點的標簽依賴其鄰居節點的標簽信息，影響程度由節點相似度決定，通過傳播迭代更新達到穩定。圖10中的節點經標簽傳播聚類后將得2個子圖，其中節點1、2、3、4屬于一個子圖，節點5、6、7、8屬于一個子圖。

圖10.標簽傳播聚類算法的圖結構

標簽傳播聚類的子圖間可以有少量連接。適用場景：節點之間“高內聚低耦合”。圖10用***聯通圖得1個子圖，用標簽傳播聚類得2個子圖。

8.行為序列(馬爾科夫鏈)

如圖11所示，用戶在搜索引擎上有5個行為狀態：頁面請求(P)，搜索(S)，自然搜索結果(W)，廣告點擊(O)，翻頁(N)。狀態之間有轉移概率，由若干行為狀態組成的一條鏈可以看做一條馬爾科夫鏈。

圖11.用戶行為狀態圖

統計正常行為序列中任意兩個相鄰的狀態，然后計算每個狀態轉移到其他任意狀態的概率，得狀態轉移矩陣。針對每一個待檢測用戶行為序列，易得該序列的概率值，概率值越大，越像正常用戶行為。

9.有監督模型

上述方法都是無監督方法，實現和理解相對簡單。但是由于部分方法每次使用較少的特征，為了全方位攔截作弊，需要維護較多策略;另外上述部分方法組合多特征的效果取決于人工經驗。而有監督模型能自動組合較多特征，具備更強的泛化能力。

9.1 機器學習模型GBDT

樣本：使用前面的無監督方法挖掘的作弊樣本作為訓練樣本。如果作弊樣本仍然較少，用SMOTE或者GAN生成作弊樣本。然后訓練GBDT模型，用轉化數據評估模型的效果。

9.2 深度學習模型Wide&Deep

Wide&Deep通過分別提取wide特征和deep特征，再將其融合在一起訓練，模型結構如圖12所示。wide是指高維特征和特征組合的LR。LR高效、容易規模化(scalable)、可解釋性強。出現的特征組合如果被不斷加強，對模型的判斷起到記憶作用。但是相反的泛化性弱。

deep則是利用神經網絡自由組合映射特征，泛化性強。deep部分本質上挖掘一些樣本特征的更通用的特點然后用于判斷，但是有過度泛化的風險。

算法通過兩種特征的組合去平衡記憶(memorization)和泛化( generalization)。

為了進一步增加模型的泛化能力，可以使用前面的無監督方法挖掘的作弊樣本作為訓練樣本，訓練Wide&Deep模型識別作弊。

圖12.Wide&Deep模型

10.其他問題

10.1 常用選擇閾值的思路

上述各種方法都需要計算異常閾值，可以用下述思路先選閾值，再用轉化數據驗證該閾值的合理性。

a.無監督方法：使用分位點定閾值、找歷史數據的分布曲線的拐點;

b.有監督模型：看驗證集的準召曲線

10.2 非高斯分布轉高斯分布

有些特征不符合高斯分布，那么可以通過一些函數變換使其符合高斯分布，以便于使用上述統計方法。常用的變換函數：，其中c為非負常數;

，c為0-1之間的一個分數。

參考文獻：

[1] Charu C, Aggarwal, et al. Outlier Analysis Second Edition, Springer.2016

[2] Varun Chandola, Arindam Banerjee, et al. Anomaly Detection: A survey,ACM Computing Surveys. 2009

[3] Kalyan Veeramachaneni, Ignacio Arnaldo, et al. AI2: Training abig data machine to defend, In Proc. HPSC and IDS. 2016

[4] Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou, et al. Isolationforest, ICDM. 2008