高潤峰，蘇一丹，覃 華

(廣西大學(xué) 計算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

密度峰聚類算法(density peak clustering，DPC)，具有對初始點不敏感、能對各種形狀進(jìn)行聚類等優(yōu)點[1]。但該算法也存在一些不足，例如：需要手動選擇聚類中心點，主觀性較大，自動化程度差；當(dāng)簇的密度差異較大的時候，密度較小簇的中心點不容易被發(fā)現(xiàn)導(dǎo)致聚類結(jié)果不準(zhǔn)確。針對這些問題，國內(nèi)外學(xué)者進(jìn)行了研究。Xie等用K近鄰計算樣本點的密度，并采用模糊加權(quán)K近鄰來分配樣本[2]；Liu等提出用高斯核確定閾值來自動選擇聚類中心[3]；Liu Rui等通過共享最近鄰和兩次分配策略優(yōu)化非簇中心點的分配[4]；王洋等利用基尼系數(shù)自動識別聚類中心[5]；Sun等提出一種基于數(shù)據(jù)分布和線性判斷的自動選擇簇中心方法[6]；賈露等采用物理學(xué)中的萬有引力來優(yōu)化密度峰聚類[7]；Zhao等將數(shù)據(jù)空間劃分為圓形網(wǎng)格，通過網(wǎng)格相似度來實現(xiàn)密度峰聚類[8]；Cheng等用密度核來避免噪聲[9]。

上述改進(jìn)的DPC算法中，共享最近鄰密度峰算法(shared nearest neighbor density peak clustering，SNN-DPC)的聚類效果較好[4]，但仍存在不能自動化選簇中心和容易忽略密度較小的簇等問題，針對這些問題，提出一種罰處共享最近鄰密度峰聚類算法(penalty shared nearest neighbor density peak clustering，PSNN-DPC)，主要思路是：首先找出罰處點，使用共享最近鄰和罰處系數(shù)計算樣本點的密度，然后再根據(jù)改進(jìn)的樣本密度確定與更高密度點的距離計算γ，根據(jù)迭代閾值方法γ進(jìn)行迭代以選出聚類中心，接著采用二次分配策略將簇的非中心點分配到對應(yīng)的簇中。通過在各種數(shù)據(jù)集上的實驗，驗證所提算法是可行的。

1 共享最近鄰密度峰聚類算法

共享最近鄰的定義為：對數(shù)據(jù)集X中的任意一點i和j，點i的K近鄰集合為Г(i)，點j的K近鄰集合為Г(j)，那么點i和點j的共享最近鄰定義為

SNN (i,j) = Γ (i)∩Γ (j)

(1)

SNN相似度(SIM)定義為：對數(shù)據(jù)集X中的任意一點i和j，有

(2)

式中：dip與djp分別是點i和j到它們的共享最近鄰集合中一點p的歐氏距離。

SNN局部密度是通過將與點i附近k個相似度最大的點L(i)={x1,x2,x3,…,xk}的SNN相似度(SIM)進(jìn)行相加，即

(3)

點i為數(shù)據(jù)集X中的任意一點，其與密度更大最近點j的距離，定義為點i距最近更大密度點的距離(相對距離)即

(4)

特殊的，如果該點是局部密度最大點，點i距最近更大密度點的距離(相對距離)定義為

(5)

點i為數(shù)據(jù)集X中的任意一點，其決策值為

γi=ρi*δi

(6)

本文采用了罰處思想來改進(jìn)算法，后文給出密度ρ的新定義。

2 罰處思想與迭代閾值法

2.1 罰處思想

由于SNN-DPC算法的特點：一般來說，SNN局部密度都較大，使得密度在決策值中所占權(quán)重較大，會忽略低密度簇的中心點，該算法給出的解決方案是針對特殊數(shù)據(jù)集采用非常規(guī)方法選點，即選擇δ較大的點而忽略常規(guī)方法中選擇γ較大點，但此方法不具備普適性，也無法實現(xiàn)自動化，對此本文提出了一種罰處思想來罰處高密度簇中的非密度中心，改進(jìn)密度分布不均時的聚類效果，罰處思想主要有兩點：第一點是對罰處區(qū)域的定義，第二點是對罰處點的定義。

罰處區(qū)域：當(dāng)某一區(qū)域點都具有較大的SNN局部密度ρold，如果該數(shù)據(jù)集中有其它低密度簇的中心點存在，那么傳統(tǒng)的密度峰聚類算法會忽略低密度簇的中心點的存在，從而造成忽略低密度簇。為降低低密度區(qū)域中，中心點被其附近其它簇高密度點影響，需要對這些高密度中的點的密度進(jìn)行罰處，這些高密度點所處的區(qū)域我們稱為罰處區(qū)域。

罰處點(penalty point，PP)：當(dāng)發(fā)現(xiàn)其附近k個點的SNN傳統(tǒng)局部密度ρold都較高，可以認(rèn)為其在罰處區(qū)域，把在罰處區(qū)域的點稱為罰處點(penalty point，PP)。將罰處點的k個相似度最大的點分為兩類，一類是離該點較近的n個Pi={x1,x2,x3,…,xn}，另一類是離該點較遠(yuǎn)的z個Qi={x1,x2,x3,…,xz}。根據(jù)聚類中心的特點：聚類中心附近的點較密集，所以對該點較近的點貢獻(xiàn)的SNN局部密度值不作罰處，但對該點較遠(yuǎn)的點貢獻(xiàn)的SNN局部密度值作罰處，這樣對高密度簇中真正的聚類中心影響不大，且可以有效地降低高密度簇中非聚類中心的密度值。由此，我們將SNN新的局部密度定義為

(7)

式中：α為罰處系數(shù)，該系數(shù)的作用是對懲處點中距離該點較遠(yuǎn)的z個點貢獻(xiàn)的SNN局部密度進(jìn)行罰處。在傳統(tǒng)SNN局部密度中，對SNN局部密度都采用一個度量標(biāo)準(zhǔn)，所以在高密度簇中，每一點的傳統(tǒng)SNN局部密度都較高；而在低密度簇中，每一點的傳統(tǒng)SNN局部密度都較低，導(dǎo)致會遺漏在密度較小簇中的聚類中心。我們引用罰處系數(shù)α后，新的SNN局部密度削弱了高密度簇中的非聚類中心的SNN局部密度值，使得低密度簇中的聚類中心顯現(xiàn)出來，從而減少低密度簇中心點被忽視的機(jī)率，使得聚類結(jié)果更加準(zhǔn)確。

距離遠(yuǎn)近的判斷標(biāo)準(zhǔn)：對于數(shù)據(jù)集X中任意一點i，計算其距離最遠(yuǎn)的第k個鄰居的歐氏距離Ei，若距離小于等于1/2Ei則認(rèn)為其距離較近，否則認(rèn)為其距離較遠(yuǎn)。

2.2 迭代閾值法

迭代閾值法[10]是圖像分割中廣泛使用的方法，由于圖像前景和背景值的差別較大，使用迭代閾值法可以將前景和背景區(qū)分開來，利用這一特點，我們將該方法移植到數(shù)據(jù)集分割上，把一個數(shù)據(jù)集分割成兩個互相之間差別很大的數(shù)據(jù)集。由于密度峰算法聚類中心的γ的值都遠(yuǎn)遠(yuǎn)大于非中心的γ值，非常符合迭代閾值法適用的條件，所以迭代閾值法很適合用于選擇密度峰聚類中心。本文用迭代閾值法選出簇中心的子算法如下：

輸入：數(shù)據(jù)集W={μ1,μ2,μ3,…,μn}

輸出：閾值T，數(shù)據(jù)集M和數(shù)據(jù)集I

步驟1計算數(shù)據(jù)集W中n個數(shù)據(jù)的平均值，記為m0，且T=m0；

步驟2將數(shù)據(jù)集W分為大于等于T和小于等于T兩組數(shù)據(jù)集，分別為M={σ1,σ2,σ3…,σn1}和I={θ1,θ2,θ3…,θn2}；

步驟3令T0=T，對數(shù)據(jù)集M和數(shù)據(jù)集I進(jìn)行求平均值分別為m1，m2并計算出新的閾值T=(m1+m2)/2，通過新的閾值T計算出新的數(shù)據(jù)集M和數(shù)據(jù)集I；

步驟4重復(fù)步驟2到步驟3，直到閾值T=T0為止。

傳統(tǒng)密度峰聚類算法由于不能自動根據(jù)γ的區(qū)分簇中心和非簇中心，而采用手動選擇聚類中心的方法，造成算法自動性差，主觀性強(qiáng)，在某些數(shù)據(jù)集上也很難進(jìn)行選點。本文提出使用迭代閾值法將聚類中心點自動選擇出來，實現(xiàn)密度峰的自動聚類，提高了算法的自動化程度。

3 罰處共享最近鄰密度峰聚類算法

3.1 算法描述與分析

本文所提算法的基本過程為：首先判斷出罰處點，通過使用公式計算γ，對γ進(jìn)行排序，并且通過迭代閾值找出簇中心，最后通過兩次分配策略[4]分配樣本點。

所提算法描述如下：

輸入：數(shù)據(jù)集Xi={x1,x2,x3,…,xn}，K近鄰個數(shù)k，罰處系數(shù)α

輸出：聚類結(jié)果ψ={C1,C2,C3，…,Cm}(m為聚簇個數(shù))

步驟1計算樣本間的歐式距離形成距離矩陣Dn*n={dij}n*n；

步驟4使用式(4)和式(5)計算δi；

步驟5使用式(6)計算決策值γi；

步驟6使用迭代閾值法，選出聚類中心。

步驟7分配確定從屬點：

(1)初始化隊列Q，將所有聚類中心點ψ={C1,C2,C3，…,Cm}加入隊列Q；

(2)取出隊列Q中的一點r；

(3)分配點r的鄰居中的確定從屬點，并將其加入隊列Q；

(4)重復(fù)步驟7(2)和步驟7(3)直到隊列Q為空為止。

步驟8分配可能從屬點：

(1)尋找未分配的點并重新編號；

(2)形成分配矩陣M，其行對應(yīng)于未分配的點的編號，列對應(yīng)于簇；

(3)填充矩陣M；

(4)根據(jù)矩陣M對可能從屬點進(jìn)行分配；

(5)判斷是否還有未分配的點，如果還有則令鄰居數(shù)量k=k+1，重復(fù)步驟8(3)到步驟8(5)。

上述算法的一些關(guān)鍵細(xì)節(jié)說明如下：

(1)步驟7(3)中，可能從屬點的定義和分配規(guī)則：如果r和r的鄰居e的SNN的值大于k/2，即|SNN(r,e)|≥k/2，則定義e為確定從屬點，如果e是確定從屬點，則將其分配到r所在的簇中。

(2)步驟8(3)中，矩陣M的填充規(guī)則：對于所有未分配的點p，找到它所有鄰居點q，判斷q屬于哪一簇，并在M中對p編號的行q所屬簇的列數(shù)上+1，直到處理完p所有的鄰居。重復(fù)填充，直到所有未分配的點全部處理完。

(3)步驟8(4)中，根據(jù)矩陣M對可能從屬點分配規(guī)則：尋找矩陣M中的最大值，如果最大值大于0，則記錄其出現(xiàn)的行和列，將行所對應(yīng)的點分配到列所對應(yīng)的簇上，直到M中的最大值等于0為止。

3.2 算法時間復(fù)雜度分析

計算SNN相似度(SIM)與傳統(tǒng)SNN-DPC算法的時間復(fù)雜度相同為O(kn2)，計算δ和ρold為O(kn2)；計算ρ時的復(fù)雜度小于O(kn)；γ需要進(jìn)行排序，對其排序的時間復(fù)雜度為O(nlogn)；進(jìn)行迭代閾值時的復(fù)雜度為O(n2)；兩次分配策略需要O((k+m)n2)的時間復(fù)雜度，因此所提算法的時間復(fù)雜度為O((2k+m+1)n2)，與傳統(tǒng)SNN-DPC算法同處一個數(shù)量級。

4 仿真實驗

仿真實驗的計算機(jī)硬件環(huán)境為Intel Pentium Gold G5400 (3.7 GHz) CPU，內(nèi)存8 GB。在Windows10 x64平臺下使用MATLAB R2019a實現(xiàn)所提算法。

4.1 實驗數(shù)據(jù)集說明

本實驗使用了5個人工數(shù)據(jù)集、6個UCI真實數(shù)據(jù)集、2個圖像數(shù)據(jù)集，數(shù)據(jù)集的詳細(xì)情況見表1到表3。

表1 實驗用的人工數(shù)據(jù)集

表2 實驗用的UCI數(shù)據(jù)集

表3 實驗用的圖像數(shù)據(jù)集

4.2 人工數(shù)據(jù)集上的實驗結(jié)果及分析

本文算法與原始SNN-DPC算法[4]在人工數(shù)據(jù)集上的比較如圖1到圖6所示，圓圈代表決策圖中正確的聚類中心；結(jié)果圖中聚類中心使用星星標(biāo)出，經(jīng)過聚類被分為同一簇的擁有相同的圖案。

圖1 兩種算法在Jain數(shù)據(jù)集上決策圖的對比

圖2 兩種算法在Jain數(shù)據(jù)集上聚類效果的對比

圖3 兩種算法在Aggregation數(shù)據(jù)集上聚類效果的對比

圖4 兩種算法在Spiral數(shù)據(jù)集上聚類效果的對比

圖1為SNN-DPC和PSNN-DPC的決策圖對比，從圖1可看出：由于SNN-DPC沒有對高密度中心點進(jìn)行罰處，導(dǎo)致其決策圖右上角的兩個點并不全是真正的聚類中心，SNN-DPC將其錯選為聚類中心；而PSNN-DPC引入了罰處策略，決策圖中右上兩點即為正確的聚類中心，從而能選出正確的聚類中心。圖2顯示，SNN-DPC把兩個聚類中心點都選擇在密度較大的簇上，忽略了密度較小簇的聚類中心，出現(xiàn)了錯選聚類中心點的問題，導(dǎo)致聚類出錯；而PSNN-DPC引入了罰處和迭代閾值法后，可以正確自動選擇聚類中心，沒有忽略密度較小的簇中的聚類中心，可以正確的將其分為兩簇。對此問題，SNN-DPC[4]采取的辦法是用非常規(guī)方法選點，選相對距離較高的點，而不選其算法中γ較高的點，這種方法不具備普適性，且主觀性大，不能實現(xiàn)自動化選中心點。

根據(jù)圖1和圖2，PSNN-DPC中的罰處策略可以有效地將低密度簇中的聚類中心顯露出來，進(jìn)而對密度分布不均的數(shù)據(jù)具有良好的聚類效果。

圖3的聚類結(jié)果對比顯示，在每個簇不同形狀差異的數(shù)據(jù)集Aggregation中，PSNN-DPC和SNN-DPC都能正確識別聚類中心，但PSNN-DPC較原始算法有所提升，體現(xiàn)簇的邊界方面。SNN-DPC會在將部分邊界區(qū)域較多的錯分，而改進(jìn)的PSNN-DPC算法錯分的數(shù)量較小。反映在指標(biāo)上的是，原SNN-DPC算法的AMI為0.9500而PSNN-DPC的AMI為0.9687，提升了大約2%；雖然幅度不大但是PSNN-DPC是自動選擇聚類中心的；而原始算法是需要手動選擇聚類中心的。圖4的聚類結(jié)果對比顯示，在Spiral數(shù)據(jù)集中，PSNN-DPC和SNN-DPC都能準(zhǔn)確地識別簇，驗證了本文算法在環(huán)形數(shù)據(jù)中具有良好的聚類效果。

圖5的聚類結(jié)果對比顯示，由于DIM512數(shù)據(jù)集具有較高的維數(shù)和較多的簇中心，給自動識別簇中心帶來了一定難度，但PSNN-DPC依然表現(xiàn)了良好的效果，正確識別了聚類中心且發(fā)現(xiàn)16簇，聚類結(jié)果完全正確。這說明本文算法不僅能處理簇數(shù)量小維數(shù)低的數(shù)據(jù)，在簇數(shù)量多、維數(shù)高的情況下，依然能準(zhǔn)確地自動地識別聚類中心和簇數(shù)，具有良好的普適性。

圖6的聚類結(jié)果對比顯示，在Flame數(shù)據(jù)集中，PSNN-DPC較SNN-DPC有較大的優(yōu)勢，雖然兩者都正確的聚類中心和兩簇，但PSNN-DPC的AMI達(dá)到了0.9615，較SNN-DPC的0.8975提升了近7%，能夠準(zhǔn)確地將該數(shù)據(jù)集分為兩類。這說明本文引入罰處思想和迭代閾值后，邊界點歸屬的劃分準(zhǔn)確性提高，所提的改進(jìn)思路是有效的。

從這5個在模擬數(shù)據(jù)集中的聚類結(jié)果我們可以發(fā)現(xiàn)，PSNN-DPC算法不僅僅可以自動地準(zhǔn)確地確定聚類中心，增加算法的自動化，而且由于引進(jìn)了罰處思想，使得低密度簇中的密度中心得以顯露，由此聚類效果更加準(zhǔn)確，解決了傳統(tǒng)SNN-DPC算法中的問題。

4.3 UCI數(shù)據(jù)集上的實驗結(jié)果及分析

本文將對PSNN-DPC和其原始算法(SNN-DPC)、經(jīng)典密度算法DBSCAN以及DPC算法和其近年來改進(jìn)的其它DPC改進(jìn)算法，如WDPC[7]、DPC-CP-GS[8]進(jìn)行對比，結(jié)果采用AMI[11]、ARI[12]進(jìn)行量化對比，其取值范圍皆為[-1,1]，值越大代表聚類結(jié)果與真實情況越吻合，AMI和ARI的特點是可以衡量極端情況下的聚類效果，如果一個方法聚類效果相比隨機(jī)分配都不如，其值可以為負(fù)數(shù)；這相比傳統(tǒng)的ACC等指標(biāo)更能準(zhǔn)確反映聚類效果。實驗結(jié)果見表4和表5。表中的符號“-”表示文獻(xiàn)未給出該指標(biāo)的結(jié)果。

圖5 兩種算法在DIM512數(shù)據(jù)集上聚類效果的對比

圖6 兩種算法在Flame數(shù)據(jù)集上聚類效果的對比

表4 各算法聚類結(jié)果AMI指標(biāo)的對比

表5 各算法聚類結(jié)果ARI指標(biāo)的對比

通過表4和表5的結(jié)果分別進(jìn)行分析：

在最常用的Iris數(shù)據(jù)集中，本文算法較SNN-DPC算法持平，均為實驗中算法里最好的，對比其它算法，PSNN-DPC在該數(shù)據(jù)集中其聚類效果最高有60.3%的提升，平均也有10%的提升。

在噪聲比較多樣本數(shù)量大且維數(shù)較大的Waveform數(shù)據(jù)集中，由于本文所提算法具有罰處的特性，使得在該數(shù)據(jù)集中較SNN-DPC算法提升了4%，對比其它算法有更大的優(yōu)勢，是所有實驗算法中效果最好的，驗證了PSNN-DPC算法不僅僅能自動找出聚類中心，還能擁有良好的聚類效果。

在大腸桿菌Ecoli數(shù)據(jù)集中，其與原始SNN-DPC算法并列第一，均具有良好的聚類效果，相比其它聚類算法具有至少2%的提升。

在種子Seeds數(shù)據(jù)集中，本文算法與其它兩種算法相比略差，但是差距不是很大，也說明本文算法依然還是需要改進(jìn)。

在具有13個特征的Wine數(shù)據(jù)集中，本文算法表現(xiàn)出了良好的聚類，較SNN-DPC算法有所提升，較DPC算法具有60.5%的提升，平均也有13.7%的提升，驗證罰處思想在聚類中具有一定的優(yōu)勢。

在Libras數(shù)據(jù)集中，本文AMI指標(biāo)較原始SNN-DPC算法有所提高，也領(lǐng)先于其它算法。

綜上所述，本文所提算法的聚類效果在大多數(shù)UCI真實數(shù)據(jù)集上優(yōu)于其它算法，這說明引入迭代閾值法和罰處思想，不僅可以準(zhǔn)確無誤地自動找出簇中心，還可以有效地減少低密度中心點被忽略的機(jī)率，提高簇中心點選擇的準(zhǔn)確度和樣本點分配的準(zhǔn)確率。

4.4 圖像數(shù)據(jù)集上的實驗結(jié)果及分析

聚類分析的一個重要方面是進(jìn)行圖像聚類，本文使用了一個物體數(shù)據(jù)集Coil-20和人臉數(shù)據(jù)集Olivetti face進(jìn)行實驗。因圖像的維數(shù)較高，所以聚類前需要用降維方法來預(yù)處理數(shù)據(jù)。我們采用PCA法對圖像進(jìn)行降維，并且只過濾累計90%的主成分[13]，這樣可以有效地降低維數(shù)并且可以降低噪音。我們將實驗結(jié)果與手動的SNN-DPC作對比，結(jié)果見表6。

表6 SNN-DPC與PSNN-DPC在圖像數(shù)據(jù)集中的對比

Coil-20是一個物品圖片集合，其包含對20個物體從不同角度的拍攝，每隔5度拍攝一副圖像，每個物體72張圖像[14]。從表6可知，PSNN-DPC算法在該數(shù)據(jù)集中聚類結(jié)果的各項指標(biāo)都優(yōu)于SNN-DPC，其中ARI指標(biāo)領(lǐng)先幅度較大，提升了約13%。Olivetti face數(shù)據(jù)集包含1992年4月至1994年4月之間在AT&T劍橋?qū)嶒炇遗臄z的一組面部圖像，數(shù)據(jù)集共有40個人，每個人具有10張不同的照片，由表6的結(jié)果可知，PSNN-DPC算法較SNN-DPC也有略微優(yōu)勢。根據(jù)這兩組物品和人臉數(shù)據(jù)集的結(jié)果，PSNN-DPC在圖像數(shù)據(jù)集中聚類是有效的，所提算法對圖像數(shù)據(jù)聚類有良好的效果。

5 結(jié)束語

針對大多數(shù)密度算法容易忽略低密度簇和不能自動選擇聚類中心的問題，本文在SNN-DPC算法的基礎(chǔ)上提出一種罰處共享最近鄰密度峰聚類算法，利用罰處思想使高密度簇非聚類中心的局部密度變小，令低密度簇中的聚類中心得以顯現(xiàn)；迭代閾值思想可以通過閾值將數(shù)據(jù)分為普通點和簇中心點。人工數(shù)據(jù)集和UCI真實數(shù)據(jù)集以及圖像數(shù)據(jù)集上實驗結(jié)果表明所提算法是可行的、有效的。