K均值算法中初始聚类中心的确定问题研究

摘要

聚类方法是最重要的数据挖掘方法之一，K-means更是因其简洁有效的特点成为用途最广的聚类算法之一。然而，该算法的表现高度依赖于初始聚类中心的选取。而如果初始聚类中心选取不当，则很容易陷入局部最优解而造成聚类效果不佳。基于此，国内外许多学者提出了诸多改进方法，但其中大多数方法都不能动态适应不同特点的数据集。事实上，现实中的数据集具有各自不同的特点。因此，提出一种具有自适应性的初始聚类中心选取方法具有很重要的意义。本文根据目前的研究现状，主要进行了以下工作： (1)以往较多的初始聚类中心选取方法中都对数据点密度给出了定义，但其定义方法使得数据点密度具有较小的区分度。针对此问题，本文提出了一种基于邻域模型的密度定义方法，该方法可以有效地增加数据点密度的区分度。 (2)初始聚类中心的选取对于K-means算法最终的聚类效果起着决定性作用。为此，大量文献都提出了针对此问题的解决方法，但这些方法往往只在部分数据集上取得良好的效果，而不具有动态适应性。真实世界中的数据集特点各异，提出一种能够动态适应不同特点数据集的初始聚类中心选取方法具有很重要的意义。为此，本文提出了一种新的距离度量——混合距离，并基于混合距离模型提出了一种带有参数λ的初始聚类中心选取方法。实验结果表明，该方法较以往的初始聚类中心选取方法更能有效地提高K-means聚类精度。 (3)在参数λ的调整下，聚类结果具有若干种，但在正确类标未知的情况下去确定哪种为最佳聚类结果值得进一步探讨。为此，本文提出了一种新的基于邻点模型的内部聚类评价指标CVN。我们运用聚类指标CVN去确定最佳的聚类结果，其有效性优于应用较为广泛的其他几种内部聚类评价指标。

目录

第一章 绪论

1.1 研究的背景与意义

1.2 国内外研究现状

1.3 本文的主要工作

1.4 文章内容安排

第二章 聚类分析相关理论

2.1 聚类的基本概念

2.2 相似性度量

2.3 聚类评价指标

2.4 本章小结

第三章 常用聚类算法

3.1 聚类算法的分类

3.2 K-means聚类算法

3.3 本章小结

第四章 常见的K-means初始聚类中心的改进方法

4.1 最大最小距离算法

4.2 K-means++算法

4.3 CCIA算法

4.4 Kd-tree算法

4.5 FSDP算法

4.6 本章小结

第五章 基于混合距离的K-means初始聚类中心算法

5.1 数据点密度的定义

5.2 混合距离模型

5.3 基于混合距离的初始聚类中心选取算法

5.4 混合距离模型实验结果与分析

5.5 本章小结

第六章 内部聚类评价指标CVN

6.1 内部聚类评价指标CVNN的分析

6.2 内部聚类评价指标CVN

6.3 内部聚类评价指标CVN实验结果与分析

6.4 本章小结

第七章 全文总结与展望

7.1 全文工作总结

7.2 研究展望

参考文献

致谢

攻读硕士学位期间的相关成果