基本原理

DBSCAN算法是比较经典的聚类算法了，除了sklearn之外，open3d这种常用的点云模块也提供了DBSCAN算法的实现，例如Open3d数据滤波和点云分割。

和其他聚类算法相比，DBSCAN存在一种去中心化的特性，即不存在一聚类中心，这样做的好处是，在面对不规则的数据时，有着更好的聚类效果。

在DBSCAN算法中，将数据点分为三类：

1. 核心点：若样本$x_i$的$\epsilon$邻域内至少包含了$M$个点，则为核心点
2. 边界点：若样本$x_i$的$\epsilon$邻域内包含的点数小于$M$，但在其他核心点的$\epsilon$邻域内，则为边界点
3. 噪声：既非核心点也非边界点则为噪声

常规的测试数据是体现不出DBSCAN的威力的，为了测试DBSCAN比那种更关注全局数值的算法更优秀，可以采用同心圆作为测试数据。下面对比DBSCAN和KMeans对这种数据的作用。

测试

from sklearn import datasets
from sklearn.cluster import DBSCAN, KMeans
import matplotlib.pyplot as plt
X, y = datasets.make_circles(n_samples=10000, factor=0.5, noise=0.05)
# 此为DBSCAN
dbModel = DBSCAN(eps = 0.1, min_samples = 2).fit(X)
kmModel = KMeans(2).fit(X)

fig = plt.figure()
ax = fig.add_subplot(121)
ax.scatter(X[:,0], X[:,1], c=dbModel.labels_, marker='.')

ax = fig.add_subplot(122)
ax.scatter(X[:,0], X[:,1], c=kmModel.labels_, marker='.')


plt.show()

效果如下，可见DBSCAN将数据按照我们希望的方式进行聚类了。

构造函数

DBSCAN在sklearn中的构造函数为

DBSCAN(eps=0.5, *, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=None)

其各项参数含义如下

• eps： 即前面原理部分提到的$\epsilon$，默认0.5。如果$\epsilon$过大，会导致更多的点会落在核心对象的$\epsilon$-邻域，导致最终得到的聚类簇较少。在上面的案例中，如将eps设为0.5，则无法完成上图那样的聚类。
• min_samples： 样本点要成为核心对象所需要的$\epsilon$-邻域的样本数阈值，即前面原理部分中的$M$，默认为5。
• metric：最近邻距离度量参数，默认欧式距离，见后面的距离表
• algorithm：最近邻搜索算法参数，其中brute为暴力搜索；kd_tree为kd树实现；ball_tree通过球树实现。默认auto为自动选择
• leaf_size：当使用kd_tree或ball_tree为最邻近算法时，停止建子树的叶子节点数量的阈值。
• p: 表示闵氏距离的p值，p=1为曼哈顿距离，p=2为欧式距离。

常见距离的定义：

距离参数	备注	表达式
chebyshev	切比雪夫距离	$\max (\vec{u}-\vec{v})$
minkowski	闵氏距离	$\Vert u-v{\Vert }_p$
manhattan	曼哈顿距离	$\sum |u_i-v_i|$
euclidean	欧氏距离	$\Vert u-v{\Vert }_2$
seuclidean	归一化欧式距离	各特征纬度均值为0；方差为1
mahalanobis	马氏距离	$\sqrt{(x-y{)}^T{S}^{-1}(x-y)}$
wminkowski	加权闵氏距离	$\sqrt[p]{{\sum }_{i=1}^n(w|x_i-y_i|{)}^p}$