Ce este KNN (K-Nearest Neighbors)?

Ce este K-Nearest Neighbors (KNN)?

K-Nearest Neighbors este o tehnică și un algoritm de învățare automată care poate fi utilizat atât pentru sarcini de regresie, cât și pentru sarcini de clasificare. K-Nearest Neighbors examinează etichetele unui număr ales de puncte de date din jurul unui punct de date țintă, pentru a face o previziune despre clasa în care se încadrează punctul de date. K-Nearest Neighbors (KNN) este un algoritm conceptual simplu, dar foarte puternic, și din aceste motive, este unul dintre cele mai populare algoritme de învățare automată. Să facem o analiză detaliată a algoritmului KNN și să vedem exact cum funcționează. Având o înțelegere bună a modului în care KNN funcționează, vă va permite să apreciați cele mai bune și mai rele cazuri de utilizare pentru KNN.

Prezentare generală a K-Nearest Neighbors (KNN)

Foto: Antti Ajanki AnAj via Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

Să vizualizăm un set de date pe un plan 2D. Imaginați-vă un grup de puncte de date pe un grafic, răspândite pe grafic în grupuri mici. KNN examinează distribuția punctelor de date și, în funcție de argumentele date modelului, le separă în grupuri. Aceste grupuri sunt apoi etichetate. Principala ipoteză pe care o face un model KNN este că punctele de date/instanțele care există în proximitate una față de cealaltă sunt foarte asemănătoare, în timp ce dacă un punct de date este departe de alt grup, este disimilar față de acele puncte de date.

Un model KNN calculează similaritatea utilizând distanța dintre două puncte pe un grafic. Cu cât distanța dintre puncte este mai mare, cu atât ele sunt mai puțin asemănătoare. Există mai multe moduri de a calcula distanța dintre puncte, dar cea mai comună metrică de distanță este doar distanța euclidiană (distanța dintre două puncte într-o linie dreaptă).

KNN este un algoritm de învățare supravegheat, ceea ce înseamnă că exemplele din setul de date trebuie să aibă etichete atribuite. Există două lucruri importante de știut despre KNN. În primul rând, KNN este un algoritm non-parametric. Acest lucru înseamnă că nu se fac ipoteze despre setul de date atunci când se utilizează modelul. În schimb, modelul este construit în întregime din datele furnizate. În al doilea rând, nu există o separare a setului de date în seturi de antrenament și testare atunci când se utilizează KNN. KNN nu face generalizări între un set de antrenament și un set de testare, astfel încât toate datele de antrenament sunt utilizate și atunci când modelul este solicitat să facă previziuni.

Funcționarea algoritmului KNN

Un algoritm KNN trece prin trei faze principale pe măsură ce este efectuat:

1. Setarea lui K la numărul ales de vecini.
2. Calcularea distanței dintre un exemplu/test dat și exemplele din setul de date.
3. Sortarea distanțelor calculate.
4. Obținerea etichetelor pentru primele K intrări.
5. Revenirea unei previziuni despre exemplul de test.

În prima etapă, K este ales de utilizator și îi spune algoritmului câți vecini (câte puncte de date din jur) ar trebui să fie luați în considerare atunci când se face o previziune despre clasa în care se încadrează exemplul țintă. În a doua etapă, observați că modelul verifică distanța dintre exemplul țintă și fiecare exemplu din setul de date. Distanțele sunt apoi adăugate într-o listă și sortate. După aceea, lista sortată este verificată și etichetele pentru primele K elemente sunt returnate. Cu alte cuvinte, dacă K este setat la 5, modelul verifică etichetele pentru primele 5 puncte de date cele mai apropiate de punctul de date țintă. Atunci când se face o previziune despre punctul de date țintă, contează dacă sarcina este una de regresie sau clasificare. Pentru o sarcină de regresie, se utilizează media etichetelor pentru primele K, în timp ce pentru o sarcină de clasificare se utilizează modul etichetelor pentru primele K.

Operațiunile matematice exacte utilizate pentru a efectua KNN diferă în funcție de metrica de distanță aleasă. Dacă doriți să aflați mai multe despre modul în care se calculează metricile, puteți citi despre unele dintre cele mai comune metrici de distanță, cum ar fi Euclidean, Manhattan și Minkowski.

De ce contează valoarea lui K

Principala limitare atunci când se utilizează KNN este că o valoare incorectă a lui K (numărul incorect de vecini care trebuie luați în considerare) poate fi ales. Dacă se întâmplă acest lucru, previziunile care sunt returnate pot fi substanțial incorecte. Este foarte important ca, atunci când se utilizează un algoritm KNN, să se aleagă valoarea corectă pentru K. Doriți să alegeți o valoare pentru K care maximizează capacitatea modelului de a face previziuni pe date nevăzute, în timp ce reduce numărul de erori pe care le face.

Foto: Agor153 via Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Valori mai mici ale lui K înseamnă că previziunile făcute de KNN sunt mai puțin stabile și mai puțin fiabile. Pentru a obține o intuiție despre de ce se întâmplă acest lucru, considerați un caz în care avem 7 vecini în jurul unui punct de date țintă. Să presupunem că modelul KNN lucrează cu o valoare a lui K de 2 (îi cerem să examineze cei doi vecini mai apropiați pentru a face o previziune). Dacă majoritatea vecinilor (cinci din șapte) aparțin clasei Albastră, dar cei doi vecini mai apropiați se întâmplă să fie Roșii, modelul va prezice că exemplul de test este Roșu. În ciuda previziunii modelului, într-un astfel de scenariu, Albastrul ar fi o previziune mai bună.

Dacă este cazul, de ce nu alegeți pur și simplu valoarea cea mai mare a lui K pe care o puteți? Acest lucru se datorează faptului că, dacă spuneți modelului să ia în considerare prea mulți vecini, va reduce, de asemenea, precizia. Pe măsură ce raza pe care modelul KNN o ia în considerare crește, va începe în cele din urmă să ia în considerare puncte de date care sunt mai apropiate de alte grupuri decât de punctul de date țintă și se va produce o clasificare greșită. De exemplu, chiar dacă punctul care a fost inițial ales se afla într-una dintre regiunile roșii de mai sus, dacă K este setat prea mare, modelul va ajunge la puncte din alte regiuni. Atunci când se utilizează un model KNN, se încearcă diferite valori ale lui K pentru a vedea care valoare oferă modelului cea mai bună performanță.

Avantajele și dezavantajele KNN

Să examinăm unele dintre avantajele și dezavantajele modelului KNN.

Avantaje:

KNN poate fi utilizat atât pentru sarcini de regresie, cât și pentru sarcini de clasificare, spre deosebire de alți algoritmi de învățare supravegheați.

KNN este foarte precis și ușor de utilizat. Este ușor de interpretat, de înțeles și de implementat.

KNN nu face ipoteze despre date, ceea ce înseamnă că poate fi utilizat pentru o varietate largă de probleme.

Dezavantaje:

KNN stochează majoritatea sau toate datele, ceea ce înseamnă că modelul necesită multă memorie și este scump din punct de vedere computațional. Seturile de date mari pot cauza, de asemenea, ca previziunile să dureze mult timp.

KNN se dovedește a fi foarte sensibil la scala setului de date și poate fi ușor deranjat de caracteristici irelevante în comparație cu alte modele.

Rezumat al K-Nearest Neighbors (KNN)

K-Nearest Neighbors este unul dintre cele mai simple algoritme de învățare automată. În ciuda faptului că KNN este atât de simplu în concept, este, de asemenea, un algoritm puternic care oferă o precizie destul de ridicată în majoritatea problemelor. Când utilizați KNN, asigurați-vă că experimentați cu diferite valori ale lui K pentru a găsi numărul care oferă cea mai mare precizie.