基于微正則退火算法對(duì)K-means 聚類算法的優(yōu)化

周浩理，李太君，肖 沙

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 海口570228)

K－means 算法是經(jīng)典的基于劃分的聚類算法，雖然已經(jīng)被提出近60 年，但仍然是聚類分析中研究的熱點(diǎn)問題。因?yàn)槠浜?jiǎn)單、高效的特點(diǎn)，在許多領(lǐng)域中都有著廣泛的應(yīng)用。對(duì)于數(shù)據(jù)簇比較密集、簇與簇之間有著明顯區(qū)別的情況下，使用K－means 聚類算法進(jìn)行聚類的效果良好;在處理大數(shù)據(jù)的情況下該算法也有著相對(duì)可伸縮和高效率的優(yōu)點(diǎn)。但該算法也有難以解決的問題:依賴于初始聚類中心、容易陷入局部最優(yōu)解、對(duì)孤立點(diǎn)敏感、需事先指定聚類的數(shù)目等。針對(duì)其對(duì)初始聚類中心的依賴和容易陷入局部最優(yōu)等缺點(diǎn)，學(xué)者們提出了多種改進(jìn)策略以改進(jìn)K－means 算法，而改進(jìn)算法主要分為兩類。一類是從算法本身著手，改進(jìn)初始聚類中心的選取，比如，賴玉霞提出了基于密度的K－means 算法，從數(shù)據(jù)的自然分布來選取初始聚類中心，找出分布密集的區(qū)域作為聚類劃分，減少了聚類中心隨機(jī)選取對(duì)聚類結(jié)果造成的不穩(wěn)定性［1］。陳光平利用最大距離作為初始聚類中心劃分的標(biāo)準(zhǔn)，將相距較遠(yuǎn)的聚類中心作為K－means 算法的初始聚類中心，得到較好的聚類結(jié)果［2］。另一類是結(jié)合其他尋優(yōu)算法，而主要的算法是智能算法，WANG 利用自組織特征映射神經(jīng)網(wǎng)絡(luò)選取初始聚類中心，再采用K－means 算法聚類，克服了Kmeans 算法的缺點(diǎn)［3］。黃浩提出將模擬退火算法與K－means算法結(jié)合進(jìn)行聚類分析，前期利用K－means 算法求出聚類劃分結(jié)果，在后期結(jié)合模擬退火算法，檢驗(yàn)聚類結(jié)果的準(zhǔn)確性［4］。本文考慮到微正則退火算法比模擬退火算法更具有高效全局尋優(yōu)特性，因此，在K－means 聚類算法的基礎(chǔ)上結(jié)合微正則退火算法進(jìn)行了改進(jìn)。

1 K－means 聚類算法

K－means 算法屬于無監(jiān)督學(xué)習(xí)，樣本中設(shè)有給定類別標(biāo)簽y，給定訓(xùn)練樣本{x(1)，x(2)，…，x(m)}，其中x(i)∈Rn，將樣本聚類成k 個(gè)簇，具體實(shí)現(xiàn)的基本步驟如下:

1)隨機(jī)選取給定的k 個(gè)聚類質(zhì)心點(diǎn)μ1，μ2，…，μk∈Rn。

2)重復(fù)以下過程直到目標(biāo)函數(shù)收斂:

對(duì)于每個(gè)樣例i，計(jì)算其屬于的類

對(duì)于每個(gè)類j，重新計(jì)算該類的質(zhì)心

式中:c(i)的值是1 ～k 個(gè)類中的一個(gè)，其代表k 個(gè)類與樣例i距離最近的類。質(zhì)心μj是對(duì)屬于同一個(gè)類的樣本中心點(diǎn)的猜測(cè)。

2 微正則退火算法

微正則退火算法基于微正則系綜的概念，微正則系綜與外界之間沒有物質(zhì)和能量的交換。在一定時(shí)間內(nèi)系統(tǒng)的能量守恒，系統(tǒng)處于任意狀態(tài)的概率是相等的。但實(shí)際上對(duì)溫度的測(cè)量結(jié)果可以得出溫度的大小還是會(huì)有相應(yīng)變化的［5］。微正則退火算法和模擬退火算法的最大不同是不再直接依賴系統(tǒng)的溫度，在退火的狀態(tài)轉(zhuǎn)移中不再使用Metropolis 準(zhǔn)則，而是基于一種確定性的方式［6］。其配分函數(shù)為

式中:E0為初始能量值;E(C)表示在狀態(tài)C 時(shí)系統(tǒng)的能量，E(P)為在C 狀態(tài)下動(dòng)量P 的能量值。

在微正則退火算法的運(yùn)算過程中，“妖”為一種能量載體，初始化它的動(dòng)量為P。“妖”可以在狀態(tài)空間內(nèi)任意移動(dòng)，而當(dāng)“妖”的狀態(tài)變化時(shí)，系統(tǒng)的能量會(huì)隨之變化，最后系統(tǒng)會(huì)擺脫亞穩(wěn)態(tài)。在這個(gè)運(yùn)算中，系統(tǒng)和“妖”的能量和將在一定時(shí)間段內(nèi)為一常量。設(shè)ED為“妖”的能量，且其初始值在正常情況下為0，當(dāng)變化時(shí)是一個(gè)正數(shù)。Z 的形式為

設(shè)定系統(tǒng)初始的能量狀態(tài)后，能量載體“妖”在狀態(tài)空間中被釋放，按上式的初始條件，令“妖”的初始能量值為零，當(dāng)“妖”移動(dòng)后，系統(tǒng)能量需要重新進(jìn)行測(cè)定，而當(dāng)系統(tǒng)能量表現(xiàn)為能量下降時(shí)，“妖”接受新狀態(tài)，且能量值增大，如下所示

式中:Enew，Eold分別表示系統(tǒng)在新舊狀態(tài)時(shí)所對(duì)應(yīng)的能量;為新狀態(tài)下的能量為舊狀態(tài)下的能量。因?yàn)橹挥邢到y(tǒng)的能量表現(xiàn)為下降時(shí)，“妖”才接受新狀態(tài)，因此，經(jīng)過多次移動(dòng)后，系統(tǒng)的能量為下降的趨勢(shì)。

3 微正則退火K－means 算法

3.1 算法原理

K－means 在聚類分析過程中，可能會(huì)陷入停滯狀態(tài)，即算法陷入局部最優(yōu)。如何跳出局部最優(yōu)，獲得全局最優(yōu)解是非常關(guān)鍵的問題。李梓提出首先使用模擬退火算法智能搜索初始聚類中心，再利用K－means 算法進(jìn)行聚類，減少了算法陷入局部最優(yōu)解的概率［7］。模擬退火算法需要生成隨機(jī)數(shù)并按照Metropolis準(zhǔn)則來判斷拒絕或接受新狀態(tài)，但微正則退火實(shí)行確定性的狀態(tài)轉(zhuǎn)移規(guī)則，無須生成隨機(jī)數(shù)來判斷接受或者拒絕新狀態(tài)，在大規(guī)模問題上要比模擬退火算法更有時(shí)間效率［8］。因此，可以采用全局尋優(yōu)能力更強(qiáng)的微正則退火算法對(duì)K－means算法進(jìn)行優(yōu)化，擺脫以往算法在尋優(yōu)方面的局限性。

本文首先對(duì)樣本進(jìn)行隨機(jī)劃分，對(duì)微正則退火算法進(jìn)行初始化，然后用微正則退火算法得到聚類的聚類中心，也即全局最優(yōu)解，然后再把聚類中心交給K－means 算法，再對(duì)其進(jìn)行聚類，得到聚類結(jié)果。其算法主要步驟的流程圖如圖1所示。

圖1 微正則退火K－means 算法的主要步驟的流程圖

3.2 參數(shù)的設(shè)定

作為“妖”的能量上界初始值，依據(jù)上式能量函數(shù)取值范圍，應(yīng)被設(shè)定為適中的大小。在選擇系統(tǒng)的參數(shù)時(shí)，設(shè)p為下降參數(shù);×p 表示為對(duì)能量函數(shù)進(jìn)行幾何下降處理。微正則退火算法進(jìn)行最優(yōu)解搜索主要變現(xiàn)為:當(dāng)>為常數(shù)時(shí)，p 變化;或當(dāng)p 為常數(shù)時(shí)， 變化的情形。當(dāng)p 為常數(shù)時(shí)，與算法的復(fù)雜度成正比;當(dāng)為常數(shù)時(shí)，p 不會(huì)影響算法對(duì)最優(yōu)解的搜索結(jié)果。從以上分析可知，需要明確標(biāo)定能量上界參數(shù)、能量下降參數(shù)p，得到2 個(gè)參數(shù)的最佳組合，以此尋優(yōu)全局解。

在微正則退火算法中，能量調(diào)整因子q 也將影響到算法的搜索成功率。當(dāng)取q 為過大或過小值時(shí)，“妖”的能量會(huì)相應(yīng)出現(xiàn)增大或縮減過度的現(xiàn)象，而對(duì)于q 的取值，進(jìn)行了不同的測(cè)試，并得出最為合適的結(jié)果［9］。在界定算法進(jìn)行過程所處的位置時(shí)，引入界定參數(shù)r，以此為算法進(jìn)行相應(yīng)的能量獎(jiǎng)勵(lì)策略;設(shè)定t 為進(jìn)行能量調(diào)整策略的參考值，取值空間為［0，1］。

對(duì)于K－means 算法的判斷準(zhǔn)則，本文選取當(dāng)前聚類劃分的總類間離散度作為目標(biāo)函數(shù)

式中:聚類的劃分為w，各聚類中心和對(duì)應(yīng)樣本之間的距離總和為Jw，樣本向量為X，以及第i 個(gè)聚類中心為，樣本到對(duì)應(yīng)聚類中心的距離為d)。

3.3 算法的具體流程

1)對(duì)樣本進(jìn)行隨機(jī)劃分，得到初始狀態(tài)t1，t2，…，tk，聚類空間S;將S 作為退火的解空間，初始化循環(huán)變量i=1，j=1。

2)系統(tǒng)能量E0=0，在狀態(tài)空間中設(shè)定一個(gè)行走的“妖”，令其能量初值為ED=0。

3)循環(huán)4)～8)，直到i ＞N，即遍歷完聚類空間S 中的所有結(jié)果。

4)設(shè)定“妖”的能量上界Edmax，即Edmax=Edmax×p(p 為能量下降參數(shù))。

5)重復(fù)6)、7)、8)，直到j(luò) ＞jmax，jmax為循環(huán)變量j 的上界，即執(zhí)行完所有可能變換。

6)在狀態(tài)空間中，當(dāng)“妖”產(chǎn)生新解(表現(xiàn)為“妖”進(jìn)行移動(dòng))，得到ΔE，即系統(tǒng)相鄰狀態(tài)的差值。

7)當(dāng)ED＞Edmax×t，實(shí)行能量縮減ED=ED×(1－P)。如果ED＞ΔE，則接受新的系統(tǒng)狀態(tài)，更新最優(yōu)狀態(tài)數(shù)組，并檢查“妖”的能量是否已越界，即ED是否大于Edmax;否則拒絕新解，當(dāng)ED＜E0×r，實(shí)行獎(jiǎng)勵(lì)ED=ED×(1+q)。

8)如果連續(xù)若干次拒絕新解，將狀態(tài)回溯，重新移動(dòng)。

9)得到全局最優(yōu)的聚類中心，即為K－means 算法的初始聚類中心，進(jìn)行聚類，使目標(biāo)函數(shù)收斂，得到聚類結(jié)果。

4 實(shí)驗(yàn)研究

4.1 數(shù)據(jù)集的選擇

為了測(cè)試微正則退火K－means 算法的性能，本文采用UCI 數(shù)據(jù)庫(kù)進(jìn)行測(cè)試，UCI 數(shù)據(jù)庫(kù)是加州大學(xué)歐文分校(University of California Irvine)提出的，目前，該數(shù)據(jù)庫(kù)共有187 個(gè)數(shù)據(jù)集，是常用的進(jìn)行數(shù)據(jù)挖掘?qū)嶒?yàn)的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集。UCI 數(shù)據(jù)可以使用MATLAB 的dlmread 或textread 函數(shù)讀取，也可以導(dǎo)入，進(jìn)行測(cè)試非常方便，不過需要先將非數(shù)字的類別用數(shù)字替換，否則不能讀入數(shù)值。本文的實(shí)驗(yàn)環(huán)境和算法運(yùn)行參數(shù)配置如下:在Windows 7 系統(tǒng)下，4 核，CPU 處理速度3.20 GHz，4 Gbyte 內(nèi)存，采用MATLAB 2010b 編寫程序。為了能夠和其他研究算法進(jìn)行對(duì)比，本文在數(shù)據(jù)庫(kù)中選取研究人員常用的測(cè)試聚類算法性能的6 個(gè)數(shù)據(jù)集:Iris、Image、Glass、Balance、Wine 和Zoo，通過這6 個(gè)數(shù)據(jù)集來測(cè)試Kmeans 算法、模擬退火K－means 算法和微正則退火K－means算法性能的優(yōu)劣，具體數(shù)據(jù)集描述見表1。

表1 測(cè)試數(shù)據(jù)集

4.2 實(shí)驗(yàn)結(jié)果和分析

本文通過直觀的二維散點(diǎn)圖、查準(zhǔn)率和查全率以及運(yùn)行時(shí)間對(duì)算法進(jìn)行比較。為了方便顯示，二維散點(diǎn)圖采用Iris 數(shù)據(jù)集的花瓣長(zhǎng)和花瓣寬作為橫縱坐標(biāo)，如圖2、圖3、圖4 所示。

圖2 基于K－means 算法的仿真結(jié)果

圖2 可以得到K－means 算法陷入局部最優(yōu)，圖中的3 類數(shù)據(jù)分類失敗，即收斂于局部極值的情況;圖3 是基于模擬退火算法的聚類結(jié)果，從圖中可以看出該算法對(duì)數(shù)據(jù)的分類結(jié)果是準(zhǔn)確的;圖4 是基于微正則退火算法的聚類結(jié)果，從圖中

圖4 基于微正則退火K－means 算法的仿真結(jié)果

可以看出該算法對(duì)3 類數(shù)據(jù)的分類準(zhǔn)確，而且和圖3 的結(jié)果圖進(jìn)行對(duì)比可知，本文提出的算法達(dá)到了模擬退火K－means 算法的分類結(jié)果的準(zhǔn)確度，2 種算法得到的分類結(jié)果比較接近。從圖2 和圖4 可直觀看出微正則退火K－means 算法的聚類效果比K－means 算法更顯著，能夠擺脫局部極值點(diǎn)的束縛。經(jīng)過對(duì)每個(gè)數(shù)據(jù)集的多次仿真實(shí)驗(yàn)，得出表2 的測(cè)試結(jié)果。

表2 為3 種算法的測(cè)試結(jié)果的比較，CP 為查準(zhǔn)率，即聚類得到的正確結(jié)果與得到的全部結(jié)果的比值，CR 為查全率，即聚類得到的正確結(jié)果與測(cè)試數(shù)據(jù)集中全部的正確結(jié)果的比值。RUNTIEN 是CPU 運(yùn)行時(shí)間。從表中數(shù)據(jù)可以看出，微正則退火K－means 算法的查準(zhǔn)率和查全率都要高于經(jīng)典的K－means 算法和模擬退火K－means 算法，而且通過圖2、圖3和圖4 的二維散點(diǎn)圖也可以看出改進(jìn)的算法和基于模擬退火K－means 算法一樣能夠優(yōu)化聚類結(jié)果，使之能夠擺脫局部最優(yōu)解的束縛。但是在運(yùn)行時(shí)間上，微正則退火的K－means 算法和模擬退火K－means 算法都要大于K－means 算法，這是由于微正則退火算法和模擬退火K－means 算法在執(zhí)行過程中尋求全局最優(yōu)解增加搜索時(shí)間，在尋找最優(yōu)解的過程中，本文改進(jìn)的算法的運(yùn)行時(shí)間要低于模擬退火K－means 算法，可知，本文改進(jìn)的算法在運(yùn)行效率上有明顯的提升，從實(shí)驗(yàn)仿真結(jié)果表明本文算法的改進(jìn)還是比較成功的，聚類的效果較改進(jìn)前有明顯提升。

表2 3 種算法的測(cè)試結(jié)果

5 結(jié)束語(yǔ)

本文將K－means 算法和微正則退火算法進(jìn)行有效結(jié)合，提出了微正則退火K－means 算法，由于K－means 算法存在需要事先指定聚類的數(shù)目、容易陷入局部最優(yōu)解、對(duì)孤立點(diǎn)敏感、依賴于初始聚類中心等缺點(diǎn)，本文利用微正則退火算法針對(duì)這些缺點(diǎn)進(jìn)行了有效的改進(jìn)，實(shí)驗(yàn)表明，改進(jìn)算法是可行的，對(duì)K－means 算法諸多缺點(diǎn)也有很好的魯棒性，是一種改進(jìn)K－means 算法性能的可行方案。改進(jìn)后的算法延長(zhǎng)了運(yùn)行時(shí)間，相對(duì)于模擬退火K－means 算法的運(yùn)行效率，本文的運(yùn)行效率有一定的提高，往后可以在運(yùn)行效率上進(jìn)一步研究改進(jìn)。

［1］賴玉霞，劉建平. K－means 算法的初始聚類中心的優(yōu)化［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(10):147－149.

［2］陳光平，王文鵬，黃俊. 一種改進(jìn)初始聚類中心選擇的K－means算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，33(6):1320－1323.

［3］WANG H B，YANG H L，XU Z J，et al. A clustering algorithm use SOM and K－means in intrusion detection［C］//Proc. International Conference on E－Business and E－Government. Guangzhou:IEEE Press，2010:1281－1284.

［4］黃浩，肖立志，張國(guó)毅.基于模擬退火的K－means 算法研究［J］.艦船電子對(duì)抗，2008，31(6):103－105.

［5］CREUTZ M. Microcanonical Monte Carlo simulation［J］. Physical Review Letters，1983，50(19):1411－1414.

［6］XUE G X，WANG X F，WEI L，et al. An improved microcanonical mean field annealing algorithm［C］//Proc. ICINIS’09. Tianjin:IEEE Press，2009:542－545.

［7］李梓，于海濤，賈美娟.基于改進(jìn)模擬退火的優(yōu)化K－means 算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(24):77－116.

［8］徐俊杰，忻展紅. 具有能量獎(jiǎng)勵(lì)策略的微正則退火算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2008，29(10):1842－1844.

［9］徐暢.大規(guī)模路網(wǎng)下基于蟻群微正則退火算法的路徑優(yōu)化方法研究［D］.長(zhǎng)春:吉林大學(xué)，2013.