algoritmi de clasificare
Post on 25-Feb-2018
245 Views
Preview:
TRANSCRIPT
-
7/25/2019 Algoritmi de Clasificare
1/65
-
7/25/2019 Algoritmi de Clasificare
2/65
-
7/25/2019 Algoritmi de Clasificare
3/65
Cuprins
Cuprins i
1 Introducere 11.1 Motivatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Structura tezei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Diseminarea rezultatelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Data mining 10
2.1 Reguli de asociere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Algoritmi secventiali utilizati n determinarea
regulilor de asociere . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Metode de paralelizare ale algoritmilor secventiali . . . . . . . . . 11
2.1.3 Discutii asupra tehnicilor existente de extragere a regulilor de asociere 13
2.2 Reguli de clasificare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.1 Algoritmi secventiali utilizati n determinarea
regulilor de clasificare . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Segmentarea datelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Notiuni teoretice fundamentale . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Algoritmi secventiali utilizati n segmentarea datelor . . . . . . . . 15
2.3.3 Metode de paralelizare ale algoritmilor secventiali . . . . . . . . . 16
2.3.4 Discutii asupra tehnicilor existente de segmentare
a datelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Noi algoritmi si modele de paralelizare pentru determinarea tiparelor
frecvente 183.1 Algoritmul Apriori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1 Algoritmul secvential de baza . . . . . . . . . . . . . . . . . . . . . 18
3.1.2 Modificari aduse algoritmului HPA . . . . . . . . . . . . . . . . . . 21
3.1.3 Rezultate si discutii . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Algoritmul Fast Itemset Miner . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.1 Algoritmul secvential de baza . . . . . . . . . . . . . . . . . . . . . 24
3.2.2 Algoritmul paralel - modelul simplu . . . . . . . . . . . . . . . . . 26
3.2.3 Algoritmul paralel - modelul generalizat . . . . . . . . . . . . . . . 28
3.2.4 Rezultate si discutii . . . . . . . . . . . . . . . . . . . . . . . . . . 30
i
-
7/25/2019 Algoritmi de Clasificare
4/65
ii CUPRINS
4 Topologii de comunicare eficiente pentru problema segmentarii datelor 32
4.1 Algoritmul Parallel K-Means . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 Modificarea comunicatiilor pentru algoritmul paralel standard . . . . . . . 33
4.2.1 Topologia de tip hipercub . . . . . . . . . . . . . . . . . . . . . . . 344.2.2 Partitionarea datelor pe topologia de tip hipercub . . . . . . . . . 34
4.2.3 Tiparul comunicational utilizat n determinarea centroizilor . . . . 37
4.3 Rezultate si discutii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Sisteme Grid 41
6 Integrarea aplicatiilor MPI sub forma serviciilor Grid 45
6.1 Justificarea abordarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.1.1 Model generic pentru serviciile Grid destinate
problemei descoperirii de cunostinte . . . . . . . . . . . . . . . . . 45
6.2 Arhitectura serviciului Grid propus . . . . . . . . . . . . . . . . . . . . . . 46
6.2.1 Modelul Fabrica/Instanta . . . . . . . . . . . . . . . . . . . . . . . 466.2.2 Integrarea modulelor MPI n serviciul Grid . . . . . . . . . . . . . 47
6.3 Consideratii asupra aplicatiilor client . . . . . . . . . . . . . . . . . . . . . 48
6.4 Rezultate importante. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7 Concluzii, contributii si directii viitoare de cercetare 51
7.1 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.2 Contributii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
7.3 Directii viitoare de cercetare. . . . . . . . . . . . . . . . . . . . . . . . . . 55
Bibliografie 57
-
7/25/2019 Algoritmi de Clasificare
5/65
Capitolul 1
Introducere
1.1 Motivatie
Un numar din ce n ce mai mare de domenii stiintifice sau economice se confrunta cu
o crestere impresionanta a volumului de date acumulat. Aceasta stare de fapt este
ncura jata si de dezvoltarea rapida a tehnicii de calcul si a dispozitivelor si mediilor de
stocare. Extragerea informatiilor relevante din aceste baze de date reprezinta n contin-
uare un proces laborios, necesitand resurse costisitoare si, uneori, greu accesibile. Toto-
data, timpul necesar pentru obtinerea informatiilor necesare pentru diferite decizii sau
operatii ce trebuie efectuate asupra datelor tinta este din ce n ce mai mare, implicand
deseori resurse aditionale, n ciuda cresterii puterii de calcul si a scaderii costurilor echipa-
mentelor de calcul de mare performanta [Two 05,Adamo 00]. Mai mult, datele stocate
pot ngloba informatii utile ce sunt adeseori ascunse unei analize directe din partea unor
eventuali operatori umani.
In scopul reducerii acestor costuri, precum si pentru micsorarea timpilor necesari, sunt
dezvoltate noi metode pentru analiza detaliata a datelor, metode al caror rezultat este
reprezentat de o restructurare automata/semiautomata a datelor [Adamo 00]. Astfel,
prin dezvoltarea acestor metode avansate de analiza se ncearca regasirea acelor informatii
suplimentare care pot evidentia moduri noi de grupare a datelor stocate sau relatii noi
ntre aceste date. Aceste tehnici de analiza sunt cunoscute sub denumirea de tehnici de
descoperire a cunostintelor n baze de date. Descoperirea de cunostinte n baze de date
este descrisa ca fiind un proces ce se desfasoara n mai multe etape si are drept scop
detectarea automata a unor tipare si identificarea unor relatii noi ntre datele stocate
[Two 05]. Semnificatia rezultatelor obtinute este strict corelata cu domeniul pentru carese aplica aceste noi tehnici: informatiile noi pot fi utile n realizarea unor predictii asupra
unor noi nregistrari de acelasi tip sau pot reprezenta pur si simplu o noua descriere sau
o noua perspectiva asupra datelor existente.
Cu alte cuvinte, descoperirea de cunostinte nseamna extragerea si interpretarea
informatiilor de interes - netriviale, implicite, necunoscute anterior si potential utile -
sau descoperirea de tipare n datele stocate sub diferite forme. Procesul n sine include
urmatoarele etape [Two 05]:
1. ntelegerea domeniului de aplicatie, a cunostintelor anterioare, precum si a scopu-
1
-
7/25/2019 Algoritmi de Clasificare
6/65
rilor ce se doresc a fi atinse prin analiz a;
2. crearea unui set tinta de date, fapt ce implica selectarea unui set de date, con-
centrarea asupra unui subset de variabile sau modele de date asupra carora sa se
execute procesul de descoperire a cunostintelor;
3. curatareadatelor si preprocesarea acestora: colectarea informatiilor necesare pen-
tru modelarea sau recunoastereazgomotelor, nlaturarea acestorzgomote si a datelor
ce nu furnizeaza informatii relevante, generarea de strategii pentru tratarea c am-
purilor de date lipsa sau incomplete;
4. reducerea seturilor de date ce vor fi analizate prin transformarea unui set de
atribute, prin extrapolarea unor valori de interes sau pur si simplu prin restrangerea
setului complet de atribute/caracteristici catre un set minimal de strict interes;
5. alegerea unei metode de extragere a informatiilor, n funct ie de telul dorit (ex-
tragerea regulilor de clasificare a datelor, extragerea regulilor de asociere sau analizadiferitelor secvente ntalnite n baza de date);
6. alegerea unui algoritm adecvat: selectarea metodelor de analiza n functie de even-
tuale constrangeri impuse de particularitatile datelor analizate sau adoptarea unui
model valabil, adecvat domeniului tinta;
7. aplicarea metodelor de analiza si extragerea efectiva a informatiilor noi: identifi-
carea tiparelor de interes pentru o forma de reprezentare particulara sau pentru
un set de astfel de reprezentari, precum reguli sau arbori de clasificare, reduceri,
clusterizari, asocieri, seturi frecvente, s.a.m.d.;
8. validarea si interpretarea rezultatelor extrase;
9. consolidarea informatiilor descoperite.
Etapele descrise anterior sunt sintetizate n Figura1.1.
Figura 1.1: Procesul de descoperire de cunostinte (adaptare dupa [Fayyad 96])
2
-
7/25/2019 Algoritmi de Clasificare
7/65
In mod uzual, procesul de descoperire de cunostinte n volume mari de date este con-
stituit din urmatoarele metode/modele de analiza (n engleza: data mining) [Fayyad 96]:
identificarea gruparilor de date - clusterizare: taskdescriptiv ce are drept scop
identificarea unui numar finit de categorii (grupuri/clustere) ce descriu mai bine
datele existente pe baza similaritatilor dintre aceste date;
identificarea regulilor de clasificare: taskpredictivce are drept scop determinarea/
,,nvatarea, pe baza datelor existente, a unei funct ii de mapare (clasificator) cu
rol n determinarea claselor de apartenenta pentru datele noi ce vor fi analizate;
regresia: task predictiv ce are drept scop determinarea unei functii de mapare
a valorilor atributelor de interes peste numere reale pentru a prezice un anumit
comportament;
identificarea tiparelor frecvente si a regulilor de asociere: taskdescriptiv ce are
drept scop determinarea subseturilor ce apar mpreuna ntr-un anumit set de valorisau determinarea unor relatii ( n mod uzual, relatii de co-existenta) n cadrul acelui
set de valori;
analiza secventelor: taskdescriptivce are drept scop determinarea acelor secvente
ce apar mpreuna n cadrul unui anumit volum de date. Spre deosebire de deter-
minarea tiparelor frecvente, n cadrul analizei secventelor entitatile ce pot constitui
o secventa nu sunt n mod necesar omogene (nu au aceeasi semnificatie). In plus,
o secvent a frecventanu este conditionata de o limita de tip suport minim.
Aplicarea corecta a etapelor descrise anterior, precum si indentificarea corespunza-
toare a metodelor de analiza ce vor fi utilizate si obtinerea unor rezultate de interes nu
este posibila daca nu sunt bine ntelese limitarile descoperirii de cunostinte. Tehnicile
si modelele utilizate n descoperirea de cunostint e nu sunt general valabile. Nu ofera
rezultate ,,pe tava, indiferent de natura domeniului pentru care sunt aplicate. In foarte
mult cazuri, rezultatele obtinute nu sunt valabile fara o eventuala certificare din partea
unui grup de potentiali experti umani pe domeniul de interes abordat. Mai mult, un
set particular de rezultate obtinute pentru un anumit caz nu este general valabil pentru
domeniul din care face parte cazul respectiv. Practic, se poate afirma ca provocarile n
domeniu deriva si din caracteristicile intrinseci ale procesului n sine: trebuie cunoscut
ce se cauta si trebuie cunoscute datele n care se cauta, altfel rezultatele obtinute pot fi
irelevante.
Rezumand cele expuse pana acum, se poate afirma ca domeniul descoperirii de cu-
nostinte n volume mari de date este un domeniu deosebit de complex, cu un pronuntatcaracter interdisciplinar. Provocarile ridicate de metodele de analiza caracteristice nu
pot fi surmontate fara colaborarea specialistilor din diverse arii de cercetare. Mai mult,
aceste metode de analiza trebuie sa gestioneze un volum din ce n ce mai mare de date
achizit ionate. Astfel, pentru o buna parte dintre algoritmii ce adreseaza problemele
specifice descoperirii de cunostinte trebuie dezvoltate modele de paralelizare si/sau de
distribuire eficiente. Acest fapt implica existenta unor echipamente si a unei infrastruc-
turi hardware si software adecvate, fara a conditiona accesul eventualilor experti ce nu
activeaza n domeniul IT. O posibila solutie pentru depasirea acestor impedimente este
reprezentata de sistemele Grid. Un exemplu edificator n acest sens este reprezentat de
3
-
7/25/2019 Algoritmi de Clasificare
8/65
proiectul Data Mining Grid1. Scopul proiectului este de a expune un framework coe-
rent pentru dezvoltarea si expunerea de aplicatii de descoperire de cunostinte n cadrul
sistemelor Grid.
Termenul desistem Grida fost utilizat pentru prima data la mijlocul anilor 90 pen-tru a sintetiza specificatiile unei arhitecturi avansate de calcul distribuit. Ian Foster,
considerat de multi personalitatea numarul unu n domeniul sistemelor Grid, subliniaza
n [Foster 01] faptul ca modalitatea anterioara de definire este mult prea sumara pen-
tru a ncapsula conceptele unui astfel de sistem. Potrivit lui Foster, problemele reale
adresate de Grid-uri sunt reprezentate de partajarea resurselor si rezolvarea problemelor
n cadrul unui mediu dinamic multi-institutional [Foster 01]. Conceptul de resursa n
cadrul unui sistem Grid nglobea-za semnificatii diverse. Astfel, o resursa Grid poate
nsemna un calculator sau un cluster de calculatoare, un produs software, un set de date
sau mecanismul de acces al unui set de date.
Partajarea resurselorcapata n acest context un plus semnificativ de complexitate fata
de cazul unei partajari uzuale de fisiere. Foster subliniaza faptul capartajarearesurselor
este realizata ntr-o maniera colaborativa, n mod necesar bine controlata [Foster 01].
Pentru fiecare resursa exista unul sau mai multifurnizori si unul sau mai multiutilizatori.
Pentru fiecare dintre cele doua roluri exista un set de reguli ce definesc n mod clar,
neambiguu, modalitatile acceptate prin intermediul carora se pot accesa resursele oferite,
drepturile de acces asupra acelor resure, mecanismele de utilizare, etc.. In acest context,
se defineste conceptul de Organizatie Virtuala (OV): grup de indivizi si/sau institutii ce
stabilesc un set comun de reguli pentru partajarea resurselor disponibile.
Sistemele Grid reprezinta sisteme de calcul paralel si distribuit care permit partajarea,
selectia si agregarea resurselor distribuite de-a lungul mai multor domenii administrative
bazate pe disponibilitatea, performanta, capacitatea, costul si cererile utilizatorilor ser-
viciilor de calitate [Craus 05]. Practic, aceste sisteme de calcul de mare performanta sunt
destinate rularii proceselor de mare complexitate. Analizand schema unui proces de des-
coperisre de cunostinte (Figura1.1), se poate afirma cu certitudine ca sistemele Grid pot
furniza suportul necesar pentru oricare dintre etapele implicate. Un sistem Grid ofera
mecanismele necesare stocarii unui volum mare de informatii, precum si mecanismele de
acces consecvent la acele date. Prin intermediul sistemelor de calcul paralel/distribuit
nglobate, Grid-urile pot rula cu usurinta modulele de preprocesare a datelor sau orice
algoritm de analiza dorit de catre expertii umani.
Pe de alta parte, viziunea care a condus la dezvoltarea conceptului de sistem Grid
este de a oferi suportul hardware si software necesar colaborarii expertilor din diverse
domenii de cercetare. Asa cum aminteau si Bote-Lorenzo et al. n [Bote-Lorenzo 03], un
sistem Grid este caracterizat de acces transparent si universal. Acest lucru implica faptul
ca un eventual cercetator fara pregatire profunda n domeniul calculatoarelor ar trebui safie capabil sa utilizeze diferitele resurse expuse de un sistem Grid ca si cum ar utiliza un
browser instalat pe calculatorul personal. Aceasta consecinta este deosebit de importanta
pentru domeniul descoperirii de cunostinte, ntrucat oricat de bine automatiza ar fi o
anumita metoda de analiza implicata n acest proces, rezultatele oferite nu sunt valabile
fara o eventuala re-evaluare din partea unui expert uman. Utilizand un sistem Grid,
acest expert uman se poate concentra pe obtinerea si interpretarea rezultatelor dorite,
accesul la resursele necesare fiind transparent.
1Pentru mai multe detalii: http://www.datamininggrid.org/
4
-
7/25/2019 Algoritmi de Clasificare
9/65
Aceasta lucrare si propune investigarea ambelor domenii prezentate: domeniul des-
coperirii de cunostinte n volume mari de date si domeniul sistemelor Grid. Pentru
primul dintre acestea, cercetarile cuprinse n aceasta lucrare sunt axate pe nucleul acestui
proces: algoritmii de analiza a seturilor de date preprocesate. In acest context, se puneaccentul pe determinarea tiparelor frecvente si a regulilor de asociere si pe problemele
legate deidentificarea gruparilor similare de date(data clustering). Alegerea este bazata
pe popularitatea celor doua metode de analiza. Pentru ambele componente exista n
prezent un numar considerabil de algoritmi secventiali si paraleli. Fiecare dintre acestia
exploateaza diversele particularitati ale datelor de lucru sau ale codificarii acestor date
n vederea obtinerii rapide a unor rezultate de interes coerente.
Pentru problema determinarii tiparelor frecvente si a regulilor de asocieresunt ana-
lizati initial doi algoritmi fundamentali: algoritmul Apriori [Agrawal 94] si algoritmul
FP-Growth [Han 00]. Ambii algoritmi (descrisi pe larg n subcapitolul 2.1.1) utilizeaza
structuri arborescente si considera ca obiectele de lucru sunt codificate prin index nu-
meric. Cu toate ca ambii algoritmi obtin performante bune din punctul de vedere al
timpului de raspuns oferit, este utila investigarea unor noi modaliati de codificare a
bazei de date tinta. In acest context, este prezentata o noua modalitate de codificare
binara a seturilor de date supuse analizei. Sunt analizate avantajele si dezavantajele
aduse de o astfel de codificare atat pentru cazul secvential, cat si pentru unul dintre
cele mai cunoscute modele de paralelizare ale algoritmului Apriori - Hash Partitioned
Apriori (HPA) [Shintani 96]. Este, de asemenea, analizat un nou model algoritmic pen-
tru determinarea tiparelor frecvente. Acest nou model este axat, similar algoritmului
Apriori, pe generarea si validarea unor seturi candidate. Deosebirea fundamentala fata
de Apriori este aceea ca noii candidati nu sunt generati ntr-o maniera strict marginita.
Astfel, principiul noului algoritm este de a grupa itemii frecventi/itemseturile frecvente
n intervale si de a obtine noileitemseturi candidateprin reuniuni deitemseturi frecvente
cu nucleul comun, ce apartin de intervale diferite.Pentru problemaidentificarii gruparilor similare de date, n lucrarea de fata accentul
cade pe analiza algoritmului K-Means Clustering si a uneia dintre cele mai des utilizate
metode de paralelizare ale algoritmului -Parallel K-Means - PKM. Rezultatele cecetarilor
efectuate pentru acest algoritm sunt menite sa evidentieze importanta utilizarii unor
topologii de comunicatie adecvate pentru a obtine implementari eficiente ale paralelizarii
n discutie. Pentru o parte dintre algoritmii analizti, lucrarea a avut n vedere abordari
paralele bazate pe implementarea LAM/MPI2 a standardului MPI (Message Passing
Interface).
Partea a doua a acestei lucrari este dedicata sistemelor Grid. Cercetarile efectuate
n cadrul acestui domeniu vizeaza posibilitatile de expunere a aplicatiilor dezvoltate uti-
lizand standardul MPI sub forma servicii Grid. Primul considerent care trebuie avut nvedere n justificarea acestei alegeri este legat de evolutia sistemelor Grid. Inca de la
nceputul anilor 2000, Foster utilizeaza notiunea de,,serviciu pentru a defini conceptul
deOV [Foster 01]:
...examples of VOs: the applicationserviceproviders, storageservice providers,
cycle providers, and consultants engaged by a car manufacturer to perform
scenario evaluation during planning for a new factory...
2Pentru mai multe detalii http://www.lam-mpi.org/
5
-
7/25/2019 Algoritmi de Clasificare
10/65
In anul 2002, Foster et al. definesc un prim set de specificatii pentru sistemele Grid
orientate pe servicii [Foster 02c]. Aceste specificatii au devenit standardul de facto n
cadrul sistemelor Grid bazate pe arhitecturi orientate pe servicii - standard cunoscut n
prezent sunt numele de Open Grid Services Architecture (OGSA). Unul dintre primelemiddleware-uri ce a implementat acest standard este Globus Toolkit (ncepand cu ver-
siunea 3.0)3. Cu toate ca n versiunile curente acest middleware asigura suport pentru
aplicatiile Griddezvoltate utilizand diferite implementari ale standardului MPI (MPICH-
G2, LAM/MPI - prin job-managerulimplicit, OpenMPI), experimentele au evidentiat
faptul ca acest suport nu este bine stabilizat pentru expunerea acestui tip de aplicatii
sub formaserviciilor Grid. Avand n vedere aceasta observatie, este propus un model de
expunere a aplicatiilor paralele dezvoltate utilizand LAM/MPI sub forma unui serviciu
Grid. Acest model este prezentat pe larg n capitolul 6, implementarea fiind expusa de
Grid-ul GRAI dezvoltat n cadrul proiectului de cercetare 74 CEEX-II03/31.07.2006.
Un al doilea motiv pentru alegerea acestei directii de cercetare este derivat din mo-
delul propus de Foster et al. pentru abordarea problemelor legate de descoperirea de
cunostinte n cadrul sistemelor Grid [Foster 02b]. Practic, considerand natura complexa
a procesului amintit anterior, Foster et al. justifica faptul ca metodele de analiza speci-
fice ar trebui implementate sub forma de servicii Grid. Acest fapt atrage dupa sine o
mbinare mai facila a metodelor de analiza pentru aplicatiile complexe. Modelul descris
n [Foster 02b] este prezentat n subcapitolul6.1.1si reprezinta puntea de legatura ntre
cele doua domenii de cercetare abordate.
1.2 Structura tezei
Lucrarea de fata este structurata pe doua parti. Prima parte, intitulataALGORITMI
PARALELI PENTRU APLICATII DATA MINING, este dedi-cata domeniuluidescoperirii de cunostinte n volume mari de date si cuprinde trei capitole.
Incapitolul2 este analizat stadiul actual al cercetarilor din cadrul acestui domeniu.
Sunt prezentate fundamentele teoretice care stau la baza determinarii tiparelor frecvente
si a regulilor de asociere, a determinarii regulilor de clasificare si, respectiv, a metodelor de
clusterizare. Pentru fiecare dintre aceste metode sunt analizat i atat algoritmii secventiali
importanti, cat si metode eficiente de paralelizare ale acestora. In centrul atentiei se afla
algoritmii de identificare a tiparelor frecvente n volume mari de date si cei utilizati n
clusterizarea datelor. In cazul determinarii tiparelor frecvente sunt analizati doi dintre
cei mai importanti algoritmi n domeniu: Apriori si FP-Growth. In ambele cazuri sunt
supuse atentiei atat modelele secventiale cat si cele paralele. In cazul tehnicilor de
clusterizare, analiza este focalizata n jurul algoritmului K-Means Clustering. Alegerea
este justificata de popularitatea acestui algoritm n cadrul domeniilor ce necesita astfel
de analize de date. Subcapitolul de concluzii aferent evidentiaza un set suplimentar de
motive ce justifica alegerea temei de cercetare.
Capitolul3 prezinta modificarile propuse pentru optimizarea algoritmului secvential
Apriori (subcapitolul3.1). Aceste modificari vizeaza codarea binara a itemitor si, respec-
tiv, a seturilor de itemi. In continuare sunt discutate modalitatile prin care sunt modifi-
cate structurile de date caracteristice algoritmului n discutie. In subcapitolul urmator
este prezentata o propunere de modificare a algoritmului HPA, propunere care se refer a
3Pentru mai multe detalii http://www.globus.org/
6
-
7/25/2019 Algoritmi de Clasificare
11/65
la implementarile MPI ale HPA. Aceasta vizeaza unul dintre puncte slabe ale modelu-
lui de paralelizare amintit anterior: nivelul ridicat al comunicatiilor implicat de faza de
generare de candidati caracteristica algoritmului secvential de baza. Datorita codificarii
binare amintite anterior, se poate slabi conditia de generare a cheii de dispersie utilizatan identificarea seturilor de itemi. Astfel, cheia de dispersie poate fi aplicata asupra
setului generator al candidatului curent, fapt ce atrage dupa sine o reducere semnifica-
tiva a comunicatiilor amintite. In continuare, subcapitolul3.2prezinta un nou algoritm
pentru determinarea seturilor frecvente. Acest algoritm este bazat tot pe generarea de
candidati, similar algoritmului Apriori. Spre deosebire de Apriori, candidatii noi nu sunt
generati pe baza combinarii unor seturi frecvente de dimensiune k-1 (unde k reprezinta
lungimea seturilor corespunzatoare iteratiei curente), ci pe a mpartiitemii/itemseturile
frecvente n intervale initial disjuncte si a generacandidatiinoi din reuniuni deitemseturi
ce apartin de intervale diferite.
Capitolul 4 vizeaza mbunatatirile aduse unor implementari MPI ale algoritmu-
lui Paralel K-Means. Cu toate ca paralelizarea existenta este eficienta, foarte multe
dintre implementarile curente nu tin cont de un factor deosebit de important pentru
paralelizarile bazate pe standardul MPI: topologia de comunicatie dintre noduri. O
topologie adecvata unui anumit algoritm poate reduce considerabil timpul suplimentar
implicat n comunicatii. In acest sens, n prima parte a subcapitolului este prezentata n
detaliu o astfel de topologie, cu perfomante crescute pentru comunicatiile colective im-
plicate dePKM. Peste aceasta topologie sunt detaliate modul de partitionare a datelor si
modificarile aduse n determinarea colectiva a datelor de lucru pentru o eventuala iteratie
ulterioara. Implementarea astfel modificata este comparata din punctul de vedere al tim-
pului de raspuns oferit cu o implementare ce utilizeaza bibliotecile puse la dispozit ie de
implementarea LAM/MPI a standardului MPI.
Partea a doua a tezei, intitulata SOLUTII DE IMPLEMENTARE PENTRU
APLICATII DATA MINING IN SISTEME GRID, vizeaza cerce-tarile efectuatepentru expunerea metodelor de analiza aferente procesului de descoperire de cunostinte
n cadrul unui sistem Grid. Aceasta a doua parte cuprinde doua capitole.
Capitolul 5 descrie n detaliu middleware-ul Globus Toolkit, versiunea 4. Sunt
prezentate arhitectura generala a middleware-ului, standardele pe care se bazeaza acesta
si suportul oferit pentru dezvoltarea serviciilor Grid. Sunt aduse n discutie si cateva
dintre implementarile cele mai importante ale standardului MPI si este analizat suportul
oferit de GT 4 pentru acestea.
Capitolul6este dedicat solutiei propuse pentru integrarea aplicatiilor paralele dez-
voltate utilizand standardul mentionat sub forma de servicii Grid. Accentul se pune
pe aplicatiile dezvoltate utilizand implementarea LAM/MPI a standardului. Motivul
acestei alegeri se bazeaza pe faptul ca LAM/MPI versiunea 7.1.* este printre singureleversiuni ce ofera suport complet pentru versiunea 2.0 a specificat iilor MPI. Este prezentat
modelul generic propus de Foster et al. pentru servicii Grid destinate analizei datelor.
Pornind de la acest model, a fost dezvoltat un serviciu capabil s a expuna diferite module
de analiza caracteristice data mining, module ce sunt implementate utilizand LAM/MPI.
Managerul de job-uri Grid utilizat este cel predefinit pentru versiunea curenta a toolkit-
ului n discutie (Fork). Serviciul dezvoltat respecta arhitecturaFabrica/Instanta si poate
fi intergrat usor cu orice instalare standard a GT 4. In finalul capitolului este prezentate
un set de rezultate importante menite sa sublinieze necesitatea unui astfel de serviciu.
Incapitolul7 sunt prezentate sintetic rezultatele obtinute si sunt evident iate contri-
7
-
7/25/2019 Algoritmi de Clasificare
12/65
butiile aduse pentru cele doua domenii abordate. Finalul capitolului contine propunerile
de cercetare ce deriva din rezultatele obtinute.
1.3 Diseminarea rezultatelor
Articolele stiintifice ce stau la baza acestei lucrari au fost publicate n reviste (3), volume
de specialitate (3) sau prezentate la conferinte internationale (6) si sunt indexate n baze
de date bibliografice recunoscute: Thomson ISI (3), IEEE (1).
A. Archip, M. Craus, and S. Arustei. Efficient Grid Service Design to In-
tegrate Parallel Applications. In Marten van Sinderen, editor,Proceedings of
2nd International Workshop on Architectures, Concepts and Technologies for
Service Oriented Computing held in conjunction with 3rd International Con-
ference on Software and Data Technologies, pages 7-16, Porto PORTUGAL,
2008. INSTICC Press. (ISI)
M. Craus & A. Archip. A generalized parallel algorithm for frequent item-
set mining. In ICCOMP08: Proceedings of the 12th WSEAS international
conference on Computers, PTS 1-3, pages 520-523. World Scientific and En-
gineering Academy and Society (WSEAS), 2008. (ISI)
S. Arustei, M. Craus, and A. Archip. Towards a Generic Framework for
Deploying Applications as Grid Services. In Marten van Sinderen, editor,
Proceedings of 2nd International Workshop on Architectures, Concepts and
Technologies for Service Oriented Computing held in conjunction with 3rd
International Conference on Software and Data Technologies, pages 17-26,
Porto, Portugal, 2008. INSTICC Press. (ISI)
S. Arustei,A. Archipand C.M. Amarandei. Grid Based Visualization Using
Sort-Last Parallel Rendering. In H.N. Teodorescu and M. Craus, editors,
Scientific and Educational Grid Applications, pages 101-109, Iasi, Romania,
2008. Politehnium.
A.Archip, C.M. Amarandei, S. Arustei, and M. Craus. Optimizing Associa-
tion Rule Mining Algorithms Using C++ STL Templates. Buletinul Institu-
tului Politehnic din Iasi, Automatic Control and Computer Science Section,
LIII(LVII):123-132, 2007.
C.M. Amarandei,A. Archip, and S. Arustei. Performance Study for MySql
Database Access Within Parallel Applications. Buletinul Institutului Po-
litehnic din Iasi, Automatic Control and Computer Science Section, LII(LVI):
127 - 134, 2006.
A. Archip, S. Arustei, C.M. Amarandei and A. Rusan. On the design of
Higher Order Components to integrate MPI applications in Grid Services.
In H.N. Teodorescu and M. Craus, editors, Scientific and Educational Grid
Applications, pages 25-35, Iasi, Romania, 2008. Politehnium.
8
-
7/25/2019 Algoritmi de Clasificare
13/65
C.M. Amarandei, A. Rusan,A. Archipand S. Arustei. On the Development
of a GRID Infrastructure. In H.N. Teodorescu and M. Craus, editors, Sci-
entific and Educational Grid Applications, pages 13-23, Iasi, Romania, 2008.
Politehnium.
S. Caraiman, A. Archip, and V. Manta. A Grid Enabled Quantum Com-
puter Simulator. InSYNASC09: Proceedings of the 11th International Sym-
posium on Symbolic and Numeric Algorithms for Scientific Computing, Ti-
misoara, Romania, 2009. IEEE Xplore.
S. Arustei, A. Archip, and C.M. Amarandei. Parallel RANSAC for Plane
Detection in Point Clouds. Buletinul Institutului Politehnic din Iasi, Auto-
matic Control and Computer Science Section, LIII(LVII):139-150, 2007.
M. Craus, H.N. Teodorescu, C. Croitoru, O. Brudaru, D. Arotaritei, M. Calin
& A. Archip. Academic Grid for Complex Applications - GRAI. In Proc.of 16th International Conference on Control Systems and Computer Science.
POLITEHNICA University of Bucharest, May 22-25 2007.
M. Craus, H.N. Teodorescu, C. Croitoru, O. Brudaru, D. Arotaritei, M. Calin
& A. Archip. The Service Layer of the Academic Grid GRAI. In Proc. of
16th International Conference on Control Systems and Computer Science.
POLITEHNICA University of Bucharest, May 22-25 2007.
Lucrari acceptate spre publicare:
A. Archip, V. Manta & G. Danilet, Parallel K-Means Revisited: A Hy-
percube Approach, In Proceedings of the 10th International Symposium on
Automatic Control and Computer Science, October 2010.
I. Astratiei & A. Archip, A Case Study on Improving the Performance
of Text Classifiers, In Proceedings of the 10th International Symposium on
Automatic Control and Computer Science, October 2010.
O parte dintre cercetarile ce au condus la scrierea acestei teze au fost efectuate n
cadrul proiectului de cercetareGrid academic pentru aplicatii complexe(GRAI), contract
74 CEEX-II03/31.07.2006, Parteneri: UT Iasi (coordonator), UAIC Iasi, USAMV Iasi,
IIT Iasi, Director proiect: prof. dr. Mitica Craus, Perioada: 2006 - 2008.
9
-
7/25/2019 Algoritmi de Clasificare
14/65
Capitolul 2
Data mining
2.1 Reguli de asociere
Problema extragerii regulilor de asociere din baze de date poate fi formulata astfel: Dat
fiind un set de obiecte (itemi)I si un set de tranzactiiD(sau colectii/multimi de itemi),
sa se identifice toate regulile de forma:
A B (2.1)
unde A si B reprezinta colectii disjuncte de obiecte [Agrawal 94,Zaki 99].
O observatie importanta este aceea ca regulile de asociere de forma (2.1) nu trebuie
interpretate ca fiind implicatii n sensul existenta setului A implica existena setului B.
Aceste reguli au semnificatiacoexistentei seturilor A si B.
2.1.1 Algoritmi secventiali utilizati n determinarea
regulilor de asociere
In prezent exista un numar considerabil de algoritmi secventiali propusi pentru extragerea
regulilor de asociere. Fiecare dintre acestia propune fie noi structuri de date pentru
generarea si testarea seturilor candidate (cazul algoritmilor ce extind Apriori, propus
n [Agrawal 94]), fie reorganizeaza spatiul de cautare n forme structurate, fie modifica
organizarea bazei de date propuse spre analiza (cum este cazul algoritmilor bazat i pe
Eclat). O sinteza coerenta a algoritmilor dezvoltati pana n anul 1999, este propusa de
Zaki n [Zaki 99].
O prima diferenta apare n modul n care sunt cautate itemseturile frecvente n bazarelatiilor de incluziune ce apar ntre multimi. Astfel, algoritmii bazati pe Apriori, precum
si algoritmii anteriori Apriori (AIS si SETM), folosesc o asa numita cautare bottom-up.
Practic, n cazul acestor algoritmi se porneste de la itemii frecventi si pe baza acestora
se genereaza apoi itemseturi frecvente de dimensiune din ce n ce mai mare, pana la
determinarea totala sau partiala a itemseturilor maximale. Exista nsa situatii cand este
preferata o abordare top-down, pentru indentificarea itemseturilor maximale. In acest
sens au fost dezvoltati algoritmi de cautare hibrizi - cum ar fi, spre exemplu, MaxEclat
si, respectiv, MaxClique. Acest tip de algoritmi identifica, ntr-o prima etapa, o multime
de itemseturi frecvente de dimensiune variabila. In etapele urmatoare, aceste itemseturi
10
-
7/25/2019 Algoritmi de Clasificare
15/65
sunt fie combinate pentru obtinerea unor itemseturi maximale, fie sunt sparte pentru
obtinerea subseturilor frecvente incluse.
O alta deosebire importanta, evidentiata de Zaki n [Zaki 99], este legata de modul n
care sunt generate seturile candidate si, respectiv, identificate apoi itemseturile frecvente.Astfel, algoritmii bazati pe Apriori sau pe FP-Growth realizeaza o cautare completa a
spatiului solutiilor, identificand n final toate itemseturile frecvente si, respectiv, toate
regulile de asociere posibile. Exista, nsa, cazuri n care nu este necesara identificarea
tuturor tiparelor frecvente. De asemenea, situatia propusa spre analiza poate impune
regasirea numai a itemseturilor maximale.
Un alt aspect deosebit de important n diferentierea algoritmilor existenti este orga-
nizarea bazei de date tinta. Majoritatea algoritmilor - Apriori si derivati, FP-Growth,
DHP, SEAR, etc. - sunt orientati pe analiza bazelor de date cu organizare orizontala:
nregistrarile sunt memorate n forma[identificator tranzactie (TID), lista itemi inclusi n
tranzactie]. Exista o grupa de algoritmi - Eclat si derivati, si, respectiv, Clique si derivati
- care sunt orientati pe analiza bazelor de date cu organizare verticala: nregistrarile sunt
memorate sub forma [item, lista identificatori tranzactii ce includ itemul (TID)].
Unul dintre principalii algoritmi de extragere a regulilor de asociere, folosit si n
prezent, este algoritmul Apriori, propus n [Agrawal 94]. Principiul de baza al algo-
ritmului este de a calcula seturile frecvente de itemi de dimensiune k prin combinari
ale seturilor de dimensiune k 1, pentru k cel putin egal cu 2. In plus, n partea de
generare a seturilor candidate de dimensiune k, se impune urmatoarea constrangere:
un set candidat de dimensiune k nu poate fi obtinut decat prin combinarea a 2 seturi
frecvente de dimensiunek 1 ce au primelek 2 elemente comune. In plus, se impune si
conditia ca orice subset de dimensiune k 1 inclus n k-itemsetul candidat sa fie frecvent
[Agrawal 94,Adamo 00,Tan 05].
Zaki nota faptul ca algoritmul propus de Agrawal et al. n [Agrawal 94] obtine o
complexitate timp liniar marginita fata de dimensiunea listei de tranzactii [Zaki 99].Un al doilea algoritm deosebit de important pentru problema regasirii tiparelor frec-
vente este reprezentat de algorimul FP-Growth [Han 00]. Acesta este, n prezent, unul
dintre cei mai rapizi algoritmi folositi n extragerea tiparelor frecvent. Algoritmul este
bazat pe o reprezentare de tip arbore prefix (arbore FP) a tranzactiilor nregistrate n
baza de date tinta, modalitate de reprezentare care reduce considerabil memoria folosita
pentru stocarea tranzactiilor [Han 00]. Ideea de baza a algoritmului este bazata pe o
schema de eliminare recursive [Han 00,Grahne 05]
2.1.2 Metode de paralelizare ale algoritmilor secventiali
In aceasta sectiune sunt prezentate cateva dintre cele mai cunoscute paralelizari pentrualgoritmii prezentati anterior.
Paralelizari ale algoritmului Apriori
Tehnicile de paralelizare ale algoritmului Apriori pot fi mpartite n 4 categorii, n
functie de tinta paralelizarii [Shintani 96,Zaki 99,Kumar 03]:
distribuirea candidatilor - paralelizari de tip ,,candidate distribution: generarea
candidatilor este distribuita ntre nodurile de procesare. Partile bazei de date sunt
memorate pe fiecare procesor n parte. Multimea de candidati este comunicata
11
-
7/25/2019 Algoritmi de Clasificare
16/65
celorlalte procesoare printr-un proces de tip gather/broadcast. O observatie impor-
tanta este cea a lui Zaki, care sustine ca acest tip de paralelizare este una extrem
de ineficienta, datorita comunicatiilor excesive [Zaki 99];
distribuirea calculului suportului minim - paralelizari de tip ,,count distribution :n acest caz, baza de date este partitionata n subseturi disjuncte ntre proce-
soare. Fiecare procesor cunoaste integral arborele hash al itemilor si, respectiv,
al candidatilor. Suportul este incrementat local, pentru fiecare candidat n parte.
Urmeaza apoi o etapa de comunicare, pentru calcularea suportului global. Un astfel
de algoritm este Non Partitioned Apriori, propus n [Shintani 96];
distribuirea datelor - paralelizari de tip ,,data distribution : acest model propune o
generare disjuncta a itemseturilor candidate. Totusi, acest model implica, din nou,
comunicatii excesive, de aceasta data pentru transmiterea candidatilor ntre proce-
soare si calculul suportului global. Un exemplu de algoritm este Simple Partitioned
Apriori [Shintani 96];
paralelizari hibride: modelul algoritmic propus n acest caz este reprezentat de
Hash Partitioned Apriori (HPA) [Shintani 96] si va fi expus pe larg n contin-
uare.
Algoritmul HPA are la baza, dupa cum indica si numele sau, algoritmul Apriori, fiind
una dintre cele mai eficiente paralelizari ale algoritmului mentionat.
Cum am amintit anterior, ideea algoritmului Apriori este aceea de a genera seturi
candidate de itemi de dimensiune k pe baza seturilor frecvente de itemi de dimensiune
k 1. Fiecare set de itemi candidat este apoi testat pentru a se determina dac a este un
set frecvent de itemi sau nu. Acest pas se repeta pana n momentul n care nu mai sunt
gasite seturi frecvente de itemi sau pana cand se ajunge n imposibilitatea generarii de
seturi candidate.
Algoritmul HPA partitioneaza itemseturile canditate si baza de date ntre procesoare,
folosind o functia hash caracteristica algoritmului secvential de baza. Se elimina astfel
broadcastul inutil al datelor tranzactionate si se obtin reduceri semnificative din punct
de vedere al timpului consumat n calculul suportului pentru un set dat [Shintani 96].
Paralelizari ale algoritmului FP-Growth
Una dintre cele mai interesante paralelizari ale algoritmului FP-Growth este propusa
de Zaiane si este prezentata n continuare [Zaiane 01] . Modelul algoritmic poarta numele
de Multiple Local Frequent Pattern Trees (MLFPT) si este constituit din doua faze.
Prima dintre acestea consta n construirea unor arbori FP locali, n timp ce etapa a doua
consta n explorarea acestor arbori si construirea seturilor frecvente de itemi.Pentru construirea arborilor MLP (Multiple Local Pattern), init ial se scaneaza baza
de date pentru a se identifica seturile de itemi frecvent i de dimensiune 1 (sau, cu alte cu-
vinte, itemii frecventi). In acest scop, baza de date tinta este mpartita ntre procesoare
n mod aproximativ egal. Fiecare procesor va calcula suportul partial al itemilor regasiti
n subsetul de tranzactii ce i-a fost repartizat din baza de date init iala. Aceasta etapa se
ncheie cu o operat ie colectiva de reducere pentru a determina suportul global al fiec arui
item n parte. Urmeaza un pas computational de eliminare a itemilor nefrecventi si de
sortare a itemilor frecventi n ordinea descrescatoare a suportului calculat. Similar algo-
ritmului secvential, tranzactiile sunt de asemenea sortate descrescator relativ la suportul
12
-
7/25/2019 Algoritmi de Clasificare
17/65
itemilor inclusi si sunt eliminati din tranzactii itemii nefrecventi. Urmeaza o etapa de
calcul, cu scopul de a construi arborii FP locali. Trebuie facuta observatia ca acesti
arbori locali vor avea radacina un element null. Fiecare procesor va scana din nou setul
de tranzactii ce i-a fost asignat pentru determinarea arborilor FPlocali. Pasii urmati nacest caz sunt similari (la nivel local) cu cei ai algoritmului FP-Growth secvent ial.
Se construieste apoi baza de tipare condit ionale: o lista care contine toti itemii ce
apar naintea itemului studiat si pana la radacina (ntr-o parcurgere bottom-up). Prin
combinarea acestor baze de tipare conditionate se identifica pentru fiecare item n parte
un sir ce contine toti ceilalti itemi cu care itemul curent poate forma seturi frecvente,
precum si suportul pentru fiecare set n parte. Se obtin, astfel, arbori FP-conditionali.
Pe baza acestora din urma se determina tiparele frecvente. Aceasta ultima etapa este
una intensiv comunicationala. Pentru fiecare itemset n parte sunt necesare operatii
de comunictie colective pentru determinarea suportului global pe baza arborilor FP-
conditionali.
2.1.3 Discutii asupra tehnicilor existente de extragere a regulilor de asociere
In subcapitolele anterioare au fost prezentati doi dintre cei mai important i algoritmi
utilizati n determinarea regulilor de asociere (Apriori siFP-Growth) si doua dintre cele
mai cunoscute metode de paralelizare pentru algoritmii n discutie. Cu toate ca ambii
algoritmi sunt eficienti, exista un set de dezavantaje ce ar putea fi eliminate.
Astfel, cu toate ca obtine timpi de raspuns performanti prin reducerea semnificativa
a scanarilor bazei de date tinta (doar doua scanari ale bazei de tranzactii), algorit-
mul FP-Growth implica existenta unor sturcturi de date complexe. Acest fapt atrage
dupa sine o complexitate mult crescuta pentru modelele paralele. Implementarile mod-
elului MLFPTrealizate pentru sisteme de calcul paralel bazate pe principiul memoriei
partajate se pot dovedi ineficiente datorita sincronizarilor implicate de construirea arbo-rilor FP-conditionali. Pe de alta parte, daca sistemul de calcul paralel este unul bazat pe
memorie distribuita si comunicare de mesa je, atunci detereminarea tiparelor frecvente pe
baza arborilor FP-locali implica un necesar crescut de comunicatii ce pot cauza scaderea
performantelor.
Legat de primul algoritm,Apriori, se pot observa rapid doua dezavantaje majore ale
algoritmului. In primul rand, algoritmul interogheaza la fiecare iteratie baza de date tinta,
inclusiv n faza de generare a k-itemseturilor candidat [Agrawal 94]. In al doilea rand,
functia cheie a algoritmului introduce timpi de calcul suplimentari. Dupa determinarea
celor doua seturilor de dimensiune k 1 ce vor genera k-itemsetul candidat, trebuie
verificat daca toate (k 1)-itemseturile incluse n noul candidat sunt (k 1)-itemseturi
frecvente. Ordinul de complexitate al functiei de generare este O(rk12 rk k).In cazul general, algoritmii existenti utilizati n extragerea regulilor de asociere pot
fi optimizati doar din punctul de vedere al raspunsului timp. Considerand o astfel de
abordare, Agrawal propune (propunere reluata apoi n [Adamo 00]) un al doilea algoritm,
AprioriTid [Agrawal 94]. Fata de varianta de baza, algoritmul AprioriTidmemoreaza,
pentru fiecarek-itemset frecvent, si un set de identificatori ai tranzactiilor pe baza carora
a fost calculat suportul itemului n discutie. Totusi, nici aceasta abordare nu obtine un
plus de performante considerabil.
Un alt aspect negativ legat de algoritmii utilizati n determinarea regulilor de asociere
este ca, n afara de algoritmul Apriori nu au fost exploatate alte mecanisme de gene-
13
-
7/25/2019 Algoritmi de Clasificare
18/65
rare a candidatilor ce ar putea reduce considerabil mult imea de seturi parcurse. O alta
observatie importanta este ca, desi autorii din [Tan 05] introduc n mod demonstrativ
codificarea binara a itemseturilor, nu se regasesc publicate nici un set de rezultate care
sa ofere detalii legate de performantele acestei codificari.
2.2 Reguli de clasificare
Formal, extragerea regulilor de clasificare poate fi rezumata la urmatoarea definitie
[Freitas 00,Tan 05]:
Definitia 2.1(Regula de clasificare). Extragerea regulilor de clasificare dintr-un set
de date reprezinta generarea, pe baza cunostintelor acumulate, a unui set de constrangeri
pentru a sorta datele ulterioare.
2.2.1 Algoritmi secventiali utilizati n determinarea
regulilor de clasificare
Asa cum am amintit n capitolul introductiv, prin extragerea unui set de reguli de clasi-
ficare dintr-un set de date tinta se ncearca identificarea unei functii capabile sa mapeze
corect un set de atribute de intrare pe un set de etichete predefinite, numite clase. In
cazul general, aceasta operatie este compusa din doua etape distincte [Tan 05]:
prima dintre acestea implica nvatarea regulilor de clasificare pe baza unui model
predefinit, construit, n mod uzual, pe baza experientei beneficiarilor finali [Two 05];
a doua etapa implica aplicarea acestui model de clasificare pe un set de date de test,
pentru a se masura acuratetea modelului. In cazul n care modelul de clasificare
obtinut este unul satisfacator, atunci se poate trece la aplicarea sa pe bazele dedate de interes. Daca, dimpotriva, acuratetea modelului lasa de dorit, atunci se
ncearca crearea unui nou set de test, pentru renvatarea regulilor de clasificare,
eventual prin adaugarea de noi constrangeri.
O alta grupare posibila este legata de specificarea exacta sau nu a claselor rezultat.
Din acest punct de vedere se pot distinge doua clase de algoritmi: algoritmi statici -
clasele si constrangerile pentru fiecare clasa n parte sunt specificate de la inceput -
si, respectiv, algoritmi dinamici - se ncearca determinarea automata a claselor si a
numarului acestora.
2.3 Segmentarea datelorDefinitia 2.2 (Clusterizarea datelor). Clusterizarea datelor(sau segmentarea da-
telor) nseamn a, n sens larg, regasirea unei structuri ntr-o colectie de date nemarcate/
nestructurate.
Conceptual, procesul de clusterizare/partitionare a datelor poate fi privit ca fiind
organizarea unui set de obiecte (date) n grupuri ale caror membri sunt similari dupa un
anumit set de restrictii impuse.
In prezent, un numar din ce n ce mai mare de aplicatii utilizeaza metode de clusteri-
zare pentru a obtine rezultate superioare. Exemplele cele mai uzuale includ clusterizarea
14
-
7/25/2019 Algoritmi de Clasificare
19/65
documentelor [Li 05] si sistemele de regasire a informatiilor [Grossman 04]. Un studiu
recent a indicat o crestere a acuratetii de clasificare a algoritmuluik-nn(k-nearest neigh-
bor) n cazul n care setul de antrenament corespunzator a fost generat pe baza unei
clusterizari a documentelor incluse de acest set de antrenament [Astratiei 10]. O prob-lema comuna care apare n cazul acestor aplicatii este legata de volumul mare de date
care trebuie procesate. Algoritmii de clusterizare sunt n general de tipul lazy learner si
trebuie utilizate metode eficiente de paralelizare pentru a obt ine timpi de raspuns si o
scalabilitate rezonabile.
2.3.1 Notiuni teoretice fundamentale
Conform definitiei de mai sus (Definitia 2.2, adaptare dupa [Han 06]), clusterizarea
reprezinta o tehnica descriptiva de data mining care urmareste divizarea unui set de
obiecte date n grupuri distincte. Procesul de mpartire a setului dat de date este real-
izat pe baza similaritatii intrinseci a itemilor, tinand cont de atributele interesante.
Definitia 2.3 (Similaritate). In mod uzual, similaritatea este definita ca fiind o met-
rica/distant a peste un set de atribute.
Rezultatele clusterizarii ar trebui sa ofere o reprezentare mai buna a setului de date
de intrare, tinand cont de metrica de similaritate (obiectele apartinand aceluiasi grup au
aceleasi caracteristici, n timp ce doua obiecte apartinand de grupuri diferite ar trebui
sa fie semnificativ diferite). Metodele de clusterizare sunt considerate n general ca fiind
o forma de nvatare nesupervizata [Han 06, Berkhin 02]. Din acest punct de vedere,
[Berkhin 02] subliniaza ca rezultatele reprezinta un model ascuns care furnizeaza o noua
reprezentare a datelor existente.
2.3.2 Algoritmi secventiali utilizati n segmentarea datelor
Unul dintre cei mai des utilizati algoritmi de segmentare, algoritmul K-Means Cluster-
ing (KMC), a fost introdus de catre MacQueen n anul 1967 [MacQueen 67]. In prezent,
KMC este unul dintre cele mai vechi, si conform [Joshi 03], si unul dintre cei mai populari,
algoritmi de clusterizare. Motivul acestei popularitati este dat de simplitatea n imple-
mentare, de scalabilitate si de viteza de convergenta. De asemenea, daca se utilizeaza o
metrica adecvata, algoritmul poate fi adaptat pentru o varietate mare de tipuri de date.
Algoritmul KMC reprezinta o metoda de partitionare care are ca scop divizarea setului
de date de intrare de dimunsiune n n k partitii. Obiectele apartinand unei partitii tre-
buie sa fie asemanatoare ntre ele, n timp ce obiectele care apartin unor partitii diferite
trebuie sa difere. M. Joshi n [Joshi 03], citand [Dhillon 00], prezinta urmatoarele etapegenerice pentru algoritmul KMC:
1. initializarea - se selecteaza un set de k itemi din setul de date de intrare pentru a
fi centroizii initiali;
2. calcularea distantelor - pentru fiecare item din setul de date, se calculeaz a distanta
pana la centroizii selectati; itemul este distribuit celui mai apropiat centroid;
3. recalcularea centroizilor - pentru fiecare cluster, se recalculeaza centroidul ca fiind
media itemilor atribuiti;
15
-
7/25/2019 Algoritmi de Clasificare
20/65
4. conditia de convergenta - se repeta etapa 2 si 3 pana la atingerea convergentei.
Din punct de vedere logic, conditia de convergenta pentru etapa 4 poate fi una dintre
urmatoarele variante: atunci cand nu se mai redistribuie nici un item ntre doua clustere
sau atunci cand coordonatele centroizilor nu s-au modificat n etapa 3. Din punct de
vedere matematic, convergenta este reprezentata de eroarea patratica calculata conform
relatiei (2.2). In acest caz etapa 4 poate fi definita ca fiind valoarea minima pentru relatia
(2.2) [Han 06] (n capitolul 8):
E=
k
xiC(k)
xi mk2. (2.2)
Este important de mentionat ca algoritmul KMC este o abordare de tip greedy pentru
metodele de partitionare (datorita modului de alegere a centroizilor ntre etape). Pentru
diferite variante de alegere a centroizilor initiali, eroarea patratica minima calculata
conform (2.2) poate varia. Daca luam n considerarek- numarul de clustere,n- numarul
de itemi care trebuie clusterizati si t - numarul de iteratii necesare pentru a atingeconvergenta, algoritmul KMC are o complexitate de timp de ordinul O(nkt) [Han 06]
(capitolul 8). In mod normal, ntre n, k si t exista urmatoarea relatie (a se vedea
[Han 06] capitolul 8 pentru mai multe detalii):
k n
t n.(2.3)
Daca luam n considerare relatia (2.3), se poate observa usor ca numarul total de
itemi neste factorul cu cea mai mare influenta asupra timpului de raspuns pentru orice
implementare KMC.
2.3.3 Metode de paralelizare ale algoritmilor secventiali
Au fost realizate diferite ncercari de a optimiza paralelizarea algoritmului KMC. Unul
dintre cele mai cunoscute si utilizate modele este Parallel K-Means (prescurtat PKM)
[Dhillon 00,Joshi 03,Stoffle 99]. Cel mai mare consumator de timp este pasul de calcu-
lare a distantelor. Aceasta etapa n sine presupuneO(nk) pasi pentru a calcula distantele
ntre fiecare item din setul de date (compus din n itemi) si fiecare dintre cei k cen-
trozii. Modelul paralel pentruPKM mparte ntregul set de date de intrare ntre procese
[Dhillon 00,Joshi 03,Stoffle 99]. Considerandp procese, fiecare va primi (n/p) elemente
din setul de intrare. Divizarea itemilor va reduce fazele locale de calculare a distantelor
la complexitatea de timp data de relatia:
O(n k
p ). (2.4)
2.3.4 Discutii asupra tehnicilor existente de segmentare
a datelor
Modelul PKM se bazeaza pe o paradigma de tipul SIMD (Single Instruction Multiple
Data). O prima observatie importanta este faptul ca acest model nu este aplicabil doar
unei metode specifice de implementare. In functie de diferitele cerinte, algoritmul PKM
16
-
7/25/2019 Algoritmi de Clasificare
21/65
poate fi implementat utilizand fie paralelism la nivel de thread-uri/memorie partajata
sau paralelism la nivel de proces/ memorie distribuita. Totusi, diversi autori sustin faptul
ca ultima metoda ar trebui aleasa, n special atunci cand avem de-a face cu volume mari
de date [Dhillon 00,Joshi 03,Stoffle 99] (acesta ar fi si cazul aplicarii metodelor bazatepe KMC n domeniul clusterizarii documentelor text [Han 06]).
Daca avem n vedere implementarea efectiva a PKM utilizand o schema de distributie
a memoriei, standardul Message Passing Interface (MPI pe scurt) este considerat cea mai
buna abordare [Joshi 03]. Aceasta alegere este bazata pe o serie de argumente, cum ar
fi [Joshi 03]:
MPI este un standard pentru calculul paralel bazat pe momorie distribuia si trans-
mitere de mesaje (n prezent, urmeaza sa fie lansata versiunea 3 a specificatiilor);
este portabil (cu conditia ca aplicatiile sa fie recompilate ntre diferitele platforme
de operare), este heterogen si ofera un suport adecvat pentru diferite topologii de
comunicare;
paralelismul este explicit, programatorului fiindu-i oferita libertate n implementare;
o mare varietate de implementari sunt disponibile (exemplele cele mai rapide sunt
MPICH-G2, IntelMPI, LAM/MPI, OpenMPI) pentru toate limbajele de progra-
mare (cum ar fi C/C++ sau FORTRAN).
O deficienta importanta legata de acesata abordare este reprezentata de faptul ca nu
se pune accent pe topologiile de comunicatie ce pot fi manipulate prin intermediul MPI.
Capitolul4 reia n detaliu aceasta problema.
2.4 Concluzii
In cadrul acestui capitol au fost evidentiati algoritmii clasici destinati problemei des-
coperirii reguilor de asociere, a regulilor de clasificare, precum si cei destinati seg-
mentarii/clusterizarii datelor. Se observa n acest fel faptul ca, desi ultimii algoritmi
clasici pentru extragerea de cunostinte din baze de date sunt de data relativ recenta
- 2001 sau 2003, exista putine cercetari legate de mbunatatirea timpului de raspuns.
Se mai poate observa totodata si faptul ca pentru algoritmii adusi n discut ie nu sunt
epuizate toate posibilitatile de mbunatatire a performantelor. Parte dintre aceste posi-
bilitati vor fi investigate n continuare.
17
-
7/25/2019 Algoritmi de Clasificare
22/65
Capitolul 3
Noi algoritmi si modele de paralelizare
pentru determinarea tiparelor frecvente
3.1 Algoritmul Apriori
In cadrul subcapitolului 2.1 au fost evidentiate un set de dezavantaje ale algoritmu-
lui Apriori. Astfel, algoritmul propus de Agrawal este puternic dependent de metoda
de generare a candidatilor [Agrawal 94]. Aceasta metoda implica un consum de timp
substantial pentru o generare eficienta de candidati. Mai mult, generarea candidatilor
implica un consum suplimentar substantial de memorie.
Cu toate ca HPA reprezinta un model de paralelizare eficient pentru algoritmul
Apriori (implementarile eficiente partitioneaza atat determinarea candidatilor, cat si
tranzactiile bazei de date tinta), exista un set de dezavantaje ale modelului:
partitionarea candidatilor este realizata n baza unei chei de dispersie caracteristica
algoritmului secvential de baza. Aceasta cheie nu este, de cele mai multe ori,
determinata astfel ncat sa realizeze o buna echilibrare a ncarcarii nodurilor de
lucru.
considerand ca functia de calcul a cheii de dispersie se aplic a la nivel de set de
itemi, acest lucru poate conduce la o crestere substantiala a comunicatiilor pentru
determinarea completa a tuturor seturilor candidate.
pentru a rezolva orice dezechilibru ce poate aparea n timpul rularii sau pentru a
determina conditia de oprire, modelul implica existenta unui nod coordonator.
3.1.1 Algoritmul secvential de baza
Considerand observatiile anterioare, o prima modificare propusa pentru algoritmul Apri-
ori vizeaza modul de reprezentare al itemilor/itemseturilor de lucru.
Reprezentarea itemilor
O prima modificare efectuata vizeaza modul de reprezentare al itemilor. Un prim aspect
important este legat de consumul de memorie. Implementarile uzuale ale algoritmului
18
-
7/25/2019 Algoritmi de Clasificare
23/65
Apriori codeaza itemii fie printr-un caracter alfa-numeric (se poate face, n acest caz,
distinctie ntre litere mari si litere mici pentru a mari capacitatea de reprezentare a
metodei), fie printr-un index numeric atribuit itemului (n general, o valoare ntreaga
cuprinsa ntre 0 si nr max 1, undenr max reprezinta numarul total de itemi).Autorul a introdus n [Archip 07] o metoda de codare binara a itemilor si, respectiv, a
itemset-urilor, similara cu [Tan 05]. Itemii sunt codificti prin intermediul valorilor binare
de 0/1. Considerand o numerotare a itemilor n intervalul [0, n 1], un item de index x
este reprezentat de bitul de pe pozitia 2x ntr-un sir de nbiti. Reprezentarea tranzactiilor
si, respectiv, a itemset-urilor este redata n Tabelul3.1. Au fost considerati un set de 5
itemi (A,B , C, D ,E - itemul A este reprezentat binar prin bitul de pozitie 0, itemul E
prin bitul corespunzator pozitiei 4).
Tabelul 3.1: Reprezentarea binara a tranzactiilor/itemseturilor
Itemset/Tranzactie Reprezentare binara{A, B, C} 00111{A, C, E} 10101{B, D} 01010{C, D, E} 11100{A, B, C, D, E} 11111
In Tabelul 3.1 se poate observa si un aparent dezavantaj al acestei reprezentari:
seturile de itemi/tranzactii au dimensiune fixa, indiferent de numarul de itemi inclusi.
Se poate usor observa ca, n cazul reprezentarii itemilor prin index numeric (din
punctul de vedere al tipului de data utilizat, ar fi necesari cel putin 2 octeti pentru
reprezentarea unui singur item) consumul de memorie ar fi mult mai mare. Din acestmotiv nu se mai fac comparatii ntre reprezentarea prin index numeric si reprezentarea
binara propusa n [Archip 07].
O observatie importanta asupra algoritmului Apriori - observatie care si mentine
valabilitatea si pentru algoritmii derivati din Apriori - este aceea ca trateaza tranzactiile
la nivel de multime de itemi. Practic, pentru acesti algoritmi, determinarea suportului
se reduce la problema incluziunii unei submultimi ntr-o multime data. Din acest punct
de vedere reprezentarea binara ofera din nou un avantaj foarte important: se poate
determina, n timp constant daca setul curent de itemi este sau nu inclus n tranzactia
curenta.
Generarea candidatilor
Modelul clasic pentru generarea candidatilor a fost propus n [Agrawal 94] si are la baza
urmatorul principiu: seturile candidate de itemi de dimensiunek se pot obtine numai
prin combinarea seturilor frecvente de itemi de dimensiune k 1 ce au primii k 2 itemi
comuni [Adamo 00].
Dupa cum a fost amintit si n partea introductiva, functia are la baza principiul
Apriori, conform caruia daca un set de itemi este frecvent, atunci toate subseturile de
itemi ce apartin de acest set sunt seturi frecvente [Tan 05]. Literatura de specialitate
considera aceasta functie ca realizand o eliminare optima a seturilor ce nu pot fi frecvente,
seturi pentru care nu se va mai determina suportul n cadrul tranzactiilor, ntrucat aceste
19
-
7/25/2019 Algoritmi de Clasificare
24/65
seturi contin cel putin un subset nefrecvent [Zaki 99, Adamo 00,Tan 05]. Functia este
totusi una consumatoare de timp si este considerata un dezavantaj major al algoritmului
Apriori.
Unul dintre avantajele utilizarii reprezentarii binare a seturilor de itemi si, respectiv,a tranzactiilor este cel al vitezei cu care sunt realizate operatiile logice peste multimi de
biti. Aceste operatii binare elementare pot fi mapa rapid orice operatie ar fi necesara n
lucrul cu multimi de itemi.
Remarcabil n acest sens este si faptul ca aceste operatii binare elementare nu depind
direct, din punctul de vedere al vitezei de executie, de dimensiunead a multimilor asupra
carora sunt aplicate, daca d este mai mica decat o anumita valoare maxima specifica
fiecarui procesor n parte.
Pornind de la aceste considerente, se poate demonstra usor ca determinarea oricaror
itemi necomuni ntre oricare 2 seturi de itemi se realizeaza n timp constant. Particu-
larizand, se poate arata ca utilizand o reprezentare binara a seturilor de itemi se poate
identifica setul de dimensiune 2 format din itemii necomuni printr-o singura operatie.Metoda particulara de generare a candidatilor implementata este bazata pe obser-
vatiile anterioare. Nu se ncearca, precum n cazul clasic [Tan 05], generarea tuturor
subseturilor de dimensiune k 1 ale candidatului curent (de dimensiune k), ci se deter-
mina direct setul format din cei 2 itemi necomuni pentru perechea curent a. Daca acest
set este frecvent, atunci candidatul obtinut va fi adaugat la lista de candidat i valizi, iar
daca acest set este nefrecvent, atunci candidatul va fi ignorat. Algoritmul3.1 prezinta
pseudocodul dezvoltat pentru a implementa aceasta metoda de generare a candidatilor.
Algoritmul 3.1Generarea candidatilor pentru codificarea binara a itemseturilor
Require: Lk11: for all (set1,set2) in Lk1 Lk1 such thatset1.parent == set2.parent do2: test set.code= set1.code set2.code;3: if isFrequent(test set)then4: candidate.code= set1.code | set2.code5: candidate.parent= min(set1,set2)6: add candidate to candidateList7: end if8: end for
In Algoritmul3.1 au fost utilizate urmatoarele notatii:
set1,set2 - variabile generice pentru reprezentarea binara a unui set de itemi;
set1.parent,set2.parent- notatii folosite pentru a desemna primiik 2 biti comuni
pentru cele 2 seturi frecvente ce pot genera un candidat;
set1.code, set2.code - codul binar al celor 2 seturi.
Dupa cum se poate usor observa din pseudocodul anterior, singurul test facut asupra
unui candidat este legat de itemii necomuni si anume setul de dimensiune 2 format de
acestia. Desi acest lucru nu conduce la o eliminare optima a candidatilor ce contin
subseturi nefrecvente, functia compenseaza prin scaderea timpilor de raspuns.
20
-
7/25/2019 Algoritmi de Clasificare
25/65
3.1.2 Modificari aduse algoritmului HPA
Modificarile aduse algoritmului secvential Apriori pot fi utilizate si pentru a solutiona
parte dintre dezavantajele modelului de paralelizare HPA. O prima observatie impor-
tanta este aceea ca modalitatea de reprezentare a itemseturilor si a tranzactiilor prinintermediul unei codificari binare elimina dependeta algoritmului de un eventual arbore
de dispersie. Acest fapt reprezinta o slabire importanta a conditiilor de generare a cheilor
de dispersie pentru ca aceste chei nu vor mai avea rol de identificator unic al unei anumite
combinatii de itemi.
Un alt punct nevralgic pentru HPA este reprezentat de partitionarea candidatilor
determinati pentru determinarea suportului. In mod uzual, aceasta etapa este una in-
tensiv comunicationala. Mai mult, este posibil ca un set generator s a fie repartizat unui
nod de procesare, n timp ce perechea sa este repartizata altui nod de calcul. Aceasta
situatie implica din nou comunicatii.
Particularitat i ale functiei de dispersie
Considerand observatiile anterioare, functia de dispersie utilizata a fost una de tipmodulo-
bitonic. Cheilehashsunt n acest caz valori n clasa de resturimodulon, unden reprezinta
numarul total de procesoare implicate n analiza. Seturile de itemi sunt mpartite n or-
dine ntre procesoare astfel ncat pentru fiecare item/set de itemi n parte cheia hash
variaza dupa o alternanta bitona [Archip 07]. In Tabelul3.2 este prezentat un exemplu
pentru un numar de 10 itemi cu etichete de la 0 la 9 si un total de 3 noduri de procesoare.
Tabelul 3.2: Distribuirea itemilor intiali ntre procesoare
Eticheta item 0 1 2 3 4 5 6 7 8 9Cheie Hash 0 1 2 2 1 0 0 1 2 2
Un aspect important al acestei functii hash, legat de implementarea practica n mod
special, este acela ca timpulnecesar calculului cheii hash curente trebuie sa fie n clasa
de complexitate O(1). Algoritmul3.2 reprezinta pseudocodul utilizat n implementarile
de test [Archip 07].
Dupa cum se poate usor observa, indiferent ce valoare trebuie generata pentru cheia
curenta, functia propusa realizeaza cel mult 4 pasi: 2 teste si, respectiv, fie o operat ie de
atribuire urmata de o operatie de incrementare/decrementare, fie 2 operatii de atribuire.
Mai mult, functia nu este conditionata sub nici o forma de numarul total de itemi, iarvitezade generare a valorilor rezultat nu este influentata de numarul total de procesoare.
In plus, se poate demonstra usor, prin reducere la absurd, faptul ca indiferent de numarul
de procesoare si de numarul de itemi sau de seturi de itemi ale pasului curent se reali-
zeaza o foarte buna echilibrare a distributiei itemilor/seturilor de itemi ntre nodurile de
procesare.
Fiek numarul total de itemi/seturi de itemi ai pasului curent si n numarul total de
procesoare (se considera k > n). Din Tabelul 3.2 si Algoritmul 3.2 se observa foarte
rapid ca toate celen procesoarear primi un numar de[k/n] itemi/seturi de itemi si doar
[k%n] procesoarear primi un singur item/set de itemi n plus fata de restul nodurilor.
21
-
7/25/2019 Algoritmi de Clasificare
26/65
Algoritmul 3.2Functia Hash utilizata n cadrul algoritmului HPA
1: static d = 02: if d= 0 then3: iflast key < size 1 then4: new key= last key+ +5: else6: new key= last key7: d= 18: end if9: else
10: if 0< last key then11: new key= last key 12: else13: new key= last key14: d= 015: end if
16: end if
Partitionarea itemset-urilor
Un alt punct slab al HPA este reprezentat de determinarea si de distribuirea candidatilor
ntre procese n vederea calcularii suportului pentru fiecare candidat n parte. Aceste
doua etape sunt intensiv comunicationale si pot introduce timpi suplimentari considera-
bili.
O prima modificare adusa algoritmului HPA este de a aplica functia de calcul a cheii
de dispersie la nivelul setului parinteal candidatului curent.
Definitia 3.1 (Itemset parinte). Prin conventie, se numeste itemset parinte al unuicandidat de dimensiune k acel itemset care contine primii k-1 itemi din candidatul curent.
Algoritmul3.3prezinta modalitatea de generare a candidatilor conform cu modificarile
propuse.
Algoritmul 3.3Generarea candidatilor - adaptare HPA
Require: Lidk1 - multimea seturilor frecvente repartizate nodului id
1: foriter= 0 to iter < length(Lidk1) 1 do2: hashKey:= nextKey(set[iter])3: for allpairSet in Lid
k1 such thatset[iter].parent== pairSet.parent do
4: candidate.code:= set[iter].code pairSet.code5: if true== isFrequent(candidate) then6: candidate.code:= set[iter].code |pairSet.code7: candidate.parent:= set[iter]8: candidate.hashKey:= hashKey9: end if
10: end for11: end for
In Algoritmul3.3, functianextKeynoteaza o implementare a Algoritmului 3.2.
22
-
7/25/2019 Algoritmi de Clasificare
27/65
3.1.3 Rezultate si discutii
Testarea algoritmului secvential modificat
Pentru evaluarea modificarilor aduse din punctul de vedere al timpului de raspuns, aufost realizate un set de 15 teste. Pentru toate cele 15 teste a fost considerata o baza
de date formata din tranzactii generate aleator, cu suport pentru maxim 32 de itemi.
Pentru evaluarea performantelor, au fost considerate seturi de 10, 15 si, respectiv 20 de
itemi, iar limita suportului minim a fost variata ntre 1%, 5%, 10%, 20% si, respectiv,
35%. In toate cazurile, baza de date contine un numar de 1.000.000 tranzactii. Evaluarile
au urmarit n principal comportamentul functiei de generare a candidatilor, dar si timpii
totali consumati de analiza.
Rezultatele timp obtinute pentru cazul n care au fost considerati 10 itemi, iar limita
suportului a fost variata ntre 1 si, respectiv, 35% evdentiaza obtinuta o scadere pentru
functia de generare a candidatilor. Daca ntr-un un caz clasic, literatura de specialitate
[Adamo 00,Tan 05] considera metodele de generare a candidatilor ca fiind comparabile
ca rapuns timp cu metodele de selectie ale seturilor frecvente, pentru abordarea pro-
pusa timpii consumati de generarea candidatilor sunt mult inferiori timpilor implicati n
determinarea seturilor frecvente.
Totusi, acest castig este unul minor pentru cazul secvential. Abordarea propusa
nu se preteaza cazului secvential deoarece renuntarea la structurile de tip ,,hash-tree
caracteristice abordarilor bazate pe Apriori [Agrawal 94, Adamo 00, Tan 05] conduce
catre timpi de raspuns globali din ce n ce mai mari. Rezultatele timp pentru aceeasi
baza de date (de 1.000.000 de tranzactii) pentru cazul n care au fost considerati 15 itemi
de start. Suportul a fost variat si n acest caz ntr-o maniera identica testului anterior.
Se observa, ca si n cazul anterior, un timp foarte mic pentru generarea candidatilor.
Comparand totusi timpii totali implicati se observa ca pentru o cresterea cu doar 5 itemi
a bazei de analizat, timpi cresc cu pana la un ordin de marime. Acest comportament
se datoreaza faptului ca o codificare binara a itemilor/seturilor de itemi atrage dupa
sine o complexitate de O(n ck) pentru determinarea suportului seturilor candidate (n
reprezinta numarul total de tranzactii, ck reprezinta numarul total de candidati de di-
mensiunek). In foarte multe cazuri, factorul ck este comparabil din punct de vedere al
valorii cu factorul n. Literatura de specialitate sustine pentru aceasta etapa a algorit-
mului o complexitate timp pseudo-liniara n raport cu dimensiunea bazei de date tinta
[Agrawal 94,Adamo 00,Tan 05].
Rezultatele prezentate nu recomanda, n mod clar, aceasta abordare pentru modelul
secvential al algoritmului Apriori.
Testarea algoritmului HPA modificat
In vederea testarii modificarilor aduse algoritmului HPA, experimentele au fost conduse
n aceeasi maniera ca si n cazul clasic. Astfel a fost utilizata aceeasi baza de date de
1.000.000 de tranzactii, oferind suport pentru 10, 15 sau 20 itemi. Limita de suport
minim a fost variata ntre 1%, 5%, 10%, 20% si, respectiv, 35%.
Implementarea de test include un set de particularitati importante. Codul algorit-
mului HPA a fost dezvoltat utilizand limbajul C++, suportul pentru paralelizare fiind
oferit de bibliotecile LAM/MPI. Pentru a elimina completcomunicatiile, baza de date
tinta a fost utlizata pentru a stoca si seturile frecvente determinate n cadrul unei etape
23
-
7/25/2019 Algoritmi de Clasificare
28/65
k. Astfel, pentru etapa urmatoare, fiecare procesor de rang id selecteaza din baza de
itemseturi frecvente doa acele itemseturi a caror cheie de dispersie este egala cu valoarea
id. Acest lucru este posibil datorita faptului ca, n urma modificarilor aduse, cheia de
dispersie identifica strict perechile ce pot forma candidati. Serverul suport pentru bazelede date a fost MySQL, versiunea 4. Atat tabelele de tranzactii cat si tabele rezultat au
folosit suport InnoDB [Amarandei 06]. Este important de retinut ca un astfel de scenariu
poate fi aplicat n cadrul sistemelor Grid, n cazul n care restrictiile impuse n cadrul
unei organizatii virtuale nu permit migrarea datelor de analizat.
Din analiza rezultatelor obtinute se poate observa ca timpii de lucru pentru fiecare
procesor n parte sunt timpi foarte apropiati ca valori. Aceste rezultate sustin conside-
ratiile teoretice asupra functiei hash proiectate si implementate si, n plus, sust in modul
de aplicare al acesteia.
Se poate observa ca, spre deosebire de cazul secvential, unde renuntarea la arborele
hash atragea dupa sine pierderi semnificative n ceea ce consta performanta timp, versi-
unea paralela a algoritmului mentine stabilitatea timpilor de raspuns. Mai mult, pentru
fiecare procesor n parte, faptul ca timpul de raspuns este foarte apropiat de timpul
mediu de executie. Acest lucru subliniaza o foarte buna echilibrare a sarcinilor de lucru.
Aceasta echilibrare a fost obtinuta prin utilizarea functiei de dispersie prezentata n Al-
goritmul3.2 si prin aplicarea acestei chei la nivel de itemset parinte (conform Definitiei
3.1).
3.2 Algoritmul Fast Itemset Miner
In cadrul subcapitolului 3.1 a fost analizata o abordare noua pentru codarea itemilor
si, respectiv, a itemseturilor pentru algoritmul Apriori. Cu toate ca abordarile re-
cente n domeniul identificarii tiparelor frecvente evita generarea seturilor candidate
[Tan 05, Han 00], este interesant de observat faptul ca n literatura de specialitate nu
sunt prezentate alte propuneri pentru aceste abordari. In continuare, este descris un
model algoritmic nou destinat problemei n discutie. Acest model algoritmic este bazat
tot pe generarea seturilor candidate, dar utilizeaza o euristica noua de generarea acestor
candidati.
Dupa cum este mentionat si n capitolele anterioare, principiul de baza al algoritmului
Apriori este de a genera seturi candidate de dimensiune k pe baza seturilor frecvente de
dimensiunek 1 [Adamo 00,Zaki 99,Agrawal 94]. Practic, acest lucru implica, la fiecare
etapa, cresterea cu o unitatea dimensiunii seturilor supuse analizei. In cazul algoritmului
Apriori o unitate este echivalenta cu un item. Algoritmul nou, denumit Fast Itemset
Miner (prescurtat FIM), are la baza cresterea cu o unitate a dimensiunii intervalului
de care apartin seturile candidate aferente unei etape [Craus 07c]. Spre deosebire dealgoritmul Apriori, n cazul FIM o unitate este echivalenta fie cu un item, fie cu un
index de interval (multime de itemi/itemseturi frecvente) [Craus 08a].
3.2.1 Algoritmul secvential de baza
Ideea fundamentala a algoritmului FIM este de a determina, pas cu pas, itemseturile
frecvente prin a creste treptat intervalul de care apartin itemii individuali ce compun un
itemset candidat [Craus 07c]. Astfel, daca n pasul k al agoritmului candidatii noi sunt
generati din itemi ce apartin intervalelor [i, i+k] (undei {1, 2,...,nk},nreprezentand
24
-
7/25/2019 Algoritmi de Clasificare
29/65
numarul total de itemi frecventi), n pasul k +1 candidatii noi vor fi generati din generati
din itemi ce apartin intervalelor [i, i + k+ 1] (unde i {1, 2,...,n k 1}).
In continuare vor fi utilizate notatiile date de setul de relatii (3.1).
Fi,j multimea tuturor itemseturilor frecvente ce apartin de intervalul [i, j]
Ci,j multimea tuturor itemseturilor candidate ce apartin de intervalul[i, j](3.1)
Sunt enuntate urmatoarele doua leme [Craus 07c].
Lema 3.1. Un itemset frecvent inclus n multimeaFi,j care nu contine simultan itemii
i sij va apartine fie de multimeaFi,j1, fie de multimeaFi+1,j .
Lema 3.2. Itemseturile frecvente noi ce apartin de multimeaFi,j contin simultan itemii
i sij.
Din Lema 3.2 rezulta ca itemseturile candidate ce apartin de multimea Ci,j vor figenerate dupa relatia [Craus 07c]:
Ci,j ={X Y|(XFi,j1 i X) (Y Fi+1,j j X)}. (3.2)
Pseudocodul algoritmului FIM este prezentat n Algoritmul3.4 [Craus 07c].
Algoritmul 3.4AlgoritmulFast Itemset Miner
Require: Fi,j = multimea itemseturilor frecvente din intervalul [i, j]Require: D = multimea de tranzactii, t D
1: fork = 1 to n 1 do2: for alli, j : i 1,...,n k; j =i + k do3:
Fi,j Fi,j
1 Fi+1,j4: Ci,j ={X Y|(XFi,j1 i X) (Y Fi+1,j j X)}5: for alltranzactiilet D do6: Ct subset(Ci,j , t) {determinarea candidatilor din intervalul Ci,j inclusi n
tranzactiat}7: for allcandidatiic Ct do8: c.support++9: end for
10: end for11: Fi,j =Fi,j {c Ci,j |c.support minsupp}12: Fk Fk Fi,j13: end for14: end for
Definitia 3.2(Itemset nucleu). In contextul notatiilor (3.1) se numesteitemset nucleu
al unui itemsetXFi,j acel subsetNX, N=X de dimensiune maxima pentru care
este valabila relatia:
N {i}= N {j}= . (3.3)
Lema 3.3. Un itemset nu poate fi frecvent daca itemsetul sau nucleu nu este la randul
lui frecvent.
25
-
7/25/2019 Algoritmi de Clasificare
30/65
Un rezultat direct al Lemei3.3este reprezentat de faptul ca un candidat valid (itemset
candidat ce ar putea satisface condit ia de suport minim) trebuie sa fie generat pentru
analiza numai daca nucleul sau este frecvent. Mai mult, un itemset candidat este valid
daca toate subseturile sale, exceptand itemseturile care contin simultan itemiii sij , suntitemseturi frecvente.
Pentru simplificare, n continuare vor fi utilizate urmatoarele notatii:
sufix(X) =X\ {i}
pref ix(X) =X\ {j}.(3.4)
In relatia (3.4) i,j reprezinta primul si, respectiv, ultimul item al itemsetului XFi,j .
Lema 3.4. Un itemset candidatT Ci,j este valid daca si numai daca se poate obtine
din reuniunea a doua itemseturi X Fi,j1 si Y Fi+1,j care respecta simultan pro-
prietatile:
i X sij Y (3.5)
sufix(X) =prefix(Y). (3.6)
Algoritmul3.5prezinta pseudocodul necesar generarii candidatilor ce apartin multimii
Ci,j .
Algoritmul 3.5Algoritmul de generare a candidatilor specificFIM
Require: Fi,j1, Fi+1,j1: for all itemset XFi,j1 do2: for allitemsetY Fi+1,j do3: if sufix(X) =prefix(Y)then4: candidat X Y5: adauga candidat n Ci,j6: end if7: end for8: end for
Un exemplu detaliat al principiului de functionare al algoritmuluiFIMeste prezentat
n [Craus 07c].
Considerand aceste observatii, Algoritmul 3.4 este modificat conform Algoritmului
3.6. Aceasta restrangere a multimii de tranzactii de scanat reprezinta un avantaj semni-
ficativ fata de algoritmul Apriori. Spre deosebire de algoritmul Apriori, algoritmulFIM
nu va scana complet multimea de tranzactii de analizat pentru nici o etapa de deter-
minare a tiparelor frecvente. In cadrul Algoritmului 3.6, Di reprezinta acel subset de
tranzactiit D ce contin itemul i.
3.2.2 Algoritmul paralel - modelul simplu
Avantajul major al acestei metode de paralelizare este ca tiparul comunicational este
cunoscut nainte de rularea algoritmului [Craus 07c,Craus 08a,Craus 08b]. Un alt avan-
taj important consta n faptul ca seturile de tranzactii pot fi distribuite procesoarelor
26
-
7/25/2019 Algoritmi de Clasificare
31/65
Algoritmul 3.6 Algoritmul Fast Itemset Miner - restrangerea setului de tranzactiiscanateRequire: Fi,j = multimea itemseturilor frecvente din intervalul [i, j]Require: D = multimea de tranzactii sortata descrescator relativ la suportul itemilor
frecventi,t D1: fork = 1 to n 1 do2: for alli, j : i 1,...,n k; j =i + k do3: Fi,j Fi,j1 Fi+1,j4: Ci,j ={X Y|(XFi,j1 i X) (Y Fi+1,j j X)}5: for alltranzactiilet Di do6: Ct subset(Ci,j , t) {determinarea candidatilor din intervalul Ci,j inclusi n
tranzactiat}7: for allcandidatiic Ct do8: c.support++9: end for
10: end for
11: Fi,j =Fi,j {c Ci,j |c.support minsupp}12: Fk Fk Fi,j13: end for14: end for
nainte de nceputul algoritmului. Acest lucru este posibil deoarece un procesor Pi tre-
buie sa calculeze Fi,j , j {i,...,n} si prin urmare sunt necesare doar tranzactiile care
contin itemul frecventi [Craus 08a,Craus 08b].
Algoritmul3.7prezinta pseudocodul aferent modelului de paralelizare descris anterior
[Craus 08a].
Algoritmul 3.7AlgoritmulFIM Paralel- modelul simplu
Require: Fi,i = {itemul frecventi}Require: Di = multimea de tranzactii repartizata procesorului Pi (multimea de
tranzactii ce contine itemul i)1: fork = 1 to n 1 do2: for alli : i 1,...,n k parallel do3: j = i + k4: Fi,j Fi,j1 Fi+1,j5: Ci,j ={X Y|(XFi,j1 i X) (Y Fi+1,j j X)}6: for alltranzactiilet Di do7: Ct subset(Ci,j , t) {determinarea candidatilor din intervalul Ci,j inclusi n
tranzactiat}8: for allcandidatiic Ct do9: c.support++
10: end for11: end for12: Fi,j =Fi,j {c Ci,j |c.support minsupp}13: end for14: end for
Se poate observa usor faptul ca si n cazul Algoritmului3.7poate fi utilizat Algoritmul
3.5pentru a genera candidatii corespunzatori fiecarei etape de calcul.
27
-
7/25/2019 Algoritmi de Clasificare
32/65
3.2.3 Algoritmul paralel - modelul generalizat
In cazul n care numarul de procesoare (m) este mai mic decat numarul de itemi frecventi
(n), algoritmul paralel poate fi modificat si generalizat dupa cum urmeaza:
In prima etapa, fiecare procesorPi, i {1,...,m1} calculeaza secvential itemseturilefrecvente din intervalul Ii = [(i 1)p + 1, ip], undep = [
nm
]. Procesorul Pm calculeaza
itemseturile frecvente din intervalul Im= [(m 1)p + 1, n]. Pentru aceasta etapa poate
fi utilizat Algoritmul3.6.
Pentru cea de-a doua faza, se aplica algoritmul paralel generalizat.
In continuare este utilizat urmatorul set de notatii:
FIi,Ij multimea tuturor itemseturilor frecvente ce apartin de intervalul
Ii,j =Ii Ii+1 ... Ij
CIi,Ij multimea tuturor itemseturilor candidate ce apartin de intervalul Ii,j .
(3.7)
In [Craus 08a] sunt enuntate si demonstrate urmatoarele 2 leme:
Lema 3.5. Un itemset frecvent apartinand deFIi,Ij , care nu contine simultan subseturi
de itemi dinIi siIj, apartine fie deFIi,Ij1 , fie deFIi+1,Ij .
Lema 3.6. Noile itemseturi frecventeFIi,Ij contin simultan subseturi de itemi dinIi si
Ij.
Un rezultat important al Lemei 3.6este faptul ca noii candidati apartinand interva-
lului Ii,j sunt obtinuti conform relatiei:
CIi,Ij ={X Y|(XFIi,Ij1 Ii X= ) (Y FIi+1,Ij Ij Y = )}. (3.8)
Algoritmul3.8 prezinta pseudocodul modelului generalizat prezentat anterior.
Algoritmul 3.8AlgoritmulFIM Paralel - modelul generalizat
Require: FIi,Ii ={multimea de itemseturi frecvente ce apartin intervaluluiIi}Require: Di = multimea de tranzactii repartizata procesorului Pi (multimea de
tranzactii ce contine itemul i)1: fork = 1 to m 1 do2: for allIi : i 1,...,n k parallel do3: Ij =Ii+k4: FIi,Ij FIi,Ij1 FIi+1,Ij
5: CIi,Ij ={X Y|(XFIi,Ij1 Ii X= ) (Y FIi+1
top related