基于PSO的K均值算法在肝病診斷中的應用

譚德燕,唐德玉

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

關鍵詞： K-means； 粒子群優化； 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 引言

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

1 K-means算法

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

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

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

⑴

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

圖1 K-means算法流程圖

2 基于粒子群優化的K-means算法

2.1 粒子群優化算法介紹

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

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

粒子移動的下一位置：

Vid'=Xid+Vid ⑶

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

⑷

其中ω1和ω2分別是初始值和結束值。Max_iter和iter分別是最大值和當前慣性權重。

2.2 算法描述

根據上述K-means聚類和粒子群優化算法原理，基于粒子群優化的K-means聚類算法描述如下。

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

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

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

⑷ 根據⑵式和⑶式調整粒子的速度和位置。

⑸ 新個體的k均值優化。

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

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

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

⑹ 如果達到結束條件（足夠好的位置或最大迭代次數），則結束，否則轉步驟⑵。

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

3 實驗結果及其分析

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

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

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

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

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

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

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

其中L為樣本數，Xi為輸入樣本[6]。

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

表1 K-means算法與PSO-K算法運行10次適應度結果對比

[ ＼&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＼&]

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

4 結束語

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

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

參考文獻：

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

版）[M].機械工業出版社，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] 基于粒子群優化的k均值算法在網絡入侵檢測中的應用[D].廣東工

業大學，2007.

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

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

2010.