Fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams

ABSTRACT

Patterns of contrast are a very important way of comparing multi-dimensional datasets. Such patterns are able to capture regions of high difference between two classes of data, and are useful for human experts and the construction of classifiers. However, mining such patterns is particularly challenging when the number of dimensions is large. This paper describes a new technique for mining several varieties of contrast pattern, based on the use of Zero-Suppressed Binary Decision Diagrams (ZBDDs), a powerful data structure for manipulating sparse data. We study the mining of both simple contrast patterns, such as emerging patterns, and more novel and complex contrasts, which we call disjunctive emerging patterns. A performance study demonstrates our ZBDD technique is highly scalable, substantially improves on state of the art mining for emerging patterns and can be effective for discovering complex contrasts from datasets with thousands of attributes.

REFERENCES

• 1: F. A. Aloul, I. L. Markov, and K. A. Sakallah. MINCE: A static global variable ordering for SAT and BDD. In Int'l Workshop on Logic Synthesis, 2001.
• 2: F. A. Aloul, M. N. Mneimneh, and K. Sakallah. ZBDD-based backtrack search SAT solver. In Int'l Workshop on Logic Synthesis, 2002.
• 3: James Bailey , Thomas Manoukian , Kotagiri Ramamohanarao, Fast Algorithms for Mining Emerging Patterns, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.39-50, August 19-23, 2002
• 4: James Bailey , Thomas Manoukian , Kotagiri Ramamohanarao, A Fast Algorithm for Computing Hypergraph Transversals and its Application in Mining Emerging Patterns, Proceedings of the Third IEEE International Conference on Data Mining, p.485, November 19-22, 2003
• 5: Stephen D. Bay , Michael J. Pazzani, Detecting Group Differences: Mining Contrast Sets, Data Mining and Knowledge Discovery, v.5 n.3, p.213-246, July 2001 [doi>10.1023/A:1011429418057]
• 6: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 7: Multi-resolution on compressed sets of clauses, Proceedings of the 12th IEEE International Conference on Tools with Artificial Intelligence, p.2, November 13-15, 2000
• 8: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 9: Guozhu Dong , Jinyan Li, Mining border descriptions of emerging patterns from dataset pairs, Knowledge and Information Systems, v.8 n.2, p.178-202, August 2005 [doi>10.1007/s10115-004-0178-1]
• 10: Guozhu Dong , Xiuzhen Zhang , Limsoon Wong , Jinyan Li, CAEP: Classification by Aggregating Emerging Patterns, Proceedings of the Second International Conference on Discovery Science, p.30-42, December 01, 1999
• 11: Jeff Edmonds , Jarek Gryz , Dongming Liang , Renée J. Miller, Mining for empty spaces in large data sets, Theoretical Computer Science, v.296 n.3, p.435-452, 14 March 2003 [doi>10.1016/S0304-3975(02)00738-7]
• 12: Hongjian Fan , Kotagiri Ramamohanarao, Fast Discovery and the Generalization of Strong Jumping Emerging Patterns for Building Compact and Accurate Classifiers, IEEE Transactions on Knowledge and Data Engineering, v.18 n.6, p.721-737, June 2006 [doi>10.1109/TKDE.2006.95]
• 13: Hiroshige Fujii , Goichi Ootomo , Chikahiro Hori, Interleaving based variable ordering methods for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.38-41, November 07-11, 1993, Santa Clara, California, United States
• 14: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 15: Haym Hirsh, Generalizing Version Spaces, Machine Learning, v.17 n.1, p.5-46, Oct. 1994 [doi>10.1023/A:1022600917598]
• 16: Haiquan Li , Jinyan Li , Limsoon Wong , Mengling Feng , Yap-Peng Tan, Relative risk and odds ratio: a data mining perspective, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065215]
• 17: Jinyan Li , Guozhu Dong , Kotagiri Ramamohanarao, Making Use of the Most Expressive Jumping Emerging Patterns for Classification, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.220-232, April 18-20, 2000
• 18: J. Li, H. Liu, J. R. Downing, A. Yeoh, and L. Wong. Simple rules underlying gene expression profiles of more than six subtypes of Acute Lymphoblastic Leukaemia (ALL) patients. Bioinformatics, 19:71--78, 2003.
• 19: J. Li and L. Wong. Emerging patterns and gene expression data. In Proc. of the 12th Workshop on Genome Informatics, pages 3--13, 2001.
• 20: J. Li and L. Wong. Identifying good diagnostic gene groups from gene expression profiles using the concept of emerging patterns. Bioinformatics, 18(10):1406--1407, 2002.
• 21: B. Liu, L. P. Ku, and W. Hsu. Discovering interesting holes in data. In Proc. of IJCAI, pages 930--935, 1997.
• 22: Hongyan Liu , Jiawei Han , Dong Xin , Zheng Shao, Top-Down Mining of Interesting Patterns from Very High Dimensional Data, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.114, April 03-07, 2006 [doi>10.1109/ICDE.2006.161]
• 23: Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164890]
• 24: S. Minato. Zero-suppressed BDDs and their applications. Int'l Journal on Software Tools for Technology Transfer (STTT), 3(2):156--170, 2001.
• 25: Shin-ichi Minato , Hiroki Arimura, Efficient Method of Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs, Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration, p.4-11, April 08-09, 2005
• 26: A. Mishchenko. An introduction to Zero-suppressed Binary Decision Diagrams.
• 27: T. M. Mitchell. Generalization as Search. AI, 18(2):203--226, 1982.
• 28: Feng Pan , Gao Cong , Anthony K. H. Tung , Jiong Yang , Mohammed J. Zaki, Carpenter: finding closed patterns in long biological datasets, 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.956832]
• 29: A. Rauzy. Mathematical foundations of minimal cutsets. IEEE Transactions on Reliability, 50(4), 2001.
• 30: François Rioult , Jean-François Boulicaut , Bruno Crémilleux , Jérémy Besson, Using transposition for pattern discovery from microarray data, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882099]
• 31: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 32: Christoph Scholl , Bernd Becker , Andreas Brogle, The multiple variable order problem for binary decision diagrams: theory and practical application, Proceedings of the 2001 conference on Asia South Pacific design automation, p.85-90, January 2001, Yokohama, Japan [doi>10.1145/370155.370284]
• 33: M. Sebag. Delaying the choice of bias: A disjunctive version space approach. In Proc. of ICML 1996, pages 444--452.
• 34: F. Somenzi. CUDD: CU decision diagram package, 1997. Public software, Colorado University, Boulder.
• 35: A. Soulet, B. Cramilleux, and F. Rioult. Condensed representation of emerging patterns. In Proc. of PAKDD 04, pages 127--132, 2004.
• 36: 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
• 37: Geoffrey I. Webb , Shane Butler , Douglas Newlands, On detecting differences between groups, 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.956781]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
contrast patterns, disjunctive emerging patterns, zero-suppressed binary decision diagrams