内容发布更新时间 : 2025/4/7 20:25:49星期一 下面是文章的全部内容请认真阅读。
青岛科技大学研究生学位论文
受，它在数据挖掘方面的应用也得到了极大的重视。遗传算法应用于决策树、关联规则、聚类分析等方面的文献不断涌现，遗传算法已是数据挖掘领域的一个重要课题。遗传算法效仿了生物的进化过程，通过种群一代又一代地繁殖和交换，它能搜索到多个局部极值，从而增加了找到全局最优解的可能行。将遗传算法引入到聚类中，可以提高聚类算法的找到全局最优的可能性。
用遗传算法求解聚类问题，首先要解决三个问题： (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