An effective algorithm for mining 3-clusters in vertically partitioned data

ABSTRACT

Conventional clustering algorithms group similar data points together along one dimension of a data table. Bi-clustering simultaneously clusters both dimensions of a data table. 3-clustering goes one step further and aims to concurrently cluster two data tables that share a common set of row labels, but whose column labels are distinct. Such clusters reveal the underlying connections between the elements of all three sets. We present a novel algorithm that discovers 3-clusters across vertically partitioned data. Our approach presents two new and important formulations: first we introduce the notion of a 3-cluster in partitioned data; and second we present a mathematical formulation that measures the quality of such clusters. Our algorithm discovers high quality, arbitrarily positioned, overlapping clusters, and is efficient in time. These results are exhibited in a comprehensive study on real datasets.

REFERENCES

• 1: G. Liu, K. Sim, and J. Li. Efficient Mining of large maximal bicliques In Dawak pp. 437--448, 2006.
• 2: Bernhard Ganter , C. Franzke , Rudolf Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: 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]
• 4: Lizhuang Zhao , Mohammed J. Zaki, TRICLUSTER: an effective algorithm for mining coherent clusters in 3D microarray data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066236]
• 5: Takeaki Uno , Masashi Kiyomi , Hiroki Arimura, LCM ver.3: collaboration of array, bitmap and prefix tree for frequent itemset mining, Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, p.77-86, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1133905.1133916]
• 6: Mohammed J. Zaki , Karam Gouda, Fast vertical mining using diffsets, 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.956788]
• 7: 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]
• 8: 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
• 9: H. Bian and R. Bhatnagar An Algorithm for Lattice-Structured Subspace Clustering. Proceedings of the SIAM International Conference on Data Mining, April 2005.
• 10: Yoon, S. Benini , L. De Micheli, G. Co-clustering: A Versatile Tool for Data Analysis in Biomedical Informatics. Information Technology in Biomedicine, IEEE Transactions on. Volume: 11, Issue: 4. pp.493--494.
• 11: Haiyun Bian , Raj Bhatnagar , Barrington Young, An Efficient Constraint-Based Closed Set Mining Algorithm, Proceedings of the Sixth International Conference on Machine Learning and Applications, p.67-72, December 13-15, 2007 [doi>10.1109/ICMLA.2007.15]
• 12: Haiyun Bian , Raj Bhatnagar, A Levelwise Search Algorithm for Interesting Subspace Clusters, Proceedings of the Fifth IEEE International Conference on Data Mining, p.573-576, November 27-30, 2005 [doi>10.1109/ICDM.2005.9]
• 13: 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]
• 14: S. Datta, C. Giannella, and H. Kargupta. K-Means Clustering over a Large, Dynamic Network. In Proceedings of 2006 SIAM Conference on Data Mining, Bethesda, MD, April 2006.
• 15: H. Dutta, C. Giannella, K. Borne and H. Kargupta. Distributed Top-K Outlier Detection from Astronomy Catalogs using the DEMAC System. Proceedings of the SIAM International Conference on Data Mining, Minneapolis, USA, April 2007
• 16: Souptik Datta , Hillol Kargupta, Uniform Data Sampling from a Peer-to-Peer Network, Proceedings of the 27th International Conference on Distributed Computing Systems, p.50, June 25-27, 2007
• 17: Eshref Januzaj , Hans-Peter Kriegel , Martin Pfeifle, Scalable density-based distributed clustering, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.231-244, September 20-24, 2004, Pisa, Italy
• 18: D. K. Tasoulis and M. N. Vrahatis. Unsupervised distributed clustering. In IASTED International Conference on Parallel and Distributed Computing and Networks, pages 347--351. Innsbruck, Austria, 2004.
• 19: Waseem Ahmad, Ashfaq Khokhar, Phoenix: Privacy Preserving Biclustering on Horizontally Partitioned Data amid Malicious Adversaries. ACM SIGKDD. San Jose, 2007
• 20: Arindam Banerjee, Sugato Basu, Srujana Merugu, "Multi-way Clustering on Relation Graphs." Proceedings of the SIAM International Conference on Data Mining. SDM-2007
• 21: Haiyun Bian , Raj Bhatnagar , Barrington Young, An Efficient Constraint-Based Closed Set Mining Algorithm, Proceedings of the Sixth International Conference on Machine Learning and Applications, p.67-72, December 13-15, 2007 [doi>10.1109/ICMLA.2007.15]

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

General Terms:
Algorithms

Keywords:
bi-clustering, formal concept analysis, multi-clustering