隔离森林算法简介

孤立森林算法是一种适用于连续数据的无监督异常检测方法。它最初是由南京大学的周志华教授在2008年提出的，然后在2012提出了一个改进版本。与其他异常检测算法通过距离、密度等量化指标来描述样本之间的疏远程度不同，孤立森林算法通过隔离样本点来检测离群点。具体来说，该算法使用一种称为隔离树的二叉查找树结构来隔离样本。由于异常值数量少，且与大多数样本疏离，因此异常值会被较早隔离，即异常值会更靠近根节点，而正常值会更远离根节点。此外，与LOF和K-means等传统算法相比，孤立森林算法对高纬度数据具有更强的鲁棒性。

首先，我们给出了隔离树的定义和隔离树中样本点的路径长度。

孤立树:如果是孤立树的节点，有两种情况:外部节点没有子节点，内部节点有两个子节点和一个测试。中的测试由一个属性和一个拆分点组成，该点属于，反之亦然。

孤立树中样本点的路径长度:样本点从根节点到叶节点的边数。

从下图中我们可以直观的看到，相对异常的点只有经过4次切割才脱离整体，而比较正常的点经过11次分裂才脱离整体。这也体现了孤立森林算法的基本思想。(ps:图片来自原纸)

接下来，我们来详细介绍一下孤立森林算法。算法大致可以分为两个阶段。在第一阶段，我们需要训练一棵孤立的树，形成一个孤立的森林。然后我们把每个样点带入森林中的每棵孤立树，计算平均高度，再计算每个样点的异常值得分。

步骤1:对于给定的数据集，从其中随机选择一个样本点子集，并将其放入根节点。

步骤2:从尺寸中随机指定一个尺寸，并在当前数据中随机生成一个切割点。

第三步:这个切割点生成一个超平面，将当前数据空间分成两个子空间:指定维数小于p的样本点放入左侧子节点，维数大于等于p的样本点放入右侧子节点。

步骤4:递归地执行步骤2和步骤3，直到所有的叶子节点只有一个样本点或者孤立树已经达到指定的高度。

步骤5:循环步骤1到步骤4，直到生成一棵孤立树。

第二阶段:

Step1:对于每个数据点，使其遍历每棵孤立树，计算该点在森林中的平均高度，并归一化所有点的平均高度。异常值分数的计算公式如下:

其中，

参考资料:https://dl.acm.org/citation.cfm? doid = 213360.26665436366