Impara Confronto delle Prestazioni Algoritmiche | Estrazione di Regole ad Alte Prestazioni e Ottimizzazione della Scalabilità

Scorri per mostrare il menu

Comprendere le differenze computazionali tra Apriori e FP-Growth è fondamentale nell'analisi delle regole associative su larga scala. Di seguito una panoramica strutturata per confrontare efficacemente questi due algoritmi:

Utilizzo della memoria

Apriori

Genera tutti i possibili insiemi di item e li memorizza in memoria, il che può causare una crescita esponenziale dell'utilizzo della memoria all'aumentare del numero di item unici;

FP-Growth

Costruisce una struttura compatta FP-tree che memorizza le transazioni in modo più efficiente comprimendo i prefissi comuni, riducendo notevolmente l'occupazione di memoria per dataset densi.

Velocità

Apriori

Esegue ripetute scansioni del dataset per contare le frequenze degli insiemi di item, comportando tempi di esecuzione elevati, soprattutto con l'aumentare della dimensione degli insiemi;

FP-Growth

Richiede solo due passaggi completi sui dati—uno per determinare gli item frequenti e un altro per costruire l'FP-tree—rendendolo significativamente più veloce per dataset di grandi dimensioni.

Scalabilità

Apriori

Ha difficoltà di scalabilità a causa dell'esplosione combinatoria degli insiemi di item candidati, rendendolo poco pratico per dataset molto grandi o densi;

FP-Growth

Scala meglio evitando la generazione di candidati e sfruttando la compressione ad albero, consentendo un'estrazione efficiente anche con l'aumentare della dimensione dei dati e della complessità degli insiemi di item.

Scenari pratici

Usa Apriori

Quando i dataset sono piccoli o sparsi, l'interpretabilità e la semplicità sono importanti, oppure quando si desidera regolare facilmente le soglie di supporto minimo;

Usa FP-Growth

Quando i dataset sono grandi, densi, oppure l'efficienza della memoria e la velocità sono priorità.

Il seguente esempio di codice mostra come creare un dataset sintetico di transazioni di market basket e confrontare le prestazioni in termini di tempo di esecuzione degli algoritmi Apriori e FP-Growth utilizzando la libreria mlxtend di Python. Verrà illustrato come ciascun algoritmo gestisce gli stessi dati e come differiscono i loro tempi di esecuzione, evidenziando l'efficienza in scenari pratici.


              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. Quando è preferibile utilizzare FP-Growth rispetto ad Apriori per l'estrazione di regole di associazione?

2. Quale affermazione descrive meglio la differenza di complessità computazionale tra Apriori e FP-Growth?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 2. Capitolo 2

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Sezione 2. Capitolo 2