1. Concepte fundamentale ale SRF

1.1. Ce este recunoaşterea formelor?

Prin recunoaşterea formelor se înţelege în mod obişnuit acel ansamblu de metode şi tehnici cu ajutorul căruia se poate realiza o clasificare în cadrul unei mulţimi de obiecte, procese sau fenomene. Setul de obiecte, procese sau fenomene care urmează a fi clasificate pot fi obiecte (fenomene) fizice sau structuri intelectuale, prin acestea înţelegând ansamblul concretizat de procese legate de o activitate intelectuală coerentă (scris, vorbit, etc)

Scopul recunoaşterii formelor constă în determinarea clasei din care face parte o colecţie de observabile. Metoda este deosebit de utilă atunci când abordarile directe sunt imposibile sau când inferenţele teoretice lipsesc.

Stabilirea numărului de clase în care se împart formele este o problemă particulară care depinde exclusiv de aplicaţiile concrete ale metodei.

1.2. Spaţiul formelor

Conceptul fundamental al teoriei recunoaşterii formelor este următorul: Un obiect sau un fenomen variabil, Xj, este descris (caracterizat) printr-un set de n

caracteristici xij (i=1,…,n). Toate aceste n caracteristici ale unui obiect formează o formă.Mulţimea x={Xj}j=1,m poartă denumirea de spaţiul formelor. Deci un obiect

(formă) X poate fi reprezentat printr-un punct X(x1,…,xn) în spaţiul formelor.O problemă este aceea a raportului dintre numărul de forme luate în considerare,

m, şi numărul de dimensiuni al spaţiului formelor, n, adică raportul m/n dintre numărul maxim de obiecte din setul respectiv, m, şi numărul de caracteristici, n, aferent fiecăruia dintre obiecte. Dacă numărul de forme, m, este mai mic, egal sau numai puţin mai mare decât numărul de caracteristici atunci discriminarea dintre forme şi atribuirea lor la diferitele clase posibile este un proces pur aleator.

În general, se consideră că acest raport m/n, pentru orice aplicaţie de recunoaşterea formelor, trebuie să îndeplinească următoarele condiţii:

(i)

(ii) , (1.1)

unde m reprezintă numărul de forme, iar n este numărul de caracteristici independente (număr de dimensiuni).

Condiţia (i) reprezintă minimum necesar pentru o clasificare binară, în timp ce condiţia (ii) este de dorit în aplicaţiile concrete ale tehnicilor de recunoaşterea formelor.

2. Caracteristicile unui SRF                    Translatorul                    Selectorul de caracteristici                    Clasificatorul

Un sistem de recunoaştere a formelor trebuie să asigure, corect şi eficient observarea, transformarea, prelucrarea preliminară (selectarea) şi clasificarea eşantionului de date.

Elementele esenţiale ale unui sistem general de recunoaşterea formelor sunt următoarele: translatorul, selectorul de caracteristici (care realizează o prelucrare preliminară) numit şi preprocesor, sau extractor de caracteristici şi clasificatorul (Fig. 1.4-1). Deşi aceste 3 subunităţi sunt interdependente, în cele ce urmează le vom prezenta separat.

Fig. 1.4-1 Sistem general de recunoaştere a formelor

1.2.1. Translatorul

Translatorul transformă şi transferă informaţiile din lumea reală în spaţiul formelor într-o formă compatibilă cu modul de reprezentare din calculatoarele electronice. În consecinţă datele primare, rezultat al observaţiei sunt transformate într-un şir de mărimi scalare care formează vectorul de formă n-dimensional. Fiecare componentă xi a vectorului de formă X reprezintă o cantitate fizică măsurabilă; este foarte important ca ea să surprindă esenţa datelor primare.

Modul de implementare al translatorului depinde exclusiv de natura datelor primare. Dacă acestea sunt constituite dintr-o succesiune de valori măsurate la intervale de timp, cum sunt traseele EEG, atunci sunt necesare procedee de eşantionare în timp, pe când dacă ele sunt funcţie de frecvenţă, cum sunt de exemplu spectrele în infraroşu ale compuşilor chimici, atunci trebuie dezvoltate procedeele de eşantionare a frecvenţei (respectiv numerelor de undă). În cazul imaginilor sunt luate în considerare suprafeţele mai luminoase sau mai întunecate, muchiile sau formele geometrice. Aceasta este o problemă ceva mai complicată şi, de aceea , au fost propuse o serie de metode pentru reducerea complexităţii imaginilor la un şir de măsurători.

O situaţie fericită, în care translatorul nu mai este necesar, apare atunci când informaţiile din lumea reală sunt exprimate numeric (de exemplu, în cazul spectrelor de masă).

Vectorii de formă dezvoltaţi de translator constituie mărimile de intrare pentru selectorul de caracteristici.

1.2.2. Selectorul de caracteristici

Scopul selectorului de caracteristici constă în prelucrarea vectorilor de formă în aşa fel încât procedeul de clasificare să fie optimizat.

Selectorul de caracteristici (denumit şi extractor de caracteristici sau preprocesor) acceptă ca mărimi de intrare vectorii de formă produşi de translator şi operează asupra lor transformându-i pentru a elimina sau, cel puţin, pentru a reduce cantitatea de informaţie

irelevantă sau ambiguă menţinând în vectori suficientă informaţie pentru a putea discerne între diferitele clase de forme şi descoperi invarianţele dintre formele aceleiaşi clase.

Pentru realizarea acestor deziderate au fost propuse şi utilizate o mare varietate de metode.

Una dintre cele mai simple metode pentru prelucrarea vectorilor de formă constă în normarea acestora. O astfel de normare implică egalarea sumei componentelor fiecărui vector de formă (respectiv suma pătratelor componentelor lor) cu o constată arbitrară convenabil aleasă. Un alt procedeu, mult mai sofisticat, care utilizează matricea de covarianţă duce, în final, la o ecuaţie matricială din care se obţin vectorii proprii şi valorile proprii ( procedeul numit analiza componentelor principale sau analiza Karhuneu-Loeve).

Pentru prelucrarea vectorilor de formă şi selectarea celor mai reprezentative caracteristici au fost utilizate şi o serie de transformări mult mai complexe, cum ar fi transformata Fourier.

Pentru identificarea caracteristicilor mai importante au fost utilizate forme model sau prototip, s-au dezvoltat şi implementat tehnici interactiv, implicând repreyentări grafice şi rutine speciale de comparare, s-au calculat parametrii statistici, cum sunt momentele sau histogramele direct din forme.

Această etapă este esenţială, de ea depinde succesul sau insuccesul oricărui studiu de recunoaştere a formelor.

1.2.3. Clasificatorul

Sarcina oricărui clasificator este, în general, următoarea: având dată o mulţime de vectori de formă prelucraţi corespunzător, numită set de formare, se pune problema determinării unei funcţii de decizie f(X) astfel încât dacă:

f(X) > 0 atunci X aparţine clasei 1f(X) >= 0 atunci X aparţine clasei 2 (1.2)

Această etapă în care este determinată funcţia de decizie f(X) este cunoscută sub numele de fază de formare (formarea), de adaptare sau uneori de învăţare. Scopul urmărit este minimalizarea probabilităţii de eroare în procesul de clasificare.

Conceptul de clasificare a formelor poate fi înţeles ca o partiţionare a spaţiului formelor, x ={X} prin atribuirea fiecărui vector X sau punct X (x1, …,xn) la o clasă de forme corespunzătoare în regiuni reciproc exclusive, fiecare regiune corespunzând unei clase de forme particulară. Din punct de vedere matematic problema clasificării poate fi formulată sub forma funcţiilor de decizie discriminate.

Fie 1, 1,….p cele p clase distincte posibile care urmează a fi recunoscute cu X = 1 U 2 U ….Up,1 2 …… p = Fd (1.3.)

şi fie X=|xi |i=1,n vectorul de formă, xi reprezentând a i-a caracteristică reprezentativă. Atunci funcţia de decizie discriminant f(X)=Dj (X) asociată clasei de forme j, j=1,…,p, astfel încât dacă forma de intrare reprezentată prin vectorul X, respectiv punctul X, este în

clasa i, fapt pe care-l vom nota prin Xi , valoarea lui Di(X) trebuie să fie cea mai mare, adică pentru toţi Xi vom avea satisfăcută relaţia:

Di(X) > Dj(X), i, j =1,…,p. (1.4)

În felul acesta, în spaţiul formelor x frontiera partiţiei, denumită limita de decizie, dintre regiunile corespunzând claselor i şi respectiv, j, poate fi definită prin următoarea relaţie:

Fd= Di(X)-Dj(X) = 0 (1.5)

În figura 2.8. este reprezentat modelul unui clasificator care utilizează funcţiile discriminant. Forma de intrare este analizată conform relaţiei (1.4), clasificatorul furnizând drept ieşire indicele k aparţine {1,2,…,p} corespunzător clasei k din care face parte forma respectivă X.

Fig. 1.4-2 Modelul clasificatorului ce utilizează funcţia discriminant

Pentru determinarea funcţiilor discriminant neparametrice setul de formare trebuie să fie mare şi, de asemenea, reprezentativ pentru a permite estimarea acestora din funcţiile de probabilitate.

3. Metode teoretice decisionale ale tehnicilor de recunoastereSunt cunoscute două moduri de abordare a procesului de recunoaştere a formelor.

Primul mod cunoscut sub numele de recunoaştere controlată presupune existenţa unui set de forme a căror apartenenţă la clasă este cunoscută. Acest set este împărţit în două părţi: setul de formare utilizat pentru a dezvolta un clasificator (ce utilizează, de exemplu, matricea distanţelor dintre forme) care să recunoască cât mai bine apartenenţa formelor din set la clasele corespunzătoare şi setul de predicţie pe care clasificatorul format este evaluat (testat). Clasificatorul astfel dezvoltat este utilizat în continuare pentru stabilirea apartenenţei unei forme necunoscute la o clasă.

Cel de-al doilea mod cunoscut sub numele de recunoaştere necontrolată nu face apel la o cunoaştere prealabilă a apartenenţei formelor la o clasă. Metoda dezvoltă algoritmi care permit în cursul execuţiei acestora construirea claselor pe măsură ce formele analizate sunt luate în considerare.

Un caz particular al metodelor teoretice decizionale îl constituie tehnicile de învăţare. Acestea utilizează un set de forme a căror apartenenţă la clase este cunoscută. Setul este utilizat în mod iterativ de un algoritm care construieşte coeficienţii clasificatorului, corespunzător tipului de problemă (fără a utiliza matricea distanţelor dintre forme).

1.2.4. Vectori de formă şi spaţiul formelor

Fiecare caracteristică poate fi considerată ca fiind o variabilă într-un spaţiu n-dimensional unde fiecare caracteristică este atribuită unei dimensiuni. Fiecare formă apare ca un punct în spaţiul formelor. Când o formă este descrisă de mai multe caracteristici ea poate fi privită ca un vector X, denumit vectorul de formă. Acest vector este dat de relaţia:

(2.1)

unde xi, i= 1,…, n reprezintă cele n caracteristici.Spaţiul formelor notat cu X poate fi descris cu ajutorul relaţiei

(2.2)

unde X’i desemnează vectorul transpus a lui X, iar m numărul de forme.

4. Tehnici de deciziesi clasificare

Conceptul de clasificare al formelor poate fi înţeles ca o partiţionare a spaţiului caracteristicilor acestuia. Clasificarea formelor, adică atribuirea fiecărui vector posibil sau punct din spaţiul caracteristicilor clasei din care face parte, poate fi interpretată ca o partiţionare a acestuia în regiuni (domenii) reciproc exclusive, fiecare domeniu aparţinând unei clase de forme particulare. Din punct de vedere matematic acest gen de problemă de clasificare poate fi definită sub forma unei funcţii discriminant. Astfel fie 1, 2,…m cele m clase de forme posibile cu proprietăţile:

1 2 … m= X, (2.3) şi

1 2 … m = F.

Unde cu F s-a notat mulţimea care constituie frontierele dintre clase, iar cu X s-a notat vectorul de formă. În acest caz funcţia discriminant Dj(X) asociată clasei de forme

j, j =1,…, m are proprietatea că dacă forma reprezentată prin vectorul X face parte din i, fapt pe care-l vom simboliza Xi, cu i specificat, atunci valoarea lui Di(X) trebuie să fie cea mai mare, adică pentru toţi Xi va fi îndeplinită condiţia

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

În felul acesta limitele de partiţionare ale spaţiului caracteristicilor (desemnate anterior cu F), denumite şi limite de decizie, pot fi exprimate cu ajutorul relaţiei

F = Di(X) – Dj(X) = 0; i, j=1,…,m, ij (2.5)

Au fost propuse foarte multe forme pentru funcţii discriminant D i(X), forme ce satisfac condiţia (2.4). dintre acestea vom menţiona în continuare doar pe cele mai importante.

1.2.4.1.Funcţii discriminant liniare

Într-un spaţiu bidimensional aceste funcţii sunt liniare şi pot fi scrise sub forma:x1-mx2-b=0,

sauW1x1+W2x2+W3x3=0 (2.6)

unde: m - este coeficientul unghiular,b - termenul liber, iar W1= 1, W2= -m şi W3= -b.Într-un spaţiu n- dimensional funcţiile sunt hiperplane de forma:

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

În acest caz funcţia discriminant Di(X) asociată clasei de forme i reprezintă o combinaţie liniară a caracteristicilor xi, i =1,…,m, dată în relaţia:

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

Ecuaţiile hiperplanelor date de relaţia (1.8), pentru m clase de forme, pot fi scrise matriceal astfel:

D(X)=Unde:

şi (2.9)

În vectorul X s-a introdus suplimentar termenul 1 pentru a da posibilitatea efectuării operaţiei de înmulţire.

Limita de decizie dintre regiunile x corespunzătoare claselor i şi j este de forma:

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

unde:Wk=Wi,k – Wj,k

şiWn+1=Wi,n+1-Wj,n+1.

Ecuaţia (2.10) reprezintă ecuaţia unui hiperplan din spaţiul caracteristicilor x, numit şi plan de decizie. Pentru a ilustra modul de utilizare a funcţiilor discriminant liniare prezentăm un exemplu în care avem două forme într-un spaţiu bi-dimensional. Fie formele X1 şi X2 date de:

şi

şi funcţia de decizie D(X) = 0 dată de relaţia:

Relaţia de mai sus poate fi scrisă sub forma:

Dacă înlocuim pe X1 şi X2 în D(X), obţinem:

şi respectiv

Pentru orice punct aflat deasupra lui D(X) = 0, D(X) este pozitiv şi negativ pentru punctele de sub dreaptă. Astfel, pentru cazul a două clase, polaritatea în evaluarea lui D(X) determină la care clasă aparţine forma dată (Fig. 1.2-1).

Fig. 2.2-3Funcţia de decizie liniară în două dimensiuni.

În cazul în care este necesară discriminarea pentru mai mult de două forme sunt necesare două sau mai multe funcţii de decizie. Pentru această situaţie există trei tipuri de clasificatori.

i) Tipul 1 utilizează o funcţie de decizie care împarte spaţiul formelor în două clase. Prima clasă notată cu i conţine o singură formă, iar cea de a doua clasă conţine restul formelor. Pentru a asigura apartenenţa unei forme la clasa i este suficient să fie îndeplinită condiţia Di(X)>0 şi Dj(X)<0 pentru toţi i, j. Pentru n clase sunt necesare n funcţii de decizie.

ii) Tipul 2 utilizează funcţii de decizie care separă spaţiul formelor în două regiuni. Prima regiune conţine două clase, iar cea de-a doua restul claselor. Separarea celor două clase i şi j se face cu ajutorul unei funcţii de decizie de forma Dij(X) = 0. Apartenenţa unei forme la clasa i sau j este asigurată dacă Dij(X) > 0.

iii) Tipul 3 reprezintă un caz special al tipului 2 de clasificare. Din analiza figurilor 2.2-2a şi 2.2-2b se observă prezenţa unui spaţiu nedeterminat care apare în interiorul triunghiului format din cele trei drepte corespunzătoare funcţiei de decizie. Punctele din interiorul acestui triunghi nu pot fi atribuite la nici una din cele trei clase. Pentru a elimina această nedeterminare, funcţia de decizie de tipul 2, Dij(X) = 0 este înlocuită cu Di(X)-Dj(X) = 0, unde Di(X) şi Dj(X) sunt funcţii de decizie de tipul 1. Pentru ca o formă să fie atribuită clasei i este necesar, în acest caz, îndeplinirea condiţiei Di(X)>Dj(X) pentru toţi ji (vezi fig. 2.2-2c).

Fig. 2.2-4 Funcţii de decizie multi-categorie: a-tipul 1; b-tipul 2; c-tipul 3.

Dacă clasele pot fi separate utilizând tipul 1 de clasificare, regiunile în care este prezentă clasele vor fi mai compacte, fapt care conduce la o mai bună identificare a claselor decât în cazul utilizării tipului 2 sau 3 de clasificare. In schimb, însă, regiunea de nedeterminare este mare. Dacă în aplicaţia practică apar forme în regiunea de nedeterminare rezultate în urma aplicării tipului 1 de clasificare, poate fi încercată utilizarea tipului 2 de clasificare, în care regiunea de nedeterminare este mai mică sau a tipului 3 (tipul 3 de clasificare are dezavantajul că timpul de calcul este mare)

5. Clasificatorul de distanta minimaO importantă clasă de clasificatori se bazează pe valoarea distanţelor dintre forma

de intrare şi un set de vectori de referinţă sau puncte prototip din spaţiul caracteristicilor (prototipurile sunt forme a căror apartenenţă la clase este cunoscută). Dacă vom presupune că sunt cunoscuţi m vectori de referinţă, notaţi cu R1, R2,…Rm, cu Rj asociat clasei j , atunci clasificatorul de distanţă minimă va atribui forma de intrare X clasei i

dacă distanţa dintre aceasta şi vectorii de referinţă este minimă, adică X i dacă d = X-Ri = minim. (2.11)

Considerăm două grupe de puncte distincte în spaţiul formelor şi ne propunem să determinăm funcţia de decizie care va putea separa spaţiul formelor în două regiuni care vor corespunde celor două clase. Iniţial vom determina vectorii de referinţă pe care îi vom considera reprezentând centrele celor două grupări de puncte. Valoarea punctelor prototip poate fi calculată cu o relaţie de forma :

(2.12)

unde N reprezintă numărul de forme dintr-o grupare. Distanţa dintre o formă X şi centrul grupării R (R este de forma R = (r1, r2,…,rm)) este dată de relaţia d = X-R. Dacă considerăm că cele două grupări se află într-un spaţiu bi-dimensional, atunci d va avea următoarea formă :

d2 = (x1 - r1)2 +(x2 - r2)2 = x12 - 2x1r1 + r1

2 + x22 - 2x2r2 + r2

2.

In cazul când avem mai mult de două clase, distanţa dintre o formă X şi Ri al grupării i este dată de :

(2.13)Deoarece este aceeaşi pentru toate clasele, el poate fi eliminat. Dacă

înmulţim relaţia (1.13) cu –0.5, vom obţine :(2.14)

Deoarece di2 a fost înmulţit cu un număr negativ rezultă că cea mai mare funcţie

de decizie (max Di(X)) identifică distanţa minimă şi deci clasa lui X.Pentru determinarea termenilor W, din funcţia de decizie se

utilizează relaţia (2.14) şi rezultă , pentru i = 1,.., n şi .

Din cele spuse anterior rezultă că un clasificator de distanţă minimă este un clasificator liniar. Performanţa unui astfel de clasificator depinde evident de modul cum sunt aleşi vectorii de referinţă dar şi de felul cum sunt evaluate distanţele. Cele mai frecvente distanţe utilizate sunt cele derivate de distanţa generală Minkovski.

(2.15)

Astfel, pentru k = 2 se obţine binecunoscuta distanţă Euclidiană.

(2.16)

Pentru k = 1 se obţine distanţa Manhattan.

(2.17)

Dacă toate caracteristicile xi şi ri, i =1,…,n sunt codificate binar (au doar valorile 0 sau 1), atunci distanţa Manhattan poartă numele de distanţa Hamming. Distanţa Hamming este echivalentă cu numărul de caracteristici care sunt diferite în X şi R. Aplicarea lui SAU EXCLUSIV, simbolizat aici prin XOR, permite calcului foarte rapid al distanţei Hamming conform relaţiei:

(1.18)

6. Clasificatorul vecinului cel mai apropiat

i) Clasificatorul vecinului cel mai apropiat. Acesta dezvoltă un clasificator de distanţă minimă în raport cu mai multe seturi de vectori de referinţă. Astfel, fie R1, …,Rm cele m seturi de vectori prototip asociate, respectiv, claselor 1,…,m şi Rj

(k) setul de vectori de referinţă din setul Rj, care aparţin

clasei j. În acest caz distanţa dintre forma de intrare reprezentată prin vectorul X şi setul de vectori de referinţă Rj se defineşte astfel:

, j = 1,…,m (2.19)

Uj fiind numărul de vectori de referinţă din setul Rj. Clasificatorul ce utilizează acest tip de distanţă va fi de forma

i =1, …, m (2.20)

Aceşti clasificatori sunt adesea denumiţi clasificatori liniari pe porţiuni sau clasificatori bazaţi pe cei mai apropiaţi U vecini.

7. Tehnici de grupareTehnicile de grupare constă dintr-un set de algoritmi care asigură împărţirea

spaţiului formelor în clase, grupe de forme, fără a face apel la existenţa prealabilă a unui set de predicţie cunoscut. Conceptul de grupare poate fi înţeles cel mai bine prin prezentarea celui mai simplu algoritm de grupare (denumit algoritm de tip prag). Algoritmul presupune existenţa în spaţiul formelor a unui set de forme şi stabilirea iniţială a unei distanţe minime (numită distanţa de prag) dintre două forme. Dacă distanţa dintre două forme este mai mică decât distanţa de prag, cele două forme fac parte din aceeaşi clasă. Notăm cu T distanţa prag. Iniţial se stabileşte aleatoriu un prim centru de grup pe care-l notăm cu Z1(Z1 corespunde cu una din cele N forme). Se calculează distanţa dintre acest centru şi toate celelalte forme. Dacă distanţele calculate sunt mai mici decât T, formele respective sunt atribuite clasei 1 , a cărei centru este Z1. Prima formă situată la o distanţă mai mare decât T conduce la crearea unei noi grupări (clase) i

cu centrul definit de forma respectivă. Se reia calculul distanţelor pentru formele rămase, luând în considerare noua grupare creată.

Procesul de obţinere de noi grupări şi de atribuire a formelor la aceste grupări continuă până în momentul în care sunt clasificate toate formele. Algoritmul este prezentat în figura Fig. 2.3-1.

Fig. 2.3-5Algoritm de tip prag.

Studiind acest algoritm pot fi determinate o serie de caracteristici ale tehnicilor de grupare.

1. Alegerea centrelor claselor (grupărilor). Modul de alegere afectează viteza de clasificare ca şi numărul de grupe (clase) care rezultă în urma executării procedurii de clasificare. Din acest motiv se recurge, de obicei, la calculul continuu a unui centru al clasei pe măsură ce la acesta se atribuie noi forme. În acest caz, centrul grupării poate să nu corespundă cu o forma existentă.2. Alegerea criteriului de clasificare. În cazul exemplului dat, criteriul de clasificare este o distanţă. Se observă că valoarea lui T afectează rezoluţia procesului de clasificare. Dacă T este prea mare, două sau mai multe clase distincte pot fi grupate în una singură. În cazul în care T este prea mic, o grupare poate fi împărţită în mod artificial în câteva grupe. Pentru determinarea valori lui T se ţine cont de efectul pe care-l va avea această valoare asupra numărului de grupări. În cazul general se utilizează criteriile de similaritate şi nesimilaritate prin care se asigură apartenenţa unei forme la o clasă. Acestea pot fi distanţe sau alţi parametri.

8. Masuri de disimilaritate

1.2.5. Măsuri de disimilaritate.Fie X o mulţime de obiecte de clasificat. Cea mai generală măsură de disimilaritate pe

care o putem defini peste X este o funcţie D: X*XR care satisface axiomele:(1) D(x,y)0 x,yX(2) D(x,x)=0 xX(3) D(x,y)=D(y,x) x,yX

Se admite că X este mulţime de instruire (cunoaştem pentru fiecare obiect din X clasa căruia el aparţine) iar D este o măsură de disimilaritate adecvată. În aceste condiţii este de aşteptat ca disimilaritatea dintre obiectele aceleiaşi clase să fie sensibil mai mică decât disimilaritatea dintre puncte aflate în clase diferite. În cazul când datele sunt obiecte dintr-un spaţiu euclidian vom considera metrica spaţiului ca o măsură a disimilarităţii.

Dacă X şi Y sunt puncte dintr-un spaţiu euclidian d-dimensional X = (x1, x2,...,xd),Y =(y1, y2,...,yd),

atunci pentru orice număr real p1 se poate defini metrica:

d(X, Y) (1)

De fapt (1) reprezintă o familie infinită de matrici. Pentru p = 1 din (1) se obţine:

d(X, Y) (2)

numită metrica absolută sau distanţa City Black.Dacă p = 2 se obţine distanţa euclidiană :

d(X, Y) (3)

iar pentru p∞ se obţine metrica valorii maxime :d(X, Y) (4)Să considerăm că valorile posibile ale caracteristicilor formelor de clasificat sunt în

număr finit şi fie d acest număr. În acest caz ca măsură de disimilaritate se pot utiliza distanţele Hamming şi Lee.

Distanţa Hamming dintre vectorii X şi Y este dată de numărul componentelor (poziţiilor) în care cei doi vectori diferă. Ponderea Hamming a vectorului X, notată cu WH(X), se defineşte ca fiind numărul de componente nenule ale lui X. Rezultă că distanţa Hamming dintre X şi Y este egală cu ponderea Hamming a diferenţei lor :

dH (X, Y)= WH(X, Y) (5)

Distanţa LeeFie q un număr întreg, pozitiv, q2 şi X = (x1, x2,...,xd), cu xi{0,1, . . . ,q-1}.

Ponderea Lee a vectorului X, notată cu WL(X), se defineşte ca fiind:

WL(X)

unde: