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

董炎焱

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

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

1 引言

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

2 K-means聚類算法

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

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

（1）在{Xu}中任取k個初始聚類中心點，記為{wu}，k

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

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

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

2.2 K-means的收斂測度SSE

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

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

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

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

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

3.1 算法原理

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

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

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

（3）k=3，將wu1、Wu2分別與xu1，Xu2，Xu3，……xum進行K-means聚類，記錄與min{SSEi）對應的第三個聚類中心Wu3;

（4）依次類推，其中k

3.2 對比實驗

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

傳統(tǒng)的K-means算法對初始聚類中心點隨機選取，得到的聚類結果不穩(wěn)定，設k=3，三次實驗分別取不同的初始聚類中心，結果如表l。

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

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

3.3 實驗分析

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

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

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

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

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

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

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

4 結論

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

參考文獻

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

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

[3]周世兵，徐振源，唐旭.新的K一均值算法最佳聚類數(shù)確定方法[J].計算機工程與應用，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]王紅睿，趙黎明，裴劍，均衡化的改進K均值聚類法[J].吉林大學學報（信息科學版），2006，24 （03）：172-176.