Apriori-algoritmen

Kundkorgsanalys i R

Christopher Bruffaerts

Statistician

Associationsregelutvinning

Associationsregelutvinning används för att upptäcka intressanta samband mellan objekt i en stor transaktionsdatabas.

Denna uppgift kan delas in i två deluppgifter:

Generering av frekventa objektmängder: identifiera alla frekventa objektmängder i en potentiellt stor transaktionsdatabas. En objektmängd anses frekvent om den uppfyller ett minsta supporttröskelvärde.
Regelgenerering: från ovanstående frekventa objektmängder genereras associationsregler med ett konfidensvärde över ett minsta konfidenströskelvärde.

Apriori-algoritmen är en klassisk och snabb utvinningsalgoritm inom klassen av associationsregelalgoritmer.

Idén bakom apriori-algoritmen

Apriori-algoritmen:

Nedifrån-och-upp-strategi
Genererar kandidatobjektmängder med hjälp av apriori-principen

Apriori-principen:

Om en objektmängd är frekvent måste alla dess delmängder också vara frekventa.
- t.ex. om {A,B} är frekvent är både {A} och {B} frekventa
Om en objektmängd är infrequent är alla dess supermängder infrekventa.
- t.ex. om {A} är infrequent är {A,B}, {A,C} och {A,B,C} infrekventa.

¹ Agrawal and Srikant (1994)

Exempel: 1-objektmängd

item_set_lattice2

TID	Transaktion
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}

¹ Minsta supporttröskelvärde = 3/7 = 0.42

Exempel: 2-objektmängder

item_set_lattice3

TID	Transaktion
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}

¹ Minsta supporttröskelvärde = 3/7 = 0.42

Exempel: 3-objektmängder

all_itemsets

TID	Transaktion
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}

¹ Minsta supporttröskelvärde = 3/7 = 0.42

Exempel: frekventa objektmängder

item_set_lattice3

Objektmängd	Antal	Support
{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

¹ Minsta supporttröskelvärde = 3/7 = 0.42

Apriori: regelgenerering

Efter den beräkningsintensiva genereringen av frekventa objektmängder genererar apriori regler:

Börja med regler med hög konfidens och ett enda antecedent
- t.ex. {A,C} $\rightarrow$ {B}
Bygg mer komplexa regler med fler objekt på höger sida
- t.ex. {A,C} $\rightarrow$ {B, D}

Tips: beskärning av associationsregler

t.ex.: om regeln {B,C,D} $\rightarrow$ {A} har låg konfidens kan alla regler som innehåller objektet A i sin konsekvens förkastas (t.ex. regeln {B,D} $\rightarrow$ {A, C} eller {D} $\rightarrow$ {A,B, C}).

Ett första försök med apriori

Transaktionsdata

inspect(head(trans,2))

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

Första anropet till apriori-funktionen – frekventa objektmängder

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

Apriori-utdata – frekventa objektmängder

Frekventa objektmängder

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

item_set_lattice3

Extrahera regler med apriori-funktionen

Parameter: utvinningsparametrarna styr egenskaperna hos de utvunna objektmängderna eller reglerna.

Support = 3/7
Konfidens = 60%
Minsta regellängd = 2

Anrop till apriori-funktionen för regelgenerering med specifika argument

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

Extrahera regler: utdata

Granska reglerna

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

Nu kör vi en övning!

Kundkorgsanalys i R