空間密度相似性度量K-means算法

薛 衛,楊榮麗,趙 南,徐煥良,任守綱

(南京農業大學 信息科學技術學院,南京 210095)

1 引 言

數據聚類一直是機器學習領域具有挑戰性的研究內容[1],它基于“物以類聚”的基本原理,根據數據對象間的相似性,將數據分配到特定的類別或簇中.一個好的聚類算法要達到簇內高相似性和簇間低相似性的效果[2],即數據對象在同一簇中的相似性高于在不同簇的相似性.

K均值(K-means) 算法是應用最廣泛的聚類算法之一[3],初始聚類中心通過迭代生成最終的聚類中心,從而將含有n個樣本的數據集分成K個類別.K-means算法的思路易于理解、同時具有聚類效率高和局部搜索能力強等優點.但是傳統的K-means算法存在初始聚類中心不穩定;聚類效果和迭代次數對初始聚類中心過于依賴[4];易陷入局部最優[5]等問題.為改善以上缺陷,國內外學者從不同角度對K-means算法提出了一系列的優化方法.如Huang等提出一種基于自動計算權值的K-means算法,改進聚類中變量的選擇問題[6].Dhillon等為提高算法性能調整K-means迭代過程中計算聚類中心的方法[7].Redmond等將k-d樹和Katsavounidis提出的算法相結合,在基于密度選擇初始聚類中心時能盡可能分散選擇,使初始聚類中心的選擇更加合理化[8].Sarafis將遺傳算法應用在K-means的目標函數構建中,并在此基礎上提出新的聚類算法RBCGA,取得較好效果[9].經過系列的改進,K-means的聚類性能和準確率均有所提高,但在非簇型數據集上K-means算法還沒有取得較好效果.

在傳統及改進K-means算法中通常采用歐氏距離直接表達樣本間的相似性距離,但歐氏距離往往不能較為準確地表達各種流形數據點間的相似性,本文算法通過采用空間密度的相似性距離彌補這一缺陷,并提出新的K-means算法類中心的迭代模型,使算法能反映各種數據集的真實分布規律,得到準確穩定的聚類效果.

2 K-means聚類算法

已知樣本空間的數據集D={Xi|Xi∈Rm,i=1,2,…,n},n為樣本集大小,m為樣本數據維數.樣本集所屬的類別空間C={ck|ck∈Rm,i=1,2,…,k},K為所屬類別個數,C0表示初始聚類中心.兩個樣本之間的距離公式一般采用歐氏距離:

(1)

聚類中心

(2)

K-means算法的基本思想是通過初始化聚類中心C0和預先設定好的K值,不斷迭代更新類中的樣本至目標函數達到最優,即E值最小,達到簇內樣本距離最小化,簇間樣本最大化的效果.

(3)

K-means算法過程:

輸入:n個樣本、數據集D和聚類中心個數K

輸出:使目標函數E值最優的K個簇中心

1)隨機從n個樣本中選擇K個樣本作為初始聚類中心C0(t為迭代次數,此時t=0);

2)遍歷n個樣本,根據與C0的最小距離劃分樣本;

4)根據與Ct最小距離重新劃分所屬樣本;

5)循環執行(3)和(4)直至目標函數E的值達到最優,即不再變化.

3 空間密度相似性度量K-means算法

在傳統和改進K-means算法中,通常采用歐氏距離計算在m維空間中兩個樣本之間的距離.然而,在任意形狀分布的復雜數據集上,K-means算法通過歐式距離來衡量樣本間的相似性距離,往往達不到預期效果.如圖1中,樣本集中分布的A、B、C三點,歐式距離計算可得A點和C點的距離大于A點和B點的距離,而實際期望是通過某種距離計算得到,A點和C點的距離小于A點和B點的距離.本文提出的空間密度相似性距離的計算可達到預期效果.

圖1 樣本分布圖Fig.1 Sample distribution

如圖1中,A點可通過高密度集區域到達C點,而A點和B點之間存在低密度集區域.在數據集樣本空間分布中,由于類內距離遠小于類間距離,所以同一類別的樣本集的分布往往趨向于在同一個高密度集區域,不同類別的樣本集間的分布往往存在一個低密度集區域.

空間密度相似性距離通過密集度可調節的線段長度衡量相鄰點的距離,同時采用最短距離優化不相鄰點的相似性距離.在密集度可調節的線段長度中根據指數函數的性質給高密度集區域的樣本賦予更小的距離,給低密度集區域的樣本賦予更大的距離,可在任意形狀分布的復雜樣本空間中準確反映樣本的基本分布規律.

本文改進的K-means算法類中心迭代模型,不是求同一類別樣本的平均值得到此類別新一輪的聚類中心,而是通過計算同一類別樣本的空間密度相似性距離,選擇出與此類別所有樣本的相似性距離代價和最小的樣本,作為此類別新一輪的聚類中心.

3.1 基本定義

定義1.數據集D中任意兩個樣本距離的伸縮系數為:

(4)

其中Dist(Xi,Xj)為(1)中的歐式距離,mean為樣本集的特征變量,即一個類內的樣本均值.在某一樣本集中,mean為一定值,A值則取決于Dist(Xi,Xj)的大小.當Dist(Xi,Xj)相對于mean越大,兩樣本間距離受到的懲罰越大,即A值越大;Dist(Xi,Xj)相對于mean越小,兩樣本間距離受到的懲罰越小,即A值越小.

定義2.數據集D中任意兩個樣本間的密集度可調節的線段長度公式為:

L(Xi,Xj)=eDist(Xi,Xj)*A-1

(5)

e為數學中的歐拉數,值近似等于2.718281828.A系數可以加強歐式距離的大小比例程度,Dist(Xi,Xj)越小,A也越小,e的指數值也越小,反之亦然,同時指數函數的性質達到加強距離的伸縮效果.

定義3.假設數據點集D為圖G=(V,E)的頂點,P表示長度為|r-1|的連接數據點x1和x|r|的路徑,(xk,xk+1)∈E.Pi,j作為xi到xj的所能經過的所有路徑.樣本空間密度的相似性距離為:

(6)

距離DistF(xi,xj)表示的是樣本xi通過圖G中任意條路徑最終到達xj的最小距離,此距離可以最大程度的逼近兩個樣本在其樣本空間上的分布距離.

定義4.樣本空間指數據集中所有樣本分布的空間范圍.數據集的樣本空間為:

Space=Max{DistF(Xi,Xj)|0

(7)

定義5.某一樣本的密集度為:

Density(Xi)={Num(Xj)|DistF(Xi,Xj)

(8)

其中Num(Xj)為符合條件的樣本個數,r為密度半徑,一般取Space/(K*2).

(9)

3.2 算法描述

根據定義3樣本間空間密度的相似性距離作為K-means算法衡量樣本間的距離,定義6作為K-means算法的類中心迭代模型.

空間密度相似性度量K-means算法過程如下:

輸入:n個樣本、數據集D和聚類中心個數K

輸出:使目標函數E值最優的K個簇中心

1)對數據集樣本進行歸一化的數據預處理;

2)初始化聚類中心:

①根據樣本間的空間密度的相似性距離得出樣本空間Space和每一個樣本的密集度Density(Xi);

②選擇最大密集度樣本作為初始聚類中心的第一個中心,循環執行3),直至選擇出K個初始聚類中心C0(t=1);

③選擇其次大的密度樣本并且此樣本與之前選擇的聚類中心的距離大于一定的值(控制迭代值distrol),添加此樣本作為初始聚類中心.

3)根據聚類中心Ct-1和數據集樣本D的空間密度相似性距離重新劃分類得到Dt;

4)通過定義6的類中心迭代模型得到新一輪的聚類中心Ct;

5)循環執行(3)和(4),直至滿足目標函數E的值達到最優,即不再變化.

3.3 算法說明及復雜度分析

算法在開始階段的歸一化處理,將樣本的每一維統一到同一個參考系下,易于測量比較.空間密度的相似性距離,將指數函數性質和樣本間的最短距離結合,作為K-means算法中樣本相似性度量的標準,可以較為準確地反映任意形狀分布的復雜數據集的基本分布規律.同時最小距離得到的樣本密集度使選擇的初始聚類中心更加穩定.算法中的控制迭代值distrol作為初始聚類中心選擇的距離控制條件,經驗值一般取(1.0/(k))*Space.

傳統的基于隨機產生聚類中心的K-means 算法,其時間復雜度為O(nKT),其中T為K-means算法的迭代次數,K為類簇數,n為數據集樣本總個數;本文空間密度相似性度量的K-means算法的實現,其時間復雜度為O(n3Kt).由于本文算法的初始聚類中心的選擇較為穩定,而且可以選擇出基本符合樣本分布規律的最佳初始聚類中心,因此本文算法類中心的迭代次數小于傳統的隨機產生聚類中心的K-means算法.

4 實驗結果及分析

為了證明本文算法在簇型和非簇型數據中的有效性,實驗采用兩類數據,一類是自生成的二維的非簇型數據集,分別為月牙形、條形和環形數據;另一類是三種UCI標準數據集,分別為Iris、Wine、Haberman.采用本文算法和現階段三種流行的K-means優化算法進行實驗對比,同時對比相關文獻中在UCI數據集上的實驗效果.

三種K-means算法分別為隨機產生初始聚類中心[10](算法1),選擇批次距離盡可能遠的K個點作為初始聚類中心[11](算法2),基于密度的初始聚類中心的改進[12](算法3).算法1通過產生隨機數選擇對應的樣本作為初始聚類中心;算法2在隨機選擇第一個初始聚類中心后,選擇其他K-1個初始聚類中心均要求與之前已選擇的聚類中心最遠;算法3通過計算每一個樣本密度選擇較大密度的樣本作為初始聚類中心.

實驗環境為:AMD 四核 A6-3400M APU,1.5GHz主頻,8G內存,500G硬盤.Windows7操作系統,MyEclipse開發平臺.

4.1 非簇型人工數據集

為了驗證本文算法在非簇型數據集的聚類效果,人工生成三種不同形狀的非簇型數據,分別為月牙型數據集(Moon)、條形數據集(Stick)、環形數據集(ring).數據集的直觀效果圖如圖2.

圖2 數據集原數據直觀圖Fig.2 Visual map of the original data sets

將三種人工數據集分別在算法1、算法2、算法3和本文算法上進行實驗,聚類效果采用直觀效果圖(圖3-圖5)和最常用的聚類指標之一Accuracy的折線圖(圖6)展示在不同算法下的聚類效果.

圖3 Moon數據集算法實驗效果圖Fig.3 Moon data set experimental results

圖4 Stick數據集算法實驗效果圖Fig.4 Stick data set experimental result

從圖2至圖5可以直觀地觀察到,算法1和算法2在非簇型數據集上的K-means效果很相似,因為算法1和算法2在選擇初始聚類中心的規則都是選擇某一個樣本作為初始聚類中心,算法2只是在選擇時添加歐式距離的控制條件,雖然使選擇更加合理,但經過迭代,隨機選擇的中心也可以達到類似的效果.而算法3是基于歐式距離計算的密度來選擇初始聚類中心,對于非簇型數據,算法3往往會對數據集本身造成誤解,歐式距離相對近的樣本并不一定比歐式距離相對遠的樣本更相似,所以效果往往不佳.由此可知,歐氏距離下K-means在非簇型數據中的聚類效果較差.算法1和算法2的K-means聚類效果的準確率均在0.6至0.85之間,算法三在非簇型數據集上的效果更加不理想.基于樣本空間密度的相似性距離方法在非簇型數據集上可達到較好的效果,它利用指數函數性質和數據集樣本自身的伸縮系數相結合,根據有限個小數據相加仍是小數據,較少個大數據相加仍是大數據的規則,可達到類內距離相對于類外距離越來越小,類外距離相對于類內距離越來越大的效果,從而保證K-means的聚類效果.

圖5 Ring數據集算法實驗效果圖Fig.5 Ringdata set experimental results

圖6 數據集算法實驗準確率Fig.6 Accuracy of algorithms on data sets

4.2 UCI數據集

選用UCI機器學習數據庫[13]中3個聚類算法常用的數據集,對本文K-means的相似性度量算法進行實驗,并與傳統的算法1、算法2、算法3以及文獻[14-18]中的相關K-means優化算法進行比較.實驗采用的UCI數據集描述如表1.

從圖7中看出,本文算法在Iris、Wine和Haberman數據集上的聚類效果與算法1、算法2、算法3相比,均占有優勢,在Haberman的優勢更加明顯.本文算法在三個數據集上的準確率分別達到96.6%,91.57%,74.5%.

表1 UCI數據集描述
Table 1 Detail of UCI data set

數據集名稱樣本數屬性數類別數Iris15043Wine178133Haberman30632

在文獻[14]中,Iris和Wine數據集在K-means中的準確率分別為86.66%和72.25%;文獻[15]中利用PSO和K-means結合改進后在此兩個數據集中取得的準確率分別為88.2%和86.73%;文獻[16]中將K-means和RNN以及耦合度相結合,達到最好效果的準確率分別為90%和76.53%;文獻[17]中結合K-means提出的兩種算法在Haberman數據集中效果較好的準確率達到74%;而文獻[18]中在K-means的基礎上提出的CUK算法,在Haberman上的錯誤率為37.58%.由此可以得出結論,本文提出基于空間密度的K-means相似性度量優化不僅在非簇型人工數據集上的效果明顯優于其他算法,而且在UCI標準數據集上的效果也優于傳統算法以及一些改進后的K-means算法.

圖7 UCI數據集在不同算法上的效果Fig.7 Effect of different algorithms on UCI Data Sets

5 結束語

傳統K-means由于初始聚類中心的隨機性,使聚類效果不穩定,并且易于陷入局部最優的結果;基于盡可能遠的距離和基于密度的產生初始化聚類中心的改進算法,雖然在一定程度使選擇初始聚類中心更加合理化,但對于非簇型人工數據集,這些改進算法效果明顯不佳.本文提出的空間密度相似性度量K-means算法,使用空間密度的相似性距離克服歐式距離在非簇型人工數據集上度量的單一性和不合理性;同時在迭代過程中,新一輪聚類中心的產生規則不再簡單地取所有本簇樣本中每一維的平均值,而是在每次迭代更新空間密度的相似性距離時,選擇離本簇中所有樣本的空間密度相似性距離和最小的樣本,這樣可以完全避免由平均值帶來的聚類中心可能在簇外的情況.比如月牙型數據在使用平均值選擇聚類中心時,聚類中心極有可能出現在本簇區域以外,甚至存在和另一簇中心相重合的情況.因此,本文算法不僅可以有效反映非簇型人工數據集本身的數據特征,使其聚類準確率明顯提高,而且在標準數據集上也能取得較好的聚類效果.

本文算法空間密度相似性距離的計算和類中心迭代模型的改進,使得計算量增大.在今后的工作中,考慮在保持其聚類效果的基礎上優化計算方法使K-means更加高效準確,這是今后工作的重點.

[1] Sun Ji-gui,Liu Jie,Zhao Lian-yu.Clustering algorithms research[J].Journal of Software,2008,19(1):48-61.

[2] Xu Q,Ding C,Liu J,et al.PCA-guided search for k-means[J].Pattern Recognition Letters,2015,54(1):50-55.

[3] Naldi M C,Campello R J G B.Evolutionary k-means for distributed data sets[J].Neurocomputing,2014,127(3):30-42.

[4] Yu Jin-ping,Zhen Jie,Mei Hong-biao.K-means clustering algorithm based on improved artificial bee colony algorithm [J].Journal of Computer Applications,2014,34(4):1065-1069.

[5] Arora P,Deepali,Varshney S.Analysis of k-means and k-medoids algorithm for big data[J].Procedia Computer Science,2016,78(1):507-512.

[6] Huang J Z,Ng M K,Rong H,et al.Automated variable weighting in k-means type clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI),2005,27(5):657-668.

[7] Dhillon IS,Guan Y,Kogan J,et al.Refining clusters in high dimensional text data[C].In Proceedings of the Second SIAM Workshop on Clustering High Dimensional Data (2 SIAM WORKSH CLUST),2002:59-66.

[8] Redmond S J,Heneghan C.A method for initialising the k-means clustering algorithm using kd-trees[J].Pattern Recognition Letters,2007,28(8):965-973.

[9] Sarafis I,Zalzala A M S,Trinder P W.Agenetic rule-based data clustering toolkit[C].IEEE World Congress on Computational Intelligence (WCCI2002),2002:1238-1243.

[10] Han Ling-bo,Wang Qiang,Jiang Zheng-feng,et al.Improved K-means initial clustering center selection algorithm[J].Computer Engineering and Applications,2010,46(17):150-152.

[11] Zhai Dong-hai,Yu Jiang,Gao Fei,et al.K-means text clustering algorithm based on initial cluster centers selection according to maximum distance[J].Application Research of Computers,2014,31(3):713-715.

[12] Fu De-sheng,Zhou Chen.Improved K-means algorithm and its implementation based on density[J].Journal of Computer Applications,2011,31(2):432-434.

[13] Frank A,Asuncion A.UCI machine learning repository[R].California:University of California,School of Information and Computer Science,2010．

[14] Fong S,Deb S,Yang X S,et al.Towards enhancement of performance of K-means clustering using natureinspired optimization algorithms[J].The Scientific World Journal,2014,(1):1-16.

[15] Saini G,Kaur H.A novel approach towards k-mean clustering algorithm with PSO[J].International Journal of Computer Science and Information Technologies(IJCSIT),2014,5(4):5978-5986.

[16] Ahmed A H,Ashour W.An initialization method for the kmeans algorithm using RNN and coupling degree[J].International Journal of Computer Applications (IJCA),2011,25(1):1-6.

[17] Bdiri T.Positive data clustering using finite inverted dirichlet mixture models[D].Canada:Concordia University,2010.

[18] Alnaji K W,Ashour W M.A novel clustering algorithm using k-means ′CUK′[J].International Journal of Computer Applications (IJCA),2011,25(1):25-30.

附中文參考文獻：

[1] 孫吉貴,劉 杰,趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

[4] 喻金平,鄭 杰,梅宏標.基于改進人工蜂群算法的K均值聚類算法[J].計算機應用,2014,34(4):1065-1069.

[10] 韓凌波,王 強,蔣正鋒,等.一種改進的K-means初始聚類中心選取算法[J].計算機工程與應用,2010,46(17):150-152.

[11] 翟東海,魚 江,高 飛,等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計算機應用研究,2014,31(3):713-715.

[12] 傅德勝,周 辰.基于密度的改進K均值算法及實現[J].計算機應用,2011,31(2):432-434.