4.3.2 Algorithme d'extraction des motifs
fréquents
L'algorithme d'extraction des motifs fréquents,
baptisé A-priori, est un algorithme d'exploration de
données concu en 1994 par Rakesh Agrawal et Ramakrish-nan
Sikrant. Il sert à parcourir l'ensemble 2|P| de
tous les motifs(ou items), à calculer leurs supports et à ne
garder que les plus fréquents.
L1 = {a, b, c, e}
47
L'approche que nous allons décrire effectue une
extraction par niveau selon le principe suivant : Tout d'abord, on commence
par déterminer les motifs fréquents de taille 1; on note cet
ensemble L1. Ensuite, on construit l'ensemble C2 des motifs
fréquents candidats de taille 2 (ce sont tous les couples construits
à partir des motifs fréquents de taille 1). On obtient ainsi la
liste des motifs fréquents de taille 2 qu'on note par L2. On ne
conservera, bien sûr, que les éléments de C2 dont
le support est supérieur au seuil. On construit encore l'ensemble
C3 des motifs fréquents candidats de taille 3 et on ne retient
que ceux dont le support est supérieur au seuil, ce qui produit
L3. On continue le processus jusqu'à ce que l'ensemble Li
n'ait plus d'éléments.[16]
Cette approche s'appuie sur deux principes fondamentaux
suivants(Principe de la décroissance du support)[51] :
1. Tout sous motif d'un motif fréquent est
fréquent. (Si m' C_ m et support(m)>
us, alors support(m')> us).
2. Tout sur-motif d'un motif non fréquent est non
fréquent. (Si m' D m et sup-port(m)<
us, alors support(m')< us).
Plus clairement on a l'algorithme suivant[17] :
Algorithme : Algorithme A-priori
Entrée :(O, P, 7Z) : Une base de
donnée formelle ; us E [0; 1]
Sortie : L'ensemble des motifs fréquents
de la base relativement au seuil us
Début
L1 -- liste des motifs dont le support est
> us
i-1
répéter
i + +
à partir de Li-1, déterminer
l'ensemble Ci des motifs fréquents
candidats comprenant i motifs.
Li --
O
Pour tout motif m E Ci
faire
si support(m) >
us alors
ajouter m à Li
fin si
fin pour
jusque Li = O
Retourner ui=1 Li
Fin
Nous allons simulé le déroulement de l'algorithme
en considérant la base de donnée
formelle donnée à la table 4.1 pour un
seuil us = 26.[51]
Génération de candidats de taille 1
:
C1 = {a,b,c,d,e}
|
dont le support respectif est :
|
3
|
5
|
5
|
1
6 et
|
5
|
|
D'où
|
6;
|
6;
|
6;
|
6
|
48
Génération de candidats de taille 2 :
Combiner 2 à 2 les candidats de taille 1 de L1
C2 = {ab, ac, ae, bc, be, ce}
dont le support respectif est :
4
6
2324 5
6' 6' 6' 6, 6
et
Ainsi L2 = C2 parce que tous les motifs de
C2 sont fréquents.
Génération de candidats de taille 3 :
Combiner 2 à 2 les candidats de taille 2 de L2
N.B: Nous ne considérons que les motifs dont la taille
vaut 3.
C3 = {abc, abe, ace, bce}
|
le support respectif est :
|
2
|
2
|
2
|
4
|
6' 6' 6' 6
Tous les motifs sont fréquents, d'où L3 =
C3 Génération de candidats de taille 4
:
2
6
C4 = {abce} le support vaut
On a : L4 = C4 pour la même raison que
précédemment. Génération de candidats de
taille 5 :
C5 = O d'où L5 =
O
L'algorithme retourne ainsi l'ensemble des motifs
fréquents :
L = L1 ? L2 ? L3 ? L4 ? L5
Remarque 1
Le déroulement de cet algorithme est similaire au
parcours du treillis des parties de P ordonnées pour
l'inclusion. Supposons que P = {a, b, c}. Le treillis des
parties de P, comme illustré à la figure 4.2,
est parcouru par niveau croissant à partir du niveau j = 1.
Quand un motif n'est pas fréquent, tous ses super-motifs sont non
fréquents. Exemple du motif c qui n'est pas fréquent(il
a été barré), et par conséquent, aucun de ses
super-motifs n'est considéré. Cela nous permet d'optimiser
l'accès à la base de donnée [51].
Notons que la valeur du seuil u,9 est
fixé par l'analyste. Celui-ci peut suivre une approche itérative
en fixant un seuil au départ, et en fonction du résutat mais
aussi de l'objectif poursuivi, changera la valeur du seuil.
| 
