Hierarchical Density-Based Clustering Using MapReduce
| Autor: | Joelson Antonio dos Santos, Joerg Sander, Talat Iqbal Syed, Ricardo J. G. B. Campello, Murilo Coelho Naldi |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Information Systems and Management
Computational complexity theory Computer science 02 engineering and technology computer.software_genre MINERAÇÃO DE DADOS 01 natural sciences Automatic summarization Hierarchical clustering Data modeling 010104 statistics & probability Exploratory data analysis Scalability 0202 electrical engineering electronic engineering information engineering Programming paradigm 020201 artificial intelligence & image processing Data mining 0101 mathematics Cluster analysis computer Information Systems |
| Zdroj: | Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual) Universidade de São Paulo (USP) instacron:USP |
| ISSN: | 2372-2096 |
| DOI: | 10.1109/tbdata.2019.2907624 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|