基于K近鄰鏈式相似性度量的聚類算法

劉佳偉, 唐錦萍

(黑龍江大學(xué)數(shù)據(jù)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150080)

1 引言

聚類算法作為一種重要的數(shù)據(jù)分析方法應(yīng)用非常廣泛,在圖像處理[1,2],推薦系統(tǒng)[3,4],隱私保護[5,6]等方面也有著重要作用。聚類的目的在于將數(shù)據(jù)集中的樣本劃分為若干個,通常是不相交的子集,每個子集稱為一個“簇”。使得簇內(nèi)的樣本同質(zhì)性盡可能高,而不同簇樣本之間的異質(zhì)性盡可能高。

聚類算法中涉及一個基本的問題——相似性度量。通?；谀撤N形式的距離來定義“相似度度量”,距離越大則相似度越小,距離越小則越相似。

如果將聚類分為兩個階段:相似性度量階段和劃分階段,傳統(tǒng)的聚類算法中大多數(shù)采用歐式距離作為相似性度量。以K-means[7]為例,相似度量采用的是歐式距離,劃分方法采用的是比較簡單的劃分為距離最近的聚類中心。自K-means之后有眾多學(xué)者專家針對聚類過程中的劃分方法做了很多改進:Nguyen[8]提出K-modes算法,將K-means使用的歐式距離替換成字符間的漢明距離,從而應(yīng)用于非數(shù)值型的數(shù)據(jù)集上;K-medoids[9]針對K-means中聚類中心選擇會受到極端值影響的問題,改為選擇當(dāng)前簇中其它點到該中心點的距離之和最小的樣本點作為聚類中心,可以削弱異常值的影響;譜聚類[10]將聚類問題轉(zhuǎn)化為圖劃分的問題,相比K-means,它能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解,并且適用于高維數(shù)據(jù)和稀疏數(shù)據(jù);Bezdek[11]提出著名的FCM(Fuzzy C-Means)算 法,該方法是圖像分割領(lǐng)域應(yīng)用的較廣泛的聚類算法;Martin Ester[12]等人提出一種代表性的基于密度的聚類算法——DBSCAN,該方法可以利用一個樣本點ε領(lǐng)域內(nèi)鄰居點數(shù)衡量點所在空間的密度,該方法可以發(fā)現(xiàn)空間內(nèi)任意形狀的簇,也不需要事先知道聚類數(shù)目;STING[13]是一種基于網(wǎng)格的多分辨率聚類技術(shù),它將空間區(qū)域劃分為矩形單元。針對不同級別的分辨率,通常存在多個級別的矩形單元,這些單元形成了一個層次結(jié)構(gòu):高層的每個單元被劃分為多個低一層的單元。Brendan J[14]等人于2007年提出Affinity Propagation(近鄰傳播)算法,該方法將全部的樣本點當(dāng)作潛在的聚類中心,數(shù)據(jù)點兩兩之間連線構(gòu)成一個網(wǎng)絡(luò)(相似度矩陣),再通過網(wǎng)絡(luò)中各條邊的消息(responsibility和availability)傳遞計算出各樣本的聚類中心;Alex Rodriguez和Alessandro Laio[15]于2014年提出密度峰值聚類算法,該方法為了查找聚類中心,假設(shè)類簇中心點的密度大于周圍鄰居點的密度、類簇中心點與更高密度點之間的距離相對較大。

上述的這些方法,都是在聚類的劃分過程中不斷改進,但是相似性度量依然是基于歐式距離或者是其它傳統(tǒng)的度量。在近些年,有部分學(xué)者關(guān)注到數(shù)據(jù)之間的非獨立同分布的性質(zhì),針對數(shù)據(jù)間相似性度量做出改進并將其應(yīng)用于聚類算法中,取得了不錯的效果:Songlei Jian[16]等人認為樣本的屬性聯(lián)系可以反映樣本之間的非獨立同分布性質(zhì),提出了CMS相似性度量方法,該方法從樣本的屬性出發(fā)計算樣本之間的相似性,將其應(yīng)用于譜聚類和K-modes聚類取得了良好的效果,但該方法復(fù)雜度過高;夏春夢[17]等人提出一種基于密度調(diào)整和流形距離的近鄰傳播算法,在近鄰傳播算法的基礎(chǔ)上改進了距離度量,使用最短路徑概念度量兩個樣本點之間的相似度;古凌嵐[18]將密度和流形概念引入K-means算法中,利用K近鄰來刻畫樣本點之間的相似性;溫愛紅[19]將將明可夫斯基和切比雪夫距離引入AP聚類中,取得了良好的聚類效果。

在改進相似性度量過程中,zhou[20]等人提出相似性度量要考慮數(shù)據(jù)的全局一致性和局部一致性,認為數(shù)據(jù)對象的相似性必須滿足以下兩個一致性條件:

1)局部一致性:如果兩個數(shù)據(jù)點在空間位置上相鄰, 這兩個數(shù)據(jù)點很可能屬于同一類。

2)全局一致性:若兩個數(shù)據(jù)點處在同一流形,這兩個數(shù)據(jù)點屬于同一類的可能性比較大。

在傳統(tǒng)的聚類算法中,大都采用了歐式距離或歐氏距離的簡單轉(zhuǎn)換作為樣本間的相似性度量,這種方法在部分數(shù)據(jù)集中是可行,但是在一些具有特殊結(jié)構(gòu)的數(shù)據(jù)集中則無法很好的反應(yīng)樣本點之間的全局一致性,下面以一個簡單的例子說明。

如圖1所示,在歐式距離的度量下,顯然點a,c之間的距離Euclid(a,c)大于點a,b之間的距離Euclid(a,b),但是可以直觀的從圖中看出實際上a,c是屬于同一簇而a,b分屬于不同簇。由此可見,若根據(jù)歐式距離來進行后續(xù)的聚類過程,則會出現(xiàn)錯誤。針對這種情況本文提出一種新的距離度量,這種距離是在歐式距離的基礎(chǔ)上通過構(gòu)建近鄰鏈來計算的,該方法在部分歐式距離無法適用的數(shù)據(jù)集上可以準確的反映數(shù)據(jù)間的全局一致性。基于改良距離度量的K-medoids[9],Affinity Propagation[14](AP)算法在仿真中取地了良好的聚類結(jié)果。

圖1 歐式距離存在的問題

2 基于密度和近鄰的鏈式距離

2.1 鏈式距離度量

從圖1的例子出發(fā),根據(jù)密度峰值聚類[15]中的理論,引入密度的定義:對于數(shù)據(jù)集中樣本點i,i的密度為距離度量下與i距離小于ε的樣本點的數(shù)目之和。其中ε為人為設(shè)定的閾值。在密度的基礎(chǔ)上文獻[15]提出了這樣一種假設(shè):

假設(shè):在歐式距離度量下,數(shù)據(jù)集內(nèi)同一簇樣本點位于高密度區(qū)域,不同簇之間由低密度區(qū)域分割開來。其中高密度區(qū)域即該區(qū)域內(nèi)的樣本點的密度值較大。

在這樣的假設(shè)下,基于歐式距離從數(shù)據(jù)集中任一樣本點出發(fā),檢索距離其最近的一個樣本點,當(dāng)檢索到的樣本點與該點處于同一簇時,兩樣本之間的歐式距離會比較小,這是因為數(shù)據(jù)集內(nèi)同一簇樣本點位于高密度區(qū)域。再將檢索到的樣本點作為新的出發(fā)點,從未遍歷過的點集合中檢索下一個距離其最近的點,根據(jù)該方法逐個檢索直到遍歷完該簇所有點時,下一個點則會檢索到距最后一個本簇點最近的一個異簇點,根據(jù)假設(shè),此時這兩個點之間的距離較大。根據(jù)這樣的特性,考慮下面一種距離度量方法:從數(shù)據(jù)集中任一樣本點出發(fā),逐個搜索未遍歷過的最近樣本點直到遍歷完數(shù)據(jù)集內(nèi)所有樣本點。根據(jù)此遍歷結(jié)果將得到一條有序長鏈,將初始點到鏈上任一點的鏈式距離置為初始點到該點的子鏈中任一相鄰兩點的歐氏距離中最大值。由此可以得到初始點到數(shù)據(jù)集中任一樣本點之間的鏈式距離。具體見如下定義:

定義1(最近鄰鏈):設(shè)有數(shù)據(jù)集D,D中樣本數(shù)量為n,di為數(shù)據(jù)集中任意一個樣本點,下面定義中用Ci表示di的最近鄰鏈,并記Ci(k)為該鏈上的第k個樣本點,則Ci滿足以下條件:

1)以di為初始點,即:Ci(1)=di．

2)Ci長度為n,且包含數(shù)據(jù)集D中全部的樣本點。

3)鏈Ci上的第k個樣本點,由下式確定

(1)

由式(1),Ci上的第k個樣本點Ci(k)即是第k-1個點與未遍歷過的樣本點的歐氏距離的取得最小值時所對應(yīng)的樣本點

定義2(最近鄰鏈式距離)設(shè)有數(shù)據(jù)集D,D中樣本點di有最近鄰鏈Ci,dj為Ci上一個樣本點,且i≠j,則di到dj的鏈式距離

CD(i,j)=max(Euclid(Ci(q),Ci(q+1)))

在理想狀態(tài)下,應(yīng)該遍歷完一個簇再轉(zhuǎn)移到另一個簇,這樣同一簇點之間的鏈式距離小,而不同簇之間點的距離大,然而在實驗中發(fā)現(xiàn)這樣的方法存在一個嚴重問題即:一個簇未遍歷完就會轉(zhuǎn)移到另一個簇,以圖2為例,存在下面這種問題:

圖2 最近鄰搜索存在的問題

問題 圖2中有A,B兩簇,假設(shè)選擇a點出發(fā),每一次尋找最近鄰點,則會經(jīng)過b,c,但是到d點時,下一步則會檢索到距離點d最近的B簇的點e,這會導(dǎo)致A簇的已經(jīng)遍歷的樣本點與A簇未遍歷的樣本點之間的鏈式距離發(fā)生錯誤。不能正確的反映數(shù)據(jù)的全局一致性。

針對這樣的問題,參考在梯度下降法中陷入局部最優(yōu)的問題的部分解決方法——擴大搜索步長、選擇多起點搜索,采用了下面兩種方法來解決:

方法1:在定義1中,最近鄰鏈的定義通過檢索距離當(dāng)前點最近的點來得到的,考慮“擴大搜索步長”的方法:將檢索最近鄰點改為檢索距離當(dāng)前點最近的K個點,后從K個點中隨機選擇一個點作為下一次檢索的起點。

方法2:在方法1的基礎(chǔ)上,最近鄰鏈式距離定義發(fā)生了改變,因為此時鏈式距離不再是穩(wěn)定的。同時考慮引入“多起點檢索”的方法:將a,b之間的最終的鏈式距離置為a到b的鏈式距離和b到a之間中的較小的那個,這樣可以進一步緩解問題。同時將鏈式距離矩陣轉(zhuǎn)化為對稱矩陣。

在提出的方法1和方法2的基礎(chǔ)上,基于K近鄰的方法將最近鄰鏈的定義改進為K近鄰鏈,并得到最終的K近鄰鏈式距離的定義:

定義3(K近鄰鏈):設(shè)有數(shù)據(jù)集D,D中樣本數(shù)量為n,di為數(shù)據(jù)集中任意一個樣本點,下面定義中用CKi表示di的K近鄰鏈,并記CKi(k)為該鏈上的第k個樣本點,則CKi滿足以下條件:

1)以di為初始點,即:CKi(1)=di．

2)CKi長度為n,且包含數(shù)據(jù)集D中全部的樣本點。

3)記NK(CKi(k-1))表示歐式距離中K近鄰意義下CKi(k-1)的K個近鄰點的集合

其中K-argmin表示使得歐式距離最小的K個樣本點。

4)在3)給出的K近鄰點集的基礎(chǔ)上,CKi(k)服從NK(CKi(k-1))中K個點的均勻分布,即

其中j∈NK(CKi(k-1)),因此可以同等的概率隨機的選取K近鄰點集中某一個點作為CKi(k)。

定義4(K近鄰鏈式距離):設(shè)有數(shù)據(jù)集D,D中樣本點di有K近鄰鏈CKi,dj為CKi上一個樣本點,且i≠j,則di到dj的K近鄰鏈式距離為

CKd(i,j)=max(Euclid(CKi(q),CKi(q+1)))

CKD(i,j)=min(CKd(i,j),CKd(j,i))

2.2 全局性距離變換

在鏈式計算鏈式距離度量之前采用了指數(shù)函數(shù)來對歐式距離進行變換。

Euclid′(x,y)=γEuclid(x,y)-1

其中γ>1為放大系數(shù)。

根據(jù)指數(shù)函數(shù)的性質(zhì),在(01時,ax的函數(shù)曲線呈凹性遞增。歐式距離經(jīng)過指數(shù)變換后,距離矩陣中較大值大幅增大,而距離較小值小幅增大,從而擴大了較大距離和較小距離的差異。這可以擴大鏈式距離下簇間距離和簇內(nèi)距離的差異。

2.3 鏈式距離計算

根據(jù)2.1和2.2節(jié)的論述,總結(jié)計算鏈式距離的完整過程如下:

輸入:數(shù)據(jù)集D,D的歐式距離矩陣 Euclid-based Matrix(EM),參數(shù)K

輸出:數(shù)據(jù)集的鏈式距離矩陣 Chained-based Matrix(CM)

1)利用式EM′(x,y)=γEM(x,y)-1對歐式距離矩陣做變換。

2)選擇數(shù)據(jù)集中第一個樣本點d1作為start point(sp)并記錄。

3)在EM′中,尋找K近鄰意義下sp的K個未記錄過的近鄰點的集合,在該點集中隨機選擇一個點作為next point(np)。

當(dāng)未記錄點數(shù)不足K個時,則在未記錄點中隨機選擇一個作為np。

4)記錄當(dāng)前np,將當(dāng)前np點作為新sp,重復(fù)步驟3)直至數(shù)據(jù)集中所有樣本點均被記錄,則得到一條以d1為起點遍歷所有樣本點的長鏈即d1的K近鄰鏈CK1。

5)根據(jù)K近鄰鏈式距離定義根據(jù)計算d1到D中任意一點dj的K近鄰鏈式距離CKd(1,j)

6)依次選擇數(shù)據(jù)集中所有點作為sp,重復(fù)步驟3)、5),計算得到數(shù)據(jù)集D中任意兩點之間的鏈式距離。

7)通過

CKD(i,j)=min(CKd(i,j),CKd(j,i))

計算得到D的鏈式距離矩陣CM

2.4 復(fù)雜度分析

當(dāng)數(shù)據(jù)集共有n個樣本點時,鏈式計算距離度量需要分別從每個樣本點出發(fā)根據(jù)一定規(guī)則尋找到一條長鏈。

當(dāng)每次尋找下一個點為當(dāng)前點的K近鄰點集中的隨機一個點時,復(fù)雜度為O(n),那么尋找一條鏈的復(fù)雜度為O(n2), 則尋找n條鏈的復(fù)雜度為O(n3)。

3 基于鏈式距離的聚類算法

3.1 鏈式距離與已有聚類算法的結(jié)合

在使用鏈式距離改進了聚類算法中的相似性度量后,下一步需要根據(jù)相似性度量來劃分數(shù)據(jù)集?，F(xiàn)有的聚類算法中提出了各種各樣的劃分方法,但是并不是所有劃分方法都可以應(yīng)用于鏈式距離上來對數(shù)據(jù)進行聚類,這是由鏈式距離的計算特性決定的。

以K-means為例,在K-means算法的聚類過程中,每一輪迭代,都將選取每一簇的樣本點均值作為新的聚類簇中心,然后根據(jù)樣本點到聚類中心的距離來劃分該樣本點的類別。顯然,這樣選取的聚類中心大多數(shù)情況下都不在給定的樣本點中,因此,每一輪劃分,都需要重新計算聚類中心到其它所有樣本點的距離。

當(dāng)使用傳統(tǒng)距離時,聚類中心和其它點的距離可以直接計算,若用鏈式距離替換傳統(tǒng)歐式距離,那么計算聚類中心到其它樣本點的鏈式距離的過程將十分耗時,算法復(fù)雜度大大增加。

所以,考慮鏈式距離與劃分方法的結(jié)合時,應(yīng)優(yōu)先選擇基于距離矩陣,或者聚類中心仍然屬于樣本之一的聚類方法,比如K-medoids算法、Affinity Propagation算法、譜聚類方法。

3.2 K-medoids和Affinity propagation算法

在后續(xù)的實驗部分,本文選擇鏈式距離分別與K-medoids和Affinity propagation算法結(jié)合,一是因為這兩種方法都是基于距離矩陣對數(shù)據(jù)集進行劃分的,可以充分利用鏈式距離矩陣;二是因為這兩種方法對于具有明顯流形結(jié)構(gòu)的數(shù)據(jù)聚類效果不理想。下面簡述K-medoids算法和Affinity propagation算法的原理。

3.2.1 基于鏈式距離的K-medoids方法

K-medoids聚類是在K-means聚類基礎(chǔ)上的改進。它們都對聚類中心進行迭代,區(qū)別在于K-means算法中,各個簇的聚類中心的計算采用的是簇內(nèi)所有點的質(zhì)心,也就是簇內(nèi)各個樣本點的平均值,由此所計算出來的聚類中心可以是連續(xù)空間中的任意值,而非已存在的樣本點。與此不同,K-medoids算法中每一輪迭代的聚類中心一定是數(shù)據(jù)集中的樣本點。

在后續(xù)的K-medoids聚類實驗中,將算法中的歐式距離矩陣替換為鏈式距離矩陣后,算法的基本流程如下:

1)在樣本點中隨機選擇K個聚類中心

2)根據(jù)鏈式距離矩陣計算各個樣本點到聚類中心的距離

3)將每個樣本點劃分到距離其最近的聚類中心,形成K個簇C1…CK。

則

5)重復(fù)步驟2),3),直到滿足迭代次數(shù)或誤差小于指定的值。

3.2.2 基于鏈式距離的Affinity Propagation方法

Affinity Propagation(AP)聚類是一種基于圖論的聚類, 它根據(jù)樣本點之間的相似度進行聚類,這些相似度構(gòu)成了所有樣本點的相似度矩陣S,一般情況下相似度采用負的歐式距離表示。

AP聚類不需要人為指定簇的數(shù)目,它將所有樣本點視為潛在的聚類中心,根據(jù)S主對角線上的值s(i,i)來判斷樣本點i是否可以成為聚類中心,該值越大,i成為聚類中心的可能越大,該值稱為p值。若所有樣本的p值相同,則所有樣本成為聚類中心的可能性相等,樣本的p值影響聚類得到的簇的數(shù)目,p值越大得到的簇越多,如果選擇輸入相似度矩陣的均值作為p的值則得到的簇的數(shù)目中等。

在樣本點構(gòu)成的網(wǎng)絡(luò)中傳遞兩種類型的消息(responsiility和availability)。r(i,k)表示k是否適合做點i的聚類中心,a(i,k)則表示i是否選擇k作為其聚類中心。r(i,k)與a(i,k)的和越大,表示k作為聚類中心的可能性就越大。所有樣本點的r(i,k)與a(i,k)構(gòu)成了吸引度矩陣R和歸屬度矩陣A。為了控制收斂速度,算法還設(shè)置有阻尼因子(damping factor),用λ表示。AP 算法通過迭代不斷更新每一個點的吸引度和歸屬度值,直到收斂或達到最大迭代次數(shù)心,然后將樣本點分配到相應(yīng)的聚類中心。

在后續(xù)的AP聚類實驗中,本文采用負的鏈式距離來表示樣本點的相似度矩陣S,聚類算法基本流程如下:

1)計算負的鏈式相似度矩陣S,設(shè)置參考度p、初始化吸引度矩陣R和歸屬度矩陣A。

2)根據(jù)下面公式更新吸引度矩陣R,其中

3)根據(jù)下面公式更新歸屬度矩陣A

at+1(i,k)

4)根據(jù)下式利用阻尼因子λ對矩陣R和A進行修正

5)重復(fù)步驟2),3),4)直到收斂或達到最大迭代次數(shù)。然后通過下式將樣本點i劃分到對應(yīng)的聚類中心ci

ci=arg maxk(r(i,k)+a(i,k))．

4 實驗

為了證明本文所提出的鏈式距離的有效性,分別在人工數(shù)據(jù)集和UCI數(shù)據(jù)集下做了對比實驗。

在八個二維和三維人工數(shù)據(jù)集下分別計算歐式距離,切比雪夫距離,曼哈頓距離,最短路徑距離[17]和鏈式距離,對比在不同距離度量下組內(nèi)距離和組間距離的差異。將這五種距離度量結(jié)合K-medoids聚類和Affinity Propagation聚類算法,采用FMI(Fowlkes-Mallows Index)評分作為評價標準對比在八個人工數(shù)據(jù)集上的聚類性能。

在UCI 數(shù)據(jù)集中,選擇了四個聚類算法-DBSCAN,Affinity propagation,K-medoids和Agglomerative層次聚類,分別在歐式距離和鏈式距離下通過這四種算法進行聚類,采用FMI評分作為評價標準對比不同算法在UCI數(shù)據(jù)集上的聚類表現(xiàn)。

4.1 數(shù)據(jù)集和算法參數(shù)設(shè)置

4.1.1 數(shù)據(jù)集

表1和表2分別列出了人工數(shù)據(jù)集和UCI數(shù)據(jù)集的基本信息,包括樣本點數(shù)目,特征維數(shù)和聚類數(shù)目。圖3、圖4和圖5為人工數(shù)據(jù)集中四個數(shù)據(jù)集的散點圖,其中兩個為二維數(shù)據(jù)集,兩個為三維數(shù)據(jù)集,可以看到樣本點的分布具有明顯的流形結(jié)構(gòu)。

表1 人工數(shù)據(jù)集基本信息

表2 UCI數(shù)據(jù)集基本信息

圖3 三維數(shù)據(jù)集swiss＿roll

圖4 三維數(shù)據(jù)集two＿hemisphere

圖5 二維數(shù)據(jù)集two＿moons、smile

4.1.2 參數(shù)設(shè)置

最短路徑距離參數(shù):放大系數(shù)γ=e。

鏈式距離參數(shù):放大系數(shù)γ=e,K=e。

K-medoids算法:給定正確的聚類數(shù)目,初始聚類中心隨機選擇,每次計算迭代300次,取10次計算結(jié)果的FMI的均值作為最終結(jié)果。

Affinity Propagation算法參數(shù):選擇較小步長在一定范圍內(nèi)逐次選擇不同的參考度p和阻尼因子λ,選擇最佳聚類結(jié)果作為最終結(jié)果。

Agglomerative層次聚類算法參數(shù):給定正確的聚類數(shù)目,判斷兩簇距離的方式的參數(shù)linkage選擇average。

DBSCAN算法參數(shù):選擇較小步長在一定范圍內(nèi)逐次選擇不同的ε-鄰域距離閾值eps和判斷樣本點是核心對象所需的ε-鄰域的樣本數(shù)閾值min＿samples,選擇最佳聚類結(jié)果作為最終結(jié)果。

FMI評分:FMI是對聚類結(jié)果和真實值計算得到的召回率和精確率,進行幾何平均的結(jié)果,取的值范圍為 [0,1],越接近1越好。具體的計算方法如下

其中TP是真正例(True Positive),即真實標簽和預(yù)測標簽屬于相同簇類的樣本對個數(shù);FP是假正例(False Positive),即真實標簽屬于同一簇類,相應(yīng)的預(yù)測標簽不屬于該簇類的樣本對個數(shù);FN是假負例(False Negative),即預(yù)測標簽屬于同一簇類,相應(yīng)的真實標簽不屬于該簇類的樣本對個數(shù)。

4.2 人工數(shù)據(jù)集實驗

4.2.1 距離矩陣對比

表3列出了不同距離度量下中簇間距離均值和簇內(nèi)距離均值的比值,表4和表5分別列出簇內(nèi)和簇間距離的方差。需要說明的是,為方便計算對比,本文只比對了8個數(shù)據(jù)集中6個2分類和3分類數(shù)據(jù)集。

表3 組間/組內(nèi)距離均值的比

表4 組內(nèi)距離方差均值

可以看到,與其它幾種距離度量相比,鏈式距離度量在這幾個數(shù)據(jù)集中尤其是具有環(huán)狀結(jié)構(gòu)的數(shù)據(jù)集two＿circles和smile中,明顯擴大了組間和組內(nèi)距離的差異,并且降低了組間、組內(nèi)距離的方差,更好的反映出數(shù)據(jù)集的全局一致性。

4.2.2 聚類結(jié)果對比

表6和表7分別列出了K-medoids算法和AP聚類算法的FMI評分,可以看出,不論是在K-medoids聚類還是AP聚類中,相比于其它四種距離度量,基于鏈式距離的聚類均取得了更優(yōu)的結(jié)果,這也符合4.1節(jié)中對于距離矩陣的對比結(jié)果,說明鏈式距離在這種具有明顯非凸特性的數(shù)據(jù)集上相比傳統(tǒng)的距離度量可以更好的反映樣本點之間的全局一致性。

表6 K-medoids聚類FMI

表7 AP聚類FMI

4.3 UCI數(shù)據(jù)集實驗

表8分別列出了4個UCI數(shù)據(jù)集下,4種聚類算法分別基于歐氏距離和鏈式距離聚類的FMI評分,為了區(qū)別起見,基于歐式距離的算法使用E標識,使用鏈式距離的算法使用C標識,比如E-DBSCAN表示基于歐式距離的DBSCAN算法,C-DBSCAN表示基于鏈式距離的DBSCAN算法,其它依次。可以看到在Iris數(shù)據(jù)集中,使用歐式距離的聚類算法得到的結(jié)果均要優(yōu)于使用鏈式距離的,而在其它三個數(shù)據(jù)集中,使用鏈式距離得到的聚類結(jié)果持平或者小幅優(yōu)于基于歐式距離得到的聚類結(jié)果。

表8 基于歐氏距離和鏈式距離聚類FMI

通過這幾組對比實驗可以看到,鏈式距離和歐式距離在沒有明顯非凸特性的數(shù)據(jù)集上,對于數(shù)據(jù)集的全局一致性的反映程度接近。但鏈式距離的計算復(fù)雜度高于計算歐氏距離,并且鏈式距離魯棒性較差,容易受到噪聲影響。

5 結(jié)論

在本文中,從K-means方法存在的缺陷出發(fā),針對歐式距離在非凸數(shù)據(jù)集中不能很好反應(yīng)全局一致性的問題上,提出一種基于歐式距離的鏈式計算的新型距離度量。在具有明顯非凸特性的人工數(shù)據(jù)集中,在傳統(tǒng)K-medoids聚類,AP聚類中使用本文所提出的距離度量方法得到了明顯優(yōu)于傳統(tǒng)距離度量的聚類效果。但是在沒有明顯非凸特性的UCI數(shù)據(jù)集中該方法相比歐式距離并沒有明顯優(yōu)勢。另外也顯示了該方法存在以下幾個缺陷:①該方法容易受到噪聲的影響②該方法的復(fù)雜度較高。接下來的研究工作是進一步優(yōu)化算法以減少距離矩陣的計算時間,以及針對具有不明顯凸特性的一般數(shù)據(jù)集提升算法的聚類效果。