全國(guó)咨詢(xún)/投訴熱線:400-618-4000

首頁(yè)技術(shù)文章正文

孤立森林算法介紹,這次終于看懂了!

更新時(shí)間:2019-11-08 來(lái)源:黑馬程序員 瀏覽量:

孤立森林算法應(yīng)用于網(wǎng)絡(luò)安全中的攻擊檢測(cè),金融交易欺詐檢測(cè),疾病偵測(cè),和噪聲數(shù)據(jù)過(guò)濾等。

 

1. 孤立森林簡(jiǎn)介

iForest(IsolationForest)孤立森林是一個(gè)基于Ensemble 的快速異常檢測(cè)方法,具有線性時(shí)間復(fù)雜度和高精準(zhǔn)度,是符合大數(shù)據(jù)處理要求的state-of-the-art算法。


iForest 適用于連續(xù)數(shù)據(jù)的異常檢測(cè),將異常定義為“容易被孤立的離群點(diǎn)”,可以理解為分布稀疏且離密度高的群體較遠(yuǎn)的點(diǎn)。用統(tǒng)計(jì)學(xué)來(lái)解釋?zhuān)跀?shù)據(jù)空間里面,分布稀疏的區(qū)域表示數(shù)據(jù)發(fā)生在此區(qū)域的概率很低,因而可以認(rèn)為落在這些區(qū)域里的數(shù)據(jù)是異常的。


iForest 即不用定義數(shù)學(xué)模型也不需要有標(biāo)記的訓(xùn)練。對(duì)于如何查找哪些點(diǎn)是否容易被孤立,iForest 使用了一套非常高效的策略。


假設(shè)我們用一個(gè)隨機(jī)超平面來(lái)切割數(shù)據(jù)空間, 切一次可以生成兩個(gè)子空間。之后我們?cè)倮^續(xù)用一個(gè)隨機(jī)超平面來(lái)切割每個(gè)子空間,循環(huán)下去,直到每子空間里面只有一個(gè)數(shù)據(jù)點(diǎn)為止。直觀上來(lái)講,我們可以發(fā)現(xiàn)那些密度很高的簇是可以被切很多次才會(huì)停止切割,但是那些密度很低的點(diǎn)很容易很早的就停到一個(gè)子空間了。

 

 

1575879241325_孤立森林算法.png


2. 算法思路

怎么來(lái)切這個(gè)數(shù)據(jù)空間是iForest的設(shè)計(jì)核心思想,這里僅介紹最基本的方法。由于切割是隨機(jī)的,所以需要用ensemble的方法來(lái)得到一個(gè)收斂值(蒙特卡洛方法),即反復(fù)從頭開(kāi)始切,然后平均每次切的結(jié)果。iForest由t個(gè)iTree(Isolation Tree)孤立樹(shù)組成,每個(gè)iTree

是一個(gè)二叉樹(shù)結(jié)構(gòu),其實(shí)現(xiàn)步驟如下:

1. 從訓(xùn)練數(shù)據(jù)中隨機(jī)選擇Ψ個(gè)點(diǎn)樣本點(diǎn)作為子樣本,放入樹(shù)的根節(jié)點(diǎn)。

2. 隨機(jī)指定一個(gè)維度,在當(dāng)前節(jié)點(diǎn)數(shù)據(jù)中隨機(jī)產(chǎn)生一個(gè)切割點(diǎn)p——切割點(diǎn)產(chǎn)生于當(dāng)前節(jié)點(diǎn)數(shù)據(jù)中指定維度的最大值和最小值之間。

3. 以此切割點(diǎn)生成了一個(gè)超平面,然后將當(dāng)前節(jié)點(diǎn)數(shù)據(jù)空間劃分為2 個(gè)子空間:把指定維度里小于p的數(shù)據(jù)放在當(dāng)前節(jié)點(diǎn)的左邊,把大于等于p的數(shù)據(jù)放在當(dāng)前節(jié)點(diǎn)的右邊。

4. 在子節(jié)點(diǎn)中遞歸步驟2 和3,不斷構(gòu)造新的子節(jié)點(diǎn),直到子節(jié)點(diǎn)中只有一個(gè)數(shù)據(jù)(無(wú)法再繼續(xù)切割)或子節(jié)點(diǎn)已到達(dá)限定高度。

 

獲得t個(gè)iTree之后,iForest訓(xùn)練就結(jié)束,然后我們可以用生成的iForest來(lái)評(píng)估測(cè)試數(shù)據(jù)了。對(duì)于一個(gè)訓(xùn)練數(shù)據(jù)x,我們令其遍歷每一棵iTree,然后計(jì)算x 最終落在每個(gè)樹(shù)第幾層(x在樹(shù)的高度)。然后我們可以得出x在每棵樹(shù)的高度平均值。獲得每個(gè)測(cè)試數(shù)據(jù)的高度平均值后,我們可以設(shè)置一個(gè)閾值(邊界值),高度平均值低于此閾值的測(cè)試數(shù)據(jù)即為異常。也就是說(shuō)異常在這些樹(shù)中只有很短的平均高度?!就扑]了解黑馬程序員大數(shù)據(jù)課程

 

1575879250727_孤立森林算法2.png


b 和c 的高度為3,a的高度是2,d的高度是1??梢钥吹絛 最有可能是異常,因?yàn)槠渥钤缇捅还铝ⅲ╥solated)了。

 

3. 算法建模

3.1 參數(shù)設(shè)置

(1)n_estimators:int,可選(默認(rèn)值= 100),集合中的基本估計(jì)量的數(shù)量

(2)max_samples:int 或float,optional(default =“auto”)

         從X 中抽取的樣本數(shù)量,以訓(xùn)練每個(gè)基本估計(jì)量。

         ?如果為int,則繪制max_samples 采樣。

         ?如果為float,則繪制max_samples * X.shape [0]個(gè)采樣。

         ?如果是“auto”,那么max_samples = min(256,n_samples)。

         ?如果max_samples 大于提供的樣本數(shù)量,則所有樣本都將用于所有樹(shù)木(不進(jìn)行采樣)。

(3)contamination:float(0.,0.5),可選(默認(rèn)值= 0.1)

(4)數(shù)據(jù)集的contamination 量,即數(shù)據(jù)集中異常值的比例。在擬合時(shí)用于定義決策函數(shù)的閾值。

3.2 代碼實(shí)戰(zhàn)

代碼實(shí)現(xiàn):

import pandas as pd
import numpy as np
from sklearn.ensemble import IsolationForest
#todo:孤立森林建模
#1. 生成訓(xùn)練數(shù)據(jù)
rng = np.random.RandomState(42)
X = 0.3 * rng.randn(100, 2) #生成100 行,2 列
X_train = np.r_[X + 2, X - 2]
print(X_train)
# 產(chǎn)生一些異常數(shù)據(jù)
X_outliers = rng.uniform(low=-4, high=4, size=(20, 2))
iForest= IsolationForest(contamination=0.1)
iForest = iForest.fit(X_train)
#預(yù)測(cè)
pred = iForest.predict(X_outliers)
print(pred)
# [-1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
#-1 為異常值1 表示正常值


代碼解釋?zhuān)?

1575879261041_孤立森林算法3.jpg


猜你喜歡:

圖論算法介紹
冒泡排序算法

分享到:
在線咨詢(xún) 我要報(bào)名
和我們?cè)诰€交談!