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

CDBSCAN:Cloud Based DBSCAN Clustering Algorithm

陳則諭(Tze-Yu Chen)

指導教授 ： 陳銘憲

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.00354

摘要

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

關鍵字

分群演算法 ； 平行式演算法 ； 分散式演算法 ； 雲端運算 ； Hadoop

並列摘要

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.

並列關鍵字

Clustering Algorithms ； Parallel Algorithms ； Distributed Algorithms ； Cloud Computing ； Hadoop

參考文獻

[5] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise”, In Proc. of th 2nd KDD Conf., pp. 226-231, 1996.

[6] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly, “Dryad: Distributed data-parallel programs from sequential building blocks”, In Proc. of the 2007 EuroSys Conf., pp. 59-72, 2007.

[9] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The Google File System”, In Proc. of 19th ACM Symposium on Operating Systems Principles, Lake George, NY, 2003.

[11] V. Gaede and O. Gunther, “Multidimensional access methods”, ACM Comput. Surv. 30(2), 170-231, 1998.

[12] X. Xu, J. Jager, and H.-P. Kriegel, “A fast parallel clustering algorithm for large spatial databases”, Data Min. Knowl. Discov. 3(3), 263-290, 1999.