２０１２年２月　第３３卷第２期　计算机工程与设计　

ＣＯＭＰＵＴＥＲ　ＥＮＧＩＮＥＥＲＩＮＧ　ＡＮＤ　ＤＥＳＩＧＮ　Ｆｅｂ．２０１２　Ｖｏ１．３３　ＮＯ．２　

Ｗｅｋａ平台上解决聚类的改进差分进化算法　

姜凯，左风朝　

（聊城大学计算机学院，山东聊城２５２０５９）　

摘要：针对Ｋ均值算法的缺陷，提出一种用于解决聚类问题的差分进化算法对聚类的准则函数进行优化，为了能够进一　

步增强算法的全局搜索能力，引入一种基于种群适应度方差的自适应策略来动态调整变异概率ｃＲ和规模因子Ｆ等参数，　

充分利用在Ｗｅｋａ工具中的类和接口，并将新提出的算法嵌入到平台中。在Ｗｅｋａ平台上将该算法与Ｋ均值算法在３个　

ＵＣＩ数据集上进行比较。仿真实验结果表明，该算法能够有效克服Ｋ均值算法的缺陷，能够获得较高的聚类质量。　

关键词：聚类；自适应差分进化算法；适应度方差；Ｋ均值；Ｗｅｋａ平台　

中图法分类号：ＴＰ３１１　文献标识号：Ａ　文章编号：１０００—７０２４（２０１２）０２—０５９１—０４　

Ａｄｖａｎｃｅｄ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ　ｏｎ　Ｗｅｋａ　

ＪＩＡＮＧ　Ｋａｉ，ＺＵＯ　Ｆｅｎｇ－ｃｈａｏ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｌｉａｏｃｈｅｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌｉａｏｃｈｅｎｇ　２５２０５９，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｆｔｅｒ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｄｒａｗｂａｃｋｓ　ｏｆ　ｔｈｅ　Ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ，ａ　ｎｏｖｅｌ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｃｌｕｓｔｅｒｉｎｇ　

ｐｒｏｂｌｅｍ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｏｐｔｉｍｉｚｅ　ｔｈｅ　ｃｒｉｔｅｒｉｏｎ　ｆｕｎｃｔｉｏｎ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｆｕｒｔｈｅｒ　ｅｎｈａｎｃｅ　ｔｈｅ　ｃａｐａｂｉｌｉｔｙ　ｏｆ　ｇｌｏｂａｌ　ｓｅａｒｃｈ，　

ａ　ｓｅｌｆ－ａｄａｐｔｉｖｅ　ｓｔｒａｔｅｇｙ　ｕｓｉｎｇ　ｆｉｔｎｅｓｓ　ｖａｒｉａｎｃｅ　ｏｆ　ｔｈｅ　ｐｏｐｕｌａｔｉｏｎ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ　ｔｏ　ａｄｊｕｓｔ　ｓｃａｌｉｎｇ　ｆａｃｔｏｒ　ａｎｄ　ｃｒｏｓｓｏｖｅｒ　ｐｒｏｂａｂｉｌｉｔｙ．　

Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｐｐｒｏａｃｈ　ｉｓ　ｉｍｐｌｅｍｅｎｔｅｄ　Ｏｎ　ｔｈｅ　Ｗｅｋａ　ｐｌａｔｆｏｒｍ　ｗｈｅｒｅ　ｉｔｓ　ｃｌａｓｓｅｓ　ａｎｄ　ｉｎｔｅｒｆａｃｅｓ　ａｒｅ　ｆｕｌｌｙ　ｕｔｉｌｉｚｅｄ．Ａｔ　ｌａｓｔ，ｔｈｅ　ｐｒｏ—　

ｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｔｅｓｔｅｄ　ｏｎ　ｔｈｒｅｅ　ＵＣＩ　ｄａｔａｓｅｔｓ　ａｎｄ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　Ｋ－ｍｅａｎｓ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｉｎｄｉｃａｔｅ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　

ａｌｇｏｒｉｔｈｍ　ｃａｎ　ａｃｑｕｉｒｅ　ｂｅｔｔｅｒ　ｃｌｕｓｔｅｒｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ．　

Ｋｅｙ　ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；ａｄａｐｔｉｖｅ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ；ｆｉｔｎｅｓｓ　ｖａｒｉａｎｃｅ；Ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ；Ｗｅｋａ　ｐｌａｔｆｏｒｍ　

０引　言　

聚类是数据挖掘研究的关键技术之一，已广泛应用于　

图像处理、模式识别、信息检索、生物信息学等多个领　

域ｎ］。通过聚类可以将一个数据集中的成员按照某种相似　

度进行分类组织，使得同一类内的成员尽可能相似而不同　

类成员之间尽可能不同。目前，常见的聚类算法可以分为　

基于划分的、基于层次的、基于网格的、基于密度的以及　

基于模型的算法。在这些算法中，基于划分的聚类算法，　

由于其本身较低的时间复杂度，在处理大规模数据集方面　

受到越来越多研究者的关注。Ｋ－ｍｅａｎｓ算法是最具代表性　

的划分聚类算法，该算法实现比较简单，收敛速度比较快，　

但其本质上是一种局部搜索技术，对于初始聚类中心的选　

择十分敏感；同时，由于Ｋ均值是利用聚类准则函数来确　

定最终的聚类划分。通常这类算法本身不能保证收敛到聚　

类准则函数的全局最优解，有时会陷入局部极值点［　。　针对以上问题，近年来，很多研究学者受到生物群体　

行为的启发，尝试引入基于群体的智能优化方法（如遗传　

算法跚、蚁群优化算法Ⅲ、粒子群优化算法　］、和声搜索　

算法［７　和人工蜂群算法［９　等）对传统的基于准则函数的Ｋ　

均值聚类算法进行改进，来克服该算法的缺点，并取得了　

满意的效果。　

差分进化算法（ｄｉｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ，ＤＥ）是由　

Ｒ．Ｓｔｏｒｎ和Ｋ．Ｐｒｉｃｅ在１９９５年提出的一种基于种群差异的　

启发式随机搜索技术，最初用于解决切比雪夫多项式问题。　

作为一种基于智能理论的优化方法，ＤＥ在解决复杂连续优　

化问题显示出比ＧＡ、ＰＳＯ等更好的效果。该算法受控系　

数少，原理简单，易于理解和实现，有较好的全局搜索　

能力　。　

针对Ｋ均值算法的上述缺陷，充分利用差分进化算法　

全局搜索能力强的优点，本文首先提出一种基于群体适应　

度方差的自适应差分进化算法，用于解决聚类问题，然后　

收稿日期：２０１１－０３—１８；修订日期：２０１１－０５—２０　基金项目：山东省教育厅科技计划基金项目（Ｊ０８ＬＪ５９）　作者简介：姜凯（１９８６一），男，山东胶州人，硕士研究生，研究方向为数据库系统与数据挖掘；左风朝（１９６３一）男，山东聊城人，教授，　硕士生导师，研究方向为数据库系统、数据挖掘和Ｐｅｔｒｉ网理论。Ｅ－ｍａｉｌ：ｋａｉｊｉａｎｇａｂｃ＠１６３．ｃｏｎ＇ｌ

　・５９２・　计算机３－程与设计　２０１２在　

介绍了该聚类算法在著名的开源数据挖掘工具ｗｅｋａ上实　

现的过程。最后，通过在Ｗｅｋａ平台上进行实验来验证该　

算法的聚类效果。　

ｌ基本差分进化算法　

同遗传算法、粒子群优化、人工蜂群等算法一样，差　

分进化算法也是一种基于群体的智能优化方法。差分进化　

算法具有３个主要优点，即：①算法首先在可行解空间内　

进行随机初始化种群，因此不像ｋ－ｍｅａｎｓ算法那样对于初　

始条件敏感，有利于发现全局最优解；②算法简单，且易　

于实现，收敛速度快；③控制参数相对较少ｍ］。差分进化　

算法通常采用浮点矢量编码，在连续空间中进行随机搜索。　

种群中的每个个体称为染色体，代表了解空间中的一个可　

行解，即　

Ｇ（￡）一［Ｇ，１（ｆ），Ｇ，２（ｆ），…，Ｇ，ｄ（　）］　

式中：ｄ一一解空间的维数，ｉ∈｛１，２，３，…Ｎ）一一种　

群中的第ｉ条染色体，Ｎ——种群的规模。基本差分进化算　

法的流程如下：　

步骤１种群初始化。设置算法参数，生成初始种群Ｇ　

（Ｏ）一［Ｇ１（０），Ｇ２（０），…ＧＮ（０）］。　

步骤２变异操作。与遗传算法不同，ＤＥ使用差分策　

略实现个体的变异，这是差分进化算法的重要特征。　

Ｒ．Ｓｔｏｒｎ和Ｋ．Ｐｒｉｃｅ在文献［１２］中提出了十多种差分策　

略，其中应用最成功的是ＤＥ／ｒａｎｄ／Ｉ／ｂｉｎ和ＤＥ／ｂｅｓｔ／Ｉ／　

ｂｉｎ，分别如式（１）和式（２）所示　

ｖｉ（￡＋１）一　（　）＋Ｆ＊（ＧＪ（￡）一　（￡））　（１）　

Ｖｉ（　＋１）＝Ｇ　（￡）＋Ｆ＊（Ｇｆ（￡）～（　（￡））　（２）　

式中：ｉ，ｋ，ｊ，　属于［１，Ｎ］且互不相等的随机整　

数，Ｇ　（　）一一的ｔ代群体中适应度最优的个体，Ｆ为缩　

放因子。　

步骤３交叉操作。对第ｔ代群体Ｇ（　）和变异后得　

到的中间个体Ｖ／（ｆ＋１）按式（３）进行交叉操作，得到试　

验个体　（￡＋１）　

（Ｖｉ．Ｊ（　＋１）　

Ｕ　（￡＋１）一　ｉｆ　ｒａｎｄ（ｏ，１）＜　ｏｒ　ｒａｎｄ（　）：　（３） ｌＧ，Ｊ（￡）ｏｔｈｅｒｗｉｓｅ　

式中：ｃＲ——交叉概率，ｒａｎｄ（Ｏ，１）一——Ｅｏ，１］之间　

均匀分布的随机数，ｒａｎｄ（　）一一属于［１，ｄ２的随机　

整数。　

步骤４选择操作。按照贪婪选择思想选择适应度较优　

的个体进入下一代群体　

Ｇｉ（ｔ＋１）一　ｉ　厂‘Ｍ　‘　＋　＜ｆ‘Ｇ　（４）　

Ｉ　（￡）　ｏｔｈｅｒｗｉｓｅ　

步骤５判断是否满足终止条件，置￡一￡＋１，如果ｔ　

达到最大迭代次数则算法终止，否则转向步骤２。　２基于自适应差分进化的Ｋ均值聚类算法　

（　：　）　

给定具有　个样本的集合Ｘ＝｛Ｘ１，ｘ２，　，…　｝，　

其中　是ｄ维向量，Ｋ均值聚类是将这ｎ个样本划分到ｋ　

个簇中，使得目标函数达到最小值。Ｋ均值算法通常使用　

误差平方和函数作为聚类准则函数　

—　－，（　１，　２，…　，Ｃ１，Ｃ２，…Ｃｋ）：　Ｍｉｎ｛｛Ｉ　Ｉｚ　一Ｃｊ　ｊ｛　ｌ　ｉ。ｓ１　一１，２，…ｋ）　（５）　式中：ｑ一第ｊ个聚类中心，Ｉ　Ｊ　ｘ／，　ｌ　一样本）（ｉ到聚　

类中心Ｃｊ的相似度，通常使用欧几里德距离。聚类准则函　

数值越小，聚类的效果越好，因此，聚类问题可以形式化　

为如下的优化问题　

ｍｉｎ－，（　１，ｚ２，…　，Ｃ１，ｆ２，…Ｃｋ）　（６）　２．１染色体编码及适应度函数的确定　

染色体编码是实施ＤＥ的前提。本文的差分进化算法　

采用基于聚类中心的实数编码方式，将一条染色体看成由　

ｋ个聚类中心组成的实数串，即用Ｐ一｛Ｃ　，Ｃｚ，Ｃｓ，…ｅｋ｝　

表示一条染色体的结构，Ｐ是一个长度为ｄ×ｋ的行向量，　

ｄ是解空间的维数，ｃ。表示第ｉ个聚类中心，其中ｉ∈｛１，　

２，３，…ｋ｝。　适应度函数采用式（５）的聚类准则函数，使用差分进　

化算法进行优化的目的就是要找到适应度函数的最小值。　

２．２参数自适应调整策略　

群体个体的多样性有利于发挥差分进化算法的全局搜　

索能力，在较大的范围内搜索最优解；而群体个体的集中　

或趋同则有利于ＤＥ进行局部搜索。交叉概率ＣＲ和缩放因　

子Ｆ越大，变异个体和试验个体与当前的目标个体的差异　

会越大，越有利于种群的多样性；反之，交叉概率ＣＲ和　

缩放因子Ｆ越小，变异个体和试验个体与当前的目标个体　

的差异会越小，越有利于种群的趋同和集中。因此，当种　

群趋于集中时，适时通过增大交叉概率ＣＲ和缩放因子Ｆ　

来增加群体的多样性，能够进一步挖掘差分进化算法的全　

局搜索能力。　

由于差分进化算法采用了贪婪选择策略，随着进化代　

数的增加，不可避免地会使得种群内的个体朝着适应度最　

优的方向集中，使得种群个体的多样性减少，从而导致算　

法过早收敛到局部最优值，影响的算法的全局搜索能力。　

借鉴文献Ｅ１３３中的思想，针对差分进化算法引入了一种　

基于群体适应度方差的自适应策略，对交叉概率ＣＲ和缩　

放因子Ｆ进行动态调整。　定义设种群规模为Ｎ，　为第ｉ条染色体的适应度，　

厶　为当前群体的平均适应度，群体适应度方差　为　“　

ｚ—　（　＿一　）ｚ　（７）