Algoritmul apriori

Analiza coșului de cumpărături în R

Christopher Bruffaerts

Statistician

Minarea regulilor de asociere

Minarea regulilor de asociere permite descoperirea relațiilor interesante dintre articole dintr-o bază de date tranzacționale.

Această sarcină se împarte în două subtask-uri:

Generarea seturilor de articole frecvente: identificarea tuturor seturilor frecvente dintr-o bază de date de tranzacții. Un set este considerat frecvent dacă satisface un prag minim de suport.
Generarea regulilor: pe baza seturilor frecvente, se generează reguli de asociere cu o încredere peste un prag minim de încredere.

Algoritmul apriori este un algoritm clasic și rapid din clasa algoritmilor de minare a regulilor de asociere.

Ideea din spatele algoritmului apriori

Algoritmul apriori:

Abordare de jos în sus
Generează seturi candidate exploatând principiul apriori

Principiul apriori:

Dacă un set de articole este frecvent, atunci toate subseturile sale sunt de asemenea frecvente.
- ex. dacă {A,B} este frecvent, atunci atât {A} cât și {B} sunt frecvente
Pentru un set de articole infrequent, toate superseturile sale sunt infrequente.
- ex. dacă {A} este infrequent, atunci {A,B}, {A,C} și {A,B,C} sunt infrequente.

¹ Agrawal și Srikant (1994)

Exemplu: set de 1 articol

rețea de seturi de articole 2

TID	Tranzacție
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}

¹ Pragul minim de suport = 3/7 = 0.42

Exemplu: seturi de 2 articole

rețea de seturi de articole 3

TID	Tranzacție
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}

¹ Pragul minim de suport = 3/7 = 0.42

Exemplu: seturi de 3 articole

toate seturile de articole

TID	Tranzacție
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}

¹ Pragul minim de suport = 3/7 = 0.42

Exemplu: seturi de articole frecvente

rețea de seturi de articole 3

Set de articole	Număr	Suport
{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

¹ Pragul minim de suport = 3/7 = 0.42

Apriori: generarea regulilor

După generarea costisitoare a seturilor frecvente, apriori generează reguli:

Se pornește cu reguli de înaltă încredere cu un singur antecedent
- ex. {A,C} $\rightarrow$ {B}
Se construiesc reguli mai complexe, cu mai multe articole în consecvent
- ex. {A,C} $\rightarrow$ {B, D}

Truc: tăierea regulilor de asociere

ex.: dacă regula {B,C,D} $\rightarrow$ {A} are încredere scăzută, toate regulile care conțin articolul A în consecvent pot fi eliminate (precum {B,D} $\rightarrow$ {A, C} sau {D} $\rightarrow$ {A,B, C}).

Prima utilizare a funcției apriori

Date tranzacționale

inspect(head(trans,2))

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

Primul apel al funcției apriori - seturi de articole frecvente

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

Rezultatul apriori - seturi de articole frecvente

Seturi de articole frecvente

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

rețea de seturi de articole 3

Extragerea regulilor cu funcția apriori

Parametri: parametrii de minare definesc caracteristicile seturilor sau regulilor extrase.

Suport = 3/7
Încredere = 60%
Lungime minimă a regulii = 2

Apel al funcției apriori pentru generarea regulilor cu argumente specifice

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

Extragerea regulilor: rezultate

Inspectarea regulilor

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

Să exersăm!

Analiza coșului de cumpărături în R