摘  要： 傳統(tǒng)K-means算法對初始聚類中心的選取和樣本的輸入順序非常敏感，容易陷入局部最優(yōu)。針對上述問題，提出了一種基于遺傳算法的K-means聚類算法GKA，將K-means算法的局部尋優(yōu)能力與遺傳算法的全局尋優(yōu)能力相結合，通過多次選擇、交叉、變異的遺傳操作，最終得到最優(yōu)的聚類數和初始質心集，克服了傳統(tǒng)K-means算法的局部性和對初始聚類中心的敏感性。
關鍵詞： 遺傳算法；K-means；聚類

    聚類分析是一個無監(jiān)督的學習過程，是指按照事物的某些屬性將其聚集成類，使得簇間相似性盡量小，簇內相似性盡量大，實現(xiàn)對數據的分類[1]。聚類分析是數據挖掘技術的重要組成部分，它既可以作為獨立的數據挖掘工具來獲取數據庫中數據的分布情況，也可以作為其他數據挖掘算法的預處理步驟。聚類分析已成為數據挖掘主要的研究領域，目前已被廣泛應用于模式識別、圖像處理、數據分析和客戶關系管理等領域中。K-means算法是聚類分析中一種基本的劃分方法，因其算法簡單、理論可靠、收斂速度快、能有效處理較大數據而被廣泛應用，但傳統(tǒng)的K-means算法對初始聚類中心敏感，容易受初始選定的聚類中心的影響而過早地收斂于局部最優(yōu)解，因此亟需一種能克服上述缺點的全局優(yōu)化算法。
    遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化搜索算法。在進化過程中進行的遺傳操作包括編碼、選擇、交叉、變異和適者生存選擇。它以適應度函數為依據，通過對種群個體不斷進行遺傳操作實現(xiàn)種群個體一代代地優(yōu)化并逐漸逼近最優(yōu)解。鑒于遺傳算法的全局優(yōu)化性，本文針對應用最為廣泛的K-means方法的缺點，提出了一種基于遺傳算法的K-means聚類算法GKA(Genetic K-means Algorithm)，以克服傳統(tǒng)K-means算法的局部性和對初始聚類中心的敏感性。
    用遺傳算法求解聚類問題，首先要解決三個問題：
    (1)如何將聚類問題的解編碼到個體中；
    (2)如何構造適應度函數來度量每個個體對聚類問題的適應程度，即如果某個個體的編碼代表良好的聚類結果，則其適應度就高；反之，其適應度就低。適應度函數類似于有機體進化過程中環(huán)境的作用，適應度高的個體在一代又一代的繁殖過程中產生出較多的后代，而適應度低的個體則逐漸消亡；
    (3)如何選擇各個遺傳操作以及如何確定各控制參數的取值。
    解決了這些問題就可以利用遺傳算法來求解聚類問題，這也顯示了遺傳算法與求解問題無關的特性。
1 K-means算法
    K-means聚類算法的目標是把包含n個對象的數據集x分為k個簇，使簇內具有較高的相似度，而簇間相似度較低。算法首先隨機選擇k個對象作為初始聚類中心，再計算剩余數據對象到各聚類中心的距離并將其賦給最近的簇，然后重新計算每個簇的平均值，不斷重復此過程，直到準則函數收斂。
    準則函數定義如下：
 

2 基于遺傳算法的K-means聚類算法（GKA）
    GKA的基本思想是：首先從要聚類的樣本集選出初始種群，并對其執(zhí)行遺傳算法；對執(zhí)行完遺傳算法后產生的新種群執(zhí)行K-means操作。如此反復循環(huán)，直到尋找出聚類問題的最優(yōu)解。
2.1 染色體編碼
    遺傳算法的編碼方法分為三大類：二進制編碼、符號編碼和浮點數編碼，其中二進制編碼方法是遺傳算法中最主要和常用的一種編碼方法。由于聚類樣本具有多維性、數據量大等特點，如果采用傳統(tǒng)的二進制編碼，染色體的長度會隨著維數的增加或精度的提高而顯著增加，從而使得搜索空間急劇增大，大大降低了計算效率，因此本文采用基于聚類中心的浮點數編碼方法。
    例如對于一個類別為3的聚類問題，假設數據集為2維，初始的3個聚類中心點為(10，20)、(30，40)和(50，60)，則染色體編碼為(10，20，30，40，50，60)。這種基于聚類中心的編碼方式意義明確、直觀，縮短了染色體的長度，提高了運算效率，對于求解大量數據的復雜聚類問題效果較好。
2.2 初始化種群
    初始群體完全隨機生成。首先從樣本空間中隨機選出k個個體，每個個體表示一個初始聚類中心，然后根據所采用的編碼方式將這組個體（聚類中心）編碼成一條染色體。然后重復進行m次染色體初始化（m為種群大?。?，直到生成初始種群。
2.3 適應度函數的設計
    適應度函數[2]是用來評價個體的適應度、區(qū)別群體中個體優(yōu)劣的標準。個體的適應度越高，其存活的概率就越大。本文依據準則函數J構造適應度函數，由于J越小說明聚類劃分的質量越好，J越大說明聚類劃分的質量越差，因此設計如下的適應度函數：
 
其中，α是一個參數，可以是常數(此時為均勻算術交叉)，也可以是一個由進化代數所決定的變量（此時為非均勻算術交叉）。
2.4.3 變異操作
    變異[2]是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位來替換，從而形成一個新的個體。變異的目的是改善遺傳算法的局部搜索能力；維持群體的多樣性，防止早熟收斂。本文采用均勻變異算子，其具體操作過程是：
    (1)依次指定個體編碼串中的每個基因座為變異點，并確定每個基因點的取值范圍[Umin，Umax]；
    (2)對每一個變異點，以變異概率Pm從對應基因的取值范圍內取一個隨機數來代替原有值。其中變異點的新基因值為：
 
其中，r為(0，1)范圍內符合均勻概率分布的一個隨機數。
2.5 K-means優(yōu)化操作
    由于K-means是一種局部搜索能力強的算法，本文算法在每一代執(zhí)行完遺傳操作后引入了K-means算法中的一個操作步驟K-means操作，對新生種群中的每個個體進行K-means優(yōu)化，優(yōu)化后的群體作為下一代種群進入演化。這樣不僅可以提高混合算法的局部搜索能力，同時也有利于提高其收斂速度。具體的優(yōu)化操作如下：先以變異后產生的新群體的編碼值作為中心，把每個數據對象分配到最近的類，形成新的聚類劃分；然后計算新的聚類中心，取代原來的編碼值；經K-means優(yōu)化操作后產生新一代種群開始下一輪遺傳操作。
2.6 算法設計
    基于遺傳算法的K-means聚類算法（GKA）流程描述如下：
    (1)設置遺傳參數：聚類數k，種群規(guī)模m，最大迭代次數T，交叉概率Pc，變異概率Pm；
    (2)種群初始化：從樣本中隨機選取k個點作為聚類中心并進行編碼，重復m次，產生初始種群；
    (3)計算群體中各個體的適應度；
    (4)通過選擇、交叉、變異、K-means操作，產生新一代群體；
    (5)重復步驟(3)和步驟(4)，直到達到最大迭代次數T；
    (6)計算新一代群體的適應度，以最大適應度的最佳個體為中心進行K-means聚類；
    (7)輸出聚類結果。
3 實驗
    為了驗證算法的有效性，本文對K-means算法和GKA算法進行了對比實驗。在Matlab環(huán)境下分別編寫K-means算法和GKA算法，導入數據進行實驗。實驗數據來自KDD CUP[3]，數據集分別是iris和wine。其中，iris包含150個數據，分為3類，每類50個數據，每個數據包含4個屬性； wine數據集包含178個數據，分為3類，每個數據包含13個屬性。本文算法的參數設置如下：種群大小m=30，算法的最大迭代次數T=50，交叉概率Pc=0.9，變異概率Pm=0.001。所有算法各運行20次，運行結果如表1所示。

    從表1可以看出，K-means算法對初始聚類中心的選取敏感性很大，容易陷入局部最小值，并不是每次都能得到最優(yōu)解，特別是對于wine這種較高維度的數據集，有時聚類準確度不夠理想。除數據集iris外，K-means算法每組數據收斂到最優(yōu)解的平均迭代次數都比GKA算法多，所以GKA算法的收斂速度也較快。
    本文針對應用最為廣泛的K-means算法的缺點，提出了一種基于遺傳算法的K-means聚類算法GKA，將K-means算法的局部尋優(yōu)與遺傳算法的全局尋優(yōu)相結合，通過多次選擇、交叉、變異的遺傳操作，最終得到最優(yōu)的聚類數和初始質心集，克服了傳統(tǒng)K-means算法的局部性和對初始聚類中心的敏感性。實驗表明，GKA算法在聚類準確度和收斂速度上均比K-means算法更優(yōu)。
參考文獻
[1] 韓家煒，堪博．數據挖掘：概念與技術[M]．北京：機械工業(yè)出版社，2007.
[2] 吳多比．數據挖掘中基于遺傳算法的聚類方法應用研究[D].重慶：重慶大學，2009.
[3] UCI Mechine Learning Repository[EB/OL].http：//archive.ics.uci.edu/ml/datasets.html.