不確定數據流上的離群點檢測處理

朱斌　鐘毓靈　王習特　白梅

摘? ?要：提出了一種快速不確定數據流上的離群點檢測算法. 采用分層次劃分思想給出了適用于流式數據的索引構建方法，并為索引結構中的葉子結點增加了部分存儲信息，使得在數據更新時新流入的數據點可以利用中間結果信息直接完成批量過濾，降低計算成本. 通過分析離群概率值求解的遞推規律，給出了一種全新的離群概率值求解方案，該方案可以最大可能地避免全近鄰集合的迭代計算，減少了大量的非離群點計算代價，從而加快處理速度. 實驗結果表明，快速不確定數據流上的離群點檢測算法能夠有效地提高檢測效率.

關鍵詞：離群點;不確定數據流;滑動窗口;過濾策略;分層次劃分

中圖分類號：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