Nonlinear subspace clustering using curvature constrained distances

• We proposed a new method to cluster multiple manifolds with the intersection.
• We defined a new notion of distance between points based on shortest constrained path.
• We applied our method to simulated and some real datasets and achieved good results.

The massive amount of high-dimensional data in science and engineering demands new trends in data analysis. Subspace techniques have shown remarkable success in numerous problems in computer vision and data mining, where the goal is to recover the low-dimensional structure of data in an ambient space. Traditional subspace methods like PCA and ICA assume that the data is coming from a single manifold. However, the data might come from several (possibly intersected) manifolds (surfaces). This has caused the development of new nonlinear techniques to cluster subspaces of high-dimensional data. In this paper, we propose a new algorithm for subspace clustering of data, where the data consists of several possibly intersected manifolds. To this end, we first propose a curvature constraint to find the shortest path between data points and then use it in Isomap for subspace learning. The algorithm chooses several landmark nodes at random and then checks whether there is a curvature constrained path between each landmark node and all other nodes in the neighborhood graph. It builds a binary feature vector for each point where each entry represents the connectivity of that point to a particular landmark. Then the binary feature vectors could be used as a input of conventional clustering algorithms such as hierarchical clustering. The performed experiments on both synthetic and real data sets confirm the performance of our algorithm.