Generating frequent itemsets incrementally: two novel approaches based on Galois lattice theory

Valtchev, Petko; Missaoui, Rokia; Godin, Robert et Meridji, Mohamed (2002). « Generating frequent itemsets incrementally: two novel approaches based on Galois lattice theory ». Journal of Experimental & Theoretical Artificial Intelligence, 14(2-3), pp. 115-142.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (517kB)

Résumé

Galois (concept) lattice theory has been successfully applied in data mining for the resolution of the association rule problem. In particular, structural results about lattices have been used in the design of efficient procedures for mining the frequent patterns (itemsets) in transaction databases. Since such databases are often dynamic, we propose a detailed study of the incremental aspects in lattice construction to support effective procedures for incremental mining of frequent closed itemsets (FCIs). Based on a set of descriptive results about lattice substructures involved in incremental updates, the paper presents a novel algorithm for lattice construction that explores only limited parts of a lattice for updating. Two new methods for incremental FCI mining are studied: the first inherits its extensive search strategy from a classical lattice method, whereas the second applies the new lattice construction strategy to the itemset mining context. Unlike batch techniques based on FCIs, both methods avoid rebuilding the FCI family from scratch whenever new transactions are added to the database and/or when the minimal support is changed.

Type: Article de revue scientifique
Mots-clés ou Sujets: Market Basket Analysis, Association Rule Mining, Closed Itemset Extraction, Galois Lattices, Incremental Algorithms
Unité d'appartenance: Faculté des sciences > Département d'informatique
Déposé par: Petko Valtchev
Date de dépôt: 27 avr. 2016 13:38
Dernière modification: 19 mai 2016 18:10
Adresse URL : http://archipel.uqam.ca/id/eprint/8330

Statistiques

Voir les statistiques sur cinq ans...