一種基于全局K-均值聚類的改進(jìn)算法

李燕梅

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

1 引言

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

2 K-均值聚類算法

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

3 全局K-均值聚類算法

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

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

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

4 基于全局K-均值聚類算法的改進(jìn)

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

圖1 算法流程圖

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

算法步驟如下：

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

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

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

5 實(shí)驗(yàn)與結(jié)果

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

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

圖2 隨機(jī)生成的樣本分布

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

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

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

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

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

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

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

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

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

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