Fast Multi-Scale Clustering and Manifold Identification in 2D and 3D

Dan Kushnir, Weizmann Institute

A multiscale approach for solving the clustering problem in 2D and 3D data is demonstrated. Our main motivation is to find partitions that are consistent with predefined features such as shape, dimensionality, and density. Starting from a graph representation, the algorithm constructs, through a bottom-up process, a hierarchy of data clusters. Similarity measures based on the multiscale features conduct this process of hierarchy construction. In addition, each cluster is described by its dimensionality, and approximated by a simplified manifold. As a feedback the simplified manifolds are used to improve the clustering. A top-down process is applied for resolving intersections of clusters and for detecting dense patterns inside noise. Our algorithm complexity is linear in the amount of data. It has been tested on 2D and 3D astrophysical and fluid turbulence data, and on representative 2D and 3D examples.

This is a joint work with Dr. Meirav Galun and Prof. Achi Brandt from the Weizmann Institute of Science, Rehovot, Israel.