Metode de Clasificare Automată

Metode de clasificare automata

Metoda vectorilor suport (SVM,

Vector Support Machine) si functii

kernel (KM, Kernel Machine)

Dificultati în rezolvarea problemelor

de clasificare

1. Pentru clasificare se pot utiliza mai multi separatori ai

2. Spatiul intrarilor nu este liniar separabil.

Rezolvarea problemei de clasificare cand spatiul

intrarilor nu este liniar separabil

- Utilizarea unui clasificator neliniar (de exemplu o

retea backpropagation);

- Utilizarea unui clasificator liniar, acceptand unele

erori de clasificare;

- Utilizarea unui clasificator liniar, într-un spatiu de

dimensiune mai mare în care au fort transferate

(transformate) datele de instruire (de intrare).

Metoda vectorilor suport (SVM)

Sa consideram urmatoarea ecuatie a unui hiperplan în spatiul

intrarilor:

0 b x w = + Å

w este perpendicular pe separatorul liniar (vector normal). b

este proportional cu distanta de la origine la separator.

Constanta de proportionalitate este negativul lungimii vectorului

normal.

este distanta (cu semn) a punctului x la hiperplan.

Clasificator liniar h(x)

) ( ) ˆ ( ) ( x w sign b x w sign x h Å a + Å =

Marginea unui punct

O varianta a distantei cu semn este marginea punctului,

definita drept:

Margine punct = Distanta * semnul dorit al distantei

j j j j j x w y b x w y Å a + Å = ³ ) (

Daca punctul este corect clasificat, produsul este pozitiv altfel

este negativ.

Algoritmul percepronului

- Se initializeaza w

- Se repeta pâna când toate punctele sunt corect

clasificate

- Repeta pentru fiecare punct i

- Se calculeaza marginea punctului i, respectiv

- Daca marginea este pozitiva, punct corect

clasificat ;

- Daca marginea este negativa, se schimba w pentru

a mari marginea (schimbarea este proportionala cu

i i x w y Å

i i x y Å

Algoritmul pocket

Daca datele nu sunt liniar separabile, se intra într-un

ciclu infinit. O solutie este memorarea celui mai bun

separator identificat si atunci când se decide

întreruperea instruirii se revine la acel separator.

Algoritmul perceptronului - forma

duala

Se considera ±i un contor care exprima numarul de

clasificari incorecte ale punctului i. ±i se initializeza pe

valoarea 0.

Valoarea finala a w este calculata dupa relatia

Clasificatorul liniar este:

Algoritmul percepronului - forma

duala

± = 0

Repeta pâna când toate punctele sunt corect clasificate

Repeta pentru fiecare punct j

Se calculeaza marginea

Daca marginea este pozitiva sau 0, punct corect

clasificat ;

Daca marginea este negativa, se incrementaeza ±

Daca datele nu sunt liniar separabile, ± j creste

necontrolat.

curs IA ASE