一种基于快速k-近邻的最小生成树离群检测方法

• 作者: 于帅 原盛 朱利 邱媛媛
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 良分割对 最小生成树 k-近邻 自适应聚类 离群检测 数据挖掘
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 软件技术
• 页码范围: 2856-2870
• 页数: 15页
• 分类号: TP18
• 字数: 12804字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2017.02856

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱利	西安交通大学软件学院	61	704	11.0	25.0
2	原盛	西安交通大学软件学院	5	68	4.0	5.0
3	于帅	西安交通大学软件学院	2	32	2.0	2.0
4	邱媛媛	西安交通大学软件学院	2	32	2.0	2.0