基于密度的統(tǒng)計(jì)合并聚類算法

劉貝貝，馬儒寧，丁軍娣

（1．南京航空航天大學(xué)理學(xué)院，江蘇南京211100；2．南京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南京210094）

基于密度的統(tǒng)計(jì)合并聚類算法

劉貝貝1，馬儒寧1，丁軍娣2

（1．南京航空航天大學(xué)理學(xué)院，江蘇南京211100；2．南京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南京210094）

針對(duì)現(xiàn)有聚類算法處理噪聲能力差和速度較慢的問(wèn)題，提出了一種基于密度的統(tǒng)計(jì)合并聚類算法（DSMC）。該算法將數(shù)據(jù)點(diǎn)的每一個(gè)特征看作一組獨(dú)立隨機(jī)變量，根據(jù)獨(dú)立有限差分不等式得出統(tǒng)計(jì)合并判定準(zhǔn)則；同時(shí)，結(jié)合數(shù)據(jù)點(diǎn)的密度信息，把密度從大到小的排序作為凝聚過(guò)程中的合并順序，實(shí)現(xiàn)了各類數(shù)據(jù)點(diǎn)的統(tǒng)計(jì)合并。人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，DSMC算法不僅可以處理凸?fàn)顢?shù)據(jù)集，對(duì)于非凸、重疊、加入噪聲的數(shù)據(jù)集也有良好的聚類效果，充分表明了該算法的適用性和有效性。

數(shù)據(jù)點(diǎn)；密度；隨機(jī)變量；合并；聚類；噪聲

聚類［1?2］是數(shù)據(jù)挖掘領(lǐng)域中十分重要的數(shù)據(jù)分析技術(shù)。具體來(lái)說(shuō)，聚類就是將給定的數(shù)據(jù)集劃分成互不相交的非空子集的過(guò)程。由于初始條件和聚類準(zhǔn)則的不唯一性，使得各種各樣的聚類算法應(yīng)運(yùn)而生。根據(jù)算法形成方式的不同，可以將其分為2大類：基于劃分的聚類算法和基于層次的聚類算法［3］?；趧澐值木垲愃惴ㄒ部梢苑Q為分割聚類算法，它的主要特點(diǎn)是在對(duì)數(shù)據(jù)集進(jìn)行分類之前，需要事先確定聚類個(gè)數(shù)，然后將數(shù)據(jù)集劃分到確定好的各類別中。根據(jù)劃分過(guò)程中數(shù)據(jù)點(diǎn)類別歸屬的明確性，又可將分割聚類分為硬聚類和模糊聚類［4］。

硬聚類中數(shù)據(jù)點(diǎn)的類別歸屬是明確的。每個(gè)數(shù)據(jù)點(diǎn)對(duì)各類別的隸屬度取0或1，即一個(gè)數(shù)據(jù)點(diǎn)必須屬于某一類別且只能屬于該類別。硬聚類的數(shù)學(xué)定義描述如下：設(shè)給定的數(shù)據(jù)集為X＝｛x1，x2，…，xn｝∈Rn×d，xi（i＝1，2，…，n）表示第i個(gè)數(shù)據(jù)點(diǎn)。預(yù)先確定將X劃分為k個(gè)子集C＝｛C1，C2，…，Ck｝（k≤n），則Ci滿足如下條件：1）Ci≠?，（i＝1，2，…，k），即每一子集至少含有一個(gè)數(shù)據(jù)點(diǎn)；2）Ci∩Cj＝?，（1≤i≠j≤k），即每個(gè)數(shù)據(jù)點(diǎn)只能屬于一個(gè)子集；3）即每個(gè)數(shù)據(jù)點(diǎn)必須歸屬于某一子集。數(shù)據(jù)點(diǎn)xj（j＝1，2，…，n）對(duì)子集Ci（i＝1，2，…，k）的隸屬關(guān)系可用隸屬函數(shù)uij表示，當(dāng)uij＝1時(shí)，xj∈Ci，當(dāng)uij＝0時(shí)，xj?Ci，其中隸屬函數(shù)uij∈｛0，1｝且滿足硬聚類的代表算法有K?means算法［5］和Ncuts（normal?ized cuts）算法［6］。二者都是致力于得到使目標(biāo)函數(shù)達(dá)到最值的最優(yōu)聚類。K?means算法取誤差平方和函數(shù)作為目標(biāo)函數(shù)，對(duì)初始聚類中心和異常點(diǎn)較為敏感，且面對(duì)非凸數(shù)據(jù)集易陷入局部最優(yōu)。Ncuts算法取規(guī)范割函數(shù)為目標(biāo)函數(shù)，將數(shù)據(jù)集的聚類問(wèn)題轉(zhuǎn)化為空間中帶權(quán)無(wú)向圖的最優(yōu)劃分問(wèn)題。Ncuts算法可以聚類任意形狀的數(shù)據(jù)，但大數(shù)據(jù)聚類問(wèn)題對(duì)其相似性矩陣的存儲(chǔ)和特征向量的計(jì)算都是種挑戰(zhàn)。

在模糊聚類中，數(shù)據(jù)點(diǎn)的類別歸屬是不明確的，一個(gè)數(shù)據(jù)點(diǎn)可以屬于所有類別。模糊聚類隸屬度的取值由硬聚類中只能取0或1變?yōu)榭梢匀。?，1］的任意值，該值用來(lái)表示每個(gè)數(shù)據(jù)點(diǎn)屬于各個(gè)類別的可能性，仍然滿足任意數(shù)據(jù)點(diǎn)對(duì)所有類別的隸屬度之和為1。代表性的模糊聚類算法有FCM算法［7］和PCM（possibilitic C means）算法［8］。FCM算法利用數(shù)據(jù)點(diǎn)對(duì)每一類別的隸屬度構(gòu)成了一個(gè)隸屬矩陣，然后將算法的目標(biāo)函數(shù)轉(zhuǎn)變?yōu)橐粋€(gè)與隸屬矩陣相關(guān)的函數(shù)，通過(guò)優(yōu)化該目標(biāo)函數(shù)完成聚類。為克服FCM對(duì)噪聲敏感的缺點(diǎn)，Krishnapuram和Keller提出了PCM算法。該算法舍棄了FCM算法中每一點(diǎn)對(duì)各類別隸屬度總和為1的約束條件，使得噪聲點(diǎn)具有很小的隸屬度值，從而增加了算法對(duì)噪聲的魯棒性。

層次聚類算法又稱為樹(shù)聚類算法。它的主要思想是對(duì)給定的數(shù)據(jù)集依照相似性矩陣進(jìn)行層次分解，使得聚類結(jié)果可以由二叉樹(shù)或系統(tǒng)樹(shù)圖來(lái)描述，即樹(shù)狀嵌套結(jié)構(gòu)為H＝｛H1，H2，…，Hq｝，（q≤n），n為數(shù)據(jù)點(diǎn)的個(gè)數(shù)，當(dāng)Ci∈Hm，Cj∈Hl且m＞l，有Ci∈Cj或Ci∩Cj＝?對(duì)所有i成立，j≠i，m，l＝1，2，…，q。層次聚類算法又分為分裂式和凝聚式2種。

分裂式層次聚類算法采用“自頂向下”的方式進(jìn)行。將數(shù)據(jù)集看作一類，根據(jù)類內(nèi)最大相似性的原則將數(shù)據(jù)集逐漸細(xì)分，直到滿足終止條件或每一個(gè)數(shù)據(jù)點(diǎn)構(gòu)成一類時(shí)停止分裂，例如MONA（mono?thetic analysis）算法［9］和DIANA（divisive analysis）算法［9］等。

凝聚式層次聚類算法［10］采用“自底向上”的方式進(jìn)行。一開(kāi)始將數(shù)據(jù)集的每個(gè)數(shù)據(jù)點(diǎn)看作一類，然后進(jìn)行一系列的合并操作，直到滿足終止條件或所有數(shù)據(jù)點(diǎn)歸為一類時(shí)停止凝聚。大部分層次聚類算法都是采用凝聚式聚類，代表性的算法有基于代表點(diǎn)的CURE算法［11］、基于稠密點(diǎn)的DBSCAN算法［12］、NBC（neighborhood based clustering）算法［13］、以及基于核心點(diǎn)的MulCA（multilevel core?sets based aggregation）算法［14］等。

隨著信息技術(shù)的迅猛發(fā)展，數(shù)據(jù)源開(kāi)始不斷膨脹，數(shù)據(jù)結(jié)構(gòu)也變得日漸復(fù)雜，具有類內(nèi)相異、類間相似、噪聲和重疊現(xiàn)象的數(shù)據(jù)集層出不窮，這對(duì)于計(jì)算機(jī)領(lǐng)域中一些易受噪聲點(diǎn)和數(shù)據(jù)集大小影響的經(jīng)典聚類算法（如K?means、Ncuts等）來(lái)說(shuō)，是一種巨大的挑戰(zhàn)。

在尋求更優(yōu)的聚類算法的道路上，人們開(kāi)始將其他專業(yè)領(lǐng)域的知識(shí)同聚類算法相結(jié)合，統(tǒng)計(jì)思想逐步被應(yīng)用于聚類算法中。早期統(tǒng)計(jì)聚類方法有GMDD算法［15］和EM算法［16］等。GMDD算法將數(shù)據(jù)點(diǎn)和噪聲點(diǎn)看作是由不同混合高斯分布生成的點(diǎn)集，利用一個(gè)增強(qiáng)的模型模擬估計(jì)含有噪聲點(diǎn)的原始模型。EM算法是一種迭代算法，用于含有隱變量的概率參數(shù)模型的最大似然估計(jì)或極大后驗(yàn)概率估計(jì)。2004年，針對(duì)復(fù)雜的圖像分割問(wèn)題，Nock和Nielsen提出了統(tǒng)計(jì)區(qū)域合并算法（statistical region merging，SRM）［17］。具體地，該算法將像素點(diǎn)作為最基本的區(qū)域，把像素的3個(gè)顏色特征看做3組獨(dú)立隨機(jī)變量，對(duì)每一組獨(dú)立隨機(jī)變量，根據(jù)獨(dú)立有限差分不等式得出合并的判定準(zhǔn)則，利用像素點(diǎn)梯度值從小到大的排序獲得合并順序，依據(jù)合并準(zhǔn)則和合并順序，結(jié)合像素或區(qū)域進(jìn)行迭代生長(zhǎng)。通過(guò)控制每組獨(dú)立隨機(jī)變量的個(gè)數(shù)，SRM算法實(shí)現(xiàn)了對(duì)復(fù)雜圖像中目標(biāo)的快速分割和有效提取。

受SRM方法的啟發(fā)，本文提出了一種基于密度的統(tǒng)計(jì)合并聚類算法（density?based statistical mer?ging clustering，DSMC），該算法主要包括2個(gè)步驟：

1）根據(jù)數(shù)據(jù)點(diǎn)的密度信息獲得合并順序及每一數(shù)據(jù)點(diǎn)的k鄰域。首先利用數(shù)據(jù)點(diǎn)的空間位置信息及多維特征信息，計(jì)算數(shù)據(jù)點(diǎn)之間的相似性得到相似性矩陣，確定每一數(shù)據(jù)點(diǎn)的k鄰域。然后將稠密點(diǎn)與其k鄰域中所有點(diǎn)的相似性的最小值作為數(shù)據(jù)點(diǎn)的密度信息，將密度從大到小的排序作為合并的順序。

2）按照合并順序依次將稠密點(diǎn)與其k鄰域中的數(shù)據(jù)點(diǎn)進(jìn)行合并判定。將數(shù)據(jù)點(diǎn)的每個(gè)特征看作一組獨(dú)立隨機(jī)變量，根據(jù)獨(dú)立有限差分不等式得出的合并判定準(zhǔn)則判斷兩點(diǎn)是否合并。當(dāng)2個(gè)數(shù)據(jù)點(diǎn)對(duì)其任意的特征具有相同的期望時(shí)，劃分為同一類別；當(dāng)2個(gè)數(shù)據(jù)點(diǎn)對(duì)其特征至少有一個(gè)期望顯著不同時(shí)，劃分為不同類別。遍歷所有的稠密點(diǎn)，實(shí)現(xiàn)對(duì)數(shù)據(jù)集的分類。

相比于上述基于密度的凝聚聚類算法（如DB?SCAN、NBC）DSMC算法在數(shù)據(jù)點(diǎn)生長(zhǎng)合并的過(guò)程中，不僅利用了數(shù)據(jù)點(diǎn)的密度信息，還利用了根據(jù)統(tǒng)計(jì)判定準(zhǔn)則得出的數(shù)據(jù)點(diǎn)每一個(gè)特征的差異性信息。因此，該算法對(duì)噪聲具有更好的魯棒性，也對(duì)不規(guī)則形狀的數(shù)據(jù)集和密度不均勻的數(shù)據(jù)集具有更好的聚類效果。

1 DSM

1．1 統(tǒng)計(jì)模型的建立

設(shè)給定的數(shù)據(jù)集為X，包含n個(gè)數(shù)據(jù)點(diǎn)，每個(gè)數(shù)據(jù)點(diǎn)含有多個(gè)特征信息，用Ω＝｛A，B，C，…｝表示特征集合，每個(gè)特征的取值范圍為［Li，Ui］（i＝A，B，C，…）。為方便應(yīng)用，對(duì)數(shù)據(jù)集X作整體移動(dòng)（特征信息整體改變不影響分類），使得特征的取值范圍變?yōu)椋?，gi］（i＝A，B，C，…），其中g(shù)i＝｜Ui－Li｜。然后，將數(shù)據(jù)點(diǎn)的每一個(gè)特征用Q個(gè)獨(dú)立隨機(jī)變量表示，每一個(gè)隨機(jī)變量對(duì)應(yīng)一個(gè)分布。以特征A為例，其可表示為A＝（A1，A2，…，AQ），隨機(jī)變量Aj（j＝1，2，…，Q）對(duì)應(yīng)第j個(gè)分布。由于Q個(gè)獨(dú)立隨機(jī)變量和的取值應(yīng)屬于［0，gi］（i＝A，B，C，…），則每一個(gè)隨機(jī)變量的取值為［0，gi／Q］（i＝A，B，C，…）。這樣，一個(gè)數(shù)據(jù)點(diǎn)的特征信息就由多組獨(dú)立隨機(jī)變量表示。

對(duì)于給定的數(shù)據(jù)集X，假設(shè)存在具有完美聚類結(jié)果的數(shù)據(jù)集X?，那么在X?中，最優(yōu)的聚類結(jié)果具有如下性質(zhì)：1）同一類別中的數(shù)據(jù)點(diǎn)，對(duì)于任意給定的數(shù)據(jù)特征都具有相同的期望；2）不同的類別中的數(shù)據(jù)點(diǎn)，對(duì)于任意給定的數(shù)據(jù)特征至少有一個(gè)期望不同。這一性質(zhì)在合并判定過(guò)程中起到非常重要的作用。

圖1 2個(gè)數(shù)據(jù)點(diǎn)任一特征聚類的統(tǒng)計(jì)說(shuō)明Fig．1 The statistical description of two data points clustering about any feature

該統(tǒng)計(jì)模型對(duì)數(shù)據(jù)點(diǎn)及數(shù)據(jù)點(diǎn)特征的取樣是相互獨(dú)立的。對(duì)于Q個(gè)獨(dú)立隨機(jī)變量的分布沒(méi)有特定要求，即獨(dú)立不一定同分布。Q的傳統(tǒng)取值一般為1，即數(shù)據(jù)點(diǎn)的每個(gè)特征只由一個(gè)隨機(jī)變量表示，但是這一取值對(duì)于較小的數(shù)據(jù)集難以獲得可靠的估計(jì)信息。當(dāng)Q增大時(shí)，數(shù)據(jù)點(diǎn)的特征可以被描述的更加細(xì)致，因此，Q成為該算法的重要參數(shù)之一。調(diào)整參數(shù)Q，不僅可以改變算法的統(tǒng)計(jì)復(fù)雜性，還可以控制分類的精確度。將Q的取值從小調(diào)大，可以建立一個(gè)層次由粗到細(xì)的數(shù)據(jù)聚類結(jié)果。

1．2 統(tǒng)計(jì)合并判定

DSM算法對(duì)數(shù)據(jù)點(diǎn)的合并由一個(gè)特定的統(tǒng)計(jì)合并判定準(zhǔn)則決定。為了簡(jiǎn)單起見(jiàn)，先只考慮含有一個(gè)特征信息的數(shù)據(jù)集，即一個(gè)數(shù)據(jù)點(diǎn)用一組獨(dú)立隨機(jī)變量表示。在此基礎(chǔ)上，將得到的結(jié)果擴(kuò)展到具有更多的特征信息的數(shù)據(jù)集中。

為了得出統(tǒng)計(jì)合并判定準(zhǔn)則，介紹定理如下：

定理1（獨(dú)立有限差分不等式［18］） 設(shè)X＝（X1，X2，…，Xn）是一組獨(dú)立隨機(jī)變量，Xk的取值范圍為Ak（k＝1，2，…，n）。假設(shè)存在一個(gè)定義在∏kAk的實(shí)值函數(shù)f，當(dāng)變量X與X′僅在第k個(gè)條件不同時(shí)，滿足｜f (X)－f（X′）｜≤rk，則?τ≥0，有

式中：μ為f（X）的期望，即μ＝Ef（X）。

根據(jù)定理1，可以推出給定數(shù)據(jù)集X中的不同類別的絕對(duì)偏差不等式。記C為數(shù)據(jù)集X中的類別（單個(gè)數(shù)據(jù)點(diǎn)可作為一個(gè)類別），｜C｜為類別內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)，C(表示類別C與其他類別合并時(shí)的代表點(diǎn)，E（C）表示該類別相關(guān)數(shù)據(jù)點(diǎn)Q個(gè)獨(dú)立隨機(jī)變量期望和的期望。

推論1 考慮數(shù)據(jù)集X中的類別組合（C1，C2），?0＜δ≤1，下面不等式成立的概率不超過(guò)δ：

式中：g＝max (gi)（i＝A，B，C，…）。

證明 已知類別C1中的數(shù)據(jù)點(diǎn)可由Q｜C1｜個(gè)獨(dú)立隨機(jī)變量表示，類別中的數(shù)據(jù)點(diǎn)可由個(gè)獨(dú)立隨機(jī)變量表示。為實(shí)值函數(shù)，由于分別是C1，C2的代表點(diǎn)，若變動(dòng)C1中的變量，rk的最大取值為g／（Q｜C1｜），若變動(dòng)C2中的變量，rk的最大取值為g／（Q｜C2｜）。

推論得證。

由推論1可知，當(dāng)δ取值接近于零時(shí)（本文若未特別標(biāo)明，δ取為1／（6｜X｜2），類別組合滿足不等式b（C1，C2）的概率接近于1，其中；若（C，C）可以合并，說(shuō)12明在數(shù)據(jù)集X?中2者屬于同一類別，則有根據(jù)這2個(gè)前提條件得到如下統(tǒng)計(jì)合并判定準(zhǔn)則：

當(dāng)類別組合（C1，C2）滿足b（C1，C2）時(shí)，則合并（C1，C2）；反之則不然。

將該準(zhǔn)則擴(kuò)展到具有多個(gè)特征信息的數(shù)據(jù)集中，形式如下：

1．3 合并順序

建立合適的合并準(zhǔn)則后，聚類算法的結(jié)果受合并順序的影響。與隨機(jī)選取數(shù)據(jù)點(diǎn)進(jìn)行合并判定的算法不同，DSMC算法利用了數(shù)據(jù)點(diǎn)的密度信息以獲得合并順序。獲取過(guò)程可敘述如下：首先，計(jì)算數(shù)據(jù)集中任意2點(diǎn)之間的距離度量（例如歐式距離、最大／最小距離、馬氏距離等），獲得度量矩陣；然后，確定每一數(shù)據(jù)點(diǎn)的k鄰域，選取k鄰域中所有點(diǎn)與稠密點(diǎn)距離度量的最大值，作為稠密點(diǎn)的局部密度信息；最后，根據(jù)獲得的局部密度信息，將所有數(shù)據(jù)點(diǎn)按密度從大到小排序，得到算法的合并順序。在整個(gè)算法過(guò)程中，基于密度的合并順序保證了在任意2個(gè)不同的類別進(jìn)行合并判定時(shí)，其自身已經(jīng)完成所有可能的合并。

由上述合并順序的獲取過(guò)程可以看出，k鄰域大小的選擇直接影響了數(shù)據(jù)點(diǎn)密度的大小，進(jìn)而影響了DSMC算法的合并順序。因此，k鄰域的大小也被看作是DSMC算法的一個(gè)重要參數(shù)。

在該算法中，密度的大小不僅受到k鄰域的影響，也會(huì)受到距離度量f（x，y）的影響。針對(duì)不同特征的數(shù)據(jù)集，選取合適的f（x，y）可以得到更好的聚類結(jié)果。在算法中較為常見(jiàn)的距離度量有歐式距離，馬氏距離，最大／最小值距離等。本文實(shí)驗(yàn)中主要應(yīng)用一種距離度量，它利用數(shù)據(jù)點(diǎn)最大特征差異進(jìn)行排序，使得B，C，…），K（x）表示點(diǎn)x的k鄰域。隨機(jī)生成含有20個(gè)點(diǎn)的數(shù)據(jù)集，選取k鄰域大小為4，利用上述距離度量，得到DSMC算法的合并順序如圖2所示。

圖2 DSMC算法的合并順序Fig．2 Merging order of DSMC algorithm

2 DSMC算法的實(shí)現(xiàn)

2．1 DSMC算法的實(shí)現(xiàn)細(xì)節(jié)

通過(guò)對(duì)DSMC算法的詳細(xì)介紹可知，DSMC算法主要通過(guò)2個(gè)步驟實(shí)現(xiàn)：步驟1是根據(jù)數(shù)據(jù)點(diǎn)的密度信息獲得合并順序及每一數(shù)據(jù)點(diǎn)的k鄰域；步驟2是按照合并順序依次將稠密點(diǎn)與其k鄰域中的數(shù)據(jù)點(diǎn)進(jìn)行合并判定，通過(guò)遍歷所有的稠密點(diǎn)完成數(shù)據(jù)的聚類。其中，為更好地處理噪聲點(diǎn)，在步驟2中只對(duì)α比例的數(shù)據(jù)（本文默認(rèn)α＝0．9）進(jìn)行統(tǒng)計(jì)判定，剩余數(shù)據(jù)點(diǎn)根據(jù)臨近數(shù)據(jù)點(diǎn)的類別標(biāo)號(hào)。根據(jù)這2個(gè)步驟的內(nèi)容，具體說(shuō)明DSMC算法的聚類過(guò)程如下。

步驟1：計(jì)算數(shù)據(jù)點(diǎn)的合并順序并獲得數(shù)據(jù)點(diǎn)的k鄰域。

輸入：數(shù)據(jù)集X；k鄰域中數(shù)據(jù)點(diǎn)個(gè)數(shù)k。

1）計(jì)算數(shù)據(jù)集中任意兩個(gè)點(diǎn)距離，存入矩陣D。

2）將矩陣D按列進(jìn)行升序排列，存入矩陣D1，其第k行按升序排列，得到密度從大到小的順序d。

3）根據(jù)順序d確定數(shù)據(jù)點(diǎn)的k鄰域。

輸出：合并順序d；k鄰域矩陣W。

步驟2：將稠密點(diǎn)與其k鄰域中的數(shù)據(jù)點(diǎn)進(jìn)行合并判定，然后合并剩余點(diǎn)完成聚類。

輸入：數(shù)據(jù)集X；合并順序d；k鄰域矩陣W。

1）對(duì)數(shù)據(jù)集中90%的數(shù)據(jù)點(diǎn)（稠密點(diǎn)）進(jìn)行合并判定。

b）計(jì)算統(tǒng)計(jì)判定準(zhǔn)則的臨界值b（C1，C2）（推論1），若滿足統(tǒng)計(jì)合并判定準(zhǔn)則，則合并；若不滿足，則進(jìn)行下一組合并判斷，直到遍歷完k鄰域內(nèi)所有的點(diǎn)；

c）重復(fù)步驟a）和b），直到遍歷完數(shù)據(jù)集X中所有的稠密點(diǎn)。

2）對(duì)剩余的10%的數(shù)據(jù)點(diǎn)進(jìn)行近鄰合并。

b）判斷其k鄰域內(nèi)點(diǎn)的分類情況。若有已分類的點(diǎn)，且其k鄰域中屬于該類別的點(diǎn)數(shù)最多，則將歸于該類別；若沒(méi)有已分類的點(diǎn)，則不作改變；

c）重復(fù)步驟a）和b），直到遍歷完剩余所有的數(shù)據(jù)點(diǎn)。

3）計(jì)算數(shù)據(jù)集X的分類個(gè)數(shù)nbcluster。

輸出：聚類個(gè)數(shù)nbcluster。

由高斯分布隨機(jī)生成一個(gè)可被分為2類的數(shù)據(jù)集X，其含40個(gè)數(shù)據(jù)點(diǎn)。用DSMC算法（參數(shù)k和Q取為5，15）對(duì)數(shù)據(jù)集X進(jìn)行聚類，具體過(guò)程如圖3所示。過(guò)程①對(duì)于給定的數(shù)據(jù)集X計(jì)算合并順序，得到首要稠密點(diǎn)及其k鄰域；過(guò)程②按照數(shù)據(jù)集的合并順序，依次對(duì)稠密點(diǎn)和其k鄰域中的點(diǎn)進(jìn)行統(tǒng)計(jì)合并判定得到聚類結(jié)果；過(guò)程③根據(jù)臨近數(shù)據(jù)點(diǎn)的類別對(duì)噪聲點(diǎn)進(jìn)行聚類，比較其k鄰域中各類別點(diǎn)的個(gè)數(shù)，將它歸為點(diǎn)數(shù)最多類別。

圖3 DSMC算法的聚類過(guò)程Fig．3 Clustering process of DSMC algorithm

2．2 計(jì)算復(fù)雜度分析

由上述聚類過(guò)程可知，DSMC算法的計(jì)算量主要集中于2個(gè)步驟：

1）構(gòu)建數(shù)據(jù)點(diǎn)的距離度量矩陣；

2）統(tǒng)計(jì)合并判定時(shí)對(duì)稠密點(diǎn)及其k鄰域的迭代。

對(duì)于步驟1），給定含有n個(gè)點(diǎn)的數(shù)據(jù)集，距離度量矩陣的計(jì)算復(fù)雜度為O（n2）；對(duì)于步驟2），遍歷數(shù)據(jù)集中所有稠密點(diǎn)，將當(dāng)前稠密點(diǎn)依次與其k鄰域中的點(diǎn)進(jìn)行統(tǒng)計(jì)合并判定，由于k鄰域內(nèi)點(diǎn)的最大迭代次數(shù)為k，因此，步驟2）的計(jì)算復(fù)雜度為O（kn）。一般地，k的取值遠(yuǎn)小于n，則DSMC算法的計(jì)算復(fù)雜度可近似于距離度量矩陣的計(jì)算復(fù)雜度O（n2）。

3 實(shí)驗(yàn)比較與評(píng)價(jià)

將DSMC算法同3種經(jīng)典聚類算法作比較，它們分別是通過(guò)聚類中心實(shí)現(xiàn)的K?means算法、基于圖論的Ncuts算法和基于密度的DBSCAN算法。針對(duì)具有不同形狀，不同重疊程度和不同噪聲點(diǎn)數(shù)的人工數(shù)據(jù)集以及部分真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。進(jìn)一步地，對(duì)本文提出的DSMC算法的參數(shù)選擇進(jìn)行了實(shí)驗(yàn)分析。

由于不同的算法具有不同的參數(shù)，在3．1～3．5節(jié)的實(shí)驗(yàn)中，實(shí)驗(yàn)參數(shù)設(shè)置如下：

1）K?means和Ncuts算法：只有1個(gè)參數(shù)，即想要達(dá)到的聚類個(gè)數(shù)。一般地，實(shí)驗(yàn)中將數(shù)據(jù)集真實(shí)的聚類個(gè)數(shù)取為參數(shù)值。

2）DBSCAN算法：共有2個(gè)參數(shù)，一個(gè)是點(diǎn)的鄰域半徑r，一個(gè)是鄰域內(nèi)點(diǎn)的個(gè)數(shù)閾值m。在實(shí)驗(yàn)中，m一般取10左右的數(shù)，鄰域半徑r則根據(jù)數(shù)據(jù)集的直徑做決定。

3）DSMC算法：共有2個(gè)參數(shù)，分別是鄰域內(nèi)點(diǎn)的個(gè)數(shù)k和劃分尺度參數(shù)Q。參數(shù)k的取值一般根據(jù)數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的總個(gè)數(shù)確定。一般初始值取10左右。對(duì)于該方法特有的參數(shù)Q，它控制了算法對(duì)數(shù)據(jù)集的劃分細(xì)度，即當(dāng)Q較小時(shí)，數(shù)據(jù)集劃分細(xì)度小，聚類個(gè)數(shù)少；當(dāng)Q較大時(shí)，數(shù)據(jù)集劃分細(xì)度大，聚類個(gè)數(shù)多。由于參數(shù)Q是一個(gè)特征獨(dú)立隨機(jī)變量的個(gè)數(shù)，因此其取值范圍為正整數(shù)，實(shí)驗(yàn)中具體取值根據(jù)數(shù)據(jù)集分類需求進(jìn)行調(diào)整，默認(rèn)初始值為1。

3．1 形狀不同的人工數(shù)據(jù)集實(shí)驗(yàn)

將4種聚類算法（K?means，Ncuts，DBSCAN，DSMC）分別應(yīng)用于4種不同形狀的人工數(shù)據(jù)集上。它們通過(guò)不同類型的高斯分布隨機(jī)生成，樣本點(diǎn)的個(gè)數(shù)從左到右第1行分別為600、900；第2行分別為660（包含60個(gè)隨機(jī)噪聲點(diǎn)），1 100（包含100個(gè)隨機(jī)噪聲點(diǎn)）。

圖4 算法對(duì)不同形狀數(shù)據(jù)集的分類結(jié)果比較Fig．4 Comparison of classification results of algorithms for different shape data sets

對(duì)任意形狀的數(shù)據(jù)集都有良好聚類效果的算法才能稱之為好的聚類算法。由圖4可以看出，K?means和Ncuts算法并不能很好的聚類非凸數(shù)據(jù)集，而DBSCAN算法（參數(shù)m和r從左到右第1行為8，0．4；7，0．7；第2行為100，48；15，0．4）和本文提出的DSMC算法（參數(shù)k和Q從左到右第1行為6，200；8，1；第2行為8，1；8，6）對(duì)任意形狀數(shù)據(jù)集的聚類效果都很令人滿意，但對(duì)于較為稀疏的數(shù)據(jù)點(diǎn)的聚類，DSMC算法相對(duì)更優(yōu)。

3．2 重疊程度不同的人工數(shù)據(jù)集實(shí)驗(yàn)

對(duì)數(shù)據(jù)重疊的魯棒性也是判斷聚類算法好壞的標(biāo)準(zhǔn)之一。本節(jié)中，通過(guò)對(duì)重疊程度逐漸增大的2類不同形狀的人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，比較4種聚類算法對(duì)數(shù)據(jù)重疊的魯棒性。其中，團(tuán)狀數(shù)據(jù)集含有600個(gè)數(shù)據(jù)點(diǎn)；環(huán)狀數(shù)據(jù)集含有1 000個(gè)數(shù)據(jù)點(diǎn)。

圖5 對(duì)不同重疊程度的團(tuán)狀和環(huán)狀數(shù)據(jù)集的分類結(jié)果比較Fig．5 Comparison of classification results on different de?gree of overlap between group and cyclicdata sets

從圖5的實(shí)驗(yàn)結(jié)果可以看出，對(duì)于團(tuán)狀數(shù)據(jù)集，K?means、Ncuts和DSMC（參數(shù)k和Q自上而下依次取為6，200；6，160）算法都能夠很好的處理重疊問(wèn)題，而DBSCAN算法（參數(shù)m和r自上而下依次取為8，0．4；10，0．6）雖然對(duì)一般的團(tuán)狀數(shù)據(jù)集聚類效果顯著，但隨著數(shù)據(jù)集重疊程度的逐漸增大，聚類效果也開(kāi)始變差。對(duì)于環(huán)狀數(shù)據(jù)集，像K?means、Ncuts這種無(wú)法很好的聚類非凸數(shù)據(jù)集的算法，對(duì)于重疊的環(huán)狀數(shù)據(jù)集一樣效果不好；而DBSCAN算法（參數(shù)m和r自上而下依次取為15，0．4；10，0．5）對(duì)環(huán)狀數(shù)據(jù)集的聚類類似于團(tuán)狀數(shù)據(jù)集，對(duì)重疊度較高的數(shù)據(jù)集不能很好地聚類；本文提出的DSMC算法（參數(shù)k和Q自上而下依次取為7，15；7，75）對(duì)于高重疊度的環(huán)狀數(shù)據(jù)集雖然沒(méi)有得到完美的聚類結(jié)果，但將內(nèi)環(huán)與外環(huán)數(shù)據(jù)歸為2類的結(jié)果基本令人滿意。相比其他3種聚類算法而言，DSMC算法對(duì)重疊的魯棒性較好。

3．3 噪聲點(diǎn)個(gè)數(shù)不同的人工數(shù)據(jù)集實(shí)驗(yàn)

隨著數(shù)據(jù)源含有噪聲現(xiàn)象的增多，算法對(duì)噪聲的處理效果也越來(lái)越受到人們的關(guān)注。為檢驗(yàn)本文提出的DSMC算法對(duì)含有噪聲的數(shù)據(jù)集的聚類效果，對(duì)逐漸增加噪聲點(diǎn)的兩類非凸數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中，第1個(gè)數(shù)據(jù)集含有400個(gè)數(shù)據(jù)點(diǎn)，第2個(gè)數(shù)據(jù)集含有1 000個(gè)數(shù)據(jù)點(diǎn)，自上而下對(duì)2個(gè)數(shù)據(jù)集分別加入100、200、300個(gè)噪聲點(diǎn)。

圖6的實(shí)驗(yàn)結(jié)果說(shuō)明，DSMC算法（參數(shù)k和Q自上而下依次取為8，1；16，70；8，70；8，6；7，8；9，20）對(duì)數(shù)據(jù)中的噪聲具有良好的魯棒性。

圖6 DSMC算法對(duì)逐漸增加噪聲點(diǎn)的數(shù)據(jù)集聚類結(jié)果Fig．6 Clustering results over the noisy data sets of DSMC algorithm

3．4 混合形狀的人工數(shù)據(jù)集實(shí)驗(yàn)

為進(jìn)一步說(shuō)明DSMC算法的有效性，將該算法應(yīng)用于混合形狀的人工數(shù)據(jù)集（凸?fàn)詈头峭範(fàn)罨旌希?，其中，該混合?shù)據(jù)集含有1 520個(gè)數(shù)據(jù)點(diǎn)，包括320個(gè)噪聲點(diǎn)。圖7表明，DSMC算法（參數(shù)k和Q為10，100）對(duì)這種密度不均勻的混合數(shù)據(jù)集也能很好地聚類。

圖7 DSMC算法對(duì)混合數(shù)據(jù)集的聚類結(jié)果Fig．7 Clustering results of DSMC algorithm for mixed data set

3．5 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

基于對(duì)人工數(shù)據(jù)集良好的聚類效果，本節(jié)繼續(xù)應(yīng)用DSMC算法對(duì)真實(shí)數(shù)據(jù)集進(jìn)行聚類，并同K?means、Ncuts、DBSCAN算法的聚類結(jié)果作比較。實(shí)驗(yàn)對(duì)象選自UCI數(shù)據(jù)庫(kù)（http：／／archive．ics．uci．edu／ml／，加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫(kù)，目前包含223個(gè)數(shù)據(jù)集）中的4個(gè)不同的數(shù)據(jù)集，分別是iris，wine，seeds，glass。4個(gè)數(shù)據(jù)集的基本特征如表1所示。

表1 真實(shí)數(shù)據(jù)集的特征描述Table 1 Characteristic description of real data sets

在實(shí)驗(yàn)中，DSMC算法中的參數(shù)k和Q自上而下依次取為6，140；8，7；6，180；6，70．DBSCAN算法中的參數(shù)m和r自上而下依次取為11，0．5；7，51；5，1．1；15，8．由表2可知，DSMC算法對(duì)iris、seeds和glass的聚類效果要好于其他3種聚類算法；對(duì)wine的聚類雖然不如Ncuts算法，但結(jié)果基本令人滿意，說(shuō)明DSMC算法對(duì)真實(shí)數(shù)據(jù)集也有良好的聚類結(jié)果。

表2 算法對(duì)真實(shí)數(shù)據(jù)集聚類結(jié)果的比較Table 2 Comparison of clustering results on real data sets

3．6 DSMC算法參數(shù)分析

DSMC算法中涉及到的2個(gè)重要參數(shù)分別是獨(dú)立隨機(jī)變量的個(gè)數(shù)Q和鄰域內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)k。

獨(dú)立隨機(jī)變量的個(gè)數(shù)Q控制了算法的分類精確度。在固定k鄰域的情況下，隨著Q取值的逐漸增大，聚類個(gè)數(shù)也會(huì)隨之增多。圖8顯示了在固定k的情況下，不同的Q值對(duì)環(huán)狀人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集iris產(chǎn)生的不同聚類效果。對(duì)于環(huán)狀人工數(shù)據(jù)集，固定k＝8，Q取1～16時(shí)數(shù)據(jù)集得到完美聚類，隨著Q值的增大，分類更加細(xì)化，聚類個(gè)數(shù)逐漸增多。對(duì)于真實(shí)數(shù)據(jù)集iris，固定k＝6，Q取1～52時(shí)數(shù)據(jù)集后2類不能被分開(kāi)，分類正確率低；當(dāng)Q增大至53～252時(shí)，后兩類被分開(kāi)，分類正確率增至最大；當(dāng)Q取252以上，類別數(shù)增加，分類正確率下降。

圖8 固定k值時(shí)，不同Q的聚類結(jié)果Fig．8 Clustering results of different Q with a fixed k value

鄰域內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)k決定了算法的合并順序，在固定Q值的情況下，隨著k鄰域的逐漸增大，聚類個(gè)數(shù)會(huì)隨之減少。圖9顯示了在固定Q的情況下，將k逐漸增大時(shí)的兩個(gè)數(shù)據(jù)集聚類效果。對(duì)于環(huán)狀人工數(shù)據(jù)集，固定Q＝1，當(dāng)k取1～7時(shí)，分類個(gè)數(shù)過(guò)多，聚類結(jié)果并不理想；當(dāng)k取8～18時(shí)，聚類結(jié)果穩(wěn)定且保持較高水平；當(dāng)k取19以上時(shí)，數(shù)據(jù)集被聚為一類，結(jié)果不理想。對(duì)于真實(shí)數(shù)據(jù)集i?ris，同人工數(shù)據(jù)集類似，當(dāng)k取53～251時(shí)，可獲得穩(wěn)定的高水平聚類結(jié)果。

圖9 固定Q值時(shí)，不同k的聚類結(jié)果Fig．9 Clustering results of different k with a fixed Q value

4 結(jié)束語(yǔ)

隨著信息技術(shù)水平的不斷提高，具有噪聲和重疊現(xiàn)象的數(shù)據(jù)源越來(lái)越多，僅限于計(jì)算機(jī)領(lǐng)域的聚類方法不能很好地處理該問(wèn)題。為此，本文提出了一種同統(tǒng)計(jì)思想相結(jié)合的快速聚類算法—DSMC算法，它使用了一個(gè)簡(jiǎn)單的合并順序和統(tǒng)計(jì)判定準(zhǔn)則，將數(shù)據(jù)點(diǎn)的每一個(gè)特征看作一組獨(dú)立隨機(jī)變量，根據(jù)獨(dú)立有限差分不等式得出統(tǒng)計(jì)合并判定準(zhǔn)則，同時(shí)，結(jié)合數(shù)據(jù)點(diǎn)的密度信息，把密度從大到小的排序作為凝聚過(guò)程中的合并順序，進(jìn)而實(shí)現(xiàn)各類數(shù)據(jù)點(diǎn)的統(tǒng)計(jì)合并。對(duì)人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集測(cè)試的實(shí)驗(yàn)結(jié)果表明，DSMC算法對(duì)于非凸?fàn)?、重疊和加入噪聲的數(shù)據(jù)集都有良好的聚類效果。

在后續(xù)的研究工作中，將進(jìn)一步推廣DSMC算法的應(yīng)用范圍，使其能夠快速、高效地處理大數(shù)據(jù)、在線數(shù)據(jù)等多種型態(tài)的復(fù)雜聚類問(wèn)題。

［1］XU Rui，WUNSCHII D．Survey of clustering algorithms［J］．IEEE Transactions on Neural Networks，2005，16（3）：645?678．

［2］JAIN A K，MURTY M N，F(xiàn)LYNN P J．Data clustering：a review［J］．Acm Computing Surveys，1999，31（2）：264?323．

［3］MURTAGH F，CONTRERAS P．Algorithms for hierarchical clustering：an overview［J］．Wiley Interdisciplinary Re?views：Data Mining and Knowledge Discovery，2012，2（1）：86?97．

［4］TSENG L Y，YANG S B．A genetic approach to the auto?matic clustering problem［J］．Pattern Recognition，2001，34（2）：415?424．

［5］FORGY E W．Cluster analysis of multivariate data：efficien?cy versus interpretability of classifications［J］．Biometrics，1965，21：768?769．

［6］SHI J，MALIK J．Normalized cuts and image segmentation［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888?905．

［7］BEZDEK J C，EHRLICH R，F(xiàn)ULL W．FCM：The fuzzy c?means clustering algorithm［J］．Computers＆Geosciences，1984，10（2?3）：191?203．

［8］KRISHNAPURAM R，KELLER J M．A possibilistic ap?proach to clustering［J］．IEEE Transactions on Fuzzy Sys?tems，1993，1（2）：98?110．

［9］ALPERT C J，KAHNG A B．Recent directions in netlist partitioning：a survey［J］．Integration，the VLSI Journal，1995，19（1）：1?81．

［10］ACKERMANN M R，BL?MER J，KUNTZE D，et al．Analysis of agglomerative clustering［J］．Algorithmica，2014，69（1）：184?215．

［11］GUHA S，RASTOGI R，SHIM K．Cure：an efficient clus?tering algorithm for large databases［J］．Information Sys?tems，2001，26（1）：35?58．

［12］ESTER M，KRIEGEL H P，SANDER J，et al．A density?based algorithm for discovering clusters in large spatial data?bases with noise［C］／／Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining．Port?land，USA，1996：226?231．

［13］ZHOU Shuigeng，ZHAO Yue，GUAN Jihong，et al．A neighborhood?based clustering algorithm［M］／／Advances in Knowledge Discovery and Data Mining．Berlin／Heidelberg：Springer，2005：361?371．

［14］馬儒寧，王秀麗，丁軍娣．多層核心集凝聚算法［J］．軟件學(xué)報(bào)，2013，24（3）：490?506．MA Runing，WANG Xiuli，DING Jundi．Multilevel core?sets based aggregation clustering algorithm［J］．Journal of Software，2013，24（3）：490?506．

［15］ZHUANG Xuan，HUANG Yan，PALANIAPPAN K，et al．Gaussian mixture density modeling，decomposition，and applications［J］．IEEE Transactions on Image Processing，1996，5（9）：1293?1302．

［16］MACLACHLAN G J，KRISHNAN T．The EM algorithm and extensions［J］．Series in Probability＆Statistics，1997，15（1）：154?156．

［17］NOCK R，NIELSEN F．Statistical region merging［J］．IEEE Transactions on Pattern Analysis and Machine Intel?ligence，2004，26（11）：1452?1458．

［18］HABIB M，MCDIARMID C，RAMIREZ?ALFONSIN J，et

al．Probabilistic methods for algorithmic discrete mathemat?ics［M］．Berlin：Springer?Verlag，1998：1?54．

Density?based statistical merging clustering algorithm

LIU Beibei1，MA Runing1，DING Jundi2

（1．College of Science，Nanjing University of Aeronautics and Astronautics，Nanjing 211100，China；2．School of Computer Science and Technology，Nanjing University of Science and Technology，Nanjing 210094，China）

The ability of existing clustering algorithms to deal with noise is poor，and the speed is slow，instead this paper proposes a density?based statistical merging clustering algorithm（DSMC）．The new algorithm takes each group of data points as a set of independent random variables，and gathers statistical criteria from the independent bounded difference inequality．Meanwhile，combined with the density information of the data points，the DSMC al?gorithm takes the descending order of the density as the merging order in the process of condensation，and thereby achieves statistical merging of different types of data points．The experimental results with both artificial datasets and real datasets show that the DSMC algorithm can not only deal with convex data set，and also has good clustering effects on nonconvex shaped，overlapped and noisy，data sets．This proves that the algorithm has good applicability and validity．

data points；density；random variable；merging；clustering algorithm；noise

劉貝貝，女，1990年生，碩士研究生，主要研究方向?yàn)槟Ｊ阶R(shí)別。

馬儒寧，男，1976年生，副教授，博士，主要研究方向?yàn)閼?yīng)用數(shù)學(xué)、模式識(shí)別。參與完成國(guó)家自然科學(xué)基金項(xiàng)目10余項(xiàng)。發(fā)表學(xué)術(shù)論文20余篇，其中被SCI、EI收錄10余篇。

丁軍娣，女，1978年生，副教授，博士，中國(guó)計(jì)算機(jī)學(xué)會(huì)會(huì)員，主要研究方向?yàn)槟Ｊ阶R(shí)別、計(jì)算機(jī)視覺(jué)。主持并完成國(guó)家自然科學(xué)基金項(xiàng)目10余項(xiàng)。發(fā)表學(xué)術(shù)論文20余篇，其中被SCI、EI收錄10余篇。

O235；TP311

A

1673?4785（2015）05?0712?10

10．11992／tis．201410028

http：／／www．cnki．net／kcms／detail／23．1538．tp．20150930．1556．016．html

劉貝貝，馬儒寧，丁軍娣．基于密度的統(tǒng)計(jì)合并聚類算法［J］．智能系統(tǒng)學(xué)報(bào)，2015，10（5）：712?721．

英文引用格式：LIU Beibei，MA Runing，DING Jundi．Density?based statistical merging clustering algorithm［J］．CAAI Transac?tions on Intelligent Systems，2015，10（5）：712?721．

2014?10?21．

日期：2015?09?30．

國(guó)家自然科學(xué)基金資助項(xiàng)目（61103058）．

丁軍娣．E?mail：dingjundi2010＠njust．edu．cn．