自然最近鄰優(yōu)化的密度峰值聚類算法*

金 輝，錢雪忠

江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院 物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無錫 214122

1 引言

聚類分析是對(duì)一組數(shù)據(jù)對(duì)象或者物理對(duì)象進(jìn)行處理，最終將對(duì)象分成幾類，使得同一類對(duì)象之間的相似度更大，不同類對(duì)象之間的相似度更小。聚類分析已經(jīng)應(yīng)用在了數(shù)據(jù)挖掘、圖像壓縮、圖像邊緣檢測(cè)、基因識(shí)別、面部識(shí)別和文檔檢索等領(lǐng)域。

在聚類分析的發(fā)展過程中，相繼提出了K-means、DBSCAN（density-based spatial clustering of applications with noise）[1]、FCM（fuzzy C-means clustering algorithm）、AP（affinity propagation）等一系列的聚類算法文獻(xiàn)。2014年Science[2]上發(fā)表了一篇“Clustering by fast search and find of fast search”，論文提出一種快速搜索和發(fā)現(xiàn)密度峰值的聚類算法。該算法能自動(dòng)給出數(shù)據(jù)集樣本的類簇中心，而且對(duì)數(shù)據(jù)集樣本的形狀沒有嚴(yán)苛的要求，對(duì)任意形狀的數(shù)據(jù)集樣本都能實(shí)現(xiàn)高效的聚類。該算法的核心思想是認(rèn)定聚類中心同時(shí)滿足兩點(diǎn)基本要求：（1）本身的密度很大，即它的周圍鄰居點(diǎn)的密度均沒有它大；（2）與比它密度更大的數(shù)據(jù)點(diǎn)之間的“距離”更大。然而DPC（clustering by fast search and find of density peaks）算法的劣勢(shì)和難點(diǎn)不容小覷：（1）各個(gè)領(lǐng)域在使用DPC算法的時(shí)候，截?cái)嗑嚯x是該算法必須設(shè)定的參數(shù)，人們一直是手工設(shè)定該參數(shù)，手工設(shè)定存在一定的隨機(jī)性和人為因素，影響聚類質(zhì)量。（2）對(duì)較高維度數(shù)據(jù)的分析處理一直是DPC算法的短板，較高維度數(shù)據(jù)自身結(jié)構(gòu)擁有稀疏性和空間復(fù)雜性，使得傳統(tǒng)的歐式距離在反映數(shù)據(jù)對(duì)象之間的相似性時(shí)無法達(dá)到準(zhǔn)確、合理的目的，因此導(dǎo)致該算法失效。（3）雖然DPC算法聲稱能自動(dòng)確定聚類結(jié)果，但在實(shí)際聚類操作中卻需要手動(dòng)進(jìn)行聚類結(jié)果的選定，聚類結(jié)果不能自動(dòng)給出。

針對(duì)DPC聚類算法存在的不足，Zhang等[3]結(jié)合該算法和 Chameleon（hierarchical clustering using dynamic modeling）算法，提出了E_CFSFDP（extended fast search clustering algorithm：widely density clusters,no density peaks），解決了CFSFDP（clustering by fast search and find of density peaks）算法中無法處理一個(gè)類簇中有一個(gè)以上密度峰值點(diǎn)的問題，但是該算法的性能有待進(jìn)一步提高并且在處理高維數(shù)據(jù)上的能力有待加強(qiáng)。Liu等[4]提出一種基于K近鄰（Knearest neighbor，KNN）的快速密度峰值搜索并高效分配樣本的算法KNN-DPC，解決了CFSFDP算法聚類結(jié)果對(duì)截?cái)嗑嚯xdc比較敏感和因?yàn)橐徊椒峙渌鶐淼倪B帶分配錯(cuò)誤的問題，但是該算法的聚類結(jié)果對(duì)近鄰數(shù)K的選取比較敏感。Bie等[5]提出了Fuzzy-CFSFDP算法，將模糊規(guī)則用于CFSFDP算法的類簇的中心點(diǎn)確定中，提高了類簇中心點(diǎn)選取和聚類結(jié)果的準(zhǔn)確率，但在處理復(fù)雜數(shù)據(jù)[6-9]時(shí)稍顯不足。

本文針對(duì)上述遇到的問題，提出了自然最近鄰[10-11]優(yōu)化的密度峰值聚類算法（optimized density peak clustering algorithm by natural nearest neighbor,TNDP）。TNDP算法自適應(yīng)地、不需要參數(shù)地、根據(jù)每個(gè)點(diǎn)的特征來獲得不同的鄰居數(shù)，以此來計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度，根據(jù)類簇中心局部密度大和被稀疏區(qū)域劃分[12]的特點(diǎn)來確定聚類中心，最后引入類間相似度的概念來合并相似度高的類簇。實(shí)驗(yàn)證明，TNDP算法具有更加優(yōu)秀的聚類效果。

2 自然最近鄰居

最近鄰居概念在早先就已經(jīng)被提出，且被廣泛應(yīng)用于模式識(shí)別、機(jī)器學(xué)習(xí)等領(lǐng)域。最著名的就是Stevens所提出的兩個(gè)鄰居概念，K-最近鄰[13-15]和ε-最近鄰。K-最近鄰的思想是給定一個(gè)數(shù)據(jù)集，設(shè)置一個(gè)參數(shù)K，然后每個(gè)數(shù)據(jù)對(duì)象在數(shù)據(jù)集中找到K個(gè)與自身相似度最大或者距離最小的數(shù)據(jù)對(duì)象。ε-最近鄰的基本思想是給定一個(gè)數(shù)據(jù)集，設(shè)置一個(gè)參數(shù)掃描半徑ε，然后求出每個(gè)數(shù)據(jù)對(duì)象在其掃描半徑ε內(nèi)的近鄰數(shù)，這樣使得每個(gè)數(shù)據(jù)對(duì)象在掃描半徑ε內(nèi)的近鄰數(shù)有可能不同。無論是K-最近鄰還是ε-最近鄰，其近鄰的搜索都是靠人為地設(shè)置參數(shù)得到的，而不是根據(jù)所給數(shù)據(jù)集自身的特性搜索。

自然最近鄰居（natural nearest neighbor，TN）是一種新的最近鄰居概念[16]，它是一種無尺度的最近鄰居，這也是它與K-最近鄰和ε-最近鄰最大的不同之處。自然最近鄰居的基本思想就是數(shù)據(jù)集中密集區(qū)域的數(shù)據(jù)點(diǎn)擁有較多的鄰居，稀疏區(qū)域的數(shù)據(jù)點(diǎn)擁有較少的鄰居，而數(shù)據(jù)集中最離群的數(shù)據(jù)點(diǎn)只有幾個(gè)或沒有最近鄰居，自然最近鄰居的特點(diǎn)是計(jì)算過程不需要任何的參數(shù)，數(shù)據(jù)點(diǎn)根據(jù)數(shù)據(jù)集自身的屬性特點(diǎn)獲得準(zhǔn)確鄰居，鄰居數(shù)由于數(shù)據(jù)的密集程度存在差異，由于噪聲點(diǎn)和異常點(diǎn)沒有鄰居，因此正常點(diǎn)也不會(huì)把噪聲點(diǎn)和異常點(diǎn)當(dāng)作鄰居。

定義1（自然最近鄰居） 基于自然鄰居搜索算法，如果點(diǎn)X屬于點(diǎn)Y的鄰居，而點(diǎn)Y屬于點(diǎn)X的鄰居，那么點(diǎn)X和Y屬于彼此的自然鄰居。

定義2（自然特征值supk） 根據(jù)TN-Searching算法，每個(gè)點(diǎn)有不同數(shù)量的鄰居，對(duì)于任何點(diǎn)i，鄰居數(shù)量是nb（i）。但是TN-Searching有一個(gè)平均數(shù)量的鄰居，稱為supk，它是自然特征值。計(jì)算supk的公式如下：

定義3（R-鄰域（R-neighbor））findKNN(xi,r)表示KNN搜索函數(shù)，它返回xi的第r個(gè)鄰居，KNNr(xi)是X的子集，定義如下：

算法1TN-Searching

3 TNDP算法

定義4（數(shù)據(jù)點(diǎn)的密度Den(Pi)） 基于自然鄰居定義的密度如下：

這里nb(i)是根據(jù)TN-Searching算法得到的每個(gè)點(diǎn)的自然鄰居數(shù)，N(i,nb(i))是點(diǎn)i的nb(i)個(gè)自然鄰居，dist(i,j)是數(shù)據(jù)點(diǎn)i和j之間的距離。

定義5（代表點(diǎn)（exemplar）） 數(shù)據(jù)點(diǎn)q的代表點(diǎn)定義為：

定義6（密度峰（density peak）） 如果數(shù)據(jù)點(diǎn)p滿足如下條件，就稱數(shù)據(jù)點(diǎn)p為一個(gè)密度峰：

二是建立完善管理責(zé)任制度。在天津日?qǐng)?bào)公布了133條（段）納入河長(zhǎng)制管理的河道和57名“河長(zhǎng)”名單，由“河長(zhǎng)”對(duì)河道水生態(tài)環(huán)境管理負(fù)總責(zé)。各區(qū)縣出臺(tái)了具體的實(shí)施方案，細(xì)化分解落實(shí)責(zé)任至街鎮(zhèn)、單位，有的區(qū)縣還明確了街鎮(zhèn)級(jí)河長(zhǎng)。各區(qū)縣制定了保潔養(yǎng)管及巡查制度，組建或利用已有保潔隊(duì)伍，對(duì)河道進(jìn)行日常保潔，全市水生態(tài)環(huán)境管理責(zé)任制初步建立。

定義7（類間相似度（similarity between clusters））

|Ci?Cj|指的是類Ci和類Cj的公共部分，supk是自然鄰居特征值，Sim(Ci,Cj)的值不小于0，如果這兩個(gè)相鄰的初始簇被稀疏區(qū)域劃分，則這兩個(gè)簇之間的相似性將很小，是兩個(gè)單獨(dú)的集群。相反，如果這兩個(gè)相鄰的初始簇通過密度區(qū)域連接，則這兩個(gè)相鄰簇之間的相似性會(huì)很大，然后這兩個(gè)集群將被合并為一個(gè)集群。

定義8（稀疏鄰居和密集鄰居（sparse and dense neighbor）） 如果數(shù)據(jù)點(diǎn)q的密度小于數(shù)據(jù)點(diǎn)p的密度且q是p的自然鄰居，則稱q是p的稀疏鄰居，相反如果數(shù)據(jù)點(diǎn)q的密度大于等于數(shù)據(jù)點(diǎn)p的密度且q是p的自然鄰居，則稱q是p的密集鄰居，定義如下：

算法2TNDP

根據(jù)以上理論，提出TNDP算法，TNDP算法的主要優(yōu)點(diǎn)：（1）用自然最近鄰居來計(jì)算數(shù)據(jù)點(diǎn)的局部密度，不需要參數(shù)，避免了參數(shù)敏感問題；（2）用自然最近鄰居計(jì)算局部密度，由于自然最近鄰居準(zhǔn)確反映數(shù)據(jù)點(diǎn)的屬性特點(diǎn)，因此這樣計(jì)算出來的局部密度能準(zhǔn)確表示每個(gè)數(shù)據(jù)點(diǎn)的密度大小，提高聚類效果；（3）由于自然最近鄰居不包含噪聲點(diǎn)和異常點(diǎn)，因此TNDP算法減少了噪聲點(diǎn)和異常點(diǎn)對(duì)聚類結(jié)果的影響。

TNDP算法的主要流程：

步驟2使用定義5和定義8找到每個(gè)數(shù)據(jù)點(diǎn)的代表點(diǎn)和稀疏鄰居；

步驟3找到所有的密度峰并任意訪問一個(gè)密度峰，將它和它的稀疏鄰居分到同一個(gè)聚類；

步驟4任意在這個(gè)簇中找到一個(gè)點(diǎn)，并將這個(gè)點(diǎn)的稀疏鄰居和這個(gè)點(diǎn)分類為同一個(gè)簇，直到這個(gè)簇的所有點(diǎn)都被訪問過；

步驟5找到一個(gè)未訪問的密度峰并重復(fù)上述步驟，直到所有的密度峰都被訪問過；

步驟6劃分好初始類簇，根據(jù)初始類簇之間的相似度關(guān)系，合并相似度高的初始類簇；

步驟7將類簇中數(shù)據(jù)個(gè)數(shù)小于最小自然鄰居數(shù)的類簇從聚類結(jié)果中除去，并將這些類簇中的數(shù)據(jù)標(biāo)記為噪聲點(diǎn)，獲得最終的聚類結(jié)果。

如圖1所示，綠色點(diǎn)同時(shí)被分類為C1和C2，相似度大于α，C1和C2合并成一類，如果相似度小于α，那么綠色點(diǎn)將被分類到其代表點(diǎn)所屬的集群中。α值越大，聚類越多。實(shí)際上，TNDP算法在參數(shù)α的選擇上是魯棒的。

因?yàn)門NDP算法使用k-d樹來求自然鄰居，所以TNDP的算法復(fù)雜度為O(n×lgn)。

Fig.1 Intersection ofC1andC2圖1 C1和C2的交集

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

為了證明TNDP算法的有效性，將TNDP算法與DPC、DBSCAN、K-means算法在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，圖2顯示了4個(gè)合成數(shù)據(jù)集。Data1是由兩個(gè)流形類組成，共1 500個(gè)點(diǎn)。Data2是由3個(gè)復(fù)雜流形類組成，共3 603個(gè)點(diǎn)。Data3由3個(gè)球形類、2個(gè)復(fù)雜流形類和1個(gè)稀疏密度類組成。Data4由6個(gè)高密度復(fù)雜流形類和一些噪聲點(diǎn)組成。對(duì)于DPC和DBSCAN算法，進(jìn)行多次實(shí)驗(yàn)取效果最好的結(jié)果進(jìn)行對(duì)比，對(duì)于K-means假設(shè)事先知道所要?jiǎng)澐值念悢?shù)進(jìn)行實(shí)驗(yàn)。

圖3顯示了Data1在DPC、DBSCAN、K-means和TNDP算法上的聚類效果。DPC算法雖然能聚類正確的類簇?cái)?shù)，但無法將所有點(diǎn)準(zhǔn)確聚類，聚類效果不好，流形簇相互靠近的地方無法正確聚類。K-means算法同樣無法準(zhǔn)確聚類兩個(gè)流形簇相互靠近的地方，聚類效果不好。DBSCAN算法和TNDP算法都能準(zhǔn)確聚類，聚類效果都不錯(cuò)，明顯比DPC和K-means算法聚類效果要好，但DBSCAN算法需要更多的參數(shù)設(shè)置。

圖4顯示了Data2在DPC、DBSCAN、K-means和TNDP算法上的聚類效果。DPC和K-means算法雖然選擇了正確的類簇?cái)?shù)，但無法將所有點(diǎn)準(zhǔn)確聚類，聚類效果不好，只是將復(fù)雜流形簇距離近的點(diǎn)聚為一類，DBSCAN聚類算法和TNDP算法都能準(zhǔn)確聚類，聚類效果都很好。

Fig.2 Original datasets圖2 原始數(shù)據(jù)集

Fig.3 Clustering results of DPC、DBSCAN、K-means and TNDP on Data1圖3 Data1在DPC、DBSCAN、K-means、TNDP上的聚類結(jié)果

Fig.4 Clustering results of DPC、DBSCAN、K-means and TNDP on Data2圖4 Data2在DPC、DBSCAN、K-means、TNDP上的聚類結(jié)果

Fig.5 Clustering results of DPC、DBSCAN、K-means and TNDP on Data3圖5 Data3在DPC、DBSCAN、K-means、TNDP上的聚類結(jié)果

圖5顯示了Data3在DPC、DBSCAN、K-means和TNDP算法上的聚類效果。DPC算法對(duì)球形簇的聚類效果很好，對(duì)復(fù)雜流形簇也有一定的聚類效果，但是對(duì)Data3顯然沒有取得很好的聚類效果，K-means可以聚類球形簇，但是對(duì)復(fù)雜流形簇聚類效果不好，顯然DBSCAN聚類效果優(yōu)于DPC和K-means算法，對(duì)球形簇和復(fù)雜流形簇都有很好的聚類效果，但是對(duì)于密度差異較大的類簇聚類效果一般，將一些正常點(diǎn)當(dāng)作噪聲點(diǎn)，也錯(cuò)誤地將不同類簇的點(diǎn)聚為一類，TNDP算法聚類效果比DBSCAN更加優(yōu)秀，不僅準(zhǔn)確聚類球形簇和復(fù)雜流形簇，對(duì)密度差異較大的類簇也準(zhǔn)確聚類。

圖6顯示了Data4在DPC、DBSCAN、K-means和TNDP算法上的聚類效果。DPC和K-means算法雖然選擇了正確的類簇?cái)?shù)，但對(duì)復(fù)雜流形簇的聚類效果不好，只是將復(fù)雜流形簇相對(duì)距離近的點(diǎn)聚為一類，DBSCAN獲得了正確的類簇?cái)?shù)，也檢測(cè)出了噪聲點(diǎn)，但是正常類簇中的一些點(diǎn)也被DBSCAN視為噪聲點(diǎn)，盡管TNDP未能檢測(cè)到Data4中的噪聲，但TNDP獲得了正確的聚類數(shù)并正確聚類了所有正常點(diǎn)。

因此，TNDP算法在Data1、Data2、Data3、Data4上的聚類效果明顯優(yōu)于DPC和K-means算法，在Data3、Data4上的聚類效果明顯優(yōu)于DBSCAN，且比DBSCAN需要更少的參數(shù)，并且對(duì)參數(shù)的設(shè)置具有一定的魯棒性。

接著，將TNDP算法在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集信息如表1。

Table 1 Information of datasets表1 數(shù)據(jù)集信息

在實(shí)驗(yàn)中，采用Acc（準(zhǔn)確率）、F-Measure（加權(quán)F值）這兩個(gè)聚類指標(biāo)來評(píng)價(jià)TNDP算法，并將TNDP算法與DPC、DBSCAN、K-means算法對(duì)比。

Fig.6 Clustering results of DPC、DBSCAN、K-means and TNDP on Data4圖6 Data4在DPC、DBSCAN、K-means、TNDP上的聚類結(jié)果

由表2可知，在準(zhǔn)確率上，TNDP算法要明顯優(yōu)于DPC、DBSCAN、K-means算法，在F值的計(jì)算上，除了在Wpbc數(shù)據(jù)集上DBSCAN要優(yōu)于TNDP算法，其他數(shù)據(jù)集上都是TNDP算法要明顯優(yōu)于DPC、DBSCAN、K-means算法，且對(duì)這幾個(gè)數(shù)據(jù)集TNDP算法都能聚類出正確的類數(shù)。綜合這三方面，顯然TNDP算法是最優(yōu)秀的。

Table 2 Information of clustering index表2 聚類指標(biāo)信息

TNDP除了在聚類效果上的優(yōu)越性，在對(duì)參數(shù)的選擇上也具有一定的魯棒性。如圖7所示，在不同的參數(shù)α的選擇下，聚類效果依舊沒有發(fā)生變化，只有當(dāng)α從0.01提高到2.00時(shí)，聚類結(jié)果才出現(xiàn)了一點(diǎn)點(diǎn)偏差。

因?yàn)槭艿阶匀蛔罱従拥挠绊?，一個(gè)類簇中相似初始簇的類簇間相似度會(huì)在一個(gè)小的范圍內(nèi)波動(dòng)，不同類簇之間的相似度一定很小，甚至為0，所以對(duì)參數(shù)α的取值不是那么敏感。做實(shí)驗(yàn)時(shí)一般取所有數(shù)據(jù)個(gè)數(shù)的1/100與自然特征值的比值作為初始α。如果α取值過高，原本屬于一個(gè)類簇的數(shù)據(jù)會(huì)被分成多個(gè)類簇；如果α取值過低，可能原本兩個(gè)相似度很小的類簇會(huì)被分成一個(gè)類簇。

Fig.7 Clustering results of TNDP with different parameter α圖7 不同參數(shù)α下TNDP的聚類結(jié)果

5 結(jié)束語

本文提出了一種新的基于自然最近鄰居的密度峰值聚類算法TNDP。首先，該算法通過引入自然最近鄰居的概念來計(jì)算數(shù)據(jù)點(diǎn)的局部密度，然后通過類簇間被稀疏區(qū)域劃分來找到密度峰值，最后通過類簇間相似度的概念來把相似的類簇合并產(chǎn)生最后的聚類結(jié)果。通過實(shí)驗(yàn)，TNDP算法在對(duì)復(fù)雜流形數(shù)據(jù)和密度變化大的數(shù)據(jù)的處理上具有相當(dāng)大的優(yōu)越性，比DPC、DBSCAN、K-means算法更有效，擁有更少的參數(shù)，只有一個(gè)類簇間相似度，且對(duì)類簇間相似度的選擇具有一定的魯棒性。