Introducere In Descoperirea Cunostintelor Data Mining

Introducere

în

descoperirea cunoștințelor

DATA MINING

Capitolul 1

INTRODUCERE

1.1 Necesitatea apariției unei noi tehnologii

de manipulare a datelor

Bazele de date pot ajunge în zilele noastre pînã la dimensiuni exprimate în terabytes (mai mult de 1015 biți de date). În interiorul acestor masive de date se gãsesc informații de o importanțã strategicã. Se pune problema cum putem trage o concluzie semnificativã despre acest masiv de date având în vedere diversitatea informației conținutã.

Cel mai nou rãspuns este data mining, tehnicã folositã în industrie atât pentru a crește veniturile, cât și pentru a reduce costurile. Câștigurile potențiale sunt enorme. Organizații inovatoare din întreaga lume folosesc deja tehnologia data mining pentru a localiza și apela la clienți cu potențial financiar, pentru a reconfigura ofertele lor de produse pentru a mãri vânzarile și sã minimizeze pierderile datorate erorilor sau fraudelor.

Procesul data mining folosește o varietate largã de unelte de analizã a datelor pentru a descoperi tipare și relații de legaturã între date care pot fi folosite pentru a face predicții valide.

Primul și cel mai simplu pas analitic în data mining este descrierea datelor (trecerea în revista a tuturor atributelor statistice precum valorile medii și abaterile standard, vizualizarea folosind grafice și grafuri și cãutarea potențialelor legaturi semnificative între variabile, precum valori care apar frecvent. Trebuie accentuat cã în data mining, colectarea, explorarea și selectarea datelor semnificative are o importanțã criticã.

Însã numai descrierea datelor nu poate oferi și un plan de acțiune.Trebuie construit și un model predictiv bazat pe tiparele determinate din rezultatele cunoscute și apoi trebuie testat acest model pe rezultate diferite de cele inițiale. Un model reușit nu trebuie niciodatã confundat cu realitatea (se stie cã o hartã a drumurilor nu este o reprezentare fidelã a drumului) dar poate fi un ghid practic pentru a întelege o afacere.

Ultimul pas într-o tehnicã data mining este verificarea empiricã a modelului. De exemplu, dintr-o bazã de date a clienților care deja au rãspuns la o anumitã ofertã, se poate construi un model care prezice care potențiali cumpãrãtori vor rãspunde aceleași oferte.

Tehnicile data mining se referã la automatizarea procesului de cãutare a tiparelor în masive de date și de gãsirea rãspunsurilor la întrebãrile:

Care tipare sunt interesante?

Care tipare sunt false?

Care tipare pot fi exploatate?

1.2 Posibilitãți oferite de tehnicile data mining

O tehnicã data mining este o unealta care necesitã îndrumare umanã experimentatã. Nu este suficient ca tehnica aleasã sã fie implementatã în baza de date și sã se aștepte ca aceasta sã atenționeze utilizatorul în momentul în care „vede” un tipar interesant. Existența tehnicilor data mining nu elimina nevoia ca utilizatorul sã-și cunoasca afacerea, sã-și înțeleagã datele și metodele analitice.O tehnica data mining asista analiștii prin gãsirea tiparelor și relațiilor dintre date, dar nu spune valoarea tiparului pentru organizație. Mai mult, tiparul descoperit de aceasta tehnicã trebuie verificat în lumea realã.

Trebuie amintit cã relațiile predictive gãsite prin intermediul tehnicilor data mining nu sunt neapãrat cauzele unei acțiuni sau comportament. De exemplu, o tehnicã data mining poate determina cã bãrbații cu venituri între anumite limite care se aboneazã la o anumitã revistã sunt posibili cumparatori ai unui produs care se dorește a fi vândut. În timp ce se folosește acest tipar, țintind cãtre cumparatori care sã se încadreze în el, nu trebuie sã se presupunã cã vreunul din factori îi determina sã cumpere acel produs.

Pentru mai multã siguranțã în obținerea unor rezultate semnificative, este foarte importantã înțelegerea datelor. Calitatea „ieșirilor” va fi deseori sensibilã la valori ale datelor care sunt diferite de valorile tipice din baza de date, la categorii irelevante sau categorii care variazã împreuna (precum vârsta și data nașterii), la felul cum sunt codificate datele, la datele care sunt luate în calcul și datele care sunt excluse. Sensibilitatea algoritmilor la astfel de probleme variazã, dar nu este recomandabil sã se depindã doar de un produs al unei tehnici data mining pentru a lua toate deciziile corecte.

O tehnica de forare în date nu descoperã automat soluții fãrã îndrumare.Decât sã se fixeze un scop vag, precum cererea ajutorului pentru a crește numãrul de rãspunsuri la o anumitã ofertã, mai bine se foreazã pentru a gãsi caracteristicile celor care rãspund unor anumite solicitãri și fac o importantã achiziție. Tiparele pe care o tehnicã data mining le va gãsi pentru cele douã scopuri pot fi foarte diferite.

Deși o unealtã eficienta de tip data mining ferește oarecum utilizatorul de complexitatea tehnicilor statistice, cere ca acesta sã înțeleagã activițile uneltelor pe care le alege și algoritmii pe care acestea se bazeazã. Alegerile pe care utilizatorul le face în programarea instrumentelor și optimizãrile asupra lor va afecta acuratețea și viteza modelelor.

O tehnicã data mining nu înlocuiește analiștii în afaceri sau managerii, ci le oferã o unealtã nouã și puternicã pentru a-și îmbunãtãți munca pe care o fac. Orice companie care își cunoaște afacerea are în vedere tipare importante pe care angajații le-au observat de-a lungul anilor. Ceea ce poate sã facã o tehnicã data mining este sã confirme astfel de observații empirice și sã gãseascã tipare noi și subtile care produc creșteri stabile, sau uneori adevãrate explozii.

1.3 Tehnicile data mining si

depozitarea datelor

În mod frecvent, datele care urmeazã a fi prelucrate în cadrul data mining sunt mai întâi extrase din „depozitul” de date al unei intreprinderi într-o bazã de date de forare sau într-un data mart. Este avantajos dacã datele fac parte deja dintr-un depozit. Problema „curațãrii” datelor pentru un depozit de date și pentru o tehnicã data mining sunt similare. Daca datele au fost deja curãțate pentru un depozit atunci este destul de probabil cã nu vor mai avea nevoie de alte verificãri pentru a fi forate. Mai mult, deja au fost rezolvate probleme de consolidare a datelor și aranjate proceduri de întreținere.

Baza de date pentru data mining este mai degrabã un subset logic decât fizic al depozitului de date, asta dacã depozitul poate suporta resursele adiționale cerute de data mining. Daca nu, este mai bine sã se foloseascã o bazã de date separatã.

Un depozit de date nu este o cerințã obligatorie pentu o tehnicã data mining. Construirea unui depozit uriaș, care adunã date din surse multiple, rezolvã problema integritãții datelor și încarcã datele într-o bazã de date de interogare însã poate presupune un efort imens, câteodatã durând ani întregi și costând sume uriașe. Se poate oricum sã se foreze datele dintr-una sau mai multe baze de date operaționale sau tranzacționale pur și simplu extrãgându-le într-o bazã de date din care se poate doar citi informație.Aceasta bazã de date nouã funcționeazã ca un subset de date.

1.4 Data mining și OLAP

Una dintre cele mai comune întrebari ale profesioniștilor care proceseazã date este în legãturã cu diferența dintre data mining și OLAP (On-Line Analytical Processing). Cele douã tehnici sunt unelte diferite, care se pot completa însã una pe cealaltã.

OLAP face parte din spectrul uneltelor folosite ca suport pentru decizii. Interogãrile tradiționale și uneltele de raport descriu ceea ce este într-o bazã de date. OLAP merge mai departe: este folosit pentru a rãspunde de ce anumite lucruri sunt adevãrate. Utilizatorul formuleazã o ipotezã despre o relație și apoi o verificã cu o serie de interogãri asupra datelor. De exemplu, un analist încearcã determinarea factorilor care duc la refuzul unui împrumut. El poate presupune inițial cã oamenii cu venituri mici prezintã riscuri mari de creditare și apoi poate analiza baza de date cu OLAP pentru a verifica ipoteza fãcutã. Dacã acea ipotezã nu a reieșit din datele analizate, analistul poate privi datoriile mari ca un determinant al riscului. Dacã datele nu au susținut nici aceastã ipotezã el poate încerca sã foloseascã drept predictor pentru riscul creditului atât datoriile, cât și venitul.

Cu alte cuvinte, analistul OLAP genereazã o serie de tipare ipotetice și relații și folosește interogãrile asupra bazelor de date pentru a le confirma, sau pentru a le respinge. Analistul OLAP este esențial pentru procesul de deducție. Dar în momentul în care numãrul variabilelor de analizat este de ordinul sutelor devine mult mai dificil și dureazã mult mai mult gãsirea unei ipoteze bune (este vorba despre siguranța cã nu existã o explicație mai bunã decât cea gãsitã) și despre analiza bazelor de date cu OLAP pentru confirmarea sau respingerea acestei ipoteze.

Data mining este diferitã ca tehnicã de OLAP pentru cã în loc sã verifice tipare ipotetice, folosește ea însãși datele pentru a descoperi asemenea tipare. Este în mod esențial un proces de inducție. De exemplu, presupunând cã analistul care voia sã identifice factorii de risc pentru un împrumut folosește o unealtã data mining. Aceasta poate descoperi cã oamenii cu venituri mici și datorii mari prezintã riscuri mari pentru împrumut (ca și anterior) dar poate merge mai departe și sã descopere un tipar pe care analistul nu l-a gândit, precum faptul cã și vârsta este un determinant al riscului.

În acest sens, OLAP și data mining se pot completa una pe cealaltã, ca tehnici. Înainte de a acționa conform tiparului, analistul are nevoie sã știe care sunt implicațiile financiare dacã se va folosi tiparul descoperit. OLAP permite analistului sã rãspundã la acest gen de întrebãri. Mai mult, OLAP este de asemenea complementar în stãrile incipiente ale procesului de descoperire a cunoștințelor, deoarece poate ajuta la explorarea datelor, de exemplu, prin concentrarea atenției asupra unor variabile importante, prin identificarea excepțiilor sau prin gãsirea interacțiunilor. Acest lucru este important pentru cã, cu cât sunt înțelese mai bine datele, cu atât mai eficient este procesul de descoperire a cunoștințelor.

1.5 Data mining, învãțarea automatelor

și statistica

Data mining profitã de progresele fãcute în domeniul inteligenței artificiale și statisticii. Ambele discipline au lucrat asupra problemelor de recunoaștere a tiparelor și clasificarea lor. Ambele comunitați și-au adus contribuții importante pentru înțelegerea și aplicarea rețelelor neuronale și ale arborilor de decizie.

Data mining nu înlocuiește tehnicile statistice tradiționale. Mai degrabã, este o extensie a metodelor statistice care este parțial un rezultat al schimbãrilor majore în comunitatea statisticã. Dezvoltarea celor mai multe tehnici statistice a fost pânã de curând bazatã pe teoria elegantã și metodele analitice care au lucrat destul de bine pe o cantitate modestã de date de analizat. Puterea crescutã a computerelor și prețul lor mai mic, alãturi de nevoia de a analiza seturi imense de date, cu milioane de linii, au permis dezvoltarea de noi tehnici bazate pe explorarea prin forțã brutã a soluțiilor posibile.

Noile tehnici includ algoritmi relativ recenți precum rețelele neuronale și arbori de decizie dar și noi abordãri ale vechilor algoritmi, precum analiza diferențelor. Tehnicile statistice tradiționale se bazeazã pe modelatoare pentru a exprima forma funcționalã și interacțiunile.

Punctul cheie în data mining este aplicarea acestor tehnici statistice sau de inteligența artificiala în probleme comune ale afacerilor într-un mod în care aceste tehnici, accesibile atât celor care lucreazã cu cunoștințe, cât și profesioniștilor în statisticã. Data mining este o unealta prin care se crește productivitatea celor care încearcã sã construiascã modele predictive.

1.6 Data mining și tendințele hardware

și software

Puternica scãdere a prețurilor discurilor de stocare pentru computere în ultimii ani a schimbat economia în ceea ce privește colectarea șectarea și stocarea cantitaților imense de date. Scãderea costurilor și în privința procesoarelor a fost la fel de puternicã. Fiecare generație de chip-uri mãrește considerabil puterea CPU pe lângã alte scãderi pe curba prețurilor. Acest lucru se reflectã în prețul RAM, unde costul unui megabyte a scãzut de câteva sute de ori în doar câțiva ani.

În timp ce puterea unui CPU individual a crescut considerabil, s-a avansat cu cercetarea și în domeniul arhitecturii calculatoarelor paralele. Virtual, astãzi toate serverele suportã CPU multiple și, folosind multiprocesarea simetricã și ciorchini de astfel de servere SMP pot fi create sisteme ce permit la sute de CPU sã lucreze pentru gãsirea unor tipare în date.

Progresul fãcut în sistemele de management al bazelor de date, profitând de acest paralelism în hardware, este benefic pentru data mining. Pentru o problemã complexã de data mining, care cere acces la multe baze de date existente, accesul nativ DBMS asigurã cele mai bune performanțe posibile.

Rezultatul tuturor acestor tendințe descrise este acela cã multe bariere de performanțã pentru gãsirea tiparelor în cantitãți imense de date au fost eliminate.

1.7 Aplicații ale tehnicii data mining

Data mining este o tehnicã din ce în ce mai popularã datoritã contribuțiilor substanțiale pe care le pot avea. Poate fi folositã sã controleze costurile și sã contribuie la creșterea veniturilor.

Multe organizații folosesc data mining pentru a ajuta la administrarea tuturor fazelor ciclului de viațã al consumatorilor, inclusiv la achiziționarea noilor consumatori, creșterea veniturilor de la consumatorii existenți și la reținerea clienților rentabili. Prin determinarea caracteristicilor clienților rentabili (profiling), o companie poate avea ca țintã populații cu aceleași caracteristici. Prin profiling-ul clienților care au cumpãrat un anumit produs se poate îndrepta atenția cãtre clienții similari care au cumpãrat acel produs (cross-selling). Prin profiling-ul clienților care au plecat, o companie poate acționa pentu a reține clienții care prezintã riscul sã plece pentru cã, de obicei, este mult mai ieftin sã reții un client decât sã atragi unul nou.

Data mining oferã valori din întreg spectrul industriei. Companiiile de telecomunicații și cele de carduri de credit dețin supremația în aplicarea tehnologiei data mining în detectarea folosirii frauduloase a serviciilor lor. Companiile de asigurare și bursele de schimb sunt deasemenea interesate de aplicarea acestei tehnologii pentru a reduce fraudele. Aplicațiile medicale sunt altã zonã fructuoasã: tehnica data mining poate fi folositã pentru a prezice eficacitatea unei intervenții chirurgicale, unui test medical, sau a unui tratament medicamentos. Companiile active pe piața financiarã folosesc data mining pentru a determina caracteristicile pieței sau industriei, dar și pentru a prezice ce produse sã fie stocate într-un anumit depozit (și cum sã fie așezate în depozit), precum și pentru a evalua eficacitatea unor promoții sau reduceri. Firmele farmaceutice foreazã în baze de date imense de compuși chimici și de material genetic pentru a descoperi substanțe care ar putea fi candidate la dezvoltarea lor ca agenți pentru tratamentul bolilor.

1.8 Succesul în data mining

Existã douã lucruri esențiale care duc la succesul în data mining. Primul este formularea precisã a problemei care se încearcã a fi rezolvatã. O afirmație concentratã dã de obicei cele mai bune rezultate. Al doilea lucru este folosirea datelor care trebuie. Dupã ce au fost alese dintre datele care stau la dispoziție sau dupã ce au fost cumpãrate din date externe, este necesarã combinarea lor în moduri semnificative pentru interogare.

Cu cât constructorul de model se poate juca cu datele, construi modele, evalua rezultate și lucra cu mai multe date, într-o anumitã unitate de timp, cu atât mai bun va fi modelul rezultat. Drept urmare gradul în care uneltele data mining suportã aceastã explorare interactivã a datelor este mai important decât algoritmul pe care îl folosește. În mod ideal, uneltele de explorare a datelor (grafico-vizuale sau interogative) sunt bine integrate cu algoritmii sau analizele care construiesc modele.

Capitolul 2

DESCRIEREA DATELOR PENTRU

DATA MINING

2.1 Sumarizare și vizualizare

Înainte de a putea fi construit un model predictiv eficient, trebuie sã fie înțelese datele. Se începe prin a aduna o varietate de caracteristici numerice (incluzând descrieri statistice precum mediile, abaterile standard, etc) și prin a observa distribuția datelor. Se pot construi și tabele pivot pentru date multidimensionale.

Datele pot fi continue, având orice valoare numericã, sau categoricale, potrivindu-se în clasele discrete. Datele categoricale pot fi mai departe definite fie ca ordinale, având o anumitã ordine (high, medium, low), sau nominale (neordonate).

Uneltele grafice și de vizualizare sunt un ajutor vital în pregãtirea datelor și importanța lor pentru ca analiza eficientã a datelor nu poate fi supraevaluatã. Vizualizarea datelor oferã cel mai adesea ideea care conduce la noi intuiții și succes. Câteva dintre cele mai comune și utile dispuneri grafice ale datelor sunt histogramele, sau schemele care afișeazã distribuția valorilor. Se pot vizualiza scheme de împrãștiere, în douã sau trei dimensiuni, ale diferitelor perechi de variabile. Abilitatea de a adãuga o a treia, de a supraîncãrca variabile mãrește puternic folosirea din plin a anumitor tipuri de graficã.

Vizualizarea funcționeazã pentru cã exploateazã banda mai largã a informațiilor grafice în comparație cu cea a textului sau a numerelor. Permite oamenilor sã vadã pãdurea și sã se concentreze și asupra copacilor. Tiparele, relațiile, valorile excepționale și valorile lipsã sunt adesea mai ușor de preceput când sunt prezentate grafic, decât atunci când sunt prezentate ca o listã de numere sau text.

Problema în folosirea vizualizãrii provine din faptul cã modelele au mai multe dimensiuni sau variabile, însã oamenii sunt restricționați la a arãta acele dimensiuni pe un monitor bidimensional, sau foaie de hârtie (de exemplu, dacã se dorește vizualizarea relației dintre riscul de credit și vãrstã, sex, stare civilã, ani vechime în muncã). În mod consecvent, uneltele de vizualizare trebuie sã foloseascã reprezentãri inteligente, pentru a cuprinde n dimensiuni în douã. Unelte de vizualizare din ce în ce mai puternice și mai sofisticate sunt dezvoltate, dar de cele mai multe ori necesitã ca oamenii sã-și formeze ochii prin practicã pentru a înțelege informația afișatã. Utilizatorii care nu disting culorile sau cei care nu au orientare în spațiu, pot avea deasemenea probleme cu uneltele de vizualizare.

2.2 Clustering

2.2.1 Definiție și exemple de clustering

Clusteringul împarte o bazã de date în grupuri diferite. Scopul clustering-ului este acela de a gãsi grupuri care sunt foarte diferite unele de altele și pe acei membri care sunt foarte asemãnãtori unii cu alții. Spre deosebire de clasificare, nu se știe care va fi cluster-ul, când se începe, sau dupã care atribute datele vor fi grupate. În mod normal, cineva care are cunoștințe în domeniul afacerilor trebuie sã interpreteze cluster-ul. De obicei este necesarã modificarea cluster-ului prin excluderea variabilelor care au fost angajate în exemple de grupuri pentru cã pe baza examinãrii, utilizatorul le identificã drept irelevante. Dupã ce au fost gãsite cluster-ele care împart rezonabil baza de date, aceste clustere pot fi apoi folosite sã clasifice și date noi. Câțiva dintre cei mai întâlniți algoritmi folosiți pentru clustering includ hãrți Kohonen și K-means.

A nu se confunda clustering-ul cu segmentarea. Segmentarea se referã la problema generalã a identificãrii grupurilor care au caracteristici comune. Clustering-ul este un mod de a segmenta datele în grupuri care nu sunt definite anterior, în timp ce clasificarea este un mod de a segmenta datele asignându-le la grupuri definite anterior.

Exemple de clustering:

1. Cu mulți ani în urmã, în timpul unei epidemii de holerã în Londra, un doctor a marcat locurile unde au fost semnalate cazuri de boalã pe o hartã și a obținut un teren segmentat astfel:

Privite cu atenție, datele aratã cazurile aglomerate în anumite intersecții, unde se aflau fântâni poluate, arãtând astfel nu numai cauza holerei, ci și o soluție a problemei.

2. „Skycat” a împarțit 2*103 corpuri cerești în stele, galaxii, quasari, etc. Fiecare corp era un punct într-un spațiu cu 7 dimensiuni și fiecare dimensiune reprezenta radiația într-o bandã a spectrului. „Sloan Sky Survey” este un program mai ambițios, încercând catalogarea întregului univers vizibil.

3. Documentele pot fi gândite ca puncte într-un spațiu cu un numãr foarte mare de dimensiuni, unde, fiecare dimensiune corespunde unui cuvânt posibil. Poziția documentului într-o dimensiune este datã de numãrul de apariții ale cuvântului în document (sau doar 1 dacã apare și 0 în caz contrar). Clusterele cu documente în acest spațiu de cele mai multe ori corespund cu grupuri de documente cu același subiect.

2.2.2 Mãsurarea distanțelor

Pentru a discuta dacã un set de puncte sunt suficient de apropiate pentru a forma un cluster, este nevoie de o mãsurare a distanței D(x,y), care aratã cât de departe este punctul x de punctul y. Axiomele distanței sunt:

D(x,x) = 0 (distanța de la un punct la el însuși este nulã)

D(x,y) = D(y,x) (distanța este simetricã)

D(x,y) D(x,z) + D(z,y) (inegalitatea triunghiului)

Adesea, punctele pot fi gândite ca „plutind” într-un spațiu euclidian k-dimensional cu distanța dintre douã puncte, x = (x1, x2,…, xk) și y = (y1, y2,…, yk) , datã de una din formulele:

Distanța comunã (norma L 2 ) : D(x,y) =

Distanța Manhattan (norma L 1 ): D(x,y)=

Maximul distanței (norma L ∞ ): D(x,y)=

Când nu existã un spațiu euclidian în care sã fie plasate punctele, clustering-ul devine mai dificil, însã mãsurarea distanței are sens și în spații neeuclidiene, dupã cum reiese și din exemplele urmãtoare:

Paginile web pot fi privite ca puncte într-un spațiu cu 10n dimensiuni, unde fiecare dimensiune corespunde unui cuvânt. Ținând cont de faptul cã, oricum calculul distanței într-un spațiu cu atât de multe dimensiuni ar fi imposibil, o abordare mai bunã a calculului este cea bazatã pe produsul vectorial al vectorilor x și y, având de a face doar cu cuvinte care apar atât în x cât și în y. Trebuie calculatã lungimea vectorilor implicați, care este radicalul sumei pãtratelor numãrului de apariții pentru fiecare cuvânt. Suma produselor aparițiilor fiecãrui cuvânt în fiecare document se împarte la fiecare lungime pentru a obține un produs vectorial normalizat. Scãzând aceastã cantitate din 1 se obține distanța dintre x și y.

De exemplu, presupunând cã existã doar patru cuvinte care prezintã interes și vectorii x = (2, 0, 3, 1) și y = (5, 3, 2, 0) care reprezintã numãrul de apariții al acestor cuvinte în douã documente. Produsul vectorial xy este dat de:

2 * 5 + 0* 3 + 1 * 0 = 16,

lungimea primului vector este:

,

iar lungimea celui de-al doilea vector este:

,

de unde:

D(x,y) = 1- = 0,

Adicã x și y sunt practic același document; desigur, nu au același subiect, dar în mod sigur vor ține de același cluster.

Șirurile de caractere, precum secvențele ADN pot fi similare chiar dacã se fac anumite inserții sau ștergeri, dar și schimbãri în unele caractere. De exemplu, „abcde” și „bcdxye” sunt oarecum asemãnãtoare chiar dacã nu au nici o poziție în comun și nici mãcar aceeași lungime. Astfel, în loc sã se încerce construirea unui spațiu euclidian cu câte o dimensiune pentru fiecare poziție se poate defini funcția de distanțã:

D(x,y) = -2,

unde LCS reprezintã inițialele de la „longest common subsequence” (cea mai lungã subsecvențã în comun) a șirurilor x și y. În exemplul dat:

LCS(„abcde”,”bcdxye”) = „bcde”, de lungime 4,

deci:

D(„abcde”,”bcdxye”) =5 + 6 – 2 * 4 = 3,

de unde tragem concluzia cã șirurile sunt suficient de apropiate.

Dacã sunt alese puncte întâmplãtoare într-un cub k-dimensional cu latura de o unitate, pentru k=2 se așteaptã ca toate punctele sã fie împrãștiate într-un plan, unele fiind foarte apropiate iar altele aflate la maximul distanței posibile, .

Dacã alegem k un numãr foarte mare , precum 100 sau 100 000 trebuie sã decidem ce normã este mai bine sã folosim, ținând cont de faptul cã:

D(x,y) ≥ , x = (x1, x2,…) și y = (y1, y2,…)

Pentru valori mai mari ale lui k este posibil sã existe dimensiuni i în care xi și yi sunt pe cât posibil diferiți, chiar dacã în alte dimensiuni xi și yi sunt foarte apropiați, de unde:

D(x,y) 1

O altã consecințã interesantã a dimensionalitãții de ordin mare este aceea cã toți vectorii

x = (x1, x2,…) și y = (y1, y2,…) sunt aproape ortogonali deoarece, dacã îi proiectãm pe oricare k/2 plane formate de douã din cele k axe va exista un plan în care vectorii proiectați sunt aproape ortogonali.

2.2.3 Clasificarea algoritmilor de clustering

Algoritmi care folosesc o abordare centroidã

În fiecare cluster se calculeazã centroizi (puncte centrale) iar punctele sunt asignate clusterului care are centroidul cel mai aproape de ele.

Algoritmi care folosesc o abordare ierarhicã

Se începe prin a presupune cã fiecare punct formeazã un cluster. Apoi, în mod repetat, clusterele apropiate se unesc folosind o funcție care mãsoarã cât de apropiate sunt douã clustere (de exemplu distanța dintre centroizi) sau cât de bun va fi clusterul rezultat (de exemplu distanța medie a punctelor din cluster, fațã de centroidul rezultat).

Algoritmul k-Means

Este un algoritm bazat pe memorie. Principiul algoritmului este urmãtorul: algoritmul alege k centroizi de clustere, asigneazã un punct la un cluster alegând cel mai apropiat centroid. În timp ce noi puncte sunt asignate la un cluster, centroidul se poate schimba.

Pentru k=2 se alege exemplul a cinci puncte în spațiul bidimensional și se asigneazã în ordine punctele 1, 2, 3, 4 și 5. Punctele 1 și 2 sunt asignate unor clustere și devin, pentru moment, centroizii lor. Când se ia în considerare punctul 3, presupunem cã este mai aproape de 1, deci 3 este asignat aceluiași cluster cu punctul 1, al cãrui centroid se mutã în punctul a. Când asignãm punctul 4, observãm cã se aflã mai aproape de 2 decât de a, deci 4 se alãturã clusterului în care se aflã și 2, al cãrui centroid se mutã în b. În sfârșit, punctul 5 este mai aproape de a decât de b, deci se alãturã clusterului {1,3}, al cãrui centroid se mutã în c.

Observații:

Centroizii pot fi inițializați alegând puncte suficient de depãrtate de alți centroizi, pânã când obținem k elemente.

În timpul calculului putem decide sã despãrțim un element și sã unim douã pentru a menține totalul la k; un criteriu de a face acest lucru este reducerea distanței medii dintre puncte și centroizii lor.

Dupã ce au fost localizați centroizii pentru k clustere, se pot reasigna toate punctele, deoarece unele puncte care au fost asignate anterior pot ajunge mai aproape de alți centroizi, dupã cum aceștia se schimbã.

Dacã nu suntem siguri de valoarea lui k, putem încerca diferite valori pentru acesta.

Considerând datele din figura urmãtoare, este clar cã numãrul corect de clustere este trei, însã putem încerca mai întâi pentru k=1. Atunci toate punctele se aflã într-un singur cluster și distanța medie fațã de centroid este mare.

Presupunând k=2, unul dintre cele trei clustere va fi de sine stãtãtor, iar celelalte douã vor fi forțate sã se uneascã, dupã cum sugereazã liniile îngroșate. Distanța medie a punctelor fațã de centroid se va micșora considerabil. Pentru k=3, fiecare cluster va fi de sine stãtãtor și distanța va scãdea și mai mult. K se poate mãri la 4 și atunci unul dintre clustere va fi artificial partiționat în douã clustere apropiate selectate prin liniile mai subțiri. Distanța medie fațã de centroid va mai scãdea puțin, dar nu prea mult și este o greșealã sã încercãm creșterea lui k.

2.2.5 Algoritmul BFR

Bazat pe tehnica anterioarã, acest algoritm citește datele o singurã datã și le memoreazã. Algoritmul lucreazã cel mai bine când datele urmeazã o distribuție normalã în jurul unui punct central, poate cu o abatere standard diferitã în fiecare dimensiune. Figura urmãtoare demonstreazã cum ar putea arãta datele care aparțin unui cluster tipic cu douã dimensiuni. Un centroid,marcat cu semnul „+” are puncte împrãștiate în jurul sãu cu o deviație standard în spațiul orizontal de douã ori mai mare decât cea din spațiul vertical. Aproximativ 70% din puncte vor fi în interiorul elipsei , 95% vor fi în elipsa 2, 99% vor fi în elipsa 3, iar 99.99% vor fi în elipsa 4.

Dupã ce a lucrat la modelarea „Skycat”, Usama Fayyad a gândit probabil clusterele precum galaxii. Un cluster este compus din:

1. Un miez central, setul de înlãturat (DS – Discard Set) și este format din punctele care aparțin cu siguranțã clusterului. Toate punctele din acest set sunt înlocuite cu niște statistici. Deși punctele sunt numite de înlãturat, ele au un rol important în reglarea algoritmului, deoarece ele determinã poziția centroidului și deviația standard a clusterelor în fiecare dimensiune.

2. Un set de reducere (CS – Compression Set), format din puncte care înconjoarã subgalaxiile. CS constã în puncte care sunt suficient de apropiate unele de altele încât sã poatã fi înlocuite cu o statisticã, așa cum DS este pentru cluster. Oricum, sunt suficient de îndepãrtate de orice centroid încât sã nu putem fi siguri cãrui cluster îi aparțin.

3. „Stelele individuale” nu fac parte din galaxie sau subgalaxie și formeazã setul de reținut (RS – Retained Set). Aceste puncte nu pot fi asignate nici unui cluster, și nici nu pot fi grupate într-un subcluster al CS. Sunt stocate în memoria principalã, ca puncte individuale, împreunã cu statisticile despre DS și CS.

Datele statistice folosite sã reprezinte fiecare cluster din DS și CS sunt:

Numãrul de puncte N;

Vectorul sumelor coordonatelor punctelor din fiecare dimensiune; vectorul se numește SUM și componenta sa din dimensiunea i este SUMi ;

Vectorul sumelor pãtratelor coordonatelor punctelor din fiecare dimensiune,numit SUMSQ și componenta sa din dimensiunea i este SUMSQi.

Se observã cã aceste tipuri de informații, în numãr de 2k + 1 în cazul a k dimensiuni, sunt suficiente pentru a efectua calculele statistice importante pentru clustere și subclustere și este mai convenabil sã se menținã pe parcursul adãugãrii de noi puncte la clustere.

De exemplu:

– coordonata yi a centroidului clusterului în dimensiunea i este SUMi/N;

– variația în dimensiunea i este:

,

iar deviația standard σi este radicalul acestei expresii.

Procesarea punctelor în BFR

La fiecare încãrcare a punctelor în memorie BFR selecteazã centroizii celor k clustere folosind algoritmi precum: se alege un set de puncte, se optimizeazã clusterele și se aleg centroizii. Tot setul de puncte care se va încãrca ulterior în memorie.

1. Se calculeazã care puncte sunt suficient de aproape, deci pot fi incluse în DS și caracteristicile lor (N, SUM, SUMSQ) vor fi combinate cu calculele statistice precedente ale clusterului. BRF oferã douã moduride a determina dacã un punct este suficient de aproape de un centroid pentru a intra în DS.

Se aleg toate punctele ale cãror raze Mahalanobis sunt mai mici decât o anumitã valoare, de exemplu, de patru ori deviația standarda clusterului. Aceastã razã este de fapt distanța fațã de centroid, împãrțitã în fiecare dimensiune i prin σi, deviația standard în acea dimensiune. Mai exact, dacã μi este media în dimensiunea i, atunci raza pentru punctul y = (y1, y2, …) este:

Ry =

În funcție de numãrul de puncte în diferite clustere verificãm dacã (mãcar cu o oarecare probabilitate) cel mai apropiat centroid curent se va deplasa în viitor suficient de departe de punctul y și alt centroid se va muta suficient de aproape de y, mai aproape chiar decât fusese primul. Este puțin probabil ca cel mai apropiat centroid pentru y va fi mereu diferit, apoi y va fi asignat la DS și plasat în clusterul celui mai apropiat centroid.

2. Se ajusteazã valorile N, SUM și SUMSQ pentru fiecare cluster pentru a lua în calcul și punctele introduse în DS.

3. Se încearcã asignarea la clustere a punctelor care nu au fost plasate în DS, inclusiv punctele din RS din etapele anterioare. Dacã se gãsește un cluster a cãrui varianțã este dincolo de o limitã aleasã, atunci aceste puncte vor fi considerate ca un subcluster, înlocuite cu statisticile lor și considerate o parte din CS. Toate celelalte puncte sunt plasate în RS.

4. Dacã considerãm cazul contopirii unui nou subcluster cu unul precedent din CS, testul trebuie fãcut pentru a vedea dacã acest lucru este avantajos și constã în compararea varianței setului de puncte combinate cu limita aleasã. Trebuie observat cã statisticile memorate despre subclusterele din CS sunt suficiente pentru a calcula varianța setului combinat.

5. Dacã ne aflãm la ultima etapã (nu mai avem date), atunci putem asigna clusterele din CS și punctele din RS celor mai apropiate clustere chiar dacã par destul de îndepãrtate de centroidul clusterului

Problema construirii spațiului euclidian

cu mãsurarea distanțelor

Oricare n puncte pot fi plasate într-un spațiu cu n-1 dimensiuni, date fiind distanțele dintre puncte.

În cazul particular a trei puncte: se dau punctele a, b, c care trebuie plasate într-un spațiu bidimensional fiind date distanțele dintre ele, calculate cu funcția D(x,y).

Rezolvare:

Se fixeazã punctele a și b și astfel apare distanța D(a,b). Se deseneazã un cerc de razã D(a,c) în jurul lui a și un cerc de razã D(b,c) în jurul lui b; datoritã inegalitãții triunghiurilor, cercurile se intersecteazã iar unul din cele douã puncte de intersecție este ales ca fiind c.

În cazul general avem mult prea multe puncte pentru a încerca sã le așezãm într-un spațiu cu doar o dimensiune mai puțin decât numãrul de puncte. O altã abordare este plasarea a n puncte într-un spațiu k-dimensional, unde k<<n se numește scalã multidimensionalã.

Rezolvare în cazul general:

Se începe cu n puncte plasate aleator în spațiul k-dimensional;

Se ia ca eroare, energia unui sistem de sãrituri, fiecare de lungime D(x,y), executate între fiecare pereche de puncte x și y; energia dintr-o sãriturã este pãtratul diferenței dintre lungimea ei realã și D(x,y);

Se viziteazã fiecare punct pe rând și se încearcã plasarea lui într-o poziție care sã minimizeze totalul de energie al sãriturilor; deoarece mutarea punctelor poate afecta poziția optimã a celorlalte puncte, punctele trebuie vizitate în mod repetat pânã când nici o îmbunãtãțire nu mai pote fi fãcutã. În acest moment, am aflat un optim local, care însã nu coincide obligatoriu cu un optim global.

Dacã avem, de exemplu trei puncte așezate într-un triunghi dreptunghic (3-4-5), dacã încercãm plasarea acestora într-o dimensiune, vor apãrea mãriri și micșorãri ale salturilor. Configurația optimã este atunci când salturile de lungime 3 și 4 sunt micșorate la 7/3 și 10/3, iar saltul de lungime 5 este „întins” la 17/3. Totalul de energie din aceastã configurație este:

2.2.6 Maparea rapidã (Fastmap)

Problemã:

Scalarea multidimensionalã are o complexitate în timp de cel puțin O(n2) pentru n puncte, deoarece trebuie calculate distanțele cel puțin odatã. Maparea rapidã este o metodã care ganereazã k pseudo-axe care servesc la plasarea a n puncte într-un spațiu k-dimensional, cu o complexitate în timp de O(nk). Fastmap alege k perechi de puncte (ai, bi), fiecare servind drept capete pentru una dintre cele k axe.Folosind teorema cosinusurilor, putem calcula proiecția xi a oricãrui punct c de pe linia ab, folosind doar distanțele între puncte și nici o altã coordonatã presupusã.

x =

Dupã ce s-a ales o pereche de puncte (a,b) ca axã, o parte din distanța dintre oricare puncte c și d se calculeazã prin proiecțiile lui c și d pe pe linia ab iar restul distanței ține de altã dimensiune. Dacã proiecțiile lui c și d sunt x și y, atunci înlocuim distanța datã dintre c și d cu o distanțã curentã dintre c și a datã de formula:

Acesta este principiul algoritmului de Fastmap: calculeazã pentru fiecare punct c, k proiecții pe care le notãm cu c(1),c(2),…,c(k) pe k axe care sunt determinate de perechile de puncte (a1, b1), (a2, b2),…, (ak, bk). Pentru i=1, 2, … ,k se parcurg urmãtorii pași:

Folosind distanța curentã Dcurent, se aleg ai, bi, dupã cum urmeazã:

(a) se alege un punct aleator c;

(b) se alege un punct ai pe cât de departe posibil de ci folosind Dcurent;

(c) se alege bi pe cât de departe posibil de ai .

Pentru fiecare punct x, se calculeazã x(i) folosind formulele cosinusurilor;

Se schimbã definiția lui Dcurent, astfel:

2.2.7 Clustering ierarhic

Este o tehnicã generalã care prezintã pericolul unei complexitãți de O(n2) pentru clustering-ul a n puncte în clustere ierarhice.

Fiecare punct ocupã un singur cluster, inițial;

Se selecteazã în mod repetat douã clustere sã se uneascã; în general se aleg douã clustere care sunt cele mai apropiate dar existã mai multe metode de a determina apropierea:

mãsurarea distanței dintre centroizi;

minimul distanței dintre punctele din cluster;

maximul distanței dintre punctele din cluster;

distanța medie dintre nodurile din cluster.

3. Încheierea procesului de unire când se considerã cã avem destul de puține clustere.

(a) prin abordare k-means: se doresc k clustere;

(b) se oprește procesul de unire când singurele clustere care mai pot rezulta din unire nu mai îndeplinesc niște criterii precum: distanța medie a punctelor fațã de centroid este prea mare.

2.2.8 Algoritmul GRGPF

Algoritmul presupune cã existã o mãsurã a distanței, D, dar nu și un spațiu euclidian. Mai presupune cã sunt prea multe date pentru a fi pãstrate în memorie. Structura folositã pentru a stoca clusterele este un R-tree. Nodurile arborelui sunt blocuri de date care diferã dacã nodurile sunt interioare sau sunt frunze:

În frunze sunt stocate date statistice despre clustere asemãnãtoare cu cele din BFR. Oricum, din momentul în care nu este spațiu euclidian, apar și diferențe:

N – numãrul de puncte din cluster;

Clustroidul – acel punct din cluster care minimizeazã suma liniilor, adicã suma pãtratelor distanțelor:

– dacã este un cluster, acesta își va indica clustroizii;

– suma liniilor clustroidului este:

;

– suma liniilor clustroidului este corespondenta pentru statistica SUMSQ folositã în BFR. Oricum, SUMSQ necesitã un spațiu euclidian, pe când GRGPF nu necesitã un astfel de spațiu. Suma liniilor poate fi folositã pentru a calcula o statisticã, raza unui cluster care este corespondenta deviației standard dintr-un cluster în BFR. Formula pentru aceasta este:

raza =

Cele p puncte din cluster care sunt cel mai aproape de clustroid și sumele liniilor pentru ele, pentru un p constant;

Cele p puncte din cluster care sunt cel mai departe de clustroid.

În nodurile interioare, sunt pãstrate mostre de clustroizi din clusterele reprezentate de descendentii acestor noduri. Se face un efort în a trece subclusterele în fiecare clasã a subarborilor. Ca în orice R-tree, nodurile interioare oferã informații despre regiunea aproximativã unde sunt gãsite clusterele și descendenții lor. Când se dorește inserarea unui punct într-un cluster se începe de la rãdãcinã și se coboarã în arbore, alegând doar acele cãi de-a lungul cãrora se poate gãsi un cluster rezonabil de apropiat, judecând dupã mostrele din fiecare nod.

Mentenanța clusterelor oferitã de GRGPF

Existã o fazã de inițializare a memoriei cu date, în care se face estimarea clusterelor și acestea sunt aranjate în ierarhia corespunzãtoare unui R-tree. Apoi sunt examinate toate celelalte puncte și inserate în clusterele existente. Alegerea clusterelor este reconsideratã dacã acestea sunt prea multe pentru a se potrivi reprezentãrii în memorie sau dacã un cluster devine prea mare (de o razã mult prea extinsã). Existã multe detalii despre ceea ce se întâmplã când un nou punct este adãugat. Iatã câteva dintre ele:

un punct nou, X, este plasat în clusterul C dupã cum distanța D(X,C) este minimã. Se folosesc mostrele din nodurile interioare ale arborelui pentru a evita cãutarea în întregul arbore și toate clusterele;

dacã un punct X este adãugat clusterului C, se adaugã la fiecare dintre 2p+1 sume de coloane reținut pentru acel cluster (suma liniilor din C, cele mai apropiate p puncte și cele mai depãrtate p puncte) pãtratul distanței dintre acesta și punctul X. De asemenea, se estimeazã suma liniilor pentru X ca fiind Nr2+ND(C,X), unde r este raza clusterului. Validitatea acestei formule, ca aproximare, se bazeazã pe calculul în spațiile cu mai multe dimensiuni. Adicã, pentru fiecare din cele N puncte Y din cluster, distanța dintre X și Y poate fi mãsuratã „mergând” pânã la clustroid (termenul D(C,X)) și apoi de la clustroid la Y (contribuția lui Y la razã). Dacã presupunem cã liniile (într-un spațiu presupus euclidian) de la X la Y sunt aproape perpendiculare, atunci formula este justificatã de teorema pitagorianã.

Trebuie luatã în calcul probabilitatea ca, dupã adãugarea lui X, clusterul C sã aibã clustroizi diferiți care poate fi X sau unul dintre cele p puncte apropiate de C. Dacã, dupã refacerea calculelor prin includerea luix, unul dintre acele puncte va avea o sumã a liniilor mai micã și va deveni clustroid. Evident cã acest proces nu poate ține la nesfârșit, deoarece clustroidul poate migra la un moment dat în afara celor p puncte apropiate.

Contopirea și separarea clusterelor în GRGPF

Câteodatã, raza unui clustroid depãșește o limitã și algoritmul decide sã despartã clusterul în douã. Acest proces cere aducerea întregului cluster în memoria principalã și aplicarea unui algoritm de separare doar acestor puncte în memorie.

O consecințã iminentã este creșterea cu 1 a numãrului clusterelor dintr-un nod. Dacã nodul se supraîncarcã, acesta trebuie separat ca într-un B-tree. Acest lucru, la rândul lui, poate cauza separarea nodurilor din arbore de deasupra nodului în cauzã și, în cel mai rãu caz, nu va mai fi spațiu în memoria principalã pentru a reține întregul arbore în continuare.

În acest caz, soluția este creșterea limitei razei pe care un cluster poate sã o aibã și sã se încerce contopirea clusterelor din cadrul arborelui. Presupunem cã se unesc clusterele Ci și Cj. Se încearcã evitarea aducerii tuturor punctelor acestor clustere în memoria principalãși se încearcã aproximarea clustroidului și a sumei liniilor astfel:

Se presupune cã clustroidul clusterului combinat va fi unul dintre punctele cele mai îndepãrtate de clustroizii atât pentru Ci cât și pentru Cj. Amintim faptul cã aceste puncte sunt toate pãstrate în arbore cu toate caracteristicile generate de clusterul de care aparțin.

Pentru a decide care este noul clustroid, trebuie estimatã suma liniilor pentru fiecare punct X din fiecare cluster. Presupunem, de exemplu cã X este în Ci, apoi estimãm:

În acest caz, Nj este numãrul de puncte din Cj, și, ca întotdeauna indicã clustroidul. Explicația pentru formula de deasupra este:

Primul termen reprezintã distanța de la X la toate nodurile din cluster;

Termenul din mijloc reprezintã o bucatã din calea de la X la fiecare punct din Cj. Presupunem calea ca pornind de la X spre , clustroidul lui Ci. De acolo, pleacã la .Se observã cã, datoritã dimensionalitãții multiple putem presupunecã liniile de la X la și de la la sunt perpendiculare, și cã le putem combina folosind teorema lui Pitagora;

Termenul final reprezintã componenta cãii de la X la toți membrii lui Cj , care sunt dincolo de ,privind dinspre X. Din nou, datoritã dimensionalitãții multiple care ne lasã sã presupunem cã toate liniile de la la membrii lui Cj sunt perpendiculare pe linia de la Ci la Cj.

Dupã ce a fost ales noul clustroid, se calculeazã suma liniilor pentru fiecarepunct pe care îl reținem în cluster, folosind formula prezentatã.

2.2.9 Algoritmul CURE

Întorcându-ne la clustering-ul în spațiul euclidian, problema rezolvatã de CURE este cea a variabilelor care nu urmeazã o distribuție normalã, dupã cum cere algoritmul BFR, de unde multe lucruri încep sã nu mai funcționeze în abordarea k-means.

Figurile urmãtoare sugereazã douã posibile probleme. În prima figurã, chiar dacã k = 4 este numãrul potrivit de clustere (cercurile solide reprezintã granițele clusterelor) un algoritm care încearcã sã minimizeze distanțele fațã de un centroid poate sã grupeze punctele dupã cum sugereazã liniile punctate, cu clusterul mare împãrțit în trei pãrți, și cu cele trei clustere mai mici combinate într-unul.

În cea de a doua figurã, un cluster mai mare poate fi interpretat ca mai multe clustere rotunde, din moment ce acest lucru ar minimiza distanța medie dintre puncte și centroizi (se observã însã cã, folosind raza Mahalonobis, un cluster care este întins într-o direcție este recunoscut ca circular, și nu ne așteptãm ca algoritmul BFR sã greșeascã:

Etapele algoritmului sunt:

Se începe cu o memorie plinã de puncte aleatoare. Punctele se asigneazã la clustere folosind abordarea ierarhicã. Se observã cã clusteringul ierarhic tinde sã evite problemele figurilor anterioare cãt timp clusterele corecte au o densitate mare a punctelor;

Pentru fiecare cluster se alege o mostrã de c puncte, pentru un c constant. Aceste puncte sunt alese pe cât posibil de împrãștiate, apoi mutate treptat cãtre mijloc, dupã cum urmeazã:

se alege primul punct al mostrei ca fiind punctul clusterului cel mai departe de centroid;

se aleg în mod repetat puncte pentru mostrã, alegând acel punct al clusterului a cãrui distanțã minimã fațã de un punct deja ales este pe cât de mare posibil.

când sunt alese c puncte pentru mostrã, se mutã toate mostrele spre centroid cu un procent al distanței fațã de acesta. Drept urmare, punctele mostrelor trebuie sã fie puncte reale ale clusterului. Efectul rezultat este acela cã mostrele devin puncte tipice, împrãștiate în jurul clusterului, indiferent de forma clusterului.

3. Se asigneazã toate punctele, inclusiv cele implicate în etapele (1) și (2) celui mai apropiat cluster, unde, „cel mai apropiat” înseamnã „cu cea mai micã distanțã fațã de un punct al mostrei”.

2.3 Analiza legãturilor

Analiza legãturilor este o abordare descriptivã de explorare a datelor, care ajutã la identificare relațiilor între valorile dintr-o bazã de date. Cele mai întâlnite abordãri ale analizei legãturilor sunt descoperirea asocierilor și descoperirea secvențelor. Descoperirea asocierilor gãsește reguli despre obiecte care apar împreunã într-un eveniment, precum o tranzacție de achiziție. Analiza coșului de cumpãrãturi este un bine cunoscut exemplu de descoperire a asocierilor. Descoperirea secvenței este similarã, ținând cont de faptul cã secvența este o asociere relativã la timp.

Asocierile sunt scrise A B, unde A se numește antecedent sau parte stângã (LHS) iar B se numește consecvent sau parte dreaptã (RHS). De exemplu: în regula de asociere „Dacã oamenii cumpãrã un ciocan, apoi cumpãrã și cuie”, antecedentul este „cumpãrã un ciocan”, iar consecventul este „cumpãrã cuie”.

Este ușor sã se determine proporția de trazacții care conțin un anumit obiect sau un set de obiecte: pur și simplu le numãrãm. Frecvența cu care o anumitã asociere, setul „ciocan și cuie”, apare în baza de date se numește suportul sãu sau preponderențã. Dacã, sã zicem, 15 tranzacții din 1000 constau din „ciocan și cuie”, suportul acestei asocieri va fi de 1.5. Un suport scãzut (de exemplu o tranzacție dintr-un milion) poate indica faptul cã respectiva asociere nu este foarte importantã sau poate indica prezența unor date greșite.

Pentru a descoperi reguli semnificative, trebuie privitã și frecvența relativã a apariției acestor obiecte sau a combinației lor. Fiind datã apariția obiectului A (antecedentul), cât de des obiectul B (consecventul) are loc? Adicã, care este probabilitatea lui B, fiind dat A? Folosind exemplul anterior, asta ar însemna sã se întrebe „când oamenii cumpãrã ciocan, cât de des cumpãrã și cuie”? Un alt termen pentru predictibilitate este acela de „încredere”. Încrederea este calculatã ca o fracție: (frecvența lui A și B) / (frecvența lui A).

Exemplu:

totalul tranzacțiilor: 1000

numãrul celor care includ ciocan: 50

numãrul celor care includ cuie: 80

numãrul celor care includ lemn: 20

numãrul celor care includ ciocan și cuie: 15

numãrul celor care includ cuie și lemn: 10

numãrul celor care includ ciocan și lemn: 10

numãrul celor care includ ciocan, cuie și lemn: 5

Acum putem calcula:

suportul pentru „ciocan și cuie” : 1.5 %

suportul pentru „ciocan, cuie și lemn” : 0.5 %

încrederea pentru „ciocan cuie” : 30 %

încrederea pentru „cuie ciocan” : 19 %

încrederea pentru „ciocan și cuie lemn” : 33 %

încrederea pentru „lemn ciocan și cuie” : 25 %

Deci putem vedea cã probabilitatea ca un cumpãrãtor de ciocan sã achiziționeze și cuie este mai mare decât probabilitatea ca cineva care cumpãrã cuie sã achiziționeze și ciocan. Preponderența acestei asocieri „ciocan și cuie” (cu suport 1.5 %) este suficient de mare pentru a sugera o regulã semnificativã:

Lift – este o altã mãsurã pentru puterea unei asocieri. Cu cât mai mare lift-ul, cu atât mai mare este influiența apariției lui A asupra probabilitãții ca sã aparã și B. Lift-ul este calculat ca fiind fracția (încrederea lui A B) / (frecvența lui B)

lift pentru „ciocan cuie” : 3.75 %

lift pentru „ciocan și cuie lemn” : 16.5 %

Algoritmii de asociere gãsesc aceste reguli fãcând echivalentul sortãrii datelor în timp ce se numãrã aparițiile și astfel se pot calcula încrederea și suportul. Eficiența cu care se poate face acest lucru este una dintre diferențierile dintre algoritmi. Unii algoritmi vor crea baze de reguli, factori de încredere și suporturi, care pot fi interogate.

Alt atribut comun pentru generatorii de reguli de asociere este abilitatea de a specifica o ierarhie a obiectelor. În exemplu, ne-am uitat la toate cuiele și ciocanele și nu la tipuri individuale. Este important sã se aleagã un nivel potrivit de agregare sau este puțin probabil sã gãsim asocierile care ne intereseazã. O ierarhie a obiectelor îți permite sã controlezi nivelul de agregare și sã experimentezi cu diferite nivele.

Trebuie amintit faptul cã asocierile sau secvențele de reguli nu sunt reguli propriu-zise, ci mai degrabã descrieri ale relațiilor într-o anumitã bazã de date. Nu existã o testare formalã a modelelor pe alte date pentru a mãri puterea de predicție a acestor reguli. Mai degrabã existã o presupunere implicitã conform cãruia, comportamentul din trecut va continua și în viitor.

Este în general dificil sã decizi ce sã faci cu regulile de asociere descoperite. În planificarea magazinului, de exemplu, a așeza unele articole lângã altele asociate, poate reduce valoarea totalã a coșului de cumpãrãturi – clienții cumpãrã mai puține lucruri neplanificate, în timp ce merg prin magazin în cãutarea articolelor dorite. Intuiția, analiza și experimentarea sunt de obicei folosite pentru a obține orice beneficiu de pe urma regulilor de asociere.

Metodele grafice pot fi deasemenea foarte folositoare în vizionarea legãturilor. În figura urmãtoare, fiecare cerc reprezintã o valoare, sau un eveniment. Liniile care conecteazã cercurile aratã legãturile. Liniile mai groase reprezintã legãturi mai puternice sau mai frecvente, evidențiind potențial relații mai importante precum asocierile. De exemplu, privind la baza de date de asigurãri, pentru a detecta fraude potențiale, se poate descoperi faptul cã un anumit doctor și avocat lucreazã împreunã la un numãr mare de cazuri:

Capitolul 3

MODELE ȘI ALGORITMI DATA MINING

3.1 Data mining predictiv

3.1.1 O ierarhie a alegerilor

Scopul tehnologiilor data mining este de a produce cunoștințe noi conform cãrora sã acționeze utilizatorul. Acesta construiește un model al realitãții bazat pe date colectate dintr-o varietate de surse care pot include tranzacțiile corporației, istoria clienților și informații demografice, date de control al procesului și baze de date externe relevante precum informații de la biroul de credit sau date despre starea vremii. Rezultatul construirii modelului este o descriere a tiparelor și relațiilor între date care pot fi folosite cu încredere pentru predicții.

Pentru a evita confundarea diferitelor aspecte ale tehnicilor data mining, ajutã sã avem o imagine a ierarhiei alegerilor și deciziilor de care ai nevoie înainte de a începe:

scopul afacerii;

tipul predicției;

tipul modelului;

algoritmul;

produsul.

Pe cel mai înalt nivel se aflã scopul afacerii: care este scopul final al forãrii acestor date? De exemplu, ca sã cãutãm tipare în date pentru a ajuta la reținerea clienților profitabili putem construi un model pentru a prezice care clienți vor aduce profituri mari și un al doilea model pentru a identifica clienții pe cale sã se retragã. Cunoștințele asupra nevoilor și obiectivelor organizației vor conduce la formularea scopului modelelor.

Pasul urmãtor este decizia asupra cãrui tip de predicție este cel mai potrivit:

1. clasificare: a prezice în ce categorie sau clasã se încadreazã un caz;

2. regresie: a prezice ce valoare numericã va avea o variabilã (dacã este o variabilã carre variazã în timp se numește predicție în serie în timp)

Dupã aceea se poate alege tipul modelului: o rețea neuronalã pentru a realiza regresia și un arbore de decizie pentru clasificare. Deasemenea, existã modele statistice tradiționale, poți sã alegi dintre regresia logisticã, analiza discriminanților sau modele liniare generale. Cele mai importante tipuri de modele de date pentru data mining sunt descrise în secțiunile urmãtoare:

Pentru construirea unor modele sunt disponibile o serie de algoritmi; se poate construi o rețea neuronalã folosind metoda ”back propagation” sau funcții cu baza radialã. Pentru arborii de decizie se poate alege din: CART, C5.0. Câțiva dintre acești algoritmi sunt deasemenea discutați în secțiunile urmãtoare.

Când se selecteazã un produs data mining trebuie ținut cont de faptul cã acestea implementeazã un anumit algoritm în diferite moduri, chiar dacã sunt identificați de aceleași nume. Aceste diferențe de implementare pot afecta caracteristici operaționale, precum folosirea memoriei și depozitarea datelor și caracteristici ale performanței precum viteza și acuitatea.

3.1.2 Terminologie

În modelele predictive, valorile claselor pe care le prezicem sunt numite rãspunsuri, subordonate sau variabile țintã. Valorile folosite pentru a face predicțiile se numesc predictori sau variabile independente.

Modelele predictive sunt construite sau antrenate folosind date pentru care valoarea variabilelor rãspuns este deja cunoscutã. Acest fel de antrenament este adeseori numit „învãțare supervizatã” deoarece valorile calculate sau estimate sunt comparate cu rezultatele cunoscute (dimpotrivã, tehnicile descriptive precum clustering-ul sunt numite adeseori învãțare supervizatã, deoarece nu existã rezultate deja cunoscute, pentru a îndruma algoritmii).

3.1.3 Clasificare

Problemele de clasificare țintesc sã identifice caracteristicile care îndicã grupul de care aparțin fiecare caz. Tiparul poate fi folosit atât pentru a înțelege datele existente și pentru a prezice în ce mod noi operații ale lor se vor comporta. De exemplu, dacã dorim sã prezicem dacã indivizii pot fi clasificați în: cei care rãspund la o solicitare directã prin poștã, sau cei care ar fi mai tentați de un serviciu de telefonie la distanțã. Data mining creazã modele de clasificare examinând datele deja clasificate (cazurile) și gãsind intuitiv tipare predictive. Aceste cazuri existente pot proveni dintr-o bazã de date existentã, precum cea a oamenilor care au urmat un anumit tratament medicamentos sau au apelat la un nou serviciu de telefonie. Pot deasemenea proveni dintr-un experiment în care o monstrã din întreaga bazã de date este testatã în lumea realã și rezultatul este folosit pentru a creea clasificãri. Câte o datã, un expert clarificã o monstrã dintr-o bazã de date și aceastã clasificare este apoi folositã pentru a crea modelul care va fi aplicat întregii baze de date.

3.1.4 Regresiile

Regresiile folosesc valori existente pentru a prezice ce alte valori vor apãrea. În cel mai simplu caz, regresiile folosesc tehnici statice standard precum regresia liniarã. Din pãcate, multe probleme ale lumii reale nu sunt proiecții liniare simple ale valorilor precedente. De exemplu, volumul vânzãrilor, prețurile stocurilor și rata rebuturilor sunt foarte dificil de prezis pentru cã pot depinde de interacțiuni complexe ale mai multor variabile de predicție. Tocmai de aceea, tehnici mai complexe (regresie logisticã, cuburi de decizie sau rețele neuronale). Ar putea fi necesare pentru a prezice variabilele viitoare. Acelorași tipuri de modele pot fi folosite atât pentru regresie cât și pentru clasificare, De exemplu, algoritmul pentru arbori de decizie CART (arbori de clasificare și regresie) poate fi folosit atât pentru a construi arbori de clasificare (pentru a clasifica variabilele de rãspuns categorice) cât și pentru arbori de regresie (pentru a prevedea variabilele de rãspuns continue). Rețelele neuronale pot deasemenea crea atât modele de clasificare cât și modele de regresie.

3.1.5 Șirurile temporale

Șirurile temporale prezic valori viitoare necunoscute bazate pe serii de predictori care variazã în timp. La fel ca la regresii, folosesc rezultate cunoscute pentru a ghida predicțiile. Modelele trebuie sã ținã cont pe perioadele de timp, în special de ierarhizarea perioadelor (incluzând varietatea definițiilor precum sãptãmâna de lucru de 5 sau 7 zile, anul de 13 luni, etc.), de sezoane, vacanțe, aritmetica datelor și considerații speciale precum cât anume din trecut este relevant.

3.2. Modele data mining

3.2.1 Introducere

Sã examinãm în cel fel anumiți algoritmi și tipuri de modele sunt folosite pentru a fora în date. Cele mai multe produse folosesc variații ale algoritmilor care au fost publicați în reviste specializate în informaticã sau statisticã, cu implementarea lor specificã, adaptatã la scopurile individuale ale ofertanților. De exemplu, mulți ofertanți vând arbori de decizie CART sau CHAID îmbunãtãțiți pentru a lucra cu computere paralele. Alți ofertanți au algoritmi proprii care fãrã a fi extensii sau variante îmbunãtãțite ale unor abordãri publicate, pot merge destul de bine.

Cele mai multe dintre modelele și algoritmii discutați în aceastã secțiune pot fi vãzuți ca generalizãri al multiutilizatului model de regresie liniarã. Un efort intens a fost depus în statisticã, informaticã, inteligențã artificialã și inginerie pentru a depãși limitãrile modelului de bazã. Caracteristicile comune ale multor tehnologii noi vor privi mecanismul de gãsire a tiparelor ca fiind mai mult condus de date decât de utilizatori. Adicã, relațiile sunt gãsite inductiv de software, bazându-se pe date existente și nu cerând modelatorului sã specifice formale funcționale și interacțiunile.

Poate cel mai important lucru de amintit este acela cã niciunul dintre modele sau algoritmi poate fi sau ar trebui fi folosit în mod exclusiv. Pentru orice problemã datã însãși natura datelor va afecta alegerea modelelor și a algoritmilor. Nu exsitã un „cel mai bun” model sau algoritm. Ca urmare, este nevoie de o varietate mare de unelte și tehnologii pentru a gãsi cel mai bun model posibil.

3.2.2 Rețele neuronale

Rețelele neuronale prezintã un interes particular deoarece oferã mijloace de modelare eficientã a problemelor complexe în care pot fi folosite de variabile de predicție care pot interacționa în multe feluri (adevãratele rețele neuronale, biologice, sunt defapt cu mult mai complexe). Rețelele neuronale pot fi folosite în probleme de clasificare (unde rezultatul este o variabilã categoricã) sau pentru regresii (unde rezultatul este o variabilã continuã).

O rețea neuronalã începe un strat al intrãrilor unde fiecare nod corespunde unei variabile de predicție. Aceste noduri de intrare sunt conectate la un numãr de noduri dintr-un strat ascuns. Fiecare nod de intrare este conectat cu fiecare nod din stratul ascuns. Nodurile din stratul ascuns pot fi controlate cu nodurile din alt strat ascuns sau dintr-un start de ieșire. Stratul de ieșire constã în una sau mai multe variabile de rãspuns.

Dupã stratul de intrare, fiecare nod primește o serie de intrãri, le înmulțește cu o pondere de legãturã Wxy, le adunã, le aplicã o funcție (numitã funcție de activare) și trece rezultatul nodului sau nodurilor din stratul urmãtor. De exemplu, valoarea trecutã de la nodul 4 la nodul 6, este funcția de activare aplicatã pentru:

[W14*val. nodului 1]+[W24*val. nodului 2]

Fiecare nod poate fi vãzut ca o variabilã de predicție sau ca o combinație de variabile de predicție. Nodul 6 este o combinație neliniarã a valorilor din nodurile 1 și 2 din cauza funcțiilor de activare aplicatã valorilor însumate în stratul ascuns. De fapt, atunci când funcția de activare este liniarã și nu existã strat ascuns, rețelele neuronale sunt echivalente cu regresiile liniare și atunci când funcțiile de activare nu sunt liniare și au anumite formule de calcul, rețelele neuronale sunt echivalente cu regresiile logistice.

Ponderile de legãturã sunt parametri necunoscuți care sunt estimați prin „metode de antrenare”. Inițial, cea mai folositã metodã de antrenare era „back propagation”; metodele mai noi includ algoritmi complecși precum: algoritmi genetici, „Levenbrg – Marquardt”, „Newton”, etc. Fiecare metodã de antrenare are un set de parametri care controleazã diferite aspecte ale antrenãrii precum evitarea optimelor locale sau ajustarea vitezei de conversie.

Arhitectura sau topologia unei rețele neuronale este datã de numãrul de noduri și de straturi ascunse și de felul în care acestea sunt legate. În proiectarea rețelelor neuronale, fie utilizatorul, fie soft-ul trebuie sã aleagã numãrul de noduri ascunse sau straturi ascunse, funcțiile de activare și limitele ponderilor. Deși existã câteva modele de îndrumare se pot experimenta arhitecturi noi cu aceste valori.

Unul dintre cele mai întâlnite tipuri de rețele neuronale este rețeaua „feed–forward- backpropagation”. Pentru a simplifica modelul, se considerã doar cazul unui singur strat ascuns.

Antrenarea backpropagation este o versiune a „pantei descendente”, un tip de algoritm care încearcã sã reducã o valoare țintã (eroare, în cazul rețelelor neuronale) la fiecare pas. Algoritmul procedeazã în felul urmãtor:

Feed – forward: Valoarea nodului de ieșire este calculatã pe baza valorilor nodurilor de intrare și un set de ponderi inițiale. Valorile din nodurile de intrare sunt combinate în stratul ascuns și valorile din acele noduri sunt combinate în valoarea de ieșire.

Backpropagation: Eroarea ieșirii este calculatã ca fiind diferența dintre ieșirea calculatã și ieșirea doritã (valori reale gãsite în setul de antrenare). Apoi, eroarea din valoarea de ieșire este atribuitã nodurilor din stratul ascuns proporțional cu ponderile lor. Acest lucru permite calculul unei erori pentru fiecare nod de ieșire și fiecare nod ascuns din rețea. În sfârșit, erorile de la fiecare nod de ieșire sau ascuns sunt folosite de algoritm sã ajusteze ponderile spre un nod vizat astfel încât sã îi reducã eroarea.

Acest proces este repetat pentru fiecare linie din setul de antrenare. Fiecare pas din fiecare linie a setului de antrenare se numește epocã. Setul de antrenare va fi folosit în mod repetat pânã când eroarea nu mai scade. În acel moment, rețeaua neuronalã se considerã a fi antrenatã pentru a gãsi tiparul în setul de test.

Din cauza numãrului mare de parametri care pot exista în straturile ascunse, o rețea neuronalã cu suficient de multe noduri ascunse va „potrivi” pânã la urmã un set de antrenare dacã este lãsatã activã o perioadã de timp suficientã, dar nu se cunosc rezultatele pe care le va da pe un set de date. Pentru a evita rețelele neuronale supraîncãrcate care lucreazã bine numai cu date din setul de antrenare trebuie știut când sã se opreascã antrenarea. Cât timp rata erorii pe datele de antrenare pot descrește, datele ar putea fi supraîncãrcate.

Graficul din figura urmãtoare, aratã cum setul de date de test poate ajuta la evitarea supraîncãrcãrii. Se poate observa cum rata erorii descrește cu fiecare pas pe care rețeaua îl face cu datele, dar rata erorii pentru datele de test își atinge minimul și apoi începe sã creascã. Având în vedere cã scopul tehnicilor data-mining este de a face predicții pe seturi de date diferite de setul de test se observã cã se obțin rezultate mai bune dacã se renunțã la folosirea unei rețele neuronale care minimizeazã eroarea în datele de test și nu în datele de antrenare.

Rețelele neuronale diferã în multe privințe de celelalte metode statistice. În primul rând, o rețea neuronalã are de obicei mai mulți parametri decât are în mod normal un model statistic tipic. De exemplu, sunt 13 parametri (9 ponderi și 4 constante) în rețeaua schițatã anterior. Deoarece parametri sun în numãr atât de mare, și datoritã numeroaselor combinații de parametri rezultate în predicții similare, valorile devin de neinterpretat și rețeaua se transformã într-o „cutie neagrã”. În realitate, un anumit rezultat poate fi asociat cu mai multe seturi diferite de ponderi. Drept urmare, ponderile rețelei nu ajutã în general la înțelegerea substraturilor procesului care genereazã predicția, dar tehnica este utilã în multe aplicații. De exemplu, la o bancã se poate dori recunoașterea automatã a unor aplicații scrise de mânã dar fãrã ase ține cont de forma sau relația funcționalã dintre pixeli și caracterele pe care le reprezintã. Câteva dintre multele aplicații în care sute de variabile sunt introduse ca date în modele cu mii de parametri (ponderi ale nodurilor) includ modelarea uzinelor chimice, a roboților și a piețelor financiare sau crearea unor tipare în probleme precum recunoașterea sunetelor, a imaginilor sau a caracterelor scrise de mânã.

Unul dintre avantajele modelelor bazate pe rețele neuronale este acela cã pot fi ușor implementate pentru a funcționa pe computere paralele de capacitãți mari, astfel încât fiecare nod estecalculat simultan.

Utilizatorii trebuie sã fie conștienți de câteva lucruri în ceea ce privește rețelele neuronale:

în primul rând, rețelele neuronale nu sunt ușor de interpretat, nu existã aplicații raționale pentru deciziile sau predicțiile pe care o rețea neuronalã le face.

în al doilea rând, rețelele neuronale tind sã supraîncarce datele de antrenare, lucru care poate fi evitat doar dacã se iau mãsuri restrictive, precum: scãderea ponderilor sau validarea încrucișatã. Acest fapt se datoreazã numãrului mare de parametri ai rețelei care, dacã i se pemite sã fie de o dimensiune suficientã va încãrca arbitrar orice set de date în mod corect și le va antrena spre convergențã.

în al treilea rând, rețelele neuronale cer un anumit timp de antrenare exceptând cazurile în care problema este mãruntã. În orice caz, odatã antrenatã, o rețea poate oferi predicții rapide.

în al patrulea rând, rețelele nu cer o pregãtire a datelor mai puțin elaboratã decât orice altã metodã, ci dimpotrivã, cer chiar o pregãtire temeinicã. Unul dintre lucrurile care se știu despre rețelele neuronale este cã datele de orice calitate pot fi folosite pentru a obține predicții „rezonabile”. Cele mai reușite implementãri ale rețelelor neuronale (sau arbori de decizie, sau regresii logistice sau orice altã metodã) presupun o „curãțare” foarte atentã a datelor, selecție, preparare și pre-procesare. De exemplu, rețelele neuronale cer ca toate variabilele sã fie numerice. Din acest motiv, date categorice precum „stratul” sunt de obicei desfãcute în mai multe variabile de dihotomie, fiecare cu valorile „0” (nu aparține unui anumit strat) și „1” (dacã aparține acelui strat). Creșterea numãrului de variabile care rezultã de aici poartã numele de „explozie categoricalã”.

în ultimul rând, rețelele neuronale au tendința de a lucra cel mai bine când setul de date este suficient de mare. Deoarece sunt atât de flexibile, ele vor conduce la multe tipare false în situații de legãturã slabã între date.

3.2.3 Arbori de decizie

Arborii de decizie sunt moduri de a reprezenta o serie de reguli care duc la o clasã sau o variabilã. De exemplu, dacã se dorește clasificarea celor care au depus pentru un împrumut în cei care prezintã un risc mic de creditare și cei care prezintã un risc mare de creditare. Un arbore de decizie simplu rezolvã problema ilustrând în același timp toate componentele de bazã ale unui arbore de decizie: nodurile de decizie, crengile și frunzele.

Prima componentã este nodul de decizie vârf sau nodul rãdãcinã, care specificã un test ce va fi aplicat. Nodul rãdãcinã din acest exemplu este „venit > sumã_prag”. Rezultatele aplicãrii acestui test determinã despãrțirea arborelui în ramuri, fiecare reprezentând unul dintre rãspunsurile posibile. În acest caz, testul „venit > sumã_prag” poate avea rãspunsurile da sau nu, și astfel se obțin douã ramuri.

În funcție de algoritm, fiecare nod poate determina douã sau mai multe ramuri. De exemplu, algoritmul CART genereazã arbori cu douã ramuri la fiecare nod. Un astfel de arbore se numește arbore binar. Când sunt permise mai mult de douã ramuri la un nod, vorbim despre un arbore multi-cãi.

Fiecare ramurã va conduce fie la un alt nod de decizie, fie la margine arborelui, unde se gãsesc nodurile frunzã. Prin parcurgerea unui arbore, se pot asigna valori sau clase unui subiect, prin alegerea ramurii de parcurs în continuare, începând de la rãdãcinã și mergând din nod în nod, pânã se atinge un nod frunzã. Fiecare nod folosește datele din proces pentru a alege ramura potrivitã.

Având în fațã un arbore precum cel din exemplu, și o cerere de împrumut, personalul care se ocupã de împrumuturi la o bancã poate determina dacã cel care a depus cererea prezintã un risc mare sau mic de creditare. Un individ cu un venit mai mare decât o sumã_prag și cu datorii mari ar fi clasificat ca prezentând un risc mare de creditare, pe când un individ cu un venit mai mic decât suma_prag, dar cu o vechime în muncã mai mare de cinci ani, ar fi clasificat ca prezentând un risc mic de creditare.

Modelul arborilor de decizie este uzual folosit în data mining pentru a examina datele și a construi arborele și regulile care vor fi folosite pentru a face predicții. La construirea arborilor de decizie, pot fi folosiți diferiți algoritmi, precum: CHAID (Chi-squared Automatic Interaction Detection), CART (Clasification and Regression Trees), Quest și C 5.0.

Arborii de decizie cresc pe baza unei împãrțiri iterative a datelor în grupuri discrete, scopul fiind maximizarea „distanței” dintre grupuri la fiecare împãrțire.

Una dintre diferențele dintre metodele bazate pe arbori de decizie constã în felul în care acestea mãsoarã „distanța”. În timp ce detalii precum „mãsurarea” sunt dincolo de scopul acestei introduceri, fiecare despãrțire poate fi gânditã ca o separare a datelor în grupuri noi, care sunt pe cât posibil de diferite unele de altele. Acest lucru mai este numit și „purificarea grupurilor”. Fațã de exemplul anterior, în care datele aveau doar douã clase de ieșire posibile, „risc mare – risc mic”, este preferabil ca fiecare datã separatã în urma unei decizii sã se regãseascã într-un „grup pur” cu apariții într-un singur astfel de grup și nu în mai multe.

Arborii de decizie care sunt folosiți pentru predicții cu variabile categorice sunt numiți arbori de clasificare, deoarece împart datele în categorii sau clase. Arborii de decizie folosiți pentru predicții cu variabile continue sunt numiți arbori de regresie.

Exemplul prezentat anterior este unul foarte simplu. Un astfel de arbore este ușor de înțeles și de interpretat. Oricum, arborii pot deveni foarte complicați: sã ne imaginãm doar complexitatea unui arbore de decizie, derivat dintr-o bazã de date cu sute de atribute și variabile de rãspuns cu zeci de clase de ieșire. Un astfel de arbore ar fi extrem de dificil de înțeles, deși fiecare cale spre o frunzã este foarte clarã. În acest sens, un arbore de decizie își poate explica predicțiile, ceea ce este un avantaj foarte important.

Aceasta claritate poate fi însã înșelãtoare. De exemplu,o ramificare puternicã a unui arbore de decizie implicã o precizie care este foarte rar reflectatã în realitate (de ce cineva al cãrui salariu este mai mare cu unitate decât o sumã prag prezintã un risc mic de creditare, în timp ce altcineva, al cãrui salariu avea aceeași valoare cu suma_prag, în aceleași condiții cu precedentul, prezintã un risc mare de creditare ?). Mai mult, din moment ce mai mulți arbori pot reprezenta adesea aceleași date, cu acuratețe egalã, ce interpretare ar trebui datã regulilor?

Arborii de decizie fac pași puțini prin date, un pas pentru fiecare nivel al arborelui și lucreazã bine cu multe variabile de predicție. Drept urmare, modelele pot fi construite rapid și sunt adaptabile la seturi mari de date.

Arborii lãsați sã creascã fãrã granițã dureazã mult mai mult pânã sunt construiți și devin neinteligibili, dar în primul rând, de cele mai multe ori supraîncarcã datele. Dimensiunea unui arbore poate fi controlatã prin reguli de oprire care limiteazã creșterea. Una dintre cele mai intâlnite reguli de oprire este limitarea adâncimii maxime a unui arbore. O altã regulã de oprire este stabilirea unei limite pentru numãrul de ramuri în care se poate despãrți un nod.

O alternativã la regulile de oprire este scurtarea arborelui. Arborele este lãsat sã creascã pânã la dimensiune maximã și apoi, fie folosind euristici încorporate, fie prin intervenția utilizatorului, arborele este tãiat pânã la cea mai micã dimensiune care nu-i compromite acuratețea. De exemplu, o ramurã sau subarbore despre care utilizatorul crede cã este irelevantã deoarece are foarte puține cazuri, poate fi îndepãrtatã. Algoritmul CART scurteazã arborii în urma validãrii încrucișate, deci dupã ce verificã dacã gradul de creștere a acurateții justificã nodul „în plus”.

Unul dintre lucrurile care se reproșeazã arborilor de decizie este faptul cã fac separãri în noduri, folosind un algoritm Greedy, în cadrul cãruia decizie pe baza cãreia variabilele sunt separate nu ține cont de efectul pe care separarea îl poate avea asupra viitoarelor separãri. Cu alte cuvinte, decizia de separare este fãcutã într-un nod, în momentul în care s-a ajuns la nod și nu se revine niciodatã asupra ei. În plus, toate separãrile sunt fãcute secvențial, astfel încât fiecare separare depinde de precedenta. Astfel, toate separãrile viitoare depind de prima separare, ceea ce înseamnã cã soluția finalã poate fi complet diferitã dacã la un moment dat s-a fãcut o altã separare. Încercarea de a face separãri bazate pe douã sau mai multe nivele în același timp încã nu dã rezultate îmbunãtãțite. Astfel de încercãri sunt incã în faza de încercare, dar solicitã intensiv resurse de calcul și astfel nu sunt disponibile pentru implementãri in scopuri comerciale.

Mai mult decât atât, algoritmii folosiți pentru separare iau în calcul fiecare variabilã de predicție pe rând. Și, în timp ce acesta este unul dintre motivele pentru care un astfel de model se construiește repede (limiteazã numãrul testãrilor regulilor de separare posibile), în același timp determinã o detectare greoaie a relațiilor dintre variabilele de predicție.

Arborii de decizie care nu sunt limitați la separãri univariabile, pot folosi mai multe variabile de predicție la o singurã regulã de separare. Un astfel de arbore de decizie poate permite combinații liniare ale variabilelor și mai este cunoscut sub numele de arbore „oblic”. Un criteriu pentru separare ar putea fi: „salariu < 0.35 * ipoteca”. Separarea pe combinații logice de variabile precum „salariu > suma_prag1 sau ipotecã < sumã_prag2” este un alt tip de separare multivariabilã.

Arborii de decizie manevreazã inclusiv date non-numerice. Abilitatea de a accepta date categorice minimizeazã numãrul de transformãri asupra datelor și explozia de variabile de predicție inerentã în cazul rețelelor neuronale. Câțiva arbori de clasificare au fost proiectați pentru astfel de date și ca urmare, lucreazã mai bine când variabilele de predicție sunt categorice. Predictorii continui pot fi folositi în mod frecvent în astfel de cazuri, prin conversia variabilelor continue la un set de șiruri. Unii arbori de decizie nu suportã variabile de rãspuns continue (nu putem construi arbori de regresie), caz în care variabilele de rãspuns din setul de antrenare trebuie deasemenea transformate în clase de ieșire.

3.2.4 Modelul MARS (Multivariate Adaptive Regression Splines)

La mijlocul anilor ’80, inventatorul algoritmului CART, Jerome H. Friedman, a dezvoltat o metodã destinatã sã îndrepre neajunsurile algoritmului sãu.

Principalele dezavantaje pe care el voia sã le elimine erau:

predicția discontinuã (separãri „dure”);

dependența tuturor separãrilor de precedentele separãri;

interpretabilitatea redusã, datoratã interacțiunilor, mai ales a celor de ordin mare.

Astfel, el a dezvoltat algoritmul MARS. Ideea care stã la baza acestei metode este una simplã, dezavantajele algoritmului CART fiind amortizate prin:

înlocuirea ramurilor discontinue la un nod cu o linie continuã de tranzit modelatã printr-o pereche de linii drepte; la sfârșitul procesului de construire a modelului, liniile drepte de la fiecare nod sunt înlocuite cu o funcție care le aproximeazã, numitã „spline” (riglã);

nu mai este necesar ca viitoarele separãri sã depindã de precedentele.

Din pãcate, asta înseamnã cã metoda MARS distruge structura de arbore ridicatã de CART, și nu poate induce reguli. Pe de altã parte, aceastã metodã gãsește în mod automat și afișeazã cere mai importante variabile de predicție, precum și interacțiunile dintre acestea. În plus, ilustreazã și dependența rãspunsului de fiecare predictor. Rezultatul este o unealtã automatã de regresie non-liniarã.

Ca și în cazurile rețelelor neuronale sau arborilor de decizie, modelul MARS are tendința de a supraîncãrca datele de antrenare și acest lucru poate fi evitat în douã feluri: se poate face o validare încrucișatã și algoritmul poate fi potrivit astfel încât sã determine predicții bune cu datele din setul de test, sau existã destui parametri interni pe care algoritmul le poate folosi, astfel încât sã-și valideze singur datele.

3.2.5 Reguli de inducție

Metoda regulilor de inducție constã în aplicare unui set de reguli pentru a determina clasificãri. Deși arborii de decizie pot determina și ei un astfel de set de reguli, metoda regulilor de inducție genereazã un set de reguli independente care nu formeazã cu necesitate un arbore (este chiar puțin probabil). Deoarece generatorul de reguli nu forțeazã separãri la fiecare nivel și poate înainta în date, este capabil sã gãseascã tipare diferite (uneori chiar mai bune) pentru clasificare. Spre deosebire de arbori, regulile generate s-ar putea sã nu acopere toate situațiile posibile. Tot o diferențã fațã de arbori este și faptul cã regulile pot duce uneori la conflicte, caz în care este necesar sã se aleagã regula ce va fi aplicatã. Una dintre metodele cele mai obișnuite de a rezolva conflicte este de a asigna coeficienți de încredere regulilor și de o folosi pe aceea cu coeficientul mai mare.

3.2.6 Metoda celor mai apropiați vecini

Când se încearcã rezolvarea unor noi probleme, sunt luate în calcul și soluțiile unor probleme similare. Metoda celor mai apropiați vecini (K – nearest neighbor) este o tehnicã de clasificare care folosește o versiune a metodei însãși. Decide în ce clasã sã încadreze un nou subiect, examinând un numãr de k subiecți similar (vecini). Calculeazã numãrul de subiecți pentru fiecare clasã și asigneazã noul subiect acelei clase cãreia îi aparțin cei mai mulți dintre vecinii sãi.

N reprezintã noul subiect, iar X și Y subiecții care țin de clasele X, respectiv Y. Interiorul elipsei reprezintã vecinãtatea lui N. Se obsevã cã N va fi asignat clasei X, deoarece cei mai mulți dintre vecinii sãi aparțin acestei clase.

Primul pas în aplicarea acestei metode constã în gãsirea unui mod de a mãsura „distanța” dintre atributele datelor și în calculul acestei distanțe. Acest lucru este banal când se lucreazã cu date numerice, însã în cazul variabilelor categorice este nevoie de tehnici speciale (de exemplu, cum se calculeazã distanța dintre galben și albastru?). Odatã calculate distanțele dintre subiecți, se selecteazã un set de subiecți deja clasificați pentru a-l folosi ca bazã pentru clasificarea noilor subiecți, dupã care se va decide cât de mare va fi vecinãtatea în cadrul cãreia se vor face comparațiile și cum se vor determina vecinii.

Aceastã metodã solicitã intens resursele unui sistem de calcul, deoarece timpul de calcul crește factorial, odatã cu numãrul de subiecți testați. În timp ce aplicarea unei rețele neuronale sau a unui arbore de decizie asupra unui nou subiect este un proces rapid, algoritmul celor mai apropiați vecini cere noi calcule pentru fiecare subiect în parte. Pentru a mãri viteza de lucru a algoritmului, o soluție ar fi memorarea tuturor datelor. MBR (Memory Based Reasoning) se referã de obicei la seturi memorate de date, care țin de acest algoritm.

Modelele construite de algoritmul celor mai apropiați vecini, sunt ușor de înțeles, când este implicat un numãr mic de variabile de predicție. Pot fi folosite pentru a construi modele care implicã tipuri de date diferite de cele obișnuite, precum datele de tip text. Singura cerințã pentru a putea utiliza astfel de tipuri de date este existența unei metrici adecvate.

3.2.7 Regresii logistice

Regresia logisticã este o generalizare a regresiei liniare. Se folosește pentru variabilele de predicție binare (cu valori precum da/nu sau 0 și 1) și, ocazional, pentru variabilele multiclasã. Deoarece variabila de rãspuns este discretã, nu poate fi modelatã direct prin regresie liniarã. Din aceastã cauzã, în loc sã se prezicã dacã un eveniment (variabila de rãspuns) va avea loc, se construiește un model pentru a prezice logaritmul șansei ca evenimentul sã aibã loc. Acest logaritm se numește „log odds” sau „transformare logit”.

Șansa se calculeazã ca raportul dintre probabilitatea ca un eveniment sã aibã loc și probabilitatea ca evenimentul sã nu aibã loc și are aceeași interpretare ca șansa calculatã la jocurile de noroc sau la pariurile sportive.

Când se spune cã șansele sunt de 3 la 1 ca o anumitã echipã sã învingã într-un meci spunem cã probabilitatea ca echipa sã câștige este de trei ori mai mare decât probabilitate ca ea sã piardã, deci existã o șansã de 75% ca ea sã câștige și 25% șanse ca ea sã piardã.

O terminologie asemãnãtoare se poate aplica și în cazul șansei obținerii unui rãspuns la o ofertã din partea unui anumit client (cu un anumit venit, cu o anumitã stare civilã, etc.). Dacã spunem cã șansele sunt de trei la unu ca subiectul sa rãspundã pozitiv, spunem cã probabilitatea ca acel tip de client sã rãspundã pozitiv este de trei ori mai mare ca probabilitatea unui rãspuns nefavorabil.

Dupã ce a fost calculat logaritmul, rezultatului i se aplicã funcția inversã pentru a afla șansa. O șansã de 62% poate însemna cã subiectulva fi asignat clasei cu valorile „1” sau „da”.

Regresia logisticã este o unealtã de modelare foarte puternicã, însã presupune cã variabila de rãspuns (logaritmul, și nu evenimentul însuși) este liniar în coeficienții variabilelor de predicție. Mai mult, modelatorul, pe baza experiței sale în prelucrarea datelor, trebuie sã aleagã valorile de intrare potrivite și sã specifice relațiile lor funcționale cu variabila de rãspuns. Astfel, modelatorul trebuie sã aleagã de exemplu între variabilele „venit”, „(venit)2” sau log(venit) pentru predicția sa. În plus, modelatorul trebuie sã adauge limite pentru fiecare interacțiune.

Este de datoria modelatorului sã aleagã variabilele potrivite, expresiile lor corecte și sã ținã cont de posibilele interacțiuni între ele. Aceste lucruri cer efectiv o mare pricepere și experientã din partea analistului.

Rețelele neuronale, pe de altã parte folosesc straturile lor ascunse pentru a forma termeni neliniari și interacțiuni în moduri semiautomate. Utilizatorii folosesc un set diferit de abilitãți analitice pentru a aplica cu succes rețelele neuronale. De exemplu, alegerea unei funcții de activare va afecta viteza cu care o rețea neuronalã se antreneazã.

3.2.8 Analiza discriminantã

Analiza discriminantã este cea mai veche tehnicã de clasificare matematicã, fiind publicatã pentru prima datã de R. A. Fisher în 1936. Aceastã tehnicã gãsește hiperplane (linii, în spațiul bidimensional, plane, în spațiul tridimensional, etc.) care separã clasele. Modelul rezultat este foarte ușor de interpretat deoarece tot ceea ce utilizatorul trebuie sã facã este sã determine de c parte a liniei (sau hiperplanului) se aflã un punct. Antrenarea este simplã și gradatã. Tehnica este foarte sensibilã la tiparele dintr-o mulțime de date. Este folositã foarte des în cadrul unor discipline precum medicina, științele sociale, biologia, etc.

Analiza discriminantã nu este o tehnicã des utilizatã în data mining din trei motive:

presupune cã toate variabilele de predicție urmeazã o distribuție normalã (histograma lor are forma unui clopot), ceea ce nu este adevãrat.

Variabilele categorice neordonabile (roșu, albastru, verde) nu pot fi folosite.

Granițele care separã clasele sunt toate forme liniare (linii, plane) dar, câteodatã, datele pur și simplu nu pot fi separate în acest mod.

Versiuni mai recente ale analizei discriminante corecteazã câteva dintre aceste probleme permițând granițelor sã fie atât liniare, cât și pãtratice, ceea ce mãrește semnificativ sensibilitatea la unele cazuri. Existã și tehnici care înlocuiesc presupunerea de normalitate cu o estimare a distribuției reale (înlocuiesc curba teoreticã a clopotului cu histograma variabilelor de predicție).

3.2.9 Modelul aditiv generalizat

Existã o clasã de modele care extinde atât regresia liniarã cât și pe cea logisticã, cunoscutã sub numele de clasa modelelor aditive generalizate sau GAM. Ele sunt numite aditive deoarece se bazeazã pe presupunerea cã modelul poate fi scris ca o sumã de funcții posibil neliniare, una penru fiecare predictor. GAM pote fi folosit atât pentru regresii cât și pentru clasificarea unui rãspuns binar. Variabila de rãspuns poate fi, virtual, orice funcție aplicatã predictorilor cu condiția sã nuprezinte discontinuitãți. De exemplu, funcția venit/delicvențã este o funcție complicatã aplicatã variabilei venit, conform cãreia, inițal, delicvența scade odatã cu creșterea venitului. Apoi începe sã creascã din nou la venituri moderate pentru a-și atinge vârful înainte de a scãdea pentru venituri mari. Într-un asemenea caz, un model liniar poate trece cu vederea legãtura dintre venit și delicvențã datoritã comportamentului neliniar al funcției. Modelul aditiv generalizat, folosind puterea calculatoarelor în locul teoriei funcționalelor va determina o curbã netedã, vizualizând relațiile exact așa cum au fost descrise anterior. Cel mai des întâlnit procedeu de estimare este cel de „backfeetting”. În locul estimãrii unui numãr mare de parametrii, ca în cazul rețelelor neuronale, GAM face un pas înainte și folosește estimarea unei valori de ieșire pentru fiecare valoare de intrare (un punct – o estimare).

3.2.10 Boosting

În cazul în care se construiește un model folosind un subset al setului de date, și apoi se construiește un alt model folosind același algoritm dar alt subset de date, se poate ajunge la rezultate complet diferite. Dupã validarea celor douã modele, poate fi ales acela care se apropie cel mai mult de obiectivul propus. Rezultatele se pot chiar îmbunãtãți dacã se construiesc mai multe modele care sunt supuse la vot, predicția fãcându-se dupã votul majoritãții. Desigur, orice interpretabilitate a predicției este pierdutã însã acest lucru poate fi compensat prin calitatea rezultatelor.

Aceastã abordare a datelor stã la baza metodei „boosting”, o tehnicã publicatã pentru prima oarã în 1996 de cãtre Freund și Schapire. Astfel, metoda alege la întâmplare subseturi de date și constuiește modele de clasificare pentru fiecare. Setul de antrenare este schimbat în funcție de rezultatele date de modelul precedent. Clasificarea finalã asigneazã un subiect clasei la care a fost asignat de cele mai multe clasificãri. Algoritmii de boosting au evoluat fațã de cel original dar ideea care stã la bazã a rãmas aceeași.

Metoda boosting a devenit o unealtã auxiliarã foarte popularã pentru tehicile de data mining.

3.2.11 Algoritmi genetici

Algoritmii genetici nu sunt folosiți pentru a gãsi tipare ci pentru a ghida procesul de învãțare al algoritmilor ce țin de data mining, precum rețelele neuronale. Algoritmii genetici se comportã ca metode de cãutare ghidatã a modelelor potrivite în spațiul soluțiilor.

Sunt numiți algoritmi genetici deoarece se încadreazã în tiparul evoluției biologice în care membrii unei generații (sau modele) se întrec în a trece caracteristicile lor generaței viitoare (de modele), pânã când cel mai bun este gãsit. Informația care se moștenește este conținutã în cromozomii care dețin parametrii pentru construirea unui model.

De exemplu, în construirea unei rețele neuronale, algoritmii genetici pot înlocui „backpropagation” și deveni o cale de a ajusta ponderile. O alternativã ar fi folosirea algoritmilor genetici pentru a gãsi cea mai bunã arhitecturã și, în acest caz, cromozomii ar conține numãrul de straturi ascunse și numãrul de noduri din fiecare strat.

Algoritmii genetici sunt o abordare interesantã a problemei optimizãrii modelelor, însã au dezavantajul de a suprasolicita resursele computaționale.

3.3 Modelul episoadelor

3.3.1 Introducere în modelul episoadelor

În modelul episoadelor, datele sunt vâzute ca o înșiruire de evenimente; fiecare eveniment are un tip și un timp al apariției. Un exemplu de tip de eveniment ar putea fi:

„Switch-ul 34 a fost supraîncãrcat și a trebuit sã piardã un pachet de date.”

Este un eveniment mult prea general pentru a avea un timp anume. Multe evenimente pot apãrea în același timp și nu este nici o garanție cã în fiecare unitate de timp are loc un eveniment.

Aplicații ale modelului episoadelor

Prin episoade se înțelege o serie de secvențe sau seturi de evenimente care au loc într-un interval scurt. Aceastã idee poate fi folositã pentru a monitoriza trecerea pachetelor prin switch-uri în cadrul rețelelor, pentru a dezvolta reguli pentru rutarea datelor în cazuri de congestie avansatã a traficului. Este posibil sã se foreze și pentru cãutarea unor reguli pentru a prezice eșecuri ale unor combinații de componente în sisteme complexe.

3.3.2 Episoade

Un episod paralel este un set de episoade, {A, B, C}. În diagrame, aceste episoade sunt reprezentate printr-un chenar vertical în care sunt cuprinse A, B și C. Specificul episoadelor paralele este acela cã fiecare dintre episoade are loc într-un interval de timp, dar ordinea lor nu este importantã.

Un episod serial este o listã de evenimente, (A, B, C). În diagrame, aceste evenimente sunt reprezentate printr-un chenar orizontal, în care sunt cuprinse în ordine evenimentele A, B și C. Specificul lor este acela cã evenimentele au loc într-un interval de timp în ordinea din diagramã.

Observație:

Un singur eveniment poate fi considerat atât serial, cât și paralel.

Un episod compus este construit în mod recursiv din compunere serialã și paralelã de evenimente, deci un episod compus se definește recursiv ca:

un eveniment;

o serie de douã sau mai multe evenimente;

o compunere paralelã de douã sau mai multe evenimente.

Observație:

Orice episod serial sau paralel este un episod compus, dar existã evenimente compuse care nu sunt seriale sau paralele.

Exemplu:

Fie un episod compus, o serie de trei episoade:

primul este un eveniment singular A;

al doilea este un episod paralel {B, C, D};

al treilea este din nou un episod compus, ori compunere paralelã, de douã episoade seriale, (E, F) și (G, H).

Episodul poate fi parcurs în mai multe feluri, în funcție de ordinea în care au loc evenimentele ce compun episoadele paralele: ABCDEFGH, ACDBEFGH, ABCDGHEF, etc.

3.3.3 Monotonia episoadelor si algoritmul A-Priori

Fiid dat un interval de timp W (intervalul de timp în care poate avea loc un eveniment), un episod este frecvent dacã are loc în cel puțin s intervale, unde s este o limitã datã. Aceeași secvenț. Aceeași secvențã de evenimente poate sã aparã ca un episod în mai multe intervale consecutive; se considerã o apariție pentru fiecare astfel de interval. Oricum, în nici un interval nu putem considera același episod de mai multe ori, chiar dacã acel episod este construit din mai multe seturi diferite de evenimente în același interval.

Episoadele frecvente sunt monotone: daca un episod E este frecvent, atunci și orice alt episod format prin eliminarea unor evenimente din E este frecvent. Astfel, episoadele frecvente pot fi construite „descrescãtor”, folosind un algoritm A-Priori:

Fie {Ci}i >0 mulțimea episoadelor candidate formate din i evenimente, și {Li}i >0 mulțimea episoadelor frecvente, formate din i evenimente.

C1 este un set cu toate tipurile de evenimente.

se construiește Ci+1 din Li, unde Ci+1 este mulțimea tuturor episoadelor E, formate din i+1 evenimente, pentru care, dacã ștergem orice eveniment, se obține un eveniment din Li.

Exemplu:

Episodul din figura (a) poate fi frecvent în C3, doar dacã cele trei episoade din figura (b) sunt frecvente.

3.3.4 Verificarea episoadelor paralele

Problema în transformarea lui Ci în Li este trecerea o singurã datã prin date cu numãrarea aparițiilor fiecãrui episod din Ci. Un algoritm banal poate privi pe rând fiecare interval de lungime W și, pentru fiecare episod candidat se verificã dacã are loc în acel interval; Dacã da, atunci numãrul aparițiilor episodului crește cu 1.

Scopul algoritmului MTV este de a cãuta proporțional cu aparițiile tuturor evenimentelor din toate episoadele candidate care au acele evenimente, inclusiv subepisoade sau episoade compuse. Algoritmul a fost dezvoltat în clase și pare mult prea puțin restrictiv, deoarece nu presupune imposibilitatea unui eveniment de a apãrea de mai multe ori într-un interval. Pentru a descrie cum datele sunt parcurse o singurã datã pentru a calcula Li din Ci, considerând fiecare interval în parte, de la începutul secvenței, sunt necesare urmãtoarele structuri de date:

pentru fiecare eveniment A:

A.count – numãrã aparițiile evenimentului A în intervalul curent;

A.contains – o listã a tuturor episoadelor E care conțin evenimentul A;

2. pentru fiecare episod candidat E:

a. E.startingTime – momentul de început al intervalelor consecutive în care E a fost prezent, pânã la intervalul curent;

b. E.support – numãrul de intervale în care E apare, fãrã sã se ia în calcul intervalele de la E.startingTime pânã la intervalul curent;

c. E.missing – numãrul de evenimente A din E care nu au loc în intervalul curent, de unde E este prezent într-un interval, doar dacã E.missing = 0 pentru acel interval.

Algoritmul aratã ce se întâmplã când intervalul înainteazã cu câte o unitate de timp.

Trebuie luate în calcul situațiile speciale în care un eveniment A nu se mai încadreazã într-un interval și aceea în care un eveniment B intrã într-un interval.

Cazul 1:

Un eveniment A nu se mai încadreazã într-un interval.

A.count – – ;

If (A.count == 0) /* A nu se mai încadreazã în interval */

For (all E in A.contains)

{

E.missing + +;

If (E.missing==1) /*Episodul E nu se mai încadreazã în interval*/ E.support += (E.startingTime – currentTime);

}

Cazul 2:

Un eveniment nou B se încadreazã în interval

B.count + + ;

If (B.count == 1) /* B este un eveniment nou în interval */

For (all E in B.contains)

{

E.missing – -;

If (E.missing==0) /* Episodul E este nou în interval */ E.startingTime = currentTime;

}

3.3.5 Verificare episoadelor seriale

Pentru verificarea unui episod serial (A1, A2, …, An) este simulat un automat finit nedeterminist (AFN) care recunoaște șirul A1A2…An. În timp ce verificã evenimentele din date, se urmãresc stãrile în care se aflã AFN.

(qi)i=1,n – stãri ale AFN

Presupunând cã structura datelor este aceeași ca la verificarea episoadelor paralele, AFN este folosit pentru diferite episoade E, astfel:

starea AFN nu se modificã dacã simbolul de intrare nu este un eveniment care face parte din episod, de unde structura acestui automat nu necesitã timp decât dacã episodul face parte din A.contains, pentru evenimentul curent A;

în timp ce se simuleazã, se pãstreazã pentru fiecare stare în care AFN se aflã curent, cel mai recent punct din care am fi putut începe automatul și am fi obținut acea stare. Aceastã valoare este:

momentul curent, dacã am indus starea q1;

momentul stãrii qi+1 dacã am indus starea qi prin citirea evenimentului Ai;

același moment cu precedentul, dacã ne aflãm în qi și urmãtoarea intrare este diferitã de Ai.

dacã AFN pentru episodul E intrã în starea acceptatã qn, dar nu a mai fost în acea stare, atunci E.startingTime ia valoarea momentului curent asociat cu qn.

Dacã orice moment asociat cu o stare este mai mic decât momentul curent din care scãdem lungimea W a intervalului de timp, atunci se șterge acea stare din setul de stãri în care se aflã AFN. Dacã o stare acceptatã este pierdutã, atunci la E.support se adaugã E.startingTime din care scãdem momentul curent;

Exemplu:

Presupunem cã evenimentul E este (A, B, C). AFN pentru E este:

Fie setul de date (A,B,A,B,C), toate evenimentele având loc în intervalul curent. Stãrile în care intrã AFN sunt urmãtoarele:

Verificarea episoadelor compuse

Pentru a extinde verificãrile anterioare (pentru episoade paralele și seriale) trebuie construite mecanisme speciale pentru fiecare subepisod. Intrã în sarcina fiecãrui mecanism al unui subepisod sã raporteze mecanismului supraepisodului (supraepisoadelor) din care face parte subepisodul dacã acesta nu este prezent, sau dacã este prezent, sã raporteze care este cel mai recent moment în care se poate considera cã acesta a început:

dacã subepisodul este o compunere paralelã de evenimente și/sau alte subepisoade se folosește o structurã de date ca la verificarea episoadelor paralele, însã valoarea A.count pentru un eveniment A se înlocuiește cu cel mai recent moment de început pentru episodul compus.

Pentru episoade seriale se menține automatul, însã intrãrile sunt aparițiile subepisoadelor sale.

E.startingTime și E.support se pãstreazã doar pentru episoadele din C1 și nu pentru subepisoade.

Capitolul 4

MODELAREA PROCESULUI DE DATA MINING

4.1 Modelarea proceselor. Generalitãți

Ținând cont de faptul cã o abordare sistematicã este esențialã într-un proces data mining, consultanții de specialitate au specificat un model general al procesului, construit pentru a ghida utilizatorul (mai ales un începãtor în construirea modelelor de predicție) printr-o secvența de pași care conduce la rezultate reușite. Printre cele mai des folosite specificații sunt:

5 A’s: Assess, Access, Analyse, Act and Automate;

SEMMA : Sample, Explore, Modify, Model and Asses;

CRISP-DM : Cross Industry Standard Process for Data Mining

Two Crows Model

4.2 Modelarea de tip „TwoCrows”

În înțelegerea acestui proces trebuie ținut cont de faptul cã, deși pașii apar ordonați într-o listã, procesul de data mining nu este liniar și, în mod inevitabil va fi necesar un salt înapoi la un pas precedent. De exemplu, în etapa de explorare a datelor se poate ajunge la situații în care vor fi necesare adãugãri de date noi la baza de date pentru data mining, deci va fi necesarã o întoarcere la etapa de construire a bazei de date.

Pașii de bazã în procesul data mining sunt:

Definirea problemei

Construirea bazei de date

Explorarea datelor

Pregãtirea datelor pentru modelare

Construirea modelului

Evaluarea modelului

Aplicarea modelului și culegerea rezultatelor

Definirea problemei

În primul rând, o condiție prealabilã în descoperirea cunoștințelor este înțelegerea datelor și a problemei. Fãrã aceastã „înțelegere”, nici un algoritm, indiferent de gradul lui de complexitate, nu poate oferi rezultate în care se poate avea încredere. Pe aceastã „înțelegere” se bazeazã competența de a identifica problemele de rezolvat, prepararea datelor pentru prelucrare sau interpretarea corectã a rezultelor. Pentru a profita din plin de rezultatele oferite de tehnicile de data mining trebuie descrise cu claritate obiectivele; dacã, de exemplu se dorește creșterea rãspunsurilor la o campanie de oferte prin poșta electronicã, în funcție de un scop specific, care poate fi „creșterea numãrului de rãspunsuri” sau „creșterea valorilor rãspunsurilor” se construiesc douã modele diferite.

Construirea bazei de date

Acest pas, împreunã cu urmãtoarele douã constituie „miezul” procesului de preparare a datelor. Împreunã, solicitã mai mult efort sau resurse temporale decât toți ceilalți pași la un loc. Pot apãrea repetãri iterative ale preparãrii datelor și construirii modelului pe mãsurã ce modelul care solicitã modificarea datelor „învațã”. Executarea pașilor de preparare a datelor poate ocupa de la 50% pânã la 90% din timpul și resursele întregului proces de descoperire a cunoștințelor.

Datele ce urmeazã a fi forate trebuie strânse în baze de date. Acest fapt nu solicitã în mod necesar existența unui sistem de management al bazei de date. În funcție de cantitatea, complexitatea și felul în care vor fi folosite, datele pot fi gestionate printr-un „flat-file” sau „spreadsheet”.

În general, nu este recomandabil sã se foloseascã depozitul de date deja existent ci sã se creeze un „data mart” separat. Forarea datelor necesitã un acces intens la depozitul de date, ceea ce poate duce la probleme de alocare a resurselor și de acces la date al altor utilizatori; în foarte multe cazuri, vor fi necesare joncțiuni de tabele ceea ce va duce la accesarea simultanã a unei importante pãrți a depozitului de date.

Mai mult ca sigur vor fi necesare modificãri asupra datelor din depozit, importuri de date din alte depozite pentru suprapunere, adãugãri de câmpuri calculate pe baza câmpurulor deja existente sau supravegheri pentru obținerea de noi date. Un alt analist, care și el construiește un model, poate la rândul lui sã cearã aceleași tipuri de modificãri asupra datelor din depozit. În orice caz, nici o modificare asupra datelor din depozit nu este binevenitã, ținând cont cã depozitul de date este una dintre cele mai importante resurse pentru o corporație, de exemplu.

Încã un motiv pentru crearea unei baze de date separatã este acela cã structura unui depozit de date al unei corporații ar putea sã nu suporte cu ușurințã explorãrile necesare pentru înțelegerea datelor, acestea incluzând „rezumate” ale datelor, rapoarte multi-dimensionale (tabele pivot) și diferite tipuri de vizualizãri și grafice.

În sfârșit, se recomandã stocarea datelor în structuri care cer un design diferit decât cel folosit de depozitul inițial. Datoritã acestor cerințe este mai sigurã folosirea unei baze de date diferitã de depozitul corporației însã, structura acestuia oferã resursele necesare procesului de data mining și este suficient de flexibilã, acesta poate constitui o bazã de date pentru forare.

Pașii în construirea unei baze de date pentru forare sunt:

Colectarea datelor

Descrierea datelor

Selectarea datelor

Evaluarea calitãții datelor și „curãțarea” lor

Consolidare și integrare

Construirea unei metastructuri

Încãrcarea bazei de date

Întreținerea bazei de date

Acești pași nu constituie o secvențã cu o ordine strictã: ordinea executãrii pașilor este impusã de necesitãți.

De exemplu:

se poate începe prin construirea metastructurii;

colectatea de date noi va fi necesarã la fiecare pas, urmatã de descriere și selectare;

adãugarea de date poate schimba calitatea modelului, care trebuie reevaluatã.

Colectarea datelor

Primul pas în colectare este identificarea sursei de unde vor fi preluate datele necesare. Colectarea poate fi precedatã de o sesiune de strângere de date, deoarece existã posibiltatea ca anumite date necesare sã nu fi fost colectate. Sunt cazuri în care pot fi necesare și date externe, dintr-o bazã de date publicã (precum ce a informațiilor despre starea vremii) sau o bazã de date deținutã de o altã corporație. Un raport de colectare a datelor conține proprietãțile diferitelor seturi de date, printre care ar trebui incluse: sursa datelor (internã sau extern), proprietarul, persoana sau organizația responsabiliã cu întreținerea datelor, dimensiunea în tabele, celule, înregistrãri, dimensiunea în biți, mediul fizic de stocare, necesitãțile de securizare, restricțiile de folosire și necesitãți particulare.

Descrierea datelor

Aceastã etapã constã în descrierea conținutului fiecãrui fișier sau tabelã din baza de date. Un raport asupra descrierii datelor poate conține informații generale precum: numãrul de câmpuri sau coloane, numãrul înregistrãrilor incomplete, denumirile câmpurilor, etc, iar pentru fiecare câmp în parte sunt necesare informații despre: tipul datelor, descriere, sursa câmpului, unitatea de mãsurã, numãrul valorilor unice, lista valorilor, intervalul de valori, numãrul valorilor lipsã, informații despre colectare (când, cum, unde ?), chei pentru relații.

Selectarea

Urmãtorul pas în prepararea unei baze de date pentru data mining este selectarea unui subset de date, pentru forare. Nu este vorba despre un set de exemplificare sau despre alegerea variabilelor pentru predicție, ci mai degrabã este o eliminare grossierã a datelor nerelavante sau nedorite. Alte criterii pe baza cãrora se eliminã date pot fi restricțiile impuse de resurse, restricțiile de acces la date sau probleme de calitate.

d) Evaluarea calitãții datelor și curãțarea datelor

Pentru a obține rezultate bune (modele reușite) este nevoie de date „bune” (se aplicã GIGO – Garbage In Garbage Out) . Un estimator al calitãții datelor identificã trãsãturi ale datelor care vor afecta calitatea modelului. În esențã, se încearcã nu numai asigurarea corectitudinii și consistenței valorilor ci și satisfacerea necesitãților ca toate datele sã mãsoare aceleași lucruri în același mod.

Existã mai multe tipuri de probleme privind calitatea datelor, precum: valori incorecte, asocieri incorecte, lipsa unei valori sau lipsa de consecvențã.

Lipsa datelor poate fi o problemã periculoasã pentru proces. Dacã ar fi sã se elimine toate înregistrãrile cu cel puțin un câmp lipsã, s-ar putea ajunge la o bazã de date redusã în dimensiuni, sau cu o imagine nesemnificativã a întregii baze. Faptul cã valoarea unui câmp lipsește nu afecteazã întotdeuna întreaga bazã de date (de exemplu, clienții bine situați financiar lasã câmpul venituri necompletat). Meritã osteneala sã se creeze o nouã variabilã care sã înlocuiascã valorile lipsã, sã se construiascã un model folosind-o și sã se compare rezultatul cu unul obținut prin completarea valorilor lipsã pentru a vedea care duce la o predicție mai bunã.

O altã abordare a acestei probleme este calculul unei valori de substituție. Cele mai folosite strategii de calcul pentru valorile lipsã sunt: valoarea modalã (pentru variabile nominale), mediana (pentru variabile ordinale) sau mijlocul (pentru variabile continue). O strategie mai puțin folositã este asignarea unei valori unui câmp necompletat pe baza distribuției valorilor celorlalte câmpuri. De exemplu dacã informațiile din baza de date sunt 40% despre femei și 60% despre bãrbați, atunci în 40% din cazurile valorilor lipsã pentru câmpul „sex” acesta va fi înlocuit cu femeie, iar în restul de 60% cu bãrbat. Câteodatã, modelele sunt construite folosind tehnici data mining pentru a prezice valorile lipsã. Aceastã metodã dã de obicei rezultate mai bune decãt un simplu calcul, dar necesitã mai multe resurse temporale.

Nu toate problemele întâlnite în procesul de evaluare a calitãții datelor pot fi rezolvate și de multe ori este nevoie sã se lucreze pe cât de mult posibil fãrã a le rezolva și chiar este preferabil și mai puțin costisitor înlocuirea rezolvãrii lor cu proceduri și validãri, pentru a evita problemele de calitate ce pot apãrea în viitor. Oricum, construirea unui model cu datele care existã este posibilã, în speranța cã problemele evitate vor fi rezolvate într-o etapã viitoare.

e) Integrare și consolidare

Datele necesare construirii unui model se pot afla într-o singurã bazã de date, sau în mai multe. Baza de date sursã poate fi baza de date de tranziție, folositã de sistemul operațional al unei companii. Alte date pot fi in depozite construite în scopuri speciale, sau în baze de date ce aparțin altor companii.

Etapa de integrare și consolidare combinã date din diferite surse într-o unicã bazã pentru forare și are ca cerințã principalã rezolvarea conflictelor între valorile datelor provenite din surse diferite. Datele care nu sunt „potrivite” cum trebuie, sunt o sursã majorã de probleme de calitate. În multe cazuri existã diferențe semnificative între modurile cum datele sunt definite și folosite în baze de date diferite. Unele neconcordanțe sunt ușor de acoperit precum diferite adrese pentru același client, însã cu cât aceste diferențe sunt mai subtile, cu atât sunt mai greu de rezolvat. De exemplu, același client poate figura sub nume diferite sau, mai grav, sã aibã numere de identificare multiple. Același nume poate fi folosit pentru entitãți diferite (omonime) sau nume diferite pot fi folosite pentru aceeași entitate (sinonime). Pot apãrea incompatibilitãți în legãturã cu unitãțile folosite, mai ales când datele provin din țãri diferite (de exemplu moneda).

f) Construirea unei metastructuri

Informațiile descrise în rapoartele despre setul de date și despre date, în general, reprezintã baza pentru metastructurã. În esențã, aceasta este o bazã de date despre baza de date însãși și oferã informații care vor fi folosite în crearea bazei de date propriu-zise, precum și informații care vor fi folosite de analist în înțelegerea datelor și construirea modelelor.

g) Încãrcarea bazei de date pentru forare

În cele mai multe cazuri, datele trebuie încãrcate în propria bazã de date. Odatã adunate, integrate și curãțate datele, este necesarã încãrcarea lor propriu-zisã în baza de date. În funcție de tipul de gestionare al bazei de date și de resursele hardware, în funcție de cantitatea și complexitatea datelor, aceasta se poate dovedi o sarcinã serioasã care poate necesita experiența în sisteme informaționale a profesionaliștilor.

h) Întreținerea bazei de date

Odatã creatã, o bazã de date trebuie întreținutã: are nevoie în permanențã de: copii de siguranțã periodice, activitatea trebuie monitorizatã, sau pot fi necesare reorganizãri ale stocãrii datelor pe disc pentru a îmbunãtãți performanțele. Pentru o bazã de date de dimensiuni mari și complexã, mentenanța necesitã și serviciile specialiștilor în domeniu.

4.2.3 Explorarea datelor

Explorarea datelor constã în vizualizare, analiza legãturilor și alte tehnici discutate în capitolul anterior. Scopul este identificare celor mai importante câmpuri în predicția unei ieșiri și determinarea valorilor derivate care ar putea fi folositoare. Într-un set de date cu sute de mii de coloane, explorarea datelor necesitã resurse temporale imense. O interfațã potrivitã și un rãspuns rapid al computerului sunt foarte importante, deoarece explorarea își poate pierde semnificația când trebuie sã aștepți chiar și 20 de minute pentru un grafic.

4.2.4 Prepararea datelor pentru modelare

Acesta este pasul final în prepararea datelor înainte de începerea construirii modelului. Pașii de parcurs în aceastã etapã sunt:

selectarea variabilelor;

selectarea liniilor;

construirea noilor variabile;

transformarea variabilelor;

a. Selectarea variabilelor:

În mod ideal, nu trebuie luate în calcul toate varaibilele disponibile, prelucrate cu unelte de data mining și sã se afle care sunt cei mai buni predictori. În practicã însã, acest lucru nu funcționeazã. Unul dintre motive ar fi faptul cã timpul pe care îl consumã construirea unui model crește odatã cu numãrul de variabile. Un alt motiv este obținerea de modele incorecte în momentul în care sunt luate în calcul coloane de variabile nesemnificative. O eroare comunã este de exemplu folosirea unei variabile de predicție a cãrei valoare ar putea fi calculatã pe baza valorii variabilei de rãspuns. Se poate ajunge la situația în care se încearcã prezicerea vârstei folosind data nașterii.

În timp ce unii algoritmi de data mining vor ignora automat variabile irelevante și țin cont de câmpuri care variazã împreunã, în practicã este recomandabil sã se evite dependența de algoritm în aceastã problemã. Deseori, cunoștințele umane în domeniul problemei asigurã alegerea celor mai bune soluții. De exemplu, includerea codului numeric personal sau a numãrului de asigurãri sociale ca variabile de predicție nu poate avea nici o implicație beneficã și în cel mai rãu caz poate reduce ponderea altor variabile de predicție.

b. Selectarea liniilor

Ca și în cazul selectãrii variabilelor, se încearcã folosirea tuturor liniilor de date existente în construirea modelului. Însã, în cazul unei mari cantitãți de date, poate dura mult prea mult timp, sau poate necesita folosirea unui calculator mai puternic.

Ca urmare, în cazul în care baza de date este de mari dimensiuni, se recomandã extragerea unor mostre. Acest lucru nu produce pierderi de informații, cât timp selectarea mostrei se face cu atenție, pentru a asigura faptul cã extragerea este pur și simplu întâmplãtoare. Având de ales între a investiga câteva modele construite pe baza tuturor datelor sau a investiga mai multe modele construite pe o mostrã, abordarea din urmã ajutã de cele mai multe ori la dezvoltarea unui model mai robust.

În cazul în care se dorește eliminarea datelor care sunt clar irelevante, deși în unele cazuri acestea pot conține înformații importante în construcția modelului, ele pot fi ignorate poe baza priceperii analistului.

c. Construirea de noi variabile

Adesea este necesarã construirea unor noi variabile de predicție, derivate de datele luate în calcul. De exemplu, pentru prezicerea riscului de creditare, folosind un raport datorii/venituri în loc de variabilele venit și datorii, se poate ajunge la rezultate mult mai bune și mai ușor de înțeles. Anumite variabile care au un impact mic folosite singure cer combinarea lor cu altele, folosind operații aritmetice sau algebrice (sume, fracții, etc.). În cazul în care anumite variabile iau valori într-un interval foarte mare, dimensiunea intervalului poate fi redusã prin folosirea de exemplu a logaritmului venitului în locul venitului.

d. Transformarea variabilelor

Unealta aleasã poate impune restricții asupra reprezentãrii datelor (de exemplu, explozia categoriilor folositã în rețelele neuronale). Variabilele pot fi aduse într-un anumit interval precum [0,1]. Mulți arbori de decizie folosiți pentru clasificare cer date continue precum venitul grupat pe categorii: mare, mediu, mic. Codarea aleasã poate influența rezultatul modelului.

4.2.5 Construirea modelului pentru data mining

Cel mai important lucru de care trebuie ținut cont în construirea unui model este acela cã este un proces iterativ. Trebuie exploatate mai multe modele pentru a-l gãsi pe acela care se potrivește cel mai bine problemei. Ceea ce se învațã în cãutarea unui model bun te poate trimite înapoi sa faci modificãri în datele pe care le folosești, sau sã faci modificãri în chiar enunțul problemei.

Odatã ce a fost ales tipul predicției ce urmeazã a fi fãcutã (clasificare sau regresie) trebuie ales un tip de model pentru a face aceastã predicție. Acesta poate fi un arbore de decizie, o rețea neuronalã sau o regresie logisticã. Alegerea tipului de model poate influența procesul de preparare a datelor.

De exemplu, o rețea neuronalã va necesita o explozie categoricã a variabilelor. Sau modelul poate cere ca datele sã urmeze un anumit format, ceea ce va necesita transformarea acestora. Din momentul în care datele sunt pregãtite, se poate începe antrenarea modelului.

Procesul de contruire a modelelor de predicție cere o antrenare bine definitã și un protocol de validare astfel încât sã asigure cele mai clare și robuste predicții. Acest tip de protocol este numit „învãțare supervizatã” Scopul învãțãrii supervizate este de a antrena modelul pe un subset al setului de date și apoi de a-l valida pe restul setului datelor.

Un model se considerã a fi construit când se încheie ciclul de antrenare și testare. Câteodatã, un al treilea set de date numit set de date de validare, este necesar deoarece datele de test ar putea influența etape ale modelului, iar setul de validare funcționeazã ca o mãsurã independentã de asigurare a acurateții modelului.

Antranarea și testarea modelului necesitã ca datele sã fie separate în cel puțin douã grupe: unul pentru antrenarea modelului (estimarea parametrilor modelului) și unul pentru testarea modelului. Dacã nu sunt folosite seturi diferite de date, acuratețea modelului poate fi supraestimatã. Dupã ce modelul este generat folosind o bazã de antrenare, este folosit sã prezicã o bazã de date de test, și rata acurateții rezultate este un estimator bun pentru felul în care modelul se va comporta în baze de date similare cu baza de date de antrenare și de test. Nu garanteazã faptul cã modelul este corect. Spune doar cã dacã aceeași tehnicã este folositã într-o succesiune de baze de date cu date similare cu cele din setul de test și cel de antrenare, acuratețea medie va fi apropiatã de cea obținutã în acest fel.

Validarea simplã

Cea mai comunã metodã de testare este validarea simplã. Aceastã se aplicã în felul urmãtor: se separã o anumitã parte a datelor din baza de date și se formeazã o bazã de date de test care nu se folosește sub nici o formã în construirea modelului sau estimãri. Aceastã parte a datelor reprezintã de obicei un procent între 5% și 33% din baza de date inițialã. Pentru ca toate calculele viitoare sã fie corecte, separarea datelor în douã grupuri trebuie fãcutã la întâmplare, astfel încât setul de antrenare și setul de test sã reflecte în cel mai bun mod modelarea.

Dupã construirea unui model din corpul de date principal, acesta este folosit pentru prezicerea claselor sau valorilor bazei de date de test. Împãrțind numãrul clasificãrilor incorecte la numãrul total de cazuri, obținem data erorii. Împãrțind numãrul clasificãrilor corecte la numãrul total de cazuri, obținem rata de acuratețe.

În contruirea unui singur model, chiar și validarea simplã trebuie fãcutã de câteva zeci de ori. De exepmplu, când se folosește o rețea neuronalã, câteodatã fiecare pas de antrenare prin rețea este confruntat cu o bazã de date de test. Antrenarea se oprește când rata de acuratețe nu se mai îmbunãtãțește.

Validarea încrucișatã

În cazul în care se lucreazã cu o cantitate modestã de date (câteva sute de linii) pentru construirea unui model, nu se mai poate sustrage un procent din cantitatea de date pentru o validare simplã.

Validarea încrucișatã este o metodã care permite folosirea tuturor datelor. Datele sunt împãrțite la întâmplare în douã seturi egale pentru a estima acuratețea predicției modelului. Mai întâi se construiește un model bazat pe primul set care este folosit pentru a prezice rezultate, iar în al doilea set, se calculeazã rata erorii. Apoi, rolurile celor douã seturi se schimbã. În final, se construiește un model folosind toate datele.

În mod normal, se folosește cazul general al validãrii încrucișate de ordin n. În aceastã metodã, datele sunt împãrțite la întâmplare în n grupe disjuncte. De exemplu, presupunem cã datele au fost împãrțite în zece grupe. Primul grup este pus deoparte pentru teste, iar celelalte nouã sunt folosite in construirea unui model. Modelul construit pe procentul de 90% din date este folosit apoi pentru a prezice grupul pus deoparte. Procesul se repetã de zece ori, dupã cum fiecare grup din cele zece este lãsat deoparte, iar celelalte nouã sunt folosite în construirea care va prezice grupul lãsat deoparte. În final, modelul este construit folosind toate datele. Media celor zece rate de eroare prezise este folositã ca ratã a erorii pentru modelul final.

Bootstrapping

Bootstrapping este o altã metodã pentru a estima eroarea unui model bazat pe un set mic de date. La fel ca în cazul validãrii încrucișate, modelul este construit pe setul de date întreg. Apoi, mai multe seturi de date numite mostre de bootstrap sunt extrase din setul de date originale. Dupã ce este extras fiecare subiect, este înlocuit și un nou subiect este selectat, pânã când este creatã o întreagã mostrã de bootstrap. Se observã cã înregistrãrile pot apãrea de mai multe ori în timp ce este extras un set de date. Un model este construit pe baza acestui set și se calculeazã o ratã a erorii. Aceasta se numește eroare de resubstituire. Se creazã de obicei mostre numeroase, cam peste o mie. Eroarea finalã estimatã pentru modelul construit pe întregul set de date este calculatã ca fiind media estimațiilor erorilor din fiecare mostrã.

Pe baza rezultatelor construirii modelului, se poate dori construirea unui alt model folosind aceeași tehnicã, dar parametri diferiți, sau se poate încerca folosirea altor algoritmi sau unelte. De exemplu, o altã abordare poate crește acuratețea. Nici o tehnicã sau unealtã nu este perfectã pentru toate datele și este dificil, dacã nu imposibil sã ne asigurãm înainte de început, care tehnicã va funcționa mai bine. Este normal sã se construiascã modelel numeroase, înainte de a gãsi un model satisfãcãtor.

4.2.6 Evaluare și interpretare

a. Validarea modelului

Dupã construirea unui model trebuie evaluate rezultatele acestuia și interpretate semnificațiile lor. Trebuie amintit cã rata de acuratețe gãsitã în timpul testãrilor se aplicã numai în cazul datelor, pe baza cãrora modelul a fost construit. În practicã, acuratețea poate varia dacã datele asupra cãrora modelul diferã în puncte esențiale fațã de setul inițial. Este important de reținut faptul cã acuratețea, de una singurã, nu este în mod necesar cel mai bun criteriu de selecție a unui model. Trebuie știut mai mult despre tipul erorilor și consturile asociate lor.

Matrici de confuzie

Pentru probleme de clasificare, o matrice de confuzie este o unealtã folositoare în înțelegerea rezultatelor. O matrice de confuzie confruntã realitatea cu valorile din clasele de predicție. Nu ilustrazã numai cât de bine se poate prezice un model, dar prezintã și detaliile necesare pentru a înțelege unde lucrurile au început sã funcționeze în mod greșit. Tabelul din figura urmãtoare reprezintã o matrice de confuzie. Coloanele aratã clasele reale, iar liniile aratã clasele prezise. Deci diagonala va ilustra predicțiile corecte. În matricea de confuzie se observã cã modelul a prezis 38 din cei 46 de subiecți din clasa B în mod corect, deci a greșit doar in 8 cazuri, pe care le-a trimis 2 în clasa A și 6 în clasa C. Aceastã matrice conține mult mai multã informație decât o ratã de acuratețe care spune cã au fost clasificate corect 123 de cazuri din 150.

În particular, dacã s-ar asocia costuri diferite la diferite erori, un model cu o acuratețe scãzutã per total poate fi preferabil unuia cu o acuratețe ridicatã, dar cu un cost mai mare datoratã acestui tip de erori pe care le face. Presupunând cã în matricea de confuzie fiecare rãspuns corect are o valoare de 10 puncte, și fiecare rãspuns incorect pentru clasa A costã 5 puncte, pentru clasa B costã 10 puncte și pentru clasa C costã 20 de puncte, atunci valoarea netã a matricii ar fi:

(123*10)-(5*5)-(12*10)-(10*20) = 885

Dacã se schimbã matricea de confuzie cu urmãtoarea reprezentatã mai jos, rata de acuratețe scade la 79%, însã valoarea netã va fi mai mare.

(118*10)-(22*5)-(7*10)-(3*20) = 940

Deci, dacã se dorește maximizarea valorii unui model, nu se recomandã alegerea unui model cu o acuratețe mai micã, deși are o valoare a matricii mai mare.

Metode grafice

Graficul câștigului este deasemenea un ajutor în evaluarea utilitãții unui model. Aratã în ce fel rãspunsurile sunt schimbate la aplicarea modelului. Rata de schimb poartã numele de lift. De exemplu, în loc de o ratã a rãspunsurilor de 10%, când un procent întâmplãtor de 10% din populație este solicitat, rata de rãspuns a unui procent de 10% anume ales este de peste 30%. În acest caz, valoare lift-ului este 3.

O altã componentã a interpretãrii este aprecierea valorii unui model. Reamintim cã un tipar poate fi interesant, dar acționând conform lui costã mai mult decât veniturile sau economiile pe care le genereazã. Graficul ROI (Return on Investment) este un exemplu bun pentru felul în crae atașarea unor valori unui rãspuns și costul unui program poate oferi îndrumare adiționala în alegerea unei decizii. În acest caz, ROI este definit ca raportul dintre profit si cost. Se observã cã dupã 80% valorile pentru ROI devin negative, iar valoarea maximã este atinsã la 20%.

Ca alternativã, se poate folosi graficul profitabilitãții unui model (prfitul este calculat ca venitul din care se scad costurile) dupã cum se vede in urmãtorul grafic:

b. Validarea externã

Dupã cum s-a arãtat, oricât de mare ar fi acuratețea unui model, nu existã garanții cã acesta va reflecta situații reale. Un model valid nu este în mod necesar un model corect. Una dintre principalele cazuri ale acestei probleme este faptul cã un model implicã mereu noi presupuneri. De exemplu, rata inflației poate nu a fost inclusã ca variabilã într-un model care prezice înclinația unui individ de a cumpãra, dar un salt al ratei inflației de la 3% la 17% va afecta în mod sigur comportamentul individului. Deasemenea, toate datele folosite pentru a construi modelul pot fi complet rupte de realitate, într-un anumit fel, ceea ce va conduce la un model incorect.

De aici, se trage concluzia cã este foarte importantã testarea unui model în lumea realã. Dacã un model este folosit pentru a selecta un subset de subiecți de pe o lista, se recomandã testarea subiecților pentru a verifica modelul. Dacã un model este folosit pentru a prezice riscul de creditare, modelul trebuie încercat pe un set redus de aplicanți pentru astfel de cereri, înainte de aplicarea pe întregul set de subiecți. Cu cât este mai mare riscul asociat unui model incorect, cu atât este mai importantã efectuarea unui experiment pentru verificarea rezultatelor modelului.

4.2.7 Aplicarea modelului și analiza rezultatelor

Din momentul în care un model pentru data mining este construit și validat, acesta poate fi folosit într-unul din urmãtoarele moduri:

analistul recomandã acțiuni bazate pe simpla vizionare a modelului și a rezultatelor. De exemplu, analistul poate privi cluster-ele pe care le-a identificat modelul, regulile definite de model, sau la graficele ROI.

aplicarea modelului asupra seturilor diferite de date. Modelul poate fi folosit pentru a însemna înregistrãri pe baza clasificãrii lor, sau pentru a asigna scoruri precum probabilitatea unei acțiuni. Modelul poate selecta câteva înregistrãri dintr-o bazã de date și sã le supunã unei analize mai amãnunțitã cu o unealtã OLAP.

Adesea, modelele sunt parte a unui proces din cadrul unor afaceri precum: analiza riscului, autorizarea creditului sau detectarea fraudelor. În aceste cazuri, modelul este încorporat într-o aplicație. De exemplu, un model predictiv poate fi integrat într-un proces de cerere a unui împrumut pe baza unei ipoteci pentru a ajuta personalul în evaluarea aplicantului. În alt caz, modelul poate fi incastrat într-o aplicație precum un inventar și sã dicteze sistemului generarea automatã a unei cereri de aprovizionare, când nivelul inventarului prezis scade sub o anumitã limitã.

Un model data mining este adesea aplicat unui singur eveniment sau unei singure tranzacții. Perioada de timp necesarã procesãrii unei noi tranzacții sau intervalul dupã care o nouã tranzacție sosește, va determina dacã un algoritm paralel este necesar sau nu. Astfel, în timp ce cererile de împrumut pot fi ușor evaluate pe un calculator cu performanțe medii, în monitorizarea tranzacțiilor fãcute cu ajutorul cardurilor sau a apelurilor realizate de pe telefoane celulare necesitã un sistem paralel pentru a face fațã unei rate de tranzacție foarte mare.

În timp ce servește o aplicație complexã, o tehnicã data mining este de obicei doar o micã parte a procesului final. De exemplu, descoperirea cunoștințelor prin intermediul tehnicilor data mining, poate fi combinatã cu cunoștințele experților în domeniu, și aplicatã datelor din baza de date și din tranzacțiile viitoare. În sistemul de detectare a fraudelor, tiparele cunoscute de fraudã pot fi combinate cu tiparele descoperite. Când cazuri suspecte de fraudã sunt prezentate investigatorilor pentru evaluare, aceștia pot avea nevoie sã acceseze înregistrãrile bazei de date în legãturã cu alte reclamații depuse de același reclamant sau care implicã aceeași reclamați.

Monitorizarea modelului

Întotdeauna trebuie mãsurat gradul de funcționare a unui model, dupã ce a fost folosit. Oricum, faptul cã modelul funcționeazã bine nu înseamnã cã acest lucru se va întâmpla mereu și performanțele sale trebuie monitorizate permanent. În timp, toate sistemele evolueazã. Experții în vânzãri știu cã tiparele de achiziție se schimbã în timp. Variabile externe precum rata inflației se pot schimba îndeajuns încât sã modifice comportamentul oamenilor. Deasemenea, din timp în timp un model trebuie retestat, reantranat și poate chiar reconstruit. Graficele diferențelor dintre valorile prezise și observate sunt o cale excelentã de a monitoriza rezultatele modelului. Astfel de grafice sunt ușor de folosit și de înțeles, nu cer calcule intensive și pot fi construite în cadrul soft-ului care impelmenteazã modelul. Astfel, sistemul se poate monitoriza singur.

Capitolul 5

PRODUSE ȘI APLICAȚII DATA MINING

5.1 Categorii de produse data mining

În evaluarea uneltelor de data mining , acestea trebuie privite în întregul lor ansamblu dupã cum au fost descrise în capitolele anterioare. Uneltele de data mining nu pot fi categorisite pur și simplu „cu finalitate înaltã” sau „cu finalitate redusã” deoarece produsele sunt mult prea bogate in funcționalitãți pentru a fi judecate dupã o singurã dimensiune.

Existã trei tipuri principale de produse data mining.

1. Unelte folosite pentru analiza OLAP (identificã cele mai importante dimensiuni și segmente asupra cãrora trebuie îndreptatã atenția): Business Objects Business Miner și Cognos Scenario;

2. Unelte „pure” data mining, care sunt reglate pentru rezolvarea unei game largi de probleme: IBM Intelligent Miner, Oracle Darwin, SAS Entreprise Miner, SGI Mine Set, SPSS Clementine;

3. Unelte care implementeazã procese specifice afacerilor, pentru care data mining este parte integralã; pot fi cumpãrate pachete personalizate pentru afaceri cu unelte data mining incorporate; Oricum, chiar și soluția împachetãrii uneltelor data mining cere construirea unor modele care sã se potriveascã datelor utilizatorului. În unele cazuri, pachetul poate necesita o fazã de dezvoltare completã a modelului care poate dura luni de zile.

Selecția uneltelor de data mining se aplicã celor din ultimele douã categorii, dar oricât de detaliatã ar fi o listã a capabilitãților creatã pentru a descie un produs data mining, nimic nu înlocuiește testare efectivã a uneltei. Chiar dacã aceste liste sunt parte componentã a procesului de selecție, ele nu sunt folosite decât pentru a elimina produsele care nu îndeplinesc toate cerințele necesare.

5.2 Capabilitãți esențiale

În funcție de împrejurãri (arhitectura sistemului, resurse de personal, dimensiunea bazei de date, complexitatea problemei) unele produse data mining vor fi mai adecvate decât altele, pentru cerințele utilizatorului. Evaluarea unui produs data mining implicã cunoașterea capabilitãților lui în anumite domenii cheie, care poate nu sunt atinse în prezentãrile de marketing. De exemplu, lucrarea Data Mining ’99 : Technology Report conține rãspunsurile a 24 de vânzãtori la chestionare care acoperã aceste domenii pentru 26 de produse data mining.

Arhitectura sistemului. Produsul poate fi fãcut pentru a lucra pe un calculator, sau cu o arhitecturã client-server. Însã nu dimensiunea mașinii pe care ruleaza programul este un identificator de încredere pentru complexitatea problemei. Produse foarte sofisticate care pot rezolva probleme complexe și care sã necesite utilizatori pricepuți, pot rula la fel de bine pe un calculator sau pe un sistem client-server.

Prepararea datelor. Este pe departe aspectul data mining care necesitã cele mai multe resurse temporale. Include funcții precum:

curãțarea datelor (lucru cu datele lipsã, identificarea violãrilor integritãții);

descrierea datelor (calculul valorilor din linii, al distribuției valorilor, etc);

transformãrile datelor (adãugarea de noi coloane, efectuarea unor calcule pe baza coloanelor existente, gruparea variabilelor continue în arii de valori, explziile variabilelor categorice în variabile de dihotomie);

extragerea de mostre pentru construirea unui model sau pentru crearea de seturi de date de antrenare sau validare;

selectarea predictorilor din spațiul variabilelor și identificarea coloanelor liniare;

Accesul la date. Unele unelte de data mining cer ca datele sã fie extrase din baza de date țintã într-un format intern. O tehnicã data mining trebuie sã fie capabilã sã acceseze direct structuri de date pentru a maximiza performanțele și a profita de avantaje precum accesul paralel la baza de date. Nici un produs însã nu poate suporta întreaga varietate de servere de baze de date.

Algoritmi. Trebuie înțelese caracteristicile algoritmilor pe care produsele data mining le folosesc pentru a determina dacã se potrivesc caracteristicilor problemei. În particular, trebuie învãțat cum un algoritm trateazã tipuri de date ale rãspunsului și ale variabilelor de predicție, cât de repede se antreneazã și cât de repede lucreazã cu date noi.

O altã trãsãtura importantã a unui algoritm este sensibilitatea la date irelevante. Datele reale au coloane irelevante, subiecți care nu se încadreazã în tiparul gãsit de model și valori lipsã sau incorecte.

Ne punem întrebarea câte astfel de date poate ignora un algoritm pânã când acuratețea lui scade. În unele cazuri, simpla adãugare de date reduce problemele, dar însãși adãugarea de date noi reprezintã o problemã care poate reduce acuratețea.

Interfețe cãtre alte produse. Existã mai multe unelte care pot ajuta utilizatorul sã-și înțeleagã datele înaintea de construirea unui model și sã interpreteze rezultatele modelului. Acestea includ tradiționalele rapoarte, unelte grafice și de vizualizare și unelte OLAP.

Software-ul de data mining care asigurã cãi facile de integrare cu produsele altor companii oferã utilizatorilor cãi multiple de a exploata la maxim procesul de descoperire a cunoștințelor.

Evaluarea modelului și interpretarea. Existã unelte care îndrumã utilizatorul în înțelegerea rezultatelor printr-o ofertã de indici de mãsurã a calitãții, precum: acuratețea, importanța, etc. într-un format ușor de manevrat precum matrici de confuzie sau grafice ROI, sau prin prezentãri grafice ale rezultatelor.

Desfãșurarea modelului. Rezultatul unui model poate fi aplicat prin introducerea lui într-o bazã de date sau prin extragerea de informații din cadrul lui. Când este necesarã aplicarea modelului asupra noilor subiecți care apar, este în general necesarã și încorporarea modelului într-un program, folosind un cod generat de o uneealtã data mining. Una dintre problemele cheie în desfãșurarea modelelor este efectuarea transformãrilor necesare pentru a face predicții și multe dintre uneltele de data mining considerã acest lucru o sarcinã separatã pentru utilizator sau programator.

Scalabilitatea. Cât de eficientã este o unealtã în lucrul cu cantitãți mari de date, atât linii cât și coloane, sau cu tehnici de validare sofisticate? Aceste provocãri cer abilitatea de a profita de resursele hardware. Ce tipuri de paralelism suportã tehnica? Algoritmii de data mining scriși pentru structuri uniprocesor nu vor rula mai rapid pe sisteme paralele, ci trebuie rescriși pentru a lua în calcul structura paralelã și existã douã moduri de a realiza acest lucru:

bucãți independente ale aplicației, sunt asignate la diferite procesoare. Cu cât mai multe procesoare, cu atât mai multe bucãți pot fi executate simultan. Acest mod poartã numele de „paralelism inter-modele” și este util în construirea mai multor modele independente. De exemplu, o aplicare a unei rețele neuronale poate construi diferite modele cu fiecare procesor simultan, folosind arhitecturi care diferã prin numãrul de noduri sau de strate ascunse.

în cazul în care construirea unui model dureazã foarte mult este nevoie ca acest model sã fie descompus în sarcini executate fiecare de cãtre un procesor și apoi recombinate în rãspuns. Acest mod poartã numele de „paralelism intra-modele”

Înterfața cu utilizatorul. Pentru a ușura construirea unui model, unele produse oferã o interfațã graficã pentru construirea semiautomatã a modelelor, în timp ce altele pot oferi un limbaj de descriere.

Unele produse pot oferi generatoare de cod ce pot fi include în limbaje de programare. Însã, datoritã deciziilor tehnice foarte importante în prepararea și selectarea datelor și alegerea strategiei de modelare, chiar și o interfațã graficã ce simplificã construirea modelului cere experiențã pentru gãsirea celor mai eficiente modele. Interfața cu utilizatorul a unui produs trebuie evaluatã în funcție de adaptabilitatea la fiecare categorie de utilizatori.

5.3 Forarea în World Wide Web

Scopul este crearea unor baze de date structurate conținând informații utile prin extragerea automatã a acestor informații din cadrul World Wide Web sau din alte surse Internet. Aceastã aplicație va permite tratarea WWW ca o imensã bazã de date care poate fi foratã cu ajutorul limbajelor de manipulare a bazelor de date și prin metode de inferențã deductivã.

Acest lucru va oferi:

Unelte de recuperare a datelor mult mai puternice decât actualele cãutãri dupã cheie;

Dezvoltarea unor asistenți virtuali bazați pe cunoștințe care folosesc WWW ca bazã de cunoștințe;

Noi abordãri ale tehnicii data mining în cadrul cãreia bazele de date curente vor fi mãrite prin adãugarea de informații extrase de pe WWW.

Abordarea tehnicã a acestei probleme constã în dezvoltarea unor algoritmi de învãțare automatã care pot fi antrenați sã extragã informații prin monitorizarea WWW. Este suficient ca utilizatorul sã defineascã clase și relații care sã fie extrase și sã ofere exemple de antrenare acestor algoritmi. Sistemul folosește datele de antrenare pentru a învãța proceduri originale de extragere a informațiilor din paginile WWW.

Au fost dezvoltați câțiva algoritmi pentru a rezolva aceastã problemã, precum:

algoritmi care clasificã paginile WWW dupã cuvintele conținute;

algoritmi care învațã sã identifice subcâmpuri relevante în textul unui document;

S-a demonstrat cã aceste metode pot învãța sã extragã informații despre universitãți, studenți,cursuri și proiecte, de exemplu, cu o precizie de aproximativ 70%. Proiectele curente cautã sã îmbunãtãțeascã acuratețea acestor informații, prin:

– implicarea analizei lingvistice a textelor;

– ierarhizarea claselor și a relațiilor;

– algoritmi care învațã dintr-o combinație de date de antrenare etichetate și neetichetate;

De asemenea, se încearca explorarea folosirii informației extrase. De exemplu, se încearcã crearea unui agent expert care acceptã descrierea textualã a unui proiect și apoi localizeazã cel mai adecvat expert în aceastã problemã pentru consultanțã.

5.3.1 Ierarhizarea paginilor

Este o tehnicã folositã pentru a descoperi cele mai importante pagini de web. Definiția „importanței” este una recursivã: o paginã este importantã, dacã alte pagini importante sunt legate de ea.

Dacã se creazã o matrice stochasticã a rețelei, aceasta este definitã astfel:

1.Fiecãrei pagini i îi corespunde elementul de pe coloana i și linia i din matrice;

2.Dacã pagina j are n succesori (legãturi) atunci elementul ij este 1/n dacã pagina i este unul dintre succesori și 0 în caz contrar.

Premisele care stau la baza acestei matrici sunt:

ne imaginãm cã inițial fiecare paginã are o singurã unitate de importanțã: pe rând, fiecare paginã va împãrți importanța cu succesorii sãi și va primi importanțã de la predecesori;

eventual, importanța fiecãrei pagini atinge o limitã care va fi componenta sa în eigen vector-ul” principal al matricii;

importanța este de asemenea probabilitatea ca un navigator pe web, începând de la o paginã aleatoare și urmãrind legãturi aleatoare din fiecare paginã sã ajungã la pagina în discuție.

Exemplu:

Considerând WWW ca fiind format doar din trei pagini: Netscape, Microsoft și Amazon, legate astfel:

Fie [n,m,a] vectorul importanțelor celor trei pagini: Netscape, Microsoft și Amazon, în aceastã ordine. Atunci ecuația care descrie valorile acestor trei variabile este:

De exemplu, prima coloanã a matricii reflectã faptul cã Netscape împarte importanța între ea însãși și Amazon. A doua coloanã indicã faptul cã Microsoft ofertã toatã importanța sa paginii Amazon. Se pot rezolva astfel de ecuații începând cu presupunerea cã n = m = a = 1 și aplicând repetat matricea estimației curente acestor valori. Primele patru iterații oferã urmãtoarele estimații:

La sfârșitul calculelor, soluția este n = a = 6/5, m = 3/5, ceea ce înseamnã cã Netscape și Amazon au aceeași importanțã și de douã ori importanța paginii Microsoft.

Observații:

Nu se vor obține niciodatã valori absolute pentru n, m, a din momentul în care presupunerea inițialã a fost arbitrarã;

Deoarece matricea este stochasticã (suma pe fiecare coloanã este 1) procesul descris anterior converge cãtre „eigen vectorul” principal.

5.3.2 Probleme cu grafurile rețelei reale

Deadends (înfundãturi): o paginã care nu are succesori nu are unde sã-și transmitã importanța și, eventual, aceasta se va scurge din web;

Spider traps (capcane): un grup format din una sau mai multe pagini care nu au legãturi în afara grupului, fapt care va cauza acumularea întregii importanțe a web-ului.

Exemplu de deadend:

Presupunem cã pagina Microsoft nu mai are nici o legãturã în afara ei. Noua rețea va arãta astfel:

și matricea de tranziție este:

Primii patru pași ai soluției iterative sunt:

Se observã o scãdere continuã a valorilor care în cele din urmã vor deveni 0, deci toatã importanța se va „scurge”.

Exemplu de spider trap:

Presupunem cã pagina Microsoft are legãturã numai cu ea însãși, devenind astfel o capcanã. Noua rețea va arãta astfel:

și matricea care descrie tranzițiile este :

Primii pași ai soluției iterative sunt:

Se observã cã valoarea lui m converge spre 3, pe când celelalte converg la 0.

5.3.3 Soluții Google pentru problemele rețelei

În loc sã se aplicea matricea direct, fiecare paginã este „taxatã” cu un procent din importanța ei și importanța taxatã este distribuitã tuturor paginilor:

Dupã ce se aplicã o taxã de 20%, ecuația devine:

Soluția acestei ecuații este:

care reprezintã o distribuție a importanței mult mai rezonabilã decât în exemplele anterioare.

5.3.4 Dispozitive anti-spam

Prin apamming se înțelege încercarea mai multor site-uri web de a pãrea legate de un anumit subiect care sã atragã navigatorii, fãrã sã aibã într-adevãr acel subiect.

Google, ca oricare alt motor de cãutare, încearcã sã potriveascã cuvintele din cererea navigatorului cu cuvintele din pagina web însã, spre deosebire de acestea, Google încearcã sã înțeleagã ceea ce alte pagini spun despre o altã paginã în textele ancorã, îngreunând astfel încercarea paginii de apaãrea legatã de alt subiect.

Folosirea rangului unei pagini pentru a mãsura importanța, mai degrabã decât naivul „numãr de legãturi spre paginã” oferã de asemenea protecție împotriva spammingului; vechea mãsurã putea fi pãcãlitã de spammeri care pot crea 1000 de pagini care se leagã mutual una de cealaltã, în timp ce rangul paginii nu recunoaște importanța niciuneia dintre acele pagini.

5.3.5 Centri și autoritãți

In mod intuitiv, centrii și autoritãțile sunt definite mutual recursiv: un centru se leagã la mai multe autoritãți, și o autoritate este legatã la mai mulți centri:

Autoritãțile se dovedesc a fi pagini care oferã informații în legãturã cu un subiect;

Centrii sunt pagini care nu oferã informație, dar spun unde se gãsește informația;

Se folosește o matrice similarã cu cea a rangului paginilor, dar fãrã restricția stochasticã; fiecare legãturã se contorizeazã cu unu, indiferent câți succesori sau predecesori are o pagina;

Aplicarea repetatã a matricii duce la divergențã dar se pot introduce și valori de scalare care sã pãstreze valorile calculate pentru autoritãți și centri, pentru fiecare paginã, în limite finite.

Se definește matricea A ale cãrei linii și coloane corespund paginilor web, cu intrãrile:

se obsevã cã AT, transpusa matricii A, seamãnã cu matricea folositã pentru calculul rangurilor, dar AT are valoarea 1, unde matricea pentru rang are fracții.

Fie a și h vectori ale cãror componente corespund gradului de autoritate și de centru al paginii i. Fie λ și μ factori de scalare potriviți care urmeazã a fi determinați. Putem exprima:

h = λAa : gradul de centru al fiecãrei pagini este suma autoritãților tuturor paginilor legate de ea, scalate prin λ.

a = μATh : autoritatea fiecãrei pagini este suma gradelor de centru al tuturor paginilor legate de ea, scalatã prin μ.

Relațiile 1. și 2. pot fi transformate și se obțin douã ecuații în care vectorii a și h sunt calculați doar în funcție de propriile valori:

Drept urmare, se pot calcula valorile pentru a și h și rezultã vectorii principali pentru matricile A și AT.

Exemplu:

Matricile pentru acest exemplu sunt:

Dacã folosim λ=μ=1 și presupunem cã vectorii h = [hn,hm,ha] și a = [an,am,aa] sunt fiecare egali cu vectorul [1,1,1], atunci primele trei iterații ale ecuațiilor pentru a și h sunt:

5.3.6 Gãsirea seturilor de obiecte neobișnuite

Problema care se pune este gãsirea seturilor de cuvinte care apar împreunã neobișnuit de des pe Web, precum: „New” și „York” sau {„ducesa”, „de”, „York”}.

neobișnuit de des poate fi definit în multe feluri in încercarea de a cuprinde ideea cã un numãr de documente Web conținând un set de cuvinte este mult mai mare decât acela care ar fi de așteptat în cazul în care cuvintele ar fi întâlnite aleator, fiecare cuvânt cu o anumitã probabilitate de apariție într-un document.

una dintre cele mai întâlnite definiții este aceea prin entropia unui cuvânt într-un set; Prin interesul pe care îl prezintã, un cuvânt S într-un set de cuvinte se înțelege:

Exemplu: dacã trei cuvinte: a,b,c apar în 1% din toate documentele și S={a,b,c} apare în 0.1% din documente, atunci gradul de interes pe care îl prezintã S este:

În cazul în care apar mai mult de 108 cuvinte diferite pe Web, nu este posibil sã se ia în calcul toate perechile de cuvinte.

5.3.7 Motorul DICE

Motorul DICE (Dynamic Itemset Counting Engine) viziteazã în mod repetat paginile de Web, într-o manierã round-robin. De fiecare datã numãrã aparițiile anumitor seturi de cuvinte și al tuturor cuvintelor din set, luate individual. Numãrul de seturi luate în calcul este suficient de mic încât numãrãtoarea sã poatã folosi memoria principalã.

La un anumit interval, de exemplu la fiecare 5000 de pagini, DICE retesteazã seturile pe care le calculeazã. Lasã deoparte acele seturi care prezintã mai puțin interes și le înlocuiește cu alte seturi.

Alegerea noilor seturi se bazeazã pe observația verificatã de experimente conform cãreia acele cuvinte care apar într-un set de mare interes apar cu o probabilitate mai mare de apariție în alte seturi de mare interes. Astfel, când selecteazã noi seturi de cuvinte pentru a reîncepe numãrãtoarea, DICE înclinã în favoarea cuvintelor care apar deja în seturi de mare interes. Oricum, nu se bazeazã exclusiv pe acele cuvinte cãci, în caz contrar nu va putea gãsi niciodatã seturi de mare interes compuse din multe cuvinte pe care nu le-a verificat. Câteva (dar nu toate) din construcțiile pe care DICE le folosește pentru a creea seturi noi sunt:

Douã cuvinte aleatoare – aceasta este singura regulã care este independentã de presupunerea anterioarã și ajutã la pãtrunderea de noi cuvinte în memorie;

Un cuvânt dintr-un set interesant și un cuvânt aleator;

Douã cuvinte din douã seturi interesante diferite

Reuniunea a douã seturi interesante a cãror intersecție conține douã sau mai multe cuvinte

Setul {a, b, c}, dacã toate seturile {a, b}, {b, c}, {a, c}sunt interesante.

5.3.8 Cãrți și autori

Ideea principalã este de a cãuta pe Web obiecte de un anumit tip care pot fi exprimate sub forma unui tuplu precum Cãrți (titlu, autor).

Algoritmul extragerii relațiilor de pe Web:

1. Se începe cu o mostrã de tupluri care sunt cãutate (se dau exemple de titluri de cãrți și autorii lor);

2. Fiind dat un set de exemple cunoscute, se localizeazã aparițiile lor pe Web. Dacã se gãsește un tipar în care se încadreazã mai multe exemple de tupluri cunoscute și este puțin probabil sã se gãseascã un tipar în care se încadreazã mai bine, atunci se acceptã acest tipar;

3. Fiind dat un set de tipare acceptate, se gãsesc datele care se încadreazã în aceste tipare și se adaugã la setul de date cunoscute.

4. Se repetã pașii (2) și (3) de mai multe ori. În exemplul dat, la patru repetãri se gãsesc 15 000 de tupluri și care 95% din ele sunt perechi reale titlu-autor.

5.3.9 Ce este acela un tipar?

Noțiunea de tipar este compusã din cinci elemente:

Ordinea: titlul apare înaintea autorului în text, sau viceversa; într-un caz mai general, când tuplurile au mai mult de douã componente, ordinea ar putea fi permutãrile componentelor;

Prefixul URL;

Prefixul textului, precedent primei apariții a titlului sau a autorului ;

Centrul, textul cuprins între douã date;

Sufixul textului, care urmeazã celui de-al doilea element. Ambele, prefixul și sufixul, sunt limitate la zece caractere.

Exemplu:

Un tipar posibil ar consta în:

Ordinea: titlu, apoi autor;

Prefix URL: www.stanford.edu/class/ ;

Prefix, centru și sufix de forma urmãtoare:

<LI><I> titlu </I> de autor <P>

Prefixul este <LI><I>, centrul este </I> de (inclusiv spațiul dupã „de”) și sufixul este <P>. Titlul este tot ceea ce apare între prefix și centru. Autor este tot ceea ce apare între centru și sufix.

Intuiției care stã la baza acestui tipar i se poate gãsi justificarea dupã parcurgerea listelor de lecturã pentru cursurile de la Stanford.

Existã mai multe restricții asupra tiparelor:

Specificitatea unui tipar este datã de lungimile prefixului, centrului, sufixului și a prefixului URL; În mod normal, specificitatea mãsoarã probabilitatea de a gãsi un tipar: cu cât este mai mare specificitatea, cu atât ne așteptãm la mai puține apariții.

Un tipar trebuie sã îndeplineascã douã condiții pentru a fi acceptat:

trebuie sã existe un set format din cel puțin douã date în acest tipar;

produsul dintre specificitatea unui tipar și numãrul de apariții al datelor în tipar trebuie sã depãșeascã o anumitã granițã (nespecificatã)

5.3.10 Apariții ale datelor

O apariție a unui tuplu este asociatã cu un tipar în care apare: același titlu sau autor pot apãrea în mai multe tipare diferite. În acest caz, o apariție a unei informații se considerã a fi formatã din:

1. titlul și autorul;

2. adresa URL completã, nu doar prefixul ca la tipar;

3. ordinea, prefixul, centrul și sufixul tiparului în care apar titlul și autorul.

Fiind date câteva perechi titlu-autor, primul pas în gãsirea noilor tipare este cãutarea pe Web pentru a gãsi apariții ale acestora. Presupunând cã existã o indexare a paginilor Web și având un cuvânt dat, se pot gãsi toate paginile care conțin acel cuvânt. Metoda folositã este una a-priori:

se gãsesc toate acele pagini care conțin un autor cunoscut; din moment ce numele autorului este format în general din douã cuvinte, se cautã fiecare dintre ele și se verificã dacã aparițiile acestora sunt consecutive în document;

se gãsesc toate acele pagini care conțin un titlu cunoscut. Se începe prin gãsirea tuturor paginilor care conțin cuvintele din acel titlu și se verificã apoi dacã acele cuvinte apar în ordinea din titlu.

se intersecteazã seturile de pagini care conțin autorul și titlul. Vor fi cercetate doar acele pagini din intersecție pentru a gãsi un tipar. Pentru sufix și prefix se iau cele zece caractere înconjurãtoare, sau mai puține dacã nu existã zece.

5.3.11. Construirea tiparelor din apariții ale datelor

Aparițiile datelor se grupeazã dupã ordine și centri. De exemplu, un grup poate sã corespundã aparițiilor cu ordinea „titlu apoi autor” și centrul „</I> by”;

pentru fiecare grup, se gãsește cel mai lung prefix, sufix, sau prefix URL comun.

dacã este trecut testul de specificitate al tiparului, atunci acesta este acceptat.

dacã testul nu este trecut, se încearcã separarea grupului în douã, prin creșterea lungimii prefixului URL cu un caracter și se repetã procesul de la pasul doi. Dacã este imposibilã separarea grupului (deoarece existã un singur URL), atunci nu se poate crea un tipar din grup.

Exemplu:

Presupunem cã grupul în cauzã conține trei URL-uri:

www.stanford.edu/class/cs345/index.html

www.stanford.edu/class/cs145/intro.html

www.stanford.edu/class/cs140/readings.html

Prefixul comun este www.stanford.edu/class/cs . Dacã ar trebui separat grupul, atunci urmãtorul caracter, care la o adresã este 3 și la celelalte este 1, separã grupul în douã, cu aparițiile de pe prima paginã mergând într-un grup și cu cele de pe urmãtoarele douã în alt grup.

Fiind date mai multe tipare, aparițiile datelor se gãses astfel:

se gãsesc toate adresele, care se potrivesc cu prefixul URL în cel puțin un tipar;

pentru fiecrae din acele pagini, se scaneazã textul, folosind expresii regulate, construite din prefixul, centrul și sufixul tiparului;

se extrage din fiecare potrivire titlul și autorul, conform ordinii specificate în tipar.

5.4 Învãțarea automatelor

5.4.1 Capacitatea roboților de a învãța

Scopul cercetãrii posibilitãții roboților de a învãța este acela de a dezvolta algoritmi și tehnici de învãțare în cazul roboticii. De exemplu, este încurajatã cercetarea metodelor de achiziționare a modelelor spațiale bazate pe date înregistrate de roboți mobili, iar datele obținute sunt folosite de tehnicile de învãțare pentru a genera autocontrol pentru acești roboți.

Cercetarea acestei posibilitãți poate duce la o familie de roboți mai puternicã. Abilitatea de a învãța din experiențã va da posibilitatea acestor roboți de a conlucra cu o mare varietate de sarcini și în medii mai puțin predictibile decât roboții actuali. Pentru a dezvolta aceastã abilitate la roboți, este necesarã o înțelegere atentã a felului cum se extrag cunoștințele dintr-o cantitate mare de date numerice și grafice furnizate de senzori, o analizã a interacțiunii cu mediile fizice în timpul învãțãrii și construirea unor algoritmi de învãțare eficienți.

Una dintre direcțiile de cercetare este studierea cauzului roboților cu viațã lungã, care înfruntã o întreagã colecție de sarcini de învãțare. Au fost dezvoltați algoritmi speciali care studiazã tehnicile de învãțare cunoscute și genereazã „meta-cunoștințe” generale folosite pentru a dirija învãțarea când robotul înfruntã noi sarcini de învãțare. Ca urmare, roboții „au fost învãțați sã învețe”.

O altã direcție de cercetare este utilitatea modelelor statistice în contextul roboticii. Pânã acum, statistica a fost aplicatã cu succes în probleme ale roboticii, precum: localizare, mapare, recunoașterea obiectelor, navigare și explorare.

5.4.2 Ce se înțelege prin învãțarea automatelor?

Învãțarea acoperã o gamã largã de procese, motiv pentru care este dificil sã se defineascã precis. O definiție din dicționar conține fraze precum: „A obține cunoștințe sau a înțelege cunoștințele prin studiu, instruire sau experiențã” și „modificãri ale pornirilor comportamentale în urma experienței”.

Zoologii și fiziologii studiazã învãțarea la animale și la oameni. Existã câteva paralele între învãțarea la animale si învãțarea automatelor, multe tehnici folosite în învãțarea automatelor derivând din eforturile fiziologilor de a-și prezenta teoriile referitoare la învãțarea la animale și la oameni prin intermediul unor modele informatice; Este posibil însã și faptul ca unele dintre conceptele și tehnicile studiate de cercetãtorii în domeniul automatelor sã lumineze anumite aspecte al învãțarii biologice.

În ceea ce privește automatele, se poate spune cã un automat învața în momentul în care își schimbã structura, programul sau datele, pe baza unor intrãri sau ca rãspuns la informații externe, în așa fel încât performanțele sale viitoare sã creascã. Unele dintre aceste schimbãri, precum adãugarea unei inregistrãri la baza de date, țin de alte domenii și nu se poate spune cã automatul a învãțat, însã când performanțele unui dispozitiv de recunoaștere a vorbirii se îmbunãtãțesc dupã ce
”a ascultat” mai multe fragmente din discusul unei persoane, este justificat sã se spunã cã automatul a învãțat.

Învãțarea auotmatelor se referã de obicei la schimbãri în sisteme care îndeplinesc sarcini asociate cu inteligența artificialã („I.A.”). Astfel de sarcini implicã recunoaștere, diagnozã, planificare, controlul roboților, predicție, etc. Schimbãrile pot fi fie îmbunãtãțiri ale sistemelor deja existente, fie sinteze ale unor noi sisteme.

Pentru mai multã claritate, aceasta este arhitectura unui agent inteligent:

Acest agent percepe și modeleazã mediul sãu înconjurãtor și calculeazã acțiuni potrivite, probabil prin anticiparea efectelor lor. Schimbãrile fãcute în oricare din componentele sale fac parte din învãțare. Diferite mecanisme de învãțare pot fi implicate în funcție de subsistemul care este schimbat.

Se pot pune întrebãrile: „De ce automatele trebuie sã învețe ?”, „De ce nu se proiecteazã automate care sã acționeze cum dorim încã de la început ?”, și existã mai multe rãspunsuri. Deja s-a menționat ajutorul oferit în înțelegerea modului în care învațã oamenii sau animalele, însã existã și mai multe motive inginerești, precum:

Unele sarcini nu pot fi definite decât prin exemple; Se pot specifica perechi de intrare – ieșire, însã nu și relația precisã dintre intrãri și ieșirile dorite; Automatele trebuie sã fie capabile sã porducã ieșiri corecte pentru un numãr mare de intrãri și deci sã-și ajusteze funcția de intrare-ieșire pentru a aproxima relația dintre intrãri și ieșiri din exemple.

Este posibil ca în aglomerãri mari de date sã existe relații și corelații; Metodele folosite pentru învãțarea automatelor pot fi folosite pentru a extrage aceste relații (data minig);

Experții umani proiecteazã automate care de cele mai multe ori nu funcționeazã la fel de bine în diferite medii; de fapt, anumite caracteristici ale mediului de lucru pot fi imcomplet cunoscute în momentul proiectãrii. Metodele de invãțare a automatelor pot fi folosite pentru ajustarea în funcție de mediu a proiectelor existente.

Cantitatea de cunoștințe disponibilã în legãturã cu anumite sarcini poate fi prea mare pentru a putea fi codatã de experții umani; Automatele care invațã aceste cunoștințe gradat pot fi capabile sã cuprindã mai mult decât ar fi vrut experții umani sã codeze.

Mediile de lucru se schimbã în timp; Automatele care se adapteazã la un mediu în schimbare ar reduce nevoia constantã de reproiectare;

Informații noi despre sarcini sunt descoperite in mod constant; Vocabularul se schimbã; existã mereu evenimente noi în lume; reproiectarea sistemelor I.A. conform noilor informații nu este practicã, însã metodele de învãțare a automatelor pot fi capabile sã ținã pasul cu schimbãrile.

5.4.3 Contribuții în învãțarea automatelor

Cercetarea în învãțarea automatelor se bazeazã pe cercetãri în alte domenii de tradiție, fiecare din acestea aducând diferite metode și un vocabular specific și toate acestea sunt acum asimilate într-o disciplinã unificatã. Câteva dintre aceste discipline sunt:

Statistica. Una dintre cele mai vechi probleme în statisticã este estimarea cât mai bunã a valorilor unei funcții necunoscute într-un punct nou, fiind cunoscute valorile în anumite puncte. Metodele statistice de rezolvare a acestei probleme pot fi considerate instanțe ale învãțãrii automatelor, deoarece regulile de decizie și estimare depind de un grup de mostre extrase din mediul problemei.

Modele neuronale. Elemente non-liniare cu intrãri ponderate sunt propuse ca modele simple ale neuronilor biologici. Modelatorii acestor elemente sunt interesați cât de aproape aceste rețele aproximeazã fenomenul de învãțare al creierelor biologice. Multe tehnici de învãțare a automatelor sunt bazate pe rețele de elemente non-liniare (rețele neuronale).

Teoria controlului pentru adaptare. Teoreticienii studiazã problema controlãrii unui proces cu parametri necunoscuți care trebuie estimați în timpul desfãșurãrii acestuia. Adesea, parametrii se schimbã în timpul unei operații și procesul de control trebuie sã ținã o evidențã a acestor schimbãri. O astfel de problemã o reprezintã controlul roboților bazat pe impulsuri senzoriale.

Modele psihologice. Psihologii au studiat performanțele umane în diferite sarcini de învãțare, ceea ce a dus la dezvoltarea unei noi ramuri: învãțarea dirijatã.

Inteligența artificialã. Încã de la început, cercetarea in inteligența artificialã a fost îndreptatã cãtre învãțarea automatelor. Cercetãtorii I.A. au explorat rolul analogiilor în învãțare și felul in care acțiuni viitoare și decizii pot fi bazate pe cazuri precedente. Direcții noi sunt: descoperirea regulilor pentru sisteme expert folosind metode bazate pe arbori de decizie și programarea logico-inductivã.

Modele evoluționiste. În naturã, speciile evolueazã pentru a acționa mai bine conform nevoilor proprii. Deoarece distincția dintre „a evolua” și „a învãța” poate fi destul de neclarã în domeniul computerelor, tehnicile care modeleazã anumite aspecte ale evoluției biologice au fost propuse ca metode de învãțare pentru a îmbunãtãți performanțele programelor computerelor. Algoritmii genetici și programarea geneticã sunt cele mai cunoscute tehnici folosite în aceastã evoluție.

Învãțarea probabilã aproximativ corectã

S-a pus problema calculului unei funcții fiind dat un set de valori de intrare și de ieșire; Prin diferite prelucrãri ale datelor se poate ghici „aproximativ corect” valorile funcției pentru alte intrãri. Pe scurt, fiind dat un set de tipare de antrenare potrivite încât sã permitã alegerea unei funcții consistente cu un set de mostre etichetate sã se poatã vorbi de probabilitatea ca funcția aleasã sã fie aproximativ corectã (probabilitatea de eroare sã fie foarte micã), de unde denumirea de „învãțare probabilã aproximativ corectã” (PAC Learning ).

5.4.5 Aplicații în lumea realã ale învãțãrii automatelor

Conceptele legate de invãțarea automatelor nu ar prezenta la fel de mult interes dacã ar fi irelevante pentru problemele lumii reale. Tehnici ale învãțãrii automatelor au fost aplicate cu succes în diferite aspecte ale activitãții umane. Câteva dintre aceste aplicații sunt:

Prevederea supraîncãrcãrilor electrice, folosind un sistem de reguli bazat pe metoda „K-nearest neighbour” (1987);

Clasificarea stelelor și a galaxiilor (1993);

Sistemul Sharp de recunoaștere a caracterelor chinezești (poate procesa 200 de caractere pe secundã și are o acuratețe mai mare de 99%); recunoaște mai mult de 300 de caractere;

Rețeaua neuronalã Fujitsu pentru monitorizarea producției de oțet (opeareazã încã din 1990).

În concluzie, este relativ ușor in zilele noastre sã gãsim exemple de aplicații ale tehnicilor de învãțare a automatelor. Acest lucru nu ar trebui sã ne surprindã, ținând cont de faptul cã multe dintre aceste tehnici pot fi vãzute ca extensii ale unor binecunoscute metode statistice care sunt aplicate cu succes de mulți ani.

Concluzii:

Data mining oferã promisiunea unui ajutor important pentru descoperirea tiparelor ascunse în date, care pot fi folosite pentru a prezice comportamentul clienților, produselor și proceselor. În orice caz, uneltele de data mining trebuie ghidate de utilizatorii care înțeleg afacerile, datele și natura generala a metodelor analitice implicate. Cerințele rezonabile își gãsesc rezolvare prin aplicațiile data mining de la cresterea veniturilor și pânã la reducerea costurilor.

Construirea modelelor este doar un pas în descoperirea cunoștințelor. Este vital sã se colecteze și pregãteascã datele în mod corect, și sã se confrunte modelele cu realitatea. Cel mai bun model este adesea gãsit dupã construirea mai multor modele de diferite tipuri, sau prin aplicarea de diferite tehnologii sau algoritmi.

Alegerea celui mai potrivit produs data mining înseamnã a gãsi o unealtã cu capabilitãțile necesare, o interfațã care se potrivește cu priceperea utilizatorilor și care poate fi aplicatã într-o problemã specificã afacerii.

Bibliografie

1. „Introduction to Data Mining and Knowledge Discovery”

– Two Crows Corporation, Third Edition

– www.andypryke.com/university/The datamine.html

2. „Data mining” (note de curs)

– Prof. J. D. Ullman – Stanford University

– www.thearling.com/dmintro/dmintro.html

3. „Regression and Clasification with Neuronal Networks”

– Andrew W. Moore, School of Computer Science, Carnagie, Mellon University, 2001

– www.cs.helsinky.fi/research/pmdm/data mining

4. „Decision Trees”

– Andrew W. Moore, School of Computer Science, Carnagie, Mellon University, 2001

– www.sian.org/meetings/sdm01/

5. „PAC Learning”

– Andrew W. Moore, School of Computer Science, Carnagie, Mellon University, 2001

– www.cs.waikato.ac.nz/~ml/weka

6. „Probably Approximately Corerct Learning”

– Prof. Hassler, 1990, Cambridge

– www.request.com

7. „Introduction to Machine Learning”

– Nils j. Nilsson, Robotics Laboratory, Department of Computer Science, Stanford University, 2001

– www.cs.sfu.ca/sections/publication/kbd/kbd.html