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

高潤峰，蘇一丹，覃 華

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

0 引 言

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

點i為數據集X中的任意一點，其決策值為

γi=ρi*δi

(6)

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

2 罰處思想與迭代閾值法

2.1 罰處思想

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

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

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

(7)

式中：α為罰處系數，該系數的作用是對懲處點中距離該點較遠的z個點貢獻的SNN局部密度進行罰處。在傳統SNN局部密度中，對SNN局部密度都采用一個度量標準，所以在高密度簇中，每一點的傳統SNN局部密度都較高；而在低密度簇中，每一點的傳統SNN局部密度都較低，導致會遺漏在密度較小簇中的聚類中心。我們引用罰處系數α后，新的SNN局部密度削弱了高密度簇中的非聚類中心的SNN局部密度值，使得低密度簇中的聚類中心顯現出來，從而減少低密度簇中心點被忽視的機率，使得聚類結果更加準確。

距離遠近的判斷標準：對于數據集X中任意一點i，計算其距離最遠的第k個鄰居的歐氏距離Ei，若距離小于等于1/2Ei則認為其距離較近，否則認為其距離較遠。

2.2 迭代閾值法

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

輸入：數據集W={μ1,μ2,μ3,…,μn}

輸出：閾值T，數據集M和數據集I

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

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

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

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

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

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

3.1 算法描述與分析

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

所提算法描述如下：

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

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

步驟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)重復步驟7(2)和步驟7(3)直到隊列Q為空為止。

步驟8分配可能從屬點：

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

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

(3)填充矩陣M；

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

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

上述算法的一些關鍵細節說明如下：

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

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

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

3.2 算法時間復雜度分析

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

4 仿真實驗

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

4.1 實驗數據集說明

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

表1 實驗用的人工數據集

表2 實驗用的UCI數據集

表3 實驗用的圖像數據集

4.2 人工數據集上的實驗結果及分析

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

圖1 兩種算法在Jain數據集上決策圖的對比

圖2 兩種算法在Jain數據集上聚類效果的對比

圖3 兩種算法在Aggregation數據集上聚類效果的對比

圖4 兩種算法在Spiral數據集上聚類效果的對比

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

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

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

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

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

從這5個在模擬數據集中的聚類結果我們可以發現，PSNN-DPC算法不僅僅可以自動地準確地確定聚類中心，增加算法的自動化，而且由于引進了罰處思想，使得低密度簇中的密度中心得以顯露，由此聚類效果更加準確，解決了傳統SNN-DPC算法中的問題。

4.3 UCI數據集上的實驗結果及分析

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

圖5 兩種算法在DIM512數據集上聚類效果的對比

圖6 兩種算法在Flame數據集上聚類效果的對比

表4 各算法聚類結果AMI指標的對比

表5 各算法聚類結果ARI指標的對比

通過表4和表5的結果分別進行分析：

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

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

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

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

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

在Libras數據集中，本文AMI指標較原始SNN-DPC算法有所提高，也領先于其它算法。

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

4.4 圖像數據集上的實驗結果及分析

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

表6 SNN-DPC與PSNN-DPC在圖像數據集中的對比

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

5 結束語

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