- Title
- Efficient computation and visualization of multiple density-based clustering hierarchies
- Creator
- Neto, Antonio Cavalcante Araujo; Sander, Jörg; Campello, Ricardo J. G. B.; Nascimento, Mario A.
- Relation
- IEEE Transactions on Knowledge and Data Engineering Vol. 33, Issue 8, no. 8943293, p. 3075-3089
- Publisher Link
- http://dx.doi.org/10.1109/TKDE.2019.2962412
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- journal article
- Date
- 2021
- Description
- HDBSCAN*, a state-of-the-art density-based hierarchical clustering method, produces a hierarchical organization of clusters in a dataset w.r.t. a parameter mpts. While a small change in mpts typically leads to a small change in the clustering structure, choosing a “good” mpts value can be challenging: depending on the data distribution, a high or low mpts value may be more appropriate, and certain clusters may reveal themselves at different values. To explore results for a range of mpts values, one has to run HDBSCAN* for each value independently, which can be computationally impractical. In this paper, we propose an approach to efficiently compute all HDBSCAN* hierarchies for a range of mpts values by building upon results from computational geometry to replace HDBSCAN*'s complete graph with a smaller equivalent graph. An experimental evaluation shows that our approach can obtain over one hundred hierarchies for the computational cost equivalent to running HDBSCAN* about twice, which corresponds to a speedup of more than 60 times, compared to running HDBSCAN* independently that many times. We also propose a series of visualizations that allow users to analyze a collection of hierarchies for a range of mpts values, along with case studies that illustrate how these analyses are performed.
- Subject
- clustering; density-based clustering; hierarchical clustering; data mining; relative neighborhood graph
- Identifier
- http://hdl.handle.net/1959.13/1437383
- Identifier
- uon:40332
- Identifier
- ISSN:1041-4347
- Language
- eng
- Reviewed
- Hits: 923
- Visitors: 921
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|