重心隨機(jī)漂移KMeans聚類算法的設(shè)計(jì)

尹曉麗

(山西大學(xué)商務(wù)學(xué)院 基礎(chǔ)教學(xué)部,太原 030006)

重心隨機(jī)漂移KMeans聚類算法的設(shè)計(jì)

尹曉麗

(山西大學(xué)商務(wù)學(xué)院 基礎(chǔ)教學(xué)部,太原 030006)

利用KMeans聚類算法進(jìn)行聚類過(guò)程中，有可能會(huì)產(chǎn)生孤立聚點(diǎn)，這種情況一旦發(fā)生，會(huì)嚴(yán)重影響算法的聚類效果。為避免產(chǎn)生孤立聚點(diǎn)，本文改進(jìn)了KMeans聚類算法，設(shè)計(jì)了一類重心隨機(jī)漂移(Center Random Drift，簡(jiǎn)稱CRD)KMeans聚類算法。該算法會(huì)首先判斷生成的聚點(diǎn)是否是孤立聚點(diǎn)，利用CRD算法對(duì)孤立聚點(diǎn)進(jìn)行替換，從而有效避免了孤立聚點(diǎn)的產(chǎn)生。通過(guò)在Matlab環(huán)境下進(jìn)行圖像聚類對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，針對(duì)色彩豐富的圖片，新算法和傳統(tǒng)KMeans算法性能沒(méi)有明顯差異，而針對(duì)圖片色彩比較單一的圖片，傳統(tǒng)的KMeans聚類算法聚類效果不佳，新算法依然可以有效聚類。

KMeans聚類；機(jī)器學(xué)習(xí)；CRD KMeans聚類；Matlab

0 引言

隨著人工智能、物聯(lián)網(wǎng)以及互聯(lián)網(wǎng)的發(fā)展，獲取大規(guī)模數(shù)據(jù)變得越來(lái)越容易，各種數(shù)據(jù)平臺(tái)的快速發(fā)展逐漸奠定了當(dāng)代大數(shù)據(jù)應(yīng)用的基礎(chǔ)[1]。對(duì)大量數(shù)據(jù)進(jìn)行初步的加工往往要求將某些相似的數(shù)據(jù)進(jìn)行分類，聚類是一種利用數(shù)據(jù)的分布特點(diǎn)進(jìn)行數(shù)據(jù)加工的常用技術(shù)。在人工智能應(yīng)用中，聚類算法屬于無(wú)監(jiān)督學(xué)習(xí)的一種。KMeans聚類是著名的聚類算法之一，其簡(jiǎn)潔、高效使其成為科技工作者最青睞的聚類工具[2]。

針對(duì)傳統(tǒng)KMeans聚類算法隨機(jī)選取初始聚類中心造成聚類精度及效率較低的問(wèn)題，近年來(lái)，有大量相關(guān)的研究成果發(fā)表。文獻(xiàn)[3-6]討論了KMeans聚類算法在不同編程環(huán)境的實(shí)現(xiàn)問(wèn)題。文獻(xiàn)[7]利用了遺傳算法的全局尋優(yōu)能力，對(duì)K均值算法進(jìn)行改進(jìn)，以克服傳統(tǒng)K均值算法的局部性和對(duì)初始中心的敏感性。文獻(xiàn)[8]采用密度敏感的相似性度量來(lái)計(jì)算對(duì)象的密度，啟發(fā)式生成樣本初始中心；文獻(xiàn)[9]提出通過(guò)計(jì)算每個(gè)數(shù)據(jù)對(duì)象的密度參數(shù)，然后選取處于高密度分布的點(diǎn)作為初始距離中心；文獻(xiàn)[10]提出基于密度參數(shù)和距離理論的初始聚類中心的確定和孤立點(diǎn)的判斷方法，對(duì)孤立點(diǎn)問(wèn)題給出了解決辦法；文獻(xiàn)[11]采用僅對(duì)代表性數(shù)據(jù)點(diǎn)而非數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)進(jìn)行迭代聚類的方法，能夠在保證聚類質(zhì)量的前提下，有效提高聚類效率；文獻(xiàn)[12]則利用擬蒙特卡洛(Quasi-Monte Carlo,QMC)方法序列分布的超均勻性特點(diǎn)，對(duì)整個(gè)樣本空間中的樣本分布進(jìn)行采樣估計(jì)，從而得到初始聚類中心。上述算法在初始聚點(diǎn)的選取方面做了有效的改進(jìn)，取得了較好的效果，但一定程度上增加了算法的復(fù)雜度，本文設(shè)計(jì)的算法將在保持傳統(tǒng)KMeans聚類算法簡(jiǎn)單實(shí)用的特點(diǎn)基礎(chǔ)上，解決隨機(jī)選擇初始聚點(diǎn)導(dǎo)致的聚類效率較低的問(wèn)題，并通過(guò)圖像聚類實(shí)驗(yàn)對(duì)算法的有效性進(jìn)行了驗(yàn)證。

1 孤立聚點(diǎn)分析

KMeans聚類算法的實(shí)現(xiàn)步驟是先選k個(gè)點(diǎn)作為初始聚點(diǎn)，然后對(duì)所有的點(diǎn)進(jìn)行一次遍歷，為每個(gè)點(diǎn)尋找一個(gè)最近的聚點(diǎn)，實(shí)現(xiàn)所有點(diǎn)按聚點(diǎn)進(jìn)行分類，然后重新計(jì)算每類點(diǎn)的均值作為新的聚點(diǎn)，重復(fù)這個(gè)過(guò)程直到各個(gè)數(shù)據(jù)點(diǎn)與所屬聚點(diǎn)的距離的平方和達(dá)到最小(這也是評(píng)價(jià)Kmeans算法最后聚類效果的評(píng)價(jià)標(biāo)準(zhǔn))就能實(shí)現(xiàn)所有點(diǎn)的聚類。但有些情況下會(huì)出現(xiàn)下面定義的孤立聚點(diǎn)。

定義1. 若隨機(jī)生成的聚點(diǎn)中，存在聚點(diǎn)使得所有點(diǎn)都不屬于該聚點(diǎn)，則稱該聚點(diǎn)為孤立聚點(diǎn)。

圖1 孤立聚點(diǎn)示意

如圖1所示，p1, p2是原始點(diǎn)集，c1, c2是隨機(jī)生成的聚點(diǎn)，因?yàn)閜1, p2都離c1更近，所以顯然c2是孤立聚點(diǎn)。

2 CRD-KMeans聚類算法

2.1 算法核心思想

設(shè)p1,p2,…pm是待聚類點(diǎn)集，z1,z2,…,zk是隨機(jī)設(shè)置的k個(gè)聚點(diǎn)，不妨設(shè)前k-1個(gè)聚點(diǎn)是正常聚點(diǎn)，只有zk是孤立聚點(diǎn)。則采用以下方法對(duì)zk進(jìn)行更新：

其中，ai是滿足以下要求的一組隨機(jī)數(shù)：

(1)0

當(dāng)隨機(jī)生成的聚點(diǎn)中包含多個(gè)孤立聚點(diǎn)時(shí)，可利用非孤立聚點(diǎn)，重復(fù)采用上述方法依次更新孤立聚點(diǎn)，從而生成新的一組聚點(diǎn)。

注1：ai為滿足(2.1-2.2)約束的隨機(jī)取值保證了代替所有孤立聚點(diǎn)的新聚點(diǎn)都是非孤立聚點(diǎn)的隨機(jī)凸組合，故將改算法命名為重心隨機(jī)漂移KMEAN聚類算法(簡(jiǎn)稱CRD-KMeans)。

2.2 設(shè)計(jì)步驟

CRD-KMeans聚類算法的設(shè)計(jì)分為以下幾個(gè)步驟：

(1)初始化，即創(chuàng)建對(duì)象集X，設(shè)置聚點(diǎn)數(shù)目k，在X中隨機(jī)選取k個(gè)對(duì)象作為初始聚類點(diǎn)；

(2)按聚點(diǎn)分類，即為每個(gè)數(shù)據(jù)對(duì)象計(jì)算最接近的聚類中心，完成針對(duì)當(dāng)前聚點(diǎn)的分類；

(3)利用重心隨機(jī)漂移算法更新可能產(chǎn)生的孤立聚點(diǎn)；

(4)為各組對(duì)象重新計(jì)算平均值，作為新的聚點(diǎn)；

(5)設(shè)定迭代中止條件，一般設(shè)置為當(dāng)各個(gè)像素點(diǎn)與所在類的距離的平方和更新幅度小于閾值(tol)時(shí)停止迭代。

反復(fù)執(zhí)行(2)-(4)，直至滿足終止條件。

2.3 算法核心代碼

以下是實(shí)現(xiàn)更新孤立聚點(diǎn)的偽代碼：

{ st=[];

j=0;

for i=1:k//k表示聚點(diǎn)數(shù)目

if notEmpty(Z(i))//如果第i個(gè)聚點(diǎn)不是孤立聚點(diǎn)，執(zhí)行下面的代碼：

st=[st;Z(i)];//將非孤立聚點(diǎn)保存在st中

j=j+1;//j用于記錄非孤立聚點(diǎn)數(shù)

end

end

for i=1:k

if isEmpty(Z(i))//如果第i個(gè)聚點(diǎn)是孤立聚點(diǎn)，執(zhí)行下面的代碼

a=rand(1,j);//生成一個(gè)j維隨機(jī)行向量，元素為隨機(jī)正數(shù)

a=a/sum(a); //將a化為單位向量

Z(i)=a*st;//利用矩陣運(yùn)算生成新聚點(diǎn)代替原來(lái)的孤立聚點(diǎn)

end

end

}

其中，Z是聚點(diǎn)集，isEmpty(Z(i))和notEmpty(Z(i))用于判斷Z(i)是否是孤立聚點(diǎn)，st用于存儲(chǔ)非孤立聚點(diǎn)，a為滿足約束(2.1-2.2)的隨機(jī)行向量，該算法可實(shí)現(xiàn)將全部孤立聚點(diǎn)更新為非孤立聚點(diǎn)的隨機(jī)凸組合。

3 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)采用了兩張圖片，一張色彩比較豐富，另一張色彩比較簡(jiǎn)單。分別針對(duì)兩張圖片用傳統(tǒng)KMeans算法和本文設(shè)計(jì)的CRD-KMeans算法進(jìn)行了兩組實(shí)驗(yàn)。具體步驟是：對(duì)圖片的像素點(diǎn)進(jìn)行聚類，用聚點(diǎn)代替像素點(diǎn)重構(gòu)圖像。

實(shí)驗(yàn)參數(shù)設(shè)置及運(yùn)行結(jié)果如表1所示。

表1 實(shí)驗(yàn)參數(shù)設(shè)置及運(yùn)行結(jié)果

表1中，tol表示迭代終止的閾值(即J的改變小于tol時(shí)迭代終止)；K表示聚點(diǎn)個(gè)數(shù)；N表示迭代結(jié)束后進(jìn)行迭代的總次數(shù)；J表示迭代結(jié)束后各個(gè)像素點(diǎn)與所在類的距離的平方和。相同條件下，J越小越好。

圖2 針對(duì)第一張圖的實(shí)驗(yàn)結(jié)果

圖3 針對(duì)第二張圖的實(shí)驗(yàn)結(jié)果

表1和圖2表明，針對(duì)色彩較豐富的圖片，兩種算法都進(jìn)行了64次迭代，最終形成10個(gè)聚點(diǎn)，各個(gè)像素點(diǎn)與所在類的距離的平方和都為1.4094e+07，兩種算法的聚類效果沒(méi)有明顯區(qū)別。表1的數(shù)據(jù)顯示，針對(duì)色彩比較簡(jiǎn)單的圖片，實(shí)驗(yàn)設(shè)定聚點(diǎn)個(gè)數(shù)都為4，傳統(tǒng)的KMeans算法迭代3次后迭代步驟結(jié)束，各個(gè)像素點(diǎn)與所在類的距離的平方和為2.2646e+08；而CRD-KMeans算法迭代了4次，J的值為4.2869e+05，明顯優(yōu)于傳統(tǒng)KMeans算法。圖3的實(shí)驗(yàn)結(jié)果直觀地表明CRD-KMeans算法很好地完成了聚類。

4 結(jié)語(yǔ)

本文設(shè)計(jì)的CRD-KMeans算法保持了傳統(tǒng)的KMeans聚類算法簡(jiǎn)單高效的特點(diǎn)，同時(shí)解決了傳統(tǒng)KMeans聚類算法可能產(chǎn)生孤立聚點(diǎn)從而導(dǎo)致聚類效果不佳的問(wèn)題。雖然傳統(tǒng)的KMeans聚類算法設(shè)定足夠大的聚點(diǎn)數(shù)k也可以在一定程度上避免出現(xiàn)孤立聚點(diǎn)導(dǎo)致的聚類異常，但增加了計(jì)算量和人工試錯(cuò)的成本。在數(shù)據(jù)規(guī)模較大的情況下，CRD-KMeans聚類算法的優(yōu)勢(shì)更加明顯。因此，CRD-KMeans聚類算法比傳統(tǒng)的KMeans聚類算法適應(yīng)范圍更廣，更具有實(shí)用性。

[1] 王若倪,趙慧玲. 大數(shù)據(jù)技術(shù)發(fā)展趨勢(shì)及燈塔大數(shù)據(jù)行業(yè)應(yīng)用平臺(tái)[J]. 中興通訊技術(shù), 2016, 22(3): 57-61.

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

[3] 吳再龍,張?jiān)迫?徐建良，等. 基于OpenCL的Kmeans算法的優(yōu)化研究[J]. 計(jì)算機(jī)科學(xué)與探索, 2014, 8(10): 1162-1176.

[4] 陳壽文,李明東. 基于面向?qū)ο笏枷隟Means算法實(shí)現(xiàn)[J]. 滁州學(xué)院學(xué)報(bào), 2008, 10(3): 42-44.

[5] 孫宇鋒. 基于Matlab的模糊聚類分析及應(yīng)用[J]. 韶關(guān)學(xué)院學(xué)報(bào)(自然科學(xué)版), 2006, 27(9):1-4.

[6] 宋麗紅. K-均值聚類的Matlab仿真設(shè)計(jì)[J]. 實(shí)驗(yàn)技術(shù)與管理, 2010, 27(10): 101-103.

[7] 賴玉霞,劉建平,楊國(guó)興. 基于遺傳算法的K均值聚類分析[J]. 計(jì)算機(jī)工程, 2008, 34(20): 200-202.

[8] 汪中,劉貴全,陳恩紅. 一種優(yōu)化初始中心點(diǎn)的K-means算法[J]. 模式識(shí)別與人工智能, 2009, 22(2): 299-304.

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

[10] 楊金花,劉顯為. K-means聚類算法初始中心選擇研究[J]. 河南科學(xué), 2016, 34(3): 348-351.

[11] 趙文沖,蔡江輝,趙旭俊,等. 一種影響空間下的快速K-means聚類算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2016, 37(9): 2060-2064.

[12] 莊瑞格, 倪澤邦, 劉學(xué)藝.基于擬蒙特卡洛的K均值聚類中心初始化方法[J].濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2017, 31(1):35-41.

責(zé)任編輯：程艷艷

Design of Center Random Drift (CRD) KMeans Clustering Algorithm

YIN Xiaoli

(Department of Basic Teaching, Business College of Shanxi University, Taiyuan 030006, China)

KMeans clustering algorithm will probably generate isolated points during clustering process, once this happens, it will seriously deteriorate the effect of the clustering algorithm. In order to avoid generating isolated points, an algorithm called center random drift (CRD) KMeans clustering is designed, which will firstly determine whether the cluster point is isolated, and if it is, it will be replaced by using CRD algorithm, so as to avoid the isolated point effectively. Through comparative experiments of image clustering in Matlab environment, it is found that there is no significant difference between the new algorithm and the traditional KMeans algorithm for the colorful pictures, while for a picture with a single color, the traditional KMeans clustering algorithm’s clustering effect is poor, but the new algorithm can still work effectively.

KMeans clustering; machine learning; CRD KMeans clustering; Matlab

2017-04-20

國(guó)家社會(huì)科學(xué)規(guī)劃基金(16BTJ034)

尹曉麗(1984-)，女，山西臨汾人，講師、碩士，主要從事自然語(yǔ)言處理、智能控制方面研究。

TP301

A

1009-3907(2017)08-0035-04