L'algorithme apriori

Analyse des paniers d'achats en R

Christopher Bruffaerts

Statistician

Extraction de règles d'association

L'extraction de règles d'association permet de découvrir des relations pertinentes entre des articles dans une grande base de transactions.

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

Génération d'ensembles fréquents : trouver tous les ensembles d'articles fréquents dans une base de transactions potentiellement volumineuse. Un ensemble est dit fréquent s'il respecte un seuil minimal de support.
Génération de règles : à partir des ensembles fréquents, générer des règles d'association dont la confiance dépasse un seuil minimal de confiance.

L'algorithme apriori est un classique rapide appartenant à la famille des algorithmes d'extraction de règles d'association.

Idée derrière l'algorithme apriori

L'algorithme apriori :

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

Principe d'apriori :

Si un ensemble est fréquent, tous ses sous-ensembles le sont aussi.
- p. ex. si {A,B} est fréquent, alors {A} et {B} le sont aussi
Si un ensemble est non fréquent, tous ses sur-ensembles sont non fréquents.
- p. ex. si {A} est non fréquent, alors {A,B}, {A,C} et {A,B,C} sont non fréquents.

¹ Agrawal et Srikant (1994)

Exemple : ensembles 1‑article

treillis_d_ensembles_1

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 minimal de support = 3/7 = 0,42

Exemple : ensembles 2‑articles

treillis_d_ensembles_2

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 minimal de support = 3/7 = 0,42

Exemple : ensembles 3‑articles

tous_les_ensembles

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 minimal de support = 3/7 = 0,42

Exemple : ensembles fréquents

treillis_d_ensembles_3

Ensemble	Nombre	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 minimal de support = 3/7 = 0,42

Apriori : génération de règles

Après la coûteuse étape de génération des ensembles fréquents, apriori génère des règles :

Commencer par des règles très confiantes avec un seul antécédent
- p. ex. {A,C} $\rightarrow$ {B}
Construire des règles plus complexes, avec plus d'articles à 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 – ensembles fréquents

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

Sortie d'apriori – ensembles fréquents

Ensembles 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_ensembles_3

Extraire des règles avec la fonction apriori

Paramètre : les paramètres d'extraction influencent les caractéristiques des ensembles ou des règles trouvés.

Support = 3/7
Confiance = 60 %
Longueur minimale de la règle = 2

Appel de la fonction apriori pour générer des règles avec des arguments précis

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 des paniers d'achats en R