tdm1final

Universitatea “Politehnica” din Bucuresti

Facultatea de Electronica, Telecomunicatii şi Tehnologia Informatiei

PROIECT DATA MINING

Profesor coordonator Studenti

Prof. Dr. Ing. Victor Neagoe Stan Mihaela Andreea

Stancu Gabriela

2011

Proiect DATA MINING 2011

2

Cuprins

Capitol 1 Introducere ......................................................................................................................................................... 4

1.1 Definire tema ........................................................................................................................................................... 4

1.2 Baza de date ............................................................................................................................................................ 4

1.3 Reducerea dimensionalitatii .................................................................................................................................... 7

Capitolul 2 Analiza componentelor principale - PCA ......................................................................................................... 8

2.1 Descriere PCA .......................................................................................................................................................... 8

2.2 Rezultate obtinute ................................................................................................................................................. 13

2.2.1 Vectorul medie ............................................................................................................................................... 13

2.2.2.Matricea de covariatie .................................................................................................................................... 15

2.2.3.Valori si vectori propri ................................................................................................................................... 18

2.2.4.Matricea transformarii KLT ............................................................................................................................. 21

2.2.5.Variatia energiei conservate si a erorii patratice ............................................................................................ 24

2.2.6.Componente retinute ..................................................................................................................................... 25

Capitolul 3 Algoritmi de Grupare (Clustering) ................................................................................................................. 26

3.1 CLUSTERING .......................................................................................................................................................... 26

3.2 ALGORITMUL K-NEAREST NEIGHBOUR (K-NN) ......................................................................................................... 28

3.3 Algoritmul K-means supervizat.............................................................................................................................. 30

3.3.1 Metoda generala K-Means. ............................................................................................................................ 30

3.3.2 Metoda originala K-Means ............................................................................................................................. 32


3

ANEXA Tabele si Figuri

Tabel 1. Media vectorilor din clasa 1 din setul de antrenare Tabel 2. Media vectorilor din clasa 2 din setul de antrenare Tabel 3. Media vectorilor din setul de antrenare Tabel 4. Valori matrice de covariatie a vectorilor din prima clasa Tabel 5. Valori matricea de covariatie ale vectorilor din clasa a doua Tabel 6. Valorile propri corespunzatoare vectorilor din clasa 1 Tabel 7. Valorile propri corespunzatoare vectorilor din clasa 2 Tabel 8. Valorile propri corespunzatoare vectorilor din lotul de antrenare Tabel 9. Vectorii proprii corespunzatori valorilor proprii din prima clasa Tabel 10. Vectorii proprii corespunzatori valorilor proprii din clasa a doua Tabel 9. Matricea KLT1 corespunzatoare vectorilor din prima clasa Tabel 10. Matricea KLT2 corespunzatoare vectorilor din clasa a doua

Figura 1. Matricea de covarianta a vectorilor din prima clasa Figura 3. Matricea de covarianta a vectorilor din clasa a doua Figura 4. Matricea de covarianta a vectorilor din lotul de antrenare Figura 5. Valori propri corespunzatoare vectorilor din clasa 1 Figura 6. Valori propri corespunzatoare vectorilor din clasa 2 Figura 7. Valori propri corespunzatoare vectorilor din lotul de antrenare


4

Capitol 1 Introducere

1.1 Definire tema

Se imparte baza de date in lot de antrenare si lot de test. Pentru fiecare clasa de vectori se considera 2/3 in lotul de antrenare si 1/3 in lotul de test.

Pe setul de antrenare:

1) Sa se deduca vectorul medie (media inregistrarilor) 2) Sa se deduca matricea de covariatie 3) Sa se calculeze valorile proprii si sa se ordoneze descrescator 4) Sa se deduca matricea transformarii KLT pentru PCA (cu ajutorul vectorilor proprii) 5) Sa se testeze ortogonalitatea matricii KLT 6) Sa se reprezinte graficul valorilor proprii ordonate 7) Sa se studieze variatia energiei conservate si a erorii patratice retinand un numar variabil de componente ( de la 1 la dimensiunea vectorilor) 8) Sa se stabileasca numarul de componente retinute in variantele: a. Criteriul valorii proprii (se retin numai componentele ale caror valori proprii depasesc 1% din valoarea proprie maxima) b. Varianta (energia totala >α%). Se considera α = 50; 75; 90; 95; 99. c. Se considera cazul cand se retin numai 2 componente din spatial transformat. Sa se calculeze energia prezervata . 9) Sa se clasifice datele din lotul de test in spatiul initial n-dimensional si in spatiul transformat conform punctelor 8b si 8c. folosind algoritmiil:

a) NN ; b) K-means (supervizat) c) Bayes pentru repartitii normale

Pentru fiecare caz sa se evaluze scorul de clasificare corecta.

1.2 Baza de date

Baza de date asupra careia am efectuat mai multe teste de DATA MINIG este: Forest Fires. Modelul bazei de date:

X,Y,month,day,FFMC,DMC,DC,ISI,temp,RH,wind,rain,area


5

7,5,mar,fri,86.2,26.2,94.3,5.1,8.2,51,6.7,0,0 7,4,oct,tue,90.6,35.4,669.1,6.7,18,33,0.9,0,0 7,4,oct,sat,90.6,43.7,686.9,6.7,14.6,33,1.3,0,0 8,6,mar,fri,91.7,33.3,77.5,9,8.3,97,4,0.2,0 8,6,mar,sun,89.3,51.3,102.2,9.6,11.4,99,1.8,0,0 8,6,aug,sun,92.3,85.3,488,14.7,22.2,29,5.4,0,0 8,6,aug,mon,92.3,88.9,495.6,8.5,24.1,27,3.1,0,0 8,6,aug,mon,91.5,145.4,608.2,10.7,8,86,2.2,0,0 8,6,sep,tue,91,129.5,692.6,7,13.1,63,5.4,0,0 7,5,sep,sat,92.5,88,698.6,7.1,22.8,40,4,0,0 7,5,sep,sat,92.5,88,698.6,7.1,17.8,51,7.2,0,0 7,5,sep,sat,92.8,73.2,713,22.6,19.3,38,4,0,0 6,5,aug,fri,63.5,70.8,665.3,0.8,17,72,6.7,0,0 6,5,sep,mon,90.9,126.5,686.5,7,21.3,42,2.2,0,0 6,5,sep,wed,92.9,133.3,699.6,9.2,26.4,21,4.5,0,0 6,5,sep,fri,93.3,141.2,713.9,13.9,22.9,44,5.4,0,0 5,5,mar,sat,91.7,35.8,80.8,7.8,15.1,27,5.4,0,0 8,5,oct,mon,84.9,32.8,664.2,3,16.7,47,4.9,0,0 6,4,mar,wed,89.2,27.9,70.8,6.3,15.9,35,4,0,0 6,4,apr,sat,86.3,27.4,97.1,5.1,9.3,44,4.5,0,0 6,4,sep,tue,91,129.5,692.6,7,18.3,40,2.7,0,0 5,4,sep,mon,91.8,78.5,724.3,9.2,19.1,38,2.7,0,0 7,4,jun,sun,94.3,96.3,200,56.1,21,44,4.5,0,0 …………………………………………….. Unde: 1. X - x-axis spatial coordinate within the Montesinho park map: 1 to 9 2. Y - y-axis spatial coordinate within the Montesinho park map: 2 to 9 3. month - month of the year: "jan" to "dec" 4. day - day of the week: "mon" to "sun" 5. FFMC - FFMC index from the FWI system: 18.7 to 96.20 6. DMC - DMC index from the FWI system: 1.1 to 291.3 7. DC - DC index from the FWI system: 7.9 to 860.6 8. ISI - ISI index from the FWI system: 0.0 to 56.10 9. temp - temperature in Celsius degrees: 2.2 to 33.30 10. RH - relative humidity in %: 15.0 to 100 11. wind - wind speed in km/h: 0.40 to 9.40 12. rain - outside rain in mm/m2 : 0.0 to 6.4 13. area - the burned area of the forest (in ha): 0.00 to 1090.84 (this output variable is very skewed towards 0.0, thus it may make sense to model with the logarithm transform). Initial am citit datele din baza de date, le-am pus intr-un fisier.. Am codat numele zilelor saptamanii

si numele lunilor anului in felul urmator: Ianuarie-1 Februarie -2 ......


6

Decembrie-12 Luni-1 Marti-2 ...... Duminica-7 Etapa urmatoare am impartit vectorii in 2 clase. Cele 2 clase le-am ales in functie de componenta

numarul 13 si anume aria de padure arsa. Astfel daca aceasta componenta este 0 am considerat ca nu avem incendiu si am pus acesti vectori intr-un nou vector in care o sa am toti vectorii care apartin clasei 1. Toti ceilalti vectori in care aria arsa e diferita de 0 => o sa am incendiu, acesti vectori vor constitui cea de-a doua clasa. Dupa aceasta impartire a vectorilor in clase am reimpartit vectorii din fiecare clasa in vectori pentru lot de antrenare -2/3 din numarul total de vectori ai clasei respective si 1/3 din numarul total in lotul de test. Mai jos am pus codul Matlab pe care l-am utilizat pentru a realiza ce am explicat mai sus: v=zeros(nrlinii,1);

k=0;l=0;

for i=1:nrlinii if V(i,13)==0 k=k+1; B(k,:)=V(i,:); v(i)=1; else l=l+1; C(l,:)=V(i,:); v(i)=2; end end length1=165; for i=1:length1 for j=1:nrcoloane lot_antrenare_cls1(i,j)=B(i,j); end end for i=length1+1:247 for j=1:nrcoloane lot_test_cls1(i-165,j)=B(i,j); end end length2=180; for i=1:length2 for j=1:nrcoloane lot_antrenare_cls2(i,j)=C(i,j); end end for i=length2+1:270 for j=1:nrcoloane lot_test_cls2(i-180,j)=C(i,j); end end


7

1.3 Reducerea dimensionalitatii

Atunci cand vorbim de reducerea dimensionalitatii datelor ne referim la un proces de

recunoastere a formelor. Acesta presupune doua etape: selectia si clasificarea caracteristicilor.

Selectia caracteristicilor este o problema cheie în Data Mining, afectand puternic

performantele clasificarii . Selectia caracteristicilor este considerata ca un proces de transformare liniara sau neliniara a spatiului initial al observatiilor într-un spatiu cu dimensionalitate redusa. Aceasta transformare este necesara deoarece unii algoritmi care sunt eficienti într-un spatiu cu un numar redus de dimensiuni pot deveni nepractici intr-un spatiu cu mai multe dimensiuni. Pentru o singura clasa, criteriul de selectie reflecta eficienta transformarii în reducerea

dimensiunii concomitent cu conservarea informatiei originale.In cazul mai multor clase, selectia caracteristicilor este functie de eficienta lor privind separabilitatea claselor. Aceasta separabilitate depinde atat de repartitia claselor cat si de clasificatorul utilizat.


8

Capitolul 2 Analiza componentelor principale - PCA

2.1 Descriere PCA

Analiza componentelor principale (Principal Component Analysis – PCA) cunoscuta si sub numele de Transformata Karhunen-Loève este o metodă clasica , caracterizata prin aceea ca realizeaza o decorelare a datelor. Este o metoda eficienta de selectie a caracteristicilor si în

decursul timpului a devenit o metoda de referinta . Se considera cazul selectiei caracteristicilor pentru o singură clasa. Selectia caracteristicilor unor repartitii individuale ajuta la separarea acestor repartitii.

Fie X un vector aleator n-dimensional. Se caută o transformare ortogonală care să

permită reprezentarea optimă a vectorului X în raport cu criteriul erorii medii pătratice

minime. Fie K transformarea căutată:

T

nK ),,,( 21 ΦΦΦ= K

(1.1)

unde sunt vectori n-dimensionali, deocamdata nedeterminati.

Se presupune în plus că vectorii coloană ai lui K formează un sistem ortonormat, adică:

≠

==Φ⋅Φ

ji

jiT

j

T

i ,0

,1. (1.2)

Fiecare vector X se transforma in:

( )TnyyyKXY K,, 21== , (1.3)

unde .XyT

ii ⋅Φ=

Ecuatiile (1.1) si (1.2) conduc la n

TTIKKKK =⋅=⋅ , unde nI este matricea unitate n x n;

rezulta:

∑=

Φ⋅=⋅=n

i

ii

TyYKX

1 (1.4)


9

Se vor reŃine numai m < n componente ale lui Y , restul de n - m componente fiind înlocuite

cu constantele preselectate ib , astfel că se estimează X ca:

Eroarea corespunzatoare acestei estimari este:

Vom considera criteriul erorii patratice medii:

care, Ńinând cont de relaŃia (1.2), devine ( ){ }22 )( ii byEm −=ε . FuncŃia eroare )(2 mε se

minimizează alegând în mod adecvat iΦ şi ib .

Acest proces se realizează în două etape:

A) Se minimizeaza )(2 mε in raport cu ib punand conditia necesara

de unde, conform relatiei (1.3), deducem

Atunci eroarea patratica medie devine:

unde xΣ este matricea de covariatie a vectorului X , adica:


10

B) Pentru a determina iΦ optimali, se minimizeaza )(2 mε in raport cu iΦ , adaugand

restrictiile ni1pentru 1 ≤≤=Φ⋅Φ iiT

. Se utilizeaza metoda multiplicatorilor Lagrange,

care cere minimizarea expresiei:

(1.5)

in raport cu iΦ , unde iβ sunt multiplicatorii Lagrange.

Se tine seama ca si Atunci din conditia

rezulta

(1.6)

Ecuatia (1.6) arata ca iΦ este un vector propriu al matricei de covariatie xΣ , iar iβ este

valoarea proprie corespunzatoare, pe care o notam cu iλ unde .1 ni ≤≤

Introducand relatia (1.6) in relatia (1.5), rezulta

(1.7)

Formula (1.4) se mai numeşte dezvoltarea Karhunen- Loève, iar transformarea definită

de relaŃia (1.3) se numeşte transformarea Karhunen-Loève. Problema minimizării lui )(2 mε

se numeşte în statistică analiză factorială (sau analiza componentelor principale).

ObservaŃii:

a)

ImportanŃa fiecărei caracteristici este determinată de valoarea proprie corespunzătoare. Dacă

o caracteristică, de exemplu iy , este eliminată, atunci eroarea pătratică medie creşte cu

iλ .

Aşadar caracteristicile cu cele mai mici valori proprii trebuie eliminate primele. Dacă valorile

proprii (care sunt reale şi pozitive deoarece matricea xΣ este simetrică) sunt indexate astfel:

,021 >>>> nλλλ K atunci prioritatea reŃinerii caracteristicilor iy este în ordinea naturală a

indicilor;


11

b)

Dacă XKY ⋅= , atunci între matricile de covariaŃie ale lui X şi Y există relaŃia

T

XY KK ⋅Σ⋅=Σ . Pentru transformarea Karhunen-Loève deducem că Y are componentele

necorelate, adică YΣ este o matrice diagonală şi anume:

c)

Vectorii proprii ai lui xΣ minimizează )(2 mε pentru orice alegere a unor baze ortonormate de

vectori.

Algoritmul de selectie a caracteristicilor este urmatorul:

(1) Se determină matricea de covariaŃie unde sunt

imaginile de intrare aranjate sub forma unor vectori n_dimensionali

media vectorilor de intrare;

(2) Se determină valorile proprii ale matricii xΣ (soluŃiile ecuaŃiei de mai

jos) şi se ordonează descrescător, se reŃin cele mai mari m valori dintre ele.

este matricea unitate n-dimensionala si λ este necunoscuta.

(3) Fie ecuaŃiile

cu vectorii proprii ai matricii xΣ corespunzand valorilor proprii in

ordine descrescatoare si matricea ortogonala corespunzatoare. In urma

reducerii la m elemente, se obtine matricea Prin transformarea Karhunen-

Loève se obŃin vectorii care sunt m-dimensionali, m < n dimensiunea iniŃială.


12

Factorul de prezervare a energiei semnalului in m componente se poate bine aproxima

cu formula

(1.8)

undeiλ sunt valorile proprii ordonate descrescator, iar η este factorul de conservare a

energiei.

Complementul lui , notat cu ηε −= 100 este eroarea patratica medie de selectie (costul

reducerii dimensiunii).

Analiza Componentelor Principale (PCA) este o metodă statistică simplă pentru

reducerea dimensionalităŃii (compresie) care a devenit probabil cea mai frecvent utilizată .

Vectorii proprii ar putea fi priviŃi ca fiind un set de caracteristici generale ale variaŃiilor

vectorilor din baza de date. Odată ce datele sunt normalizate (aduse la o dimensiune

standard), ele pot fi tratate ca vectori unidimensionali de valori de pixeli.

Pentru imagini, această metodă este sensibilă la variaŃii ca scalare, iluminare, rotaŃie

sau translaŃie şi necesită o reînvăŃare completă a datelor de antrenare pentru a adăuga noi

subiecŃi în baza de date.

Schema algoritmului PCA pentru lotul de antrenare:


13

Figura 1. Calculul transformatei Karhunen-Loève pentru lotul de antrenare

2.2 Rezultate obtinute

2.2.1 Vectorul medie

Pentru determinarea vectorului medie al vectorilor de intrarea m implementat urmatoarea formula:

Unde vectorii Xi sunt vectorii din lotul de antrenare ai clasei 1 si sunt aranjati sub forma unor vectori n-dimensionali i = 1,..,L, L = numarul de componente din fiecare vector . Pentru determnarea mediei calculam suma tuturor vectorilor apoi impartim la numarul total de vectori care i-am adaugat in suma mea.


14

In tabelul urmator am pus valorile obtinute cu implementarea mea atat pe clase cat si pe tot lotul de antrenare

Media data de implementarea mea Media calculata cu functia „mean” 4.43 4.43

4.18 4.18

6.92 6.92

4.42 4.42

90.01 90.01

86.57 86.57

481.67 481.67

8.69 8.69

17.80 17.80

43.67 43.67

3.94 3.94

0.01 0.01

Tabel 1. Media vectorilor din clasa 1 din setul de antrenare


4.36 4.36

7.93 7.93

4.06 4.06

90.99 90.99

99.63 99.63

569.79 569.79

9.03 9.03

18.35 18.35

42.01 42.01

3.99 3.99

22.38 22.38

Tabel 2. Media vectorilor din clasa 2 din setul de antrenare


4.2725 4.2725

7.4464 7.4464

4.2319 4.2319

90.5217 90.5217

93.3838 93.3838

527.6423 527.6423

8.8684 8.8684

18.0907 18.0907

42.8058 42.8058


15

3.9678 3.9678

0.0041 0.0041

Tabel 3. Media vectorilor din setul de antrenare

Observatie: Am obtinut aceleasi valori atat cu implementarea mea cat si cu functia mean implementata de Matlab exact cum ne asteptam.

2.2.2.Matricea de covariatie %Matricea de covariatie matcov=zeros(nr-1,nr-1); %Inializare matricea de covariatie cu 0 for j=1:dim matcov=matcov +((1/dim)*(V(1:nr-1,j)-mediaV)*(V(1:nr-1,j)-mediaV)'); end disp('Matricea de covariatie este:') disp(matcov) %------------------------------------------------------------------

4.66 1.62 -0.13 0.05 -0.67 -7.60 -36.27 1.01 -0.24 5.70 0.24 0.02

1.62 1.77 -0.75 -0.04 -0.85 -8.83 -88.25 0.00 -1.01 4.56 0.06 0.00

-0.13 -0.75 6.57 -0.13 4.89 73.44 648.69 3.51 6.84 -3.10 -0.54 0.00

0.05 -0.04 -0.13 4.61 -0.12 1.70 -15.52 1.63 0.57 0.62 0.14 0.01

-0.67 -0.85 4.89 -0.12 25.77 97.81 520.95 13.54 9.18 -24.75 -0.11 0.01

-7.60 -8.83 73.44 1.70 97.81 2069.05 8253.31 98.59 116.17 20.21 -1.42 0.59

-6.27 -88.25 648.69 -15.52 520.95 8253.31 68718.49 336.30 699.93 -230.5 -2.32 0.78

1.01 0.00 3.51 1.63 13.54 98.59 336.30 29.22 7.49 -7.00 1.03 0.04

-0.24 -1.01 6.84 0.57 9.18 116.17 699.93 7.49 23.29 -48.50 -1.11 0.01

5.70 4.56 -3.10 0.62 -24.75 20.21 -230.59 -7.00 -48.50 290.07 0.95 0.30

0.24 0.06 -0.54 0.14 -0.11 -1.42 -62.32 1.03 -1.11 0.95 2.83 0.03

0.02 0.00 0.00 0.01 0.01 0.59 0.78 0.04 0.01 0.30 0.03 0.01

Tabel 4. Valori matrice de covariatie a vectorilor din prima clasa


16

Figura 2. Matricea de covariatie a vectorilor din prima clasa

5.43 1.27 -0.79 0.42 -0.70 -18.83 -88.77 -0.07 -1.35 2.55 0.16 6.44

1.27 1.34 -0.00 0.12 -0.49 -5.57 -34.19 -0.56 -0.25 0.10 -0.12 1.41

-0.79 -0.00 4.81 -0.79 0.58 30.51 365.02 0.47 1.66 -3.64 0.10 11.26

0.42 0.12 -0.79 4.15 1.18 3.95 -33.98 1.10 1.01 3.09 -0.13 14.61

-0.70 -0.49 0.58 1.18 12.06 83.81 295.25 9.00 10.02 -7.45 -1.33 10.06

-8.83 -5.57 30.51 3.95 83.81 1743.76 6396.28 84.45 151.33 -33.73 -21.64 268.78

-88.7 -34.1 365.02 -33.9 295.25 6396.28 48521.52 253.47 659.19 -265.8 -123.6 986.00

-0.07 -0.56 0.47 1.10 9.00 84.45 253.47 15.06 9.19 -0.40 0.38 -11.11

-1.35 -0.25 1.66 1.01 10.02 151.33 659.19 9.19 32.11 -35.64 -4.00 48.62

2.55 0.10 -3.64 3.09 -7.45 -33.73 -265.89 -0.40 -35.64 192.59 -0.22 -135.36

0.16 -0.12 0.10 -0.13 -1.33 -21.64 -123.60 0.38 -4.00 -0.22 3.63 -1.67

6.44 1.41 11.26 14.61 10.06 238.78 986.00 -11.11 48.62 -135.3 -1.67 7445.06

Tabel 5. Valori matricea de covariatie ale vectorilor din clasa a doua

Pentru afisarea matricei de covariatie am folosit urmatoarea linie de cod: figure, image(abs(matcov2))


17

Figura 3. Matricea de covariatie a vectorilor din clasa a doua

Figura 4. Matricea de covariatie a vectorilor din lotul de antrenare


18

2.2.3.Valori si vectori propri

Am calculat valorile proprii, apoi i-am ordonat descrescator. Cu ajutorul acestora am calculat vectorii proprii corespunzatori fiecarei valori propri si i-am pus intr-o matrice.

%Calculul valorilor proprii si ordonarea descrescatoare a acestora disp('Vectorii proprii si matricea valorilor proprii este: ') [vectori,val_propri]=eig(matcov1) % returneaza vectorii proprii vect_proprii si vectorul de valori proprii %-----------------------------------------------------------------

Am obtinut urmatoarele rezultate pentru valorile proprii corespunzatoare celor 2 clase: - clasa 1

69745.28

1070.17

297.45

30.07

13.27

7.27

4.76

4.13

2.55

0.96

0.40

0.01

Tabel 6. Valorile propri corespunzatoare vectorilor din clasa 1

- clasa 2 49422.04

7425.93

892.22

194.74

17.04

11.51

5.50

4.77

3.59

2.18

1.32

0.69

Tabel 7. Valorile propri corespunzatoare vectorilor din clasa 2


19

- pentru tot lotul de antrenare

61125

3995

978

245

22

11

8

5

4

3

1

1

Tabel 8. Valorile propri corespunzatoare vectorilor din lotul de antrenare

Odata aflate si ordonate decrescator am realizat cate un grafic pentru vizualizarea valorilor propri. Deoarece valorile acestora variaza foarte mult, cea mai mare valoare proprie este 69745.28 si cea mai mica 0.01 am calculat logaritm din aceste valori pentru a avea o reprezentare semnificativa.

Figura 5. Valori propri corespunzatoare vectorilor din clasa 1


20

Figura 6. Valori propri corespunzatoare vectorilor din clasa 2

Figura 7. Valori propri corespunzatoare vectorilor din lotul de antrenare


21

-0.01 0.02 -0.39 0.10 0.49 -0.67 -0.35 -0.06 -0.06 -0.02 0.00 -0.00

0.01 0.03 0.92 0.11 0.18 -0.29 -0.16 -0.02 -0.02 -0.01 -0.00 -0.00

0.01 -1.00 0.02 -0.03 0.01 -0.02 -0.03 -0.02 -0.02 0.00 0.01 0.01

-0.00 -0.01 0.02 0.07 0.76 0.63 -0.09 -0.05 -0.05 -0.00 -0.00 -0.00

-0.00 -0.01 -0.01 -0.03 0.02 0.05 -0.25 -0.57 -0.57 0.09 -0.03 0.01

-0.00 -0.01 -0.00 0.01 0.02 -0.01 0.03 0.07 0.07 0.05 -0.99 0.12

-0.00 0.01 0.00 0.00 0.00 -0.00 0.01 -0.00 -0.00 -0.01 0.12 0.99

0.00 0.02 0.00 0.05 -0.11 -0.02 0.20 -0.81 -0.81 0.04 -0.05 0.00

-0.01 0.03 -0.00 -0.18 -0.32 0.23 -0.84 0.01 0.01 0.17 -0.03 0.01

-0.00 0.00 -0.01 -0.03 -0.07 0.06 -0.15 -0.08 -0.08 -0.98 -0.06 -0.00

-0.01 0.03 0.06 -0.97 0.19 -0.10 0.12 -0.04 -0.04 -0.00 -0.01 -0.00

1.00 0.02 -0.01 -0.01 0.00 0.00 -0.00 -0.00 -0.00 -0.00 -0.00 0.00

Tabel 7. Vectorii proprii corespunzatori valorilor proprii din prima clasa

0.06 -0.18 0.22 -0.13 -0.20 -0.92 0.01 0.10 -0.01 -0.01 -0.00 0.00

0.05 0.60 -0.74 -0.03 -0.08 -0.27 0.05 -0.00 0.00 -0.00 -0.00 0.00

0.23 0.73 0.60 0.06 0.11 -0.04 -0.14 -0.14 0.01 -0.02 -0.00 -0.01

-0.11 0.01 0.02 0.94 -0.28 -0.06 0.03 0.15 -0.02 0.01 -0.00 0.00

0.34 0.03 0.02 -0.21 -0.68 0.24 -0.34 0.45 0.03 0.05 -0.00 -0.01

-0.00 0.00 0.01 0.00 -0.00 -0.02 -0.01 -0.11 -0.01 0.99 -0.02 -0.13

-0.00 -0.01 -0.01 0.00 -0.00 -0.00 -0.00 0.00 -0.01 -0.13 0.03 -0.99

-0.36 0.06 -0.02 0.02 0.46 -0.09 -0.55 0.59 -0.00 0.06 0.00 -0.01

0.23 0.08 0.08 -0.02 0.22 0.05 0.69 0.61 0.18 0.07 -0.00 -0.01

0.06 0.02 0.02 -0.02 0.02 0.03 0.11 0.12 -0.98 0.00 0.02 0.01

0.79 -0.24 -0.18 0.23 0.38 -0.08 -0.27 -0.06 0.00 -0.01 -0.00 0.00

-0.00 -0.00 -0.00 -0.00 -0.00 -0.00 -0.00 0.00 -0.02 -0.02 -1.00 -0.02

Tabel 8. Vectorii proprii corespunzatori valorilor proprii din clasa a doua

2.2.4.Matricea transformarii KLT

Urmatorul pas a fost deducerea matricea transformarii KLT pentru PCA (cu ajutorul vectorilor proprii).

%Matricea transformarii KLT pentru PCA (cu ajutorul vectorilor proprii) disp('Matricea KLT pentru PCA clasa 1 este:') KLT1=matrice_vectori1' %----------------------------------------------------------------


22

Matricea KLT1 pentru PCA corespunzatoare vectorilor din clasa 1este:

-0.01 0.01 0.01 -0.00 -0.00 -0.00 0.00 0.00 -0.01 -0.00 -0.01 1.00

0.02 0.03 -1.00 -0.01 -0.01 -0.01 0.01 0.02 0.03 0.00 0.03 0.02

-0.39 0.92 0.02 0.02 -0.01 -0.00 0.00 0.00 -0.00 -0.01 0.06 -0.01

0.10 0.11 -0.03 0.07 -0.03 0.01 0.00 0.05 -0.18 -0.03 -0.97 -0.01

0.49 0.18 0.01 0.76 0.02 0.02 0.00 -0.11 -0.32 -0.07 0.19 0.00

-0.67 -0.29 -0.02 0.63 0.05 -0.01 -0.00 -0.02 0.23 0.06 -0.10 0.00

-0.35 -0.16 -0.03 -0.09 -0.25 0.03 0.01 0.20 -0.84 -0.15 0.12 -0.00

0.12 0.04 0.03 0.12 -0.78 -0.01 0.00 0.53 0.29 -0.01 0.02 0.00

-0.06 -0.02 -0.02 -0.05 -0.57 0.07 -0.00 -0.81 0.01 -0.08 -0.04 -0.00

-0.02 -0.01 0.00 -0.00 0.09 0.05 -0.01 0.04 0.17 -0.98 -0.00 -0.00

0.00 -0.00 0.01 -0.00 -0.03 -0.99 0.12 -0.05 -0.03 -0.06 -0.01 -0.00

-0.00 -0.00 0.01 -0.00 0.01 0.12 0.99 0.00 0.01 -0.00 -0.00 0.00

Tabel 9. Matricea KLT1 corespunzatoare vectorilor din prima clasa

0.06 0.05 0.23 -0.11 0.34 -0.00 -0.00 -0.36 0.23 0.06 0.79 -0.00

-0.18 0.60 0.73 0.01 0.03 0.00 -0.01 0.06 0.08 0.02 -0.24 -0.00

0.22 -0.74 0.60 0.02 0.02 0.01 -0.01 -0.02 0.08 0.02 -0.18 -0.00

-0.13 -0.03 0.06 0.94 -0.21 0.00 0.00 0.02 -0.02 -0.02 0.23 -0.00

-0.20 -0.08 0.11 -0.28 -0.68 -0.00 -0.00 0.46 0.22 0.02 0.38 0.00

-0.92 -0.27 -0.04 -0.06 0.24 -0.02 -0.00 -0.09 0.05 0.03 -0.08 0.00

0.01 0.05 -0.14 0.03 -0.34 -0.01 -0.00 -0.55 0.69 0.11 -0.27 -0.00

0.10 -0.00 -0.14 0.15 0.45 -0.11 0.00 0.59 0.61 0.12 -0.06 0.00

-0.01 0.00 0.01 -0.02 0.03 -0.01 -0.01 -0.00 0.18 -0.98 0.00 -0.02

-0.01 -0.00 -0.02 0.01 0.05 0.99 -0.13 0.06 0.07 0.00 -0.01 -0.02

-0.00 -0.00 -0.00 -0.00 -0.00 -0.02 0.03 0.00 -0.00 0.02 -0.00 -1.00

0.00 0.00 -0.01 0.00 -0.01 -0.13 -0.99 -0.01 -0.01 0.01 0.00 -0.02

Tabel 10. Matricea KLT2 corespunzatoare vectorilor din clasa a doua

2.2.4.1 Ortogonalitatea matricii KLT

La acest punct am testat ogonalitatea matricii KLT. Pentru aceasta am parcurs urmatoarele etape: - Am calculat produsul intre matricea KLT si transpusa acesteia, matrice pe care am notat-o cu Q; - Am construit o noua matrice in care am retinut valorile rotungite ale matricei Q notata r; - Am generat o matrice identitate de ordinul matricei Q notata g; - Am verificat conditia de ortogonalitate care spune ce o matrice este ortogonala daca produsul ei

este egal cu matricea identitate.


23

- Daca am egalitate se afiseaza mesajul „Matricea KLT e ortogonala”, daca nu afisez „Matricea KLT nu e ortogonala”

%Ortogonalitatea matricei KLT Q=KLT*KLT' %Se calculeaza produsul dintre matricea KLT si transpusa ei r=round(Q); %Se rotunjesc valorile obtinute in urma inmultirii g=eye(nr-1) %Se genereaza matricea identitate de dimensiune egala cu numarul vectorilor de intrare if (isequal(r,g)) disp('Matricea KLT e ortogonala') else disp('Matricea KLT nu e ortogonala') end %----------------------------------------------------------------- r =

1.00 0 0 0 0 0 0 0 0 0 0 0

0 1.00 0 0 0 0 0 0 0 0 0 0

0 0 1.00 0 0 0 0 0 0 0 0 0

0 0 0 1.00 0 0 0 0 0 0 0 0

0 0 0 0 1.00 0 0 0 0 0 0 0

0 0 0 0 0 1.00 0 0 0 0 0 0

0 0 0 0 0 0 1.00 0 0 0 0 0

0 0 0 0 0 0 0 1.00 0 0 0 0

0 0 0 0 0 0 0 0 1.00 0 0 0

0 0 0 0 0 0 0 0 0 1.00 0 0

0 0 0 0 0 0 0 0 0 0 1.00 0

0 0 0 0 0 0 0 0 0 0 0 1.00

g =

1.00 0 0 0 0 0 0 0 0 0 0 0

0 1.00 0 0 0 0 0 0 0 0 0 0

0 0 1.00 0 0 0 0 0 0 0 0 0

0 0 0 1.00 0 0 0 0 0 0 0 0

0 0 0 0 1.00 0 0 0 0 0 0 0

0 0 0 0 0 1.00 0 0 0 0 0 0

0 0 0 0 0 0 1.00 0 0 0 0 0

0 0 0 0 0 0 0 1.00 0 0 0 0

0 0 0 0 0 0 0 0 1.00 0 0 0

0 0 0 0 0 0 0 0 0 1.00 0 0

0 0 0 0 0 0 0 0 0 0 1.00 0

0 0 0 0 0 0 0 0 0 0 0 1.00

Concluzie: r = g => Matricea KLT e ortogonala.


24

2.2.5.Variatia energiei conservate si a erorii patratice

La acest punct am studiat variatia energiei conservate si a erorii patratice retinand un numar variabil de componente ( de la 1 la dimensiunea vectorilor).

1 componenta Variatia energiei conservate eta= 97.9417

Eroarea = 2.0583

2 componente Variatia energiei conservate eta= 99.5156

Eroarea = 0.4844


Eroarea = 0.0899


Eroarea = 0.0538


Eroarea = 0.0357


Eroarea = 0.0223


Eroarea = 0.0138


Eroarea = 0.0073


Eroarea = 0.0031


Eroarea = 0.0013


25

11 componente Variatia energiei conservate eta= 100

Eroarea = 4.5e-06

12 componente Variatia energiei conservate eta= 100

Eroarea = 0

Concluzie: Cu cat numarul de componente creste creste energia iar eroarea scade ajungand la 0 cand luam in considerare toate componentele.

2.2.6.Componente retinute

Sa se stabileasca numarul de componente retinute in variantele:

a. Criteriul valorii proprii (se retin numai componentele ale caror valori proprii depasesc 1% din valoarea proprie maxima) Punand conditia sa se retina numai componentele ale caror valori proprii depasesc 1% din valoarea proprie maxima am obtinut urmatorul rezultat: numarul componentelor retinute = 2 dintr-un numar total de 12.

b. Varianta (energia totala >α%). Se considera α = 50; 75; 90; 95; 99.

Numarul de componente retinute cand energia totala este mai mare de 50% este 1.





c. Se considera cazul cand se retin numai 2 componente din spatial transformat. Sa se calculeze energia prezervata . Energia obtinuta in cazul in care se retin 2 componente este: eta= 99.5156.


26

Capitolul 3 Algoritmi de Grupare (Clustering)

3.1 CLUSTERING

Pentru a clasifica elementele, trebuie in prima faza stabilite atributelor elementelor pe

care va fi bazata clusterizarea si reprezentarea lor. Dupa stabilirea modelului, clusterizarea

este apoi efectuata folosind ca intrare vectorii care reprezinta vectorii si un algoritm de

clusterizare a componentelor.

In cadrul clasificarii bazate pe text se caracterizeaza fiecare document in functie de

continutul sau : cuvintele continute, frazele sau fragmentele. Ideea de la care se pleaca este ca

daca doua documente contin multe cuvinte comune, atunci este foarte probabil ca ele sa fie

documente similare. Abordarile din aceasta categorie pot fi impartite în functie de metoda de

clusterizare folosita in: partitionale, ierarhice, bazate pe grafuri, bazate pe retele neurale si

algoritmi probabilistici.

Clusterizarea partitionala. Clusterizarea de documente partitionala incearca

partitionarea neteda a unei colectii de documente intr-un numar predefinit de clustere

disjuncte. Algoritmii de clusterizare partitionali sunt împartiti in algoritmi cu metode iterative

sau de realocare si în algoritmi cu metode cu un singur pas. Cei mai cunoscuti algoritmi de

clusterizare partitionala sunt k-means, care se bazeaza pe ideea ca centrul clusterului, numit

centroid, este o buna reprezentare a clusterului. In prima faza se aleg n centroizi; apoi se

calculeaza distanta cosinus dintre fiecare document din colectie si centroizi, iar documentul

este asignat clusterului cu centroidul cel mai apropiat. In cea de-a doua etapa sunt recalculati

centroizii noului cluster si procedura continua pana este atins un anumit prag. Un alt algoritm

de clusterizare partitionala este algoritmul celei mai apropiate vecinatati.


27

Clusterizarea ierarhica. Algoritmii de clusterizare ierarhica produc o secventa de

partitii de acelasi fel. Similaritatea dintre fiecare pereche de documente este stocata intr-o

matrice de similaritate n x n. La fiecare pas, algoritmul fie uneste doua clustere, fie împarte

un cluster în doua. Rezultatul unei clusterizari poate fi vazut sub forma unei structurii

arborescente cu un cluster rădacină care contine toate documentele colectiei si multe clustere

la baza, fiecare continand un singur document.

Clusterizarea bazata pe grafuri. Documentele care urmeaza sa fie clusterizate pot fi

vazute ca un set de noduri si muchiile dintre noduri reprezinta relatiile dintre ele. Fiecare

muchie are o pondere, care da gradul acelei relații. Algoritmii bazati pe grafuri se bazeaza pe

partitionarea grafului, adica pe identificarea clusterelor prin taierea muchiilor din graf astfel

încat muchiile taiate sa fie minimizate. Din moment ce muchiile din graf reprezinta

similaritatea dintre documente, taind muchiile cu suma minima a ponderilor, algoritmul

minimizeaza similaritatea dintre documentele din clustere diferite. Ideea de baza este ca

ponderile muchiilor din același cluster vor fi mai mari decat ponderile muchiilor dintre

clustere.

Clusterizarea Fuzzy. Algoritmii fuzzy de obicei incearca sa gaseasca cea mai buna

clusterizare prin optimizarea unei anumite functii criteriu. Faptul ca un document poate

apartine de mai mult de un singur cluster este descris de o functie de membru. Functia de

membru calculeaza pentru fiecare document un vector de membru, in care al i-lea element

indica gradul de apartenenta a documentului la al i-lea cluster. Cel mai utilizat algoritm de

clusterizare fuzzy este Fuzzy c-means, care este o varitie a algoritmului partitional kmeans.

Clusterizarea bazata pe retele neurale. SOM (Self-Organizing Maps - Kohonen) este

un model de rețea neurala nesupervizata des folosit. Consta din doua straturi: nivelul de

intrare cu n noduri de intrare, corespunzator celor n documente si stratul de iesire cu k noduri

de iesire, care corespunde celor k regiuni de decizie. Fiecarei din cele k unităti de iesire ii este

asignat un vector de ponderi. In timpul unui pas de învatare, un document din colectie este

asociat cu un nod de iesire care are cel mai similar vector de ponderi. Vectorul de ponderi a

nodului «castigator» este apoi adaptat în asemenea fel încât va fi si mai aproape de vectorul


28

care reprezinta acel document. Iesirea algoritmului este aranjamentul documentelor de intrare

într-un spatiu 2-dimensional in asemenea fel încat similaritatea dintre doua documente de

intrare este oglindita în termenii distantei topografice dintre cele k regiuni de decizie.

In recunoasterea formelor prin metode statistice, orice forma este reprezentata cu ajutorul

unui număr de descriptori scalari, grupaŃi într-un vector. Un asemenea vector defineste un

punct în spaŃiul formelor. Rezolvarea unei aplicatii de recunoastere a formelor prin metode

statistice presupune alegerea unui set de caracteristici adecvat pentru constructia vectorilor de

forma si proiectarea unui clasificator, capabil sa atribuie orice forma, reprezentata cu ajutorul

unui asemenea vector, unei clase, __ dintr-un numar finit de clase posibile, K. Recunoasterea

formelor cuprinde doua etape: proiectarea clasificatorului, sau stabilirea regulilor de decizie si

clasificarea propriu-zisa, adica folosirea clasificatorului.

Un clasificator este un algoritm care primeste o multime de trasaturi ca intrare, si produce o

eticheta a unei clase ca iesire. Clasificatorii sunt construiti luând o multime de exemple

etichetate si folosindu-le pentru a produce o regula care va atasa o eticheta la un exemplu nou.

În cazul general, avem un set de date ce contine exemple, D = [X1, X2, …, Xp]T. Fiecare

exemplu din set este caraczerizat de o multime de trasaturi, Xk= (x1, x2,…, xd ) si fiecare

exemplu are eticheta unei clase, yi ce descrie tipul obiectului. Cunoastem costul relativ al unei

clasificari incorecte, si trebuie sa generam o regula ce poate atasa o clasa oricarui exemplu

plauzibil x.

3.2 ALGORITMUL K-NEAREST NEIGHBOUR (K-NN)

Metodele vecinului cel mai apropiat clasifica un exemplu necunoscut prin folosirea clasei

exemplului cel mai apropiat cu clasa cunoscuta din multimea de antrenare, sau folosirea mai

multor exemple din multimea de antrenare si combinarea rezultatelor prin vot.

Principiul acestei metode este clasificarea unei flori prin găsirea florii cea mai apropiata din

setul de antrenament. Metodele care se bazează pe acest principiu sunt numite metode de

”învățare bazată pe memorie”. Sunt folosite ponderile, calculându-se similaritatea dintre


29

exemplele de test și centroizii clusterelor. Ponderea asignată unui termen este o combinație a

ponderilor sale într-o interogare originală și documentele considerate relevante și irelevante.

In algoritmul de mai jos se folosește distanța Euclidiană pentru a determina similaritatea

dintre două documente.

Un clasificator de tip vecinul cel mai apropiat (k, l) gaseste k exemple apropiate de cel pe care

vrem sa îl clasificam, si clasifica acest exemplu cu clasa care are cel mai mare numar de

voturi, atâta timp cât aceasta clasa are mai mult de l voturi (altfel exemplul se clasifica

necunoscut).

Un clasificator (k, 0) – este de obicei cunoscut ca un clasificator k-nearest neighbor, iar un

clasificator (1, 0)- ca clasificator nearest neighbor.

Algoritm:

%input

K: number of neighbours

X: training set patterns

Y: class labels of the training set

z: new pattern

%output

l: predicted label of new pattern

for each x in X

compute Euclidean distance of z from x

d(x) = distance(z,x)

d is an array containing the distances of all x in X from z

end;

;order patterns of X in increasing order of d(x)


30

(sorted_d, index) = sort(X,d)

sorted_d is the list of elements of d sorted in increasing order,

and index(i) is the index in X of the i-th element of sorted_d

neighbours = index(1:k);

;index(1:k) are the first k elements of index

label_neighbours = Y(neighbours);

;Y(neighbours) are the elements of Y with index equal to neighbours;

l = majority(label_neighbours);

;majority(label_neighbours) is the class label occurring more times in the

;label_neighbours list.

Algoritmul pentru clasificatorul (k,0)-este:

• Dându-se o imagine de clasificat, cu un vector de trasaturi X=(x1,x2,…,xd)

1. Se determina k exemple din multimea de antrenare care sunt cele mai apropiate, X1, . . . ,

Xk; (vezi sectiunea 2.2).

2. Se determina clasa c (care poate fi fata sau nu) care are cel mai mare numar de reprezentanti

q în aceasta multime; se clasifica X ca c.

Rezultatele obtinute in matlab atunci cand am clasificat datele din lotul de test raportat

la vectorii din lotul de antrenare folosind algoritmul NN sunt urmatoarele: scorul pe care l-am obtinut in urma acestui algoritm este scor_NN= 36.04651.

3.3 Algoritmul K-means supervizat

3.3.1 Metoda generala K-Means.

Metoda K-Means reprezinta o procedura iterativa de obtinere a punctelor ce reprezinta

centrele clusterelor determinate de punctele de intrare date. Metoda se bazeaza pe deplasarea


31

iterativa a centrelor clusterelor catre centrul de greutate al clusterelor. Prin aceasta se asigura

satisfacerea conditiei de minim global pentru fiecare functie cost atasata unui cluster.

Daca aplicarea algoritmului K-Means provoaca deplasarea centrului unui cluster,

atunci s-ar putea ca anumite puncte situate la frontiera acelui cluster sa schimbe clusterele de

apartenenta. De aceea este necesara o noua iteratie a algoritmului deoarece clusterele s-au

modificat si centrele nu mai corespund, fiind necesara o noua deplasare a acestor centre.

Algoritmul general K-Means poate fi formulat astfel:

· Pasul 1: Initializarea clusterelor, prin distributia punctelor de intrare date, un cluster trebuind

sa contina cel putin un punct, si alegerea unor puncte Q1, Q2,..., Qm, Qi apartine R la puterea

n care sa reprezinte centrele clusterelor;

· Pasul 2: Pentru fiecare cluster (j = 1,2,...,m) se executa:

· Pasul 2.1: Deplasam centrul clusterului Qj catre media ponderata a punctelor de

intrare Xi, i apartine Ij;

· Pasul 2.2: Actualizarea multimilor index;

· Pasul 3: Se repeta Pasul 2 pâna când nici un cluster nu se mai modifica;

Algoritmul prezentat mai sus are urmatoarele dezavantaje:

- eroarea depinde esential de configuratia initiala a clusterelor (Pasul 1); configuratii initiale

diferite vor conduce la configuratii finale diferite cu erori diferite.

- numarul clusterelor este fix. De aceea nu este posibil a se construi atâtea clustere câte sunt

poate necesara pentru a obtine o eroare sub o toleranta data;

- actualizarea multimilor index necesita un efort computational considerabil. La fiecare

iteratie, trebuie calculata distanta de la toate punctele de intrare date la centrele tuturor

clusterelor;

- modificarea ulterioara a clusterelor sau a punctelor de intrare date este dificila; De aceea

introducem o metoda originala, care urmareste o idee prezentata în lucrarea.


32

3.3.2 Metoda originala K-Means

Algoritmul se bazeaza pe o metoda de inserare secventiala adaptiva a unui nou centru

de cluster în regiunea cu cea mai mare eroare relativ la functiile fi ale diagramelor Voronoi

ale tuturor punctelor de intrare care au fost inserate pâna în acel moment.

Descrierea simplificata a algoritmului este urmatoarea:

· Pasul 1: Initializam primul centru de cluster cu media aritmetica ponderata ale tuturor

punctelor de intrare. Regiunea corespunzatoare diagramei Voronoi va fi întregul spatiu al

punctelor de intrare.

· Pasul 2: Se determina regiunea Re care are eroarea cea mai mare. Multimea punctelor de

intrare Xi care apartin regiunii Re se partitioneaza în doua submultimi care vor reprezenta

doua noi clustere, pentru care se calculeaza multimile index si punctele care reprezinta

centrele noilor clustere.

· Pasul 2.1: Calculam axa de coordonate k care are care mai mare varianta a proiectiei:

· Pasul 2.2: Separam toate punctele Xi (i apartine Ie) prin intermediul unui hiperplan

perpendicular pe a k-a axa de coordonate ce trece prin punctul Qe,în doua submultimi. Pentru

cele doua noi submultimi calculam multimile index si centrele m1 si m2 ale clusterelor astfel

formate:

· Pasul 3: Actualizam diagrama Voronoi:

· Pasul 3.1: Se deplaseaza centrul clusterului Qe în centrul m1 calculat la Pasul 2.2

· Pasul 3.2: Se insereaza un nou centru de cluster în centrul m2 calculat la Pasul 2.2

· Pasul 3.3: Actualizam multimile index ale regiunilor afectate.

· Pasul 4: Pentru toate regiunile modificate:


33

· Pasul 4.1: Se deplaseaza centrul clusterului în punctul ce reprezinta media aritmetica

ponderata ale punctelor ce apartin acelei regiuni;

· Pasul 4.2: Actualizam diagrama Voronoi, multimile index si multimile de puncte ale

regiunilor modificate.

· Pasul 5: Se repeta Pasii 2 - 4 pâna când este satisfacuta conditia de clustering:

· conditia de clustering:

- s-au inserat un numar dat de centre de clustere si/sau

- eroarea maxima este mai mica decât o valoare prag impusa si/sau

- fiecare cluster contine un numar dat de puncte de intrare;

Obs 1: La Pasul 2 poate fi folosita o functie cost diferita de functia cost F. Este astfel

posibila optimizarea unei functii cost secundare, ca de exemplu cerinta ca numarul punctelor

din clustere sa fie aproximativ egala.

Obs 2: Dupa fiecare iteratie centrele clusterelor precum si triangulatia

Delauney corespunzatoare poate fi memorata pentru o utilizare ulterioara. Mai ales daca

aplicatia este în domeniul graficii, datele memorate pot fi folosite la o reprezentare triangulara

ierarhica a suprafetei reprezentate de punctele de intrare date.

In urma implementarii si aplicarii acestui algoritm la baza mea de date am obtinut

urmatorul scor: scor_Kmeans = 46.2428 si dupa cum se poate observa acest rezultat este mai bun

decat cel obtinut in cazul anterior in urma aplicarii algoritmului NN.


34

Cod Matlab

clc close all clear all V=csvread('forest_fires.data'); [nrlinii,nrcoloane]=size(V); v=zeros(nrlinii,1); k=0;l=0; for i=1:nrlinii if V(i,13)==0 k=k+1; B(k,:)=V(i,:); v(i)=1; else l=l+1; C(l,:)=V(i,:); v(i)=2; end end length1=165; for i=1:length1 for j=1:nrcoloane lot_antrenare_cls1(i,j)=B(i,j); end end for i=length1+1:247 for j=1:nrcoloane-1 lot_test_cls1(i-165,j)=B(i,j); end end for i=length1+1:247 for j=1:nrcoloane lot_test_1(i-165,j)=B(i,j); end end length2=180; for i=1:length2 for j=1:nrcoloane lot_antrenare_cls2(i,j)=C(i,j); end end for i=length2+1:270 for j=1:nrcoloane-1


35

lot_test_cls2(i-180,j)=C(i,j); end end for i=length2+1:270 for j=1:nrcoloane lot_test_2(i-180,j)=C(i,j); end end lot_antrenare_cls1=lot_antrenare_cls1'; lot_antrenare_cls2=lot_antrenare_cls2'; lot_test_cls1=lot_test_cls1'; lot_test_cls2=lot_test_cls2'; lot_test_1=lot_test_1'; lot_test_2=lot_test_2'; antrenare=[lot_antrenare_cls1 lot_antrenare_cls2]; test=[lot_test_cls1 lot_test_cls2]; test1=[lot_test_1 lot_test_2]; %Vectorul medie pentru vectorii de intrare din setul de antrenare %implementat folosind functia din curs [nr1,dim1]=size(lot_antrenare_cls1) mediacls1=zeros(nr1,1); % Initializare media vectorilor de intrare cu 0 for i=1:dim1 mediacls1=mediacls1+((1/dim1)*lot_antrenare_cls1(1:nr1,i)); end disp('Media vectorilor din clasa 1 este:')% Se afiseaza "Media vectorilor de intrare este:" disp(mediacls1)% Se afiseaza media vectorilor din clasa1 media1_matlab = mean(lot_antrenare_cls1,2);%media calculata cu functia matlab %------------------------------------------------------------------- [nr,dim]=size(antrenare) mediaantr=zeros(nr,1); % Initializare media vectorilor de intrare cu 0 for i=1:dim mediaantr=mediaantr+((1/dim)*antrenare(1:nr,i)); end disp('Media vectorilor din lotul de antrenare e:')% Se afiseaza "Media vectorilor de intrare este:" disp(mediaantr)% Se afiseaza media vectorilor din clasa1 media_matlab = mean(antrenare,2);%media calculata cu functia matlab %Vectorul medie pentru vectorii de intrare din setul de antrenare %implementat folosind functia din curs [nr2,dim2]=size(lot_antrenare_cls2) mediacls2=zeros(nr2,1); % Initializare media vectorilor de intrare cu 0 for i=1:dim2 mediacls2=mediacls2+((1/dim2)*lot_antrenare_cls2(1:nr2,i)); end disp('Media vectorilor din clasa 2 este:')% Se afiseaza "Media vectorilor de intrare este:" disp(mediacls2)% Se afiseaza media vectorilor din clasa1


36

media2_matlab = mean(lot_antrenare_cls2,2);%media calculata cu functia matlab %------------------------------------------------------------------- matcov=zeros(nr,nr); %Inializare matricea de covariatie cu 0 for j=1:dim matcov=matcov +((1/dim)*(antrenare(1:nr,j)-mediaantr)*(antrenare(1:nr,j)-mediaantr)'); end disp('Matricea de covariatie a vectorilor din lotul de antrenare:') disp(matcov); Aa=cov(antrenare');%matricea de covarianta calculata cu functia matlab %-------------------------------------------------------------------------- %Matricea de covarianta matcov1=zeros(nr1,nr1); %Inializare matricea de covariatie cu 0 for j=1:dim1 matcov1=matcov1 +((1/dim1)*(lot_antrenare_cls1(1:nr1,j)-mediacls1)*(lot_antrenare_cls1(1:nr1,j)-mediacls1)'); end disp('Matricea de covariatie a vectorilor din clasa 1 este:') disp(matcov1); A1=cov(lot_antrenare_cls1');%matricea de covarianta calculata cu functia matlab %-------------------------------------------------------------------------- %Matricea de covarianta matcov2=zeros(nr2,nr2); %Inializare matricea de covariatie cu 0 for j=1:dim2 matcov2=matcov2 +((1/dim2)*(lot_antrenare_cls2(1:nr2,j)-mediacls2)*(lot_antrenare_cls2(1:nr2,j)-mediacls1)'); end disp('Matricea de covariatie a vectorilor din clasa 2 este:') disp(matcov2) A2=cov(lot_antrenare_cls2');%matricea de covarianta calculata cu functia matlab %-------------------------------------------------------------------------- %Calculul valorilor proprii si ordonarea descrescatoare a acestora disp('Vectorii proprii si matricea valorilor proprii din clasa 1 sunt: ') [matrice_vectori1,matrice_val_propri1]=eig(matcov1) % returneaza vectorii proprii vect_proprii si vectorul de valori proprii val_propri1 = zeros(nr1-1,1); for i=1:(nr1-1) val_propri1(i) = matrice_val_propri1(i,i) end val_propri1 = sort (val_propri1, 'descend'); %valorile proprii in ordine descrescatoare matrice_vectori1 = matrice_vectori1(:,nr1-1:-1:1); %rearanjam vectorii a.i. sa coresp valorilor in ord descresc (inversam ordinea col) matrice_vectori1 val_propri1 %-----------------------------------------------------------------


37

%Calculul valorilor proprii si ordonarea descrescatoare a acestora disp('Vectorii proprii si matricea valorilor ai vectorilor din lotul de antrenare sunt: ') [matrice_vectori,matrice_val_propri]=eig(matcov) % returneaza vectorii proprii vect_proprii si vectorul de valori proprii val_propri = zeros(nr-1,1); for i=1:(nr-1) val_propri(i) = matrice_val_propri(i,i) end val_propri = sort (val_propri, 'descend'); %valorile proprii in ordine descrescatoare matrice_vectori = matrice_vectori(:,nr-1:-1:1); %rearanjam vectorii a.i. sa coresp valorilor in ord descresc (inversam ordinea col) matrice_vectori val_propri %Calculul valorilor proprii si ordonarea descrescatoare a acestora disp('Vectorii proprii si matricea valorilor proprii din clasa a 2-a sunt: ') [matrice_vectori2,matrice_val_propri2]=eig(matcov2) % returneaza vectorii proprii vect_proprii si vectorul de valori proprii val_propri2 = zeros(nr2-1,1); for i=1:(nr2-1) val_propri2(i) = matrice_val_propri2(i,i) end val_propri2 = sort (val_propri2, 'descend'); %valorile proprii in ordine descrescatoare matrice_vectori2 = matrice_vectori2(:,nr2-1:-1:1); %rearanjam vectorii a.i. sa coresp valorilor in ord descresc (inversam ordinea col) matrice_vectori2 val_propri2 %----------------------------------------------------------------- %Matricea transformarii KLT pentru PCA (cu ajutorul vectorilor proprii) disp('Matricea KLT pentru PCA clasa 1 este:') KLT1=matrice_vectori1' %---------------------------------------------------------------- %Matricea transformarii KLT pentru PCA (cu ajutorul vectorilor proprii) disp('Matricea KLT pentru PCA clasa 2 este:') KLT2=matrice_vectori2' %---------------------------------------------------------------- %Matricea transformarii KLT pentru PCA (cu ajutorul vectorilor proprii) disp('Matricea KLT pentru PCA lot antrenare:') KLT=matrice_vectori' %---------------------------------------------------------------- %Ortogonalitatea matricei KLT Q1=KLT1*KLT1' %Se calculeaza produsul dintre matricea KLT si transpusa ei r1=round(Q1) %Se rotunjesc valorile obtinute in urma inmultirii g1=eye(nr1-1) %Se genereaza matricea identitate de dimensiune egala cu numarul vectorilor de intrare if (isequal(r1,g1)) disp('r1 = g1 => Matricea KLT1 e ortogonala') else


38

disp('r1 <> g1 => Matricea KLT1 nu e ortogonala') end %----------------------------------------------------------------- %Ortogonalitatea matricei KLT Q2=KLT2*KLT2' %Se calculeaza produsul dintre matricea KLT si transpusa ei r2=round(Q2) %Se rotunjesc valorile obtinute in urma inmultirii g2=eye(nr2-1) %Se genereaza matricea identitate de dimensiune egala cu numarul vectorilor de intrare if (isequal(r2,g2)) disp('r2 = g2 => Matricea KLT2 e ortogonala') else disp('r2 <> g2 => Matricea KLT2 nu e ortogonala') end %----------------------------------------------------------------- %Ortogonalitatea matricei KLT Q=KLT*KLT' %Se calculeaza produsul dintre matricea KLT si transpusa ei r=round(Q) %Se rotunjesc valorile obtinute in urma inmultirii g=eye(nr-1) %Se genereaza matricea identitate de dimensiune egala cu numarul vectorilor de intrare if (isequal(r,g)) disp('r = g => Matricea KLT e ortogonala') else disp('r <> g => Matricea KLT nu e ortogonala') end %----------------------------------------------------------------- %Graficul valorilor proprii ordonate figure(1),plot(log(diag(val_propri1)),'b*') %----------------------------------------------------------------- %Graficul valorilor proprii ordonate figure(2),plot(log(diag(val_propri2)),'g*') %----------------------------------------------------------------- %Graficul valorilor proprii ordonate figure(3),plot(log(diag(val_propri)),'r*') %----------------------------------------------------------------- %7. ENERGIA CONSERVATA SI EROAREA PATRATICA eroare1=0;%eroarea for m=1:(nr-1) %numarul de componente retinut suma1=0; suma2=0; for i=1:m suma1=suma1+val_propri(i,1); end for i=1:nr-1 suma2=suma2+val_propri(i,1); end


39

eta1 = (suma1/suma2)*100; %factorul de conservare a energiei informationale eroare1 = 100-eta1 disp('Factorul de conservare a energiei pentru vectorii din clasa1 este: eta1='); disp(eta1); disp('Eroarea este: eroare1='); disp(eroare1); end %-------------------------------------------------------------------------- %8. STABILIREA NR DE COMP RETINUTE %a) criteriul valorilor proprii: prag = val_propri(1)/100; nr_componente = 0; for i=1:nr-1 if (val_propri(i)>prag) nr_componente=nr_componente+1; end end disp('Se retin %i componente\n'); disp(nr_componente); %_____________________________________________________________________% % %b) energia totala>50% %_____________________________________________________________________% prag_energ50 = 0.5; suma1=0; suma2=0; for i=1:nr-1 suma2=suma2+val_propri(i,1); end prag_val50 = prag_energ50*suma2; i=1; while (suma1<prag_val50) suma1 = suma1+val_propri(i,1); if (suma1<prag_val50) i = i+1; end end suma1=0; suma2=0; for j=1:i suma1=suma1+val_propri(j,1); end for j=1:nr-1 suma2=suma2+val_propri(j,1); end


40

eta50 = (suma1/suma2)*100 disp('Numarul componentelor retinute pt 50% '); disp(i); %__________________________________________________________________% % %b) energia totala>75% %_____________________________________________________________________% prag_energ75 = 0.75; suma1=0; suma2=0; for i=1:nr-1 suma2=suma2+val_propri(i,1); end prag_val75 = prag_energ75*suma2; i=1; while (suma1<prag_val75) suma1 = suma1+val_propri(i,1); if (suma1<prag_val75) i = i+1; end end suma1=0; suma2=0; for j=1:i suma1=suma1+val_propri(j,1); end for j=1:nr-1 suma2=suma2+val_propri(j,1); end eta75 = (suma1/suma2)*100 disp('Numarul componentelor retinute pt 75%'); disp(i); %_____________________________________________________________________% % %b) energia totala>90% %_____________________________________________________________________% prag_energ90 = 0.90; suma1=0; suma2=0; for i=1:nr-1 suma2=suma2+val_propri(i,1); end


41

prag_val90 = prag_energ90*suma2; i=1; while (suma1<prag_val90) suma1 = suma1+val_propri(i,1); if (suma1<prag_val90) i = i+1; end end suma1=0; suma2=0; for j=1:i suma1=suma1+val_propri(j,1); end for j=1:nr-1 suma2=suma2+val_propri(j,1); end eta90 = (suma1/suma2)*100 disp('Numar componente retinute pt 90%'); disp(i); %_____________________________________________________________________% % %b) energia totala>95% %_____________________________________________________________________% prag_energ95 = 0.95; suma1=0; suma2=0; for i=1:nr1-1 suma2=suma2+val_propri(i,1); end prag_val95 = prag_energ95*suma2; i=1; while (suma1<prag_val95) suma1 = suma1+val_propri(i,1); if (suma1<prag_val95) i = i+1; end end suma1=0; suma2=0; for j=1:i suma1=suma1+val_propri(j,1); end for j=1:nr1-1


42

suma2=suma2+val_propri(j,1); end eta95 = (suma1/suma2)*100 disp('Numar componente retinute pt 95%'); disp(i); %_____________________________________________________________________% % %b) energia totala>99% %_____________________________________________________________________% prag_energ99_1 = 0.99; suma1=0; suma2=0; for i=1:nr1-1 suma2=suma2+val_propri1(i,1); end prag_val99_1 = prag_energ99_1*suma2; i=1; while (suma1<prag_val99_1) suma1 = suma1+val_propri1(i,1); if (suma1<prag_val99_1) i = i+1; end end suma1=0; suma2=0; for j=1:i suma1=suma1+val_propri1(j,1); end for j=1:nr1-1 suma2=suma2+val_propri1(j,1); end eta99 = (suma1/suma2)*100 disp('nr componente retinute pt 99%'); disp(i); %_____________________________________________________________________% % %c) energia daca se retin 2 elemente %_____________________________________________________________________% suma1=0; suma2=0; for i=1:2


43

suma1=suma1+val_propri1(i,1); end for i=1:nr1-1 suma2=suma2+val_propri1(i,1); end eta2 = (suma1/suma2)*100; disp('energia conservata daca se retin 2 elemente='); disp(eta2); %_____________________________________________________________________% %9. CLASIFICATORI %_____________________________________________________________________% lot_test_cls1=lot_test_cls1'; %TOTI VECTORII SUNT COLOANA %9a Nearest Neighbour %calc dist dintre fiecare vect de test si fiecare vector de antrenare lung=13; cls=zeros(1,172); alegeri_corecte = 0; for j = 1:172%nr vectori test i_min = 1; dist_min = 1000000; for i=1:345%nr de vectori de antrenament dist = 0; for l = 1:lung-1 dist = dist+(antrenare(l,i)-test(l,j))*(antrenare(l,i)-test(l,j)); end if (dist<dist_min) dist_min = dist; i_min = i; end end if (antrenare(lung, i_min) == 0) cls(1,j)=0 else cls(1,j)=1; end if (test1(lung, j) ==0 && cls(1,j)==1) alegeri_corecte = alegeri_corecte+1; end end %n_test= nr vect de test scor_nn = (alegeri_corecte/172)*100; fprintf ('scor nn = %f%', scor_nn);

% b. k-means supervizat


44

medie1=zeros(mm-1,1); medie2=zeros(mm-1,1); for i=1:a1 for j=1:n1 medie1(i)=medie1(i)+Y_cls1_antr(i,j); end for k=1:n2 medie2(i)=medie2(i)+Y_cls2_antr(i,j); end end medie1=medie1/n1; medie2=medie2/n2; %SAU % medie1=mean(Y_cls1_antr,2); % medie2=mean(Y_cls2_antr,2); P=zeros(e,1); contor=0; BB=[]; for i=1:e dist1=0; dist2=0; for j=1:(mm-1) dist1=dist1+(Y_test(j,i)-medie1(j,1))^2; dist2=dist2+(Y_test(j,i)-medie2(j,1))^2; end dist1=sqrt(dist1); dist2=sqrt(dist2); if (dist1==dist2) nr=rand(1); if nr<0.5 clasa=0; P(i,1)=clasa; else clasa=1; P(i,1)=clasa; end elseif (dist1<dist2) clasa=0; P(i,1)=clasa; elseif (dist2<dist1) clasa=1; P(i,1)=clasa; end end Y_cls1_test=Y_cls1(1:mm,2*nnn_n+1:nnn); Y_cls2_test=Y_cls2(1:mm,2*nnnn_n+1:nnnn); Y_test=[Y_cls1_test,Y_cls2_test]; contor=1;


45

for i=1:e if Y_test(mm,i)==P(i) %&((Y_test(mm,i)~=0)&(P(i)~=0))) contor=contor+1; end end disp('Scorul (procentajul claselor atribuite corect) obtinut folosind algoritmul k-means supervizat este'); scor_K=(contor/e)*100

tdm1final

Documents