Efficient closed pattern mining in the presence of tough block constraints

ABSTRACT

Various constrained frequent pattern mining problem formulations and associated algorithms have been developed that enable the user to specify various itemset-based constraints that better capture the underlying application requirements and characteristics. In this paper we introduce a new class of block constraints that determine the significance of an itemset pattern by considering the dense block that is formed by the pattern's items and its associated set of transactions. Block constraints provide a natural framework by which a number of important problems can be specified and make it possible to solve numerous problems on binary and real-valued datasets. However, developing computationally efficient algorithms to find these block constraints poses a number of challenges as unlike the different itemset-based constraints studied earlier, these block constraints are tough as they are neither anti-monotone, monotone, nor convertible. To overcome this problem, we introduce a new class of pruning methods that significantly reduce the overall search space and present a computationally efficient and scalable algorithm called CBMiner to find the closed itemsets that satisfy the block constraints.

REFERENCES

• 1: R. Agarwal, C. Aggarwal, V. Prasad, and V. Crestana. A tree projection algorithm for generation of large itemsets for association rules. IBM Research Report, RC21341, November 1998.
• 2: 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
• 3: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 4: Constraint-Based Rule Mining in Large, Dense Databases, Proceedings of the 15th International Conference on Data Engineering, p.188, March 23-26, 1999
• 5: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 6: Cristian Bucila , Johannes Gehrke , Daniel Kifer , Walker White, DualMiner: a dual-pruning algorithm for itemsets with constraints, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775054]
• 7: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 8: A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing: Design and Analysis of Algorithms, 2nd Edition. Adison Wesley Publishing Company, 2003.
• 9: 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
• 10: K. Gade, J. Wang, and G. Karypis. Effcient Closed Pattern Mining in the Presence of Tough Block Constraints. Technical Report TR #03--45, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 2003. Available on the WWW at: http://cs.umn.edu/~karypis/publications.
• 11: George Karypis , Eui-Hong (Sam) Han, Fast supervised dimensionality reduction algorithm with applications to document categorization & retrieval, Proceedings of the ninth international conference on Information and knowledge management, p.12-19, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354772]
• 12: Daniel Kifer , Johannes Gehrke , Cristian Bucila , Walker White, How to quickly find a witness, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.272-283, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773180]
• 13: Carson Kai-Sang Leung , Laks V. S. Lakshmanan , Raymond T. Ng, Exploiting succinct constraints using FP-trees, ACM SIGKDD Explorations Newsletter, v.4 n.1, June 2002 [doi>10.1145/568574.568581]
• 14: Bing Liu , Wynne Hsu , Yiming Ma, Mining association rules with multiple minimum supports, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.337-341, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312274]
• 15: Guimei Liu , Hongjun Lu , Wenwu Lou , Jeffrey Xu Yu, On computing, storing and querying frequent 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.956827]
• 16: Raymond Ng , Laks V. S. Lakshmanan , Jiawei Han , Teresa Mah, Exploratory mining via constrained frequent set queries, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.556-558, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 17: 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
• 18: Jian Pei , Jiawei Han, Constrained frequent pattern mining: a pattern-growth view, ACM SIGKDD Explorations Newsletter, v.4 n.1, June 2002 [doi>10.1145/568574.568580]
• 19: Jian Pei , Jiawei Han , Laks V. S. Lakshmanan, Mining Frequent Item Sets with Convertible Constraints, Proceedings of the 17th International Conference on Data Engineering, p.433-442, April 02-06, 2001
• 20: Jian Pei , Jiawei Han , Hongjun Lu , Shojiro Nishio , Shiwei Tang , Dongqing Yang, H-Mine: Hyper-Structure Mining of Frequent Patterns in Large Databases, Proceedings of the 2001 IEEE International Conference on Data Mining, p.441-448, November 29-December 02, 2001
• 21: J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In Proc. of the DMKD'00, May 2000.
• 22: Masakazu Seno , George Karypis, LPMiner: An Algorithm for Finding Frequent Itemsets Using Length-Decreasing Support Constraint, Proceedings of the 2001 IEEE International Conference on Data Mining, p.505-512, November 29-December 02, 2001
• 23: R. Srikant, Q. Vu, and R. Agrawal. Mining associations rules with item constraints. In Proc. of the ACM SIGKDD'97, August 1997.
• 24: 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]
• 25: Ke Wang , Yu He , Jiawei Han, Mining Frequent Itemsets Using Support Constraints, Proceedings of the 26th International Conference on Very Large Data Bases, p.43-52, September 10-14, 2000
• 26: K. Wang, Y. Jiang, J. Xu Yu, G. Dong, and J. Han. Pusing aggregate constraints by divide-and-approximate. In Proc. of the ICDE'03, March 2003.
• 27: J. Wang and G. Karypis. BAMBOO: Accelerating closed itemset mining by deeply pushing the length-decreasing support constraint. In Proc. of the SDM'04, April 2004.
• 28: 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]
• 29: M. Zaki and C. Hsiao. Charm: An efficient algorithm for closed itemset mining. In Proc. of the SDM'02, April 2002.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
block constraint, closed pattern, tough constraint