A top-down search grid based algorithm for fast subspace clustering

In this paper, a top-down search grid based algorithm is proposed to search all subspace that may contain clusters. Different from bottom-up search grid algorithms, the new approach starts from high-level subspace to low-level subspace, avoiding a lot of useless computation. Active spaces and grids are introduced to prune the search space, which reduces searching candidates dramatically. A new filter method based on active axis numbers is adopted to filter noise objects, since the noise is more serious in high-dimensional space. The advantages of the new approach are: it can discover clusters both on entire space and subspace; the computation complexity is proximate linear with objectpsilas number, space dimension, and clusterspsila dimension respectively; it is not sensitive to noise; it can find both disjoint clusters or overlap clusters; it can find clusters of arbitrary shape; it is also able to find any number of clusters in any number of dimensions and the number is not predetermined by a parameter.