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

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

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

中圖分類號(hào)：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(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

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

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

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

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

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

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

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

3）利用大量的對(duì)比實(shí)驗(yàn)，驗(yàn)證本文所提出的

FOD_OUDS算法的有效性.

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

1.1? ?問題描述

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

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

3? ?結(jié)? ?論

本文針對(duì)不確定數(shù)據(jù)流環(huán)境中的離群點(diǎn)查詢問題，提出了FOD_OUDS算法. 首先，采用分層次劃分思想給出了索引構(gòu)建策略，使其具備良好的過濾性能. 然后，在分析了不確定數(shù)據(jù)點(diǎn)的離群概率值求解的遞推規(guī)律后，提出了優(yōu)先過濾非離群點(diǎn)的概率值求解方法，從而加快了過濾速度. 其次，給出了動(dòng)態(tài)維護(hù)的更新方法，以減少更新過程中的必要計(jì)算代價(jià)，從而提高了算法的運(yùn)算效率. 最后，通過實(shí)驗(yàn)驗(yàn)證了FOD_OUDS算法具有較高的查詢效率與較好的過濾性能.

參考文獻(xiàn)

[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)測(cè)信息管理系統(tǒng)設(shè)計(jì)與應(yīng)用[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(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]? ? 周傲英，金澈清，王國(guó)仁，等. 不確定性數(shù)據(jù)管理技術(shù)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào)，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ù)集中快速離群點(diǎn)檢測(cè)方法[J]. 計(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