Tehnologia Data Warehouse

Cuprins

1 Introducere 3

2 Constructia i structura unui data warehouse 5

2.1 Integrarea datelor 5

2.2 Principalele deosebiri dintre OLTP

i O LAP 6

2.3 Modelul multidimensional 8

2.3.1 Schema stea 8

2.3.2 Agregarea n schema multidimensional. 8

2.3.3 Normalizare parial; schema fulg .... 10

2.3.4 Stocarea datelor n vectori multidimensionali . 11

2.4 IndeCi 14

2.4.1 IndeCii n sistemele OLTP . 15

2.4.2 IndeCii n sistemele OLAP . 15

2.5 View-uri 21

2.5.1 Materializarea view-urilor . 21

2.5.2 Problema MVC - Multiple View Consistency . 22

2.6 Structura unui Data Warehouse 23

3 Interogarea unui depozit de date 26

3.1 Probleme legate de cererile tipice OLAP 26

3.1.1 Extinderea SQL . 29

3.2 Calculul cubului de date 31

3.2.1 Cazul relaional 31

3.2.2 Cazul multidimensional . 33

4 Exploatarea unui Data Warehouse - cteva elemente de data mining 38

4.1 Motivaie 38

4.1.1 Statistic inferenial versus data mining 38

4.2 Formalizarea matematic a problemei.

Terminologie ... 39

4.2.1 Indivizi 39

4.2.2 Variabile. 41

4.3 Metode de analiz factorial 42

4.3.1 Analiza n componente principale 42

4.3.2 Metode ierarhi ce

4.4.1 Prezentarea datelor . 4.5 Clasificare automat (cluster analises) 4.5.1 Metode neierarhice5 Concluzii i perspective

5.1 Inteligena artificial i depozitele de date

5.2 Statistica i depozitele de date .

5.3 ncheiere .

Introducere

n lumea anilor 2005, odat cu fenomenul de globalizare i continua cretere economic, nevoia de a asigura un management performant se manifest din ce n ce mai intens. Dinamismul evoluiei economiei, crescut i el n ultima vreme cere din partea companiilor s se adapteze rapid la orice schimbare; n plus, dimensiunile afacerilor au crescut, la fel ca i dimensiunile pieei. Pentru a lua deciziile optime, conducerile companiilor au nevoie de date despre evoluia afacerii n trecut pe baza crora s se poata face prognoze de calitate pe termen scurt, mediu sau lung. Competiia e neierttoare i fiecare pas greit cost. Dictonul folosit de economiti pentru a exprima aceast realitate este foarte sugestiv what you dont know can hurt you (ceea ce nu tii, te poate costa). Rezultatul este o permanent i acut foame de informaii, problem pentru a crei rezolvare e nevoie de prelucrarea unui volum mare de date din surse diferite i adesea neomegene.

Vechile sisteme de gestiune a bazelor de date, proiectate pentru procesarea tranzaciilor curente (OLTP), nu mai pot face fa i acestor noi cerine, pe de o parte pentru c nu rein n baza de date informaii cu caracter istoric, strict necesare n procesul de luare a deciziilor manageriale, dar inutile n derularea operaiunilor curente i pe de alt parte pentru c sunt optimizate pentru prelucrarea unor cantiti relativ mici de informaie, n timp ce procesul de analiz a unei afaceri implic necesitatea unei viziuni globale asupra ntregii activiti, ceea ce nu se poate obine dect prin consultarea unui volum mare de date.

Pentru a rezolva toate aceste probleme se construiete, conform principiului c ntre

structura unei entiti i funciile pe care le ndeplinete exist ntotdeauna o relaie strns, o

noua baz de date, altfel structurat dect clasicele sisteme OLTP. Volumul mare de informaii pe care trebuie s le conin aceast baz de date i-a adus denumirea de depozit de date, in englez data warehouse, de unde i numele acestei tehnologii. Evident, n aceasta baz de date trebuie puse toate informaiile cu caracter istoric relevante n analiza economic.

n domeniile n care relaia cu publicul este foarte important, cum ar fi comerul, data warehouse se dovedete a fi un instrument important pentru fidelizarea clienilor.

Supermarket-urile n special ncearc s in n baza lor de date informaii despre clienii lor cu scopul de a avea o relaie strns cu ei. Clientul este ntmpinat cu un salut familiar i i se cunosc preferinele, ceea ce l face s revin cu plcere n magazinul respectiv. Studiul pieei i al comportamentului clientului este n aceste cazuri foarte important, de el depinznd n mare masur succesul afacerii. Lucrul direct cu foarte muli clieni face ca metodele statistice de exploatare a depozitului de date s aib o importan crescut. n acest caz, dimensiunile bazei de date sunt foarte mari, chiar dac nu este vorba despre o companie mare.

Dar lumea afacerilor nu este singurul loc n care aceast tehnologie i gsete aplicaii. n fond, oriunde e nevoie de un management performant, care trebuie s bazeze pe criterii tiinifice, data warehouse i poate aduce aportul. Astfel, n Statele Unite, fiscul a construit un astfel de depozit de date i astfel le poate oferi foarte rapid contribuabililor informaii despre situaia impozitelor pe care le mai au de pltit. Acesta nu este singurul avantaj pe care l-a adus aceast investiie. Analiznd modul n care cetenii i pltesc taxele, contabilii pot determina mai uor eventualele fraude. Detecia fraudelor e o problem care nu preocup doar pe colectorii de impozite, ci i pe conducerile marilor corporaii. Studiind datele angajailor care au comis ilegaliti n dauna companiei se pot gsi modele de comportament caracteristice celor predispui s fac la fel i astfel pot fi prevenite noi pagube.

n fine, trebuie s precizm i care este eficiena economic a acestei tehnologii. n unele cazuri s-a nregistrat pe termen mediu un profit de circa patru dolari petru fiecare dolar investit ntr-un data warehouse. Sigur, ctigul nu este peste tot la fel de mare, dar pe msur ce acest tehnologie ctig popularitate i fiecare companie i construiete propriul depozit de date, problema nu se mai pune n termeni de ctiguri, ci n termeni de limitarea pierderilor. Data warehouse devine din ce n ce mai mult un instrument necesar, iar cine nu-l are pierde n faa concurenei. Pe termen lung, neutilizarea acestei tehnologii (sau a uneia echivalente) poate duce chiar la dispariia de pe scen a companiilor care adopt o asemenea politic managerial.

Capitolul I

CONCEPTE DE BAZ PRIVIND TEHNOLOGIA DEPOZITELOR DE DATE

1.1 Depozite de date - delimitri conceptuale

Depozitele de date (data warehouse) au fost definite n foarte multe moduri, nct este destul de dificil de formulat o definiie riguroas. n sens larg, un depozit de date reprezint o baz de date care este ntreinut separat de bazele de date operaionale ale organizaiei. Datele din sistemele surs sunt extrase, curite, transformate i stocate n depozite speciale n scopul sprijinirii proceselor decizionale. Depozite,le de date sprij ins procesarea informaiilor furniznd o platform solid de consolidare a datelor istorice pentru analiz. Un depozit de date este o sum de date consistent, din punct de vedere semantic, care servete la o implementare fizic a unui model de date pentru sprijinirea deciziei i stocheaz informaii pe care o organizaie le solicit n luarea deciziilor strategice.

n concordan cu W. H. Inmon, liderul n construirea sistemelor data warehouse, "un depozit de date este o colecie de date orientate pe subiecte, integrate, istorice i nevolatile destinat sprijinirii procesului de luare a deciziilor manageriale" . n sintez, definiia prezentat mai sus exprim caracteristicile majore ale depozitelor de date:

orientare pe subiecte;

integrare;

caracter istoric ;

persistena datelor.

Aceste caracteristici fac distincia ntre data warehouse i alte depozite de date (data repository systems), cum ar fi sistemele de baze de date relaionale i sistemele de prelucrare a tranzaciilor.

Orientarea pe subiecte. Sistemele operaionale tradiionale erau focalizate pe datele cerute de compartimentele funcionale ale ntreprinderii. O dat cu reingineria proceselor (Business Process Reengineering - BPR), ntreprinderile ncep s se axeze pe cerinele decizionale ale echipelor de conducere. Sistemele operaionale moderne sunt orientate pe cerinele ntregului proces tranzacional i sprijin execuia proceselor de la nceput pn la sfrit. Un depozit de date merge dincolo de informaiile tradiionale prin focalizarea pe subiecte ale activitii ntreprinderii cum ar fi: clieni, vnzri, profituri etc. Aceste subiecte necesit informaii din diverse surse pentru a furniza o imagine complet a domeniului. n loc de a se concentra pe procesarea operaiilor i tranzaciilor zilnice dintr-o organizaie, un depozit de date se focalizeaz pe modelarea i analiza datelor pentru luarea deciziilor. Din acest motiv, depozitele de date ofer, n mod tipic, o viziune simpl i concis relativ la un subiect specific, excluznd datele care nu sunt utile n procesul de sprijinire a deciziei.

Integrarea. Un depozit de date este, n mod uzual, construit prin integrarea unor multiple surse heterogene: baze de date relationale, fiiere, nregistrri privind tranzactii on-line. Tehnicile de curtire a datelor (data cleaning) i de integrare sunt aplicate pentru a asigura concordanta n conventiile de atribuire a numelor, de codificare a structurilor, de atribuire a valorilor .a.m.d.

Caracterul istoric. Datele sunt stocate pentru a furniza informatii n perspectiv istoric (de exemplu, 5-10 ani n urm). Astfel, decidentii pot consulta valorile succesive ale acelorai date pentru a determina evolutia n timp i a calcula anumiti indicatori.

Persistena datelor. Datele dintr-un depozit sunt permanente i nu pot fi modificate. O actualizare a depozitului de date, ca urmare a modificrilor efectuate n datele surs, nsemn adugare de date noi fr a modifica sau terge datele existente. Un depozit de date este ntotdeauna memorat separat din punct de vedere fizic de datele transformate din alte aplicatii. Datorit acestei separri, un depozit de date nu necesit mecanisme de procesare a concurentei. n mod uzual solicit numai dou operatiuni n accesarea datelor: ncrcarea initial a datelor i accesul la date.

Alte definitii ale depozitelor de date surprind, cu unele nuantri, aceleai elemente esentiale :

Un depozit de date contine un volum foarte mare de date. Unele dintre aceste date provin din sursele operationale ale organizatiei, altele pot proveni din surse externe ;

Depozitul de date este organizat astfel nct s faciliteze folosirea datelor n scopuri decizionale ;

Depozitul de date furnizeaz instrumente prin intermediul crora utilizatorii finali pot accesa rapid datele.

n continuare prezentm cteva definitii reprezentative din literatura de specialitate.

n viziunea lui Barry Devlin, un depozit de date nseamn "o stocare a datelor, unitar, complet i consistent, obtinut dintr-o varietate de surse, disponibil utilizatorilor finali ntr-un mod uor perceptibil i utilizabil n contextul afacerii".

Dup Ralph Kimball "depozitul de date ofer acces la datele organizationale; datele continute sunt consistente; datele pot fi separate i combinate n functie de fiecare dimensiune sau aspect al afacerii. Depozitul de date include, de asemenea, un set de instrumente pentru interogare, analiz i prezentare a informatiilor; reprezint locul n care sunt publicate datele folosite; calitatea datelor continute n depozit reprezint o premis pentru reingineria afacerii".

Sam Anahory subliniaz finalitate a depozitelor de date preciznd c un depozit de date include "datele ... i procesele manageriale ... care fac informatiile disponibile, permitnd managerilor s ia decizii corect fundamentate" .

De asemenea, o serie de firme i-au adus contributia n definirea, dezvoltarea i popularizarea tehnologiilor data warehouse IBM, Software AG, Oracle, Microsoft, Prism Solutions etc. De exemplu, Software AG definete depozitul de date ca "punctul central pentru difuzarea informatiilor ctre utilizatorii finali pentru sprijinirea deciziilor i pentru acoperirea cerintelor informationale ale conducerii". IBM a propus un termen propriu pentru depozitele de date: lnformation , Warehouse. Dup unii autori, viziunea IBM se refer mai degrab la conecti, vitatea global a diverselor surse de date, fiind un fel de "middleware generalizat" bazat pe arhitectura proprie DRDA - Distributed Relational Database , Architecture.

De altfel, n literatura de specialitate se folosesc i simultan cei doi termeni pentru depozite de date: Data Warehouse i Information Warehouse. Dup Efraim Turban, scopul unui "data (sau information) warehouse este de a realiza un fond de date (data repository) care s fac accesibile datele operationale ntr-o form acceptabil pentru asistarea deciziilor i pentru alte aplicatii".

1.2. Data warehousing

n legtur cu depozitele de date o notiune frecvent utilizat este cea de "data warehousing" care desemneaz procesul de construire i utilizare a depozitelor de date (data warehouse). Construirea unui depozit de date necesit integrarea datelor, curtirea datelor (data cleaning) i consolidarea datelor. Utilizarea unui depozit de date necesit adesea o colecie de tehnologii de asistare a deciziilor. Acestea permit managerilor i specialitilor (de exemplu, analiti, consilieri etc.) s utilizeze depozitul pentru a obine rapid i convenabil datele necesare i s ia deciziile bazate pe informaiile din depozit. Ali autori utilizeaz termenul de "data warehousing" pentru a referi numai procesul de construire a depozitului de date, n timp ce termenul de "warehouse DBMS" este utilizat pentru a referi conducerea i utilizarea depozitului de date.

n privinla utilizrii datelor din depozitele de date trebuie precizat c multe organizaii utilizeaz aceste informaii pentru sprijinirea lurii deciziilor n diferite domenii de activitate cum ar fi :

sporirea focalizrii pe clieni, care include analize ale vnzrilor (preferine, periodicitate, cicluri bugetare, apetit pentru cumprare etc.) ;

reorientarea produciei i gestionarea portofoliului de produse, comparnd performanele vnzrilor pe trimestre, ani, zone geografice, n ordinea celor mai bune strategii de producie;

analiza operaiilor i cutarea surselor de profit;

gestionarea relaiilor cu clienii ;

gestionarea costului activelor corporale.

Data warehousing este, de asemenea, foarte util din punct de vedere al integrrii surselor de date heterogene. Multe organizaii colecteaz, n mod obinuit, diferite tipuri de date i ntrein baze de date mari din surse de informaii multiple, heterogene, autonome i distributive. Integrarea acestor date i obinerea unui acces eficient la ele este lucrul cel mai dorit. Multe eforturi au fost depuse n industria bazelor de date i n comunitile de cercetare pentru ndeplinirea acestui scop.

n concepia bazelor de date tradiionale integrarea bazelor de date heterogene este realizat de "wrappers" i integratori (integrators) sau mediatori (mediators) asupra bazelor de date multiple (de exemplu: IBM Data Joiner, Informix Data Blade). Cnd o interogare este pus unui site client, un dicionar de metadate este utilizat la transformarea interogrii n interogri corespunztoare site-urilor heterogene implicate. Aceste interogri sunt atunci mapate i transmise proceselor locale de interogare. Rezultatele primite de la diferite site-uri sunt integrate n rspunsul global.

Acest concept de interogare necesit procese complexe de filtrare i integrare, care concureaz la resursele de procesare. Este ineficient i potenial scump pentru interogri frecvente, n special pentru interogri ce solicit agregri. Data warehousing furnizeaz o interesant alternativ la conceptul tradiional de integrare a bazelor de date heterogene descrise mai sus. Data warehousing folosete conceptul "update-driven" n care informaiile din surse multiple, heterogene sunt interogate n avans i stocate n depozitul de date pentru integrare direct i analiz. Spre deosebire de bazele de date cu procesare on-line, depozitele de date nu conin informaiile cele mai proaspete. Cu toate acestea, un depozit de date determin o nalt performan prin integrarea bazelor de date heterogene ntruct datele sunt copiate, preprocesate, integrate, adnotate, nsumate i restructurate ntr-o colecie semantic de date (semantic data store). n plus procesul de interogare din depozitul de date nu interfereaz cu procesele din sursele locale. De altfel, depozitele de date pot stoca i integra informaii istorice i sprijin interogri multidimensionale complexe. 1.3. Obiectivele Data Warehouse

n sintez, scopurile unui depozit de date sunt urmtoarele:

Acces sporit la date pentru utilizatori. Depozitul de date furnizeaz accesul la datele integrate ale ntreprinderii, anterior blocat prin ci neprietenoase. Utilizatorii pot acum s stabileasc, cu un minim de efort, o conexiune garantat la depozitul de date prin intermediul unui microca1culator. Securitatea este ntrit prin the warehouse front-end application, prin serverul bazei de date sau prin ambele.

O singur versiune a adevrului. Datele din depozitele de date sunt consistente i au calitatea asigurat nainte de a fi puse la dispoziia utilizatorilor finali. n msura n care se se utilizeaz o surs comun de date, depozitele de date pun capt dezbaterilor privind veridicitatea datelor utilizate sau citate n edinele de lucru. Depozitul de date ncepe s fie resursa comun de date pentru nivelurile decizionale din organizaii. Menionm c "o singur versiune a adevrului" este adesea posibil numai dup multe discuii i dezbateri asupra termenilor utilizai n organizaie. De exemplu, termenul de "client ru platnic" poate avea mai multe nelesuri: client care nu pltete la timp, client care nu pltete dect parial, client care nu pltete niciodat etc. Ar putea fi stabilit i o alt acceptiune: clienti care au datorii mai vechi de o lun. n mod sigur aceste acceptiuni au influen asupra proceselor decizionale i asupra pertinentei deciziilor.

nregistrarea cu acuratete a trecutului. Multe date primite de manageri nu sunt semnificative, dac nu sunt comparate cu datele anterioare. De exemplu, rapoartele care compar performantele actuale ale companiei cu cele din anul precedent sunt comune. Rapoartele care arat performantele companiei pentru fiecare lun din ultimii trei ani pot fi foarte interesante pentru decidenti. Sistemele operationale nu vor putea permite acest gen de informatii. Un depozit de date va fi utilizat pentru nregistrarea cu acuratete a trecutului, prsind sistemele OLPT libere pentru a realiza focalizarea pe corecta nregistrare curent a tranzactiilor. Datele istorice sunt ncrcate i integrate cu alte date n depozit pentru un acces rapid.

Acces combinat sintez/detaliu la date. Rapoartele dinamice i instrumentele de interogare OLAP (de exemplu, releveele din programele de calcul tabelar, drill-up, drill-down) permit utilizatorilor s vizualizeze informatiile din depozitul de date sub diferite unghiuri i la diferite niveluri de detaliere. Aceste disponibilitti oferite de depozitele de date reduc timpul i efortul necesar pentru colectarea, formatarea i filtrarea informatiilor plecnd de la date.

Separarea prelucrri/ar de nivel opera1ional i analitic. Procesele decizionale i procesele operationale sunt totalmente divergente arhitectural. ncercarea de a se reuni n acelai sistem informatiile decizionale i operationale determin ca ntretinerea sistemului s devin o problem.

Pornind de la procesele operationale, depozitul de date furnizeaz o arhitectur separat pentru implementarea deciziilor. Aceasta face ca ntreaga arhitectur IT a ntreprinderii s devin mult mai deschis schimbrii cerintelor informationale.

Capitolul 2

CONSTRUCIA SI STRUCTURA UNUI

DEPOZIT DE DATE

S analizm n continuare principalele cerine pe care trebuie s le ndeplineasc un

depozit de date i efectele pe care acestea le au asupra structurii sale.

La fel ca i n cazul sistemelor OLTP, exist o foarte strns legtur ntre caracteristicile particulare ale afacerii i structura bazei de date, pentru simplul motiv c optimizarea performanelor nu se poate face fr a ine cont de ele. n plus, data warehouse este utilizat n procesul de luare a deciziilor, deci interaciunea sa cu personalul uman este mult mai intens. Trebuie ca sistemul s raspund rapid la ntrebri care presupun prelucrarea

unui volum mare de date i calculul unor funcii statistice relevante pentru mangementul afacerii respecive. Cum ntrebrile nu sunt tot tipul asemntoare, iar personalul care trebuie s foloseasc baza de date nu este dect rare ori pregtit n domeniul IT, se poate considera c pregtirea acestui personal face parte din construcia depozitului de date. n concluzie, data warehouse nu e n general un produs care s poat fi furnizat la cheie de ctre o firm de specialitate, ci un proiect de dezvoltare al companiei beneficiare, proiect care va fi realizat n colaborare cu o firm din domeniul IT.

Dezvoltarea unui astfel de proiect cere mult timp (n funcie de mrimea companiei i de resursele alocate, de la cteva luni pn la perioade de timp ce se apropie de un an) i se lovete adesea de obstacole neprevzute; de aceea multe companii dezvolt mai nti un proiect-pilot pentru a ctiga experien. O alt alternativ des folosit este construcia unui depozit de date ceva mai mic, folosit de obicei doar de un departament, i care poart numele de data mart.

2.1 Integrarea datelor

Prima problem practic pe care o ntlnim n construirea unui depozit de date este

eterogenitatea surselor de date. Unele companii au dorit s includ n depozit i date vechi de zece-cinsprezece ani, date care au fost memorate n formate vechi i pe dispozitive fizice considerate astzi depite. n plus, exist i probleme de inconsisten (erori, date lips, etc.). Aceste probleme trebuie rezolvate n manier specific; spre exemplu, informaia care lipsete va fi nlocuit de obicei cu o medie a valorilor vecine, pentru c nu trebuie s influeneze parametrii statistici ai variabilelor pe care le caracterizeaz. Adunarea tuturor datelor poate deci s dureze destul de mult, n unele cazuri luni de zile. Achiziionarea de hardware nou, destinat special depozitului de date, pare a fi necesar, dei multe companii ncearc (n general fr succes) s foloseasc acelai hardware pe care au i vechile sisteme OLTP. Datorit dimensiunilor mari (i perspectivelor de a crete i mai mult) ale bazei de date se opteaz cel mai frecvent pentru o organizare distribuit. Pentru a mbunti accesul la nregistrrile din baza de date, copii ale dicionarului datelor sunt pstrate n fiecare din fragmentele sistemului, chiar dac administrarea sa se face centralizat. Datorit cantitii mari de informaie care trebuie prelucrat, se opteaz de obicei pentru scrierea de programe care s fac toate prelucrrile necesare nainte de introducerea n depozit. Se disting trei grupe principale de instrumente care trebuiesc proiectate i utilizate :

instrumente pentru migrri de date, transformri simple care au ca scop aducerea tuturor datelor la acelai format, n general prin nlocuirea unor termeni echivaleni cu un sinonim unic (de exemplu, clas, categorie i grup cu categorie)

instrumente de periere (scrubbing), care se folosesc n transformri specifice domeniului, cum ar fi extragerea unor componente ale unei adrese

instrumente de audit, ceva mai complexe, folosite la scanarea datelor pentru a detecta diverse anomalii i relaii ntre entiti (sau violri de reguli sau relaii deja stabilite)

Odat construite, aceste instrumente vor fi utile i dup terminarea construciei depozitului de date, la operaiunile de actualizare.

2.2 Principalele deosebiri dintre OLTP i OLAP

Pn acum am pus n eviden numai probleme pe care un depozit de date trebuie s le rezolve n plus fa de o baz de date OLTP. Exist ns i reversul medaliei, adic mici avantaje pe care ni le ofer problema implementrii unui data warehouse, avantaje pe care le putem specula att pentru a eficientiza sistemul ct i pentru a ne simplifica munca. Pentru a pune n eviden aceste avantaje vom enumera cteva deosebiri ntre sarcinile pe care trebuie s le indeplineasc un sistem OLTP i cele pe care le va ndeplini un sistem OLAP (On Line Analithical Processing) :

Cantitatea de date coninut :

OLTP - puine date, reprezentnd valori curente

OLAP - multe date, o adevrat arhiv

Cantitatea de date folosit la o tranzacie :

OLTP - puine, adesea doar o nregistrare

OLAP - multe date, adesea tabele ntregi

Timpul de rspuns :

OLTP - rapid, cel mult de ordinul secundelor

OLAP - pn la cateva minute

Actualizri ale datelor :

OLTP - frecvente, fcute de mai muli utilizatori, de obicei simultan

OLAP - rare, fcute de un singur utilizator

Numr de tranzacii :

OLTP - mare ntr-o unitate de timp

OLAP - relativ mic

Scrierile n baza de date n sistemele OLAP sunt completri cu date la zi. Nu este esenial s se scrie datele imediat ce au fost obinute, pentru c oricum nu vor influena mult analiza. De aici rezult n primul rand c aceste scrieri se pot face ntr-o perioad de timpn care baza de date nu este folosit, de exemplun timpul nopii. Problema accesului concurent, de-a dreptul dificil n cazul sistemelor OLTP, i a crei rezolvare e mare consumatoare de resurse, este practic inexistent n cazul OLAP. De aceea putem renuna fr probleme la meninerea unor jurnale complete ale tranzaciilor i la msurile de protejare a consistenei informaiei din baza de date (segmente roll-back). De asemenea, faptul c up-date-ul se face fr a modifica datele existente (operaii de tergere sunt extrem de rare pentru c nimeni nu are motive serioase de a modifica date de arhiv) simplific metodele de organizare a fiierelor care conin datele.

Din nefericire exploatarea acestor mici avantaje nu rezolv principala problem de care ne lovim, i anume viteza mic a sistemului, datorat n special faptului c se utilizeaz volume mari de date la fiecare tranzacie. Cum utilizatorii consider inacceptabil s atepte o jumtate de or sau mai mult rezultatul unei cereri, ne vedem nevoii s sacrificm spaiu pe disc n scopul mbuntirii vitezei. Creterea redundanei duce la creterea costurilor hardware-ului folosit, dar odat cu progresul tehnic acest lucru nu mai este chiar aa de important, preurile componentelor hard de stocare scznd vertiginos n ultima vreme.

Se observ aici c modelul relaional nu mai este potrivit sistemelor OLAP. Normalizarea tabelelor, pas esenial n proiectarea unui sistem OLTP cu ajutorul modelului relaional, avea ca efect (i scop) reducerea redundanei. Un sistem puternic normalizat are ns dezavantajul c e nevoie de un numr mare de join-uri pentru a regsi informaia din tabele. Pentru baze de date foarte mari, cum e depozitul de date, aceast reducere a vitezei este inacceptabil i de aici rezult c strategia de proiectare tradiional a unei baze de date relaionale nu e aplicabil i pentru data warehouse.

Modelul relainal nu este ns total depit de situaie. Totul depinde, aa cum am mai spus, de caracteristicile particulare ale datelor care trebuie incluse n depozit. Dac modelul relaional se potrivete bine situaiei, se poate adopta o organizare de tip entitate-relaie, cu modificri, desigur. Dup normalizarea tabelelor (necesar pentru stabilirea cu claritate a structurii depozitului nostru de date) trebuie aplicat o operaiune de denormalizare, constnd n recombinarea cu grij a tabelelor care nu introduc redundan mare, dar urmeaz a fi folosite la multe operaii de tip join.

2.3 Modelul multidimensional

Modelul multidimensional constituie o alternativ de proiectare a structurii bazelor de date. Acest model rspunde mai bine cerinelor data warehouse dect clasicul model relaional. Conceptele fundamentale ale modelului multidimensional sunt faptele i dimensiunile. Faptele sunt elementele centrale, datele afacerii, iar dimensiunile sunt moduri de a privi informaia. Exemplul clasic este reprezentarea vnzrilor unei companii. Fiecare tranzacie comercial reprezint un fapt, iar locul unde s-a produs aceast tranzacie, momentul i tipul produsului vndut constituie dimensiunile. Sigur, acest model nu e aplicabil numai n tehnologia depozitelor de date, poate fi folosit i n proiectarea sistemelor OLTP. Productorii SGBD-urilor de acest tip susin chiar c pentru baze de date de dimensiuni medii, modelul multidimesional are perfomane superioare celui relaional.

Faptele pot fi memorate ntr-un tabel i dimensiunile n tabele separate, ceea ce face posibil aplicarea modelului multidimensional i n SGBD-uri relaionale. Avantajele acestei abordri sunt uurina n navigare prin baza de date i folosirea softului deja existent pentru manipularea datelor.

2.3.1 Schema stea

Dac privim tabela faptelor (sau msurilor) ca pe un centru al bazei de date, iar tabelele dimensiuni ca pe nite satelii ai si, reprezentarea grafic a arhitecturii modelului de organizare multidimensional capt un aspect de stea. Tabelul central, al faptelor, va conine cte o cheie extern (la nivel de nregistrare, desigur) pentru fiecare tabel-satelit ce reprezint o dimensiune a informaiei-fapt.

Schema este simpl i poate fi foarte eficient cu condiia ca dimensiunile s fie alese corect, adic s reprezinte concepte naturale proprii afacerii pe care trebuie s-o deserveasc sistemul respectiv. De asemenea, munca analitilor care vor exploata depozitul de date este uurat fiindc organizarea informaiei este n conformitate cu modelul intuitiv n care gndesc ei afacerea.

Aceast arhitectur are i un punct slab : implic ocuparea unui spaiu mare pentru

stocarea datelor, aspect asupra cruia se va reveni mai trziu.

2.3.2 Agregarea n schema multidimensional

Multe din operaiile care se efectueaz n procesul de luare a deciziilor sunt de natur statistic i implic sumri pariale. Spre exemplu, n analiza vnzarilor unui anume tip de produs, cum ar fi siropul de tuse, poate fi util, dac nu chiar necesar s se sumeze toate tranzaciile din fiecare lun, pentru a se urmri evoluia cererii i a se putea prevedea consumul n viitor. Nu ar fi de loc nelept s se studieze fiecare vnzare n parte, pentru c acest lucru nu ar aduce nici un fel de informaie nou, dar o prognoz corect nu poate fi fcut doar pe baza faptului c n lunile de iarn mbolnvirile sunt mai frecvente, fiind nevoie de precizia pe care doar experiena, acumulat sub form de date n depozit, o poate da.

Aceste sume pariale (pot fi i alte funcii statistice, foarte frecvent medii) se pot face la diferite nivele (n cazul de mai sus la nivel de lun, sezon sau an). Rezultatele pariale de acest tip se numesc agregri, iar nivelele respective nivele de agregare. Rezult de aici o organizare natural a dimensiunilor n ierarhii. Navigarea prin aceste ierarhii se poate face n dou direcii, spre nivelul superior, operaie cunoscut sub numele de roll-up sau spre nivelul inferior, adic drill-down. Ambele operaii se dovedesc a fi foarte utile i frecvent folosite, ceea ce subliniaz calitile modelului multidimensional.

Iat i un exemplu de tabele de fapte i dimensiuni :

a) tabela faptelor

Cod produs Cod timp Cod magazin Cantitate vandut Pre unitar

100 352 14 30 200

101 316 12 59 211

104 567 5 43 143

110 234 13 78 2000

b) tabela dimensiunii timp

Cod timp Data Nivel

352 21.07.95 tranzacie

316 18.04.89 tranzacie

567 dec 1999 medie lunar

n tabela dimensiune de mai sus se observ dou tipuri de date, i anume nregistrri la nivel de tranzacie i nregistrri medii lunare. Sigur, mediile lunare pot fi calculate din nregistrrile la nivel de de tranzacie, deci pstrarea lor n tabel introduce redundan. Dar dac baza de date va avea de rspuns frecvent la ntrebri de tipul Care este graficul vnzrilor lunare ale produsului X n ultimii 5 ani ?, atunci viteza de rspuns ar putea crete semnificativ.

Se nate acum o ntrebare natural : Cte nivele de agregare s pstrm n tabelul dimensiune ?

Distingem dou soluii extreme : s reinem n tabel toate nivelele posibile, soluie care ar optimiza viteza cu preul unui consum mare de spaiu pe disc (dimensiunile bazei de date pot crete de cteva ori) sau s nu reinem nici un nivel, soluie care ar reduce la minimum spaiul ocupat, dar cu consecine dezastruoase n ceea ce privete viteza de operare. n plus, toate datele agregate trebuiesc calculate n momentul introducerii de date n depozit. La prima populare a depozitului cu date, adic la construcia sa, acest fapt nu constituie un impediment, deoarece construcia dureaz oricum destul de mult, dar up-datrile ulterioare nu mai au la dispoziie la fel de mult timp, pentru c baza de date nu poate fi meninut mult n stare de inoperabilitate.

Evident, nici una din aceste soluii nu este suficient de bun pentru a putea fi aplicat practic. Optimul este pe undeva pe la mijloc, dar unde ? Din nefericire nu s-a gsit pn la ora actual un algoritm care s rezolve automat aceast problem. De cele mai mult ori rspunsul de afl la cei care vor folosi efectiv depoztul da date fiindc ei tiu cel mai bine care sunt ntrebrile la care va trebui s rspund sistemul. Acesta e principlul motiv pentru care dezvoltarea unui asemenea sistem trebuie s fie fcut n colaborare cu beneficiarii. Oportunitatea sau inoportunitatea unei anume agregri poate fi decis n funcie de raportul dintre spaiul suplimentar pe care l cere i creterea de vitez pe care o aduce. Pentru a evalua acest raport nu dispunem de nici o unitate de msur, dar avem totui un criteriu calitativ care ne pemite s difereniem agregrile utile de cele proaste, i anume densitatea datelor. Daca un nivel al unei ierarhii (numit uneori element al dimensunii) totalizeaz informaii dintr-un numr mare de linii al unui alt nivel din ierarhia sa, atunci agregarea pe nivelul respectiv e pe de o parte consumatoare de spatiu puin i pe de alt parte un factor bun de mbuntire a vitezei, deci o agregare recomandabil. Reciproc, dac un nivel ierarhic totalizeaz un numar mic de linii ale nivelului inferior, agregarea respectiv nici nu aduce un spor de vitez demn de considerat, nici nu ocup un spaiu suficient de mic pentru ca s nu deranjeze.

Problema care a rmas nerezolvat este timpul mare necesar actualizrii tabelelor cu multe nivele de agregare; din consideretele artate mai sus, vom avea cel mai frecvent agregri care totalizeaz un mare numr de linii, deci necesit un volum mare de calcul pentru actualizare atunci cnd liniile de care depind sunt modificate. Rezolvarea acestei probleme este adesea dificil, mai ales dac suntem n cazul unui depozit de date foarte mare. E posibil ca fereastra de timp disponibil pentru up-date, de obicei o noapte, s nu fie suficient. innd cont de particularitile datelor se pot gsi metode de actualizare a tabelelor dimensionale fr a le reconstrui de zero; dac e posibil, se recurge la dou tipuri de up-date : unul implicnd un volum de date mai mic, i care se poate face ntr-o noapte, i unul mai complex, cu un volum de date mai mare, care s fie fcut automat n week-end. De asemenea, dac arhitectura bazei de date este distribuit se vor face scrieri n paralel. Dac unele componente cer un timp mult peste media pentru up-date i structura bazei permite, se pot up-data componente diferite la momente diferite, fr a afecta pe utilizatori.

2.3.3 Normalizare parial; schema fulg

Pstrarea datelor n tabele nenormalizate prezint avantajele unui acces rapid i al simplitii modelului de organizare al informaiei. Exist, bineneles, i un mare dezavantaj: spaiul prea mare ocupat pe disc. Cnd acest spaiu este prea mare, costurile devin insuportabile i atunci trebuie fcute nite compromisuri.

De obicei se prefer meninerea tabelelor de fapte n form nenormalizat, dar se normalizeaz tabelele-dimensiuni. Se ctig astfel spaiu pe disc, dar cu preul creterii complexitii organizrii datelor. Navigarea este din acest motiv ngreuiat, iar instrumentele folosite pentru formularea cererilor complexe devin greu de proiectat i de utilizat. De aici rezult c e de preferat s nu se elimine toate anomaliile, ci numai cele care introduc redundan mare n baza de date. Gsirea modelului optim nu e ntotdeauna simpl, dar efortul depus va fi pe deplin recompensat de rezultate.

n general, fiecare tabel - dimensiune va conine cheia primului nivel de agregare, iar fiecare nivel de agregare va conine cheia nivelului imediat urmtor n ierarhie. Schema obinut astfel are un aspect de fulg de zapad, de undei primete i numele. Dac exist mai multe tabele de fapte care partajeaz aceleai dimensiuni, lucru ntalnit frecvent n depozitele de date mari, modelul fulg devine prin extensie o constelaie de fapte. Sigur, schema devine ceva mai complicat, dar exploatarea relaiilor dintre fapte poate aduce mbuntiri ale performanei sistemului.

Micorarea tabelelor dimensionale este un ctig nu numai din punct de vedere al spaiului necesar pentru stocarea informaiei, ci i din punct de vedere al vitezei de rspuns; i acest fapt trebuie avut n vedere la stabilirea arhitecturii depozitului de date.

O analiz atent a acestei scheme de organizare a datelor arat faptul c ea ofer un sprijin natural pentru ierarhiile dimensionale, ceea ce constituie un argument n plus pentru utilizarea sa.

Dei din punct de vedere practic este superioar schemei stea, schema fulg nu rezolv ns toate problemele legate de viteza de rspuns a sistemului. Nevoia de instrumente care s sporeasc rapiditatea calculului rmne stringent. Principalele instrumente folosite pentru mbuntirea vitezei sunt indecii i view-urile materializate.

2.3.4 Stocarea datelor n vectori multidimensionali

Pn acum am vorbit despre implementarea modelului multidimensional ntr-un sistem de gestiune a bazelor de date relaional ( soluie cunoscut i sub numele de ROLAP - Relational On Line Analithical Processing). Aceasta nu este ns singura opiune; datele pot fi stocate n structuri de date speciale, i anume vectorii multidimensionali, soluie denumit generic MOLAP (Multidimensional On Line Analithical Processing).

nainte de a descrie efectiv reprezentarea datelor sub form de vectori multidimensionali vom da o descriere formal a modelului multidimensional. Dei din punct de vedere conceptual acest model pare a fi destul de simplu, descrierile matematice sunt ceva mai complicate dact algebra relaional. Interesul crescut care se manifest n ultima vreme pentru aceste baze de date (reamintesc, productori de asemenea sisteme susin c performanele lor sunt superioare SGBD-urilor relaionale, pentru baze de date de dimensiuni medii) a dus la apariia mai multor modele matematice pentru ele. Ne vom opri asupra unuia din ele, cunoscut sub numele de model MD, propus de Cabibbo i Torlone.

Pentru a fixa ideile, relum n termeni mai precii principalele concepte de lucru :

Definiia 1 Numim fapte sau msuri datele principale pe care le urmrim.

Faptele sunt deci n general date numerice care caracterizeaz tranzaciile. Cele mai ntlnite exemple sunt vnzrile unei companii, stocurile dintr-un depozit, etc.

Definiia 2 Dimensiunile sunt modurile naturale de a privi informaia reprezentat de fapte.

Exemple tipice de dimensiuni sunt timpul, zona geografic, tipul produsului vndut.

Definiia 3 Elementele dimensiunii sunt date care reprezint fiecare cte un nivel al unei

ierarhii.

Fiecare nivel corespunde unei agregri. De remarcat c o dimensiune poate fi mprit n mai multe feluri n ierarhii. De exemplu, dimesiunea geografic poate fi mprit n urmtoarele moduri

1. ora < jude < ar

2. ora < zon < regiune istoric (Ardeal, Moldova, etc)

Definiia 4 Atributele dimensiunii sunt valori atomice sau compuse care caracterizeaz dimensiunea.

Atributele permit caracterizarea datelor neierarhice. Un exemplu de atribut pentru dimensiunea produs este managerul de marc.

O formalizare matematic a modelului multidimensional

Pentru a formaliza aceste concepte, fixm nti dou multimi numrabile i disjuncte,

de nume i de valori. Pentru fiecare nivel alegem un nume. Fie N mulimea de nume asociat nivelelor. Fiecrui nivel i vom asocia o mulime numrabil de valori, numit domeniu, i pe care o notm cu DOM(l), ( l N De notat c domeniile a dou nivele distincte sunt disjuncte, adic

Definiia 5 Numim dimensiune MD o mulime parial ordonat de nivele L ( N mpreun cu o familie de funcii roll-up care include cte o funcie

Dac l1, l2 ( L cu spunem c l1 este deasupra lui l2. Funciie roll-up definesc, bineneles, operaiile de roll-up de la un nivel la altul. Vom numi asstomic o dimensiune cu un singur nivel. Se poate identifica, pentru comoditate, o dimensiune atomic cu singurul su nivel.

Definiia 6 Se numete schem MD un triplet de forma (D, F, ), unde

D este o mulime finit de dimensiuni

F este o mulime finit de f-tabele de forma

EMBED Equation.DSMT4 , unde f este un nume, Ai cu 0 '2002-06-01'

AND Data < '2002-09-01';

CREATE VIEW X AS

SELECT Cod_comis, sum(Pret*Cantitate) val, max(Pret*Cantitate) maxval

FROM U

GROUP BY Cod_comis;

SELECT V.Cod_comis, U.Cod_reg,

FROM V, U, X

WHERE V.Cod_comis = U.Cod_comis

AND V.Cod_comis = X.Cod_comis

AND X.val > V.val

AND X.maxval < X.val * 4;

Dac structura bazei de date ar fi fost mai complicat, aa cum se ntmpl de obicei n realitate, cererile de mai sus ar fi devenit i mai lungi i mai greu de neles. De asemenea, astfel de cereri odat scrise nu vor fi folosite mereu la fel, datorit faptului c procesul de analiz la care este folosit baza de date este dinamic. Cererile vor trebui adaptate (sau rescrise), de unde rezult c e nevoie de ntreinerea lor, ori asta e un lucru dificil dac ele nu sunt uor de neles. n plus, se remarc faptul c toate rezolvrile problemelor de mai sus se fac prin mai multe parcurgeri ale tabelelor. Acest lucru, coroborat cu structura lor complicat induce o nou problem : motorul de analiz SQL nu va putea s le optimizeze (sau nu le va putea optimiza pe toate). Cum renunarea la SQL nu este fezabil din considerente mai sus descrise, e necesar un compromis, i anume extinderea limbajului SQL astfel nct s poat exprima clar i succint i astfel de cereri. Utilizatorii vor putea nva relativ repede i uor noile faciliti ale limbajului, iar sintaxa va fi mai simpl i codul mai uor de optimizat.

3.1.1 Extinderea SQL

Pentru a satisface toate criteriile de mai sus, e necesar ca modificrile aduse sintaxei

SQL s fie minime i n plus s se pstreze principiile generale de formulare a unei cereri. O soluie n acest sens este adugarea unor clauze instruciunii SELECT care s permit exprimarea natural a restriciilor impuse variabilelor de grupare.

Modificri aduse sintaxei SQL

Clauzele FROM i WHERE nu vor fi modificate. n clauza GROUP BY se va opera doar o schimbare minor, i anume se va permite specificarea variabilelor de grupare, de exemplu

GROUP BY Cantitate, Pret : C, P

C i P fiind variabile de grupare.

Se introduce o nou clauz, SUCH THAT. Ea are rolul de a introduce restricii asupra variabilelor de grupare. Condiia care conine restriciile respective poate fi complex, format eventual din mai multe subclauze conectate prin operatori logici (AND, NOT i OR). Clauza HAVING va conine alturi de restriciile obinuite i agregri dup unul sau mai multe atribute. Se observ c din punctul de vedere al utilizatorului schimbrile sunt foarte uor de nvat (cteva ore par a fi arhisuficiente chiar i pentru un nespecialist). Pentru a demonstra i eficiena lor vom prezenta rezolvrile cererilor de mai sus folosind sintaxa mbogit.

Rezolvrile exemplelor n noul context

Soluie pentru prima cerere :

SELECT Cod_comis, Cantitate, Cod_regiune

FROM Vanzari

GROUP BY Cod_comis : C

SUCH THAT C.Cantitate = max(Cantitate);

mbuntirea este evident. Iat i forma pe care o ia interogarea de la problema 2 :

SELECT Cod_comis, avg(A.Cantitate), avg(B.Cantitate)

FROM Vanzari

GROUP BY Cod_comis : A, B

SUCH THAT A.Cod_prod=100 AND B.Cod_prod=200;

Cererea de mai sus ilustreaz modul de utilizare a variabilelor de grupare. i n acest caz exprimarea este mult mai scurt i mai uor de neles. Problema 3 se rezolv astfel :

SELECT Cod_comis, COUNT(A.*), COUNT(B.*)

FORM Vanzari

GROUP BY Cod_comis : A, B

SUCH THAT (A.Data < '2002-07-01'

AND A.Cantitate > avg(Cantitate))

AND (B.Data >= '2002-07-01'

AND B.Cantitate > avg(Cantitate));

n fine, problema 4 poate fi rezolvat cu urmtoarea cerere:

SELECT Pret*Cantitate, Cod_reg

FROM Vanzari

GROUP BY Cod_comis : A

SUCH THAT A.Data >= '2002-06-01' AND B.Data < '2002-09-01'

HAVING sum(A.Pret * A.Cantitate) > 4*sum(Pret*Cantitate)

AND A.Pret * A.Cantitate = max(A.Pret * A.Cantitate);

Odat cu aceste modificri nu putem spune ns c am rezolvat complet problema interogrilor specifice OLAP. Cererile se pot scrie acum mai uor i mai natural, dar problema rezolvrii lor eficiente rmne. n seciunea urmtoare se trateaz un aspect specific implementrii cererilor n OLAP, i anume calculul rezultatelor cererilor cu agregri multiple.

3.2 Calculul cubului de date

Aa cum am menionat n seciunea dedicat agregrilor, meninerea tuturor nivelelor de agregare n baza de date este practic imposibil. Cum procesul de analiz pe care trebuie s-l sprijine sistemele OLAP necesit utilizarea tuturor acestor nivele, chiar dac nu simultan, rezult c viteza de calcul a diferitelor agregri rmne o chestiune de prim importan n domeniul data warehouse. n cazul agregrilor de date relativ la mai multe dimensiuni, operaii foarte frecvent ntlnite n OLAP, datele stocate n nivelele de agregare ale dimensiunilor ajut mai puin la creterea vitezei, deci e nevoie de algoritmi performani pentru ca analiza s se poat desfura n condiii bune. Soluia stocrii unor agregri precalculate e i ea binevenit (aproape indispensabil). S-au cutat diverse soluii pentru aceast problem, att n cazul reprezentrii relaionale, ct i n cazul reprezentrii datelor cu vectori multidimensionali.

3.2.1 Cazul relaional

Operatorul Cub

Operatorul de grupare implementat n SQL standard nu este suficient pentru a rezolva problema; n situaiile practice analiza cere adesea calcularea tuturor agregrilor, adic dup toate combinrile de atribute, sau mcar a unei submulimi mari a acestei mulimi. Operatorul Cub, propus de Gray face tocmai acest calcul. S lum drept exemplu un model multidimensional cu numai trei dimensiuni, dar tipice, i anume produs, zon i timp. Faptul va fi valoarea tranzaciei. Atunci Cubul va calcula vnzrile grupate dup produs, zon i timp; dup zon i timp; dup produs i zon; dup produs i timp; numai dup produs; numai dup timp; numai dup zon, i n final vnzrile totale. Acceptarea rapid de ctre specialiti a utilitii operatorului a fcut ca o variant a acestuia s fie propus pentru mbogirea standardului SQL. S-au propus diveri algoritmi pentru implementarea Cubului n cadrul ROLAP, muli fiind n fapt extensii ale algoritmilor clasici pentru calculul operatorului SQL de grupare. Pentru creterea eficienei s-au urmrit trei idei principale :

1. Folosirea unor operaii de grupare sau sortare a atributelor dimensiunii pentru a apropia tuplurile ntre care exist relaii

2. Folosirea rezultatelor pariale ale unor grupri efectuate pentru calculul unei subagregri la sub-agregarea urmtoare, i n fine

3. Calculul unei agregri pe baza unei alte agregri gata fcute, n general mult mai mici dect tabela de baz.

Cei mai cunoscui algoritmi sunt PipeSort, PipeHash i Overlap. Vom descrie n continuare unul dintre ei, si anume Pipehash.

Algoritmul PipeHash

Vom defini mai nti o latice de cutare, structur pe care algoritmul o primete la intrare.

Se numete latice de cutare pentru cubul de date un graf cu urmtoarele proprieti:

nodurile reprezint fiecare cte o grupare a cubului

ntre un nod i i un nod j exist o muchie dac i numai dac j poate fi generat din i (de unde i se numete printele lui j) i j are exact cu un atribut mai puin dect i.

fiecare muchie mij a laticei are asociate dou costuri, i anume costul calculrii lui j din i cnd i nu este sortat, notat S(mij), i costul calculrii lui j din i cnd i este sortat, notat A(mij).

Observaie : gradul exterior al fiecrui nod este egal cu cardinalul mulimii atributelor gruprii pe care o reprezint. Nivelul k al laticei este mulimea nodurilor de grad exterior k. Costurile S(mij) i A(mij) trebuie calculate n prealabil cu ajutorul unor proceduri statistice.

Dup cum sugereaz i numele, algoritmul se bazeaz pe tabele de dispersie. Principala problem care trebuie rezolvat este incapacitatea de a ncrca n memorie tabelele de dispersie datorit dimensiunilor prohibitive. Algoritmul calculeaz un arbore MTS (Minimum spanning tree), subarbore al laticii cubului de date, pe care-l utilizeaz la calculul efectiv al cubului. Proprietatea principal a acestui arbore este c pentru fiecare muchie (i; j), i este cel mai mic printe al lui j. Se obin optimizri ale vitezei prin procedee ca pstrarea rezultatelor pariale ntr-un buffer-cache.

Descrierea algoritmului

Intrare : laticea de cutare

Pas 1 calculeaz aMTS = arborele MTS asociat laticii de cutare

Pas 2 lista_arbori aMTS

Pas 3 Ct timp lista arbori execut :

1. scoate un arbore A din lista arbori

2. Selecteaz-subarbore(A, A)

3. Calculeaz-subarbore(A)

Selecteaz-subarbore(A,A)

Dac memoria disponibil > memoria necesar calculului lui A atunci return A

Altfel

/* Se alege s S care va determina partiionarea lui A */

Fie S mulimea atributelor rdcinii lui A

Fie Ps = numrul maxim de partiii ale rdcinii lui A dac se face partiionarea determinat de s

/* Deteminm un subarbore As al lui A care are aceeai rdcin i conine toate gruprile care conin s */

Fie s S astfel nct memoria cerut de As / Ps s fie mai mic dect memoria disponibil

sterge As din A

se introduc arbori rmai n lista arbori

return AsCalculare-subarbore(A)

Fie M memoria disponibil;

Fie nrPri memoria necesar lui A*factor de siguran;

se partiioneaz rdcina lui A n nrPri

Pentru fiecare partiie

Se parcurge A n lrgime i pentru fiecare nod n

Se calculeaz toi fiii lui n (cu o singur parcurgere)

Dac n se afl n cache se salveaz pe disc i se elibereaz memoria ocupat de tabela sa de dispersie

Comentarii

Complexitatea acestui algoritm este exponenial; practica a artat c se comport mai bine dac datele sunt compacte. Dei performanele sale sunt net superioare abordrilor simpliste, n care gruprile se calculeaz independent, exist i soluii mai rapide.

3.2.2 Cazul multidimensional

Dei vectorii multidimensionali par la prima vedere o alegere proast pentru modalitatea de stocare i manipulare a datelor, n principal datorit mprtierii lor, proprietile lor structurale i fac o soluie foarte potrivit pentru implementarea modelului multidimensional. Calculul cubului de date este una din problemele la a crei rezolvare folosirea vectorilor multidimensionali aduce un plus de performan, demonstrnd astfel viabilitatea lor. Vom prezenta n continuare un algoritm de calcul al cubului de date bazat pe

vectori multidimensionali, elaborat de Y. Zhao, P.M. Deshpande i J.F. Naughton.

Varianta naiv

Vom descrie mai nti, pentru un plus de claritate, o variant simplificat a algoritmului, care nu evit calcule redundante i din a crei rafinare rezult algoritmul propriu-zis.

Fie V un vector tri-dimensional i A, B i C dimensiunile sale. Calculul agregrii AB poate fi vzut ca o parcurgere a vectorului de-a lungul dimensiunii C cu un plan (reprezentat de produsul cartezian al dimensiunilor A i B). n practic, V va fi partiionat, deci nu vom putea parcurge tot planul AB deodat i va trebui s facem aceast operaie pe fiecare partiie. Ne putem imagina o amplasare a partiiilor cubice n felul urmtor : aezm partiiile una lang alta astfel ncat planele corespunztoare dimensiunilor A i B s fie paralele, iar dreptele corespunztoare dimensiunii C s fie n prelungire. Dac fiecare partiie are dimensiunile de lungimi Ap , Bp , Cp , parcurgem tot corpul geometric obinut de-a lungul dimensiunii C cu dreptunghiuri de dimensiuni AcBc, trecnd prin fiecare partiie. Putem calcula rezultate pariale la trecerea prin fiecare partiie, stocndu-le pe disc i calculnd la sfrit agregarea total din toate rezultatele pariale. n felul acesta, fiecare partiie este citit o singur dat, deci numrul accesurilor de disc este minim, iar cantitatea de memorie utilizat este egal cu spaiul ocupat de o partiie. Cum partiiile sunt proiectate tocmai pentru a ncpea n memorie, nu avem probleme. Generalizarea pentru mai mult de trei dimensiuni nu pune nici un fel de probleme.

Calculul cubului presupune ns mai multe agregri. n cazul nostru, (vectorul V), trebuie s calculm agregrile AB, BC, AC, A, B, C i n final agregarea total. Se observ c putem privi mulimea agregrilor de calculat ca pe o latice (termen ntlnit i la algoritmul PipeHash) cu ABC avnd fiii AB, AC i BC, AC avnd fiii A i C, etc. Un calcul eficient se poate face dac se ia un subarbore n aceast latice i fiecare nod se va calcula din printele su din acest arbore. Determinarea arborelui optim era o problem n contextul ROLAP, pentru c dimensiunile nodurilor nu erau cunoscute dect dup calculul cubului i eram nevoii s folosim estimri mai mult sau mai puin precise. Vectorii multidimensionali ne permit ns calculul exact al acestor valori i n plus cantitatea de memorie necesar pentru calculul unui fiu, deoarece cunoatem dimensiunile vectorilor i ale partiiilor. Putem deci defini (i determina) arborele MST al laticii. Pentru fiecare nod n, printele su n arborele MST este un nod n1 de mrime minim din care se poate calcula n.

Descrierea algoritmului (varianta naiv)

Intrare : laticea de cutare

Pas 1 Calculeaz arborele MST pentru laticea de cautare

Pas 2 Calculeaz fiecare group-bydin printele

de mrime minim (din arborele MST). Se parcurge fiecare partiie a printelui de-a lungul dimensiunii i se pune rezultatul fiecrei agregri ntr-o partiie a cand o partiie e gata,se salveaz pe disc, se elibereaz memoria i se trece la urmtoarea. Dup parcurgereapartiiile produse formeaz chiar nodul ce trebuia calculat.

Algoritmul utilizeaz puin memorie (nu ncarc dect o singur partiie odat), dar sufer din urmtorul motiv : unele date sunt citite de pe disc de mai multe ori, de unde rezult pierderi de timp mari, pentru c operaiile I/O sunt foarte lente. De exemplu, nodul ABC este parcurs o dat pentru calculul fiului AB, o dat pentru BC i nc o dat pentru a calcula AC.

Din fericire, algoritmul admite mbuntiri consistente.

Varianta mbuntit (Multi-Way Array Algoritm)

Eficientizarea algoritmului se bazeaz pe minimizarea numrului de citiri ale datelor de pe disc. (Amortizarea scanrilor) Se ncearc minimizarea spaiului de memorie folosit

pentru a stoca n RAM ct mai multe date pariale, pentru a nu mai fi nevoie de rescanri.

Ordine dimensional

Un factor care poate influena pozitiv nevoia de memorie a algoritmului este ordinea logic n care privim dimensiunile. Dac avem de-a face cu un vector multidimensional ale crui dimensiuni sunt D1 , D2, , Dn, putem alege s-l parcurgem dup o ordine

= () Acest lucru e independent de memorarea lui fizic, pentru c la partiionare dimesiunile sunt tratate uniform, deci nu e nevoie de nici o operaie suplimentar.

Studiind modul de utilizare a memoriei s-a ajuns la urmtoarea regul de alocare eficient :

Dac avem de calculat o agregare () a unui vector de dimensiuni (D1 , D2, , Dn ) citit n ordinea dimensional = (D1 , D2, , Dn ) i () conine un prefix al = (D1 , D2, , Dn ) de lungime p, 1p n-1, vom aloca spaiu pentru

uniti ale elementului vectorului, unde este mrimea dimensiunii Di, iar este mrimea aceleiai dimensiuni, dar pentru partiie, deci mai mic n majoritatea cazurilor dect .

Spre exemplu, calculul agregrii BC (n cadrul exemplului de mai sus) e nevoie de

octei, pentru AC de octei, iar pentru AB de octei, unde u este numrul de octei necesar pentru a memora un element al vectorului, iar e marimea dimensiunii X a vectorului (respectiv bucii de vector rezultat n urma partiionrii).

Memoria economisit va fi folosit la calculul mai multor agregri simultan, reducnd astfel numrul de operaii I/O i deci aducnd un plus de vitez. Pentru a organiza calculele se folosete un arbore MST, la fel ca n algoritmul PipeHash.

Gsirea unui arbore MST

Arborele MST pentru un cub (D1,,Dn) ntr-o ordine dimensional dat = () este un arbore cu n + 1 nivele, rdcina () fiind la nivelul n. Fiecare nod din arbore poate fi calculat din prinii si. Calculul nu va fi ns la fel de eficient pentru fiecare dintre prini; vom alege cel mai bun printe pe baza regulii de mai sus privind necesarul de memorie. Pentru calculul nodului i se va folosi acel printe care are proprietatea c necesarul de memorie pentru calculul lui i este minim. Pentru ca acest minim s se ating, trebuie ca prefixul nodului printe coninut n i s fie de lungime minim. Dac sunt mai multe altfel de noduri, se va alege cel mai mic termeni de spaiu ocupat.

Gsirea unui arbore MST nu rezolv complet problema optimizrii calculului scubului; asta deoarece nu toi arborii MST necesit la fel de mult memorie. Diferena ntre eficiena a doi arbori MST poate fi chiar foarte mare i depinde de ordinea dimensional aleas.

Care e cel mai bun arbore MST ?

Pentru a rspunde la aceast ntrebare vom determina mai nti ct memorie e necesar pentru calculul cubului folosind un arbore MST dat. S presupunem c pentru fiecare partiie mrimea fiecrei dimensiuni este aceeai, notat cu c, adic . La nivelul n este rdcina D1,,Dn creia i alocm cn uniti de memorie; la urmtorul nivel avem nodurile, unde semnific faptul c termenul respectiv lipsete. Fiecare nod conine un prefix al rdcinii i lungimile acestor prefixe sunt evident de

lungimi n-1, n-2,,0. Conform regulii de mai sus privind alocarea memoriei, pentru acest nivel va fi nevoie de

uniti de memorie. Generaliznd, se obine pentru nivelul k un necesar de memorie de:

Putem privi aceast expresie ca pe un polinom n c; observm c ordinea n care am parcurs dimensiunile este determinant pentru valoarea sa, deoarece coeficienii depind numai de aceast ordine. E relativ simplu de gsit ordinea dimensional optim din punct de vedere al consumului de memorie; valoarea expresiei se minimizeaz dac se minimizeaz coeficienii polinomului. n consecin, minimul se atinge pentru ordinea = (D1 , D2, , Dn ) cu . Putem deci calcula necesarul de memorie pentru calculul unui arbore. Formula de calcul este ns prea complicat, fiind compus din sumele de pe fiecare nivel. E natural ntrebarea Care este o margine superioar pentru memoria necesar calculului cubului parcurgnd un arbore dat ?. Chiar dac aceast margine ar fi ceva mai mare dect necesarul real de memorie, ea ar putea fi utilizat cu succes din punct de vedere practic, pentru c oricum trebuie s rmn i o zon de memorie de rezerv. Dac notm cu d media geometric a mrimilor dimensiunilor D1 , D2, , Dn o margine superioar este cn + (d + 1 + c)n-1. Demonstraia acestui fapt este calculatorie. Pornind de la inecuaiile

(evidente din relaia de ordine dintre ), obinem prin nmulire

i aplicnd apoi regula de calcul a memoriei pentru fiecare nivel, sumnd i grupnd termenii avnd aceeai putere a lui d, rezult n final ceea ce trebuia demonstrat.

n final, utiliznd toate rezultatele de mai sus se poate trece la scrierea efectiv a algoritmului. Dac T este un arbore i nu avem destul memorie pentru a-l calcula, vom fi nevoii s nu-l parcurgem n ntregime ; unii subarbori vor fi calculai ulterior i se numesc arbori incomplei. Problema alegerii subarborilor care s fie calculai pare a fi NP-complet i se folosesc metode euristice pentru a o rezolva.

Descrierea algoritmului

Pas 1 Calculeaz T un MST pentru o ordinea dimensional optim Pas 2 Iniializeaz lista arborilor de calculat cu T

Pas 3 Pentru fiecare arbore T din lista aborilor de calculat

Pas 3.1 Creeaz subarborele de lucru W i subarborii incomplei Is Pas 3.2 Aloc memorie subarborilor

Pas 3.3 Parcurge partiiile rdcinii lui T n ordinea Pas 3.3.1 calculeaz agregarea fiecrei partiii n gruprile din W

Pas 3.3.2 genereaz rezultate intermediare pentru Is Pas 3.3.3 scrie partiiile complete ale lui W pe disc

Pas 3.3.4 scrie rezultatele intermediare n partiiile lui Is Pas 3.4 Pentru toi I

Pas 3.4.1 genereaz partiiile complete din prile lui Is Pas 3.4.2 scrie partiiile complete pe disc

Pas 3.4.3 Introduce I n lista arborilor de calculat

Importana algoritmului

Aa cum am menionat anterior, eficiena algoritmului este superioar algoritmilor rezultai din generalizarea celor folosii pentru calculul gruprilor n sistemele relaionale. Mai mult, acest algoritm poate fi utilizat i n sisteme relaionale, sigur, nu direct, ci prin ncrcarea tabelelor n vectori multidimensionali i transformarea rezultatelor n tabele. Testele practice au demonstrat un fapt surprinztor : chiar dac sunt necesare operaii suplimentare pentru cele dou transformri n i din vectori multidimensionali, algoritmul de mai sus rmne mai eficient dect cei care folosesc tabelele n mod direct.

Capitolul 4

EXPLOATAREA UNUI DEPOZIT DE DATE

-cteva elemente de data mining-

4.1 Motivaie

Cantitatea mare de date dintr-un data warehouse pune nu numai probleme legate de gestionare i accesare, ci i de interpretare. Mai concret, dac sistemul nu face altceva dect s rspund la diversele cereri formulate de utilizator pur i simplu afind nite cifre, e posibil ca rezultatul s nu fie satisfctor. Motivul este simplu: un morman de cifre, chiar dac este prezentat sub forma unui raport, se poate dovedi nefolositor dac lipsesc instrumentele adecvate pentru analiza sa. n procesul de luare a deciziilor se folosesc desigur i datele numerice, dar centrul de interes se plaseaz n sfera legturilor (corelaiilor) dintre faptele studiate. Aceste legturi nu sunt ns uor de observat, mai ales dac datele sunt eterogene (adic prezint aspecte esenial diferite ale afacerii, sub form de msurtori asupra faptelor, exprimate n uniti de msur incomensurabile).

4.1.1 Statistic inferenial versus data mining

Statistica se ocup de interpretarea datelor numerice i ofer mijloace de rezolvare a

problemei de mai sus. Din nefericire ns aceste tehnici sunt limitate, pentru c se bazeaz pe teste statistice. Un test statistic este o metod de a verifica o ipotez. Spre exemplu, testul 2 poate fi folosit pentru a determina dac dou variabile aleatoare discrete sunt independente. Valorile trebuiesc puse ntr-un tabel de contingen i apoi se aplic pur i simplu o formul de calcul. Rspunsul este confirmarea sau infirmarea ipotezei n funcie de valoarea rezultat din calculul efectuat, cu o marj de eroare prestabilit. Se evideniaz aici cteva dezavantaje:

1. Dei formula e simplu de aplicat, matematica din spatele ei este destul de complicat; dac nu cunoate bine i aceste detalii utilizatorul poate grei.

2. Testul funcioneaz doar pentru testarea unei ipoteze. Adaptarea lui pentru alte ipoteze necesit cunotine avansate de statistic.

3. Chiar dac avem la dispoziie un numr mare de teste pentru diferite ipoteze, e posibil ca la un moment dat n analiz s fie nevoie de construirea unui nou test.

4. Pentru aplicarea unui test trebuie s formulm problema n termeni matematici, lucru care nu poate fi convenabil dect pentru o persoan cu pregtire matematic.

5. Raportul dintre cantitatea de munc fcut de om i cea fcut de calculator nu este foarte bun pentru c procesul nu este automatizat.

6. n fine, ipoteza pe care o testeaz un astfel de test trebuie formulat a priori de analist. ntr-o situaie practic exist o multitudine de ipoteze care ar putea fi testate. Intuiia analistului este solicitat la maxim, pentru c el trebuie s aleag ipotezele viabile i nu are a dispoziie nici un fel de algoritm pentru aceasta. Dac n plus avem de-a face cu o situaie n care e adevrat o ipotez complet neateptat, ansele ca acest fapt s fie descoperit sunt foarte mici. Avem aici o problem serioas, pentru c tocmai descoperirea unor informaii total noi (i deci neateptate) aduce cele mai mari beneficii.

Tehnicile de analiz pe care le vom descrie ncearc s surmonteze aceste dezavantaje. Metode de analiz de acest tip au aprut nc din anii 60, dar lipsa dispozitivelor de calcul avansate a fcut ca ele s nu poat fi utilizate. Aceste rezultate au fost obinute de statisticieni ca Benzecri sau Tuckey i domeniul a fost numit de acetia statistic exploratorie. Diferena ntre statistica exploratorie i ceea ce numim n mod clasic statistic

este ns destul de mare i de aceea muli prefer s utilizeze denumirea de data mining, denumire care va fi folosit i n aceast lucrare.

4.2 Formalizarea matematic a problemei. Terminologie

n cele ce urmeaz vom descrie cteva metode matematice care pot facilita interpretarea datelor numerice. Dac aceste date se prezint sub forma unui tabel, lucru foarte frecvent n cazul rapoartelor create de un SGBD, vom privi coloanele ca pe nite variabile, iar liniile ca pe indivizi. Noiunile de individ i variabil vor fi n centrul analizei i deci merit s aruncm o privire asupra lor. Vom nota n general cu n numrul de indivizi (linii) i cu p numrul de variabile (coloane).

4.2.1 Indivizi

Indivizii pot fi vzui ca vectori reali cu p componente. Fiecare individ este caracterizat de cele p variabile, valorile acestor variabile fiind deci componenetele vectorului-individ. Spaiul se va numi spaiul indivizilor. Pentru a compara indivizii ntre ei trebuie aleas o metric pe acest spaiu. Metrica trebuie s fie compatibil cu problema pe care o studiem, adic dac doi indivizi sunt apropiai (distana dintre ei este mic), atunci

cei doi sunt asemntori. Reciproc, dac cei doi sunt la mare distan, ei trebuie s fie esenial diferii din punctul de vedere al analizei. Distaa euclidian este o bun alegere n multe cazuri, dar exist i situaii n care se vor prefera alte distane.

O calitate important a indivizilor este importana lor. Spre exemplu, dac indivizii sunt regiuni geografice i se studiaz vnzrile companiei n aceste regiuni, e posibil ca analistul s considere (din motive economice) c unele regiuni sunt mai importante, adic au un potenial mai mare pentru creterea volumului tranzaciilor. n acest caz, fiecrui individ i se va asocia un numr real subunitar numit pondere. Suma ponderilor tuturor indivizilor trebuie s fie egal cu 1. Ponderea fiecrui individ va fi proporional cu importana sa. Dac ns indivizii au importan egal, ponderile lor vor fi egale i vom considera c sunt neponderai, pentru c ponderea nu mai aduce n acest caz nici o informaie util. Indivizii neponderai se mai numesc anonimi. Acest termen este motenit, ca i termenul de individ de altfel, de la analiza sondajelor de opinie, unde pstrarea anonimatului celor intervievai mpiedic atribuirea unor ponderi.

Motivul pentru care considerm indivizii vectori n este faptul c vectorii reali pot fi reprezentai grafic prin puncte. Mulimea indivizilor pe care i analizm se va reprezenta printr-un nor de astfel de puncte. De aceea ne vom referi la aceast mulime cu sintagma norul de puncte-indivizi. Forma acestui nor poate releva informaii noi despre faptele pe care le studiem, intruct este determinat de relaiile dintre variabile. O noiune important n studiul norului de indivizi este noiunea de inerie.

Definiia 8 (Ineria)

Fie a

EMBED Equation.DSMT4 un punct oarecare. Atunci numim inerie a norului de puncte-indivizi fa

de punctul a numrul

unde M este matricea simetric i pozitiv definit care d metrica aleas pentru spaiul indivizilor, iar ei este individul cu numrul de ordine i; pi este ponderea individului i.

Definiia 9 Ineria global

Dac g este centrul de greutate al norului (e vorba de noiunea geometric de centru de greutate), atunci ineria norului fa de g se numete inerie global i se noteaz cu Ig .

Ineria fa de un punct satisface proprietatea:

relaie cunoscut sub numele de formula lui Huygens.

Tehnicile de analiz pe care le vom trata sunt bazate pe faptul c distana dintre punctele-indivizi ascunde informaie util. Din nefericire n marea majoritate a cazurilor (de fapt aproape ntotdeauna) p este mai mare dect 3, i de aceea reprezentarea grafic nu poate fi vizualizat direct. Matematica ofer ns metode de reprezentare n plan a acestui nor, cu pierdere minim de informaie. Vom reveni la acest aspect n cele ce urmeaz.

4.2.2 Variabile

La fel ca i indivizii, variabilele pot fi vzute ca vectori reali de n componente. Spaiul va fi numit spaiul variabilelor. Denumirea de variabil vine din statistic; din punct de vedere statistic, coloanele tabelului sunt selecii de volum n asupra unor variabile

aleatoare.

n general variabilele iau valori reale (procente, sume de bani, cantiti de mrfuri, etc), dar exist i cazuri n care valorile sunt discrete. Sigur, numerele naturale sunt n particular numere reale, dar dac valorile posibile ale variabilei sunt puine nu o mai putem trata ca i cum ar lua valori reale. De exemplu, dac indivizii sunt nregistrri ale datelor unor persoane putem avea o variabil care indic sexul, deci cu numai dou valori posibile. Variabilele care iau valori reale se vor numi continue, iar cele care iau valori naturale se vor numi variabile nominale. Valorile unei variabile nominale se numesc modaliti.

Pentru studiul variabilelor se folosesc urmtoarele obiecte matematice:

Definiia 10 (Media) Media de selecie a variabilei Xj este

unde pi este ponderea individului i, iar Xij este valoarea pe care o ia variabila j pentru individul i.

Definiia 11 (Dispersia) Dispersia de selecie a variabilei Xj este

cu aceleai semnificaii pentru pi i Xj .

Definiia 12 (Covariana de selecie) Covariana a dou variabile Xj i Xk este

Definiia 13 (Coeficientul de corelaie) Numim coeficient de corelaie de selecie a dou variabile numrul real

Coeficientul de corelaie dintre dou variabile este un numr subunitar. Dac valoarea

sa este apropiat de -1, cele dou variabile sunt puternic corelate negativ (creterea uneia coincide cu descreterea celeilalte), iar dac e aproape de 1, variabilele sunt corelate pozitiv. Dac ns valoarea coeficientului este zero sau aproape zero, vom spune c variabilele sunt necorelate. Practic acest lucru va fi interpretat ca un indicator la faptului c variabilele sunt independente, dei din punct de vedere matematic necorelarea nu implic independen.

4.3 Metode de analiz factorial

Analiza factorial nseamn studierea norului de puncte-indivizi prin proiecia pe un plan. Acest plan trebuie ales astfel nct deformarea norului (inevitabil datorit proieciei) s fie minim. Planul ales se va numi plan factorial principal. Astfel vom obine o imagine grafic a norului de puncte-indivizi, imagine care poate ajuta analiza. n plus, va trebui s putem caracteriza cantitativ eroarea introdus de deformarea prin proiecie si s gsim cele mai bune metode de a interpreta graficul obinut.

4.3.1 Analiza n componente principale

Analiza n componente principale (A.C.P.) este o tehnic de analiz prin proiecie care funcioneaz atunci cnd variabilele sunt continue. Avem la dispoziie doi nori de puncte : indivizi i variabile. Principiul A.C.P. este reprezentarea acestor nori ntr-un spaiu de dimensiune mult mai mic (se presupune c dimensiunile n i p ale spaiilor indivizilor i respectiv variabilelor sunt prea mari pentru a se putea face o reprezentare grafic).

n general dimensiunea acestui spaiu este 2 (deci spaiul de proiecie este chiar planul

factorial principal), dar dac reprezentarea n plan nu este suficient de precis se poate alege soluia reprezentrii norului proiectat ntr-un spaiu tridimensional, graficul rezultat fiind reprezentabil pe calculator.

Reprezentarea grafic obinut va releva informaii noi despre relaiile dintre indivizii

variabile. Spre exemplu, dac norul de puncte-indivizi are o form alungit, elipsoidal, atunci rezult c exist o corelaie liniar ntre variabile. Dac ns norul are forma aproape sferic, punctele fiind mprtiate uniform n cadrul lui, atunci nu avem nici o corelaie.

Corelaie de-a lungul unei axe Necorelare (izotropie)

Figura 4.1: Formele norilor i interpretarea lor

Analiza norului de puncte-indivizi

Aa cum am menionat anterior, spaiul de proiecie trebuie ales astfel nct deformarea s fie minim. Pentru a putea alege acest spaiu avem ns nevoie de o formulare precis, matematic, a criteriului de mai sus. Ipoteza cu care lucrm este c distanele dintre indivizi ascund informaii utile. De aceea vom cuta s minimizm modificarea acestor distane. Este evident c oricare ar fi spaiul de proiecie ales, unele distane vor fi mult modificate prin proiecie, iar altele mai puin. Trebuie s facem n aa fel nct deformarea global s fie ct mai mic. Vom alege deci spaiul de proiecie astfel nct suma ptratelor distanelor dintre proiecii s fie maxim. Aceast alegere se justific prin faptul c prin proiecie distanele se micoreaz, deci atunci cnd suma ptratelor este maxim, deformarea global este minim. Pentru a enuna acest principiu n termeni de inerie avem nevoie de urmtorul rezultat:

Lem

Ineria global este media ptratelor distanelor dintre indivizi.

Demonstraie

Se aplic formula lui Huygens pentru fiecare individ i se sumeaz relaiile :

.

rezult :

(M este peste tot matricea care d metrica)

n consecin, n termeni de inerie, criteriul de optim ia forma urmtoare : cel mai bun spaiu de proiecie este acela care maximizeaz ineria global a norului de puncte-indivizi.

Notm cu X tabelul de date, iar cu Y tabelul centrat (din fiecare variabil se scade media sa empiric). Vom lucra pe tabelul centrat. Faptul c folosim tabelul centrat Y i nu pe cel iniial X nu schimb rezultatul analizei. Acest artificiu are un singur efect, i anume mutarea centrului de greutate al norului de puncte-indivizi n originea spaiului. Astfel se simplific semnificativ calculele.

V este matricea de covarian (vij = cov(Xi ,Xj), iar M metrica. Cu aceste notaii, rezolvarea problemei reprezentrii optime a norului de puncte-indivizi este dat de urmtoarea teorem :

Teorema 1 (Spaiul de proiecie)

Subspaiul de dimensiune q pe care se proiecteaz optim n sensul maximizrii ineriei globale este generat de primii q vectori proprii ai matricii A = VM din Mp,p (). Vectori proprii sunt considerai n ordinea descresctoare a valorilor proprii corespunztoare .

Demonstraie

Fie H spaiul de proiecie optim i P1 , , Pn proieciile punctelor-indivizi A1 ,, An n acest spaiu. Aplicnd teorema lui Pitagora avem relaiile pentru

de unde rezult

, unde O este originea spaiului.

Minimizarea deformrilor revine deci la minimizarea , distanele fiind constante.

Fie un vector M-normat (i.e. aTMa = 1) i dreapta determinat de a i origine (dreapta versor a lui a). Proiecia pe a unui punct Ai, notat Qi va avea proprietatea OQi =, unde Yi este vectorul cu p componante egal cu linia i din tabelul Y . Acest fapt rezult imediat din definiia produsului scalar i innd seama c tabelul Y este obinut prin centrarea lui X. n consecin, coordonatele Qi pe sunt i deci

unde D este matricea ponderilor definit de relaia D = diag(p1,, pn).

Dac vrem s minimizm deformarea proieciei pe o dreapt de versor a, putem determina a ca soluie a problemei de programare ptratic

Rezolvm aceast problem cu metoda multiplicatorilor lui Lagrange :

EMBED Equation.DSMT4

(1)nmulim (1) la stnga cu aT i avem , M fiind matricea care d metrica pe spaiul indivizilor, trebuie s fie pozitiv definit, deci inversabil. Putem deci nmuli n relaia (1) cu M-1, de unde obinem Aa =a, de unde rezult c este valoare proprie a matricii A. Fiind solui a problemei de programare ptratic enunate mai sus, este n plus si valoarea proprie maxim. De aici rezult c a este vectorul propriu al matricii A corespunztor valorii proprii maxime.

Cutarea celui de-al doilea generator al spaiului H se face dup aceeai metod. Trebuie s gsim a2 M-normat, M-perpendicular pe a i care s minimizeze funcia . Problema de programare ptratic are deci forma

Lagrange-anul este deci :

i din condiia de anulare a derivatei avem :

Prin nmulire cu aT avem :

dar.

De aici rezult , i innd cont de faptul c avem

. Acum problema este asemntoare cu prima, deci va avea acelai tip de soluie. va fi cea de-a doua valoare proprie n ordinea mrimii. Repetnd raionamentul de q ori i renotnd a cu a1 i cu avem demonstraia complet. Subspaiul H cutat va fi deci subspaiul generat de primii q vectori proprii ai matricii A.

Observaie A se numete matricea ineriei deoarece urma sa este egal cu ineria global.

Definiia 14 (Ax principal) Se numete ax principal de inerie un vector propriu a, M-normat, al matricii de inerie.

Definiia 15 (Factor principal) Se numete factor principal asociat axei principale aj , notat uj , vectorul din uj = Maj .

Definiia 16 (Component principal) Se numete component principal de ordin j vectorul din definit de relaia cj = Y uj .

Proprietate Factorii principali uj sunt vectori proprii M-1 ortogonali ai matricii MV asociai valorilor proprii ale matricii de inerie.Analiza nenormat

Dac datele sunt omogene, adic msurate cu aceelai uniti de msur, nu e nevoie de transformri ale tabelului nainte de reprezentarea grafic. n acest caz analiza se va numi nenormat, ntruct transformarea pe care o vom aplica pentru date eterogene va fi o normare a vectorilor variabile. Metrica M utilizat n acest caz va fi matricea identitate. Aceast metric d importan egal tuturor variabilelor, indiferent de dispersia lor. Din acest motiv variabilele cu dispersia mare vor influena mai mult analiza dect cele cu dispersie mic.

Analiza normat

Datele pot fi ns destul de eterogene, i atunci este necesar o ponderare a variabilelor n funcie de dispersia lor empiric. O soluie la ndemn este mprirea fiecrei variabile cu dispersia sa. Dac ne gndim la uniti de msur, observm c rezultatul acestei

mpriri nu depinde de unitatea de msur a variabilei iniiale. De aici deducem c aceast operaie produce i o adimensionalizare a datelor. Variabilele nou obinute vor avea toate dispersia egal cu 1, deci ponderea lor n analiz va fi echilibrat. Lucrm tot cu tabelul centrat Y , din aceleai motive ca la analiza nenormat.

Cum fiecare coloan din Y reprezint o variabil centrat, deci cu media nul, rezult c este egal cu dispersia variabilei necentrate, unde D = diag(p1,, pn). n consecin, alegnd metrica D pentru spaiul variabilelor, transformarea pe care o vom aplica tabelului pentru omogenizare va fi normarea vectorilor coloane. Operaia poart numele de reducere, iar tabelul rezultat se numete tabelul centrat redus i se noteaz cu Z.

n plus, din definiia coeficientului de corelaie dintre dou variabile rezult o proprietate util a tabelului centrat redus : d2(Zj ,Zk) = 2(1-rjk), unde Zj, Zk sunt coloanele j,

respectiv k din Z iar rjk este coeficientul de corelaie dintre cele dou variabile. Consecina practic este faptul c distana dintre dou variabile centrat-reduse poate fi interpretat exact aa cum ne spune intuiia :

Dac dou variabile sunt foarte apropiate, i.e. distana dintre ele este mic, atunci ele sunt puternic corelate pozitiv i deci creterea sau descreterea uneia va finsoit de creterea i respectiv descreterea celeilalte;

Dac dimpotriv variabilele sunt foarte deprtate (i.e. distana dintre ele 4, adic maxim), atunci ele vor fi corelate negativ (rjk -1) i deci creterea uneia va fi insoit de descreterea celeilalte;

Dac distana este medie (2), atunci variaia uneia nu va influena pe cealalt, corelaia fiind aproximativ nul.

Vectorii Zj vor avea toi norma egal cu 1 (evident, de vreme ce au fost normai) i deci ntr-o reprezentare grafic vor fi puncte pe cercul de raz 1. Vom folosi acest fapt la analizarea norului de puncte-variabile.

Analiza norului de puncte-variabile

Proiecia norului de puncte-variabile pe un subspaiu de dimensiune 2 sau 3 poate fi folosit pentru analiz. Se pune aceeai problem a minimizrii deformrii, criteriul de optim fiind acelai. Rezolvarea este foarte asemntoare (de fapt absolut analoag) cu rezolvarea problemei proieciei norului de puncte-indivizi.

Se ajunge la un rezultat similar cu cel obinut pentru norul de puncte-indivizi. Subspaiul de proiecie va fi generat de vectorii proprii corespunztori primelor q valori proprii ale matricii YMYTD. Se demonstreaz ns c valorile proprii obinute n urma acestui calcul sunt egale cu cele obinute pentru indivizi. Din punct de vedere practic, asta nseamn c nu este nevoie s le mai calculm nc o dat. n plus, dimensiunea matricii ineriei este p, iar dimensiunea matricii YMYTD este n, i cum n general p este mult mai mic dect n, se vor calcula mai uor valorile proprii pentru matricea ineriei.

Reprezentarea grafic a variabilelor se face puin diferit de a indivizilor, pentru a sprijini interpretarea intuitiv a graficului. Dac indivizii se vor reprezenta prin puncte, mici discuri sau ptrate, variabilele se vor reprezenta ca nite sgei care pleac din origine i care au vrful n punctul-variabil. Variabilele vor fi astfel mai uor comparate cu nite direcii, iar dou variabile vor fi considerate asemntoare, nrudite, dac vor fi reprezentate prin direcii apropiate, ceea ce corespunde conceptului statistic de corelaie.

Definiia 17 Se numete cerc de corelaie principal subspaiul generat de vectorii corespunztori primilor q valori proprii ale matricii de inerie.

Dac analiza este normat, variabilele vor fi reprezentate ca nite sgei cu vrfurile pe cercul unitate. Unghiurile dintre aceste sgei sunt uor de comparat i de interpretat.

Putem alege i soluia reprezentrii simultane pe acelai grafic a proieciilor celor doi nori. Trebuie ns menionat c n acest caz apropierea dintre un punct-individ i un punct-variabil nu are nici o interpretare, ntruct cele dou puncte fac parte din spaii diferite. Direciile indicate de sgeile care reprezint variabilele pot ajuta la interpretarea poziiilor indivizilor n nor. Dac doi indivizi sunt diametral opui pe direcia indicat de o variabil, atunci putem trage concluzia c variabila respectiv i difereniaz puternic.

Calitatea analizei

Reprezentarea grafic ntr-un plan a norului de puncte-indivizi nu se poate face fr

deformare. Tehnica pe care am folosit-o minimizeaz aceast deformare, dar se pune problema calitii rezultatelor obinute. Cu alte cuvinte, am obinut un optim, dar ct de bun este acest optim ?

O alt ntrebare este n ce condiii putem obine rezultate satisfctoare ? n plus, dac suntem n situaia de a nu putea folosi A.C.P. din cauza rezultatelor prea imprecise, ce concluzii putem trage din acest fapt ?

Mai trebuie remarcat c n cele de mai sus s-a ignorat posibilitatea ca matricea A s

aib mai puin de q valori proprii. Avnd ns n vedere c de obicei q este 2, rareori 3, iar n i p (numrul de indivizi respectiv variabile) sunt n marea majoritate a cazurilor cel puin de ordinul zecilor, putem presupune c nu ne vom lovi niciodat practic de aceast problem.

n esen, A.C.P. revine la gsirea unui sistem de axe convenabil i la reprezentarea norului de puncte n acest sistem, fcnd abstracie de ultimele p - q axe. n consecin, pentru ca analiza s nu fie compromis, trebuie ca proiecia norului pe subspaiul generat de aceste axe s aib un procent ct mai mic din ineria norului iniial. Acest criteriu se bazeaz i el pe ipoteza c informaia este ascuns n distanele dintre indivizi.

Pentru a caracteriza calitativ analiza trebuie s gsim ct de importante sunt coordonatele punctelor pe o ax oarecare din punctul de vedere al ineriei, adic ce procent din inerie se pierde prin neglijarea axei respective. Se poate verifica printr-un calcul rapid c acest procent este proporional cu valoarea proprie j corespunztoare axei respective. Cu alte cuvinte, calitatea analizei este cu att mai bun cu ct valorile proprii 1 i 2 sunt mai mari n comparaie cu celelalte. Cazul ideal este atunci cnd primele dou valori proprii sunt mari, iar toate celelalte sunt aproape nule. Atunci graficul obinut prin A.C.P. conine aproape toat informaia din norul iniial. La polul opus se situeaz cazul n care valorile proprii descresc liniar. Raportul dintre suma primelor dou i suma total este mic i analiza mai puin precis.

Se remarc faptul ca prin A.C.P. se arunc o parte din informaia coninut de norul iniial. De aici rezult c dac datele de lucru iniiale au infomaie redundant, este posibil s-o aruncm tocmai pe aceasta, realiznd astfel o analiz precis. A.C.P. elimin deci o redundan, dac aceasta exist. Dac nu, analiza nu va fi precis, aruncndu-se informaie util. Redundana pe care o poate elimina A.C.P. este o redundan ascuns n corelaiile dintre variabile. Cu ct variabilele sunt mai puin corelate, cu att ansele unei analize precise sunt mai mici. n consecin, atunci cnd A.C.P. nu d rezultate, putem trage concluzia c variabilele pe care le studiem sunt puin corelate.

Indivizi i variabile ilustrative

Pierderea de informaie datorat proieciei, chiar dac nu este mare, poate duce la unele confuzii. Nu putem sti cu siguran dac o relaie gsit este rezultatul unui fapt obiectiv sau o iluzie dat de deformarea inerent analizei. De aceea se prefer s nu se utilizeze toate datele disponibile pentru efectuarea analizei. Se va pstra nealterat un grup de indivizi (alei aleator sau dup un criteriu specific domeniului din care provin datele). Acest grup va servi ca eantion de verificare a rezultatelor analizei. Rezultatele care se confirm i pentru aceti indivizi sunt rezultate n care putem avea ncredere. Indivizii din acest eantion se vor numi indivizi ilustrativi.

Aceeai tehnic se poate folosi i pentru variabile. Variabilele alese pentru testarea rezultatelor analizei se vor numi variabile ilustrative.

Dezavantajele ACP

Din cele de mai sus rezult c analiza n componente principale nu sufer de neajunsurile statisticii clasice, infereniale. Procesul de analiz poate fi n mare msur automatizat, reducnd la minim volumul de munc al omului. Analistul nu trebuie s formuleze nici o ipotez i nici nu are nevoie de cunotine avansate de matematic pentru a utiliza aceast metod. Este suficient s cunoasc noiunile de medie, dispersie i corelaie pentru a putea folosi un soft care face astfel de analize.

Partea proast este c analiza nu poate releva dect corelaii liniare ntre variabile. Corelaiile neliniare nu vor fi puse n eviden i pentru descoperirea lor vor trebui utilizate alte metode.

Deasemenea, n cazul unui volum mare de date, graficul poate deveni foarte aglomerat i greu de interpretat.

4.3.2 Analiza de coresponden simpl (ACS)

n cazul n care variabilele cu care lucrm nu sunt continue, ACP nu mai poate fi folosit direct. Pentru analiza relaiilor dintre dou variabile nominale se poate folosi ACS. Efectuarea acestei analize revine la aplicarea unor transformri datelor, urmate de efectuarea unei ACP.

Primul pas este construirea unui tabel de contingen. Dac X i Y sunt variabilele pe care le analizm, iar X are n modaliti i Y are p modaliti, tabelul de contingen K este o matrice cu n linii i p coloane, care conine pe poziia i, j numrul de indivizi care au simultan modalitatea i a variabilei X i modalitatea j a variabilei Y .

Prin mprirea tururor componentelor acestui tabel cu k = n p se obine un nou tabel notat cu F i numit tabelul frecvenelor relative. Vom nota cu suma elementelor de pe linia i a tabelului F i cu suma elementelor de pe coloana j a lui F.

Putem face acum o ACP pe acest tabel privind liniile ca pe nite indivizi i coloanele

ca pe nite variabile.

Metrica pe care o vom folosi trebuie s fie ns compatibil cu problema. Distana euclidian are dezavantajul c nu e stabil la agregarea liniilor (coloanelor). Din modul de construcie al tabelului pe care se face analiza e natural ca la combinarea prin adunare pe componente a dou coloane distana dintre oricare dou linii s nu se modifice, i analog i pentru tabelul transpus. Asta deoarece dac hotrm din motive independente de analiz s cumulm dou modaliti ale unei variabile, analiza nu trebuie s se schimbe, ntruct relaia dintre variabile nu este afectat.

O distan care are proprietatea de stabilitate la agregarea liniilor/coloanelor este distana . Prin definiie, distana dintre dou linii i i k este dat de relaia:

4.4 Exemplu de analiz ACP

Pentru a exemplifica aceast metod de analiz vom face un mic studiu asupra calitii vieii n Romnia. Datele se prezint sub forma unui tabel cu valori ale unor indicator

socio-economici la nivel de jude.

4.4.1 Prezentarea datelor

Indivizii sunt n numr de 43, reprezentnd cele 41 de judee ale rii, municipiul

Bucureti i media pe toat ara. Pentru a nu aglomera graficele, vom folosi denumiri prescurtate att pentru indivzi ct i pentru variabile. Pentru judee folosim prescurtrile de la numerele de nmatriculare auto, iar pentru variabile cte o prescurtare specific.

Avem 18 variabile, grupate natural:

Variabile demografice :

1. Gradul de urbanizare a populaie