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

précédent sommaire suivant

2.3 Discussion

Il est bien connu que l'etape la plus complexe et la plus consommatrice en temps d'execution est celle de la decouverte des itemsets (fermes) frequents. Comme effet de bord, cette etape peut generer un nombre important d'itemsets frequents et par consequent de regles d'association. Les algorithmes bases sur l'extraction des itemsets fermes frequents sont une nouvelle alternative avec la promesse claire de reduire considerablement la taille de l'ensemble des regles d'association. Durant notre description des principaux algorithmes d'extraction des itemsets fermes frequents, nous les avons distingue par rapport A la strategie d'exploration adoptee. D'autres criteres peuvent être utilises pour classer ces algorithmes tels que [43] :

- Choix des generateurs : certains algorithmes ont choisi les generateurs minimaux comme generateurs de chaque classe d'equivalence (cas de l'algorithme CLOSE) tandis que d'autres optent pour une technique se basant sur le fait qu'a chaque fois qu'un generateur est trouve, sa fermeture est calculee. Ceci permettrait de creer de nouveaux generateurs a partir des itemsets fermes frequents trouves (cas de l'algorithme CLOSET).

- Calcul de la fermeture : le calcul de la fermeture peut être fait selon deux methodes. Dans la premiere methode, chaque fois qu'un sous-ensemble de l'ensemble total des generateurs - caracterise par la même taille des generateurs - est determine, la fermeture

de chaque generateur appartenant a ce sous-ensemble est calculee (cas de l'algorithme CLOSE). Dans l'autre methode, le calcul des fermetures de l'ensemble de tous les generateurs se fait dans une meme etape (cas de l'algorithme A-CLOSE).

Le calcul de la fermeture d'un itemset X differe aussi par le fait qu'il peut etre realise soit par des operations d'intersection sur les transactions auxquelles appartient X (cad son extension), soit d'une maniere incrementale en cherchant les items appartenant a la fermeture d'un itemset X et qui verifient la relation suivante : ø(X) C ø(i) = i E ã(X), avec i un item n'appartenant pas a X [55, 57].

Le probleme de decouverte des regles d'association, considere sous l'optique de decouverte des itemsets fermes, pourrait etre reformule comme suit [9] :

1. Decouvrir deux "systemes de fermeture" distincts, cad ensembles d'ensembles fermes sous l'operateur d'intersection, a savoir l'ensemble des itemsets fermes et l'ensemble des generateurs minimaux. Aussi, la relation d'ordre sous-jacente devrait etre determinee.

2. A partir de toute l'information collectee, cad les deux "systemes de fermeture" et la relation d'ordre sous-jacente, deriver des bases generiques de regles d'association.

A la lumière de cette reformulation et en tenant compte de l'objectif de reduire le nombre de regles d'association, nous considerons les caracteristiques (ou dimensions) suivantes permettant de determiner les buts realises (construction de la relation d'ordre, etc.) et de montrer les differences majeures qui pourraient exister entre les algorithmes passes en revue (strategie adoptee, elements generes, etc.). Ces caracteristiques sont les suivantes

[⁹] :

1. Strategie d'exploration : trois strategies principales sont utilisees afin d'explorer l'espace de recherche : "Generer-et-tester", "Diviser-et-generer" et une strategie hybride qui beneficie des avantages des deux premieres.

2. Espace de recherche : la valeur "exhaustive" de cette dimension indique que toutes les transactions seront prises en compte lors du premier balayage. En revanche, la valeur "echantillon" signifie que seul un echantillon du contexte d'extraction sera considere du moins pour un premier balayage [59].

3. Type du format des donnees : cette dimension peut prendre comme valeur : format de donnees horizontal (etendu), format de donnees vertical, relationnel, texte brut, donnees multimedia.

4. Structure de donnees : differentes structures de donnees peuvent etre utilisees

pour stocker les informations nécessaires a l'exécution d'un algorithme (pour stocker les candidats, le contexte d'extraction, etc.). La structure la plus privilégiée semble etre la structure trie.

5. Calcul des fermetures : nous distinguons principalement deux faZons pour calculer la fermeture d'un générateur (minimal) : soit via des intersections des transactions auxquelles il appartient (cad son extension), soit d'une maniere incrémentale, cad via des recherches des items susceptibles d'appartenir a la fermeture en question.

6. Elements generes en sortie : cette caractéristique indique les éléments générés en sortie.

7. Ordre partiel : cette caractéristique indique si la relation d'ordre sous-jacente des itemsets fermés fréquents a été déterminée ou non.

Le tableau 2.1 résume les principales caractéristiques des algorithmes de génération d'itemsets fermés fréquents par rapport aux dimensions présentées ci-dessus.

Une premiere constatation qui se dégage de ce tableau est qu'aucun algorithme n'est arrivé a tenir la promesse avancée par cette nouvelle alternative d'algorithmes en matiere de réduction de la redondance des regles d'association. L'origine de cet échec réside dans le fait qu'aucun de ces algorithmes n'a pu supporter le coUt élevé de la construction de la relation d'ordre (cf. derniere ligne du tableau 2.1). Cette derniere est une condition sine qua non pour l'obtention de la base générique des regles d'association approximatives [9].

Une deuxieme constatation concerne la notion de générateur minimal. En effet, malgré l'importance de cette derniere dans les bases génériques étant donné qu'elle permet d'avoir des prémisses minimales, seuls les algorithmes adoptant la stratégie "Générer-et-tester" permettent l'extraction des générateurs minimaux (cf. avant derniere ligne du tableau 2.1). Pour ces algorithmes, l'obtention des regles génériques exactes peut se faire d'une maniere directe étant donné qu'ils extraient les générateurs minimaux fréquents. Pour pouvoir extraire les regles génériques approximatives, ils nécessitent l'exécution en aval d'un algorithme permettant de construire la relation d'ordre partiel, tel que celui proposé par Valtchev et al. [64]. Les algorithmes adoptant les deux autres stratégies se sont focalisés sur l'énumération des itemsets fermés fréquents. Pour obtenir les bases génériques de regles, ces algorithmes nécessitent alors l'application de deux autres algorithmes. Le premier permettra de construire l'ordre partiel et le second aura pour objectif de retrouver les générateurs minimaux fréquents tel que JEN [23]. Ce dernier permet de retrouver les générateurs minimaux a condition que l'ordre partiel soit déjà construit.

TAB . 2.1: Caractéristiques des algorithmes CLOSE, A-CLOSE, TITANIC, CLOSET et CHARM

Une troisième constatation concerne le colit induit par le calcul de la fermeture. En effet, bien que ces algorithmes constituent une alternative intéressante, dans le cas de contextes d'extraction denses, leurs performances sont faibles dans le cas des contextes épars. En effet, dans ce type de contexte, l'espace de recherche des itemsets fermés fréquents tend a se confondre avec celui des itemsets fréquents.

En comparant les algorithmes décrits dans ce chapitre, nous pouvons noter aussi les remarques suivantes :

Parmi les cinq algorithmes, seul TITANIC considère la classe d'équivalence dont l'en-
semble vide est le générateur minimal. Ainsi, il est le seul algorithme dont les éléments
générés permettent de construire un treillis d'Iceberg en utilisant par exemple l'algo-

rithme proposé par Valtchev et al. [64].

CLOSE, A-CLOSE et TITANIC ont pour désavantage de calculer la même fermeture plusieurs fois dans le cas oft elle admet plusieurs générateurs minimaux. Cette lacune est évitée par CLOSET et CHARM grace aux tests de couverture. Cependant, afin d'accélérer ces tests, CLOSET et CHARM sont obligés de maintenir en mémoire centrale, l'ensemble des itemsets fermés fréquents trouvés. Le travail présenté dans [43] essaie d'extraire les itemsets fermés fréquents sans duplication et sans les maintenir en mémoire centrale. Pour cela, les auteurs introduisent une stratégie permettant la détection des duplications dans le calcul des fermetures.

Les stratégies d'élagage adoptées par TITANIC sont une amélioration de celle de A-CLOSE. En effet, en utilisant le support estimé d'un candidat, TITANIC évite le coUt des balayages effectués par A-CLOSE pour comparer le support d'un candidat générateur minimal de taille k aux supports de ses sous-ensembles de taille (k-1). Les stratégies d'élagage adoptées par CLOSET et celles utilisées dans CHARM peuvent aussi être considérées comme les mêmes.