Intro

  2008年刘飞、周志华等提出Isolation Forest算法，iforest不借助类似距离、密度等指标去描述样本与其他样本的差异，而是直接去刻画所谓的疏离程度(isolation)。该算法简单、高效，在工业界应用较多(好像没有看到很多case)~
  Isolation Forest算法的逻辑很直观，算法采用二叉树对数据进行split，样本选取、特征选取、split value选取都采用随机化的方式。如果某个样本是异常值，可能需要很少次数就可以切分出来。

算法逻辑

前提假设

前提假设(fewAndDifferent)

• 异常样本较少few
• 和正常样本差异较大different

算法思想

• 异常样本更容易快速落入叶子结点

训练

训练逻辑:

• 从原始数据中，不放回的抽取部分样本，构建一颗二叉树(iTree即Isolation Tree)
• 利用集成学习的思想，多次抽取样本，完成多棵iTree的构建。

iTree停止条件:

• 树达到指定的高度/深度
• 数据不可再分，即：只包含一条数据，或者全部数据相同

具体的算法如下:

几个小问题:

• 树的最大深度=ceiling(log(subsimpleSize))，paper里说自动指定，sklearn也是在代码中写死:
  max_depth = int(np.ceil(np.log2(max(max_samples, 2))))
  这个值接近树的平均深度，我们只关注那些小于平均深度的异常值，所以无需让树完全生长
• Sub-sampling size，建议256即可。大于256，性能上不会有大的提升
• Number of tree,建议100

预测

PathLength计算逻辑
  类似二分类模型，预测时可输出$P(y=1)$P(y=1)，iforest最终也可以输出一个异常得分。很容易想到用该样本落入叶子结点时，split的次数(即样本落入叶子结点经过的边)作为衡量指标，对于$t$t棵树，取平均即可。先看PathLength的计算逻辑：

PathLength计算公式如下：
$h(x) = e + c(T.size)$h(x)=e+c(T.size)
其中$e$e为样本$x$x从树的根节点到叶节点的过程中经历的边的个数，即split次数。$T.size$T.size表示和样本$x$x同在一个叶子结点样本的个数，$C(T.size)$C(T.size)可以看做一个修正值，表示$T.size$T.size个样本构建一个二叉树的平均路径长度。$c(n)$c(n)计算公式如下：
KaTeX parse error: No such environment: split at position 10: \begin{̲s̲p̲l̲i̲t̲}̲ c(n)&=2H(n-1)-…
其中，0.5772156649为欧拉常数

为何加入这一修正值？
由于树的深度设置为$ceiling(log(subsimpleSize))$ceiling(log(subsimpleSize)),所以可能大部分样本的PathLength都比较接近，而如果叶子结点的样本数越多，该样本是异常值的概率也较低(基于fewAndDifferent的假设)。另外$c(n)$c(n)是单调递增的，总之，加了修正，使得异常和正常样本的PathLength差异更大，可以简单的理解，如果样本快速落入叶子结点，并且该叶子结点的样本数较少，那么其为异常样本的可能性较大。

Anomaly score
样本落入叶子结点经过的边数(split次数)，除了和样本本身有关，也和limit length和抽样的样本子集有关系。这里，作者采用归一化的方式，把split length的值域映射到0-1之间。具体公式如下：
$s(x,n)=2^{-\frac{E(h(x))}{c(n)}}$s(x,n)=2−c(n)E(h(x))​

其中：

• $h(x)$h(x)为样本在iTree上的PathLength
• $E(h(x))$E(h(x))为样本在$t$t棵iTree的PathLength的均值
• $c(n)$c(n)为$n$n个样本构建一个二叉树的平均路径长度

上述公式，指数部分值域为$(- \infty,0)$(−∞,0)，因此$s$s值域为$(0,1)$(0,1)。当PathLength越小，$s$s越接近1，此时样本为异常值的概率越大。

其他

Paper遗留问题

• 实验评估逻辑
• 峰度筛选特征逻辑
• 判断异常值的阈值怎么定
• 特征的随机化，是在每一次split时做，还是subsample时候做？

Tricks

• subsample样本过多，引入较多的正样本，反而会影响模型的效果
• 特征筛选逻辑，根据峰度筛选

Ref

Paper
Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation forest."Data Mining, 2008. ICDM’08. Eighth IEEE International Conference on. IEEE, 2008.
Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation-based anomaly detection."ACM Transactions on Knowledge Discovery from Data (TKDD)6.1 (2012): 3.
Source Code
R源码
Python源码
Blog
知乎-iForest （Isolation Forest）孤立森林 异常检测 入门篇
知乎-机器学习-异常检测算法（一）：Isolation Forest

                                         2020-01-06 于南京市江宁区九龙湖