Multi-class clustering by analytical two-class formulas

Abstract

This paper proposes a new clustering method based on the hierarchical use of the analytical two-class clustering tool introduced by Lin and Tsai.(1) The method comprises two phases. In the first phase, called the splitting phase, the data set is hierarchically decomposed into some subsets. In the second phase, called the merging phase, the set-to-set distances between these subsets are checked so that some subsets can be merged back together to obtain better clustering results. We use the idea of the so-called dense cut to determine when to stop the splitting phase. We also use a trace-following technique for the so-called boundary data to reduce significantly the computational load involved in the merging phase. Two algorithms are provided, and many experiments are included to show that the data being processed are not required to be linearly separable, noiseless, or formed of spherical clusters.