一种基于遗传算法的聚类集成方法

基于遗传算法的聚类算法研究随着数据量不断增长，聚类这种数据挖掘技术也越来越受到人们的关注。

聚类是将相似的样本划分到同一簇，不相似的样本划分到不同簇的过程。

聚类算法是实现这一过程的数学模型。

目前，聚类算法有很多种，其中基于遗传算法的聚类算法是较为先进的一种。

一、遗传算法基础遗传算法是模拟自然界生物进化过程计算最优解的一种计算机算法。

在遗传算法中，每个解都有一定的适应值（也称为适应性），适应性高的解在演化中具有更高的选择概率。

按照类比，适应度就相当于生物进化中适应环境的能力。

新一代解的产生通过变异、交叉和选择等操作完成，进而实现求解过程。

二、遗传算法聚类算法遗传算法聚类算法就是将遗传算法与聚类算法结合起来。

由于传统聚类算法存在着诸如局部极小值、初始化对最终结果影响大等缺点，导致其在某些情况下精度和效率都无法满足需求。

而遗传算法的快速收敛速度、全局优化能力等特点，使其在一定程度上弥补了传统聚类算法的不足。

因此，基于遗传算法的聚类算法在聚类领域备受瞩目。

在遗传算法聚类算法中，样本在选择过程中通过适应性来体现其在聚类中的相似度。

距离（distance）是样本之间的相似度度量标准，通常采用欧氏距离；适应度（fitness）是样本在进化中的重要性度量标准，适应度高的被优先选择。

基于遗传算法的聚类算法通常包括以下步骤：1.随机初始化一组种群，每个个体代表一个聚类簇。

2.计算每个聚类簇的适应度值，并按照适应度值选择一定数量的优秀个体参与下一代群体的生成。

3.使用遗传算法的交叉、变异机制对优秀个体进行操作，生成下一代群体。

4.计算新群体的适应度值并筛选出优秀个体，参与下一代群体的生成。

5.重复第3、4步，直到满足结束条件（如达到最大迭代次数）。

6.输出聚类结果。

三、基于遗传算法的聚类算法优缺点基于遗传算法的聚类算法具有以下优点：1.全局搜索能力强：基于遗传算法的聚类算法可以对搜索空间进行全面的探索，在全局范围内寻找最优解。

1999年10月系统工程理论与实践第10期　基于遗传算法的动态聚类方法α戴晓晖,李敏强,寇纪淞(天津大学系统工程研究所,天津300072)摘要:　针对常规动态聚类方法对初始聚类中心的敏感性以及聚类结果与样本输入次序有关等问题,本文另辟蹊径,提出了一种基于GA的动态聚类方法,并将它应用到数据库的数据分析中.计算结果表明,该方法是一个具有全局最优解的动态聚类方法,其结果明显好于K2均值聚类算法.关键词:　遗传算法;动态聚类;全局优化;数据分析A D ynam ic C lustering M ethod Based on Genetic A lgo rithm sDA I X iao2hu i,L IM in2qiang,KOU J i2song(In stitu te of System s Engineering,T ian jin U n iversity,T ian jin300072) Abstract:　To so lve the p rob lem of sen sitivity w ith the o riginal clu stering cen ter andclu stering resu lts depended on the o rder of the inpu t examp le in common dynam icclu stering algo rithm,a new dynam ic clu stering m ethod based on genetic algo rithm s isp resen ted in th is paper and is app lied to data analysis in pu ting resu ltsindicate that the m ethod is a dynam ic clu stering algo rithm w ith global op ti m izati on andis superi o r to K2m ean s algo rithm.Keywords:　genetic algo rithm s;dynam ic clu stering;global op ti m izati on;data analysis1　引言聚类分析就是通过无监督训练将样本按相似性分类,把相似性大的样本归为一类,占据特征空间的一个局部区域,而每个局部区域的聚合中心又起着相应类型的代表的作用.聚类分析一方面可以作为一种有效的信息压缩与提取手段,另一方面又往往是其它模式识别的基础.在各类聚类分析中,动态聚类方法是较普遍采用的方法.现有的各种动态聚类方法都是先根据一定的经验准则选取某些聚类参数,诸如希望的聚类数、最小标准差、初始聚类中心、聚类中心间的最小距离等,然后根据距离最近的原则对各样本进行依次训练调节,直至目标函数即各样本到相应聚类中心距离平方和收敛到最小为止.这些算法的计算结果与这些参数的设置是否得当至关重要,因此在设置这些参数之前往往需要对样本数据进行必要的分析研究.这在数据量较大,特别是在高维情况下,要得到合理的参数尤为困难,只能通过多次实验[1].由于在聚类算法中自变量(待聚类点的坐标值)与目标函数都是离散量,存在着许多局部极值,而通常的方法又没有相应接受劣解的机制,因此初始聚类中心和样本输入次序对最终结果有着很大的影响.经常采用的对策是用若干不同的初始中心分别进行聚类,然后选择最满意的一个作为最终聚类结果.这种方法应用在大型数据库的数据分析中,不仅工作量巨大,而且不能保证聚类结果的最优性.遗传算法(Genetic A lgo rithm—GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,它是由美国M ich igan大学的Ho lland教授于1975年首次提出的[2],这是一种新的全局优化搜索算法,其简单通用,鲁棒性强,适于并行处理,已经广泛地应用在计算机科学[3]、优化调度[4]、运输问题[5]、组合优α收稿日期:1997210226资助项目:国家自然科学基金资助项目(79400013,69574022)化[6]等领域.针对动态聚类算法的离散性及局部极值特征,本文运用GA 来解决动态聚类的全局优化问题.2　GA 动态聚类方法2.1　聚类分析的数学模型设目标函数 J =m in6Pr =16m ri =1‖X(r )i-C r ‖2其中:聚类中心C r =1mr 6m ri =1X(r )i　(i =1,2,…,m r ,;r =1,2,…,P )6Pr =1m r =Nm r 为属于r 类的样本(记录)个数;X (r )i表示样本X i 属于第r 类;N 为样本(记录)数;P 为聚类中心数(2ΦP ΦN -1).2.2　染色体的构造通过对模型的分析,我们采用自然数编码,具体如下:用X {=(S 1,S 2,…,S N )表示GA 的染色体结构,X {为1×N 维行向量,S l 为第l 位的基因,则染色体要求如下:S l ∈{1,2,…,P },　l =1,2,…,N2.3　适应度的选择选择f =C m ax -m in 6Pr =16m ri =1‖X(r )i-C r ‖2作为适应度函数,其中,C m ax =6N i =16Nj =1‖X i -X j ‖2,把求最小极值问题转化为求最大极值问题,这样在选择规则中就可以使用赌轮策略.2.4　遗传算子遗传算子包括选择、交叉、变异和进化逆转等过程.1)选择规则按照2.3选定的适应度函数,使用赌轮策略进行选择,并且保留上一代M 个较优的个体做为下一代的样本,来保证算法的收敛.2)交叉规则交叉按照OX 规则进行[3].3)变异规则由于在选择机制中采用了保留最佳样本方式,以及引入了“进化逆转”操作技术,为保持群体内个体的多样性,我们采用连续多次对换的变异技术,使可行解有较大顺序排列上的变化,以抑制“进化逆转”的同化作用.若发生变异,则用随机方法产生交换次数K ,对所需变异操作的染色体进行K 次对换(对换的两码位也是随机产生的).4)“进化逆转”规则引进“进化逆转”操作的主要目的是改善遗传算法的局部搜索能力.在遗传算法中,“逆转”是一种常见的“变异”技术.我们使用的“进化逆转”是一种单方向的(朝着改进的方向)和连续多次的“逆转”操作,即对于给定的串,若“逆转”使串(可行解)的适应度提高,则执行逆转操作,如此反复,直至不存在这样的逆转操作为止.这一操作实际上使给定的串改良到它的局部极点,这种局部爬山能力与基本遗传算法的全局搜索能力相结合在实验中显示了良好的效果.2.5　基于GA 的动态聚类方法的具体迭代步骤1)输入P ,pop size ,P c ,P m 及gen 2m ax ;2)置G =0(G 为代数);901第10期基于遗传算法的动态聚类方法3)生成初始群体;4)评价各初始母体的适应度;5)选择母体,进行交叉、变异、进化逆转等操作,生成新一代母体群;6)计算新的聚类中心和累积类内距离平方和;7)评价新一代母体群的适应度;8)若迭代次数已达最大迭代次数,则输出结果;否则G=G+1转入第5)步.输入的控制参数:聚类中心数P、群体规模pop size、交叉概率P c、变异概率P m和最大迭代次数gen2 m ax.3　数据聚类研究为了验证上述算法的有效性,我们以某一数据库中的记录(记录值为:(0,1)、(1,0)、(1,1)、(2,2)、(2, 3)、(3,2)、(5,6)、(6,5)、(6,6)、(7,7)、(7,8)、(8,7)等12个记录)为例,采用K2均值聚类算法(以前4个样本为初始聚类中心)和遗传算法分别进行计算,计算结果如表1:表1　K2均值聚类算法基于GA的动态聚类算法样本样本类别样本类别样本类别样本类别117411732284218332943193431044210453114521146312462124目标函数:12.833目标函数:5.333 遗传算法的运行设置参数如下:P=4,pop size=30,P c=0.7,P m=0.001和gen2m ax=1000.运行50次,平均收敛代数为156代.由仿真结果表明,常规聚类方法因不能有效地处理局部极值问题,因此当初始聚类中心在整个样本空间不平衡时,它很难将这种不平衡纠正过来,从而导致聚类结果对初始聚类中心的选取有着很大的敏感性;而基于GA的动态聚类方法因具有很好的处理局部极值能力,因此对初始聚类中心的选取以及样本的输入次序没有任何要求.另一方面,从它们各自的收敛速度上来看,基于GA的动态聚类方法的收敛速度较慢,但是这显然比用常规方法对不同初始聚类中心进行聚类来获取全局最优解要有效的多.4　结论本文提出了一种基于GA的动态聚类方法,它可以得到全局最优解,从而很好地解决了其它动态聚类方法中普遍存在的初始聚类中心敏感性以及聚类结果与样本的输入次序有关等问题,为聚类分析提供了一个新的思路.计算结果表明,该方法不仅可以用于分析大型数据库中的数据,而且可以辅助指导决策.对于如何提高GA的收敛效率等问题尚需进一步研究.参考文献:[1]　黄振华,吴成一.模式识别原理.杭州:浙江大学出版社.1989.[2]　Ho lland T H.A dap tati on in natu ral and artificial system.A nn A rbo r:T he U n iversity of M ich iganP ress,1975.(下转第116页)A1　A2　…　A mZ T=Z11Z21…Z m1Z12Z22…Z m2Z1k Z2k…Z m kS1S2S k 因S i为效益型指标,对每一个属性S i(i=1,2,…,k),A j(j=1,2,…,m)可按其大小排序:　1　2　…　mA11A12 (1)A21A22 (2)A k1A k2…A km S1 S2…S k其中S i:A i1,A i2,…,A i m,A ij∈A(i=1,2,…,k;j=1,2,…,m)是按第i个属性对m个方案的排序.如果把S i看成E i(i=1,2,…,k),即k个专家,并且再假设E i有序(可按S i(i=1,2,…,k)的重要性决定),这样就转化为前文中的排序矩阵EA,于是可以利用n维足码选择定位法解决多目标决策问题.6　结束语本文给出了一种专家数据信息后处理的群排序方法[3],具有简洁、易于操作等特点.它避开了确定专家权重的困难,采用了较为容易的确定专家顺序的方法,具有客观实用性.对于专家和方案均较多的情形,可以利用计算机进行排序.参考文献:[1]　陈明琴,何湘藩.二维足码选择定位法.系统工程理论与实践,1997,17(2):83～87.[2]　王应明,傅国伟.关于专家最优综合评价模型的改进和完善.系统工程,1992,(6):51～57.[3]　张四维,刘进生.专家数据信息后处理的群排序方法.系统工程理论与实践,1995,15(2):46～50.[4]　H e X iangfan,Chen M ingqin.A new m ethod of group o rdering:info rm ati on flow ed m ethod.M CDM:T heo ry and A pp licati on,SC I2T ECH Info rm ati on Services,A ugu st,1995:203～205.(上接第110页)[3]　Go ldberg D E.Genetic algo rithm s in search,op ti m izati on and m ach ine learn ing.M A:A ddisonW elsey,1989.[4]　马光文,王黎,W alters G A.水电站优化调度的FP遗传算法.系统工程理论与实践.1996,16(11):77～81.[5]　V ignaux G A,M ichalew icz Z.A genetic algo rithm fo r the linear tran spo rtati on p rob lem,IEEET ran s Syst.M an Cybern,1994,21(2)[6]　Karo ly F pal.Genetic algo rithm s fo r the traveling sales m an p rob lem based on a heu ristic cro ssoveroperati on.B i o l Cybern,1993,69:539～546.[7]　Tou J T.D YNOC——a dynam ic op ti m al clu stering seek ing techn ique,In pu ter Info rm ati onScience,1979,8(6):43～50.[8]　方开泰,潘恩沛.聚类分析.北京:地质出版社.1982.。

一种新的基于遗传算法的动态聚类算法
陆林花
【期刊名称】《计算机仿真》
【年(卷),期】2009(0)7
【摘要】为了在聚类数不明确的情况下实现聚类分析,提出一种新的结合最近邻聚类和遗传算法的动态聚类算法.新算法包括两个阶段:第一阶段用最近邻聚类算法根据最近邻方法把最相似的实例分到同一个簇中并根据一些相似性或相异性度量过滤掉噪声数据从而得到初始聚类集,第二阶段是遗传优化阶段,利用动态聚类评估函数,动态地合并初始聚类集,从而获得接近最优的解.最后对算法进行了实验仿真,实验结果表明方法在事先不知道聚类数的情况下能够有效地进行聚类.
【总页数】5页(P122-125,158)
【作者】陆林花
【作者单位】福州大学阳光学院,福建福州,350015
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.一种改进的基于遗传算法的K均值聚类算法 [J], 唐朝霞
2.一种基于遗传算法改进的蚁群聚类算法 [J], 秦福高
3.基于遗传算法的一种改进的K-均值聚类算法 [J], 张春凯;王丽君
4.一种基于改进遗传算法的 WSN 负载均衡聚类算法 [J], 杨建;刘述木;黎远松
5.一种基于遗传算法的K-means聚类算法 [J], 王娟
因版权原因，仅展示原文概要，查看原文内容请购买。

一种基于遗传算法的K-means聚类算法一种基于遗传算法的K-means聚类算法摘要：传统K-means算法对初始聚类中心的选取和样本的输入顺序非常敏感，容易陷入局部最优。

针对上述问题，提出了一种基于遗传算法的K-means聚类算法GKA，将K-means算法的局部寻优能力与遗传算法的全局寻优能力相结合，通过多次选择、交叉、变异的遗传操作，最终得到最优的聚类数和初始质心集，克服了传统K-means 算法的局部性和对初始聚类中心的敏感性。

关键词：遗传算法；K-means；聚类聚类分析是一个无监督的学习过程，是指按照事物的某些属性将其聚集成类，使得簇间相似性尽量小，簇内相似性尽量大，实现对数据的分类[1]。

聚类分析是数据挖掘技术的重要组成部分，它既可以作为独立的数据挖掘工具来获取数据库中数据的分布情况，也可以作为其他数据挖掘算法的预处理步骤。

聚类分析已成为数据挖掘主要的研究领域，目前已被广泛应用于模式识别、图像处理、数据分析和客户关系管理等领域中。

K-means算法是聚类分析中一种基本的划分方法，因其算法简单、理论可靠、收敛速度快、能有效处理较大数据而被广泛应用，但传统的K-means算法对初始聚类中心敏感，容易受初始选定的聚类中心的影响而过早地收敛于局部最优解，因此亟需一种能克服上述缺点的全局优化算法。

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法。

在进化过程中进行的遗传操作包括编码、选择、交叉、变异和适者生存选择。

它以适应度函数为依据，通过对种群个体不断进行遗传操作实现种群个体一代代地优化并逐渐逼近最优解。

鉴于遗传算法的全局优化性，本文针对应用最为广泛的K-means方法的缺点，提出了一种基于遗传算法的K-means聚类算法GKA(Genetic K-means Algorithm)，以克服传统K-means算法的局部性和对初始聚类中心的敏感性。

用遗传算法求解聚类问题，首先要解决三个问题：(1)如何将聚类问题的解编码到个体中；(2)如何构造适应度函数来度量每个个体对聚类问题的适应程度，即如果某个个体的编码代表良好的聚类结果，则其适应度就高；反之，其适应度就低。

一种基于遗传算法的K-means聚类算法王娟【期刊名称】《微型机与应用》【年(卷),期】2011(030)020【摘要】传统K—means算法对初始聚类中心的选取和样本的输入顺序非常敏感，容易陷入局部最优。

针对上述问题，提出了一种基于遗传算法的K—means聚类算法GKA，将K—means算法的局部寻优能力与遗传算法的全局寻优能力相结合，通过多次选择、交叉、变异的遗传操作，最终得到最优的聚类数和初始质心集，克服了传统K—means算法的局部性和对初始聚类中心的敏感性。

%Traditional K-means algorithm is sensitive to selecting initial clustering centers and input sequence, it is easy to get into the local best. In view of the above-mentioned problems, this paper proposes a K-means clustering algorithm （GKA） based on genetic algorithm. It combines local optimization of K-means algorithm with global optimization of genetic algorithm. By multiple selection, crossover and mutation, it can get optimal clustering number and initial centroid collection. So it overcomes the locality of traditional K-means algorithm and sensitivity of initial clustering centers.【总页数】4页(P71-73,76)【作者】王娟【作者单位】贵州民族学院计算机与信息工程学院,贵州贵阳550025【正文语种】中文【中图分类】TP18【相关文献】1.基于改进自适应遗传算法的K-means聚类算法研究 [J], 佟昕2.基于混合遗传算法的K-Means最优聚类算法 [J], 吕强; 俞金寿3.一种基于密度和距离的K-means聚类算法 [J], 罗军锋;洪丹丹4.一种基于K-Means均值聚类算法的大地测量数据粗差探测方法 [J], 杨玉;吴云龙;单维锋;石江浩5.基于Hadoop平台的一种改进K-means文本聚类算法 [J], 潘俊辉;王辉;张强;王浩畅因版权原因，仅展示原文概要，查看原文内容请购买。

《基于遗传—蚁群融合算法的聚类算法研究》篇一基于遗传-蚁群融合算法的聚类算法研究一、引言聚类算法作为数据挖掘和机器学习领域的重要技术，广泛应用于图像处理、模式识别、生物信息学等多个领域。

然而，传统的聚类算法在处理大规模、高维度的数据时，往往存在计算复杂度高、聚类效果不佳等问题。

为了解决这些问题，本文提出了一种基于遗传-蚁群融合算法的聚类算法，通过融合遗传算法和蚁群算法的优点，提高聚类的准确性和效率。

二、相关技术背景1. 遗传算法：遗传算法是一种模拟自然进化过程的优化算法，通过模拟生物进化过程中的选择、交叉、变异等操作，实现对问题空间的搜索和优化。

2. 蚁群算法：蚁群算法是一种模拟蚂蚁觅食过程中信息素传递的优化算法，通过模拟蚂蚁的信息素传递和协作行为，实现对问题的求解。

3. 聚类算法：聚类算法是一种无监督学习方法，将数据划分为若干个簇，使得同一簇内的数据相似度高，不同簇间的数据相似度低。

三、基于遗传-蚁群融合算法的聚类算法1. 算法思想本算法融合了遗传算法和蚁群算法的优点，通过遗传算法的全局搜索能力和蚁群算法的局部优化能力，实现对聚类问题的求解。

具体思想如下：（1）初始化：随机生成一定数量的聚类中心，作为初始解集。

（2）编码与解码：将聚类中心编码为染色体，通过遗传操作生成新的染色体，解码得到新的聚类中心。

（3）适应度评价：根据聚类效果评价函数，计算每个染色体的适应度。

（4）选择、交叉、变异：根据适应度选择优秀的染色体进行交叉、变异操作，生成新的解集。

（5）蚁群局部优化：在遗传算法的基础上，利用蚁群算法对聚类结果进行局部优化，提高聚类的准确性。

2. 具体实现步骤（1）初始化聚类中心，形成初始解集。

（2）将聚类中心编码为染色体，进行遗传操作，生成新的染色体。

（3）解码得到新的聚类中心，计算每个染色体的适应度。

（4）根据适应度选择优秀的染色体进行交叉、变异操作，生成新的解集。

（5）利用蚁群算法对聚类结果进行局部优化，得到最终的聚类结果。

基于遗传算法的高维数据聚类技术研究一、引言随着科技的飞速发展，数据的积累也逐渐变得海量起来。

而大数据中的高维数据因其数据量大、耗时长、难以解释等优势，已经成为了各个领域中的一个热点问题。

在这个背景下，高维数据聚类技术成为了研究的重点之一。

然而，由于维数的增加，传统的聚类方法在效率和准确性上面临着挑战。

为了克服这些问题，研究人员开始尝试利用遗传算法来解决高维数据聚类问题。

二、高维数据聚类技术高维数据聚类技术是数据挖掘领域中的一个重要分支，其目的是将给定的数据集划分为若干个具有相似特征的簇。

聚类算法的效果直接影响着后续的数据处理结果质量，因此如何选择合适的聚类算法成为了研究人员探讨的问题。

传统的聚类算法，如K均值、层次聚类等，其基本思想是将数据集中的对象划分为若干个组，使得组内之间的距离较小，而组间之间的距离较大。

然而，这些方法在处理高维数据时，由于“维数灾难”问题的存在，其效率和准确性急剧下降。

因此，研究人员开始探索利用遗传算法来解决高维数据聚类问题。

三、遗传算法遗传算法是一种模拟自然选择和遗传机制的计算机算法。

它模拟了生物进化过程中的“适者生存，不适者淘汰”的规则，可以用于解决复杂的优化问题。

遗传算法通常包括以下步骤：1.初始化种群2.选择操作3.交叉操作4.变异操作5.重复2-4步骤，直到达到预设终止条件四、基于遗传算法的高维数据聚类技术在基于遗传算法的高维数据聚类技术中，每个染色体代表一个簇划分方案，其中每个基因代表数据点在该簇中的类别。

遗传算法的目的是通过基因的组合和变异，找到一组最优的簇划分方案。

通过遗传算法对高维数据进行聚类，可以实现以下优点：1. 不需要事先指定聚类个数传统的聚类算法需要事先指定聚类个数，但是这个数字很难确定，也可能导致聚类结果不够准确。

而遗传算法不需要指定聚类个数，可以自动选择合适的聚类个数。

2. 可以降低“维数灾难”遗传算法通过初始种群、交叉、变异等操作，可以优化聚类结果，降低“维数灾难”的影响。