基于进化策略的K-means聚类算法

基于进化策略的K-means聚类算法 第3卷第3期江南大学(自然科学版) 2004年6月JournalofSouthernYangtzeUniversity(NaturalScienceEdition) VoI.3No.3 Ju2004 文章?号:1671--7147(2004)03—0245—04 基于进化策略的K—means聚类算法 阎岭,蒋静坪 (浙江大学电气工程学院,浙江杭州310027) 摘要:针对K—means聚类算法易陷入局部极小以及K值选取的问题,提出一类基 于进化策略的 可以有效地搜索最优聚类中心和聚类个数K;还提出了确定K值范围的聚类算法, 经验公式,以减 小搜索空间,提高搜索效率,并给出了理论分析.相对遗传算法而言,本方法鳊码简 单,种群较小. 对Fisher'siris数据集的仿真实验 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明,该方法得到最优解的可能性比经典算法大 得多. 关键词:进化策略;K-means聚类;全局最优 中圈分类号:TP301.6文献标识码:A K-meansClusteringBasedonEvolutionStrategy YANLing.JIANGJing—ping (CollegeofElectricalEngineering.ZhejiangUniversity.Ha~gzhou310027.China) Abstract:K— meansclusteringhastWOdisadvantages.Thefirstoneiseasytobetrappedinlocal minimum,andtheanotheroneisdifficulttodeterminethenumberofclustersK.Toaddressthe problems,thepaperproposes3newK— meansalgorithmsbasedonEvolutionStrategy.Theyown theeasiercodingschemeandthesmallerpopulationthanGeneticAlgorithm.Thesealgorith ms areappliedtoclusterFisherSirisdatasetandworkverywell,especiallywhenthepriori Knowledgeareinsufficient. Keywords:evolutionstrategy;K-meansclustering;globaloptimum K-means聚类算法简单有效,已经应用到许多 领域,包括模式识别,图像和语音数据压缩,径向基 神经网络学习算法等.但是,该算法本质上是一种 局部搜索技术,它采用所谓的爬山法(hill-climbing) 来搜寻最优解,因此必然会存在局部极小的问题. 而且,目前没有较好的方法来确定K值,这对聚类 效果会产生较大的影响. 进化计算(EC),包括遗传算法(GA),进化策略 (ES),进化规划(EP),是一种模拟自然随机优化算 法,不依赖对象的数学模型,具有全局搜索能力,已 经成功应用于多种优化问题[1].文Ez]应用遗传算 法优化聚类算法,效果较好,但是仍然需要试凑K 值;而且遗传编码的选择也是一个较难解决的问 题.如果选用常规的二进制编码,染色体的长度会 随着维数的增加或精度的提高而显着增加.如果选 用其他的编码方式,会导致算法的复杂,这无疑会 影响GA的有效性.采用ES进行聚类分析的研究 相对较少.由于ES采用实数直接编码,以及处理约 束的简单性,使得ES优化聚类算法更为简单有效. 作者提出了基于进化策略的K-means聚类算 收撬日期:2003一ll一27I修订日期;2004—03—10. 作奢筒介:阎岭(1976一).男.山东德州人.控制理论与控制工程专业博士研究生. 蒋静坪(1935一),男,浙江宁波人.教授.博士生导师.主要从】|'进化计算.智能控制与机器人控制. 246江南大学(自然科学版)第3卷 法,可以自动搜索最佳的聚类数K.进化策略可以 全局搜索,具备较强的局部极值逃逸能力;而且,对 于初始值不敏感.作者还提出了确定K取值范围的 经验公式,可以有效减小搜索空间,提高搜索效率. 1K—means聚类算法 设R是P维实数集x一(z.,z.,…,z)是任 一 有限数据集,K-means聚类算法的目标函数是 n上 J一??(1) 其中:d—IIz—c0为第个数据点到第i个聚 类中心的距离;c.,c.,…,是K个聚类中心,c? Rp,?(0,1),表示第个数据属于(一1)或不 属于(一0)第i类. 其步骤为:任意选定一组K个初始聚类中心,按欧氏距离把x一(z.,z.,…,z)分到K类中去; 重新计算每一类的均值,即聚类中心,直到中心不 再发生改变.显然,该算法无法确定K值,存在局部 极小的问题,而且与初始聚类中心的选择有极大的 相关性. 2基于进化策略的聚类算法 应用ES而不是GA主要是基于两点考虑.其 一 是ES是实数直接编码的,因此目标向量的长度 仅随着待优化变量数目的增长而线性地增长.如果 采用常规的GA二进制编码,目标向量的长度会增 加到难以忍受的程度.其二是ES处理约束问题比 较容易,可以保证该算法能够搜索更大的参数空 间.但是这并不意味着认为进化策略优于遗传算法 或者相反,正如NFL定理指出的那样,无法设计出 一 种算法,在解决所有优化问题的时候,都优于其 他算法,而只能认为该算法在此领域占有优势乳. 2.1进化策略简介 ES是一种简单高效的启发式多点随机搜索算 法,它更倾向于应用进化论中变异和选择的概念. 不断地变异和选择,使群体的适应度不断提高,最 终得到最优的个体.由于本文中待优化变量包括实 数和整数,所以采用了一种稍加变化的(,)一ES 算法[5].简述如下: (,)一ES一(I,,;m,s,盯;f,g)(2) 其中,I是由实数和整数组成的向量,代表种群 中的一个个体;和分别表示父代和子代的个数; ,,l是变异算子,即ES中的主要算子;s代表选择的方 只能从个子代中选取;盯 法,在这里下一代的父代, 是变异步长,在ES算法中,不仅仅变量变异,变异 步长盯也要进行变异;f是目标函数;g是约束条件. 目标参数和步长参数的变异公式如下: i一?exp(rl?N(0,1)+r2?Nf(0,1)), i一1,2…,Q(3) I,i—+f*N(0,1), i一1,2…,Ql(4) I,一+ko*N(0,1)j, i—Ql+1,Ql+2,…,Q(5) 其中,N(0,1)和N(0,1)是0均值, 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 差为1 的正态分布随机数;Q.是实数值目标参数的个数; Q—Q.是整数值目标参数的个数,L]是取整符号.r. 是标准差向量盯的整体步长参数,r.是盯的每个分 量盯的步长参数. 为了更好地获得全局最优解,当盯变得非常小 时,给它重新赋一个初值1,增强它跳出局部极小的 能力.同时,在每一次进化过程中,记录迄今最优的 个体,但不参加下一代的竞争. 2.2给定K值时的进化编码和适值函数的建立 为简单起见,首先考虑给定K值时的进化聚类 算法.对于聚类的参数的编码,有两种方式.在第一 种方式中,设个数据要分成K类,每个个体Ij一 (i,…,i)是一个整数串,表示一种分类结果, 其中?(1,2,…K),表示第,1个数据属于第i 类.变异产生的子代,表示新产生的分类组合.计算 每一类的均值,得到聚类中心.当达到给定的性能 指标时,算法结束.在第二种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 中,每个个体i,一 (i,,…,)是一个实数串,表示K个数据聚类 中心.变异产生的子代,表示新的聚类中心. 对于两种方案,均选用相同的适值函数: .K" ??一c0. F一半土兰———一(6)?0 c一c0. …p?^ (6)式的意义是:同一类的输入样本与聚类中心的 欧式距离越近,不同聚类中心的欧式距离越远,则 聚类结果的合理性越好.进化策略的任务是搜索适 值函数F的最小值.进化策略的流程如图1所示. 2.3未给定K值时的进化编码和适值函数的建立 在实际应用中,尤其在先验知识不足的情况 下,很难得到一个较好的K值,传统的K均值聚类 只能用试凑的方法人为地指定K值,这一点对聚类 结果的精度影响很大.因此,作者提出,在搜索聚类 中心的同时,也应该搜索K值.其编码方式为:在第 一 种聚类方案的基础上,在每个个体Ii中增加一个 分量f,即 If一{,,,…,)(7) 第3期阎岭等:基于进化策略的K—means聚类算法247 Ii是一个整数串,表示一种分类结果,其中f.=矗, 表示聚类个数;其余各个分量与未给定K值编码方 式的含义相同,只是其取值范围会根据K值的变化 而相应地改变.搜索空间为?k"个点.'=1 初始化父代个体 根mO)-(s)式进行 产生子代个体 变异. 据编码方式得到 聚类方案 计算适值函数.选取最 优和次优个体作为新的 父代.保留最优值 是否达到给定\Y / JrNl 是否达到给定\YJ,.. 的繁衍代数?l爆曩0' 圈1进化策略的流程 脚1AflowchartofevoluUonclustering 2.4提高搜索效率的经验公式 众所周知,进化算法是一种随机搜索算法,效 率较低.如果能缩小搜索空间,就能够有效地提高 搜索效率.因此提出如下经验公式: 2?K?Lj(8) 厶 (8)式的意义是,对于大多数实际问题,最少分为2 类,否则就失去了聚类的意义;最大分为L昙j类,即厶 平均最少每l类有2个数据,否则无实际意义.下面 对于(8)式的作用给出理论分析: 不失一般性,只考虑样本数,z为偶数的情况,,z 为奇数时推导过程类似. 引理若口?0且bi>0(—l,2,…,,1),则满足 ?n一一 证}= ?b'i=1 口l+口2+…+口一 bl+b2+…+b 口lI口2I bl+b2+…+b.bl+b2+…+b. … +—1——牟—(9).bl+b2+…+b… ?{?0且bf>0(=1,2,…,,1) . ? . ?...+ i=1 E一毕. 令m号,则根据(8)式给定K值范围后,搜 索空间有?k"个点.其与?k"的比值为t=2t=1 ?k"t一2一 ?k"一1'一1 ?k"?[+(矗+m)"]'=1t=1 根据引理和(9)式得到 ?+(矗+)"]'一1 ? ?? (9) 皇==:|]...:土兰!.f101 k"+(2矗)"l+2"8(1+2")… (10)式表明,利用(8)式,搜索空间会显着减小,尤 其是当,z较大的时候.例如,设数据样本数为2O,代 入(1O)式可得缩小范围后搜索空间的点数小于原 当,l更大时,这个比例会更 来的0.0052.显然, 小.因此,(8)式可以有效地提高搜索效率.实际上 (8)式估计仍然过于保守,尤其对于,z较大的情况, 该范围可以进一步缩小,以减小搜索空间,提高算 法收敛的速度.当然,(8)式只是根据众多实际情况 归纳出的一个经验公式,理论上存在不满足(8)式 的可能.因此作者建议,进行运算时,首先应用(8) 式确定K值的范围,然后搜索最优个体;如果无法 收敛,则去掉(8)式,K值的范围确定为l,,z,重新 搜索最优个体. 2.5仿真实例及分析 1920年前后,植物学家收集了3种虹膜(鸢尾 属植物),每种5O个,共计150个样本的数据,包括 萼片长度,宽度和花瓣的长度,即着名的Fishers iris数据集.这些数据的分类结果是已知的,有助于 各种方法之间进行比较. 为了便于比较,分别采用传统的K均值聚类和 上述3种基于进化策略的聚类方法,对Fisher'siris 一 ? ? 一 ?? 248江南大学(自然科学版)第3卷 数据集各做了1O次仿真,仿真结果见表1.其中采远远小于一般遗传算法的种群规 模. 用进化策略的地方,父代个数为2,子代个数为14, 表1仿真结果 Tab.1SimuIntionresult 进化策略可以搜索出全局最 从表1可以看出, 优解,结果比较稳定.而传统的聚类方法则有两次 落人局部极小.但是进化策略所需要的进化代数较 多,其中,在给定K值的情况下,分别是传统聚类方 法的迭代次数的17.82和25.17倍.在未给定K值 的情况下,第3种方法可以自动搜索出最佳的K_-- 3,进化代数是传统方法迭代次数的221.78倍.但 是为了得到一个可靠的结果,在实时性要求不强的 情况下,该方法还是具有较大的优越性. 3结语 本文通过简述了K—means聚类的不足,提出了 参考文献: 两种给定K值时的基于进化策略的聚类算法,较好 地解决了局部极小的问题;针对K值选取的问题, 提出了可同时寻优K值的基于进化策略的聚类算 法,可搜索到最优K值,使得类内距最小,类外距最 大.并且给出确定K取值范围的经验公式,可有效 减小搜索空间,提高搜索效率.相对于遗传算法,本 法也具有编码简单,种群小的特点.通过对Fishers iris数据集的仿真实验,表明该算法是有效的.但是 该方法也存在一些不足,所需要的进化代数较多, 只适用于对实时性要求不高的场合. [1]BACKT.Paralleloptimizationofevolutionalgorithms[R].ParallelProblemSolvingfro mNature-ppSNm.Jerusalem. 1994.' [2]刘健庄,谢维信,黄建军.等.聚类分析的遗传算法方法D].电子.1995.23(11):81—83. [3]李敏强.寇纪淞.林丹.等.遗传算法的基本理论与应用[M].北京:科学出版社,2002. [4]WOLPERTDH.MACREADYWG.Nofreelunchtheoremsforoptimization[J].IEEET~ rtion蚰Evolutionm'y (~mputation?1997.1(1):67—82. [5]JINYAOCHU.KnowledgeinEvolutionaryLearningSystems[M].Aachen:ShakerVerla g.2001. (责任编辑:秦和平,彭守敏)