4.3.5 Algorithme de génération de
règles d'associations valides
Soit la règle d'association définit par R
= p1 -+ p2 \p1 avec p1 Ç
p2(Notons que E \ F = {x|x E E
et x E6 F}). Le principe de l'algirithme est le suivant
: On s'in-téresse aux règles valides c'est-à-dire dont
support(R) = support(p2) > ós.
Etant donné que p1 Ç p2, par le principe de la
décroissance du support, support(p1) > ós
51
1. On considère les règles de la forme
p1 -? p2 \ p1 où la conclusion est de
longueur 1;
2. On supprime les règles non valides ;
3. On combine les conclusions des règles valides ;
4. Puis on passe à des conclusions de longueur 2, on
supprime les règles non valides et on combine les conclusions des
règles valides ;
5. On passe à des conclusions de longueur 3 et ainsi
de suite
Comme exemple, considérons toujours la base de
donnée de la table 4.1. On fixe le seuils ós
= 26 et óc = 25.
[51]
Motifs fréquents de longueur 1 :
a, b, c, e. A ce niveau il est difficile
d'appliquer l'algorithme parce qu'il n'y a pas de règles d'association
à partir de ces motifs. Il faut un motif de longueur 2 au moins.
Motifs fréquents de longueur 2 :
ab, ac, ae, bc, be, ce. Pour chacun de ces
motifs fréquents m on regarde les règles p1 -?
p2 \ p1 avec p2 = m.
- Pour m = p2 = ab,
deux règles peuvent être engendrées : a -? b
(pour p1 = a) et b -? a (pour
p1 = b). Le support de ces deux règles est le
même :
= 23 = óc
2
6
support(p2) = 2 6, et la
confiance donne : confiance(a -? b) = 3
6
et confiance(b -? a) =
|
2
6
5
6
|
=
|
25 = óc. On obtient donc deux
règles valides :
|
|
a -? b et b -? a.
- Pour m = p2 = ac,
on a deux règles a -? c et c -? a
dont le support est le même et vaut 36. La
confiance de a -? c vaut 33 = 1(règle exacte) et celle
de c -? a vaut 53
- Pour m = p2 = ae dont le
support est 26, on a les règles a -?
e de confiance 23 et e -? a de confiance
25.
- Pour m = p2 = bc dont le
support est 46, on a les règles b -?
c de confiance 45 et c -? b de confiance
45.
- Pour m = p2 = be dont le
support est 56, on a les règles b -?
e de confiance 5 5 = 1 et e -? b de confiance 55 =
1.
- Pour m = p2 = ce dont le
support est 46, on a les règles c -?
e de confiance 45 et e -? c de confiance
45.
Motifs fréquents de longueur 3 :
abc, abe, ace, bce. Pour chacun de ces motifs
fréquents m de longueur 3 on regarde les règles
p1 -? p2 \ p1 avec p2 = m.
- Pour m = p2 = abc dont le
support est 26, on a les règles :
1. A conclusion de longueur 1 : ab -? c (de
confiance 22 = 1), ac -? b (de confiance
23), bc -? a (de confiance 24 = â
)
2. A conclusion de longueur 2 (obtenue par union de
conclusion de longueur 1) : a -? bc (de confiance
23), b -? ac (de confiance
25), c -? ab (de confiance
25)
- Pour m = p2 = abe dont le
support est 26, on a les règles :
1. A conclusion de longueur 1 : ab -? e (de
confiance 22 = 1), ae -? b (de confiance 22 = 1), be
-? a (de confiance 25)
2. A conclusion de longueur 2 (obtenue par union de
conclusion de longueur 1) : a -? be (de confiance
23), b -? ae (de confiance
25), e -? ab (de confiance 2
5)
- Pour m = p2 = ace dont le
support est 26, on a les règles :
52
1. A conclusion de longueur 1 : ac -+ e (de
confiance 23), ae -+ c (de confiance 22 = 1),
ce -+ a (de confiance 24 = 12)
2. A conclusion de longueur 2 (obtenue par union de
conclusion de longueur 1) : a -+ ce (de confiance
23), c -+ ae (de confiance
25), e -+ ab (de confiance
25)
- Pour m = p2 = bce dont le
support est 46 = 23, on a les règles :
1. A conclusion de longueur 1 : bc -+ e (de
confiance 22 = 1), be -+ c (de confiance 45),
ce -+ b (de confiance 22 = 1)
2. A conclusion de longueur 2 (obtenue par union de
conclusion de longueur 1) : b -+ ce (de confiance
45), c -+ ae (de confiance
45), e -+ ab (de confiance
45)
Motifs fréquents de longueur 4 :
abce
Pour chacun de ces motifs fréquents m de
longueur 4 on regarde les règles p1 -+ p2 \
p1 avec p2 = m. Son support vaut
26. On a les règles suivantes :
1. A conclusion de longueur 1 : abc -+ e (de confiance
22 = 1), abe -+ c (de confiance 22 = 1), ace -+ b (de
confiance 22 = 1), bce -+ a (de confiance
=
1)
2 .
2
4
2. A conclusion de longueur 2 (obtenue par union de
conclusion de longueur 1) : ce -+ ab (de confiance 24 =
12), be -+ ac (de confiance
25), bc -+ ae (de confiance 24 =
12), ae -+ bc (de confiance 22 = 1,), ac -+
be (de confiance 23), ab -+ ce (de
confiance 22 = 1).
3. A conclusion de longueur 3 (obtenue par union de
conclusion de longueur 2) : e -+ abc (de confiance
25), c -+ abe (de confiance
25), b -+ ace (de confiance
25), a -+ bce (de confiance
23).
Remarque 2
Pour un motif donné, si on a une règle R
= p1 -+ p2 \ p1 valide et
p'1 tel que p1 g p'1 g
p2 (support(p1) >
support(p'1)) alors R' =
p'1 -+ p2 \ p'1. Ainsi
support(R) =
support(R') =
support(p2)
Et
|
support(p2)
confiance(R) = <
support(p)1
|
support(p2)
support(p'1)
|
= confiance(R')
|
Donc si R est valide, R' l'est aussi. Par
exemple, la règle e -+ abc est valide. On peut en
déduire que les règles suivantes sont également valides
[51] :
ea -+ bc, eb -+ ac, ec -+ ab, abe
-+ c, ebc -+ a, ace -+ b.
53
| 
