DARM: Decremental Association Rules Mining
- 1
- 2
- 3
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.
- 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.
- 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.
- 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
- 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
- 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
- A. Ceglar and J. F. Roddick, “Association Mining,” ACM Computing Surveys Journal, Vol. 38, No. 2, 2006, Article 5.
- 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.
- 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.
- 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.
- 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.
- 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.