Laborator - Algoritmi de clasificare Bayes

Introducere :

Formele sunt atat obiectele fizice observabile dar si modele matematice relativ la celule, particule , forme de unda, spectre de frecventa (imagini TV, semnale radar, zgomote, EKG-uri), aplicatiile de recunoasterea formelor fiind prezente in medicina, imageria satelitara, meteorologie, criminalistica sau aplicatii militare. O forma data poate fi descrisa printr-un set de entitati caracteristice exprimate prin numere reale (biti) X_F=(x₁,..x_n), unde N depinde de precizia urmarita (de exemplu rezolutia unei imagini). Algoritmii de clasificare Bayes fac parte din metodele statistice de clasificare si recunoastere a formelor.

Baza teoretica :

I. Algoritmi de clasificare Bayes (cazul a doua clase)

Fie W = w (M clase disjuncte de forme de acelasi tip w w_M, M ≥ 2) si se considera cunoscute din determinari statistice probabilitatile apriori P ( w_i ) ale claselor w_i (pentru i=1.M), si se presupune ca P( w_i ) > 0 si P( w_i

1. Regula lui Bayes de clasificare (ipoteza binara)

In cazul a doua clase de forme w w (M=2), o forma noua de intrare X (vector aleator n-dimensional de caracteristici) poate fi clasificata (teoretic) prin compararea probabilitatilor aposteriori dupa regula :

unde:

i=1,2:

P ( w_i | X ) este probabilitatea aposteriori (probabilitatea ca dupa ce X a fost clasificat, forma X sa apartina clasei w_i

P ( w_i ) este probabilitatea apriori a clasei w_i, i=1,2 (probabilitatea ca o forma sa apartina clasei w_i

2. Algoritmul lui Bayes cu eroare minima de clasificare

Algoritmul Bayes cu eroare minima realizeaza clasificarea formelor pe baza compararii raportului de plauzibilitate cu un anumit prag. Definim :

raportul de plauzibilitate L ( x ) = (al claselor w w , relative la forma X), unde f( x | w ) si f( x | w ) sunt functiile densitate ale vectorului X conditionate de w respectiv w

pragul raportului de plauzibilitate n =

si notam cu h = - ln L

Relatia lui Bayes devine :

h( x ) _>^< ln T X I { (2)

Testul de clasificare Bayes poate duce la situatii de ambiguitate, in cazul egalitatii membrului stang. De aceea se evalueaza performanta testului prin calcularea probabilitatii erorii de clasificare. La egalitate se obtine ecuatia suprafetei de separatie:

L (x) = n

ce imparte spatiul Rⁿ in doua regiuni

R₁ : L (x) ≥ n si R₂: L (x) < n

Eroarea de clasificare a formei X apare cand se atribuie X regiunii R₂ in cazul in care XI R₁ sau daca X se atribuie lui R₁ cand in realitate XI R₂

Probabilitatea erorii de clasificare e este :

In ipoteza ca densitatile de probabilitate conditionate f ( x | w ) si f ( x | w ) sunt normal distribuite, avand vectorii medie m si m , si matricele de covariatie S si S se poate scrie relatia echivalenta :

Demonstratie:

Din relatia (2) avem ln _>^< ln ,

Inlocuind f ( x | w ) =exp(-(x - m )^T S (x - m )) (vezi mai jos def. 3) si f ( x | w ) => (x - m )^T S (x - m ) - (x - m )^T S (x - m ) + ln _>^< ln (q.e.d.)

4. Algoritmul lui Bayes de risc minim (extinde algoritmul cu eroare minima de clasificare)

Notam cu c_ij costul clasificarii eronate a formei X I wj cand de fapt este w_I i, j 2) si presupunem ca o decizie eronata este mai scumpa decat o decizie corecta:

Pentru c₁₂ > c₁₁ si c₂₁ > c₂₂ in urma minimizarii costului mediu

r = c_ij P( w_i ) f (x | w_i) dx.

Se obtine relatia :

^>_< T X I { (4)

Pentru cazul cand c₁₂-c₁₁=c₂₁-c₂₂ (ex. cazul particular c₁₁=c₂₂=0 si c₁₂=c₂₁) din relatia de calcul al algoritmului de risc minim (4) se obtine relatia algoritmului Bayes cu eroare minima de clasificare (2).

Daca in membrul stang al ecuatiilor (1) si (4) apare o situatie de egalitate nu se poate trage nici o concluzie. In consecinta se poate atribui forma uneia dintre clase, sau se rafineaza testul prin adaugarea de noi caracteristici, sau se aplica alt algoritm.

Odata ce clasificatorul a fost proiectat si antrenat, in situatia in care densitatile de probabilitate conditionate ale vectorilor caracteristicilor selectate sunt cunoscute pentru fiecare clasa sau pot fi estimate precis dintr-un set de esantioane (set de antrenare), se aplica regula de clasificare Bayes, care minimizeaza probabilitatile de recunoastere eronata sau riscul mediu. In situatia, mai des intalnita, cand acestea nu sunt cunoscute se utilizeaza fie functiile discriminant, fie metode neparametrice de clasificare.

II. Clasificare Bayes pentru M clase (M>2)

Pentru M (M > 2) clase de forme din spatiul Rⁿ , notate w w_M, o forma noua de intrare X (vector aleator n-dimensional de caracteristici) poate fi clasificata prin :

a)      compararea probabilitatilor aposteriori dupa regula de forma :

P ( w_i | X ) ^>_< P ( w_j | X ) => X I{, pentru j j (5)

ceea ce e echivalent cu

P ( w_i ) f (x | w_i ^>_< P ( w_j ) f( x | w_j) => X I{, pentru j j (6)

unde :

i, j =1.M, cu M > 2

P ( w_i | X ) este probabilitatea aposteriori (probabilitatea ca dupa ce X a fost clasificat, forma X sa apartina clasei w_i

P ( w_i ), P ( w_j ) este probabilitatea apriori a clasei w_i (respectiv w_j) (probabilitatea ca o forma sa apartina clasei w_i, respectiv w_j

b) decizie bazata pe minimizarea riscului (costului mediu) pentru M clase

Pentru calculul riscului avem expresia :

r = c_ij P( w_i ) f (x | w_i) dx (7)

unde :

R_i sunt regiunile din spatiul Rⁿ corespunzand claselor w_i, pentru 2 i .M

iar cij este costul deciziei eronate X I w_j cand clasa adevarata este w_i

Algoritmul Bayes de risc minim poate fi scris pentru cazul a M clase de forme:

c_ij P( w_i ) f (x | w_i) < c_ik P( w_i ) f (x | w_i
pentru k j T X Iw_j, i,j,k .M (8)

In cazul particular c_ii = 0 si c_ij=1 pentru i j algoritmul capata forma de la punctul (a)

Covrola Corolar : In ipoteza ca f ( x | wi ) si f ( x | wj ) sunt densitati normale cu vectorii medie mi si mj, si matricile de covarianta Si si Sj se poate scrie relatia echivalenta: (x - mi)T Si (x - mi)T - (x - mj)T Sj (x - mj)T + + ln >< 2 ln , T X I wi (9) r : In ipoteza ca f ( x | wi ) si f ( x | wj ) sunt densitati normale cu vectorii medie mi si mj, si matricile de covarianta Si si Sj se poate scrie relatia echivalenta: (x - mi)T Si (x - mi)T - (x - mj)T Sj (x - mj)T + + ln >< 2 ln , T X I wi (9)

Clasificatori si functii discriminant

Pentru cazul a M clase de forme din spatiul Rⁿ (M > 2), notate w w_M, se considera cunoscute probabilitatile apriori P ( w_i ) si densitatile conditionate f (x | w_i  i   M.

Proiectarea unui clasificator presupune calcularea explicita a unui set de M functii discriminant si selectarea clasei care corespunde maximului g_k::

g_k : Rⁿ R, 1 k M, astfel ca g_i (X) > g_j (X), pentru j j (9)

Cand inegalitatea din ecuatia (8) nu este stricta se ajunge la ambiguitatea deciziei, caz in care clasificarea nu poate fi decisa. Solutia: fie se alege oricare din cele doua clase w_i, w_j fie se alege un algoritm mai puternic.

Ex: Se poate alege setul de functii discriminant de forma:

Functii discriminant de tip Bayes pentru vectori de caracteristici repartizati normal

Pentru forme X de intrare din spatiul Rⁿ cu densitati conditionate normale de forma :

f ( x, w_i ) N (m_i S_i i M

Luam in considerare un clasificator Bayes cu eroare minima de clasificare pentru M clase, cu functiile discriminant :

g_k (x) = ln P (w_k) + ln f (x | w_k ), pentru 1 k M

se obtine pentru vectori repartizati normal relatia:

selectarea clasei corespunzand lui g_k:

Cazuri particulare:

a) Pentru = s I_n (componente vectorilor X sunt independente avand dispersia s ) se obtine relatia:

g_k (x) = - || x - m_k||² + ln P(w_k k M (11)

b) Pentru clase echiprobabile P(w_k) = 1/M atunci functiile discriminant sunt

g_k (x) = || x - m_k (12)

Clasificator utilizand cele mai apropiate esantioane (algoritmul K-NN - "the k^th Nearest Neighbour") in ipoteza binara, aceasta regula de clasificare este simplu de aplicat si consta in a acorda lui x clasa care este cel mai frecvent reprezentata printre cele k esantioane mai apropiate (pe baza distantei euclidiene) de x (se alege k impar). Dezavantajul ei consta in nevoia de a stoca toate esantioanele si de a le compara pe fiecare cu un esantion necunoscut.

Pentru k = 1 se obtine regula de clasificare pe baza celui mai apropiat esantion (The Nearest Neighbour): se aloca lui x clasa w sau w careia ii apartine cel mai apropiat din esantioanele x₁, x₂, . x_N stocate in memorie. Pentru M > 2 clasa de apartenenta a lui x este stabilita de asemenea de clasa de apartenenta a celui mai apropiat vecin.

g_k (x)={d² (x_F, x)} (13)

unde x_F - tot lotul cunoscut si repartizat pe clase, x - forma de clasificat.

Selectarea clasei se face prin .

Clasificatorul bazat pe cel mai apropiat prototip. Se construieste cate un prototip pentru fiecare clasa cate un prototip prin medierea tuturor formelor deja cunoscute, apartinand acelei clase. Pentru o forma F reprezentata prin vectorul X_F de caracteristici se calculeaza distantele dintre X_F si vectorii medie ai claselor, distanta minima stabilind clasa de apartenenta (comparare este de tip template-matching cand vectorul medie este prototipul clasei sale):

min d² (x_F, m_k) =|| x - m_k||²=g_k (x)= d² (x_F, m_i0 T X Iw_i0 (14)

Clasificatorul liniar are setul de functii discriminant:

unde w_k = m_k, si w_k0 = -m_k^T m_k+ ln P(w_k), pentru 1 k M

Problema : Fie patru clase de semnale bidimensionale X= repartizate normal.

clasa w {A₁=, B₁=, C₁=, D₁=},

clasa w {A₂=, B₂=, C₂=, D₂=},

clasa w {A₃=, B₃=, C₃=, D₃=},

clasa w {A₄=, B₄=, C₄=, D₄=}.

Se cere:

a) Calculati probabilitatile apriori (P(w ) , P(w ) , P(w ) , P(w )), vectorii medie (m m m m ) si matricele de covariatie (S S S S

b) Ecuatia suprafetei de separatie

c) Reprezentarea grafica

d) Regula de decizie

e) Sa se clasifice vectorii : J₁=, J₂=, J₃=, J₄= folosind

functiile discriminant de tip Bayes;

cel mai apropiat vecin;

cel mai apropiat prototip.

Laborator

In fisierul C: wine.names se afla descrierea unui set de date care reprezinta trei clase de vinuri. Prima clasa este formata din 59 de vectori de caracteristici, a II^-a din 71 de vectori, iar ultima clasa contine 48 de vectori. In fisierul C: wine.data sunt prezentati toti acesti vectori, avand la inceput indexul clasei de apartenenta. Astfel, fiecare vector are 15 caracteristici.

Se introduc manual datele vinurilor in Matlab (excluzand indexul clasei), astfel incat 98 de vectori sa fie utilizati ca vectori de antrenare (vectori cunoscuti apriori) si 80 de vectori utilizati in testare. Vectorii vor fi alesi in ordinea prezentata in fisier, mai intai vectorii de antrenare si apoi vectorii de test, impartirea vectorilor in lot de antrenare si test este data la fata locului. Fiecare vector astfel introdus va reprezenta o linie in matricea de antrenare respectiv in cea de test. Fisierul C:wine.doc contine datele asezate astfel incat sa fie copiate cu usurinta in Matlab.

Se clasifica apoi vectorii de test, pe baza vectorilor de antrenare cu ajutorul algoritmului Bayes, apoi prin algoritmul Nearest Neighbour si prin Nearest Prototipe, notandu-se rezultatele.

Anexa

Pentru a atribui valori unei matrice in Matlab, se utilizeaza spatii pentru separarea elementelor aceleiasi linii si ; pentru separarea liniilor. De exemplu pentru a scrie matricea se utilizeaza linia A = [1 2 3;4 5 6;7 8 9].

Avand un vector V, pentru a alege toate elementele cu indexul cuprins in intervalul [a;b] se utilizeaza selectia V(a:b). In cazul unei matrice X(a:b,c:d) alege toate liniile avand indexul in intervalul [a;b] si toate coloanele avand indexul in intervalul [c;d] (a < b si c < d). O atribuire ar duce la o matrice cu
b - a + 1 linii si c - d + 1 coloane. Prin folosirea sintaxei X(a:b,:) se aleg toate liniile cu indexul in intervalul [a;b] si toate coloanele matricei X.

Mai departe, toate cuvintele scrise cu rosu in cadrul unei linii de comanda in Matlab reprezinta variabile.

Functia np implementeaza algoritmul de recunoastere cel mai apropiat prototip:

[clt,cla] = np(x,xt,cl,nrva,nrvt);

unde x - matricea vectorilor de antrenare, vectori asezati pe liniile matricei pe baza carora se construiesc prototipurile claselor, xt - matricea vectorilor de test, asezati pe liniile matricei, cl - numarul claselor, nrva/nrvt - reprezinta un vector care contine numarul vectorilor din fiecare clasa in matricea de antrenare/test (implicit numarul vectorilor pe fiecare clasa este acelasi, deci, in cazul de fata, acesti parametrii sunt ignorati); clt/cla - matricele de confuzie pentru lotul de test/antrenare. Rata de recunoastere corecta va fi afisata pe ecran dupa fiecare rulare.

Functia nn implementeaza algoritmul de recunoastere cel mai apropiat vecin:

clt = nn(x,xt,cl,nrva,nrvt);

unde x - matricea vectorilor de antrenare, vectori asezati pe liniile matricei pe baza carora se construiesc prototipurile claselor, xt - matricea vectorilor de test, asezati pe liniile matricei, cl - numarul claselor, nrva/nrvt - reprezinta un vector care contine numarul vectorilor din fiecare clasa in matricea de antrenare/test (implicit numarul vectorilor pe fiecare clasa este acelasi, deci, in cazul de fata, acesti parametrii sunt ignorati); clt - matricea de confuzie pentru lotul de test. Rata de recunoastere corecta va fi afisata pe ecran dupa fiecare rulare.

Functia bayes implementeaza functiile discriminant de tip Bayes, facand concomitent si clasificarea corespunzatoare:

[cla,clt] = bayes(x,xt,cl,nrva,nrvt);

unde x - matricea vectorilor de antrenare, vectori asezati pe liniile matricei pe baza carora se construiesc prototipurile claselor, xt - matricea vectorilor de test, asezati pe liniile matricei, cl - numarul claselor, nrva/nrvt - reprezinta un vector care contine numarul vectorilor din fiecare clasa in matricea de antrenare/test (implicit numarul vectorilor pe fiecare clasa este acelasi, deci, in cazul de fata, acesti parametrii sunt ignorati); clt/cla - matricele de confuzie pentru lotul de test/antrenare. Rata de recunoastere corecta va fi afisata pe ecran dupa fiecare rulare.