k vecinos más próximos

(Redirigido desde «K-nearest neighbors»)

El método de los k vecinos más cercanos (en inglés: k-nearest neighbors, abreviado -nn)[1]​ 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 de las predictoras por cada clase .

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 pertenezca a la clase 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 -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. -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 -nn.[2][3]

Algoritmo

editar
 
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   atributos considerando   clases para la clasificación. Los valores de los atributos del  -ésimo ejemplo (donde  ) se representan por el vector  -dimensional

 

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   si esta es la clase más frecuente entre los k ejemplos de formación más cercanos. Generalmente se usa la distancia euclidiana.

 

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   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  -nn se resume en dos algoritmos:

Algoritmo de formación

editar

Para cada ejemplo   , donde  , agregar el ejemplo a la estructura representando los ejemplos de aprendizaje.

Algoritmo de clasificación

editar

Dado un ejemplar   que debe ser clasificado, sean   los   vecinos más cercanos a   en los ejemplos de aprendizaje, regresar

 

donde usamos la notación de corchete de Iverson.

El valor   devuelto por el algoritmo como un estimador de   es solo el valor más común de   entre los   vecinos más cercanos a  . Si elegimos  ; entonces el vecino más cercano a   determina su valor.

Elección del

editar

La mejor elección de   depende fundamentalmente de los datos; generalmente, valores grandes de   reducen el efecto de ruido en la clasificación, pero crean límites entre clases parecidas. Un buen   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  ) 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

editar

Vecinos más cercanos con distancia ponderada

editar

Se puede ponderar la contribución de cada vecino de acuerdo a la distancia entre él y el ejemplar a ser clasificado  , 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

 

donde

 

De esta manera se ve que no hay riesgo de permitir a todos los ejemplos formación contribuir a la clasificación de  , 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   vecinos más cercanos el algoritmo puede evitar el impacto de ejemplos con ruido aislados.

Regresión -nn

editar

Como otras regresiones se trata de un algoritmo para estimar una variable continua  . El conjunto de formación es una muestra   de un espacio métrico (vectorial)  . El modelo formado es una función   que a cada elemento   fuera de   asigna la media de   donde los puntos   son los   elementos de la muestra más próximos a  .

Referencias

editar
  1. Fix, E.; Hodges, J.L. (1989). «(1951): An Important Contribution to Nonparametric Discriminant Analysis and Density Estimation: Commentary on Fix and Hodges (1951)». International Statistical Review / Revue Internationale de Statistique 57 (3): 233-238. doi:10.2307/1403796. .
  2. Piryonesi, S. Madeh; El-Diraby, Tamer E. (2020-06). «Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems». Journal of Transportation Engineering, Part B: Pavements (en inglés) 146 (2): 04020022. ISSN 2573-5438. doi:10.1061/JPEODX.0000175. Consultado el 7 de agosto de 2020. 
  3. Hastie, Trevor.; Friedman, J. H. (Jerome H.) (2001). The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. Springer. ISBN 0-387-95284-5. OCLC 46809224. Consultado el 7 de agosto de 2020.