An Incremental Updating Algorithm Based on Prefix General List for Association Rules
Ming Yang · Chinese Journal of Computers · 2003
Finding association rules is a major aspect of data mining research. Efficient maintenance of discovered association rules is the key problem. Conventional maintenance algorithms employ same framework as Apriori. However, candidate set generation is still costly, and the algorithms need repeatedly scan the database, especially when there exist prolific patterns and /or long patterns. In this paper, we improve the structure of FP-tree and propose prefix general List——PG-List, and introduce mining and incremental updating algorithms of association rules based on PG-List——MARBPGL and IUABPGL. MARBPGL only scans transaction database twice; in worse case, IUABPGL only scans original transaction database once, scans incremental transaction database twice; both MARBPGL and IUABPGL need not generate candidate itemsets. Therefore, the two algorithms proposed avoid producing combinatorial explosion problem of knowledge and improve efficiently mining and maintenance of association rules. Theory analysis and experimental results show the feasibility and effectiveness of the two algorithms.