DBSCAN聚类算法

简介

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法。该算法通过对空间中的密度区域进行聚类，将高密度区域相互连接的区域划分为同一类，从而达到将数据集划分为若干个聚类的目的。

原理

DBSCAN 算法的基本思想是：对于给定的数据集，从任意一个样本点出发，通过搜索其邻域内的样本点，判断是否存在核心点（即密度达到阈值的点）或边界点（即位于两个不同密度的边界上的点），将核心点与邻域内的点相连，形成一条路径，并将路径上的所有点划分为同一类。通过不断扩展核心点和边界点的集合，最终将整个数据集划分为若干个聚类。

核心概念

DBSCAN 算法中有两个重要参数：Eps 和 MmPtS。Eps 是定义密度时的邻域半径，MmPts 为定义核心点时的阈值。

数据点可分为核心点、边界点和噪音点：

• 核心点：如果一个对象在其半径 Eps 内含有超过 MmPts 数目的点，则该对象为核心点。
• 边界点：如果一个对象在其半径 Eps 内含有点的数量小于 MinPts，但是该对象落在核心点的邻域内，则该对象为边界点。
• 噪音点：如果一个对象既不是核心点也不是边界点，则该对象为噪音点。

Eps 邻域：点的距离小于等于Eps的所有点的集合。
直接密度可达：如果点 p 在核心点 q 的 Eps 邻域内，则称数据对象 p 从数据对象 q 出发是直接密度可达的。
密度可达：如果存在数据对象链 $p_1, p_2, p_3, ..., p_{i+1}$，其中 $p_{i+1}$ 是从 $p_i$ 关于 Eps 和 MinPts 直接密度可达的，则数据对象 $p_n$ 是从数据对象 $p_1$ 密度可达的。
密度相连：对于数据对象 p 和数据对象 q ，如果存在核心对象样本 o ，使数据对象 p 和数据对象 q 均从 o 密度可达，则称 p 和 q 密度相连，显然密度相连具有对称性。
密度聚类簇：由一个核心点和与其密度可达的所有对象构成一个密度聚类簇。

算法描述

DBSCAN 算法对簇的定义很简单，由密度可达关系导出的最大密度相连的样本集合，即为最终聚类的一个簇。

DBSCAN 算法的簇里面可以有一个或者多个核心点。如果只有一个核心点，则簇里其他的非核心点样本都在这个核心点的 Eps 邻域里。如果有多个核心点，则簇里的任意一个核心点的 Eps 邻域中一定有一个其他的核心点，否则这两个核心点无法密度可达。这些核心点的 Eps 邻域里所有的样本的集合组成一个 DBSCAN 聚类簇。

DBSCAN算法的描述如下。

输入：数据集，邻域半径 Eps，邻域中数据对象数目阈值 MinPts;
输出：密度联通簇。
处理流程如下。

1. 从数据集中任意选取一个数据对象点 p；
2. 如果对于参数 Eps 和 MinPts，所选取的数据对象点 p 为核心点，则找出所有从 p 密度可达的数据对象点，形成一个簇；
3. 如果选取的数据对象点 p 是边缘点，选取另一个数据对象点；
4. 重复2、3步，直到所有点被处理。

DBSCAN 算法的计算复杂的度为 $O(n^2)$，n 为数据对象的数目。这种算法对于输入参数 Eps 和 MinPts 是敏感的。