Clustering by pattern similarity in large data sets

ABSTRACT

Clustering is the process of grouping a set of objects into classes of similar objects. Although definitions of similarity vary from one clustering model to another, in most of these models the concept of similarity is based on distances, e.g., Euclidean distance or cosine distance. In other words, similar objects are required to have close values on at least a set of dimensions. In this paper, we explore a more general type of similarity. Under the pCluster model we proposed, two objects are similar if they exhibit a coherent pattern on a subset of dimensions. For instance, in DNA microarray analysis, the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very much alike. Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks. E-commerce applications, such as collaborative filtering, can also benefit from the new model, which captures not only the closeness of values of certain leading indicators but also the closeness of (purchasing, browsing, etc.) patterns exhibited by the customers. Our paper introduces an effective algorithm to detect such clusters, and we perform tests on several real and synthetic data sets to show its effectiveness.

References

1. R. C. Agarwal, C. C. Aggarwal, and V. Parsad. Depth first generation of long patterns. In SIGKDD, 2000.]]
2. C. C. Aggarwal, C. Procopiuc, J. Wolf, P. S. Yu, and J. S. Park. Fast algorithms for projected clustering. In SIGMOD, 1999.]]
3. C. C. Aggarwal and P. S. Yu. Finding generalized projected clusters in high dimensional spaces. In SIGMOD, pages 70-81, 2000.]]
4. R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Authomatic subspace clustering of high dimensional data for data mining applications. In SIGMOD, 1998.]]
5. K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft. When is nearest neighbors meaningful. In Proc. of the Int. Conf. Database Theories, pages 217-235, 1999.]]
6. C. H. Cheng, A. W. Fu, and Y. Zhang. Entropy-based subspace clustering for mining numerical data. In SIGKDD, pages 84-93, 1999.]]
7. Y. Cheng and G. Church. Biclustering of expression data. In Proc. of 8th International Conference on Intelligent System for Molecular Biology, 2000.]]
8. P. D'haeseleer, S. Liang, and R. Somogyi. Gene expression analysis and genetic network modeling. In Pacific Symposium on Biocomputing, 1999.]]
9. M. Ester, H. Kriegel, J. Sander, and X. Xu. A density-bsed algorithm for discovering clusters in large spatial databases with noise. In SIGKDD, pages 226-231, 1996.]]
10. D. H. Fisher. Knowledge acquisition via incremental conceptual clustering. In Machine Learning, 1987.]]
11. K. Fukunaga. Introduction to Statistical Pattern Recognition. Academic Press, 1990.]]
12. H. V. Jagadish, J. Madar, and R. Ng. Semantic compression and pattern extraction with fascicles. In VLDB, pages 186-196, 1999.]]
13. R. S. Michalski and R. E. Stepp. Learning from observation: conceptual clustering. In Machine Learning: An Artificial Intelligence Approach, pages 331-363, 1983.]]
14. F. Murtagh. A survey of recent hierarchical clustering algorithms. In The Computer Journal, 1983.]]
15. H. Nagesh, S. Goil, and A. Choudhary. Mafia: Efficient and scalable subspace clustering for very large data sets. Technical Report 9906-010, Northwestern University, 1999.]]
16. R. T. Ng and J. Han. Efficient and effective clustering methods for spatial data mining. In VLDB, 1994.]]
17. J. Riedl and J. Konstan. Movielens dataset. In http://www.cs.umn.edu/Research/Group Lens.]]
18. U. Shardanand and P. Maes. Social information filtering: Algorithms for automating 'word of mouth'. In Proceeding of ACM CHI, pages 210-217, 1995.]]
19. S. Tavazoie, J. Hughes, M. Campbell, R. Cho, and G. Church. Yeast micro data set. In http://arep.med.harvard.edu/biclustering/yeast.matrix, 2000.]]
20. J. Yang, W. Wang, H. Wang, and P. S. Yu. Δ-clusters: Capturing subspace correlation in a large data set. In ICDE, pages 517-528, 2002.]]
21. T. Zhang, R. Ramakrishnan, and M. Livny. Birch: An efficient data clustering method for very large databases. In SIGMOD, pages 103-114, 1996.]]

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Systems biology

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Cluster analysis

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Clustering and classification

  • Information systems applications

    • Data mining

      • Clustering