Siekiant geriau išsiaiškinti asociacinių taisyklių radimo metodiką,
buvo nuspręsta pradžioje sukurti asociacinių taisyklių radimo programą su
grafiniu interfeisu. Ši programa nėra skirta algoritmų greitaveikos
patikrinimui. Ji skirta vaizdžiai pateikti analizuojamus duomenis ir tarpinius
rezultatus. Programos kūrimui buvo pasirinkta Delphi programavimo kalba.
Programos išeities tekstas pateikiamas priede 1. Programa turi patogų vartotojo
interfeisą:Programoje
realizuotas asociacinių taisyklių radimo procesas išskaidytas į 4 etapus:
1.
Nuskaitoma
elementų aibė
2.
Suformuojamos visos
įmanomos netuščios ir
nepasikartojančios elementų aibės
3.
Atliekamas aibių
palaikymų suskaičiavimas
4. Randamos asociacinės taisyklės, bei suskaičiuojami jų stiprumai
Šiuos etapus vartotojas valdo atitinkamų mygtukų paspaudimais.
Šiuos etapus vartotojas valdo atitinkamų mygtukų paspaudimais.
Programa duomenis nuskaito į dinaminę duomenų struktūrą. Šiam tikslui
buvo sukurti sekantys duomenų tipai:
•
Aibe - tiesinis
dinaminis sąrašas, kurio nariai laiko informaciją apie aibei priklausančius
elementus
•
Palaik - tiesinis
dinaminis sąrašas, kurio kiekvienas narys turi nuoroda į aibę, bei suskaičiuotą
palaikymo vertę
•
Asoc - tiesinis
dinaminis sąrašas, kurio kiekvienas narys turi po dvi nuorodas į aibes, bei tų
aibių suskaičiuotas palaikymo vertes.
Pradžioje nuskaitomas elementų sąrašas (procedūra Button3Click), kuris
patalpinamas į elementų vardų masyvą ElemVard, bei pateikiamas vartotojui
kairioje interfeiso lango dalyje.
Antrame etape generuojamos aibės iš nuskaitytųjų elementų (procedūra
Button4Click). Aibės yra generuojamos rekurentiškai, įtraukiant ar išmetant po
vieną elementą (procedūra ElmGo). Visos sugeneruotos aibės apjungiamos į sąrašą
Sp, bei išvedamos vartotojui centrinėje interfeiso lango dalyje.
Trečio etapo metu skaičiuojami palaikymai (procedūra Button5Click). Tam
imama kiekviena sugeneruotoji aibė ir skaičiuojamas jos pasikartojimų kiekis
duomenų bazėje. Rezultatai vartotojui pateikiami centrinėje interfeiso lango
dalyje.
Ketvirtame etape
ieškoma asociacinių taisyklių (procedūra Button6Click). Tam formuojama nauja
struktūra Sc. Taisyklės randamos skaidant aibes, turinčias daugiau nei vieną
elementą, bei turinčias nenulinį palaikymą. Sugeneruotos asociacinės taisyklės
pateikiamos vartotojui dešinėje interfeiso lango dalyje.
Šios programos kūrimo metu buvo išsiaiškintas darbas su duomenimis ir
įgyta patirtis, kuri buvo panaudota kuriant greitaveikius asociacinių taisyklių
radimo algoritmus.
3.2 Asociacinių taisyklių radimo algoritmų
bendra dalis
Siekiant užtikrinti asociacinių taisyklių radimo
algoritmų greitaveiką, buvo nuspręsta programines algoritmų realizacijas kurti
C++ kalba (kompiliatorius Borland C++ 5.5.1 for Win32), kaip komandinės eilutės
aplikacijas be grafinio vartotojo interfeiso. Tai leidžia maksimaliai išnaudoti
kompiuterio resursus, bei atlikti automatizuotą algoritmų greitaveikos tyrimą.
Taip pat buvo nuspręsta, kad skirtingų algoritmų programos turi būti su
vienodais duomenų interfeisais.
Išnagrinėjus teorinėje dalyje pateiktus algoritmus buvo pastebėta, kad
algoritmai turi daug bendrų dalių, bei naudoja tokias pačias duomenų struktūras,
todėl buvo nuspręsta bendrąsias algoritmų dalis iškelti į atskirą modulį. Šis
modulis turi talpinti savyje visus naudojamus objektus.
Bendrosios dalies
išeities tekstas pateiktas priede 2.
Elementų saugojimui ir darbui su jais, greitaveikos sumetimais, pasirinkta
naudoti elementų skaitinius identifikatorius. Šių identifikatorių greitam
nustatymui (tai reikalinga atliekant transakcijų duomenų bazės nuskaitymą)
sukurtas objektas RaidSar. Objekte realizuota medžio struktūra:
Tad medyje ieškant elemento pavadinimo ARA, gaunamas
identifikatorius 2, o pavadinimo AHA - 9. Taip išvengiama didelio kiekio
tikrinimų, palyginus su masyvo struktūra.
Elementų vardų medis padarytas dinaminis, tad atitinkamos šakos
sukuriamos tik jei yra elementų, turinčių tokius simbolius savo pavadinimuose.
Atminties taupymo sumetimais, simbolių, galimų naudoti elementų varduose, aibė
apribota iki didžiųjų lotyniškų raidžių, mažųjų lotyniškų raidžių, arabiškų
skaitmenų ir pabraukimo simbolio „_".
Greitam elemento vardo radimui, kai turimas elemento identifikatorius,
sukurtas dinaminis elementų vardų masyvo objektas NumSar, kur elemento
identifikatorius sutampa su masyvo indeksu.
Šiuos du objektus RaidSar ir NumSar į vieną visumą apjungia objektas
Elementai. Šiame objekte papildomai realizuoti metodai naujo elemento įdėjimui,
elemento pašalinimui, elemento pavadinimo radimui žinant identifikatorių,
elemento identifikatoriaus radimui žinant elemento pavadinimą, pilno elementų
sąrašo nusiskaitymui iš užduoto failo, bei elementų pasikartojimo
suskaičiavimui užduotoje transakcijų duomenų bazėje.
Elementų aibės
saugojimui atmintyje sukurtas objektas Aibe. Kiekvienas elementas Aibe objekte
užima 1 bitą. Binarinis elementų saugojimas įgalina greitai atlikinėti veiksmus
su aibėmis - aibių sudėtis, atimtis, daugyba. Šie metodai realizuoti objekte.
Papildomai dar sukurti metodai elemento buvimo aibėje patikrinimui, aibių
palyginimui, išvedimui į nurodytą failą.
Objektas
Palaikymas apibendrina Aibe objektą papildydamas jį atminties ląstele
suskaičiuoto palaikymo saugojimui, bei suriša aibes į tiesinį dinaminį sąrašą.
Visų aukščiau paminėtų duomenų struktūrų apibendrinimui sukurtas
objektas PalaikymuSk. Šis objektas tarnauja ir kaip elementų aibių palaikymo,
bei asociacinių taisyklių radimo ir stiprumo skaičiavimo metodų konteineris.
Objekte sukurti metodai Aibių prijungimui, pašalinimui, radimui, aibės
palaikymo radimui, mažų aibių pašalinimui, palaikymų skaičiavimui, kito objekto
duomenų perėmimui, algoritmas ARGen asociacinių taisyklių radimui.
Mėginio ir Padalinimo algoritmuose naudojamas duomenų bazės dalies
patalpinimas operatyvinėje atmintyje, todėl sukurtas objektas VidBaze
realizuojantis tiesinį sąrašą, kuriame saugomi transakcijų duomenų bazės
elementai. Objektas turi duomenų bloko nusiskaitymo iš užduoto failo metodą.
Sukurtieji objektai yra skirti tik šiam darbui, todėl visi objektų
elementai ir metodai yra viešojo tipo. Norint sukurtuosius objektus panaudoti
kitiems komerciniams tikslams, rekomenduotina vidinius objektų elementus
padaryti privačiais ir palikti atvirus tik interfeisus.
3.3 Algoritmų programinės realizacijos
Turint bendrus visiems algoritmams duomenų objektus, sekančiame etape
buvo sukurtos keturių algoritmų programinės realizacijos. Kadangi buvo iškeltas
reikalavimas vienodiems interfeisams, tai visos programos priima tokią
komandinę eilutę:
<vardas> <baze> <elementai>
<rezultatai> <palaikymas> <stiprumas> <vardas> programos vykdomojo failo pavadinimas
<baze> transakcijų duomenų bazės failo pavadinimas
<elementai> elementų sąrašo failo
pavadinimas <rezultatai> išvedamų
rezultatų failo pavadinimas <palaikymas> pareikalaujamas minimalus
palaikymas <stiprumas>
pareikalaujamas minimalus asociacinės taisyklės stiprumas
3.3.1 Pilno perrinkimo algoritmas
Šio algoritmo
programos išeities tekstas pateiktas priede 3.
Programoje realizuotas elementų sąrašo nuskaitymas, visų įmanomų
elementų aibių suformavimas, transakcijų duomenų bazės skaitymas ir palaikymų
skaičiavimas, asociatyvinių taisyklių radimas. Programa nuskaitinėja
transakcijų duomenų bazę tik vieną kartą.
Elementų aibių
formavimui panaudota rekurentinė funkcija Formuoti.
3.3.2 Apriorinis algoritmas
Šio algoritmo
programos išeities tekstas pateiktas priede 4.
Programa nuskaito elementų sąrašą ir suformuoja kandidatus-aibes po
vieną elementą. Toliau vykdomas ciklas, kol yra nors vienas kandidatas. Cikle
atliekamas transakcijų duomenų bazės praėjimas ir palaikymų suskaičiavimas.
Panaudojant Apriori-Gen algoritmą atliekamas naujų kandidatų radimas. Pabaigus
ciklą atliekamas asociatyvinių taisyklių radimas.
3.3.3 Mėginio algoritmas
Šio algoritmo
programos išeities tekstas pateiktas priede 5.
Programa nuskaito elementų sąrašą ir
patalpina dalį transakcijų duomenų bazės į operatyvinę atmintį. Tada su šia
dalimi atlieka Apriorinį algoritmą. Gautos aibės ir aibės iš negatyvios ribos
funkcijos naudojamos kaip kandidatai pilnam transakcijų duomenų bazės
skanavimui. Jei šio skanavimo metu buvo gautos aibės, priklausiusios negatyvios
ribos funkcijos rezultatui, tai atliekamas kandidatų sąrašo išplėtimas ir dar
vienas transakcijų duomenų bazės praėjimas. Pabaigoje vykdomas asociatyvinių
taisyklių radimas.
3.3.4 Padalinimo algoritmas
Šio algoritmo
programos išeities tekstas pateiktas priede 6.
Programa nuskaito elementų sąrašą ir vykdo ciklą. Ciklo metu patalpina
eilinę duomenų bazės dalį į atmintį ir atlieka Apriorinį algoritmą. Ciklas
baigiamas, kai nuskaitomas paskutinis transakcijų duomenų bazės blokas. Visos
sukauptosios elementų aibės naudojamos kaip kandidatai antram transakcijų
duomenų bazės praėjimui. Pabaigoje vykdomas asociatyvinių taisyklių radimas.
3.3.5 Elementų sąrašo sudarymas
Visų algoritmų programinės realizacijos naudoja
elementų sąrašo failą, todėl duomenų paruošimo fazėje yra reikalingas tokio
failo sudarymas. Šią funkciją atliekančios programos išeities tekstas pateiktas
priede 7.
Programa skaito visus transakcijų duomenų bazės įrašus ir formuoja
pavadinimų medį. Kai pabaigiamas skaitymas, programa įrašo elementų sąrašą į
failą, išrūšiuodama elementus abėcėlės tvarka.
3.4 Testinės duomenų aibės
Algoritmų tyrimui reikia testinių transakcijų duomenų
bazių. Tam buvo pasirinkta naudoti devynias duomenų aibes:
1.
Maža duomenų aibė
iš 5 elementų ir 5 įrašų. Aibė pateikta priede 8. Ši aibė naudojama
pavyzdžiuose teorinėje algoritmų analizėje.
2.
Praplėstas mažos
duomenų aibės variantas. Aibę sudaro 11 elementų ir 23 įrašai. Aibė pateikta
priede 9.
3.
Mažas realių
skambučių poaibis. Šią aibę sudaro 21 elementas ir 40 įrašų. Aibė pateikta
priede 10.
4.
Realių skambučių
vienos paros rajonų kodų duomenys. Aibę sudaro 218 elementų ir 42913 įrašų.
Aibės dalis pateikta priede 11.
5.
Realių skambučių
kilmės kodų vienos paros duomenys. Aibę sudaro 65 elementai ir 45069 įrašai.
Aibės dalis pateikta priede 12.
6.
Realių skambučių
paskirties kodų vienos paros duomenys. Aibę sudaro 228 elementai ir 20479
įrašai. Aibės dalis pateikta priede 13.
7.
Realių skambučių
vienerių metų rajonų kodų duomenys. Aibę sudaro 503 elementai ir 15205852
įrašai. Aibės struktūra identiška 4 variantui.
8.
Realių skambučių
kilmės kodų vienerių metų duomenys. Aibę sudaro 106 elementai ir 16169534
įrašai. Aibės struktūra identiška 5 variantui.
9.
Realių skambučių
paskirties kodų vienerių metų duomenys. Aibę sudaro 502 elementai ir 7608725
įrašai. Aibės struktūra identiška 6 variantui.
3.5 Realių duomenų aibių
paruošimas
Turima informacija apie 50000 telefono abonentų metų skambučius formate
(pateiktas vienas įrašas):
8|1|356|2004.05.20|01:16:59|01111011111111111111111111111111|45|E034|??|
Global|852 65 0199|68|00|890155555|0|-1|-1|0|384|01|12 8|00|55555|??|??|0|
0|1|0|1|0|FF|??|??|0|0|??|0|0|0|0|0|0|00000000000000000000|??|0|0|00|0|
0|00000000000000000000|55555|??|??|0|3|0|25|??
Šiuose įrašuose yra daug perteklinės informacijos,
todėl sukurta programa įrašų supaprastinimui (programos išeities tekstas
pateiktas priede 23). Programa iš įrašų išskiria skambinančiojo ir paskirties
abonentų numerius, tad iš aukščiau pateikto įrašo suformuojamas naujas įrašas:
852650199,890155555
Tokie atskirų
abonentų įrašai panaudojami trijų tipų duomenų aibių sukūrimui:
1.
Skambučių rajonų
kodų duomenys, nusakantys skambučių trauką tarp skirtingų rajonų. Programos,
atliekančios šį pertvarkymą išeities tekstas pateiktas priede 24.
2.
Skambučių kilmės
kodų į vieną fizinį numerį sąrašas, nusakantis rajonų kodus, skambinusius į tam
tikrą numerį. Programos, atliekančios šį pertvarkymą išeities tekstas pateiktas
priede 25.
3.
Skambučių
paskirties kodų iš vieno fizinio numerio sąrašas, nusakantis rajonų kodus, į
kuriuos buvo skambinto iš vieno tam tikro numerio. Programos, atliekančios šį
pertvarkymą išeities tekstas pateiktas priede 26.
Šių tipų aibės buvo naudojamos tiek algoritmų
greitaveikos tyrime, tiek ir pačių duomenų analizėje.
3.6 Algoritmų veikimo tyrimas
Tiriant algoritmus buvo panaudotas automatizuotas
programų paleidimas ir registruojami paleidimo, bei programos darbo pabaigos
laikai. Šiam tikslui sukurtas komandinis failas:
@Echo
Off
if %1.==. Goto Klaida
Echo Paleidimo laikas :
%Time% > Data_1_Met_%1.Run
"..\Met
%1\Met_%1.Exe" Data_1.Dat Data_1.Elm Data_1_Met_%1.Rez
0.3 0.5 Echo Pabaigos laikas : %Time% >> Data_1_Met_%1.Run Goto
Pabaiga
:Klaida
Echo Klaida !
Echo Nenurodytas metodas.
:Pabaiga
Tokie komandiniai failai (jie buvo sukurti kiekvienai
duomenų aibei atskirai) atlikinėjo nurodytų programų iškvietimą, bei laiko
registravimą.
Pilno perrinkimo algoritmas buvo naudojamas tik su pirmomis trejomis
duomenų aibėmis, nes didėjant elementų kiekiui, eksponentiškai didėjo šio
algoritmo pareikalaujamas operatyviosios atminties kiekis. Testuojant su
trečiąja duomenų aibe, turinčia 21 elementą, programa pareikalavo ~900 Mb
darbinės atminties.
3.6.1 Teisingumas
Visi algoritmai gavo teisingus rezultatus, t.y. visi algoritmai rado
visas dideles elementų aibes. Gautieji algoritmų rezultatai yra identiški
visose devyniose duomenų aibėse. Algoritmų sugeneruotos didelės elementų aibės
su palaikymais, bei rastos asociatyvinės taisyklės su jų stiprumo įverčiais
pateiktos prieduose:
|
Duomenų aibė
|
Pareikalautieji parametrai
|
Priedo numeris
|
|||||
|
Palaikymas
|
Stiprumas
|
||||||
|
1
|
30%
|
50%
|
14
|
||||
|
2
|
10%
|
50%
|
15
|
||||
|
3
|
15 %
|
50%
|
16
|
||||
|
Duomenų aibė
|
Pareikalautieji parametrai
|
Priedo numeris
|
|||||
|
Palaikymas
|
Stiprumas
|
||||||
|
4
|
0,5 %
|
20%
|
17
|
||||
|
5
|
0,5 %
|
5 %
|
18
|
||||
|
6
|
0,5 %
|
5 %
|
19
|
||||
|
7
|
0,5 %
|
20%
|
20
|
||||
|
8
|
0,5 %
|
5 %
|
21
|
||||
|
9
|
0,5 %
|
5 %
|
22
|
||||
3.6.2 Greitaveika
Užregistruotieji
algoritmų veikimo laiko įrašai yra pateikti priede 27. Apibendrinta panaudoto
mašininio laiko lentelė atrodo taip:
|
Duomenys
|
Algoritmas
|
|||
|
1
Pilno perrinkimo
|
2
Apriorinis
|
3
Mėginio
|
4
Padalinimo
|
|
|
1
|
00:00:00
|
00:00:00
|
00:00:00
|
00:00:00
|
|
2
|
00:00:00
|
00:00:00
|
00:00:00
|
00:00:00
|
|
3
|
00:00:09
|
00:00:00
|
00:00:00
|
00:00:00
|
|
4
|
|
00:00:05
|
00:00:15
|
00:00:06
|
|
5
|
|
00:00:01
|
00:00:02
|
00:00:01
|
|
6
|
|
00:00:03
|
00:00:06
|
00:00:03
|
|
7
|
|
00:54:58
|
01:35:17
|
00:53:56
|
|
8
|
|
00:05:22
|
00:10:24
|
00:06:23
|
|
9
|
|
00:29:24
|
00:52:31
|
00:28:47
|
Kaip matoma, pilno perrinkimo algoritmas, net su
sąlyginai maža duomenų aibe 3, veikė 9 sek. Taip įvyko dėl operatyviosios
atminties trūkumo ir intensyvaus diskinio „swap" naudojimo. Tačiau reikia
neužmiršti, kad pilno perrinkimo algoritmas visada atlieka tik vieną pilną
transakcijų duomenų bazės nuskaitymą, tad jis būtų naudotinas tais atvejais,
kai turimas didelis įrašų skaičius, tačiau šiuos įrašus sudarančių elementų
kiekis yra nedidelis.
Panagrinėkime detaliau
algoritmų laikus su 7, 8 ir 9 duomenų aibėmis:
Algoritmų greitaveika
Laikas
01:40:48 01:26:24 01:12:00
00:57:36 00:43:12 00:28:48 00:14:24
00:00:00
|
□ 2
|
□ 3
|
□ 4
|
|
|
||
7 8 9
Duomenų
aibė
Šioje histogramoje skaitmenimis 2, 3 ir 4 atitinkamai
pažymėti Apriorinis, Mėginio ir Padalinimo algoritmai. Matome, kad Mėginio
algoritmas visais atvejais buvo prasčiausias. Tai įvyko todėl, kad atliekant
mėginio analizę yra naudojamas mažesnis palaikymo lygis ir yra sugeneruojamas
didelis kandidatų kiekis pilnam transakcijų duomenų bazės skanavimui.
Padalinimo algoritmas buvo pranašesnis už Apriorinį,
su 7 ir 9 duomenų aibėmis, tačiau su 8 duomenų aibe atsiliko. Tai įvyko todėl,
kad 8 duomenų aibėje nėra antros eilės didelių elementų aibių ir Aprioriniam
algoritmui nereikėjo antrojo praėjimo. Šis Padalinimo algoritmo pranašumas,
matomas 7 ir 9 variantuose, turėtų dar labiau išryškėti, jei būtų sudarinėjamos
aukštesnės eilės kandidatų aibės.
3.7 Realių duomenų analizė
Gautieji rezultatai, panaudojant realias telefoninių
skambučių duomenų aibes parodo, kad Asociatyvinių ryšių analizė gali būti
praktiškai pritaikoma versle.
7 duomenų aibės analizė atskleidė miestų kodus, tarp kurių abonentų
vyksta masiškiausi skambučiai. Tai yra vertinga informacija naujam
telekomunikacijų rinkos dalyviui. Jei jis norės plėtoti savo veiklą vietovėje,
aptarnaujamoje tarpmiestiniu kodu [Kodas 1], tai jam tikslinga turėti
tiesioginį sujungimą su kodą [Kodas 2] aptarnaujančia stotimi, nes 78%
skambučių, kuriuose dalyvauja [Kodas 1], vyksta su [Kodas 2]. Operatorius šiuo
atveju galės pasiūlyti pigesnius tarifus į minėtąjį kodą, kas turėtų pritraukti
tokiomis kryptimis aktyviai skambinančius klientus.
9 duomenų aibės analizė parodė, kad yra asociatyviniai ryšiai tarp
kodų, kuriuos renka abonentai. Net 54.4% abonentų, kurie skambina kodais [Kodas
3] ir [Kodas 4], aktyviai skambina ir kodu [Kodas 5]. Tai vėlgi naudinga
informacija, kuria galima remtis atliekant telekomunikacijų tinklo
dimensijavimą ir optimizavimą.
4 Išvados
Šiame darbe buvo atlikta trijų asociatyvinių algoritmų
teorinė analizė, sukurtos keturių algoritmų programinės realizacijos, atlikti
jų teisingumo, bei greitaveikos tyrimai. Papildomai patyrinėta asociatyvinių
ryšių radimo pritaikomumas realių verslo uždavinių sprendimui.
Algoritmų
teisingumo tyrimas parodė, kad:
1.
Visi algoritmai
rado visas dideles elementų aibes.
2.
Gautieji algoritmų
rezultatai yra identiški visose devyniose duomenų aibėse.
Algoritmų
greitaveikos tyrimas nustatė, kad:
1.
Pilno perrinkimo
algoritmas yra iš viso nenaudotinas, kai elementų kiekis >20, tačiau jis
būtų naudotinas tais atvejais, kai turimas didelis įrašų skaičius, tačiau šiuos
įrašus sudarančių elementų kiekis yra nedidelis.
2.
Mėginio algoritmas
buvo mažiausiai našus, nes atliekant mėginio analizę yra naudojamas mažesnis
palaikymo lygis ir yra sugeneruojamas didelis kandidatų kiekis pilnam
transakcijų duomenų bazės skanavimui.
3.
Padalinimo
algoritmas yra pranašiausias kai sudarinėjamos aukštesnės eilės kandidatų
aibės.
Asociatyvinių
ryšių radimas realiuose verslo duomenyse parodė, kad:
1.
Asociatyvinių
ryšių analizė gali būti praktiškai pritaikoma versle.
2.
Remiantis šios
analizės rezultatais galima suformuoti tikslinės klientų grupės pritraukimo
kampaniją.
5 Literatūros sąrašas
1.
David Hand, Heikki Mannila,
Padhraic Smyth. Principles of Data Mining. -Massachusetts:
Massachusetts Institute of Technology, 2001.
2.
Jiawei Han, Micheline
Kamber. Data Mining: Concepts and Techniques. - Morgan
Kaufmann Publishers, 2000.
4.
Margaret H. Dunham. Data
Mining Introductory and Advanced Topics. - New
Jersey: Pearson Education, Inc., 2003.
5.
Mehmed Kantardzic. Data
Mining: Concepts, Models, Methods and Algorithms. -John
Wiley &
Sons, 2003.
6.
Mohammed J. Zaki,
Ching-Tien Ho. Large-Scale Parallel Data Mining. - Berlin:
Springer, 2000.
7.
Paul J. Lucas. The C++ Programmer's
Handbook. -
New Jersey: AT&T Bell Laboratories, 1992.
8.
R. Tidikis, J. S. Pečkaitis, S. Šedbaras. Magistrų baigiamųjų darbų rengimas ir
gynimas. - Vilnius: Lietuvos teisės universitetas, 2003.
6 Santrauka
Šio darbo tikslas yra palyginti asociacinių taisyklių
sudarymo algoritmus ir išanalizuoti jų tinkamumą praktinių uždavinių
sprendimui. Šio tikslo pasiekimui, darbe yra teoriškai išnagrinėti trys didelių
elementų aibių radimo algoritmai:
1.
Apriorinis
algoritmas, kuris remiasi taisykle, kad bet kuris didelės elementų aibės
poaibis turi būti didelis. Šis algoritmas intensyviai naudojasi transakcijų
duomenų baze - maksimalus duomenų bazės peržiūrėjimų skaičius yra vienu
didesnis nei didžiausios rastos didelės elementų aibės eilė.
2.
Mėginio
algoritmas, paimantis duomenų bazės dalį (mėginį) potencialių didelių elementų
aibių radimui. Šis algoritmas leidžia sumažinti duomenų bazės praėjimų skaičių
iki dviejų arba net vieno, geriausiu atveju, kai visos didelės elementų aibės
nustatomos iš mėginio.
3.
Padalinimo
algoritmas, kuris analizuoja duomenų bazę dalimis ir remiasi taisykle, kad 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ų.
Darbo praktinėje
dalyje atliekamas algoritmų palyginimas. Tam sukurtos keturių algoritmų (trejų
išnagrinėtų teorinėje dalyje ir pilno perrinkimo algoritmo) programinės
realizacijos C++ kalba. Siekiant užtikrinti asociacinių taisyklių radimo
algoritmų greitaveiką, programos yra komandinės eilutės aplikacijos be grafinio
vartotojo interfeiso. Algoritmų palyginimas atliktas tiriant algoritmų darbą su
devyniomis testinių duomenų aibėmis, kurių apimtis kinta nuo mažiausios duomenų
aibės, iš 5 elementų ir 5 įrašų, iki
didžiausios - 503 elementai ir 15205852 įrašai. Algoritmai lyginami dviem
aspektais: algoritmų veikimo teisingumas ir algoritmų greitaveika.
Ištyrus algoritmų veikimo teisingumą buvo nustatyta, kad visi
algoritmai gavo teisingus rezultatus, t.y. visi algoritmai rado visas dideles
elementų aibes.
Algoritmų greitaveikos tyrimas parodė, kad pilno perrinkimo algoritmas
yra iš viso nenaudotinas, kai
elementų kiekis >20; mėginio algoritmas buvo mažiausiai našus, nes atliekant
mėginio analizę yra naudojamas mažesnis palaikymo lygis ir yra sugeneruojamas
didelis kandidatų kiekis; padalinimo algoritmas yra pranašiausias kai
sudarinėjamos aukštesnės eilės kandidatų aibės.
Algoritmų tyrimas su realiais duomenimis parodė, kad asociatyvinių
ryšių analizė gali būti praktiškai pritaikoma versle ir gali padėti suformuoti
tikslines klientų grupes.
Komentarų nėra:
Rašyti komentarą