摘要：iForest用于挖掘異常數(shù)據(jù)步绸，如網(wǎng)絡(luò)安全中的攻擊檢測(cè)和流量異常分析，金融機(jī)構(gòu)則用于挖掘出欺詐行為。算法對(duì)內(nèi)存要求很低，且處理速度很快辕漂，其時(shí)間復(fù)雜度也是線性的烛芬∑统保可以很好的處理高維數(shù)據(jù)和大數(shù)據(jù)揍堰，并且也可以作為在線異常檢測(cè)隐砸。

0x14.jpg

01 孤立森林

isolation式塌，意為孤立/隔離偏窝，是名詞劳淆，其動(dòng)詞為isolate，forest是森林疾捍，合起來(lái)就是“孤立森林”了吊趾，也有叫“獨(dú)異森林”，好像并沒(méi)有統(tǒng)一的中文叫法坟瓢≌赣梗可能大家更習(xí)慣用其英文的名字isolation forest执赡，簡(jiǎn)稱iForest。

iForest算法用于挖掘異常(Anomaly)數(shù)據(jù)函筋，或者說(shuō)離群點(diǎn)挖掘沙合，總之是在一大堆數(shù)據(jù)中，找出與其它數(shù)據(jù)的規(guī)律不太符合的數(shù)據(jù)跌帐。通常用于網(wǎng)絡(luò)安全中的攻擊檢測(cè)和流量異常等分析首懈，金融機(jī)構(gòu)則用于挖掘出欺詐行為。對(duì)于找出的異常數(shù)據(jù)谨敛，然后要么直接清除異常數(shù)據(jù)究履，如數(shù)據(jù)清理中的去除噪聲數(shù)據(jù)，要么深入分析異常數(shù)據(jù)脸狸，比如分析攻擊最仑、欺詐的行為特征。

算法起源于08年的一篇論文《Isolation Forest》炊甲，這論文由澳大利亞莫納什大學(xué)的兩位教授Fei Tony Liu, Kai Ming Ting(這兩個(gè)名字看起來(lái)都像是華人)和南京大學(xué)的周志華教授共同完成泥彤，而這三人在2011年又發(fā)表了《Isolation-based Anomaly Detection》，這兩篇論文算是確定了這個(gè)算法的基礎(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上遇到國(guó)際機(jī)器學(xué)習(xí)學(xué)會(huì)首任主席Dietterich教授颈娜，對(duì)我們的iForest算法大贊剑逃，說(shuō)嘗試了很多方法，還是這個(gè)又快又好揭鳞。前段時(shí)間澳洲某startup公司也說(shuō)他們發(fā)現(xiàn)iForest在信息安全領(lǐng)域的異常檢測(cè)應(yīng)用中表現(xiàn)最佳并準(zhǔn)備做進(jìn)產(chǎn)品炕贵。isolation Forest，推薦給有異常檢測(cè)任務(wù)的同學(xué)野崇。

從上面的評(píng)價(jià)中來(lái)看称开，iForest算法在實(shí)際的應(yīng)用中應(yīng)該具有不錯(cuò)的效果，得益于隨機(jī)森林的思想乓梨，能快速處理大規(guī)模的數(shù)據(jù)鳖轰，在當(dāng)前的大數(shù)據(jù)環(huán)境下，應(yīng)該很受歡迎扶镀。

02 算法原理

與隨機(jī)森林由大量決策樹組成一樣蕴侣，iForest森林也由大量的樹組成。iForest中的樹叫isolation tree臭觉，簡(jiǎn)稱iTree昆雀。iTree樹和決策樹不太一樣辱志，其構(gòu)建過(guò)程也比決策樹簡(jiǎn)單，因?yàn)槠渲芯褪且粋€(gè)完全隨機(jī)的過(guò)程狞膘。

假設(shè)數(shù)據(jù)集有N條數(shù)據(jù)揩懒，構(gòu)建一顆iTree時(shí)，從N條數(shù)據(jù)中均勻抽樣(一般是無(wú)放回抽樣)出ψ個(gè)樣本出來(lái)挽封，作為這顆樹的訓(xùn)練樣本已球。

在樣本中，隨機(jī)選一個(gè)特征辅愿，并在這個(gè)特征的所有值范圍內(nèi)(最小值與最大值之間)隨機(jī)選一個(gè)值智亮，對(duì)樣本進(jìn)行二叉劃分，將樣本中小于該值的劃分到節(jié)點(diǎn)的左邊点待，大于等于該值的劃分到節(jié)點(diǎn)的右邊阔蛉。

這樣得到了一個(gè)分裂條件和左、右兩邊的數(shù)據(jù)集亦鳞，然后分別在左右兩邊的數(shù)據(jù)集上重復(fù)上面的過(guò)程馍忽，直接達(dá)到終止條件。終止條件有兩個(gè)燕差，一個(gè)是數(shù)據(jù)本身不可再分(只包括一個(gè)樣本遭笋，或者全部樣本相同)，另外一個(gè)是樹的高度達(dá)到log2(ψ)徒探。不同于決策樹瓦呼，iTree在算法里面已經(jīng)限制了樹的高度。當(dāng)然不限制也可以测暗，只是算法為了效率考慮央串，只需要達(dá)到log2(ψ)深度即可。

把所有的iTree樹構(gòu)建好了碗啄，就可以對(duì)測(cè)數(shù)據(jù)進(jìn)行預(yù)測(cè)了质和。預(yù)測(cè)的過(guò)程就是把測(cè)試數(shù)據(jù)在iTree樹上沿對(duì)應(yīng)的條件分支往下走，直到達(dá)到葉子節(jié)點(diǎn)稚字，并記錄這過(guò)程中經(jīng)過(guò)的路徑長(zhǎng)度h(x)饲宿，即從根節(jié)點(diǎn)，穿過(guò)中間的節(jié)點(diǎn)胆描，最后到達(dá)葉子節(jié)點(diǎn)瘫想，所走過(guò)的邊的數(shù)量(path length)。

最后昌讲，將h(x)帶入国夜，計(jì)算每條待測(cè)數(shù)據(jù)的異常分?jǐn)?shù)(Anomaly Score)，其計(jì)算公式為：

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

其中 $ c(n) = 2H(n ? 1) ? (2(n ? 1)/n) $ 是二叉搜索樹的平均路徑長(zhǎng)度短绸，用來(lái)對(duì)結(jié)果進(jìn)行歸一化處理, 其中的H(k)可以通過(guò)公式 $ H(k) = ln(k) + \xi $來(lái)估計(jì)车吹，$\xi$是歐拉常數(shù)筹裕，其值為0.5772156649。

$ h(x)$ 為路徑長(zhǎng)度礼搁，$ E(h(x)) $ 為森林中所有iTree樹的平均路徑長(zhǎng)度饶碘。

使用異常分?jǐn)?shù)，具有以下性質(zhì)：

如果分?jǐn)?shù)越接近1馒吴，其是異常點(diǎn)的可能性越高；

如果分?jǐn)?shù)都比0.5要小瑟曲，那么基本可以確定為正常數(shù)據(jù)饮戳；

如果所有分?jǐn)?shù)都在0.5附近，那么數(shù)據(jù)不包含明顯的異常樣本洞拨。

上面的步驟扯罐，可以總結(jié)為兩步：

訓(xùn)練：從訓(xùn)練集中進(jìn)行采樣，并構(gòu)建iTree樹烦衣；

測(cè)試：對(duì)iForest森林中的每顆iTree樹進(jìn)行測(cè)試歹河，記錄path length，然后根據(jù)異常分?jǐn)?shù)計(jì)算公式花吟，計(jì)算每條測(cè)試數(shù)據(jù)的anomaly score秸歧。

03 算法特點(diǎn)

在論文中，也比較了其它的常用異常挖掘的算法衅澈。比如常用的統(tǒng)計(jì)方法键菱，基于分類的方法，和基于聚類的方法今布，這些傳統(tǒng)算法通常是對(duì)正常的數(shù)據(jù)構(gòu)建一個(gè)模型经备，然后把不符合這個(gè)模型的數(shù)據(jù)，認(rèn)為是異常數(shù)據(jù)部默。而且侵蒙，這些模型通常為正常數(shù)據(jù)作優(yōu)化，而不是為異常數(shù)據(jù)作優(yōu)化傅蹂。而iForest可以顯示地找出異常數(shù)據(jù)纷闺，而不用對(duì)正常的數(shù)據(jù)構(gòu)建模型。

由于異常數(shù)據(jù)的兩個(gè)特征（少且不同： few and different）

異常數(shù)據(jù)只占很少量;

異常數(shù)據(jù)特征值和正常數(shù)據(jù)差別很大贬派。

異常數(shù)據(jù)的這兩個(gè)特征急但，確定了算法的理論基礎(chǔ)。因此搞乏，構(gòu)建二叉樹型結(jié)構(gòu)的時(shí)候波桩，異常數(shù)據(jù)離根更近，而正常數(shù)據(jù)離根更遠(yuǎn)请敦，更深镐躲。算法為了效率考慮储玫，也限定了樹的深度：ceil(log2(n))，這個(gè)值近似于樹的平均深度萤皂，因?yàn)橹恍枰P(guān)心那些低于平均高度的數(shù)據(jù)點(diǎn)撒穷，而不需要樹進(jìn)行完全生成。

算法只需要兩個(gè)參數(shù)：樹的多少與采樣的多少裆熙。實(shí)驗(yàn)發(fā)現(xiàn)端礼，在100顆樹的時(shí)候，路徑的長(zhǎng)度就已經(jīng)覆蓋得比較好了入录，因此選100顆也就夠了蛤奥。采樣，是為了更好的將正常數(shù)據(jù)和異常數(shù)據(jù)分離開來(lái)僚稿。有別于其它模型凡桥，采樣數(shù)據(jù)越多，反面會(huì)降低iForest識(shí)別異常數(shù)據(jù)的能力蚀同。因?yàn)槊骞簦ǔＪ褂?56個(gè)樣本，這也是scikit-learn實(shí)現(xiàn)時(shí)默認(rèn)使用的采樣數(shù)蠢络。

由于算法只需要采樣數(shù)據(jù)256條樣本衰猛，并且對(duì)樹的深度也有限制，因此谢肾，算法對(duì)內(nèi)存要求很低腕侄，且處理速度很快，其時(shí)間復(fù)雜度也是線性的芦疏。

不像其它算法冕杠，需要計(jì)算距離或者密度來(lái)尋找異常數(shù)據(jù)，iForest算法可以很好的處理高維數(shù)據(jù)和大數(shù)據(jù)酸茴，并且也可以作為在線預(yù)測(cè)分预。假設(shè)采樣為256條，結(jié)點(diǎn)最大為511個(gè)薪捍，假設(shè)一個(gè)節(jié)點(diǎn)占b字節(jié)笼痹，共使用t顆樹，那么需要的內(nèi)存只有511tb字節(jié)酪穿，基本上只需要幾M到幾十M的內(nèi)存就夠了凳干。數(shù)據(jù)還顯示，預(yù)測(cè)287,748條數(shù)據(jù)只花了7.6秒被济。

另外救赐，iForest既能發(fā)現(xiàn)群異常數(shù)據(jù)，也能發(fā)現(xiàn)散點(diǎn)異常數(shù)據(jù)只磷。同時(shí)也能處理訓(xùn)練數(shù)據(jù)中不包含異常數(shù)據(jù)的情況经磅。

這么好的算法泌绣，你還在等什么？

04 sklearn示例

IsolationForest在scikit-learn的0.18中才有實(shí)現(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.gitcdscikit-learnpythonsetup.pyinstall

算法基本上不需要配置參數(shù)就可以直接使用苗沧，通常就以下幾個(gè)(參數(shù)明顯比隨機(jī)森林簡(jiǎn)單)：

n_estimators: 默認(rèn)為100，配置iTree樹的多少

max_samples: 默認(rèn)為265炭晒，配置采樣大小

max_features: 默認(rèn)為全部特征崎页，對(duì)高維數(shù)據(jù)，可以只選取部分特征

示例：

importpandas as pdfrom sklearn.ensembleimportIsolationForestilf= IsolationForest(n_estimators=100,n_jobs=-1,# 使用全部cpuverbose=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**6all_pred= []for iinrange(shape/batch+1):start= i * batchend= (i+1) * batchtest= data[X_cols][start:end]# 預(yù)測(cè)pred= ilf.predict(test)? ? all_pred.extend(pred)data['pred'] = all_preddata.to_csv('outliers.csv',columns=["pred",],header=False)

算法的訓(xùn)練過(guò)程需要的內(nèi)存很少，但如果數(shù)據(jù)量太大蜈膨，在預(yù)測(cè)的時(shí)候屿笼，可能會(huì)把內(nèi)存擠爆，上面代碼中的for循環(huán)便是分塊對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)翁巍，最后再組合起來(lái)驴一。

參考文章

http://www.cnblogs.com/fengfenggirl/p/iForest.html

http://qf6101.github.io/machine%20learning/2015/08/01/Isolation-Forest/