Towards efficient mining of proportional fault-tolerant frequent itemsets

ABSTRACT

Fault-tolerant frequent itemsets (FTFI) are variants of frequent itemsets for representing and discovering generalized knowledge. However, despite growing interest in this field, no previous approach mines proportional FTFIs with their exact support (FT-support).

This problem is difficult because of two concerns: (a) non anti-monotonic property of FT-support when relaxation is proportional, and (b) difficulty in computing FT-support. Previous efforts on this problem either simplify the general problem by adding constraints, or provide approximate solutions without any error guarantees.

In this paper, we address these concerns in the general FTFI mining problem. We limit the search space by providing provably correct anti monotone bounds for FT-support and develop practically efficient means of achieving them. Besides, we also provide an efficient and exact FT-support counting procedure.

Extensive experiments using real datasets validate that our solution is reasonably efficient for completely mining FTFIs. Implementations for the algorithms are available from www.cais.ntu.edu.sg/~vivek/pubs/ftfim09.

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: J. Besson, R. G. Pensa, C. Robardet, and J.-F. Boulicaut. Constraint-based mining of fault-tolerant patterns from boolean data. In KDID, pages 55--71, 2005.
• 3: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 4: T. Calders and B. Goethals. Depth-first non-derivable itemset mining. In SDM, 2005.
• 5: T. Calders and B. Goethals. Quick inclusion-exclusion. In KDID, pages 86--103, 2005.
• 6: H. Cheng, P. S. Yu, and J. Han. Approximate frequent itemset mining in the presence of random noise. In Soft Computing for Knowledge Discovery and Data Mining, pages 363--389, 2007.
• 7: Rohit Gupta , Gang Fang , Blayne Field , Michael Steinbach , Vipin Kumar, Quantitative evaluation of approximate frequent pattern mining algorithms, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401930]
• 8: J. Li, K. Sim, G. Liu, and L. Wong. Maximal quasi-bicliques with balanced noise tolerance: Concepts and co-clustering applications. In SDM, pages 72--83, 2008.
• 9: Jinze Liu , Susan Paulsen , Wei Wang , Andrew Nobel , Jan Prins, Mining Approximate Frequent Itemsets from Noisy Data, Proceedings of the Fifth IEEE International Conference on Data Mining, p.721-724, November 27-30, 2005 [doi>10.1109/ICDM.2005.93]
• 10: J. Pei, A. K. H. Tung, and J. Han. Fault-tolerant frequent pattern mining: Problems and challenges. In DMKD, 2001.
• 11: Ardian Kristanto Poernomo , Vivekanand Gopalkrishnan, Mining Statistical Information of Frequent Fault-Tolerant Patterns in Transactional Databases, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.272-281, October 28-31, 2007 [doi>10.1109/ICDM.2007.48]
• 12: A. K. Poernomo and V. Gopalkrishnan. Efficient computation of partial-support for mining interesting itemsets. In SDM, 2009.
• 13: J. K. Seppanen. Using and Extending Itemsets in Data Mining: Query Approximation, Dense Itemsets, and Tiles. PhD thesis, Helsinki University of Technology, May 2006.
• 14: Jouni K. Seppänen , Heikki Mannila, Dense itemsets, 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.1014140]
• 15: Kelvin Sim , Jinyan Li , Vivekanand Gopalkrishnan , Guimei Liu, Mining Maximal Quasi-Bicliques to Co-Cluster Stocks and Financial Ratios for Value Investment, Proceedings of the Sixth International Conference on Data Mining, p.1059-1063, December 18-22, 2006 [doi>10.1109/ICDM.2006.111]
• 16: Cheng Yang , Usama Fayyad , Paul S. Bradley, Efficient discovery of error-tolerant frequent itemsets in high dimensions, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.194-203, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502539]
• 17: M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In KDD, pages 283--286, 1997.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
anti monotone bound, error tolerance, frequent itemset, proportional fault tolerance