網盛創新研究院 - AI、區塊鏈、云計算、大數據技術的研究與應用交流平臺!

網盛創新研究院/百科/正文

孤立森林

相關新聞/

Related Info

1 孤立森林

isolation,意為孤立/隔離,是名詞,其動詞為isolate,forest是森林,合起來就是“孤立森林”了,也有叫“獨異森林”,好像并沒有統一的中文叫法。可能大家更習慣用其英文的名字isolation forest,簡稱iForest。

iForest算法用于挖掘異常(Anomaly)數據,或者說離群點挖掘,總之是在一大堆數據中,找出與其它數據的規律不太符合的數據。通常用于網絡安全中的攻擊檢測和流量異常等分析,金融機構則用于挖掘出欺詐行為。對于找出的異常數據,然后要么直接清除異常數據,如數據清理中的去除噪聲數據,要么深入分析異常數據,比如分析攻擊、欺詐的行為特征。

2 算法原理

與隨機森林由大量決策樹組成一樣,iForest森林也由大量的樹組成。iForest中的樹叫isolation tree,簡稱iTree。iTree樹和決策樹不太一樣,其構建過程也比決策樹簡單,因為其中就是一個完全隨機的過程。

假設數據集有N條數據,構建一顆iTree時,從N條數據中均勻抽樣(一般是無放回抽樣)出ψ個樣本出來,作為這顆樹的訓練樣本。

在樣本中,隨機選一個特征,并在這個特征的所有值范圍內(最小值與最大值之間)隨機選一個值,對樣本進行二叉劃分,將樣本中小于該值的劃分到節點的左邊,大于等于該值的劃分到節點的右邊。

這樣得到了一個分裂條件和左、右兩邊的數據集,然后分別在左右兩邊的數據集上重復上面的過程,直接達到終止條件。終止條件有兩個,一個是數據本身不可再分(只包括一個樣本,或者全部樣本相同),另外一個是樹的高度達到log2(ψ)。不同于決策樹,iTree在算法里面已經限制了樹的高度。當然不限制也可以,只是算法為了效率考慮,只需要達到log2(ψ)深度即可。

把所有的iTree樹構建好了,就可以對測數據進行預測了。預測的過程就是把測試數據在iTree樹上沿對應的條件分支往下走,直到達到葉子節點,并記錄這過程中經過的路徑長度h(x),即從根節點,穿過中間的節點,最后到達葉子節點,所走過的邊的數量(path length)。

最后,將h(x)帶入,計算每條待測數據的異常分數(Anomaly Score),其計算公式為:

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

其中 $ c(n) = 2H(n ? 1) ? (2(n ? 1)/n) $ 是二叉搜索樹的平均路徑長度,用來對結果進行歸一化處理, 其中的H(k)可以通過公式 $ H(k) = ln(k) + xi $來估計,$xi$是歐拉常數,其值為0.5772156649。

$ h(x)$ 為路徑長度,$ E(h(x)) $ 為森林中所有iTree樹的平均路徑長度。

使用異常分數,具有以下性質:

 
  1. 1、如果分數越接近1,其是異常點的可能性越高;

  2. 2、如果分數都比0.5要小,那么基本可以確定為正常數據;

  3. 3、如果所有分數都在0.5附近,那么數據不包含明顯的異常樣本。

上面的步驟,可以總結為兩步:

 
  1. 1、訓練:從訓練集中進行采樣,并構建iTree樹;

  2. 2、測試:對iForest森林中的每顆iTree樹進行測試,記錄path length,然后根據異常分數計算公式,計算每條測試數據的anomaly score。

3 算法特點

在論文中,也比較了其它的常用異常挖掘的算法。比如常用的統計方法,基于分類的方法,和基于聚類的方法,這些傳統算法通常是對正常的數據構建一個模型,然后把不符合這個模型的數據,認為是異常數據。而且,這些模型通常為正常數據作優化,而不是為異常數據作優化。而iForest可以顯示地找出異常數據,而不用對正常的數據構建模型。

由于異常數據的兩個特征(少且不同: few and different)

 
  1. 1、異常數據只占很少量;

  2. 2、異常數據特征值和正常數據差別很大。

異常數據的這兩個特征,確定了算法的理論基礎。因此,構建二叉樹型結構的時候,異常數據離根更近,而正常數據離根更遠,更深。算法為了效率考慮,也限定了樹的深度:ceil(log2(n)),這個值近似于樹的平均深度,因為只需要關心那些低于平均高度的數據點,而不需要樹進行完全生成。

算法只需要兩個參數:樹的多少與采樣的多少。實驗發現,在100顆樹的時候,路徑的長度就已經覆蓋得比較好了,因此選100顆也就夠了。采樣,是為了更好的將正常數據和異常數據分離開來。有別于其它模型,采樣數據越多,反面會降低iForest識別異常數據的能力。因為,通常使用256個樣本,這也是scikit-learn實現時默認使用的采樣數。

由于算法只需要采樣數據256條樣本,并且對樹的深度也有限制,因此,算法對內存要求很低,且處理速度很快,其時間復雜度也是線性的。

不像其它算法,需要計算距離或者密度來尋找異常數據,iForest算法可以很好的處理高維數據和大數據,并且也可以作為在線預測。假設采樣為256條,結點最大為511個,假設一個節點占b字節,共使用t顆樹,那么需要的內存只有511tb字節,基本上只需要幾M到幾十M的內存就夠了。數據還顯示,預測287,748條數據只花了7.6秒。

另外,iForest既能發現群異常數據,也能發現散點異常數據。同時也能處理訓練數據中不包含異常數據的情況。


標簽:
關于我們創新研究院大講堂服務介紹
? 生意寶(002095) 版權所有  浙公網安備 33010002000015號 工商執照 浙ICP證  網絡工商
韩国色情禁片视频床,玉女聊斋1998 免费观看,韩国禁片大全电影在线 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>