IsolationForest原理总结

Isolation Forest&＃xff08;以下简称iForest&＃xff09;算法是由南京大学的周志华和澳大利亚莫纳什大学的Fei Tony Liu, Kai Ming Ting等人共同提出&＃xff0c;用于挖掘异常数据【Isolation Forest&＃xff0c;Isolation-based Anomaly Detection】。该算法基于异常数据的两个特征&＃xff1a;&＃xff08;1&＃xff09;异常数据只占少量&＃xff1b;&＃xff08;2&＃xff09;异常数据特征值和正常数据差别很大。iForest算法由于简单高效的特点&＃xff0c;常用于网络安全中的攻击检测和流量异常等分析【A survey of network anomaly detection techniques】。

iForest算法得益于随机森林的思想&＃xff0c;与随机森林由大量决策树组成一样&＃xff0c;iForest森林也由大量的二叉树组成。iForest中的树叫isolation tree&＃xff0c;简称iTree。iTree树和决策树不太一样&＃xff0c;其构建过程也比决策树简单&＃xff0c;是一个完全随机的过程。

假设数据集有N条数据&＃xff0c;构建一颗iTree时&＃xff0c;从N条数据中均匀抽样(一般是无放回抽样)出ψ个样本出来&＃xff0c;作为这颗树的训练样本。在样本中&＃xff0c;随机选一个特征&＃xff0c;并在这个特征的所有值范围内(最小值与最大值之间)随机选一个值&＃xff0c;对样本进行二叉划分&＃xff0c;将样本中小于该值的划分到节点的左边&＃xff0c;大于等于该值的划分到节点的右边。由此得到一个分裂条件和左、右两边的数据集&＃xff0c;然后分别在左右两边的数据集上重复上面的过程&＃xff0c;直到数据集只有一条记录或者达到了树的限定高度。

图1 iForest构建iTree示例&＃xff0c;异常数据点&＃xff08;17,17&＃xff09;通常离根节点很近

由于异常数据较小且特征值和正常数据差别很大。因此&＃xff0c;构建iTree的时候&＃xff0c;异常数据离根更近&＃xff0c;而正常数据离根更远。一棵iTree的结果往往不可信&＃xff0c;iForest算法通过多次抽取样本&＃xff0c;构建多棵二叉树。最后整合所有树的结果&＃xff0c;并取平均深度作为最终的输出深度&＃xff0c;由此计算数据点的异常分值。