聚类(DBSCAN)算法原理

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。下面我们就对DBSCAN算法的原理做一个总结。

基于密度的聚类算法主要的目标是寻找被低密度区域分离的高密度区域。与基于距离的聚类算法不同的是，基于距离的聚类算法的聚类结果是球状的簇，而基于密度的聚类算法可以发现任意形状的聚类，这对于带有噪音点的数据起着重要的作用。

密度聚类原理

DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一种典型的基于密度的聚类算法，在DBSCAN算法中将数据点分为一下三类：

• 核心点。在半径Eps内含有超过MinPts数目的点
• 边界点。在半径Eps内点的数量小于MinPts，但是落在核心点的邻域内
• 噪音点。既不是核心点也不是边界点的点

在这里有两个量，一个是半径Eps，另一个是指定的数目MinPts。

• Eps邻域。简单来讲就是与点的距离小于等于Eps的所有的点的集合，可以表示为。
• 直接密度可达。如果在核心对象的Eps邻域内，则称对象从对象出发是直接密度可达的。
• 密度可达。对于对象链：，是从关于Eps和MinPts直接密度可达的，则对象是从对象关于Eps和MinPts密度可达的。

DBSCAN算法优点：

• 与K-means算法比起来，不需要预先输入划分的聚类个数。
• 聚类形成的簇的形状可以是任意的。
• 可以在需要的时候输入过滤噪声的参数。

DBSCAN算法的聚类过程：

1. 初始状态，给出一个数据集D，并设置半径ε和MinPts，将D中的所有对象标记为"unvisited"（未被访问）
2. 随机从D中选取一个未被访问的对象p，并标记为"visited"（已被访问），检查p的ε-邻域内是否至少包含MinPts个对象（即p是否是核心对象），若不是，则将p标记为噪声点，否则，为p创建一个新的簇C，把p的ε-邻域中所有对象放入候选集合N中，并迭代的将N中不属于其它簇的对象加入到新簇C中，在这个过程中，将N中的"unvisited"的对象q标记为"visited"，若q的ε-邻域是否至少包含MinPts个对象，则将q的ε-邻域中所有的对象加入到C中，直到C不再扩大，N为空的时候，此时簇C完成聚类，并输出。
3. 继续从D中随机选取未被访问的对象s，同样使用（2）中的聚类方法，直到对象集D中所有对象都被访问。

下面是该算法的伪代码：

算法：DBSCAN，一种基于密度的聚类算法
输入：
	D:包含若干个对象的数据集
	ε:半径
	MinPts:密度邻域阈值
输出：簇的集合
方法：
	1.标记D中所有的对象为"unvisited";
	2.Do
	3.随机选择一个"unvisited"对象p;
	4.标记p为"visited";
	5.If p的ε-邻域至少含有MinPts个对象
	6.   创建一个新的簇C;
	7.   令N为p的ε-邻域对象的集合;
	8.   For N中的每个对象q
	9.       If q是"unvisited"
	10.          则标记q为"visited";
	11.          If q是核心对象
	12.              则将q的ε-邻域中的所有对象集合加到N中;
	13.          If q不属于其它簇
	14               则将q加入到簇C中;
	15.  End For;
	16.  输出C
	17.Else 标记p为噪声点
	18.Until D中所以对象都是"visited"

： » 聚类(DBSCAN)算法原理