进化K-Means算法研究

进化K-Means算法研究

论文摘要

聚类是一种重要的数据挖掘任务,广泛应用于模式识别、机器学习、图像处理等多个领域。它可以看作是一种组合优化问题,很多学者将具有全局优化能力的进化算法用于聚类研究。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算法,大大降低了算法的运行时间。

论文目录

  • 中文摘要
  • Abstract
  • 第一章 引言
  • 1.1 研究背景及意义
  • 1.1.1 聚类
  • 1.1.2 进化聚类
  • 1.1.3 研究意义
  • 1.2 内容安排
  • 第二章 进化聚类算法
  • 2.1 K-Means算法
  • 2.2 遗传算法
  • 2.2.1 算法思想
  • 2.2.2 算法特点
  • 2.3 进化聚类的关键因素
  • 2.3.1 编码方式
  • 2.3.2 进化算子
  • 2.3.3 适应值函数
  • 2.3.4 K-Means局部搜索
  • 2.3.5 其它
  • 2.4 本章小结
  • 第三章 F-EAC算法
  • 3.1 编码方式
  • 3.2 适应值函数
  • 3.3 变异算子
  • 3.3.1 消除算子
  • 3.3.2 分裂算子
  • 3.3.3 算子的选择
  • 3.4 算法描述
  • 3.5 本章小结
  • 第四章 全局性分裂算子
  • 4.1 原分裂算子的分析
  • 4.1.1 局部分裂较差
  • 4.1.2 全局划分不利
  • 4.1.3 初始分裂点的选择
  • 4.2 全局性分裂
  • 4.2.1 分裂思想
  • 4.2.2 半全局分裂
  • 4.2.3 全局分裂
  • 4.3 实验结果
  • 4.3.1 实验数据
  • 4.3.2 结果分析
  • 4.4 本章小结
  • 第五章 自适应合并算子
  • 5.1 待变异状态分析
  • 5.1.1 待合并状态
  • 5.1.2 待消除状态
  • 5.1.3 待分裂状态
  • 5.2 合并算子
  • 5.2.1 算子流程
  • 5.2.2 自适应选择
  • 5.2.3 算子分析
  • 5.3 实验结果
  • 5.4 本章小结
  • 第六章 算法并行
  • 6.1 并行模型
  • 6.1.1 概念模型
  • 6.1.2 OpenMP编程模型
  • 6.2 多核并行
  • 6.2.1 多核计算
  • 6.2.2 串行F-EAC算法分析
  • 6.2.3 并行实现
  • 6.3 实验结果
  • 6.4 本章小结
  • 总结与展望
  • 参考文献
  • 致谢
  • 个人简历、在学期间的研究成果及发表的学术论文
  • 相关论文文献

    标签:;  ;  ;  ;  

    进化K-Means算法研究
    下载Doc文档

    猜你喜欢