PuSH - Publication Server of Helmholtz Zentrum München

Mai, S.T.* ; He, X.* ; Hubig, N. ; Plant, C. ; Böhm, C.*

Active density-based clustering.

Proc. IEEE Inst. Electr. Electron. Eng., 508-517 (2013)
DOI
Open Access Green as soon as Postprint is submitted to ZB.
The density-based clustering algorithm DBSCAN is a fundamental technique for data clustering with many attractive properties and applications. However, DBSCAN requires specifying all pair wise (dis)similarities among objects that can be non-trivial to obtain in many applications. To tackle this problem, in this paper, we propose a novel active density-based clustering algorithm, named Act-DBSCAN, which works under a restricted number of used pair wise similarities. Act-DBSCAN exploits the pair wise lower-bounding (LB) similarities to initialize the cluster structure. Then, it adaptively selects the most informative pair wise LB similarities to update with the real ones in order to reconstruct the result until the budget limitation is reached. The goal is to approximate as much as possible the true clustering result with each update. Our Act-DBSCAN framework is built upon a proposed probabilistic model to score the impact of the update of each pair wise LB similarity on the change of the intermediate clustering structure. Deriving from this scoring system and the monotonicity and reduction property of our active clustering process, we propose the two efficient algorithms to iteratively select and update pair wise similarities and cluster structure. Experiments on real datasets show that Act-DBSCAN acquires good clustering results with only a few pair wise similarities, and requires only a small fraction of all pair wise similarities to reach the DBSCAN results. Act-DBSCAN also outperforms other related techniques such as active spectral clustering.
Altmetric
Additional Metrics?
[➜Log in]
Edit extra informations Login
Publication type Article: Journal article
Document type Scientific Article
Corresponding Author
Keywords Active clustering ; Density-based clustering ; Active lerning
ISSN (print) / ISBN 0018-9219
e-ISSN 1558-2256
Conference Title 2013 IEEE 13th International Conference on Data Mining
Conference Date 7-10 December 2013
Conference Location Dallas, TX
Journal Proceedings of the IEEE
Quellenangaben Volume: , Issue: , Pages: 508-517 Article Number: , Supplement: ,
Publisher Institute of Electrical and Electronics Engineers (IEEE)
Non-patent literature Publications
Reviewing status Peer reviewed
Institute(s) Research Unit Scientific Computing (ASC)