Asociacinių taisyklių sudarymo algoritmai

Darbo tikslas:

•   Palyginti asociacinių taisyklių sudarymo algoritmus, išanalizuoti jų tinkamumą praktinių uždavinių sprendimui.

Iškelti uždaviniai:

1.      Susipažinti su didelių duomenų sekų analize, jos komercine nauda

2.      Identifikuoti kylančias asociacinių taisyklių radimo problemas

3.      Išanalizuoti žinomus asociacinių taisyklių radimo algoritmus

4.      Sukurti techninę bazę algoritmų analizei ir palyginimui

5.      Sukurti testinių duomenų aibes

6.      Atlikti algoritmų palyginimą, panaudojant sukurtas duomenų aibes

7.      Atlikti algoritmų palyginimą, panaudojant realius duomenis (telefono abonentų pokalbių įrašai)

8.      Atlikti gautų rezultatų analizę ir pateikti išvadas

Visame pasaulyje duomenų kiekis, kaupiamas duomenų saugyklose, sparčiai didėja. Tuo pačiu vartotojai nori gauti vis sudėtingesnės informacijos iš šių duomenų. Pardavimų vadovo jau nebetenkina paprastas klientų sąrašas, bet jis nori gauti detalią informaciją apie klientų pirkinius, bei ateities prognozes. Paprastos struktūrinės užklausos į duomenų bazes nebegali patenkinti šio vis didėjančio poreikio, todėl pasitelkiama duomenų analizė.

Šiuo metu duomenų analizė yra panašiame etape, kuriame buvo paprastų duomenų užklausų sistemos 1970-taisiais. Per ateinančius dešimt metų, duomenų analizės dėka, prognozuojama padaryti didelius kokybinius šuolius informacinėse verslo palaikymo sistemose. Nors duomenų analizė šiuo metu yra dar „kūdikystės" stadijoje, per praėjusį dešimtmetį buvo sukurta daug duomenų analizės algoritmų, taikomųjų programų, algoritminių siūlymų.

Duomenų analizėje yra naudojami skirtingi metodai, priklausantys nuo sprendžiamos užduoties. Tai gali būti prognoziniai metodai (klasifikavimas, regresija, laiko eilučių analizė, tiesinė prognozė) arba analitiniai metodai (klasterizavimas, apibendrinimas, asociacinių taisyklių radimas, sekų analizė). Visi duomenų analizės metodai sukuria modelį, kuris geriausiai atvaizduoja analizuojamus duomenis pasirinktu pjūviu.

Pastaruoju metu pradedamas plačiai naudoti „Žinių radimo duomenų bazėse" terminas. Tai terminas apibūdinantis daugiapakopį procesą, kurio viena iš sudedamųjų dalių yra duomenų analizė:

Pradiniai        Atrinkti        Apdoroti    Transformuoti    Modelis                             Žinios

duomenys     duomenys     duomenys     duomenys

Atrinkimas      Apdoro-       Transfor-      Duomenų        Interpre-
jimas                    macija                 analizė                      tacija

Ateityje duomenų analizės tobulėjimas leis sukurti naujas duomenų sistemas, galinčias ne tik kaupti, bet ir analizuoti duomenis; galinčias sukurti modelius, kurie remtųsi turimais duomenimis. Šios sistemos galės vykdyti DMQL (Data Mining Query Language) užklausas, kurios skirtingai nuo standartinių SQL (Structured Query Language) užklausų, galės būti naudojamos su hierarchinėmis duomenų struktūromis ir grąžinamas rezultatas bus ne duomenų poaibis, o išanalizuotas modelis.

Šio darbo teorinėje dalyje yra nagrinėjamas asociacinių taisyklių radimo duomenų analizės metodas, bei analizuojami šio metodo algoritmai.

Praktinėje dalyje yra pateikiamas algoritmų sukūrimas, duomenų paruošimas, algoritmų testavimas.

2   Teorinė dalis

2.1    Ryšių tarp duomenų elementų (asociacinės) taisyklės

Vieno produkto pirkimas, kai yra perkamas kitas produktas, nusako asociacinę taisyklę. Asociacinės taisyklės dažnai naudojamos mažmeninės prekybos įmonėse, kad palengvinti įvairių efektyvių reklamos kampanijų organizavimą, padėti racionaliai išnaudoti prekybinį plotą. Nors asociacinės taisyklės daugiausia efekto duoda mažmeninėje prekyboje, tačiau jos gali būti panaudotos ir kitose verslo srityse, pavyzdžiui telekomunikacijų tinklo efektyvaus elementų apkrovimo planavime, bei gedimų prevencijoje. Asociacinės taisyklės nusako ryšius tarp duomenų elementų. Šie ryšiai nėra funkcinės priklausomybės, ar bet kokio tipo koreliaciniai priežastiniai ryšiai. Asociacinės taisyklės nusako bendrą duomenų elementų naudojimą.

Pavyzdžiui:

Maisto mažmeninės prekybos įmonė užregistravo savaitės pardavimų informaciją ir turi duomenis apie kiekvieno pirkėjo pirktas prekes. Ši turima informacija leidžia nustatyti, kokios prekės buvo perkamos kartu. Tarkime 100% atveju, perkant sviestą, buvo perkama duona. Nors sviestas buvo perkamas tik 50% sandorių. Tad įmonė gali priimti sprendimą, kad būtų patogiau vartotojui sviesto ir duonos lentynas patalpinti netoli vienas kito prekybinėje salėje. Kadangi žinoma, jog 100% pirkėjų paėmę sviestą eis link duonos, tai šiame kelyje galima patalpinti kitas norimas parduoti prekes.

Asociacinės taisyklės yra randamos duomenų bazėje, kurią sudaro įrašai apie transakcijas. Viena transakcija turi duomenis apie susijusius duomenų elementus, tarkime apie vieno pirkėjo nupirktas prekes: (Sviestas, Duona, Sūris). T.y. viena transakcija gali būti pirkimo čekis, atmetus iš jo prekių kainas bei nupirktus kiekius.

Šiame pavyzdyje yra pateiktos penkios transakcijos sudarytos iš penkių galimų elementų (Duona, Saldainiai, Sviestas, Alus, Pienas).

Elemento palaikymas nusako procentinę dalį transakcijų, kuriose yra šis elementas. Žemiau esančioje lentelėje yra pateiktos visos galimos elementų kombinacijos ir jų palaikymai bazėje:

Aibe	Palaikymas
Sviestas	60
Saldainiai	20
SaldainiaLSviestas	20
Pienas	40
Pienas,S viestas	20
Pienas,Saldainiai	0
Pienas,S aldainiaLS viestas	0
Duona	80
Duona,S viestas	60
Duona,Saldainiai	20
D uona,S aldainiaLS viestas	20
DuonaPienas	20
D uonaPienas..S viestas	20
DuonaPienas,Saldainiai	0
D uonaPienas,S aldainiaLS viestas	0
Alus	40
Alus,S viestas	0
Alus„Saldainiai	0
Alus„S aldainiaLS viestas	0
AlusPienas	20
AlusPienas,S viestas	0
AlusPienas,Saldainiai	0
AlusPienas,S aldainiaLS viestas	0
Alus,Duona	20
Alus,Duona,S viestas	0
Alus„Duona,Saldainiai	0
Alus„Duona,S aldainiaLS viestas	0
Alus„DuonaPienas	0
Alus„DuonaPienas,S viestas	0
Alus„D uonaPienas,S aldainiai	0
Alus„DuonaPienas,SaldainiaLS viestas	0

Didėjant elementų skaičiui, galimų elementų kombinacijų kiekis didėja eksponentiškai. Pateiktame pavyzdyje su 5 elementais yra 31 galima elementų kombinacija. Bendru atveju, pažymėjus elementų skaičių m, galimų elementų kombinacijų kiekis yra 2^m-1. Ši, didelio galimų elementų kombinacijų kiekio, problema yra viena iš problemų, kurias turi išspręsti Asociacinių taisyklių radimo algoritmai.

Formalus asociacinių taisyklių aprašymas yra toks:

Turima elementų aibė I = I₂, I_m) ir transakcijų duomenų bazė D = (t₁, t₂, t_n), sudaryta iš transakcijų t_i = I_i2, ..., I_ik), kur I_ij g I. Asociacinė taisyklė yra implikacija X => Y, kur X ir Y yra elementų kombinacijos X e I ir Y e I, bei X n Y = 0.

Asociacinės taisyklės X => Y palaikymas (s) yra procentinė duomenų bazės transakcijų dalis, kuriose yra X u Y.

Asociacinės taisyklės X == Y stiprumas (a) yra duomenų bazės transakcijų, kuriose yra X u Y, kiekio santykis su duomenų bazės transakcijų, kuriose yra X, kiekiu. T.y. a = s_X=_Y / s_X.

Ieškant asociacinių taisyklių duomenų bazėse, dažniausiai domina ne visi ryšiai, o tik tie, kurie yra svarbūs. Svarbumą nusako du parametrai - palaikymas ir stiprumas.

Lentelėje pateiktos asociacinės taisyklės X = Y, kurių stiprumas didesnis už 0 (naudojami duomenys iš aukščiau pateiktos transakcijų duomenų bazės):

AibeX	Aibe Y	Palaik	Stiprurn
Duona	Alus	20	25
Alus	Duona	20	50
Pienas	Alus	20	50
Alus	Pienas	20	50
Sviestas	DuonaPienas	20	33.33333
Pienas	Duona,Sviestas	20	50
Pienas,Sviestas	Duona	20	100
Duona	Pienas,Sviestas	20	25
Duona,Sviestas	Pienas	20	33.33333
DuonaPienas	Sviestas	20	100
Pienas	Duona	20	50
Duona	Pienas	20	25
Sviestas	Duona,Saldainiai	20	33.33333
Saldainiai	Duona,Sviestas	20	100
SaldainialSviestas	Duona	20	100
Duona	Saldainiais viestas	20	25
Duona,Sviestas	Saldainiai	20	33.33333
Duona,Saldainiai	Sviestas	20	100
Saldainiai	Duona	20	100
Duona	Saldainiai	20	25
Sviestas	Duona	60	100
Duona	Sviestas	60	75
Sviestas	Pienas	20	33.33333
Pienas	Sviestas	20	50
Sviestas	Saldainiai	20	33.33333
Saldainiai	Sviestas	20	100

Duomenys parodo, kad 100% perkančiųjų saldainius, perka ir duona, tačiau, palyginus su bendru įrašu kiekiu, tokių transakcijų yra tik 20%. Nusakant svarbumą dviem parametrais s = 30% ir a = 50% (t.y. domina tik asociacinės taisyklės, kurių palaikymas >= 30%, bei stiprumas >= 50%), lieka tik dvi taisyklės:

Sviestas == Duona, s = 60%, a = 100%

Duona = Sviestas, s = 60%, a = 75%

Turint elementų aibę I = (Ii, I₂, I_m) ir transakcijų duomenų bazę D = (ti, t₂, t_n), sudarytą iš transakcijų t_i = (I_ii3 I_i2, I_ik), kur I_ij g I, asociacinių taisyklių radimo algoritmų uždavinys yra rasti implikacijas X => Y su užduotu minimaliu palaikymu ir stiprumu.

Asociacinių taisyklių radimo algoritmų efektyvumas apsprendžiamas dviem dydžiais:

•         duomenų bazės nuskaitymo kartų skaičiumi (nes realios transakcijų duomenų bazės yra labai didelės apimties);

•         generuojamu elementų kombinacijų kiekiu (nes, kaip pateikta aukščiau, galimų elementų kombinacijų kiekis didėja eksponentiškai, didėjant elementų skaičiui);

2.2    Didelės elementų aibės

Asociacinių taisyklių radimo uždavinį galima padalinti į dvi dalis:

1.      Rasti dideles elementų aibes.

2.      Suformuoti asociacines taisykles iš didelių elementų aibių.

Didelių elementų aibių aibė L = (h, l₂, ...,l_n) yra sudaryta iš elementų aibių l_i3 kurių palaikymas yra didesnis už užduotąjį s.

Kai rastos visos didelės elementų aibės, tai visų, užduotą minimalų palaikymą tenkinančių, asociacinių taisyklių X == Y jungtinės aibės X u Y turi būti tarp šių didelių elementų aibių. Bet kuris didelės elementų aibės poaibis yra didelė elementų aibė.

Didelių elementų aibių radimas yra labai daug resursų reikalaujantis uždavinys. Paprasčiausias būdas yra sugeneruoti visas galimas elementų aibes ir patikrinti jas duomenų bazėje. Tačiau galimų elementų aibių skaičius eksponentiškai priklauso nuo elementų skaičiaus ir turint m elementų, galima sugeneruoti 2^m - 1 skirtingų elementų aibių. Kaip parodyta pavyzdyje aukščiau, kai elementų skaičius m = 5, tai galimų aibių skaičius lygus 31. Tačiau kai elementų skaičius m = 30, tai galimų aibių skaičius išauga iki 1073741823. Dauguma asociacinių taisyklių radimo algoritmų stengiasi sumažinti nagrinėtinų aibių skaičių. Šios nagrinėtinos aibės sudaro aibių-kandidatų aibę (C).

Kai visos didelės elementų aibės yra rastos, tada atliekamas asociacinių taisyklių radimas. Taisyklių radimo algoritmas yra tiesinis:

Įvesties duomenys:

D    // Transakcijų duomenų bazė I     // Elementai L    // Didelės elementų aibės s     // Palaikymai

a    // Stiprumas Išvesties duomenys:

R    // Asociacinės taisyklės Algoritmas ARGen:

R = 0;

kiekvienam l g L vykdyti

kiekvienam x e l, išskyrus x = 0 vykdyti jei s_l / s_x > a tai

R = R u (x == (1 - x));

Iš aukščiau pavyzdžiuose pateiktos transakcijų duomenų bazės, naudojant palaikymą s = 30%, yra rastos didelės elementų aibės L = ((Alus), (Duona), (Pienas), (Sviestas), (Duona, Sviestas)). Paskutinioji aibė (Duona, Sviestas) turi du netuščius poaibius (Duona) ir (Sviestas). Panaudoję pirmąjį (x = (Duona)), gauname:

s(Duona, Sviestas) / s(Duona) = 60 / 80 = 75%,

asociacinės taisyklės Duona => Sviestas stiprumas yra 75%. Atitinkamai panaudoję antrąjį poaibį (x = (Sviestas)), gauname:

^s(Duona, Sviestas) ^{/ s}(Sviestas) ^{= 60 / 60 = 100%,} asociacinės taisyklės Sviestas == Duona stiprumas yra 100%.

Toliau nagrinėjamų asociacinių taisyklių radimo algoritmų pirminis uždavinys yra efektyviai rasti dideles elementų aibes L.

2.3    Apriorinis algoritmas

Apriorinis yra labiausiai paplitęs asociacinių taisyklių radimo algoritmas, naudojamas daugelyje komercinių produktų. Jis naudojasi viena taisykle:

Bet kuris didelės elementų aibės poaibis turi būti didelis.

Todėl didelė elementų aibė yra uždara žemyn, nes jei ji tenkina reikalavimus, tai šiuos reikalavimus tenkins ir bet kuris aibės poaibis. Jei kažkuri elementų aibė nėra didelė, tai ji nėra nagrinėtina, kaip stambesnės elementų aibės poaibis.

Tarkime turime 4 elementus (A, B, C, D). Šių elementų sudaromų poaibių grafas yra:

Linijos grafe parodo ryšį tarp aibių ir jas sudarančių poaibių. Aibė ACD yra sudaryta iš poaibių AC, AD, CD, A, C, D. Ir jei ACD yra didelė, tai visi šie poaibiai yra dideli, o jei nors vienas iš poaibių nėra didelis, tai ACD nėra didelė.

Apriorinis algoritmas generuoja tam tikros eilės (elementų skaičių aibėje) kandidatus ir tikrina transakcijų duomenų bazėje ar šie kandidatai yra dideli. Tik tie kandidatai, kurie buvo dideli, yra naudojami sekančios eilės kandidatų generavime. Tai yra Li yra naudojama generuojant C_i+1. Generuojant i+1 eilės kandidatus, yra apjungiamos aibės iš L_i.

Pavyzdžiui:

Eilė	Kandidatai	Didelės elementų aibės
1	(Alus), (Duona), (Saldainiai), (Pienas), (Sviestas)	(Alus), (Duona), (Pienas), (Sviestas)
2	(Alus, Duona), (Alus, Pienas), (Alus, Sviestas), (Duona, Pienas), (Duona, Sviestas), (Pienas, Sviestas)	(Duona, Sviestas)
3	0

Trečios eilės kandidatų nėra, nes yra tik viena antros eilės didelė elementų aibė.

Aukštesnės nei pirmos eilės kandidatų generavimui yra naudojamas algoritmas Apriori-Gen. Pirmos eilės kandidatais naudojamos vienaelementės aibės. Algoritmas Apriori-Gen apjungia i-1 eilės dideles elementų aibes, kurios skiriasi tik vienu elementu:

Įvesties duomenys:

L_i-1  // i-1 eilės didelės elementų aibės

Išvesties duomenys:

Ci    // i eilės kandidatai Algoritmas Apriori-Gen:

Ci = 0;

kiekvienam I g L_i-1 vykdyti

kiekvienam J g L_i-1s išskyrus J = I vykdyti jei i-2 elementai tarp I ir J yra lygūs tai Ci = Ci u (I u J);

Algoritmas Apriori naudojasi algoritmu Apriori-Gen kandidatų generavimui, bei atlieka kandidatų pasikartojimų transakcijų duomenų bazėje suskaičiavimą:

Įvesties duomenys:

D    // Transakcijų duomenų bazė

I     // Elementai

s     // Reikalaujamas palaikymas

Išvesties duomenys:

L    // Didelės elementų aibės

Algoritmas Apriori: L = 0;

k = 0;      // k nurodo eilės numerį

C1 = I;

kartoti

k = k+ 1;

Lk = 0;

kiekvienam I_i g C_k vykdyti

ci = 0;      // elementų aibių skaitikliai kiekvienam tj g D vykdyti

kiekvienam I_i g C_k vykdyti jei I_i g tj tai

^ci ^{= c}i ^{+ 1;}

kiekvienam I_i g C_k vykdyti

jei ci > (s * |D|) tai Lk = Lk u Ii;

L = L u L_k;

Ck+1 = Apriori-Gen (Lk); kol Ck+1 = 0;

Algoritmas Apriori intensyviai naudojasi transakcijų duomenų baze, todėl laikoma, kad duomenų bazė yra operatyvinėje atmintyje. Maksimalus duomenų bazės peržiūrėjimų skaičius yra vienu didesnis nei didžiausios rastos didelės elementų aibės eilė. Šis didelis duomenų bazės peržiūrėjimo kartų kiekis yra algoritmo trūkumas.

2.4    Mėginio algoritmas

Kai transakcijų duomenų bazės yra didelės, galima naudoti mėginio paėmimo metodus. Algoritmas, paimantis mėginį potencialių didelių elementų aibių radimui, leidžia sumažinti duomenų bazės praėjimų skaičių iki dviejų arba net vieno - geriausiu atveju. Pradžioje yra paimamas duomenų bazės mėginys, telpantis į operatyvinę atmintį, ir yra panaudojamas Apriorinis algoritmas didelių elementų aibių radimui šiame mėginyje. Rastosios elementų aibės yra vadinamos potencialiai didelėmis elementų aibėmis PL. Jos yra naudojamos, atliekant pilną transakcijų duomenų bazės peržiūrą, kaip kandidatai. Papildomi kandidatai yra pridedami atliekant negatyvios ribos funkciją BD (). Bendra kandidatų aibė, atliekant pilną transakcijų duomenų bazės peržiūrą, yra C = BD (PL) u PL. Negatyvios ribos funkcija yra algoritmo Apriori-Gen apibendrinimas bet kurios eilės elementų aibėms. BD (PL) grąžina aibes, kurios nėra PL, bet visi tos aibės poaibiai yra PL.

Pavyzdžiui:

Turimi keturi elementai (A, B, C, D) ir atlikus mėginio analizę yra rastos potencialiai didelės elementų aibės PL = (A, C, D, CD). Tada kandidatai pirmam pilnam transakcijų duomenų bazės praėjimui yra C = BD (PL) u PL = (B, AC, AD) u (A, C, D, CD). Kandidatas AC buvo pridėtas todėl, kad abu poaibiai A ir C yra PL. Kandidatas ACD nėra pridėtas todėl, kad nei AC, nei AD nėra PL. B pridėtas, nes B negalima išskaidyti į netuščius poaibius.

Suformavus kandidatus, yra atliekama pirma pilna transakcijų duomenų bazės peržiūra. Jei peržiūros metu visos rastos didelės elementų aibės L priklauso PL, tai laikoma, jog visos galimos didelės elementų aibės yra rastos ir antra peržiūra nėra reikalinga. Jei tarp L buvo tokių aibių, kurios nepriklauso L, bet priklauso BD (PL), tai antra peržiūra yra reikalinga, nes dar potencialiai yra kitų nepatikrintų kandidatų. Turimos keturios elementų aibių grupės:

1.      Elementų aibės, kurios žinomai yra didelės

2.      Elementų aibės, kurios žinomai yra mažos

3.      Elementų aibės, kurios yra BD (PL) buferyje

4.      Kitos dar neištirtos elementų aibės

Negatyvios ribos funkcija BD (PL) veikia kaip elementų aibių buferis tarp žinomai didelių elementų aibių ir kitų dar neištirtų elementų aibių. BD (PL) nusako mažiausią poaibį elementų aibių, kurios gali būti didelės. Jei pirmos pilnos transakcijų duomenų bazės peržiūros metu nebuvo rastos didelės elementų aibės buferyje BD (PL), tai tikrai didelių elementų aibių nėra tarp kitų dar neištirtų elementų aibių.

Antros pilnos transakcijų duomenų bazės peržiūros metu tikrinami kiti kandidatai, kurių parinkimas turi užtikrinti, jog visos didelės elementų aibės bus rastos. Tam yra atliekamas pakartotinis negatyvios ribos funkcijos BD () panaudojimas jau rastoms didelėms elementų aibėms, kol nebesugeneruojama naujų elementų aibių. Šio proceso metu sugeneruojama daug kandidatų, tačiau tai užtikrina, kad antros pilnos transakcijų duomenų bazės peržiūros metu visos didelės elementų aibės bus rastos.

Mėginio paėmimo algoritmas Sampling:

Įvesties duomenys:

D    // Transakcijų duomenų bazė

I     // Elementai

s     // Reikalaujamas palaikymas Išvesties duomenys:

L    // Didelės elementų aibės Algoritmas Sampling:

D_s = D bazės mėginys;

PL = Apriori (I, D_s, smalls);

C = BD(PL) u PL;

L = 0;

kiekvienam I_i g C vykdyti

ci = 0;      // elementų aibių skaitikliai
kiekvienam tj g D vykdyti                             // pirmas bazės praėjimas

kiekvienam I_i g C vykdyti jei I_i g tj tai

^ci ^{= c}i ^{+ 1;}

kiekvienam I_i g C vykdyti

jei ci > (s * |D|) tai L = L u Ii;

ML = (x | x g BD (PL) a x g L);      // Buferyje buvusios aibės jei ML ^ 0 tai

C = L;

kartoti

C = BD(C) u C; kol C nebebus papildyta naujomis aibėmis; kiekvienam I_i g C vykdyti

ci = 0;

kiekvienam tj g D vykdyti       // antras bazės praėjimas kiekvienam I_i g C vykdyti jei I_i g tj tai

^ci ^{= c}i ^{+ 1;}

kiekvienam I_i g C vykdyti

jei ci > (s * |D|) tai L = L u Ii;

Algoritmas mėginio analizei naudoja Apriorinį algoritmą su palaikymo reikšme smalls. Čia smalls gali būti naudojama bet kokia mažesnė reikšmė už s. Palaikymo sumažinimas leidžia mėginyje rasti daugiau didelių elementų aibių, kurios bus naudojamos atliekant pilną transakcijų duomenų bazės peržiūrą, tad didesnė tikimybė, kad visos didelės elementų aibės bus rastos pirmos peržiūros metu.

Pavyzdžiui:

Duomenų bazės mėginį sudaro dvi transakcijos Ds = ((Duona, Saldainiai, Sviestas), (Duona, Sviestas)). Reikalaujamas palaikymas s = 40%. Mėginio analizei naudojamas palaikymas smalls = 20%, t.y. aibė bus didelė, jei ji pasikartos ne mažiau kaip 0,2 x 2 transakcijose (bent vienoje iš dviejų mėginio transakcijų). Atlikus Apriorinį algoritmą su Ds ir smalls gaunamos potencialiai didelės elementų aibės:

PL = ((Duona), (Saldainiai), (Sviestas), (Duona, Saldainiai), (Duona, Sviestas), (Saldainiai, Sviestas), (Duona, Saldainiai, Sviestas)) Įvykdžius negatyvios ribos funkciją gaunama: BD(PL) = ((Alus), (Pienas))

Tad kandidatų aibė pirmai pilnai transakcijų duomenų bazės peržiūrai yra:

C = ((Duona), (Saldainiai), (Sviestas), (Duona, Saldainiai), (Duona, Sviestas), (Saldainiai, Sviestas), (Duona, Saldainiai, Sviestas), (Alus), (Pienas))

Tada atliekama peržiūra su s = 40%, kuri grąžina tokias dideles elementų aibes: L = ((Duona), (Sviestas), (Duona, Saldainiai), (Alus), (Pienas))

Kadangi ML = ((Alus), (Pienas)), tai reikalinga antra bazės peržiūra. Kandidatai jai yra: BD (C) = ((Alus, Duona), (Alus, Pienas), (Alus, Sviestas), (Duona, Pienas), (Pienas, Sviestas));

Kartojant negatyvios ribos funkciją gaunami nauji kandidatai:

BD (C) = ((Alus, Duona, Pienas), (Alus, Duona, Sviestas), (Duona, Pienas, Sviestas), (Alus, Pienas, Sviestas));

Dar kartą kartojant negatyvios ribos funkciją gaunami nauji kandidatai: BD (C) = ((Alus, Duona, Pienas, Sviestas));

Tolesnis kartojimas naujų kandidatų nesugeneruoja. Kandidatų aibė antrai pilnai transakcijų duomenų bazės peržiūrai yra:

C = ((Duona), (Sviestas), (Duona, Saldainiai), (Alus), (Pienas), (Alus, Duona), (Alus, Pienas), (Alus, Sviestas), (Duona, Pienas), (Pienas, Sviestas), (Alus, Duona, Pienas), (Alus, Duona, Sviestas), (Duona, Pienas, Sviestas), (Alus, Pienas, Sviestas), (Alus, Duona, Pienas, Sviestas))

2.5    Padalinimo algoritmas

Didelė transakcijų duomenų bazė D gali būti padalinama į p dalių D¹, D², D^p. Toks padalinimas leidžia didelių elementų aibių radimą padaryti efektyvesniu, nei naudojant pilną bazę, nes:

•         Duomenų bazės dalis gali būti patalpinama operatyvinėje atmintyje.

•         Kandidatų, kurie ieškomi duomenų bazės dalyje, aibė potencialiai yra mažesnė, nei kandidatų aibė, naudojama paieškoje pilnoje bazėje.

•         Galima panaudoti paralelinius ar paskirstytuosius algoritmus ir skirtingas duomenų bazės dalis gali analizuoti skirtingi kompiuteriai.

Padalinimo algoritmas remiasi taisykle:

Bet kuri didelė elementų aibė visoje bazėje turi būti didelė bent vienoje iš dalių.

Padalinimo panaudojimas leidžia sumažinti duomenų bazės praėjimų skaičių iki dviejų. Pirmo praėjimo metu dalys paeiliui užkraunamos į operatyvinę atmintį ir yra atliekama didelių elementų aibių paieška. Lⁱ pažymi dideles elementų aibes, rastas nagrinėjant Dⁱ transakcijų duomenų bazės dalį. Didelės elementų aibės gali būti randamos panaudojant Apriorinį algoritmą. Pirmo praėjimo rezultate suformuojama kandidatų aibė C = L¹ u L² u ... u L^p. Antrojo pilno transakcijų duomenų bazės praėjimo metu tikrinami sugeneruoti kandidatai. Padalinimo algoritmas Partition:

Įvesties duomenys:

p     // Duomenų bazės dalių skaičius

D = (D¹, D²,    D^p)   // Transakcijų duomenų bazė

I     // Elementai

s     // Reikalaujamas palaikymas Išvesties duomenys:

L    // Didelės elementų aibės Algoritmas Partition:

C = 0;

kiekvienam i g [1 ... p] vykdyti

Lⁱ = Apriori (I, Dⁱ, s); C = C u Lⁱ ; L=0;

kiekvienam I_i g C vykdyti

ci = 0;      // elementų aibių skaitikliai
kiekvienam tj g D vykdyti                             // pirmas bazės praėjimas

kiekvienam I_i g C vykdyti jei I_i g tj tai ci = ci+ 1; kiekvienam I_i g C vykdyti jei ci > (s * |D|) tai L = L u Ii;

Pavyzdžiui:

Turimos dvi duomenų bazės dalys:

D¹ = ((Duona, Saldainiai, Sviestas), (Duona, Sviestas))

D² = ((Duona, Pienas, Sviestas), (Alus, Duona), (Alus, Pienas))

Šiuo atveju p = 2. Reikalaujamas palaikymas s = 40%, tad pirmoje dalyje aibei pakanka būti vienoje transakcijoje, o antroje dalyje aibe privalo būti ne mažiau kaip dvejose transakcijose. Apriorinio algoritmo pritaikymas duomenų bazės dalims duoda:

L¹ = ((Duona), (Saldainiai), (Sviestas), (Duona, Saldainiai), (Duona, Sviestas), (Saldainiai, Sviestas), (Duona, Saldainiai, Sviestas))

L² = ((Duona), (Alus), (Pienas))

Bendras kandidatų sąrašas antram praėjimui yra:

L¹ = ((Duona), (Saldainiai), (Sviestas), (Duona, Saldainiai), (Duona, Sviestas), (Saldainiai, Sviestas), (Duona, Saldainiai, Sviestas), (Alus), (Pienas))

Bazės padalinimo algoritmo veikimas priklauso nuo duomenų pasiskirstymo transakcijų duomenų bazėje. Jei duomenys pasiskirstę tolygiai, tai kiekvienos dalies analizė duos didelių elementų aibių sąrašą artimą galutiniam ir antrame praėjime naudojamas kandidatų sąrašas bus minimalus. Jei duomenys pasiskirstę netolygiai, tai potencialiai galimas didelis neteisingų kandidatų skaičius.