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

précédent sommaire suivant

3.4 Preuves theoriques

Dans cette section, nous allons montrer la validite de l'algorithme PRINCE. Ensuite, nous allons prouver la terminaison et la completude de l'algorithme PRINCE.

Proposition 5 L'algorithme PRINCE est valide. En effet, il permet de déterminer tous les itemsets fermés fréquents, leurs générateurs minimaux associés ainsi que toutes les règles généri ques informatives valides.

Preuve.

Nous allons montrer la validité de PRINCE en montrant la validité de chacune des étapes le constituant.

1. Première étape : Détermination des générateurs minimaux

PRINCE détermine tous les générateurs minimaux fréquents et la bordure négative des générateurs minimaux. En effet, PRINCE parcourt l'espace de recherche par niveau (et donc par taille croissante des candidats générateurs minimaux). Tout au long de ce parcours, PRINCE élimine un candidat g de taille k ayant un de ses sous-ensemble de taille (k-1), disons g₁, vérifiant une des deux conditions suivantes :

(a) g1 n'est pas un générateur minimal fréquent alors, d'après la propriété d'idéal d'ordre des générateurs minimaux fréquents (cf. Proposition 1 page 24), g ne pourra pas être un générateur minimal fréquent.

(b) g1 a un support égal a celui de g. Ce dernier ne pourra pas être un générateur minimal car il existe un sous-ensemble de g (en l'occurrence g₁) ayant la même fermeture que g (cf. Lemme 1 page 46).

Si aucune de ces deux conditions n'est vérifiée, g est un générateur minimal. S'il est fréquent, il sera introduit lors de la deuxième étape dans le treillis des générateurs minimaux. Si g est infréquent, g appartient a la bordure négative des générateurs minimaux. En effet, tous les sous-ensembles de g sont des générateurs minimaux fréquents et g sera alors utilisé dans le mécanisme de comptage par inférence utilisé lors de la deuxième étape.

2. Deuxième étape : Construction du treillis des générateurs minimaux

Le résultat de cette étape est le treillis des générateurs minimaux. Cette étape per-met, d'une part, de déterminer la classe d'équivalence adéquate relative a chaque générateur minimal fréquent. D'autre part, elle permet de trouver tous les successeurs immédiats d'une classe d'équivalence. Montrons que cette étape est valide. Chaque générateur minimal g est introduit dans le treillis des générateurs minimaux via sa comparaison avec les listes des successeurs immédiats des classes d'équivalence aux quelles appartiennent ses sous-ensembles de taille (k-1). En effet, au moment de l'introduction de g, les classes d'équivalence de ses sous-ensembles de taille (k-1) ont déjà été introduites dans le treillis des générateurs minimaux. Ceci est dii au fait que le support des générateurs minimaux fréquents composant chacune de ces classes d'équivalence est strictement supérieur a celui de g. Ainsi, la fonction REPRESENTANT permet de retrouver, pour chacun de ses sous-ensembles, disons g₁, le

representant de Cg₁ et donc le generateur minimal frequent oft est stockee la liste L des successeurs immediats de Cg₁ ⁰⁾. Lors des comparaisons de g avec L, deux cas sont a distinguer (cf. Proposition 3 page 47) :

(a) Si g est compare avec le representant R de C_g, les comparaisons avec les elements de L s'arretent. Ensuite, la fonction GESTION-CLASSE-EQUIV est executee. Elle remplace toutes les occurrences de g par R, dans les listes des successeurs immediats oft g a ete ajoute. Ceci permet de n'avoir que des representants dans les listes des successeurs immediats et n'affecte en rien le resultat de la deuxieme etape, etant donne que g et R appartiennent a la meme classe d'equivalence. Pour la meme raison - n'avoir que des representants dans les listes des successeurs immediats - les comparaisons a faire avec g seront effectuees avec R.

(b) Si g est un successeur d'un des elements de L, disons g₂, g sera compare aux elements de la liste des successeurs de C_g2. Pour chaque element g₃ appartenant au reste des elements de L, g ne pourra etre qu'un successeur de C_g3. En effet, le cas (a) ne peut avoir lieu car sinon g ne serait pas un successeur de g₂.

Si aucun de ces deux cas ne se presente, g est un successeur immédiat de g₁ et est ajoute a L et ne sera plus enleve⁽⁶⁾. Cet ajout est valide etant donne que si un generateur minimal frequent, disons h, est compare dans la suite a g, alors h ne peut que verifier qu'un des deux cas (a) ou (b) si Ch et C_g sont comparables (cad h ? C_g ou Ch est un successeur de C_g). En effet, h a un support inferieur ou egal = celui de g.

Ainsi, chaque liste des successeurs immediats est comparee a tous les generateurs minimaux frequents susceptibles d'y appartenir. Les traitements s'arrêtent lorsqu'il n'y a plus de generateurs minimaux frequents a introduire dans le treillis des générateurs minimaux.

3. Troisième étape : Extraction des bases générigues informatives de règles

Dans cette etape, le parcours du treillis des générateurs minimaux se fait en partant de Co. Montrons que cette etape est valide. Toute classe d'equivalence autre que Co admet au moins un predecesseur immediat et sera donc incluse dans au moins une liste des successeurs immediats d'une autre classe d'equivalence. Ceci permettra de

⁵Comme mentionné précédemment, les générateurs minimaux fréquents autres que les représentants

ont des listes de successeurs immédiats vides.

⁶Eventuellement, g ne pourra qu'être remplacé par le représentant de Cg.

l'inclure dans la liste des classes d'équivalence a traiter lors de la prochaine itération (cad dans la liste L₂ de l'algorithme 4 page 53). Les traitements s'arrêtent lorsque la (resp. les) liste(s) des successeurs immédiats de la (resp. des) classe(s) d'équivalence traitée(s) en dernier est (resp. sont) vide(s). Ainsi, toutes les classes d'équivalence seront traitées. En appliquant la proposition 4 (cf. page 51), tous les itemsets fermés fréquents sont retrouvés au fur et a mesure de ce parcours ascendant et les regles génériques informatives valides sont alors extraites d'une maniere directe.

Proposition 6 L'algorithme PRINCE termine et son résultat est complet.

Preuve.

Montrons que l'algorithme PRINCE termine quel que soit le contexte d'extraction 1C donné en entrée et quelles que soient les valeurs de minsup et minconf. Etant donné que le nombre de couples du contexte d'extraction est fini, le nombre de générateurs minimaux fréquents extraits du contexte 1C lors de la premiere étape, et qui est donc a traiter lors de la deuxieme étape, est aussi fini. De même, le treillis des générateurs minimaux a parcourir lors de la troisieme étape a une taille finie, égale au nombre de classes d'équivalence.

Le résultat de l'algorithme PRINCE est complet étant donné que la construction du treillis des générateurs minimaux assure l'exhaustivité des éléments (les générateurs minimaux fréquents) de chaque classe d'équivalence. De même, elle assure l'exhaustivité des éléments de la liste des successeurs immédiats de chaque classe d'équivalence. Les traitements effectués lors de la troisieme étape prennent ainsi en compte toutes les classes d'équivalence et le résultat est donc complet.

3.5 Complexite

Dans cette section, nous allons étudier la complexité théorique au pire des cas de l'algorithme PRINCE.

Soit un contexte d'extraction 1C = (O, Z, 7Z), le pire des cas est obtenu quand le nombre de générateurs minimaux fréquents est égal au nombre d'itemsets fréquents et est égal au nombre d'itemsets fermés fréquents (cad 2¹¹¹) . En d'autres termes, chaque générateur

minimal frequent est aussi un ferme et le treillis des generateurs minimaux se confond avec le treillis des itemsets frequents.

Soient m=1O1 et n=1I1. La taille maximale d'une transaction est egale au nombre maximum d'items distincts, cad n. Nous allons considerer que toutes les transactions ont pour longueur n. Pour chaque transaction et dans le pire des cas, nous determinons ses 2ⁿ sous-ensembles afin de calculer les supports des itemsets. Nous allons calculer la complexite theorique au pire des cas de l'algorithme PRINCE en calculant la complexite au pire des cas de chacune des trois etapes le constituant.

Premiere etape : Determination des generateurs minimaux

1. L'initialisation de l'ensemble des items candidats se fait en O(1) (ligne 3 dans Algorithme 1 page 43).

2. Le cofit du calcul des supports des items est de l'ordre de O(m × n) (ligne 4).

3. Les affectations des lignes 5-6 se font en O(1).

4. Le cofit de l'elagage par rapport aux supports des items est de l'ordre de O(n) (lignes 7-15).

5. Le cofit de la determination des generateurs minimaux frequents de tailles superieures ou egales a 2 (lignes 16-17) est egal a la somme des cofits suivants :

(a) APRIORI-GEN : il y a (2ⁿ - n - 1) candidats a generer. Ainsi, le cofit de cette phase est de l'ordre de O(2ⁿ - n) (lignes 3-4 dans Algorithme 2 page 44) ;

(b) Le cofit de la verification de l'ideal d'ordre, et en meme temps, le calcul du support estime et le stockage des liens vers les sous-ensembles adequats est de l'ordre de O(n² × (2ⁿ - n)) (lignes 5-14) ;

(c) Le cofit du calcul des supports des candidats de tailles superieures ou egales a 2 est de l'ordre de O(m × (2ⁿ - n)) (ligne 16) ;

(d) Le cofit de l'elagage par rapport aux supports des candidats est de l'ordre de O(2ⁿ - n) (lignes 17-22).

La complexite C_l de cette etape est alors : C_l = O(m × n + n + (2ⁿ - n) + n² × (2ⁿ - n) + m × (2ⁿ - n) + 2ⁿ - n) = O(m × 2ⁿ + 2ⁿ + (n² + 1) × (2n - n)).

Etant donne que 2ⁿ est largement superieur a n, alors C_l = O(m×2ⁿ+2ⁿ+(n²+1)×2ⁿ) : O(m × 2ⁿ + (n2 + 2) × 2n) = O(m × 2n + n2 × 2n) :O((n² + m) × 2n).

D'ofi, C, = O((n² + m) × 2n).

G Deuxieme etape : Construction du treillis des generateurs minimaux

1. La boucle pour de la ligne 3 (dans Algorithme 3 page 50) se repetent 2ⁿ fois etant donne que dans le pire des cas, nous avons 2ⁿ generateurs minimaux frequents.

2. Pour chaque generateur minimal frequent g de taille k, la boucle pour de la ligne 4 se repete k fois etant donne que g admet k sous-ensembles de taille (k-1) (k, le nombre de sous-ensembles, sera largement majore par n). Pour chaque sous-ensemble de g de taille (k-1), disons g₁, les traitements suivants sont realises :

(a) Le coUt de l'instruction de la ligne 5 est en O(1) etant donne que dans le pire des cas, g₁ est le seul generateur minimal frequent de sa classe d'equivalence et est donc son representant (g₁ est egal a R).

(b) La boucle pour de la ligne 6 se repete au maximum (n-k) fois. En effet, g₁, etant de taille egale a (k-1), possede au maximum n - (k - 1) - 1 successeurs immediats, au moment de l'integration de g dans le treillis des generateurs minimaux ((n-k), le nombre maximal de successeurs immediats, sera largement majore par n). Dans chaque iteration de cette boucle, g est compare a un element de g₁.succs-immediats , disons g₂. Le coUt de la comparaison de g avec g₂ est la somme des deux coUts suivants :

i. Le premier coUt est relatif a l'union de g et g₂ et est, au pire des cas, de l'ordre de O(n). Soit q, l'itemset resultat de cette union.

ii. Le second coUt est relatif a la recherche du support adequat de q et est, au pire des cas, de l'ordre de O(n). Notons que l'itemset q est un generateur minimal frequent. En effet, q est inclus dans l'itemset contenant tous les items, cad l'itemset I. Or, ce dernier -- dans le pire des cas -- est un generateur minimal frequent et d'apres la propriete de l'ideal d'ordre des generateurs minimaux frequents (cf. Proposition 1 page 24), q est un generateur minimal frequent.

Etant donne que l'union de g avec tout element de g₁.succs-immediats donne toujours un generateur minimal, aucune des deux conditions specifiees par la proposition 3 (cf. page 47) n'est verifiee (ces conditions sont decrites par les lignes 7-12). Ainsi, C_g est incomparable avec toutes les classes d'equivalence des representants appartenant a g₁.succs-immediats . g est donc ajoute a cette liste en O(1) (lignes 13-14).

Ainsi, la complexite C₂ de cette etape est de l'ordre de : C₂ = O(2ⁿ × n × (1 + (n ×

(n + n)) + 1)) = O(2ⁿ × n × (n × (n + n))).

D'oft, C₂ = O(n³ × 2ⁿ).

Troisieme etape : Extraction des bases generigues informatives de regles

1. Le cofit des initialisations des lignes 3-6 (dans Algorithme 4 page 53) se fait en

O(1).

2. La condition de la boucle tant que est verifiee tant qu'il y a des classes d'equivalence a traiter (ligne 7). Dans le pire des cas, chaque generateur minimal frequent ferme forme une classe d'equivalence. Ainsi, 2ⁿ classes d'equivalence sont traitees. Pour chaque classe d'equivalence C (ligne 8), le coilt total de cette etape est egal a la somme des deux cofits suivants :

(a) Le premier cofit consiste a deriver la fermeture correspondante a C. Cette derniere est le resultat de l'union du generateur minimal frequent de C avec la fermeture d'un de ses predecesseurs immediats (lignes 12-14). Ceci est realise, au pire des cas, en O(n).

(b) Le deuxieme cofit est relatif a l'extraction des regles d'association informatives.

i. Etant donne que, le generateur minimal frequent de C est egal A sa fermeture, la condition de la ligne 9, testee en O(1), n'est pas verifiee. Ainsi, aucune regle exacte informative n'est extraite (ligne 10).

ii. Soit k la taille de l'itemset ferme frequent de C. C possede alors k predecesseurs immediats. Ainsi, pour une valeur de minconf egale a 0, k regles approximatives informatives valides sont extraites (lignes 15-16). Le cont de l'extraction de chacune des regles approximatives est egal au cont du calcul de la difference entre la premisse et la conclusion et est, au pire des cas, de l'ordre de O(n).

Le cont total, pour chaque classe d'equivalence, est alors de l'ordre de O(n+
1 + n × n) (la taille k d'un itemset ferme frequent etant largement majoree

par n).

La complexite C₃ de cette etape est alors de l'ordre de : C₃ = O(1 + (n+ 1 +n²)×2ⁿ).

D'oft, C₃ = O(n² × 2n).

Au pire des cas, la complexite totale de l'algorithme PRINCE est de l'ordre de :

Cpire = C₁ -h C2 -h C₃ = O((n² + m) × 2ⁿ) -h O(n³ × 2ⁿ) -h O(n² × 2ⁿ) = O((n³ + 2 × n² + m)2ⁿ) = O((n³ + m) × 2ⁿ).

D'oft, Cpire = O((n³ + m) × 2ⁿ).

Ainsi, la complexite de PRINCE est de même ordre de grandeur que celle des algorithmes dedies a l'extraction des itemsets fermes frequents [29, 47], bien qu'il determine les trois composantes necessaires a l'extraction des bases generiques de regles d'association.

3.6 Conclusion

Dans ce chapitre, nous avons introduit un nouvel algorithme, appele PRINCE, pour l'extraction des bases generiques de regles. L'algorithme PRINCE determine les generateurs minimaux frequents. Ensuite, il les ordonne partiellement sous la forme d'un treillis des generateurs minimaux. Un balayage de bas en haut de cette structure permet de retrouver les itemsets fermes frequents et d'extraire les regles d'association informatives. Des preuves theoriques ainsi qu'une etude de la complexite theorique relatives au nouvel algorithme ont ete proposees.

Dans le chapitre suivant, nous allons essayer d'evaluer experimentalement notre algorithme sur la base d'une serie de tests. Ces tests permettront de voir l'influence de quelques optimisations que nous introduisons, d'analyser les caracteristiques de notre algorithme, ainsi que de comparer ses performances aux algorithmes d'exploration par niveau existants.