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:

În aplicații reale, multe dintre acestea pot fi de fapt necunoscute, sau nedefinite.

Exemplu: recunoașterea feței unei persoane

Să comparăm recunoașterea fețelor cu detecția semnalelor

Terminologia folosită în domeniul învățării automate (machine learning):

Setul de antrenare conține informațiile pe care le-ar conține distribuțiile condiționate w(r|H0) și w(r|H1)

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 x1...xN, din L clase posibile de semnal C1CL
    • clasele vectorilor de antrenare sunt cunoscute
    • vector de test r care trebuie clasificat
    • parametrul k
  1. Se calculează distanța între r și fiecare vector de antrenare xi

    • se poate utiliza distanța Euclidiană, aceeași utilizată pentru detecția semnalelor din secțiunile precedente
  2. Se aleg cei mai apropiați k vectori de r (cei k “nearest neighbours”)

  3. Se determină clasa lui r = clasa majoritară între cei k cei mai apropiați vecini

  • Ieșire: clasa vectorului r

Algoritmul k-NN ilustrat [1]

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 r este proporțional cu w(r|Hi). Așadar, dacă sunt mai mulți vecini din clasa A decât din clasa B, caz în care k_NN ia decizia A, e totuna cu a spune că w(r|HA)>w(r|HB) care este de fapt regula de decizie ML, tot în favoarea clasei A.

Exemplu: frunze și copaci, de povestit.

Exercițiu
  1. Fie următorul set de antrenare, compus din 5 vectori din clasa A și alți 5 vectori din clasa B:
    • Clasa A: v1=[12]v2=[11]v3=[42]v4=[21]v5=[22]

    • Clasa B: v6=[70]v7=[23]v8=[32]v9=[38]v10=[25]

    Determinați clasa vectorului x=[36] utilizând algoritmul k-NN, cu k=1, k=3, k=5, k=7 and k=9

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 k se reflectă în gradul de “netezire” a frontierei de decizie: - k mic: frontieră foarte cotită / “șifonată” / cu multe coturi - k mare: frontieră mai netedă

Cum se găsește o valoare optimă pentru k?. În general, doar prin încercări (“băbește”), pe baza unui mic set de date de test. Această metodă se numește “cross-validation”.

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 k=1, și se testează cu setul de “cross-validare” câți vectori sunt clasificați corect. Apoi se repetă pentru k=2,3,...max. La final se alege valoarea lui k cu care s-au obținut rezultatele cele mai bune.

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 (k)
      • mai mic, aprox. 20% din date (de ex. 20 imagini ale lui of A și 20 ale lui B)
    • 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)

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 x1...xN
    • numărul de clase C
  • Inițializare: centroizii C iau valori aleatoare ci valori aleatoare 
  • Repetă
    1. Clasificare: se clasifică fiecare vector x pe baza celui mai apropiat centroid: classx=argminid(x,ci),x
    2. Actualizare: se actualizează centroizii ci = media vectorilor x din clasa i ci media vectorilor x,x din clasa i
  • Ieșire: centroizii ci, clasele tuturor vectorilor de intrare xn

Pentru explicații video pe Youtube:

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++)

Exercițiu
  1. Fie datele următoare: {vn}=[1.3,0.1,0.5,4.7,5.1,5.8,0.4,4.8,0.7,4.9]

    Utilizați algoritmul k-Means pentru a găsi doi centroizi c1 și c2, pornind de la valorile aleatoare c1=0.5 și c2=0.9. Realizați 5 iterații ale algoritmului.