K-Nearest Neighbour

KNN es un algoritmo de Inteligencia Artificial que clasifica datos por proximidad.

Existen métodos de lazy evaluation que no tienen un proceso previo de entrenamiento, sino que intentan clasificar recién cunado llega una nueva instancia. Estos métodos lazy se caracterizan por tres propiedades:

1. Evaluación posterior a la llegada de una instancia.
2. Clasificación de acuerdo a instanias similares.
3. Necesitan representar las instancias en espacios $r$-dimensionales.

El algoritmo tiene dos etapas:

$$\begin{array}{rl}& \text{Training algorithm }\\ & \text{for each training example }<x,f(x)>:\\ & \text{add the example to the list training\_examples}\end{array}$$ $$\begin{array}{rl}& \text{Classification algorithm }\\ & \text{given a query instance xq to be classified:}\\ & \text{let x1…xk denote the k instances from training\_examples that are nearest to xq}\\ & \text{return f^(xq)⟵v∈Vargmax∑i=1kδ(v,f(xi))}\\ & \text{where δ(a,b)=1 if a=b and where δ(a,b)=0 otherwise.}\end{array}$$

Una variante de KNN es el KNN ponderado.