2024年5月30日发(作者：)

Dbscan简介

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比

较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连

的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发

现任意形状的聚类。

DBSCAN中的几个定义：

Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；

核心对象：如果给定对象Ε领域内的样本点数大于等于MinPts，则称该对象为核心对

象；

直接密度可达：对于样本集合D，如果样本点q在p的Ε领域内，并且p为核心对象，

那么对象q从对象p直接密度可达。

密度可达：对于样本集合D，给定一串样本点p1,p2….pn，p= p1,q= pn,假如对象

pi从pi-1直接密度可达，那么对象q从对象p密度可达。

密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达

的，那么p和q密度相联。

核心点：在半径Eps之内，数目超过MinPts数目的点称为核心点

边界点：在半径Eps之内，点的数目小于MinPts，但是在Eps之内有核心点，这样

的点称为边界点。

噪声点：不是核心点或边界点的点

可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相

连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。

DBSCAN算法描述:

输入: 包含n个对象的数据库，半径e，最少数目MinPts;

输出:所有生成的簇，达到密度要求。

(1)Repeat

(2)从数据库中抽出一个未处理的点；

(3)IF抽出的点是核心点 THEN 找出所有从该点密度可达的对象，形成一个簇；