L’algorithme A-priori

Définitions :

L’algorithme A-priori1 est un algorithme d’exploration de données conçu en 1994, par Rakesh Agrawal et Ramakrishnan Sikrant, dans le domaine de l’apprentissage des règles d’association. Il sert à reconnaître des propriétés qui reviennent fréquemment dans un ensemble de données et d’en déduire une catégorisation.

A-Priori détermine les règles d’association présentes dans un jeu de données, pour un seuil de support et un seuil de confiance fixés. Ces deux valeurs peuvent être fixées arbitrairement par l’utilisateur. (Continuer la lecture…)

Une règle d’association est une règle ayant la forme ai = vi , aj = vj , …am = vm , ce qui s’interprète par :

« si les attributs ai, aj , … am ont une certaine valeur, alors l’attribut a? prend généralement une certaine valeur v? , ab une certaine valeur vb, … ».

La difficulté consiste notamment à trouver des règles qui soient significatives et non seulement le résultat du hasard.

Dans un jeu de données, on dispose de xi éléments (ex : lignes dans une table de données) connus aussi sous le nom de Transactions. Chaque élément est décrit par un ensemble d’attributs aj (ex : colonnes dans une ligne de données). Un attribut correspond aussi à un item. Un ensemble d’items est dit fréquent s’il correspond à un motif fréquent dans la base de transactions.

Chaque règle d’association a deux mesures : le « support » et la « confiance ». Le support d’un ensemble d’items est définit comme la fréquence d’apparition simultanée des items figurant dans l’ensemble des données.

La « confiance » d’une règle « si condition alors conclusion » est le rapport :

Nombre de données où les items de la condition et de la conclusion apparaissent simultanément


Nombre de données où les items de la condition apparaissent simultanément

Le tableau suivant illustre l’exemple de paniers d’achats de certains clients :

Article A

Article B

Article C

Article D

Client 1

x

x

Client 2

x

x

Client 3

x

Client 4

x

x

x

Client 5

x

  • support (A, B) = 1/5 , car A et B n’apparaissent simultanément que dans le panier du Client 1.
  • support (A, C) = 2/5 , car A et C apparaissent simultanément dans le panier des clients 2 et 4.

On dit qu’un ensemble d’items est un ensemble d’items fréquents si le support de cet ensemble d’items est supérieur à un certain seuil (> 5% par exemple).

  • confiance (si A, alors B) = 1/3 ,  car A et B apparaissent simultanément dans le panier de 1 client et A apparait dans le panier de 3 clients.
  • confiance (si A, alors C) = 2/3 car A et C apparaissent simultanément dans le panier de 2 clients et A apparait dans 3 clients.

On définit un seuil de confiance comme la valeur minimale que la confiance doit avoir pour que l’apparition simultanée
des items considérés ne puisse pas être simplement due au hasard. Toutefois on ne s’intéresse qu’aux règles ayant une confiance maximale.

Extraction  Itemsets Frequents

Extraction Itemsets Frequents

Fonctionnement :

L’algorithme A-Priori fonctionne en deux phases : on commence par rechercher les ensembles d’items fréquents (EIF);
ensuite, on utilise ces EIF pour déterminer les règles d’association dont la confiance est supérieure au seuil fixé.

La construction des EIF est itérative : on construit d’abord les EIF contenant un seul item, puis ceux contenant 2 items,
puis ceux contenant 3 items, …
On commence par déterminer les EIF de taille 1, on note cet ensemble L1. Ensuite, on construit l’ensemble C2 des EIF candidats de taille 2 : ce sont tous les couples construits à partir des EIF de taille 1. On obtient la liste des EIF de taille 2 (L2) en ne conservant que les éléments de C2 dont le support est supérieur au seuil. On construit alors C3, l’ensemble des triplets d’items dont les 3 sous-paires sont dans L2 et on ne retient que ceux dont le support est supérieur au seuil, ce qui produit L3. Et ainsi de suite, tant que Li n’est pas vide.

Toutefois, si on considère Xk un sous-ensemble d’items fréquent, tous les sous-ensembles d’items contenus dans Xk et qui soient de longueurs inférieurs à k sont fréquents. Par exemple si ABCD est un sous-ensemble d’items fréquents, alors, les sous ensembles : ABC, ABD, BCD, AB, AC, BC, BD, CD, A, B, C, D les sont aussi.

L’algorithme A-priori

Apriori

On notera que la donnée Ck (ainsi que Lk) est un ensemble d’enregistrements contenant deux champs :

· itemset : ce champs contient le sous ensemble d’items,

· count : ce champs contient la fréquence de cet ensemble dans la base de transactions.

Cliquez pour agrandir

L’inconvénient majeur de cet algorithme est le nombre considérable de l’accès à la base de données D. Une amélioration qui consiste à intégrer les identificateurs des transactions est proposée dans la section suivante.

L’algorithme AprioriTid

L’amélioration qu’apporte cet algorithme par rapport au précédent est le fait de stocker à chaque itération les identificateurs des transactions contenant les sous-ensembles fréquents dans l’ensemble Ck.La propriété des sous-ensembles fréquents nous permet de voir clairement que les transactions sollicitées à l’itération k +1 seront parmi celles identifiées à l’itération k. Par conséquent, l’accès à D est effectué seulement pour l’itération 1.

Cliquez pour agrandir

Génération des règles

Disposant des EIF, il nous faut maintenant les transformer en règles. Avec les notations précédentes, on dispose d’un ensemble de Li pour des i croissant de 1 à une certaine valeur, chaque Li étant une liste de i items dont la fréquence d’apparitions est supérieure à un certain seuil.

Supposons que L3 contienne le triplet (a, b, c). Plusieurs règles d’association peuvent être
engendrées par ce triplet :

1.  si a et b alors c

2.  si a alors b et c

3.  si b et c alors a

4.  si b alors a et c

5.  si a et c alors b

6.  si c alors a et b

Parmi ces 6 règles candidates, on ne doit retenir que celles dont la confiance est supérieure au seuil fixé.

Si l’énumération des règles candidates est possible sur ce petit exemple, il faut bien être conscient que sur dans une application réelle cela est impossible : à nouveau, le nombre de règles candidates est beaucoup trop grand. Il nous faut donc une méthode plus judicieuse.

Une bonne stratégie de recherche de règles serait d’adopter la méthode suivante :

1. Trouver les plus grands ensembles d’items fréquents.

2. En extraire les règles de confiance supérieure au seuil, ayant des conditions minimales.

3. Pour les configurations n’ayant pas engendré des règles d’association, explorer d’une façon analogue, les sous-ensembles immédiats.

105 Responses to “L’algorithme A-priori”

  1. samir says:

    je veux des cours de data mining

  2. Bravo et merci pour cet article “L’algorithme A-priori | Khaled TANNIR”, ça fait toujours plaisir de voir des choses comme celles-ci. On voit tellement de bêtises à droite et à gauche sur internet que quand on tombe sur un billet comme le votre on se doit de le dire. C’est pourquoi je me suis permis de déposer un commentaire, chose qui n’est pas des mes habitudes, mais là ça valait le coup. Merci et bonne continuation.

  3. j’ai une bdd xml et je veut travailler avec apriori pour trouver les regles d’association mais il faut que je met les données dans un format intermidiaire.
    je veux savoir quelles sont les format qu’accepte apriori
    merci

    • le format de la source de données importe peu. Ce qui compte c’est le volume de données et comment est-il représenté en mémoire. Il existe plusieurs methodes pour optimiser ceci par la création de tableau binaire par exemple avec une distribution en colonne ou en ligne. Il ne faut pas oublier que la comparaison de chaines de caractères (string) est très gourmande en ressources et ça ralentit bcp l’execution de l’algorithme.

Leave a Reply to KTA