Direct mining of discriminative and essential frequent patterns via model-based search tree

ABSTRACT

Frequent patterns provide solutions to datasets that do not have well-structured feature vectors. However, frequent pattern mining is non-trivial since the number of unique patterns is exponential but many are non-discriminative and correlated. Currently, frequent pattern mining is performed in two sequential steps: enumerating a set of frequent patterns, followed by feature selection. Although many methods have been proposed in the past few years on how to perform each separate step efficiently, there is still limited success in eventually finding highly compact and discriminative patterns. The culprit is due to the inherent nature of this widely adopted two-step approach. This paper discusses these problems and proposes a new and different method. It builds a decision tree that partitions the data onto different nodes. Then at each node, it directly discovers a discriminative pattern to further divide its examples into purer subsets. Since the number of examples towards leaf level is relatively small, the new approach is able to examine patterns with extremely low global support that could not be enumerated on the whole dataset by the two-step method. The discovered feature vectors are more accurate on some of the most difficult graph as well as frequent itemset problems than most recently proposed algorithms but the total size is typically 50% or more smaller. Importantly, the minimum support of some discriminative patterns can be extremely low (e.g. 0.03%). In order to enumerate these low support patterns, state-of-the-art frequent pattern algorithm either cannot finish due to huge memory consumption or have to enumerate 10¹ to 10³ times more patterns before they can even be found. Software and datasets are available by contacting the author.

REFERENCES

• 1: http://dtp.nci.nih.gov. The Aids Antiviral Screen.
• 2: http://pubchem.ncbi.nlm.nih.gov. The PubChem Project.
• 3: 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
• 4: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 5: H. Cheng, X. Yan, J. Han, and C. Hsu. Discriminative frequent pattern analysis for effective classification. In Proc. of ICDE, 2007.
• 6: H. Cheng, X. Yan, J. Han, and P. Yu. Direct discriminative pattern mining for effective classification. In Proc. of ICDE, 2008.
• 7: Gao Cong , Kian-Lee Tan , Anthony K. H. Tung , Xin Xu, Mining top-K covering rule groups for gene expression data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066234]
• 8: Shengnan Cong , Jiawei Han , David Padua, Parallel mining of closed sequential patterns, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081937]
• 9: Mukund Deshpande , Michihiro Kuramochi , Nikil Wale , George Karypis, Frequent Substructure-Based Approaches for Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1036-1050, August 2005 [doi>10.1109/TKDE.2005.127]
• 10: Holger Fröhlich , Jörg K. Wegner , Florian Sieker , Andreas Zell, Optimal assignment kernels for attributed molecular graphs, Proceedings of the 22nd international conference on Machine learning, p.225-232, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102380]
• 11: Amol Ghoting , Gregory Buehrer , Srinivasan Parthasarathy , Daehyun Kim , Anthony Nguyen , Yen-Kuang Chen , Pradeep Dubey, Cache-conscious frequent pattern mining on a modern processor, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: G. Grahne and J. Zhu. Efficiently using prefix-trees in mining frequent itemsets. In ICDM Workshop on Frequent Itemset Mining Implementations (FIMI'03), 2003.
• 13: 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
• 14: Tamás Horváth , Thomas Gärtner , Stefan Wrobel, Cyclic pattern kernels for predictive graph mining, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014072]
• 15: Stefan Kramer , Luc De Raedt , Christoph Helma, Molecular feature mining in HIV data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.136-143, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502533]
• 16: T. Kudo, E. Maeda, and Y. Matsumoto. An application of boosting to graph classification. In Proc. of NIPS, pages 729--736, 2004.
• 17: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 18: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 19: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In Proc. of KDD, 1998.
• 20: P. Mahë, N. Ueda, T. Akutsu, J. Perret, and J. Vert. Extensions of marginalized graph kernels. In Proc. of ICML, pages 552--559, 2004.
• 21: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Helen Pinto , Qiming Chen , Umeshwar Dayal , Meichun Hsu, PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth, Proceedings of the 17th International Conference on Data Engineering, p.215-224, April 02-06, 2001
• 22: Nikil Wale , George Karypis, Comparison of Descriptor Spaces for Chemical Compound Retrieval and Classification, Proceedings of the Sixth International Conference on Data Mining, p.678-689, December 18-22, 2006 [doi>10.1109/ICDM.2006.39]
• 23: J. Wang and G. Karypis. HARMONY: Efficiently mining the best rules for classification. In Proc. of SDM, pages 205--216, 2005.
• 24: Xifeng Yan , Hong Cheng , Jiawei Han , Philip S. Yu, Mining significant graph patterns by leap search, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376662]
• 25: Xifeng Yan , Jiawei Han, CloseGraph: mining closed frequent graph patterns, 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.956784]
• 26: Guizhen Yang, Computational aspects of mining maximal frequent patterns, Theoretical Computer Science, v.362 n.1, p.63-85, 11 October 2006 [doi>10.1016/j.tcs.2006.05.029]
• 27: X. Yin and J. Han. Cpar: Classification based on predictive association rules. In Proc. of SDM, 2003.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
frequent pattern, graph mining, itemsets, scalability