基于k近邻隔离森林的异常检测_丁鹏霖.pdf

基于k近邻隔离森林的异常检测丁鹏霖(福建师范大学计算机与网络空间安全学院,福州350117)通信作者:丁鹏霖,E-mail:摘要:异常检测是机器学习与数据挖掘的热点研究领域之一,主要应用于故障诊断、入侵检测、欺诈检测等领域.当前已有很多有效的相关研究工作,特别是基于隔离森林的异常检测方法,但在处理高维数据时仍然存在许多困难.提出了一种新的 k 近邻隔离森林的异常检算法:k-nearestneighborbasedisolationforest(KNIF).该方法采用超球体作为隔离工具,利用第 k 近邻的方法来构建隔离森林,并构建基于距离的异常值计算方法.通过充分实验表明KNIF 方法能有效地进行复杂分布环境下的异常检测,并能适应不同分布形式的应用场景.关键词:异常检测;隔离森林;k 近邻;超球体引用格式:丁鹏霖.基于 k 近邻隔离森林的异常检测.计算机系统应用,2023,32(2):199206.http:/www.c-s- Detection Based on k-nearest Neighbor Isolation ForestDINGPeng-Lin(CollegeofComputerandCyberSecurity,FujianNormalUniversity,Fuzhou350117,China)Abstract:Anomalydetectionisoneoftheresearchfocusesinmachinelearninganddatamining,whichismainlyusedinfaultdiagnosis,intrusiondetection,andfrauddetection.Therehavebeenmanyeffectiverelatedstudies,especiallythoseoftheanomalydetectionmethodbasedonisolationforest,buttherearestillmanydifficultiesintheprocessingofhigh-dimensionaldata.Anewanomalydetectionalgorithm,k-nearestneighborbasedisolationforest(KNIF),isproposed.Themethoduseshyperspheresasanisolationtool,utilizesthek-nearestneighbormethodtoconstructanisolationforest,andconstructsadistance-basedoutliercalculationmethod.SufficientexperimentsshowthattheKNIFmethodcaneffectivelydetectanomaliesincomplexdistributionenvironmentsandcanadapttoapplicationscenariosofdifferentdistributionforms.Key words:anomalydetection;isolationforest;k-nearestneighbor;hypersphere异常检测14就是检测数据中不符合行为的异常数据,异常数据也可以称之为离群点、污点、不一致点,数据异常可以转化为各种应用领域中的重要可操作信息.在大数据信息时代,异常检测在许多领域都发挥着不可忽视的作用,包括信用卡欺诈检测,保险或医疗保健,交通管理,网络安全入侵检测,安全攸关系统中的故障检测以及对敌方活动的军事监视等58.异常检测技术的研究是当前机器学习与数据挖掘的热点研究领域之一,具有非常重要的应用意义.当前学术界也产业界已有很多异常检测方法的研究.Breunig 等人提出了基于密度的 LOF 算法9,其基本原理是对数据点进行计算,找出其 k 个近邻,然后计算LOF得分,得分越高则异常的可能性越大.LOF 是一个比值,其分子是 k 个近邻的平均局部可达密度,分母则是该数据点局部可达密度.Chen 等人提出了基于聚类的 DBSCAN 算法10,该算法通过将紧密相连的样计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(2):199206doi:10.15888/ki.csa.008988http:/www.c-s-中国科学院软件研究所版权所有.Tel:+86-10-62661041基金项目:国家自然科学基金(61772004);福建省科技计划重大项目(2020H6011);福建省自然科学基金(2020J01161)收稿时间:2022-05-31;修改时间:2022-08-09;采用时间:2022-09-27;csa 在线出版时间:2022-12-09CNKI 网络首发时间:2022-12-13SoftwareTechniqueAlgorithm软件技术算法199本划为各个不同的类别,最终得出聚类类别结果.K-means 算法11假设距离最近的聚类结果较远的点为异常点.该算法首先对数据进行聚类,然后通过计算样本与所属聚类的两个距离,一个是样本与所属聚类中心的距离,一个是样本与所属聚类的类内平均距离,通过两个距离的比值衡量异常程度.在不同的异常检测算法中,isolationforest1214是具有独特能力的方法,该方法计算效率高,易用于并行计算范式15,且已被证明在检测异常方面非常有效16.该算法的主要优点是它不依靠构建模型来查找不符合此模型的样本;而是利用了异常数据“少而不同”的特点,通过理解异常来发现异常,观察它们的属性并将它们与其余的正常数据样本隔离1719.在隔离森林中,数据被子采样,并以树状结构处理随机选择的值.在数据被树状结构处理后,那些走得更深的样本进入树枝,也就是叶子节点的异常可能性较小,而较短的分支表示该数据很快就被隔离至叶子节点,有更大的概率是异常数据.因此,叶节点的深度即为度量每个给定点的异常或“异常分数”的关键因素.然而,隔离森林算法仍然存在一些问题.事实证明,虽然该算法在计算上行之有效,但由于它固有的分支方式,传统隔离森林算法存在很多局限性.为了解决这些局限性,诞生了一系列“改进版”隔离森林,例如extendedisolationforest20,inne21等.显然,这些改进版的隔离森林算法解决了传统隔离森林算法的一些问题,但是,它们依然存在一些需要改进的地方.大体来说,这些算法仍然存在以下几点问题.(1)采用超平面来对空间进行随机切割和隔离,不能充分利用数据中每个维度的信息,可能导致大量维度信息没有被利用,算法的可靠性较低.(2)当前的方法仅适应于一些分布比较常见、比较简单的数据,由于其采用随机超平面进行空间的划分,在处理不均衡数据集时存在一定程度的分类准确率低、误警率高的问题,难以拥有稳定且良好的表现.(3)仅对全局的稀疏点、异常点敏感,不善于处理局部的、内部的异常点.针对以上问题,本文提出了基于 k 近邻隔离森林(k-nearestneighborbasedisolationforest,KNIF)的异常检测方法.KNIF 方法具有不同的隔离机制,先对数据空间进行多次采样,构建一个个检测集合,并由多个集合共同构成一片“森林”.与隔离森林不一样,本算法采用超球体作为隔离工具,充分利用每个维度的信息.在隔离区域中,每个区域都是一个超球体,其中心由来自子样本,其边界由到该子样本的第 n 近邻的距离定义,以便将每个实例与其余的数据空间隔离开来.简而言之,我们使用基于第 n 近邻的方法来执行隔离而不是原始的轴平行细分方法.也采用兼具创新性的异常得分计算方法,并确定每个隔离区域的隔离分数.此方法在继承之前隔离森林系算法的优点的同时,也由其创新性解决了之前算法存在的痛点,是一种更高效、更稳定、更全面的算法.本文的主要贡献及创新点如下.(1)使用所有可用属性将数据空间划分为隔离区域,充分利用数据集中所有维度的信息,而不是仅为其分区过程使用属性的子集.因此,新方法不存在子空间方法的缺点.(2)将隔离森林的集成学习方法与最近邻的方法有机结合起来,并提出新颖的、有效的异常点界定方式.(3)相比于随机超平面的隔离划分,超球体能更好地检测局部的、内部的异常,在密集区域创建更小的超球体,在稀疏区域创建更大的超球体,每个球体的半径都是判断异常的关键依据,能更好地适应和处理分布复杂且多样的数据,提升分类准确率.本文进行了充分的实验,先采用人工合成数据生成的热力图来直观地展示本算法的优势.且在 4 个高维真实数据集进行评估实验,将实验结果与已有的数个异常检测算法作比较,并使用 AUC 指标客观地评估各算法的表现,以充分说明此算法的优越性.本文第1 节介绍隔离森林及其背景基础;第 2 节给出本文的问题定义;第 3 节提出了问题的解决方案;第 4 节实验与结果分析;最后是结论与展望.1隔离森林及相关基础隔离森林,又名孤立森林,不同于传统异常检测算法的思想,其用隔离的方法将异常点与正常点区分开来,通过利用数量稀少和不同的异常特性并测量个体的被隔离敏感度,通过将特征空间划分区域来执行隔离.这种方法充分利用了异常点的特性,背后的思想是异常更容易被隔离.隔离森林是由 N 个树构成的.每棵树的学习过程非常随机:它会随机抽取特征,随机选取随机选择的真实值样本中所选属性的最小值和最大值之间的值来建立决策树,从而将每一个样本分到一个独立的子节点上(取值相同的样本视为同一个样本).从超空间的角计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第2期200软件技术算法SoftwareTechniqueAlgorithm度看,这样就是不断地用随机选取的超平面切分样本点,直到所有的样本点都被这些超平面“隔离”起来,即与其他样本点分隔开.隔离森林使用 x 落入的叶节点的路径长度来计算其隔离分数,使用少量的平行轴来隔离具有很少数据点的区域分区.实例 x 的路径长度 h(x)基于 x 落入的叶节点定义.xix0隔离森林可以使用较小的样本来建立隔离模型.与其他方法相比,时间复杂度和空间复杂度都较低.第一个隔离方法为iForest,构建了一个称为隔离的树集合树,其中每个隔离树都是从随机选择的大小为 的子样本构建的.隔离树是一棵二叉树,其中在每个节点上,对随机选择的一个节点执行随机分裂来自特征空间的属性.分割点是随机选择的真实值样本中所选属性的最小值和最大值.iForest 使用 x 落入的叶节点的路径长度作为其隔离分数,其中直觉上,可以使用少量的平行轴来隔离具有很少数据点的区上图就是对子样本进行切割训练的过程,如图 1 所示,图 1(a)的 处于密度较高的区域,因此切割了十几次才被分到了单独的子空间,而图 1(b)的落在边缘分布较稀疏的区域,只经历了 4 次切分就被“隔离”了.x0(b)隔离 x0 xi(a)隔离 xi图 1隔离森林切割过程由于切割过程是完全随机的,所以需要用整合的方法来使结果收敛,即反复从头开始切,整合全部隔离树的结果,然后计算每次切分结果的平均值.获得 t 棵隔离树后,单棵树的训练就结束了.接下来就可以用生成的隔离树来评估测试数据了,即计算异常分数 s.对于每个样本 x,需要对其综合计算每棵树的结果,通过式(1)计算异常得分:s(x,)=2E(h(x)c()(1)c()其中,h(x)为 x 在每棵树的高度,为给定样本数 时路径长度的平均值,用来对样本 x 的路径长度 h(x)进行标准化处理.如果异常得分接近 1,那么一定是异常点.如果异常得分远小于 0.5,那么一定不是异常点.如果异常得分所有点的得分都在 0.5 左右,那么样本中很可能不存在异常点.2问题定义致力于提升隔离森林算法的鲁棒性和可靠性,本文提出 KNIF 算法.KNIF 基于 k 近邻构建超球体作为隔离工具.定义1及定义2给出所使用的距离及第k近邻定义.x1