Extraction des bases génériques informatives de règles sans calcul de fermetures

précédent sommaire suivant

Chapitre 2

Algorithmes d'extraction des itemsets

fermes frequents : Etat de l'art

2.1 Introduction

L'extraction des regles d'association est l'une des techniques les plus importantes dans le domaine de la fouille de données [11]. La premiere approche d'extraction des regles d'association s'est basée sur la découverte des itemsets fréquents [2]. Cependant, cette approche souffre de deux problemes majeurs, a savoir le coit de l'extraction des itemsets fréquents a partir desquels seront extraites de grandes quantités de regles d'association. Cette quantité énorme de connaissance rend quasi impossible leur analyse par un expert humain. Pour pallier ces inconvénients, une nouvelle approche basée sur l'extraction des itemsets fermés fréquents [48] est apparue. Cette approche exploitant les fondements mathématiques de l'analyse formelle de concepts [66], propose de réduire le coit de l'extraction des itemsets fréquents en se basant sur le fait que l'ensemble des itemsets fermés fréquents est un ensemble générateur de l'ensemble des itemsets fréquents [48]. En outre, elle propose une sélection, sans perte d'information, d'un sous-ensemble de toutes les regles d'association, appelé base générigue, a partir duquel le reste des regles pourrait etre dérivé [48]. Cette approche permet de réduire le nombre de regles extraites en ne gardant que les plus intéressantes pour l'utilisateur et lui donne la possibilité de mieux les visualiser et les exploiter.

2.2 Algorithmes d'extraction des itemsets fermes frequents

La premiere approche d'extraction des regles d'association s'est basee sur l'extraction des itemsets frequents. Les algorithmes, adoptant cette approche, peuvent etre classes suivant les strategies d'exploration utilisees pour traverser le treillis des itemsets : en largeur d'abord [2], en profondeur d'abord [34] ou une strategie hybride [70]. En adoptant une strategie en largeur d'abord, tous les k-itemsets candidats sont generes en faisant une auto-jointure de l'ensemble des (k-1)-itemsets frequents [2]. Quand une strategie en profondeur d'abord est adoptee, etant donne un (k-1)-itemset frequent X, les k-itemsets candidats sont generes en ajoutant un item i, i/?X, a X. Si {X U i} est aussi frequent, le processus est repete recursivement pour {X U i} [34]. La troisieme strategie explore en profondeur d'abord le treillis des itemsets, mais ne genere qu'un seul itemset a la fois [70].

Afin de resoudre les problemes rencontres par les algorithmes d'extraction des itemsets frequents, une nouvelle approche basee sur l'extraction des itemsets fermes frequents est apparue. Cette approche est basee sur la fermeture de la connexion de Galois [27] pour resoudre le probleme d'extraction de regles d'association [48]. Elle est fondee sur un elagage du treillis des itemsets fermes, en utilisant les operateurs de fermeture de la connexion de Galois [27]. Plusieurs algorithmes ont ete proposes dans la litterature [49, 50, 51, 57, 69], dont le but est de decouvrir les itemsets fermes frequents.

Quand nous nous interessons a l'extraction des itemsets fermes frequents seulement, la generation des candidats et la verification s'ils sont fermes ou non, ne peuvent pas etre directement appliquees contrairement aux algorithmes permettant de determiner les itemsets frequents [43]. En effet, il n'est pas possible de generer des itemsets fermes candidats en faisant une auto-jointure des itemsets fermes dejà decouverts. Par exemple, etant donne un itemset ferme X, il peut arriver qu'aucun des sur-ensembles de X, obtenus en etendant X par un seul item, ne soit un ferme [43].

Etant donne le fait que les candidats fermes frequents ne peuvent pas etre generes directement, tous les algorithmes, permettant de trouver les itemsets fermes frequent, sont bases sur deux etapes qui co-existent. La premiere etape consiste a naviguer dans l'espace de recherche en traversant le treillis des itemsets frequents d'une classe d'equivalence a une autre. Durant la deuxieme etape, ces algorithmes calculent les fermetures des itemsets

frequents visites, dans le but de determiner les itemsets fermes frequents de la classe d'equivalence correspondante [43].

Ainsi, nous proposons que les strategies adoptees pour l'exploration de l'espace de recherche soient decomposees en trois strategies, a savoir "Generer-et-tester", "Diyiser-etgenerer" et une strategie hybride :

1. La strategie "Generer-et-tester" : les algorithmes adoptant cette strategie parcourent l'espace de recherche par niveau. A chaque niveau k, un ensemble de candidats de taille k est genere. Cet ensemble de candidats est, generalement, elague par la conjonction d'une metrique statistique (cad le support) et des heuristiques basees essentiellement sur les proprietes structurelles des itemsets fermes et/ou des generateurs minimaux [9].

2. La strategie "Diviser-et-generer" : les algorithmes adoptant cette strategie essaient de diviser le contexte d'extraction en des sous-contextes et d'appliquer le processus de decouverte des itemsets fermes recursivement sur ces sous-contextes. Ce processus de decouverte repose sur un elagage du contexte base essentiellement sur l'utilisation d'une metrique statistique et d'heuristiques introduites [9].

3. La strategie hybride : les algorithmes adoptant cette strategie utilisent les proprietes des deux strategies precedentes. Ils explorent l'espace de recherche en profondeur d'abord (tel que les algorithmes de la strategie "Diyiser-et-generer") mais sans diviser le contexte d'extraction en des sous-contextes. Ces algorithmes genèrent un ensemble de candidats tel que c'est le cas dans la strategie "Generer-et-tester". Cependant, cet ensemble est toujours reduit a un seul element. Ces algorithmes essaient alors de verifier si ce candidat est un itemset ferme frequent ou non. Le processus d'extraction se base aussi sur des strategies d'elagage [69]. Ces derniers consistent a utiliser une metrique statistique en conjonction avec d'autres heuristiques.

Dans la suite, nous allons passer en revue les principaux algorithmes permettant l'extraction des itemsets fermes frequents en les distinguant par rapport a la strategie d'exploration etant donne que c'est le critère utilise dans la litterature [9, 36].

2.2.1 Les algorithmes de type !^,Générer-et-tester!^,

Dans cette sous section, nous allons passer en revue les algorithmes les plus connus operant selon la strategie "Generer-et-tester". Une structure generale d'un algorithme entrant dans cette categorie est presentee dans [9].

Chacun des algorithmes, que nous allons presenter dans la suite, est caracterise par une phase d'elagage et par une phase de construction. Lors de la phase d'elagage et en plus de l'elagage des candidats infrequents, cad ayant un support strictement inferieur a minsup, chaque algorithme introduit de nouvelles strategies d'elagage pour essayer de reduire le coUt supplementaire du calcul des fermetures des itemsets [9]. Notons que ces strategies dependent de l'information dont dispose l'algorithme. Cette information peut être soit l'ensemble des generateurs minimaux seuls, soit accompagne de l'ensemble des itemsets fermes [9]. La phase de construction relative a une iteration k, permet de generer les candidats de taille k a partir de ceux retenus lors de l'iteration (k-1) (cad de taille (k-1)).

Une methode d'elagage commune aux algorithmes adoptant la strategie "Generer-ettester" se base sur la verification de l'ideal d'ordre des generateurs minimaux frequents. Cette notion est definie comme suit :

Proposition 1 [55, 571 L'ensemble GMFK des generateurs minimaux frequents extraits d'un contexte d'extraction K verifie la propriete de l'ordre ideal de (P(I),? ), cad si g ? GMFK et g₁ ? g alors g₁ ? GMFK, pour tout g, g₁ ? I.

La definition d'un ordre ideal des generateurs minimaux frequents est equivalente a : g₁ ?/ GMFK, g₁ ? g g ?/ GMFK, pour tout g, g₁ ? I.

Definition 5 [55, 571 Soit GMFK un ordre ideal de (P(I),? ). Un itemset candidat g pour GMFK est un sous-ensemble de I tel que tous ses sous-ensembles sont des generateurs minimaux frequents.

Ainsi, tout candidat generateur minimal frequent g de taille k, est elague dans le cas oft un de ses sous-ensembles n'est pas un generateur minimal frequent.

2.2.1.1 L'algorithme CLOSE

L'algorithme CLOSE propose par Pasquier et al. [48, 49] est le premier algorithme permettant l'extraction des itemsets fermes frequents. Cet algorithme se base sur les generateurs minimaux pour calculer les itemsets fermes. Ces generateurs minimaux sont utilises pour construire un ensemble d'itemsets fermes candidats (itemsets fermes potentiellement frequents), qui sont les fermetures des generateurs minimaux. Ainsi, etant donne un contexte d'extraction K, CLOSE genere toutes les regles d'association en trois etapes successives [9] :

1. Decouverte des itemsets fermes frequents ;

2. Derivation de tous les itemsets frequents a partir des itemsets fermes frequents obtenus durant la premiere etape ;

3. Pour chaque itemset frequent, generation de toutes les regles ayant une confiance au moins egale a minconf.

L'algorithme CLOSE parcourt l'ensemble des generateurs minimaux des itemsets fermes frequents par niveaux. L'ensemble d'itemsets fermes frequents candidats d'une iteration k est l'ensemble des fermetures des k-generateurs minimaux frequents de cette iteration. Durant la premiere iteration, l'ensemble des 1-generateurs minimaux est initialise avec la liste des 1-itemsets du contexte d'extraction, tries par ordre lexicographique. CLOSE calcule alors le support et la fermeture de ces generateurs moyennant un acces au contexte d'extraction. Les generateurs minimaux infrequents et leurs fermetures sont alors elimines. Ensuite, pour chaque iteration k, CLOSE construit un ensemble de candidats generateurs minimaux frequents de taille k en utilisant la phase combinatoire d'APRiORi-GEN [2] appliquee aux (k-1)-generateurs minimaux frequents retenus lors de l'iteration precedente. De cet ensemble est elague tout candidat ne verifiant pas l'ideal d'ordre des generateurs minimaux frequents ou s'il est inclus dans la fermeture d'un de ses sous-ensembles de taille (k-1), calculee lors de l'iteration precedente [48, 49]. Une fois ces tests d'elagage effectues, CLOSE accede au contexte d'extraction pour calculer le support et la fermeture des candidats retenus. Pour calculer la fermeture des candidats, CLOSE utilise la fonction GEN-CLOSURE [48, 49]. Cette fonction determine, pour chaque transaction T du contexte d'extraction, les generateurs minimaux qui sont inclus dans T. Pour chacun de ces generateurs minimaux, GEN-CLOSURE calcule sa fermeture et incremente son support. La fermeture est egale a l'intersection de T avec l'ancienne valeur de la fermeture, si cette derniere est non nulle sinon la nouvelle valeur est egale a T. Une fois l'acces au contexte d'extraction termine, CLOSE ne retient que les fermetures des generateurs minimaux qui sont frequents. Ainsi, les candidats infrequents, et pour lesquels le calcul de la fermeture est logiquement non necessaire, sont elimines. L'execution de l'algorithme CLOSE prend fin quand il n'y plus de candidats a generer.

Etant donne que dans chaque iteration, le calcul des supports et des fermetures des candidats est l'etape la plus exigeante en temps d'execution, CLOSE utilise une structure de donnees avancee basee sur la notion d'arbre prefixe (ou trie(')) derivee de celle proposee

'Le mot trie est inspire du mot anglais reTRIEval.

par Mueller dans [46]. Dans cette structure, chaque candidat est represente par un chemin de la racine a une feuille du trie. La fermeture de chaque candidat est stockee au niveau de la feuille le representant dans le trie. A la fin de chaque iteration, les generateurs minimaux frequents, leurs supports et leurs fermetures sont stockes dans un autre trie ayant la meme structure que celui utilise pour le calcul des supports et des fermetures. Le fait d'utiliser un trie pour chaque ensemble de generateurs minimaux frequents, d'une taille k donnee, necessite une grande quantite d'espace memoire (etant donne qu'il y a beaucoup de redondance).

CLOSE necessite au pire des cas acces au contexte d'extraction (TIT etant la taille

maximale possible d'un generateur minimal).

2.2.1.2 L'algorithme A-CLOSE

L'algorithme A-CLOSE, propose par Pasquier et al. [50], permet l'extraction des itemsets fermes frequents en utilisant les proprietes des supports des generateurs minimaux des itemsets fermes frequents. L'amelioration apportee a l'algorithme A-CLOSE par rapport a l'algorithme CLOSE, reside dans le fait que A-CLOSE, apres avoir construit un ensemble de k-generateurs candidats a partir des (k-1)-generateurs minimaux retenus dans la (k1)i`eme iteration, supprime de cet ensemble tout candidat g dont le support est egal au support d'un de ses sous-ensembles de taille (k-1) [50].

Ainsi, A-CLOSE procede en deux etapes successives :

1. Il determine tous les generateurs minimaux frequents, cad les plus petits elements incomparables des classes d'equivalence induites par l'operateur de fermeture ã.

2. Pour chaque classe d'equivalence, il determine l'element maximal residant au sommet de la hierarchie, cad l'itemset ferme frequent.

Lors de la premiere etape, A-CLOSE parcourt l'espace de recherche en largeur d'abord. A-CLOSE initialise alors l'ensemble des 1-generateurs minimaux par les 1-itemsets du contexte d'extraction, tries par ordre lexicographique. Un acces au contexte d'extraction permet de calculer seulement le support de ces generateurs (les fermetures ne sont pas calculees). Ensuite, a chaque iteration k, A-CLOSE construit un ensemble de k-candidats generateurs minimaux en joignant les generateurs minimaux frequents retenus lors de l'iteration precedente (cad de taille (k-1)) grace a la phase combinatoire d'APRiORi-GEN [2]. De cet ensemble est elague tout candidat ne verifiant pas l'ideal d'ordre des generateurs minimaux frequents. Une fois cet elagage effectue, un acces au contexte d'extraction est

effectué pour calculer le support des candidats retenus. Ensuite, A-CLOSE élimine tout candidat g qui se révèle infréquent ou ayant un support égal a celui d'un de ses sous-ensembles de taille (k-1) [50]. Afin de vérifier cette dernière condition, A-CLOSE effectue un balayage des générateurs minimaux retenus de taille (k-1) permettant de comparer le support de g avec le support de ses sous-ensembles de taille (k-1) [50]. La première étape de l'algorithme A-CLOSE prend fin lorsqu'il n'y a plus de candidats a générer.

Lors de la deuxième étape, A-CLOSE calcule les fermetures de tous les générateurs minimaux fréquents retenus lors de la première étape. A cette fin, A-CLOSE accède au contexte d'extraction et utilise la fonction AC-CLOSURE [50] qui est la même que la fonction GEN-CLOSURE utilisée dans l'algorithme CLOSE amoindrie de la phase du calcul du support [50].

Pour alléger le calcul des fermetures, l'algorithme A-CLOSE mémorise le numéro de la première itération durant laquelle un candidat fréquent non générateur minimal (cad ayant un support égal a celui d'un de ses sous-ensembles) a été identifié. Le numéro de cette itération correspond a la taille t de ce candidat. Il n'est alors pas nécessaire de calculer la fermeture des générateurs minimaux fréquents de tailles inférieures a (t-1), puisqu'ils sont tous des itemsets fermés fréquents [50]. En effet, ils sont eux-mêmes leur propres générateurs uniques [47].

Comme dans le cas de l'algorithme CLOSE, et pour chaque itération, A-CLOSE utilise un trie pour accélérer le calcul du support des candidats et un autre trie pour stocker l'ensemble des générateurs minimaux fréquents retenus. La fermeture de chaque générateur minimal fréquent sera complétée lors de la deuxième étape.

A-CLOSE nécessite au plus (1/1+1) accès au contexte d'extraction (1/1 étant la taille maximale possible d'un candidat générateur minimal). Les 1/1 accès sont nécessaires pour déterminer l'ensemble des générateurs minimaux fréquents, alors que le dernier accès permet éventuellement de calculer les fermetures des générateurs retenus.