一種高效的基于初始聚類中心優(yōu)化的K-means算法

張曉倩，曲福恒，楊勇，才華，梁鮮

（長春理工大學(xué) 計算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022）

聚類分析是數(shù)據(jù)挖掘中常用的無監(jiān)督學(xué)習(xí)方法［1］。聚類問題的基本形式被定義為找到給定數(shù)據(jù)集中的同組數(shù)據(jù)，每組數(shù)據(jù)又稱為一個簇，并且處于某個簇中的數(shù)據(jù)對象的密度高于該對象處于其它的簇。目前已有的聚類方法很多，根據(jù)基本聚類思想的不同，聚類分析方法大致可以分為劃分聚類、層次聚類、密度聚類、網(wǎng)格聚類和模型聚類五大類。

聚類分析旨在將給定的數(shù)據(jù)集劃分為不相干的子集，并且每個子集中的數(shù)據(jù)對象具有較高的相似度。K-means是一種最常用的迭代劃分聚類算法，使用該算法進(jìn)行聚類時，首先它需要指定集群的數(shù)量，然后，提供初始數(shù)據(jù)集的劃分并且這些初始簇的質(zhì)心是提前計算出來的。在最初的K-means方法中，初始集群通常是隨機(jī)選擇的，顯然，這種隨機(jī)性會導(dǎo)致聚類結(jié)果的不穩(wěn)定。為解決這個問題，許多K-means的初始化方法被提出。如文獻(xiàn)［2］提出基于相異度的K-means改進(jìn)算法，根據(jù)由相異度矩陣組成的霍夫曼樹選擇初始質(zhì)心。文獻(xiàn)［3］提出了一種利用反向最近鄰（RNN）搜索方法選取初始質(zhì)心。文獻(xiàn)［4］結(jié)合數(shù)據(jù)密度分布和kd-tree進(jìn)行選擇初始質(zhì)心。文獻(xiàn)［5］根據(jù)樣本空間分布信息，根據(jù)每個數(shù)據(jù)樣本方差的大小以及樣本間平均距離選取初始聚類中心。文獻(xiàn)［6］提出了基于全局優(yōu)化的思想選取初始聚類中心，該算法通過多次運(yùn)行K-means算法得到k個初始聚類中心。但由于選取初始質(zhì)心的計算代價和時間代價大，該文獻(xiàn)中又提出了快速全局K-means聚類算法，對選取初始中心的方法進(jìn)行了改進(jìn)，縮短了聚類時間。本文在文獻(xiàn)［7］提出算法的基礎(chǔ)上，對進(jìn)一步提高聚類算法的效率問題進(jìn)行了研究，提出了一種高效的基于初始聚類中心優(yōu)化的K-means算法，通過存儲每次迭代中的一些信息，用于下一次迭代，減少一部分計算量，提高算法執(zhí)行效率。

1 最小方差優(yōu)化初始聚類中心的K-均值算法

傳統(tǒng)的K-means算法的聚類過程是隨機(jī)選擇k個初始質(zhì)心，根據(jù)最近鄰原則，將數(shù)據(jù)集中的數(shù)據(jù)樣本與最近的初始質(zhì)心歸為一類，重復(fù)迭代，直至初始質(zhì)心不再發(fā)生變化或準(zhǔn)則函數(shù)收斂，得到最終的k個簇。K-means算法的核心計算為計算每個數(shù)據(jù)對象到k個聚類中心的距離，算法的時間復(fù)雜度為O（nkt），其中，n為數(shù)據(jù)對象個數(shù)，t為迭代次數(shù)。

圖1 最小方差K均值算法流程圖

最小方差優(yōu)化初始聚類中心的K-means算法［6］根據(jù)樣本空間分布信息，根據(jù)每個數(shù)據(jù)樣本方差的大小以及樣本間平均距離選取初始聚類中心。首先選擇所有樣本中方差最小的那個作為第一個初始聚類中心；然后選取距離第一初始聚類中心距離大于樣本間平均距離并且方差最小的樣本作為第二個初始中心；重復(fù)該過程，直到找到k個初始聚類中心。在選取k個初始質(zhì)心時，首先計算樣本之間的距離矩陣，然后根據(jù)距離矩陣中的數(shù)據(jù)計算每個數(shù)據(jù)樣本方差的大小，總的時間復(fù)雜度為O（n2），其中選取初始質(zhì)心的時間復(fù)雜度為O（n2），在對每個數(shù)據(jù)對象進(jìn)行歸類分配時的時間復(fù)雜度為O（nkt1），其中t1為迭代次數(shù)。算法流程如圖1所示。

2 本文改進(jìn)算法

在K-means算法聚類過程中，在每次迭代數(shù)據(jù)點分配的過程中，需要每個計算數(shù)據(jù)點到所有聚類中心的距離，而在不斷迭代過程中，一些樣本點所在簇是不發(fā)生變化的。文獻(xiàn)［7］中提出了一種改進(jìn)的K-means算法，通過設(shè)置簡單的數(shù)據(jù)結(jié)構(gòu)，存儲每次迭代中的一些信息用于下一次迭代。主要思想是：設(shè)置兩個簡單的數(shù)據(jù)結(jié)構(gòu)，保存所有數(shù)據(jù)點的簇標(biāo)志和到最近中心點的距離，用于下一次迭代，在計算數(shù)據(jù)對象到新中心的距離，如果這個距離小于或等于到原來中心的距離，則該數(shù)據(jù)對象仍在原來簇中。因此，不需要計算到剩余聚類中心的距離，節(jié)省了計算到剩余聚類中心距離的時間。本文將該文獻(xiàn)中提到的改進(jìn)算法的思想引入到最小方差優(yōu)化初始聚類中心K-means算法中，在避免選擇初始質(zhì)心隨機(jī)選取的同時縮短聚類時間。

2.1 幾個相關(guān)的基本概念

定義1：樣本之間的歐氏距離：

定義2：樣本xi到所有樣本距離的均值：

定義3：樣本xi的方差：

定義4：所有數(shù)據(jù)樣本的平均距離：

定義5：聚類準(zhǔn)則函數(shù)：

2.2 算法執(zhí)行過程

改進(jìn)算法的執(zhí)行過程描述如下：

（1）選擇初始聚類中心

1）根據(jù)定義1計算數(shù)據(jù)對象間距離；

2）根據(jù)1）中計算出來的數(shù)據(jù)對象間距離以及定義4計算平均距離d；

3）計算每個樣本方差并選取方差最小的那個樣本作為第一個聚類中心；

4）把與已有聚類中心距離大于平均距離d的樣本方差置空，在剩余樣本方差中選取最小的那個樣本作為下一個聚類中心；重復(fù)該步，得到k個聚類中心，執(zhí)行（2）；

（2）執(zhí)行改進(jìn)后的K-means算法：

1）計算每個數(shù)據(jù)樣本到各個初始聚類中心的距離，按最近離原則將其分到各個簇，存儲每個數(shù)據(jù)對象的類標(biāo)簽和對象到最近中心點的距離到cluster［］和dis［］中；

讓cluster［i］=j，j為對象i最近的簇標(biāo)簽；

讓dis［i］=d（xi，cj），d（xi，cj）為到最近中心點的距離；

2）按照平均法計算各簇的質(zhì)心，得到新的簇中心；

3）計算準(zhǔn)則函數(shù)E；

（3）重復(fù)以下過程

1）計算每個數(shù)據(jù)對象到新聚類中心的距離d；

a）如果 d ＜=dis［i］，則第 i個數(shù)據(jù)對象仍近似的在原來的簇中，將該數(shù)據(jù)對象分給原來的簇。

b）否則，計算數(shù)據(jù)點到所有中心的距離d(xi,ck)，分配數(shù)據(jù)到最近的簇中心；讓

cluster［i］=k ，dis［i］=d(xi,ck)；

2）更新簇中心

3）計算準(zhǔn)則函數(shù)E，判斷E是否收斂，若收斂，則算法結(jié)束，輸出最終聚類結(jié)果。

由前面對最小方差優(yōu)化初始聚類中心K-means算法的復(fù)雜度分析可知，選取初始質(zhì)心的復(fù)雜度為O（n2），在進(jìn)行數(shù)據(jù)分配時，首先將N個數(shù)據(jù)對象分到k個簇，計算量為O（nk），在后面的迭代計算過程中，一些數(shù)據(jù)對象仍近似的保留在原來的簇中，而一些數(shù)據(jù)對象將分配到其它的簇中。如果數(shù)據(jù)點仍近似的留在原來的簇中，時間復(fù)雜度為O（1），否則，為O（k）。隨著算法的不斷收斂，每個簇中移動的數(shù)據(jù)點的數(shù)量也在不斷減少，如果有一半的數(shù)據(jù)移動，此時的時間復(fù)雜度為O（nk/2），因此在進(jìn)行數(shù)據(jù)分配時的總的時間復(fù)雜度為O（nk t2），其中t2為迭代次數(shù)，因此本文算法總的時間復(fù)雜度為O（n2）。

3 實驗測試及結(jié)果分析

本文在UCI數(shù)據(jù)庫中取5個不同的數(shù)據(jù)集進(jìn)行測試，給出了數(shù)據(jù)集描述表以及各個算法的時間復(fù)雜度對比表，并對本文算法中的優(yōu)化方法進(jìn)行描述。各個算法在數(shù)據(jù)集運(yùn)行30次得出實驗結(jié)果，在聚類準(zhǔn)則函數(shù)E上對傳統(tǒng)K-均值，快速全局K均值、最小方差K均值算法，以及本文改進(jìn)算法進(jìn)行實驗結(jié)果的比較；在運(yùn)行時間上本文算法首先與前兩種方法進(jìn)行比較；由于本文算法與最小方差K均值選取初始質(zhì)心的計算方法相同，則選取初始質(zhì)心的時間上也相同，算法的提速主要是在后續(xù)聚類，因此，對兩種算法運(yùn)行時間的比較分兩方面：選取初始質(zhì)心時間T1與數(shù)據(jù)聚類時間T2，主要是對數(shù)據(jù)聚類時間進(jìn)行比較。給出算法本身的迭代次數(shù)t，然后對各個算法的時間復(fù)雜度進(jìn)行了對比分析。數(shù)據(jù)集描述如表1所示，時間復(fù)雜度對比如表2所示，實驗結(jié)果的比較分別如表3、表4、表5所示。

表1 數(shù)據(jù)集描述表

表2 時間復(fù)雜度對比

表3 各算法準(zhǔn)則函數(shù)E上的比較

由表3可知，在pima數(shù)據(jù)集上，本文算法與最小方差優(yōu)化初始聚類中心的K-means算法以及快速全局K-means算法保持了聚類結(jié)果的一致性。在yeast數(shù)據(jù)集上，本文算法聚類誤差平方和略高于改進(jìn)前算法，但優(yōu)于快速全局K-means算法。在其它數(shù)據(jù)集上與最小方差優(yōu)化初始聚類中心的K-means算法相比E雖然有所增大，但都接近于傳統(tǒng)K-means算法最好或平均聚類誤差平方和。由以上分析可知，本文算法基本上沒有影響聚類結(jié)果，證明了改進(jìn)后算法的有效性。

表4 各算法運(yùn)行時間T上的比較

根據(jù)表2和表4的對比，可知本文算法與快速全局K均值的時間復(fù)雜度大于傳統(tǒng)K均值，本文算法的時間復(fù)雜度小于快速全局K均值。由于通過計算的方法選取初始聚類中心相對于隨機(jī)選取初始質(zhì)心會消耗一部分運(yùn)行時間，并且隨著數(shù)據(jù)量的增大，選取初始質(zhì)心的時間消耗增長，因此就表3中的所有數(shù)據(jù)集而言，快速全局K均值，以及本文算法不如K-means算法運(yùn)行時間效率高，但本文算法的運(yùn)行時間效率高于快速全局K均值。

由表2知本文算法選取初始質(zhì)心的時間復(fù)雜度小于快速全局K均值選取初始質(zhì)心的時間復(fù)雜度。在進(jìn)行數(shù)據(jù)分配聚類時，本文算法的優(yōu)化方法是通過存儲每個數(shù)據(jù)對象的類標(biāo)簽以及與所屬類中心的距離，在下一次迭代中，計算數(shù)據(jù)點與所屬類中更新后的聚類中心的距離，若小于與原來聚類中心的距離，則近似的將該數(shù)據(jù)對象分給原來的簇，減少到其余k-1個中心距離的計算。隨著迭代的進(jìn)行，所需移動的數(shù)據(jù)點的個數(shù)在不斷減少，在數(shù)據(jù)聚類時，需要與所有聚類中心計算距離的計算量減少，并且由于每個簇中數(shù)據(jù)點的變化減小，使得簇達(dá)到穩(wěn)定所需的迭代次數(shù)也相對減少，縮短了算法收斂所需要的時間。

如表4所示，由于iris與pima兩個數(shù)據(jù)集的數(shù)據(jù)量與簇的數(shù)目較少，算法的迭代次數(shù)變化不大，在其余三個數(shù)據(jù)集上，算法收斂的迭代次數(shù)都有明顯的減少。迭代次數(shù)的減少以及本文算法選取初始質(zhì)心與數(shù)據(jù)聚類所需的計算量小，使得算法的整體運(yùn)算效率要明顯高于快速全局K均值。

由于本文算法與最小方差k均值選取初始聚類中心的計算方法相同，選取初始質(zhì)心時間T1相同，算法的提速主要是在后續(xù)聚類，因此本文算法主要在數(shù)據(jù)聚類時間T2上進(jìn)行比較。根據(jù)上面對本文算法進(jìn)行數(shù)據(jù)聚類時優(yōu)化方法的描述可知，本文算法在已選出初始聚類中心的情況下，對數(shù)據(jù)點進(jìn)行分配歸類時，減少了數(shù)據(jù)點與聚類中心計算距離的計算量以及算法收斂所需的迭代次數(shù)，縮短了數(shù)據(jù)聚類所需的聚類時間。由表5可以看出，隨著數(shù)據(jù)集的增大，聚簇數(shù)目的增多，算法收斂所需的迭代次數(shù)明顯減少，本文算法相對于最小方差K均值的運(yùn)算效率也有明顯的提高，在iris與pima數(shù)據(jù)集上，進(jìn)行數(shù)據(jù)聚類時的運(yùn)算速度提高了40%～50%，在剩余的三個數(shù)據(jù)集上，進(jìn)行數(shù)據(jù)分配歸類時，進(jìn)行數(shù)據(jù)聚類時的運(yùn)算速度提高了70%～90%，可見，改進(jìn)后的算法明顯縮短了數(shù)據(jù)分配歸類所需的聚類時間，證明了改進(jìn)后算法在時間性能上的高效性。

表5 本文算法與最小方差K均值的運(yùn)行時間比較

綜上所述，快速全局K均值，最小方差K均值以及本文算法的時間復(fù)雜度大于傳統(tǒng)K均值的時間復(fù)雜度，但這三種方法都是通過計算來獲得穩(wěn)定的初始質(zhì)心，由表3可知，這三種算法的聚類結(jié)果相對于傳統(tǒng)K均值算法的聚類結(jié)果，更具有穩(wěn)定性和準(zhǔn)確性。由表2、表4可知，本文算法的時間復(fù)雜度優(yōu)于快速全局K均值，算法的整體運(yùn)行效率明顯高于快算全局K均值。本文算法與最小方差K均值相比，由于兩種算法選取初始聚類中心的計算方法相同，選取初始質(zhì)心的時間相同，主要是對后續(xù)的數(shù)據(jù)聚類進(jìn)行優(yōu)化提速，由上面的分析可知，本文算法相對于最小方差K均值算法，減少了后續(xù)聚類的計算量以及算法收斂所需的迭代次數(shù)（如表5所示），證明了本文算法在時間性能上的高效性。

4 總結(jié)

本文通過將一個簡單有效的數(shù)據(jù)聚類方法引入到最小誤差優(yōu)化初始聚類中心的K-means算法中，在避免隨機(jī)選取初始聚中心導(dǎo)致聚類結(jié)果不穩(wěn)定的基礎(chǔ)上，減少了計算量，提高算法的執(zhí)行效率，并在UCI數(shù)據(jù)集進(jìn)行了實驗驗證，實驗結(jié)果證明了改進(jìn)算法在聚類結(jié)果上的有效性以及在聚類時間上的高效性。

［1］Han Jiawei，Kamber M.Data mining：concepts and techniques［M］.Beijing：China Machine Press，2011.

［2］Shunye W.An improved k-means clustering algorithm based on dissimilarity［C］//Mechatronic Sciences，Electric Engineering and Computer（MEC），Proceedings 2013 International Conference on IEEE，2013：2629-2633.

［3］Xu J，Xu B，Zhang W.Stable initialization scheme for k-means clustering［J］.Wuhan University Journal of Natural Sciences，2009，14（1）：24-28.

［4］Redmond S J，Heneghan C.A method forinitializing the K-means clustering algorithm using kd-trees［J］.Pattern Recognition letters，2007，28（8）：965-973.

［5］謝娟英，王艷娥.最小方差優(yōu)化初始聚類中心的K-means算法［J］.計算機(jī)工程，2014，40（8）：205-211.

［6］Likas A，Vlassis M，Verbeek J.The global K-means clustering algorithm［J］.Pattern Recognition，2003，36（2）：451-461.

［7］Na S，Xumin L，Yong G.Research on k-means clustering algorithm：An improved k-means clustering algorithm［C］//Intelligent Information Technology and Security Informatics（IITSI），2010 Third International Symposium on IEEE，2010：63-67.