Survey of Proximity Methods for Outlier Detection

doi:10.3778/j.issn.1002-8331.2206-0127

Abstract

Abstract: Outlier detection is widely used in data mining, but not all outlier detection problems can be solved by an optimal method. For different applications, different methods are used to solve practical problems most effectively. At present, detection methods can be roughly divided into statistics-based, clustering-based, proximity-based（distance-based and density-based） methods. In order to grasp the current research status of outlier detection methods based on proximity technology, through collation and induction, the representative outlier detection methods based on proximity are introduced and evaluated. it is mainly divided into distance-based method and density-based method, and the application scenarios, algorithm ideas, problems that can be solved and their advantages and disadvantages of all the mentioned methods are analyzed and summarized in detail. The existing problems and the development direction of future research are pointed out. It is of great significance to carry out the research of neighborhood outlier detection.

Key words: proximity, outlier detection, distance-based, density-based

摘要： 离群点检测在数据挖掘中有非常广泛的应用，然而并不是所有的离群点检测问题都能用一种最优的方法去解决。针对不同的应用，需要用不同的方法，才能够最有效地解决实际问题。检测方法大致可以分为基于统计、基于聚类、基于邻近性（基于距离和基于密度）的方法。为了及时掌握当前基于邻近性技术的离群点检测方法的研究现状，通过整理和归纳，将代表性强的基于邻近性的离群点检测方法进行了介绍和评价，将其主要分为基于距离的方法和基于密度的方法，对所有提及的方法的应用场景、算法思想、能解决的问题以及各自的优缺点进行了详细的分析和归纳，指出目前存在的问题和对未来研究的发展方向。对开展邻近性的离群点检测研究具有重要意义。

关键词: 邻近性, 离群点检测, 基于距离, 基于密度

LIU Caihui, LIU Dijin. Survey of Proximity Methods for Outlier Detection[J]. Computer Engineering and Applications, 2022, 58(21): 1-12.

刘财辉, 刘地金. 离群点检测的邻近性方法综述[J]. 计算机工程与应用, 2022, 58(21): 1-12.

References

[1] 黄彧.相似性度量的研究及其在数据挖掘中的应用[D].福州：福建师范大学，2009.
HUANG Y.Research on similarity measure and its application in data mining[D].Fuzhou：Fujian Normal University，2009.
[2] 刘凤，戴家佳，胡阳.基于局部密度离群点检测k-means算法[J].重庆工商大学学报（自然科学版），2021，38（4）：30-35.
LIU F，DAI J J，HU Y.The k-means algorithm based on local density outlier detection[J].Journal of Chongqing Technology ＆ Business University（Natural Science Edition），2021，38（4）：30-35.
[3] HAN J W，KAMBER M.数据挖掘：概念与技术[M].范明，孟小峰，译.3版.北京：机械工业出版社，2012：186-188.
HAN J W，KAMBER M.Data mining：concepts and techniques[M].FAN M，MENG X F.3rd ed.Beijing：China Machine Press，2012：186-188.
[4] 吴小燕，刘强，朱成璋.社交网络中协同舆论欺诈检测方法应用研究[J].郑州大学学报（工学版），2022，43（2）：7-14.
WU X Y，LIU Q，ZHU C Z.Research on application of collaborative public opinion fraud detection method in social network[J].Journal of Zhengzhou University（Engineering Science），2022，43（2）：7-14.
[5] 胡永健，王宇飞，刘琲贝，等.人脸欺诈检测最新进展及典型方法[J].信号处理，2021，37（12）：2261-2277.
HU Y J，WANG Y F，LIU B B，et al.A survey on the latest development and typical methods of face anti-spoofing[J].Journal of Signal Processing，2021，37（12）：2261-2277.
[6] 刘少钦，唐爽，赵俊峰，等.基于扩展主题模型的异常医疗处方检测方法[J].计算机科学与探索，2020，14（1）：30-39.
LIU S Q，TANG S，ZHAO J F，et al.Extended topic model based abnormal medical prescription detection method[J].Journal of Frontiers of Computer Science and Technology，2020，14（1）：30-39.
[7] 马子健.面向公共安全的异常检测关键技术研究[D].北京：北京交通大学，2021.
MA Z J.Research on key technology of anomaly detection for public security[D].Beijing：Beijing Jiaotong University，2021.
[8] 施珮，匡亮，唐玥，等.基于改进SVDD算法的池塘水质数据流异常检测[J].农业工程学报，2021，37（24）：249-256.
SHI P，KUANG L，TANG Y，et al.Abnormal detection of aquaculture water quality data stream using an improved SVDD in pond[J].Transactions of the Chinese Society of Agricultural Engineering，2021，37（24）：249-256.
[9] 吕承侃，沈飞，张正涛，等.图像异常检测研究现状综述[J].自动化学报，2022，48（6）：1402-1428.
LV C K，SHEN F，ZHANG Z T，et al.Review of image anomaly detection[J].Acta Automatica Sinica，2022，48（6）：1402-1428.
[10] 顾兆军，郭靖轩.基于角色异常行为挖掘的内部威胁检测方法[J].计算机工程与设计，2020，41（10）：2740-2746.
GU Z J，GUO J X.Internal threat detection method based on role abnormal behavior mining[J].Computer Engineering and Design，2020，41（10）：2740-2746.
[11] 李楠，孙伯鑫，樊瑞，等.基于多维特征的终端区异常轨迹实时检测[J].安全与环境学报，2022，22（1）：242-249.
LI N，SUN B X，FAN R，et al.Research on real-time detection ofabnormal trajectory in terminal area based on multidimensional features[J].Journal of Safety Environment，2022，22（1）：242-249.
[12] 梅林，张凤荔，高强.离群点检测技术综述[J].计算机应用研究，2020，37（12）：3521-3527.
MEI L，ZHANG F L，GAO Q.Overview of outlier detection technology[J].Application Research of Computers，2020，37（12）：3521-3527.
[13] 周玉，朱文豪，房倩，等.基于聚类的离群点检测方法研究综述[J].计算机工程与应用，2021，57（12）：37-45.
ZHOU Y，ZHU W H，FANG Q，et al.Survey of outlier detection methods based on clustering[J].Computer Engineering and Applications，2021，57（12）：37-45.
[14] DANG T T，NGAN H Y T，LIU W.Distance-based [k]-nearest neighbors outlier detection method in large-scale traffic data[C]//2015 IEEE International Conference on Digital Signal Processing，2015：507-510.
[15] KNORR E M，NG R T.Algorithms for mining distance based outliers in large data sets[C]//Proceedings of 24th International Conference on Very Large Databases，1998：392-403.
[16] YANG X，LATECKI L J，POKRAJAC D.Outlier detection with globally optimal exemplar-based GMM[C]//Proceedings of the SIAM International Conference on Data Mining（SDM），2009：145-154.
[17] SATMAN M H.A new algorithm for detecting outliers in linear regression[J].International Journal Statistics and Probability，2013，2（3）：101-109.
[18] RAMASWAMY S，RASTOGI R，KYUSEOK S.Efficient algorithms for mining outliers from large data sets[C]//Proceedings of ACM SIGMOD International Conference on Management Data，May 2000：427-438.
[19] KNORR E M，NG R T，TUCAKOV V.Distance-based outliers：algorithms and applications[J].The VLDB Journal，2000，8（3/4）：237-253.
[20] GHOTING A，PARTHASARATHY S，OTEY M E.Fast mining of distance-based outliers in high-dimensional datasets[J].Data Mining and Knowledge Discovery，2008，16（3）：349-364.
[21] ANGIULLI F，BASTA S，PIZZUTI C.Distance-based detection and prediction ofoutliers[J].IEEE Transactions on Knowledge Data Engineering，2006，18（2）：145-160.
[22] ZHANG K，HUTTER M，JIN H.A new local distance-based outlier detection approach for scattered real-world data[C]//Proceedings of Pacific-Asia Conference on Knowledge Discovery Data Mining，2009：813-822.
[23] 张戈，盖赟.局部离群因子算法（LOF）在异常检测中的应用研究[J].网络安全技术与应用，2020（11）：49-50.
ZHANG G，GAI Y.Research on the application of local outlier factor algorithm（LOF） in anomaly detection[J].Network Security Technology and Application，2020（11）：49-50.
[24] 程张玉.融合iForest和LOF的大规模多维数据离群点检测方法研究[D].武汉：武汉理工大学，2020.
CHENG Z Y.Research on iForest and LOF based outlier detection method for large-scale multidimensional data[D].Wuhan：Wuhan University of Technology，2020.
[25] LIU J，DENG H.Outlier detection on uncertain data based on local information[J].Knowledge Based Systems，2013，51：60-71.
[26] 张倩倩，于炯，李梓杨，等.基于近邻传播的离群点检测算法[J].计算机应用研究，2021，38（6）：1662-1667.
ZHANG Q Q，YU J，LI Z Y，et al.Outlier detection algorithm based on affinity propagation[J].Application Research of Computers，2021，38（6）：1662-1667.
[27] ANGIULLI F，BASTA S，PIZZUTI C.Distance-based detection and prediction of outliers[J].IEEE Transactions on Knowledge & Data Engineering，2005，18（2）：145-160.
[28] KRIEGEL H P，SCHUBERT M，ZIMEK A.Angle-based outlier detection in high-dimensional data[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2008：444-452.
[29] RADOVANOVI? M，NANOPOULOS A，IVANOVI? M.Reverse nearest neighbors in unsupervised distance-based outlier detection[J].IEEE Transactions on Knowledge Data Engineering，2015，27（5）：1369-1382.
[30] HUANG J，ZHU Q，YANG L，et al.A non-parameter outlier detection algorithm based on natural neighbor[J].Knowledge Based Systems，2016，92：71-77.
[31] HA J，SEOK S，LEE J S.A preciseranking method for outlier detection[J].Information Sciences：An International Journal，2015，324：88-107.
[32] TANG B，HE H.A local density-based approach for outlier detection[J].Neurocomputing，2017，241：171-180.
[33] 杨晓玲，冯山，袁钟.基于相对距离的反[k]近邻树离群点检测[J].电子学报，2020，48（5）：937-945.
YANG X L，FENG S，YUAN Z.Outlier detection based on reversed [k]-nearest neighborhood MST of relative distance measure[J].Acta Electronica Sinica，2020，48（5）：937-945.
[34] HUANG H，MEHROTRA K，MOHAN C K.Rank-based outlier detection[J].Journal of Statistical Computation Simulation，2013，83（3）：518-531.
[35] KRIEGEL H P，KR?GER P，SCHUBERT E，et al.Outlier detection in axis-parallel subspaces of high dimensional data[C]//Proceedings of Pacific-Asia Conference on Knowledge Discovery Data Mining.Berlin，Germany：Springer，2009：831-838.
[36] BHATTACHARYA G，GHOSH K，CHOWDHURY A S.Outlier detection using neighborhood rank difference[J].Pattern Recognition Letters，2015，60：24-31.
[37] WANG X，WANG X L，MA Y，et al.A fast MST-inspired kNN-based outlier detection method[J].Information Systems，2015，48：89-112.
[38] PANG G，CAO L，CHEN L，et al.Learning representations of ultrahigh-dimensional data for random distance-based outlier detection[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，2018：2041-2050.
[39] 姜高霞，樊瑞宣，王文剑.近邻感知的标签噪声过滤算法[J].模式识别与人工智能，2020，33（6）：518-529.
JIANG G X，FAN R X，WANG W J.Label noise filtering via perception of nearest neighbors[J].Pattern Recognition and Artificial Intelligence，2020，33（6）：518-529.
[40] BAY S，SCHWABACHER M.Mining distance-based outliers in near linear time with randomization and a simple pruningrule[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery Data Mining，Aug 2003：29-38.
[41] ANGIULLI F，FASSETTI F.Very efficient mining of distance-based outliers[C]//Proceedings of 16th ACM Conference on Information Knowledge Management，Nov 2007：791-800.
[42] REN D，RAHAL I，PERRIZO W，et al.A vertical distance-based outlier detectionmethod with local pruning[C]//Proceedings of 13th ACM CIKM International Conference on Information Knowledge Management，Nov 2004：279-284.
[43] VU N H，GOPALKRISHNAN V.Efficient pruning schemes for distance-based outlier detection[C]//Proceedings of European Conference on Machine Learning Knowledge Discovery Databases，2009：160-175.
[44] SHUKLA M，KOSTA Y P，CHAUHAN P.Analysis and evaluation of outlier detection algorithms in data streams[C]//Proceedings of IEEE International Conference on Computer，Communication and Control（IC4），Sep 2015：1-8.
[45] ANGIULLI F，FASSETTI F.Distance-based outlier queries in data streams：the novelt-ask and algorithms[J].Data Mining Knowledge Discovery，2010，20：290-324.
[46] AGGARWAL C C.On abnormality detection in spurious populated data streams[C]//Proceedings of SIAM International Conference on Data Mining，Apr 2005：80-91.
[47] SUBRAMANIAM S，PALPANAS T，PAPADOPOULOS D，et al.Online outlier detection in sensor data using nonparametric models[C]//Proceedings of International Conference on Very Large Data Bases，Sep 2006：187-198.
[48] YANG D，RUNDENSTEINER E A，WARD M.Neighbor-based pattern detection for windows over streaming data[C]//Proceedings of 12th International Conference on Extending Database Technology，Mar 2009：529-540.
[49] ZHANG J.Advancement of outlier detection：a survey[J].ICST Transactions on Scalable Information Systems，2013，13：1-26.
[50] KONTAKI M，GOUNARIS A，PAPADOPOULOS A N，et al.Continuous monitoring of distance-based outliers over data streams[C]//Proceedings of IEEE 27th International Conference on Data Engineering，Apr 2011：135-146.
[51] ANGIULLI F，FASSETTI F.Detecting distance-based outliers in streams of data[C]//Proceedings of 16th ACM Conference on Information Knowledge Management，Nov 2007：811-820.
[52] CAO L，YANG D，WANG Q，et al.Scalable distance-based outlier detection over high-volume data streams[C]//Proceedings of IEEE 30th International Conference on Data Engineering，Apr 2014：76-87.
[53] 江峰，杜军威，眭跃飞，等.基于边界和距离的离群点检测[J].电子学报，2010，38（3）：700-705.
JIANG F，DU J W，SUI Y F，et al.Outlier detection based on boundary and distance[J].Acta Electronica Sinica，2010，38（3）：700-705.
[54] JIANG F，SUI Y F，CAO C G.Outlier detection using rough set theory[C]//Proceedings of the 10th International Conference on Rough Sets Fuzzy Sets Data Mining and Granular Computing.Canada：Springer-Verlag，2005：79-87.
[55] 袁钟，冯山.基于邻域值差异度量的离群点检测算法[J].计算机应用，2018，38（7）：1905-1909.
YUAN Z，FENG S.Outlier detection algorithm based on neighborhood value difference metric[J].Journal of Computer Applications，2018，38（7）：1905-1909.
[56] AGGARWAL C C，YU P S.Outlier detection for high dimensional data[J].ACM SIGMOD Record，2001，30（2）：37-46.
[57] BHADURI K，MATHEWS B L，GIANNELLA C R.Algorithms for speeding up distance-based outlier detection[C]//Proceedings of ACM KDD Conference，Aug 2011：859-867.
[58] TRAN L，FAN L，SHAHABI C.Distance-based outlier detection in data streams[J].Proceedings of VLDB Endowment（PVLDB），2016，9（12）：1089-1100.
[59] BREUNIG M，KRIEGEL H，NG R T，et al.LOF：Identifying density-based local outliers[J].ACM SIGMOD Record，2000，29（2）：93-104.
[60] SCHUBERT E，ZIMEK A，KRIEGEL H P.Local outlier detection reconsidered：a generalized view on locality with applications to spatial，video，and network outlier detection[J].Data Mining Knowledge Discovery，2014，28（1）：190-237.
[61] TANG J，CHEN Z，FU A，et al.Enhancing effectiveness of outlier detections for low density patterns[C]//Advances in Knowledge Discovery and Data Mining.Berlin，Germany：Springer，2002：535-548.
[62] KRIEGEL H，KR?GER P，SCHUBERT E，et al.LoOP：local outlier probabilities[C]//Proceedings of 18th ACM Conference on Information Knowledge Management，2009：1649-1652.
[63] 李长镜，赵书良，池云仙.一种基于谱嵌入和局部密度的离群点检测算法[J].计算机科学，2019，46（3）：260-266.
LI C J，ZHAO S L，CHI Y X.Outlier detection algorithm based on spectral embedding and local density[J].Computer Science，2019，46（3）：260-266.
[64] MOMTAZ R，MOHSSEN N，GOWAYYED M A.DWOF：a robust density-based outlier detection approach[C]//Proceedings of Iberian Conference on Pattern Recognition Image Analysis，2013：517-525.
[65] FAN H，ZA?ANE O R，FOSS A，et al.Resolution-based outlier factor：detecting the top-n most outlying data points in engineering data[J].Knowledge Information Systems，2009，19（1）：31-51.
[66] PAPADIMITRIOU S，KITAGAWA H，GIBBONS P B，et al.LOCI：fast outlier detection using the local correlation integral[C]//Proceedings of 19th International Conference on Data Engineering，Mar 2003：315-326.
[67] REN D，WANG B，PERRIZO W.RDF：a density-based outlier detection method using vertical data representation[C]//Proceedings of International Conference on Data Mining，Nov 2004：503-506.
[68] 洪沙，林佳丽，张月良.基于密度的不确定数据离群点检测研究[J].计算机科学，2015，42（5）：230-233.
HONG S，LIN J L，ZHANG Y L.Density-based outlier detection on uncertain data[J].Computer Science，2015，42（5）：230-233.
[69] JIN W，TUNG A K，HAN J，et al.Ranking outliers using symmetric neighborhood relationship[C]//Proceedings of 10th Pacific-Asia Conference on Advance Knowledge Discovery Data Mining，2006：577-593.
[70] CAO K，SHI L，WANG G，et al.Density-based local outlier detection on uncertain data[C]//International Conference on Web-Age Information Management，2014.
[71] 邹云峰，张昕，宋世渊，等.基于局部密度的快速离群点检测算法[J].计算机应用，2017，37（10）：2932-2937.
ZOU Y F，ZHANG X，SONG S Y，et al.Fast outlier detection algorithm based on local density[J].Journal of Computer Applications，2017，37（10）：2932-2937.
[72] KELLER F，MüLLER E，BOHM K.HiCS：high contrast subspaces for density-based outlier ranking[C]//Proceedings of IEEE 28th International Conference on Data Engineering（ICDE），Apr 2012：1037-1048.
[73] BANDARAGODA T.Efficient anomaly detection by isolation using nearest neighbour ensemble[C]//Proceedings of the 2014 IEEE International Conference on Data Mining Workshop，2014：698-705.
[74] PANG G S，KAI M T，ALBRECHT D.LeSiNN：detecting anomalies by identifying least similar nearest neighbours[C]//Proceedings of the 2015 IEEE International Conference on Data Mining Workshop（ICDMW’15），2015：623-630.
[75] CAMPELLO R J G B，MOULAVI D，ZIMEK A，et al.Hierarchical density estimates for data clustering，visualization，and outlier detection[J].ACM Transactions on Knowledge Discovery Data（TKDD），2015，10（1）.
[76] WU K，ZHANG K，FAN W，et al.RS-forest：a rapid density estimator for streaming anomaly detection[C]//Proceedings of IEEE International Conference on Data Mining，Dec 2014：600-609.
[77] BAI M，WANG X，XIN J，et al.An efficient algorithm for distributed density-based outlier detection on big data[J].Neurocomputing，2016，181：19-28.
[78] LOZANO E，ACUFIA E.Parallel algorithms for distance-based anddensity-based outliers[C]//Proceedings of 5th IEEE International Conference on Data Mining，Nov 2005：729-732.
[79] 黄添强，李凯，郭躬德.基于局部相关维度的流形离群点检测算法[J].模式识别与人工智能，2011，24（5）：629-636.
HUANG T Q，LI K，GUO G D.Manifold outlier detection algorithm based on local-correlation dimension[J].Pattern Recognition and Artificial Intelligence，2011，24（5）：629-636.
[80] NA G S，KIM D，YU H.Dilof：effective and memory efficient local outlier detection in data streams[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，2018：1993-2002.
[81] QIN X，RUNDENSTEINER E.Scalable kernel density estimation-based local outlier detection over large data streams[C]//Proceedings of the 22nd International Conference on Extending Database Technology（EDBT），2019.
[82] 毛亚琼，田立勤，王艳，等.引入局部向量点积密度的数据流离群点快速检测算法[J].计算机工程，2020，46（11）：132-138.
MAO Y Q，TIAN L Q，WANG Y，et al.Fast outlier detection algorithm in data stream with local density of vector dot product[J].Computer Engineering，2020，46（11）：132-138.
[83] VáZQUEZ F I，ZSEBY T，ZIMEK A.Outlier detection based on low density models[C]//Proceedings of ICDM Workshops，2018：970-979.
[84] NING J，CHEN L，CHEN J.Relative density-based outlier detection algorithm[C]//Proceedings of CSAI/ICIMT，Dec 2018：227-231.
[85] SU S，XIAO L，RUAN L，et al.An efficient density-based local outlier detection approach for scattered data[J].IEEE Access，2019，7：1006-1020.
[86] 金利娜，于炯，杜旭升，等.基于生成对抗网络和变分自编码器的离群点检测算法[J].计算机应用研究，2022，39（3）：774-779.
JIN L N，YU J，DU X S，et al.Generative adversarial network and variational auto-encoder based outlier detection[J].Application Research of Computers，2022，39（3）：774-779.
[87] 王晓辉，宋学坤，王晓川.基于邻域密度的异构数据局部离群点挖掘算法[J].计算机仿真，2021，38（7）：281-285.
WANG X H，SONG X K，WANG X C.Local outlier mining algorithmfor heterogeneous data based on neigh-borhood density[J].Computer Simulation，2021，38（7）：281-285.
[88] 杜旭升，于炯，陈嘉颖，等.一种基于邻域系统密度差异度量的离群点检测算法[J].计算机应用研究，2020，37（7）：1969-1973.
DU X S，YU J，CHEN J Y，et al.Outlier detection algorithm based on neighborhood system density difference measurement[J].Application Research of Computer，2020，37（7）：1969-1973.
[89] 王敬华，金鹏.基于粗约简和网格的离群点检测[J].计算机工程与应用，2015，51（3）：133-137.
WANG J H，JIN P.Outlier detection based on rough reduction and grid[J].Computer Engineering and Applications，2015，51（3）：133-137.
[90] 邓廷权，刘金艳，王宁.高维数据离群点检测的局部线性嵌入方法[J].计算机工程与应用，2018，54（6）：115-122.
DENG T Q，LIU J Y，WANG N.Locally linear embedding method for high dimensional data outlier detection[J].Computer Engineering and Applications，2018，54（6）：115-122.
[91] BARNETT V，LEWIS T.Outliers in statistical data[M].Hoboken，NJ，USA：Wiley，1994.
[92] WANG W，YANG J，MUNTZ R.STING：a statistical information grid approach to spatial data mining[C]//Proceedings of 23rd VLDB Conference，Aug 1997：186-195.
[93] 林雪.海量不确定数据集中离群点快速检测方法仿真[J].计算机仿真，2021，38（6）：378-382.
LIN X.Simulation of quick detection method for outliers in massive uncertain data sets[J].Computer Simulation，2021，38（6）：378-382.
[94] HIDO S，TSUBOI Y，KASHIMA H，et al.Statistical outlier detection using direct density ratioestimation[J].Knowledge Infarmation Systems，2011，26（2）：309-336.