聚类算法--DBSCAN算法

一、DBSCAN算法

  1. 简介

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个基于密度的聚类算法。算法把簇看作数据空间中由低密度区域分割开的高密度对象区域;将足够高密度的区域划为簇,可以在有噪音的数据集中发现任意形状的聚类。
  1. 基本概念

在DBSCAN 算法中有两个重要的参数:Eps 和 MinPtS。Eps 是定义密度时的邻域半径,MinPts 为定义核心点时的阈值。

基于中心定义密度的方法可将点分为三类:

(1)核心点:给定用户指定阈值MinPts,如果一个点的给定邻域内的点的数目超过给定阈值MinPts, 那么该点称为核心点。

(2)边界点:边界点不是核心点,但它落在某个核心点的Eps邻域内。

(3)噪声点:噪声点既不是核心点,也不是边界点。

基于密度的簇定义如下:

(1)密度直达:给定一个对象集合D,如果p是在q的邻域内,且q是一个核心对象,则称p从对象q出发是直接密度直达的。

(2)密度可达:如果存在一个对象链 , ,对于

是从关于Eps和MinPts直接密度可达的,则对象p是从对象q关于Eps和MinPts密度可达的。

(3)密度连接:如果对象集D中存在一个对象o,使得对象p和q是从o关于Eps和MinPts密度可达的,那么对象p和q是关于Eps和MinPts密度连接的。

(4)密度可达是密度直达的传递闭包,这种关系非对称的,只有核心对象之间是相互密度直达的。

  1. 算法过程