基于遺傳模擬退火的K-means聚類方法

鄧森林，陳衛東

（國防科學技術大學 信息系統與管理學院，湖南 長沙 410073）

K-means算法是一種算法簡單、收斂速度快，被廣泛的應用于各個領域的聚類算法。其基本思想為根據聚類所期望的簇的個數，選擇K個初始質心，每個點指派到最近的質心，指派到一個質心的點集為一個簇。然后根據指派到簇的點，更新每個簇的質心[1]。對于處理大數據集，該方法是相對可伸縮的和高效率的。因K-means在尋找聚類中心的過程中采用了啟發式方法，使得該算法對初始聚類中心的選擇較為敏感，易于陷入局部最優解。

美國Holland教授于1975年提出了一種全局優化自適應概率搜索算法，即遺傳算法（GA）。該算法模擬生物遺傳進化的過程，是一種借鑒生物界自然選擇思想和自然遺傳機制的全局隨機搜索算法。引入了選擇、復制、交叉重組和變異等方法，運算簡單且可以解決、非常困難的尋優問題[2]。理論上已經證明，遺傳算法能從概率的意義上以隨機的方式尋求到問題的最優解。但是基于遺傳算法的K-means聚類算法（GA-KM）存在前期過早收斂而后期收斂慢的缺點。

Metropolis等人于1953提出了模擬退火算法（SA），其基本思想是把某類優化問題求解過程與統計力學中的熱平衡問題進行對比。固體退火過程的物理圖像和統計性是建立模擬退火算法的物理背景，Metropolis接受準則使算法跳離局部最優的陷阱[3]。在模擬退火算法的搜索過程中融合遺傳算法的思想，算法的收斂速度快，各種性能均優于簡單遺傳算法，能夠以較大概率找到全局或準全局最優解，是提高算法運行效率和求解質量的有效手段之一。論文就是根據GA和SA的特點，提出一種基于GA和SA的K-means聚類算法（GASA-KM）。

1 遺傳模擬退火算法

遺傳算法在運行早期個體差異較大，當采用經典的輪盤賭方式選擇時，后代的產生的個數與父個體適應度大小成正比，因此在早期容易使個別好的個體后代充斥整個種群，造成早熟。在遺傳算法后期，適應度趨向一致，優秀的個體在產生后代時，優勢不明顯，從而使整個種群進化停滯不前，因此對適應度適當進行拉伸時必要的。

模擬退火算法引入Metropolis準則接受新解，因此，除了接受到較理想的新解外，同時也有可能在一定范圍內接受劣解。由于開始時溫度T取值較大，存在接受劣解的可能。隨著T值不斷變小，可行解越來越接近最優解，即當T值趨近于零時，可行解接近最優解，從而有可能避免搜索算法陷入局部最優的“陷阱”，得到整體最優解。

遺傳模擬退火算法是將傳統的遺傳算法和模擬退火算法相結合的一種優化算法，可對適應度適當的進行拉伸。當溫度高時（遺傳算法前期），適應度相近的個體產生后代的概率相近，而當溫度不斷下降后，拉伸作用加強，使適應度相近的個體適應度差異放大，從而得到優秀個體的優勢更加明顯。該算法通過模擬退火算法和遺傳算法相互間取長補短，有效的克服了傳統遺傳算法早熟的現象，同時根據聚類問題的具體情況設計遺傳編碼方式及適應度函數，使該算法更有效、更快速地收斂到全局最優解[4]。

2 基于遺傳模擬退火的K-means聚類

K-means算法對初始聚類中心較敏感，初始聚類中心越精確，則聚類的效果就越好[5]。用遺傳模擬退火算法查找初始聚類中心，可以看作是遺傳模擬退火算法在查找種群內的最優個體，這個最優個體就是K-means聚類算法需要的初始聚類中心。因此我們將遺傳模擬退火算法與K-means算法相結合，提出基于遺傳模擬退火算法的K-means聚類方法。

2.1 染色體編碼及種群初始化

染色體編碼有很多方式，常用的是基于聚類中心的浮點數編碼、基于聚類劃分的整數編碼以及二進制編碼。根據聚類樣本具有高維性和數量大的特點，本文采用浮點數編碼。初始種群的產生采用隨機生成，方法為：假設隨機從樣本空間中選K個樣本作為簇的中心，其他樣本隨機分到這K個簇中，并計算各個簇的中心作為初始個體的染色體編碼，最后增加一位該個體所對應的適應度，即1條染色體可以用長度為 （K+1）個基因位組成的浮點碼串A=a1a2…akf表示，重復進行sizepop次（sizepop為種群大小），得到初始種群。

2.2 染色體適應度的選取

適應度函數用來評價樣本聚類劃分的優劣。一般來說，使類內距離極小化而類間距離最大化的聚類是最優聚類。根據該準則，為了提高GASA-KM算法的聚類劃分質量，針對GASA-KM算法特點，我們將適應度函數f設定為：

其中，α和β為正的f常系數，其取值受樣本大小和預計的聚類數所影響。

簇間距離Emax為：

其中，ci表示簇i的中心，k為聚類類別數。

簇內距離Emin為：

其中，xi表示簇Ii的樣本，ni表示簇Ii的樣本數。

式（1）通過Emax對進行線性變換，使平均簇間距離被適當放大，將f從以K值為自變量的遞增函數轉化為單峰值函數，從而能更快的獲得最優值。并且，相對于選取簇間最大中心距離作為簇間距離的傳統方法，本文選取簇間平均距離作為簇間距離，更具有代表性和全面性。相對于選取每一個簇的樣本到該簇中心點的距離之和作為簇內距離的傳統方法，本文選取每一個簇的樣本到該類中心點的距離的平均值之和作為簇內距離，消除了因每一個簇的樣本個數不同對類內距離計算的影響。

本論文在傳統遺傳算法的生存策略中引入Metropolis準則：設新產生的個體適應性為f，變動的閾值為f′，當f＜f′時，接受新個體；否則，以一定的概率體，其中T是控制參數，相當于熱力學中的溫度。運行過程反復迭代，直到滿足終止條件。

2.3 遺傳操作設計

1）選擇算子：首先計算出每個樣本的適應度函數值，依據函數值得大小進行排序，再根據輪盤賭選擇法選取樣本；

2）交叉算子：交叉的目的是為了能夠在下一代產生新的個體，因此交叉操作是遺傳算法的關鍵部分，交叉算子的好壞，在很大程度上決定了算法性能的好壞，本文采用最簡單的單點交叉方法；

3）變異算子：變異不僅能增強算法的局部搜索能力，而且能增加種群的多樣性，改善算法的性能，避免早熟收斂。在選擇交叉的基礎上，再考慮變異，本文采用基本位變異方法。

3 算法流程

基于遺傳模擬退火算法的K-means聚類包含3層循環：最外層循環為模擬退火算法的降溫循環，中間層循環為遺傳算法的進化循環，最內層循環為K-means算法的聚類循環。其算法的具體過程如下：

1）初始化控制參數：聚類個數cn，種群個數大小sizepop，最大進化次數MAXGEN，交叉概率Pc，變異概率Pm，退火初始溫度T0，溫度冷卻系數k，終止溫度Tend；

2）隨機初始化cn個聚類中心，并生成初始種群Chrom，依照聚類中心對各個樣本進行聚類，再計算每個聚類的適應度值 fi，其中 i=1，2，…，sizepop；

3）設循環計數變量gen=0；

4）對群體Chrom實施選擇、交叉和變異等遺傳操作，對新產生的個體計算cn個聚類中心，依照新的聚類中心對各個樣本進行聚類形成新簇，計算每一個個體的適應度值f′i。若f′i＜fi，則以新個體替換舊個體；否則，以概率新個體，舍棄舊個體；

5）若 gen＜MAXGEN，則 gen=gen+1，轉至步驟 4）；否則，轉至步驟6）；

6）若 Ti＜Tend，則算法成功結束，返回全局最優解；否則，執行降溫操作 Ti+1=kTi，轉至步驟 3）[6-8]。

4 仿真實驗

將基于遺傳模擬退火的K-means算法作用于隨機產生的數據進行實驗。數據由4 000個四維平面上的點組成，這個點構成4個集合，但彼此間沒有明顯的界限。通過使用標準的K-means算法、基于遺傳算法的K-means算法和使用遺傳模擬退火算法優化初始聚類中心點后的K-means算法來說明后者的優勢。3種算法分別運算10次，結果取平均值，實驗結果如表1。

表1 四維數據聚類結果Tab.1 The result of the four-dimensional data clustering

聚類算法的理想結果是同時獲得最小的簇內距離和最大的簇間距離。標準K-means算法由于對初始中心選取敏感性很大，在初始中心選擇不當的情況下易陷入局部最優，出現過早收斂。基于遺傳算法的K-means聚類算法由于個體的多樣性不足而常出現早熟現象，本論文提出的算法在全局搜索能力方面優于K-means和基于遺傳算法的K-means算法，所獲得的聚類結果具有更強的穩定性和更優的目標函數值，對于隨機分布的數據聚類有明顯的優越性。

5 結 論

論文將K-means聚類方法與模擬退火和遺傳算法結合，即利用了K-means算法的快速收斂性，又利用了模擬退火和遺傳算法的全局搜索性，而不至于陷入局部最優。最后通過實驗證明了該方法能克服K-means算法對初始聚類中心較敏感性。該算法的主要缺點是運行時間較長，但是可以利用并行結構處理遺傳算法。另外，還可以更好地設置控制參數提高搜索能力和進化速度。

[1]TANPang-Ning，Michael Steinbach，Vipin Kumar.Introduction to Data Mining[M].BeiJing:China Machine Press，2010.

[2]馬坤，于海平，彭啟山.改進的遺傳模擬退火算法在TSP中的應用[J].武漢科技大學學報，2006，29（3）:266-269.MA Kun，YU Hai-ping，PENG Qi-shan.Application of improved genetic simulated annealing a lgorithmin traveling salesman problem[J].Journal of Wuhan University of Science and Technology：Natural ScienceEdition，2006，29（3）:266-269.

[3]李梓，于海濤，賈美娟.基于改進模擬退火的優化K-means算法[J].計算機工程與應用，2012，48（24）:77-80 LI Zi，YU Hai-tao，JIA Mei-juan.Optimized K-means algorithmbased on improved simulated annealing[J].Computer Engineering and Applications，2012，48（24）:77-80.

[4]張濟強，高玉良．遺傳模擬退火算法在K-means聚類中的應用[J].電腦與知識，2012，8（7）:1611-1613.ZHANG Ji-qiang，GAO Yu-liang.Research of K-means clustering method based on genetic simulated annealing algorithm[J].Computer Knowledge and Technology，2012，8（7）:2012，8（7）:1611-1613.

[5]TAI De-yi，XIE Fei，HU Xue-gan.New text categorization method based on cluster partitioning[J].Computer Engineering and Design，2009，30（6）:1461-1463.

[6]劉秋菊，王仲英，劉素華.基于遺傳模擬退火算法的模糊聚類方法[J].微計算機信息，2006，29（3）:266-269.LIU Qiu-ju，WANG Zhong-ying，LIU Su-hua.A optimization clus tering algorithm based on simulated annealing and genetic algorithm[J].Microcomputer Information，2006，29（3）:266-269.

[7]趙永雷，黃家棟，李配配.基于加權模糊C均值聚類算法的變壓器故障診斷[J].陜西電力，2011（9）：39-41.ZHAO Yong-lei，HUANG Jia-dong，LI Pei-pei.Fault diagnosis on transformer based on weighted fuzzy C-means clustering algorithm[J].Shaanxi Electric Power，2011（9）：39-41.

[8]高勇，吳江.基于三比值法與模糊聚類的變壓器故障診斷[J].陜西電力，2012（7）：80-82.GAO Yong，WU Jiang.Study on transformer fanlt diagnosis based on the combination of IEC three-ratio codes method and fuzzy clustering algorithm[J].Shaanxi Electric Power，2012（7）：80-82.