Incremental association rule mining: a survey

Overview

A. Ghosh, D. K. Bhattacharyya, B. Nath

Published Online: Feb 25 2013

DOI: 10.1002/widm.1086

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Abstract Association rule mining is a computationally expensive task. Despite the huge processing cost, it has gained tremendous popularity due to the usefulness of association rules. Several efficient algorithms can be found in the literature. This paper provides a comprehensive survey on the state‐of‐the‐art algorithms for association rule mining, specially when the data sets used for rule mining are not static. Addition of new data to a data set may lead to additional rules or to the modification of existing rules. Finding the association rules from the whole data set may lead to significant waste of time if the process has started from the scratch. Several algorithms have been evolved to attend this important issue of the association rule mining problem. This paper analyzes some of them to tackle the incremental association rule mining problem. © 2013 Wiley Periodicals, Inc. This article is categorized under: Algorithmic Development > Association Rules Technologies > Classification

Taxonomy of frequent itemset generation algorithms.

[ Normal View | Magnified View ]

References

Agrawal, R,Imeilinski, T,Swami, A.Mining association rules between sets of items in large databases. In:Proceeding of ACM SIGMOD Conference on Management of Data.Washington, DC: ACM;1993,207–216.
Nath, B,Bhattacharyya, DK,Ghosh, A.Faster generation of association rules.Int J Inform Technol Knowl Manage2008,1:267–279.
Srikant, R.Fast algorithms for mining association rules and sequential patterns. Ph.D thesis, University of Wisconsin, Madison, WI, 1996.
Han, J,Kamber, M.Data Mining Concepts and Techniques.San Francisco, CA: Morgan Kaufmann;2001.
Agrawal, R,Srikant, R.Mining sequential patterns. In:Proceedings of the 1995 International Conference on Data Engineering (ICDE95).Taipei, Taiwan;1995,3–14.
Agarwal, R,Mannila, H,Srikant, R,Toivonan, H,Verkamo, A.Fast discovery of association rules. In:Fayyad, U, Piatetsky‐Shapiro G, Smyth P, Uthurusamy R, (eds).Advances in KDD.Boston, MA: MIT Press;1996,307–328.
Brin, S,Motwani, R,Tsur, D,Ullman, J.Dynamic itemset counting and implication rules for market basket data. In:Proceedings of ACM SIGMOD International Conference on Management of Data.Tucson, AZ;1997,255–264.
Das, A,Bhattacharyya, DK,Kalita, J.Horizontal vs. vertical partitioning in association rule mining: a comparison. In:Proceedings of the 6th International Conference on Computational Intelligence and Natural Computation (CINC).Cary, NC;2003,1617–1620.
Park, JS,Chen, MS,Yu, PS.An effective hash based algorithm for mining association rules. In:Proceedings of ACM SIGMOD;1995,175–186.
Savasere, A,Omiecinski, E,Navathe, S.An efficient algorithm for mining association rules in large databases. In:Proceeding of the 1995 International Conference on Very Large Data Bases (VLDB95).Zurich, Switzerland;1995,432–443.
Toivonen, H.Sampling large databases for association rules. In:Proceeding of the 1996 International Conference on Very Large Data Bases (VLDB96).Bombay, India;1996,134–145.
Lin, DI,Kedem, ZM.Pincer‐search: an efficient algorithm for discovering the maximal frequent set. In:Proceedings of 6th European Conference on Extending DB Tech;1998,105–119.
Houtsma, M,Swami, A.Set‐oriented mining of association rules in relational databases. In:Proceedings of the 11th International Conference on Data Engineering;1995,25–33.
Cheung, DW,Han, J,Ng, VT,Wong, CY.Maintenance of discovered association rules in large databases: an incremental updating technique. In:Proceedings of 12th International Conference on Data Engineering.New Orleans, LA;1996,106–114.
Agrawal, R,Shafer, JC.Parallel mining of association rules: design, implementation, and experience.IEEE Trans Knowl Data Eng1996,8:962–969.
Cheung, DW,Han, J,Ng, V,Fu, A,Fu, Y.A fast distributed algorithm for mining association rules. In:Proceeding of the 1996 International Conference on Parallel and Distributed Information Systems.Miami Beach, FL;1996,31–44.
Zaki, MJ,Parthasarathy, S,Ogihara, M,Li, W.Parallel algorithm for discovery of association rules.Data Mining Knowl Discov1997,1:343–374.
Sarawagi, S,Thomas, S,Agrawal, R.Integrating association rule mining with relational database systems: alternatives and implications. In:Proceeding of the 1998 ACM‐SIGMOD International Conference on Management of Data (SIGMOD98).Seattle, WA;1998,343–354.
Grahne, G,Zhu, J.Fast algorithms for frequent itemset mining using fp‐trees.IEEE Trans Knowl Data Eng2005,17:1347–1362.
Juan, X,Feng, Y,Zhiyong, Z.Association rule mining and application in intelligent transportation system. In:Preceedings of the 27th Chinese Control Conference, China;2008,538–540.
Lee, CH,Chen, MS,Lin, CR.Progressive partition miner: an efficient algorithm for mining general temporal association rules.IEEE Trans Knowl Data Eng2003,15:1004–1017.
Zhang, C,Zhang, S,Webb, GI.Identifying approximate itemsets of interest in large databases.Appl Intell2003,18:91–104.
Park, JS,Ch, en M,Yu, PS.Efficient parallel data mining for association rules. In:Proceedings of ACM International Conference on Information and Knowledge Management.New York: ACM Press;1995,31–36.
Cheung, D.A fast distributed algorithm for mining association rules. In:Proceedings of 4th International Conference on Parallel and Distributed Information Systems.Los Alamitos, CA: IEEE Computer Society Press;1996,31–42.
Cheung, D,Xiao, Y.Effect of data skewness in parallel mining of association rules. In:Proceedings of Pacific‐Asia Conference on Knowledge Discovery and Data Mining.New York: Springer‐Verlag;1998,48–60.
Webb, GI.Filtered‐top‐k association discovery.WIREs Data Mining Knowl Discov2011,1:183–192.
Zhang, S,Wu, X.Fundamentals of association rules in data mining and knowledge discovery.WIREs Data Mining Knowl Discov2011,1:97–116.
Han, J,Pei, J,Yin, Y.Mining frequent patterns without candidate generation. In:Proceedings of 2000 ACM‐SIGMOD International Conference on Management of Data.Dallas, TX;2000,1–12.
Agarwal, R,Aggarwal, CC,Prasad, VVV.A tree projection algorithm for generation of frequent itemsets.J Parallel Distribut Comput2001,61:350–371.
Pei, J,Han, J,Mortazavi‐Asl, B,Pinto, H,Chen, Q,Dayal, U,Hsu, MC.Prefixspan: mining sequential patterns efficiently by prefix‐projected pattern growth. In:Proceeding of the 2001 International Conference on Data Engineering (ICDE01).Heidelberg, Germany;2001,215–224.
Liu, G,Lu, H,Lou, W,Yu, JX.On computing, storing and querying frequent patterns. In:Proceeding of the 2003 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD03).Washington, DC: ACM;2003,607–612.
Liu, J,Pan, Y,Wang, K,Han, J.Mining frequent item sets by opportunistic projection. In:Proceeding of the 2002 ACM SIGKDD International Conference on Knowledge Discovery in Databases (KDD02).Edmonton, Canada;2002,239–248.
Grahne, G,Zhu, J.Efficiently using prefix‐trees in mining frequent itemsets. In:Proceeding of the ICDM03 International Workshop on Frequent Itemset Mining Implementations (FIMI03).Melbourne, FL;2003,123–132.
Garcia, S,Luengo, J,Saez, JA,Lopez, V,Herrera, F.A survey of discretization techniues: taxonomy and empirical analysis in supervised learning.IEEE Trans Knowl Data Eng2012.
Cheung, DW,Lee, SD,Kao, B.A general incremental technique for maintaining discovered association rules. In:Proceedings of the 5th International Conference on Database System for Advanced Applications.Melbourn, Australia;1997,185–194.
Xu, B,Yi, T,Wu, F,Chen, Z.An incremental updating algorithm for mining association rules.J Electron2002,19:403–407.
Aumann, Y,Feldman, R,Lipshtat, O,Manilla, H.Borders: an efficient algorithm for association generation in dynamic databases.J Intell Inform Syst1999,12:61–73.
Ayan, NF,Tansel, AU,Arkun, ME.An efficient algorithm to update large itemsets with early pruning.Knowl Discov Data Mining1999,287–291.
Ng, R,Lakshamnan, VS,Han, J,Pang, A.Exploratory mining and pruning optimizations of constrained association rules. In:Proceedings of 1998 International Conference on Management of Data (ACM‐SIGMOD);1998,13–24.
Ganti, V,Gehrke, J,Ramakrishnan, R.DEMON:mining and monitoring evolving data.IEEE Trans Knowl Data Eng2001,13:50–63.
Ayad, AM.A new algorithm for incremental mining of constrained association rules Masters Thesis. Department of Computer Sciences and Automatic Control, Alexandria University, Alexandria, Egypt; 2000.
Ezeife, CI,Su, Y.Mining incremental association rules with generalized FP Tree. In:Proceedings of 15th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence.Calgary, Canada;2002,147–160.
Das, A,Bhattacharyya, DK.Rule mining for dynamic databases.Australasian J Inform Syst2005,13:19–39.
Guirguis, S,Ahmed, KM,Makky, NME,Hafez, AM.Mining the future: predicting itemsets support of association rules mining. In:Proceedings of Sixth IEEE International Conference on Data Mining ‐ Workshops (ICDMW`06);2006,474–478.
Amornchewin, R,Kreesuradej, W.Incremental association rule mining using promising frequent itemset algorithm. In:Proceedings of 6th International Conference on Information, Communications and Signal Processing;2007,1–5.
Amornchewin, R,Kreesuradej, W.False positive item set algorithm for incremental association rule.Int J Multimedia Ubiquitous Eng2009,4:1–12.
Gharib, TF,Nassar, H,Taha, M,Abraham, A.An efficient algorithm for incremental mining of temporal association rules.Data Knowl Eng2010,69:800–815.
Hong, TP,Lin, CW,Wu, YL.Incrementally fast updated frequent pattern trees.Expert Syst Appl2008,34:2424–2435.
Huang, JP,Chen, SJ,Kuo, HC.An efficient incremental mining algorithm‐QSD.Intell Data Anal2007,11:265–278.
Kao, B,Zhang, M,Yip, CL,Cheung, DW,Fayyad, U.Efficient algorithms for mining and incremental update of maximal frequent sequences.Data Mining Knowl Discov2005,10:87–116.
Laur, PA,Symphor, JE,Nock, R,Poncelet, P.Statistical supports for mining sequential patterns and improving the incremental update process on data streams.Intell Data Anal2007,11:29–47.
Li, J,Manoukian, T,Dong, G,Ramamohanarao, K.Incremental maintenance on the border of the space of emerging patterns.Data Mining Knowl Discov2004,9:89–116.
Lin, CW,Hong, TP,Lu, WH.The Pre‐FUFP algorithm for incremental mining.Expert Syst Appl2009,36:9498–9505.
Ou, JC,Lee, CH,Chen, MS.Efficient algorithms for incremental web log mining with dynamic thresholds.Int J Very Large Data Bases2008,17:827–845.
Pradeepini, G,Jyothi, S.Tree‐based incremental association rule mining without candidate itemset generation. In:Trends in Information Sciences Computing (TISC);2010,78–81.
Shaw, G,Xu, Y,Geva, S.Deriving non‐redundant approximate association rules from hierarchical datasets. In:Proceeding of the 17th ACM Conference on Information and Knowledge Management.Napa Valley, CA;2008,26–30.
Tseng, MC,Lin, WY,Jeng, R.Incremental maintenance of generalized association rules under taxonomy evolution.Inform Sci2008,34:174–195.
Yafi, E,Al Hegami, AS,Alam, MA,Biswas, R.Incremental mining of shocking association patterns.ProcWorld Acad Sci Eng Technol2009,49:801–805.
Ghosh, A,Nath, B.Multi‐objective rule mining using genetic algorithms.Inform Sci2004,163:123–133.
DeLima, P,Yen, G.Multiple objective evolutionary algorithm for temporal rule extraction In: 31st Annual Conference of IEEE Industrial Electronics Society, 2005 (IECON 2005); 2005, 1–6.
Nath, B,Bhattacharyya, DK,Ghosh, A.Discovering association rules from incremental datasets.Int J Comput Sci Commun2010,1:433–441.
Matthews, SG,Gongora, MA,Hopgood, AA.Evolving temporal fuzzy association rules from quantitative data with a multi‐objective evolutionary algorithm. Corchado, E,Kurzynski, M,Wozniak, M, (eds). In:Hybrid Artificial Intelligent Systems.Lecture Notes in Computer Science, Berlin, Germany: Springer;2011,6678:198–205.
Matthews, SG,Gongora, MA,Hopgood, AA.Evolving temporal association rules with genetic algorithms. Bramer, M,Petridis, M,Hopgood, A, (eds). In:Research and Development in Intelligent Systems XXVII.London: Springer;2010,107–120.
Mitra, S,Pal, SK,Mitra, P.Data mining in soft computing framework: a survey.IEEE Trans Neural Netw2002,13:3–14.
del, Jesús MJ,Gámez, JA,González, P,Puerta, JM.On the discovery of association rules by means of evolutionary algorithms.WIREs Data Mining Knowl Discov2011,1:397–415.
Kianmehr, K,Kaya, M,ElSheikh, AM,Jida, J,Alhajj, R.Fuzzy association rule mining framework and its application to effective fuzzy associative classification.WIREs Data Mining Knowl Discov2011,1:477–495.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

Incremental association rule mining: a survey

Browse by Topic

Access to this WIREs title is by subscription only.

The latest WIREs articles in your inbox