Deriving quantitative models for correlation clusters

ABSTRACT

Correlation clustering aims at grouping the data set into correlation clusters such that the objects in the same cluster exhibit a certain density and are all associated to a common arbitrarily oriented hyperplane of arbitrary dimensionality. Several algorithms for this task have been proposed recently. However, all algorithms only compute the partitioning of the data into clusters. This is only a first step in the pipeline of advanced data analysis and system modelling. The second (post-clustering) step of deriving a quantitative model for each correlation cluster has not been addressed so far. In this paper, we describe an original approach to handle this second step. We introduce a general method that can extract quantitative information on the linear dependencies within a correlation clustering. Our concepts are independent of the clustering model and can thus be applied as a post-processing step to any correlation clustering algorithm. Furthermore, we show how these quantitative models can be used to predict the probability distribution that an object is created by these models. Our broad experimental evaluation demonstrates the beneficial impact of our method on several applications of significant practical importance.

REFERENCES

• 1: E. Achtert, C. Böhm, H.-P. Kriegel, P. Kröger, and A. Zimek. Robust, complete, and efficient correlation clustering. submitted.
• 2: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.61-72, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: 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
• 4: 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
• 5: Christian Bohm , Karin Kailing , Hans-Peter Kriegel , Peer Kroger, Density Connected Clustering with Local Subspace Preferences, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.27-34, November 01-04, 2004
• 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: Yizong Cheng , George M. Church, Biclustering of Expression Data, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.93-103, August 19-23, 2000
• 8: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1--31, 1977.
• 9: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd ACM International Conference on Knowledge Discovery and Data Mining (KDD), Portland, OR, 1996.
• 10: E. Georgii, L. Richter, U. Rückert, and S. Kramer. Analyzing microarray data using quantitative association rules. Bioinformatics, 21(Suppl. 2):ii1--ii8, 2005.
• 11: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 12: J. A. Hartigan. Direct clustering of a data matrix. Journal of the American Statistical Association, 67(337):123--129, 1972.
• 13: D. Husmeier. Sensitivity and specificity of inferring genetic regulatory interactions from microarray experiments with dynamic Bayesian networks. Bioinformatics, 19(17):2271--2282, 2003.
• 14: K. Kailing, H.-P. Kriegel, and P. Kröger. Density-connected subspace clustering for high-dimensional data. In Proceedings of the 4th SIAM International Conference on Data Mining (SDM), Orlando, FL, 2004.
• 15: Jinze Liu , Wei Wang, OP-Cluster: Clustering by Tendency in High Dimensional Space, Proceedings of the Third IEEE International Conference on Data Mining, p.187, November 19-22, 2003
• 16: Jian Pei , Xiaoling Zhang , Moonjung Cho , Haixun Wang , Philip S. Yu, MaPle: A Fast Algorithm for Maximal Pattern-based Clustering, Proceedings of the Third IEEE International Conference on Data Mining, p.259, November 19-22, 2003
• 17: Cecilia M. Procopiuc , Michael Jones , Pankaj K. Agarwal , T. M. Murali, A Monte Carlo algorithm for fast projective clustering, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564739]
• 18: Ulrich Ruckert , Lothar Richter , Stefan Kramer, Quantitative Association Rules Based on Half-Spaces: An Optimization Approach, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.507-510, November 01-04, 2004
• 19: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• 20: 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]
• 21: Haixun Wang , Wei Wang , Jiong Yang , Philip S. Yu, Clustering by pattern similarity in large data sets, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564737]
• 22: Geoffrey I. Webb, Discovering associations with numeric variables, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.383-388, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502569]
• 23: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 24: d-Clusters: Capturing Subspace Correlation in a Large Data Set, Proceedings of the 18th International Conference on Data Engineering, p.517, February 26-March 01, 2002
• 25: T. Yuster. The reduced row echelon form of a matrix is unique: A simple proof. Mathematics Magazine, 57(2):93--94, 1984.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms

Keywords:
cluster description, cluster model, clustering, correlation clustering, data mining