论文摘要
聚类是一种重要的数据挖掘任务,广泛应用于模式识别、机器学习、图像处理等多个领域。它可以看作是一种组合优化问题,很多学者将具有全局优化能力的进化算法用于聚类研究。K-Means是一种经典的聚类算法,但需要提前指定聚类个数k,且对初始聚类中心比较敏感。为了克服K-Means初始聚类中心对聚类结果的影响,学者们提出遗传K-Means聚类算法GKA （Genetic K-Means Algorithm）,它利用进化的思想不断优化聚类中心。然而,GKA只是针对k为指定的聚类问题,为了能自适应地确定k, Hruschka设计了一种进化聚类算法E AC （Evolutionary Algorithm for Clustering）,它舍弃了复杂的交叉算子,采用两种特殊的变异算子来进化类簇的中心及个数,并把K-Means作为局部搜索算子。但是它对变异对象和变异算子的选择是随机的,缺少指导性。根据簇的质量信息来选择变异对象,通过算子的应用性能选择变异算子,Alves与Naldi提出了F-EAC （Fast EAC）算法,并分析了它的有效性。本文在F-EAC算法框架下,对进化算子进行深入研究,从不同角度对变异算子作出了改进,以提高聚类准确率；并研究了算法的多核并行,以提高运行效率。主要完成了四个方面的工作：第一,介绍与分析了进化聚类的关键因素：编码方式、进化算子、适应值函数、局部搜索等。第二,针对分裂算子中簇分裂的随机性与局部性,提出了两个全局分裂算子：结合最大最小距离的思想,利用周边簇中心来指导簇分裂初始点的选择,使簇的局部分裂更有利于全局划分,进一步提高了进化聚类的准确率。第三,针对F-EAC对进化操作的完备性及合理性缺少相应的分析与说明,探讨了簇的具有不同特征的待变异状态,提出了一个合并算子,自适应地应用于待变异对象上,实现了更加有效的聚类。第四,针对进化操作和K-Means的计算复杂性,并根据进化算法本身易于并行的特点,利用OPenMP实现了多核并行F-EAC算法,大大降低了算法的运行时间。