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

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

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

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

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

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