薛小娜，高淑萍，彭弘銘，吳會(huì)會(huì)

XUE Xiaona1,GAO Shuping1,PENG Hongming2,WU Huihui1

1.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安 710126

2.西安電子科技大學(xué) 通信工程學(xué)院，西安 710071

1.School of Mathematics and Statistics,Xidian University,Xi’an 710126,China

2.School of Telecommunications Engineering,Xidian University,Xi’an 710071,China

1　引言

聚類是數(shù)據(jù)挖掘領(lǐng)域中的一種無(wú)監(jiān)督分類方法，其目的是將混亂的數(shù)據(jù)進(jìn)行分組，使得同一簇中的樣本盡可能相似，而不同簇中的樣本盡量不同[1-3]，現(xiàn)已被廣泛應(yīng)用于信息檢索、模式分類及數(shù)據(jù)挖掘等領(lǐng)域[4]?；诓煌瑢W(xué)習(xí)策略，傳統(tǒng)聚類算法可被劃分為分割聚類（如K-means[5]）、密度聚類（如DBSCAN[6]），以及基于傳播的方法（如AP[7]）等。

文獻(xiàn)[8]提出了一種新穎的密度峰值聚類算法DPC，其不僅能檢測(cè)出樣本集中存在的聚類數(shù)目，而且能夠有效處理具有不規(guī)則形狀的簇以及異常樣本。盡管DPC算法優(yōu)勢(shì)明顯，但其仍存在一些局限：（1）對(duì)于大小不同的數(shù)據(jù)集，采用的局部密度計(jì)算方式不同，這無(wú)形中降低了算法的靈活性；（2）對(duì)剩余點(diǎn)的分配策略易造成誤差傳播。近兩年來(lái)，許多學(xué)者都在對(duì)DPC算法進(jìn)行改進(jìn)，雖取得了許多研究成果，但也發(fā)現(xiàn)了一些新問(wèn)題。例如，文獻(xiàn)[9]基于信息熵理論提出了一種從原始數(shù)據(jù)集中自動(dòng)獲取截?cái)嗑嚯x參數(shù)的新方法，但其所需的時(shí)間成本大大增加；文獻(xiàn)[10]將DPC算法和Chameleon算法的優(yōu)點(diǎn)相結(jié)合提出了E_CFSFDP算法，雖避免了將包含多個(gè)密度峰值的一個(gè)類聚成多類，但其計(jì)算開銷高達(dá)O(N2+NlbN+NM)且不利于處理高維數(shù)據(jù)。由于 K 近鄰（K-Nearest-Neighbors，KNN）具有簡(jiǎn)單、高效等特點(diǎn)，它不但可以處理文本分類以及流數(shù)據(jù)分類問(wèn)題，其在聚類中也展現(xiàn)出很強(qiáng)的技巧性[11-13]，故該方法不斷被引入DPC算法。例如，文獻(xiàn)[14]提出了DPC-KNN算法，其利用KNN思想來(lái)估計(jì)每點(diǎn)的密度，并使用主成分分析方法對(duì)數(shù)據(jù)降維，提高了對(duì)高維數(shù)據(jù)的處理能力且能獲得良好的聚類效果。然而，由于DPC-KNN算法的聚類過(guò)程與DPC相同，故DPC算法的缺陷在該算法中仍存在。文獻(xiàn)[15]將模糊加權(quán)KNN引入DPC算法提出了FKNN-DPC算法，也使用KNN來(lái)計(jì)算每點(diǎn)的密度，并利用新提出的分配策略對(duì)剩余點(diǎn)進(jìn)行分配，雖提高了聚類質(zhì)量，但其模型較為復(fù)雜[16]。

針對(duì)上述問(wèn)題，本文根據(jù)各樣本的相似程度給出一種可適用于任意數(shù)據(jù)集的局部密度計(jì)算方法，以增強(qiáng)算法靈活度；受KNN以及隊(duì)列思想的啟發(fā)，設(shè)計(jì)了兩種不同的策略來(lái)分配剩余點(diǎn)，以提升聚類質(zhì)量和聚類效率。在21個(gè)常用數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法IDPCA不僅減少了運(yùn)行時(shí)間，而且提升了聚類質(zhì)量。

2　DPC算法

DPC算法基于以下兩點(diǎn)假設(shè)進(jìn)行設(shè)計(jì)：（1）聚類中心點(diǎn)總是被低密度點(diǎn)包圍；（2）聚類中心與其他高密度點(diǎn)間的距離相對(duì)較遠(yuǎn)。將待聚類數(shù)據(jù)集記為X，其大小和維度分別為N和D。對(duì)于X中的任意數(shù)據(jù)點(diǎn)xi，其分布情況由兩個(gè)屬性刻畫，即局部密度ρi及該點(diǎn)與其他具有較高密度點(diǎn)之間的最小距離δi。ρi的計(jì)算方式為：

其中，φ(x)是分段函數(shù)，當(dāng) dij＜dc時(shí)，φ(x)=1；否則φ(x)=0；dc為截?cái)嗑嚯x參數(shù)；dij為點(diǎn) xi和xj間的距離；ρi可解釋為點(diǎn)xi的dc鄰域內(nèi)點(diǎn)的個(gè)數(shù)。對(duì)于較小的數(shù)據(jù)集，由式（1）估計(jì)的密度可能會(huì)受統(tǒng)計(jì)誤差的影響，此時(shí)采用式（2）來(lái)估計(jì)其局部密度[8]。

xi的距離δi定義為：

對(duì)于局部密度最大的點(diǎn)xi，其距離為δi=majx (dij)。

DPC算法通過(guò)引入一種啟發(fā)式方法（決策圖）來(lái)幫助用戶獲取聚類中心（或稱密度峰值）。圖1（a）顯示了由4個(gè)類組成的數(shù)據(jù)分布情況。為了獲取該數(shù)據(jù)的聚類中心，DPC算法首先將每點(diǎn)的ρ值和δ值于坐標(biāo)平面內(nèi)繪出，然后將ρ和δ值都較大的點(diǎn)作為聚類中心，即圖1（b）中右上角的4個(gè)數(shù)據(jù)點(diǎn)。然而，對(duì)于分布稀疏的數(shù)據(jù)，通過(guò)ρ-δ決策圖難以確定其聚類中心，此時(shí)DPC算法使用γ=ρ×δ來(lái)獲取，其中γi值越大，xi越可能是聚類中心。將所有點(diǎn)的γ值降序排列，并于坐標(biāo)平面上繪出，如圖1（c）所示。由于聚類中心的γ值較大，而其他點(diǎn)的γ值較小且呈平滑趨勢(shì)，故可使用一條平行于橫軸的直線將其分開，使得直線上方的γ值所對(duì)應(yīng)的點(diǎn)即為聚類中心。當(dāng)聚類中心找出后，將剩余點(diǎn)分配到其高密度最近鄰所屬的類中。

圖1　DPC算法

3　IDPCA算法

3.1　算法思想

對(duì)于密度聚類算法來(lái)說(shuō)，各樣本密度的估計(jì)準(zhǔn)確與否不僅影響聚類中心的選取，其對(duì)聚類質(zhì)量也有直接影響。

由距離δ定義可知，δ值的大小與密度ρ也密切相關(guān)，故ρ對(duì)于聚類中心的選取至關(guān)重要。由于DPC算法的密度計(jì)算方法不一致且深受截?cái)嗑嚯xdc影響，其不能夠保證與當(dāng)前點(diǎn)距離小于dc的點(diǎn)的數(shù)目[15]，故有不少成果對(duì)該算法中的密度公式進(jìn)行了改進(jìn)。例如，DPC-KNN[14]和FKNN-DPC[15]算法為了消除dc的影響，均從數(shù)據(jù)局部分布情況出發(fā)，利用KNN來(lái)估計(jì)密度，其計(jì)算方式分別為：

盡管改進(jìn)方法中的參數(shù)K比dc容易確定，但面對(duì)類間樣本數(shù)不均衡以及疏密度不一的數(shù)據(jù)，使用γ=ρ×δ方式選取聚類中心時(shí)，類中心點(diǎn)與其他點(diǎn)的區(qū)分度并不高。為了以較高區(qū)分度識(shí)別出任意數(shù)據(jù)集中的聚類中心，本文從數(shù)據(jù)的整體分布出發(fā)，通過(guò)引入相似性系數(shù)來(lái)調(diào)節(jié)各點(diǎn)對(duì)當(dāng)前點(diǎn)的密度貢獻(xiàn)權(quán)重，給出一種帶有相似性系數(shù)的高斯核函數(shù)來(lái)計(jì)算其局部密度。

對(duì)于每個(gè)數(shù)據(jù)點(diǎn)xi，其局部密度ρi定義為：

其中，σ取數(shù)據(jù)量的2%[8]，r為相似性系數(shù)，表示密度函數(shù)與數(shù)據(jù)點(diǎn)間相似度的關(guān)系程度，該值越大，距離點(diǎn)xi越近的點(diǎn)對(duì)其密度ρi的貢獻(xiàn)權(quán)重越大。聚類中心的擇取方式類似于DPC算法，即先利用式（3）和式（6）計(jì)算各點(diǎn)的δ和ρ值，然后通過(guò)γ值決策圖輔助獲得M個(gè)局部類的聚類中心，即選取較大的前M個(gè)γ值對(duì)應(yīng)的點(diǎn)。

因本文算法IDPCA、DPC、DPC-KNN及FKNN-DPC計(jì)算距離δ的方式相同，僅密度計(jì)算方法不同，故可通過(guò)γ=ρ×δ值來(lái)比較各密度公式。圖2（a）顯示了由3個(gè)類組成的合成數(shù)據(jù)集；圖2（b）～（f）顯示了采用不同密度方法得到的γ值決策圖，各參數(shù)為K=4，dc=1，r=2。圖2中，所采用的計(jì)算方式依次為式（2）、式（1）、式（4）～（6）。

圖2　采用5種不同密度方法計(jì)算的γ值

觀察圖2可以發(fā)現(xiàn)，與DPC算法相比，本文算法IDPCA能夠以較高區(qū)分度識(shí)別出圖2（a）數(shù)據(jù)中的3個(gè)聚類中心，而DPC-KNN算法和FKNN-DPC算法僅區(qū)分出兩個(gè)，故本文提出的密度度量方式在聚類中心選取方面具有一定的優(yōu)勢(shì)。

由于聚類中心往往出現(xiàn)在高密度區(qū)域，故將各聚類中心某鄰域內(nèi)的點(diǎn)看作核心點(diǎn)，而將其他點(diǎn)看作非核心點(diǎn)。核心點(diǎn)的獲取方法為：先將剩余點(diǎn)均分配到距其最近的聚類中心所在的類中，然后計(jì)算各局部類Cm中所有點(diǎn)與其類中心cenm間的平均距離um，若xi∈Cm在cenm的εum鄰域內(nèi)（即滿足式（8）），則 xi為核心點(diǎn)。

其中，|Cm|為第m個(gè)局部類Cm中的所有數(shù)據(jù)點(diǎn)的數(shù)目，(i=1,2,|Cm|,m=1,2,…,M)為點(diǎn) xi∈Cm與cenm間的距離；分離閾值ε與數(shù)據(jù)集大小N有關(guān)，為N‰；Xcore為核心點(diǎn)集合。

為了將剩余點(diǎn)（非核心點(diǎn)）正確歸類，本文設(shè)計(jì)了兩種分配策略：全局搜索分配策略和統(tǒng)計(jì)學(xué)習(xí)分配策略。前者是以Xcore中的每點(diǎn)為中心，不斷地搜索其未分配的KNN并將之分配到該點(diǎn)所在的局部類中。后者則是通過(guò)學(xué)習(xí)每個(gè)剩余點(diǎn)被分配至各局部類的概率來(lái)將其歸類，其學(xué)習(xí)過(guò)程如下：首先依式（9）計(jì)算xi與xj的相似度sij，若兩點(diǎn)距離越近，則其相似度越高。每點(diǎn)的歸屬由其KNN分布信息決定，若xi的KNN（KNNi）中屬于Cm的點(diǎn)越多且與xi的距離越近，則sij值越大，此時(shí)xi被分配到Cm的概率Pmi也越大。Pmi的計(jì)算方式如式（10）所示。

3.2　算法步驟

輸入：數(shù)據(jù)集X，相似性系數(shù)r，最近鄰個(gè)數(shù)K。

輸出：類標(biāo)簽labels。

步驟1使用式（3）和（6）計(jì)算每點(diǎn)的δ與ρ值。

步驟2通過(guò)決策圖獲取聚類中心。

步驟3使用式（7）和（8）提取核心點(diǎn)，并采用全局搜索分配策略將待分類點(diǎn)歸類：

（1）將核心點(diǎn)集合Xcore置入隊(duì)列Q。

（2）取隊(duì)列頭xa，并將之從Q中刪除，然后查找其K個(gè)最近鄰KNNa。

（3）若 x′∈KNNa未被分配，則將 x′分配到 xa所在的類中，并將x′添加至Q尾部；否則轉(zhuǎn)（2）。

步驟4采用統(tǒng)計(jì)學(xué)習(xí)策略分配剩余k個(gè)點(diǎn)：

（2）若MP中有非零值，則將Pmo值最大的點(diǎn)xo歸入MI(o)所表示的類中，轉(zhuǎn)（3）；否則終止該策略。

（3）更新P、MP、MI，令MP(o)=0。對(duì)于未分配點(diǎn)xp∈KNNo，更新 P[p][m]、MP(p)及 MI(p)。

（4）若MP中所有元素均為0，則終止；否則轉(zhuǎn)（3）。

步驟5仍未被處理的點(diǎn)可看作噪聲點(diǎn)，并將之歸入到其最近鄰所在的類中。

3.3　算法時(shí)間復(fù)雜度

設(shè)||U0為待分類點(diǎn)的總數(shù)目，N′為全局搜索分配

策略分配的點(diǎn)數(shù)。IDPCA算法的時(shí)間耗費(fèi)主要表現(xiàn)在四方面：（1）計(jì)算各數(shù)據(jù)點(diǎn)間的距離所需時(shí)間為O(N2)。（2）計(jì)算 ρ、δ及 γ值所需時(shí)間均為O(N)。（3）將待分類點(diǎn)都分配到距其最近的類中心，并獲取核心點(diǎn)所需時(shí)間為O(NM+N+|U0|)。（4）利用全局搜索策略分配N′個(gè)點(diǎn)所需時(shí)間為O((N-|U0|+N′)2)，使用統(tǒng)計(jì)學(xué)習(xí)策略分配剩余的N″=N-N″個(gè)點(diǎn)所需時(shí)間為O(N″2)。因此，IDPCA算法的時(shí)間復(fù)雜度近似于O(N2)。

4　實(shí)驗(yàn)結(jié)果與分析

聚類算法的性能通常是采用多種不同測(cè)試數(shù)據(jù)集來(lái)驗(yàn)證說(shuō)明的，本文選取21個(gè)不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。通過(guò)與經(jīng)典聚類算法DBSCAN、K-means、AP及近期提出的DPC算法各項(xiàng)指標(biāo)的比較，以驗(yàn)證本文算法IDPCA的性能。關(guān)于合成和真實(shí)數(shù)據(jù)集的基本屬性將于4.2節(jié)及4.3節(jié)中給出。

文中將聚類算法研究中廣為采用的聚類精度（Clustering Accuracyn，Acc）、調(diào)整互信息系數(shù)（Adjusted Mutual Information，AMI）、調(diào)整 Rand系數(shù)（Adjusted Rand Index，ARI）這3個(gè)指標(biāo)[17-18]作為聚類算法性能度量標(biāo)準(zhǔn)。其中，Acc與AMI的取值范圍均為[]0,1，ARI取值范圍為[]

-1,1，各指標(biāo)值越大，表明聚類質(zhì)量越高。

實(shí)驗(yàn)環(huán)境：硬件平臺(tái)為Intel?Core?i5-6500 CPU@3.2 GHz 3.19 GHz處理器，16.0 GB RAM；編程環(huán)境為Win7-Matlab 2015b。

4.1　實(shí)驗(yàn)參數(shù)分析

本文所提算法包含兩個(gè)參數(shù)：最近鄰個(gè)數(shù)K和相似性系數(shù)r。為了分析這兩個(gè)參數(shù)對(duì)IDPCA算法聚類質(zhì)量的影響，本文選取了較為典型的數(shù)據(jù)集Circle和S2進(jìn)行實(shí)驗(yàn)，其真實(shí)分布如圖3所示。

圖3　樣本數(shù)據(jù)分布

圖4（a）、（b）顯示了在Circle數(shù)據(jù)集上參數(shù) K 和 r對(duì)IDPCA聚類質(zhì)量的影響。當(dāng)K從3變到4時(shí)，對(duì)應(yīng)的聚類精度Acc從76.33%變到99.0%，AMI從53.68%變到95.21%，ARI從48.70%變到96.96%；當(dāng)K繼續(xù)增大時(shí)，對(duì)應(yīng)的Acc、AMI和ARI呈現(xiàn)下降趨勢(shì)。當(dāng)r從0.25變到1時(shí)，Acc、AMI和ARI急劇增大，Acc從78.67%變到了99%，AMI從61.45%變到95.21%，ARI從54.27%變到96.96%；而當(dāng)r繼續(xù)增大時(shí)，對(duì)應(yīng)的Acc、AMI和ARI亦呈緩慢下降趨勢(shì)。因此，IDPCA算法在Circle數(shù)據(jù)集上的參數(shù)選擇為 K=4和r=1。圖4（c）、（d）顯示了在S2數(shù)據(jù)集上參數(shù)K和r對(duì)IDPCA算法聚類質(zhì)量的影響。當(dāng)K逐漸增大時(shí)，對(duì)應(yīng)的Acc、AMI和ARI也逐漸增大，然后趨于穩(wěn)定。當(dāng)r逐漸增加時(shí)，各指標(biāo)值變化相對(duì)穩(wěn)定。由此可知S2數(shù)據(jù)集對(duì)參數(shù)K和r不敏感，故IDPCA算法在該數(shù)據(jù)集上的參數(shù)選擇可同Circle數(shù)據(jù)集。

圖4　參數(shù)對(duì)IDPCA算法聚類質(zhì)量的影響

通過(guò)對(duì)4.2節(jié)和4.3節(jié)中其他數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)發(fā)現(xiàn)：當(dāng)最近鄰數(shù)目K=4，相似性系數(shù)r在(0,2]區(qū)間取值時(shí)，均能獲得較好的聚類效果。為了便于獲取較好的r值，本文依文獻(xiàn)[19]的尋優(yōu)策略，通過(guò)網(wǎng)格搜索法進(jìn)行尋找。該方法將參數(shù)區(qū)域劃分成等距網(wǎng)格，通過(guò)遍歷所有網(wǎng)格點(diǎn)來(lái)尋找使算法性能達(dá)到最優(yōu)的參數(shù)。由于網(wǎng)格搜索法在步距足夠小的情況下可以在給定區(qū)域內(nèi)找出全局最優(yōu)解[20-21]，故適用于本文算法IDPCA。文中將參數(shù)r所在區(qū)間(0,2]劃分為步長(zhǎng)為0.2的10個(gè)網(wǎng)格點(diǎn)，然后遍歷每個(gè)網(wǎng)格點(diǎn)，選取使聚類結(jié)果達(dá)到最優(yōu)的r值。

4.2　合成數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)選取12個(gè)合成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，各數(shù)據(jù)集的基本屬性如表1所示。

表1　合成數(shù)據(jù)集

圖5和圖6分別顯示了IDPCA算法與DPC算法對(duì)表1中的二維數(shù)據(jù)集進(jìn)行聚類所得到的實(shí)驗(yàn)結(jié)果圖，圖中不同顏色標(biāo)識(shí)的點(diǎn)對(duì)應(yīng)著不同的類，由黑色“.”標(biāo)記的點(diǎn)為各算法識(shí)別出的聚類中心。

從圖5可看出，IDPCA算法不僅能夠給出符合直觀判斷和真實(shí)聚類情況的結(jié)果，而且能有效處理這10個(gè)數(shù)據(jù)集中所包含的類間重疊、結(jié)構(gòu)復(fù)雜以及含有噪聲干擾等情況。而在DPC算法的聚類結(jié)果中，則明顯存在著一些類別誤判。例如，對(duì)于結(jié)構(gòu)復(fù)雜Circle數(shù)據(jù)集，IDPCA算法僅將外環(huán)樣本中的兩個(gè)點(diǎn)錯(cuò)分到內(nèi)環(huán)的類中，而DPC算法卻將外環(huán)樣本中大部分點(diǎn)錯(cuò)分到內(nèi)環(huán)中的類中，主要原因是該算法對(duì)剩余點(diǎn)的分配策略會(huì)導(dǎo)致誤差傳播，即一旦有一點(diǎn)錯(cuò)分，那么比該點(diǎn)密度小的點(diǎn)也會(huì)被誤分。

為了更全面客觀地評(píng)價(jià)IDPCA算法的性能，本文不僅將IDPCA算法與DPC算法作了比較，而且與另外3種經(jīng)典的聚類算法（DBSCAN、K-means、AP）也進(jìn)行對(duì)比。使用這5種聚類算法對(duì)表1中數(shù)據(jù)集進(jìn)行聚類所得的Acc、AMI、ARI指標(biāo)結(jié)果見表2，其中粗體數(shù)據(jù)為最優(yōu)結(jié)果。

對(duì)比表2中各聚類算法所獲得Acc、AMI和ARI值可發(fā)現(xiàn)，這5種算法在DIM512和DIM1024數(shù)據(jù)集上表現(xiàn)相同，均達(dá)到了最優(yōu)，而對(duì)于其他數(shù)據(jù)集，無(wú)論是結(jié)構(gòu)較為復(fù)雜的Spiral和Circle，還是數(shù)據(jù)量較大、含噪聲程度不同以及類之間高度重疊的S1～S4，IDPCA均獲得良好的聚類效果。

4.3　真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

4.3.1UCI數(shù)據(jù)集實(shí)驗(yàn)

為了進(jìn)一步測(cè)試IDPCA算法的性能，從UCI數(shù)據(jù)庫(kù)[27]中選取8個(gè)真實(shí)數(shù)據(jù)集（如表3）進(jìn)行實(shí)驗(yàn)，以期獲得具有指導(dǎo)意義的結(jié)果。

圖5　IDPCA算法的聚類結(jié)果

圖6　DPC算法的聚類結(jié)果

表2　5種聚類算法在合成數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比

表3　UCI真實(shí)數(shù)據(jù)集

表4顯示了IDPCA及其他4種聚類算法對(duì)這8個(gè)UCI數(shù)據(jù)集進(jìn)行聚類所得的Acc、AMI、ARI指標(biāo)值，其中符號(hào)“—”表示無(wú)相應(yīng)值，加粗?jǐn)?shù)據(jù)為最優(yōu)聚類結(jié)果。

觀察表4可以發(fā)現(xiàn)，從AMI和ARI指標(biāo)看，DPC僅在Ionosphere數(shù)據(jù)集上獲得了最優(yōu)的聚類結(jié)果，K-means算法在Parkinson數(shù)據(jù)集上獲得了最優(yōu)的AMI結(jié)果，而在其余真實(shí)數(shù)據(jù)集上的最優(yōu)值均由IDPCA算法獲得。

4.3.2人臉數(shù)據(jù)集實(shí)驗(yàn)

Olivetti人臉數(shù)據(jù)集[8]（Olivetti Face Dataset）由40個(gè)類組成，每類又包含10幅維數(shù)為92×112的人臉圖，現(xiàn)已成為測(cè)試機(jī)器學(xué)習(xí)算法性能的基準(zhǔn)。由于不同類中各圖像維數(shù)及其相似度都很高，一般算法難以獲得理想的聚類效果且計(jì)算開銷較高，故本節(jié)選取該數(shù)據(jù)集的前10個(gè)類（100幅圖）進(jìn)行實(shí)驗(yàn)。

使用IDPCA及DPC、DBSCAN、AP、K-means算法對(duì)人臉數(shù)據(jù)集聚類的各指標(biāo)結(jié)果見表5。由于DPC在對(duì)該數(shù)據(jù)集聚類時(shí)，選取10個(gè)聚類中心會(huì)導(dǎo)致包含多個(gè)密度峰值的類被分裂成多類，故DPC對(duì)該數(shù)據(jù)集的聚類結(jié)果是在選取9個(gè)聚類中心時(shí)獲得的。圖7直觀顯示了IDPCA與DPC在該數(shù)據(jù)集上的聚類性能，圖中不同顏色對(duì)應(yīng)著不同的類，由紅色框標(biāo)識(shí)的為錯(cuò)分圖，右下角用白色方塊標(biāo)記的圖為算法識(shí)別出的聚類中心。

表4　五種聚類算法在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比

表5　人臉數(shù)據(jù)集對(duì)比實(shí)驗(yàn)

圖7　人臉數(shù)據(jù)集聚類對(duì)比

對(duì)比圖7（a）和（b）可以發(fā)現(xiàn)，IDPCA有效地識(shí)別出了該數(shù)據(jù)集中的10類，僅分配錯(cuò)4幅圖，其主要原因是這些圖距其真實(shí)類中的圖較遠(yuǎn)，以致它們被分配到真實(shí)類的概率值較低，故被歸入到其他類，而DPC表現(xiàn)略差。

對(duì)比表5中各聚類算法對(duì)Olivetti人臉數(shù)據(jù)集的聚類指標(biāo)值可知，IDPCA的結(jié)果均優(yōu)于其他對(duì)比算法，精度高達(dá)96%，AP表現(xiàn)也很好，精度達(dá)到了92%，其次是DPC算法。

4.4　算法效率

算法的執(zhí)行效率通常也是評(píng)估其性能的重要指標(biāo)，本節(jié)從時(shí)間復(fù)雜度方面將IDPCA與DPC、DBSCAN、AP、K-means算法進(jìn)行比較，并將這5種算法對(duì)真實(shí)數(shù)據(jù)集進(jìn)行聚類所消耗的時(shí)間進(jìn)行對(duì)比，以驗(yàn)證其優(yōu)劣性。

表6　5種聚類算法時(shí)間復(fù)雜度對(duì)比

表6顯示了IDPCA及另外4種對(duì)比算法的時(shí)間復(fù)雜度，由該表可知IDPCA與DPC算法的時(shí)間復(fù)雜度相同，均優(yōu)于AP，而劣于DBSCAN和K-means算法。表7為5種聚類算法對(duì)真實(shí)數(shù)據(jù)集進(jìn)行聚類所耗時(shí)間（均不包括計(jì)算距離矩陣或相似度矩陣的時(shí)間）。

表7　各聚類算法對(duì)真實(shí)數(shù)據(jù)集聚類所需時(shí)間s

由表7可知，K-means與DBSCAN算法的運(yùn)行時(shí)間最短，驗(yàn)證了這兩種算法具有快速有效的優(yōu)勢(shì)。盡管IDPCA與DPC算法的時(shí)間復(fù)雜度相同，但前者的執(zhí)行速率略優(yōu)于后者，而AP的計(jì)算開銷均高于其他對(duì)比算法。

通過(guò)不同數(shù)據(jù)集的聚類實(shí)驗(yàn)及算法效率對(duì)比實(shí)驗(yàn)可知，本文算法IDPCA不僅在聚類精度方面表現(xiàn)較好，其在執(zhí)行效率方面也略顯優(yōu)勢(shì)。

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

面對(duì)結(jié)構(gòu)復(fù)雜、維數(shù)較高及含噪聲的數(shù)據(jù)集，DPC算法仍難以給出符合直觀判斷并與真實(shí)聚類情況相吻合的結(jié)果，本文將K近鄰與DPC算法思想相結(jié)合，提出了一種改進(jìn)的密度峰值聚類算法。本文算法優(yōu)點(diǎn)是給出了適用于任意數(shù)據(jù)集的局部密度計(jì)算方法，以及兩種不同的剩余點(diǎn)分配策略，不僅減少了誤差傳播，而且有效提高了聚類效率。通過(guò)合成數(shù)據(jù)集實(shí)驗(yàn)表明IDPCA算法能夠獲得良好的聚類結(jié)果，尤其在處理結(jié)構(gòu)復(fù)雜的Circle、Spiral數(shù)據(jù)集以及含噪聲程度不同的S1～S4數(shù)據(jù)集時(shí)，其聚類性能在Acc、AMI及ARI方面明顯優(yōu)于DPC、AP、DBSCAN和K-means算法。IDPCA算法在真實(shí)數(shù)據(jù)集上的突出表現(xiàn)及較快的運(yùn)行速率，進(jìn)一步驗(yàn)證了其可行性和有效性。

參考文獻(xiàn):

[1]Berkhin P.A survey of clustering data mining techniques[J].Grouping Multidimensional Data，2006，43（1）：25-71.

[2]Xu R，Wunsch D.Survey of clustering algorithm[J].IEEE Transactions on Neural Networks，2005，16（3）：645-678.

[3]Xu D，Tian Y.A comprehensive survey of clustering algorithm[J].Annals of Data Science，2015，2（2）：165-193.

[4]Jain A K，Murty M N，F(xiàn)lynn P J.Data clustering：A review[J].ACM Computing Surveys，1999，31（3）：264-323.

[5]Anil K.Data clustering：50 years beyondK-means[J].Pattern Recognition Letters，2010，31（8）：651-666.

[6]Frey B J，Dueck D.Clustering by passing messages between data points[J].Science，2007，315：972-976.

[7]Ester M，Kriegel H，Sander J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining.Menlo Park：AAAI Press，1996：226-231.

[8]Rodriguez A，Laio A.Clustering by fast search and find of density peaks[J].Science，2014，344：1492-1496.

[9]Wang S，Wang D，Li C，et al.Comment on“Clustering by fast search and find of density peaks”[J].Computer Science，arXiv：1501.04267v2.

[10]Zhang W，Li J.Extended fast search clustering algorithm：widely density clusters，no density peaks[J].Computer Science，2015（5）：1-17.

[11]毋雪雁，王水花，張煜東.K最近鄰算法理論與應(yīng)用綜述[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（21）：1-7.

[12]周志陽(yáng)，馮百明，楊朋霖，等.基于Storm的流數(shù)據(jù)KNN分類算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（19）：71-75.

[13]Qin C，Song S，Huang G，et al.Unsupervised neighborhood component analysis for clustering[J].Neurocomputing，2015，168：609-617.

[14]Du M，Ding S，Jia H.Study on density peaks clustering based onK-Nearest Neighbors and principal component analysis[J].Knowledge-Based Systems，2016，99：135-145.

[15]Xie J Y，Gao H C，Xie W X，et al.Robust clustering by detecting density peaks and assigning points based on fuzzy weightedK-Nearest Neighbors[J].Information Science，2016，354：19-40.

[16]Liu Y，Ma Z，Yu F.Adaptive density peak clustering based onK-Nearest Neighbors with aggregating strategy[J].Knowledge-Based Systems，2017，133：208-220.

[17]Vinh N，Epps J，Bailey J.Information theoretic measures for clusterings comparison：Is a correction for chance necessary[C]//Proc of the 26th Annual InternationalConferenceonMachineLearning.NewYork：ACM Press，2009：1073-1080.

[18]Vinh N X，Epps J，Bailey J.Information theoretic measures for clusterings comparison：Variants，properties，normalization and correction for chance[J].Journal of Machine Learning Research，2010，11：2837-2854.

[19]Jiang Y Z，Deng Z H，Wang J，et al.Transfer generalized Fuzzy C-Means clustering algorithm with improved fuzzy partitions by leveraging knowledge[J].PR&AI，2013，26（10）：975-983.

[20]王健峰，張磊，陳國(guó)興，等.基于改進(jìn)的網(wǎng)格搜索法的SVM參數(shù)優(yōu)化[J].應(yīng)用科技，2012（3）：28-31.

[21]董婷，趙儉輝，胡勇.基于時(shí)空優(yōu)化深度神經(jīng)網(wǎng)絡(luò)的AQI等級(jí)預(yù)測(cè)[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（21）：17-23.

[22]Chang H，Yeung D Y.Robust path-based spectral clustering[J].Pattern Recognition，2008，41（1）：191-203.

[23]Veenman C，Reinders M，Backer E.A maximum variance cluster algorithm[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2002，24（9）：1273-1280.

[24]Frant P，Virmajoki O，Hautamaki V.Fast agglomerative clustering using aK-Nearest Neighbor graph[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2006，28（11）：1875-1881.

[25]Fr?nti P，Virmajoki O.Iterative shrinking method for clustering problems[J].Pattern Recognition，2006，39（5）：761-765.

[26]Fr?nti P，Virmajoki O，Hautam?ki V.Fast agglomerative clustering using aK-Nearest Neighbor graph[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2006，28（11）：1875-1881.

[27]Bache K，Lichman M.UCI machine learning repository[EB/OL].[2017-11-30].http：//archive.ics.uci.edu/ml.