凌 靜，江凌云，趙 迎

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

0 引 言

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

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

文中提出一種結(jié)合模擬退火算法的遺傳K-Means聚類方法。配合局部尋優(yōu)能力強的模擬退火算法改進遺傳算法的缺陷，得到性能在兩者之上的遺傳模擬退火算法，再將其應(yīng)用于K-Means算法，從而提高K-Means聚類算法的性能，實現(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算法的詳細步驟，并用數(shù)學(xué)方法對K-Means算法進行了證明。K-Means算法的主要思想[5]是：對n個給定的對象，給出k個劃分，每個劃分代表一個類，其中k≤n。首先，從給定的所有對象中任意選擇k個對象，作為k個類的聚類中心。對剩余對象，分別計算它們與各個聚類中心的相似度，分到相似度最高的類中；分類完成后，計算新類的平均值作為新的聚類中心，再計算所有對象與新聚類中心的相似度，將對象分到最相似的類中。不斷重復(fù)直到準則函數(shù)的值達到最小，準則函數(shù)定義如下：

(1)

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

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

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

1.2 遺傳模擬退火算法

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

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

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

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

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

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

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

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

2.1 樣本編碼

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

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

圖2 樣本編碼

舉例：一個數(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)，編碼長度l=6。

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

2.2 種群初始化

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

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

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

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

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

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

(2)

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

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

2.4 選擇操作

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

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

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

(3)

在父群體中進行sizepop次選擇，即生成新種群P1。

2.5 模擬退火變異操作

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

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

(4)

(5)

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

對父種群P1中的每個個體都進行上述模擬退火變異操作，得到新群體P2。

2.6 K-Means操作

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

(6)

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

對父種群P2中所有個體都進行KMO操作，形成新的種群P3。然后再進行下一輪遺傳操作。

2.7 聚類方法的具體過程

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

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

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

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

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

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

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

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

圖3 聚類方法流程

3 實驗結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)束語

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