Conceitos e Práticas em Sistemas de Recomendação
09/04/2014 !
Joel Pinho Lucas
1
Agenda
• Big Data e Sistemas de Recomendação (SR)
• Técnicas utilizadas em SR
• Principais problemas e desafios em SR
• Algoritmos utilizados
• Cases
• Como começar a desenvolver SR?
2
Big Data (Volume) - Sistemas de Recomendação
2/3 dos filmes acessados no Netflix são originados de recomendações (Celma & Lamere - ISMIR 2007)
O volume de informação no mundo ocuparia o equivalente a 295 trilhões de megabytes (University of Southern California - 2011)
3
Big Data (Velocidade) - Sistemas de Recomendação
• Análise de dados:
✓ Processamento em “batch”
✓ Processamento em tempo real
4
Sistemas de Recomendação
• Cenário em E-Commerce:
✓A “explosão da informação” resultou em uma enorme quantidade de itens ao alcance do usuário
✓Dificuldade na escolha para compra de produtos
✓Falta de personalização
✓Email / SPAM
5
Sistemas de Recomendação
• 35% das compras na Amazon.com são originadas por recomendações (Celma & Lamere - ISMIR 2007)
6
“Se tenho 3 milhões de clientes na Web, tenho de ter 3 milhões de lojas on-line” Jeff Bezos, Fundador da amazon.com
Técnicas Utilizadas em SR
✓Métodos baseados em Conteúdo (CB):
!
!
!
✓Filtragem Colaborativa (CF):
‣ Baseada em Usuário
‣ Baseada em Item
7
Técnicas Utilizadas em SR
Figura: Recomendação baseada em Conteúdo (Gmail.com)
8
Técnicas Utilizadas em SR
Figura: Recomendação baseada em Item - Filtragem Colaborativa (Amazon.com,)
9
Técnicas Utilizadas em SR
Figura: Recomendação baseada em Usuário - Filtragem Colaborativa (Netflix.com)10
11
“É complexo definir similaridade, mas…
você sabe quando você a vê.” (Dr. E. Keogh)
• Falsos Positivos x Falsos Negativos
• Implementação própria x Frameworks + tools (ex.: Mahout)
!
• Processamento em “batch" x Tempo Real
12
Problemas e Desafios
Problemas e Desafios
• Dispersão de dados (sparsity): usuários conseguem avaliar (rating) em média1% dos itens disponíveis (Breese, et. al. - 2010)
• Escalabilidade
• Ovelha Negra
• Primeiro Rating (early-rater)
13
Cases
14
Figura: Gameverse (Mobjoy)Figura: MovieLens (GroupLens - University of Minnesota)
Arquitetura Típica para Recomendações
15
Algoritmos de CB - TFIDF
✦ TF: Term Frequency ✦ IDF: Inverse Document Frequency
16
Tabela: documentos representando itens
Algoritmos de CB - TFIDF
17
Figura: Modelo Vetorial [Dr. Edberto Ferneda, Unesp, 2010]
Algoritmos de CF - Conceito Geral
18
a) Matriz User-Item b) User rating document no MongoDB
✦ CF: predizer ratings do usuário ativo para cada produto com base nos ratings de outros usuários
Algoritmos de CF - KNN
19
✦ K-Nearest User Neighborhood (KNN): buscar os K vizinhos mais próximos
• Input: vetores de ratings de usuários
• Output: os k vizinhos mais próximos
• Recomendação: top ratings de k
Algoritmos de CF - Regras de Associação
20
• Encontrar conjuntos de itens (frequent itemsets) que ocorram juntos em um conjunto de dados
• Em SR: se item A e B estão relacionados, então recomendar item B se User1 gostou de item A
Tabela 1: Exemplo de um conjunto de transações
Tabela 2: Possíveis regras a partir de T1
Algoritmos - Scaling out
21
• Implementar Escalabilidade Horizontal
Algoritmos - Scaling out
22
• TFIDF: dividir conjuntos de documentos para realizar o processamentos dos vetores de palavras
!
• KNN e Conjunto de Itens Frequentes: paralelizar o cruzamento de dados utilizando Map-Reduce !
!! !!
Map Input: {[user: U1, items: [P1, P3, P6], user: U2, items: [P1, P9], user: U3, items: [P1, P6, P8]]}
23
Algoritmos - Scaling out
Map Output/Reduce Input: (P1: [P3, P6]; P3: [P1, P6]; P6: [P1, P3]; P1: [P9]; P9: [P1]; P1: [P6, P8]; P6: [P1, P8]; P8: [P1, P6])
Reduce Output: (P1: [P3, P6, P8]; P3: [P1, P6]; P6: [P1, P3, P8]; P8: [P1, P6])
Como Começar?
✓Coursera (http://www.coursera.org):
• Recommender Systems
• Introduction to Data Science
• Machine Learning
✓Amazon EMR Training: http://aws.amazon.com/elasticmapreduce/training/
24
✓Netflix Tech Blog: http://techblog.netflix.com/
✓GroupLens - University of Minnesota, EUA: http://www.grouplens.org/
✓Toby Segaran, Programming Collective Intelligence. O’Reilly, 2007
25
Como Começar?
✓Amazon Public datasets: http://aws.amazon.com/publicdatasets/
✓GroupLens Public Data Sets: http://www.grouplens.org/
✓Weka Machine Learning: http://www.cs.waikato.ac.nz/ml/weka/
26
Como Começar?
27
Como Começar?
Perguntas - Contato
‣ Linkedin: http://br.linkedin.com/in/joelplucas/
!
‣ Email: [email protected]
28