3. faze de lucru în recunoaşterea de pattern-uri...temporare (semnal vocal, eeg etc.). În...

3. Faze de lucru în recunoaşterea de pattern-uri În problemele de recunoaştere de pattern-uri putem împărţi problema

recunoaşterii în mai multe faze de lucru. În funcţie de opţiunea programatorului, aceea de a introduce sau nu clusterizarea ca un pas premergător fazei de clasificare propriuzise întâlnim în practică următoarele două situaţii (vezi şi Figura 3.1):

Faza 1: achiziţia de date, Faza 2: preprocesare şi/sau procesare, Faza 3: extragere de trăsături şi Faza 4: clasificare.

sau Faza 1: achiziţie de date, Faza 2: preprocesare şi/sau procesare, Faza 3: extragere de trăsături, Faza 4: clusterizare şi Faza 5: clasificare.

Figura 3.1. Scheme bloc ale unui sistem de recunoaştere de trăsături

În continuare vom prezenta fiecare dintre blocurile/fazele de lucru

introduse anterior.

Spaţiul trăsăturilor

Spaţiul trăsăturilor Spaţiul

pattern-uri de intrare

Bloc achiziţie

date

Preprocesare şi/sau

procesare

Bloc extragere trăsături

Bloc de clasificare

Bloc achiziţie

date

Bloc clusterizare

Preprocesare şi/sau

procesare

Bloc extragere trăsături

Bloc de clasificare

Spaţiul pattern-uri de intrare

Algoritmi şi metode inteligente cu aplicaţii în electronică şi biomedicină, vol I

6

3.1. Blocul de achiziţie a datelor

În ceea ce priveşte achiziţia datelor, informaţiile despre lumea înconjurătoare, starea utilizatorului unui sistem sau diferite informaţii conţinute în rezultatul diferitelor tehnici investigative (imagistice sau de altă natură) sunt de obicei culese cu ajutorul unui senzor şi convertite apoi în format digital. Informaţia analogică este convertită într-un set de date cu ajutorul unor senzori optici (CCD camera, scanner, fibre optice), acustici (microfon), de mişcare (piezorezistiv, inductiv, laser, capacitivi etc.) sau de potenţial (electrozi de suprafaţă pentru semnale de tipul: EEG, ECG sau EMG) etc. Datele astfel achiziţionate sunt apoi fie stocate în vederea prelucrării lor ulterioare (aşa zisa prelucrare offline) fie sunt prelucrate direct, caz în care vorbim de prelucrare online sau în timp real a setului de date.

Sintetizând putem spune că în urma procesului de achiziţie vor rezulta o serie de pattern-uri care pot fi: spaţiale (amprente, semnături, feţe etc.) sau temporare (semnal vocal, EEG etc.).

În accepţiune acestui curs printr-un pattern sau formă înţelegem un set de date (caracterizat de o anumită structură şi de anumiţi parametri) ce poartă o anumită simbolistică sau o anumită semnificaţie.

3.2. Blocul de preprocesare/procesare

În cadrul etapei de preprocesare/procesare se urmăresc o serie de deziderate după cum urmează: eliminarea diferitelor semnale perturbatoare (brumul de reţea, zgomote etc.), eliminarea artefactelor (prin intermediul tehnicilor de filtrare sau prin utilizarea metodelor adaptive), amplificarea semnalului, posibile mecanisme de combinare a informaţiilor diferitelor semnale în unul rezultant (tehnici de tipul data fusion), reducerea dimensionalităţii spaţiului de intrare etc. Scopul acestor blocuri fiind acela de a susţine şi uşura activitatea următoarelor blocuri de prelucrare şi clasificare a informaţiilor. În multe lucrări de specialitate în cadrul blocului de preprocesare/procesare sunt introduşi şi algoritmii de extragere a trăsăturilor. În cadrul acestei cărţi ei vor fi consideraţi ca un bloc de sine stătător în principal datorită rolului conceptual diferit al acestor tehnici de prelucrare.

Ca o observaţie suplimentară vom mai spune că uneori parte din aceste

Faze de lucru în recunoaşterea de pattern-uri

7

tehnici numite de preprocesare sunt, din construcţie, incluse chiar în blocul de achiziţie a datelor (la nivelul senzorilor). Astfel de situaţii întâlnim de exemplu atunci când semnalul dat de un anumit traductor este de amplitudine mică şi foarte mică şi este astfel foarte susceptibil la contaminarea cu diferite zgomote. Într-o astfel de situaţie se preferă amplificarea lui locală şi abia ulterior trimiterea către următoarele blocuri ale sistemului.

3.3. Blocul de extragere a trăsăturilor

Pentru a înţelege mai bine rolul funcţional al acestui bloc de lucru vom prezenta în continuare un exemplu ilustrativ. Să presupunem că lucrăm cu pattern-uri (forme) vizuale care reprezintă cele 10 de cifre arabe (în particular aceasta poate fi o problemă dedicată recunoaşterii scrisului de mână). În acest caz recunoaşterea de pattern-uri se limitează la asignarea unui astfel de pattern de intrare al unei cifre la una dintre cele 10 clase reprezentate de cifrele alfabetului.

Etapele intermediare de digitizare a intrării şi izolare a câte unui singur caracter le considerăm în acest punct al discuţiei ca fiind rezolvate, caz în care avem pentru clasificare o mulţime de matrici specifice ce conţin diferite valori ale luminozităţii pentru fiecare cifră singulară în parte. Pentru clasificare vom alge cea mai la îndemână metodă, şi anume vom compara intrarea sistemului cu un pattern standard care aparţine fiecărei clase, în final urmând a selecta acea clasă pentru care potrivirea între pattern-ul de intrare şi cel reprezentativ clasei este maximă. Acest gen de abordare nu este însă unul lipsit de probleme. Problemele fundamentale asociate acestei abordări ţin pe de o parte de informaţiile care se compară şi, pe de altă parte, de modul în care se măsoară gradul de similaritate între cele două pattern-uri comparate.

1234567890

123567890

Figura 3.2. Variabilitatea caracterelor funcţie de tipul fontul folosit pentru o dimensiune constantă a tipului de font

Ceea ce face ca majoritatea problemelor de recunoaştere de pattern-uri să

fie considerate a fi foarte dificile ţine, în principal, de gradul mare de


8

variabilitate al exemplarelor care aparţin aceleiaşi clase comparativ cu diferenţele relativ reduse care există între clase diferite.

Pentru rezolvarea acestei probleme trebuie găsite acele proprietăţi specifice sau trăsături ale paternului/obiectului/evenimentului/stării/undei etc. care să ne dea o descriere cât mai completă şi unică a acestuia. În această idee, pentru exemplul nostru de clasificare a celor 10 cifre s-ar putea dovedi utile: aria, perimetrul caracterului, gradul de compactare (dat de raportul între aria la pătrat şi perimetru), gradul de simetrie (faţă de axa orizontală sau verticală sau de una din diagonale) etc. Ceea ce este important este tocmai faptul că parte din aceste trăsături pot fi foarte sensibile chiar la mici diferenţe care ar exista între pattern-uri, lucru ce ne-ar facilita diferenţierea. De exemplu, pentru a distinge între cele două incon-uri emoţionale prezentate în Figura 3.3 o posibilă trăsătură ce poate fi utilizată cu succes este distanţa între mijlocul ochiului şi capătul gurii.

Figura 3.3. Posibil mod de selecţie a unei trăsături, distanţa d, pentru distincţia între cele două imagini

Alegerea trăsăturilor este una specifică problemei pe care dorim să o

rezolvăm. Totodată din larga practică în domeniu s-a observat că alegerea unui set reprezentativ de trăsături este mai mult o artă decât o ştiinţă, ea bazându-se foarte mult pe experienţa aceluia care construieşte sistemul global de clasificare.

Numărul de trăsături extrase din informaţia brută, de intrare, este dictat de gradul de complexitate al problemei de clasificare dar şi de puterea de discriminare a acestor trăsături. În general vorbim de două sau mai multe trăsături utilizate la intrarea clasificatorului. În această situaţie este necesar să înţelegem modul cum putem construi, pe baza acestor trăsături, setul de date de intrare a clasificatorului şi cum interpretăm aceste date în spaţiul trăsăturilor.

Să presupunem că pentru un pattern de intrare am selectat un număr d de trăsături ce îl caracterizează în mod unic. În cazul clasificării literelor alfabetului aceste trăsături pot fi:

x1 = aria x2 = perimetrul

d1 d2


9

x3 = gradul de simetrie al caracterului

... xd = gradul de curbură a părţii inferioare a caracterului

În acest caz particular mulţimea trăsăturilor poate fi grupată într-un vector de trăsături de tip coloana, x, d dimensional.

Ca interpretare, putem să ne gândim că vectorul x0 este de fapt un punct în spaţiul d dimensional al trăsăturilor. În concluzie putem afirma că orice proces, stare sau eveniment poate fi reprezentat în final ca un punct în spaţiul trăsăturilor; spunem spaţiul trăsăturilor deoarece vectorii ce determină acest spaţiu sunt daţi de chiar diferitele trăsături specifice ce sunt utilizate în clasificare. În acest mod diferite intrări (pattern-uri) în blocul de extragere a trăsăturilor vor produce vectori de trăsături diferiţi şi putem doar să sperăm că variabilitatea în interiorul unei clase va fi mai mică decât variabilitatea dintre două clase, astfel încât “punctele” care reprezintă pattern-uri din aceeaşi clasă (şi care se vor grupa într-o anumită zonă a spaţiului de trăsături) să poată fi uşor separate.

Figura 3.4. Spaţiul trăsăturilor şi o realizare particulară a vectorului x (pentru cazul d = 3)

În practică adesea alegerea trăsăturilor este făcută în mod intuitiv, fără ca cel care dezvoltă sistemul de clasificare să dispună de o metodă riguroasă de selecţie a lor. Mai mult, pentru a optimiza soluţia implementată de multe ori se preferă fie compactarea acestor trăsături (pentru a reduce dimensionalitatea spaţiului de intrare, care este indicat să nu fie foarte mare), fie se recurge la o selecţie doar a acelor trăsături care sunt cu adevărat purtătoare de informaţie utilă în procedura de clasificare considerată. Printre metodele de compactare mai utilizate amintim analiza de tip PCA (Principal Component Analysis) [Duda, 2001], [Muhammad, 2005], [Anke, 2003], ICA (Independent Component Analysis) [Muhammad, 2005], LDA (Linear Discriminant Analysis), [Muhammad, 2005] etc., în

Spațiul trăsăturilor:

curburagrad

perimetru

arie

x

x

x

x

d

2

1

O realizare a vectorului x:

0

02

01

0

dx

x

x

x

x0

x10

x20

x30

x1

x2

x3


10

timp ce selectarea trăsăturilor cu adevărat importante se face fie empiric (prin verificări repetate a diferitelor combinaţii de trăsături), fie printr-o prelucrare automată generată de teoria clasificatorului Bayes-ian (metodă prezentată în subcapitolul 5.3.4.) sau, de exemplu, utilizând o metodă relativ nouă şi mai elegantă bazată pe algoritmii genetici [Dobrea, 2009].

În cadrul acestui volum vom presupune că cel care a proiectat blocul de extragere a trăsăturilor a selectat în mod corespunzător trăsăturile astfel încât acestea să conţină toate informaţiile necesare pentru a separa pattern-urile în clase. Pornind de la acest set de trăsături, în continuare vor fi prezentate metode de proiectare a clasificatorului şi, respectiv, a blocului de clusterizare.

3.4. Clusterizarea În situaţia în care problema de clasificare pe care dorim să o rezolvăm

posedă în mod natural subcategorii putem îmbunătăţi acurateţea procesului de recunoaştere de pattern-uri prin găsirea mai întâi a acestor subcategorii (clusteri) urmând ca ulterior algoritmul să fie continuat cu un clasificator. Astfel, procesul de clasificare este realizat prin spargerea problemei în două etape: obţinerea subcategoriilor urmată apoi de o clasificare finală.

Este important de sesizat care este diferenţa dintre clusterizare şi clasificare.

Figura 3.5. (a) Datele de intrare, (b) clusterizarea, (c) clasificarea propriuzisă

(a) (b) (c)

Cluster 1 Cluster 2

Cluster 3 Cluster 4 Cluster 5

Clasa 1

Clasa 2

1 2


11

Clusterizarea este procesul nesupervizat de grupare a punctelor din spaţiul trăsăturilor, puncte care sunt spaţial vecine.

Clasificarea este procesul de etichetare, deci supervizat, de împărțire a punctelor din spaţiul trăsăturilor conform unui criteriu extern.

Deosebirea fundamentală este dată astfel de faptul că clusterizarea este un proces nesupervizat de grupare în timp ce clasificarea este unul supervizat. În plus, întrucât procedurile de clusterizare sunt nesupervizate ele nu pot fi utilizate direct pentru clasificare.

În Figura 3.5 este prezentat un exemplu de clusterizare urmat de un proces de clasificare. Se pot observa 5 clusteri diferiţi de date şi două clase. Deoarece clusterii sunt determinaţi numai de modul natural de grupare a setului de date de intrare în spaţiul trăsăturilor atunci vom avea mai multe combinaţii posibile de clusteri care să genereze cele două clase. În cazul nostru clusterii 1 şi 4 pot fi consideraţi drept elementele care generează clasa 1, dar la fel de bine datele de intrare pot fi grupate şi în alte moduri posibile.

Figura 3.6. Prototipurile (mediile) claselor prezentate Figura 3.5

În unele aplicaţii practice datele aparţinând unei clase sunt dense şi foarte bine delimitate, de exemplu dacă în exemplul din Figura 3.5 fiecare cluster ar reprezenta o clasă distinctă. Într-o asemenea situaţie clusterizarea anterioară a setului de date nu mai este necesară. Clasificare realizându-se foarte simplu prin determinarea distanţei dintre elementul necunoscut şi prototipul fiecărei clasei (vectorul mediu al clasei respective). În final alegându-se clasa de apartenenţă a elementului necunoscut pentru care această distanţă este minimă.

În alte situaţii, clasele nu sunt omogene, ele fiind adesea compuse dintr-un număr distinct de subclase, vezi Figura 3.5(c). În astfel de situaţii clusterizarea poate fi utilă, ea reprezentând un preprocesor pentru

Prototip clasă 1

Prototip clasă 2

Clasa 1

Clasa 2 x1

x2


12

clasificare. De exemplu, dacă clusterii din Figura 3.5(b) ar fi fost utilizaţi ca intrare pentru un clasificator, pentru acesta din urmă, procesul de clasificare ar fi foarte simplu (toate elementele din clusterii 1 şi 4 ar fi asignate clasei 1, în timp ce restul elementelor aparţinând celorlalţi clusteri vor fi atribuite clasei 2), câştigul rezultat fiind dat în acest caz de simplitatea clasificatorului.

Pentru a înţelege mai bine conceptele prezentate anterior vom considera că spaţiul trăsăturilor este unul bidimensional, similar cu cel prezentat în Figura 3.5, această particularizare a analizei la un spaţiu bidimensional nu va afecta în nici un fel gradul de generalitate a afirmaţiilor de mai jos. Din Figura 3.6 se poate observa că prin medierea vectorilor de trăsături aferenţi fiecărei clase obţinem câte un element prototip pentru fiecare clasă. Din exemplul prezentat se poate observa de asemenea şi faptul că prototipul clasei poate foarte bine să nu aparţină nici unuia dintre clusterii claselor respective. În proiectarea clasificatorului se va ţine cont de toate cele 2, respectiv 3 subcategorii ale celor 2 clase şi vom spune că intrarea aparţine clasei 1, de exemplu, nu dacă distanţa de la elementul necunoscut la prototipul clasei este minimă, ci dacă elementul necunoscut aparţine uneia din clusterii 1 sau 4, sau va aparţine clasei 2 dacă elementul necunoscut aparţine unuia din clusterii 2, 3 sau 5.

În cazul cel mai general în care o clasă cunoscută conţine k subclase, vom proiecta un clasificator care va conţine două etaje. Primul etaj asignează vectorul de trăsături x unei subclase şi apoi funcţie de subclasa în care se găseşte elementul necunoscut cel de al doilea etaj va furniza rezultatul final.

3.5. Clasificarea

3.5.1. Introducere

Pentru a prezenta particularităţile şi problemele care apar în încercarea de a clasifica un set de date vom lua un exemplu foarte simplu. Să presupunem că activitatea cardiacă a unui subiect (cuantizată prin pulsul acestuia) este utilizată ca un indicator a stării de oboseală fizică a acestuia. Experienţa ne arată ca în momentul în care organismul este odihnit, acesta reglează numărul de bătăi pe minut a inimii în jurul valorii de 65. În cazul unei activităţi motorii intense subiectul oboseşte iar activitatea cardiacă creşte pentru a suplini necesarul de oxigen şi elemente nutritive consumate de această activitate motorie. Orice măsurătoare a activităţii cardiace se


13

consideră ca un punct în spaţiul de intrare (spaţiul pattern-urilor), care în acest caz particular corespunde şi cu spaţiul trăsăturilor fiind astfel un spaţiu monodimensional. În cazul reprezentării pe o linie a pulsului măsurată pentru un singur subiect se poate verifica că de obicei valori mai mici de 90 bătăi per minut corespund persoanelor sănătoase și odihnite (deci a primei clase), iar o activitate cardiacă de valori mai ridicate corespunde unor subiecţi ce desfăşoară sau au desfăşurat o activitate fizică susţinută (deci celei de a doua clase a subiecţilor obosiţi), vezi Figura 3.7. Această distribuţie de valori ale activităţii cardiace, a pulsului, determină apariţia claselor sau categoriilor în spaţiul pattern-urilor.

Figura 3.7. Graficul pulsului pentru două clase de indivizi odihniţi şi obosiţi

Dacă în limbajul comun prin clasificare se înţelege „distribuire, repartizare sistematică pe clase1 sau într-o anumită ordine” [Academia Română, 1998], în limbaj matematic clasificarea (implementată cu ajutorul unui sistem numit clasificator) s-ar traduce prin existenţa unei funcţii de la un spaţiu (discret sau continuu) al trăsăturilor, X, la un set discret de etichete (label-uri), Y, ataşate claselor corespunzătoare. Practic, se obţine o partiţionare a spaţiului trăsăturilor, X, în „k” regiuni (clase) disjuncte, notate {ci}i=1,…,k şi care îndeplinesc condiţiile:

Fccc

Xccc

k

k

...

...

21

21 (3.1)

În relaţia (3.1) F este mulţimea punctelor care alcătuiesc frontierele, graniţele dintre aceste clase.

Revenind la exemplul anterior, un mod natural de a realiza asignările la

1 Clasă, conform dicţionarului explicativ al limbii române, reprezintă un “grup (mare) de obiecte, de elemente, de fiinţe, de fenomene care au însuşiri comune” [Academia Română, 1998].

55 70 85 100 115 130 145 160

Pulsul [bătăi/min.]

Imediat după o activitate fizică

susţinută – subiectul obosit

Măsurători realizate pentru o activitate

de birou – subiectul odihnit

Clasa 1 Clasa 2

Frontiera, graniţa – suprafaţa de decizie


14

cele două clase este acela de a defini o graniţă sau o frontieră, o valoare a pulsului, sub care subiectul este odihnit iar peste care este obosit. Această graniţă sau frontieră în teoria sistemelor de clasificare este denumită suprafaţă de decizie.

3.5.2. Funcţii discriminant

O schemă bloc a unui posibil clasificator care are C clase de ieşire este prezentată în Figura 3.8. Fiecare funcţie gi(x), Ci ,1 , atribuie în urma evaluării câte un “scor” fiecărui element din spaţiul trăsăturilor. Aceste funcţii poartă numele de funcţii discriminant, fiecare clasă are o astfel de funcţie, rolul ei fiind acela de a furniza valori maxime pentru vectorii de trăsături care aparţin clasei respective şi valori cât mai mici pentru vectorii de trăsături ce aparţin celorlalte claselor.

Figura 3.8. Schemă bloc generală a unui clasificator

Ca o regulă generală, vom avea tot atâtea funcţii discriminant gi(x), Ci ,1 , rezultate din însăşi construcţia clasificatorului, câte clase de ieşire

are acesta. La intrare clasificatorului se aplică exemplarele xk = [ x1k, x2

k, ..., xd

k ]T ce urmează a fi clasificate (vectorii de trăsături), d reprezentând dimensiunea spaţiului de trăsături iar k numărul curent al exemplarului aparţinând setului de date de intrare.

În spaţiul trăsăturilor aceste funcţii discriminant creează anumite regiuni spaţiale decizionale în care toate elementele ce se regăsesc în aceste regiuni sunt asociate unei anumite clase. Fiecare regiune decizională este caracterizată matematic de o relaţie dată de:

g1(x)

g2(x)

gi(x)

gC(x)

Valoarea maxima

xk apartine clasei ipentru care gi(x)

este maxim

x1k

x2k

xdk


15

CiijxgxgxR jii ,1,,: (3.2)

Regiunile decizionale definite conform relaţiei (3.2) sunt separate între ele prin anumite frontiere ce poartă numele de suprafeţe de decizie. Pentru două regiuni alăturate Ri şi Rj suprafaţa de decizie ce le separă este dată de:

xgxg ji (3.3)

Figura 3.9. Funcţiile discriminant şi suprafaţa de decizie pentru un caz particular d = 2 şi C = 2

Deci, funcţiile discriminant se intersectează în spaţiul de intrare

determinând suprafeţele de decizie. Punctele situate pe suprafaţa de decizie obţin scoruri egale date de către funcţiile discriminant generatoare a suprafeţei de decizie respective (vezi Figura 3.9). În concluzie, suprafeţele de decizie împart spaţiul de intrare (al trăsăturilor) în regiuni. În aceste regiuni unul dintre discriminanţi (funcţia de discriminare) asociat regiunii respective are valoare mai mare decât toate celelalte funcţii discriminant. Fiecare regiune din spaţiul de intrare este apoi atribuită clasei ce are valoarea de ieşire a funcţiei discriminant corespondente de valoare maximă.

Suprafeţele de decizie vor determina separarea pattern-urilor aparţinând diferitelor clase, iar pattern-urile din aceeaşi clasă se vor grupa împreună în

Funcţia discriminant pentru prima clasă

g1(x1, x2)

g1(x1, x2) g2(x1, x2)

Funcţia discriminant pentru cea de a doua

clasă g2(x1, x2)

x1

x2

Prima clasă g1(x1, x2) > g2(x1, x2)

Cea de a doua clasă g1(x1, x2) < g2(x1, x2)

Suprafaţa de decizie g1(x1, x2) = g2(x1, x2)

g1 = g2


16

diferite regiuni ale spaţiului de intrare. În această situaţie distanţa dintre pattern-uri, dată de o metrică, poate fi utilizată ca o măsură a similarităţii între pattern-uri în spaţiul trăsăturilor.

(a) (b) (c) (d)

Figura 3.10. Tipuri de suprafeţe de decizie: (a) liniară, (b) liniară pe porţiuni, (c) cuadratică, (d) polinomială

3.5.3. Suprafaţa de decizie

Găsirea suprafeţei de decizie nu este o problemă trivială în multe aplicaţii. În cazul măsurării pulsului subiecţilor odihniţi/obosiţi vom observa că pulsul variază funcţie de subiect şi pentru acelaşi subiect vom avea valori diferite funcţie de ora zilei, starea intelectuală a acestuia (odihnit/obosit), starea emoţională etc. Aceeaşi variabilitate apare şi pentru indivizii bolnavi (de exemplu funcţie de gradul şi tipul afecţiunii) şi, mai mult, se observă o suprapunere între valorile pulsului subiecţilor odihniți şi ale celor obosiți. În concluzie, observăm că problema centrală în recunoaşterea de pattern-uri din punctul de vedere al clasificatorului este de a:

defini forma, vezi Figura 3.10, numărul, vezi Figura 3.10, şi locul de plasare a suprafeţei respectiv, acolo unde este cazul, a

suprafeţelor de decizie

astfel încât eroarea de clasificare să fie minimizată. Suprafeţele de decizie sunt definite ca o graniţă sau suprafaţă în spaţiul d-

dimensional al trăsăturilor de intrare. Forma suprafeţelor este de tip hiperplan, în cele mai simple situații, și sunt (d - 1) dimensionale. Când, de exemplu d = 1 suprafaţa de decizie este un punct ca în exemplul anterior (în care căutam să clasificăm o persoană funcţie de valoarea pulsului pe care o are în cele două clase) sau, de exemplu, pentru d = 2 (pentru un spaţiu de trăsături bidimensional, Figura 3.9) suprafaţa de decizie este o dreaptă.


17

Problema care se ridică acum este dată de întrebarea relativ firească: cum obţinem suprafaţa sau suprafeţele de decizie? Răspunsul la această întrebare îl vom afla în cele ce urmează.

3.5.4. Metrica O aplicaţie |||| : T R+ (T spațiul trăsăturilor, R+ este mulțimea

numerelor real pozitive ce include şi elementul zero) care satisface proprietăţile:

||x|| 0, ||x|| = 0 x = 0; (3.4)

||ax|| = |a| ||x||; x T, a R; (3.5)

||x+y|| ||x|| + ||y||, x, y T; (3.6)

se numeşte normă. Norma generează, dar şi generalizează, noţiunea de lungime sau distanţă

din spaţiul Euclidian. Norma permite compararea a două sau mai multe elemente din spaţiul T

din punct de vedere al “lungimii” lor. Importanţa deosebită a normei constă în faptul că ea induce o metrică prin relaţia:

d(x, y) = || x – y ||, x, y T (3.7)

Adică norma diferenței a două elemente dintr-un spaţiu linear normat este o metrică, spaţiul respectiv devenind spaţiu metric cu metrica indusă de normă.

Sunt mai multe moduri de a defini norma ||x||, acestea corespunzând diferitelor moduri de a măsura distanţa, deci diferitelor metrice. Patru dintre cele mai cunoscute şi uzuale sunt:

metrica Manhattan:

d(x, y) = || x – y ||, x, y T (3.8)

Cu ajutorul acestei metrice se construieşte şi criteriul L1 (pe care îl vom folosi ulterior în cadrul dat de clasificatorii neuronali) cunoscut şi sub numele de distanţă Hamming sau mai simplu norma L1.

metrica Euclidiană:

|| x || = ( x12 + x2

2 + … xd2 )1/2 (3.9)


18

Cunoscuta și sub numele de normă L2. metrica Minkovsi:

kkd

kkxxxx

/1

21 ...

(3.10)

Această metrică este o generalizare a celor două anterioare şi poartă numele de metrică Lk.

metrica Mahalanobis:

|| x || = xT· Cx·x (3.11)

În relația (3.11) Cx este matricea de covarianță a setului de date de intrare. Dacă spaţiul de intrare este d dimensional această matrice are o dimensionalitate d x d.

Figura 3.11. Contururile metricelor pentru diferite distanţe constante sunt prezentate astfel: (a). metrica Manhattan, (b). metrica Euclidiană,

(c). metrica Minkovsi, pentru k = 4, (d). metrica Mahalanobis. Contururile pentru distanţe constante date de fiecare tip de metrică

(Figura 3.11) vor fi:

pentru distanţe constante în cazul normei Manhattan sunt pătrate (cuburi sau hipercuburi);

pentru distanţe constante când se utilizează norma Euclidiană vor fi cercuri (sfere sau hipersfere – funcţie de dimensionalitatea spaţiului de intrare);

543210-1-2-3-4-5

5

4

3

2

1

0

-1

-2

-3

-4

-5

543210-1-2-3-4-5

5

4

3

2

1

0

-1

-2

-3

-4

-5

543210-1-2-3-4-5

5

4

3

2

10

-1

-2

-3

-4

-5

32.521.510.50-0.5-1-1.5-2-2.5-3

1

0.8

0.6

0.4

0.20

-0.2

-0.4

-0.6

-0.8

-1

(a). (b).

(c). (d).


19

în cazul metricii Minkovsi contururile vor fi sfere sau hipersfere turtite; iar pentru distanţe constante prin utilizarea normei Mahalanobis

contururile sunt elipse (sau elipsoizi). Orientarea spaţială a acestor elipsoizi va fi dată de matricea Cx, matrice ce caracterizează setul de date.

3. faze de lucru în recunoaşterea de pattern-uri...temporare (semnal vocal, eeg etc.). În...

Documents