Embed Size (px)
DESCRIPTION
Examen de Título: Implementación de un sistema de recomendación con PSO (Particle swarm optimization).
Citation preview
Implementación de un sistema de recomendaciones con PSO
Ignacio Salas DonosoProfesora Guía: María Cristina RiffProfesora Co-referente: Elizabeth Montero
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D. 1
2
Contenido•Pr
oblema: Paradoja de la Elección
•Sistema de Recomendación Basado en PSO
•Experimentos y Resultados
•Conclusiones
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
3
Problema: Paradoja de la elección
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Necesito fideos :(
4
Problema: Paradoja de la elección
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Muchas opciones para una misma necesidad
Elecciones más complejas al aumentar costos
Las experiencias y expectativas definen la elección
5Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Paradoja de la elección
Teoría de la Perspectiva
6Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Paradoja de la elección
El Maximizador
Busca y acepta sólo lo mejor
Tienden a estar menos satisfechos con las elecciones que toman
“El remordimiento del comprador”
7
Comercio Electrónico
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
El cliente dispone de más información
El costo de captación es muy elevado
Lealtad a la marca
Es en donde más se nota “La paradoja de la elección”
8
Sistema de Recomendación Basado en PSO
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Tipos de Sistemas de Recomendación
Basado en Filtrado Colaborativo
Basado en Contenido Minería de Datos Social
Ítem
9Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en Filtrado Colaborativo
Se buscan personas con intereses similares al usuario objetivo
Serendipia
Sistema de Recomendación Basado en PSO
10Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en Filtrado Colaborativo
Sistema de Recomendación Basado en PSO
Problemas
Alto esparcimiento de los datos
El problema del primer voto
Malos resultados cuando no hay un vecindario
11Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
¿Qué se quiere lograr?
Sistema de Recomendación Basado en PSO
Mejorar la calidad de la recomendación
Enriqueciendo la información personal del usuario
Se busca tener buenos resultados, aún cuando no haya
una vecindad adecuada
El componente clave, es la función de estimación del voto
12Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en PSO
Función de estimación del voto de Breese
Experiencia personal del
UsuarioExperiencia de la VecindadVoto
estimado
Correlación de Pearson
13Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en PSO
Nueva función de estimación del voto
Experiencia personal del
Usuario
Se enriquece la experiencia del usuario
Lograr capturar la diversidad de apreciaciones del usuario
Ofrecer un soporte cuando no haya una vecindad adecuada
14Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en PSO
Nueva función de estimación del voto
Experiencia personal del
Usuario
Dar diferentes importancias a la experiencia personal y grupal
Experiencia de la VecindadVS
Reconocer qué información influye más para cada usuario
Acotar la diversidad para cada usuario
15Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en PSO
Nueva función de estimación del voto
Desviación Estándar de los votos del
Usuario
Experiencia de la Vecindad
Promedio de votos del usuario
Experiencia personal del Usuario
Voto estimado
Se puede ver como un problema de
optimización
16Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en PSO
PSO: Optimización por Enjambre de Partículas
Posición
Velocidad
Mejor Posición Grupal
Mejor Posición Personal
Requiere de pocos parámetros
Se puede implementar en poco tiempo
Puede manejar varias soluciones a la vez
17Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en PSO
PSO: Representación
Posición
Mientras no se alcance la cantidad de iteraciones
Para cada partícula
Actualizar posición y velocidad
Calcular pBest
Calcular gBest partícula
PSO: Algoritmo
18
Dinámica de partículas de Algoritmo PSO
Velocidad Nueva
Velocidad Actual
Experiencia personal
Experiencia grupal
Posición Nueva
Velocidad Nueva
Posición Actual
Sistema de Recomendación Basado en PSO
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Vector de 2 dimensiones, que contiene los valores de
k0 y k1
19
Dinámica de partículas
Experiencia personal
Experiencia grupal
Ítems evaluados por el usuario objetivo
Grupo de Entrenamiento
Grupo de Validación
Grupo de Prueba
Sistema de Recomendación Basado en PSO
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
20
Fitness
Fitness parcial Voto real Voto
estimado
Fitness Fitness parcial
Cantidad de ítems
Sistema de Recomendación Basado en PSO
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
El óptimo es 0
21
Para cada usuario
Mientras no se alcance la cantidad de iteraciones
Para cada partícula
Actualizar posición y velocidad
Calcular pBest
Calcular gBest partícula
Almacenar factores k0 y k1 para el usuario, obtenidos del gBest
Sistema de Recomendación Basado en PSO
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Algoritmo PSO
22
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Book Crossing
278.858 usuarios
271.379 libros
1.149.780 votos de 77.837 usuarios
ID U1 ISBN•Voto 1
…ISBN•Voto n
… … … …
ID Um ISBN•Voto 1
…ISBN•Voto n
Casos de Prueba
23
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Experimento 1: Prueba de GeneralizaciónExperimento 2: Contraste entre
resultados de la función de Breese y la propuesta
Grupo 1: Usuarios que han evaluado más de 300 ítems
Grupo 2: Usuarios que han evaluado entre 100 y 200 ítems
Grupo 3: Usuarios que han evaluado entre 50 y 150 ítems
Cada grupo tiene 50 usuarios elegidos al azar
24
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Grupo 1 Grupo 2 Grupo 30
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Promedios de Fitness de los Usuarios de cada Grupo en el Ex-
perimento 1
Grupo de Entre-namiento
Grupo de Validación
Grupo de Prueba
Prom
edio
de
Fitn
ess
Grupo 1 Grupo 2 Grupo 30
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Promedios de Fitness de los Usua-rios de cada Grupo en el Experi-
mento 2
Función de (Breese et al. 1998)
Función de esta Memoria
Prom
edio
de
Fitn
ess
Diferencias medias entre el voto real y el estimado
25
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Comparación de cantidad de usuarios para k0 y k1
43%57%
Grupo 1K0 > K1 K0 < K1
42%
58%
Grupo 2K0 > K1 K0 < K1
44%56%
Grupo 3K0 > K1 K0 < K1
Se observa una mayor importancia de la experiencia grupal, pero la personal no lo es
menos
26
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25-1
-0.5
0
0.5
1
1.5
2
Factores k0 y k1 de 25 usuarios del grupo 3
K0 K1
27
Conclusiones
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Rendimiento de PSO
1 2 30
20
40
60
80
100
120
140
Tiempo de Ejecución Tiempo de Eje-cución
Grupo
Min
utos
Pudo encontrar buenas combinaciones de k0 y k1, para cada usuario
En el grupo 1 se obtuvieron los mejores resultados
Se pudieron encontrar soluciones cercanas al óptimo, desde 15 minutos para 50 usuariosGrupo no homogéneo
Procesador: AMD Turion II P520 Dual-Core 2.30GHzMemoria RAM: 3 GBTipo de Sistema Operativo: Windows 7 Home Premium, 64 bits
28
Conclusiones
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
El modelo resultante, logró aprovechar mejor la información
La desviación estándar mostró ser relevante para mejorar la calidad de la recomendación
Los factores k0 y k1 pudieron capturar las prioridades de cada usuario y mejorar los resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Implementación de un sistema de recomendaciones con PSO
29
Ignacio Salas DonosoProfesora Guía: María Cristina RiffProfesora Co-referente: Elizabeth Montero
30
? Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
31
Diapositivas Extra
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
32
Fitness parcial Voto real Voto
estimado
Fitness Fitness parcial
Cantidad de ítems
Especificación de cómo se calculó pBest y gBest
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Grupo de Entrenamiento Grupo de Validación
pBest gBest
33
Coeficiente de Correlación de Pearson
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Voto del usuario a por
el ítem iVoto
promedio del usuario a
34
Sistemas de Recomendación Basados en Filtrado Colaborativo
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
1. Asignar un peso a todos los usuarios con respecto a la similitud con el usuario activo.
0.1
0.7
0.7
1.0
0.1
0.9
0.2
2. Seleccionar los k usuarios más parecidos al usuario activo
3. Calcular una predicción desde una combinación ponderada de los puntajes de la vecindad
0.8
0.8 0.9 1.0
35
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Grupo 1 Grupo 2 Grupo 30
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Promedios de Fitness de los Usuarios de cada Grupo en el Ex-perimento 1
Grupo de En-trenamiento
Grupo de Validación
Grupo de Prueba
Prom
edio
de
Fitn
ess
36
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Grupo 1 Grupo 2 Grupo 30
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Promedios de Fitness de los Usuarios de cada Grupo en el Ex-perimento 2
Función de (Breese et al. 1998)
Función de esta Memoria
Prom
edio
de
Fitn
ess
37
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50-1
-0.5
0
0.5
1
1.5
2
2.5
3
3.5
4Valores de K0 y K1 Grupo 1
K0 K1
Usuarios
38
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
1 2 3 4 5 6 7 8 9 1011121314151617181920212223242526272829303132333435363738394041424344454647484950-1
0
1
2
3
4
5
Valores de K0 y K1 Grupo 2
K0 K1
Usuarios
39
Experimentos y Resultados
Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
1 2 3 4 5 6 7 8 9 1011121314151617181920212223242526272829303132333435363738394041424344454647484950-1
-0.5
0
0.5
1
1.5
2
Valores de K0 y K1 para el Grupo 3
K0 K1
Usuarios
40Implementación de un sistema de recomendaciones con PSO -- Ignacio Salas D.
Sistema de Recomendación Basado en PSO
PSO: Optimización por Enjambre de Partículas
Posición
Velocidad
Fuente : http://www.yunphoto.net/es/photobase/yp1328.html
Partícula
Posición
Velocidad
Mejor Posición Personal (pBest)
Mejor Posición Global (gBest)
