How to cite this WIREs title:
WIREs Data Mining Knowl Discov

Impact Factor: 7.250

A survey of erasable itemset mining algorithms

Overview

Tuong Le, Bay Vo, Giang Nguyen

Published Online: Oct 29 2014

DOI: 10.1002/widm.1137

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Pattern mining, one of the most important problems in data mining, involves finding existing patterns in data. This article provides a survey of the available literature on a variant of pattern mining, namely erasable itemset (EI) mining. EI mining was first presented in 2009 and META is the first algorithm to solve this problem. Since then, a number of algorithms, such as VME, MERIT, and dMERIT+, have been proposed for mining EI. MEI, proposed in 2014, is currently the best algorithm for mining EIs. In this study, the META, VME, MERIT, dMERIT+, and MEI algorithms are described and compared in terms of mining time and memory usage. WIREs Data Mining Knowl Discov 2014, 4:356–379. doi: 10.1002/widm.1137 This article is categorized under: Algorithmic Development > Association Rules

Mining time for T10I4D100K dataset.

[ Normal View | Magnified View ]

Mining time for Pumsb dataset.

[ Normal View | Magnified View ]

Mining time for Mushroom dataset.

[ Normal View | Magnified View ]

Mining time for Connect dataset.

[ Normal View | Magnified View ]

Mining time for Chess dataset.

[ Normal View | Magnified View ]

Mining time for Accidents dataset.

[ Normal View | Magnified View ]

Tree of EIs obtained using dPidset without sorting erasable 1‐itemsets for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Erasable 3‐itemsets of node {ed} for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Tree of EIs obtained using pidset for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Tree of all EIs obtained by MEI for DBe with ξ = 16%.

[ Normal View | Magnified View ]

All EIs of node {e} for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Erasable 2‐itemsets of node {e} for DBe with ξ = 16%.

[ Normal View | Magnified View ]

MEI algorithm.

[ Normal View | Magnified View ]

Efficient algorithm for subtracting two dPidsets.

[ Normal View | Magnified View ]

Complete set of erasable itemsets identified by dMERIT+ for DBe with ξ = 16%.

[ Normal View | Magnified View ]

EIs of node {e} for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Erasable 2‐itemsets of node {e} for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Erasable 1‐itemsets and their NC′_Set for DBe with ξ = 16%.

[ Normal View | Magnified View ]

dMERIT+ algorithm.

[ Normal View | Magnified View ]

Efficient method for subtracting two dNC'_Sets.

[ Normal View | Magnified View ]

Efficient method for combining two NC_Sets.

[ Normal View | Magnified View ]

Result of MERIT+ for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Erasable 1‐itemsets, E1, and its NC_Sets for DBe with ξ = 16%.

[ Normal View | Magnified View ]

MERIT algorithm.

[ Normal View | Magnified View ]

WPPC‐tree for DBe with ξ = 16%.

[ Normal View | Magnified View ]

Illustration of WPPC‐tree construction process for DBe.

[ Normal View | Magnified View ]

WPPC‐tree construction algorithm.

[ Normal View | Magnified View ]

VME algorithm.

[ Normal View | Magnified View ]

META algorithm.

[ Normal View | Magnified View ]

Memory usage for T10I4D100K dataset.

[ Normal View | Magnified View ]

Memory usage for Pumsb dataset.

[ Normal View | Magnified View ]

Memory usage for Mushroom dataset.

[ Normal View | Magnified View ]

Memory usage for Connect dataset.

[ Normal View | Magnified View ]

Memory usage for Chess dataset.

[ Normal View | Magnified View ]

Memory usage for Accidents dataset.

[ Normal View | Magnified View ]

References

Agrawal, R, Srikant, R. Fast algorithms for mining association rules. In: Proceedings of the International Conference on Very Large Databases, Santiago de Chile, Chile, 1994, 487–499.
Zaki, MJ, Parthasarathy, S, Ogihara, M, Li, W. New algorithms for fast discovery of association rules. In: Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, Newport Beach, California, USA, 1997, 283–286.
Lin, KC, Liao, IE, Chen, ZS. An improved frequent pattern growth method for mining association rules. Expert Syst Appl 2011, 38:5154–5161.
Vo, B, Le, B. Interestingness measures for mining association rules: combination between lattice and hash tables. Expert Syst Appl 2011, 38:11630–11640.
Vo, B, Hong, TP, Le, B. DBV‐Miner: a dynamic bit‐vector approach for fast mining frequent closed itemsets. Expert Syst Appl 2012, 39:7196–7206.
Vo, B, Hong, TP, Le, B. A lattice‐based approach for mining most generalization association rules. Knowl‐Based Syst 2013, 45:20–30.
Abdi, MJ, Giveki, D. Automatic detection of erythemato‐squamous diseases using PSO‐SVM based on association rules. Eng Appl Artif Intel 2013, 26:603–608.
Kang, KJ, Ka, B, Kim, SJ. A service scenario generation scheme based on association rule mining for elderly surveillance system in a smart home environment. Eng Appl Artif Intel 2012, 25:1355–1364.
Verykios, VS. Association rule hiding methods. WIREs Data Min Knowl Discov 2013, 3:28–36.
Agrawal, R, Gehrke, J, Gunopulos, D, Raghavan, P. Automatic subspace clustering of high dimensional data for data mining applications. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, WA, 1998, 94–105.
Lin, CW, Hong, TP, Lu, WH. The Pre‐FUFP algorithm for incremental mining. Expert Syst Appl 2009, 36:9498–9505.
Nguyen, LTT, Vo, B, Hong, TP, Thanh, HC. Classification based on association rules: a lattice‐based approach. Expert Syst Appl 2012, 39:11357–11366.
Nguyen, LTT, Vo, B, Hong, TP, Thanh, HC. CAR‐Miner: an efficient algorithm for mining class‐association rules. Expert Syst Appl 2013, 40:2305–2311.
Borgelt, C. Frequent item set mining. WIREs Data Min Knowl Discov 2012, 2:437–456.
Han, J, Pei, J, Yin, Y. Mining frequent patterns without candidate generation. In: International Proceedings of the 2000 ACM SIGMOD, Dallas, TX, 2000, 1–12.
Zaki, M, Gouda, K. Fast vertical mining using diffsets. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, 326–335.
Vo, B, Le, T, Coenen, F, Hong, TP. A hybrid approach for mining frequent itemsets. In: Proceedings of the 2013 IEEE International Conference on Systems, Man, and Cybernetics, Manchester, UK, 2013, 4647–4651.
Hong, TP, Lin, CW, Wu, YL. Maintenance of fast updated frequent pattern trees for record deletion. Comput Stat Data Anal 2009, 53:2485–2499.
Hong, TP, Lin, CW, Wu, YL. Incrementally fast updated frequent pattern trees. Expert Syst Appl 2008, 34:2424–2435.
Lin, CW, Hong, TP, Lu, WH. Using the structure of prelarge trees to incrementally mine frequent itemsets. New Generat Comput 2010, 28:5–20.
Lin, CW, Hong, TP. Maintenance of prelarge trees for data mining with modified records. Inform Sci 2014, 278:88–103.
Nath, B, Bhattacharyya, DK, Ghosh, A. Incremental association rule mining: a survey. WIREs Data Min Knowl Discov 2013, 3:157–169.
Vo, B, Le, T, Hong, TP, Le, B. Maintenance of a frequent‐itemset lattice based on pre‐large concept. In: Proceedings of the Fifth International Conference on Knowledge and Systems Engineering, Ha Noi, Vietnam, 2013, 295–305.
Vo, B, Le, T, Hong, TP, Le, B. An effective approach for maintenance of pre‐large‐based frequent‐itemset lattice in incremental mining. Appl Intell 2014, 41:759–775.
Lucchese, B, Orlando, S, Perego, R. Fast and memory efficient mining of frequent closed itemsets. IEEE Trans Knowl Data Eng 2006, 18:21–36.
Zaki, MJ, Hsiao, CJ. Efficient algorithms for mining closed itemsets andtheir lattice structure. IEEE Trans Knowl Data Eng 2005, 17:462–478.
Hu, J, Mojsilovic, A. High‐utility pattern mining: a method for discovery of high‐utility item sets. Pattern Recogn 2007, 40:3317–3324.
Lin, CW, Hong, TP, Lu, WH. An effective tree structure for mining high utility itemsets. Expert Syst Appl 2011, 38:7419–7424.
Lin, CW, Lan, GC, Hong, TP. An incremental mining algorithm for high utility itemsets. Expert Syst Appl 2012, 39:7173–7180.
Liu, J, Wang, K, Fung, BCM. Direct discovery of high utility itemsets without candidate generation. In: Proceedings of the IEEE 12th International Conference on Data Mining, Brussels, Belgium, 2012, 984–989.
Fan, W, Zhang, K, Cheng, H, Gao, J, Yan, X, Han, J, Yu, P, Verscheure, O. Direct mining of discriminative and essential frequent patterns via model‐based search tree. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, 2008, 230–238.
Gupta, R, Fang, G, Field, B, Steinbach, M, Kumar, V. Quantitative evaluation of approximate frequent pattern mining algorithms. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, 2008, 301–309.
Jin, R, Xiang, Y, Liu, L. Cartesian contour: a concise representation for a collection of frequent sets. In: Proceedings of ACM SIGKDD Conference, Paris, 2009, 417–425.
Poernomo, A, Gopalkrishnan, V. Towards efficient mining of proportional fault‐tolerant frequent itemsets. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, 2009, 697–705.
Aggarwal, CC, Li, Y, Wang, J, Wang, J. Frequent pattern mining with uncertain data. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, 2009, 29–38.
Aggarwal, CC, Yu, PS. A survey of uncertain data algorithms and applications. IEEE Trans Knowl Data Eng 2009, 21:609–623.
Leung, CKS. Mining uncertain data. WIREs Data Min Knowl Discov 2011, 1:316–329.
Lin, CW, Hong, TP. A new mining approach for uncertain databases using CUFP trees. Expert Syst Appl 2012, 39:4084–4093.
Wang, L, Cheung, DWL, Cheng, R, Lee, SD, Yang, XS. Efficient mining of frequent item sets on large uncertain databases. IEEE Trans Knowl Data Eng 2012, 24:2170–2183.
Yun, U, Shin, H, Ryu, KH, Yoon, E. An efficient mining algorithm for maximal weighted frequent patterns in transactional databases. Knowl‐Based Syst 2012, 33:53–64.
Vo, B, Coenen, F, Le, B. A new method for mining Frequent Weighted Itemsets based on WIT‐trees. Expert Syst Appl 2013, 40:1256–1264.
Deng, ZH. Mining top‐rank‐k erasable itemsets by PID_lists. Int J Intell Syst 2013, 28:366–379.
Deng, ZH, Xu, XR. Fast mining erasable itemsets using NC_sets. Expert Syst Appl 2012, 39:4453–4463.
Deng, ZH, Fang, G, Wang, Z, Xu, X. Mining erasable itemsets. In: Proceedings of the 8th IEEE International Conference on Machine Learning and Cybernetics, Baoding, Hebei, China, 2009, 67–73.
Deng, ZH, Xu, XR. An efficient algorithm for mining erasable itemsets. In: Proceedings of the 2010 International Conference on Advanced Data Mining and Applications (ADMA), Chongqing, China, 2010, 214–225.
Le, T, Vo, B. MEI: an efficient algorithm for mining erasable itemsets. Eng Appl Artif Intel 2014, 27:155–166.
Le, T, Vo, B, Coenen, F. An efficient algorithm for mining erasable itemsets using the difference of NC‐Sets. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Manchester, UK, 2013, 2270–2274.
Nguyen, G, Le, T, Vo, B, Le, B. A new approach for mining top‐rank‐k erasable itemsets. In: Sixth Asian Conference on Intelligent Information and Database Systems, Bangkok, Thailand, 2014, 73–82.
Agrawal, R, Imielinski, T, Swami, AN. Mining association rules between sets of items in large databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington DC, May 1993, 207–216.
Dong, J, Han, M. BitTableFI: an efficient mining frequent itemsets algorithm. Knowl‐Based Syst 2007, 20:329–335.
Grahne, G, Zhu, J. Fast algorithms for frequent itemset mining using FP‐trees. IEEE Trans Knowl Data Eng 2005, 17:1347–1362.
Song, W, Yang, B, Xu, Z. Index‐BitTableFI: an improved algorithm for mining frequent itemsets. Knowl‐Based Syst 2008, 21:507–513.
Deng, ZH, Wang, ZH, Jiang, JJ. A new algorithm for fast mining frequent itemsets using N‐lists. Sci China Inf Sci 2012, 55:2008–2030.
Deng, ZH, Wang, Z. A new fast vertical method for mining frequent patterns. Int J Comput Int Syst 2010, 3:733–744.
Liu, B, Hsu, W, Ma, Y. Integrating classification and association rule mining. In: ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD`98), New York, NY, 1998, 80–86.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts