機器學習-異常檢測演算法（一）：Isolation Forest

"An outlier is an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism." — D. M. Hawkins, Identification of Outliers, Chapman and Hall, 1980.

異常檢測 (anomaly detection)，或者又被稱為「離群點檢測」 (outlier detection)，是機器學習研究領域中跟現實緊密聯繫、有廣泛應用需求的一類問題。但是，什麼是異常，並沒有標準答案，通常因具體應用場景而異。如果要給一個比較通用的定義，很多文獻通常會引用 Hawkins 在文章開頭那段話。很多後來者的說法，跟這個定義大同小異。這些定義雖然籠統，但其實暗含了認定「異常」的兩個標準或者說假設：

1. 異常數據跟樣本中大多數數據不太一樣。
2. 異常數據在整體數據樣本中佔比比較小。

為了刻畫異常數據的「不一樣」，最直接的做法是利用各種統計的、距離的、密度的量化指標去描述數據樣本跟其他樣本的疏離程度。而 Isolation Forest (Liu et al. 2011) 的想法要巧妙一些，它嘗試直接去刻畫數據的「疏離」(isolation)程度，而不藉助其他量化指標。Isolation Forest 因為簡單、高效，在學術界和工業界都有著不錯的名聲。

演算法介紹

我們先用一個簡單的例子來說明 Isolation Forest 的基本想法。假設現在有一組一維數據（如下圖所示），我們要對這組數據進行隨機切分，希望可以把點 A 和點 B 單獨切分出來。具體的，我們先在最大值和最小值之間隨機選擇一個值 x，然後按照 <x 和 >=x 可以把數據分成左右兩組。然後，在這兩組數據中分別重複這個步驟，直到數據不可再分。顯然，點 B 跟其他數據比較疏離，可能用很少的次數就可以把它切分出來；點 A 跟其他數據點聚在一起，可能需要更多的次數才能把它切分出來。

我們把數據從一維擴展到兩維。同樣的，我們沿著兩個坐標軸進行隨機切分，嘗試把下圖中的點A"和點B"分別切分出來。我們先隨機選擇一個特徵維度，在這個特徵的最大值和最小值之間隨機選擇一個值，按照跟特徵值的大小關係將數據進行左右切分。然後，在左右兩組數據中，我們重複上述步驟，再隨機的按某個特徵維度的取值把數據進行細分，直到無法細分，即：只剩下一個數據點，或者剩下的數據全部相同。跟先前的例子類似，直觀上，點B"跟其他數據點比較疏離，可能只需要很少的幾次操作就可以將它細分出來；點A"需要的切分次數可能會更多一些。

按照先前提到的關於「異常」的兩個假設，一般情況下，在上面的例子中，點B和點B" 由於跟其他數據隔的比較遠，會被認為是異常數據，而點A和點A" 會被認為是正常數據。直觀上，異常數據由於跟其他數據點較為疏離，可能需要較少幾次切分就可以將它們單獨劃分出來，而正常數據恰恰相反。這其實正是 Isolation Forest（IF）的核心概念。IF採用二叉樹去對數據進行切分，數據點在二叉樹中所處的深度反應了該條數據的「疏離」程度。整個演算法大致可以分為兩步：

1. 訓練：抽取多個樣本，構建多棵二叉樹（Isolation Tree，即 iTree）；
2. 預測：綜合多棵二叉樹的結果，計算每個數據點的異常分值。

訓練：構建一棵 iTree 時，先從全量數據中抽取一批樣本，然後隨機選擇一個特徵作為起始節點，並在該特徵的最大值和最小值之間隨機選擇一個值，將樣本中小於該取值的數據划到左分支，大於等於該取值的划到右分支。然後，在左右兩個分支數據中，重複上述步驟，直到滿足如下條件：

1. 數據不可再分，即：只包含一條數據，或者全部數據相同。
2. 二叉樹達到限定的最大深度。

預測：計算數據 x 的異常分值時，先要估算它在每棵 iTree 中的路徑長度（也可以叫深度）。具體的，先沿著一棵 iTree，從根節點開始按不同特徵的取值從上往下，直到到達某葉子節點。假設 iTree 的訓練樣本中同樣落在 x 所在葉子節點的樣本數為 T.size，則數據 x 在這棵 iTree 上的路徑長度 h(x)，可以用下面這個公式計算：

公式中，e 表示數據 x 從 iTree 的根節點到葉節點過程中經過的邊的數目，C(T.size) 可以認為是一個修正值，它表示在一棵用 T.size 條樣本數據構建的二叉樹的平均路徑長度。一般的，C(n) 的計算公式如下：

其中，H(n-1) 可用 ln(n-1)+0.5772156649 估算，這裡的常數是歐拉常數。數據 x 最終的異常分值 Score(x) 綜合了多棵 iTree 的結果：

公式中，E(h(x)) 表示數據 x 在多棵 iTree 的路徑長度的均值， 表示單棵 iTree 的訓練樣本的樣本數， 表示用條數據構建的二叉樹的平均路徑長度，它在這裡主要用來做歸一化。

從異常分值的公式看，如果數據 x 在多棵 iTree 中的平均路徑長度越短，得分越接近 1，表明數據 x 越異常；如果數據 x 在多棵 iTree 中的平均路徑長度越長，得分越接近 0，表示數據 x 越正常；如果數據 x 在多棵 iTree 中的平均路徑長度接近整體均值，則打分會在 0.5 附近。

演算法應用

Isolation Forest 演算法主要有兩個參數：一個是二叉樹的個數；另一個是訓練單棵 iTree 時候抽取樣本的數目。實驗表明，當設定為 100 棵樹，抽樣樣本數為 256 條時候，IF 在大多數情況下就已經可以取得不錯的效果。這也體現了演算法的簡單、高效。

Isolation Forest 是無監督的異常檢測演算法，在實際應用時，並不需要黑白標籤。需要注意的是：（1）如果訓練樣本中異常樣本的比例比較高，違背了先前提到的異常檢測的基本假設，可能最終的效果會受影響；（2）異常檢測跟具體的應用場景緊密相關，演算法檢測出的「異常」不一定是我們實際想要的。比如，在識別虛假交易時，異常的交易未必就是虛假的交易。所以，在特徵選擇時，可能需要過濾不太相關的特徵，以免識別出一些不太相關的「異常」。

參考文獻

1. F. T. Liu, K. M. Ting and Z. H. Zhou，Isolation-based Anomaly Detection，TKDD，2011