不確定數(shù)據(jù)的聚類分析與異常點檢測算法.pdf

1、不確定數(shù)據(jù)作為一種新型的數(shù)據(jù)模型，被廣泛應(yīng)用于金融、基于位置的服務(wù)、移動物體監(jiān)測、傳感器網(wǎng)絡(luò)等許多類型應(yīng)用領(lǐng)域。近年來出現(xiàn)的面向不確定數(shù)據(jù)的分析處理技術(shù)已成為數(shù)據(jù)庫、數(shù)據(jù)挖掘等領(lǐng)域的研究熱點。不確定性的存在給研究人員帶來了新的挑戰(zhàn):一方面，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)中的基本概念都是面向確定數(shù)據(jù)的，需要擴(kuò)展后應(yīng)用于不確定數(shù)據(jù);另一方面，不確定數(shù)據(jù)對應(yīng)的可能世界模型中的實例數(shù)量是指數(shù)級增長的，會增加挖掘算法的復(fù)雜度并增加運行時間、內(nèi)存占用率等資源消

2、耗。
　　基于此，在了解和掌握數(shù)據(jù)挖掘基本概念和相關(guān)算法、不確定數(shù)據(jù)的產(chǎn)生背景及數(shù)據(jù)模型特點的基礎(chǔ)上，本文主要研究了不確定數(shù)據(jù)的聚類和異常點檢測問題，旨在為不確定數(shù)據(jù)提供更為多樣的聚類分析和異常點檢測功能。同時，對本文所提出的算法進(jìn)行大量的相關(guān)實驗分析，實驗結(jié)果證明了提出算法的有效性和高效性。本文的主要貢獻(xiàn)體現(xiàn)在以下幾個方面:
　　(1)本文提出了一種障礙空間中不確定數(shù)據(jù)聚類算法OBS-UK-means(ObstacleUn

3、certain K-means)，為了保證聚類準(zhǔn)確性的前提下提高算法效率，分別提出了基于R樹和Voronoi圖的兩種剪枝策略和最近距離區(qū)域的概念。通過實驗驗證了OBS-UK-means算法的高效性和準(zhǔn)確性，同時證明了剪枝策略在不損害聚類有效性的情況下，能夠有效的提高聚類效率。
　　(2)本文提出了基于密度的局部不確定數(shù)據(jù)異常點檢測算法。首先提出了一個新的基于密度的局部異常點的定義，其次，為提高算法效率，提出基于動態(tài)規(guī)劃的方法進(jìn)行異

4、常點檢測。最后，設(shè)計相應(yīng)的剪枝策略以降低存儲代價并提高算法的效率。
　　(3)本文提出了基于不確定數(shù)據(jù)流參數(shù)可變的異常點檢測算法。首先根據(jù)不確定數(shù)據(jù)流上異常點的性質(zhì)，提出了可以有效檢測不確定數(shù)據(jù)流中異常點的算法CUOD(Continuous Uncertain Outlier Detection)。其次為了提高算法效率，提出了通過估計異常點的概率而進(jìn)行剪枝的算法PCUOD（Probability pruning forContin

5、uous Uncertain Outlier Detection）。然后，為了滿足用戶在不同時刻對異常點查詢參數(shù)有不同的需求，提出了不確定數(shù)據(jù)流中參數(shù)可變的異常點查詢算法。
　　(4)本文提出了面向不確定數(shù)據(jù)流基于距離的異常點檢測算法。首先針對特定的不確定數(shù)據(jù)模型提出了異常點的定義，同時設(shè)計動態(tài)存儲結(jié)構(gòu)，以滿足算法在檢測效率和存儲空間兩方面的要求。其次，為了降低近鄰查詢的代價以進(jìn)一步提高算法的效率，提出了基于SM-tree（Sta