异常值挖掘方法——孤立森林Isolation Forest

异常值挖掘方法

一、内容概览

内容大致分为两大部分，第一部分是异常值挖掘方法概述，简略介绍异常值挖掘方法的分类及其优缺点。第二部分介绍孤立森林算法（iForest），Isolation Forest 简称 iForest，该算法是周志华在2010年提出的一个异常值检测算法，在工业界很实用，算法效果好，时间效率高。第二部分包括对iForest算法思想、原理、流程的介绍，以及来自sklearn官网上的一个iForest例子实战讲解，并附上代码与注释。

二、异常值挖掘方法概述

2.1统计量检验

先对变量做一个描述性统计，进而查看哪些数据是不合理的。如箱型图分析，平均值，最大最小值分析，统计学上的3σ法则等。 假设原数据服从某个分布（如高斯分布），然后计算 $\mu$ 和 $\sigma$再计算$(\mu -3\sigma ,\mu +3\sigma )$的区间，最后落在区间之外的数据点就被认为是异常值。

• 优点：

  1.比较直观，方法简单

  2.建立在标准的统计学理论之上，当存在充分数据以及选对检验方法时，效果非常好。

• 缺点：

  适合一元场合情况之下，对于高维数据，检验可能性较差。

2.2基于邻近度的方法

通常可以在对象之间定义邻近性度量，并且许多移仓检测方法都基于邻近度。异常对象是那些远离大部分其他对象的对象，这一邻域的许多技术都基于距离，称作基于距离的离群点检测技术，代表算法：基于KNN的密度检测算法。

• 优点：

  原理简单，比统计量检验法应用范围更广。

• 缺点：

  1.基于邻近度的方法一般需要O(m^2)时间(其中m是对象个数)，这对于大型数据集可能代价过高。

  2.该方法对参数的选择是敏感的。

  3.不能处理具有不同密度区域的数据集，不能考虑这种密度的变化。

2.3基于密度的离群点检测

离群点是在低密度区域中的对象。基于密度的离群点检测与基于邻近度的离群点检测密切相关，因为密度通常用邻近度定义。一种常用的定义密度的方法是，定义密度为到k个最近邻的平均距离的倒数。如果该距离小，则密度高，反之亦然。

• 优点：

  1.给出了对象离群程度的定量度量。

  2.数据具有不同密度的区域也能够很好地处理。

• 缺点：

  1.有O(m^2)时间复杂度(其中m是对象个数)

  2.参数选择困难，评估指标缺乏参照标准。

2.4基于聚类的离群点检测

一种利用聚类检测离群点的方法是丢弃原理其他簇的小簇。这种方法可以与任何聚类技术一起使用，但是需要最小簇大小和小簇与其他簇之间距离的阈值，通常，该过程可以简化为丢弃小于某个最小尺寸的所有簇。

• 优点

  1. 聚类技术(如K均值)的时间和空间复杂度是线性或接近线性的，该检测技术较为高效的。
  2. 可能同时发现簇和离群点（簇的定义通常是离群点的补）

• 缺点

  产生的离群点集和它们的得分可能非常依赖所用的簇的个数和数据总离群点的存在性。聚类算法产生的簇的 质量对该算法产生的离群点的质量影响非常大。

三、孤立森林

3.1思想介绍

对于如何查找哪些点是否容易被孤立，iForest使用了一套非常高效的策略。假设我们用一个随机超平面来切割数据空间, 切一次可以生成两个子空间，再继续用一个随机超平面来切割每个子空间，循环下去，直到每子空间里面只有一个数据点为止。那些密度很高的簇是可以被切很多次才会停止切割，但是那些密度很低的点很容易很早的就停到一个子空间了。由于切割是随机的，所以需要用集成（ensemble）的方法来得到一个收敛值，即反复从头开始切，然后平均每次切的结果，且随着森林中树木棵树增多，收敛越快。孤立森林为给定的数据集构建了一组iTree，较少的异常实例会导致树结构中的较短路径，而且具有可区分的属性值的实例更可能在早期分区。 因此，当一棵由随机树木组成的森林为某些特定点共同产生较短的路径长度时，则它们很可能是异常的。通过集成算法求出平均路径长度之后，异常是那些在iTree上具有较短平均路径长度的实例。

如图2.1所示，异常更容易被隔离，因此路径长度较短。正常点xi需要隔离十二个随机分区，xo异常仅需要隔离四个分区，显然异常点更早被区分出来。

3.2 算法原理

• 疑问：为什么要用树结构来分区？

递归分区可以用树结构表示，所以隔离一个点所需的分区数等于从根节点到终止节点的路径长度。

孤立森林算法总共分两步：

1. 训练 iForest：从训练集中进行采样，构建孤立树，对森林中的每棵孤立树进行测试，记录路径长度；

   2.计算异常分数：根据异常分数计算公式，计算每个样本点的 anomaly score。

• 训练iForest实现步骤如下：

1. 从训练数据中随机选择t个点样本点作为子样本，放入树的根节点。
2. 随机指定一个属性，在当前节点数据中随机产生一个切割点p(切割点产生于当前节指定属性的最大值和最小值之间)。
3. 以此切割点生成了一个超平面，然后将当前节点数据空间划分为2个子空间：把指定属性里小于p的数据放在当前节点的左孩子，把大于等于p的数据放在当前节点的右孩子。
4. 在孩子节点中递归步骤2和3，不断构造新的孩子节点，直到 孩子节点中只有一个数据（无法再继续切割） 或 孩子节点已到达限定高度 。

• 计算异常分数

获得t个iTree之后，iForest 训练就结束，然后就可以用生成的iForest来评估测试数据。对于一个训练数据x，我们令其遍历每一棵iTree，然后计算x最终落在每个树第几层（x在树的高度）。然后我们可以得出x在每棵树的高度平均值，即 平均路径长度（the average path length over t iTrees）,通过平均路径长度可以得到每个实例的异常分数。

如图4.2所示，a,b,c,d四个实例中，d的平均路径最短，最早被区分出来，可能是异常值点。

平均路径长度:
c ( n ) = 2 H ( n − 1 ) − ( 2 ( n − 1 ) / n ) (1) c(n)=2H(n-1)-(2(n-1)/n)\tag{1} c(n)=2H(n−1)−(2(n−<