An Easy-to-Implement Framework of Fast Subspace Clustering For Big Data Sets

Abstract

Subspace clustering has attracted much attention due to its successful application on many data mining and computer vision tasks. However, most subspace clustering algorithms suffer from the scalability and the curse of dimensionality problems. When the volume or the dimension of the datasets becomes high, these algorithms are infeasible for the high computational complexity and large memory requirement. To enable the fast implementation of subspace clustering on big datasets, this paper proposes a simple but effective subspace clustering framework called Fast Subspace Clustering (FSC), which adopts a "sampling, random projecting, clustering, and classifying" strategy. We prove that under certain conditions on the subspace and the original subspace clustering algorithm, both the time and space complexity of FSC is O(MN) for M samples in N-dimensional space. Experimental results on several real-world datasets demonstrate the effectiveness and efficiency of the proposed framework.