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

高潤(rùn)峰，蘇一丹，覃 華

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

0 引 言

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

γi=ρi*δi

(6)

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

2 罰處思想與迭代閾值法

2.1 罰處思想

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

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

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

(7)

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

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

2.2 迭代閾值法

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

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

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

步驟1計(jì)算數(shù)據(jù)集W中n個(gè)數(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，對(duì)數(shù)據(jù)集M和數(shù)據(jù)集I進(jìn)行求平均值分別為m1，m2并計(jì)算出新的閾值T=(m1+m2)/2，通過(guò)新的閾值T計(jì)算出新的數(shù)據(jù)集M和數(shù)據(jù)集I；

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

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

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

3.1 算法描述與分析

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

所提算法描述如下：

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

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

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

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

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

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

步驟7分配確定從屬點(diǎn)：

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

(2)取出隊(duì)列Q中的一點(diǎn)r；

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

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

步驟8分配可能從屬點(diǎn)：

(1)尋找未分配的點(diǎn)并重新編號(hào)；

(2)形成分配矩陣M，其行對(duì)應(yīng)于未分配的點(diǎn)的編號(hào)，列對(duì)應(yīng)于簇；

(3)填充矩陣M；

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集說(shuō)明

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

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

表2 實(shí)驗(yàn)用的UCI數(shù)據(jù)集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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