朱斌　鐘毓靈　王習(xí)特　白梅

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

關(guān)鍵詞：離群點;不確定數(shù)據(jù)流;滑動窗口;過濾策略;分層次劃分

中圖分類號：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標(biāo)志碼：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

離群點檢測是數(shù)據(jù)管理領(lǐng)域的熱點問題之一[1]， 廣泛應(yīng)用于工業(yè)損毀、金融詐騙和環(huán)境監(jiān)測等應(yīng)用場景中，離群點被認(rèn)為是數(shù)據(jù)集合中顯著區(qū)分于其他數(shù)據(jù)點的數(shù)據(jù)對象[2]. 目前，因為基于距離的離群點定義[3]能夠直觀反映離群點本質(zhì)而得到廣泛的應(yīng)用，其具體描述為：對于數(shù)據(jù)集合中任意數(shù)據(jù)點p，若p在半徑r范圍內(nèi)的鄰居個數(shù)少于k個，那么p被認(rèn)為是離群點.

近年來，數(shù)據(jù)以高速度高容量的流式形式應(yīng)用于工業(yè)生產(chǎn)、社會生活中，在這規(guī)模龐大、速度極快的流式數(shù)據(jù)里面，不確定性數(shù)據(jù)廣泛存在于其中[4]. 數(shù)據(jù)的不確定性主要分為屬性級不確定與存在級不確定，本文主要關(guān)注存在級不確定數(shù)據(jù)[5]. 目前，傳統(tǒng)的離群點檢測算法尚無法滿足諸多現(xiàn)實需求， 以氣象監(jiān)測系統(tǒng)為例，傳感器不間斷地采集局部氣溫、氣壓和紫外線指數(shù)等環(huán)境信息并以流的形式傳輸?shù)綌?shù)據(jù)庫中，實時識別出離群點（異常氣象信息），可以有效地防范自然災(zāi)害. 但是，受到傳感器精度及周圍環(huán)境等因素影響，產(chǎn)生的數(shù)據(jù)流具有流速較快、規(guī)模較大及不確定性等數(shù)據(jù)特點，使得傳統(tǒng)解決方案無法直接應(yīng)用到上述問題中[5]. 因此，設(shè)計出一種高效的不確定數(shù)據(jù)流上的離群點檢測算法成為本文的主要研究目標(biāo).

文獻[6]首次給出了存在級不確定數(shù)據(jù)中的離群點定義，并提出了DPA算法用以解決集中式環(huán)境中的離群點檢測問題. 隨后，文獻[7]在文獻[6]的基礎(chǔ)上將研究內(nèi)容擴展至不確定數(shù)據(jù)流環(huán)境中，利用網(wǎng)格索引結(jié)構(gòu)管理不確定數(shù)據(jù)，并采用動態(tài)規(guī)劃思想來求解離群概率值用以避免可能世界的空間膨脹. 但因該算法在批量過濾時不可避免地需要近鄰空間的查詢，這就使得在處理多維數(shù)據(jù)時具有一定的局限性，另外，由于其忽略了離群概率值求解的遞推規(guī)律，使其在概率值求解中也無法避免冗余計算. 文獻[8]也關(guān)注于該研究問題并提出了PCUOD算法，該算法通過估算數(shù)據(jù)點的離群概率范圍進行概率剪枝，從而減少了必要的計算成本. 但是，由于PCUOD算法中的界限估算方法在近鄰數(shù)目急劇增加時會產(chǎn)生失效的情況，從而也造成了一定的局限性. 總之，目前相關(guān)解決方案中仍存在諸多不足，無法高效地滿足現(xiàn)實應(yīng)用的需求.

本文主要研究快速不確定數(shù)據(jù)流上的離群點檢測算法（Fast Outlier Detection algorithm Over Uncertain Data Streams，F(xiàn)OD_OUDS），旨在提高算法的執(zhí)行效率. 主要貢獻包括以下幾個部分：

1）采用分層次劃分思想給出了不確定數(shù)據(jù)流環(huán)境中索引的構(gòu)建方法，利用這種索引結(jié)構(gòu)可以克服傳統(tǒng)索引對多維數(shù)據(jù)管理的局限性. 與此同時，本文通過對索引結(jié)構(gòu)中的葉子子塊增加部分存儲信息，可以快速地完成新到達數(shù)據(jù)點的批量過濾，極大地減少了數(shù)據(jù)更新過程中的計算代價.

2）通過深入分析離群概率值求解的遞推規(guī)律

后，提出了一種新的離群概率值求解方法. 該方法盡最大可能地避免了全近鄰集合的迭代計算，從而極大地減少了冗余計算.

3）利用大量的對比實驗，驗證本文所提出的

FOD_OUDS算法的有效性.

1? ?不確定數(shù)據(jù)流離群點檢測算法

1.1? ?問題描述

本文主要研究不確定數(shù)據(jù)流環(huán)境中基于距離的離群點檢測問題. 首先，給出不確定數(shù)據(jù)流中基于距離的離群點定義;然后，簡要描述在基于計數(shù)的滑動窗口上的處理流程. 表1列出了本文使用的符號及其含義.

綜上所述，F(xiàn)OD_OUDS算法在針對不確定數(shù)據(jù)流環(huán)境中的離群點檢測問題上的檢測時間更短并且過濾性能更優(yōu)，從而驗證了本文提出的FOD_OUDS算法的有效性與高效性.

3? ?結(jié)? ?論

本文針對不確定數(shù)據(jù)流環(huán)境中的離群點查詢問題，提出了FOD_OUDS算法. 首先，采用分層次劃分思想給出了索引構(gòu)建策略，使其具備良好的過濾性能. 然后，在分析了不確定數(shù)據(jù)點的離群概率值求解的遞推規(guī)律后，提出了優(yōu)先過濾非離群點的概率值求解方法，從而加快了過濾速度. 其次，給出了動態(tài)維護的更新方法，以減少更新過程中的必要計算代價，從而提高了算法的運算效率. 最后，通過實驗驗證了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，F(xiàn)rance：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]? ? 吳杰，衣枚玉，張金輝，等. 大數(shù)據(jù)下的結(jié)構(gòu)性態(tài)監(jiān)測信息管理系統(tǒng)設(shè)計與應(yīng)用[J]. 湖南大學(xué)學(xué)報（自然科學(xué)版），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]? ? 周傲英，金澈清，王國仁，等. 不確定性數(shù)據(jù)管理技術(shù)研究綜述[J]. 計算機學(xué)報，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]? ? 鐘毓靈，王習(xí)特，白梅，等. FODU：不確定數(shù)據(jù)集中快速離群點檢測方法[J]. 計算機工程與應(yīng)用，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