* n3 }( J3 a/ b* g. `6 T 3 i) o1 G8 I8 r4. DBSCAN思想: B- f& q, y6 W% D3 B
DBSCAN的聚类定义很简单:由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇。' s0 R/ n1 u( @
这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象,则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里;如果有多个核心对象,则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象,否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。; N+ W ]) c+ G, G6 {/ T7 r% {
( F& a# x* k+ p 那么怎么才能找到这样的簇样本集合呢?DBSCAN使用的方法很简单,它任意选择一个没有类别的核心对象作为种子,然后找到所有这个核心对象能够密度可达的样本集合,即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合,这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。+ w* f9 o- z3 C U9 o4 v
/ M( M& \$ ?; U- m1 D* B- {这基本上就是DBSCAN算法的主要内容了,但是还有三个问题没有考虑:4 F# J) z: C$ f
1)一些异常样本点或者说少量游离于簇外的样本点,这些点不在任何一个核心对象在周围,在DBSCAN中,我们一般将这些样本点标记为噪音点。! b, m. r2 C$ H. E
2)距离的度量问题,即如何计算某样本和核心对象样本的距离。在DBSCAN中,一般采用最近邻思想,采用某一种距离度量来衡量样本距离,比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本,寻找最近邻可以直接去计算所有样本的距离,如果样本量较大,则一般采用KD树或者球树来快速的搜索最近邻。9 ]- F' A; {# I7 E% }7 C* l
3)第三种问题比较特殊,某些样本可能到两个核心对象的距离都小于ϵ,但是这两个核心对象由于不是密度直达,又不属于同一个聚类簇,那么如果界定这个样本的类别呢?一般来说,此时DBSCAN采用先来后到,先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法 7 A0 Z! J" ?7 w , Z9 q; E& z; T4 M1 z: ^5. DBSCAN算法步骤 7 y. r# ]1 Z) @! C, `4 P* E下面是DBSCAN聚类算法的主要步骤% Z& u; j- f2 w' X8 ]9 m
输入:样本集D=(x1,x2,...,xm),邻域参数(ϵ,MinPts), 样本距离度量方式 + c% Q/ J M6 x4 k 输出: 簇划分C. ) I% T7 o. q6 [6 ?; Z0 J# _( r
1)初始化核心对象集合Ω=∅, 初始化聚类簇数k=0,初始化未访问样本集合Γ = D, 簇划分C = ∅+ R9 |! ^2 y1 v3 v" \0 x
2) 对于j=1,2,…m, 按下面的步骤找出所有的核心对象: 6 A9 J& ^( N4 d a) 通过距离度量方式,找到样本xj的ϵ-邻域子样本集Nϵ(xj)0 e @- D) | h$ X1 K+ D
b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts, 将样本xj加入核心对象样本集合:Ω=Ω∪{xj} $ ]& ^% I% u6 l, P e( y! J 3)如果核心对象集合Ω=∅,则算法结束,否则转入步骤4. $ F1 [0 y) C% `- W/ ]6 m# K 4)在核心对象集合Ω中,随机选择一个核心对象o,初始化当前簇核心对象队列Ωcur={o}, 初始化类别序号k=k+1,初始化当前簇样本集合Ck={o}, 更新未访问样本集合Γ=Γ−{o}% X1 P0 X/ [( p( ~' L+ w& q% x
5)如果当前簇核心对象队列Ωcur=∅,则当前聚类簇Ck生成完毕, 更新簇划分C={C1,C2,...,Ck}, 更新核心对象集合Ω=Ω−Ck, 转入步骤3。否则更新核心对象集合Ω=Ω−Ck。1 a9 F B2 l" g
6)在当前簇核心对象队列Ωcur中取出一个核心对象o′,通过邻域距离阈值ϵ找出所有的ϵ-邻域子样本集Nϵ(o′),令Δ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪Δ, 更新未访问样本集合Γ=Γ−Δ, 更新Ωcur=Ωcur∪(Δ∩Ω)−o′,转入步骤5.2 m' q, w& w) m) l, k2 `
输出结果为: 簇划分C={C1,C2,…,Ck} 2 E* Y, _* I, q8 V 6 B6 N; `/ \; R9 p4 z) A+ s- `! S* i& v6. DBSCAN算法在python scikit-learn实现 - y) L0 {$ w6 ~ 在scikit-learn中,DBSCAN算法类为sklearn.cluster.DBSCAN。要熟练的掌握用DBSCAN类来聚类,除了对DBSCAN本身的原理有较深的理解以外,还要对最近邻的思想有一定的理解。 / O i/ S! M7 ~1 C DBSCAN重要参数也分为两类,一类是DBSCAN算法本身的参数,一类是最近邻度量的参数: ' F+ n0 U# h% z6 Z P 1)eps: DBSCAN算法参数,即我们的ϵ-邻域的距离阈值,和样本距离超过ϵ的样本点不在ϵ-邻域内。默认值是0.5.一般需要通过在多组值里面选择一个合适的阈值。eps过大,则更多的点会落在核心对象的ϵ-邻域,此时我们的类别数可能会减少, 本来不应该是一类的样本也会被划为一类。反之则类别数可能会增大,本来是一类的样本却被划分开。$ Q/ i; L; l. D- z2 |" g
2)min_samples: DBSCAN算法参数,即样本点要成为核心对象所需要的ϵ-邻域的样本数阈值。默认值是5. 一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下,min_samples过大,则核心对象会过少,此时簇内部分本来是一类的样本可能会被标为噪音点,类别数也会变多。反之min_samples过小的话,则会产生大量的核心对象,可能会导致类别数过少。 0 k: s0 P( k [9 P$ b) n4 M 3)metric:最近邻距离度量参数。可以使用的距离度量较多,一般来说DBSCAN使用默认的欧式距离(即p=2的闵可夫斯基距离)就可以满足我们的需求。可以使用的距离度量参数有: ) i/ k- a3 Y3 D a) 欧式距离 “euclidean” : B' B6 v$ i: N6 y b) 曼哈顿距离 “manhattan”& t \- n! O) ~; y9 Y/ G
c) 切比雪夫距离“chebyshev”0 _8 Z* [" s5 K" d3 C* C8 R' Z
d) 闵可夫斯基距离 “minkowski”4 H4 X5 I7 n7 h; r
e) 带权重闵可夫斯基距离 “wminkowski”: y8 s# E1 C1 d; @6 L+ g4 f, n
f) 标准化欧式距离 “seuclidean”: 即对于各特征维度做了归一化以后的欧式距离。此时各样本特征维度的均值为0,方差为1.* V" J9 X$ v1 E& k2 T7 Y- `
g) 马氏距离“mahalanobis”:当样本分布独立时,马氏距离等同于欧式距离。 ' A! [9 A+ u- s- a 还有一些其他不是实数的距离度量,一般在DBSCAN算法用不上,这里也就不列了。8 r: O% C0 D8 v1 {) a5 l& a
0 x+ A2 m. v$ k* U
4)algorithm:最近邻搜索算法参数,算法一共有三种,第一种是蛮力实现,第二种是KD树实现,第三种是球树实现。对于这个参数,一共有4种可选输入,‘brute’对应第一种蛮力实现,‘kd_tree’对应第二种KD树实现,‘ball_tree’对应第三种的球树实现, ‘auto’则会在上面三种算法中做权衡,选择一个拟合最好的最优算法。需要注意的是,如果输入样本特征是稀疏的时候,无论我们选择哪种算法,最后scikit-learn都会去用蛮力实现‘brute’。个人的经验,一般情况使用默认的 ‘auto’就够了。 如果数据量很大或者特征也很多,用"auto"建树时间可能会很长,效率不高,建议选择KD树实现‘kd_tree’,此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时,可以尝试用‘ball_tree’。而如果输入样本是稀疏的,无论你选择哪个算法最后实际运行的都是‘brute’。 1 ~6 h3 I5 X0 f V$ l 5)leaf_size:最近邻搜索算法参数,为使用KD树或者球树时, 停止建子树的叶子节点数量的阈值。这个值越小,则生成的KD树或者球树就越大,层数越深,建树时间越长,反之,则生成的KD树或者球树会小,层数较浅,建树时间较短。默认是30. 因为这个值一般只影响算法的运行速度和使用内存大小,因此一般情况下可以不管它。 ( u+ I2 ^) Y8 Z" q2 O5 K9 \' ~- Y 6) p: 最近邻距离度量参数。只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择,p=1为曼哈顿距离, p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。 8 e+ z9 }$ ?3 n* H% A* S8 Y 以上就是DBSCAN类的主要参数介绍,需要调参的两个参数eps和min_samples,这两个值的组合对最终的聚类效果有很大的影响。因此,DBSCAN聚类算法的结果对参数比较敏感,基于DBSCAN开发的OPTICS聚类算法则很好的解决了这个问题,后续会更新OPTICS算法的详解。 , K- P* O1 `( S , k) ?$ W& B* Z1 x. Q9 I生成一组随机数据,为了体现DBSCAN在非凸数据的聚类优点,我们生成了三簇数据,两组是非凸的
import numpy as np % w2 I! O! o7 \% Z |/ X) @
import matplotlib.pyplot as plt0 J/ ]6 c4 ^# F* i, {
from sklearn import datasets 5 G# I% G% A/ s# ?; i7 F\" g
%matplotlib inline l3 m$ n' G6 K
X1, y1=datasets.make_circles(n_samples=5000, factor=.6,9 h- d2 K6 r% k7 g. m* U