Algoritmia Informática y Matemáticas Inteligencia Artificial Investigación

abril 15, 2020

Tiempo de lectura: 6 minutos

Hace unas semanas subí un pequeño artículo que explicaba para qué son útiles los algoritmos de Machine Learning y expliqué un pequeño ejemplo que nos permitía calcular un algoritmo aproximado de lo que sería una auténtica solución.

Por ello, hoy os traigo un algoritmo real de Machine Learning, utilizado por muchas empresas para mostrar sugerencias de imágenes, etiquetas, ubicaciones… por ejemplo, la página web GIPHY (que es la encargada de dar soporte a los gifs de Instagram) utiliza este algoritmo para sugerir etiquetas a los gifs subidos por sus usuarios.

¿Qué es el algoritmo K-Nearest?

K-Nearest Neighbor (KNN) es un algoritmo de ML que clasifica datos (data)
no etiquetados en función de datos sí etiquetados que le proporcionamos al modelo (input). Este método sirve tanto para clasificar nuevas muestras (valores discretos) como para predecir (regresión, valores continuos).

Por ejemplo, este modelo puede entrenarse para reconocer que las fotos en las que aparece un perro tienen la etiqueta “perro”, de forma que etiquetará con “perro” todas las imágenes nuevas con dicho animal.

La simplicidad de KNN radica en que tan solo busca en las observaciones más cercanas al punto cuya probabilidad se está tratando de predecir y lo clasifica en función de los datos que le rodean.
Para ello, primero definimos la distancia entre todas las observaciones basadas en los elementos de entrada. Después, para cada punto $(x_1,x_2)$ para el que queramos estimar su probabilidad $p(x_1,x_2)$ , observamos los k puntos más próximos a $(x_1,x_2)$ y hacemos una media de los ceros y unos asociados a dichos puntos.
Nos referiremos a los puntos utilizados para calcular la media como los vecinos (the neighbors).
Esto nos proporcionará un valor $\hat{p}(x_1,x_2)$ que utilizaremos como estimador de $p(x_1,x_2)$ .

Ventajas

Una de las ventajas que presenta este algoritmo es que podemos controlar la flexibilidad del mismo a través del parámetro k: con un valor de k elevado tenemos unos valores estimados más “suaves”, mientras que con valores de k pequeños tenemos valores estimados más “escarpados”. A continuación adjunto un ejemplo de cálculo con los mismos datos, variando el valor de k para que veáis a que me refiero con suave y escarpado:

Fig 1: Comparación para valores de k=5 y 401.

Cómo podéis observar, si tenemos una k que nos proporcione valores muy escarpados, nuestro modelo se va a ajustar demasiado a los datos proporcionados para su entrenamiento (los datos actuales), por lo que sería poco eficiente para otras muestras. Mientras, si tomamos un valor de k muy elevado nuestro modelo se transformaría prácticamente en un algoritmo lineal (basado en regresión, como vimos en el artículo anterior), lo cual no es lo que queremos hacer (buscamos algo más eficiente que lo que ya conocemos).

¿Cómo escogemos entonces k?

Pues aplicando el método de Cross Validation (os dejo un enlace que explica cómo aplicarlo a un modelo), el cual nos proporciona la k que maximiza la probabilidad, es decir, minimiza el error cuadrático medio esperado.

Antes de proseguir os adjunto aquí un ejemplo de la influencia del valor de k aplicado a la clasificación de gifs según sus etiquetas (ejemplo comentado con anterioridad):

GIPHY Gets Tagged by K-Nearest Neighbors

Recapitulemos

Tenemos por lo tanto un algoritmo de ML basado en un conjunto de datos de entrenamiento, cuyos resultados utiliza posteriormente para clasificar los elementos analizados en una categoría u otra. Para calcular el radio de selección de elementos que van a influir en la muestra tenemos el parámetro k, el cual calculamos a partir del método de Cross Validation, que nos proporciona el mayor $\hat{p}(x_1,x_2)$ (valor estimado de la probabilidad).

Código

Hasta aquí todo bien, ¿no? Pues vamos a mancharnos un poco las manos con código. Para esta explicación utilizaré el mismo ejemplo que en el artículo anterior: clasificación de un 2 o un 7 escrito a mano.

Comenzamos accediendo a los datos y enseñando un gráfico de la salida:

library(tidyverse)
library(dslabs)
data(“mnist_27")
mnist_27$test%>% ggplot(aes(x_1, x_2, color = y)) +  geom_point()

Usaremos esta información para estimar la probabilidad condicionada:

$p(x_1,x_2)=Pr(Y=1|X_1=x_1,X_2=x_2)$

Aplicando la teoría explicada en el apartado anterior estimamos $p(x_1,x_2)$ definiendo la distancia entre todas las observaciones basadas en los elementos de entrada.

Para implementar el algoritmo usaremos la función knn3 del paquete caret de R. La fórmula a implementar tendrá la forma: $salida\thicksim predictor_1+predictor_2+predictor_3…$

Por lo tanto, escribiremos $y\thicksim.$ , sirviendo el punto para seleccionar todos los predictores:

library(caret) knn_fit <- knn3(y ~ ., data = mnist_27$train, k=5)

Primera aproximación

Cómo podeís observar tenemos que seleccionar un valor de k; empezamos con 5. La función de predicción para KNN produce la probabilidad para cada clase, por lo que seleccionaremos la probabilidad de ser 7 (de forma totalmente trivial) como el valor $\hat{p}(x_1,x_2)$ .

y_hat_knn <- predict(knn_fit, mnist_27$train, type = "class")
confusionMatrix(y_hat_knn, mnist_27$test$ y)$overall[“Accuracy”]

Obtenemos así una precisión del 81.5%, mejor que el 75% que obteníamos mediante regresión lineal.

Para que os hagáis una idea, esto es lo que hemos conseguido construir:

Fig 2: Resultado para k=5 comparado con el valor real de la probabilidad

Vemos claramente que el método KNN se adapta mucho mejor a la forma curva (no lineal) de $p(x_1,x_2)$ .

A pesar de ello, nuestro estimador presenta algunas islas azules, es decir, se trata de una muestra demasiado específica que no se adaptará bien a muestras que difieran mucho del training set. He aquí la importancia de tomar el valor de k adecuado.

Si por ejemplo tomamos k=401 ocurre precisamente lo contrario, lo que hacemos es “suavizar” en extremo la gráfica, siendo esta muy similar al modelo de regresión:

Fig.3: Resultado para k=401 comparado con el modelo de regresión

Segunda aproximación

Sin embargo, tomando la k que minimiza el error cuadrático medio esperado (en este caso k=27), podemos obtener resultados realmente asombrosos:

train_knn <- train(y ~ ., method = “knn”, 
                   data = mnist_27$train,
                   tuneGrid = data.frame(k = seq(9, 71, 2)))

Hemos conseguido alcanzar una precisión del 83.5%, y aunque existen algoritmos que pueden alcanzar hasta el 98% de precisión, no es un mal resultado para una lección rápida (y con tan poco código, que eso siempre suele animar 😉).

Espero que os haya gustado y si os interesa conocer algún otro método con resultados más precisos hacédmelo saber en los comentarios ⚡️🤙🏽.

AUTORA

María Caseiro Arias
Matemáticas e Ingeniería Informática

BIBLIOGRAFÍA

Puntuación

Votos: 1 Promedio: 5

María Caseiro Arias

Web | + posts

Coordinadora de desarrollo y diseño web de QS.
Estudiante de 6º de Matemáticas e Ing.Informática en la Universidad de Santiago de Compostela.

#Algoritmia Avanzado Data Science Machine Learning

CONTINUACIÓN DE MACHINE LEARNING CON R #2