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

整合全部孤立树的结果

由于切割过程是完全随机的，所以需要用 ensemble 的方法来使结果收敛，即反复从头开始切，然后计算每次切分结果的平均值。
获得 t 个孤立树后，单棵树的训练就结束了。接下来就可以用生成的孤立树来评估测试数据了，即计算异常分数 s 。对于每个样本 x ，需要对其综合计算每棵树的结果，通过下面的公式计算异常得分：

文章插图
h(x) 为 x 在每棵树的高度， c(Ψ) 为给定样本数 Ψ 时路径长度的平均值，用来对样本 x 的路径长度 h(x) 进行标准化处理。

文章插图
上图为孤立树的数目与每个样本点的平均高度的关系，可以看到数目选取在 10 以内时，结果非常不稳定，当数目达到 100 后就趋于收敛了。因此我们在使用过程中，树的棵树设置为 100 即可，如果棵树过少结果可能不稳定，若过多则白白浪费了系统开销。

异常得分

如果异常得分接近 1 ，那么一定是异常点；
如果异常得分远小于 0.5 ，那么一定不是异常点；
如果异常得分所有点的得分都在 0.5 左右，那么样本中很可能不存在异常点。

文章插图
算法伪代码

文章插图
第一段伪代码为孤立树的创建。
树的高度限制 l 与子样本数量 ψ 有关。之所以对树的高度做限制，是因为我们只关心路径长度较短的点，它们更可能是异常点，而并不关心那些路径很长的正常点。

文章插图
第二段伪代码为每棵孤立树的生长即训练过程。

文章插图
第三段伪代码为每个样本点的高度整合计算。
其中 c(size) 是一个 adjustment 项，因为有一些样本点还没有被孤立出来，树就停止生长了，该项对其高度给出修正。
总结孤立森林算法总共分两步：

训练 iForest：从训练集中进行采样，构建孤立树，对森林中的每棵孤立树进行测试，记录路径长度；
计算异常分数：根据异常分数计算公式，计算每个样本点的 anomaly score 。

两个坑在使用孤立森林进行实际异常检测的过程中，可能有两个坑：

若训练样本中异常样本的比例较高，可能会导致最终结果不理想，因为这违背了该算法的理论基础；
异常检测跟具体的应用场景紧密相关，因此算法检测出的 “异常” 不一定是实际场景中的真正异常，所以在特征选择时，要尽量过滤不相关的特征。

一个生动的例子
因为我比较喜欢武林外传，而且这部剧中每个人的特点都很鲜明，所以拿过来做例子。以下是 9 位主要角色的基本数据：

文章插图
接下来，我们模拟一棵孤立树的训练过程，把这九个人作为一个子样本放入一棵孤立树的根节点：

文章插图
首先随机选择到的维度是 “年龄” ，然后随机选择一个切割点 18 ，小于 18 岁的只有莫小贝一个人，所以她最先被 “孤立” 出来了；第二个随机选择的特征是 ”体重“ ，只有大嘴高于 80 公斤，所以也被 ”孤立“ 了；第三个选择 ”文化程度“ 这个特征，由于只有秀才的文化程度为高，于是被 ”孤立“ 出来了 ……
假设我们设定树的高度为 3 ，那么这棵树的训练就结束了。在这棵树上，莫小贝的路径长度为 1 ，大嘴为 2 ，秀才为 3 ，单看这一棵树，莫小贝的异常程度最高。但很显然，她之所以最先被孤立出来，与特征被随机选择到的顺序有关，所以我们通过对多棵树进行训练，来去除这种随机性，让结果尽量收敛。