关于孤立森林算法，看这一篇就够了 _孤立森林算法

文章插图
孤立森林（Isolation Forest）算法是西瓜书作者周志华老师的团队研究开发的算法，一般用于结构化数据的异常检测。
异常的定义针对于不同类型的异常，要用不同的算法来进行检测，而孤立森林算法主要针对的是连续型结构化数据中的异常点。
使用孤立森林的前提是，将异常点定义为那些 “容易被孤立的离群点” —— 可以理解为分布稀疏，且距离高密度群体较远的点。从统计学来看，在数据空间里，若一个区域内只有分布稀疏的点，表示数据点落在此区域的概率很低，因此可以认为这些区域的点是异常的。
也就是说，孤立森林算法的理论基础有两点：

异常数据占总样本量的比例很小；
异常点的特征值与正常点的差异很大。

文章插图
上图中，中心的白色空心点为正常点，即处于高密度群体中。四周的黑色实心点为异常点，散落在高密度区域以外的空间。
使用场景孤立森林算法是基于 Ensemble 的异常检测方法，因此具有线性的时间复杂度。且精准度较高，在处理大数据时速度快，所以目前在工业界的应用范围比较广。常见的场景包括：网络安全中的攻击检测、金融交易欺诈检测、疾病侦测、噪声数据过滤（数据清洗）等。
与其他异常检测算法的差异孤立森林中的 “孤立” (isolation) 指的是 “把异常点从所有样本中孤立出来” ，论文中的原文是 “separating an instance from the rest of the instances”.
大多数基于模型的异常检测算法会先 ”规定“ 正常点的范围或模式，如果某个点不符合这个模式，或者说不在正常范围内，那么模型会将其判定为异常点。
孤立森林的创新点包括以下四个：

Partial models：在训练过程中，每棵孤立树都是随机选取部分样本；
No distance or density measures：不同于 KMeans、DBSCAN 等算法，孤立森林不需要计算有关距离、密度的指标，可大幅度提升速度，减小系统开销；
Linear time complexity：因为基于 ensemble ，所以有线性时间复杂度。通常树的数量越多，算法越稳定；
Handle extremely large data size：由于每棵树都是独立生成的，因此可部署在大规模分布式系统上来加速运算。

算法思想想象这样一个场景，我们用一个随机超平面对一个数据空间进行切割，切一次可以生成两个子空间（也可以想象用刀切蛋糕）。接下来，我们再继续随机选取超平面，来切割第一步得到的两个子空间，以此循环下去，直到每子空间里面只包含一个数据点为止。直观上来看，我们可以发现，那些密度很高的簇要被切很多次才会停止切割，即每个点都单独存在于一个子空间内，但那些分布稀疏的点，大都很早就停到一个子空间内了。

文章插图
训练-测试过程

单棵树的训练

从训练数据中随机选择 Ψ 个点作为子样本，放入一棵孤立树的根节点；
随机指定一个维度，在当前节点数据范围内，随机产生一个切割点 p —— 切割点产生于当前节点数据中指定维度的最大值与最小值之间；
此切割点的选取生成了一个超平面，将当前节点数据空间切分为2个子空间：把当前所选维度下小于 p 的点放在当前节点的左分支，把大于等于 p 的点放在当前节点的右分支；
在节点的左分支和右分支节点递归步骤 2、3 ，不断构造新的叶子节点，直到叶子节点上只有一个数据（无法再继续切割）或树已经生长到了所设定的高度。（至于为什么要对树的高度做限制，后续会解释）