Apriori : Guide complet — Principes, Exemples et Implémentation Python

Résumé

L’algorithme Apriori est l’un des piliers fondamentaux de l’apprentissage non supervisé et de l’analyse de données transactionnelles. Proposé par Rakesh Agrawal et Ramakrishnan Srikant en 1994, il permet de découvrir des règles d’association fréquentes au sein d’ensembles de transactions — le fameux problème du « market basket analysis ». Si vous avez déjà vu une recommandation du type « les clients qui ont acheté ce produit ont aussi acheté… », c’est très probablement une règle d’association découverte par Apriori ou l’un de ses descendants.

Dans ce guide, nous couvrons en détail le principe mathématique de l’algorithme, son intuition, une implémentation Python complète avec la bibliothèque mlxtend, les hyperparamètres clés, les avantages et limites, ainsi que quatre cas d’usage concrets.

Principe mathématique

Itemset, transaction et base de données

Une transaction est un ensemble d’éléments achetés ou observés ensemble. Par exemple, un ticket de caisse dans un supermarché : {lait, pain, beurre}.

Un itemset est un sous-ensemble d’éléments. Un itemset contenant k éléments est appelé un k-itemset. L’objectif d’Apriori est de trouver tous les itemsets dont la fréquence d’apparition dépasse un seuil minimal.

Support

Le support d’un itemset mesure la proportion de transactions dans lesquelles cet itemset apparaît. Formellement :

support(A) = nombre de transactions contenant A / nombre total de transactions

Pour une règle d’association A → B :

support(A → B) = support(A ∪ B) = P(A ∩ B)

Le support reflète la fréquence globale de la règle. Une règle avec un support élevé est fréquente dans l’ensemble des données.

Confiance

La confiance d’une règle A → B mesure la probabilité conditionnelle que B apparaisse sachant que A est présent :

confiance(A → B) = P(B | A) = support(A ∪ B) / support(A)

La confiance indique la fiabilité de la règle : une confiance de 0,8 signifie que dans 80 % des cas où A apparaît, B apparaît également.

Lift

La confiance seule peut être trompeuse si B est déjà très fréquent en soi. Le lift corrige ce biais en comparant la confiance à la fréquence marginale de B :

lift(A → B) = confiance(A → B) / support(B) = P(A ∩ B) / (P(A) × P(B))

• lift = 1 : A et B sont indépendants (aucune association).
• lift > 1 : A et B sont positivement corrélés (association intéressante).
• lift < 1 : A et B sont négativement corrélés (ils tendent à s’exclure).

Le lift est probablement la métrique la plus informative pour évaluer la qualité d’une règle d’association.

Propriété anti-monotone (anti-monotonie)

Le cœur génial d’Apriori repose sur la propriété anti-monotone du support :

Si un itemset n’est pas fréquent, alors aucun de ses sur-ensembles ne peut être fréquent.

Autrement dit, si l’itemset {bière, chips} n’apparaît pas suffisamment souvent, alors {bière, chips, cacahuètes} ne pourra certainement pas atteindre le seuil de fréquence requis. Cette propriété permet d’élaguer massivement l’espace de recherche — c’est ce qui rend Apriori calculable en pratique.

Itérations : candidats k, join step et prune step

L’algorithme procède par itérations successives :

1. Candidats k : à partir des (k-1)-itemsets fréquents, on génère des candidats k-itemsets en les combinant deux à deux (join step). Deux itemsets sont joints s’ils partagent k-2 éléments communs.
2. Filtrage par support minimum : on parcourt l’ensemble des transactions pour compter la fréquence de chaque candidat k-itemset. Ceux dont le support est inférieur au min_support sont écartés.
3. Prune step : grâce à la propriété anti-monotone, on peut éliminer un candidat k-itemset si l’un de ses sous-ensembles (k-1) n’est pas fréquent. Cela évite de compter inutilement des itemsets qui ne pourront jamais être fréquents.

On répète ces étapes en incrémentant k jusqu’à ce qu’aucun nouvel itemset fréquent ne soit trouvé.

Intuition

Imaginez que vous gériez un supermarché. Vous voulez comprendre quels produits sont souvent achetés ensemble pour optimiser le placement en rayon, les promotions croisées, ou les suggestions de panier.

L’idée d’Apriori est simple mais puissante : si une combinaison de produits est rare, aucune combinaison plus grande contenant ces produits ne peut être fréquente. Par exemple, si les clients n’achètent presque jamais « bière et chips » en même temps, alors il est inutile de vérifier si « bière, chips et cacahuètes » est fréquent — c’est mathématiquement impossible que ce triplet soit plus fréquent que la paire qui le compose.

Cette intuition de « filtrage ascendant » est ce qui permet à Apriori d’éviter une explosion combinatoire. Sans la propriété anti-monotone, il faudrait évaluer 2^n – 1 itemsets possibles pour n produits distincts — ce qui devient rapidement ingérable. Avec l’élagage, seuls les candidats prometteurs sont examinés.

Implémentation Python

Installation des dépendances

pip install mlxtend pandas

Préparation des données transactionnelles

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules

# Dataset transactionnel exemple : tickets de caisse d'un supermarché
dataset = [
    ['lait', 'pain', 'beurre'],
    ['lait', 'couches', 'jus de fruits'],
    ['pain', 'beurre', 'lait'],
    ['lait', 'pain', 'jus de fruits'],
    ['bière', 'chips', 'cacahuètes'],
    ['bière', 'chips'],
    ['lait', 'pain', 'beurre', 'jus de fruits'],
    ['bière', 'cacahuètes', 'pain'],
    ['lait', 'beurre'],
    ['chips', 'cacahuètes', 'bière', 'jus de fruits'],
    ['pain', 'beurre', 'lait', 'couches'],
    ['bière', 'chips', 'cacahuètes'],
    ['lait', 'pain'],
    ['jus de fruits', 'couches', 'lait'],
    ['pain', 'beurre'],
]

# Encodage one-hot des transactions
te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)

print("Shape du DataFrame :", df.shape)
print(df.head())

Exécution de l’algorithme Apriori

# Trouver les itemsets fréquents avec un support minimum de 0,3 (30 %)
frequent_itemsets = apriori(df, min_support=0.3, use_colnames=True)

print("\nItemsets fréquents (support >= 0,3) :")
print(frequent_itemsets.sort_values('support', ascending=False))

La fonction apriori retourne tous les itemsets dont le support dépasse le seuil défini. Le paramètre use_colnames=True garantit que les noms des produits apparaissent directement dans le résultat, au lieu d’indices numériques.

Extraction des règles d’association

# Générer les règles d'association à partir des itemsets fréquents
# On filtre par lift > 1 pour ne garder que les associations positives
rules = association_rules(
    frequent_itemsets,
    metric="lift",
    min_threshold=1.0
)

# Trier par lift décroissant
rules = rules.sort_values('lift', ascending=False)

print("\nRègles d'association (lift > 1.0) :")
print(rules[['antecedents', 'consequents', 'support', 'confidence', 'lift']])

Interpréter les résultats

Chaque règle produite contient :

Visualisation des règles

import matplotlib.pyplot as plt

# Nuage de points : support vs confiance, coloré par lift
plt.figure(figsize=(10, 6))
scatter = plt.scatter(
    rules['support'],
    rules['confidence'],
    s=rules['lift'] * 100,
    c=rules['lift'],
    cmap='viridis',
    alpha=0.7,
    edgecolors='k'
)
plt.colorbar(scatter, label='Lift')
plt.xlabel('Support')
plt.ylabel('Confiance')
plt.title("Règles d'association Apriori : support vs confiance (taille = lift)")
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('regles_apriori.png', dpi=200)
plt.show()

Cette visualisation permet d’identifier rapidement les règles les plus intéressantes : celles situées en haut à droite avec une grande taille (fort lift) sont à la fois fréquentes, fiables et fortement corrélées.

Hyperparamètres

Le réglage des hyperparamètres est crucial pour obtenir des résultats pertinents avec Apriori :

min_support

Le seuil minimum de support pour considérer un itemset comme fréquent. C’est le paramètre le plus impactant :

• Trop élevé (ex. 0,5) : vous risquez de ne trouver aucun itemset au-delà des singletons.
• Trop bas (ex. 0,01) : l’algorithme explore un nombre exponentiel de candidats et peut devenir très lent.

En pratique, commencez par 0,1 à 0,3 selon la taille de votre dataset et ajustez.

min_confidence

Appliqué lors de la génération des règles, ce seuil élimine les règles peu fiables. Une confiance minimale de 0,5 à 0,7 est un bon point de départ.

min_lift / min_threshold

Dans mlxtend, le paramètre min_threshold s’applique à la métrique choisie via metric. Si metric="lift", alors min_threshold=1.0 ne garde que les règles présentant une association positive. Un lift minimum de 1,2 à 2,0 est souvent pertinent pour isoler les règles véritablement intéressantes.

max_length

Ce paramètre limite la taille maximale des itemsets explorés. Par exemple, max_length=3 empêche l’algorithme de générer des 4-itemsets ou plus. C’est utile pour :

• Réduire le temps de calcul sur de grands jeux de données.
• Se concentrer sur des règles actionnables (des règles à 4-5 conditions sont rarement exploitables en pratique).

Avantages et limites

Avantages

• Simplicité conceptuelle : Apriori est intuitif et facile à expliquer à des non-techniciens, ce qui en fait un excellent outil de communication.
• Théorie solide : les métriques de support, confiance et lift ont une interprétation statistique claire et rigoureuse.
• Élagage efficace : la propriété anti-monotone réduit drastiquement l’espace de recherche par rapport à une exploration naïve.
• Large applicabilité : au-delà du retail, Apriori s’applique à la bio-informatique, l’analyse de logs, la détection de fraudes, et bien d’autres domaines.
• Implémentations fiables : la bibliothèque mlxtend offre une implémentation robuste, et des alternatives comme efficient-apriori ou PyFIM existent pour les datasets massifs.

Limites

• Coût sur les grands datasets : Apriori nécessite de multiples parcours complets de la base de données (un par niveau k), ce qui devient prohibitif au-delà de quelques centaines de milliers de transactions.
• Explosion combinatoire : même avec l’élagage, un nombre élevé d’items distincts ou un min_support trop bas génère un nombre massif de candidats.
• Sensibilité aux paramètres : le choix du min_support influence massivement les résultats. Il n’existe pas de valeur universelle optimale.
• Règles redondantes : Apriori peut produire de nombreuses règles similaires (par exemple, A → B et A,C → B), ce qui nécessite une étape de post-traitement.
• Pas de prise en compte du contexte : l’algorithme ne modélise pas la temporalité, la saisonnalité ou les préférences individuelles. Des algorithmes plus récents comme FP-Growth ou Eclat offrent de bien meilleures performances.

4 cas d’usage concrets

1. Analyse de panier en grande distribution

Le cas d’usage historique et le plus connu. Un supermarché analyse les tickets de caisse pour identifier les produits fréquemment achetés ensemble. Résultats typiques :

• {bière, chips} → lift de 2,3 : les amateurs de bière achètent significativement plus de chips que la moyenne.
• {couches, lait} → support élevé mais lift proche de 1 : corrélation due à une cause commune (les jeunes parents) plutôt qu’à une relation directe.

Ces insights guident le placement en rayon, les promotions croisées et la composition des lots promotionnels.

2. Recommandation de contenu sur les plateformes numériques

Les plateformes de streaming ou d’e-commerce utilisent des règles d’association pour suggérer du contenu. Si un utilisateur regarde le film A et le film B, et que la règle {film A, film B} → {film C} présente un lift élevé, alors le film C sera recommandé. Netflix et Amazon ont historiquement exploité ce type de mécanique avant de migrer vers des approches de filtrage collaboratif plus sophistiquées.

3. Détection de motifs en bio-informatique

En génomique, Apriori permet d’identifier des combinaisons de mutations génétiques qui co-occurrent fréquemment dans des populations de patients. Un itemset {mutation_A, mutation_B, symptôme_C} avec un lift élevé peut révéler une interaction biologique significative et ouvrir des pistes de recherche médicale. Ce domaine exploite la capacité d’Apriori à découvrir des corrélations dans des données catégorielles à haute dimension.

4. Analyse de logs et cybersécurité

En sécurité informatique, Apriori peut détecter des séquences d’événements anormales. Par exemple, si les itemsets {connexion échouée SSH, scan de port, tentative d'élévation de privilèges} apparaissent avec un support anormalement élevé par rapport au bruit de fond, cela peut signaler une attaque coordonnée. L’élagage anti-monotone est particulièrement utile ici car il permet de filtrer rapidement les combinaisons d’événements insignifiantes.

Voir aussi

• Maîtriser les Duodigits en Python : Guide Complet pour Optimiser vos Calculs Numériques
• Maîtriser les Permutations de Projet avec Python : Guide Complet pour Développeurs