L’algoritmo FP-Growth (Frequent Pattern Growth) e l’associazione dei dati nel data mining

L’algoritmo FP-Growth (Frequent Pattern Growth) è un algoritmo di data mining utilizzato per identificare itemset frequenti e generare regole di associazione in un dataset. È specificamente progettato per superare alcune limitazioni dell’algoritmo Apriori in termini di efficienza computazionale, soprattutto quando si affrontano dataset di grandi dimensioni.

[wpda_org_chart tree_id=42 theme_id=50]

L’algoritmo FP-Growth

L’algoritmo FP-Growth (Frequent Pattern Growth) è stato proposto da Jiawei Han, Jian Pei e Yiwen Yin nel loro paper intitolato “Mining Frequent Patterns without Candidate Generation” pubblicato nel 2000. Gli autori hanno sviluppato questo algoritmo come alternativa più efficiente rispetto all’algoritmo Apriori, che era ampiamente utilizzato in quel periodo per l’identificazione di itemset frequenti e la generazione di regole di associazione.

L’algoritmo Apriori, introdotto prima degli anni 1990, era un metodo efficace per identificare itemset frequenti e generare regole di associazione. Tuttavia, aveva limitazioni in termini di efficienza computazionale, specialmente su dataset di grandi dimensioni. Per superare le limitazioni di Apriori, Han, Pei e Yin hanno proposto l’FP-Growth nel loro articolo del 2000. L’idea principale era quella di utilizzare una struttura dati ad albero chiamata FP-Tree per rappresentare in modo efficiente gli itemset frequenti senza dover generare tutti gli itemset candidati.

L’FP-Growth sfrutta la ricorsione e la struttura compatta dell’FP-Tree per identificare gli itemset frequenti senza la necessità di generare tutte le combinazioni candidate. Ciò ha reso l’algoritmo più efficiente rispetto ad Apriori, specialmente su dataset con un alto numero di item o transazioni.

L’algoritmo FP-Growth ha guadagnato rapidamente popolarità nel campo del data mining grazie alla sua efficienza e alla capacità di gestire dataset di grandi dimensioni. È stato utilizzato in diverse applicazioni, tra cui l’analisi del carrello della spesa, la raccomandazione di prodotti e la scoperta di pattern in dati transazionali.

L’FP-Growth ha contribuito significativamente al progresso del data mining, fornendo un’alternativa più efficiente e scalabile per l’analisi di associazione. La sua introduzione ha stimolato ulteriori ricerche e sviluppi in questo campo.

Oggi, l’algoritmo FP-Growth è ancora ampiamente utilizzato nei contesti di data mining e machine learning, in particolare quando si tratta di affrontare dataset complessi e di grandi dimensioni.

Funzionamento dell’algoritmo FP-Growth

Ecco come funziona l’algoritmo FP-Growth:

• Costruzione dell’albero FP-Tree: Il passo iniziale consiste nella creazione di un’FP-Tree, una struttura dati ad albero che rappresenta i pattern frequenti nel dataset. L’albero è costruito in modo incrementale, partendo dalla transazione con meno frequenza e aggiungendo i nodi via via che si procede attraverso le transazioni.
• Generazione degli Itemset Frequenti: Dopo la costruzione dell’FP-Tree, l’algoritmo esplora ricorsivamente l’albero per identificare gli itemset frequenti. Questo processo è più efficiente rispetto all’approccio Apriori, poiché evita di generare esplicitamente tutti gli itemset candidati.
• Generazione di Regole di Associazione: Infine, l’algoritmo genera le regole di associazione basate sugli itemset frequenti identificati. Queste regole seguono lo stesso principio delle regole di associazione in Apriori, che indicano le relazioni tra gli item nel dataset.

FP-Growth vs Apriori

• Efficienza Computazionale: FP-Growth è generalmente più efficiente di Apriori, specialmente su dataset di grandi dimensioni, poiché evita di generare tutti gli itemset candidati.
• Struttura Compatta: L’FP-Tree consente di rappresentare in modo compatto l’informazione riguardante gli itemset frequenti, riducendo la necessità di scansioni ripetute del dataset.
• Minore Utilizzo di Memoria: Rispetto ad Apriori, FP-Growth spesso richiede meno memoria per memorizzare le strutture dati intermedie.

L’algoritmo FP-Growth è particolarmente utile quando si tratta di dataset complessi e di grandi dimensioni, dove la scalabilità e l’efficienza sono fondamentali per un’analisi rapida ed efficace dei pattern di associazione.

Implementazione in Python

Per quanto riguarda il linguaggio Python, l’implementazione di questo algoritmo è molto semplice, dato che esiste una libreria specifica:pyfpgrowth. Assicurati di installare la libreria prima di continuare:

pip install pyfpgrowth

Adesso possiamo cominciare a lavorare con il codice di esempio:

import pyfpgrowth

# Esempio di dataset
dataset = [
    ['mela', 'birra', 'pane'],
    ['mela', 'latte'],
    ['latte', 'pane'],
    ['mela', 'birra', 'latte'],
]

# Impostazione del supporto minimo
min_support = 2

# Applicazione dell'algoritmo FP-Growth
patterns = pyfpgrowth.find_frequent_patterns(dataset, min_support)

# Estrazione delle regole di associazione
rules = pyfpgrowth.generate_association_rules(patterns, 0.7)  # Impostazione di una soglia di confidenza del 70%

# Stampa dei risultati
print("Itemset Frequenti:")
print(patterns)

print("\nRegole di Associazione:")
print(rules)

In questo esempio:

• find_frequent_patterns viene utilizzato per trovare gli itemset frequenti nel dataset con un supporto minimo specificato.
• generate_association_rules viene utilizzato per generare regole di associazione basate sugli itemset frequenti con una soglia di confidenza specificata.

Puoi regolare il dataset, il supporto minimo e la soglia di confidenza in base alle tue esigenze specifiche. I risultati mostreranno gli itemset frequenti e le regole di associazione identificate nel tuo dataset. Eseguendo il codice infatti otterremo il seguente risultato.

Itemset Frequenti:
{('birra',): 2, ('birra', 'mela'): 2, ('pane',): 2, ('mela',): 3, ('latte',): 3, ('latte', 'mela'): 2}

Regole di Associazione:
{('birra',): (('mela',), 1.0)}

Analizziamo insieme i risultati ottenuti ed il loro significato.

Gli itemset frequenti indicano la frequenza con cui gli item compaiono nel dataset. Ad esempio, il singolo item ‘mela’ compare in tre transazioni, mentre la combinazione ‘latte’ e ‘mela’ compare in due transazioni.

Itemset Frequenti:

• ('birra',): 2: La birra appare in due transazioni.
• ('birra', 'mela'): 2: La combinazione di birra e mela appare in due transazioni.
• ('pane',): 2: Il pane appare in due transazioni.
• ('mela',): 3: La mela appare in tre transazioni.
• ('latte',): 3: Il latte appare in tre transazioni.
• ('latte', 'mela'): 2: La combinazione di latte e mela appare in due transazioni.

Regole di Associazione:

• ('birra',) => ('mela',): Questa regola indica che se qualcuno acquista birra, acquisterà anche mela con una confidenza del 100% (1.0). Ciò significa che in tutte le transazioni in cui è presente la birra, è anche presente la mela.

Ad esempio, se consideriamo questa regola di associazione, significa che in tutte le transazioni in cui la birra è presente (due transazioni), la mela è anche presente. La confidenza è 1.0, il che significa che questa associazione è stata osservata in tutte le transazioni contenenti birra.

Questi risultati forniscono informazioni sulle associazioni di itemset frequenti nel tuo dataset, aiutandoti a identificare pattern o relazioni di co-occorrenza tra gli elementi.