RAC UNALNI STVO
Algoritem Apriori in povezovalna pravila
Damjan Strnao
-> Morda ste se kdaj vprašali, na kakšen nacin trgovci uporabijo znanje o nakupovalnih navadah strank za izboljšanje kakovosti svoje ponudbe, posledično pa tudi za dvig prometa. Ko na blagajni v trgovini plačate za nakup, se seznam artiklov v vaši košarici zabeleži kot transakcija (transaction). Z zbiranjem transakcij si trgovec ustvari obsežno bazo nakupovalnih navad svojih kupcev, s pomocjo t. i. kartic zvestobe pa jih lahko vodi celo za vsako gospodinjstvo posebej. Poznavanje nakupovalnih navad lahko trgovec s pridom uporabi za oblikovanje akcijskih ponudb, ki bodo bolj verjetno pritegnile kupce. Prav tako lahko artikle, ki jih stranke pogosto kupujejo v paketu, trgovec na policah postavi blizu skupaj, kar bo strankam olajšalo nakup in hkrati pospešilo prodajo. V tem prispevku bomo opisali algoritem oz. metodo, s pomocjo katere lahko trgovec iz zbirke transakcij izlušci tovrstne koristne informacije. Opisani postopki so uporabni tudi pri ugotavljanju navad uporabnikov v drugih situacijah, ki omogocajo beleženje neke vrste transakcij (npr. hranjenje br-skalnih navad uporabnikov svetovnega spleta za prikazovanje reklam).
Oznacimo s T seznam vseh zabeleženih transakcij. Posamezna transakcija Ti G T,i = l,...,m, je množica postavk (items), t. j. Ti = {x1, x2,..., xni} za xi G X, kjer je X = {xi; i = 1 ...n} množica vseh možnih postavk. V primeru nakupovalne košarice je npr. postavka posamezen tip kupljenega artikla (dva ali vec enakih artiklov štejemo kot eno postavko). Prvi korak, ki ga lahko izvedemo pri obdelavi T, je is-
kanje pogostih množic postavk (frequent itemsets), t. j. stvari, ki jih pogosto kupujemo skupaj. Pogostost neke množice postavk S je določena kot delež transakcij v T, pri katerih S nastopa kot podmnožica. Tak delež imenujemo relativna podpora (relative support) množice postavk in ga bomo označevali z rS. Formalno bi to lahko zapisali kot
rs =
\Ts I |T|
kjer je TS = {Ti G T\S c Ti}. Vrednost v števcu je velikost množice TS in se imenuje podpora (support) za množico postavk S.
Množica postavk je pogosta, ce je njena podpora enaka ali vecja od dolocene vnaprej postavljene meje rmin G (0,1). Pojasnimo to s preprostim zgledom, v katerem množico vseh postavk X sestavlja pet artiklov, ki jih bomo označevali s crkami od a do e (bralec si lahko predstavlja, da a pomeni ananas, b banane itd.). Podana naj bo naslednja zbirka T desetih transakcij:
Transakcija	a	b	c	d	e
Ti	x	x			x
Tz	x	x	x		
t3		x	x		x
T4		x			
Ts	x	x		x	x
Te	x		x		
Tj			x	x	
Tg		x			x
Tg	x		x		x
Tio	x	x			x
V tabeli oznaka 'x' v dolocenem stolpcu in vrstici pomeni, da je pripadajoci artikel prisoten v ustrezni transakciji. Tako lahko npr. transakcijo T1 zapišemo kot T1 = {a, b, e}.
26
PRESEK 43 (2015/2016) 2	19
RACUNALNIŠ TVO
Iskanje pogostih množic postavk z grobim pristopom bi pomenilo pregledovanje vseh nepraznih pod-množic množice X. Za množico postavk S = {a,b,c} bi tako ugotovili, da je njena relativna podpora enaka ria,b,c} = 0-1, saj se artikli a, b in c skupaj nahajajo samo v eni (T2) izmed desetih transakcij. V nadaljevanju bomo zaradi preglednosti množice postavk zapisovali v strnjeni obliki, npr. abd = {a, b, d}.
Število nepraznih množic postavk pri n postavkah je enako 2n-1 (t.j. moc potencne množice P(X) brez 0), zato je časovna zahtevnost grobega pristopa eksponentna. V zgornjem primeru s petimi postavkami je grobi pristop še izvedljiv, v realnih situacijah z vec 100 ali 1000 artikli pa bi bilo pregledovanje celotne potencne množice prakticno neobvladljivo. Algoritem Apriori je preprosta izboljšava grobega pristopa, ki potrebno število pregledanih množic postavk zmanjša z upoštevanjem naslednjega dvodelnega pravila:
Pravilo Apriori a) Vse podmnožice pogoste množice postavk so pogoste in b) nobena nadmnožica ne-pogoste množice postavk ni pogosta.
Oznacimo z F seznam vseh pogostih množic postavk, ki jih algoritem Apriori poišce. Za vsako množico postavk bomo vodili tudi njeno relativno podporo, zato bodo elementi seznama F pari oblike (S,rS). Delovanje algoritma povzema naslednja psevdokoda:
Algoritem 1 Apriori(T, X, rmin)
1:	F = 0 # inicializiraj prazen seznam pogostih množic postavk
2:	D0 = {0}	# inicializiraj delovni seznam množic postavk
3:	J = 0	# števec iteracij
4:	ponavljaj
5: J = J + 1
6: DJ = {Q U{x}|Q G DJ-1 A X G X\Q} 7: odstrani iz Dj vse množice S,
za katere velja 3y G S : S\{y} ( DJ-1 8: izracunaj relativno podporo množicam postavk v Dj 9: odstrani iz Dj vse množice S,
za katere velja rS < rmin 10: F = F U Dj 11: dokler Dj * 0 12: vrni F
Algoritem za svoje delovanje uporablja delovni seznam D, v katerem hrani pogoste množice postavk, najdene v zadnjem koraku. Za lažje sledenje algoritmu bomo z Di oznacevali stanje delovnega seznama po izvedbi i-te iteracije zanke. V prvi itera-ciji algoritem Apriori poišce pogoste množice posameznih postavk in jih v kasnejših iteracijah razširja. Pri vsakem nadaljevanju iskanja algoritem upošteva prvi del prej zapisanega pravila v koraku 7, kjer obdrži samo tiste razširjene množice postavk, ki ne vsebujejo nobene nepogoste podmnožice. Drugi del pravila algoritem upošteva v koraku 9, kjer iz nadaljnje obravnave izloci vse nepogoste množice postavk, saj tudi nobena njihova nadmnožica ne more biti pogosta.
Delovanje algoritma demonstrirajmo na prejšnjem primeru za rmin = 0-3. Po zacetni inicializaciji algoritem med izvajanjem prvega cikla zanke tvori naslednje množice postavk z njihovimi relativnimi podporami:
S	a	bc	de
rS	0.6	0.7 0.5	0.2 0.6
Množico postavk {d} algoritem v koraku 9 odstrani, ker nima zadostne podpore, tako da ob zakljucku prve zanke velja
■ D1 = {a, b, c, e} in
F = {(a, 0-6), (b, 0-7), (c, 0-5), (e, 0-6)}-
V naslednji iteraciji algoritma v koraku 6 vsako od množic postavk iz D1 razširimo na vse možne na-cine z eno dodatno postavko. Iz tako dobljenega delovnega seznama D2 sproti izlocimo podvojene množice postavk (npr. {a} U {b} in {b} U {a}), v koraku 7 pa še tiste, katerih podmnožice niso v D1 (vse kombinacije s postavko d). Po izracunu relativne podpore dobimo
S	ab	ac	ae	bc	be	ce
rS	0.4	0.3	0.4	0.2	0.5	0.2
Zaradi prenizke podpore tokrat izlocimo množici postavk bc in ce, tako da je stanje seznamov po za-kljucku druge iteracije algoritma naslednje:
■ D2 = {ab,ac,ae,be}
F = {(a, 0-6), (b, 0-7), (c, 0-5), (e, 0-6), (ab, 0-4), (ac, 0-3), (ae, 0-4), (be, 0-5)}-

PRESEK 43 (2015/2016) 2
19
RAČUNALNIŠTVO

V tretji iteraciji algoritma Apriori računamo podporo samo še za množico postavk abe, saj je edina, katere vse podmnožice so v D2. Z relativno podporo rabe = 0.3 množica postavk abe izpolnjuje pogoj za obstoj v seznamu D3. V cetrti iteraciji algoritma pogoja v koraku 7 ne izpolni vec nobena razširitev množice postavk abe in algoritem se zakljuci. Koncni seznam pogostih množic postavk je tako
■ F = Ha, 0.6), (b, 0.7), (c, 0.5), (e, 0.6), (ab, 0.4), {ac, 0.3), (ae, 0.4), (be, 0.5), (abe, 0.3)}.
Delovanje algoritma lahko ponazorimo tudi gra-ficno z drevesom, kakršno je za naš primer prikazano na sliki 1. Algoritem Apriori zacne v korenu in drevo razvija po nivojih. Vsa vozlišca, obarvana s sivo, predstavljajo nepogoste množice postavk, ki se odstranijo v koraku 9. Izmed vozlišc sinov vsakega vozlišca starša so zaradi preglednosti prikazana samo tista, ki jih ne odstranimo v koraku 7.
Racunska zahtevnost algoritma Apriori je v najslabšem primeru še vedno eksponentna, vendar v realnih primerih število pogostih množic postavk z nivoji drevesa hitro upada, zato je prakticna casovna zahtevnost obicajno precej manjša.
Pridobitev seznama pogostih množic postavk je ponavadi samo prvi korak do prakticne uporabe teh informacij. Iz pogoste množice postavk Zi G F lahko izpeljemo eno ali vec povezovalnih pravil (association rules) oblike Pi j : X-,

Yt j, kjer Xi j
c Zi in
Yij = Zi\Xij. Veljavnost posameznega pravila Pij izražamo z zaupanjem (confidence) ci j, ki se izra-cuna po naslednji enacbi:
Ci j = CXij ~Yij =
rZi rXij '
{a, 0.6)		{b, 0.7)	{c, 0.5)	{d, 0.2)	{e 0.6)
					
{ab 0.4) {aC 0.3)		{ ae 0 . 4 )	{bc, 0.2)	{be 0.5)	{ce, 0.2)
Pogosto dolocimo prag zaupanja cmin G (0 , 1) in obdržimo samo pravila s ci j > cmin. Takim pravilom recemo, da so zanesljiva (strong). S povezovalnim pravilom P in pripadajocim zaupanjem c izražamo verjetnost, da se bo v seznamu, ki že vsebuje množico postavk X, pojavila tudi množica postavk Y, npr. da bo kupec ob artiklih X kupil še artikle Y. S pomocjo takšnih pravil lahko trgovec oblikuje politiko akcijskih cen (npr. zniža ceno samo artiklom X, ker pricakuje, da bo kupec potem kupil še neznižane artikle Y) ali postavitev artiklov na policah (npr. postavi artikle Y blizu artiklov X, da vzpodbudi vecji nakup).
Izcrpno iskanje vseh zanesljivih povezovalnih pravil lahko optimiziramo s preprosto izboljšavo. Ko izpeljujemo povezovalna pravila iz pogoste množice postavk Z, pricnemo z maksimalno podmnožico X. Ce po izracunu zaupanja ugotovimo, da cX—Y < cmin, potem lahko iz nadaljnje obravnave izlocimo vse podmnožice od X. Za vsak W c X namrec velja rw > rX in posledicno cw—z\w ^ cx—z\x.
Poišcimo zanesljiva povezovalna pravila za naš primer, ce je cmin = 0.75:
■	P1 : a — b z zaupanjem c1 = 06 = 0.67
■	P2 : b — a z zaupanjem c2 = 07 = 0.57
0 3
■	P3 : a — c z zaupanjem c3 = 0g = 0.5
0 3
■	P4 : c — a z zaupanjem c4 = 05 = 0.6
■	P5 : a — e z zaupanjem c5 = 06 = 0.67
■	P6 : e — a z zaupanjem c6 = 06 = 0.67
■	P7 : b — e z zaupanjem c7 = = 0.71
■	P8 : e — b z zaupanjem c8 = 06 = 0.83
■	P9 : ab — e z zaupanjem c9 = 0f = 0.75
■	P10 : ae — b z zaupanjem c10 = °4 = 0.75
0.4 0.3
■	P11 : be — a z zaupanjem c11 = 05 = 0.6
■	P12 : a — be z zaupanjem c12 = 06 = 0.5
Od vseh izpeljanih pravil bi obdržali samo pravila P8, P9 in P10. Zaupanja za pravili b — ae in e — ab nismo racunali, potem ko smo ugotovili, da c11 < cmin.
Literatura
{abe, 0.3)
SLIKA 1.
Grafična ponazoritev delovanja algoritma Apriori
[1] M. J. Zaki in W. Meira Jr., Data Mining and Analysis: Fundamental Concepts and Algorithms, Cambridge University Press, 2014.
_ XXX
28
PRESEK 43 (2015/2016) 2	19