一種基于密度的聚類的算法

將物理或抽象對象的集合分成由類似的對象組成的多個(gè)類的過程被稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個(gè)簇中的對象彼此相似，與其他簇中的對象相異目前，它已成為數(shù)據(jù)挖掘研究領(lǐng)域中一個(gè)非?；钴S的研究方向。聚類分析技術(shù)在模式識別、數(shù)據(jù)分析、圖像處理和市場研究等許多領(lǐng)域得到了廣泛的應(yīng)用。

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

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

　　1 DBSCAN算法

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

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

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

　　2 M-DBSCAN算法

　　2.1 在線聚類

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

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

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

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

　?。?）通過對相似度矩陣進(jìn)行比較分析，找出鄰域密度最大的數(shù)據(jù)點(diǎn)作為第一個(gè)初始類的中心c1；

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

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

　　（5）直到?jīng)]有數(shù)據(jù)到來為止，輸出聚類結(jié)果。[!--empirenews.page--]

　　2.2 改進(jìn)的算法

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

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

　　改進(jìn)后整個(gè)算法描述如下：

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

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

　?。?）對尚未加入的數(shù)據(jù)點(diǎn)，計(jì)算某一個(gè)數(shù)據(jù)點(diǎn)到類c1中的所有點(diǎn)的平均距離d1，類的平均距離d2；

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

　　如果不能加入到任何一個(gè)已有聚類，則創(chuàng)建一個(gè)新的類，將其存入S’中。[!--empirenews.page--]

　部分偽代碼：

　　Cluster M-DBSCAN（）

　　{

　　Initialize S（n×n），dthr;

　　For i=1:n

　　If S（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;

　　If meandistance1<meandistance2

　　If meanradiusnew<meanradius

　　Add xj to S’（1）；

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

　　Else

　　Next class;

　　End

　　If no class

　　Create a new class S’（2）；

　　End

　　…

　　Until no data come

　　It’s over

　　Output S’

　　}[!--empirenews.page--]

　　3 算法性能及分析

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

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

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

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

　　本文討論了一種將DBSCAN聚類算法進(jìn)行改進(jìn)的M-DBSCAN聚類算法，它克服了DBSCAN聚類算法不能處理大數(shù)據(jù)集的問題，并實(shí)現(xiàn)可以對閾值進(jìn)行實(shí)時(shí)更改。試驗(yàn)結(jié)果顯示，M-DBSCAN算法的準(zhǔn)確性比DBSCAN算法要好，處理大數(shù)據(jù)集的速度更快。但是對于聚類數(shù)目的確定仍然是判斷是否超過某閾值才可算作某一類的標(biāo)準(zhǔn)，聚類數(shù)目與閾值的選擇有很大關(guān)系。因此如何自動(dòng)確定聚類數(shù)目將是下一步工作的方向。