Subspace Clustering

Textual data (esp in Vector Space Models) suffers from the Curse of Dimensionality

But often we can use the following idea:

  • correlation in high-dimensional data is usually local (esp. in text data)
  • for some data items features are correlated, but for some the same features are not

Subspace clustering:

  • it's the task of detecting all clusters in all subspaces
  • a data point may belong to many different clusters - with each cluster in some subspace

Survey paper:

  • Parsons, Lance, Ehtesham Haque, and Huan Liu. "Subspace clustering for high dimensional data: a review." (2004). [1]
  • Domeniconi, Carlotta, et al. "Subspace Clustering of High Dimensional Data." SDM. Vol. 73. 2004. [2]

There are two types of subspace clustering

  • based on how they determine a measure of locality for evaluating subspaces
  • bottom-up subspace search
  • top-down search

Bottom-up Subspace Search

Use downward closure property for density to reduce the search space (Apriori-style)


  • Agrawal, Rakesh, et al. Automatic subspace clustering of high dimensional data for data mining applications.1998. [3]


  • Cheng, Chun-Hung, Ada Waichee Fu, and Yi Zhang. "Entropy-based subspace clustering for mining numerical data." 1999. [4]


  • Goil, Sanjay, Harsha Nagesh, and Alok Choudhary. "MAFIA: Efficient and scalable subspace clustering for very large data sets." 1999. [5]


  • Chang, Jae-Woo, and Du-Seok Jin. "A new cell-based clustering method for large, high-dimensional data in data mining applications.", 2002. [6]


  • clustering via decision trees


  • Procopiuc, Cecilia M., et al. "A Monte Carlo algorithm for fast projective clustering." 2002. [7]

Iterative Top-Down Subspace Search


  • Aggarwal, Charu C., et al. "Fast algorithms for projected clustering." 1999. [8]


  • Aggarwal, Charu C., and Philip S. Yu. Finding generalized projected clusters in high dimensional spaces. 2000. [9]


  • Woo, Kyoung-Gu, et al. "FINDIT: a fast and intelligent subspace clustering algorithm using dimension voting." (2004). [10]


  • Yang, Jiong, et al. "δ-clusters: Capturing subspace correlation in a large data set." 2002. [11]


  • Friedman, Jerome H., and Jacqueline J. Meulman. "Clustering objects on subsets of attributes (with discussion)." (2004). [12]

Document Subspace Clustering

Text data is very high-dimensional

Adaptive subspace iteration:

  • reduce data
  • identify subspaces


Share your opinion