優化初始聚類中心的K-means聚類算法

郭永坤，章新友，劉莉萍，丁 亮，牛曉錄

1.江西中醫藥大學 計算機學院，南昌 330004

2.江西中醫藥大學 藥學院，南昌 330004

1 引言

聚類是根據數據不同特征，將其劃分為不同的數據類，屬于一種無監督學習方法。它的目的是使得屬于同一類別個體之間的密度盡可能的高，而不同類別個體間的密度盡可能的低。傳統的聚類算法[1-12]可分為：基于劃分的聚類、基于密度的聚類、基于層次的聚類、基于網格的聚類等。K-means算法屬于基于劃分的聚類算法之一，也屬于一種經典的分布式聚類算法。K-means算法作為一種基于樣本間相似性度量的間接聚類方法[13]，該算法以簇類數目K為參數，把n個數據對象按規則劃分為K個簇，使得簇內的相似度較高，而簇間的相似度較低。雖然K-means算法具有算法簡單、高效、易于理解的優點，但其仍存在一些不足，即一般只能處理球狀或類球狀的數據集、初始聚類中心不穩定、易陷入局部最優解等等。針對該算法的不足之處，許多學者進行了許多的改進，例如，文獻[14-15]針對傳統K-means算法隨機選取初始聚類中心，容易導致聚類結果不穩定問題，分別選擇方差最小（即緊密度最高）且相距一定距離的樣本和最大化減少誤差平方和的數據點作為聚類初始中心作為初始聚類中心，從而實現優化的K-means聚類；文獻[16]針對現有基于密度優化的K-means算法存在聚類中心搜索范圍大、消耗時間久及聚類結果對孤立點敏感等問題，提出了一種基于平均密度優化初始聚類中心的K-means算法adk-means；文獻[17-18]針對傳統K-means算法初始聚類中心選擇的隨機性可能導致迭代次數增加、陷入局部最優和聚類結果不穩定現象的缺陷，分別提出一種基于隱含狄利克雷分布（LDA）主題概率模型的初始聚類中心選擇算法和基于樣本密度的全局優化K均值聚類算法；文獻[19]針對典型K-means算法隨機選取初始中心點導致算法迭代次數過多的問題，采取數據分段方法，將數據點根據距離分成k段，在每段內選取一個中心作為初始中心，進行迭代運算，以減少迭代次數；文獻[20-21]針對K-means算法易受初始聚類中心影響而陷入局部最優問題，運用螢火蟲算法的全局搜索能力，提出了改進的K-means算法；文獻[22]針對傳統K-means算法由于初始聚類中心的隨機選擇，導致聚類結果不穩定問題，提出一種基于離散量改進K-means初始聚類中心選擇的算法；文獻[23]為了解決初始聚類中心敏感問題，本文采用分層凝聚聚類算法選取初始聚類中心，以保證中心點的高質量；文獻[24]提出了一種改進的K-means算法，建立了一個高質量訓練數據集，大大提高了分類器性能，縮短了分類器的訓練時間，提高了效率；文獻[25]針對K-means算法對初始聚類中心和離群點敏感的缺點，預先處理離群點，從而提出了一種優化初始聚類中心的改進K-means算法；文獻[26]針對K-means算法易受聚類中心影響而陷入局部最優的問題，引入了衰減因子加快收斂速度，從而提出一種基于改進森林優化算法的K-means聚類算法；文獻[27]針對簇類K值的選取問題，利用指數函數性質、權重調節、偏執項和手肘法基本思想，提出了一種改進K值選擇算法ET-SSE算法；文獻[28]針對現有的基于密度的聚類算法存在參數敏感，處理非球面數據和復雜流形數據聚類效果差問題，提出一種自然最近鄰優化的密度峰值的聚類算法；文獻[29]針對K-means算法易受初始中心影響的缺點，引入了混沌搜索思想，提出基于改進粒子群算法的K-means算法。盡管許多研究者對于初始聚類中心敏感問題做出了一些改進，但沒有充分考慮到數據集的密度分布情況，對于密度差異較大的數據集處理效果并不是很好。

對于K-means算法初始聚類中心敏感和無法很好地處理密度差異較大的數據集問題，本文提出了一種改進的初始聚類中心選擇算法，該算法引入了高密度優先聚類的思想，提高密度差異較大數據集的聚類效果，并增強算法的穩定性。實驗表明，對于差異較大的數據集，本文的改進算法聚類結果更加穩定，聚類效果也較好，從而充分說明了本文改進算法是可行的、合理的和有效的。隨著數據集的復雜化和多樣化，致使數據集的密度差異越來越大，本文算法的提出為以后的研究提供了一個新的思路。

2 改進算法的基本思想

為了了解改進算法的基本思想，需先了解K-means算法基本思想[11]：首先在數據集上隨機選取K個數據對象作為初始聚類中心，然后計算每個數據對象與中心點的歐式距離并劃分給距離最小的中心點，形成K個簇類，重新計算更新后的簇類中心，重復以上步驟直到聚類中心不再變化或相鄰兩次簇內誤差平方和的差值小于閾值為止。

為了降低隨機選取初始聚類中心的敏感性所造成的不穩定性，結合密度塊劃分的思想，提出了基于初始聚類中心優化的K-means聚類算法。改進算法的基本思想：采用高密度對象更可能為聚類中心的思想，劃分了密度集合區間，并在各個集合區間選取初始聚類中心，充分考慮到了數據集的密度分布情況且選取的中心一般都具有唯一性，大大地減少了隨機性選取初始中心帶來的影響。

設樣本數據集合：D={x1,x2,…,xn}，k個簇類：C={C1,C2,…,Ck}，m個集合：M={M1,M2,…,Mm}。

定義1兩個數據對象間的歐氏距離為：

其中，xi,xj為數據對象，xil為xi的l個特征屬性，xjl為xj的第l個特征屬性。

定義2類簇的中心(Centerk)為：

其中，Centerk表示第k個簇類的中心，Ck表示第k個簇類，xi∈Ck表示屬于簇類Ck的數據對象。

定義3點與樣本集合間的距離為點與集合內數據對象均值間的距離：

其中，M表示距離最短的兩點組成的集合，D′表示刪除集合M中數據后的樣本數據集，centerMm表示第m個集合Mm的均值。

定義4目標函數即誤差平方和為：

定義5某一數據對象與其他簇類內所有數據對象間的距離和為：

在K-means算法中，數據對象間的相似度是用歐氏距離來計算的，距離越小則相似度越高。對于密度不均勻的數據集密度越高越容易聚在一起，如果能夠找到k個分別代表了相似程度較大數據集合的聚類中心，那么將會更加有利于目標函數的收斂。

根據上述的原理（可稱為初始聚類中心選擇原理）可知，在數據空間分布上找到不同密度內的k個點作為初始聚類中心，具體步驟如下：

（1）根據公式（1）計算數據對象兩兩間的歐式距離d(xi,xj)(i,j=1,2,…,n)，找出距離最短的兩個數據對象組成一個樣本集合Mm(0≤m≤k)，并將它們從總的數據集D中刪除。

（2）計算樣本集合Mm內所有數據對象的均值。

（3）根據公式（3）計算數據集D中每個對象與樣本集合Mm間的距離，找到距離最近的點加入集合Mm，并將它從數據集D中刪除。

（4）計算樣本集合Mm內所有數據對象的均值。

（5）重復步驟（3）、（4）直到樣本集合Mm內的數據對象大于等于α(n k) ，0<α≤1。

（6）如果m

例如有一個2維數據集D，數據大小為14，且它的數據分布如圖1所示。

假設需要把它們劃分成兩類，按照上述的思想尋找初始聚類中心。由圖1可知，a和b之間的距離最短，那么就選擇a、b構成一個集合M1，并將它們從數據集D中刪除；根據公式（3）計算D內對象點與集合M1的距離找出了相鄰最短的點c，將c加入集合M1并將它從D中刪除，如果規定每個樣本集合數據對象最大個數為5，在通過上步思想找到了d、e添加到集合M1中并將它們從D中刪除，然后再在D中找到距離最近的兩個點l、m構成集合M2并將它們從D中刪除，D中距離M2最近的點是j，將j加入集合M2并將它從D中刪除，同理i、f也會加入集合M2并將它們從D中刪除；最后分別計算集合M1、M2的算術平均作為兩個簇類的初始聚類中心。

圖1 數據分布圖

3 改進算法的具體描述

若數據集N={x1,x2,…,xn}含有n個數據對象，每個數據對象有s維，則改進算法的詳細描述如下（占比率P(0

輸入：數據集N={x1,x2,…,xn}，簇類數目K，占比率P(0

輸出：聚類結果。

（1）按照上述初始聚類中心選擇原理得到K個聚類中心作為初始中心。

（2）依據公式（1）計算每個數據對象與中心的距離，并把它劃分給最近的聚類中心，得到K個簇類。

（3）根據公式（2）重新計算每個簇類的中心。

（4）重新劃分簇并更新中心。

（5）直到聚類中心不再變化或連續兩次E值的差值小于閾值。

（6）算法結束。

4 實驗結果與分析

4.1 實驗環境

處理器是 Intel?Core? i5-3470 CPU@3.20 GHz，內存為8.00 GB，Microsoft Windows10的操作系統，系統類型是64位操作系統，x64的處理器，算法編寫和編譯是在Python3.5環境下實現的。

4.2 實驗數據

為了驗證本文改進算法對于聚類的有效性，在實驗中選取了UCI數據庫中的Wine、Hayes-Roth、Iris、Tae、Heart-stalog、Ionosphere、Haberman數據集來進行實驗分析，這七個數據集的維度從幾維到十幾維不等，數據集的大小從幾百到上千不等，從而反映出改進算法在不同數據維度和大小上的聚類效果，使得實驗結果更具有說服力。數據集詳細信息見表1。

表1 數據集基本信息

4.3 實驗結果

為了驗證改進算法的有效性，實驗過程中利用傳統K-means算法、文獻[14]算法與改進算法進行對比。實驗中采用了精準率（precision）、召回率（recall）、F1值、輪廓系數（SC）對算法的聚類結果進行評價。精準率是指正確預測為正占全部預測為正的比例，其值一般在[0，1]區間上，值越大表示正確分類的數據越多；召回率是指正確預測為正與全部為正樣本的比值，其值一般在[0，1]區間上；F1值是精準率和召回率的調和均值，其值一般也在[0，1]區間上；輪廓系數[30]是聚類效果好壞的一種評價方式，SC的值在[?1，1]區間上，值越大則表示聚類的結果與真實情況越相近。其中，數據對象的輪廓系數（SC）可通過下列公式得到：

其中，a(i)表示第i個數據對象到所它屬于的簇中其他點距離的平均距離，b(i)表示第i個數據對象到所有非它本身所在簇的點的平均距離的最小值，S(i)表示任意一個數據對象的輪廓系數。

另外，精準率、召回率、F1值的計算公式為：

其中，P是精準率，R是召回率，Tp：樣本為正，預測結果為正。Fp：樣本為負，預測結果為正。Tn：樣本為負，預測結果為負。Fn：樣本為正，預測結果為負。

為了更好地調節參數，首先需了解參數對結果的影響并對其性能進行測試，測試結果如圖2所示。

為了驗證改進算法的聚類效果，采用UCI數據集中常見的七組數據集作為實驗數據，每組數據分別測試5次，得到傳統K-means算法、K-means++、文獻[14]算法、本文改進算法聚類結果比較見表2～表4。

圖2 參數的性能變化

表2 聚類結果穩定性和準確性比較

表3 各算法在UCI數據集上的SC和F1結果比較

表4 各算法在UCI數據集上的聚類時間比較

4.4 結果分析

從表2中可以看出，在Wine、Hayes-Roth、Iris、Tae數據集中本文改進算法的聚類結果穩定性和準確率明顯比K-means++、文獻[14]算法、傳統K-means算法的效果要好，在Heart-stalog、Ionosphere、Haberman數據集中，本文改進算法的聚類結果穩定性和準確率與K-means++、傳統K-means算法相比效果要好，與文獻[14]算法相比效果略低。另外，在表2中，改進算法初始聚類中心具有唯一性且敏感度更低，結合表1數據信息，Wine、Hayes-Roth、Iris、Tae數據集樣本較小且密度差異較大，其他幾個樣本較大，因此可推斷本文改進算法可能更加適用于小樣本和密度差異較大的數據集。對于K-means算法，不同的初始聚類中心會有不同的結果，且結果浮動較大，效果也不明顯，而本文算法的初始中心具有唯一性，且最終的聚類效果也較好。從表3可以看出，對于同一數據集本文改進算法聚類結果的輪廓系數都大于或等于傳統K-means算法、K-means++、文獻[14]算法的輪廓系數，而且對于F1值本文算法較其他三種算法效果更明顯。最后，從表4中的數據可以看出，本文算法的時間復雜度較高，算法運行的時間長，不利于提高算法的運行效率。綜上對表2和表3的分析，可以得出本文改進算法是可行、合理和有效的。

5 改進算法敏感性分析

本文采用UCI數據集中常用的Iris、Wine、Hayes-Roth和Tae驗證改進算法初始聚類中心的敏感性，分別將每個數據集聚為多類，每種情況分別生成20組初始聚類中心進行測試，與傳統K-means算法、K-means++以及文獻[14]算法相比較，實驗結果采用最終的聚類結果有多少種以及每個簇類中心與其余點的均值之和（ASSE）評價算法的初始聚類中心的敏感性，分析該改進算法初始聚類中心對于聚類結果的影響情況。最終的敏感性分析情況見表5。從表5可看出，對于同一數據集改進算法的聚類結果更穩定，且效果也較好，說明改進算法的敏感性更低，抗干擾能力更強。

表5 算法敏感性分析

圖3 各算法收斂性比較

6 改進算法收斂性和復雜度分析

改進算法的收斂速率主要取決于初始聚類中心的選取和聚類數目的多少。本文采用了四個真實UCI數據集：Iris、Wine、Hayes-Roth和Tae進行實驗，當保持每一個數據集相同的簇類數目時，對不同算法在達到同一精度時的迭代次數和運行時間進行比較，每個數據集在不同算法下的迭代次數和的運行速率，如圖3所示。從圖3（a）可以看出，在每個數據集中改進算法的迭代次數比K-means、K-means++和文獻[14]算法的迭代次數都較高一些，說明了改進算法達到同一精度時更晚收斂，由圖3（b）可知，在每個數據中改進算法的運行時間比K-means、K-means++和文獻[14]算法的運行時間都略長，說明了改進算法達到同一精度時運行時間更長。另外，從圖3（a）和（b）可看出Iris、Wine和Tae三個數據集的運行速率比Hayes-Roth快，那是因為前三個數據集的數據量大；Iris、Wine和Tae三個數據集的迭代次數比Hayes-Roth多，那是因為前三個數據集的數據結構更加復雜。該實驗說明算法的收斂速率受多個因素的影響。本文的改進算法主要是在初始聚類中心選取時增加了優化過程，因此其復雜度主要體現：一是改進算法的時間復雜度為O(n(k+s-1)-s2+k×m×d×n)與傳統K-means算法的時間復雜度(O(n×m×d×k)相比更長，二是空間復雜度為O(s×m+n×m)與傳統K-means算法的空間復雜度(O(n×m)相比更大，式中n為數據對象數目，k為簇類數，m為每個元素字段個數，d為迭代次數，s為集合空間的數據對象數目。

7 結束語

傳統K-means聚類算法廣泛運用于數據挖掘領域，隨著大數據信息時代的到來，該算法已不能滿足數據挖掘的需要，為了提高算法的聚類效果，本文提出一種改進K-means聚類算法。實驗表明，改進算法的初始聚類中心穩定，消除了初始聚類中心的敏感性，且通過比較聚類評價指數的值得到改進算法的聚類效果更好。另外，本文算法的提出，為高密度差異數據集的處理提供了一個更加高效的方法。本文只對初始聚類中心的影響和樣本數據的密度差異兩方面進行了相關研究，還有許多的方面有待于去研究和思考，基于此本研究的下一步就是對該算法的收斂性和復雜度做出改進，探索一種更好的方式提高算法的效率。