Association rule mining from a transaction database (TDB) is a classical data mining task, whereby the most computationally intensive step is the detection of frequently occurring patterns, called frequent itemsets (FIs), from which association rules are constructed at a later step. The number of FIs may be potentially large, leading to an even greater number of rules. In order to reduce the size of the rule set and increase its readability, some recent approaches rely on basic results from concept lattice theory. Thus, the association rule mining process has been reconsidered based on the notion of closed itemset (CI), while limiting the set of the extracted association rules to a basis, i.e., a minimal rule set that conveys all the information contained in the complete collection of rules. In the two steps of the process, the notion of CI generator plays a key role in the itemset (and rule) construction, while helping reduce the rule set and hence the computation cost.

In this talk, we present a straightforward approach to the maintenance of an association rule basis when a new transaction is added to the TDB. To that end, we recall a set of results related to the incremental update of lattices and extend them with novel properties to form a complete framework for an incremental maintenance of association rule bases. In particular, we define a simple and efficient method for incrementally maintaining the generators for closed itemsets and show how the results are used to efficiently update the rule basis.

References

Valtchev, P., Missaoui, R., Godin, R. & Meridji, M. (2002). A Framework for Incremental Generation of Frequent Closed Itemsets using Galois (Concept) Lattice Theory. Journal of Experimental and Theoretical Artificial Intelligence (JETAI). Special Issue on Concept Lattice based Theory, Methods and Tools for Knowledge Discovery in Databases, 14(2/3), p. 115-142, September 2002.

Valtchev, P., Rouane Hacene, M. & Missaoui, R. (2003). A generic scheme for the design of efficient on-line algorithms for concept lattices. Proceedings of the 11th International Conference on Conceptual Structures (ICCS’2003), July 2003, Dresden, Germany.

Valtchev, P. & Missaoui, R. (2001). Building Galois (Concept) Lattices From Parts: Generalizing the Incremental Approach. Proceedings of the 9th International Conference on Conceptual Structures (ICCS’2001), Stanford, CA, p. 290-303.