面向流数据的θ-近似离群点检测算法

θ-Approximate Outlier Detection Algorithm over Data Stream

摘要

针对高速流数据环境下基于距离的离群点检测很难在有效时间内完成实时处理的问题,提出一种面向流数据的θ-近似离群点检测算法.该算法以对象分布的局部均匀性为基础,通过构建局部均匀分布概要结构,识别并维护满足近似均匀分布特征的区域节点,从而利用查询对象与这些区域节点之间的位置关系估计其邻居数量,并在概率误差保证下判断对象的离群状态.与传统方法需要频繁执行精确范围查询不同,该算法优先通过概率保证下的邻居数量估计完成对象状态判定,仅在必要情况下执行精确邻居计算,从而降低范围查询和距离计算开销.在真实数据集和合成数据集上的实验结果表明:该算法能在保持较好检测准确率的同时显著减少处理时间;利用局部分布特征进行概率近似判断,可有效提升高速流数据环境下离群点检测的实时处理能力,为大规模流数据管理与分析提供一种兼具效率和质量保证的解决方案.

Abstract

Aiming at the problem that it was difficult to achieve real time processing of distance-based outlier detection in high speed data stream environments within an effective time, we proposed a θ-approximate outlier detection algorithm over data stream. The algorithm was based on the local uniformity of object distributions. It constructed a summary structure of local uniform distribution to identify and maintain regional nodes that satisfied approximate uniform distribution characteristics. By using the positional relationship between the query object and these regional nodes, it estimated the number of neighbors and determined the outlier state of the object under the guarantee of probability error. Unlike traditional methods that required frequent execution of precise range queries, the algorithm prioritized object state determination through estimating the number of neighbors under probability guarantee, and only performed exact neighbor computation when necessary, thereby reducing the cost of range queries and distance calculations. The experimental results on real and synthetic datasets show that the proposed algorithm can significantly reduce processing time while maintaining good detection accuracy. The use of local distribution characteristics for probabilistic approximation judgment can effectively improve the real time processing capability of outlier detection in high-speed data stream environments, providing an efficient and quality guaranteed solution for large-scale data stream management and analysis.

关键词

基于距离的离群点检测 / 流数据 / 概率误差 / 局部均匀分布

Key words

distance-based outlier detection / data stream / probability error / local uniform distribution

参考文献

[1] Bhatia S, Liu R, Hooi B, et al. Real-Time Anomaly Detection in Edge Streams[J]. ACM Transactions on Knowledge Discovery from Data, 2022, 16(4): 75-1-75-22.

[2] Chai C L, Cao L, Li G L, et al. Human-in-the-Loop Outlier Detection[C]// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2020: 19-33.

[3] Su Y X, Song S X, Huang X D, et al. Distance-Based Outlier Query Optimization in Apache IoTDB[J]. Proceedings of the VLDB Endowment, 2024, 17(11): 2778-2790.

[4] Zhang S, Ursekar V, Akoglu L, et al. Sparx: Distributed Outlier Detection at Scale[C]// Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2022: 4530-4540.

[5] Lakshmi R, Sajesh T A. A Robust Distance-Based Approach for Detecting Multidimensional Outliers[J]. Journal of Applied Statistics, 2025, 52(6): 1278-1298.

[6] Boukerche A, Zheng L N, Alfandi O. Outlier Detection: Methods, Models, and Classification[J]. ACM Computing Surveys, 2020, 53(3): 55-1-55-37.

[7] Yoon S, Shin Y, Lee J G, et al. Multiple Dynamic Outlier-Detection from a Data Stream by Exploiting Duality of Data and Queries[C]// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2021: 2063-2075.

[8] Amagata D, Onizuka M, Hara T. Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-Based Approach[C]// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2021: 36-48.

[9] Sadik S, Gruenwald L, Leal E. Wadjet: Finding Outliers in Multiple Multi-dimensional Heterogeneous Data Streams[C]// 2018 IEEE 34th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2018: 1232-1235.

[10] Breitenbacher D, Homoliak I, Aung Y L, et al. Hades-IoT: A Practical Host-Based Anomaly Detection System for IoT Devices[C]// Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security. New York: ACM, 2019: 479-484.

[11] Cao L, Yang D, Wang Q Y, et al. Scalable Distance-Based Outlier Detection over High-Volume Data Streams[C]// 2014 IEEE 30th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2014: 76-87.

[12] Tran L, Mun M Y, Shahabi C, et al. Real-Time Distance-Based Outlier Detection in Data Streams[J]. Proceedings of the VLDB Endowment, 2020, 14(2): 141-153.

[13] Yoon S, Lee J G, Lee B S, et al. NETS: Extremely Fast Outlier Detection from a Data Stream via Set-Based Processing[J]. Proceedings of the VLDB Endowment, 2019, 12(11): 1303-1315.

[14] Angiulli F, Fassetti F. Detecting Distance-Based Outliers in Streams of Data[C]// Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management. New York: ACM, 2007: 811-820.

[15] Yang D, Rundensteiner E A, Ward M O, et al. Neighbor-Based Pattern Detection for Windows over Streaming Data[C]// Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. New York: ACM, 2009: 529-540.

[16] Zhu R, Wang B, Yang X C, et al. Closest Pairs Search over Data Stream[J]. Proceedings of the ACM on Management of Data, 2023, 1(3): 205-1-205-26.

[17] Kontaki M, Gounaris A, Papadopoulos A N, et al. Continuous Monitoring of Distance-Based Outliers over Data Streams[C]// 2011 IEEE 27th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2011: 135-146.

[18] Tran L, Fan L, Shahabi C, et al. Fast Distance-Based Outlier Detection in Data Streams Based on Micro Clusters[C]// Proceedings of the 10th International Symposium on Information and Communication Technology. New York: ACM, 2019: 162-169.

[19] Zhu R, Yu T T, Tan Z Y, et al. PTAOD: A Novel Framework for Supporting Approximate Outlier Detection over Streaming Data for Edge Computing[J]. IEEE Access, 2019, 8: 1475-1485.

[20] Zhu R, Ji X L, Yu D Y, et al. KNN-Based Approximate Outlier Detection Algorithm over IoT Streaming Data[J]. IEEE Access, 2020, 8: 42749-42759.

[21] Bhattacharjee P, Garg A, Mitra P, et al. KAGO: An Approximate Adaptive Grid-Based Outlier Detection Approach Using Kernel Density Estimate[J]. Pattern Analysis and Applications, 2021, 24(4): 1825-1846.

基金资助

国家自然科学基金(62472293)