文献类型：期刊文章

作　　者：朱利[1] 邱媛媛[1] 于帅[1] 原盛[1]

ZHU Li;QIU Yuan-Yuan;YU Shuai;YUAN Sheng(School of Software Engineering,Xi’an Jiaotong University,Xi’an710049)

机构地区：[1]西安交通大学软件学院,西安710049

出　　处：《计算机学报》

基　　金：国家自然基金项目(61473220);陕西省自然基金项目(S2015YFJM2129)资助~~

年　　份：2017

卷　　号：40

期　　号：12

起止页码：2856-2870

语　　种：中文

收录情况：BDHX、BDHX2014、CSCD、CSCD2017_2018、EI、IC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：离群检测也称异常点检测,是数据挖掘领域很有意义的热点问题之一,在很多方面都有广泛应用,如入侵行为、欺诈行为、医学上疾病前期的征兆等.基于k-近邻的算法能够很好的运用到大数据集上,因此在基于距离和基于密度的离群检测技术方面得到广泛应用.然而k-近邻算法的时间复杂度为O(N^2),随着数据集规模的增加,时间开销大大增加.基于最小生成树的聚类算法在使用Prim或者Kruskal算法构建最小生成树时空间复杂度和时间复杂度均为O(N^2),聚类结果依赖于用户参数的选择,而且容易漏检稠密簇中的局部离群点.针对以上问题,融合基于密度和基于聚类方法的优势,提出一种新的离群检测方法.该方法具有以下优点:(1)计算k-近邻的时间复杂度为O(kN)(k<<N);(2)构建最小生成树的时间复杂度为O(NlogN);(3)自适应识别聚类数目;(4)能够检测出多种类型的离群数据.最后通过大量实验验证了文中所提的KDNS算法,FkNN算法和ADC算法的有效性.实验结果表明,相对于现有算法,文中算法可以大幅度降低时间复杂度并显著提高离群检测率.

关 键 词：良分割对  最小生成树 K-近邻 自适应聚类 离群检测 数据挖掘

分 类 号：TP18]