Filtragem Colaborativa
João Carlos
Jobert Sá
• Introdução;
• Desafios da Filtragem Colaborativa;
• Técnicas
o Model-based;
o Memory-based;
• Casos de estudo;
Introdução
• Quantidade crescente quantidade de informação disponível;
Introdução
• Pessoas confiam em recomendações como forma de
filtragem;
Introdução
• Se usuário X e Y avaliam os itens de forma similar, ou têm
comportamentos semelhantes, então eles devem avaliar ou
agir em outros itens de forma similar;
Introdução
• Em uma base típica de preferências "Itens por Usuário"
temos:
Características e Desafios
•
•
•
•
•
Dispersão dos dados;
Escalabilidade;
Sinonímias;
Problema da "ovelha cinza";
Shilling Attacks;
Dispersão dos dados
•
•
•
•
Matriz Item-Usuário pode ficar extremamente dispersa;
Partida fria;
Cobertura reduzida;
Transitividade com o vizinho;
Escalabilidade
• Algoritmos tradicionais de CF podem sofrer problemas
sérios de escalabilidade;
10 million users
X
1 million items
Sinonímias
Problemas gerados:
• Itens com nomes diferentes, porém significados iguais ou
similares;
• Leva a recomendar itens já adquiridos;
Problema da "ovelha cinza"
• O usuário não se encaixa em nenhum grupo;
• Só é possível fazer recomendações baseadas em conteúdo;
Shilling Attacks
• Usuário propositalmente positiva determinados de forma
para provocar recomendações artificiais;
• Memory-based são menos afetados;
O prêmio para o desafio do Netflix
CF Baseados em Memória
• Usa os dados brutos da matriz de avaliações;
• Encontra os vizinhos mais próximos para fazer as previsões
e recomendações;
Computando as Similaridades
• Correlação de Pearson;
• Similaridade baseada no cálculo do cosseno;
Top-N Recomendações
User-based:
• Encontra os usuários com o padrão mais parecidos;
• Encontra o conjunto de itens avaliados/comprados pelos
usuários encontrados;
• As top-N recomendações serão os itens mais
avaliados/comprados pelo grupo pré-selecionado;
Items-based:
• Encontra os itens C com padrão de compra mais parecidos;
• Remove de C o conjunto U de itens já comprados pelo
usuário;
• Calcula a similaridade entre cada elemento de C com os
elementos de U;
Técnicas de CF Baseados em Memória
Vantagens:
• Fácil implementação;
• Novos dados podem ser adicionados facilmente;
• Não precisa se preocupar com o conteúdo dos itens
recomendados;
• Bem escalável para itens co-avaliados;
Técnicas de CF baseados em memória
Desvantagens:
• Dependente das avaliações dos usuários;
• Perde performance com a dispersão dos dados;
• Não consegue recomendar com poucos itens/usuários;
• Tem escalabilidade limitada;
Técnicas de CF baseados em modelo
• Gera modelos que representam a matriz de avaliações;
• Permite o sistema reconhecer padrões complexos;
• Utiliza protipagem e redução de dimensionalidade;
Técnicas de CF baseados em modelo
Vantagens:
• Lida melhor com dispersão dos dados e escalabilidade;
• Melhora performance de previsão;
• Dá uma justificativa intuitiva para as recomendações;
Técnicas de CF baseados em modelo
Desvantagens:
• Construção do modelo pode ser custosa;
• Possui trade-offs entre performance de previsão e
escalabilidade;
• Perde informações úteis com o uso de técnicas de redução
de dimensionalidade;
Casos de Estudo: Tapestry
• Motivação: Aumento do
uso de correio eletrônico
Casos de Estudo: Tapestry
• Filtragem baseada em conteúdo e Filtragem Colaborativa
• Anotações
• Listas moderadas
o emails filtrados segundo anotações criadas pelos
"moderadores"
o Feedback dos usuários
• Relacionamento entre dois ou mais emails
Casos de Estudo: Tapestry
Fluxo de mensagens
Casos de Estudo: Tapestry
O Sistema é realmente eficiente?
Catherine cria um filtro de consulta a fim de receber
mensagens que Amy, Annie ou Allison consideraram
engraçadas.
Priority Inbox
Casos de Estudo:
Algoritmos de recomendação para e-commerce encontram
ambientes desafiadores:
• Uma grande loja pode ter enormes quantidades de dados
• Resultados em tempo real, ao mesmo tempo em que gera
boas recomendações
• Novos clientes tem informações extremamente limitadas
• Clientes mais velhos tem excesso de informações
• Dados dos clientes são voláteis
Item-to-Item Collaborative Filtering
Casos de Estudo:
Algoritmo da amazon.com X outros métodos
• Filtragem Colaborativa Tradicional
o Cliente = vetor de itens N-dimensional
o Componentes do vetor podem ser positivos ou negativos
o
Computacionalmente muito caro: O(MN), O(M+N)
Casos de Estudo:
Algoritmo da amazon.com X outros métodos
• Modelos de Clusters
o Divide o banco de clientes em vários segmentos
o Problema de classificação
 Agrupar clientes mais similares para formar clusters
o Melhor performance do que o método anterior
o Recomendações menos relevantes
 Melhorar as recomendações aumentando a
granularidade dos segmentos o torna quase tão caro
quanto Filtragem Colaborativa
Casos de Estudo:
Algoritmo da amazon.com X outros métodos
• Métodos baseados em conteúdo (ou busca)
o Tratam o problema de recomendação como uma busca
o Recomenda itens com atributos similares
o Boa performance e escalabilidade se o usuário fez
poucas compras e classificações
o Baixa qualidade nas recomendações para usuários que
fizeram poucas compras
Casos de Estudo:
Algoritmo da amazon.com X outros métodos
• Filtragem Colaborativa Item-a-Item
o Combina cada item comprado e classificado pelo usuário
com itens similares
o Tabela de itens comprados em conjunto
Casos de Estudo:
Algoritmo da amazon.com X outros métodos
• Filtragem Colaborativa Item-a-Item
o Similaridade é calculada pela fórmula do cosseno
 Item = Vetor de consumidores M-dimensional
o Cálculo de similaridade e construção da tabela é offline
o O(N²M) no pior caso. Aproximadamente O(NM)
o Dada uma tabela de itens similares, o algoritmo agrupa
os itens similares ao item que o usuário está comprando.
E então recomenda os itens mais populares ou
correlacionados
o Geração das recomendações é rápida, dependendo do
número de itens que o usuário comprou ou classificou
Casos de Estudo:
Resumo comparativo:
• Filtragem colaborativa tradicional: computação online
aumenta de acordo com o número de clientes e itens
o Bons resultados para bancos de dados pequenos
o Baixa qualidade em grandes bancos de dados, pois é
preciso utilizar um subconjunto de dados
• Modelos de clusters: Maior parte da computação offline,
mas qualidade da recomendação é baixa. Aumentar o
número de clusters torna mais caro
• Modelos baseados em conteúdo: Falham em fornecer
recomendações relevantes e não são bem escaláveis para
clientes com muitas compras ou classificações
Casos de Estudo:
Resumo comparativo:
• Filtragem Colaborativa Item-a-Item
o Parte computacional mais cara (tabela de similaridade) é
feita offline
o A parte online possui um algoritmo que é escalável
independente do tamanho do catálogo de itens ou
número de clientes
o Depende somente da quantidade de itens que o usuário
comprou ou classificou
o Rápido, mesmo para grandes conjuntos de dados
o Boa qualidade das recomendações, mesmo com
informações limitadas
Referências
• A Survey of Collaborative Filtering Techniques (Su e
Khoshgoftar - 2009)
• Using Collaborative Filtering to weave an information
Tapestry (Goldberg - 1992)
• From Tapestry to SVD: A Survey of the Algorithms That
Power Recommender Systems (Huttner - 2009)
• Amazon Recommendations: Item-to-Item Collaborative
Filtering (Linden, Smith, York - 2003)
Dúvidas?