Computational Aspects of Trimmed SingleLink Clust

Authors: Evangelos Tabakis

Publish Date: 1996

Volume: , Issue: , Pages: 375-389

PDF Link

Abstract

The main drawback of the singlelink method is the chaining effect A few observations between clusters can create a chain ie a path of short edges joining the real clusters and thus making their singlelink distances small It has been suggested Tabakis 1992a that a density estimator could help by eliminating those lowdensity 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 singlelink can be applied on n points in On 2 time ie its time complexity does not exceed that of the classical singlelink method We also discuss the space requirements of the method

Keywords: