Het apriori-algoritme

Market Basket-analyse in R

Christopher Bruffaerts

Statistician

Association rule mining

Met association rule mining ontdek je interessante relaties tussen items in een grote transactiedatabase.

Deze taak bestaat uit twee subtaken:

Genereren van frequente itemsets: vind alle frequente itemsets in een (grote) transactiedatabase. Een itemset is frequent als deze voldoet aan een minimale supportdrempel.
Regelgeneratie: genereer op basis van de frequente itemsets regels met een confidence boven een minimale confidencedrempel.

Het apriori-algoritme is een klassiek en snel algoritme binnen association rule mining.

Idee achter het apriori-algoritme

Het apriori-algoritme:

Bottom-up-aanpak
Genereert kandidaat-itemsets met het apriori-principe

Apriori-principe:

Als een itemset frequent is, dan zijn al haar subsets ook frequent.
- bv. als {A,B} frequent is, dan zijn {A} en {B} frequent
Is een itemset infrequent, dan zijn al haar supersets infrequent.
- bv. als {A} infrequent is, dan zijn {A,B}, {A,C} en {A,B,C} infrequent.

¹ Agrawal en Srikant (1994)

Voorbeeld: 1-itemset

item_set_lattice2

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

¹ Minimale supportdrempel = 3/7 = 0,42

Voorbeeld: 2-itemsets

item_set_lattice3

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

¹ Minimale supportdrempel = 3/7 = 0,42

Voorbeeld: 3-itemsets

all_itemsets

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

¹ Minimale supportdrempel = 3/7 = 0,42

Voorbeeld: frequente itemsets

item_set_lattice3

Itemset	Aantal	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

¹ Minimale supportdrempel = 3/7 = 0,42

Apriori: regelgeneratie

Na de rekenintensieve generatie van frequente itemsets genereert apriori regels:

Begin met hoge-confidence regels met één antecedent
- bv. {A,C} $\rightarrow$ {B}
Bouw complexere regels met meer items rechts
- bv. {A,C} $\rightarrow$ {B, D}

Truc: regels snoeien

bv.: als {B,C,D} $\rightarrow$ {A} lage confidence heeft, kun je alle regels met A in het consequent verwerpen (zoals {B,D} $\rightarrow$ {A, C} of {D} $\rightarrow$ {A,B, C}).

Een eerste poging met apriori

Transactionele data

inspect(head(trans,2))

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

Eerste aanroep van apriori — frequente itemsets

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

Uitvoer van apriori — frequente itemsets

Frequente itemsets

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

Regels extraheren met apriori

Parameter: de miningparameters bepalen de eigenschappen van de gevonden itemsets of regels.

Support = 3/7
Confidence = 60%
Minimale regellengte = 2

Aanroep van apriori voor regelgeneratie met specifieke argumenten

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

Regels extraheren: uitvoer

Regels inspecteren

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

Laten we oefenen!

Market Basket-analyse in R