题目：基于粗糙集与遗传算法的聚类算法

随着信息技术的发展，数据挖掘技术得到了广泛的关注。聚类是数据挖掘中的一个重要研究领域，对它的研究有着重要的理论意义和应用价值。目前关于聚类的研究大体分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法以及模糊聚类。K-均值聚类算法是一种基于划分的聚类算法，是一种应用非常广泛的聚类算法，它具有简单、快速，且能够有效地处理大数据集的特点。但是K-均值算法需要事先给定聚类个数K的值，并需要确定K个初始聚类中心。初始聚类中心选取的不同，聚类结果会有很大差异。K-均值算法对初始聚类中心的依赖性导致了其聚类结果的不稳定性，容易陷入局部最优解。
本文针对K-均值聚类算法的聚类结果严重依赖于初始聚类中心，容易陷入局部最优解的缺憾，提出了基于粗糙集的密度加权K-均值聚类新算法，并在对遗传算法和小生境遗传算法进行改进研究的基础上，提出了基于小生境遗传算法的K-均值聚类算法。本文所提出的几个K-均值聚类算法都是企图找到K-均值聚类算法的最佳初始聚类中心，以便K-均值聚类算法的聚类结果能收敛于全局最优解或近似全局最优解，克服以往K-均值聚类算法的聚类结果依赖于初始聚类中心，易于陷入局部最优解的缺憾。
本文的具体研究工作包括以下几个方面：
首先，借助粗糙集理论处理不精确知识的能力，提出一种新的密度加权粗糙K-均值聚类算法。该算法基于数据对象所在区域的样本点密集程度，定义了新的样本密度函数，选择相互距离最远的K个高密度样本点作为初始聚类中心，根据各样本的密度在类均值计算过程中对其赋以不同的权重，得到不受噪音点影响的更合理的质心。克服了现有粗糙K-均值聚类算法的初始中心点随机选取，以及基于密度加权的粗糙K-均值聚类改进算法的样本密度函数定义所存在的缺憾。UCI机器学习数据库的6组数据集，以及随机生成的带有噪音点的人工模拟数据集进行测试，实验结果证明我们的算法具有更好的聚类效果，而且对噪音数据有很强的抗干扰性能。
第二，针对遗传算法存在早熟和收敛速度慢等问题，我们基于低等生物的分裂生殖现象，提出了分裂算子的概念，并将该算子引入到传统遗传算法和自适应遗传算法中，对这两种遗传算法进行改进。一系列多峰函数的实验证明，引入分裂算子后的遗传算法和自适应遗传算法不仅能有效地收敛到全局最优解，而且提高了收敛速度。
第三，针对小生境遗传算法容易产生进化停滞和局部最优性能差等缺陷，我们在小生境遗传算法基础上提出的改进梯度算子的小生境遗传算法和改进梯度算子的自适应小生境遗传算法，Shubert函数的实验测试证明我们的改进梯度算子的小生境遗传算法和改进梯度算子的自适应小生境遗传算法具有更快的收敛速度和更高的求解精度，能快速找到具有多个最优解的多峰函数——Shubert函数的所有最优解。
第四，借助小生境遗传算法的在求解多峰值函数优化问题时，可以找出全部最优解的优点，我们提出两种基于小生境遗传算法的K-均值聚类算法，我们的算法将K-均值聚类问题转化为一个具有K个极值的多峰函数优化问题，利用小生境遗传算法来求解。我们的基于小生境遗传算法的K-均值聚类算法克服了经典K-均值算法对初始中心敏感，易于陷入局部最优解的缺憾。6组UCI机器学习数据库数据集，以及人工随机生成的带有噪音点的模拟数据集实验测试，证明我们提出的两种基于小生境遗传算法的K-均值聚类算法不仅聚类效果好，且对噪音数据具有强的抗干扰性能。