EDSC: efficient density-based subspace clustering

ABSTRACT

Subspace clustering mines clusters hidden in subspaces of high-dimensional data sets. Density-based approaches have been shown to successfully mine clusters of arbitrary shape even in the presence of noise in full space clustering. Exhaustive search of all density-based subspace clusters, however, results in infeasible runtimes for large high-dimensional data sets. This is due to the exponential number of possible subspace projections in addition to the high computational cost of density-based clustering.

In this paper, we propose lossless efficient detection of density-based subspace clusters. In our EDSC (efficient density-based subspace clustering) algorithm we reduce the high computational cost of density-based subspace clustering by a complete multistep filter-and-refine algorithm. Our first hypercube filter step avoids exhaustive search of all regions in all subspaces by enclosing potentially density-based clusters in hypercubes. Our second filter step provides additional pruning based on a density monotonicity property. In the final refinement step, the exact unbiased density-based subspace clustering result is detected. As we prove that pruning is lossless in both filter steps, we guarantee completeness of the result.

In thorough experiments on synthetic and real world data sets, we demonstrate substantial efficiency gains. Our lossless EDSC approach outperforms existing density-based subspace clustering algorithms by orders of magnitude.

REFERENCES

• 1: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, ACM SIGMOD Record, v.28 n.2, p.61-72, June 1999
• 2: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, ACM SIGMOD Record, v.29 n.2, p.70-81, June 2000
• 3: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 4: Ira Assent , Ralph Krieger , Emmanuel Müller , Thomas Seidl, DUSC: Dimensionality Unbiased Subspace Clustering, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.409-414, October 28-31, 2007 [doi>10.1109/ICDM.2007.49]
• 5: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceedings of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 6: Chun-Hung Cheng , Ada Waichee Fu , Yi Zhang, Entropy-based subspace clustering for mining numerical data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.84-93, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312199]
• 7: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases. In KDD, pages 226--231, 1996.
• 8: A. Hinneburg and D. Keim. An efficient approach to clustering in large multimedia databases with noise. In KDD, pages 58--65, 1998.
• 9: I. Joliffe. Principal Component Analysis. Springer, New York, 1986.
• 10: K. Kailing, H.-P. Kriegel, and P. Kröger. Density-connected subspace clustering for high-dimensional data. In SDM, pages 246--257, 2004.
• 11: K. Kailing, H.-P. Kriegel, P. Kröger, and S. Wanka. Ranking interesting subspaces for clustering high dimensional data. In PKDD, pages 241--252, 2003.
• 12: Hans-Peter Kriegel , Peer Kroger , Matthias Renz , Sebastian Wurst, A Generic Framework for Efficient Subspace Clustering of High-Dimensional Data, Proceedings of the Fifth IEEE International Conference on Data Mining, p.250-257, November 27-30, 2005 [doi>10.1109/ICDM.2005.5]
• 13: Steffen L. Lauritzen, The EM algorithm for graphical association models with missing data, Computational Statistics & Data Analysis, v.19 n.2, p.191-201, Feb. 1995 [doi>10.1016/0167-9473(93)E0056-A]
• 14: J. MacQueen. Some methods for classification and analysis of multivariate observations. In Berkeley Symp. Math. stat. & prob., pages 281--297, 1967.
• 15: Gabriela Moise , Jorg Sander , Martin Ester, P3C: A Robust Projected Clustering Algorithm, Proceedings of the Sixth International Conference on Data Mining, p.414-425, December 18-22, 2006 [doi>10.1109/ICDM.2006.123]
• 16: H. Nagesh, S. Goil, and A. Choudhary. MAFIA: Efficient and scalable subspace clustering for very large data sets. In TR 9906--010, NWU, 1999.
• 17: D. Newman, S. Hettich, C. Blake, and C. Merz. UCI repository of MLDBs, 1998.
• 18: Karlton Sequeira , Mohammed Zaki, SCHISM: A New Approach for Interesting Subspace Mining, Proceedings of the Fourth IEEE International Conference on Data Mining, p.186-193, November 01-04, 2004
• 19: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Management

Keywords:
data mining, density-based clustering, efficiency, high-dimensional data, subspace clustering