L’algoritmo Apriori

Analisi del carrello in R

Christopher Bruffaerts

Statistician

Mining di regole associative

Il mining di regole associative permette di scoprire relazioni tra item in grandi basi transazionali.

Questo compito si divide in due sotto-attività:

Generazione di itemset frequenti: trova tutti gli itemset frequenti in un grande insieme di transazioni. Un itemset è frequente se soddisfa una soglia minima di supporto.
Generazione di regole: dagli itemset frequenti sopra, genera regole con confidenza sopra una soglia minima di confidenza.

L’algoritmo Apriori è un classico algoritmo veloce della famiglia del mining di regole associative.

Idea alla base di Apriori

Algoritmo Apriori:

Approccio bottom-up
Genera candidati sfruttando il principio di Apriori

Principio di Apriori:

Se un itemset è frequente, tutti i suoi sottoinsiemi sono frequenti.
- es. se {A,B} è frequente, allora {A} e {B} sono frequenti
Se un itemset è infrequente, tutti i suoi sovrainsiemi sono infrequenti.
- es. se {A} è infrequente, allora {A,B}, {A,C} e {A,B,C} sono infrequenti.

¹ Agrawal e Srikant (1994)

Esempio: itemset da 1

reticolo_itemset2

TID	Transazione
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Soglia di supporto minima = 3/7 = 0,42

Esempio: itemset da 2

reticolo_itemset3

TID	Transazione
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Soglia di supporto minima = 3/7 = 0,42

Esempio: itemset da 3

tutti_gli_itemset

TID	Transazione
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Soglia di supporto minima = 3/7 = 0,42

Esempio: itemset frequenti

reticolo_itemset3

Itemset	Conteggio	Supporto
{A}	3	0,42
{B}	6	0,85
{C}	4	0,57
{D}	5	0,71
{A,B}	3	0,42
{B,C}	3	0,42
{B,D}	4	0,57
{C,D}	3	0,42

¹ Soglia di supporto minima = 3/7 = 0,42

Apriori: generazione delle regole

Dopo la costosa generazione degli itemset frequenti, Apriori genera le regole:

Parte da regole ad alta confidenza con singolo antecedente
- es. {A,C} → {B}
Estende a regole più complesse, con più item a destra
- es. {A,C} → {B, D}

Trucco: potatura delle regole associative

es.: se la regola {B,C,D} → {A} ha bassa confidenza, si possono scartare tutte le regole che hanno A nel conseguente (come {B,D} → {A, C} o {D} → {A,B, C}).

Un primo tentativo con Apriori

Dati transazionali

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

Prima chiamata a apriori: itemset frequenti

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))

Output di Apriori: itemset frequenti

Itemset frequenti

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

reticolo_itemset3

Estrazione di regole con apriori

Parametro: i parametri di mining cambiano le caratteristiche degli itemset o delle regole.

Supporto = 3/7
Confidenza = 60%
Lunghezza minima regola = 2

Chiamata ad apriori per generare regole con argomenti specifici

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )

Estrazione di regole: output

Ispezione delle regole

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4

Ayo berlatih!

Analisi del carrello in R