[1]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(5):998-1006.[doi:10.11992/tis.201809032]
Copy

A parameter-free outlier detection algorithm based on natural neighborhood graph

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 14 Number of periods: 2019 5 Page number: 998-1006 Column: 学术论文—机器学习 Public date: 2019-09-05
Title:
A parameter-free outlier detection algorithm based on natural neighborhood graph
Author(s):
FENG Ji;  RAN Ruisheng;  WEI Yan
College of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China
Keywords:
parameter-free; adaptive neighbor; nearest neighbor; weighted graph; outlier detection; outlier factor; global outlier; local outlier
CLC:
TP311
DOI:
10.11992/tis.201809032
Abstract:
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.
References:
[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
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems