DBSCAN 是一种非常著名的基于密度的聚类算法。其英文全称是 Density-Based Spatial Clustering of Applications with Noise，意即：一种基于密度，对噪声鲁棒的空间聚类算法。直观效果上看，DBSCAN 算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

DBSCAN 算法具有以下特点：

• 基于密度，对远离密度核心的噪声点鲁棒
• 无需知道聚类簇的数量
• 可以发现任意形状的聚类簇

DBSCAN 通常适合于对较低维度数据进行聚类分析。

基本概念

DBSCAN 的基本概念可以用 1、2、3、4 来总结。

1 个核心思想

这个核心思想是基于密度。直观效果上看，DBSCAN 算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

2 个算法参数

2 个算法参数：邻域半径 R 和最少点数目 MinPoints。

这 2 个算法参数实际可以刻画什么叫密集：当邻域半径 R 内点的个数大于最少点数目 R 时，就是密集。

3 种点的类别

3 种点的类别：核心点、边界点和噪声点。邻域半径 R 内样本点的数量大于等于 MinPoints 的点叫做核心点，不属于核心点但在某个核心点的邻域内的点叫做边界点，既不是核心点也不是边界点的是噪声点。

4 种点的关系

4 种点的关系：密度直达，密度可达，密度相连，非密度相连。

如果 P 为核心点，Q 在 P 的 R 邻域内，那么称 P 到 Q 密度直达。任何核心点到其自身密度直达，密度直达不具有对称性，如果 P 到 Q 密度可达，那么 Q 到 P 不一定密度可达。

如果存在核心点 P2，P3……Pn，且 P1 到 P2 密度直达，P2 到 P3 密度直达……P(n-1) 到 Pn 密度直达，Pn 到 Q 密度直达，则 P1 到 Q 密度可达。密度可达也不具有对称性。

如果存在核心点 S，使得 S 到 P 和 Q 都密度可达，则 P 和 Q 密度相连。密度相连具有对称性，如果 P 和 Q 密度相连，那么 Q 和 P 也一定密度相连。密度相连的两个点属于同一个聚类簇。

如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。

算法步骤

DBSCAN 的算法步骤分成两步。

寻找核心点形成临时聚类簇

Step1：寻找核心点形成临时聚类簇。扫描全部样本点，如果某个样本点 R 半径范围内点数目大于等于 MinPoints，则将其纳入核心点列表，并将其密度直达的点形成对应的临时聚类簇。

合并临时聚类簇得到聚类簇

对于每一个临时聚类簇，检查其中的点是否为核心点，如果是，将该点对应的临时聚类簇和当前临时聚类簇合并，得到新的临时聚类簇。

重复此操作，直到当前临时聚类簇中的每一个点要么不在核心点列表，要么其密度直达的点都已经在该临时聚类簇，该临时聚类簇升级成为聚类簇。

继续对剩余的临时聚类簇进行相同的合并操作，直到全部临时聚类簇被处理。

sklearn 调包范例

生成样本点

%matplotlib inline
%config InlineBackend.figure_format = 'svg'
import numpy as np
import pandas as pd
from sklearn import datasets


X,_ = datasets.make_moons(500,noise = 0.1,random_state=1)
df = pd.DataFrame(X,columns = ['feature1','feature2'])

df.plot.scatter('feature1','feature2', s = 100,alpha = 0.6, title = 'dataset by make_moon');

调用 dbscan 方法完成聚类

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

from sklearn.cluster import dbscan

# eps 为邻域半径，min_samples 为最少点数目
core_samples,cluster_ids = dbscan(X, eps = 0.2, min_samples=20) 
# cluster_ids 中-1 表示对应的点为噪声点

df = pd.DataFrame(np.c_[X,cluster_ids],columns = ['feature1','feature2','cluster_id'])
df['cluster_id'] = df['cluster_id'].astype('i2')

df.plot.scatter('feature1','feature2', s = 100,
    c = list(df['cluster_id']),cmap = 'rainbow',colorbar = False,
    alpha = 0.6,title = 'sklearn DBSCAN cluster result');

手工实现范例

前方高能提醒。下面使用 Python 和 Pandas 手工实现 DBSCAN 聚类算法。

看懂这个实现需要对 Pandas 的相关操作相当熟悉，并且对 DBSCAN 的算法细节有深入的了解。

这个实现和 sklearn 中的实现有所不同，适当拓展可以在 Spark 上进行分布式实现。

实践中一般掌握 DBSAN 的基本原理和调包方法就够用了。无相关基础的同学可以跳过该部分。

生成样本点

import numpy as np
import pandas as pd
from sklearn import datasets
%matplotlib inline

X,_ = datasets.make_moons(500,noise = 0.1,random_state=1)
df = pd.DataFrame(X,columns = ['feature1','feature2'])

df.head()

计算样本点中两两之间的距离

dfdata = df.copy()
dfdata.columns = ["feature1_a","feature2_a"]
dfdata["id_a"] = range(1,len(df)+1)
dfdata = dfdata.set_index("id_a",drop=False)
dfdata = dfdata.reindex(columns=["id_a","feature1_a","feature2_a"])

dfdata.head()

dfpairs = pd.DataFrame(columns = ["id_a","id_b","distance_ab"])

q = dfdata.loc[:,["feature1_a","feature2_a"]].values 

for i in dfdata.index:
    p = dfdata.loc[i,["feature1_a","feature2_a"]].values 
    dfab = dfdata[["id_a"]].copy()
    dfab["id_b"] = i
    dfab["distance_ab"] = np.sqrt(np.sum((p -q )**2,axis = 1))
    dfpairs = pd.concat([dfpairs,dfab])

dfpairs.head()

构造临时聚类簇

dfnears = dfpairs.query("distance_ab<0.2")

dfglobs = dfnears.groupby("id_a").agg({"id_b":[len,set]})
dfglobs.columns = ["neighbours_cnt","neighbours"]
dfglobs = dfglobs.query("neighbours_cnt>=20")
dfglobs = dfglobs.reset_index()

# 找到核心点 id
core_ids = set(dfglobs["id_a"])
dfcores = dfglobs.copy()

# 剔除非核心点的 id
dfcores["neighbours"] = [x & core_ids for x in dfcores["neighbours"]]
dfcores.head()

合并相连的临时聚类簇得到聚类簇

#定义合并函数：将有共同核心点的临时聚类簇合并

def mergeSets(set_list):
    result = []
    while  len(set_list)>0 :
        cur_set = set_list.pop(0)
        intersect_idxs = [i for i in list(range(len(set_list)-1,-1,-1)) if cur_set&set_list[i]]
        while  intersect_idxs :
            for idx in intersect_idxs:
                cur_set = cur_set|set_list[idx]

            for idx in intersect_idxs:
                set_list.pop(idx)

            intersect_idxs = [i for i in list(range(len(set_list)-1,-1,-1)) if cur_set&set_list[i]]

        result = result+[cur_set]
    return result

# 测试 mergeSets 效果
test_set_list = [{1,2,3},{3,4,5},{10,12,13},{4,5,8},{13,15},{7,8},{20,22}]
print(mergeSets(test_set_list))

[{1, 2, 3, 4, 5, 7, 8}, {10, 12, 13, 15}, {20, 22}]

set_list = list(dfcores["neighbours"])
result = mergeSets(set_list)
core_clusters = {i:s for i,s in enumerate(result)}
print(core_clusters)

{0: {1, 2, 5, 7, 11, 15, 17, 21, 22, 24, 26, 32, 34, 35, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 54, 55, 57, 58, 60, 61, 64, 65, 66, 67, 68, 69, 72, 76, 84, 87, 88, 90, 91, 92, 93, 95, 103, 105, 111, 112, 113, 114, 117, 120, 121, 124, 126, 128, 133, 135, 136, 137, 139, 144, 146, 160, 163, 164, 165, 169, 170, 173, 182, 183, 185, 190, 194, 196, 198, 200, 201, 202, 203, 206, 210, 213, 227, 228, 229, 230, 231, 233, 234, 235, 238, 245, 246, 248, 249, 250, 251, 252, 255, 256, 257, 258, 259, 261, 264, 267, 270, 275, 283, 289, 292, 293, 295, 296, 297, 307, 312, 313, 316, 323, 326, 327, 328, 332, 334, 335, 339, 341, 343, 346, 349, 351, 356, 357, 365, 366, 368, 373, 374, 377, 379, 384, 385, 387, 391, 394, 396, 403, 409, 411, 415, 417, 418, 419, 427, 429, 434, 435, 437, 438, 442, 444, 446, 448, 457, 458, 462, 473, 474, 477, 478, 479, 484, 488, 491, 492, 498}, 1: {3, 8, 10, 12, 14, 16, 19, 20, 25, 27, 29, 31, 44, 51, 52, 53, 56, 59, 62, 73, 74, 75, 80, 82, 85, 96, 97, 98, 100, 104, 110, 116, 118, 119, 122, 125, 132, 134, 141, 142, 143, 147, 148, 149, 150, 152, 154, 158, 159, 167, 168, 171, 172, 174, 175, 176, 177, 178, 180, 184, 188, 191, 195, 197, 204, 205, 207, 209, 211, 212, 216, 217, 218, 220, 222, 226, 232, 237, 244, 253, 254, 266, 268, 269, 272, 274, 276, 277, 279, 280, 281, 282, 284, 286, 287, 290, 291, 294, 298, 301, 302, 303, 306, 308, 310, 311, 317, 318, 319, 320, 321, 322, 324, 325, 329, 331, 337, 342, 344, 345, 347, 348, 350, 352, 354, 358, 359, 360, 361, 362, 363, 364, 370, 371, 372, 376, 378, 381, 383, 386, 389, 398, 401, 406, 408, 412, 413, 414, 416, 420, 421, 425, 428, 430, 431, 433, 436, 440, 445, 449, 450, 454, 456, 464, 466, 470, 471, 472, 483, 486, 487, 489, 490, 494, 497, 499, 500}}

关联所有样本点

core_map = {}
for k,v in core_clusters.items():
    core_map.update({vi:k for vi in v})

cluster_map = {}
for i in range(len(dfglobs)):
    id_a = dfglobs["id_a"][i]
    neighbours = dfglobs["neighbours"][i]
    cluster_map.update({idx:core_map[id_a] for idx in neighbours})

print(len(cluster_map))

483

dfdata["cluster_id"] = [cluster_map.get(id_a,-1) for id_a in dfdata["id_a"]]
dfdata.head()

# 可视化样本点的聚类结果，可以看到和 sklearn 中的结果完全一致。

dfdata.plot.scatter('feature1_a','feature2_a', s = 100,
    c = list(dfdata['cluster_id']),cmap = 'rainbow',colorbar = False,
    alpha = 0.6,title = 'Hands DBSCAN Cluster Result ');

小结

今天与大家一起学习聚类常用的另一个算法 DBSCAN，关于此算法记住 1、2、3、4 和 DBSCAN 算法实施两步走：先形成临时簇，然后临时簇合并为聚类簇。最后分别给出调包和不调包的完整代码实现，建议大家都手动敲代码实现一遍。