Impact de la structure de treillis dans le domaine de fouille de données et la représentation des connaissances.

4.3.3 Extraction de règles d'associations

Dans cette section nous vous présenterons le concept de règles d'associations dont la contribution à l'émergence du data mining, en tant que domaine scientifique à part entier, est non négligeable.

49

FIGURE 4.2 - Exemple de treillis des parties ordonnées par inclusion

4.3.4 Règles d'association

Un gérant d'un super marché a observé que les clients qui achètent les couchent culottes achètent également un pack de bières alors il s'est dit qu'il serait judicieux de disposer ces deux articles côte à côte afin de permettre au client de trouver vite les produits qu'il cherche. Ainsi, si vous visitez le site de vente de livres en ligne amazone.com et que vous recherchez des livres sur le data mining, vous pouvez voir ressortir des livres de statistique mais pas de livres de topologie par exemple. Ce résultat peut être issu du fait que l'étude des transactions des anciens clients a montrée qu'un nombre significatif de ceux qui ont acheté un ou plusieurs livres de data mining ont également acheté un ou plusieurs livres de statistique et non de topologie. [23]

Les règles d'associations interviennent dans plusieurs applications comme l'ana-lyse du panier de la menagère où elles servent à trouver les association entre les produits achetés par un consomateur particulier ou encore sur internet dans le but d'associer les différentes pages visitées par les internautes, comme illustré dans le paragraphe précédent.[11][15]

Définition 5(règle d'association)

Une règle d'association R est la donnée de deux motifs A et B où A est appelé prémisse de la règle et B la conséquence. Elle est notée par:

R = A -+ B

L'extraction de règles d'associations nous donne une information générale des relations existant entre motifs d'une base de donnée. Elle a pour objectif de déterminer si l'occurence du motif A est associé à l'occurence du motif B. Ainsi la qualité d'une règle sera évaluée en fonction de son support et de sa confiance.[25]

Définition 6(support d'une règle d'association)

Le support d'une règle d'association est défini comme étant le nombre d'oc-currences dans lesquelles les associations entre motifs sont observées divisé par le nombre total d'événements : [25]

Nombre de cas favorables

support{A -+ B} = support(A B) = (4.1)

Nombre de cas possible

50

On peut rapprocher la notion de support d'une règle à celle de probabilité des évé-nements[23]. En effet le support(A -+ B) est la probabilité que x possède le motif

A et que x possède le motif B (en supposant que x soit une variable aléatoire sur O avec une distribution uniforme)

Définition 7(confiance d'une règle d'association)

La confiance est défini comme étant la proportion de cas dans lequel les associations entre motifs sont réalisées sur le nombre de cas contenant la prémisse. Elle st notée par :[25]

support(A U B)

confiance(A -+ B) = (4.2)

support(A)

En effet, confiance(A -+ B) est la probabilité que la variable x possède la motif

B sachant qu'elle possède déjà la motif A. Ainsi :

- confiance(A -+ B) = 1 signifie que tous les objets possédant le motif A possèdent le motif B ;

- confiance(A -+ B) = 0 signifie qu'aucun n'objet possédant le motif A ne possède le motif B ;

Définition 8(Règle valide)

Une règle d'association R est valide si elle vérifie :

· support(R) > ó_s ;

· confiance(R) > ó_c ;

où ó_s, ó_c E [0; 1] sont des valeurs seuils prédéfinies.

N.B : Dans l'extraction de règles d'associations, seuls les règles valides intéressent l'analyste parce qu'elles renferment un maximum d'informations nécessaires pour celui-ci. Cependant L'extraction des règles d'association consiste à extraire toutes les règles solides ayant un support et une confiance suffisants par rapport à des seuils fixés à priori, à savoir le support et la confiance minima. [51]

Définition 8(Règle exacte, règle approximative)

Une règle d'association est exacte si sa confiance vaut 1. Dans le cas contraire, elle est dite approximative.

Si R = A -+ B est exacte, alors support(A U B) = support(A). En se basant sur la base de données formelle (table 4.1) on a :

3

support(a) = support(ac) = 6

Donc a -+ b est une règle exacte. Sa confiance vaut 1.[24]