基于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算法为每个聚类确定初始聚类中心，确保其能最小距离被分配到最邻近聚类，将每个数据进行归类分档。基于粒子群优化的K-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.