[e-mail] 2006

Analiza asocjacji

[e-mail] 2006

Sformułowanie problemu

Celem analizy asocjacji jest wykrycie w bazie danych zawierającej
transakcje elementów, które występują razem w wielu transakcjach.

Efektem analizy asocjacji są reguły asocjacyjne, które są probabilistycznym
stwierdzeniem o współwystępowaniu pewnych zdarzeń w bazie danych i
ma szczególne zastosowanie przy rzadkich zbiorach transakcyjnych.

Rozwinięciem analizy asocjacji jest analiza sekwencji, która pozwala na
uwzględnienie powiązania zdarzeń (elementów transakcji) w czasie.

Analiza asocjacji pozwala odpowiedzieć na pytania:



Jakie produkty są kupowane najczęściej razem ?



Jakie jest prawdopodobieństwo, że klient, który odwiedzi w internecie stronę A
odwiedzi również stronę B ?



Jakie produkty kupują klienci, którzy korzystają z promocji A ?

[e-mail] 2006

Przykłady zastosowania

Zwiększenie przychodów z transakcji (cross-selling)



e-sklep - na przykład do trafnej rekomendacji on-line zakupu

następnego towaru

web mining - może być użyta do grupowania stron
odwiedzanych przez użytkownika podczas jednej sesji,
optymalizacja struktury serwisu internetowego.

wyświetlenie odpowiedniej reklamy na stronie WWW

supermarket - na przykład do budowania ofert
specjalnych skłaniających do zwiększonych zakupów,
lub doskonalenia ekspozycji produktów na półkach
(analiza koszykowa – basket analysis)

[e-mail] 2006

Reguły asocjacyjne

I – zbiór wszystkich elementów, jakie występują w transakcjach (np. Zbiór

wszystkich książek sprzedawanych w księgarni internetowej)

t – pojedyncza transakcja, jest podzbiorem zdarzeń elementów I, t ⊆ I

(zbiór książek, które kupił klient podczas jednej wizyty w księgarni)

T – rodzina wszystkich transakcji ( zbiór wszystkich transackji dokonanych

przez klientów interentowej księgarni)

Niech X, Y – rozłączne podzbiory T elementów . (wzorce).

X ⊆ I , Y ⊆ I , X ∩ Y = ∅

t zawiera X ⇔ X ⊆ t

Częstością fr(X) wzorca elementów jest liczba przypadków w danych

spełniająca X, czyli zawierająca wszystkie elementy ze zbiory X.

Reguła asocjacji: X ⇒ Y

jeżeli transakcja zawiera zbiór X to zawiera również zbiór Y,

[e-mail] 2006

Miary istotności reguł
asocjacyjnych

Confidence level (zaufanie, pewność, dokładność, ufność) –
częstość występowania następnika,. przy założeniu że
poprzednik jest spełniony. Pokazuje ile transakcji, które
zawierały poprzednik X zawiera również następnik Y.

Support (wsparcie reguły)– odsetek transakcji w danych
historycznych, które spełniają regułę - częstość występowania
reguły w zbiorze wszystkich rekordów.

Expected confidence – prawdopodobieństwo wystąpienia
następnika (bez względu na poprzednika)

Lift (przyrost) – mówi o ile wzrasta prawdopodobieństwo
wystąpienia następnika jeżeli spełniony jest poprzednik.

}

|

{

}

|

{

t

X

T

t

count

t

Y

t

X

T

t

count

confidence

⊆

∈

⊆

∧

⊆

∈

=

}

{

}

|

{

T

count

t

Y

t

X

T

t

count

support

⊆

∧

⊆

∈

=

}

{

}

|

{

T

count

t

Y

T

t

count

confidence

expected

⊆

∈

=

confidence

expected

confidence

lift =

[e-mail] 2006

Algorytm wyszukiwania reguł
(apriori)

Iteracyjne wyszukiwanie „częstych” zbiorów elementów występujących w
transakcjach. „Częsty” zbiór danych oznacza zbiór, którego częstość (frequency)
przekracza założony poziom wsparcia (support)



Generacja zbiorów



wyliczenie częstości występowania zbiorów i selekcja

n-ta iteracja wyszukuje wszystkie n - elementowe „częste” zbiory, w oparciu o wyniki
działania poprzedniej iteracji. Przechodząc od zbiorów częstych o rozmiarze k-1 do
zbiorów częstych o rozmiarze k, możemy odrzucać wszystkie zbiory rozmiaru k, które
zawierają podzbiór k-1 elementowy, sam w sobie nie będący częstym na k-1
poziomie.

Generacja reguł asocjacyjnych w oparciu wyznaczone „częste” zbiory elementów. Dla
reguły {x1, x2, x3,}→ x4 jest konieczne, aby zarówno {x1, x2, x3 x4} jak i {x1, x2, x3}
było zbiorem częstym. Poziom zaufania jest obliczany jako:



confidence = fr {x1, x2, x3, x4} / fr {x1 x2, x3}.

Mocne reguły są to reguły, są to te reguły, których ufność przekracza założony
poziom.

[e-mail] 2006

Przykład działania algorytmu

Wyszukać reguły asocjacyjne, przyjmując graniczne wartości współczynników:

support

= 50%

confidence

= 80%,

Id

Items

T01

{A,C,D}

T02

{B,C,E}

T03

{A,B,C,E}

T04

{B,E}

[e-mail] 2006

A – 2 (50%)

AB

ABC

ABCD

ABCE

ABD

ABDE

ABE

AC

ACD

ACDE

ACE

AD

AD

ADE

ADE

AE

B – 3 (75%)

BC

BCD

BCDE

BCE

BD

BDE

BE

C – 3 (75%)

CD

CD

CDE

CDE

CE

D – 1 (25%)

DE

E – 3 (75%)

Id

Items

T01

{A,C,D}

T02

{B,C,E}

T03

{A,B,C,E}

T04

{B,E}

ABDE

[e-mail] 2006

Id

Items

T01

{A,C,D}

T02

{B,C,E}

T03

{A,B,C,E}

T04

{B,E}

A – 2 (50%)

AB –1 (25%)

ABC

ABCE

ABE

AC -2 (50%)

ACE

AE – 1 (25%)

B – 3 (75%)

BC – 2 (50%)

BCE

BE –3 (75%)

C – 3 (75%)

CE – 2 (50%)

E – 3 (75%)

[e-mail] 2006

A – 2 (50%)

B – 3 (75%)

BC – 2 (50%)

BCE -2 (50%)

BE –3 (75%)

C – 3 (75%)

CE – 2 (50%)

E – 3 (75%)

Id

Items

T01

{A,C,D}

T02

{B,C,E}

T03

{A,B,C,E}

T04

{B,E}

[e-mail] 2006

A – 2 (50%)

B – 3 (75%)

BC – 2 (50%)

BCE -2 (50%)

BE –3 (75%)

C – 3 (75%)

CE – 2 (50%)

E – 3 (75%)

Regu

Regu

ł

ł

y asocjacyjne:

y asocjacyjne:

{B} ⇒

⇒

⇒

⇒

{C} confidence = 66%

{C} ⇒

⇒

⇒

⇒

{B} confidence = 66%

{B} ⇒

⇒

⇒

⇒

{E} confidence = 100%

{E} ⇒

⇒

⇒

⇒

{B} confidence = 100%

{E} ⇒

⇒

⇒

⇒

{C} confidence = 66%

{C} ⇒

⇒

⇒

⇒

{E} confidence = 66%

{BC} ⇒

⇒

⇒

⇒

{E} confidence = 100%

{BE} ⇒

⇒

⇒

⇒

{C} confidence = 66%

{CE} ⇒

⇒

⇒

⇒

{B} confidence = 100%

{B} ⇒

⇒

⇒

⇒

{CE} confidence = 66%

{C} ⇒

⇒

⇒

⇒

{BE} confidence = 66%

{E} ⇒

⇒

⇒

⇒

{BC} confidence = 66%

[e-mail] 2006

Modyfikacje wydajnościowe

Algorytm apriori dokonuje kilkukrotnego pełnego przeglądy zbioru
transakcji (liczba iteracji zależy od liczby elementów w „częstym” zbiorze).

Partition-based Apriori – wymaga tylko dwóch przeglądów zbioru danych.
Zbiór jest dzielony na partycje o rozmiarze umożliwiającym załadowanie ich

do pamięci operacyjnej.



W pierwszym przebiegu, algorytm wyszukuje w każdej partycji lokalnie częste
zbiory.



W drugim przebiegu, wyliczane jest wsparcie dla wyznaczonych częstych
zbiorów w całym zbiorze. Jeżeli zbiór jest częsty w całej bazie danych, musi być
częsty przynajmniej w jednej partycji.

Algorytmy oparte o próbkę danych: na podstawie próbki wyznaczane są
„częste” zbiory, natomiast ufność i wsparcie wyliczane jest w drugim

przebiegu w oparciu o cały zbiór danych.

Algorytmy inkrementalnej aktualizacji wyznaczonego zbioru reguł.

[e-mail] 2006

Analiza asocjacji dla danych
hierarchicznych

Dla analizy danych hierarchicznych,
reprezentacja transakcji w postaci elementów
detalicznych musi zostać rozszerzona o
elementy z wyższego poziomu hierarchii.

[e-mail] 2006

FP-growth alghorithm

Frequent-Pattern growth – reguły
generowane są z pominięciem kosztownego
procesu generacji kandydujących „częstych”
wzorców.

Algorytm budowania drzewa na przykładzie:



Budowana jest lista L „częstych”
jednoelementowych zbiorów, uporządkowana
malejąco według częstości.

L = {(f, 4), (c, 4), (a, 3), (b, 3), (m, 3), (p, 3)}



W kolejnych iteracjach każda transakcja
modyfikuje drzewo FP, zawierające
początkowo wyłącznie korzeń ROOT

afcelpmn

T05

bcksp

T04

bfhjo

T03

abcflmo

T02

facdgimp

T01

Items

TID

[e-mail] 2006

FP-tree

afcelpmn

T05

bcksp

T04

bfhjo

T03

abcflmo

T02

facdgimp

T01

Items

TID

[e-mail] 2006

FP tree

Generacja wzorców na podstawie listy
L, wybór odpowiednich ścieżek z
drzewa, wyznaczenie „częstych”
zbiorów.

X1 = {f, c, a, b, m, p}



{f, c, a, m, p} - 2



{c,b,p} -1



{c,p } -3

X2 = {f, c, a, b, m}



{f, c, a,m} -2



{f,c,a,b,m} -1



{ f, c, a, m} -3

X3 = {f, c, a, b}



{f,c,a,b} -1



{f,b} -1



{c,b} – 1



X4 = {f, c, a }



{f, c, a} – 3



X5 = {f, c}



{f, c } - 3



X6 = {f}

ROOT

f
4

c
3

a
3

m
2

p
2

b
1

m
1

b
1

c
1

b
1

p
1

[e-mail] 2006

Lift

Nie wszystkie reguły, które mają wystarczające wysokie wartości współczynników confidence
oraz support automatycznie można przyjąć jako interesujące (poprawne).

Przykład:
Przebadano 5 000 studentów.
60 % gra w koszykówkę (3000)
75% je rano owsiankę (3750)
40 % gra w koszykówkę i je owsiankę (2000).

support

= 0.4

confidence

= 0.6%.

gra w koszykówkę ⇒ je owsiankę

Ale ogólny poziom jedzenie owsianki jest wyższy niż w przypadku koszykarzy, co oznacza, że w
rzeczywistości fakty grania w koszykówkę i jedzenia owsianki są ze sobą powiązane negatywnie.

Dlatego należy dodatkowo brać pod uwagę współczynnik lift. Powinien on być większy od
jedności. W tym przypadku:

1

88

,

0

%

75

%

66

<

=

=

lift

[e-mail] 2006

Zadanie 1

Dla podanego zbioru
transakcji oraz
granicznych wartości
parametrów:



Confidence = 60%



Support=25%

Należy wyznaczyć:



„częste” zbiory



Reguły asocjacyjne



Reguły asocjacyjne, które

nie są interesujące.

C D F G

T08

A B G

T07

D F G

T06

B C G

T05

A D F B

T04

C D E G A

T03

A C D F

T02

A B C D

T01

Items

TID

[e-mail] 2006

Zadanie 2

Dla podanego zbioru transakcji oraz
granicznych wartości parametrów:



Confidence = 60%



Support=30%

należy wyznaczyć:



„częste” zbiory



„częste” zbiory na poziomie

zagregowanym przyjmując następującą

hierarchę:

A={A1, A2, A3}

B={B1,B2}

C={C1,C2,C3}

D={D1, D2}

E = {E1,E2}



Wyznaczyć reguły asocjacyjne dla

grup produktów zdefiniowanych

powyżej.

C1 D2 E2

T06

A3 C3 E2

T05

B1 C1 E1

T04

B2 C2 E2

T03

A2 C1 D1

T02

A1 B1 C2

T01

Items

TID

[e-mail] 2006

Literatura

Hand David, Mannila Heikki, Smyth
Padhraic „Eksploracja danych”, WNT 2005

Mehmed Kantardzic „Data Mining:
Concepts, Models, Methods, and
Algorithm” Wiley & Sons 2003