RAČUNALNIŠ TVO
Algoritem BatMiner za rudarjenje asociativnih pravil
Iztok Fister ml. in Iztok Fister
-> Razvoj spletnega računalništva dandanes spremljata dva med seboj tesno prepletena izziva: velika količina neraziskanih podatkov v podatkovnih bazah in eksponentna rast računske moči računalniških sistemov. Prvi izziv je pripeljal do nastanka moderne računalniške disčipline podatkovno rudarjenje, katerega čilj je odkrivanje infor-mačij, skritih v podatkih, medtem ko drugi izziv poskuša zadovoljiti vse večje zahteve spletnega računalništva po pročesorski moči in velikosti po-mnilniških medijev. Dejansko je prav zadnji omogočil veliko rast in razvoj podatkovnega rudarjenja v zadnjem desetletju.
Podatkovno rudarjenje je multidisciplinarno področje, ki se zgleduje po principih ostalih znanstvenih področij, matematike, statistike, računalništva, fizike, inženirstva. Na to področje so imele največji vpliv naslednje disčipline:
■ statistika z uporabo statističnih metod in vizuali-začijo podatkov,
umetna inteligenča z uporabo metod strojnega učenja,
metode računske inteligenče in sistemi podatkovnih baz.
Dandanes se na tem področju pojavlja več vrst apli-kačij, ki jih lahko razdelimo v napovedne in opisne.
Prvi tip aplikačij je namenjen napovedovanju (npr. klasifikačija, regresija) vrednosti ene ali več spremenljivk v prihodnosti na podlagi dela spremenljivk v podatkovnih bazah, medtem ko se drugi tip (npr. gručenje, rudarjenje asočiativnih pravil, odkrivanje zaporednih vzorčev) ukvarja z identifikačijo vzorčev za opis podatkov, shranjenih v podatkovnih bazah, in njihovo vizualizačijo na način, ki je enostavno razumljiv uporabnikom. V tem članku se osredoto-čamo na rudarjenje asočiativnih pravil.
Rudarjenje asočiativnih pravil je pročes identifiči-ranja pravil odvisnosti med objekti znotraj velikih transakčijskih podatkovnih baz [4]. S temi pravili iščemo povezave med objekti oziroma napovedujemo pojavitev objektov v primeru, da se pojavi določeno sosledje drugih objektov.
Formalna definičija rudarjenja asočiativnih pravil je naslednja: Predpostavimo, da sta podani množiča objektov O = {oi,..., on} in množiča transakčij T v transakčijski podatkovni bazi D, kjer je vsaka tran-sakčija t G T podmnožiča objektov T c o. Potem lahko asočiativno pravilo definiramo kot implikačijo oblike
X ^ Y,
(1)
kjer velja X c O, Y c O in X n Y = 0. Množičo mogočih pravil očenimo z naslednjima meriloma [i]:
supp(X Y) =
in
conf (X ^ Y) =
|{t e T ; X u t}
IT |
supp(X u Y)
supp(X )
(2)
(3)
26
PRESEK 44 (2016/2017) 5	26
RAČUNALNIŠ TVO
kjer podpora supp(X = Y) označuje, kako pogosto se objekt X pojavlja v transakcijski podatkovni bazi in zaupanje conf (X == Y), kako pogosto asociativno pravilo X == Y vrača vrednost pravilno. Iz te množice izberemo tista pravila, ki izpolnjujejo nasledni relaciji:
■	SUpp(X = Y) > Smin in
■	conf (X = Y) > C min,
kjer Smn oznacuje minimalno zaupanje in Cmin minimalno podporo. Do danes je bilo razvitih veliko algoritmov za rudarjenje asociativnih pravil, kot npr. Apriori, Eclat, FP-Growth.
Zadnjih nekaj let poskušajo raziskovalci reševati ta problem tudi z uporabo algoritmov po vzorih iz narave. Med algoritme po vzorih iz narave štejemo evolucijske algoritme in algoritme inteligence rojev. Oboji spadajo med populacijske algoritme, kar pomeni, da operirajo s populacijo rešitev. Prva vrsta posnema Darwinovo evolucijsko teorijo, po kateri imajo v naravi najvec možnosti za preživetje najuspešnejši posamezniki. Druga vrsta pa temelji na obnašanju delcev znotraj roja delcev, kjer delci delujejo kot agenti, ki so sposobni izvajanja relativno enostavnih opravil. Ce ti agenti delujejo povezani v skupnost, so sposobni izvajanja tudi kompleksnejših opravil.
Vec informacij o teh algoritmih lahko najde bralec v clanku [2].
Eden izmed algoritmov za rudarjenje asociativnih pravil je tudi BatMiner, ki ga predstavljamo podrobneje v nadaljevanju clanka. Ta temelji na algoritmu na osnovi obnašanja netopirjev [5] in ga je za rudarjenje asociativnih pravil potrebno prilagoditi. Pri tem sta najpomembnejši dve:
prilagoditev predstavitve rešitev, in
■	prilagoditev ocenitvene funkcije.
Rešitev algoritma za rudarjenje asociativnih pravil BatMiner je predstavljena kot vektor realnih števil:
. x(t) _ (x(t) x(t) (t) (t) ) kjer xitj G [0,1) za i =	A j = !,■■■, d ko-
dira znacilnice v asociativnem pravilu, o ozna-
čuje tocko reza, x(t)+2 pa smer asociativnega pravila.
Spremenljivka n doloca velikost populacije, d maksimalno število atributov v asociativnem pravilu in je t števec generacij. Tocka reza doloca, katere znacilnice spadajo v predpostavko (angl. antecedent) in katere v posledico (angl. consequence) specifičnega asociativnega pravila.
Vsak element vektorja x(tj kodira dve vrsti informacije. Ko so elementi urejeni po narašcajocem vrstnem redu, pripadajoci indeksi tvorijo permutacijo znacilnic, ki doloca vrstni red pojavitve elementov v asociativnem pravilu. Povedano z drugimi besedami, glede na relacijo >manjši ali enak< dobimo naslednjo relacijo urejenosti:
(t)
(t)
xi,n(i, 1) - xi,n(i,2) -
< X{t) - xi, n(i, d)'
kjer n(i, j) doloca pripadajoči indeks atributa na j-ti poziciji i-tega vektorja.
Po drugi strani je območje dopustnih vrednosti znacilnic v intervalu x^j G [0,1] za j = 0,...,d razdeljeno v mj + 1 ekvidistantnih intervalov, kjer vsak inteval [k, k + 1] za k = 0,...,mj ustreza enemu izmed elementov množice atributov j-te znacilnice oij G {aio0, aii1,..., aimj} in parameter mj oznacuje
število elementov te množice. Atribut aij v generaciji t izracunamo po naslednji enacbi:
a(t) -ai,j =
x
(t) i,j
mj + 1
za i = 0'...,n A j = 0'...,d.
(4)
Atribut a( q = NULL ima poseben pomen, saj doloca, da pripadajoce znacilnice ni v asociativnem pravilu.
Tocko reza p(it) asociativnega pravila doloca nadzorni parameter xit)+1 in jo dekodiramo po naslednji enacbi:
Pi] = Xh(d - 2)J + 1'
za i = O,
,n'
kjer dovoljujemo maksimalno d - 2 tock reza v vsakem asociativnem pravilu.
Element xf\+2 G [0,1] doloca smer branja asociativnega pravila, ki ga dekodiramo po naslednji enacbi:
& =
O,
ce xith - 0.5' ce x\%o > °.5,
za i = °'...,n.

PRESEK 44 (2016/2017) 5
27
RAČUNALNIŠ TVO
->
Znacilnica	Atributi	Vrednosti
	KRATKO	< 150 min
TRAJANJE	SREDNJE	> 150 min A < 300 min
	DOLGO	> 300 min
	KRATKA	< 50 km
DOLŽINA	SREDNJA	> 50 km A < 120 km
	DOLGA	> 120 km
	MAJHNA	< 1200 kCal
PORABA	SREDNJA	> 1200 kCal A < 2800 kCal
	VISOKA	> 2800 kCal
	MAJHEN	< 130 BPM
UTRIP	SREDNJI	> 130 BPM A < 170 BPM
	VISOK	> 170 BPM
TABELA 1.
Diskretizacija zveznih spremenljivk, ki služijo kot znacilnice.
TRAJANJE	DOLŽINA	PORABA	UTRIP	VREME	TIP	SPANJE	KRCI	P	
KRATKO	KRATKA	0	0	0	INTERVAL	0	0	3	0
Predpostavka	Posledica	Nadz. par.
TABELA 2.
Primer veljavne rešitve.
Ce je vrednost q(t = 0, asociativno pravilo beremo z leve proti desni, ce je q(t) = 1 pa z desne proti levi.
Ocenitvena funkcija v algoritmu BatMiner je podobna funkciji, uporabljeni v [3] in jo izrazimo na naslednji nacin:
f(Xf) =
Í a * conf (x(t) ) + y * supp (x1^) ü+y	'
-1-
ce feasible(x(t^) = true, drugače,
kjer je conf () merilo zaupanja, supp() merilo podpore pravila, a in y so uteži, namenjene uravno-teževanju vpliva zaupanja in podpore ter funkcija feasible(xi), ki določa, ce je rešitev dopustna ali ne. Naloga optimizacije je poiskati maksimalno vrednost ocenitvene funkcije.
Algoritem BatMiner uporabimo za ugotavljanje znacilnostih športnika v športnem treningu. S športnimi aktivnostmi se namrec v današnjih casih zace-nja ukvarjati vse vec ljudi, v kar jih najveckrat prisili moderni življenjski slog. Ti športniki obicajno spremljajo napredek svojega treniranja s pomocjo športnih ur oziroma mobilnih naprav, ki jih nosijo med treningom. Te naprave praviloma generirajo veliko število podatkov, ki lahko služijo športnim trenerjem pri nacrtovanju športnih treningov, ugotavljanju trenutne pripravljenosti športnika v treningu, sestavljanju športnih jedilnikov ipd. V naši študiji uporabimo te podatke (tj. dolžino, trajanje, srcni utrip in porabo kalorij med treningom) kot osnovo za ugotavljanje znacilnostih športnika v športnem treningu.
Pri tem podatke o spremljanju športnih treningov, pridobljenih z mobilnih naprav, dopolnimo s informacijami o psiho-fizicnem stanju športnika pred tre-
28
PRESEK 44 (2016/2017) 5	28
RAČUNALNIŠ TVO
ningom (tj. vpliv vremena, tip treninga, nocno spanje pred treningom, morebitni krci) in vse skupaj shranimo v podatkovno bazo. Iz podatkov v podatkovni bazi izluščimo dejavnike, ki vplivajo na izvedbo športnega treninga posameznega športnika, in te shranimo kot značilnice (angl. features) v transakcijsko podatkovno bazo. Algoritem BatMiner za rudarjenje asociativnih pravil v tej bazi išče asociativna pravila, ki so za športnega trenerja lahko zelo uporabna pri napovedovanju športnikove forme ali odkrivanju problemov, povezanih s športnim treningom oziroma tekmovanji.
V našem primeru imamo opravka z osmimi znacil-nicami predstavljenimi kot zvezne oziroma diskretne spremenljivke. Zvezne znacilnice, dobljene iz mobilnih naprav, je potrebno najprej diskretizirati. Primer diskretizacije podatkov, pridobljenih z mobilnih naprav, je prikazan v tabeli 1. Omenjena dis-kretizacija je narejena na osnovi teorije športnega treninga in velja tako za profesionalne kot amaterske športnike.
Diskretne znacilnice, ki oznacujejo psiho-fizicno stanje športnika, imajo preddefinirano število atributov. V našem primeru so to:
■	VREME = {SONČNO, OBLAČNO, DEŽEVNO,
SNEŽENO}, TIP ={RAZPELJAVA, INTERVAL, MOČ, VZDRŽLJIVOST}, SPANJE ={DOBRO, SREDNJE, SLABO}, KRČI ={BREZ, RAHLI, VELIKI}.
Primer predstavitve asociativnega pravila, ki ga je odkril algoritem BatMiner v traksakcijski podatkovni bazi z 80 transakcijami, prikazuje tabela 2, kjer nadzorni parameter p = 3 pomeni tocko reza, ki deli pravilo na predpostavko in posledico, in kjer nadzorni parameter q = 0 doloca smer branja asociacij-skega pravila z leve proti desni. Če predpostavimo, da znacilnico združimo z atributom s pomocjo operacije združevanja (znak >_<), posledicno iz rešitve dekodiramo naslednje asociativno pravilo
■	TRAJANJE_KRATKO A DOLŽINA_KRATKA ^ TIP_INTERVAL,
ki pravi: Če je trening kratke dolžine in kratkega trajanja, gre za intervalni tip treninga. Seveda je pravilo v skladu s teorijo športnega treninga, saj gre pri intervalnih treningih za zelo intenzivne kratkotrajne treninge kratkih dolžin.
Kot prikazuje zgornji primer, so algoritmi po vzorih iz narave uporabni tudi pri rudarjenju asociativnih pravil. V današnji družbi se ne moremo izogniti veliki rasti podatkov, ki nastajajo prakticno na vsakem koraku, lahko pa se iz njih veliko novega naucimo. V prihodnosti lahko pricakujemo, da se bodo podobne rešitve z algoritmi po vzorih iz narave za podatkovno rudarjenje zacele uporabljati tudi na ostalih podrocjih clovekove dejavnosti.
Literatura
[1]	R. Agrawal, T. Imielinski in A. Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, 22(2), 207-216, 1993.
[2]	I. Fister Jr., X.-S. Yang, I. Fister, J. Brest in D. Fister, A brief review of nature-inspired algorithms for optimization, Elektrotehniški vestnik, 80(3), 116-122, 2013.
[3]	K. E. Heraguemi, N. Kamel in H. Drias, Association rule mining based on bat algorithm, In Bio-Inspired Computing-Theories and Applications, 182-186, Springer, 2014.
[4]	G. Hrovat, G. Stiglic, P. Kokol in M. Ojster-šek, Contrasting temporal trend discovery for large healthcare databases, Computer methods and programs in biomedicine, 113(1), 251-257, 2014.
[5]	K. Ljubic in I. Fister Jr., Algoritem na osnovi obnašanja netopirjev, Presek, 42(3), 26-28, 2015.
_XXX
www.obzornik.si www.dmfa-zaloznistvo.si
PRESEK 44 (2016/2017) 5
29