Cluster Trees on Manifolds

2013/07/24 by Sivaraman Balakrishnan, Balakrishnan, Sivaraman, Srivatsan Narayanan +7
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1307.6515

28 pages, 3 figures

arxiv created 2013/07/24 · arxiv updated 2013/07/25

Abstract

In this paper we investigate the problem of estimating the cluster tree for a density f supported on or near a smooth d-dimensional manifold M isometrically embedded in ℝ^D. We analyze a modified version of a k-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta. The main results of this paper show that under mild assumptions on f and M, we obtain rates of convergence that depend on d only but not on the ambient dimension D. We also show that similar (albeit non-algorithmic) results can be obtained for kernel density estimators. We sketch a construction of a sample complexity lower bound instance for a natural class of manifold oblivious clustering algorithms. We further briefly consider the known manifold case and show that in this case a spatially adaptive algorithm achieves better rates.

Related

• Efficient Clustering on Riemannian Manifolds: A Kernelised Random Projection Approach
• Rethinking k-means from manifold learning perspective
• Adaptive Manifold Clustering
• Manifold Clustering with Schatten p-norm Maximization
• Clustering is semidefinitely not that hard: Nonnegative SDP for manifold disentangling