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

周浩理，李太君，肖 沙

(海南大學 信息科學技術(shù)學院，海南 ?？?70228)

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

1 K－means 聚類算法

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

1)隨機選取給定的k 個聚類質(zhì)心點μ1，μ2，…，μk∈Rn。

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

對于每個樣例i，計算其屬于的類

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

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

2 微正則退火算法

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

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

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

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

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

3 微正則退火K－means 算法

3.1 算法原理

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

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

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

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

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

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

對于K－means 算法的判斷準則，本文選取當前聚類劃分的總類間離散度作為目標函數(shù)

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

3.3 算法的具體流程

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

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

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

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

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

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

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

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

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

4 實驗研究

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

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

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

4.2 實驗結(jié)果和分析

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

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

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

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

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

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

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

5 結(jié)束語

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

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

［2］陳光平，王文鵬，黃俊. 一種改進初始聚類中心選擇的K－means算法［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］黃浩，肖立志，張國毅.基于模擬退火的K－means 算法研究［J］.艦船電子對抗，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］李梓，于海濤，賈美娟.基于改進模擬退火的優(yōu)化K－means 算法［J］.計算機工程與應用，2012，48(24):77－116.

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

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