發(fā)布時間：2021-04-10 01:12

　　由于存儲技術(shù)的進步和日常生活工作中不斷產(chǎn)生各種數(shù)據(jù),加快了大數(shù)據(jù)時代的到來。人們可以通過對大量的數(shù)據(jù)進行分析和挖掘,得到所需要的有價值的信息。然而目前處理海量數(shù)據(jù)的速度仍難以滿足人們的需求,因此從大規(guī)模數(shù)據(jù)中高效的挖掘出人們所需要的有價值的信息成為了數(shù)據(jù)處理的一個難題。機器學習在解決這類問題中發(fā)揮了重要的作用,其中聚類算法是機器學習十大經(jīng)典算法之一。密度峰值聚類算法（DPeak）是目前熱門聚類算法的一種。該算法具有思想簡單、參數(shù)唯一且能聚類成任意形狀簇等優(yōu)點。憑借這些優(yōu)點,DPeak一經(jīng)提出就吸引了大量科研人員的關(guān)注。雖然DPeak有許多優(yōu)勢,但是其時間復雜度為O（n²）,難以滿足海量數(shù)據(jù)的處理。因為該算法中ρ和δ這兩個量都是通過復雜度為O（n²）的蠻力算法得到的,故計算當中存在大量的冗余計算。本文對DPeak算法進行了深入的分析,并在總結(jié)前人的基礎上取其精華棄其糟粕,提出了快速密度峰值聚類算法。該算法顯著的提高了DPeak算法處理大規(guī)模數(shù)據(jù)的速度。本文主要包括以下幾個方面的內(nèi)容:（1）分析了DPeak算法的性質(zhì),對其在整個聚類算法體系中位置... 

【文章來源】：華僑大學福建省

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

【學位級別】：碩士

【部分圖文】：

DCore的密度核心區(qū)與數(shù)據(jù)漂移[51]

25(1)這兩種算法形成簇的方式都是沿著點密度變大的方向。(2)在meanshift中，漂移的中間點可能是虛擬點，而在DPeak中，漂移的中間點為真實點。(a)實例1(b)實例2圖3.3DPeak的局部峰值中心2個實例(3)meanshift實際上是ShadowKernel(影子)梯度上升法，但其步長是動態(tài)變化的[74]。如果數(shù)據(jù)為標準的高斯分布，那么該方法為SteepestAscentMethod(最速上升法)。當它的核函數(shù)是PiecewiseConst（分段常數(shù))時，均值漂移過程實際上又是牛頓法[81]。當核函數(shù)是其它任意形式時，該算

37圖4.1在三個二維合成數(shù)據(jù)集的實驗4.2.2實驗二FastDPeak的速度在這一小節(jié)中，本文介紹了一些在大規(guī)模數(shù)據(jù)集上進行的實驗，并與其他算法進行了比較。第一個實驗在BigCross200k，BigCross500k和KDD04上進行，其中BigCross200k和BigCross500k分別有20萬和50萬個點，均是從BigCross中隨機選取的。結(jié)果如表4.2所示，從表中可以看出，在K=50和K=100的兩個數(shù)據(jù)集上，F(xiàn)astDPeak算法都比EDDPC算法好的多。以BigCross200k為例，F(xiàn)astDPeak算法對EDDPC算法的速度提升為2-3倍，BigCross500k的速度約為LSH-DDP算法的1.635-2.7倍。在KDD04上，F(xiàn)astDPeak算法相對于其他兩種算法的優(yōu)勢更加明顯。表4.2三個數(shù)據(jù)集上運行時間比較(單位:秒)BigCross200kBigCross500kKDD04EDDPC15599768FastDPeak(K=50)3812228FastDPeak(K=100)5115034FastDPeak(K=150)6620142第二個實驗也是在BigCross上進行的。其中K是固定的，而n從100000到500000不等。結(jié)果如圖4.2所示。從圖中可以看出FastDPeak在BigCross上，隨著K=50，K=100，K=150，運行時間越來越短，其速度比EDDPC快很多。EDDPC的時間復雜度大于O(nlog(n))，隨著數(shù)據(jù)量的增大，運行時間迅速會增加。FastDPeak的時間復雜度為O(nlog(n))，滿足上述復雜度分析。圖4.3為BigCross上FastDPeak算法和EDDPC算法的距離計算量隨n增加的情況，其中FastDPeak的距離計算量包括距離計算的KNN算法。還發(fā)現(xiàn)FastDPeak的距離

【參考文獻】：
博士論文
[1]基于流形學習的分類與聚類方法及其應用研究[D]. 王勇.國防科學技術(shù)大學 2011



本文編號：3128662