Apprendre Comparaison des performances algorithmiques | Extraction de Règles Haute Performance et Optimisation de l'Échelle

Glissez pour afficher le menu

Comprendre les différences de calcul entre Apriori et FP-Growth est essentiel lors de l'extraction de règles d'association à grande échelle. Voici une présentation structurée pour comparer efficacement ces deux algorithmes :

Utilisation de la mémoire

Apriori

Génère tous les itemsets possibles et les stocke en mémoire, ce qui peut entraîner une croissance exponentielle de l'utilisation de la mémoire à mesure que le nombre d'éléments uniques augmente ;

FP-Growth

Construit une structure FP-tree compacte qui stocke les transactions de manière plus efficace en regroupant les préfixes communs, réduisant considérablement l'empreinte mémoire pour les ensembles de données denses.

Vitesse

Apriori

Analyse répétée du jeu de données pour compter la fréquence des itemsets, entraînant un temps d'exécution élevé, surtout lorsque la taille des itemsets augmente ;

FP-Growth

Nécessite seulement deux passages complets sur les données—un pour déterminer les items fréquents et un autre pour construire l'arbre FP—ce qui le rend nettement plus rapide pour les grands ensembles de données.

Scalabilité

Apriori

Difficultés de passage à l'échelle en raison de l'explosion combinatoire des itemsets candidats, le rendant peu pratique pour des ensembles de données très volumineux ou denses ;

FP-Growth

Meilleure scalabilité grâce à l'absence de génération de candidats et à la compression par arbre, permettant une exploration efficace même lorsque la taille des données et la complexité des itemsets augmentent.

Scénarios pratiques

Utiliser Apriori

Lorsque les ensembles de données sont petits ou clairsemés, que l'interprétabilité et la simplicité sont importantes, ou lorsque vous souhaitez facilement ajuster les seuils de support minimal ;

Utiliser FP-Growth

Lorsque les ensembles de données sont volumineux, denses, ou que l'efficacité mémoire et la rapidité sont prioritaires.

L'exemple de code suivant montre comment créer un jeu de données synthétique de transactions de paniers d'achat et comparer les performances d'exécution des algorithmes Apriori et FP-Growth en utilisant la bibliothèque mlxtend de Python. Vous verrez comment chaque algorithme traite les mêmes données et comment leurs temps d'exécution diffèrent, mettant en évidence leur efficacité dans des scénarios pratiques.


              123456789101112131415161718192021222324252627
            
import pandas as pd
from mlxtend.frequent_patterns import apriori, fpgrowth
import numpy as np
import time

# Create a medium-sized synthetic dataset
np.random.seed(42)
items = ['apple', 'banana', 'milk', 'bread', 'butter', 'cheese', 'eggs', 'juice']
n_transactions = 3000
data = []
for _ in range(n_transactions):
    basket = np.random.choice(items, size=np.random.randint(2, 6), replace=False)
    data.append({item: (item in basket) for item in items})
df = pd.DataFrame(data)

# Timing Apriori
start_apriori = time.time()
apriori(df, min_support=0.05, use_colnames=True)
end_apriori = time.time()

# Timing FP-Growth
start_fpgrowth = time.time()
fpgrowth(df, min_support=0.05, use_colnames=True)
end_fpgrowth = time.time()

print(f"Apriori runtime: {end_apriori - start_apriori:.3f} seconds")
print(f"FP-Growth runtime: {end_fpgrowth - start_fpgrowth:.3f} seconds")

1. Quand faut-il privilégier FP-Growth par rapport à Apriori pour l'extraction de règles d'association ?

2. Quelle affirmation décrit le mieux la différence de complexité computationnelle entre Apriori et FP-Growth ?

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 2

Demandez à l'IA

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

Section 2. Chapitre 2