基于快速密度峰值聚类离群因子的离群点检测算法

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

Abstract

Abstract:

For the problem that peak density clustering algorithm requires human set parameters and high time complexity, an outlier detection algorithm based on fast density peak clustering outlier factor was proposed.Firstly, k nearest neighbors algorithm was used to replace the density peak of density estimate, which adopted the KD-Tree index data structure calculation of k close neighbors of data objects, and then the way of the product of density and distance was adopted to automatic selection of clustering centers.In addition, the centripetal relative distance and fast density peak clustering outliers were defined to describe the degree of outliers of data objects.Experiments on artificial data sets and real data sets were carried out to verify the algorithm, and compared with some classical and novel algorithms.The validity and time efficiency of the proposed algorithm are verified.

Key words: data mining, density peak clustering, outlier, k nearest neighbor, centripetal relative distance

CLC Number:

TP311

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.

Figures/Tables 13

算法	D₁	D₂	D₃	D₄
FDPC-OF	$100 . 00 %$	$97 . 67 %$	$87 . 05 %$	$95 . 83 %$
COF	86.04%	95.34%	76.47%	93.05%
NOF	95.34%	41.86%	57.64%	75.00%
LDF	93.02%	$97 . 67 %$	84.70%	81.94%
RDOS	97.67%	32.55%	58.82%	84.72%
IForest	53.48%	93.02%	76.47%	26.38%
NANOD	48.83%	32.55%	71.76%	18.05%
MOD	83.72%	93.02%	76.47%	88.89%

算法	D₁	D₂	D₃	D₄
FDPC-OF	$97 . 72 %$	$95 . 45 %$	$85 . 05 %$	$93 . 87 %$
COF	85.23%	93.18%	75.29%	91.84%
NOF	93.18%	40.90%	56.32%	74.15%
LDF	92.05%	$95 . 45 %$	83.91%	80.27%
RDOS	96.60%	31.81%	58.05%	82.99%
IForest	52.27%	92.05%	74.71%	25.85%
NANOD	47.72%	31.81%	70.11%	18.35%
MOD	81.82%	90.91%	76.44%	88.44%

算法	Ionosphere	Iris	Wdbc	Vowels
FDPC-OF	$91 . 26 %$	70%	$78 . 78 %$	$78 %$
COF	77.77%	60%	36.36%	50%
RDOS	53.17%	60%	15.15%	4%
LDF	87.30%	70%	33.33%	48%
NOF	69.04%	50%	12.12%	26%
IForest	63.49%	50%	57.57%	14%
NANOD	73.81%	$80 %$	$78 . 78 %$	52%
MOD	84.92%	60%	$78 . 78 %$	42%

算法	Ionosphere	Iris	Wdbc	Vowels
FDPC-OF	$89 . 14 %$	70%	$79 . 09 %$	$76 . 47 %$
COF	76.36%	60%	37.27%	49.01%
RDOS	53.17%	60%	14.92%	3.92%
LDF	85.27%	70%	32.83%	48.03%
NOF	68.61%	50%	11.94%	26.45%
IForest	62.01%	50%	56.71%	14.65%
NANOD	72.48%	$80 %$	77.61%	52.90%
MOD	84.12%	60%	$79 . 09 %$	42.15%

References 32

[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 (Basel,Switzerland), 2018,18(8): 2491.
[2]	AVDIIENKO V , KUZNETSOV K , ROMMELFANGER I ,et al. Detecting behavior anomalies in graphical user interfaces[C]// Proceedings of IEEE/ACM 39th International Conference on Software Engineering Companion (ICSE-C). Piscataway:IEEE Press, 2017: 201-203.
[3]	NGAI E W T , HU Y , WONG Y H ,et al. The application of data mining techniques in financial fraud detection:a classification framework and an academic review of literature[J]. Decision Support Systems, 2011,50(3): 559-569.
[4]	季一木, 杨卫东, 李奎 ,等. 基于主机系统调用频率的容器入侵检测方法[J]. 网络与信息安全学报, 2021,7(4): 18-29.
	JI Y M , YANG W D , LI K ,et al. Container intrusion detection method based on host system call frequency[J]. Chinese Journal of Network and Information Security, 2021,7(4): 18-29.
[5]	ANDRYSIAK T . Sparse representation and overcomplete dictionary learning for anomaly detection in electrocardiograms[J]. Neural Computing and Applications, 2020,32(5): 1269-1285.
[6]	ROUSSEEUW P J , LEROY A M . Robust regression and outlier detection[M]. New Jersey: John Wiley ＆ Sons, 1987.
[7]	BARNETT V , LEWIS T , ABELES F . Outliers in statistical data[M]. New Jersey: John Wiley ＆ Sons, 1994.
[8]	KNORR E M , NG R T , TUCAKOV V . Distance-based outliers:algorithms and applications[J]. The VLDB Journal, 2000,8(3/4): 237-253.
[9]	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.
[10]	JAIN A K , MURTY M N , FLYNN P J . Data clustering[J]. ACM Computing Surveys, 1999,31(3): 264-323.
[11]	ESTER M , KRIEGEL H , SANDER J ,et al. 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.
[12]	KARYPIS G , HAN E H , KUMAR V . Chameleon:hierarchical clustering using dynamic modeling[J]. Computer, 1999,32(8): 68-75.
[13]	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.
[14]	杨晓晖, 刘晓明 . 基于双向邻居修正的局部异常因子算法[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.
[15]	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.
[16]	WANG L N , FENG C , REN Y J ,et al. Local outlier detection based on information entropy weighting[J]. International Journal of SensorNetworks, 2019,30(4): 207.
[17]	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.
[18]	WAHID A , ANNAVARAPU C S R . NaNOD:a natural neigh-bour-based outlier detection algorithm[J]. Neural Computing and Applications, 2021,33(6): 2107-2123.
[19]	RODRIGUEZ A , LAIO A . Clustering by fast search and find of density peaks[J]. Science, 2014,344(6191): 1492-1496.
[20]	XU X , DING S F , DU M J ,et al. DPCG:an efficient density peaks clustering algorithm based on grid[J]. International Journal of Machine Learning and Cybernetics, 2018,9(5): 743-754.
[21]	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.
[22]	MACQUEEN J , . Some methods for classification and analysis of multivariate observations[C]// Proceedings of Berkeley Symposium on Mathematical Statistics ＆ Probability. Berkeley:University of California Press, 1967: 281-297.
[23]	ESTER M , KRIEGEL H , SANDER J ,et al. 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.
[24]	COMANICIU D , MEER P . MeanShift:a robust approach toward feature space analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(5): 603-619.
[25]	DANG T T , NGAN H Y T , LIU W . Distance-based k-nearest neighbors outlier detection method in large-scale traffic data[C]// Proceedings of IEEE International Conference on Digital Signal Processing. Piscataway:IEEE Press, 2015: 507-510.
[26]	TANG J , CHEN Z X , FU A W C ,et al. Enhancing effectiveness of outlier detections for low density patterns[C]// Advances in Knowledge Discovery and Data Mining. Berlin:Springer, 2002: 535-548.
[27]	TANG B , HE H B . A local density-based approach for outlier detection[J]. Neurocomputing, 2017,241: 171-180.
[28]	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.
[29]	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.
[30]	WAHID A , ANNAVARAPU C S R . NaNOD:a natural neighbour-based outlier detection algorithm[J]. Neural Computing and Applications, 2021,33(6): 2107-2123.
[31]	YANG J W , RAHARDJA S , FR?NTI P , . Mean-shift outlier detection and filtering[J]. Pattern Recognition, 2021,115:107874.
[32]	FRANK A , ASUNCION A . UCI machine learning repository[R]. 2010.

Metrics

Recommended 0

No Suggested Reading articles found!

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

数据集	样本个数/个	离群点个数/个	离群点比例
D₁	1 256	43	3.4%
D₂	1 043	43	4.1%
D₃	1 000	85	8.5%
D₄	1 372	72	5.2%

数据集	样本个数/个	属性个数/个	离群点个数/个	离群点比例
Ionosphere	351	34	126	35.9%
Iris	110	4	10	9.1%
Wdbc	390	30	33	8.4%
Vowels	1 456	12	50	3.4%

Outlier detection algorithm based on fast density peak clustering outlier factor

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 32

Related Articles 15

Metrics

Recommended 0

[1]	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.
[2]	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.
[3]	Xiaohui YANG,Xiaoming LIU. Local outlier factor algorithm based on correction of bidirectional neighbor [J]. Journal on Communications, 2020, 41(8): 130-140.
[4]	Fengli XU,Yong LI. Survey on user’s mobility behavior modelling in urban environment [J]. Journal on Communications, 2020, 41(7): 18-28.
[5]	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.
[6]	Ying WANG,Zhuang SU. Survey of mobility prediction in wireless network [J]. Journal on Communications, 2019, 40(8): 157-168.
[7]	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.
[8]	Jianqiu XU,Junxiu LIANG,Xiaolin QIN. k nearest neighbor pattern match queries over spatio-temporal label trajectories [J]. Journal on Communications, 2018, 39(4): 112-122.
[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]	Zhi-qiang GAO,Yu-tao WANG. Survey on differential privacy and its progress [J]. Journal on Communications, 2017, 38(Z1): 151-155.
[11]	Chang-li ZHOU,Hui TIAN,Chun-guang MA,Song-tao YANG. Research on LBS privacy preservation based on pseudorandom permutation in road network [J]. Journal on Communications, 2017, 38(6): 19-29.
[12]	Ming HE,Wei-shi LIU,Jiang ZHANG. Association rules recommendation algorithm supporting recommendation nonempty [J]. Journal on Communications, 2017, 38(10): 18-25.
[13]	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.
[14]	Yu-fei ZHAO,Gang XIONG,Long-tao HE,Zhou-jun LI. Approach to detecting SQL injection behaviors in network environment [J]. Journal on Communications, 2016, 37(2): 89-98.
[15]	Hong-cheng LI,Xiao-ping WU,Yan CHEN. k-means clustering method preserving differential privacy in MapReduce framework [J]. Journal on Communications, 2016, 37(2): 125-131.