Computing Clusters of Correlation Connected objects

ABSTRACT

The detection of correlations between different features in a set of feature vectors is a very important data mining task because correlation indicates a dependency between the features or some association of cause and effect between them. This association can be arbitrarily complex, i.e. one or more features might be dependent from a combination of several other features. Well-known methods like the principal components analysis (PCA) can perfectly find correlations which are global, linear, not hidden in a set of noise vectors, and uniform, i.e. the same type of correlation is exhibited in all feature vectors. In many applications such as medical diagnosis, molecular biology, time sequences, or electronic commerce, however, correlations are not global since the dependency between features can be different in different subgroups of the set. In this paper, we propose a method called 4C (Computing Correlation Connected Clusters) to identify local subgroups of the data objects sharing a uniform but arbitrarily complex correlation. Our algorithm is based on a combination of PCA and density-based clustering (DBSCAN). Our method has a determinate result and is robust against noise. A broad comparative evaluation demonstrates the superior performance of 4C over competing methods such as DBSCAN, CLIQUE and ORCLUS.

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: 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: 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: 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
• 5: Daniel Barbará , Ping Chen, Using the fractal dimension to cluster datasets, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.260-264, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347145]
• 6: Independent Quantization: An Index Compression Technique for High-Dimensional Data Spaces, Proceedings of the 16th International Conference on Data Engineering, p.577, February 28-March 03, 2000
• 7: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 8: Kaushik Chakrabarti , Sharad Mehrotra, Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces, Proceedings of the 26th International Conference on Very Large Data Bases, p.89-100, September 10-14, 2000
• 9: 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]
• 10: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise". In Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD'96), Portland, OR, 1996.
• 11: S. Goil, H. Nagesh, and A. Choudhary. "MAFIA: Efficiant and Scalable Subspace Clustering for Very Large Data Sets". Tech. Report No. CPDC-TR-9906-010, Center for Parallel and Distributed Computing, Dept. of Electrical and Computer Engineering, Northwestern University, 1999.
• 12: A. Hinneburg and D. A. Keim. "An Efficient Approach to Clustering in Large Multimedia Databases with Noise". In Proc. 4th Int. Conf. on Knowledge Discovery and Data Mining (KDD'98), New York, NY, 1998.
• 13: B. Liebl, U. Nennstiel-Ratzel, R. von Kries, R. Fingerhut, B. Olgemöller, A. Zapf, and A. A. Roscher. "Very High Compliance in an Expanded MS-MS-Based Newborn Screening Program Despite Written Parental Consent". Preventive Medicine, 34(2):127--131, 2002.
• 14: 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
• 15: E. Parros Machado de Sousa, C. Traina, A. Traina, and C. Faloutsos. "How to Use Fractal Dimension to Find Correlations between Attributes". In Proc. KDD-Workshop on Fractals and Self-similarity in Data Mining: Issues and Approaches, 2002.
• 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: Saccharomyces Genome Database (SGD). http://www.yeastgenome.org/. (visited: Oktober/November 2003).
• 19: Jörg Sander , Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications, Data Mining and Knowledge Discovery, v.2 n.2, p.169-194, June 1998 [doi>10.1023/A:1009745219419]
• 20: S. Tavazoie, J. D. Hughes, M. J. Camphell, R. J. Cho, and C. G. M. "Systematic Determination of Genetic Network Architecture". Nature Genetics, 22:281--285, 1999.
• 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: Xiaowei Xu , Martin Ester , Hans-Peter Kriegel , Jörg Sander, A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.324-331, February 23-27, 1998
• 23: 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