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

【文章來源】：華僑大學(xué)福建省

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

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

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

【參考文獻(xiàn)】：
博士論文
[1]基于流形學(xué)習(xí)的分類與聚類方法及其應(yīng)用研究[D]. 王勇.國(guó)防科學(xué)技術(shù)大學(xué) 2011



本文編號(hào)：3128662