一种基于邻域粒度熵的离群点检测算法

摘要/Abstract

摘要： 离群点检测是数据挖掘领域的重要研究方向之一，其目的是找出数据集中与其他数据对象显著不同的一小部分数据。离群点检测在网络入侵检测、信用卡欺诈检测、医疗诊断等领域有着非常重要的应用。近年来，粗糙集理论被广泛用于离群点检测，然而，经典的粗糙集模型不能有效处理数值型数据。对此，本文利用邻域粗糙集模型来检测离群点，在邻域粗糙集中引入一种新的信息熵模型——邻域粒度熵。基于邻域粒度熵，提出一种新的离群点检测算法OD_NGE。实验结果表明，相对于已有的离群点检测算法，OD_NGE具有更好的离群点检测性能。

关键词: 离群点检测, 邻域粗糙集, 知识粒度, 邻域粒度熵, 数值型数据

Abstract: Outlier detection is one of the important research directions in the field of data mining. Its purpose is to find out a small portion of data in the data set that is significantly different from other data objects. Outlier detection has very important applications in the fields of network intrusion detection, credit card fraud detection, medical diagnosis and so on. Recently, rough set theory has been widely used in outlier detection. However, the classical rough set model can not effectively deal with the numerical and mixed data. Therefore, in this paper we employ the neighborhood rough set model to detect outliers, and introduce a new information entropy model——neighborhood granular entropy in neighborhood rough sets. Based on the neighborhood granularity entropy, a new outlier detection algorithm called OD_NGE is proposed. Experimental results show that OD_NGE has better outlier detection performance than the existing algorithms.

Key words: outlier detection, neighborhood rough set, knowledge granularity, neighborhood granular entropy, numeric data

段珣, 杨志勇, 江峰. 一种基于邻域粒度熵的离群点检测算法[J]. 计算机与现代化, 2022, 0(10): 19-23.

DUAN Xun, YANG Zhi-yong, JIANG Feng. An Outlier Detection Algorithm Based on Neighborhood Granular Entropy[J]. Computer and Modernization, 2022, 0(10): 19-23.

参考文献［28］

［1］	ROUSSEEUW P J, LEROY A M. Robust Regression and Outlier Detection［M］. New York: John Wiley & Sons, 1987.
［2］	JIANG F, SUI Y F, CAO C G. A hybrid approach to outlier detection based on boundary region［J］. Pattern Recognition Letter, 2011,32(14):1860-1870.
［3］	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. 2000:93-104.〖HJ0.27mm〗
［4］	耿志强,姬威,韩永明,等. 基于维度最大熵数据流聚类的异常检测方法［J］. 控制与决策, 2016,31(2):343-348.
［5］	江峰,王凯郦,于旭,等. 基于粗糙熵的离群点检测方法及其在无监督入侵检测中的应用［J］. 控制与决策, 2020,35(5):1199-1204.
［6］	袁钟,冯山. 基于邻域值差异度量的离群点检测算法［J］. 计算机应用, 2018,38(7):1905-1909.
［7］	袁钟,张贤勇,冯山. 邻域粗糙集中基于序列的混合型属性离群点检测［J］. 小型微型计算机系统, 2018,39(6):1317-1322.
［8］	PAWLAK Z. Rough sets［J］. International Journal of Computer and Information Sciences, 1982,11(5):341-356.
［9］	HU Q H, YU D R, XIE Z X. Neighborhood classifiers［J］. Expert Systems with Applications, 2008,34(2):866-876.
［10］	HU Q H, LIU J F, YU D R. Mixed feature selection based on granulation and approximation［J］. Knowledge-Based Systems, 2008,21(4):294-304.
［11］	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.
［12］	SHANNON C E. A mathematical theory of communication［J］. The Bell System Technical Journal, 1948,27(3):379-423.
［13］	HU Q H, YU D R. Neighborhood entropy［C］// Proceedings of the 2009 International Conference on Machine Learning and Cybernetics. 2009,3:1776-1782.
［14］	CHEN Y M, WU K S, CHEN X H, et al. An entropy-based uncertainty measurement approach in neighborhood systems［J］. Information Sciences, 2014,279:239-250.
［15］	ZENG K, SHE K, NIU X Z. Feature selection with neighborhood entropy-based cooperative game theory［J］. Computational Intelligence and Neuroscience, 2014,2014. DOI:10.1155/2014/479289.
［16］	WILSON D R, MARTINEZ T R. Improved heterogeneous distance functions［J］. Journal of Artificial Intelligence Research, 1997,6(1):1-34.
［17］	YUAN Z, ZHANG X Y, FENG S. Hybrid data-driven outlier detection based on neighborhood information entropy and its developmental measures［J］. Expert Systems with Applications, 2018,112:243-257.
［18］	盛魁,卞显福,董辉,等. 基于邻域粗糙集组合度量的混合数据属性约简算法［J］. 计算机应用与软件, 2020,37(2):234-239.
［19］	RAMASWAMY S, RASTOGI R, SHIM K. Efficient algorithms for mining outliers from large data sets［C］// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. 2000:427-438.
［20］	CHEN Y M, MIAO D Q, ZHANG H. Y. Neighborhood outlier detection［J］. Expert Systems with Application, 2010,37(12):8745-8749.
［21］	袁钟. 基于邻域粗糙集的混合型属性离群点检测方法研究［D］. 成都:四川师范大学, 2018.
［22］	HARKINS S, 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. 2002:170-180.
［23］	江峰,杜军威,葛艳,等. 基于粗糙集理论的序列离群点检测［J］. 电子学报, 2011,39(2):345-350.
［24］	张玉婷. 基于邻域粗糙度量的离群点检测方法研究［D］. 成都:四川师范大学, 2021.
［25］	谭阳. 基于粗糙熵的渐进式离群点检测方法研究［D］. 成都:四川师范大学, 2021.
［26］	杨晓玲,张贤勇. 基于邻域粗糙隶属函数的离群点检测［J］. 计算机工程与设计, 2019,40(2):533-539.
［27］	郭春. 基于数据挖掘的网络入侵检测关键技术研究［D］. 北京:北京邮电大学, 2014.
［28］	TAN P N, STEINBACH M, KUMAR V. Introduction to Data Mining［M］. Pearson Education India, 2016.［1］ ROUSSEEUW P J, LEROY A M. Robust Regression and Outlier Detection［M］. New York: John Wiley & Sons, 1987.
［2］	JIANG F, SUI Y F, CAO C G. A hybrid approach to outlier detection based on boundary region［J］. Pattern Recognition Letter, 2011,32(14):1860-1870.
［3］	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. 2000:93-104.〖HJ0.27mm〗
［4］	耿志强,姬威,韩永明,等. 基于维度最大熵数据流聚类的异常检测方法［J］. 控制与决策, 2016,31(2):343-348.
［5］	江峰,王凯郦,于旭,等. 基于粗糙熵的离群点检测方法及其在无监督入侵检测中的应用［J］. 控制与决策, 2020,35(5):1199-1204.
［6］	袁钟,冯山. 基于邻域值差异度量的离群点检测算法［J］. 计算机应用, 2018,38(7):1905-1909.
［7］	袁钟,张贤勇,冯山. 邻域粗糙集中基于序列的混合型属性离群点检测［J］. 小型微型计算机系统, 2018,39(6):1317-1322.
［8］	PAWLAK Z. Rough sets［J］. International Journal of Computer and Information Sciences, 1982,11(5):341-356.
［9］	HU Q H, YU D R, XIE Z X. Neighborhood classifiers［J］. Expert Systems with Applications, 2008,34(2):866-876.
［10］	HU Q H, LIU J F, YU D R. Mixed feature selection based on granulation and approximation［J］. Knowledge-Based Systems, 2008,21(4):294-304.
［11］	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.
［12］	SHANNON C E. A mathematical theory of communication［J］. The Bell System Technical Journal, 1948,27(3):379-423.
［13］	HU Q H, YU D R. Neighborhood entropy［C］// Proceedings of the 2009 International Conference on Machine Learning and Cybernetics. 2009,3:1776-1782.
［14］	CHEN Y M, WU K S, CHEN X H, et al. An entropy-based uncertainty measurement approach in neighborhood systems［J］. Information Sciences, 2014,279:239-250.
［15］	ZENG K, SHE K, NIU X Z. Feature selection with neighborhood entropy-based cooperative game theory［J］. Computational Intelligence and Neuroscience, 2014,2014. DOI:10.1155/2014/479289.
［16］	WILSON D R, MARTINEZ T R. Improved heterogeneous distance functions［J］. Journal of Artificial Intelligence Research, 1997,6(1):1-34.
［17］	YUAN Z, ZHANG X Y, FENG S. Hybrid data-driven outlier detection based on neighborhood information entropy and its developmental measures［J］. Expert Systems with Applications, 2018,112:243-257.
［18］	盛魁,卞显福,董辉,等. 基于邻域粗糙集组合度量的混合数据属性约简算法［J］. 计算机应用与软件, 2020,37(2):234-239.
［19］	RAMASWAMY S, RASTOGI R, SHIM K. Efficient algorithms for mining outliers from large data sets［C］// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. 2000:427-438.
［20］	CHEN Y M, MIAO D Q, ZHANG H. Y. Neighborhood outlier detection［J］. Expert Systems with Application, 2010,37(12):8745-8749.
［21］	袁钟. 基于邻域粗糙集的混合型属性离群点检测方法研究［D］. 成都:四川师范大学, 2018.
［22］	HARKINS S, 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. 2002:170-180.
［23］	江峰,杜军威,葛艳,等. 基于粗糙集理论的序列离群点检测［J］. 电子学报, 2011,39(2):345-350.
［24］	张玉婷. 基于邻域粗糙度量的离群点检测方法研究［D］. 成都:四川师范大学, 2021.
［25］	谭阳. 基于粗糙熵的渐进式离群点检测方法研究［D］. 成都:四川师范大学, 2021.
［26］	杨晓玲,张贤勇. 基于邻域粗糙隶属函数的离群点检测［J］. 计算机工程与设计, 2019,40(2):533-539.
［27］	郭春. 基于数据挖掘的网络入侵检测关键技术研究［D］. 北京:北京邮电大学, 2014.
［28］	TAN P N, STEINBACH M, KUMAR V. Introduction to Data Mining［M］. Pearson Education India, 2016.

[1]	庄丽丽, 石鸿雁. 基于改进布谷鸟搜索的k-means算法的离群点检测[J]. 计算机与现代化, 2021, 0(10): 15-22.
[2]	李华，江峰，于旭，杜军威，刘国柱. 基于粒度决策熵的属性约简[J]. 计算机与现代化, 2018, 0(04): 7-.
[3]	陆柳生，余明晖. 基于离群点检测的学生学习状态分析方法[J]. 计算机与现代化, 2016, 0(3): 35-40.
[4]	魏龙1，王勇2. 基于密度划分的离群点检测算法[J]. 计算机与现代化, 2015, 0(3): 26-32.
[5]	杨维永1，何军2，郑生军3，张旭东4. 一种适宜于子空间聚类的离群点检测算法[J]. 计算机与现代化, 2015, 0(12): 39-.