異常點檢測,，有時也叫離群點檢測,，英文一般叫做Novelty Detection或者Outlier Detection,是比較常見的一類非監(jiān)督學(xué)習(xí)算法,，這里就對異常點檢測算法做一個總結(jié)。

1. 異常點檢測算法使用場景

　　　　什么時候我們需要異常點檢測算法呢,？常見的有三種情況,。一是在做特征工程的時候需要對異常的數(shù)據(jù)做過濾，防止對歸一化等處理的結(jié)果產(chǎn)生影響,。二是對沒有標(biāo)記輸出的特征數(shù)據(jù)做篩選,，找出異常的數(shù)據(jù)。三是對有標(biāo)記輸出的特征數(shù)據(jù)做二分類時,，由于某些類別的訓(xùn)練樣本非常少,，類別嚴重不平衡，此時也可以考慮用非監(jiān)督的異常點檢測算法來做,。

2. 異常點檢測算法常見類別

　　　　異常點檢測的目的是找出數(shù)據(jù)集中和大多數(shù)數(shù)據(jù)不同的數(shù)據(jù),，常用的異常點檢測算法一般分為三類,。

　　　　第一類是基于統(tǒng)計學(xué)的方法來處理異常數(shù)據(jù)，這種方法一般會構(gòu)建一個概率分布模型,，并計算對象符合該模型的概率,，把具有低概率的對象視為異常點。比如特征工程中的RobustScaler方法,，在做數(shù)據(jù)特征值縮放的時候,，它會利用數(shù)據(jù)特征的分位數(shù)分布，將數(shù)據(jù)根據(jù)分位數(shù)劃分為多段,，只取中間段來做縮放,，比如只取25%分位數(shù)到75%分位數(shù)的數(shù)據(jù)做縮放。這樣減小了異常數(shù)據(jù)的影響,。

　　　　第二類是基于聚類的方法來做異常點檢測,。這個很好理解，由于大部分聚類算法是基于數(shù)據(jù)特征的分布來做的,，通常如果我們聚類后發(fā)現(xiàn)某些聚類簇的數(shù)據(jù)樣本量比其他簇少很多,，而且這個簇里數(shù)據(jù)的特征均值分布之類的值和其他簇也差異很大,，這些簇里的樣本點大部分時候都是異常點,。比如我之前講到的BIRCH聚類算法原理和DBSCAN密度聚類算法都可以在聚類的同時做異常點的檢測,。

　　　　第三類是基于專門的異常點檢測算法來做,。這些算法不像聚類算法,，檢測異常點只是一個贈品，它們的目的就是專門檢測異常點的,，這類算法的代表是One Class SVM和Isolation Forest.

　　　　下文主要會對One Class SVM和Isolation Forest做詳細的討論分析,。

3. One Class SVM算法

　　　　One Class SVM也是屬于支持向量機大家族的，但是它和傳統(tǒng)的基于監(jiān)督學(xué)習(xí)的分類回歸支持向量機不同,，它是無監(jiān)督學(xué)習(xí)的方法,，也就是說,，它不需要我們標(biāo)記訓(xùn)練集的輸出標(biāo)簽。

　　　　那么沒有類別標(biāo)簽,，我們?nèi)绾螌ふ覄澐值某矫嬉约皩ふ抑С窒蛄磕?？One Class SVM這個問題的解決思路有很多。這里只講解一種特別的思路SVDD, 對于SVDD來說,，我們期望所有不是異常的樣本都是正類別,，同時它采用一個超球體而不是一個超平面來做劃分,，該算法在特征空間中獲得數(shù)據(jù)周圍的球形邊界，期望最小化這個超球體的體積,，從而最小化異常點數(shù)據(jù)的影響,。

 　　　　假設(shè)產(chǎn)生的超球體參數(shù)為中心 和對應(yīng)的超球體半徑 ，超球體體積 被最小化,，中心 是支持向量的線性組合,；跟傳統(tǒng)SVM方法相似，可以要求所有訓(xùn)練數(shù)據(jù)點 到中心的距離嚴格小于 ,，但同時構(gòu)造一個懲罰系數(shù)為 的松弛變量 ,，優(yōu)化問題如下所示：

　　　　和之前講的支持向量機系列類似的求解方法，在采用拉格朗日對偶求解之后,，可以判斷新的數(shù)據(jù)點 是否在類內(nèi),，如果到中心的距離小于或者等于半徑,則不是異常點，如果在超球體以外,，則是異常點,。

　　　　在sklearn中,，我們可以用svm包里面的OneClassSVM來做異常點檢測。OneClassSVM也支持核函數(shù),，所以普通SVM里面的調(diào)參思路在這里也適用,。

4. Isolation Forest算法

　　　　Isolation Forest(以下簡稱IForest)是周志華老師的學(xué)生提出來的，主要是利用集成學(xué)習(xí)的思路來做異常點檢測,，目前幾乎成為異常點檢測算法的首選項,，我之前在Bagging與隨機森林算法原理小結(jié)第4.3節(jié)中也簡略講解了IForest的思路,，它是隨機森林大家族的一員。

　　　　算法本身并不復(fù)雜,，主要包括第一步訓(xùn)練構(gòu)建隨機森林對應(yīng)的多顆決策樹,，這些決策樹一般叫iTree,，第二步計算需要檢測的數(shù)據(jù)點最終落在任意第t顆iTree的層數(shù)。然后我們可以得出在每棵樹的高度平均值,。第三步根據(jù)判斷是否是異常點,。

　　　　對于第一步構(gòu)建決策樹的過程，方法和普通的隨機森林不同,。

　　　　首先采樣決策樹的訓(xùn)練樣本時，普通的隨機森林要采樣的樣本個數(shù)等于訓(xùn)練集個數(shù),。但是iForest不需要采樣這么多,，一般來說,，采樣個數(shù)要遠遠小于訓(xùn)練集個數(shù)。原因是我們的目的是異常點檢測,，只需要部分的樣本我們一般就可以將異常點區(qū)別出來了,。

　　　　另外就是在做決策樹分裂決策時，由于我們沒有標(biāo)記輸出,，所以沒法計算基尼系數(shù)或者和方差之類的劃分標(biāo)準,。這里我們使用的是隨機選擇劃分特征，然后在基于這個特征再隨機選擇劃分閾值,，進行決策樹的分裂,。直到樹的深度達到限定閾值或者樣本數(shù)只剩一個。

　　　　第二步計算要檢測的樣本點在每棵樹的高度平均值,。首先需要遍歷每一顆iTree,，得到檢測的數(shù)據(jù)點最終落在任意第t顆iTree的數(shù)層數(shù)。這個代表的是樹的深度,，也就是離根節(jié)點越近,，則越小,，越靠近底層，則越大,，根節(jié)點的高度為0.

　　　　第三步是據(jù)判斷是否是異常點,。我們一般用下面的公式計算的異常概率分值：

　　　　從表示式可以看出,，如果高度, 則，即是異常點的概率是100%,，如果高度, 則,即不可能是異常點。如果高度, 則，即是異常點的概率是50%,，一般我們可以設(shè)置$s(x,m)的一個閾值然后去調(diào)參,，這樣大于閾值的才認為是異常點。

　　　　在sklearn中,，我們可以用ensemble包里面的IsolationForest來做異常點檢測,。

5. 異常點檢測算法小結(jié)

　　　　IForest目前是異常點檢測最常用的算法之一,，它的優(yōu)點非常突出，它具有線性時間復(fù)雜度,。因為是隨機森林的方法,，所以可以用在含有海量數(shù)據(jù)的數(shù)據(jù)集上面。通常樹的數(shù)量越多,，算法越穩(wěn)定,。由于每棵樹都是互相獨立生成的，因此可以部署在大規(guī)模分布式系統(tǒng)上來加速運算,。對于目前大數(shù)據(jù)分析的趨勢來說，它的好用是有原因的,。

　　　　但是IForest也有一些缺點,，比如不適用于特別高維的數(shù)據(jù)。由于每次切數(shù)據(jù)空間都是隨機選取一個維度和該維度的隨機一個特征,，建完樹后仍然有大量的維度沒有被使用,，導(dǎo)致算法可靠性降低,。此時推薦降維后使用,，或者考慮使用One Class SVM。

　　　　另外iForest僅對即全局稀疏點敏感,，不擅長處理局部的相對稀疏點 ,，這樣在某些局部的異常點較多的時候檢測可能不是很準。

　　　　而One Class SVM對于中小型的數(shù)據(jù)分析,，尤其是訓(xùn)練樣本不是特別海量的時候用起來經(jīng)常會比iForest順手,，因此比較適合做原型分析。