孤立森林（Isolation Forest）算法是西瓜書作者周志華老師的團隊研究開發(fā)的算法，一般用于結構化數(shù)據(jù)的異常檢測。
異常的定義
針對于不同類型的異常，要用不同的算法來進行檢測，而孤立森林算法主要針對的是連續(xù)型結構化數(shù)據(jù)中的異常點。
使用孤立森林的前提是，將異常點定義為那些 “容易被孤立的離群點” —— 可以理解為分布稀疏，且距離高密度群體較遠的點。從統(tǒng)計學來看，在數(shù)據(jù)空間里，若一個區(qū)域內只有分布稀疏的點，表示數(shù)據(jù)點落在此區(qū)域的概率很低，因此可以認為這些區(qū)域的點是異常的。
也就是說，孤立森林算法的理論基礎有兩點：
- 異常數(shù)據(jù)占總樣本量的比例很小；
- 異常點的特征值與正常點的差異很大。
上圖中，中心的白色空心點為正常點，即處于高密度群體中。四周的黑色實心點為異常點，散落在高密度區(qū)域以外的空間。
使用場景
孤立森林算法是基于 Ensemble 的異常檢測方法，因此具有線性的時間復雜度。且精準度較高，在處理大數(shù)據(jù)時速度快，所以目前在工業(yè)界的應用范圍比較廣。常見的場景包括：網絡安全中的攻擊檢測、金融交易欺詐檢測、疾病偵測、噪聲數(shù)據(jù)過濾（數(shù)據(jù)清洗）等。
與其他異常檢測算法的差異
孤立森林中的 “孤立” (isolation) 指的是 “把異常點從所有樣本中孤立出來”，論文中的原文是 “separating an instance from the rest of the instances”.
大多數(shù)基于模型的異常檢測算法會先 ”規(guī)定“ 正常點的范圍或模式，如果某個點不符合這個模式，或者說不在正常范圍內，那么模型會將其判定為異常點。
孤立森林的創(chuàng)新點包括以下四個：
- Partial models：在訓練過程中，每棵孤立樹都是隨機選取部分樣本；
- No distance or density measures：不同于 KMeans、DBSCAN 等算法，孤立森林不需要計算有關距離、密度的指標，可大幅度提升速度，減小系統(tǒng)開銷；
- Linear time complexity：因為基于 ensemble，所以有線性時間復雜度。通常樹的數(shù)量越多，算法越穩(wěn)定；
- Handle extremely large data size：由于每棵樹都是獨立生成的，因此可部署在大規(guī)模分布式系統(tǒng)上來加速運算。
算法思想
想象這樣一個場景，我們用一個隨機超平面對一個數(shù)據(jù)空間進行切割，切一次可以生成兩個子空間（也可以想象用刀切蛋糕）。接下來，我們再繼續(xù)隨機選取超平面，來切割第一步得到的兩個子空間，以此循環(huán)下去，直到每子空間里面只包含一個數(shù)據(jù)點為止。直觀上來看，我們可以發(fā)現(xiàn)，那些密度很高的簇要被切很多次才會停止切割，即每個點都單獨存在于一個子空間內，但那些分布稀疏的點，大都很早就停到一個子空間內了。
訓練-測試過程
- 單棵樹的訓練
- 從訓練數(shù)據(jù)中隨機選擇 Ψ 個點作為子樣本，放入一棵孤立樹的根節(jié)點；
- 隨機指定一個維度，在當前節(jié)點數(shù)據(jù)范圍內，隨機產生一個切割點 p —— 切割點產生于當前節(jié)點數(shù)據(jù)中指定維度的最大值與最小值之間；
- 此切割點的選取生成了一個超平面，將當前節(jié)點數(shù)據(jù)空間切分為2個子空間：把當前所選維度下小于 p 的點放在當前節(jié)點的左分支，把大于等于 p 的點放在當前節(jié)點的右分支；
- 在節(jié)點的左分支和右分支節(jié)點遞歸步驟 2、3，不斷構造新的葉子節(jié)點，直到葉子節(jié)點上只有一個數(shù)據(jù)（無法再繼續(xù)切割） 或樹已經生長到了所設定的高度 。（至于為什么要對樹的高度做限制，后續(xù)會解釋）
上圖就是對子樣本進行切割訓練的過程，左圖的 xi 處于密度較高的區(qū)域，因此切割了十幾次才被分到了單獨的子空間，而右圖的 x0 落在邊緣分布較稀疏的區(qū)域，只經歷了四次切分就被 “孤立” 了。
- 整合全部孤立樹的結果
由于切割過程是完全隨機的，所以需要用 ensemble 的方法來使結果收斂，即反復從頭開始切，然后計算每次切分結果的平均值。
獲得 t 個孤立樹后，單棵樹的訓練就結束了。接下來就可以用生成的孤立樹來評估測試數(shù)據(jù)了，即計算異常分數(shù) s。對于每個樣本 x，需要對其綜合計算每棵樹的結果，通過下面的公式計算異常得分：
h(x) 為 x 在每棵樹的高度，c(Ψ) 為給定樣本數(shù) Ψ 時路徑長度的平均值，用來對樣本 x 的路徑長度 h(x) 進行標準化處理。
上圖為孤立樹的數(shù)目與每個樣本點的平均高度的關系，可以看到數(shù)目選取在 10 以內時，結果非常不穩(wěn)定，當數(shù)目達到 100 后就趨于收斂了。因此我們在使用過程中，樹的棵樹設置為 100 即可，如果棵樹過少結果可能不穩(wěn)定，若過多則白白浪費了系統(tǒng)開銷。
- 異常得分
如果異常得分接近 1，那么一定是異常點；
如果異常得分遠小于 0.5，那么一定不是異常點；
如果異常得分所有點的得分都在 0.5 左右，那么樣本中很可能不存在異常點。
算法偽代碼
第一段偽代碼為孤立樹的創(chuàng)建。
樹的高度限制 l 與子樣本數(shù)量 ψ 有關。之所以對樹的高度做限制，是因為我們只關心路徑長度較短的點，它們更可能是異常點，而并不關心那些路徑很長的正常點。
第二段偽代碼為每棵孤立樹的生長即訓練過程。
第三段偽代碼為每個樣本點的高度整合計算。
其中 c(size) 是一個 adjustment 項，因為有一些樣本點還沒有被孤立出來，樹就停止生長了，該項對其高度給出修正。
總結
孤立森林算法總共分兩步：
- 訓練 iForest：從訓練集中進行采樣，構建孤立樹，對森林中的每棵孤立樹進行測試，記錄路徑長度；
- 計算異常分數(shù)：根據(jù)異常分數(shù)計算公式，計算每個樣本點的 anomaly score。
兩個坑
在使用孤立森林進行實際異常檢測的過程中，可能有兩個坑：
- 若訓練樣本中異常樣本的比例較高，可能會導致最終結果不理想，因為這違背了該算法的理論基礎；
- 異常檢測跟具體的應用場景緊密相關，因此算法檢測出的 “異常” 不一定是實際場景中的真正異常，所以在特征選擇時，要盡量過濾不相關的特征。
一個生動的例子
因為我比較喜歡武林外傳，而且這部劇中每個人的特點都很鮮明，所以拿過來做例子。以下是 9 位主要角色的基本數(shù)據(jù)：
接下來，我們模擬一棵孤立樹的訓練過程，把這九個人作為一個子樣本放入一棵孤立樹的根節(jié)點：
首先隨機選擇到的維度是 “年齡”，然后隨機選擇一個切割點 18，小于 18 歲的只有莫小貝一個人，所以她最先被 “孤立” 出來了；第二個隨機選擇的特征是 ”體重“，只有大嘴高于 80 公斤，所以也被 ”孤立“ 了；第三個選擇 ”文化程度“ 這個特征，由于只有秀才的文化程度為高，于是被 ”孤立“ 出來了 ……
假設我們設定樹的高度為 3，那么這棵樹的訓練就結束了。在這棵樹上，莫小貝的路徑長度為 1，大嘴為 2，秀才為 3，單看這一棵樹，莫小貝的異常程度最高。但很顯然，她之所以最先被孤立出來，與特征被隨機選擇到的順序有關，所以我們通過對多棵樹進行訓練，來去除這種隨機性，讓結果盡量收斂。
