Odkrywanie asocjacji
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.