Qué es el algoritmo K-Nearest Neighbors (Vecinos más próximos K), en un artículo

Definición del algoritmo del vecino más próximo (K Nearest Neighbour Algorithm)

El algoritmo K-Nearest Neighbors (K-Primeros vecinos) es un algoritmo de aprendizaje supervisado basado en instancias que puede utilizarse para tareas de clasificación y regresión. La idea central del algoritmo es muy intuitiva: dada una nueva muestra, encontrar las K muestras de entrenamiento más cercanas a ella en el espacio de características y hacer una predicción basada en la información de estos vecinos. Para los problemas de clasificación, se utiliza un mecanismo de votación para tomar como predicción la categoría con más ocurrencias entre los K vecinos; para los problemas de regresión, se toma como predicción la media de los valores objetivo de los K vecinos. La K del nombre del algoritmo significa el número de vecinos considerados y es un parámetro clave que puede ajustar el usuario. El algoritmo K del vecino más próximo es un método no paramétrico que no hace ninguna suposición sobre la distribución de los datos y es muy adaptable. La elección de la métrica de distancia es crucial; las más comunes son la distancia euclidiana, la distancia de Manhattan, la distancia de Minkowski, etc. Diferentes métricas de distancia son adecuadas para diferentes tipos de datos. El rendimiento del algoritmo también se ve afectado por el escalado de las características, que suele requerir un preprocesamiento de normalización.El algoritmo del vecino más próximo K, también conocido como aprendizaje basado en la memoria, almacena esencialmente los datos de entrenamiento y los recupera mediante el cálculo de similitudes en el momento de la predicción. La ventaja del método es que el modelo es sencillo e intuitivo; el inconveniente es que el coste computacional de la fase de predicción aumenta considerablemente a medida que aumenta la cantidad de datos.

Orígenes históricos del algoritmo del vecino más próximo K

• Germinación conceptual tempranaEn la década de 1950, Fix y Hodges introdujeron por primera vez el concepto básico de clasificación del vecino más próximo en el análisis discriminante no paramétrico. Este trabajo sentó las bases para la formalización del posterior algoritmo del vecino más próximo K.
• Establecimiento teórico del sistemaEn 1967, Cover y Hart publicaron el artículo "Nearest Neighbour Pattern Classification", que analizaba sistemáticamente los límites de la tasa de error de los clasificadores de vecino más próximo. Este trabajo seminal aportó garantías teóricas al algoritmo.
• Puesta en marcha del perfeccionamiento de algoritmosEn la década de 1970, con el auge de la investigación en reconocimiento de patrones, los algoritmos de K vecino más próximo se utilizaron ampliamente en diversos campos. Los investigadores empezaron a estudiar los efectos de las distintas métricas de distancia y de la elección del valor K en el rendimiento.
• Retos en la era de los macrodatosEn el siglo XXI, el algoritmo tradicional del vecino más próximo K se enfrenta a un cuello de botella de eficiencia computacional ante la masificación de datos. Esto ha llevado a los investigadores a desarrollar diversas técnicas de optimización, como árboles KD, árboles de bolas y otras estructuras de datos aceleradas.
• Desarrollo moderno de la integraciónEn los últimos años, los algoritmos K-nearest neighbour se han combinado con el aprendizaje profundo para producir nuevos métodos, como el aprendizaje métrico profundo. También las implementaciones distribuidas en plataformas de big data han ampliado la gama de aplicaciones de los algoritmos.

Principios básicos del algoritmo K de vecino más próximo

• Base de los supuestos de similitudEl algoritmo se basa en el supuesto de continuidad local, es decir, que los puntos vecinos del espacio de características tienen propiedades similares. Este supuesto es coherente con la percepción intuitiva del mundo que tienen las personas y es fundamental para la eficacia del algoritmo.
• Papel fundamental de las métricas de distanciaLa distancia euclidiana: Las distintas métricas de distancia determinan diferentes definiciones de "proximidad", lo que afecta directamente al rendimiento del algoritmo. La distancia euclidiana es adecuada para características continuas, la distancia Manhattan es más robusta frente a valores atípicos y la similitud coseno es adecuada para datos dispersos de alta dimensión.
• El arte del equilibrio KUn valor de K demasiado pequeño es susceptible a interferencias de ruido, lo que lleva a un ajuste excesivo; un valor de K demasiado grande suaviza el límite de decisión y puede ignorar características locales. El valor óptimo de K debe encontrar un equilibrio entre el sesgo y la varianza.
• Propiedades geométricas del espacio de característicasEl rendimiento de los algoritmos está estrechamente relacionado con la estructura geométrica del espacio de características. El problema de la catástrofe dimensional es especialmente grave en los espacios de gran dimensión, en los que la diferencia de distancia entre puntos llega a ser insignificante.
• Estrategia de ponderación del votoMientras que en el algoritmo K-Nearest Neighbor estándar cada vecino vota con la misma ponderación, el algoritmo K-Nearest Neighbor ponderado asigna distintas ponderaciones en función de la distancia. Cuanto más cerca están los vecinos, más influyen en la decisión, lo que mejora la precisión del algoritmo.

Flujo de trabajo del algoritmo K Nearest Neighbour

• Fase de preprocesamiento de datosNormalizar las características para eliminar el efecto de las diferencias en la magnitud de las distintas características. Garantizar la equidad de la métrica de distancia y evitar que determinadas características dominen el cálculo de la distancia.
• Cálculo de la matriz de distanciasLa distancia entre la muestra que se va a probar y todas las muestras de entrenamiento se calcula durante la predicción para formar una matriz de distancias. Este paso tiene una alta complejidad computacional y es el principal cuello de botella en la eficiencia del algoritmo.
• Proceso de búsqueda del vecino más próximoBúsqueda de las muestras de entrenamiento correspondientes a las K distancias más pequeñas de la matriz de distancias. Los algoritmos de búsqueda eficientes, como KD-tree, pueden reducir significativamente la complejidad temporal de este paso.
• Aplicación de las normas de decisiónVotación por mayoría: la votación por mayoría se utiliza para problemas de clasificación y el promedio para problemas de regresión. En caso de empate, se suele elegir la categoría a la que pertenece la muestra más cercana.
• Optimización de la evaluación de resultadosEvaluar el rendimiento del algoritmo mediante validación cruzada y ajustar el valor K y los parámetros de la métrica de distancia. La selección del modelo debe tener en cuenta el ámbito específico del problema y las características de los datos.

Características ventajosas del algoritmo K vecino más próximo

• Principios intuitivos y fáciles de entenderLa lógica del algoritmo es sencilla y no requiere una base matemática compleja para entenderlo, y esta intuición hace que el algoritmo K del vecino más próximo sea el caso elegido para enseñar el aprendizaje automático introductorio.
• No requiere proceso de formaciónAlgoritmo de aprendizaje: Como algoritmo de aprendizaje inerte, K-próximos más cercanos no tiene una fase de entrenamiento explícita, y pueden añadirse nuevos datos al modelo en cualquier momento, lo que permite al algoritmo adaptarse rápidamente a los cambios en la distribución de los datos.
• Procesamiento natural MulticlasificaciónEl algoritmo admite de forma natural problemas de clasificación multicategoría sin necesidad de construir múltiples clasificadores como hacen algunos algoritmos de clasificación binaria, y el algoritmo funciona de forma estable en escenarios multicategoría.
• Límite superior de la tasa de error teóricaCuando las muestras de entrenamiento tienden a ser infinitas, la tasa de error del clasificador del vecino más próximo no es más de dos veces superior a la tasa de error bayesiano, lo que garantiza la fiabilidad del algoritmo mejorado.
• Adaptación a límites de decisión complejosEl algoritmo K-próximo más cercano es capaz de aprender límites de decisión complejos y no lineales, lo que le permite sobresalir en el tratamiento de datos complejos del mundo real.

Limitaciones del algoritmo K de vecino más próximo

• cuello de botella de la eficiencia computacionalPredicción: la predicción requiere calcular la distancia a todas las muestras de entrenamiento, y la complejidad temporal crece linealmente con la cantidad de datos, lo que dificulta la aplicación del algoritmo a conjuntos de datos a gran escala.
• El problema de la catástrofe dimensionalEn un espacio de características de alta dimensionalidad, la distancia entre puntos se convierte en una falta de diferenciación y el rendimiento del algoritmo disminuye significativamente, por lo que la selección de características o la reducción de la dimensionalidad se convierte en un paso necesario del preprocesamiento.
• Sensible al factor de ruidoEl ruido y los valores atípicos en los datos de entrenamiento pueden afectar directamente a los resultados de la predicción, especialmente cuando el valor de K es pequeño, la calidad de los datos tiene un mayor impacto en el rendimiento del algoritmo.
• Dependencia de la escala de característicasEl rendimiento del algoritmo depende en gran medida de la forma en que se escalan las características, y el preprocesamiento de normalización es indispensable si un amplio rango de valores para algunas características domina el cálculo de la distancia.
• Datos desequilibradosCuando el tamaño de las muestras de las categorías varía mucho, la categoría mayoritaria puede tener un efecto desproporcionado en la clasificación de la categoría minoritaria, lo que debe corregirse mediante técnicas de votación ponderada o muestreo.

Aplicaciones prácticas del algoritmo del vecino más próximo K

• Construcción de sistemas de recomendaciónFiltrado colaborativo basado en el usuario: el filtrado colaborativo basado en el usuario es esencialmente una aplicación del algoritmo K-próximo más cercano para hacer recomendaciones encontrando usuarios o artículos similares. El comercio electrónico y las plataformas de streaming utilizan mucho esta técnica.
• Diagnóstico complementarioEl objetivo es ayudar a los médicos a diagnosticar enfermedades basándose en la similitud de los síntomas del paciente con casos históricos. Los algoritmos pueden integrar múltiples manifestaciones clínicas para facilitar la toma de decisiones.
• Tareas de clasificación de imágenesEn visión por computador, el algoritmo K-nearest neighbour puede utilizarse para la clasificación simple de imágenes, como el reconocimiento de dígitos manuscritos. Aunque el aprendizaje profundo es mejor, K-nearest neighbour se sigue utilizando como método de referencia.
• Evaluación del riesgo de créditoLos bancos utilizan el algoritmo K Nearest Neighbour para analizar la similitud entre los clientes y los clientes que históricamente han incumplido sus calificaciones crediticias. El algoritmo es capaz de combinar múltiples factores de riesgo.
• Análisis de información geográficaEl algoritmo K nearest neighbor (vecino más próximo): predicción analítica basada en la proximidad geográfica en sistemas SIG, por ejemplo, evaluación del precio de la vivienda, vigilancia medioambiental. La proximidad natural de los datos espaciales es idónea para el algoritmo K del vecino más próximo.

Una variante mejorada del algoritmo del vecino más próximo K

• Algoritmo del vecino más próximo K ponderado: Asigna diferentes pesos a los distintos vecinos en función de la distancia, siendo mayor el peso cuanto más cercana sea la distancia. Esta mejora aumenta la sensibilidad del algoritmo a las estructuras locales y mejora la precisión de la predicción.
• Aprendizaje métrico a distanciaEl aprendizaje automático: los métodos de aprendizaje automático se utilizan para aprender automáticamente la función métrica de distancia que mejor se adapta a unos datos concretos. Métodos como el análisis de componentes de vecindad a gran escala son representativos de esta dirección.
• búsqueda aproximada del vecino más próximoDesarrollar algoritmos de aproximación para acelerar la búsqueda del vecino más próximo en datos a gran escala, por ejemplo, hashing localmente sensible, grafos jerárquicos navegables de pequeño mundo.
• algoritmo kernel de vecino más próximoIntroducción de trucos de kernel para mapear los datos a un espacio de características de alta dimensión, donde se ejecuta el algoritmo K-próximo más cercano y es capaz de manejar problemas no lineales más complejos.
• Selección de características ponderada por la distanciaCombinación de técnicas de selección de características para optimizar su peso en la métrica de distancias. El método relacionado puede identificar automáticamente características importantes y mejorar el rendimiento del algoritmo.

Ajuste de los parámetros del algoritmo del vecino más próximo K

• Estrategia de selección del valor KEl valor K óptimo suele seleccionarse mediante validación cruzada, empezando con un valor pequeño y aumentándolo gradualmente para observar los cambios en el rendimiento del modelo. Como regla general, se recomienda elegir un número impar de valores K para evitar el caso de votos planos.
• Selección de la métrica de distanciaMétrica de distancia: elija una métrica de distancia adecuada en función del tipo de datos y las características de los rasgos. La distancia euclidiana se suele utilizar para características continuas, la distancia de Hamming es adecuada para características categóricas y la similitud coseno se suele utilizar para datos textuales.
• Diseño de la función de ponderaciónFunción de ponderación: en los vecinos más próximos K ponderados, se diseña una función de ponderación razonable, por ejemplo, inversamente proporcional al cuadrado de la distancia. La función de ponderación afecta a la sensibilidad del algoritmo a la estructura local.
• Aplicación de técnicas de reducción de la dimensionalidadLa reducción de la dimensionalidad: frente a los datos de alta dimensionalidad, las características se preprocesan mediante técnicas de reducción de la dimensionalidad como el análisis de componentes principales. La reducción de la dimensionalidad mejora la eficiencia computacional y alivia el problema de la catástrofe de la dimensionalidad.
• Optimización de la computación paralelaAcelerar el proceso de cálculo de distancias utilizando procesadores multinúcleo o marcos informáticos distribuidos. Las plataformas modernas de big data ofrecen soporte técnico para que los algoritmos se apliquen a escala.