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

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

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

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