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

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

離群點(diǎn)檢測(cè)是數(shù)據(jù)管理領(lǐng)域的熱點(diǎn)問(wè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).

近年來(lái)，數(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è)算法尚無(wú)法滿足諸多現(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)解決方案無(wú)法直接應(yīng)用到上述問(wèn)題中[5].因此，設(shè)計(jì)出一種高效的不確定數(shù)據(jù)流上的離群點(diǎn)檢測(cè)算法成為本文的主要研究目標(biāo).

文獻(xiàn)[6]首次給出了存在級(jí)不確定數(shù)據(jù)中的離群點(diǎn)定義，并提出了DPA算法用以解決集中式環(huán)境中的離群點(diǎn)檢測(cè)問(wèn)題.隨后，文獻(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ī)劃思想來(lái)求解離群概率值用以避免可能世界的空間膨脹.但因該算法在批量過(guò)濾時(shí)不可避免地需要近鄰空間的查詢，這就使得在處理多維數(shù)據(jù)時(shí)具有一定的局限性，另外，由于其忽略了離群概率值求解的遞推規(guī)律，使其在概率值求解中也無(wú)法避免冗余計(jì)算.文獻(xiàn)[8]也關(guān)注于該研究問(wèn)題并提出了PCUOD算法，該算法通過(guò)估算數(shù)據(jù)點(diǎn)的離群概率范圍進(jìn)行概率剪枝，從而減少了必要的計(jì)算成本.但是，由于PCUOD算法中的界限估算方法在近鄰數(shù)目急劇增加時(shí)會(huì)產(chǎn)生失效的情況，從而也造成了一定的局限性.總之，目前相關(guān)解決方案中仍存在諸多不足，無(wú)法高效地滿足現(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í)，本文通過(guò)對(duì)索引結(jié)構(gòu)中的葉子子塊增加部分存儲(chǔ)信息，可以快速地完成新到達(dá)數(shù)據(jù)點(diǎn)的批量過(guò)濾，極大地減少了數(shù)據(jù)更新過(guò)程中的計(jì)算代價(jià).

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

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

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

1.1 問(wèn)題描述

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

表1 符號(hào)列表Tab.1 List of symbols

DS表示具有d維屬性的不確定數(shù)據(jù)流，在DS中任意數(shù)據(jù)點(diǎn)p都有一個(gè)存在概率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和查詢鄰居個(gè)數(shù)k，若點(diǎn)p是P內(nèi)的（r，k）-離群點(diǎn)，則p在半徑r范圍內(nèi)的鄰居個(gè)數(shù)小于k，即

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

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

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

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

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

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

1.2.1 索引模型

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

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

1.2.2 過(guò)濾方法

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

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

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

批量過(guò)濾時(shí)，利用引理1，按照存在概率值由大到小的順序計(jì)算出數(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ò)濾操作.

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

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

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

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

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

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

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

證畢.

由定理1可知，在求解數(shù)據(jù)點(diǎn)p的離群概率值時(shí)，按照近鄰集合中近鄰點(diǎn)存在概率值由大到小順序來(lái)計(jì)算，可以保證每一次的計(jì)算中點(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)的個(gè)數(shù)的增加而減少.

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

例2圖2展示了b1.dis

圖2 批量過(guò)濾示例Fig.2 The example of batch filtering

1.2.3 更新方法

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

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

定理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ù)時(shí)，對(duì)于滿足定理2的點(diǎn)將永遠(yuǎn)不可能成為離群點(diǎn)，也就不需要被更新計(jì)算.

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

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

對(duì)于葉子劃分子塊將增加部分存儲(chǔ)信息，包括3個(gè)部分：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)的時(shí)間戳b.label.

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

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

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

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

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

1.3 算法描述

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

5.更新b的記錄信息，并更新b中的批量過(guò)濾；6.ENDIF 7.集合D←近鄰集合N（pold）中未被處理更新的點(diǎn)；8.FOR遍歷集合D中的數(shù)據(jù)點(diǎn)p DO 9.計(jì)算屬于候選集中的點(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中的批量過(guò)濾；15.ENDIF 16.集合D←近鄰集合N（pnew）中未被處理更新的點(diǎn)；17.FOR遍歷集合D中的數(shù)據(jù)點(diǎn)p DO 18.計(jì)算屬于候選集或離群集中的點(diǎn)p的離群概率，若p的離群概率小于閾值，根據(jù)定理2，將其加入到候選集或安全集中；19.ENDFOR 20.IF pnew未被b中過(guò)濾THEN 21.計(jì)算pnew的離群概率，若pnew的離群概率小于閾值，則將pnew加入到候選集，否則加入到離群集；22.ENDIF 23.ENDWHILE

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

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

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

在對(duì)比實(shí)驗(yàn)中，對(duì)本文提出的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)行性能對(duì)比.其中，真實(shí)數(shù)據(jù)集采用的是森林環(huán)境監(jiān)測(cè)數(shù)據(jù)，共包含120 000個(gè)數(shù)據(jù)點(diǎn)和4個(gè)屬性維度，其中，每一個(gè)屬性值均被映射在0～100范圍內(nèi).由于真實(shí)數(shù)據(jù)并非是概率數(shù)據(jù)，所以對(duì)每一個(gè)數(shù)據(jù)點(diǎn)隨機(jī)生成一個(gè)存在概率值來(lái)增加概率屬性.實(shí)驗(yàn)中主要對(duì)比的是查詢時(shí)間，表2展示了對(duì)比實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果.

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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