![](https://csdnimg.cn/release/download_crawler_static/18270284/bg1.jpg)
收稿日期:20181220;修回日期:20190311 基金项目:国家自然科学基金资助项目(61862060,61462079,61562086,61562078)
作者简介:杜旭升(1995),男,甘肃宁县人,硕士研究生,主要研究方向为机器学习;于炯(1964),男(通信作者),北京人,教授,博导,博士,主
要研究方向为并行计算、机器学习、大数据(yujiong@xju.edu.cn);陈嘉颖(1988),女,新疆沙湾人,博士,主要研究方向为推荐系统、机器学习;王
跃飞(1991),男,新疆乌鲁木齐人,博士,主要研究方向为机器学习;蒲勇霖(1991),男,山东淄博人,博士,主要研究方向为内存计算、流式计算、
绿色计算等;叶乐乐(1993),男,湖北随州人,硕士研究生,主要研究方向为机器学习、计算机视觉.
一种基于邻域系统密度差异度量的离群点检测算法
杜旭升
1a
,于 炯
1a,1b
,陈嘉颖
1b
,王跃飞
1b
,蒲勇霖
1b
,叶乐乐
2
(1.新疆大学 a.软件学院;b.信息科学与工程学院,乌鲁木齐 830008;2.西安交通大学 软件学院,西安 710049)
摘 要:针对离群点检测算法 LOF在高维离散分布数据集中检测精度较低及参数敏感性较高的问题,提出了
基于邻域系统密度差异度量的离群点检测 NSD(neighborhoodsystemdensitydifference)算法。相较于传统基于密
度的离群点检测方法,
NSD算法引入了截取距离的概念。首先计算数据集中对象在截取距离内的邻居点个数;
其次计算对象的邻域系统密度;然后将对象的密度与它邻居的密度进行比较,判定目标对象与其邻居趋向于同
一簇的程度;最后输出最可能是离群点的对象。将
NSD算法与 LOF、LDOF、CBOF算法在真实数据集与合成数
据集中对比实验发现,NSD算法具有较高的检测准确率和执行效率以及较低的参数敏感性,证明了 NSD算法是
有效可行的。
关键词:数据挖掘;离群点检测;基于密度;LOF;LDOF;CBOF
中图分类号:TP301.6 文献标志码:A 文章编号:10013695(2020)07010196905
doi:10.19734/j.issn.10013695.2018.12.0932
Outlierdetectionalgorithmbasedonneighborhood
systemdensitydifferencemeasurement
DuXusheng
1a
,YuJiong
1a,1b
,ChenJiaying
1b
,WangYuefei
1b
,PuYonglin
1b
,YeLele
2
(1.a.SchoolofSoftware,b.SchoolofInformationScience&Engineering,XinjiangUniversity,Urumqi830008,China;2.SchoolofSoftware,
Xi’anJiaotongUniversity,Xi’an710049,China)
Abstract:LOFisafamousalgorithmforoutlierdetection,andithaslowerdetectionaccuracyandhigherparametersensitivity
onhighdimensionaldiscretedistributiondatasets.Aimingattheseproblems,thispaperproposedaneighborhoodsystemden
sitydifference(NSD)algorithmbasedondensitydifferencemeasurementofneighborhoodsystems.Comparedwiththetradi
tionaldensitybasedmethods,NSDalgorithmproposedandintroducedtheconceptofinterceptdistance.Firstly,itcalculated
thenumberofneighborsofanobjectwithintheinterceptdistanceondataset.Then,itcomputedthedensityofneighborhood
system.Afterthat
,itestimatedthedegreeoftendingtothesameclusterbycomparingthedensitybetweentheobjectandits
neighbors.Finally,itoutputtheobjectswhichclosedtooutlierwithmaximumlikelihood.ExperimentswithNSD,LOF,LD
OF,CBOFalgorithmscarriedoutontherealworlddatasetandsyntheticdataset,showthattheNSDalgorithmperformswith
higherdetectionaccuracyandexecutionefficiency
,whilewithlowerparametersensitivity.
Keywords:datamining;outlierdetection;densitybased;LOF(localoutlierfactor);LDOF(localdistancebasedoutlier
factor);CBOF(cohesivenessbasedoutlierfactor)
0 引言
离群点检测是数据挖掘与知识发现研究中的重点领域之
一。现如今,离群点检测已经在诸如网络入侵检测、医疗辅助
诊断、防控金融风险、变质农畜产品检测、气象预测等领域取得
了广泛应用
[1~3]
。在早期的研究中,离群点被定义为:在一个
给定的数据集中,如果一个数据对象大幅度偏离其他大多数对
象,使人不得不怀疑这个对象与其他大多数数据对象的产生机
制不同,则它就是一个离群点
[4]
。引起数据对象离群的原因
主要有三种:数据对象自身的异常性;数据对象的固有分布特
征;收集数据时所造成的误差
[5]
。由前两种原因产生的离群
点最有可能包含有益的信息,对其进行深层次的挖掘可以了解
到许多潜在的有益知识;而由第三种原因产生的离群点并不存
在有益的信息,相反会降低对应数据集的分析质量。
前期针对离群点的研究认为离群点并不存在分析的价值,
其主要研究目标是消除数据集当中的离群点。但一个人的噪
声可能是另一个人的信号
[6]
,不加辨别地剔除数据集中的离
群点可能会失去未知的重要信息。现有的离群点检测算法将
离群点视为一种有益的信号并进行深入的挖掘,以更加详细地
了解它们潜藏的有意义的信息。贯穿于离群点研究过程中的
三个问题是:
a)如何恰当地定义数据集中的离群点,即数据对
象所表现出的哪种特征可判定其离群;b)如何高效且精准地
检测出数据集中的离群点;c)如何恰当地描述检测出的离群
点所包含的知识
[7]
。
针对如何高效且精准地检测数据集中的离群点,现有研究
方向大致可分为基于分布、基于深度、基于聚类、基于距离和基
于密度五类
[8]
,其中以基于距离与基于密度的研究方向最具
代表性。基于密度的离群点检测算法
LOF对数据集中每一个
数据对象都需要复杂的密度与离群度计算过程,算法检测的准
确率高度依赖恰当的参数选择,且在高维离散分布的数据集中
检测精度不高。若 LOF算法参数中的近邻参数 k取值过小,
数据集中的离群点又恰好聚集在一起形成较小的簇时,算法会
第 37卷第 7期
2020年 7月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.37No.7
Jul.2020