A scalable framework for discovering coherent co-clusters in noisy data

ABSTRACT

Clustering problems often involve datasets where only a part of the data is relevant to the problem, e.g., in microarray data analysis only a subset of the genes show cohesive expressions within a subset of the conditions/features. The existence of a large number of non-informative data points and features makes it challenging to hunt for coherent and meaningful clusters from such datasets. Additionally, since clusters could exist in different subspaces of the feature space, a co-clustering algorithm that simultaneously clusters objects and features is often more suitable as compared to one that is restricted to traditional "one-sided" clustering. We propose Robust Overlapping Co-Clustering (ROCC), a scalable and very versatile framework that addresses the problem of efficiently mining dense, arbitrarily positioned, possibly overlapping co-clusters from large, noisy datasets. ROCC has several desirable properties that make it extremely well suited to a number of real life applications.

REFERENCES

• 1: Arindam Banerjee , Inderjit Dhillon , Joydeep Ghosh , Srujana Merugu , Dharmendra S. Modha, A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation, The Journal of Machine Learning Research, 8, p.1919-1986, 12/1/2007
• 2: Simon Barkow , Stefan Bleuler , Amela Prelić , Philip Zimmermann , Eckart Zitzler, BicAT: a biclustering analysis toolbox, Bioinformatics, v.22 n.10, p.1282-1283, May 2006 [doi>10.1093/bioinformatics/btl099]
• 3: Amir Ben-Dor , Benny Chor , Richard Karp , Zohar Yakhini, Discovering local structure in gene expression data: the order-preserving submatrix problem, Proceedings of the sixth annual international conference on Computational biology, p.49-57, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565203]
• 4: Bergmann, S., Ihmels, J., & Barkai, N. (2003). Iterative signature algorithm for the analysis of large-scale gene expression data. Phys. Rev. E. Stat. Nonlin. Soft Matter Phys., 67.
• 5: 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
• 6: Hyuk Cho , Inderjit S. Dhillon, Coclustering of Human Cancer Microarrays Using Minimum Sum-Squared Residue Coclustering, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.3, p.385-400, July 2008 [doi>10.1109/TCBB.2007.70268]
• 7: Deodhar, M., Cho, H., Gupta, G., Ghosh, J., & Dhillon, I. (2008). Robust overlapping co-clustering. Dept. of ECE, Univ. of Texas at Austin, IDEAL-TR09, Downloadable from http://www.lans.ece.utexas.edu/papers/techreports/deodhar08ROCC.pdf.
• 8: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, A divisive information theoretic feature clustering algorithm for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 9: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 10: Ester, M., Kriegel, H., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Proc. Know. Disc. and Data Mining '96.
• 11: Gasch, A., Spellman, P., Kao, C., Carmel-Harel, et al. (2000). Genomic expression program in the response of yeast cells to environmental changes. Molecular Cell Biology, 11, 4241--4257.
• 12: Gordon, G. J., Jensen, R. V., Hsiao, L., Gullans, S. R., et al. (2002). Translation of microarray data into clinically relevant cancer diagnostic tests using gene expression ratios in lung cancer and mesothelioma. Cancer Research, 62, 4963--4967.
• 13: Gunjan Gupta , Joydeep Ghosh, Bregman Bubble Clustering: A Robust, Scalable Framework for Locating Multiple, Dense Regions in Data, Proceedings of the Sixth International Conference on Data Mining, p.232-243, December 18-22, 2006 [doi>10.1109/ICDM.2006.32]
• 14: Lazzeroni, L., & Owen, A. B. (2002). Plaid models for gene expression data. Statistica Sinica, 12, 61--86.
• 15: Martin H. C. Law , Mario A. T. Figueiredo , Anil K. Jain, Simultaneous Feature Selection and Clustering Using Mixture Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1154-1166, September 2004 [doi>10.1109/TPAMI.2004.71]
• 16: Lee, I., Date, S., Adai, A., & Marcotte, E. (2004). A probabilistic functional network of yeast genes. Science, 306, 1555--1558.
• 17: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 18: Murali, T., & Kasif, S. (2003). Extracting conserved gene expression motifs from gene expression data. Pacific Symposium on Biocomp., 8, 77--88.
• 19: Lance Parsons , Ehtesham Haque , Huan Liu, Subspace clustering for high dimensional data: a review, ACM SIGKDD Explorations Newsletter, v.6 n.1, p.90-105, June 2004 [doi>10.1145/1007730.1007731]
• 20: Amela Prelić , Stefan Bleuler , Philip Zimmermann , Anja Wille , Peter Bühlmann , Wilhelm Gruissem , Lars Hennig , Lothar Thiele , Eckart Zitzler, A systematic comparison and evaluation of biclustering methods for gene expression data, Bioinformatics, v.22 n.9, p.1122-1129, May 2006 [doi>10.1093/bioinformatics/btl060]
• 21: Tanay, A., Sharan, R., & Shamir, R. (2002). Discovering statistically significant biclusters in gene expression data. Bioinformatics, 18, 136--144.
• 22: 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]
• 23: Ward, J. (1963). Hierarchical grouping to optimize an objective function. Jl. of American Stat. Assoc., 58, 236--244.
• 24: Xin Xu , Ying Lu , Anthony K. H. Tung , Wei Wang, Mining Shifting-and-Scaling Co-Regulation Patterns on Gene Expression Profiles, Proceedings of the 22nd International Conference on Data Engineering, p.89, April 03-07, 2006 [doi>10.1109/ICDE.2006.98]
• 25: Sungroh Yoon , Christine Nardini , Luca Benini , Giovanni De Micheli, Discovering Coherent Biclusters from Gene Expression Data Using Zero-Suppressed Binary Decision Diagrams, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.4, p.339-354, October 2005 [doi>10.1109/TCBB.2005.55]
• 26: Mengsheng Zhang , Wei Wang , Jinze Liu, Mining Approximate Order Preserving Clusters in the Presence of Noise, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.160-168, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497424]

INDEX TERMS

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

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation; Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory