基于MapReduce的改进DBSCAN算法

计算机科学 ›› 2015, Vol. 42 ›› Issue (Z11): 396-399.

基于MapReduce的改进DBSCAN算法

赖丽萍,聂瑞华,汪疆平,黄家鸿

华南师范大学计算机学院广州510631,华南师范大学计算机学院广州510631,华南师范大学计算机学院广州510631,华南师范大学计算机学院广州510631

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受教育部-中移动基金项目(MCM20130651),广州市科技和信息化局基金项目(2014Y2-00006)资助

Improved DBSCAN Algorithm Based on MapReduce

LAI Li-ping, NIE Rui-hua, WANG Jiang-ping and HUANG Jia-hong

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 针对聚类算法DBSCAN中存在的Eps参数问题和处理海量数据集时的效率问题,提出OPDBSCAN算法。OPDBSCAN算法通过交叠分区获取局部Eps以降低全局Eps参数对聚类质量的影响,并结合MapReduce并行框架提高算法效率。实验结果表明,OPDBSCAN算法的效率和聚类质量都高于原DBSCAN算法。

关键词: OPDBSCAN,MapReduce,Eps,K-dist图,交叠分区

Abstract: Aimed at solving DBSCAN’s problems of the Eps parameters and the efficiency of processing of massive data sets,the article put forward a new algorithm called OPDBSCAN.It uses overlapping partitions to get a local Eps for reducing the effect of global Eps,then uses MapReduce to cluster in parallel to improve the efficiency.At last,the experiment shows that the OPDBSCAN can cluster faster and better.

Key words: OPDBSCAN,MapReduce,Eps,K-dist,Overlap-partion

赖丽萍,聂瑞华,汪疆平,黄家鸿. 基于MapReduce的改进DBSCAN算法[J]. 计算机科学, 2015, 42(Z11): 396-399. https://doi.org/

LAI Li-ping, NIE Rui-hua, WANG Jiang-ping and HUANG Jia-hong. Improved DBSCAN Algorithm Based on MapReduce[J]. Computer Science, 2015, 42(Z11): 396-399. https://doi.org/

参考文献

[1] 李爱国,厍向阳.数据挖掘原理、算法及应用[M].西安:西安电子科技大学出版社,2012:29-35
[2] Ekan Y J,Pallickara S.MapReduce for data intensive scientific analysis[C]∥eScience 2008:Proceedings of the Fourth IEEE,International Conference on eScience.Piscataway:IEEE Press,2008:277-284
[3] Dean J,Ghemawat S.MapReduce:Simplified data processing on large clusters [J].Communications of the ACM,2008,1(1):107-113
[4] Ester M,et al.A density based algorithm fordiscovering clusters in large spatial databases with noise[C]∥Proc of 2nd Inter Conf Knowledge Discovering in Databases and Data Mining (KDD-96).Portland:AAAI Press,1996
[5] 侯荣涛,朱斌.基于DBSCA聚类算法的闪电临近预报模型[J].计算机应用,2012,2(3):847-851
[6] 李莉平,沈俊媛.基于数据挖掘的DBSCAN算法及其应用[J].科技创业月刊,2009(8):134-135
[7] 黄毅磊.DBSCAN算法及在城市网格化管理中的应用[D].上海:上海交通大学,2010
[8] 夏鲁宁,荆继武.SA-DBSCAN:一种自适应基于密度聚类算法[J].中国科学院大学学报,2009(4):530-538
[9] 陈刚,刘秉权,吴岩.一种基于高斯分布的自适应DBSCAN算法[J].微电子学与计算机,2013,30(3):27-30
[10] 周水庚,周傲英,金文,等.FDBSCAN:一种快速 DBSCAN算法[J].软件学报,2000,1(6):735-744
[11] Ankerst M,Breunig M,Kriegel H-P,et al.Optics:Orderingpoints to Identify the Clustering Structure[C]∥Alex D,Christos F,Shahram G,eds.Proc ACM SIGMOD Int Conf on Mana-gement of Data.Philadephia:ACM Press,1999:49-60
[12] 周水庚,周傲英.基于数据分区的DBSCAN算法[J].计算机研究与发展,2000,37(10):1153-1159
[13] 孙凌燕.基于密度的聚类算法研究[D].太原:中北大学,2009
[14] 熊忠阳,吴林敏,张玉芳.针对非均匀数据集的DBSCAN过滤式改进算法[J].计算机应用研究,2009,6(10):3721-3723

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed