Isolation Forest介紹

05-06

本文介紹將Isolation Forest用於異常檢測(Anomaly Detection), 主要內容來自於Liu F T, Kai M T, Zhou Z H. Isolation-Based Anomaly Detection[M]. ACM, 2012.

1. 異常檢測

An anomaly is an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism.

異常是一個觀測值，其偏離其他觀測值太多以至於可以合理地推測該觀測來自於其他機制。

Anomalies are referred to as patterns in data that do not conform to a well-defined characteristic of normal patterns. They are generated by a variety of abnormal activities, e.g., credit card fraud, mobile phone fraud, cyber attacks, etc., which are significant to data analysts.

異常是指數據中與預先定義好的正常模式的特性不同的模式，由各種各樣的不正常活動產生，例如信用卡詐騙、手機詐騙、網路攻擊等，對分析人員具有重要意義。

異常數據通常有兩個特點(few and different)：

異常數據的比例較少(few)
異常數據某些或者全部特徵與其他數據點差別較大(different)

異常檢測演算法如下所示

絕大部分的異常檢測方法，包括基於分類的方法，例如Replicator Neural Network、one-class SVM等，都是對正常數據點創建profile，然後將不符合正常profile的數據識別為異常數據。它們並非設計用於異常檢測(例如classification or clustering)，而異常測能力往往是副產品，因此存在兩個問題：

這些方法並非optimized to detect anomalies，因此通常效果很差，產生大量誤報漏報；
很多的現有方法都只能解決低維和數據量很小的數據

Isolation Forest這篇論文提出Isolation的概念，就是將異常數據孤立，來從數據集中識別異常數據。

Isolatlion means separating an instance from the rest of the instances

任何可以將數據分隔開的方法都可以實現Isolation，本文採用了binary tree結構來實現，稱為iTree，在iTree中，異常點被isolated之後更加靠近樹的根部，而正常數據isolated之後在樹中更深，這是文章的key point.

2. Isolation Tree

如下圖1所示，樹的每個節點都任意選擇一個特徵 $q$ 並且選擇一個split value $p$ ，其中 $q<p$ 的數據分類到左子節點， $q>p$ 的數據分類到右子節點。

圖中異常點為紅色點 $(17,17)$ ，正常點為左邊紅色和藍色點，我們可以看出異常點直接就被isolated，而正常點都需要經過多次split才能夠isolated。

圖1. Isolation Tree示意圖

Isolation Tree的Training：

隨機選擇一個屬性 $q$ ；
隨機選擇該屬性的一個值 $p(min<p<max)$ ；
根據Attr對每條記錄進行分類，把 $q<p$ 的記錄放在左子節點，把 $qge p$ 的記錄放在右子節點；
然後遞歸的構造左子節點和右子節點，直到滿足以下條件之一：

傳入的數據集只有一條記錄或者多條一樣的記錄；
樹的高度達到了限定高度；

3. Isolation Forest

上面給出了單個的Isolation Tree如何訓練的問題，現在介紹Isolation Forest如何訓練的問題。每個isolation tree都採用訓練集數據中的某個子集 $X^{}subset X$ 來進行訓練.

演算法1中有兩個參數：

樣本大小 $psi$
isolation tree的數量 $t$

樣本大小 $psi$ 決定了每個isolation tree的訓練數據的大小，我們發現當 $psi$ 增加到一定數量，isolation tree的檢測能力增長停滯，這時候就不需要繼續增加了，因為會增加計算量和內存佔用。我們假設異常數據是few and different, 因此正常數據是many and similar, 在這樣的假設下一個小的樣本就足夠iForest來區分正常數據和異常數據了。我們的經驗是設置到 $2^{8}$ 就足夠進行異常檢測了，effect of subsampling size如下圖所示

Number of trees $t$ 控制了ensemble size，我們發現在 $t=100$ 之前path lengths就會收斂，因此我們採用 $t=100$ 作為實驗默認值。

通過演算法1和演算法2，我們就完成了訓練過程，得到了一個isolation tree的collection。

訓練一個iForest的最差情況下時間複雜度是 $O(tpsi^{2})$ ,空間複雜度是 $O(tpsi)$ .

4. Evaluation

既然建立了多個isolation tree組成的isolation forest，我們採用isolation tree來進行區分一個測試數據，從root到一個leaf node的距離作為path length $h(x)$ ，演算法如演算法3所示。

從root節點往下遍歷，如果

遍歷到了葉子結點，或者
path length超過了預定limit(如果深度太高，這意味著數據是正常數據，繼續遍歷就沒有意義了額)

得到結果為 $h(x)=e+c(T.size)$ ,其中e是邊的個數， $c(T.size)$ 是一個adjustment，用來表示一個數量為 $T.size$ 的樹的average path length(這是很合理的)

4.1 Anomaly Score

每種anomaly detection method都需要給出一個anomaly score，對於一個包含n條記錄的數據集，其構造的樹的高度最小值為 $log(psi)$ ，最大值為 $psi-1$ ，當需要比較不同模型給出的path length的時候，採用上述term對 $h(x)$ 進行規範化是不合理的，因此採用以下方式進行normalization：

其中 $H(i)$ 是諧波數，可以用 $ln(i)+0.5772156649$ 來進行近似，因為 $c(psi)$ 表示給定 $psi$ 的情況下 $h(x)$ 的平均值，因此我們用 $c(psi)$ 來normalize $h(x)$ ,一個測試數據 $x$ 的異常分數 $s$ 定義為：

$s(x,psi)=2^{-frac{E(h(x))}{c(psi)}}$

其中 $E(h(x))$ 表示所有isolation tree的 $h(x)$ 的平均值。我們有以下關係，

可以看出：

$E(h(x))$ 越接近0，表示path length很小，因此很容易就將樣本數據isolate， $s(x,psi)$ 就越接近1，樣本異常的概率更高；
$E(h(x))$ 越接近 $psi-1$ ，表示path length很長，因此就很難將樣本數據isolate， $s(x,psi)$ 就越接近0，樣本是正常的概率更高；

5. 處理高維數據

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

參考文獻

Ahmed M, Mahmood A N, Hu J. A survey of network anomaly detection techniques[J]. Journal of Network & Computer Applications, 2015, 60:19-31.