6 Algoritmi practici
În continuare, vom studia o serie de algoritmi practici, foarte utilizați atunci când distribuțiile datelor sunt necunoscute.
În analiza de până acum, am considerat că se cunosc întotdeauna parametrii matematici ai tuturor datelor:
- Se cunosc semnalele
, - Se cunoaște zgomotul (gaussian, uniform etc.)
- Se cunosc distribuțiile condiționate
,
În aplicații reale, multe dintre acestea pot fi de fapt necunoscute, sau nedefinite.
Exemplu: recunoașterea feței unei persoane
- Identificarea persoanei A sau B bazată pe o imagine a feței
- Avem:
- 100 imagini ale persoanei A, în condiții diverse
- 100 imagini ale persoanei B, în condiții diverse
Să comparăm recunoașterea fețelor cu detecția semnalelor
- Aspecte comune:
- două ipoteze
(persoana A) și (persoana B) - un vector de eșantioane
= imaginea pe baza căreia se face decizia - se pot lua două decizii
- 4 scenarii: rejecție corectă, alarmă falsă, pierdere, detecție corectă
- două ipoteze
- Ce diferă? Nu există formule matematice
- nu există semnalele “originale”
și - (fețele persoanelor A și B nu pot fi exprimate matematic ca semnale)
- în schimb, avem multe exemple din fiecare distribuție
- 100 imagini ale lui A = exemple ale
în ipoteza - 100 imagini ale lui B = exemple ale
în ipoteza
- 100 imagini ale lui A = exemple ale
- nu există semnalele “originale”
Terminologia folosită în domeniul învățării automate (machine learning):
Acest tip de problemă = problemă de clasificare a semnalelor
- se dă un vector de date, găsiți-i clasa
Clase de semnal = categoriile posibile ale semnalelor (ipotezele
, persoanele A/B etc)Set de antrenare = un set de semnale cunoscute inițial
- de ex. 100 de imagini ale fiecărei persoane
- setul de date va fi folosit în procesul de decizie
Setul de antrenare conține informațiile pe care le-ar conține distribuțiile condiționate
exprimă cum arată valorile lui în ipoteza exprimă cum arată valorile lui în ipoteza- setul de antrenare exprimă același lucru, nu prin formule, dar prin multe exemple
Cum se face clasificarea în aceste condiții?
6.1 Algoritmul k-NN
6.1.1 Definiția algoritmului
Algoritmul k-Nearest Neighbours (k-NN) este descris mai jos.
Intrare:
- set de antrenare cu vectorii
, din clase posibile de semnal … - clasele vectorilor de antrenare sunt cunoscute
- vector de test
care trebuie clasificat - parametrul
- set de antrenare cu vectorii
Se calculează distanța între
și fiecare vector de antrenare- se poate utiliza distanța Euclidiană, aceeași utilizată pentru detecția semnalelor din secțiunile precedente
Se aleg cei mai apropiați
vectori de (cei “nearest neighbours”)Se determină clasa lui
= clasa majoritară între cei cei mai apropiați vecini
- Ieșire: clasa vectorului
6.1.2 Relația între k-NN și decizia ML
Dacă setul de antrenare este foarte mare, algoritmul k-NN devine simular cu decizia pe baza criteriului ML, pentru că numărul de vectori situați într-o vecinătate a unui punct
Exemplu: frunze și copaci, de povestit.
6.1.3 Discuții
Algoritmul k-NN este un algoritm de învățare supervizată, întrucât se cunosc clasele vectorilor din setul de antrenare.
Efectul lui
Cum se găsește o valoare optimă pentru
“Cross-validation” = folosirea unui mic set de test pentru a verifica care valoare a parametrului e mai bună
Acest set de date se numește set de “cross-validare”.
Practic, se alege
6.1.4 Evaluarea algoritmilor
- Cum se evaluează performanța algoritmului k-NN?
- Se folosește un set de date de testare, și se calculează procentajul vectorilor clasificați corect
- Setul de date pentru evaluarea finală trebuie să fie diferit de setul de “cross-validare”
- pentru evaluarea finală se folosesc date pe care algoritmul nu le-a mai utilizat niciodată
- Cum se împarte setul de date disponibile?
6.1.5 Seturi de date
- Presupunem că avem în total 200 imagini tip fețe, 100 imagini ale persoanei A și 100 ale lui B
- Setul de date total se împarte în:
- Set de antrenare
- vectorii care vor fi utilizați de algoritm
- cel mai numeros, aprox. 60% din datele totale
- de ex. 60 imagini ale persoanei A și 60 ale lui B
- Set de cross-validare
- utilizat pentru a testa algoritmul în vederea alegerii parametrilor optimi (
) - mai mic, aprox. 20% din date (de ex. 20 imagini ale lui of A și 20 ale lui B)
- utilizat pentru a testa algoritmul în vederea alegerii parametrilor optimi (
- Set de testare
- utilizat pentru evaluarea finală a algoritmului, cu valorile parametrilor fixate
- mai mic, aprox. 20% din date (de ex. 20 imagini ale lui of A și 20 ale lui B)
- Set de antrenare
6.2 Algoritmul k-Means
k-Means este un algoritm pentru clusterizarea datelor.
Prin clusterizare se înțelege operația de identificare a grupurilor de date apropiate între ele (clustere).
6.2.1 Definiția algoritmului
Algoritmul k-Means funcționează astfel:
- Intrare:
- set de antrenare cu vectorii
- numărul de clase C
- set de antrenare cu vectorii
- Inițializare: centroizii C iau valori aleatoare
- Repetă
- Clasificare: se clasifică fiecare vector
pe baza celui mai apropiat centroid: - Actualizare: se actualizează centroizii
= media vectorilor din clasa
- Clasificare: se clasifică fiecare vector
- Ieșire: centroizii
, clasele tuturor vectorilor de intrare
Pentru explicații video pe Youtube:
Urmăriți video-ul următor, de la 6:28 to 7:08
Urmăriți video-ul următor, de la 3:05 la final
6.2.2 Discuții
Algoritmul k-Means este un exemplu de algoritm de învățare nesupervizată.
Învățare nesupervizată = când nu se cunosc clasele semnalelor din setul de antrenare
Algoritmul k-Means poate să nu conveargă spre niște grupuri adecvate de date. Cu alte cuvinte, rezultate bune nu sunt garantate; rezultatele depind foarte mult de inițializarea aleatoare a centroizilor.
O soluție frecventă, în practică, este să rulăm algoritmul de mai multe ori, pentru a alege apoi cel mai bun rezultat. De asemenea, există în literatură și unele metode de inițializare optimizate (k-Means++)