Clustering on Laplacian-embedded latent manifolds when clusters overlap
Stéphane Chrétien, Kavya Jagan, Elena Barton · Measurement Science and Technology · 2020
Abstract The purpose of clustering is to identify groups in a dataset in the hope of revealing some unforeseen latent discrete variable. Clustering however, is known to be one of the most difficult tasks in practice for two main reasons: (i) high dimensionality of data which requires appropriate feature extraction; and (ii) computational complexity of the associated optimisation problems. Spectral clustering was designed as a joint embedding and clustering technique that first embeds the data into a low dimensional space and then delineates between the clusters by considering the sign of the components of (a linearly transformed version of) the second eigenvector of a similarity matrix. Hence, spectral clustering seemingly solves the two main challenges associated with clustering problems, at least when the clusters are well separated. In this paper, we address the question of clustering when clusters overlap. In this regime, one relevant approach to clustering is to consider the modes of the point cloud distribution and, in particular, how the modes of the distribution of the raw data are mapped to the modes of the embedded data via the Laplacian eigenmap. The main contribution of the present paper is to provide a simulation study of the (approximate) mode-preserving property of Laplacian eigenmaps and how relevant the mode chasing approach is to high dimensional clustering. As a consequence of the mode-preserving property of Laplacian eigenmaps, this method is as good as finding modes in the original high dimensional space but with much better computational efficiency. The method is illustrated on simulated data and on satellite data relating to ground movement.