文/林龍成

（江蘇省南通衛(wèi)生高等職業(yè)技術(shù)學(xué)校 江蘇省南通市 226010）

K-means算法[1][2][3]是一種廣泛使用的聚類算法，思想簡(jiǎn)單易行，時(shí)間復(fù)雜度接近線性，對(duì)大數(shù)據(jù)集，具有高效性和可伸縮性。但是算法也有一些局限性，需事先給定聚類數(shù)k 值；對(duì)于初始值的選擇比較敏感，選擇不同的初始值，可能會(huì)導(dǎo)致不同的分類結(jié)果。

遺傳算法[4][5]被廣泛應(yīng)用于提高人工智能技術(shù)的性能。結(jié)合遺傳算法能夠?qū)ふ胰肿顑?yōu)解的優(yōu)勢(shì)，以及K-means 算法容易因?yàn)槌跏季垲愔行牡倪x擇不同而陷入局部最優(yōu)解的問題，本文利用遺傳算法初始化K-means的初始聚類中心點(diǎn)，提出基于遺傳算法的K-means聚類算法GA-K-means。

1 K-means聚類算法

K-means 算法，也被稱為k-均值算法，是基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，兩個(gè)數(shù)據(jù)點(diǎn)的距離越近，則相似度越大。計(jì)算樣本間的距離公式有歐氏距離、曼哈頓距離、余弦相似度等，其中最常用的是歐氏距離。

K-means 算法基本思想是通過迭代將數(shù)據(jù)集劃分為不同的類簇，使得用不同類簇的均值來代表相應(yīng)各類樣本中心時(shí)所得的總體方差最小。誤差平方和準(zhǔn)則函數(shù)公式為：

E 表示樣本空間中所有數(shù)據(jù)點(diǎn)到聚類中的平方誤差的總和。p表示數(shù)據(jù)對(duì)象，Ci表示第i 個(gè)類簇，mi表示第i 個(gè)類簇的平均值。

2 基于遺傳算法的K-means算法

2.1 GA-K-means算法的具體流程

GA-K-means 是在K-means 聚類中利用遺傳算法選擇最優(yōu)的初始種子。圖1 為GA-K-means 聚類的總體框架。

首先，系統(tǒng)生成初始種群，用于尋找全局最優(yōu)初始種子，遺傳算法對(duì)當(dāng)前種群進(jìn)行選擇、交叉和變異等遺傳操作，不斷更新種群，直到滿足停止條件；然后根據(jù)輸出的初始聚類中心，使用K-means算法進(jìn)行聚類，輸出聚類結(jié)果。

2.2 染色體編碼

以學(xué)習(xí)風(fēng)格為例，本文采用實(shí)數(shù)編碼方式，能夠直接反映問題的固有結(jié)構(gòu)，便于設(shè)計(jì)專門的遺傳算子，緩解“組合爆炸”的問題。染色體的結(jié)構(gòu)如表1 所示，前4 位表示第一聚類中心的學(xué)習(xí)風(fēng)格向量，依次類推。

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

表1：染色體編碼

表2：10 次實(shí)驗(yàn)結(jié)果

圖1：GA-K-means 算法

圖2：?jiǎn)吸c(diǎn)交叉

圖3：變異操作

適應(yīng)度函數(shù)是促使遺傳算法收斂到最優(yōu)解的一個(gè)因素。我們選擇總最小距離函數(shù)作為染色體強(qiáng)度的適應(yīng)度函數(shù)，以找到K-means算法的最優(yōu)初始種子。適應(yīng)度函數(shù)定義如下：

其中，Gi表示第i 個(gè)聚類，Lj 表示屬于Gi的學(xué)習(xí)者，LSj表示第j 個(gè)學(xué)習(xí)者Lj的學(xué)習(xí)風(fēng)格向量，gj表示Gj 的聚類中心。適應(yīng)度函數(shù)Fit 越小，說明初始聚類中心的選擇越好.

2.4 遺傳算子

圖4：兩種算法的聚類結(jié)果

在遺傳算法中，通過一些列算子來決定子代的生成，本文使用選擇、交叉、變異算子，交叉算子通過雙親染色體交換有意義的遺傳物質(zhì)來產(chǎn)生兩個(gè)新的后代，變異算子通過向種群中引入一個(gè)全新的成員來維持種群的遺傳多樣性。

2.4.1 選擇算子

選擇操作通過適應(yīng)度選擇優(yōu)質(zhì)個(gè)體，拋棄劣質(zhì)個(gè)體，體現(xiàn)了“適者生存”的生物法則。常見的選擇操作主要有：輪盤賭選擇、排序選擇、最優(yōu)個(gè)體保存及隨機(jī)聯(lián)賽選擇。本文采用輪盤賭選擇方式，某染色體被選的概率Pc 為：

其中：f(xi)表示第i 個(gè)染色體的適應(yīng)度值；∑f(xi)表示種群中所有染色體適應(yīng)度值之和。

2.4.2 交叉算子

交叉是指兩個(gè)染色體按照某種方式交換部分基因信息，從而產(chǎn)生兩個(gè)新的染色體。常用的交叉方法有：?jiǎn)吸c(diǎn)交叉、雙點(diǎn)交叉、均勻交叉及算術(shù)交叉。本文使用單點(diǎn)交叉，從其中可能的三個(gè)交叉點(diǎn)P1、P2、P3、P4中隨機(jī)選擇一個(gè)交叉點(diǎn)。交叉操作如圖2 所示，其中P2 是所選交叉點(diǎn)。

2.4.3 變異算子

變異是指以一定概率隨機(jī)改變?nèi)旧w編碼串中部分基因值，形成新的個(gè)體。常用的變異方法有：基本位變異、均勻變異、二元變異及高斯變異。本文采用基本位變異方法，從五種可能性（I 到V）中選擇一個(gè)隨機(jī)基因組（四位），并根據(jù)學(xué)習(xí)風(fēng)格情境，使用相反選擇答案得到的4 位編碼串替換它。變異操作如圖3 所示，IV 基因被反向基因組（7 8 10 6）替換。

2.5 K-means聚類

（1）以遺傳算法得到的最優(yōu)解作為初始聚類中心

（2）計(jì)算所有數(shù)據(jù)對(duì)象到這k 個(gè)初始聚類中心的距離，并將數(shù)據(jù)劃歸到離其最近的那個(gè)中心所在的類

（3）重新計(jì)算已經(jīng)得到的各個(gè)簇的質(zhì)心，作為新的聚類中心

（4）計(jì)算公式（1）中的準(zhǔn)則函數(shù)E，若E 不滿足，重復(fù)第2、3 步，直到聚類的中心不再移動(dòng)，輸出聚類結(jié)果

3 實(shí)證分析

為了檢驗(yàn)本文提出的算法的有效性及對(duì)學(xué)生學(xué)習(xí)風(fēng)格進(jìn)行分析，本文使用MATLAB 進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境的硬件配置為 Inter(R)Core(TM)i5-3470 CPU@3.20GHz 4.00GB，開發(fā)環(huán)境為 MATLAB R2016a。

下面采用傳統(tǒng)K-means 和GA-K-means 分別對(duì)學(xué)習(xí)風(fēng)格數(shù)據(jù)進(jìn)行分類，驗(yàn)證本文提出的GA-K-means 算法的有效性。實(shí)驗(yàn)結(jié)果如圖4 所示。

可以看出，傳統(tǒng)K-means 算法雖然收斂速度快，但是容易陷入局部最優(yōu)解，而本文提出的GA-K-means 算法則能夠避免早熟現(xiàn)象，且收斂平穩(wěn)，收斂效果明顯優(yōu)于傳統(tǒng)K-means 算法。

為了進(jìn)一步驗(yàn)證算法的有效性，對(duì)傳統(tǒng)K-means 算法和本文提出的GA-K-means 算法分別進(jìn)行10 次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2 所示。其中匹配度計(jì)算公式為：

從表2 可以看出，由于傳統(tǒng)K-means 算法對(duì)初始聚類中心的選擇比較敏感，導(dǎo)致每次聚類結(jié)果都有很大差異，10 次實(shí)驗(yàn)結(jié)果的匹配度較低，而本文提出的GA-K-means 算法匹配度較高，具有較好的穩(wěn)定性。

4 結(jié)論

本文在傳統(tǒng)K-means 算法的基礎(chǔ)上，提出了基于遺傳算法的GA-K-means 聚類算法。該方法彌補(bǔ)了K-means 在尋找全局最優(yōu)解方面的不足，在穩(wěn)定性和有效性方面都明顯好于傳統(tǒng)K-means 聚類算法。