论文总字数：25862字

摘 要

聚类分析是数据挖掘研究领域的重点课题之一，研究者们一致致力于寻找高效可靠的分析方法及算法思路。这一毕业设计课题——基于数据点密度的聚类算法研究，是受到Alex Rodriguez 和 Alessandro Laio发表在Science上的一篇有关无监督分聚类的论文，《Clustering by fast search and find of density peaks》的启发而来。原作者提出了一种新的聚类思路，尽管已经在原文中的一些分析案例中证明了其有效性，但这一算法还是受到了很多质疑。正因为其有亮眼的性能表现，却没有受到广泛的认可和使用，这一课题希望通过编程的方式实现这一算法，验证其在处理其他数据时的表现，与其他成熟的聚类算法进行对比，通过学习和讨论原作者的思想，加深对聚类分析这一领域的理解和认识。研究方法：本课题将使用K-medoids算法、DBSCAN算法和新算法处理一组1-10的字迹数据，该数据保存在5620x64的矩阵中，另有一维标签保存笔迹对应的正确数字，用于计算精确度。通过精确度的对比确定该算法的有效性，并依靠实验过程和结果对这一新算法进行分析和讨论。实验结果：新的聚类算法确实有出色的表现，相比对比的两种算法准确率有明显提高。说明这确实是一种有效的聚类算法思路。结论：虽然证实了新算法在聚类结果上的可靠性，但是这一算法也有很多不足，这些缺点主要反映在算法不够“自动”上，参数的选取和簇中心的选取一定程度上还是依靠人的估算，而不能完全由系统实现，这无异对算法的精度带来了不好的影响。所以说，这一新的算法思路（或者说新的选取簇的方法）是非常有建设性的，但在算法的具体实现上还不够成熟，需要进一步的讨论和完善。

关键词：聚类算法；K-means算法；K-medoids算法；DBSCAN；基于密度的聚类算法

Abstract

Cluster analysis is a significant research field of data mining. All the researchers in this field desire a more reliable and efficient method. My research is inspired by the article Clustering by fast search and find of density peaks, which is published in Science. This article is mainly about unsupervised learning technique proposes a brand new method for cluster analysis. , many people doubt effect of the new algorithm, even the authors have used some cases to support their algorithm. Since the algorithm performs well in many cases but has not be widely accepted, I want to realize the algorithm by programing and test it. It could be a great chance to learn more about cluster analysis. Approach: In this research, three different algorithms (K-medoids, DBSCAN and the new algorithm) will be used to process a same set of data. The 5620x20 data contains information about handwriting. By calculating their accuracy and then comparing them with each other, the advantages and disadvantages of the new method could be found. Results: According to the finally computed accuracy, the new algorithm was proved to be the best among the three algorithms. Conclusion:

The new algorithm finally achieved the highest accuracy, however, it still has several drawbacks. The drawbacks mainly reflect in the terms that the algorithm is not ‘automatic’ enough, we still have to estimate parameter and the number of clusters, since system could not automatically calculate or detect them. These subjective elements badly influence the performance of the algorithm. Therefore, on one hand, the new algorithm is creative and effective, on the other hand, it is not perfect and need more discussion.

Keyword: cluster algorithm; K-means clustering; K-medoids clustering; DBSCAN; density-based clustering

目录

摘 要 3

Abstract 4

第一章 绪论 1

1.1本课题研究的背景和意义 1

1.2聚类分析概述 1

1.3用于聚类分析的技术 3

1.4本文的结构安排 4

第二章 K-means算法 6

2.1 K-means算法基本理论 6

2.2 K-means算法的收敛性 6

2.3由K-means引出的一些关键概念 7

第三章 K-medoids算法 8

3.1 K-medoids算法基本理论 8

3.2K-medoids算法的实现 8

3.3计算结果 9

第四章 DBSCAN算法 11

4.1 DBSCAN算法基本理论 11

4.2 DBSCAN算法复杂度分析 12

4.3 确定参数和MinPts 12

4.4DBSCAN算法的实现 13

4.5DBSCAN算法计算结果 15

第五章 基于快速搜索和密度峰值的聚类算法 17

5.1簇中心的选取 17

5.1.1局部密度的计算 17

5.1.2距离的计算 18

5.1.3决策图 18

5.2可靠性检测 20

5.3参数的选取 22

5.3.1选取原则 22

5.3.2比较与结论 24

5.4算法的具体实现 25

5.5计算结果 26

5.6结果分析 27

第六章 结论 28

参考文献reference 29

第一章 绪论

本节主要对聚类算法这一概念进行了总体上的叙述，介绍了其分类和应用。最后还对全文的结构进行了概括。

1.1本课题研究的背景和意义

聚类分析最初是1932年在人类学研究中由Driver和Kroeber提出的，在相近的时期，心理学家Zubin和Robert Tryon也分别涉及了这一概念。后来因为Cattell在1943年开始在个性心理学的试验理论分类中使用这一概念，这种理论才开始广泛为人们所知。

聚类分析研究有几十年的历史，一直以来其重要性及与其他研究方向的交叉特性得到人们的肯定。聚类分析的目的是将一组对象分组，使得同一组（在聚类算法中被称为cluster,本文中统一称为簇）中的对象之间相比不同组中对象之间具有更高的相似性。这是探索性的数据挖的主要任务，也是一种统计数据分析的常用技术。这一方法在众多领域都被运用，包括机器学习，信息检索，模式识别，图形分析，数据压缩，生物信息学等等。

剩余内容已隐藏，请支付后下载全文，论文总字数：25862字