Regole di associazione
- Introdotto da
- Agrawal, R., Imielinski, T., & Swami, A.
- Anno
- 1993
- Tipo
- Unsupervised pattern discovery
- Famiglia
- Machine learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'apprendimento delle regole di associazione è una tecnica non supervisionata che scopre pattern di co-occorrenza — implicazioni 'se X allora Y' — all'interno di grandi set di dati transazionali.
Formalizzata originariamente da Agrawal, Imielinski e Swami (1993) per l'analisi del carrello della spesa nei supermercati, è ora ampiamente applicata nelle raccomandazioni e-commerce, nell'informatica sanitaria, nella bioinformatica e nella ricerca comportamentale.
L’intuizione alla base del metodo
Immagina di scansionare milioni di ricevute di acquisto e di chiedere: quali combinazioni di prodotti tendono ad apparire insieme? L'estrazione di regole di associazione risponde a questa domanda contando quante volte gli insiemi di articoli co-occorrono (supporto), quanto affidabilmente un articolo ne predice un altro (confidenza) e se la co-occorrenza è più forte del caso (lift). Regole come 'pannolini → birra' con alta confidenza e lift rivelano pattern comportamentali genuini piuttosto che coincidenze, rendendo questo uno strumento esplorativo potente quando non si dispone di una variabile di esito da supervisionare.
Storia
L'apprendimento delle regole di associazione è stato formalmente introdotto da Agrawal, Imielinski e Swami alla conferenza ACM SIGMOD del 1993, motivato dalla sfida di estrarre dati dai database delle transazioni dei supermercati. Il loro successivo articolo del 1994 ha introdotto l'algoritmo Apriori, fornendo un metodo computazionale efficiente. Il campo è cresciuto rapidamente negli anni '90 e 2000, con FP-growth (Han et al., 2000) che in seguito ha offerto ulteriori miglioramenti di velocità. Le regole di associazione rimangono una tecnica fondamentale nei curricula di data mining e sono regolarmente applicate nell'analisi al dettaglio, sanitaria e web.
Quando usarlo
Utilizzare le regole di associazione quando il vostro obiettivo è la scoperta esplorativa di pattern di co-occorrenza in dati transazionali o codificati in binario — carrelli della spesa, co-diagnosi cliniche, clickstream, batterie di item di sondaggi o profili di espressione genica. Il metodo è non supervisionato e non richiede etichette di esito, rendendolo ideale per la generazione di ipotesi. Non utilizzarlo quando si dispone di una variabile di esito definita e si cerca di predire (utilizzare invece la classificazione o la regressione supervisionata); quando i dati sono continui e non sono stati discretizzati in modo significativo; quando le dimensioni del campione sono piccole (itemset sparsi producono stime di supporto inaffidabili); o quando l'output delle regole verrà confuso con l'inferenza causale — le regole di associazione sono puramente correlazionali.
Limiti e considerazioni
- Richiede che i dati siano transazionali o discretizzati in binario; le caratteristiche continue necessitano di discretizzazione, che introduce scelte arbitrarie.
- Il numero di regole può essere enorme; il filtraggio post-hoc e la classificazione per lift o altre misure di interesse sono obbligatori.
- Le soglie di supporto e confidenza devono essere impostate dal ricercatore; i risultati sono sensibili a queste scelte.
- Le regole sono puramente correlazionali — le affermazioni causali richiedono ulteriori studi (es. esperimento o quasi-esperimento).
- Computazionalmente costoso su set di dati con itemset molto grandi anche con potatura.
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 è richiesta una variabile di esito etichettata, consentendo la scoperta di pattern aperti.
- Output interpretabile: ogni regola è un'istruzione LEGGI-SCRIVI leggibile dall'uomo con supporto, confidenza e lift quantificati.
- Scalabile a database transazionali molto grandi tramite euristiche di potatura (Apriori, FP-growth).
- Applicabile in diversi domini ovunque la co-occorrenza in record codificati in binario sia significativa.
- Generazione di ipotesi: fa emergere co-occorrenze inaspettate che possono guidare analisi di conferma successive.
Applicazioni
- Analisi del carrello della spesa: identificare quali prodotti vengono acquistati frequentemente insieme per guidare il posizionamento dei prodotti e le promozioni.
- Raccomandazione e-commerce: generare suggerimenti del tipo 'i clienti che hanno acquistato X hanno acquistato anche Y'.
- Scoperta di co-morbilità cliniche: trovare insiemi di diagnosi, farmaci o sintomi che co-occorrono nei registri dei pazienti.
- Bioinformatica: rilevare geni co-espressi o varianti genetiche co-occorrenti in campioni diversi.
- Estrazione di utilizzo del web: scoprire pattern di clickstream comuni e sequenze di navigazione sui siti web.
- Ricerca comportamentale e di sondaggi: trovare insiemi di item di questionari o comportamenti che co-occorrono tra i rispondenti.
Come funziona
Come funziona
Il set di dati è rappresentato come una matrice di transazioni binaria: ogni riga è una transazione e ogni colonna è un possibile articolo, con un 1 che indica la presenza dell'articolo. Questa rappresentazione sparsa e ampia è il formato di input principale; articoli non binari o quantitativi devono essere discretizzati prima di questo passaggio.
Vengono identificate tutte le combinazioni di articoli (itemset) la cui frequenza nel database delle transazioni soddisfa una soglia minima di supporto impostata dall'utente. Il principio Apriori — ogni sottoinsieme di un itemset frequente è anch'esso frequente — riduce drasticamente lo spazio di ricerca combinatorio, rendendo l'enumerazione trattabile anche su cataloghi di grandi dimensioni.
Formula
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|} \geq \text{min\_sup}Per ogni itemset frequente, vengono generate come regole candidate tutte le possibili suddivisioni antecedente-conseguente (X → Y dove X e Y sono sottoinsiemi disgiunti non vuoti). Il numero di candidati può essere elevato, quindi il successivo passaggio di filtraggio è essenziale.
Formula
X \Rightarrow Y, \quad X \cap Y = \emptyset
Ogni regola candidata viene valutata in base alla sua confidenza: la probabilità condizionale che Y sia presente dato che X è presente. Solo le regole che superano una soglia minima di confidenza vengono mantenute, filtrando gli antecedenti che predicono il conseguente solo marginalmente meglio del tasso di base.
Formula
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}Le regole mantenute vengono classificate in base al lift, il rapporto tra il supporto congiunto osservato e il supporto atteso in caso di indipendenza. Un lift maggiore di 1 segnala una genuina associazione positiva; un lift vicino a 1 indica che gli articoli co-occorrono non più del caso; un lift inferiore a 1 indica un'associazione negativa. L'ordinamento per lift fa emergere le regole più attuabili e non banali.
Formula
\text{lift}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Errori comuni
- Impostare un supporto minimo troppo basso, che inonda l'output con regole spurie a bassa frequenza che non generalizzano.
- Ignorare il lift e riportare tutte le regole ad alta confidenza, molte delle quali possono semplicemente riflettere articoli con alta frequenza di base.
- Trattare le regole scoperte come causali senza ulteriore validazione (es. confondere 'birra e pannolini co-occorrono' con 'la birra causa l'acquisto di pannolini').
- Applicare regole di associazione a dati continui senza una discretizzazione basata su principi, producendo regole che dipendono interamente da confini di intervallo arbitrari.
- Trascurare le preoccupazioni relative ai confronti multipli quando vengono generate migliaia di regole e selezionate selettivamente.
Domande frequenti
Come scelgo le soglie minime di supporto e confidenza?
Non esiste una regola universale. Iniziare esplorando la distribuzione del supporto dei singoli articoli, quindi impostare il supporto minimo abbastanza basso da catturare i pattern di interesse ma abbastanza alto da garantire che gli itemset appaiano in almeno un numero assoluto significativo di transazioni. Una confidenza minima di 0,6-0,8 è un intervallo di partenza comune, ma la conoscenza del dominio e la classificazione basata sul lift dovrebbero guidare la selezione finale.
Qual è la differenza tra confidenza e lift, e quale dovrei privilegiare?
La confidenza misura quante volte Y segue X tra le transazioni contenenti X, ma ignora il tasso di base di Y. Il lift corregge questo dividendo la confidenza per il supporto marginale di Y. Una regola con alta confidenza ma lift vicino a 1 aggiunge poca informazione oltre al sapere che Y è comune. Privilegiare il lift quando si filtrano associazioni genuinamente non banali.
Le regole di associazione possono essere utilizzate per la predizione?
Sono principalmente descrittive ed esplorative piuttosto che predittive. Sebbene sia possibile utilizzare regole con un conseguente fisso (un singolo articolo target) per la classificazione — una tecnica chiamata classificazione associativa — l'estrazione standard di regole di associazione non ottimizza una funzione di perdita predittiva e non dovrebbe sostituire i modelli supervisionati quando è disponibile un esito etichettato.
Il mio set di dati contiene variabili continue. Posso ancora usare le regole di associazione?
Solo dopo la discretizzazione. Le variabili continue devono essere raggruppate in intervalli categorici (es. fasce d'età, quintili) prima di essere codificate come articoli binari. La scelta dei confini degli intervalli influisce sostanzialmente su quali regole emergono, quindi le decisioni di discretizzazione dovrebbero essere motivate teoricamente e riportate in modo trasparente.
In che modo le regole di associazione differiscono dall'analisi di correlazione?
La correlazione (es. r di Pearson) misura la relazione lineare tra due variabili continue. Le regole di associazione scoprono pattern di co-occorrenza tra insiemi di articoli binari — di qualsiasi dimensione combinatoria — in dati transazionali. Le metriche (supporto, confidenza, lift) sono basate sulla frequenza piuttosto che sui momenti, e l'output è un insieme di regole LEGGI-SCRIVI leggibili dall'uomo piuttosto che un singolo coefficiente numerico.
Metodi correlati
Fonti
Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 207–216.
Apri il riferimento DOICopiato.Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.
ISBN: 978-0-13-312890-1Copiato.