孤立森林算法介紹，這次終于看懂了！

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

1. 孤立森林簡介

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

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

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

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

2. 算法思路

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

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

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

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

3. 以此切割點(diǎn)生成了一個超平面，然后將當(dāng)前節(jié)點(diǎn)數(shù)據(jù)空間劃分為2 個子空間：把指定維度里小于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)中只有一個數(shù)據(jù)（無法再繼續(xù)切割）或子節(jié)點(diǎn)已到達(dá)限定高度。

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

b 和c 的高度為3，a的高度是2，d的高度是1。可以看到d 最有可能是異常，因?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)練每個基本估計(jì)量。

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

         ?如果為float，則繪制max_samples * X.shape [0]個采樣。

         ?如果是“auto”，那么max_samples = min（256，n_samples）。

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

（3）contamination：float（0.，0.5），可選（默認(rèn)值= 0.1）

（4）數(shù)據(jù)集的contamination 量，即數(shù)據(jù)集中異常值的比例。在擬合時用于定義決策函數(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ù)測
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 表示正常值

代碼解釋：

猜你喜歡：

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