¿Qué es kNN?

kNN, o el algoritmo de k vecino más cercano, es un algoritmo de machine learning que usa la proximidad para comparar un punto de datos con un set de datos con el que se entrenó y el cual memorizó para realizar predicciones. Este aprendizaje basado en instancias le da a kNN la denominación "aprendizaje vago" y permite al algoritmo ocuparse de problemas de clasificación o regresión. kNN funciona sobre la suposición de que los puntos similares pueden encontrarse cerca unos de otros; "cada oveja con su pareja".

Como algoritmo de clasificación, kNN asigna un nuevo punto de datos al set de mayoría entre sus vecinos. Como algoritmo de regresión, kNN hace una predicción sobre la base del promedio de los valores más cercanos al punto de búsqueda.

kNN es un algoritmo de aprendizaje supervisado en el que "k" representa el número de vecinos más cercanos considerado en el problema de clasificación o regresión, y "NN" se refiere a los vecinos más cercanos del número elegido para k.

kNN fue desarrollado por Evelyn Fix y Joseph Hodges en 1951 en el contexto de una investigación realizada para el servicio militar de Estados Unidos¹. Explicaron en una publicación el análisis discriminante, que es un método de clasificación no paramétrico. En 1967, Thomas Cover y Peter Hart hicieron una ampliación sobre el método de clasificación no paramétrico y publicaron "Nearest Neighbor Pattern Classification" (Clasificación de patrones de vecino más cercano)². Casi 20 años después, James Keller, quien desarrolló un "KNN difuso" que genera tasas de error más bajas, refinó el algoritmo³.

En la actualidad, el algoritmo de kNN es el algoritmo más usado gracias a su adaptabilidad para la mayoría de los campos; desde la genética hasta las finanzas y el servicio al cliente.

El algoritmo de kNN funciona como un algoritmo de aprendizaje supervisado, lo que significa que se alimenta con sets de datos de entrenamiento que memoriza. Depende de estos datos de entrada etiquetados para aprender una función que produzca una salida adecuada cuando se le dan datos nuevos sin etiquetar.

Esto permite al algoritmo resolver problemas de clasificación o regresión. Si bien el cómputo de kNN se realiza durante una búsqueda y no durante una fase de entrenamiento, tiene requisitos de almacenamiento de datos importantes y, por lo tanto, depende en gran medida de la memoria.

En relación con los problemas de clasificación, el algoritmo de KNN asignará una etiqueta de clase con base en una mayoría, lo que significa que usará la etiqueta que se encuentra con mayor frecuencia en torno a un punto de datos dado. En otras palabras, la salida de un problema de clasificación es el modo de los vecinos más cercanos.

Una diferencia: votación de mayoría frente a votación de pluralidad

La votación de mayoría indica que cualquier resultado por sobre el 50 % es la mayoría. Esto es aplicable si hay dos etiquetas de clase en consideración. Sin embargo, el voto de pluralidad aplica si se están considerando varias etiquetas de clase. En estos casos, cualquier resultado por sobre el 33.3 % sería suficiente para denotar una mayoría y, por lo tanto, para brindar una predicción. Entonces, el voto de pluralidad es un término más preciso para definir el modo de kNN.

Si tuviéramos que ilustrar esta diferencia:

Una predicción binaria

Y: 🎉🎉🎉❤️❤️❤️❤️❤️

Voto de mayoría: ❤️

Voto de pluralidad: ❤️

Una configuración de varias clases

Y: ⏰⏰⏰💰💰💰🏠🏠🏠🏠

Voto de mayoría: Ninguno

Voto de pluralidad: 🏠

Los problemas de regresión usan el promedio de los vecinos más cercanos para predecir una clasificación. Un problema de regresión generará números reales como salida de la búsqueda.

Por ejemplo, si estuvieras haciendo un gráfico para predecir el peso de alguien según su altura, los valores que denotan la altura serían independientes, mientras que los valores de peso serían dependientes. Al realizar un cálculo de la razón altura-peso promedio, podrías estimar el peso de alguien (la variable dependiente) según su altura (la variable independiente).

La clave para el algoritmo de kNN es determinar la distancia entre el punto de búsqueda y los otros puntos de datos. Determinar las métricas de distancia posibilita los límites de decisión. Estos límites crean diferentes regiones de puntos de datos. Existen distintos métodos que se usan para calcular la distancia:

• La distancia euclidiana es la medición de distancia más común, la cual mide una línea recta entre el punto de búsqueda y el otro punto que se está midiendo.
• La distancia Manhattan también es una medición de distancia popular, la cual mide el valor absoluto entre dos puntos. Se representa en una cuadrícula y, con frecuencia, se la llama geometría del taxi; ¿cómo se llega del punto A (tu punto de búsqueda) al punto B (el punto que se está midiendo)?
• La distancia de Minkowski es una generalización de las métricas de distancia euclidiana o Manhattan, la cual permite la creación de otras métricas de distancia. Se calcula en un espacio de vectores normalizado. En la distancia de Minkowski, p es el parámetro que define el tipo de distancia usado en el cálculo. Si p=1, se usa la distancia Manhattan. Si p=2, se usa la distancia euclidiana.
• La distancia de Hamming, también conocida como métrica de superposición, es una técnica usada con vectores de cadena o booleanos para identificar los sitios en los que los vectores no coinciden. En otras palabras, mide la distancia entre dos cadenas de igual longitud. Es particularmente útil para los códigos de corrección de errores y detección de errores.

Para elegir el mejor valor k (el número de vecinos más cercanos considerado), debes experimentar con algunos valores para encontrar el valor k que genere las predicciones más exactas con la menor cantidad de errores. Determinar el mejor valor es un acto de balanceo:

• Los valores k bajos hacen predicciones inestables.
  Toma este ejemplo: un punto de búsqueda está rodeado por dos puntos verdes y un triángulo rojo. Si k=1 y el punto más cercano al punto de búsqueda es uno de los puntos verdes, el algoritmo predecirá incorrectamente un punto verde como el resultado de la búsqueda. Los valores k bajos tienen variación alta (el modelo se ajusta demasiado a los datos de entrenamiento), complejidad alta y sesgo bajo (el modelo es lo suficientemente complejo como para ajustarse bien a los datos de entrenamiento).
• Los valores k altos son ruidosos.
  Un valor k más alto aumentará la precisión de las predicciones dado que hay más números a partir de los cuales calcular los modos o promedios. Sin embargo, si el valor k es demasiado alto, probablemente dará como resultado una variación baja, complejidad baja y sesgo alto (el modelo NO es lo suficientemente complejo para ajustarse bien a los datos de entrenamiento).

Lo ideal es encontrar un valor k que se encuentre entre variación alta y sesgo alto. También se recomienda elegir un número impar para k, a fin de evitar empates en el análisis de clasificación.

El valor k correcto también es relativo al set de datos. Para elegir ese valor, puedes intentar encontrar la raíz cuadrada de N, donde N es el número de puntos de datos en el set de datos de entrenamiento. Las tácticas de validación cruzada también pueden ayudarte a elegir el valor k más adecuado para el set de datos.

El algoritmo de kNN suele describirse como el algoritmo de aprendizaje supervisado "más simple", lo cual lleva a sus diversas ventajas:

• Simple: kNN es fácil de implementar debido a lo simple y preciso que es. Como tal, suele ser uno de los primeros clasificadores que aprende un científico de datos.
• Adaptable: tan pronto se agregan nuevas muestras de entrenamiento al set de datos, el algoritmo de kNN ajusta sus predicciones para incluir los datos de entrenamiento nuevos.
• Fácil de programar: kNN requiere solo algunos hiperparámetros; un valor k y una métrica de distancia. Esto hace que sea un algoritmo relativamente poco complicado.

Además, el algoritmo de kNN no requiere tiempo de entrenamiento dado que almacena los datos de entrenamiento y su potencia de procesamiento solo se utiliza al realizar predicciones.

Si bien el algoritmo de kNN es simple, también tiene un conjunto de desafíos y limitaciones, que se deben en parte a su simpleza:

• Difícil de escalar: como kNN ocupa mucha memoria y almacenamiento de datos, aumenta los gastos asociados con el almacenamiento. Esta dependencia de la memoria también significa que el algoritmo es intensivo respecto al procesamiento, lo cual requiere muchos recursos.
• Curso de dimensionalidad: esto se refiere a un fenómeno que ocurre en la informática, en el que un set establecido de ejemplos de entrenamiento se ve desafiado por una cantidad creciente de dimensiones y el aumento inherente de los valores de las características en estas dimensiones. En otras palabras, los datos de entrenamiento del modelo no pueden mantener el ritmo de la dimensionalidad en evolución del hiperespacio. Esto significa que las predicciones se vuelven menos precisas debido a que la distancia entre el punto de búsqueda y puntos similares aumenta; en otras dimensiones.
• Sobreajuste: el valor de k, como mostramos antes, afectará el comportamiento del algoritmo. Esto puede suceder, en especial, cuando el valor de k es demasiado bajo. Los valores más bajos de k pueden sobreajustar los datos, mientras que valores más altos "suavizarán" los valores de predicción dado que el algoritmo hace un promedio de los valores de una zona más amplia.

El algoritmo de kNN, popular por su simpleza y precisión, tiene una variedad de aplicaciones, en especial cuando se usa para análisis de clasificación.

• Clasificación de relevancia: kNN usa algoritmos de procesamiento de lenguaje natural (NLP) para determinar qué resultados son más relevantes para una búsqueda.
• Búsqueda por similitud para imágenes o videos: la búsqueda por similitud de imágenes usa descripciones de lenguaje natural para encontrar imágenes que coincidan con búsquedas de texto.

• Reconocimiento de patrones: kNN se puede usar para identificar patrones en la clasificación de dígitos o texto.
• Finanzas: en el sector financiero, kNN se puede usar para la predicción en el mercado de valores, las cotizaciones de monedas, etc.
• Recomendaciones de productos y motores de recomendaciones: ¡piensa en Netflix! "Si te gustó esto, creemos que también te puede gustar…". Cualquier sitio que use una versión de esa oración, de manera expresa o no, probablemente use un algoritmo de kNN para impulsar su motor de recomendación.
• Atención médica: en el campo de la medicina y la investigación médica, el algoritmo de kNN se puede usar en genética para calcular la probabilidad de ciertas expresiones de genes. Esto permite a los médicos predecir la probabilidad de cáncer, ataques cardiacos o cualquier otra afección hereditaria.
• Preprocesamiento de datos: el algoritmo de kNN se puede usar para estimar los valores faltantes en los sets de datos.

Elasticsearch te permite implementar la búsqueda de kNN. Se brinda soporte para dos métodos: kNN aproximado y kNN exacto de fuerza bruta. Puedes usar la búsqueda de kNN en el contexto de búsqueda por similitud, clasificación de relevancia basada en algoritmos de NLP y recomendaciones de productos y motores de recomendaciones.

Implementa la búsqueda de kNN con Elastic

kNN significa algoritmo de k vecino más cercano, en donde k indica la cantidad de vecinos más cercanos que se consideraron en el análisis.