El Algoritmo KNN (K Nearest Neighbours)

El algoritmo “k nearest neighbours”, traducido como “los k vecinos más cercanos”, es aquel que se basa en la búsqueda de atributos similares dentro del conjunto de los datos, y así poder predecir la clase a la que pertenece dicho atributo. Llevado hacia un razonamiento más humano, se  podría explicar así: “Si se parece a un avión, es tan grande como un avión, vuela y van personas dentro, entonces es un avión”. Entra dentro de los algoritmos supervisados, y no debe confundirse con el K-Means.

Este algoritmo destaca por tener la K delante, que viene a indicar el número de vecinos con los que se va a comparar la observación determinada para obtener cuál es su clase. Así, si K es igual a 1, el elemento que esté más cerca de la observación sobre la que se quiere saber la clase será la que determine la clase de la misma. En caso de que el número K sea un número mayor, la clase que posea más elementos cerca de la observación será la que determine el tipo de la observación. En caso de que haya dos o más clases en estado de empate, se resuelve de forma arbitraria.

Es importante incidir en que la búsqueda de estos K vecinos se realiza de una forma radial mediante distancias gaussianas, de tal manera que, cuanto mayor sea K, más grande será el círculo que se formará alrededor de la observación determinada para buscar los vecinos de la misma.

Explicación práctica

Como se puede apreciar en la figura anterior, el elemento sobre el que se quiere predecir la clase, representado con una estrella, ha buscado a los 3 elementos más cercanos y los ha introducido dentro de un círculo. Como se puede observar, es mayoría el número de elementos naranjas a los de azul dentro de este círculo, de tal manera que el elemento cuya clase estamos determinando tendrá inferida la clase B, correspondiente al grupo naranja.

 

El algoritmo funciona usando la distancia como elemento de similitud, puesto que dos elementos muy cercanos se supone que serán muy parecidos. Así, del elemento del que se quiere saber el grupo se obtiene una lista de elementos cercanos, y usando modernas técnicas de indexación las computaciones que se deben de hacer para obtener esta lista son mucho menores.

Una vez que se tiene la lista, se clasifica en función del grupo que posea la mayoría, donde todas las observaciones de la lista poseen el mismo peso.

Características del KNN

El algoritmo KNN alberga una serie de características propias que determinan cuando debe ser utilizado y los “peligros” que entraña, exponiéndose todo ello a continuación:

  1. Este algoritmo no requiere de la construcción de un modelo explícito

Un modelo es el conjunto de un algoritmo con una serie de datos. El algoritmo KNN no crea modelo, de tal manera que no se pierde tiempo a la hora de la creación del mismo, pero a la hora de la computación del algoritmo es bastante costoso debido a la necesidad de calcular las distancias de todos los elementos a determinar con el resto de elementos. Recordemos que otros modelos, como el SVM, sí crean modelo.

  1. Es un algoritmo que toma decisiones en zonas locales, no globalmente

Como se puede deducir, al mirar sólo a los elementos más cercanos se incurre en que se toma una decisión a nivel local, no como otros algoritmos como los árboles de decisión, que las toman a nivel global. De esta forma, se deberá tener especial cuidado con los valores de K, puesto que un valor pequeño es susceptible al ruido que pueda generar una zona y, por lo tanto, brindar un valor erróneo.

Además, este modelo sufre de underfitting y overfitting muy fácilmente si no se obtiene un valor de K preciso. En caso de obtener un valor demasiado pequeño, debido al ruido se caerá en overfitting, puesto que solo miraremos el elemento más cercano. Si el valor de K, por el contrario, es demasiado grande, se puede sufrir de underfitting y el modelo se volverá demasiado simple. De este modo, como aproximación se suele aceptar que el valor de K sea la raíz cuadrada del número total de elementos a determinar, aunque este valor siempre debe de ser corroborado puesto que depende de los datos del problema.

  1. KNN produce predicciones erróneas si no se hace un pre-procesamiento correcto

KNN es un algoritmo muy delicado en términos de pre-procesamiento, puesto que al trabajar con distancias son importante los cambios que se hagan a las medidas de los datos. Por ejemplo, si hay numerosas dimensiones cercanas a un número, y también hay otra dimensión con una variabilidad enorme, el algoritmo no funcionará bien puesto que esta última será la más influyente de todas.

De este modo, para trabajar con este algoritmo un pre-procesamiento a base de centrado y escalado, y una eliminación de las columnas menos importantes escogidas con un PCA sería óptimo.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Si sigue navegando por esta página daremos por hecho que acepta nuestra política de cookies.    Ver Política de cookies