Algoritmi de Clasificare

7/25/2019 Algoritmi de Clasificare

1/65


2/65


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


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


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


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/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


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


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


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


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


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


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


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.


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


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


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


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


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.


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

Date post:	25-Feb-2018
Category:	Documents
Upload:	antonia-ruxandra
View:	241 times
Download:	0 times

Algoritmi de Clasificare

Documents