Numéro spécial CARI'04 - novembre 2005 Fiche article : |
Algorithme de construction d'un treillis des concepts formels
et de détermination des générateurs minimaux
|
RÉSUMÉ.Le
nombre prohibitif de règles d'association qui peuvent être
dérivées même pour des bases de données de
taille raisonnable est à l'origine du développement de
techniques pour réduire la taille de l'ensemble de ces
règles. Dans ce contexte, les résultats obtenus par
l'Analyse de Concepts Formels (AFC) a permis de définir un
sous-ensemble de règles appelé base
générique. Cependant, un survol de la littérature
montre que tous les algorithmes qui leur sont dédiés ont
négligé une composante essentielle : soit la relation
d'ordre sous-jacente ou c'est l'extraction des
générateurs minimaux qui manque à l'appel. Dans ce
papier, nous proposons un algorithme, appelé GenAll, pour
construire un treillis de concepts formels, dans lequel chaque concept
formel est "décoré" par ses générateurs
minimaux. L'objectif de cet algorithme est d'extraire toute la
connaissance nécessaire pour extraire les bases
génériques des règles d'association. La principale
originalité de GenAll est l'emploi d'un processus de raffinement
des listes des successeurs immédiats pour déterminer,
d'une manière simultanée, l'ensemble des concepts
formels, leur ordre partiel sous-jacent et l'ensemble de
générateurs minimaux associés à chacun des
concepts formels. Les résultats expérimentaux ont
prouvé que l'algorithme proposé est
particulièrement efficace pour des contextes d'extraction denses
comparé à Nourine et al. Le temps de réponse de
l'algorithme GenAll surpasse celui de l'algorithme de Nourine et al. ABSTRACT. The extremely large number of association rules that can be drawn from --even reasonably sized datasets--, bootstrapped the development of more acute techniques or methods to reduce the size of the reported rule sets. In this context, the battery of results provided by the Formal Concept Analysis (FCA) allowed to define "irreducible" nuclei of association rule subset better known as generic basis. However, a thorough overview of the literature shows that all the algorithms dedicated neglected an essential component: the relation of order, or the extraction of the minimal generators. In this paper, we introduce the GenAll algorithm to build a formal concept lattice, in which each formal concept is "decorated" by its minimal generators. The GenAll algorithm aims to extract generic bases of association rules. The main novelty in this algorithm is the use of refinement process to compute immediate successor lists to simultaneously determine the set of formal concepts, their underlying partial order and the set of minimal generators associated with each formal concept. Carried out experiments showed that the GenAll algorithm is especially efficient for dense extraction contexts compared to that of Nourine et al. Response times obtained from the GenAll algorithm largely outperform those of Nourine et al.
MOTS-CLÉS : Fouille de données, Analyse de Concepts Formels, Treillis de Galois, Règles d'associations génériques, Générateur minimal. KEYWORDS: Data Mining, Formal Concept Analysis, Galois lattice, Generic association rules, Minimal generator. |
A R I M A arima-office@inria.fr