基于遗传算法的k-means聚类挖掘方法研究
计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类问题，人们已意识到应把主要精力放到寻求其满意解上，而遗传算法就是寻求这种满意解的最佳工具之一。时间证明，遗传算法对于组合优化中的NP完全问题非常有效。
(3) 生产调度问题
采用遗传算法能够解决复杂的生产调度问题。在单间生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。
(4) 自动控制
在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步应用，并显示出了良好效果。例如，基于遗传算法的模糊控制器优化设计，用遗传算法进行航空控制系统的优化，使用遗传算法设计空间教会控制器等。
(5) 机器学习
基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属函数等。基于遗传算法的机器学习可用于调整人工神经网络的连接权，也可用于神经网络结构的优化设计。分类器系统在多机器人路径规划系统中取得了成功的应用。
(6) 图像处理
图像处理是计算机视觉中的一个重要领域，在图像处理中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理的优化计算方面找到了用武之地。
(7) 机器人学
机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要领域。例如，遗传算法已经在移动机器人路径规划、机关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。
3.7本章小结
本章详细介绍了遗传算法的有关知识，包括遗传的历史与发展、基本术语、遗传算法的基本要素、算法的特点、算法思想及其执行过程、应用等。
30
青岛科技大学研究生学位论文
第四章 一种改进的遗传k-means聚类算法
k-means算法是一种重要的聚类算法，算法简单、收敛速度快，被广泛地应用于各个领域。虽然k-means算法具有较强的局部搜索能力，但因对初始聚类中心敏感，容易陷入局部最优，从而影响聚类结果。遗传算法是一种高效的全局搜索方法，但其局部搜索能力较差。若将k-means算法与遗传算法相结合，互相取长补短，既通过遗传算法保证获取全局最优解，又利用k-means算法兼顾局部寻优能力，提高收敛速度，从而达到理想的聚类效果。基于这种思想，本文在简单遗传算法的基础上进行了一些改进，提出一种改进型遗传k-means聚类方法(Improved Genetic k-means Algorithm，IGKA)。
4.1 k-means算法的思想与流程
k-means算法是由J.B.MacQueen[48]于1967年提出的，目前是用于科学和工业应用的诸多算法中的一种极有影响力的技术。k-means算法属于聚类分析中的划分算法，它是一种己知聚类类别数的算法。由于本文重点研究基于遗传的k-means聚类方法，因此必须详细掌握k-means算法的基本原理。 4.1.1 k-means算法思想[49]
对于给定的包含n个数据对象的数据集，k-means算法首先要求用户指定最终划分类别数目为k，然后随机选取k个点作为聚类中心，计算剩余数据对象到各聚类中心的距离，利用距离最近原则，把数据对象归到离它最近的那个聚类中心所在的类中去，聚类结果由k个聚类中心来表达，基于给定的聚类目标函数(或者说是聚类效果判别准则)，算法采用迭代更新的方法，每一次迭代过程都是朝目标函数值减小的方向进行。
k-means算法以相邻两次的聚类中心没有任何变化，数据对象调整结束，聚类准则函数J收敛作为终止准则。该算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整。在全部数据调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的数据对象被正确分类，则不会有调整，聚类中心也不会有任何变化，这标志着J己经收敛，至此算法结束。
31
基于遗传算法的k-means聚类挖掘方法研究
k-means算法的最终聚类结果是使目标函数值取得极小值，使得类内对象的相似性最大，类间对象的相似性最小。因此k-means算法通常采用欧几里德距离作为衡量相似性的指标，则评价划分质量的目标函数J的可定义为：
knij2 J???wi?1j?1dij
(4-1)
其中，k为分类数，n为样本点总数，dij?xj?zi为欧式距离，表示原始的
样本点xj到类Ci的中心zi的距离，zi是类Ci中所有数据对象的平均值，wij表示数据对象隶属于哪个类。该目标函数又称为误差平方和准则函数。
wij???1?0若第j个对象属于第否则Ci个类 (4-2)
聚类结果用隶属矩阵W?[wij]表示。该式保证一个类中至少有一个对象且一个对象仅属于一个类。 k-means算法伪代码描述如下：
//输入 数据库中的n个样本{x1,x2,?,xn}，要划分的类别数k； //输出 使目标函数最小化的k个类； 初始化k个聚类中心； Repeat
For(对每一个样本xi，i=1,2,?,n) 计算xi与每个聚类中心之间的距离； 将xi分配给距离最近的类Cj； For(对划分好的类别Cj，j=1,2,?,k) 计算每个类中所有样本的平均值；
计算目标函数J；
用当前Cj中所有样本的平均值替代上一次的聚类中心； Until J不再明显变化或者聚类中心不再改变。 4.1.2 k-means算法流程
k-means算法的具体过程描述如下：
(1) 给定样本数据集?x1,x2,x3,?xn?、类别数k，并从中随机选择k个点
c1,c2,c3,?ck作为k个聚类类别的中心点。
32
青岛科技大学研究生学位论文
(2) 计算每个数据对象与聚类中心的距离D(xi,cj)，i=1，2，3，?，n，j=1，2，3，?k，如果满足
D(xi,ck)?min{D(xi,cj)，i?1,2,3,?n;j?1,2,3,?k} (4-3)
则将xi划分到类Ck中。
***(3) 根据划分后各集合中的点计算新的聚类中心c1*,c2计算公式为： ,c3,?,ck，
c*j?1nj?x j=1,2,3,?k (4-4)
mxm?Cj其中nj为类Cj中点的个数。
(4) 判断：如果cj?c*j，则算法结束当前中心点为最终的聚类划分结果；否则令cj??c*j，返回(2)继续执行。
为防止步骤(4)的终止条件不能满足而出现的无限循环，通常在算法执行时给出一个固定的最大迭代次数。
4.2 k-means算法的特点
k-means算法是解决聚类问题的一种经典算法。它最大的特点是采用两阶段反复循环结构，算法结束的条件是不再有数据元素被重新分配；两个阶段分别是：(1) 指定聚类。即指定数据xi到某一聚类，使得它与这个聚类中心的距离比它到其他聚类中心的距离要近。(2)修改聚类中心。
该算法的主要优点是算法简洁、计算速度快、资源消耗小。如果结果簇是密集的，簇与簇之间明显分离时，它的聚类效果最好，而且对于处理大数据集，这个算法是相对可伸缩和高效的。
其缺点主要包括以下四方面：
(1) 对初始聚类中心和样本的输入顺序敏感，不同的初始聚类中心或是样本的输入顺序不同产生的聚类结果差别很大；
(2) 该算法采用一个类中所有对象的平均值作为中心，比较容易发现球状簇，而不容易发现其他形状的簇，而且它对于“噪声”和孤立点数据是敏感的，少量的孤立点数据会对计算平均值产生很大的影响，这会使平均值得到很大的偏离。
(3) 在k-means算法中常采用误差平方和准则函数作为聚类准则，一旦选择
33
基于遗传算法的k-means聚类挖掘方法研究
了准则函数，聚类问题就成为一个定义明确的优化问题，即使得准则函数取极值。所以在运用误差平方和准则函数测度聚类效果时，最佳聚类结果对应于目标函数的极值点，由于目标函数存在着许多局部极小点，而算法的每一步都是沿着目标函数减小的方向进行，若初始化落在了一个局部极小点附近，就会造成算法在局部极小处收敛。
(4) 从k-means算法流程可以看出，该算法在运行过程中需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心。因此，当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。
针对以上的局限性，所以考虑对k-means算法进行改进或将它与其他全局搜索算法结合起来用于聚类分析当中。
4.3基于k-means的改进聚类算法
由于k-means算法在实际应用中易于实现而且其复杂性相对较小，所以目前对k-means算法的研究已非常深入，其中已作出的主要研究成果有：
(1) 将模拟退火运算用于聚类之中[50]，采用模拟退火算法对k-means算法的分类矩阵进行退火优化运算，易于找到全局最优解。
(2) 基于遗传算法的k-means聚类方法，用遗传算法指导聚类问题[51][52][53]。 (3) 用Tabu搜索算法求解k-means聚类问题[54]，它通过对划分矩阵的随机搜索以获得全局最优解。
(4) 用k-means算子代替遗传算法中的交叉算子[55]，设计出一种混合遗传算法，并根据Guter引入的有限状态齐次马尔科夫链方法证明了该方法以概率1收敛到全局最优点。
(5) 将普利姆算法思想引入到k-means初始中心选择的过程中[56]，降低k-means算法对初始中心的敏感。
由于人工模拟，遗传算法,免疫算法，进化策略等随机搜索算法可以避免收敛到局部最优解，并能找到一个全局最优解，于是我们考虑用这些算法来弥补传统k-means算法的缺点。本文重点研究遗传算法结合k-means算法的方法，下面的章节将对这种思想给予详细的描述。
4.4聚类分析中的遗传算法
遗传算法作为一种有效的全局并行优化搜索工具早已被众多应用领域所接
34