II.2 L'induction et l'évaluation des
règles
L'induction est en effet l'extraction de règles
qui satisfont des seuils minimums prédéfinis de support et de
confiance à partir d'une base de données volumineuse [Agrawal et
Srikant., 1994]. Cette extraction se déroule en deux phases
:
(1) extraction des Itemsets fréquents
;
(2) génération des règles
d'association confiantes.
Le nombre d'Itemsets possibles pour une base de
données stockant n Items est 2n. Ceci rend le nombre de
règles encore plus énorme. Il en découle que l'extraction
de la totalité des Itemsets (pour ensuite tester leurs
fréquences) soit une opération très coûteuse voir
impossible. Les deux mesures qui évaluent le degré
d'intérêt de l'utilisateur envers un motif sont : le support et la
confiance. L'utilisateur mentionne alors un seuil minimal de support et un
seuil minimal de confiance, et les règles dont les confiances sont
supérieures au seuil fixé sont acceptées et les autres
sont alors rejetées. On peut dire alors que ces deux seuils sont des
contraintes d'extraction de règles. Ainsi, le problème
d'extraction de règles d'association est décomposé en deux
étapes :
- la première consiste à dégager
les Itemsets fréquents, i.e., les Itemsets dont le nombre d'occurrences
est supérieur au seuil minimum de support ;
- la seconde consiste à générer
des règles d'association à partir de ces Itemsets
fréquents qui respectent un seuil minimum de confiance. Cette seconde
étape est beaucoup plus simple. En effet, une fois les Itemsets
fréquents trouvés, il y a génération des
règles possibles pour chaque Itemset.
Génération des règles
La génération des règles est donc
une opération de transformation des ensembles d'Items en règles
de manière efficace. De ce fait, à partir d'un ensemble de
n Items, on
Chapitre II : L'extraction de règles d'association -
36 -
peut générer 2n-1
règles potentielles, et on ne gardera que les règles avec une
confiance supérieure au minimum fixé par
l'utilisateur.
On peut alors dire : Etant donné deux seuils
minimaux, s de support et c de confiance, l'extraction de règles
d'association se fait en deux étapes :
(1) Extraction des Itemsets fréquents (dont la
fréquence est supérieure à s)
(2) Extraction des règles d'associations
confiantes (dont la confiance est supérieure à c) à partir
des Itemsets fréquents.
Ce traitement se traduit par :
(1) un calcul coûteux des supports;
(2) une génération coûteuse des
règles ;
(3) un calcul coûteux de la confiance
;
(4) un parcours des données initiales
récurrent.
Évaluation des règles
La méthode d'extraction de règles
d'association peut produire des règles d'association triviales ou
inutiles. Ces règles triviales sont des règles évidentes
(par exemple : Si marié Alors non-célibataire) qui n'apporte pas
d'information supplémentaire. Les règles inutiles sont des
règles difficiles à interpréter qui peuvent provenir de
particularités propres à la liste des t-uples ayant servi
à l'apprentissage. De plus, une règle d'association est
destinée à être utilisée par la suite dans un but
décisionnel, il est nécessaire d'évaluer sa
qualité. Il faut qu'à l'étape de fouille, il y ait
suffisamment d'exemples vérifiant cette règle, et une
quantité de contre-exemples qui ne porte pas préjudice au sens
que prend cette règle dans son contexte d'extraction.
De nombreux critères d'évaluation
existent [Hip et al., 2000]. Ils peuvent être aussi subjectifs. L'expert
du domaine sait quels attributs il souhaite avoir dans les règles
d'association, mais ce cas de figure est très rare, car contraire au but
de l'ECD qui est la découverte des connaissances dont on ignore à
priori l'existence. Il existe également de nombreux critères
beaucoup plus objectifs qui consistent à étudier le nombre
d'exemples et de contre-exemples afin que la règle obtenue ne soit pas
trop générale ou évidente, car dans ce cas il n'y a rien
de nouveau. Les statistiques sont utilisées pour associer à
chaque règle d'association de la forme X ? Y des
mesures permettant d'avoir une idée de sa qualité :
- le support est une mesure dite d'utilité.
C'est la probabilité p (X, Y) pour que X et Y soient vrais en même
temps ;
Chapitre II : L'extraction de règles d'association -
37 -
- la confiance est une mesure dite de
précision. C'est la probabilité pour que Y soit vrai lorsque l'on
a X vrai, soit la probabilité conditionnelle p (Y | X).
Suivant le contexte dans lequel est extraite cette
règle, le taux d'erreur admissible dépend du facteur risque. Par
exemple, on exigera une qualité de cette règle d'association
beaucoup plus importante dans le domaine médical. Dans ce cas, les
valeurs des seuils minimaux de support et de confiance seront
élevées afin de ne retenir que les règles les plus fiables
dans le sens où elles ont très peu de contre-exemples (dont
l'existence peut être dangereuse). De nombreux autres indices de mesure
de la qualité d'une règle d'association existent [Agrawal et al.,
1993].
| 
