|
|
|
Scopul lucrarii
Lucrarea are ca scop prezentarea unor algoritmi de baza in procesul de clasificare a formelor.
Notiuni teoretice.
Tehnicile de grupare consta dintr-un set de algoritmi care asigura impartirea spatiului formelor in clase, grupe de forme, fara a face apel la existenta prealabila a unui set de predictie cunoscut. Conceptul de grupare poate fi inteles cel mai bine prin prezentarea celui mai simplu algoritm de grupare (denumit algoritm de tip prag). Algoritmul presupune existenta in spatiul formelor a unui set de forme si stabilirea initiala a unei distante minime (numita distanta de prag) dintre doua forme. Daca distanta dintre doua forme este mai mica decat distanta de prag, cele doua forme fac parte din aceeasi clasa. Notam cu T distanta prag. Initial se stabileste aleator un prim centru de grup pe care-l notam cu Z1(Z1 corespunde cu una din cele N forme). Se calculeaza distanta dintre acest centru si toate celelalte forme. Daca distantele calculate sunt mai mici decat T, formele respective sunt atribuite clasei w1, a carei centru este Z1. Prima forma situata la o distanta mai mare decat T conduce la crearea unei noi grupari (clase) wi cu centrul definit de forma respectiva. Se reia calculul distantelor pentru formele ramase, luand in considerare noua grupare creata.
Procesul de obtinere de noi grupari si de atribuire a formelor la aceste grupari continua pana in momentul in care sunt clasificate toate formele. Algoritmul este prezentat in figura Fig. 3.1.
Fig. 3.1 Algoritm de tip prag.
Studiind acest algoritm pot fi determinate o serie de caracteristici ale tehnicilor de grupare.
1. Alegerea centrelor claselor (gruparilor)
Modul de alegere afecteaza viteza de clasificare ca si numarul de grupe (clase) care rezulta in urma executarii procedurii de clasificare. Din acest motiv se recurge, de obicei, la calculul continuu a unui centru al clasei pe masura ce la acesta se atribuie noii forme. In acest caz, centrul gruparii poate sa nu corespunda cu o forma existenta.
2. Alegerea criteriului de clasificare.
In cazul exemplului dat, criteriul de clasificare este o distanta. Se observa ca valoarea lui T afecteaza rezolutia procesului de clasificare. Daca T este prea mare, doua sau mai multe clase distincte pot fi grupate in una singura. In cazul in care T este prea mic, o grupare poate fi impartita in mod artificial in cateva grupe. Pentru determinarea valori lui T se tine cont de efectul pe care-l va avea aceasta valoare asupra numarului de grupari. In cazul general se utilizeaza criteriile de similaritate si nesimilaritate prin care se asigura apartenenta unei forme la o clasa. Acestea pot fi distante sau alti parametri.
In figura Fig 3.2 se prezinta un algoritm general de grupare care ia in considerare criteriile de grupare specificate anterior.
Fig 3.2
3.2 Algoritm de grupare
Aceste tehnici dezvolta algoritmi prin care sunt construiti coeficientii functiei de decizie utilizand o metoda tip 'feed-back'. Algoritmii opereaza asupra unui set de forme a caror apartenenta la clasa este cunoscuta. Determina coeficientii functiei de decizie conform unuia din cele trei criterii de clasificare (specificate anterior), interativ, pana la satisfacerea conditiilor impuse.
Pentru a ilustra cele mentionate presupunem un set de N forme impartit in doua clase w1 si w2. Ne propunem sa determinam coeficientii vectorului pondere W. Functia de decizie data de relatia (1.9), pentru un spatiu n-dimensional, are forma
D(X)=[W1, .,Wn,Wn+1]X, unde X [x1I,x2I] pentru i=1,.,n.
Pentru formele x1i ce aprtin clasei w1, functia de decizie este pozitiva si negativa daca x2I apartine w2 (vezi paragraful 1.2.2.a). Prin urmare criteriul care se urmareste a fi atins este D(X)>0. Algoritmul alege o forma si calculeaza functia sa de decizie. Daca D(X)>0, vectorul pondere este satisfacator si nu se modifica. Se trece la urmatoarea forma. Daca D(X)<0, vectorul de ponderi trebuie sa fie modificat astfel incat functia de decizie sa devina pozitiva. Daca aceasta conditie a fost indeplinita pentru toate formele din clasa w1 se repeta operatia pentru formele din clasa w2 (care au fost inmultite in prealabil cu -1 pentru ca functia de decizie sa fie pozitiva). Operatia presupune:
i) stabilirea unei valori initiale pentru vectorul de ponderi;
ii) stabilirea unei modalitati de modificare a lui W.
Fig.3.3. Algoritm de invatare.
Un exemplu concret pentru acest algoritm este urmatorul:
Fie un set de forme, intr-un spatiu bidimensional al formelor, dat de
Alegand C=1 si W(0)=0, algoritmul lucreaza astfel
Deoarece D(X1) nu este mai mare ca zero, W trebuie modificat
Pentru cea de-a doua forma din clasa v1se calculeaza
Deci
Procedura continua, iar rezultatele sunt trecute in tabelul de mai jos.
Toti D(X) sunt corecti cand procedura se temina cu
Din modul de desfasurare al algoritmului se observa ca C = 1 a fost arbitrar ales. Pentru a asigura o viteza mai mare de convergenta a algoritmului, C poate fi calculat astfel: din conditia W(k+1) X>0, respectiv [W(k)+C X>0, ne rezulta C>-W(k)X/X X. Deoarece X X >0 si presupunand ca am avut o clasificare incorecta adica W X 0, este necesar ca -W X 0. Astfel ecuatia pentru C poate fi scrisa sub forma
C =W(k) X/X X.
Iteratie
Clasa
W
D(X)
Modificare W
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
2
2
1
1
2
2
1
1
2
2
1
1
(0 0 0)
(3 1 1)
(3 1 1)
(1 -3 2)
(1 -3 2)
(1 -3 2)
(2 -1 3)
(2 -1 3)
(-2 -4 4)
(1 -3 5)
(2 -1 6)
(2 -1 6)
(3 -1 6)
(4 -1 6)
(3 1 1)
(1 2 1)
(-2 -4 1)
(-4 -3 1)
(3 1 1)
(1 2 1)
(-2 -4 1)
(-4 -3 1)
(3 1 1)
(1 -3 5)
(2 -4 1)
(-4 -3 1)
(2 -1 6)
(2 -1 6)
0
6
-9
7
2
-3
3
-2
-6
0
6
1
11
6
Da
Nu
Da
Nu
Nu
Da
Nu
Da
Da
Da
Nu
Nu
Nu
Nu
1. Sa se implementeze algoritmul de tip prag, care sa imparta n forme in m clase pentru centre generate continuu (n si m se vor considera date de intrare).
2. Sa se implementeze algorimul de invatare prezentat la paragraful 3.1, luand in considerare clasele v1 si v2 definite astfel:
