当前位置:文档之家› Weka平台上解决聚类的改进差分进化算法

Weka平台上解决聚类的改进差分进化算法

2012年2月 第33卷第2期 计算机工程与设计 

COMPUTER ENGINEERING AND DESIGN Feb.2012 Vo1.33 NO.2 

Weka平台上解决聚类的改进差分进化算法 

姜凯,左风朝 

(聊城大学计算机学院,山东聊城252059) 

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

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

充分利用在Weka工具中的类和接口,并将新提出的算法嵌入到平台中。在Weka平台上将该算法与K均值算法在3个 

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

关键词:聚类;自适应差分进化算法;适应度方差;K均值;Weka平台 

中图法分类号:TP311 文献标识号:A 文章编号:1000—7024(2012)02—0591—04 

Advanced differential evolution algorithm for clustering on Weka 

JIANG Kai,ZUO Feng-chao 

(School of Computer Science,Liaocheng University,Liaocheng 252059,China) 

Abstract:After analyzing the drawbacks of the K-means algorithm,a novel differential evolution algorithm for solving clustering 

problem is proposed to optimize the criterion function for clustering.In order to further enhance the capability of global search, 

a self-adaptive strategy using fitness variance of the population is introduced to adjust scaling factor and crossover probability. 

The proposed approach is implemented On the Weka platform where its classes and interfaces are fully utilized.At last,the pro— 

posed algorithm is tested on three UCI datasets and compared with K-means.The simulation results indicate that the proposed 

algorithm can acquire better clustering performance. 

Key words:clustering;adaptive differential evolution;fitness variance;K-means algorithm;Weka platform 

0引 言 

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

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

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

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

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

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

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

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

受到越来越多研究者的关注。K-means算法是最具代表性 

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

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

择十分敏感;同时,由于K均值是利用聚类准则函数来确 

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

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

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

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

算法[7 和人工蜂群算法[9 等)对传统的基于准则函数的K 

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

满意的效果。 

差分进化算法(diferential evolution,DE)是由 

R.Storn和K.Price在1995年提出的一种基于种群差异的 

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

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

化问题显示出比GA、PSO等更好的效果。该算法受控系 

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

能力 。 

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

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

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

收稿日期:2011-03—18;修订日期:2011-05—20 基金项目:山东省教育厅科技计划基金项目(J08LJ59) 作者简介:姜凯(1986一),男,山东胶州人,硕士研究生,研究方向为数据库系统与数据挖掘;左风朝(1963一)男,山东聊城人,教授, 硕士生导师,研究方向为数据库系统、数据挖掘和Petri网理论。E-mail:kaijiangabc@163.con'l

 ・592・ 计算机3-程与设计 2012在 

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

现的过程。最后,通过在Weka平台上进行实验来验证该 

算法的聚类效果。 

l基本差分进化算法 

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

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

算法具有3个主要优点,即:①算法首先在可行解空间内 

进行随机初始化种群,因此不像k-means算法那样对于初 

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

于实现,收敛速度快;③控制参数相对较少m]。差分进化 

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

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

行解,即 

G(£)一[G,1(f),G,2(f),…,G,d( )] 

式中:d一一解空间的维数,i∈{1,2,3,…N)一一种 

群中的第i条染色体,N——种群的规模。基本差分进化算 

法的流程如下: 

步骤1种群初始化。设置算法参数,生成初始种群G 

(O)一[G1(0),G2(0),…GN(0)]。 

步骤2变异操作。与遗传算法不同,DE使用差分策 

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

R.Storn和K.Price在文献[12]中提出了十多种差分策 

略,其中应用最成功的是DE/rand/I/bin和DE/best/I/ 

bin,分别如式(1)和式(2)所示 

vi(£+1)一 ( )+F*(GJ(£)一 (£)) (1) 

Vi( +1)=G (£)+F*(Gf(£)~( (£)) (2) 

式中:i,k,j, 属于[1,N]且互不相等的随机整 

数,G ( )一一的t代群体中适应度最优的个体,F为缩 

放因子。 

步骤3交叉操作。对第t代群体G( )和变异后得 

到的中间个体V/(f+1)按式(3)进行交叉操作,得到试 

验个体 (£+1) 

(Vi.J( +1) 

U (£+1)一 if rand(o,1)< or rand( ): (3) lG,J(£)otherwise 

式中:cR——交叉概率,rand(O,1)一——Eo,1]之间 

均匀分布的随机数,rand( )一一属于[1,d2的随机 

整数。 

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

的个体进入下一代群体 

Gi(t+1)一 i 厂‘M ‘ + <f‘G (4) 

I (£) otherwise 

步骤5判断是否满足终止条件,置£一£+1,如果t 

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

( : ) 

给定具有 个样本的集合X={X1,x2, ,… }, 

其中 是d维向量,K均值聚类是将这n个样本划分到k 

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

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

— -,( 1, 2,… ,C1,C2,…Ck): Min{{I Iz 一Cj j{ l i。s1 一1,2,…k) (5) 式中:q一第j个聚类中心,I J x/, l 一样本)(i到聚 

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

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

为如下的优化问题 

min-,( 1,z2,… ,C1,f2,…Ck) (6) 2.1染色体编码及适应度函数的确定 

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

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

k个聚类中心组成的实数串,即用P一{C ,Cz,Cs,…ek} 

表示一条染色体的结构,P是一个长度为d×k的行向量, 

d是解空间的维数,c。表示第i个聚类中心,其中i∈{1, 

2,3,…k}。 适应度函数采用式(5)的聚类准则函数,使用差分进 

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

2.2参数自适应调整策略 

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

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

或趋同则有利于DE进行局部搜索。交叉概率CR和缩放因 

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

会越大,越有利于种群的多样性;反之,交叉概率CR和 

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

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

群趋于集中时,适时通过增大交叉概率CR和缩放因子F 

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

局搜索能力。 

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

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

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

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

借鉴文献E133中的思想,针对差分进化算法引入了一种 

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

放因子F进行动态调整。 定义设种群规模为N, 为第i条染色体的适应度, 

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

z— ( _一 )z (7)

相关主题