内容发布更新时间 : 2024/11/14 3:11:24星期一 下面是文章的全部内容请认真阅读。
青岛科技大学研究生学位论文
受，它在数据挖掘方面的应用也得到了极大的重视。遗传算法应用于决策树、关联规则、聚类分析等方面的文献不断涌现，遗传算法已是数据挖掘领域的一个重要课题。遗传算法效仿了生物的进化过程，通过种群一代又一代地繁殖和交换，它能搜索到多个局部极值，从而增加了找到全局最优解的可能行。将遗传算法引入到聚类中，可以提高聚类算法的找到全局最优的可能性。
用遗传算法求解聚类问题，首先要解决三个问题： (1) 如何将聚类问题的解编码到个体中；
(2) 如何构造适应度函数来度量每个个体对聚类问题的适应程度，即如果某个体的编码代表良好的聚类结果，则其适应度就高；反之，其适应度就低。适应度函数类似于有机体进化过程中环境的作用，适应度高的个体在一代又一代的繁殖过程中，产生出较多的后代，而适应度低的个体则逐渐消亡；
(3) 如何选择各个遗传操作以及如何确定各控制参数的取值。
解决了这些问题后就可以利用遗传算法来求解聚类问题，这也显示了遗传算法与求解问题无关的强大通用性。
4.5改进的遗传k-means算法(IGKA)
为了能够让遗传算法和k-means算法的结合更好地弥补它们各自的缺陷，同时提高算法的收敛速度并改善聚类结果，本文算法主要从四个方面对传统遗传算法聚类做了改进[57]：
首先，采用了把聚类中心作为染色体的浮点数编码方式，这样既使大数据集的编码过程得到了简化，又减少了整个算法的运算量；
其次，为了保证进化过程中每一代当前最优个体不被遗传操作破坏，采用了轮盘赌和最优保存策略相结合的混合遗传算子；
再次，在交叉操作中，为了减少无意义个体的产生，先对交叉个体进行了基于最短距离的基因匹配，然后再运用算术交叉来增强遗传算法的局部搜索能力；
最后，为了提高遗传聚类的收敛速度，在每一代遗传操作结束之后对要进入下一代的群体进行k-means优化操作。 4.5.1 IGKA算法流程
通过上面的描述可知，与基本遗传算法的总体运行过程相比，IGKA算法也是从随机产生的初始群体开始全局最优解的搜索过程，只不过它在进行遗传操作后，再对生成的种群中的每个个体进行一步k-means优化操作，然后将优化后的
35
基于遗传算法的k-means聚类挖掘方法研究
结果作为下一代的种群。这个过程反复迭代进行，直到达到最大代数或者结果符合要求为止。
改进的遗传k-means算法流程描述如下：
(1) 参数设置：样本数N，聚类数K，种群大小Psize，最大迭代次数T，交叉概率Pc，变异概率Pm。
(2) 种群初始化：从样本中随机选取K个点作为聚类中心并进行编码，重复Psize次，产生初始种群。
(3) 对种群中的个体进行适应度计算；
(4) 根据计算处的适应度值，对种群进行选择操作。 (5) 对选出的个体进行交叉操作。
(6) 对交叉后的个体进行变异操作，产生新的种群。
(7) 对产生的新种群中的每个个体执行k-means操作，将其优化为以该个体为初始值的k均值问题的局部最优解。
(8) 产生出新一代的种群。
(9) 判断结束条件，当条件满足时结束操作，输出结果；否则，转向第(3)步。 改进型遗传k-means的伪代码描述为： Procedure IGKA
{ Initialize /*初始化*/ 聚类样本集X，聚类数K
初始种群大小Psize，交叉概率Pc 变异概率Pm，最大迭代次数Tmax；
t=0； /*t为进化代数计数器*/ 初始化种群P(0)； While (t 计算第t代种群中各个体的适应度； End for For i=1 to Psize do 对P(t)代种群进行选择、交叉、变异操作； 对遗传操作后的种群进行k-means优化，产生新的种群P(t+1); End for End while } 输出末代的最优个体。 36 青岛科技大学研究生学位论文 改进型遗传k-means算法的流程图如下： 输入参数,数据集将聚类中心编码成位串生成初始种群P(t)对种群个体进行适应度计算选择操作交叉操作t=t+1变异操作k-means优化操作产生新一代种群P（t+1)是否满足终止条件是输出最佳聚类中心否 图4-1改进型遗传k-means算法的流程图 Fig.4-1 The flow chart of Improved genetic k-means algorithm 4.5.2目标函数 改进型遗传k-means聚类算法(IGKA)目标与k-means聚类算法是一致的，即将包含n个对象的集合划分为k个类，每个对象都是d维向量，最终使目标函数最小化。因此IGKA算法的目标函数采用k-means算法的聚类目标函数式(4-1)， 37 基于遗传算法的k-means聚类挖掘方法研究 又可表示为： k2 J???i?1xj?Cixj?zi (4-6) 4.5.3编码方法 按照遗传算法的程序流程，用遗传算法求解问题，首先要解决的问题是如何确定编码和解码运算，编码形式决定了交叉算法和变异算子的操作方式，对于算法的性能如搜索能力和计算效率等影响很大。 常用的编码方案有浮点数编码和二进制编码。浮点数编码方法又叫真值编码方法，它是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数，具有适合于大空间搜索、局部搜索能力强、不已陷入局部极值、收敛速度快的特点。由于聚类样本具有多维性、数据量大的特点，如果采用传统的二进制编码染色体的长度会随着维数的增加或精度的提高而显著增加，从而使得搜索空间急剧增大，大大降低了计算效率。基于上面分析，这里采用浮点数编码。 在遗传聚类问题中，可采用的染色体编码方式有两种：一是按照数据所属的聚类划分来生成染色体的整数编码方式；一是把聚类中心(聚类原型矩阵)作为染色体的浮点数编码。聚类问题的解是各聚类中心，因此本文采用基于聚类中心的浮点数编码。 所谓的将聚类中心作为染色体的浮点数编码，就是把一条染色体看成由K个聚类中心组成的一个串。具体编码方式如下：对于D维样本数据的K类聚类分析，基于聚类中心的染色体结构为： S??x11,x12,?,x1d,x21,x22,?,x2d,?,xk1,xk2,?,xkd? 即一条染色体是一个长度为k?d的浮点基因串。这种编码方式意义明确、直观，避免了二进制编码在运算过程中反复进行译码、解码以及长度受限等问题。 4.5.4 种群初始化 确定了编码方式之后，接下来要进行种群初始化。初始化的过程是随机产生一个初始种群的过程。首先从样本空间中选K个个体，K值由用户自己来指定，每个个体表示一个聚类中心，根据我们所采用的编码方式把这组个体(聚类中心)编码成一条染色体。然后重复进行Psize次染色体初始化，Psize为种群大小。 38 青岛科技大学研究生学位论文 4.5.5适应度函数的设计 适应度函数是用来评价个体的适应度，区别群体中个体优劣的标准。由于聚类问题实际上是找到一种划分，也就是要使待聚类数据集的目标函数J达到最小化。遗传算法在处理过程中对每个染色体，采用与k-means算法相同的方式进行类别划分和重新计算各聚类中心，k-means算法是根据式(4-1)每个聚类中的点与相应聚类中心的距离作为判别聚类划分质量好坏的准则函数J，J越小表示聚类划分的质量越好。 遗传算法的目的是搜索使目标函数J值最小的聚类中心，因此可借助目标函数来构造适应度函数如下式： f?4.5.6选择操作 在生物的遗传和自然进化的过程中，对生存环境适应度较高的物种将有更多的机会遗传到下一代；而适应度较低的物种遗传到下一代的机会就相对较少。遗传算法中的选择操作体现了这一“适者生存”的原则：适应度越高的个体，参与后代繁殖的概率越高。遗传算法中的选择操作就是用来确定如何从父代群体中按照某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。选择操作是建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。 为了保证适应度最好的染色体保留到下一代群体而不被遗传操作破坏掉，根据目前已有的选择方法，本文采用了轮盘赌和最优策略保存法相结合的混合选择算子。该选择算子具体操作如下： (1) 首先在计算完当前种群的适应度后，记录下其中适应度最大的个体； (2) 再根据各个体的适应度值f(Si)，i?1,2,?,Psize计算各个体的选择概率： Pi?f(Si)Psize11?J (4-7) (4-8) ?j?1Psizef(Sj)式中，Psize为种群大小, ?j?1f(Sj)为所有个体适应度的总和。 (3) 根据计算出的选择概率，使用轮盘赌法选出个体； 39