【摘要】：DBSCAN是一種基于密度的聚類算法,其能從包含噪聲點(diǎn)的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的聚類并且無需預(yù)先設(shè)定聚類個(gè)數(shù),因此得到了廣泛應(yīng)用。但隨著數(shù)據(jù)規(guī)模的增大,迭代式的點(diǎn)間距離計(jì)算導(dǎo)致經(jīng)典單機(jī)串行DBSCAN算法的性能顯著下降,使之無法滿足實(shí)際應(yīng)用的效率需求。為此,該文提出一種性能改進(jìn)的分布式并行聚類算法——KDSG-DBSCAN。該算法利用K-D Tree鄰域查詢減少點(diǎn)間距離計(jì)算次數(shù),利用圖連通算法優(yōu)化局部類簇合并過程,并基于Apache Spark MapReduce平臺(tái)實(shí)現(xiàn)了計(jì)算過程的并行化。通過4組對(duì)比實(shí)驗(yàn),分析了KDSGDBSCAN、經(jīng)典DBSCAN與未使用圖連通的KDS-DBSCAN算法的執(zhí)行效率、KDSG-DBSCAN各子階段執(zhí)行時(shí)間占比、不同數(shù)據(jù)規(guī)模下KDSG-DBSCAN的擴(kuò)展性以及不同計(jì)算節(jié)點(diǎn)數(shù)量和CPU核數(shù)下KDSG-DBSCAN的擴(kuò)展性。結(jié)果表明,KDSG-DBSCAN算法具有良好的可擴(kuò)展性和加速比。
[Abstract]:DBSCAN is a density-based clustering algorithm, which can find arbitrary shape clustering from data sets containing noise points and does not need to set the number of clusters, so it has been widely used. However, with the increase of the data scale, the performance of the classical single-machine serial DBSCAN algorithm is significantly decreased due to the iterative calculation of the distance between points, which makes it unable to meet the efficiency requirements of practical applications. In this paper, an improved distributed parallel clustering algorithm, KDSG-DBSCAN., is proposed. The algorithm uses K-D Tree neighborhood query to reduce the number of times of computing distance between points, uses graph connectivity algorithm to optimize the local cluster merging process, and realizes the parallelization of computing process based on Apache Spark MapReduce platform. Through four groups of comparative experiments, the execution efficiency of KDSGDBSCAN, classical DBSCAN and KDS-DBSCAN algorithm without graph connectivity is analyzed, and the execution time of each sub-stage of KDSG-DBSCAN is analyzed. The expansibility of KDSG-DBSCAN under different data scales and the expansibility of KDSG-DBSCAN with different number of computing nodes and CPU kernels. The results show that the KDSG-DBSCAN algorithm has good scalability and speedup.
【作者單位】： 武漢大學(xué)測(cè)繪遙感信息工程國家重點(diǎn)實(shí)驗(yàn)室;地球空間信息技術(shù)協(xié)同創(chuàng)新中心;武漢大學(xué)遙感信息工程學(xué)院;
【基金】：國家自然科學(xué)基金項(xiàng)目(41501434、41371372、41471326)
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 周水庚,周傲英,曹晶;基于數(shù)據(jù)分區(qū)的DBSCAN算法[J];計(jì)算機(jī)研究與發(fā)展;2000年10期

2 ;Scaling up the DBSCAN Algorithm for Clustering Large Spatial Databases Based on Sampling Technique[J];Wuhan University Journal of Natural Sciences;2001年Z1期

3 岳士弘,李平,郭繼東,周水庚;Using Greedy algorithm: DBSCAN revisited II[J];Journal of Zhejiang University Science;2004年11期

4 蔡穎琨,謝昆青,馬修軍;屏蔽了輸入?yún)?shù)敏感性的DBSCAN改進(jìn)算法[J];北京大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年03期

5 宋明,劉宗田;基于數(shù)據(jù)交疊分區(qū)的并行DBSCAN算法[J];計(jì)算機(jī)應(yīng)用研究;2004年07期

6 熊忠陽,孫思,張玉芳,王秀瓊;一種基于劃分的不同參數(shù)值的DBSCAN算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2005年09期

7 何中勝;劉宗田;莊燕濱;;基于數(shù)據(jù)分區(qū)的并行DBSCAN算法[J];小型微型計(jì)算機(jī)系統(tǒng);2006年01期

8 李杰;賈瑞玉;張璐璐;;一個(gè)改進(jìn)的基于DBSCAN的空間聚類算法研究[J];計(jì)算機(jī)技術(shù)與發(fā)展;2007年01期

9 馮少榮;肖文俊;;基于密度的DBSCAN聚類算法的研究及應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2007年20期

10 譚穎;胡瑞飛;殷國富;;多密度閾值的DBSCAN改進(jìn)算法[J];計(jì)算機(jī)應(yīng)用;2008年03期

相關(guān)會(huì)議論文 前7條

1 馬帥;宋國杰;唐世渭;楊冬青;王騰蛟;;基于單元?jiǎng)澐值腄BSCAN聚類算法[A];第十九屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2002年

2 朵春紅;王翠茹;;基于取樣的DBSCAN聚類算法及其遺傳優(yōu)化[A];第一屆中國高校通信類院系學(xué)術(shù)研討會(huì)論文集[C];2007年

3 龐洋;李海林;郭義喜;;基于DBSCAN算法的日志信息聚類研究[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展·2007——全國第18屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集[C];2007年

4 宮蕊;舒紅平;郭遠(yuǎn)遠(yuǎn);;基于DBSCAN的密度聚類算法的研究[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（二）[C];2008年

5 張健沛;許慧;楊靜;崔洪晶;;基于數(shù)據(jù)分區(qū)、QR~*-樹的并行DBSCAN算法[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)——通信與信息技術(shù)會(huì)議論文集（下）[C];2006年

6 范曄;周水庚;曹晶;周傲英;;通過數(shù)據(jù)取樣擴(kuò)展基于密度的聚類算法[A];第十六屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集[C];1999年

7 曹晶;周水庚;范曄;周傲英;;數(shù)據(jù)分區(qū):一種改善基于密度的聚類算法的方法[A];第十六屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集[C];1999年

相關(guān)碩士學(xué)位論文 前10條

1 陸穎華;基于局部敏感哈希的DBSCAN算法研究[D];南京信息工程大學(xué);2015年

2 韓梅;基于改進(jìn)DBSCAN的復(fù)雜工業(yè)過程建模數(shù)據(jù)異常點(diǎn)檢測(cè)研究[D];天津工業(yè)大學(xué);2016年

3 劉聰;基于SPARK平臺(tái)的LAMOST早M型光譜聚類的研究[D];山東大學(xué);2016年

4 馮振華;基于DBSCAN聚類算法的研究與應(yīng)用[D];江南大學(xué);2016年

5 田路強(qiáng);基于DBSCAN的分布式聚類及增量聚類的研究與應(yīng)用[D];北京工業(yè)大學(xué);2016年

6 李宗林;基于DBSCAN的自適應(yīng)聚類算法研究[D];長(zhǎng)沙理工大學(xué);2015年

7 劉宏超;基于DBSCAN的文本聚類算法研究[D];江西財(cái)經(jīng)大學(xué);2016年

8 王實(shí)美;基于DBSCAN的自適應(yīng)非均勻密度聚類算法研究[D];北京交通大學(xué);2017年

9 羅啟福;基于云計(jì)算的DBSCAN算法研究[D];武漢理工大學(xué);2013年

10 吳林敏;針對(duì)非均勻數(shù)據(jù)集的DBSCAN過濾式改進(jìn)算法[D];重慶大學(xué);2009年

，

本文編號(hào)：2417999