论文研究-自适应确定DBSCAN算法参数的算法研究.pdf

所需积分/C币:46 2019-09-16 11:09:00 1.63MB .PDF
收藏 收藏
举报

传统DBSCAN算法需要人为确定[Eps]和[MinPts]参数,参数的选择直接决定了聚类结果的合理性,因此提出一种新的自适应确定DBSCAN算法参数算法,该算法基于参数寻优策略,通过利用数据集自身分布特性生成候选[Eps]和[MinPts]参数,自动寻找聚类结果的簇数变化稳定区间,并将该区间中密度阈值最少时所对应的[Eps]和[MinPts]参数作为最优参数。实验结果表明,该算法能够实现聚类过程的全自动化并且能够选择合理的[Eps]和[MinPts]参数,得到了高准确度聚类结果。
李文杰,等:自适应确定 DBSCAN算法参数的算法研究 2019,55(5)3 密度阈值太大,可能导致同簇集合内部被划分为多值进行计算,得到K平均最近邻距离向量。具体步骤 个集合;密度阈值太小,可能导致不同簇集合之间被合如下 并,因此确定合适的密度阈值十分关键。 步骤计算数据集D的距离分布矩阵,即 本文通过采用不同的密度阈值进行 DBSCAN算法 ={Dst(i11≤i≤7,1≤j≤m 聚类实验,发现以下规律 式中,Dxn为nXn的实对称矩阵;n为数据集D所包 (1)随着密度阈值υe灬iy参数的递减,聚类结果的含的对象数量;Dist(j为数据集D屮第i个对象到第 簇数通常会发生收敛,并在一定密度阈值区间保持稳个对象的距离 定。这是由丁高密度数据集合之间存在着低密度区城, 步骤2对距离矩阵Dx的每一行元素进行升序排 且低密度区域存在着一定的宽度因此本文认为该密度序,则第1列的元素所组成的距离向量D表示对象到 阈值区问对应的聚类结果簇数是正确的。 白身的距离,全为0。第K列的元素构成所有数据点的 (2)在聚类结果簇数正确的前提下,密度阈值越小,k最近邻距离向量Dk。 则噪声率越低,而且聚类结果的F值呈增大趋势。这 步骤3对向量Dk中的元素求平均,可得到向量 是由于随着密度值的降低,越多的低密度数据点被划Dk的K平均最近邻距离D,并将其作为候选E参 分进簇,因此噪声率变低,同时F值的增大则表明准确数。对所有的K值进行计算,则得到E参数列表 率增加,聚类结果趋于正确。 D,表示为: 综上所述,本文认为聚类结果簇数正确的前提下, DE={Dk≤K≤n 密度阈值越小,则聚类效果越好。 图2为S3数据集的E参数列表与K值的关系曲 32算法实现 线,可见随着K值的增加Eps参数平稳增大。 KANN- DBSCAN算法的关键在于确定合适的密度 阈值参数列表,列表的取值范围和参数间距,决定了聚 70 类的精确度和运算量,需要在二者之间寻找平衡点。基 于以上考虑本文提出利用数据集自身的空间分布特性, 基于K-平均最近邻算法(K- Average Nearest Neighbor, 40 KANN)和数学期望法生成密度阈值列表 S3是一个15种类别共5000个对象的二维数据 集叫,其分布如图1所示,为方便描述算法,下文以该数 10 据集为例进行具体分析 110002000300040005000 图2Eps参数列表与K值的关系图 322生成 Minpts参数列表 3”,·善 采用数学期望法生成 MinPts参数列表。对于给定 的Ep参数列表,依次求出每个Ep参数对应的Ep邻 域对象数量,并计算所有对象的E邻域对象数量的数 学期望值,作为数据集D的邻域密度阈值MiPs参数, 表示为: 100 Minpts= l 77 图1S3数据集散点图(N=5000,C=15) 式中,P为第i个对象的E邻域对象数量,n为数据 321生成E参数列表 集D中的对象总数。 采川K-平均最近邻法和数学期望法生成Ep列表 对集合D中的候选EPs参数依次进行计算,得到 K-平均最近邻法是平均最近邻法的延伸,该算法的S3数据集邻域密度阈值MiP参数值与K值的关系如 基本思想是通过计算数据集υ中每个数据点与其第K图3所示,随着K值的增加,MinP的参数值呈现平稳 个最近邻数据点之间的K-最近邻距离,并对所有数据 升的趋势 点的K-最近邻距离求平均值,得到数据集的K平均最 基于生成的Ep和MPs参数列表,利用式将对应 近邻距离(K-1时,即为平均最近邻距离)对所有的K的参数进行计算可得到 Density参数列表,如图4所示 2019,55(5) Computer Engineering and4 pplications计算机工程与应用 5000 MinP参数。 4000 利用述3个步骤对S3数据集进行分析,得到聚类 结果簇数与K值的关系如图5所示,可见当K=6时 300 聚类结果的簇数进入稳定区间,直到K=62结束,因此 K-62对应的K平均最近邻距离Dk-2即为最优Es 参数,进而利用式得到最优MmPs参数,分别为Eps 1000- =-- 3825, Minpts=87。 10002000300040005000 13MmP参数列表与K值的关系图 可见 Density参数随着K值的增大递减,关系曲线先急 剧降低后趋于线性,说明 Density参数对在一定范围内 20 对K值比较敏感,这与数据集自身的分布特性相关 Density参数列表的生成完全基于数据集本身,无需人 为干预,反映了数据集的分布特性,因此作为参数输入 16102030405062708090100 非常合适。 3.0 图5聚类结果簇数与K值的关系图 图6为聚类结果的F值曲线图,可见选取的最优参 数聚类结果评价较优。将最优参数输入 DBSCAN算 2.0 法,得到聚类结果如图7所示,共生成15个簇,与数据集 15 标识的类别数一致,证明本文算法可以自动选择合适的 1.0 E和 Minis参数,有效发现和划分数据集中的高密度 0.5 nannI 0.8 10002000300040005000 0.7 图4Deiy参数列表与k值的关系图 0.6 山于在实际应川中, DBSCAN算法的输入为Ep和 MinP参数,因此仍将当前K值对应的 Densit参数分 0.5 解为对应的E和 MinPts参数 0.4 3.23自适应确定最优参数 KANN-DBSCAN算法的具体实现步骤如下: 0. 1102030405062708090100 步骤Ⅰ根据κ-平均最近邻法求出数据集D的侯选 ps参数集合DE。 图6聚类结果F值与K值的关系图 步骤2依次选用不同K值(K=1,2,…,n)所对应 100 Noise Cluster #1 的K-平均最近邻距离,即依次选用集合D2中的元素 80 Cluster #3 作为候选F参数和由公式(8)得到MiP参数,输入 Cluster #4 Cluster #5 DBSCAN算法对数据集进行聚类分析,分别得到不同 60 Cluster #G K值下所生成的簇数。当生成的簇数迕续一次相同时, 40 Cluster #g 本文认为聚类结果趋丁稳定,记该簇数N为最优簇数。 Cluster #10 Cluster #f) 步骤3继续执行步骤2,直到生成的簇数不再为 Cluster #12 x Cluster #f 13 并选用当簇数为N时所对应的最大K值作为最优 x Cluster #14 K值。最优K值对应的K-平均最近邻距离Dk则为 2040608000 Cluster#15 最优Ep参数,最优K值对应的MmP参数则为最优 图7基于 KANN-DBSCAN的S3数据集聚类结果 李文杰,等:自适应确定 DBSCAN算法参数的算法研究 2019,55(5) 4实验与结果分析 种类别共788个对象的二维数据集; Compound是一个 KANN-DBSCAN算法采川 Matlab语言实现,为了6种类别共399个对象的二维数据集;Rl5是一个15 验证本文算法的有效性和先进性,实验通过采用人工标种类别共600个对象的二维数据集;D31是一个31种类 记数据集和地表火点数据集进行聚类分析,并将利用本别共3100个对象的二维数据集。 文算法得到的结果与采用AF- DBSCAN、I- DBSCAN和 图9为KANN- DBSCAN与对比算法对四种数据集 Kernel-DBSCAN算法的聚类结果进行对比,聚类结果的聚类结果,可见 KANN-DBSCAN可以有效发现密度 评价采用有监督的F值进行度量。 集中区域并将其划分为簇,聚类结果直观判断上较为合 41人工标记数据集 理,表1为四种自适应确定参数算法的具体聚类结果和 人工标记数据集如图8所示, Aggregation是一个7评价指标 30 10 10203040 10203040 10203040 (a)Aggregation(N=788,C (b)Compound( N=399, c-6) (c)R15(N-600,C=15) (d)D31(N=3100,C=31) 图8有标记数据集散点图 (Eps-2851. MinPts-33, Cluster-7)(Eps-0941, MinPis-3, Cluster-10)(Eps-1504, MinPts-10, Cluster-7)(Eps-5.51, MinPts-94, Cluster-4) 螺萬: 20 10203040 10203040 10203040 03040 X X X (Eps=1. 802, MinPts=16, Cluster=5)(Eps=0.64, MinPis=2, Cluster=8)(Eps=0.904, MinPts=4, Cluster=5) (Eps=4.05, MinPts=59, Cluster=2) 10 10203040 0102030 10 Eps-1404, Min Pts=32, Cluster=15)(Eps=0. 351, MinPis=4, Cluster=21)( Eps=0.44, MinPts=6. Cluster=15)( Eps=1. 501, MinPts=34, Ciuster=9) 20 2 10… 0 10 03040 10203040 10203040 10203040 (Eps=1.628, Min Pts=56, Cluster=31)(Eps=0.372, MinPis=4, Cluster=70)(Eps=0.69, MinPts=14, Cluster=31)(Ep s=2.824, Min Pts=117. Chusiere5) 20 20 1020304 10203040 (aKANN-DBSCA (b)AF-DBSCAN (c)I-DBSCAN (d) Kernel-DBSCAN 图9自适应确定 DBSCAN算法参数算法聚类结果对比 6 2019,55(5) Computer Engineering and4 pplications计算机工程与应用 表1聚类结果对比 数据集类别对象数 聚类算法 fmPs数F值耗时s KANN-DBSCAN 70.98832.14 AF-DBSCAN 094 100.96390.29 Aggregation 7 788 I-DBSCAN1504 70.99420.56 cl-)SCAN5.5109440.88721.33 50.91460.32 AF-DBSCAN 0.640 2 80.81800.05 6 399 I-DBSCAN 0.904 0.87760.08 Kernel-DBSCAN 4050 0.730 KANN-DISCAN1404 150.99501.58 AF-DBSCAN 0.3514 10.82020.07 15 600 L-DBSCAN 0.440 150.88520.21 Kcrncl-DBSCAN 1.501 90.677 KANN- DBSCAN1.62856310.993832.40 AF-DBSCAN 0.372 700.8153169 3100 I-DBSCAN 0.690 310.89676.34 Kernel-DBSCAN 2.824 117 50.28802.93 从聚类结果簇数来看,KANN- DBSCAN与- DBSCAN DBSCAN算法和对比算法进行聚类分析,得到的簇表 算法均比较准确(除 Compound数据集外), Compound示该区域为地表火点高发密集区域。 数据集密度分布差异较大,KANN- DBSCAN对密度分 从图11的聚类结果可以看出, AF-DBSCAN、 Kernel 布差异较大的数据集进行聚类时存在定的误差,导致 DBSCAN的聚类结朱生成∫过多的簇,一些比较稀疏 聚类结果簇数和数据集类别数不一致的情况出现,这是的区域同样生成了簇,造成了簇数过多,影响对密集区 DBSCAN算法自身存在的不足。从F值评价指标来域的进一步判断。 KANN-DBSCAN和 I-DBSCAN的聚 看,对不同类型的数据集进行聚类, KANN-DBSCAN算类簇数相同,但是从E和MinP参数可以看出KANN 法均优于对比算法,说明κ∧NN-DBSC∧N算法具有较 DBSCAN确定的火点区城的密度值更低,可以得到 高的精确性。从耗时指标来看,数据量不大时,与对比更精确的火点高发区域。由结果可以看出我国东北部 算法的耗时差距不明显,随着数据量变大,耗时差距逐部以及东南亚和西亚是地表火点的高发区域,可为预 渐变大,这是由于 KANN-DBSCAN算法基于参数寻优防和火点监测提供参考依据 策略,通过多次分析确定最优参数。 43算法复杂度分析 4.2地表火点数据集 对于二维数据言, DBSCAN算法的基本时间复 采用地表火点数据米验证 KANN-DBSCAN的实际杂度为On2)叫,在使用R树建立空间索引时的基本时 应用效果,地表火点数据来自中国科学院遥感与数字地间复杂度为Obn),n为数据集中数据点的数目。 球研究所研发的 Sat See-Fire近实时地表高温异常点查 KANN-DBSCAN算法在 DBSCAN算法的基础上进行迭 询服务系统。时间范围为2018年1月份全月,坐标范代运算,迭代次数由最优参数对应的K值大小决定,在 围为0260N,50°E-140°E,火点数据分布如图10听示。算法实际运行过程中,K远小于n时,聚类过程即发 实验仅采用地表火点的地理坐标数据利用KANN生收敛。因此,在使用R树建立空间索引时KANN 60°N DBSCAN的时间复杂度为 O(Knlbn)K≤n) DBSCAN算法的空间复杂度为O(n2),KN 48°N DBSCAN算法在运算过程中仅生成了Ep列表,空间复 36°N 杂度为On),因此 KANN-DBSCAN算法的空间复杂度 为O1n2)+O(n)。 综上,KANN- DBSCAN算法的算法复杂度虽然较 12°N 传统 DBSCAN算法略高,但是提升了聚类的精确性, 0E0°E80°E100°E120E140°E 适合于一般数据规模且对聚类精确度要求较高的应用 图10地表火点数据分布图 场景。 李文杰,等:自适应确定 DBSCAN算法参数的算法研究 2019,55(5) (Eps=0.647, MinPts=59, Cluster=16 ps=0, 108, MinPts=9, Cluster=141) ,喂, 40 述, 50)6070090100110120130140 506070809010010120130140 OKANN-DBSCAN (b)AF-DbSCaN (Eps=0.54. MinPts=48 Cluster=16) (Eps=0.346, MinPts=28, Cluster=30) s 50 飞 飞3 5060708090100110120130140 5060708090100110120130140 (c)I-DBSCAN (d)Kerncl-DBSCAN 图11地表火点数据聚类结果 5结東语 distance parameter in density based clustering[J].Expert DBSCAN是基于密度的聚类算法中的典型代表, Systerns with Applicalions, 2014, 41(6): 2939-2946 可以有效识别噪声并自动将密度足够大的点区域划分3] Kim J H, Choi J H,Yo0KH, et al.AA- DBSCAN:an 簇,实现任意形状的点聚类。山于 DBSCAN算法对F approximate adaptive dbscan for finding clusters with 和MinP参数十分敏感,取值不当会导致聚类效果变差 varying densities [J]Journal of Supercomputing, 2018: 1-28 [4]Khan MM R, Siddique M, Bakr A, ct aL. ADBSCAN 甚至不正确。本文在DBSC∧N算法的基础上,引入密 adaptive density-based spatial clustering of applications 度阈值的概念,详细描述了算法的基本思想,提出了基 ith noise for identifying clusters with varying densi- 于参数寻优策略的自适应确定Fs和MiPs参数的算 tes[J] arXiv:1809.06189,2018 法,利用数据集自身的分布特性,通过运用K平均最近5夏鲁宁,荆继武 SA-DBSCAN:一种自适应基丁密度聚类 邻法生成候选参数,并运用数学期望法获得对应的 算法[门中国科学院大学学报,2009,26(4):530-538 MinP参数,自动寻找聚类结果簇数的变化稳定区间,[6周红芳,王鹏 DBSCAN算法中参数自适应确定方法的研 同时以簇数变化稳定区间中噪声个数最少吋所对应的 究[门西安理T人学学报,2012,28(3):289-292 EP和MmP值作为最优参数聚类全部过程无需人为71周治平,王杰锋,朱书伟,等,一种改进的自适应快速AF 干预,实现全自动化聚类。实验表明,本文算法可以实 DBSCAN聚类算法J智能系统学报,2016,11(1):93-98 现高准确率的聚类过程,但算法时间复杂度较高,适合 [8]李宗林,罗可 DBSCAN算法中参数的自适应确定[门计算 面向一般数据规模且对聚类精确度要求较高的应用场 机工程与应用,2016,52(3):70-73 [9 Ester M, Kriegel H P, Xu X A density-based algorithIn for 景。下一步,如何有效降低算法时间复杂度是工作的 discovering clusters a density-based algorithm for discov 重点。 ering clusters in large spalial databases with noise[C]/ International Conference on Knowledge Discovery and 参考文献: Data Mining, 1996: 226-231 [1] Yue S H, Ping L 1, Guo J D, et al.A statistical information- [10] Steinbach M, Karypis G, Kumar VA comparison of based clustering approach in distance space[J] Journal document clustcring techniques[C]//KDD workshop on of Zhejiang University-Science A, 2005, 6(1): 71-78 Text Mining, 2000: 525-526 [2 Jahirabadkar S, Kulkarni P algorithm to determine a (卜转第148页)

...展开详情
试读 7P 论文研究-自适应确定DBSCAN算法参数的算法研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744375 如果觉得有用,不妨留言支持一下
2019-09-16
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-自适应确定DBSCAN算法参数的算法研究.pdf 46积分/C币 立即下载
1/7
论文研究-自适应确定DBSCAN算法参数的算法研究.pdf第1页
论文研究-自适应确定DBSCAN算法参数的算法研究.pdf第2页

试读结束, 可继续读1页

46积分/C币 立即下载 >