基于划分和密度的聚类算法研究

论文摘要

近年来随着信息产业的迅速发展,数据挖掘得到了广泛的应用。数据挖掘主要包括关联分析,分类,聚类等应用。聚类是数据挖掘的一个重要研究方向。传统的聚类算法包括划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。聚类可以有效处理大量复杂没有类标志的数据集,广泛应用于金融业,生物学,天文学等多个领域。本文首先介绍了数据挖掘的相关概念,然后详细介绍了传统的聚类算法,划分聚类和密度聚类比较常用,但是传统的聚类算法本身存在许多问题,比如容易受数据输入顺序影响以及孤立点影响等,降低了聚类的质量。所以本文主要对K-Means算法和DBSCAN算法进行分析和研究,提出改进思想,从而有效的提高算法质量。K-Means算法是一种经典的聚类算法,有很多优点,也存在许多不足。比如初始聚类数K要事先指定,初始聚类中心选择存在随机性,算法容易生成局部最优解,受孤立点的影响很大等。本文主要针对K-Means算法初始聚类中心的选择以及孤立点问题加以改进,首先计算所有数据对象之间的距离,根据距离和的思想排除孤立点的影响,然后提出了一种新的初始聚类中心选择方法,并通过实验比较了改进算法与原算法的优劣。实验表明,改进算法受孤立点的影响明显降低,而且聚类结果更接近实际数据分布。DBSCAN算法是一种基于密度的聚类算法,可以在带有噪声的环境下发现任意形状的类。但是算法对输入参数Eps敏感,DBSCAN由于采用全局Eps值,所以在数据密度不均匀和类间距离相差比较大的情况下,聚类质量会受到很大影响。本文主要针对算法输入参数Eps以及数据密度不均匀问题加以改进,提出了一种新的数据分区方法,通过对k-dist图纵坐标距离值单维度聚类,然后对比横坐标实现分区,使每个分区的数据尽可能均匀。实验证明,改进算法明显缓解了全局Eps导致的聚类质量恶化问题,聚类结果更加准确。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 课题背景及研究意义
• 1.2 国内外研究现状
• 1.3 论文主要内容
• 第二章 数据挖掘简介
• 2.1 数据挖掘介绍
• 2.2 数据挖掘的任务
• 2.3 数据挖掘流程
• 2.4 数据挖掘的方法
• 2.5 数据挖掘的分类
• 2.6 数据挖掘存在的问题
• 第三章 聚类分析
• 3.1 聚类分析简介
• 3.2 聚类分析的数据类型和相异度度量方法
• 3.2.1 聚类分析的数据类型
• 3.2.2 聚类分析的相异度度量方法
• 3.3 聚类准则函数
• 3.4 聚类算法分类
• 3.5 聚类算法的要求
• 第四章 K-Means算法研究
• 4.1 K-Means算法
• 4.2 K-Means算法的优缺点
• 4.3 改进的K-Means算法
• 4.3.1 改进算法基本思想
• 4.3.2 初始聚类中心的选择
• 4.3.3 改进算法具体流程
• 4.4 实验分析
• 4.4.1 随机数据
• 4.4.2 标准数据
• 第五章 DBSCAN算法研究
• 5.1 DBSCAN算法
• 5.1.1 DBSCAN算法定义
• 5.1.2 DBSCAN算法过程
• 5.2 DBSCAN算法的优缺点
• 5.3 改进的DBSCAN算法
• 5.4 实验分析
• 5.4.1 一般数据
• 5.4.2 环绕型数据
• 第六章 总结与展望
• 参考文献
• 附录A 图目录
• 附录B 表目录
• Appendix A: Figure Index
• Appendix B: Table Index
• 致谢
• 攻读硕士学位期间发表的论文