Algoritmo Apriori
- Introdotto da
- Agrawal, R. & Srikant, R.
- Anno
- 1994
- Tipo
- Frequent itemset and association rule mining algorithm
- Famiglia
- Machine learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'algoritmo Apriori, introdotto da Agrawal e Srikant nel 1994, è il metodo fondamentale per scoprire insiemi di item frequenti e regole di associazione in database transazionali.
Utilizza una ricerca a livello, breadth-first, guidata dalla proprietà anti-monotona del supporto per enumerare efficientemente tutte le combinazioni di item che co-occorrono al di sopra di una soglia minima impostata dall'utente, quindi estrae regole interpretabili se-allora da tali pattern.
L’intuizione alla base del metodo
Considerare un database di scontrini di supermercato. L'intuizione di Apriori è la proprietà anti-monotona: se una coppia di prodotti viene acquistata raramente insieme, nessun insieme più grande contenente quella coppia può essere frequente. Ciò consente all'algoritmo di potare lo spazio di ricerca esponenzialmente grande di possibili combinazioni di item costruendo candidati livello per livello — partendo da singoli item, poi coppie, poi triple — e scartando qualsiasi candidato i cui sottoinsiemi siano già noti per essere infrequenti, prima ancora di contarli nei dati.
Storia
Trascurare la rimozione di regole non informative (ad esempio, regole che coinvolgono item acquistati universalmente come una carta fedeltà del negozio).
Quando usarlo
Utilizzare Apriori quando l'obiettivo è scoprire pattern di co-occorrenza o relazioni se-allora in dati transazionali o di presenza di item binari — analisi del carrello della spesa, co-endorsement di item nei sondaggi, co-occorrenza di diagnosi mediche, o associazione di termini testuali. È adatto per dataset di dimensioni moderate dove la trasparenza e l'interpretabilità delle regole di output sono una priorità. Non utilizzare Apriori quando il database delle transazioni è molto grande (milioni di righe con cataloghi di item ampi), poiché le sue scansioni ripetute dell'intero database lo rendono lento rispetto a FP-Growth; in tali casi si preferisce FP-Growth. È inoltre inappropriato per dati numerici continui senza una precedente discretizzazione e non modella la direzionalità o la causalità.
Limiti e considerazioni
- Le ripetute scansioni complete del database lo rendono lento su dataset di grandi dimensioni — FP-Growth è spesso preferito su larga scala.
- Abbassare la soglia di supporto può produrre un numero esponenziale di insiemi di item candidati e regole, rendendo difficile l'interpretazione.
- Non cattura l'ordine temporale, la direzionalità o le relazioni causali tra gli item.
- I risultati sono sensibili alla scelta delle soglie di supporto e confidenza, che richiedono conoscenza del dominio o una messa a punto sistematica.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Genera regole se-allora completamente interpretabili con supporto, confidenza e lift quantificati.
- La proprietà di potatura anti-monotona rende trattabile una ricerca altrimenti esponenziale.
- Non richiede etichettatura preliminare dei dati; è interamente non supervisionato.
- I parametri di soglia (supporto, confidenza) conferiscono all'analista il controllo diretto sulla granularità delle regole.
- Le regole di output sono attuabili e possono essere comunicate a stakeholder non tecnici senza background algoritmico.
- Seminale, pesantemente citato e implementato in quasi tutte le principali librerie di data mining.
Applicazioni
- Rakesh Agrawal e Ramakrishnan Srikant hanno introdotto l'algoritmo Apriori al VLDB 1994, basandosi sulla formulazione del problema di mining delle regole di associazione di Agrawal et al. del 1993. Il nome riflette la sua intuizione chiave: utilizzare la conoscenza a priori degli insiemi di item frequenti (k) per potare i candidati al livello k+1. È diventato il benchmark canonico rispetto al quale vengono misurati tutti i successivi algoritmi di mining di insiemi di item frequenti — inclusi FP-Growth (2000) ed Eclat — e rimane un capitolo standard nei libri di testo di data mining e machine learning.
- Analisi del carrello della spesa: scoprire quali prodotti vengono acquistati frequentemente insieme per guidare la disposizione degli scaffali e le promozioni.
- Informatica medica: identificare sintomi, diagnosi o prescrizioni di farmaci co-occorrenti nei registri dei pazienti.
- Web usage mining: trovare quali pagine o funzionalità gli utenti tendono a visitare o attivare insieme.
- Analisi di sondaggi e questionari: rilevare quali item o risposte di scala vengono sistematicamente co-endorse.
- Bootstrapping di sistemi di raccomandazione: generare associazioni di item candidati prima di distribuire il filtraggio collaborativo.
Come funziona
Come funziona
L'analista sceglie due soglie prima di eseguire l'algoritmo: supporto minimo (la frazione di transazioni che devono contenere un dato insieme di item affinché sia considerato frequente) e confidenza minima (la probabilità condizionata richiesta affinché una regola se-allora venga mantenuta). Questi due valori controllano il volume e la specificità dell'output e dovrebbero essere calibrati tramite conoscenza del dominio o esecuzioni esplorative.
L'algoritmo effettua una scansione completa del database delle transazioni per contare quante volte appare ciascun singolo item. Vengono mantenuti solo gli item il cui supporto soddisfa o supera la soglia di supporto minima; gli altri vengono scartati. Questo insieme di singoli item frequenti forma il primo livello di candidati.
Formula
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}Gli insiemi di item frequenti trovati al livello k vengono uniti a coppie per formare insiemi di item candidati di dimensione k+1. Vengono unite solo le coppie che condividono gli stessi primi k-1 item, una regola che mantiene compatto l'insieme dei candidati. Una nuova scansione del database conta il supporto di ciascun candidato.
Prima del conteggio, ogni candidato di dimensione k+1 viene verificato rispetto a tutti i suoi sottoinsiemi di dimensione (k). Se un qualsiasi sottoinsieme non era frequente al livello precedente, il candidato viene scartato immediatamente senza leggere i dati, sfruttando la proprietà anti-monotona per ridurre il calcolo. I sopravvissuti a questo passaggio di potatura formano il livello successivo di insiemi di item frequenti.
Da ogni insieme di item frequenti di dimensione due o superiore, vengono generate tutte le possibili regole se-allora partizionando gli item in un antecedente e un conseguente. Ogni regola viene valutata in base alla confidenza — la proporzione di transazioni con l'antecedente che contengono anche il conseguente. Le regole al di sotto della confidenza minima vengono scartate.
Formula
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}Le regole sopravvissute vengono classificate per lift, che confronta la confidenza osservata con la frequenza di base del conseguente. Un lift superiore a 1 segnala che l'antecedente e il conseguente co-occorrono più del caso; un lift vicino a 1 indica indipendenza; un lift inferiore a 1 indica un'associazione negativa. Le regole con il lift più alto sono le scoperte più attuabili.
Formula
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}Errori comuni
- Eseguire Apriori direttamente in MethodMind — caricare il proprio dataset transazionale, impostare le soglie di supporto e confidenza, e ricevere regole di associazione classificate con supporto, confidenza e lift, insieme a una visualizzazione di rete delle connessioni di item più forti.
- Impostare il supporto minimo troppo basso e affogare in migliaia di regole di bassa qualità senza filtrarle per lift.
- Interpretare un'alta confidenza come causalità piuttosto che co-occorrenza — una regola con alta confidenza ma lift vicino a 1 è banale.
- Applicare Apriori a caratteristiche continue senza prima discretizzarle, il che gonfia lo spazio degli item e degrada i risultati.
- Riportare regole senza verificare se le dimensioni dei campioni degli insiemi di item sono sufficientemente grandi da fidarsi delle stime del supporto.
Domande frequenti
Rilevamento frodi: far emergere pattern di co-occorrenza insoliti nei log delle transazioni che deviano dai carrelli normali.
Qual è la differenza tra supporto, confidenza e lift?
Il supporto è la frazione di tutte le transazioni che contengono l'insieme di item — misura la prevalenza. La confidenza è la probabilità condizionata che il conseguente appaia dato l'antecedente — misura l'affidabilità della regola. Il lift è il rapporto tra la confidenza osservata e la frequenza di base del conseguente; un lift superiore a 1 mostra un'associazione positiva genuina piuttosto che una coincidenza guidata dalla popolarità dell'item.
Quando dovrei scegliere FP-Growth rispetto ad Apriori?
FP-Growth comprime il database in una struttura ad albero e lo analizza senza scansioni complete ripetute, rendendolo sostanzialmente più veloce su dataset di grandi dimensioni o quando il supporto minimo è basso. Apriori è più facile da capire e implementare e funziona bene su dataset da piccoli a moderati dove il tempo di esecuzione non è un collo di bottiglia.
Come scelgo il supporto e la confidenza minimi?
Non esiste una regola universale. La pratica comune è eseguire l'algoritmo a diversi livelli di supporto, tracciare il numero di insiemi di item frequenti rispetto al supporto e scegliere un valore nel gomito della curva. La confidenza viene quindi impostata in base alla domanda di business o di ricerca — confidenza più alta per regole mission-critical, più bassa per la scoperta esplorativa. Validare sempre le regole principali rispetto all'esperienza del dominio.
Apriori può gestire dati numerici o continui?
Apriori richiede dati binari di presenza di item. Le variabili continue devono essere discretizzate in intervalli (ad esempio, età in basso/medio/alto) prima di essere codificate come item. Una discretizzazione errata può distorcere gravemente le regole scoperte, quindi la strategia di binning merita un'attenta riflessione.
Apriori implica causalità tra gli item?
Metodi correlati
Fonti
Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.
Apri il riferimento della pubblicazioneCopiato.Apriori algorithm. Wikipedia.
Apri il riferimento della pubblicazioneCopiato.