cross_val_score 如何对孤立森林_异常检测孤立森林(iForest)反欺诈

目前的异常值检测方法非常多，主要分为基于模型、基于距离、基于密度三大类。

关于异常的两个假设

1、异常数据跟样本中大多数数据不太一样。

2、异常数据在整体数据样本中占比比较小。

算法介绍

一维的情况

一维异常值情况

假设有一组一维数据（如上图所示），我们要对这组数据进行随机切分，希望可以把点 A 和点 B 单独切分出来。具体的，

先在最大值和最小值之间随机选择一个值 x，然后按照 <x 和 >=x 可以把数据分成左右两组

。接着，在刚切分的两组数据中分别重复这个步骤，直到数据不可再分。显然，点 B 跟其他数据比较疏离，可能用很少的次数就可以把它切分出来；点 A 跟其他数据点聚在一起，可能需要更多的次数才能把它切分出来。

二维的情况

二维异常值情况

假设有一组二维数据（如上图所示），我们要对这组数据进行随机切分，希望可以把点 A 和点 B 单独切分出来。具体的，

先在纵轴最大值和最小值之间随机选择一个值 y，然后按照 <y 和 >=y可以把数据分成上下两个平面，接着在横轴最大值和最小值之间随机选择一个值 x，然后按照 <x 和 >=x可以把数据分成左右两个平面，此时其实有了四个平面（先切哪个维度都可以）

。然后，在刚切分的平面上分别重复以上步骤，直到数据不可再分。显然，点 B 跟其他数据比较疏离，可能用很少的次数就可以把它切分出来；点 A 跟其他数据点聚在一起，可能需要更多的次数才能把它切分出来。

算法本质

直观理解上，异常数据由于跟其他数据点较为疏离，可能需要较少几次切分就可以将它们单独划分出来，而正常数据恰恰相反。这其实正是 Isolation Forest（IF）的核心概念。

IF采用二叉树去对数据进行切分，数据点在二叉树中所处的深度反应了该条数据的“疏离”程度

。

iTree能有效检测异常的假设是：异常点一般都是非常稀有的，

在iTree中会很快被划分到叶子节点

。

算法步骤

整个算法大致可以分为两步：

1. 训练：抽取多个样本，构建多棵二叉树（Isolation Tree，即 iTree）；
2. 预测：综合多棵二叉树的结果，计算每个数据点的异常分值。

训练

构建一棵 iTree 时，先从全量数据中随机抽取一批样本，然后随机选择一个特征作为起始节点，

(数据随机、特征随机)

并在该特征的最大值和最小值之间

随机选择一个值

，将样本中小于该取值的数据划到左分支，大于等于该取值的划到右分支。然后，在左右两个分支数据中，重复上述步骤，直到满足如下条件：

1. 数据不可再分，即：只包含一条数据，或者全部数据相同。
2. 二叉树达到限定的最大深度。

进行N次，这样我们就得到了N个（基本）不相同的树。 二分法是在中间选择。

下图是论文中表示孤立森林树的集合构建过程：其中X表示输入的数据，t表示树的个数，ψ表示采样的大小，输入表示t个数的集合。过程如下：先初始化树，l=math.ceil(math.log(subSampleSize)).toInt 是为了避免算法无限制的训练下去即

树的深度限制。每个树都随机采样样本，构成树的集合。

孤立森林训练树的构建

下图是论文中表示孤立森林单个树的构建过程：其中X表示输入的数据，e表示当前树的高度，l表示采树的深度限制，输出是一个完整的树

。

过程如下：如果树的深度大于限制深度或者数据不可分，直接返回树的叶子节点；如果数据集Q是X的子集，那么随机选取Q的属性q,在属性q的最大值和最小值之前选择一个切分点p，如果q<p归为左子树，如果q>=p归为右子树。一个节点包含左子树，右子树切分点属性q,和切分的值p，这样不断递归就构建了一颗完整的树。

孤立森林训练每个树的叶子节点构建

预测

计算数据 x 的异常分值时，先要估算它在每棵iTree中的路径长度（也可以叫深度）。具体的，先沿着一棵iTree，从根节点开始按不同特征的取值从上往下，直到到达某叶子节点。假设iTree的训练样本中同样落在x所在叶子节点的样本数为 T.size，则数据 x 在这棵 iTree 上的路径长度 h(x)，可以用下面这个公式计算：

公式中，

e 表示数据x从iTree的根节点到叶节点过程中经过的边的数目，C(T.size) 可以认为是一个修正值，它表示在一棵用T.size条样本数据构建的二叉树的平均路径长度

。一般的，C(n) 的计算公式如下：

其中，H(n-1) 可用 ln(n-1)+0.5772156649 估算，这里的常数是欧拉常数。数据 x 最终的异常分值 Score(x) 综合了多棵 iTree 的结果：

公式中，

E(h(x)) 表示数据 x 在多棵 iTree 的路径长度的均值

，

ψ

表示单棵 iTree 的训练样本的样本数，

C(

ψ

) 表示用

ψ

条数据构建的二叉树的平均路径长度，它在这里主要用来做归一化

。

下图是论文中的预测阶段路径长度的表示：x表示预测的一条数据，T表示一棵树，e表示当前所在树的深度，刚开始被初始化为0。输出是x的得分也就是评价的距离长度。如果T是叶子节点，直接返回h(x)，如果不是，将根据x的某个属性值a,继续划分，落到不同的左右节点上，不断的循环递归，直到遇到叶子节点，得到一个具体的路径长度。

孤立森林预测阶段路径长度计算

math.pow(2, -(predictions.sum/predictions.size)/cost(num_samples)) //Anomaly Score

从异常分值的公式看

1. 如果数据x在多棵iTree中的平均路径长度越短，得分越接近 1，表明数据 x 越异常；
2. 如果数据 x 在多棵 iTree中的平均路径长度越长，得分越接近0，表示数据x 越正常；
3. 如果数据 x 在多棵 iTree中的平均路径长度接近整体均值，则打分会在 0.5 附近。

分隔原理

从超空间的角度看，这样就是不断地用

随机选取的超平面切分样本点

，直到所有的样本点都被这些超平面“孤立”起来，即与其他样本点分隔开了。

用一个一个超平面，也就是说一棵树就是一个超平面去切分,样本点

。 我们可以看那些点用了较少的超平面就可以孤立出来，特别容易孤立出来的点。

一般距离密度较高的地方比较远，所处位置的样本点密度较小，因而也更容易被孤立。

因此，我们把非常容易被“孤立”的那些点判定为异常值。

度量孤立程度

如何度量一个样本点被“孤立”的容易程度呢？刘飞查询前面建立的决策树，找到这个样本所处的叶子结点的高度（与根节点的距离），一共是N和高度，求到的均值，就是这个容易程度了。算法的实现里，叶子结点的高度被归一化了，一般判定高度小于0.1的叶子结点对应的样本就是异常点。

可调参数

影响孤立森林效果的几个主要参数：

树的个数 (numTrees = 30)

当设定为 100 棵树，抽样样本数为256条时候，IF在大多数情况下就已经可以取得不错的效果。这也体现了算法的简单、高效。

树的深度(maxDepth =10)

math.ceil(math.log(subSampleSize)).toInt 为6 为了避免算法无限制的训练下去、直到真的把所有点都孤立起来，孤立森林会设置一个停止分割样本点的条件，即

树的深度限制

。这样做是有理由的：

需要切分很多次才能被孤立的样本点，所处的位置密度必然很高，这个点是异常点的概率很低

。

还要给每棵iTree设置最大高度

l=ceiling(log2Ψ)

，这是因为异常数据记录都比较少，其路径长度也比较低，而我们也只需要把正常记录和异常记录区分开来，因此只需要关心低于平均高度的部分就好，这样算法效率更高

认为异常的比例(contamination = 0.1)

这个参数是将所有的打分排序，获取最高的设置比例，实际情况可以根据需要，自行控制异常比例。

每个树的训练样本数量(maxSamples = 256)

训练一个树的时候，孤立森林会从样本中随机抽取一定数量的样本——抽样的数量不宜过大，

一般最大256个

。研究表明，这个小样本集的容量超过256以后，模型的效果提升不大，有时候反而会降低模型的效果。当样本太多的时候，

他们在高维空间中的分布会比较稠密，树会比较复杂，不利于离群点被区分出来

。

上图a是原始数据，下图b是采样了数据，蓝色是正常样本，红色是异常样本。可以看到，在采样之前，正常样本和异常样本出现重叠，因此很难分开，但我们采样之后，异常样本和正常样本可以明显的分开。

数据的要求

适用于连续数据（Continuous numerical data）的异常检测

适用场景

孤立森林的特点是计算量小、天生可以分布式训练和计算，非常适合海量数据的场景（如果数据的维度特别高，孤立森林的规模会过于庞大，就没有了计算开销较小的优势）。

优点

（1） iForest具有

线性时间复杂度

。因为是ensemble的方法，所以可以用在含有海量数据的数据集上面。通常

树的数量越多，算法越稳定

。由于每棵树都是互相独立生成的，因此可以部署在

大规模分布式系统上来加速运算

。

（2） iForest推动了重心估计（Mass Estimation）理论发展，目前在分类聚类和异常检测中都取得显著效果，发表于各大顶级数据挖掘会议和期刊（如SIGKDD，ICDM，ECML）。

缺点

（1）

iForest不适用于特别高维的数据

。由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低。

高维空间还可能存在大量噪音维度或无关维度（irrelevant attributes），影响树的构建。

对这类数据，建议使用子空间异常检测（Subspace Anomaly Detection）技术。此外，切割平面默认是axis-parallel的，也可以随机生成各种角度的切割平面，详见“On Detecting Clustered Anomalies Using SCiForest”。

（2） iForest仅对GlobalAnomaly敏感，即全局稀疏点敏感，不擅长处理局部的相对稀疏点 （Local Anomaly）。目前已有改进方法发表于PAKDD，详见“Improving iForest with Relative Mass”。

对于高维数据的处理

在处理高维数据时，可以对算法进行改进，采样之后并不是把所有的属性都用上，而是用峰度系数Kurtosis挑选一些有价值的属性，再进行iTree的构造，这跟随机森林就更像了，随机选记录，再随机选属性。

只使用正常样本

这个算法本质上是一个无监督学习，不需要数据的类标，有时候异常数据太少了，少到我们只舍得拿这几个异常样本进行测试，不能进行训练，论文提到只用正常样本构建IForest也是可行的，效果有降低，但也还不错，并可以通过适当调整采样大小来提高效果。

注意点

（1）如果训练样本中

异常样本的比例比较高

，违背了先前提到的异常检测的基本假设，可能最终的效果会受影响；

（2）异常检测跟具体的应用场景紧密相关，算法检测出的“异常”不一定是我们实际想要的。比如，在识别虚假交易时，异常的交易未必就是虚假的交易。所以，在特征选择时，可能需要

过滤不太相关的特征

，以免识别出一些不太相关的“异常”。

原文地址：

https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf?q=isolation-forest​cs.nju.edu.cn