Apprendre Construction d’Arbres de Motifs Fréquents avec l’Algorithme FP-Growth | Extraction de Règles Haute Performance et Optimisation de l'Échelle

Glissez pour afficher le menu

Présentation de FP-Growth

FP-Growth est un algorithme haute performance conçu pour l'extraction d'ensembles d'items fréquents dans de grands ensembles de données transactionnelles. Contrairement à Apriori, qui génère des ensembles candidats et parcourt plusieurs fois la base de données, FP-Growth construit une structure de données compacte appelée FP-Tree (arbre de motifs fréquents) permettant d'extraire les motifs fréquents sans génération de candidats. Cela se traduit par des gains significatifs en vitesse et en mémoire, en particulier pour les ensembles de données comportant de nombreux motifs fréquents.

Structure de l'arbre

La structure FP-Tree compresse l'ensemble des transactions dans un format d'arbre préfixe. Chaque transaction est traitée en triant ses items par ordre décroissant de fréquence, puis en les insérant dans l'arbre, partageant les préfixes communs avec les chemins existants. Le nœud racine est un nœud nul servant de point d'entrée, et chaque nœud de l'arbre représente un item ainsi qu'un compteur indiquant combien de transactions partagent ce préfixe jusqu'à ce point.

Chaînage des nœuds

Pour faciliter l'extraction efficace, tous les nœuds représentant le même item sont reliés par une liste chaînée, formant ce que l'on appelle une table d'en-tête. Cela permet de parcourir rapidement toutes les occurrences d'un item particulier dans l'arbre. Chaque entrée de la table d'en-tête pointe vers le premier nœud de l'arbre pour cet item, et chaque nœud contient un lien vers le nœud suivant portant le même nom d'item.

Extraction des motifs

L'extraction des motifs fréquents à partir du FP-Tree implique deux étapes principales. D'abord, il s'agit de parcourir l'arbre de bas en haut, en suivant les liens pour chaque item dans la table d'en-tête afin de collecter tous les chemins préfixes menant à cet item. Ensuite, il faut construire des FP-Trees conditionnels pour chaque item et les explorer récursivement afin d'extraire tous les ensembles d'items fréquents. Ce processus récursif se poursuit jusqu'à ce qu'aucun motif fréquent supplémentaire ne soit trouvé.

Exemple : Construction étape par étape d’un FP-Tree

Examinons la construction exacte étape par étape à l’aide de vos transactions d’exemple, en supposant un seuil de support minimal de 2 (c’est-à-dire que les articles doivent apparaître au moins deux fois pour être pris en compte).

Supposons que vous ayez les transactions suivantes :

- Transaction 1: A, B, D;
- Transaction 2: B, C, E;
- Transaction 3: A, B, C, E;
- Transaction 4: B, E.

Étape 1 : Scanner la base de données et trier par fréquence

Tout d’abord, l’algorithme lit l’ensemble du jeu de données pour compter combien de fois chaque article individuel apparaît. Tout article en dessous du seuil de support minimal est écarté. Ensuite, un ordre de tri global est établi, de la fréquence la plus élevée à la plus faible.

Nombre global d’occurrences des articles :

B apparaît 4 fois

E apparaît 3 fois

A apparaît 2 fois

C apparaît 2 fois

D apparaît 1 fois (Écarté car inférieur au support minimal de 2)

Règle d’ordre final : Chaque transaction sera désormais filtrée et réorganisée pour suivre strictement cet ordre de fréquence décroissante :

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

Étape 2 : Réorganiser chaque transaction

Avant d’insérer les articles dans l’arbre, l’algorithme réécrit chaque transaction. Il retire l’article peu fréquent (D) et réorganise les articles restants selon la nouvelle règle d’ordre global.

- Transaction 1: A, B, D devient B, A
- Transaction 2: B, C, E devient B, E, C
- Transaction 3: A, B, C, E devient B, E, A, C
- Transaction 4: B, E devient B, E

Étape 3 : Insérer les chemins dans le FP-Tree

Chaque FP-Tree commence par un nœud racine vide appelé le nœud racine nul. Nous insérons maintenant nos transactions réorganisées dans l’arbre une par une, en incrémentant les compteurs lorsque les chemins se chevauchent et en créant des branches lorsqu’ils divergent.

Insertion de la transaction 1 {B, A} : l’arbre crée une nouvelle branche directement depuis la racine.

Insertion de la transaction 2 {B, E, C} : l’algorithme commence à la racine et vérifie le premier article, B. Comme B existe déjà comme enfant de la racine, le chemin se chevauche ! L’algorithme se déplace vers B et incrémente son compteur à 2. L’article suivant est E. Comme B n’a pas encore d’enfant nommé E, l’arbre se divise ici et crée une nouvelle sous-branche pour E, suivie de C.

Insertion de la transaction 3 {B, E, A, C} : à partir de la racine, le chemin passe par B (le compteur passe à 3), puis descend vers le nœud E existant (le compteur passe à 2). L’article suivant est A. Comme E n’a pas d’enfant nommé A, l’arbre crée une nouvelle division sous E pour (A:1) -> (C:1).

Insertion de la transaction 4 {B, E} : l’algorithme suit le chemin de préfixe le plus populaire et B passe à 4, E passe à 3. La transaction s’arrête ici, donc aucun nouveau nœud n’est ajouté.

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

Cet exemple de code montre comment construire un FP-Tree à partir d’une liste de transactions en Python. Voici une explication détaillée de chaque étape :

Comptage des fréquences des articles :
- Le code utilise la classe Counter du module collections pour compter combien de fois chaque article apparaît dans toutes les transactions ;
- Cela permet d’identifier les articles suffisamment fréquents pour être inclus dans l’arbre.
Suppression des articles peu fréquents :
- Les articles qui ne respectent pas le seuil de support minimal sont filtrés ;
- L’ensemble freq_items contient uniquement les articles apparaissant au moins autant de fois que la valeur de min_support.
Tri des transactions par fréquence :
- Chaque transaction est filtrée pour ne conserver que les articles fréquents ;
- Les articles sont ensuite triés par ordre décroissant de leur fréquence globale (et par ordre alphabétique en cas d’égalité) ;
- Ce tri maximise le partage de préfixes dans le FP-Tree, rendant l’arbre plus compact.
Définition de la classe de nœud FP-Tree :
- La classe FPTreeNode représente chaque nœud de l’arbre ;
- Chaque nœud stocke le nom de l’article, le compteur, un pointeur vers son parent, un dictionnaire de ses enfants et un lien vers le prochain nœud portant le même nom d’article (pour le parcours via la table d’en-tête).
Construction du FP-Tree et de la table d’en-tête :
- La fonction build_fp_tree crée l’arbre en insérant chaque transaction triée ;
- En partant de la racine, pour chaque article d’une transaction, la fonction vérifie si un nœud enfant existe : sinon, elle en crée un et l’ajoute à la table d’en-tête ;
- Si un nœud existe déjà, son compteur est incrémenté ;
- Après la construction de l’arbre, le code relie tous les nœuds portant le même nom d’article via l’attribut link, ce qui permet un parcours rapide via la table d’en-tête.
Affichage de la structure du FP-Tree :
- La fonction print_tree affiche l’arbre en imprimant récursivement chaque nœud et son compteur avec une indentation pour visualiser la structure de l’arbre ;
- Cette sortie permet de visualiser comment les transactions sont compressées en chemins partagés dans le FP-Tree.

1. Lequel des éléments suivants est un avantage clé de FP-Growth par rapport à l’algorithme Apriori ?

2. Quelle est la structure d’un nœud de FP-Tree ?

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 1

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Section 2. Chapitre 1