Recomendador Slope One

IIC 3633 - Sistemas Recomendadores

Denis Parra
Profesor Asistente, DCC, PUC CHile

TOC

En esta clase

  1. Resumen últimas clases
  2. Recomendador Slope One
  3. Ejemplo pequeño

Resumen últimas clases

  • Ranking no personalizado: Ordenar items considerando el porcentage de valoraciones positivas y la cantidad total de valoraciones.

  • Filtrado Colaborativo basado en el usuario: buscar K usuarios más parecidos, luego predecir rating de items no consumidos por el active user.

  • Filtrado Colaborativo basado en items: pre-calcular directamente similaridad entre items co-rated, saltándose búsqueda de K-vecindario.

Métricas y Procedimientos a Considerar para Implementar Tarea 1

  • Métrica de Similaridad/Distancia
  • En CF, tamaño del vecindario
  • En CF, pre-Clustering para evitar cálculo de CF
  • Ponderaciones distintas a usuarios/items con más ratings
  • Tasa training/testing

Tarea 1

  • Plazo hasta el 4 de Septiembre (3 semanas)
  • Considerando un dataset que nosotros les entregaremos, deben utlizar herramientas o implementar los recomendadores vistos hasta ahora y elegir el mejor. Con ese "mejor recomendador" realizarán dos tareas sobre un Hold Out dataset: predecir ratings y generar una lista topN de recomendaciones.
Predicción Recomendación Top-N

Recomendador de Pendiente Uno

Lemire, D., & Maclachlan, A. (2005, April). Slope One Predictors for Online Rating-Based Collaborative Filtering. In SDM (Vol. 5, pp. 1-5).

Los autores se enfocan en 5 objetivos:

  1. Fácil de Implementar y mantener
  2. Actualizable en línea: nuevos ratings deberían cambiar las predicciones rápidamente.
  3. Eficiente al momento de consulta: costo principal debería llevarlo el almacenamiento.
  4. Funciona con poco feedback del usuario
  5. Razonablemente preciso, dento de ciertos rangos en los que una pequeña ganancia en exactitud no signifique un gran sacrificio de simplicidad y escalabilidad.

Idea Principal

Si observamos las diferencias de ratings entre pares de items, podemos hacer una predicción.

Fórmula principal y Ponderación

  • Ecuación Lineal de Pendiente uno

\[ f(x) = x + b \]

  • Si tenemos dos vectores con ratings \(v_i\) y \(w_i\) donde \(i=1..n\), buscamos el mejor predictor de la forma \(f(x)=x+b\) para predecir \(w\) usando \(v\). Luego, tratamos de minimizar la expresión

\[\sum_{i=1}^{n}{(v_i+b-w_i)^2}\]

  • Derivando con respecto a \(b\) e igualando la expresión a 0, nos queda

\[b=\frac{\sum_i{(v_i-w_i)}}{n}\]

Implementación Normal y Ponderaciones

  • Implementación Normal \[dev_{j,i}=\sum_{u \in S_{j,i(\chi)}}{\frac{u_j-u_i}{card(S_{j,i}(\chi))}},\ desviacion\ promedio\ entre\ dos\ items\ i,\ j\] \[P(u)_j = {\frac{1}{card(R_j)}}{\sum_{i \in R_j}{(dev_{j,i}+u_i)}},\ prediccion\ en\ base\ a\ varios\ items\ i\] \[P(u)_j^{S1} = \bar{u}+{\frac{1}{card(R_j)}}{\sum_{i \in R_j}{dev_{j,i}}},\ aproximacion\ cuando\ R_j = S(u)\]
  • Métodos de Ponderación
    • Weighted
    • Bipolar

Métodos de Ponderación

  • Weighted Slope One: Algunos pares de items han sido evaluados por muchos usuarios, otros no tanto

\[P(u)_j^{wS1} = \frac{\sum_{i \in S(u)-\{j\}}{(dev_{j,i}+u_i)c_{j,i}} }{\sum_{i \in S(u)-\{j\} }{c_{j,i}}},\ donde\ c_{i,j} = card(S_{j,i}(\chi))\]

  • Bi-Polar: los items evaluados positivamente son considerados distintos a los evaludos negativamente.

\[dev_{j,i}^{like}=\sum_{u \in S_{j,i(\chi)}^{like}}{\frac{u_j-u_i}{card(S_{j,i}^{like}(\chi))}},\text{ desviacion media entre dos items liked}\] \[p_{j,i}^{like}=dev_{j,i}^{like}+u_i \text{, y de modo similar, } p_{j,i}^{dislike}=dev_{j,i}^{dislike}+u_i\]

Combinando ambos, like y dislike, la predicción queda:

\[P(u)_j^{bpS1} = \frac{\sum_{i \in S(u)^{like}-\{j\}}{p_{j,i}^{like}c_{j,i}^{like}} + \sum_{i \in S(u)^{dislike}-\{j\}}{p_{j,i}^{dislike}c_{j,i}^{dislike}}}{\sum_{i \in S(u)^{like}-\{j\} }{c_{j,i}^{like}} + \sum_{i \in S(u)^{dislike}-\{j\} }{c_{j,i}^{dislike}}}\]

Resultados en paper de Lemire (2005)

Ejercicio :-)

(A pedido de A.P.)

  • Usando Weighted Slope One, calcule qué rating le daría U3 a Spiderman*:
User Harry Potter Batman Spiderman
U1 5 3 4
U2 ? 2 4
U3 4 2 ?
  • Usando Weighted Slope One, calcule qué rating le daría U3 a Spiderman*:
  1. Desviación promedio entre Spiderman y Batman (en la resta, primero Spiderman) \[dev_{j,i}=\sum_{u \in S_{j,i(\chi)}}{\frac{u_j-u_i}{card(S_{j,i}(\chi))}},\text{j: Spiderman, i:Batman}\]
  2. Desviación promedio Spider Man y Harry Potter (en la resta, primero Spiderman) \[dev_{j,i}=\sum_{u \in S_{j,i(\chi)}}{\frac{u_j-u_i}{card(S_{j,i}(\chi))}},\text{j: Spiderman, i:Harry Potter}\]
  3. Predicción: Usando el rating que el usuario U3 le dio a Batman y a Harry Potter, calcular rating de U3 a Spiderman

\[P(u)_j^{wS1} = \frac{\sum_{i \in S(u)-\{j\}}{(dev_{j,i}+u_i)c_{j,i}} }{\sum_{i \in S(u)-\{j\} }{c_{j,i}}},\ donde\ c_{i,j} = card(S_{j,i}(\chi))\]

Usando Weighted Slope One, calcule qué rating le daría U3 a Spiderman*:

  • Desviación promedio entre Spiderman y Batman (en la resta, primero Spiderman)

\[[(4-3)+(4-2)]/2=1,5\]

  • Desviación promedio SpiderMan y Harry Potter (en la resta, primero Spiderman)

\[[(4-5)]/1=-1\]

  • Predicción: Usando el rating que el usuario U3 le dio a Batman y a Harry Potter, calcular rating de U3 a Spiderman
    • Usando Batman (rating the U3 a Batman + desviación)
      \(r=2+1,5=3,5\)
    • Usando Harry Potter (rating the U3 a Harry Potter + desviación)
      \(r=4-1=3\)
    • Considerando ambas predicciones y la cantidad de muestras usadas en cada uno
      \((3,5*2 + 3*1)/(2+1)=3,33\)

Herramientas para tarea 1

  • MyMediaLite
  • Lenskit
  • LibRec
  • Debido a que usarán herramientas, considerar leer Said, A., & Bellogín, A. (2014, October). Comparative recommender system evaluation: benchmarking recommendation frameworks. In Proceedings of the 8th ACM Conference on Recommender systems (pp. 129-136). ACM.

Referencias