2024年3月15日发(作者：)

聚类算法DBSCAN在二维空间上的实现

摘 要

聚类分析是数据挖掘领域一个重要研究方向，在模式识别、图像处理等领域均有广

泛应用，迄今已提出许多相关算法。在介绍几种具有代表性的聚类算法后，我们主要探

讨聚类算法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 considerately 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