A truly unsupervised, non-parametric clustering method

Abstract

Human perception is extremely adapted to group similar visual objects. The Gestalt school studied the perceptual organization and identified a set of rules that govern human perception. One of the earlier and most powerful qualities, or gestalts, is proximity, which states that spatial or temporal proximity of elements may induce to perceive them as a single group. From an algorithmic point of view, the main problem with the gestalt rules is their qualitative nature. Our goal is to design a clustering method that can be considered a quantitative assessment of the proximity gestalt. We show that this can be achieved by analyzing the inter-point distances of the Minimum Spanning Tree, a structure that is closely related to human perception. We present a method that relies on the sole characterization of non-clustered data, thus being capable of detecting non-clustered data as such, and to detect clusters of arbitrary shape. The method is fully unsupervised in the sense that the user input only relates to the nature of the problem to be treated, and not the clustering algorithm itself. Even the number of clusters does not need to be previously chosen. Strictly speaking the method involves one single parameter that controls the degree of reliability of the detected clusters. However, the algorithm can be considered parameter-free, as the result is not sensitive to its value.