基于數據劃分和融合策略的并行DBSCAN算法

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

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