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

Obtenga más información sobre el algoritmo de los k vecinos más cercanos, uno de los clasificadores de clasificación y regresión populares y más simples que se utilizan actualmente en el machine learning.

Vista posterior del código de escritura del desarrollador

Algoritmo de k vecinos más cercanos

El algoritmo de k vecinos más cercanos, también conocido como KNN o k-NN, es un clasificador de aprendizaje supervisado no paramétrico, que utiliza la proximidad para hacer clasificaciones o predicciones sobre la agrupación de un punto de datos individual. Si bien se puede usar para problemas de regresión o clasificación, generalmente se usa como un algoritmo de clasificación, partiendo de la suposición de que se pueden encontrar puntos similares cerca uno del otro.


Para los problemas de clasificación, se asigna una etiqueta de clase sobre la base de un voto mayoritario, es decir, se utiliza la etiqueta que se representa con más frecuencia alrededor de un punto de datos determinado. Si bien esto técnicamente se considera "voto por mayoría", el término "voto por mayoría" se usa más comúnmente en la literatura. La distinción entre estas terminologías es que "voto mayoritario" 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 al que puede acceder  aquí  (PDF, 1,2 MB)  (enlace externo a ibm.com). 

Los problemas de regresión usan un concepto similar al de los problemas 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 distinción principal 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, y nos profundizaremos más a continuación.
También vale la pena señalar que el algoritmo KNN también forma parte de una familia de modelos de "aprendizaje perezoso", lo que significa que solo almacena un conjunto de datos de entrenamiento en lugar de pasar por una etapa de entrenamiento. Esto también significa que todo el cálculo ocurre 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 lo denomina método de aprendizaje basado en instancias o basado 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 (PDF, 1,1 MB)  (enlace externo a ibm.com)  mientras que Thomas Cover amplía su concepto en su  investigación  (PDF 1 MB) (enlace externo a ibm.com), "Clasificación de patrones de vecinos más cercanos". Si bien no es tan popular como lo fue antes, sigue siendo uno de los primeros algoritmos que uno aprende 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 usa comúnmente para sistemas de recomendación simples, reconocimiento de patrones, extracción de datos, predicciones del mercado financiero, detección de intrusos y más. 


Calcular KNN: métricas de distancia

En resumen, el objetivo del algoritmo del vecino más cercano es identificar los vecinos más cercanos de un punto de consulta dado, de modo que podamos asignar una etiqueta de clase a ese punto. Para hacer esto, KNN tiene algunos requisitos:

Determine sus métricas de distancia

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 otros 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. Por lo general, verá límites de decisión visualizados 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 utilizada y está limitada a vectores de valor real. Usando la fórmula a continuación, mide una línea recta entre el punto de consulta y el otro punto que se mide.

Distancia 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 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 usa típicamente con vectores booleanos o de cadena, identificando los puntos donde los vectores no coinciden. Como resultado, también se la conoce como la métrica de superposición. Esto se puede representar con la siguiente fórmula:

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


Calcule KNN: definiendo k

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 llevar 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 grandes de k pueden generar 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 la k óptima para su conjunto de datos.

k vecinos más cercanos y python

Para profundizar más, puede aprender más sobre el algoritmo k-NN usando 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:

de sklearn.neighbors importar KNeighborsClassifier
model_name = 'K-Clasificador de vecino más cercano'
knnClassifier = KNeighborsClassifier(n_vecinos = 5, métrica = 'minkowski', p=2)
knn_model = Pipeline(steps=[('preprocessor', preprocessorForFeatures), ('classifier' , knnClassifier)])
knn_model.fit(X_tren, y_tren)
y_pred = knn_model.predict(X_test)


Aplicaciones de k-NN en machine learning

El algoritmo k-NN se ha utilizado en una variedad de aplicaciones, principalmente dentro de la clasificación. Algunos de estos paquetes incluyen:

-Preprocesamiento de datos: Los conjuntos de datos suelen tener valores faltantes, pero el algoritmo KNN puede estimar esos valores en un proceso conocido como imputación de datos faltantes.

-Motores de recomendación : utilizando datos de flujo de clics de sitios web, el algoritmo KNN se ha utilizado para proporcionar recomendaciones automáticas a los usuarios sobre contenido adicional. Estainvestigación  (enlace externo a ibm.com) muestra que un usuario está asignado 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 económico y financiero. Por ejemplo, un artículo (PDF, 439 KB)  (enlace externo a ibm.com)  muestra cómo el uso de KNN en datos crediticios puede ayudar a los bancos a evaluar el riesgo de un préstamo para una organización o individuo. Se utiliza para determinar la solvencia crediticia de un solicitante de préstamo. Otro periódico  (PDF, 447 KB) (enlace externo ibm.com)  destaca su uso en la previsión del mercado de valores, valores de cambio de divisas, comercio de futuros y análisis de lavado de dinero.

Cuidado de la salud: KNN se ha aplicado dentro de la industria de la salud, haciendo predicciones sobre el riesgo de ataques cardíacos 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 texto y clasificación de dígitos  (enlace externo a ibm.com). Esto ha sido particularmente útil para identificar números escritos a mano que puede encontrar en formularios o sobres de correo. 


Ventajas y desventajas del algoritmo KNN

Al igual que cualquier algoritmo de machine learning, k-NN tiene sus puntos fuertes y débiles. Dependiendo del proyecto y la aplicación, puede o no ser la elección correcta.

Ventajas

- 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 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, que es baja en comparación con otros algoritmos de machine learning.

Desventajas

- No escala bien: Dado que KNN es un algoritmo perezoso, ocupa más memoria y almacenamiento de datos en comparación con otros clasificadores. Esto puede ser costoso desde una perspectiva de tiempo y dinero. Más memoria y almacenamiento aumentarán los gastos comerciales y más datos pueden tardar más en procesarse. Si bien 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. Esto a veces también se conoce como fenómeno de pico  (PDF, 340 MB)  (enlace externo a ibm.com), donde después de que el algoritmo alcanza la cantidad óptima de funciones, las funciones 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. 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 están promediando los valores en un área o vecindario más grande. Sin embargo, si el valor de k es demasiado alto, entonces puede ajustarse mal a los datos. 


Soluciones relacionadas

IBM Cloud Pak for Data

IBM Cloud Pak for Data es una plataforma de datos abierta y extensible que proporciona una estructura de datos para que todos los datos estén disponibles para inteligencia artificial y análisis, en cualquier nube.


IBM Watson Studio

Cree, ejecute y gestione modelos de IA. Prepare datos y cree modelos en cualquier nube utilizando código fuente abierto o modelado visual. Prediga y optimice sus resultados.


IBM Db2 on Cloud

Obtenga más información sobre Db2 on Cloud, una base de datos SQL en la nube completamente gestionada y optimizada para obtener excelentes resultados.



Próximos pasos

Nodo k-NN e IBM Cloud Pak for Data

Cloud Pak for Data es un conjunto de herramientas que ayuda a preparar los datos para la implementación de IA. El nodo k-NN es un método de modelado disponible en IBM Cloud Pak for Data, que facilita mucho el desarrollo de modelos predictivos. El complemento se implementa en cualquier nube y se integra a la perfección en su infraestructura de nube existente.