異常檢測演算法演變及學習筆記
【說在前面】本人部落格新手一枚，象牙塔的老白，職業場的小白。以下內容僅為個人見解，歡迎批評指正，不喜勿噴！[認真看圖][認真看圖]
【補充說明】異常檢測，又稱離群點檢測，有著廣泛應用。例如金融反欺詐、工業損毀檢測、電網竊電行為等！
一、基於時間序列分析
關於時間序列分析的介紹，歡迎瀏覽我的另一篇部落格：時間序列分析中預測類問題下的建模方案，這裡不再贅述。
1. 基於同比和環比
適合數據呈周期性規律的場景中。例如：
- 監控APP的DAU的環比和同比，及時發現DAU上漲或者下跌
- 監控實時廣告點擊、消耗的環比和同比，及時發現變化
當上述比值超過一定閾值，則判定出現異常。
2. 基於統計學模型預測
移動平均MA是一種分析時間序列的常用工具，它可過濾高頻雜訊和檢測異常點。
- 根據計算方法的不同，常用的移動平均演算法包括簡單移動平均、加權移動平均、指數移動平均。
- 在序列取值隨時間波動較小的場景中，上述移動均值與該時刻的真實值的差值超過一定閾值，則判定該時刻的值異常。
當然，還有ARMA、ARIMA、SARIMA等適用於時間序列分析的統計學模型，可以預測訊號並指出其中的異常值。
3. 基於時間序列分解
STL是一種單維度時間指標異常檢測演算法。大致思路是：
（1）先將指標做STL時序分解，得到seasonal、trend、residual成分。
（2）用ESD演算法對trend+residual成分進行異常檢測。
（3）為增強對異常點的魯棒性，將ESD演算法中的mean、std等統計量用median, MAD替換。
（4）異常分輸出：abnorm_score = (value – median)/MAD，負分表示異常下跌，正分表示異常上升。
當然，還有其他的時間序列分解演算法，例如STL、X12-ARIMA、STAMP等。
二、基於概率統計
一般會構建一個概率分布模型，並計算對象符合該模型的概率，把具有低概率的對象視為異常點。
還記得不，機器學習特徵工程中的RobustScaler方法，在做數據特徵值縮放的時候，利用數據特徵的分位數分布，將數據根據分位數劃分為多段，只取中間段來做縮放（例如只取25%分位數到75%分位數的數據做縮放等），這樣減小了異常數據的影響。
1. 單特徵且符合高斯分布
在正態分布的假設下，如果有一個新樣本x，當x的正態分布值小於某個閾值時，就可以認為這個樣本是異常的。
在正態分布中，μ-3σ<=x<=μ+3σ的區域包含了絕大部分數據，可以以此為參考，調整ε的值：
值得一提的是，如果有些特徵不符合高斯分布，可以通過一些函數變換，使其符合高斯分布，再使用基於統計的方法。
- 例如取log變換、求內積、指數變換等。
2. 多個特徵，不相關，且均符合高斯分布
可以直接對每個獨立特徵都進行單特徵下的異常檢測（參考1）。
3. 多個特徵，相關，且符合多元高斯分布
可以通過以下函數判斷一個樣本是否是異常的：
目的是設法根據訓練集求得μ和σ，以得到一個確定的多元分正態布模型。具體來說，通過最大似然估計量可以得出下面的結論：
其中Σ是協方差對角矩陣，最終求得的多元正態分布模型可以寫成：
關於最大似然估計量、協方差矩陣和多元正態分布最大似然估計的具體推導過程，這裡不詳細介紹。
4. 馬氏距離 Mahalanobis distance
其中S為二元高斯分布的協方差矩陣，為所有數據對象的均值。Mahalanobis距離越大，數據對象偏離均值越大，也就越異常。
5. G檢驗 Grubbs’ Test
Grubbs’ Test可理解為檢驗最大值、最小值偏離均值的程度是否為異常。
其中，O為觀測值，E為期望值。
為了將Grubbs’ Test擴展到k個異常值檢測，需要在數據集中逐步刪除與均值偏離最大的值（即最大值或最小值），同步更新對應的t分布臨界值，檢驗原假設是否成立。基於此，Rosner提出了Grubbs’ Test的泛化版ESD。
6. 箱線圖
箱線圖演算法不需要數據服從特定分布。該方法需要先計算第一四分位數Q1（25%）和第三四分位數Q3（75%）。
令IQR=Q3-Q1，然後算出異常值邊界點Q3+λIQR和Q1- λIQR，通常λ取1.5。
當然還有其他的統計方法，例如基於混合模型的異常檢測方法（假設正常和異常數據分布不同，然後用G檢驗）等，這裡不再展開。
三、基於距離
1. 基於角度的異常點檢測
2. 基於KNN的異常點檢測
D是點集，則對於任意點，計算其K近鄰的距離之和Dist(K，X)。Dist(K，X)越大的點越異常。
四、基於密度
基於距離的方法中，閾值是一個固定值，屬於全局性方法。但是有的數據集數據分布不均勻，有的地方比較稠密，有的地方比較稀疏，這就可能導致閾值難以確定。我們需要根據樣本點的局部密度資訊去判斷異常情況。
基於密度的方法主要有LOF、COF、ODIN、MDEF、INFLO、LoOP、LOCI、aLOCI等，具體實現這裡不具體介紹。
1. LOF
首先對於每一個數據點，找出它的K個近鄰，然後計算LOF得分，得分越高越可能是異常點。
LOF是一個比值，分子是K個近鄰的平均局部可達密度，分母是該數據點的局部可達密度。
- 可達密度是一個比值，分子是K-近鄰的個數，分母是K-近鄰可達距離之和。
- A到B的可達距離定義：A和B的真實距離與B的k-近鄰距離的最大值。
2. COF
LOF中計算距離是用的歐式距離，也是默認了數據是球狀分布，而COF的局部密度是根據最短路徑方法求出的，也叫做鏈式距離。
3. INFLO
LOF容易將邊界處的點判斷為異常，INFLO在計算密度時，利用k近鄰點和反向近鄰集合，改善了LOF的這個缺點。
4. LoOP
將LOF中計算密度的公式加了平方根，並假設近鄰距離的分布符合正態分布。
五、基於聚類
關於聚類演算法的介紹，歡迎瀏覽我的另一篇部落格：機器學習中的聚類演算法演變及學習筆記，這裡不再贅述。
此類方法主要有三種假設，三種假設下有各自的方法。
1. 假設一：不屬於任何聚類的點是異常點
主要方法：DBSCAN、SNN clustering、FindOut algorithm、WaveCluster Algorithm。
缺點：不能發現異常簇
2. 假設二：距離最近的聚類結果較遠的點是異常點
主要方法：K-Means、Self-Organizing Maps（SOM）、GMM。
主要步驟：首先進行聚類，然後計算樣例與其所屬聚類中心的距離，計算其所屬聚類的類內平均距離，用兩者的比值衡量異常程度。
缺點：不能發現異常簇
3. 假設三：稀疏聚類和較小的聚類里的點都是異常點
主要方法：CBLOF、LDCOF、CMGOS。
主要步驟：首先進行聚類，然後啟發式地將聚類簇分成大簇和小簇。
- 如果某一樣例屬於大簇，則利用該樣例和其所屬大簇計算異常得分
- 如果某一樣例屬於小簇，則利用該樣例和距離其最近的大簇計算異常得分
優點：考慮到了數據全局分布和局部分布的差異，可以發現異常簇
六、基於線性方法：矩陣分解和PCA降維
基於矩陣分解的異常點檢測方法的主要思想是利用主成分分析（PCA）去尋找那些違反了數據之間相關性的異常點。
為了找到這些異常點，基於主成分分析的演算法會把數據從原始空間投影到主成分空間，然後再從主成分空間投影回原始空間。
- 對於大多數的數據而言，如果只使用第一主成分來進行投影和重構，重構之後的誤差是較小的。
- 但是對於異常點而言，重構之後的誤差相對較大。
這是因為第一主成分反映了正常點的方差，最後一個主成分反映了異常點的方差。
七、基於分布
即對比基準數據和待檢測數據的某個特徵的分布。
1. 相對熵（KL散度）
相對熵（KL散度）可以衡量兩個隨機分布之間的距離。
- 當兩個隨機分布相同時，它們的相對熵為零。
- 當兩個隨機分布的差別增大時，它們的相對熵也會增大。
2. 卡方檢驗
卡方檢驗通過檢驗統計量來比較期望結果和實際結果之間的差別，然後得出實際結果發生的概率。
檢驗統計量提供了一種期望值與觀察值之間差異的度量辦法，最後根據設定的顯著性水平查找卡方概率表來判定。
八、基於樹模型
該類方法假設我們用一個隨機超平面來切割數據空間，每切一次便可以生成兩個子空間。接著繼續用一個隨機超平面來切割每個子空間，循環下去，直到每個子空間裡面只有一個數據點為止。
- 那些密度很高的簇是需要被切很多次才能讓子空間中只有一個數據點
- 那些密度很低的點的子空間則很快就被切割成只有一個數據點
此類方法不受球形鄰近的限制，可以劃分任意形狀的異常點。不同的方法區別主要在三個地方：特徵的選取、分割點的選取和分類空間打標籤的方案。此類方法主要包括iForest、SCiForest、RRCF。
1. iForest
此方法適用於異常點較少的情況，採用構造多個決策樹的方式進行異常檢測。
- 對數據集進行有放回抽樣，對每一次抽樣出來的樣本構建二叉樹。
- 構建二叉樹時，隨機選取一個特徵，然後在特徵上隨機選一個分割點，將該特徵小於分割點的數據放在二叉樹左邊，反之放在右邊。
- 直至二叉樹達到一定深度或者葉子節點只包含一個數據點為止。
- 進行異常檢測時，計算該數據點在多個二叉樹上的平均深度，深度越淺，越可能是異常值。
iForest只適合檢測全局異常點，不適合檢測局部異常點。
- 如左圖所示，黑點是異常點，被切幾次就停到一個子空間。白點為正常點，白色點聚焦在一個簇中。
- 如右圖所示，用iForest切割4個數據，b和c的高度為3，a的高度為2，d的高度為1，d最先被孤立，它最有可能異常。
2. SCiForest
傳統iForest方法在選擇特徵是隨機選取的，SCiForest在選擇特徵時利用了方差。
傳統iForest選擇分割點後形成的分割超平面是平行於坐標軸的，SCiForest可以生成任意角度的分割超平面。
3. RRCF
可以動態增刪樹種的節點，適用於流數據異常檢測。
九、基於圖模型
1. 最大聯通圖
在無向圖G中，若從頂點A到頂點B有路徑相連，則稱A和B是連通的。在圖G中存在若干子圖，其中每個子圖中所有頂點之間都是連通的，但不同子圖間不存在頂點連通，那麼稱圖G的這些子圖為最大連通子圖。
- 最大聯通圖的前提條件是每條邊必須置信，當數據中存在不太置信的邊時，需要先剔除臟數據，否則會影響最大聯通圖的效果。
- 如圖所示，device是設備id，mbr是會員id，節點之間有邊表示設備上有對應的會員登錄過，容易看出device_1、device_2、device_3、device_4是同人，可以根據場景用於判斷作弊，常用於挖掘團伙作弊。
2. 標籤傳播聚類
標籤傳播圖聚類演算法是根據圖的拓撲結構，進行子圖的劃分，使得子圖內部節點的連接較多，子圖之間的連接較少。
標籤傳播演算法的基本思路是：節點的標籤依賴其鄰居節點的標籤資訊，影響程度由節點相似度決定，通過傳播迭代更新達到穩定。
標籤傳播聚類的子圖間可以有少量連接。適用場景：節點之間「高內聚低耦合」。
- 圖中的節點經標籤傳播聚類後將得2個子圖，其中節點1、2、3、4屬於一個子圖，節點5、6、7、8屬於一個子圖。
- 值得一提的是，圖中如果用最大聯通圖（參考1）只會得到1個子圖，用標籤傳播聚類則會得到2個子圖。
十、基於行為序列：馬爾科夫鏈
如圖所示，用戶在搜索引擎上有5個行為狀態：頁面請求（P），搜索（S），自然搜索結果（W），廣告點擊（O），翻頁（N）。狀態之間有轉移概率，由若干行為狀態組成的一條鏈可以看做一條馬爾科夫鏈。
統計正常行為序列中任意兩個相鄰的狀態，然後計算每個狀態轉移到其他任意狀態的概率，得狀態轉移矩陣。針對每一個待檢測用戶行為序列，易得該序列的概率值，概率值越大，越像正常用戶行為。
十一、基於半監督模型
此類方法適用於標註的數據全都是正常數據，常用方法有one-class SVM、SVDD、AutoEncoder、GMM、Naïve Bayes等。
此類方法與無監督方法有些重合，因為無監督方法的基本假設就是數據集中正常數據遠遠多於異常數據。
1. One-class SVM
利用核函數將數據映射到高維空間，尋找超平面使得數據和坐標原點間隔最大。
2. SVDD
利用核函數將數據映射到高維空間，尋找儘可能小的超球體包裹住正常數據。
3. AutoEncoder
對正常數據進行訓練Encoder和Decoder，進行異常檢測時，如果Decoder出來的向量與原始向量差別很大，就認為是異常數據。
4. GMM
對正常數據進行高斯混合模型建模，最大似然估計參數。進行異常檢測時，將其特徵帶入模型，可得出它屬於正常數據的概率。
5. Naïve Bayes
過程同高斯混合模型。
6. 生成對抗網路GAN：比較新的方法
最直觀的理解：利用生成對抗的思想，生成器從隨機雜訊中生成異常數據，判別器判別數據是生成的異常數據，還是原始的正常數據。
- 生成器的目標是生成儘可能和正常數據相似的數據，讓判別器無法識別出。
- 判別器的目標是儘可能判別出真實數據和異常數據。
兩者進行博弈，最終達到平衡。在異常檢測過程中，對於給定數據，只需要利用判別器判別出是正常數據還是異常數據。
十二、基於有監督模型
上述方法都是無監督方法，實現和理解相對簡單。但是由於部分方法每次使用較少的特徵，為了全方位攔截作弊，需要維護較多策略。
同時，上述部分方法組合多特徵的效果取決於人工經驗。而有監督模型能自動組合較多特徵，具備更強的泛化能力。
1. 基於機器學習模型
關於機器學習演算法的介紹，歡迎瀏覽我的另一篇部落格：數據挖掘比賽/項目全流程介紹 ，這裡不再贅述。
可以使用前面的無監督方法挖掘的作弊樣本作為訓練樣本。如果作弊樣本仍然較少，用SMOTE或者GAN生成作弊樣本。
可以採用LR、SVM、GBDT、XGBOOST等機器學習演算法進行回歸，實現二分類，完成異常檢測。
2. 基於深度學習模型
關於深度學習演算法的介紹，歡迎瀏覽我的另一篇部落格：深度學習中的序列模型演變及學習筆記，這裡不再贅述。
關於深度學習組件的介紹，歡迎瀏覽我的另一篇部落格：深度學習中的一些組件及使用技巧 ，這裡不再贅述。
同樣的，可以使用前面的無監督方法挖掘的作弊樣本作為訓練樣本。如果作弊樣本仍然較少，用SMOTE或者GAN生成作弊樣本。
可以採用CNN、RNN、LSTM等深度學習模型及其融合進行回歸，實現二分類，完成異常檢測。
值得一提的是，其他隨筆提到的很多深度學習模型，均適用於「異常檢測」這個應用場景，細品！
舉個例子，阿里的GEM模型實現了異構圖網路在異常檢測中的應用，採用圖神經網路相關演算法實現了「是否異常」的二分類。
同時，自然還有基於知識圖譜、引入遷移學習、引入強化學習等新技術的推進。
十三、數據類型
隨著資訊流的不斷發展，除了上文提到的時間序列數據、高維數據，目前有影像、影片、文本、日誌等數據類型的異常檢測方法。
十四、開源工具庫
可以使用Python異常檢測工具庫Pyod。這個工具庫除了支援Sklearn上支援的模型外，還額外提供了很多模型。
本文參考了阿里巴巴的一篇文章：異常檢測的N種方法，阿里工程師都盤出來了
如果您對人工智慧演算法感興趣，歡迎瀏覽我的另一篇部落格：人工智慧新手入門學習路線和學習資源合集（含AI綜述/python/機器學習/深度學習/tensorflow）、人工智慧領域常用的開源框架和庫（含機器學習/深度學習/強化學習/知識圖譜/圖神經網路）
如果你是電腦專業的應屆畢業生，歡迎瀏覽我的另外一篇部落格：如果你是一個電腦領域的應屆生，你如何準備求職面試？
如果你是電腦專業的本科生，歡迎瀏覽我的另外一篇部落格：如果你是一個電腦領域的本科生，你可以選擇學習什麼？
如果你是電腦專業的研究生，歡迎瀏覽我的另外一篇部落格：如果你是一個電腦領域的研究生，你可以選擇學習什麼？
如果你對金融科技感興趣，歡迎瀏覽我的另一篇部落格：如果你想了解金融科技，不妨先了解金融科技有哪些可能？
之後部落客將持續分享各大演算法的學習思路和學習筆記：hello world: 我的部落格寫作思路
