🧺 Analizzatore del Carrello della Spesa — Algoritmo Apriori dal vivo

Apriori è un algoritmo classico (Agrawal & Srikant, 1994) per l'estrazione di itemset frequenti e regole di associazione da dati transazionali come i carrelli della spesa. Costruisce gli itemset frequenti livello per livello: prima conta i singoli articoli, poi le coppie, poi le triple e così via, scartando a ogni livello tutto ciò che è sotto una soglia di supporto minimo prima che venga mai usato per costruire candidati più grandi. Questo pruning livello per livello è ciò che gli permette di scalare a grandi cataloghi di articoli senza mai enumerare esplicitamente ogni possibile combinazione.

Il supporto(X) è semplicemente la frazione di tutte le transazioni che contengono l'itemset X — una misura di quanto sia comune. La confidenza(A→B) = supporto(A∪B) / supporto(A) è la probabilità condizionata che un carrello contenga B dato che contiene già A. Il lift(A→B) = confidenza(A→B) / supporto(B) confronta quella probabilità condizionata con la frequenza di base di B: un lift maggiore di 1 significa che A rende B più probabile del caso, un lift vicino a 1 significa che sono essenzialmente indipendenti, e un lift inferiore a 1 significa che A rende B effettivamente meno probabile.

Apriori si basa sulla proprietà di chiusura verso il basso: se un itemset è frequente, anche ognuno dei suoi sottoinsiemi deve essere frequente, perché ogni transazione che contiene l'itemset completo contiene anche ciascun sottoinsieme. Il contrapposto è la regola di pruning — se un qualsiasi sottoinsieme di dimensione (k−1) di un candidato k-itemset non è frequente, il candidato non può essere frequente a sua volta, quindi viene scartato prima ancora di scansionare una singola transazione. Senza questo pruning, il numero di itemset candidati cresce combinatoriamente con la dimensione del catalogo; con esso, vengono testate solo combinazioni costruite da pezzi già frequenti.

Una volta trovato un itemset frequente di dimensione due o superiore, ogni modo di suddividerlo in un antecedente A non vuoto e il conseguente B rimanente produce una regola candidata A→B. Il suo supporto è semplicemente il supporto dell'itemset stesso; la sua confidenza e il suo lift sono calcolati a partire dai supporti di A e B, già misurati durante l'estrazione. Le regole vengono poi filtrate per mantenere solo quelle che soddisfano una soglia di confidenza minima, poiché un itemset frequente non garantisce che una particolare suddivisione di esso sia una regola predittiva forte.

Il supporto minimo controlla fino a che punto arriva la crescita degli itemset livello per livello: alzalo e solo le combinazioni più forti e più comuni sopravvivono a ogni livello, quindi l'estrazione si ferma dopo uno o due livelli; abbassalo e le combinazioni più rare sopravvivono, vengono esplorati livelli più profondi, e sia il tempo di esecuzione sia il numero puro di itemset candidati aumentano bruscamente. La confidenza minima viene applicata dopo, puramente come filtro sulle regole derivate da qualsiasi itemset trovato — alzarla scarta suddivisioni A→B deboli o casuali mantenendo solo le direzioni più sbilanciate e predittive dell'itemset.

L'estrazione è reale. Il simulatore genera un insieme di transazioni di spesa sintetiche con una genuina struttura di co-occorrenza (alcuni articoli sono deliberatamente resi propensi a comparire insieme), poi conta le occorrenze di articoli e itemset direttamente su quella lista di transazioni, applica la procedura standard Apriori di join-e-pruning livello per livello, e calcola confidenza e lift a partire dai supporti effettivamente misurati — nulla è scriptato o falso. Muovere i cursori riesegue l'intero algoritmo da zero sulle stesse transazioni.