精华内容
下载资源
问答
  • DBSCAN密度聚类算法的原理

    千次阅读 2019-11-13 14:29:16
    DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的空间聚类方法)是一种很典型的密度聚类算法,和 K-Means , BIRCH 这些一般只适用于凸样本集的聚类相比,DBSCAN 既可以...

    前言

    DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的空间聚类方法)是一种很典型的密度聚类算法,和 K-MeansBIRCH 这些一般只适用于凸样本集的聚类相比,DBSCAN 既可以适用于凸样本集,也可以适用于非凸样本集

    一、基于密度的聚类思想

    DBSCAN 是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本,他们之间是紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。

    通过将紧密相连的样本划为一类,这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别,则我们就得到了最终的所有聚类类别结果。

    二、DBSCAN密度定义

    在上一小节我们定性描述了密度聚类的基本思想,本节我们就看看DBSCAN是如何描述密度聚类的。DBSCAN是基于一组邻域来描述样本集的紧密程度的,参数( ϵ \epsilon ϵ, MinPts)用来描述邻域的样本分布紧密程度。其中, ϵ \epsilon ϵ 描述了某一样本的邻域距离阈值,MinPts 描述了某一样本的距离为 ϵ \epsilon ϵ 的邻域中样本个数的阈值。

    假设我的样本集是 D = ( x 1 , x 2 , . . . , x m ) D=(x_1, x_2, ..., x_m) D=(x1,x2,...,xm) ,则DBSCAN具体的密度描述定义如下:

    • ϵ \epsilon ϵ - 邻域:对于 x j ∈ D x_j \in D xjD ,其 ϵ \epsilon ϵ - 邻域包含样本集 D D D 中与 x j x_j xj 的距离不大于 ϵ \epsilon ϵ 的子样本集,即 N ϵ ( x j ) = { x i ∈ D ∣ d i s t a n c e ( x i , x j ) ≤ ϵ } N_{\epsilon}(x_j) = \{x_i \in D | distance(x_i, x_j) \leq \epsilon \} Nϵ(xj)={xiDdistance(xi,xj)ϵ} ,这个子样本集的个数记为 ∣ N ϵ ( x j ) ∣ |N_{\epsilon}(x_j)| Nϵ(xj)
    • 核心对象:对于任一样本 x j ∈ D x_j \in D xjD ,如果其 ϵ \epsilon ϵ - 邻域对应的 N ϵ ( x j ) N_{\epsilon}(x_j) Nϵ(xj) 至少包含MinPts个样本,即如果 ∣ N ϵ ( x j ) ∣ ≥ M i n P t s |N_{\epsilon}(x_j)| \geq MinPts Nϵ(xj)MinPts,则 x j x_j xj 是核心对象;
    • 密度直达:如果 x i x_i xi 位于 x j x_j xj ϵ \epsilon ϵ - 邻域中,且 x j x_j xj 是核心对象,则称 x i x_i xi x j x_j xj 密度直达。注意反之不一定成立,即此时不能说 x j x_j xj x i x_i xi 密度直达,除非且 x i x_i xi 也是核心对象;
    • 密度可达:对于 x i x_i xi x j x_j xj ,如果存在样本序列 p 1 , p 2 , . . . , p T p_1, p_2, ..., p_T p1,p2,...,pT ,满足 p 1 = x i , p T = x j p_1=x_i, p_T=x_j p1=xi,pT=xj ,且 p t + 1 p_{t+1} pt+1 p t p_t pt 密度直达,则称 x j x_j xj x i x_i xi 密度可达。也就是说,密度可达满足传递性。此时序列中的传递样本 p 1 , p 2 , . . . , p T − 1 p_1, p_2, ..., p_{T−1} p1,p2,...,pT1 均为核心对象,因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性,这个可以由密度直达的不对称性得出;
    • 密度相连:对于 x i x_i xi x j x_j xj ,如果存在核心对象样本 x k x_k xk ,使 x i x_i xi x j x_j xj 均由 x k x_k xk 密度可达,则称 x i x_i xi x j x_j xj 密度相连。注意密度相连关系是满足对称性的

    从下图可以很容易理解上述定义,图中 MinPts=5 ,红色的点都是核心对象,因为其 ϵ \epsilon ϵ - 邻域至少有 5 个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内,如果不在超球体内,则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的 ϵ \epsilon ϵ - 邻域内所有的样本相互都是密度相连的。
    1
    有了上述定义,DBSCAN的聚类定义就简单了。

    三、DBSCAN密度聚类思想

    DBSCAN的聚类定义很简单:由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇

    这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象,则簇里其他的非核心对象样本都在这个核心对象的 ϵ \epsilon ϵ -邻域里;如果有多个核心对象,则簇里的任意一个核心对象的 ϵ \epsilon ϵ -邻域中一定有一个其他的核心对象,否则这两个核心对象无法密度可达。这些核心对象的 ϵ \epsilon ϵ -邻域里所有的样本的集合组成的一个DBSCAN聚类簇

    那么怎么才能找到这样的簇样本集合呢?DBSCAN使用的方法很简单,它任意选择一个没有类别的核心对象作为种子,然后找到所有这个核心对象能够密度可达的样本集合,即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合,这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止

    基本上这就是DBSCAN算法的主要内容了,是不是很简单?但是我们还是有三个问题没有考虑。

    第一个是一些异常样本点或者说少量游离于簇外的样本点,这些点不在任何一个核心对象的周围,在DBSCAN中,我们一般将这些样本点标记为噪音点

    第二个是距离的度量问题,即如何计算某样本和核心对象样本的距离。在DBSCAN中,一般采用最近邻思想,采用某一种距离度量来衡量样本距离,比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本,寻找最近邻可以直接去计算所有样本的距离,如果样本量较大,则一般采用KD-tree或者ball-tree来快速的搜索最近邻。

    第三种问题比较特殊,某些样本可能到两个核心对象的距离都小于 ϵ \epsilon ϵ ,但是这两个核心对象由于不是密度直达,又不属于同一个聚类簇,那么如果界定这个样本的类别呢?一般来说,此时DBSCAN采用先来后到,先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法

    四、DBSCAN聚类算法的实现流程

    输入:样本集 D = ( x 1 , x 2 , . . . , x m ) D = (x_1, x_2, ..., x_m) D=(x1,x2,...,xm),邻域参数( ϵ \epsilon ϵMinPts),样本距离度量方式。

    输出: 簇划分(样本所属类别) C C C

    • ① 初始化核心对象集合 Ω = ϕ \Omega = \phi Ω=ϕ ,初始化聚类簇数 k = 0 k=0 k=0 ,初始化未访问样本集合 Γ = D \Gamma = D Γ=D ,簇划分 C = ϕ C = \phi C=ϕ
    • ② 对于 j = 1 , 2 , . . . , m j = 1, 2, ..., m j=1,2,...,m ,按下面的步骤找出所有的核心对象:
      a) 通过距离度量方式,找到样本 x j x_j xj ϵ \epsilon ϵ - 邻域子样本集 N ϵ ( x j ) N_{\epsilon}(x_j) Nϵ(xj)
      b) 如果子样本集的样本个数满足 ∣ N ϵ ( x j ) ∣ ≥ M i n P t s |N_{\epsilon}(x_j)| \geq MinPts Nϵ(xj)MinPts , 将样本 x j x_j xj 加入核心对象样本集合: Ω = Ω ∪ { x j } \Omega = \Omega \cup \{x_j\} Ω=Ω{xj}
    • ③ 如果核心对象集合 Ω = ϕ \Omega = \phi Ω=ϕ,则算法结束,否则转入步骤④;
    • ④ 在核心对象集合 Ω \Omega Ω 中,随机选择一个核心对象 o o o ,初始化当前簇核心对象队列 Ω c u r = { o } \Omega_{cur} = \{o\} Ωcur={o} ,初始化类别序号 k = k + 1 k = k+1 k=k+1,初始化当前簇样本集合 C k = { o } C_k = \{o\} Ck={o} ,更新未访问样本集合 Γ = Γ − { o } \Gamma = \Gamma − \{o\} Γ=Γ{o}
    • ⑤ 如果当前簇核心对象队列 Ω c u r = ϕ \Omega_{cur} = \phi Ωcur=ϕ ,则当前聚类簇 C k C_k Ck 生成完毕,更新簇划分 C = { C 1 , C 2 , . . . , C k } C=\{C_1, C_2, ..., C_k\} C={C1,C2,...,Ck} ,更新核心对象集合 Ω = Ω − C k \Omega = \Omega − C_k Ω=ΩCk ,转入步骤③;
    • ⑥ 在当前簇核心对象队列 Ω c u r \Omega_{cur} Ωcur 中取出一个核心对象 o ′ o' o ,通过邻域距离阈值 ϵ \epsilon ϵ 找出所有的 ϵ \epsilon ϵ - 邻域子样本集 N ϵ ( o ′ ) N_{\epsilon}(o') Nϵ(o),令 Δ = N ϵ ( o ′ ) ∩ Γ \Delta = N_{\epsilon}(o') \cap \Gamma Δ=Nϵ(o)Γ ,更新当前簇样本集合 C k = C k ∪ Δ C_k = C_k \cup \Delta Ck=CkΔ ,更新未访问样本集合 Γ = Γ − Δ \Gamma = \Gamma − \Delta Γ=ΓΔ ,更新 Ω c u r = Ω c u r ∪ ( Δ ∩ Ω ) − o ′ \Omega_{cur} = \Omega_{cur} \cup (\Delta \cap \Omega) − o' Ωcur=Ωcur(ΔΩ)o ,转入步骤⑤。

    输出结果为: 簇划分 C = { C 1 , C 2 , . . . , C k } C = \{C_1, C_2, ..., C_k\} C={C1,C2,...,Ck}

    五、总结

    和传统的 K-Means 算法相比,DBSCAN 最大的不同就是不需要输入类别数k ,当然它最大的优势是可以发现任意形状的聚类簇,而不是像K-Means,一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点,这点和BIRCH算法类似。

    那么我们什么时候需要用DBSCAN来聚类呢?一般来说,如果数据集是稠密的,并且数据集不是凸的,那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的,则不推荐用DBSCAN来聚类。

    DBSCAN的主要优点有:

    • ① 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。

    • ② 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。

    • ③ 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。

    DBSCAN的主要缺点有:

    • ① 如果样本集的密度不均匀、聚类间距相差很大时,聚类质量较差,这时用DBSCAN聚类一般不适合。

    • ② 如果样本集较大时,聚类收敛时间较长,此时可以通过在搜索最近邻时建立的KD-tree或者ball-tree进行规模限制来改进。

    • ③ 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值 ϵ \epsilon ϵ ,邻域样本数阈值 M i n P t s MinPts MinPts 联合调参,不同的参数组合对最后的聚类效果有较大影响。

    六、参考文献

    DBSCAN密度聚类算法 - 刘建平

    展开全文
  • DBSCAN密度聚类算法

    2021-06-15 17:01:03
    DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法,和K-Means,BIRCH这些一般只适用于凸样本集的聚类相比,DBSCAN既可以适用于凸...

    DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法,和K-Means,BIRCH这些一般只适用于凸样本集的聚类相比,DBSCAN既可以适用于凸样本集,也可以适用于非凸样本集。下面我们就对DBSCAN算法的原理做一个总结。

    1. 密度聚类原理
          DBSCAN是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本,他们之间的紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。

    通过将紧密相连的样本划为一类,这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别,则我们就得到了最终的所有聚类类别结果。

    1. DBSCAN密度定义
          在上一节我们定性描述了密度聚类的基本思想,本节我们就看看DBSCAN是如何描述密度聚类的。DBSCAN是基于一组邻域来描述样本集的紧密程度的,参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度。其中,ϵ描述了某一样本的邻域距离阈值,MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。

    假设我的样本集是D=(x1,x2,…,xm),则DBSCAN具体的密度描述定义如下:

    1) ϵ-邻域:对于xj∈D,其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集,即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)|

    2) 核心对象:对于任一样本xj∈D,如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本,即如果|Nϵ(xj)|≥MinPts,则xj是核心对象。

    3)密度直达:如果xi位于xj的ϵ-邻域中,且xj是核心对象,则称xi由xj密度直达。注意反之不一定成立,即此时不能说xj由xi密度直达, 除非且xi也是核心对象。

    4)密度可达:对于xi和xj,如果存在样本样本序列p1,p2,…,pT,满足p1=xi,pT=xj, 且pt+1由pt密度直达,则称xj由xi密度可达。也就是说,密度可达满足传递性。此时序列中的传递样本p1,p2,…,pT−1均为核心对象,因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性,这个可以由密度直达的不对称性得出。

    5)密度相连:对于xi和xj,如果存在核心对象样本xk,使xi和xj均由xk密度可达,则称xi和xj密度相连。注意密度相连关系是满足对称性的。

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

    在这里插入图片描述

    有了上述定义,DBSCAN的聚类定义就简单了。

    1. DBSCAN密度聚类思想
          DBSCAN的聚类定义很简单:由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇。

    这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象,则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里;如果有多个核心对象,则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象,否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。

    那么怎么才能找到这样的簇样本集合呢?DBSCAN使用的方法很简单,它任意选择一个没有类别的核心对象作为种子,然后找到所有这个核心对象能够密度可达的样本集合,即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合,这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

    基本上这就是DBSCAN算法的主要内容了,是不是很简单?但是我们还是有三个问题没有考虑。

    第一个是一些异常样本点或者说少量游离于簇外的样本点,这些点不在任何一个核心对象在周围,在DBSCAN中,我们一般将这些样本点标记为噪音点。

    第二个是距离的度量问题,即如何计算某样本和核心对象样本的距离。在DBSCAN中,一般采用最近邻思想,采用某一种距离度量来衡量样本距离,比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本,寻找最近邻可以直接去计算所有样本的距离,如果样本量较大,则一般采用KD树或者球树来快速的搜索最近邻。如果大家对于最近邻的思想,距离度量,KD树和球树不熟悉,建议参考之前写的另一篇文章K近邻法(KNN)原理小结。

    第三种问题比较特殊,某些样本可能到两个核心对象的距离都小于ϵ,但是这两个核心对象由于不是密度直达,又不属于同一个聚类簇,那么如果界定这个样本的类别呢?一般来说,此时DBSCAN采用先来后到,先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。

    1. DBSCAN聚类算法
          下面我们对DBSCAN聚类算法的流程做一个总结。

    输入:样本集D=(x1,x2,…,xm),邻域参数(ϵ,MinPts), 样本距离度量方式

    输出: 簇划分C.

    1)初始化核心对象集合Ω=∅, 初始化聚类簇数k=0,初始化未访问样本集合Γ = D, 簇划分C = ∅
        2) 对于j=1,2,…m, 按下面的步骤找出所有的核心对象:

    a) 通过距离度量方式,找到样本xj的ϵ-邻域子样本集Nϵ(xj)
          b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts, 将样本xj加入核心对象样本集合:Ω=Ω∪{xj}
        3)如果核心对象集合Ω=∅,则算法结束,否则转入步骤4.

    4)在核心对象集合Ω中,随机选择一个核心对象o,初始化当前簇核心对象队列Ωcur={o}, 初始化类别序号k=k+1,初始化当前簇样本集合Ck={o}, 更新未访问样本集合Γ=Γ−{o}
        5)如果当前簇核心对象队列Ωcur=∅,则当前聚类簇Ck生成完毕, 更新簇划分C={C1,C2,…,Ck}, 更新核心对象集合Ω=Ω−Ck, 转入步骤3。否则更新核心对象集合Ω=Ω−Ck。

    6)在当前簇核心对象队列Ωcur中取出一个核心对象o′,通过邻域距离阈值ϵ找出所有的ϵ-邻域子样本集Nϵ(o′),令Δ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪Δ, 更新未访问样本集合Γ=Γ−Δ, 更新Ωcur=Ωcur∪(Δ∩Ω)−o′,转入步骤5.

    输出结果为: 簇划分C={C1,C2,…,Ck}
    5. DBSCAN小结
        和传统的K-Means算法相比,DBSCAN最大的不同就是不需要输入类别数k,当然它最大的优势是可以发现任意形状的聚类簇,而不是像K-Means,一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点,这点和BIRCH算法类似。

    那么我们什么时候需要用DBSCAN来聚类呢?一般来说,如果数据集是稠密的,并且数据集不是凸的,那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的,则不推荐用DBSCAN来聚类。

    下面对DBSCAN算法的优缺点做一个总结。

    DBSCAN的主要优点有:

    1) 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。

    2) 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。

    3) 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。

    DBSCAN的主要缺点有:

    1)如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差,这时用DBSCAN聚类一般不适合。

    2) 如果样本集较大时,聚类收敛时间较长,此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。

    3) 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值ϵ,邻域样本数阈值MinPts联合调参,不同的参数组合对最后的聚类效果有较大影响。

    展开全文
  • 基于密度聚类算法

    2019-12-10 16:34:28
    基于密度算法 基于密度算法的核心思想是根据样本点某一邻域内的邻居数定义样本空间的密度,这类算法可以找出空间中形状不规则的簇,并且不用指定簇的数量。算法的核心是计算每一点处的密度值,以及根据密度来...

    基于密度的算法

    基于密度的算法的核心思想是根据样本点某一邻域内的邻居数定义样本空间的密度,这类算法可以找出空间中形状不规则的簇,并且不用指定簇的数量。算法的核心是计算每一点处的密度值,以及根据密度来定义簇。

    1.DBSCAN算法理论

    DBSCAN算法是一种基于密度的算法,可以有效的处理噪声,发现任意形状的簇。它将定义为样本点密集的区域,算法从一个种子样本开始,持续向密集的区域生长直至到达边界。
      算法使用了两个人工设定的参数 ε \varepsilon ε M M M,前者是样本点的领域半径,后者是定义核心点的样本数阈值。下面介绍他们的概念。
      假设有样本集 X = { x 1 , x 2 , . . . , x N } X=\{x_1,x_2,...,x_N\} X={x1,x2,...,xN},样本点 x x x ε \varepsilon ε邻域定义为样本集中与该样本的距离小于等于 ε \varepsilon ε的样本构成的集合
    N ε ( x ) = { y ∈ X : d ( x , y ) } N_\varepsilon(x)=\{y\in X:d(x,y)\} Nε(x)={yX:d(x,y)}
    其中, d ( x , y ) d(x,y) d(x,y)是两个样本之间的距离,可以采用任何一种距离定义。样本的密度定义为它的 ε \varepsilon ε邻域的样本数:
    ρ ( x ) = ∣ N ε ( x ) ∣ \rho(x)=|N_\varepsilon(x)| ρ(x)=Nε(x)
      密度是一个非负整数。核心点定义为数据集中密度大于指定阈值的样本点,即如果
    ρ ( x ) ≥ M \rho(x)\ge M ρ(x)M
    则称 x x x为核心点,核心点是样本分布密集的区域。样本集 X X X中所有的核心点构成的集合为 X c X_c Xc,非核心点构成的集合为 X n c X_nc Xnc。如果 x x x是非核心点,并且它的 ε \varepsilon ε邻域内存在核心点,则称 x x x为边界点,边界点是密集区域的边界。如果一个点既不是核心点也不是边界点,则称之为噪声点,噪声点是样本稀疏的区域。
      如果 x x x是核心点, y y y在它的 ε \varepsilon ε邻域内,则称 y y y是从 x x x直接密度可达的。对于样本集中 的一组样本 x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1,x2,...,xn,如果 x i x_i xi + _+ + 1 _1 1是从 x i x_i xi直接密度可达的,则称 x n x_n xn是从 x i x_i xi可达的,密度可达是直接密度可达的推广。
      对于样本集中的样本点 x , y x,y x,y z z z,如果 y y y z z z都从 x x x密度可达,则称他们是密度相连的,根据定义,密度相连具有对称性。
      基于上面的概念可以给出簇的定义。样本集 C C C是整个样本集的一个子集,如果它满足下列条件:对于样本集 X X X中的任意两个样本 x x x y y y,如果 x ∈ C x\in C xC,且 y y y是从 x x x直接密度可达的,则 y ∈ C y\in C yC;如果 x ∈ C , y ∈ C x\in C,y\in C xC,yC,则 x x x y y y是密度相连的,则称集合 C C C是一个簇。
      根据簇的定义可以构造出聚类算法,具体做法是从某一核心点出发,不断 向密度可达的区域扩张,得到一个包含核心点和边界点的最大区域。这个区域中惹事两点的密度相连。
      假设有样本集 X X X,聚类算法将这些样本划分成 K K K个簇以及噪声点的集合,其中 K K K由算法确定。每个样本要么属于这些簇中的一个,要么是噪声点。定义变量 m i m_i mi为样本 x i x_i xi所属的簇,如果它属于第 j j j个簇,则 m i m_i mi的值为 j j j,如果它不属于这些簇中的任意一个,即是噪声点,则其值为-1, m i m_i mi就是聚类算法的返回结果。变量 k k k表示当前的簇号,每发现一个新的簇其值加1。聚类算法流程如下:
      第一阶段,初始化
      计算每个样本的邻域 N ε ( x i ) N_\varepsilon(x_i) Nε(xi)
      令 k = 1 , m i = 0 k=1,m_i=0 k=1,mi=0,初始化待处理样本集合 I = { 1 , 2 , . . . , N } I=\{1,2,...,N\} I={1,2,...,N}
      第二阶段,生成所有的簇
      循环,当 I I I不为空
        从 I I I中取出一个样本 i i i,并将其从集合中删除
        如果 i i i没被处理过,即 m i = 0 m_i=0 mi=0
          初始化集合 T = N ε ( x i ) T=N_\varepsilon(x_i) T=Nε(xi)
          如果 i i i为非核心点
            令 m i = − 1 m_i=-1 mi=1,暂时标记为噪声
          如果 i i i为核心点
            令 m i = k m_i=k mi=k,将当前簇编号赋予该样本
            循环,当 T T T不为空
              从集合 T T T中取出一个样本 j j j并从该集合中将其删除
              如果 m i = 0 m_i=0 mi=0或者 m i = − 1 m_i=-1 mi=1
                令 m i = k m_i=k mi=k
              如果 j j j是核心点
                将 j j j的邻居集合 N ε ( x i ) N_\varepsilon(x_i) Nε(xi)加入集合 T T T
            结束循环
            令 k = k + 1 k=k+1 k=k+1
    结束循环

      算法的核心步骤是依次处理每一个还未标记额的点,如果是核心点,则将其邻居点加入到连接的结合浩总,反复扩张,直到找到一个完整的簇。
      在实现时有几个问题需要考虑,第一个问题是如何快速找到一个点的所有邻居集合,可以用R树或者KD树等数据结构加速,第二个问题是参数 ε \varepsilon ε M M M的设定, ε \varepsilon ε的取值在有的时候非常难以确定,而它对聚类的结果有很大影响。 M M M值的选择有一个指导性原则,如果样本向量是 n n n维的,则 M M M的取值至少为 n + 1 n+1 n+1
      DBSCAN无须指定簇的数量,可以发现任意形状的簇,并且对噪声不敏感。其缺点是聚类的质量受距离函数的影响很大,如果数据维度很高,将面临维度灾难的问题。参数 ε \varepsilon ε M M M的设定有时候很困难。

    2.DBSCAN算法的sklearn实现

    在sklearn库中包含着各种各样的聚类算法,下面我们实现DBSCAN算法并实现其他聚类算法与DBSCAN算法形成对照。
    在这里插入图片描述
    五种算法代码实现

    import numpy as np
    import matplotlib.pyplot as plt
    import matplotlib as mpl
    from sklearn.cluster import KMeans
    from sklearn import datasets
    # 小批量K均值算法
    from sklearn.cluster import MiniBatchKMeans
    # 使用Birch的层次分类方法
    from sklearn.cluster import Birch
    # 基于带有噪音干扰的密度分类法
    from sklearn.cluster import DBSCAN
    # 谱分类,需要计算基于rbf距离的相似矩阵
    from sklearn.cluster import SpectralClustering
    x1, _ = datasets.make_circles(n_samples=5000, factor=.6, noise=0.05)
    x2, _ = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]], random_state=9)
    data = np.concatenate((x1, x2), axis=0)
    plt.figure(figsize=(15, 9))
    plt.subplot(231)
    # 解决中文无法显示问题
    mpl.rcParams['font.sans-serif'] = [u'SimHei']
    mpl.rcParams['axes.unicode_minus'] = False
    # 原始数据作图
    plt.scatter(data[:, 0], data[:, 1])
    plt.title("原始数据")
    plt.grid(True)
    plt.subplot(232)
    #使用Kmeans聚类进行分析
    result = KMeans(n_clusters=3, random_state=9).fit_predict(data)
    plt.scatter(data[:, 0], data[:, 1], c=result)
    plt.title("kmeans聚类算法")
    plt.grid(True)
    # 小批量K均值算法
    plt.subplot(233)
    result = MiniBatchKMeans(n_clusters=3, random_state=9).fit_predict(data)
    plt.scatter(data[:, 0], data[:, 1], c=result)
    plt.title("小批量K均值算法")
    plt.grid(True)
    # 使用Birch的层次分类方法
    plt.subplot(234)
    result = Birch(n_clusters=3).fit_predict(data)
    plt.scatter(data[:, 0], data[:, 1], c=result)
    plt.title("使用Birch的层次分类算法")
    plt.grid(True)
    # 基于带有噪音干扰的密度分类法,这种方法不需要制定分类类别,但是需要制定距离和每一簇的最小样本数。
    plt.subplot(235)
    result = DBSCAN(eps=0.1, min_samples=10).fit_predict(data)
    plt.scatter(data[:, 0], data[:, 1], c=result)
    plt.title("基于带有噪音干扰的密度的DBSCAN算法",fontsize=10)
    plt.grid(True)
    # 谱分类,需要计算基于rbf距离的相似矩阵
    plt.subplot(236)
    result = SpectralClustering(n_clusters=3).fit_predict(data)
    plt.scatter(data[:, 0], data[:, 1], c=result)
    plt.title("谱分类算法")#需要计算基于rbf距离的相似矩阵
    plt.suptitle(u'各种聚类算法分析对比', fontsize=18)
    plt.show()
    

    请大家多多指教!
    注:原理参考《机器学习与应用》雷明著,清华大学出版社

    展开全文
  • 层次聚类算法流程: 将每个对象看作一类,计算两两之间的最小距离; 2. 将距离最小的两个类合并成一个新类; 3. 重新计算新类与所有类之间的距离; 4. 重复2、3,直到所有类最后合并成一类 K-Mea...

    DBSCAN:

    从任一对象点p开始;
    寻找并合并点p直接密度可达(eps)的对象;
    如果p是一个核心点,则找到了一个聚类,如果p是一个边界点则寻找下一个对象点;
    重复2、3,直到所有点都被处理

    层次聚类算法流程:

    1. 将每个对象看作一类,计算两两之间的最小距离; 2. 将距离最小的两个类合并成一个新类; 3. 重新计算新类与所有类之间的距离; 4. 重复2、3,直到所有类最后合并成一类

    K-Means聚类算法流程:

    1.设置初始质心;2.将每个样本指派到最近的质心;3.用每个簇的样本均值来更新质心;4.直到目标函数变化程度小于预设的阈值, 或迭代次数大于预设的最大迭代次数,停止迭代

    MeanShift聚类算法流程:

    1.初始确定一个中心点center,计算在设置的半径为D的圆形空间内所有的点与中心点center的向量;2.计算整个圆形空间内所有向量的平均值,得到一个偏移均值;3.将中心点center移动到偏移均值位置;4.重复移动,直到满足一定条件结束

    展开全文
  • 机器学习之密度聚类算法

    万次阅读 2018-06-26 11:22:23
    基于密度的聚类算法假设聚类结构能够通过样本分布的紧密程度确定,以数据集在空间分布上的稠密程度为依据进行聚类,即只要一个区域中的样本密度大于某个阈值,就把它划入与之相近的簇中。 密度聚类从样本密度的角度...
  • 聚类算法概念聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法,同时也是数据挖掘的一个重要算法。聚类(Cluster)分析是由若干模式(Pattern)组成的,通常,模式是一个度量(Measurement)的向量,...
  • C++实现DBSCAN密度聚类算法

    千次阅读 2021-12-15 11:27:07
    直观效果上看,DBSCAN算法可以找到样本点的全部密集区域,并把这些密集区域当做一个一个的聚类簇。 2个算法参数:邻域半径R和最少点数目minpoints 这两个算法参数实际可以刻画什么叫密集——当邻域半径R内的点...
  • 密度峰值聚类算法(DPC)

    千次阅读 2021-04-16 22:06:26
    密度峰值聚类算法(DPC) 1. 简介 基于密度峰值的聚类算法全称为基于快速搜索和发现密度峰值的聚类算法(clustering by fast search and find of density peaks, DPC)。它是2014年在Science上提出的聚类算法,该算法...
  • 4.基于密度峰值的聚类算法 主要思想是寻找被低密度区与分离的高密度区域,基于的假设为: 1)类簇中心点的密度大于周围邻居点的密度; 2)类簇中心点与更高密度点之间的距离相对较大 因此有两个需要计算的量:局部...
  • 基于密度聚类算法的改进

    千次阅读 2016-07-28 22:45:44
    使用基于密度聚类算法,进行高维特征的聚类分析,从高维数据中提取出类似的有用信息,从而简化了特征数量,并且去除了部分冗余信息。 在聚类算法中,有这样几种算法: 划分的算法, K-Means 层次的方法, CURE 基于密度的...
  • 密度聚类算法(一)

    千次阅读 2017-02-26 10:41:11
    之前的两个小专题已经把划分方法聚类/层次方法聚类过了一遍,接下来就是我个人非常喜欢的一类聚类算法——密度聚类算法。 通过之前的博文,我们发现划分方法聚类算法与层次聚类算法把距离(欧氏距离,闵可夫斯基距离...
  • 无监督学习聚类:按照相似度对数据进行聚簇(cluster)划分,N个样本映射到K个簇中,每个簇至少有一个样本,一个样本只能属于一个簇,先给定一个初始划分,迭代改变样本和簇的关系,聚类的副产品可以做异常值检测 ...
  • 机器学习算法之聚类算法密度聚类)原理+手动实现前言介绍密度聚类方法DBSCAN介绍DBSCAN伪代码介绍DBSCAN手动实现代码(Python)后记 前言 笔者在最近完成了一道数据挖掘课程的有关密度聚类的小实验,为了实现...
  • 上一篇博客提到 K-kmeans 算法存在好几个缺陷,其中之一就是该算法无法聚类哪些非凸的数据集,也就是说...通常情况下,密度聚类从样本密度的角度出来,来考查样本之间的可连接性,并基于可连接样本不断扩展聚类簇,...
  • 聚类算法(DBSCAN):(一般比k-means等效果好) ​ 通俗理解:找到一个核心点的时候,就建立一个簇,里面的所有点,是它的下线,然后一直发展下线,一般边界点就不会继续发展了,里面的核心点继续发展下线,并且...
  • 密度聚类算法有多种,我们这里主要介绍一种著名的密度聚类算法:DBSCAN。 首先,我们通过下了解几个概念:   (1)邻域,与中心x距离不超过ε距离,如上红色虚线圈 (2)核心对象,确定聚类的初始点,如上...
  • DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个出现得比较早(1996年),比较有代表性的基于密度聚类算法。算法的主要目标是相比基于划分的聚类方法和层次聚类方法,需要更少的...
  • 来源 DBSCAN(Density-Based Spatial Clustering of Applications with Noise,基于密度的抗噪聚类方法)。和K-Means,BIRCH这些...DBSCAN是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的
  • 机器学习实战——密度聚类算法1 密度聚类2 sklearn中的实现 1 密度聚类 密度聚类假设聚类结构能够通过样本分布的密集程度确定,通常情形下,密度聚类算法从样本密度的角度来考察样本之间的可连接性,并基于可连接...
  • 密度聚类python

    2020-12-01 10:11:13
    本人在此就不搬运书上关于密度聚类的理论知识了,仅仅实现密度聚类的模板代码和调用skelarn的密度聚类算法。 有人好奇,为什么有sklearn库了还要自己去实现呢? 其实,库的代码是比自己写的高效且容易,但自己实现...
  • 图像聚类算法

    2021-01-31 21:37:47
    文章目录图像聚类算法一、聚类二、聚类常见的算法2.1 K-Means聚类K-means聚类算法的分析流程:K-Means聚类与图像处理2.2 层次聚类2.3 密度聚类 图像聚类算法 一、聚类   从广义上说,聚类就是将数据集中某些方面...
  • 凝聚的层次聚类——AGNES算法 采用自底向上的策略,首先将每个对象作为一个簇,然后这些簇根据某些准则被一步步合并,两个簇之间的距离由这两个的不同簇中距离最近的数据点的相似度来确定;聚类的过程直到所有对象...
  • 本文主要讲解有关聚类的相关算法,包括K均值聚类、层次聚类以及密度聚类等,除此之外,还会讲解聚类算法中的一些基本概念,以及聚类算法效果评判的一个标准——轮廓系数。 本文主要是依据李航老师的《统计学习方法...
  • 密度聚类算法(五)总结

    千次阅读 2017-02-27 17:09:21
    前面的四篇博文已经大致的将密度聚类以及密度聚类常用的算法DBSCAN,OPTICS,DENCLUE介绍了一下,按照惯例要改将这一部分串一下了。 (1)DBSCAN算法全局参数,导致聚类质量不是很好. (2)OPTICS针对全局参数做了...
  • 一种基于密度峰值的聚类算法

    千次阅读 2018-11-26 23:38:53
    一种基于密度峰值的聚类算法 1.引入 2014年Science刊发了一篇标题为Clustering by fast search and find of density peaks的文章,文章中介绍了一种基于密度峰值的聚类算法。 传统的聚类算法k-means,通常不适用于非...
  • 聚类算法之密度聚类算法DBSCAN

    千次阅读 2016-03-06 19:24:20
    DBSCAN算法流程
  • 聚类算法概述,K-Means算法,聚类算法的衡量指标,层次聚类方法,密度聚类方法及谱聚类方法详述。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,190
精华内容 2,076
关键字:

密度聚类算法流程图