¿Qué son los k vecinos más cercanos (kNN)?

Definición

El algoritmo de los k vecinos más cercanos (kNN) es un método de aprendizaje supervisado que clasifica un punto según la clase mayoritaria de sus k puntos almacenados más cercanos.

kNN no tiene un paso explícito de entrenamiento. Almacena los ejemplos etiquetados y hace su cálculo cuando llega una consulta. Scikit-learn lo llama aprendizaje basado en instancias, sin generalización.

Funcionamiento

1. Elija k y una medida de distancia. La distancia euclidiana es la opción más habitual.
2. Busque los k puntos almacenados más cercanos al punto de consulta.
3. Asigne al punto de consulta la clase que tienen la mayoría de esos k puntos.

Por defecto, cada vecino tiene un voto. En el kNN ponderado, los vecinos más cercanos cuentan más, por ejemplo con un peso de 1/d, donde d es la distancia al vecino.

Elección de k

El mejor valor de k depende de los datos. Un k mayor suprime el ruido, pero hace que los límites de clase sean menos nítidos. La validación cruzada encuentra un buen valor de k a partir de los datos. Para dos clases, un k impar evita los empates en la votación.

Límites

• Si las características tienen unidades o escalas distintas, normalizar cada característica puede mejorar mucho la precisión.
• Una búsqueda por fuerza bruta compara la consulta con cada punto almacenado. Esto resulta inviable cuando crece el número de puntos.
• La búsqueda basada en árboles, como un árbol KD, es rápida solo en dimensiones bajas (por debajo de unas 20). En dimensiones altas, la distancia euclidiana también es menos útil, porque todos los vectores están casi a la misma distancia de la consulta.
• Bibliotecas como Faiss buscan en conjuntos grandes de vectores. Ofrecen búsqueda exacta e índices comprimidos. Los índices comprimidos dan una búsqueda menos precisa.

Historia

Evelyn Fix y Joseph Hodges desarrollaron el método por primera vez en 1951, en un informe para la USAF School of Aviation Medicine. Thomas Cover y Hart publicaron “Nearest neighbor pattern classification” en 1967. Con datos de entrenamiento ilimitados, la tasa de error de la regla del 1-vecino más cercano no es peor que el doble de la tasa de error de Bayes.