FARMER: finding interesting rule groups in microarray datasets

ABSTRACT

Microarray datasets typically contain large number of columns but small number of rows. Association rules have been proved to be useful in analyzing such datasets. However, most existing association rule mining algorithms are unable to efficiently handle datasets with large number of columns. Moreover, the number of association rules generated from such datasets is enormous due to the large number of possible column combinations.In this paper, we describe a new algorithm called FARMER that is specially designed to discover association rules from microarray datasets. Instead of finding individual association rules, FARMER finds interesting rule groups which are essentially a set of rules that are generated from the same set of rows. Unlike conventional rule mining algorithms, FARMER searches for interesting rules in the row enumeration space and exploits all user-specified constraints including minimum support, confidence and chi-square to support efficient pruning. Several experiments on real bioinformatics datasets show that FARMER is orders of magnitude faster than previous association rule mining algorithms.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Roberto J. Bayardo, Jr. , Rakesh Agrawal, Mining the most interesting rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.145-154, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312219]
• 3: Constraint-Based Rule Mining in Large, Dense Databases, Proceedings of the 15th International Conference on Data Engineering, p.188, March 23-26, 1999
• 4: Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 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: G. Cong, A. K. H. Tung, X. Xu, F. Pan, and J. Yang. Farmer: Finding interesting rule groups in microarray datasets. Technical Report: National University of Singapore, 2004.
• 7: C. Creighton and S. Hanash. Mining gene expression databases for association rules. Bioinformatics, 19, 2003.
• 8: S. Doddi, A. Marathe, S. Ravi, and D. Torney. Discovery of association rules in medical data. Med. Inform. Internet. Med., 26:25--33, 2001.
• 9: 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
• 10: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest - A Framework for Fast Decision Tree Construction of Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.416-427, August 24-27, 1998
• 11: Jiawei Han , Jian Pei, Mining frequent patterns by pattern-growth: methodology and implications, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.14-20, Dec. 2000 [doi>10.1145/380995.381002]
• 12: T. Joachims. Making large-scale svm learning practical. 1999. svmlight.joachims.org/.
• 13: J. Li and L. Wong. Identifying good diagnostic genes or genes groups from gene expression data by using the concept of emerging patterns. Bioinformatics, 18:725--734, 2002.
• 14: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In Proc. 1998 Int. Conf. Knowledge Discovery and Data Mining (KDD'98).
• 15: S. Morishita and J. Sese. Traversing itemset lattices with statistical metric prunning. In Proc. of PODS, 2002.
• 16: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 17: 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]
• 18: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 19: J. L. Pfaltz and C. Taylor. Closed set mining of biological data. In Workshop on Data Mining in BIoinformatics with (SIGKDD02), 2002.
• 20: R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. In Proc. 1997 Int. Conf. Knowledge Discovery and Data Mining (KDD'97), 1997.
• 21: Jianyong Wang , Jiawei Han , Jian Pei, CLOSET+: searching for the best strategies for mining frequent closed itemsets, 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.956779]
• 22: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]
• 23: M. Zaki and C. Hsiao. Charm: An efficient algorithm for closed association rule mining. In Proc. of SIAM on Data Mining, 2002.