基于密度的聚类算法（1）——DBSCAN详解

2744557306

1. DBSCAN简介
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种典型的基于密度的空间聚类算法。和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。
2 j4 X7 u- B# l6 o1 F% |
4 T1 q: C0 g0 v3 B0 R2 e5 R  e该算法利用基于密度的聚类的概念，即要求聚类空间中的一定区域内所包含对象（点或其他空间对象）的数目不小于某一给定阈值。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。但是当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差。
2 E5 k6 b4 G0 l9 s2 P
1 Z: k% u; X8 \* `# r2. DBSCAN的优缺点
, @0 Z7 x$ E! O) h5 o, b' Z/ a6 I, d和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点和BIRCH算法类似。

/ b% ]/ |2 t- A2 o  K那么什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。
. i  g% W- S, V: a" R2 ]（1）DBSCAN的优点：
1） 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
- X; l; Q- {- \4 V& c2） 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
3） 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
1 H6 p( z, h/ C9 [0 }: [（2）DBSCAN的缺点：
1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
8 y: c& `; ?. q0 |- t% r. N4 c$ e& k2） 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3） 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响

  h) b0 U( `& v3 M; @: h8 ^3. DBSCAN详细描述及参数含义
DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度。其中，ϵ描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。
　　　　假设样本集是*D=(x1,x2,...,xm)*,则DBSCAN具体的密度描述如下：
　　　　1） ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)|　
, }4 i: `; R" C3 h7 z0 O　　　　2) 核心对象：对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts，则xj是核心对象。　
　　　　3）密度直达：如果xi位于xj的ϵ-邻域中，且xj是核心对象，则称xi由xj密度直达。注意反之不一定成立，即此时不能说xj由xi密度直达, 除非且xi也是核心对象。
; e8 D: Y, q  h* f　　　　4）密度可达：对于xi和xj,如果存在样本样本序列p1,p2,...,pT,满足p1=xi,pT=xj, 且pt+1由pt密度直达，则称xj由xi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1,p2,...,pT−1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
9 Y0 i8 \; O! [; g+ O9 b; [　　　　5）密度相连：对于xi和xj,如果存在核心对象样本xk，使xi和xj均由xk密度可达，则称xi和xj密度相连。注意密度相连关系是满足对称性的。

从下图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。
" g. V8 z3 j' \; A" @

3 U2 m4 W) F+ S3 S) y4. DBSCAN思想
0 X! l  g) S4 a, V1 U* a　　DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。
( f7 c! N* p7 @( {! B0 k' W3 h　　这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。

! V: Y( g5 H- c! `8 e- }% L+ h1 b% `/ o; V　　那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。
9 y4 `! X$ T* T/ B8 P+ O
$ K$ O1 _+ B, j+ `8 o这基本上就是DBSCAN算法的主要内容了，但是还有三个问题没有考虑：
' u) D5 ]4 `; ~0 M! K! u( T　　1）一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。
% t  `' b2 s  [( O6 n3 v　　2）距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。
5 \8 I7 Z$ H# ~9 J　　3）第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法

/ Q- i8 y0 [8 d# f) W5. DBSCAN算法步骤
下面是DBSCAN聚类算法的主要步骤
　　输入：样本集D=(x1,x2,...,xm)，邻域参数(ϵ,MinPts), 样本距离度量方式
　　输出： 簇划分C.　
/ {% o2 Y: B! {/ A8 X- U" K: W
0 U% u$ b" j) t0 X' h+ g7 {　　1）初始化核心对象集合Ω=∅, 初始化聚类簇数k=0，初始化未访问样本集合Γ = D, 簇划分C = ∅
9 R1 b8 b0 G/ d" g　　2) 对于j=1,2,…m, 按下面的步骤找出所有的核心对象：
, [: p1 [  C0 ~' g　　　 a) 通过距离度量方式，找到样本xj的ϵ-邻域子样本集Nϵ(xj)
　　　 b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts， 将样本xj加入核心对象样本集合：Ω=Ω∪{xj}
　　3）如果核心对象集合Ω=∅，则算法结束，否则转入步骤4.
) ~, `% H1 X+ a" N9 j　　4）在核心对象集合Ω中，随机选择一个核心对象o，初始化当前簇核心对象队列Ωcur={o}, 初始化类别序号k=k+1，初始化当前簇样本集合Ck={o}, 更新未访问样本集合Γ=Γ−{o}
　　5）如果当前簇核心对象队列Ωcur=∅，则当前聚类簇Ck生成完毕, 更新簇划分C={C1,C2,...,Ck}, 更新核心对象集合Ω=Ω−Ck， 转入步骤3。否则更新核心对象集合Ω=Ω−Ck。
) i" @+ k5 T8 B: B' L+ e! Y8 @. L  H　　6）在当前簇核心对象队列Ωcur中取出一个核心对象o′,通过邻域距离阈值ϵ找出所有的ϵ-邻域子样本集Nϵ(o′)，令Δ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪Δ, 更新未访问样本集合Γ=Γ−Δ, 更新Ωcur=Ωcur∪(Δ∩Ω)−o′，转入步骤5.
3 @' j; c* u) t% X  s  ]　　输出结果为： 簇划分C={C1,C2,…,Ck}

4 p& ~5 r6 z1 ~9 t6. DBSCAN算法在python scikit-learn实现
0 j4 i* j0 y- @　　在scikit-learn中，DBSCAN算法类为sklearn.cluster.DBSCAN。要熟练的掌握用DBSCAN类来聚类，除了对DBSCAN本身的原理有较深的理解以外，还要对最近邻的思想有一定的理解。
, j1 l$ r/ v8 K　　DBSCAN重要参数也分为两类，一类是DBSCAN算法本身的参数，一类是最近邻度量的参数：
　　1）eps： DBSCAN算法参数，即我们的ϵ-邻域的距离阈值，和样本距离超过ϵ的样本点不在ϵ-邻域内。默认值是0.5.一般需要通过在多组值里面选择一个合适的阈值。eps过大，则更多的点会落在核心对象的ϵ-邻域，此时我们的类别数可能会减少， 本来不应该是一类的样本也会被划为一类。反之则类别数可能会增大，本来是一类的样本却被划分开。
　　2）min_samples： DBSCAN算法参数，即样本点要成为核心对象所需要的ϵ-邻域的样本数阈值。默认值是5. 一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下，min_samples过大，则核心对象会过少，此时簇内部分本来是一类的样本可能会被标为噪音点，类别数也会变多。反之min_samples过小的话，则会产生大量的核心对象，可能会导致类别数过少。
　　3）metric：最近邻距离度量参数。可以使用的距离度量较多，一般来说DBSCAN使用默认的欧式距离（即p=2的闵可夫斯基距离）就可以满足我们的需求。可以使用的距离度量参数有：
　　　　a) 欧式距离 “euclidean”
　　　　b) 曼哈顿距离 “manhattan”
　　　　c) 切比雪夫距离“chebyshev”
　　　　d) 闵可夫斯基距离 “minkowski”
6 N+ X; F0 \& _  C4 b+ H7 N　　　　e) 带权重闵可夫斯基距离 “wminkowski”
　　　　f) 标准化欧式距离 “seuclidean”: 即对于各特征维度做了归一化以后的欧式距离。此时各样本特征维度的均值为0，方差为1.
　　　　g) 马氏距离“mahalanobis”：当样本分布独立时，马氏距离等同于欧式距离。
% S$ S7 j8 D- `+ p　还有一些其他不是实数的距离度量，一般在DBSCAN算法用不上，这里也就不列了。

　　4）algorithm：最近邻搜索算法参数，算法一共有三种，第一种是蛮力实现，第二种是KD树实现，第三种是球树实现。对于这个参数，一共有4种可选输入，‘brute’对应第一种蛮力实现，‘kd_tree’对应第二种KD树实现，‘ball_tree’对应第三种的球树实现， ‘auto’则会在上面三种算法中做权衡，选择一个拟合最好的最优算法。需要注意的是，如果输入样本特征是稀疏的时候，无论我们选择哪种算法，最后scikit-learn都会去用蛮力实现‘brute’。个人的经验，一般情况使用默认的 ‘auto’就够了。 如果数据量很大或者特征也很多，用"auto"建树时间可能会很长，效率不高，建议选择KD树实现‘kd_tree’，此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时，可以尝试用‘ball_tree’。而如果输入样本是稀疏的，无论你选择哪个算法最后实际运行的都是‘brute’。
, L4 M) C4 b; v$ k3 g7 i4 H9 M/ l  L　　5）leaf_size：最近邻搜索算法参数，为使用KD树或者球树时， 停止建子树的叶子节点数量的阈值。这个值越小，则生成的KD树或者球树就越大，层数越深，建树时间越长，反之，则生成的KD树或者球树会小，层数较浅，建树时间较短。默认是30. 因为这个值一般只影响算法的运行速度和使用内存大小，因此一般情况下可以不管它。
　　6） p: 最近邻距离度量参数。只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择，p=1为曼哈顿距离， p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。
　　以上就是DBSCAN类的主要参数介绍，需要调参的两个参数eps和min_samples，这两个值的组合对最终的聚类效果有很大的影响。因此，DBSCAN聚类算法的结果对参数比较敏感，基于DBSCAN开发的OPTICS聚类算法则很好的解决了这个问题，后续会更新OPTICS算法的详解。

生成一组随机数据，为了体现DBSCAN在非凸数据的聚类优点，我们生成了三簇数据，两组是非凸的

1. import numpy as np
   ' Q. i) w. t% B+ b! R
2. import matplotlib.pyplot as plt. v\" a$ @- }- G7 ]1 _, z$ \. E
   
3. from sklearn import datasets. t8 C0 }& b% [& K
   
4. %matplotlib inline! s1 }! i# l0 O* |- m* J
   
5. X1, y1=datasets.make_circles(n_samples=5000, factor=.6,2 @( E6 B) j3 K3 j
   
6.                                       noise=.05)8 V, M6 W3 W7 f, i7 N
   
7. X2, y2 = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2,1.2]], cluster_std=[[.1]],  z4 y9 J) h) l' D' N& s5 e
   
8.                random_state=9)/ N# {' b4 v& w; @- q
   
9. 9 Y& q. |$ K* g( A; Q) j& R, H' o6 |( N
   
10. X = np.concatenate((X1, X2))
    0 [9 m+ W% B. q8 T0 Y
11. plt.scatter(X[:, 0], X[:, 1], marker='o')\" w& f) `9 l- z/ j/ [
    
12. plt.show()1 K, _( U# I6 r2 R4 j* W1 S5 T
    

复制代码

9 [: y! f! e3 S* x# p) v
1）利用K-Means聚类，代码如下：

1. from sklearn.cluster import KMeans
   & n) x. R\" `7 h8 _0 [! o* K
2. y_pred = KMeans(n_clusters=3, random_state=9).fit_predict(X)
   5 M4 F+ V0 Z9 [% w1 k
3. plt.scatter(X[:, 0], X[:, 1], c=y_pred)
   4 D9 X5 f- _& Z6 B# \  T6 g9 `! z
4. plt.show()% r, l\" q2 a% N, X2 w
   

复制代码

( H& Z- H  \0 {! s2）使用DBSCAN，用默认参数，代码如下：

1. from sklearn.cluster import DBSCAN
   ; v5 [# V5 k6 ^$ j
2. y_pred = DBSCAN().fit_predict(X): @( e6 d- g3 j% a
   
3. plt.scatter(X[:, 0], X[:, 1], c=y_pred)
   - u# c; F$ ^# m
4. plt.show()4 g$ q4 h) j4 Y4 i
   

复制代码

但是聚类结果是只有一类。。。
# H6 Z- ?, U9 c9 ?: u  C
- \& A# A3 M" i  O: D3）使用DBSCAN，调整两个重要参数：
从上图可以发现，类别数太少，因此需要增加类别数，可以通过减少ϵ-邻域的大小来实现，默认是0.5，减到0.1看看效果。代码如下：

1. y_pred = DBSCAN(eps = 0.1).fit_predict(X)
   6 E9 c+ @6 `9 G3 W* I5 _9 y\" N
2. plt.scatter(X[:, 0], X[:, 1], c=y_pred)
   9 V' S( `0 l: l& `/ v, I3 e' z. M+ t
3. plt.show()

复制代码

4 ^8 A) m% ~2 O! M
可以看到聚类效果有了改进。继续调参增加类别，有两个方向都是可以的，一个是继续减少eps，另一个是增加min_samples。将min_samples从默认的5增加到10，代码如下：

1. y_pred = DBSCAN(eps = 0.1, min_samples = 10).fit_predict(X)' n3 \. ^  L; Y8 v0 _
   
2. plt.scatter(X[:, 0], X[:, 1], c=y_pred)
   4 ~6 x/ k) u  J% s4 }0 L6 [9 X
3. plt.show()

复制代码

2 z1 S- t7 I  {# m6 ?
此时的聚类效果基本是可以令人满意的。
9 w- t; u  o) {9 P
7. 总结
DBSCAN需要调参的两个参数eps和min_samples，这两个值的组合对最终的聚类效果有很大的影响，即DBSCAN聚类算法的结果对参数比较敏感。
基于DBSCAN开发的OPTICS聚类算法，则很好的解决了这个问题，后续会更新OPTICS算法的详解与应用。

- t  v2 r. K: g: Y$ I* q