Skip to content
Torna ai risultati

FP-Growth (Frequent Pattern Growth)

Introdotto da
Jiawei Han, Jian Pei & Yiwen Yin
Anno
2000
Tipo
Frequent-itemset mining algorithm
Famiglia
Pattern mining

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

FP-Growth, introdotto da Jiawei Han, Jian Pei e Yiwen Yin nel 2000, estrae itemset frequenti da dati transazionali senza generare set candidati, il passaggio costoso che rallenta il classico algoritmo Apriori.

Comprime il database in un albero dei pattern frequenti (FP-tree) in due scansioni, quindi fa crescere i pattern frequenti ricorsivamente da quella struttura, rendendolo notevolmente più veloce di Apriori su dataset grandi e densi.

L’intuizione alla base del metodo

Apriori trova gli itemset frequenti generando e testando ripetutamente combinazioni candidate — un processo costoso e ad alta intensità di scansioni che esplode su dati densi. FP-Growth adotta un percorso diverso: comprime l'intero database transazionale in un albero compatto dove i prefissi condivisi sono memorizzati una sola volta, in modo che i pattern comuni si sovrappongano e si comprimano. Quindi, invece di generare candidati, legge i pattern frequenti direttamente dall'albero seguendo i percorsi che portano a ciascun item ed estraendo ricorsivamente alberi 'condizionali' più piccoli. Due passaggi sui dati e un'intelligente struttura dati sostituiscono i molti passaggi di Apriori e l'esplosione combinatoria dei candidati.

Storia

Han, Pei e Yin hanno presentato FP-Growth al SIGMOD 2000 come alternativa ad Apriori senza generazione di candidati, con un trattamento ampliato nel loro articolo del 2004 su Data Mining and Knowledge Discovery. L'idea dell'albero dei pattern frequenti — comprimere le transazioni in una struttura a prefisso condiviso ed estrarla ricorsivamente — è diventata una tecnica fondamentale nell'estrazione di pattern, insieme ad Apriori (basato sui candidati) ed ECLAT (formato verticale). Rimane un miner di itemset standard e ad alte prestazioni nelle librerie di data mining.

Quando usarlo

Utilizzare FP-Growth per estrarre itemset frequenti (e, a valle, regole di associazione) da dati transazionali — analisi del carrello della spesa, analisi dell'utilizzo del web e dei clickstream, raccomandazione e co-occorrenza in bioinformatica — specialmente su dataset grandi o densi dove la generazione di candidati di Apriori è troppo lenta. Richiede solo due scansioni del database e tipicamente supera di gran lunga Apriori. I suoi costi: l'FP-tree deve rientrare in memoria (una limitazione per dati molto grandi o estremamente sparsi, dove l'albero si comprime male), la ricorsione può essere complessa da implementare e, come tutte le estrazioni basate sul supporto, è sensibile alla soglia di supporto minimo (troppo bassa fa esplodere l'output, troppo alta perde pattern). ECLAT (intersezione di tidset verticali) è un'alternativa; per le regole stesse, abbinare alla generazione di regole di associazione.

Limiti e considerazioni

  • L'FP-tree deve rientrare in memoria; dataset molto grandi potrebbero non farlo.
  • Su dati sparsi l'albero si comprime male, erodendo il vantaggio.
  • La costruzione ricorsiva dell'albero condizionale è relativamente complessa da implementare.
  • Sensibile alla soglia di supporto minimo, come tutte le estrazioni di itemset frequenti.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Nessuna generazione di candidati — molto più veloce di Apriori su dati grandi/densi.
  • Solo due scansioni del database, indipendentemente dalla lunghezza del pattern.
  • L'FP-tree comprime la struttura condivisa, risparmiando memoria e tempo su dati densi.
  • Si adatta a pattern frequenti lunghi che sopraffanno i metodi basati sui candidati.

Applicazioni

  • Analisi del carrello della spesa ed estrazione di associazioni nel commercio al dettaglio.
  • Analisi dell'utilizzo del web ed estrazione di pattern di clickstream.
  • Raccomandazione tramite item che co-occorrono frequentemente.
  • Co-occorrenza e scoperta di motivi in bioinformatica.
  • Qualsiasi attività di estrazione di itemset frequenti su larga scala in cui Apriori è troppo lento.

Come funziona

Come funziona

1

Una prima scansione del database conta il supporto di ciascun item e scarta quelli al di sotto della soglia di supporto minimo. Gli item frequenti rimanenti vengono ordinati per frequenza decrescente — questo ordinamento consente alle transazioni di condividere i prefissi dell'albero e mantiene l'FP-tree compatto.

Formula
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

Una seconda scansione inserisce ogni transazione (i suoi item frequenti, nell'ordine ordinato) nell'FP-tree, incrementando i conteggi lungo i percorsi dei prefissi condivisi e aggiungendo nuovi rami secondo necessità. Una tabella di intestazione collega tutte le occorrenze di ciascun item, in modo che l'albero rappresenti in modo compatto la struttura frequente dell'intero dataset.

Formula
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

Per ogni item frequente (elaborato prima il meno frequente), l'algoritmo raccoglie la sua base di pattern condizionali — l'insieme dei percorsi prefisso nell'albero che co-occorrono con quell'item, ciascuno pesato dal suo conteggio. Questo cattura il contesto in cui l'item appare frequentemente.

Formula
\text{for each item: collect its conditional pattern base (prefix paths)}
4

Da ogni base di pattern condizionali viene costruito e analizzato ricorsivamente un FP-tree condizionale più piccolo, facendo crescere itemset frequenti più lunghi aggiungendo l'item ai pattern trovati nel suo albero condizionale. La ricorsione termina con alberi a percorso singolo, le cui combinazioni di itemset vengono enumerate direttamente — producendo tutti gli itemset frequenti senza generazione di candidati.

Formula
\text{build conditional FP-trees recursively to grow frequent patterns}

Errori comuni

  • Impostare il supporto minimo troppo basso, producendo un'esplosione di itemset.
  • Assumere che batta sempre Apriori — su dati piccoli o sparsi il guadagno è modesto.
  • Dimenticare che gli itemset frequenti non sono regole; la generazione di regole è un passaggio separato.
  • Trascurare i limiti di memoria quando l'FP-tree non può essere mantenuto nella RAM.

Domande frequenti

In che modo FP-Growth è più veloce di Apriori?

Apriori genera e testa ripetutamente itemset candidati, scansionando il database molte volte. FP-Growth evita completamente la generazione di candidati: comprime i dati in un FP-tree in due scansioni ed estrae i pattern ricorsivamente da esso. Questo elimina l'esplosione combinatoria dei candidati, fornendo grandi accelerazioni su dati densi.

Cos'è l'FP-tree?

Un albero prefisso compresso degli item frequenti del database. Le transazioni che condividono un prefisso condividono un percorso, con i conteggi dei nodi che registrano il supporto, e una tabella di intestazione collega le occorrenze di ciascun item. Memorizza la struttura frequente del dataset in modo compatto in modo che i pattern possano essere letti senza riscansionare i dati.

Come si relaziona FP-Growth con ECLAT e le regole di associazione?

FP-Growth, ECLAT e Apriori trovano tutti itemset frequenti; ECLAT utilizza un approccio di intersezione di tidset verticali invece di un albero. Trovare itemset frequenti è solo la prima fase — le regole di associazione (con confidenza/lift) vengono generate da quegli itemset in un passaggio separato.

Metodi correlati

Fonti

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    Apri il riferimento DOI
    Copiato.
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    Apri il riferimento DOI
    Copiato.