優(yōu)化初始聚類中心的K-means聚類算法

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

1.江西中醫(yī)藥大學(xué) 計(jì)算機(jī)學(xué)院，南昌 330004

2.江西中醫(yī)藥大學(xué) 藥學(xué)院，南昌 330004

1 引言

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

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

2 改進(jìn)算法的基本思想

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

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

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

定義1兩個(gè)數(shù)據(jù)對象間的歐氏距離為：

其中，xi,xj為數(shù)據(jù)對象，xil為xi的l個(gè)特征屬性，xjl為xj的第l個(gè)特征屬性。

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

其中，Centerk表示第k個(gè)簇類的中心，Ck表示第k個(gè)簇類，xi∈Ck表示屬于簇類Ck的數(shù)據(jù)對象。

定義3點(diǎn)與樣本集合間的距離為點(diǎn)與集合內(nèi)數(shù)據(jù)對象均值間的距離：

其中，M表示距離最短的兩點(diǎn)組成的集合，D′表示刪除集合M中數(shù)據(jù)后的樣本數(shù)據(jù)集，centerMm表示第m個(gè)集合Mm的均值。

定義4目標(biāo)函數(shù)即誤差平方和為：

定義5某一數(shù)據(jù)對象與其他簇類內(nèi)所有數(shù)據(jù)對象間的距離和為：

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

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

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

（2）計(jì)算樣本集合Mm內(nèi)所有數(shù)據(jù)對象的均值。

（3）根據(jù)公式（3）計(jì)算數(shù)據(jù)集D中每個(gè)對象與樣本集合Mm間的距離，找到距離最近的點(diǎn)加入集合Mm，并將它從數(shù)據(jù)集D中刪除。

（4）計(jì)算樣本集合Mm內(nèi)所有數(shù)據(jù)對象的均值。

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

（6）如果m

例如有一個(gè)2維數(shù)據(jù)集D，數(shù)據(jù)大小為14，且它的數(shù)據(jù)分布如圖1所示。

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

圖1 數(shù)據(jù)分布圖

3 改進(jìn)算法的具體描述

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

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

輸出：聚類結(jié)果。

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

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

（3）根據(jù)公式（2）重新計(jì)算每個(gè)簇類的中心。

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

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

（6）算法結(jié)束。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

處理器是 Intel?Core? i5-3470 CPU@3.20 GHz，內(nèi)存為8.00 GB，Microsoft Windows10的操作系統(tǒng)，系統(tǒng)類型是64位操作系統(tǒng)，x64的處理器，算法編寫和編譯是在Python3.5環(huán)境下實(shí)現(xiàn)的。

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

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

表1 數(shù)據(jù)集基本信息

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

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

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

另外，精準(zhǔn)率、召回率、F1值的計(jì)算公式為：

其中，P是精準(zhǔn)率，R是召回率，Tp：樣本為正，預(yù)測結(jié)果為正。Fp：樣本為負(fù)，預(yù)測結(jié)果為正。Tn：樣本為負(fù)，預(yù)測結(jié)果為負(fù)。Fn：樣本為正，預(yù)測結(jié)果為負(fù)。

為了更好地調(diào)節(jié)參數(shù)，首先需了解參數(shù)對結(jié)果的影響并對其性能進(jìn)行測試，測試結(jié)果如圖2所示。

為了驗(yàn)證改進(jìn)算法的聚類效果，采用UCI數(shù)據(jù)集中常見的七組數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，每組數(shù)據(jù)分別測試5次，得到傳統(tǒng)K-means算法、K-means++、文獻(xiàn)[14]算法、本文改進(jìn)算法聚類結(jié)果比較見表2～表4。

圖2 參數(shù)的性能變化

表2 聚類結(jié)果穩(wěn)定性和準(zhǔn)確性比較

表3 各算法在UCI數(shù)據(jù)集上的SC和F1結(jié)果比較

表4 各算法在UCI數(shù)據(jù)集上的聚類時(shí)間比較

4.4 結(jié)果分析

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

5 改進(jìn)算法敏感性分析

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

表5 算法敏感性分析

圖3 各算法收斂性比較

6 改進(jìn)算法收斂性和復(fù)雜度分析

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

7 結(jié)束語

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