1.2 Derivation des regles d'association
1.2.1 Base de transactions
Une base de transactions peut etre formellement representee
sous la forme d'un triplet K = (O,I,R) dans lequel O
et I sont, respectivement, des ensembles finis d'objets (les
transactions) et d'attributs (les items) et R ? O × I est une
relation binaire entre les transactions et les items. Un couple
(o,i) ? R denote le fait que la transaction o ?
O contient l'item i ? I.
Une transaction T, avec un identificateur appele TID
(Tuple IDentifier), contient un ensemble, non vide, d'items de I. Un
sous-ensemble X de I ou k = |X| est appele
un k-itemset ou simplement un itemset, et k represente la
longueur de X. Le nombre de transactions de K contenant un
itemset X, |{T ? K | X ? T }|, est appele
support absolu de X. Le support relatif de X est le
quotient de son support absolu par le nombre
1IX.
total de transactions de K, cad Supp(X)
{TEK
= Un itemset X est dit frequent
|O| cni
si son support relatif est superieur ou egal a un seuil minimum
minsup(1) specifie par l'utilisateur.
1.2.2 Regles d'association
La formalisation du probleme d'extraction des regles
d'association a ete introduite par Agrawal et al. en 1993 [1]. Une regle
d'association r est une relation entre itemsets de la forme r
: X (Y-X), dans laquelle X et Y sont des
itemsets frequents, tel que X ? Y . Les itemsets X et (Y
-X) sont appeles, respectivement, premisse et conclusion de la
regle r. La generation des regles d'association est realisee a partir
d'un ensemble F d'itemsets frequents dans un contexte d'extraction
K, pour un seuil minimal de support minsup. Les regles d'association
valides sont celles dont la mesure de confiance, Conf(r) =
SSuuppp*(Y
X , est superieure ou egale a un seuil minimal de confiance, defini par
l'utilisateur et qui sera note dans la suite minconf. Si Conf(r) = 1
alors r est appelee regle d'association exacte, sinon elle
est appelee regle d'association approximative [50].
Ainsi, chaque regle d'association, X (Y
-X), est caracterisee par :
1. Le niveau de support : il correspond au nombre de fois oft
l'association est presente, rapporte au nombre de transactions comportant
l'ensemble des items de Y.
Le niveau de support permet de mesurer la frequence de
l'association [42].
2. Le niveau de confiance : il correspond au nombre de fois
oft l'association est presente, rapporte au nombre de presences de X.
Le niveau de confiance permet de mesurer la force de l'association [42].
Ainsi, etant donne un contexte d'extraction /C, le probleme de
l'extraction des regles d'association dans 1C consiste a determiner
l'ensemble des regles d'association dont le support et la confiance sont au
moins egaux respectivement a minsup et minconf. Ce probleme peut etre decompose
en deux sous-problemes comme suit [1] :
1. Determiner l'ensemble des itemsets frequents dans /C, cad les
itemsets dont le support est superieur ou egal a minsup.
2. Pour chaque itemset frequent Ii, generer
toutes les regles d'association de la forme r : I, = I, tel
que I, C I, et dont la confiance est superieure ou egale a minconf.
Ces deux problemes sont resolus par un algorithme fondamental
dans la fouille de donnees, a savoir APRIORI [2]. Le premier sous-probleme a
une complexite exponentielle en fonction du nombre d'itemsets. En effet, etant
donne un ensemble d'items de taille n, le nombre d'itemsets frequents
potentiels est egal a 2'. Le deuxieme sous-probleme est exponentiel en la
taille des itemsets frequents. En effet, pour un itemset frequent I,
le nombre de regles d'association non triviales qui peuvent etre generees est
2|I| - 1. Toutefois, la generation des regles d'association
a partir des itemsets frequents ne necessite aucun balayage de la base de
donnees et les temps de calcul de cette generation sont faibles compares aux
temps necessaires pour la decouverte des itemsets frequents [47]. Neanmoins, le
probleme de la pertinence et de l'utilite des regles extraites est d'une
premiere importance etant donne que dans la plupart des bases de transactions
reelles, des milliers et meme des millions de regles d'association sont
generees [56, 67]. Or, il a ete constate que dans la pratique, plusieurs regles
etaient redondantes [10].
Afin de resoudre ces deux problemes, cad les temps
d'extraction des itemsets fréquents ainsi que la redondance au niveau
des règles d'association valides, Pasquier et al. [48] ont propose, en
1998, une approche qui consiste a extraire les itemsets fermés frequents
au lieu des itemsets frequents. Cette approche est basee sur le fait que
l'ensemble des itemsets fermes frequents est un ensemble generateur de
l'ensemble des itemsets frequents [47]. L'approche par extraction des itemsets
fermes frequents repose sur les fondements mathematiques de l'analyse formelle
de concepts [66]. La section suivante est consacree a la presentation de ces
fondements.
| 