ads:
Universidade Federal do Amazonas
Instituto de Ciˆencias Exatas
Departamento de Ciˆencia da Computa¸c˜ao
Programa de P´os-Gradua¸c˜ao em Inform´atica
Avalia¸c˜ao de Sistemas de Recomenda¸c˜ao
Baseados em Filtragem Colaborativa
Sheila da N´obrega Silva
Manaus – Amazonas
Mar¸co de 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Universidade Federal do Amazonas
Departamento de Ciˆencia da Computa¸c˜ao
Autor: Sheila da N´obrega Silva
Orientador: Prof. Dr. Edleno Silva de Moura
Disserta¸c˜ao de Mestrado apresentada ao Pro-
grama de P´os-Gradua¸c˜ao em Inform´atica do De-
partamento de Ciˆencia da Computa¸c˜ao da UFAM,
como parte dos requisitos necess´arios para a ob-
ten¸c˜ao do t´ıtulo de Mestre em Inform´atica.
´
Area
de concentra¸c˜ao: Recupera¸c˜ao de Informa¸c˜ao.
Banca Examinadora
Edleno Silva de Moura, Dr. . . . . . . . . . . . . . . . . UFAM/PPGI
Jo˜ao Marcos Bastos Cavalcanti, Dr. . . . . . . . . UFAM/PPGI
Wagner Meira Jr., PhD. . . . . . . . . . . . . . . . . . . . . . . . . . . UFMG
Manaus, AM
Mar¸co/2007
ads:
Resumo
Os Sistemas de Recomenda¸c˜ao surgiram para facilitar a vida do cliente, ajudando-
o a encontrar itens que seriam do seu interesse diante de uma vasta variedade
de produtos dispon´ıveis. V´arios algoritmos de recomenda¸c˜ao tˆem sido propostos
[2, 4, 6, 9, 17, 22] na literatura. Avaliar a qualidade deste algoritmos n˜ao ´e uma
tarefa simples [15, 13].
A maioria dos experimentos encontrados na literatura foram avaliados exclu-
sivamente com base em logs, principalmente pela praticidade de avaliar m´ultiplas
t´ecnicas simultaneamente [22, 18, 6]. Alguns autores questionam se este tipo de
avalia¸c˜ao ´e ou n˜ao confi´avel, considerando que as avalia¸c˜oes com pessoas conseguem
captar melhor a rea¸c˜ao `a recomenda¸c˜ao e que um sistema com alta acur´acia pode
em algumas situa¸c˜oes levar a resultados errˆoneos [13, 23, 15].
Nesta disserta¸c˜ao ´e apresentado um estudo de como os Sistemas de Recomenda¸c˜ao
Colaborativos s˜ao avaliados e ´e proposta uma forma de validar as avalia¸c˜oes basea-
das em logs tornando o uso do log mais confi´avel. Para realiza¸c˜ao desta valida¸c˜ao
´e executada al´em da avalia¸c˜ao baseada em logs, uma avalia¸c˜ao inicial com pessoas.
A id´eia ´e comparar os resultados das duas avalia¸c˜oes, identificar e filtrar poss´ıveis
ru´ıdos que possam ser os respons´aveis pela distˆancia entre o resultado da avalia¸c˜ao
baseada em logs e da avalia¸c˜ao com pessoas. O objetivo principal ´e que ap´os o fim
do processo, a base de logs possa ser utilizada como uma cole¸c˜ao de referˆencia mais
segura em novos experimentos.
iii
Sum´ario
Resumo iii
Lista de Figuras vii
Lista de Tabelas viii
1 Introdu¸c˜ao 1
1.1 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 M´etodos de Avalia¸c˜ao de Sistemas de Recomenda¸c˜ao . . . . . 3
1.2.2 Avalia¸c˜ao de experimentos . . . . . . . . . . . . . . . . . . . . 5
1.3 Nota¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Conceitos B´asicos 8
2.1 Sistemas de Recomenda¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Processo de Recomenda¸c˜ao . . . . . . . . . . . . . . . . . . . . 8
2.1.2 Classifica¸c˜ao do Problema da Recomenda¸c˜ao . . . . . . . . . . 11
2.2 M´etodos de Recomenda¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Baseada em Minera¸c˜ao de Regras de Associa¸c˜ao . . . . . . . . 12
2.2.2 Baseada em conte´udo . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Baseada em Filtragem Colaborativa . . . . . . . . . . . . . . . 14
2.2.4 Abordagens h´ıbridas . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Sistemas de Recomenda¸c˜ao Colaborativos . . . . . . . . . . . . . . . 16
2.3.1 Sistema de Recomenda¸c˜ao Colaborativo Baseado em usu´ario . 16
2.3.2 Sistema de Recomenda¸c˜ao Colaborativo Baseado em Item . . 17
2.4 M´etodos de Avalia¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Avalia¸c˜ao baseada em logs . . . . . . . . . . . . . . . . . . . . 18
iv
SUM
´
ARIO v
2.4.2 Avalia¸c˜ao com pessoas . . . . . . . . . . . . . . . . . . . . . . 19
2.5 M´etricas de Acur´acia . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.1 MAE (Mean Absolute Error) . . . . . . . . . . . . . . . . . . 20
2.5.2 Hits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.3 HR (Hit rate) . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.4 ARHR (average reciprocal hit-rank) . . . . . . . . . . . . . . . 21
2.5.5 Precis˜ao e Revoca¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . 22
3 Valida¸c˜ao de Avalia¸c˜oes Baseadas em Log 24
3.1 Gera¸c˜ao das Recomenda¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Compara¸c˜ao de Avalia¸c˜oes com Pessoas e Baseada em Logs . . . . . . 26
3.3 Identifica¸c˜ao de ru´ıdos no log . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Filtragem do Log . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Estudo de Caso 30
4.1 Implementa¸c˜ao do Sistema de Recomenda¸c˜ao . . . . . . . . . . . . . . 31
4.1.1 Algoritmo de Recomenda¸c˜ao top-N Baseado em Item . . . . . 31
4.2 Log de transa¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Gera¸c˜ao das Recomenda¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Avalia¸c˜oes do Sistema de Recomenda¸c˜ao . . . . . . . . . . . . . . . . 38
4.4.1 Avalia¸c˜ao baseada em logs . . . . . . . . . . . . . . . . . . . . 39
4.4.2 Avalia¸c˜ao com pessoas . . . . . . . . . . . . . . . . . . . . . . 39
4.5 Identifica¸c˜ao de Ru´ıdos e filtragem do log . . . . . . . . . . . . . . . . 42
4.5.1 Filtro dos populares do top-N . . . . . . . . . . . . . . . . . . 42
4.5.2 Filtro dos populares da base de treino . . . . . . . . . . . . . . 43
4.6 Compara¸c˜ao das avalia¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . 44
4.7 Alguns Resultados da Aplica¸c˜ao . . . . . . . . . . . . . . . . . . . . . 46
4.7.1 Recomenda¸c˜ao N˜ao-Personalizada . . . . . . . . . . . . . . . . 48
4.7.2 Produtos n˜ao-similares . . . . . . . . . . . . . . . . . . . . . . 48
5 Conclus˜oes e Trabalhos Futuros 52
5.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Referˆencias Bibliogr´aficas 53
Lista de Figuras
2.1 Exemplo de recomenda¸c˜ao do tipo n˜ao-personalizada . . . . . . . . . 10
2.2 Exemplo de recomenda¸c˜ao do tipo personalizada . . . . . . . . . . . . 11
4.1 Avalia¸c˜ao baseada em Log: ARHR - forma¸c˜ao da base de teste M1 . 39
4.2 ARHR - Avalia¸c˜ao com Pessoas . . . . . . . . . . . . . . . . . . . . . 41
4.3 Resultado da avalia¸c˜ao baseada em log: ARHR - filtro dos populares
do top-N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4 Resultado da avalia¸c˜ao baseada em log: ARHR - base treino com
filtro dos populares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Resultado da avalia¸c˜ao com pessoas: ARHR - base treino com filtro
dos populares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.6 Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Marca . . . . . . . . . . 49
4.7 Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Cor . . . . . . . . . . . 49
4.8 Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Dimens˜ao . . . . . . . . 49
4.9 Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Compatibilidade . . . . 49
4.10 Gr´afico de acur´acia X satisfa¸c˜ao por categoria de produtos recomen-
dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
vi
Lista de Tabelas
4.1 C´alculo da fun¸c˜ao de utilidade u(A,B ) . . . . . . . . . . . . . . . . . 34
4.2 Caracter´ısticas das bases de teste obtidas com as forma¸c˜oes M1, M2,
M3 e M4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Avalia¸c˜ao baseada em log: Hit rate calculado em bases de teste dife-
rentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4 Resultado do Hits, HR, ARHR e Cobertura de clientes utilizando as
forma¸c˜oes de base de teste M1 e M2 . . . . . . . . . . . . . . . . . . . 38
4.5 Resultado da avalia¸c˜ao com Pessoas: Hits, HR e ARHR . . . . . . . . 41
4.6 Resultado das avalia¸c˜oes baseadas em logs e pessoas . . . . . . . . . . 42
4.7 Identifi¸cao dos ru´ıdos . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.8 Avalia¸c˜ao Baseada em Log:Hits, HR, ARHR e Cobertura de clientes
- Base Treino com Filtro dos Populares . . . . . . . . . . . . . . . . . 44
4.9 Avalia¸c˜ao com pessoas:Hits, HR e ARHR - Base Treino com Filtro
dos Populares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.10 Filtro dos populares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.11 C´alculo da distˆancia de Kendall . . . . . . . . . . . . . . . . . . . . . 47
vii
Cap´ıtulo 1
Introdu¸c˜ao
1.1 Motiva¸c˜ao
Os com´ercios varejistas possuem como caracter´ıstica o grande volume de clientes
e tamb´em a oferta de uma elevada variedade de produtos. Empresas como subma-
rino.com, por exemplo, possuem milhares de produtos dispon´ıveis para venda, isso
tamb´em ´e verdade em lojas varejistas convencionais.
Para os clientes, a defini¸c˜ao do produto a ser comprado ´e um problema muitas ve-
zes resolvido atrav´es de conversas com amigos e solicita¸c˜oes de recomenda¸c˜oes sobre,
por exemplo, que m´aquina digital comprar diante de tantos modelos dispon´ıveis, ou
ainda atrav´es de recomenda¸c˜oes de novos produtos que pessoas parecidas com eles
compraram e gostaram. Em geral, o cliente considera a recomenda¸c˜ao baseando-se
em trˆes premissas sobre quem est´a recomendando [13]: Primeiro, o cliente acredita
em quem recomenda; segundo: assume que quem recomenda conhece seus gostos
ou conhece os gostos de pessoas parecidas com ele; e por ´ultimo, entende que quem
recomenda conhece boa parte das alternativas existentes.
Os Sistemas de Recomenda¸c˜ao surgiram para facilitar a vida do cliente, ajudando-
o a encontrar itens que seriam do seu interesse diante de uma vasta variedade de
1
1.1 Motiva¸c˜ao 2
produtos dispon´ıveis atrav´es da recomenda¸c˜ao de um conjunto de N itens que seriam
do seu interesse. Do lado do varejista, estes sistemas passaram a tornar poss´ıvel a
personaliza¸c˜ao em v´arios canais de contato com o cliente, seja no site de e-commerce
[14], em uma loja convencional, televendas ou atrav´es de mala direta.
V´arios algoritmos de recomenda¸c˜ao tˆem sido propostos [2, 4, 6, 9, 17, 22] na
literatura. Avaliar a qualidade deste algoritmos n˜ao ´e uma tarefa simples [15, 13].
Em geral as avalia¸c˜oes s˜ao realizadas de duas formas:(1)Baseada em um log de
transa¸c˜oes de vendas: neste c aso o log ´e dividido em duas partes, sendo uma para
treino dos algoritmos de recomenda¸c˜ao e a outra parte para avaliar a capacidade de
predi¸c˜ao dos mesmos; (2) Baseada em pess oas: neste tipo de avalia¸c˜ao, pessoas s˜ao
convidadas a avaliar a recomenda¸c˜ao com base em um hist´orico de compras utilizado
como treino.
A maioria dos experimentos encontrados na literatura possuem avalia¸c˜oes base-
adas em logs. Esta forma de realizar experimento ´e escolhida pelo seu baixo custo,
praticidade e tamb´e m pela dificuldade de serem conduzidos experimentos controla-
dos no meio acadˆemico. Embora possua muitas vantagens, a avalia¸c˜ao baseada em
logs pode levar a resultados errˆoneos, considerando que um alto ´ındice de predi¸c˜ao
n˜ao implica nec essariamente em um sistema de recomenda¸c˜ao de qualidade [23]. Por
exemplo, em um estudo de caso que realizamos utilizando o log de transa¸c˜oes de uma
loja de departamentos, verificamos uma grande disparidade entre os resultados das
avalia¸c˜oes realizadas com log de transa¸c˜oes e o resultado das avalia¸c˜oes realizadas
com pessoas.
Tal disparidade se deu em nosso caso porque a recomenda¸c˜ao de itens populares,
que o cliente compraria independentemente da qualidade da recomenda¸c˜ao, produz
bons resultados quando avaliamos os sistemas utilizando logs, mas produz resultados
ruins quando os sistemas s˜ao avaliados por pessoas. Por exemplo, oferecer um cart˜ao
de celular (item popular) a quem est´a comprando uma cama de casal n˜ao faz sentido,
1.2 Trabalhos Relacionados 3
no caso o cliente normalmente esperaria uma sugest˜ao de item complementar ao
produto, como o colch˜ao adequado `as dimens˜oes da cama, um criado-mudo com
acabamento similar, etc. Apesar disso, se o cliente costuma comprar cart˜oes na
loja, a avalia¸c˜ao baseada em logs tender´a a considerar a recomenda¸c˜ao do cart˜ao
como boa, ainda que os produtos n˜ao sejam considerados como relacionados por
uma pessoa. Observe que neste caso a recomenda¸c˜ao do cart˜ao tende a ser ruim
porque o cliente normalmente j´a compra o cart˜ao na loja e porque n˜ao considera o
contexto da compra.
Os objetivos deste trabalho s˜ao: implementar um Sistema de Recomenda¸c˜ao e
realizar um estudo sobre a forma de avalia¸c˜ao deste sistema; propor uma forma de
validar as avalia¸c˜oes baseadas em logs e mostrar como o log utilizado no estudo de
caso pˆode ser filtrado para reduzir a distˆancia entre a avalia¸c˜ao baseada em logs e a
avalia¸c˜ao com pessoas.
1.2 Trabalhos Relacionados
1.2.1 M´etodos de Avalia¸c˜ao de Sistemas de Recomenda¸c˜ao
Os principais trabalhos relacionados ao estudo de formas de avaliar de sistemas
de recomenda¸c˜ao s˜ao:
Hayes et al.[13] propuseram um m´etodo on-line de avalia¸c˜ao de Sistemas de Reco-
menda¸c˜ao para complementar a avalia¸c˜ao off-line (baseada em logs), considerando
que a satisfa¸c˜ao do usu´ario com a t´ec nica de recomenda¸c˜ao pode ser medida so-
mente de forma on-line (com pessoas). Propuseram uma arquitetura similar a uma
arquitetura padr˜ao de Sistemas de Recomenda¸c˜ao, a principal diferen¸ca ´e que ao
inv´es de uma ´unica m´aquina de recomenda¸c˜ao existiriam duas m´aquinas de reco-
menda¸c˜ao. No caso, o usu´ario receberia simultaneamente em um sistema on-line
1.2 Trabalhos Relacionados 4
as recomenda¸c˜oes geradas por duas t´ecnicas implementadas e ent˜ao avaliaria a re-
comenda¸c˜ao. Como trabalhos futuros, al´em da necessidade de um teste pr´atico do
m´etodo, os autores evidenciaram a necessidade da realiza¸c˜ao de uma compara¸c˜ao
direta entre avalia¸c˜oes off-line e on-line. Em nosso trabalho n´os realizamos esta
compara¸c˜ao, mostramos uma forma de medir esta disparidade utilizando m´etricas
de dis tˆancia entre os resultados e apresentamos um exemplo de como um log pode
ser filtrado para reduzir a distˆancia no estudo de caso que realizamos.
McNee et al.[23] acreditam na premissa que os sistemas de recomenda¸c˜ao com
altas taxas de acur´acia ,conforme as m´etricas utilizadas, em algumas situa¸c˜oes n˜ao
geram recomenda¸c˜oes consideradas ´uteis pelos usu´arios. Os autores propuseram
a seguinte maneira de realizar avalia¸c˜ao: Primeiro, julgar a qualidade das reco-
menda¸c˜oes da forma em que os usu´arios vˆeem as recomenda¸c˜oes, como uma lista de
recomenda¸c˜oes. Destacam a neces sidade de m´etricas que atuem sobre a lista inteira,
n˜ao apenas sobre um item que est´a aparecendo na lista. Segundo, ir al´em dos re-
sultados das analises off-line utilizando o feedback dos pr´oprios usu´arios do sistema
de recomenda¸c˜ao. Por ´ultimo, entender o prop´osito da recomenda¸c˜ao considerando
o momento em que o usu´ario est´a iteragindo com o sistema de recomenda¸c˜ao. Seria
julgar as recomenda¸c˜oes de cada usu´ario tendo como base se o sistema ´e ou n˜ao
capaz de conhecer as suas necessidades daquele momento.
Os dois trabalhos a seguir, evidenciam a necessidade ainda atual de experi-
mentos voltados `a defini¸c˜ao de uma metodologia para a avalia¸c˜ao de Sistemas de
Recomenda¸c˜ao:
Adomavicius et al.[8] escreveram um survey sobre o que seria o estado-da-arte
em Sistemas de Recomenda¸c˜ao e destacaram que ainda s˜ao necess´arios experimentos
de qualidade elevada para entender os benef´ıcios e limita¸c˜oes de uma t´ecnica de
recomenda¸c˜ao proposta.
Herlocker et al.[15] fez um levantamento amplo dos fatores que s˜ao considerados
1.2 Trabalhos Relacionados 5
em avalia¸c˜oes de Sistemas de Recomenda¸c˜ao e identificou fatores que influenciam
nos resultados, como o tipo dos dados, o prop´osito da recomenda¸c˜ao e outros. Mos-
trou como os sistemas tem sido avaliados e a diferen¸ca que os torna incompar´aveis,
mesmo quando as mesmas m´etricas s˜ao utilizadas em trabalhos distintos. S˜ao apre-
sentados tamb´em resultados de avalia¸c˜oes emp´ıricas sobre v´arias m´etricas, inclusive
sobre as m´etricas chamadas de m´etricas de n˜ao-acur´acia e que s˜ao voltadas para
identifica¸c˜ao da satisfa¸c˜ao do usu´ario. A necessidade do desenvolvimento de mais
m´etodos padronizados para avalia¸c˜ao de Sistemas de Recomenda¸c˜ao faz parte da
conclus˜ao deste trabalho.
1.2.2 Avalia¸c˜ao de experimentos
Um extenso estudo feito por [15] sobre avalia¸c˜ao de Sistemas de Recomenda¸c˜ao
Colaborativos indica quais m´etricas s˜ao mais apropriadas considerando determina-
dos objetivos da recomenda¸c˜ao. O mesmo es tudo tamb´em mostra a necessidade
da utiliza¸c˜ao de m´etricas padronizadas para que seja poss´ıvel realizar compara¸c˜oes
entre os diversos algoritmos de recomenda¸c˜ao que s˜ao propostos. Apesar deste es-
tudo, ainda podem ser encontrados na literatura grupos de pesquisadores utilizando
m´etricas distintas e v´arias propostas de novas m´etricas.
Encontramos v´arios trabalhos na literatura onde s˜ao comparados diferentes m´etodos
de implanta¸c˜ao de Sistemas de Recomenda¸c˜ao e s˜ao propostos novos algoritmos. Os
principais trabalhos e as m´etricas utilizadas para realiza¸c˜ao das avalia¸c˜oes s˜ao rela-
cionados a seguir: Sarwar et al.[21] fizeram a an´alise de algor´ıtmos de recomenda¸c˜ao
para e-commerce. O objetivo da an´alise era identificar escalabilidade e qualidade
dos sistemas de recomenda¸c˜ao. Os experimentos utilizaram dois tipos diferentes
de dados, o hist´orico de compras da loja fingerhut.com e a base de dados do Mo-
vieLens
1
. A base de dados da loja fingerhut.com continha 6502 Clientes, 25.554
1
http://www.movielens.org/
1.3 Nota¸c˜oes 6
produtos e um total de 97.045 registros de compras. Para medir a qualidade dos ex-
perimentos utilizaram como m´etrica as curvas de precis˜ao, revoca¸c˜ao e F1. Huang et
al.[24] propuseram a utiliza¸c˜ao de um grafo para modelar Sistemas de Recomenda¸c˜ao
para e-commerce. A avalia¸c˜ao foi feita utilizando-se curvas de precis˜ao e revoca¸c˜ao.
Karypis et al.[6, 11, 18] utilizaram as seguintes m´etricas medir a qualidade dos al-
goritmos propostos:(1) N´umero de Hits , que ´e o n´umero de transa¸c˜oes na base de
teste que possuem algum produto que coincide com a lista de top-N pro dutos reco-
mendados para cada cliente. A lista de top-N recomenda¸c˜oes ´e uma lista contendo
N produtos em ordem decrescente de relevancia, onde N refere-se `a quantidade de
recomenda¸c˜oes que ser´a gerada pelo Sistema de Recomenda¸c˜ao. (2)Hit-rate, que ´e
o n´umero de hits/n, onde n ´e a quantidade de clientes; ARHR (average reciprocal
hit-rank), m´etrica que considera a posi¸c˜ao do acerto. Sarwar et.al [21], Karypis et
al. [11] e Ziegler et al.[4] utilizaram para medir a qualidade dos algoritmos propostos
adapta¸c˜oes das curvas de precis˜ao e revoca¸c˜ao, m´etricas amplamente utilizadas em
Recupera¸c˜ao de Informa¸c˜ao.
1.3 Nota¸c˜oes
Como a aplica¸c˜ao do Sistema de Recomenda¸c˜ao estudada aqui est´a voltada para o
contexto de um com´ercio varejista, nesta disserta¸c˜ao ser˜ao usados os termos clientes
e produtos como sinˆonimos de usu´arios e itens, respectivamente. Os usu´arios para
os quais deseja-se computar as recomenda¸c˜oes ser˜ao referenciados como clientes
ativos. Utilizaremos o termo log para denotar um conjunto de transa¸c˜oes com os
registros de compras dos clientes, sendo que cada cliente possui uma ´unica transa¸c˜ao
contendo to dos os produtos comprados em um determinado per´ıodo e cada compra
em particular convencionou-se chamar de ticket.
1.4 Estrutura do Texto 7
1.4 Estrutura do Texto
Esta disserta¸c˜ao est´a dividida em 5 cap´ıtulos. No Cap´ıtulo 2 s˜ao apresentados os
conceitos b´asicos para o entendimento deste trabalho. No Cap´ıtulo 3 ´e apresentada
uma proposta de como deve ser feita a valida¸c˜ao de avalia¸c˜oes baseadas em logs.
No Cap´ıtulo 4 ´e apresentado o estudo de caso realizado para valida¸c˜ao de avalia¸c˜oes
realizadas com logs. Neste cap´ıtulo est˜ao descritas as caracter´ısticas do Sistema de
Recomenda¸c˜ao impleme ntado, as defini¸c˜oes das forma¸c˜oes das bases de treino e teste
e os resultados e compara¸c˜oes entre as avalia¸c˜oes baseadas em logs e com pessoas.
Neste mesmo cap´ıtulo tamb´em s˜ao apresentadas algumas observa¸c˜oes sobre o Sis-
tema de Recomenda¸c˜ao implementado. Por fim, no Cap´ıtulo 5, s˜ao apresentadas as
conclus˜oes gerais do trabalho proposto bem como algumas perspectivas de trabalhos
futuros.
Cap´ıtulo 2
Conceitos B´asicos
2.1 Sistemas de Recomenda¸c˜ao
Um Sistema de Recomenda¸c˜ao pode ser definido como um sistema de filtragem
de informa¸c˜ao utilizado para identificar um conjunto de produtos que seriam de
interesse de determinado cliente.
2.1.1 Processo de Recomenda¸c˜ao
O primeiro passo do processo de recomenda¸c˜ao ´e a entrada de dados, que po-
dem ser transa¸c˜oes de compras, dados demogr´aficos dos clientes, caracter´ısticas dos
produtos, coment´arios, dentre outros. Esses dados s˜ao chamados de votos e podem
ser obtidos de duas formas [19]:
• Expl´ıcita: O pr´oprio cliente indica explicitamente a sua opini˜ao sobre um
determinado item, indicando o seu n´ıvel de satista¸c˜ao. Por exemplo, em uma
escala de 1 a 5, uma estrela indicaria insatisfa¸c˜ao com o produto e 5 estrelas
o n´ıvel m´aximo de satisfa¸c˜ao.
• Impl´ıcita: As avalia¸c˜oes ou votos s˜ao obtidos de forma impl´ıcita, atrav´es da ex-
8
2.1 Sistemas de Recomenda¸c˜ao 9
tra¸c˜ao de um perfil do cliente identificado conforme navega¸c˜ao no site, hist´orico
de compras realizadas pelo cliente (assim o registro da compra de um produto
j´a demonstra um forte interesse do cliente), etc.
Ap´os a coleta dos dados, um m´etodo ou uma combina¸c˜ao de m´etodos s˜ao imple-
mentados para gera¸c˜ao das recomenda¸c˜oes. Em geral as recomenda¸c˜oes s˜ao geradas
considerando-se a correla¸c˜ao entre produtos, correla¸c˜ao entre clientes ou uma com-
bina¸c˜ao destas informa¸c˜oes.
De acordo com o grau de personaliza¸c˜ao utilizado ser´a necess´ario que o cliente
identifique-se para que as recomenda¸c˜oes sejam apresentadas. O grau de persona-
liza¸c˜ao pode ser categorizado da seguinte forma [14]:
• N˜ao-Personalizado: Neste caso, o cliente n˜ao precisa ser identificado e ao
realizar uma consulta por determinado produto (em um site de e-commerce
ou em uma loja f´ısica) a mesma recomenda¸c˜ao que aparece para o cliente
aparece para todos os outros clientes. O exemplo apresentado na Figura 2.1
´e um exemplo t´ıpico de recomenda¸c˜ao n˜ao personalizada onde os produtos
fortemente relacionados s˜ao apresentados juntos com o objetivo principal de
realizar uma venda adicional de um monitor, impressora ou nobreak a quem
est´a olhando uma CPU. A recomenda¸c˜ao ´e gerada com base no comportamento
de compras dos clientes que no passado compraram o produto em quest˜ao.
• Persistente ou Personalizado: Na recomenda¸c˜ao personalizada, como o
pr´oprio nome enfatiza, a recomenda¸c˜ao ´e gerada para um cliente individual-
mente, sendo necess´ario coletar informa¸c˜oes que identifiquem de forma ´unica o
cliente ativo. Por exemplo, na Figura 2.2 um cliente espec´ıfico que havia com-
prado uma impressora, um cart˜ao de recarga de celular, uma munhequeira
e um cadeado, recebeu como recomenda¸c˜oes um cart˜ao de recarga de maior
valor, cartuchos para impressora e um tˆenis.
2.1 Sistemas de Recomenda¸c˜ao 10
• Efˆemero: Os produtos que fizerem parte do carrinho de compras do cliente s˜ao
considerados em conjunto para gera¸c˜ao de rec omenda¸c˜oes, no caso de sites de
e-commerce, os produtos selecionados, as buscas e outros comportamentos da
navega¸c˜ao do cliente entre as categorias de produtos tamb´em s˜ao considerados
durante o processo de gera¸c˜ao das recomenda¸c˜oes. Compras anteriores n˜ao
s˜ao consideradas e o cliente n˜ao ´e reconhecido pelo sistema de recomenda¸c˜ao.
Fig. 2.1: Exemplo de recomenda¸c˜ao do tipo n˜ao-personalizada
A apresenta¸c˜ao das recomenda¸c˜oes pode ser feita de v´arias formas. O cli-
ente pode indicar explicitamente que quer visualizar as recomenda¸c˜oes ou as re-
comenda¸c˜oes podem ser mostradas sem que haja uma solicita¸c˜ao do cliente, por
exemplo, em um site de e-commerce atrav´es da leitura do cookie
1
, a p´agina inicial j´a
´e aberta mostrando as recomenda¸c˜oes espec´ıficas para o cliente ativo. Outra forma
tamb´em ´e apresentar as recomenda¸c˜oes sem que esteja explicitado para o cliente que
s˜ao recomenda¸c˜oes geradas especificamente para ele.
Assim como em outros sistemas, existem duas preocupa¸c˜oes a serem consideradas
no proje to de um Sistema de Recomenda¸c˜ao [21], a primeira ´e o falso positivo, que ´e
1
Grup o de dados trocados entre o navegador e o servidor de p´aginas, colocado num arquivo
(ficheiro) de texto criado no computador do usu´ario.
2.1 Sistemas de Recomenda¸c˜ao 11
Fig. 2.2: Exemplo de recomenda¸c˜ao do tipo personalizada
a recomenda¸c˜ao de produtos que n˜ao s˜ao de interesse do Cliente; A segunda, ´e o falso
negativo, que seria n˜ao recomendar produtos que seriam de interesse do Cliente. O
mais cr´ıtico ´e o falso positivo, pois impacta diretamente na credibilidade do Sistema
de Recomenda¸c˜ao e pode levar a n˜ao utiliza¸c˜ao do sistema.
2.1.2 Classifica¸c˜ao do Problema da Recomenda¸c˜ao
O problema da recomenda¸c˜ao pode ser visto de duas formas distintas:
1. Problema da Predi¸c˜ao [8, 11]: consiste em predizer se um c liente em parti-
cular ir´a gostar de um produto aleat´orio estimando um voto para este produto
com base em votos anteriormente atribu´ıdos pelo cliente a outros produtos.
Ou seja, se reduz a estimar votos aos produtos ainda n˜ao vistos pelo cliente
[8]. No caso, s˜ao recomendados os produtos com maiores estimativas de voto.
2.2 M´etodos de Recomenda¸c˜ao 12
O Sistemas MovieLens, por exemplo, utiliza informa¸c˜oes expl´ıcitas quando ao
gosto de um usu´ario por determinados filmes para em seguinda predizer o
quanto o mesmo usu´ario iria gostar de outros filmes.
2. Problema da Recomenda¸c˜ao top-N [11, 21]: neste caso, o problema ´e
identificar o conjunto de N itens que seriam de interesse de determinado cliente.
Em geral, o problema da recomenda¸c˜ao top-N pode ser formulado da seguinte
forma [8]: Seja C o conjunto de todos os clientes e seja P o conjunto de todos
os produtos candidatos a recomenda¸c˜ao, existe uma fun¸c˜ao u que mede a
utilidade do produto p para o usu´ario c, u:C X P → R, onde R ´e um conjunto
ordenado. Para cada cliente c ∈ C pretende-se obter os N produtos p
∈ P
com maior taxa de utilidade. A utilidade de um item ´e representada por um
voto, obtido de forma impl´ıcita ou expl´ıcita, evidenciando algum interesse do
usu´ario por um determinado item.
Como no estudo de caso que realizamos a base de dados dispon´ıvel ´e o log de
transa¸c˜oes de compras e n˜ao votos atribu´ıdos pelos cliente indicando explicitamente
uma preferˆencia ou n˜ao por determinados produtos, daremos ˆenfase neste trabalho
ao problema da recomenda¸c˜ao top-N.
2.2 M´etodos de Recomenda¸c˜ao
Muitas abordagens tˆem sido propostas, a seguir relacionamos as principais abor-
dagens utilizadas em Sistemas de Recomenda¸c˜ao de produtos.
2.2.1 Baseada em Minera¸c˜ao de Regras de Associa¸c˜ao
A t´ecnica mais utilizada em minera¸c˜ao de dados para gera¸c˜ao de recomenda¸c˜ao
´e a extra¸c˜ao de regras de associa¸c˜oes entre produtos e clientes a partir de um c on-
2.2 M´etodos de Recomenda¸c˜ao 13
junto de hist´oricos de transa¸c˜oes. Basicamente, e sta t´ecnica consiste em descobrir
associa¸c˜oes entre dois conjuntos de produtos de forma que a ocorrˆencia de algum
produto em uma determinada transa¸c˜ao implique que outros pro dutos de outras
transa¸c˜oes tamb´em estar˜ao presentes. Ou seja, a associa¸c˜ao X ⇒ Y , ´e a repre-
senta¸c˜ao da probabilidade condicional de ocorrer Y dado que X ocorre, onde X e
Y s˜ao conjuntos de produtos.
As recomenda¸c˜oes usando regras de associa¸c˜ao podem ser geradas da seguinte
forma [21]:
1. Considerar como entrada um conjunto de transa¸c˜oes, onde cada transa¸c˜ao
cont´em todos os produtos comprados por um cliente. C hamaremos de transa¸c˜ao
o hist´orico de compras de um cliente.
2. Executar um algoritmo para encontrar todas as regras de associa¸c˜oes entre
conjuntos de produtos, considerando um limiar de suporte (percentual de
transa¸c˜oes que cont´em X e Y) e confian¸ca (percentual das transa¸c˜oes que
cont´em X e que tamb´em cont´em Y). Onde:
suporte =
X ∩ Y
total de transa¸c˜oes
(2.1)
confian¸ca =
X ∩ Y
quantidade de transa¸c˜oes que cont´em X
(2.2)
3. Para gerar as top-N recomenda¸c˜oes de um cliente m, deve-se selecionar todas
as regras que contenham no conjunto X os itens do hist´orico de compras do
cliente.
4. Selecionar todos os c onjuntos Y das regras selecionadas no passo anterior e
descarte produtos que j´a tenham sido comprados pelo Cliente.
2.2 M´etodos de Recomenda¸c˜ao 14
5. Ordenar os produtos em ordem crescente de confian¸ca e recomendar os top-N
produtos.
2.2.2 Baseada em conte´udo
Nesta abordagem s˜ao recomendados produtos similares aos produtos comprados
anteriormente pe lo cliente. Formalmente , a utilidade u(p, c) do produto p para o
cliente c ´e estimada com base nas utilidades u(p
i
, c) atribu´ıdas pelo cliente c aos
produtos p
i
∈ P que s˜ao similares ao produto p [8]. Por exemplo, para recomendar
um CD para um cliente, o sis tema de recomenda¸c˜ao busca produtos similares aos
comprados anteriormente pelo cliente considerando puramento o texto (descri¸c˜ao
do item) e caracter´ısticas, como artista e gˆenero musical. Para determinadas cate-
gorias de produtos esta abordagem funciona, mas para outras categorias n˜ao. Um
exemplo seria: Em uma recomenda¸c˜ao personalizada qual seria a utilidade de re-
comendar geladeiras similares a geladeira que o Cliente acabou de comprar? J´a
em uma recomenda¸c˜ao n˜ao personalizada, pode ser ´util apresentar recomenda¸c˜oes
de geladeira similares (caracter´ısticas como cor, pre¸co e funcionalidades, por exem-
plo) a geladeira que o cliente est´a consultando. A principal vantagem do Sistema
de Recomenda¸c˜ao baseado em conte´udo ´e n˜ao necessitar de um avaliador ou uma
quantidade de compras expressiva para gerar recomenda¸c˜oes. Por outro lado, possui
a desvantagem de especializar as recomenda¸c˜oes de produtos, recomendando sempre
produtos similares aos produtos comprados ou vistos anteriormente pelo cliente.
2.2.3 Baseada em Filtragem Colaborativa
Consiste em recomendar produtos, ainda n˜ao comprados pelo cliente ativo, que
outros clientes com preferˆencias similares compraram no passado. O sistema Ta-
pestry [12] foi a primeira implementa¸c˜ao de Sistema de Recomenda¸c˜ao baseado em
2.2 M´etodos de Recomenda¸c˜ao 15
filtragem colaborativa, em uma pequena comunidade de usu´arios, o sistema permi-
tia que os usu´arios registrassem rea¸c˜oes aos documentos lidos e essas anota¸c˜oes das
rea¸c˜oes eram vistas por outros usu´arios, sendo poss´ıvel filtrar documentos avaliados
como releventas por um usu´ario determinado. Atualmente, a filtragem colaborativa
´e a t´ecnica mais utilizada para construir sistemas de recomenda¸c˜ao. Como esta
disserta¸c˜ao ´e sobre avalia¸c˜ao de Sistema de Recomenda¸c˜ao baseado em filtragen
colaborativa, na Se¸c˜ao
2.2.4 Abordagens h´ıbridas
As abordagens h´ıbridas s˜ao utilizadas combinando a abordagem baseada em
conte´udo e a abordagem colaborativa com o objetivo de reduzir as limita¸c˜oes das
duas abordagens. Em [8] as diferentes formas de combinar os m´etodos colaborativo e
basedo em conte´udo dentro de um sistema de recomenda¸c˜ao h´ıbrido s˜ao classificadas
em uma das categorias a seguir:
• Implementa¸c˜ao dos m´etodos colaborativo e baseado em conte´udo separada-
mente e posteriomente combina¸c˜ao das predi¸c˜oes.
• Incorpora¸c˜ao de algumas caracter´ısticas do modelo baseado em conte´udo den-
tro do modelo colaborativo.
• Incorpora¸c˜ao de algumas caracter´ısticas do modelo colaborativo dentro do
modelo baseado em conte´udo.
• Constru¸c˜ao de um modelo unificado que incorpora caracter´ısticas do modelo
colaborativo e do modelo baseado em conte´udo.
2.3 Sistemas de Recomenda¸c˜ao Colaborativos 16
2.3 Sistemas de Recomenda¸c˜ao Colaborativos
Sistemas de recomenda¸c˜ao colaborativos utilizam a opini˜ao de uma comunidade
de usu´arios para ajudar usu´arios dentro da pr´opria comunidade a identificarem
conte´udos, produtos, servi¸cos e at´e mes mo pessoas, de seu interesse, de forma mais
eficiente.
Para gerar recomenda¸c˜oes com base em informa¸c˜oes colaborativas ´e necess´ario
coletar opini˜oes de clientes a respeito dos produtos. Em Sistemas de Recomenda¸c˜ao
para com´ercio, a opini˜ao dos clientes pode ser obtida atrav´es de votos (avalia¸c˜oes)
atribu´ıdos aos produtos pelos clientes. Estes votos s˜ao em geral, hist´orico de compras
realizadas pelos clientes ou um valor num´erico onde o cliente expressa seu gosto pelo
produto.
Na literatura, encontramos duas abordagens para constru¸c˜ao de Sistemas de
Recomenda¸c˜ao baseados em filtragem colaborativa: Baseado em usu´ario e baseado
em Item, tamb´em chamados de baseado em mem´oria e baseado em modelo [22].
2.3.1 Sistema de Recomenda¸c˜ao Colaborativo Baseado em
usu´ario
Em linhas gerais consiste em: Identificar k clientes que s˜ao mais similares ao
cliente ativo; Computar a uni˜ao entre os produtos comprados por todos os k clientes e
associar um peso para c ada produto baseado na sua importˆancia dentro do conjunto;
Por ´ultimo, dentro desta uni˜ao, gerar a recomenda¸c˜ao dos N produtos de maior peso
e que ainda n˜ao foram comprados pelo cliente ativo. Desta forma, para construir
um Sistema de Recomenda¸c˜ao baseado em usu´ario ´e necess´ario [11]:
1. Contruir uma matriz R de dimens˜ao m × n, onde a dimens˜ao m representa os
clientes e a dimens˜ao n os produtos e r
ij
= 1 caso o cliente i tenha comprado
o produtoj e r
ij
= 0, caso contr´ario.
2.3 Sistemas de Recomenda¸c˜ao Colaborativos 17
2. Computar a similaridade entre clientes. Esta similaridade ´e comumente cal-
culada utilizando a correla¸c˜ao de Person ou o conseno. Para cada cliente c,
encontrar uma lista de x clientes C=c
1
, c
2
, ..., c
x
em ordem crescente de simi-
laridade, tal que sim(c, c
1
) > sim(c, c
2
) >.. > sim(c, c
x
).
3. Gerar a lista de recomenda¸c˜oes. Basta selecionar os produtos comprados por
todos os clientes em C mais similares ao cliente ativo, acumulando a frequˆencia
dos produtos candidatos a recomenda¸c˜ao e descartando os produtos j´a com-
prados anteriormente pelo cliente ativo. Ser˜ao recomendados os N mais fre-
quentes. Uma outra forma seria gerar regras de associa¸c˜ao entre os produtos
comprados pelos clientes mais similares, mas tem como desvantagem ser em
muitas situa¸c˜oes uma base pequena tornando dif´ıcil a identifica¸c˜ao de um com-
portamento de compra.
Uma grande vantagem do Sistema de Recomenda¸c˜ao utilizando filtragem colabo-
rativa baseado em cliente ´e justamente a capacidade de detectar um comportamento
de compra e consequentemente gerar recomenda¸c˜oes ”n˜ao ´obvias”. Mas, possui for-
tes limita¸c˜oes relacionadas a: esparsidade, pois enquanto a matriz m x n ´e bastante
esparsa a matriz m x m ´e muito densa; e escalabilidade, j´a que a complexidade de
tempo deste m´etodo cresce linearmente com o n´umero de clientes, o que dificulta
a sua utiliza¸c˜ao por grandes empresas varejistas onde existem milh˜oes de clientes e
produtos.
2.3.2 Sistema de Recomenda¸c˜ao Colaborativo Baseado em
Item
A abordagem de recomenda¸c˜ao colaborativa baseada em item surgiu para resol-
ver o problema de escalabilidade existente na abordagem baseada em usu´ario. V´arias
2.4 M´etodos de Avalia¸c˜ao 18
abordagens tem sido desenvolvidas utilizando similaridades entre itens, [1, 22, 18, 17]
que em linhas gerais consistem em [18, 17]:
1. Construir um modelo que captura o relacionamento entre itens.
2. A partir deste modelo pr´e-computado determinar as top-N recomenda¸c˜oes para
um cliente ativo.
Conforme estudos realizados por [22, 11], algoritmos de recomenda¸c˜ao baseado
em item apresentam melhor performance computacional e qualidade equivalente
ou superior aos algoritmos baseados em usu´ario. Estes foram o principais motivos
pela escolha desta abordagem para implementa¸c˜ao do Sistema de Recomenda¸c˜ao e
utiliza¸c˜ao no estudo de caso. No Cap´ıtulo 4, apresentamos em detalhes o algoritmo
de recomenda¸c˜ao top-N baseado em item que implementamos.
2.4 M´etodos de Avalia¸c˜ao
Um estudo realizado por [8], mostra a importˆancia do tipo da recomenda¸c˜ao para
defini¸c˜ao da m´etrica mais apropriada a ser utilizada na avalia¸c˜ao da qualidade da
recomenda¸c˜ao. Nesta sess˜ao, explicaremos as m´etricas mais utilizadas na literatura
em avalia¸c˜oes de Sistema de Recomenda¸c˜ao.
2.4.1 Avalia¸c˜ao baseada em logs
Este tipo de avalia¸c˜ao ´e a mais utilizada na literatura principalmente pela pra-
ticidade, considerando-se que com pouco esfor¸co ´e poss´ıvel realizar avalia¸c˜oes de
m´ultiplas t´ecnicas e tamb´em repetir experimentos. Em geral, o log ´e dividido em
duas partes, uma parte para treino (chamada de base de treino) dos algor´ıtmos e a
outra para teste (chamada de base de teste). No caso, as recomenda¸c˜oes s˜ao geradas
2.4 M´etodos de Avalia¸c˜ao 19
tendo como entrada os dados da base de treino e para medir a qualidade destas re-
comenda¸c˜oes s˜ao utilizadas as compras do cliente na base de teste, sendo que neste
tipo de avalia¸c˜ao quanto mais o sistema conseguir predizer as compras da base de
teste melhor ser´a o seu resultado. Este tipo de avalia¸c˜ao vem sendo questionado p or
v´arios autores [13, 15, 23] partindo-se da premissa de que um sistema com acur´acia
n˜ao significa necessariamente um sistema que gera recomenda¸c˜oes ´uteis para os cli-
entes. O principal ponto deficit´ario des ta forma de avalia¸c˜ao ´e que n˜ao ´e poss´ıvel
captar a rea¸c˜ao do cliente a uma recomenda¸c˜ao e consequentemente medir a sua real
satisfa¸c˜ao com a utilidade do produto recomendado.
2.4.2 Avalia¸c˜ao com pessoas
Na avalia¸c˜ao com pessoas, clientes reais ou volunt´arios s˜ao convidados a opinarem
sobre a qualidade do Sistema de Recomenda¸c˜ao. As avalia¸c˜oes com pessoas s˜ao mais
dif´ıceis de serem realizadas pelo custo da avalia¸c˜ao quando comparadas `a avalia¸c˜ao
baseada em logs. A grande vantagem da avalia¸c˜ao com pessoas ´e a capacidade de
captar a satisfa¸c˜ao do cliente e identificar ocorrˆencias de falso positivo, problema
bastante cr´ıtico em um sistema de recomenda¸c˜ao. A situa¸c˜ao ideal seria que os
pr´oprios clientes avaliassem as recomenda¸c˜oes durante o processo de compra, mas
n˜ao ´e uma situa¸c˜ao vi´avel por deixar exposto um sistema experimental que em
determinados momentos poder´a gerar recomenda¸c˜oes ruins. Uma desvantagem da
avalia¸c˜ao em um ambiente experimental ´e que n˜ao existe a inten¸c˜ao de compra.
Na avalia¸c˜ao com pessoas ´e necess´ario definir como as recomenda¸c˜oes geradas
pelos algoritmos ser˜ao apresentadas. Em [13] s˜ao identificadas trˆes alternativas de
apresenta¸c˜ao das recomenda¸c˜oes:
• Misturadas: neste caso, o avaliador ir´a visualizar um conjunto un´ıco de reco-
menda¸c˜oes, ou seja, a uni˜ao das recomenda¸c˜oes geradas por todas as t´ecnicas
2.5 M´etricas de Acur´acia 20
que fazem parte do experimento. Desta forma, os produtos duplicados ser˜ao
visualizados uma ´unica vez e o avaliador n˜ao saber´a qual t´ecnica est´a avali-
ando.
• Separadas: cada conjunto de recomenda¸c˜oes resultante de uma t´ecnica ser´a
apresentado s eparadamente para o avaliador, de tal forma que o avaliador
saiba exatamente que est´a avaliando t´ecnicas diferentes.
• Em cascata: a recomenda¸c˜oes resultantes das diferentes t´ecnicas s˜ao apre-
sentadas de forma alternada.
2.5 M´etricas de Acur´acia
Na literatura encontramos diversas m´etricas que s˜ao utilizadas para avaliar a
qualidade de um Sistema de Recomenda¸c˜ao. As m´etricas de acur´acia s˜ao em geral
categorizadas como, m´etricas de acur´acia estat´ıstica e m´etricas de acur´arica de su-
porte a de cis˜ao. A primeira avalia a acur´acia de um sistema comparando um score
num´erico de recomenda¸c˜ao e o voto atribu´ıdo p elo cliente ao par cliente-item dentro
da base de teste. A segunda avalia o qu˜ao efetivamente uma m´aquina de predi¸c˜ao
ajuda um cliente a selecionar produtos de qualidade entre os demais produtos dis-
pon´ıveis [21].
2.5.1 MAE (Mean Absolute Error)
Mede a capacidade que o algoritmo tem de predizer o voto que seria dado por
um cliente a um produto selecionado aleatoriamente.
´
E classificada como m´etrica
de acur´acia estat´ıstica.
MAE =
N
i=1
|p
i
− v
i
|/N (2.3)
2.5 M´etricas de Acur´acia 21
onde, p
i
´e o valor da predi¸c˜ao e v
i
´e o valor do voto.
Esta m´etrica ´e aplicada aos sistemas de recomenda¸c˜ao que tratam o problema da
predi¸c˜ao do voto que o cliente daria a um produto espec´ıfico, mas para o sistema de
recomenda¸c˜ao que tiver como objetivo gerar o ranking dos melhores produtos que
seriam de interesse do cliente, esta m´etrica n˜ao ´e apropriada [15].
2.5.2 Hits
Para computar o n´umero de hits, dividi-se o log de transa¸c˜oes em duas partes,
sendo uma para treino, chamada de base de treino, e a outra para teste, chamada
de base de teste. As recomenda¸c˜oes s˜ao geradas com base nos dados contidos na
base de treino. O n´umero de Hits, ou acertos, ´e o total de produtos na base de teste
que tamb´em est˜ao presentes na lista de produtos recomendados para cada cliente.
´
E computado no m´aximo um acerto por cliente.
2.5.3 HR (Hit rate)
A m´etrica mais recentemente usada na literatura para medir a qualidade dos Sis-
temas de Recomenda¸c˜ao cujo objetivo ´e gerar uma lista com top-N recomenda¸c˜oes,
´e o HR (Hit-rate). Seja n o n´umero de clientes, o hit-rate ´e calculado da seguinte
forma:
HR(hit − rate) = n´umero de hits/n (2.4)
2.5.4 ARHR (average reciprocal hit-rank)
Como o hit-rate trata igualmente os acertos independentemente da posi¸c˜ao em
que o item aparece dentro da lista de recomenda¸c˜oes, escolhemos o ARHR por
considerar a ocorrˆencia do acerto dentro do top-N gerado para cada cliente. Desta
2.5 M´etricas de Acur´acia 22
forma, quanto mais perto do topo da lista forem os hits maior ser´a o seu peso. O
c´alculo do ARHR ´e:
ARHR = 1/n
h
i=1
1/p
i
(2.5)
Onde h ´e o n´umero de acertos nas posi¸c˜oes p
i
para cada lista top-N gerada.
Sendo 1 <= p
i
<= N.
2.5.5 Precis˜ao e Revoca¸c˜ao
S˜ao m´etricas amplamente utilizadas em Recupera¸c˜ao de Informa¸c˜ao. Em Siste-
mas de Recomenda¸c˜ao, a precis˜ao mede a acur´acia de predi¸c˜ao do comportamento
de compra do cliente e a revoca¸c˜ao, mede a relevˆancia da recomenda¸c˜ao para um
cliente. Em [15], existe a seguinte defini¸c˜ao destas m´etricas no contexto de Sistemas
de Recomenda¸c˜ao:
Precis˜ao =
N
RL
N
R
(2.6)
onde, N
RL
´e o total de produtos relevantes recomendados e N
R
´e o total de
produtos recomendados.
Revoca¸c˜ao =
N
RL
N
RLD
(2.7)
onde, N
RL
´e o total de produtos relevantes recomendados e N
RLD
´e o total de
produtos relevantes dispon´ıvels.
Algumas adapta¸c˜oes destas m´etricas foram sugeridas [21, 11] e a proposta por
[11] acabou sendo adotada em v´arios trabalhos encontrados na literatura e ´e igual
ao hit rate, ou seja, a revoca¸c˜ao ´e igual ao n´umero de produtos contidos na base
de teste e que tamb´em fazem parte das top-N recomenda¸c˜oes retornadas para cada
2.5 M´etricas de Acur´acia 23
cliente.
Revoca¸c˜ao =
T este ∩ top − N
n
(2.8)
onde n ´e o n´umero de clientes.
Cap´ıtulo 3
Valida¸c˜ao de Avalia¸c˜oes Baseadas
em Log
A grande maioria das avalia¸c˜oes de Sistemas de Recomenda¸c˜ao encontradas na
literatura ´e baseada em logs. Essa forma de avalia¸c˜ao ´e escolhida principalmente
pela praticidade, considerando-se que com pouco esfor¸co ´e possivel avaliar um grande
n´umero de algoritmos. J´a a avalia¸c˜ao com pessoas possui um custo elevado e por
isso muitas vezes acaba n˜ao sendo considerada, apesar de ser a avalia¸c˜ao que melhor
consegue captar a rea¸c˜ao do cliente `a recomenda¸c˜ao [13, 15, 23].
A quest˜ao ´e se a avalia¸c˜ao baseada em log ´e suficiente ou n˜ao para indicar se um
sistema de recomenda¸c˜ao ´e melhor ou pior que outro. A situa¸c˜ao ideal seria a rea-
liza¸c˜ao de avalia¸c˜oes baseadas em log com resultados os mais pr´oximos poss´ıveis das
avalia¸c˜oes com pessoas, ou sabendo-se qual a distˆancia entre as avalia¸c˜oes. Neste
trabalho ´e proposta uma forma de verificar se a avalia¸c˜ao baseada em um dado
log pode ser utilizada de forma confi´avel e apresentando resultados pr´oximos de
avalia¸c˜oes com pessoas. Para realiza¸c˜ao desta valida¸c˜ao dever´a ser executada neces-
sariamente, al´em da avalia¸c˜ao baseada no log, uma avalia¸c˜ao inicial com pessoas.
A id´eia principal ´e comparar os resultados das duas avalia¸c˜oes, identificar e filtrar
24
3.1 Gera¸c˜ao das Recomenda¸c˜oes 25
poss´ıveis ru´ıdos que possam ser os respons´aveis pela distˆancia entre o resultado da
avalia¸c˜ao baseada em log e a avalia¸c˜ao com pessoas. O objetivo principal ´e que,
uma vez realizada a valida¸c˜ao, novos experimentos possam ser realizados apenas
com logs, mas de maneira confi´avel. Desta forma, ap´os o fim do processo, a base
de logs possa ser utilizada como uma cole¸c˜ao de referˆencia mais segura em novos
experimentos.
Neste cap´ıtulo ser˜ao apresentados os passos necess´arios para valida¸c˜ao de expe-
rimentos realizados com logs. Na Sess˜ao 3.1 s˜ao apresentados alguns pontos a serem
considerados na gera¸c˜ao das recomenda¸c˜oes para que os ru´ıdos possam ser eviden-
ciados. Na Sess˜ao 3.2 ´e definido o modo como as avalia¸c˜oes ser˜ao comparadas. Na
Sess˜ao 3.3 ser˜ao mostradas algumas formas de identificar quais s˜ao os produtos que
podem gerar ru´ıdos na avalia¸c˜ao baseada em logs. Por fim, na Sess˜ao 3.4 ´e apresen-
tada uma sugest˜ao de como pode ser feito o filtro de um log e quais os impactos que
essa filtragem pode trazer para o Sistema de Recomenda¸c˜ao.
3.1 Gera¸c˜ao das Recomenda¸c˜oes
Alguns pontos na gera¸c˜ao das recomenda¸c˜oes dever˜ao ser considerados para re-
aliza¸c˜ao da valida¸c˜ao de uma avalia¸c˜ao baseada em log :
•
´
E necess´ario que seja explorado um n´umero significativo de p oss´ıves reco-
menda¸c˜oes. A gera¸c˜ao de recomenda¸c˜oes as mais variadas poss´ıveis facilita a
identifica¸c˜ao de ru´ıdos que possam distorcer o resultado da avalia¸c˜ao baseada
em log quando comparada com a avalia¸c˜ao com pessoas.
• Os algoritmos devem se r executados sobre a mesma base de treino para que
as recomenda¸c˜oes geradas sejam compar´aveis entre si. As recomenda¸c˜oes que
ser˜ao avaliadas por pessoas dever˜ao ser uma amostragem das recomenda¸c˜oes
3.2 Compara¸c˜ao de Avalia¸c˜oes com Pessoas e Baseada em Logs 26
geradas para avalia¸c˜ao baseada em log. As recomenda¸c˜oes devem ser arma-
zenadas em uma base de rec omenda¸c˜oes de tal forma que seja poss´ıvel iden-
tificar qual algoritmo originou cada recomenda¸c˜ao. A partir desta base de
recomenda¸c˜oes ´unica podem ser realizadas em paralelo as avalia¸c˜oes baseadas
em log e as avalia¸c˜oes com pessoas.
3.2 Compara¸c˜ao de Avalia¸c˜oes com Pessoas e Ba-
seada em Logs
Ap´os as avalia¸c˜oes com pessoas e avalia¸c˜oes baseadas em log serem conclu´ıdas ´e
necess´ario compar´a-las para identificar se as avalia¸c˜oes baseadas em log produzem
resultados que refletem a percep¸c˜ao de qualidade indicada pelas pessoas.
Uma forma de comparar a avalia¸c˜ao com pessoas e a avalia¸c˜ao baseada em log
seria simplesmente medir as distˆancias entre os resultados, mas como os resultados
n˜ao s˜ao compat´ıveis, considerando-se que a primeira mede satisfa¸c˜ao e a segunda
capacidade de predi¸c˜ao, optou-se por comparar a ordem de qualidade atribu´ıda aos
v´arios sistemas estudados nas duas avalia¸c˜oes. Com estas listas sabe-se exatamente
quais algoritmos geram recomenda¸c˜oes melhores ou piores na avalia¸c˜ao baseada em
log e na avalia¸c˜ao com pessoas. Quanto maior a diferen¸ca entre as listas menor ´e a
utilidade da avalia¸c˜ao baseada em log.
Para comparar a distˆancia entre estas listas ´e proposta a utiliza¸c˜ao da distˆancia
de Kendall [16], por ser de f´acil entendimento e uma m´etrica amplamente utilizada
na literatura. Sendo L
1
a lista com os algoritmos em ordem decrescente de acur´acia
conforme avalia¸c˜ao baseada em log e L
2
a lista com os algoritmos em ordem decres-
cente de avalia¸c˜ao da utilidade das recomenda¸c˜oes conforme avalia¸c˜ao com pessoas.
Utilizando-se a f´ormula para medir a distˆancia de Kendall entre duas listas L
1
e L
2
3.3 Identifica¸c˜ao de ru´ıdos no log 27
temos:
K(L
1
, L
2
) =
i,j∈P
K
i,j
(L
1
, L
2
)
(n(n − 1)/2)
(3.1)
onde, P ´e o conjunto dos pares dos distintos elementos em L
1
e L
2
;
K
i,j
(L
1
, L
2
) = 0, se i e j est˜ao na mesma ordem dentro das listas L
1
e L
2
;
K
i,j
(L
1
, L
2
) = 1, se i e j n˜ao est˜ao na mesma ordem dentro das listas L
1
e L
2
;
A distˆancia ´e normalizada dividindo-se o resultado por (n(n − 1)/2), onde n ´e o
tamanho da lista. Assim, o valor 1 indica o n´ıvel m´aximo de divergˆencia entre L
1
e
L
2
.
Se a distˆancia entre as listas n˜ao for satisfat´oria, ou seja, pr´oxima de 1, uma
estrat´egia para reduzir esta distˆancia ´e filtrar entradas do log que possam ser os
respons´aveis pela distˆancia entre as avalia¸c˜oes.
3.3 Identifica¸c˜ao de ru´ıdos no log
Uma forma de identificar entradas no log respons´aveis pela distˆancia entre o
resultado da avalia¸c˜ao com pessoas e o resultado da avalia¸c˜ao baseada em logs ´e
analisar os produtos n˜ao relevantes na avalia¸c˜ao com pessoas e que s˜ao classificados
como relevantes na avalia¸c˜ao baseada em logs e tentar encontrar caracter´ısticas
gen´ericas entre estes produtos.
´
E importante identificar estes produtos pois s˜ao
eles que certamente geram os falsos positivos, problema que pode comprometer a
credibilidade do sistema de recomenda¸c˜ao.
Em um Sistema de Recomenda¸c˜ao para um com´ercio varejista os produtos po-
pulares certamente ser˜ao fortes candidatos a gerarem falsos positivos. Em geral
s˜ao produtos que o cliente compraria independentemente da recomenda¸c˜ao. Re-
comend´a-los pode parecer ´obvio demais e algumas vezes sem sentido. Um ponto
a ser destacado ´e que em um Sistema de Recomenda¸c˜ao onde o log de transa¸c˜oes
3.4 Filtragem do Log 28
possui produtos de uma ´unica categoria, tais como Livros, CDs e DVDs, n˜ao ´e
t˜ao evidente o impacto dos populares, pois acaba sendo indicado um popular da
mesma categoria. Mas, quando h´a muitas categorias, os produtos populares podem
gerar recomenda¸c˜oes avaliadas como estranhas ou sem utilidade pelas pessoas. Por
exemplo, o cliente seleciona uma geladeira e o sistema recomenda o CD da Banda
Calypso.
Ap´os identifica¸c˜ao dos produtos respons´aveis pelos falsos positivos na avalia¸c˜ao
com log, deve-se retirar esta entrada do ranking das recomenda¸c˜oes geradas e realizar
novo c´alculo da efic´acia de predi¸c˜ao do algoritmo, comparando-se o resultado com
a avalia¸c˜ao com pessoas. Quanto mais pr´oximos forem os resultados, melhor ´e a
idenfica¸c˜ao dos ru´ıdos, pois significar´a que a simula¸c˜ao da avalia¸c˜ao com pessoas
est´a sendo realizada com maior exatid˜ao pela avalia¸c˜ao baseada em logs.
3.4 Filtragem do Log
Uma vez identificados os produtos que podem estar ocasionando ru´ıdos, o log
pode ser filtrado de duas formas:
1. Antes de Gerar as Recomenda¸c˜oes: Neste caso, a parte do log de transa¸c˜oes
que comp˜oe a base de treino deve ter um filtro dos produtos identificados
como ru´ıdos. Deve-se observar que a filtragem do log pode resultar em uma
cobertura menor de produtos recomendados e de clientes com recomenda¸c˜oes,
consideran-se que os produtos fitrados n˜ao ser˜ao recomendados.
2. Na gera¸c˜ao da lista top-N: No momento de gerar o ranking das recomenda¸c˜oes
s˜ao descartados os produtos geradores de ru´ıdos. Mesmo nesta situa¸c˜ao ainda
h´a uma diminui¸c˜ao na cobertura de clientes que recebem recomenda¸c˜oes. Uma
solu¸c˜ao para amenizar este problema seria n˜ao recomendar os produtos gera-
3.4 Filtragem do Log 29
dores de ru´ıdo somente em situa¸c˜oes em que hajam outros N produtos a serem
recomendados.
Cap´ıtulo 4
Estudo de Caso
Este estudo de caso tem como principal objetivo realizar a valida¸c˜ao de avalia¸c˜oes
de Sistemas de Recomenda¸c˜ao top-N baseadas em log s eguindo os passos descritos
no Cap´ıtulo 3. Para realiza¸c˜ao deste estudo de caso teve-se acesso a um log de
transa¸c˜oes de vendas de uma empresa varejista que possui lojas convencionais, um
site de e-commerce e lojas h´ıbridas (com venda por cat´alogo). Foi implementado
no site
1
de e-commerce desta empresa um sistema de recomenda¸c˜ao personalizado e
n˜ao personalizado. A principal caracter´ıstica deste log ´e a diversidade, sendo cerca
de 35.000 produtos ativos em mais de 100 categorias diferentes. Os dados obtidos
s˜ao impl´ıcitos, sendo que a compra de um determinado produto por um cliente ´e
uma forte demonstra¸c˜ao de interesse no produto e o fato do cliente n˜ao comprar um
produto em particular n˜ao significa que o cliente n˜ao goste deste produto.
Na Sess˜ao 4.1 s˜ao apresentados os detalhes de implementa¸c˜ao do Sistema de
Recomenda¸c˜ao. Na Sess˜ao 4.2 s˜ao descritas as caracter´ısticas do log de transa¸c˜oes
utilizado neste estudo de caso. Na Sess˜ao 4.3 ´e apresentada a forma na qual as
recomenda¸c˜oes foram geradas e um detalhamento de como foi escolhida a forma¸c˜ao
das bases de treino e teste. Na Sess˜ao 4.4 s˜ao apresentados os res ultados das ava-
1
http://www.bemol.com.br
30
4.1 Implementa¸c˜ao do Sistema de Recomenda¸c˜ao 31
lia¸c˜oes baseadas em logs e avalia¸c˜oes com pessoas. Na Sess˜ao 4.5 s˜ao identificados e
filtrados os ru´ıdos encontrados no log de transa¸c˜oes. Na Sess˜ao 4.6 s˜ao comparados
os resultados das avalia¸c˜oes e finalmente na Sess˜ao 4.7 s˜ao apresentadas algumas
observa¸c˜oes
4.1 Implementa¸c˜ao do Sistema de Recomenda¸c˜ao
Na implementa¸c˜ao do Sistema de Recomenda¸c˜ao optou-se por utilizar o Algo-
ritmo de Recomenda¸c˜ao top-N baseado em Item pela escalabilidade, por obter bons
resultados quando comparado `a recomenda¸c˜ao colaborativa baseada em usu´arios
[22, 11] e por j´a ser um algoritmo implementado em sites comerciais, como por
exemplo o site da Amazon.com [17].
4.1.1 Algoritmo de Recomenda¸c˜ao top-N Baseado em Item
Este algoritmo parte do princ´ıpio de que os produtos comprados no passado
podem determinar uma preferˆencia de compra no futuro, considerando o comp orta-
mento de outros clientes que compraram os mesmos produtos e tamb´em outros pro-
dutos. Os outros produtos comprados s˜ao os produtos candidatos `a recomenda¸c˜ao.
A constru¸c˜ao do modelo pode ser definida como: Seja C o conjunto de todos
os clientes, P o conjunto de produtos e T o conjunto de transa¸c˜oes, onde cada
transa¸c˜ao t
´e composta por um cliente c
e os respectivos produtos p
comprados.
Contruir uma matriz R de dimens˜ao n × n, onde n ´e o n´umero de produtos e r
ij
=
u(p
i
, p
j
), sendo u(p
i
, p
j
) uma fun¸c˜ao que para cada produto p
i
⊂ P mede a utilidade
de recomendar um produto p
j
⊂ P , considerando a ocorrˆencia simultˆanea de p
i
e p
j
em cada transa¸c˜ao t
⊂ T .
Foi implementado o mesmo algoritmo descrito em [17], conforme pode ser visto
no Algoritmo 1, primeiramente nas linhas 02 a 08 registra-se na matriz item × item
4.1 Implementa¸c˜ao do Sistema de Recomenda¸c˜ao 32
Algoritmo 1 C´alculo da matriz item × item
01 in´ıcio
02 para cada produto p
i
⊂ P
03 para cada cliente c que comprou p
i
04 para cada produto p
j
comprado por c
05 Atualizar Matriz item × item (p
i
, p
j
)
06 fim
07 fim
08 fim
09 para cada produto p
j
10 Computar fun¸c˜ao de utilidade u(p
i
, p
j
)
11 fim
fim
a ocorrˆencia simultˆanea de produtos dentro da mesma transa¸c˜ao de compras, em
seguida, nas linhas 09,10 e 11, faz-se o c´alculo da utilidade de recomendar um
produto p
j
dado que o cliente demonstrou algum interesse pelo produto p
i
.
Uma vez computada a matriz que calcula a utilidade entre produtos u(p
i
, p
j
),
a recomenda¸c˜ao n˜ao-personalizada pode ser realizada simplesmente indicando para
um produto p
i
os N produtos p
j
relacionados em ordem decrescente de utilidade
u(p
i
, p
j
). A recomenda¸c˜ao personalizada ´e realizada com base nos produtos com-
prados anteriormente pelo cliente ativo. Conforme descrito no Algoritmo 2, para
gerar a recomenda¸c˜ao personalizada ´e passado como parametro o cliente ativo c e o
seu hist´orico de compras t
, nas linhas 03 a 05 ´e feita a uni˜ao dos pro dutos candidatos
`a recomenda¸c˜ao de cada p ⊂ t
, em seguida na linha 06 a fun¸c˜ao GeraTopN(r,N) re-
torna os top-N mais relacionados j´a excluindo-se ocorrˆencias de produtos comprados
anteriormente pelo cliente.
Fun¸c˜ao de Utilidade
Embora na literatura seja bastante utilizado o termo similaridade entre produ-
tos, neste trabalho ´e utilizado o termo utilidade de um produto dada a acorrˆencia
de outro, ou simplesmente utilidade. Um exemplo pr´atico seria: qual a utilidade
4.1 Implementa¸c˜ao do Sistema de Recomenda¸c˜ao 33
Algoritmo 2 Recomenda(c,t’): Recomenda¸c˜ao personalizada
01 r: matriz[1,n]{n ´e a quantidade de produtos distintos}
02 in´ıcio
03 para cada produto p ⊂ t
04 r = SomaLinha(p
i
)
05 fim
06 GeraTopN(r,N)
07 fim
de se recomendar um depurador de ar considerando-se que um fog˜ao foi comprado,
no caso, A e B n˜ao s˜ao produtos similares. Para que fossem geradas diversas reco-
menda¸c˜oes distintas o calculo da fun¸c˜ao de utilidade u(A, B) foi fe ito de 8 formas
distintas (vide Tabela 4.1). A maioria das f´ormulas utilizadas ´e baseada na probabi-
liade condicional de compra de um item considerando que outro item foi comprado
anteriormente. Em [11] ´e poss´ıvel encontrar um estudo detalhado sobre a utiliza¸c˜ao
de probabilidade condicional para c´alculo da fun¸c˜ao de utilidade. Sendo P (B/A) a
probabilidade condicional do cliente comprar um produto B, considerando que um
produto A foi comprado anteriormente, ent˜ao P (B/A) pode ser definida [11] como a
quantidade de clientes que compraram os produtos A e B, dividido pela quantidade
de clientes que compraram o produto A, sendo
P (B/A) =
F req(A, B)
F req(A)
, (4.1)
onde Freq(X) ´e definido como o n´umero de clientes que compraram produtos
dentro do conjunto X. Este c´alculo claramente tende a beneficiar os itens popula-
res, ou seja, P (A, B) resultar´a em valores elevados que n˜ao refletir˜ao exatamente a
ocorrˆencia simultˆanea de A e B e sim a popularidade de B.Existem algumas solu¸c˜oes
apresentadas em [11] para reduzir es te problema. Experimentos realizados por [18]
chegaram `a seguinte f´ormula para computar a utilidade de recomendar um produto
B dado que um produto A foi comprado anteriomente:
4.1 Implementa¸c˜ao do Sistema de Recomenda¸c˜ao 34
u(A, B) =
F req(AB)
F req(A) ∗ Freq(B)
α
(4.2)
onde α ´e um valor entre 0 e 1. Quando α = 0 a Equa¸c˜ao 4.2 fica idˆentica a
Equa¸c˜ao 4.1.
Como suspeita-se que os itens populares distorcem os resultados das avalia¸c˜oes
com log, algumas das f´ormulas que ser˜ao utilizadas neste estudo claramente be-
neficiam os populares e outras p enalizam os populares. Conforme apresentado
na Tabela 4.1, as f´ormulas F 4, F 5 e F 6 s˜ao idˆenticas `a f´ormula apresentada na
Equa¸c˜ao 4.2, com α = 0, α = 1, α = 0, 5, respectivamente. A f´ormula F 3 ´e P (A/B)
multiplicado por log
2
P (B) e foi proposto em [10]. As f´ormulas F 1, F 7 e F 8 fo-
ram propostas como alternativas para complementar as possibilidades de gera¸c˜ao
de recomenda¸c˜oes distintas, onde F 7 nada mais ´e do que P (A/B) multiplicado por
log
2
P (A), F 8 ´e P (B/A) multiplicado por P (A/B) e por ´ultimo a f´ormula F 1 ´e a
f´ormula F 3 modificada, sendo igual a F 3 multiplicada por F req(AB).
u(A,B)
F 1 = (F req(AB)/F req(B)) ∗ (F req(AB) ∗ log
2
(P (B))
F 2 = F req(AB)
F 3 = (F req(AB)/F req(B)) ∗ log
2
P (B)
F 4 = F req(AB)/(F req(A) ∗ F req(B)
1
)
F 5 = F req(AB)/(F req(A) ∗ F req(B)
0
)
F 6 = F req(AB)/(F req(A) ∗ F req(B)
5
)
F 7 = (F req(AB)/F req(A)) ∗ log
2
(P (B))
F 8 = (F req(AB)/F req(A)) ∗ (F req(AB)/F req(B))
Tab. 4.1: C´alculo da fun¸c˜ao de utilidade u(A,B)
Complexidade
A computa¸c˜ao da matriz com a utilidade entre os produtos ´e O(N
2
M) no pior
caso, onde N ´e a quantidade de produtos e M a quantidade de clientes. Na pr´atica
a complexidade ´e pr´oxima de O(NM), pois a grande maioria dos clientes compra
4.2 Log de transa¸c˜oes 35
um n´umero pequeno de produtos comparado com a quantidade dispon´ıvel.
4.2 Log de transa¸c˜oes
Teve-se acesso a um log de transa¸c˜oes onde est˜ao registrados 9 meses de compras
realizadas por 29.664 clientes identificados. O crit´erio para sele¸c˜ao dos clientes foi
buscar somente os clientes que possu´ıam pelo menos uma compra no mˆes seguinte
aos trˆes primeiros meses iniciais. Para facilitar o entendimento da forma¸c˜ao das
bases de treino e teste, o log de transa¸c˜oes foi dividido em trˆes bases conforme
descrito a seguir:
1. Base1: 3 meses de compras (abril, maio, junho)
2. Base2: 2 meses de compras (julho e agosto)
3. Base3: 6 meses de compras (julho, agosto, setembro, outubro, novembro e
dezembro)
Na literatura encontram-se v´arios tipos de forma¸c˜oes da base de teste. A ausˆencia
de um padr˜ao torna dif´ıcil a compara¸c˜ao dos resultados dos experimentos. Neste
estudo de caso utilizou-se inicialmente as seguintes forma¸c˜oes de bases de treino e
teste:
• M1: Base de teste composta pela primeira compra realizada por cada Cliente
logo ap´os o per´ıodo de treino. A base de treino ´e a Base1 e a base de teste ´e
o primeiro ticket de compra do cliente registrado na base2. Desta forma ser´a
medida a acur´acia da recomenta¸c˜ao dada uma compra (ticket) do Cliente.
• M2: Define-se um produto comprado por cada cliente para compor a base de
teste. Para esta forma¸c˜ao de base, foi retirado aleatoriamente um produto
4.3 Gera¸c˜ao das Recomenda¸c˜oes 36
do ´ultimo ticket de compra do cliente da base 1 e estes produtos passaram a
compor a base de teste.
• M3: Todas as compras realizadas durante 2 meses ap´os o per´ıodo utilizado na
base de treino ir˜ao compor a base de teste. A base de treino ´e a Base1 e a
base de teste ´e a Base2.
• M4: Todas as compras realizadas durante 6 meses ap´os o per´ıodo utilizado na
base de treino ir˜ao compor a base de teste.A base de treino ´e a Base1 e a base
de teste ´e a Base3.
Na Tabela 4.2 s˜ao apresentadas as caracter´ısticas de cada base de teste, quanti-
dade de clientes, n´umero de tickets de compra, o n´umero m´edio de tickets por cliente
e a n´umero m´e dio de produtos distintos comprados por cliente.
Forma¸c˜ao da base de teste
Caracter´ısticas M1 M2 M3 M4
Quant. de c lientes 29.664 25.353 29.664 29.664
N´umero de Tickets 29.664 25.353 91.842 148.708
M´edia de Tickets 1 1 3,10 5,02
M´edia de Produtos 1,91 1 4,97 10,22
Tab. 4.2: Caracter´ısticas das bases de teste obtidas com as forma¸c˜oes M1, M2, M3
e M4
4.3 Gera¸c˜ao das Recomenda¸c˜oes
As recomenda¸c˜oes foram geradas a partir da execu¸c˜ao do algoritmo de reco-
menda¸c˜ao sobre a base de treino. O resultado da execu¸c˜ao ´e a lista top-N de itens
que seriam de interesse do cliente, onde N ´e igual a 10. Foram geradas 8 listas top-N
para cada cliente, sendo cada uma das listas geradas utilizando uma das fun¸c˜oes de
utilidade u(A, B) descritas na Tabela 4.1.
4.3 Gera¸c˜ao das Recomenda¸c˜oes 37
Para defini¸c˜ao de qual forma¸c˜ao da base de treino e teste seria utilizada neste
estudo de caso, calculou-se o HR sobre as 4 forma¸c˜oes da base de teste indicadas na
Tabela 4.2. Na Figura 4.3 pode ser visto o hit rate (HR) obtido em cada uma das
fun¸c˜oes de utilidade u(a,b) avaliadas utilizando as bases de teste M1, M2, M3 e M4.
Analisando-se o HR obtido sobre as bases M1, M3 e M4, ´e f´acil observar que quanto
maior a base de teste, maior o hit rate, entretanto o n´umero m´edio de tickets por
cliente tamb´em aumenta.
HR (Hit Rate)
u(a,b) M1 M2 M3 M4
F1 0,081 0,147 0,162 0,218
F2 0,124 0,156 0,237 0,331
F3 0,023 0,062 0,047 0,067
F4 0,044 0,094 0,086 0,121
F5 0,124 0,159 0,235 0,329
F6 0,094 0,154 0,179 0,244
F7 0,120 0,162 0,224 0,311
F8 0,088 0,157 0,172 0,233
Tab. 4.3: Avalia¸c˜ao baseada em log: Hit rate calculado em bases de teste diferentes.
As forma¸c˜oes de base M1 e M2 parecem ser as mais indicadas por refletirem a
acur´acia do Sistema dada uma compra espec´ıfica. Por este motivo, as avalia¸c˜oes
utilizando estas duas possibilidades de forma¸c˜oes de bases ser˜ao analisadas mais
detalhadamente para ent˜ao definir-se qual forma¸c˜ao ser´a utilizada neste estudo de
caso.
Os resultados do hits e demais m´etricas utilizando a forma¸c˜ao da base de teste
M2 foran melhores, como pode ser visto na Tabela 4.4, por fazer da base de teste
um ´unico produto por cliente, que comp˜oe um ticket de compra que possui outros
produtos comprados juntos e que f azem parte da base de treino. Supondo-se que
um cliente possui um ´unico ticket de compras com dois produtos, uma cama e um
4.4 Avalia¸c˜oes do Sistema de Recomenda¸c˜ao 38
colch˜ao, o processo normal de um Sistema de Recomenda¸c˜ao seria a partir deste
hist´orico tentar predizer quais produtos seriam de interesse deste cliente. Portanto,
dividir um ticket de compra em treino e teste certamente aumenta a acur´acia pois
em in´umeras situa¸coes a base de treino j´a possui outros produtos fortemente relaci-
onados, entretanto n˜ao segue o processo normal de recomenda¸c˜ao.
Optou-se por utilizar a base M1 por parece ser a mais adequada por trˆes mo-
tivos: primeiro, reflete a qualidade da recomenda¸c˜ao na primeira compra (ticket)
realizada pelo cliente logo ap´os a gera¸c˜ao da recomenda¸c˜ao; segundo, com este tipo
de forma¸c˜ao a avalia¸c˜ao com pessoas ´e feita simulando-se exatamente um sistema
onde as recomenda¸c˜oes s˜ao apresentadas ao cliente considerando todo o seu hist´orico
de compras; e por ´ultimo, como consequˆencia do segundo motivo, torna p oss´ıvel
comparar o resultado da avalia¸c˜ao baseada em logs e avalia¸c˜ao com pessoas.
Hits HR ARHR Cob.Cliente
u(A,B) M1 M2 M1 M2 M1 M2 M1 M2
F1 2429 3742 0,081 0,147 0,0385 0,0824 29664 25353
F2 3692 3963 0,124 0,156 0,0605 0,0882 29664 25353
F3 697 1580 0,023 0,062 0,0083 0,0288 29658 25348
F4 1304 2395 0,044 0,094 0,0146 0,0422 29658 25348
F5 3707 4042 0,124 0,159 0,0598 0,0919 29663 25352
F6 2809 3916 0,094 0,154 0,0411 0,0854 29653 25342
F7 3568 4115 0,120 0,162 0,0568 0,0933 29661 25350
F8 2623 3999 0,088 0,157 0,0410 0,0890 29661 25350
Tab. 4.4: Resultado do Hits, HR, ARHR e Cobertura de clientes utilizando as
forma¸c˜oes de base de teste M1 e M2
4.4 Avalia¸c˜oes do Sistema de Recomenda¸c˜ao
Ap´os geradas as recomenda¸c˜oes foram realizadas 2 avalia¸c˜oes de qualidade das
recomenda¸c˜oes: a primeira, baseada em logs e a segunda, com pessoas. O resultado
4.4 Avalia¸c˜oes do Sistema de Recomenda¸c˜ao 39
de cada avalia¸c˜ao ´e uma lista contendo as fun¸c˜oes de utilidade em ordem decrescente
do resultado da m´etrica ARHR.
4.4.1 Avalia¸c˜ao baseada em logs
Na avalia¸c˜ao baseada em logs utilizou-se exclusivamente a base de teste. Utilizando-
se a base de teste M1, para cada fun¸c˜ao de utilidade foram computados o hits, HR,
ARHR e cobertura de clientes com recomenda¸c˜oes, os resultados podem ser vistos
na Tabela 4.4. O pr´oximo passo foi gerar um ranking a partir de uma determinada
m´etrica, no caso, a m´etrica ARHR. Seja r
1
o ranking da qualidade das fun¸c˜oes que ge-
raram as recomenda¸c˜oes na avalia¸c˜ao com log utilizando a m´etrica ARHR, conforme
resultado apresentado na Figura 4.1 tem-se r
1
= F 2, F5, F 7, F6, F8, F1, F4, F3.
Fig. 4.1: Avalia¸c˜ao baseada em Log: ARHR - forma¸c˜ao da base de teste M1
4.4.2 Avalia¸c˜ao com pessoas
Vinte pessoas foram convidades a participar do experimento, sendo 15 pessoas do
grupo GTI da UFAM, dentre eles alunos de gradua¸c˜ao e mestrado, e 5 pessoas com
conhecimento em varejo. Foram selecionados aleatoriamente 120 clientes da base
4.4 Avalia¸c˜oes do Sistema de Recomenda¸c˜ao 40
de treino e as suas 8 respectivas top-10 recomenda¸c˜oes. Cada pessoa teve acesso
ao hist´orico de compras e as recomenda¸c˜oes geradas para 12 clientes diferentes. As
recomenda¸c˜oes foram apresentadas em ordem crescente do c´odigo do item e sendo
a uni˜ao das oito top-10 recomenda¸c˜oes geradas para cada cliente.
Para o dom´ınio do estudo de caso, que ´e para uma empresa de venda de produtos
no varejo, as recomenda¸c˜oes podem ser apresentadas de forma diferente conforme o
objetivo da avalia¸c˜ao. Dois exemplos seriam:
1. Existˆencia de muitos algoritmos de recomenda¸c˜ao e necessidade de identificar
os melhores. Situa¸c˜ao t´ıpica quando se est´a implantado um sistema de re-
comenda¸c˜ao e uma avalia¸c˜ao inicial ser´a realizada. Neste caso, o ideal ´e que
as recomenda¸c˜oes sejam apresentadas misturadas para que o avaliador n˜ao
saiba qual t´ecnica est´a avaliando e concentre-se nas recomenda¸c˜oes, n˜ao em
comparar qual t´ecnica ´e melhor ou pior.
2. Dois ou trˆes algoritmos com resultados muito pr´oximos. Quando se est´a em
uma fase de refinamento do sistema de recomenda¸c˜ao, o total conhecimento dos
avaliadores quanto a qual algoritmo est´a sendo avaliado dever´a ajudar na ob-
ten¸c˜ao de avalia¸c˜oes onde as pess oas j´a apontam, atrav´es de uma compara¸c˜ao
expl´ıcita dos resultados, qual a melhor t´ecnica na percep¸c˜ao das pe ssoas.
Neste estudo de caso, as recomenda¸c˜oes forma apresentadas misturadas. Cada
produto recomendado foi avaliado indicando-se o grau de relevˆancia, se muito rele-
vante (nota 3), relevante (nota 2), pouco relevante (nota 1) ou n˜ao relevante (nota
0). Cada cliente foi avaliado por 3 pessoas, sendo considerada a avalia¸c˜ao da terceira
pessoa somente na ocorrˆencia de divergˆencia entre o primeiro e o segundo avaliador.
Para calcular o hits,HR e ARHR f oram consideradas as notas 3 e 2 como relevantes
e as notas 1 e 0 como n˜ao relevantes, o resultado pode ser visto na Tabela 4.5.
4.4 Avalia¸c˜oes do Sistema de Recomenda¸c˜ao 41
Seja r
2
o ranking da qualidade das fun¸c˜oes que geraram as recomenda¸c˜oes na
avalia¸c˜ao com pessoas, utilizando a m´etrica ARHR, conforme resultado apresentado
na Figura 4.2, tem-se:
r
2
= F 8, F4, F 6, F1, F3, F7, F5, F2
u(A,B) Hits HR ARHR
F1 117 0,975 2,0248
F2 114 0,950 1,3992
F3 117 0,975 1,8573
F4 119 0,991 2,0934
F5 118 0,983 1,5004
F6 119 0,991 2,1131
F7 119 0,991 1,7760
F8 119 0,991 2,1450
Tab. 4.5: Resultado da avalia¸c˜ao com Pessoas: Hits, HR e ARHR
Fig. 4.2: ARHR - Avalia¸c˜ao com Pessoas
4.5 Identifica¸c˜ao de Ru´ıdos e filtragem do log 42
4.5 Identifica¸c˜ao de Ru´ıdos e filtragem do log
Conforme pode ser visto na Tabela 4.6, o resultado da avalia¸c˜ao baseada em
log (r
1
) e o resultado da avalia¸c˜ao com pessoas (r
2
) s˜ao praticamente opostos, as
recomenda¸c˜oes geradas com as fun¸c˜oes de utilidade F2, F5 e F7 classificadas na
avalia¸c˜ao baseada em log como primeira, segunda e terceira melhores fun¸c˜oes foram
a oitava, s´etima e sexta na avalia¸c˜ao com pessoas.
Neste caso a avalia¸c˜ao baseada em log n˜ao foi suficiente para indicar de forma
correta qual a fun¸c˜ao de utilidade que gerou de fato as melhores recomenda¸c˜oes.
Lista 1 2 3 4 5 6 7 8
r
1
(Aval. baseada em log) F2 F5 F7 F6 F8 F1 F4 F3
r
2
(Aval. com pessoas) F8 F6 F4 F1 F3 F7 F5 F2
Tab. 4.6: Resultado das avalia¸c˜oes baseadas em logs e pessoas
4.5.1 Filtro dos populares do top-N
Atrav´es da observa¸c˜ao das recomenda¸c˜oes n˜ao-personalizadas geradas pelo algo-
ritmo e das avalia¸c˜oes com pessoas, identificou-se que os itens populares diminuem
a qualidade da recomenda¸c˜ao. Este problema ficou mais evidente por tratar-se de
um log com produtos diversificados, onde existem transa¸c˜oes de vendas de produtos
de diversas categorias diferentes.
Para confirmar se realmente os produtos populares eram os geradores do falso
positivo, realizou-se um novo experimento filtrando do top-N os produtos populares.
Este experimento foi conduzido de forma similar ao experimento baseado em log.
Como resultado obteve-se a lista r
3
= F 8, F6, F1, F4, F7, F5, F3, F2, que ´e o ran-
king da qualidade das fun¸c˜oes que geraram as recomenda¸c˜oes na avalia¸c˜ao com log
excluindo os populares do top-N, conforme valores da m´etrica ARHR apresentados
na Figura 4.3.
4.5 Identifica¸c˜ao de Ru´ıdos e filtragem do log 43
Fig. 4.3: Resultado da avalia¸c˜ao baseada em log: ARHR - filtro dos populares do
top-N
Lista 1 2 3 4 5 6 7 8
r
2
(Aval. com pessoas) F8 F6 F4 F1 F3 F7 F5 F2
r
3
(Aval. com filtro dos populares do top-N) F8 F6 F1 F4 F7 F5 F3 F2
Tab. 4.7: Identifi¸cao dos ru´ıdos
4.5.2 Filtro dos populares da base de treino
Para confirmarmos que um tratamento no log reduziria a distˆancia entre as
avalia¸c˜oes baseada em log e avalia¸c˜oes com pessoas, realizamos outro experimento,
agora retirando os itens populares antes da gera¸c˜ao das recomenda¸c˜oes. As ava-
lia¸c˜oes foram realizadas baseada em log e com pessoas, como j´a existe uma base das
avalia¸c˜oes com pessoas, neste se gundo experimento as pessoas avaliaram somente as
recomenda¸c˜oes que n˜ao tinham sido avaliadas anteriormente, sendo assim reduzido
o esfor¸co de execu¸c˜ao da avalia¸c˜ao. Nas Tabelas 4.8 e 4.9 s˜ao apresentamos os
resultados dos valores de Hits, HR e ARHR obtidos nas avalia¸c˜oes baseadas em logs
e com pessoas respectivamente. Nas Figuras 4.4 e 4.5 ´e poss´ıvel visualizar mais
claramente o ranking das recomenda¸c˜oes utilizando as diversas fun¸c˜oes de utilidade.
Desta forma tem-se como resultado as listas, r
4
que ´e o ranking da avalia¸c˜ao baseada
4.6 Compara¸c˜ao das avalia¸c˜oes 44
em log e r
5
qu´e o ranking da avalia¸c˜ao com pessoas.
u(A,B) Hits HR ARHR Cob ertura
F1 796 0,0323 0,0143 24607
F2 957 0,0388 0,0174 24607
F3 627 0,0254 0,0106 24602
F4 700 0,0284 0,0111 24602
F5 943 0,0383 0,0170 24605
F6 844 0,0343 0,0142 24597
F7 920 0,0373 0,0166 24603
F8 831 0,0337 0,0146 24605
Tab. 4.8: Avalia¸c˜ao Baseada em Log:Hits, HR, ARHR e Cobe rtura de clientes -
Base Treino com Filtro dos Populares
u(A,B) Hits HR ARHR
F1 107 0,8916 1,8752
F2 107 0,8916 1,8616
F3 107 0,8916 1,8298
F4 107 0,8916 1,8599
F5 107 0,8916 1,8818
F6 107 0,8916 1,9087
F7 107 0,8916 1,9253
F8 107 0,8916 1,9125
Tab. 4.9: Avalia¸c˜ao com pessoas:Hits, HR e ARHR - Base Treino com Filtro dos
Populares
4.6 Compara¸c˜ao das avalia¸c˜oes
Para medir a distˆancia entre as avalia¸c˜oes utilizou-se a m´etrica proposta por
Kendall. Conforme detalhado no Cap´ıtulo 3, esta m´etrica conta o n´umero de pares
divergentes nas duas listas e quanto maior a distˆancia menor ´e a similaridade entre
as listas. Na Tabela 4.11 ´e apresentado o c´alculo da distˆancia de Kendall entre as
4.6 Compara¸c˜ao das avalia¸c˜oes 45
Fig. 4.4: Resultado da avalia¸c˜ao baseada em log: ARHR - base treino com filtro dos
populares
Lista 1 2 3 4 5 6 7 8
r
4
(Aval. baseada em log) F2 F5 F7 F8 F1 F6 F4 F3
r
5
(Aval. com pessoas) F7 F8 F6 F5 F1 F2 F4 F3
Tab. 4.10: Filtro dos populares
seguintes listas: r
1
e r
2
, que representam o resultado da avalia¸c˜ao baseada em log
e avalia¸c˜ao com pessoas; r
3
e r
2
, que s˜ao os resultados das avalia¸c˜oes com filtro
dos populares do top-N e avalia¸c˜oes com pessoas; e por fim r
4
e r
5
, que foram as
avalia¸c˜oes baseadas em log e com pessoas cujas recomenda¸c˜oes foram geradas sobre
o log ja’ com o filtro dos populares.
A maior distˆancia ´e entre as listas r
1
e r
2
.
´
E a distˆancia mais pr´oxima de 1,
indicando listas na ordem praticamente oposta. Esta distˆancia de 0, 7142 ´e uma
forte evidˆencia de que realizar avalia¸c˜oes somente com logs pode levar a resultados
errˆoneos, como os obtidos neste estudo de caso. Ap´os avaliar o log, houve a suspeita
de que os produtos populares eram os principais responsaveis pela distˆancia entre
as avalia¸c˜oes. Ent˜ao, filtrou-se os populares do top-N e fez-se uma nova avalia¸c˜ao
baseada em log com o objetivo de identificar se realmente estes produtos estavam
4.7 Alguns Resultados da Aplica¸c˜ao 46
Fig. 4.5: Resultado da avalia¸c˜ao com pessoas: ARHR - base treino com filtro dos
populares
gerando o falso positivo. Calculou-se a distˆancia entre esta ´ultima avalia¸c˜ao realizada
com log e a avalia¸c˜ao originalmente feita com pessoas e obteve-se listas bastante
similares com distˆancia de Kendall igual a 0, 1078. Desta forma ficou claro n˜ao
somente o qu˜ao distante da avalia¸c˜ao com pessoas est´a a avalia¸c˜ao com log, mas
tamb´em que a recomenda¸c˜ao de produtos populares, na opini˜ao das pessoas, n˜ao
´e relevante. Por fim, as recomenda¸c˜oes foram geradas ap´os tratamento do log e a
distˆancia entre os resultados da avalia¸c˜ao baseada em log e com pessoas de fato
reduziu consideravelmente de 0, 7142 para 0, 1875.
4.7 Alguns Resultados da Aplica¸c˜ao
Nesta sess˜ao apresentaremos alguns resultados da implementa¸c˜ao da aplica¸c˜ao e
que podem ser fonte de estudo em futuros trabalhos.
4.7 Alguns Resultados da Aplica¸c˜ao 47
Pares (r
1
, r
2
) (r
3
, r
2
) (r
4
, r
5
)
1,2 1 1
1,3
1,4 1 1
1,5 1
1,6 1
1,7 1
1,8
2,3 1
2,4 1
2,5 1 1
2,6 1 1
2,7 1 1
2,8 1 1
3,4
3,5 1 1
3,6
3,7 1 1
3,8
4,5 1
4,6
4,7 1
4,8
5,6 1 1
5,7 1 1
5,8 1 1
6,7 1
6,8 1
7,8 1
Kendall 0,7142 0,1071 0,1875
Tab. 4.11: C´alculo da distˆancia de Kendall
4.7 Alguns Resultados da Aplica¸c˜ao 48
4.7.1 Recomenda¸c˜ao N˜ao-Personalizada
Atrav´es da implementa¸c˜ao do Sistema de Recomenda¸c˜ao N˜ao-Personalizado ob-
servamos que o algoritmo consegue identificar:
• Itens com caracter´ısticas similares. Caracter´ısticas como marca (ver Figura 4.7.1),
cor (ver Figura 4.7), dimens˜oes (ver Figura 4.8) e compatibilidade (ver Fi-
gura 4.9) s˜ao relacionadas pelo pr´oprio hist´orico de compras.
• Itens complementares. Com um grande volume de hist´orico de transa¸c˜oes, o
algoritmo mostra resultados muito bons de vendas adicionais n˜ao personaliza-
das.
• Itens da mesma linha de pre¸co. O hist´orico tamb´em evidˆencia o comporta-
mento de Clientes que compram produtos da linha baixa, m´edia ou alta e
recomenda novos produtos na mesma linha de pre¸co.
4.7.2 Produtos n˜ao-similares
Uma das caracter´ısticas do log de transa¸c˜oes utilizado neste estudo de caso ´e a
diversidade. Os experimentos encontrados na literatura s˜ao em sua grande maioria
realizados com grupos de produtos espec´ıficos como CDs, DVDs e Livros. Pode-se
conceituar produtos similares como produtos que possuem as mesmas caracter´ısticas
b´asicas de funcionamento e a diferen¸ca entre eles est´a em atributos visuais (ex.cor,
dimens˜ao,etc), performance ou funcionalidades adicionais. Como exemplo destes
tipos de produtos temos, geladeira, liquidificador, TV e muitos outros. Produtos n˜ao
similares s˜ao produtos ´unicos, sendo necess´ario especificar o produto para identificar
as suas caracter´ısticas b´asicas (ex. Livro, CD, DVD,etc).
Com base nesta classifica¸c˜ao dos produtos foi poss´ıvel observar algumas rela¸c˜oes
entre a acur´acia (avalia¸c˜ao baseada em log) e a satisfa¸c˜ao (avalia¸c˜ao com pessoas).
4.7 Alguns Resultados da Aplica¸c˜ao 49
Fig. 4.6: Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Marca
Fig. 4.7: Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Cor
Fig. 4.8: Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Dimens˜ao
Fig. 4.9: Recomenda¸c˜ao n˜ao-personalizada: Exemplo - Compatibilidade
4.7 Alguns Resultados da Aplica¸c˜ao 50
Fig. 4.10: Gr´afico de acur´acia X satisfa¸c˜ao por categoria de produtos recomendados
Cada quadrante apresentado na Figura 4.10 ´e detalhado a seguir:
Alta Acur´aria e Alta Satisfa¸c˜ao: Em produtos classificados como similares,
quando recomenda-se produtos relacionados ao hist´orico de compras do cliente e
pertencentes a outra categoria (ex. o cliente comprou um criado mudo e o sistema
recomenda um abajour), em geral a acur´aria e satisfa¸c˜ao coincidem, sendo ambas
mais elevadas. J´a quando tratam-se de produtos n˜ao-similares, a acur´aria e a sa-
tisfa¸c˜ao s˜ao elevadas quando recomenda-se produtos da mesma categoria (ex. se o
cliente est´a consultando um CD ou comprou um CD anteriormete, ele espera que
um outro CD de seu interesse seja recomendado e n˜ao um outro tipo de item.
Alta Acur´acia e Baixa Satisfa¸c˜ao: A recomenda¸c˜ao de produtos populares
certamente produzem altas taxas de acur´acia, mas possuem baixo n´ıvel de satisfa¸c˜ao
e pode comprometer fortemente a credibilidade do sistema de recomenda¸c˜ao.
Baixa Acur´aria e Alta Satisfa¸c˜ao: Certamente, outra forma de alcan¸car um
n´ıvel elevado de satisfa¸c˜ao do cliente ´e recomendando um produto novo relacionado
aos produtos comprados anteriormente pelo cliente. Este tipo de recomenda¸c˜ao ´e
poss´ıvel utilizando outras t´ecnicas de recomenda¸c˜ao, como a t´ecnica baseada em
conte´udo onde as caracter´ısticas do produto podem ser exploradas para gera¸c˜ao de
recomenda¸c˜ao de novos produtos.
4.7 Alguns Resultados da Aplica¸c˜ao 51
Baixa Acur´aria e Baixa Satisfa¸c˜ao: Em produtos classificados como simi-
lares, a recomenda¸c˜ao de produtos pertencentes a mesma categoria dos produtos
comprados anteriormente, para muitos categorias existentes, possui baixa acur´acia
e n˜ao ´e considerada uma recomenda¸c˜ao ´util pelas pessoas. (ex. recomendar um novo
modelo de lavadoura de roupa a um cliente que acabou de comprar este produto).
O inverso ocorre com itens n˜ao-similares onde a baixa Acur´aria e baixa Satisfa¸c˜ao
ocorrem quando s˜ao recomendados itens de outras categorias.
Cap´ıtulo 5
Conclus˜oes e Trabalhos Futuros
Este trabalho realizou estudos sobre como os Sistemas de Recomenda¸c˜ao s˜ao
avaliados. Identificou-se que a grande maioria dos experimentos encontrados na
literatura foram avaliados exclusivamente com base em logs, principalmente pela
praticidade de avaliar m´ultiplas t´ecnicas simultaneamente [22, 18, 6]. Tamb´em
verificou-se que existem estudos questionando se este tipo de avalia¸c˜ao ´e ou n˜ao
confi´avel, considerando que as avalia¸c˜oes com pessoas conseguem captar melhor a
rea¸c˜ao `a recomenda¸c˜ao e que um sistema com alta acur´acia pode em algumas si-
tua¸c˜oes levar a resultados errˆoneos.
Com base nesta pesquisa, a proposta desta disserta¸c˜ao foi apresentar uma forma
de validar as avalia¸c˜oes baseadas em logs tornando o uso do log confi´avel em ava-
lia¸c˜oes de sistemas de recomenda¸c˜ao colaborativos. Foi realizado um estudo de caso
partindo do princ´ıpio que algumas entradas do log de transa¸c˜oes poderiam ocasio-
nar uma distˆancia consider´avel entre a simples verifica¸c˜ao da acur´acia de predi¸c˜ao
do sistema de recomenda¸c˜ao e a real percep¸c˜ao de qualidade das recomenda¸c˜oes
identificadas por pessoas.
Neste estudo de caso verificou-se uma grande disparidade entre os resultados
das avalia¸c˜oes baseadas em log e avalia¸c˜oes com pessoas. Tal disparidade ocorreu
52
5.1 Trabalhos Futuros 53
porque a recomenda¸c˜ao de produtos populares, que o cliente compraria independente
de haver uma recomenda¸c˜ao, produziu bons resultados na avalia¸c˜ao baseada em logs
e o mesmo n˜ao ocorreu na avalia¸c˜ao com pessoas, onde os resultados das avalia¸c˜oes
foram ruins. Esta e vidˆencia confirma a suspeita levantada por alguns autores [13,
23, 15] de que sistemas de recomenda¸c˜ao com alta acur´acia, conforme as m´etricas
existentes, podem n˜ao gerar as recomenda¸c˜oes mais ´uteis para os clientes
Pode-se concluir deste trabalho que n˜ao ´e suficiente realizar avalia¸c˜oes de Siste-
mas de Recomenda¸c˜ao somente baseadas em logs de transa¸c˜oes. Conclui-se tamb´em
que ´e poss´ıvel realizar avalia¸c˜oes baseadas em log obtendo resultados pr´oximos das
avalia¸c˜oes realizadas com pessoas desde que sejam identificados e filtrados ru´ıdos do
log que p ossam ser os principais respons´aveis pelas divergˆencias entre as avalia¸c˜oes.
5.1 Trabalhos Futuros
Nesta sess˜ao s˜ao apresentadas sugest˜oes de trabalhos futuros que poder˜ao dar
continuidade aos experimentos realizados nesta disserta¸c˜ao.
Sugere-se o estudo de uma m´etrica que penalize a recomenda¸c˜ao de produtos
populares, ocorrˆencia comum em logs de transa¸c˜oes de empresas varejistas, n˜ao
havendo com isso a necessidade de filtragem do log. Seria interessante tamb´em
estudos mais aprofundados de avalia¸c˜oes de recomenda¸c˜ao n˜ao-personalizada a partir
da consulta de um produto categorizado como similar e n˜ao-similar.
Referˆencias Bibliogr´aficas
[1] Brendan Kitts, David Freed, Martin Vrieze. Cross-sell: A Fast Promotion-
Tunable Customer-Item Recommendation Method Based on Conditionally In-
dependet Probabilities. KDD, 2000, Boston, USA.
[2] Cai-Nicolas Ziegler, Lars schmidt-Thieme, and Gerorge Lausen. Exploiting
Semantic Product Descriptions for Recommender Systems. In Proceedings of the
2nd ACM SIGIR Semantic Web and Information Retrieval Workshop, Sheffie ld,
UK, July 2004.
[3] Cai-Nicolas Ziegler, Gerorge Lausen, and Lars schmidt-Thieme. Taxonomy-
driven Computation of Product Recommendations. In Proceedings of the
2004 ACM CIKM - Conference on Information and Knowledge Management,
Washington, D.C., USA, November 2004.
[4] Cai-Nicolas Ziegler, Sean M. McNee, Joseph A. Konstan, and Gerorge Lausen.
Improving Reommendation Lists Through Topic Diversification. In Proceedings
of WWW 2005, Chiba, Japan.
[5] Cosley D., Lam, S.K., Albert, I.,Konstan, J.A., and Riedl,J. Is Seeing Belie-
ving? How Recommender Interfaces Affect User’s Opinion. In CHI, Florida,
USA, 2003.
54
REFER
ˆ
ENCIAS BIBLIOGR
´
AFICAS 55
[6] Eui-Hong Han and George Karypis. Feature-Based Recommendation System.
CIKM, november 2005.
[7] G. Adomavicius and A. Tuzhilin. Multidimensional Recommender System:
a data werehousing approach. In Proceedings of the Second International
Workshop on Eletronic Commerce. Lecture Notes in Computer Science, vol
2232, Springer 2001.
[8] G. Adomavicius and A. Tuzhilin. Toward the Next Generation of Recommen-
der Systems: A Survey of the State-of-the-Art and Possible Extensions. IEEE
Transactions on Knowledge and Data Engineering, vol.17, NO.6, June 2005.
[9] G. Adomavicius, R. Sankaranarayanan, S. Sen, and A. Tuzhilin. Incorpora-
ting Contextual Information in Recommender System Using a Multidimensio-
nal Approach. In ACM Transactions on Information Systems (TOIS), Volume
23 Issue 1 , january 2005.
[10] G. Salton. Automatic Text Processing: The Transformation Analysis and Re-
trieval of Information by Computer. Addison-Wesley, 1989.
[11] George Karypis. Evaluation of Item-Based Top-N Recommendation Algorithms.
CIKM, 2001.
[12] Goldberg, D., Nichols, D., Oki, B . M., and Terry, D. Using Collaborative
Filtering to Weave an Information Tapestry. Communications of ACM, 1992.
[13] Hayes, C., Massa, P., Avesani, P., and Cunningham, P. An on-line evaluation
framework for recommender systems. In Workshop on Recommendation and
Personalization Systems, Springer Verlag, 2002. Lecture Notes in Computer
Science, vol 2232, Springer 2001.
REFER
ˆ
ENCIAS BIBLIOGR
´
AFICAS 56
[14] J. B. Schafer, J.A.Konstan, and J. Riedl. E-commerce Recommendation Ap-
plications. Data Mining and Knowledge Discovery, vol.5, pages 115–153,2001.
[15] Jonathan L. Herlocker and Joseph A. Konstan, Loren G. Terveen, and John
T. Riedl. Evaluating Collaborative Filtering Recommender Systems. In ACM
Transactions on Information Systems (TOIS), Volume 22 Issue 1, pages 5-53,
january 2004.
[16] Kendall, M. Rank Correlation Methods. Charles Griffin and Company Limited,
(1948)
[17] Linden, G., Smith, B., and York, J. Amazon.com Recommendations: Item-to-
Item Collaborative Filtering. IEEE Internet Computing, january 2003.
[18] Mukund Deshpande and George Karypis. Item-Based Top-N Recommendation
Algorithms. TOIS, january 2004.
[19] Nichols, D. Impliciting Rating and Filtering. In Proceedings of the Fifth DE-
LOS Workshop on Filtering and Collaborative Filtering, page 31–36. Budabeste,
1998.
[20] Rashmi R. Sinha and Kirsten Swearingen. Comparing Recommendations Made
by Online Systems and Friends. DELOS Workshop: Personalisation and Re-
commender Systems in Digital Libraries 2001.
[21] Sarwar, B., Karypis,G., Konstan J., and Riedl, J. Analysis of Recommendation
Algorithms for e-commerce. In Proceddings of the 2nd ACM Conference on
Electronic Commerce, pages 158–167, Minneapolis, USA, 2000.
[22] Sarwar, B., Karypis,G., Konstan J., and Riedl, J. Item-Based Collaborative
Filtering Recommendation algorithms. In WWW10, may, Hong Kong 2001.
REFER
ˆ
ENCIAS BIBLIOGR
´
AFICAS 57
[23] Sean M. Mcnee, J.A.Konstan, and J. Riedl. Being Accurate in Not Enough. How
Accuracy Metrics have hurt Recommeder Systems. CHI’06 - Conference on
Human Factors in Computing Systems , pages 1097 - 1101, Montr´eal, Qu´ebec,
Canada, 2006.
[24] Z. Huang, W. Chung, and H. Chen. A Graph Model for E-Commerce Recom-
mender System. Journal of the American Society for Information Science and
Technology, pages 259-274, 2004.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
