資源描述：
《基于MapReduce的DBSCAN聚類算法的并行實(shí)現(xiàn).pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、ISSN1009-3044E-mail：eduf@dnzs．net．enComputerKnowledgeandTechnology電腦知識(shí)與技術(shù)http：／／www．dnzs．net．cnVo1．11．N0．10．April2015Te1：+86—551—6569096365690964基于MapReduce的DBSCAN聚類算法的并行實(shí)現(xiàn)林阿弟，陳曉鋒(廈門大學(xué)計(jì)算機(jī)科學(xué)系，福建廈門361005)摘要：DBSCAN是一種簡單、有效的基于密度的聚類算法，用于尋找被低密度區(qū)域分離的高密度區(qū)域。DBSCAN是最經(jīng)常被使用、在科學(xué)文獻(xiàn)中被引用最多的聚類算法之一。在
2、數(shù)據(jù)維度比較高的情況下，DBSCAN的時(shí)間復(fù)雜度為0(n)。然而，在現(xiàn)實(shí)世界中，數(shù)據(jù)集的大小已經(jīng)增長到超大規(guī)模。對此，一個(gè)有效率的并行的DBSCAN算法被提出，并在MapRe—duce平臺(tái)下實(shí)現(xiàn)它。首先，對已經(jīng)預(yù)處理過的數(shù)據(jù)進(jìn)行劃分。接下來，局部的DBSCAN算法將對每一塊劃分好的數(shù)據(jù)空間實(shí)現(xiàn)聚類。最終，利用合并算法對上一階段的聚類結(jié)果進(jìn)行合并。實(shí)驗(yàn)結(jié)果驗(yàn)證了并行算法的有效性。關(guān)鍵詞：DBSCAN；MapReduce；聚類算法；并行算法：數(shù)據(jù)挖掘中圖分類號：TP391文獻(xiàn)標(biāo)識(shí)碼：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．后，根據(jù)各個(gè)維的劃分點(diǎn)，得到了數(shù)據(jù)劃分。接著，調(diào)整得到的SCAN基本時(shí)間復(fù)雜度是(n找出樣本點(diǎn)的Eps鄰域中的點(diǎn)所數(shù)據(jù)劃分作為局部DBSCAN算法的輸入，實(shí)施局部DBSCAN算需要的時(shí)間)，其中n是樣本點(diǎn)的大小。低維數(shù)據(jù)空間下，利用法。最后，利用合并算法對上一階段的聚
7、類結(jié)果進(jìn)行合并。一些空間索引結(jié)構(gòu)，如kd樹【2]、R樹[3】、R樹[4】等，時(shí)間復(fù)雜度1DBSCAN算法介紹可以降到．高維數(shù)據(jù)空間下，DBSCAN的時(shí)間復(fù)雜度為。1．1DBSCAN的簇PDBSCAN[5]首次采用dR～tree提出了一個(gè)有效的DBSCAN并行算法。然而，創(chuàng)建dRtree在海量數(shù)據(jù)情況下非常的困難，而DBSCAN聚類算法需要用戶自己確定兩個(gè)參數(shù)Eps和在數(shù)據(jù)是高緯度時(shí)則毫無效率。MR—DBSCAN[6]提出了基于MinPts。其中，Eps為用戶定義的半徑，MinPts為定義一個(gè)點(diǎn)為MapReduce[7]平臺(tái)下的DBSCAN并行算法。MR—DBS
8、CAN提出核心點(diǎn)時(shí)其鄰域內(nèi)要求的最少點(diǎn)
