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

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

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

CLC Number:

TP311

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.

Figures/Tables 13

算法	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

算法	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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

数据集	离群得分
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: outlier detection algorithm based on entropy weight distance and relative density outlier factor

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 29

Related Articles 15

Metrics

Recommended 0

[1]	Zhongping ZHANG, Sen LI, Weixiong LIU, Shuxia LIU. Outlier detection algorithm based on fast density peak clustering outlier factor [J]. Journal on Communications, 2022, 43(10): 186-195.
[2]	Yimin MAO, Qianhu DENG, Zhigang CHEN. Parallel association rules incremental mining algorithm based on information entropy and genetic algorithm [J]. Journal on Communications, 2021, 42(5): 122-136.
[3]	Sheng GAO, Kang XIANG, Youliang TIAN, Weijie TAN, Tao FENG, Xiaoxue WU. BCP-based joint delegation learning model and protocol [J]. Journal on Communications, 2021, 42(5): 137-148.
[4]	Xiaohui YANG,Xiaoming LIU. Local outlier factor algorithm based on correction of bidirectional neighbor [J]. Journal on Communications, 2020, 41(8): 130-140.
[5]	Fengli XU,Yong LI. Survey on user’s mobility behavior modelling in urban environment [J]. Journal on Communications, 2020, 41(7): 18-28.
[6]	Yingzhuo XIANG,Zhengguo XU,Ling YOU. Instruction flow mining algorithm based on the temporal sequence of node communication actions [J]. Journal on Communications, 2019, 40(9): 51-60.
[7]	Ying WANG,Zhuang SU. Survey of mobility prediction in wireless network [J]. Journal on Communications, 2019, 40(8): 157-168.
[8]	Zheng HU,Hao YUAN,Xinning ZHU,Wanli NI. Research on crowd flows prediction model for 5G demand [J]. Journal on Communications, 2019, 40(2): 1-10.
[9]	Jian PENG,Tuntun WANG,Yu CHEN,Tang LIU,Wenzheng XU. User recommendation based on cross-platform online social networks [J]. Journal on Communications, 2018, 39(3): 147-158.
[10]	Yihan YU,Yu FU,Xiaoping WU. Metric and classification model for privacy data based on Shannon information entropy and BP neural network [J]. Journal on Communications, 2018, 39(12): 10-17.
[11]	Zhi-qiang GAO,Yu-tao WANG. Survey on differential privacy and its progress [J]. Journal on Communications, 2017, 38(Z1): 151-155.
[12]	Peng-hao SUN,Ju-long LAN,Shao-jun ZHANG,Jun-fei LI. Information entropy based match field cutting algorithm [J]. Journal on Communications, 2017, 38(5): 182-189.
[13]	Rong-hua CHI,Yuan CHENG,Su-xia ZHU,Shao-bin HUANG,De-yun CHEN. Uncertain data analysis algorithm based on fast Gaussian transform [J]. Journal on Communications, 2017, 38(3): 101-111.
[14]	Ming HE,Wei-shi LIU,Jiang ZHANG. Association rules recommendation algorithm supporting recommendation nonempty [J]. Journal on Communications, 2017, 38(10): 18-25.
[15]	Hai-rong MU,Li-ping DING,Yu-ning SONG,Guo-qing LU. DiffPRFs:random forest under differential privacy [J]. Journal on Communications, 2016, 37(9): 175-182.