張忠林,趙 昱,閆光輝
蘭州交通大學(xué) 電子與信息工程學(xué)院,蘭州 730000
數(shù)據(jù)聚類(lèi)把數(shù)據(jù)對(duì)象按照不同屬性分割成確定數(shù)目的同質(zhì)子集,每個(gè)同質(zhì)子集貼上屬性標(biāo)簽后稱(chēng)之為類(lèi)簇。對(duì)于任何一個(gè)類(lèi)簇滿足簇內(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為文章所定義數(shù)據(jù)符號(hào)和算法縮寫(xiě)摘要。
表1 符號(hào)摘要Table 1 Summary of notations
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所示,以歐式距離度量數(shù)據(jù)對(duì)象a和b之間的相似性,因距離較近則兩個(gè)數(shù)據(jù)對(duì)象相似性較高,可劃分到同一個(gè)簇中。但在數(shù)據(jù)集實(shí)際分布中a和c處在同一簇中,因此歐氏距離度量準(zhǔn)則在該數(shù)據(jù)集中的度量誤差較大,同時(shí)不滿足上述聚類(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)所示:
數(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(離群點(diǎn)[18])觀察一組數(shù)據(jù)對(duì)象,存在異于這組觀察值的數(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)。
自然鄰居[20]是一種無(wú)參的近鄰概念,提出的目的是解決k-最近鄰[21-22]中參數(shù)選擇問(wèn)題。
定義3(自然穩(wěn)定結(jié)構(gòu)[23])xi存在鄰居為xj,同時(shí)xj也存在鄰居為xi,若滿足上述條件則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)。
根據(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)整因子采用線性方式計(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)。
根據(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)。
為了驗(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)效果明顯。
本節(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算法在Aggregation、Jain、Flame、Spiral上緊湊結(jié)果Fig.4 Compact results of NN-DEC algorithm on Aggregation,Jain,F(xiàn)lame,Spiral
圖5 NN-DEC和DPC算法在Aggregation、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ì)比的算法。具體分析:在Aggregation數(shù)據(jù)集上因?yàn)閿?shù)據(jù)分布廣且密度分布不均勻,因此NN-DEC算法在上面聚類(lèi)效果是最佳的,NNDP算法的性能要優(yōu)于EC算法,因?yàn)閿?shù)據(jù)點(diǎn)密度分布較為均勻,EC算法在Aggregation數(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ò)的效果。
采用折線圖方式來(lái)直觀表達(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算法。
本節(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
采用折線圖方式來(lái)直觀表達(dá)NN-DEC算法NMI值,整體上優(yōu)于其他對(duì)比算法,如圖7。
分別在合成數(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 算法在Aggregation數(shù)據(jù)集上運(yùn)行時(shí)間Fig.8 Algorithm runtime on Aggregation dataset
NN-DEC算法運(yùn)行時(shí)間效率上,比不上K-means和DBSCAN線性時(shí)間復(fù)雜度的算法,但是在聚類(lèi)效果上明顯優(yōu)于這兩個(gè)算法,因?yàn)樵贏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算法。
本文提出了一種自然鄰居密度極值算法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ù)集。