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

Aunque el algoritmo KNN se puede usar para problemas de regresión o clasificación, se suele utilizar como un algoritmo de clasificación, que parte de la suposición de que se pueden encontrar puntos similares cerca unos de otros.

Para los problemas de clasificación, la etiqueta de clase se asigna en función de la mayoría de votos, es decir, se utiliza la etiqueta que se representa con más frecuencia en torno a un punto de datos determinado. Si bien esto se considera técnicamente “votación por pluralidad”, en la literatura se utiliza más comúnmente el término “voto por mayoría”. La distinción entre estas terminologías es que la “votación por mayoría” técnicamente requiere una mayoría superior al 50 %, lo que funciona principalmente cuando solo hay dos categorías. Cuando tiene varias clases, por ejemplo cuatro categorías, no necesita necesariamente el 50 % de los votos para llegar a una conclusión sobre una clase; puede asignar una etiqueta de clase con un voto superior al 25 %. La Universidad de Wisconsin-Madison lo resume bien con un ejemplo aquí.

Los problemas de regresión utilizan un concepto similar al problema de clasificación, pero en este caso, se toma el promedio de los k vecinos más cercanos para hacer una predicción sobre una clasificación. La principal distinción aquí es que la clasificación se usa para valores discretos, mientras que la regresión se usa para valores continuos. Sin embargo, antes de que se pueda hacer una clasificación, se debe definir la distancia. La distancia euclidiana es la más utilizada, en la que profundizaremos más adelante.

También vale la pena señalar que el algoritmo KNN también es parte de una familia de modelos de "aprendizaje vago", lo que significa que solo almacena un conjunto de datos de entrenamiento en lugar de someterse a una etapa de entrenamiento. Esto también significa que todo el cálculo se produce cuando se está haciendo 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 conoce como un método de aprendizaje basado en instancias o en 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 no es tan popular como antes, sigue siendo uno de los primeros algoritmos que se aprenden en la ciencia de datos debido a su simplicidad y precisión. Sin embargo, a medida que crece un conjunto de datos, KNN se vuelve cada vez más ineficiente, lo que compromete el rendimiento general del modelo. Se utiliza habitualmente para sistemas de recomendación sencillos, reconocimiento de patrones, minería de datos, predicciones de mercados financieros, detección de intrusiones y más.

Para recapitular, el objetivo del algoritmo de vecino k más cercano 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. Estas métricas de distancia ayudan a formar límites de decisión, que dividen los puntos de consulta en diferentes regiones. Es frecuente ver los límites de decisión visualizados con diagramas de Voronoi.

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

Distancia euclídea (p=2): es la medida de distancia más utilizada y se limita a vectores de valor real. Mediante la fórmula siguiente, mide una línea recta entre el punto de consulta y el otro punto medido.

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 euclidianas y de 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 utiliza normalmente con vectores booleanos o de cadena, para identificar los puntos en los que los vectores no coinciden. Como resultado, también se ha denominado 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 comprobará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 único vecino más cercano.

Definir k puede ser un acto de equilibrio, ya que diferentes valores pueden conducir a un ajuste excesivo o insuficiente. Los valores más bajos de k pueden tener una varianza alta, pero un sesgo bajo, y los valores más altos de k pueden provocar 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 para evitar empates en la clasificación, y las tácticas de validación cruzada pueden ayudarlo a elegir el k óptimo para su conjunto de datos.

Para profundizar, puede obtener más información sobre el algoritmo k-NN mediante Python y Scikit-learn (también conocido como sklearn). Nuestro tutorial de watsonx Studio le 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 utilizado en una variedad de aplicaciones, principalmente en la clasificación. Algunos de estos casos de uso incluyen:

• Preprocesamiento de datos: a los conjuntos de datos les faltan valores con frecuencia, pero el algoritmo KNN puede estimarlos en un proceso conocido como imputación de datos faltantes.
  
  
• Motores de recomendación: al utilizar los datos del flujo de clics de los sitios web, se ha utilizado el algoritmo KNN para ofrecer 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 escalado 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 financiero y económico. 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 utiliza para determinar la solvencia crediticia de un solicitante de préstamo. Otra revista destaca su uso en la previsión del mercado de valores, los tipos de cambio de divisas, el comercio de futuros y los análisis de blanqueo de capitales.
  
  
• Sanidad: el KNN también ha tenido aplicaciones en el sector sanitario, ya que hace predicciones sobre el riesgo de ataques al corazón y cáncer de próstata. El algoritmo funciona calculando las expresiones genéticas más probables.
  
  
• Reconocimiento de patrones: KNN también ha ayudado a identificar patrones, como en la clasificación de textos y dígitos. Esto ha resultado especialmente útil para identificar los números escritos a mano que puede 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 o no ser la opción correcta.

• Fácil de implementar: dada la simplicidad 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 añaden nuevas muestras de entrenamiento, el algoritmo se ajusta para tener en cuenta los datos nuevos, 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 se escala bien: como KNN es un algoritmo vago, 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 aumentarán los gastos de la empresa, y más datos pueden tardar más en calcularse. Aunque se han creado diferentes estructuras de datos, como Ball-Tree, para abordar las ineficiencias computacionales, un clasificador diferente puede ser ideal según el problema comercial.
  
  
• La maldición de la dimensionalidad: el algoritmo KNN tiende a 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. A veces también se denomina fenómeno del pico, en el que, después de que el algoritmo alcance 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 sobreajuste: debido a la "maldición de la dimensionalidad", KNN también es más propenso al sobreajuste. Aunque se aprovechan las técnicas de selección de características y reducción de la dimensionalidad para evitar que esto ocurra, el valor de k también puede influir en el comportamiento del modelo. Los valores bajos de k pueden sobreajustar los datos, mientras que los valores altos de k tienden a "suavizar" los valores de predicción, ya que se promedian los valores sobre un área mayor, o vecindario. Sin embargo, si el valor de k es demasiado alto, puede subajustar los datos.