DARM: Decremental Association Rules Mining

Mohamed Taha, Tarek F. Gharib, Hamed Nassar

.

DOI: 10.4236/jilsa.2011.33019                

Abstract

Frequent item sets mining plays an important role in association rules mining. A variety of algorithms for finding frequent item sets in very large transaction databases have been developed. Although many techniques were proposed for maintenance of the discovered rules when new transactions are added, little work is done for maintaining the discovered rules when some transactions are deleted from the database. Updates are fundamental aspect of data management. In this paper, a decremental association rules mining algorithm is present for updating the discovered association rules when some transactions are removed from the original data set. Extensive experiments were conducted to evaluate the performance of the proposed algorithm. The results show that the proposed algorithm is efficient and outperforms other well-known algorithms.

Keywords

Decremental Mining, Association Rules Maintenance, Updating Association Rules

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Z. Q. Zhou and C. I. Ezeife, “A Low-Scan Incremental Association Rule Maintenance Method,” Proceedings of the 14th Canadian Conference on Artificial Intelligence (AI 2001), Ottawa, 2001, pp. 26-35.
[2]	R. Kashef and Y. El-Sonbaty, “NBP: Negative Border with Partitioning Algorithm for Incremental Mining of Association Rules,” Proceedings of the International Conference on Intelligent Systems Design and Applications (ISDA’04), Budapest, Hungary, August 2004.
[3]	G. Grahne and J. Zhu, “Fast Algorithms for Frequent Itemset Mining Using FP-Trees,” IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No. 10, 2005, pp. 1347-1362. doi:10.1109/TKDE.2005.166
[4]	R. C. Agarwal, C. C. Aggarwal and V. V. V. Prasad, “A Tree Projection Algorithm for Generation of Frequent Item Sets,” Parallel and Distributed Computing Journal, Vol. 61, No. 3, 2001, pp. 350-371. doi:10.1006/jpdc.2000.1693
[5]	J. Han, J. Pei and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” Proceedings of ACM-SIGMOD International Conference on Management of Data, Dallas, TX, 2000, pp. 1-12. doi:10.1145/342009.335372
[6]	A. Ceglar and J. F. Roddick, “Association Mining,” ACM Computing Surveys Journal, Vol. 38, No. 2, 2006, Article 5.
[7]	S. C. Zhang, J. L. Zhang and Z. Jin, “A Decremental Algorithm of Frequent Itemset Maintenance for Mining Updated Databases,” The Journal of Expert Systems with Applications, Vol. 36, No. 8, 2009, pp. 10890-10895.
[8]	S. C. Zhang, X. D. Wu, J. L. Zhang and C. Q. Zhang, “A Decremental Algorithm for Mining Dynamic Databases,” Proceedings of 7th International Conference on Data Warehousing and Knowledge Discovery (DaWak 2005), Copenhagen, 2005, pp. 305-314.
[9]	C. H. Lee, C. R. Lin and M. S. Chen, “Sliding-Window Filtering: An Efficient Algorithm for Incremental Mining,” Proceedings of 10th International Conference on Information and Knowledge Management, Atlanta, GA, 2001, pp. 263-270.
[10]	D. W. Cheung, J. Han, V. T. Ng and C. Y. Wong, “Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique,” Proceedings of 12th International Conference on Data Engineering, New Orleans, LA, 1996, pp. 106-114.
[11]	N. F. Ayan, A. U. Tansel and E. Arkun, “An Efficient Algorithm to Update Large Itemsets with Early Pruning,” Proceedings of 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, 1999, pp. 287-291.
[12]	D. W. Cheung, S. D. Lee and B. Kao, “A General Incremental Technique for Maintaining Discovered Association Rules,” Proceedings of 5th International Conference on Database Systems for Advanced Applications, Melbourne, 1997, pp. 185-194. doi:10.1142/9789812819536_0020
[13]	S. Thomas, S. Bodagala, K. Alsabti and S. Ranka, “An Efficient Algorithm for the Incremental Updating of Association Rules in Large Database,” Proceedings of 3rd International Conference on Data Mining and Knowledge Discovery, Newport Beach, CA, 1997, pp. 263-266.
[14]	C.-C. Chang, Y.-C. Li and J.-S. Lee, “An Efficient Algorithm for Incremental Mining of Association Rules,” Proceedings of 15th International IEEE Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications (RIDE-SDMA’05), Tokyo, 2005.
[15]	C. Xu and J. Wang, “An Efficient Incremental Algorithm for Frequent Itemsets Mining in Distorted Databases with Granular Computing,” Proceedings of 2006 IEEE/WIC/ ACM International Conference on Web Intelligence, Hong Kong, 2006, pp. 913-918.
[16]	Ch.-H. Chang, S.-H. Yang, “Enhancing SWF for Incremental Association Mining by Itemset Maintenance,” Proceedings of 7th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD 2003), Seoul, 2003, pp. 301-312.
[17]	S. C. Zhang, J. L. Zhang and Ch. Q. Zhang, “EDUA: An Efficient Algorithm for Dynamic Database Mining,” Information Sciences Journal, Vol. 177, No. 13, 2007, pp. 2756-2767. doi:10.1016/j.ins.2007.01.034
[18]	W. Lian, D. W. Cheung and S. M. Yiu, “Maintenance of Maximal Frequent Itemsets in Large Databases,” Proceedings of 2007 ACM Symposium on Applied Computing (SAC’07), Seoul, 2007, pp. 388-392.
[19]	M. L. Feng, G. Z. Dong, J. Y. Li, Y.-P. Tan and L. Wong, "Pattern Space Maintenance for Data Updates and Interactive Mining," Computational Intelligence, Vol. 26, No. 3, 2010, pp. 282-316. doi:10.1111/j.1467-8640.2010.00360.x