遗传聚类（精选7篇）
遗传聚类 篇1
模糊聚类以Zadeh提出的模糊集理论[1]为基础,描述了样本在性态和类属方面存在着不确定性,能够客观地反映现实世界,已经成为聚类分析研究的热点。在众多基于目标函数的模糊聚类算法中,模糊C-均值聚类算法[2]理论最完善、应用最为广泛。模糊C-均值聚类算法采用一种迭代的爬山技术来寻找最优解的局部搜索算法,它对初始化值非常敏感而容易陷入局部极小值,对于这一缺点学者们提出了一些改进方法[3,4]。
遗传算法[5]是一种模拟自然进化过程搜索最优解的全局优化方法,是一种与求解问题无关的算法模式,能够有效解决模糊C-均值聚类算法对初始值敏感的问题。文献[6]提出用模糊C-均值聚类算法代替遗传算法的交叉操作,从而实现遗传模糊聚类算法,但由于每次都要运行模糊C-均值聚类算法,且没有对遗传算法做其他改变,所以运行时间和聚类效果不佳。文献[7]也是在遗传算法中引入了模糊C-均值聚类算法,在遗传操作之后,用模糊C-均值聚类算法局部寻优,并使用最短距离法进行整体交叉的操作,提高了算法的全局搜索能力,聚类效果进步不少,但是难以改变时间消耗的问题。本文在这些研究的基础上对遗传算法进行了改进,使得聚类在运行效率和聚类质量上都有一定的提高。
1 遗传模糊聚类
模糊C-均值聚类算法因对初始值非常敏感而容易陷入局部最优,在迭代过程中由于保证不了向着全局最优的方向搜索,所以也就不能保证收敛到全局最优。算法是否能够收敛到全局最优值,这在一定程度上依赖初始值的选择,如此重要的选择让那些学者们在初始化数据时总是想方设法地使用一些更好的办法。
遗传算法是一种最受关注的全局优化算法之一,通过模拟生物进化和遗传过程中个体的选择、交叉和变异机理,来完成搜索问题最优解的过程。它以群体搜索技术进行操作,用遗传算子交换个体间的信息,经过对种群中的个体适应度的评价,使得群体中的个体一代一代地不断进化,并渐渐逼近最优解。它以决策变量的编码作为运算对象,以目标函数值作为搜索信息,从多个点同时搜索,并且使用概率搜索技术,使得该算法有很强的寻优能力,即使是在很复杂的解空间中,也很快就能找到良好的解。遗传算法正是具有这些优点,才能够有效解决模糊C-均值聚类算法易陷入局部极小值的问题。模糊C-均值聚类算法是局部寻优,遗传算法是全局寻优,两者结合起来使用,可以同时体现两个算法的寻优能力,提高了收敛速度,能更好地解决聚类问题。
2 遗传模糊聚类改进策略
目前对遗传算法应用到聚类中已经有许多研究[6,7,8,9],但遗传算法仍然存在局部搜索能力差、容易早熟、效率不高[10]等缺陷,针对这些问题提出一种基于改进遗传算法的模糊C-均值聚类算法,该算法使用遗传算法对初始聚类中心进行优化,而后执行模糊C-均值聚类算法。
2.1 主、副种群隔离机制
传统的遗传算法将个体进化过程放在一个种群内反复进行,这样做使得种群内基因交流畅通,个体很难向着各自的方向发展,从而导致种群多样性的不足。另一个原因是采用比例选择算子有缺陷,当种群中有个别个体的适应度值远远大于种群的平均适应度值时,这些个体将迅速扩张,从而使种群中个体相似度降低,破坏种群多样性。遗传算法全局搜索能力不强的主要原因是种群多样性不足,而小生境技术的引入可以解决这一问题。
种群依据离最优种子的距离动态地分成主种群和副种群两部分,对主、副种群隔离进化,提高算法效率,缩短遗传算法的运行时间。通过设定一个自适应的距离,该距离能够隔离出一个随当前最优种子变化的小生境。针对小生境外部,用较大变异概率的方法实现种群的多样性,而对于小生境内部,主要选择以交叉为主的方法来稳定选择压力,如此划分的目的是使种群的多样性和选择压力达到一种平衡状态[11]。
2.2 实数编码机制
遗传算法主要通过遗传操作对种群中的个体进行重新组成,通过不断优化种群中的个体,渐渐逼近问题的最优解,直至最后达到搜索到最优个体的目的。对于一些高维、高精度要求的优化问题,使用二进制编码将会带来计算误差、编码空间Hamming 悬崖等诸多问题[12,13],为了克服这些不足,提出了实数编码的方法。实数编码是每个个体向量被编码成一个与解向量相同长度的实数向量。遗传操作过程中,遗传空间就是问题空间,个体直接反映了问题的规律与特性。
在遗传算法编码中采用了把聚类中心作为个体的实数编码方式,这种表示方法使用决策变量的真实值来编码,达到较高精度要求,并且个体搜索空间比较大,利于全局搜索。
2.3 双精英参与机制
为了防止己经得到的最优种子不被淘汰掉,所以经常使用精英保留策略来保证算法的收敛性。除此之外,精英种子还能够引导种群向最优值搜索。然而,保留的精英种子和引导搜索的精英种子可能不是同一个种子;若发现某精英种子是已经搜索到的局部极小值时,则需要把它作为己经获得的最优值保存起来,而不能让它再引导种群搜索。因此,为了划分出精英保存策略的功能,提出了双精英种子参与机制,一个是保存起来的己经获得历史局部极小值的精英种子,一个则是作为前最优值引导搜索的精英种子。为此,第一步是采用精英保存策略保存精英种子,而下一代的交叉、变异操作需要引进当前精英个体,使其引导种群向全局最优解逼近;第二步是依照个体适应度值,采用轮盘赌选择策略把当前群体中的个体选出来,并对主、副种群进行相应策略的交叉、变异操作,以提高种群的平均适应度和增加种群的多样性。
3 算法描述
设N为种群总规模,N1为主种群的种子个数,N2为副种群的种子个数,初始化时N1和N2约为种群总规模N的二分之一。种群在主副种群距离界限值不断减小的情况下逐步进化,进化中主种群进化比较快,副种群进化相对比较慢,究其原因是主种群里保持比较大的选择压力,而副种群里因变异概率和交叉概率比较大选择压力比较小。
算法步骤如下:
(1)初始化参数,生成初始种群;
(2)计算各个个体适应度值;
(3)判断是否满足停止准则,满足则执行(4),否则执行(9);
(4)求出N1,N2,其中N1=INT(N×0.5) ,N2=N—N1;
(5)求出当前最优种子,并计算各种子到当前最优种子的欧氏距离;
(6)计算主副种群的距离界限值L,L为最大距离×0.5和排序后距离向量的中位数,二者中的最小值。根据L划分主副种群并计算N1、N2,设D为个体与当前最优种子的距离,ε为一个设定的极小值,则:
如果 L>ε, N1={D≤L的个体},N2={D>L的个体};
否则,N1={D>L的个体和当前最优种子},N2=空集。
(7)对主种群和副种群里的种子按各自策略分别进化;
(8)将进化后的主种群和副种群混合生成新种群,令T=T+1,T为遗传代数,返回(2);
(9)求出最优个体;
(10)执行模糊C-均值聚类算法,输出聚类结果。
4 实验仿真及应用
4.1 仿真结果
本文应用改进的遗传模糊聚类算法(简称为IGAFCM)对标准IRIS数据集进行了仿真实验,并与模糊C-均值聚类算法(FCM)、遗传模糊混合算法(HGFA)相比较,三种算法的比较结果如图1和表1。
图1中T表示进化代数,J表示目标函数值,其定义为:
图1中J-T曲线是目标函数值J跟随进化代数T的变化趋势。不难看出,随着进化的不断进行,三种算法都能达到相应的目标函数值。曲线变化表明,本文提出的改进算法在达到目标函数值的时候所用的迭代次数最少,即收敛速度要比其他两个算法快,充分体现该算法在收敛速度方面的优势。
三种算法从进化代数、误分数、误分率方面来比较。误分是指本属于某类的样本被错误地划分到其他类的样本,所有类中被错误划分的样本个数之和称为误分数。误分率定义为:
误分率
表1中数据显示,本文算法在进化次数上最少,误分数最少,误分率最低,即在聚类精度上有一定的提高,从而保证了聚类的质量。
4.2 算法应用
为了进一步验证该算法的有效性并加以利用,取一组实际数据作为测试用例,数据集来自某次学生考试成绩库,试卷包括五个大题,每题20分。实验中抽取总得分为70—80的100位考生的考试数据进行模糊聚类分析。聚类结果如图2所示。
经过大量实验得出聚类结果可有效地分为五个类别,并将聚类后的数据作均值化处理,结果发现五个类别中有一类是各题得分比较均匀,其他四类中总有某一个题目得分比较低,这就给我们提供了聚类的依据,能够充分挖掘、分析试卷数据。
显然,基于本文算法的试卷分析和传统的试卷分析都是把学生成绩作为分析对象,但传统的试卷分析只是考虑了学生的成绩排名情况,所以基于本文算法的试卷分析要比传统的试卷分析有内涵。按照传统的试卷分析方法来看,本文所列举的100位考生应属于一个类别,而基于本文算法的试卷分析将学生依据题目得分高低划分为有意义的若干类别,可以更加深刻和准确地发现这些学生对知识点的理解程度有所不同,掌握知识点的能力不尽相同,这也为以后的教学工作提供了改进的思路和方法,具有一定的现实意义。
5 结语
由于模糊C-均值聚类算法强烈依赖于参数初始化的优劣,而一个靠近最优解的初始化方法将以更少的迭代步骤收敛到全局最优解,所以采用遗传算法初始化聚类中心,并提出了改进的遗传模糊聚类。仿真实验结果体现了改进算法的优越性,并将该算法应用到试卷数据聚类分析中,深层次的挖掘出隐含的信息,有目的、针对性地指导个性化教学。虽然改进后的算法提高了聚类质量,但还遗留许多问题丞待解决,例如在处理数据的维度高、量大时收敛速度比较慢,消耗时间比较多;增加动态聚类分析方法的研究,以便处理数据动态增加的情况;复杂类型数据集聚类分析的研究,寻求新的度量方法,以便处理复杂的数据集等等。
遗传聚类 篇2
聚类分析[1]是模式识别和数据压缩领域中一种重要的非监督学习过程,其目的是将若干特征相似的特征模式划分到一个集合,每个集合的特征模式之间按照某种度量来衡量相似程度,使得同一个集合内的数据对象具有较高的相似度,而不同集合中的数据对象间的相似度尽可能小,数据对象间特性差异的大小通常是借助于某一距离空间中的距离概念来刻划的。在现有的聚类算法中,K-均值算法以其简单和高效占有重要地位[2]。但因K-均值算法在寻找聚类中心的过程中采用了启发式方法,使得该算法对初始聚类中心的选择较为敏感,易于陷入局部最优解。尤其在大矢量空间中,这种算法的性能会变得更差[3,4]。美国Holland教授于1975年提出了一种全局优化自适应概率搜索算法—遗传算法(GA)[5,6]。该算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法,具有较强的鲁棒性和全局寻优的能力,但基于遗传的K均值算法(GA-K均值算法)存在前期过早收敛而后期收敛慢的缺点[7]。本文借助免疫机制的优点[8],将免疫原理的选择操作机制引入遗传算法中,提出基于改进遗传算法的K-均值聚类算法。该算法结合K-均值算法的高效性和局部搜索能力,以及改进遗传算法的全局优化能力,达到了较好的聚类效果。
1 基于改进遗传算法的K-均值聚类算法
遗传算法在解决实际问题时,目标函数和约束条件作为抗原输入,随机产生初始抗体群,并通过一系列遗传操作及个体浓度的计算,在保持抗体多样性的情况下找出针对该抗原的抗体。本研究借助免疫机制来调整选择概率,以优化初始聚类中心,同时,在种群进化过程中,自适应动态调节交叉概率和变异概率,避免了早熟现象的发生。具体步骤如下:
1.1 染色体编码及种群初始化
染色体编码有很多方式,聚类分析中常用的是基于聚类中心的浮点数编码和基于聚类划分的整数编码。根据聚类样本的高维性和数量大的特点,本文采用浮点数编码。初始种群的产生采用随机生成,方法为:假设随机从样本空间中选K个样本作为聚类中心,其它样本随机分到这K个聚类中,并计算各个聚类的聚类中心作为初始个体的染色体编码,最后增加一位该个体所对应的适应度,即1条染色体可以用长度为(K+1)个基因位组成的浮点码串S=Z1Z2…Zkf表示,重复进行psize次(psize为种群大小),得到初始种群。
1.2 染色体适应度的选取
根据染色体的构成,采用的适应度函数为
上式中:k为聚类类别数;是簇内距离;是簇间距离。,计算公式分别为
上式中:xi表示类簇Ij中的样本;cj表示类簇j的中心。这样定义考虑了簇内聚类最小的原则。
上式中:ci,cj分别为簇i,j的中心。这样定义考虑了簇间距离最大的原则。
适应度函数受3个因素影响,即1/k,E1/Ek及。第一个因素减少的时候,另外两个因素随着k的增加而增加,所以这个适应度函数表达的内涵是在所分类别数尽可能小的情况下提高聚类的紧凑度和分离程度。
1.3 选择操作
针对基于遗传算法的聚类算法在算法开始前期收敛速度快,而后期由于各条染色体的个体差异变小使收敛速度变得很慢,本研究采用一种基于免疫原理[6]的选择操作和比例适应度分配方法相结合的混合选择算子计算个体被选中的概率以克服上述缺点。
定义1 个体浓度:
找出群体中个体浓度最大的m个个体,设为1,2,…,m,则这m个个体的个体浓度概率为
设某一个个体的适应度为fi,该个体被选中的概率为pfi,则
式中:i=1,2,…,psize。
此种选择策略有两个优点:一是个体适应度越大,则选中的概率越大,加速了算法的收敛;二是个体浓度越大则被选择的概率越小,起到抑制作用,保证了进化群体中个体的多样性,避免过早收敛。
1.4 交叉操作
标准遗传算法由于在进化过程中采用固定的交叉概率和变异概率,已经被证明无法收敛到问题的全局最优解,容易出现早熟现象,后期还会因为个体差异的减小出现收敛速度缓慢的现象。鉴于此,本研究按照一定的交叉概率采用最邻近法则进行交叉操作。首先对交叉概率和变异概率做出如下约定:当群体适应度比较集中时,使得交叉概率Pc和变异概率Pm增大;当群体适应度比较分散时,使得交叉概率Pc和变异概率Pm适当减小。这样约定能使算法在迭代过程中根据个体的适应度来改变其交叉概率Pc和变异概率Pm,从而在能保护最优个体的同时加速较差个体的淘汰速度,增强了算法的全局搜索能力。其数学模型为:
式中:K1,K2,K3,K4是小于0的常数;fmax为群体的最大适应度;favg为群体的平均适应度;f′为交叉产生的2个新个体中适应度较大的那个个体的适应度;f为变异个体的适应度值。
采用最邻近法则的基因匹配交叉操作:设待交叉的2条染色体为S1=Z
,选择S2中与Z
1.5 变异操作
变异操作是一种局部随机搜索,与选择、交叉算子结合可以保证算法的有效性。本研究中采用按基因位(一个基因即为一个聚类中心)的维向量来进行,每个基因位的每维向量(一个浮点数)按变异概率Pm来发生随机变异。在整个算法开始之前,先求出每维向量的最大值和最小值,分别保存在向量
1.6 算法终止条件
只要满足以下2个条件中的任意一个条件则算法终止:
(1)算法迭代次数超过设定一个最大的迭代次数maxGen;
(2)运行过程中得到相同的最优结果次数连续超过某一阀值。
本文采用第2个条件作为结束条件。
2 算法描述
给定样本数据集合
(1)确定要生成的类簇数目k、种群规模为psize个个体及算法结束条件。
(2)先随机选择k个初始聚类中心组成一个个体
(3)对数据集中的每一个样本数据di,依次计算它与各个聚类中心的相似度;将样本数据di合并到与其具有最大相似度的类簇中。
(4)按照相似度公式计算新的类簇的中心,组成一个个体,并计算新个体的适应度;
(5)对所有的个体实施遗传算子,得到下一代的群体;
(6)得到优化后的个体。如果所有聚类中心均达到稳定,则结束;否则,t=t+1,转(3)。
3 试验结果及分析
分别采用 k-均值算法、遗传K-均值算法(GA-K均值算法)和本文算法在VC++和MatlAB环境下进行仿真实验。遗传算法的交叉概率和变异概率初始值分别取为0.75,0.09,群体规模为100,迭代次数为100次,当运行过程中得到最优结果次数连续10次以上时算法结束。实验采用数据是Fisher的Iris 3种植物150样本个数据[9]进行10次试验,每个样本均为四维向量,代表植物的4种属性。三种算法分别单独运行10次,计算出簇内距离Ek与簇间距离Dk的最大值,最小值及平均值。实验结果见表1。
注:以上数据为单个算法运行10次的平均值。
聚类算法的理想结果是同时获得最小的簇内距离和最大的簇间距离。从表1中的数据可以看出,标准的K-均值算法由于对初始中心选取敏感性很大,在初始中心选择不当的情况下易陷入局部最优,出现过早收敛;GA-K均值算法由于个体的多样性不足而常出现早熟现象;本研究提出的算法在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,对于随机分布的数据聚类有明显的优越性;同时从达到最优解迭代次数看,本文提出的算法达到最优解的平均迭代次数要远少于K-均值和GA-K均值算法,所以本文提出的算法收敛速度更快。
4 结束语
本文对遗传算法和K-均值聚类算法进行了研究,针对K-均值聚类效果易受初始聚类中心影响的不足,为克服遗传算法引入K-均值算法所带来的易出现局部早熟的缺点,将免疫机制的选择操作引入遗传算法,使个体浓度和适应度同时对个体的选择操作产生作用,改变以往单纯以适应度来作为个体选择的依据,对算法进行改进,然后将改进的遗传算法引入K-均值算法中以优化聚类中心,提出一种基于改进遗传算法的K-均值聚类算法。试验结果表明,本研究的算法与传统的K-均值算法和GA-K均值算法比较,在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,能够有效改善聚类质量。
参考文献
[1]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社,2005:185-218
[2]Bandyopadhyay S,Maulik U.An evolutionary technique based on k-means algorithm for optional clustering in rn[J].Information Sciences,2002,(146):221-237
[3]Ahmadyfard Alireza,Modares Hamidreza.Combining PSO and k-means to enhance data clustering[A].IST2008International Symposium[C].Tehran:IEEE Press,2008.
[4]Hai-xiang Guo,Ke-jun Zhu,Si-wei Gao,et al.Animproved genetic k-means algorithm for optimal clustering[A].Sixth IEEE International Conference[C].Leipzig:IEEE Press,2006.
[5]李茂军,罗安.单亲遗传算法的机理分析[J].长沙理工大学学报(自然科学版),2004,1(1):76-79
[6]贺志民,方美娥.基于遗传算法的特征值问题求解[J].长沙电力学院学报(自然科学版),2003,18(1)12-14
[7]赖玉霞,刘建平,杨国兴.基于遗传算法的K-均值聚类分析[J].计算机工程2008,34(20):200-202
[8]王磊,潘进,焦李成.免疫算法[J].电子学报2000,28(7):74-78
遗传聚类 篇3
在对图像的研究和应用中,人们往往仅对图像中的某些部分感兴趣。这些部分常称为目标,其他部分称为背景,它们一般对应图像中特定的、具有独特性质的区域。为了辨识和分割目标,需要提取并分离这些区域,在此基础上才有可能对目标进一步利用。图像分割是指把图像分成各具特征的区域,并提取出感兴趣目标的技术和过程[1]。
图像分割在实际中已经得到广泛的应用,例如工业自动化、在线产品检验、生产过程控制、文档图像处理、遥感和生物医学图像分析、保安监视以及军事、体育、农业工程等方面[2]。总的来说,在各种图像应用中,只要需要对图像目标进行提取、测量之处都离不开图像分割。图像分割技术的发展与许多其他学科和领域密切相关。近年来,随着各学科许多新理论和新方法的出现,人们也提出了许多新的图像分割技术。例如不断涌现出利用马尔可夫随机场、专家系统、Gibbs随机场、Bayesian理论、小波模极大值、分形、布朗链、模拟退火、聚类算法和遗传算法等新的分割算法[3,4]。
1 模糊C均值(FCM)聚类算法
聚类分析方法大致可以分为四种类型:谱系聚类法、基于等价关系的聚类法、图论聚类法和基于目标函数的聚类方法。前三种方法由于各种原因实际应用不够广泛,普遍受欢迎的是第四种方法,即基于目标函数的聚类方法。该方法把聚类分析归结成一个带约束的非线性规划问题,通过优化求解获得数据集的最优模糊划分和聚类。该方法设计简单,解决问题范围广,FCM算法就属于这种方法。
给定数据集X={x1,x2,…,xn}⊂R为模式空间中n个模式的一组有限观测的样本集,对给定样本集的X聚类分析就是要产生X的聚类类别数c(2≤c≤n)划分[5]。硬聚类算法将每个辨识对象严格地划分为属于某一类。不过在实际中一些对象并不具有严格的属性,它们可能位于两类之间,这时采用模糊聚类可以获得更好的效果。FCM算法是由隶属度确定每个数据点属于某个聚类程度的一种聚类算法[6],准备将给定数据集X分为c类,设X中的任意样本xk对第i类的隶属度为μik(0≤μik≤1);该分类结果可以用一个c×n阶矩阵U来表示,该矩阵称为模糊划分矩阵。
FCM的一般描述为:
式中:m称为加权指数,又称作平滑参数;Mfc为X的模糊c划分空间:
上述目标函数中,样本xk与第i类聚类原型pi之间距离度量的一般表达式定义为:
式中:A为s×s阶的对称正定矩阵,当A取单位矩阵I时,上式对应于欧氏距离。
聚类的准则是求取Jm(U,P)的极小值min{Jm(U,P)}[4]。
由于矩阵U中各列都是独立的,因此:
考虑到dik可能为0,应分两种情况加以讨论。对于∀k,定义集合Ik和
使得Jm(U,P)为最小的μik值为:
用类似方法可获得Jm(U,P)为最小值时pi的值:
若数据集X、聚类类别数c和加权指数m值已知,就能确定最佳模糊分类矩阵和聚类中心。
2 基于模糊聚类的遗传算法
传统基于目标函数法的聚类算法本质上是一种局部搜索方法,它们采用的是迭代爬山技术来寻找最优解,存在的致命问题是容易陷入局部最优解。在一定的条件下,利用遗传算法(GA)可以在搜索空间中收敛到全局最优解。
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机全局搜索和优化方法。其本质是一种高效、并行、全局搜索方法。它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程,以求得最优解[7]。
采用遗传算法可以做到对可行解表示广泛、群体搜索性强、不需要辅助信息、内在启发式随机搜索特性,具有固有的并行性和并行计算能力,可扩展性强,易于与别的技术混合等。因此遗传算法不易陷入局部最优解,并能快速可靠地解决求解非常困难的问题[8]。用遗传算法求解聚类问题,首先要解决以下两个问题:
(1) 如何将聚类问题的解编码到基因串中。对于聚类问题的编码,有两种方式:第一种是对硬划分矩阵U进行编码,设n个样本要分成c类,用基因串a={α1,α2,…,αi,…αn}来表示某一类的分类结果,其中:αi∈{1,2,…,c};i=1,2,…,n;第二种是采用对聚类原型P进行编码,把c组表示聚类原型的参数连接起来,根据各自的取值范围,将其量化值(用二进制串表示)编码成基因串b={β1,β2,…,βk,βk+1…,β2k,…,βck},其中每个聚类原型Pi都有一组参数与之相对应。b中的前k个表示的是第一个k维聚类原型,第k+1到第2k表示的是第二个k维聚类原型,同理,共c个聚类原型。第二种方法的搜索空间只与原型参数数目和类别数有关,与数据量无关,搜索空间往往比第一种方法小的多,所以在此采用第二种编码方法。
(2) 如何构造适应度函数来度量每条基因串对聚类问题的适应程度,该方法可以这样判别:如果某条基因串的编码代表着良好的聚类结果,则其适应度就高,反之则低。
对于基于目标函数的模糊聚类问题,其最优聚类结果对应目标函数的极小值,即聚类效果越好,则目标函数越小,而此时适应度越大,因此可以借助目标函数Jm(U,P)来定义GA的适应度函数:
基于模糊聚类遗传算法的实现步骤:
① 设定种群数目N,对聚类原型pi进行二进制编码,并产生初始种群;
② 对初始种群进行解码,并用式(8)计算每条基因串的适应度值;
③ 将适应度大的个体复制到下一代种群中,然后对父代进行选择、交叉、变异等遗传算子运算,产生下一代种群的其他基因串;
④ 如果达到了设定的繁衍代数,返回最优的基因串并解码,否则,返回到步骤③进行下一代的繁衍。
3 图像分割实验结果与分析
在
这里取基于模糊聚类的遗传算法种群数目N=30,聚类数C=2,搜索代数为200代,交叉率前期为0.6,后期为0.75,变异率为0.02。
从分割图1(d)中可以看出,该算法实现了图像的有效分割,人物轮廓清晰,物体的受光面和阴影面区别明显。在分割图2(a)中,由于添加了高斯噪声,对原图的污染比较严重,但从分割图2(d)上可明显看出,采用基于模糊聚类遗传算法,其分割结果明显优于前两种方法。根据分割评价中的定性实验性准则可知[9],如果算法分割的结果大致相同,那么对预/后处理要求低的算法的相对性能要更优越一些,聚类算法对预处理的要求比较高,对初始点的选择很敏感,所以可能使分割效果不太理想,如图2(c)所示;在引入遗传算法后,利用遗传算法的全局搜索特点,可以解决FCM对初始化敏感的问题,增强了算法的抗噪性,所以图2(d)的分割效果最好。在分割速度方面,传统FCM算法的运行速度较慢,遗传算法自身具有隐并行性的特点,比盲目的搜索效率要高。用遗传算法和聚类相结合的方法,既解决了对初始化敏感的问题,又能在一定程度上提高程序的运行速度。表1列出了对图1、图2进行分割的时间列表。
4 结 语
在此,采用基于模糊聚类遗传算法的图像分割。实验表明,比传统FCM算法和简单遗传算法有了较大的改进。在保持聚类算法良好的分割效果的同时,降低了对初始化的要求,并在一定程度上提高了运行速度,验证了本文方法的有效性。遗传算法与FCM算法的结合正是近年来研究的热点之一。
参考文献
[1]章毓晋.图像分割[M].北京:科学出版社,2001.
[2]章毓晋.图像处理和分析基础[M].北京:高等教育出版社,2002.
[3]IM J,Jensen J R,Tullis J A.Object-based Change DetectionUsing Correlation Image Analysis and Image Segmentation[J].International Journal of Remote Sensing,2008,29(2):399-423.
[4]Wu Yi-Ta,Shih,Frank Y,et al.A Top-down Region Divid-ing Approach for Image Segmentation[J].Pattern Recogni-tion,2008,41(6):1 948-1 960.
[5]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2003.
[6]匡泰,朱清新,孙跃.FCM算法用于灰度图像分割的初始化方法的研究[J].计算机应用,2006,26(4):784-786.
[7]雷英杰.Matlab遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005.
[8]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社,2004.
[9]狄宇春,邓雁萍.关于图像分割性能评估的评述[J].中国图像图形学报,1999(3):183-187.
遗传聚类 篇4
关键词：遗传算法,聚类分析,交叉概率,变异概率
0 引言
遗传算法(简称GA)作为一种自适应全局优化概率搜索方法,它最早由美国Michigan大学的Holland教授提出。该算法具有很好的鲁棒性、随机性、全局性,现已被人们广泛地应用于以下主要应用领域[1]:自动控制、图像处理、机器学习、数据挖掘。聚类分析[2]是模式识别理论的一个重要方法,聚类分析通常是基于距离的,通过构造一个m维空间的距离函数,利用这个距离函数来进行聚类。传统的基于聚类准则的聚类算法本质上是一种局部搜索算法,它们采用了一种迭代的爬山技术来寻找最优值。因此,存在两个问题:一是处理大数据量费时,二是容易陷入局部极小值。
利用遗传算法可以降低传统聚类算法对初始化的要求。例如傅景广[3]等人提出了一种基于遗传算法的聚类分析方法,该算法采用二进制编码方式对聚类的中心进行编码,用特征量与相应聚类中心的欧氏距离之和来判断聚类划分的质量;张伟[4]等人也提出了一种改进的遗传算法,并用来解决聚类问题;国外也有Krishna K等人于1999年在IEEE上发表的文章《Genetic K-means Algorithm》[5],也是一种遗传K-means聚类算法。本文在总结多位专家学者的研究后,改进了传统GA算法应用于聚类分析中的交叉概率和变异概率,引入了一种与进化代数相关联的交叉概率和与个体适应度相关联的变异概率,它们具有的自适应性质能够较好地改进算法的全局性能。将该改进算法应用到图像聚类实验,并且和k-均值算法进行了比较,结果表明了其准确率明显优越于k-均值算法。
1 改进的遗传算法
1.1 传统的GA
人们习惯上把1975年提出的GA称为传统的GA,它的主要步骤如下。
编码:GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合便构成了不同的点。
初始群体的生成:随机产生n个初始串结构数据,每个串结构数据称为一个个体, n个个体构成了一个群体。GA以这n个串结构数据作为初始点开始迭代。
适应度评估检测:根据实际标准计算个体的适应度,适应性函数表明个体或解的优劣性。不同的问题,适应性函数的定义方式也不同。
选择:选择的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想,进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。
交叉:交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体,新个体组合了其父辈个体的特性。交换体现了信息交换的思想。
变异:变异首先在群体中随机选择一个个体,对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样,GA中变异发生的概率很低,通常取值在0.001～0.01之间。变异为新个体的产生提供了机会。
经典遗传算法的一次执行过程如图1所示,该图给出了第n代群体经过选择、交叉、变异生成第n+1代群体的过程。
1.2 自适应交叉概率pc与变异概率pm的设计
遗传算法中交叉概率控制着交叉算子使用的频率,交叉率越高,群体中结构的引入就越快,已获得的优良基因结果的丢失速度也相应提高了,而交叉概率太低则可能导致搜索阻滞。变异操作是保持群体多样性的手段,变异概率太小,可能使某些基因位过早地丢失信息无法恢复;而变异概率过高,则遗传算法将变成随机搜索。在传统GA算法中,pc和pm值在整个遗传优化过程中采用固定值,这就使得遗传算法在应用过程中出现一些问题(如收敛速度过慢、局部极值,很容易出现成熟收敛)。目前,国内外专家学者们认识到:如果pc、pm值能随着遗传进程而自适应地变化,那么这种有自组织性能的遗传算法将具有更高的鲁棒性、全局最优性和更快的收敛速度。
文献[6]中设计了与进化代数相关的交叉概率:
mtmp=pc,Max×2(-t/TGen) (1)
式中,mtmp是一个中间计算变量;TGen为预设的最大进化代数,t为当前进化代数(0≤t≤TGen);pc,Max是预设置的最大交叉概率;pc,Min是预设置的最小交叉概率;pc(t)是当前种群(第t代)的交叉概率。
在此基础上,本文利用Gauss函数和sigmoid函数构造与进化代数相关的交叉概率计算公式:
pc(t)=(pc,max-pc,min)·f(t)+pc,min (3)
f(t)=e-A(TGen-2t)+(1+e-B(TGen-2t))-1 (4)
式(4)中,A、B都为形状参数。该公式有利于加强GA算法在优化初期对新个体的开发和后期保护算法的稳定性。
同一代种群中各个个体的变异概率应该随个体优劣变化而变化。为了保证算法的稳定性,变异概率的取值应该是随进化过程而逐渐减小,从而使群体能够迅速集中。基于此,给出一种具有自适应的变异概率pm。
式(5)中, f(t)为式(4),f(Xi)为待变异个体的适应度值,fmax为第t代群体中的最优个体适应度值。pm,max为预设置的最大变异概率;pm,min为预设置的最小变异概率;pm(t)为第t代种群中个体的变异概率。
2 算法设计描述
综上所述,结合传统的GA算法,改进的自适应遗传算法步骤如下。
Step 1:初始化相关参数
初始化种群总数PopSize,初始代数T=0,预设的最大进化代数TGen,预设置的最大交叉概率pc,max,预设置的最小交叉概率Pm,min,为预设置的最大变异概pm,max;预设置的最小变异概率pm,min,选取参数A、B的值。
Step 2:产生初始种群
产生PopSize个满足约束条件的初始染色体xn,xi,min≤xi≤xi,max,k=1,2,…,PopSize,xi,min和xi,max分别为第i个染色体的约束条件,并计算每个染色体的评估值Value。
Step 3:适应值与评估值计算
对这个群体以Value值排序,求出序号index,根据index计算适应度值f(index),记录当前群体中最优和最差个体。建立适应度数组cfitness[PopSize],cfitness[i]的值为从第1个个体到第i个个体适应度值之和与所有个体适应值总和的比例。
Step 4:遗传运算
①选择运算
采用比例选择法执行选择操作,形成种群规模为PopSize的父代。
②交叉运算
对选择出的每一个染色体计算根据公式(3)、(4),以求得当前的,每个个体对按交叉概率pc经过杂交(即互换串中部分代码)产生两个新的子个体。
③变异运算
在群体中随机地选择一个个体,对于选中的个体以当前变异概率pm(由公式(4)、(5)求出)改变字符串中某位上的字符的值,以得到新的个体。
Step 5:停机判断
当前群体的进化代数是否大于最大迭代次数或是否达到最优解,否则转到Step 3继续执行。
3 实验仿真
目前国内外学者多用数据集进行聚类仿真并分析结果,本文现给出改进的自适应遗传算法在图像聚类方面的应用。通常在所给出的一幅图像中同时含有多个物体,在图像中进行聚类分析时需要对不同的物体分割标识。将改进的自适应遗传算法应用于图像聚类分析的重点是寻找这些物体特征的相似性。分别对三幅不同的二值图像分别应用本文算法和k-均值聚类算法进么图像聚类划分。要想对图像中的物体进行归类,则必须先找到各个物体,让计算机能够识别它们,因此,首先要确定物体是否是独立的目标物体,此处,图像中物体的标识依据图像的8点连通域判别方法。
图2(a)、图2(b)、图2(c)图分别为标准体数字的二值图、包含不同大小的几何图形物体的二值图、手写体数字的二值图。分别对三幅图用本文算法和k-均值聚类算法进么图像聚类划分,k-均值算法的迭代次数都设为100,物品间的距离计算公式采用欧式距离法。本文算法参数选取为:TGen=100,pc,min=0.1,pc,max=1,pm,min=0.01,pm,max=0.1,A=0.2,B=6.0。结果如图3所示(在进行聚类划分时,通过观察,可分别为图2(a)、图2(b)、图2(c)图标记类中心数目为4、3、4,)。
图3的各子图中,图3(a)-图3(c)图为应用k-均值聚类算法划分结果;图3(d)-图3(f)为应用本文算法划分结果。各子图内每个物体(数字或几何图形)的右下标即为类号,例如(d)图中,数字“4”的右下标都为1,说明被划分到“第1类”;数字“1”的右下标都为2,说明被划分到“第2类”;数字“2”的右下标都为3,说明被划分到“第3类”;数字“3”的右下标都为4,说明被划分到“第4类”。
为了比较两种算法,此处,定义识别率为ψ,令
其中,n为当前被正确识别的物体数目,即既不存在同类物品归入不同类中,也不存在不同类物品归入同类中。N为总的识别物体数目,计算图3各子图中的识别率,统计得到表1。
由表1可知,本文算法对3幅图像中的物品均达到了准确的聚类划分,没有误差,而k-均值算法对3幅图像的物品的聚类划分都没有“成功”,效果不佳。实验表明,对比于k均值聚类算法,本文算法具有较好的聚类划分效果。
4 结束语
文中提出的一种改进的自适应遗传算法的聚类分类,在保证全局寻优能力和收敛速度的前提下,进一步提高了在聚类分析上的准确性,并通过实验仿真对比说明这一方法的可行性。但是,当图像内含物体(样品)数量多,物体(样品)本身有较高复杂性等情况时,用本文算法还是难以达到很高的准确率。因此还有许多工作有待进行更深一步的细致研究。
参考文献
[1]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000.
[2]Han J,Kambr M.Data mining:Concepts and techniques[M].Be-jing Higher Education Press,2001.
[3]傅景广,许蹦,王裕目.基于遗传算法的聚类分析[J].计算机工程,2004.
[4]张伟,廖晓峰,吴中福.一种基于遗传算法的聚类新方法[J].计算机科学,2002,29(6):114-116.
[5]Krishna K,Muay MN.Genetic K-means Algorithm[J].IEEE Trans.on System,Man,and Cybernetics,Part B,1999,29(3):433-439.
遗传聚类 篇5
数据挖掘(Data Mining)就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。在庞大的数据集合中存在相似性很强的数据集,如果能将数据集进行分类,依据相似性建立一个种群,使得数据挖掘更有目的性和针对性。K-means聚类算法是一种快速有效的分类方法,具有较快的分类速度,但必须手动确定初始聚类中心,因此,若能够利用算法求得初始聚类中心,则结合K一均值聚类算法可以实现自动分类。遗传算法(Genetic A1gorithm—GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,它是一种启发式的全局优化搜索算法,其简单通用,鲁棒性强,适于并行处理,应用范围广。遗传聚类是将GA应用于聚类的一种方法,其基本思想是通过遗传学习,将上一代的优良特性保留下来,并通过个体之间的基因组合、变异从而产生更为优良的下一代个体,这样经过数代的个体进化,最终找到满意的个体。鉴此,本文采用K-means算法进行聚类,并采用遗传聚类算法确定聚类中心,实例结果验证了改进的算法有效可行。
1 K-means聚类算法
在聚类算法中需要考虑到底聚类算法到什么时候终止,即是如何确定聚类中心,确定多少聚类中心。K-means聚类将数据划分为n个模式,每个模式的维度为d,取其中的最小K组作为我们的聚类起点,定义如下:
令{xi,i=1,2,…,n}为模式n的集合。其中xij表示xi的第个特征。定义i=1,2,…,n;k=1,2,…,K,
那么,数组W=[wij]就有属性如下
令第k个聚类中心族为ck=(ck1,ck2,…,ckd),那么
第k个族群的内联相关族群定义为
总的内联相关族群定义为
由此就可以找到W*=[w*ik]中的最小S(W),例如
K-means算法是一个迭代算法,它开始于一个任意的族群,在每一次迭代的过程中确定那些模式属于同一聚类中心族模式,下一次的迭代就是取与该中心族相关的模式进行划分,该算法终止于没有一个模式可以在被重新指配给其它的聚类中心族。该算法由于初始的聚类中心选择的随机性,使得算法存在一个潜在的问题,及选择的聚类中心是否合适。
2 混合遗传聚类算法
遗传算法的主要问题是针对不同数据集的编码。通常采取自由选择的方法,在进化过程中生成:下一代的编码依据当前这一代的编码而不同。下面就关于编码及初始化及遗传运算做进一步的阐述。
2.1 编码
遗传算法的染色体编码有很多种,本文中采用较常用的是基于聚类中心的浮点数编码和基于聚类划分的整数编码。由于内联相关族群S(W)通常具有多维性、数量大等特点,聚类问题的样本数目一般远大于其聚类数目,因此确定染色体的长度n在{1,2,…,K}中取值,将各个类别的中心编码为染色体。例如对于一个类别为4的聚类问题,假设数据集为2维。初始的4个聚类中心点为(1,3),(2,4),(6,9),(8,7),则染色体编码为(1,3,2,4,6,9,8,7)。这种基于聚类中心的编码方式缩短了染色体的长度,提高了遗传算法的速度,对于求解大量数据的复杂聚类问题效果较好。
2.2 初始
第一代的初始聚类中心P(0)是在集合{1,2,…,K}中随机选择的。基于此种选择算法可以在运行到选择某些族群为空概率为非零的匹配族群的时候停止,由于随机选择初始聚类族群以及其他族群可以围绕此聚类中心进行计算,使得p达到一个较为理想的赋值。
2.3 选择
根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。
其中F(Si)表示串Si的合适的取值并且确定下一次变异的取值。本文采用轮盘赌的原则随机的选择。显然,从式(6)可知:(1)适应度较高的个体,繁殖下一代的数目较多。(2)适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。
2.4 交叉
交叉从相互关联的数据源中,根据不同的聚类中心的距离,按照某种关系交叉其中的基因从而形成新的个体。为了从依存对象xi中找到适应的等位基因sw(i),令dj=d(xi,cj)为xi与cj的欧氏距离,所以等位基因可以依据下面的公式选择
其中cm≥1并且dmax=maxj{dj}。
3 改进的混合遗传聚类算法
新群体的编码值为中心在变异后产生,将每个数据点分配到最近的类,形成新的聚类划分。按照新的聚类划分,计算新第二代的聚类中心,取代原来的编码值。因为K–means算法具有较强的局部搜索能力,因此引入K-means操作后,可以大大提高遗传算法的收敛速度。
混合遗传聚类算法主要是改进了初始模板的选定方法。以每个向量为圆心,以向量空间中所有句子之间距离的平均值为半径作圆,然后根据每个圆内的数据点的密度来排序确定初始聚类中心和初始聚类数。这样,K-means聚类算法需要的初始模板就由以上算法动态生成,而无需用户进行事先指定。整个过程包括以下几个基本步骤:
步骤1:选取两个正数,一般R2=2R1,其中R1为距离矩阵W(i,j)中所有元素之间距离的平均值。
步骤2:以每个句子为圆心,以R1为半径作圆,计算落在每个圆内的数据元素数目,即样本密度。
步骤3:将样本密度按从大到小的顺序排列,取密度最大者作为第一个凝聚点Z1,在密度次大的单元中任选一点k,若与第一凝聚点之间距离大于R2,即|Z1-k|>R2,则把k作为第二个凝聚点Z2,否则继续判定下一密度最大者,若下一密度最大者中的任一点与前面若干个凝聚点之间距离均大于R2,则将之作为又一新的凝聚点,如此反复迭代直到没有新的凝聚点生成。
步骤4:这些凝聚点作为聚类模板的初值即分类个数k以及初始k个聚类中心Z1,Z2,Z3,.......,Z k。
步骤5:把得到的k和k个聚类中心Z1,Z2,Z3,.......,Zk作为k-means算法的初始模板,继续用k-means算法迭代,最后得到k个聚类。
经过以上步骤的初始分类,可以得到整个向量空间的分类个数k以及模板初始聚类中心Z={Z1,Z2,Z3,.......,Zk},这样我们就从整个向量空间的统计信息中自动确定了聚类所需要的初始聚类数目和初始聚类中心,为后面的聚类过程打下了一个较好的基础。
在确定k和聚类中心Z后,接下来对数据元素向量空间进行k-means迭代。其基本原理是根据所有向量与聚类中心距离的远近程度,形成k个互不相交的聚类,较为相似的句子都聚在同一类中。因此自动聚出来的这些自然的类可以被看成描述不同侧面的理想信息,用于区分及表达不同的类。
4 实例
本文选择从网络下载的语料,选用其中的1000篇,利用手工进行分类,分类结果如表1。
衡量信息检索性能的召回率和精度也是衡量分类算法效果的常用指标。但是聚类过程中的分类类别与手工分类类别不存在确定的一一对应关系,因此直接以精度和召回率作为评价标准是不可取的。为此本文选择了平均准确率作为评价的标准。平均准确率是通过考察任意两篇文章之间类属关系是否一致从而来评价聚类的效果。实验中分别采用传统的K-means算法与改进算法,比较如表2。
实验结果表明改进与传统的K-means算法在运行速度上有一定的提高,平均准确率普遍要好,特别是在正确的指定聚类中心数K时,平均准确率提高了约9%,由此可以看到改进算法具有一定的优势。由于使用的文本集文本数量较小,未来还会继续在更大规模的文本集上测试改进算法。
另外,分别用本文所描述的改进方法和传统K-means聚类算法进行聚类确定文档集合的子主题数,并人工确定每个主题文档集合中包括的子主题数。其中,在采用传统K-means聚类方法时,初始聚类数目和初始聚类中心是需要人为给定的(取句子总数的10%)。本文分别将改进算法以及传统K-means算法得到的子主题数列出如3表所示。
从上表中可以看出,改进的混合遗传聚类算法得到的子主题数比较接近,这表明通过文中的方法在发现文档集合中的潜在子主题时比较符合文档的客观情况,而通过人为主观经验得到的子主题数相对较大。综上所述,通过改进的混合遗传聚类算法自适应发现的子主题数比较能客观的反映文档集合的情况,具有一定的效果。
5 结语
本文对数据挖掘中聚类算法做了详细的分析,对于不同的聚类方法中所出现的人工确定聚类中心点问题做了改进。本文详细分析了K-means聚类算法,在此基础上对于聚类中心点选择遗传算法通过交叉变异自适应的方式选取,构造向量间的距离矩阵,计算中心点。通过实验分析,发现改进的聚类算法有一定的效果。
摘要：针对数据挖掘因数据集合庞大而不易开展,本文提出了一种采用K-means算法进行聚类、遗传聚类算法确定聚类中心的改进方法。实例结果表明,改进的混合遗传聚类算法有效可行。
关键词：数据挖掘,遗传算法,K-means,聚类
参考文献
[1]申锐.数据挖掘技术中聚类算法的探索与研究[J].山西科技.2009.
[2]张翠萍,杨善超.基于K-均值聚类算法的中药叶片显微图像分割[J].石河子大学学报(自然科学版).2009.
[3]范明译.JiaweiHan Micheline Kamber.Data Mining:Concepts and Techniques[M].北京:机械工业出版社.2001.
遗传聚类 篇6
常规的系统评价方法存在一个共同特点,即采用“对数据结果或分布特征先作某种假定——按照一定准则建立显式评价函数——对建立的评价函数模型进行证实”这样一条证实性数据分析方法。目前常用的评价方法有:模糊综合评价方法在对各指标进行“特征化”处理后,会出现不同程度的信息丢失,为评价结论带来误差;AHP法和灰色关联评价法具有能解决多目标、多层次、多准则决策问题的优势,但评价结果往往受主观因素的支配与干扰;基于特征向量的最优综合评价法,不需人为确定权重,评价结果接近实际,但难于从系统各层次把握被评对象的综合水平及应采取的技术措施。而且由于数学化、形式化等局限性,这类方法对于处理某些高维度、非线性,非正态评价问题的适应能力不强。
针对上述问题, 学术界提出了直接由样本数据驱动的探索性数据分析方法,投影寻踪(Projection Pursuit,PP)方法[1,2]是这类方法的典型代表。所谓投影寻踪就是将高维数据向低维空间投影, 通过分析低维空间的投影特性进而来研究高维数据的特征, 是处理多因素复杂问题的统计方法。投影寻踪聚类(Projection Pursuit Cluster,PPC)模型则是依据投影寻踪思想建立的聚类分析模型, 它已被广泛应用于模式识别和多因素分析领域[3,4,5,6,7,8,9,10,11,12]。其基本思想是:把高维度的数据通过一定的组合投影到低维度子空间上,对于投影到的构型,采用投影指标函数(目标函数)来描述投影值,进而暴露原系统综合评价问题某种分类排序结构的可能性大小,寻找出使投影指标函数达到最优(即能反映高维度数据结构或者特征)的投影值,然后根据该投影值来分析高维度数据的分类结构特征(即投影寻踪聚类评价模型)。其中,投影指标函数的构造及其优化问题是应用PP方法能否成功的关键因素,其复杂性在一定程度上限制了PP方法的深入研究和广泛应用。为此,本文提出基于实数编码的加速遗传算法(Real coding based Accelerating Genetic Algorithm,RAGA)的投影寻踪聚类评价模型,并开展了相应的应用研究。
2 基于遗传算法的投影寻踪聚类评价模型
基于RAGA的投影寻踪聚类评价模型(Projection Pursuit Classification model based on RAGA,RAGA—PPC模型)的建模过程包括以下四个步骤:
(1)评价指标值的无量纲化
设各指标值的样本集(评价对象集)为{x*(i, j)|i=1～n, j=1～p}。其中x*(i,j)为第i个样本第j个指标值,分别为样本的个数(样本容量)和指标的数目。为消除各指标值的量纲和同意各指标值的变化范围,采用下式进行极值归一化处理:
式中, xmax(j), xmin(j)分别为样本集中第j个指标值的最大值和最小值。
(2)构建投影指标函数
PP方法就是把p维数据{x(i,j)|j=1～p}综合成以a=(a(1),a(2),…,a(p))为投影方向的一维投影值z(i):
然后根据{z(i)|i=1～n}的一维散布图进行分类。式(2)中的a为单位长度向量,即
在综合投影值时,要求投影值z(i)的散布特征应为:局部投影点尽可能密集,最好凝聚成若干个点团;而在整体上投影点团之间尽可能分散开。基于此,投影指标函数可构造为
式中, Sz为投影值z(i)的标准差, Dz为投影值z(i)的局部密度,即
式中,
(3)优化投影指标函数
① 投影指标函数的优化
当各指标值的样本集给定时,投影指标函数Q(a)只随投影方向a的变化而变化。不同的投影方向反映不同的数据结构特征,最佳投影方向就是最大可能暴露高维度数据某类特征结构的投影方向。可通过求解投影指标函数最大化问题来估计最佳投影方向,即
这是一个以{a(j)|j=1～p}为优化变量的复杂非线性优化问题,用常规优化方法处理较困难。模拟生物优胜劣汰规则与群体内部染色体信息交换机制的加速遗传算法(RAGA)是一种通用的全局优化方法,可用它来求解上述问题较为简便和有效。
② 基于实码的加速遗传算法原理及实现的流程
基于实码加速遗传算法(RAGA)的选择、交叉、变异是并行处理的,因此RAGA实际搜索范围广,得到全局最优点的机会也大。RAGA的循环可逐步调整、缩小优化变量的寻优区间,解的精度随着循环次数的增加可望逐步提高。
基于实码的加速遗传算法是分别在父代群体的基础上通过选择、交叉、变异算子得到3个子代群体,选择N(群体规模)个优秀个体作为下一代父代群体。有限次运算后进行加速遗传,缩小优秀个体选择的区间(分别将M次演化迭代的S个优秀个体共M×S个体的变化区间作为下一次加速遗传的变量区间),这样演化迭代与加速遗传的反复交替进行可实现遗传进化逐步向最优个体逼近,并且随着接近优秀个体,个体的密度加大,这样可在一定程度上减少早熟收敛的机率。加速遗传算法的流程见图1。
(4)聚类(优序排列)
把由(3)求得的最佳投影方向a*带入式(2)后即得各样本点的投影值z*(i)。投影值z*(i)与z*(j)越接近,表示样本i与样本j越倾向于归为一类。按z*(i)值从大到小排序,据此可把对样本集进行分类。
3 实例运用与分析
现以南京地区(5县4区)的农业生产力综合评价为例[13],进一步说明RAGA—PPC模型的应用。农业生产力综合评价指标体系包括劳动生产率、土地生产率、农业总产值、化肥用量、机械总动力、农村用电量、有效灌溉率、耕地复种指数、每劳动力负担耕地能力、净产值率、水稻气候生产力和小麦气候生产力共12项评价指标,因而指标样本集共有9个(5县4区),12个评价指标(已归一化处理),详见表1。
把该样本集依次代入式(2)、式(4)、式(5)、式(3),即得此例的投影指标函数,然后根据式(6)和式(7)所确定的问题,用RAGA进行优化,即可得到最大投影指标函数为1.02, 最佳投影方向a*=(0.348,0.125,0.095,0.046,0.279,0.503,0.188,0.302,0.286,0.427,0.249,0.262)。把a*代入式(6)后即得个样本的投影值z*(i),结果见表1和图2。
由表1和图2可知:
①该样本集按投影值的大小(即农业生产力综合水平从高到低)排序的样本序号依次为3(江宁县)、9(雨花区)、5(高淳县)、8(栖霞区)、1(六合区)、4(溧水县)、6(浦口区)、7(大厂区)和2(江浦县)。其中样本3和9可评为优,样本5、8和1可评为良,样本4、6和7可评为中等,样本2可评为差。该评价结果于文献[13]的最优综合评价法和多层次灰色关联评价法的结论基本一致。
②根据最佳投影方向,可进一步分析各评价指标对评价结果的影响程度。在本例中, a*值说明, 评价指标6、10、1、8、9、5、12、11、7、2、3和4对评价结果的影响程度依次减小,这可为各地区进一步提高农业生产力水平提供决策依据。
4 结论
投影寻踪模型(PPC)作为一种统计方法,将高维数据通过寻求最佳投影方向映射到低维子空间,将多项系统指标压缩为单向指标进行系统决策评价,可在很大程啡上避免个人主观因素对决策的不良影响,适用于数据量丰富、指标层明晰的评价体系。将基于实码的加速遗传算法(RAGA)与投影寻踪相结合, 解决了高维数据全局寻优的难题, 大大减少了寻优工作量,为高维指标评价与决策研究提供一条新的方法与思路。
本文给出了RAGA—PPC建模的详细步骤,采用实码加速遗传算法简化了投影寻踪的实现过程,克服了传统投影寻踪方法计算复杂、编程实现困难的缺点,并将其应用于农业生产力综合水平评价决策中,不仅得出南京各个区县的综合评判优劣排序, 而且由优化投影方向反映出各个评价指标对各样本总体评判的重要程度,其计算简便,适用性强,评价结果更加准确客观,为投影寻踪方法在各种综合评价中的推广应用提供了强有力的工具。
摘要：针对农业生产力综合评价这类高维指标体系决策问题,采用降维技术:投影寻踪分类模型,利用基于实数编码的加速遗传算法优化其投影方向,将多维数据指标(样本评价指标)转换到低维子空间,根据投影函数值的大小评价出样本的优劣,从而做出决策。该模型最大限度地避免了传统评判中权重取值的人为干扰,评价结果更为准确客观,为农业生产力综合评价决策及其它评判决策问题提供一条新的方法与思路。
遗传聚类 篇7
考试作为教学管理过程不可或缺的环节之一,具有教与学的双重功能,既是对学生应掌握的知识和能力的测试,也是对教师教学质量和效果的同步检验。为充分发挥考试的效能,综合评价命题质量,及时反馈教学效果,沟通教学信息,教学部门对考试成绩进行统计分析和总结是非常必要的。如果只统计考试成绩,不分析试题、试卷和考试过程,则无法确认成绩的可信性和有效性,因此把数据挖掘技术引入到考试成绩分析中,找出影响考试的真实原因,有针对性地指导教学,提高教学质量和教学效果。
本文利用学校大一学生某学期《大学计算机基础》的期末考试成绩,采用基于遗传算法的模糊聚类进行考试成绩分析,分析结果可以更好的评价学生对不同知识点的掌握,同时指导教师的教学活动。
1 基于遗传算法的模糊聚类算法
1.1 模糊C-均值算法(FCM)
模糊C-均值算法把n个向量xi(i=1,2,…,n)分为c类,采用模糊矩阵U=(uij)描述,使得被划分到同一簇的对象之间相似度最大,而不同簇之间的相似度最小。其中uij是矩阵U的第i行,第j列元素,代表xi属于第j(1荞j荞c)类的隶属度,且。
FCM算法是一个简单的迭代过程,用下列步骤确定聚类中心ci和模糊矩阵U:
步骤1:用[0,1]间的随机数初始化模糊矩阵U,使其满足;
步骤2:用计算c个聚类中心ci(i=1,2,…,c);
步骤3:根据计算目标函数。如果它小于某个确定的阀值,或它相对上次目标函数值的改变量小于某个阀值,则算法停止。这里uij介于0,1间;ci为聚类中心,dij=‖ci-xj‖为第i个聚类中心与第j个数据点间的欧式距离;且m∈[1,∞)是一个加权指数。
步骤4:用计算新的U矩阵。返回步骤2。
1.2 基于遗传算法的模糊C-均值聚类
FCM算法采用一种迭代的爬山方法来寻找最优解,因此对初始化非常敏感而容易陷入局部极小值。遗传算法是一种应用广泛的全局优化方法,利用交叉操作和变异操作可以将个体之间的信息进行交换,通过多次迭代得到最优解。因此将遗传算法和FCM算法结合起来,利用遗传算法的全局优化能力更好的进行聚类分析。
遗传算法一般需要进行以下几个操作:首先采用合适的方法将问题的解编码到基因串中,即将种群进行初始化;设置合适的适应度函数,并根据适应度函数值的大小挑选个体进行选择操作、交叉操作和变异操作等进行一代一代的演化,逐步逼近问题的最优解。因此需要根据不同的优化目标,对遗传算法的染色体编码、适应度函数、遗传操作以及停止准则进行相应的分析设计。
1.2.1 染色体编码
针对初始聚类中心固定的特点,选取定长染色体编码,即染色体的长度在遗传过程中保持不变。染色体编码由c个聚类中心在样本集中的编号组成,将编号串联在一起就形成一条染色体。染色体的表示形式为:B={b1,b2,…,bc},其中c为聚类数,bi(i=1,2,…,c}为第i个聚类中心对应的样本在样本集中的编号,为一个[1,n]之间的自然数,n为样本个数。
1.2.2 遗传操作
(1)选择操作。遗传算法中的选择操作,就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到子代群体的一种遗传运算,它是建立在对个体的适应度进行评价的基础之上,即个体适应度越高,其被选择的机会就越多,各个个体被选中的概率与其适应度大小成正比。
(2)交叉操作。交叉操作是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉操作使遗传算法的搜索能力得以提高。假设在两个父代个体XAt、XBt之间进行线性组合后所产生的两个新个体为:
其中,e为[0,1]之间的随机常数,当它是一个常数时所进行的交叉运算称为均匀算术交叉。
(3)变异操作。变异操作指把个体染色体的某些基因值采用其它基因值替换,从而形成一个新的个体。变异用来保持种群的多样性,能够改变遗传算法的局部搜索能力。
其中,r为[0,1]范围内符合均匀概率分布的一个随机数。
1.2.3 适应度函数设计
群体中每个个体根据与适应度函数值成正比的概率来决定是否能遗传到下一代,用于表示评价在整个种群中的优劣程度。在FCM算法中,个体以J(U,c1,…,cc)为目标函数值,函数值越小,个体的适应度越高。所以个体的适应度函数结合FCM算法的目标函数来定义为:
当算法进行指定的最大迭代次数Gmax代遗传或当平均适应度连续多代遗传后趋于稳定,遗传算法停止。在遗传操作的最后一代中得到适应度最高的编码,形成聚类中心矩阵。根据FCM算法计算模糊矩阵U,根据矩阵U中各个元素的隶属度划分各元素所属分类,得到最终结果。
根据以上讨论,基于遗传算法的模糊聚类的大致流程图如图1所示。
2 实例分析
用于实验的考试数据来自大一新生某学期《大学计算机基础》考试成绩,试卷包括打字、Windows、网络、Word、Power Point、Excel六个大题,其中打字部分10分,Windows和网络部分各15分,其余三部分各20分。从总得分在70到80分数段的学生中随机抽取60名考生,利用之前讨论的基于遗传的模糊聚类进行模糊聚类分析得出聚类结果可为六类:
第一类:
{4,13,16,25,29,32,39,40,42,43,45,56}
第二类:
{1,11,28,36,44,55,59}
第三类:
{2,6,7,10,15,17,19,23,27,31,34,37,48,50,52,58}
第四类:
{5,18,20,22,26,35,49,57}
第五类:
{8,30,33,38,41,46,47,51,53,54}
第六类:
{3,9,12,14,21,24}
为验证聚类结果可信性和有效性,对表中聚类后的数据对各类别题目求均值,结果如表1所示。
通过对表1数据并联系学生的实际情况可以发现:第一类的聚类依据是Windows部分得分偏低,和这部分学生平时上机的习惯有关系;第二类的聚类依据是Excel部分得分比较低,由于Excel部分涉及到函数以及数据分析等内容,相对其它部分掌握起来有一定难度;第三类Power Point部分得分较低,和学生的课下作业完成不好有关;第四类Word部分得分较低,和这部分学生以后的操作习惯有关系;第五类网络部分得分较低,和学生以往接触网络的机会不多有关;第六类打字测试的得分较低,这部分学生基本上没有任何计算机基础,甚至没有接触过计算机有关。
基于遗传算法的模糊聚类的考试成绩分析和传统的分析方法都是把考试成绩作为分析对象,对于传统的分析方法来说,样本数据都属于良好一类,只能得到成绩的均值、方差等信息,但基于遗传算法的模糊聚类的考试成绩分析能够把原本属于同一类的样本划分成更有意义的若干类,更好的评价学生对不同的知识点的实际掌握情况。同时考试成绩的分析结果能够反映教师的教学效果,指导教师在以后的教学活动中有所侧重,针对不同的学生群体采用不同的教学方法,进行个性化教学。
3 结束语
本文通过对模糊C-均值聚类算法和遗传算法的研究,为了使模糊C-均值聚类算法与遗传算法能更好地结合以弥补它们各自的缺陷,采用遗传算法对初始聚类中心进行优化,然后执行模糊C-均值聚类算法。通过抽取部分学生成绩进行模糊聚类,从分析结果来看,体现了模糊聚类数据分析相比传统数据分析的意义和价值,同时证明了本文提出的算法能克服模糊C-均值聚类算法初始化敏感的缺点,且收敛速度快。
参考文献
[1]高新波.模糊聚类分析及其应用.西安:西安电子科技大学出版社,2004.
[2]周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,2001.
[3]胡宝清.模糊理论基础.武汉:武汉大学出版社,2004.
[4]刘素华,韩萍.基于遗传算法的模糊模式识别及其应用.计算机工程与设计,2005,26(4):932-934.
[5]冯梅.基于模糊聚类分析的教师课堂教学质量评价.数学的实践与认识,2008,38(2):12—15.
[6]张秀梅,王涛.模糊聚类分析方法在学生成缋评价中的应用.渤海大学学报(自然科学版),2007,28(2):169—172.
[7]张维,潘福铮.一种基于遗传算法的模糊聚类.湖北大学学报,2002(2):101-104.