Odkrywanie asocjacji

Agenda

Wprowadzenie

Sformułowanie problemu

Typy reguł asocjacyjnych

Geneza problemu

Geneza problemu odkrywania reguł asocjacyjnych:

problem analizy koszyka zakupów (MBA – Market Basket Analysis)

Dane:

baza danych zawieraj

ą

ca informacje realizowanych

Cel:

znalezienie grup produktów, które klienci supermarketu najcz

ęś

ciej kupuj

ą

razem

Analiza koszyka zakupów

Cel analizy MBA:

znalezienie naturalnych wzorców zachowa

ń

konsumenckich klientów

Wykorzystanie wzorców zachowa

ń

organizacji półek w supermarkecie

opracowania akcji promocyjnych

opracowania katalogu oferowanych produktów

Zastosowanie MBA

Znaleziony wzorzec:

„kto

ś

kto kupuje pieluszki, najcz

ęś

ciej kupuje równie mleko w proszku”

Akcja promocyjna: (typowy trick)

Ogło

ś

obni

ż

k

ę

cen pieluszek, jednocze

ś

nie podnie

ś

mleka w proszku

Organizacja sklepu:

Staraj si

ę

umieszcza

ć

produkty kupowane wspólnie w przeciwległych

ko

ń

cach sklepu, zmuszaj

ą

c klientów do przej

ś

cia przez cały sklep

MBA

znajduje zastosowanie wsz

ę

dzie tam, gdzie „klienci” nabywaj

ą

ł

ą

cznie

pewien

zbiór

dóbr

lub

usług

(analiza

pogody,

telekomunikacja, bankowo

ść

, diagnostyka medyczna, techniczna)

Model koszyka zakupów

Model koszyka zakupów jest pewna abstrakcja umo

ż

liwiaj

ą

ca

modelowanie relacji wiele-do-wiele pomi

ę

dzy encjami „produkty” i

„koszyki”.

Formalnie, model koszyka zakupów mo

ż

na opisa

ć

za pomoc

ą

tzw.

tablicy obserwacji.

Tablica obserwacji

Dany jest zbiór atrybutów A= {A

1

, A

2

, ..., A

n

} oraz zbiór obserwacji T =

{T

1

, T

2

, ..., T

m

}

TR_id

A

1

A

2

A

3

A

4

A

5

T

1

1

0

0

0

1

T

2

1

1

1

1

1

T

3

1

0

1

0

0

T

4

0

0

1

0

1

T

5

0

1

1

1

1

T

6

1

1

1

0

1

T

7

1

0

1

1

0

T

8

1

1

1

0

0

Tablica obserwacji

Elementy tablicy obserwacji:

Atrybuty tablicy reprezentuj

ą

wyst

ą

pienia encji „produkty”

Wiersze tablicy reprezentuj

ą

wyst

ą

pienia encji „koszyki”

Dodatkowy atrybut TR_id – warto

ś

ciami atrybutu s

ą

identyfikatory

poszczególnych obserwacji

Pozycja T

i

[A

j

] = 1 tablicy wskazuje, e i-ta obserwacja zawiera

wyst

ą

pienie j-tego atrybutu

Tablica obserwacji

Elementy tablicy obserwacji:

„koszyki” = studenci, „produkty” = wykłady oferowane przez uczelni

ę

MBA – poszukiwanie wykładów, które studenci wybieraj

ą

najcz

ęś

ciej ł

ą

cznie

„koszyki” = strony WWW, „produkty” = słowa kluczowe

poszukiwanie stron WWW opisanych tymi samymi, lub podobnymi lub
podobnymi, zbiorami słów kluczowych (prawdopodobnie, znalezione strony
dotycz

ą

podobnej problematyki)

Skala problemu

Rozwi

ą

zanie problemu MBA musi by

ć

skalowane:

Supermarket sprzedaje ponad 150 000 produktów i przechowuje informacje o
miliardach wykonanych transakcji rocznie

Web zawiera kilkadziesi

ą

t miliardów stron i zawiera wiele milionów słów

Reguły asocjacyjne

Wynikiem analizy koszyka jest zbiór reguł asocjacyjnych postaci

nast

ę

puj

ą

cej relacji:

{(A

i1

= 1)

∧

...

∧

(A

ik

= 1)}

→

{(A

ik+1

= 1)

∧

...

∧

(A

ik+l

= 1)} (1)

Interpretacja reguły:

„je

ż

eli klient kupił produkty A

i1

, A

i2

, ..., A

ik

, to prawdopodobnie kupił równie

produkty A

ik+1

, A

ik+2

, ..., A

ik+l

”

Reguł

ę

asocjacyjn

ą

(1) mo

ż

na przedstawi

ć

jednoznacznie w równowa

ż

nej

postaci

θ → ϕ

: (A

i1

, A

i2

, ..., A

ik

)

→

(A

ik+1

, A

ik+2

, ..., A

ik+l

)

Z ka

ż

d

ą

reguł

ą

asocjacyjn

ą

θ → ϕ

zwi

ą

zane s

ą

dwie podstawowe miary

okre

ś

laj

ą

ce statystyczn

ą

wa

ż

no

ść

i sił

ę

reguły:

wsparcie - sup(

θ→ϕ

)

ufno

ść

- conf(

θ→ϕ

)

Reguły asocjacyjne

Statystyczna wa

ż

no

ść

i siła reguły:

Wsparciem sup reguły asocjacyjnej

θ → ϕ

nazywac b

ę

dziemy stosunek liczby

obserwacji, które spełniaja warunek

θ ∧ ϕ

,do liczby wszystkich obserwacji

(wsparcie reguły = prawdopodobienstwu zaj

ś

cia zdarzenia

θ ∧ ϕ

)

Ufno

ś

ci

ą

conf reguły asocjacyjnej

θ → ϕ

nazywac b

ę

dziemy stosunek liczby

obserwacji, które spełniaja warunek

θ ∧ ϕ

, do liczby obserwacji, które spełniaja

warunek

θ

(ufno

ść

reguły = warunkowemu prawdopodobienstwu p(

ϕ

ϕ

ϕ

ϕ

|

θθθθ

)

Klasyfikacja reguł asocjacyjnych

Klasyfikacja reguł asocjacyjnych ze wzgl

ę

du na

Typ przetwarzanych danych

Wymiarowo

ść

przetwarzanych danych

Stopie

ń

abstrakcji przetwarzanych danych

Inne typy reguł asocjacyjnych

Asocjacje vs. analiza korelacji

Klasyfikacja reguł asocjacyjnych
(typ przetwarzanych danych)

Mo

ż

na wyró

ż

ni

ć

:

binarne reguły asocjacyjne

ilo

ś

ciowe reguły asocjacyjne

Reguł

ę

asocjacyjn

ą

nazywamy binarn

ą

, je

ż

eli dane wystepujace w

regule sa danymi (zmiennymi) binarnymi.

Reguł

ę

asocjacyjna nazywamy ilosciow

ą

, je

ż

eli dane wystepujace w

regule sa danymi ciagłymi i/lub kategorycznymi

Klasyfikacja reguł asocjacyjnych
(typ przetwarzanych danych)

Binarna reguła asocjacyjna:

pieluszki = 1

→

mleko w proszku=1

(reprezentuje współwyst

ę

powanie danych)

Ilo

ść

iowa reguła asocjacyjna:

wiek = ’30...40’

∧

wykształcenie = ‘wy

ż

sze’

→

opcja_polityczna =‘demokrata’

(reprezentuje współwyst

ę

powanie wartosci danych

Klasyfikacja reguł asocjacyjnych
(wymiarowo

ść

przetwarzanych danych)

Mo

ż

na wyró

ż

ni

ć

:

jednowymiarowe reguły asocjacyjne

wielowymiarowe reguły asocjacyjne

Regułe asocjacyjn

ą

nazywamy jednowymiarow

ą

, je

ż

eli dane

wyst

ę

puj

ą

ce w regule reprezentuj

ą

t

ę

sam

ą

dziedzin

ę

warto

ś

ci

Reguł

ę

asocjacyjna nazywamy wielowymiarow

ą

, je

ż

eli dane

wyst

ę

puj

ą

ce w regule reprezentuj

ą

ró

ż

ne dziedziny warto

ś

ci

Klasyfikacja reguł asocjacyjnych
(wymiarowo

ść

przetwarzanych danych)

Jednowymiarowa reguła asocjacyjna:

pieluszki = 1

→

mleko w proszku=1

(reprezentuje współwyst

ę

powanie danych)

Wielowymiarowa reguła asocjacyjna:

wiek = ’30...40’

∧

wykształcenie = ‘wy

ż

sze’

→

opcja_polityczna =‘demokrata’

(reprezentuje współwyst

ę

powanie warto

ś

ci danych

Stopie

ń

abstrakcji przetwarzanych

Jednopoziomowa reguła asocjacyjna:

pieluszki_Pampers = 1

→

mleko_Bebiko2 =1

Wielopoziomowa reguła asocjacyjna:

pieluszki_Pampers = 1

∧

mleko_Bebiko2 =1

→

ż

ywno

ść

_dla_niemowl

ą

t = 1

(produkt

ż

ywno

ść

_dla_niemowl

ą

t reprezentuje pewna abstrakcj

ę

,

b

ę

d

ę

c

ą

generalizacja okre

ś

lonych produktów)

Odkrywanie binarnych reguł
asocjacyjnych

Dane:

I={i

1

, i

2

, ..., i

n

}: zbiór literałów, nazywanych dalej elementami

Transakcja T: zbiór elementów, takich

ż

e T

⊆

I i T

≠ ∅

Baza danych D: zbiór transakcji

Transakcja T wspiera element x

∈

I, je

ż

eli x

∈

T

Transakcja T wspiera zbiór X

⊆

I, je

ż

eli T wspiera ka

ż

dy element ze zbioru

X, X

⊆

T

Reguły asocjacyjne – miary

Binarna reguła asocjacyjna

Binarn

ą

reguł

ą

asocjacyjn

ą

(krótko, reguł

ą

asocjacyjn

ą

) nazywamy relacj

ę

postaci X

→

Y, gdzie X

⊂

I, Y

⊂

I, i X

∩

Y =

∅

Wsparcie

Reguła X

→

Y posiada wsparcie sup w bazie danych D, 0

≤

sup

≤

1,je

ż

eli

sup% transakcji w D wspiera zbiór X

∪

Y

Ufno

ść

Reguła X

→

Y posiada ufno

ść

conf w bazie danych D, 0

≤

conf

≤

1,je

ż

eli

conf% transakcji w D, które wspieraj

ą

zbiór X, wspieraj

ą

równie

ż

Y

Reguły asocjacyjne – miary

Wsparcie (X

→

Y)

oznacza liczb

ę

transakcji w bazie danych, które potwierdzaj

ą

dan

ą

reguł

ę

–

miara wsparcia jest symetryczna wzgl

ę

dem zbiorów stanowi

ą

cych

poprzednik i nast

ę

pnik reguły

Ufno

ść

(X

→

Y)

oznacza stosunek liczby transakcji zawieraj

ą

cych X

∪

Y do liczby transakcji

zawieraj

ą

cych Y – miara ta jest asymetryczna wzgl

ę

dem zbiorów

stanowi

ą

cych poprzednik i nast

ę

pnik reguły

Reguły asocjacyjne – miary

Ograniczenia miar (definiowane przez u

ż

ytkownika):

Minimalne wsparcie – minsup

Minimalna ufno

ść

– minconf

Mówimy,

ż

e reguła asocjacyjna X

→

Y jest silna je

ż

eli

sup(X

→

Y)

≥

minsup i conf(X

→

Y)

≥

minconf

Dana jest baza danych transakcji. Nale

ż

y znale

źć

wszystkie silne binarne

reguły asocjacyjne

Trans_Id

Produkty

100

A, B, C

200

A,C

300

A,D

400

B,E,F

Reguły asocjacyjne – miary-przykład

Dana jest baza danych transakcji. Nale

ż

y znale

źć

wszystkie silne binarne

reguły asocjacyjne

Zakładaj

ą

c minsup = 50% oraz minconf = 50% (tylko takie nas interesuj

ą

)

w przedstawionej bazie danych mo

ż

na znale

źć

nast

ę

puj

ą

ce reguły asocjacyjne:

A

→

C sup = 50%, conf = 66,6 %

C

→

A sup = 50%, conf = 100%

S

ą

jeszcze inne miary reguł asocjacyjnych (Coviction, Lift, Interest)

Trans_Id

Produkty

100

A, B, C

200

A,C

300

A,D

400

B,E,F

Algorytm naiwny

Dany jest zbiór elementów I i baza danych D

Wygeneruj wszystkie mo

ż

liwe podzbiory zbioru I i nast

ę

pnie, dla ka

ż

dego

podzbioru oblicz wsparcie tego zbioru w bazie danych D.

Dla ka

ż

dego zbioru, którego wsparcie jest wi

ę

ksze/równe minsup, wygeneruj

reguł

ę

asocjacyjn

ą

– dla ka

ż

dej otrzymanej reguły oblicz ufno

ść

reguły

Liczba wszystkich mo

ż

liwych podzbiorów zbioru I wynosi 2|I| - 1 (rozmiar I

≈

200 000 elementów)

Ogólny algorytm odkrywania reguł
asocjacyjnych

1.

Znajd

ź

wszystkie zbiory elementów

L

i

={i

i1

, i

i2

, ..., i

im

},

L

i

⊆

I, których wsparcie(L

i

) minsup

Zbiory Li nazywa

ć

b

ę

dziemy zbiorami cz

ę

stymi

2.

Korzystaj

ą

c z Algorytmu 1.2 i znalezionej kolekcji

zbiorów cz

ę

stych wygeneruj wszystkie reguły asocjacyjne)

Algorytm 1.1 składa si

ę

z dwóch kroków. W pierwszym kroku znajdowane s

ą

wszystkie zbiory cz

ę

ste, które reprezentuj

ą

zbiory elementów wyst

ę

puj

ą

cych

wspólnie w transakcjach. W kroku drugim, na podstawie znalezionych
zbiorów cz

ę

stych, generowane s

ą

wszystkie silne binarne reguły

asocjacyjne, których ufno

ść

jest nie mniejsza ni

ż

zadany próg minimalnej

ufno

ś

ci minconf

Ogólny algorytm odkrywania reguł
asocjacyjnych

1.

Znajd

ź

wszystkie zbiory elementów

L

i

={i

i1

, i

i2

, ..., i

im

},

L

i

⊆

I, których wsparcie(L

i

) minsup

Zbiory Li nazywa

ć

b

ę

dziemy zbiorami cz

ę

stymi

2.

Korzystaj

ą

c z Algorytmu 1.2 i znalezionej kolekcji

zbiorów cz

ę

stych wygeneruj wszystkie reguły asocjacyjne

Algorytm składa si

ę

z dwóch kroków. W pierwszym kroku znajdowane s

ą

wszystkie zbiory cz

ę

ste, które reprezentuj

ą

zbiory elementów wyst

ę

puj

ą

cych

wspólnie w transakcjach. W kroku drugim, na podstawie znalezionych
zbiorów cz

ę

stych, generowane s

ą

wszystkie silne binarne reguły

asocjacyjne, których ufno

ść

jest nie mniejsza ni

ż

zadany próg minimalnej

ufno

ś

ci minconf

Ogólny algorytm odkrywania reguł
asocjacyjnych-alg 1.2

for each zbioru czestego Li do

for each podzbioru subLi zbioru Li do

if wsparcie(Li)/wsparcie(subLi)

≥

minconf

then

output reguła subLi

→

(Li-subLi)

conf(subLi

→

(Li-subLi)) =

support(Li)/support(subLi),

sup(subLi

→

(Li-subLi)) = support(Li)

W ostatnim kroku algorytmu wygenerowane reguły s

ą

poddawane

analizie. W zbiorze wynikowym pozostan

ą

tylko te reguły , kt

ó

rych

wsp

ó

łczynnik ufno

ś

ci b

ę

dzie co najmniej tak dobry jak minimalny pr

ó

g

wsparcia. W ten spos

ó

b otrzymujemy tylko silne reguły asocjacyjne.