The Algoritmul K-Nearest Neighbours (KNN). este o metodă de învățare automată supravegheată folosită pentru a aborda problemele de clasificare și regresie. Evelyn Fix și Joseph Hodges au dezvoltat acest algoritm în 1951, care a fost ulterior extins de Thomas Cover. Articolul explorează fundamentele, funcționarea și implementarea algoritmului KNN.

Ce este algoritmul K-Nearest Neighbours?

KNN este unul dintre cei mai de bază, dar esențiali algoritmi de clasificare în învățarea automată. Acesta aparține învăţare supravegheată domeniu și găsește o aplicare intensă în recunoașterea modelelor, Este de unică folosință în scenarii din viața reală, deoarece este neparametric, ceea ce înseamnă că nu face ipoteze fundamentale cu privire la distribuția datelor (spre deosebire de alți algoritmi precum GMM, care presupun o distribuție gaussiană a datelor date). Ni se oferă câteva date anterioare (numite și date de antrenament), care clasifică coordonatele în grupuri identificate printr-un atribut.

flux de filtru java

Ca exemplu, luați în considerare următorul tabel de puncte de date care conține două caracteristici:

Vizualizare de lucru cu algoritmul KNN

Acum, având în vedere un alt set de puncte de date (numite și date de testare), alocați aceste puncte unui grup analizând setul de antrenament. Rețineți că punctele neclasificate sunt marcate ca „Alb”.

Intuiția din spatele algoritmului KNN

Dacă trasăm aceste puncte pe un grafic, este posibil să reușim să localizăm niște clustere sau grupuri. Acum, având în vedere un punct neclasificat, îl putem atribui unui grup observând ce grup îi aparțin cei mai apropiați vecini. Aceasta înseamnă că un punct apropiat de un grup de puncte clasificat ca „Roșu” are o probabilitate mai mare de a fi clasificat ca „Roșu”.

În mod intuitiv, putem vedea că primul punct (2.5, 7) ar trebui clasificat ca „Verde”, iar al doilea punct (5.5, 4.5) ar trebui clasificat ca „Roșu”.

De ce avem nevoie de un algoritm KNN?

Algoritmul (K-NN) este un algoritm de învățare automată versatil și utilizat pe scară largă, care este utilizat în principal pentru simplitatea și ușurința sa de implementare. Nu necesită ipoteze cu privire la distribuția datelor subiacente. De asemenea, poate gestiona atât date numerice, cât și date categoriale, făcându-l o alegere flexibilă pentru diferite tipuri de seturi de date în sarcini de clasificare și regresie. Este o metodă neparametrică care face predicții bazate pe asemănarea punctelor de date dintr-un anumit set de date. K-NN este mai puțin sensibil la valori aberante în comparație cu alți algoritmi.

Algoritmul K-NN funcționează prin găsirea celor mai apropiați K vecini de un anumit punct de date pe baza unei metrici a distanței, cum ar fi distanța euclidiană. Clasa sau valoarea punctului de date este apoi determinată de votul majoritar sau de media celor K vecini. Această abordare permite algoritmului să se adapteze la diferite modele și să facă predicții bazate pe structura locală a datelor.

Măsuri de distanță utilizate în algoritmul KNN

După cum știm că algoritmul KNN ne ajută să identificăm cele mai apropiate puncte sau grupurile pentru un punct de interogare. Dar pentru a determina cele mai apropiate grupuri sau cele mai apropiate puncte pentru un punct de interogare avem nevoie de o măsurătoare. În acest scop, folosim valorile de distanță de mai jos:

Distanta euclidiana

Aceasta nu este altceva decât distanța carteziană dintre cele două puncte care se află în plan/hiperplan. distanta euclidiana poate fi vizualizată și ca lungimea dreptei care unește cele două puncte care sunt luate în considerare. Această măsurătoare ne ajută să calculăm deplasarea netă realizată între cele două stări ale unui obiect.

Distanța Manhattan

Distanța Manhattan metrica este utilizată în general atunci când suntem interesați de distanța totală parcursă de obiect în loc de deplasare. Această măsurătoare este calculată prin însumarea diferenței absolute dintre coordonatele punctelor în n dimensiuni.

Distanța Minkowski

Putem spune că distanța Euclidiană, precum și distanța Manhattan, sunt cazuri speciale ale distanta Minkowski .

Din formula de mai sus putem spune că atunci când p = 2 atunci este aceeași cu formula pentru distanța euclidiană și când p = 1 atunci obținem formula pentru distanța Manhattan.

Valorile discutate mai sus sunt cele mai comune atunci când se ocupă cu a Învățare automată problemă, dar există și alte valori ale distanței Distanța Hamming care sunt utile atunci când se confruntă cu probleme care necesită comparații suprapuse între doi vectori al căror conținut poate fi boolean, precum și valori de șir.

Cum să alegeți valoarea lui k pentru algoritmul KNN?

Valoarea lui k este foarte crucială în algoritmul KNN pentru a defini numărul de vecini din algoritm. Valoarea lui k în algoritmul k-nearest neighbors (k-NN) ar trebui aleasă pe baza datelor de intrare. Dacă datele de intrare au mai multe valori aberante sau zgomot, o valoare mai mare a lui k ar fi mai bună. Este recomandat să alegeți o valoare impară pentru k pentru a evita egalitățile în clasificare. Validare încrucișată metodele pot ajuta la selectarea celei mai bune valori k pentru setul de date dat.

Funcționarea algoritmului KNN

Algoritmul K-Nearest Neighbors (KNN) funcționează pe principiul similarității, în care prezice eticheta sau valoarea unui nou punct de date, luând în considerare etichetele sau valorile K vecinilor săi cei mai apropiați din setul de date de antrenament.

heapify sort

Explicația pas cu pas a modului în care funcționează KNN este discutată mai jos:

Pasul 1: Selectarea valorii optime a lui K

• K reprezintă numărul de vecini cei mai apropiați care trebuie luat în considerare atunci când faceți predicții.

Pasul 2: Calcularea distanței

• Pentru a măsura asemănarea dintre punctele de date țintă și de antrenament, se folosește distanța euclidiană. Distanța este calculată între fiecare dintre punctele de date din setul de date și punctul țintă.

Pasul 3: Găsirea celor mai apropiați vecini

• K puncte de date cu cele mai mici distanțe până la punctul țintă sunt cei mai apropiați vecini.

Pasul 4: Votarea pentru clasificare sau luarea mediei pentru regresie

• În problema de clasificare, etichetele clasei de sunt determinate prin efectuarea votului majoritar. Clasa cu cele mai multe apariții printre vecini devine clasa prezisă pentru punctul de date țintă.
• În problema de regresie, eticheta clasei este calculată luând media valorilor țintă ale K vecini cei mai apropiați. Valoarea medie calculată devine rezultatul estimat pentru punctul de date țintă.

Fie X setul de date de antrenament cu n puncte de date, unde fiecare punct de date este reprezentat de un vector caracteristic d-dimensional și Y să fie etichetele sau valorile corespunzătoare pentru fiecare punct de date din X. Având în vedere un nou punct de date x, algoritmul calculează distanța dintre x și fiecare punct de date. în X utilizând o metrică a distanței, cum ar fi distanța euclidiană:

Algoritmul selectează K puncte de date din X care au cele mai scurte distanțe la x. Pentru sarcinile de clasificare, algoritmul atribuie eticheta y care este cea mai frecventă dintre cei mai apropiați K vecini de x. Pentru sarcinile de regresie, algoritmul calculează media sau media ponderată a valorilor y ale celor mai apropiați K vecini și o atribuie ca valoare prezisă pentru x.

Avantajele algoritmului KNN

• Ușor de implementat întrucât complexitatea algoritmului nu este atât de mare.
• Se adapteaza usor – Conform funcționării algoritmului KNN, acesta stochează toate datele în memorie și, prin urmare, ori de câte ori se adaugă un nou exemplu sau un punct de date, algoritmul se ajustează în conformitate cu acel nou exemplu și are și contribuția sa la previziunile viitoare.
• Puțini hiperparametri – Singurii parametri care sunt necesari în antrenamentul unui algoritm KNN sunt valoarea lui k și alegerea metricii distanței pe care am dori să o alegem din metrica noastră de evaluare.

Dezavantajele algoritmului KNN

• Nu scala – După cum am auzit despre asta, algoritmul KNN este, de asemenea, considerat un algoritm leneș. Semnificația principală a acestui termen este că aceasta necesită multă putere de calcul, precum și stocarea datelor. Acest lucru face ca acest algoritm să fie atât consumator de timp, cât și epuizant de resurse.
• Blestemul dimensionalității – Există un termen cunoscut sub numele de fenomen de vârf, conform căruia algoritmul KNN este afectat de blestemul dimensionalității ceea ce implică că algoritmul se confruntă cu dificultăți în clasificarea corectă a punctelor de date atunci când dimensionalitatea este prea mare.
• Predispus la supraadaptare – Deoarece algoritmul este afectat din cauza blestemului dimensionalității, este predispus și la problema supraajustării. Prin urmare, în general selectarea caracteristicilor precum și reducerea dimensionalității sunt aplicate tehnici pentru a rezolva această problemă.

Exemplu de program:

Să presupunem că 0 și 1 sunt cei doi clasificatori (grupuri).

C++

>                      
 // Java program to find groups of unknown> // Points using K nearest neighbour algorithm.> import> java.io.*;> import> java.util.*;> class> GFG {> >static> class> Point {> >int> val;>// Group of point> >double> x, y;>// Co-ordinate of point> >double> distance;>// Distance from test point> >}> >// Used to sort an array of points by increasing> >// order of distance> >static> class> comparison>implements> Comparator {> >public> int> compare(Point a, Point b)> >{> >if> (a.distance   return -1;  else if (a.distance>b.distanta) retur 1;  returnează 0;  } } // Această funcție găsește clasificarea punctului p folosind // k algoritmul celui mai apropiat vecin. Presupune doar două // grupuri și returnează 0 dacă p aparține grupului 0, altfel // 1 (aparține grupului 1).  static int classifyAPoint(Punctul arr[], int n, int k, Punctul p) { // Completați distanțele tuturor punctelor de la p pentru (int i = 0; i arr[i].distanță = Math.sqrt( (arr[ i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)); // Sortează punctele după distanța de la p Arrays.sort(arr, new comparison() // Acum considerăm primele k elemente și doar // două grupuri int freq1 = 0 // Frecvența grupului 0 int freq2 = 0; (int i = 0; i dacă (arr[i].val == 0) frecvență1++; altfel dacă (arr[i].val == 1) frecvență2++; } return (frecvență1> frecvență2 ? 0 : 1); } / / Driver code public static void main(String[] args) { int n = 17 // Număr de puncte de date Point[] arr = new Point[n] pentru (int i = 0; i<17; i++) {  arr[i] = new Point();  }  arr[0].x = 1;  arr[0].y = 12;  arr[0].val = 0;  arr[1].x = 2;  arr[1].y = 5;  arr[1].val = 0;  arr[2].x = 5;  arr[2].y = 3;  arr[2].val = 1;  arr[3].x = 3;  arr[3].y = 2;  arr[3].val = 1;  arr[4].x = 3;  arr[4].y = 6;  arr[4].val = 0;  arr[5].x = 1.5;  arr[5].y = 9;  arr[5].val = 1;  arr[6].x = 7;  arr[6].y = 2;  arr[6].val = 1;  arr[7].x = 6;  arr[7].y = 1;  arr[7].val = 1;  arr[8].x = 3.8;  arr[8].y = 3;  arr[8].val = 1;  arr[9].x = 3;  arr[9].y = 10;  arr[9].val = 0;  arr[10].x = 5.6;  arr[10].y = 4;  arr[10].val = 1;  arr[11].x = 4;  arr[11].y = 2;  arr[11].val = 1;  arr[12].x = 3.5;  arr[12].y = 8;  arr[12].val = 0;  arr[13].x = 2;  arr[13].y = 11;  arr[13].val = 0;  arr[14].x = 2;  arr[14].y = 5;  arr[14].val = 1;  arr[15].x = 2;  arr[15].y = 9;  arr[15].val = 0;  arr[16].x = 1;  arr[16].y = 7;  arr[16].val = 0;  /*Testing Point*/  Point p = new Point();  p.x = 2.5;  p.y = 7;  // Parameter to decide group of the testing point  int k = 3;  System.out.println(  'The value classified to unknown point is '  + classifyAPoint(arr, n, k, p));  } } // This code is contributed by Karandeep1234>
    
>
    
>
 
Python3
                    
 import> math> def> classifyAPoint(points,p,k>=>3>):> >'''> >This function finds the classification of p using> >k nearest neighbor algorithm. It assumes only two> >groups and returns 0 if p belongs to group 0, else> >1 (belongs to group 1).> >Parameters -> >points: Dictionary of training points having two keys - 0 and 1> >Each key have a list of training data points belong to that> >p : A tuple, test data point of the form (x,y)> >k : number of nearest neighbour to consider, default is 3> >'''> >distance>=>[]> >for> group>in> points:> >for> feature>in> points[group]:> >#calculate the euclidean distance of p from training points> >euclidean_distance>=> math.sqrt((feature[>0>]>->p[>0>])>*>*>2> +>(feature[>1>]>->p[>1>])>*>*>2>)> ># Add a tuple of form (distance,group) in the distance list> >distance.append((euclidean_distance,group))> ># sort the distance list in ascending order> ># and select first k distances> >distance>=> sorted>(distance)[:k]> >freq1>=> 0> #frequency of group 0> >freq2>=> 0> #frequency og group 1> >for> d>in> distance:> >if> d[>1>]>=>=> 0>:> >freq1>+>=> 1> >elif> d[>1>]>=>=> 1>:> >freq2>+>=> 1> >return> 0> if> freq1>frecvență2>>>.> >format>(classifyAPoint(points,p,k)))> if> __name__>=>=> '__main__'>:> >main()> 
    
>
    
>
 
C#
                    
 using> System;> using> System.Collections;> using> System.Collections.Generic;> using> System.Linq;> // C# program to find groups of unknown> // Points using K nearest neighbour algorithm.> class> Point {> >public> int> val;>// Group of point> >public> double> x, y;>// Co-ordinate of point> >public> int> distance;>// Distance from test point> }> class> HelloWorld {> >// This function finds classification of point p using> >// k nearest neighbour algorithm. It assumes only two> >// groups and returns 0 if p belongs to group 0, else> >// 1 (belongs to group 1).> >public> static> int> classifyAPoint(List arr,>int> n,>int> k, Point p)> >{> >// Fill distances of all points from p> >for> (>int> i = 0; i   arr[i].distance = (int)Math.Sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y));  // Sort the Points by distance from p  arr.Sort(delegate(Point x, Point y) {  return x.distance.CompareTo(y.distance);  });  // Now consider the first k elements and only  // two groups  int freq1 = 0; // Frequency of group 0  int freq2 = 0; // Frequency of group 1  for (int i = 0; i   if (arr[i].val == 0)  freq1++;  else if (arr[i].val == 1)  freq2++;  }  return (freq1>frecvență 2? 0 : 1);  } static void Main() { int n = 17; // Numărul de puncte de date List arr = new List();  for(int i = 0; i arr.Add(new Point()); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1] .x = 2; arr[1].y = 0; arr[2].val = 1; arr[3].x = 3; arr[3].val = 1; arr[4].y = 6; val = 0; arr[5].x = 1,5; arr[6].x = 2; [6].val = 1; arr[7].x = 1; arr[8].x; = 3; arr[8].val = arr[9].x = 10; arr[10].x; 10].y = 4; arr[10].val = 1; arr[11].x = 1; 3,5; arr[12].y = 0 arr[13].x = 11; ].x = 2; arr[14].y = 1; arr[15].y = 0; ; arr[16].x = 1; arr[16].val = 0; Punct p = p.y = 7; // Parametru pentru a decide grupul punctului de testare int k = 3;  Console.WriteLine('Valoarea clasificată la punctul necunoscut este ' + classifyAPoint(arr, n, k, p));  } } // Codul este contribuit de Nidhi goel.>>>
    
>                      
 class Point {> >constructor(val, x, y, distance) {> >this>.val = val;>// Group of point> >this>.x = x;>// X-coordinate of point> >this>.y = y;>// Y-coordinate of point> >this>.distance = distance;>// Distance from test point> >}> }> // Used to sort an array of points by increasing order of distance> class Comparison {> >compare(a, b) {> >if> (a.distance   return -1;  } else if (a.distance>b.distanta) { intoarcere 1;  } returnează 0;  } } // Această funcție găsește clasificarea punctului p folosind // k algoritmul celui mai apropiat vecin. Presupune doar două // grupuri și returnează 0 dacă p aparține grupului 0, altfel // 1 (aparține grupului 1). function classifyAPoint(arr, n, k, p) { // Completați distanțele tuturor punctelor de la p pentru (fie i = 0; i arr[i].distance = Math.sqrt((arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y) } // Sortează punctele după distanța de la p arr.sort (nou Comparison()); // Acum considerăm primele k elemente și numai două grupuri fie frecvența1 = 0 // Frecvența grupului 0 fie frecvența grupului 1 pentru (fie i = 0; i dacă; [i].val === 0) { freq1++ } else if (arr[i].val === 1) { freq2++ } return freq1> freq2 } // Driver code const; 17; // Număr de puncte de date const arr = new Array(n);<17; i++) {  arr[i] = new Point(); } arr[0].x = 1; arr[0].y = 12; arr[0].val = 0; arr[1].x = 2; arr[1].y = 5; arr[1].val = 0; arr[2].x = 5; arr[2].y = 3; arr[2].val = 1; arr[3].x = 3; arr[3].y = 2; arr[3].val = 1; arr[4].x = 3; arr[4].y = 6; arr[4].val = 0; arr[5].x = 1.5; arr[5].y = 9; arr[5].val = 1; arr[6].x = 7; arr[6].y = 2; arr[6].val = 1; arr[7].x = 6; arr[7].y = 1; arr[7].val = 1; arr[8].x = 3.8; arr[8].y = 3; arr[8].val = 1; arr[9].x = 3; arr[9].y = 10; arr[9].val = 0; arr[10].x = 5.6; arr[10].y = 4; arr[10].val = 1; arr[11].x = 4 arr[11].y = 2; arr[11].val = 1; arr[12].x = 3.5; arr[12].y = 8; arr[12].val = 0; arr[13].x = 2; arr[13].y = 11; arr[13].val = 0; arr[14].x = 2; arr[14].y = 5; arr[14].val = 1; arr[15].x = 2; arr[15].y = 9; arr[15].val = 0; arr[16].x = 1; arr[16].y = 7; arr[16].val = 0; // Testing Point let p = {  x: 2.5,  y: 7,  val: -1, // uninitialized }; // Parameter to decide group of the testing point let k = 3; console.log(  'The value classified to unknown point is ' +  classifyAPoint(arr, n, k, p) ); function classifyAPoint(arr, n, k, p) {  // Fill distances of all points from p  for (let i = 0; i   arr[i].distance = Math.sqrt(  (arr[i].x - p.x) * (arr[i].x - p.x) + (arr[i].y - p.y) * (arr[i].y - p.y)  );  }  // Sort the Points by distance from p  arr.sort(function (a, b) {  if (a.distance return -1;  else if (a.distance>b.distanta) retur 1;  returnează 0;  });  // Acum considerăm primele k elemente și doar două grupuri fie freq1 = 0; // Frecvența grupului 0 fie frecvența2 = 0; // Frecvența grupului 1 pentru (fie i = 0; i dacă (arr[i].val == 0) frecvență1++; altfel dacă (arr[i].val == 1) frecvență2++; } returnează frecvență1> frecvență2 ? 0 : 1; }>>>
    
>        Ieșire:    
 
The value classified as an unknown point is 0.>
    Complexitatea timpului:    O(N * logN)  
    Spațiu auxiliar:    O(1)
 
Aplicații ale algoritmului KNN
    Preprocesarea datelor    – În timp ce ne confruntăm cu orice problemă de învățare automată, efectuăm mai întâi Imputați KNN care este destul de eficient și utilizat în general pentru metodologii sofisticate de imputare.
    Recunoasterea formelor    – Algoritmii KNN funcționează foarte bine dacă ați antrenat un algoritm KNN folosind setul de date MNIST și apoi ați efectuat procesul de evaluare, atunci trebuie să fi dat peste faptul că acuratețea este prea mare.
    Motoare de recomandare    – Sarcina principală care este efectuată de un algoritm KNN este de a atribui un nou punct de interogare unui grup preexistent care a fost creat folosind un corpus imens de seturi de date. Acesta este exact ceea ce se cere în   K Cei mai apropiati vecini cu Python | ML  
  Implementarea K-Nearest Neighbours de la zero folosind Python  
  Explicația matematică a K-Nearest Neighbor  
  K-NN ponderat  
 Întrebări frecvente (FAQs) 
 Î. De ce KNN învață leneș? 
 
 Algoritmul KNN nu construiește un model în timpul fazei de antrenament. Algoritmul memorează întregul set de date de antrenament și efectuează acțiuni asupra setului de date în momentul clasificării. 
   
 Î. De ce KNN este neparametric? 
 
 Algoritmul KNN nu face ipoteze cu privire la datele pe care le analizează. 
   
 Î. Care este diferența dintre KNN și K înseamnă? 
 
 KNN este un model de învățare automată supravegheat utilizat pentru probleme de clasificare, în timp ce K-means este un model de învățare automată nesupravegheat utilizat pentru grupare. 
 K în KNN este numărul de vecini cei mai apropiați, în timp ce K în K înseamnă numărul de clustere.