Extras din curs
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.
Preview document
Conținut arhivă zip
- Metode de Clasificare Automata.pdf