凌 靜，江凌云，趙 迎

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

迄今為止已經(jīng)有了多種聚類算法，根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則，以及應(yīng)用這些規(guī)則的方法，聚類算法主要可以分為[1]：基于劃分、基于層次、基于網(wǎng)格、基于密度以及基于模型等類型。聚類算法被廣泛應(yīng)用于模式識(shí)別、圖像處理、文本檢索、網(wǎng)絡(luò)入侵檢測(cè)、生物信息學(xué)等領(lǐng)域。其中，K-Means聚類算法是最為經(jīng)典的一種聚類算法[2]，優(yōu)點(diǎn)是簡(jiǎn)單有效、收斂速度快、局部搜索能力強(qiáng)；但也存在難以克服的缺陷，如過度依賴初始聚類中心、聚類結(jié)果極易陷入局部最優(yōu)解、全局搜索能力不強(qiáng)等。

針對(duì)K-Means聚類算法過度依賴初始聚類中心，全局搜索能力不強(qiáng)的問題，已經(jīng)有了大量的研究成果，如文獻(xiàn)[3-4]中提出的遺傳K-Means算法、優(yōu)化遺傳K-Means算法等。這些結(jié)合遺傳算法的改進(jìn)方法，有效提高了K-Means聚類算法的穩(wěn)定性和全局性，但遺傳算法自身存在早熟現(xiàn)象，且其局部尋優(yōu)能力較弱。

文中提出一種結(jié)合模擬退火算法的遺傳K-Means聚類方法。配合局部尋優(yōu)能力強(qiáng)的模擬退火算法改進(jìn)遺傳算法的缺陷，得到性能在兩者之上的遺傳模擬退火算法，再將其應(yīng)用于K-Means算法，從而提高K-Means聚類算法的性能，實(shí)現(xiàn)聚類結(jié)果的優(yōu)化。

1 相關(guān)工作

1.1 K-Means算法、遺傳算法與模擬退火算法

K-Means算法是一種基于劃分的經(jīng)典聚類算法，是由Mac Queen于1967年提出的，他結(jié)合Cox、Fisher、Sebestyen等的研究成果，給出了K-Means算法的詳細(xì)步驟，并用數(shù)學(xué)方法對(duì)K-Means算法進(jìn)行了證明。K-Means算法的主要思想[5]是：對(duì)n個(gè)給定的對(duì)象，給出k個(gè)劃分，每個(gè)劃分代表一個(gè)類，其中k≤n。首先，從給定的所有對(duì)象中任意選擇k個(gè)對(duì)象，作為k個(gè)類的聚類中心。對(duì)剩余對(duì)象，分別計(jì)算它們與各個(gè)聚類中心的相似度，分到相似度最高的類中；分類完成后，計(jì)算新類的平均值作為新的聚類中心，再計(jì)算所有對(duì)象與新聚類中心的相似度，將對(duì)象分到最相似的類中。不斷重復(fù)直到準(zhǔn)則函數(shù)的值達(dá)到最小，準(zhǔn)則函數(shù)定義如下：

(1)

其中，k為類別數(shù)；xi為樣本對(duì)象；zj為類cj的聚類中心。

遺傳算法(GA)是一種全局優(yōu)化自適應(yīng)概率搜索算法，由Holland于1975年提出的。該算法模擬了生物的繁衍、交配和變異現(xiàn)象[6]，在初始種群的基礎(chǔ)上產(chǎn)生新的更適應(yīng)環(huán)境的種群，一代代繁衍進(jìn)化，最終收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上。在搜索過程中，該算法能夠自動(dòng)獲取搜索空間的相關(guān)知識(shí)，并積累獲得的信息；通過對(duì)搜索過程的自適應(yīng)控制，能夠獲得問題的最優(yōu)解。遺傳算法使用適應(yīng)度函數(shù)作為度量標(biāo)準(zhǔn)，通過計(jì)算群體中的每個(gè)個(gè)體的適應(yīng)度函數(shù)值，來判斷個(gè)體的優(yōu)劣程度。適應(yīng)度函數(shù)值越高，個(gè)體越優(yōu)秀，就越有可能被遺傳到新種群中，成為最適應(yīng)環(huán)境個(gè)體的概率也就越高。一般會(huì)根據(jù)實(shí)際情況設(shè)計(jì)相應(yīng)的適應(yīng)度函數(shù)。

模擬退火算法(SA)又被稱為模擬冷卻法、概率爬山法，是由Kirpatrick于1982年提出的。模擬退火算法是模擬了一個(gè)高溫固體的退火過程[7]，在搜索過程中，開始先設(shè)定一個(gè)溫和的初始結(jié)果作為最優(yōu)解，然后隨機(jī)獲得一個(gè)新解，當(dāng)?shù)玫降男陆鈨?yōu)于當(dāng)前最優(yōu)解時(shí)，直接接受新解為最優(yōu)解；當(dāng)新解劣于最優(yōu)解時(shí)，以一定的概率接受新解為最優(yōu)解，隨著溫度的下降重復(fù)上述操作，最終得到全局最優(yōu)解。模擬退火算法利用了概率的突跳特性，具有并行性和漸近收斂性，理論上能夠證明，模擬退火算法是以概率1收斂于全局最優(yōu)解的。

1.2 遺傳模擬退火算法

在遺傳算法運(yùn)行過程中，早期種群的個(gè)體之間差異較大即個(gè)體適應(yīng)度函數(shù)值差異較大，而在通過選擇算子生成下一代新種群時(shí)，新種群的子個(gè)體出現(xiàn)概率與上一代種群中父?jìng)€(gè)體的適應(yīng)度函數(shù)值成正比，也就是說，適應(yīng)度值越高的個(gè)體越容易遺傳到下一代種群中，這就容易出現(xiàn)優(yōu)秀個(gè)體占領(lǐng)整個(gè)種群，形成早熟現(xiàn)象。后期，整個(gè)種群中的個(gè)體適應(yīng)度值基本一致，差異較小，這就導(dǎo)致優(yōu)秀個(gè)體在生成下一代種群個(gè)體時(shí)的優(yōu)勢(shì)較小，造成整個(gè)種群的進(jìn)化停滯。因此，在算法運(yùn)行過程中可以對(duì)個(gè)體的適應(yīng)度函數(shù)值進(jìn)行適當(dāng)拉伸。

模擬退火算法中按照Metropolis準(zhǔn)則[8]接受新解，除了接受優(yōu)于當(dāng)前最優(yōu)解的新解作為新的最優(yōu)解，還能以一定的概率接受劣于當(dāng)前最優(yōu)解的新解。在算法早期，溫度值T較大，能夠接受較劣的新解。隨著算法不斷運(yùn)行，T值也在不斷變小，當(dāng)前最優(yōu)解的值會(huì)越來越逼近整體最優(yōu)解，當(dāng)T值接近0時(shí)，當(dāng)前最優(yōu)解最接近整體最優(yōu)解，能夠避免算法陷入局部最優(yōu)。

遺傳模擬退火算法是一種優(yōu)化算法[9]，在算法前期，種群中個(gè)體的適應(yīng)度相差較大即存在較為突出的優(yōu)良個(gè)體，而此時(shí)溫度較高，有較大可能接受較差的個(gè)體，避免種群過早集中于優(yōu)良個(gè)體；而在算法后期，種群中個(gè)體的適應(yīng)度函數(shù)值較為接近，此時(shí)溫度較低，模擬退火算法能對(duì)遺傳算法中這些個(gè)體的適應(yīng)度函數(shù)值進(jìn)行拉伸，放大這些個(gè)體之間的適應(yīng)度差異，提高優(yōu)秀個(gè)體在選擇過程中的優(yōu)勢(shì)。遺傳模擬退火算法能夠更加快速有效地收斂到全局最優(yōu)解。

已有許多研究嘗試將遺傳算法與K-Means聚類算法進(jìn)行結(jié)合，以改善K-Means聚類算法的缺陷。文獻(xiàn)[10]將基于準(zhǔn)則函數(shù)的經(jīng)典聚類算法K-Means引入到遺傳算法，用K-Means算法的一步—K-means操作(KMO)代替標(biāo)準(zhǔn)遺傳算法中的交叉操作，這樣既能利用遺傳算法確保聚類結(jié)果的穩(wěn)定性，又能借助K-Means算法提高混合算法的收斂速度。

該算法融合了遺傳算法與K-Means算法，保證了算法的全局搜索能力，也保證了算法的簡(jiǎn)單有效，同時(shí)還具有爬山能力。然而遺傳算法自身還存在早熟、局部尋優(yōu)能力弱等缺點(diǎn)。為此，在文獻(xiàn)[10]的基礎(chǔ)上，文中提出一種結(jié)合模擬退火算法的遺傳K-Means聚類方法。將模擬退火算法引入已有的遺傳K-Means算法，保留K-Means操作取代交叉操作的方法，通過模擬退火算法增強(qiáng)聚類方法的局部搜索能力，實(shí)現(xiàn)聚類結(jié)果的進(jìn)一步優(yōu)化。

2 結(jié)合模擬退火算法的遺傳K-Means聚類方法

標(biāo)準(zhǔn)遺傳算法中包括選擇操作、交叉操作以及變異操作。文獻(xiàn)[10]提出的方法在遺傳算法中引入K-Means操作代替交叉操作，文中在其基礎(chǔ)上，引入模擬退火算法對(duì)遺傳算法的變異操作進(jìn)行改進(jìn)，改善遺傳算法的早熟缺點(diǎn)，避免結(jié)果陷入局部最優(yōu)，提高原有遺傳K-Means聚類算法的性能，從而實(shí)現(xiàn)聚類結(jié)果的優(yōu)化。該方法的整體結(jié)構(gòu)如圖1所示。

圖1 聚類方法整體結(jié)構(gòu)

2.1 樣本編碼

樣本編碼[11]是遺傳算法的基礎(chǔ)操作，要將問題的解進(jìn)行編碼才能進(jìn)行后續(xù)操作。遺傳算法有多種編碼方式，如符號(hào)編碼、二進(jìn)制編碼、浮點(diǎn)數(shù)編碼等。在聚類樣本維度高、數(shù)量大時(shí)，如果采用傳統(tǒng)的二級(jí)制編碼方式，種群中的個(gè)體編碼長(zhǎng)度會(huì)隨著維度的增加、精度的提高而出現(xiàn)顯著增加的情形，從而導(dǎo)致整個(gè)搜索空間的增大，影響聚類方法的計(jì)算效率。因此文中采用的是一種基于聚類中心的十進(jìn)制編碼方式。

具體編碼方式如下：設(shè)一個(gè)數(shù)據(jù)集中的樣本個(gè)數(shù)為n，最終聚類的類別數(shù)目為k。有k個(gè)聚類中心，每個(gè)中心對(duì)應(yīng)一個(gè)類別號(hào)，計(jì)算所有樣本到各個(gè)聚類中心的距離，將其劃分到相應(yīng)的類中，編碼值對(duì)應(yīng)樣本所屬聚類的類別號(hào)，最終編碼長(zhǎng)度l=n。如圖2所示，Sn為聚類的類別號(hào)，編碼總長(zhǎng)度為n。

圖2 樣本編碼

舉例：一個(gè)數(shù)據(jù)集為{x1,x2,x3,x4,x5,x6}，類別數(shù)目k=3，分類模式為1{x1,x4} 2{x3,x6} 3{x2,x5}，則編碼為(1 3 2 1 3 2)，編碼長(zhǎng)度l=6。

文中采用的這種基于聚類中心的編碼方式直觀明確，相比二進(jìn)制編碼有效縮短了個(gè)體編碼的長(zhǎng)度，提高了整體的計(jì)算效率，對(duì)于大數(shù)據(jù)復(fù)雜問題的求解效果較好。

2.2 種群初始化

文中采用隨機(jī)方式生成初始種群，具體方法為：從樣本空間中隨機(jī)選出k個(gè)樣本作為聚類中心，將所有樣本按其到各個(gè)聚類中心的距離分類到k個(gè)類中，得到一個(gè)個(gè)體，計(jì)算此時(shí)的個(gè)體編碼Sn；設(shè)種群大小為sizepop，將上述操作重復(fù)進(jìn)行sizepop次，即可得到初始種群P0。

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)[12]會(huì)影響整個(gè)聚類方法的收斂速度，以及對(duì)最優(yōu)解的確定。一般使用適應(yīng)度函數(shù)來衡量個(gè)體的適應(yīng)度，判別該個(gè)體在種群中的優(yōu)劣程度。某個(gè)體適應(yīng)度的值越大，該個(gè)體在整個(gè)遺傳過程中的存活概率也就越大。

K-Means算法中判斷聚類劃分質(zhì)量的標(biāo)準(zhǔn)是準(zhǔn)則函數(shù)J，J的值與所有聚類中的點(diǎn)到相應(yīng)聚類中心的距離總和相等。J的值越小，表明該聚類劃分的質(zhì)量越好，反之表明該聚類劃分的質(zhì)量越差。

對(duì)于種群中的每個(gè)個(gè)體，根據(jù)準(zhǔn)則函數(shù)J來構(gòu)造適應(yīng)度函數(shù)，適應(yīng)度函數(shù)定義如下：

F(Si)=1.5×Jmax-J(Si),i=1,2,…,sizepop

(2)

其中，Jmax是種群中所有個(gè)體的準(zhǔn)則函數(shù)值的最大值；J(Si)是當(dāng)前個(gè)體的準(zhǔn)則函數(shù)值。

根據(jù)函數(shù)定義可以看出，準(zhǔn)則函數(shù)J的值越小，該個(gè)體代表的聚類劃分的質(zhì)量越好，適應(yīng)度函數(shù)值越大，其存活概率也就越高。

2.4 選擇操作

選擇操作[13]遵循優(yōu)勝劣汰原則，以個(gè)體的適應(yīng)度函數(shù)值為基礎(chǔ)，由父種群選出新種群。在進(jìn)行選擇操作時(shí)，適應(yīng)度函數(shù)值越大的個(gè)體經(jīng)過選擇操作后，遺傳到新種群中的概率就越高，反之被遺傳到新種群中的概率就越小，經(jīng)過多次選擇操作得到的個(gè)體組成新種群。

選擇操作常用的方法有輪盤賭選擇法、最優(yōu)個(gè)體保留法、錦標(biāo)賽選擇法[14]，文中使用輪盤賭方法來進(jìn)行選擇操作。輪盤賭方法是將種群中所有個(gè)體適應(yīng)度函數(shù)的總和，作為輪盤的整個(gè)圓周，按照每個(gè)個(gè)體的適應(yīng)度值在總和中所占的比例，為其分配輪盤中相應(yīng)大小的扇區(qū)。每選擇一個(gè)個(gè)體就是隨機(jī)轉(zhuǎn)動(dòng)一次輪盤，轉(zhuǎn)動(dòng)輪盤后選中哪個(gè)區(qū)域，就選擇該區(qū)域?qū)?yīng)的個(gè)體作為新種群的個(gè)體。在輪盤賭方法中，面積越大的區(qū)域越有可能被選中，反之被選中的概率就越低，而適應(yīng)度函數(shù)值越大的個(gè)體其面積也就越大。

種群P中第i個(gè)個(gè)體的適應(yīng)度函數(shù)值為F(Si)，則個(gè)體i被選中的概率為：

(3)

在父群體中進(jìn)行sizepop次選擇，即生成新種群P1。

2.5 模擬退火變異操作

變異操作[15]按位進(jìn)行，在個(gè)體編碼時(shí)每個(gè)樣本都有多個(gè)可能的編碼值，變異就是將指定位置的樣本的現(xiàn)有編碼值，按變異概率Pi用其余的可能值進(jìn)行替換。

文中使用的是均勻變異操作，具體過程為：對(duì)個(gè)體編碼上的每個(gè)樣本點(diǎn)，依次進(jìn)行變異操作，也就是按概率Pi從樣本現(xiàn)有的類別號(hào)中選一個(gè)編碼值替代原有值，最終得到新個(gè)體。變異概率Pi定義如下：

(4)

(5)

其中，d(xi-ck)是樣本xi與第k個(gè)簇的質(zhì)心ck之間的歐幾里得距離。引入偏差0.5是為了避免除0錯(cuò)誤。這里采用的概率Pi不是固定值，使得個(gè)體上每個(gè)基因座的變異概率都不同，能夠大幅度提高個(gè)體的變異概率，進(jìn)一步避免遺傳算法的早熟現(xiàn)象。

對(duì)父種群P1中的每個(gè)個(gè)體都進(jìn)行上述模擬退火變異操作，得到新群體P2。

2.6 K-Means操作

為了加速聚類算法的收斂過程，使用K-Means算法中的一個(gè)步驟，即K-Means操作(KMO)代替遺傳算法中的交叉操作。K-Means操作的具體過程為：經(jīng)過選擇操作，模擬退火變異操作后得到新的種群P2。對(duì)群體P2中的某個(gè)個(gè)體，根據(jù)其現(xiàn)有的聚類結(jié)果計(jì)算新的聚類中心，計(jì)算方法如下：

(6)

然后計(jì)算數(shù)據(jù)集中所有樣本到這些新的聚類中心的距離，并將樣本分配到距離最近的類中，從而獲得新個(gè)體。

對(duì)父種群P2中所有個(gè)體都進(jìn)行KMO操作，形成新的種群P3。然后再進(jìn)行下一輪遺傳操作。

2.7 聚類方法的具體過程

文中聚類方法主要包含2層循環(huán)：外層為遺傳K-Means算法的進(jìn)化循環(huán)，內(nèi)層為模擬退火算法的降溫循環(huán)。

算法的具體過程(見圖3)如下：

(1)初始化控制參數(shù)：聚類個(gè)數(shù)k，種群個(gè)數(shù)sizepop，最大迭代次數(shù)MAXGEN；退火初始溫度T0，溫度冷卻系數(shù)a，模擬退火內(nèi)部迭代次數(shù)N，終止溫度Te；

(2)隨機(jī)初始化k個(gè)聚類中心，依照聚類中心對(duì)各個(gè)樣本進(jìn)行聚類得到一個(gè)個(gè)體，重復(fù)sizepop次生成初始種群P0；

(3)計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值：F(Si)，i=1,2,…,sizepop；

(4)對(duì)初始種群P0依次進(jìn)行選擇操作、模擬退火變異操作、K-Means操作，生成新種群；

(5)重復(fù)步驟3和步驟4，直到達(dá)到最大迭代次數(shù)MAXGEN；

(6)將最后生成的種群中適應(yīng)度函數(shù)值最大的個(gè)體作為聚類結(jié)果輸出。

圖3 聚類方法流程

3 實(shí)驗(yàn)結(jié)果

對(duì)傳統(tǒng)K-Means算法、文獻(xiàn)[4]中提出的遺傳K-Means算法以及文中提出的結(jié)合模擬退火算法的遺傳K-Means聚類方法進(jìn)行了對(duì)比實(shí)驗(yàn)。

實(shí)驗(yàn)工具為MATLAB軟件，實(shí)驗(yàn)數(shù)據(jù)是來自UCI Machine Learning Repository的iris數(shù)據(jù)集和wine數(shù)據(jù)集。其中iris數(shù)據(jù)集包含150個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)有4個(gè)屬性，一共分為3類，每類各有50個(gè)數(shù)據(jù)；wine數(shù)據(jù)集包含178個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)有13個(gè)屬性，一共分為3類，每類分別有59、71、48個(gè)數(shù)據(jù)。

分別編寫K-Means算法、遺傳K-Means算法以及文中的聚類方法，導(dǎo)入iris數(shù)據(jù)集和wine數(shù)據(jù)集進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果分別如表1和表2所示。

表1 平均聚類準(zhǔn)確度(iris數(shù)據(jù)集) %

表2 平均聚類準(zhǔn)確度(wine數(shù)據(jù)集) %

通過對(duì)表1和表2的實(shí)驗(yàn)結(jié)果進(jìn)行分析，可以看出，與傳統(tǒng)K-Means聚類算法相比，GAKM算法的準(zhǔn)確率有了明顯的提升，而且傳統(tǒng)K-Means聚類算法中會(huì)出現(xiàn)計(jì)算結(jié)果的浮動(dòng)，每次的聚類結(jié)果都會(huì)存在較大的差異，而GAKM算法相對(duì)來說就比較穩(wěn)定，結(jié)果基本不會(huì)發(fā)生太大的變化。

在iris數(shù)據(jù)集中，文中方法的平均聚類準(zhǔn)確率最高能夠達(dá)到90.99%，最低能達(dá)到88.53%，高于GAKM算法的84.78%；在wine數(shù)據(jù)集中，文中方法的平均聚類準(zhǔn)確率能達(dá)到71.46%，同樣高于GKAM算法中的70.13%。通過數(shù)據(jù)對(duì)比可以發(fā)現(xiàn)，文中的聚類方法相對(duì)GAKM算法平均聚類準(zhǔn)確度有了提升，而且能保證聚類結(jié)果的穩(wěn)定。

標(biāo)準(zhǔn)K-Means聚類算法的計(jì)算結(jié)果受選取的初始聚類中心的影響較大，初始中心選擇不當(dāng)會(huì)導(dǎo)致結(jié)果陷入局部最優(yōu)；基于遺傳算法的K-Means聚類算法由于遺傳算法自身的缺陷，容易出現(xiàn)早熟現(xiàn)象，其局部尋優(yōu)能力較弱；文中提出的結(jié)合模擬退火算法的遺傳K-Means聚類方法，充分利用模擬退火算法較強(qiáng)的局部尋優(yōu)能力，改善遺傳算法的缺陷，改善早熟現(xiàn)象，有效避免聚類結(jié)果陷入局部最優(yōu)，最終獲得的聚類結(jié)果要優(yōu)于K-Means算法與GKAM算法。

4 結(jié)束語

提出一種結(jié)合遺傳模擬退火算法的K-Means聚類方法，使用K-Means操作取代遺傳算法的交叉操作，并引入模擬退火算法對(duì)遺傳算法中的變異操作進(jìn)行改進(jìn)。該算法有效地解決了K-Means聚類算法過于依賴初始中心選擇，易于陷入局部最優(yōu)等問題，克服了遺傳算法容易出現(xiàn)早熟現(xiàn)象以及局部搜索能力較弱的缺點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該方法有效提高了K-Means聚類算法的聚類精度，聚類結(jié)果更加準(zhǔn)確。