Impara Costruzione di Alberi di Pattern Frequenti con l'Algoritmo FP-Growth | Estrazione di Regole ad Alte Prestazioni e Ottimizzazione della Scalabilità

Scorri per mostrare il menu

Panoramica di FP-Growth

FP-Growth è un algoritmo ad alte prestazioni progettato per l'estrazione di insiemi frequenti di item in grandi dataset transazionali. A differenza di Apriori, che genera insiemi candidati e scansiona ripetutamente il database, FP-Growth costruisce una struttura dati compatta chiamata FP-Tree (Frequent Pattern Tree) che consente di estrarre pattern frequenti senza generare insiemi candidati. Questo comporta notevoli miglioramenti in termini di velocità e memoria, soprattutto per dataset con molti pattern frequenti.

Struttura dell'albero

La struttura FP-Tree comprime l'intero insieme di transazioni in un formato ad albero prefisso. Ogni transazione viene elaborata ordinando i suoi item in ordine decrescente di frequenza e poi inserendoli nell'albero, condividendo i prefissi comuni con i percorsi esistenti. Il nodo radice è un nodo nullo che funge da punto di ingresso, e ogni nodo nell'albero rappresenta un item insieme al conteggio di quante transazioni condividono quel prefisso fino a quel punto.

Collegamento dei nodi

Per facilitare l'estrazione efficiente, tutti i nodi che rappresentano lo stesso item sono collegati tramite una lista collegata, formando quella che viene chiamata header table. Questo permette di attraversare rapidamente tutte le occorrenze di un particolare item nell'albero. Ogni voce nella header table punta al primo nodo nell'albero per quell'item, e ogni nodo contiene un collegamento al nodo successivo con lo stesso nome di item.

Estrazione dei pattern

L'estrazione dei pattern frequenti dall'FP-Tree prevede due passaggi principali. Prima si attraversa l'albero dal basso verso l'alto, seguendo i collegamenti per ogni item nella header table per raccogliere tutti i percorsi prefisso che portano a quell'item. Successivamente, si costruiscono FP-Tree condizionali per ogni item e li si estrae ricorsivamente per ottenere tutti gli insiemi frequenti di item. Questo processo ricorsivo continua finché non si trovano più pattern frequenti.

Esempio: Costruzione passo-passo dell'FP-Tree

Analisi dettagliata della costruzione passo-passo utilizzando le transazioni di esempio, assumendo una Soglia Minima di Supporto pari a 2 (gli articoli devono comparire almeno due volte per essere considerati).

Supponiamo di avere le seguenti transazioni:

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

Passo 1: Scansione del database e ordinamento per frequenza

L'algoritmo legge l'intero dataset per contare quante volte ciascun articolo compare. Gli articoli che non raggiungono la soglia minima di supporto vengono scartati. Successivamente, viene stabilito un ordine globale dal più frequente al meno frequente.

Conteggio globale degli articoli:

B compare 4 volte

E compare 3 volte

A compare 2 volte

C compare 2 volte

D compare 1 volta (Scartato perché inferiore al Supporto Minimo di 2)

Regola finale di ordinamento: Ogni transazione verrà ora filtrata e riordinata per seguire rigorosamente questo ordine di frequenza decrescente:

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

Passo 2: Riordinare ogni transazione

Prima di inserire gli articoli nell'albero, l'algoritmo riscrive ogni transazione. Rimuove l'articolo poco frequente (D) e riordina i restanti articoli secondo la nuova regola di ordinamento globale.

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

Passo 3: Inserimento dei percorsi nell'FP-Tree

Ogni FP-Tree inizia con un nodo radice vuoto chiamato Null Root Node. Ora si inseriscono le transazioni riordinate nell'albero una alla volta, incrementando i contatori quando i percorsi si sovrappongono e ramificando quando divergono.

Inserimento della Transazione 1 {B, A}: l'albero crea un nuovo ramo diretto dalla radice.

Inserimento della Transazione 2 {B, E, C}: l'algoritmo parte dalla radice e controlla il primo articolo, B. Poiché B esiste già come figlio della radice, il percorso si sovrappone! L'algoritmo si sposta su B e incrementa il suo contatore a 2. Il prossimo articolo è E. Poiché B non ha ancora un figlio chiamato E, l'albero si divide qui e crea un nuovo sotto-ramo per E, seguito da C.

Inserimento della Transazione 3 {B, E, A, C}: partendo dalla radice, il percorso raggiunge B (il contatore sale a 3), poi scende sul nodo E esistente (il contatore sale a 2). Il prossimo articolo è A. Poiché E non ha un figlio chiamato A, l'albero crea una nuova divisione sotto E per (A:1) -> (C:1).

Inserimento della Transazione 4 {B, E}: l'algoritmo segue il percorso prefisso più popolare e B sale a 4, E sale a 3. La transazione termina qui, quindi non vengono aggiunti nuovi nodi.

(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)

Questo esempio di codice mostra come costruire un FP-Tree da una lista di transazioni utilizzando Python. Di seguito una spiegazione dettagliata di ciascun passaggio:

Conteggio delle frequenze degli articoli:
- Il codice utilizza la classe Counter dal modulo collections per contare quante volte ogni articolo compare in tutte le transazioni;
- Questo aiuta a identificare quali articoli sono abbastanza frequenti da essere inclusi nell'albero.
Rimozione degli articoli poco frequenti:
- Gli articoli che non soddisfano la soglia minima di supporto vengono filtrati;
- L'insieme freq_items contiene solo gli articoli che compaiono almeno tante volte quanto specificato da min_support.
Ordinamento delle transazioni per frequenza:
- Ogni transazione viene filtrata per mantenere solo gli articoli frequenti;
- Gli articoli vengono poi ordinati in ordine decrescente di frequenza globale (e alfabeticamente in caso di parità);
- L'ordinamento massimizza la condivisione dei prefissi nell'FP-Tree, rendendo l'albero più compatto.
Definizione della classe nodo FP-Tree:
- La classe FPTreeNode rappresenta ciascun nodo dell'albero;
- Ogni nodo memorizza il nome dell'articolo, il contatore, un puntatore al nodo genitore, un dizionario dei figli e un collegamento al prossimo nodo con lo stesso nome (per la traversata tramite header table).
Costruzione dell'FP-Tree e della header table:
- La funzione build_fp_tree crea l'albero inserendo ciascuna transazione ordinata;
- Partendo dalla radice, per ogni articolo in una transazione, la funzione verifica se esiste già un nodo figlio—se non esiste, ne crea uno e lo aggiunge alla header table;
- Se il nodo esiste già, il suo contatore viene incrementato;
- Dopo la costruzione dell'albero, il codice collega tutti i nodi con lo stesso nome tramite l'attributo link, permettendo una traversata rapida tramite la header table.
Stampa della struttura dell'FP-Tree:
- La funzione print_tree mostra l'albero stampando ricorsivamente ciascun nodo e il suo contatore con indentazione per rappresentare la struttura ad albero;
- Questo output aiuta a visualizzare come le transazioni vengono compresse in percorsi condivisi all'interno dell'FP-Tree.

1. Quale delle seguenti è un vantaggio chiave di FP-Growth rispetto all'algoritmo Apriori?

2. Qual è la struttura di un nodo FP-Tree?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 2. Capitolo 1

Chieda ad AI

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

Sezione 2. Capitolo 1