Outlier detection algorithm based on neighborhood value difference metric

doi:10.11772/j.issn.1001-9081.2017123028

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 1905-1909.DOI: 10.11772/j.issn.1001-9081.2017123028

Previous Articles Next Articles

Outlier detection algorithm based on neighborhood value difference metric

YUAN Zhong, FENG Shan

College of Mathematics and Software Science, Sichuan Normal University, Chengdu Sichuan 610068, China

Received:2017-12-25 Revised:2018-02-07 Online:2018-07-10 Published:2018-07-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61673258), the Sichuan Youth Science and Technology Foundation (2017JQ0046), the Scientific Research Project of Sichuan Provincial Education Department (15ZB0029).

基于邻域值差异度量的离群点检测算法

袁钟, 冯山

四川师范大学数学与软件科学学院, 成都 610068

通讯作者: 冯山
作者简介:袁钟(1991-),男,四川井研人,硕士研究生,主要研究方向:粗糙集、数据挖掘;冯山(1967-),男,重庆丰都人,教授,博士,主要研究方向:粗糙集、数据挖掘。
基金资助:
国家自然科学基金资助项目（61673285）；四川省青年科技基金资助项目（2017JQ0046）；四川省教育厅自然科学重点基金资助项目（15ZB0029）。

Abstract

Abstract: Aiming at the problems that symbolic attribute data set can not be processed effectively with traditional distance measure method and numerical attribute data set can not be processed effectively by classical rough set method, an improved method of Neighborhood Value Difference Metric (NVDM) was proposed for outlier detection by utilizing the granulation features of neighborhood rough set. Firstly, with attribute values being normalized, the Neighborhood Information System (NIS) was constructed based on optimized Heterogeneous Euclidian-Overlap Metric (HEOM) and neighborhood radius with adaptive characteristic. Secondly, Neighborhood Outlier Factor (NOF) of data object was constructed based on the NVDM. Finally, a Neighborhood Value Difference Metric-based Outlier Detection (NVDMOD) algorithm was designed and implemented, which improves the traditional unordered one by one model via making full use of the idea of ordered binary and nearest neighbor search in computing Single Attribute Neighborhood Cover (SANC). The NVDMOD algorithm was analyzed and compared with existing outlier detection algorithms including NEighborhood outlier Detection (NED) algorithm, DIStance-based outlier detection (DIS) algorithm and K-Nearest Neighbor (KNN) algorithm on UCI standard data sets. The experimental results show that NVDMOD algorithm has much higher adaptability and effectiveness, and it provides a more effective new method for outlier detection of mixed attribute data sets.

Key words: outlier detection, neighborhood rough set, Neighborhood Value Difference Metric (NVDM), mixed attribute, data mining

摘要： 针对离群点检测中传统距离法不能有效处理符号型属性和经典粗糙集方法不能有效处理数值型属性的问题，利用邻域粗糙集的粒化特征提出了改进的邻域值差异度量（NVDM）方法进行离群点检测。首先，将属性取值归一化并以混合欧氏重叠度量（HEOM）和具有自适应特征的邻域半径构建邻域信息系统（NIS）；其次，以NVDM构造对象的邻域离群因子（NOF）；最后，设计并实现了基于邻域值差异度量的离群点检测（NVDMOD）算法，该算法在计算单属性邻域覆盖（SANC）的方式上充分利用有序二分和近邻搜索思想改进了传统的无序逐一计算模式。在UCI标准数据集上与现有离群点检测算法——邻域离群点检测（NED）算法、基于距离的离群点检测（DIS）算法和K最近邻（KNN）算法进行了实验对比、分析。实验结果表明，NVDMOD算法具有更好的适应性和有效性，为混合型属性数据集的离群点检测提供了一条更有效的新途径。

关键词: 离群点检测, 邻域粗糙集, 邻域值差异度量, 混合型属性, 数据挖掘

CLC Number:

TP274

YUAN Zhong, FENG Shan. Outlier detection algorithm based on neighborhood value difference metric[J]. Journal of Computer Applications, 2018, 38(7): 1905-1909.

袁钟, 冯山. 基于邻域值差异度量的离群点检测算法[J]. 计算机应用, 2018, 38(7): 1905-1909.

References

[1] HAWKINS D. Identification of Outliers[M]. London:Chapman and Hall, 1980:1-2.
[2] 王习特,申德荣,白梅,等.BOD:一种高效的分布式离群点检测算法[J].计算机学报,2016,39(1):36-51.(WANG X T, SHEN D R, BAI M, et al. BOD:an efficient algorithm for distributed outlier detection[J]. Chinese Journal of Computers, 2016, 39(1):36-51).
[3] 邹云峰,张昕,宋世渊,等.基于局部密度的快速离群点检测算法[J].计算机应用,2017,37(10):2932-2937.(ZOU Y F, ZHANG X, SONG S Y, et al. Fast outlier detection algorithm based on local density[J]. Journal of Computer Applications, 2017, 37(10):2932-2937.)
[4] HAN J W, KAMBER M, PEI J. Data Mining:Concepts and Techniques[M]. 3rd ed. San Francisco:Morgan Kaufmann, 2011:543-583.
[5] ROUSSEEUW P J, LEROY A M. Robust Regression and Outlier Detection[M]. Hoboken:John Wiley and Sons, 1987:1-18.
[6] KNORR E M, NG R T, TUCAKOV V. Distance-based outliers:algorithms and applications[J]. The VLDB Journal, 2000, 8(3):237-253.
[7] KNORR E, NG R. A unified notion of outliers:properties and computation[C]//Proceedings of the 1997 International Conference on Knowledge Discovery & Data Mining. Menlo Park, CA:AAAI Press, 1997:219-222.
[8] BREUNIG M M, KRIEGEL H P, NG R T, et al. LOF:identifying density-based local outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2000:93-104.
[9] JAIN A K, MURTY M N, FLYNN P J. Data clustering:a review[J]. ACM Computing Surveys, 1999, 31(3):264-323.
[10] JIANG F, SUI Y F, CAO C G. An information entropy-based approach to outlier detection in rough sets[J]. Expert Systems with Applications, 2010, 37(9):6338-6344.
[11] LIN T Y. Neighborhood systems-application to qualitative fuzzy and rough sets[C]//Advances in Machine Intelligence and Soft-Computing. Durham:Department of Electrical Engineering, 1997:132-155.
[12] HU Q H, YU D R, LIU J F, et al. Neighborhood rough set based heterogeneous feature subset selection[J]. Information Sciences, 2008, 178(18):3577-3594.
[13] CHEN Y M, MIAO D Q, ZHANG H Y. Neighborhood outlier detection[J]. Expert Systems with Applications, 2010, 37(12):8745-8749.
[14] WILSON D R, MARTINEZ T R. Improved heterogeneous distance functions[J]. Journal of Artificial Intelligence Research, 1997, 6(1):1-34.
[15] STANFILL C, WALTZ D. Toward memory-based reasoning[J]. Communications of the ACM, 1986, 29(12):1213-1228.
[16] WILLIAMS J W J. Algorithm 232(heapsort)[J]. Communications of the ACM, 1964, 7(6):347-348.
[17] RAMASWAMY S, RASTOGI R, SHIM K. Efficient algorithms for mining outliers from large datasets[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2000:427-438.
[18] BAY S D. The UCI KDD repository[EB/OL].[2017-05-12]. http://kdd.ics.uci.edu.
[19] AGGARWAL C C, YU P S. Outlier detection for high dimensional data[C]//Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2001:37-46.
[20] HARKINS, HE H X, WILLIAMS G J, et al. Outlier detection using replicator neural networks[C]//Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery. Berlin:Springer, 2002:170-180.

Outlier detection algorithm based on neighborhood value difference metric

基于邻域值差异度量的离群点检测算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	MENG Fan, CHEN Guang, WANG Yong, GAO Yang, GAO Dequn, JIA Wenlong. Multi-granularity temporal structure representation based outlier detection method for prediction of oil reservoir [J]. Journal of Computer Applications, 2021, 41(8): 2453-2459.
[2]	LIU Shize, QIN Yanjun, WANG Chenxing, SU Lin, KE Qixue, LUO Haiyong, SUN Yi, WANG Baohui. Traffic flow prediction algorithm based on deep residual long short-term memory network [J]. Journal of Computer Applications, 2021, 41(6): 1566-1572.
[3]	LI Xujuan, PI Jianyong, HUANG Feixiang, JIA Haipeng. Self-generated deep neural network based 4D trajectory prediction [J]. Journal of Computer Applications, 2021, 41(5): 1492-1499.
[4]	CHEN Kai, YU Yanwei, ZHAO Jindong, SONG Peng. Work location inference method with big data of urban traffic surveillance [J]. Journal of Computer Applications, 2021, 41(1): 177-184.
[5]	NING Jin, CHEN Leiting, LUO Zijuan, ZHOU Chuan, ZENG Huiru. Evaluation metrics of outlier detection algorithms [J]. Journal of Computer Applications, 2020, 40(9): 2622-2627.
[6]	LONG Yangyang, CHEN Yuling, XIN Yang, DOU Hui. Secure energy transaction scheme based on alliance blockchain [J]. Journal of Computer Applications, 2020, 40(6): 1668-1673.
[7]	DU Xusheng, YU Jiong, YE Lele, CHEN Jiaying. Outlier detection algorithm based on graph random walk [J]. Journal of Computer Applications, 2020, 40(5): 1322-1328.
[8]	XU Zhoubo, YANG Jian, LIU Huadong, HUANG Wenwen. Protein complex identification algorithm based on XGboost and topological structural information [J]. Journal of Computer Applications, 2020, 40(5): 1510-1514.
[9]	CHEN Xi, MEI Guang, ZHANG Jinjin, XU Weisheng. Student grade prediction method based on knowledge graph and collaborative filtering [J]. Journal of Computer Applications, 2020, 40(2): 595-601.
[10]	MA Dong, CHEN Hongmei, WANG Lizhen, XIAO Qing. Dominant feature mining of spatial sub-prevalent co-location patterns [J]. Journal of Computer Applications, 2020, 40(2): 465-472.
[11]	LI Shasha, LIANG Dongyang, YU Jie, JI Bin, MA Jun, TAN Yusong, WU Qingbo. Research team mining algorithm based on teacher-student relationship [J]. Journal of Computer Applications, 2020, 40(11): 3198-3202.
[12]	SUN Heli, ZHANG Youyou, YANG Zhou, HE Liang, JIA Xiaolin. Urban reachable region search based on time segment tree [J]. Journal of Computer Applications, 2020, 40(10): 2936-2941.
[13]	LI Bo, ZHANG Xiao, YAN Jingyi, LI Kewei, LI Heng, LING Yulong, ZHANG Yong. Application of KNN algorithm based on value difference metric and clustering optimization in bank customer behavior prediction [J]. Journal of Computer Applications, 2019, 39(9): 2784-2788.
[14]	NING Jin, CHEN Leiting, ZHOU Chuan, ZHANG Lei. Intelligent trigger mechanism for model aggregation and disaggregation [J]. Journal of Computer Applications, 2019, 39(6): 1614-1618.
[15]	JI Lina, CHEN Kai, YU Yanwei, SONG Peng, WANG Shuying, WANG Chenrui. Vehicle type mining and application analysis based on urban traffic big data [J]. Journal of Computer Applications, 2019, 39(5): 1343-1350.