摘 要： 基于密度的聚類(lèi)是聚類(lèi)算法中的一種，其主要優(yōu)點(diǎn)是可以發(fā)現(xiàn)任意形狀的簇，但處理大數(shù)據(jù)集時(shí)效果不佳，為此提出了一種改進(jìn)的算法M-DBSCAN，保留了基于密度聚類(lèi)算法的優(yōu)點(diǎn)，同時(shí)克服了以往算法不能處理大數(shù)據(jù)集的缺點(diǎn)。實(shí)驗(yàn)結(jié)果證明，M-DBSCAN聚類(lèi)算法在聚類(lèi)質(zhì)量及速度上都比原DBSCAN有較大提高。
關(guān)鍵詞： 聚類(lèi)； DBSCAN算法； 在線聚類(lèi)
聚類(lèi)就是把相似的東西歸為一類(lèi)，有明顯區(qū)別的事物分屬在不同的類(lèi)別中，方便處理的一種數(shù)據(jù)挖掘的方法。目前，它已成為數(shù)據(jù)挖掘研究領(lǐng)域中一個(gè)非常活躍的研究方向。聚類(lèi)分析技術(shù)在模式識(shí)別、數(shù)據(jù)分析、圖像處理和市場(chǎng)研究等許多領(lǐng)域得到了廣泛的應(yīng)用。
迄今為止，人們提出了許多聚類(lèi)分析的算法，其中基于密度的聚類(lèi)算法能夠發(fā)現(xiàn)任意形狀的簇，應(yīng)用較為廣泛。其主要思想是:只要臨近區(qū)域的密度(對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目)超過(guò)某個(gè)閾值就繼續(xù)聚類(lèi)。也就是說(shuō)，對(duì)給定類(lèi)中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中必須至少包含某個(gè)數(shù)目的點(diǎn)。這樣的方法可以用來(lái)過(guò)濾噪聲和孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的類(lèi)。
基于密度的聚類(lèi)算法主要有：DBSCAN（Density Based Spatial Clustering of Applications with Noise），OPTICS（Ordering Points to Identify the Clustering Structure）等。DBSCAN算法利用類(lèi)的高密度連通性可以快速發(fā)現(xiàn)任意形狀的類(lèi)，但是當(dāng)處理的數(shù)據(jù)量較大時(shí)，一般的聚類(lèi)算法不能滿足在線聚類(lèi)這一特點(diǎn)，計(jì)算復(fù)雜度高，速度慢。針對(duì)此問(wèn)題本文提出了一種改進(jìn)的M-DBSCAN（Modified-DBSCAN）算法，改善了DBSCAN存在的不足，而且對(duì)處理大量數(shù)據(jù)有較好的效果。
1 DBSCAN算法
MARTIN E等人提出的DBSCAN算法將具有足夠高密度的區(qū)域劃分為一類(lèi)，并可以在帶有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi)[1]。
DBSCAN算法提出了一些新的定義：
DBSCAN算法是基于密度的聚類(lèi)算法，它將類(lèi)看作是數(shù)據(jù)空間中被低密度區(qū)域分割開(kāi)的高密度對(duì)象區(qū)域。在該算法中，發(fā)現(xiàn)一個(gè)聚類(lèi)的過(guò)程是基于這樣的事實(shí)：一個(gè)聚類(lèi)能夠被其中的任意一個(gè)核心對(duì)象所確定。其基本思想是：考察數(shù)據(jù)庫(kù)D中的某一個(gè)點(diǎn)P，若P是核心點(diǎn)，則通過(guò)區(qū)域查詢得到該點(diǎn)的鄰域，鄰域中的點(diǎn)和P同屬于一個(gè)類(lèi)，這些點(diǎn)將作為下一輪的考察對(duì)象(即種子點(diǎn))，并通過(guò)不斷地對(duì)種子點(diǎn)進(jìn)行區(qū)域查詢來(lái)擴(kuò)展它們所在的類(lèi)，直至找到一個(gè)完整的類(lèi)。然后，依此過(guò)程尋找其他的類(lèi)。最后剩下的不屬于任何類(lèi)的點(diǎn)即為噪聲。DBSCAN算法可以挖掘任意形狀的聚類(lèi)，對(duì)數(shù)據(jù)輸入順序不敏感，并且具有處理異常數(shù)據(jù)(噪音)的能力。對(duì)具有N個(gè)樣本的數(shù)據(jù)庫(kù)，該算法的時(shí)間復(fù)雜性為O(NlogN)。
2 M-DBSCAN算法
2.1 在線聚類(lèi)
由于處理數(shù)據(jù)量較大，一次性處理完畢不但運(yùn)算量大，復(fù)雜度高，而且對(duì)存儲(chǔ)空間的需求量大，因此本文提出一種在線式聚類(lèi)算法，可以動(dòng)態(tài)增加聚類(lèi)數(shù)目。
算法的原理是：隨著輸入樣本數(shù)據(jù)的不斷增加，實(shí)時(shí)動(dòng)態(tài)地增加聚類(lèi)個(gè)數(shù)或調(diào)整聚類(lèi)中心及聚類(lèi)半徑，在形成的任意一個(gè)聚類(lèi)中，聚類(lèi)中心與屬于此聚類(lèi)的樣本點(diǎn)的相似度都不小于一個(gè)閾值dthr，dthr的選取將直接影響到聚類(lèi)數(shù)目。
將在線式聚類(lèi)算法引入后，算法的描述如下：
(1)積累一小段時(shí)間內(nèi)的數(shù)據(jù)，進(jìn)行歸一化壓縮，進(jìn)行相似度計(jì)算，得到相似度矩陣；
(2)通過(guò)對(duì)相似度矩陣進(jìn)行比較分析，找出鄰域密度最大的數(shù)據(jù)點(diǎn)作為第一個(gè)初始類(lèi)的中心c1；
(3)對(duì)尚未加入此類(lèi)的數(shù)據(jù)點(diǎn)xi，比較與類(lèi)中心的距離是否大于給定閾值dthr，若是，則加入此類(lèi)，否則創(chuàng)建一個(gè)新類(lèi)cj；
(4)處理完這一小段數(shù)據(jù)后，對(duì)新到來(lái)的一個(gè)數(shù)據(jù)點(diǎn)進(jìn)行與(3)相同的做法，確定其類(lèi)別；
(5)直到?jīng)]有數(shù)據(jù)到來(lái)為止，輸出聚類(lèi)結(jié)果。
2.2 改進(jìn)的算法
DBSCAN算法在對(duì)類(lèi)的劃分時(shí)采用的方法是：比較此數(shù)據(jù)點(diǎn)到各類(lèi)中心的距離，若小于某閾值，則屬于此類(lèi)。可見(jiàn)閾值的選擇直接影響類(lèi)的劃分及類(lèi)的數(shù)目。但是如圖1所產(chǎn)生的聚類(lèi)模塊[3]所示，這種方法帶來(lái)的問(wèn)題就是：距離近的不一定屬于同一類(lèi)，在閾值半徑內(nèi)的不一定屬于同一類(lèi)。
針對(duì)此問(wèn)題,本文提出一種改進(jìn)的算法M-DBSCAN。首先實(shí)現(xiàn)在線聚類(lèi)，可以動(dòng)態(tài)調(diào)整聚類(lèi)的數(shù)目；之后，通過(guò)將數(shù)據(jù)點(diǎn)到類(lèi)的平均距離與類(lèi)內(nèi)平均距離以及新半徑與原半徑作比較進(jìn)行雙重判決，確定數(shù)據(jù)點(diǎn)是否可以加入此類(lèi)中，以實(shí)時(shí)調(diào)整閾值半徑，解決了類(lèi)劃分錯(cuò)誤的問(wèn)題。
改進(jìn)后整個(gè)算法描述如下：
(1)積累一小段時(shí)間內(nèi)的數(shù)據(jù)，得到相似度矩陣
(2)給定閾值dthr，找出鄰域密度最大的數(shù)據(jù)點(diǎn)作為第一個(gè)初始類(lèi)的中心c1，計(jì)算S中每行值大于dthr的個(gè)數(shù)，個(gè)數(shù)最多的行號(hào)即為第一個(gè)類(lèi)的中心，將第一類(lèi)中的數(shù)據(jù)點(diǎn)存放到矩陣S’(n×n+2)的第一行，每行中的第一個(gè)為類(lèi)中心，計(jì)算類(lèi)的平均半徑r，同時(shí)計(jì)算此類(lèi)的平均距離d2，放到最后兩位。
(3)對(duì)尚未加入的數(shù)據(jù)點(diǎn)，計(jì)算某一個(gè)數(shù)據(jù)點(diǎn)到類(lèi)c1中的所有點(diǎn)的平均距離d1，類(lèi)的平均距離d2；
若d1<d2，則判斷加入此數(shù)據(jù)后類(lèi)的半徑是否變大；如果變小，將數(shù)據(jù)點(diǎn)加入此類(lèi)，同時(shí)改變此類(lèi)的平均半徑；否則尋找下一個(gè)聚類(lèi)，計(jì)算同上。
如果不能加入到任何一個(gè)已有聚類(lèi)，則創(chuàng)建一個(gè)新的類(lèi)，將其存入S’中。直到?jīng)]有新數(shù)據(jù)到來(lái)，算法結(jié)束。
部分偽代碼：
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’
}
3 算法性能及分析
對(duì)M-DBSCAN算法的性能作了測(cè)試，并與DBSCAN作了比較。所有的測(cè)試都在1臺(tái)PC機(jī)上進(jìn)行,配置P4，2.0 GHz CPU，512 MB內(nèi)存，80 GB硬盤(pán),算法用Matlab7.3實(shí)現(xiàn)。
測(cè)試數(shù)據(jù)集同時(shí)使用了真實(shí)數(shù)據(jù)和自行構(gòu)造的模擬數(shù)據(jù)，真實(shí)數(shù)據(jù)采用SEQUOIA 2000數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)也被參考文獻(xiàn)[4]用于對(duì)算法的性能測(cè)試。
首先用構(gòu)造的模擬數(shù)據(jù)對(duì)聚類(lèi)結(jié)果進(jìn)行驗(yàn)證。圖2為DBSCAN算法在閾值半徑為20時(shí)得到的結(jié)果，明顯地將不同的三類(lèi)作為一類(lèi)輸出，形成了錯(cuò)誤的類(lèi)劃分；而在取同樣的初始閾值半徑時(shí)，圖3可以看出M-DBSCAN算法得到更好的聚類(lèi)結(jié)果。
從圖4中可以看到兩種算法在SEQUOIA 2000數(shù)據(jù)庫(kù)上對(duì)不同數(shù)據(jù)量樣本的執(zhí)行時(shí)間的比較。算法M-DBSCAN比算法DBSCAN快得多，且隨著數(shù)據(jù)量的不斷增大，這種速度上的差別越來(lái)越大。表1為兩種算法的錯(cuò)誤率比較圖，錯(cuò)誤率為
，N1為算法所得聚類(lèi)數(shù)目，N2為實(shí)際聚類(lèi)數(shù)目。表1中可看出,改進(jìn)的M-DBSCAN算法錯(cuò)誤概率普遍要小于DBSCAN的，表明改進(jìn)后的算法減小了錯(cuò)誤率,對(duì)處理大樣本集有較好的性能。
表2中的測(cè)試數(shù)據(jù)集來(lái)自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[6]雖然有較短的運(yùn)行時(shí)間，但是存在大量的噪音點(diǎn)，所以從綜合性能上比較M-DBSCAN更加完善，聚類(lèi)質(zhì)量更高。
本文討論了一種將DBSCAN聚類(lèi)算法進(jìn)行改進(jìn)的M-DBSCAN聚類(lèi)算法，它克服了DBSCAN聚類(lèi)算法不能處理大數(shù)據(jù)集的問(wèn)題，并實(shí)現(xiàn)可以對(duì)閾值進(jìn)行實(shí)時(shí)更改。試驗(yàn)結(jié)果顯示，M-DBSCAN算法的準(zhǔn)確性比DBSCAN算法要好，處理大數(shù)據(jù)集的速度更快。但是對(duì)于聚類(lèi)數(shù)目的確定仍然是判斷是否超過(guò)某閾值才可算作某一類(lèi)的標(biāo)準(zhǔn)，聚類(lèi)數(shù)目與閾值的選擇有很大關(guān)系。因此如何自動(dòng)確定聚類(lèi)數(shù)目將是下一步工作的方向。
參考文獻(xiàn)
[1] ESTER M，KRIEGEL H P，SANDER J，et a1． A densitybased algorithm for discovering cluster in large spatial databases with noise[A]． In：SIMOUDIS E，HAN J， FAYYAD U． Proeeedins of the 2nd International Conference Knowledge Discovering in Databases and Data Mining (KDD-96)[C]．Massachusetts：AAAI Press．1996:226-232．
[2] HAN Jia Wei，KAMBER M． Data mining，ovncepts and Techniques[M]．CA：Morgan Kaufmann Publishers，2000．
[3] 朱蔚恒，印鑒，謝益煌．基于數(shù)據(jù)流的任意形狀聚類(lèi)算法[J]．軟件學(xué)報(bào)，2006，17(3)：379-386．
[4] 忻凌，倪志偉，黃玲.基于數(shù)據(jù)流的BIRCH改進(jìn)聚類(lèi)算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（5）：121-123
[5] 田地，王世卿.數(shù)據(jù)挖掘中基于密度和距離聚類(lèi)算法設(shè)計(jì)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（10）：254-257.
[6] 陳燕，耿國(guó)華，鄭建國(guó).一種改進(jìn)的基于密度的聚類(lèi)算法.微機(jī)發(fā)展，2005，15(3).
[7] 王翠茹，朵春紅.一種改進(jìn)的基于密度的DBSCAN聚類(lèi)算法.廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，25（4）.
[8] 周水庚，周傲英，曹晶． 基于數(shù)據(jù)分區(qū)的DBSCAN算法[J]．計(jì)算機(jī)研究與發(fā)展，2000，37(10)：1153-1159.