Chapitre II.
L'extraction de règles d'association
L'extraction des règles d'association est une
méthode descriptive de fouille de données qui a reçu
beaucoup d'intérêt de la part des chercheurs. On peut la
définir comme étant la recherche de relations entre des Items
dans un ensemble de données.
Cette technique est très utilisée pour
l'analyse des paniers. Il s'agit d'analyser l'ensemble des achats
effectués par les clients d'une entreprise commerciale. Chaque achat
contient un ensemble d'Items (articles), il correspond à un panier. Pour
cela, l'entreprise doit archiver les achats (transactions) effectués
dans une base de données binaire (Transaction, Items) où
l'attribut Transaction est une clé et Items est l'ensemble de n articles
article1, article2, ....articlen .
Plusieurs algorithmes d'extraction de règles
d'association à partir de bases de données ont été
proposés [Agrawal et al., 1993], [Agrawal et Srikant., 1994], [Savasere
et al., 1995], [Hip et al., 2000].
Motivations
L'ECD est un domaine relativement récent.
Plusieurs recherches intéressantes ont été faites et ont
produit des résultats satisfaisants. Il s'agit de techniques et de
méthodes nouvelles qui concernent chacune des phases du processus d'ECD,
en particulier la fouille de données. Il existe alors plusieurs travaux
développés pour l'extraction de motifs et particulièrement
les règles d'association. Dans la section qui suit, nous
présentons l'extraction de ce type de motifs et nous expliquons nos
choix, mais bien avant et pour la clarté nous donnons quelques
définitions.
Les Itemsets et les règles d'association.
Ils sont le produit du processus d'extraction des
règles d'association et ils tirent leurs origines des Items.
Définition 1 : Item
Un Item est un article au sens où il est pris en
extraction de règles d'association.
Définition 2 :
Itemset
Un Itemset est un ensemble de n Items noté :
{A, B, C, D....}. L'ensemble de tous les Itemsets possiblement formés
par les éléments d'Items est 2n.
Chapitre II : L'extraction de règles d'association -
34 -
Définition 3 : le support
Le support d'un Itemset k dans une base de
données, est l'ensemble de toutes les transactions qui supportent k, il
est noté supp(k).
Définition 4 : la confiance
La confiance dans une règle, notée
conf(X?Y) est la probabilité qu'une transaction supportant X supporte
également Y.
Exemple :
Etant donné une base de données, chaque
instance est un ensemble d'Items:
Transaction
|
Item
|
1
|
A C T W
|
2
|
C D W
|
3
|
A C T W
|
4
|
A C D W
|
5
|
A C D T W
|
6 C D T
|
|
Support
|
Items Set
|
100 % (6)
|
C
|
85
|
%
|
(5)
|
CW
|
67
|
%
|
(4)
|
A, D, T, AC, AW,CD, CT, ACW
|
50
|
%
|
(3)
|
AT, DW, TW, ACT, ATW, DW, CTW, ACTW,CDW
|
|
Item sets Frequent Maximum: ACTW, CDW
· Sous-Itemsets : CDW (3), CD (4), CW (5), DW (3),
C (6), D(4), W (5)
· CD W, conf = 3/4
|
=
|
75%
|
· CW D, conf = 3/5
|
=
|
60%
|
· DW = C, conf = 3/3
|
=
|
100%
|
· C DW, conf = 3/6
|
=
|
50%
|
· D = CW, conf = 3/4
|
=
|
75%
|
· W = CD, conf = 3/5
|
|
=
|
60%
|
|
II.1 Les règles d'association
Une règle d'association est une relation
d'implication X - Y entre deux ensembles d'Items X et Y tel
que XnY =Ø et X?Ø. X est appelé corps de la règle
et Y est la tête. Cette règle indique que les transactions qui
contiennent les articles de l'ensemble X ont tendance à contenir les
articles de l'ensemble Y. X est appelé condition ou prémisse et Y
est appelé résultat ou conclusion. Ces règles sont de la
forme :
Si {Item 1, Item 2, ..., Item j } Alors { Item
k,....,Item p }
Exemple : Si {gene1 = "1"} Alors {gene5="1"}
Cette règle est interprétée de la
manière suivante :
"Si la séquence possède gene1 Alors elle
possède gene5"
Chapitre II : L'extraction de règles d'association -
35 -
Les règles d'association induisent deux notions
:
- le support qui est le pourcentage (%) d'instances de la
base vérifiant la règle ou fréquence d'apparition ensemble
de la partie gauche et la partie droite de la règle. Support(X
-* Y) = p(XuY) = support ({X,Y})
- la confiance qui est la probabilité que la
partie droite de la règle soit vérifiée, si partie gauche
de la règle est vérifiée.
Confiance(X -* Y) = p(Y|X) = p(XuY) /
p(X) = support({X,Y}) / support({X})
| 
