0x14 異常挖掘各吨,Isolation Forest

摘要: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)該很受歡迎口猜。


知識(shí)星球.jpeg

02 算法原理

與隨機(jī)森林由大量決策樹(shù)組成一樣,iForest森林也由大量的樹(shù)組成透揣。iForest中的樹(shù)叫isolation tree济炎,簡(jiǎn)稱iTree。iTree樹(shù)和決策樹(shù)不太一樣辐真,其構(gòu)建過(guò)程也比決策樹(shù)簡(jiǎn)單须尚,因?yàn)槠渲芯褪且粋€(gè)完全隨機(jī)的過(guò)程。

假設(shè)數(shù)據(jù)集有N條數(shù)據(jù)侍咱,構(gòu)建一顆iTree時(shí)耐床,從N條數(shù)據(jù)中均勻抽樣(一般是無(wú)放回抽樣)出ψ個(gè)樣本出來(lái),作為這顆樹(shù)的訓(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è)是樹(shù)的高度達(dá)到log2(ψ)塔插。不同于決策樹(shù),iTree在算法里面已經(jīng)限制了樹(shù)的高度拓哟。當(dāng)然不限制也可以想许,只是算法為了效率考慮,只需要達(dá)到log2(ψ)深度即可断序。

把所有的iTree樹(shù)構(gòu)建好了流纹,就可以對(duì)測(cè)數(shù)據(jù)進(jìn)行預(yù)測(cè)了。預(yù)測(cè)的過(guò)程就是把測(cè)試數(shù)據(jù)在iTree樹(shù)上沿對(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) 是二叉搜索樹(shù)的平均路徑長(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樹(shù)的平均路徑長(zhǎng)度掀亥。

使用異常分?jǐn)?shù)撞反,具有以下性質(zhì):

  1. 如果分?jǐn)?shù)越接近1,其是異常點(diǎn)的可能性越高铺浇;
  2. 如果分?jǐn)?shù)都比0.5要小痢畜,那么基本可以確定為正常數(shù)據(jù)垛膝;
  3. 如果所有分?jǐn)?shù)都在0.5附近鳍侣,那么數(shù)據(jù)不包含明顯的異常樣本。

上面的步驟吼拥,可以總結(jié)為兩步:

  1. 訓(xùn)練:從訓(xùn)練集中進(jìn)行采樣倚聚,并構(gòu)建iTree樹(shù);
  2. 測(cè)試:對(duì)iForest森林中的每顆iTree樹(shù)進(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)

  1. 異常數(shù)據(jù)只占很少量;
  2. 異常數(shù)據(jù)特征值和正常數(shù)據(jù)差別很大设联。

異常數(shù)據(jù)的這兩個(gè)特征,確定了算法的理論基礎(chǔ)灼捂。因此仑荐,構(gòu)建二叉樹(shù)型結(jié)構(gòu)的時(shí)候,異常數(shù)據(jù)離根更近纵东,而正常數(shù)據(jù)離根更遠(yuǎn)粘招,更深。算法為了效率考慮偎球,也限定了樹(shù)的深度:ceil(log2(n))洒扎,這個(gè)值近似于樹(shù)的平均深度,因?yàn)橹恍枰P(guān)心那些低于平均高度的數(shù)據(jù)點(diǎn)衰絮,而不需要樹(shù)進(jìn)行完全生成袍冷。

算法只需要兩個(gè)參數(shù):樹(shù)的多少與采樣的多少。實(shí)驗(yàn)發(fā)現(xiàn)猫牡,在100顆樹(shù)的時(shí)候胡诗,路徑的長(zhǎng)度就已經(jīng)覆蓋得比較好了,因此選100顆也就夠了淌友。采樣煌恢,是為了更好的將正常數(shù)據(jù)和異常數(shù)據(jù)分離開(kāi)來(lái)。有別于其它模型震庭,采樣數(shù)據(jù)越多瑰抵,反面會(huì)降低iForest識(shí)別異常數(shù)據(jù)的能力。因?yàn)槠髁ǔJ褂?56個(gè)樣本二汛,這也是scikit-learn實(shí)現(xiàn)時(shí)默認(rèn)使用的采樣數(shù)婿崭。

由于算法只需要采樣數(shù)據(jù)256條樣本,并且對(duì)樹(shù)的深度也有限制肴颊,因此氓栈,算法對(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顆樹(shù)婉陷,那么需要的內(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.git
cd scikit-learn
python setup.py install
知識(shí)星球.jpeg

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

n_estimators: 默認(rèn)為100荣挨,配置iTree樹(shù)的多少
max_samples: 默認(rèn)為265,配置采樣大小
max_features: 默認(rèn)為全部特征朴摊,對(duì)高維數(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ù)測(cè)
    pred = ilf.predict(test)
    all_pred.extend(pred)

data['pred'] = all_pred
data.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/

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末这溅,一起剝皮案震驚了整個(gè)濱河市组民,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌悲靴,老刑警劉巖臭胜,帶你破解...
    沈念sama閱讀 216,496評(píng)論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異癞尚,居然都是意外死亡耸三,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,407評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門浇揩,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)仪壮,“玉大人,你說(shuō)我怎么就攤上這事胳徽』” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 162,632評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵养盗,是天一觀的道長(zhǎng)缚陷。 經(jīng)常有香客問(wèn)我,道長(zhǎng)往核,這世上最難降的妖魔是什么箫爷? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,180評(píng)論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮聂儒,結(jié)果婚禮上蝶缀,老公的妹妹穿的比我還像新娘。我一直安慰自己薄货,他們只是感情好翁都,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,198評(píng)論 6 388
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著谅猾,像睡著了一般柄慰。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上税娜,一...
    開(kāi)封第一講書(shū)人閱讀 51,165評(píng)論 1 299
  • 那天坐搔,我揣著相機(jī)與錄音,去河邊找鬼敬矩。 笑死概行,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的弧岳。 我是一名探鬼主播凳忙,決...
    沈念sama閱讀 40,052評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼业踏,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了涧卵?” 一聲冷哼從身側(cè)響起勤家,我...
    開(kāi)封第一講書(shū)人閱讀 38,910評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎柳恐,沒(méi)想到半個(gè)月后伐脖,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,324評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡乐设,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,542評(píng)論 2 332
  • 正文 我和宋清朗相戀三年讼庇,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片近尚。...
    茶點(diǎn)故事閱讀 39,711評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡巫俺,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出肿男,到底是詐尸還是另有隱情介汹,我是刑警寧澤,帶...
    沈念sama閱讀 35,424評(píng)論 5 343
  • 正文 年R本政府宣布舶沛,位于F島的核電站嘹承,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏如庭。R本人自食惡果不足惜叹卷,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,017評(píng)論 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望坪它。 院中可真熱鬧骤竹,春花似錦、人聲如沸往毡。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,668評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)开瞭。三九已至懒震,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間嗤详,已是汗流浹背个扰。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,823評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留葱色,地道東北人递宅。 一個(gè)月前我還...
    沈念sama閱讀 47,722評(píng)論 2 368
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親办龄。 傳聞我的和親對(duì)象是個(gè)殘疾皇子烘绽,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,611評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容