基于遺傳算法的K-means 聚類改進研究?

馮永亮 李 浩

（1.西安文理學院信息工程學院 西安 710065）（2.西安文理學院西安市物聯網應用工程實驗室 西安 710065）

1 引言

作為一種經典的基于劃分的聚類算法，K-means 以其運算簡單快捷、資源消耗較少、伸縮性強等優勢，受到業界的廣泛推崇。然而該算法也存在一些不足：聚類數目無法直接得到，需要根據先驗知識或者隨機設置，這使得結果變得不穩定；初始聚類中心往往是隨機選取的，而選取的結果又直接影響了聚類的結果。本文利用遺傳算法的全局尋優特性和自適應搜索概率技術等優勢來彌補K-means的劣勢，形成一種改進的聚類方法。

2 K-means聚類算法

2.1 K-means概況

K-means 聚類旨在將集合分成若干個簇，盡量使簇內對象高相似，而簇間對象低相似［1］。K-means 首先在包含N 個點的集合中，隨機假設K個點為起始的聚類中心，然后依據所有點到中心點的距離大小，將每個點分配到離中心點較近的簇中，再重新求出每個簇的中心點，不斷重復，直至中心點不再發生變化，或者聚類準則函數收斂為止［2］。

K-means算法的基本步驟如下：

1）隨機選取若干點作為起始聚類中心點；

2）將每個點劃分到距離它最近的中心點所在的簇中；

3）形成每個簇中新的中心點；

4）若簇的中心點已穩定不變，或者聚類準則函數已收斂，則結束并輸出結果，否則轉至步驟2）繼續進行。

2.2 K-means的優缺點

K-means 聚類算法的優點在于運算簡單快捷，資源消耗較少，且處理大型數據庫或者大數據集時，算法具備可伸縮性和高效性。同時，K-means能夠有效解決分布比較均勻的數據集的聚類問題，往往應用于文本、網頁和圖像的聚類分析，但是，K-means 也存在一些明顯的不足，主要包括：1）聚類生成的簇數K 值需要憑經驗預先給定，而根據經驗設定的K 值往往不是最佳聚類數目，會影響到聚類的結果［3］。2）算法容易受到初始聚類中心選取的影響，如果改變初始聚類中心，聚類結果也會隨之變化［4］。3）算法是一種針對局部的搜索技術，往往尋找的并非全局最優值［5］。

K-means 聚類算法需要從三方面進行改進：1）尋找一種更優的方式來獲取K 值，而不是隨機或憑經驗設置K 值，提高聚類效果。2）尋求更高效的方式來選取初始聚類中心，而非隨機或憑經驗設置初始聚類中心，提高聚類效果的穩定性。3）尋找全局性更優的算法來彌補K-means 易于陷入局部最優的不足。

3 遺傳算法

3.1 遺傳算法概況

為了模仿生物在自然環境中的遺傳方式，人們提出了一種自適應的、面向全局的尋優搜索算法，即遺傳算法［6］。該算法首先將每個可能解編碼成染色體，然后隨機選擇若干個染色體，形成起始的種群，再根據預設的適應度函數算出所有染色體的適應值。接著選取具有較高適應值的染色體擔任新的父代染色體，隨后使用交叉、變異等操作產生子代染色體，即新的適應值更高的染色體，經過若干代不斷繁衍，最后得到適應值最優的染色體［7］，即問題的最優解。

遺傳算法運行的詳細過程是［8］：

1）設置個體數，交叉概率，變異概率，終止條件等參數；

2）隨機性設置雙親群體中的碼串，作為初始值；

3）設置進化代數為0；

4）算出各條基因串的適應度值；

5）進行遺傳操作，通過概率參數生成后代；

6）用子代更新父代，生成下一代個體；

7）如果終止條件尚未滿足，跳轉到步驟4）；如果已滿足，則得出最優解。

3.2 遺傳算法的優劣勢

遺傳算法的優勢比較明顯，主要包括：1）應用比較廣泛。遺傳算法并非直接處理問題的參數，而是通過編碼生成的基因，任何問題通過編碼成基因個體后，就可以使用遺傳算法［9］。2）全局尋優特性和并行性。遺傳算法在點群中而不是在一個單點上尋優，并且對搜索的多個點進行評價，這些特性既增強了算法的全局搜索能力和并行化能力［10］。3）遺傳算法是一種自適應概率搜索技術，它使用概率規則，其選擇、交叉、變異等操作都是基于概率進行的，使得搜索過程更加靈活［11］。雖然遺傳算法具備上述優勢，但也存在易過早收斂、缺乏定量分析等劣勢［12］。本文考慮利用遺傳算法的全局尋優特性和自適應搜索概率技術等優勢，改進K-means聚類質量。

4 基于遺傳算法的K-means聚類研究

4.1 基于遺傳算法的K-means聚類研究現狀

Krishna 將以前的遺傳交叉算子更新成K-means，得出一種新的遺傳算法，并證明了新算法能求出全局最優值［13］。Manlik 利用浮點數操作提升了算法的查找效率［14］。Cristofor.D 設計了一種變長基因編碼，提升了聚類的效率［15］。Sarafis 將遺傳算法用于構建K-means目標函數，并得出一種更高效的聚類算法［16］。武兆慧等將模擬退火算法與遺傳算法有機結合，形成了一種新的聚類算法［17］。趙峰等在復合型遺傳算法的基礎上進行優化設計，彌補了易陷入局部最優的不足［18］。賈兆紅等利用一種混合遺傳聚類算法中的禁忌搜索提升了聚類速度［19］。耿躍等改進了遺傳算法中的變異算子，設計出了一種新的聚類算法［20］。

4.2 基于遺傳算法的K-means聚類設計

本文結合K-means的不足，以及遺傳算法優劣勢，考慮對K-means 進行三點改進：1）改進K-means 初始K 值的獲取方式，對N 個對象的樣本集N'，利用遺傳算法來學習K 值，作為K-means 算法的初始K 值。2）改進K-means 初始聚類中心形成方式，利用遺傳算法的自適應搜索概率技術和全局尋優特性，形成更加穩定的K-means初始聚類中心。3）進一步改進遺傳算法中的選擇、交叉、和變異算子，既可防止早熟現象，又能提高K-means 全局搜索能力和計算效率。改進后的算法包括以下幾方面的設計。

1）生成樣本集

考慮原始數據集規模大小不一，如果能夠對較大規模的原始數據進行隨機均勻采樣，生成樣本集，這樣就可以更快地獲取最優的K值和初始聚類中心，在此基礎上，再在原始數據集上進行K-means 聚類，這樣就可以提高聚類的質量和效率。具體操作是：首先判斷原始數據集的個體數量，如果高于設定的閾值（一般設定為60～130），則對原始數據集進行隨機均勻采樣，生成原始數據集的子集，即樣本集；如果低于閾值，則直接將原始數據集作為樣本集。

2）遺傳算法相關設計

（3）設計選擇算子。遵循“優勝劣汰，適者生存”的原則，本文采用輪盤賭法，使個體被選中的概率取決于其對應的適應度值的大小，適應度值越高，其參與后代繁殖的概率越高。設為個體Xi的適應度值，P( )

Xi為個體Xi的選擇概率，N 為個體數量，則：

（4）設計自適應交叉算子。本文設計一種交叉概率隨染色體適應度值自動變化的交叉算子，如果個體適應度值低于平均適應值，則直接進行交叉操作，相反，如果個體適應度值高與平均適應值，選擇一定的交叉概率。這樣既保留了高適應度值得個體特征，又保證了低適應度值個體交叉操作，進一步提高算子全局搜索能力。設Fmax為最大適應度值，Favg為平均適應度值，F'為進行交叉操作中的個體中的較大適應度值，自適應交叉概率Pc的公式為

（5）設計自適應變異算子。同自適應交叉算子類似，本文也設計了一種基于自適應概率的變異算子，如果某個體適應值高于群體平均值，則對其采用低變異率，保證使其順利進入下一代，否則，對該個體直接進行變異操作，使其高概率的被淘汰。設F 為要變異個體的的適應度值，自適應交叉概率Pm的公式為

3）基于遺傳算法的K-means聚類算法步驟

（1）判斷原始數據集規模大小，如果小于等于設定的閾值（一般在60～130 之間），則直接將原始數據集作為樣本集。否則，對原始數據集進行均勻采樣，生成樣本集。

（2）利用遺傳對樣本集K 值尋優，獲得最優K值。

（3）利用上一步獲得最優K 值，再次利用遺傳算法對樣本集尋優，獲得最優初始聚類中心。

（4）利用第（2）、（3）步獲取的K 值和聚類中心，對原始的數據集進行聚類操作。

（5）得到最優聚類結果。

基于遺傳算法的K-means 聚類流程圖如圖1所示，其中利用遺傳算法進行K 值尋優如圖2 所示，利用遺傳算法進行初始聚類中心尋優的流程與K 值尋優類似，不同的是其初始K 值是上一步尋優得到的最優K值。

圖1 基于遺傳算法的K-means聚類流程圖

圖2 利用遺傳算法進行K值尋優的流程圖

5 仿真實驗結果及分析

實驗平臺包括：Intel（R）Core（TM）i5-4590 CPU 3.30GHz，4G 內存，500G 硬盤，操作系統Windows7。分別采用K-means 算法和本文算法在Matlab 環境下，對Iris 數據集（數據規模：110）和Automatives數據集（數據規模：630）進行聚類，聚類結果如表1 和表2 所示。實驗表明，基于遺傳算法的K-means 聚類在平均迭代次數和準確率方面明顯優于普通的K-means算法。

表1 Iris數據集聚類結果

表2 Automatives數據集聚類結果

6 結語

本文針對K-means存在的若干不足，利用遺傳算法的全局尋優和自適應搜索概率技術等優勢，設計了一種基于遺傳算法的K-means聚類算法，仿真實驗結果表面，新算法在迭代次數和準確率方面均優于普通的K-means算法。