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

    千次阅读 2017-12-24 20:29:43
    DBSCAN聚类算法相关概念、算法步骤、优缺点及改进简述

    1、算法引入及简介

         为什么要引入DBSCAN?

         K均值聚类使用非常广泛,作为古老的聚类方法,它的算法非常简单,而且速度很快。但是其缺点在于它不能识别非球形的簇;而DBSCAN算法是将所有点标记为核心点、边界点或噪声点,将任意两个距离不大于E(eps)的核心点归为同一个簇,任何与核心点足够近的边界点也放到与之相同的簇中,可以发现任意形状的簇类。

       人为构造基于sin函数和cos函数构成的两组点数据,分别用K均值与DBSCAN算法聚类,对比如下:

             

                                          K均值                                                                                                         DBSCAN
          可以发现K均值聚类结果是不理想的
           
            DBSCAN定义
          
          DBSCAN(Density-Based Spatial Clustering of Application with Noise),是一个较有代表性的基于密度的聚类算法。它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪声的空间数据库中发现任意形状的聚类。简单的说就是过滤低密度区域,把扎堆的点(高密度区域)找出来。

    2、相关概念
       
        1)密度:任意一点的密度是以该点为圆心、以E为半径的圆区域内包含的点数目。   4
        2)Ε邻域:给定对象半径为Ε内的区域称为该对象的Ε邻域。
        3)核心对象:如果对象的E邻域样本点数大于等于MinPts(最小样本点数),则称该对象为核心对象。   a
        4)边界点:在以半径为E的邻域内点的数量小于MinPts,但是落在其他核心点的邻域内。    d
        5)噪声点:既不是边界点也不是核心点的任意点。   e
               
       6)直接密度可达:对于样本集合D,如果样本点q在p的Ε领域内,并且p为核心对象,那么对象q从对象p直接密度可达(如果p是一个核心对象,q属于p的邻域,q从p直接密度可达)。
                           a为核心对象,b为边界对象,b从a直接密度可达,反过来不成立,因为b不是核心对象

         7)密度可达:对于样本集合D,给定一串样本点p1,p2….pn,p= p1,q= pn,假如对象pi从pi-1直接密度可达,那么对象q从对象p密度可达。

                   b从a直接密度可达,a从c直接密度可达, 故b从c密度可达,同理c从b密度不可达
         
          8)密度相连:存在样本集合D中的一点o,如果对象o到对象p和对象q都是密度可达的,那么p和q密度相连。
                b从a密度可达,c也从a密度可达,故b和c密度相连。

    示例
        

           

         如图,E用相应半径表示,设MinPts=3
         m、p、o、r为核心对象,s、q为边界点(对应E领域内点的个数为2<MinPts,且在核心对象m的邻域内)
         q和p从m直接密度可达,m从p直接密度可达,故p从q密度可达,p和q密度相连
         s和r从o密度可达,s和r密度相连


    3、算法描述
        
        输入: 包含n个对象的数据库,半径E,最小样本点MinPts;
        输出:所有生成的簇。
      (1)Repeat
      (2)从数据库中抽出一个未处理的点;
      (3)IF抽出的点是核心点 THEN 找出所有从该点密度可达的对象,形成一个簇;
      (4)ELSE 抽出的点是边缘点(非核心对象),跳出本次循环,寻找下一个点;
      (5)UNTIL 所有的点都被处理。

     3.1步骤
     
      (1)DBSCAN需要二个参数: 扫描半径 (E)和最小包含样本点数(MinPts)。 任选一个未被访问(unvisited)的点开始,找出与其距离在E之内(包括E)的所有附近点。
      (2)如果 附近点的数量 ≥ minPts,则当前点与其附近点形成一个簇,并且出发点被标记为已访问(visited)。 然后递归,以相同的方法处理该簇内所有未被标记为已访问(visited)的点,从而对簇进行扩展。
      (3)如果 附近点的数量 < minPts,则该点暂时被标记作为噪声点。
      (4)如果簇充分地被扩展,即簇内的所有点被标记为已访问,然后用同样的算法去处理未被访问的点。

      3.2具体实现过程
      
       (1)检测数据库中尚未检查过的对象p,找出与其距离在E之内(包括E)的所有附近点,若包含的对象数不小于MinPts,建立新簇C,将其中的所有点加入候选集N;
       (2)对候选集N 中所有尚未被处理的对象q,检查其邻域,若至少包含minPts个对象,则将这些对象加入N;如果q 未归入任何一个簇,则将q 加入C;
       (3)重复步骤2),继续检查N 中未处理的对象,当前候选集N为空;
       (4)重复步骤1)~3),直到所有对象都归入了某个簇或标记为噪声。

      3.3实例
       
        如下二维数据集,设E=3.MinPts=3,使用DBSCAN对其聚类
       
         先扫描样本点P1(1,2)
              计算其E邻域,即找样本点中与其距离不大于E的样本点
              P1样本点的E邻域为:{P1、P2、P3、P13}

              P1的密度为4>MinPts,因此P1是核心点
              以P1点建立新簇C1,令N为P1邻域内的点的集合
              对N中的每一个点q,如果q未处理过且是核心点,则将q邻域内的点并入N。如果q还不是任何簇的成员,把q添加到C1

                     对P2邻域为{P1,P2,P3,P13},为核心点且未处理过将其邻域内的点并入N,把P2添加到C1
                     对P3,邻域为{P1,P2,P3,P4,P13},同上,将P3邻域内的点并入N,把P3添加到C1
                     对P13,邻域为{P1,P2,P3,P4,P13},同上,将P13邻域内的点并入N,把P13添加到C1
                     继续考虑N中未处理的点P4,邻域为{P3,P4,P13},将P4邻域内的点并入N, 把P4添加到C1

           此时集合N中对象全部处理完毕,得到簇C1,包含点{P1,P2,P3,P4,P13}

           继续扫描样本点P5(5,8),同
    上得簇C2,包含{P5,P6,P7,P8}
           继续扫描样本点P9(9,5):

                计算其E邻域为{P9},为非核心点

           继续扫描样本点P10(1,12):
                P10样本点的E邻域为{P10,P11},为非核心点
           继续扫描样本点P11(3,12):
                P11 样本点E邻域为{P10,P11,P12},P11是核心点
                以P11点建立新簇C3,令N为P11邻域内点的集合
                对N中的每一个点q,如果q未处理过且是核心点,则将q邻域内的点并入N。如果q还不是任何簇的成员,把q添加到C1
                      对P10,非核心点,把P10加入C3
                      对P12,邻域为{P11,P12},非核心点,把P12加入C3

         此时N中对象处理完毕得到簇C3
         继续扫描样本点,P12和P13都已经处理过,算法结束
         最后聚类结果为:3个簇    C1{P1,P2,P3,P4,P13}    C2{P5,P6,P7,P8}    C3{P10,P11,P12}
         样本点P9未归类为任何一个,最后判定为噪声

      3.4算法伪代码
     
           其中ExpandCluster算法伪码如下:
     
        
       3.5关于E和MinPts参数的选择
      
          给定MinPts
          1)E值过大:很多噪声被错误的归入簇,分离的若干个               自然簇错误的合并为一个簇
          2)E值过小:大量对象被错误的标记为噪声

          给定E值
          1)MinPts值过大:核心点数量减少,使得一些包含对象数较少的自然簇被弄丢
          2)MinPts值过小:大量对象被标记为核心点,从而将噪声归入簇

    4、算法优缺点及改进
        
        4.1优点:
          1)与K-means方法相比,DBSCAN不需要事先知道要形成的簇类的数量。
          2)与K-means方法相比,DBSCAN可以发现任意形状的簇类。
          3)同时,DBSCAN能够识别出噪声点。
          4)DBSCAN对于数据库中样本的顺序不敏感,但是,对于处于簇类之间边界样本,可能会根据哪个簇类优先被探测到而其归属有所摆动。
       
        4.2缺点:
          1)于高维数据,密度定义较麻烦。
          2)簇的密度变化太大,会有麻烦。

       4.3算法改进
       
         一种基于距离的自适应确定参数E和MinPts的方法
        
         (1)给定数据集P={p(i); i=0,1,…n},对于任意点P(i),计算点P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有点之间的距离,距离按照从小到大的顺序排序,假设排序后的距离集合为D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)},则d(k)就被称为k-距离。也就是说,k-距离是点p(i)到所有点(除了p(i)点)之间距离第k近的距离。对待聚类集合中每个点p(i)都计算k-距离,最后得到所有点的k-距离集合E={e(1), e(2), …, e(n)}
        
         (2)对集合E进行升序排序后,绘出曲线,通过观察,将急剧发生变化的位置所对应的k-距离的值,确定为半径Eps的值
        
         (3)在上述E确定的情况下,统计数据集中每个点的E邻域内点的数目,然后对整个数据集中每个点的E邻域内的点的数目求数学期望得到MinPts,此时的MinPts为每个聚类中核心对象E邻域内的数据点个数的最优值。计算公式为:
           
                                                                     
             其中,Pi为点i的的E邻域内点的个数
                           

          

    展开全文
  • 基于改进DBSCAN聚类算法在电子商务网站评价中的应用研究
  • 基于数据场的改进DBSCAN聚类算法,杨静,高嘉伟,DBSCAN算法是一种典型的基于密度的聚类算法。该算法可以识别任意形状的类簇,但聚类结果依赖于参数Eps和MinPts的选择,而且对于一些密
  • 针对基于密度带有“噪声”的空间聚类应用(DBSCAN)聚类算法存在的3个主要问题:输入参数敏感、对内存要求...仿真实验表明,新方法较好解决了传统DBSCAN聚类算法存在的问题,在聚类效率和聚类效果方面均优于传统DBSCAN
  • DBSCAN聚类算法的研究与改进 pdf格式文件。比较不错的研究DBSCAN的文章
  • 基于密度的DBSCAN聚类算法可以识别任意形状簇,但存在全局参数Eps与Min Pts的选择需人工干预,采用的区域查询方式过程复杂且易丢失对象等问题,提出了一种改进的参数自适应以及区域快速查询的密度聚类算法。根据KNN分布...
  • 针对基于密度的DBSCAN聚类算法及其改进算法在全局参数Eps与MinPts选择上需人工干预以及区域查询方式过程复杂和查询易丢失对象等不足,提出一种改进的参数自适应以及区域快速查询的密度聚类算法。根据KNN分布与数学...

    本人研究生期间写的关于聚类算法的一篇论文,已发表,希望对大家学习机器学习、数据挖掘等相关研究有所帮助!

    一种改进的自适应快速AF-DBSCAN聚类算法

    An Improved Adaptive and Fast AF-DBSCAN Clustering Algorithm

    摘要:针对基于密度的DBSCAN聚类算法及其改进算法在全局参数EpsMinPts选择上需人工干预以及区域查询方式过程复杂和查询易丢失对象等不足,提出一种改进的参数自适应以及区域快速查询的密度聚类算法。根据KNN分布与数学统计分析自适应计算出最优全局参数EpsMinPts,避免聚类过程中的人工干预,实现聚类过程的全自动化。通过改进种子代表对象选取方式进行区域查询,无需漏检操作,有效提高聚类的效率。对4种典型数据集的密度聚类实验结果表明,提出的方法有效解决了DBSCAN算法参数选取困难和算法效率的问题。

    关键字:数据挖掘;DBSCAN;区域查询;全局参数

    AbstractFor the density-based DBSCAN clustering algorithm and its improved algorithm at the choice of the global parameter Eps and MinPts require manual intervention and the process of regional query is complex and such query easily lose objects, improved adaptive parameters and fast regional query density clustering algorithm. According to KNN distribution and mathematical statistical analysis adaptively calculates the optimal global parameter Eps and MinPts, which avoid manual intervention and achieve full automation of the clustering process. Through the improved the way of selecting the representative seed to query region, without losing objects, improved the efficiency of clustering. Density clustering results of four typical data sets show that the proposed method effectively solves the difficulties of DBSCAN in parameter selection and efficiency.

    Key words: Data Mining; DBSCAN;Region query; Global Parameters


    0.引言

    数据挖掘作为一种从大量数据中发现感兴趣信息的技术,聚类算法在数据挖掘应用中已经得到日益广泛的应用。其中,基于密度的聚类算法可以发现任意形状的簇且能够较好地处理噪声数据,越来越受到广泛的关注。

    DBSCAN算法能够发现任意形状的簇,并有效识别离群点,但聚类之前需要人工选择EpsminPts 2个参数。当数据量增大时,要求较大的内存支持,I/O消耗也很大;当空间聚类的密度不均匀,聚类间距离相差很大时,聚类质量较差。针对DBSCAN算法在大型数据库与多密度数据集聚类精度低,计算复杂度高,全局参数人工选取等问题,已有不少学者进行了相关研究:Selim Mimaroglu等人[1]提出对位向量使用裁剪技术,提高DBSCAN算法的执行时间;H. Zhou 等人[2] 针对DBSCAN中全局参数EpsMinPts人工确定的问题,发现距离分布矩阵的每列数据符合一定的数学统计特性,自适应确定出聚类全局参数;H. Jiang等人[3]提出一种基于划分的DBSCAN算法,旨在解决DBSCAN算法在内存占用,处理高维数据和密度分布不均数据聚类效果不好等问题;S.-H. Yue等人[4]提出一种基于距离空间统计特性的方法,确定全局参数;B. Borah等人[5]针对DBSCAN处理整个数据库时内存占率大的问题,提出一种改进的基于抽样的DBSCAN算法,可以有效聚类大规模空间数据;B. Liu[6]提出一种基于密度的快速聚类方法,按照特定维的坐标排序后,选择有序的未被标记的在核心对象邻域以外的点作为种子扩展簇,这样执行区域查询的频率能够降低,对象转换为核函数提高了聚类精度,一定程度上减少了对密度阈值的依赖性;M. Yu[7]提出一种基于概率分布的DBSCAN算法;S. Jahirabadkar[8]等人提出两种聚类方式,一种方式可自适应确定参数Eps和另一种基于每个维度的数据得出子维数据的Eps参数;Z. Xiong[9]等人针对多密度分布数据,提出DBSCAN-DLP算法,通过分析数据的统计特性将数据集按照密度分级,再对各级别进行Eps参数估计;D. Kellner[10]等人提出一种基于格点的DBSCAN算法,解决了输入参数难以估计的问题。

    综上所述,基于密度聚类算法的改进点主要集中在全局参数的选择以及如何提高密度聚类效率等问题上。DBSCAN全局参数选择根据k-dist曲线人工确定,过程繁琐,实用性不高。其他基于统计分析的方法,部分以特定数据分布确定全局参数,而数据分布存在不确定性,以特定分布规定不能准确反映数据的分布特性,使计算出的全局参数不准确;在提高密度聚类效率问题上,主要集中在区域查询中的代表对象选择方面,但是选择的代表对象进行区域查询时存在丢失对象现象,也有对丢失对象进行查漏操作,在一定程度上增加了区域查询的复杂度。

    1 DBSCAN 算法及改进算法思路

    DBSCAN[2]是一种经典的基于密度聚类算法,可以自动确定簇的数量,并能够发现任意形状的簇。Eps近邻表示一个给定对象的Eps半径内的近邻称为该对象的Eps近邻,表示为NEps(p)

    1

    直接密度可达是指对于给定的MinptsEps,从对象q可以直接密度可达p,需要满足的条件是:

    2

    由于DBSCAN算法的全局参数EpsMinPts的选取依赖于人工干预,对密度分布均匀的数据根据k-dist曲线升序排列后,人为选择曲线变化幅度开始陡升的点作为Eps参数,并且确定MinPts参数为固定常量4,实施过程繁琐,依赖于人工干预。本文提出一种全局参数自适应选择的方法,根据数据的距离空间的统计分布特性,统计出k-dist值的分布情况,再进行曲线拟合,拟合出分布曲线,通过计算拟合曲线的拐点处对应的值,自适应确定出Eps参数,并根据数据中每个点Eps领域内点数的分布情况,计算出参数MinPts

    DBSCAN以一个核心对象P来拓展一个簇,通过对包含在P邻域内的点进行区域查询扩展簇。由于包含在P中邻域的对象相互交叉QP的邻域内的一个对象,如果它的邻域被P中其他对象的邻域所覆盖,那么Q的区域查询操作就可以省略,Q不需要作为种子对象用于类的扩展。因此,用于Q的区域查询时间和Q作为核心对象的内存占用都可以被省去。而一个核心对象边界的对象有利于作为候选对象被选为种子因为内部对象邻域往往会被外部对象的邻域覆盖因此抽样种子实际上是选择代表对象能够准确描绘出核心对象邻域形状的一个问题。实际上,对于密度聚类,在核心对象邻域内的相当一部分种子对象可以被忽略,而选择出核心对象边界的部分代表对象来进行类的扩展,从而达到减少区域查询频度的目的。

    所以,为了自适应确定合适的全局参数EpsMinPts,减少内存占用量和I/O消耗,提高DBSCAN的计算效率, 基于这些分析,本文提出一种改进的自适应快速算法AF-DBSCAN(Adaptive and FastDensity-Based Spatial Clustering of Applications with Noise),旨在以自适应方式确定合理的全局参数EpsMinPts,以及区域查询时选择部分具有代表性的对象作为种子对象进行类扩展,而不采用所有核心对象的邻域对象作为种子进行类拓展的方式。改进算法算法描述如下:

    1)自适应确定全局参数EpsMinPts;(2)将所有点分类,分别标记为核心点,边界点和噪声点;(3)删除标记出的噪声点;(4)连接距离在Eps距离累的所有核心点,并归入到同一簇中;(5)各个簇中的核心点对应种子代表对象的选择;(6)遍历数据集,根据选择的代表对象进行区域查询,将边界点分入与之对应核心点的簇中。如果数据集合中所有的点都被处理,则算法结束。

    2 AF-DBSCAN聚类算法细节

    2.1 参数Eps与参数MinPts的确定

    由于密度衡量指标单一,数据集主要针对簇密度差异不明显的数据。根据输入数据集D计算出距离分布矩阵DISTn×n,如公式(3)所示:

    3

    其中,n为数据集D的对象数目。DISTn×n是一个n行和n列的实对称矩阵,其中每个元素表示数据集D中对象i和对象j之间的距离。

    计算DISTn×n中的每个元素的值,然后逐行按照升序排列。用DISTn×i表示DISTn×n中第i列的的值。对DISTn×i中每一列进行升序排列得到KNN分布,如图1所示。

     

    1 KNN分布图

    其中,k=1,…,45,根据k-dist分布曲线可以看出,k=4dist4曲线可以反映出其他distk曲线的形状。本文选择k=4distkk-最近邻距离)的数据进行统计分析,统计dist4的概率分布,如图2所示。

     

    2 distk(k=4)概率分布图

    由图1可以发现任何一条曲线都是在平缓变化后急剧上升,Distk中大部分值落在一个比较密集的区域内,因此可以判断Distk中大部分值应落在一个比较密集的区域内(曲线平缓段),如果可以通过数学方法找出distk中平缓变化到急剧上升处的点或者distk概率分布最为密集的区域,可确定扫描半径参数Eps,所以本文选择图1distk拐点处的值为Eps。由图2可以看到Distk的概率分布情况,假如能够通过数学方法找到分布曲线的峰值,也可以用峰值点所对应的k-最近邻距离值(横坐标刻度)作为Eps

    对于概率分布数据,通过分析数据集的统计特性,建立统计模型对数据集进行曲线拟合[12]。本文通过实验对概率分布使用傅立叶、高斯和多项式三种典型曲线拟合方法,如图3所示。其中,Gaussian曲线拟合方法的效果最佳,但是由于概率分布的拟合精度过低,不可用于全局参数Eps的估计SSE: 312.7R-square: 0.6755,调整R-square: 0.6514RMSE: 3.403,参数SSERMSE越接近0越拟合准确,调整后的R-squareR-square越接近于1越准确高斯拟合曲线如公式(4)所示:

     (4)


    3 Gaussian拟合曲线

    根据KNN升序排列曲线确定Eps,对dist4曲线进行拟合,对于升序排列得到KNN分布数据,采用三种拟合方法进行曲线拟合,实验发现高斯拟合精度高,但拟合阶数高,计算复杂度高,傅立叶拟合精度不高,而多项式拟合不仅拟合阶数低,而且拟合精度高,计算复杂的低,拟合结果为SSE:0.04636R-square: 0.9883,调整 R-square: 0.988RMSE: 0.01788,如图4所示。多项式曲线拟合如公式(5)所示:

    5

     

    4多项式拟合曲线

    根据多项式拟合曲线,求解曲线的拐点,对y求二次导可得公式(6

    6

    求解二次导方程得x的解,见公式(7

    7

    由于较小的值为靠近边界的点,取x解中较大的值,舍去较小的值,将其带入公式(5),可以得到EPS=f(x)。在Eps确定之后,需要确定MinPts的值。首先,根据每个点领域数据点的统计分布特性,依次计算出每个点的Eps-邻域的对象数量,然后计算数据对象的数学期望,即MinPts的值,如公式(8)所示,

    8

    其中,pi表示在点iEps邻域的点数。

    本文将密度聚类算法与基于统计模型相结合的方法,基于数理统计理论,假定数据集由统计过程产生,并通过找出最佳拟合模型来描述数据集,自适应计算出最优全局参数EpsMinpts

    2.2 种子代表对象的选择

    本文提出一种改进的基于DBSCAN的快速聚类算法。在通过选用核心对象附近区域包含的所有对象的代表对象作为种子对象来扩展类,该算法减少了区域查询的次数,减低了聚类时间和I/O开销。

    对于一个给出EpsMinPts的核心对象P,为了便于阐述,仅考虑2维对象,算法可用于其他大于两维的高维对象,代表对象选择过多则难以发挥算法效率,选择过少则容易造成对象丢失,影响算法聚类质量。本文提出一种以代表对象扩展类的方法,针对FDBSCAN[11]算法在区域查询后,在第一轮核心点区域查询时无丢失对象现象,而在以种子对象进行类扩展时,产生丢失对象,需要选择足够多的代表对象,而I-DBSCAN[5]在二维数据中采用至多8个代表对象,不存在对象丢失的情况。文本结合FDBSCANI-DBSCAN,在第一轮区域查询时采用4个代表对象进行类扩展,在继续扩展类的时候,采用选择8个代表对象进行类扩展,在提高查询效率的基础上,解决了类扩展时丢失对象的问题。

    在自适应得出EpsMinPts后,本文提出的代表对象选择方式如下:以核心对象p为中心,并以Eps为半径画圆,以对象p为原点画坐标系交圆周于ACEG四点,再画两条分别与x轴成45度和135度角的两条直径交圆周于BDFH四点。在第一轮的代表对象选择时,以核心点边界的ACEG点为参照,在PEps区域中分别选择离ACEG点最近的点作为代表对象,当对于不同参照点存在离其距离最近的点为同一点时,此点只能被选择一次,且属于第一个参考点的代表对象。如果对象是n维数据,则至多可以选择2n个代表对象。

    在继续扩展类选择代表对象时,以核心点边界的ABCDEFGH点为参照点,代表对象选取原则在PEps区域中选择离参考点对象最近的点作为代表对象,即使一个代表对象到两个以上的参考点都是最近的,它也只被选一次,且归入第一个参考点的代表对象。因此,在2维空间范围内对任一对象的被选代表对象数最多为8个。一般情况下,对n维空间,由于有3n-1个参考点和2n个象限,因此被选种子数最多为3n-1个,按照以上方式实现区域查询,有效提高聚类效率以及解决对象丢失的问题。

    3.实验与分析

    本文算法采用java语言编程实现,并在Windows XP系统和eclipse环境下调试运行,PC机硬件配置:Pentium(R) CPU3G内存, 300GB硬盘。

    3.1实验分析

    为了验证本文改进算法的参数自适应选择以及区域查询方式的有效性,根据数据集的维度,数据量以及数据密度分布三种标准进行数据库地选择,选取UCI数据库中的4种典型数据集IrisWineGlasscmc。根据聚类准确度和时间特性分析两项指标对DBSCANI-DBSCAN[2]AF-DBSCAN算法性能进行比较分析,其中聚类准确度采用F-Measure[3]DBSCAN中的Eps值得设定依据k-dist曲线,选取Dist4曲线图进行参数确定,如图5所示。


    5 dist4曲线图

    根据图中平缓变化后急剧上升处对应的k-dist值作为全局参数Eps的值,且Minpts值设为4。可以得到三种数据集IrisWineGlasscmc的(MinptsEps)分别为(40.436)、(427.330)、(43.700)和(41.732)。本文提出的AF-DBSCAN的(MinptsEps)分别为(70.389)、(629.870)、(42.695)和(51.646)。聚类结果如表1所示。由表1可以看出,本文提出的AF-DBSCAN算法自适应计算出的全局参数减少了人为根据k-dist曲线确定全局参数Eps的误差及工作量,以及设定MinPts为固定值4,而使聚类结果达不到全局最优的效果。通过比较分析4种数据集的聚类结果,AF-DBSCANF-Measure值均优于其他两种典型算法,尤其在IrisGlass数据集上,聚类精度比DBSCAN算法分别高12.55%13.18%。而I-DBSCAN算法规定数据符合泊松分布,对于不同数据集其F-Measure值不稳定,不能适应不同统计特性的数据集。由于密度衡量指标单一,AF-DBSCAN算法适用于簇密度差异不明显的数据集。经过区域查询改进后的AF-DBSCAN算法,算法运行速度明显比DBSCANI-DBSCAN算法快,有效减少了密度聚类的时间。

    4.结论

    针对DBSCAN算法的参数选取困难,计算效率低以及区域查询中代表对象选择后类扩展易丢失对象点等问题,提出一种改进的自适应快速AF-DBSCAN聚类算法,通过分析数据的KNN的数学统计规律,辅助用户自适应确定全局参数EpsMinPts。通过改进的区域查询方法,有效提高类扩展的效率,AF-DBSCAN算法解决了DBSCAN算法人工干预,给定全局参数导致聚类质量恶化以及大数据集计算效率低的问题。


    1实验比较

    数据集

    算法

    MinPts

    Eps

    运行时间(s

    准确度

    Iris

    DBSCAN

    4

    0.436

    0.342

    0.7407

    I-DBSCAN

    6

    0.405

    0.335

    0.8803

    AF-DBSCAN

    7

    0.389

    0.157

    0.8662

    Wine

    DBSACN

    4

    27.330

    0.481

    0.5994

    I-DBSCAN

    6

    22.890

    0.467

    0.5667

    AF-DBSCAN

    6

    29.870

    0.172

    0.6091

    Glass

    DBSCAN

    4

    3.700

    0.516

    0.6561

    I-DBSCAN

    4

    2.980

    0.525

    0.6522

    AF-DBSCAN

    4

    2.695

    0.188

    0.7879

    cmc

    DBSCAN

    4

    1.732

    3.239

    0.4491

    I-DBSCAN

    6

    1.691

    3.145

    0.4491

    AF-DBSCAN

    5

    1.646

    1.266

    0.4491



    参考文献

    [1]S. Mimaroglu and E. Aksehirli, "Improving DBSCAN's execution time by using a pruning technique on bit vectors,"Pattern Recognition Letters,vol. 32, pp. 1572-1580, 2011.

    [2]H. Zhou, P. Wang, and H. Li, "Research on adaptive parameters determination in DBSCAN algorithm,"Journal of Information and Computational Science,vol. 9, pp. 1967-1973, 2012.

    [3]H. Jiang, J. Li, S. Yi, X. Wang, and X. Hu, "A new hybrid method based on partitioning-based DBSCAN and ant clustering,"Expert Systems with Applications,vol. 38, pp. 9373-9381, 2011.

    [4]S.-H. Yue, P. Li, J.-D. Guo, and S.-G. Zhou, "Statistical information-based clustering approach in distance space,"Journal of Zhejiang University: Science,vol. 6 A, pp. 71-78, 2005.

    [5]B. Borah and D. K. Bhattacharyya, "An Improved Sampling-Based DBSCAN for Large Spatial Databases," inProceedings of International Conference on Intelligent Sensing and Information Processing, ICISIP 2004, January 4, 2004 - January 7, 2004, Chennai, India, 2004, pp. 92-96.

    [6]B. Liu, "A fast density-based clustering algorithm for large databases," in2006 International Conference on Machine Learning and Cybernetics, August 13, 2006 - August 16, 2006, Dalian, China, 2006, pp. 996-1000.

    [7]M. Yu, G. Yuling, and S. Shaoyun, "The algorithm of DBSCAN based on probability distribution," in 5th International Symposium on IT in Medicine and Education, ITME 2013, July 19, 2013 - July 21, 2013, Xining, China, 2014, pp. 2785-2792.

    [8]S. Jahirabadkar and P. Kulkarni, "Algorithm to determine ε-distance parameter in density based clustering,"Expert Systems with Applications,vol. 41, pp. 2939-2946, 2014.

    [9]Z. Xiong, R. Chen, Y. Zhang, and X. Zhang, "Multi-density DBSCAN algorithm based on Density Levels Partitioning,"Journal of Information and Computational Science,vol. 9, pp. 2739-2749, 2012.

    [10]D. Kellner, J. Klappstein, and K. Dietmayer, "Grid-based DBSCAN for clustering extended objects in radar data," in2012 IEEE Intelligent Vehicles Symposium, IV 2012, June 3, 2012 - June 7, 2012, Alcal de Henares, Madrid, Spain, 2012, pp. 365-370.

    [11]周水庚,周傲英,曹晶, 胡运发.一种基于密度的快速聚类算法[J].计算机研究与发展,2000,11: 1287- 1292.

    [12]夏鲁宁,荆继武. SA-DBSCAN:一种自适应基于密度聚类算法[J].中国科学院研究生院学报,2009,04:530- 538.

     

    基金项目国家自然科学基金(61373126)江苏省产学研联合创新资金-前瞻性联合研究项目(BY2013015-33)基金

    展开全文
  • 1DBSCAN聚类算法 2 参数选择 3 步骤 4 实例 5 常用的评估方法:轮廓系数 6DBSCAN 算法评价及改进 基于密度的聚类是根据样本的密度分布来进行聚类。通常情况下,密度聚类从样本密度的角度出来,来考查样本之间...

    目录

    1 DBSCAN聚类算法

    2 参数选择

    3 步骤

    4 实例

    5 常用的评估方法:轮廓系数

    6 DBSCAN 算法评价及改进


            基于密度的聚类是根据样本的密度分布来进行聚类。通常情况下,密度聚类从样本密度的角度出来,来考查样本之间的可连接性,并基于可连接样本不断扩展聚类簇,以获得最终的聚类结果。其中最著名的算法就是 DBSCAN 算法。

            DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意形状的簇,它将簇定义为密度相连的点的最大集合

    1 DBSCAN聚类算法

            如下图所示,下面这些点是分布在样本空间的众多样本,现在我们的目标是把这些在样本空间中距离相近的聚成一类。我们发现A点附近的点密度较大,红色的圆圈根据一定的规则在这里滚啊滚,最终收纳了A附近的5个点,标记为红色也就是定为同一个簇。其它没有被收纳的根据一样的规则成簇。(形象来说,我们可以认为这是系统在众多样本点中随机选中一个,围绕这个被选中的样本点画一个圆,规定这个圆的半径以及圆内最少包含的样本点,如果在指定半径内有足够多的样本点在内,那么这个圆圈的圆心就转移到这个内部样本点,继续去圈附近其它的样本点,类似传销一样,继续去发展下线。等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值,就停止了。那么我们称最开始那个点为核心点,如A,停下来的那个点为边界点,如B、C,没得滚的那个点为离群点,如N)。

             

            基于密度这点有什么好处呢,我们知道kmeans聚类算法只能处理球形的簇,也就是一个聚成实心的团(这是因为算法本身计算平均距离的局限)。但往往现实中还会有各种形状,比如下面两张图,环形和不规则形,这个时候,那些传统的聚类算法显然就悲剧了。于是就思考,样本密度大的成一类,就是DBSCAN聚类算法。

                

    2 参数选择

            上面提到了红色圆圈滚啊滚的过程,这个过程就包括了DBSCAN算法的两个参数:半径 eps 和密度阈值 MinPts。

            (1)半径:半径是最难指定的 ,大了,圈住的就多了,簇的个数就少了;反之,簇的个数就多了,这对我们最后的结果是有影响的。我们这个时候K距离可以帮助我们来设定半径r,也就是要找到突变点,比如:
              

            以上虽然是一个可取的方式,但是有时候比较麻烦 ,大部分还是都试一试进行观察,用k距离需要做大量实验来观察,很难一次性把这些值都选准。 

            (2)MinPts:这个参数就是圈住的点的个数,也相当于是一个密度,一般这个值都是偏小一些,然后进行多次尝试

            国外有一个特别有意思的网站:https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/,它可以把我们DBSCAN的迭代过程动态图画出来。

    3 步骤

    1. 以每一个数据点 xi 为圆心,以 eps 为半径画一个圆圈。这个圆圈被称为 xi 的 eps 邻域
    2. 对这个圆圈内包含的点进行计数。如果一个圆圈里面的点的数目超过了密度阈值 MinPts,那么将该圆圈的圆心记为核心点,又称核心对象。如果某个点的 eps 邻域内点的个数小于密度阈值但是落在核心点的邻域内,则称该点为边界点。既不是核心点也不是边界点的点,就是噪声点。
    3. 核心点 xi 的 eps 邻域内的所有的点,都是 xi 的直接密度直达。如果 xj 由 xi 密度直达,xk 由 xj 密度直达。。。xn 由 xk 密度直达,那么,xn 由 xi 密度可达。这个性质说明了由密度直达的传递性,可以推导出密度可达。
    4. 如果对于 xk,使 xi 和 xj 都可以由 xk 密度可达,那么,就称 xi 和 xj 密度相连。将密度相连的点连接在一起,就形成了我们的聚类簇。

            用更通俗易懂的话描述就是如果一个点的 eps 邻域内的点的总数小于阈值,那么该点就是低密度点。如果大于阈值,就是高密度点。如果一个高密度点在另外一个高密度点的邻域内,就直接把这两个高密度点相连,这是核心点。如果一个低密度点在高密度点的邻域内,就将低密度点连在距离它最近的高密度点上,这是边界点。不在任何高密度点的 eps  邻域内的低密度点,就是异常点。

    • 噪声: 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”
    • 边界点:边界点不是核心点,但落在某个核心点的邻域内。

          周志华《机器学习》书上给的伪代码如下。

            

            公式性有点强,用语义表达算法的伪码如下:

    1. 根据 eps 邻域和密度阈值 MinPts ,判断一个点是核心点、边界点或者离群点。并将离群点删除
    2. 如果核心点之间的距离小于 MinPts ,就将两个核心点连接在一起。这样就形成了若干组簇
    3. 将边界点分配到距离它最近的核心点范围内
    4. 形成最终的聚类结果

    4 实例

            根据所给的数据通过对其进行DBSCAN算法,以下为算法的步骤(设n=12,用户输入ε=1,MinPts=4)

                          

    DBSCAN聚类过程

            第1步,在数据库中选择一点1,由于在以它为圆心的 以1为半径的圆内包含2个点(小于4),因此它不是核心点,选择下一个点。

            第2步,在数据库中选择一点2,由于在以它为圆心的,以1为半径的圆内包含2个点, 因此它不是核心点,选择下一个点。

            第3步,在数据库中选择一点3,由于在以它为圆心的,以1为半径的圆内包含3个点, 因此它不是核心点,选择下一个点。

          

            第4步,在数据库中选择一点4,由于在以它为圆心的,以1为半径的圆内包含5个点, 因此它是核心点,寻找从它出发可达的点(直接可达4个,间接可达3个), 聚出的新类{1,3,4,5,9,10,12},选择下一个点。

                

            第5步,在数据库中选择一点5,已经在簇1中,选择下一个点。

            第6步,在数据库中选择一点6,由于在以它为圆心的,以1为半径的圆内包含3个点, 因此它不是核心点,选择下一个点。

               

            第7步,在数据库中选择一点7,由于在以它为圆心的,以1为半径的圆内包含5个点, 因此它是核心点,寻找从它出发可达的点,聚出的新类{2,6,7,8,11},选择下一个点。

                   

            第8步,在数据库中选择一点8,已经在簇2中,选择下一个点。

            第9步,在数据库中选择一点9,已经在簇1中,选择下一个点。

            第10步,在数据库中选择一点10,已经在簇1中,选择下一个点。

            第11步,在数据库中选择一点11,已经在簇2中,选择下一个点。

            第12步,选择12点,已经在簇1中,由于这已经是最后一点所有点都以处理,程序终止。

    算法执行过程:

     

    5 常用的评估方法:轮廓系数

            聚类算法中最常用的评估方法——轮廓系数(Silhouette Coefficient):

                

            计算样本i到同簇其它样本到平均距离ai。ai越小,说明样本i越应该被聚类到该簇(将ai称为样本i到簇内不相似度)。
            计算样本i到其它某簇Cj的所有样本的平均距离bij,称为样本i与簇Cj的不相似度。定义为样本i的簇间不相似度:                                                     bi=min(bi1,bi2,...,bik2)

    • si接近1,则说明样本i聚类合理
    • si接近-1,则说明样本i更应该分类到另外的簇
    • 若si近似为0,则说明样本i在两个簇的边界上

    DBSCAN 算法评价及改进

    DBSCAN优点:

    1、对噪声不敏感。这是因为该算法能够较好地判断离群点,并且即使错判离群点,对最终的聚类结果也没什么影响

    2、能发现任意形状的簇。这是因为DBSCAN 是靠不断连接邻域呢高密度点来发现簇的,只需要定义邻域大小和密度阈值,因此可以发现不同形状,不同大小的簇

    DBSCAN 缺点:

    1、对两个参数的设置敏感,即圈的半径 eps 、阈值 MinPts。

    2、DBSCAN 使用固定的参数识别聚类。显然,当聚类的稀疏程度不同,聚类效果也有很大不同。即数据密度不均匀时,很难使用该算法

    3、如果数据样本集越大,收敛时间越长。此时可以使用 KD 树优化

    DBSCAN的时间复杂性:

            DBSCAN算法要对每个数据对象进行邻域检查时间性能较低。DBSCAN的基本时间复杂度是 O(N*找出Eps领域中的点所需要的时间), N是点的个数。 最坏情况下时间复杂度是O(N2)在低维空间数据中,有一些数据结构如KD树,使得可以有效的检索特定点给定距离内的所有点, 时间复杂度可以降低到O(NlogN)。

    DBSCAM的空间复杂性:

            在聚类过程中,DBSCAN一旦找到一个核心对象,即以该核心对象为中心向外扩展。 此过程中核心对象将不断增多,未处理的对象被保留在内存中。若数据库中存在庞大的聚类, 将需要很大的存来存储核心对象信息,其需求难以预料。当数据量增大时,要求较大的内存支持 I/0 消耗也很大;低维或高维数据中,其空间都是O(N)。

     

     

    https://www.cnblogs.com/stormtides/p/11891384.html

    https://blog.csdn.net/denghecsdn/article/details/82793940

    https://blog.csdn.net/huacha__/article/details/81094891

    https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

    展开全文
  • 针对传统的DBSCAN(Density-Based Spatial Clustering of Application with Noise,DBSCAN聚类算法全局参数设置不合理、参数选取困难、无法识别重叠模块的问题,以及人工蜂群优化算法(Artificial Bees Colony,...
  • Dbscan算法做如下改进:(1)对于核心对象 ,其邻域不再做进一步考查 ,而是将其归为某个簇 。 该簇有可能是核心对象所在簇 ,也有可能是与其他簇合并过的簇 。 (2)对于边界对象 ,进一步考查其邻域中是否存在...
  • 改进的图像分割算法:运用SLIC超像素分割和DBSCAN聚类算法相结合的方法实现图像分割资源下载此资源下载价格为3D币,请先登录资源文件列表Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/rgb2lab....

    改进的图像分割算法:运用SLIC超像素分割和DBSCAN聚类算法相结合的方法实现图像分割

    资源下载此资源下载价格为3D币,请先登录

    资源文件列表

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/rgb2lab.m , 1157

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/slic.m , 17145

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/circularstruct.m , 677

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/cleanupregions.m , 5658

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/dbscan.m , 5381

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/drawregionboundaries.m , 2374

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/finddisconnected.m , 2646

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/makeregionsdistinct.m , 2197

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/maskimage.m , 1167

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/mcleanupregions.m , 4455

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/regionadjacency.m , 4638

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/renumberregions.m , 2414

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/testdbscan.m , 2326

    Image Segmentation using SLIC SuperPixels and DBSCAN Clustering/ע.txt , 526

    展开全文
  • 针对DBSCAN算法对Eps和Minpts值要求敏感可能得到聚类效果不佳的缺点,提出了聚类前对点的K距离进行降序排列和设置有密度水平的Eps值的过滤式DBSCAN改进算法,以提高聚类的性能和结果
  • Python实现经纬度空间点DBSCAN聚类

    万次阅读 多人点赞 2020-09-22 09:33:32
    博主前期科研工作中,涉及到要对某个地区的一些空间点进行聚类分析,想到读研期间,曾经用DBSCAN聚类算法实现了四线激光雷达扫描的三维点云数据聚类(论文题目:基于改进DBSCAN算法的激光雷达目标物检测方法),当初...
  • DBSCAN 获得的最终聚类结果取决于算法运行过程中处理对象的顺序。 在本文中,提出了一种改进版的 DBSCAN 算法来解决这个问题。 结果表明,通过使用修改后的算法聚类结果得到了显着改善,特别是对于包含具有...
  • 针对DBSCAN算法对数据分布不均匀和大规模数据处理问题上的不足,提出了一种新的整合算法算法使用信息熵和蚁群聚类技术对聚类数据集进行代表性子集选择,在子集基础上进行DBSCAN聚类,实验证明这一算法能显著降低I/...
  • 聚类算法改进——DBSCAN

    千次阅读 2019-07-04 11:16:08
    聚类算法改进——DBSCAN K-means算法有几个明显的缺点,例如需要用户指定聚类数目,而且聚类的形状比较有局限性。 这里考虑采用DBSCAN(Density - Based Spatial Clustering of Applications with Noise) 该算法...
  • 针对基于密度的DBSCAN算法对于输入参数敏感、无法聚类多密度数据集等问题,提出了一种贪心的DBSCAN改进算法(greedy DBSCAN)。算法仅需输入一个参数MinPts,采用贪心策略自适应地寻找Eps半径参数进行簇发现,利用...
  • 基于密度的聚类是聚类算法中的一种,其主要优点是可以发现任意形状的簇,但处理大数据集时效果不佳,为此提出了一种改进的算法M-DBSCAN,...实验结果证明,M-DBSCAN聚类算法在聚类质量及速度上都比原DBSCAN有较大提高。
  • DDBSCAN(论文:Ddbscan: a density detection dbscan algorithm in e-commerce sites evaluation) 一、首先介绍DBSCAN的步骤,毕竟是它基础上的优化 DBSCAN这个博客讲得简单易懂 ...
  • DBSCAN聚集算法改进,可用于车辆GPS经纬度聚集计算

    千次阅读 热门讨论 2016-09-08 09:52:11
    DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意...
  • 提出了一种改进式的空间聚类算法,研究针对瓦斯灾难信息特征提取的具体方法,将DBSCAN聚类算法应用在煤矿瓦斯监测系统中,通过数据的集成和选取、确定目标、结果表述、评价等多个步骤来实现该算法,发挥仿真和结果的作用...
  • 针对现有道路事故多发段鉴别方法在阈值选择中存在的缺点和局限,提出了一种改进DBSCAN聚类算法用于鉴别事故多发段。聚类算法中最小密度点的选取结合了累计频率曲线方法,能实现阈值的自适应选取。算法应用于安徽省...
  • 基于密度聚类算法改进

    千次阅读 2016-07-28 22:45:44
    使用基于密度的聚类算法,进行高维特征的聚类分析,从高维数据中提取出类似的有用信息,从而简化了特征数量,并且去除了部分冗余信息。 在聚类算法中,有这样几种算法: 划分的算法, K-Means 层次的方法, CURE 基于密度的...
  • 一、经典DBSCAN的不足 1.由于“维度灾难”问题,应用高维数据效果不佳 ...二、DBSCAN在高维数据的改进 目前的研究有Grid-based和approx等方向,基于Grid-based结构的有Fast-DBSCAN,时间复杂度最坏是O(n...

空空如也

空空如也

1 2 3 4 5 6
收藏数 102
精华内容 40
关键字:

dbscan聚类算法改进