遗传优化的K均值聚类算法

论文摘要

数据挖掘作为一种能挖掘出隐藏在数据复杂关系背后有价值信息的一种新兴技术,由于其实用性而迅速发展。聚类分析方法是数据挖掘的一个重要研究方向,其作为一种无监督学习方法被广泛应用于各行各业。K均值聚类算法是聚类分析方法中一种非常典型的划分方法,该算法简单、易懂,但是存在诸如对初始中心点敏感,需事先确定聚类数及易陷入局部最优等缺陷。遗传算法提供了一个全局寻优问题的模型,近年来,越来越多的学者采用遗传算法对K均值聚类算法进行优化,形成K均值遗传算法。该算法针对染色体编码方式、遗传算子及控制参数等方面进行改进,从而实现聚类中心点的优化选取,或最佳聚类数的获取等,力求得到质量较高的聚类结果。本文在总结前人已取得的研究成果基础上,设计了一种新的遗传优化的K均值聚类算法,该算法利用遗传算法的遗传操作实现了K值的自动调整与中心点的优化选取,并借助遗传算法的全局优化能力有效克服了K均值聚类算法易陷入局部最优的缺点。在将遗传算法引入K均值聚类算法时,对遗传算子进行了如下两方面的改进:(1)适应度函数的构造。适应度函数的好坏直接影响后续一系列遗传算子的操作。在本文中适应度函数值除优化了聚类中心点的选取外,也解决了聚类数K值需事先确定且在算法执行过程中不能更改的缺陷。将遗传算法引入到K均值算法中,以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索、学习最佳聚类数K值,因此适应度函数的选取与确定将决定K值的选取与优化问题。(2)变异操作的设计。本文设计了一种新的变异操作方法,该方法通过对个体适应度函数的求解,实现对于聚类数K值的自动调整,使其能够自动向最佳聚类数靠拢。最后,在算法的实现上,采用了java程序设计语言与Mysql数据库。实验数据除采用常用的Iris数据集与Glass数据集以外,还对大量电信业务中长途电话使用情况的数据记录做了实际应用分析。经过对这些数据的验证及结果分析,证明了该算法不仅能处理不同维数的数据、具有可伸缩性,而且通过对电信数据的分析,证实该算法具有实用价值,并在此基础上设计了一种基于电信业务聚类分析的模型。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 数据挖掘
• 1.1.2 遗传算法
• 1.2 本课题研究现状
• 1.3 本文主要工作
• 1.4 内容组织
• 第二章 相关技术概述
• 2.1 聚类分析算法
• 2.1.1 聚类算法的基本理论
• 2.1.2 主要聚类分析方法
• 2.1.3 聚类有效性评价
• 2.2 K 均值聚类算法
• 2.2.1 K 均值聚类算法的基本思想
• 2.2.2 K 均值聚类算法流程
• 2.2.3 K 均值聚类算法实现
• 2.2.4 K 均值聚类算法的不足与改进
• 2.3 基本遗传算法
• 2.3.1 基本遗传算法构成要素
• 2.3.2 基本遗传算法描述
• 2.3.3 基本遗传算法研究进展
• 2.4 本章小结
• 第三章 遗传优化的K 均值聚类算法
• 3.1 问题的提出
• 3.2 遗传优化的K 均值聚类算法
• 3.2.1 算法的基本流程
• 3.2.2 染色体编码
• 3.2.3 初始种群的确定
• 3.2.4 适应度函数的构造
• 3.2.5 K 值的自动学习
• 3.2.6 遗传算子的设计
• 3.3 算法实现
• 3.4 本章小结
• 第四章 实验结果分析
• 4.1 实验设计
• 4.1.1 实验工具
• 4.1.2 实验数据
• 4.2 实验模块介绍
• 4.3 实验结果分析
• 4.3.1 仿真实验一
• 4.3.2 仿真实验二
• 4.3.3 电信长途业务分析
• 4.4 本章小结
• 第五章 遗传优化的K 均值聚类算法在电信中的应用
• 5.1 电信背景
• 5.1.1 聚类分析方法在电信中的应用
• 5.1.2 电信客户分群的意义
• 5.2 应用设计
• 5.3 本章小结
• 第六章 结论与展望
• 6.1 结论
• 6.2 展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文