DBSCAN聚类算法

简介

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

主要参数及概念

DBscan算法需要设定两个参数： Ε（邻域距离阈值）和MinPts（邻域密度阈值）。

Ε描述了某一数据的邻域距离阈值，MinPts描述了某一数据的距离为 的邻域中数据点的个数。

对于任意数据点p来说，其是核心点的充要条件是：p的半径为 的邻域中点的总个数值大于或者等于MinPts。

DBscan中的相关概念主要有：

（1） Ε -邻域：对象O的  Ε-邻域是与O为中心，与 Ε为半径的空间。

（2）MinPts（领域密度阀值）：对象的  Ε-邻域的对象数量。

（3）核心对象：O的 Ε -邻域中点的总个数值大于或者等于MinPts。

（4）直接密度可达：p在q的 Ε -邻域中，即可以认为p是从q直接密度可达的。

（5）密度可达：若对于数据 p1,p2….pn，使得p= p1,q= pn ,
且满足pi+1在 pi的 Ε-邻域内，则 p1到 pn是密度可达的。

（6）密度相连：若存在q ，使p1 和p2 都是从q密度可达的，
则p1 ，p2 是密度相连的。

为简单直观地解释这些概念，下面通过简单的数据样例说明。

将相关概念联系图3.4可得出下列结论：

（1）q是从m直接密度可达的；
（2）m从p直接密度可达的；
（3）r和s是从O密度可达的；
（4）O，r和s是密度相连的。

算法流程

输入为原始数据集， 和MinPts；输出为聚类结果及噪声数据。

（1）从原始数据集中找出一个核心点d；
（2）找出d点 -邻域中存在的核心点，并找出与这些核心点密度相连的点；
（3）通过密度相连产生最终结果；
（4）重新扫描数据集，寻找遗漏的核心点，重复步骤2和3，
直到数据集中任一对象为“已处理”。

由上述步骤可知，DBscan找出了原始数据集中的一组密度相连的数据，没有被划分到任一聚类的数据就是噪声点。