流數(shù)據(jù)的離群點(diǎn)檢測在信用卡欺詐檢測、股票投資計劃等許多現(xiàn)代應(yīng)用中都發(fā)揮著重要作用,是數(shù)據(jù)管理領(lǐng)域中的一項重要問題。應(yīng)用最為廣泛的基于距離的離群點(diǎn)檢測現(xiàn)已被廣泛研究。但現(xiàn)有技術(shù)無法支持面向多維流數(shù)據(jù)的離群點(diǎn)高效檢測,其根本原因是高昂的范圍查詢和候選對象維護(hù)代價。針對上述問題,本文提出了查詢處理框架PIOD（Partition-Index based Outlier Detection）和ISOD（Index based Slide-query Outlier Detection）。本文首先研究了滑動窗口模型下基于kNN的離群點(diǎn)檢測問題。針對此類問題,本文提出查詢處理框架PIOD。PIOD首先利用分片技術(shù)對滑動窗口進(jìn)行劃分,基于此,PIOD以Z曲線為基礎(chǔ)提出ZPH-Tree索引管理流數(shù)據(jù),同時本文增加緩沖區(qū)更新機(jī)制提高索引的適用性。再次,PIOD基于ZPH-Tree提出候選離群維護(hù)算法,該算法通過分片技術(shù)和索引空間過濾,避免維護(hù)所有對象的k近鄰。此外,本文提出基于EM-tree索引的CSM（Candidate-Set Maintain）算法通過維護(hù)候選對象間的位置關(guān)系和分值關(guān)系,降低候選對... 

【文章來源】：沈陽航空航天大學(xué)遼寧省

【文章頁數(shù)】：56 頁

【學(xué)位級別】：碩士

【部分圖文】：

不同窗口大小下算法的CPU運(yùn)行時間

(a) Tao (b) Stock (c) HPC圖 5.2 不同窗口大小下算法的內(nèi)存峰值隨著滑動對象個數(shù)的增加，本文有以下發(fā)現(xiàn)：CPU 時間. 1)kNN_PIOD 算法的性能更好，在最好情況下，它的運(yùn)行時間是kNN_LEAP 的 0.01 倍；2)兩種算法的運(yùn)行時間基本上都隨滑動對象個數(shù)的增加而增加，當(dāng) s/N 達(dá)到 50%時 kNN_PIOD 與 kNN_LEAP 運(yùn)行時間逐漸接近。其原因是：①和kNN_LEAP 相比，kNN_PIOD 算法利用索引維護(hù)了流數(shù)據(jù)間的位置關(guān)系，支持高效范圍查詢，降低了計算代價；②kNN_PIOD 算法采用分片技術(shù)維護(hù)算法的穩(wěn)定性，但當(dāng) s/N達(dá)到 50%及其以上時，與 kNN_LEAP 的基于滑動對象個數(shù)劃分相同，因此運(yùn)行時間逐漸接近。內(nèi)存峰值. 1)kNN_LEAP 的內(nèi)存峰值是 kNN_PIOD 的 1 到 3 倍；2)隨著滑動對象個數(shù)的增加，kNN_LEAP 內(nèi)存峰值的增長速度更快。其原因是：滑動對象個數(shù)的增長會導(dǎo)致 kNN_LEAP 中對象鄰居信息的頻繁更新，需要重復(fù)計算非候選對象鄰居信息，而kNN_PIOD 通過候選集合維護(hù)候選對象間的分值關(guān)系，避免了非潛在離群點(diǎn)的空間維護(hù)代價。

(a) Tao (b) Stock (c) HPC圖 5.3 不同滑動對象個數(shù)下算法的 CPU 運(yùn)行時間(a) Tao (b) Stock (c) HPC圖 5.4 不同滑動對象個數(shù)下算法的內(nèi)存峰值CPU 時間. 1)kNN_PIOD 算法的性能更好，在最好情況下，它的運(yùn)行時間是kNN_LEAP 的 0.01 倍；2)兩種算法的運(yùn)行時間都隨離群點(diǎn)個數(shù)的增加而增加，當(dāng) n/W 增長到接近 20%時，kNN_PIOD 與 kNN_LEAP 運(yùn)行時間逐漸接近。其原因是：①和kNN_LEAP 相比，kNN_PIOD 算法維護(hù)了潛在離群點(diǎn)，避免了對象間距離的重復(fù)計算代價和掃描窗口代價；②同樣地，正是由于 kNN_PIOD 維護(hù)了至少 1 倍的潛在離群點(diǎn)，當(dāng)

【參考文獻(xiàn)】：
期刊論文
[1]VDOD:一種基于KD樹的分布式離群點(diǎn)檢測算法[J]. 李子茂,駱慶,劉晶.  計算機(jī)與數(shù)字工程. 2018(03)
[2]一種分布式計算的空間離群點(diǎn)挖掘算法[J]. 張衛(wèi)平,劉紀(jì)平,仇阿根,張用川,趙陽陽.  測繪科學(xué). 2017(08)
[3]無線傳感網(wǎng)離群點(diǎn)檢測技術(shù)研究綜述[J]. 葉冬芬,楊明霞,范偉,邵鵬飛.  計算機(jī)應(yīng)用研究. 2015(07)
[4]BOD:一種高效的分布式離群點(diǎn)檢測算法[J]. 王習(xí)特,申德榮,白梅,聶鐵錚,寇月,于戈.  計算機(jī)學(xué)報. 2016(01)
[5]一種基于密度的不確定數(shù)據(jù)離群點(diǎn)檢測算法[J]. 姜元凱,鄭洪源,丁秋林.  計算機(jī)科學(xué). 2015(04)
[6]基于密度劃分的離群點(diǎn)檢測算法[J]. 魏龍,王勇.  計算機(jī)與現(xiàn)代化. 2015(03)
[7]基于層次聚類的離群點(diǎn)分析方法[J]. 張俊溪,楊海粟.  計算機(jī)技術(shù)與發(fā)展. 2014(08)
[8]NLOF:一種新的基于密度的局部離群點(diǎn)檢測算法[J]. 王敬華,趙新想,張國燕,劉建銀.  計算機(jī)科學(xué). 2013(08)

碩士論文
[1]QAR數(shù)據(jù)集離群點(diǎn)檢測及故障定位算法研究[D]. 王麗婧.中國民航大學(xué) 2015
[2]基于密度的局部離群點(diǎn)檢測算法的研究與改進(jìn)[D]. 趙新想.華中師范大學(xué) 2014



本文編號：3063863