不确定数据流上的离群点检测处理

朱斌　钟毓灵　王习特　白梅

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

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

中图分类号：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]. 数据的不确定性主要分为属性级不确定与存在级不确定，本文主要关注存在级不确定数据[5]. 目前，传统的离群点检测算法尚无法满足诸多现实需求， 以气象监测系统为例，传感器不间断地采集局部气温、气压和紫外线指数等环境信息并以流的形式传输到数据库中，实时识别出离群点（异常气象信息），可以有效地防范自然灾害. 但是，受到传感器精度及周围环境等因素影响，产生的数据流具有流速较快、规模较大及不确定性等数据特点，使得传统解决方案无法直接应用到上述问题中[5]. 因此，设计出一种高效的不确定数据流上的离群点检测算法成为本文的主要研究目标.

文献[6]首次给出了存在级不确定数据中的离群点定义，并提出了DPA算法用以解决集中式环境中的离群点检测问题. 随后，文献[7]在文献[6]的基础上将研究内容扩展至不确定数据流环境中，利用网格索引结构管理不确定数据，并采用动态规划思想来求解离群概率值用以避免可能世界的空间膨胀. 但因该算法在批量过滤时不可避免地需要近邻空间的查询，这就使得在处理多维数据时具有一定的局限性，另外，由于其忽略了離群概率值求解的递推规律，使其在概率值求解中也无法避免冗余计算. 文献[8]也关注于该研究问题并提出了PCUOD算法，该算法通过估算数据点的离群概率范围进行概率剪枝，从而减少了必要的计算成本. 但是，由于PCUOD算法中的界限估算方法在近邻数目急剧增加时会产生失效的情况，从而也造成了一定的局限性. 总之，目前相关解决方案中仍存在诸多不足，无法高效地满足现实应用的需求.

本文主要研究快速不确定数据流上的离群点检测算法（Fast Outlier Detection algorithm Over Uncertain Data Streams，FOD_OUDS），旨在提高算法的执行效率. 主要贡献包括以下几个部分：

1）采用分层次划分思想给出了不确定数据流环境中索引的构建方法，利用这种索引结构可以克服传统索引对多维数据管理的局限性. 与此同时，本文通过对索引结构中的叶子子块增加部分存储信息，可以快速地完成新到达数据点的批量过滤，极大地减少了数据更新过程中的计算代价.

2）通过深入分析离群概率值求解的递推规律

后，提出了一种新的离群概率值求解方法. 该方法尽最大可能地避免了全近邻集合的迭代计算，从而极大地减少了冗余计算.

3）利用大量的对比实验，验证本文所提出的

FOD_OUDS算法的有效性.

1   不确定数据流离群点检测算法

1.1   問题描述

本文主要研究不确定数据流环境中基于距离的离群点检测问题. 首先，给出不确定数据流中基于距离的离群点定义;然后，简要描述在基于计数的滑动窗口上的处理流程. 表1列出了本文使用的符号及其含义.

综上所述，FOD_OUDS算法在针对不确定数据流环境中的离群点检测问题上的检测时间更短并且过滤性能更优，从而验证了本文提出的FOD_OUDS算法的有效性与高效性.

3   结   论

本文针对不确定数据流环境中的离群点查询问题，提出了FOD_OUDS算法. 首先，采用分层次划分思想给出了索引构建策略，使其具备良好的过滤性能. 然后，在分析了不确定数据点的离群概率值求解的递推规律后，提出了优先过滤非离群点的概率值求解方法，从而加快了过滤速度. 其次，给出了动态维护的更新方法，以减少更新过程中的必要计算代价，从而提高了算法的运算效率. 最后，通过实验验证了FOD_OUDS算法具有较高的查询效率与较好的过滤性能.

参考文献

[1]    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. Paris，France：IEEE，2018：1232—1235.

[2]    HAWKINS D M. Identification of outliers[J]. Biometrics，1981，37（4）：27—41.

[3]   KNORR E M，NG R T. Algorithms for mining distance-based outliers in large datasets[C]// Proceedings of the 24th International Conference on Very Large Data Bases. New York：Springer，1998：392—403.

[4]    吴杰，衣枚玉，张金辉，等. 大数据下的结构性态监测信息管理系统设计与应用[J]. 湖南大学学报（自然科学版），2016，43（9）：76—81.

WU J，YI M Y，ZHANG J H，et al. Design and application of an information management system for structural behavior monitoring based on big data technology[J]. Journal of Hunan University（Natural Sciences），2016，43（9）：76—81.（In Chinese）

[5]    周傲英，金澈清，王国仁，等. 不确定性数据管理技术研究综述[J]. 计算机学报，2009，32（1）：1—16.

ZHOU A Y，JIN C Q，WANG G R，et al. A survey on the management of uncertain data[J]. Chinese Journal of Computers，2009，32（1）：1—16. （In Chinese）

[6]    YU H，WANG B，XIAO G，et al. Distance-based outlier detection on uncertain data[J]. Journal of Computer Research and Development，2010，47（3）：474—484.

[7]    WANG B，YANG X C，WANG G R，et al. Outlier detection over sliding windows for probabilistic data streams[J]. Journal of Computer Science and Technology，2010，25（3）：389—400.

[8]   CAO K Y，WANG G R，HAN D H，et al. Continuous outlier monitoring on uncertain data streams[J]. Journal of Computer Science & Technology，2014，29（3）：436—448.

[9]    钟毓灵，王习特，白梅，等. FODU：不确定数据集中快速离群点检测方法[J]. 计算机工程与应用，2019，55（19）：105—114

ZHONG Y L，WANG X T，BAI M，et al. FODU：A fast outlier detection approach on uncertain data sets[J]. Computer Engineering and Applications，2019，55（19）：105—114. （In