聚类分析在许多科学领域发挥着重要作用,聚类算法和聚类验证是聚类分析的两个基本要素。在聚类分析之前,聚簇的数量是聚类算法的基本参数。在聚类分析之后,对聚类结果的有效性进行评估。而在整个过程中最佳聚类数的合理选择对形成正确的聚类结果有着十分重要的影响。然而,聚类分析属于无监督学习方法,这一特性使其在应用中很难获取具体数据集的最佳聚类数。作为一种度量聚类性能和确定聚类数的有效方法,聚类有效性指标在聚类分析的过程中就显得尤为重要。本文主要工作是在改进的聚类算法的同时对聚类有效性指标进行研究,并在此基础上针对一些不足之处提出了新的聚类有效性指标。新算法和新指标都比较适合处理重叠数据,改进了之前一些指标和算法对重叠数据无法处理的不足。具体工作内容如下:(1)本文主要对不同类型的聚类算法进行了研究和分析并提出了一种新的聚类算法。本文共对其中12种聚类算法进行了分析。基于对12种不同类别聚类算法的研究,总结了不同类别的算法都存在各自的优点和缺陷。着重对K-means算法进行了介绍,因为新算法是利用网格划分方法对K-means算法做出的改进。新算法不仅克服了K-means算法的缺陷还可以有效的处理重叠数据集。(2)文章中着重对13种聚类有效性指标进行研究,这13种指标被分为两类进行讨论分析。通过分析以及结合大量的相关文献总结可知无论是外部有效性指标还是内部有效性指标对于数据结构的多样性以及重叠度方面都存在不足。(3)本文主要提出一种新的聚类有效性指标,新指标是一种适用于重叠数据的指标——WCH指标。新的聚类有效性指标是由聚簇内紧密度、聚簇间分离度以及聚簇间重叠度三部分构成的。新指标的提出不仅考虑到了大部分指标考虑到的聚簇内紧密度和聚簇间分离度的问题还在此基础之上加入了数据重叠度对聚类结果判断的因素。本文并用数学方法分类讨论、归纳总结将数据重叠度表示出来。(4)本文针对新指标性能的检测做了大量的对比实验。从众多指标中选择了比较经典的有代表性的指标DI指标,DBI指标,I指标和COP指标与新的聚类有效性指标基于新聚类算法对不同类型数据集的聚类结果的判断做了对比试验。其中,这些不同类型的数据集其中包括5个模拟数据集和3个真实数据集,有着不同的维数,不同的空间分布,不同的重叠度和不同的规模等。用这些对比实验证明新指标的优越性。大量对比实验的结果表明:新的聚类有效性指标——WCH指标能够对不同维数,不同规模,不同形状等不同的数据集特别是不同重叠度的数据集的聚类结果做出高效准确的判断。