Vecinos Más Cercanos (K-Nearest Neighbors)

El algoritmo de vecinos más cercanos (KNN) es un algoritmo de aprendizaje supervisado no paramétrico utilizado para tareas de clasificación y regresión en aprendizaje automático. Se basa en el concepto de proximidad, asumiendo que los puntos de datos similares se encuentran cerca entre sí. KNN es un algoritmo de aprendizaje perezoso, lo que significa que no requiere una fase de entrenamiento y realiza predicciones almacenando todo el conjunto de datos de entrenamiento y utilizándolo para determinar la clase o el valor de nuevos puntos de datos. El algoritmo predice el resultado para un punto de prueba identificando los ‘k’ puntos de datos de entrenamiento más cercanos al punto de prueba e infiere la salida en función de estos vecinos. Este método es altamente intuitivo y replica estrategias de percepción humana que dependen de comparar nuevos datos con ejemplos conocidos.

Cómo funciona KNN

KNN opera identificando los ‘k’ puntos de datos más cercanos a un punto de consulta dado y utilizando estos vecinos para hacer una predicción.

• En tareas de clasificación, el algoritmo asigna el punto de consulta a la clase más común entre sus ‘k’ vecinos más cercanos, lo que se conoce como votación mayoritaria. La votación mayoritaria en KNN puede entenderse como “votación por pluralidad” cuando se trata de múltiples clases, donde el punto de consulta se asigna a la clase con el mayor número entre sus vecinos más cercanos, aunque no constituya una mayoría absoluta.
• En tareas de regresión, predice el valor promediando los valores de los ‘k’ vecinos más cercanos.

Los principios de proximidad y similitud, que son fundamentales en la percepción humana, también son centrales para el funcionamiento de KNN, ya que se asume que los puntos de datos cercanos en el espacio de características son más similares y, por tanto, probablemente tendrán resultados similares.

Métricas de Distancia

Para determinar los vecinos más cercanos, KNN utiliza diversas métricas de distancia, que son críticas para su rendimiento:

• Distancia Euclidiana: La distancia en línea recta entre dos puntos en un espacio multidimensional, comúnmente utilizada para variables continuas. Es la métrica de distancia más usada en KNN y resulta especialmente útil cuando los datos son densos y continuos.
• Distancia Manhattan: También conocida como distancia de taxista, calcula la distancia sumando las diferencias absolutas entre las coordenadas de dos puntos. Es útil en escenarios de caminos en cuadrícula donde los movimientos están restringidos a direcciones ortogonales.
• Distancia Minkowski: Una forma generalizada de las distancias Euclidiana y Manhattan, parametrizada por ‘p’. Si p=1, se convierte en la distancia Manhattan, y si p=2, es la Euclidiana. Esta métrica proporciona flexibilidad dependiendo del valor de ‘p’ elegido.
• Distancia Hamming: Utilizada para datos categóricos, cuenta el número de bits diferentes entre dos vectores binarios. Es particularmente útil en problemas de clasificación binaria donde los atributos tienen valores binarios.

Elección del valor adecuado de ‘k’

El parámetro ‘k’ en KNN representa el número de vecinos a considerar. Elegir el ‘k’ correcto es crucial:

• Un ‘k’ pequeño puede llevar a sobreajuste, donde el modelo es demasiado sensible al ruido en los datos de entrenamiento, capturando patrones espurios que no se generalizan.
• Un ‘k’ grande puede resultar en subajuste, donde el modelo se vuelve demasiado general y pasa por alto patrones importantes, lo que lleva a un bajo rendimiento predictivo.
• Por lo general, ‘k’ se elige mediante validación cruzada y debería ser un número impar para evitar empates en las decisiones de clasificación. La elección de ‘k’ puede afectar significativamente la precisión del modelo y suele determinarse empíricamente.

Ventajas y Desventajas

Ventajas

• Simple e intuitivo: Fácil de entender e implementar, lo que lo convierte en una buena opción para principiantes. La simplicidad de KNN radica en su enfoque directo de comparar instancias de prueba con ejemplos almacenados.
• Sin fase de entrenamiento: KNN no requiere una fase explícita de entrenamiento, ya que realiza predicciones utilizando el conjunto de datos almacenado. Esto significa que el modelo puede actualizarse simplemente añadiendo nuevos puntos de datos al conjunto.
• Versátil: Puede usarse tanto para clasificación como para regresión, y su aplicación es amplia en diferentes dominios. También es útil para problemas de clasificación multilabel.

Desventajas

• Computacionalmente intensivo: Al requerir almacenar y comparar cada nuevo punto de datos con todo el conjunto, puede ser lento y exigir muchos recursos, especialmente con conjuntos de datos grandes. La complejidad temporal de KNN es O(n), donde n es el número de muestras de entrenamiento.
• Sensible a valores atípicos: La presencia de valores atípicos puede afectar significativamente las predicciones, ya que estos puntos anómalos pueden sesgar los resultados, especialmente cuando ‘k’ es pequeño.
• Maldición de la dimensionalidad: En espacios de alta dimensión, el rendimiento del algoritmo puede degradarse, ya que las distancias entre puntos de datos pierden significado. A medida que aumenta la dimensionalidad, el volumen del espacio se incrementa, provocando que los datos se dispersen. Esta dispersión dificulta que KNN encuentre vecinos cercanos de manera efectiva.

Casos de Uso

KNN se aplica en diversos campos gracias a su simplicidad y eficacia:

• Sistemas de recomendación: Se utiliza para recomendar productos o contenidos a los usuarios en función de las preferencias de usuarios similares. KNN puede ayudar a identificar usuarios o elementos similares evaluando la similitud de características.
• Reconocimiento de patrones: Empleado en reconocimiento de escritura a mano y otras tareas de reconocimiento de patrones, donde puede clasificar imágenes según la similitud de los valores de píxeles.
• Imputación de datos: Útil para completar valores faltantes en conjuntos de datos estimándolos en función de puntos similares, manteniendo así la integridad del conjunto.
• Finanzas y salud: Aplicado en predicciones del mercado bursátil, evaluación de riesgos y diagnóstico médico analizando similitudes en datos históricos. En el sector salud, puede predecir diagnósticos comparando síntomas con casos conocidos.

Implementación en Python

KNN puede implementarse utilizando librerías como scikit-learn en Python. Aquí tienes un ejemplo básico de uso de KNN para clasificación:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# Cargar el conjunto de datos
iris = load_iris()
X, y = iris.data, iris.target

# Dividir los datos en entrenamiento y prueba
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Inicializar el clasificador KNN con k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Ajustar el modelo
knn.fit(X_train, y_train)

# Realizar predicciones
y_pred = knn.predict(X_test)

# Evaluar la precisión
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

Vecinos Más Cercanos (KNN) en la Investigación Científica

K-Nearest Neighbors (KNN) es un algoritmo fundamental utilizado en diversos campos como la recuperación de información multimedia, minería de datos y aprendizaje automático, especialmente en el contexto de grandes conjuntos de datos.

Artículos de investigación destacados:

• “Approximate k-NN Graph Construction: a Generic Online Approach” de Wan-Lei Zhao et al.:
  Presenta un método eficaz tanto para la búsqueda aproximada de vecinos más cercanos como para la construcción de grafos. El artículo demuestra una solución dinámica y factible para manejar escalas y dimensiones de datos diversas, permitiendo actualizaciones en línea que no son posibles en muchos métodos existentes. Leer más.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” de Magdalen Dobson y Guy Blelloch:
  Introduce algoritmos paralelos que combinan kd-tree y el ordenamiento Morton en una estructura zd-tree, optimizada para datos de baja dimensión. Los autores muestran que su enfoque es más rápido que los algoritmos existentes, logrando importantes aumentos de velocidad con procesamiento paralelo. El zd-tree permite, de manera única, actualizaciones dinámicas por lotes en paralelo, siendo el primero en las estructuras de datos para vecinos más cercanos. Leer más.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” de Sebastian J. Wetzel:
  Explora un enfoque novedoso para la regresión de vecinos más cercanos utilizando redes neuronales gemelas. Este método se centra en predecir diferencias entre objetivos de regresión, logrando un mejor rendimiento respecto a las redes neuronales tradicionales y técnicas estándar de regresión KNN en conjuntos de datos pequeños a medianos. Leer más.