Outlier Detection over Sliding Windows for Probabilistic Data Streams
Outlier Detection over Sliding Windows for Probabilistic Data Streams
复制标题
概率数据流滑动窗口的异常值检测
DOI：
10.1007/s11390-010-9332-2
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
Bin Wang, Xiaochun Yang, Guoren Wang, Ge Yu
中科院分区：
文献类型：
--
作者：
Bin Wang, Xiaochun Yang, Guoren Wang, Ge Yu
在许多应用中，异常值检测是一种非常有用的技术，在这些应用中，数据通常是不确定的，可以用概率来描述。虽然在确定性数据领域已经得到了深入的研究，但在新兴的不确定数据领域，离群值检测仍然是一个新的领域。本文研究了概率数据流中离群点检测的语义，提出了基于距离的滑动窗口离群点的新定义。然后，我们证明了在一组可能世界实例中检测异常值的问题等价于在其邻域中找到第k个元素的问题。在此基础上，提出了一种动态规划算法（DPA）来降低mo (2|R(e; d)|) toO（|k·R(e; d)|）的检测成本，其中（e; d）为e的邻域。此外，我们提出了一种基于剪枝的方法（PBA）来有效地过滤单窗口的非异常值，并动态地增量检测最近元素。最后，详细的分析和全面的实验结果证明了该方法的有效性和可扩展性。
Outlier detection is a very useful technique in many applications, where data is generally uncertain and could be described using probability. While having been studied intensively in the field of deterministic data, outlier detection is still novel in the emerging uncertain data field. In this paper, we study the semantic of outlier detection on probabilistic data stream and present a new definition of distance-based outlier over sliding window. We then show the problem of detecting an outlier over a set of possible world instances is equivalent to the problem of finding thek-th element in its neighborhood. Based on this observation, a dynamic programming algorithm (DPA) is proposed to reduce the detection cost fromO(2|R(e; d)|) toO(|k·R(e; d)|), whereR(e; d) is thed-neighborhood ofe. Furthermore, we propose a pruning-based approach (PBA) to effectively and efficiently filter non-outliers on single window, and dynamically detect recentmelements incrementally. Finally, detailed analysis and thorough experimental results demonstrate the efficiency and scalability of our approach.
登录
查看更多内容
DOI：
10.1109/icde.2008.4497423
发表时间：
2008-04
期刊：
2008 IEEE 24th International Conference on Data Engineering
影响因子：
--
作者：
C. Aggarwal;Philip S. Yu
通讯作者：
C. Aggarwal;Philip S. Yu
DOI：
10.1145/1081870.1081955
发表时间：
2005-08
期刊：
--
影响因子：
--
作者：
H. Kriegel;M. Pfeifle
通讯作者：
H. Kriegel;M. Pfeifle
DOI：
--
发表时间：
1998-08
期刊：
--
影响因子：
--
作者：
Edwin M. Knorr;R. Ng
通讯作者：
Edwin M. Knorr;R. Ng
DOI：
10.1109/icde.2005.137
发表时间：
2005-04
期刊：
21st International Conference on Data Engineering (ICDE'05)
影响因子：
--
作者：
Xuemin Lin;Yidong Yuan;Wei Wang-;Hongjun Lu
通讯作者：
Xuemin Lin;Yidong Yuan;Wei Wang-;Hongjun Lu
DOI：
10.1007/bfb0100984
发表时间：
1998-03
期刊：
--
影响因子：
--
作者：
Sunita Sarawagi;R. Agrawal;N. Megiddo
通讯作者：
Sunita Sarawagi;R. Agrawal;N. Megiddo