Método de los K vecinos más cercanos

Share on facebook
Share on twitter
Share on linkedin

En machine learning, un método sencillo de clasificación y regresión es el de los K vecinos más cercanos (en inglés K-nearest neighbors, k-NN). Es un método no paramétrico. Se usará la notación NN(K, xq) para denotar el conjunto de los k vecinos más cercanos al objeto xq.

El algoritmo.

En la clasificación por k-NN, la salida es la pertenencia a una clase. Un objeto es clasificado como perteneciente a una clase si la mayoría de sus k vecinos pertenecen a esa clase: Si se quiere clasificar un objeto, con k= 5 vecinos, con 3 vecinos de la clase A y 2 de la clase B, por mayoría el objeto se clasifica como clase A. Para evitar empates, se prefiere que el número de vecinos k seleccionado sea un número impar. En la regresión por k-NN, la salida es un valor de una propiedad del objeto; ese valor se puede calcular usando el promedio de los valores de los k vecinos. La palabra “cercano” implica una métrica de la distancia. Típicamente se puede usar la distancia Euclidiana:

En el plano cartesiano toma la siguiente forma:

También puede usarse la distancia de Manhattan, conocida como la métrica del taxista:

Cuya forma en el plano cartesiano es:

Es común normalizar los datos de cada una de las dimensiones del objeto, para evitar que un cambio en la escala en alguna de las dimensiones, afecte el resultado.

Los vecinos son tomados de un conjunto de objetos cuya clase (para clasificación) o valor de la propiedad es conocida. Éste sería el conjunto de entrenamiento del algoritmo, aunque no se requiere un entrenamiento explícito.

La función NN(K, xq) es sencilla: dado un conjunto de N ejemplos y un objeto xq, se itera sobre los ejemplos, se mide la distancia a xq desde cada uno y se obtienen los mejores k ejemplos. 

En espacios de dimensión baja con suficientes datos, k-NN funciona muy bien: es muy probable tener suficientes datos cercanos para obtener una buena respuesta. Pero conforme el número de dimensiones aumenta, nos encontramos con la maldición la dimensión (curse of dimensionality en inglés). En el contexto de k-NN, esto significa que la distancia euclidiana no funciona en conjuntos de dimensión alta ya que todos los vectores son casi equidistantes al vector que representa al objeto xq.

La complejidad del algoritmo es de O(N). Sin embargo, para conjuntos de datos más grandes se podría requerir una mejor complejidad por lo que se pueden usar k-NN en conjunto con árboles binarios.

Un ejemplo

El siguiente es un ejemplo simple en el que clasificaremos el punto (4, 3) para saber si es de color azul o rojo. Tenemos los siguientes puntos con sus respectivos colores:

RojosAzules
(1, 1)
(1, 2)
(2, 4)
(2, 5)
(3, 1)
(3, 3)
(4, 2)
(4, 5)
(4, 7)
(5, 2)
(5, 3)
(6, 3)
(7, 1)
(7, 4)
(1, 4)
(1, 7)
(2, 2)
(2, 7)
(2, 8)
(3, 4)
(3, 6)
(4, 4)
(4, 6)
(5, 4)
(5, 5)
(5, 8)
(6, 4)
(6, 5)
(7, 5)

Usando la distancia euclidiana, podemos calcular la distancia entre el punto (4, 3) y los demás puntos. Para este ejemplo seleccionaremos k = 7 vecinos más cercanos.

La siguiente tabla muestra las distancias de cada punto al punto (4, 3).

RojosDistanciaAzulesDistancia
(1, 1)3.605551275(1, 4)3.16227766
(1, 2)3.16227766(1, 7)5
(2, 4)2.236067977(2, 2)2.236067977
(2, 5)2.828427125(2, 7)4.472135955
(3, 1)2.236067977(2, 8)5.385164807
(3, 3)1(3, 4)1.414213562
(4, 2)1(3, 6)3.16227766
(4, 5)2(4, 4)1
(4, 7)4(4, 6)3
(5, 2)1.414213562(5, 4)1.414213562
(5, 3)1(5, 5)2.236067977
(6, 3)2(5, 8)5.099019514
(7, 1)3.605551275(6, 4)2.236067977
(7, 4)3.16227766(6, 5)2.828427125
(7, 5)3.605551275

Como se puede ver en la tabla los puntos (3, 3), (3, 4), (3, 6), (4, 2), (4, 4), (5, 2), (5, 3) y (5, 4) son los puntos con menor distancia al punto (4, 3), de los cuales 4 son rojos y 3 son azules. Por lo tanto, clasificamos el punto (4, 3) como rojo. 

Concluyendo…

El método de los k vecinos más cercanos es sencillo y puede dar excelentes resultados usando datos con pocas dimensiones. Para evitar la maldición de la dimensión, se pueden usar técnicas de extracción de características para reducir la dimensión y poder usar la técnica sin problema. Adicionalmente, existen variaciones del algoritmo, en el que a cada vecino se le asigna un peso, o en el que se reduce el conjunto de datos.

Share on facebook
Share on twitter
Share on linkedin

Comments are closed.

¡Conozcámonos mejor!

Te haremos llegar las novedades de SoldAI, ofertas exclusivas, notificaciones, y mucho más.

¡Deja tu correo, tenemos mucho que contarte!