基于进化规划的聚类算法研究

摘要

随着互联网等现代信息技术的飞速发展，人们必须面对海量的信息，如何对这些信息进行整理、分类和挖掘成为人们日益关心的话题。聚类分析技术作为一种信息处理手段近些年来一直受到人们的关注，而且在机器学习、模式识别，数据挖掘、信息检索等很多领域得到了广泛的研究和应用。 聚类算法主要分为基于划分的聚类算法和基于层次的聚类算法，基于划分的聚类算法是数据挖掘中最常用的算法，K均值算法和模糊C均值聚类算法(FCM)作为两种重要的划分算法在实际中广为应用。但它们都存在三个缺点：类中心个数需要用户预先指定；容易收敛到局部极小值或鞍点；聚类结果受初始类中心影响较大。 为了解决这几个缺点，本文提出了基于进化规划的K均值算法(KEP)和基于进化规划的FCM算法(EPFCM)两个算法。 利用进化规划的全局优化能力，KEP算法避免了K均值算法易陷入局部极值和受初始类中心影响大两个缺陷。实验表明，与K均值算法相比，KEP具有的显著的聚类效果；与基于遗传算法的K均值算法(KGA)相比，KEP具有更快的速度和更优的聚类效果。 在EPFCM算法中，借助聚类有效性指标对聚类结果的评价和进化规划算法的全局优化能力，用户无需预先指定类中心的个数，算法可以搜索到最佳的类中心个数及其对应的最佳聚类结构。 为了加快算法的收敛过程，我们在进化规划的迭代过程中加入了FCM算法的迭代步骤，为了能找到最佳的类中心个数，我们采用Modify算法动态改变类中心个数。 实验表明，EPFCM算法可以有效地得到最佳的类中心个数，聚类结果不受初始类中心影响，并且陷入局部极小的概率较FCM算法大大降低。

目录

文摘

英文文摘

致谢

1 引言

1.1聚类的意义

1.2聚类有效性的评价指标

1.3 自动聚类的意义和现状

1.4进化规划算法

1.5本文的工作

2 聚类算法与聚类有效性

2.1聚类算法

2.1.1聚类算法的分类

2.1.2 K均值聚类算法

2.1.3模糊C均值聚类算法

2.2聚类有效性

2.2.1聚类有效性的意义

2.2.2几种重要的模糊聚类有效性指标

3 进化计算与进化规划算法

3.1进化计算

3.1.1进化计算的基本框架

3.1.2进化计算的特点

3.1.3进化计算的应用

3.2进化规划算法

3.2.1进化规划的组成与主要特点

3.2.2单点变异进化规划算法

4 基于进化规划的聚类算法

4.1基于进化规划的K均值聚类算法

4.2基于进化规划的模糊C均值自动聚类算法

4.2.1自动聚类的研究意义与现状

4.2.2算法的基本思想

4.2.3算法的步骤

5 KEP算法的实验结果与分析

5.1实验数据

5.2实验结果

6 EPFCM算法的实验结果与分析

6.1实验数据

6.2实验结果

6.2.1聚类效果

6.2.2类数的动态变化

6.2.3聚类有效性值的动态变化

6.3算法的性能分析

7 结束语

7.1总结

7.2下一步工作

参考文献

作者简历

独创性声明及学位论文版权使用授权书