【算法系列】孤独森林（Isolation Forest）异常点监测方法，附源码

背景

iForest （Isolation Forest）孤立森林是一个基于Ensemble的快速异常检测方法，具有线性时间复杂度和高精准度，是符合大数据处理要求的state-of-the-art算法。其可以用于网络安全中的攻击检测，金融交易欺诈检测，疾病侦测，和噪声数据过滤等。

数据异常的两个特点：

• 异常数据只占很少量
• 异常数据特征值和正常数据差别很大

现有的异常检测方法：

• 主要是通过对正常样本的描述，给出一个正常样本在特征空间中的区域，对于不在这个区域中的样本，视为异常。
• 主要缺点：异常检测器只会对正常样本的描述做优化，而不会对异常样本的描述做优化，这样就有可能造成大量的误报，或者只检测到少量的异常。

孤立森林异常点检测法：

• 在孤立森林(iForest)中，异常被定义为“容易被孤立的离群点 (more likely to be separated)”，可以将其理解为分布稀疏且离密度高的群体较远的点。

• 在特征空间里，分布稀疏的区域表示事件发生在该区域的概率很低，因而可以认为落在这些区域里的数据是异常的。

• 孤立森林是一种适用于连续数据(Continuous numerical data)的无监督异常检测方法，即不需要有标记的样本来训练，但特征需要是连续的。

• 对于如何查找哪些点容易被孤立(isolated)，iForest使用了一套非常高效的策略。在孤立森林中，递归地随机分割数据集，直到所有的样本点都是孤立的。在这种随机分割的策略下，异常点通常具有较短的路径。
  即切一次数据空间可以生成两个子空间（想象拿刀切蛋糕一分为二）。之后我们再继续用一个随机超平面来切割每个子空间，循环下去，直到每子空间里面只有一个数据点为止。

• 直观上来讲，那些密度很高的簇是需要被切很多次才能被孤立，但是那些密度很低的点很容易就可以被孤立。这里参考下面的图进行说明。
  
  

孤立树的特点：

• 孤立森林作为孤立树的总体，将具有较短路径长度的点识别为异常点，不同的树扮演不同异常识别的专家。
• 已经存在的那些异常检测的方法大部分都期望有更多的数据，但是在孤立森林中，小数据集往往能取得更好的效果。样本数较多会降低孤立森林孤立异常点的能力，因为正常样本会干扰隔离的过程，降低隔离异常的能力。子采样就是在这种情况下被提出的。
• swamping和masking是异常检测中比较关键的问题：
  swamping指的是错误地将正常样本预测为异常。当正常样本很靠近异常样本时，隔离异常时需要的拆分次数会增加，使得从正常样本中区分出异常样本更加困难。
  

masking指的是存在大量异常点隐藏了他们的本来面目。当异常簇比较大，并且比较密集时，同样需要更多的拆分才能将他们隔离出来。上面的这两种情况使得孤立异常点变得更加困难。

故如果异常样本和其他正常样本相似度很高或者其在空间里分布稠密，那么iForest无效。

• 孤立树的独有特点使得孤立森林能够通过子采样建立局部模型，减小swamping和masking对模型效果的影响。其中的原因是：子采样可以控制每棵孤立树的数据量；每棵孤立树专门用来识别特定的子样本。

iForest异常检测的过程

包括两个步骤：

• 训练阶段，基于训练集的子样本来建立孤立树；
• 测试阶段，用孤立树为每一个测试样本计算异常分数。

训练阶段

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

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

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

4. 在孩子节点中递归步骤2和3，不断构造新的孩子节点，直到孩子节点中只有一个数据（无法再继续切割） 或孩子节点已到达限定高度（子节点中可能存在多个数据）。

测试阶段

获得t个iTree之后，iForest 训练就结束，然后我们可以用生成的iForest来评估测试数据了。

1. 对于一个训练数据x，我们令其遍历每一棵iTree，然后计算x最终落在每个树第几层（x在树的高度）。
2. 得出x在每棵树的高度平均值，即 the average path length over t iTrees。如果x落在一个节点中含多个训练数据，可以使用一个公式来修正x的高度计算，详细公式推导见原论文。
3. 设置一个阈值（边界值），average path length 低于此阈值的测试数据即为异常。
   值得注意的是，论文中对树的高度做了归一化，并得出一个0到1的数值，即越短的高度越接近1（异常的可能性越高）。

iForest算法默认参数设置如下：

• subsample size: 256
• Tree height： 8
• Number of trees: 100

通俗解释就是——建100棵iTree，每棵iTree最高8层，且每棵iTree都是独立随机选择256个数据样本建成。

其他

• iForest不适用于特别高维的数据。由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低。高维空间还可能存在大量噪音维度或无关维度（irrelevant attributes），影响树的构建。
• 对高维数据，建议使用子空间异常检测（Subspace Anomaly Detection）技术。
• 此外，切割平面默认是axis-parallel的，也可以随机生成各种角度的切割平面，详见“On Detecting Clustered Anomalies Using SCiForest”。
• iForest仅对Global Anomaly 敏感，即全局稀疏点敏感，不擅长处理局部的相对稀疏点 （Local Anomaly）。目前已有改进方法发表于PAKDD，详见“Improving iForest with Relative Mass”。

参考资料

[1] https://www.jianshu.com/p/5af3c66e0410?utm_campaign=maleskine
[2] https://blog.csdn.net/extremebingo/article/details/80108247

论文及源码下载

• 论文：
  http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf
  http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/tkdd11.pdf
• 源码：
  R语言 https://sourceforge.net/projects/iforest/
  Python语言 http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html
  Java语言 http://weka.sourceforge.net/packageMetaData/isolationForest/index.html
  Matlab语言 https://github.com/zhuye88/iForest