K-cei mai apropiați vecini

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Curly Brackets.svg Șablonul sinoptic {{ Algoritmo }} trebuie adăugat la acest articol sau secțiune
Puteți adăuga și completa șablonul conform instrucțiunilor și apoi eliminați acest avertisment. Dacă nu reușiți să o umpleți într-o mare măsură, nu faceți nimic; nu introduceți șabloane goale.

K-cei mai apropiați vecini (k-NN) este un algoritm utilizat în recunoașterea modelelor pentru clasificarea obiectelor pe baza caracteristicilor obiectelor apropiate de cel luat în considerare. În ambele cazuri, intrarea reprezintă cele mai apropiate exemple de instruire k din spațiul de caracteristici. Ieșirea depinde de utilizarea k-NN pentru clasificare sau regresie:

În clasificarea k-NN, rezultatul este apartenența la o clasă. Un obiect este clasat prin votul pluralității vecinilor săi, cu obiectul atribuit clasei cele mai comune dintre cei mai apropiați k vecini (k este un număr întreg pozitiv de obicei mic). Dacă k = 1, obiectul este pur și simplu atribuit clasei acelui vecin cel mai apropiat.

În regresia k-NN, ieșirea este valoarea proprietății obiectului. Această valoare este media celor mai apropiate valori k învecinate.

Caracteristici principale

Este cel mai simplu algoritm dintre cei utilizați în „ învățarea automată (machine learning).

Parametrul k

Un obiect este clasat pe baza majorității voturilor celor k vecini. k este un întreg pozitiv de obicei nu foarte mare. Dacă k = 1, atunci obiectul este atribuit clasei vecinului său. Într-un context binar în care există doar două clase, este recomandabil să alegeți k impar pentru a evita să vă regăsiți în situații egale.

Această metodă poate fi utilizată pentru tehnica de regresie prin atribuirea obiectului media valorilor k obiectelor vecine.

Având în vedere doar voturile celor k obiecte învecinate, există dezavantajul datorat predominanței claselor cu mai multe obiecte. În acest caz, poate fi util să cântărești contribuțiile vecinilor pentru a acorda, în calculul mediei, o importanță mai mare pe baza distanței de la obiectul luat în considerare.

Alegerea parametrului k

Alegerea lui k depinde de caracteristicile datelor. În general, pe măsură ce k crește, zgomotul care compromite clasificarea este redus, dar criteriul de alegere pentru clasă devine mai instabil. Alegerea poate fi făcută prin tehnici euristice , cum ar fi validarea încrucișată .

Algoritmul

Faza de învățare

Spațiul este împărțit în regiuni pe baza locațiilor și caracteristicilor obiectelor de învățare. Acesta poate fi considerat setul de învățare pentru algoritm, chiar dacă nu este cerut în mod explicit de condițiile inițiale.

Calculul distanței

În scopul calculării distanței, obiectele sunt reprezentate prin vectori de poziție într-un spațiu multidimensional. Distanța euclidiană este de obicei utilizată, dar alte tipuri de distanță sunt la fel de utilizabile, cum ar fi distanța Manhattan . Dacă trebuie să manipulați șirurile și nu numerele, puteți utiliza alte distanțe, cum ar fi distanța Hamming . Algoritmul este sensibil la structura de date locale.

Faza de clasificare

Un punct (reprezentând un obiect) este atribuit clasei C dacă acesta este cel mai frecvent dintre exemplele k cele mai apropiate de obiectul examinat, proximitatea este măsurată pe baza distanței dintre puncte. Vecinii sunt luați dintr-un set de obiecte pentru care este cunoscută clasificarea corectă. În cazul regresiei pentru calcularea mediei (clasificare) se utilizează valoarea proprietății considerate.

Exemplu de utilizare

KnnClassification.svg

Figura prezintă un exemplu de clasificare folosind kNN. Punctul observat este punctul verde. Există două clase:

  • cea a triunghiurilor roșii;
  • cea a pătratelor albastre.

Dacă k = 3 (adică sunt luate în considerare cele mai apropiate 3 obiecte), atunci punctul verde este plasat în aceeași clasă ca triunghiurile roșii, deoarece există 2 triunghiuri și 1 pătrat. Dacă k = 5, atunci este plasat în aceeași clasă cu pătratele albastre, deoarece există 3 pătrate și 2 triunghiuri.

Evaluări

Dezavantaje

Calculul distanțelor este împovărător din punct de vedere al calculului și proporțional cu dimensiunea setului de date examinate. Algoritmii propuși care îmbunătățesc acest dezavantaj urmăresc în principal scăderea numărului de distanțe care trebuie calculate pentru decizie. În unele cazuri, se încearcă partiționarea spațiului vector și se calculează doar distanțele dintre volumele spațiului vector.

Algoritmi similari

Unii algoritmi k-NN sunt enumerați mai jos:

Beneficii

Deoarece cantitatea de date tinde spre infinit, algoritmul nu depășește niciodată rata de eroare Bayes de două ori (eroarea minimă datorată distribuției datelor). Pentru unele valori ale lui k , cu k crescând în funcție de cantitatea de date, algoritmul atinge rata de eroare Bayes.

Variabile continue

k-NN poate fi utilizat, cu adaptări adecvate, pentru a estima variabilele continue. Acest tip de implementare utilizează o medie ponderată bazată pe inversul distanței.

Note bibliografice

  • Belur V. Dasarathy , editor (1991 ) Norme pentru vecinul cel mai apropiat (NN): tehnici de clasificare a modelelor NN , ISBN 0-8186-8930-7
  • Cele mai apropiate metode de învățare și viziune , editat de Shakhnarovish, Darrell și Indyk, The MIT Press, 2005, ISBN 0-262-19547-X
  • Estimarea volumelor de arboret forestier prin imagini Landsat TM și date de inventar de teren la nivel de arboret. Forest Ecology and Management , Volumul 196, Numărurile 2-3, 26 iulie 2004, paginile 245-255. Helena Mäkelä și Anssi Pekkarinen
  • Estimarea și cartarea densității, volumului și tipului de acoperire a pădurilor folosind metoda k- cel mai apropiat vecin. Teledetecția mediului, volumul 77, numărul 3, septembrie 2001, paginile 251-274. Hector Franco-Lopez, Alan R. Ek și Marvin E. Bauer

linkuri externe

Adus de la „ https://it.wikipedia.org/w/index.php?title=K-nearest_neighbors&oldid=120129218 ”