一種基于密度的聚類的算法-設計應用

精品文檔-下載后可編輯一種基于密度的聚類的算法-設計應用將物理或抽象對象的集合分成由類似的對象組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異目前，它已成為數(shù)據(jù)挖掘研究領域中一個非?；钴S的研究方向。聚類分析技術在模式識別、數(shù)據(jù)分析、圖像處理和市場研究等許多領域得到了廣泛的應用。

許多算法被設計用來聚類數(shù)值類型的數(shù)據(jù)。但是，應用可能要求聚類其他類型的數(shù)據(jù)，如二元類型（binary），分類/標稱類型（categorical/nominal），序數(shù)型（ordinal）數(shù)據(jù)，或者這些數(shù)據(jù)類型的混合。其主要思想是：只要臨近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個閾值就繼續(xù)聚類。樣的方法可以用來過濾噪聲和孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀的類。

DBSCAN算法利用類的高密度連通性可以快速發(fā)現(xiàn)任意形狀的類，但是當處理的數(shù)據(jù)量較大時，一般的聚類算法不能滿足在線聚類這一特點，計算復雜度高，速度慢。

1DBSCAN算法

DBSCAN（Density-BasedSpatialClusteringofApplacationswithNoise）是一個比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它將簇定義為密度相連的點的集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。DBSCAN算法具有足夠高密度的區(qū)域劃分為一類，并可以在帶有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類

DBSCAN算法提出了一些新的定義：

DBSCAN算法是基于密度的聚類算法，它將類看作是數(shù)據(jù)空間中被低密度區(qū)域分割開的高密度對象區(qū)域。在該算法中，發(fā)現(xiàn)一個聚類的過程是基于這樣的事實：一個聚類能夠被其中的任意一個對象所確定。其基本思想是：考察數(shù)據(jù)庫D中的某一個點P，若P是點，則通過區(qū)域查詢得到該點的鄰域，鄰域中的點和P同屬于一個類，這些點將作為下一輪的考察對象，并通過不斷地對種子點進行區(qū)域查詢來擴展它們所在的類，直至找到一個完整的類。

2M-DBSCAN算法

2.1在線聚類

由于處理數(shù)據(jù)量較大，性處理完畢不但運算量大，復雜度高，而且對存儲空間的需求量大，因此本文提出一種在線式聚類算法，可以動態(tài)增加聚類數(shù)目。

算法的原理是：隨著輸入樣本數(shù)據(jù)的不斷增加，實時動態(tài)地增加聚類個數(shù)或調(diào)整聚類中心及聚類半徑，在形成的任意一個聚類中，聚類中心與屬于此聚類的樣本點的相似度都不小于一個閾值dthr，dthr的選取將直接影響到聚類數(shù)目。

將在線式聚類算法引入后，算法的描述如下：

（1）積累一小段時間內(nèi)的數(shù)據(jù)，進行歸一化壓縮，進行相似度計算，得到相似度矩陣；

（2）通過對相似度矩陣進行比較分析，找出鄰域密度的數(shù)據(jù)點作為個初始類的中心c1；

（3）對尚未加入此類的數(shù)據(jù)點xi，比較與類中心的距離是否大于給定閾值dthr，若是，則加入此類，否則創(chuàng)建一個新類cj；

（4）處理完這一小段數(shù)據(jù)后，對新到來的一個數(shù)據(jù)點進行與（3）相同的做法，確定其類別；

（5）直到?jīng)]有數(shù)據(jù)到來為止，輸出聚類結果。

2.2改進的算法

DBSCAN算法在對類的劃分時采用的方法是：比較此數(shù)據(jù)點到各類中心的距離，若小于某閾值，則屬于此類?？梢婇撝档倪x擇直接影響類的劃分及類的數(shù)目。但是如圖1所產(chǎn)生的聚類模塊[3]所示，這種方法帶來的問題就是：距離近的不一定屬于同一類，在閾值半徑內(nèi)的不一定屬于同一類。

針對此問題，本文提出一種改進的算法M-DBSCAN。首先實現(xiàn)在線聚類，可以動態(tài)調(diào)整聚類的數(shù)目；之后，通過將數(shù)據(jù)點到類的平均距離與類內(nèi)平均距離以及新半徑與原半徑作比較進行雙重判決，確定數(shù)據(jù)點是否可以加入此類中，以實時調(diào)整閾值半徑，解決了類劃分錯誤的問題。

改進后整個算法描述如下：

（1）積累一小段時間內(nèi)的數(shù)據(jù)，得到相似度矩陣

（2）給定閾值dthr，找出鄰域密度的數(shù)據(jù)點作為個初始類的中心c1，計算S中每行值大于dthr的個數(shù)，個數(shù)多的行號即為個類的中心，將類中的數(shù)據(jù)點存放到矩陣S’（n×n+2）的行，每行中的個為類中心，計算類的平均半徑r，同時計算此類的平均距離d2，放到兩位。

（3）對尚未加入的數(shù)據(jù)點，計算某一個數(shù)據(jù)點到類c1中的所有點的平均距離d1，類的平均距離d2；

若d1d2，則判斷加入此數(shù)據(jù)后類的半徑是否變大；如果變小，將數(shù)據(jù)點加入此類，同時改變此類的平均半徑；否則尋找下一個聚類，計算同上。

如果不能加入到任何一個已有聚類，則創(chuàng)建一個新的類，將其存入S’中。

部分偽代碼：

ClusterM-DBSCAN（）

{

InitializeS（n×n），dthr;

Fori=1:n

IfS（i,j）=dthr

sum（i）++;

count（i,j）=j;

j++;

end

end

sort（sum（：））；

S’（1,:）=count（，：）；

S’（1,n+1）=meanradius;

S’（1,n+2）=meandistance2;

Ifmeandistance1meandistance2

Ifmeanradiusnewmeanradius

AddxjtoS’（1）；

S’（1,n+1）=newmeanradius;

Else

Nextclass;

End

Ifnoclass

CreateanewclassS’（2）；

End

…

Untilnodatacome

It’sover

OutputS’

}

3算法性能及分析

對M-DBSCAN算法的性能作了測試，并與DBSCAN作了比較。所有的測試都在1臺PC機上進行，配置P4，2.0GHzCPU，512MB內(nèi)存，80GB硬盤，算法用Matlab7.3實現(xiàn)。

首先用構造的模擬數(shù)據(jù)對聚類結果進行驗證。圖2為DBSCAN算法在閾值半徑為20時得到的結果，明顯地將不同的三類作為一類輸出，形成了錯誤的類劃分；而在取同樣的初始閾值半徑時，圖3可以看出M-DBSCAN算法得到更好的聚類結果。

從圖4中可以看到兩種算法在SEQUOIA2000數(shù)據(jù)庫上對不同數(shù)據(jù)量樣本的執(zhí)行時間的比較。算法M-DBSCAN比算法DBSCAN快得多，且隨著數(shù)據(jù)量的不斷增大，這種速度上的差別越來越大。表1為兩種算法的錯誤率比較圖，錯誤率為，N1為算法所得聚類數(shù)目，N2為實際聚類數(shù)目。表1中可看出，改進的M-DBSCAN算法錯誤概率普遍要小于DBSCAN的，表明改進后的算法減小了錯誤率，對處理大樣本集有較好的性能。

表2中的測試數(shù)據(jù)集來自Dr.JSrgSander提供的仿照DBSCAN中DataBase2生成的數(shù)據(jù)集DB2[8]。由表中可以看出，當數(shù)據(jù)規(guī)模為50000時，雖然SGDO[7]處理噪音點的能力比M-DBSCAN強，但是從錯誤率和運行時間上M-DBSCAN比前兩者都有較大的改善。CURD雖然有較短的運行時間，但是存在大量的噪音點。

本文討論了一種將DBSCAN聚類算法進行改