Universitatea babeş-bolyai cluj-napoca

UNIVERSITATEA BABEŞ-BOLYAI CLUJ-NAPOCA

FACULTATEA DE MATEMATICǍ ŞI INFORMATICǍ
SPECIALIZAREA INFORMATICĂ ROMÂNĂ

LUCRARE DE DIPLOMǍ
Modele de învățare nesupervizată


Conducător ştiinţific

Prof. univ. dr. Czibula Gabriela
Absolvent

Codrean Florina

2012

Cuprins

Introducere 4

1. Învățarea automată 6

1.1. Problematica învățării automate 6

1.2. Învățarea supervizată 7

1.2.1. Rețele neuronale 8

1.2.2. Arbori de decizie 9

1.2.3. Învãțarea Bayesianã 9

1.3. Învãțarea prin întãrire 9

1.4. Învãțarea nesupervizatã 11

1.4.1. Clustering 12

1.4.2. Rețele cu auto-organizare (SOM) 13

1.4.3. Învățarea Hebbiană 14

2. Clustering 15

2.1. Descriere 15

2.2. Formalizarea problemei 16

2.3 Clasificarea tehnicilor de clustering 18

2.4. Măsuri de similaritate 20

2.5. Metoda K-means 22

2.6. Metoda Fuzzy C-means 25

2.7. Mãsuri de calitate 26

3. Aplicații ale Analizei Cluster 30

3.1. Domenii de aplicații 30

3.1.1. Electroenergetică 30

3.1.2. Segmentarea pieței 30

3.1.3. Probleme de recunoaștere de imagini 30

3.1.4. Medicină 31

3.1.5. Web mining 31

3.2. Îmbunătățiri aduse tehnicilor de clustering. Hibridizare. 31

3.2.1. Clustering și agenți inteligenți în web mining 31

3.2.2. Clustering folosit în sisteme predictive 32

3.2.3. Clustering în cadrul GIS (Geographical Information System) 32

4. Prezentarea aplicației 34

4.1. Motivație 34

Concluzii 35

Bibliografie 36

Introducere

1. Învățarea automată

1.1. Problematica învățării automate

Învăţarea automată, unul din sub-domeniile de bază ale Inteligenţei Artificiale, se preocupă cu dezvoltarea de algoritmi şi metode ce permit unui sistem informatic să înveţe date, reguli, chiar algoritmi. Învăţarea automată presupune în primul rând identificarea şi implementarea unei modalităţi cât mai eficiente de a reprezenta informaţii, în sensul facilitării căutării, reorganizării şi modificării lor. Alegerea modului de a reprezenta aceste date ţine atât de concepţia generală asupra modului de rezolvare a problemei, cât şi de caracteristicile datelor cu care se lucrează. [1]

Învăţarea nu se poate face pe baza unui set foarte mare de cunoştinţe, atât din cauza costurilor mari, presupuse de acumularea unor baze de informaţii mari cât şi din cauza complexităţii memorării şi prelucrării unui volum mare de informaţii. În acelaşi timp însă, învăţarea trebuie să ducă la formularea de suficiente „reguli” atât cât să permită rezolvarea unor probleme dintr-un spaţiu mai larg decât cel pe baza căruia s-a făcut învăţarea. Adică învăţarea trebuie să îmbunătăţească performanţa unui sistem nu doar în rezolvarea repetată a unui acelaşi set de probleme, ci şi în rezolvarea unor probleme noi. Acest lucru presupune o generalizare a unei metode de rezolvare pentru a acoperi un număr cât mai mare de instanţe posibile, dar şi păstrarea unei specializări suficiente pentru a fi identificate corect instanţele acceptate. Aceasta se poate face fie inductiv, generalizând o problemă plecând de la un set de exemple, fie deductiv, plecând de la o bază de cunoştinţe suficiente asupra universului problemei şi extrăgând date şi reguli esenţiale. Pentru a putea face acest lucru, un algoritm de învăţare trebuie să fie capabil să selecteze acele elemente semnificative pentru rezolvarea unei instanţe viitoare a problemei. Aceasta alegere se face pe baza unor criterii de selecţie numite diagonale inductive. [2][3]

O altă componentă esenţială al unui algoritm de învăţare este metoda de verificare, o metodă capabilă să confirme dacă generalizările făcute sau regulile deduse se apropie mai mult de soluţia ideală decât starea anterioară a sistemului. Studiul învăţării automate a dus la descrierea a numeroase metode, variind după scop, date de antrenament, strategia de învăţare şi modalitatea de reprezentare a datelor.

În cadrul învățării automate se pot distinge trei mari direcții de cercetare și de tipuri de învățare. Prima dintre ele este reprezentată de învățarea supervizată, care presupune construirea unui model al datelor inițiale în care o parte dintre ele sunt explicative, etichetate, iar una sau mai multe sunt neetichetate, considerate date de test. Cel de-al doilea tip de învățare automată este învățarea prin întărire, care presupune oferirea unei recompense sau a unei pedepse simulate, în funcție de anumite tipuri de comportamente ale sistemului, cu ajutorul cărora sistemul învață un comportament așteptat. Ultima categorie, cea a învățării nesupervizate, se aplică cel mai bine pe anumite probleme din viația reală, deoarece nu necesită nicio etapă de antrenare, aplicându-se direct pe datele neetichetate. În continuare vor fi prezentate cele trei tipuri de învățare. [4]