ERDOF：基于相对熵权密度离群因子的离群点检测算法

doi:10.11959/j.issn.1000-436x.2021152

通信学报 ›› 2021, Vol. 42 ›› Issue (9): 133-143.doi: 10.11959/j.issn.1000-436x.2021152

ERDOF：基于相对熵权密度离群因子的离群点检测算法

张忠平¹^,²^,³, 刘伟雄¹, 张玉停¹, 邓禹¹, 魏棉鑫¹

¹ 燕山大学信息科学与工程学院，河北秦皇岛 066004
² 河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛 066004
³ 河北省软件工程重点实验室，河北秦皇岛 066004

修回日期:2021-06-30 出版日期:2021-09-25 发布日期:2021-09-01
作者简介:张忠平（1972− ），男，吉林松原人，博士，燕山大学教授，主要研究方向为大数据、数据挖掘、半结构化数据等
刘伟雄（1997− ），男，广东广州人，燕山大学硕士生，主要研究方向为数据挖掘
张玉停（1996− ），男，安徽阜阳人，燕山大学硕士生，主要研究方向为数据挖掘
邓禹（1996− ），男，河北唐山人，燕山大学硕士生，主要研究方向为数据挖掘
魏棉鑫（1997− ），男，广东汕头人，燕山大学硕士生，主要研究方向为数据挖掘
基金资助:
河北省创新能力提升计划基金资助项目(20557640D)

ERDOF: outlier detection algorithm based on entropy weight distance and relative density outlier factor

Zhongping ZHANG¹^,²^,³, Weixiong LIU¹, Yuting ZHANG¹, Yu DENG¹, Mianxin WEI¹

¹ College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China
² The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province, Qinhuangdao 066004, China
³ The Key Laboratory of Software Engineering of Hebei Province, Qinhuangdao 066004, China

Revised:2021-06-30 Online:2021-09-25 Published:2021-09-01
Supported by:
Hebei Province Innovation Capability Improvement Plan Project(20557640D)

摘要/Abstract

摘要：

针对现有离群点检测算法在复杂数据分布和高维度数据集上精度低的问题，提出了一种基于相对熵权密度离群因子的离群点检测算法。首先引入熵权距离取代欧氏距离以提高离群点检测精度。然后结合自然邻居的概念对数据对象进行高斯核密度估计。同时提出相对距离来刻画数据对象偏离邻域的程度，提高所提算法在低密度区域检测离群点的能力。最后提出相对熵权密度离群因子来刻画数据对象的离群程度。在人工数据集和真实数据集下进行的实验表明，所提算法能有效适应各种数据分布和高维数据的离群点检测。

关键词: 数据挖掘, 离群点检测, 信息熵, 核密度估计

Abstract:

An outlier detection algorithm based on entropy weight distance and relative density outlier factor was proposed to solve the problem of low accuracy in complex data distribution and high dimensional data sets.Firstly, entropy weight distance was introduced instead of euclidean distance to improve the detection accuracy of outliers.Then, the Gaussian kernel density estimation was carried out for the data object based on the concept of natural neighbor.At the same time, relative distance was proposed to describe the degree of the data object deviating from the neighborhood and improve the ability of the algorithm to detect outliers in the low-density region.Finally, the entropy weight distance and relative density outlier factor were proposed to describe the degree of outliers.Experiments with artificial data sets and real data sets show that the proposed algorithm can effectively adapt to various data distributions and outlier detection of high-dimensional data.

Key words: data mining, outlier detection, information entropy, kernel density estimation

中图分类号:

TP311

张忠平, 刘伟雄, 张玉停, 邓禹, 魏棉鑫. ERDOF：基于相对熵权密度离群因子的离群点检测算法[J]. 通信学报, 2021, 42(9): 133-143.

Zhongping ZHANG, Weixiong LIU, Yuting ZHANG, Yu DENG, Mianxin WEI. ERDOF: outlier detection algorithm based on entropy weight distance and relative density outlier factor[J]. Journal on Communications, 2021, 42(9): 133-143.

图/表 13

图1

表1

图2

表2

图3

图4

图5

表3

表4

各算法在人工数据集上的AUC得分"

算法	D₁	D₂	D₃	D₄	D₅	D₆
ERDOF	$0 . 99$	$0 . 99$	$0 . 96$	$0 . 99$	$0 . 98$	$0 . 96$
NaNOD	$0 . 99$	$0 . 99$	0.95	0.97	0.96	0.89
NOF	0.97	0.67	0.85	0.74	0.92	0.92
IForest	0.93	$0 . 99$	0.89	0.90	0.68	0.82
LDF	0.94	0.95	0.93	0.97	0.95	0.81
RDOS	0.89	0.95	0.86	0.98	0.97	0.89
COPOD	0.67	0.86	0.92	0.16	0.74	0.35

表4

表5

图6

表6

各算法在真实数据集上的F1得分"

算法	Iris	Wdbc	Wbc	Ionosphere	Rbds	Musk
ERDOF	$0 . 89$	$0 . 92$	0.90	$0 . 88$	$0 . 84$	$0 . 81$
NaNOD	0.78	0.88	0.84	0.75	0.16	0.11
NOF	0.73	0.52	0.58	0.76	0.59	0.51
IForest	0.73	0.75	$0 . 95$	0.83	0.81	0.77
LDF	0.78	0.67	0.90	0.83	0.81	0.77
RDOS	0.64	0.70	$0 . 95$	0.86	0.12	0.07
COPOD	0.84	0.80	0.89	0.10	0.54	0.49

表6

图7

参考文献 29

[1]	RAMOTSOELA D , ABU-MAHFOUZ A , HANCKE G . A survey of anomaly detection in industrial wireless sensor networks with critical water system infrastructure as a case study[J]. Sensors, 2018,18(8): 2491.
[2]	KIRLIDOG M , ASUK C . A fraud detection approach with data mining in health insurance[J]. Procedia-Social and Behavioral Sciences, 2012,62: 989-994.
[3]	ANDRYSIAK T . Sparse representation and overcomplete dictionary learning for anomaly detection in electrocardiograms[J]. Neural Computing and Applications, 2020,32(5): 1269-1285.
[4]	杨加, 李笑难, 张扬 ,等. 基于大数据分析的校园电子邮件异常行为检测技术研究[J]. 通信学报, 2018,39(S1): 116-123.
	YANG J , LI X N , ZHANG Y ,et al. Abnormal behavior detection for campus email systems based on big data analysis[J]. Journal on Communications, 2018,39(S1): 116-123.
[5]	DENNING D E . An intrusion-detection model[J]. IEEE Transactions on Software Engineering, 1987,13(2): 222-232.
[6]	琚安康, 郭渊博, 李涛 ,等. 基于网络通信异常识别的多步攻击检测方法[J]. 通信学报, 2019,40(7): 57-66.
	JU A K , GUO Y B , LI T ,et al. Multi-step attack detection method based on network communication anomaly recognition[J]. Journal on Communications, 2019,40(7): 57-66.
[7]	ROUSSEEUW P J , LEROY A M . Robust regression and outlier detection[M]. New York: John Wiley ＆ Sons,Inc., 1987.
[8]	BARNETT V , LEWIS T , ABELES F . Outliers in statistical data[M]. 3rd ed. Hoboken: John Wiley ＆ Sons, 1994.
[9]	KNORR E M , NG R T , TUCAKOV V . Distance-based outliers:algorithms and applications[J]. The VLDB Journal, 2000,8(3/4): 237-253.
[10]	KNORR E M , NG R T . A unified approach for mining outliers:properties and computation[C]// Proceedings of Conference of the Centre for Advanced Studies on Collaborative Research.[S.n.:s.l.], 1997: 219-222.
[11]	JAIN A K , MURTY M N , FLYNN P J . Data clustering[J]. ACM Computing Surveys, 1999,31(3): 264-323.
[12]	ESTER M , KRIEGEL H , SANDER J . A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]// International Conference on Knowledge Discovery ＆ Data Mining. New York:ACM Press, 1996: 226-231.
[13]	KARYPIS G , HAN E H , KUMAR V . Chameleon:hierarchical clustering using dynamic modeling[J]. Computer, 1999,32(8): 68-75.
[14]	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 Press, 2000: 93-104.
[15]	杨晓晖, 刘晓明 . 基于双向邻居修正的局部异常因子算法[J]. 通信学报, 2020,41(8): 130-140.
	YANG X H , LIU X M . Local outlier factor algorithm based on correction of bidirectional neighbor[J]. Journal on Communications, 2020,41(8): 130-140.
[16]	ZHANG K , HUTTER M , JIN H D . A new local distance-based outlier detection approach for scattered real-world data[C]// Advances in Knowledge Discovery and Data Mining. Berlin:Springer, 2009: 813-822.
[17]	WANG L N , FENG C , REN Y J ,et al. Local outlier detection based on information entropy weighting[J]. International Journal of Sensor Networks, 2019,30(4): 207.
[18]	SCHUBERT E , ZIMEK A , KRIEGEL H P . Generalized outlier detection with flexible kernel density estimates[C]// Proceedings of the 2014 SIAM International Conference on Data Mining.[S.n.:s.l.], 2014: 542-550.
[19]	WAHID A , ANNAVARAPU C S R . NaNOD:a natural neighbour-based outlier detection algorithm[J]. Neural Computing and Applications, 2021,33(6): 2107-2123.
[20]	ZHU Q S , FENG J , HUANG J L . Natural neighbor:a self-adaptive neighborhood method without parameter K[J]. Pattern Recognition Letters, 2016,80: 30-36.
[21]	OMOHUNDRO S M . Five Balltree construction algorithms[R]. Technical Report,International Computer Science Institute, 1989.
[22]	ZHANG L W , LIN J , KARIM R . Adaptive kernel density-based anomaly detection for nonlinear systems[J]. Knowledge-Based Systems, 2018,139: 50-63.
[23]	JIN W , TUNG A K H , HAN J W ,et al. Ranking outliers using symmetric neighborhood relationship[C]// Advances in Knowledge Discovery and Data Mining. Berlin:Springer, 2006: 577-593.
[24]	LIU F T , TING K M , ZHOU Z H . Isolation-based anomaly detection[J]. ACM Transactions on Knowledge Discovery from Data, 2012,6(1): 1-39.
[25]	LATECKI L J , LAZAREVIC A , POKRAJAC D . Outlier detection with kernel density functions[C]// Machine Learning and Data Mining in Pattern Recognition. Berlin:Springer, 2007: 61-75.
[26]	TANG B , HE H B . A local density-based approach for outlier detection[J]. Neurocomputing, 2017,241: 171-180.
[27]	HUANG J L , ZHU Q S , YANG L J ,et al. A non-parameter outlier detection algorithm based on Natural Neighbor[J]. Knowledge-Based Systems, 2016,92: 71-77.
[28]	LI Z , ZHAO Y , BOTTA N ,et al. COPOD:copula-based outlier detection[C]// 2020 IEEE International Conference on Data Mining. Piscataway:IEEE Press, 2020: 1118-1123.
[29]	FLACH P A , . Putting things in order:on the fundamental role of ranking in classification and probability estimation[C]// European Conference on Principles of Data Mining ＆ Knowledge Discovery. Berlin:Springer, 2007: 2-3.

数据集	离群得分
C₁簇的最大值	0.547 4
C₂簇的最大值	0.041 2
o₁	1.835 2
o₂	0.220 9

软硬件环境	参数
CPU	2.60 Hz Inter i7-4720HQ
硬盘	512.0 GB
内存	16.0 GB
开发环境	PyCharm
编译环境	Python 3.8
可视化工具	PyCharm

数据集	样本个数/个	离群点个数/个	离群点比例
D₁	1 256	43	3.4%
D₂	1 043	43	4.1%
D₃	1 000	85	8.5%
D₄	876	77	8.7%
D₅	1 372	72	5.2%
D₆	2 042	64	3.1%

数据集	样本个数/个	属性个数/个	离群点个数/个	离群点比例
Iris	110	4	10	9.1%
Wdbc	390	30	33	8.4%
Wbc	223	9	10	4.5%
Ionosphere	351	34	126	35.8%
Rbds	372	105	38	10.2%
Musk	5 852	166	241	4.1%

ERDOF：基于相对熵权密度离群因子的离群点检测算法

ERDOF: outlier detection algorithm based on entropy weight distance and relative density outlier factor

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 29

相关文章 15

Metrics

推荐阅读 0

[1]	张忠平, 李森, 刘伟雄, 刘书霞. 基于快速密度峰值聚类离群因子的离群点检测算法[J]. 通信学报, 2022, 43(10): 186-195.
[2]	毛伊敏, 邓千虎, 陈志刚. 基于信息熵与遗传算法的并行关联规则增量挖掘算法[J]. 通信学报, 2021, 42(5): 122-136.
[3]	高胜, 向康, 田有亮, 谭伟杰, 冯涛, 吴晓雪. 基于BCP的联合委托学习模型及协议[J]. 通信学报, 2021, 42(5): 137-148.
[4]	徐丰力,李勇. 城市环境下的用户移动行为建模概述[J]. 通信学报, 2020, 41(7): 18-28.
[5]	项英倬,徐正国,游凌. 基于节点通信行为时序的指控信息流挖掘算法[J]. 通信学报, 2019, 40(9): 51-60.
[6]	王莹,苏壮. 无线网络中的移动预测综述[J]. 通信学报, 2019, 40(8): 157-168.
[7]	胡铮,袁浩,朱新宁,倪万里. 面向5G需求的人群流量预测模型研究[J]. 通信学报, 2019, 40(2): 1-10.
[8]	彭舰,王屯屯,陈瑜,刘唐,徐文政. 基于跨平台的在线社交网络用户推荐研究[J]. 通信学报, 2018, 39(3): 147-158.
[9]	俞艺涵,付钰,吴晓平. 基于Shannon信息熵与BP神经网络的隐私数据度量与分级模型[J]. 通信学报, 2018, 39(12): 10-17.
[10]	高志强,王宇涛. 差分隐私技术研究进展[J]. 通信学报, 2017, 38(Z1): 151-155.
[11]	孙鹏浩,兰巨龙,张少军,李军飞. 基于信息熵的匹配域裁剪算法[J]. 通信学报, 2017, 38(5): 182-189.
[12]	迟荣华,程媛,朱素霞,黄少滨,陈德运. 基于快速高斯变换的不确定数据聚类算法[J]. 通信学报, 2017, 38(3): 101-111.
[13]	何明,刘伟世,张江. 支持推荐非空率的关联规则推荐算法[J]. 通信学报, 2017, 38(10): 18-25.
[14]	房玉琢,许志勇,赵兆. 基于近似核密度估计的近场多声源定位算法[J]. 通信学报, 2017, 38(1): 106-116.
[15]	穆海蓉,丁丽萍,宋宇宁,卢国庆. DiffPRFs：一种面向随机森林的差分隐私保护算法[J]. 通信学报, 2016, 37(9): 175-182.