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

    千次阅读 2018-09-04 08:30:49
    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是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本,他们之间的紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。

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

    2. DBSCAN密度定义

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

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

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

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

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

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

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

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

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

    3. DBSCAN密度聚类思想

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

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

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

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

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

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

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

    4. DBSCAN聚类算法

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

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

        输出: 簇划分C. 

        1)初始化核心对象集合Ω=∅Ω=∅, 初始化聚类簇数k=0,初始化未访问样本集合ΓΓ = D,  簇划分C = ∅∅

        2) 对于j=1,2,...m, 按下面的步骤找出所有的核心对象:

          a) 通过距离度量方式,找到样本xjxj的ϵϵ-邻域子样本集Nϵ(xj)Nϵ(xj)

          b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts, 将样本xjxj加入核心对象样本集合:Ω=Ω∪{xj}Ω=Ω∪{xj}

        3)如果核心对象集合Ω=∅Ω=∅,则算法结束,否则转入步骤4.

        4)在核心对象集合ΩΩ中,随机选择一个核心对象oo,初始化当前簇核心对象队列Ωcur={o}Ωcur={o}, 初始化类别序号k=k+1,初始化当前簇样本集合Ck={o}Ck={o}, 更新未访问样本集合Γ=Γ−{o}Γ=Γ−{o}

        5)如果当前簇核心对象队列Ωcur=∅Ωcur=∅,则当前聚类簇CkCk生成完毕, 更新簇划分C={C1,C2,...,Ck}{C1,C2,...,Ck}, 更新核心对象集合Ω=Ω−CkΩ=Ω−Ck, 转入步骤3。

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

        输出结果为: 簇划分C={C1,C2,...,Ck}{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联合调参,不同的参数组合对最后的聚类效果有较大影响。

     

    展开全文
  • 我们总结一下DBSCAN聚类算法原理的基本要点:DBSCAN算法需要选择一种距离度量,对于待聚类的数据集中,任意两个点之间的距离,反映了点之间的密度,说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义...
  • DBSCAN聚类算法原理总结2

    千次阅读 2018-09-04 08:41:31
    DBSCAN聚类算法三部分: 1、 DBSCAN原理、流程、参数设置、优缺点以及算法; http://blog.csdn.net/zhouxianen1987/article/details/68945844 2、 matlab代码实现;  blog:...

    DBSCAN聚类算法三部分:

    1、        DBSCAN原理、流程、参数设置、优缺点以及算法;

    http://blog.csdn.net/zhouxianen1987/article/details/68945844

    2、        matlab代码实现; 

    blog:http://blog.csdn.net/zhouxianen1987/article/details/68946169

    code:http://download.csdn.net/detail/zhouxianen1987/9789230

    3、        C++代码实现及与matlab实例结果比较。

    blog:http://blog.csdn.net/zhouxianen1987/article/details/68946278

           code:http://download.csdn.net/detail/zhouxianen1987/9789231

     

     

    DBSCAN(Density-based spatial clustering ofapplications with noise)是Martin Ester, Hans-PeterKriegel等人于1996年提出的一种基于密度的空间的数据聚类方法,该算法是最常用的一种聚类方法[1,2]。该算法将具有足够密度区域作为距离中心,不断生长该区域,算法基于一个事实:一个聚类可以由其中的任何核心对象唯一确定[4]。该算法利用基于密度的聚类的概念,即要求聚类空间中的一定区域内所包含对象(点或其他空间对象)的数目不小于某一给定阈值。该方法能在具有噪声的空间数据库中发现任意形状的簇,可将密度足够大的相邻区域连接,能有效处理异常数据,主要用于对空间数据的聚类,优缺点总结如下[3,4]:

     

    优点

    (1)聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类;

    (2)与K-MEANS比较起来,不需要输入要划分的聚类个数;

    (3)聚类簇的形状没有偏倚;

    (4)可以在需要时输入过滤噪声的参数。

    缺点:

    (1)当数据量增大时,要求较大的内存支持I/O消耗也很大;

    (2)当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差,因为这种情况下参数MinPts和Eps选取困难。

    (3)算法聚类效果依赖与距离公式选取,实际应用中常用欧式距离,对于高维数据,存在“维数灾难”。

    基本概念[5]如下基本概念在[6]中有更为详细说明介绍。

    (1)Eps邻域:给定对象半径Eps内的邻域称为该对象的Eps邻域;

    (2)核心点(core point):如果对象的Eps邻域至少包含最小数目MinPts的对象,则称该对象为核心对象;

    (3)边界点(edge point):边界点不是核心点,但落在某个核心点的邻域内;

    (4)噪音点(outlier point):既不是核心点,也不是边界点的任何点;

    (5)直接密度可达(directly density-reachable):给定一个对象集合D,如果p在q的Eps邻域内,而q是一个核心对象,则称对象p从对象q出发时是直接密度可达的;

    (6)密度可达(density-reachable):如果存在一个对象链  p1, …,pi,.., pn,满足p1 = p 和pn = q,pi是从pi+1关于Eps和MinPts直接密度可达的,则对象p是从对象q关于Eps和MinPts密度可达的;

    (7)密度相连(density-connected):如果存在对象O∈D,使对象p和q都是从O关于Eps和MinPts密度可达的,那么对象p到q是关于Eps和MinPts密度相连的。

    (8)类(cluster):设非空集合,若满足:,

    (a),且从密度可达,那么。
    (b)和密度相连。
    则称构成一个类簇

    有关核心点、边界点、噪音点以及直接密度可达、密度可达和密度相连解释如图1[1]:

    图1红色为核心点,黄色为边界点,蓝色为噪音点,minPts = 4,Eps是图中圆的半径大小有关“直接密度可达”和“密度可达”定义实例如图2所示[5]:其中,Eps用一个相应的半径表示,设MinPts=3,请分析Q,M,P,S,O,R这5个样本点之间的关系。

     

     

    图2   “直接密度可达”和“密度可达”概念示意描述。根据前文基本概念的描述知道:由于有标记的各点­M、P、O和R的Eps近邻均包含3个以上的点,因此它们都是核对象;M­是从P“直接密度可达”;而Q则是从­M“直接密度可达”;基于上述结果,Q是从P“密度可达”;但P从Q无法“密度可达”(非对称)。类似地,S和R从O是“密度可达”的;O、R和S均是“密度相连”(对称)的。

     

    DBSCAN算法原理[5]

    (1)DBSCAN通过检查数据集中每点的Eps邻域来搜索簇,如果点p的Eps邻域包含的点多于MinPts个,则创建一个以p为核心对象的簇;

    (2)然后,DBSCAN迭代地聚集从这些核心对象直接密度可达的对象,这个过程可能涉及一些密度可达簇的合并;

    (3)当没有新的点添加到任何簇时,该过程结束。

     

    有关算法的伪代码wiki百科中给出了,[5]用中文描述了其流程:

    DBSCAN算法伪代码描述:

    输入:数据集D,给定点在邻域内成为核心对象的最小邻域点数:MinPts,邻域半径:Eps   

    输出:簇集合

     

    
     
    1. (1) 首先将数据集D中的所有对象标记为未处理状态

    2. (2) for(数据集D中每个对象p) do

    3. (3) if (p已经归入某个簇或标记为噪声) then

    4. (4) continue;

    5. (5) else

    6. (6) 检查对象p的Eps邻域 NEps(p) ;

    7. (7) if (NEps(p)包含的对象数小于MinPts) then

    8. (8) 标记对象p为边界点或噪声点;

    9. (9) else

    10. (10) 标记对象p为核心点,并建立新簇C, 并将p邻域内所有点加入C

    11. (11) for (NEps(p)中所有尚未被处理的对象q) do

    12. (12) 检查其Eps邻域NEps(q),若NEps(q)包含至少MinPts个对象,则将NEps(q)中未归入任何一个簇的对象加入C;

    13. (13) end for

    14. (14) end if

    15. (15) end if

    16. (16) end for


    wiki百科中代码描述:

     

     

    
     
    1. DBSCAN(D, eps, MinPts) {

    2. C = 0

    3. foreach point P in dataset D {

    4. ifP is visited

    5. continue next point

    6. mark P as visited

    7. NeighborPts = regionQuery(P, eps)

    8. ifsizeof(NeighborPts) < MinPts

    9. mark P as NOISE

    10. else {

    11. C = next cluster

    12. expandCluster(P, NeighborPts, C, eps, MinPts)

    13. }

    14. }

    15. }

    16.  
    17. expandCluster(P, NeighborPts, C, eps, MinPts) {

    18. add Pto cluster C

    19. foreach point P' in NeighborPts {

    20. ifP' is not visited {

    21. mark P' as visited

    22. NeighborPts' = regionQuery(P', eps)

    23. if sizeof(NeighborPts') >= MinPts

    24. NeighborPts = NeighborPts joined with NeighborPts'

    25. }

    26. ifP' is not yet member of any cluster

    27. add P' to cluster C

    28. }

    29. }

    30.  
    31. regionQuery(P, eps)

    32. returnall points within P's eps-neighborhood (including P)

     

     

    时间复杂度

    (1)DBSCAN的基本时间复杂度是 O(N*找出Eps领域中的点所需要的时间), N是点的个数。最坏情况下时间复杂度是O(N2)

    (2)在低维空间数据中,有一些数据结构如KD树,使得可以有效的检索特定点给定距离内的所有点,时间复杂度可以降低到O(NlogN)

    空间复杂度:低维和高维数据中,其空间都是O(N),对于每个点它只需要维持少量数据,即簇标号和每个点的标识(核心点或边界点或噪音点)

     

    参数设置:DBSCAN共包括3个输入数据:数据集D,给定点在邻域内成为核心对象的最小邻域点数:MinPts,邻域半径:Eps,其中Eps和MinPts需要根据具体应用人为设定。

    (1)  Eps的值可以使用绘制k-距离曲线(k-distance graph)方法得当,在k-距离曲线图明显拐点位置为对应较好的参数。若参数设置过小,大部分数据不能聚类;若参数设置过大,多个簇和大部分对象会归并到同一个簇中。

    K-距离:K距离的定义在DBSCAN算法原文中给出了详细解说,给定K邻域参数k,对于数据中的每个点,计算对应的第k个最近邻域距离,并将数据集所有点对应的最近邻域距离按照降序方式排序,称这幅图为排序的k距离图,选择该图中第一个谷值点位置对应的k距离值设定为Eps。一般将k值设为4。原文如下[2]:

     

    (2)  MinPts的选取有一个指导性的原则(a rule of thumb),MinPts≥dim+1,其中dim表示待聚类数据的维度。MinPts设置为1是不合理的,因为设置为1,则每个独立点都是一个簇,MinPts≤2时,与层次距离最近邻域结果相同,因此,MinPts必须选择大于等于3的值。若该值选取过小,则稀疏簇中结果由于密度小于MinPts,从而被认为是边界点儿不被用于在类的进一步扩展;若该值过大,则密度较大的两个邻近簇可能被合并为同一簇。因此,该值是否设置适当会对聚类结果造成较大影响。

     

     

    参考资料:

    [1] https://en.wikipedia.org/wiki/DBSCAN

    [2]  Ester,Martin; Kriegel, Hans-Peter; Sander,Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M.,eds. Adensity-based algorithm for discovering clusters in large spatial databaseswith noise. Proceedings of the Second International Conference on KnowledgeDiscovery and Data Mining (KDD-96). AAAI Press.pp. 226–231.CiteSeerX 10.1.1.121.9220. ISBN 1-57735-004-9.

    [3] 各种聚类算法的比较 

     http://blog.163.com/qianshch@126/blog/static/48972522201092254141315/

    [4] http://www.cnblogs.com/chaosimple/p/3164775.html

    [5] https://wenku.baidu.com/view/ce3e324aa8956bec0975e3d5.html

    [6]http://blog.csdn.net/itplus/article/details/10088625

    [7] http://www.tuicool.com/articles/euAZneu

    [8] http://cn.mathworks.com/matlabcentral/fileexchange/52905-dbscan-clustering-algorithm

    [9] http://blog.csdn.net/snnxb/article/details/29880387

    [10] 聚类算法-DBSCAN-C++实现,http://blog.csdn.net/k76853/article/details/50440182

    [11] DBSCAN聚类算法C++实现,http://blog.csdn.net/u011367448/article/details/18549823

    [12] DBSCAN 算法介绍以及C++实现,http://blog.csdn.net/u011557212/article/details/53203323

    [13] https://github.com/siddharth-agrawal/DBSCAN

    [14] http://download.csdn.net/download/piaominnan/8480767

    展开全文
  • 关于DBSCAN聚类原理的动画演示,我在B站的投稿《DBSCAN聚类原理 动画演示》中已作了介绍,有兴趣的朋友可以先看一下链接中的1分半钟动画演示。 在[Python数据挖掘] sklearn-DBSCAN聚类一文中,我们调用sklearn库的...

    注明:本文主要内容亦曾整理作为本人所选课程《模式识别与机器学习》的期末课程报告。

    [问题背景]

    关于DBSCAN聚类原理的动画演示,我在B站的投稿《DBSCAN聚类原理 动画演示》中已作了介绍,有兴趣的朋友可以先看一下链接中的1分半钟动画演示。

    [Python数据挖掘] sklearn-DBSCAN聚类一文中,我们调用sklearn库的DBSCAN聚类方法,成功对以下ANSI编码的grade.txt文本文档数据集进行了聚类:

    YZN,133,108,76
    ZHY,96,145,101
    WYZ,132,107,60
    DHY,100,102,120
    CYH,139,99,93
    LHY,73,149,81
    ZHY,85,148,93
    TQP,39,138,85
    ZZL,145,112,71
    HJC,101,116,118
    XZY,99,98,117

    [问题分析]

    下面从底层实现的角度,只需用到math库,无需使用numpy,逐步实现DBSCAN聚类算法。

    针对grade.txt文本文档进行数据预处理并聚类的实例代码:

    (grade.txt需要与代码的.py文件位于同一目录下)

    import math
    
    class DBSCAN:
        'DBSCAN类'
        eps = 0
        min_samples = 0
        labels_ = []
        
    
        def __init__(self, eps, min_samples):
            self.eps = eps
            self.min_samples = min_samples
    
        def distance(self, data1, data2): # 计算距离
            distance = 0
            for i in range(len(data1)):
                distance = distance + pow(data1[i]-data2[i], 2)
            distance = math.sqrt(distance)
            return distance
    
        def spread(self, i, Dict, labels_):
            for m in Dict[i]:
                if (labels_[m] == -1):
                    labels_[m] = labels_[i] 
                    self.spread(m, Dict, labels_)
        
        def fit(self, Data): # 聚类
            # 初始化
            flag = []
            for t in range(len(Data)):
                flag.append(-1) # 核心点(1)、边界点(0)、噪声点(-1)标记 # 默认标注为噪声点
                
            Dict = {}
            for t in range(len(Data)): # 生成相邻点关系
                Dict[t] = []
                
            # 样本点标注    
            for i in range(len(Data)):
                self.labels_.append(-1)
                samples = 0
                for j in range(len(Data)): 
                    if (i == j):
                        pass
                    else:
                        if (self.distance(Data[i], Data[j]) <= self.eps): 
                            samples = samples + 1 
                            if (flag[j] != 1): 
                                flag[j] = 0 
                            Dict[i].append(j) 
                if (samples >= self.min_samples): 
                    flag[i] = 1 
    
            # 样本点聚类
            for i in range(len(Data)):
                
                if (flag[i] == 1 and self.labels_[i] == -1):
                    self.labels_[i] = i
                    self.spread(i, Dict, self.labels_)
                else:
                        pass
            sort = []
            for t in self.labels_:
                if ((t not in sort) and (t != -1)):
                    sort.append(t)
            for td in range(len(self.labels_)):
                if (self.labels_[td] != -1):
                    for index in range(len(sort)):
                        if (sort[index] == self.labels_[td]):
                            self.labels_[td] = index
     
    def loadData(filePath):
        fr = open(filePath, 'r+')
        lines = fr.readlines()
        retName = []
        retData = []
        for line in lines:
            items = line.strip().split(',')
            retName.append(items[0])
            retData.append([float(items[i]) for i in range(1,len(items))])
        return retName, retData
     
    if __name__ == '__main__':
        Name, Data = loadData('grade.txt')
        
        eps = 21
        min_samples = 2
        db = DBSCAN(eps, min_samples)
        db.fit(Data) # 分开写,否则会return一个None,提示None不包含labels_
        label = db.labels_
        outputName = []
        noise = []
     
        for i in range(max(label)+1):
            outputName.append([])
        for i in range(len(Name)):
            if(label[i] != -1):
                outputName[label[i]].append(Name[i])
            else:
                noise.append(Name[i])
        print(outputName)
        print("噪声点:", noise)
    

    运行结果为:

    [['YZN', 'WYZ', 'CYH', 'ZZL'], ['ZHY', 'LHY', 'ZHY'], ['DHY', 'HJC', 'XZY']]
    噪声点: ['TQP']

    可以看到,这一聚类结果与我们用sklearn的DBSCAN得到的聚类结果是一致的。

    DBSCAN算法的核心实现部分:

    import math
    
    class DBSCAN:
        'DBSCAN类'
        eps = 0
        min_samples = 0
        labels_ = []
        
    
        def __init__(self, eps, min_samples): # 参数初始化
            self.eps = eps
            self.min_samples = min_samples
    
        def distance(self, data1, data2): # 计算距离
            distance = 0
            for i in range(len(data1)):
                distance = distance + pow(data1[i]-data2[i], 2)
            distance = math.sqrt(distance)
            return distance
    
        def spread(self, i, Dict, labels_): # 传播标记
            for m in Dict[i]:
                if (labels_[m] == -1):
                    labels_[m] = labels_[i] 
                    self.spread(m, Dict, labels_)
        
        def fit(self, Data): # 聚类
            # 初始化
            flag = []
            for t in range(len(Data)):
                flag.append(-1) # 核心点(1)、边界点(0)、噪声点(-1)标记 # 默认标注为噪声点
                
            Dict = {}
            for t in range(len(Data)): # 生成相邻点关系
                Dict[t] = []
                
            # 样本点标注    
            for i in range(len(Data)):
                self.labels_.append(-1)
                samples = 0
                for j in range(len(Data)): 
                    if (i == j):
                        pass
                    else:
                        if (self.distance(Data[i], Data[j]) <= self.eps): 
                            samples = samples + 1 
                            if (flag[j] != 1): 
                                flag[j] = 0 
                            Dict[i].append(j) 
                if (samples >= self.min_samples): 
                    flag[i] = 1 
    
            # 样本点聚类
            for i in range(len(Data)):
                
                if (flag[i] == 1 and self.labels_[i] == -1):
                    self.labels_[i] = i
                    self.spread(i, Dict, self.labels_)
                else:
                        pass
            sort = []
            for t in self.labels_:
                if ((t not in sort) and (t != -1)):
                    sort.append(t)
            for td in range(len(self.labels_)):
                if (self.labels_[td] != -1):
                    for index in range(len(sort)):
                        if (sort[index] == self.labels_[td]):
                            self.labels_[td] = index

     

    展开全文
  • DBSCAN聚类算法原理及图解

    千次阅读 2019-11-18 22:01:21
    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是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本,他们之间的紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。

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

    2. 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由xixi密度直达, 除非且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的聚类定义就简单了。

    3. DBSCAN密度聚类思想

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

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

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

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

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

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

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

    4. 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, 将样本xjxj加入核心对象样本集合:Ω=Ω∪{xj}

        3)如果核心对象集合Ω=∅,则算法结束,否则转入步骤4.

        4)在核心对象集合Ω中,随机选择一个核心对象o,初始化当前簇核心对象队列Ωcur={o}, 初始化类别序号k=k+1,初始化当前簇样本集合Ck={o}, 更新未访问样本集合Γ=Γ−{o}

        5)如果当前簇核心对象队列Ωcur=∅,则当前聚类簇Ck生成完毕, 更新簇划分{C1,C2,...,Ck}, 更新核心对象集合Ω=Ω−Ck, 转入步骤3。

        6)在当前簇核心对象队列ΩcurΩcur中取出一个核心对象o′o′,通过邻域距离阈值ϵϵ找出所有的ϵϵ-邻域子样本集Nϵ(o′),令Δ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪Δ 更新未访问样本集合Γ=Γ−Δ  更新Ωcur=Ωcur∪(Δ∩Ω)−o′Ω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联合调参,不同的参数组合对最后的聚类效果有较大影响。

    6. 算法伪代码

    7.效果图

    展开全文
  • 前言:无监督学习想快一点复习完,就转入有监督学习 聚类算法主要包括哪些算法?主要包括:K-means、DBSCAN、Density Peaks聚类(局部密度聚类)、层次聚...
  • 【机器学习】2:DBSCAN聚类算法原理

    千次阅读 2018-04-09 10:55:42
    4、DBSCAN聚类算法原理 DBSCAN通过检查数据集中每个点的r邻域来搜索簇,如果点p的r邻域包含多于MinPts个点,则创建一个以p为核心对象的簇; 然后, DBSCAN迭代的聚集从这些核心对象直接密度可达的对象,这个...
  • 算法描述: (1)检测数据库中尚未检查过的对象p,如果p为被处理(归为某个簇或者标记为噪声),则检查其邻域,若包含的对象数不小于minPts,建立新簇C,将其中的所有点加入候选集N; (2)对候选集N 中所有尚未被...
  • DBSCAN聚类算法 1、算法原理 DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一个有代表性的基于密度的空间聚类算法。它将类定义为密度相连的点的最大集合,...
  • 二、DBSCAN聚类算法 三、参数选择 四、DBSCAN算法迭代可视化展示 五、常用的评估方法:轮廓系数 六、用Python实现DBSCAN聚类算法 一、前言 DBSCAN(Density-Based Spatial Clustering of Applications with Noise,...
  • DBSCAN聚类算法

    2020-07-19 15:43:42
     DBSCAN是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本,他们之间的紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。 通过将...
  • DBSCAN聚类算法的理解与应用

    千次阅读 多人点赞 2020-11-27 22:27:23
    在前面的文章中,我们讲了KNN算法的原理与简单应用,KNN一种有监督学习的分类算法,也就是说该算法首先需要训练数据来进行学习之后才能对数据进行分类。在本文中我们讲到的DBSCAN聚类算法...
  • 基于sk-learn的DBSCAN聚类算法

    千次阅读 2017-07-10 20:34:31
    在DBSCAN密度聚类算法中,我们对DBSCAN聚类算法原理做了总结,本文就对如何用scikit-learn来学习DBSCAN聚类做一个总结,重点讲述参数的意义和需要调参的参数。 1. scikit-learn中的DBSCAN类  在scikit-...
  • 超详解DBSCAN聚类算法(含源码)

    千次阅读 2020-01-02 17:15:30
    DBSCAN聚类算法学习: DBSCAN算法的基本原理: DBSCAN算法实现 数据集的使用: 聚类结果及参数对结果的影响: 关于DBSCAN算法的实验 DBSCAN与K-means聚类的比较: DBSCAN参数设置 ...
  • DBSCAN聚类算法Python实现

    万次阅读 2019-03-30 20:26:54
    DBSCAN是一种基于密度的聚类算法,这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本,他们之间的紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。 通过将...
  • DBSCAN聚类算法原理及sklearn的演示

    千次阅读 2018-10-06 18:20:26
    概念:基于密度的带有噪声点的聚类方法。 内部概念理解: 1.核心对象:若某个点的密度达到算法设定的阈值则称为核心点。 2.距离阈值:设定的半径r。 3.直接密度可达:若某点p在点q的r邻域内,且q是核心密度点,则pq...
  • DBSCAN 密度聚类算法原理及伪代码

    千次阅读 2017-10-30 17:52:20
    DBSCAN 密度聚类算法原理及伪代码
  • 一、工作原理 对于每个实例,该算法都会计算在它一小段距离内 ε\varepsilonε 内有多少个实例。该区域称为实例的 ε−\varepsilon-ε− 邻域。 如果一个实例在其 ε\varepsilonε 邻域内至少包含 min_samples 个...
  • 题记:没有落脚到数据结构的对算法的理解都是没有灵魂的复制粘贴! 其实很多算法,我们通过开源的算法包比如sklearn,...DBSCAN密度聚类算法 西瓜书上对于密度聚类的讲解: 聚类的过程示例: 直观理解: 可以这样
  • DBSCAN聚类原理及详解

    千次阅读 多人点赞 2018-12-14 14:48:01
    DBSCAN聚类 (1)DBSCAN简介 DBSCAN是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪声的空间数据库中发现...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 197
精华内容 78
关键字:

dbscan聚类算法原理