基于優(yōu)化初始聚類中心的Kmeans聚類算法

摘?要：針對(duì)傳統(tǒng)的Kmeans算法運(yùn)行的結(jié)果依賴于初始的聚類數(shù)目和聚類中心，本文提出了一種基于優(yōu)化初始聚類中心的Kmeans算法。該算法通過量化樣本間距離和聚類的緊密性來(lái)確定聚類數(shù)目K值;根據(jù)數(shù)據(jù)集的分布特征來(lái)選取相距較遠(yuǎn)的數(shù)據(jù)作為初始聚類中心，避免了傳統(tǒng)Kmeans算法的聚類數(shù)目和聚類中心的隨機(jī)選取。UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)數(shù)據(jù)集的實(shí)驗(yàn)證明，本文所提出的改進(jìn)的聚類算法獲得了良好的聚類效果，同時(shí)獲得較高的聚類準(zhǔn)確率。

關(guān)鍵詞：聚類;Kmeans聚類;聚類數(shù)目;初始聚類中心

文獻(xiàn)標(biāo)識(shí)碼：A

在模式識(shí)別、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域，聚類算法是很有意義的研究?jī)?nèi)容[1]。物以類聚，聚類是將數(shù)據(jù)集中的數(shù)據(jù)對(duì)象按照對(duì)象間的相似性劃分成若干個(gè)類，使同一類的對(duì)象間差別小，而不同類的對(duì)象間差別大[2]。

Kmeans聚類算法是經(jīng)典且應(yīng)用廣泛的劃分方法之一，具有理論可靠、算法簡(jiǎn)單、收斂速度快、能有效處理大數(shù)據(jù)集等優(yōu)點(diǎn)[3]。但是傳統(tǒng)的Kmeans算法過度依賴于初始條件。初始聚類數(shù)目K值的確定影響了最終的聚類效果和整個(gè)算法的收斂速度。假設(shè)聚類數(shù)目K值已經(jīng)確定，選取不同的初始聚類中心又會(huì)導(dǎo)致不同的聚類結(jié)果，隨機(jī)選取的初始聚類中心點(diǎn)將會(huì)增加最終聚類結(jié)果的隨機(jī)性和不可靠性。由此可見，對(duì)于聚類初始條件優(yōu)化的研究在Kmeans聚類算法改進(jìn)中有著重要的地位。國(guó)內(nèi)外諸多學(xué)者致力于Kmeans算法初始條件的研究，以改善K均值算法的聚類效果[46]。

本文提出一種基于優(yōu)化初始聚類中心的Kmeans算法，該算法在聚類數(shù)目K值的確定上和初始聚類中心的選取上都做了改進(jìn)，避免了傳統(tǒng)Kmeans算法的聚類數(shù)目和聚類中心的隨機(jī)選取。UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試證明，本文所提出的算法具有良好的聚類效果，聚類準(zhǔn)確率高。

1?Kmeans聚類算法

傳統(tǒng)的Kmeans聚類算法用聚類誤差平方和作為衡量聚類效果的準(zhǔn)則函數(shù)。傳統(tǒng)Kmeans算法會(huì)隨機(jī)選擇出K個(gè)數(shù)據(jù)作為最初的聚類中心，然后計(jì)算出數(shù)據(jù)集中剩余數(shù)據(jù)和各聚類中心的距離，根據(jù)距離將其余數(shù)據(jù)分配到各類中，重新確定各個(gè)類簇的新中心點(diǎn)，再分配數(shù)據(jù)集中樣本到新的聚類中心，再計(jì)算各個(gè)類的新中心點(diǎn)，再次分配數(shù)據(jù)集樣本。反復(fù)迭代到準(zhǔn)則函數(shù)收斂為止，也就是聚類中心點(diǎn)不再發(fā)生變化。

2?基于優(yōu)化初始聚類中心的Kmeans聚類算法

2.1?聚類數(shù)目K值的確定

聚類算法是通過量化樣本間距離和聚類的緊密性來(lái)評(píng)價(jià)聚類效果的好壞。具體表示為：同一個(gè)類內(nèi)數(shù)據(jù)間的距離越小越好、不同類間的距離越大越好。本文將同一類簇內(nèi)的差異值和不同類簇間的差異值的比值定義為評(píng)價(jià)聚類效果優(yōu)劣的標(biāo)準(zhǔn)。

將數(shù)據(jù)集所有的類簇內(nèi)距離和定義為Ein，表示每個(gè)類簇中所包含的數(shù)據(jù)樣本到各個(gè)類中心點(diǎn)間的距離之和。類簇內(nèi)距離和Ein的計(jì)算公式表示為：

其中，n是表示數(shù)據(jù)集中所有的樣本數(shù)量，k表示類的個(gè)數(shù)，Ci表示第i個(gè)類簇，x為第i類中的數(shù)據(jù)樣本，Zi表示第i個(gè)類的中心點(diǎn)。類簇內(nèi)距離和Ein值越小，意味著所有類簇中的數(shù)據(jù)樣本越緊湊，聚類的緊密型越好。

另外，還需要計(jì)算各個(gè)類簇中心點(diǎn)相互間的距離作為類簇間距離，類簇間距離定義為Eout，類簇間距離Eout的計(jì)算公式為：

其中，k表示類的數(shù)目，即類簇?cái)?shù)，Ci表示第i個(gè)類簇的聚類中心點(diǎn)，C表示各個(gè)類簇的聚類中心平均值，類簇間距離Eout的值越大，意味著類和類之間的相似度小。

綜合類簇內(nèi)距離和Ein與類簇間距離Eout兩個(gè)值來(lái)評(píng)定聚類效果的優(yōu)劣性，本文將類簇內(nèi)距離和Ein與類簇間距離Eout的比值作為聚類效果的評(píng)價(jià)標(biāo)準(zhǔn)，當(dāng)類簇內(nèi)距離和Ein與類簇間距離Eout的比值越小時(shí)，表示此時(shí)的聚類效果越好。用EE表示聚類效果優(yōu)劣程度的評(píng)價(jià)標(biāo)準(zhǔn)，則EE表示為：

由上式可以得出，EE值為先逐漸變小然后會(huì)慢慢變大，EE值越小，表示聚類的效果越好，當(dāng)EE達(dá)到局部最小值時(shí)，聚類效果最佳，由此可以確定聚類數(shù)目K值。

2.2?算法描述

本文通過聚類數(shù)目K值的確定和優(yōu)化初始聚類中心來(lái)改進(jìn)傳統(tǒng)Kmeans算法。在確定聚類數(shù)目K值時(shí)，隨著EE=Ein/Eout的值不斷變小讓K++，當(dāng)EE值達(dá)到局部最小值時(shí)來(lái)確定K值;優(yōu)化初始聚類中心時(shí)，根據(jù)數(shù)據(jù)集樣本分布的特點(diǎn)，選擇出K個(gè)相距較遠(yuǎn)的數(shù)據(jù)樣本作為初始聚類中心。本文基于優(yōu)化初始聚類中心的Kmeans算法一方面解決了傳統(tǒng)Kmeans算法中聚類數(shù)目K值無(wú)法確定的問題，另一方面解決了傳統(tǒng)算法中隨機(jī)選取初始中心點(diǎn)而造成的局部最優(yōu)問題。

本文基于優(yōu)化初始聚類中心的Kmeans算法具體描述如下：

（1）初始化：K=1，運(yùn)行傳統(tǒng)的Kmeans算法并計(jì)算此時(shí)的EE值;

（2）讓K++，再次運(yùn)行傳統(tǒng)的Kmeans算法并記錄EE;

（3）隨著K的逐漸增大運(yùn)行Kmeans算法，直到EE值出現(xiàn)局部最小值，保留此時(shí)的K值，由此確定聚類數(shù)目K值;

（4）選擇數(shù)據(jù)集中任意一個(gè)數(shù)據(jù)對(duì)象作為第一個(gè)聚類中心點(diǎn);

（5）重復(fù)步驟（4），選取出K個(gè)初始的聚類中心點(diǎn);

（6）計(jì)算數(shù)據(jù)集剩余樣本到離得最近聚類中心的距離，定義該距離為D（X）;

（7）為每個(gè)類重新選擇聚類中心點(diǎn)，此時(shí)選取概率與D（X）的大小成正比，即離原聚類中心越近的點(diǎn)越有可能被選取為新的聚類中心點(diǎn);

（8）重復(fù)步驟（7）直到K個(gè)聚類中心點(diǎn)全部被選出來(lái);

（9）再運(yùn)行傳統(tǒng)的Kmeans聚類算法。

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

本文實(shí)驗(yàn)環(huán)境為：Intel?CPU，8GB內(nèi)存，500G硬盤，Windows10操作系統(tǒng)和MATLAB應(yīng)用軟件。

在UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[7]的Iris等6個(gè)聚類算法常用的測(cè)試數(shù)據(jù)集上對(duì)本文基于優(yōu)化初始聚類中心的改進(jìn)Kmeans算法和傳統(tǒng)Kmeans算法進(jìn)行實(shí)驗(yàn)測(cè)試并比較。UCI數(shù)據(jù)集的描述見表1。

采用聚類誤差平方和、聚類時(shí)間和聚類準(zhǔn)確率、Rand指數(shù)、Jaccard系數(shù)[89]，“Adjusted?Rand?index”參數(shù)[10]對(duì)聚類算法的運(yùn)行結(jié)果進(jìn)行比較分析。表2是本文基于優(yōu)化初始聚類中心的Kmeans算法和傳統(tǒng)Kmeans算法的聚類誤差平方和與聚類時(shí)間比較的結(jié)果。圖1～圖4分別是兩種算法的Rand指數(shù)、Jaccard系數(shù)、“Adjusted?Rand?index”參數(shù)和聚類正確率的比較結(jié)果。

從表2可以看出，在各個(gè)數(shù)據(jù)集上，本文基于優(yōu)化初始聚類中心的Kmeans算法的聚類誤差平方和都小于傳統(tǒng)Kmeans算法，有良好的聚類效果。聚類時(shí)間的比較顯示，本文算法的時(shí)間性能略差于傳統(tǒng)Kmeans算法，分析原因在于本文算法在確定K值和選取聚類中心點(diǎn)時(shí)會(huì)消耗一定的時(shí)間。

圖4顯示，在所有數(shù)據(jù)集上本文基于優(yōu)化初始聚類中心的Kmeans算法的聚類正確率優(yōu)于傳統(tǒng)Kmeans算法。因此，本文算法獲得良好的聚類效果，獲得較高的聚類準(zhǔn)確率。

結(jié)語(yǔ)

本文在分析傳統(tǒng)Kmeans聚類算法不足的基礎(chǔ)上，提出一種基于優(yōu)化初始聚類中心的Kmeans算法。該算法通過量化樣本間距離和聚類的緊密性來(lái)確定聚類數(shù)據(jù)K值，利用數(shù)據(jù)集樣本的分布特征選取相距較遠(yuǎn)的初始聚類中心點(diǎn)，克服了傳統(tǒng)Kmeans算法對(duì)初始聚類中心敏感、聚類效果不理想的缺陷。在UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)數(shù)據(jù)集上的實(shí)驗(yàn)表明：本文基于優(yōu)化初始聚類中心的Kmeans算法有很好的聚類效果，準(zhǔn)確率高，聚類性能優(yōu)于傳統(tǒng)Kmeans算法。

參考文獻(xiàn)：

[1]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008，19（1）：4861.

[2]Han?J?W，Kamber?M.Data?Mining：Concepts?and?Techniques，2nd?ed.[M].Beijing：Chain?machine?Press，2000：383466.

[3]謝娟英，郭文娟，謝維信，等.基于樣本空間分布密度的初始聚類中心優(yōu)化K均值算法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（3）：888892.

[4]韓凌波，王強(qiáng)，蔣正峰，等.一種改進(jìn)的kmeans初始聚類中心選取算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（17）：150152.

[5]黃敏，何中市，邢欣來(lái)，等.一種新的kmeans聚類中心選取算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（35）：132134.

[6]熊忠陽(yáng)，陳若田，張玉芳.一種有效的Kmeans聚類中心初始化方法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（11）：41884190.

[7]Frank?A，Asuncion?A.UCI?machine?learning?repository[EB/OL].Irvine，CA：University?of?California，School?of?Information?and?Computer?Science，2010.http：//archive.ics.uci.edu/ml.

[8]張惟皎，劉春煌，李芳玉.聚類質(zhì)量的評(píng)價(jià)方法[J].計(jì)算機(jī)工程，2005，31（20）：1012.

[9]于劍，程乾生.模糊聚類方法中的最佳聚類數(shù)的搜索范圍[J].中國(guó)科學(xué)（E輯），2002，32（2）：274280.

[10]楊燕，靳蕃，Kamel?M.聚類有效性評(píng)價(jià)綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，41（06）：16311632.

基金項(xiàng)目：甘肅政法大學(xué)校級(jí)青年項(xiàng)目（GZF2019?XQNLW08），甘肅省青年科技基金項(xiàng)目（21JR7RA572），2019年甘肅省高校引進(jìn)和使用優(yōu)質(zhì)在線開放課程項(xiàng)目

作者簡(jiǎn)介：郭文娟（1986—?），女，甘肅武威人，講師，研究方向：智能信息處理。