Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme



Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Calculatoare


Index » educatie » » informatica » Calculatoare
Concepte de baza necesare in procesul de clasificare a formelor


Concepte de baza necesare in procesul de clasificare a formelor




Tehnici de decizie si clasificare.

Scopul lucrarii

Lucrarea are ca scop prezentarea unor concepte de baza necesare in procesul de clasificare a formelor.

Notiuni teoretice




Selectarea trasaturilor

Este necesara determinarea unei clase optimale de trasaturi care sa permita separarea obiectelor ce trebuiesc recunoscute. Ansamblul optimal de trasaturi este functie de familia de obiecte de recunoscut. Adaugarea sau eliminarea unui obiect din aceasta familie poate modifica ansamblul trasaturilor optimale. Nu exista o teorie generala pentru selectarea parametrilor, dar se utilizeaza tehnici pentru aprecierea puterii discriminante a unei clase de trasaturi.

Printre tehnicile folosite pentru marirea relevantei informatiilor furnizate de vectorul de trasaturi mentionam:

Normarea trasaturilor - procedeu util atunci cand extragerea trasaturilor este facuta din mai multe surse diferite;

Ponderarea trasaturilor - permite accentuarea trasaturilor esentiale ale procesului de clasificare;

Transformarea sau combinarea trasaturilor - astfel incat utilizarea lor sa fie mai usoara;

Analiza componentelor principale (Karhunen- Loeve) - determina vectori ortogonali de dimensiuni mai reduse;

Reducerea dimensiunii vectorului trasaturilor - pe baza unor metode matematice utilizand transformate diagonale, rotationale, transformata Fourier, Walsh/Hadamard.

Clasificarea propriu-zisa

Exista doua moduri de abordare a clasificarii propriu-zise:

Clasificarea controlata - presupune existenta unui set de forme a caror apartenenta la clase este cunoscuta.

Clasificarea necontrolata - in care nu se face apel la o cunoastere prealabila a apartenentei unei forme la o clasa.

Vectori de forma si spatiul formelor

Fiecare caracteristica poate fi considerata ca fiind o variabila intr-un spatiu n-dimensional unde fiecare caracteristica este atribuita unei dimensiuni. Fiecare forma apare ca un punct in spatiul formelor. Cand o forma este descrisa de mai multe caracteristici ea poate fi privita ca un vector X, denumit vectorul de forma. Acest vector este dat de relatia:

(2.1)

unde xi, i= 1, . , n reprezinta cele n caracteristici.

Spatiul formelor notat cu WX poate fi descris cu ajutorul relatiei

(2.2)

unde Xi desemneaza vectorul transpus a lui X, iar m numarul de forme.

Tehnici de decizie si clasificare

Conceptul de clasificare al formelor poate fi inteles ca o partitionare a spatiului caracteristicilor acestuia. Clasificarea formelor, adica atribuirea fiecarui vector posibil sau punct din spatiul caracteristicilor clasei din care face parte, poate fi interpretata ca o partitionare a acestuia in regiuni (domenii) reciproc exclusive, fiecare domeniu apartinand unei clase de forme particulare. Din punct de vedere matematic acest gen de problema de clasificare poate fi definita sub forma unei functii discriminant. Astfel fie w w wm cele m clase de forme posibile cu proprietatile:

w w . wm WX (2.3)

si

w1 w . wm = F.

Unde cu F s-a notat multimea care constituie frontierele dintre clase, iar cu X s-a notat vectorul de forma. In acest caz functia discriminant Dj(X) asociata clasei de forme wj, j =1, . , m are proprietatea ca daca forma reprezentata prin vectorul X face parte din wi, fapt pe care-l vom simboliza X wi, cu i specificat, atunci valoarea lui Di(X) trebuie sa fie cea mai mare, adica pentru toti X wi va fi indeplinita conditia

Di(X) > Dj(X); i,j = 1, . , m, i j. (2.4)

In felul acesta limitele de partitionare ale spatiului caracteristicilor (desemnate anterior cu F), denumite si limite de decizie, pot fi exprimate cu ajutorul relatiei

F = Di(X) Dj(X) = 0; i, j=1, . ,m, i j   

Au fost propuse foarte multe forme pentru functii discriminant Di(X), forme ce satisfac conditia (2.4). dintre acestea vom mentiona in continuare doar pe cele mai importante.

Functii discriminant liniare

Intr-un spatiu bidimensional aceste functii sunt liniare si pot fi scrise sub forma:

x1-mx2-b=0,

sau

W1x1+W2x2+W3x3=0    (2.6)

unde:

m - este coeficientul unghiular,

b - termenul liber,

iar W1= 1, W2= -m si W3= -b.

Intr-un spatiu n- dimensional functiile sunt hiperplane de forma:

W1x1+W2x2+ . .+Wnxn+Wn+1= 0 (2.7)

In acest caz functia discriminant Di(X) asociata clasei de forme wi reprezinta o combinatie liniara a caracteristicilor xi, i =1, . ,m, data in relatia:

Di(X)= Wi,kxk+ Wi,n+1 , I =1, . ,m (2.8)

Ecuatiile hiperplanelor date de relatia (1.8), pentru m clase de forme, pot fi scrise matriceal astfel:





D(X)=

Unde:

si (2.9)

In vectorul X s-a introdus suplimentar termenul 1 pentru a da posibilitatea efectuarii operatiei de inmultire.

Limita de decizie dintre regiunile Wx corespunzatoare claselor wi si wj este de forma:

Di(X) Dj(X) = Wkxk+Wn+1 ; k = 1n; (2.10)

unde:

Wk=Wi,k Wj,k

si

Wn+1=Wi,n+1-Wj,n+1.

Ecuatia (2.10) reprezinta ecuatia unui hiperplan din spatiul caracteristicilor Wx, numit si plan de decizie. Pentru a ilustra modul de utilizare a functiilor discriminant liniare prezentam un exemplu in care avem doua forme intr-un spatiu bi-dimensional. Fie formele X1 si X2 date de:

si

si functia de decizie D(X) = 0 data de relatia:

Relatia de mai sus poate fi scrisa sub forma:

Daca inlocuim pe X1 si X2 in D(X), obtinem:

si respectiv

Pentru orice punct aflat deasupra lui D(X) = 0, D(X) este pozitiv si negativ pentru punctele de sub dreapta. Astfel, pentru cazul a doua clase, polaritatea in evaluarea lui D(X) determina la care clasa apartine forma data (Fig. 2.2-1).

Fig. Functia de decizie liniara in doua dimensiuni.

In cazul in care este necesara discriminarea pentru mai mult de doua forme sunt necesare doua sau mai multe functii de decizie. Pentru aceasta situatie exista trei tipuri de clasificatori.

i)            Tipul 1 utilizeaza o functie de decizie care imparte spatiul formelor in doua clase. Prima clasa notata cu wi contine o singura forma, iar cea de a doua clasa contine restul formelor. Pentru a asigura apartenenta unei forme la clasa wi este suficient sa fie indeplinita conditia Di(X)>0 si Dj(X)<0 pentru toti i, j. Pentru n clase sunt necesare n functii de decizie.

ii)          Tipul 2 utilizeaza functii de decizie care separa spatiul formelor in doua regiuni. Prima regiune contine doua clase, iar cea de-a doua restul claselor. Separarea celor doua clase wi si wj se face cu ajutorul unei functii de decizie de forma Dij(X) = 0. Apartenenta unei forme la clasa wi sau wj este asigurata daca Dij(X) > 0.

iii)        Tipul 3 reprezinta un caz special al tipului 2 de clasificare. Din analiza figurilor 2.2-2a si 2.2-2b se observa prezenta unui spatiu nedeterminat care apare in interiorul triunghiului format din cele trei drepte corespunzatoare functiei de decizie. Punctele din interiorul acestui triunghi nu pot fi atribuite la nici una din cele trei clase. Pentru a elimina aceasta nedeterminare, functia de decizie de tipul 2, Dij(X) = 0 este inlocuita cu Di(X)-Dj(X) = 0, unde Di(X) si Dj(X) sunt functii de decizie de tipul 1. Pentru ca o forma sa fie atribuita clasei wi este necesar, in acest caz, indeplinirea conditiei Di(X)>Dj(X) pentru toti j i (vezi fig. 2.2-2c).

Fig. Functii de decizie multi-categorie: a-tipul 1; b-tipul 2; c-tipul 3.

Daca clasele pot fi separate utilizand tipul 1 de clasificare, regiunile in care este prezenta clasele vor fi mai compacte, fapt care conduce la o mai buna identificare a claselor decat in cazul utilizarii tipului 2 sau 3 de clasificare. In schimb, insa, regiunea de nedeterminare este mare. Daca in aplicatia practica apar forme in regiunea de nedeterminare rezultate in urma aplicarii tipului 1 de clasificare, poate fi incercata utilizarea tipului 2 de clasificare, in care regiunea de nedeterminare este mai mica sau a tipului 3 (tipul 3 de clasificare are dezavantajul ca timpul de calcul este mare)

Clasificatorul de distanta minima

O importanta clasa de clasificatori se bazeaza pe valoarea distantelor dintre forma de intrare si un set de vectori de referinta sau puncte prototip din spatiul caracteristicilor (prototipurile sunt forme a caror apartenenta la clase este cunoscuta). Daca vom presupune ca sunt cunoscuti m vectori de referinta, notati cu R1, R2, . Rm, cu Rj asociat clasei wj atunci clasificatorul de distanta minima va atribui forma de intrare X clasei wi daca distanta dintre aceasta si vectorii de referinta este minima,

adica X wi daca d = X-Ri = minim.    (2.11)

Consideram doua grupe de puncte distincte in spatiul formelor si ne propunem sa determinam functia de decizie care va putea separa spatiul formelor in doua regiuni care vor corespunde celor doua clase. Initial vom determina vectorii de referinta pe care ii vom considera reprezentand centrele celor doua grupari de puncte. Valoarea punctelor prototip poate fi calculata cu o relatie de forma :

(2.12)

unde N reprezinta numarul de forme dintr-o grupare. Distanta dintre o forma X si centrul gruparii R (R este de forma R = (r1, r2, . ,rm)) este data de relatia d = X-R . Daca consideram ca cele doua grupari se afla intr-un spatiu bi-dimensional, atunci d va avea urmatoarea forma :

d2 = (x1 - r1)+(x2 - r2)2 = x12 - 2x1r1 + r12 + x22 - 2x2r2 + r22.

In cazul cand avem mai mult de doua clase, distanta dintre o forma X si Ri al gruparii i este data de :

(2.13)

Deoarece este aceeasi pentru toate clasele, el poate fi eliminat. Daca inmultim relatia (1.13) cu 0.5, vom obtine :

(2.14)

Deoarece di2 a fost inmultit cu un numar negativ rezulta ca cea mai mare functie de decizie (max Di(X)) identifica distanta minima si deci clasa lui X.

Pentru determinarea termenilor W, din functia de decizie se utilizeaza relatia (2.14) si rezulta , pentru i = 1,.., n si .

Din cele spuse anterior rezulta ca un clasificator de distanta minima este un clasificator liniar. Performanta unui astfel de clasificator depinde evident de modul cum sunt alesi vectorii de referinta dar si de felul cum sunt evaluate distantele. Cele mai frecvente distante utilizate sunt cele derivate de distanta generala Minkovski.



(2.15)

Astfel, pentru k = 2 se obtine binecunoscuta distanta Euclidiana.

(2.16)

Pentru k = 1 se obtine distanta Manhattan.

(2.17)

Daca toate caracteristicile xi si ri, i =1, . ,n sunt codificate binar (au doar valorile 0 sau 1), atunci distanta Manhattan poarta numele de distanta Hamming. Distanta Hamming este echivalenta cu numarul de caracteristici care sunt diferite in X si R. Aplicarea lui SAU EXCLUSIV, simbolizat aici prin XOR, permite calcului foarte rapid al distantei Hamming conform relatiei:

(2.18)

Distanta Tanimoto reprezinta distanta Hamming normalizata.

(2.19)

Exemplu de determinare a functiilor de decizie.

Fie un spatiu bidimensional ce contine un numar de trei clase w w w Cele trei clase contin urmatoarele forme:

,

,

.

Vectorii prototip ai claselor vor fi:

.

Functiile de decizie sunt de forma:

Pentru a testa acest clasificator se alege un punct din spatiul trasaturilor de forma:

si se substituie in , pentru I=1,2,3.

Se observa ca in acest caz avem D1>D2 si D1>D3 . Conform clasificatorului de tip 3, forma X este cea mai apropiata de de clasa 1 si cea mai indepartata de clasa 3. Rezulta ca X.

Alte tipuri de clasificatori

In literatura de specialitate sunt dezvoltati un numar mare de clasificatori, majoritatea avand ca punct de plecare clasificatorul distantei minime prezentat anterior. Dintre acestia cei mai importanti sunt:

i)            Clasificatorul vecinului cel mai apropiat. Acesta dezvolta un clasificator de distanta minima in raport cu mai multe seturi de vectori de referinta. Astfel, fie R1, . ,Rm cele m seturi de vectori prototip asociate, respectiv, claselor w wm si Rj(k) setul de vectori de referinta din setul Rj, care apartin clasei wj. In acest caz distanta dintre forma de intrare reprezentata prin vectorul X si setul de vectori de referinta Rj se defineste astfel:

, j = 1, . ,m (2.19)

Uj fiind numarul de vectori de referinta din setul Rj. Clasificatorul ce utilizeaza acest tip de distanta va fi de forma

i =1, . , m (2.20)

Acesti clasificatori sunt adesea denumiti clasificatori liniari pe portiuni sau clasificatori bazati pe cei mai apropiati U vecini.

ii)          Functii discriminant polinomiale.

Acestea dezvolta un clasificator de forma:

(2.21)

unde:

k1, k2, . .kr = 1, . ,n

pentru si

n1, n2, . ,nr = 0 si 1.

Limita de decizie dintre oricare 2 clase are forma unui polinom de ordinul r. In mod particular, pentru r = 2 obtinem o functie discriminant patrata cu

pentru k1, k2= 1, . ,n; n1, n2 = 0 si 1 (2.22)

si L = (1/2) n (n+3).   

In aceasta situatie limita de decizie este un hiper-hiperboloid (in unele cazuri speciale aceste limite pot fi hipersfere sau hiperelipsoizi).

iii)        Clasificatorul Bayes

Se foloseste atunci cand distributia formelor nu este total disjuncta si exista suprapuneri semnificative ale valorilor trasaturilor diferitelor clase de forme.

In abordarea Bayesiana se folosesc cunostinte probabilistice despre trasaturile formelor si despre frecventa lor de aparitie.

Se presupune ca probabilitatea formelor clasei wi este P(wi Acesta inseamna ca apriori cunoastem probabilitatea de aparitie a unei forme din clasa wI si, in absenta oricaror alte cunostinte, putem minimiza probabilitatea erorii de decizie presupunand ca forma necunoscuta apartine clasei cu probabilitatea P(wi maxima. In luarea unei decizii de apartenenta se tine seama si de observatii asupra formelor.

Comportarea unei clase de forme este descrisa de probabilitatea conditionata p(x/wi Probabilitatea p(x/wi ne spune ca o trasatura masurata a unei forme apartinand clasei w are valoarea x cu probabilitatea p(x/wI Bazat pe aceste cunostinte se poate calcula probabilitatea a posteriori p(wj /x) pentru o forma necunoscuta. Probabilitatea a posteriori p(wj /x) a unei forme necunoscute ne spune ca daca o masuratoare facuta asupra formei necunoscute are valoarea x forma apartine clasei wj cu probabilitatea p(wj /x)



In multe aplicatii practice componentele lui x sunt valori ale variabilelor binare sau ternare asa incat x poate sa primeasca doar una dintre valorile discrete ale lui m, v1, . ,vm. In asemenea cazuri densitatea de probabilitatea a functiei p(x/wj devine singulara; integrale ca si

sunt transformate in sume de forma

unde P(vk|vj este probabilitatea conditionata ca x = vk, dindu-se astfel stara lui vj

Calculul probabilitati conditionate p(wj /x) se face pe baza formulei lui Bayes:

, (2.23)

unde:

si

m reprezinta numarul de clase.

Forma necunoscuta trebuie asignata clasei cu p(wj /x) maxim. Formula poate fi generalizata pentru cazul unor vectori de trasaturi n dimensionali.

, (2.24)

unde:

,

m reprezinta numarul de clase si

X este vectorul de forma n-dimensional.

Functia discriminant dezvoltata pentru clasificatorul Bayes este de forma:

Di(X) = P(wi)*p(X/wi), i =1, . ,n

PROBLEME PROPUSE

Considerand un spatiu bidimensional si folosind functia discriminant liniara x1-mx2-b=0 pentru m =4 si b =2, scrieti un program care sa stabileasca apartenenta la unul din semiplanele delimitate de frontiera de decizie pentru perechi de forme, specificate de utilizator.

Aceleasi cerinte ca la problema precedenta considerand urmatoarea functie polinomiala de decizie

x1+x2-x3+1=0

intr-un spatiu tridimensional.

Folosind metoda clasificatorului de distanta minimala si utilizind la alegere una din metodele de calcul a distantei minimale (Minkovski, Euclidiana, Manhattan), pe baza determinarii functiei de decizie in spatiul bidimensional, stabiliti apartenenta unei forme x din spatiul bidimensional uneia din cele trei clase de forme w w w definite de utilizator.

Ind. Puteti folosi ca model clasele definite in exemplul dat pentru calculul functiei de decizie in cazul clasificatorului de distanta minimala.

Fiind dat un spatiu bidimensional si trei clase de forme definite de utilizator, scrieti un program care sa stabileasca apartenenta unei forme necunoscute x la una din clasele date cunscand apriori probabilitatea de aparitie a unei forme din clasa wi, i =1, . ,3 P(wi si probabilitatea ca o trasatura masurata a formei apartinand clasei wi sa aiba o anumita valoare (p(x/wi

Obs. P se exprima ca nr.cazuri favorabile /nr. cazuri posibile .

Sa consideram problema densitatii conditionate pentru doua categorii unidimensionale data de distributia Cauchy

i =1, 2.

Daca P(w )= P(w aratati ca p(w /x)= p(w /x) daca x=

Calculati p(w /x) pentru cazul .Cum se comporta p(w /x) cand






Politica de confidentialitate


Copyright © 2020 - Toate drepturile rezervate