IsolationForest-01原理

IsolationForest-01原理

Intro

2008年刘飞、周志华等提出Isolation Forest算法，iforest不借助类似距离、密度等指标去描述样本与其他样本的差异，而是直接去刻画所谓的疏离程度(isolation)。该算法简单、高效，在工业界应用较多(好像没有看到很多case)~   Isolation Forest算法的逻辑很直观，算法采用二叉树对数据进行split，样本选取、特征选取、split value选取都采用随机化的方式。如果某个样本是异常值，可能需要很少次数就可以切分出来。

算法逻辑

前提假设

前提假设(fewAndDifferent)

异常样本较少few和正常样本差异较大different

算法思想

异常样本更容易快速落入叶子结点

训练

训练逻辑:

从原始数据中，不放回的抽取部分样本，构建一颗二叉树(iTree即Isolation Tree)利用集成学习的思想，多次抽取样本，完成多棵iTree的构建。

iTree停止条件:

树达到指定的高度/深度数据不可再分，即：只包含一条数据，或者全部数据相同

具体的算法如下:

几个小问题:

树的最大深度=ceiling(log(subsimpleSize))，paper里说自动指定，sklearn也是在代码中写死:​​​max_depth = int(np.ceil(np.log2(max(max_samples, 2))))​​ 这个值接近树的平均深度，我们只关注那些小于平均深度的异常值，所以无需让树完全生长Sub-sampling size，建议256即可。大于256，性能上不会有大的提升Number of tree,建议100

预测

PathLength计算公式如下：

其中：

其他

Paper遗留问题

实验评估逻辑峰度筛选特征逻辑判断异常值的阈值怎么定特征的随机化，是在每一次split时做，还是subsample时候做？

Tricks

subsample样本过多，引入较多的正样本，反而会影响模型的效果特征筛选逻辑，根据峰度筛选

Ref

Paper​​​Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation forest."Data Mining, 2008. ICDM’08. Eighth IEEE International Conference on. IEEE, 2008. ​​​​Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation-based anomaly detection."ACM Transactions on Knowledge Discovery from Data (TKDD)6.1 (2012): 3. ​​Source Code​​R源码​​​​Python源码​​Blog​​知乎-iForest （Isolation Forest）孤立森林 异常检测 入门篇​​​​知乎-机器学习-异常检测算法（一）：Isolation Forest​​

2020-01-06 于南京市江宁区九龙湖

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。