Association Rule Mining (Apriori)
- Introdotto da
- Rakesh Agrawal & Ramakrishnan Srikant
- Anno
- 1994
- Tipo
- Unsupervised pattern discovery algorithm
- Famiglia
- Pattern mining
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'Association Rule Mining è una tecnica di data-mining non supervisionata che scopre pattern di co-occorrenza tra item in dataset transazionali.
Introdotta formalmente da Agrawal, Imieliński e Swami nel 1993, e raffinata con il fondamentale algoritmo Apriori da Agrawal e Srikant nel 1994, identifica regole del tipo X ⇒ Y — il che significa che le transazioni contenenti l'itemset X tendono a contenere anche l'itemset Y — quantificate da supporto, confidenza e lift.
L’intuizione alla base del metodo
Immaginate un registro di scontrini di un supermercato: se migliaia di clienti che comprano pane e burro comprano anche latte, quel pattern merita attenzione. L'Association Rule Mining funziona come un meticoloso bibliotecario che setaccia ogni scontrino, conta quante volte le combinazioni di item appaiono insieme, ed evidenzia le combinazioni che superano una frequenza minima. Una volta trovati i gruppi frequenti, l'algoritmo chiede: dati questi item, con quale affidabilità questo predice il prossimo item? Questa logica a due passaggi, prima frequenza poi confidenza, è il cuore di Apriori.
Storia
L'articolo fondamentale di Agrawal, Imieliński e Swami (1993) definì il problema delle regole di associazione nel contesto dei dati transazionali dei supermercati. L'articolo VLDB del 1994 di Agrawal e Srikant introdusse l'algoritmo Apriori e la sua efficiente strategia di pruning, rendendo praticabile il mining su larga scala. Lavori successivi produssero FP-Growth (Han et al., 2000), che evita del tutto la generazione di candidati, ed ECLAT, che esegue il mining in formato dati verticale — stabilendo una ricca famiglia algoritmica ora centrale nei curricula di data mining.
Quando usarlo
L'Association Rule Mining è adatto a grandi dataset transazionali dove l'obiettivo è scoprire pattern di co-occorrenza senza una variabile target predefinita. Presuppone che gli item siano binari (presenti/assenti) per transazione. È appropriato per l'analisi del carrello della spesa (market basket analysis), sistemi di raccomandazione, analisi di clickstream web e scoperta di co-diagnosi mediche. Non è adatto per dati continui o ordinali a meno che non siano pre-discretizzati, per dataset con dimensionalità molto elevata (spazio candidato esponenziale), o quando è richiesta un'inferenza causale piuttosto che associativa. Le alternative includono FP-Growth per un'enumerazione più rapida degli itemset frequenti e il sequence mining quando l'ordine temporale è importante.
Limiti e considerazioni
- Spazio candidato esponenziale: il numero di regole cresce combinatoriamente con il numero di item distinti.
- Il framework supporto-confidenza può produrre regole fuorvianti quando le frequenze di base degli item variano ampiamente (richiede aggiustamento del lift).
- Il modello binario di transazione richiede la discretizzazione di variabili continue, introducendo perdita di informazione.
- Soglie di supporto minimo elevate fanno perdere regole rare ma preziose; soglie basse generano migliaia di regole triviali.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Completamente non supervisionato: non sono necessari dati etichettati o un target predefinito.
- Output interpretabile: le regole sono affermazioni leggibili dall'uomo del tipo se-allora con supporto e confidenza quantificati.
- Scalabile tramite potatura (pruning) Apriori; la variante FP-Growth elimina del tutto le scansioni ripetute del database.
- Indipendente dal dominio: applicato in settori come retail, sanità, analisi web e bioinformatica.
Applicazioni
- Retail: posizionamento prodotti e raccomandazioni di cross-selling da log transazionali di punti vendita.
- Sanità: analisi di co-occorrenza di diagnosi, procedure o farmaci in cartelle cliniche elettroniche.
- Analisi web: scoperta di pattern di clickstream per raccomandazione di pagine e ottimizzazione della navigazione.
- Bioinformatica: identificazione di insiemi di geni co-espressi e motivi di interazione proteica.
- Cybersecurity: rilevamento di eventi di rete correlati indicativi di pattern di intrusione.
Come funziona
Come funziona
L'algoritmo scansiona il database delle transazioni D per contare quante volte appare ogni itemset X. Un itemset è dichiarato frequente — e posto in L_k — solo quando il suo supporto (la frazione di transazioni che lo contengono) raggiunge o supera la soglia minima di supporto definita dall'utente σ_min. Il processo inizia con singoli item (k=1) e costruisce iterativamente insiemi candidati più grandi.
Formula
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}La proprietà anti-monotonica del supporto afferma che ogni sottoinsieme di un itemset frequente deve essere esso stesso frequente. Apriori sfrutta questo fatto eliminando ogni itemset candidato k i cui sottoinsiemi (k-1) non siano tutti presenti nell'insieme frequente verificato L_{k-1}. Questo riduce drasticamente lo spazio di ricerca, evitando costose scansioni del database per itemset che non possono essere frequenti.
Formula
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_kDa ogni itemset frequente X ∪ Y, l'algoritmo genera regole X ⇒ Y dove X e Y sono sottoinsiemi disgiunti. Una regola viene conservata solo quando la sua confidenza — la probabilità condizionale di Y dato X, calcolata come supporto(X ∪ Y) / supporto(X) — raggiunge o supera la soglia minima di confidenza γ_min. Questo passaggio converte la co-occorrenza grezza in affermazioni predittive direzionali.
Formula
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}Le regole conservate vengono classificate e filtrate per lift, che misura quanto sia più probabile che Y appaia con X rispetto al caso. Lift > 1 indica correlazione positiva oltre l'indipendenza; lift = 1 indica indipendenza; lift < 1 indica una correlazione negativa. Ulteriori misure di interesse come la convinzione (conviction) e il leverage possono ulteriormente affinare l'insieme di regole per l'implementazione pratica.
Formula
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Errori comuni
- Impostare il supporto minimo troppo basso inonda l'analista di regole spurie; la selezione della soglia richiede conoscenza del dominio o convalida incrociata (cross-validation).
- Confusione tra associazione statistica e causalità: un lift elevato non implica che X causi Y.
- Ignorare la distribuzione di frequenza degli item: item comuni dominano le regole e soffocano associazioni significative di item rari.
- Trattare la sola confidenza come metrica di qualità; una regola con alta confidenza ma basso lift potrebbe non fare meglio del caso.
Domande frequenti
Qual è la differenza tra supporto, confidenza e lift?
Il supporto misura quanto frequentemente un itemset appare nel dataset nel suo complesso. La confidenza misura la probabilità condizionale del conseguente dato l'antecedente. Il lift normalizza la confidenza per la frequenza marginale del conseguente, rivelando se la co-occorrenza supera quanto ci si aspetterebbe sotto indipendenza. Tutte e tre le metriche sono necessarie insieme per una valutazione robusta delle regole.
Come l'algoritmo Apriori riduce il costo computazionale?
Apriori sfrutta la proprietà anti-monotonica: se un itemset è infrequente, tutti i suoi superinsiemi devono essere anch'essi infrequenti. Scartando ogni candidato i cui sottoinsiemi non siano tutti verificati come frequenti, l'algoritmo pota vaste porzioni dello spazio di ricerca prima di contare, riducendo drasticamente il numero di passaggi del database richiesti rispetto all'enumerazione brute-force.
Quando dovrei usare FP-Growth invece di Apriori?
FP-Growth è preferibile quando il dataset è grande e la soglia di supporto minimo è bassa, poiché comprime il database delle transazioni in una struttura compatta FP-tree ed estrae pattern direttamente senza generare candidati espliciti. Questo elimina scansioni complete ripetute del database, rendendolo sostanzialmente più veloce di Apriori su dataset densi con molti itemset frequenti.
Metodi correlati
Fonti
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.
Apri il riferimento DOICopiato.Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.
Apri il riferimento della pubblicazioneCopiato.