譚德燕,唐德玉

摘 要： 針對傳統(tǒng)K-means算法容易陷入局部最優(yōu)的缺點，提出了基于粒子群優(yōu)化的K-means算法。以肝臟疾病為例對新方法在醫(yī)學(xué)中的應(yīng)用進行了探討，使用 MATLAB編程工具進行驗證，實驗結(jié)果表明，新方法更優(yōu)于K-means算法。

關(guān)鍵詞： K-means； 粒子群優(yōu)化； PSO-k； 肝病

中圖分類號：TP301 文獻標志碼：A 文章編號：1006-8228（2013）06-34-02

Application of k-means algorithm in diagnosis of liver diseases based on PSO

Tan Deyan， Tang Deyu

（Medical information engineering institute， Guangdong college of pharmacy， Zhongshan， Guangdong 528458， China）

Abstract： In order to overcome the weakness of the traditional K-means algorithm that it is easily trapped into local optimization， a new K-means algorithm based on particle swarm optimization is presented in this paper. Taking the liver disease diagnosis as an example， the application of new methods in medicine is discussed and verified by MATLAB programming tool. The experimental results show that the new method is better than the traditional K-means algorithm.

Key words： K-means； particle swarm optimization； the PSO-k； liver disease

0 引言

數(shù)據(jù)挖掘技術(shù)中，聚類分析[1]被用作數(shù)據(jù)分析、數(shù)據(jù)理解和模式識別的有效工具，其中K-means算法是聚類分析中廣泛應(yīng)用的算法，它具有簡單、快速的優(yōu)點。本文針對K-means算法易陷入局部最小值和對初始值敏感的問題，引入粒子群算法，通過與K-means算法的有效結(jié)合來改善K-means的全局尋優(yōu)能力；以肝功能疾病的診斷為例，對新方法是否改進了K-means算法進行了研究。

1 K-means算法

K-means算法[2]是J. B. MacQueen在1967年提出的，它是一種被廣泛應(yīng)用于科學(xué)研究和工業(yè)應(yīng)用中的經(jīng)典聚類算法。

K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類，使每個聚類中的數(shù)據(jù)點到該聚類中心的平方和最小。其算法流程圖如圖1所示。

首先從n個數(shù)據(jù)對象中任意選擇k個對象作為初始聚類中心；而對于所剩下的其他對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類。然后再計算每個新聚類的聚類中心（該聚類中所有對象的均值）。不斷重復(fù)這一過程，直到標準測度函數(shù)開始收斂為止。一般都采用計算歐氏距離的方式進行計算。具體計算公式如下：

⑴

[滿足終止條件][開始][結(jié)束][選擇k個聚類中心][計算每一個數(shù)據(jù)對象與k個中心的距離，把它歸到距離最近的那個類中去][計算新的聚類中心][輸出結(jié)果] [否][是]

圖1 K-means算法流程圖

2 基于粒子群優(yōu)化的K-means算法

2.1 粒子群優(yōu)化算法介紹

粒子群算法（PSO）[3-4]是一種有效的全局尋優(yōu)算法，它是基于群體智能理論的優(yōu)化算法，通過群體中粒子間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索與進化算法比較，PSO保留了基于種群的全局搜索策略，將每個個體看作D維搜索空間中的一個沒有體積的微粒（點），在搜索空間中以一定的速度飛行。這個速度根據(jù)它本身的飛行經(jīng)驗，以及同伴的飛行經(jīng)驗進行動態(tài)地調(diào)整。第i個微粒表示為Xi=（Xi1，Xi2，…，XiD），它經(jīng)歷過的最好位置（有最好的適應(yīng)值）記為Pi=（Pi1，Pi2，…，PiD），也稱為Pid。在群體所有微粒經(jīng)歷過的最好位置的索引號稱為Pgd。微粒i的速度用Vi=（Vi1，Vi2，…，ViD）表示。對每一代，其第d維（1≤d≤D）根據(jù)如下方程變化：

Vid=ωVid+c1rand（）（Pid-Xid）+c2Rand（）（Pgd-Xid） ⑵

粒子移動的下一位置：

Vid'=Xid+Vid ⑶

其中：ω為慣性權(quán)重，c1和c2為加速常數(shù)，rand（）Rand（）為兩個在[0，1]范圍內(nèi)變化的隨機函數(shù)。此外，微粒的速度Vi被一個最大速度Vmax所限制。如果當前對微粒的加速導(dǎo)致它在某維的速度Vid超過該維的最大速度Vmaxd，則該維的速度被限制為該維最大速度Vmaxd。式子⑵的第一部分為微粒先前的速度；第二部分為“認知”部分，表示微粒本身的思考；第三部分為社會部分，表示微粒間的信息共享與相互合作。有關(guān)研究表明：由于ω較大算法具有較強的全局搜索能力，ω較小則算法傾向于局部搜索，所以對ω做如下改進：隨著迭代進行，速度更新公式的加權(quán)因子ω：

⑷

其中ω1和ω2分別是初始值和結(jié)束值。Max_iter和iter分別是最大值和當前慣性權(quán)重。

2.2 算法描述

根據(jù)上述K-means聚類和粒子群優(yōu)化算法原理，基于粒子群優(yōu)化的K-means聚類算法描述如下。

⑴ 在初始化粒子時，先將每個樣本隨機指派為某一類，作為最初的聚類劃分，并計算各類的聚類中心，作為初始粒子的位置編碼，計算粒子的適應(yīng)度，并初始化粒子的速度。反復(fù)進行N次，共生成N個粒子群。

⑵ 對每個粒子，比較它的適應(yīng)度值和它經(jīng)歷過的最好位置Pid的適應(yīng)度值，如果更好，更新Pid。

⑶ 對每個粒子，比較它的適應(yīng)度值和群體所經(jīng)歷的最好位置Pgd的適應(yīng)度值，如果更好，更新Pgd。

⑷ 根據(jù)⑵式和⑶式調(diào)整粒子的速度和位置。

⑸ 新個體的k均值優(yōu)化。

對于新一代粒子，按照以下的k均值算法進行優(yōu)化：

（a） 根據(jù)粒子的聚類中心編碼，按照最近鄰法則，來確定對應(yīng)該粒子的聚類劃分；

（b） 按照聚類劃分，計算新的聚類中心，更新粒子的適應(yīng)度值，取代原來的編碼值。

⑹ 如果達到結(jié)束條件（足夠好的位置或最大迭代次數(shù)），則結(jié)束，否則轉(zhuǎn)步驟⑵。

由于k均值具有很好的局部搜索能力，PSO的收斂速度會有效地提高。在步驟⑸中當重新分配數(shù)據(jù)集時，可能會發(fā)生一個空的聚類。如果有空的聚類產(chǎn)生的話，距離這個聚類中心最遠的一個數(shù)據(jù)點將被隨機選擇并被分配到這個空簇類中。

3 實驗結(jié)果及其分析

為了檢驗本文中提出的基于粒子群優(yōu)化的K-means算法在醫(yī)學(xué)中應(yīng)用的有效性和可行性，本文UCI機器學(xué)習(xí)數(shù)據(jù)庫中的Liver Disorders數(shù)據(jù)集作為測試樣本集。樣本集的實驗資料是取自理查德·福賽斯于1990年所撰寫的肝臟疾病資料集。該資料集是由隨機人群進行檢測，由生物醫(yī)學(xué)的儀器設(shè)備，花費多年時間，針對每位測試者的進行身體檢查，并紀錄測試結(jié)果而得。資料集中共有345個記錄樣本，6個輸入屬性為連續(xù)性資料，1個類別標記屬性status（或稱為輸出屬性），status的值有0與1兩種， 當status=1時表示為確定病例。樣本集可分為2個種類，這兩類樣本的個數(shù)分別為142、203。

部分屬性說明如下：紅細胞平均體積（MCV），堿性磷酸酶（alkphos），丙氨酸氨基轉(zhuǎn)移酶（sgpt），天門冬氨酸氨基轉(zhuǎn)移酶（sgot），γ-谷氨酰轉(zhuǎn)（gammagt），每天喝的酒精飲料的半脫品值（drinks number）。

本次實驗的試驗平臺如下。操作系統(tǒng)：Windows XP Service Pack3；CPU：Pentium（R） Dual-Core CPU T4500；內(nèi)存：1G；開發(fā)工具：matlab[5]。

本實驗首先使用K-means算法為每個聚類確定初始聚類中心，確保其能最小距離被分配到最鄰近聚類，將每個數(shù)據(jù)進行歸類分檔?；诹Ｗ尤簝?yōu)化的K-means算法主要通過對數(shù)據(jù)集進行種群的初始化優(yōu)化，不斷更新每個粒子的適應(yīng)度值然后對新個體進行k均值優(yōu)化，由于k均值具有較強的局部搜索能力，因此引入K均值優(yōu)化后的粒子群算法的收斂速度可以大大提高，從而更能接近全局最優(yōu)。此時數(shù)據(jù)集能得到最好的聚類效果，對于本實驗來說，得到好的聚類效果意味著能夠較準確地區(qū)分出某個人是否患有肝臟疾病，從而在醫(yī)學(xué)診斷上得到很好的應(yīng)用。

每個粒子都有其相應(yīng)的速度、位置和一個由目標函數(shù)決定的適應(yīng)度，算法通過適應(yīng)度來評價粒子的優(yōu)劣。粒子群和K 均值聚類算法采用基于聚類中心的編碼方式，也就是每個粒子的位置由m個聚類中心組成，粒子除了位置之外，還有速度和適應(yīng)度。設(shè)樣本向量維數(shù)為d，因此粒子的位置和速度是m×d維變量，另外每個粒子還有一個適應(yīng)度fi。這樣，粒子就可以采用以下的編碼結(jié)構(gòu)：C11 C12…C1d…C1mC2m…CdmV11V12…V1d…V1mV2m…Vdmfi。當聚類中心確定時，聚類的劃分由下面的最近鄰法則決定，若Xi，Cj滿足：

||Xi-Cj||=min||Xi-Ck||，k=1，2，…，m

則Xi屬于第j類。對于某粒子，按照以下方法計算其適應(yīng)度：

其中L為樣本數(shù)，Xi為輸入樣本[6]。

本文用K-means算法和PSO-K算法對數(shù)據(jù)集Liver Disorders樣本中的345個數(shù)據(jù)進行50次實驗，取其中的10次實驗結(jié)果。粒子群算法選用兩種參數(shù)，迭代次數(shù)（ge）為100，種群規(guī)模（q）為50，并以最初的聚類中心作為一個種群，分為兩個簇。分別得出這兩種算法的適應(yīng)度，其中適應(yīng)度越小越好。

表1 K-means算法與PSO-K算法運行10次適應(yīng)度結(jié)果對比

[ ＼&1＼&2＼&3＼&4＼&5＼&6＼&7＼&8＼&9＼&10＼&平均＼&PSO-K＼&9.8517＼&9.8149＼&9.7317＼&9.8382＼&9.8382＼&9.7909＼&9.9781＼&9.9906＼&9.7909＼&9.9781＼&9.86033＼&k-means＼&10.213＼&10.213＼&10.213＼&10.213＼&10.238＼&10.231＼&10.213＼&10.213＼&10.213＼&10.238＼&10.2198＼&]

由以上實驗結(jié)果可以明顯看出，基于粒子群優(yōu)化的K-means算法對肝病數(shù)據(jù)集進行數(shù)據(jù)分析所得到結(jié)果適應(yīng)度都比K-means小，由此可知其聚類效果更優(yōu)。

4 結(jié)束語

通過對K-means算法的研究，提出了基于粒子群優(yōu)化的K-means算法。實驗結(jié)果表明，該方法很好地解決了K-means算法易陷入局部最優(yōu)的問題，得到了較好的聚類效果，在幫助醫(yī)學(xué)診斷肝病方面能起到重要的作用，此時數(shù)據(jù)集能得到最好的聚類效果，對于本實驗來說，得到好的聚類效果意味著能夠較準確地區(qū)分出某個人是否患有肝臟疾病，因而該算法可以在醫(yī)學(xué)診斷上得到很好的應(yīng)用。

盡管本文對K-means算法提出了些許的改進，但相對于聚類分析的龐大體系而言這些改進僅為滄海一粟，而且由于時間和水平的限制，本文中的算法還有很多需要完善和深入研究的地方，下一步的工作有：①基于PSO的K-means算法雖然聚類效果比較好，但運行時間長，下一步將研究如何改進該算法的效率；②本文中的實驗都是小數(shù)據(jù)集上進行研究的，對于大的數(shù)據(jù)集其聚類的效率和時間還有待改進。

參考文獻：

[1] Han J W， Kamber M著，范明，孟小峰譯.數(shù)據(jù)挖掘概念與技術(shù)（第2

版）[M].機械工業(yè)出版社，2007.

[2] MacQueen J. Some Methods for Classification and Analysis of

Multitvariate Observations[C].In：Proceeding of the 5th Berkeley symposium on mathematical statistcs and probability. Berkeley，university of California press，1967：281-297

[3] EBERHART RC，KENNEDY J.A new optimizer using particle

swarm theory[A]. P.6th Int.Symposium on Micromachine and Human Science[C].Nagoya，japan，1995：39-43

[4] 基于粒子群優(yōu)化的k均值算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用[D].廣東工

業(yè)大學(xué)，2007.

[5] 宋麗紅.K-均值聚類的Matlab仿真設(shè)計[D].重慶工商大學(xué)，2010.

[6] 一種改進的粒子群和k均值混合聚類算法[D].哈爾濱工程大學(xué)，

2010.