L’Algorithme FP-Growth pour l’Extraction de Motifs Fréquents

Une approche efficace sans génération de candidats

Authors
Affiliation

Wilson Toussile1 2

ENSPY

1ENSPY, 2ESSFAR

Published

May 29, 2025

1 Introduction à FP-Growth

1.1 Qu’est-ce que FP-Growth ?

L’algorithme FP-Growth (pour Frequent Pattern Growth) est une méthode alternative et souvent plus efficace que l’algorithme Apriori pour l’extraction d’itemsets fréquents dans de grands ensembles de données transactionnelles. Développé par Han et al. en 2000, son objectif principal est de découvrir les combinaisons d’items qui apparaissent fréquemment ensemble, mais en évitant certaines des étapes les plus coûteuses de l’approche Apriori.

Au lieu de générer et de tester explicitement un grand nombre d’itemsets candidats, FP-Growth utilise une structure de données arborescente compacte, appelée FP-Tree, pour encoder les informations essentielles sur les fréquences des items. Cette approche permet de réduire considérablement l’espace de recherche et le nombre de balayages de la base de données.

1.2 Pourquoi FP-Growth ? Les Limites d’Apriori

Bien que l’algorithme Apriori soit fondamental et facile à comprendre, il présente des limitations notables, en particulier lorsque l’on travaille avec de grands volumes de données ou des seuils de support minimum (minsup) bas :

  1. Génération Coûteuse d’Ensembles Candidats :
    • Apriori génère des itemsets candidats de taille \(k\) en joignant des itemsets fréquents de taille \(k-1\). Si le nombre d’items ou la profondeur des motifs fréquents est élevé, le nombre de candidats peut devenir astronomique, consommant beaucoup de temps et de mémoire. Par exemple, pour générer des candidats de taille 3, il faut joindre les paires fréquentes ; pour la taille 4, les triplets fréquents, et ainsi de suite.
  2. Scans Multiples de la Base de Données :
    • Pour chaque niveau \(k\) d’itemsets candidats, Apriori doit scanner l’intégralité de la base de données pour compter le support de ces candidats. Pour une base de données volumineuse, ces lectures répétées du disque peuvent être très lentes.

Comment FP-Growth surmonte ces défis :

FP-Growth a été conçu pour pallier ces inconvénients :

  • Évite la Génération Explicite de Candidats : La principale innovation de FP-Growth est qu’il ne génère pas d’itemsets candidats de la même manière qu’Apriori. Au lieu de cela, il utilise une approche “diviser pour régner” pour décomposer le problème de minage en sous-problèmes plus petits.
  • Utilise une Structure de Données Compacte (FP-Tree) : L’algorithme compresse la base de données transactionnelle en une structure arborescente appelée FP-Tree. Cette structure retient les informations de fréquence des items et de leurs cooccurrences. Une fois l’FP-Tree construit (ce qui ne nécessite que deux scans de la base de données), les itemsets fréquents peuvent être extraits directement de cette structure sans avoir à rescanner la base de données originale.

1.3 L’Idée Centrale de FP-Growth

L’approche de FP-Growth peut être résumée en trois points clés :

  1. Compression de la Base de Données :
    • FP-Growth commence par scanner la base de données une première fois pour identifier tous les items individuels fréquents et leur support. Les items non fréquents sont écartés.
    • Lors d’un deuxième scan, chaque transaction est traitée : seuls les items fréquents y sont conservés et triés par ordre décroissant de leur support global. Ces transactions “nettoyées et triées” sont ensuite utilisées pour construire l’FP-Tree.
    • L’FP-Tree est une représentation compacte de la base de données, où les transactions partageant des préfixes communs sont fusionnées dans l’arbre, ce qui permet une compression significative. Chaque nœud de l’arbre représente un item et stocke un compteur indiquant combien de transactions passent par ce nœud.
  2. Approche “Diviser pour Régner” (Divide and Conquer) :
    • Une fois l’FP-Tree global construit, l’algorithme extrait les itemsets fréquents en examinant l’arbre de manière récursive.
    • Pour chaque item fréquent, FP-Growth construit une “base de patrons conditionnels” (l’ensemble des préfixes des chemins se terminant par cet item dans l’FP-Tree) puis un “FP-Tree conditionnel” à partir de cette base.
  3. Extraction Récursive des Motifs Fréquents :
    • Le processus de minage est appliqué récursivement sur ces FP-Trees conditionnels, qui sont plus petits et plus faciles à traiter.
    • Les itemsets fréquents sont ainsi “cultivés” (d’où le “Growth” dans le nom) à partir de ces sous-problèmes, sans jamais avoir à générer explicitement des candidats qui pourraient s’avérer non fréquents.

Cette méthode permet de réduire considérablement l’espace de recherche et d’améliorer l’efficacité, en particulier pour les jeux de données denses ou lorsque le support minimum est bas.

2 Concepts Clés de FP-Growth

Pour bien comprendre le fonctionnement de l’algorithme FP-Growth, il est essentiel de maîtriser quelques concepts et structures de données spécifiques qu’il utilise.

2.1 L’Arbre FP (FP-Tree - Frequent Pattern Tree)

L’Arbre FP (FP-Tree) est la pierre angulaire de l’algorithme FP-Growth.

  • Définition et Rôle : L’FP-Tree est une structure de données arborescente compacte conçue pour stocker les informations quantitatives sur les itemsets fréquents sans générer explicitement les candidats. Chaque chemin de la racine à un nœud représente un itemset, et les transactions partageant des préfixes communs partagent également la partie initiale de leur chemin dans l’arbre. Cela permet une compression significative des données transactionnelles. Le rôle principal de l’FP-Tree est de faciliter une extraction efficace des itemsets fréquents.

  • Structure d’un Nœud FP-Tree : Chaque nœud dans un FP-Tree (à l’exception de la racine, qui est généralement nulle ou représente un concept de base) est composé des éléments suivants :

    • Nom de l’item (Item-name) : L’item que le nœud représente (par exemple, “Pain”, “Lait”).
    • Compteur de support (Count/Frequency) : Un entier indiquant le nombre de transactions dont les chemins passent par ce nœud. Essentiellement, c’est le support de l’itemset représenté par le chemin de la racine jusqu’à ce nœud (en incluant ce nœud).
    • Lien vers le nœud parent (Parent link) : Un pointeur vers le nœud parent dans l’arbre.
    • Liens vers les nœuds enfants (Children links) : Une collection de pointeurs vers les nœuds enfants. Un nœud peut avoir plusieurs enfants, chacun représentant un item différent qui suit l’item du nœud courant dans une ou plusieurs transactions.
    • Lien de “node-link” (Node-link) : Un pointeur spécial qui relie ce nœud au prochain nœud dans l’FP-Tree ayant le même nom d’item. Ces liens forment des listes chaînées pour chaque item fréquent, facilitant la traversée de tous les nœuds d’un item spécifique.

  • Table d’En-tête (Header Table) : Associée à chaque FP-Tree, la table d’en-tête (parfois appelée “liste d’en-tête” ou “header list”) joue un rôle crucial. Elle contient une entrée pour chaque item fréquent unique présent dans les données. Chaque entrée de la table d’en-tête stocke :

    • Nom de l’item (Item-name) : L’item fréquent.
    • Support de l’item (Support count) : Le support total de cet item dans la base de données.
    • Pointeur de tête de liste (Head of node-link) : Un pointeur vers la première occurrence (le premier nœud) de cet item dans l’FP-Tree, via les “node-links”. Cela permet d’accéder rapidement à toutes les occurrences d’un item donné dans l’arbre.

    La table d’en-tête est généralement triée par ordre décroissant de support des items, ce qui est important pour l’efficacité de la construction de l’arbre et du processus de minage.

2.2 Base de Patrons Conditionnels (Conditional Pattern Base)

Lors de la phase d’extraction des motifs fréquents, FP-Growth utilise le concept de “base de patrons conditionnels”.

  • Définition : Pour un item donné P (ou un itemset suffixe), sa base de patrons conditionnels est un ensemble de “préfixes de chemins” (prefix paths) collectés à partir de l’FP-Tree. Plus précisément, pour chaque occurrence de P dans l’FP-Tree (accessible via la table d’en-tête et les node-links), on remonte le chemin vers la racine. Le chemin de la racine jusqu’au parent du nœud P constitue un préfixe. Chaque préfixe dans la base de patrons conditionnels est associé à un support, qui est le support du nœud P sur ce chemin particulier.

    Par exemple, si nous avons un chemin Racine -> A:5 -> B:3 -> P:2 dans l’FP-Tree, et que nous cherchons la base de patrons conditionnels pour P, alors {A, B} avec un support de 2 serait un des patrons (préfixes) dans cette base.

  • Utilité : La base de patrons conditionnels représente l’ensemble des transactions (ou parties de transactions) qui coexistent avec l’item P. Elle est utilisée comme “mini base de données” pour construire un FP-Tree conditionnel spécifique à P. Cela permet de décomposer le problème de minage : au lieu de chercher tous les motifs dans le grand FP-Tree global, on cherche les motifs se terminant par P dans un arbre beaucoup plus petit et spécifique.

2.3 Arbre FP Conditionnel (Conditional FP-Tree)

L’arbre FP conditionnel est une conséquence directe de la base de patrons conditionnels.

  • Définition : Un arbre FP conditionnel (ou P-conditional FP-Tree) est un FP-Tree construit à partir de la base de patrons conditionnels d’un item (ou itemset) P. La construction de cet arbre suit les mêmes principes que la construction de l’FP-Tree global :
    1. Calculer le support des items dans la base de patrons conditionnels de P.
    2. Éliminer les items non fréquents (par rapport au minsup et aux supports dans la base conditionnelle).
    3. Trier les items fréquents restants.
    4. Construire l’arbre en insérant chaque patron (préfixe) de la base conditionnelle.
  • Utilité : L’arbre FP conditionnel pour P contient toutes les informations nécessaires pour trouver les itemsets fréquents qui sont des super-ensembles de P (c’est-à-dire, les itemsets fréquents se terminant par P). Le processus de minage est ensuite appliqué récursivement sur cet arbre FP conditionnel. Si l’arbre FP conditionnel est vide ou ne contient qu’un seul chemin, le processus récursif s’arrête ou se simplifie pour cette branche.

Ces trois concepts – l’FP-Tree, la base de patrons conditionnels, et l’arbre FP conditionnel – sont interconnectés et forment le cœur de la stratégie “diviser pour régner” de l’algorithme FP-Growth. Ils permettent de décomposer le problème complexe de l’extraction de tous les itemsets fréquents en une série de sous-problèmes plus petits et plus gérables.

3 L’Algorithme FP-Growth : Pas à Pas

L’algorithme FP-Growth, contrairement à Apriori, évite la génération coûteuse d’ensembles candidats. Il opère principalement en deux phases distinctes : la construction d’une structure de données compacte appelée FP-Tree, suivie de l’extraction des motifs fréquents à partir de cet arbre.

3.1 Phase 1 : Construction de l’FP-Tree Global

L’objectif de cette première phase est de compresser la base de données transactionnelle en une structure FP-Tree. Cela se fait en deux scans de la base de données.

  1. Premier Scan de la Base de Données : Identification et Tri des Items Fréquents
    • a. Calcul du Support Individuel : Parcourir l’ensemble des transactions une première fois pour calculer le support de chaque item individuel. Le support d’un item est le nombre de transactions dans lesquelles il apparaît.
    • b. Identification des Items Fréquents : Comparer le support de chaque item au seuil de support minimum (minsup) défini par l’utilisateur.
      • Les items dont le support est supérieur ou égal à minsup sont considérés comme des items fréquents de taille 1.
      • Les items dont le support est inférieur à minsup sont éliminés car, en vertu de la propriété d’anti-monotonie (comme pour Apriori), aucun itemset plus grand les contenant ne pourra être fréquent.
    • c. Tri des Items Fréquents : Créer une liste, souvent appelée \(L\), contenant tous les items fréquents de taille 1, triés par ordre décroissant de leur support. En cas d’égalité de support, un critère secondaire comme l’ordre lexicographique (alphabétique) peut être utilisé pour assurer un ordre constant. Ce tri est crucial pour maximiser le partage de préfixes dans l’FP-Tree et donc sa compacité.
  2. Deuxième Scan de la Base de Données : Construction de l’FP-Tree
    • L’FP-Tree est initialisé avec un nœud racine (généralement null ou un symbole spécial). Une table d’en-tête est également créée.
    • Pour chaque transaction dans la base de données :
      • i. Filtrage et Tri de la Transaction :
        • Conserver uniquement les items fréquents (ceux présents dans la liste \(L\)) de la transaction courante.
        • Trier ces items fréquents selon l’ordre défini dans la liste \(L\) (ordre décroissant de support global).
      • ii. Insertion dans l’FP-Tree : Insérer la transaction filtrée et triée dans l’FP-Tree. Pour ce faire :
        • Commencer au nœud racine de l’FP-Tree.
        • Pour chaque item de la transaction triée (dans l’ordre) :
          • Vérifier si un enfant de la racine (ou du nœud courant) correspond à cet item.
          • Si oui, suivre ce chemin et incrémenter le compteur de support de ce nœud enfant de 1.
          • Si non, créer un nouveau nœud pour cet item, l’attacher comme enfant du nœud courant, et initialiser son compteur de support à 1.
          • Mettre à jour le “node-link” dans la table d’en-tête pour cet item afin qu’il pointe vers ce nouveau nœud (ou l’ajoute à la liste chaînée des nœuds de cet item).
        • Le nœud courant devient le nœud enfant qui vient d’être parcouru ou créé.

À la fin de ce deuxième scan, l’FP-Tree global est construit, et la table d’en-tête est remplie avec les items fréquents et les pointeurs vers leurs occurrences dans l’arbre.

3.2 Phase 2 : Extraction des Itemsets Fréquents à partir de l’FP-Tree (Processus Récursif)

Une fois l’FP-Tree global construit, l’algorithme extrait les itemsets fréquents en utilisant une approche “diviser pour régner”. Ce processus est généralement implémenté sous forme d’une fonction récursive, que nous pouvons appeler FP_growth(Tree, alpha) :

  • Tree : L’FP-Tree (ou FP-Tree conditionnel) à partir duquel miner les motifs.
  • alpha : L’itemset suffixe courant avec lequel les nouveaux motifs trouvés seront combinés. Initialement, alpha est vide (ou null).

Le processus de minage se déroule comme suit :

  1. Cas de Base de la Récursion :
    • Si Tree est vide, il n’y a rien à miner, donc on retourne.
    • Si Tree ne contient qu’un seul chemin (c’est-à-dire que chaque nœud a au plus un enfant, à l’exception de la racine), alors tous les itemsets formés par les combinaisons des items présents sur ce chemin, lorsqu’ils sont concaténés avec le suffixe alpha, sont des itemsets fréquents.
      • Pour chaque combinaison beta d’items sur ce chemin unique, l’itemset fréquent est beta U alpha.
      • Le support de cet itemset fréquent est le support minimum parmi les items de beta dans ce chemin unique.
      • Après avoir généré ces itemsets, on retourne.
  2. Cas Récursif (si Tree a plusieurs chemins) :
    • Pour chaque item a_i dans la table d’en-tête de Tree (traités généralement par ordre croissant de support, c’est-à-dire en commençant par le moins fréquent des items de la table d’en-tête actuelle) :
      • a. Générer un Nouvel Itemset Fréquent : Former un nouvel itemset fréquent Pattern = a_i U alpha. Le support de Pattern est le support de a_i tel qu’indiqué dans la table d’en-tête de Tree. Ajouter Pattern à la liste des itemsets fréquents découverts.
      • b. Construire la Base de Patrons Conditionnels de a_i :
        • Pour chaque occurrence du nœud a_i dans Tree (accessible via les node-links depuis la table d’en-tête), collecter le chemin préfixe. Le chemin préfixe est la séquence d’items allant de la racine de Tree jusqu’au parent du nœud a_i sur ce chemin particulier.
        • Le support associé à chaque chemin préfixe dans cette base est le support du nœud a_i sur ce chemin.
        • L’ensemble de ces chemins préfixes (avec leurs supports) forme la base de patrons conditionnels pour a_i.
      • c. Construire l’Arbre FP Conditionnel de a_i (Tree_Pattern) :
        • À partir de la base de patrons conditionnels de a_i, construire un nouvel FP-Tree, appelé l’arbre FP conditionnel de a_i (ou Tree_Pattern).
        • Lors de la construction de cet arbre conditionnel, seuls les items qui sont fréquents au sein de la base de patrons conditionnels (c’est-à-dire dont le support cumulé dans cette base est \(\ge\) minsup) sont conservés.
      • d. Appel Récursif : Si l’arbre FP conditionnel Tree_Pattern n’est pas vide, appeler récursivement la fonction de minage : FP_growth(Tree_Pattern, Pattern).

Ce processus récursif explore l’espace des itemsets fréquents de manière efficace. En construisant des FP-Trees conditionnels de plus en plus petits, l’algorithme se concentre sur des sous-ensembles de données pertinents pour chaque item, évitant ainsi la génération et le test de nombreux candidats non fréquents.

4 Exemple Détaillé de FP-Growth

Pour illustrer concrètement l’algorithme FP-Growth, nous allons reprendre le même ensemble de transactions que celui utilisé pour l’exemple de l’algorithme Apriori. Cela nous permettra de comparer les étapes et les résultats.

Données de Transactions :

ID Transaction Articles Achetés
T1 {Pain, Lait, Oeufs}
T2 {Pain, Beurre}
T3 {Lait, Oeufs, Beurre}
T4 {Pain, Lait, Beurre}
T5 {Pain, Lait, Oeufs, Beurre}

Paramètre : * Support Minimum (minsup) = 3 (Un itemset doit apparaître dans au moins 3 transactions pour être considéré comme fréquent).

4.1 Construction de l’FP-Tree Global

Étape 1.1 : Premier Scan de la Base de Données et Tri des Items Fréquents

  1. Calcul du Support Individuel :
    • Pain : 4
    • Lait : 4
    • Oeufs : 3
    • Beurre : 4
  2. Identification des Items Fréquents : Avec minsup = 3, tous les items sont fréquents.
  3. Tri des Items Fréquents (Liste \(L\)) : On trie les items fréquents par support décroissant. En cas d’égalité de support, on utilise l’ordre alphabétique (par exemple).
    • Pain (4), Lait (4), Beurre (4), Oeufs (3).
    • Pour un ordre déterministe avec égalité de support, choisissons : \(L = [(\text{Pain}:4), (\text{Lait}:4), (\text{Beurre}:4), (\text{Oeufs}:3)]\). (Note: l’ordre alphabétique pour les ex-aequo donnerait Beurre, Lait, Pain). Nous suivrons l’ordre Pain, Lait, Beurre pour la cohérence avec l’exemple Apriori si possible, mais le tri par support est la clé. Adoptons l’ordre de l’exemple Apriori pour les items de même support : Pain, Lait, Beurre. Donc, \(L = [(\text{Pain}:4), (\text{Lait}:4), (\text{Beurre}:4), (\text{Oeufs}:3)]\).

Étape 1.2 : Deuxième Scan et Construction de l’FP-Tree

  1. Filtrage et Tri des Transactions selon \(L\) :

    • T1: {Pain, Lait, Oeufs} \(\rightarrow\) (Pain, Lait, Oeufs)
    • T2: {Pain, Beurre} \(\rightarrow\) (Pain, Beurre)
    • T3: {Lait, Oeufs, Beurre} \(\rightarrow\) (Lait, Beurre, Oeufs)
    • T4: {Pain, Lait, Beurre} \(\rightarrow\) (Pain, Lait, Beurre)
    • T5: {Pain, Lait, Oeufs, Beurre} \(\rightarrow\) (Pain, Lait, Beurre, Oeufs)

  2. Construction de l’FP-Tree :

    • Initialiser un FP-Tree avec un nœud racine (null) et une table d’en-tête vide.
    • Insertion de T1 (Pain, Lait, Oeufs) : (null) –Pain:1–> (Lait:1) –Oeufs:1–>
    • Insertion de T2 (Pain, Beurre) : (null) –Pain:2 (incrémenté) –Beurre:1–>
    • Insertion de T3 (Lait, Beurre, Oeufs) : (null) –Lait:1 (nouvelle branche) –Beurre:1–> (Oeufs:1)–>
    • Insertion de T4 (Pain, Lait, Beurre) : (null) –Pain:3 (incrémenté) –Lait:2 (incrémenté) –Beurre:1–>
    • Insertion de T5 (Pain, Lait, Beurre, Oeufs) : (null) –Pain:4 (incrémenté) –Lait:3 (incrémenté) –Beurre:2 (incrémenté) –Oeufs:1–>

    Structure Finale de l’FP-Tree (représentation textuelle) :

    (null)
  |-- Pain:4
  |    |-- Lait:3
  |    |    |-- Oeufs:1  (Nœud nO1)
  |    |    +-- Beurre:2 (Nœud nB4)
  |    |         +-- Oeufs:1  (Nœud nO5)
  |    +-- Beurre:1 (Nœud nB2)
  +-- Lait:1 (Nœud nL3, branche distincte de la racine)
       +-- Beurre:1 (Nœud nB3)
            +-- Oeufs:1  (Nœud nO3)

    Table d’En-tête Finale (Item:Support, Tête de liste de nœuds) :

    • Oeufs:3, head \(\rightarrow\) nO5 \(\rightarrow\) nO3 \(\rightarrow\) nO1
    • Beurre:4, head \(\rightarrow\) nB4 \(\rightarrow\) nB2 \(\rightarrow\) nB3 (L’ordre des liens dépend de l’implémentation, l’important est de lister tous les nœuds)
    • Lait:4, head \(\rightarrow\) nL1 (associé à Pain:4->Lait:3) \(\rightarrow\) nL3
    • Pain:4, head \(\rightarrow\) nP1 (associé à Pain:4) (Note : nX sont des identifiants de nœuds pour la clarté. La table d’en-tête est triée par ordre inverse de \(L\) pour le minage, c.-à-d. Oeufs, puis Beurre, etc.)

4.2 Extraction des Itemsets Fréquents

On mine l’FP-Tree en commençant par l’item le moins fréquent de la table d’en-tête (selon l’ordre inverse de \(L\)) et en remontant. Suffixe initial \(\alpha = \emptyset\).

  1. Miner pour l’item “Oeufs” (support=3)
    • Itemset fréquent généré : {Oeufs} (support=3). Nouveau suffixe \(\alpha = \{\text{Oeufs}\}\).
    • Base de Patrons Conditionnels pour Oeufs (CPB_Oeufs) :
      • Chemin via nO1 (Pain:4 \(\rightarrow\) Lait:3 \(\rightarrow\) Oeufs:1) : Préfixe (Pain, Lait), support du nœud Oeufs = 1.
      • Chemin via nO3 (Lait:1 \(\rightarrow\) Beurre:1 \(\rightarrow\) Oeufs:1) : Préfixe (Lait, Beurre), support du nœud Oeufs = 1.
      • Chemin via nO5 (Pain:4 \(\rightarrow\) Lait:3 \(\rightarrow\) Beurre:2 \(\rightarrow\) Oeufs:1) : Préfixe (Pain, Lait, Beurre), support du nœud Oeufs = 1.
      • CPB_Oeufs = { (Pain, Lait):1, (Lait, Beurre):1, (Pain, Lait, Beurre):1 }
    • FP-Tree Conditionnel pour Oeufs (FPcond_Oeufs) :
      • Supports des items dans CPB_Oeufs : Lait (1+1+1=3), Pain (1+1=2), Beurre (1+1=2).
      • Items fréquents (avec minsup=3) dans CPB_Oeufs : {Lait:3}.
      • FPcond_Oeufs (trié par support) : (null) –Lait:3–>
    • Miner FPcond_Oeufs avec \(\alpha = \{\text{Oeufs}\}\) :
      • L’arbre a un seul chemin (Lait:3).
      • Item a_i = Lait. Itemset fréquent généré : `{Lait} {} = {}$ (support=3).
      • CPB pour Lait (dans FPcond_Oeufs) est vide. Fin de cette branche.
  2. Miner pour l’item “Beurre” (support=4)
    • Itemset fréquent généré : {Beurre} (support=4). Nouveau suffixe \(\alpha = \{\text{Beurre}\}\).
    • CPB_Beurre :
      • Chemin via nB4 (Pain:4 \(\rightarrow\) Lait:3 \(\rightarrow\) Beurre:2) : Préfixe (Pain, Lait), support du nœud Beurre = 2.
      • Chemin via nB2 (Pain:4 \(\rightarrow\) Beurre:1) : Préfixe (Pain), support du nœud Beurre = 1.
      • Chemin via nB3 (Lait:1 \(\rightarrow\) Beurre:1) : Préfixe (Lait), support du nœud Beurre = 1.
      • CPB_Beurre = { (Pain, Lait):2, (Pain):1, (Lait):1 }
    • FPcond_Beurre :
      • Supports des items dans CPB_Beurre : Pain (2+1=3), Lait (2+1=3).
      • Items fréquents : {Pain:3, Lait:3}. Triés (ex: Pain, Lait).
      • FPcond_Beurre (construit à partir des préfixes de CPB_Beurre) : (null) –Pain:3–> (Lait:2)–> (de (Pain,Lait):2 et (Pain):1) –Lait:1–> (de (Lait):1, si Lait est traité après Pain et n’est pas enfant de Pain) Structure plus précise: (null) –Pain:3–> (Lait:2) ; (null) –Lait:1 (si Lait est un item de tête séparé dans l’arbre conditionnel) Ou, si on insère (Pain,Lait):2 puis (Pain):1 puis (Lait):1 dans un arbre avec items [Pain, Lait]: (null) –Pain:3–> (Lait:2) –Lait:1–> (si Lait est un item de tête distinct) Correctement : (null) –Pain:3–> (Lait:2) ; (null) –Lait:1 (si Lait est un item de tête distinct) En fait, l’arbre conditionnel est : (null) –Pain:3–> (Lait:2) ; et une branche (null) –Lait:1 (si Lait est traité comme item de tête après Pain). Si l’ordre de la table d’en-tête de FPcond_Beurre est [Lait:3, Pain:3] (ordre alphabétique inverse pour le minage) : (null) –Lait:3–> (Pain:2)
    • Miner FPcond_Beurre avec \(\alpha = \{\text{Beurre}\}\) (supposons table d’en-tête de FPcond_Beurre: [Pain:3, Lait:3])
      • Pour a_i = Lait (support=3 dans FPcond_Beurre) : Itemset fréquent : `{Lait} {} = {}$ (support=3). CPB_Lait (pour \(\alpha=\{\text{Lait, Beurre}\}\)) à partir de FPcond_Beurre : {(Pain):2}. Pain (support=2) n’est pas fréquent. FPcond est vide.
      • Pour a_i = Pain (support=3 dans FPcond_Beurre) : Itemset fréquent : `{Pain} {} = {}$ (support=3). CPB_Pain (pour \(\alpha=\{\text{Pain, Beurre}\}\)) à partir de FPcond_Beurre est vide. FPcond est vide.
  3. Miner pour l’item “Lait” (support=4)
    • Itemset fréquent généré : {Lait} (support=4). Nouveau suffixe \(\alpha = \{\text{Lait}\}\).
    • CPB_Lait :
      • Chemin via nL1 (Pain:4 \(\rightarrow\) Lait:3) : Préfixe (Pain), support du nœud Lait = 3.
      • Chemin via nL3 (Lait:1) : Préfixe (), support du nœud Lait = 1.
      • CPB_Lait = { (Pain):3 } (le préfixe vide est ignoré pour la construction de l’arbre conditionnel).
    • FPcond_Lait :
      • Supports des items dans CPB_Lait : Pain (3).
      • Items fréquents : {Pain:3}.
      • FPcond_Lait : (null) –Pain:3–>
    • Miner FPcond_Lait avec \(\alpha = \{\text{Lait}\}\) :
      • L’arbre a un seul chemin (Pain:3).
      • Item a_i = Pain. Itemset fréquent généré : `{Pain} {} = {}$ (support=3).
      • CPB pour Pain (dans FPcond_Lait) est vide. Fin de cette branche.
  4. Miner pour l’item “Pain” (support=4)
    • Itemset fréquent généré : {Pain} (support=4). Nouveau suffixe \(\alpha = \{\text{Pain}\}\).
    • CPB_Pain :
      • Chemin via nP1 (Pain:4) : Préfixe (), support du nœud Pain = 4.
    • FPcond_Pain : Vide, car il n’y a pas d’items dans les préfixes. Fin de cette branche.

Itemsets Fréquents Trouvés par FP-Growth (avec minsup=3) : * {Oeufs} (support=3) * {Lait, Oeufs} (support=3) * {Beurre} (support=4) * {Lait, Beurre} (support=3) * {Pain, Beurre} (support=3) * {Lait} (support=4) * {Pain, Lait} (support=3) * {Pain} (support=4)

Ces résultats sont identiques à ceux obtenus avec l’algorithme Apriori (\(L_1\) et \(L_2\)), ce qui est attendu. Notamment, l’itemset {Pain, Lait, Beurre} n’est pas trouvé comme fréquent car son support réel est de 2, ce qui est inférieur à minsup=3. FP-Growth, comme Apriori, identifie correctement les mêmes ensembles d’items fréquents.

5 Implémentation de FP-Growth

Après avoir compris la théorie derrière FP-Growth, voyons comment l’implémenter en pratique. Nous nous concentrerons sur Python avec la bibliothèque mlxtend, qui offre une implémentation directe et efficace de FP-Growth.

5.1 Avec Python et mlxtend

La bibliothèque mlxtend (machine learning extensions) est un excellent outil pour l’extraction de motifs fréquents en Python. Elle fournit des implémentations des algorithmes Apriori et FP-Growth, ainsi que des fonctions pour générer des règles d’association.

Si vous ne l’avez pas encore installée, vous pouvez le faire avec pip :

# Importations nécessaires
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth, association_rules

# Données de transactions (reprendre l'exemple)
dataset = [['Pain', 'Lait', 'Oeufs'],
            ['Pain', 'Beurre'],
            ['Lait', 'Oeufs', 'Beurre'],
            ['Pain', 'Lait', 'Beurre'],
            ['Pain', 'Lait', 'Oeufs', 'Beurre']]

te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df_transactions = pd.DataFrame(te_ary, columns=te.columns_)

# Application de FP-Growth
min_support_val = 0.6 # (3/5 transactions)
frequent_itemsets_fp = fpgrowth(df_transactions, min_support=min_support_val, use_colnames=True)

print("--- Itemsets Fréquents (FP-Growth, minsup = 0.6) ---")
--- Itemsets Fréquents (FP-Growth, minsup = 0.6) ---
print(frequent_itemsets_fp)
   support        itemsets
0      0.8          (Pain)
1      0.8          (Lait)
2      0.6         (Oeufs)
3      0.8        (Beurre)
4      0.6    (Lait, Pain)
5      0.6   (Lait, Oeufs)
6      0.6  (Beurre, Pain)
7      0.6  (Beurre, Lait)
# Génération des règles d'association (identique à Apriori)
rules_fp = association_rules(frequent_itemsets_fp, metric="confidence", min_threshold=0.7)
print("\n--- Règles d'Association (FP-Growth, minconf = 0.7) ---")

--- Règles d'Association (FP-Growth, minconf = 0.7) ---
print(rules_fp[['antecedents', 'consequents', 'support', 'confidence', 'lift']])
  antecedents consequents  support  confidence    lift
0      (Lait)      (Pain)      0.6        0.75  0.9375
1      (Pain)      (Lait)      0.6        0.75  0.9375
2      (Lait)     (Oeufs)      0.6        0.75  1.2500
3     (Oeufs)      (Lait)      0.6        1.00  1.2500
4    (Beurre)      (Pain)      0.6        0.75  0.9375
5      (Pain)    (Beurre)      0.6        0.75  0.9375
6    (Beurre)      (Lait)      0.6        0.75  0.9375
7      (Lait)    (Beurre)      0.6        0.75  0.9375
  • Comparer les résultats avec ceux obtenus par Apriori sur le même exemple.

5.2 Avec R et arules (ou autres packages pertinents)

  • arules utilise Apriori par défaut. Vérifier si une option pour FP-Growth existe ou si un autre package est plus adapté (ex: rCBA qui peut utiliser des variantes).
  • Si arules ne propose pas FP-Growth directement, mentionner que l’accent est mis sur Apriori mais que des implémentations existent dans l’écosystème R.
library(arules)   

library(arulesViz)  

library(tidyverse)

library(fim4r)
Code 
# Data as transactions
data(Groceries)
transactions <- Groceries

# Find unique products in the data set
products <- itemLabels(transactions)

# View the unique products
products[1:10]
 [1] "frankfurter"       "sausage"           "liver loaf"       
 [4] "ham"               "meat"              "finished products"
 [7] "organic sausage"   "chicken"           "turkey"           
[10] "pork"
Code 
# Number of transactions
nrow(transactions)
[1] 9835
Code 
# Average basket size
size <- size(transactions)
mean(size)
[1] 4.409456
Code 
# Frequancies of products
itemFrequencyPlot(transactions, support = 0.05, cex.names = 0.8, col = "pink")

Code 
# Most frequent 30 products
itemFrequencyPlot(transactions, topN=30, col="pink")

Code 
# Drop product with frequency <= 0.005
transactions <- transactions[, itemFrequency(transactions)>0.005]

sort(itemFrequency(transactions, type="relative")) 
               liver loaf               curd cheese                   cleaner 
              0.005083884               0.005083884               0.005083884 
                   spices                       jam                    sauces 
              0.005185562               0.005388917               0.005490595 
                 softener            sparkling wine                   cereals 
              0.005490595               0.005592272               0.005693950 
              dental care            kitchen towels  female sanitary products 
              0.005795628               0.005998983               0.006100661 
        finished products                   vinegar                     soups 
              0.006507372               0.006507372               0.006812405 
                 zwieback                   popcorn            instant coffee 
              0.006914082               0.007219115               0.007422471 
                     rice        liquor (appetizer)     Instant food products 
              0.007625826               0.007930859               0.008032537 
                   turkey    house keeping products    frozen potato products 
              0.008134215               0.008337570               0.008439248 
         specialty cheese                  dog food                   candles 
              0.008540925               0.008540925               0.008947636 
            sweet spreads     chocolate marshmallow                mayonnaise 
              0.009049314               0.009049314               0.009150991 
               photo/film                  pet care            condensed milk 
              0.009252669               0.009456024               0.010269446 
           roll products             flower (seeds)              dish cleaner 
              0.010269446               0.010371124               0.010472801 
           frozen dessert                      salt         canned vegetables 
              0.010777834               0.010777834               0.010777834 
                   liquor             spread cheese           cling film/bags 
              0.011082867               0.011184545               0.011387900 
              frozen fish                   mustard packaged fruit/vegetables 
              0.011692933               0.011997966               0.013014743 
                 cake bar         seasonal products                     pasta 
              0.013218099               0.014234875               0.015048297 
              canned fish                     herbs          processed cheese 
              0.015048297               0.016268429               0.016573462 
              soft cheese                pot plants                     flour 
              0.017081851               0.017285206               0.017386884 
                   dishes       semi-finished bread             baking powder 
              0.017590239               0.017691917               0.017691917 
       pickled vegetables                white wine            red/blush wine 
              0.017895272               0.019013726               0.019217082 
                detergent               chewing gum                    grapes 
              0.019217082               0.021047280               0.022369090 
                 cat food             sliced cheese               hard cheese 
              0.023284189               0.024504321               0.024504321 
                ice cream                      meat                       ham 
              0.025012710               0.025826131               0.026029487 
                beverages             specialty bar               butter milk 
              0.026029487               0.027351296               0.027961362 
                      oil              frozen meals           misc. beverages 
              0.028063040               0.028368073               0.028368073 
                    candy       specialty chocolate                    onions 
              0.029893238               0.030401627               0.031011693 
         hygiene articles            hamburger meat                   berries 
              0.032943569               0.033248602               0.033248602 
                 UHT-milk                     sugar                   dessert 
              0.033451957               0.033858668               0.037112354 
 long life bakery product               salty snack                   waffles 
              0.037417387               0.037824098               0.038434164 
            cream cheese                white bread                   chicken 
              0.039654296               0.042094560               0.042907982 
        frozen vegetables                 chocolate                   napkins 
              0.048093543               0.049618709               0.052364006 
                     beef                      curd                    butter 
              0.052465684               0.053279105               0.055414337 
                     pork                    coffee                 margarine 
              0.057651246               0.058057956               0.058566345 
              frankfurter             domestic eggs               brown bread 
              0.058973055               0.063446873               0.064870361 
       whipped/sour cream     fruit/vegetable juice                 pip fruit 
              0.071682766               0.072292832               0.075648195 
              canned beer                newspapers              bottled beer 
              0.077681749               0.079816980               0.080528724 
             citrus fruit                    pastry                   sausage 
              0.082765633               0.088967972               0.093950178 
            shopping bags            tropical fruit           root vegetables 
              0.098525674               0.104931368               0.108998475 
            bottled water                    yogurt                      soda 
              0.110523640               0.139501779               0.174377224 
               rolls/buns          other vegetables                whole milk 
              0.183934926               0.193492628               0.255516014
Code 
# apriori
association_rules <- apriori(transactions, parameter = list(support = 0.01, confidence = 0.25, minlen = 2))
Apriori

Parameter specification:
 confidence minval smax arem  aval originalSupport maxtime support minlen
       0.25    0.1    1 none FALSE            TRUE       5    0.01      2
 maxlen target  ext
     10  rules TRUE

Algorithmic control:
 filter tree heap memopt load sort verbose
    0.1 TRUE TRUE  FALSE TRUE    2    TRUE

Absolute minimum support count: 98 

set item appearances ...[0 item(s)] done [0.00s].
set transactions ...[120 item(s), 9835 transaction(s)] done [0.00s].
sorting and recoding items ... [88 item(s)] done [0.00s].
creating transaction tree ... done [0.00s].
checking subsets of size 1 2 3 4 done [0.00s].
writing ... [170 rule(s)] done [0.00s].
creating S4 object  ... done [0.00s].
Code 
plot(association_rules, measure=c("support", "confidence"), shading="lift",col="#FF66CC")

Code 
fpgrowth <- fim4r(transactions, method = "fpgrowth", target = "rules", supp = 0.01, conf = 0.25)
fim4r.fpgrowth 

Parameter specification:
 supp conf target report
    1   25  rules    scl

Data size: 9835 transactions and 120 items 
Result: 171 rules
Code 
summary(fpgrowth)
set of 171 rules

rule length distribution (lhs + rhs):sizes
 1  2  3 
 1 96 74 

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  1.000   2.000   2.000   2.427   3.000   3.000 

summary of quality measures:
    support          confidence          lift            count       
 Min.   :0.01007   Min.   :0.2517   Min.   :0.9932   Min.   :  99.0  
 1st Qu.:0.01159   1st Qu.:0.2965   1st Qu.:1.5175   1st Qu.: 114.0  
 Median :0.01454   Median :0.3582   Median :1.7716   Median : 143.0  
 Mean   :0.01961   Mean   :0.3697   Mean   :1.8695   Mean   : 192.8  
 3rd Qu.:0.02115   3rd Qu.:0.4252   3rd Qu.:2.1412   3rd Qu.: 208.0  
 Max.   :0.25552   Max.   :0.5862   Max.   :3.2950   Max.   :2513.0
Code 
plot(fpgrowth, measure=c("support", "confidence"), shading="lift",col="#FF66CC")

Code 
milk.rules <- sort(subset(fpgrowth, subset = rhs %in% "whole milk"), by = "confidence")
inspect(milk.rules)
     lhs                           rhs             support confidence      lift count
[1]  {curd,                                                                          
      yogurt}                   => {whole milk} 0.01006609  0.5823529 2.2791250    99
[2]  {other vegetables,                                                              
      butter}                   => {whole milk} 0.01148958  0.5736041 2.2448850   113
[3]  {tropical fruit,                                                                
      root vegetables}          => {whole milk} 0.01199797  0.5700483 2.2309690   118
[4]  {root vegetables,                                                               
      yogurt}                   => {whole milk} 0.01453991  0.5629921 2.2033536   143
[5]  {other vegetables,                                                              
      domestic eggs}            => {whole milk} 0.01230300  0.5525114 2.1623358   121
[6]  {yogurt,                                                                        
      whipped/sour cream}       => {whole milk} 0.01087951  0.5245098 2.0527473   107
[7]  {root vegetables,                                                               
      rolls/buns}               => {whole milk} 0.01270971  0.5230126 2.0468876   125
[8]  {pip fruit,                                                                     
      other vegetables}         => {whole milk} 0.01352313  0.5175097 2.0253514   133
[9]  {tropical fruit,                                                                
      yogurt}                   => {whole milk} 0.01514997  0.5173611 2.0247698   149
[10] {other vegetables,                                                              
      yogurt}                   => {whole milk} 0.02226741  0.5128806 2.0072345   219
[11] {other vegetables,                                                              
      whipped/sour cream}       => {whole milk} 0.01464159  0.5070423 1.9843854   144
[12] {other vegetables,                                                              
      fruit/vegetable juice}    => {whole milk} 0.01047280  0.4975845 1.9473713   102
[13] {butter}                   => {whole milk} 0.02755465  0.4972477 1.9460530   271
[14] {curd}                     => {whole milk} 0.02613116  0.4904580 1.9194805   257
[15] {root vegetables,                                                               
      other vegetables}         => {whole milk} 0.02318251  0.4892704 1.9148326   228
[16] {tropical fruit,                                                                
      other vegetables}         => {whole milk} 0.01708185  0.4759207 1.8625865   168
[17] {citrus fruit,                                                                  
      yogurt}                   => {whole milk} 0.01026945  0.4741784 1.8557678   101
[18] {domestic eggs}            => {whole milk} 0.02999492  0.4727564 1.8502027   295
[19] {pork,                                                                          
      other vegetables}         => {whole milk} 0.01016777  0.4694836 1.8373939    99
[20] {other vegetables,                                                              
      pastry}                   => {whole milk} 0.01057448  0.4684685 1.8334212   104
[21] {yogurt,                                                                        
      rolls/buns}               => {whole milk} 0.01555669  0.4526627 1.7715630   153
[22] {citrus fruit,                                                                  
      other vegetables}         => {whole milk} 0.01301474  0.4507042 1.7638982   128
[23] {whipped/sour cream}       => {whole milk} 0.03223183  0.4496454 1.7597542   317
[24] {root vegetables}          => {whole milk} 0.04890696  0.4486940 1.7560310   481
[25] {tropical fruit,                                                                
      rolls/buns}               => {whole milk} 0.01098119  0.4462810 1.7465872   108
[26] {sugar}                    => {whole milk} 0.01504830  0.4444444 1.7393996   148
[27] {hamburger meat}           => {whole milk} 0.01474326  0.4434251 1.7354101   145
[28] {ham}                      => {whole milk} 0.01148958  0.4414062 1.7275091   113
[29] {sliced cheese}            => {whole milk} 0.01077783  0.4398340 1.7213560   105
[30] {other vegetables,                                                              
      bottled water}            => {whole milk} 0.01077783  0.4344262 1.7001918   105
[31] {other vegetables,                                                              
      soda}                     => {whole milk} 0.01392984  0.4254658 1.6651240   137
[32] {frozen vegetables}        => {whole milk} 0.02043721  0.4249471 1.6630940   201
[33] {other vegetables,                                                              
      rolls/buns}               => {whole milk} 0.01789527  0.4200477 1.6439194   176
[34] {cream cheese }            => {whole milk} 0.01647178  0.4153846 1.6256696   162
[35] {butter milk}              => {whole milk} 0.01159126  0.4145455 1.6223854   114
[36] {margarine}                => {whole milk} 0.02419929  0.4131944 1.6170980   238
[37] {hard cheese}              => {whole milk} 0.01006609  0.4107884 1.6076815    99
[38] {chicken}                  => {whole milk} 0.01759024  0.4099526 1.6044106   173
[39] {white bread}              => {whole milk} 0.01708185  0.4057971 1.5881474   168
[40] {beef}                     => {whole milk} 0.02125064  0.4050388 1.5851795   209
[41] {tropical fruit}           => {whole milk} 0.04229792  0.4031008 1.5775950   416
[42] {oil}                      => {whole milk} 0.01128622  0.4021739 1.5739675   111
[43] {yogurt}                   => {whole milk} 0.05602440  0.4016035 1.5717351   551
[44] {pip fruit}                => {whole milk} 0.03009659  0.3978495 1.5570432   296
[45] {onions}                   => {whole milk} 0.01209964  0.3901639 1.5269647   119
[46] {hygiene articles}         => {whole milk} 0.01281139  0.3888889 1.5219746   126
[47] {brown bread}              => {whole milk} 0.02521607  0.3887147 1.5212930   248
[48] {other vegetables}         => {whole milk} 0.07483477  0.3867578 1.5136341   736
[49] {pork}                     => {whole milk} 0.02216573  0.3844797 1.5047187   218
[50] {yogurt,                                                                        
      soda}                     => {whole milk} 0.01047280  0.3828996 1.4985348   102
[51] {sausage,                                                                       
      other vegetables}         => {whole milk} 0.01016777  0.3773585 1.4768487    99
[52] {napkins}                  => {whole milk} 0.01972547  0.3766990 1.4742678   193
[53] {pastry}                   => {whole milk} 0.03324860  0.3737143 1.4625865   327
[54] {dessert}                  => {whole milk} 0.01372649  0.3698630 1.4475140   135
[55] {citrus fruit}             => {whole milk} 0.03050330  0.3685504 1.4423768   300
[56] {fruit/vegetable juice}    => {whole milk} 0.02663955  0.3684951 1.4421604   262
[57] {long life bakery product} => {whole milk} 0.01352313  0.3614130 1.4144438   133
[58] {berries}                  => {whole milk} 0.01179461  0.3547401 1.3883281   116
[59] {frankfurter}              => {whole milk} 0.02053889  0.3482759 1.3630295   202
[60] {newspapers}               => {whole milk} 0.02735130  0.3426752 1.3411103   269
[61] {chocolate}                => {whole milk} 0.01667514  0.3360656 1.3152427   164
[62] {waffles}                  => {whole milk} 0.01270971  0.3306878 1.2941961   125
[63] {coffee}                   => {whole milk} 0.01870869  0.3222417 1.2611408   184
[64] {sausage}                  => {whole milk} 0.02989324  0.3181818 1.2452520   294
[65] {bottled water}            => {whole milk} 0.03436706  0.3109476 1.2169396   337
[66] {rolls/buns}               => {whole milk} 0.05663447  0.3079049 1.2050318   557
[67] {salty snack}              => {whole milk} 0.01118454  0.2956989 1.1572618   110
[68] {}                         => {whole milk} 0.25551601  0.2555160 1.0000000  2513
[69] {bottled beer}             => {whole milk} 0.02043721  0.2537879 0.9932367   201
Code 
plot(milk.rules,method="graph",shading="lift",col="#FF66CC")

Code 
yogurt.rules <- sort(subset(fpgrowth, subset = rhs %in% "yogurt"), by = "confidence")
inspect(yogurt.rules)
     lhs                                       rhs      support    confidence
[1]  {whole milk, curd}                     => {yogurt} 0.01006609 0.3852140 
[2]  {tropical fruit, whole milk}           => {yogurt} 0.01514997 0.3581731 
[3]  {other vegetables, whipped/sour cream} => {yogurt} 0.01016777 0.3521127 
[4]  {tropical fruit, other vegetables}     => {yogurt} 0.01230300 0.3427762 
[5]  {whole milk, whipped/sour cream}       => {yogurt} 0.01087951 0.3375394 
[6]  {citrus fruit, whole milk}             => {yogurt} 0.01026945 0.3366667 
[7]  {curd}                                 => {yogurt} 0.01728521 0.3244275 
[8]  {berries}                              => {yogurt} 0.01057448 0.3180428 
[9]  {cream cheese }                        => {yogurt} 0.01240468 0.3128205 
[10] {other vegetables, whole milk}         => {yogurt} 0.02226741 0.2975543 
[11] {root vegetables, whole milk}          => {yogurt} 0.01453991 0.2972973 
[12] {whipped/sour cream}                   => {yogurt} 0.02074225 0.2893617 
[13] {tropical fruit}                       => {yogurt} 0.02928317 0.2790698 
[14] {whole milk, rolls/buns}               => {yogurt} 0.01555669 0.2746858 
[15] {root vegetables, other vegetables}    => {yogurt} 0.01291307 0.2725322 
[16] {other vegetables, rolls/buns}         => {yogurt} 0.01148958 0.2696897 
[17] {butter}                               => {yogurt} 0.01464159 0.2642202 
[18] {citrus fruit}                         => {yogurt} 0.02165735 0.2616708 
[19] {whole milk, soda}                     => {yogurt} 0.01047280 0.2614213 
[20] {fruit/vegetable juice}                => {yogurt} 0.01870869 0.2587904 
[21] {frozen vegetables}                    => {yogurt} 0.01240468 0.2579281 
     lift     count
[1]  2.761356  99  
[2]  2.567516 149  
[3]  2.524073  99  
[4]  2.457146 121  
[5]  2.419607 107  
[6]  2.413350 101  
[7]  2.325615 170  
[8]  2.279848 104  
[9]  2.242412 122  
[10] 2.132979 219  
[11] 2.131136 143  
[12] 2.074251 204  
[13] 2.000475 288  
[14] 1.969049 153  
[15] 1.953611 127  
[16] 1.933235 113  
[17] 1.894027 144  
[18] 1.875752 213  
[19] 1.873964 102  
[20] 1.855105 184  
[21] 1.848924 122
Code 
plot(yogurt.rules,method="graph",shading="lift",col="#FF66CC")

Code 
plot(fpgrowth, method = "graph", measure = "lift", shading = "confidence", engine = "htmlwidget", network = TRUE, itemCol="pink", max = 200)
Available control parameters (with default values):
itemCol  =  #CBD2FC
nodeCol  =  c("#EE0000", "#EE0303", "#EE0606", "#EE0909", "#EE0C0C", "#EE0F0F", "#EE1212", "#EE1515", "#EE1818", "#EE1B1B", "#EE1E1E", "#EE2222", "#EE2525", "#EE2828", "#EE2B2B", "#EE2E2E", "#EE3131", "#EE3434", "#EE3737", "#EE3A3A", "#EE3D3D", "#EE4040", "#EE4444", "#EE4747", "#EE4A4A", "#EE4D4D", "#EE5050", "#EE5353", "#EE5656", "#EE5959", "#EE5C5C", "#EE5F5F", "#EE6262", "#EE6666", "#EE6969", "#EE6C6C", "#EE6F6F", "#EE7272", "#EE7575", "#EE7878", "#EE7B7B", "#EE7E7E", "#EE8181", "#EE8484", "#EE8888", "#EE8B8B",  "#EE8E8E", "#EE9191", "#EE9494", "#EE9797", "#EE9999", "#EE9B9B", "#EE9D9D", "#EE9F9F", "#EEA0A0", "#EEA2A2", "#EEA4A4", "#EEA5A5", "#EEA7A7", "#EEA9A9", "#EEABAB", "#EEACAC", "#EEAEAE", "#EEB0B0", "#EEB1B1", "#EEB3B3", "#EEB5B5", "#EEB7B7", "#EEB8B8", "#EEBABA", "#EEBCBC", "#EEBDBD", "#EEBFBF", "#EEC1C1", "#EEC3C3", "#EEC4C4", "#EEC6C6", "#EEC8C8", "#EEC9C9", "#EECBCB", "#EECDCD", "#EECFCF", "#EED0D0", "#EED2D2", "#EED4D4", "#EED5D5", "#EED7D7", "#EED9D9", "#EEDBDB", "#EEDCDC", "#EEDEDE", "#EEE0E0",  "#EEE1E1", "#EEE3E3", "#EEE5E5", "#EEE7E7", "#EEE8E8", "#EEEAEA", "#EEECEC", "#EEEEEE")
precision    =  3
igraphLayout     =  layout_nicely
interactive  =  TRUE
engine   =  visNetwork
max  =  100
selection_menu   =  TRUE
degree_highlight     =  1
verbose  =  FALSE
Code 
# Si une implémentation directe de FP-Growth est disponible dans un package courant :
# Exemple (hypothétique si arules ne le fait pas directement)
transactions_list <- list(
   c("Pain", "Lait", "Oeufs"),
   c("Pain", "Beurre"),
   c("Lait", "Oeufs", "Beurre"),
   c("Pain", "Lait", "Beurre"),
   c("Pain", "Lait", "Oeufs", "Beurre")
 )
 transactions <- as(transactions_list, "transactions")

# Supposons une fonction fpgrowth_function
frequent_itemsets_fp_r <- fim4r(transactions, method = "fpgrowth", support = 0.6)
fim4r.fpgrowth 

Parameter specification:
 supp conf   target report
   60   80 frequent    scl

Data size: 5 transactions and 4 items 
Result: 9 itemsets
Code 
inspect(frequent_itemsets_fp_r)
    items          support count
[1] {Lait}         0.8     4    
[2] {Lait, Pain}   0.6     3    
[3] {Pain}         0.8     4    
[4] {Beurre, Lait} 0.6     3    
[5] {Beurre, Pain} 0.6     3    
[6] {Beurre}       0.8     4    
[7] {Lait, Oeufs}  0.6     3    
[8] {Oeufs}        0.6     3    
[9] {}             1.0     5
Code 
plot(frequent_itemsets_fp_r, method = "graph", measure = "lift", shading = "confidence", engine = "htmlwidget", network = TRUE, itemCol="pink", max = 200)
Available control parameters (with default values):
itemCol  =  #CBD2FC
nodeCol  =  c("#EE0000", "#EE0303", "#EE0606", "#EE0909", "#EE0C0C", "#EE0F0F", "#EE1212", "#EE1515", "#EE1818", "#EE1B1B", "#EE1E1E", "#EE2222", "#EE2525", "#EE2828", "#EE2B2B", "#EE2E2E", "#EE3131", "#EE3434", "#EE3737", "#EE3A3A", "#EE3D3D", "#EE4040", "#EE4444", "#EE4747", "#EE4A4A", "#EE4D4D", "#EE5050", "#EE5353", "#EE5656", "#EE5959", "#EE5C5C", "#EE5F5F", "#EE6262", "#EE6666", "#EE6969", "#EE6C6C", "#EE6F6F", "#EE7272", "#EE7575", "#EE7878", "#EE7B7B", "#EE7E7E", "#EE8181", "#EE8484", "#EE8888", "#EE8B8B",  "#EE8E8E", "#EE9191", "#EE9494", "#EE9797", "#EE9999", "#EE9B9B", "#EE9D9D", "#EE9F9F", "#EEA0A0", "#EEA2A2", "#EEA4A4", "#EEA5A5", "#EEA7A7", "#EEA9A9", "#EEABAB", "#EEACAC", "#EEAEAE", "#EEB0B0", "#EEB1B1", "#EEB3B3", "#EEB5B5", "#EEB7B7", "#EEB8B8", "#EEBABA", "#EEBCBC", "#EEBDBD", "#EEBFBF", "#EEC1C1", "#EEC3C3", "#EEC4C4", "#EEC6C6", "#EEC8C8", "#EEC9C9", "#EECBCB", "#EECDCD", "#EECFCF", "#EED0D0", "#EED2D2", "#EED4D4", "#EED5D5", "#EED7D7", "#EED9D9", "#EEDBDB", "#EEDCDC", "#EEDEDE", "#EEE0E0",  "#EEE1E1", "#EEE3E3", "#EEE5E5", "#EEE7E7", "#EEE8E8", "#EEEAEA", "#EEECEC", "#EEEEEE")
precision    =  3
igraphLayout     =  layout_nicely
interactive  =  TRUE
engine   =  visNetwork
max  =  100
selection_menu   =  TRUE
degree_highlight     =  1
verbose  =  FALSE

6 Comparaison Détaillée : Apriori vs. FP-Growth

Caractéristique Apriori FP-Growth
Approche Principale Génération et Test (Breadth-First) Diviser pour Régner (Depth-First sur l’FP-Tree)
Génération Candidats Oui, explicite et potentiellement coûteuse Non, implicite via la construction de l’FP-Tree
Scans Base Données k scans (où k est la taille max. itemset) 2 scans pour FP-Tree, puis opérations en mémoire
Structure Données Pas de structure de données complexe dédiée FP-Tree, Table d’En-tête
Vitesse Plus lent, surtout si minsup bas ou données denses Généralement plus rapide dans ces cas
Utilisation Mémoire Principalement pour les candidats \(C_k\) Peut être élevée pour l’FP-Tree (données sparse)
Complexité Implém. Relativement plus simple à implémenter Plus complexe à implémenter (surtout la partie minage)
Adapté pour… Données sparse, minsup élevé Données denses, minsup bas

7 Quand Choisir FP-Growth ?

  • Lorsque la performance est critique et qu’Apriori est trop lent.
  • Pour les jeux de données denses où de nombreux items apparaissent ensemble.
  • Lorsque le seuil de support minimum (minsup) doit être relativement bas.
  • Si la génération de candidats d’Apriori devient un goulot d’étranglement.
  • Il est souvent bon de l’essayer en parallèle ou comme alternative à Apriori pour comparer les performances sur un jeu de données spécifique.

8 Exercices sur FP-Growth

Exercise 1 (Construction Manuelle d’un FP-Tree) Considérez le jeu de données transactionnelles suivant :

ID Transaction Articles Achetés
T1 {A, B, D}
T2 {B, C, E}
T3 {A, B, C, E}
T4 {A, B, E}

Paramètre : * Support Minimum (minsup) = 2

Tâches :

  1. Calcul des Supports et Tri des Items Fréquents :
    • Calculez le support de chaque item individuel.
    • Identifiez les items fréquents (ceux dont le support est \(\ge\) minsup).
    • Créez la liste \(L\) des items fréquents, triée par ordre décroissant de support. En cas d’égalité de support, utilisez l’ordre alphabétique.
  2. Construction de l’FP-Tree :
    • Pour chaque transaction (après l’avoir filtrée pour ne garder que les items fréquents et les avoir triés selon l’ordre de \(L\)) :
      • Montrez l’état de l’FP-Tree après l’insertion de cette transaction. Décrivez clairement quels nœuds sont créés ou mis à jour (incrémentation du compteur).
    • Dessinez l’FP-Tree final après l’insertion de toutes les transactions.
  3. Table d’En-tête Finale :
    • Présentez la table d’en-tête finale associée à l’FP-Tree construit. Pour chaque item fréquent, indiquez son support et le pointeur vers la première occurrence de cet item dans l’arbre (vous pouvez nommer les nœuds pour plus de clarté si besoin).

Exercise 2 (Extraction Manuelle à partir d’un FP-Tree Donné) Considérez l’FP-Tree suivant et sa table d’en-tête. Le support minimum (minsup) utilisé pour sa construction et pour l’extraction est de 2.

FP-Tree :

(null)
  |-- A:4
  |    |-- B:3  (nB1)
  |    |    +-- C:1  (nC1)
  |    |    +-- D:1  (nD1)
  |    +-- C:1  (nC2)
  +-- B:2  (nB2)
       +-- E:2  (nE1)

Table d’En-tête (Item:Support, Tête de liste de nœuds) : (Triée par support croissant pour le minage)

  • D:1, head \(\rightarrow\) nD1
  • E:2, head \(\rightarrow\) nE1
  • C:2, head \(\rightarrow\) nC1 \(\rightarrow\) nC2
  • B:5, head \(\rightarrow\) nB1 \(\rightarrow\) nB2
  • A:4, head \(\rightarrow\) (Nœud A:4 directement sous la racine)

Note : Pour cet exercice, nous allons ignorer l’item ‘D’ car son support (1) est inférieur au minsup (2). Nous commencerons donc le minage à partir de ‘E’.

Tâches :

En utilisant le support minimum minsup = 2 :

  1. Miner pour l’item “E” :
    • Générez l’itemset fréquent se terminant par “E”.
    • Construisez la base de patrons conditionnels pour “E” (CPB_E).
    • Construisez l’arbre FP conditionnel pour “E” (FPcond_E).
    • Extrayez les itemsets fréquents de FPcond_E en combinaison avec “E”.
  2. Miner pour l’item “C” :
    • Générez l’itemset fréquent se terminant par “C”.
    • Construisez la base de patrons conditionnels pour “C” (CPB_C).
    • Construisez l’arbre FP conditionnel pour “C” (FPcond_C).
    • Extrayez les itemsets fréquents de FPcond_C en combinaison avec “C”.
  3. Continuer le processus pour les items restants dans la table d’en-tête (“B”, puis “A”) en respectant le minsup = 2. Pour chaque item :
    • Générez l’itemset fréquent.
    • Construisez sa base de patrons conditionnels.
    • Construisez son arbre FP conditionnel (s’il y a lieu).
    • Extrayez les itemsets fréquents supplémentaires.
  4. Lister tous les itemsets fréquents trouvés avec leur support.

Exercise 3 (Implémentation et Comparaison) Contexte : Pour cet exercice, utilisez le jeu de données de l’exemple détaillé présenté dans la section “Exemple Détaillé de FP-Growth” de ce document (celui avec 5 transactions : T1={Pain, Lait, Oeufs}, T2={Pain, Beurre}, etc.).

  • Support Minimum (minsup) = 0.6 (ce qui correspond à 3 transactions sur 5).
  • Confiance Minimum (minconf) = 0.7.

Tâches Python (mlxtend) :

  1. Préparation des Données :
    • Reprenez le dataset Python (liste de listes) fourni dans la section “Implémentation de FP-Growth avec Python et mlxtend”.
    • Utilisez TransactionEncoder pour le transformer en un DataFrame binaire (one-hot encoded) adapté à mlxtend.
  2. Application de FP-Growth :
    • Utilisez la fonction fpgrowth de mlxtend pour trouver les itemsets fréquents avec min_support = 0.6. Assurez-vous d’utiliser use_colnames=True.
    • Affichez les itemsets fréquents trouvés et leur support.
  3. Génération des Règles d’Association :
    • À partir des itemsets fréquents obtenus, utilisez la fonction association_rules pour générer les règles d’association. Utilisez metric="confidence" et min_threshold=0.7.
    • Affichez les règles d’association (incluant antecedents, consequents, support, confiance, et lift).
  4. Comparaison avec Apriori (via mlxtend) :
    • Sur le même DataFrame binaire, appliquez l’algorithme Apriori en utilisant la fonction apriori de mlxtend avec min_support = 0.6 et use_colnames=True.
    • Générez également les règles d’association à partir des itemsets fréquents d’Apriori avec min_threshold=0.7.
    • Comparez les itemsets fréquents et les règles d’association obtenus par FP-Growth et Apriori. Sont-ils identiques ?
  5. (Optionnel) Comparaison de Performance (sur le même petit dataset) :
    • Dans un environnement Jupyter Notebook ou IPython, utilisez la commande magique %timeit pour mesurer et comparer le temps d’exécution de fpgrowth() et apriori() pour l’extraction des itemsets fréquents sur ce petit jeu de données.
    • %timeit fpgrowth(df_transactions, min_support=0.6, use_colnames=True)
    • %timeit apriori(df_transactions, min_support=0.6, use_colnames=True)
    • Commentez les résultats. Les différences sont-elles significatives pour cette taille de données ? À quoi vous attendriez-vous sur un jeu de données beaucoup plus volumineux ?

Tâches R (fim4r et arules) :

  1. Préparation des Données :
    • Créez un objet transactions en R à partir du même jeu de données (les 5 transactions). Vous pouvez le faire en créant une liste de listes, puis en la convertissant avec as(..., "transactions").
  2. Application de FP-Growth (fim4r) :
    • Utilisez la fonction fim4r avec method = "fpgrowth" et target = "frequent itemsets". Spécifiez supp = 0.6 (correspondant à 60% de support).
    • Affichez les itemsets fréquents trouvés en utilisant inspect().
  3. Génération des Règles d’Association (fim4r) :
    • Utilisez fim4r avec method = "fpgrowth" et target = "rules". Spécifiez supp = 0.6 et conf = 0.7.
    • Affichez les règles d’association générées en utilisant inspect().
  4. Comparaison avec Apriori (arules) :
    • Sur le même objet transactions, appliquez l’algorithme Apriori en utilisant la fonction apriori du package arules. Spécifiez les paramètres support = 0.6 et confidence = 0.7 (dans la section parameter).
    • Extrayez et inspectez les itemsets fréquents et les règles d’association obtenus par Apriori.
    • Comparez les itemsets fréquents et les règles d’association obtenus par FP-Growth (fim4r) et Apriori (arules). Sont-ils identiques ?
  5. (Optionnel) Comparaison de Performance (sur Groceries) :
    • Chargez le jeu de données Groceries (disponible dans le package arules : data(Groceries)).
    • Utilisez la fonction system.time() pour mesurer et comparer le temps d’exécution de fim4r (avec method = "fpgrowth", target = "frequent itemsets") et apriori (pour les itemsets fréquents) sur le dataset Groceries. Choisissez un seuil de support bas (par exemple, supp = 0.01 ou supp = 0.005) pour rendre la tâche plus exigeante.
    • system.time(fim4r(Groceries, method = "fpgrowth", target = "frequent itemsets", supp = 0.01))
    • system.time(apriori(Groceries, parameter = list(support = 0.01, target = "frequent itemsets")))
    • Commentez les différences de temps observées.