首先隨機(jī)選擇到的維度是 “年齡”盯蝴，然后隨機(jī)選擇一個(gè)切割點(diǎn) 18碘耳，小于 18 歲的只有莫小貝一個(gè)人，所以她最先被 “孤立” 出來(lái)了僻澎；第二個(gè)隨機(jī)選擇的特征是 ”體重“，只有大嘴高于 80 公斤十饥，所以也被 ”孤立“ 了窟勃；第三個(gè)選擇 ”文化程度“ 這個(gè)特征，由于只有秀才的文化程度為高逗堵，于是被 ”孤立“ 出來(lái)了 ……
假設(shè)我們?cè)O(shè)定樹(shù)的高度為 3秉氧，那么這棵樹(shù)的訓(xùn)練就結(jié)束了。在這棵樹(shù)上蜒秤，莫小貝的路徑長(zhǎng)度為 1汁咏，大嘴為 2，秀才為 3作媚，單看這一棵樹(shù)攘滩，莫小貝的異常程度最高。但很顯然纸泡，她之所以最先被孤立出來(lái)漂问，與特征被隨機(jī)選擇到的順序有關(guān)，所以我們通過(guò)對(duì)多棵樹(shù)進(jìn)行訓(xùn)練女揭，來(lái)去除這種隨機(jī)性蚤假，讓結(jié)果盡量收斂。
1.原理
使用孤立森林的前提是吧兔，將異常點(diǎn)定義為那些 “容易被孤立的離群點(diǎn)——孤立森林算法的理論基礎(chǔ)有兩點(diǎn)：
- 異常數(shù)據(jù)占總樣本量的比例很辛籽觥；
- 異常點(diǎn)的特征值與正常點(diǎn)的差異很大境蔼。
1.1算法思想
想象-我們用一個(gè)隨機(jī)超平面對(duì)一個(gè)數(shù)據(jù)空間進(jìn)行切割灶平，切一次可以生成兩個(gè)子空間-伺通。接下來(lái)，我們?cè)倮^續(xù)隨機(jī)選取超平面民逼，來(lái)切割第一步得到的兩個(gè)子空間泵殴，以此循環(huán)下去，直到每子空間里面只包含一個(gè)數(shù)據(jù)點(diǎn)為止拼苍。直觀上來(lái)看笑诅，我們可以發(fā)現(xiàn)，那些密度很高的簇要被切很多次才會(huì)停止切割疮鲫，即每個(gè)點(diǎn)都單獨(dú)存在于一個(gè)子空間內(nèi)吆你，但那些分布稀疏的點(diǎn)，大都很早就停到一個(gè)子空間內(nèi)了
孤立森林算法總共分兩步：
訓(xùn)練 iForest：從訓(xùn)練集中進(jìn)行采樣俊犯，構(gòu)建孤立樹(shù)妇多，對(duì)森林中的每棵孤立樹(shù)進(jìn)行測(cè)試，記錄路徑長(zhǎng)度燕侠；
計(jì)算異常分?jǐn)?shù)：根據(jù)異常分?jǐn)?shù)計(jì)算公式者祖，計(jì)算每個(gè)樣本點(diǎn)的 anomaly score。
1.2單棵樹(shù)的訓(xùn)練
- 從訓(xùn)練數(shù)據(jù)中隨機(jī)選擇 Ψ 個(gè)點(diǎn)作為子樣本绢彤，放入一棵孤立樹(shù)的根節(jié)點(diǎn)七问；
- 隨機(jī)指定一個(gè)維度，在當(dāng)前節(jié)點(diǎn)數(shù)據(jù)范圍內(nèi)茫舶，隨機(jī)產(chǎn)生一個(gè)切割點(diǎn) p—— 切割點(diǎn)產(chǎn)生于當(dāng)前節(jié)點(diǎn)數(shù)據(jù)中指定維度的最大值與最小值之間
- 此切割點(diǎn)的選取生成了一個(gè)超平面械巡，將當(dāng)前節(jié)點(diǎn)數(shù)據(jù)空間切分為2個(gè)子空間：把當(dāng)前所選維度下小于 p 的點(diǎn)放在當(dāng)前節(jié)點(diǎn)的左分支，把大于等于 p 的點(diǎn)放在當(dāng)前節(jié)點(diǎn)的右分支饶氏；
- 在節(jié)點(diǎn)的左分支和右分支節(jié)點(diǎn)遞歸步驟 2讥耗、3，不斷構(gòu)造新的葉子節(jié)點(diǎn)疹启，直到葉子節(jié)點(diǎn)上只有一個(gè)數(shù)據(jù)（無(wú)法再繼續(xù)切割） 或樹(shù)已經(jīng)生長(zhǎng)到了所設(shè)定的高度 古程。（至于為什么要對(duì)樹(shù)的高度做限制，后續(xù)會(huì)解釋）
1.3整合全部孤立樹(shù)的結(jié)果
由于切割過(guò)程是完全隨機(jī)的喊崖，所以需要用 ensemble 的方法來(lái)使結(jié)果收斂籍琳，即反復(fù)從頭開(kāi)始切，然后計(jì)算每次切分結(jié)果的平均值贷祈。
獲得 t 個(gè)孤立樹(shù)后，單棵樹(shù)的訓(xùn)練就結(jié)束了喝峦。接下來(lái)就可以用生成的孤立樹(shù)來(lái)評(píng)估測(cè)試數(shù)據(jù)了势誊，即計(jì)算異常分?jǐn)?shù) s。對(duì)于每個(gè)樣本 x谣蠢，需要對(duì)其綜合計(jì)算每棵樹(shù)的結(jié)果粟耻，通過(guò)下面的公式計(jì)算異常得分：
h(x) 為 x 在每棵樹(shù)的高度查近，c(Ψ) 為給定樣本數(shù) Ψ 時(shí)路徑長(zhǎng)度的平均值，用來(lái)對(duì)樣本 x 的路徑長(zhǎng)度 h(x) 進(jìn)行標(biāo)準(zhǔn)化處理挤忙。
如果異常得分接近 1霜威，那么一定是異常點(diǎn)；
如果異常得分遠(yuǎn)小于 0.5册烈，那么一定不是異常點(diǎn)戈泼；
如果異常得分所有點(diǎn)的得分都在 0.5 左右，那么樣本中很可能不存在異常點(diǎn)赏僧。
1.4偽代碼
1.孤立樹(shù)的創(chuàng)建大猛。
樹(shù)的高度限制 l 與子樣本數(shù)量 ψ 有關(guān)。之所以對(duì)樹(shù)的高度做限制淀零，是因?yàn)槲覀冎魂P(guān)心路徑長(zhǎng)度較短的點(diǎn)挽绩，它們更可能是異常點(diǎn)，而并不關(guān)心那些路徑很長(zhǎng)的正常點(diǎn)驾中。
2.每棵孤立樹(shù)的生長(zhǎng)即訓(xùn)練過(guò)程唉堪。
3.為每個(gè)樣本點(diǎn)的高度整合計(jì)算。
其中 c(size) 是一個(gè) adjustment 項(xiàng)肩民，因?yàn)橛幸恍颖军c(diǎn)還沒(méi)有被孤立出來(lái)唠亚，樹(shù)就停止生長(zhǎng)了，該項(xiàng)對(duì)其高度給出修正此改。
2.總結(jié)
孤立森林中的 “孤立” (isolation) 指的是 “把異常點(diǎn)從所有樣本中孤立出來(lái)”趾撵，論文中的原文是 “separating an instance from the rest of the instances”.
大多數(shù)基于模型的異常檢測(cè)算法會(huì)先 ”規(guī)定“ 正常點(diǎn)的范圍或模式，如果某個(gè)點(diǎn)不符合這個(gè)模式共啃，或者說(shuō)不在正常范圍內(nèi)占调，那么模型會(huì)將其判定為異常點(diǎn)。
優(yōu)點(diǎn)：
- Partial models：在訓(xùn)練過(guò)程中移剪，每棵孤立樹(shù)都是隨機(jī)選取部分樣本究珊；
- No distance or density measures：不同于 KMeans、DBSCAN 等算法纵苛，孤立森林不需要計(jì)算有關(guān)距離剿涮、密度的指標(biāo)，可大幅度提升速度攻人，減小系統(tǒng)開(kāi)銷取试；
- Linear time complexity：因?yàn)?strong>基于 ensemble，所以有線性時(shí)間復(fù)雜度怀吻。通常樹(shù)的數(shù)量越多瞬浓，算法越穩(wěn)定；
- Handle extremely large data size：由于每棵樹(shù)都是獨(dú)立生成的蓬坡，因此可部署在大規(guī)模分布式系統(tǒng)上來(lái)加速運(yùn)算猿棉。
缺點(diǎn)：
若訓(xùn)練樣本中異常樣本的比例較高磅叛，可能會(huì)導(dǎo)致最終結(jié)果不理想，因?yàn)檫@違背了該算法的理論基礎(chǔ)萨赁；
異常檢測(cè)跟具體的應(yīng)用場(chǎng)景緊密相關(guān)弊琴，因此算法檢測(cè)出的 “異常” 不一定是實(shí)際場(chǎng)景中的真正異常杖爽，所以在特征選擇時(shí)敲董，要盡量過(guò)濾不相關(guān)的特征。
3.sklearn
IsolationForest(behaviour=' deprecated", bootstrap=False, contamination=0.1, max_features=1.0, max_samples=' auto',n_estimators=5e, n_jobs=None, random_state=None, verbose=e, warm_start=False)
- n_estimators : 森林中樹(shù)的顆數(shù)
- max_samples : 對(duì)每棵樹(shù)掂林，樣本個(gè)數(shù)或比例
- contamination : 用戶設(shè)置樣本中異常點(diǎn)的比例
- bootstrap,采樣是有放回還是無(wú)放回
- max_features : 對(duì)每棵樹(shù)臣缀，特征個(gè)數(shù)或比例
方法
- predict(X)返回值：+1 表示正常樣本， -1表示異常樣本泻帮。
- decision_function(X) 返回樣本的異常評(píng)分精置。 值越小表示越有可能是異常樣本。
import numpy as np
from sklearn.ensemble import IsolationForest
a=[[1,2,3,4,5,7,8],
[2,3,4,5,6,8,9],
[2,3,4,5,6,7,8],
[1,3,5,6,6,7,8],
[1,10,3,5,6,2,3],
[45,67,88,52,85,84,63]]
df = np.array(a)
rng = np.random.RandomState(42)
n_samples=6 #樣本總數(shù)
# fit the model
clf = IsolationForest(max_samples=n_samples, random_state=rng, contamination=0.33) #contamination為異常樣本比例
clf.fit(df)
scores_pred = clf.decision_function(df)
print(scores_pred, '----------\n', clf.predict(df))
test=[[2,4,50,3,5,69,8]]
print(clf.decision_function(test))
[ 0.07008625 0.11427815 0.14274793 0.10726402 0.00840173 -0.26031859]
---------------
[ 1 1 1 1 -1 -1]
[0.00754274]
