marcin.mazurek@wat.edu.pl 2006 

Analiza asocjacji

marcin.mazurek@wat.edu.pl 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 ? 

marcin.mazurek@wat.edu.pl 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)

marcin.mazurek@wat.edu.pl 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, 

marcin.mazurek@wat.edu.pl 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 =

marcin.mazurek@wat.edu.pl 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.  

marcin.mazurek@wat.edu.pl 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}

marcin.mazurek@wat.edu.pl 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

marcin.mazurek@wat.edu.pl 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%)

marcin.mazurek@wat.edu.pl 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}

marcin.mazurek@wat.edu.pl 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%

marcin.mazurek@wat.edu.pl 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ł. 

marcin.mazurek@wat.edu.pl 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.  

marcin.mazurek@wat.edu.pl 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

marcin.mazurek@wat.edu.pl 2006

FP-tree

afcelpmn

T05

bcksp

T04

bfhjo

T03

abcflmo

T02

facdgimp

T01

Items

TID

marcin.mazurek@wat.edu.pl 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

marcin.mazurek@wat.edu.pl 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

marcin.mazurek@wat.edu.pl 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

marcin.mazurek@wat.edu.pl 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

marcin.mazurek@wat.edu.pl 2006

Literatura

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

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