带交叉变异算子的自适应粒子群聚类算法的研究

摘要

聚类分析是数据挖掘中一项重要的挖掘任务。所谓“物以类聚”,聚类分析从大量数据对象中寻找数据属性间的相似性,并以此为数据对象分类,从而达到和优化大规模数据的查询和发现隐含有用信息的目的。
　　本文着重对聚类分析中应用最广泛的是基于划分的聚类方法——K-means聚类方法进行了深入地研究,并对其优缺点进行了分析,该算法具有思想简单、结构简单、执行效率高等优点,但是算法也存在着对初始聚类中心敏感、容易陷入局部最优的缺点,而这两个缺点也是制约该算法应用的主要原因。为了改善K-means聚类方法对初始聚类中心敏感、容易陷入局部最优的缺点,本文采用具有全局寻优能力和更高分类准确度的改进型粒子群算法与K-means算法相结合。其中主要研究工作包括:
　　(1)对标准粒子群算法惯性权重因子的研究。由于标准粒子群算法中粒子飞行方向与速度对惯性权重w的依赖性强,本文提出了惯性权重改进方案,即随粒子群算法执行过程动态变化的自适应惯性权重。
　　(2)设计了基于适应度为基准的交叉操作,这样保证了种群中粒子的多样性,加强了粒子的全局搜索能力,也加快粒子群收敛速度。提出了基于群适应度标准差的变异操作,变异操作通过粒子群的群体适应度标准差σ2和当前粒子理论最优值fgbest来控制粒子的变异概率。同时,构造了比较直观的适应度函数。粒子群算法中适应度函数至关重要,特别在本文中适应度函数不仅直接影响交叉算子对粒子的操作而且决定着变异操作,这样适应度函数将会影响聚类中心点的优化及聚类划分的情况。在本文中所给出的适应度函数主要依据类内总的离散度,即通过类内尽量紧凑、类间尽量松散的原则来构建。
　　(3)将改进后的粒子群算法与K-means聚类算法融合。给出了把粒子群优化算法引入到K-means算法中去的粒子的编码方案和算法流程。通过两种算法的结合改善K-means算法对初始聚类中心选择敏感等问题。
　　文章最后将基于交叉变异算子的自适应粒子群聚类算法应用到UCI学习型数据库中,并通过将该文提出的聚类方法与K-means聚类算法、基于遗传算法的聚类算法、基于粒子群算法的聚类算法作比较,从实验结果可以看出,本文中提出的聚类算法较上述三种算法拥有更好的适应度值和分类正确率并且算法更加稳定,因此,本文的方法改善了K-means聚类算法对初始聚类中心敏感和容易陷入局部最优的缺陷。

目录

封面

声明

中文摘要

英文摘要

目录

第1 章 引言

1.1 研究背景和意义

1.2 国内外研究现状

1.3 研究内容及组织结构

第2章 数据挖掘中传统的聚类分析方法

2.1 数据挖掘概述

2.2 类分析基础知识

2.3 K-means算法

2.4 本章小结

第3章 基于交叉变异算子的自适应粒子群聚类算法

3.1 群智能优化算法

3.2 提出的自适应惯性权重

3.3 改进的交叉变异策略

3.4 基于交叉变异算子的自适应粒子群聚类算法

3.5 本章小结

第4章 基于交叉变异算子的自适应粒子群聚类算法在UCI数据库中的应用

4.1 UCI数据库实验数据集描述

4.2 结果评价标准

4.3 实验环境以及实验结果分析

4.4 本章小结

第5章 总结与展望

5.1 总结

5.2 展望

参考文献

致谢

附录A 攻读硕士学位期间录用的论文