iForest （Isolation Forest）孤立森林 異常檢測 入門篇

iForest （Isolation Forest）孤立森林 是一個基於Ensemble的快速異常檢測方法，具有線性時間複雜度和高精準度，是符合大數據處理要求的state-of-the-art演算法（詳見新版教材「Outlier Analysis」第5和第6章）。其可以用於網路安全中的攻擊檢測，金融交易欺詐檢測，疾病偵測，和雜訊數據過濾等。本文將通俗解釋實現方法和日常運用，即無需深厚的數學功底。

首先，我們先了解下該演算法的動機。目前學術界對異常（anomaly detection）的定義有很多種，iForest 適用與連續數據（Continuous numerical data）的異常檢測，將異常定義為「容易被孤立的離群點 (more likely to be separated)」——可以理解為分布稀疏且離密度高的群體較遠的點。用統計學來解釋，在數據空間裡面，分布稀疏的區域表示數據發生在此區域的概率很低，因而可以認為落在這些區域里的數據是異常的。一個例子如下（來源）：

iForest屬於Non-parametric和unsupervised的方法，即不用定義數學模型也不需要有標記的訓練。對於如何查找哪些點是否容易被孤立（isolated），iForest使用了一套非常高效的策略。假設我們用一個隨機超平面來切割（split）數據空間（data space）, 切一次可以生成兩個子空間（想像拿刀切蛋糕一分為二）。之後我們再繼續用一個隨機超平面來切割每個子空間，循環下去，直到每子空間裡面只有一個數據點為止。直觀上來講，我們可以發現那些密度很高的簇是可以被切很多次才會停止切割，但是那些密度很低的點很容易很早的就停到一個子空間了。上圖裡面黑色的點就很容易被切幾次就停到一個子空間，而白色點聚集的地方可以切很多次才停止。

怎麼來切這個數據空間是iForest的設計核心思想，本文僅介紹最基本的方法。由於切割是隨機的，所以需要用ensemble的方法來得到一個收斂值（蒙特卡洛方法），即反覆從頭開始切，然後平均每次切的結果。iForest 由t個iTree（Isolation Tree）孤立樹 組成，每個iTree是一個二叉樹結構，其實現步驟如下：

1. 從訓練數據中隨機選擇Ψ個點樣本點作為subsample，放入樹的根節點。

2. 隨機指定一個維度（attribute），在當前節點數據中隨機產生一個切割點p——切割點產生於當前節點數據中指定維度的最大值和最小值之間。

3. 以此切割點生成了一個超平面，然後將當前節點數據空間劃分為2個子空間：把指定維度里小於p的數據放在當前節點的左孩子，把大於等於p的數據放在當前節點的右孩子。

4. 在孩子節點中遞歸步驟2和3，不斷構造新的孩子節點，直到 孩子節點中只有一個數據（無法再繼續切割） 或 孩子節點已到達限定高度 。

獲得t個iTree之後，iForest 訓練就結束，然後我們可以用生成的iForest來評估測試數據了。對於一個訓練數據x，我們令其遍歷每一棵iTree，然後計算x最終落在每個樹第幾層（x在樹的高度）。然後我們可以得出x在每棵樹的高度平均值，即 the average path length over t iTrees。*值得注意的是，如果x落在一個節點中含多個訓練數據，可以使用一個公式來修正x的高度計算，詳細公式推導見原論文。

獲得每個測試數據的average path length後，我們可以設置一個閾值（邊界值），average path length 低於此閾值的測試數據即為異常。也就是說 「iForest identifies anomalies as instances having the shortest average path lengths in a dataset 」(異常在這些樹中只有很短的平均高度). *值得注意的是，論文中對樹的高度做了歸一化，並得出一個0到1的數值，即越短的高度越接近1（異常的可能性越高）。

4個測試樣本遍歷一棵iTree的例子如下：

b和c的高度為3，a的高度是2，d的高度是1。

可以看到d最有可能是異常，因為其最早就被孤立（isolated）了。

生成一棵iTree的詳細演算法（來源）:

iForest演算法默認參數設置如下：

subsample size: 256

Tree height： 8

Number of trees: 100

通俗解釋就是——建100棵iTree，每棵iTree最高8層，且每棵iTree都是獨立隨機選擇256個數據樣本建成。

個人見解：

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

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

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

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

參考文獻：

iForest 是劉飛博士(Fei Tony Liu)在莫納什大學就讀期間由陳開明(Kai-Ming Ting)教授和周志華(Zhi-Hua Zhou)教授指導發表的。第一個版本是在2008年ICDM上，獲得年度最佳論文，擴充版本發表與TKDD。

Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation forest."Data Mining, 2008. ICDM08. Eighth IEEE International Conference on. IEEE, 2008.

Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation-based anomaly detection."ACM Transactions on Knowledge Discovery from Data (TKDD)6.1 (2012): 3.

論文下載：

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

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

源碼下載：

R語言 Isolation Forest

Python語言 sklearn.ensemble.IsolationForest - scikit-learn 0.18.1 documentation

Java語言 Waikato Environment for Knowledge Analysis (WEKA)

Matlab語言 https://github.com/zhuyemvp/iForest

全文完，轉載必須註明出處： ? Ye Zhu 2017

推薦閱讀：