A threshold criterion, auto-detection and its use in MST-based clustering

Article type: Research Article

Authors: He, Yu | Chen, Lihui

Affiliations: Department of Electrical and Electronic Engineering, Nanyang Technological University, Republic of Singapore, 639798. E-mail: heyv2002@yahoo.com, elhchen@ntu.edu.sg

Abstract: Clustering is to group data points into homogenous clusters so that data points within the same cluster are more similar than data points belonging to different clusters. There are many effective clustering algorithms for discovering arbitrary shaped clusters, but one common problem of many algorithms is the difficulty for users to decide appropriate parameters for these algorithms. To reduce the dependence of clustering performance on parameters, this paper proposes a threshold criterion for the single linkage cluster analysis and incorporates it into the Minimum Spanning Tree (MST) based clustering method. Since the threshold can be automatically decided according to the underlying data distributions, arbitrary shaped clusters can be discovered with little human intervention. The experimental results on spatial data are very encouraging.

Keywords: clustering, single linkage cluster analysis, arbitrary shaped clusters, minimum spanning trees, threshold criterion

DOI: 10.3233/IDA-2005-9303

Journal: Intelligent Data Analysis, vol. 9, no. 3, pp. 253-271, 2005