異常點檢測，有時也叫離群點檢測，英文一般叫做Novelty Detection或者Outlier Detection,是比較常見的一類非
監督學習算法，這裡就對異常點檢測算法做一個總結。
1. 異常點檢測算法使用場景 什麼時候我們需要異常點檢測算法呢？常見的有三種情況。一是在做特徵工程的時候需要對異常的數據做過濾，防止
對歸一化等處理的結果產生影響。二是對沒有標記輸出的特徵數據做篩選，找出異常的數據。三是對有標記輸出的特徵數據做
二分類時，由於某些類別的訓練樣本非常少，類別嚴重不平衡，此時也可以考慮用非監督的異常點檢測算法來做。
2. 異常點檢測算法常見類別 異常點檢測的目的是找出數據集中和大多數數據不同的數據，常用的異常點檢測算法一般分為三類。
第一類是基於統計學的方法來處理異常數據，這種方法一般會構建一個概率分佈模型，並計算對象符合該模型的概
率，把具有低概率的對象視為異常點。比如特徵工程中的RobustScaler方法，在做數據特徵值縮放的時候，它會利用數據特徵
的分位數分佈，將數據根據分位數劃分為多段，只取中間段來做縮放，比如只取25%分位數到75%分位數的數據做縮放。這樣
減小了異常數據的影響。
第二類是基於聚類的方法來做異常點檢測。這個很好理解，由於大部分聚類算法是基於數據特徵的分佈來做的，通常
如果我們聚類後發現某些聚類簇的數據樣本量比其他簇少很多，而且這個簇裡數據的特徵均值分佈之類的值和其他簇也差異很
大，這些簇裡的樣本點大部分時候都是異常點。比如我之前講到的BIRCH聚類算法原理和DBSCAN密度聚類算法都可以在聚類
的同時做異常點的檢測。
第三類是基於專門的異常點檢測算法來做。這些算法不像聚類算法，檢測異常點只是一個贈品，它們的目的就是專門
檢測異常點的，這類算法的代表是One Class SVM和Isolation Forest.
下文主要會對One Class SVM和Isolation Forest做詳細的討論分析。
3. One Class SVM算法 One Class SVM也是屬於支持向量機大家族的，但是它和傳統的基於監督學習的分類迴歸支持向量機不同，它是無監
督學習的方法，也就是說，它不需要我們標記訓練集的輸出標籤。
那麼沒有類別標籤，我們如何尋找劃分的超平面以及尋找支持向量呢？One Class SVM這個問題的解決思路有很多。
這裡只講解一種特別的思路SVDD, 對於SVDD來說，我們期望所有不是異常的樣本都是正類別，同時它採用一個超球體而不是
一個超平面來做劃分，該算法在特徵空間中獲得數據周圍的球形邊界，期望最小化這個超球體的體積，從而最小化異常點數據
的影響。
假設產生的超球體參數為中心 和對應的超球體半徑 ，超球體體積 被最小化，中心 是支持向量的線
性組合；跟傳統SVM方法相似，可以要求所有訓練數據點 到中心的距離嚴格小於 ，但同時構造一個懲罰係數為 的鬆弛
變量 ，優化問題如下所示：
和之前講的支持向量機系列類似的求解方法，在採用拉格朗日對偶求解之後，可以判斷新的數據點 是否在類內，如
果 到中心的距離小於或者等於半徑 ,則不是異常點，如果在超球體以外，則是異常點。
在sklearn中，我們可以用svm包裡面的OneClassSVM來做異常點檢測。OneClassSVM也支持核函數，所以普通
SVM裡面的調參思路在這裡也適用。
4. Isolation Forest算法 Isolation Forest(以下簡稱IForest)是周志華老師的學生提出來的，主要是利用集成學習的思路來做異常點檢測，目
前幾乎成為異常點檢測算法的首選項，我之前在Bagging與隨機森林算法原理小結第4.3節中也簡略講解了IForest的思路，它
是隨機森林大家族的一員。
算法本身並不複雜，主要包括第一步訓練構建隨機森林對應的多顆決策樹，這些決策樹一般叫iTree，第二步計算需要
檢測的數據點 最終落在任意第t顆iTree的層數 。然後我們可以得出 在每棵樹的高度平均值 。第三步根據 判
斷 是否是異常點。
對於第一步構建決策樹的過程，方法和普通的隨機森林不同。
首先採樣決策樹的訓練樣本時，普通的隨機森林要採樣的樣本個數等於訓練集個數。但是iForest不需要採樣這麼多，
一般來說，採樣個數要遠遠小於訓練集個數。原因是我們的目的是異常點檢測，只需要部分的樣本我們一般就可以將異常點區
別出來了。
另外就是在做決策樹分裂決策時，由於我們沒有標記輸出，所以沒法計算基尼係數或者和方差之類的劃分標準。這裡
我們使用的是隨機選擇劃分特徵，然後在基於這個特徵再隨機選擇劃分閾值，進行決策樹的分裂。直到樹的深度達到限定閾值
或者樣本數只剩一個。
第二步計算要檢測的樣本點在每棵樹的高度平均值 。首先需要遍歷每一顆iTree，得到檢測的數據點 最終落在任
意第t顆iTree的數層數 。這個 代表的是樹的深度，也就是離根節點越近，則 越小，越靠近底層，則 越
大，根節點的高度為0.
第三步是據 判斷 是否是異常點。我們一般用下面的公式計算 的異常概率分值：
, 的取值範圍是[0,1],取值越接近於1，則是異常點的概率也越大。其中，m為樣本個數。的表達式為：
從 表示式可以看出，如果高度 , 則 ，即是異常點的概率是100%，如果高度
, 則 ,即不可能是異常點。如果高度 , 則 ，即是異常點的概率是
50%，一般我們可以設置$s(x,m)的一個閾值然後去調參，這樣大於閾值的才認為是異常點。
在sklearn中，我們可以用ensemble包裡面的IsolationForest來做異常點檢測。
5. 異常點檢測算法小結 IForest目前是異常點檢測最常用的算法之一，它的優點非常突出，它具有線性時間複雜度。因為是隨機森林的方法，
所以可以用在含有海量數據的數據集上面。通常樹的數量越多，算法越穩定。由於每棵樹都是互相獨立生成的，因此可以部署
在大規模分佈式系統上來加速運算。對於目前大數據分析的趨勢來說，它的好用是有原因的。
但是IForest也有一些缺點，比如不適用於特別高維的數據。由於每次切數據空間都是隨機選取一個維度和該維度的隨
機一個特徵，建完樹後仍然有大量的維度沒有被使用，導致算法可靠性降低。此時推薦降維後使用，或者考慮使用One Class
SVM。
另外iForest僅對即全局稀疏點敏感，不擅長處理局部的相對稀疏點 ，這樣在某些局部的異常點較多的時候檢測可能不
是很準。
而One Class SVM對於中小型的數據分析，尤其是訓練樣本不是特別海量的時候用起來經常會比iForest順手，因此
比較適合做原型分析。
閱讀更多 洛鴻0920 的文章
