基于模拟退火的扩展孤立森林异常检测算法_王诗愉.pdf

计算机与现代化JISUANJI YU XIANDAIHUA2023年第1期总第329期0引言在数据挖掘中，异常检测是指对不符合预期模式的样本进行识别，从数据集中识别出与大多数样本差异较大的对象。异常点也被称为离群值、噪声和偏差等1，通常被认为是与其他数据点明显不同或不符合整体预期正常模式的数据点2。异常检测是数据挖掘领域中一个重要的方面，被广泛应用于各个领域。例如，在医学领域中，异常数据可能意味着禽流感等传染类疾病的预警，而在天文领域中，异常数据则可能标志着新星的发现3-6。因此，异常数据可能具备和正常数据相等的科学价值。近年来，国内外学者对异常检测领域进行了深入的探讨，提出了许多实用性很高的异常检测算法，为异常检测的进一步研究奠定了基础。Domingues等7对常见的异常检测算法进行了分类总结，并根据异常检测所使用技术的不同，分为基于连接函数的异常检测方法8（Copula-Based Outlier Detection，COPOD）、基于距离的异常检测方法9和基于密度评估的异常检测方法等。其中基于密度评估的局部离群因子检测方法10（Local Outlier Factor，LOF）解决了数据倾斜分布下的异常检测问题。LOF通过计算局部可达密度来得到每一个样本点的局部离群因子，最后根据阈值判断该样本点是否异常。但是，基于密度评估的文章编号：1006-2475（2023）01-0088-07基于模拟退火的扩展孤立森林异常检测算法王诗愉1，肖利东1，严心淳2，应文豪1（1.常熟理工学院计算机科学与工程学院，江苏 常熟 215500；2.常熟市医学检验所，江苏 常熟 215500）摘要：扩展孤立森林（Extended Isolation Forest，EIF）有效解决了孤立森林（Isolation Forest，iForest）对局部异常点不敏感的问题，但EIF将轴平行的孤立条件更替为使用随机斜率的超平面，导致算法模型损失了一部分泛化能力，并由于大量的向量点乘运算增加了时间开销。针对上述情况，提出一种基于模拟退火的扩展孤立森林算法（Extended Isolation Forestbased on Simulated Annealing，SA-EIF）。该算法根据每棵孤立树（Isolation Tree，iTree）对于数据集的预测结果计算每棵iTree的精度值和差异值，并基于此构建适应度函数，最终利用模拟退火算法筛选数棵检测性能较优的iTree构建集成学习模型。在ODDS 异常检测数据集中进行K折交叉验证的实验结果表明：SA-EIF算法对局部异常点敏感，较现有的EIF算法减少约20%40%的时间开销，提高约5%10%的检测精度。关键词：扩展孤立森林；孤立森林；模拟退火；异常检测中图分类号：TP391.4文献标志码：ADOI：10.3969/j.issn.1006-2475.2023.01.015Extended Isolated Forest Anomaly Detection Algorithm Based on Simulated AnnealingWANG Shi-yu1，XIAO Li-dong1，YAN Xin-chun2，YING Wen-hao1（1.School of Computer Science and Engineering，Changshu Institute of Technology，Changshu 215500，China；2.Changshu Medicine Examination Institute，Changshu 215500，China）Abstract:Extended Isolation Forest（EIF）effectively solves the problem that Isolation Forest（iForest）is not sensitive to localabnormal points，but EIF replaces the isolated condition of axis-parallel with a hyperplane with random slope，which causes thealgorithm model to lose part of the generalization ability，and increases time cost due to a large number of vector dot multiplication operations.In response to the above situation，an Extended Isolation Forest based on Simulated Annealing（SA-EIF）is proposed.The algorithm calculates the accuracy value and the difference value of each iTree（Isolation Tree）according to the prediction result of each iTree for the data set，then builds fitness function based on this.Finally，the iTree with better detection performance is selected by the simulated annealing algorithm to construct integrative learning model.The experimental results of K-fold cross-validation in the ODDS anomaly detection dataset indicate that the SA-EIF algorithm is sensitive to local anomalies，reducing the time cost by 20%40%compared with EIF，and the recognition accuracy is about 5%10%higher than EIF.Key words:extended isolation forest；isolation forest；simulated annealing；anomaly detection收稿日期：2022-03-18；修回日期：2022-03-22基金项目：国家重点研发计划项目（2018YFB1004901）；教育部人文社科基金资助项目（18YJCZH229）；国家自然科学基金资助项目（61972059）；江苏省教育科学“十三五”规划课题（X-a/2018/08）；江苏省大学生创新创业训练计划项目（202110333006）作者简介：王诗愉（2000），男，四川江油人，本科生，研究方向：机器学习与异常检测，E-mail：；肖利东（2000），男，福建晋江人，本科生，研究方向：机器学习与数据挖掘，E-mail：；严心淳（1980），男，江苏常熟人，高级工程师，硕士，研究方向：医学数据分析挖掘，E-mail:；通信作者：应文豪（1979），男，江苏常熟人，副教授，硕士生导师，博士，研究方向：数据挖掘与智能计算，E-mail:。2023年第1期局部异常检测方法时间复杂度均为O（n2）11，这种方法在大规模数据集上的计算成本很高。同时，因为数据相似度的计算离不开距离计算，所以可能会面临距离计算上的“维数灾难”问题12。随着大数据时代的到来，数据集的数量和维度呈爆炸式增长，基于此，设计出在高维数据集上表现良好的异常检测算法具有重要意义。iForest13是一种基于相似度的算法，与集成学习算法随机森林14有许多内在的相似之处。iForest的主要优点在于直接孤立异常点达到异常检测的目的，从而在一定程度上缓解异常检测的掩盖和淹没效应15，而传统的异常检测算法通常需要针对正常数据构建模型。iForest 利用数据集中异常点“少而不同”的特点采用子采样的方法构建iTree，将数据遍历划分到iTree的节点中，数据在iTree中所处的深度反映了该数据的“异常”程度，因此数据点在iTree中的深度越浅，越有可能为异常点。iForest不需要计算距离或密度度量，也不需要构建完全的模型，且具备线性复杂度，因而能高效处理高维数据16-17。即使iForest适用于高维数据集的异常检测，但由于在构建iTree时，每次划分数据空间都是随机选取一个特征，构建完iTree后仍有大量维度信息没有被使用，并且每个数据点对于随机选取特征的异常程度也是不同的，最终导致算法的稳定性降低 18。基于上述问题，杨晓辉等 19 提出了基于多维度随机超平面的 iForest异常检测算法（Multi-dimensionalRandom Hyperplane iForest，MRH-iForest）。该算法结合滑动窗口的多粒度扫描机制，在每个维度子集上分别构建iForest，多个iForest构造层次化集成学习异常检测模型。该模型改善了iForest在高维数据集中异常检测精度下降和稳定性较低的缺陷，但是随着数据集维度的增加，MRH-iForest的时间开销增量要远大于iForest。同时，因为iForest使用的切割平面是轴平行的，而轴平行的切割方式可能会导致隔离超平面的交叉，进而产生异常分数分布不准确的区域。Hariri等20发现 iForest对于局部异常点不敏感，基于此提出了EIF，该算法可以随机生成各种角度的切割平面，有效解决了iForest对于局部异常点不敏感的问题。但由于 EIF 在构建扩展孤立树（Extended Isolation Tree，EIT）时进行了多次向量点乘运算，所以在高维数据集上其计算成本往往远大于 iForest。同时因为 EIF将轴平行的孤立条件更替为使用随机斜率21的超平面，导致算法模型损失了一部分泛化能力。基于上述问题，本文利用模拟退火能够有效避免算法陷入局部最优解并最终以一定概率趋于全局最优解的特性，提出一种基于模拟退火的扩展孤立森林算法SA-EIF。SA-EIF的核心思想是：1）在集成构建 EIF的过程中计算iTree之间的差异值。2棵iTree之间的差异值越大，则说明2棵iTree的关联性越小。2）基于 K 折交叉验证的方法计算 iTree 的精度值。因为检测精度较低的iTree在集成学习模型中具有相同的投票权重，因此低精度的iTree通常会降低集成学习模型的异常检测能力。3）基于每棵iTree的平均差异值和检测精度构建适应度函数，最终选择部分高平均差异值和检测能力较强的 iTree 构建集成学习模型22。这就使得 SA-EIF可以在保持原有检测精度的情况下，降低构造过程中所占用的内存，减少约20%40%的时间开销，增强了算法的泛化能力和稳定性。1相关工作1.1iForest算法iForest是一种集成学习算法，类似于随机森林由多棵决策树组成，iForest也由多棵iTree组成。iForest的异常检测分为2个部分，第一个部分是训练阶段，第二个部分是评估阶段。1.1.1训练阶段在iForest的训练阶段算法步骤中，假设数据集=x1，x2，xn，数据的维度为d，l为iTree的数目，随机子采样的大小为，将树的深度限制设为 l，一棵iTree的构造步骤如下：Step1从数据集中随机选取个数据，组成样本子空间，作为iTree的根节点。Step2从样本子空间中随机选取一个特征q作为起始节点，并在该特征的值区间内随机选取划分点p。Step3基于划分点生成的超平面，将当前样本子空间划分为2个部分。把样本子空间中小于划分点p的数据划分到当前节点的左子树，大于等于p的数据划分到当前节点的右子树。Step4在 iTree 的 所 有 左 右 子 树 中 重 复 执Step