基于SSE的全局最優(yōu)K-means算法

董炎焱

摘要 傳統(tǒng)的K-means聚類算法對(duì)初值敏感，隨機(jī)的初始聚類中心會(huì)造成簇的不穩(wěn)定。本文采取全局搜索的方法避免了局部最優(yōu)解，實(shí)驗(yàn)證明，采用SSE作為分類的標(biāo)準(zhǔn)，可以提高簇的穩(wěn)定性。

[關(guān)鍵詞]K-means聚類SSE 全局最優(yōu)解 初始聚類中心

1 引言

聚類分析能夠?qū)崿F(xiàn)數(shù)據(jù)的歸類，是數(shù)據(jù)挖掘的重要方法。K-means在聚類算法中的收斂速度較快，可以對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，產(chǎn)生數(shù)據(jù)的基本分布規(guī)律，但是傳統(tǒng)的K-means算法中人為確定聚類數(shù)k，初始聚類中心的k個(gè)點(diǎn)隨機(jī)選取，均影響到了聚類結(jié)果。本文針對(duì)k個(gè)聚類點(diǎn)的選取提出改進(jìn)，增加K-means算法的穩(wěn)定性。

2 K-means聚類算法

2.1 傳統(tǒng)的K-means算法

設(shè)有數(shù)據(jù)點(diǎn)集{xu），xu是u維空間的一個(gè)點(diǎn)，u表示全部屬性個(gè)數(shù)，人工設(shè)定聚類數(shù)為k：

（1）在{Xu}中任取k個(gè)初始聚類中心點(diǎn)，記為{wu}，k

（2）計(jì)算Xu和Wu的歐氏距離，歸于最近的簇;

（3）更新聚類中心點(diǎn)，以各簇的均值代替原聚類中心點(diǎn);

（4）重復(fù)（2）（3），直到連續(xù)兩次聚類中心的距離小于或等于某閾值。

2.2 K-means的收斂測(cè)度SSE

聚類效果體現(xiàn)于聚類函數(shù)SSE的值，若SSE的值越小，認(rèn)為聚類效果越好。設(shè)SSE=∑∑lI Xu-Wu || 2，對(duì)Wu求偏導(dǎo)數(shù)，并取為0，得到Wu=1/m∑Xu，m是以wu為聚類中心的點(diǎn)個(gè)數(shù)，1/m∑Xu就是SSE函數(shù)在wu類的最優(yōu)解，每一次迭代，SSE將減小，最終趨于收斂。

2.3 傳統(tǒng)K-means的局限性

聚類數(shù)人為確定，在大多數(shù)情況下，以人的先驗(yàn)知識(shí)不足以分清類別，要么k值偏小，忽略差別，要么k值偏大，過(guò)分強(qiáng)調(diào)類別，因此k值的選取需要多次的嘗試，得到較為合理的聚類數(shù)。

SSE是非凸函數(shù)，由于初始聚類中心的選取是隨機(jī)的，會(huì)形成局部最小值，不能保證是全局最小值，可多次更新初始聚類中心，重復(fù)算法，取其中最小的SSE。

3 全局最優(yōu)解的K-means聚類算法

3.1 算法原理

設(shè)數(shù)據(jù)集點(diǎn){xu}，k為聚類個(gè)數(shù)，{wu）為聚類中心點(diǎn)集：

（1）k=1，求解1/m∑Xu，其中m為數(shù)據(jù)點(diǎn)個(gè)數(shù)，得到第一個(gè)初始聚類中心wu1;

（2）k=2，將第一個(gè)聚類中心wu1分別與xul，xu2，Xu3，……xum進(jìn)行K-means聚類，分別求出每次聚類的SSE.，找到min{SSEi），記錄與之對(duì)應(yīng)的第二個(gè)聚類中心wu2;

（3）k=3，將wu1、Wu2分別與xu1，Xu2，Xu3，……xum進(jìn)行K-means聚類，記錄與min{SSEi）對(duì)應(yīng)的第三個(gè)聚類中心Wu3;

（4）依次類推，其中k

3.2 對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)來(lái)源為中華人民共和國(guó)統(tǒng)計(jì)局發(fā)布的“第六次人口普查”中“1—8各地區(qū)分性別、受教育程度的6歲及以上人口”的統(tǒng)計(jì)數(shù)據(jù)，選用該數(shù)據(jù)的原因是不考慮異常數(shù)據(jù)對(duì)實(shí)驗(yàn)的影響，取對(duì)數(shù)后進(jìn)行聚類分析。

傳統(tǒng)的K-means算法對(duì)初始聚類中心點(diǎn)隨機(jī)選取，得到的聚類結(jié)果不穩(wěn)定，設(shè)k=3，三次實(shí)驗(yàn)分別取不同的初始聚類中心，結(jié)果如表l。

實(shí)驗(yàn)四為全局最優(yōu)解的K-means聚類算法，第一個(gè)初始聚類中心是數(shù)據(jù)集的均值wul=6.73，數(shù)據(jù)集的每個(gè)點(diǎn)分別作為第二個(gè)初始聚類中心進(jìn)行K-means聚類，得到SSE，如表2。

將表2的數(shù)值以圖形表示，如圖1。

3.3 實(shí)驗(yàn)分析

傳統(tǒng)的K-means聚類算法對(duì)初始聚類中心選取敏感，造成簇的不穩(wěn)定性。分析數(shù)據(jù)集{xu），x=6.73，σ=0.462，x±3σ的范圍是（5.344，8.116），當(dāng)數(shù)據(jù)點(diǎn)在這個(gè)范圍內(nèi)時(shí)，隨機(jī)選擇的初始聚類中心對(duì)聚類的穩(wěn)定性影響小，否則會(huì)產(chǎn)生奇異的簇，如實(shí)驗(yàn)二。

實(shí)驗(yàn)四中如果按照全局最優(yōu)解的理論算法，需要找到min{SSE），才能確定第二個(gè)聚類中心，但是通過(guò)數(shù)據(jù)點(diǎn)與SSE的圖1就可以發(fā)現(xiàn)數(shù)據(jù)點(diǎn)己明顯的分為三類，三個(gè)簇的SSE分別是0.585，0.847，2.204，數(shù)據(jù)點(diǎn)小于Wul，SSE就大。將SSE所對(duì)應(yīng)的聚類中心作為初始聚類中心進(jìn)行傳統(tǒng)的K-means聚類，迭代5次后，最終的聚類中心是6.57，7.05，5.65，每個(gè)簇的SSE是0.32，0.36，0.31。實(shí)驗(yàn)四與實(shí)驗(yàn)一、三的最終聚類中心和SSE接近。

3.4 全局最優(yōu)解的K-means聚類算法的改進(jìn)

設(shè)數(shù)據(jù)集點(diǎn){xu），k為聚類個(gè)數(shù)，{wu}為聚類中心點(diǎn)集：

（1）k=1，求解1/m∑Xu，其中m為數(shù)據(jù)點(diǎn)個(gè)數(shù)，得到第一個(gè)初始聚類中心wu1;

（2）將第一個(gè)聚類中心wul分別與wu1，Wu2，Wu3，……xum進(jìn)行K-means聚類，分別求出每次聚類的SSEi，按照SSEi進(jìn)行分類，相同SSE，的歸為一簇;

（3）將不同簇的最終聚類中心作為初始聚類中心，進(jìn)行K-means聚類，得到聚類結(jié)果。

4 結(jié)論

傳統(tǒng)的K-means聚類高效而簡(jiǎn)單，應(yīng)用范圍廣，但是隨機(jī)的初始聚類中心和局部最優(yōu)的存在影響了聚類的穩(wěn)定性。本文從結(jié)合前人的研究成果對(duì)全局最優(yōu)解的K-means聚類提出改進(jìn)，縮短多次全局搜索的時(shí)間，增加聚類的穩(wěn)定性。

參考文獻(xiàn)

[1]謝娟英，蔣帥，王春霞，張琰，謝維信，一種改進(jìn)的全局K-均值聚類算法[J].陜西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，38 （02）：18-22

[2]王曉東，張姣，薛紅，基于蝙蝠算法的K均值聚類算法[J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2016，34 （06）：805-810.

[3]周世兵，徐振源，唐旭.新的K一均值算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46 （16）：27-31.

[4]Park H S，Jun C H.A simple and fastalgorithm for K-medoids clustering[J]. Expert SystemswithApplications，2009， 36 （02）： 3336-3341.

[5]王紅睿，趙黎明，裴劍，均衡化的改進(jìn)K均值聚類法[J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2006，24 （03）：172-176.