不確定數(shù)據(jù)流上的離群點(diǎn)檢測處理

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

（大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧大連116026）

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

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

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

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

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

2）通過深入分析離群概率值求解的遞推規(guī)律后，提出了一種新的離群概率值求解方法.該方法盡最大可能地避免了全近鄰集合的迭代計算，從而極大地減少了冗余計算.

3）利用大量的對比實(shí)驗(yàn)，驗(yàn)證本文所提出的FOD_OUDS算法的有效性.

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

1.1 問題描述

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

表1 符號列表Tab.1 List of symbols

DS表示具有d維屬性的不確定數(shù)據(jù)流，在DS中任意數(shù)據(jù)點(diǎn)p都有一個存在概率P（p）（0

定義1（r-近鄰）給定數(shù)據(jù)集P和查詢半徑r，點(diǎn)p在P內(nèi)的近鄰集合是p在r范圍內(nèi)包含的所有點(diǎn)的集合，即N（P，p）={p′|p′∈P，dist（p，p′）＜r}.

定義2（（r，k）-離群點(diǎn)）給定數(shù)據(jù)集P和查詢鄰居個數(shù)k，若點(diǎn)p是P內(nèi)的（r，k）-離群點(diǎn)，則p在半徑r范圍內(nèi)的鄰居個數(shù)小于k，即

在數(shù)據(jù)集P中每個可能世界W都是P的子集.W的存在概率為：

定義3（Threshold-離群點(diǎn)）給定查詢閾值Threshold，若點(diǎn)p的離群概率POutlier（p）＞Threshold，那么p是Threshold-離群點(diǎn).

可知，所有滿足定義3的點(diǎn)組成了數(shù)據(jù)集P中的離群集合Outlier（P）={p|p∈P，POutlier（p）＞Threshold}.

在不確定數(shù)據(jù)流DS上，采用基于計數(shù)的滑動窗口模型管理數(shù)據(jù)，嚴(yán)格按照數(shù)據(jù)點(diǎn)p到達(dá)窗口的先后次序標(biāo)記p的時間戳p.label.當(dāng)窗口大小是S時，窗口內(nèi)的數(shù)據(jù)集記作DSS，窗口內(nèi)的點(diǎn)的生存周期是[p.label，p.label+S].同時，窗口中保存且僅保存最近到達(dá)的S個數(shù)據(jù)點(diǎn)，因此每當(dāng)窗口中擴(kuò)充一個新的點(diǎn)pnew時將對應(yīng)一個舊的點(diǎn)pold消失.

具體描述為，滑動窗口中的不確定離群點(diǎn)查詢就是返回當(dāng)前窗口中所有離群概率大于閾值的數(shù)據(jù)點(diǎn)的集合，就是Outlier（DSS）={p|p∈DSS，POutlier（p）＞Threshold}.

例1圖1（a）（b）分別給出了當(dāng)前時刻與下一時刻滑動窗口內(nèi)的數(shù)據(jù)點(diǎn)集，圖1（c）給出了每個點(diǎn)的存在概率.假設(shè)窗口大小S=5，查詢半徑r=3，查詢鄰居個數(shù)k=3和查詢閾值Threshold=0.6，數(shù)據(jù)點(diǎn)按照p1～p6的次序到達(dá).以點(diǎn)p2為例，根據(jù)上述定義，當(dāng)前時刻p2的離群概率POutlier（p2）≈0.63，可知p2是離群點(diǎn).下一時刻，隨著窗口的滑動點(diǎn)p6到達(dá)而點(diǎn)p1消失，p2的離群概率變?yōu)镻Outlier（p2）≈0.42，可知，隨著窗口的滑動，下一時刻p2將變?yōu)榉请x群點(diǎn).

圖1 處理流程示例Fig.1 The example of process flow

1.2 不確定數(shù)據(jù)流上的離群點(diǎn)檢測處理

首先，采用分層次劃分索引結(jié)構(gòu)管理不確定流數(shù)據(jù)；然后，提出了全新的過濾方法；最后，給出了離群點(diǎn)查詢動態(tài)維護(hù)的更新方法.

1.2.1 索引模型

采用分層次劃分索引結(jié)構(gòu)管理不確定流數(shù)據(jù).這種索引結(jié)構(gòu)：一方面，可以克服傳統(tǒng)索引對多維數(shù)據(jù)管理的局限性；另一方面，能夠避免過多空白子塊的產(chǎn)生，減少了存儲空間的浪費(fèi).同時，利用劃分子塊內(nèi)不確定數(shù)據(jù)點(diǎn)的特性，可以快速批量過濾數(shù)據(jù)點(diǎn)，從而加速最終結(jié)果的查詢.

在文獻(xiàn)[9]工作的基礎(chǔ)上，采用相同的劃分策略構(gòu)建索引結(jié)構(gòu).為便于后續(xù)批量過濾，將每個劃分子塊b內(nèi)的數(shù)據(jù)點(diǎn)按照存在概率由大到小的順序排序，并記錄塊內(nèi)數(shù)據(jù)點(diǎn)個數(shù)b.num和塊內(nèi)空間最大距離b.dis.

1.2.2 過濾方法

首先，給出了空間數(shù)據(jù)點(diǎn)的批量過濾方法，利用這種方法可以在遍歷劃分子塊的過程中，通過快速估算出子塊內(nèi)數(shù)據(jù)點(diǎn)整體的離群概率上界限值來完成批量過濾操作；然后，提出了一種新的離群概率值計算方法用以減少離群概率值的計算代價，該方法盡最大可能地避免了全近鄰集合的迭代運(yùn)算，從而減少了大量的運(yùn)算成本，提高了算法的運(yùn)算效率.

批量過濾方法具體的理論依據(jù)由引理1給出.

引理1[9]給定查詢半徑r.在b.dis＜r的劃分子塊b中，若點(diǎn)p1的存在概率小于點(diǎn)p2的存在概率，那么在b中p1的離群概率一定小于p2的離群概率.

批量過濾時，利用引理1，按照存在概率值由大到小的順序計算出數(shù)據(jù)點(diǎn)在劃分子塊b內(nèi)的離群概率，若某一數(shù)據(jù)點(diǎn)的離群概率小于Threshold，那么在子塊b中存在概率不大于該點(diǎn)的點(diǎn)均為非離群點(diǎn)，由此可以完成劃分子塊b中數(shù)據(jù)點(diǎn)的批量過濾操作.

離群概率值計算方法通過深入分析離群概率值求解的遞推規(guī)律后給出了一種新的解決方案，該方案可以最大可能地避免全近鄰集合的迭代計算從而減少運(yùn)算成本的消耗.具體的理論依據(jù)由定理1給出.

定理1給定不確定數(shù)據(jù)點(diǎn)p和點(diǎn)p的近鄰集合N（p），如果n_MaxSubN（p）是近鄰集合N（p）中存在概率最大的n個近鄰點(diǎn)組成的子集合，那么在所有由N（p）中n個近鄰點(diǎn)組成的子集合里，點(diǎn)p在子集合n_MaxSubN（p）中成為離群點(diǎn)的概率值最小.

證明：給出查詢鄰居個數(shù)k，不確定數(shù)據(jù)點(diǎn)p和點(diǎn)p的近鄰集合N（p）.其中，n_SubN（p）是由近鄰集合N（p）中n個點(diǎn)組成的近鄰子集合.

當(dāng)n＜k時，點(diǎn)p在近鄰子集合n_SubN（p）中成為離群點(diǎn)的概率值等于點(diǎn)p自身的存在概率值，即POutlier（p，n_SubN（p））=P（p）.

易知，當(dāng)n=k時，若n_SubN（p）是由N（p）中存在概率最大的k個點(diǎn)組成的子集合，則點(diǎn)p在子集合n_SubN（p）中成為離群點(diǎn)的概率值最小.

當(dāng)n＞k時，假設(shè)點(diǎn)p在由N（p）中存在概率最大的n個點(diǎn)組成的子集合n_MaxSubN（p）中成為離群點(diǎn)的概率值最小.那么當(dāng)n_MaxSubN（p）中擴(kuò)充一個數(shù)據(jù)點(diǎn)p′（p′∈N（p）∧p′?n_MaxSubN（p））時，點(diǎn)p在新的近鄰子集合中成為離群點(diǎn)的概率值為：

其中：P（a-n_MaxSubN（p））是子集合n_MaxSubN（p）中a個數(shù)據(jù)點(diǎn)發(fā)生的概率.由此可見，不確定數(shù)據(jù)點(diǎn)p′的存在概率越大，點(diǎn)p在新擴(kuò)充的子集合中成為離群點(diǎn)的概率值越小.綜上，可證明結(jié)論成立.

證畢.

由定理1可知，在求解數(shù)據(jù)點(diǎn)p的離群概率值時，按照近鄰集合中近鄰點(diǎn)存在概率值由大到小順序來計算，可以保證每一次的計算中點(diǎn)p在當(dāng)前近鄰集合中成為離群點(diǎn)的概率值都是最小的.那么，為了快速判定點(diǎn)p是否為非離群點(diǎn)，進(jìn)一步給出引理2.

引理2[9]給定數(shù)據(jù)點(diǎn)p和p的近鄰集合N（p），p的離群概率隨著N（p）中點(diǎn)的個數(shù)的增加而減少.

由引理2可知，若數(shù)據(jù)點(diǎn)p在其近鄰子集合中成為離群點(diǎn)的概率值小于查詢閾值，那么點(diǎn)p將是一個非離群點(diǎn).也由此可知，根據(jù)定理1按照近鄰集合中近鄰點(diǎn)存在概率值由大到小的順序來求解點(diǎn)p的離群概率值，若點(diǎn)p是非離群點(diǎn)則可以在最少的迭代計算中判定出來.具體示例由例2所示.

例2圖2展示了b1.dis

圖2 批量過濾示例Fig.2 The example of batch filtering

1.2.3 更新方法

為節(jié)省窗口滑動時數(shù)據(jù)更新所帶來的計算成本，本小節(jié)中首先分析了不確定數(shù)據(jù)流中離群點(diǎn)的性質(zhì)，并將滑動窗口內(nèi)的數(shù)據(jù)進(jìn)行歸類，用以避免對部分?jǐn)?shù)據(jù)點(diǎn)的重復(fù)計算.然后，對當(dāng)前窗口中的葉子劃分子塊增加了部分存儲信息，使得新到達(dá)窗口中的數(shù)據(jù)點(diǎn)可以利用存儲信息直接完成批量過濾，從而達(dá)到減少計算成本的目的.

首先，給出定理2用以確定窗口中不可能成為離群點(diǎn)的數(shù)據(jù)點(diǎn)，以此避免重復(fù)計算.

定理2給定不確定數(shù)據(jù)點(diǎn)p，若點(diǎn)p在后近鄰集合NewN（p）中的離群概率值小于查詢閾值，那么點(diǎn)p不可能成為離群點(diǎn).

證明根據(jù)引理2可知，若點(diǎn)p在近鄰子集合中的離群概率值小于查詢閾值，那么點(diǎn)p的離群概率值一定小于查詢閾值.又因?yàn)镹ewN（p）中的近鄰點(diǎn)到達(dá)窗口都比點(diǎn)p晚，所以若點(diǎn)p在后近鄰集合NewN（p）中的離群概率值小于查詢閾值，則點(diǎn)p將不可能成為離群點(diǎn).

證畢.

由此更新維護(hù)時，對于滿足定理2的點(diǎn)將永遠(yuǎn)不可能成為離群點(diǎn)，也就不需要被更新計算.

具體地，可將當(dāng)前窗口內(nèi)的數(shù)據(jù)DSS分為以下3類集合：1）當(dāng)前窗口內(nèi)的離群點(diǎn)的集合Outlier（DSS）.2）當(dāng)前窗口內(nèi)是非離群點(diǎn)但隨著窗口滑動可能成為離群點(diǎn)的候選集合Candidate（DSS）.3）所有滿足定理2的安全點(diǎn)的集合Inlier（DSS）.

然后，對當(dāng)前窗口中的葉子子塊增加部分存儲信息并利用這些存儲信息來直接完成新到達(dá)數(shù)據(jù)點(diǎn)的批量過濾.與此同時，給出了劃分子塊中批量過濾的動態(tài)維護(hù)過程.

對于葉子劃分子塊將增加部分存儲信息，包括3個部分：1）記錄b內(nèi)是非離群點(diǎn)且存在概率最大的點(diǎn)p的存在概率b.temp；2）記錄包括點(diǎn)p和點(diǎn)p按照定理1滿足它在b中的近鄰子集合中是非離群點(diǎn)的近鄰子集合的集合b.SubN；3）b.SubN中最早消失的數(shù)據(jù)點(diǎn)的時間戳b.label.

下面，主要介紹批量過濾的動態(tài)維護(hù)，包括處理失效數(shù)據(jù)點(diǎn)pold和處理新插入數(shù)據(jù)點(diǎn)pnew.

1）失效數(shù)據(jù)點(diǎn)pold的處理.對于pold映射到的劃分子塊b，若pold屬于b.SubN，則需要更新b的記錄信息并更新b中的批量過濾.若pold不屬于b.SubN，則直接刪除pold.

2）新插入數(shù)據(jù)點(diǎn)pnew的處理.檢測pnew映射到的劃分子塊b，如果P（pnew）＜b.temp那么pnew是非離群點(diǎn)并加入到候選集；如果b.temp＜P（pnew），那么需要更新b的記錄信息并更新b中的批量過濾，用以過濾更多數(shù)據(jù)點(diǎn).

例3展示了利用劃分子塊的存儲信息完成新到達(dá)數(shù)據(jù)點(diǎn)的批量過濾并給出了動態(tài)維護(hù)的過程.

例3圖2（a）（b）分別展示了當(dāng)前時刻與下一時刻劃分子塊b1內(nèi)的數(shù)據(jù)點(diǎn)集.假設(shè)r=3，k=3和Threshold=0.6.當(dāng)前時刻b1的記錄信息b.label=2、b.temp=0.8和b.SubN={p4，p5，p6，p2}.根據(jù)引理1，b1內(nèi)的點(diǎn)均為非離群點(diǎn)，其中，p1是安全點(diǎn)，其他點(diǎn)是候選點(diǎn).下一時刻，b1中點(diǎn)p6和p7到達(dá)而點(diǎn)p1和p2消失.首先處理消失點(diǎn)：當(dāng)p1消失時，不會影響b1中的過濾；當(dāng)p2消失時將重新計算b1中的記錄信息，有b.label=3、b.temp=0.8和b.SubN={p4，p5，p6，p3}，此時b1中各點(diǎn)均為候選點(diǎn).然后處理新插入點(diǎn)：當(dāng)插入p7時，因P（p7）＜b.temp可直接判定p7是候選點(diǎn)；當(dāng)插入p8時，因b.temp＜P（p8）需要更新b1的記錄信息，經(jīng)計算b.label=6、b.temp=0.9和b.SubN={p8，p7，p6}.此時，b1中各點(diǎn)均是非離群點(diǎn)，其中p8、p7和p6是候選點(diǎn)而其他點(diǎn)是安全點(diǎn).

1.3 算法描述

FOD_OUDS算法描述：輸入：滑動窗口數(shù)據(jù)集DNS，查詢閾值Threshold，查詢鄰居個數(shù)k，查詢半徑r，待刪除點(diǎn)pold，待插入點(diǎn)pnew；輸出：離群集合Outlier（DNS）1.WHILE pnew插入到當(dāng)前窗口中DO 2.IF滑動窗口已滿DO //處理失效點(diǎn)pold 3.刪除待消失數(shù)據(jù)點(diǎn)pold；4.IF pold在b記錄的集合b.SubN中THEN

5.更新b的記錄信息，并更新b中的批量過濾；6.ENDIF 7.集合D←近鄰集合N（pold）中未被處理更新的點(diǎn)；8.FOR遍歷集合D中的數(shù)據(jù)點(diǎn)p DO 9.計算屬于候選集中的點(diǎn)p的離群概率，如果p的離群概率大于閾值，那么將p移入到離群集中.10.ENDFOR 11.ENDIF//處理插入點(diǎn)pnew 12.根據(jù)P（pnew）將其插入到所映射的劃分子塊b中；13.IF P（pnew）大于b的b.temp THEN 14.更新b的記錄信息，并更新b中的批量過濾；15.ENDIF 16.集合D←近鄰集合N（pnew）中未被處理更新的點(diǎn)；17.FOR遍歷集合D中的數(shù)據(jù)點(diǎn)p DO 18.計算屬于候選集或離群集中的點(diǎn)p的離群概率，若p的離群概率小于閾值，根據(jù)定理2，將其加入到候選集或安全集中；19.ENDFOR 20.IF pnew未被b中過濾THEN 21.計算pnew的離群概率，若pnew的離群概率小于閾值，則將pnew加入到候選集，否則加入到離群集；22.ENDIF 23.ENDWHILE

在檢測過程中，首先，判斷當(dāng)前滑動窗口內(nèi)數(shù)據(jù)是否已滿，若是，則每當(dāng)有新的點(diǎn)pnew到達(dá)窗口時都將對應(yīng)一個舊的點(diǎn)pold失效（算法中行2），并考慮刪除pold后對它近鄰點(diǎn)和對它映射到劃分子塊的批量過濾的影響，其近鄰集合中的某個原來屬于候選集的點(diǎn)，有可能變?yōu)殡x群點(diǎn)（算法中行3～行11）.然后，對于新插入的點(diǎn)pnew，一方面需要考慮pnew的到達(dá)對它近鄰點(diǎn)和它映射到劃分子塊的批量過濾的影響，并做出相應(yīng)的調(diào)整.另一方面，檢測pnew是否能被批量過濾，若不能則計算它的最終結(jié)果（算法中行12～22）.

2 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用C++編程語言實(shí)現(xiàn)不確定數(shù)據(jù)流上的離群點(diǎn)檢測算法.環(huán)境配置為Inter Core i5 3230 2.6 GHz CPU，6 GB內(nèi)存，Winsows10操作系統(tǒng).

在對比實(shí)驗(yàn)中，對本文提出的FOD_OUDS算法與WDPA（Dynamic Programming Algorithm for Window）算法[7]和PCUOD（Probability Pruning for Continuous Uncertain Outlier Detection）算法[8]分別在真實(shí)數(shù)據(jù)集和人工模擬數(shù)據(jù)集中進(jìn)行性能對比.其中，真實(shí)數(shù)據(jù)集采用的是森林環(huán)境監(jiān)測數(shù)據(jù)，共包含120 000個數(shù)據(jù)點(diǎn)和4個屬性維度，其中，每一個屬性值均被映射在0～100范圍內(nèi).由于真實(shí)數(shù)據(jù)并非是概率數(shù)據(jù)，所以對每一個數(shù)據(jù)點(diǎn)隨機(jī)生成一個存在概率值來增加概率屬性.實(shí)驗(yàn)中主要對比的是查詢時間，表2展示了對比實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果.

表2 實(shí)驗(yàn)結(jié)果Tab.2 Experimental result

表2展示了真實(shí)數(shù)據(jù)集中3種算法的性能對比，其中，由于WDPA算法采用網(wǎng)格索引結(jié)構(gòu)管理不確定數(shù)據(jù)并在批量過濾時不可避免地需要近鄰空間查詢，因而在4維數(shù)據(jù)中的檢測代價相對較高.而對于PCUOD算法，由于其在近鄰數(shù)目較多時過濾性能將會減弱，因而過濾性能相對較低，從而導(dǎo)致需要精確計算的數(shù)據(jù)點(diǎn)增多使得查詢較為緩慢.相比之下，由于FOD_OUDS算法采用分層次劃分索引，因而能夠較好地管理多維數(shù)據(jù)，并且在過濾方法中避免了近鄰空間的查詢，也最大可能地避免了全近鄰集合迭代計算，因而擁有較好的處理性能.

在人工模擬數(shù)據(jù)集的對比實(shí)驗(yàn)中，默認(rèn)的測試數(shù)據(jù)具有5個維度屬性，每個維度屬性值被映射到0～1 000內(nèi)，并對每個數(shù)據(jù)點(diǎn)隨機(jī)生成一個存在概率值.實(shí)驗(yàn)中主要考察查詢鄰居個數(shù)k、查詢半徑r、數(shù)據(jù)維度以及窗口大小S變化對查詢時間和過濾數(shù)量的影響.其中，固定設(shè)置查詢閾值為0.6，具體參數(shù)如表3所示.

表3 參數(shù)設(shè)置Tab.3 Parameter setting

圖3為查詢鄰居個數(shù)k對算法性能的影響.隨著k值的增大，3種算法都需要消耗更多的查詢時間并且過濾數(shù)量都相應(yīng)減少.主要是因?yàn)閗值的增大導(dǎo)致離群點(diǎn)數(shù)目增多，使得算法的計算成本相對增加.通過對比發(fā)現(xiàn)，F(xiàn)OD_OUDS算法的查詢時間明顯低于另外2種算法，這主要是因?yàn)镕OD_OUDS算法的離群概率值計算可以盡最大可能地避免全近鄰集合的迭代計算，從而有利于非離群點(diǎn)的高效過濾使得整體查詢時間較短.

圖3 參數(shù)k對算法的影響Fig.3 The effect of k for the algorithm

圖4為查詢半徑r對算法性能的影響.隨著r值的增大，幾種算法都需要消耗更多的查詢時間.在過濾數(shù)量上，隨著r值增大，PCUOD算法的過濾數(shù)量逐漸減少，F(xiàn)OD_OUDS算法和WDPA算法的過濾數(shù)量逐漸增多.對于PCUOD算法，由于其過濾性能的減弱將直接導(dǎo)致其計算成本增大；對于WDPA算法，由于在批量過濾時不可避免地需要近鄰空間查詢，所以利用網(wǎng)格索引結(jié)構(gòu)維護(hù)多維數(shù)據(jù)會產(chǎn)生非常高昂的空間查詢代價.相對來說，F(xiàn)OD_OUDS算法利用分層次劃分索引在空間查詢代價相對較低且批量過濾時并不需要近鄰空間查詢，所以性能相對較好.

圖4 參數(shù)r對算法的影響Fig.4 The effect of r for the algorithm

圖5為數(shù)據(jù)維度變化對算法性能的影響.隨著維度的增大，算法的查詢時間都明顯增大，過濾性能也都減弱.主要是因?yàn)殡S著維度的增大，空間搜索和索引更新都將更加耗時，但是FOD_OUDS算法的處理性能相對較優(yōu)，主要是因?yàn)镕OD_OUDS算法所采用的索引在多維數(shù)據(jù)中的搜索能力和更新性能相對較好，并且通過增加索引結(jié)構(gòu)中的部分存儲信息，在一次索引映射中就可以直接完成數(shù)據(jù)點(diǎn)的批量過濾，也使得其查詢時間大幅減少.

圖5 維度對算法的影響Fig.5 The effect of dimensionality for the algorithm

圖6為窗口大小變化對算法性能的影響.隨著窗口增大，算法的查詢時間都明顯增多，這是因數(shù)據(jù)量的增多增加了計算成本.同時，過濾數(shù)量也明顯增多，主要是因?yàn)殡S著數(shù)據(jù)量的增大導(dǎo)致非離群點(diǎn)數(shù)目逐漸增多，使得幾種算法均容易滿足過濾條件.但是，整體性能上FOD_OUDS算法較優(yōu).

圖6 窗口大小對算法的影響Fig.6 The effect of window size for the algorithm

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

3 結(jié)論

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