RIC: Parameter-free noise-robust clustering

ABSTRACT

How do we find a natural clustering of a real-world point set which contains an unknown number of clusters with different shapes, and which may be contaminated by noise? As most clustering algorithms were designed with certain assumptions (Gaussianity), they often require the user to give input parameters, and are sensitive to noise. In this article, we propose a robust framework for determining a natural clustering of a given dataset, based on the minimum description length (MDL) principle. The proposed framework, robust information-theoretic clustering (RIC), is orthogonal to any known clustering algorithm: Given a preliminary clustering, RIC purifies these clusters from noise, and adjusts the clusterings such that it simultaneously determines the most natural amount and shape (subspace) of the clusters. Our RIC method can be combined with any clustering technique ranging from K-means and K-medoids to advanced methods such as spectral clustering. In fact, RIC is even able to purify and improve an initial coarse clustering, even if we start with very simple methods. In an extension, we propose a fully automatic stand-alone clustering method and efficiency improvements. RIC scales well with the dataset size. Extensive experiments on synthetic and real-world datasets validate the proposed RIC framework.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
• 2: 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
• 3: Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.49-60, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Banfield, J. D. and Raftery, A. E. 1993. Model-based Gaussian and non-Gaussian clustering. Biometrics 49, 3, 803--821.
• 5: Arnab Bhattacharya , Vebjorn Ljosa , Jia-Yu Pan , Mark R. Verardo , Hyungjeong Yang , Christos Faloutsos , Ambuj K. Singh, ViVo: Visual Vocabulary Construction for Mining Biomedical Images, Proceedings of the Fifth IEEE International Conference on Data Mining, p.50-57, November 27-30, 2005 [doi>10.1109/ICDM.2005.151]
• 6: Christian Böhm , Karin Kailing , Peer Kröger , Arthur Zimek, Computing Clusters of Correlation Connected objects, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007620]
• 7: Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014064]
• 8: Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the ACM SIGKDD Conference on International Knowledge Discovery and Data Mining.
• 9: Grünwald, P. 2005. A tutorial introduction to the minimum description length principle. Advances in Minimum Description Length: Theory and Applications.
• 10: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 11: Hamerly, G. and Elkan, C. 2003. Learning the k in k-means. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS).
• 12: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 13: Jolliffe, I. 1986. Principal Component Analysis. Springer.
• 14: Murtagh, F. 1983. A survey of recent advances in hierarchical clustering algorithms. Comput. J. 26, 4, 354--359.
• 15: Ng, A., Jordan, M., and Weiss, Y. 2001. On spectral clustering: Analysis and an algorithm. In Proceedings of the Conference on Advances in Neural Information Processing Systems.
• 16: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 17: Dan Pelleg , Andrew W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, Proceedings of the Seventeenth International Conference on Machine Learning, p.727-734, June 29-July 02, 2000
• 18: Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]
• 19: Susanne Still , William Bialek, How Many Clusters? An Information-Theoretic Perspective, Neural Computation, v.16 n.12, p.2483-2506, December 2004 [doi>10.1162/0899766042321751]
• 20: Tibshirani, R., Walther, G., and Hastie, T. 2000. Estimating the number of clusters in a dataset via the gap statistic. Tech. Rep., Stanford University.
• 21: Tishby, N., Pereira, F. C., and Bialek, W. 2000. The information bottleneck method. In Proceedings of the 37th Allerton Conference on Communication, Control and Computing.
• 22: Anthony K. H. Tung , Xin Xu , Beng Chin Ooi, CURLER: finding and visualizing nonlinear correlation clusters, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066211]
• 23: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 24: Bin Zhang , Meichun Hsu , Umeshwar Dayal, K-Harmonic Means - A Spatial Clustering Algorithm with Boosting, Proceedings of the First International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining-Revised Papers, p.31-45, September 12, 2000
• 25: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

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

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Performance

Keywords:
Clustering, data summarization, noise robustness, parameter-free data mining