FP-Growth : Guide complet — Principes, Exemples et Implémentation Python

Résumé

FP-Growth (Frequent Pattern Growth) est un algorithme d’extraction de motifs fréquents et de règles d’association qui révolutionne l’approche traditionnelle définie par Apriori. Au lieu de générer et tester des combinaisons candidates de manière itérative, FP-Growth construit une structure arborescente compacte appelée FP-Tree (Frequent Pattern Tree) qui encode l’ensemble des transactions en une seule passe. Le mining récursif de cet arbre permet d’extraire tous les itemsets fréquents sans jamais générer de candidats explicites. Cette approche est généralement 10 à 100 fois plus rapide qu’Apriori, particulièrement sur des jeux de données denses. Dans ce guide, nous explorerons le principe mathématique de l’algorithme, l’intuition derrière la structure FP-Tree, une implémentation pratique avec la bibliothèque mlxtend, et quatre cas d’usage concrets.

Principe mathématique du FP-Growth

Contexte et définitions

Soit un ensemble d’items I = {i₁, i₂, …, iₘ} et une base de transactions D = {T₁, T₂, …, Tₙ}, où chaque transaction Tₖ est un sous-ensemble de I. Un itemset est un sous-ensemble non vide d’items. Le support d’un itemset X est défini comme le nombre (ou la proportion) de transactions contenant X :

support(X) = |{T ∈ D | X ⊆ T}| / |D|

Un itemset est dit fréquent si son support est supérieur ou égal à un seuil minimal min_support.

Construction du FP-Tree

Le FP-Tree est une structure arborescente compressée construite en deux passes sur la base de données :

Première passe — calcul des fréquences et création de l’en-tête :

1. Parcourir toutes les transactions pour compter la fréquence de chaque item.
2. Supprimer les items dont la fréquence est inférieure à min_support × |D|.
3. Trier les items restants par fréquence décroissante. Cette liste ordonnée constitue la table d’en-tête (header table).
4. Chaque entrée de la table d’en-tête pointe vers le premier nœud correspondant dans l’arbre via une chaîne liée (chaîne de nœuds).

Deuxième passe — insertion des transactions dans l’arbre :

1. Pour chaque transaction :
   – Supprimer les items non fréquents.
   – Trier les items restants selon l’ordre de la table d’en-tête (fréquence décroissante).
   – Insérer cette séquence triée comme un chemin dans l’arbre :
   • Si un nœud correspondant existe déjà sur le chemin, incrémenter son compteur.
   • Sinon, créer un nouveau nœud avec un compteur initialisé à 1.
2. Chaque transaction devient ainsi un chemin racine-vers-feuille, et les préfixes communs sont partagés, ce qui compressé la représentation.

La racine de l’arbre est un nœud vide (null). Chaque nœud contient trois informations : le nom de l’item, le compteur (nombre de transactions passant par ce nœud), et un lien vers le nœud suivant du même item dans l’arbre (via la chaîne de la table d’en-tête).

Mining récursif des itemsets fréquents

Une fois le FP-Tree construit, l’extraction des itemsets fréquents se fait de manière récursive, sans génération de candidats :

1. Pour chaque item α de la table d’en-tête (traité de bas en haut, c’est-à-dire des items les moins fréquents aux plus fréquents) :
   – Collecter tous les chemins menant à des occurrences de α en remontant depuis chaque nœud α jusqu’à la racine. Cet ensemble de chemins forme la base de motifs conditionnels (conditional pattern base) de α.
   – Construire le FP-Tree conditionnel à partir de cette base : on recompte les items dans les chemins conditionnels et on ne conserve que ceux qui respectent le seuil min_support.
   – Si le FP-Tree conditionnel n’est pas vide, on le mine récursivement pour trouver tous les itemsets fréquents β dans ce sous-arbre.
   – Chaque itemset β trouvé est combiné avec le suffixe α pour former l’itemset fréquent β ∪ {α}.
2. Si le FP-Tree conditionnel ne contient qu’un seul chemin linéaire, tous les sous-ensembles de ce chemin sont automatiquement fréquents, ce qui permet une énumération directe sans récursion supplémentaire.

Propriété clé : la propriété de downward closure (ou anti-monotonie) garantit que tout sous-ensemble d’un itemset fréquent est aussi fréquent. Cette propriété est exploitée par le FP-Tree conditionnel pour garantir l’exhaustivité du mining sans avoir à tester explicitement toutes les combinaisons.

Extraction des règles d’association

À partir des itemsets fréquents extraits, on génère des règles d’association de la forme A ⇒ B :

• Confiance (confidence) : conf(A ⇒ B) = support(A ∪ B) / support(A)
• Lift : lift(A ⇒ B) = conf(A ⇒ B) / support(B) — un lift supérieur à 1 indique une corrélation positive.
• Leverage : lev(A ⇒ B) = support(A ∪ B) − support(A) × support(B)
• Conviction : conv(A ⇒ B) = (1 − support(B)) / (1 − conf(A ⇒ B))

Intuition : pourquoi le FP-Growth est si efficace

Pour bien comprendre la puissance du FP-Growth, comparons-le brièvement avec Apriori :

Apriori fonctionne par élimination itérative : il teste d’abord tous les items individuels, puis toutes les paires d’items fréquents, puis tous les triplets, et ainsi de suite. À chaque niveau k, il génère C(n,k) candidats potentiels et parcourt l’intégralité de la base de données pour compter leurs occurrences. Sur un dataset avec 100 items, cela peut représenter des millions de candidats à tester, et autant de passages sur les données.

FP-Growth, lui, change complètement la stratégie. Au lieu de tester toutes les combinaisons possibles, il construit en deux passes seulement un arbre compressé qui contient toute l’information nécessaire. Imaginez que chaque transaction soit un chemin dans une forêt : les transactions qui partagent les mêmes articles empruntent les mêmes sentiers. Les parties communes sont partagées (un seul chemin avec un compteur), et les déviations sont autant de branches. C’est comme avoir un index compressé de toutes les combinaisons existantes dans vos données.

Le mining récursif navigue ensuite dans cet arbre au lieu de recalculer des comptages. Pour trouver les combinaisons contenant un item donné, on suit simplement les chaînes de la table d’en-tête et on remonte les chemins correspondants. C’est extrêmement plus économique en termes d’accès mémoire et de nombre de passages sur les données.

Le gain de performance est dramatique quand les données sont denses (beaucoup d’items récurrents avec de nombreux préfixes partagés). Sur des données très clairsemées, l’arbre est moins compressé, mais FP-Growth reste généralement compétitif.

Implémentation Python avec mlxtend

En pratique, on utilise rarement une implémentation manuelle du FP-Growth. La bibliothèque mlxtend (Machine Learning Extensions) fournit une implémentation optimisée accessible via deux fonctions clés : fpgrowth pour extraire les itemsets fréquents et association_rules pour générer les règles.

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

# --- 1. Préparation des données ---
# Dataset exemple : transactions d'un supermarché
transactions = [
    ["lait", "pain", "beurre"],
    ["lait", "oeufs"],
    ["pain", "beurre", "oeufs"],
    ["lait", "pain", "beurre", "oeufs"],
    ["lait", "pain"],
    ["lait", "pain", "beurre"],
    ["pain", "beurre"],
    ["lait", "pain", "beurre", "yaourt"],
    ["oeufs", "yaourt"],
    ["lait", "oeufs", "yaourt"],
    ["pain", "yaourt"],
    ["lait", "pain", "yaourt"],
    ["beurre", "oeufs", "yaourt"],
    ["lait", "pain", "beurre", "oeufs", "yaourt"],
    ["pain", "beurre", "yaourt"],
]

# Encodage one-hot avec TransactionEncoder
te = TransactionEncoder()
te_ary = te.fit(transactions).transform(transactions)
df = pd.DataFrame(te_ary, columns=te.columns_)
print("Données encodées :")
print(df.head())

# --- 2. Comparaison de performance : FP-Growth vs Apriori ---
min_sup = 0.3

# FP-Growth
start_fg = time.time()
fp_items = fpgrowth(df, min_support=min_sup, use_colnames=True)
fp_time = time.time() - start_fg
print(f"\nFP-Growth ({fp_time:.4f}s) :")
print(fp_items.sort_values("support", ascending=False).to_string(index=False))

# Apriori (pour comparaison)
start_ap = time.time()
ap_items = apriori(df, min_support=min_sup, use_colnames=True)
ap_time = time.time() - start_ap
print(f"\nApriori ({ap_time:.4f}s) :")
print(ap_items.sort_values("support", ascending=False).to_string(index=False))

# Ratio de vitesse
print(f"\nFP-Growth est {ap_time/fp_time:.1f}x plus rapide qu'Apriori")

# --- 3. Extraction des règles d'association ---
rules = association_rules(fp_items, metric="confidence", min_threshold=0.5)
rules = rules.sort_values("lift", ascending=False)
print("\nRègles d'association (triées par lift) :")
cols = ["antecedents", "consequents", "support", "confidence", "lift", "leverage", "conviction"]
print(rules[cols].to_string(index=False))

# --- 4. Filtrer par lift > 1 ---
strong_rules = rules[rules["lift"] > 1.0]
print(f"\nRègles avec corrélation positive (lift > 1) : {len(strong_rules)}")
print(strong_rules[["antecedents", "consequents", "lift"]].to_string(index=False))

Analyse du résultat

Cet exemple illustre plusieurs points clés :

1. Les itemsets fréquents sont retournés avec leur support. On remarque que l’ensemble {lait, pain, beurre} apparaît fréquemment, ce qui est cohérent avec nos données.
2. La comparaison de vitesse montre généralement que FP-Growth est nettement plus rapide qu’Apriori, même sur un petit dataset. Sur des datasets de taille industrielle (millions de transactions, centaines d’items), l’écart se mesure en ordres de grandeur.
3. Les règles d’association révèlent les corrélations entre produits. Par exemple, une règle comme {beurre} ⇒ {pain} avec un lift de 1,3 indique que les clients qui achètent du beurre ont 30 % plus de chances d’acheter du pain que la moyenne générale.

Hyperparamètres essentiels

min_support

Le paramètre le plus critique. Il définit le seuil de fréquence minimal pour qu’un itemset soit considéré comme fréquent.

• Trop élevé (ex. 0,5) : peu d’itemsets sont trouvés, risque de passer à côté de patterns intéressants mais modérément fréquents.
• Trop bas (ex. 0,01) : explosion combinatoire du nombre d’itemsets trouvés, consommation mémoire excessive, temps de calcul long.

use_colnames

Paramètre booléen de la fonction fpgrowth. Quand use_colnames=True, les itemsets sont retournés avec les noms réels des colonnes (ex. {'lait', 'pain'}) au lieu d’indices numériques. C’est presque toujours préférable pour la lisibilité et la compatibilité avec association_rules.

max_len

Limite la taille maximale des itemsets retournés. Utile pour contrôler la complexité quand le nombre d’itemsets explose.

# Ne garder que les itemsets de taille 1 à 3
items_limited = fpgrowth(df, min_support=0.1, use_colnames=True, max_len=3)

Paramètres d’association_rules

• metric : métrique de filtrage ("confidence", "lift", "leverage", "conviction").
• min_threshold : seuil minimal pour la métrique choisie.
• num_itemsets : nombre d’itemsets fréquents en entrée (calculé automatiquement).

# Règles avec lift > 1,5 uniquement
rules_lift = association_rules(fp_items, metric="lift", min_threshold=1.5)

Avantages et limites du FP-Growth

Avantages

• Pas de génération de candidats : Contrairement à Apriori, FP-Growth ne génère jamais explicitement l’ensemble des combinaisons candidates.
• Deux passes sur les données seulement : La construction du FP-Tree nécessite exactement deux parcours de la base de transactions.
• Compression naturelle : Les préfixes communs sont partagés, ce qui réduit drastiquement la mémoire sur des données denses.
• Performance supérieure : Généralement 10 à 100 fois plus rapide qu’Apriori, selon la densité des données.
• Résultat exhaustif et identique : Le FP-Growth trouve exactement les mêmes itemsets fréquents qu’Apriori, sans aucune approximation.
• Mining récursif élégant : La décomposition par sous-arbres conditionnels est conceptuellement élégante et facile à paralléliser.

Limites

• Consommation mémoire sur données clairsemées : Quand les transactions partagent peu de préfixes, le FP-Tree est peu compressé et peut même dépasser la taille de la base originale.
• Construction du FP-Tree coûteuse : L’allocation récursive des nœuds et des chaînes de la table d’en-tête peut être lourde pour des millions d’items distincts.
• Sensibilité au min_support : Comme Apriori, un seuil mal calibré rend l’algorithme inutilisable (trop de résultats ou aucun résultat).
• Pas adapté aux données incrémentales : Le FP-Tree doit être reconstruit entièrement à l’ajout de nouvelles transactions. Des variantes comme FP-Stream existent pour le streaming.
• Pas de pondération par défaut : L’algorithme standard ne distingue pas les items par poids ou profit. Des extensions comme Weighted FP-Growth adressent ce point.

4 cas d’usage concrets

1. Market Basket Analysis (analyse de panier d’achat)

L’application historique du FP-Growth. Un supermarché ou un site e-commerce analyse les paniers d’achat pour identifier les produits souvent achetés ensemble. Les règles extraites alimentent directement les systèmes de recommandation (« Les clients qui ont acheté X ont aussi acheté Y »), le merchandising en rayon (placer les produits corrélés à proximité) et les campagnes promotionnelles ciblées (promotions croisées).

# Exemple de recommandation basée sur les règles
top_rules = rules.sort_values("lift", ascending=False).head(5)
for _, row in top_rules.iterrows():
    ante = ", ".join(row["antecedents"])
    cons = ", ".join(row["consequents"])
    print(f"Si un client achète {{{ante}}}, il a de fortes chances d'acheter {{{cons}}}"
          f" (lift={row['lift']:.2f})")

2. Diagnostic médical et pharmacovigilance

Dans le domaine de la santé, le FP-Growth est utilisé pour analyser les co-occurrences de symptômes, de diagnostics et de médicaments dans les dossiers patients. On peut ainsi identifier des combinaisons de symptômes qui signalent une pathologie spécifique, ou détecter des interactions médicamenteuses rares mais récurrentes. L’avantage majeur ici est la capacité à traiter des milliers de codes diagnostics (CIM-10) sans explosion combinatoire.

3. Détection d’intrusions en cybersécurité

Les logs système réseau génèrent des séquences d’événements qui peuvent être traitées comme des transactions. Le FP-Growth identifie des combinaisons d’événements récurrentes associées à des attaques connues. Par exemple, une séquence de port scanning + tentative de connexion SSH + élévation de privilège peut constituer un pattern fréquent dans les logs d’intrusion. Les règles extraites servent ensuite à enrichir les systèmes de détection (IDS/IPS) avec de nouvelles signatures comportementales.

4. Analyse de navigation web et personnalisation

Les sessions de navigation sur un site web peuvent être modélisées comme des transactions, où chaque page visitée est un item. Le FP-Growth révèle les parcours typiques des utilisateurs : quelles pages sont fréquemment visitées ensemble, quels enchaînements sont les plus courants. Ces informations permettent d’optimiser l’architecture de l’information, de créer des raccourcis contextuels, et de proposer du contenu personnalisé en fonction du parcours en cours de l’utilisateur.

Voir aussi

• Calcul des Sommes des Carrés des Diviseurs Unitaires en Python : Guide Complet et Code Optimisé
• Question d’Entretien: Conversion de Nombres Romains en Entier avec Python