A novel construction of connectivity graphs for clustering and visualization

Abstract

We [5, 6] have recently investigated several families of clustering algorithms. In this paper, we show how a novel similarity function can be integrated into one of our algorithms as a method of performing clustering and show that the resulting method is superior to existing methods in that it can be shown to reliably find a globally optimal clustering rather than local optima which other methods often find. We discuss some of the current difficulties with using connectivity graphs for solving clustering problems, and then we introduce a new algorithm to build the connectivity graphs. We compare this new algorithm with some famous algorithms used to build connectivity graphs. The new algorithm is shown to be superior to those in the current literature. We also extend the method to perform topology preserving mappings and show the results of such mappings on artificial and real data.