Sistemas de
Recomendação
AULA 17
DATA MINING
Sandra de Amo
Esquema Geral






Aula 1:
 Introdução:
 Filtragem Colaborativa versus Baseados em Conteúdo
 Sistemas baseados em conteúdo
Aula 2:
 Sistemas baseados em filtragem colaborativa
Aula 3:
 Um sistema Hibrido: PrefRec
 Fatores latentes
Aula 4:
 Sistemas baseados em filtragem colaborativa híbridos: vizinhança e
fatores latentes
Aula 5:
 Sistemas de Recomendação Sociais: introdução, conceitos sobre redes
complexas
Aula 6:
 Um exemplo de Sistema de Recomendação Social
Referências

Anand Rajaraman, Jure Leskovec, Jeffrey D. Ullman - Mining
Massive Datasets, Cambridge University Press, 2012. – Capitulo 9

Yehuda Koren: Matrix Factorization Techniques for Recommender
Systems – 2009

Yehuda Koren: Factorization meets the neighborhood: A
multifaceted collaborative filtering model – KDD 2008
O que é um Sistema de
Recomendação ?
DADOS DE TREINAMENTO
gostei
não gostei
Odiei
Gostei muito
USUÁRIOS
ITEMS
USUÁRIOS AVALIAM ITEMS
O que é um Sistema de
Recomendação ?
DADOS DE
TREINAMENTO
MODELO DE
RECOMENDAÇÃO M
Algoritmo de
Aprendizagem
+
Uma sequência de items
<I1,I2,…,IK> que u ainda
não avaliou e que lhe serão
recomendados
Usuário ativo u
e algumas de
suas
avaliações
Principais Desafios

Esparsidade dos dados de treinamento (sparsity) :



Cold-start de usuário


alguns usuários avaliam poucos items
alguns items são avaliados por poucos usuários.
Dificil recomendar items para um usuário que não avaliou nenhum item.
Cold-start de item

Dificil recomendar items que nunca foram avaliados por nenhum usuário
ainda
O que é um “bom” Sistema de
Recomendação






Tem boa acurácia: Recomenda items que são do agrado
do novo usário
Recomendação é um processo rápido executado online.
Recomenda items que “surpreendem” o usuário
Recomenda items que não são populares.
Consegue recomendar items e agradar o usuário sem
exigir um grande número de avaliações prévias do novo
usuário.
Consegue recomendar novos items que ainda não foram
avaliados por nenhum usuário.
Aplicações de SR


Recomendações de produtos:
 Livros (Amazon, Liv. Cultura, etc)
 Música (Itunes)
Recomendações de filmes
 Netflix
 Concurso Netflix em 2006: 1 milhão de dólares para o primeiro
algoritmo que superasse em 10% a acurácia de seu SR
(Cinematch)



Prêmio vencido em 2009 pelo grupo de pesquisadores “Bellkor’s
Pragmatic Chaos” – 3 anos de trabalho.
Algoritmo vencedor nunca foi utilizado: baixissima escalabilidade.
Recomendações de artigos de notícias ou outro conteúdo
 New York Times
 Blogs
 You Tube
Um modelo simples de SR
Dados de entrada (treinamento) :




Duas entidades principais: usuários e items
Relacionamento: Preferências (notas)
Matriz de utilidade (MU) : usuários versus items
HP1
A
4
B
5
HP2
HP3 TW
5
5
C
3
ITEMS (FILMES)
1
4
4
D
SW1 SW2 SW3
2
2
3
USUARIOS
Característica da MU: muito esparsa
Ex. : filmes SW2, SW3, HP3 foram avaliados por somente 1 usuário
Um modelo simples de SR

Objetivo:





predizer os lugares vagos na MU
Ex: Qual seria a nota que o usuário C daria para o
filme HP1 ?
Predizer notas é dificil. SR que predizem notas
normalmente não têm boa acurácia.
Não é necessário predizer todos os lugares vagos
(notas), mas sim, fornecer um ranking de alguns
items que seriam recomendados para o usuário.
Para fornecer um ranking, não é necessário predizer
uma nota exata para os items.
Como predizer as notas que seriam dadas
por A para o filme SW2 ?

Examinando filmes parecidos com SW2 a partir de seus conteúdos:
diretor, gênero,...



Examinando filmes que tiveram avaliações parecidas com as de
SW2




SW2 é parecido com SW1.
A não gostou de SW1, logo podemos concluir que A não gostaria de SW2.
Por exemplo: C avaliou SW1 e SW2 e gostou de ambos
Assim, infere-se que os usuários normalmente tem preferências similares por
estes dois filmes
Como A não gostou de SW1 então não gostaria de SW2.
Examinando usuários parecidos com A em termos de gosto:



O usuário C avaliou os mesmos filmes que A avaliou, e ambos deram notas
parecidas para tais filmes.
C não gostou de SW2.
Logo poderíamos concluir que A também não gostaria.
Porque Sistemas de
Recomendação são necessários ?

Lojas fisicas versus lojas virtuais
 Fisicas: Estoque disponivel << estoque real
Virtuais:Estoque disponivel = estoque real

Recomendações no “mundo fisico”: baseada na
popularidade dos items
 Lojas fisicas só podem mostrar os items populares.
 Somente os livros best-sellers são expostos
 Somente notícias que atraem a maioria dos leitores
são divulgadas nos jornais fisicos
Número de avaliações
O Fenômeno da “Cauda
Longa”
Items
Popularidade de um item = Número de avaliações do item
Sistemas de Recomendação são
imprescindíveis no mundo online

Lojas online não tem problemas para disponibilizar tudo o
que têm.

Usuários não tem condições de verificar tudo o que está
disponível

Usuários precisam ter uma idéia se gostariam ou não de
um produto que desconhecem.
Um exemplo típico da utilidade
dos sistemas de recomendação

Livros “Touching the void” e “Into the air” sobre montanhismo
 "Touching the void “ : nada popular quando publicado
 Anos depois, “Into the air” é publicado

Sistema de recomendação da Amazon:
 Notou alguns usuários que compravam os dois livros.
 Começou a recomendar “Touching the Void” a clientes que
compraram “ Into the air”
 Resultado: Popularidade de “ Touching the Void” aumenta –
ultrapassa “ Into the air”

Sem um sistema de recomendação, usuários dificilmente
conheceriam “Touching the Void”
Técnicas

Filtragem Colaborativa
 Clusterização
 Usuários similares são agrupados: itens apreciados por um usuário
similar a mim (cujas avaliações passadas são parecidas com as
minhas) são recomendados para mim.
 Items similares são agrupados: items similares àqueles que eu avaliei
positivamente são recomendados.
 Modelos de Fatores Latentes

Baseada em Conteúdo
 Mineração de Preferências
 Utiliza informações sobre as características dos items para criar um
modelo de recomendação
 Modelos enfrentam bem o desafio do cold-start de item.

Híbrida
 Mescla filtragem colaborativa e técnicas baseadas em conteúdo.
Dados de treinamento:
Como obtê-los ?


Dados de treinamento: = matriz de utilidade
Técnicas para preencher a MU:
 Diretas
 Pedir a um grupo de usuários que avalie items de um conjunto
fixado.
 A maioria dos usuários não gosta de dar notas
 Os dados obtidos desta maneira são tendenciosos: provém de um
tipo preciso de usuário que gosta de avaliar produtos
 Indiretas: fazer inferências sobre preferências a partir de ações
tomadas pelo usuário
 Viu um filme, leu um artigo  gostou !
 Viu informações sobre um livro na Amazon  tem interesse no livro !
 Avaliações são do tipo 1 ou 0.
 Somente o valor 1 tem significado.
 Valor zero = ausência de nota
SISTEMAS BASEADOS EM
CONTEÚDO
Técnicas

Similaridade de perfis: item x usuário





Recomenda-se items cujo perfil é mais próximo do perfil do usuário.
Não se cria um modelo de recomendação
Vantagem: rapidez na recomendação
Desvantagem: acurácia baixa
Classificadores:



Cria-se um modelo de recomendação para cada usuário.
Classes: notas ou “gosta/não-gosta”
Para cada usuário:




Treina-se um classificador onde os dados de treinamento são os items com
suas características e sua classe (com o valor da preferência deste usuário:
gosta/não-gosta)
Recomenda-se items a um usuário utilizando o classificador treinado para
este usuário.
Vantagem: acurácia melhor do que a técnica de similaridade de perfis.
Desvantagem: treinamento para cada usuário pode levar tempo.
Técnica de Similaridade de
Perfis

Perfil do item: atributos importantes dos items são selecionados







Filme: Diretor, Gênero, Ano, Ator principal
Livro: Autor, Pais, Gênero, Ano
Música: Gênero, Compositor, Tipo, Ano
Características : Atributo = Valor
Exemplo: características escolhidas são Ator = X, onde X é o nome de
um ator. Existem infinitas características deste tipo, uma para cada
possivel ator.
Um filme que tem os atores Julia Roberts e Mel Gibson, teria valores 1
para as caracteristicas Ator = Julia Roberts e Ator = Mel Gibson
Perfil do usuário: vetor que sumariza as preferências do usuário
com relação às características dos items.

Exemplo: a coordenada referente à característica Ator = Julia Roberts é 20%
(0.2), significando que 20% dos filmes que o usuário gosta têm a atriz Julia
Roberts
Como representar o perfil do
item


Vetor: coordenadas boleanas, coordenadas numéricas
Exemplo:
 Items = filmes.
 Atributo = ator.
 A = conjunto de todos os atores.
 Seja
 f1: filme com 5 atores A2,A3,A5,A6,A8
 f2: filme com 5 atores A1,A2,A4,A6,A7
 Média de notas de f1 = 3; Média de notas de f2 = 4
 As características escolhidas são 9: Ator = A1, Ator = A2, ..., Ator =
A8 e Média.
 Perfil de f1 = p1 = (0,1,1,0,1,1,0,1,3)
 Perfil de f2 = p2 = (1,1,0,1,0,1,1,0,4)
Como medir a similaridade
entre dois perfis

Medida de similaridade entre os perfis dos items = cosseno(p1,p2) =
p1.p2/ |p1||p2|

Obervação: p1 e p2 têm infinitas coordenadas, mas somente as mostradas no
perfil são distintas de zero para ambos os vetores. As outras coordenadas que não
aparecem não influenciam no cálculo do cosseno.

Cuidado com escala utilizada em coordenadas com valores numéricos (como a
média das notas):







Exemplo: suponha que se utilize um fator de escala ɑ > 0 para a média das notas.
Logo p1 = (0,1,1,0,1,1,0,1,3ɑ) e p2 = (1,1,0,1,0,1,1,0,4ɑ)
Cosseno(p1,p2) = 2 + 12ɑ2 / 25 + 125ɑ2 + 144ɑ4
Se ɑ = 1 : cosseno(p1,p2) = 0.816
Se ɑ = 2 : cosseno(p1,p2) = 0.940
Se ɑ = 1/2 : cosseno(p1,p2) = 0.619
A similaridade entre os vetores depende da escala utilizada para os valores
numéricos.
Como representar o perfil do
usuário ?



Vetor contendo as preferências do usuário
Uma coordenada por característica do produto
Caso em que a MU só contém 1’s ou 0’s



Valor da coordenada = X%
X por cento dos produtos que o usuário gosta tem a característica
representada pela coordenada.
Exemplo (preferência do usuário é binária: gostou/não gostou



Supondo Items = filmes; Atributo = Ator; características escolhidas
Ator = A1, Ator = A2, ..., Ator = A8
Para cada i = 1,...,8, seja xi = porcentagem de filmes contendo o
ator Ai que o usuário u gostou.
Perfil de u = (x1,x2,...,x8)
Como representar o perfil do
usuário ?
Exemplo (preferência do usuário é uma nota de 1 a 5):
 Supondo Items = filmes; Atributo = Ator; características escolhidas Ator =
A1, Ator = A2, ..., Ator = A8
 A média das notas dadas pelo usuário u é 3
 Suponha que dos filmes avaliados por u, 3 deles contém o ator A1, com
notas 5, 4 e 3
 Então o valor da coordenada 1 (referente ao ator A1) no perfil de u é a
média entre 5-3, 4-3 e 3-3 = 1

Exercício: suponha usuário V avaliou 3 filmes com o ator A1, com notas 2,
3 e 5. Qual a componente relativa ao ator A1 para o perfil do usuário A1 ?
Como recomendar items utilizando a
técnica da similaridade de perfis ?


“grau” de preferência de um usuário u sobre um item i =
similaridade entre perfil(u) e perfil(i)
Itens com perfis mais próximos ao perfil(u) serão
recomendados.
Exercício: Proponha outras maneiras de recomendar itens
a um usuário a partir de seus perfis.
Exercício
Exercicio 9.2.1 – Capítulo 9 livro texto
Calcular similaridade entre perfis de items, com
atributos numéricos
Items não convencionais:
documentos, imagens
Documentos podem ser items a serem recomendados: artigos, notícias, blogs,
web pages, ...
Que atributos utilizar para caracterizar um documento ?
 Seja BD = {D1,D2,...,Dn} um banco de dados de documentos.
 Di = conjunto de palavras = {w1,w2, ..., wn} (após eliminação de stop
words)


Stop words = pronomes, conectivos, ... (dizem muito pouco sobre o documento,
estão presentes na maioria dos documentos)
Para cada palavra wi de Dj, calcula-se seu score TF.IDF (Term Frequency
times Inverse Document Frequency)




Tij = fij/max fkj (fij = número de vezes que wi aparece no documento Di)
IDFi = log2(n/ni) onde ni = número de documentos do BD onde wi aparece
O TF.IDF de wi em Di = Tij . IDFi
Um score TF.IDF alto de wi em Di significa que wi aparece muito em Di e pouco
em outros documentos.
Perfil de um documento D

Considera-se as n palavras de D com os mais altos scores TD.IDF.





W_D = {w1,...,wn}
Por exemplo: se D é uma notícia, estas palavras incluiriam os
nomes das pessoas que aparecem na notícia, palavras
descrevendo os eventos que aparecem na notícia, etc
Considera-se W = união dos W_D = conjunto das palavras que têm
alto score TD.IDF em algum documento do BD.
Seja K = tamanho de W.
Perfil(D) = vetor de K coordenadas = (0,1,1,....)


Uma coordenada por palavra de W.
Se a palavra aparece em D, a coordenada = 1 (e zero em caso
contrário)
Perfil de uma imagem I
Imagem = vetores caracteristica (histograma de cores, forma, textura)
Imagem = conjunto de tags = palavras que descrevem a imagem

Por-do-sol em Malibu, Praça da Sé, ...
Exemplo: site del.icio.us pede aos usuários para associar tags para páginas
web
Objetivo inicial de del.icio.us:

novo método de busca de páginas:
1. usuário entra um conjunto de tags,
2. Sistema busca páginas web com perfis similares
Uso de tags para recomendação
1.
Para cada usuário temos um conjunto P de páginas
por onde ele navegou ou que guardou em seu
bookmark.
2.
Recomenda-se páginas cujo perfil é similar ao perfil
das páginas de P.

Exercicio: propor novas maneiras de recomendar
páginas para um usuário, utilizando informações sobre
tags.