Universitatea babeş-bolyai cluj-napoca

2.3.Programare genetică

Programarea genetică este o metodă bazată pe algoritmi evolutivi, inspirată din evoluția biologică, prin care se caută expresii sau algoritmi care ar rezolva cât mai bine o anumită problemă. Structurile care sunt supuse adaptării și evoluției în paradigma programării genetice sunt programe structurate ierarhic, ale căror mărime, formă și complexitate se pot schimba de-a lungul procesului [9].

Programarea genetică este o tehnică de învățare automată folosită pentru a optimiză o populație de programe în concordanță cu o funcție de fitness determinată de abilitatea programului de a realiza sarcina cerută.

Programele manipulate de algoritmii de programare genetică sunt reprezentate prin arbori de expresii. Fiecare apel de funcție este reprezentat printr-un nod intern în arbore, iar argumentele funcției sunt date de nodurile fii ale nodului respectiv. Pentru a aplica programarea genetică la un domeniu particular, trebuie definit un set de funcții primitive sau operatori cu care se va lucra (de ex: sin, cos, +, -, or, and, xor), precum și un set de noduri terminale, reprezentate prin variabile (datele de intrare în program) sau constante.

Algoritmii bazați pe programare genetică au următoarea formă [10]:

1. 
   Creează în mod aleator o populație inițială de programe individuale alcătuite din funcțiile disponibile și din terminale.
   
2. 
   În mod iterativ execută următorii pași (o generație) asupra populației, până când criteriul de oprire este satisfăcut:
   

1. 
   Execută fiecare program din populație și calculează fitness-ul acestuia folosind funcția de fitness definită.
   
2. 
   Alege unul sau două programe din populație cu o probabilitate bazată pe fitness pentru a participa la operațiile genetice de la punctul c).
   
3. 
   Creează un nou program pentru a fi inclus în populație aplicând următoarele operații cu probabilitățile specificate:
   

1. 
   Reproducere: Copiază programul selectat în noua populație.
   
2. 
   Crossover: Creează un nou program pentru noua populație, recombinând bucăți aleatoare din două programe selectate.
   
3. 
   Mutație: Creează un nou program pentru noua populație, modificând o parte aleatoare a unui program selectat.
   

3. 
   După ce criteriul de oprire a fost satisfăcut, programul cu cel mai bun rezultat pentru funcția de fitness este ales și este întors de către algoritm.
   

2.4.Mașini cu suport vectorial

Mașinile cu suport vectorial (Support vector machines, SVM) sunt bazate pe teoria învățării statistice. Ideea de bază este de a mapa datele originale într-un spațiu inițial printr-o funcție neliniară și de a construi un hiperplan optim într-un spațiu nou cu mai multe dimensiuni [11]. Acești algoritmi pot fi utilizați atât pentru clasificare, cât și pentru regresie. În cazul clasificării, se caută un hiperplan optim care ar separa datele în 2 clase diferite. Iar în cazul regresiei, se contruiește un hiperplan care se află aproape de cât mai multe puncte, fiind reprezentați sub formă de vectori, care reprezintă datele problemei. În cazul problemelor de regresie, algoritmul este numit Support Vector Regression (SVR).

Mașinile cu suport vectorial sunt o metodă de învățare supervizată state-of-the-art. Algoritmii SVM sunt folosiți pe larg în bioinformatică datorită acurateții înalte și a capacității de a se descurca cu date multi-dimensionale, cum ar fi descrierea genelor, și flexibilitatea modelării diverselor surse de date [12].

Tehnicile SVM aparțin categoriei de metode kernel. O metodă kernel este un algoritm care depinde de date numai prin produse scalare. Când acesta e cazul, produsul scalar poate fi înlocuit cu o funcție kernel care calculeaza produsul scalar într-un posibil spatiu de caracteristici multi-dimensional. Acest lucru are două avantaje: în primul rând, abilitatea de a genera limite de decizie non-liniare folosind metode pentru clasificatori liniari. În al doilea rand, folosirea funcțiilor kernel permite utilizatorului să aplice clasificatorul pe seturi de date care nu au o reprezentare într-un spațiu vectorial de o dimensiune fixată. Un exemplu de astfel de date este prezent în bioinformatică, și anume secvențele de ADN și de proteine [12].

Sunt numeroase aplicații practice ale tehnicilor SVM. Cele mai cunoscute situații reale în care s-a folosit SVM sunt: recunoașterea cifrelor scrise de mână, clasificarea textului și a hiper-textului, identificarea sexului din imagini și algoritmi de ordonare a paginilor după relevanță [13].

Capitolul 3. Sisteme predictive inteligente

Studiul care se ocupă cu sistemele predictive este analiza predictivă. În acest capitol se va prezenta aspecte generale legate de analiza predictivă și modalități prin care se pot aplica tehnici de învățare automată pentru a construi sisteme predictive. Analiza predictivă poate fi folosită pentru a construi modele de clasificare și modele de regresie, dar în această lucrare se pune accentul pe modelele de regresie. Se va discuta și despre unul din tipurile de modele predictive, și anume cele bazate pe serii de timp. Ultimul subcapitol va conține câteva masuri de performanță utilizate pentru modelele predictive de regresie.

3.1.Analiza predictivă

Analiza predictivă este un domeniu al analizei statistice care se ocupă cu extragerea informațiilor din date și folosirea acestora pentru a prezice comportamentul unor fenomene din viitor. Cuprinde tehnici statistice din învățare automată, data mining, teoria jocurilor, care analizează evenimente curente și din trecut pentru a face predicții despre evenimente din viitor. Dacă modelul dorit trebuie să genereze date de ieșire care fac parte dintr-o mulțime discretă, atunci acesta e numit model de clasificare. Daca multimea datelor de ieșire este continuă, atunci modelul este de regresie. Domeniile de aplicare ale analizei predictive sunt numeroase: finanțe, marketing, asigurări, transporturi, telecomunicații etc.

Din punct de vedere al afacerilor, analiza predictivă este vazută ca un set de tehnici de business intelligence (BI) prin care se caută descoperirea unor relații și șabloane în volume mari de date care pot fi folosite pentru a prezice comportamente și evenimente. Spre deosebire de alte tehnici de BI, analiza predictivă este anticipativă, folosind evenimente din trecut pentru a anticipa viitorul [14].

Analiza predictivă este considerată mai mult decât doar statistică. Regresia liniară și logistică – tehnici clasice din statistică – încă sunt folosite pe larg în modelele predictive de azi și aproape toți modelatorii analitici folosesc statistica descriptivă (medie, mod, mediana, deviația standard, histograme) pentru a înțelege natura datelor care trebuie analizate [14].

Însă descoperirile din informatică și tehnologie au facut posibil să se folosească o clasă mai largă de tehnici predictive, cum ar fi: arbori de decizie, rețele neuronale, algoritmi evolutivi, mașini cu suport vectorial și alți algoritmi matematici. Aceste noi tehnici se folosesc de puterea de lucru tot mai mare a calculatoarelor pentru a face calcule complexe care de multe ori necesită parcurgeri multiple ale setului de date. Ele sunt modelate, astfel încât să ruleze cu volume mari de date, cu multe variabile. De asenemenea, sunt gândite să gestioneze zgomotul din date cu diverse anomalii care ar face probleme modelelor tradiționale.

Indiferent de metodă, majoritatea proceselor pentru a crea modele predictive includ următorii pași [14]:

1. 
   Definirea proiectului: Definește obiectivul și rezultatele așteptate pentru un anumit proiect, acestea fiind traduse în obiective și sarcini din analiza predictivă.
   
2. 
   Explorare: Analizează sursa de date și determină cel mai potrivit set de date și cea mai bună abordare pentru a construi modelul.
   
3. 
   Pregătirea datelor: Selectează, extrage și transformă datele care vor fi folosite pentru crearea modelului.
   
4. 
   Construirea modelului: Creează, testează și validează modelul. Evaluează cât de bine acesta satisface cerințele proiectului.
   
5. 
   Exploatare: Aplică rezultatele modelului în deciziile și procesele de business care sunt studiate.
   
6. 
   Gestiunea modelului: Gestionează și întreține modelele construite pentru a îmbunătăți performanța, a promova reutilizabilitatea și a minimiza activitățile redundante.
   

Unul din tipurile de modele de regresie care sunt obținute în urma analizei predictive sunt modelele bazate pe serii de timp.