异常点检测-孤立森林

异常点检测-孤立森林Isolation Forest

1.基于划分的思想：
假设我们用一个随机超平面来切割（split）数据空间（data space）, 切一次可以生成两个子空间（想象拿刀切蛋糕一分为二）。之后我们再继续用一个随机超平面来切割每个子空间，循环下去，直到每子空间里面只有一个数据点为止。直观上来讲，我们可以发现那些密度很高的簇是可以被切很多次才会停止切割，但是那些密度很低的点很容易很早的就停到一个子空间了。
2.iTree的构造算法的流程

image.png
1）随机选择一个特征
2）随机选择该特征的一个值Value；
3）根据该特征对每个样本进行分类，把该特征值小于Value的记录放在左孩子，把大于等于Value的记录放在右孩子；
4）然后递归的构造左女儿和右女儿，直到满足以下条件中的其中之一：
- 传入的数据集只有一条记录或者多条一样的记录；
- 树的高度达到了限定高度；（树的高度达到log2(ψ)。其中ψ是采样的个数。不同于决策树，iTree在算法里面已经限制了树的高度。当然不限制也可以，只是算法为了效率考虑，只需要达到log2(ψ)深度即可。）
3.iForest的构造
image.png

iTree搞明白了，我们现在来看看iForest是怎么构造的，给定一个包含n条记录的数据集D，如何构造一个iForest。iForest和Random Forest的方法有些类似，都是随机采样一一部分数据集去构造每一棵树，保证不同树之间的差异性，不过iForest与RF不同，采样的数据量不需要等于n，可以远远小于n（随机森林的采样是等于n）,论文中提到采样大小超过256效果就提升不大了。
对于一个训练数据x，我们令其遍历每一棵iTree，然后计算x最终落在每个树第几层（x在树的高度）。然后我们可以得出x在每棵树的高度平均值，即 the average path length over t iTrees。

4.默认参数
iForest算法默认参数设置如下：
n_estimators: 默认为100，配置iTree树的多少
max_samples: 默认为265，配置采样大小
max_features: 默认为全部特征，对高维数据，可以只选取部分特征

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

参考资料：
机器学习之：异常检测