El algoritmo k-nearest neighbours (k-NN) es relativamente simple de entender. Primero, debes saber que es un algoritmo de aprendizaje supervisado que nos permite resolver no solo un problema de clasificación, sino también un problema de regresión.
Como recordatorio, el aprendizaje supervisado es cuando un algoritmo necesita datos de entrada etiquetados (es decir, entradas con una etiqueta) y datos de salida (es decir, datos que el algoritmo tendrá que predecir más adelante).
La idea es la siguiente: en una fase de aprendizaje, el algoritmo debe ser entrenado para aprender la relación entre las entradas y salidas de datos.
Este es un punto clave. De hecho, el aprendizaje supervisado se basa en la organización de los datos según una serie de pares {entrada-salida}.
Una vez que el algoritmo ha sido entrenado, puede predecir un
valor de salida, únicamente sobre la base de los valores de entrada.
El método de k-vecinos más cercanos y sus principios
Una vez que se ha completado una fase de aprendizaje del algoritmo, el algoritmo puede hacer una predicción basada en una nueva observación desconocida al encontrar la observación más cercana en el conjunto de datos de entrenamiento.
Luego, el algoritmo asigna la etiqueta de estos datos de entrenamiento a la nueva observación, que antes se desconocía.
La k en la fórmula “k-vecinos más cercanos” significa que en lugar de solo el vecino más cercano de la observación desconocida, se puede considerar un número fijo (k) de vecinos en el conjunto de datos de entrenamiento.
En última instancia, podemos hacer una predicción basada en la clase mayoritaria de este barrio.
Este principio puede parecer complicado de explicar, pero observe el siguiente ejemplo que simplemente ilustra la idea general de este método.
Una ilustración simple del principio de funcionamiento del algoritmo:
Encontremos los K vecinos más cercanos de la observación desconocida “?”
En resumen, los pasos del algoritmo son los siguientes: A partir de los datos de entrada:
• Se selecciona una función de definición para la distancia (también conocida como función de similitud) entre las observaciones. (Volveremos a esto en el siguiente párrafo).
• Establecemos un valor para “k”, el número de vecinos más cercanos.
Pseudocódigo:
Debemos hacer lo siguiente para una nueva observación de entrada desconocida para la que queremos predecir la variable de salida.
- Paso 1: calcule todas las distancias entre esta observación y las demás observaciones en el conjunto de datos.
- Paso 2: seleccione las observaciones del conjunto de datos que son las “más cercanas” a la observación pronosticada.
Nota: Para determinar si un valor está “más cerca” que otro, se utiliza una función de similitud basada en el cálculo de la distancia (consulte el siguiente párrafo).
- Paso 3 – Tome los valores de las observaciones seleccionadas:
Si se realiza una regresión, el algoritmo calculará el promedio (o la mediana) de los valores de las observaciones seleccionadas.
Si se realiza una clasificación, el algoritmo asignará la etiqueta de clase mayoritaria a los datos previamente desconocidos.
- Paso 4: devuelva el valor calculado en el paso 3 como el valor que predijo el algoritmo para la observación de entrada previamente desconocida.
Para este algoritmo, la elección del número (k) y la elección de la función de similitud son pasos que pueden hacer que los resultados varíen mucho.
Métricas para evaluar la similitud entre observaciones
Como acabamos de decir, para medir la proximidad entre observaciones se debe imponer al algoritmo una función de similitud.
Esta función calcula la distancia entre dos observaciones y estima la afinidad entre las observaciones de esta manera: “Cuanto más cerca están dos puntos entre sí, más similares son”.
Sin embargo, esta declaración trivial viene con algunos matices matemáticos y hay muchas funciones de similitud en la literatura relacionada.
La distancia euclidiana es una de las funciones de similitud más conocidas. Usamos esta función en el ejemplo anterior.
Es la función de similitud más intuitiva porque formaliza la idea de distancia: la distancia en línea recta entre dos puntos en el espacio.
La Distancia Manhattan (también conocida como Geometría Taxicab) corresponde a un movimiento en ángulo recto sobre un tablero de ajedrez.
Si te interesa, te invito a mirar las definiciones matemáticas de otras métricas como la Función de Minkowski, la Función de Jaccard, la Distancia de Hamming, la Distancia de Levenshtein, la Métrica de Jaro, o incluso la Distancia de Jaro-Winker.
Debe saber que la función de distancia generalmente se elige de acuerdo con los tipos de datos que estamos manejando y el significado matemático o físico del problema a resolver. La distancia euclidiana es una buena opción para comenzar con datos cuantitativos (p. ej., altura, peso, salario, facturación, etc.), ya que es muy esquemática.
La distancia de Manhattan puede ser interesante para datos que no son del mismo tipo (por ejemplo, datos que no se han puesto en la misma escala). Además, le recomiendo encarecidamente que profundice en su conocimiento del tema para dominar los casos de uso clásicos de las diversas funciones de similitud, según el problema a resolver.
Tu turno para programar… (Python)
Este párrafo proporciona algunos elementos para ayudarlo a codificar el algoritmo usted mismo. Todos los modelos de aprendizaje automático en scikitlearn se implementan en sus propias clases, que se denominan clases Estimator.
La clase para el algoritmo de k-vecinos más cercanos es KNeighboursClassifier, del módulo de vecinos.
Antes de que podamos usar la plantilla, debe crearse una instancia de la siguiente manera:
En nuestro ejemplo, el objeto clasificador encapsula el algoritmo que se usará para crear el modelo a partir de los datos de entrenamiento, así como el algoritmo que hará predicciones para nuevas observaciones.
Para crear el modelo k-NN, primero debemos dividir los datos en 2 bases de datos: una para entrenar el algoritmo y otra para probar el rendimiento obtenido.
Nota: test_size = 0.2 = 20% da el tamaño de la base de datos de prueba, es decir, el 20% de la muestra de datos inicial.
A continuación, usamos el método de ajuste del objeto clasificador, que toma como argumentos el conjunto de datos de entrenamiento X_train y el conjunto de datos de prueba y_train.
El método de ajuste devuelve el propio objeto k-NN.
La configuración del algoritmo por defecto es la siguiente:
KNeighboursClassifier (algorithm=’auto’, leaf_size=30, metric=’minkowski’, n_jobs=1, n_neighbours=3, p=2, weights=’uniformes’)
Notará que todos los parámetros, excepto el número de vecinos más cercanos, tienen su valor predeterminado establecido en n_ vecinos = 3.
Para hacer una predicción sobre nuevos datos desconocidos, creamos un vector que contiene los datos de entrada conocidos. El vector X_new está debajo.
Luego usaremos el método de predicción del objeto clasificador.
Las limitaciones del algoritmo de K-vecinos más cercanos
Although the operation of the nearest neighbours algorithm is easy to understand, the main drawback of the method is its cost in terms of complexity. Indeed, the algorithm searches for the k-nearest neighbours for each observation. Therefore, if the database is very large (a few million rows), the calculation time can be extremely long. Special attention must therefore be paid to the size of the input data set.
Another focal point: the choice of similarity function can lead to very different results between models.
It is therefore recommended to create a rigorous state of the art to better choose the similarity distance according to the problem to be solved. Above all, it is recommended to test several combinations to estimate the impact on the results.
Despite everything, remember that if the k-NN algorithm is interesting from a didactic point of view, it is almost never used as it is by data scientists.
Para datos de alta dimensión, es necesario utilizar técnicas de reducción de dimensionalidad (como PCA, ACM, CCA) antes de aplicar el algoritmo k-NN, de lo contrario, la Distancia Euclidiana será inútil para medir distancias de similitud en un espacio grande. Un buen caso de uso para KNN es ver qué artículos comunes los clientes compran juntos, para animarlos a completar su cesta. Por un lado, esto crea una experiencia de cliente personalizada al facilitar la búsqueda de artículos necesarios; y uno por el otro, aumenta los ingresos.
