朱斌　钟毓灵　王习特　白梅

摘   要：提出了一种快速不确定数据流上的离群点检测算法. 采用分层次划分思想给出了适用于流式数据的索引构建方法，并为索引结构中的叶子结点增加了部分存储信息，使得在数据更新时新流入的数据点可以利用中间结果信息直接完成批量过滤，降低计算成本. 通过分析离群概率值求解的递推规律，给出了一种全新的离群概率值求解方案，该方案可以最大可能地避免全近邻集合的迭代计算，减少了大量的非离群点计算代价，从而加快处理速度. 实验结果表明，快速不确定数据流上的离群点检测算法能够有效地提高检测效率.

关键词：离群点;不确定数据流;滑动窗口;过滤策略;分层次划分

中图分类号：TP391                                 文献标志码：A

Abstract：This paper proposed a Fast Outlier Detection algorithm Over Uncertain Data Streams （FOD_OUDS）. Firstly，an index inspired by hierarchical ideas was designed to manage uncertain data stream，and some storage information was added for the leaf nodes in the index structure，so that the newly inflowed data points can directly perform batch filtering by using the intermediate result information when the data is updated，thereby achieving the purpose of reducing the calculation cost. Secondly，by analyzing the recursive rules of outlier probability values in calculation，a novel outlier probability value solution scheme was presented，which can avoid as much as possible the calculating cost of nearest neighbor set，reduce the processing cost of a large number of inliers，thus speeding up processing. At last，a large amount of experiments show that the FOD_OUDS algorithm can effectively improve the detection efficiency.

Key words：outliers;probabilistic data stream;sliding window;filtering strategy;hierarchical division

离群点检测是数据管理领域的热点问题之一[1]， 广泛应用于工业损毁、金融诈骗和环境监测等应用场景中，离群点被认为是数据集合中显著区分于其他数据点的数据对象[2]. 目前，因为基于距离的离群点定义[3]能够直观反映离群点本质而得到广泛的应用，其具体描述为：对于数据集合中任意数据点p，若p在半径r范围内的邻居个数少于k个，那么p被认为是离群点.

近年来，数据以高速度高容量的流式形式应用于工业生产、社会生活中，在这规模庞大、速度极快的流式数据里面，不确定性数据广泛存在于其中[4]. 数据的不确定性主要分为属性级不确定与存在级不确定，本文主要关注……