結(jié)合共享近鄰和共享逆近鄰的密度峰聚類

周歡歡，張 征，張 琦

(西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009)

聚類分析是數(shù)據(jù)挖掘的重要研究領(lǐng)域之一，是一種無需先驗(yàn)信息的無監(jiān)督學(xué)習(xí)方法[1]。聚類分析的主要目的是：根據(jù)某種相似度度量關(guān)系分析未標(biāo)記數(shù)據(jù)點(diǎn)之間的聯(lián)系，從而揭示數(shù)據(jù)內(nèi)在的屬性[2-4]，將彼此相似的樣本點(diǎn)歸為同一個(gè)簇，同時(shí)使不同類簇的樣本點(diǎn)相似度盡可能小。學(xué)者基于不同理論提出了許多不同的聚類算法，這些聚類方法可分為基于劃分、網(wǎng)格、模型、層次和密度的聚類算法[5]。

Rodriguez和Laio于2014年提出的密度峰聚類算法[6](Clustering by fast search and find of Density Peaks，DPC)能處理具有任意形狀的數(shù)據(jù)集。由于該算法具有原理簡單、無需迭代并且通過決策圖能準(zhǔn)確找到聚類中心等優(yōu)點(diǎn)，自被提出以來便引起了廣泛關(guān)注，在短時(shí)間內(nèi)就被應(yīng)用到計(jì)算機(jī)視覺[7]、醫(yī)學(xué)[8]、圖像識別[9]、生物學(xué)[10]等各個(gè)領(lǐng)域。但是DPC算法也存在缺陷：(1)基于歐氏距離和截?cái)嗑嚯x定義樣本的相似度和局部密度，導(dǎo)致對高維數(shù)據(jù)集和分布不均數(shù)據(jù)集的聚類結(jié)果不理想；(2)分配策略容錯(cuò)能力差，樣本點(diǎn)分配錯(cuò)誤會(huì)引起鏈?zhǔn)椒磻?yīng)進(jìn)而導(dǎo)致一連串的樣本點(diǎn)分配錯(cuò)誤；(3)全局參數(shù)截?cái)嗑嚯xdc難以確定。

針對DPC算法存在的不足，學(xué)者提出了一些相應(yīng)的改進(jìn)算法。Du等[11]提出了基于k近鄰的KNN-DPC算法，該算法引入了k近鄰的概念和主成分分析法，提供了一種新的計(jì)算局部密度的方法，能反映數(shù)據(jù)的局部結(jié)構(gòu)；Guo等[12]提出了基于逆近鄰的NDPC算法，將DPC算法的局部密度重新定義為每個(gè)樣本點(diǎn)的逆近鄰數(shù)，能較好地處理密度不均衡數(shù)據(jù)；鮑舒婷等[13]提出了基于共享近鄰相似度的DPCSNNS算法，克服了DPC算法對截?cái)嗑嚯x敏感的問題；Xie等[14]提出了FKNN-DPC算法，該算法引入了k近鄰的新局部密度和基于模糊準(zhǔn)則的分配策略；Liu等[15]提出了基于共享近鄰的SNN-DPC算法，依據(jù)共享近鄰的思想重新定義了相似度、局部密度和距離度量，并提出了兩步分配非聚類中心的方法，該算法不僅能處理高維復(fù)雜數(shù)據(jù)集，還能避免樣本點(diǎn)被錯(cuò)誤分配時(shí)產(chǎn)生的鏈?zhǔn)椒磻?yīng)。

目前，大部分DPC改進(jìn)算法通過k近鄰、逆近鄰或共享近鄰來構(gòu)造樣本之間的相似度，忽略了兩個(gè)點(diǎn)之間的相似度與這兩個(gè)點(diǎn)的共享近鄰和共享逆近鄰都有關(guān)。鑒于此，為了更好地解決DPC算法的不足，本文提出了結(jié)合共享近鄰和共享逆近鄰的密度峰聚類算法，同時(shí)考慮到了樣本點(diǎn)之間的共享近鄰和共享逆近鄰。該算法利用共享近鄰和共享逆近鄰構(gòu)造新的相似度，并通過該相似度提出了一種新的局部密度度量方法。同時(shí)，提出了基于近鄰和逆近鄰的分配策略，以從眾的思想分配樣本點(diǎn)，避免樣本點(diǎn)被分配錯(cuò)誤時(shí)出現(xiàn)的鏈?zhǔn)椒磻?yīng)。

1 DPC算法

DPC算法的聚類中心主要具備兩個(gè)基本的設(shè)定：(1)聚類中心被密度較低的近鄰點(diǎn)包圍；(2)聚類中心之間的距離相對較遠(yuǎn)，即聚類中心與具有較高局部密度的點(diǎn)距離相對較大。根據(jù)假設(shè)可知，聚類中心擁有較大的局部密度和距其他聚類中心相對較遠(yuǎn)。要確定數(shù)據(jù)集的聚類中心，需要計(jì)算每個(gè)樣本點(diǎn)的局部密度ρ和距離δ。DPC算法采用兩種方法計(jì)算樣本點(diǎn)的局部密度：

當(dāng)數(shù)據(jù)規(guī)模比較大時(shí)，采用截?cái)嗪擞?jì)算局部密度ρi，計(jì)算公式為：

(1)

(2)

其中，N是樣本點(diǎn)的維數(shù)。

當(dāng)規(guī)模比較小時(shí)，采用指數(shù)核[16]計(jì)算局部密度ρi，計(jì)算公式如下：

(3)

式(1)和式(3)中的截?cái)嗑嚯x都需要人為設(shè)定，并且截?cái)嗑嚯x的微小變化會(huì)引起聚類結(jié)果的劇烈波動(dòng)。文獻(xiàn)[6]認(rèn)為截?cái)嗑嚯x的設(shè)定通常要滿足樣本平均近鄰的數(shù)量為數(shù)據(jù)集的1%～2%。

樣本點(diǎn)的距離計(jì)算公式如下：

(4)

DPC算法以每個(gè)樣本點(diǎn)的局部密度ρ和距離δ為依據(jù)，文獻(xiàn)[6]提出用下式來計(jì)算每個(gè)樣本點(diǎn)的決策值，進(jìn)而構(gòu)造決策圖。根據(jù)決策圖選取較大的決策值γi為聚類中心，即聚類中心擁有較大的ρi和δi值。

γi=ρiδi。

(5)

DPC算法根據(jù)決策圖選出聚類中心之后，將剩下的樣本點(diǎn)分配到距其最近且具有更大局部密度的點(diǎn)所屬的簇。

2 結(jié)合共享近鄰和共享逆近鄰的密度峰聚類

2.1 相關(guān)定義

定義1(k近鄰集)樣本點(diǎn)i與其他樣本點(diǎn)的歐式距離最近k個(gè)點(diǎn)的集合，稱為樣本點(diǎn)i的k近鄰集KNN(i)，數(shù)學(xué)表達(dá)如下：

KNN(i)={j∈X|dij≤diik}，

(6)

其中，dij表示樣本點(diǎn)i和j的歐式距離，ik是樣本點(diǎn)i到其他點(diǎn)歐式距離升序排序后位于第k個(gè)位置的樣本點(diǎn)，X是數(shù)據(jù)集。

定義2(逆近鄰集[17])如果樣本點(diǎn)i在其他樣本點(diǎn)的k近鄰集中，則稱這些樣本點(diǎn)為點(diǎn)i的逆近鄰集RNN(i)，數(shù)學(xué)表達(dá)如下：

RNN(i)={j∈X|i∈KNN(j)}。

(7)

定義3(共享k近鄰集[18])樣本點(diǎn)i和j的共享k近鄰集SNN(i,j)定義如下：

SNN(i,j)=KNN(i)∩KNN(j)。

(8)

定義4(共享逆近鄰集)樣本點(diǎn)i和j的共享逆近鄰集SRNN(i,j)定義如下：

SRNN(i,j)=RNN(i)∩RNN(j)。

(9)

定義5(距最近較大密度點(diǎn)的距離[15])樣本點(diǎn)i的局部距離δi值公式如下：

(10)

2.2 基于共享近鄰和共享逆近鄰改進(jìn)的局部密度

由于DPC算法以歐氏距離來度量樣本點(diǎn)之間的相似度，而歐氏距離只考慮樣本點(diǎn)之間的局部一致性，導(dǎo)致DPC算法處理樣本點(diǎn)分布不均和高維復(fù)雜數(shù)據(jù)集的聚類效果不理想。因此，本文借助共享近鄰和共享逆近鄰構(gòu)造了相似度，包含了兩個(gè)點(diǎn)之間的k近鄰和逆近鄰的信息，k近鄰能反映數(shù)據(jù)的局部特征，逆近鄰從全局的視角獲得樣本點(diǎn)的密度信息。

定義6(相似度)對于數(shù)據(jù)集X中樣本點(diǎn)i和j，它們之間基于共享近鄰和共享逆近鄰的相似度定義為：

(11)

其中，NN(i,j)=SNN(i,j)∪SRNN(i,j)；dip表示樣本點(diǎn)i和p的歐式距離；| |表示集合的元素?cái)?shù)量。

高月等[19]證明了逆近鄰能更好地反映樣本的密度信息，所以本文提出了以逆近鄰為主的局部密度，樣本點(diǎn)的局部密度是每個(gè)樣本點(diǎn)與其逆近點(diǎn)的相似度之和除以該點(diǎn)的逆近鄰集的元素?cái)?shù)量。

定義7(局部密度)?i∈X，樣本點(diǎn)i的逆近鄰集中的所有樣本點(diǎn)與該點(diǎn)的相似度之和除以該點(diǎn)逆近鄰的數(shù)量，則為點(diǎn)i的局部密度ρi。局部密度ρi公式如下：

(12)

2.3 分配策略

算法1：樣本點(diǎn)分配算法

Step1:初始化隊(duì)列Q，將所有的聚類中心點(diǎn)放入隊(duì)列Q中；

Step2:取隊(duì)列Q頭部點(diǎn)為xi，獲得xi的k個(gè)近鄰點(diǎn)，其集合為Ki；

Step2-1:取未分配的點(diǎn)x′，其中x′∈Ki；

Step2-3:重復(fù)Step2-1至Step2-2兩個(gè)步驟，直至集合Ki中k個(gè)近鄰點(diǎn)處理完成；

Step2-4:將k個(gè)近鄰點(diǎn)處理完后，從隊(duì)列Q中刪除頭部點(diǎn)；

Step3:跳轉(zhuǎn)Step2反復(fù)循環(huán)，直至隊(duì)列Q為空；

Step4:找到所有未分配的樣本點(diǎn)pi，設(shè)未分配的點(diǎn)有b個(gè)，那么i=1，2，…，b；

Step5:構(gòu)造分配矩陣A，初始值為0，其中分配矩陣行數(shù)等于b，列數(shù)等于簇?cái)?shù)m；

Step6:對每個(gè)未分配的樣本點(diǎn)pi，i=1,2,…,b，找到pi的所有k個(gè)近鄰點(diǎn)qij，j=1，2，…，k。如果點(diǎn)qij已經(jīng)被分配給某個(gè)簇c，1≤c≤m，則Aic=Aic+1；

Step7:求出分配矩陣A中所有行里的最大值max(max>0)，用最大值所在的簇來表示該行未分配點(diǎn)簇。

Step8:循環(huán)Step4—Step7，直至所有樣本點(diǎn)分配完。

2.4 完整算法

至此，給出結(jié)合共享近鄰和共享逆近鄰的密度峰聚類的完整算法如下：

算法2：結(jié)合共享近鄰和共享逆近鄰的密度峰聚類算法

Step1:輸入數(shù)據(jù)集X，簇?cái)?shù)m；

Step2:根據(jù)式(6)和(7)計(jì)算每個(gè)樣本點(diǎn)的k近鄰集和逆近鄰集；

Step3:根據(jù)式(11)計(jì)算每個(gè)樣本點(diǎn)與其他點(diǎn)的相似度Sim；

Step4:根據(jù)式(12)計(jì)算每個(gè)樣本點(diǎn)的局部密度ρi；

Step5:根據(jù)式(10)計(jì)算每個(gè)樣本點(diǎn)對應(yīng)的距離δi；

Step6:根據(jù)式(5)計(jì)算每個(gè)樣本點(diǎn)的決策值γi；

Step7:對Step6得到的決策值排降序，并且自動(dòng)選取排序后列表中前m個(gè)樣本點(diǎn)作為聚類中心；

Step8:通過樣本點(diǎn)分配算法將剩下的樣本點(diǎn)分配到相應(yīng)的簇中；

Step9:輸出聚類結(jié)果。

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證算法的性能，本文在人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集上進(jìn)行測試。采用AMI[20]、ARI[20]和FMI[21]為評價(jià)指標(biāo)，并與SNNDPC[15]、傳統(tǒng)DPC[6]、FKNN-DPC[14]、DBSCAN[22]、OPTICS[23]、AP[24]和K-Means[25]算法進(jìn)行比較。

在進(jìn)行實(shí)驗(yàn)之前，采用最大最小歸一化方法對數(shù)據(jù)集進(jìn)行預(yù)處理，以消除數(shù)據(jù)的缺失和維數(shù)差異對聚類結(jié)果的影響。最大最小歸一化方法如下式所示：

3.1 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

選取7個(gè)人工數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，數(shù)據(jù)集的詳細(xì)信息如表1所示，所選數(shù)據(jù)集具有不同的樣本個(gè)數(shù)和簇?cái)?shù)。圖2～圖8是人工數(shù)據(jù)集的原始聚類圖和本文算法獲得的聚類效果圖對比，其中具有不同顏色的點(diǎn)被分配給不同的簇，聚類中心以星號表示。Aggregation數(shù)據(jù)集包含7個(gè)形狀規(guī)模不同的多密度團(tuán)狀簇；Flame、S2和D31數(shù)據(jù)集具有簇與簇之間距離較近的特點(diǎn)；R15數(shù)據(jù)集包含15個(gè)形狀不一的簇；Spiral是螺旋形數(shù)據(jù)集；Pathbased數(shù)據(jù)集的特點(diǎn)是數(shù)據(jù)分布不均。從圖2～圖8可以看出，本文聚類算法借助共享近鄰和共享逆近鄰的概念，能準(zhǔn)確找到數(shù)據(jù)集每個(gè)簇的聚類中心；基于近鄰和逆近鄰的分配策略能正確分配簇邊緣區(qū)域樣本點(diǎn)。本文算法避免了DPC算法中截?cái)嗑嚯x難以選取的問題，克服了DPC算法人工選擇局部密度計(jì)算方法的缺陷，以及能處理分布不均的數(shù)據(jù)集。

表1 人工數(shù)據(jù)集

表2是本文算法與其他7種算法在7個(gè)人工數(shù)據(jù)集上的評價(jià)指標(biāo)結(jié)果，表中加粗的值表示最好的聚類結(jié)果。由實(shí)驗(yàn)結(jié)果知，除了Aggregation和Flame數(shù)據(jù)集，在其他數(shù)據(jù)集中本文算法的AMI、ARI和FMI值均優(yōu)于其他算法，尤其在Pathbased數(shù)據(jù)集上，本文算法得到的AMI、ARI和FMI值分別比DPC算法高41.44%、48.8%和30.67%。在Aggregation數(shù)據(jù)集上，比DPC算法的AMI、ARI和FMI值分別低0.44%、0.22%和0.17%；在Flame數(shù)據(jù)集上，比DPC算法的AMI、ARI和FMI值分別低7.33%、3.34%和1.55%。

表2 人工數(shù)據(jù)集聚類結(jié)果

3.2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

選取4個(gè)數(shù)據(jù)分布不一樣的UCI數(shù)據(jù)集進(jìn)行測試，數(shù)據(jù)集的詳細(xì)信息如表3所示。各算法在UCI數(shù)據(jù)集的聚類結(jié)果如表4所示。Wine數(shù)據(jù)集包含3個(gè)分布不均的簇，本文算法得到的AMI、ARI和FMI值分別比DPC算法高18.49%、24.25%和16.00%；Iris數(shù)據(jù)集包含3個(gè)規(guī)模一樣的簇，本文算法得到的AMI、ARI和FMI值分別比DPC算法高5.27%、3.65%和2.46%,與SNN-DPC算法聚類結(jié)果一樣；Seed數(shù)據(jù)集包含3個(gè)樣本點(diǎn)數(shù)量相同的簇，本文算法得到的AMI、ARI和FMI值分別比DPC算法高6.30%、6.56%和5.96%；Blance Scale數(shù)據(jù)集是平衡比例尺數(shù)數(shù)據(jù)集，本文算法得到的AMI、ARI和FMI值分別比DPC算法高32.98%、32.37%和20.55%。同時(shí)本文算法的AMI、ARI和FMI值均優(yōu)于其他算法。

表3 UCI數(shù)據(jù)集

表4 UCI數(shù)據(jù)集聚類結(jié)果

4 結(jié) 語

為了解決DPC算法的局部密度定義過于簡單、全局參數(shù)截?cái)嗑嚯x難以確定以及聚類分配策略容錯(cuò)能力差等問題，提出了一種結(jié)合共享近鄰和共享逆近鄰的密度峰聚類算法。該算法借助共享近鄰和共享逆近鄰定義了新的相似度與局部密度，能更準(zhǔn)確反應(yīng)數(shù)據(jù)的局部特征和內(nèi)在聯(lián)系，找到準(zhǔn)確的聚類中心，避免了參數(shù)截?cái)嗑嚯x的選擇。同時(shí)，提出了一種新的分配策略，能有效避免樣本點(diǎn)被錯(cuò)誤分配時(shí)導(dǎo)致進(jìn)一步的錯(cuò)誤。實(shí)驗(yàn)結(jié)果表明，與其他算法相比，本文算法可以處理更多類型的數(shù)據(jù)集，整體上具有理想的聚類效果。