隨著信息技術(shù)的不斷發(fā)展,流數(shù)據(jù)逐漸成為當今主要數(shù)據(jù)類型,它具有數(shù)據(jù)規(guī)模大、傳輸速度快等特征,這些特征給高效管理流數(shù)據(jù)帶來巨大挑戰(zhàn)。離群點檢測是數(shù)據(jù)挖掘領(lǐng)域一種重要數(shù)據(jù)挖掘技術(shù),在流環(huán)境下有著廣泛的應(yīng)用�，F(xiàn)有算法普遍存在計算和空間代價大等問題,無法在高速流環(huán)境下高效工作,用戶的實時性要求無法滿足。本文研究面向流數(shù)據(jù)的離群點近似檢測問題,以降低精度為代價換取計算代價的大幅降低,滿足用戶實時性需求。本文貢獻點總結(jié)如下:本文首先研究了滑動窗口模型下基于距離閾值的離群點近似檢測問題。針對此類問題,本文提出查詢處理框架PBOAD（Partition-Based Outlier Approximate Detection）。PBOAD首先利用分片技術(shù)對滑動窗口進行劃分,以此為基礎(chǔ),提出基于M-Tree的索引PMT（Partition based M-Tree）管理各分片數(shù)據(jù)。再次,PBOAD使用帶概率誤差保證的離群點預測算法過濾安全對象,降低算法復雜性。本文隨后研究了滑動窗口模型下基于kNN平均距離的離群點近似檢測問題。針對此問題,本文提出查詢處理框架GAOAD（Grid-based Average... 

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

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

【學位級別】：碩士

【部分圖文】：

PBOAD與其它算法在不同窗口N下的CPU時間比較

PBOAD 的增長速度最慢，且消耗的計算代價最低。其原因在于，窗口長度越長，查詢范圍內(nèi)鄰居的數(shù)目越多。然而，PBOAD 只在最后一個分片內(nèi)進行查詢，這導致該框架對窗口長度的增加不敏感。因此，PBOAD 的效率最高。與此同時，PBOAD 擁有較好的空間效率，它消耗的內(nèi)存最小。其原因在于，該算法只維護少量對象的 k 近鄰列表，而其它對象需要維護所有安全對象的 k 近鄰列表。由此可見，PBOAD 適合在內(nèi)存受限的環(huán)境下使用。(a) 數(shù)據(jù)集 Tao (b) 數(shù)據(jù)集 Stock (c) 數(shù)據(jù)集 HPC圖 5.1 PBOAD 與其它算法在不同窗口 N 下的 CPU 時間比較

(a) 數(shù)據(jù)集 Tao (b) 數(shù)據(jù)集 Stock (c) 數(shù)據(jù)集 HPC圖 5.3 PBOAD 與其它算法在不同滑動 s 下的 CPU 時間比較(a) 數(shù)據(jù)集 Tao (b) 數(shù)據(jù)集 Stock (c) 數(shù)據(jù)集 HPC圖 5.4 PBOAD 與其它算法在不同滑動 s 下的 MEMORY 比較第三組實驗測試參數(shù) k 對算法性能的影響，k 從 5 變化到 100，其它參數(shù)使用默認參數(shù)。如圖所示，三個算法的運行時間均隨 k 的增加而增加，但是 PBOAD 的增長速度最慢，其原因在于，隨著 k 的增加，算法需要維護的 k 鄰居數(shù)目也會相應(yīng)增加，但是，PBOAD 只需維護少量非安全對象的 k 近鄰列表。因此，當 k 增加時，PBOAD 計算時間

【參考文獻】：
期刊論文
[1]VDOD:一種基于KD樹的分布式離群點檢測算法[J]. 李子茂,駱慶,劉晶.  計算機與數(shù)字工程. 2018(03)
[2]基于K-means的數(shù)據(jù)流離群點檢測算法[J]. 韓崇,袁穎珊,梅燾,耿慧玲.  計算機工程與應(yīng)用. 2017(03)
[3]BOD:一種高效的分布式離群點檢測算法[J]. 王習特,申德榮,白梅,聶鐵錚,寇月,于戈.  計算機學報. 2016(01)
[4]基于密度的不確定數(shù)據(jù)離群點檢測研究[J]. 洪沙,林佳麗,張月良.  計算機科學. 2015(05)
[5]一種基于密度的不確定數(shù)據(jù)離群點檢測算法[J]. 姜元凱,鄭洪源,丁秋林.  計算機科學. 2015(04)
[6]不確定數(shù)據(jù)流上Top-k異常點查詢算法[J]. 曹科研,王國仁,韓東紅,李碩儒.  計算機科學與探索. 2015(02)

碩士論文
[1]不確定數(shù)據(jù)挖掘技術(shù)研究及應(yīng)用[D]. 張穎.南京航空航天大學 2016



本文編號：3387062