Hierarchical Density-Based Clustering Using MapReduce
Open Access
- 26 March 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Big Data
- Vol. 7 (1) , 102-114
Abstract
Hierarchical density-based clustering is a powerful tool for exploratory data analysis, which can play an important role in the understanding and organization of datasets. However, its applicability to large datasets is limited because the computational complexity of hierarchical clustering methods has a quadratic lower bound in the number of objects to be clustered. MapReduce is a popular programming model to speed up data mining and machine learning algorithms operating on large, possibly distributed datasets. In the literature, there have been attempts to parallelize algorithms such as Single-Linkage, which in principle can also be extended to the broader scope of hierarchical density-based clustering, but hierarchical clustering algorithms are inherently difficult to parallelize with MapReduce. In this paper, we discuss why adapting previous approaches to parallelize Single-Linkage clustering using MapReduce leads to very inefficient solutions when one wants to compute density-based clustering hierarchies. Preliminarily, we discuss one such solution, which is based on an exact, yet very computationally demanding, random blocks parallelization scheme. To be able to efficiently apply hierarchical density-based clustering to large datasets using MapReduce, we then propose a different parallelization scheme that computes an approximate clustering hierarchy based on a much faster, recursive sampling approach. This approach is based on HDBSCAN*, the state-of-the-art hierarchical density-based clustering algorithm, combined with a data summarization technique called data bubbles. The proposed method is evaluated in terms of both runtime and quality of the approximation on a number of datasets, showing its effectiveness and scalability.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
- Conselho Nacional de Desenvolvimento Científico e Tecnológico (304137/2013-8, 400772/2014-0)
- FAPESP and FAPEMIG
- Fundação de Amparo à Pesquisa do Estado de São Paulo
- Fundação de Amparo à Pesquisa do Estado de Minas Gerais
This publication has 27 references indexed in Scilit:
- Density-Based Clustering Based on Hierarchical Density Estimates2013
- Density‐based clusteringWIREs Data Mining and Knowledge Discovery, 2011
- DECODE: a new method for discovering clusters of different densities in spatial dataData Mining and Knowledge Discovery, 2008
- MapReduceCommunications of the ACM, 2008
- Efficient Parallel Algorithms for Hierarchical Clustering on Arrays with Reconfigurable Optical BusesJournal of Parallel and Distributed Computing, 2000
- Parallel hierarchical clustering algorithms on processor arrays with a reconfigurable bus systemPattern Recognition, 1997
- Parallel algorithms for hierarchical clusteringParallel Computing, 1995
- Data structures and algorithms for disjoint set union problemsACM Computing Surveys, 1991
- Comparing partitionsJournal of Classification, 1985
- Optimal Expected-Time Algorithms for Closest Point ProblemsACM Transactions on Mathematical Software, 1980