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

魏文浩,唐澤坤,劉 剛

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

0 概述

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

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

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

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

1 相關(guān)算法

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

圖1 K-means算法二分聚類(lèi)步驟1

圖2 K-means算法二分聚類(lèi)步驟2

圖3 K-means算法二分聚類(lèi)步驟3

算法1二分K-means算法

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

輸出聚類(lèi)結(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給定聚類(lèi)數(shù)K和數(shù)據(jù)集D={x1,x2,…,xn}。

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

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

步驟4選擇SSE值最小的簇群,用新生成的兩個(gè)中心點(diǎn)覆蓋C中的生成這兩類(lèi)的中心點(diǎn)。

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

對(duì)于含有K個(gè)中心點(diǎn)的集合C,ci為簇Ci的聚類(lèi)中心,x為該簇中的一個(gè)樣本,d(x,ci)表示x與ci之間的歐氏距離,SSE指標(biāo)的計(jì)算公式為:

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

2 PBK-means算法

2.1 基本定義

對(duì)于給定數(shù)據(jù)集D={x1,x2,…,xn},每個(gè)樣本元素可表示為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個(gè)特征上的最大值和最小值。

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

(3)

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

(4)

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

2.2 并行二分原則

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

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

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

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

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

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

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

算法2PBK-means算法

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

輸出聚類(lèi)結(jié)果

1.initialize the Array List

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

3.compute Range(D)

4.WHILE(size of C

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

6. computeMeansDis(Di)//計(jì)算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))//通過(guò)最//大權(quán)重原則選擇2個(gè)新的中心點(diǎn)

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){//更新中心點(diǎn)集合C

23. remove ciin sets C

24. add ci1,ci2to sets C

25. }

26.}END WHILE

27.update C//合并更新中心點(diǎn)集合C

28.K-means input(C,K)//將中心點(diǎn)集合C和類(lèi)別數(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)計(jì)算所有樣本的權(quán)重,選擇滿(mǎn)足條件max(p(i)/t(i))的c1作為第1個(gè)聚類(lèi)中心,并將c1加入到集合C中。同時(shí),與c1的距離小于MeanDis(D)的樣本不能參與下一次聚類(lèi)中心的選擇。

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

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

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

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

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

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

3 實(shí)驗(yàn)數(shù)據(jù)

對(duì)本文提出算法以及對(duì)比算法進(jìn)行的實(shí)驗(yàn)由以下3個(gè)部分組成:

1)算法中心點(diǎn)合并策略;

2)測(cè)試本文算法與對(duì)比算法在實(shí)驗(yàn)數(shù)據(jù)集上的精準(zhǔn)度等聚類(lèi)指標(biāo);

3)比較本文算法與對(duì)比算法在實(shí)驗(yàn)數(shù)據(jù)集上聚類(lèi)所用的時(shí)間。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

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

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 中心點(diǎn)合并策略

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

圖6 不同合并方法精度

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

3.2.2 聚類(lèi)效果

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

表2 Soybean-small數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

表3 Iris數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

表4 Wine數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

表5 Seeds數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

表6 Hepatitis數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

表7 Pima數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

表8 Glass數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

表9 Segmentation數(shù)據(jù)集聚類(lèi)結(jié)果指標(biāo)

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

3.2.3 聚類(lèi)時(shí)耗

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

表10 UCI數(shù)據(jù)集聚類(lèi)耗時(shí)

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

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

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

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

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