Le regole di associazione sono uno dei concetti importanti dell’apprendimento automatico e del data mining.

Il classico esempio per comprendere meglio questo concetto è quello di un supermercato in cui i clienti possono acquistare una varietà di articoli.

Quando ci si reca al supermercato lo si fa consapevoli di quello che si vuole acquistare, e ciò cambia a seconda delle esigenze di ognuno di noi. Ad esempio, le neomamme potrebbero più facilmente acquistare prodotti per bambini come latte e pannolini. Le ragazze potrebbero comprare articoli per la moda e il trucco, mentre gli studenti universitari birre e cibi surgelati, ecc.

Solitamente poi, non è un caso che tutte le verdure vengano collocate nella stessa navata, come poi tutti gli articoli caseari vengono messi insieme e i detersivi formano un altro gruppo in una serie di scaffali prossimi tra loro.

Investire tempo e risorse in posizionamenti di prodotti deliberati permette di ridurre il tempo di acquisto di un cliente, nonchè ricorda anche al cliente quali articoli rilevanti potrebbe essere interessato all’acquisto, aiutando così i negozi a vendere.

Capire come queste associazioni vengono a crearsi è importante per un manager logistico. Vediamo in questo articolo cosa esse sono e come poterle calcolare avvalendoci dell’algoritmo Apriori.

Regole di associazione

Le regole di associazione aiutano a scoprire tutte queste relazioni tra elementi da enormi database, aiutando i manager a dislocare prodotti con più alta associazione vicini tra di loro.

L’obiettivo di determinare una regola di associazione è quello di non estrarre le preferenze di un individuo, piuttosto trovare relazioni tra un insieme di elementi di ogni transazione distinta.

Infatti se chi compra spesso il prodotto A, compra spesso anche il prodotto B (e viceversa), allora conviene posizionare vicini tra loro questi prodotti nelle scaffalature. Quindi, si potrebbe valutare di:

Mettere i due item insieme in modo tale che quando un cliente acquista uno dei prodotti non deve andare lontano per acquistare l’altro prodotto.
Focalizzarsi sulle persone che acquistano uno dei prodotti in modo da avvalersi di campagne pubblicitarie per invogliarli ad acquistare l’altro.
Offrire sconti collettivi su questi prodotti se il cliente li acquista entrambi.
Impacchettare insieme sia A che B (ove possibile).

Misurare l’associazione

Capita l’importanza di queste associazioni non ci resta che capire come misurarle.

L’analisi delle regole di associazione è una tecnica per scoprire in che modo gli elementi sono associati tra loro. Esistono tre modi comuni per misurare l’associazione.

Ipotizziamo di avere quattro transazioni con due prodotti acquistati: Pane e burro (l’esempio è a titolo semplificativo, non si vuole qui affermare che ci compra pane compra anche burro e viceversa).

Support

Il supporto è un’indicazione della frequenza con cui gli articoli compaiono nei dati. Matematicamente, il supporto di un prodotto A è la frazione rispetto al numero totale di transazioni in cui si trova il prodotto:

Il supporto per l’item Pane è pari a:

Perché il Pane compare tre volte nelle quattro transazioni di esempio. Per il burro avremo 2/4.

Mentre il supporto di A e B (ossia trovo transazioni dove è incluso sia A che B) è pari a:

Con N il numero delle transazioni totali eseguite. Il supporto di pane e burro è pari così a:

Proprio perché esiste solo una transazione dove i due prodotti sono comprati insieme.

Confidence

La regola della confidenza ci spiega come l’item B è comprato quando è comprato l’item A, espresso come A -> B. Aiuta a scremare le transazioni, aiutando a rispondere:

Di tutte le transazioni che contengono A, quante contengono anche B? La formula per calcolare la confidenza è la seguente:

Quindi la confidenza per aver comprato Pane e Burro insieme è pari a:

Può anche essere interpretata come la probabilità condizionata P(B|A), ovvero la probabilità di trovare il set di articoli B nelle transazioni dato che la transazione contiene già A.

Può dare alcuni spunti importanti, ma ha anche un grosso svantaggio. Tiene conto solo della popolarità del set di elementi A e non della popolarità di B. Se B è ugualmente popolare come A, allora ci sarà una maggiore probabilità che una transazione contenente A conterrà anche B, aumentando così la confidenza.

Difatti questo valore cambia se si inverte la relazione. La confidenza di B -> A, risulta differente rispetto a prima (poiché cambia la frequenza dell’item B):

Per ovviare a questo inconveniente esiste un’altra misura chiamata lift.

Lift

Il lift ci mostra come l’item B è comprato quando è comprato l’item A, mentre viene controllato quanto è popolare l’item B. In pratica è simile alla misura di confidenza, solo che a denominatore viene aggiunto anche il supporto del prodotto B. La formula è così rappresentata:

I valori dei vari supporti sono stati calcolati in precedenza. Per il valore del Lift tra i due prodotti avremo:

Terminologia

Prima di vedere come l’algoritmo Apriori calcola queste regole di associazione è bene dare qualche definizione. Considereremo:

Itemset: gli articoli/item che vengono associati tra loro. Ad esempio 1 itemset è un articolo con un elemento ({a}, {b}, {c}), 2 itemset significa avere 2 articoli come ad esempio {a, b}, {c, d}, {a, c}. Infine k itemset, k elementi ({i1, i2, i3, … ik}, {j1, j2, j3, …. jk}).
Candidati: sono gli item che vengono utilizzati ad ogni fase per essere uniti con itemset frequenti dell’iterazione precedente (L_k-1). Vengono denominati con la lettera C_k.
Itemset Frequenti: gli itemset frequenti sono quelli che hanno un supporto minimo, che non viene eliminato con la potatura (vedi sotto). Quelli di ampiezza k sono denominati con L_k.
Join step: in questa fase si creano L_k,unendo un set di k candidati generati (C_k) con L_k-1. Ad esempio, un itemset a un elemento è fatto per auto-unirsi con sè stesso (ma item differente) per generare un itemset a due elementi.
Pruning (Potatura): La potatura analizza il conteggio di ciascun elemento nel database e se l’elemento candidato (C_k) non soddisfa il supporto minimo, viene considerato poco frequente e quindi rimosso. Questo passaggio viene eseguito per ridurre le dimensioni degli articoli candidati.

Algoritmo Apriori

L’algoritmo Apriori è un algoritmo che è stato proposto per la prima volta da R. Agrawal e R. Srikant nel 1994 (fonte wikipedia).

Si prefigge di trovare i set di elementi più frequenti nel database specificato.

Un articolo A si dice frequente se la sua probabilità P(A) è superiore a un valore minimo di supporto. Se non lo è esso sarà considerato non frequente.

Allo stesso modo se A è comprato insieme a B, viene definita la probabilità (P(A + B)). Se tale probabilità supera il supporto allora i due articoli saranno frequenti altrimenti no.

L’Apriori utilizza un approccio iterativo in cui k-itemset vengono utilizzati per esplorare (k + 1) -itemset. Innanzitutto, la serie di set frequenti composti di 1 elemento viene rilevata eseguendo la scansione del database per accumulare il conteggio di ciascun elemento.

Il set risultante è indicato come L1. Successivamente, L1 viene utilizzato per trovare L2, l’insieme di 2 set di articoli frequenti, che viene utilizzato per trovare L3 e così via, fino a quando non viene trovato alcun k-itemset più frequente. La ricerca di ogni L_krichiede una scansione completa del database.

Una volta trovati i k item più frequenti ci si chiede se possiamo trovare altri candidati da associare agli elementi frequenti nei sottoinsiemi di itemset k-1 (L_k-1): se non vengono trovati ci fermiamo (per l’algoritmo un item composto da due articoli non frequente non rappresenta un itemset frequente di 3 articoli, ma anch’esso è considerato non frequente. Questa viene detta proprietà di anti-monocità della misura di supporto).

I k-itemset frequenti in pratica servono per generare le regole di associazione. Per selezionare regole interessanti, dall’insieme di tutte le regole possibili, vengono applicate varie misure di vincolo come il supporto e confidenza sopra visti.

Principio di funzionamento

Vediamo brevemente un esempio di come funziona questo algoritmo, per capirlo meglio. La seguente tabella mostra un esempio di 6 transazioni distinte:

Scegli una soglia minima

Inizialmente viene fornita una soglia di supporto minima, che può essere anche assunta dall’utente.

Ipotizziamo di scegliere una soglia di supporto minima del 50%. Ciò significa che al di sotto di questa soglia, gli item saranno considerati non frequenti.

Ora questa soglia è moltiplicata per il numero di transazioni per valutare il valore del supporto minimo.

In questo caso abbiamo: 50% * 6 = 0,5 *6 = 3

3 rappresenta il valore del supporto minimo.

Determiniamo anche un valore di confidenza del 70%.

Step 1: Conta ogni Item

In questa fase vengono conteggiati gli item singolarmente in tutte le transazioni. Di conseguenza avremo la serie di candidati C1 mostrata dalla seguente tabella:

Step 1: Escludi gli item che non raggiungono il supporto minimo

Il supporto minimo di 3 item è verificato per i primi 4 articoli, mentre l’ultimo essendo minore di tale valore viene scartato (potatura).

La precedente tabella (L1) include gli item ad un elemento frequenti, che soddisfano il supporto minimo.

Step 2: Forma itemset da due articoli (k = 2)

Ogni articolo viene ora associato agli altri presenti nella tabella precedente in modo da poter valutare le relazioni tra di essi e creare C2. Non è importante l’ordine con cui ciò avviene perché in questa sede l’associazione Mela, Pera, ad esempio è uguale a Pera, Mela. Successivamente contiamo quante volte queste associazioni sono presenti nella tabella iniziale.

Step 2: Escludi gli item che non raggiungono il supporto minimo

Anche qua l’item {Mela, Burro} e {Latte, Burro} non raggiungono il valore di soglia minimo definito in precedenza, quindi vengono scartati. L2 sarà così pari a:

Step 3: Forma itemset da tre articoli (k = 3)

Si ripete la procedura, e creiamo ora itemset da tre articoli, conteggiando anche in quante transazioni vengono trovati.

Attenzione però che ora entra in gioco la proprietà dell’algoritmo per cui tutti i sottoinsiemi di un set di articoli frequente devono anche essere frequenti. In pratica per avere un itemset frequente di 3 elementi, tutti i suoi sottoinsiemi a due elementi devono essere inclusi nel set di item frequenti di 2 elementi (L2). Quindi avremo solamente il successivo candidato (C3):

Abbiamo solo l’associazione frequente {Mela, Pera, Latte} perché solamente {Mela, Pera}, {Pera Latte} e {Mela Latte} sono inclusi in L2, l’itemset frequente a 2 articoli.

Qua ci fermiamo, avendo trovato un solo itemset frequente di tre elementi.

Genera le regole di associazione

Fino ad ora, abbiamo esaminato l’algoritmo Apriori rispetto alla generazione frequente di articoli. Esiste un’altra attività per la quale è possibile utilizzare questo algoritmo, ovvero trovare le regole di associazione in modo efficiente.

Se A è un set di elementi frequente con k elementi, allora ci sono 2^k-2 regole di associazione dei candidati. Quindi avendo k = 3, troviamo 6 associazioni potenziali. Esse sono:

{Mela, Pera} => {Latte}

Confidenza = supporto {Mela, Pera, Latte} / supporto {Mela, Pera} = (3/4) * 100 = 75%

{Mela, Latte} => {Pera}

Confidenza = supporto {Mela, Pera, Latte} / supporto {Mela, Latte} = (3/3) * 100 = 100%

{Pera, Latte} => {Mela}

Confidenza = supporto {Mela, Pera, Latte} / supporto {Pera, Latte} = (3/4) * 100 = 75%

{Mela} => {Pera, Latte}

Confidenza = supporto {Mela, Pera, Latte} / supporto {Mela} = (3/4) * 100 = 75%

{Pera} => {Mela, Latte}

Confidenza = supporto {Mela, Pera, Latte} / supporto {Pera} = (3/5) * 100 = 60%

{Latte} => {Mela, Pera}

Confidenza = supporto {Mela, Pera, Latte} / supporto {Latte} = (3/4) * 100 = 75%

Ciò dimostra che tutte le regole di associazione di cui sopra, fuorchè la penultima, sono forti se la soglia minima di confidenza è del 70%. Quella esclusa viene rifiutata e non utilizzata come regola di associazione forte.

Con questi passaggi, abbiamo identificato un insieme di regole di associazione che soddisfano sia il supporto minimo sia la condizione di confidenza minima. Il numero di tali regole ottenute varierà con i valori definiti inizialmente di supporto minimo e confidenza minima.

Ora, questo sottoinsieme di regole così generate può essere cercato per i più alti valori di lift per prendere decisioni aziendali.

Limitazioni

Uno dei principali fattori che limita l’utilizzo di quest’algoritmo è che risulta computazionalmente costoso. Anche se l’algoritmo apriori riduce il numero di item candidati da considerare, questo numero potrebbe comunque essere enorme quando gli inventari dei negozi sono grandi o quando la soglia di supporto è bassa.

Tuttavia, una soluzione alternativa sarebbe quella di ridurre il numero di confronti utilizzando strutture di dati avanzate, come le tabelle hash, per ordinare i set di elementi candidati in modo più efficiente.

Una seconda limitazione è dovuta alla creazione di associazioni spurie, ossia associazioni che appaiono collegate casualmente ma che in realtà non lo sono (per maggiori informazioni vedi questo link).

L’analisi di grandi inventari comporterebbe più configurazioni di set di elementi e potrebbe essere necessario abbassare la soglia di supporto per rilevare determinate associazioni.

Tuttavia, abbassando la soglia di supporto potrebbe anche aumentare il numero di associazioni spurie rilevate. Per garantire che le associazioni identificate siano generalizzabili, potrebbero essere prima distillate da un set di dati di formazione, e successivamente valutati in un set di dati di test separato.

Conclusione

In questo articolo abbiamo visto le regole di associazione, come misurarle e come funziona l’algoritmo Apriori per calcolare un set di item frequente e valutare tali regole trovate.

L’algoritmo può essere utile in quei settori cui è importante definire delle associazioni tra item, in modo da comprendere le relazioni tra gli stessi. Questo può avvenire:

Nel settore della grande distribuzione organizzata, o nel piccolo negozio al dettaglio, dove si devono scegliere come posizionare i prodotti tra i vari scaffali;
Nel campo dell’istruzione, per scoprire regole e pattern nascosti nell’apprendimento degli studenti.
Nel campo medico, ad esempio per eseguire analisi specifiche del paziente, in modo da identificare la combinazione delle caratteristiche del paziente e dei farmaci che portano a effetti collaterali negativi.
Nelle aziende tecnologiche, in cui l’algoritmo Apriori è utilizzato da Amazon come sistema di raccomandazione di prodotti visualizzati e comprati da clienti simili e da Google per la funzionalità di completamento automatico in modo da capire l’associazione tra le parole cercate nel più famoso motore di ricerca.

Pin2