¿Qué es el algoritmo de k vecinos más cercanos (KNN)?

Si bien el algoritmo KNN se puede usar para problemas de regresión o clasificación, generalmente se usa como un algoritmo de clasificación, partiendo del supuesto de que se pueden encontrar puntos similares cerca uno del otro.

En los problemas de clasificación, la etiqueta de clase se asigna por mayoría de votos, es decir, se emplea la etiqueta que se representa con más frecuencia en torno a un punto de datos determinado. Aunque técnicamente se considera "votación por pluralidad", el término "votación por mayoría" se emplea más comúnmente en las publicaciones al respecto. La distinción entre estas terminologías es que la "votación por mayoría" requiere técnicamente una mayoría superior al 50%, lo que funciona sobre todo cuando sólo hay dos categorías. Cuando hay varias clases, por ejemplo, cuatro categorías, usted no requiere necesariamente el 50% de los votos para llegar a una conclusión sobre una clase, ya que podría asignar una etiqueta de clase con un voto superior al 25%. La Universidad de Wisconsin-Madison resume bien esto con un ejemplo.

Los problemas de regression emplean un concepto similar al de los problemas de clasificación, pero en este caso se toma el promedio de los 'k-nearest neighbors' para hacer una predicción sobre una clasificación. La principal distinción es que la clasificación se emplea para valores discretos, mientras que regression se emplea con valores continuos. Sin embargo, antes de hacer una clasificación, hay que definir la distancia. La distancia euclidiana es la más empleada, en la que profundizaremos más adelante.

Cabe señalar que el algoritmo KNN también forma parte de una familia de modelos de "aprendizaje perezoso", lo que significa que sólo almacena un conjunto de datos de entrenamiento en lugar de someterse a una fase de entrenamiento. Esto también significa que todo el cálculo se produce cuando se realiza una clasificación o predicción. Dado que depende en gran medida de la memoria para almacenar todos sus datos de entrenamiento, también se denomina método de aprendizaje basado en instancias o en la memoria.

A Evelyn Fix y Joseph Hodges se les atribuyen las ideas iniciales en torno al modelo KNN en este artículo de 1951, mientras que Thomas Cover amplía su concepto en su investigación,"Nearest Neighbor Pattern Classification". Aunque ya no es tan popular como antes, sigue siendo uno de los primeros algoritmos que se aprenden en la ciencia de datos debido a su sencillez y precisión. Sin embargo, a medida que un conjunto de datos crece, KNN se vuelve cada vez más ineficaz, comprometiendo el rendimiento general del modelo. Se utiliza con frecuencia en sistemas de recomendación sencillos, reconocimiento de patrones, minería de datos, predicción de mercados financieros, detección de intrusiones y mucho más.

Para resumir, el objetivo del algoritmo de k vecinos más cercanos es identificar los vecinos más cercanos de un punto de consulta determinado, de modo que podamos asignar una etiqueta de clase a ese punto. Para ello, KNN tiene algunos requisitos:

Para determinar qué puntos de datos están más cerca de un punto de consulta determinado, será necesario calcular la distancia entre el punto de consulta y los demás puntos de datos. Esas métricas de distancia ayudan a formar límites de decisión, que dividen los puntos de consulta en diferentes regiones. Por lo general, los límites de decisión se visualizan con diagramas de Voronoi.

Si bien hay varias medidas de distancia entre las que puede elegir, este artículo solo cubrirá lo siguiente:

Distancia euclidiana (p=2): esta es la medida de distancia más comúnmente empleada y está limitada a vectores de valores reales. Empleando la siguiente fórmula, se mide una línea recta entre el punto de consulta y el otro punto que se está midiendo.

Distancia de Manhattan (p=1): esta es también otra métrica de distancia popular, que mide el valor absoluto entre dos puntos. También se conoce como distancia de taxi o distancia de cuadra de la ciudad, ya que comúnmente se visualiza con una cuadrícula, que ilustra cómo se puede navegar de una dirección a otra a través de las calles de la ciudad.

Distancia de Minkowski: esta medida de distancia es la forma generalizada de las métricas de distancia euclidiana y Manhattan. El parámetro, p, en la fórmula a continuación, permite la creación de otras métricas de distancia. La distancia euclidiana se representa mediante esta fórmula cuando p es igual a dos, y la distancia de Manhattan se denota con p igual a uno.

Distancia de Hamming: esta técnica se emplea normalmente con vectores booleanos o de cadena, identificando los puntos donde los vectores no coinciden. Como resultado, también se conoce como la métrica de superposición. Esto se puede representar con la siguiente fórmula:

Por ejemplo, si tuviera las siguientes cadenas, la distancia de Hamming sería 2, ya que solo dos de los valores difieren.

El valor k en el algoritmo k-NN define cuántos vecinos se verificarán para determinar la clasificación de un punto de consulta específico. Por ejemplo, si k=1, la instancia se asignará a la misma clase que su vecino más cercano.

Definir k puede ser un acto de equilibrio, ya que diferentes valores pueden conducir a un sobreajuste o un ajuste insuficiente. Los valores más bajos de k pueden tener una varianza alta, pero un sesgo bajo, y los valores más grandes de k pueden conducir a un sesgo alto y una varianza más baja. La elección de k dependerá en gran medida de los datos de entrada, ya que los datos con más valores atípicos o ruido probablemente funcionarán mejor con valores más altos de k. En general, se recomienda tener un número impar para k a fin de evitar empates en la clasificación, y las tácticas de validación cruzada pueden ayudarlo a elegir la k óptima para su conjunto de datos.

Para profundizar, puede aprender más sobre el algoritmo k-NN empleando Python y scikit-learn (también conocido como sklearn). Nuestro tutorial en Watson Studio lo ayuda a aprender la sintaxis básica de esta biblioteca, que también contiene otras bibliotecas populares, como NumPy, pandas y Matplotlib. El siguiente código es un ejemplo de cómo crear y predecir con un modelo KNN:

El algoritmo k-NN se ha usado en diversas aplicaciones, principalmente dentro de la clasificación. Algunos de estos casos de uso son:

• Preprocesamiento de datos: los conjuntos de datos suelen tener missing values, pero el algoritmo KNN puede estimar esos valores en un proceso conocido como imputación de datos faltantes.
  
  
• Motores de recomendación: empleando datos de flujo de clics de sitios web, el algoritmo KNN se ha usado para proporcionar recomendaciones automáticas a los usuarios sobre contenido adicional. Esta investigación muestra que un usuario se asigna a un grupo en particular y, en función del comportamiento del usuario de ese grupo, se le da una recomendación. Sin embargo, dados los problemas de escala con KNN, este enfoque puede no ser óptimo para conjuntos de datos más grandes.
  
  
• Finanzas: también se ha utilizado en una variedad de casos de uso financieros y económicos. Por ejemplo, un artículo muestra cómo el uso de KNN en datos crediticios puede ayudar a los bancos a evaluar el riesgo de un préstamo a una organización o individuo. Se emplea para determinar la solvencia crediticia de un solicitante de préstamo. Otra revista destaca su uso en forecasting bursátil, tipos de cambio de divisas, futuros comerciales y análisis del lavado de dinero.
  
  
• Atención médica: KNN también se ha aplicado dentro de la industria de la atención médica, haciendo predicciones sobre el riesgo de ataques cardiacos y cáncer de próstata. El algoritmo funciona calculando las expresiones génicas más probables.
  
  
• Reconocimiento de patrones: KNN también ha ayudado en la identificación de patrones, como en texto y clasificación de dígitos. Esto ha sido particularmente útil para identificar números escritos a mano que puedes encontrar en formularios o sobres de correo.

Al igual que cualquier algoritmo de machine learning, k-NN tiene sus fortalezas y debilidades. Dependiendo del proyecto y la aplicación, puede que sea la elección correcta o no.

• Fácil de aplicar: Dada la sencillez y precisión del algoritmo, es uno de los primeros clasificadores que aprenderá un nuevo científico de datos.
  
• Se adapta fácilmente: a medida que se agregan nuevas muestras de entrenamiento, el algoritmo se ajusta para tener en cuenta cualquier dato nuevo, ya que todos los datos de entrenamiento se almacenan en la memoria.
  
  
• Pocos hiperparámetros: KNN solo requiere un valor 'k' y una métrica de distancia, lo que es bajo en comparación con otros algoritmos de machine learning.

• No es escalable: Dadoque KNN es un algoritmo perezoso, ocupa más memoria y almacenamiento de datos en comparación con otros clasificadores. Esto puede ser costoso tanto desde el punto de vista del tiempo como del dinero. Más memoria y almacenamiento elevarán los gastos de la compañía y más datos pueden tardar más tiempo en computarse. Aunque se crearon diferentes estructuras de datos, como Ball-Tree, para abordar las ineficiencias computacionales, un clasificador diferente puede ser ideal en función del problema empresarial.
  
  
• Maldición de la dimensionalidad: el algoritmo KNN suele ser víctima de la maldición de la dimensionalidad, lo que significa que no funciona bien con entradas de datos de alta dimensión. Esto a veces también se conoce como el fenómeno de pico ya que, después de que el algoritmo alcanza el número óptimo de características, las características adicionales aumentan la cantidad de errores de clasificación, especialmente cuando el tamaño de la muestra es más pequeño.
  
  
• Propenso al ajuste excesivo: debido a la "maldición de la dimensionalidad", KNN también es más propenso al ajuste excesivo. Si bien se aprovechan las técnicas de selección de características y reducción de dimensionalidad para evitar que esto ocurra, el valor de 'k' también puede afectar el comportamiento del modelo. Los valores más bajos de 'k' pueden sobreajustar los datos, mientras que los valores más altos de 'k' tienden a "suavizar" los valores de predicción, ya que promedian los valores en un área o vecindario mayor. Sin embargo, si el valor de 'k' es demasiado alto, entonces puede subestimar los datos.