FENG Ji,RAN Ruisheng,WEI Yan.A parameter-free outlier detection algorithm based on natural neighborhood graph[J].CAAI Transactions on Intelligent Systems,2019,14(05):998-1006.[doi:10.11992/tis.201809032]





A parameter-free outlier detection algorithm based on natural neighborhood graph
冯骥 冉瑞生 魏延
重庆师范大学 计算机与信息科学学院, 重庆 401331
FENG Ji RAN Ruisheng WEI Yan
College of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China
parameter-freeadaptive neighbornearest neighborweighted graphoutlier detectionoutlier factorglobal outlierlocal outlier
This study aims to deal with the practical shortages of nearest-neighbor-based data mining techniques, particularly outlier detection. In particular, when data sets have arbitrarily shaped clusters and varying density, determining the appropriate parameters without a priori knowledge becomes difficult. To address this issue, on the basis of the natural neighbor method, which can better reflect the relationship between elements in a data set than the k-nearest neighbor method, we present a graph called the weighted natural neighborhood graph for outlier detection. The weighted natural neighborhood graph does not need to set parameters artificially in the entire process and can identify global and local outliers in the data set with different distribution characteristics. The outlier detection results of artificial dataset and real data prove that the algorithm can obtain an effect similar to that of the optimal parameter in the algorithm with parameters. The algorithm detection result is far better than that of most parameter-sensitive algorithms and is much better than that of the parameter-insensitive algorithm, which has stronger universality and more practicality.


[1] BOLTON R J, HAND D J. Statistical fraud detection:a review[J]. Statistical science, 2002, 17(3):235-255.
[2] DENG Hongmei, XU R. Model selection for anomaly detection in wireless ad hoc networks[C]//Proceedings of 2007 IEEE Symposium on Computational Intelligence and Data Mining. Honolulu, USA, 2007:540-546.
[3] DURAN O, PETROU M. A Time-efficient method for anomaly detection in hyperspectral images[J]. IEEE Transactions on geoscience and remote sensing, 2007, 45(12):3894-3904.
[4] PODGORELEC V, HERICKO M, ROZMAN I. Improving mining of medical data by outliers prediction[C]//Proceedings of the 18th IEEE Symposium on Computer-Based Medical Systems. Dublin, Ireland, 2005:91-96.
[5] NASI J, SORSA A, LEIVISKA K. Sensor validation and outlier detection using fuzzy limits[C]//Proceedings of the 44th IEEE Conference on Decision and Control. Seville, Spain, 2005:7828-7833.
[6] KIM S, CHO N W, KANG B, et al. Fast outlier detection for very large log data[J]. Expert systems with applications, 2011, 38(8):9587-9596.
[7] CAMPELLO R J G B, MOULAVI D, ZIMEK A, et al. Hierarchical density estimates for data clustering, visualization, and outlier detection[J]. ACM transactions on knowledge discovery from data, 2015, 10(1):5.
[8] 苟和平, 景永霞, 冯百明, 等. 基于DBSCAN聚类的改进KNN文本分类算法[J]. 科学技术与工程, 2013, 13(1):219-222 GOU Heping, JING Yongxia, FENG Baiming, et al. An improved KNN text categorization algorithm based on DBSCAN[J]. Science technology and engineering, 2013, 13(1):219-222
[9] 周芳芳, 高飞, 刘勇刚, 等. 基于密度-距离图的交互式体数据分类方法[J]. 软件学报, 2016, 27(5):1061-1073 ZHOU Fangfang, GAO Fei, LIU Yonggang, et al. Interactive volume data classification based on density-distance graph[J]. Journal of software, 2016, 27(5):1061-1073
[10] 周国兵, 吴建鑫, 周嵩. 一种基于近邻表示的聚类方法[J]. 软件学报, 2015, 26(11):2847-2855 ZHOU Guobing, WU Jianxin, ZHOU Song. Clustering method based on nearest neighbors representation[J]. Journal of software, 2015, 26(11):2847-2855
[11] 王习特, 申德荣, 白梅, 等. BOD:一种高效的分布式离群点检测算法[J]. 计算机学报, 2016, 39(1):36-51 WANG Xite, SHEN Derong, BAI Mei, et al. BOD:an efficient algorithm for distributed outlier detection[J]. Chinese journal of computers, 2016, 39(1):36-51
[12] 陆海青, 葛洪伟. 自适应灰度加权的鲁棒模糊C均值图像分割[J]. 智能系统学报, 2018, 13(4):584-593 LU Haiqing, GE Hongwei. Adaptive gray-weighted robust fuzzy C-means algorithm for image segmentation[J]. CAAI transactions on intelligent systems, 2018, 13(4):584-593
[13] 赵冠哲, 齐建鹏, 于彦伟, 等. 移动社交网络异常签到在线检测算法[J]. 智能系统学报, 2017, 12(5):752-759 ZHAO Guanzhe, QI Jianpeng, YU Yanwei, et al. Online check-in outlier detection method in mobile social networks[J]. CAAI transactions on intelligent systems, 2017, 12(5):752-759
[14] 张美琴, 白亮, 王俊斌. 基于加权聚类集成的标签传播算法[J]. 智能系统学报, 2018, 13(6):994-998 ZHANG Meiqin, BAI Liang, WANG Junbin. Label propagation algorithm based on weighted clustering ensemble[J]. CAAI transactions on intelligent systems, 2018, 13(6):994-998
[15] HA J, SEOK S, LEE J S. Robust outlier detection using the instability factor[J]. Knowledge-based systems, 2014, 63(2):15-23.
[16] 冯骥, 张程, 朱庆生. 一种具有动态邻域特点的自适应最近邻居算法[J]. 计算机科学, 2017, 44(12):194-201 FENG Ji, ZHANG Cheng, ZHU Qingsheng. Adaptive nearest neighbor algorithm with dynamic neighborhood[J]. Computer science, 2017, 44(12):194-201


[1]徐长明,南晓斐,王 骄,等.中国象棋机器博弈的时间自适应分配策略研究[J].智能系统学报,2006,1(02):39.
 XU Chang-ming,NAN Xiao-fei,WANG Jiao,et al.Adaptive time allocation strategy in computer game of Chinese Chess[J].CAAI Transactions on Intelligent Systems,2006,1(05):39.
[2]李 晔,常文田,万 磊,等.水下机器人自适应卡尔曼滤波技术研究[J].智能系统学报,2006,1(02):44.
 LI Ye,CHANG Wen-tian,WAN Lei,et al.Research on underwater vehicle adaptive Kalman filter[J].CAAI Transactions on Intelligent Systems,2006,1(05):44.
 CHEN Xiao-bo,CHENG Xian-yi.An adaptive image segmentation technique based on multiAgent system[J].CAAI Transactions on Intelligent Systems,2007,2(05):80.
 YANG Zhenyu,TANG Ke.An overview of parameter control and adaptation strategiesin differential evolution algorithm[J].CAAI Transactions on Intelligent Systems,2011,6(05):415.
 CHEN Mingjie,HUANG Baichuan,ZHANG Min.Function optimization based on an improved hybrid ACO[J].CAAI Transactions on Intelligent Systems,2012,7(05):370.
 SUN Wenxin,MU Huaping.Particle swarm optimization based on self-adaptive population structure[J].CAAI Transactions on Intelligent Systems,2013,8(05):372.[doi:10.3969/j.issn.1673-4785.201211041]
 LIU Changfen,HAN Honggui,QIAO Junfei.Self-adaptive DE algorithm via generalized opposition-based learning[J].CAAI Transactions on Intelligent Systems,2015,10(05):131.[doi:10.3969/j.issn.1673-4785.201310068]
 MA Limin.Global chattering-free sliding mode trajectory tracking control of underactuated autonomous underwater vehicles[J].CAAI Transactions on Intelligent Systems,2016,11(05):200.[doi:10.11992/tis.201512015]
 WANG Xiaoyan,LU Huaxiang,JIN Min,et al.Wavelet entropy denoising algorithm of electrocardiogram signals based on correlation[J].CAAI Transactions on Intelligent Systems,2016,11(05):827.[doi:10.11992/tis.201611017]
 YANG Xiaolan,QIANG Yan,ZHAO Juanjuan,et al.Hashing retrieval for CT images of pulmonary nodules based on medical signs and convolutional neural networks[J].CAAI Transactions on Intelligent Systems,2017,12(05):857.[doi:10.11992/tis.201706035]


更新日期/Last Update: 1900-01-01