外文翻译译文--基于遗传算法的聚类分析研究.doc

《外文翻译译文--基于遗传算法的聚类分析研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、讹I工工芳七本科毕业设计外文翻译（2014届）论文题目基于遗传算法的聚类分析研究作者姓名应豪超指导教师盛伟国学科（专业）计算机科学与技术+口动化1001所在学院计算机科学与技术学院提交U期2014年2月基于遗传算法的聚类分析研究摘要：遗传算法(GAs)通常被描述成能够在一•个有限样本函数值内寻找最优值的搜索过程。在本文屮，gas用于尝试寻找关于聚类问题的n标函数值的最优值。一些在模拟和实际数据集上的实验结果展示了这种方法的有效性。K-Means算法是解决聚类问题的最常用算法之一，对实验结果的分析也

2、展示了本文所提出的算法也能够改善K-Means算法的输出结果。—、引言聚类是观察数据内在结构的一-种重要的手段。更具体地，聚类分析的H标(Anderberg,1973;DevijverandKittier,1982;JainandDubes,1988;TouandGonzalez,1974)是将模式特别是高维空间的向量分成簇的过程，使得同一簇内的的数据高度同质，不同簇内的数据高度相异。我们假设给定的模式属于n维的欧几里德空间，那么相异度就可以用欧氏距离来度量。我们假定模式集M是｛州宀,・・・,心｝

3、,其中兀•是第i个模式向量。聚类中心数是k。如果聚类集合用CPC2,...,C,表示，那么需满足以下几个条件：Pl.GH0,foi-i=l,・・・,k.P2.C,cC=0foriHj,andJP3.U'=1C,=M聚类方法大体上可分为两种：层次聚类和非层次聚类(Anderberg,1973)K-means算法是众多非层次方法屮应用最为广泛的算法，其主要在给定的H标函数上寻优。它力求寻找到模式和其聚类屮心欧氏距离之和的最小值，但是这种算法容易收敛到局部最优解(SelimandIsmail,1984)

4、。复杂问题的全局最优解已被证明不能在一个可行计算时间内找到(Spath,I980)o这就使得一•些解决内在优化问题的近似方法得以发展。许多这类技术能够找到局部最优解，却不一定能够达到全局最优解(SelimandIsmail,1984)0在本文屮，我们尝试使用遗传算法(GAs)寻找聚类问题的最优解。实验结果将在一些模拟和实际的数据上呈现。第二部分是问题描述，第三部分是我们所提的遗传算法的细节，第三部分是实验结果与分析。二、问题描述己有一些方法度量如何将给定数聚集进行聚类。一•种用于聚类的原则是尽量减

5、少来自各个聚类集合的数据点的欧氏距离平方之和。数学描述如下：1.CpC2,...,Q是M的k个数据集合2.工心严)/#5佝T=l,2,...,k,其中x是q中的一个模式向量,#q是q中数据点的数冃3.H标函数是/«2，・・・,4.在满足第一部分Pl,P2,P3的条件下最小化/'(GG，…,CQFl标函数.f是非凸的，因此聚类问题可能找到局部最小值而不是全局最小解(SelimandIsmail,1984)O事实上，为了找到最优解CPC2,...,CA,M屮所有可能的聚类屮心都被考虑。因此考虑到计算机

6、的内存和速度，在允许的吋间内找到问题的精确解只有在理论上存在可能。如果通过枚举的方式求解，那么有S(zn,Q中可能(Anderberg,1973;Spath,1980),其中S(计)詁£(—厂k!；=1I丿丿这明显地显示了在有限的计算时问内采用枚举法解决现实牛活小绝大多数的聚类问题是不可能的。例如，本文所使用的原油数据(JohnsonandWichem,1982)，精确解要求考虑5(56,3)种划分(S(56,3)>10】8)。因此，启发式的估算方法是在寻找一•种折屮或者在不需要全局最优值的情况下

7、考虑局部最优解。在木文屮我们应用遗传算法寻找给定聚类问题的FI标函数/的最优解。下一•部分将描述算法细节。三、基于遗传算法的聚类分析遗传算法是基于自然基因系统规则的启发式搜索方法(Goldberg,1989;Michalewicz,1992)。遗传算法为了求解优化问题屮适应度函数的最优值来搜索解空间。不像其他搜索方法，遗传算法同吋搜索多个可行解并且计算他们的适应度函数值。在运筹学，超大规模集成电路设计，模式识别，图像处理，机器学习等领域，遗传算法已经在理论和实际运用屮被发现能够找到复杂优化问题的全

8、局近似解(Ankerbrandtetal.,1990;BelewandBooker,1991;BornholdtandGraudenz,1992)o当用遗传算法解决优化问题吋，每一种可行解通常被编码成一定长度的二进制串(称为染色体)。每一个串或者染色体被称作是一个个体，所有个体的集合称作种群。遗传算法从一个随即产牛的大小为P的种群开始,并在每一次迭代屮,同一大小的种群从当代种群屮在个体屮使用两种基本的算子产牛。这两种算子是选择和重纽，并且重纽乂由交叉和变杲算子组成。在遗传算法屮，H