DBSCAN原理及其实现

相比其他的聚类方法，基于密度的聚类方法可以在有噪音的数据中发现各种形状和各种大小的簇。

DBSCAN（Ester, 1996）是该类方法中最典型的代表算法之一（DBSCAN获得2014 SIGKDD Test of Time Award）。其核心思想就是先发现密度较高的点，然后把相近的高密度点逐步都连成一片，进而生成各种簇。算法实现上就是，对每个数据点为圆心，以eps为半径画个圈（称为邻域eps-neigbourhood），然后数有多少个点在这个圈内，这个数就是该点密度值。然后我们可以选取一个密度阈值MinPts，如圈内点数小于MinPts的圆心点为低密度的点，而大于或等于MinPts的圆心点高密度的点（称为核心点Core point）。如果有一个高密度的点在另一个高密度的点的圈内，我们就把这两个点连接起来，这样我们可以把好多点不断地串联出来。之后，如果有低密度的点也在高密度的点的圈内，把它也连到最近的高密度点上，称之为边界点。这样所有能连到一起的点就成一了个簇，而不在任何高密度点的圈内的低密度点就是异常点。下图展示了DBSCAN的工作原理。

当设置MinPts=4的时候，红点为高密度点，蓝点为异常点，黄点为边界点。红黄点串成一起成了一个簇。

由于DBSCAN是靠不断连接邻域内高密度点来发现簇的，只需要定义邻域大小和密度阈值，因此可以发现不同形状，不同大小的簇。下图展示了一个二维空间的DBSCAN聚类结果。

DBSCAN可以发现2个弧形的簇

DBSCAN算法伪码表达如下：

DBSCAN实现伪码（来源： Han 2011）

发现不同密度的簇

由于DBSCAN使用的是全局的密度阈值MinPts, 因此只能发现密度不少于MinPts的点组成的簇，即很难发现不同密度的簇。其成功与失败的情况举例如下：

左图有三个簇，一个全局密度阈值可以把三个簇分开。但是在右图中，一个阈值无法把三个簇分开，过高的阈值会把C3全部变成异常点，过低的阈值会把C1和C2合并起来。（来源：）

为了解决其发现不同密度的簇，目前已经有很多新的方法被发明出来，比如OPTICS（Ordering points to identify the clustering structure）将邻域点按照密度大小进行排序，再用可视化的方法来发现不同密度的簇，如下图所示。OPTICS必须由其他的算法在可视化的图上查找"山谷"来发现簇，因此其性能直接受这些算法的约束。

OPTICS将数据以密度的形式排序并展示，不同的山谷就是不同密度大小的簇。（来源：）

另外SNN采用一种基于KNN（最近邻）来算相似度的方法来改进DBSCAN。对于每个点，我们在空间内找出离其最近的k个点（称为k近邻点）。两个点之间相似度就是数这两个点共享了多少个k近邻点。如果这两个点没有共享k近邻点或者这两个点都不是对方的k近邻点，那么这两个点相似度就是0。然后我们把DBSCAN里面的距离公式替换成SNN相似度，重新算每个点的邻域和密度，就可以发现不同密度的簇了。SNN的核心就是，把原始的密度计算替换成基于每对点之间共享的邻域的范围，而忽略其真实的密度分布。SNN的缺点就是必须定义最近邻个数k, 而且其性能对k的大小很敏感。下图展示了SNN计算相似度的方法。

i点和j点共享4个近邻点，所以它们相似度为4

2014年Science杂志刊登了一种基于密度峰值的算法DP（Clustering by fast search and find of density peaks），也是采用可视化的方法来帮助查找不同密度的簇。其思想为每个簇都有个最大密度点为簇中心，每个簇中心都吸引并连接其周围密度较低的点，且不同的簇中心点都相对较远。为实现这个思想，它首先计算每个点的密度大小（也是数多少点在邻域eps-neigbourhood内），然后再计算每个点到其最近的且比它密度高的点的距离。这样对每个点我们都有两个属性值，一个是其本身密度值，一个是其到比它密度高的最近点的距离值。对这两个属性我们可以生成一个2维图表（决策图），那么在右上角的几个点就可以代表不同的簇的中心了，即密度高且离其他簇中心较远。然后我们可以把其他的点逐步连接到离其最近的且比它密度高的点，直到最后连到某个簇中心点为止。这样所有共享一个簇中心的点都属于一个簇，而离其他点较远且密度很低的点就是异常点了。由于这个方法是基于相对距离和相对密度来连接点的，所以其可以发现不同密度的簇。DP的缺陷就在于每个簇必须有个最大密度点作为簇中心点，如果一个簇的密度分布均与或者一个簇有多个密度高的点，其就会把某些簇分开成几个子簇。另外DP需要用户指定有多少个簇，在实际操作的时候需要不断尝试调整。下图展示了一个DP生成的决策图。

左图为5个簇的分布，右图为DP生成的决策图，其右上角5个点就是左图五个簇的中心点。（来源：）

除此之外，还可以用密度比估计（Density-ratio estimation）来克服DBSCAN无法发现不同密度簇的缺陷。密度比的核心思想就是对每个点，计算其密度与其邻域密度的比率，然后用密度比计算替换DBSCAN的密度计算来发现核心点Core point，而其他过程和DBSCAN不变。这样一来，每个局部高密度点就会被选出来作为核心点，从而发现不同密度的簇。基于这个思想，我们还可以把原始数据按其密度分布进行标准化（ReScale），即把密度高的区域进行扩张，密度低的区域继续收缩。这样以来，不同密度的簇就可以变成密度相近的簇了，我们再在标准化后的数据上直接跑DBSCAN就搞定了。这种方法需要用户设置邻域范围来计算密度比，下图展示了标准化前后的数据分布对比。

不同密度的簇在（ReScale）标准化后，变成密度相近的簇，进而DBSCAN可以用全局阈值发现不同的簇

源码下载 (Matlab)

DP:

DBSCAN, SNN, OPTICS 和 Density-ratio: