自適應(yīng)聚合策略優(yōu)化的密度峰值聚類算法*

錢雪忠，金 輝

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

1 引言

隨著信息技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展，數(shù)據(jù)源的多樣化和數(shù)據(jù)量的高速增長，如何進(jìn)行大規(guī)模的數(shù)據(jù)挖掘和快速獲得有價(jià)值的信息成為近期研究的焦點(diǎn)。聚類分析作為一種重要的數(shù)據(jù)挖掘技術(shù)，廣泛應(yīng)用于模式識(shí)別、圖像處理、機(jī)器學(xué)習(xí)、信息檢索等領(lǐng)域。聚類是一個(gè)根據(jù)樣本間的相似性將數(shù)據(jù)集劃分成簇的過程，使得簇內(nèi)的對象最大程度地相似，同時(shí)不同簇間的對象最大程度地相異。

在聚類分析的發(fā)展過程中，相繼提出了DBSCAN[1]（density-based spatial clustering of applications with noise）、FCM（fuzzy C-means）、AP（affinity propagation）等一系列的具有代表性的聚類算法。2014年Science[2]上發(fā)表了一篇Clustering by fast search and find of fast search（DPC），論文提出一種快速搜索和發(fā)現(xiàn)密度峰值的聚類算法。該算法簡單高效，無需迭代，性能不受數(shù)據(jù)空間維度影響自動(dòng)給出數(shù)據(jù)集樣本的類簇中心，而且對數(shù)據(jù)集樣本的形狀沒有嚴(yán)苛的要求，對任意形狀的數(shù)據(jù)集樣本都能實(shí)現(xiàn)高效的聚類。然而DPC 算法也存在一些缺陷：算法需要設(shè)置截?cái)嗑嚯xdc，算法的準(zhǔn)確性需要依賴截?cái)嗑嚯xdc的選擇和對數(shù)據(jù)集的密度估計(jì);算法使用歐氏距離定義樣本之間的相似性來計(jì)算局部密度，存在局限性；聚類中心的選擇需要人工干預(yù)而且有的時(shí)候聚類中心的選擇不是那么明顯，選擇起來有一定的困難等。

針對DPC 聚類算法存在的不足，Xu 等[3]提出將網(wǎng)格劃分和圓劃分的方法應(yīng)用于DPC 算法來篩選點(diǎn)，提出基于網(wǎng)格劃分的密度峰值聚類算法和基于圓劃分的密度峰值聚類算法，都能降低算法復(fù)雜度，前者的計(jì)算時(shí)間更短，后者在大規(guī)模數(shù)據(jù)集上的準(zhǔn)確度要高于DPC 算法。Du 等[4]提出一種基于K近鄰的快速密度峰值搜索并高效分配樣本的算法KNNDPC（study on density peaks clustering based onKnearest neighbors and principal component analysis），解決了DPC 算法聚類結(jié)果對截?cái)嗑嚯xdc比較敏感和因?yàn)橐徊椒峙渌鶐淼倪B帶分配錯(cuò)誤的問題，但是該算法的聚類結(jié)果對近鄰數(shù)K的選取比較敏感。針對如何準(zhǔn)確獲取密度峰值聚類算法聚類中心的問題，文獻(xiàn)[5-6]提出了新的獲取聚類中心的策略，并且較少受到參數(shù)影響，提高了聚類的準(zhǔn)確率，但是在處理復(fù)雜數(shù)據(jù)[7-10]和大數(shù)據(jù)時(shí)稍顯不足。

本文針對上述遇到的問題，提出了自適應(yīng)聚合策略優(yōu)化的密度峰值聚類算法AKDP（optimited density peak clustering algorithm by adaptive aggregation strategy）。AKDP 算法根據(jù)數(shù)據(jù)點(diǎn)的K近鄰數(shù)來計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度[11-16]，然后用一種新的方法來確定初始聚類中心，最后提出類簇間密度可達(dá)的概念來聚合相似度高的類簇，實(shí)驗(yàn)證明AKDP 算法具有更加優(yōu)秀的聚類效果。

2 局部密度和初始類簇中心

密度峰聚類DPC 算法基于這樣的假設(shè)：聚類中心具有比其鄰居更高的局部密度，并且與其他中心的距離相對較大[17-19]。為了建立決策圖然后找到理想的聚類中心，DPC 計(jì)算每個(gè)點(diǎn)i的兩個(gè)量：由式（1）定義的局部密度ρi和由式（2）定義的和更高密度點(diǎn)的距離δi。

其中，dij是點(diǎn)i和點(diǎn)j之間的距離，dc是用戶輸入的截止距離，其可以根據(jù)百分比參數(shù)p計(jì)算得到，p則表示數(shù)據(jù)對象的近鄰數(shù)占總樣本數(shù)的平均百分比，一般情況下p在1～2 取值時(shí)，DPC 算法能夠取得較好的聚類效果。如果t＜0，則χ(t)=1，否則χ(t)=0。對于具有最高密度的點(diǎn)，其Δ取為δi=maxj(dij)。在計(jì)算所有點(diǎn)的密度和Δ值之后，DPC 繪制決策圖，其由點(diǎn)的集合(ρi,δi)組成?？梢栽跊Q策圖的右上區(qū)域找到聚類中心，這些聚類中心是具有高δ和相對高ρ的點(diǎn)。通過聚類中心，DPC 可以在一個(gè)步驟中將剩余的點(diǎn)分配給與其最近的較高密度的鄰居相同的聚類。結(jié)果，DPC 的執(zhí)行是有效的。具體地，對于“小”數(shù)據(jù)集（例如，對于聲納數(shù)據(jù)集），難以對密度進(jìn)行可靠的估計(jì)。因此，DPC 采用式（3）給出的另一個(gè)密度度量來計(jì)算局部密度。

然而，它沒有客觀的度量來決定數(shù)據(jù)集是小還是大，而使用這兩個(gè)密度指標(biāo)進(jìn)行聚類會(huì)產(chǎn)生非常不同的結(jié)果。此外，對于小型數(shù)據(jù)集，即使使用式（3）計(jì)算局部密度，DPC 的聚類結(jié)果也會(huì)受到截止距離dc的極大影響。為了消除截止距離dc的影響并為任何大小的數(shù)據(jù)集提供統(tǒng)一的密度度量，本文將引入K最近鄰居的思想來計(jì)算局部密度，采用一種新的方法來選擇初始聚類中心，并且提供一種新的聚合策略來聚合初始的類簇。

為了使得核心區(qū)域中的點(diǎn)更易于區(qū)分其他區(qū)域中的點(diǎn)，也為了提供一個(gè)統(tǒng)一的密度度量，通過使用高斯核函數(shù)提出了基于K最近鄰概念的新密度度量，這將有助于群集獲得更準(zhǔn)確的結(jié)果。相對于原先的局部密度度量計(jì)算不同數(shù)據(jù)集需要的不同度量方式，本文提出的局部密度度量減少了算法的人為選擇，也使算法更易區(qū)分類簇中心。為了簡化算法使算法具有更高的普適性和減少人為的干預(yù)，將截?cái)嗑嚯xdc定義為一個(gè)普適性的公式，使算法更加智能。因此，本文提出了一種新的局部密度定義公式，如式（4）所示：

其中，N指的是數(shù)據(jù)點(diǎn)的個(gè)數(shù)，指的是數(shù)據(jù)點(diǎn)i和它的第K個(gè)近鄰之間的距離，uk指的是所有數(shù)據(jù)點(diǎn)和它的第K個(gè)近鄰之間的距離的平均值，即所有數(shù)據(jù)點(diǎn)的值的平均值。為了AKDP 算法的聚類效果，定義了一個(gè)確定初始聚類中心的閾值α，如式（5）所示：

3 聚合策略

為了使AKDP 算法更加智能有效地將數(shù)據(jù)集進(jìn)行有效的聚合分離，本文基于以下的定義提出了一種新的有效的聚合策略。

定義1（簇核距離（core-distance of a cluster））一個(gè)類簇u的核距離，表示為σu，定義為：

其中，|Cu|指的是類簇u中的數(shù)據(jù)點(diǎn)的個(gè)數(shù)，di,center指的是數(shù)據(jù)點(diǎn)i和類簇中心之間的距離。

定義2（邊界點(diǎn)對（border-points-pair））在類簇Cu和類簇Cv之間的邊界點(diǎn)對，表示為，定義為：

定義3（邊界密度（border-density of a cluster））類簇u的邊界密度表示為，定義為：

其中，Bu是類簇u和數(shù)據(jù)集中所有其他的類簇的邊界點(diǎn)對。

定義4（密度直接可達(dá)（density directly-reachable））一個(gè)類簇u和一個(gè)類簇v可以通過邊界密度直接密度可達(dá)，只要滿足以下條件：

即類簇u和v之間存在邊界點(diǎn)對，且存在邊界點(diǎn)對滿足第二個(gè)條件。

定義5（密度可達(dá)（density reachable））如果存在類簇u和類簇w直接密度可達(dá)，類簇w又和類簇v直接密度可達(dá)，那么說類簇u和類簇v是密度可達(dá)的。

通過以上定義，在實(shí)驗(yàn)中如果發(fā)現(xiàn)兩個(gè)類簇之間是密度可達(dá)的，那么就會(huì)合并這兩個(gè)類簇。通過自適應(yīng)合并策略，可以找出所有的初始類簇中心，但是這些初始類簇并不一定就是最好的聚類結(jié)果，它們之間具有一定的相似性，通過類簇間密度可達(dá)合并相似類簇，不會(huì)遺漏掉類簇原本的類簇中心，也大大提高了算法的準(zhǔn)確性。

根據(jù)以上理論，提出AKDP 算法，AKDP 算法的主要優(yōu)點(diǎn)：

（1）用一種新的基于K近鄰的公式來計(jì)算數(shù)據(jù)點(diǎn)的局部密度，避免了參數(shù)敏感問題，提高了算法對數(shù)據(jù)集的普適性；

（2）算法自適應(yīng)策略給出的初始閾值可以找出所有的初始類簇中心，確保不會(huì)遺漏掉真實(shí)的類簇中心，有效提高算法準(zhǔn)確率；

（3）用一種有效的、無參的聚合策略來產(chǎn)生最后的結(jié)果，合并相似度高的類簇，提高聚類效果。

算法AKDP：

假設(shè)AKDP 算法要處理的數(shù)據(jù)集有N個(gè)數(shù)據(jù)點(diǎn)，存儲(chǔ)每個(gè)點(diǎn)到第K個(gè)近鄰點(diǎn)的距離需要K×N個(gè)空間；其次，存儲(chǔ)每個(gè)數(shù)據(jù)點(diǎn)的δ和ρ值，需要2×N個(gè)空間；最后，存儲(chǔ)邊界點(diǎn)對集合最多需要N2個(gè)空間，因此AKDP 算法的空間復(fù)雜度是O(N2)。

AKDP 算法的時(shí)間復(fù)雜度由以下幾點(diǎn)決定，計(jì)算數(shù)據(jù)點(diǎn)之間的距離的時(shí)間復(fù)雜度是O(N2)，但可以用快速排序降至O(N×lgN)，每個(gè)數(shù)據(jù)點(diǎn)的邊界點(diǎn)的數(shù)量理論上可以達(dá)到N，計(jì)算邊界點(diǎn)對的時(shí)間復(fù)雜度為O(N2)，因此AKDP 算法的時(shí)間復(fù)雜度為O(N2)。

AKDP 算法對參數(shù)K的選擇遵循一定的規(guī)律，一般先選擇數(shù)據(jù)樣本的10%作為初始值，聚類個(gè)數(shù)如果偏多則增加K的值，反之減小K的值。

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

為了證明AKDP 算法的有效性，將AKDP 算法與DPC[2]、DBSCAN[1]、KNNDPC[4]算法在合成數(shù)據(jù)集和UCI 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，真實(shí)數(shù)據(jù)集上加上了Kmeans 算法進(jìn)行對比。圖1 顯示了4 個(gè)合成數(shù)據(jù)集。Data1由兩個(gè)不平衡的流形類組成，共567個(gè)點(diǎn)。Data2由3 個(gè)復(fù)雜流形類組成，共3 603 個(gè)點(diǎn)。Data3 由7 個(gè)復(fù)雜球形類組成，共788 個(gè)點(diǎn)。Data4 由31 個(gè)高密度復(fù)雜球形類組成，共3 100 個(gè)點(diǎn)。對于DPC 算法、KNNDPC 算法和DBSCAN 算法，進(jìn)行多次實(shí)驗(yàn)取效果最好的結(jié)果進(jìn)行對比，但DPC 算法和KNNDPC 算法在人為選擇聚類中心時(shí)要符合選取聚類中心的一般規(guī)則。

圖2 顯示了Data1 在DPC、DBSCAN、KNNDPC和AKDP 算法上的聚類效果。DPC 算法能聚類正確的類簇?cái)?shù)，也可以將所有點(diǎn)準(zhǔn)確聚類，聚類效果較好，KNNDPC 算法同樣可以準(zhǔn)確聚類，DBSCAN 算法無法準(zhǔn)確確定類簇的個(gè)數(shù)，聚類效果不好，錯(cuò)誤地將一個(gè)類簇的點(diǎn)聚類成了兩個(gè)類簇，AKDP 算法能準(zhǔn)確聚類，聚類效果也很好，明顯比DBSCAN 算法聚類效果要好，總之在Data1 數(shù)據(jù)集上，DBSCAN 算法聚類效果不好，DPC 算法、KNNDPC 算法和AKDP 算法可以準(zhǔn)確確定類簇的個(gè)數(shù)且聚類效果很好，但是DPC算法和KNNDPC 算法需要一定的人為選擇，有不確定因素。

Fig.1 Original dataset圖1 原始數(shù)據(jù)集

Fig.2 Clustering results of DPC,DBSCAN, KNNDPC and AKDP on Data1圖2 Data1 在DPC、DBSCAN、KNNDPC、AKDP 上的聚類結(jié)果

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

圖4 顯示了Data3 在DPC、DBSCAN、KNNDPC和AKDP 算法上的聚類效果。DPC 算法對球形簇的聚類效果很好，對復(fù)雜流形簇也有一定的聚類效果，但是對Data3 數(shù)據(jù)集顯然沒有取得很好的聚類效果，將離得近的一大兩小三個(gè)球形數(shù)據(jù)集錯(cuò)誤地聚為一個(gè)類簇，KNNDPC 算法存在和DPC 算法類似的問題，錯(cuò)誤地將兩個(gè)流形的數(shù)據(jù)集聚為一類，聚類產(chǎn)生偏差，顯然DBSCAN 算法聚類效果優(yōu)于DPC 算法和KNNDPC 算法，對數(shù)據(jù)集具有很好的聚類效果，但是DBSCAN 算法的參數(shù)需求更大，AKDP 算法能夠準(zhǔn)確確定類簇的個(gè)數(shù)，同時(shí)最后的聚類效果也十分優(yōu)秀。

圖5 顯示了Data4 在DPC、DBSCAN、KNNDPC和AKDP 算法上的聚類效果。DPC 算法和KNNDPC算法雖然選擇了正確的類簇?cái)?shù)，聚類效果也很不錯(cuò)，但是聚類時(shí)間較長，且在人工決策圖上需要選出的聚類中心點(diǎn)多且密集，稍有偏差就會(huì)對聚類效果產(chǎn)生不好的影響，DBSCAN 獲得了正確的類簇?cái)?shù)，也獲得了好的聚類效果，但是同樣的需要較多的參數(shù)，AKDP 算法獲得了正確的聚類數(shù)并獲得了很好的聚類效果，人為影響較小。

因此，AKDP算法在Data1數(shù)據(jù)集上的聚類效果明顯優(yōu)于DBSCAN 算法，在Data2、Data3 上的聚類效果明顯優(yōu)于DPC算法和KNNDPC 算法，且比DBSCAN需要更少的參數(shù)，比DPC 算法和KNNDPC 算法需要人為干預(yù)的更少，具有一定的魯棒性。

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

在實(shí)驗(yàn)中，采用Acc（準(zhǔn)確率）、F-measure（加權(quán)F值）和算法聚類個(gè)數(shù)與正確的類簇?cái)?shù)的比這3 個(gè)聚類指標(biāo)來評價(jià)AKDP 算法，并將AKDP 算法與DPC、DBSCAN、KNNDPC、K-means 算法對比，實(shí)驗(yàn)結(jié)果如表2 所示。

Fig.3 Clustering results of DPC,DBSCAN, KNNDPC and AKDP on Data2圖3 Data2 在DPC、DBSCAN、KNNDPC、AKDP 上的聚類結(jié)果

Fig.5 Clustering results of DPC,DBSCAN, KNNDPC and AKDP on Data4圖5 Data4 在DPC、DBSCAN、KNNDPC、AKDP 上的聚類結(jié)果

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

由表2 可知，在準(zhǔn)確率上，除了在Vote 數(shù)據(jù)集上KNNDPC 算法比AKDP 算法高0.2 個(gè)百分點(diǎn)，在其他數(shù)據(jù)集上AKDP 算法要明顯優(yōu)于DPC、DBSCAN、KNNDPC 和K-means算法。

在F值的計(jì)算上，除了在Breast 和Wpbc 數(shù)據(jù)集上DBSCAN 要稍稍優(yōu)于AKDP 算法，其他數(shù)據(jù)集上AKDP 算法都明顯優(yōu)于DPC、DBSCAN、KNNDPC 和K-means算法。

在最終聚類數(shù)的準(zhǔn)確率上，AKDP 算法都能聚類出正確的類數(shù)，K-means 算法由于提前選擇了正確的類簇?cái)?shù)目，因此不存在能不能聚類出最終正確的類簇?cái)?shù)這一評價(jià)指標(biāo)，DNSCAN 算法在Ecoli、Seed、Waform3、Vowel 和Wpbc 數(shù)據(jù)集上無法聚類正確的類簇個(gè)數(shù)，而DPC 算法無法在Bupa、Ecoli、Vowel、Leuk72_3k 和Breast 數(shù)據(jù)集上聚類正確的類簇個(gè)數(shù)，KNNDPC 算法在Wine、Ecoli、Vowel 和Leuk72_3k 數(shù)據(jù)集上無法聚類正確的類簇個(gè)數(shù)。因此在聚類正確類簇個(gè)數(shù)這個(gè)評價(jià)指標(biāo)上，AKDP 算法也是最優(yōu)秀的。

綜合這三方面，顯然AKDP 算法是最優(yōu)秀的。

5 結(jié)束語

本文提出了一種新的自適應(yīng)聚合策略優(yōu)化的密度峰值聚類算法AKDP。首先該算法通過最近K近鄰的概念，用一個(gè)新的公式來定義數(shù)據(jù)點(diǎn)的局部密度，然后根據(jù)閾值判斷初始聚類中心，最后通過類簇間密度可達(dá)概念來把相似的類簇合并產(chǎn)生最后的聚類結(jié)果。通過實(shí)驗(yàn)，AKDP 算法在對人工數(shù)據(jù)集、UCI 數(shù)據(jù)集和復(fù)雜流形數(shù)據(jù)集的處理上具有相當(dāng)大的優(yōu)越性，比DPC、DBSCAN、KNNDPC 和K-means算法更準(zhǔn)確有效，且受人為影響更少。

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