Mining association rules from large databases of business data is an important topic in data mining. In many applications, there are explicit or implicit taxonomies (hierarchies) for items, so it may be useful to find associations at levels of the taxonomy other than the primitive concept level. Previous work on the mining of generalized association rules, however, assumed that the taxonomy of items remained unchanged, disregarding the fact that the taxonomy might be updated as new transactions are added to the database over time. If this happens, effectively updating the generalized association rules to reflect the database change and related taxonomy evolution is a crucial task. In this paper, we examine this problem and propose two novel algorithms, called IDTE and IDTE2, which can incrementally update the generalized association rules when the taxonomy of items evolves as a result of new transactions. Empirical evaluations show that our algorithms can maintain their performance even for large numbers of incremental transactions and high degrees of taxonomy evolution, and are faster than applying contemporary generalized association mining algorithms to the whole updated database.
R. Agrawal, T. Imielinski and A. Swami, Mining association rules between sets of items in large databases, Proceedings of 1993 ACM-SIGMOD International Conference on Management of Data (1993) 207—216.
2.
R. Agrawal and R. Srikant, Fast algorithms for mining association rules, Proceedings of the 20th International Conference on Very Large Data Bases (1994) 487—499.
3.
J. Han and Y. Fu, Discovery of multiple-level association rules from large databases, Proceedings of the 21st International Conference on Very Large Data Bases (1995) 420—431.
4.
R. Srikant and R. Agrawal, Mining generalized association rules, Proceedings of the 21st International Conference on Very Large Data Bases ( 1995) 407—419.
5.
K. Sriphaew and T. Theeramunkong, Fast algorithms for mining generalized frequent patterns of generalized association rules, IEICE Transactions on Information and Systems87(3) (2004) 761—770.
6.
M.A. Domingues and S.O. Rezende, Using taxonomies to facilitate the analysis of the association rules, Proceedings of the Second International Workshop on Knowledge Discovery and Ontologies ( 2005) 59—66.
7.
J. Han and Y. Fu, Dynamic generation and refinement of concept hierarchies for knowledge discovery in databases, Proceedings of AAAI'94 Workshop on Knowledge Discovery in Databases (1994) 157—168.
8.
S. Brin, R. Motwani, J.D. Ullman and S. Tsur, Dynamic itemset counting and implication rules for market-basket data, SIGMOD Record (26) (1997) 255—264.
9.
J.S. Park, M.S. Chen and P.S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of ACM-SIGMOD International Conference on Management of Data (1995) 175—186.
10.
A. Savasere, E. Omiecinski and S. Navathe, An efficient algorithm for mining association rules in large databases, Proceedings of the 21st International Conference on Very Large Data Bases (1995) 432—444.
11.
M.J. Zaki , Scalable algorithms for association mining, IEEE Transactions on Knowledge and Data Engineering12(2) (2000) 372—390.
12.
D.W. Cheung, J. Han, V.T. Ng and C.Y. Wong, Maintenance of discovered association rules in large databases: an incremental update technique, Proceedings of 1996 International Conference on Data Engineering (1996) 106—114.
13.
D.W. Cheung, S.D. Lee and B. Kao, A general incremental technique for maintaining discovered association rules , Proceedings of the 5th International Conference on Database Systems for Advanced Applications (1997) 185—194.
14.
T.P. Hong, C.Y. Wang and Y.H. Tao, A new incremental data mining algorithm using pre-large itemsets, Intelligent DataAnalysis5(2) (2001) 111—129.
15.
K.K. Ng and W. Lam, Updating of association rules dynamically, Proceedings of 1999 International Symposium Database Applications in Non-Traditional Environments (2000) 84—91.
16.
N.L. Sarda and N.V. Srinivas, An adaptive algorithm for incremental mining of association rules, Proceedings of the Ninth International Workshop on Database and Expert Systems Applications (1998) 240—245.
17.
S. Thomas, S. Bodagala, K. Alsabti and S. Ranka, An efficient algorithm for the incremental updation of association rules in large databases, Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (1997) 263—266.
18.
A. Veloso, W. Meira Jr , M. Carvalho, S. Parthasarathy and M.J. Zaki, Parallel, incremental and interactive mining for frequent itemsets in evolving databases, Proceedings of the 6th International Workshop on High Performance Data Mining: Pervasive and Data Stream Mining (2003) 617—620.
19.
D.W. Cheung, V.T. Ng and B.W. Tam, Maintenance of discovered knowledge: a case in multi-level association rules , Proceedings of 1996 International Conference on Knowledge Discovery and Data Mining (1996) 307—310.
20.
Y.F. Huang and C.M. Wu, Mining generalized association rules using pruning techniques, Proceedings of 2002 IEEE International Conference on Data Mining (2002) 227—234.
21.
T.P. Hong, T.J. Huang and C.S. Chang, Maintenance of multiple-level association rules for record modification, Proceedings of 2004 IEEE International Conference on Systems, Man & Cybernetics (2004) 3140—3145.
22.
M.C. Tseng and W.Y. Lin , Maintenance of generalized association rules with multiple minimum supports, Intelligent Data Analysis8(4) ( 2004) 417—436.
23.
B. Babcock, S. Babu, M. Datar, R. Motwani and J. Widom, Models and issues in data stream systems, Proceedings of the 2002 ACM Symposium on Principles of Database Systems ( 2002).
24.
L. Golab and M.T. Ozsu, Issues in data stream management, SIGMOD Record32(2) (2003) 5—14.
25.
R. Jin and G. Agrawal, Frequent pattern mining in data streams. In: C.C. Aggarwal (ed.), Data Streams: Models and Algorithms (Springer, 2007).
26.
G.S. Manku and R. Motwani, Approximate frequency counts over data streams, Proceedings of the 28th International Conference on Very Large Data Bases (2002) 346—357.
27.
H.F. Li, S.Y. Lee, and M.K. Shan, An efficient algorithm for mining frequent itemsets over the entire history of data streams, Proceedings of the 1st International Workshop on Knowledge Discovery in Data Streams (2004).
28.
R. Jin and G. Agrawal, An algorithm for in-core frequent itemset mining on streaming data, Proceedings of the 5th IEEE International Conference on Data Mining (2005) 210—217.
29.
J.X. Yu , Z. Chong, H. Lu , Z. Zhang and A. Zhou, A false negative approach to mining frequent itemsets from high speed transactional data streams, Information Sciences176(14) (2006) 1986—2015.
30.
M. Datar, A. Gionis, P. Indyk and R. Motwani, Maintaining stream statistics over sliding windows, Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (2002) 635—644.
31.
Y. Chi, H. Wang, P.S. Yu and R.R. Muntz, Moment: Maintaining closed frequent itemsets over a stream sliding window , Proceedings of the IEEE International Conference on Data Mining (2004) 59—66.
32.
J.H. Chang and W.S. Lee, Finding recent frequent itemsets adaptively over online data streams, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2003) 487—492.
33.
C. Giannella , J. Han , J. Pei , X. Yan and P.S. Yu , Mining frequent patterns in data streams at multiple time granularities. In: H. Kargupta , A. Joshi, K. Sivakumar and Y. Yesha (eds), Next Generation Data Mining, AAAI/ MIT (2003) 487—492.
