Conceitos e práticas em Sistemas de Recomendação

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: joelpl@gmail.com

28