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

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

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

【學位級別】：碩士

【部分圖文】：

不同窗口大小下算法的CPU運行時間

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

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

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

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



本文編號：3063863