论文研究-GreedyDBSCAN:一种针对多密度聚类的DBSCAN改进算法.pdf

所需积分/C币:17 2019-07-22 22:20:31 3.63MB .PDF
收藏 收藏 1
举报

针对基于密度的DBSCAN算法对于输入参数敏感、无法聚类多密度数据集等问题,提出了一种贪心的DBSCAN改进算法(greedy DBSCAN)。算法仅需输入一个参数MinPts,采用贪心策略自适应地寻找Eps半径参数进行簇发现,利用相对稠密度识别和判定噪声数据,在随机寻找核对象过程中使用邻域查询方式提升算法效率,最终通过簇的合并产生最终的聚类结果。实验结果表明,改进后的算法能有效地分离噪声数据,识别多密度簇,聚类准确度较高。
第9期 冯振华,等: Creedy DBSCAN:一种针对多密度聚类的 DBSCAN改进算法 2695 “回滚”操作,即将该簇内的点及簇相关信息全部撤销。如图3准确识别了距离高密度簇较近的两个噪声点。 中点p的半径参数s远远大于簇内其余点间平均距离dis- 为了验证算法在更复杂的多密度数据集上的表现,第二组 ance,说明点p为离群的噪声点。 实验在 Shape 数据集中随机选取两组合并成为一个更 distance.<< 复杂的多密度数据集上进行。合并后的数据集共有624个数 据点,包含∫四个形状、密度各不相同的簇和若十噪声点。不 同算法的聚类结果如图5所示。 distanceas Minpts_4 图3噪声点作为随机初始点 24 Greedy DBSCAN伪代码 Greedy DBSCAN算法的伪代码如下所示。其中,D表示聚 类的数据集,O1表示数据集D中的点对象。 01020304050 function Greedy DBSCAN( int MinPts a)DBSCAN算法聚类结果 il改进的 OPTICS算法聚类结果 k= minPts -l Mark all points in D as unprocessed 口口口日日匚口口 E日日3a日 while there is a unprocessed point Mark p as 十算半径 Search for the h points closest to p Put the distance-values into array k_nearest Sort array k_nearest[]//对k个邻近距离排序 01020304050 01020304050 文献[5中算法聚类结果 d igreedy DBSCAN算法聚类结 Expand cluster C around p in epslion eps 图4实验一聚类结果 //判断噪声数据 (i)-P(h Rollback(C)//回滚操作 Mark p as a non-Drm object 20 Mark points in cluster C as is Classed( processed Mark /核对象邻域查询 Search new cluster in C's neighborhood areal i 合并含有相同公共点的簇(“密度连接”) (a) DESCAN算法聚类结果 ()改进的 OPTICS算法聚类结果 if( c Ci s object )i Merge(Ci, C /输出噪声数据 1l O cD if 0. is nol is classed Then print O, is an Outline 上nd 1020 102030405060 3实验分析 (c)文献5中算法聚类结果 ( IGreedy dbSCan算法聚类结果 5实验二聚类结 本文提出的 Greedy DBSCAN算法通过Java语言在 Eclipse 上述实验结果中,图5(a)的低密度簇中的绝大部分对象 环境中实现, MATLAB具处理实验结果。实验的环境是:都被处理为噪声点(噪声点用黑色“x”表示),图5(b)中只识 CPU为 Intel centrino2.2GHz;内存为2GB;OS为 Windows 别出两个簇,而且将噪声数据归入了簇屮,图5(c)屮算法虽然 实验在各个算法所需参数均等、公平的情况下,通过在四个不 识别出了4个簇,但对于边界数据处理较为粗糙,影响了最终 同类型和规模的多密度数据集上分别与 DBSCAN算法改进的聚类结果。而 Greedy dscan算法成功识别出了4个密度 的 OPTICS算法、文献[15]中的算法进行聚类效果比较,最形状各不相同的簇,噪声数据检测也|分准确。 后对木文所提算法性能进行评估分析。 实验三针对高密度簇与低密度相邻、并且有临界点干扰的 3.1实验结果分析 情况,使用加入了噪声的Sze5数据集。 Minpts参数取样本 第一组实验采用类似于图1中的含有噪声点的人工模拟点个数的L1/25」,取值为38,聚类结果如图6所示 构造的多密度数据集,山于该数据集样本点个数较少, Minpts 图6屮用黑色“×”表示噪声点, DBSCAN算法只识别了三 参数统一取4。实验结果如图4所示。 个簇,其中一个低密度簇仝部处理为了噪声数据;改进的OP- 在图4的实验结果中以黑色的“×”表小噪声点,图4(a)TICS算法识别了两个簇,但其将与高密度簇相邻的低密度簇 (b)中的方法均不能在不同密度的簇中准确识别噪声点。图4错误地并入∫同一簇中;文献[15中算法聚类结果得到∫正 (c)(d)中的方法均正确识别了密度高低不冋的三个簇,并且确簇数,但是错误地将边缘噪声归入∫高密度簇中,同吋对于 2696· 计算机应用研究 第33卷 低密度簇的识别也不够完整;( reedY DBSCAN算法准确识别出小的数据集上独立运行20次,分别计算平均运行时间,并将其 了四个相邻的密度不同的簇,且仅吸收了少量的噪声数据到图表化,如图8所示。 簇中。 100厂 第四组仿真实验在来源于文献L20」中的 Chameleon数据 改进的 OPTIC +文献15中算法 集上进行,实验结果如图7所示。 Greedy DBSCAN 15 00300050007000900 付象个数∧个 : 图8四个算法的运行时间对比图 从图8中可以看出,四个算法的运行吋间都随着数据集规 -5051015 模的扩大而增长,但 DBSCAN算法效率最高,但它对于含有噪 ( a)DBSCAN算法聚类结果 )改进的 OPTICS算坛聚类结果声的多密度数据集无能为力。 OPTICS算法需要为数据集中的 每一个对象寻找核心距离和可达距离,而且在迭代查找可达对 15x 象时,需要对种子对象依可达对象距离进行排序;文献[15 中的算法首先需要在数据集中找到区域中心点(区域密度最大 的点)依次作为候选核心点,而这个过程需要遍历数据集中所有 o松,,∷ 的数据,耗时严重,并且在簇的扩吋需计算其k个最邻近 Greedy DBSCAN算法按照贪心策略,只需为每一个圆形簇找到 10 其邻域半径,同时算法在寻找核对象时利用邻域查询提高效率 c)文献[15中算法聚类结果 d) Greedy dbsCan算法聚类结果 而且在数据集中圆形簇的数量远远小于点的个数,因此算法运 佟6含有噪声的Sκes5数据集实验结果 行效率要优于改进的 OPTICS算法和文献[15]屮的算法。 160 4结束语 4删:4 本文提出的 Greedy dBSCAN算法继承了基于密度聚类算 法的优势,可以识别仼意形状和数量的簇,对丁含有噪声点的 多密度数据集有着很好的聚类效果,仅需用户输入一个参数, 01002003004005006008001002030040500600700800而且在算法运行效率上要优于政进的 OPTICS算法和文献 a) DBSCAN算法聚类结果 (b)改进的 OPTICS算法聚类结果 [15中的算法,具有较高的执行效率。但当面对海量数据集 7160 时算法的处理时间仍有待提高,下一步研究重点是如何结合启 发式搜索策略和网格技术来进一步提升算法效率 10 参考文献 [IⅠ Han jiawei, Kamber m.数据挖掘穊念与技术[M].沌明,孟小峰 译.3版.北京:机械工业出版社,2012:288-322 01002003004005006007008000100200300400500600700800 2 Dhami C, Bnasal M. An improvement of DBSCAN algorithm to analyze ()文献[15]中算法聚类结果 (d) Greedy DBSCAN算法聚类结果 cluster for large datasets[ C]//Proe of IEEE International Conference 图7 Chameleon数据集实验结果 on MOOC Innovation and Technology in Education. [S1.]: IEEE Chameleon数据集共有8000个数据对象,包含六个字母 Press.2013:42-46 形状的簇。图7(a)中认别了六个簇,但是在簇与簇间连接处 [3 Rodriguez A, Laio A. Clustering by fast search and find of density 的噪声数据没有被识别;图7(b)只识别出了四个簇,而且吸收 peaks[J. Science,2014,344(6191):1492-1496 了数量相当多的噪声数据到簇中;图7()中基本认别出了六4】Smi.,Eoz. Soft dbscan; improving dbSCan clustering method using fuzzy set theory[C]//Proc of the 6th International Conference on 个字母形状的簇,但是对于簇周边的嗓声及簇间干扰未能准确 luman System Interaction [S1.: IEEE Press, 2013: 380-385 识别;图7(d中对扌处在六个簇间的“横线”噪声数据干扰进L5」孙言貴,刘杰,赵连宇,聚类算法研究J.软学报,200,19 行了准确的识别,仅吸收了少量噪声数据到簇中。 (1):48-61 3.2性能分析 [6」曾依灵,许洪波,白硕,改进的 OPTICS算法及其在文本聚类中的 通过上述四组仿真实验结果,可以发现文献[15]中的方 应月[J,中文信息学报,2008,22(1):51-55 法和木文提出的 Greedy DBSCAN算法都貝备处理多密度数据 [7]蔡颖琨,谢昆青,马修军.屏蔽了揄入参教敏感性的 DESCAN改 进算法[J],北京大学学报:自然科学版,204,40(3):480-486 集的能力,但是当数据集中噪声数据较多或簇门存在明显噪声 8 Antunes A, Santos M Y, Moreira A. Fast S\N-based clustering ap 干扰的情况下,本文所提算法的聚类结果准确率要明显优于文 roach for large geospatial data sets[M]//Connecting a Digital Eu 献l15中的方法。下面在 Chameleon数据集中随机抽取10组 ope Through Location and Place. [S.I.]: Springer International Pub- 不同规模大小的数据集,对应地将四个算法分别在不同规模大 lishing,2014:179-195 (下转第2700页) 2700· 计算机应用研究 第33卷 表3Wine数据集测试结果表 能将是下一步工作的重点。 序号 殖机 K-meansF M 74.15 85.39 参考文献 50.00 [ 1 Han Jiawei, Kamber m.数据挖掘念与技术[M].范明,孟小峰, 57.87 68.54 译.3版,北京:机械工业出版社,2012:288-376 97.19 [2] Richard0, Peter E, David g. Pattern classification[M].李宏东,等 译.2版.北京:机械工业出版社,2003:415-477 Recognition Letters, 2010, 31(8): 651-666 85.39 10 [4 Deng Hongbo, Han Jiawei Data clustering: probabilistic models for 83.71 clustering[M. Minnesota: CRC Press, 2013: 61-81 表4 Soybean数据集测试结果表 [5 Li Ximing, Ouyang Jihong, Zho Xiaolang Centroid prior topic model 号 随机EM K-meansEM DDEM for multi-label classification [J]. Pattern Recognition Letters 70.21 72.34 76.60 2015,62(9):8-13 63.83 72.34 76.60 [6 Halima B Gilles C. Adrian E, et al. Inference in model-based cluster 61.70 72.34 76.60 analysis[ J. Statistics and Computing, 1997, 7(1): 1-10 72.34 76.60 61.70 46.80 76.60 [7 Dempster A, Laird N, Rubin D. Maximum likelihood from incomplete 56789 53.19 55.32 76.60 data via the EM algorithm[ J. Royal Statistical Society, 1977, 39 78.72 76.60 (1):1-38. 74.47 72.34 76.60 [8 Charles B, camille B Model-based clustering of high-dimensional da- 61.7( 72.34 ta: a review[ J]. Computational Statistics and Data Analysis 10 1.70 72.34 63.83 68.08 76.60 2012,71(3):52-78 随机EM算法由于随机选择初始值,最终收敛得到的聚类 [9 Martin E, Hans-Peter K, Sander X, et al. a density-based algorithm for discovering clusters in large spatial databases with noise[ C]//Proc of 结果很不稳定。K- meanseM算法先通过运行K- means算法,得 e 2nd International Conference on Know ledge Discovery and Data 钊一个收敛后的中心作为EM算法的初始值,最终聚类结果相 Mining. USA: AAAl, 1996: 226-231 对随机EM算法稳定些。但是K- means算法本身只能聚类10] Raymond T, Vladimir t. Distance-based outliers: algorithms and ap- 球形簇,并且收敛效果取决于其随机初始中心的选择,所以通 plications[ J 1. VLDB Joumal, 2000, 8(2): 237-253 过K- means算法收敛取得的中心并不能保证是较优的并且不 [1l Jin Wen, Tung A, Han jiawei, et al. Ranking outliers using symmetr neigh rhood relationship [C]//Proe of the 10th Pacific-Asia Confer 稳定。嬝类过程中簇中心具有附近数据点分布较密集,并且每 ence Advances in Knowledge Discovery and Data Mining.[S 1.] 个簇中心相距较远的特点,DDEM算法通过查找密度大并且与 pringer,2006:577-593 其他中心点距离远的点,保证了初始中心更接近丁簇中心,从[12] Arthur d, Vassilvitskii S. K-means+: the advantage of careful sce 而最终结果相比于其他两个算法有更高的准确率,同时DDEM ding c//Proc of the 18th Annual ACM-SIAM Symposium on Dis 算法锊次均可取得相同的初始中心,侏证∫稳定性。 crete Algorithms. New York: ACM Press, 2007: 1027-1035 13 Zhai Donghai, Yu Jiang K-means text clustering algorithm hased on 4结束语 initial cluster centers selection according maximum distance[ J]. Ap plication Research of computers, 2014, 31(3): 713-719 DDEM算法通过基于密度的方法识别噪声点,基于密度和 [14 Christophe B Initializing EM using the properties of its trajectories in 距离的方法优化了初始值的选择。通过实验验证了DDEM算 Gaussian mixtures[ J]. Statistics and Computing, 2004, 14(3): 267-279 法可以有效识别噪声点,在保证准确率的同时提高了算法的稳[151 Chandan K, Bhanukiran v. A survey of partitional and hierarchical 定性。将改进后的算法应用于实际的工程中,并提高算法的性 lustering algorithms[ M. USA: CR. Press, 2013: 88-105 (上接第2696页) [14 Narmadchian A, Esfandani G. DSCLU: a new dala slream clustring [ 9] Chen Xiaoyun, Min Yufang, Zhao Y an, et al. GMDBSCAN: mulli-den algorithm for mulli density environmenTs C]//Pror of the 13th ACIS sity DBSCan cluster based on grid[ C]//Proc of IEEE International International Conference on Software Engineering. Artificial Intelli Conferenee on e-Business Engineering.[S.1.]: IEEE Press, 2008 gence, Networki and Parallel Distributed Computing.S1. IEEE Press 2012: 83-88 [10黄红伟,黄天民,基于网格相对密度差的扩展聚类算法[冂.计[15]范敏,夺泽明,石欣,一种基于区成中心点的聚类算法[J]计 算机工程与科学,2014,36(9):1817-1822. 算机应用研究,2014,31(6):1702-1705. 「16]孙凌燕.基于密度的聚类算法应用研究「D1.太原:中北大学 「II夏敦,孪克非,丰江帆.基于闷格梯度的多密度聚类算法「J].计 200. 算机应用研究,2008,25(11):3278-3280 [17 Daszykowski M, Walczak B, Massart D L. Looking for natural patterns L12」邢长征,温培.基于网格密度和引力的不确定数据流聚类算法 in data: Part 1. density-based approach [I ]. Chemometrics and [J.计算机应研究,2015,32(1):98-101 Intelligent Laboratory Systems, 2001, 56 (2): 83-92 13 Yang Xiaobing, He Lingmin, Lu Huijuan. A new method for non- [18] htlp: //es joensuu. fi/sipudal ases[EB/0L.] udn.com/downlnads219/soureer(dle/rmath/etail spherical and multi-density clustering[ C]//Proc of the 3rd Interna- 1030717.hnFB/O] tional Symposium on Intelligent Information Technology Application. [20] Karypis G, Han E H, Kumar V Chameleon: hierarchical clustering [S.1.]: IEEE Press,2009:35-38 using dynamic modeling[ J]. Computer, 1999, 32(8): 68-75

...展开详情
试读 5P 论文研究-GreedyDBSCAN:一种针对多密度聚类的DBSCAN改进算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-GreedyDBSCAN:一种针对多密度聚类的DBSCAN改进算法.pdf 17积分/C币 立即下载
    1/5
    论文研究-GreedyDBSCAN:一种针对多密度聚类的DBSCAN改进算法.pdf第1页
    论文研究-GreedyDBSCAN:一种针对多密度聚类的DBSCAN改进算法.pdf第2页

    试读已结束,剩余3页未读...

    17积分/C币 立即下载 >