基于距離和密度的PBK-means算法

魏文浩,唐澤坤,劉 剛

(蘭州大學 信息科學與工程學院,蘭州 730000)

0 概述

數(shù)據(jù)挖掘是指從大量的數(shù)據(jù)中通過算法搜索隱藏于其中信息的過程,已廣泛應(yīng)用于大中型企業(yè)、軍事、銀行、醫(yī)學等領(lǐng)域[1]。聚類是數(shù)據(jù)挖掘中將物理或抽象對象的集合分成由類似的對象組成的多個類的方法。由聚類所生成的簇是一組數(shù)據(jù)對象的集合,這些對象與同一個簇中的對象彼此相似,與其他簇中的對象相異[2]。在自然科學和社會科學中[3],存在著大量的分類問題。

在現(xiàn)實世界中存在著越來越多的無標簽數(shù)據(jù),因此使用無監(jiān)督學習方法解決問題就顯得非常重要[4],而無監(jiān)督學習中的聚類則可以利用數(shù)據(jù)自身特征對無標簽數(shù)據(jù)進行分類。文獻[5]提出一種基于簡單觀測的迭代方法,由數(shù)據(jù)集導(dǎo)出K個簇的質(zhì)心作為中心點,即K-means聚類算法。K-means算法因思想較為簡單且易實現(xiàn)的特點,成為應(yīng)用最廣泛的聚類算法[6],它將距離作為相似度把數(shù)據(jù)集分為若干個類[7-8],在同一類中,數(shù)據(jù)間的相似度更高,在不同的類中,數(shù)據(jù)間的相似度更低。但是K-means算法也有局限性,如算法初始中心設(shè)置的隨機性使聚類結(jié)果易陷入局部最優(yōu)解,并且聚類結(jié)果不穩(wěn)定,易受噪聲點影響。

近年來,研究人員提出了很多新的聚類算法,其中多數(shù)是對于K-means算法初始聚類中心選擇的優(yōu)化。文獻[9]通過將數(shù)據(jù)集劃分為幾個最佳子集,然后在每個子集選擇中心點,解決了K-means算法中心點選擇的隨機性問題,但中心點的合理性取決于數(shù)據(jù)集劃分的好壞。文獻[10]將數(shù)據(jù)集存儲在kd-tree中,根據(jù)距離選擇中心點,未考慮密度對聚類效果的影響。除使用kd-tree減小算法時間復(fù)雜度外,R*-tree[11]和X-tree[12]也被用來存儲數(shù)據(jù)集,但也相應(yīng)地增加了空間復(fù)雜度。文獻[13]提出基于統(tǒng)計相關(guān)性的區(qū)分因子算法,通過引入Pearson指標[14]決定聚類過程,可以自動確定簇數(shù),但多次BWP指標的計算增加了算法時間復(fù)雜度。文獻[15-17]提出了WK-means算法,該算法通過特征加權(quán)[18]選擇中心點,考慮了數(shù)據(jù)特征對聚類效果的影響,但是沒有考慮特征值的尺度和特征權(quán)重之間的直接關(guān)系,因此文獻[19]提出MWK-means算法,采用異常簇初始化的方法解決上述問題,但當數(shù)據(jù)集更加復(fù)雜時,MWK-means算法需要更多時間進行特征加權(quán)。文獻[20]提出一種鄰聚類算法,利用圖熵的概念可以對復(fù)雜數(shù)據(jù)集進行有效聚類,DBSCAN[21]和OPTICS[22]根據(jù)密度選擇核心對象進行聚類分析,但這3種算法都對閾值的設(shè)定存在一定敏感性。2014年,《Science》雜志發(fā)表一篇基于密度峰值的快速聚類算法[23],但沒有給出明確的閾值設(shè)定,文獻[24]提出了DCK-means算法,利用數(shù)據(jù)集特征選擇初始聚類中心,參數(shù)設(shè)置更加合理,但當數(shù)據(jù)集規(guī)模變大時算法時間復(fù)雜度會大幅提升。

針對以上問題,本文提出一種PBK-means算法。該算法考慮密度和距離對聚類效果的影響,將得到的初始聚類中心作為K-means算法的輸入?yún)?shù),解決K-means算法易陷入局部最優(yōu)解和抗噪能力差的問題。同時采用構(gòu)造滿二叉樹的方法并行產(chǎn)生聚類中心,以降低算法的時間復(fù)雜度。

1 相關(guān)算法

Bisecting K-means算法是一種無監(jiān)督學習算法,由STEINBACH、KARYPIS和KUMAR于2000年提出,該算法通過對待切分簇的選擇和切分結(jié)果的優(yōu)選來獲得高質(zhì)量的初始聚類中心。如圖1～圖3所示,為了得到K個簇,將數(shù)據(jù)集所有點作為一個簇,放入簇表中,不斷地從簇表中選擇簇使用K-means算法進行二分聚類,從所有二分實驗中選取具有最小SSE值和的2個簇,更新簇表,直到產(chǎn)生K個簇。

圖1 K-means算法二分聚類步驟1

圖2 K-means算法二分聚類步驟2

圖3 K-means算法二分聚類步驟3

算法1二分K-means算法

輸入數(shù)據(jù)集D,聚類數(shù)K

輸出聚類結(jié)果

1.initialize the Array List

2.compute the center S of mass of D

3.add S to the central point sets C

4.WHILE(size of C

5. FOR(each sample i∈C){

6. K-means(Di,2)

7. get the data sets Di1,Di2belonging to i1,i2

8. compute the SSE values of D

9. }END FOR

10. select j1,j2with minimum SSE values

11. remove j in sets C

12. add j1,j2to sets C

13.}END WHILE

14.PRINT(sets C,D after classification)

算法具體步驟如下:

步驟1給定聚類數(shù)K和數(shù)據(jù)集D={x1,x2,…,xn}。

步驟2計算D的質(zhì)心,并把它加入中心點集合C中。

步驟3遍歷C中的全部中心點,使用K-means算法將每個中心點代表的類分為兩類,并計算分類后數(shù)據(jù)集D的SSE值的和。

步驟4選擇SSE值最小的簇群,用新生成的兩個中心點覆蓋C中的生成這兩類的中心點。

步驟5重復(fù)步驟3和步驟4,直至得到K個中心點。

對于含有K個中心點的集合C,ci為簇Ci的聚類中心,x為該簇中的一個樣本,d(x,ci)表示x與ci之間的歐氏距離,SSE指標的計算公式為:

SSE指標的計算增加了算法時間開銷,同時,使用K-means算法將簇一分為二會受到K-means算法隨機性的影響,不能保證收斂到全局最優(yōu)值。因此,本文提出一種基于距離和密度的并行二分K-means算法,取消了SSE指標的計算,加入權(quán)重的概念,在保持數(shù)據(jù)集空間劃分合理性的前提下解決了中心點選擇的隨機性問題。

2 PBK-means算法

2.1 基本定義

對于給定數(shù)據(jù)集D={x1,x2,…,xn},每個樣本元素可表示為xm={xm1,xm2,…,xmr},1≤m≤n,其中,r是樣本元素的維度,d(xi,xj)代表樣本元素xi和xj之間的歐氏距離。

定義1數(shù)據(jù)集D的平均樣本距離定義為[24]:

(1)

定義2數(shù)據(jù)集D的特征空間大小定義為:

(2)

其中,maxi和mini分別代表數(shù)據(jù)集第i個特征上的最大值和最小值。

定義3樣本元素i的密度參數(shù)定義為[25]:

(3)

定義4觀察式(3)很容易發(fā)現(xiàn)p(i)是以數(shù)據(jù)樣本i為圓心,以MeanDis(D)為半徑的圓內(nèi)的數(shù)據(jù)樣本數(shù)量。計算數(shù)據(jù)樣本i與圓內(nèi)全部數(shù)據(jù)樣本的距離,結(jié)合數(shù)據(jù)集特征空間大小,樣本元素i的距離參數(shù)定義為:

(4)

定義5樣本元素i的異類參數(shù)定義為:

(5)

其中,m是密度參數(shù)大于樣本數(shù)據(jù)i的樣本數(shù)據(jù)數(shù)量。

定義6樣本元素i的權(quán)重定義為:

(6)

其中,w(i)的大小與p(i)和a(i)成正比,與t(i)成反比。t(i)與a(i)的設(shè)定相對文獻[24]的參數(shù)設(shè)定進行改進,利用Range參數(shù)將每個數(shù)據(jù)對t(i)的貢獻度控制在[1,1+r]之間,a(i)計算了密度參數(shù)比i大的全部數(shù)據(jù)點與i的平均距離,規(guī)范化密度和距離對聚類的影響,考慮了全局的數(shù)據(jù)點分布,有利于發(fā)現(xiàn)全局最優(yōu)而不是局部最優(yōu)。p(i)值越大,點i的MeanDis(D)半徑內(nèi)的點越多,t(i)值越小,點i的MeanDis(D)半徑內(nèi)的點越密集,a(i)值越大,兩個以MeanDis(D)為半徑的圓差異越大。因此,每次根據(jù)權(quán)值w選取下一個中心點可以保證數(shù)據(jù)集空間劃分合理性,同時,p(i)的設(shè)定可以明顯提高算法的抗噪能力。

2.2 并行二分原則

首先將數(shù)據(jù)集一分為二得到兩個簇,然后以每個簇為起點再一分為二,如此重復(fù),第r次獲得2r個簇,此過程與細胞分裂過程類似。細胞分裂式的二分給予每個簇均等的切分機會,每次迭代都要對所有的簇進行切分,這個過程可以并行實現(xiàn),最后會產(chǎn)生一棵完全二叉樹。

顯然,對于K=2r的數(shù)據(jù)集,PBK-means算法可以直接得到結(jié)果,對于2r-1

雖然都采用了二分思想,但二分K-means算法與本文提出的算法差別依舊明顯,二分K-means算法通過計算SSE值確定要切分的簇,每次迭代只切分一個簇,完成聚類需要多次計算SSE值,增加了時耗。PBK-means算法通過結(jié)合權(quán)值保證每次對簇的切分都得到較好的效果,第r次迭代同時對2r-1個簇進行切分,同時并行實現(xiàn)的特點使本文算法的執(zhí)行時間大幅減少。

2.3 最大權(quán)重原則

根據(jù)式(6)計算樣本的權(quán)重,如果滿足條件max(p(i)/t(i)),則將樣本元素i作為第1個聚類中心,計算所有樣本元素與當前聚類中心的距離,小于MeanDis(D)的樣本元素不能參與下一次聚類中心的選擇,將此距離與權(quán)重相乘,選擇相乘后最大值樣本元素作為第2個聚類中心。通過產(chǎn)生的2個中心點生成2個簇,然后對產(chǎn)生的全部子簇重復(fù)上述過程,在迭代過程中不斷更新子簇的MeanDis(D),直到產(chǎn)生的子簇數(shù)大于或等于需要的類數(shù)K。通過最大權(quán)重選擇中心點的并行二分方法步驟如圖4和圖5所示。

圖4 本文算法并行二分方法步驟1

圖5 本文算法并行二分方法步驟2

算法2PBK-means算法

輸入數(shù)據(jù)集D,聚類數(shù)K

輸出聚類結(jié)果

1.initialize the Array List

2.initialize Central point sets C//創(chuàng)建中心點集合C

3.compute Range(D)

4.WHILE(size of C

5. get the data sets Dici//將D中的元素分配給ci//生成Di

6. computeMeansDis(Di)//計算Di相關(guān)參數(shù)

7. FOR(each center ciC){

9. compute p(j) and t(j)

10. }

11. select center ci1←sample max(p(j)/t(j))//通過最//大權(quán)重原則選擇2個新的中心點

13. compute a(j)

14. compute w(j)=p(j)*a(j)*1/t(j)

15. }

17. compute d(j,ci1)

18. IF(d(j,ci1)>MeanDis(Di)){

19. center ci2←sample max(d(j,ci1)*w(j))

20. }

21. }

22. FOR(each center ciC){//更新中心點集合C

23. remove ciin sets C

24. add ci1,ci2to sets C

25. }

26.}END WHILE

27.update C//合并更新中心點集合C

28.K-means input(C,K)//將中心點集合C和類別數(shù)K//作為輸入?yún)?shù)執(zhí)行K-means算法

29.WHILE(new center!=original center){

31. FOR(each centercjC){

32. Compute d(i,cj)

33. }

34. IF(MinDis=d(i,cj)){

35. centercj←sample i

36. }

37. }END FOR

38. compute new center ci=Mean(sample(i&&(icenter ci)))

39.}END WHILE

40.PRINT(Cluster C)

算法具體步驟如下:

步驟1給定數(shù)據(jù)集,根據(jù)式(6)計算所有樣本的權(quán)重,選擇滿足條件max(p(i)/t(i))的c1作為第1個聚類中心,并將c1加入到集合C中。同時,與c1的距離小于MeanDis(D)的樣本不能參與下一次聚類中心的選擇。

步驟2計算剩余樣本與c1之間的距離,選擇滿足條件max(w(i)×d(i,c1))的樣本元素設(shè)為c2,并將其加入到集合C中。

步驟3根據(jù)距離將所有樣本元素分配給c1和c2,得到2個簇。然后重新計算這2個簇的MeanDis(D)和簇中全部樣本元素的w。對于產(chǎn)生的2個簇,并行執(zhí)行步驟1和步驟2,產(chǎn)生4個新的聚類中心c3、c4、c5、c6。刪除集合C中的c1和c2,并將c3、c4、c5、c6加入集合C中。

步驟4根據(jù)距離將對應(yīng)的樣本元素分配給集合C中的m個中心點,產(chǎn)生m個簇,更新每個簇的MeanDis(D)和簇中的樣本元素權(quán)重,對產(chǎn)生的m個簇并行執(zhí)行步驟1和步驟2,刪除集合C中原有元素,將得到的2m個聚類中心添加到集合C中。

步驟5重復(fù)步驟4直至集合C中的元素個數(shù)大于或等于類數(shù)K。迭代q次后會得到2q個聚類中心,如果大于K,則使用PCA將2q個中心點減少至K個。

2.4 算法時間復(fù)雜度

傳統(tǒng)K-means算法的時間復(fù)雜度可以被描述為O(nKT),n是樣本集中的樣本元素個數(shù),K是分類數(shù),T是算法迭代次數(shù)。本文提出的PBK-means算法時間復(fù)雜度為O(n2+nr+nKT),文獻[24]提出的DCK-means算法時間復(fù)雜度為O(n2+nS+nKT),r是使用二分法的迭代次數(shù),r值較小,約等于lbK,S是尋找中心點的迭代次數(shù),大小約為K,T是產(chǎn)生的初始聚類中心執(zhí)行K-means算法的迭代次數(shù),O(n2)是使用最大權(quán)重法耗費的時間復(fù)雜度。將本文提出算法得到的初始聚類中心作為K-means算法的輸入?yún)?shù)時,需要的迭代次數(shù)T明顯小于傳統(tǒng)K-means算法隨機選取聚類中心所需的迭代次數(shù)T,因此,PBK-means算法的時間復(fù)雜度主要由數(shù)據(jù)集規(guī)模n決定。在處理規(guī)模中小型數(shù)據(jù)集時,本文算法在聚類效果和耗時方面都有較好的表現(xiàn)。當數(shù)據(jù)集規(guī)模增大到一定程度時,本文算法的時間復(fù)雜度約為O(n2)。目前提出的改進聚類算法由于結(jié)合密度或距離,算法時間復(fù)雜度均在O(n2)～O(n3)之間,本文算法由于結(jié)合了并行實現(xiàn)的特點,初始中心點的選擇過程耗時更短,效率更高。

3 實驗數(shù)據(jù)

對本文提出算法以及對比算法進行的實驗由以下3個部分組成:

1)算法中心點合并策略;

2)測試本文算法與對比算法在實驗數(shù)據(jù)集上的精準度等聚類指標;

3)比較本文算法與對比算法在實驗數(shù)據(jù)集上聚類所用的時間。

實驗環(huán)境為8 GB內(nèi)存、Intel?CoreTMi5-7500、3.40 GHz,Windows10操作系統(tǒng)。

3.1 實驗數(shù)據(jù)集參數(shù)

本文實驗用到了UCI數(shù)據(jù)集,從UCI 網(wǎng)站獲取,數(shù)據(jù)集參數(shù)如表1所示。

表1 實驗數(shù)據(jù)集參數(shù)

3.2 實驗結(jié)果

3.2.1 中心點合并策略

當實際聚類數(shù)為k時,若k正好為2r,則本文提出算法在r次迭代后得到的中心點可直接作為初始中心點執(zhí)行K-means算法。若2r-1

圖6 不同合并方法精度

從圖6可以看出,PCA在合并策略中表現(xiàn)最好,在5個UCI數(shù)據(jù)集上均取得了最高的聚類精度,PCA方法的原理是將中心點集數(shù)據(jù)矩陣轉(zhuǎn)置后把原先的2r個特征用數(shù)目更少的k個特征取代,從舊特征到新特征的映射保持原有數(shù)據(jù)特性。t-SNE比其他3種方法表現(xiàn)都好,但與使用PCA時的聚類精度平均相差2.36%。在類別數(shù)和樣本數(shù)較少時,通過聚類特征對簇進行合并產(chǎn)生的聚類效果較差。

3.2.2 聚類效果

聚類效果通過準確率、蘭德系數(shù)(Rand)、輪廓系數(shù)(Silhouette)、Jaccard系數(shù)、SSE指標評判。Canopy-Kmeans算法表示為CK-means,二分K-means算法表示為BK-means,本文提出的算法表示為PBK-means。本文算法與DCK-means算法得到的聚類結(jié)果是固定的,對其他5種對比算法分別進行100次實驗,取實驗結(jié)果的平均值。表2～表9為算法在UCI數(shù)據(jù)集上的實驗結(jié)果。

表2 Soybean-small數(shù)據(jù)集聚類結(jié)果指標

表3 Iris數(shù)據(jù)集聚類結(jié)果指標

表4 Wine數(shù)據(jù)集聚類結(jié)果指標

表5 Seeds數(shù)據(jù)集聚類結(jié)果指標

表6 Hepatitis數(shù)據(jù)集聚類結(jié)果指標

表7 Pima數(shù)據(jù)集聚類結(jié)果指標

表8 Glass數(shù)據(jù)集聚類結(jié)果指標

表9 Segmentation數(shù)據(jù)集聚類結(jié)果指標

通過表2～表9對聚類結(jié)果各項指標的比較發(fā)現(xiàn):本文提出的算法在Segmentation數(shù)據(jù)集上與DCK-means算法基本相同,原因是Segmentation數(shù)據(jù)集不同類別的數(shù)目差異較大,數(shù)據(jù)分布分隔明顯,由于DCK-means算法與本文算法都考慮了距離與密度,因此都能得到較好的結(jié)果。而在其他數(shù)據(jù)集上PBK-means算法各項指標均是最優(yōu)的,本文提出算法在上述8個UCI數(shù)據(jù)集上的聚類結(jié)果準確率比傳統(tǒng)K-means算法高27.1%,比Canopy-Kmeans算法高13.6%,比Bisecting K-means算法高14%,比WK-means算法高9.4%,比MWK-means算法高5.8%,比DCK-means算法高3.3%。無論是二分類任務(wù)或者多分類任務(wù),PBK-means算法都能得到較好的聚類效果,證明了算法思想和參數(shù)設(shè)置的合理性。本文提出的PBK-means算法通過結(jié)合距離與密度,每次將選擇的向量空間一分為二,相比于其他算法,更好地考慮了樣本集全部數(shù)據(jù)的分布情況,初始中心點的選擇結(jié)合了距離與密度,可以更快地收斂至全局最優(yōu)。

3.2.3 聚類時耗

本節(jié)比較了PBK-means算法與6種對比算法在UCI數(shù)據(jù)集上聚類所用的時間,具體耗時如表10所示。

表10 UCI數(shù)據(jù)集聚類耗時

通過對表10的分析,可以得出以下結(jié)論:

1)傳統(tǒng)的K-means算法隨機選擇初始聚類中心,Canopy-Kmeans算法已選取中心點固定半徑內(nèi)的點不能選為中心點,但中心點的選取仍是隨機的,Bisecting K-means算法第1個中心點選取數(shù)據(jù)集質(zhì)心,但后續(xù)對簇的二分過程相當于面對二分類任務(wù)時的傳統(tǒng)K-means算法。以上3種算法選取初始中心點的隨機性造成后續(xù)迭代多次才能得到穩(wěn)定的聚類結(jié)果,因此聚類耗時較大。

2)在面對多分類任務(wù)時,二分K-means算法計算SSE指標值的大量耗時使其聚類時間最長。由于并行實現(xiàn)的特點,本文提出的PBK-means算法所需聚類時間最少,通過權(quán)衡距離與密度,在保證聚類效果的前提下避免了SSE指標的計算耗時。在面對二分類任務(wù)時,PBK-means算法略優(yōu)于DCK-means算法,明顯優(yōu)于WK-means算法和MWK-means算法,得到的初始聚類中心在執(zhí)行K-means算法時迭代次數(shù)明顯小于其他算法。

4 結(jié)束語

由于標簽信息的缺乏,無監(jiān)督學習在數(shù)據(jù)挖掘中越來越重要,聚類在網(wǎng)絡(luò)入侵檢測、自然災(zāi)害監(jiān)測等方面有廣泛的應(yīng)用。本文提出一種PBK-means算法,根據(jù)數(shù)據(jù)分布情況對數(shù)據(jù)集進行分類,將距離和密度相結(jié)合從而快速處理中小型規(guī)模的數(shù)據(jù)集。實驗結(jié)果表明,該算法面對大型數(shù)據(jù)集時在效率和精度方面都有較好的表現(xiàn)。為獲得最佳初始聚類中心,將PBK-means算法與Mapreduce框架相結(jié)合以及尋找更好的中心點合并策略將是后續(xù)研究的內(nèi)容。