学位论文 > 优秀研究生学位论文题录展示

K均值算法初始聚类中心选取相关问题研究

作　者: 李宇泊
导　师: 李秦
学　校: 兰州交通大学
专　业: 计算数学
关键词: K均值算法初始聚类中心密度邻域半径高密度点
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 221次
引　用: 0次
阅　读: 论文下载

内容摘要

聚类分析是数据挖掘的功能之一,是在训练数据不提供类标号的情况下按照最大化类内对象间的相似性、最小化不同类对象之间的相似性的原则聚类和分组数据。目前,存在着大量的聚类算法,K均值算法是应用广泛的聚类算法之一。K均值算法的优点是：算法思想简单;时间复杂度接近线性；对大规模数据的挖掘具有可伸缩性,但是该算法存在如下缺点：对聚类初始值的依赖；聚类个数K需要预先给定；准则函数易陷入局部极小；对离群点敏感等等。本文重点针对K均值算法对初始聚类中心的依赖性,提出了基于密度选取K个初始聚类中心的算法。其主要思想是：在一个数据集合里,高密度区域的数据对象被低密度区域的对象所分割,处于低密度区域的数据对象通常被认为是噪声点。首先根据两个参数(邻域半径ε、高密度点在邻域半径内至少包含数据对象的数目MinPts),划分高低密度点,然后取高密度点集合G中相距最远的K个点作为初始聚类中心。通过在不同数据集(来自UCI数据库)上对两个算法的多次对比实验,验证了基于密度选取K个初始聚类中心的K均值算法比传统的K均值算法聚类结果准确率更高,更稳定。研究进一步给出了基于距离矩阵D确定ε和MinPts参数值的方法。主要思想是：通过距离矩阵计算每个对象距离的中间值(median),然后取这些中间值的平均值作为ε的值。计算每个对象邻域半径e内对象的个数,将这些个数相加,再除以2*n,获得参数MinPts的值,其中n是数据集对象的个数。通过检验聚类结果是否理想或者以文献已给定的经验值作正确性判断依据,两种检验方法的多次实验都验证了计算两个参数值的算法是可用的。

全文目录

摘要  4-5
Abstract  5-8
引言  8-10
1 数据挖掘  10-15
  1.1 数据挖掘的定义和过程  10-11
  1.2 数据挖掘的功能  11-12
  1.3 数据挖掘的数据集  12-14
    1.3.1 结构化数据  12-13
    1.3.2 复杂形式的数据  13-14
  1.4 数据挖掘的研究方向  14-15
2 聚类分析  15-29
  2.1 聚类分析的定义  15
  2.2 聚类分析的过程  15-16
  2.3 聚类分析中的数据类型  16-17
  2.4 相异度  17-21
    2.4.1 区间标度变量描述的对象间的相异度  17-18
    2.4.2 二元变量描述的对象间的相异度  18-19
    2.4.3 分类变量描述的对象间的相异度  19
    2.4.4 序数变量描述的对象间的相异度  19-20
    2.4.5 比例标度变量描述的对象间的相异度  20
    2.4.6 混合类型变量描述的对象间的相异度  20-21
  2.5 聚类算法的分类  21-26
    2.5.1 划分方法(Partitioning Method)  21-23
    2.5.2 层次方法(Hierarchical Method)  23-24
    2.5.3 基于密度的方法(Density-Based Method)  24-26
    2.5.4 基于网格的方法(Grid-Based Method)  26
    2.5.5 基于模型的方法(Model-Based Method)  26
  2.6 聚类有效性评价  26-29
    2.6.1 外部评价法  26-28
    2.6.2 内部评价法  28-29
3 经典的改进K均值算法  29-33
  3.1 PAM算法  29-31
    3.1.1 PAM算法的基本思想  29-30
    3.1.2 PAM算法的基本步骤  30-31
    3.1.3 与K均值算法的比较  31
  3.2 经典k-modes算法  31-33
    3.2.1 经典k-modes算法的基本思想  31-32
    3.2.2 经典k-modes算法的基本步骤  32
    3.2.3 与K均值算法的比较  32-33
4 K均值算法分析  33-35
  4.1 K均值算法的缺点分析  33-34
  4.2 K均值算法对初始聚类中心的依赖性分析  34-35
    4.2.1 K均值算法对初始聚类中心的依赖性分析  34
    4.2.2 实验分析  34-35
5 基于密度的K均值初始聚类中心选取算法  35-53
  5.1 基于密度的K均值初始聚类中心选取算法  35-42
    5.1.1 算法的基本思想  35-36
    5.1.2 算法的步骤  36-42
  5.2 确定邻域半径ε的算法  42-43
    5.2.1 算法的思想  42
    5.2.2 算法的基本步骤  42-43
  5.3 确定参数MinPts的算法  43-44
    5.3.1 算法的基本思想  43
    5.3.2 算法的基本步骤  43-44
  5.4 实验分析  44-53
    5.4.1 确定参数ε、MinPts值的算法实验分析  44-46
    5.4.2 数据集  46-47
    5.4.3 基于密度的初始聚类中心选取算法的实验分析  47-50
    5.4.4 基于密度的初始聚类中心选取算法的MATLAB程序  50-53
结论  53-54
参考文献  54-56
致谢  56-57
附录A 传统K均值算法的MATLAB程序  57-60
攻读学位期间的研究成果  60

K均值算法初始聚类中心选取相关问题研究

内容摘要

全文目录

相似论文