Mining closed frequent itemsets for incremental and diminished database with lexicographic tree traversal

摘要

In this paper we design an algorithm for discovering and updating the closed frequent itemsets in the dynamic transaction database. When new transactions are added or transactions which exist in database are deleted from the original database, we do not need to re-generate discovered rules and repeat all the work done previously. The proposed algorithm uses vertical layout for data presentation where we associate with each itemset a list of transactions in which it occurs. We use lexicographic tree traversal to check every itemsets between the original database and incremental (diminished) database. There are nine cases between the original database and the incremental (diminished) database. By checking all these nine kinds of itemsets, we can find all closed frequent itemsets in the updated database. All frequent itemsets can be enumerated via simple tid-list (list of transaction identifier) intersections. By recording all closed frequent itemsets and infrequent 1-itemsets, we do not need to scan the original database, which is the most time-consuming.