摘要
聚类分析是数据挖掘领域一个重要研究方向，在模式识别、图像处理等领域均有广泛应用，迄今已提出许多相关算法。在介绍几种具有代表性的聚类算法后，我们主要探讨聚类算法DBSCAN（Density-Based Spatial Clustering of Application with Noise），它是一个典型的基于密度的聚类算法，并已得到广泛应用。 现实世界的聚类分析应用，有很多是基于二维空间的，因此本文主要探讨DBSCAN 在二维空间上的实现，主要集中在DBSCAN的理论分析、二维空间上的算法效率改进，并分别从理论和实验结果证明了改进的效果。本文首先介绍数据挖掘的目的意义及现状，阐述聚类算法在数据挖掘中的地位和作用，而后对DBSCAN进行详尽的理论分析。DBSCAN在二维空间上有多种实现方式，其中需权衡的是基础数据结构如何建立，如何提高其效率。该数据结构主要用于表示数据点集的空间分布状况，从而为聚类操作提供有效的支持。综合各方面评估，我们选择相对简单的邻接表作基础数据结构，并以此为出发点对算法进行改进，以取得较高的时间和空间效率。 在不同的数据源（人工合成和随机生成）上，通过对二维空间上原DBSCAN和改进后的DBSCAN进行测试和对比，结果表明，算法实现是成功的，具有良好的可伸缩性，可发现任意形状的聚类，处理噪声数
据的能力强，且具有较强的可解释性和可用性。
关键词：数据挖掘，聚类算法，DBSCAN，二维空间
I
Abstract
As an important research field in data mining, clustering analysis is a promising application in pattern recognition, image processing, etc. And people have developed various clustering algorithms. After the introduction of several representative algorithms, we probe into DBSCAN（Density-Based Spatial Clustering of Application with Noise), which is an outstanding clustering algorithm based on density and is well used in many applications.
There have been tremendous applications upon planar space, so we try to implement DBSCAN upon it. The theoretical analysis, high performance implementation upon the planar space and the testing of algorithm improvement forms the principal part of this thesis. First of all, we would introduce the purpose, meaning and recent development of data mining, expatiate the status and function of clustering analysis in this field. Later, we would analyse the density based DBSCAN consi
derately on the theory level. The implementation of DBSCAN has different choices upon planar space, and one important thing is to select the appropriate fundamental data structure in order to enhance the efficency of the algorithm. The aim of the data structure is to represent the spatial distribution of the data points, so it should support the clustering effectively. Considerately, we select the adjacency list, which is a simple data structure, as the fundamental data structure. And we would improve the DBSCAN algorithm base on it in order to make spatiotemporal efficiency better.
Upon different data sets (synthetical data sets and randomly generated data sets), we implement both the original DBSCAN algorithm and improved DBSCAN algorithm, and tested them in different aspects. The experiment results proved the improved algorithm is successful. No matter in the aspects of scalability, the ability to find clusters of any shape, the ability to deal with noise, and the ability of explanation and implementation.
Key words:data mining, clustering analysis, DBSCAN，planar space
II
目录
摘要.....................................................................................................................................II 1绪论.. (1)
1.1 课题背景和意义 (1)
1.2国内外概况 (3)
1.3 DBSCAN在二维空间上的实现 (5)
2DBSCAN算法的理论分析 (10)
2.1DBSCAN算法模型 (10)
2.2DBSCAN算法模型在理论层次上设计实现 (12)
3DBSCAN算法的具体实现 (16)
绿体育
3.1体现数据点集相互联系的数据结构的建立 (16)
3.2在该数据结构上的聚类的实施过程 (20)
钛钢复合板3.3时间复杂度和空间复杂度的理论分析 (21)
4实现过程中涉及到的关键问题及其解决 (23)
4.1与数据库的底层连接及其数据交换 (23)
4.2程序实际运行时间的精确测量 (25)
5实验分析 (26)胡和生简介
5.1准确度分析 (26)
5.2参数敏感性分析 (30)
5.3可扩展性分析 (37)
6总结 (45)
致谢...................................................................................................错误！未定义书签。参考文献 (46)
III
1绪论
数据挖掘是近年来很多领域竞相研究的一个热点领域，而聚类分析是数据挖掘的一个研究分支。为了研究基于聚类分析的数据挖掘算法，有必要首先对数据挖掘做一个大体上的介绍。
1.1 课题背景和意义
近几十年来，人们利用信息技术生产和搜集数据的能力以惊人的速度在增长，千千万万的数据库被用于商业管理、政府办公、科学研究以及工程开发等等。与此同时随着各个机构内部局域网的建立和Internet的飞速发展，人们已经被铺天盖地的信息所淹没。于是一个新的问题和挑战被提了出来：在这被称为信息爆炸的的时代，信息过量几乎成为人人需要面对的问题。如何才能使人们不在数据的海洋中迷失并且能够识别海量数据背后隐藏的重要信息？这就迫切要求能够对海量数据进行更高层次的分析。而目前的数据库系统虽然可以高效地实现数据的录入、查询、统计等功能，但却没有发现数据中存在的关系和规则的能力，也无法根据现有的数据预测未来的发展方向。由于缺乏挖掘数据背后隐藏的知识的能力，导致了现在所谓的“数据爆炸但知识贫乏”的现象。[1-2]需求是创新之母，正是在这种情形下，数据挖掘技术应运而生。所以说，数据挖掘是信息技术自然演化的结果。 数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。
何谓知识？从广义的角度上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式
、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至可以是分布在网络上的异构型数据。发
1
现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理、查询优化、决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉性学科，涉及到人工智能、数据库、统计学、机器学习、知识获取、数据可视化、高性能计算等多个领域。它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持上来。
抚州地质学院
极速互联和数据挖掘同时出现或交互使用的还有另外一个名词是数据库中的知识发现（Knowledge Discovery in Database，KDD），一般把知识发现描述为数据库中获取正确、新颖、有潜在应用价值和最终可理解的模式的处理过程。而普遍认为数据挖掘是KDD的一个最关键的步骤，同时也是它技术难点所在。如图1—1 数据挖掘是KDD中的关键步骤。因为数据挖掘算法的好坏将直接影响到KDD所发现知识的准确性，而且目前KDD 研究大部分集中在数据挖掘算法和应用的技术上，因此人们往往不严格区分数据挖掘和数据库中的知识发现。一般在科研领域中称为KDD，而在工程领域则称为数据挖掘。
图 1—1 数据挖掘是KDD中的关键步骤
数据挖掘从一开始就是面向应用的。它不仅是面向特定数据库的简单检索查询或调
2五章一簿
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议