Algorytm apriori

Analiza koszyka zakupowego w R

Christopher Bruffaerts

Statistician

Eksploracja reguł asocjacyjnych

Eksploracja reguł asocjacyjnych pozwala odkrywać interesujące zależności między elementami w dużej transakcyjnej bazie danych.

Zadanie to można podzielić na dwa podzadania:

Generowanie częstych zbiorów elementów: wyznaczenie wszystkich częstych zbiorów w potencjalnie dużej bazie transakcji. Zbiór jest częsty, jeśli spełnia minimalne progowe wsparcie.
Generowanie reguł: na podstawie powyższych częstych zbiorów generowanie reguł asocjacyjnych z ufnością powyżej minimalnego progowego poziomu ufności.

Algorytm apriori to klasyczny i szybki algorytm eksploracji należący do klasy algorytmów reguł asocjacyjnych.

Idea algorytmu apriori

Algorytm apriori:

Podejście oddolne
Generuje kandydatów na zbiory elementów, korzystając z zasady apriori

Zasada apriori:

Jeśli zbiór elementów jest częsty, wszystkie jego podzbiory są również częste.
- np. jeśli {A,B} jest częsty, to {A} i {B} są częste
Jeśli zbiór jest niezbyt częsty, wszystkie jego nadzbiory są niezbyt częste.
- np. jeśli {A} jest niezbyt częsty, to {A,B}, {A,C} i {A,B,C} są niezbyt częste.

¹ Agrawal and Srikant (1994)

Przykład: 1-elementowe zbiory

zbiory_elementów_krata2

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

¹ Minimalne progowe wsparcie = 3/7 = 0,42

Przykład: 2-elementowe zbiory

zbiory_elementów_krata3

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

¹ Minimalne progowe wsparcie = 3/7 = 0,42

Przykład: 3-elementowe zbiory

wszystkie_zbiory

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

¹ Minimalne progowe wsparcie = 3/7 = 0,42

Przykład: częste zbiory elementów

zbiory_elementów_krata3

Zbiór	Liczba	Wsparcie
{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

¹ Minimalne progowe wsparcie = 3/7 = 0,42

Apriori: generowanie reguł

Po kosztownym obliczeniowo etapie generowania częstych zbiorów apriori generuje reguły:

Zaczyna od reguł wysokiej ufności z jednym poprzednikiem
- np. {A,C} $\rightarrow$ {B}
Buduje bardziej złożone reguły z większą liczbą elementów po prawej stronie
- np. {A,C} $\rightarrow$ {B, D}

Trick: przycinanie reguł asocjacyjnych

np.: jeśli reguła {B,C,D} $\rightarrow$ {A} ma niską ufność, wszystkie reguły zawierające A w następniku można odrzucić (np. {B,D} $\rightarrow$ {A, C} lub {D} $\rightarrow$ {A,B, C}).

Pierwsze użycie apriori

Dane transakcyjne

inspect(head(trans,2))

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

Pierwsze wywołanie funkcji apriori – częste zbiory elementów

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

Wynik apriori – częste zbiory elementów

Częste zbiory elementów

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

zbiory_elementów_krata3

Wydobywanie reguł funkcją apriori

Parametry: parametry eksploracji wpływają na właściwości wydobywanych zbiorów lub reguł.

Wsparcie = 3/7
Ufność = 60%
Minimalna długość reguły = 2

Wywołanie funkcji apriori do generowania reguł z określonymi argumentami

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

Wydobywanie reguł: wyniki

Inspekcja reguł

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

Czas na ćwiczenia!

Analiza koszyka zakupowego w R