划分聚类与基于密度聚类算法的改进方法研究

摘要

数据挖掘就是从大量的、不完全的、有噪音的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。聚类分析是数据挖掘领域中重要的研究课题，用于发现大规模数据集中未知的对象类。因此，聚类算法的研究具有重要的意义和广阔的前景。本文针对传统K-means聚类算法和基于密度聚类算法进行了重点研究并对所存在的问题提出了改进算法。 K-means聚类算法在数据挖掘领域具有非常重要的应用价值。但随着应用领域的拓展和新的问题需求，K-means本身存在的局限越来越突出。首先，随机选取的初始值可能会导致不同的聚类结果，甚至会造成无解。其次，K-means算法采用了典型的爬山搜索方法，易于陷入局部最优。本文针对K-means聚类算法存在的缺陷提出了KSNN聚类算法。KSNN在数据集中搜索中心点，依据中心点查找数据集个数，为K-means聚类提供参数。有效克服了K-means需要人工设定聚类个数的问题，同时具有较好的全局收敛性。其次，为了解决数据集密度分布不均匀等实际应用问题，本文改进了基于密度的聚类算法，提出了CABONW聚类算法。CABONW首先利用最近邻居节点的方法构建出数据集中节点间的自然链接关系，然后建立节点间优先级，并将其用于对数据节点的有效关系进行排序，生成顺序表。最后，通过对顺序表的深度优先搜索生成最终的簇。通过与DBSCAN、OPTICS等基于密度聚类算法的对比实验证明，CABONW很好地解决了密度分布不均匀的数据集的处理，执行效率优于DBSCAN和OPTICS等基于密度的聚类算法。最后，本文设计了聚类分析系统原型，并将KSNN和CABONW等聚类算法加入到系统中。此原型系统可用于教学对比和实际数据集的分析，具有实际应用价值。 通过理论分析和实验结果证明，KSNN和CABONW能够很好的解决K-means聚类算法和基于密度聚类算法所存在的缺陷，并且在聚类分析系统原型中得到了验证。

目录

文摘

英文文摘

声明

1绪论

1.1课题研究背景和意义

1.2国内外研究现状

1.3论文组织结构

2聚类分析

2.1基本概论

2.1.1聚类分析定义

2.1.2聚类分析的工作流程

2.2聚类分析中的数据预处理

2.2.1数据结构

2.2.2差异度测量方法

2.2.3数据预处理方式

2.2.4聚类算法选择准则

2.3聚类分析算法

2.4聚类分析算法的评价

2.5聚类分析算法的特性

2.6本章小结

3基于最近共享邻居节点的多中心聚类算法

3.1 K-means聚类算法及其改进

3.1.1 K-means算法的基本思想

3.1.2 K-means算法的数学描述

3.1.3 K-means算法的处理流程

3.1.4 K-means算法的复杂度分析

3.1.5 K-means算法的局限

3.2基于最近共享邻居节点的多中心聚类算法(KSNN)

3.2.1最近共享邻居节点算法

3.2.2相关定义

3.2.3算法描述

3.2.4复杂度分析

3.2.5数学描述

3.3实验验证

3.3.1实验设置

3.3.2实验结果

3.3.3结果分析

3.4本章小结

4基于节点优先级的聚类算法(CABONW)

4.1基于密度的聚类算法

4.1.1基于密度算法的基本思想

4.1.2典型基于密度的算法

4.1.3基于密度算法存在的缺陷

4.2基于节点优先级的聚类算法

4.2.1节点间关系建立

4.2.2数据集排序

4.2.3搜索顺序表

4.3实验

4.3.1实验设置

4.3.2实验结果

4.3.3结果分析

4.4本章小结

5聚类分析系统的设计与实现

5.1系统分析

5.2系统设计

5.3系统功能实现

5.3.1系统类图分析

5.3.2系统功能分析

5.4系统应用

5.5本章小结

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢