research-article

An efficient method for mining frequent itemsets with double constraints

Authors:

Bay VoAuthors Info & Claims

Engineering Applications of Artificial Intelligence, Volume 27, Issue C

Pages 148 - 154

Published: 01 January 2014 Publication History

Abstract

Constraint-based frequent itemset mining is necessary when the needs and interests of users are the top priority. In this task, two opposite types of constraint are studied, namely anti-monotone and monotone constraints. Previous approaches have mainly mined frequent itemsets that satisfy one of these two types of constraint. Mining frequent itemsets that satisfy both types is of interest. The present study considers the problem of mining frequent itemsets with the following two conditions: they include a set C0 (monotone) and contain no items of set C'1 (anti-monotone), where the intersection of C0 and C'1 is empty and they are changed regularly. A unique representation of frequent itemsets restricted on C0 and C'1 using closed itemsets and their generators is proposed. Then, an algorithm called MFS_DoubleCons is developed to quickly and distinctly generate all frequent itemsets that satisfy the constraints from the lattice of closed itemsets and generators instead of mining them directly from the database. The theoretical results are proven to be reliable. Extensive experiments on a broad range of synthetic and real databases that compare MFS_DoubleCons to dEclat-DC (a modified version of dEclat utilized to mine frequent itemsets with constraints) show the effectiveness of our approach.

References

[1]

Agrawal, R., Srikant, R., 1994. Fast algorithms for mining association rules. In: Proceedings of the 20th International Conference on Very Large Data Bases, pp. 478-499.

[2]

Anh, T., Hai, D., Tin, T., Bac, L., 2011. Efficient algorithms for mining frequent itemsets with constraint. In: Proceedings of the Third International Conference on Knowledge and Systems Engineering, pp. 19-25.

[3]

Anh, T., Hai, D., Tin, T., Bac, L., 2012. Mining frequent itemsets with dualistic constraints. In Proceedings of the PRICAI 2012, LNAI, vol. 7458, Springer, pp. 807-813.

[4]

Anh, T., Tin, T., Bac, L., Hai, D., 2012. Mining association rules restricted on constraint. In Proceedings of the IEEE-RIVF 2012, pp. 51-56.

[5]

Anon{http://www.cs.rpi.edu/~zaki/wwwnew/pmwiki.php/Software/Software#patutils} (accessed 2010)

[6]

R.J. Bayardo, R. Agrawal, D. Gunopulos, Constraint-based rule mining in large, dense databases, Data Mining and Knowledge Discovery, 4 (2000) 217-240.

[7]

G. Birkhoff, Lattice Theory, American Mathematical Society, New York, 1948.

[8]

Bonchi, F., Lucchese, C., 2004. On closed constrained frequent pattern mining. In: Proceedings of the IEEE ICDM'04, pp. 35-42.

[9]

Bonchi, F., Giannotti, F., Mazzanti, A., Pedreschi, D., 2003. Examiner: optimized level-wise frequent pattern mining with monotone constraints. In Proceedings of the IEEE ICDM'03, pp. 11-18.

[10]

Boulicaut, J.F., Bykowski, A., 2000. Frequent closures as a concise representation for binary Data Mining. In Proc. PAKDD'00, vol. 1805, pp. 62-73, Springer.

[11]

J.F. Boulicaut, A. Bykowski, C. Rigotti, Free-sets: a condensed representation of boolean data for the approximation of frequency queries, Data Mining and Knowledge Discovery, 7 (2003) 5-22.

[12]

C. Bucila, J.E. Gehrke, D. Kifer, W. White, Dualminer: a dual-pruning algorithm for itemsets with constraints, Data Mining and Knowledge Discovery, 7 (2003) 241-272.

[13]

Burdick, D, Calimlim, M, Gehrke, J., 2001. MAFIA: a maximal frequent itemset algorithm for transactional databases. In Proceedings of the IEEE ICDE'01, pp. 443-452 .

[14]

J. Dong, M. Han, BitTable-FI: an efficient mining frequent itemsetsalgorithm, Knowledge Based Systems, 20 (2007) 329-335.

Digital Library

[15]

Frequent Itemset Mining Dataset Repository (FIMDR), {http://fimi.cs.helsinki.fi/data/} (accessed 2009)

[16]

G. Grahne, J. Zhu, Fast algorithms for frequent itemset mining using fp-trees, IEEE Transactions on Knowledge and Data Engineering, 17 (2005) 1347-1362.

Digital Library

[17]

Hai, D., Tin, T., Bac, L., 2013. An efficient algorithm for mining frequent itemsets with single constraint. In: Proceedings of ICCSAMA 2013, Advanced Computational Methods for Knowledge Engineering, Springer, pp. 367-378.

[18]

Han, J., Pei, J., Yin, Y., 2000. Mining frequent patterns without candidate generation. SIGMOD'00, 1-12.

[19]

B. Jeudy, J.F. Boulicaut, Optimization of association rule mining queries, Intelligent Data Analysis, 6 (2002) 341-357.

Digital Library

[20]

D.I. Lin, Z.M. Kedem, Pincer search: an efficient algorithm for discovering the maximum frequent sets, IEEE Transactions on Knowledge and Data Engineering, 14 (2002) 553-566.

Digital Library

[21]

H. Mannila, H. Toivonen, Levelwise search and borders of theories in knowledge discovery, Data Mining and Knowledge Discovery, 1 (1997) 241-258.

[22]

Nguyen, R.T., Lakshmanan, V.S., Han, J., Pang, A., 1998. Exploratory mining and pruning optimizations of constrained association rules. In Proceedings of the 1998 ACM-SIG-MOD International Conference on the Management of Data, pp. 13-24 .

[23]

N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering frequent closed itemsets for association rules, ICDT'12 (1999) 398-416.

[24]

N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Efficient mining of association rules using closed itemset lattices, In: Information Systems, 24 (1999) 25-46.

[25]

N. Pasquier, R. Taouil, Y. Bastide, G. Stumme, L. Lakhal, Generating a condensed representation for association rules, Journal of Intelligent Information Systems, 24 (2005) 29-60.

Digital Library

[26]

J. Pei, J. Han, Constrained frequent pattern mining: A Pattern-Growth view, ACM SIGKDD Explorations, 4 (2002) 31-39.

Digital Library

[27]

Pei, J., Han, J., & Mao, R., 2000. CLOSET: an efficient algorithm for mining frequent closed itemsets. SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, p. 11-20.

[28]

Pei, J., Han, J., Lakshmanan, L.V.S., 2001. Mining frequent itemsets with convertible constraints. In Proceedings of the IEEE ICDE'01, pp. 433-442

[29]

W. Song, B. Yang, Z. Xu, Index-BitTableFI: an improved algorithm formining frequent itemsets, Knowledge Based Systems, 21 (2008) 507-513.

Digital Library

[30]

Srikant, R., Vu, Q., Agrawal, R., 1997. Mining association rules with item constraints. In Proc. KDD'97, pp. 67-73.

[31]

Tin, T., Anh, T., 2010. Structure of set of association rules based on concept lattice. Adv. in Intelligent Infor. and Database Systems, SCI, 283, Springer, p. 217-227.

[32]

B. Vo, T.P. Hong, B. Le, DBV-Miner: a dynamic bit-vector approach for fast mining frequent closed itemsets, Expert Systems with Applications, 39 (2012) 7196-7206.

[33]

B. Vo, T.P Hong, B. Le, A lattice-based approach for mining most generalization association rules, Knowledge-Based Systems, 45 (2013) 20-30.

Digital Library

[34]

J. Wang, J. Han, J. Pei, CLOSET+: searching for the best strategies for mining frequent closed itemsets, SIGKDD'03 (2003) 236-245.

[35]

R. Wille, Concept lattices and conceptual knowledge systems, Computers & Mathematics with Applications, 23 (1992) 493-515.

[36]

Zaki, M.J. 2004. Mining Non-Redundant Association Rules. Data Mining and Knowledge Discovery, pp. 223-248

[37]

M.J. Zaki, C.J. Hsiao, Efficient algorithms for mining closed itemsets and their lattice structure, IEEE Transactions on Knowledge and Data Engineering, 17 (2005) 462-478.

Digital Library

[38]

Zaki, M.J., Parthasarathy, S., Ogihara, M., Li, W., 1997. New algorithms for fast discovery of association rules. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (KDD'97), pp. 283-296.

Cited By

Javed MNawaz WKhan K(2021)HOVA-FPPMScientific Programming10.1155/2021/88411882021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8841188
Le TNguyen AHuynh BVo BPedrycz W(2018)Mining constrained inter-sequence patternsApplied Intelligence10.1007/s10489-017-1123-948:5(1327-1343)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10489-017-1123-9
Mai TVo BNguyen L(2017)A lattice-based approach for mining high utility association rulesInformation Sciences: an International Journal10.1016/j.ins.2017.02.058399:C(81-97)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.ins.2017.02.058
Show More Cited By

An efficient method for mining frequent itemsets with double constraints
1. Information systems
  1. Information systems applications

Recommendations

An efficient method for mining association rules based on minimum single constraints

Mining association rules with constraints allow us to concentrate on discovering a useful subset instead of the complete set of association rules. With the aim of satisfying the needs of users and improving the efficiency and effectiveness of mining ...
Mining frequent itemsets with dualistic constraints
PRICAI'12: Proceedings of the 12th Pacific Rim international conference on Trends in Artificial Intelligence

Mining frequent itemsets can often generate a large number of frequent itemsets. Recent studies proposed mining itemset with the different types of constraint. The paper is to mine frequent itemsets, where a one: does not contain any item of C₀ or ...
Efficient Algorithms for Mining Closed Itemsets and Their Lattice Structure

The set of frequent closed itemsets uniquely determines the exact frequency of all itemsets, yet it can be orders of magnitude smaller than the set of all frequent itemsets. In this paper, we present CHARM, an efficient algorithm for mining all frequent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Engineering Applications of Artificial Intelligence

Engineering Applications of Artificial Intelligence Volume 27, Issue C

January 2014

250 pages

ISSN:0952-1976

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 January 2014

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Javed MNawaz WKhan K(2021)HOVA-FPPMScientific Programming10.1155/2021/88411882021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8841188
Le TNguyen AHuynh BVo BPedrycz W(2018)Mining constrained inter-sequence patternsApplied Intelligence10.1007/s10489-017-1123-948:5(1327-1343)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10489-017-1123-9
Mai TVo BNguyen L(2017)A lattice-based approach for mining high utility association rulesInformation Sciences: an International Journal10.1016/j.ins.2017.02.058399:C(81-97)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.ins.2017.02.058
Tran ATruong TLe B(2017)Efficiently mining association rules based on maximum single constraintsVietnam Journal of Computer Science10.1007/s40595-017-0096-24:4(261-277)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s40595-017-0096-2
Ryang HYun U(2016)High utility pattern mining over data streams with sliding window techniqueExpert Systems with Applications: An International Journal10.1016/j.eswa.2016.03.00157:C(214-231)Online publication date: 15-Sep-2016
https://dl.acm.org/doi/10.1016/j.eswa.2016.03.001
Lin JWu TFournier-Viger PLin GZhan JVoznak M(2016)Fast algorithms for hiding sensitive high-utility itemsets in privacy-preserving utility miningEngineering Applications of Artificial Intelligence10.1016/j.engappai.2016.07.00355:C(269-284)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.engappai.2016.07.003
Weng C(2016)Identifying association rules of specific later-marketed productsApplied Soft Computing10.1016/j.asoc.2015.09.04738:C(518-529)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.asoc.2015.09.047
Nguyen LNguyen N(2015)An improved algorithm for mining class association rules using the difference of ObidsetsExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.01.00242:9(4361-4369)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1016/j.eswa.2015.01.002
Fariha AAhmed CLeung CSamiullah MPervin SCao L(2015)A new framework for mining frequent interaction patterns from meeting databasesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2015.06.01945:C(103-118)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.engappai.2015.06.019
Chanda ASaha SNishi MSamiullah MAhmed C(2015)An efficient approach to mine flexible periodic patterns in time series databasesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2015.04.01444:C(46-63)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.engappai.2015.04.014

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents