Computational Aspects of Trimmed Single-Link Clustering

The main drawback of the single-link method is the chaining effect. A few observations between clusters can create a chain, i.e. a path of short edges joining the real clusters and thus making their single-link distances small. It has been suggested (Tabakis (1992a)) that a density estimator could help by eliminating those low-density observations creating the problem. Since the amount of trimming necessary is not known, we may have to compute and compare several minimal spanning trees using standard algorithms such as Prim’s algorithm. In this paper we are concerned with the computational aspects of the problem. In particular, we prove that trimmed single-link can be applied on n points in O(n2) time, i.e. its time complexity does not exceed that of the classical single-link method. We also discuss the space requirements of the method.