异常检测算法之IForest

比眉伴天荒 2022-09-09 15:53 214阅读 0赞

# 前言 #

IForest即孤立森林，可以用于做异常检测。一句话总结IForest做异常检测的原理：异常点密度小，基于树模型容易被一下切割出来，正常值密度大，需要切割多次才能得到目标值。

# 原理 #

iForest算法得益于随机森林的思想，与随机森林由大量决策树组成一样，iForest森林也由大量的二叉树组成。iForest中的树叫isolation tree，简称iTree。iTree树和决策树不太一样，其构建过程也比决策树简单，是一个完全随机的过程。  
每个iTree的实现步骤  
1、 假设数据集有N条数据，构建一颗iTree时，从N条数据中均匀抽样(一般是无放回抽样)出ψ个样本出来，作为这颗树的训练样本。  
2、 在样本中，随机选一个特征，并在这个特征的所有值范围内(最小值与最大值之间)随机选一个值，对样本进行二叉划分，将样本中小于该值的划分到节点的左边，大于等于该值的划分到节点的右边。由此得到一个分裂条件和左、右两边的数据集。  
3、 然后分别在左右两边的数据集上重复上面的过程，直到数据集只有一条记录或者达到了树的限定高度。

获得t个iTree之后，iForest 训练就结束，然后我们可以用生成的iForest来评估测试数据了。对于一个训练数据x，我们令其遍历每一棵iTree，然后计算x最终落在每个树第几层（x在树的高度）。然后我们可以得出x在每棵树的高度平均值，即 the average path length overt iTrees。  
获得每个测试数据的average path length后，我们可以设置一个阈值（边界值），average path length 低于此阈值的测试数据即为异常。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbm9ib2R5fg_size_20_color_FFFFFF_t_70_g_se_x_16]  
图1 iForest构建iTree示例，异常数据点（17,17）通常离根节点很近

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

# 优缺点 #

## 优点： ##

iForest具有线性时间复杂度，IForest是集成算法，因此可以用在海量数据集上，通常树的数量越多，算法越稳定。

## 缺点： ##

1、**不适用与特别高维的数据**。由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低。高维空间还可能存在大量噪音维度或无关维度（irrelevant attributes），影响树的构建。对这类数据，建议使用子空间异常检测（Subspace Anomaly Detection）技术  
2、iForest仅对Global Anomaly 敏感，即全局稀疏点敏感，不擅长处理局部的相对稀疏点 （Local Anomaly）。目前已有改进方法发表于PAKDD，详见“Improving iForest with Relative Mass”。

# 适用场景 #

适用于样本维度不是特别高的场景

# 参数详解 #

classpyod.models.iforest.IForest(n_estimators=100, max_samples='auto', contamination=0.1, max_features=1.0, bootstrap=False, n_jobs=1, random_state=None, verbose=0)
    
    n_estimators：估算器数量。默认100棵树
    max_samples：训练每个估算器（tree）需要抽取的样本数。默认选256个样本建树
    int：抽取max_samples个
    float：抽取max_samples*X.shape[0]（即样本行数）个
    auto：抽取min(256, n_samples)个
    
    contamination：污染度即假设每个数据集包含的噪声含量
    ;
    max_features：训练每个估算器需要抽取的特征数，高维数据时不必分割所有特征
    int：抽取max_features个
    float：抽取max_features*X.shape[1]即（样本列数）个<占比>
    
    bootstrap：
    true：单一树需拟合替换的随机样本
    false：进行无需更换的取样
    
    n_jobs：并行作业数。-1时，n_jobs为CPU核心数
    
    random_state：随机数种子/生成器
    
    verbose：控制建树过程

# 总结 #

经实践，发现IForest针对数据量大，特征少的业务场景，进行异常识别的效果非常不错。但是需要注意在调整contamination参数的时候，若数据中识别的噪声数据量不满足该参数，则不会做任何处理。即若设置噪声占比为10%，但是模型识别的噪声数量小于10%（比如只识别了7%的噪声），这个时候模型只会返回7%的噪声，并不会按照10%噪声占比量进行返回。一定要注意这种情况，这种情况可能的原因之一：当噪声数据聚成了一个簇时，若实际的噪声占比为15%，但是我初始设置的是contamination为10%。这时候由于有约5%的噪声在模型中对应的深度相同，即异常分数相同，则造成模型最终认为这些数据在当前的参数设定下不能认定为噪声。  
PS：该模型最终是将每条数据在IForest中所处的深度转化为一个异常值分数，按照异常值分数进行排序，通过contamination的设定值截取前top的数据作为噪声输出来完成整个噪声识别流程。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbm9ib2R5fg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/b7b3ae89663f4bca8a82c0d219376545.png