基于密度的統計合并聚類算法

劉貝貝，馬儒寧，丁軍娣

（1．南京航空航天大學理學院，江蘇南京211100；2．南京理工大學計算機科學與技術學院，江蘇南京210094）

基于密度的統計合并聚類算法

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

（1．南京航空航天大學理學院，江蘇南京211100；2．南京理工大學計算機科學與技術學院，江蘇南京210094）

針對現有聚類算法處理噪聲能力差和速度較慢的問題，提出了一種基于密度的統計合并聚類算法（DSMC）。該算法將數據點的每一個特征看作一組獨立隨機變量，根據獨立有限差分不等式得出統計合并判定準則；同時，結合數據點的密度信息，把密度從大到小的排序作為凝聚過程中的合并順序，實現了各類數據點的統計合并。人工數據集和真實數據集的實驗結果表明，DSMC算法不僅可以處理凸狀數據集，對于非凸、重疊、加入噪聲的數據集也有良好的聚類效果，充分表明了該算法的適用性和有效性。

數據點；密度；隨機變量；合并；聚類；噪聲

聚類［1?2］是數據挖掘領域中十分重要的數據分析技術。具體來說，聚類就是將給定的數據集劃分成互不相交的非空子集的過程。由于初始條件和聚類準則的不唯一性，使得各種各樣的聚類算法應運而生。根據算法形成方式的不同，可以將其分為2大類：基于劃分的聚類算法和基于層次的聚類算法［3］。基于劃分的聚類算法也可以稱為分割聚類算法，它的主要特點是在對數據集進行分類之前，需要事先確定聚類個數，然后將數據集劃分到確定好的各類別中。根據劃分過程中數據點類別歸屬的明確性，又可將分割聚類分為硬聚類和模糊聚類［4］。

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

在模糊聚類中，數據點的類別歸屬是不明確的，一個數據點可以屬于所有類別。模糊聚類隸屬度的取值由硬聚類中只能取0或1變為可以取［0，1］的任意值，該值用來表示每個數據點屬于各個類別的可能性，仍然滿足任意數據點對所有類別的隸屬度之和為1。代表性的模糊聚類算法有FCM算法［7］和PCM（possibilitic C means）算法［8］。FCM算法利用數據點對每一類別的隸屬度構成了一個隸屬矩陣，然后將算法的目標函數轉變為一個與隸屬矩陣相關的函數，通過優化該目標函數完成聚類。為克服FCM對噪聲敏感的缺點，Krishnapuram和Keller提出了PCM算法。該算法舍棄了FCM算法中每一點對各類別隸屬度總和為1的約束條件，使得噪聲點具有很小的隸屬度值，從而增加了算法對噪聲的魯棒性。

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

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

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

隨著信息技術的迅猛發展，數據源開始不斷膨脹，數據結構也變得日漸復雜，具有類內相異、類間相似、噪聲和重疊現象的數據集層出不窮，這對于計算機領域中一些易受噪聲點和數據集大小影響的經典聚類算法（如K?means、Ncuts等）來說，是一種巨大的挑戰。

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

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

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

2）按照合并順序依次將稠密點與其k鄰域中的數據點進行合并判定。將數據點的每個特征看作一組獨立隨機變量，根據獨立有限差分不等式得出的合并判定準則判斷兩點是否合并。當2個數據點對其任意的特征具有相同的期望時，劃分為同一類別；當2個數據點對其特征至少有一個期望顯著不同時，劃分為不同類別。遍歷所有的稠密點，實現對數據集的分類。

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

1 DSM

1．1 統計模型的建立

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

對于給定的數據集X，假設存在具有完美聚類結果的數據集X?，那么在X?中，最優的聚類結果具有如下性質：1）同一類別中的數據點，對于任意給定的數據特征都具有相同的期望；2）不同的類別中的數據點，對于任意給定的數據特征至少有一個期望不同。這一性質在合并判定過程中起到非常重要的作用。

圖1 2個數據點任一特征聚類的統計說明Fig．1 The statistical description of two data points clustering about any feature

該統計模型對數據點及數據點特征的取樣是相互獨立的。對于Q個獨立隨機變量的分布沒有特定要求，即獨立不一定同分布。Q的傳統取值一般為1，即數據點的每個特征只由一個隨機變量表示，但是這一取值對于較小的數據集難以獲得可靠的估計信息。當Q增大時，數據點的特征可以被描述的更加細致，因此，Q成為該算法的重要參數之一。調整參數Q，不僅可以改變算法的統計復雜性，還可以控制分類的精確度。將Q的取值從小調大，可以建立一個層次由粗到細的數據聚類結果。

1．2 統計合并判定

DSM算法對數據點的合并由一個特定的統計合并判定準則決定。為了簡單起見，先只考慮含有一個特征信息的數據集，即一個數據點用一組獨立隨機變量表示。在此基礎上，將得到的結果擴展到具有更多的特征信息的數據集中。

為了得出統計合并判定準則，介紹定理如下：

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

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

根據定理1，可以推出給定數據集X中的不同類別的絕對偏差不等式。記C為數據集X中的類別（單個數據點可作為一個類別），｜C｜為類別內數據點的個數，C(表示類別C與其他類別合并時的代表點，E（C）表示該類別相關數據點Q個獨立隨機變量期望和的期望。

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

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

證明 已知類別C1中的數據點可由Q｜C1｜個獨立隨機變量表示，類別中的數據點可由個獨立隨機變量表示。為實值函數，由于分別是C1，C2的代表點，若變動C1中的變量，rk的最大取值為g／（Q｜C1｜），若變動C2中的變量，rk的最大取值為g／（Q｜C2｜）。

推論得證。

由推論1可知，當δ取值接近于零時（本文若未特別標明，δ取為1／（6｜X｜2），類別組合滿足不等式b（C1，C2）的概率接近于1，其中；若（C，C）可以合并，說12明在數據集X?中2者屬于同一類別，則有根據這2個前提條件得到如下統計合并判定準則：

當類別組合（C1，C2）滿足b（C1，C2）時，則合并（C1，C2）；反之則不然。

將該準則擴展到具有多個特征信息的數據集中，形式如下：

1．3 合并順序

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

由上述合并順序的獲取過程可以看出，k鄰域大小的選擇直接影響了數據點密度的大小，進而影響了DSMC算法的合并順序。因此，k鄰域的大小也被看作是DSMC算法的一個重要參數。

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

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

2 DSMC算法的實現

2．1 DSMC算法的實現細節

通過對DSMC算法的詳細介紹可知，DSMC算法主要通過2個步驟實現：步驟1是根據數據點的密度信息獲得合并順序及每一數據點的k鄰域；步驟2是按照合并順序依次將稠密點與其k鄰域中的數據點進行合并判定，通過遍歷所有的稠密點完成數據的聚類。其中，為更好地處理噪聲點，在步驟2中只對α比例的數據（本文默認α＝0．9）進行統計判定，剩余數據點根據臨近數據點的類別標號。根據這2個步驟的內容，具體說明DSMC算法的聚類過程如下。

步驟1：計算數據點的合并順序并獲得數據點的k鄰域。

輸入：數據集X；k鄰域中數據點個數k。

1）計算數據集中任意兩個點距離，存入矩陣D。

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

3）根據順序d確定數據點的k鄰域。

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

步驟2：將稠密點與其k鄰域中的數據點進行合并判定，然后合并剩余點完成聚類。

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

1）對數據集中90%的數據點（稠密點）進行合并判定。

b）計算統計判定準則的臨界值b（C1，C2）（推論1），若滿足統計合并判定準則，則合并；若不滿足，則進行下一組合并判斷，直到遍歷完k鄰域內所有的點；

c）重復步驟a）和b），直到遍歷完數據集X中所有的稠密點。

2）對剩余的10%的數據點進行近鄰合并。

b）判斷其k鄰域內點的分類情況。若有已分類的點，且其k鄰域中屬于該類別的點數最多，則將歸于該類別；若沒有已分類的點，則不作改變；

c）重復步驟a）和b），直到遍歷完剩余所有的數據點。

3）計算數據集X的分類個數nbcluster。

輸出：聚類個數nbcluster。

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

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

2．2 計算復雜度分析

由上述聚類過程可知，DSMC算法的計算量主要集中于2個步驟：

1）構建數據點的距離度量矩陣；

2）統計合并判定時對稠密點及其k鄰域的迭代。

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

3 實驗比較與評價

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

由于不同的算法具有不同的參數，在3．1～3．5節的實驗中，實驗參數設置如下：

1）K?means和Ncuts算法：只有1個參數，即想要達到的聚類個數。一般地，實驗中將數據集真實的聚類個數取為參數值。

2）DBSCAN算法：共有2個參數，一個是點的鄰域半徑r，一個是鄰域內點的個數閾值m。在實驗中，m一般取10左右的數，鄰域半徑r則根據數據集的直徑做決定。

3）DSMC算法：共有2個參數，分別是鄰域內點的個數k和劃分尺度參數Q。參數k的取值一般根據數據集中數據點的總個數確定。一般初始值取10左右。對于該方法特有的參數Q，它控制了算法對數據集的劃分細度，即當Q較小時，數據集劃分細度小，聚類個數少；當Q較大時，數據集劃分細度大，聚類個數多。由于參數Q是一個特征獨立隨機變量的個數，因此其取值范圍為正整數，實驗中具體取值根據數據集分類需求進行調整，默認初始值為1。

3．1 形狀不同的人工數據集實驗

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

圖4 算法對不同形狀數據集的分類結果比較Fig．4 Comparison of classification results of algorithms for different shape data sets

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

3．2 重疊程度不同的人工數據集實驗

對數據重疊的魯棒性也是判斷聚類算法好壞的標準之一。本節中，通過對重疊程度逐漸增大的2類不同形狀的人工數據集進行實驗，比較4種聚類算法對數據重疊的魯棒性。其中，團狀數據集含有600個數據點；環狀數據集含有1 000個數據點。

圖5 對不同重疊程度的團狀和環狀數據集的分類結果比較Fig．5 Comparison of classification results on different de?gree of overlap between group and cyclicdata sets

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

3．3 噪聲點個數不同的人工數據集實驗

隨著數據源含有噪聲現象的增多，算法對噪聲的處理效果也越來越受到人們的關注。為檢驗本文提出的DSMC算法對含有噪聲的數據集的聚類效果，對逐漸增加噪聲點的兩類非凸數據集進行實驗。其中，第1個數據集含有400個數據點，第2個數據集含有1 000個數據點，自上而下對2個數據集分別加入100、200、300個噪聲點。

圖6的實驗結果說明，DSMC算法（參數k和Q自上而下依次取為8，1；16，70；8，70；8，6；7，8；9，20）對數據中的噪聲具有良好的魯棒性。

圖6 DSMC算法對逐漸增加噪聲點的數據集聚類結果Fig．6 Clustering results over the noisy data sets of DSMC algorithm

3．4 混合形狀的人工數據集實驗

為進一步說明DSMC算法的有效性，將該算法應用于混合形狀的人工數據集（凸狀和非凸狀混合），其中，該混合數據集含有1 520個數據點，包括320個噪聲點。圖7表明，DSMC算法（參數k和Q為10，100）對這種密度不均勻的混合數據集也能很好地聚類。

圖7 DSMC算法對混合數據集的聚類結果Fig．7 Clustering results of DSMC algorithm for mixed data set

3．5 真實數據集實驗

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

表1 真實數據集的特征描述Table 1 Characteristic description of real data sets

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

表2 算法對真實數據集聚類結果的比較Table 2 Comparison of clustering results on real data sets

3．6 DSMC算法參數分析

DSMC算法中涉及到的2個重要參數分別是獨立隨機變量的個數Q和鄰域內數據點的個數k。

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

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

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

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

4 結束語

隨著信息技術水平的不斷提高，具有噪聲和重疊現象的數據源越來越多，僅限于計算機領域的聚類方法不能很好地處理該問題。為此，本文提出了一種同統計思想相結合的快速聚類算法—DSMC算法，它使用了一個簡單的合并順序和統計判定準則，將數據點的每一個特征看作一組獨立隨機變量，根據獨立有限差分不等式得出統計合并判定準則，同時，結合數據點的密度信息，把密度從大到小的排序作為凝聚過程中的合并順序，進而實現各類數據點的統計合并。對人工數據集和真實數據集測試的實驗結果表明，DSMC算法對于非凸狀、重疊和加入噪聲的數據集都有良好的聚類效果。

在后續的研究工作中，將進一步推廣DSMC算法的應用范圍，使其能夠快速、高效地處理大數據、在線數據等多種型態的復雜聚類問題。

［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，FLYNN 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，FULL 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］．軟件學報，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年生，碩士研究生，主要研究方向為模式識別。

馬儒寧，男，1976年生，副教授，博士，主要研究方向為應用數學、模式識別。參與完成國家自然科學基金項目10余項。發表學術論文20余篇，其中被SCI、EI收錄10余篇。

丁軍娣，女，1978年生，副教授，博士，中國計算機學會會員，主要研究方向為模式識別、計算機視覺。主持并完成國家自然科學基金項目10余項。發表學術論文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

劉貝貝，馬儒寧，丁軍娣．基于密度的統計合并聚類算法［J］．智能系統學報，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．

國家自然科學基金資助項目（61103058）．

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