首页技术文章正文

孤立森林算法介绍,这次终于看懂了!

更新时间:2019-11-08 来源:黑马程序员 浏览量:

孤立森林算法应用于网络安全中的攻击检测,金融交易欺诈检测,疾病侦测,和噪声数据过滤等。

 

1. 孤立森林简介

iForest(IsolationForest)孤立森林是一个基于Ensemble 的快速异常检测方法,具有线性时间复杂度和高精准度,是符合大数据处理要求的state-of-the-art算法。


iForest 适用于连续数据的异常检测,将异常定义为“容易被孤立的离群点”,可以理解为分布稀疏且离密度高的群体较远的点。用统计学来解释,在数据空间里面,分布稀疏的区域表示数据发生在此区域的概率很低,因而可以认为落在这些区域里的数据是异常的。


iForest 即不用定义数学模型也不需要有标记的训练。对于如何查找哪些点是否容易被孤立,iForest 使用了一套非常高效的策略。


假设我们用一个随机超平面来切割数据空间, 切一次可以生成两个子空间。之后我们再继续用一个随机超平面来切割每个子空间,循环下去,直到每子空间里面只有一个数据点为止。直观上来讲,我们可以发现那些密度很高的簇是可以被切很多次才会停止切割,但是那些密度很低的点很容易很早的就停到一个子空间了。

 

 

1575879241325_孤立森林算法.png


2. 算法思路

怎么来切这个数据空间是iForest的设计核心思想,这里仅介绍最基本的方法。由于切割是随机的,所以需要用ensemble的方法来得到一个收敛值(蒙特卡洛方法),即反复从头开始切,然后平均每次切的结果。iForest由t个iTree(Isolation Tree)孤立树组成,每个iTree

是一个二叉树结构,其实现步骤如下:

1. 从训练数据中随机选择Ψ个点样本点作为子样本,放入树的根节点。

2. 随机指定一个维度,在当前节点数据中随机产生一个切割点p——切割点产生于当前节点数据中指定维度的最大值和最小值之间。

3. 以此切割点生成了一个超平面,然后将当前节点数据空间划分为2 个子空间:把指定维度里小于p的数据放在当前节点的左边,把大于等于p的数据放在当前节点的右边。

4. 在子节点中递归步骤2 和3,不断构造新的子节点,直到子节点中只有一个数据(无法再继续切割)或子节点已到达限定高度。

 

获得t个iTree之后,iForest训练就结束,然后我们可以用生成的iForest来评估测试数据了。对于一个训练数据x,我们令其遍历每一棵iTree,然后计算x 最终落在每个树第几层(x在树的高度)。然后我们可以得出x在每棵树的高度平均值。获得每个测试数据的高度平均值后,我们可以设置一个阈值(边界值),高度平均值低于此阈值的测试数据即为异常。也就是说异常在这些树中只有很短的平均高度。【推荐了解黑马程序员大数据课程

 

1575879250727_孤立森林算法2.png


b 和c 的高度为3,a的高度是2,d的高度是1。可以看到d 最有可能是异常,因为其最早就被孤立(isolated)了。

 

3. 算法建模

3.1 参数设置

(1)n_estimators:int,可选(默认值= 100),集合中的基本估计量的数量

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

         从X 中抽取的样本数量,以训练每个基本估计量。

         •如果为int,则绘制max_samples 采样。

         •如果为float,则绘制max_samples * X.shape [0]个采样。

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

         •如果max_samples 大于提供的样本数量,则所有样本都将用于所有树木(不进行采样)。

(3)contamination:float(0.,0.5),可选(默认值= 0.1)

(4)数据集的contamination 量,即数据集中异常值的比例。在拟合时用于定义决策函数的阈值。

3.2 代码实战

代码实现:

import pandas as pd
import numpy as np
from sklearn.ensemble import IsolationForest
#todo:孤立森林建模
#1. 生成训练数据
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)
# 产生一些异常数据
X_outliers = rng.uniform(low=-4, high=4, size=(20, 2))
iForest= IsolationForest(contamination=0.1)
iForest = iForest.fit(X_train)
#预测
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 表示正常值


代码解释:

1575879261041_孤立森林算法3.jpg


猜你喜欢:

图论算法介绍
冒泡排序算法

分享到:
在线咨询 我要报名
和我们在线交谈!