Incremental Mining of Constrained Association Rules
Ahmed Ayad, Nagwa El-Makky, Yousry Taha · 2001
The problem of mining association rules has attracted a lot of attention in the research community. Several techniques for efficient discovery of association rules have appeared. However, it is nontrivial to perform incremental mining or efficient mining of constrained association rules, in spite of their practical benefits. The research community has recently focused on providing separate solutions for these two problems. Since many believe that constrained mining will be the standard, incremental mining of constrained rules will be necessary. In this paper, a new algorithm, ICAP, for incremental mining of constrained association rules is introduced. The concept of constrained negative border is also introduced and its usage for the maintenance of constrained association rules when new transaction data is added to a transactional database is proposed. This fast incremental mining technique is applied to the constrained association mining algorithm CAP. A key feature of the proposed algorithm is that it requires at most one scan of the original database only if the database insertions cause the constrained negative border to expand. Thus the speedup of incremental mining is combined with the flexibility of the framework of constrained frequent-set queries, CFQs, used for specifying user constraints on the produced association rules. The correctness of the proposed algorithm is studied and a proof of it is given. Several experiments were conducted to measure the relative performance of the new algorithm compared to the single alternative approach available so far, which is rerunning the CAP algorithm on the whole updated database. The results of the experiments show a significant improvement over rerunning CAP in almost all of the cases.