k vecinos más próximos

El método de los k vecinos más cercanos (en inglés: k-nearest neighbors, abreviado $k$-nn)​ es un método de clasificación supervisada (Aprendizaje, estimación basada en un conjunto de formación y prototipos) que sirve para estimar la función de densidad $F(x/Cj)$ de las predictoras $x$ por cada clase $C_{j}$.

Este es un método de clasificación no paramétrico, que estima el valor de la función de densidad de probabilidad o directamente la probabilidad a posteriori de que un elemento $x$ pertenezca a la clase $C_{j}$ a partir de la información proporcionada por el conjunto de prototipos. En el proceso de aprendizaje no se hace ninguna suposición acerca de la distribución de las variables predictoras.

En el reconocimiento de patrones, el algoritmo $k$-nn es usado como método de clasificación de objetos (elementos) basado en una formación mediante ejemplos cercanos en el espacio de los elementos. $k$-nn es un tipo de aprendizaje vago (lazy learning), donde la función se aproxima solo localmente y todo el cómputo es diferido a la clasificación. La normalización de datos puede mejorar considerablemente la exactitud del algoritmo $k$-nn.​​

Algoritmo

Ejemplo del algoritmo Knn. El ejemplo que se desea clasificar es el círculo verde. Para k = 3 este es clasificado con la clase triángulo, ya que hay solo un cuadrado y 2 triángulos, dentro del círculo que los contiene. Si k = 5 este es clasificado con la clase cuadrado, ya que hay 2 triángulos y 3 cuadrados, dentro del círculo externo.

Los ejemplos de formación son vectores en un espacio característico multidimensional, cada ejemplo está descrito en términos de $p$ atributos considerando $q$ clases para la clasificación. Los valores de los atributos del $i$-ésimo ejemplo (donde $1\leq i\leq n$) se representan por el vector $p$-dimensional

$x_{i}=(x_{1i},x_{2i},...,x_{pi})\in X$

El espacio es particionado en regiones por localizaciones y etiquetas de los ejemplos de formación. Un punto en el espacio es asignado a la clase $C$ si esta es la clase más frecuente entre los k ejemplos de formación más cercanos. Generalmente se usa la distancia euclidiana.

$d(x_{i},x_{j})={\sqrt {\sum _{r=1}^{p}(x_{ri}-x_{rj})^{2}}}$

La fase de formación del algoritmo consiste en almacenar los vectores característicos y las etiquetas de las clases de los ejemplos de formación. En la fase de clasificación, la evaluación del ejemplo (del que no se conoce su clase) es representada por un vector en el espacio característico. Se calcula la distancia entre los vectores almacenados y el nuevo vector, y se seleccionan los $k$ ejemplos más cercanos. El nuevo ejemplo es clasificado con la clase que más se repite en los vectores seleccionados.

Este método supone que los vecinos más cercanos nos dan la mejor clasificación y esto se hace utilizando todos los atributos; el problema de dicha suposición es que es posible que se tengan muchos atributos irrelevantes que dominen sobre la clasificación: dos atributos relevantes perderían peso entre otros veinte irrelevantes.

Para corregir el posible sesgo se puede asignar un peso a las distancias de cada atributo, dándole así mayor importancia a los atributos más relevantes. Otra posibilidad consiste en tratar de determinar o ajustar los pesos con ejemplos conocidos de formación. Finalmente, antes de asignar pesos es recomendable identificar y eliminar los atributos que se consideran irrelevantes.

En síntesis, el método $k$-nn se resume en dos algoritmos:

Algoritmo de formación

Para cada ejemplo $\langle x,f(x)\rangle$ , donde $x\in X$, agregar el ejemplo a la estructura representando los ejemplos de aprendizaje.

Algoritmo de clasificación

Dado un ejemplar $x_{q}$ que debe ser clasificado, sean $x_{1},...,x_{k}$ los $k$ vecinos más cercanos a $x_{q}$ en los ejemplos de aprendizaje, regresar

${\hat {f}}(x)\leftarrow \arg \max _{v\in V}\sum _{i=1}^{k}[v=f(x_{i})]$

donde usamos la notación de corchete de Iverson.

El valor ${\hat {f}}(x_{q})$ devuelto por el algoritmo como un estimador de $f(x_{q})$ es solo el valor más común de $f$ entre los $k$ vecinos más cercanos a $x_{q}$. Si elegimos $k=1$; entonces el vecino más cercano a $x_{i}$ determina su valor.

Elección del $k$

La mejor elección de $k$ depende fundamentalmente de los datos; generalmente, valores grandes de $k$ reducen el efecto de ruido en la clasificación, pero crean límites entre clases parecidas. Un buen $k$ puede ser seleccionado mediante una optimización de uso. El caso especial en que la clase es predicha para ser la clase más cercana al ejemplo de formación (cuando $k=1$) es llamada Nearest Neighbor Algorithm, Algoritmo del vecino más cercano.

La exactitud de este algoritmo puede ser severamente degradada por la presencia de ruido o características irrelevantes, o si las escalas de características no son consistentes con lo que uno considera importante. Muchas investigaciones y esfuerzos fueron puestos en la selección y crecimiento de características para mejorar las clasificaciones. Particularmente una aproximación en el uso de algoritmos que evolucionan para optimizar características de escalabilidad. Otra aproximación consiste en escalar características por la información mutua de los datos de formación con las clases de formación.

Posibles variantes del algoritmo básico

Vecinos más cercanos con distancia ponderada

Se puede ponderar la contribución de cada vecino de acuerdo a la distancia entre él y el ejemplar a ser clasificado $x_{q}$, dando mayor peso a los vecinos más cercanos. Por ejemplo podemos ponderar el voto de cada vecino de acuerdo al cuadrado inverso de sus distancias

${\hat {f}}(x_{q})\leftarrow \arg \max _{v\in V}\sum _{i=1}^{k}w_{i}[v=f(x_{i})]$

donde

$w_{i}\equiv {\frac {1}{d(x_{q},x_{i})^{2}}}$

De esta manera se ve que no hay riesgo de permitir a todos los ejemplos formación contribuir a la clasificación de $x_{q}$, ya que al ser muy distantes no tendrían peso asociado. La desventaja de considerar todos los ejemplos sería su lenta respuesta (método global). Se quiere siempre tener un método local en el que solo los vecinos más cercanos son considerados.

Esta mejora es muy efectiva en muchos problemas prácticos. Es robusto ante los ruidos de datos y suficientemente efectivo en conjuntos de datos grandes. Se puede ver que al tomar promedios ponderados de los $k$ vecinos más cercanos el algoritmo puede evitar el impacto de ejemplos con ruido aislados.

Regresión $k$-nn

Como otras regresiones se trata de un algoritmo para estimar una variable continua $X$. El conjunto de formación es una muestra $M$ de un espacio métrico (vectorial) $V$. El modelo formado es una función ${\overline {X}}$ que a cada elemento $v\in V$ fuera de $M$ asigna la media de $\lbrace X(m_{i})\mid 1\leq i\leq k\rbrace$ donde los puntos $\lbrace m_{i}\mid 1\leq i\leq k\rbrace$ son los $k$ elementos de la muestra más próximos a $v$.

Referencias

• Datos: Q1071612