基于遗传算法的数据挖掘方法研究

论文摘要

随着生产、生活节奏的加快和信息技术的进步,数据信息量以指数形式增长。数据挖掘技术具有强大的数据分析处理能力,能为决策者提供重要的、极有价值的信息或知识,从而产生不可估量的效益。因此数据挖掘方法的研究具有很重要的理论和现实意义。聚类分析是数据挖掘的主要任务之一,k均值算法是最常用的聚类方法。k均值算法的局部搜索能力强、收敛速度快,且聚类结果不受样本数据输入顺序的影响。但该算法对初始聚类中心的选取非常敏感,极易陷入局部极小值。遗传算法具有强大的全局寻优能力,运算过程不依赖于梯度信息或其它辅助知识,只需确定目标函数和适应度函数,被广泛用于解决各类优化问题。因此,将遗传算法与k均值算法相结合,既能发挥遗传算法强大的全局寻优能力,又能兼顾k均值算法较强的局部搜索特点。如何将遗传算法与k均值算法更好的结合,优势互补,提高聚类算法效率,是本文研究的主要内容。针对聚类问题,本文对标准遗传算法进行改进。首先,遗传算法采用浮点数编码方法,在保持交叉、变异后的搜索空间不变的基础上,缩短了染色体编码长度;其次,采用基于最短距离基因匹配的算术交叉算子和均匀变异算子,保证产生有意义的新染色体;再次,用父代种群参与竞争的策略代替经常使用的最优保存策略,提高算法的收敛速度;最后,用两种停止准则结合使用的方法,控制遗传算法的运算过程,有效缩短了算法的运行时间。这两种停止准则分别是:种群的进化代数达到指定的终止代数T ,遗传算法停止;连续多次迭代的种群个体的平均适应度值之间差异小于某一极小阈值,遗传算法停止。若两种准则满足其一,遗传算法停止。本文提出了一种改进的遗传k均值聚类算法(IGK),就是将改进的遗传算法与k均值算法相结合,先用改进的遗传算法对初始聚类中心进行优化,再执行k均值算法。测试结果证明,IGK算法可以避免聚类算法陷入局部极小值,算法的稳定性高,收敛速度快。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 选题背景及研究意义
• 1.2 国内外研究现状
• 1.2.1 数据挖掘研究现状
• 1.2.2 遗传算法研究现状
• 1.3 遗传算法与数据挖掘
• 1.4 本文研究内容及论文安排
• 2 数据挖掘概述
• 2.1 数据挖掘的起源
• 2.2 数据挖掘研究的理论基础
• 2.3 数据挖掘的任务、方法和过程
• 2.3.1 数据挖掘的任务
• 2.3.2 数据挖掘的方法
• 2.3.3 数据挖掘的过程
• 2.4 数据挖掘的应用领域
• 2.5 数据挖掘面临的问题与挑战
• 2.6 本章小结
• 3 遗传算法的基本原理与方法
• 3.1 编码方式
• 3.1.1 二进制编码方法
• 3.1.2 浮点数编码方法
• 3.1.3 符号编码方法
• 3.2 适用度函数
• 3.2.1 常见的几种适应度函数
• 3.2.2 适应度函数的设计
• 3.2.3 适应度函数的尺度变换
• 3.3 遗传算子
• 3.3.1 选择算子
• 3.3.2 交叉算子
• 3.3.3 变异算子
• 3.4 控制参数的选择
• 3.5 遗传算法的流程
• 3.6 标准遗传算法
• 3.7 本章小结
• 4 遗传算法在聚类分析中的应用
• 4.1 聚类分析概述
• 4.1.1 聚类定义
• 4.1.2 相似性度量
• 4.1.3 聚类准则
• 4.1.4 聚类分析算法
• 4.2 遗传算法用于聚类分析
• 4.2.1 k 均值算法基本思想
• 4.2.2 k 均值作为优化问题
• 4.2.3 使用遗传算法改进k 均值算法的必要性
• 4.3 改进的遗传k 均值聚类算法
• 4.3.1 编码方式
• 4.3.2 适应度函数设计
• 4.3.3 遗传算子
• 4.3.4 停止准则
• 4.3.5 k 均值操作
• 4.4 改进的遗传k 均值聚类算法流程图
• 4.5 本章小结
• 5 算法测试与应用实例
• 5.1 算法测试
• 5.1.1 实验数据集
• 5.1.2 实验结果与分析
• 5.2 应用实例
• 5.3 本章小结
• 6 结论
• 6.1 本文工作总结
• 6.2 展望
• 致谢
• 参考文献
• 附录