摘要：iForest用于挖掘異常數(shù)據(jù)，如網(wǎng)絡(luò)安全中的攻擊檢測和流量異常分析，金融機構(gòu)則用于挖掘出欺詐行為。算法對內(nèi)存要求很低，且處理速度很快，其時間復(fù)雜度也是線性的?？梢院芎玫奶幚砀呔S數(shù)據(jù)和大數(shù)據(jù)，并且也可以作為在線異常檢測。
01 孤立森林
isolation，意為孤立/隔離，是名詞，其動詞為isolate，forest是森林，合起來就是“孤立森林”了，也有叫“獨異森林”，好像并沒有統(tǒng)一的中文叫法。可能大家更習(xí)慣用其英文的名字isolation forest，簡稱iForest。
iForest算法用于挖掘異常(Anomaly)數(shù)據(jù)，或者說離群點挖掘，總之是在一大堆數(shù)據(jù)中，找出與其它數(shù)據(jù)的規(guī)律不太符合的數(shù)據(jù)。通常用于網(wǎng)絡(luò)安全中的攻擊檢測和流量異常等分析，金融機構(gòu)則用于挖掘出欺詐行為。對于找出的異常數(shù)據(jù)，然后要么直接清除異常數(shù)據(jù)，如數(shù)據(jù)清理中的去除噪聲數(shù)據(jù)，要么深入分析異常數(shù)據(jù)，比如分析攻擊、欺詐的行為特征。
算法起源于08年的一篇論文《Isolation Forest》，這論文由澳大利亞莫納什大學(xué)的兩位教授Fei Tony Liu, Kai Ming Ting(這兩個名字看起來都像是華人)和南京大學(xué)的周志華教授共同完成，而這三人在2011年又發(fā)表了《Isolation-based Anomaly Detection》，這兩篇論文算是確定了這個算法的基礎(chǔ)。
論文地址：
http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf
http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/tkdd11.pdf
關(guān)于算法 ，網(wǎng)上的中文資料也并不多，下面是搜索到周志華教授在2015-07-12發(fā)的信息：
ICML上遇到國際機器學(xué)習(xí)學(xué)會首任主席Dietterich教授，對我們的iForest算法大贊，說嘗試了很多方法，還是這個又快又好。前段時間澳洲某startup公司也說他們發(fā)現(xiàn)iForest在信息安全領(lǐng)域的異常檢測應(yīng)用中表現(xiàn)最佳并準(zhǔn)備做進(jìn)產(chǎn)品。isolation Forest，推薦給有異常檢測任務(wù)的同學(xué)。
從上面的評價中來看，iForest算法在實際的應(yīng)用中應(yīng)該具有不錯的效果，得益于隨機森林的思想，能快速處理大規(guī)模的數(shù)據(jù)，在當(dāng)前的大數(shù)據(jù)環(huán)境下，應(yīng)該很受歡迎。
02 算法原理
與隨機森林由大量決策樹組成一樣，iForest森林也由大量的樹組成。iForest中的樹叫isolation tree，簡稱iTree。iTree樹和決策樹不太一樣，其構(gòu)建過程也比決策樹簡單，因為其中就是一個完全隨機的過程。
假設(shè)數(shù)據(jù)集有N條數(shù)據(jù)，構(gòu)建一顆iTree時，從N條數(shù)據(jù)中均勻抽樣(一般是無放回抽樣)出ψ個樣本出來，作為這顆樹的訓(xùn)練樣本。
在樣本中，隨機選一個特征，并在這個特征的所有值范圍內(nèi)(最小值與最大值之間)隨機選一個值，對樣本進(jìn)行二叉劃分，將樣本中小于該值的劃分到節(jié)點的左邊，大于等于該值的劃分到節(jié)點的右邊。
這樣得到了一個分裂條件和左、右兩邊的數(shù)據(jù)集，然后分別在左右兩邊的數(shù)據(jù)集上重復(fù)上面的過程，直接達(dá)到終止條件。終止條件有兩個，一個是數(shù)據(jù)本身不可再分(只包括一個樣本，或者全部樣本相同)，另外一個是樹的高度達(dá)到log2(ψ)。不同于決策樹，iTree在算法里面已經(jīng)限制了樹的高度。當(dāng)然不限制也可以，只是算法為了效率考慮，只需要達(dá)到log2(ψ)深度即可。
把所有的iTree樹構(gòu)建好了，就可以對測數(shù)據(jù)進(jìn)行預(yù)測了。預(yù)測的過程就是把測試數(shù)據(jù)在iTree樹上沿對應(yīng)的條件分支往下走，直到達(dá)到葉子節(jié)點，并記錄這過程中經(jīng)過的路徑長度h(x)，即從根節(jié)點，穿過中間的節(jié)點，最后到達(dá)葉子節(jié)點，所走過的邊的數(shù)量(path length)。
最后，將h(x)帶入，計算每條待測數(shù)據(jù)的異常分?jǐn)?shù)(Anomaly Score)，其計算公式為：
其中 是二叉搜索樹的平均路徑長度，用來對結(jié)果進(jìn)行歸一化處理, 其中的H(k)可以通過公式
來估計，
是歐拉常數(shù)，其值為0.5772156649。
為路徑長度，
為森林中所有iTree樹的平均路徑長度。
使用異常分?jǐn)?shù)，具有以下性質(zhì)：
- 如果分?jǐn)?shù)越接近1，其是異常點的可能性越高；
- 如果分?jǐn)?shù)都比0.5要小，那么基本可以確定為正常數(shù)據(jù)；
- 如果所有分?jǐn)?shù)都在0.5附近，那么數(shù)據(jù)不包含明顯的異常樣本。
上面的步驟，可以總結(jié)為兩步：
- 訓(xùn)練：從訓(xùn)練集中進(jìn)行采樣，并構(gòu)建iTree樹；
- 測試：對iForest森林中的每顆iTree樹進(jìn)行測試，記錄path length，然后根據(jù)異常分?jǐn)?shù)計算公式，計算每條測試數(shù)據(jù)的anomaly score。
03 算法特點
在論文中，也比較了其它的常用異常挖掘的算法。比如常用的統(tǒng)計方法，基于分類的方法，和基于聚類的方法，這些傳統(tǒng)算法通常是對正常的數(shù)據(jù)構(gòu)建一個模型，然后把不符合這個模型的數(shù)據(jù)，認(rèn)為是異常數(shù)據(jù)。而且，這些模型通常為正常數(shù)據(jù)作優(yōu)化，而不是為異常數(shù)據(jù)作優(yōu)化。而iForest可以顯示地找出異常數(shù)據(jù)，而不用對正常的數(shù)據(jù)構(gòu)建模型。
由于異常數(shù)據(jù)的兩個特征（少且不同： few and different）
- 異常數(shù)據(jù)只占很少量;
- 異常數(shù)據(jù)特征值和正常數(shù)據(jù)差別很大。
異常數(shù)據(jù)的這兩個特征，確定了算法的理論基礎(chǔ)。因此，構(gòu)建二叉樹型結(jié)構(gòu)的時候，異常數(shù)據(jù)離根更近，而正常數(shù)據(jù)離根更遠(yuǎn)，更深。算法為了效率考慮，也限定了樹的深度：ceil(log2(n))，這個值近似于樹的平均深度，因為只需要關(guān)心那些低于平均高度的數(shù)據(jù)點，而不需要樹進(jìn)行完全生成。
算法只需要兩個參數(shù)：樹的多少與采樣的多少。實驗發(fā)現(xiàn)，在100顆樹的時候，路徑的長度就已經(jīng)覆蓋得比較好了，因此選100顆也就夠了。采樣，是為了更好的將正常數(shù)據(jù)和異常數(shù)據(jù)分離開來。有別于其它模型，采樣數(shù)據(jù)越多，反面會降低iForest識別異常數(shù)據(jù)的能力。因為，通常使用256個樣本，這也是scikit-learn實現(xiàn)時默認(rèn)使用的采樣數(shù)。
由于算法只需要采樣數(shù)據(jù)256條樣本，并且對樹的深度也有限制，因此，算法對內(nèi)存要求很低，且處理速度很快，其時間復(fù)雜度也是線性的。
不像其它算法，需要計算距離或者密度來尋找異常數(shù)據(jù)，iForest算法可以很好的處理高維數(shù)據(jù)和大數(shù)據(jù)，并且也可以作為在線預(yù)測。假設(shè)采樣為256條，結(jié)點最大為511個，假設(shè)一個節(jié)點占b字節(jié)，共使用t顆樹，那么需要的內(nèi)存只有511tb字節(jié)，基本上只需要幾M到幾十M的內(nèi)存就夠了。數(shù)據(jù)還顯示，預(yù)測287,748條數(shù)據(jù)只花了7.6秒。
另外，iForest既能發(fā)現(xiàn)群異常數(shù)據(jù)，也能發(fā)現(xiàn)散點異常數(shù)據(jù)。同時也能處理訓(xùn)練數(shù)據(jù)中不包含異常數(shù)據(jù)的情況。
這么好的算法，你還在等什么？
04 sklearn示例
IsolationForest在scikit-learn的0.18中才有實現(xiàn)，scikit-learn目前的stable版本為0.17，而0.18是dev版本。需要直接去github中clone。
源碼和文檔地址：
https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/ensemble/iforest.py
http://scikit-learn.org/dev/modules/generated/sklearn.ensemble.IsolationForest.html
下載源碼與安裝：
git clone https://github.com/scikit-learn/scikit-learn.git
cd scikit-learn
python setup.py install
算法基本上不需要配置參數(shù)就可以直接使用，通常就以下幾個(參數(shù)明顯比隨機森林簡單)：
n_estimators: 默認(rèn)為100，配置iTree樹的多少
max_samples: 默認(rèn)為265，配置采樣大小
max_features: 默認(rèn)為全部特征，對高維數(shù)據(jù)，可以只選取部分特征
示例：
import pandas as pd
from sklearn.ensemble import IsolationForest
ilf = IsolationForest(n_estimators=100,
n_jobs=-1, # 使用全部cpu
verbose=2,
)
data = pd.read_csv('data.csv', index_col="id")
data = data.fillna(0)
# 選取特征，不使用標(biāo)簽(類型)
X_cols = ["age", "salary", "sex"]
print data.shape
# 訓(xùn)練
ilf.fit(data[X_cols])
shape = data.shape[0]
batch = 10**6
all_pred = []
for i in range(shape/batch+1):
start = i * batch
end = (i+1) * batch
test = data[X_cols][start:end]
# 預(yù)測
pred = ilf.predict(test)
all_pred.extend(pred)
data['pred'] = all_pred
data.to_csv('outliers.csv', columns=["pred",], header=False)
算法的訓(xùn)練過程需要的內(nèi)存很少，但如果數(shù)據(jù)量太大，在預(yù)測的時候，可能會把內(nèi)存擠爆，上面代碼中的for循環(huán)便是分塊對數(shù)據(jù)進(jìn)行預(yù)測，最后再組合起來。
- 參考文章
http://www.cnblogs.com/fengfenggirl/p/iForest.html
http://qf6101.github.io/machine%20learning/2015/08/01/Isolation-Forest/
