Sobre sistemas de recomendación, ejemplo sencillo.

Sobre los sistemas de recomendación

Los sistemas de recomendación son quizás una de esas cosas con las cuales todos tenemos contacto actualmente, van desde sistemas sofisticados y predictivos, hasta otros menos rebuscados que solo nos hacen una lista fija de sugerencia. Los ejemplo conocidos son youtube, spotify, los sistemas de facebook, amazon, Netflix,etc.

Pese a que no es un tema fijo o algo que aparezca como tema dentro de las referencias importantes de Machine Learning, existen algunas referencias que hablan sobre el tema [2] y en particular un laboratorio reconocido por su investigación en sistemas de recomendación es GroupLens de la Universidad de Minnesota.

Este tipo de sistemas se hicieron famosos gracias a la competencia de Netflix,  en la cual un equipo logró cumplir con el reto de minimizar un indicador estadístico para asegurar que se obtenían mejores sugerencias [3]. Existen mucho artículos respecto a este concurso y sobre el sistema que se desarrollo, pero lo que se debe de resaltar es que el equipo ganador no hizo solo de un algoritmo de Machine Learning, uso varios y la parte más importante fue el pre-procesamiento de los datos [4].

Sobre el ejemplo

El siguiente ejemplo de sistema de recomendación lo presento como se discute el texto Machine Learning for Hackers [1]. En el ejemplo se hace uso de la técnica k-Nearest Neighbor(Knn) para definir las recomendaciones, es un método de clasificación no paramétrico. Antes de explicar un poco sobre Knn hago un ejemplo sencillo sobre series de tiempo y principalmente sobre la estimación de la “regresión de k-vecinos cercanos“.

#Regresión Vecinos Cercanos
Mortalidad<-scan("data/cmort.dat")
t=1:lenght(Mortalidad)
#Usamos la función supsmu
plot(t,Mortalidad,col="4",main="Mortalidad por semanas",xlab="Semanas",ylab="Número de muertes")
lines(supsmu(t,Mortalidad,span=0.5),col="2")
lines(supsmu(t,Mortalidad,span=0.01),col="4")

Ejemplo_Regresión_vecinos_cercanos

En la gráfica se observan dos curvas cercanas a los datos que están en color verde.Observando con detenimiento la curva en rojo se parece mucho a la línea de tendencia de los datos, pero no es tal cual una recta. Por otro lado la curva en azul, parece más cercana a una descripción del comportamiento “real” de los datos. En ambos casos lo que se hace es ir calculando una regresión para cierta cantidad de vecinos cercanos a cada punto, la línea roja se calcula para una cantidad mayor de vecinos en cada punto y la azul para una cantidad menor, por ello la línea roja no es una recta del todo y la azul tiene pequeños picos y a la vista nos parece mejor para describir los datos.

La gráfica anterior dice que cuando se calcula la regresión o el mejor ajuste lineal para una cantidad mayor de vecinos se tiende a seguir la tendencia de los datos. Cuando se calcula para una cantidad menor de vecinos es probable que la curva siga de cerca el comportamiento de los datos. Con este ejemplo solo deseo mostrar que Knn es hasta cierto punto útil para hacer exploración de la información y que si bien este caso es una regresión, la idea en general es la misma de considerar los vecinos cercanos. Esto de que “parezca” muy parecido a los datos tienen un costo  en el sentido estadístico en caso de considerar dichos algoritmos como candidatos para implementación.

Una imagen burda del algoritmo Knn es pensar en que si se está localizado en uno de los datos en color verde  se traza un circulo centrado en ese punto y se cuenta la cantidad k vecinos para luego hacer la regresión. Lo que se debe de resaltar es que trazar un circulo implica hablar de una distancia para comparar qué puntos están dentro o no del circulo, igual que en el análisis de Cluster se requiere la noción de distancia en el algoritmo de Knn.

Hago un ejemplo solo para mostrar como funciona la librería class que contiene la función knn que permite hacer el cálculo de k-vecinos cercanos. Tomo un subconjunto de entrenamiento y uno de prueba, estimo el modelo para el conjunto de datos de entrenamiento y comparo el resultado con los datos de prueba. Hago una comparación de un método lineal paramétrico de clasificación ( regresión logística) con respecto al método Knn.

Los datos empleados se pueden descargar desde github.

#Comparación de métodos
data.path<-file.path("data","example_data.csv")
datos<-read.csv(data.path)
n<-1:nrow(datos)
set.seed(1)

#Tomamos el 50% de los datos
library(class)
indices<-sort(sample(n,50))
training.x<-datos[indices,1:2]
training.y<-datos[indices,3]
test.x<-datos[-indices,1:2]
test.y<-datos[-indices,3]
#Aplicamos el método Knn
prediccion<-knn(training.x,test.x,training.y,k=5)
sum(prediccion!=test.y)
#Aplicamos un método lineal logit
modelo.logit<-glm(Label~ X+Y,data=datos[indices,])
prediccion2<-as.matrix(predict(modelo.logit,newdata=df[-indices,])>0)
sum(prediccion2!=test.y)

Se observa que en el ejemplo el método Knn da como predicción un 88% de coincidencias y el método lineal solo el 60%. Así que para situaciones no lineales se puede usar con mejor eficiencia el método Knn. Cuando digo predicción, me refiero a cuantos de los puntos de prueba el método clasificó correctamente y cuantos no.

Ejemplo de sistema de recomendación

Para el ejemplo se toma un conjunto de datos respecto a los paquetes instalados en R project. La intención de detectar de una lista de paquetes instalados cuando un usuario va  instalar otro paquete sabiendo cuales tiene instalados. Fue parte de una competencia en Kaggle. Lo interesante es ver que con una muestra pequeña se pudo aprender del comportamiento de los usuarios caracterizados por los paquetes instalados.

#Revisión de paquetes instalados
data.path<-file.path("data","isntallations.csv")
instalaciones<-read.csv(data.path)
#Revisamos las cabeceras
head(instalaciones)
#Construimos una matriz de datos
library(reshape)
matriz.de.paquetes<-cast(instalaciones,User~Package,value='Installed')
#Modificamos las filas 
row.names(matriz.de.paquetes) <- matriz.de.paquetes[, 1]
matriz.de.paquetes <- matriz.de.paquetes[, -1]
#Matriz de similitud
matriz.similitud <- cor(matriz.de.paquetes)
#Definimos una distancia
distancia <- -log((matriz.similitud / 2) + 0.5)

#Calculamos los vecinos cercanos
k.nearest.neighbors <- function(i, distancia, k = 25)
{
 return(order(distancia[i, ])[2:(k + 1)])
}

#Función para estimar la probabilidad
prob.instalacion <- function(user, package, matriz.de.paquetes, distancia, k = 25)
{
 neighbors <- k.nearest.neighbors(package, distancia, k = k)
 
 return(mean(sapply(neighbors, function (neighbor) {matriz.de.paquetes[user, neighbor]})))
}

#Función para elegir los paquetes más probables de isntalar
paquetes.mas.prob <- function(user,matriz.de.paquetes, distancia, k = 25)
{
 return(order(sapply(1:ncol(matriz.de.paquetes),
 function (package)
 {
 prob.instalacion(user,package,matriz.de.paquetes,distancia,k = k)
 }),
 decreasing = TRUE))
}

user <- 1

listing <- paquetes.mas.prob(user, matriz.de.paquetes, distancia)

colnames(matriz.de.paquetes)[listing[1:15]]
 [1] "adegenet" "AIGIS" "ConvergenceConcepts" "corcounts" "DBI" "DSpat" "ecodist" 
 [8] "eiPack" "envelope" "fBasics" "FGN" "FinTS" "fma" "fMultivar" 
[15] "FNN" 

Explico en lo general los pasos del código anterior. Primero  se cargan los datos que se encuentran en formato “csv”, luego se transforman a una matriz lo cual se hace con la función cast de la librería reshape. Una vez transformados, se calcula su matriz de correlaciones, pero la observación es que el método Knn no funciona con la matriz de correlaciones, sino con la matriz de distancias o similitudes.

El paso clave es usar el logaritmo y definir una distancia mediante la “normalización” de los valores obtenidos en la matriz de correlaciones, este paso es crucial para poder aplicar el algoritmo. Espero se pueda entender este paso, lo que se hace es considerar que las correlaciones tienen valores entre -1 y 1, suponiendo que no se alcanza el valor -1, entonce el intervalo de posibles valores tienen longitud 2. Si dividimos cada valor de la correlación sobre 2 y después se le sumamos 0.5, obligamos a que los valores estén entre 0 y 1. El logaritmo , de hecho el negativo del logaritmo con valores entre 0 y 1 indicarán que cuando los valores se aproximen a cero indica que son más distantes los paquetes de los usuarios  y que cuando se aproximen a 1 son muy cercanos.

Por último define una funciones que permite estimar la probabilidad mediante el cálculo de Knn. Entonces se obtiene una matriz la cual permite conocer cuales son los paquetes con mayor probabilidad para poder recomendarlos al usuario. La última línea muestra los 15 paquetes con mayor probabilidad de recomendar al usuario 1.

Entonces construir un sistema de recomendaciones es prácticamente tener una versión de este tipo de algoritmos o de este tipo de técnicas en el sistema, pero como lo mencioné al inicio de la entrada no existe un solo algoritmo útil para estos sistemas ya que se puede recurrir a varios para determinar cual funciona de manera adecuada. Ejemplo, si los datos muestran un comportamiento lineal es preferible usar la regresión logística que knn ya que clasificará mejor los datos.

Puede parecer confuso lo que hago en el ejemplo, pero en resumen es lo siguiente:

  1. Se cargaron los datos.
  2. Se construye una matriz de correlaciones con la información de los paquetes instalados en cada usuario.
  3. Se define una matriz de distancia por medio de la matriz de correlaciones.
  4. Se aplica el método Knn, el cual estimará los paquetes más cercanos a cada usuario.

Faltaría diseñar una interfaz agradable para mostrar los resultados.

Referencias:

1.-http://shop.oreilly.com/product/0636920018483.do

2.-http://www.mmds.org/

3.-http://www.wired.com/2009/09/bellkors-pragmatic-chaos-wins-1-million-netflix-prize/

4.-http://www.netflixprize.com/assets/ProgressPrize2008_BigChaos.pdf

Anuncios

Un comentario sobre “Sobre sistemas de recomendación, ejemplo sencillo.

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s