L’algoritmo A-Priori ha un semplice obiettivo, trovare oggetti comprati assieme dentro dei carrelli, cioè trovare le regole di associazione degli elementi all’interno di un insieme di dati.
Il nome A-Priori deriva da come l’algoritmo opera, cioè senza avere nessuna conoscenza effettiva dei dati, ma lavorando sull’intuizione delle associazioni fra gli elementi.
Quando un cliente compra in un supermercato ha di solito una lista delle cose che vuole comprare. Ogni cliente ha bisogni diversi, dalla casalinga al lavoratore single, ma dietro questi clienti ci sono pattern di oggetti comprati spesso assieme. Scoprire questi pattern è molto utile in quanto permette di fare promozioni questi oggetti quando sono comprati assieme.
Un problema che tratta le regole di associazione di elementi si basa su un Dataset formato in questo modo:
| Transazioni | Cestino |
| 1 | {“Mela”,”Lampone”,”Ananas”} |
| 2 | {“Mela”,”Kiwi”,”Ananas”} |
| 3 | {“Lampone”,”Ananas”} |
| 4 | {“Banana”,”Kiwi”,”Ananas”} |
| 5 | {“Kiwi”} |
| 6 | {“Mela”,”Kiwi”} |
| … | … |
Abbiamo cioè delle transazioni con carrelli di frutta comprati assieme, dobbiamo trovare quindi quando un elemento è stato comprato assieme ad un altro.
L’algoritmo utilizza un approccio bottom-up, parte cioè dai singoli elementi per arrivare poi a creare insiemi di oggetti.
L’effettività dell’algoritmo A-Priori si basa sul fatto che l’insieme degli oggetti frequenti derivato dall’insieme di tutti gli oggetti è monotono.
Per monotono si intende questo:
Se per il nostro Dataset, l’insieme di elementi {“A”,”B”,”C”} è il più frequente (cioè l’insieme di elementi che compare più spesso), allora i sottoinsiemi di questo (cioè {“A”,”B”},{“B”,”C”},{“A”,”C”},{“A”},{“B”},{“C”}) saranno a loro volta fra i più frequenti.
Trovando cioè la transizione più lunga più frequente, sappiamo automaticamente che tutti i sottoinsieme derivati da questa sono frequenti!
Un altro vantaggio dell’algoritmo A-Priori è che riduce la memoria necessaria a individuare gli insiemi di oggetti associati. Senza l’algoritmo A-Priori dovremmo enumerare tutti i gli insiemi possibili di oggetti a 2 a 2, a 3 a 3, a 4 a 4 e trovare poi i più frequenti nel nostro Dataset.
Le regole associative dei nostri dati si basano sugli attributi che legano i valori delle transazioni. Le regole associative sono nella forma A=>B, che si legge come: Le transazioni in cui compare A compare anche B.
Le regole associative sono soddisfatte quando superano due valori statistici: Il supporto e la confidenza.
Per supporto intendo la percentuale di transazioni che contengono sia A che B sul totale. Per confidenza invece intendo la percentuale percentuale di transazioni che contengono sia A che B sul numero di transazioni che contengono A.
Nel nostro caso precedente se prendiamo il dataset della frutta troviamo che:
Supporto(Mela,Kiwi) = 2/6
Confidenza(Mela,Kiwi) = 2/2
Abbiamo cosi’ notato che la confidenza che Mela e Kiwi siano comprate assieme è molto alta mentre il numero valore di supporto è basso.
Formalmente quindi l’algoritmo A-Priori si basa sull’estrarre regole di associazione in un dato Dataset con un supporto superiore al minimo stabilito e/o una confidenza superiore alla minima stabilita.
Le regole che soddisfano questi dati sono dette Regole di associazione forte.
Nel prossimo articolo illustrerò lo pseudo codice e il codice per l’algoritmo A-Priori che utilizza come metrica il supporto.