Impara Elaborazione di Flussi di Dati Transazionali con l'Algoritmo Apriori | Fondamenti delle Regole di Associazione e Analisi Transazionale

Scorri per mostrare il menu

L'algoritmo Apriori è uno strumento fondamentale per individuare insiemi frequenti di articoli nei dati transazionali, elemento essenziale per l'analisi del carrello della spesa. Al centro di Apriori si trova il Principio di Apriori, noto anche come proprietà di chiusura verso il basso.

Definizione

Principio di Apriori - Se un insieme di articoli è frequente, allora anche tutti i suoi sottoinsiemi devono essere frequenti.

Questa intuizione riduce drasticamente il numero di insiemi di articoli da valutare, poiché qualsiasi insieme che contiene un sottoinsieme non frequente può essere immediatamente scartato.

La generazione dei candidati rappresenta la fase di abbinamento dell'algoritmo. In ogni iterazione, l'algoritmo prende gli insiemi frequenti individuati nel turno precedente e li combina per formare nuovi gruppi più grandi chiamati candidati. Per farlo in modo efficiente, l'algoritmo unisce solo insiemi che sono quasi identici, condividendo tutti gli articoli tranne l'ultimo.

Come funziona: Se l'algoritmo scopre che {Bread, Milk} e {Bread, Diapers} sono entrambi molto popolari singolarmente, li combina per creare un nuovo candidato a tre elementi per il turno successivo: {Bread, Milk, Diapers}.

Immediatamente dopo la generazione dei nuovi candidati, l'algoritmo avvia la fase di Potatura per eliminare i pesi morti prima di eseguire calcoli pesanti sul database. Questo passaggio si basa interamente sul Principio di Apriori, secondo cui un insieme di articoli di grandi dimensioni può essere frequente solo se tutte le sue parti più piccole sono anch'esse frequenti. Durante la potatura, l'algoritmo analizza meticolosamente ogni nuovo candidato e ne esamina i sottoinsiemi. Se anche solo un sottoinsieme non ha superato la selezione nel turno precedente, l'intero candidato viene eliminato all'istante.

Come funziona: Immagina che venga generato il candidato {Bread, Milk, Eggs}. L'algoritmo controlla i suoi sottoinsiemi: {Bread, Milk}, {Bread, Eggs} e {Milk, Eggs}. Se i tuoi log storici delle transazioni mostrano che {Milk, Eggs} è una combinazione rara che non ha superato il turno precedente, l'algoritmo elimina completamente {Bread, Milk, Eggs}. Questo ti permette di risparmiare potenza di calcolo su una combinazione che è matematicamente destinata a fallire.

Una volta che la lista dei candidati è stata ridotta ai contendenti più validi, l'algoritmo passa all'Identificazione degli insiemi frequenti. Il sistema esamina i database delle transazioni grezze per contare esattamente quante volte questi gruppi di candidati rimasti compaiono insieme nelle vere transazioni. Il conteggio totale di ciascun candidato viene convertito in percentuale. Se questo valore raggiunge o supera la Soglia Minima di Supporto predefinita, il candidato viene ufficialmente riconosciuto come Insieme Frequente.

Definizione

Soglia di supporto minimo è un valore definito dall'utente che determina la frequenza minima che un insieme di articoli deve avere per essere considerato significativo nell'algoritmo Apriori. Impostando questa soglia, si filtrano gli insiemi di articoli che compaiono troppo raramente nel dataset. Scegliere una soglia elevata porterà a meno insiemi, più comuni, rischiando di perdere combinazioni interessanti ma rare. Impostarla troppo bassa può generare un numero eccessivo di insiemi, inclusi quelli di scarso valore pratico. La soglia selezionata influisce direttamente sulla profondità e sul focus dell'analisi, quindi dovrebbe riflettere gli obiettivi e la scala dell'esplorazione dei dati.

Questo ciclo di tre passaggi si ripete consecutivamente. Si passa da singoli articoli a coppie, poi a gruppi di tre, e continua ad espandersi finché non si esegue un ciclo in cui non si trovano nuovi insiemi frequenti, mappando con successo l'intera rete di comportamenti di acquisto dei consumatori.

Per rendere concreti questi concetti, considera un semplice Esempio utilizzando un piccolo dataset. Supponiamo di avere le seguenti transazioni:

Transazione 1: {Milk, Bread};
Transazione 2: {Milk, Diaper, Beer, Bread};
Transazione 3: {Milk, Diaper, Beer, Cola};
Transazione 4: {Diaper, Beer};
Transazione 5: {Milk, Diaper, Bread, Beer}.

L'algoritmo identificherà prima tutti i singoli articoli che compaiono frequentemente, poi genererà coppie candidate da questi, eliminerà quelle che contengono articoli poco frequenti e continuerà questo processo per scoprire gruppi frequenti più grandi, come {Milk, Diaper, Beer}.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

Questo codice Python mostra una semplice implementazione dell'algoritmo Apriori per l'identificazione degli itemset frequenti nei dati transazionali. Ecco come viene eseguito ciascun passaggio:

Preparazione dei dati

Le transazioni sono rappresentate come una lista di liste, dove ogni sottolista contiene gli articoli acquistati insieme.
Tutti gli articoli unici vengono identificati e ordinati.
Viene creato un DataFrame one-hot encoded: ogni riga rappresenta una transazione e ogni colonna corrisponde a un articolo, con True o False che indicano la presenza o l'assenza.

Fasi dell'algoritmo Apriori

1. Identificazione degli itemset frequenti di lunghezza 1

L'algoritmo calcola il supporto per ogni singolo articolo (la proporzione di transazioni che contengono l'articolo).
Se il supporto di un articolo raggiunge o supera la soglia min_support (qui, 0.6), viene considerato frequente e incluso nel primo elenco di itemset frequenti.

2. Generazione dei candidati

Per gli itemset di lunghezza k (a partire da 2), l'algoritmo genera nuovi itemset candidati combinando gli itemset frequenti del turno precedente che condividono tutti gli elementi tranne uno.
Vengono considerate solo combinazioni uniche, evitando duplicati.

3. Potatura

Vengono controllati i sottoinsiemi di lunghezza k-1 di ciascun nuovo candidato.
Se un qualsiasi sottoinsieme non è presente nell'elenco degli itemset frequenti dell'iterazione precedente, il candidato viene escluso (potato), secondo il Principio di Apriori.

4. Conteggio del supporto

Per ciascun candidato rimanente, l'algoritmo conta quante transazioni contengono tutti gli articoli del candidato.
Il supporto viene calcolato e confrontato con la soglia. Solo i candidati che soddisfano la soglia vengono mantenuti come itemset frequenti per il turno successivo.

5. Iterazione

I passaggi 2–4 si ripetono, aumentando ogni volta la dimensione degli itemset, fino a quando non vengono trovati nuovi itemset frequenti.

Output

L'elenco finale include tutti gli itemset frequenti e i loro valori di supporto.
Il codice stampa ogni itemset frequente e il relativo supporto, mostrando quali combinazioni di articoli compaiono comunemente insieme nelle transazioni.

1. Quale delle seguenti descrive meglio la fase di generazione dei candidati nell'algoritmo Apriori?

2. Qual è la principale ragione per la potatura degli itemset candidati durante l'algoritmo Apriori?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 4

Chieda ad AI

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

Sezione 1. Capitolo 4