El Algorisme K-Nearest Neighbors (KNN). és un mètode d'aprenentatge automàtic supervisat que s'utilitza per abordar problemes de classificació i regressió. Evelyn Fix i Joseph Hodges van desenvolupar aquest algorisme el 1951, que va ser ampliat posteriorment per Thomas Cover. L'article explora els fonaments, el funcionament i la implementació de l'algorisme KNN.

Què és l'algoritme K-Nearest Neighbors?

KNN és ​​un dels algorismes de classificació més bàsics però essencials en l'aprenentatge automàtic. Pertany a la aprenentatge supervisat domini i troba una intensa aplicació en el reconeixement de patrons, És àmpliament d'un sol ús en escenaris de la vida real, ja que no és paramètric, és a dir, no fa cap hipòtesi subjacent sobre la distribució de dades (a diferència d'altres algorismes com el GMM, que assumeixen una Distribució gaussiana de les dades proporcionades). Ens donen algunes dades prèvies (també anomenades dades d'entrenament), que classifiquen les coordenades en grups identificats per un atribut.

mides de lletra en làtex

Com a exemple, considereu la següent taula de punts de dades que conté dues característiques:

Visualització de treball de l'algoritme KNN

Ara, donat un altre conjunt de punts de dades (també anomenats dades de prova), assigneu aquests punts a un grup mitjançant l'anàlisi del conjunt d'entrenament. Tingueu en compte que els punts no classificats estan marcats com a 'Blanc'.

Intuïció darrere de l'algoritme KNN

Si tracem aquests punts en un gràfic, podrem localitzar alguns clústers o grups. Ara, donat un punt no classificat, podem assignar-lo a un grup observant a quin grup pertanyen els seus veïns més propers. Això significa que un punt proper a un grup de punts classificats com a 'Vermell' té una probabilitat més alta de ser classificat com a 'Vermell'.

Intuïtivament, podem veure que el primer punt (2.5, 7) s'hauria de classificar com a 'Verd', i el segon punt (5.5, 4.5) s'hauria de classificar com a 'Vermell'.

Per què necessitem un algorisme KNN?

L'algorisme (K-NN) és un algorisme d'aprenentatge automàtic versàtil i àmpliament utilitzat que s'utilitza principalment per la seva simplicitat i facilitat d'implementació. No requereix cap hipòtesi sobre la distribució de dades subjacent. També pot gestionar dades tant numèriques com categòriques, la qual cosa la converteix en una opció flexible per a diversos tipus de conjunts de dades en tasques de classificació i regressió. És un mètode no paramètric que fa prediccions basades en la similitud dels punts de dades en un conjunt de dades determinat. K-NN és ​​menys sensible als valors atípics en comparació amb altres algorismes.

L'algorisme K-NN funciona trobant els K veïns més propers a un punt de dades donat en funció d'una mètrica de distància, com ara la distància euclidiana. Aleshores, la classe o el valor del punt de dades es determina pel vot majoritari o la mitjana dels K veïns. Aquest enfocament permet que l'algoritme s'adapti a diferents patrons i faci prediccions basades en l'estructura local de les dades.

Mètriques de distància utilitzades a l'algoritme KNN

Com sabem que l'algorisme KNN ens ajuda a identificar els punts més propers o els grups d'un punt de consulta. Però per determinar els grups més propers o els punts més propers per a un punt de consulta necessitem alguna mètrica. Per a això, utilitzem les mètriques de distància següents:

Distància euclidiana

Això no és més que la distància cartesiana entre els dos punts que es troben en el pla/hiperpla. Distància euclidiana també es pot visualitzar com la longitud de la recta que uneix els dos punts que es tenen en compte. Aquesta mètrica ens ajuda a calcular el desplaçament net realitzat entre els dos estats d'un objecte.

Distància de Manhattan

Distància de Manhattan La mètrica s'utilitza generalment quan ens interessa la distància total recorreguda per l'objecte en lloc del desplaçament. Aquesta mètrica es calcula sumant la diferència absoluta entre les coordenades dels punts en n dimensions.

Distància de Minkowski

Podem dir que l'Euclidià, així com la distància de Manhattan, són casos especials de la Distància de Minkowski .

A partir de la fórmula anterior podem dir que quan p = 2 és el mateix que la fórmula de la distància euclidiana i quan p = 1 obtenim la fórmula de la distància de Manhattan.

Les mètriques comentades anteriorment són més habituals quan es tracta d'a Aprenentatge automàtic problema, però també hi ha altres mètriques de distància com Distància de Hamming que són útils per tractar problemes que requereixen comparacions superposades entre dos vectors el contingut dels quals pot ser booleà i valors de cadena.

Com triar el valor de k per a l'algoritme KNN?

El valor de k és molt crucial en l'algorisme KNN per definir el nombre de veïns de l'algorisme. El valor de k en l'algorisme de k-veïns més propers (k-NN) s'ha de triar en funció de les dades d'entrada. Si les dades d'entrada tenen més valors atípics o soroll, seria millor un valor de k més alt. Es recomana triar un valor senar per a k per evitar empats en la classificació. Validació creuada Els mètodes poden ajudar a seleccionar el millor valor k per al conjunt de dades donat.

Funcionament de l'algorisme KNN

L'algorisme K-Nearest Neighbors (KNN) funciona segons el principi de similitud, on prediu l'etiqueta o el valor d'un nou punt de dades tenint en compte les etiquetes o els valors dels seus K veïns més propers al conjunt de dades d'entrenament.

nombre de palíndrom

A continuació s'explica l'explicació pas a pas de com funciona KNN:

Pas 1: selecció del valor òptim de K

• K representa el nombre de veïns més propers que cal tenir en compte per fer la predicció.

Pas 2: Càlcul de la distància

• Per mesurar la similitud entre els punts de dades objectiu i d'entrenament, s'utilitza la distància euclidiana. La distància es calcula entre cadascun dels punts de dades del conjunt de dades i el punt objectiu.

Pas 3: Trobar els veïns més propers

• Els k punts de dades amb les distàncies més petites al punt objectiu són els veïns més propers.

Pas 4: votar per a la classificació o fer la mitjana per a la regressió

• En el problema de classificació, les etiquetes de classe de es determinen mitjançant la votació majoritària. La classe amb més ocurrències entre els veïns es converteix en la classe prevista per al punt de dades objectiu.
• En el problema de regressió, l'etiqueta de classe es calcula fent la mitjana dels valors objectiu de K veïns més propers. El valor mitjà calculat es converteix en la sortida prevista per al punt de dades objectiu.

Sigui X el conjunt de dades d'entrenament amb n punts de dades, on cada punt de dades està representat per un vector de característiques d-dimensionals i Y siguin les etiquetes o valors corresponents per a cada punt de dades a X. Donat un nou punt de dades x, l'algorisme calcula la distància entre x i cada punt de dades. en X utilitzant una mètrica de distància, com ara la distància euclidiana:

L'algorisme selecciona els K punts de dades de X que tenen les distàncies més curtes a x. Per a les tasques de classificació, l'algorisme assigna l'etiqueta y que és més freqüent entre els K veïns més propers a x. Per a les tasques de regressió, l'algoritme calcula la mitjana o mitjana ponderada dels valors y dels K veïns més propers i l'assigna com a valor previst per a x.

Avantatges de l'algoritme KNN

• Fàcil d'implementar ja que la complexitat de l'algorisme no és tan alta.
• S'adapta fàcilment - Segons el funcionament de l'algorisme KNN, emmagatzema totes les dades a l'emmagatzematge de memòria i, per tant, cada vegada que s'afegeix un nou exemple o punt de dades, l'algoritme s'ajusta segons aquest nou exemple i també té la seva contribució a les prediccions futures.
• Hiperparàmetres pocs – Els únics paràmetres que es requereixen en l'entrenament d'un algorisme KNN són el valor de k i l'elecció de la mètrica de distància que voldríem triar de la nostra mètrica d'avaluació.

Inconvenients de l'algoritme KNN

• No escala – Com hem sentit parlar d'això, l'algoritme KNN també es considera un algorisme mandros. El significat principal d'aquest terme és que això requereix molta potència de càlcul i emmagatzematge de dades. Això fa que aquest algorisme consumeixi temps i esgoti els recursos.
• Maledicció de la dimensionalitat – Hi ha un terme conegut com a fenomen del pic segons aquest, l'algoritme KNN es veu afectat pel maledicció de la dimensionalitat la qual cosa implica que l'algorisme s'enfronta a dificultats per classificar correctament els punts de dades quan la dimensionalitat és massa alta.
• Propens al sobreajustament – Com que l'algoritme es veu afectat a causa de la maledicció de la dimensionalitat, també és propens al problema del sobreajustament. Per tant en general selecció de característiques així com reducció de la dimensionalitat s'apliquen tècniques per fer front a aquest problema.

Exemple de programa:

Suposem 0 i 1 com els dos classificadors (grups).

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.distància) retorn 1;  retorn 0;  } } // Aquesta funció troba la classificació del punt p utilitzant // k algorisme del veí més proper. Assumeix només dos // grups i retorna 0 si p pertany al grup 0, en cas contrari // 1 (pertany al grup 1).  static int classifyAPoint(Point arr[], int n, int k, Point p) { // Omple les distàncies de tots els punts des de p per (int 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) // Ordena els punts per distància de p Arrays.sort(arr, new comparison() // Considereu ara els primers k elements i només // dos grups int freq1 = 0 // Freqüència del grup 0 int freq2 = 0; (int i = 0; i si (arr[i].val == 0) freq1++; sinó si (arr[i].val == 1) freq2++; } retorn (freq1> freq2 ? 0 : 1); } / / Codi del controlador public static void main(String[] args) { int n = 17 // Nombre de punts de dades Point[] arr = new Point[n] per (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>
    
>
    
>
 
Python 3
                    
 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>freqüència2>>>1> # driver function> def> main():> ># Dictionary of training points having two keys - 0 and 1> ># key 0 have points belong to class 0> ># key 1 have points belong to class 1> >points>=> {>0>:[(>1>,>12>),(>2>,>5>),(>3>,>6>),(>3>,>10>),(>3.5>,>8>),(>2>,>11>),(>2>,>9>),(>1>,>7>)],> >1>:[(>5>,>3>),(>3>,>2>),(>1.5>,>9>),(>7>,>2>),(>6>,>1>),(>3.8>,>1>),(>5.6>,>4>),(>4>,>2>),(>2>,>5>)]}> ># testing point p(x,y)> >p>=> (>2.5>,>7>)> ># Number of neighbours> >k>=> 3> >print>(>'The value classified to unknown point is: {}'>.> >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>freqüència 2? 0: 1);  } static void Principal() { int n = 17; // Nombre de punts de dades 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 = 5; arr[2].x = 3; arr[3].x = 3; arr[3].val = 1; arr[4].y = 6; val = 0; arr[5].x = 1,5; arr[5].val = 7; [6].val = 1; arr[7].x = 6; arr[7].val = 3,8; = 3; arr[8].val = 1 arr[9].x = 10; arr[10].x; 10].y = 4; arr[10].val = 1; arr[11].x = 1; 3,5; arr[12].y = 8; arr[13].x = 11; ].x = 2; arr[14].y = 5; arr[15].x = 9; ; arr[16].x = 1; arr[16].val = 0 Punt p = p.x = 7; // Paràmetre per decidir el grup del punt de prova int k = 3;  Console.WriteLine('El valor classificat com a punt desconegut és ' + classifyAPoint(arr, n, k, p));  } } // El codi és aportat per 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.distància) { retorn 1;  } retorna 0;  } } // Aquesta funció troba la classificació del punt p utilitzant // k algorisme del veí més proper. Assumeix només dos // grups i retorna 0 si p pertany al grup 0, en cas contrari // 1 (pertany al grup 1). function classifyAPoint(arr, n, k, p) { // Ompliu les distàncies de tots els punts des de p per (sigui 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) } // Ordena els punts per distància des de p arr.sort (nou Comparació()); // Considereu ara els primers k elements i només dos grups siguin freq1 = 0 // Freqüència del grup 0 siguin freq2 = 0 (det i = 0; i si; [i].val === 0) { freq1++ } else if (arr[i].val === 1) { freq2++ } } return freq1> freq2 } // Codi del controlador n = 17; // Nombre de punts de dades 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.distància) retorn 1;  retorn 0;  });  // Considereu ara els primers k elements i només dos grups siguin freq1 = 0; // Freqüència del grup 0 deixem freq2 = 0; // Freqüència del grup 1 per (deixar i = 0; i si (arr[i].val == 0) freq1++; sinó si (arr[i].val == 1) freq2++; } retorn freq1> freq2 ? 0 : 1; }>>>
    
>        Sortida:    
 
The value classified as an unknown point is 0.>
    Complexitat temporal:    O(N * logN)  
    Espai auxiliar:    O(1)
 
Aplicacions de l'algoritme KNN
    Preprocessament de dades    – Mentre tractem qualsevol problema d'aprenentatge automàtic, primer realitzem el Imputació de KNN que és força eficaç i s'utilitza generalment per a metodologies d'imputació sofisticades.
    Reconeixement de patró    – Els algorismes KNN funcionen molt bé si heu entrenat un algorisme KNN amb el conjunt de dades MNIST i després heu realitzat el procés d'avaluació, haureu d'haver trobat el fet que la precisió és massa alta.
    Motors de recomanació    – La tasca principal que realitza un algorisme KNN és ​​assignar un nou punt de consulta a un grup preexistent que s'ha creat utilitzant un gran corpus de conjunts de dades. Això és exactament el que es requereix al   K Veïns més propers amb Python | ML  
  Implementació de K-Nearest Neighbors des de zero mitjançant Python  
  Explicació matemàtica de K-Nearest Neighbor  
  K-NN ponderat  
 Preguntes freqüents (FAQ) 
 P. Per què KNN és ​​un aprenent gandul? 
 
 L'algorisme KNN no construeix un model durant la fase d'entrenament. L'algorisme recorda tot el conjunt de dades d'entrenament i realitza accions sobre el conjunt de dades en el moment de la classificació. 
   
 P. Per què KNN no és paramètric? 
 
 L'algoritme KNN no fa suposicions sobre les dades que està analitzant. 
   
 P. Quina diferència hi ha entre KNN i K significa? 
 
 KNN és ​​un model d'aprenentatge automàtic supervisat que s'utilitza per a problemes de classificació, mentre que K-means és un model d'aprenentatge automàtic no supervisat utilitzat per a l'agrupació. 
 La K en KNN és ​​el nombre de veïns més propers, mentre que la K en K significa el nombre de clústers.