4 Tehnologii pentru extragerea cunoştinţelor – Data Mining

4.1 În căutarea informaţiei ascunse

După mai multe decenii în cursul cărora mijloace şi tehnici informatice tot mai evoluate au contribuit la amplificarea capacităţii de memorare şi stocare a datelor, ultimii ani au marcat o reorientare semnificativă în utilizarea volumelor de date stocate, de la un proces de explorare retrospectivă spre unul cu caracter prospectiv. Această schimbare a devenit posibilă ca urmare a maturizării tehnologiilor legate de data mining.

Denumirea provine de la analogia cu activitatea minieră; tot aşa cum este necesară dislocarea şi rafinarea a tone de minereu pentru a obţine câteva grame de aur, aici sunt examinate şi analizate sute de mii sau milioane de date pentru a extrage din ele informaţii şi semnificaţii noi, dincolo de scopurile pentru care acestea au fost colectate şi memorate la origine.

Data mining are, ca şi alte concepte folosite în informatică, mai multe definiţii. În esenţă, acestea converg spre ideea formulată anterior: un proces de extragere de informaţii noi din colecţiile de date existente. Termenul de dată este utilizat aici cu semnificaţia de descriere a unui eveniment precis, produs în lumea reală şi verificabil prin raportare la aceasta. Informaţia (sau cunoaşterea transmisă) constituie descrierea unei categorii abstracte, ce acoperă mai multe evenimente sau exemple concrete.

Principiul de funcţionare în data mining este următorul: se prelucrează datele referitoare la perioadele trecute, examinând o varietate de situaţii care s-au produs şi ale căror rezultate sau consecinţe sunt deci, bine cunoscute, pentru a evidenţia caracteristicile acestora şi a permite elaborarea unui model. Odată construit, modelul poate fi aplicat situaţiilor noi de acelaşi tip.

Informaţiile obţinute prin data mining sunt de natură predictivă sau descriptivă.

Un exemplu tipic de problemă predictivă este direcţionarea acţiunilor de marketing. Datele rezultate din corespondenţa promoţională trecută se folosesc pentru a identifica destinatarii pentru care următoarea campanie promoţională poate aduce un maxim de efect.

Detectarea tranzacţiilor frauduloase cu carduri bancare constituie unul dintre exemplele tipice de aplicaţii descriptive. Explorarea ansamblului tranzacţiilor permite evidenţierea unui anumit tipar comportamental, considerat normal. Deîndată ce la un bancomat se cere efectuarea unei tranzacţii ce iese din acest tipar, solicitarea poate fi refuzată. Este posibil ca operaţia cerută să fie sau să nu fie frauduloasă; o analiză ulterioară poate stabili acest lucru dar, în acest stadiu, sistemul o respinge pentru a preveni orice consecinţe nedorite.

4.2 Fundamentele explorării datelor

1

Expansiunea tehnicilor de data mining se explică, printre altele, prin faptul că firmele au acumulat volume foarte mari de date, stocate pe suporturi informatice, privitoare la tranzacţii de diverse tipuri, derulate de-a lungul mai multor ani. Băncile posedă, spre exemplu, arhive de milioane de înregistrări, în care sunt consemnate în detaliu operaţiile efectuate de clienţii lor. În orice firmă se găsesc mii şi sute de mii de înregistrări privitoare la cumpărările, vânzările, încasările şi plăţile făcute. Societăţile de telefonie mobilă posedă date privitoare la fiecare convorbire efectuată de abonaţii lor, incluzând data, momentul şi locul apelului, numărul de telefon al corespondentului, durata convorbirii. Un magazin de tipul cash and carry posedă sute de mii de înregistrări, provenind de la casele de marcaj, în care figurează nu numai articolele cumpărate ci şi cumpărătorii, identificaţi prin legitimaţiile de acces. Multă vreme acestea s-au acumulat pur şi simplu în virtutea nevoii de arhivare. Creşterea permanentă a concurenţei, exigenţele din ce în ce mai mari ale pieţei au determinat firmele să devină conştiente de potenţialul pe care aceste arhive de date îl reprezintă. Toate exemplele enumerate au un element comun: vizează, în mod direct sau indirect, clienţii. Exploatarea lor din această perspectivă oferă oportunităţi deosebite. Datele sunt la dispoziţia organizaţiei respective; datele sunt cât se poate de precise şi analitice; datele sunt în volum mare şi acoperă perioade de timp de ordinul anilor. Dar relaţia cu clienţii nu este singura direcţie de re-utilizare a acestor date. În multe alte domenii ale activităţii de afaceri, tendinţele pe care acestea le încorporează sau le reflectă în mod obiectiv, structurile sau tiparele pe care le relevă sunt deosebit de valoroase.

Alături de existenţa colecţiilor de date istorice memorate pe suporturi informatice, încă doi factori explică emergenţa cunoscută actualmente de data mining: maturizarea algoritmilor şi a produselor program dedicate şi creşterea capacităţii de memorare şi prelucrare a calculatoarelor, care permite tratarea în corelaţie a volumelor foarte mari de date.

Unele dintre tehnicile de data mining datează de ceva mai mulţi ani. Algoritmii folosiţi au cunoscut însă un proces de evoluţie continuă, care a permis înlăturarea unora dintre limitele sau deficienţele iniţiale. Produsele program au evoluat şi ele spre o utilizare cât mai facilă, la un asemenea nivel încât pot fi folosite cu o cunoaştere minimă a tehnicii pe care o implementează. În sfârşit, au apărut firme care oferă spre vânzare colecţii de date istorice de uz general – cum ar fi, spre exemplu, evoluţia indicatorilor bursieri din ultimii 20 de ani - special constituite pentru asemenea utilizări.

Depozitele de date şi tehnologiile OLAP vizează şi ele datele colectate la nivelul organizaţiilor. În ciuda unor cerinţe şi prelucrări preliminare asemănătoare, există deosebiri esenţiale în privinţa demersului la care recurg fiecare dintre ele şi nu mai puţin, a obiectivelor urmărite. Nu este mai puţin adevărat că depozitele de date se pretează foarte bine ca surse pentru data mining iar rezultatele furnizate de acesta pot completa câmpurile înregistrărilor celor dintâi şi pot fi valorificate apoi prin proiecţiile multidimensionale specifice OLAP.

4.3 O explorare dirijată de oportunităţi

Potenţialul oferit de tehnicile de data mining trebuie încorporat în procesele comerciale curente ale organizaţiilor pentru a deveni realmente

2

utile. Căutarea de informaţii nu este un scop în sine; ea devine utilă doar în măsura în care se transpune în acţiune.

Declanşarea unui demers bazat pe data mining se face ca urmare a observării sau constatării unei necesităţi sau oportunităţi comerciale. Observarea diminuării numărului de clienţi, scăderea vânzărilor la un anumit produs, lansarea unui nou produs sau serviciu sunt câteva exemple de situaţii de acest tip. O firmă poate alege să reacţioneze sau nu la asemenea situaţii şi, în caz afirmativ, poate alege diverse moduri de a o face. Tehnicile de data mining constituie una dintre acestea. Totuşi, este de reţinut că fiecare dintre ele este adecvată unui anumit gen de probleme sau de circumstanţe şi că, de multe ori, aplicarea lor în combinaţie poate produce rezultatele cele mai bune. Alegerea trebuie să aibă în vedere şi compatibilitatea dintre cerinţele în materie de date ale tehnicii sau tehnicile alese şi cele de care se poate dispune realmente.

Pasul următor constă în explorarea propriu-zisă a datelor. La rândul său, acesta este departe de a fi simplu sau liniar. Multe dintre aceste tehnici solicită, înainte de a putea fi utilizate, un proces de învăţare; datele, fiind eterogene, impun o etapă de pregătire prealabilă; rezultatele sunt rareori aplicabile în forma în care sunt obţinute, cerând un efort suplimentar de interpretare şi adaptare, la care să participe şi decidentul, cu cunoştinţele şi experinţa sa în afaceri. Spre exemplu, aplicarea unui algoritm de grupare poate evidenţia existenţa a 20 de clustere diferite; dintre acestea, doar unul se poate dovedi util dar relevanţa lor nu poate fi apreciată decât de specialistul sau specialiştii din firmă.

Informaţiile obţinute anterior au valoarea acţiunilor întreprinse pe baza lor. Tehnicile de data mining permit obţinerea de cunoştinţe mai bogate privitoare la mediul în care există şi funcţionează întreprinderea. Acestea trebuie însă transformate în acţiune iar efectul acţiunilor măsurat.

Este posibil ca acţiunea de data minig să fie un eşec şi nu o reuşită. Este posibil ca măsurile întreprinse să nu fie cele mai adecvate în raport cu informaţiile obţinute. Atât reuşita cât şi eşecul pot fi sursă de învăţăminte pentru viitor, pot fi stimulii unor noi acţiuni de data mining, mai bine şi mai precis orientate şi derulate.

Toate aceste conturează ideea unui ciclu1 în utilizarea data mining, în cursul căruia se parcurg cele patru etape menţionate:

identificarea oportunităţii comerciale şi a datelor pe care se poate baza explorarea

extragerea de informaţii din colecţiile de date existente prin tehnici adecvate de data mining

adoptarea de decizii şi întreprinderea de acţiuni pe baza informaţiilor obţinute

măsurarea rezultatelor concrete pentru a identifica şi alte modalităţi de exploatare a datelor disponibile

1 M.J.A. Berry, C. Linoff, Data Mining -Techniques appliquée au marketing, à la vente et aux services clients, Masson, InterEditions, 1997

3

Figura 4-1. Ciclul de utilizare a data mining

4.4 Verificarea ipotezelor şi căutarea cunoştinţelor

Aplicarea tehnicilor de data mining poate fi făcută din perspectiva unui demers ascendent sau descendent.

În abordarea descendentă, efortul este orientat spre confirmarea sau infirmarea unor idei (ipoteze) formulate în prealabil prin alte mijloace. Un demers asemănător se aplică în statistică şi în analiza datelor, dar folosind alte tehnici şi metode.

Figura 4-2. Utilizări ale tehnicilor de data mining

Abordarea ascendentă are o cu totul altă finalitate; ea urmăreşte extragerea de cunoştinţe sau informaţii noi din datele disponibile. Căutarea poate fi dirijată sau nedirijată2.

2 M.J.A. Berry, C. Linoff, op. cit.

4

Decizie şi acţiune

Data mining

Oportunitate de afaceri

Evaluare rezultate

Data mining

verificarea ipotezelor

căutarea de cunoştinţe

dirijată nedirijată

Căutarea dirijată ia în considerare un atribut sau un câmp, ale cărui valori încearcă să le explice prin celelalte câmpuri. Este cea mai folosită în practică.

Căutarea nedirijată are ca scop identificarea relaţiilor sau structurilor existente în ansamblul datelor examinate, fără a acorda prioritate unui câmp sau altul. Deşi mai spectaculoasă, în practică se recurge mult mai puţin la ea decât la căutarea dirijată.

4.5 Tehnici şi acţiuni

Ceea ce se exploatează prin data mining sunt colecţiile de date de care dispune o organizaţie, colecţii care au fost însă constituite pentru alte scopuri; în cazurile cele mai frecvente, este vorba de datele privitoare la tranzacţiile derulate într-o anumită perioadă de timp: comenzi, livrări, plăţi, încasări etc. La acestea se adaugă, deseori, date provenite din alte surse, cum ar fi, spre exemplu, statistici oficiale privitoare la evoluţia economiei în ansamblu, date privitoare la concurenţă, diverse măsuri legislative sau normative etc. Aceasta explică utilizarea frecventă a calificativului de informaţii ascunse: volumul mare sau foarte mare şi faptul că structura şi conţinutul lor sunt edificate în perspectiva altor finalităţi, fac foarte dificilă sau imposibilă detectarea corelaţiilor sau raporturilor de ansamblu pe care le încorporează în mod intrinsec.

Rezultatele sunt cu atât mai sigure şi relevante, cu cât se bazează pe un volum mai mare de date, din motive lesne de înţeles: o tendinţă relevată de un număr foarte mare de cazuri practice este mult mai pertinentă decât cea dedusă din doar câteva situaţii.

Explorarea datelor în vederea obţinerii de informaţii recurge la diverse tehnici, printre cele mai folosite aflându-se:

reţelele neuronale arborii de decizie algoritmii genetici analiza grupurilor raţionamentele bazate pe cazuri analiza legăturilor

La acestea se pot asocia şi tehnici statistice, cum sunt, spre exemplu, regresiile, analiza factorială etc.

Data mining nu este un panaceu universal, capabil să rezolve orice problemă de gestiune. În fapt, aportul său se rezumă la un număr limitat de acţiuni: clasificarea, estimarea, predicţia, gruparea, analiza grupărilor, dar care, folosite în mod adecvat, se pot dovedi extrem de utile pentru numeroase probleme şi situaţii din domeniul decizional.

Clasificarea urmăreşte să plaseze obiectele prelucrate într-un grup limitat de clase predefinite. Spre exemplu, o cerere de credit va fi încadrată, prin clasificare, în una dintre următoarele categorii de risc: scăzut, mediu, ridicat. Obiectele clasificate sunt reprezentate, în general, sub formă de înregistrări, compuse din atribute sau câmpuri. Dintre tehnicile de data mining, cele mai adecvate clasificării sunt arborii de decizie şi raţionamentul bazat pe cazuri.

Estimarea urmăreşte să atribuie o valoare unei variabile, pe baza celorlalte date de intrare. Prin intermediul său se poate aprecia, de exemplu,

5

numărul de copii sau venitul total al unei familii. Rezultatele obţinute prin estimare sunt valori continue. Reţelele neuronale sunt printre cele mai bune tehnici de data mining pentru acest gen de prelucrări.

Predicţia urmăreşte să claseze înregistrările tratate în funcţie de un comportament sau o valoare estimată viitoare. În acest scop, se recurge la o colecţie de exemple, bazate pe date din trecut, în care valorile variabilei de previzionat sunt deja cunoscute. Cu ajutorul acestora se construieşte un model care să explice comportamentul observat. Aplicând acest model asupra înregistrărilor de prelucrat, se obţine o predicţie a comportamentului sau valorilor acestora în viitor. Cu condiţia folosirii unui set adecvat de exemple trecute, toate tehnicile de clasificare sau estimare pot fi folosite şi pentru predicţii.

Gruparea urmăreşte să determine care sunt obiectele care apar cel mai frecvent împreună. Exemplul tipic pentru acest gen de acţiune este determinarea mărfurilor care se cumpără uzual împreună, de unde şi denumirea de “analiză a coşului gospodinei”.

Analiza grupurilor urmăreşte să dividă o populaţie eterogenă în grupuri mai omogene, numite “cluster”. Spre deosebire de celelalte tipuri de acţiuni asemănătoare, aici nu există un set predeterminat de clase ca în cazul clasificării şi nici exemple trecute. Segmentarea se face în exclusivitate pe baza similitudinilor sesizate între obiecte.

4.6 Etapele procesului de explorare a datelor

Existenţa programelor pentru implementarea algoritmilor specifici tehnicilor de data mining este indispensabilă dar insuficientă. În amonte, programele trebuie alimentate cu date. Cum datele disponibile provin din surse variate şi au fost, la origine, organizate şi constituite pentru a răspunde altor scopuri, este necesară o fază de pregătire prealabilă, de curăţare şi uniformizare. În aval, rezultatele nu pot fi folosite în forma în care sunt furnizate de către programele respective; conţinutul lor trebuie analizat şi interpretat de către specialişti pentru a identifica informaţiile pertinente pe care le conţin. Nu este mai puţin importantă selecţia tehnicilor adecvate naturii problemei vizate. Este evident, prin urmare, că tehnicile de data mining se pot utiliza numai în cadrul unor procese specifice, relativ complexe şi deseori neliniare. În cadrul acestora, se pot distinge următoarele etape:

definirea problemei identificarea surselor de date colectarea şi selectarea datelor pregătirea datelor construirea modelului evaluarea modelului integrarea modelului

Definirea problemei

Aşa cum s-a precizat anterior, declanşarea procesului este determinată de sesizarea unei oportunităţi sau necesităţi de afaceri. În cadrul acesteia,

6

este nevoie să se delimiteze exact ce urmează a fi rezolvat prin data mining, care sunt obiectivele urmărite şi rezultatele aşteptate.

Problema de rezolvat prin data mining contribuie, ca parte componentă, la valorificarea oportunităţii sesizate de întreprindere, dar nu se identifică cu ea. În plus, trebuie să primească o formă în care să poată fi tratată prin aceste tehnici. Spre exemplu, iniţiativa unei companii de telefonie mobilă de a testa pe piaţă un nou produs, ca oportunitate, este mult prea complexă şi prea generală. Cum este vorba despre o testare, oferta va fi adresată doar câtorva sute dintre zecile de mii de abonaţi. Care dintre clienţii actuali ai companiei ar putea fi cei mai interesaţi de noul serviciu şi a căror apreciere ar fi deci cea mai pertinentă ? Abia aceasta este o problemă de data mining.

Identificarea surselor de date

Odată problema definită, este necesară stabilirea structurii generale a datelor necesare rezolvării sale şi a regulilor de constituire a acestora. Urmează localizarea surselor acestora. În cazurile cele mai frecvente, este vorba de date dispersate în diverse sisteme informaatice operaţionale, stocate în formate diferite, administrate cu produse software diferite, uneori disponibile numai pe hârtie. Înainte de a trece la etapa următoare, este recomandabilă examinarea conţinutului fiecăreia dintre surse, pentru o familiarizare cu conţinutul său şi pentru identificarea, cât mai precoce, a eventualelor incoerenţe sau probleme de definire, care pot compromite rezultatele analizelor următoare.

Colectarea şi selecţia datelor

Această etapă urmăreşte extragerea şi plasarea într-o bază comună a tuturor datelor ce urmează a fi folosite. Este o muncă relativ anostă, care ocupă până la 80% din timpul global consumat. Existenţa depozitelor de date constituie un avantaj major.

Una dintre problemele de rezolvat în acestă fază constă în alegerea între prelucrarea întregului fond de date disponibil sau a unui eşantion. Limitele echipamentelor şi a produselor program utilizate, bugetul alocat proiectului, cerinţele şi particularităţile studiului sunt factorii care intervin în această alegere. În cazul opţiunii pentru lucrul cu eşantioane, vor fi respectate toate regulile şi cerinţele de constituire a acestora.

Pregătirea datelor

Datele selectate în faza anterioară au fost, în marea majoritate a cazurilor, culese şi stocate în cu totul alte scopuri. În consecinţă, trebuie supuse unui proces preliminar de pregătire înainte de a putea fi supuse extracţiei prin data mining. Alături de cerinţele specifice fiecăreia dintre tehnici, care vor fi prezentate în paragrafele următoare, există o serie de transformări comune care vizează:

valorile extreme sau aberante valorile lipsă valorile de tip text rezumarea

7

codificarea incoerentă arhitecturile informatice incompatibile

Tratarea valorilor extreme sau aberante se poate face prin mai multe tehnici: încadrarea între limitele cuprinse între medie şi un anumit număr de abateri standard prin excludere sau plafonare, izolarea vârfurilor, etc. Tratarea acestor valori trebuie făcută totuşi cu mult discernământ deoarece în unele cazuri ele sunt cele care pot evidenţia anumite trăsături relevante.

Valorile lipsă pot ridica probleme în funcţionarea unor algoritmi de data mining. Şi în acest caz, există mai multe acţiuni posibile: eliminarea înregistrărilor având câmpuri cu valori nule, completarea datelor omise cu valori medii, cu valoarea cea mai frecventă sau cu valori calculate după alte relaţii sau gestionarea distinctă a acestora prin înlocuirea cu constante predeterminate.

Valorile de tip text ridică numeroase dificultăţi. Aceleaşi cuvinte separate de un număr diferit de spaţii reprezintă, în calculator, valori diferite. Chiar notaţii cu structură riguros definită, cum sunt numerele de înmatriculare auto, pot genera asemenea probleme. Din această cauză este preferabilă excluderea acestui tip de variabile. Dacă prelucrarea lor nu poate fi totuşi evitată, soluţia cea mai sigură constă în codificarea prin tabele de corespondenţe, în care să figureze toate şirurile valide de caractere.

Rezumarea se poate aplica atunci când detaliile conţinute în date sunt nesemnificative pentru rezolvarea problemei abordate, atunci când numărul de exemple analitice este insuficient sau atunci când datele sunt prea numeroase în raport cu capacităţile de prelucrare.

Codificarea incoerentă apare în cazurile în care obiecte identice sunt reprezentate diferit în unele dintre sursele folosite. Spre exemplu, acelaşi partener al firmei este referit prin coduri diferite în calitate de furnizor şi de client. Dacă nu sunt compensate, aceste diferenţe pot conduce la rezultate şi concluzii eronate. Aceaşi situaţie poate apare în cazul utilizării abrevierilor curente, în care abateri minime de ortografiere conduc la interpretarea lor drept elemente diferite.

Incompatibilităţile arhitecturale informatice vizează, în principal, diferenţele în modul de reprezentare internă a valorilor, mai ales atunci când este vorba despre date create cu sisteme din generaţii diferite.

Pentru multe dintre problemele de genul celor amintite, există programe specializate; de asemenea, numeroase produse program de data mining includ în mod implicit funcţii de pregătore a datelor. Din păcate, acestea nu izbutesc să răspundă tuturor cerinţelor şi solicită adesea intervenţii punctuale suplimentare.

Construirea modelului

Aceasta este etapa care se apropie cel mai mult de semnificaţia termenului de data mining. Având în vedere că întregul proces a fost dirijat de o anumită perspectivă de rezolvare, în care s-au făcut opţiuni privitoare la acţiunile de întreprins pentru explorarea datelor, la structura şi la conţinutul acestora, etapa se rezumă, în esenţă, la crearea modelului informatic care va efectua explorarea propriu-zisă.

Demersul aplicat influenţează considerabil această etapă, iar uneori şi etapele precedente.

8

În cazul căutării de informaţii, dirijate sau nu, construirea modelului este acompaniată de o fază de instruire, de învăţare. Detaliile acesteia depind de tehnica de data mining folosită. Dar pentru toate se parcurg două momente distincte: al învăţării şi al testării.

Învăţarea se bazează pe un ansamblu de exemple complete, pornind de la care sunt identificate relaţiile care leagă între ele valorile câmpurilor sau atributelor. Procesul de învăţare se încheie atunci cînd rezultatele furnizate de model se apropie suficient de mult de soluţiile conţinute de datele după care s-a învăţat. Nu există însă certitudinea că modelul se va comporta la fel de bine şi în alte situaţii. Din acest motiv, este supus testării cu date diferite de cele folosite pentru învăţare, dar aparţinând aceleiaşi populaţii. Urmează, dacă este necesar, o fază de reajustare necesară pentru a-l face să furnizeze rezultate bune şi în raport cu datele de test. Doar după încheierea acesteia, modelul poate fi considerat terminat. Aceasta va adăuga la etapele anterioare două sarcini suplimentare: obţinerea de date preclasate şi distribuirea acestora, după colectare şi pregătire, în trei seturi: de învăţare, de testare şi de evaluare.

Obţinerea de explicaţii privitoare la modul în care un atribut variază în funcţie de conţinutul altor atribute presupune ca înregistrările de date să includă valori pentru toate aceste câmpuri luate împreună şi să reflecte toate cazurile cunoscute cu un număr cît mai mare de exemple. Căutând, spre exemplu, clienţii care prezintă riscuri în privinţa capacităţii de rambursare a împrumuturilor, va fi nevoie ca datele colectate să marcheze clar acest aspect. În caz contrar, informaţiile obţinute nu vor putea fi utilizate pentru a face ulterior predicţii pe baza lor.

Odată datele preclasate colectate, este necesară divizarea lor în cele trei părţi. Acestea se crează din acelaşi fişier dar conţin înregistrări diferite. În general, 70-80% din înregistrări sunt alocate învăţării, restul rămânând pentru testare sau fiind împărţit egal între aceasta şi evaluare.

Figura 4-3. Schema procesului de creare a modelelor de căutare a informaţiilor

După depăşirea momentului căruia îi este destinată, fiecare dintre acestea devine inutilizabilă, deoarece nu mai poate aduce nici o ameliorare modelului.

9

Date de învăţare

Date de test

Date de evaluare

Model utilizabil

Datele colectate

Evaluarea modelului

Evaluarea are scopul de a stabili capacitatea modelului de a determina corect valorile pentru cazuri noi. Pentru aceasta, va fi aplicat asupra ultimei părţi a datelor preclasate disponibile, reţinute pentru evaluare. Procentul de eroare înregistrat cu acestea poate fi acceptat ca valoare valabilă şi pentru datele noi. În general, performanţele unui model se apreciază cu ajutorul unei „matrice de confuzie”, care compară situaţia reală cu cea furnizată de acesta. Calitatea globală se exprimă prin raportul dintre numărul de predicţii exacte şi numărul total de predicţii.

Integrarea modelului

Această etapă finalizează procesul, prin includerea modelului obţinut într-un SIAD, al cărui „inimă” va deveni, sau prin integrarea sa într-un proces decizional mai general din întreprindere.

Două observaţii finale se impun aici. Orice model are o durată de viaţă limitată. Cum construcţia sa se

face pe baza corelaţiilor semnalate în datele existente la un moment dat, schimbările survenite ulterior nu mai pot fi luate în considerare. Deşi durata de valabilitate în timp poate fi forate diferită de la un tip de model la altul, unele putând fi folosite fără schimbări timp de mai mulţi ani, observaţia anterioră rămâne strict valabilă: modelele trebuie actualizate permanent, pentru a putea urmările schimbările survenite în domeniul la care se referă.

Rezolvarea unei probleme se obţine prin combinarea mai multor tehnici. În faţa diversităţii factorilor ce acţionează în realitatea economico-socială actuală, aplicarea unei singure tehnici de data mining poate conduce la rezultate nesemnificative sau la o lipsă completă de rezultate. Combinarea tehnicilor permite obţinerea unei viziuni mai largi şi mai diversificate, cu implicaţii lesne de întrevăzut asupra actului decizional, chiar dacă acest lucru este mai costisitor.

10

4.7 Raţionamentul bazat pe cazuri

Raţionamentul bazat pe cazuri caută răspunsurile la problemele noi în experienţele acumulate în trecut. În faţa unei situaţii noi, vor fi căutate cazurile asemănătoare cunoscute iar concluziile acestora vor fi aplicate şi în noua situaţie. Metoda este aplicabilă atât pentru clasificări cât şi pentru predicţii şi oferă un bun răspuns, pragmatic şi evolutiv, pentru o mare diversitate de probleme.

Cazurile pe care se bazează raţionamentul sunt memorate sub formă de înregistrări. Înregistrarea este compusă din setul de atribute care descriu fiecare caz în parte. Cazul nou este şi el reprezentat ca o înregistrare, în care unul dintre câmpuri – cel al cărui valoare trebuie determinată – este vid. Pentru aflarea sa, se caută înregistrările cu care acesta seamănă cel mai mult – vecinele - şi conţinutul acestora este folosit pentru a produce un răspuns. Există prin urmare, două funcţii de prelucrare fundamentale:

măsurarea distanţei dintre membrii fiecărui cuplu de înregistrări, pentru a putea afla vecinele cele mai apropiate

combinarea rezultatelor furnizate de vecine în răspunsul propus pentru cazul curent.

Măsurarea distanţei dintre câmpuri

Distanţa este expresia modului în care se evaluează similitudinea. Proprietăţile sale esenţiale în raport cu acest scop sunt următoarele:

poate fi întotdeauna definită şi are forma unui număr real cu valori mai mari sau egale cu zero;

distanţa de la un element la el însăşi este întotdeauna nulă; sensul măsurării nu are importanţă: distanţa de la elementul A la

elementul B este egală cu distanţa de la B la A; nu poate exista niciodată un punct intermediar C prin a cărui

parcurgere să se scurteze distanţa dintre A şi B.

Cele mai utilizate moduri de calcul al distanţei pentru câmpurile numerice sunt:

diferenţa în valoare absolută A-B pătratul diferenţei (A-B)2

diferenţa în valoare absolută normalizată A-B/(diferenţa maximă)

Ultima variantă are avantajul de a produce rezultate cu valori cuprinse întotdeauna între 0 şi 1.

Pentru exemplificare, tabelul următor prezintă înregistrările aferente unui număr de 5 clienţi ai unei bănci comerciale, cărora li se virează salariul în conturi de card.

Distanţele dintre clienţi pentru atributele vârstă şi venit, calculate în valori normalizate, sunt prezentate în următoarele două tabele.

Vârstă Stare civilă Venit

11

1 52 celibatar 5.400.0002 46 căsătorit 4.800.0003 48 căsătorit 4.900.0004 38 divorţat 3.100.0005 24 celibatar 2.800.000

Tabelul 4-1. Datele privitoare la cinci clienţi ai băncii

52 46 48 38 2452 0,00 0,21 0,14 0,50 1,0046 0,21 0,00 0,07 0,29 0,7948 0,14 0,07 0,00 0,36 0,8638 0,50 0,29 0,36 0,00 0,5024 1,00 0,79 0,86 0,50 0,00

Tabelul 4-2. Matricea distanţelor între clienţi în funcţie de vârstă

5.400.000 4.800.000 4.900.000 3.100.000 2.800.0005.400.000 0,00 0,23 0,19 0,88 1,004.800.000 0,23 0,00 0,04 0,65 0,774.900.000 0,19 0,04 0,00 0,69 0,813.100.000 0,88 0,65 0,69 0,00 0,122.800.000 1,00 0,77 0,81 0,12 0,00

Tabelul 4-3. Matricea distanţelor între clienţi în funcţie de venituri

Calcularea distanţei pentru datele nenumerice se poate face prin funcţii particulare, adaptate problemei de rezolvat. Spre exemplu, pentru un câmp reprezentând starea civilă, se poate recurge la următoarea funcţie, în care identitatea valorilor câmpului din cele două înregistrări este notată cu 0 iar deosebirea cu 1 :

D(celibatar, celibatar) = 0D(celibatar, căsătorit) = 1D(celibatar, văduv) = 1D(căsătorit, căsătorit) = 0D(căsătorit, divorţat) = 1 …

celibatar casatorit casatorit divortat celibatarcelibatar 0 1 1 1 0casatorit 1 0 0 1 1casatorit 1 0 0 1 1divortat 1 1 1 0 1celibatar 0 1 1 1 0

Tabelul 4-4. Matricea distanţelor pentru starea civilă

Uneori, valorile câmpurilor implicate conţin expresii ascunse ale distanţei. Numerele de înmatriculare auto pot indica, spre exemplu, localizarea geografică a domiciliului posesorului său şi permit astfel efectuarea de clasificări. Codurile poştale şi numerele de telefon constituie

12

alte exemple de valori ce pot fi exploatate prin funcţii adecvate în scopul ierarhizării sau grupării înregistrărilor.

Măsurarea distanţei dintre înregistrări

Funcţiile menţionate anterior servesc pentru evaluarea distanţei pentru un anumit câmp. În cazurile în care este necesară considerarea simultană a mai multor câmpuri ale înregistrării, se calculează distanţa pentru fiecare câmp în parte iar rezultatul se combină într-o valoare unică, care exprimă distanţa înregistrării respective. Cele mai utilizate procedee de combinare a distanţelor câmpurilor sunt:

însumarea însumarea normalizată (suma distanţelor / suma maximă) distanţa euclidiană (rădăcina pătrată din suma pătratelor

distanţelor).Figura următoare prezintă distanţele dintre înregistrări, calculate

conform acestor trei procedee.

Însumare1 2 3 4 5

1 0,00 1,45 1,34 2,38 2,002 1,45 0,00 0,11 1,94 2,553 1,34 0,11 0,00 2,05 2,664 2,38 1,94 2,05 0,00 1,625 2,00 2,55 2,66 1,62 0,00

Însumare normalizată1 2 3 4 5

1 0,00 0,54 0,50 0,89 0,752 0,54 0,00 0,04 0,73 0,963 0,50 0,04 0,00 0,77 1,004 0,89 0,73 0,77 0,00 0,615 0,75 0,96 1,00 0,61 0,00

Distanţă euclidiană1 2 3 4 5

1 0,00 1,05 1,03 1,43 1,412 1,05 0,00 0,08 1,23 1,493 1,03 0,08 0,00 1,27 1,554 1,43 1,23 1,27 0,00 1,125 1,41 1,49 1,55 1,12 0,00

Tabelul 4-5. Matrici ale distanţelor dintre înregistrări

Pentru aceleaşi înregistrări, aplicarea acestor procedee poate conduce la vecinătăţi diferite. Distanţa euclidiană este cea care evidenţiază cel mai pregnant înregistrările pentru care toate câmpurile sunt vecine; celelalte două metode pot masca discrepanţa unor câmpuri compensată prin marea apropiere a altor câmpuri.

În oricare dintre metodele anterioare poate fi introdus un coeficient care să exprime importanţa "subiectivă" acordată câmpurilor în calcularea distanţei.

13

Obţinerea rezultatului

Aflarea celor mai apropiaţi vecini este doar primul pas: soluţia problemei se obţine prin combinarea răspunsurilor oferite de aceştia. Cum fiecare poate avea variante de răspuns diferite, demersul cel mai firesc este acela de a cere celor mai apropiaţi vecini să voteze. Rezultatul care obţine majoritatea va fi cel atribuit cazului curent. O cerinţă minimală este ca numărul votanţilor să fie impar, pentru a evita situaţiile de indeterminare (balotaj).

Pentru ilustrare, s-a considerat cazul unui nou client, ale cărui caracteristici sunt:

Vârstă Stare civilă Venit34 celibatar 4.200.000

Distanţele corespunzătoare celor trei atribute şi distanţa faţă de celelalte înregistrări, sunt cuprinse în tabelul următor.

Vârsta52 46 48 38 24

34 0,64 0,43 0,50 0,14 0,36

Venit5.400.000 4.800.000 4.900.000 3.100.000 2.800.000

4.200.000 0,46 0,23 0,27 0,42 0,54

Starea civilăcelibatar casatorit casatorit divortat celibatar

celibatar 0 1 1 1 0

Tabelul 4-6. Distanţele atributelor aferente noii înregistrări

1 2 3 4 5 6 Vecini6 1,10 1,66 1,77 1,57 0,90 0,00 5;1;4;2;3

Tabelul 4-7. Poziţia noii înregistrări faţă de cele existente. Vecinele sunt prezentate în ordinea descrescătoare a apropierii de aceasta.

Banca este interesată în constituirea de depozite la termen pentru clienţii ale căror salarii sunt virate în conturi de card. Situaţia actuală se prezintă astfel:

Vârstă Stare civilă Venit Depozit1 52 celibatar 5.400.000 nu2 46 casatorit 4.800.000 da3 48 casatorit 4.900.000 nu4 38 divortat 3.100.000 da5 24 celibatar 2.800.000 nu6 34 celibatar 4.200.000

14

Noul client va deschide sau nu un depozit ?. Răspunsul, obţinut prin votul celor mai apropiaţi vecini este următorul:

Rezultat

Vecinii în ordinea

apropieriiDepozite la

termen deschise 1 votant 2 votanţi 3 votanţi 4 votanţi5;1;4;2;3 n;n;d;d;n nu nu nu ?

Rezultatul final poate fi semnificativ influenţat de numărul de votanţi. Din acest motiv, este recomandabilă încorporarea unui indicator care să exprime procentul celor care au votat pentru rezultatul reţinut din totalul votanţilor.

1 votant 2 votanţi 3 votanţi 4 votanţinu nu nu ?

100% 100% 67% 50%

În locul votului simplu, se poate apela la un vot ponderat, în care greutatea răspunsului fiecărui vecin este invers proporţională cu distanţa acestuia faţă de cazul curent. Votul vecinilor mai apropiaţi devine astfel mai important decât al celor aflaţi la o distanţă ceva mai mare.

Metodele bazate pe vot dau bune rezultate în situaţiile în care răspunsurile căutate sunt de tip enumerativ. Dacă este necesară însă obţinerea de rezultate cu valori continue, acestea trebuie stabilite altfel. O posibilă soluţie o reprezintă interpolarea valorilor înregistrărilor vecine. Interpolarea introduce însă o aplatizare a rezultatelor, care se înscriu inevitabil între cel două limite folosite în calcul. Rezultate mult mai bune se obţin prin metode de regresie statistică, aplicate asupra valorilor furnizate de vecinii cei mai apropiaţi. Ecuaţia dreptei sau curbei astfel obţinute permite calcularea mult mai precisă a valorilor aferente cazului curent.

Avantaje şi limite ale raţionamentului bazat pe cazuri

Raţionamentul bazat pe cazuri este o tehnică de data mining deosebit de puternică. Există un număr mare de probleme în care aplicarea demersului său specific poate conduce la soluţii. O fraudă nouă va fi, foarte probabil, asemănătoare celor deja cunoscute; prin această tehnică ea poate fi identificată şi marcată, în vederea unei examinări ulterioare mai amănunţite. În faţa unei acţiuni de promovare de produse, un client va avea, foarte probabil, un comportament asemănător celui manifestat faţă de campaniile de marketing anterioare; prin această metodă pot fi identificaţi cei la care acţiunea respectivă poate conduce la cele mai bune rezultate. Şi enumerarea aceasta poate continua.

Calitatea rezultatelor depinde direct de volumul de date pe care se bazează. O modalitate de estimare a calităţii acestuia constă în aplicarea tehnicii asupra propriilor date de învăţare. Dacă o anumită situaţie, supusă votului unui set de testare format din doi, trei şi apoi patru vecini, conduce la

15

rezultate discordate sau ambigui, înseamnă că numărul înregistrărilor pe care se bazează raţionamentul este prea mic.

Printre avantajele raţionamentului bazat pe cazuri se pot enumera: poate fi aplicat pentru o mare diversitate de tipuri de date,

inclusiv pentru structurile de date complexe, cum sunt, spre exemplu imaginile, ale căror tratare este mult mai dificilă cu alte tehnici. Câmpurile de tip text sunt, de asemenea, mai uşor de tratat decât în alte tehnici.

pot fi luate în considerare oricât de multe câmpuri, spre deosebire de alte tehnici la care numărul acestora este limitat (uneori chiar foarte drastic).

rezultatele furnizate sunt explicite; sistemul ajunge la o anumită concluzie în virtutea apropierii sau similitudinii cazului tratat cu alte cazuri produse în trecut.

elementele noi survenite în datele de învăţare sunt uşor încorporate şi folosite în raţionamente, spre deosebire de alte tehnici pentru care asemenea schimbări presupun reluarea întregului proces de “învăţare”.

Principalele dezavantaje constau în volumul mare de memorie şi în timpii importanţi de prelucrare necesari pentru aplicarea funcţiilor de distanţă asupra tuturor înregistrărilor şi câmpurilor ce participă la aflarea soluţiei.

În concluzie, raţionamentul bazat pe cazuri constituie o tehnică puternică, foarte adecvată situaţiilor în care sunt necesare clasificări sau predicţii fundamentate pe corelaţii cu caracter local.

4.8 Analiza grupurilor (clustering)

Această tehnică permite identificarea automată a grupurilor existente în ansamblul datelor analizate, fiind una dintre puţinele ce pot fi aplicate în căutarea nedirijată a informaţiilor. Grupurile – denimite în engleză clusters – rezultă automat în urma procesului de prelucrare, fără a avea ca punct de pornire un anumit criteriu sau proprietate. Este o tehnică ce are capacitatea de a releva realmente caracteristici ascunse – sub volumul şi diversitatea detaliilor – într-un anumit set de înregistrări. Grupurile astfel definite pot fi sau nu semnificative; având în vedere că procesul este automat şi nedirijat, există întotdeauna riscul de a obţine rezultate nerelevante. Totuşi, numeroase aplicaţii ale acestei tehnici au permis descoperirea unor elemente noi în variate domenii de activitate, ceea ce explică interesul de care se bucură.

Detecţia grupurilor prin divizare

Metoda celor k-medii este una dintre cele mai folosite în practică pentru detecţia de grupuri. Ideea pe care se bazează este aceea de a căuta, prin mai multe iteraţii succesive, acele k puncte care formează punctele centrale ale grupărilor formate de înregistrări în funcţie de poziţia pe care o ocupă unele faţă de altele. Considerând, pentru exemplificare, că se prelucrează înregistrări care au numai două câmpuri, acestea pot plasate într-un spaţiu

16

plan, valorile celor două atribute fiind coordonatele punctului corespunzător înregistrării respective. Deoarece nu există un criteriu predeterminat de grupare, în primul pas se stabilesc aleator k puncte drept centre de grupare. Algoritmul prevede alegerea în acest scop a primelor k înregistrări dacă acestea sunt complet neordonate sau a înregistrărilor aflate la distanţe relativ egale dacă există o relaţie de ordonare. Odată aceste puncte alese, se trasează frontiere echidistante între ele şi celelalte înregistrări sunt grupate în funcţie de poziţia pe care o au faţă de aceste frontiere. După această distribuire iniţială, se execută mai multe iteraţii, în cursul cărora centrele grupurilor şi componenţa lor se rafinează. Prelucrările efectuate într-o asemenea iteraţie constau în calcularea coordonatelor centrale ale fiecărui grup delimitat în iteraţia anterioară, ca medie a coordonatelor corespunzătoare ale tuturor înregistrărilor alocate grupului respectiv. Spre exemplu, lucrând în două coordonate x1, x2, se va calcula, pur şi simplu, media valorilor x1 ale tuturor înregistrărilor din grup şi media valorilor x2, rezultatele constituind coordonatele x1 şi x2 ale noului centru. După găsirea acestor noi cluster-e, înregistrările sunt din nou distribuite, fiecare fiind asociată cluster-ului celui mai apropiat. Procesul se încheie atunci când se ajunge la o configuraţie în care noile iteraţii nu mai conduc la schimbări ale frontierelor. Demersul descris poate fi aplicat nu numai pentru două dimensiuni, ci pentru oricât de multe, folosind un număr corespunzător de coordonate.

Mărimea lui kFixând pe k la o anumită valoare, există şanse să se găsească k clustere.

Dar nimic nu atestă că ansamblul iniţial conţine doar atâtea grupuri; este foarte posibil să existe şi altele, perfect individualizabile, care ar fi fost descoperite dacă s-ar fi ales o mărime diferită pentru k. Prin urmare, pentru a obţine rezultate cât mai bune, este necesar ca, pentru aceleaşi date, să se aplice în mod repetat algoritmul de grupare, pentru valori diferite ale lui k. După fiecare asemenea prelucrare, se poate face o evaluare a consistenţei cluster-elor găsite, comparând distanţa medie a înregistrărilor aflate în interiorul unui cluster cu distanţa dintre cluster-e. Având în vedere că proprietatea esenţială urmărită este aceea de a avea în interiorul unui cluster înregistrări cât mai apropiate, se poate recurge la calcularea varianţei - suma pătratelor diferenţelor fiecărui element în raport cu media. Varianta cea mai bună este cea care conduce la cluster-e cu varianţă minimală.

Există şi un criteriu de evaluare subiectivă, bazat pe estimarea utilităţii cluster-elor. Este foarte posibil ca algoritmul să identifice un anumit număr de cluster-e, bine delimitate din punct de vedere formal, dar nesemnificative în spaţiul problemei sau activităţii vizate.

De la înregistrări la coordonate

Una dintre dificultăţile întâlnite în aplicarea acestei tehnici constă în găsirea modalităţii de exprimare a valorilor luate de atributele înregistrărilor, astfel încât măsurarea apropierii pe care se bazează repartizarea lor în grupuri să fie relevantă. Alături de problemele ridicate de reprezentarea numerică a datelor, care pot fi de diferite tipuri, inclusiv text, apare şi aspectul, mult mai delicat, al stabilirii acestor mărimi astfel încât să adopte

17

un comportament adecvat cerinţelor utilizării lor drept coordonate poziţionale. Dincolo de mărimi cum sunt lungimea, volumul sau greutatea, care exprimă măsuri propriu-zise, altele, chiar numerice fiind, pot ridica dificultăţi în momentul utilizării drept coordonate. Spre exemplu, se poate calcula diferenţa dintre două temperaturi dar nu se poate afirma că într-o zi în care s-au atins 32º C a fost de două ori mai cald decât într-o zi cu 16º C.

O altă dificultate vine din faptul că dimensiunile luate în considerare pot să nu aibă aceeaşi importanţă pentru problema tratată: o variaţie minimă a unei variabile poate fi mult mai importantă decât variaţii de zeci de ori mai mari ale altora. Cum importanţa acestora este, din punct de vedere geometric egală, trebuie găsită modalitatea de a exprima şi nivelul de semnificaţie al unei variabile, prin poziţia sa pe axa care o reprezintă în modelul geometric.

În principiu, orice funcţie care asociază la două puncte o valoare unică prin care se exprimă o relaţie dintre acestea poate fi folosită pentru măsurarea distanţei; totuşi, aceasta este pe deplin corespunzătoare dacă posedă cele patru proprietăţi menţionate la raţionamentul bazat pe cazuri.

În cazul în care se lucrează cu măsuri sau cu intervale, se poate considera că fiecare înregistrare este un punct în spaţiu, ale cărui coordonate sunt exprimate de vectorul format de valorile câmpurilor sale. Pentru a măsura apropierea dintre ele se pot folosi diverse metode, dintre care cea mai utilizată se bazează pe distanţa euclidiană. Aceasta se determină calculând pătratele diferenţelor dintre fiecare pereche de coordonate ale celor două puncte comparate şi extrăgând apoi rădăcina pătrată din suma acestora.

Uneori, comparaţiile directe sunt irelevante. Apropierea este exprimată de similitudinea raporturilor sau corelaţiilor dintre valorile câmpurilor înregistrărilor şi nu de mărimea lor absolută. Una dintre soluţiile preferate în asemenea circumstanţe constă în interpretarea valorilor drept vectori şi nu drept puncte în spaţiu. În aceste condiţii, ceea ce se compară sunt unghiurile dintre vectori sau sinusul acestor unghiuri, care are avantajul suplimentar de a produce întotdeauna rezultate cuprinse între 0 şi 1. Unghiul vectorilor permite o evaluare a apropierii care nu este influenţată de diferenţele de talie dintre obiectele comparate. Reluând un exemplu din literatura de specialitate, comparaţia directă dintre lungimea corpului, a cozii şi a ghearelor unui leu şi a unei pisici va indica fără îndoială puncte situate la mare distanţă între ele. Dacă raporturile dintre lungimea diverselor părţi ale corpului şi lungimea totală sunt similare la leu şi la pisică, atunci vectorii vor fi aproape paraleli, indicând acum asemănarea dintre aceştia.

Pentru valorile de tip enumerativ, măsura cea mai simplă a distanţei se obţine prin raportarea numărului de câmpuri similare din cele două înregistrări comparate la numărul total de câmpuri. În funcţie de circumstanţe, se poate amplifica sau, dimpotrivă, diminua rezoluţia cu care sunt examinate similitudinile dintre înregistrări.

Detecţia suplă este o variantă a metodei celor k medii, bazată pe utilizarea de distribuţii gauss în repartizarea punctelor în cluster-e. În această abordare, un punct poate aparţine, cu probabilităţi diferite, mai multor cluster-e în acelaşi timp.

Detecţia grupurilor prin aglomerare

18

Acest demers acţionează în sens contrar celui prezentat anterior: se porneşte de la o stare iniţială în care fiecare punct este considerat a fi un cluster şi se execută aglomerări succesive până când se obţine un singur cluster, care reuneşte toate punctele. Toate variantele generate în cursul acestor iteraţii sunt conservate astfel încât, printr-o analiză ulterioară, să se poată reţine configuraţia cea mai bună, cea mai relevantă în raport cu scopul căutării.

Procesul debutează prin construirea unei matrici de similitudine, în care figurează distanţele sau gradele de asociere dintre toate punctele. Din matricea de similitudini, se extrage perechea de puncte cu valoarea cea mai mică – cele mai apropiate – care sunt grupate împreună într-un cluster distinct. Matricea se reconstruieşte, înlocuind cele două puncte prin cluster-ul lor şi recalculând distanţele de la cluster la celelalte puncte. Procesul se reia, într-o manieră similară, până când se ajunge la un singur cluster. Începând cu a doua iteraţie, devine necesară şi măsurarea distanţei dintre cluster-e. Pentru aceasta există mai multe variante:

distanţa dintre două cluster-e este distanţa dintre cele mai apropiate puncte ale acestora;

distanţa dintre două cluster-e este distanţa dintre cele mai îndepărtate puncte ale acestora;

distanţa dintre două cluster-e este distanţa dintre centrele (centroidele) lor.

La fiecare iteraţie, se memorează cluster-le obţinute şi distanţa dintre ele, în vederea analizei ulterioare.

Figura 4-4 Trei modalităţi de măsurare a distanţei dintre cluster-e

Datele comerciale asupra căreia se aplică metoda sunt, ca şi în cazul anterior, reprezentate prin înregistrări. Variantele de măsurare a asocierii menţionate anterior – distanţa euclidiană, unghiul vectorilor, numărul câmpurilor similare raportat la numărul total de înregistrări – pot fi utilizate la fel de bine şi în aceleaşi condiţii şi aici.

Gruparea prin aglomerare produce mai multe nivele succesive de grupare, până la obţinerea unui singur cluster. Este necesar să se dea şi aici un răspuns întrebării: care este cel mai bun număr de cluster-e ? Diferenţa dintre valoarea distanţei în momentul formării cluster-ului şi aceeaşi valoare la gruparea pe nivelul imediat superior este o bună măsură în acest caz. Varianta prezentată anterior, constând în compararea distanţei medii din interiorul cluster-ului cu distanţa medie dintre cluster-e, poate fi aplicată şi aici. Eventual, această comparaţie se poate face pentru o singură variabilă, considerată a fi cea mai semnificativă.

Schimbarea de scală, necesară pentru a face comparabile datele econommice exprimate uzual în unităţi de măsură diferite constă în proiecţia

19

acestor valori pe un interval comun, cuprins, spre exemplu, între 0 şi 1 sau -1 şi 1. Această proiecţie se poate face în următoarele moduri:

valoarea curentă/valoarea medie (valoarea curentă – valoarea minimă)/(valoarea maximă – valoarea

minimă) (valoarea curentă – valoarea medie)/abaterea standard (numită

conversie la scala Z).

Avantaje şi limite ale analizei grupurilor

Principalul avantaj al acestei tehnici constă în capacitatea sa de căutare nedirijată. Acesta este însă şi motivul pentru care nu este, aproape niciodată, utilizată singură. Informaţiile privitoare la configuraţiile structurale existente în masa de date analizată trebuie examinate în continuare prin alte tehnici, pentru a extrage elemente mai detaliate şi mai pertinente. Chiar şi în cadrul strict al acestei tehnici, este recomandabil ca înregistrările ce aparţin cluester-elor celor mai puternice să fie eliminate din setul de date iniţiale şi să se declanşeze un nou proces de grupare asupra datelor rămase. Există astfel şansa descoperirii de noi grupări, mascate iniţial de decalajul mare dintre distanţe sau asocieri.

Aplicarea sa este deosebit de adecvată în cazurile în care trebuie examinate structuri de date complexe, cu multe câmpuri.

Alte avantaje constau în uşurinţa de prelucrare a datelor de diverse tipuri, inclusiv a celor de tip text şi în cerinţele minimale de pregătire prealabilă a datelor de lucru.

Principalele dezavantaje constau în dificultatea găsirii metricilor potrivite pentru exprimarea distanţelor şi a ponderilor. De asemenea, interpretarea rezultatelor poate fi uneori dificilă în virtutea faptului că este vorba despre o căutare nedirijată. Proprietăţile care au stat la baza constituirii grupurilor trebuie găsite printr-o analiză suplimentară a componenţei fiecărui grup, tehnica neavând capacitatea de a furniza cunoştinţe explicite în această privinţă.

Detectarea automată de cluster-e este recomandabilă ca tehnică de debut pentru un proiect de data mining. Rezultatele furnizate de aceasta urmează a explorate în continuare cu alte tehnici pentru a obţine informaţii mai complete.

4.9 Reţelele neuronale

Reţelele neuronale constituie una dintre tehnicile de data mining ce se bucură de o largă utilizare din ce în ce mai largă în ultimul timp. Motivul acestui interes stă în eficacitatea, dovedită în numeroase aplicaţii practice, de a furniza soluţii, în special de natură predictivă, pentru probleme de mare complexitate sau volatilitate. Poate fi citat, ca exemplu sugestiv, cazul unei companii nord-americane3, distribuitoare de gaze naturale, ce obţine, cu ajutorul unei reţele neuronale, previziuni cu o acurateţe medie de 97% asupra preţurilor la gaze pe un orizont de o lună. Alte cazuri tipice de

3 Northern Natural Gas, Nebraska. Reţeaua neuronală a fost implementată cu produsul BrainMaker

20

utilizare cu succes a reţelelor neuronale includ: stabilirea preţurilor pe piaţa imobiliară, evoluţia cotaţiilor pe pieţele financiare, analiza cererilor de creditare etc.

Spre deosebire de alte metode şi tehnici utilizabile pentru a rezolva acest gen de probleme, reţelele neuronale recurg la o prelucrare ce imită funcţionarea creierului uman. Mai precis, este vorba de o simulare a comportamentului unui ansamblu de neuroni conectaţi între ei analog sinapselor din creierul uman.

O reţea neuronală dobândeşte capacitatea de a rezolva un anumit tip de problemă în urma unui proces de învăţare. Datele de învăţare conţin o serie de exemple rezolvate; prin generalizarea acestora, reţeaua neuronală poate trata ulterior şi cazuri noi. Reţeaua amintită anterior, utilizată pentru previzionarea preţurilor la gaze naturale, a învăţat în prealabil pe baza datelor acumulate privitoare la modificările de preţuri survenite, spre exemplu, în ultimii trei ani. Procesul de învăţare a permis reţelei să identifice automat un set de corelaţii între valoarea anumitor variabile şi preţurile de furnizare a gazelor naturale, pe care aceasta le foloseşte apoi pentru a face predicţii.

Toate exemplificările anterioare s-au referit numai la predicţii; reţelele neuronale sunt însă capabile să facă şi clasificări. Mai precis, ele sunt tehnici utilizabile atât pentru căutarea dirijată cât şi pentru căutarea nedirijată de informaţii. Procesele de învăţare, ca şi topologia reţelei, diferă însă substanţial pentru fiecare dintre aceste utilizări.

Funcţionarea unui neuron artificial

Neuronul artificial constituie unitatea elementară a unei reţele. Comportamentul său se apropie destul de mult de modelul unui neuron natural. Astfel, acesta va rămâne inert sau va avea o reacţie minimă la stimulii primiţi, până la un anumit nivel al acestora. Odată acest nivel depăşit reacţia devine mult mai marcată, putând depăşi în intensitate creşterea stimulului; o modificare minimală a acestuia poate antrena o reacţie puternică. Neuronul natural are, cu alte cuvinte, un comportament neliniar. Neuronul artificial simulează acest comportament prin două transformări succesive, definite prin funcţiile de combinare şi de transfer.

Funcţia de combinare priveşte modul de tratare al intrărilor; mai precis, aceasta precizează maniera de transformare a setului valorilor apărute la fiecare punct de intrare într-o valoare unică. Cea mai utilizată funcţie în acest scop este suma ponderată. Fiecărei intrări i se atribuie o anumită pondere, cu care valoarea aflată la intrarea respectivă se înmulţeşte înaintea însumării. Se pot utiliza şi alte funcţii, cum ar fi, spre exemplu, reţinerea maximului sau minimului valorilor ponderate dar, în practică, suma ponderată rămâne aproape întotdeauna o soluţie bună. Ea este, de altfel, şi cea care corespunde cel mai bine modelului biologic de origine.

Reţelele neuronale funcţionează în condiţiile cele mai bune dacă valorile de intrare şi de ieşire sunt cuprinse între 0 şi 1. Transformarea datelor economice reale în asemenea valori se face înaintea transmiterii lor către punctele de intrare şi nu are nimic de-a face cu funcţia de combinare. Aceasta primeşte valorile deja încadrate între aceste limite.

21

Funcţia de transfer este cea care transformă valoarea ponderată a intrărilor într-o valoare unică de ieşire. Cea mai utilizată în acest scop este funcţia sigmoid, având expresia:

Figura 4-5. Funcţia sigmoid

Figura 4-6. Intrările şi ieşirea unui neuron artificial

Rezultatele acesteia sunt cuprinse între 0 şi 1. Funcţia este neliniară şi are un comportament neliniar, aşa cum se poate observa din Figura 4-5. Alături de aceasta, se mai utilizează drept funcţie de transfer tangenta hiperbolică, de asemenea neliniară, ale cărei valori sunt însă cuprinse între -1 şi 1. O funcţie liniară poate fi, de asemenea, folosită în acest scop; o reţea în care se folosesc numai neuroni cu funcţie de transfer liniară produce o regresie liniară.

Interesul existenţei mai multor funcţii de transfer stă în posibilitatea de-a o alege pe cea mai potrivită pentru problema de rezolvat. Mai mult decât atât, în aceeaşi reţea neuronală pot fi prezente unităţi ce folosesc funcţii de transfer diferite. Totuşi, asemenea facilităţi sunt oferite numai de anumite produse program evoluate; funcţia utilizată în mod implicit, uneori singura disponibilă, este sigmoid-ul.

Interconectarea neuronilor

Reţeaua neuronală este compusă din mai mulţe unităţi elementare de tipul neuronilor artificiali prezentaţi anterior, conectate între ele, astfel încât ieşirile unora formează intrările altora. Există mai multe configuraţii posibile

22

0,41259

-0,29771

Combinare0,37255

0,74002

0,37255*0,41259 + 0,74002*-0,29771

Transfer

1/(1+e-0,0666)0,483356

Ponderi

Intrări

Ieşire

de structurare, cea mai folosită fiind în straturi succesive. Într-o asemenea topologie, un neuron nu poate comunica decât cu cei aflaţi pe straturile adiacente. Va exista, fără îndoială, un nivel de intrare, care primeşte datele iniţiale ale problemei şi un nivel de ieşire care furnizează rezultatul. Între acestea, pot exista unul sau mai multe straturi intermediare.

În mod uzual, fiecare dintre intrările problemei posedă pe primul nivel câte o unitate elementară distinctă. În exemplul privitor la gazele naturale, compania a considerat că evoluţia preţurilor este influenţată de următorii factori: trimestrul, anotimpul, rata vânzărilor din anul precedent, variaţia preţurilor în luna precedentă, variaţia preţurilor în anul anterior. În consecinţă, primul nivel al reţelei folosit în acest caz va include 5 unităţi elementare de intrare (neuroni artificiali). Cum este urmărit un singur rezultat – rata de variaţie a preţului pentru luna următoare, pe nivelul de ieşire va exista o singură unitate elementară. Presupunând că se recurge la un singur strat intern (suficient în numeroase cazuri), reţeaua poate avea structura din figura următoare.

Figura 4-7. Conectarea neuronilor într-o reţea neuronală

Învăţarea

Aşa cum s-a precizat, înainte de a putea fi utilizată pentru predicţii sau clasificări, reţeaua neuronală trebuie să înveţe. Învăţarea urmăreşte ajustarea comportamentului neuronilor astfel încât aceştia să producă rezultate identice sau cât mai apropiate de cele cuprinse în datele de test. Dintre toate componentele amintite, învăţarea afectează numai ponderile atribuite intrărilor, funcţiile de combinare şi de transfer rămânând neschimbate.

Cea mai utilizată tehnică de învăţare pentru reţelele cu flux direct se bazează pe retropropagarea erorilor. În linii generale, procesul de învăţare se derulează în felul următor: se furnizează reţelei datele iniţiale ale unui exemplu şi se compară rezultatul generat de aceasta cu rezultatul real. Abaterea constatată este propagată în reţea în sens invers, de la ieşire spre

23

Nivel de intrare

Nivel intern

Nivel de ieşire

trimestrul

anotimpul

rata vânzărilor în anul precedent

variaţia preţurilor în

luna precedentă

variaţia preţurilor în anul anterior

rata de variaţie a preţului în luna următoare

intrare, iar ponderile folosite de către neuroni se reajustează astfel încât eroarea să se diminueze cât mai mult. Se procedează identic pentru fiecare dintre exemplele aflate în setul de învăţare, după care procesul se reia din nou şi din nou, în aceiaşi termeni, până când ponderările nu mai suferă modificări şi eroarea rămâne stabilă. Este momentul în care reţeaua a terminat de învăţat.

Căutarea dirijată a informaţiilor

Etapele de urmat pentru utilizarea reţelelor neuronale în căutarea dirijată de informaţii sunt:

identificarea caracteristicilor de intrare şi ieşire pregătirea datelor constituirea unei reţele cu topologie adecvată învăţarea testarea aplicarea reţelei în rezolvarea problemelor

Identificarea caracteristicilor de intrare şi ieşire

Abordarea specifică reţelelor neuronale presupune, aşa cum a rezultat din paragrafele anterioare, formularea problemei de rezolvat sub forma unui set de intrări, ale căror valori determină, prin corelaţii complexe ce rămân de aflat, valoarea luată de caracteristica ce constituie rezultatul urmărit. Spre exemplu, într-o aplicaţie din domeniul imobiliar, ieşirea va fi reprezentată de preţul locuinţei. Intrările vor fi: localitatea, zona de amplasare, tipul locuinţei, caracteristicile clădirii în care se află, anul construcţiei, suprafaţa totală, numărul de camere, etajul, sistemul de încălzire etc. Este aşadar normal ca procesul să debuteze cu identificarea acestor caracteristici. Aici intervin cunoştinţele de specialitate ale decidentului, viziunea sa asupra problemei şi, nu mai puţin, structura înregistrărilor de date disponibile pentru învăţare. Nu serveşte la nimic luarea în considerare a unor intrări care nu sunt disponibile, chiar dacă, în plan conceptual, selecţia lor este pe deplin justificată. De asemenea, nu există certitudinea că toate intrările alese sunt relevante în raport cu ieşirea; că au, cu alte cuvinte, o influenţă semnificativă asupra mărimii acesteia.

Pregătirea datelor

Pregătirea datelor este adesea partea cea mai critică. Aceasta vizează două aspecte esenţiale: alegerea adecvată a datelor ce vor fi folosite pentru învăţare şi normalizarea intrărilor şi ieşirilor în intervalul de valori cuprins între 0 şi 1.

Normalizarea se realizează după metode diferite, în funcţie de natura valorilor de tratat.

24

Variabilele tip raport, ale căror valori sunt mărimi cantitative, pot fi normalizate printr-o relaţie de tipul următor:

valoare normalizată = (valoare de normalizat – valoarea minimă) / (valoarea maximă – valoarea minimă)

În această categorie se regăsesc diverse sume (preţuri, active şi pasive bilanţiere, venituri etc), mărimi fizice (suprafeţe ale locuinţelor, greutăţi, lungimi etc), mărimi medii (salarii medii, încasări medii zilnice) rapoarte (cursuri valutare, rate ale profitului) ş.a.m.d. Relaţia anterioară dă bune rezultate, cu condiţia cunoaşterii exace a valorilor extreme – minimală şi maximală. Dacă acest lucru nu este posibil, se poate recurge la mai multe soluţii:

prevederea din start a unui interval mai mare decât cel aferent valorilor cunoscute;

excluderea valorilor care depăşesc limitele prestabilite; trunchierea valorilor excedentare la valorile extreme ale

intervalului; modificarea relaţiei de calcul astfel încât aceasta să plaseze

rezultatele între 0,1 şi 0,9.Fiecare dintre aceste soluţii are avantaje şi dezavantaje şi trebuie

aplicată numai după analiza implicaţiilor sale asupra rezultatului final. O altă problemă pentru acest tip de variabile poate proveni din

distribuţia asimetrică a valorilor. Dacă marea majoritate a acestora se plasează într-o zonă restrânsă, relaţia anterioară va conduce la diferenţe nesemnificative între rezultatele ce corespund valorilor din grupul majoritar. Pentru o plajă de venituri lunare cuprinsă între 1 milion şi 25 de milioane, sumelor de 2 şi 3 milioane le corespund valorile normalizate 0,04 şi 0,08, cu diferenţe foarte mici între ele deşi în realitate ele sunt foarte semnificative pentru un procent însemnat al populaţiei. O bună soluţie pentru o asemenea situaţie constă în aplicarea relaţiei de normalizare asupra valorii logaritmice a venitului. Valoarea normalizată pentru venitul de 2 milioane devine acum 0,22, iar pentru venitul de 3 milioane, 0,344.

Variabilele tip interval primesc valori ordonate şi discrete, deosebite de cele precedente doar prin faptul că au un punct de origine convenţional şi nu natural. În această categorie se regăsesc diversele numărări (numărul de copii, numărul de autoturisme, numărul mediu de articole comandate), vârsta, enumerările ordonate (calitatea întâia, calitatea a doua) etc.

Normalizarea acestor variabile se poate obţine în mai multe moduri. O primă soluţie, foarte simplă, constă în împărţirea intervalului dintre 0 şi 1 la numărul de valori existente. Presupunând, spre exemplu, că o familie poate avea între 0 şi 7 copii de vârstă preşcolară, vor exista 8 valori diferite. În aceste condiţii, valorile normalizate devin: 0 (0 copii), 0,143 (1 copil), 0,286 (2 copii), 0,429 (3 copii), …, 0,857 (6 copii), 1 (7 copii).

Dacă valorile de acest tip nu sunt egal distanţate din punct de vedere al semnificaţiei în spaţiul problemei, se poate recurge la o soluţie care să exprime, prin valorile normalizate generate, şi această diferenţiere. În acest scop, poziţiile valorilor respective, începând cu cele mai puţin importante, se codifică binar, după care se normalizează valorile zecimale corespunzătoare

4 (log(2000000) – log(1000000)) / (log 25000000) – log(1000000))

25

acestora. Atribuirea codurilor binare se face mărind secvenţa de valori unu de la stânga spre dreapta, similar creşterii nivelului de mercur dintr-un termometru5. Păstrând relaţia de ordonare, prin această soluţie distanţa dintre valori nu mai este aceeaşi, poziţiile superioare fiind mai apropiate una de alta. Spre exemplu, gradele didactice universitare ar putea fi reprezentate astfel:

Cod binar Valoare normalizatăpreparator 10000 0,500asistent 11000 0,767lector 11100 0,900conferenţiar 11110 0,967profesor 11111 1,000

Se poate recurge şi la alte modalităţi de reprezentare normalizată pentru a transmite reţelei neuronale faptul că anumite valori sunt mai importante sau mai semnificative decât altele.

Variabilele nominale primesc valori enumerative, între care nu există relaţii de ordonare, cum sunt, spre exemplu: sexul, starea civilă, profesia, codurile de produse etc. Acestea pot fi normalizate ca şi variabilele tip interval, cu condiţia ca relaţia de ordonare, introdusă implicit de acestea, să nu consituie o sursă de perturbaţii, având în vedere că reţeaua neuronală o va lua automat în considerare. O soluţie care elimină orice posibilă relaţie de ordonare constă în definirea valorilor respective drept variabile diferite, cărora li se atribuie valori ce se exclud reciproc. Spre exemplu, pentru a reprezenta în aceste condiţii sexul unei persoane, vor exista două variabile - VFeminin şi VMasculin - care vor primi, fiecare, valorile normalizate1 sau 0.

Sex VFeminin VMasculinfeminin 1 0masculin 0 1necunoscut 0 0

Variabilele şi valorile de alte tipuri pot ridica diverse probleme, la care trebuie căutate soluţii pe măsură, neuitând nici un moment că maniera de reprezentare şi normalizare trebuie alese în aşa fel încât să permită recunoaşterea coleraţiilor şi structurilor încorporate în datele tratate. În strânsă legătură cu acest aspect, este de menţionat că uneori, pentru a surprinde mai bine semnificaţia ascunsă a datelor, este necesară înlocuirea valorilor originale cu indicatori derivaţi din acestea. Spre exemplu, într-o aplicaţie bursieră, este mult mai adecvată reprezentarea variaţiei cotaţiilor acţiunilor decât utilizarea mărimii acestora. De asemenea, într-o aplicaţie de marketing, va fi mult mai semnificativă cunoaşterea zilei din săptămână în care se face vânzarea decât a datei calendaristice.

Interpretarea rezultatelor furnizate de reţeua neuronală ridică şi ele probleme, de acestă dată de denormalizare. Valorile obţinute, cuprinse ca şi

5 Din cauza acestei similitudini, este denumit chiar "cod termometru".

26

intrările între 0 şi 1, trebuie transpuse într-o scală de măsurare adecvată interpretării şi utilizării lor practice. Pentru multe dintre rezultate, acesta este un proces foarte simplu, solicitând doar raportarea la valorile extreme ale variabilelor rezultat din datele de învăţare. Spre exemplu, ştiind că preţurile locuinţelor în datele de învăţare se încadrează între 124.000.000 lei ( 4000$) şi 1.860.000.000 lei ( 60000 $), rezultatul 0,274 furnizat de reţeaua neuronală va reprezenta suma de 600.000.000 lei.

Dacă rezultatele exprimă caracteristici cu valori binare sau enumerative, interpretarea este mai dificilă deoarece reţeaua furnizează, prin definiţie, valori continue. Soluţiile simpliste, de genul interpretării rezultatului în funcţie de poziţia faţă de valorile extreme 0 şi 1, pot conduce la erori importante. Din această cauză, o rezolvare corectă a problemei presupune construirea unei scale de corespondenţe elaborată pe baza unui set de date de testare. Acestea sunt diferite de datele de învăţare şi servesc verificării reţelei înainte de a trece la utilizarea sa efectivă. Cum rezultatele sunt şi aici cunoscute dinainte, se poate stabili, în modul cel mai sigur, care sunt plajele de valori furnizate de reţea care le corespund. Presupunând, pentru exemplificare, o reţea destinată identificării tentativelor de fraudă prin carduri bancare, aceasta va produce în mod firesc două rezultate, corespunzând autorizării sau blocării tranzacţiei. Soluţia de a stabili că valorile mai mari de 0,5 corespund autorizării iar cele inferioare, blocării, deşi aparent corectă, poate conduce la rezultate necorespunzătoare în practică. Recurgând la calibrarea cu un set de date de test, se obţine o distribuţie a rezultatelor de genul celei reprezentate în figura următoare, din care rezultă că plaja de rezultate ce corespund tentativelor de fraudă începe, în fapt, de la valoarea 0,64.

Pentru rezultatele enumerative, se poate recurge şi la definirea de unităţi elementare de ieşire distincte pentru fiecare valoare a acestora. Aceasta nu exclude însă posibilitatea de a obţine valori simultane la mai multe ieşiri; cu alte cuvinte, reţeaua exprimă tendinţa spre unul sau altul dintre rezultate şi nu punctează în mod exclusiv pe unul dintre ele.

27

0,5 A A AA AB B BBB A A

A – autorizareB - blocare

Interpretarea iniţială

Interpretarea corectă, pe baza datelor de testare

Rezultatele la testare

Figura 4-8. Aplicarea reţelei neuronale pe un set de date de testare permite calibrarea corectă a rezultatelor

Constituirea reţelei

Principala problemă la care trebuie dat un răspuns aici se referă la stabilirea numărului de straturi şi a numărului de neuroni pe fiecare strat. Configuraţia cea mai simplă este compusă din două straturi: intrarea şi ieşirea; rezultatul pe care-l poate oferi aceasta echivalează cu metoda statistică de regresie logistică.

Dimensiunea stratului de intrare este determinată de numărul de caracteristici

Numărul de straturi interne depinde de natura problemei de rezolvat. În marea majoritate a cazurilor, un singur strat intern este suficient.

Mărimea stratului intern are implicaţii importante asupra funcţionării reţelei. În termeni generali, cu cât numărul de neuroni din compunerea acestuia este mai mare, cu atât reţeaua este mai puternică. Un strat intern prea mare face însă posibil ca reţeaua să memoreze exemplele de învăţare în loc să le generalizeze şi, în felul acesta, să compromită capacitatea de a rezolva probleme noi. O regulă empirică recomandă ca stratul intern să nu depăşească dublul stratului de intrare. Ulterior, acest număr mai poate fi modificat, în funcţie de comportamentul manifestat de reţea în cursul învăţării.

Pentru reţelele destinate rezolvării problemelor de clasificare, este necesar cel puţin un neuron intern pentru fiecare clasă de elemente.

Tot aici mai pot interveni alegerea funcţiilor de combinare şi transfer, în cazul în care produsul program folosit oferă asemenea facilităţi.

Învăţarea

Reţeaua neuronală construieşte un model al exemplelor de învăţare pe care-l foloseşte apoi pentru a rezolva probleme noi. Valoarea reţelei este dată aşadar de ansamblul datelor folosite pentru învăţare.

Având în vedere că învăţarea constă în găsirea mărimilor adecvate pentru ponderile aplicate intrărilor, setul de date folosite pentru învăţare trebuie să includă suficiente exemple pentru fiecare dintre intrări şi, nu mai puţin, pentru întreaga plajă de valori pe care o pot lua fiecare dintre acestea. Chiar dacă, în realitate, anumite valori vor apărea mult mai frecvent decât altele, în datele de învăţare acestea trebuie să apară în proporţie relativ egală, astfel încât reţeaua să poată recunoaşte şi trata corect toate cazurile. Volumul exemplelor trebuie corelat, de asemenea, cu numărul total de ponderi existente în reţea. Se consideră că pentru fiecare pondere sunt necesare cel puţin 5 exemple, ceea ce va conduce, pentru o reţea cu 8 intrări şi 15 unitătţi elementare pe stratul intern, la un volum minim de 600 înregistrări în datele de învăţare (8 * 15 * 5).

Testarea

Înaintea trecerii la utilizare efectivă, reţeaua neuronală este supusă unui proces de testare. Datele de test conţin, ca şi cele de învăţare, seturi complete

28

de valori de intrare împreună cu rezultatele corespunzătoare. Intrările sunt supuse reţelei iar ieşirile acesteia se compară cu rezultatele cunoscute. Validarea urmăreşte să verifice calitatea modelului obţinut prin învăţare; în consecinţă, datele pe care se bazează trebuie să fie total diferite de datele de învăţare dar să fie de aceeaşi natură. Practic, se procedează la împărţirea setului iniţial de exemple disponibile în două grupuri – învăţare şi testare, având grijă ca repartizarea între acestea a înregistrărilor să fie cât mai aleatoare cu putinţă. Din punct de vedere al mărimii, se recomandă o proporţie de 80% din totalul exemplelor pentru învăţare şi 20% pentru test.

Unele produse program combină interactiv învăţarea cu testarea; după fiecare parcurgere completă a datele de învăţare, modelul obţinut este verificat prin intermediul datelor de test.

Cum reţeaua nu furnizează reguli explicite, singura modalitate de a înţelege modul în care se ajunge de la intrări la rezultate rămâne analiza de sensibilitate. Aceasta urmăreşte să indice importanţa relativă a intrărilor în rezultatul final. Pentru a stabili care dintre intrări influenţează cel mai mult rezultatul, se poate proceda în felul următor: se determină valoarea medie a fiecărei intrări şi se calculează rezultatul în acestă situaţie, după care se modifică una câte una intrările cu valori ce tind spre extreme şi se urmăreşte efectul asupra rezultatului. Analiza poate lua în considerare şi efectul combinat al anumitor cupluri de intrări. Se constată astfel că pentru unele intrări sensibilitatea reţelei este foarte mică, în timp ce pentru altele, variaţia valorii are efecte importante.

Utilizarea

Odată modelul validat, reţeaua este memorată şi poate fi folosită pentru prelucrarea de intrări noi. În timpul utilizării, trebuie acordată atenţie permanentă tendinţei de uzură, de îndepărtare treptată de realitate. Acest proces are loc deoarece modelul obţinut prin învăţare este static. El corespunde realităţii reflectate de datele de învăţare. Schimbările petrecute în realitate după acest moment nu mai sunt percepute de model; în consecinţă există riscul ca rezultatele furnizate după o anumită perioadă de utilizare, care în unele cazuri se poate măsura în zile, să nu mai fie cele corecte. Este lesne de imaginat la ce rezultate s-ar putea ajunge cu o reţea pentru tranzacţii bursiere, în care ultimele tendinţe ale pieţei sunt lăsate în afara modelului. Acest risc este cu atât mai mare cu cât reţeaua se caracterizează prin robusteţe, ceea ce face ca inadecvarea să devină sesizabilă prin observaţie directă destul de târziu. Pentru a preveni asemenea stări, este necesar un proces de reînvăţare periodică, care se poate face pe aceeaşi reţea sau pe o reţea nouă, adăugând exemplele noi la setul iniţial de învăţare.

Avantajele şi limitele utilizării reţelelor neuronale

Unul dintre avantajele cele mai importante ale reţelelor nuronale constă în capacitatea de a furniza rezultate în domenii complexe sau delicate, cum sunt detecţia fraudelor sau prelucrarea seriilor cronologice (cotaţii bursiere spre exemplu).

29

Învăţând singure din setul de exemple pus la dispoziţie, reţelele neuronale sunt mult mai puternice decât alte tehnici şi se pot aplica unei mari diversităţi de probleme. Pot fi folosite atât pentru predicţii cât şi pentru clasificări, admiţând ambele modalităţi de căutare: dirijată şi nedirijată.

Metodele de normalizare existente le fac aplicabile pentru o mare varietate de tipuri de variabile.

Principalul reproş care se poate face acestei tehnici constă în faptul că cunoaşterea acumulată nu primeşte o formulare explicită, astfel încât să poată fi folosită şi în afara reţelei. Analiza de sensibilitate rămâne singura modalitate de a obţine informaţii despre acţiunea sa în rezolvarea problemelor. Cu toate acestea, constituie o foarte bună soluţie atunci când rezolvarea problemelor este mai importantă decât înţelegerea sau explicarea modelului.

S-a subliniat deja importanţa setului de date de învăţare. Dacă acestea nu sunt bine alese şi echilibrate, există riscul ca rezultatele să fie fals orientate, spre soluţii cu caracter local.

În fine, este de remarcat că reţelele neuronale nu sunt recomandabile în rezolvarea de probleme ce folosesc un număr însemnat de variabile de intrare, din cauza perturbaţiilor ce pot surveni, în aceste condiţii, în procesul de învăţare.

4.10 Algoritmii genetici

Algoritmii genetici aplică principalele mecanisme ale selecţiei naturale pentru a favoriza conservarea şi reproducerea, dintr-o populaţie numerosă, a celor mai performanţi, mai bine adaptaţi indivizi. Populaţia este formată din ansamblul de soluţii posibile ale unei probleme; cel mai adaptat individ este prin urmare, cea mai bună soluţie. Algoritmii genetici permit aşadar găsirea soluţiei optime şi ocupă, prin aceasta, un loc particular în cadrul tehnicilor de data mining, orientate, ca regulă generală, spre efectuarea de predicţii sau clasificări.

Termenul algoritm genetic a fost folosit pentru prima oară în anul 1967 de către olandezul J.D.Bagley. Totuşi, anul de debut în utilizarea lor efectivă este considerat a fi 1975, când John Holland a prezentat o metodă de optimizare bazată pe principiile de selecţie naturală, prin care a demonstrat cu rigoarea necesară de ce funcţionează algoritmii genetici şi cum reuşesc aceştia să producă rezultate atât de performante.

Funcţionarea algoritmilor genetici

Algoritmii genetici funcţionează prin producerea de generaţii succesive de indivizi. Indivizii cei mai puternici supravieţuiesc şi au descendenţi iar indivizii neadaptaţi dispar treptat. Unităţile elementare care controlează această evoluţie sunt genele. Prin reproducere, genele părinţilor se combină şi conduc la o nouă generaţie, mai bine adaptată.

Materialul genetic este numit cromozom. Un cromozom poate fi compus din una sau mai multe gene. Genele sunt reprezentate printr-o secvenţă de simboluri – în general 0 şi 1. Algoritmii genetici funcţionează prin producerea de generaţii succesive de cromozomi cu aptitudini din ce în ce

30

mai bune, până la atingerea unui punct de stabilitate a acestora, coincizând cu soluţia optimă.

Paşii în care funcţionează algoritmii genetici sunt: Definirea cromozomului şi a funcţiei de aptitudine a acestuia; Crearea primei generaţii Modificarea populaţiei existente prin selecţie, încrucişare şi

mutaţie, în mod repetat, până la obţinerea unei stări stabile (care nu mai evoluează).

Definirea cromozomului constă în stabilirea numărului de gene şi a semnificaţiei acestora în spaţiul problemei. Pentru a putea aprecia cât de apt este cromozomul, este necesară definirea unei funcţii de aptitudine. Funcţia de aptitudine este cea care permite aprecierea "calităţii" sau a nivelului de adaptare a cromozomilor produşi. Semnificaţia acesteia, derivată de asemenea din problema de rezolvat, nu are importanţă pentru algoritm decât prin aceea că furnizează o valoare de apreciere a nivelului atins.

Presupunând, spre exemplu, o problemă în care intervin patru caracteristici: starea civilă, grupa de vârstă, nivelul de studii şi nivelul venitului anual, se poate recurge la următoarea convenţie de reprezentare:

starea "căsătorit" se notează prin 1, orice altă stare civilă prin 0 vârsta sub 35 de ani se notează prin 0, altfel prin 1 studiile medii se notează prin 0, studiile superioare prin 1 venitul anual mai mic sau egal cu 45 de milioane lei se notează

prin 0, peste această limită prin 1.În aceste condiţii, un individ necăsătorit, de 31 de ani, cu studii

superioare şi un venit anual de 58 de milioane lei va fi simbolizat prin 0011, notaţie ce reprezintă cromozomul său. Dacă este necesară tratarea de caracteristici cu valori continue - cum ar fi, spre exemplu, vârsta exactă în ani – valorile respective pot fi reprezentate ca numere binare (în cazul exemplului anterior, vârsta devine astfel 11111).

Să presupunem că funcţia de aptitudine este reprezentată de procentul de posesori de telefoane mobile. În urma observaţiilor făcute, s-a întocmit tabelul următor. Se poate constata că cea mai bună performanţă este obţinută de cromozomul 0011 iar cea mai slabă, de cromozomul 0010.

Selecţia urmăreşte să permită numai indivizilor celor mai adaptaţi să transmită materialul lor genetic generaţiilor următoare. Cu cât un individ este mai adaptat – în alţi termeni, cu cât valoarea funcţiei sale de aptitudine este mai bună – cu atât şansele sale de supravieţuire în generaţiile următoare sunt mai mari. Numărul indivizilor ce compun populaţia nu creşte de la o generaţie la alta, ceea ce face să existe o puternică presiune selectivă.

Tip Valoarea funcţiei de aptitudine (%)

Număr de persoane

Pondere în total observaţii

0011 8% 2150 18,14%1101 3,2% 4200 35,44%0010 1,8% 2450 20,68%1001 5,1% 3050 25,74%

11850

Tabelul 4-8. Un exemplu de populaţie cu patru tipuri de cromozomi

31

Selecţia candidaţilor ce vor supravieţui în generaţia următoare se face prin tragere la sorţi. Hazardul este însă uşor dirijat astfel încât indivizii cei mai apţi să aibă şansele cele mai mari. În acest scop, se ia în considerare raportul dintre valoarea funcţiei de aptitudine şi aptitudinea medie. Deoarece acesta este fracţionar, iar numărul de indivizi selectaţi trebuie să fi întreg, alegerea se face sub forma unei "roţi de ruletă", împărţită în sectoare proporţionale cu aptitudinile tipurilor existente de cromozomi. La fiecare activare, aceasta se opreşte în interiorul unui sector şi marchează un individ cu cromozomul respectiv.

Tabelul 4-9 prezintă aceste elemente calculate pentru exemplul anterior. Se poate observa redistribuirea indivizilor între cei patru cromozomi, proporţional cu valoarea funcţiei de aptitudine a acestora. Cei mai numeroşi sunt acum indivizii cu cromozomul 0011, care primesc o pondere de 44% faţă de 18% în situaţia iniţială, ceea ce le dă dreptul la 2,4 urmaşi, în timp ce indivizilor cu cromozomul 1101, cei mai numeroşi iniţial, le revine acum doar 18% din total, adică 0,5 urmaşi.

Tip Valoarea funcţiei de aptitudine

(%)

Proporţia indivizilor aşteptaţi

la generaţia următoare

Ponderea în total

0011 8% 1,77 44%1101 3,2% 0,71 18%0010 1,8% 0,40 10%1001 5,1% 1,13 28%

Tabelul 4-9. Parametrii de selecţie pentru populaţia anterioară

Selecţia este urmată în algoritm de încrucişare. Aceasta pleacă de la doi cromozomi existenţi, din care anumite părţi sunt permutate iar celelalalte sunt păstrate neschimbate, pentru a obţine doi cromozomi noi. Figura 4-9 ilustrează acţiunea acestui operator.

Figura 4-9. Schema operatorului de încrucişare

32

11010111

1111101

11110111

1101101

Cromozomii iniţiali

Cromozomii rezultaţi din încrucişare

Poziţia de încrucişare

Cromozomii rezultanţi, numiţi copii, moştenesc o parte dintre caracteristicile celor doi părinţi.

În mod concret, se aleg aleator perechi de cromozomi şi se trage apoi la sorţi pentru a stabili dacă vor fi sau nu încrucişaţi. O probabilitate de încrucişare de 0,5 (echivalentă cu aruncarea unei monede) este, în cele mai multe cazuri, corespunzătoare. Cromozomii rezultaţi din încrucişare îşi înlocuiesc părinţii în noua generaţie.

Mutaţia intervine ca o eroare în transmiterea materialului genetic. Practic, aceasta constă în schimbarea unei gene din zero în unu sau invers. Frecvenţa sa de apariţie în natură este redusă şi rămâne la fel şi în cadrul algoritmului: în general, câte o singură mutaţie la fiecare generaţie.

Figura 4-10. Schema producerii mutaţiilor genetice

Mutaţiile sunt, în marea majoritate a cazurilor, destructive. Indivizii apăruţi prin efectul lor sunt foarte puţin viabili şi în una sau două generaţii succesive vor fi eliminaţi. Interesul folosirii lor în algoritmii genetici vine din faptul că permit evitarea situaţiilor de blocaj sau migrarea rapidă spre un optim local. Spre exemplu, toate genele pot ajunge, la un moment dat, să aibă valoarea zero. În aceste condiţii, încrucişarea nu mai poate genera nimic. Mutaţia produce, în asemenea cazuri, noi cromozomi, permiţând continuarea procesului.

Ca efect al selecţiei, încrucişării şi mutaţiei, cromozomii pot primi orice combinaţie de biţi. Unele dintre aceste secvenţe ar putea să nu aibă sens pentru problema tratată. Cum apariţia lor nu poate fi împiedicată, funcţia de aptitudine trebuie astfel definită încât să acorde, pentru asemenea cromozomi, valori extrem de mici, care să conducă la eliminarea lor “naturală”.

Pentru exemplificare, vom considera următoarea problemă ultrasimplificată: un capital de 8 miliarde de lei este disponibil pentru amplasarea unor unităţi productive în trei localităţi: L1, L2 şi L3. Costul amplasării depinde de fiecare localitate, având următoarele valori: 1,5 miliarde pentru L1, 1,2 miliarde pentru L2 şi 1,7 miliarde pentru L3. Profiturile unitare asociate investiţiilor din fiecare localitate sunt: 0,35 miliarde pentru L1, 0,4 miliarde pentru L2 şi 0,45 miliarde pentru L3. Se cere să se stabilescă ce localităţi trebuie alese şi câte unităţi productive x trebuie construite în fiecare pentru ca beneficiul total să fie maxim.

Având în vdere că numărul maxim de unităţi, în limita sumei disponibile, este 6, numărul x de unităţi din fiecare localitate va fi reprezentat printr-un număr binar cu lungimea de 3 biţi, ceea ce conduce la un cromozom din 9 biţi. Funcţia de aptitudine calculează profitul total pentru situaţiile în care investiţia totală se încadrează în limita de 8 miliarde şi 0 în caz contrar, pentru a exclude soluţiile care duc la depăşirea acesteia:

33

1101011

Generaţia următoare

1111011

F = x1*0,34 + x2* 0,32 + x3*0,5 dacă x1*1,3+x2*1,2+x3*1,7 ≤8 0 în caz contrar.

Tabelul 4-10 prezintă patru cromozomi oarecare, valorile corespunzătoare ale funcţie de aptitudine şi proporţia calculată pentru generaţia următoare.

Cromozomi Valoare fct. aptitudine

Proporţia pentru generaţia următoare

001 001 001 1,16 0,97000 001 001 0,82 0,68010 000 001 1,18 0,98000 010 010 1,64 1,37

Tabelul 4-10. Cromozomii iniţiali pentru rezolvarea problemei investiţiei optime

În urma selecţiei au fost reţinuţi cromozomii prezentaţi în tabelul următor. Valoarea medie a funcţiei de aptitudine a crescut deja, de la 1,2 în situaţia iniţială, la 1,32.

Cromozomi Valoarea funcţiei de aptitudine

Proporţia pentru generaţia următoare

000 010 010 1,16 1,24000 001 001 0,82 0,62010 000 001 1,18 0,89000 010 010 1,64 1,24

Tabelul 4-11. Rezultatele primei selecţii

Având în vedere că sunt doar patru cromozomi, se va face o singură încrucişare, între 2 şi 3, din poziţia 4. Valoarea medie a funcţiei de aptitudine rămâne aceeaşi dar se schimbă semnificativ proporţia pentru generaţia următoare (Tabelul 4-12).

O eventuală mutaţie la bitul 4 al primului cromozom va conduce însă la scăderea aptitudinii medii la valoarea 0,91 (Tabelul 4-13). Chiar şi în această ipoteză, pasul următor conduce la creşterea aptitudinii medii la 1,57 (Tabelul4-14 ).

Cromozomi Valoarea funcţiei de aptitudine

Proporţia pentru generaţia următoare

000 010 010 1,64 1,24010 001 001 1,5 1,14000 000 001 0,5 0,38000 010 010 1,64 1,24

Tabelul 4-12. Efectul încrucişării cromozomilor 2 şi 3, din poziţia 4.

34

Cromozomi Valoarea funcţiei de aptitudine

Proporţia pentru generaţia următoare

000 110 010 0 0,00010 001 001 1,5 1,65000 000 001 0,5 0,55000 010 010 1,64 1,80

Tabelul 4-13. Efectul mutaţiei bitului 4 al primului cromozom.

Cromozomi Valoarea funcţiei de aptitudine

Proporţia pentru generaţia următoare

000 010 010 1,64 1,04010 001 001 1,5 0,96010 001 001 1,5 0,96000 010 010 1,64 1,04

Tabelul 4-14. Rezultatul celei de a doua selecţii.

Continând în acest mod, se ajunge la cromozomul 000 001 100 care reprezintă soluţia optimă (nici o unitate în localitatea L1, 1 unitate în L2, 4 unităţi în L3, profitul total 2,32 miliarde lei).

Este remarcabil faptul că natura a găsit această modalitate de a tinde spre o aptitudine cât mai bună, practic independent de semnificaţia acordată genelor ce compun cromozomii. Nu trebuie uitat de asemenea că această tehnică urmează cel mai simplu model de cromozom, numit haploid, în care genele sunt organizate pe un singur nivel, configuraţie existentă numai în organismele unicelulare, de complexitate redusă. Organismele evoluate conţin însă cromozomi diploizi, în care există un număr dublu de gene, dispuse pe două şiruri.

Utilizări ale algoritmilor genetici

Algoritmii genetici se caracterizează prin uşurinţă în aplicare şi robusteţe. Capacitatea de a se orienta rapid spre cea mai bună soluţie într-un spaţiu complex le face să fie utilizate, cu predilecţie, pentru rezolvarea problemelor de optimizare a utilizării resurselor. În special în cazurile caracterizate prin reguli numeroase şi date relativ reduse, se dovedesc extrem de utili. Unul dintre cei mai mari producători de whisky din lume6 a recurs la această tehnică pentru a îmbunătăţi depozitarea ingredientelor necesare fabricaţiei. La producerea fiecărui sortiment se foloseşte un anumit număr de tipuri de whisky, produs în diverse distilerii, din diverse tipuri de malţ şi cereale, cu un anumit număr de ani de vechime, care se combină în proporţii bine stabilite. Toate acestea se păstrează în recipiente distincte, plasate în mai multe încăperi ale spaţiilor de depozitare. Numărul de recipiente folosite anual este de ordinul milioanelor, ceea ce justifică preocuparea pentru reducerea manipulărilor acestora, cu atât mai mult cu cât

6 United Distillers, cf. http://www.attar.com

35

aproape jumătate servesc numai pentru a elibera calea de acces spre cele necesare fabricaţiei în curs. A fost dezvoltată prin urmare o soluţie bazată pe algoritmi genetici, care stabileşte, în funcţie de sortimentele de whisky ce urmează a fi produse în perioada imediat următoare, amplasarea optimă a recipientelor astfel încât să se obţină un minim al numărului de “uşi” de încăperi de depozitare prin care trebuie să treacă acestea şi al numărului de deplasări pentru a elibera calea de acces. Prin aplicarea sa, numărul de uşi tranzitate săptămânal s-a redus la jumătate iar manipulările legate de eliberarea căilor de acces s-au redus la 4% din total, faţă de aproape 50% iniţial.

Algoritmii genetici sunt folosiţi frecvent în procesul de învăţare al reţelelor neuronale. Cu ajutorul lor, găsirea ponderilor fiecărei unităţi elementare se face mult mai rapid. În acest scop, fiecare pondere primeşte o reprezentare binară. Cum valorile sunt cuprinse între 0 şi 1, numerele binare folosite pentru reprezentarea lor definesc diviziuni ale acestui interval; spre exemplu, 00000101 va reprezenta 5/255, adică 0,019608 (255 fiind valoarea maximă reprezentabilă cu 8 biţi). Cromozomul este format, în consecinţă, din grupurile de biţi aferente tuturor ponderilor din reţea. Funcţia de aptitudine măsoară diferenţele dintre ieşirea produsă de reţea şi ieşirea corectă. Algoritmul va funcţiona căutând minimizarea acestei valori sau maximizarea rezultatului scăderii acesteia dintr-o valoare constantă, suficient de mare.

Eficacitatea dovedită de algoritmii genetici în procesul de învăţare a reţelelor neuronale a determinat încorporarea acestora în numeroase produse program profesionale.

Avantajele şi limitele utilizării algoritmilor genetici

Unul dintre cele mai semnificative avantaje ale algoritmilor genetici este abilitatea lor de a rezolva probleme de optim în situaţii caracterizate printr-un spaţiu vast de soluţii. Una dintre concluziile rezultate din studiul făcut de Holland este aceea că, pe o populaţie de N cromozomi, numărul de explorări realizate este proporţional cu N3. Cu alte cuvinte, la fiecare generaţie se prelucrează doar cei N cromozomi, dar prin modul de acţiune sunt evaluate din punct de vedere al utilităţii N3 combinaţii.

Rezultatele oferite pot fi explicate prin corelarea genelor cu expresia funcţiei de aptitudine folosită. Aplicarea lor nu ridică problemele ridicate de celelalte tehnici cu privire la tipul datelor tratate. Algoritmii genetici se pot folosi în orice problemă ale cărei date pot fi reprezentate prin şiruri de biţi de lungime constantă. Semnificaţia acestora nu are nici o importanţă pentru algoritm; prelucrarea are loc prin selecţie, încrucişare şi mutaţie astfel încât să se obţină valori cât mai bune ale funcţiei de aptitudine, oricare ar fi semnificaţia acesteia. Comportamentul de tip “cutie neagră” conferă astfel o foarte bună flexibilitate faţă de problemele tratate.

Unele dintre avantajele amintite sunt şi surse de limitare. Utilizarea acestei tehnici este condiţionată de găsirea modalităţii adecvate de expresie a problemei prin cromozomi de lungime fixă şi funcţie de aptitudine, ceea ce nu este întotdeauna prea simplu. Aceasta presupune, de asemenea, o bună înţelegere a mecanismului specific de funcţionare şi a importanţei valorilor

36

parametrilor de selecţie, încrucişare şi mutaţie, pentru a evita anumite riscuri de deviere spre soluţii optime locale.

O serie de cercetări în curs pot aduce ameliorări notabile în privinţa utilităţii acestei tehnici în rezolvarea problemelor de gestiune.

4.11 Arborii de decizie

Arborii de decizie constituie o tehnică aplicabilă atât pentru clasificare cât şi pentru predicţie. Aşa cum indică şi numele, rezultatul ia forma unei arborescenţe care prezintă o ierarhie de reguli logice stabilite automat prin explorarea unei baze de exemple. Exemplele au forma unor înregistrări compuse din mai multe atribute. Regulile se obţin ca efect al subdivizării din ce în ce mai detaliate a ansamblului exemplelor, în funcţie de conţinutul atributelor.

Construcţia arborelui începe de la rădăcină. Aceasta reprezintă totalitatea exemplelor disponibile. Ansamblul iniţial este divizat în submulţimi, ce devin noduri intermediare. Fiecare nod este evaluat în continuare şi poate fi decupat, la rândul său, în mai multe submulţimi. Procesul continuă în această manieră până când se ajunge la noduri terminale nedecompozabile. Există câte un drum unic de la rădăcină la fiecare nod terminal. Fiecare înregistrare care intră în arbore este dirijată, în funcţie de conţinutul său, spre o ramură sau alta, până când se ajunge la un nod terminal. Cu alte cuvinte, înregistrarea este inclusă în clasa pe care o reprezintă nodul terminal în care a ajuns; drumul pe care l-a parcurs până la acesta este expresia unei reguli de clasificare.

În tratarea efectivă a datelor, atributele sunt grupate în două categorii: dependente şi independente. Mai precis, există un singur atribut dependent, numit şi atribut ţintă, pentru care se caută influenţele exercitate de celelalte atribute, independente. Dintre toate, se selectează cel care are impactul cel mai puternic asupra câmpului ţintă, care permite, prin urmare, divizarea ansamblului de înregistrări în submulţimile cele mai relevante. Pentru fiecare submulţime, analiza se reia, având, evident, acelaşi câmp ţintă dar luând în considerare doar atributele rămase, căutând noi şi noi subdivizări.

După construcţia arborelui, datele noi pot fi încadrate, cu un anumit grad de certitudine, în unul dintre nodurile terminale în funcţie de valorile luate de atributele lor, clasându-le sau putând face astfel predicţii asupra lor.

O bancă doreşte, spre exemplu, să construiască un asemenea arbore pentru clienţii săi persoane fizice cărora le-au fost acordate credite7. Pentru fiecare client se cunosc diverse atribute: vârstă, sex, stare civilă, număr de copii în întreţinere, venit familial anual, locuinţă, ocupaţie, studii etc.

7 Aceste exemplu este inspirat din demonstraţia produsului de data mining Alice.

37

12150 înreg.Probleme:

Da 2724 22,42%Nu 9426 77,58%

Locuinţă: proprietate, părinţi

8970 înreg.Probleme:

Da 1875 20,9%Nu 7095 79,1%

Locuinţă: închiriată

3180 înreg.Probleme:

Da 2281 71,7%Nu 899 28,3%

Figura 4-11. Un exemplu de arbore de decizie

Câmpul ţintă, al cărui explicaţie se doreşte, precizează dacă au existat probleme la restituirea creditului. Baza de date conţine 12150 de înregistrări, dintre care 9426 au restituit fără probleme creditele primite.

Din analiză rezultă că atributul cel mai discriminant, care separă cel mai bine înregistrările clienţilor cu şi fără probleme, vizează locuinţa. Se constată astfel că 3180 sunt chiriaşi, restul fiind proprietari sau locuind împreună cu părinţii. Rata celor fără probleme la rambursare este foarte diferită între aceste două categorii: 899, respectiv 28,3% dintre chiriaşi şi 7095, adică 79,1% dintre cei aflaţi în cealaltă categorie. Figura 4-11 prezintă arborele corespunzător acestei situaţii.

Continuând analiza, se identifică pentru fiecare dintre cele două submulţimi alte variabile discriminante şi noi subdiviziuni. Astfel, pentru cei care ocupă o locuinţă închiriată, venitul anual constituie atributul cel mai discriminator, ce evidenţiază, sub raportul ratei de rambursare fără probleme, alte două subdiviziuni. Pentru celălalt grup, atributul cel mai discriminant este vârsta8. Fiecare cale din arbore exprimă, aşa cum s-a menţionat, o regulă de clasificare în raport cu atributul ţintă. Spre exemplu:

Dacă locuinţă închiriată şi venit anual < 48 milioane lei atunci probleme la rambursare

8 Exemplul este absolut ipotetic, fără nici o legătură cu realitatea.

38

12150 înreg.Probleme:

Da 2724 22,42%Nu 9426 77,58%

Locuinţă: propr, părinţi8970 înreg.Probleme:

Da 1875 20,9%Nu 7095 79,1%

Locuinţă: închiriată3180 înreg.Probleme:

Da 2281 71,7%Nu 899 28,3%

Vârstă: <331284 înreg.Probleme:

Da 992 77,3%Nu 292 22,7%

Vârstă: 33-456480 înreg.Probleme:

Da 3186 49,2%Nu 3294 50,8%

Vârstă: >451206 înreg.Probleme:

Da 311 25,8%Nu 895 74,2%

Figura 4-12. Arborele de decizie anterior cu un nivel suplimentar

După dezvoltarea completă a arborelui pe baza setului de exemple disponibile, regulile obţinute pot fi folosite pentru a face previziuni referitoare la noii clienţi în privinţa modului de rambursare a creditelor.

Algoritmi de construcţie ai arborilor de decizie

Aşa cum a rezultat din exemplul precedent, găsirea celei mai semnificative variabile stă la baza dezvoltării arborilor de decizie. Produsele program existente folosesc mai mulţi algoritmi pentru rezolvarea acestei probleme.

Una dintre cele mai folosite metode de dezvoltare a arborilor de decizie este CART (Classification and Regression Trees), propusă în anul 1984. Acesta demarează căutând variabila independentă ale căror valori permit cea mai bună divizare. În acest scop, se recurge la calcularea unui indice de diversitate al ansamblului înregistrărilor din perspectiva unui atribut. O valoarea ridicată a indicelui de diversitate semnalează existenţa unei distribuţii relativ uniforme de clase în timp ce o valoare redusă indică predominanţa unei clase în raport cu celelalte. Ceea ce se caută este, prin urmare, o divizare care să conducă la o diminuare cât mai marcată a valorii acestui indice.

Algoritmul prevede parcurgerea atributelor independente unul câte unul şi calcularea reducerii diversităţii pe care ar putea să o aducă divizarea făcută pe baza sa. Variabila reţinută drept criteriu de separare este cea care produce cel mai bun rezultat. Ceea ce se caută este un arbore binar. Atributele cu valori multiple ridică, în aceste condiţii, o problemă suplimentară: regruparea valorilor astfel încât decupajul final să conducă la numai două subdiviziuni. Principiul de evaluare operează şi aici, în următoarea formă: se ordonează valorile în funcţie de reducerea de diversitate pe care o aduc şi se alege cea mai bună dintre ele, celelalte fiind grupate împreună pe cea de a doua ramură.

Pentru fiecare dintre cele două noduri astfel obţinute, se caută o nouă divizare, procedând în aceeaşi manieră. Atunci când nu mai este posibilă reducerea semnificativă a diversităţii prin nici unul dintre atribute, se consideră că nodul respectiv este terminal.

39

Venit: ≤48 mil2289 înreg.Probleme:

Da 2007 87,7%Nu 282 12,3%

Venit: > 48 mil891 înreg.Probleme:

Da 274 30,8%Nu 617 69,2%

În ansamblul său, divizarea se încheie atunci când toate nodurile la care s-a ajuns sunt terminale.

Procedând în această manieră, există riscul de a ajunge la un număr excesiv de noduri, cărora le corespund un număr redus de înregistrări din setul de date tratat (care, cum bine a observat cititorul, servesc drept date de învăţare). Producerea de reguli pe asemenea baze poate fi uneori foarte dăunătoare. Din această cauză, soluţia iniţială este revăzută, în intenţia eliminării acelor ramuri care sunt mai puţin semnificative. În acest scop, se calculează o rată ajustată de eroare pentru fiecare ramură. Subarborii care nu o pot compensa printr-o reducere suficientă a ratei de eroare a arborelui din care fac parte, sunt eliminaţi.

Rata de eroare măsoară câte din înregistrările de intrare sunt incorect plasate în ramura respectivă în raport cu datele de învăţare. Pentru o anumită arborescenţă, aceasta este suma ponderată a ratelor de eroare a ramurilor componente.

După parcurgerea acestui proces, selecţia finală se face pe baza unui set de date de test, aparţinând aceleiaşi populaţii ca şi datele de învăţare dar compus din înregistrări diferite. Pentru a elimina şi mai bine riscurile de încadrare eronată, se recurge la o verificare suplimentară folosind un set de date de evaluare, evident diferit de primele două. Rata de eroare calculată în cursul evaluării este cea folosită pentru aprecierea rezultatelor prelucrării datelor noi.

Un algoritm de dată mai recentă este C4.59, propus de profesorul australian J.R. Quinlan. Spre deosebire de CART, care generază numai arbori binari, un nod poate avea aici un număr variabil de ramuri. O altă diferenţă vine din modul de tratare a variabilelor nominale, care vor avea acum câte o ramură pentru fiecare valoare posibilă. În felul acesta se poate junge rapid la un număr important de ramuri.

Precursorul acestui algoritm, numit ID3, dezvoltat de acelaşi autor, s-a bucurat de o largă popularite şi a fost utilizat în diverse produse informatice. Acesta foloseşte drept criteriu de evaluare a divizărilor câştigul informaţional adus de acestea, respectiv gradul de incertitudine înlăturat, concept derivat din teorema informaţiei a lui Shannon. Cum prin utilizarea sa sunt favorizate arborescenţele numeroase, cărora le vor corespunde un număr redus de înregistrări din setul de exemple, C4.5 foloseşte în această calitate raportul dintre câştigul informaţional total obţinut prin diviziunea respectivă şi câştigul informaţional datorat exclusiv numărului de subansambluri create prin aceasta. Elagajul arborelui se face de asemenea într-o manieră diferită de cea practicată în CART; mai mult decât atât, analiza se bazează tot pe datele de învăţare, fără a mai recurge la date distincte de test sau de evaluare.

În varianta informatică, C4.5 are de asemenea capacitatea de a genera automat reguli, de genul celei exemplificate anterior. Pornind de la setul complet, generat direct pe baza arborelui, programul înlănţuie un demers de generalizare, destinat reducerii numărului de reguli. În acest scop, se elimină, pentru fiecare regulă, anumite condiţii şi se verifică măsura în care acest lucru creşte rata de eroare. O serie de alte transformări mai pot fi

9 Unul dintre produsele program care implementează acest algoritm este Clementine.

40

operate în acest scop, astfel încât, în final, numărul de reguli poate deveni mai mic (sau mult mai mic) decât numărul de noduri terminale.

Cel mai vechi algoritm folosit pentru construirea de arbori de decizie este CHAID (Chi-squared Automatic Interaction Detection), publicat pentru prima oară în 1975. Scopul său principal este acela de a detecta relaţiile statistice existente între variabile şi, în această calitate, face parte din produsele program de statistică, aşa cum sunt SPSS sau SAS. CHAID nu acceptă decât variabile nominative; celelalte trebuie supuse unui proces prealabil de divizare în intervale cu care să fie înlocuite în timpul prelucrării.

Printre perfecţionările propuse în domeniul generării arborilor de decizie, încorporate deja în unele produse program comerciale, se poate menţiona ideea utilizării de combinaţii de atribute în stabilirea punctelor de ramificaţie. În felul acesta, atributele nu mai sunt tratate izolat unul de altul ci în anumite corelaţii, ceea ce are ca efect simplificarea arborelui şi obţinerea unor reguli de clasificare mult mai eficiente.

Prelucrarea seriilor cronologice

Capacitatea de a extrage elemente de previziune pe baza suitei de evenimente produse într-un anumit interval de timp din trecut prezintă un interes deosebit pentru orice organizaţie comercială. Arborii de decizie au fost utilizaţi cu succes şi pentru prelucrări de acest tip dar au fost necesare prelucrări preliminare ale datelor pentru adăugarea de câmpuri care să exprime explicit schimbările dependente de timp.

Societatea Nestlé a recurs la o soluţie de acest tip pentru realizarea unui simulator al procesului de pregătire şi prăjire a cafelei necesare obţinerii diverselor sortimente de cafea solubilă. Fiecare reţetă de fabricaţie solicită condiţii specifice de prăjire, în condiţiile în care acest proces este, în sine, foarte sensibil la diverşi factori perturbatori. În esenţă, simulatorul avea sarcina de a prevedea derularea procesului de prăjire pentru un orizont de câteva minute pe baza funcţionării anterioare, astfel încât să permită detectarea în avans a eventualelor probleme sau incidente şi luarea de măsuri corective înaintea producerii lor efective.

În realizarea sa a fost utilizat un produs informatic ce implementează un demers particular în generarea de arbori de decizie, conceput special pentru extrapolarea de forme secvenţiale. Ideea centrală a acestuia constă în utilizarea de date istorice, denumite în jargonul produsului “cazuri”, pentru a obţine reguli de generare a unui caz nou pe baza cazurilor existente. Spre deosebire de funcţionarea algoritmilor menţionaţi anterior, aceasta înseamnă proiecţia valorii tuturor atributelor. Pentru fiecare atribut, acest lucru se obţine cu ajutorul unui arbore de decizie bazat pe toate caracteristicile cazului precedent şi pe interpretările acestuia (unele interpretări fiind furnizate sau modificate de utilizatorul uman). Simulatorul a fost construit folosind un set de 34000 înregistrări cronologice şi a fost testat cu alte 40000 de înregistrări. Pentru fiecare înregsitrare de test, s-au generat predicţii pentru 60 de perioade viitoare (cu o durată de 30 de secunde fiecare). Simulatorul s-a dovedit mai precis decât oricare dintre specialiştii în

41

domeniu. Mai mult decât atât, a fost posibilă îmbunătăţirea performanţelor acestora cu ajutorul său.

Avantajele şi limitele utilizării arborilor de decizie

Arborii de decizie constituie o tehnică cu multiple utilizări în practică. Faptul că rezultatele pe care le produc îmbracă forma unor reguli explicite constituie un avantaj important. Acestea permit, spre exemplu, identificarea criteriilor preponderente în cumpărarea unui produs sau în percepţia unei campanii publicitare, explicarea evoluţiei vânzărilor pe produse sau pe regiuni, analizarea calităţii furnizorilor, relevarea cauzelor depăşirilor bugetelor sau întârzierilor în atingerea unor obiective, detectarea factorilor ce pot indica preventiv un risc de neachitare a obligaţiilor financiare, analiza orelor suplimentare sau a sporurilor de salarii etc.

Inducţia de reguli şi arborii de decizie sunt deosebit de adecvaţi în toate situaţiile de gestiune în care se operează în mod natural cu reguli. Unele reguli complicate sau mascate de volumul foarte mare de fapte sunt bine identificate şi prezentate prin intermediul acestei tehnici.

Regulile obţinute au marea calitate de a evidenţia cu pregnanţă variabilele care, înt-un anumit domeniu sau problemă, sunt realmente importante.

Arborii de decizie rămân, cu toate perfecţionările aduse, neadecvaţi pentru rezolvarea de probleme ale căror rezultate iau valori continue, cum ar fi, spre exemplu, determinarea venitului sau stabilirea unei rate a dobînzii. De asemenea, folosirea lor pentru prelucrarea de serii cronologice, date frecvent întâlnite şi foarte importante în activitatea economică, solicită eforturi particulare de prezentare a datelor.

4.12 Alte tehnici şi metode de data mining

Tehnicile de data minig prezentate anterior constituie o parte dintr-un ansamblu mult mai cuprinzător, atât în planul metodelor şi algoritmilor dezvoltaţi în condiţii de laborator, cât şi al celor implementaţi de diverse produse program şi utilizaţi intens în practică. De altfel, chiar în raport cu enumerarea din paragrafele anterioare, prezentarea este parţială. În completare, vor fi foarte rapid trecute în revistă alte câteva tehnici, urmând ca cititorul intersat să găsească detalii suplimentare în literatura de specialitate.

Analiza asocierilor, denumită şi “analiza coşului gospodinei” urmăreşte să găsească regulile care descriu apariţia frecventă împreună a unor obiecte eterogene. Rezultatele generate primesc o formă explicită şi simplă, care favorizează înţelegerea şi aplicarea lor concretă. Tehnica se poate aplica pentru căutarea nedirijată de informaţii şi este foarte puţin pretenţioasă sub aspectul tipului şi conţinutului datelor tratate. Calculele necesare sunt simple, ceea ce la face aplicabile şi pe un procesor de tabele, cu condiţia încadrării volumului de date în capacitatea de memorare a

42

acestuia. În principiu, această tehnică poate fi aplicată oricăror tranzacţii comerciale, putând servi pentru analiza vânzărilor din supermatek-uri, analiza mişcărilor de fonduri dintr-o bancă, analiza incidentelor de asigurare etc.

Reţelele de tip Bayes urmăresc să exprime legăturile dintre variabile prin analiza probabilităţilor de apariţie şi a determinărilor reciproce dintre acestea. În raport cu celelalte tehnici de data mining, posedă calitatea de a comporta foarte bine faţă de datele lipsă sau deformate de factori aleatori. teriorate. Una dintre utilizările menţionate în literatura de specialitate pentru această tehnică vizează predicţia riscurilor de neplată. Consumul important de resurse de calcul constituie o explicaţie a utilizării lor mai restrânse. Cu toate acestea, ultimii ani marchează o creştere o ofertei de produse program care le implementează.

În sfârşit, literatura de specialitate menţionează de asemenea aplicaţii ale unor metode provenite din teoria grafelor, pentru a obţine o descriere preliminară a legăturilor dintre elemente, înainte de a trece la aprofundarea studierii lor prin tehnici de genul celor prezentate anterior.

43