Algoritmus apriori

Market Basket Analysis v R

Christopher Bruffaerts

Statistician

Dolování asociačních pravidel

Dolování asociačních pravidel umožňuje odhalovat zajímavé vztahy mezi položkami ve velkých transakčních databázích.

Tuto úlohu lze rozdělit na dva dílčí úkoly:

Generování frekventovaných množin: nalezení všech frekventovaných množin v potenciálně rozsáhlé databázi transakcí. Množina je frekventovaná, pokud splňuje minimální práh podpory.
Generování pravidel: z frekventovaných množin se generují asociační pravidla s důvěrou přesahující minimální práh důvěry.

Algoritmus apriori je klasický a rychlý algoritmus patřící do třídy algoritmů pro dolování asociačních pravidel.

Myšlenka algoritmu apriori

Algoritmus apriori:

Přístup zdola nahoru
Generuje kandidátní množiny pomocí principu apriori

Princip apriori:

Pokud je množina frekventovaná, musí být frekventované i všechny její podmnožiny.
- např. pokud je {A,B} frekventovaná, jsou frekventované i {A} a {B}
Pokud je množina nefrekventovaná, jsou nefrekventované i všechny její nadmnožiny.
- např. pokud je {A} nefrekventovaná, pak {A,B}, {A,C} a {A,B,C} jsou také nefrekventované.

¹ Agrawal and Srikant (1994)

Příklad: 1-položková množina

množina_položek_mříž2

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

¹ Minimální práh podpory = 3/7 = 0,42

Příklad: 2-položkové množiny

množina_položek_mříž3

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

¹ Minimální práh podpory = 3/7 = 0,42

Příklad: 3-položkové množiny

všechny_množiny_položek

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

¹ Minimální práh podpory = 3/7 = 0,42

Příklad: frekventované množiny položek

množina_položek_mříž3

Množina	Počet	Podpora
{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

¹ Minimální práh podpory = 3/7 = 0,42

Apriori: generování pravidel

Po výpočetně náročném generování frekventovaných množin apriori generuje pravidla:

Začíná pravidly s vysokou důvěrou a jediným předchůdcem
- např. {A,C} $\rightarrow$ {B}
Buduje složitější pravidla s více položkami na pravé straně
- např. {A,C} $\rightarrow$ {B, D}

Trik: prořezávání asociačních pravidel

např.: pokud má pravidlo {B,C,D} $\rightarrow$ {A} nízkou důvěru, lze vyřadit všechna pravidla obsahující položku A v důsledku (například {B,D} $\rightarrow$ {A, C} nebo {D} $\rightarrow$ {A,B, C}).

První použití funkce apriori

Transakční data

inspect(head(trans,2))

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

První volání funkce apriori – frekventované množiny

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

Výstup apriori – frekventované množiny

Frekventované množiny

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

množina_položek_mříž3

Extrakce pravidel pomocí funkce apriori

Parametry: parametry dolování ovlivňují vlastnosti dolovaných množin nebo pravidel.

Podpora = 3/7
Důvěra = 60 %
Minimální délka pravidla = 2

Volání funkce apriori pro generování pravidel s konkrétními argumenty

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

Extrakce pravidel: výstup

Prohlížení pravidel

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

Lass uns üben!

Market Basket Analysis v R