L'algorithme apriori

Analyse de panier en R

Christopher Bruffaerts

Statistician

Extraction de règles d'association

L'extraction de règles d'association permet de découvrir des relations intéressantes entre des items dans une grande base transactionnelle.

Cette tâche se divise en deux sous-tâches :

Génération d'itemsets fréquents : trouver tous les itemsets fréquents d'une base potentiellement vaste de transactions. Un itemset est dit fréquent s'il satisfait un seuil de support minimal.
Génération de règles : à partir des itemsets fréquents, créer des règles d'association dont la confiance dépasse un seuil de confiance minimal.

L'algorithme apriori est un algorithme classique et rapide appartenant à cette famille.

Idée derrière l'algorithme apriori

L'algorithme apriori :

Approche ascendante
Génère des itemsets candidats en exploitant le principe d'apriori

Principe d'apriori :

Si un itemset est fréquent, alors tous ses sous-ensembles le sont aussi.
- p. ex. si {A,B} est fréquent, alors {A} et {B} le sont tous deux
Si un itemset est rare, tous ses sur-ensembles sont rares.
- p. ex. si {A} est rare, alors {A,B}, {A,C} et {A,B,C} sont rares.

¹ Agrawal et Srikant (1994)

Exemple : itemsets de taille 1

treillis_d'itemsets

TID	Transaction
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Seuil de support minimal = 3/7 = 0,42

Exemple : itemsets de taille 2

treillis_d'itemsets

TID	Transaction
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Seuil de support minimal = 3/7 = 0,42

Exemple : itemsets de taille 3

tous_les_itemsets

TID	Transaction
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Seuil de support minimal = 3/7 = 0,42

Exemple : itemsets fréquents

treillis_d'itemsets

Itemset	Occur.	Support
{A}	3	0.42
{B}	6	0.85
{C}	4	0.57
{D}	5	0.71
{A,B}	3	0.42
{B,C}	3	0.42
{B,D}	4	0.57
{C,D}	3	0.42

¹ Seuil de support minimal = 3/7 = 0,42

Apriori : génération de règles

Après la (coûteuse) génération des itemsets fréquents, apriori génère des règles :

Commencer par des règles à forte confiance avec un seul antécédent
- p. ex. {A,C} $\rightarrow$ {B}
Construire des règles plus complexes, avec plus d'items à droite
- p. ex. {A,C} $\rightarrow$ {B, D}

Astuce : élagage des règles d'association

p. ex. : si la règle {B,C,D} $\rightarrow$ {A} a une faible confiance, toutes les règles dont le conséquent contient A peuvent être écartées (comme {B,D} $\rightarrow$ {A, C} ou {D} $\rightarrow$ {A,B, C}).

Un premier essai avec apriori

Données transactionnelles

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

Premier appel à la fonction apriori – itemsets fréquents

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))

Sortie d'apriori – itemsets fréquents

Itemsets fréquents

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

treillis_d'itemsets

Extraire des règles avec la fonction apriori

Paramètre : les paramètres d'extraction modifient les caractéristiques des itemsets ou règles extraits.

Support = 3/7
Confiance = 60 %
Longueur minimale d'une règle = 2

Appel à la fonction apriori pour générer des règles avec des arguments spécifiques

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )

Extraction de règles : sortie

Inspection des règles

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4

Passons à la pratique !

Analyse de panier en R