Che cos'è l'algoritmo Apriori?

Introdotto nel 1994 da Rakesh Agrawal e Ramakrishnan Srikant (link esterno a ibm.com), il nome "Apriori" riconosce la conoscenza precedente di itemset frequenti utilizzati dall'algoritmo nel calcolo. L'algoritmo esegue iterazioni sui dati per identificare i k-itemset, ovvero k elementi che si verificano frequentemente insieme. Utilizza quindi i k-itemset per identificare i k+1 itemset. L'algoritmo Apriori si basa sull'insight che l'aggiunta di elementi a un gruppo acquistato di frequente può solo renderlo meno frequente, non di più. Il processo si basa sulla proprietà Apriori che indica che, se un itemset viene visualizzato frequentemente in un set di dati, anche tutti i relativi sottoinsiemi devono essere frequenti. Al contrario, se un itemset viene identificato come poco frequente, tutti i relativi superset vengono considerati non frequenti.

L'algoritmo Apriori è applicabile a tutti i tipi di set di dati, in particolare quelli generati da database transazionali ed è spesso utilizzato per la market basket analysis a supporto dei sistemi di raccomandazione. Ad esempio, quando si utilizza una piattaforma di e-commerce che vende vestiti e scarpe, un acquirente cerca scarpe e decide di aggiungere un paio di scarpe nere formali al carrello. L'acquirente nota quindi che l'interfaccia consiglia altri articoli da acquistare, come i calzini. Uno dei modi in cui funziona questo sistema di raccomandazione è apprendere i modelli di acquisto dei clienti e associare articoli che solitamente vengono acquistati insieme.

Uno dei maggiori vantaggi dell'utilizzo dell'algoritmo Apriori è la sua semplicità e adattabilità. Tuttavia, gli algoritmi Apriori non sono altrettanto efficienti quando si gestiscono set di dati di grandi dimensioni. Il processo multi-iterazione di generazione di itemset candidati può diventare computazionalmente costoso e richiede molta memoria. Apriori è spesso combinato con altre tecniche per mitigare questi problemi.

La funzione Apriori è integrata in molti linguaggi di programmazione popolari, tra cui Python, Java e R, rendendo la generazione di regole di associazione di qualità insieme a frequenti itemset semplice da integrare in applicazioni o sistemi esistenti.

Ognuno dei passaggi chiave dell'algoritmo Apriori cerca di identificare gli itemset e tutti i loro possibili superset cercando i più frequenti per creare le regole di associazione.

L'algoritmo identifica prima di tutto gli elementi unici, a volte chiamati 1-itemset, nel set di dati, insieme alle loro frequenze. Poi, combina gli elementi che appaiono insieme con una probabilità superiore a una soglia specificata in itemset candidati e filtra gli itemset poco frequenti per ridurre il costo di calcolo in fasi successive. Questo processo, noto come mining di itemset frequenti, cerca solo gli itemset con frequenze significative.

Utilizzando la proprietà Apriori, l'algoritmo combina ulteriormente gli itemset frequenti per formare itemset più grandi. Vengono eliminate le combinazioni di itemset più grandi e con una probabilità inferiore. Ciò riduce ulteriormente lo spazio di ricerca e rende il calcolo più efficiente.

L'algoritmo ripete i passaggi 1 e 2 fino a quando tutti gli itemset frequenti che soddisfano la probabilità di soglia definita vengono generati in modo esaustivo. Ogni iterazione genera associazioni più complesse e complete negli itemset.

Una volta che Apriori ha creato gli itemset, è possibile studiare la forza delle associazioni e delle relazioni generate.

L'algoritmo Apriori utilizza le metriche di supporto, confidenza e lift per definire i criteri operativi e migliorare l'efficienza delle prestazioni.

Il supporto è definito come il rapporto tra il numero di volte in cui un elemento si presenta nelle transazioni e il numero totale di transazioni. Questa metrica definisce quindi la probabilità che si verifichi ogni singolo elemento nelle transazioni. La stessa logica può essere estesa agli itemset.

$S\left(I_A\right)=\frac{OCC\left(I_A\right)}{ToTalTransaCTions}$

dove I_A è l'elemento A, Occ (I_A) è il numero di occorrenze dell'elemento A e S (I_A) equivale al supporto dell'articolo A

Ad esempio, in un negozio retail, 250 transazioni su 2000 nell'arco di un giorno potrebbero includere l'acquisto di mele. Utilizzando la formula:

$S\left(I_{Apples}\right)=\frac{250}{2000}=\mathrm{0,125}$

Questo risultato implica che c'è una probabilità del 12,5% che le mele siano state acquistate quel giorno.

È possibile indicare una soglia minima di supporto richiesta quando si applica l'algoritmo Apriori. Ciò significa che qualsiasi elemento o itemset con supporto inferiore al supporto minimo specificato sarà considerato poco frequente.

La metrica di confidenza identifica la probabilità che elementi o itemset si trovino insieme negli itemset. Ad esempio, se in una transazione sono presenti due elementi, si presuppone che l'esistenza di un elemento porti all'altro. Il primo elemento o itemset è l'antecedente e il secondo è il conseguente. La confidenza è quindi definita come il rapporto tra il numero di transazioni aventi sia l'antecedente che il conseguente e il numero di transazioni che hanno solo l'antecedente. Questo scenario è rappresentato come:

$C(A,B)=\frac{OCC(A\cap B)}{OCC\left(A\right)}$

dove A è l'antecedente, B è il conseguente e C (A, B) è la confidenza secondo cui A porta a B.

Estendendo l'esempio precedente, supponiamo che ci siano 150 transazioni in cui mele e banane sono state acquistate insieme. La confidenza è calcolata come:

$C(Apples,Bananas)=\frac{150}{250}=\mathrm{0,6}$

Questo risultato indica una probabilità del 60% che un acquisto di mele porti poi a un acquisto di banane. Allo stesso modo, supponendo un totale di 500 transazioni di banane, la confidenza che un acquisto di banane porti a un acquisto di mele viene calcolata come:

$C(Bananas,Apples)=\frac{150}{500}=\mathrm{0,3}$

Qui c'è solo il 30% di possibilità che l'acquisto di una banana porti all'acquisto di una mela.

Sebbene la confidenza sia una buona misura della probabilità, non è una garanzia di una chiara associazione tra gli elementi. Il valore della confidenza potrebbe essere alto per altri motivi. Per questo motivo, viene applicata una soglia di confidenza minima per filtrare le associazioni debolmente probabili durante il mining con le regole di associazione.

Il lift è il fattore in base al quale la probabilità che l'elemento A porti all'elemento B è superiore alla probabilità dell'elemento A. Questa metrica quantifica la forza dell'associazione tra A e B. Può aiutare a indicare se esiste una relazione reale tra gli elementi dell'itemset o se vengono raggruppati per coincidenza. 

$L(A,B)=\frac{C(A,B)}{S\left(A\right)}$ 


Dove L_A,B è il lift per l'elemento A che porta all'elemento B, C_A,B è la confidenza secondo cui l'elemento A porta all'elemento B, S_A è il supporto per l'elemento A.

Per l'esempio precedente, possiamo vedere che: 

$L(Apples,Bananas)=\frac{\mathrm{0,6}}{\mathrm{0,125}}=\mathrm{4,8}$

L'elevato valore nominale indica che la probabilità che mele e banane vengano acquistate insieme è 4,8 volte superiore a quella delle mele acquistate da sole. Inoltre, si può osservare che: 

$L(Bananas,Apples)=\frac{\mathrm{0,3}}{\mathrm{0,25}}=\mathrm{1,2}$

Il basso valore di lift indica che l'acquisto di una banana che porta all'acquisto di una mela potrebbe essere solo una coincidenza.

In molti casi applicare un approccio brute force (link esterno a ibm.com) per calcolare le soglie di supporto e confidenza per ogni regola e poi eliminare le regole che non soddisfano una soglia può essere proibitivo dal punto di vista computazionale. Per rendere più efficiente l'applicazione dell'algoritmo Apriori, viene spesso combinato con altre tecniche di mining di regole di associazione. Due dei più comuni sono l'algoritmo FP-Growth (link esterno a ibm.com) e la sua variante FP-Max per ridurre i vincoli di memoria e calcolo. L'algoritmo Apriori può anche essere combinato con alberi decisionali, in cui l'algoritmo Apriori identifica l'itemset frequente e la tecnica degli alberi decisionali aiuta a identificare le regole di associazione.

Un'altra variante popolare dell'algoritmo Apriori è il Dynamic Itemset Counting (DIC) (link esterno a ibm.com) che inizia a contare i potenziali itemset in anticipo, senza attendere la registrazione di tutte le transazioni. Il DIC divide il set di dati in segmenti più piccoli ed elabora ogni segmento separatamente. Questa segmentazione consente l'arresto anticipato quando l'algoritmo non è in grado di identificare itemset frequenti, ma il partizionamento dei dati consente anche di ridurre significativamente il costo di calcolo.

Gli algoritmi Apriori possono essere utili anche in applicazioni di intelligenza artificiale basate sull'apprendimento non supervisionato come gli algoritmi di clustering quando i dati lo supportano. Aiuta a identificare relazioni e associazioni tra entità apparentemente indipendenti, raggruppandole in possibili cluster.

La scoperta e il raggruppamento degli itemset ha diverse applicazioni e l'algoritmo Apriori viene talvolta definito come la prima cosa che i data miner provano a causa della sua versatilità. Esamineremo alcuni dei casi d'uso comuni in diversi settori.

Una delle applicazioni più comuni dell'algoritmo Apriori è la market basket analysis. I rivenditori analizzano la cronologia degli acquisti dei clienti e ottimizzano la disposizione nei negozi posizionando gli articoli acquistati di frequente uno vicino all'altro o sullo stesso scaffale. Le piattaforme di e-commerce utilizzano gli algoritmi di Apriori per studiare le relazioni basate sui prodotti in base alle preferenze degli utenti e l'analisi dei modelli di acquisto per creare sistemi efficienti di raccomandazione dei clienti. Lo stesso tipo di analisi può essere utilizzato per ottimizzare l'acquisto di servizi, ad esempio scegliendo corsi di formazione da un catalogo, o consigliando altri tipi di copertura nella scelta dell'assicurazione.

L'algoritmo Apriori può essere utilizzato per trovare forti regole di associazione tra sintomi e malattie per migliorare l'efficienza della diagnosi e ideare piani di trattamento mirati. Ad esempio, quali pazienti hanno maggiori probabilità di sviluppare il diabete (link esterno a ibm.com) o il ruolo che la dieta o lo stile di vita svolgono nella malattia (link esterno a ibm.com). Può anche aiutare a identificare i fattori associati alle reazioni avverse ai farmaci.

Gli algoritmi Apriori sono applicabili anche nei database non transazionali. Gli analisti di dati utilizzano spesso Apriori per il web usage mining, per analizzare i dati clickstream e per interpretare il comportamento degli utenti.

Un'altra applicazione comune dell'algoritmo Apriori è quella di identificare modelli fraudolenti nelle transazioni finanziarie. L'identificazione di specifici modelli di acquisto come possibilmente fraudolenti consente a un istituto finanziario di agire rapidamente per sospendere le transazioni o contattare il titolare di un conto.