基于密度峰值多起始中心的融合聚類算法

梅 婕，魏圓圓，許桃勝

1.中國科學(xué)院 合肥物質(zhì)科學(xué)研究院 智能機械研究所，合肥230031

2.中國科學(xué)技術(shù)大學(xué)，合肥230026

3.安徽省智慧農(nóng)業(yè)工程實驗室，合肥230031

聚類分析（Clustering Analysis）[1-5]是數(shù)據(jù)分析和信息挖掘的一種重要研究方法。在樣本沒有給定類別信息的情況下，聚類分析基于樣本特征的相似性計算，確定樣本的分組，同一分組的樣本具有高度的相似性，而來自不同分組的樣本之間相異度高。聚類分析方法一般需要確定聚類起始中心，進(jìn)而迭代優(yōu)化獲得聚類結(jié)果。根據(jù)聚類算法的目標(biāo)函數(shù)不同，概括有如下的聚類起始中心的定義方法：

（1）隨機設(shè)定聚類起始中心[4，6]，迭代尋找簇的劃分使得目標(biāo)函數(shù)得到最優(yōu)解。典型算法如K-Means[7]。KMeans算法首先隨機選取K個聚類中心點，計算每個樣本到K個聚類中心點的距離，將樣本劃分到距離其最近的中心點所代表的類別，然后基于目標(biāo)函數(shù)動態(tài)調(diào)整K個聚類中心點，迭代上述過程直至目標(biāo)函數(shù)（即簇內(nèi)距離平方和）最小。K-Means 算法采用樣本空間距離最近的劃分原則，因此不適用于非球型數(shù)據(jù)（如具有空間折疊結(jié)構(gòu)的流型數(shù)據(jù)）的聚類問題。

（2）針對不規(guī)則形狀的數(shù)據(jù)集，根據(jù)密度中心點[8-10]定義聚類簇中心。DBSCAN[11]是一種基于密度的聚類算法，通過將簇定義為密度相連的點的最大集合，能夠?qū)⒏呙芏葏^(qū)域劃分為簇，并可在噪聲數(shù)據(jù)中發(fā)現(xiàn)任意形狀的聚類。在密度聚類方法基礎(chǔ)上，Rodriguez 等提出一種基于密度峰值的聚類算法（Density Peaks Clustering，DPC）[12]，聚類中心點的定義是具有較高局部密度且與比它密度大的點持有較大距離。該算法計算出每個數(shù)據(jù)點對應(yīng)的局部密度ρ和距離δ，將其分別作為橫、縱坐標(biāo)構(gòu)建出“決策圖（Decision Graph）”，可在一定程度上幫助確定聚類簇中心。

（3）基于概率密度分布[13-14]定義聚類起始中心。假設(shè)數(shù)據(jù)集內(nèi)不同的簇符合不同的概率密度分布，所有樣本點收斂于局部密度最大值，最終收斂到相同局部最大值的點被判定為屬于同一簇。此類算法適用于非球型數(shù)據(jù)集，但是計算成本較高，其中較為代表性的聚類算法是Mean Shift算法[15]。

K-Means作為聚類分析的代表性方法，具有廣泛的引用，其聚類的初始中心通過隨機選取產(chǎn)生，因此KMeans不能保證每次得到一致的聚類結(jié)果。另外，若隨機的初始中心點偏離數(shù)據(jù)區(qū)域過遠(yuǎn)，則可能導(dǎo)致該中心點被孤立，沒有樣本會被劃分到該中心點，出現(xiàn)dead-unit[16]問題。同時，K-Means 算法傾向于將數(shù)據(jù)分為相對均衡的簇，這一現(xiàn)象稱為均勻效應(yīng)（Uniform Effect）[17-18]，因此對于一些存在由大子集和小子集組成的非均衡數(shù)據(jù)集，采用K-Means 聚類可能導(dǎo)致較多的聚類錯誤。針對上述問題，許多學(xué)者提出一系列K-Means-type 改進(jìn)算法[19-21]。其中，F(xiàn)SCL算法[16]將獲勝頻率作為權(quán)重加入到距離的計算中，使得獲勝次數(shù)較少的中心點具有更大的概率去贏得新的樣本，避免dead-unit 問題。此外，Liang 等人提出一種基于模糊與多聚類簇中心（Multi-Prototypes）機制的算法來避免均勻效應(yīng)。每個prototype代表一個聚類簇的中心點，將數(shù)量確定的prototypes 定位到合適的數(shù)據(jù)區(qū)域，使得大樣本集由更多的prototypes表示，小樣本集由較少的prototypes表示，最后按一定規(guī)則合并相近的prototypes得到最終的聚類結(jié)果。然而該算法不能實現(xiàn)聚類數(shù)的自動收斂，需要預(yù)先設(shè)定聚類的目標(biāo)數(shù)目。

2019 年Lu 等人提出一種針對非均衡數(shù)據(jù)集的自適應(yīng)算法SMCL（Self-adaptive Multiprototype-based Competitive Learning）[22]。該算法基于Multi-Prototypes思想，在經(jīng)典K-Means 算法的基礎(chǔ)上運用競爭懲罰機制和自適應(yīng)策略來確定初始聚類中心（PNS子算法），隨后根據(jù)一定規(guī)則融合prototypes代表的各個子簇得到最終聚類結(jié)果。其中，PNS算法以少量的prototypes開始，逐漸自適應(yīng)地增加prototypes數(shù)量，在此過程中prototypes的位置不斷改變，直至某一個prototype根據(jù)競爭懲罰機制被淘汰。但是，SMCL 算法在自適應(yīng)調(diào)整prototypes的過程中，初始聚類中心可能被定位到兩個子簇的中間區(qū)域，造成均勻效應(yīng)。另外，SMCL 算法由于動態(tài)自適應(yīng)性導(dǎo)致算法效率低下，不適合大型數(shù)據(jù)集的聚類分析，且隨著prototypes數(shù)量的增加，每個prototype獲勝次數(shù)急劇減少，無法避免PNS子算法非正常終止問題。

本文針對SMCL算法存在的問題，結(jié)合密度峰值的聚類思想，提出基于多起始中心（Multi-Prototypes）的聚類算法DP-SMCL（Density Peak-SMCL）。DP-SMCL借助Multi-Prototypes思想和SMCL子簇融合機制，通過局部密度ρ和距離δ計算篩選出密度峰值大的樣本點作為prototypes，能夠有效解決dead-unit問題，并且使算法效率得到顯著提高。另外，實驗使用聚類評價指標(biāo)蘭德指數(shù)（RI）和正確率（Accuracy）等對模擬數(shù)據(jù)集和真實數(shù)據(jù)集（來自UCI 數(shù)據(jù)庫）的聚類結(jié)果進(jìn)行對比分析。實驗結(jié)果表明，DP-SMCL算法可實現(xiàn)對非球型數(shù)據(jù)集的聚類分析且聚類結(jié)果優(yōu)于K-Means、DBSCAN和SMCL等經(jīng)典聚類算法。

1 DP-SMCL聚類算法

DP-SMCL 算法基于Multi-Prototypes 機制，首先根據(jù)所有樣本的密度峰值預(yù)選出初始聚類中心（prototypes），prototypes 的數(shù)目根據(jù)經(jīng)驗值設(shè)定（見2.2 節(jié)）。然后采用1-D 高斯混合概率密度函數(shù)[22]檢測各prototype 子簇間相連區(qū)域的密度，將相連區(qū)域密度值大的子簇優(yōu)先合并，合并過程中根據(jù)設(shè)定的指標(biāo)判斷聚類情況，選出最佳聚類數(shù)目，從而獲得精確的聚類結(jié)果。

1.1 確定初始聚類中心

一個樣本被設(shè)定為prototype應(yīng)具備以下條件：（1）該樣本本身的密度較大，即它的周圍都是密度比它小的鄰居；（2）與其他密度值更大的樣本具有較遠(yuǎn)的距離。

定義1（局部密度）假設(shè)數(shù)據(jù)集為E＝{x1,}x2,…,xN，樣本點xi的局部密度的定義如下：

其中，E{xi} 表示除xi外的所有樣本點，d(xi,xj)代表樣本xi和樣本xj之間的歐式距離，dc表示截斷距離[12]，N為樣本數(shù)。dc的選取原則是使每個樣本點的平均鄰居個數(shù)約為樣本點總數(shù)的1%～2%（用t表示該比例）。所有樣本兩兩之間的距離構(gòu)成的距離集合D共有項，按照升序關(guān)系進(jìn)行排序，D表示為{d1,d2,…,dk,…,dM}，其中dc∈D,且c＝M×t。

定義2（距離δi[12]）對所有樣本的局部密度進(jìn)行降序排列，然后基于聚類中心的特點，在密度大于ρi的所有樣本點中選擇與xi距離最近的點，兩者之間距離作為xi的δi。

特別的，若ρi對應(yīng)最大的局部密度，則

根據(jù)聚類起始中心的選取原則，樣本點xi的局部密度和距離越大，則越可能作為潛在的聚類起始中心點。為了選擇合適的prototypes，DP-SMCL算法首先對ρ和δ進(jìn)行初步篩選，將的樣本點排除，其中分別對應(yīng)局部密度和距離的均值。隨后，在符合要求的樣本點中選取較大的n個樣本點作為初始聚類中心，是對ρ和δ進(jìn)行歸一化處理之后的值，用于消除不同量綱的影響。

1.2 基于1-D高斯混合概率密度模型的子簇合并

由于樣本的分布情況存在不確定性，分析兩個prototypes 所代表子簇的相連區(qū)域的密度時，密度最小的地方并不一定正好處于兩個prototypes 的中點位置。研究表明，有限高斯混合模型可以逼近任意分布的概率密度函數(shù)[23]。針對現(xiàn)實數(shù)據(jù)集樣本分布的不確定性，本文使用高斯混合概率密度函數(shù)準(zhǔn)確描述子簇間相連區(qū)域任意位置的樣本分布情況，確定高斯混合概率密度函數(shù)最小值點，以此作為判斷不同prototypes 子簇之間相互獨立的指標(biāo)。假設(shè)子簇Ci的prototype記作zi，Cj的prototype 記作zj，通過概率密度模型計算出投影區(qū)間[a,b] 內(nèi)最小的密度值以此判定子簇Ci和子簇Cj的獨立程度。越小表明Ci和Cj的分離程度越高，越不可能屬于同一聚類類別。

借助1-D投影分布[18]分析子簇相連區(qū)域的密度來對Ci和Cj的獨立程度進(jìn)行評估，若相連區(qū)域的密度值高則更可能屬于同一類。具體地，將屬于Ci和Cj內(nèi)的所有樣本點投影到zi和zj所在直線上，設(shè)樣本x的投影點為x′，其計算公式如下：

假設(shè)待合并的prototypes共有K個，K個組間相互的獨立程度可用矩陣DK×K表示，D(i,j)為Ci和Cj所有prototypes組合的Fmin最大值。

矩陣D中最大元素Dmax所對應(yīng)兩個子簇Ci和Cj的獨立程度最低，優(yōu)先進(jìn)行合并，在合并后的新子簇集合上再計算出更新的獨立程度矩陣重復(fù)上述合并過程，直至最后只剩下一個子簇，即所有prototypes都被劃分到同一子簇。

為了獲取數(shù)據(jù)集的真實類別數(shù)目，對于每一輪合并后的聚類結(jié)果由組內(nèi)緊密度和組間分離程度綜合評估[22]。DP-SMCL算法記錄下每輪合并時所依據(jù)的最大D(i,j)元素Dmax。根據(jù)文獻(xiàn)[24]中提出的度量方法，comk＝1/Dmax可以表示組內(nèi)數(shù)據(jù)的緊密程度，值越小說明組內(nèi)越緊密，結(jié)果越好。另外，文獻(xiàn)[25]中提出了度量簇間分離程度的指標(biāo)sepk，該指標(biāo)旨在避免在計算簇間分離程度時只用單個集群中心點代表整個集群所造成的局限性，因為單一的點作為整個集群的代表只適用于數(shù)據(jù)集滿足球型簇的情況。sepk在計算簇間分離程度時借助了KNN 一致性[26]思想，若一個數(shù)據(jù)點位于數(shù)據(jù)集的中間，則它的κ個鄰居會和它同屬一個子簇，而對于一個位于分界邊緣的數(shù)據(jù)點，它的鄰居可能屬于其他的子簇，sepk的計算公式如下：

其中，k表示子簇的數(shù)量，κ是鄰居數(shù)，ni代表第i個子簇Ci內(nèi)的樣本總數(shù)，qj代表樣本j的不與它同屬一個子集的鄰居數(shù)。綜上，聚類簇數(shù)的選擇標(biāo)準(zhǔn)定義如下：

子簇合并是將相連區(qū)域密度大的子簇優(yōu)先合并為新的子簇，通過迭代，新子簇集合間相連區(qū)域的密度不斷減小，子簇間界限趨于明顯，直至確定最優(yōu)類別數(shù)目。式（7）中comk度量組內(nèi)緊密度，其值越小，代表類內(nèi)一致性越好。如果屬于不同類的兩個子簇被合并，其對應(yīng)的comk值會顯著大于同屬一類的子簇被合并所得到的comk值。sepk值用于度量簇間分離程度，定義sepk為各分組數(shù)據(jù)點與其各自的κ個鄰居不同屬一類的比例，其取值越小，說明不同分組間界限越清晰，分離程度越大?；谑剑?）comk和sepk取值都盡可能小，可保證確定的分組組內(nèi)緊密度高，組間分離程度大，以此自動確定最佳的聚類數(shù)目。

DP-SMCL算法描述如下：

輸入：數(shù)據(jù)集E＝{x1,x2,…,xN}，需預(yù)選的prototypes數(shù)量n(20 ≤n≤40)。

輸出：聚類結(jié)果。

階段I

（1）根據(jù)式（1）和式（2）計算出所有樣本的局部密度ρi和距離δi；

（2）按照ρi×δi由大到小預(yù)選出n個prototypes，作為階段II的輸入。

階段II

（1）以每個prototype 為中心的子簇各自為一組，根據(jù)式（3）～（5）確定合并順序并執(zhí)行合并；

（2）由式（7）選出最優(yōu)聚類數(shù)目K，得到最終結(jié)果。

2 實驗與分析

2.1 實驗環(huán)境

本文實驗在單機環(huán)境下進(jìn)行，電腦配置如下：處理器為標(biāo)壓銳龍R5-3550H＠2.10 GHz，內(nèi)存16 GB，操作系統(tǒng)為64位Windows 10。

2.2 DP-SMCL算法參數(shù)設(shè)置實驗

DP-SMCL 算法需要設(shè)定初始聚類中心的數(shù)目（參數(shù)n），為保證得到精確的聚類結(jié)果，n的設(shè)定需要在合理區(qū)間內(nèi)，基于4種模擬數(shù)據(jù)集（文獻(xiàn)[22]）討論參數(shù)n的設(shè)置。其中DATA_1（banana數(shù)據(jù)集）、DATA_2（Gaussian數(shù)據(jù)集）、DATA_3（ids2 數(shù)據(jù)集）和DATA_4（Lithuanian數(shù)據(jù)集）的數(shù)據(jù)集描述如表1所示。

表1 模擬數(shù)據(jù)集Table 1 Synthetic datasets

圖1展示了參數(shù)n對4種模擬數(shù)據(jù)集聚類結(jié)果正確率的影響，分別對應(yīng)參數(shù)n∈{5,15,25,35,45} 時DPSMCL 算法聚類結(jié)果正確率（Accuracy）的變化情況?？梢园l(fā)現(xiàn)n的取值對模擬數(shù)據(jù)集“DATA_1”和“DATA_4”的結(jié)果產(chǎn)生較大影響，而對模擬數(shù)據(jù)集“DATA_2”和“DATA_3”的影響較小，原因在于DATA_1 和DATA_4中各子簇數(shù)據(jù)分布的密度差大于數(shù)據(jù)集DATA_2 和DATA_3。

圖1 參數(shù)n 對4種模擬數(shù)據(jù)集聚類結(jié)果正確率的影響Fig.1 Influence of parameter n on accuracy of clustering results of 4 synthetic datasets

以數(shù)據(jù)集DATA_1 為例，在參數(shù)n分別取5 和25時，觀察不同的prototypes數(shù)對聚類結(jié)果的影響。

圖2 展示了參數(shù)n＝5 和n＝25 對應(yīng)的聚類結(jié)果。其中，（a）和（c）中紅色五角星是根據(jù)局部密度ρ和距離δ選出的初始聚類中心點（prototypes），（b）和（d）分別是初始聚類中心數(shù)n＝5 和n＝25 的聚類結(jié)果，紅色五角星對應(yīng)著決策圖中五角星代表的樣本點。結(jié)果表明，當(dāng)n＝5 時，對于如圖所示的兩個子簇的數(shù)據(jù)分布密度差距較大的非均衡分布數(shù)據(jù)集，低密度區(qū)域的樣本點在競爭成為prototype 的過程中受限于較小的局部密度而缺乏競爭力，導(dǎo)致所有的prototypes 集中在局部密度大的子簇中，聚類失敗，如圖2（b）所示。當(dāng)n＝25 時，圖2（c）表明在n足夠大（即prototypes 數(shù)量充足）的情況下，低密度區(qū)域中擁有較大距離δ的樣本點可以被選中為prototypes，圖2（d）展示了子簇密度分布不均衡的數(shù)據(jù)集被準(zhǔn)確劃分為兩類。然而，參數(shù)n的擴大雖然可以增加低密度區(qū)域樣本點成為prototype的概率，但是若參數(shù)n設(shè)置過大，過多的初始聚類中心點將在合并階段消耗不必要的計算資源。

圖2 Prototypes選擇結(jié)果和DP-SMCL算法聚類結(jié)果Fig.2 Prototypes selection results and DP-SMCL algorithm clustering results

綜合考慮算法的效率和有效性，將參數(shù)n的范圍限定在[20，40]較為合適。

2.3 DP-SMCL算法的聚類分析

2.3.1 聚類數(shù)目的確定

圖3展示了DP-SMCL算法在4種模擬數(shù)據(jù)集上的最佳聚類數(shù)目的選擇過程。圖中分別表示comk和sepk以及綜合考量comk、sepk的度量值隨聚類數(shù)目k取值不同的變化情況。其中，圖3（a）顯示DP-SMCL 針對非球型數(shù)據(jù)集（DATA_1）的聚類數(shù)目確定情況。k取值從1變化到2，comk值急劇下降，當(dāng)k＝1 時不屬于同一類的兩個子簇被合并在一起，其相連區(qū)域樣本分布概率密度極小，造成comk值偏大。另外，k從2增加到5，sepk顯著增大（紅色折線），可以看出同屬一類的子簇被劃分成多個子部分且都單獨作為新的子簇存在，樣本的κ個鄰居中不與其同屬一個子簇的樣本比例明顯增加，由式（6）可知sepk值會不斷增大。因此，根據(jù)圖3（a）可以確定DATA_1 的聚類數(shù)目為2，與真實類別一致。如圖3（c）所示，DP-SMCL算法應(yīng)用于球型數(shù)據(jù)集（DATA_3）確定其聚類數(shù)目為5。相對于k取值從5 增加到6，comk值在k從4到5時的變化更為顯著，表明k＝4 時存在不屬于同一類的子簇被合并。k＝5 之后的comk趨近于0，表明同屬一類的子簇被合并，被合并子簇間相連區(qū)域的樣本密度大，結(jié)合式（5）和comk的定義可知此時對應(yīng)的comk值極小，符合數(shù)據(jù)代表的實際類別。同時，根據(jù)sepk的變化可知，從k＝5 開始sepk顯著上升，表明同屬一個子簇的樣本被錯誤分割成更小的子簇。隨著子簇的數(shù)目不斷增多，子簇間相互緊鄰，由式（6）可知組間分離程度越來越差，sepk值趨于1。將DP-SMCL 算法分別應(yīng)用到數(shù)據(jù)集DATA_2和DATA_4上的結(jié)果如圖3（b）和（d）所示，由comk、sepk值的變化可以確定的聚類簇數(shù)分別為4 和2，與數(shù)據(jù)集實際包含的類別數(shù)一致。實驗結(jié)果表明，DP-SMCL 算法能夠自動確定數(shù)據(jù)集所包含的真實類別數(shù)目。

圖3 DP-SMCL算法依據(jù)comk、sepk 和comk ＋sepk 自動確定最佳聚類數(shù)目Fig.3 DP-SMCL algorithm automatically determines optimal number of clusters based on comk,sepk and comk ＋sepk

2.3.2 DP-SMCL算法特性分析

DP-SMCL算法通過借助密度峰值聚類算法（DPC）思想，選定局部密度ρ和距離δ相對較大的樣本點作為起始聚類中心prototypes。相對于K-Means算法隨機選擇起始聚類中心，DP-SMCL 算法可有效排除離群點作為起始聚類中心對聚類結(jié)果的影響，避免K-Means 算法中dead-unit問題。另外，通過引入Multi-Prototypes機制并借助1-D 高斯混合概率密度模型合并以prototype為中心的子簇，使得DP-SMCL 算法可以應(yīng)用于非球型數(shù)據(jù)集。

圖4為DP-SMCL應(yīng)用于球型數(shù)據(jù)集和非球型數(shù)據(jù)集的聚類結(jié)果（參數(shù)n設(shè)為25）。其中，（a）和（c）分別為兩種數(shù)據(jù)集的分布情況，（b）和（d）為DP-SMCL 算法的聚類結(jié)果，顏色相同的點代表劃分為同一類。圖中的紅色五角星是算法確定出的起始聚類中心，可以看到簇內(nèi)樣本越多密度越大，選出的起始聚類中心越多。DPSMCL 算法首先根據(jù)選定的起始聚類中心將樣本劃分為多個小簇，然后借助1-D高斯混合概率密度模型合并相連區(qū)域密度大的子簇，以子簇為單位進(jìn)行樣本融合，確定出最佳聚類結(jié)果。實驗結(jié)果表明，DP-SMCL 算法對球型和非球型數(shù)據(jù)集都能進(jìn)行有效聚類。

圖4 DP-SMCL對球型、非球型數(shù)據(jù)集的聚類Fig.4 DP-SMCL clustering of spherical and non-spherical datasets

2.3.3 模擬數(shù)據(jù)集對比實驗

本文將DP-SMCL 算法與經(jīng)典K-Means、DBSCAN算法以及SMCL 算法進(jìn)行比較，基于表1 中的4 種模擬數(shù)據(jù)集進(jìn)行實驗，實驗結(jié)果如圖5所示。

圖5 4種算法聚類結(jié)果對比Fig.5 Clustering results comparison of 4 algorithms

在進(jìn)行K-Means 算法實驗時，手動設(shè)置類別數(shù)K為各數(shù)據(jù)集的真實類別數(shù)，聚類結(jié)果中五角星代表算法最終確定的聚類中心，可以看到在預(yù)設(shè)了正確類別數(shù)目的條件下，K-Means依然可能出現(xiàn)錯誤的劃分。DBSCAN算法處理的聚類結(jié)果表明該算法對數(shù)據(jù)集“DATA_1”和“DATA_4”的劃分效果較好，但在處理“DATA_2”和“DATA_3”時，無論如何調(diào)整聚類半徑，實驗結(jié)果都出現(xiàn)了明顯的錯誤劃分。對比SMCL和DP-SMCL算法對模擬數(shù)據(jù)集的實驗結(jié)果，可以看出兩種算法應(yīng)用在4種模擬數(shù)據(jù)集上都基本可以實現(xiàn)對數(shù)據(jù)集的有效聚類。但SMCL算法在確定初始聚類中心時需不斷調(diào)整prototypes的位置以及判斷是否要添加新的prototype，導(dǎo)致消耗較多的計算資源。相對于SMCL起始中心確定的復(fù)雜性，DP-SMCL算法基于密度峰值算法（DPC）提出的簇中心點特征，根據(jù)樣本點的局部密度ρ和距離δ確定prototypes，可快速完成初始聚類中心點的選定。4種算法在模擬數(shù)據(jù)集上運行時間的對比情況如表2 所示，結(jié)果表明DPSMCL相比于SMCL算法，效率獲得極大提高。

表2 4種算法運行時間對比Table 2 Running time comparison of 4 algorithms s

為進(jìn)一步比較4種聚類算法在4種模擬數(shù)據(jù)集上的聚類效果，使用蘭德指數(shù)（RI）對聚類結(jié)果進(jìn)行評價。RI的計算公式如下：

假設(shè)U為外部評價標(biāo)準(zhǔn)，即真實的類別情況，V表示聚類結(jié)果，其中a代表在U和V中同為一類的樣本點對數(shù)，b表示在U中為同一類而在V中屬于不同類別的樣本點對數(shù)，c表示在U中不在同一類但在V中為同一類別的對數(shù)，d表示在U和V中均不屬于同一類別的樣本點對數(shù)。RI 的取值范圍是[0，1]，數(shù)值越接近1說明算法的分類結(jié)果與實際結(jié)果越吻合，即聚類模型越好。

表3 4種算法在4種數(shù)據(jù)集上的評價指標(biāo)比較Table 3 Index value comparison of 4 algorithms on 4 datasets

2.3.4 UCI數(shù)據(jù)集對比實驗

為了驗證算法的可靠性，針對UCI（https：//archive.ics.uci.edu/ml/index.php）數(shù)據(jù)庫中獲取的6 種代表性數(shù)據(jù)集進(jìn)行實驗驗證。6種數(shù)據(jù)集的描述如表4所示。

表4 數(shù)據(jù)集描述Table 4 Description of datasets

分別使用正確率（Accuracy）、蘭德指數(shù)（RI）以及F1-Score三種評價指標(biāo)來對比分析DP-SMCL、K-Means、DBSCAN 以及SMCL 算法的聚類效果。SMCL 算法在實驗時默認(rèn)使用原有參數(shù)設(shè)置，考慮到經(jīng)典K-Means算法隨機選取初始聚類中心和DBSCAN算法參數(shù)設(shè)置的不同會對聚類結(jié)果產(chǎn)生影響，實驗時采用多次實驗取平均獲得各算法結(jié)果。

從表5 中可以看出，本文提出的DP-SMCL 算法應(yīng)用在6種真實數(shù)據(jù)集上的聚類表現(xiàn)普遍優(yōu)于其他3種算法，其正確率、蘭德指數(shù)和F1-Score都能取得較好結(jié)果。

表5 4種算法在6種UCI數(shù)據(jù)集上的評價指標(biāo)對比Table 5 Index value comparison of 4 algorithms on 6 UCI datasets

3 結(jié)束語

本文借助SMCL 算法中的Multi-Prototypes 思想和融合機制，提出了一種基于密度峰值的聚類算法DPSMCL，對經(jīng)典K-Means算法進(jìn)行了改進(jìn)。通過有條件地選取prototypes 作為初始聚類中心，避免了K-Means算法中因初始聚類中心選取隨機而導(dǎo)致的dead-unit 問題。DP-SMCL算法在合并階段借助高斯混合概率密度模型完成子簇間合并，使算法不再局限于球型數(shù)據(jù)集，再通過comk和sepk指標(biāo)綜合分析來自動確認(rèn)類別數(shù)K，彌補了經(jīng)典K-Means 算法需要人為指定類別數(shù)的不足。實驗結(jié)果表明，DP-SMCL 算法可實現(xiàn)對非球型數(shù)據(jù)集的聚類，對比K-Means 和DBSCAN 算法擁有更好的聚類效果。同時，對比SMCL 算法，在確定初始聚類中心點時，DP-SMCL 算法基于密度峰值算法（DPC）提出的簇中心點特征可快速完成初始聚類中心點的選定，極大地提高了算法效率。DP-SMCL 算法將數(shù)據(jù)集投影到一維空間，并使用概率密度函數(shù)度量相連區(qū)域最小密度作為子簇合并的指標(biāo)，結(jié)果表明在低維的數(shù)據(jù)集中該算法表現(xiàn)良好。下一步研究的重點是如何將DPSMCL算法擴展到高維度的數(shù)據(jù)集上。