基于數(shù)據(jù)劃分和融合策略的并行DBSCAN算法

　　大數(shù)據(jù)是近年來(lái)計(jì)算機(jī)領(lǐng)域興起的熱點(diǎn)研究方向，通過(guò)聚類可以解決諸如機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、生物信息分析等諸多大數(shù)據(jù)領(lǐng)域的問(wèn)題。聚類是研究分類問(wèn)題的重要方法，通過(guò)聚類分析可以將樣本中具有相同或者相似特征的項(xiàng)歸為一類，而將不具有該特征的項(xiàng)排除在外。主流的聚類方法包括基于劃分的聚類方法，如K-means；層次聚類方法，如CURE和BIRCH等；基于統(tǒng)計(jì)模型的方法，如EM算法等；基于密度的方法，如DBSCAN，OPTICS等。在基于密度的方法中，DBSCAN是較為典型的一種，它以超球狀區(qū)域內(nèi)數(shù)據(jù)對(duì)象的數(shù)量來(lái)衡量此區(qū)域密度的高低，能夠發(fā)現(xiàn)任意形狀的聚類并有效識(shí)別噪聲點(diǎn)。

　　在并行RDD-DBSCAN算法的數(shù)據(jù)劃分和區(qū)域查詢過(guò)程中會(huì)對(duì)數(shù)據(jù)集進(jìn)行重復(fù)訪問(wèn)，降低了算法效率。為此，提出基于數(shù)據(jù)劃分和融合策略的并行DBSCAN算法（DBSCAN-PSM）。利用KD樹(shù)進(jìn)行數(shù)據(jù)劃分，實(shí)現(xiàn)數(shù)據(jù)分區(qū)與區(qū)域查詢步驟的合并，從而減少數(shù)據(jù)集的訪問(wèn)次數(shù)以及降低I/O過(guò)程對(duì)算法效率的影響。采用判定數(shù)據(jù)點(diǎn)自身屬性的方式，對(duì)標(biāo)注為邊緣點(diǎn)的數(shù)據(jù)進(jìn)行融合，避免全局標(biāo)記的額外時(shí)間開(kāi)銷。實(shí)驗(yàn)結(jié)果表明，DBSCAN-PSM算法相比RDD-DBSCAN算法可節(jié)省18%左右的運(yùn)行時(shí)間，適用于處理海量數(shù)據(jù)聚類問(wèn)題。
?