鮑舒婷，孫麗萍* ，鄭孝遙，郭良敏

(1.安徽師范大學(xué)計算機(jī)與信息學(xué)院，安徽蕪湖241002; 2.網(wǎng)絡(luò)與信息安全安徽省重點實驗室(安徽師范大學(xué))，安徽蕪湖241002)(*通信作者電子郵箱slp620@ahnu.edu.cn)

0 引言

聚類是數(shù)據(jù)挖掘中重要的研究領(lǐng)域之一，用來分析數(shù)據(jù)的分布。聚類是一個將數(shù)據(jù)對象劃分成若干個類簇的過程，使得簇中的對象相似度高，但每個簇之間的對象相似度低。聚類在模式識別、分類、圖像處理、Web搜索、商務(wù)智能等領(lǐng)域都有廣泛的研究。聚類方法主要分為以下幾類:基于層次聚類、基于劃分聚類、基于密度聚類以及基于圖聚類。

K-means算法［1］是基于劃分聚類的經(jīng)典算法，該算法是通過多次迭代找到最佳聚類中心，根據(jù)樣本到聚類中心點的距離對樣本進(jìn)行劃分。由于K-means算法是將樣本分配到與其最近的簇中，因此該算法不能發(fā)現(xiàn)任意形狀的簇。如果初始聚類中心選擇不好，結(jié)果很容易陷入局部最優(yōu)，導(dǎo)致聚類結(jié)果不穩(wěn)定［2］。基于密度的空間聚類(Density-based Spatial Clustering of Applications with Noise，DBSCAN)算法［3］是基于密度聚類的經(jīng)典算法，該算法是通過定義鄰域半徑eps和樣本的最小鄰域個數(shù)minpts來決定樣本分布的緊密程度。但是，該算法對參數(shù)eps較為敏感，較小的eps值可能會導(dǎo)致過度聚類的情況，較大的eps值可能會使得較小的簇被合并。標(biāo)準(zhǔn)譜聚類(Spectral Clustering，SC)算法［4］是基于圖聚類的經(jīng)典算法，利用矩陣譜分析理論對原始的數(shù)據(jù)對象進(jìn)行提取，得到新的數(shù)據(jù)特征，實現(xiàn)過程較為簡單，但聚類結(jié)果依賴于相似矩陣。

文獻(xiàn)［5］提出了基于密度的密度峰聚類 (Density Peaks Clustering，DPC)算法，簡單高效，無需迭代;同時，不需要考慮概率分布函數(shù)或?qū)?shù)據(jù)映射到向量空間，性能不受數(shù)據(jù)空間維度影響［6］。但存在一些缺陷:算法需要設(shè)置截斷距離dc，算法的準(zhǔn)確性需要依賴dc的選擇和對數(shù)據(jù)集的密度估計;算法使用歐氏距離定義樣本之間的相似性來計算局部密度，存在局限性;聚類中心的選擇需要人工干預(yù)等。

近年來，DPC算法得到了廣泛的研究。文獻(xiàn)［7］首先對數(shù)據(jù)集進(jìn)行主成分分析處理，再將k近鄰引入樣本局部密度計算中，對聚類結(jié)果進(jìn)行了優(yōu)化。文獻(xiàn)［8］提出基于DPC的模糊聚類算法，自適應(yīng)地尋找聚類中心的個數(shù)，而不需要預(yù)先指定類簇個數(shù)。文獻(xiàn)［9］基于熱擴(kuò)散技術(shù)提出一種非參數(shù)的估計給定數(shù)據(jù)集的概率分布的DPC改進(jìn)算法。但是以上算法都沒有考慮到樣本之間相似性度量和聚類中心自適應(yīng)選擇的問題。

針對以上缺陷，本文提出一種基于共享近鄰相似度［10］的密度峰聚類算法(Density Peaks Clustering algorithm based on Shared Near Neighbors Similarity，DPCSNNS)。該算法將共享近鄰相似度和歐氏距離相結(jié)合計算樣本之間相似度，避免了dc的設(shè)置，更精確地計算樣本間相似度。同時，該算法給出了一個新的聚類中心選擇策略，使得該算法能自適應(yīng)地進(jìn)行聚類中心的選擇。

1 相關(guān)工作

1.1 相關(guān)記號

假定數(shù)據(jù)集 XN×M=［x1，x2，…，xN］T，對于任意向量xi=［xi1，xi2，…，xiM］表示樣本xi(1≤i≤N)的M個屬性，N為樣本總個數(shù)。聚類是將數(shù)據(jù)集X中的樣本劃分成L個類簇C={C1，C2，…，CL}。在聚類評價過程中，本文使用 R={R1，R2，…，RL}來表示標(biāo)準(zhǔn)分類結(jié)果，{γi}={γ1，γ2，…，γN}。聚類結(jié)果要盡可能滿足如下兩個要求［11］:1)簇內(nèi)樣本相似度高;2)簇間樣本相似度低。

1.2 密度峰聚類算法

密度峰聚類算法基于一個假設(shè)條件，該條件是:理想的聚類中心被密度較低的鄰居樣本包圍并且與另一個更高密度樣本之間的距離相對較遠(yuǎn)。DPC算法主要有三個步驟:第一步，通過度量每一個樣本的局部密度ρ和距離δ得到?jīng)Q策圖(Decision Graph);第二步，根據(jù)聚類中心的特征，在決策圖上選擇最佳的聚類中心;第三步，將剩余樣本分配到距其最近并擁有較高密度的樣本所在類簇中。

原始的DPC算法通過歐氏距離度量樣本xi和xj之間的相似性，計算公式如下:

為了找到理想的聚類中心，原始的DPC算法需要計算每一個樣本局部密度ρ和距離δ，樣本xi的局部密度ρi計算公式如下:

其中:ρi就等于所有到xi的距離小于dc的樣本的個數(shù)。參數(shù)dc是截斷距離，DPC算法給出了dc選擇的標(biāo)準(zhǔn):使樣本的平均近鄰個數(shù)是整個數(shù)據(jù)集規(guī)模的1% ～2%［12］。針對小規(guī)模數(shù)據(jù)集，DPC算法采用指數(shù)核［13］計算樣本的局部密度來提高聚類中心選擇的準(zhǔn)確性，具體的計算公式如下:

原始的DPC算法需要計算樣本的局部密度和距離來選擇聚類中心，樣本xi的距離δi為xi到其他較高密度樣本之間的最短距離，如果xi已經(jīng)是最高密度的樣本，δi就等于xi到其他樣本的最大距離，具體計算公式如下所示:

根據(jù)計算后的局部密度ρi和距離δi得到?jīng)Q策圖，DPC算法根據(jù)決策圖確定最佳的聚類中心需要人工干預(yù)。由式(2)～(4)可見，若一個高密度樣本與另一個更高密度樣本相距較遠(yuǎn)，則該樣本為聚類中心的可能性較大，即理想的聚類中心為高δ值和相對較高的ρ值的樣本。因此，在文獻(xiàn)［5］中采用式(5)進(jìn)行聚類中心的選取:

在聚類中心選出后，DPC算法對剩余樣本進(jìn)行分配。根據(jù)樣本的距離δ，將剩余樣本分配到距其最近并擁有較高密度的樣本所在類簇中。DPC算法的具體描述如算法1所示。

算法1 密度峰聚類算法(DPC算法)。

輸入 數(shù)據(jù)集XN×M，類簇個數(shù)L;

輸出 聚類結(jié)果C={C1，C2，…，CL}。

1)根據(jù)式(2)或式(3)計算樣本的局部密度;

2)根據(jù)式(4)計算樣本的距離;

3)根據(jù)決策圖選擇聚類中心;

4)將剩余樣本分配到距其最近并擁有較高密度的樣本所在類簇中;

5)返回聚類結(jié)果C。

2 基于共享近鄰相似度的密度峰聚類算法

原始的DPC算法主要存在以下兩個缺陷:1)在樣本局部密度度量中，使用歐氏距離度量樣本間的相似度存在局限性，并且dc的選擇存在一定主觀性，對聚類結(jié)果影響較大［7］。例如，當(dāng)兩個簇的密度相差較大時，兩個簇的聚類中心的局部密度也應(yīng)該相差較大;但是，如果dc比較小，就會使得兩個聚類中心的局部密度相近，使得聚類效果不理想。2)在聚類中心的選擇上，根據(jù)決策圖選擇聚類中心需要人工干預(yù)［14］;如果使用式(5)選擇聚類中心，往往會忽視樣本較少、局部密度較低的簇。

為了解決上述問題，本文提出了一種基于共享近鄰相似度的密度峰聚類算法(DPCSNNS)。DPCSNNS在局部密度的計算和聚類中心的選擇上引入共享近鄰相似度的概念，有效地避免了DPC算法因dc的選擇導(dǎo)致聚類結(jié)果較差和根據(jù)決策圖選擇聚類中心需要人工干預(yù)的缺陷。

2.1 局部密度的計算

DPC算法將dc作為全局密度閾值來計算樣本的局部密度，但如果存在一個數(shù)據(jù)集不同簇之間分布差異較大，通過決策圖選取聚類中心的準(zhǔn)確性較低。本文將k近鄰集的概念引入局部密度的計算中，這樣就避免了參數(shù)dc的選取。本文給出定義1。

定義1 k近鄰集。將數(shù)據(jù)集X中的樣本xi到其他樣本的歐氏距離升序排列，取第k個距離記作dki，則樣本xi的k近鄰集KNN(xi)定義如下:

兩個樣本之間的共享近鄰個數(shù)越多，說明這兩個樣本越相似，它們所在一個簇的可能性就越大。DPC算法將歐氏距離作為判斷兩個樣本之間相似性的唯一標(biāo)準(zhǔn)來計算樣本的局部密度，局限性較強(qiáng)，本文將共享近鄰相似度和歐氏距離兩種準(zhǔn)則進(jìn)行統(tǒng)一，提出了新的基于共享近鄰相似度的局部密度計算方式，更能反映出數(shù)據(jù)集中樣本的分布特征。本文給出定義2和定義3。

定義2 共享近鄰相似度。KNN(xi)為樣本xi的k近鄰集，KNN(xj)為樣本xj的k近鄰集，則樣本xi和xj的共享近鄰相似度SNN(xi，xj)定義如下:

定義3 樣本局部密度。樣本xi的局部密度定義如下:

2.2 聚類中心選擇策略

DPC算法選擇聚類中心需要人工干預(yù)，或者使用式(5)進(jìn)行聚類中心的選擇，但是錯誤率較高。聚類中心的錯誤選擇，會直接導(dǎo)致樣本的錯誤分配，所以本文給出了一種新的聚類中心選擇策略，其步驟如下。

步驟1 初始化聚類中心隊列Q。

步驟2 根據(jù)式(5)計算{γi}，并將樣本集 XN×M按{γi}N

i=1降序排列，記為{。

步驟5 若隊列Q中樣本個數(shù)小于等于類簇個數(shù)，轉(zhuǎn)步驟4;否則，返回Q，結(jié)束。

2.3 算法流程

本文提出的DPCSNNS首先根據(jù)式(7)計算每個樣本之間的共享近鄰相似度，根據(jù)式(8)和式(4)計算樣本的局部密度和距離，再根據(jù)聚類中心選擇策略選擇聚類中心，最后對剩余節(jié)點進(jìn)行分配，DPCSNNS偽碼如算法2所示。

算法2 基于共享近鄰相似度的密度峰聚類算法(DPCSNNS)。

輸入 數(shù)據(jù)集XN×M，類簇個數(shù)L;

輸出 聚類結(jié)果C={C1，C2，…，CL}。

normalized XN×M;

for i←1 to N

for j←1 to N

calculate SNN(xi，xj)by Equation(7);

end for

end for

for i←1 to N

calculate ρiby Equation(8);

calculate δiby Equation(4);

calculate γiby Equation(5);

end for

initialize Q and C;

while length(Q)≤L

//判斷Q中樣本個數(shù)是否小于等于類簇個數(shù)L

end if

end for

end while

assign each remaining sample to the cluster Cj∈ C(j=1，2，

…，L)as its nearest neighbor with higher density;

//將剩余樣本分配到離它最近并擁有較高密度的樣本所在類簇中

end if

end for

return C

DPCSNNS流程如圖1所示。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境

實驗采用Matlab 2013b編程實現(xiàn)，硬件配置為Windows 7操作系統(tǒng)、4 GB物理內(nèi)存、CPU為1.9 GHz的計算機(jī)。

實驗參數(shù)設(shè)置如下:對于DPCSNNS，本文設(shè)置近鄰個數(shù)k=6;對于DBSCAN算法，首先根據(jù)文獻(xiàn)［3］算法思想給出dist圖，根據(jù)dist圖設(shè)置minpts=4，eps設(shè)置為圖中拐點處縱坐標(biāo);對于K-means算法，最大迭代次數(shù)設(shè)置為1000，對每個數(shù)據(jù)集進(jìn)行20次獨立的K-means算法實驗，實驗結(jié)果取20次重復(fù)實驗的平均值。為了方便數(shù)據(jù)的處理，本文首先對數(shù)據(jù)集進(jìn)行歸一化處理，將數(shù)據(jù)集中樣本映射到［0，1］內(nèi)，計算式如下:

其中:Xmax為數(shù)據(jù)集X中當(dāng)前屬性的最大值;Xmin為數(shù)據(jù)集X中當(dāng)前屬性的最小值。

3.2 評價指標(biāo)

為了驗證本文提出的DPCSNNS的有效性，實驗在UCI數(shù)據(jù)集和模擬數(shù)據(jù)集上進(jìn)行了仿真，采用準(zhǔn)確率(ACCuracy，ACC)［15］、標(biāo) 準(zhǔn) 化 互 信 息 (Normalized Mutual Information，NMI)［16］、F 值 (F-Measure)［17］三種評價指標(biāo)對聚類結(jié)果進(jìn)行評價，并將本文算法與DPC算法、DBSCAN算法、K-means算法、SC算法進(jìn)行比較。這三種評價指標(biāo)范圍是［0，1］。準(zhǔn)確率將算法得到的類標(biāo)號和正確的類標(biāo)號進(jìn)行比較，記錄了正確分類樣本個數(shù)占總樣本的比值，數(shù)值越高表示聚類的質(zhì)量越好。計算式如下:

其中:ri表示樣本xi正確分類時的類標(biāo)號;ci表示算法得到的樣本 xi的類標(biāo)號，當(dāng)ri=ci時，ω(ri，ci)=1，否則ω(ri，ci)=0。

圖1 DPCSNNS流程Fig.1 Flow chart of DPCSNNS

NMI量化聚類結(jié)果和已知類別標(biāo)簽的匹配程度，NMI值度量了聚類結(jié)果的魯棒性，計算式如下:

其中:H(R)為正確分類R的熵;H(C)為算法得到的聚類結(jié)果C的熵。

F-Measure指標(biāo)綜合了精度(precision)和召回率(recall)兩種評價指標(biāo)，其優(yōu)勢在于對聚類結(jié)果優(yōu)劣的整體區(qū)分能力。精度評估聚類結(jié)果的精確程度，計算方式如式(13)所示;召回率評估實驗結(jié)果的完備程度，計算方式如式(14)所示;F-Measure的計算方式如式(15)所示:

其中:TP表示在R中為同一類的樣本在C中也被分到同一類;FP表示在中R為不同類的樣本在C中被分到同一類;FN表示在R中為同一類的樣本在C中被分到了不同類;R為正確分類，C為算法得到的分類。

3.3 UCI數(shù)據(jù)集實驗結(jié)果與分析

為了驗證DPCSNNS的可用性，本文從UCI機(jī)器學(xué)習(xí)庫(http://archive.ics.uci.edu/ml/)中選取了 8 個完全不同的樣本規(guī)模、維數(shù)和類簇個數(shù)的UCI數(shù)據(jù)集進(jìn)行仿真實驗，數(shù)據(jù)集的基本特征如表1所示。

本文實驗中采用當(dāng)β=1時的F-Measure:

表1 實驗使用的UCI數(shù)據(jù)集Tab.1 UCI datasets used in the experiment

針對UCI數(shù)據(jù)集，本文提出的DPCSNNS與對比算法的實驗結(jié)果如表2所示。

從表2中可以看出，使用ACC指標(biāo)評價算法，本文提出的DPCSNNS在8個UCI數(shù)據(jù)集上都優(yōu)于其他算法，并且相較于原始DPC算法有了較大的提高。其中:對于鳶尾花卉數(shù)據(jù)集Iris，本文算法ACC指標(biāo)較原始DPC算法提高了60.3%;對于動物園數(shù)據(jù)集Zoo，本文算法的ACC指標(biāo)較DPC算法提高了94.9%;使用NMI指標(biāo)評價算法，本文提出的DPCSNNS在7個UCI數(shù)據(jù)集上都優(yōu)于其他算法;對于車輛數(shù)據(jù)集Vehicle，本文算法的NMI指標(biāo)比SC算法高出68.6%;對于心臟病數(shù)據(jù)集 Heart，本文算法比 K-means算法的 NMI指標(biāo)高出148.1%;使用 F-Measure指標(biāo)評價算法，本文提出的DPCSNNS在5個UCI數(shù)據(jù)集上優(yōu)于其他算法;對于乳腺癌數(shù)據(jù)集Wpbc，本文算法的F-Measure指標(biāo)較K-means算法提高了33.3%;對于天平數(shù)據(jù)集 Balance，本文算法的F-Measure指標(biāo)較DBSCAN算法提高22.72%。

實驗結(jié)果表明，在UCI數(shù)據(jù)集上，本文提出新的基于共享近鄰相似度的局部密度計算方式和聚類中心選擇方式在聚類中心選擇的正確性以及聚類結(jié)果的準(zhǔn)確性較原始DPC算法有了一定程度的提高并且優(yōu)于其他對比聚類算法。

3.4 模擬數(shù)據(jù)集實驗結(jié)果與分析

本文使用4個模擬數(shù)據(jù)集來進(jìn)一步驗證DPCSNNS的有效性，數(shù)據(jù)集的基本特征如表3所示。

表2 不同聚類算法在UCI數(shù)據(jù)集上的實驗結(jié)果Tab.2 Experimental results of different clustering algorithms on UCI datasets

針對模擬數(shù)據(jù)集，本文提出的DPCSNNS與對比算法的實驗結(jié)果如表4所示。

從表4中可以看出，用ACC、NMI、F-Measure三個指標(biāo)評價聚類結(jié)果，本文提出的算法較其他算法都存在優(yōu)勢。對Aggregation數(shù)據(jù)集，本文算法的ACC指標(biāo)較K-means算法提高了29.4%;對R15數(shù)據(jù)集，本文算法的F-Measure指標(biāo)較SC算法提高95.4%;對于Size5數(shù)據(jù)集，本文算法的ACC指標(biāo)較DPC算法提高47.8%，NMI指標(biāo)較SC算法提高59.8%;對于Forty數(shù)據(jù)集，本文算法在三個指標(biāo)上都達(dá)到了100%的聚類效果。

實驗結(jié)果表明，在模擬數(shù)據(jù)集上，本文提出的算法在評價結(jié)果中相較其他算法有明顯的優(yōu)勢。對于DPC算法聚類效果不夠理想的模擬數(shù)據(jù)集，通過本文提出的算法可以改進(jìn)其聚類效果;對于DPC算法聚類效果已經(jīng)比較理想的模擬數(shù)據(jù)集，本文的聚類算法也可以保持其較好的聚類效果。

表4 不同聚類算法在模擬數(shù)據(jù)集上的實驗結(jié)果Tab.4 Experimental results of different clustering algorithms on artificial datasets

本文對模擬數(shù)據(jù)集的聚類結(jié)果通過不同形狀聚類分布圖進(jìn)行展示。圖2～5分別為數(shù)據(jù)集 Aggregation、R15、Size5、Forty的原始分布及 DPCSNNS、DPC算法、SC算法、K-means算法和DBSCAN算法的聚類結(jié)果圖。由圖2～5可以看出:本文算法得到的聚類結(jié)果與標(biāo)準(zhǔn)分類最接近，更能準(zhǔn)確地反映樣本的分布特征;而對于數(shù)據(jù)集Aggregation和Size5，DPC算法由于錯誤計算樣本的局部密度，使得密度較高的簇選出多個聚類中心，從而使得聚類結(jié)果較差。

圖2 數(shù)據(jù)集Aggregation原始分布及不同算法聚類結(jié)果Fig.2 Original distribution of dataset Aggregation and clustering results of different algorithms

圖3 數(shù)據(jù)集R15原始分布及不同算法聚類結(jié)果Fig.3 Original distribution of dataset R15 and clustering results of different algorithms

圖4 數(shù)據(jù)集Size5原始分布及不同算法聚類結(jié)果Fig.4 Original distribution of dataset Size5 and clustering results of different algorithms

圖5 數(shù)據(jù)集Forty原始分布及不同算法聚類結(jié)果Fig.5 Original distribution of dataset Forty and clustering results of different algorithms

4 結(jié)語

針對DPC算法對參數(shù)dc敏感和不能自適應(yīng)地選擇聚類中心的不足，本文提出了一種基于共享近鄰相似度的密度峰聚類算法，將共享近鄰相似度和歐氏距離進(jìn)行統(tǒng)一計算樣本的局部密度，并提出一種新的聚類中心選擇策略。UCI數(shù)據(jù)集和模擬數(shù)據(jù)集的實驗結(jié)果表明，對比經(jīng)典的聚類算法和原始DPC算法，本文提出的算法具有良好的聚類效果。但是，本文的近鄰個數(shù)k是特定值，不能根據(jù)數(shù)據(jù)集的特性自動生成，因此近鄰個數(shù)k是進(jìn)一步研究的重點。