自然鄰居密度極值聚類(lèi)算法

張忠林，趙 昱，閆光輝

蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730000

數(shù)據(jù)聚類(lèi)把數(shù)據(jù)對(duì)象按照不同屬性分割成確定數(shù)目的同質(zhì)子集，每個(gè)同質(zhì)子集貼上屬性標(biāo)簽后稱(chēng)之為類(lèi)簇。對(duì)于任何一個(gè)類(lèi)簇滿(mǎn)足簇內(nèi)數(shù)據(jù)對(duì)象特征相似，簇間數(shù)據(jù)對(duì)象特征差異較大的條件[1]。聚類(lèi)概念已被引入到多個(gè)研究領(lǐng)域之中，例如：智能算法改進(jìn)、大數(shù)據(jù)分析、模式檢測(cè)、神經(jīng)網(wǎng)絡(luò)等[2]。聚類(lèi)算法發(fā)展過(guò)程中提出了許多經(jīng)典算法，如基于劃分思想k-means算法[3]、基于層次思想EM算法[4]、基于密度思想DBSCAN、RNNDBSCAN算法[5-6]，基于網(wǎng)格思想CLIQUE算法[7]、基于模糊思想FCM算法[8]。

隨著對(duì)數(shù)據(jù)集深入研究發(fā)現(xiàn)密度峰值是數(shù)據(jù)集的一個(gè)重要屬性，因此2014年Rodriguez等[9]提出基于密度峰值算法（clustering by fast search and find of density peaks，DPC），DPC算法迭代過(guò)程中人工調(diào)參少，可以發(fā)現(xiàn)任意非球狀簇并且敏感數(shù)據(jù)集中的噪聲點(diǎn)。但是DPC算法也存在三個(gè)不足[10]：（1）預(yù)先選取的截?cái)嗑嚯x具有一定隨機(jī)性和經(jīng)驗(yàn)性，選取的截?cái)嗑嚯x直接影響聚類(lèi)結(jié)果的好壞；（2）計(jì)算局部密度時(shí)忽略數(shù)據(jù)分布情況，當(dāng)簇間的數(shù)據(jù)稀疏程度相差較大時(shí)，即使設(shè)定合理參數(shù)也得不到理想聚類(lèi)效果；（3）數(shù)據(jù)對(duì)象間相似性度量?jī)H采用歐氏距離模型，在高維數(shù)據(jù)集中導(dǎo)致度量結(jié)果不準(zhǔn)確，并且隨著數(shù)據(jù)集規(guī)模遞增，每迭代一次相似性計(jì)算次數(shù)為n(n-1)2，導(dǎo)致算法時(shí)間復(fù)雜度為O(n2)影響算法效率。

DPC算法存在人工選擇的隨機(jī)性和數(shù)據(jù)間度量準(zhǔn)則的不準(zhǔn)確性。對(duì)上述兩個(gè)問(wèn)題提出了多種改進(jìn)方法，Du等[11]提出了k近鄰方法，利用k-近鄰概念定義截?cái)嗑嚯x和局部密度，該方法根據(jù)數(shù)據(jù)集特征能夠生成合理的截?cái)嗑嚯x，在新的截?cái)嗑嚯x下計(jì)算的局部密度更符合數(shù)據(jù)集的真實(shí)分布，引入決策圖將決策點(diǎn)選取可視化。Gou等[12]把數(shù)據(jù)對(duì)象的k-最近鄰引入圖G中，對(duì)于任意數(shù)據(jù)對(duì)象若存在數(shù)據(jù)對(duì)象是其最近鄰，則在這兩點(diǎn)之間生成一條邊賦予對(duì)應(yīng)的權(quán)值，遍歷圖用權(quán)值來(lái)定義局部密度。Jin等[13]引入自然鄰居概念，采用樹(shù)的遍歷檢索最近鄰，來(lái)消除對(duì)于參數(shù)k的敏感問(wèn)題。Wang等[14]提出了基于極值的聚類(lèi)方法剔除離群點(diǎn)，在局部范圍內(nèi)采用合并運(yùn)算找到近鄰最多的點(diǎn)設(shè)置為聚類(lèi)中心，以此聚類(lèi)中心為基礎(chǔ)完成聚類(lèi)。

基于上述研究，本文針對(duì)密度峰值算法的不足：（1）當(dāng)樣本數(shù)據(jù)集密度差異較大時(shí)，低密度區(qū)域聚類(lèi)中心比高密度區(qū)域聚類(lèi)中心難以發(fā)現(xiàn)，導(dǎo)致聚類(lèi)結(jié)果不準(zhǔn)確；（2）當(dāng)聚類(lèi)更稀疏時(shí)，一個(gè)數(shù)據(jù)對(duì)象被識(shí)別成離群點(diǎn)概率增加；為了解決上述的兩個(gè)問(wèn)題，提出了自然鄰居密度極值聚類(lèi)算法（Natural Neighbor Density Extremum Clustering algorithm，NN-DEC）。該算法以密度極值作為聚類(lèi)中心選擇標(biāo)準(zhǔn)，更加準(zhǔn)確和全面地選取數(shù)據(jù)集聚類(lèi)中心。首先調(diào)用自然鄰居搜索算法，迭代有限次后數(shù)據(jù)集形成自然穩(wěn)定狀態(tài)，在該狀態(tài)下分割出數(shù)據(jù)對(duì)象的自然鄰居；其次將處理后數(shù)據(jù)集導(dǎo)入密度距離自適應(yīng)模型，生成數(shù)據(jù)對(duì)象局部密度；然后，計(jì)算數(shù)據(jù)對(duì)象連通值，在使用連通值將數(shù)據(jù)集劃分成高低密度區(qū)域和離群點(diǎn)，引入密度極值函數(shù)找出不同區(qū)域聚類(lèi)中心點(diǎn)；最后，將不同區(qū)域內(nèi)未被分配數(shù)據(jù)對(duì)象，劃分到離其最近的聚類(lèi)中心所在簇中合并聚類(lèi)結(jié)果。

1 相關(guān)工作

表1為文章所定義數(shù)據(jù)符號(hào)和算法縮寫(xiě)摘要。

表1 符號(hào)摘要Table 1 Summary of notations

1.1 DPC算法

DPC算法聚類(lèi)中心選取條件：（1）簇中心點(diǎn)為局部密度最高的點(diǎn)，周?chē)魏我稽c(diǎn)局部密度都低于簇中心點(diǎn)；（2）對(duì)于任意簇中心點(diǎn)比它密度更高的局部密度峰值點(diǎn)，在數(shù)據(jù)集中與其分布的距離較遠(yuǎn)。DPC算法核心需要計(jì)算xi的局部密度ρi以及最近距離δi。局部密度ρi計(jì)算如公式（1）所示：

DPC算法另一種計(jì)算局部密度的方法采用高斯核定義計(jì)算，如公式（3）所示：

使用高斯核計(jì)算數(shù)據(jù)對(duì)象的局部密度，ρi等于截?cái)嗑嚯xdc內(nèi)數(shù)據(jù)對(duì)象的個(gè)數(shù)和。

δi計(jì)算方法如公式（4）所示：

DPC算法將局部密度ρi和距離δi歸一化處理后，用做標(biāo)準(zhǔn)量引入到?jīng)Q策圖中，在決策圖中選定ρ和δ標(biāo)準(zhǔn)值。DPC算法偽代碼[15]如算法1所示：數(shù)據(jù)樣本為N，算法的時(shí)間復(fù)雜度為O(N)。

算法1DPC(ρ,d)

Input：局部密度ρ，距離矩陣d

1.2 密度自適應(yīng)距離度量

如圖1所示，以歐式距離度量數(shù)據(jù)對(duì)象a和b之間的相似性，因距離較近則兩個(gè)數(shù)據(jù)對(duì)象相似性較高，可劃分到同一個(gè)簇中。但在數(shù)據(jù)集實(shí)際分布中a和c處在同一簇中，因此歐氏距離度量準(zhǔn)則在該數(shù)據(jù)集中的度量誤差較大，同時(shí)不滿(mǎn)足上述聚類(lèi)假設(shè)中特征交叉相似性。

圖1 合成數(shù)據(jù)集Fig.1 Synthetic datasets

基于上述分析應(yīng)在環(huán)狀和密度差異較大數(shù)據(jù)集中，引入一種新的密度自適應(yīng)距離度量方法。文獻(xiàn)[16]提出一種有效的密度自適應(yīng)距離度量模型，將一個(gè)數(shù)據(jù)集分布映射到一個(gè)二維橢圓模型中，建立橢圓二維空間，度量?jī)蓚€(gè)數(shù)據(jù)對(duì)象之間相似性度量，橢圓長(zhǎng)軸和短軸參數(shù)將參與到運(yùn)算過(guò)程中。

定義A={a1,a2,…,an}，B={b1,b2,…,bn}，自適應(yīng)距離度量如公式（5）所示：

其中，wl和ws計(jì)算如公式（6）所示：

其中，wij1和wij2計(jì)算如公式（7）所示：

本文中采用高斯核方式進(jìn)行局部密度計(jì)算，對(duì)于每一個(gè)數(shù)據(jù)對(duì)象都可以求出它在數(shù)據(jù)集中的局部密度ρi，密度自適應(yīng)距離度量方法如公式（8）所示：

1.3 錨點(diǎn)選取方法

數(shù)據(jù)集中固定的點(diǎn)稱(chēng)之為錨點(diǎn)，引入基于錨點(diǎn)的聚類(lèi)[17]，計(jì)算每一個(gè)成為聚類(lèi)中心點(diǎn)的最小損耗值，利用損耗值來(lái)優(yōu)化聚類(lèi)中心的選取。錨點(diǎn)選取如公式（9）所示：

f(xj)計(jì)算由公式（10）所示：

指示函數(shù)值為1表示該數(shù)據(jù)點(diǎn)可以作為錨點(diǎn)，值為0表示該數(shù)據(jù)點(diǎn)不能作為錨點(diǎn)。

1.4 高低密度區(qū)域劃分和離群點(diǎn)檢測(cè)

定義1（離群點(diǎn)[18]）觀(guān)察一組數(shù)據(jù)對(duì)象，存在異于這組觀(guān)察值的數(shù)據(jù)對(duì)象被稱(chēng)為數(shù)據(jù)集中的離群點(diǎn)。

定義2（相似性度量）定義P={p1,p2,…,pn}和S={s1,s2,…,sn}，P和S屬性之間采用余弦相似性度量準(zhǔn)則，如公式（11）所示：

數(shù)據(jù)集中所有向量計(jì)算后會(huì)生成一個(gè)余弦相似性矩陣Simn×n，n為數(shù)據(jù)集大小。矩陣中的每一項(xiàng)Sim[i,j]對(duì)應(yīng)于xi和xj之間相似性值，使用相似性矩陣構(gòu)建相互鄰居圖，問(wèn)題就轉(zhuǎn)換成了如何在圖上找到孤立的點(diǎn)。假設(shè)該圖連通子圖集合中存在孤立的點(diǎn)，則該點(diǎn)就可以稱(chēng)之為數(shù)據(jù)集中的離群點(diǎn)。

節(jié)點(diǎn)u的連通值[19]c(u)會(huì)隨著迭代次數(shù)t收斂于一個(gè)穩(wěn)定的值，如公式（12）所示：

初始化每一個(gè)節(jié)點(diǎn)的連通值c0(vi)=1n(i:1-n)。

S稱(chēng)之為轉(zhuǎn)移矩陣，如公式（14）所示：

相似矩陣標(biāo)準(zhǔn)化可以使得：（1）轉(zhuǎn)移矩陣中的每一行的求和的值為1；（2）符合馬爾可夫鏈的基本性質(zhì)；根據(jù)連通值的大小找到數(shù)據(jù)集中的高低密度區(qū)域和離群點(diǎn)。

算法2Detection(X,T)

Input：數(shù)據(jù)集X={x1,x2,…,xn}，密度閾值T

Output：X_high，X_low，Outlies

算法2中主要是對(duì)數(shù)據(jù)集中每個(gè)元素連通值計(jì)算，假設(shè)數(shù)據(jù)集大小為n，則計(jì)算連通值時(shí)間復(fù)雜度為O(n2)，轉(zhuǎn)移矩陣S計(jì)算時(shí)間復(fù)雜度也為O(n2)，算法2主要包括連通值和轉(zhuǎn)移矩陣計(jì)算，因此時(shí)間復(fù)雜度為O(n2)。

1.5 自然鄰居

自然鄰居[20]是一種無(wú)參的近鄰概念，提出的目的是解決k-最近鄰[21-22]中參數(shù)選擇問(wèn)題。

定義3（自然穩(wěn)定結(jié)構(gòu)[23]）xi存在鄰居為xj，同時(shí)xj也存在鄰居為xi，若滿(mǎn)足上述條件則xj是xi自然鄰居；若數(shù)據(jù)集任意數(shù)據(jù)對(duì)象存在至少一個(gè)自然鄰居，數(shù)據(jù)集就形成了自然穩(wěn)定結(jié)構(gòu)（Natural Stable Structure，NSS）。

定義4（k-最近鄰[24]）數(shù)據(jù)對(duì)象xi與數(shù)據(jù)集中其他數(shù)據(jù)對(duì)象的歐氏距離，小于設(shè)定閾值的所有點(diǎn)集合，通過(guò)上述集合生成自然鄰居集合（Natural Neighborhood Set，NNS）。

定義5（自然特征值[25]）自然鄰居特征值（Natural Neighbor Eigenvalue，NNE）λ是在搜索自然鄰居過(guò)程中，當(dāng)數(shù)據(jù)的形成NSS結(jié)構(gòu)時(shí)所迭代的次數(shù)。

定義6（自然鄰居[25]）自然鄰居（Natural Neighbor，NaN）在集合概念下定義如公式（18）所示：

如圖2，對(duì)比了自然穩(wěn)定狀態(tài)下數(shù)據(jù)對(duì)象之間的關(guān)系和k近鄰下數(shù)據(jù)對(duì)象之間的關(guān)系。

圖2 自然鄰居和k最近鄰對(duì)比Fig.2 Comparison of natural neighbors and k-nearest neighbors

基于上述公式的分析，給出自然鄰居搜索算法基本思想：首先要尋找到每一個(gè)數(shù)據(jù)對(duì)象的k-最近鄰，根據(jù)k-最近鄰結(jié)果構(gòu)造相互鄰居圖。算法迭代終止條件：（1）不存在最近鄰數(shù)據(jù)對(duì)象時(shí)；（2）迭代次數(shù)大于等于自然鄰居個(gè)數(shù)減去迭代次數(shù)開(kāi)方時(shí)。自然鄰居搜索算法（Natural Neighbor Search Algorithm，NaNSA）如算法3所示：

算法3NaNSA(X)

Input：數(shù)據(jù)集X={x1,x2,…,xn}

Output：自然鄰居個(gè)數(shù)num，相互鄰居圖G，自然特征值λ

算法3的時(shí)間復(fù)雜度分析：假定數(shù)據(jù)對(duì)象個(gè)數(shù)為n，算法時(shí)間消耗主要在構(gòu)建KD樹(shù)數(shù)據(jù)結(jié)構(gòu)上，構(gòu)建KD樹(shù)的時(shí)間復(fù)雜度為O(nlbn)。由于數(shù)據(jù)對(duì)象個(gè)數(shù)n是有限的，因此算法時(shí)間復(fù)雜度為O(nlbn)。

2 NN-DEC算法

2.1 聚類(lèi)中心確定

根據(jù)文獻(xiàn)[26]提出極值理論，極值描述現(xiàn)象是“不平均”分布，聚焦的是高分位數(shù)而不是數(shù)據(jù)集整體的統(tǒng)計(jì)數(shù)據(jù)。例如，樣本均方差、樣本期望、樣本離差平方和等。

密度差異較大的數(shù)據(jù)集對(duì)低密度區(qū)域聚類(lèi)中心選取存在一定誤差，會(huì)導(dǎo)致聚類(lèi)結(jié)果不準(zhǔn)確，因此引入極值概念來(lái)解決上述出現(xiàn)的問(wèn)題。本文采用密度極值目標(biāo)函數(shù)計(jì)算每一個(gè)數(shù)據(jù)對(duì)象局部密度極值，采用橢圓模型處理后，使局部密度更加貼合數(shù)據(jù)集的真實(shí)分布。

自然鄰居搜索算法自適應(yīng)得到數(shù)據(jù)對(duì)象自然鄰居，自適應(yīng)搜索過(guò)程中消除了對(duì)于截?cái)嗑嚯xdc的敏感問(wèn)題。對(duì)得到自然鄰居數(shù)據(jù)對(duì)象計(jì)算局部密度，根據(jù)數(shù)據(jù)對(duì)象之間歐式距離選擇聚類(lèi)中心存在誤差，因此引入上文提出密度自適應(yīng)距離方法，選擇高低密度區(qū)域聚類(lèi)中心。

為了提升算法效率調(diào)整因子采用線(xiàn)性方式計(jì)算wij=θwij1+(1-θ)wij2。θ計(jì)算取決于wij1和wij2，調(diào)整因子計(jì)算方式如公式（19）所示：

因此自然穩(wěn)定狀態(tài)下xi局部密度計(jì)算公式，如公式（21）所示：

采用上文提到過(guò)的密度自適應(yīng)距離度量方法，對(duì)數(shù)據(jù)對(duì)象局部密度計(jì)算。上述方法當(dāng)數(shù)據(jù)集為NSS狀態(tài)時(shí)計(jì)算每一個(gè)數(shù)據(jù)對(duì)象局部密度。

密度在一個(gè)數(shù)據(jù)集中分布是不平衡，因此會(huì)存在高密度區(qū)域和低密度區(qū)域，選取聚類(lèi)中心時(shí)需要設(shè)置一個(gè)合理閾值，區(qū)分出聚類(lèi)中心點(diǎn)和非聚類(lèi)中心點(diǎn)。

歸一化采用最小最大標(biāo)準(zhǔn)化處理（Min-Max Normalization）如公式（22）所示：

使用上述歸一化處理可以將密度和距離范圍控制到[0,1]范圍之內(nèi)。計(jì)算出ρi如公式（23）所示：

密度和距離歸一化處理后，如圖3所示。

圖3 決策圖和聚類(lèi)結(jié)果Fig.3 Decision graph and clustering results

從上述決策圖看出在決策范圍中出現(xiàn)了7個(gè)聚類(lèi)中心點(diǎn)，這些點(diǎn)可以作為聚類(lèi)中心。體現(xiàn)在圖3（b）中Aggregation聚類(lèi)結(jié)果圖，標(biāo)準(zhǔn)化后聚類(lèi)中心選擇更加準(zhǔn)確，邊界區(qū)分明顯聚類(lèi)效果提升。

本文設(shè)定φ(x)計(jì)算采用均方根公式，將其引入到聚類(lèi)中心識(shí)別函數(shù)中，如公式（24）所示：

引入上文提到錨點(diǎn)選取方法，構(gòu)造一個(gè)聚類(lèi)中心識(shí)別函數(shù)H，如公式（25）所示：

其中，密度自適應(yīng)距離度量過(guò)程中，將損益值取均方根保證算法在迭代過(guò)程中函數(shù)損益值不會(huì)出現(xiàn)負(fù)值。上述公式第二部分cosρ(xj)引入密度對(duì)于聚類(lèi)中心選擇的影響，公式（21）對(duì)于低密度區(qū)域聚類(lèi)中心選擇誤差較大，在此基礎(chǔ)上用極值來(lái)尋找聚類(lèi)中心。

對(duì)公式（25）中密度ρi求導(dǎo)可得：

對(duì)于函數(shù)H進(jìn)行求導(dǎo)時(shí)，將數(shù)據(jù)集每一個(gè)數(shù)據(jù)對(duì)象密度看作變量，數(shù)據(jù)對(duì)象xi密度在求導(dǎo)過(guò)成中當(dāng)作常量。公式（25）中f(xj)判斷該數(shù)據(jù)對(duì)象是否為錨點(diǎn)指示，若是錨點(diǎn)則取值為1，若不是則取值為0；公式（26）求導(dǎo)后得到結(jié)果為公式（27）所示，其中將ρi替換后并且去掉集合符號(hào)得到一個(gè)密度極值函數(shù)，如公式（27）所示：

其中，x代表數(shù)據(jù)對(duì)象密度，密度定義在[0,1]，函數(shù)H′中冪函數(shù)增幅是大于正弦函數(shù)增幅，根據(jù)導(dǎo)函數(shù)定義在定義域范圍內(nèi)大于零，得出該導(dǎo)函數(shù)對(duì)應(yīng)的原函數(shù)是單調(diào)遞增，對(duì)于局部來(lái)說(shuō)函數(shù)值越大，代表這個(gè)點(diǎn)周?chē)鷶?shù)據(jù)點(diǎn)分布是更加密集，說(shuō)明這個(gè)數(shù)據(jù)對(duì)象在局部范圍內(nèi)具有更高的密度。使用極值方法可以在高低密度區(qū)域中準(zhǔn)確識(shí)別到聚類(lèi)中心點(diǎn)。

2.2 高低密度區(qū)域聚類(lèi)

根據(jù)2.1節(jié)按照統(tǒng)一密度閾值去選取聚類(lèi)中心，低密度區(qū)域聚類(lèi)中心選取會(huì)存在誤差，針對(duì)上述問(wèn)題構(gòu)建馬爾可夫模型，使用模型生成相互鄰居圖，利用圖上節(jié)點(diǎn)連通值去區(qū)分低密度和高密度區(qū)域，并且剔除掉離群點(diǎn)，進(jìn)而對(duì)兩個(gè)區(qū)域分別進(jìn)行聚類(lèi)。

首先利用公式（11）計(jì)算每一個(gè)數(shù)據(jù)對(duì)象與其他剩余數(shù)據(jù)對(duì)象之間的VS值，采用這些值生成一個(gè)余弦相似性矩陣Simn×n，其中矩陣中每一項(xiàng)sim[i,j]代表，數(shù)據(jù)對(duì)象xi和數(shù)據(jù)對(duì)象xj之間VS值；對(duì)Simn×n每一行進(jìn)行歸一化處理得到轉(zhuǎn)移矩陣，得到轉(zhuǎn)移矩陣后初始化每一個(gè)數(shù)據(jù)對(duì)象連通值c(u)，在每一次迭代中使用公式（12）更新當(dāng)前每一個(gè)數(shù)據(jù)對(duì)象c(u)值；當(dāng)連續(xù)兩次迭代中，數(shù)據(jù)對(duì)象連通值不再發(fā)生變化說(shuō)明節(jié)點(diǎn)連通值穩(wěn)定，然后將每一個(gè)數(shù)據(jù)對(duì)象連通值進(jìn)行降序排列。根據(jù)文獻(xiàn)[19]提出的模型設(shè)定閾值T，區(qū)分出高低密度區(qū)域和離群點(diǎn)，如果一個(gè)數(shù)據(jù)對(duì)象連通值c(u)等于0，則說(shuō)明該數(shù)據(jù)點(diǎn)為這個(gè)數(shù)據(jù)集中的離群點(diǎn)。

區(qū)分出高密度和低密度區(qū)域后，兩個(gè)區(qū)域分別進(jìn)行聚類(lèi)，高密度區(qū)域聚類(lèi)，首先剔除離群點(diǎn)，再使用密度自適應(yīng)距離方法計(jì)算數(shù)據(jù)對(duì)象局部密度極值，對(duì)比密度極值，大于所設(shè)定的密度閾值點(diǎn)歸入聚類(lèi)中心點(diǎn)集合，高密度區(qū)域非聚類(lèi)中心點(diǎn)較多，可以采用最近鄰原則將剩余點(diǎn)歸并到最近的簇中。在低密度區(qū)域，將每一個(gè)數(shù)據(jù)對(duì)象密度帶入公式（27）計(jì)算密度極值，當(dāng)大于設(shè)置密度閾值時(shí)，將該點(diǎn)劃入聚類(lèi)中心集合之中，因?yàn)樵诘兔芏葏^(qū)域中剩余數(shù)據(jù)量較少，將集合中非聚類(lèi)中心點(diǎn)使用k-means算法完成聚類(lèi)，各自完成聚類(lèi)后合并兩個(gè)區(qū)域的聚類(lèi)結(jié)果。

基于上述分析，給出NN-DEC算法基本思想：首先，引入自然鄰居概念消除了對(duì)近鄰參數(shù)k的敏感問(wèn)題，采用密度自適應(yīng)距離方法來(lái)計(jì)算數(shù)據(jù)對(duì)象局部密度。其次，構(gòu)建錨點(diǎn)和密度極值函數(shù)篩選聚類(lèi)中心，計(jì)算每一個(gè)數(shù)據(jù)對(duì)象連通值，根據(jù)連通值排序?qū)?shù)據(jù)集拆分成高密度區(qū)域和低密度區(qū)域，分別計(jì)算每個(gè)區(qū)域內(nèi)數(shù)據(jù)對(duì)象密度極值，迭代對(duì)比將數(shù)據(jù)集分成聚類(lèi)中心點(diǎn)集合和非聚類(lèi)中心點(diǎn)集合。最后將非聚類(lèi)中心點(diǎn)集合，按近鄰原則歸并到距離其最近的聚類(lèi)中心所在簇中。NN-DEC算法偽代碼如算法4所示：

算法4NN-DEC(X)

Input：數(shù)據(jù)集X=(x1,x2,…,xn)

Output：聚類(lèi)結(jié)果CL

設(shè)數(shù)據(jù)集中數(shù)據(jù)樣本個(gè)數(shù)為n，首先，獲得自然鄰居的時(shí)間復(fù)雜度為O(nlbn)，在自然穩(wěn)定態(tài)下計(jì)算局部密度時(shí)間復(fù)雜度為O(n2)。在進(jìn)行聚類(lèi)之前需要將數(shù)據(jù)集分成不同的區(qū)域，采用連通值構(gòu)建相互鄰居圖時(shí)間復(fù)雜度小于O(n2)，離群點(diǎn)檢測(cè)和高低密度區(qū)域聚類(lèi)，時(shí)間復(fù)雜度均小于O(n2)，綜上所述算法4時(shí)間復(fù)雜度為O(n2)。

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

為了驗(yàn)證NN-DEC算法在不同數(shù)據(jù)集上的聚類(lèi)效果，分別在人工合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上運(yùn)行算法。合成數(shù)據(jù)集包括不同規(guī)模和不同形狀的數(shù)據(jù)集，用于驗(yàn)證算法處理不同形狀簇的效果；真實(shí)數(shù)據(jù)集：UCI公共數(shù)據(jù)集，數(shù)據(jù)集稀疏程度差異較大來(lái)驗(yàn)證算法聚類(lèi)效果。通過(guò)與基于聚類(lèi)中心的K-means算法[3]、基于密度的DBSCAN算法[5]、DPC算法[9]、基于K近鄰優(yōu)化的KNN-DPC算法[11]、基于密度極值的EC算法[14]、基于自然近鄰密度極值優(yōu)化的NNDP算法[13]進(jìn)行各項(xiàng)指標(biāo)的對(duì)比。

實(shí)驗(yàn)環(huán)境：Operating System Win10 64；Inter?Core?i5-10210U CPU＠1.60 GHz 2.11 GHz處理器，16.00 GB RAM。所有代碼采用Python語(yǔ)言實(shí)現(xiàn)。

聚類(lèi)評(píng)價(jià)指標(biāo)為標(biāo)準(zhǔn)互信息[27]（Normalized Mutual Information，NMI）、F值[1]（F-Measure）、聚類(lèi)準(zhǔn)確率[27]（Clustering Accuracy，CA）以此來(lái)判斷全局聚類(lèi)準(zhǔn)確性。其中NMI、F值和CA取值范圍為[0,1]，值越接近1表示在該數(shù)據(jù)集上聚類(lèi)效果明顯。

3.1 合成數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

本節(jié)中采用7個(gè)合成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，各類(lèi)數(shù)據(jù)集的基本屬性如表2所示。選取表2中四個(gè)數(shù)據(jù)集對(duì)比NN-DEC和K近鄰算法，聚類(lèi)中心點(diǎn)和非聚類(lèi)中心點(diǎn)之間的緊湊程度如圖4所示。選取表2中四個(gè)人工數(shù)據(jù)集對(duì)比NN-DEC算法和DPC算法，聚類(lèi)效果如圖5所示。

表2 合成數(shù)據(jù)集Table 2 Synthetic datasets

圖4 NN-DEC算法在A(yíng)ggregation、Jain、Flame、Spiral上緊湊結(jié)果Fig.4 Compact results of NN-DEC algorithm on Aggregation，Jain，F(xiàn)lame，Spiral

圖5 NN-DEC和DPC算法在A(yíng)ggregation、S1、Flame、Spiral上聚類(lèi)結(jié)果Fig.5 NN-DEC and DPC algorithm clustering results on Aggregation，S1，F(xiàn)lame，Spiral

在圖4中可以看出本文提出的算法，對(duì)于聚類(lèi)中心和非聚類(lèi)中心之間的緊湊程度表達(dá)更好，在Spiral數(shù)據(jù)集上NN-DEC算法的邊界緊湊效果更加明顯。對(duì)于Jain數(shù)據(jù)集，本文算法在聚類(lèi)的緊湊程度好于DPC算法。

圖5中前4個(gè)子圖為NN-DEC算法聚類(lèi)效果，后4個(gè)子圖為DPC算法聚類(lèi)效果。從圖5中可以看出，在Flame合成數(shù)據(jù)集上，由于簇之間分布距離較近密度分布差異不均衡，因此在DPC算法進(jìn)行聚類(lèi)時(shí)導(dǎo)致聚類(lèi)結(jié)果不準(zhǔn)確，而采用NN-DEC算法進(jìn)行聚類(lèi)時(shí)，剔除了離群點(diǎn)影響，密度分布不均衡有更好的聚類(lèi)結(jié)果，并且在其他合成數(shù)據(jù)集上具有較好聚類(lèi)分布。其余幾個(gè)數(shù)據(jù)集上來(lái)看NN-DEC算法聚類(lèi)結(jié)果的邊界更清晰，準(zhǔn)確度更高，聚類(lèi)效果更加明顯。接下來(lái)分別在合成數(shù)據(jù)集上計(jì)算CA、NMI、F值。對(duì)上述對(duì)比聚類(lèi)算法計(jì)算各指標(biāo)值，結(jié)果如表3所示。

表3中展示了NN-DEC算法與對(duì)比的NNDP算法、EC算法、KNN-DPC算法、DPC算法、DBSCAN算法、Kmeans算法在合成數(shù)據(jù)集上三種評(píng)價(jià)指標(biāo)，可以看出除了Flame數(shù)據(jù)集，其他六個(gè)數(shù)據(jù)集上性能都優(yōu)于所對(duì)比的算法。具體分析：在A(yíng)ggregation數(shù)據(jù)集上因?yàn)閿?shù)據(jù)分布廣且密度分布不均勻，因此NN-DEC算法在上面聚類(lèi)效果是最佳的，NNDP算法的性能要優(yōu)于EC算法，因?yàn)閿?shù)據(jù)點(diǎn)密度分布較為均勻，EC算法在A(yíng)ggregation數(shù)據(jù)集上性能也是較好的。S1數(shù)據(jù)集類(lèi)別數(shù)較多、每個(gè)類(lèi)之間密度差異較大、類(lèi)之間距離較遠(yuǎn)，因此NNDEC算法在S1數(shù)據(jù)上性能優(yōu)于NNDP算法。Pathbased數(shù)據(jù)集數(shù)據(jù)分布相對(duì)集中密度分布較均勻，因此NN-DEC算法在該數(shù)據(jù)集上密度計(jì)算準(zhǔn)確，聚類(lèi)效果優(yōu)于其他對(duì)比聚類(lèi)算法。Spiral是一個(gè)環(huán)狀數(shù)據(jù)分布，數(shù)據(jù)間稀疏程度適中，由于數(shù)據(jù)間稠密程度均勻，NNDP、KNN-DPC、DPC、DBCSCAN算法和NN-DEC算法在該數(shù)據(jù)集上聚類(lèi)性能相當(dāng)。Flame數(shù)據(jù)集上類(lèi)別較少密度分布相對(duì)集中，EC算法在該數(shù)據(jù)集上性能要優(yōu)于NN-DEC算法。綜上所述說(shuō)明NN-DEC算法在處理密度差異較大數(shù)據(jù)上具有不錯(cuò)的效果。

采用折線(xiàn)圖方式來(lái)直觀(guān)表達(dá)NN-DEC算法NMI值，整體上優(yōu)于其他對(duì)比算法，如圖6。

從圖6中可以看出NN-DEC算法NMI值優(yōu)于其他對(duì)比算法，在DS6數(shù)據(jù)集上NN-DEC算法聚類(lèi)結(jié)果明顯優(yōu)于EC算法。

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

本節(jié)選取6個(gè)數(shù)據(jù)稀疏程度較大UCI真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。計(jì)算NN-DEC算法和對(duì)比算法，在真實(shí)數(shù)據(jù)集上的各個(gè)指標(biāo)值。如表4所示，所選取UCI數(shù)據(jù)集都為常見(jiàn)代表數(shù)據(jù)集，其中Waveform數(shù)據(jù)集為數(shù)據(jù)密度分布較密集、不均勻程度較大，具有代表性的一類(lèi)數(shù)據(jù)。

表3 各聚類(lèi)算法在合成數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)對(duì)比Table 3 Comparison of evaluation metrics of various clustering algorithms on synthetic data sets

圖6 算法在DS1～DS7上NMI值Fig.6 Algorithm NMI values on DS1～DS7

表4 UCI數(shù)據(jù)集Table 4 UCI Datasets

表5中計(jì)算了CA、NMI、F值三個(gè)聚類(lèi)指標(biāo)，并給出了NN-DEC算法和其他六個(gè)算法，在六個(gè)UCI公共數(shù)據(jù)集上的聚類(lèi)指標(biāo)結(jié)果。從表4中可以看出NN-DEC算法，在各個(gè)真實(shí)數(shù)據(jù)集上的聚類(lèi)評(píng)價(jià)指標(biāo)結(jié)果均優(yōu)于其他六個(gè)對(duì)比算法。Iris數(shù)據(jù)集上分布較散且密度相對(duì)分布均勻，NN-DEC算法的聚類(lèi)性能雖然優(yōu)于其他幾個(gè)算法，但是由于密度較均勻其他對(duì)比算法聚類(lèi)性能參數(shù)也較好。Cancer數(shù)據(jù)集維度大、密度分布差異大，NNDEC算法在該數(shù)據(jù)集上聚類(lèi)效果較好，KNN-DPC和EC算法在該數(shù)據(jù)集上聚類(lèi)性能相當(dāng)，NNDP算法性能要優(yōu)于EC和KNN-DPC算法。Wine數(shù)據(jù)集上密度極值分布明顯，數(shù)據(jù)分布緊湊，所以NN-DEC算法和EC算法聚類(lèi)性能相差很小，而NNDP算法沒(méi)有對(duì)聚類(lèi)中心點(diǎn)之間的距離，做自適應(yīng)處理性能低于EC算法，DBSCAN算法處理密度集中分布的數(shù)據(jù)集時(shí)聚類(lèi)性能，相較于其他算法更差。Waveform數(shù)據(jù)集中數(shù)據(jù)分布集中，局部密度極值容易計(jì)算，因此NN-DEC算法的性能優(yōu)于其他對(duì)比算法。Breast數(shù)據(jù)集上類(lèi)別數(shù)較少，K-means進(jìn)行劃分時(shí)聚類(lèi)效果明顯，聚類(lèi)性能與NN-DEC算法相差不大。Segment數(shù)據(jù)集上數(shù)據(jù)分布離散，密度極值分布不均勻，EC算法的聚類(lèi)性能最差，NNDP和NN-DEC算法局部密度計(jì)算效率相當(dāng)，但對(duì)于距離的度量NN-DEC算法更加合理，所以NN-DEC算法聚類(lèi)效果更優(yōu)。綜上所述NN-DEC算法在UCI真實(shí)數(shù)據(jù)集上的性能是最優(yōu)的。

表5 各聚類(lèi)算法在UCI數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)對(duì)比Table 5 Comparison of evaluation metrics of various clustering algorithms on the UCI dataset

采用折線(xiàn)圖方式來(lái)直觀(guān)表達(dá)NN-DEC算法NMI值，整體上優(yōu)于其他對(duì)比算法，如圖7。

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

分別在合成數(shù)據(jù)集和UCI公共數(shù)據(jù)集上，對(duì)比不同算法在不同數(shù)據(jù)集下的時(shí)間復(fù)雜度。

圖7 算法在UCI數(shù)據(jù)集上NMI值Fig.7 Algorithm NMI values on UCI dataset

如圖8所示為7種算法在合成數(shù)據(jù)集Aggregation上運(yùn)行時(shí)間（迭代運(yùn)行30次取平均值）。

圖8 算法在A(yíng)ggregation數(shù)據(jù)集上運(yùn)行時(shí)間Fig.8 Algorithm runtime on Aggregation dataset

NN-DEC算法運(yùn)行時(shí)間效率上，比不上K-means和DBSCAN線(xiàn)性時(shí)間復(fù)雜度的算法，但是在聚類(lèi)效果上明顯優(yōu)于這兩個(gè)算法，因?yàn)樵贏(yíng)ggregation數(shù)據(jù)集上密度分布差異大，所以本文提出算法時(shí)間復(fù)雜度優(yōu)于NNDP和EC算法。

如圖9所示為7種算法在UCI數(shù)據(jù)集Wine上運(yùn)行時(shí)間（迭代運(yùn)行30次取平均值）。

圖9 算法在Wine數(shù)據(jù)集上運(yùn)行時(shí)間Fig.9 Algorithm runtime on Wine dataset

在Wine數(shù)據(jù)集上密度極值分布明顯，離群點(diǎn)容易剔除，所以本文提出算法在時(shí)間復(fù)雜度上優(yōu)于NNDP和EC算法。

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

本文提出了一種自然鄰居密度極值算法NN-DEC算法。當(dāng)數(shù)據(jù)集密度真實(shí)分布差異較大時(shí)，采用統(tǒng)一標(biāo)準(zhǔn)去篩選聚類(lèi)中心，對(duì)于低密度區(qū)域聚類(lèi)中心選取存在較大誤差，在這個(gè)基礎(chǔ)上引入連通值概念，采用連通值將數(shù)據(jù)集進(jìn)行區(qū)域劃分，使用數(shù)學(xué)上極值的概念計(jì)算密度極值，以此來(lái)找到不同區(qū)域的聚類(lèi)中心點(diǎn)，不同區(qū)域分開(kāi)進(jìn)行聚類(lèi)，最后將聚類(lèi)結(jié)果合并到一起。文中對(duì)于閾值選取以先前文獻(xiàn)的取值為基礎(chǔ)，這樣會(huì)導(dǎo)致對(duì)自己算法存在不足，在接下來(lái)工作中對(duì)于閾值選取可以提出一個(gè)模型優(yōu)化閾值參數(shù)選取。每次迭代要更新所有節(jié)點(diǎn)連通值消耗時(shí)間太久，采用隨機(jī)游走方式，計(jì)算連通值提高算法的效率?？梢栽黾右粋€(gè)空間度量值將數(shù)據(jù)按層次空間分開(kāi)，讓算法自適應(yīng)地去處理高維數(shù)據(jù)集。