一种基于自然最近邻的离群检测算法

计算机科学 ›› 2014, Vol. 41 ›› Issue (3): 276-278.

一种基于自然最近邻的离群检测算法

朱庆生,唐汇,冯骥

重庆大学计算机学院软件理论与技术重庆市重点实验室重庆400044;重庆大学计算机学院软件理论与技术重庆市重点实验室重庆400044;重庆大学计算机学院软件理论与技术重庆市重点实验室重庆400044

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金(61272194,61073058)资助

Outlier Detection Algorithm Based on Natural Nearest Neighbor

ZHU Qing-sheng,TANG Hui and FENG Ji

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 任何涉及k近邻求解问题的算法被应用于处理不同特征的数据集时,参数k值的选择都会明显影响算法的性能和结果。因而,如何选择k近邻算法中敏感参数k值一直是一个研究难点。提出了一种新的近邻关系——自然最近邻,它不需要设置参数k,每个节点的邻居是由算法自适应计算而形成的。针对离群点检测的特殊性,通过确定自然最近邻居搜索算法的终止条件,提出一种基于自然最近邻的新的离群检测算法ODb3N。实验表明,该算法不仅避免了k近邻中参数的选择问题,而且能够更有效地发现离群簇。

关键词: k近邻,自然最近邻,离群检测,离群簇中图法分类号TP301/TP391文献标识码A

Abstract: When the k-nearest neighbor method is used,it is difficult to choose an appropriate parameter k of the algorithm which affects obviously its efficiency and performance.Natural nearest neighbor proposed by us is a novel concept on nearest neighbor,in which each point’s neighbors are formed by an adaptive algorithm without parameter k.In this paper,we proposed an outlier detection algorithm based on natural nearest neighbor(ODb3N) by means of modifying iteration stop condition．The experiments show that our method not only has the advantage of non-parameter,but also has the ability to discover both the outlier and the cluster of outliers.

Key words: k-nearest neighbor,Natural nearest neighbor,Outlier detection,Cluster of outliers

朱庆生,唐汇,冯骥. 一种基于自然最近邻的离群检测算法[J]. 计算机科学, 2014, 41(3): 276-278. https://doi.org/

ZHU Qing-sheng,TANG Hui and FENG Ji. Outlier Detection Algorithm Based on Natural Nearest Neighbor[J]. Computer Science, 2014, 41(3): 276-278. https://doi.org/

参考文献

[1] Gogoi P,Borah B,Bhattacharyya D K．Outlier identificationusing symmetric neighborhoods[J]．Procedia Technology,2012,6:239-246
[2] Breunig M M,Kriegel H P,et al．LOF:identifying density-based local outliers[J]．Proc．of 2000ACM SIGMOD international conference on Management of data．ACM Sigmod Record,2000,29(2):93-104 (下转第305页)(上接第278页)
[3] Hautamaki V,Karkkainen I．Outlier detection using k-nearestneighbor graph[C]∥Proc．17th IEEE Int．Conf．on Pattern Recognition．2004,3:430-433
[4] Angiulli,F,Palopoli L．Detecting outlying properties of exceptional objects[J]．ACM Transaction on Database Systems,2009,34(1):62-74
[5] Richard J,Chris C．Fuzzy-rough nearest neighbor classificationand prediction[J]．Theoretical Computer Science,2011,412(42):5871-5884
[6] Pandya D H,Upadhyay S H,Harsha S P．Fault diagnosis of rol-ling element bearing with intrinsic mode function of acoustic emission data using APF-kNN[J]．Expert Systems with Applications,2013,40(10):4137-4145
[7] Xu Yong,Zhu Qi,et al．Coarse to fine K nearest neighbor classifier [J]．Pattern Recognition Letters,2013,34(9):980-986
[8] 符永铨,王意洁．DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究[J]．中国科学(信息科学),2012,42(5):561-577

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed