Clustering with the Connectivity Kernel

Abstract

Clustering aims at extracting hidden structure in dataset. While the prob- lem of finding compact clusters has been widely studied in the litera- ture, extracting arbitrarily formed elongated structures is considered a much harder problem. In this paper we present a novel clustering algo- rithm which tackles the problem by a two step procedure: first the data are transformed in such a way that elongated structures become compact ones. In a second step, these new objects are clustered by optimizing a compactness-based criterion. The advantages of the method over related approaches are threefold: (i) robustness properties of compactness-based criteria naturally transfer to the problem of extracting elongated struc- tures, leading to a model which is highly robust against outlier objects; (ii) the transformed distances induce a Mercer kernel which allows us to formulate a polynomial approximation scheme to the generally NP- hard clustering problem; (iii) the new method does not contain free kernel parameters in contrast to methods like spectral clustering or mean-shift clustering.