架構於雲端之平行化密度分群演算法

Abstract

DBSCAN是一個頗負盛名的密度分群演算法，它的特色是可以在充滿雜訊的環境中找到具有任意形狀的群體。然而當資料的規模愈來愈大時，因為單一的電腦很難在效能上有所提升，DBSCAN無法有效率地處理這大量的資料。雲端運算在近期逐漸發長成熟，他可以幫助我們處理傳統演算法在面對大量資料時效率不佳的問題。 在這篇論文裡，我們提出了CDBSCAN演算法，CDBSCAN代表以雲端(Cloud)為基礎的DBSCAN演算法，它是一個分散式版本的DBSCAN演算法，並且被實施在一個雲端的平台上─Hadoop。我們利用Map/Reduce的工作將在各個區間的資料做分群，並且將這些各自的分群結果做整合，成為最後地分群結果。我們的實驗顯示CDBSCAN是一個高度平行化的演算法，他只需要一個Map/Reduce的工作，並達到趨近於線性的擴展性。

DBSCAN is one of the well-known density-based clustering algorithms which can identify clusters with arbitrary shape in a noisy space. However, when the scales of the data become larger and larger, DBSCAN is unable to process the data efficiently due to the difficulty of a single machine to scale up. Recently, the development of cloud computing is gradually mature which can help us manage the issue of scalability. In this thesis, we propose an algorithm CDBSCAN, standing for cloud based DBSCAN, which is a distributed version of DBSCAN and is implemented on the Hadoop platform. We use Map/Reduce jobs to cluster the partitioned data set and merge the individual clustering results. The experimental evaluations show that CDBSCAN is a highly parallel algorithm that only requires one Map/Reduce job and achieves near-linearly scalability.