李燕梅

（滇西科技師范學(xué)院，云南 臨滄 677000）

1 引言

K-均值聚類算法通過迭代算法來解決實際應(yīng)用中出現(xiàn)的聚類問題，并得出聚類誤差的最優(yōu)解，被廣泛應(yīng)用于聚類誤差問題中。K-均值聚類算法采用隨機的方式選擇K個對象作為初始聚類中心，通過迭代算法降低聚類誤差以達到改變聚類中心的目的，屬于一種基于中心點的基礎(chǔ)聚類算法。K-均值聚類算法的弊端在于選取初始聚類中心點相對慎重，進而影響了算法的效率。為得到K-均值聚類算法中聚類誤差的近似最優(yōu)解，需要合理安全初始聚類中心點的位置，確保每個聚類中心點之間存有差異。針對K-均值聚類算法面臨的問題，專家學(xué)者不斷深入研究，以期通過新型算法達到全局最優(yōu)化的目的。但目前采取遺傳算法、模擬算法等技術(shù)來解決該問題還存在一定的漏洞，適用性不強，導(dǎo)致認可度不高。因此，在解決實際問題中使用度最高的聚類算法還是K-均值聚類算法。本文提出基于K-中心點算法的改進思想，將其作為全局K-均值聚類算法的初始聚類中心，最后實現(xiàn)聚類時間短、魯棒性強的目標。

2 K-均值聚類算法

K-均值聚類算法用于解決數(shù)據(jù)聚類問題，由麥克奎因首次提出。K-均值聚類算法具有算法簡單、計算速度快的優(yōu)勢，廣泛應(yīng)用于工業(yè)、科技等領(lǐng)域。K-均值聚類算法處理了含有n個數(shù)據(jù)點集合如X={x1，x2，…，xn}中需要劃分出以K為對象的Cj類簇問題，其中j=1，2，…k。K-均值聚類算法的步驟為：隨機選取K個對象作為初始聚類中心，然后計算每個數(shù)據(jù)點與各個聚類中心之間的距離，并將數(shù)據(jù)點劃分至距離最近的聚類中心內(nèi)，以此形成K個初始聚類。對初始聚類中心根據(jù)聚類中現(xiàn)有的數(shù)據(jù)點重新計算，采用迭代算法進行劃分，當聚類中心數(shù)值不再變化時，說明所有K數(shù)據(jù)對象已全部劃分完畢，進而進行聚類準則函數(shù)收斂，如若數(shù)值還處于變化，則需要繼續(xù)采用迭代算法劃分，直至成功。K-均值聚類算法需要注意使用迭代算法時是對全部數(shù)據(jù)點進行分配，沒有進入聚類中心的數(shù)據(jù)點在下次迭代過程中仍參與分配。當聚類中心不再變化后，說明聚類準則函數(shù)收斂完畢，K-均值聚類算法結(jié)束。

3 全局K-均值聚類算法

全局K-均值聚類算法是給定含有n個數(shù)據(jù)點集合如X={x1，x2，…，xn}，以期將其劃分為以K為對象的Cj類簇問題，其中j=1，2，…k，全局K-均值聚類算法具有全局最優(yōu)算法的優(yōu)勢，無須依托于初始因素，提高了算法的確定性。全局K-均值聚類算法中的局域搜索程序采用K-均值聚類算法，全局K-均值聚類算法采用最優(yōu)化方式在算法運行各個階段添加新的聚類中心，聚類中心的初始值也不再隨機選取。

針對實際應(yīng)用環(huán)節(jié)中出現(xiàn)的K個簇聚類問題，全局K-均值聚類算法的步驟如下：將簇中心的最優(yōu)位置確定為數(shù)據(jù)集的質(zhì)心以此解決一個簇的聚類問題，以此類推，解決n個簇的聚類問題是執(zhí)行n次全局K-均值聚類算法，明確簇的中心初始位置即可。當K-1為第一個聚類中心的最優(yōu)解位置時，將x數(shù)據(jù)點作為第二個簇的初始聚類中心，i=1,2,...,n，運用全局K-均值聚類算法解決n次聚類問題后，得出K-2時的聚類問題解決方法為最優(yōu)解。由此可知，使用全局K-均值聚類算法時，當我們得出（K-1）聚類問題的解決方法時，可以采用類似步驟解決K-均值聚類算法的問題。針對n次對應(yīng)以K為對象的類簇問題，執(zhí)行K-均值聚類算法，明確初始簇聚類中心，得出聚類問題的最優(yōu)解?；谌諯-均值聚類算法的步驟，最終可以得出K個聚類問題的解決方式，當聚類數(shù)目小于K的聚類問題也可采用同類方式予以解決。

全局K-均值聚類算法的優(yōu)勢在于確定類聚中心數(shù)目，為充分發(fā)揮出此優(yōu)勢，需要有效解決各種簇數(shù)目的聚類問題，基于合理的準則來確定K值，不再隨機選擇K對象。因此，應(yīng)用全局K-均值聚類算法可以排除初始類中心點對聚類算法結(jié)果造成的不良影響。但由于全局K-均值聚類算法中的全部K值都需要執(zhí)行K均值算法，計算任務(wù)量大，所以多數(shù)使用者關(guān)心全局K-均值聚類算法應(yīng)用是否過于復(fù)雜，因此在后續(xù)應(yīng)用過程中改進該算法具有重要的作用。

4 基于全局K-均值聚類算法的改進

本文研究一種基于全局K-均值聚類算法的改進，首先需要對全局K-均值聚類算法進行有效掌握。其將K個聚類中心的問題轉(zhuǎn)化為從局域搜索初始狀態(tài)入手。當K=1時，增加一個聚類中心，需要用迭代算法求出K的聚類答案。全局K-均值聚類算法將K-1聚類質(zhì)心作為默認樣本，將K-1的前一個聚類中心作為K-均值聚類算法的最佳初始位置，通過反復(fù)運行全局K-均值聚類算法來確定最佳的初始中心。

圖1 算法流程圖

本文基于全局K-均值聚類算法的算法思想，提出新的初始化方法，將K中心為初始中心的思想融入全局K-均值聚類算法中，來確定下一個聚類中心的初始中心，形成一種新型改進方法。改進后的全局K-均值聚類算法需要針對密集的樣本，找到距離現(xiàn)有簇中心較遠的簇作為樣本，并算出其最優(yōu)初始中心，這樣有利于避免現(xiàn)有簇中心點的干擾，也可以彌補全局K-均值聚類算法計算量較大的弊端。改進后的全局K-均值聚類算法確定聚類中心的初始最優(yōu)位置需要計算一個函數(shù)值，改變了中心選擇的方式，該算法選擇樣本分布密集，且距離現(xiàn)有簇中心較遠的簇作為樣本的最優(yōu)初始位置選擇點，具有相對的科學(xué)合理性。距離過近的樣本簇在使用全局K-均值聚類算法時難免重復(fù)運算問題，造成運算結(jié)果準確性降低。對改進的全局K-均值聚類算法通過人工模擬數(shù)據(jù)和學(xué)習(xí)庫中的數(shù)據(jù)實驗測試，得出其相較于改進前算法具有聚類效率提升、誤差降低的優(yōu)勢。

算法步驟如下：

第一步：針對樣本點xi，計算距離比Vi。中最小的點為xi，將其作為第一個簇的中心，并置q=1（q為簇中心數(shù)）；

第二步：針對簇中p=1,2,...,q,將xi，i=1,2,...,n劃分至最近的簇中，并更新簇中心為第i簇的樣本數(shù)，由此計算偏差

第三步：置q=q+1，當q＞k時，算法結(jié)束；

5 實驗與結(jié)果

通過以下隨機生成人工數(shù)據(jù)集來對改進全局K-均值聚類算法進行驗證，其中涵蓋噪音數(shù)據(jù)，以證明改進后全局K-均值聚類算法的抗干擾性能。將數(shù)據(jù)分為三類，各含有120個二維數(shù)據(jù)樣本，且滿足正態(tài)分布要求。第i類中橫坐標x的均值為縱坐標y的均值為第i類的標準差為在第二類數(shù)據(jù)中加入噪音點，其標準差為σ1。這三類隨機生成帶有噪音數(shù)據(jù)的參數(shù)如表1所示，樣本分布圖如圖2所示。

表1 隨機生成帶有噪音數(shù)據(jù)的參數(shù)

圖2 隨機生成的樣本分布

將全局K-均值聚類算法與改進后算法應(yīng)用于三類隨機數(shù)據(jù)中，得出的聚類誤差平方和（E）和聚類時間（T）如表2所示，聚類結(jié)果圖如圖3所示。

表2 應(yīng)用二種算法對隨機生成數(shù)據(jù)的聚類結(jié)果比較

圖3 二種算法的聚類結(jié)果圖

由圖3可知，二種算法應(yīng)用于三類隨機生成的帶有噪音點的數(shù)據(jù)中產(chǎn)生了類似的聚類效果，對比全局K-均值算法和改進后算法可知，本文中改進后的算法具有聚類時間短的優(yōu)點，且改進后的全局K-均值算法基本不受噪音點的干擾。通過實驗可知，基于全局K-均值算法改進后的算法聚類效果良好，適合推廣應(yīng)用。

[1]謝娟英，張琰，謝維信，等．一種新的密度加權(quán)粗糙K-均值聚類算法[J]．山東大學(xué)學(xué)報(理學(xué)版)，2010，45(7)：1-6．

[2]王軍敏，李艷．基于K均值算法的數(shù)據(jù)聚類和圖像分割研究[J]．平頂山學(xué)院學(xué)報，2014(2)：43-45．

[3]謝娟英，馬箐，謝維信．一種確定最佳聚類數(shù)的新算法[J]．陜西師范大學(xué)學(xué)報(自然科學(xué)版)，2012(1)：13-18．

[4]步媛媛，關(guān)忠仁．基于K-means聚類算法的研究[J]．西南民族學(xué)院學(xué)報(自然科學(xué)版)，2009，35(1)：198-200．

[5]吳景嵐朱文興．基于K中心點的文檔聚類算法[J]．蘭州大學(xué)學(xué)報(自然科版)，2005，41(5)：88-91．

[6]徐輝，李石君．一種整合粒子群優(yōu)化和K-均值的數(shù)據(jù)聚類算法[J]．山西大學(xué)學(xué)報(自然科學(xué)版)，2011，34(4)：518-523．