Isolation Forest演算法原理詳解

iTree的構造

提到森林，自然少不了樹，畢竟森林都是由樹構成的，那麼我們在看Isolation Forest（簡稱iForest）前，我們先來看看Isolation-Tree（簡稱iTree）是怎麼構成的，iTree是一種隨機二叉樹，每個節點要麼有兩個女兒，要麼就是葉子節點，一個孩子都沒有。給定一堆數據集D，這裡D的所有屬性都是連續型的變數，iTree的構成過程如下：

隨機選擇一個屬性Attr；

隨機選擇該屬性的一個值Value；

根據Attr對每條記錄進行分類，把Attr小於Value的記錄放在左女兒，把大於等於Value的記錄放在右孩子；

然後遞歸的構造左女兒和右女兒，直到滿足以下條件：

傳入的數據集只有一條記錄或者多條一樣的記錄；

樹的高度達到了限定高度；

iTree構建好了後，就可以對數據進行預測啦，預測的過程就是把測試記錄在iTree上走一下，看測試記錄落在哪個葉子節點。iTree能有效檢測異常的假設是：異常點一般都是非常稀有的，在iTree中會很快被劃分到葉子節點，因此可以用葉子節點到根節點的路徑h(x)長度來判斷一條記錄x是否是異常點；對於一個包含n條記錄的數據集，其構造的樹的高度最小值為log(n)，最大值為n-1，論文提到說用log(n)和n-1歸一化不能保證有界和不方便比較，用一個稍微複雜一點的歸一化公式：

s(x,n)就是記錄x在由n個樣本的訓練數據構成的iTree的異常指數，s(x,n)取值範圍為[0,1]異常情況的判斷分以下幾種情況：

越接近1表示是異常點的可能性高；

越接近0表示是正常點的可能性比較高；

如果大部分的訓練樣本的s(x,n)都接近於0.5，整個數據沒有明顯的異常。

由於是隨機選屬性，隨機選屬性值，一棵樹這麼隨便搞肯定是不靠譜，但是把多棵樹結合起來就變強大了；

iForest的構造

iTree搞明白了，我們現在來看看iForest是怎麼構造的，給定一個包含n條記錄的數據集D，如何構造一個iForest。iForest和Random Forest的方法有些類似，都是隨機採樣一部分數據集去構造每一棵樹，保證不同樹之間的差異性，不過iForest與RF不同，採樣的數據量Psi不需要等於n，可以遠遠小於n，論文中提到採樣大小超過256效果就提升不大了，並且越大還會造成計算時間的上的浪費，為什麼不像其他演算法一樣，數據越多效果越好呢，可以看看下面這兩個個圖：

左邊是原始數據，右邊是採樣了數據，藍色是正常樣本，紅色是異常樣本。可以看到，在採樣之前，正常樣本和異常樣本出現重疊，因此很難分開，但我們採樣之和，異常樣本和正常樣本可以明顯的分開。

除了限制採樣大小Ψ以外，我們還要給每棵iTree設置最大高度為l=ceilng(log2Ψ)，這是因為異常數據記錄都比較少，其路徑長度也比較低，而我們也只需要把正常記錄和異常記錄區分開來，因此只需要關心低於平均高度的部分就好，這樣演算法效率更高，不過這樣調整了後，後面可以看到計算h(x)需要一點點改進，先看iForest的偽代碼：

IForest構造好後，對測試進行預測時，需要進行綜合每棵樹的結果，於是

E(h(x))表示記錄x在每棵樹的高度均值，另外h(x)計算需要改進，在生成葉節點時，演算法記錄了葉節點包含的記錄數量，這時候要用這個數量Size估計一下平均高度，h(x)的計算方法如下：

對高維數據的處理

在處理高維數據時，可以對演算法進行改進，採樣之後並不是把所有的屬性都用上，而是用峰度係數Kurtosis挑選一些有價值的屬性，再進行iTree的構造，這跟隨機森林就更像了，隨機選記錄，再隨機選屬性。

只使用正常樣本

這個演算法本質上是一個無監督學習，不需要數據的類標，有時候異常數據太少了，少到我們只捨得拿這幾個異常樣本進行測試，不能進行訓練，論文提到只用正常樣本構建IForest也是可行的，效果有降低，但也還不錯，並可以通過適當調整採樣大小來提高效果。

總結

iForest具有線性時間複雜度。因為是ensemble的方法，所以可以用在含有海量數據的數據集上面。通常樹的數量越多，演算法越穩定。由於每棵樹都是互相獨立生成的，因此可以部署在大規模分散式系統上來加速運算。

iForest不適用於特別高維的數據。由於每次切數據空間都是隨機選取一個維度，建完樹後仍然有大量的維度信息沒有被使用，導致演算法可靠性降低。高維空間還可能存在大量噪音維度或無關維度（irrelevant attributes），影響樹的構建。對這類數據，建議使用子空間異常檢測（Subspace Anomaly Detection）技術。此外，切割平面默認是axis-parallel的，也可以隨機生成各種角度的切割平面，詳見「On Detecting Clustered Anomalies Using SCiForest」。

iForest僅對Global Anomaly 敏感，即全局稀疏點敏感，不擅長處理局部的相對稀疏點 （Local Anomaly）。目前已有改進方法發表於PAKDD，詳見「Improving iForest with Relative Mass」。

iForest推動了重心估計（Mass Estimation）理論發展，目前在分類聚類和異常檢測中都取得顯著效果，發表於各大頂級數據挖掘會議和期刊（如SIGKDD，ICDM，ECML）。

注意

目前燕哥還沒有發現有Java開源庫實現了該演算法。目前只有Python機器學習庫scikit-learn的0.18版本對此演算法進行了實現。而我的項目絕大多數都是Java實現的，因此我需要自己實現該演算法。演算法源碼已實現並開源到我的GitHub上，讀者可以下載源碼並用IDEA集成開發環境直接打開項目，並運行測試程序以查看演算法的檢測效果：https://github.com/JeemyJohn/AnomalyDetection

參考文獻

http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf

https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/ensemble/iforest.py

http://scikit-learn.org/dev/modules/generated/sklearn.ensemble.IsolationForest.html

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！

請您繼續閱讀更多來自 天善智能 的精彩文章: