Constraint programming for itemset mining

ABSTRACT

The relationship between constraint-based mining and constraint programming is explored by showing how the typical constraints used in pattern mining can be formulated for use in constraint programming environments. The resulting framework is surprisingly flexible and allows us to combine a wide range of mining constraints in different ways. We implement this approach in off-the-shelf constraint programming systems and evaluate it empirically. The results show that the approach is not only very expressive, but also works well on complex benchmark problems.

REFERENCES

• 1: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 2: Krzysztof R. Apt , Mark Wallace, Constraint Logic Programming using Eclipse, Cambridge University Press, New York, NY, 2007
• 3: Francesco Bonchi , Claudio Lucchese, On Closed Constrained Frequent Pattern Mining, Proceedings of the Fourth IEEE International Conference on Data Mining, p.35-42, November 01-04, 2004
• 4: Francesco Bonchi , Claudio Lucchese, Extending the state-of-the-art of constraint-based pattern discovery, Data & Knowledge Engineering, v.60 n.2, p.377-399, February, 2007 [doi>10.1016/j.datak.2006.02.006]
• 5: Cristian Bucilă , Johannes Gehrke , Daniel Kifer , Walker White, DualMiner: A Dual-Pruning Algorithm for Itemsets with Constraints, Data Mining and Knowledge Discovery, v.7 n.3, p.241-272, July 2003 [doi>10.1023/A:1024076020895]
• 6: Doug Burdick , Manuel Calimlim , Jason Flannick , Johannes Gehrke , Tomi Yiu, MAFIA: A Maximal Frequent Itemset Algorithm, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1490-1504, November 2005 [doi>10.1109/TKDE.2005.183]
• 7: James Cheng , Yiping Ke , Wilfred Ng, \delta-Tolerance Closed Frequent Itemsets, Proceedings of the Sixth International Conference on Data Mining, p.139-148, December 18-22, 2006 [doi>10.1109/ICDM.2006.1]
• 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: Eibe Frank , Ian H. Witten, Using a Permutation Test for Attribute Selection in Decision Trees, Proceedings of the Fifteenth International Conference on Machine Learning, p.152-160, July 24-27, 1998
• 10: B. Goethals and M. J. Zaki. Advances in frequent itemset mining implementations: report on FIMI'03. In SIGKDD Explorations Newsletter, volume 6, pages 109--117, 2004.
• 11: 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
• 12: 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
• 13: Francesca Rossi , Peter van Beek , Toby Walsh, Handbook of Constraint Programming (Foundations of Artificial Intelligence), Elsevier Science Inc., New York, NY, 2006
• 14: C. Schulte and P. J. Stuckey. Efficient constraint propagation engines. Transactions on Programming Languages and Systems, 2008. To appear.
• 15: Takeaki Uno , Masashi Kiyomi , Hiroki Arimura, LCM ver.3: collaboration of array, bitmap and prefix tree for frequent itemset mining, Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, p.77-86, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1133905.1133916]
• 16: 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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Theory

Keywords:
constraint programming, itemset mining