Collective Data Anomaly Detection Based on Reverse k-Nearest Neighbor Filtering

doi:10.16183/j.cnki.jsjtu.2020.011

Abstract

Abstract:

Aimed at the problem of group data anomaly detection with no data labels, a k-nearest neighbor (kNN) algorithm is proposed to detect group data anomalies in the unsupervised mode. In order to reduce false negatives and false positives caused by the mutual interference between abnormal and normal values, a reverse k-nearest neighbor (RkNN) method is proposed to filter the abnormal group data in reverse. First, the RkNN algorithm uses statistical distance as the similarity measure between different groups of data. Then, the anomaly scores of each group and the initial abnormality are obtained by using the kNN algorithm. Finally, the initial abnormality is filtered by using the RkNN method. The experiment results show that the algorithm proposed can not only effectively reduce the false negatives and false positives, but also has a high anomaly detection rate and good stability.

Key words: abnormal detection, unsupervised, k-nearest neighbor (kNN), reverse k-nearest neighbor (RkNN), statistical distance

CLC Number:

TP399

WU Jin’e, WANG Ruoyu, DUAN Qianqian, LI Guoqiang, JÜ Changjiang. Collective Data Anomaly Detection Based on Reverse k-Nearest Neighbor Filtering[J]. Journal of Shanghai Jiao Tong University, 2021, 55(5): 598-606.

Figures/Tables 9

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Tab.1

Tab.2

Fig.7

References 19

[1]	MEHROTRA K G, MOHAN C K, HUANG H M. Anomaly detection principles and algorithms[M]. Switzerland: Springer International Publishing, 2017.
[2]	TIMČENKO V, GAJIN S. Ensemble classifiers for supervised anomaly based network intrusion detection [C]//2017 13th IEEE International Conference on Intelligent Computer Communication and Processing (ICCP). Piscataway, NJ, USA: IEEE, 2017: 13-19.
[3]	HUSSAIN B, DU Q H, REN P Y. Semi-supervised learning based big data-driven anomaly detection in mobile wireless networks[J]. China Communications, 2018, 15(4):41-57.
[4]	MILLER D J, KESIDIS G, QIU Z C. Unsupervised parsimonious cluster-based anomaly detection (PCAD) [C]//2018 IEEE 28th International Workshop on Machine Learning for Signal Processing (MLSP). Piscataway, NJ, USA: IEEE, 2018: 1-6.
[5]	CHANDOLA V, BANERJEE A, KUMAR V. Anomaly detection[J]. ACM Computing Surveys, 2009, 41(3):1-58.
[6]	TAO X T, LI G Q, SUN D, et al. A game-theoretic model and analysis of data exchange protocols for Internet of Things in clouds[J]. Future Generation Computer Systems, 2017, 76:582-589. doi: 10.1016/j.future.2016.12.030 URL
[7]	EDGEWORTH F Y. On discordant observations[J]. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 1887, 23(143):364-375. doi: 10.1080/14786448708628471 URL
[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. doi: 10.1007/s007780050006 URL
[9]	LEE J G, HAN J W, LI X L. Trajectory outlier detection: A partition-and-detect framework [C]//2008 IEEE 24th International Conference on Data Engineering. Piscataway, NJ, USA: IEEE, 2008: 140-149.
[10]	LUAN F J, ZHANG Y T, CAO K Y, et al. Based local density trajectory outlier detection with partition-and-detect framework [C]//2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD). Piscataway, NJ, USA: IEEE, 2017: 1708-1714.
[11]	DJENOURI Y, BELHADI A, LIN J C, et al. Adapted K-nearest neighbors for detecting anomalies on spatio-temporal traffic flow[J]. IEEE Access, 2019, 7:10015-10027. doi: 10.1109/Access.6287639 URL
[12]	毛江云, 吴昊, 孙未未. 路网空间下基于马尔可夫决策过程的异常车辆轨迹检测算法[J]. 计算机学报, 2018, 41(8):1928-1942.
	MAO Jiangyun, WU Hao, SUN Weiwei. Vehicle trajectory anomaly detection in road network via Markov decision process[J]. Chinese Journal of Computers, 2018, 41(8):1928-1942.
[13]	WANG R Y, SUN D, LI G Q, et al. Statistical detection of collective data Fraud [C]//International Conference on Multimedia and Expo. London, UK: IEEE, 2020.
[14]	KULLBACK S, LEIBLER R A. On information and sufficiency[J]. Annals of Mathematical Statistics, 1951, 22(1):79-86. doi: 10.1214/aoms/1177729694 URL
[15]	SALEM O, NAÏT-ABDESSELAM F, MEHAOUA A. Anomaly detection in network traffic using Jensen-Shannon divergence [C]//2012 IEEE International Conference on Communications (ICC). Piscataway, NJ, USA: IEEE, 2012: 5200-5204.
[16]	COVER T, HART P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13(1):21-27. doi: 10.1109/TIT.1967.1053964 URL
[17]	WOHLKINGER W, ALDOMA A, RUSU R B, et al. 3DNet: Large-scale object class recognition from CAD models [C]//2012 IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2012: 5384-5391.
[18]	AGGARWAL C C. Proximity-based outlier detection[M]// Outlier Analysis. Switzerland: Springer International Publishing, 2016: 111-147.
[19]	陈瑜. 离群点检测算法研究[D]. 兰州: 兰州大学, 2018.
	CHEN Yu. Research on the outliers detection algorithm[D]. Lanzhou: Lanzhou University, 2018.

模式	算法名称	一阶直方图				二阶直方图
模式	算法名称	P/%	R/%	F₁/%	t/ms	P/%	R/%	F₁/%	t/ms
集中式刷信誉	SDD-RkNN	96.30	96.30	96.30	4542.80	97.23	97.23	97.23	1612.45
	DBD-RkNN	99.69	99.69	99.69	2325.97	91.69	91.69	91.69	762.44
	DSDD-E	78.84	99.69	87.99	1507.32	65.06	96.92	77.71	491.29
均衡式刷信誉	SDD-RkNN	20.92	20.92	20.92	4401.57	80.92	80.92	80.92	1517.24
	DBD-RkNN	79.38	79.38	79.38	2265.98	69.84	69.84	69.84	718.89
	DSDD-E	23.78	13.54	17.25	1400.54	54.67	80.31	64.52	494.79

模式	算法名称	一阶直方图				二阶直方图
模式	算法名称	P/%	R/%	F₁/%	t/ms	P/%	R/%	F₁/%	t/ms
集中式刷信誉	SDD-RkNN	94.46	94.46	94.46	9671.67	88.00	88.00	88.00	2108.75
	DBD-RkNN	96.30	96.30	96.30	4637.67	74.77	74.77	74.77	995.40
	DSDD-E	75.17	100.00	85.70	2140.21	49.14	91.38	63.90	565.68
均衡式刷信誉	SDD-RkNN	16.92	16.92	16.92	10356.19	79.69	79.69	79.69	1940.85
	DBD-RkNN	81.85	81.85	81.85	4913.40	58.46	58.46	58.46	898.06
	DSDD-E	23.35	13.84	17.38	2280.15	53.77	75.08	60.98	550.01