異常檢測(cè)的N種方法，阿里工程師都盤出來了

作者：黎偉斌、胡熠、王皓 2019-05-22 10:07:26

互聯(lián)網(wǎng)黑產(chǎn)盛行，其作弊手段層出不窮，導(dǎo)致廣告效果降低，APP推廣成本暴增。精準(zhǔn)識(shí)別作弊是互聯(lián)網(wǎng)公司和廣告主的殷切期望。

背景

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

[[266003]]

異常點(diǎn)(outlier)是一個(gè)數(shù)據(jù)對(duì)象，它明顯不同于其他的數(shù)據(jù)對(duì)象。如下圖1所示，N1、N2區(qū)域內(nèi)的點(diǎn)是正常數(shù)據(jù)。而離N1、N2較遠(yuǎn)的O1、O2、O3區(qū)域內(nèi)的點(diǎn)是異常點(diǎn)。

圖1.異常點(diǎn)示例

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

近期使用多種算法挖掘異常點(diǎn)，下面從不同視角介紹異常檢測(cè)算法的原理及其適用場(chǎng)景，考慮到業(yè)務(wù)特殊性，本文不涉及特征細(xì)節(jié)。

1.時(shí)間序列

1.1 移動(dòng)平均(Moving Average，MA)

移動(dòng)平均是一種分析時(shí)間序列的常用工具，它可過濾高頻噪聲和檢測(cè)異常點(diǎn)。根據(jù)計(jì)算方法的不同，常用的移動(dòng)平均算法包括簡(jiǎn)單移動(dòng)平均、加權(quán)移動(dòng)平均、指數(shù)移動(dòng)平均。假設(shè)移動(dòng)平均的時(shí)間窗口為T，有一個(gè)時(shí)間序列：

1.1.1 簡(jiǎn)單移動(dòng)平均(Simple Moving Average,SMA)

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

適用于：

a.對(duì)噪聲數(shù)據(jù)進(jìn)行平滑處理，即用移動(dòng)均值替代當(dāng)前時(shí)刻取值以過濾噪聲;

b.預(yù)測(cè)未來的取值。

1.1.2 加權(quán)移動(dòng)平均(Weighted Moving Average, WMA)

由于簡(jiǎn)單移動(dòng)平均對(duì)窗口內(nèi)所有的數(shù)據(jù)點(diǎn)都給予相同的權(quán)重，對(duì)近期的***數(shù)據(jù)不夠敏感，預(yù)測(cè)值存在滯后性。按著這個(gè)思路延伸，自然的想法就是在計(jì)算移動(dòng)平均時(shí)，給近期的數(shù)據(jù)更高的權(quán)重，而給窗口內(nèi)較遠(yuǎn)的數(shù)據(jù)更低的權(quán)重，以更快的捕捉近期的變化。由此便得到了加權(quán)移動(dòng)平均和指數(shù)移動(dòng)平均。

加權(quán)移動(dòng)平均比簡(jiǎn)單移動(dòng)平均對(duì)近期的變化更加敏感，加權(quán)移動(dòng)平均的滯后性小于簡(jiǎn)單移動(dòng)平均。但由于僅采用線性權(quán)重衰減，加權(quán)移動(dòng)平均仍然存在一定的滯后性。

1.1.3 指數(shù)移動(dòng)平均(Exponential Moving Average, EMA)

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

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

1.2 同比和環(huán)比

圖2.同比和環(huán)比

同比和環(huán)比計(jì)算公式如圖2所示。適合數(shù)據(jù)呈周期性規(guī)律的場(chǎng)景中。如：1.監(jiān)控APP的DAU的環(huán)比和同比，以及時(shí)發(fā)現(xiàn)DAU上漲或者下跌;2.監(jiān)控實(shí)時(shí)廣告點(diǎn)擊、消耗的環(huán)比和同比，以及時(shí)發(fā)現(xiàn)變化。當(dāng)上述比值超過一定閾值(閾值參考第10部分)則判定出現(xiàn)異常。

1.3 時(shí)序指標(biāo)異常檢測(cè)(STL+GESD)

STL是一種單維度時(shí)間指標(biāo)異常檢測(cè)算法。大致思路是：

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

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

(3)為增強(qiáng)對(duì)異常點(diǎn)的魯棒性，將GESD算法中的mean,std等統(tǒng)計(jì)量用median, MAD(median absolute deviation)替換;

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

圖3.STL分解示例

2.統(tǒng)計(jì)

2.1 單特征且符合高斯分布

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

異常檢測(cè)的N種方法，阿里工程師都盤出來了

我們可以使用已有的樣本數(shù)據(jù)來預(yù)測(cè)總體中的，計(jì)方法如下：

2.2 多個(gè)不相關(guān)特征且均符合高斯分布

假設(shè)n維的數(shù)據(jù)集合形如：。

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

如果有一個(gè)新的數(shù)據(jù)，可以計(jì)算概率如下：

2.3 多個(gè)特征相關(guān)，且符合多元高斯分布

假設(shè)n維的數(shù)據(jù)集合異常檢測(cè)的N種方法，阿里工程師都盤出來了，且每一個(gè)變量均符合高斯分布，可以計(jì)算n維的均值向量的協(xié)方差矩陣：

如果有一個(gè)新的數(shù)據(jù)，可以計(jì)算概率：

2.4 馬氏距離(Mahalanobis distance)

對(duì)于一個(gè)多維列向量的數(shù)據(jù)集合D，假設(shè)是均值向量，那么對(duì)于數(shù)據(jù)集D中的任意對(duì)象，從到的馬氏距離是：

其中是協(xié)方差矩陣。可以對(duì)數(shù)值進(jìn)行排序，如果數(shù)值過大，那么就可以認(rèn)為點(diǎn)是離群點(diǎn)。

2.5 箱線圖

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

圖4.箱線圖算法示意圖

3.距離

3.1、基于角度的異常點(diǎn)檢測(cè)

圖5.點(diǎn)集和角度

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

D是點(diǎn)集，則對(duì)于任意不同的點(diǎn)，點(diǎn)X的所有角度的方差為：

異常點(diǎn)的上述方差較小。該算法的時(shí)間復(fù)雜度是，適合數(shù)據(jù)量N較小的場(chǎng)景。

3.2 基于KNN的異常點(diǎn)檢測(cè)

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

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

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

假設(shè)X是一個(gè)p維的數(shù)據(jù)集合，有N個(gè)樣本，它的協(xié)方差矩陣是。那么協(xié)方差矩陣就可以分解為：。

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

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

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

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

圖6.矩陣變換示意圖

定義數(shù)據(jù)的異常值分為：

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

5.分布

即對(duì)比基準(zhǔn)流量和待檢測(cè)流量的某個(gè)特征的分布。

5.1 相對(duì)熵(KL散度)

相對(duì)熵(KL散度)可以衡量?jī)蓚€(gè)隨機(jī)分布之間的距離，當(dāng)兩個(gè)隨機(jī)分布相同時(shí)，它們的相對(duì)熵為零，當(dāng)兩個(gè)隨機(jī)分布的差別增大時(shí)，它們的相對(duì)熵也會(huì)增大。所以相對(duì)熵可以用于比較兩個(gè)分布的相似度。設(shè)是兩個(gè)概率分布的取值，則對(duì)應(yīng)相對(duì)熵為異常檢測(cè)的N種方法，阿里工程師都盤出來了。

5.2 卡方檢驗(yàn)

卡方檢驗(yàn)通過檢驗(yàn)統(tǒng)計(jì)量來比較期望結(jié)果和實(shí)際結(jié)果之間的差別，然后得出實(shí)際結(jié)果發(fā)生的概率。其中O代表觀察值，E代表期望值。這個(gè)檢驗(yàn)統(tǒng)計(jì)量提供了一種期望值與觀察值之間差異的度量辦法。***根據(jù)設(shè)定的顯著性水平查找卡方概率表來判定。

6.樹(孤立森林)

圖7.iForest檢測(cè)結(jié)果

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

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

圖8.iForest切割過程

7.圖

7.1 ***聯(lián)通圖

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

如圖9所示，device是設(shè)備id，mbr是會(huì)員id，節(jié)點(diǎn)之間有邊表示設(shè)備上有對(duì)應(yīng)的會(huì)員登錄過，容易看出device_1、device_2、device_3、device_4是同人，可以根據(jù)場(chǎng)景用于判斷作弊，常用于挖掘團(tuán)伙作弊。

圖9.***聯(lián)通圖結(jié)果

***聯(lián)通圖的前提條件是每條邊必須置信。適用場(chǎng)景：找所有連通關(guān)系。當(dāng)數(shù)據(jù)中存在不太置信的邊時(shí)，需要先剔除臟數(shù)據(jù)，否則會(huì)影響***聯(lián)通圖的效果。

7.2 標(biāo)簽傳播聚類

標(biāo)簽傳播圖聚類算法是根據(jù)圖的拓?fù)浣Y(jié)構(gòu)，進(jìn)行子圖的劃分，使得子圖內(nèi)部節(jié)點(diǎn)的連接較多，子圖之間的連接較少。標(biāo)簽傳播算法的基本思路是節(jié)點(diǎn)的標(biāo)簽依賴其鄰居節(jié)點(diǎn)的標(biāo)簽信息，影響程度由節(jié)點(diǎn)相似度決定，通過傳播迭代更新達(dá)到穩(wěn)定。圖10中的節(jié)點(diǎn)經(jīng)標(biāo)簽傳播聚類后將得2個(gè)子圖，其中節(jié)點(diǎn)1、2、3、4屬于一個(gè)子圖，節(jié)點(diǎn)5、6、7、8屬于一個(gè)子圖。

圖10.標(biāo)簽傳播聚類算法的圖結(jié)構(gòu)

標(biāo)簽傳播聚類的子圖間可以有少量連接。適用場(chǎng)景：節(jié)點(diǎn)之間“高內(nèi)聚低耦合”。圖10用***聯(lián)通圖得1個(gè)子圖，用標(biāo)簽傳播聚類得2個(gè)子圖。

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

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

圖11.用戶行為狀態(tài)圖

統(tǒng)計(jì)正常行為序列中任意兩個(gè)相鄰的狀態(tài)，然后計(jì)算每個(gè)狀態(tài)轉(zhuǎn)移到其他任意狀態(tài)的概率，得狀態(tài)轉(zhuǎn)移矩陣。針對(duì)每一個(gè)待檢測(cè)用戶行為序列，易得該序列的概率值，概率值越大，越像正常用戶行為。

9.有監(jiān)督模型

上述方法都是無監(jiān)督方法，實(shí)現(xiàn)和理解相對(duì)簡(jiǎn)單。但是由于部分方法每次使用較少的特征，為了全方位攔截作弊，需要維護(hù)較多策略;另外上述部分方法組合多特征的效果取決于人工經(jīng)驗(yàn)。而有監(jiān)督模型能自動(dòng)組合較多特征，具備更強(qiáng)的泛化能力。

9.1 機(jī)器學(xué)習(xí)模型GBDT

樣本：使用前面的無監(jiān)督方法挖掘的作弊樣本作為訓(xùn)練樣本。如果作弊樣本仍然較少，用SMOTE或者GAN生成作弊樣本。然后訓(xùn)練GBDT模型，用轉(zhuǎn)化數(shù)據(jù)評(píng)估模型的效果。

9.2 深度學(xué)習(xí)模型Wide&Deep

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

deep則是利用神經(jīng)網(wǎng)絡(luò)自由組合映射特征，泛化性強(qiáng)。deep部分本質(zhì)上挖掘一些樣本特征的更通用的特點(diǎn)然后用于判斷，但是有過度泛化的風(fēng)險(xiǎn)。

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

為了進(jìn)一步增加模型的泛化能力，可以使用前面的無監(jiān)督方法挖掘的作弊樣本作為訓(xùn)練樣本，訓(xùn)練Wide&Deep模型識(shí)別作弊。