Sistemas de Recomendação - Parte 2

View
165
Download
1
Category

Data & Analytics

Preview:

Citation preview

Sistemas de Recomendação: uma visão geral (Parte 2)

Ralph J. R. Filho

Tópicos

Parte I● Conceitos básicos● Exemplos usando MovieLens

Parte II● Algoritmos● Aplicações na Indústria● Pesquisa● Considerações Finais

Parte IIIII. Algoritmos

/ralphrass/recsysQuick and dirty

COMO FAZER?Filtro colaborativo usuário-usuário

Implementação

• Montar matriz de avaliações (Usuário x Item)• Calcular similaridades• Montar matriz de correlações

• Prever notas

• Ordenar as previsões • Mostrar os resultados

Correlação

Toy Story Shawshank Redemption

Shindler’s list

Silence of the Lambs

Ana 4.5 5 4.5 4

Bruno 4 5 5 4.5

Similaridade: 0.426

Correlação

Toy Story Shawshank Redemption

Shindler’s list

Silence of the Lambs

Filme Raro X

Ana 4.5 5 4.5 4 4

Bruno 4 5 5 4.5 1

Similaridade: 0.607

Toy Story Shawshank Redemption

Shindler’s list

Silence of the Lambs

Filme Raro X

Ana 4.5 5 4.5 4 4

Bruno 4 5 5 4.5 1

Correlação

Similaridade: 0.607

Correlação

• Simples e eficiente

• Ganha de várias outras medidas de similaridades para o filtro colaborativo entre usuários [Herlocker et al. 1999]

• Desconsidera popularidade dos itens (boa ou ruim)

• Predições saem da escala de avaliação (1-5 pode produzir predições de 6 ou até 7)

• Usuários que concordam em poucos, mas importantes, itens podem ter uma baixa correlação

Filtro Colaborativo

•k-NN

• k entre 20 e 50 (Herlocker et al. 2002)

• k entre 20 e 30 (Coursera MOOC)

Filtro Colaborativo

• Entre itens (Amazon)

• Pode ser calculado off-line porque as notas dos itens tendem a ser mais estáveis que as dos usuários (Sarwar B. et al. 2001)

• Indicado utilizar similaridade cosseno (Sarwar B. et al. 2001)

COMO FAZER?Filtro colaborativo entre itens

Implementação

• Montar matriz de avaliações (Item x Usuário)• Montar matriz de correlações (cosseno ajustado –

média do usuário)

• Prever avaliações para cada item para cada usuário com base na similaridade entre itens que o usuário avaliou

• Ordenar as previsões e apresentar as recomendações

Filtro Colaborativo

• Quando escolher I-I ou U-U?

Filtro Colaborativo

• Quando escolher I-I ou U-U?• p = max de avaliações por usuário• q = max de avaliações por item• k = max de vizinhos

Ricci, F. et al. (eds.), Recommender Systems Handbook pg. 120

Filtro Colaborativo

• DataSet MovieLens:• ≈ 700 users• ≈ 10,000 movies• ≈ 100,000 ratings

Ricci, F. et al. (eds.), Recommender Systems Handbook pg. 120

Filtro Colaborativo

• Quando escolher I-I ou U-U?

• Preferências dos itens tendem a ser mais estáveis do que as preferências dos usuários

• Avaliar nro de itens versus usuários

• U-U favorece serendipidade (Ekstrand et al. 2011)

• Ressaltando, filtro colaborativo utiliza unicamente as avaliações, ignorando completamente os atributos

Filtro Colaborativo

• Para o filtro baseado em conteúdo, a abordagem mais utilizada é a similaridade cosseno.

• É claro, pode ter várias dimensões

https://kallistec.wordpress.com/tag/k-nearest-neighbors/

COMO FAZER?Filtro baseado em conteúdo

Implementação ingênua

• Definir vetor de palavras-chave• Construir perfil dos itens (vetor binário assimétrico)

• temFeatureX = 1• Construir perfil dos usuários (contagem simples)

• (rating > limiar) ? +1

• (rating < limiar) ? -1

• senão, 0• Calcular dot-product entre os perfis de itens e usuários• Ordenar e mostrar os resultados

Sistemas de Recomendação

• Desafios

• 0-1 ou contagem

• Feedback implícito

• Preferência versus importância de palavra-chave

• Como normalizar os vetores?

• Como atribuir pesos?

• Melhores formas de atualizar os vetores (on-line)?

Sistemas de Recomendação

• Como extrair atributos qualitativos (contexto)?• Se eu avaliar bem um filme de comédia, não quer dizer que o

gênero apenas seja representativo o suficiente para a minha preferência

• Tags tentam capturar isto

• “Genres, actors, director are not the content of a movie. It is knowledge about it” Recommender Systems – An Introduction

• Fatoração matricial (filtro colaborativo)

Sistemas de Recomendação

• Combinação de dois ou mais algoritmos

http://dataconomy.com/an-introduction-to-recommendation-engines/

Sistemas de Recomendação

Burke, R., 2002 - Hybrid Recommender Systems: Survey and Experiments

Técnica Vantagens Desvantagens

Filtro Colaborativo A. Pode identificar nichosB. Conhecimento de domínio

não é necessárioC. Feedback implícito é

suficienteD. A qualidade melhora com o

tempo

E. Cold-start para usuário F. Cold-start para itemG. Problema da ovelha-

negraH. Qualidade depende do

históricoI. Problema da

estabilidade VS Plasticidade

Baseado em conteúdo

B, C, D E, H, I

Sistemas de Recomendação

Burke, R., 2002 - Hybrid Recommender Systems: Survey and Experiments

Método Descrição

Pesos Combinar os escores de diferentes técnicas de recomendação para produzir uma única recomendação

Switching Muda o algoritmo dependendo da situação

Misto Mistura as recomendações geradas por diferentes técnicas

Combinação de características

Características de diferentes técnicas de recomendação são unidas em um único algoritmo

Cascata Um algoritmo filtra as recomendações gerada por outo

Ampliação de características

A saída de uma técnica é usada como entrada de outra

Meta-nível O modelo aprendido por uma técnica é usado como entrada para outra

Sistemas de Recomendação

•Avaliação

• Esparcidade

• MAE / NMAE, RMSE

• Precision, Recall e Medida-F

• Rank

• Cobertura

Avaliação

• R = avaliações, I = Itens, U = Usuários

• MovieLens 100k current DataSet tem esparcidade = 0,978 (2,2%)

Avaliação

• U = Usuários• testsetu = Conjunto de itens que o usuário u avaliou

• rec(u, i) = avaliação prevista para o usuário u no item i• ru,i é a avaliação real do usuário u para o item i

• MovieLens MAE = 0.83

Avaliação

• Precision (relevância) (Pu), Recall (entre os top) (Ru) e Medida-F (F1)

• hitsu é o número de recomendações relevantes presentes no top-n

• recsetu é o valor de top-n

• testsetu é o total de recomendações relevantes

http://aimotion.blogspot.com.br/2011/05/evaluating-recommender-systems.html

Avaliação

• Usuário “Alice”

Filme Avaliação (0.5 – 5.0)

Toy Story 5.0

Alien 2.0

Titanic 4.5

Indiana Jones and the Raiders… 3.0

Pirates of the Caribean and the Curse…

3.5

Avaliação

Filme Recomendado Previsão

Toy Story 4,89

Matrix 4,78

Inception 4,32

Titanic 4,18

Band of Brothers 3,99

Precisão: 1/3Recall: 1/2

Recomendações, Top-3

Avaliação

Filme Recomendado Previsão

Iron Man 4,95

Mulan 4,77

Prometheus 4,71

Alien 4,63

Terminator 2 4,61

Predator 4,59

The Expandables 4,50

First Blood 4,42

Precision: ?Recall: ?

Recomendações, Top-5

Usuário assistiu e gostou (top)

Usuário assistiu e gostou

Avaliação

Filme Recomendado Previsão

Iron Man 4,95

Mulan 4,77

Prometheus 4,71

Alien 4,63

Terminator 2 4,61

Predator 4,59

The Expandables 4,50

First Blood 4,42

Precision: 2/5Recall: 2/4

Recomendações, Top-5

Usuário assistiu e gostou (top)

Usuário assistiu e gostou

Avaliação

• Qualidade do ranking

Avaliação

• Usuário “234” com 20 itens na lista de recomendação e hits nas posições 04 e 20

• Pode-se notar que um item posicionado acima no ranking tem um peso maior

Avaliação

• Cobertura de Usuários (Ucov), Cobertura de Catálogo (Ccov)

• Útil para avaliar usuários com poucas avaliações (listas não-vazias de recomendações são geradas)

• Deve ser usado em conjunto com métricas de erro (MAE)

Avaliação

•Existem outras•Área em aberto para pesquisa•Para Herlocker e McLaughlin (2004) Precision e Recall reflete melhor a experiência do usuário do que MAE

•No entanto, vários experimentos usam MAE / RMSE como medida

•Netflix Prize pedia para reduzir o RMSE em 10%

Avaliação

•Como ranquear?