作者：黎偉斌、胡熠、王皓

背景

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

異常點(diǎn)（outlier）是一個(gè)數(shù)據(jù)對象，它明顯不同于其他的數(shù)據(jù)對象。如下圖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)示例

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

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

1.時(shí)間序列

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

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

1.1.1 簡單移動(dòng)平均（Simple Moving Average,SMA）

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

適用于：

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

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

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

由于簡單移動(dòng)平均對窗口內(nèi)所有的數(shù)據(jù)點(diǎn)都給予相同的權(quán)重，對近期的最新數(shù)據(jù)不夠敏感，預(yù)測值存在滯后性。按著這個(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)平均比簡單移動(dòng)平均對近期的變化更加敏感，加權(quán)移動(dòng)平均的滯后性小于簡單移動(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è)無窮級數(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之間。越大，過去的觀測值衰減得越快。

1.2 同比和環(huán)比

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

同比和環(huán)比計(jì)算公式如圖2所示。適合數(shù)據(jù)呈周期性規(guī)律的場景中。如：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)異常檢測(STL+GESD)

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

(1)先將指標(biāo)做STL時(shí)序分解，得到seasonal，trend，residual成分，如圖3所示；
(2)用GESD (generalized extreme studentized deviate)算法對trend+residual成分進(jìn)行異常檢測；
(3)為增強(qiáng)對異常點(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ù)為：

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

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

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

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

，具體來說，對于，可以計(jì)算：

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

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

假設(shè)n維的數(shù)據(jù)集合，且每一個(gè)變量均符合高斯分布，可以計(jì)算n維的均值向量的協(xié)方差矩陣：

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

2.4 馬氏距離(Mahalanobis distance)

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

其中是協(xié)方差矩陣。可以對數(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)檢測

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

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

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

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

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

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

4.線性方法（矩陣分解和PCA降維）

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

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

其中P是一個(gè)維正交矩陣，它的每一列都是的特征向量。D是一個(gè)維對角矩陣，包含了特征值。在圖形上，一個(gè)特征向量可以看成2維平面上的一條線，或者高維空間里面的一個(gè)平面。特征向量所對應(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.分布

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

5.1 相對熵（KL散度）

相對熵（KL散度）可以衡量兩個(gè)隨機(jī)分布之間的距離，當(dāng)兩個(gè)隨機(jī)分布相同時(shí)，它們的相對熵為零，當(dāng)兩個(gè)隨機(jī)分布的差別增大時(shí)，它們的相對熵也會(huì)增大。所以相對熵可以用于比較兩個(gè)分布的相似度。設(shè)是兩個(gè)概率分布的取值，則對應(yīng)相對熵為。

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檢測結(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è)簇中。孤立森林檢測到的異常邊界為圖7中紅色線條，它能正確地檢測到所有黑色異常點(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è)備上有對應(yīng)的會(huì)員登錄過，容易看出device_1、device_2、device_3、device_4是同人，可以根據(jù)場景用于判斷作弊，常用于挖掘團(tuán)伙作弊。

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

最大聯(lián)通圖的前提條件是每條邊必須置信。適用場景：找所有連通關(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)簽傳播聚類的子圖間可以有少量連接。適用場景：節(jié)點(diǎn)之間“高內(nèi)聚低耦合”。圖10用最大聯(lián)通圖得1個(gè)子圖，用標(biāo)簽傳播聚類得2個(gè)子圖。

8.行為序列（馬爾科夫鏈）

如圖11所示，用戶在搜索引擎上有5個(gè)行為狀態(tài)：頁面請求（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)移矩陣。針對每一個(gè)待檢測用戶行為序列，易得該序列的概率值，概率值越大，越像正常用戶行為。

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

上述方法都是無監(jiān)督方法，實(shí)現(xià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ù)評估模型的效果。

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

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

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í)別作弊。

圖12.Wide&Deep模型

10.其他問題

10.1 常用選擇閾值的思路

上述各種方法都需要計(jì)算異常閾值，可以用下述思路先選閾值，再用轉(zhuǎn)化數(shù)據(jù)驗(yàn)證該閾值的合理性。

a.無監(jiān)督方法：使用分位點(diǎn)定閾值、找歷史數(shù)據(jù)的分布曲線的拐點(diǎn)；

b.有監(jiān)督模型：看驗(yàn)證集的準(zhǔn)召曲線

10.2 非高斯分布轉(zhuǎn)高斯分布

有些特征不符合高斯分布，那么可以通過一些函數(shù)變換使其符合高斯分布，以便于使用上述統(tǒng)計(jì)方法。常用的變換函數(shù)：，其中c為非負(fù)常數(shù)；，c為0-1之間的一個(gè)分?jǐn)?shù)。