張新元，贠衛(wèi)國(guó)

(西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055)

1 引 言

數(shù)據(jù)挖掘領(lǐng)域中，聚類分析[1]是非常重要的一個(gè)手段.它利用一定規(guī)則將數(shù)據(jù)劃分成不同簇，同一簇下的對(duì)象具有一定的相似性，而不同簇下的對(duì)象差異性較大[2].現(xiàn)如今聚類已經(jīng)在商業(yè)、計(jì)算機(jī)應(yīng)用、生物技術(shù)、圖像分割等領(lǐng)域被應(yīng)用.

經(jīng)典的聚類算法主要有k均值聚類算法(K-means)[3]，該算法簡(jiǎn)單有效，尤其在凸類數(shù)據(jù)上有非常不錯(cuò)的表現(xiàn)，F(xiàn)CM(Fuzzy C-means)[4]通過(guò)引入模糊性建立了樣本的隸屬不確定性，該算法在多種數(shù)據(jù)上仍有不錯(cuò)的表現(xiàn).另還有AP(Affinity Propagation)算法[5]，DBSCAN(Density-Based Algorithm For Discovering Clusters in Large Spatial Databases With Noise)算法[6]，均簡(jiǎn)單有效且被廣泛使用，但仍有較大改進(jìn)空間.

Alex等[7]提出一種快速搜索和尋找密度峰值的聚類算法，簡(jiǎn)稱DPC(Density Peaks Clustering).DPC能夠快速找到聚類中心點(diǎn)，對(duì)非聚類中心點(diǎn)按照密度與距離的思想完成分配，能夠取得不錯(cuò)的效果.但仍存在不足，主要體現(xiàn)在：1)局部密度定義僅考慮距離屬性且對(duì)于低維數(shù)據(jù)和高維數(shù)據(jù)采取的密度定義不同，算法的通用性不強(qiáng)；2)對(duì)非聚類中心點(diǎn)的一次分配策略易導(dǎo)致一步錯(cuò)、步步錯(cuò)的現(xiàn)象，降低算法的效果.近年來(lái)，多位學(xué)者都對(duì)DPC算法的不足提出了不同的解決方法.紀(jì)霞[8]等通過(guò)距離矩陣將樣本點(diǎn)映射到相對(duì)鄰域來(lái)獲取局部密度，對(duì)相對(duì)距離執(zhí)行剪枝策略，僅需考慮近鄰之間的距離，提出的RN-DPC(Relative Neighborhood And Pruning Strategy Optimized Density Peaks Clustering Algorithm)算法增強(qiáng)了聚類的效率.Du[9]等通過(guò)考慮樣本的K近鄰提出了能夠反映樣本點(diǎn)空間結(jié)構(gòu)特點(diǎn)的局部密度計(jì)算方法，所提出的DPC-KNN(Density Peaks Clustering Based On K-Nearest Neighbors)算法考慮到樣本點(diǎn)空間結(jié)構(gòu)，避免了簇丟失的問(wèn)題，Rui[10]等人通過(guò)共享近鄰個(gè)數(shù)，重新定義了局部密度以及相對(duì)距離的計(jì)算，并對(duì)分配策略采用共享近鄰數(shù)的二次分配方法，提出的SNN-DPC(Shared-nearest-neighbor-based clustering by fast search and find of density peaks)算法有效提升了聚類性能.趙嘉[11]等引入樣本的鄰域思想計(jì)算局部密度，并定義了鄰近度的度量規(guī)則，提出一種考慮近鄰度的分配策略.所提出的DPC-MND(Density Peaks Clustering Based on Mutual Neighbor Degree)算法綜合了數(shù)據(jù)全局與局部特征，聚類性能優(yōu)越.吳辰文[12]等提出IA-DPC(Density Peak Clustering Algorithm for Improved Node Aggregation)算法，采用節(jié)點(diǎn)凝聚度思想，引入加權(quán)完成圖和建立新的評(píng)價(jià)函數(shù)來(lái)選擇聚類中心，IA-DPC可有效選擇正確聚類中心.

本文提出一種共享K近鄰和多分配策略的密度峰值聚類算法(SKM-DPC).其主要思想是將共享近鄰距離引入數(shù)據(jù)點(diǎn)的相似性度量中，基于放大因子定義了局部密度計(jì)算方式，并對(duì)分配策略進(jìn)行優(yōu)化.在12個(gè)數(shù)據(jù)集上的測(cè)試驗(yàn)證了該算法能夠較好的捕捉聚類準(zhǔn)確性.本文的貢獻(xiàn)包括：

1)用既能描述數(shù)據(jù)間距離特性和空間特性的共享鄰域定義了數(shù)據(jù)間的相似性，解決了傳統(tǒng)歐式距離度量相似性的不足.

2)定義了基于放大因子的數(shù)據(jù)點(diǎn)局部密度計(jì)算方法，擴(kuò)大了聚類中心與非聚類中心在決策值圖中的差異性，減少不必要的錯(cuò)誤.

3)優(yōu)化SNN-DPC算法的分配策略，對(duì)可能從屬點(diǎn)的分配進(jìn)行了限制，降低分配錯(cuò)誤的風(fēng)險(xiǎn).

2 相關(guān)工作

2.1 基礎(chǔ)知識(shí)

定義1.(K近鄰集合)計(jì)算數(shù)據(jù)集X中數(shù)據(jù)點(diǎn)xi與其他數(shù)據(jù)點(diǎn)距離并按照升序排列，第K個(gè)距離為distki，記錄前K個(gè)距離的索引值，對(duì)應(yīng)的數(shù)據(jù)點(diǎn)即為數(shù)據(jù)點(diǎn)xi的K近鄰集合，數(shù)學(xué)定義如式(1)所示：

KNN(xi)={xj∈X|dij≤distki}

(1)

定義2.(共享近鄰集合)數(shù)據(jù)點(diǎn)xi的K近鄰集合為KNN(xi)，數(shù)據(jù)點(diǎn)xj的K近鄰集合為KNN(xj)，則樣本xi和xj的共享近鄰集合的數(shù)學(xué)定義如式(2)所示：

SNN(xi，xj)=KNN(xi)∩KNN(xj)

(2)

2.2 DPC算法

DPC算法是一種基于密度與距離的聚類算法，基于兩種假設(shè)：1)聚類中心周圍的密度低；2)聚類中心間距離遠(yuǎn).DPC通過(guò)局部密度ρi為橫坐標(biāo)，相對(duì)距離δi為縱坐標(biāo)來(lái)得到?jīng)Q策圖，并選取出聚類中心，最后基于ρi與δi對(duì)未分配點(diǎn)進(jìn)行歸類.

對(duì)于給定一個(gè)數(shù)據(jù)集Xi×j={x1；x2;x3;…;xi}，其中xi={xi1；xi2;xi3;…;xij}，共有i個(gè)數(shù)據(jù)點(diǎn)，j個(gè)數(shù)據(jù)點(diǎn)屬性.DPC算法在計(jì)算局部密度時(shí)采用2種度量方式：截?cái)嗪伺c高斯核.

截?cái)嗪说木植棵芏扔?jì)算見(jiàn)式(3)：

ρi=∑i≠jχ(dij-dc)

(3)

高斯核的局部密度計(jì)算見(jiàn)式(4)：

(4)

其中，若x<0，則χ(x)=1，反之x≥0，則χ(x)=0.其中，dij為數(shù)據(jù)點(diǎn)xi和xj的距離，dc為人為指定的截?cái)嗑嚯x.

當(dāng)數(shù)據(jù)點(diǎn)xi局部密度最大時(shí)，相對(duì)距離見(jiàn)式(5)：

δi=maxi≠j(dij)

(5)

其余數(shù)據(jù)點(diǎn)的相對(duì)距離見(jiàn)式(6)：

δj=minj:ρj>ρi(dij)

(6)

截?cái)嗪硕攘康木植棵芏戎敢越財(cái)嗑嚯x為半徑構(gòu)成的圓中包含數(shù)據(jù)點(diǎn)的個(gè)數(shù)，高斯核度量的局部密度指全部數(shù)據(jù)點(diǎn)到該數(shù)據(jù)點(diǎn)的距離之和.

這是由于DPC認(rèn)為密度最高的數(shù)據(jù)點(diǎn)之外的數(shù)據(jù)點(diǎn)不可能比其密度高，認(rèn)定密度最高的點(diǎn)為聚類中心點(diǎn).其余聚類中心點(diǎn)需滿足局部密度ρi較高且相對(duì)距離δi較大.

DPC通過(guò)局部密度ρi與相對(duì)距離δi畫出決策圖來(lái)選取聚類中心.找到聚類中心后，將剩余未分配數(shù)據(jù)點(diǎn)分配給密度比其大且距離最近的簇.

2.3 DPC算法不足分析

DPC與其他密度聚類算法均有不足，表現(xiàn)為兩方面：

1)局部密度的度量上未考慮數(shù)據(jù)點(diǎn)之間的空間特性，僅考慮數(shù)據(jù)點(diǎn)間距離特性，當(dāng)多個(gè)簇之間的密度存在較大差異時(shí)，DPC不能很好的將同一簇?cái)?shù)據(jù)點(diǎn)歸類.實(shí)際上，對(duì)于小規(guī)模數(shù)據(jù)集采用的是高斯核度量局部密度，對(duì)于大規(guī)模數(shù)據(jù)集采用截?cái)嗪硕攘烤植棵芏?對(duì)于同一個(gè)數(shù)據(jù)集而言，分別采用兩種度量方式的聚類結(jié)果是有較大差別的.

圖1和圖2展示的是DPC算法在Aggregation數(shù)據(jù)集上分別采用高斯核和截?cái)嗪说玫降木垲惤Y(jié)果，清楚的看到在dc取值相同，即dc=2時(shí)，分別采用高斯核與截?cái)嗪硕攘烤植棵芏葧r(shí)，聚類效果是存在較大差別的.

圖1 DPC算法采用高斯核在Aggregation上的聚類結(jié)果Fig.1 Gaussian kernel results of clustering using DPC on Aggregation

圖2 DPC算法采用截?cái)嗪嗽贏ggregation上的聚類結(jié)果Fig.2 Cutoff kernel results of clustering using DPC on Aggregation

2)分配策略采用一站式策略，易發(fā)生連帶錯(cuò)誤，導(dǎo)致聚類結(jié)果不理想.DPC對(duì)于非聚類中心點(diǎn)的分配上，采用尋找密度比其高且距離最近的原則，這非常容易導(dǎo)致一個(gè)點(diǎn)分配錯(cuò)誤，后續(xù)大多數(shù)點(diǎn)也分配錯(cuò)誤.在環(huán)形數(shù)據(jù)集的表現(xiàn)更為明顯.如圖3所示，A、B、C 3個(gè)數(shù)據(jù)點(diǎn)為聚類中心點(diǎn)且為3個(gè)密度峰值點(diǎn)，Z為已分配給C點(diǎn)所屬簇的數(shù)據(jù)點(diǎn)，在分配X點(diǎn)時(shí)，由于Z點(diǎn)和Y點(diǎn)都比X點(diǎn)的密度值大，X點(diǎn)到Z點(diǎn)的距離為b，X點(diǎn)到Y(jié)點(diǎn)的距離為a，由圖很明顯得出a>b，則X點(diǎn)按照DPC算法的分配策略會(huì)分配給Z所在簇，而實(shí)際上X點(diǎn)應(yīng)當(dāng)分配給A簇.由此引發(fā)X點(diǎn)至M點(diǎn)間的多個(gè)數(shù)據(jù)點(diǎn)錯(cuò)誤的被歸為C簇，這種原因不僅與DPC的分配策略有關(guān)，與其密度定義方法也有一定關(guān)系[13].

圖3 DPC算法在Spiral的聚類結(jié)果Fig.3 Results of clustering using DPC on Spiral

2.4 SNN-DPC算法

SNN-DPC算法采用共享近鄰的概念描述數(shù)據(jù)點(diǎn)的局部密度和相對(duì)距離，并定義了可能從屬點(diǎn)與不可避免從屬點(diǎn)，最后利用鄰域信息完成聚類.

對(duì)于數(shù)據(jù)點(diǎn)xi和xj，xi的K近鄰集合和xj的K近鄰集合為這兩個(gè)數(shù)據(jù)點(diǎn)的共享近鄰集合，表示為SNN(xi,xj).相似度的計(jì)算見(jiàn)式(7)：

(7)

xi的局部密度定義為與xi相似度最高的K個(gè)相似度之和，計(jì)算公式見(jiàn)式(8)：

ρi=∑xj∈L(xi)Sim(xi，xj)

(8)

其中，L(xi)表示xi中相似度比較大的K個(gè)數(shù)據(jù)點(diǎn)的集合.其中K的取值同選擇的近鄰數(shù)K的取值.

在相對(duì)距離δ的計(jì)算中，SNN-DPC引入了距離最近的較大密度點(diǎn)的歐氏距離，并利用鄰近距離增加了補(bǔ)償機(jī)制，基于此原理低密度所在簇的數(shù)據(jù)點(diǎn)也可能具有比較大的相對(duì)距離δ.

當(dāng)樣本點(diǎn)xi局部密度最大，相對(duì)距離見(jiàn)式(9)：

δi=maxi≠j(dij)

(9)

其余樣本點(diǎn)的相對(duì)距離見(jiàn)式(10)：

δi=minj:ρj>ρi[dij(∑p∈KNN(xi)dip+∑q∈KNN(xj)djp)]

(10)

通過(guò)構(gòu)建局部密度為橫軸，相對(duì)距離為距離的縱軸，便可獲得聚類中心.

在SNN-DPC算法中，除聚類中心外的點(diǎn)被分成兩部分，一部分被定義為不可避免的從屬點(diǎn)，另一部分被定義為可能的從屬點(diǎn).

對(duì)于數(shù)據(jù)點(diǎn)xi和xj，當(dāng)xi和xj的共享近鄰點(diǎn)的個(gè)數(shù)為近鄰數(shù)的一半時(shí)，SNN-DPC認(rèn)為xi和xj是歸屬于同一簇的.數(shù)學(xué)定義見(jiàn)式(11)：

|{p|p∈KNN(xi)∩p∈KNN(xj)}|≥K/2

(11)

剩余未分配的數(shù)據(jù)點(diǎn)屬于可能的從屬點(diǎn)，數(shù)學(xué)定義表達(dá)見(jiàn)式(12)：

|{p|p∈KNN(xi)∩p∈KNN(xj)}|

(12)

根據(jù)式(11)來(lái)分配不可避免的從屬點(diǎn)，對(duì)于分配剩下的可能的從屬點(diǎn)，SNN-DPC利用鄰域特點(diǎn)進(jìn)一步確定可能的從屬點(diǎn)的簇.

3 SKM-DPC算法

本文提出了一種共享K近鄰和多分配策略的密度峰值聚類算法(SKM-DPC).SKM-DPC利用共享近鄰距離度量數(shù)據(jù)點(diǎn)間的相似性，重新定義了局部密度的計(jì)算，優(yōu)化了樣本的二次分配策略，有效避免DPC算法未考慮數(shù)據(jù)間空間特性以及一步式分配問(wèn)題.

3.1 局部密度

對(duì)于數(shù)據(jù)點(diǎn)xi和xj，其相似度計(jì)算由式(13)給出：

(13)

其中∑p∈SNN(xi,xj)(dip+djp)代表數(shù)據(jù)點(diǎn)xi和xj之間的共享近鄰距離，反應(yīng)數(shù)據(jù)的局部稀疏性.取值越大，分布越稀疏.取值越小，分布越密集.|SNN(xi,xj)|代表數(shù)據(jù)點(diǎn)xi和xj之間的共享近鄰個(gè)數(shù)，共享近鄰個(gè)數(shù)越多，數(shù)據(jù)點(diǎn)越相似.指數(shù)函數(shù)ex的作用為歸一化相似度，避免取值過(guò)大造成量綱層面對(duì)后續(xù)密度計(jì)算的影響.

表1和表2分別給出SNN-DPC和SKM-DPC在Flame數(shù)據(jù)集上的相似度矩陣，聚類分析的目的是使同一簇的相似性更大，不同簇的差異性更大.表格的橫縱坐標(biāo)分別為Flame數(shù)據(jù)集的1～9號(hào)數(shù)據(jù)，其中1號(hào)和2號(hào)數(shù)據(jù)屬于同一簇.3號(hào)～9號(hào)數(shù)據(jù)屬于另一簇.由于本文算法SKM-DPC對(duì)相似度進(jìn)行了歸一化，故不做數(shù)量級(jí)上的對(duì)比.

SNN-DPC算法和SKM-DPC算法均能有效識(shí)別出同一簇的數(shù)據(jù)點(diǎn)，并沒(méi)有產(chǎn)生兩個(gè)不同簇的數(shù)據(jù)點(diǎn)存在相似度的異?，F(xiàn)象.SNN-DPC算法計(jì)算1號(hào)與2號(hào)數(shù)據(jù)的相似度為16.9，計(jì)算3號(hào)與8號(hào)數(shù)據(jù)的相似度為59.7，計(jì)算3號(hào)與9號(hào)數(shù)據(jù)的相似度為46.1.而SKM-DPC算法計(jì)算1號(hào)與2號(hào)數(shù)據(jù)的相似度為0.71，3號(hào)與8號(hào)數(shù)據(jù)的相似度為0.89，3號(hào)與9號(hào)屬于的相似度為0.89.1號(hào)和2號(hào)數(shù)據(jù)屬于同一簇，3號(hào)和8號(hào)數(shù)據(jù)屬于另一簇，則1號(hào)和2號(hào)的相似度與3號(hào)和8號(hào)的相似度應(yīng)當(dāng)盡可能高且接近，SNN-DPC中，1號(hào)與2號(hào)對(duì)比3號(hào)與8號(hào)，所計(jì)算出的相似度分別為16.9和59.7，同一簇的相似度差異性過(guò)大.而SKM-DPC計(jì)算出的相似度分別為0.71和0.88，同一簇的相似性更接近.SKM-DPC很好的度量出相似度.表2中，3號(hào)～9號(hào)數(shù)據(jù)間的相似度基本都穩(wěn)定在0.88～0.91的區(qū)間內(nèi)，滿足同一簇的相似度相對(duì)較高且接近的特點(diǎn).

表1 SNN-DPC計(jì)算的相似度Table 1 Similarity of SNN-DPC

表2 SKM-DPC計(jì)算的相似度Table 2 Similarity of SKM-DPC

數(shù)據(jù)點(diǎn)xi的局部密度為與xi相似度最高的K個(gè)相似度之和的r次方，其中r為放大因子.局部密度的計(jì)算由式(14)給出：

ρi=[∑xj∈L(xi)Sim(xi,xj)]r

(14)

其中，放大因子的討論見(jiàn)3.2.1節(jié).

3.2 聚類中心選擇與分配策略

3.2.1 聚類中心選擇

定義3.(決策值)局部密度ρi與相對(duì)距離δi的乘積定義為決策值，數(shù)學(xué)表達(dá)見(jiàn)式(15)：

γi=ρi·δi

(15)

聚類中心點(diǎn)與非聚類中心點(diǎn)的決策值γi在決策值圖的分布是不同的，因此正確選擇出聚類中心的前提是聚類中心點(diǎn)與非聚類中心點(diǎn)的決策值γi存在較大差異.大多改進(jìn)措施按照決策圖來(lái)選擇聚類中心，本文依照局部密度和相對(duì)距離的乘積，即決策值圖來(lái)選擇聚類中心.這樣做的好處在于避免了由于密度或者距離差異性不大時(shí)，無(wú)法準(zhǔn)確選取出聚類中心的這一問(wèn)題.決策值權(quán)衡了密度和距離分別的貢獻(xiàn)，本文中放大了局部密度的值，對(duì)于相同的距離的兩個(gè)數(shù)據(jù)點(diǎn)，局部密度的擴(kuò)大勢(shì)必導(dǎo)致決策值的差異性更大，有助于準(zhǔn)確識(shí)別聚類中心.

Spiral數(shù)據(jù)集是3類數(shù)據(jù)集，需要在決策值圖中選取3個(gè)點(diǎn)作為聚類中心點(diǎn).如圖4所示，圖4(a)為SNN-DPC算法在Spiral數(shù)據(jù)集的決策值圖，圖4(b)為SKM-DPC算法在Spiral數(shù)據(jù)集的決策值圖.區(qū)別在于2、3點(diǎn)的識(shí)別上，圖4(a)中2、3點(diǎn)與后續(xù)點(diǎn)存在重疊現(xiàn)象，而圖4(b)中的2、3點(diǎn)與后續(xù)點(diǎn)并無(wú)規(guī)律分布特點(diǎn).

圖4 SNN-DPC和SKM-DPC在Spiral和Jain上的決策值riFig.4 riof SNN-DPC and SKM-DPC on Spiral and Jain

Jain數(shù)據(jù)集是2類數(shù)據(jù)集，需要在決策值圖中選取2個(gè)點(diǎn)作為聚類中心點(diǎn).圖4(c)為SNN-DPC算法在Jain數(shù)據(jù)集的決策值圖，圖4(d)為SKM-DPC算法在Jain數(shù)據(jù)集的決策值圖.區(qū)別在于第3個(gè)點(diǎn)的識(shí)別上，圖4(c)中第3個(gè)點(diǎn)既和1、2點(diǎn)呈規(guī)律分布，又和第4個(gè)點(diǎn)及之后的點(diǎn)呈近似規(guī)律分布.圖4(d)中第3個(gè)點(diǎn)與第4個(gè)點(diǎn)及之后的點(diǎn)呈高度規(guī)律分布，而與第1、2點(diǎn)(聚類中心)并無(wú)規(guī)律性.這表明SKM-DPC算法在聚類中心點(diǎn)識(shí)別上更具優(yōu)勢(shì).

無(wú)論是SNN-DPC算法還是SKM-DPC算法，都可以在Spiral和Jain數(shù)據(jù)集上正確選擇出聚類中心，SKM-DPC算法在聚類中心與非聚類中心之間顯示出更大的差異性，表明我們選擇SKM-DPC算法可降低錯(cuò)誤率.

放大因子r調(diào)整規(guī)則：

在實(shí)際應(yīng)用里，放大因子r的取值應(yīng)當(dāng)控制在合理范圍，r過(guò)大則會(huì)導(dǎo)致一些較大的非聚類中心決策值急劇增大，逼近聚類中心點(diǎn)的決策值.r過(guò)小又會(huì)導(dǎo)致聚類中心點(diǎn)和非聚類中心點(diǎn)的決策值差異性降低，無(wú)法達(dá)到理想聚類效果.根據(jù)實(shí)驗(yàn)，建議放大因子r的取值范圍為r∈[2,5]，默認(rèn)值取r=3，本文實(shí)驗(yàn)結(jié)果均是在r=3下得出.

3.2.2 分配策略

定義4.(近鄰數(shù)可達(dá))當(dāng)數(shù)據(jù)點(diǎn)xi已分配給對(duì)應(yīng)簇，數(shù)據(jù)點(diǎn)xj還未分配，當(dāng)且僅當(dāng)滿足式(16)：

|{p|p∈KNN(xi)∩p∈KNN(xj)}|≥3K/4

(16)

認(rèn)為數(shù)據(jù)點(diǎn)xj應(yīng)當(dāng)與數(shù)據(jù)點(diǎn)xi屬同一簇.對(duì)于大多數(shù)數(shù)據(jù)集，各個(gè)簇之間交叉重疊部分為劃分的難點(diǎn)，為了降低分配錯(cuò)誤的風(fēng)險(xiǎn)，本文相比SNN-DPC算法提高了近鄰數(shù)可達(dá)的條件，當(dāng)且僅當(dāng)兩個(gè)數(shù)據(jù)點(diǎn)xi、xj間共享鄰近個(gè)數(shù)大于等于3K/4時(shí)，才將其劃分為同一簇.剩余未分配的數(shù)據(jù)點(diǎn)，考慮其近鄰特性，按照SNN-DPC算法中不可避免從屬點(diǎn)分配方法進(jìn)行分配.本文算法SKM-DPC可以很好的刻畫聚類分析中的不確定性，減小誤差，從而提高聚類精度.

3.3 SKM-DPC算法步驟

算法1.SKM-DPC

輸入：數(shù)據(jù)集X，近鄰數(shù)K

輸出：聚類結(jié)果C

1.歸一化數(shù)據(jù)集

2.計(jì)算數(shù)據(jù)點(diǎn)間歐氏距離，根據(jù)式(1)計(jì)算樣本點(diǎn)的K近鄰集合.

3.根據(jù)式(13)計(jì)算樣本點(diǎn)的相似度.

4.根據(jù)式(14)計(jì)算樣本點(diǎn)的局部密度.

5.根據(jù)式(9)、式(10)計(jì)算樣本點(diǎn)的相對(duì)距離.

6.根據(jù)式(15)計(jì)算樣本點(diǎn)的決策值，根據(jù)決策值畫出決策值圖.

7.由決策值圖選擇出聚類中心點(diǎn).

8.滿足式(16)的數(shù)據(jù)點(diǎn)劃分為同一簇.

9.不滿足式(16)的數(shù)據(jù)點(diǎn)輸入到SNN-DPC算法中，按照對(duì)不可避免從屬點(diǎn)的分配方法進(jìn)行劃分.

10.輸出聚類結(jié)果.

3.4 復(fù)雜度分析

本節(jié)分析中，認(rèn)為數(shù)據(jù)點(diǎn)總數(shù)為n，簇?cái)?shù)為m，近鄰數(shù)為k.

3.4.1 時(shí)間復(fù)雜度

DPC算法的時(shí)間復(fù)雜度主要由計(jì)算距離、密度、相對(duì)距離組成，復(fù)雜度均為O(n2)，則DPC算法的總的時(shí)間復(fù)雜度為O(n2).

SNN-DPC算法的時(shí)間復(fù)雜度主要由距離、近鄰、密度、相對(duì)距離、分配，總體復(fù)雜度為O((k+m)n2).

SKM-DPC算法的時(shí)間復(fù)雜度主要由以下5點(diǎn)構(gòu)成：

1)計(jì)算數(shù)據(jù)點(diǎn)的歐氏距離矩陣O(n2).

2)由于SKM-DPC算法需要計(jì)算k個(gè)近鄰，則計(jì)算局部密度為O(kn).

3)計(jì)算數(shù)據(jù)點(diǎn)的相對(duì)距離O(n2)

4)分配近鄰可達(dá)點(diǎn)的復(fù)雜度為O(mn2)

5)分配剩余點(diǎn)的復(fù)雜度為O(kn2+mn2)

本文總的時(shí)間復(fù)雜度為O((k+m)n2)和SNN-DPC的復(fù)雜度O((k+m)n2)相同，但高于DPC算法的O(n2).由于近鄰個(gè)數(shù)k和類簇個(gè)數(shù)m的取值偏小，相比于n來(lái)說(shuō)可以忽略不計(jì)，不會(huì)對(duì)運(yùn)行時(shí)長(zhǎng)產(chǎn)生大的影響.

3.4.2 空間復(fù)雜度

DPC算法和SNN-DPC算法的空間復(fù)雜度均為O(n2).

SKM-DPC算法的空間復(fù)雜度主要由以下3點(diǎn)構(gòu)成：

1)計(jì)算距離矩陣和相似度矩陣的空間復(fù)雜度為O(n2).

2)計(jì)算局部密度和相對(duì)距離的空間復(fù)雜度為O(n).

3)分配非聚類中心點(diǎn)的空間復(fù)雜度為O(mn).

本文總的空間復(fù)雜度為O(n2)，與DPC算法、SNN-DPC算法相同.

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

本文選取合成數(shù)據(jù)集與UCI真實(shí)數(shù)據(jù)集與對(duì)SKM-DPC性能進(jìn)行評(píng)估，將實(shí)驗(yàn)結(jié)果與SNN-DPC、DPC-KNN、DPC，進(jìn)行對(duì)比.對(duì)比算法均使用的是作者公開(kāi)的源代碼，其中DPC算法采用的是高斯核聚類.各算法的的參數(shù)均選擇的最優(yōu)值.

本文選用3個(gè)聚類評(píng)價(jià)指標(biāo)：AMI(Adjusted Mutual Information)[14]、ARI(Adjusted Rand Index)[14]、FMI(Fowlkes Mallows Index)[15]，其中ARI的取值為[-1，1]，AMI和FMI的取值為[0，1]，取值越大，聚類性能越優(yōu).

實(shí)驗(yàn)環(huán)境：Intel(R)core(TM)i5-8300H CPU@2.3GHZ 2.30GHz處理器，機(jī)帶RAM為8.00GB，操作系統(tǒng)為Windows10 64位.

4.1 人工合成數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)選取8個(gè)合成數(shù)據(jù)集對(duì)SKM-DPC性能進(jìn)行評(píng)估，數(shù)據(jù)集的信息見(jiàn)表3.

表3 合成數(shù)據(jù)集信息Table 3 Information of synthetic dataset

表4給出4種算法在8個(gè)合成數(shù)據(jù)集上的聚類評(píng)價(jià)指標(biāo)值，分別為AMI、ARI、FMI.表中PAR為每個(gè)算法的最優(yōu)參數(shù)值，黑體的結(jié)果表示同一個(gè)數(shù)據(jù)集下某項(xiàng)指標(biāo)的最優(yōu)值.

表4 各算法在合成數(shù)據(jù)集上的性能值Table 4 Performance indicators values of various algorithms on synthetic dataset

AlgorithmPathbasedSpiralAggregationR15AMIARIFMIPARAMIARIFMIPARAMIARIFMIPARAMIARIFMIPARSKM-DPC0.94820.96950.9797201.00001.00001.000050.99220.99560.9966270.99380.99280.993315SNN-DPC0.90010.92940.952991.00001.00001.000050.95000.95940.9681150.99380.99280.993310DPC-KNN0.52710.51720.7424100.49600.39770.615250.97400.98260.9864150.99070.98920.989917DPC0.49980.45300.658521.00001.00001.000020.99220.99560.99663.90.99380.99280.99330.6

PAR參數(shù)在不同算法中的具體值說(shuō)明：在SKM-DPC算法、SNN-DPC算法、DPC-KNN算法中，PAR代表實(shí)驗(yàn)選取近鄰的個(gè)數(shù)K值.DPC中，PAR代表截?cái)嗑嚯xdc值.

在Flame數(shù)據(jù)集上，我們發(fā)現(xiàn)SKM-DPC算法的各項(xiàng)指標(biāo)值均略低于DPC.這現(xiàn)象的原因?yàn)椋?Flame數(shù)據(jù)集有2個(gè)類簇，整體呈現(xiàn)平衡性的分布特征.根據(jù)實(shí)驗(yàn)觀察得出：SKM-DPC與DPC的聚類結(jié)果僅在一個(gè)數(shù)據(jù)點(diǎn)的劃分上出現(xiàn)了區(qū)別，該數(shù)據(jù)點(diǎn)處于兩個(gè)類簇的重疊區(qū)域，SKM-DPC未能將該數(shù)據(jù)點(diǎn)正確劃分，而DPC正確劃分了該數(shù)據(jù)點(diǎn).SKM-DPC和DPC算法均能找到正確的聚類中心，對(duì)于未分配的數(shù)據(jù)點(diǎn)，DPC采用的是將其劃分到密度比起高且距離最近的已分配數(shù)據(jù)點(diǎn)所在的類簇，這種分配策略簡(jiǎn)單高效，但易受數(shù)據(jù)點(diǎn)結(jié)構(gòu)的影響，魯棒性不強(qiáng).SKM-DPC采用的是將其首先劃分到與其共享近鄰個(gè)數(shù)達(dá)到3K/4的已分配點(diǎn)所在類簇，如未滿足條件將會(huì)根據(jù)該點(diǎn)的近鄰分配情況來(lái)綜合考量該數(shù)據(jù)點(diǎn)所屬類簇.在本文實(shí)驗(yàn)中，SKM-DPC在絕大多數(shù)數(shù)據(jù)集的聚類魯棒性均強(qiáng)于DPC.

圖5和圖6分別為SKM-DPC和SNN-DPC在6個(gè)數(shù)據(jù)集上的聚類結(jié)果，由于篇幅受限，故僅給出SKM-DPC和SNN-DPC的聚類結(jié)果.圖5(a)和圖6(a)是Jain的聚類結(jié)果，Jain數(shù)據(jù)集的特點(diǎn)是月牙狀且密度不均.SKM-DPC的效果均優(yōu)于其他算法，正確的找到密度峰值點(diǎn)且對(duì)剩余點(diǎn)正確劃分，SNN-DPC算法導(dǎo)致下方月牙狀數(shù)據(jù)中的一小部分被錯(cuò)誤劃分.圖5(b)和圖6(b)是Flame的聚類結(jié)果，SKM-DPC僅有1個(gè)數(shù)據(jù)點(diǎn)被劃分錯(cuò)誤，而SNN-DPC有多個(gè)數(shù)據(jù)點(diǎn)被劃分錯(cuò)誤.圖5(c)和圖6(c)是Spiral的聚類結(jié)果，SKM-DPC和SNN-DPC均能正確聚類該數(shù)據(jù)集.圖5(d)和圖6(d)是Aggregation的聚類結(jié)果，Aggregation數(shù)據(jù)集的特點(diǎn)是呈現(xiàn)7個(gè)堆狀分布，有2堆存在交叉分布.SKM-DPC的聚類錯(cuò)誤率最低，SNN-DPC聚類錯(cuò)誤率稍大.圖5(e)和圖6(e)是S2的聚類結(jié)果，S2數(shù)據(jù)集的特點(diǎn)是15個(gè)類簇中每一簇都與其他至少一個(gè)類簇存在交叉分布.SKM-DPC的聚類效果最好，SNN-DPC次之.圖5(f)和圖6(f)是D31的聚類結(jié)果，D31具有較多的類簇個(gè)數(shù)，同時(shí)每個(gè)類簇都與其他至少一個(gè)類簇(大多數(shù)情況是3個(gè))都有交叉重疊部分，交叉重疊部分的劃分效果是展示算法優(yōu)越性的體現(xiàn).劃分精度最高的是SKM-DPC算法，SNN-DPC算法略低.

4.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)在4個(gè)真實(shí)數(shù)據(jù)集上驗(yàn)證SKM-DPC算法和另3種算法的表現(xiàn).真實(shí)數(shù)據(jù)集的信息見(jiàn)表5.

表6展示的是4種算法在4個(gè)真實(shí)數(shù)據(jù)集上的表現(xiàn).從表6中可以看出，SKM-DPC算法的AMI、ARI、FMI指標(biāo)均高于SNN-DPC、DPC-KNN、DPC算法.特別的，在ionnsphere數(shù)據(jù)集上，本文算法的AMI指標(biāo)較DPC算法提高了22.12%.在waveform數(shù)據(jù)集上，本文算法的ARI指標(biāo)較DPC算法提高了34.5%，較DPC-KNN算法ARI指標(biāo)提高了40.24%.在wine數(shù)據(jù)集上，本文算法的FMI指標(biāo)較DPC算法提高了16%.在seeds數(shù)據(jù)集上，本文算法的各項(xiàng)指標(biāo)均比其他3個(gè)方法提高了至少2%.

圖5 SKM-DPC在不同數(shù)據(jù)集的聚類結(jié)果Fig.5 Clustering results of SKM-DPC in different data sets

圖6 SNN-DPC在不同數(shù)據(jù)集的聚類結(jié)果Fig.6 Clustering results of SNN-DPC in different data set

表5 真實(shí)數(shù)據(jù)集信息Table 5 Information of real dataset

表6 各算法在真實(shí)數(shù)據(jù)集上的性能值Table 6 Performance indicators values of various algorithms on real dataset

5 結(jié) 論

針對(duì)DPC算法的局部密度定義簡(jiǎn)單且無(wú)統(tǒng)一的度量方式以及單一分配策略易導(dǎo)致連錯(cuò)問(wèn)題，本文提出一種共享K近鄰和多分配策略的密度峰值聚類算法(SKM-DPC).SKM-DPC算法引入共享近鄰距離來(lái)度量數(shù)據(jù)點(diǎn)間的相似性，增強(qiáng)了樣本點(diǎn)與其近鄰間的聯(lián)系，解決了DPC算法的局部密度定義簡(jiǎn)單且無(wú)統(tǒng)一度量方式的問(wèn)題.提出了基于放大因子優(yōu)化的局部密度計(jì)算方式，擴(kuò)大了聚類中心在決策值圖中與非聚類中心點(diǎn)的差異性.優(yōu)化了樣本點(diǎn)的二次分配策略，相比DPC算法的單一分配策略，有效提升了聚類精度.在真實(shí)數(shù)據(jù)集以及人工數(shù)據(jù)集上的測(cè)試表明，SKM-DPC算法能夠有效提高聚類精度，并能夠很好的捕捉聚類的準(zhǔn)確性.本文的實(shí)驗(yàn)結(jié)果雖較其他方法存在優(yōu)勢(shì)，但如何更準(zhǔn)確的劃分?jǐn)?shù)據(jù)集中交叉重疊部分的所屬簇是今后研究的難點(diǎn).