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

魏文浩,唐澤坤,劉 剛

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

0 概述

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

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

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

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

1 相關算法

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

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

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

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

算法1二分K-means算法

輸入數據集D,聚類數K

輸出聚類結果

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給定聚類數K和數據集D={x1,x2,…,xn}。

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

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

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

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

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

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

2 PBK-means算法

2.1 基本定義

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

定義1數據集D的平均樣本距離定義為[24]:

(1)

定義2數據集D的特征空間大小定義為:

(2)

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

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

(3)

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

(4)

定義5樣本元素i的異類參數定義為:

(5)

其中,m是密度參數大于樣本數據i的樣本數據數量。

定義6樣本元素i的權重定義為:

(6)

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

2.2 并行二分原則

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

顯然,對于K=2r的數據集,PBK-means算法可以直接得到結果,對于2r-1

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

2.3 最大權重原則

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

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

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

算法2PBK-means算法

輸入數據集D,聚類數K

輸出聚類結果

1.initialize the Array List

2.initialize Central point sets C//創建中心點集合C

3.compute Range(D)

4.WHILE(size of C

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

6. computeMeansDis(Di)//計算Di相關參數

7. FOR(each center ciC){

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

10. }

11. select center ci1←sample max(p(j)/t(j))//通過最//大權重原則選擇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和類別數K//作為輸入參數執行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給定數據集,根據式(6)計算所有樣本的權重,選擇滿足條件max(p(i)/t(i))的c1作為第1個聚類中心,并將c1加入到集合C中。同時,與c1的距離小于MeanDis(D)的樣本不能參與下一次聚類中心的選擇。

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

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

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

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

2.4 算法時間復雜度

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

3 實驗數據

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

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

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

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

實驗環境為8 GB內存、Intel?CoreTMi5-7500、3.40 GHz,Windows10操作系統。

3.1 實驗數據集參數

本文實驗用到了UCI數據集,從UCI 網站獲取,數據集參數如表1所示。

表1 實驗數據集參數

3.2 實驗結果

3.2.1 中心點合并策略

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

圖6 不同合并方法精度

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

3.2.2 聚類效果

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

表2 Soybean-small數據集聚類結果指標

表3 Iris數據集聚類結果指標

表4 Wine數據集聚類結果指標

表5 Seeds數據集聚類結果指標

表6 Hepatitis數據集聚類結果指標

表7 Pima數據集聚類結果指標

表8 Glass數據集聚類結果指標

表9 Segmentation數據集聚類結果指標

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

3.2.3 聚類時耗

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

表10 UCI數據集聚類耗時

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

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

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

4 結束語

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