基于MapReduce的DBSCAN聚类算法的并行实现.pdf

《基于MapReduce的DBSCAN聚类算法的并行实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ISSN1009-3044E-mail：eduf@dnzs．net．enComputerKnowledgeandTechnology电脑知识与技术http：／／www．dnzs．net．cnVo1．11．N0．10．April2015Te1：+86—551—6569096365690964基于MapReduce的DBSCAN聚类算法的并行实现林阿弟，陈晓锋(厦门大学计算机科学系，福建厦门361005)摘要：DBSCAN是一种简单、有效的基于密度的聚类算法，用于寻找被低密度区域分离的高密度区域。DBSCAN是最经常被使用、在科学文献中被引用最多的聚类算法之一。在

2、数据维度比较高的情况下，DBSCAN的时间复杂度为0(n)。然而，在现实世界中，数据集的大小已经增长到超大规模。对此，一个有效率的并行的DBSCAN算法被提出，并在MapRe—duce平台下实现它。首先，对已经预处理过的数据进行划分。接下来，局部的DBSCAN算法将对每一块划分好的数据空间实现聚类。最终，利用合并算法对上一阶段的聚类结果进行合并。实验结果验证了并行算法的有效性。关键词：DBSCAN；MapReduce；聚类算法；并行算法：数据挖掘中图分类号：TP391文献标识码：A文章编号：1009—3044(2015)10—0161-04TheRealiza

3、tionofMapReduce——basedDBSCANDensity‘。baseClusteringMethodLINA—di．CHENXiao—feng(DepartmentofComputerScience，XiamenUniversity，Xiamen361005，China)Abstract：DBSCANisaneffectivedensity——basedclusteringmethodwhichisdesignedtofindhigh——densityregionswhicharesep—aratedbylow—densityregions．DB

4、SCANisoneofthemostcommonclusteringalgorithmsandalsomostcitedinscientificlitera—ture．Inthecaseofthedataofhighdimension，thecomputationcomplexityofDBSCANisO(n)．However，itischallengingduetothesizeofdatasetshasbeengrowingrapidlytoextra—largescaleintherealworld．Inthispaper，alleficientpara

5、lleldensity—basedclusteringalgorithmisproposedandimplementedbyusingMapReduce．Furthermore，weadoptaquickpartitioningstrate—gyfordatawhichhasbeenpreprocessedisadopted．Then，LocalDBSCANprocessforeachsubspacedividedbythepartitionpro—fileisimplementedtogenerateclusters．Atlast，theclusterswh

6、icharegeneratedinthepreviousphasearemerged．Keywords：DBSCAN；mapreduce；clusteringalgorithms；parallelalgorithms；dataminingDBSCAN[11于1996年被提出以后便被广泛使用。DB．后，根据各个维的划分点，得到了数据划分。接着，调整得到的SCAN基本时间复杂度是(n找出样本点的Eps邻域中的点所数据划分作为局部DBSCAN算法的输入，实施局部DBSCAN算需要的时间)，其中n是样本点的大小。低维数据空间下，利用法。最后，利用合并算法对上一阶段的聚

7、类结果进行合并。一些空间索引结构，如kd树【2]、R树[3】、R树[4】等，时间复杂度1DBSCAN算法介绍可以降到．高维数据空间下，DBSCAN的时间复杂度为。1．1DBSCAN的簇PDBSCAN[5]首次采用dR～tree提出了一个有效的DBSCAN并行算法。然而，创建dRtree在海量数据情况下非常的困难，而DBSCAN聚类算法需要用户自己确定两个参数Eps和在数据是高纬度时则毫无效率。MR—DBSCAN[6]提出了基于MinPts。其中，Eps为用户定义的半径，MinPts为定义一个点为MapReduce[7]平台下的DBSCAN并行算法。MR—DBS

8、CAN提出核心点时其邻域内要求的最少点