孤立森林(Isolation Forest)

iForest

无参数无监督方法。

假设用一个随机超平面切割数据空间,切一次产生两个子空间,依次循环下去直到每个子空间只有一个数据点为止。直观的说那些密度很高的簇需要被切割很多次才会停止,但是那些密度较低的点很容易较早地停在一个子空间里

实现步骤

切割是随机的因此需要集成方法得到一个收敛值,即反复从头开始切然后平均每次的结果。

  1. 从训练数据集中选择样本点作为subsample,放入树的根节点。
  2. 随机指定一个维度,随机产生一个切割点p,位于当前数据的最大最小值之间。
  3. 以切割点生成超平面,然后将当前的节点数据空间划分为2个子空间,把小于p的放入节点的左孩子,大于等于p的放在右孩子
  4. 在孩子节点中不断递归步骤2和3,直到无法切割,或者达到限定高度。

获得t个iTree后,训练结束然后可以用生成的iForest来评估测试数据,对于每一个训练数据x遍历每一棵iTree,计算其落在第几层,得到x在每个树高度平均值。获得测试数据的高度平均值后可以设置一个阈值,低于阈值的测试数据为异常。异常在书中往往有较短的平均高度。论文对高度进行归一化结果是一个0到1的数值,越短高度越接近1(异常可能性越高)

可以看出d最有可能是异常

默认参数

  • subsample size:256
  • Tree height:8
  • Number of trees:100