Question

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一个有代表性的密度聚类算法。它将类定义为密度相连的点的最大集合，通过在样本空间中不断寻找最大集合从而完成聚类。该算法能在带噪声的样本空间中发现任意形状的聚类并排除噪声。

1.算法原理

首先我们将列出DBSCAN算法涉及的基本定义，如表8-3所示。

表8-3 DBSCAN算法基本定义

可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。只有核心对象之间相互密度可达。而密度相连是对称关系。DBSCAN算法的目的是找到所有相互密度相连对象的最大集合。DBSCAN算法基于这样一个事实：一个聚类可以由其中的任何核心对象唯一确定。等价表述可以为：任一核心对象q，对象集合D中所有从q密度可达的对象所组成的集合构成了一个完整的聚类C且q∈C_q 。所以我们只需要对所有核心对象q使用深度搜索找出全部C即可。

整个算法的具体聚类过程如下：

1）定义半径ε和MinPts。

2）从对象集合D中抽取未被访问过的样本点q。

3）检验该样本点是否为核心对象，如果是则进入步骤4），否则返回步骤2）。

4）找出该样本点所有从该点密度可达的对象，构成聚类C_q 。注意构成的聚类C_q 的边界对象都是非核心对象（否则将继续进行深度搜索）以及在此过程中所有被访问过的对象都会被标记为已被访问。

5）如果全部样本点都已被访问，则结束算法，否则返回步骤2）。

DBSCAN算法能够过滤低密度区域，发现稠密样本点。系统聚类一般会产生凸形聚类，而DBSCAN算法可以发现任意形状的聚类。而与K-Means算法比，DBSCAN算法不需要指定划分的聚类个数，算法能够返回这个信息。DBSCAN还有一个很大的优点是它可以过滤噪声。从时间复杂度分析，DBSCAN的时间复杂度是O（nlogn），比系统聚类O（n³ ）好很多，比K-Means的O（nkt）稍差。DBSCAN的时间复杂度在大数据下是有可行性的，如果我们难以预知聚类数量，我们应该放弃K-Means而选择DBSCAN。

2.Python实现

我们还是利用scikit-learn中已经封装好的DBSCAN算法，设置DBSCAN分类器格式如下：

clf  =  sklearn.cluster.DBSCAN(eps=0.3, min_samples=10)

如算法原理所述，我们需要设定两个参数：ε和MinPts。这两个参数需要根据我们的经验，或根据多次实验进行调整。代码清单8-3给出了使用此算法的一个示例。其效果图如8-5所示。

代码清单8-3 DBSCAN聚类实验

# -*- coding:utf-8 -*-
# 密度聚类模型
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler
##############################################################################
# 获取
make_blobs数据
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,
                                random_state=0)
# 数据预处理
X = StandardScaler().fit_transform(X)
##############################################################################
# 执行
DBSCAN算法
db = DBSCAN(eps=0.3, min_samples=10).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
# 标记核心对象
,后面作图需要用到
core_samples_mask[db.core_sample_indices_] = True
# 算法得出的聚类标签
,-1代表样本点是噪声点
,其余值表示样本点所属的类
labels = db.labels_
# 获取聚类数量
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
# 输出算法性能的信息
print('Estimated number of clusters: %d' % n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f"
        % metrics.adjusted_rand_score(labels_true, labels))
print("Adjusted Mutual Information: %0.3f"
        % metrics.adjusted_mutual_info_score(labels_true, labels))
print("Silhouette Coefficient: %0.3f"
        % metrics.silhouette_score(X, labels))
##############################################################################
# 绘图
import matplotlib.pyplot as plt
# 黑色用作标记噪声点
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
i = -1
# 标记样式
,x表示噪声点
marker = ['v','^','o','x']
for k, col in zip(unique_labels, colors):
    if k == -1:
        # 黑色表示标记噪声点
        col = 'k'
    class_member_mask = (labels == k)
    i += 1
    if (i>=len(unique_labels)):
        i = 0
    # 绘制核心对象
    xy = X[class_member_mask & core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], marker[i], markerfacecolor=col,
            markeredgecolor='k', markersize=14)
    # 绘制非核心对象
    xy = X[class_member_mask & ~core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], marker[i], markerfacecolor=col,
            markeredgecolor='k', markersize=6)
plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()

*代码详见：示例程序/code/8-3.py

图8-5 DBSCAN聚类效果

分析图8-5，DBSCAN算法能够很好地去除噪声，聚类效果也比较理想。图中较大的样本点是核心对象，较小的样本点是非核心对象，以非核心对象为界的思想能够较好地划分类。借助scikit-learn模块我们能够轻松使用各种聚类算法，但我们必须了解算法背后的原理，知道如何调节算法的参数，这样才会取得好的聚类效果。