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