Item-Based-ADP: Análise e Melhoramento do Algoritmo de

UNIVERSIDADE FEDERAL DE GOIÁS

INSTITUTO DE INFORMÁTICA

CIÊNCIAS DA COMPUTAÇÃO

EVERTON LIMA ALEIXO

Item-Based-ADP: Análise eMelhoramento do Algoritmo de

Filtragem Colaborativa Item-based

Goiânia2014

UNIVERSIDADE FEDERAL DE GOIÁS

INSTITUTO DE INFORMÁTICA

CIÊNCIAS DA COMPUTAÇÃO

AUTORIZAÇÃO PARA PUBLICAÇÃO DE DISSERTAÇÃO

EM FORMATO ELETRÔNICO

Na qualidade de titular dos direitos de autor, AUTORIZO o Instituto de Infor-mática da Universidade Federal de Goiás – UFG a reproduzir, inclusive em outro formatoou mídia e através de armazenamento permanente ou temporário, bem como a publicar narede mundial de computadores (Internet) e na biblioteca virtual da UFG, entendendo-seos termos “reproduzir” e “publicar” conforme definições dos incisos VI e I, respectiva-mente, do artigo 5o da Lei no 9610/98 de 10/02/1998, a obra abaixo especificada, sem queme seja devido pagamento a título de direitos autorais, desde que a reprodução e/ou publi-cação tenham a finalidade exclusiva de uso por quem a consulta, e a título de divulgaçãoda produção acadêmica gerada pela Universidade, a partir desta data.

Título: Item-Based-ADP: Análise e Melhoramento do Algoritmo de Filtragem Colabo-rativa Item-based

Autor(a): Everton Lima Aleixo

Goiânia, 02 de Setembro de 2014.

Everton Lima Aleixo – Autor

Thierson Couto Rosa – Orientador

EVERTON LIMA ALEIXO



Dissertação apresentada ao Programa de Pós–Graduação doInstituto de Informática da Universidade Federal de Goiás,como requisito parcial para obtenção do título de Mestre emMestrado em Ciências da Computação.

Área de concentração: Ciência da Computação.

Orientador: Prof. Thierson Couto Rosa

Goiânia2014

EVERTON LIMA ALEIXO



Dissertação defendida no Programa de Pós–Graduação do Instituto deInformática da Universidade Federal de Goiás como requisito parcialpara obtenção do título de Mestre em Mestrado em Ciências da Compu-tação, aprovada em 02 de Setembro de 2014, pela Banca Examinadoraconstituída pelos professores:

Prof. Thierson Couto RosaInstituto de Informática – UFG

Presidente da Banca

Prof. Celso Gonçalves Camilo JuniorInstituto de Informática – UFG

Prof. Denilson Alves PereiraDepartamento de Ciências da Computação – UFLA

Todos os direitos reservados. É proibida a reprodução total ou parcial dotrabalho sem autorização da universidade, do autor e do orientador(a).

Everton Lima Aleixo

Formado em Ciências da Computação, pelo Instituto de Informática, Univer-sidade Federal de Goiás (2008-2012). Monografia na área de monitoramentoe gerenciamento de sistemas distribuídos, tendo como estudo de caso umaaplicação GIS. Mestrando em Ciências da Computação , pelo Instituto de In-formática, Universidade Federal de Goiás (2012).Participou da maratona de programação nos anos de 2009 e 2010, ficandoem terceiro e quarto lugares respectivamente. Trabalhou como monitor nasdisciplinas de Programação e Estrutura de Dados na UFG, pelo Institutode Informática de 2009 à 2011. Trabalhou no projeto SIGMA (Sistema deInfomração Geográfica para Monitoramento Ambiental) de 2010 a 2012.Trabalha na empresa GoGEO desde 2013 como desenvolvedor e arquitetoJava. Possui bom conhecimento em sistemas Linux e proficiência com alinguagem de programação Java.

Dedico este trabalho à minha família: Pai José Lima Aleixo, Mãe Guaraciara

Goreti Lima, Irmão Emerson Lima Aleixo, grande amiga e companheira Barbara Car-

neiro Braga, ao meu Orientador Prof. Dr. Thierson Couto Rosa e a todos os meus amigos

e colegas. Em especial os amigos de mestrado Adriano Ferraz, Edjalma Queiroz da Silva

e Luiz Mario Lustosa Pascoal.

Agradecimentos

Antes de tudo gostaria de agradecer minha família, Pai José Lima Aleixo,Mãe Guaraciara Goreti Lima e Irmão Emerson Lima Aleixo, que sempre estiveram meapoiando na vida, principalmente nos momentos difíceis em que tive que tomar algumadecisão importante na vida. Possuem o meu eterno amor, gratidão e admiração.

Ao meu orientador Dr. Thierson Couto Rosa, ao qual tenho uma imensa gratidãoe admiração, por sua excelente orientação e pela oportunidade que me concedeu a realizareste trabalho.

Gostaria de agradecer aos meus amigos que trabalham comigo na goGeo porestarem sempre prontos a me ajudar nos momentos que precisei, todos colaboraram parao meu crescimento nesta etápa. Em especial gostaria de agradecer ao Anderson RogérioCunha e Welder Batista de Oliveira por me ajudar com a execução dos experimentos, aoSávio Salvarino Teles de Oliveira e Marcelo de Castro Cardoso pelas dicas e discuções eao Prof. Dr. Vagner José do Sacramento Rodrigues por toda a ajuda.

A todos os meus amigos, colegas e primos. Em especial a Barbara CarneiroBraga, que me acompanhou durante quase toda minha jornada acadêmica, por todos osmomentos divertidos que passamos juntos e também os momentos difíceis como noitesviradas! Também a Priscilla Rodrigues de Ferreira que quando eu estava perdido memostrou o cominho de volta, me ajudando a concluir mais esta etapa. Ainda gostariade agradecer a um grupo seleto de amigos ("Os sem pudores") que conheço a poucotempo mas que têm a minha mais profunda e sincera consideração, Alann Lopes de PaulaBriguiza, Guilherme França Reges, Jordana Chagas Nascimento e Nathália Silva Bueno.

Sem vocês a minha jornada não teria sido a mesma, muito obrigado! Espero queeu possa estar ao lado de vocês para sempre. Nunca esquecerei nenhum de vocês!

... pra quem tem pensamento forte, o impossível é só questão de opiniãoe disso os loucos sabem ...

Só os loucos sabem,Charlie Brown Jr.

Resumo

Aleixo, Everton Lima. Item-Based-ADP: Análise e Melhoramento do Algo-ritmo de Filtragem Colaborativa Item-based. Goiânia, 2014. 96p. Dissertaçãode Mestrado. Ciências da computação, Instituto de Informática, Universidade Fe-deral de Goiás.

Algoritmos baseados em memória são os mais populares entre os algoritmos de filtragemcolaborativa. Eles usam como entrada uma tabela contendo as avaliações feitas pelosusuários aos itens, conhecida como matriz de avaliações. Eles predizem a avaliação dadapor um usuário a a um item i, computando a similaridade de avaliações entre a e outrosusuários ou entre i e outros itens. No primeiro caso, os algoritmos baseados em memóriasão classificados como algoritmos baseados em usuários (User-based) e no segundo casosão rotulados como algoritmos baseados em itens (Item-Based). A predição é computadausando as avaliações dos k usuários (ou itens) mais similares, também conhecidos comovizinhos. Algoritmos baseados em memória são simples de entender e implementar.Normalmente produzem boas recomendações e são menos sensíveis a mudança nosdados. Entretanto, para obter os vizinhos mais similares para a predição, eles necessitamprocessar todos os dados da matriz, o que é um sério problema de escalabilidade. Elestambém são sensíveis a densidade dos dados. Neste trabalho, nós propomos um algoritmoeficiente e eficaz baseado em itens que visa diminuir a sensibilidade dos algoritmosbaseados em memória para ambos os problemas acima referidos. Esse algoritmo émais rápido (quase 50%) do que o algoritmo baseado em itens tradicional, mantendoo mesmo nível de acurácia. Entretanto, em ambientes onde existem muitos dados parapredizer e poucos para treinar o algoritmo, a acurácia do algoritmo proposto superasignificativamente a do algoritmo tradicional baseado em itens. Nossa abordagem podeainda ser facilmente adaptada para ser utilizada como o algoritmo baseado em usuários.

Palavras–chave

Sistemas de Recomendação, Acurácia, Filtragem Colaborativa, Baseado emMemória

Abstract

Aleixo, Everton Lima. Item-Based-ADP: Analysis and Improvement of Col-laborative Filtering Algorithm Item-based. Goiânia, 2014. 96p. MSc. Disser-tation. Ciências da computação, Instituto de Informática, Universidade Federalde Goiás.

Memory-based algorithms are the most popular among the collaborative filtering algo-rithms. They use as input a table containing ratings given by users to items, known as therating matrix. They predict the rating given by user a to an item i by computing similari-ties of the ratings among users or similarities of the ratings among items. In the first caseMemory-Based algorithms are classified as User-based algorithms and in the second onethey are labeled as Item-based algorithms. The prediction is computed using the ratingsof k most similar users (or items), also know as neighbors. Memory-based algorithms aresimple to understand and to program, usually provide accurate recommendation and areless sensible to data change. However, to obtain the most similar neighbors for a predic-tion they have to process all the data which is a serious scalability problem. Also theyare sensitive to the sparsity of the input. In this work we propose an efficient and effec-tive Item-Based that aims at diminishing the sensibility of the Memory-Based approachto both problems stated above. The algorithm is faster (almost 50%) than the traditionalItem-Based algorithm while maintaining the same level of accuracy. However, in envi-ronments that have much data to predict and few to train the algorithm, the accuracy ofthe proposed algorithm surpass significantly that of the traditional Item-based algorithms.Our approach can also be easily adapted to be used as User-based algorithms.

Keywords

Recommender Systems, Accuracy, Collaborative Filtering, Memory-based

Sumário

Lista de Figuras 11

Lista de Tabelas 14

Lista de Algoritmos 15

1 Introdução 161.1 Objetivos 181.2 Organização 19

2 Embasamento Teórico 202.1 Sistemas de Recomendação 20

2.1.1 Sistemas de Recomendação Baseados em Conhecimento 242.1.2 Sistemas de Recomendação Demográfico 252.1.3 Sistemas de Recomendação Baseados em Conteúdo 272.1.4 Sistemas de Recomendação Baseados em Filtragem Colaborativa 28

2.2 Obtenção de Dados para Sistemas Recomendação 302.2.1 Métodos Explícitos 302.2.2 Métodos Implícitos 32

2.3 Métodos e Métricas de Avaliação em Sistemas de Recomendação 322.4 Trabalhos Relacionados 35

3 Tipos de Filtragem Colaborativa 393.1 Sistemas baseados em modelo 39

3.1.1 Regressão de decomposição em valores singulares (RegSVD) 403.2 Sistemas baseados em memória 41

3.2.1 Métodos Baseados em Usuários 433.2.2 Métodos Baseados em Itens 443.2.3 Medidas de similaridade 463.2.4 Métodos de Predição 51

4 Item-Based-ADP 534.1 Fluxograma 544.2 Algoritmo 58

5 Experimentos 615.1 Configurações dos testes 61

5.1.1 Conjunto de dados 615.1.2 Ambiente de execução 62

5.1.3 Metodologia 625.2 Resultados 64

5.2.1 MovieLens_100k 65Seleção da medida de similaridade 65Seleção do número de vizinhos 66Seleção do limiar Delta (δ) 69Comparação dos algortimos 71Significância estatística 73Análise cada adaptação 73

5.2.2 Netflix_3m1k 75Seleção da medida de similaridade 76Seleção do número de vizinhos 77Seleção do limiar Delta (δ) 80Comparação dos algortimos 81Significância estatística 84Análise cada adaptação 85

6 Conclusão e Trabalhos Futuros 87

Referências Bibliográficas 89

Lista de Figuras

2.1 Taxonomia dos Sistemas de Recomendação. 242.2 Tela do sistema Entree. 262.3 Site Submarino. Exemplificando modo de extração de informação desse

sistema. 31

3.1 Pequeno exemplo de uma instância do User-based. 443.2 Pequeno exemplo de uma instância do Item-based. 45

4.1 Fluxograma do algoritmo Item-Based-ADP. 55

5.1 Exemplo do processo de divisão da matriz de avaliações nas matrizes deteste e treino. 63

5.2 MAE para diversas medidas de similaridade nos algoritmos User-based,Item-based e Item-Based-ADP. 65

5.3 RMSE para diversas medidas de similaridade nos algoritmos User-based,Item-based e Item-Based-ADP. 65

5.4 Tempo de execução para diversas medidas de similaridade nos algoritmosUser-based, Item-based e Item-Based-ADP. 66

5.5 MAE variando-se o número de vizinhos nos três algoritmos baseadosem memória com test ratio de 0,2, utilizando-se as duas medidas desimilaridade previamente selecionadas. 67


5.7 RMSE variando-se o número de vizinhos nos três algoritmos baseadosem memória com test ratio de 0,2, utilizando-se as duas medidas desimilaridade previamente selecionadas. 67

5.8 RMSE variando-se o número de vizinhos nos três algoritmo baseadosem memória com test ratio de 0,9, utilizando-se as duas medidas desimilaridade previamente selecionadas. 68

5.9 Tempo de execução variando-se o número de vizinhos nos tês algoritmosbaseados em memória com test ratio de 0,2, utilizando-se as duas medi-das de similaridade previamente selecionadas. 68


5.11 MAE variando-se o valor de δ no algoritmo IBA com test ratio de 0,2. 695.12 RMSE variando-se o valor de δ no algoritmo IBA com test ratio de 0,2. 69

5.13 Tempo de execução variando-se o valor de δ no algoritmo IBA com testratio de 0,2. 70

5.14 MAE variando-se o valor de δ no algoritmo IBA com test ratio de 0,9. 705.15 RMSE variando-se o valor de δ no algoritmo IBA com test ratio de 0,9. 715.16 Tempo de execução variando-se o valor de δ no algoritmo IBA com test

ratio de 0,9. 715.17 Análise da influência de cada adaptação com test ratio de 0,2, usando-se

correlação de Pearson como medida de similaridade. 745.18 Análise da influência de cada adaptação com test ratio de 0,5, usando-se

correlação de Pearson como medida de similaridade. 745.19 Análise da influência de cada adaptação com test ratio de 0,9, usando-se

correlação de Pearson como medida de similaridade. 745.20 Análise da distribuição de erros para os algoritmos. 755.21 MAE para diversas medidas de similaridade nos algoritmos User-based,

Item-based e Item-Based-ADP. 765.22 RMSE para diversas medidas de similaridade nos algoritmos User-based,

Item-based e Item-Based-ADP. 765.23 Tempo de execução para diversas medidas de similaridade nos algoritmos

User-based, Item-based e Item-Based-ADP. 775.24 MAE variando-se o número de vizinhos nos três algoritmos baseados

em memória com test ratio de 0,2, utilizando-se as duas medidas desimilaridade previamente selecionadas. 78


5.26 RMSE variando-se o número de vizinhos nos três algoritmos baseadosem memória com test ratio de 0,2, utilizando-se as duas medidas desimilaridade previamente selecionadas. 78

5.27 RMSE variando-se o número de vizinhos nos três algoritmo baseadosem memória com test ratio de 0,9, utilizando-se as duas medidas desimilaridade previamente selecionadas. 79



5.30 MAE variando-se o valor de δ no algoritmo IBA com test ratio de 0,2. 805.31 RMSE variando-se o valor de δ no algoritmo IBA com test ratio de 0,2. 815.32 Tempo de execução variando-se o valor de δ no algoritmo IBA com test

ratio de 0,2. 815.33 MAE variando-se o valor de δ no algoritmo IBA com test ratio de 0,9. 825.34 RMSE variando-se o valor de δ no algoritmo IBA com test ratio de 0,9. 825.35 Tempo de execução variando-se o valor de δ no algoritmo IBA com test

ratio de 0,9. 825.36 Análise da influência de cada adaptação com test ratio de 0,2, usando-se

o cosseno como medida de similaridade. 85

5.37 Análise da influência de cada adaptação com test ratio de 0,5, usando-seo cosseno como medida de similaridade. 86

5.38 Análise da influência de cada adaptação com test ratio de 0,9, usando-seo cosseno como medida de similaridade. 86

Lista de Tabelas

2.1 Exemplo de vetor demográfico para um usuário X. 272.2 Exemplo de vetor demográfico para um usuário X. 292.3 Análise assintótica de algoritmos de filtragem colaborativa baseada em

[18]. Na tabela m representa o número de usuários, n o número de itens, α

é a quantidade de grupos formados e o k é a quantidade de propriedadesselecionadas nos algoritmos SVDs. 36

4.1 Exemplo para mostrar problema no uso do coeficiente da correlação dePearson como medida de similaridade. 53

5.1 Análise dos algoritmos variando-se o test ratio com correlação dePearson como medida de similaridade. 72

5.2 Análise dos algoritmos variando-se o test ratio com log-Likelihoodcomo medida de similaridade. 72

5.3 Análise dos algoritmos variando-se o test ratio com a medida desimilaridade que mais favorece a acurácia. 83

5.4 Análise dos algoritmos variando-se o test ratio com log-Likelihoodcomo medida de similaridade. 83

Lista de Algoritmos

3.1 Construção do modelo RegSVD. 413.2 Algoritmos baseados em memória em alto nível. 42

4.1 Item-Based-ADP 59

CAPÍTULO 1Introdução

Mesmo antes do surgimento dos sistemas computacionais, o processo de tomadade decisão já se apresentava como um grande problema. Este problema é ocasionadodevido à grande quantidade de opções a serem escolhidas e, em geral, à incapacidade detestarmos todas elas a fim de selecionarmos a melhor. A tomada de decisão é aplicadaem diversas áreas, desde as que não causam grandes impactos até as que podem afetarcompletamente a vida de uma pessoa.

Como exemplo de área onde a tomada de decisão gera grande impacto, temos agestão empresarial, na qual uma decisão tomada erroneamente pode levar a falência daempresa e causar inúmeros casos de desemprego. Porém, áreas de menor impacto tambémfazem parte do nosso cotidiano. A escolha de um filme para assistir, por exemplo, implicadiretamente na satisfação de uma pessoa, o que a torna uma decisão importante a sertomada.

Um agravante para esse problema é o crescente volume de dados. Quanto maisdados disponíveis, mais opções existem. Atualmente é inviável operar sob o processo detomada de decisão sem o auxílio de um sistema computacional, perante a quantidade dedados existentes na era da informação.

As soluções para este problema são diferentes de acordo com o impacto em cadaárea. Goldberg et. al. [30] propõem a primeira solução colaborativa aplicada ao problemade seleção de notícias. Este problema pertence à área de menor impacto, visto que umanotícia tomada como irrelevante para uma pessoa, é simplesmente descartada.

Essa solução colaborativa se mostrou bastante interessante e eficaz. Desde então,essa solução vem sendo bastante utilizada em problemas de recomendação. A solução semostrou tão atraente que ganhou uma área de estudo própria, Filtragem Colaborativa

(FC), que é uma extensão da Recuperação de Informação (RI).Segundo Resnick em [67], pessoas que concordaram com avaliações no passado

são propensas a concordarem novamente no futuro. Essa é a base filosófica da filtragemcolaborativa. Esta pode ser dividida em dois grandes segmentos: baseados em memóriae baseados em modelos. O primeiro não requer qualquer pré-calculo, podendo ser exe-cutado sob demanda, e será descrito detalhadamente na Seção 3.2. Já o segundo, usa os

17

dados históricos dos usuários do sistema para gerar um modelo computacional, utilizadopara produzir as sugestões. Este segundo segmento requer muito poder computacionalpara produzir bons modelos e será descrito detalhadamente na Seção 3.1. Ainda existemas abordagem hibridas, que usufruem das técnicas dos dois segmentos.

A filtragem colaborativa é o tema central do presente trabalho. É realizado umestudo profundo nos sistemas baseados em memória. Esses sistemas podem ser divididosem dois grupos: baseados na similaridade de itens e baseados na similaridade de usuário.No primeiro caso, são usadas as informações dos usuários com preferências semelhantesàs do usuário que receberá a recomendação para gerar esta. Já no segundo, as informaçõesdos itens similares, em termos de avaliações ao item para o qual o sistema deseja realizara predição, são utilizadas para esse fim.

Os sistemas baseados em memória possuem basicamente três fases: 1) calcularsimilaridade; 2) selecionar os mais semelhantes; 3) gerar a predição de um item. Esseprocesso é realizado para algum item que possa ser recomendado a um usuário.

Do primeiro sistema de filtragem colaborativa até os dias atuais, diversos siste-mas e métodos foram propostos na literatura. Esse assunto será discutido no Capítulo 2. Acomparação entre esses sistemas não é uma tarefa trivial, pois um método pode ser melhorque os demais para um dado cenário, enquanto para outros, o mesmo método apresentaum comportamento inferior. Segundo Herlocker, em [35], a maioria dos algoritmos defiltragem colaborativa foram projetados para cenários onde existem muito mais usuáriosdo que itens.

Além da proporção usuários/itens, outro fator que afeta significativamente osresultados de um algoritmo é a quantidade de dados disponíveis, isto é, o somatório daquantidade de itens avaliados por cada usuário dividido pelo produto do total de usuários eo total de itens. Isso é definido como densidade dos dados, conforme mostrado na Equação1-1. Nesta equação, U representa o conjunto de todos os usuários do sistema, I representao conjunto de todos os itens do sistema e Iu representa o conjunto de itens avaliados pelousuário u.

Densidade =∑u∈U |Iu||U| ∗ |I |

(1-1)

Um fator que colaborou para a complicação da comparação entre esses diversossistemas, quando propostos na literatura, foi a falta de uma padronização das medidas deavaliação. Dessa forma, cada algoritmo apresentava seus resultados com um conjunto demétricas diferente dos demais. Essas métricas são selecionadas de acordo com o propósitopara o qual o algoritmo de filtragem colaborativa é projetado. Esses propósitos e asdiversas métricas serão discutidas no Capítulo 2.

Em todos os sistemas, a eficiência e a eficácia são preocupações constantes. Prin-cipalmente nos sistemas baseados memória que precisam realizar suas recomendações

1.1 Objetivos 18

sob demanda. Esses sistemas conseguem responder de forma rápida quando temos pou-cos dados. Porém, à medida que a base de dados aumenta, a geração de recomendaçõestorna-se muito lenta. Tal lentidão não pode ser aceita em sistemas reais, uma vez que umusuário não aguardaria, por exemplo, três minutos para receber uma lista recomendação.Em geral, essas recomendações devem ser feitas em tempo real e com boa qualidade.

A fase que faz com que os sistemas de recomendação baseados em memórialeve mais tempo é a primeira: calcular a similaridade. Isso é devido à necessidade decalcular a similaridade entre todos os pares, e à medida que a base de dados aumenta,tanto a quantidade de pares quanto a complexidade desses pares aumenta. Nos estudosrealizados, foi levantada a hipótese de que muitos pares selecionados como semelhantes,na verdade, são falsos-positivos.

Esses falsos-positivos geram um processamento desnecessário, aumentando otempo de execução e produzindo uma predição inferior. Dessa forma, foram realizadasmelhorias no método baseado na similaridade de itens para demonstrar isso. Foramrealizadas quatro melhorias. Esse novo método foi denominado Item-Based-ADP1.

Devido a esses pontos foram levantadas as seguintes hipóteses:

• Muitos vizinhos são falsos-positivos: muitos pares são considerados vizinhos e naverdade não deveriam ser;• Processamento desnecessário: não seria necessário calcular a similaridade entre os

falsos-positivos, pois não são úteis e esse cálculo é custoso;• Declínio na assertividade da predição: o fato desses pares seremerroneamente

considerados similares faz com que os algoritmos tenham uma predição pior.

Para reduzir esse problema dos falsos-positivos o Item-Based-ADP propõe téc-nicas de melhoramento na seleção de vizinhos. Isso deve reduzir o tempo computacionale melhorar as predições.

1.1 Objetivos

Um dos objetivos deste trabalho é apresentar uma condensação sobre os con-ceitos de sistemas de recomendação, facilitando os estudos para futuros pesquisadoresque venham a investigar esta área. Neste trabalho, é dado ênfase nos três métodos quepossuem maior destaque na literatura. Esses métodos são:

• Método baseado em usuários próximos• Método baseado em itens próximos

1ADP vem de adaptações.

1.2 Organização 19

• Método SVD

Desses três métodos, os dois primeiros pertencem ao segmento baseado emmemória e o último pertence ao outro segmento, baseados em modelo. Serão apresentadosos comportamentos desses métodos em diversos cenários, com diferentes conjuntos deteste.

Dentre as diversas tarefas para as quais um sistema de recomendação pode serprojetado, o trabalho focará uma específica: predizer a avaliação de um usuário para umitem do sistema. Dessa forma, os métodos acima serão avaliados e comparados em funçãodesta tarefa.

A principal contribuição deste trabalho é a criação de um novo algoritmo parasistemas de recomendação baseados em memória. Esse novo algoritmo é uma melhoriarealizada no algoritmo baseado na semelhança de vizinhos, denominado Item-Based-

ADP. Esse novo algoritmo traz duas vantagens em relação ao original:

1. Melhoria na acurácia quando se tem poucos dados para treinamento;2. Redução no tempo de execução em grandes bases de dados (ambientes com muitos

dados para treinamento).

1.2 Organização

Esta dissertação contém mais 5 capítulos, além desta Introdução. No Capítulo2, é apresentado o embasamento teórico sobre sistemas de recomendação e os conceitosnecessários para entender o restante deste trabalho. Ainda no Capítulo 2 é apresentadauma revisão bibliográfica dos algoritmos que buscam melhorias para sistemas de reco-mendação, seja no tempo de execução ou na acurácia. No Capítulo 3, são aprofundadosos estudos sobre os sistemas de recomendação do tipo filtragem colaborativa. No Capítulo4, o algoritmo proposto é devidamente explicado e detalhado. No Capítulo 5, os experi-mentos são apresentados juntamente com os seus resultados e discussões. Por fim, noCapítulo 6, são apresentadas a conclusão e as ideias de trabalhos futuros.

CAPÍTULO 2Embasamento Teórico

Como já apresentado anteriormente, os sistemas de recomendação veem se tor-nando cada vez mais importantes nas aplicações modernas. Neste capítulo, são apresenta-dos os conceitos básicos necessários para o entendimento do restante deste trabalho. Alémdisso, ainda é apresentado um levantamento bibliográfico com os trabalhos correlatos aeste.

Na Seção 2.1, são apresentados os conceitos fundamentais dos sistemas derecomendação. Nessa seção, são explorados a história dos sistemas de recomendação,seus conceitos, principais marcos e os objetivos desses sistemas. Ainda são discutidosos principais tipos. Na Seção 2.2, são explicadas as principais formas de aquisição dedados desses sistemas, apresentando suas vantagens e desvantagens. Na Seção 2.3, sãoexploradas diversas formas de se avaliar os sistemas de recomendação, e são apresentadosos métodos e métricas mais utilizados na literatura. Na Seção 2.4, são apresentadostrabalhos que almejam alcançar pelo menos um dos objetivos deste trabalho. Para essaseção, foram selecionados apenas os trabalhos julgados mais relevantes.

2.1 Sistemas de Recomendação

Sistemas de recomendação são sistemas que auxiliam no aumento da capacidadee eficácia do processo de indicação já bastante conhecido na relação social entre sereshumanos [68].

Em [79], afirma-se que o mecanismo de recomendações para a tomada de decisãoé uma prática comum entre os seres humanos, mesmo muito antes dos computadoresserem inventados. No entanto, a história dos sistemas de recomendação computacionalcomeçou na segunda metade do século XX. Um marco importante para esta área foi oano de 1992, quando foi publicado o Tapestry [30], o primeiro trabalho de sistemas derecomendação que abordou filtragem colaborativa, introduzindo esta vertente nessa áreade estudo. Antes deste marco, havia apenas Sistemas de Recomendação Baseados emConteúdo, como [29, 65, 52]. Depois deste marco, os Sistemas de Recomendação comFiltragem Colaborativa começaram a aparecer.

2.1 Sistemas de Recomendação 21

Os sistemas de recomendação estão presentes nos mais variados tipos de aplica-ções, como: Recomendação de livros e CDS [49, 58], músicas [46, 79], filmes [39, 55, 7],notícias [9, 43, 82], piadas [31], páginas web [10, 56], etc.

Herlocker et al. [35] propõem em seu artigo uma taxonomia sobre os objetivospara os quais um sistema de recomendação pode ser projetado. São esses objetivos:

• Encontrar alguns bons itens: também conhecida como Top-N, essa tarefa temcomo objetivo produzir uma lista, ranqueada por relevância, de itens de interessedo usuário. Os itens devem ser ordenados segundo o interesse do usuário-alvo. Estaé a principal tarefa que a maioria dos sistemas de recomendação comerciais tratam.

• Encontrar todos os bons itens: o objetivo desta tarefa é recomendar todos os itemsque satisfazem a necessidade do usuário. Esse tipo de tarefa é muito comum emsistemas críticos como em aplicações médicas e financeiras. Não há necessidade deordenar os itens recuperados pelo sistema, pois o usuário irá analisar cada item. Oimportante é que existam poucos falsos-positivos.

• Anotação em contexto: nesta tarefa, dado um contexto como uma lista de itensdo interesse de um usuário, o sistema de recomendação deve ordenar por grau deinteresse esta lista, podendo inclusive remover os de menor interesse. Difere datarefa de encontrar alguns bons itens, pois nesta tarefa, trabalha-se com todos ositens do sistema. Também difere da tarefa de encontrar todos os bons itens, poisnessa tarefa é necessário ordenar por grau de relevância.

• Recomendar sequência: a idéia nesta tarefa é recomendar uma ordem a ser se-guida. Por exemplo, um sistema de recomendação para ensinar um determinadoassunto, sugerindo a ordem em que os documentos a respeito do assunto devem serestudados para um melhor aprendizado. Outros exemplos incluem recomendaçõesde séries de TV e livros.

• Recomendação em lote: o objetivo neste caso é recomendar n itens para umusuário de tal forma que esses n itens são interrelacionados e de seu interesse.Por exemplo, uma recomendação de uma agência de viagem. Além do destino daviagem, a agência pode recomendar os melhores passeios a serem feitos durante aviagem.

• Apenas navegação: nesta tarefa o usuário navega pelo catálogo de itens do sistemasem a intenção iminente de realizar uma compra. O objetivo do sistema nestatarefa é colaborar para que o usuário tenha uma utilização agradável do sistema.


Nestes casos, a acurácia do sistema é menos importante que a interface oferecida,facilidade de uso e a forma como a recomendação é apresentada.

• Encontrar recomendadores confiáveis: para alguns usuários, apenas receberas recomendações não é suficiente, pois estes precisam saber o motivo de cadarecomendação e se essas recomendações realmente são interesses para eles. Destaforma, alguns sistemas apresentam essa informação. Por exemplo, o sistema reco-menda ao usuário U-1 o item I-4 porque o usuário U-2 gostou desse item e temgostos similares aos do usuário U-1. Assim, o usuário U-1 consegue entender arazão do sistema recomendar o item I-4.

• Melhorar o perfil do usuário: essa tarefa está relacionada a capacidade do usuárioprover informações para o sistema sobre o que ele gostou ou não. Esta tarefa éfundamental em qualquer sistema de recomendação para prover recomendaçõespersonalizadas. Sem esta característica, o sistema só poderia realizar recomenda-ções genéricas, utilizando por exemplo as médias. Na Seção 2.2 são discutidos osmétodos utilizados para esta tarefa.

• Satisfação pessoal: Para alguns usuários, receber recomendações não é o maisimportante. Esses usuários se satisfazem apenas em poder expressar suas opiniõese avaliações, colaborando com o sistema. Quase todos os sistemas proporcionamessa funcionalidade a seus usuários.

• Ajudar a comunidade: alguns usuários se satisfazem por contribuir com suasinformações, por exemplo suas avaliações, simplesmente por acreditarem que acomunidade se beneficiará de suas contribuições, mesmo que o próprio usuário nãovenha a se beneficiar com essa contribuição. Ás vezes, o usuário faz isso para poderse expressar, assim como na tarefa anterior. Porém, isso não é regra, por isso sãoapresentados como objetivos distintos.

• Influênciar os outros usuários: para alguns usuários, o principal objetivo é in-fluênciar explicitamente outros usuários a terem uma determinada opinião sobrealgum item. Isso traz um problema para os sistemas, que são os usuário maliciosos.Esses usuários, podem ser usuários não reais, criados com o intuito de promoverou difamar um determinado item. Dessa forma, os sistemas precisam tratar esseobjetivo com cuidado.

Esses objetivos visam os interesses do usuário final. Em [41] são definidos outroscinco objetivos. Esses objetivos são referentes aos interesse dos provedores dos sistemas


de recomendação. São eles:

• Aumentar o número de itens vendidos: provavelmente esse é o objetivo maisimportante para os provedores dos sistemas de recomendação comerciais. Nestatarefa, o objetivo central é simplesmente aumentar o número de itens vendidos.

• Vender itens mais diversificados: outra função muito importante do ponto devista do provedor para os sistemas de recomendação é vender itens que geralmentenão são vendidos. Isto é, ao invés de recomendar apenas os itens mais vendidos,o sistema deve recomendar itens que são pouco vendidos, porém que agradem aousuário.

• Aumentar a satisfação dos usuários: nesta tarefa o sistema de recomendação deveser desenvolvido de forma a proporcionar a melhor experiência para os seus usuá-rios. Isso inclui, por exemplo, a forma como as recomendações são apresentadas.

• Aumentar a fidelidade dos usuários: esta é outra tarefa importante, pois temcomo objetivo manter os clientes do provedor do sistema de recomendação ativos.Isto é, continuar visitando o sistema e realizando novas compras. Esse objetivo éatingido com boas e novas recomendações.

• Melhorar o entendimento do que os usuários desejam: esta é uma tarefa queajuda o provedor do sistema de recomendação a entender o perfil de seus clientes.Isso pode colaborar para o planejemento do provedor.

Na prática, quando se desenvolve um sistema de recomendação é necessáriobalancear os requisitos entre as necessidades do usuário final e as do provedor dos sistemade recomendação. Entretanto, para fins acadêmicos, geralmente os trabalhos estudamapenas um desses objetivos.

Na literatura [17, 41] os sistemas de recomendação são geralmente classificadosem quatro tipos: sistemas de recomendação baseados em conteúdo, baseados em conheci-mento, demográficos e baseados em filtragem colaborativa. Essa classificação é feita combase na fonte de dados utilizada para produzir as recomendações. Segundo [41], os siste-mas baseados em filtragem colaborativa são os mais populares e comumente encontrados,além de apresentarem os melhores resultados.

A Figura 2.1 apresenta um estrutura hierárquica da taxonomia dos sistemas de re-comendação, tendo em seu primeiro nível a divisão entre sistemas baseados em FiltragemColaborativa, Baseados em Conteúdo, Baseado em Conhecimento e Demográficos. Nessahierarquica a atenção é voltada para os sistemas baseados em Filtragem Colaborativa. Nodecorrer deste capítulo são detalhadas as partes dessa ramificação.


Figura 2.1: Taxonomia dos Sistemas de Recomendação.

Ainda existem os sistemas de recomendação híbridos [17]. Esses sistemas com-binam técnicas para gerar recomendações. Essa combinação pode ser entre tipos e classesde sistemas de recomendação. Por exemplo, utilizando o tipo filtragem colaborativa juntocom o tipo baseado em conteúdo, ou ainda, um algoritmo da classe baseado em memóriacom outro da classe baseado em modelo. Um estudo mais aprofundado sobre as técnicasde sistemas de recomendação baseados em filtragem colaborativa pode ser visto nos tra-balhos [2, 81]. Em [17] é apresentado um estudo comparativo entre mais de 40 formas dehibridização de técnicas de recomendação. A seguir são apresentados com mais detalhesos quatros tipos de sistemas de recomendação.

2.1.1 Sistemas de Recomendação Baseados em Conhecimento

Os sistemas de recomendação baseados em conhecimento recomendam itensbaseados no conhecimento do contexto. Isso é, o sistema recomenda um item para ousuário-alvo de acordo com o contexto em que este usuário se encontra, por exemplo, sualocalidade ou momento que a recomendação será realizada.

Em [1] é proposto um modelo multidimensional para tratar esses sistemas derecomendação. Ao invés de usar as duas dimensões convencionais (usuários x itens), essemodelo apresenta n-dimensões, por exemplo, usuários, itens, horário, companhia, local,etc.

Esses sistemas utilizam alguma heuristica para descobrir se um determinado itemé relevante ou não para o usuário-alvo. Esta heuristica pode ser em função das informações


existentes sobre o usuário-alvo, sobre os itens do sistema ou mesmo sobre os outrosusuários do sistema. Desta forma, o conjunto de itens que potencialmente poderiam serrecomendados pode ser reduzido.

A relevância de um item para um usuário depende, também, de outras variáveis(diferentes das avaliações que os usuários deram a seus itens). Essas variáveis são tratadasem [1] como "Contexto". Um bom exemplo dessas variáveis é o local que o usuário-alvoestá no momento que recebe a recomendação.

Seja um usuário-alvo o cliente de um resturante em um jantar. A variável "local"neste caso é o restaurante. Para esse contexto, uma chuteira não tem a menor relevânciapara o usuário. Um sistema baseado em conhecimento deveria perceber que o usuário-alvoestá em um jantar (por exemplo, pelo horário) e recomendar uma sobremesa, ou ainda,tendo conhecimento que o usuário-alvo gosta de se divertir após o jantar, recomendaralgum entreterimento próximo a ele.

Outros exemplos de variáveis de contexo são o nível de conhecimento e prefe-rências do usuário-alvo. Por exemplo, se o usuário-alvo tem pouco conhecimento sobrecâmeras digitais, a recomendação de uma máquina profissional que requer conhecimentosavançados pode ter muito menos relevância para este usuário do que um curso básico defotografia. Olhando as preferências do usuário, pode haver uma restrição dizendo que omesmo não se interessa por nada relativo a fotografias. Neste caso, o sistema de recomen-dação baseado em conhecimento não deveria recomendar nenhum desses dois itens a esteusuário. O principal representante desta classe de sistemas é o case-based [16, 69]. Outrorepresentante é o constraint-based [25].

Os sistemas case-based utilizam experiências de soluções de casos passados pararesolver novos problemas com características semelhantes. A Figura 2.2 mostra a tela dosistema Entree. Esse sistema é o exemplo mais famoso de case-based na literatura.

2.1.2 Sistemas de Recomendação Demográfico

Os sistemas de recomendação demográficos [63] adotam a filosofia de querecomendações devem ser feitas por ninchos demográficos. Assim, estes sistemas utizamas informações demográficas dos usuários para produzir recomendações. Por exemplo, aregião do usuário-alvo ou sua faixa etária.

Estes sistemas são as vezes confundidos com os baseados em conteúdo devidoao uso de informações relativas aos próprios usuários. A principal diferença é que nestessistemas as informações dos itens não são levadas em consideração, recomendando aousuário-alvo itens que outros usuários, de informações demográficas semelhantes, tenhamavaliado bem. Por outro lado, os sistemas de recomendação baseados em conteúdo


Figura 2.2: Tela do sistema Entree.

recomendam ao usuário-alvo itens similares aos itens que ele mesmo tenha avaliado bem,ou seja, nesses sistemas as informações dos itens são fundamentais.

O LifeStyle Finder [45] é o sistema de recomendação demográfico mais conhe-cido da literatura. Este sistema tenta classificar o usuário-alvo em um entre 62 grupos pré-definidos. Devido a grande dificuldade de obter as informações demográficas do usuário,o sistema trabalha com diálogos explícitos para categorizar o usuário.

O perfil do usuário neste tipo de sistemas de recomendação é geralmente repre-sentado no modelo de vetor, onde cada dimensão do vetor representa uma característicademográfica. A Tabela 2.1 apresenta um exemplo desse vetor para um usuário.

A implementação desse tipo de sistema geralmente é simples, porém não apre-senta resultados satisfatórios em termos de acurácia, isso é, não produz recomendaçõesmuito direcionadas e precisas para o usuário-alvo. Este é o principal problema. Entretanto,


Gênero Faixa etária Cidade Casado?Usuário X Masculino 15-25 Goiânia Não

Tabela 2.1: Exemplo de vetor demográfico para um usuário X.

alguns trabalhos [66, 85, 86] utilizam as idéias deste tipo de sistema de recomendação paramelhorar a acurácia dos seus sistemas.

2.1.3 Sistemas de Recomendação Baseados em Conteúdo

Os sistemas de recomendação baseados em conteúdo recomendam itens para ousuário-alvo baseando-se na descrição do item [34]. Para isso, é verificado se a descriçãodo item combina com os interesses do usuário-alvo. Por exemplo, se o usuário-alvoavaliou positivamente um filme do gênero de comédia, um outro item de comédia deveráser recomendado a este usuário.

Estes sistemas têm como base as técnicas de Recuperação de Informação [4, 70].A descrição de um item pode diferir bastante da descrição de outro item, tornando se umproblema de dados não estruturados.

Para representar as informações não estruturadas dos itens e o perfil dos usuárioso modelo de dados mais utilizado é o Modelo de Espaço Vetorial [72]. Este modelo dedados é a representação espacial de documentos textuais.

Neste modelo, cada item e cada usuário é representado por um vetor no espaçon-dimensional, onde cada dimensão representa um termo do vocabulário utilizado nosistema. Cada dimensão desse vetor é ponderada de acordo com o grau de existenciadesse termo na descrição do item ou no perfil do usuário. Geralmente é utilizada a técnicaTF-IDF [71] para fazer a ponderação de cada termo.

O preenchimento do vetor de cada item é realizado pela descrição do item. Já ovetor que representa o perfil dos usuários é preenchido utilizando as características dositens que o mesmo já tenha avaliado no passado.

Para verificar a relevância de um item para o usuário-alvo é realizada uma medidade similaridade entre o vetor do item e o vetor do perfil do usuário. Em geral é utilizadacomo medida de similaridade o valor correspondente ao cosseno do ângulo formado pelovetor do item e o vetor do perfil do usuário. Então, os itens com maior similaridade sãorecomendados.

Este paradigma apresenta vantagens e desvantagens, como apresentado em [51,22]. Como vantagens podemos citar:

• Independência de usuário: o sistema de recomendação depende exclusivamente dousuário-alvo para produzir recomendações, isso é, não depende da existencia deoutros usuários no sistema.


• Transparencia: é facil explicar a razão das recomendações. Basta verificar se ascaracterísticas do item assemelham-se ao perfil do usuário-alvo.• Novos itens: é possível recomendar itens recém cadastrados no sistema. Basta que

as características do novo item sejam de interesse de algum usuário.

E como desvantagens podemos citar:

• Análise limitada a conteúdo: nenhum sistema baseado em conteúdo pode fornecerboas recomendações se os itens não tiverem informações suficientes para discrimi-nar os itens que o usuário-alvo gosta dos itens que ele não gosta. Muitas vezes nãohá informação suficiente de freqüência de palavras. Além disso, técnicas de extra-ção de texto ignoram completamente qualidades estéticas e informações multimídiaadicionais.• Superespecialização: o sistema não produz recomendações inesperadas. Isso é, as

recomendações são sempre de itens que têm característica semelhantes as do perfildo usuário-alvo. Esse problema é conhecido como ”problema acaso” (serendipityproblem).• Novos usuários: não consegue fazer recomendações para novos usuários no sis-

tema. Antes que o sistema possa recomendar algum item para um novo usuário,este usuário precisa de dar informações sobre ele para que o sistema monte seuperfil.

Em [64, 5] são apresentados alguns exemplos de sistemas de recomendaçãobaseados em conteúdo.

2.1.4 Sistemas de Recomendação Baseados em Filtragem Colabora-tiva

Os sistemas de recomendação baseados em filtragem colaborativa tiveram inícioem 1992 com o Tapestry [30]. Nesses sistemas, as opiniões dos usuários sobre os itens dosistema são utilizadas para poder inferir recomendações para o usuário-alvo.

Não há necessidade de qualquer conhecimento a respeito dos itens em si. A únicainformação necessária é a matriz contendo as avaliações dos usuários sobre os itens. Estaé uma das grandes vantagens desse tipo de sistema, pois nem sempre existem informaçõessuficientes sobre os itens. Além disso, a tarefa de estruturar as informações de um item,como ocorre nos sistemas baseados em conteúdo, é por si mesma um grande desafio.

Outra grande vantagem de classificar os itens através da avaliação dos usuáriosé a capacidade de avaliar características difíceis de serem feitas de formas textuais, comoa qualidade do filme. Por exemplo, um usuário gosta de filmes de terror, mas isso não


significa que todos os filmes de terror irão agradar este usuário, desta forma, ele iráinformar quais são os filmes de terror que ele gostou e quais não gostou. É importantenotar que o usuário não precisou dizer quais eram de terror, apenas que ele gostou dosfilmes x, y e z.

Esses sistemas seguem o princípio de que pessoas que concordaram em avalia-ções de um mesmo objeto no passado também irão concordar nas avaliações de outrosobjetos no futuro.

A filtragem colaborativa é considerada a técnica de sistema de recomendaçãomais popular e utilizada em sistemas de recomendações [41, 18]. Em [76] esse tipo desistema é denominado ”correlação pessoa-para-pessoa”.

As informações de um sistema de recomendação baseado em filtragem colabo-rativa são armazenadas em uma simples matriz de avaliações, onde cada linha representaum usuário e cada coluna representa um item do sistema. Cada célula da matriz corres-pondente a uma avaliação. A Tabela 2.2 mostra um exemplo dessa matriz de avaliações.Embora as avaliações sejam a única informação disponível para esses sistemas, eles, emgeral, apresentam uma acurácia melhor que os demais tipos de sistemas.

Item 1 Item 2 Item 3 Item 4Usuário 1 4 2Usuário 2 4 2 1Usuário 3 5Usuário 4 5 2Usuário 5 2 3

Tabela 2.2: Exemplo de vetor demográfico para um usuário X.

As técnicas de filtragem colaborativa são classificadas, por muitos autores [2,7, 14, 23], em dois grupos de métodos diferentes: baseados em memória e baseados em

modelo. Esses dois métodos serão discutidos no Capítulo 3.Existem quatro problemas bastante conhecidos nos sistemas de recomendação

baseados em filtragem colaborativa. Os pesquisadores buscam sempre propor algoritmosque superem um ou mais desses problemas. Além desses quatro problemas da área, ogrande volume de dados tem se tornado um problema de performace para os pesquisado-res. Os problemas são listados abaixo.

• Problema do usuário iniciante: esse problema diz respeito a um usuário novato nosistema que avaliou poucos ou nenhum item. Logo, é difícil para o sistema descobrire opinar sobre suas preferências.• Problema do novo item: similar ao problema anterior, porém, este diz respeito a

algum item que acabou de ser adicionado no sistema. Como a única informaçãodisponível neste tipo de sistema de recomendação são as avaliações dos usuários

2.2 Obtenção de Dados para Sistemas Recomendação 30

sobre os itens e esse novo item ainda não fora avaliado por nenhum usuário, arecomendação desse item para qualquer usuário se tornam pouco provável.• Problema da esparsidade: em geral os sistemas apresentam uma base de dados

(matriz de avaliações) bastante esparsa, ou seja, pouco densa. Isso é de fato lógico,pois dificilmente algum usuário vai pover informações sobre suas avaliações devários itens. Essa dificuldade de preencher a base de dados pode ser explicada pordois motivos: grande quantidade de itens distintos e o comportamento do usuárionas avaliações, isso é, o número de avaliações entre os usuários variam muito.• Problema da ovelha negra: esse problema diz respeito ao usuário que tem gostos

peculiares. Alguns usuários apresentam gostos completamente diferentes da maio-ria. Por exemplo, os items que a grande maioria dos usuários gostam este usuárionão gosta. Assim, é difícil para o sistema encontrar alguém que possa colaborar narecomendação de itens para esse tipo de usuário.

2.2 Obtenção de Dados para Sistemas Recomendação

Embora essa atividade não seja exatamente pertencente à área de sistemas derecomendação, o assunto é tratado nesta seção devido à sua importância. A atividade deextrair informações úteis para o sistema é extremamente importante para garantir uma boaacurácia.

Diversos pesquisadores trabalham para encontrar formas mais eficazes de extrairinformações. Essas informações são utilizadas como dados de entrada para os sistemasde recomendação. Por exemplo, essas informações podem ser utilizadas para preencher amatriz de avaliações apresentadas na Seção 2.1.4.

Os métodos utilizados para extrair essas informações podem ser classificadosem dois grupos: explícitos e implícitos. Cada um apresenta vantagens e desvantagens.A seguir serão apresentados com mais detalhes esses métodos, e suas vantagens edesvantagens serão expostas.

2.2.1 Métodos Explícitos

Os métodos explícitos consistem em questionar ao usuário de forma direta, quala opinião deste a respeito de um item.

Esses métodos são bastante difundidos nos sistemas de recomendação devido àsua facilidade de implementação. Eles seguem a idéia de que o usuário sabe aquilo quegosta e o que não gosta. Essa abordagem pode ser feita na primeira interação do usuáriocom o sistema, durante a utilização deste. A Figura 2.3 mostra um exemplo de sistemaque utiliza essa abordagem para extração de dados.

2.2 Obtenção de Dados para Sistemas Recomendação 31

Figura 2.3: Site Submarino. Exemplificando modo de extração deinformação desse sistema.

Na Figura 2.3, podemos ver que o livro do Harry Potter possui estrelas abaixodele. Essas estrelas representam as possíveis notas que um usuário pode dar a este item.Esse modelo de cinco estrelas é o mais utilizado. Existem ainda outros modelos, como outilizado no sistema Jester 1, que permite o usuário dar uma nota de -10,00 a +10,00para cada piada. Podemos resumir as vantagens desses métodos como: facilidade deimplementação e possibilidade de que o usuário diga diretamente o que ele gosta, evitandoerros.

Embora essas vantagens sejam bastante atrativas, o método ainda apresentaalguns problemas. O principal deles é a falta de hábito da maioria dos usuários de avaliaros itens. E sem essas informações, o sistema não consegue gerar recomendações. Alémdisso, ainda quando o usuário faz suas avaliações, existem vários fatores que infuênciama sua avaliação naquele momento. Isso é, o gosto do usuário pode variar de um dadomomento para outro.

1http://eigentaste.berkeley.edu/user/index.php

2.3 Métodos e Métricas de Avaliação em Sistemas de Recomendação 32

2.2.2 Métodos Implícitos

Os métodos implícitos, por outro lado, não requerem uma ação direta do usuário.Nestes métodos, as ações que um usuário tem durante suas interações com o sistema sãoutilizadas como informações para inferir os gostos do mesmo. Em geral, são utilizados oslogs dos sistemas para realizar essas análises.

Esses métodos proporcionam muito mais informações do que o método anterior,além de não incomodar o usuário ao requisitar que o mesmo atue de forma direta naavaliação. Esses métodos são bastante utilizados em sistemas de grande porte, como nocomérico eletrônico da Amazon.

Um exemplo desse método é apresentado no sistema de recomendação de umabiblioteca digital CADAL2[48]. Neste sistema as inferências sobre os gostos do usuáriosão feitas de acordo com as buscas realizadas e o tempo de permanência de um usuárioem cada livro. Outro sistema bastante conhecido que utiliza esse mesmo modelo de tempode permanência para inferir o gosto do usuário por um item é o Last.fm3. Esse sistema fazsuas análises baseando-se na atitude do usuário em escutar a música completa ou saltarpara a próxima antes que a música tenha terminado.

Este método é muito eficaz, devido à facilidade que o mesmo traz para o usuárioe o grande volume de informações que pode proporcionar. Entretanto, este método podegerar dados errôneos. Por exemplo, um usuário que acesse o sistema Last.fm e comecea escutar uma lista de músicas que não são de seu interesse. Ao invés de saltar todas asmúsicas, o usuário pode se afastar do computador e deixar o sistema passar por todas asmúsicas. Assim, o sistema vai inferir que este usuário gosta daquele tipo de música.

É perceptível que cada um dos métodos apresenta vantagens e desvantagens. Osmelhores sistemas de recomendação não fazem escolha de um método ou de outro paracoletar suas informações. Ao invés disso, eles utilizam os dois métodos, explorando o quecada um tem de melhor.

2.3 Métodos e Métricas de Avaliação em Sistemas deRecomendação

O principal objetivo dos sistemas de recomendação é fazer com que as previsõesdos gostos dos usuários sejam mais precisas. A precisão dessas previsões pode seravaliada através das medidas clássicas de recuperação de informação, como o MAE e

2http://www.cadal.cn/3http://www.lastfm.com.br/


o RMSE. Pesquisadores fazem uso destas avaliações (MAE, RMSE, entre outras) a fimde melhorar os métodos e abordagens dos sistemas de recomendação [11].

Por conta dessa preocupação constante em se medir a qualidade das recomenda-ções, os sistemas de recomendação foram gradualmente testados e melhorados [18]. De talforma, as medidas de qualidade mais comumente utilizadas em sistemas de recomenda-ção são [38, 32]: (i) avaliação de previsão, (ii) avaliação de conjuntos de recomendações,e (iii) avaliação de recomendações como lista de classificados (Top-N). As métricas deavaliação [3] podem ser classificadas como [36, 32]:

1. métricas de previsão: MAE (Mean Absolute Error), RMSE (Root of Mean Square

Error) e o NMAE (Normalized Mean Average Error)2. métricas de conjunto: Precisão (Precision), Revocação (Recall) e o ROC (Receiver

Operating Characteristic)[77].3. métricas de lista de classificados (Top-N): half-life (meia-vida)[15] e o “desconto

de ganho acumulado” [6].4. métricas de diversidade: diversidade e a novidade de itens recomendados [40].

Os autores[36, 38, 3, 32, 19] e Bobadilla et al.[11] destacam a importância emmedir a precisão dos resultados de um sistema de recomendação. E dessa forma, apontamalguns indicadores que são comumente utilizados para este propósito.

Definimos U como um conjunto de usuários de um sistema de recomendação,I como um conjunto de itens e M [u][i] como sendo a avaliação dada pelo usuário u aoitem i. Definimos também M [u][i] = ε como sendo o item i não avaliado pelo usuário u.E por fim, definimos p(u,i) como sendo a avaliação do usuário u para o item i predita pelosistema.

Seja Iu = {i ∈ I |M [u, i] 6= ε} o conjunto de itens avaliados pelo usuário u eque contenham predições de avaliação. Podemos dizer que a diferença absoluta entre aavaliação real dada pelo usuário e a avaliação prevista (|M [u][i]− p(u,i)|), informa o errona previsão. As equações Equação2-1 e Equação2-2 defininem, respectivamente, o cálculopara o RMSE e para o MAE.

RMSE =1|U| ∑

u∈U

√1|Iu| ∑i∈Iu

(p(u,i)−M [u][i])2 (2-1)

MAE =1|U| ∑

u∈U(

1|Iu| ∑i∈Iu

|p(u,i)−M [u][i]|) (2-2)

A cobertura (coverage) pode ser definida como a capacidade de prever a partirde uma métrica específica aplicada a um sistema de recomendação [11]. Em suma, elacalcula o percentual de itens não avaliados pelo usuário-alvo que pode ser recomendado


pelo sistema. Assim, definimos C [u] como o conjunto de itens que o sistema poderecomendar ao usuário u e D[u] como o conjunto de itens do sistema que o usuário u

ainda não avaliou. Assim, de acordo com [11], a cobertura do sistema, como a média decobertura do usuário, é dada na Equação 2-3:

cobertura =1|U| ∑

u∈U(100× |C [u]|

|D[u]|) (2-3)

Ainda de acordo com Bobadila et al. [11], a confiança dos usuários de umdeterminado sistema de recomendação não depende diretamente da precisão para oconjunto de possíveis previsões, mas sim para um conjunto reduzido de recomendaçõesfeitas pelos sistemas de recomendação. Podemos definir as três medidas mais utilizadasno que diz respeito à qualidade recomendação: (i) de precisão (Equação 2-4), o que indicaa proporção de itens recomendados relevantes do número total de itens recomendados, (ii)de revocação (Equação 2-5), o que indica a proporção de itens recomendados relevantesem relação ao número de itens relevante, e (iii) F1, que é uma combinação de precisão erevocação (Equação 2-6).

precisão =1|U| ∑

u∈U

|R [u]n| (2-4)

revocação =1|U| ∑

u∈U

|R [u]||T [u]||

(2-5)

F1 =2×precisão× revocação

precisão+ revocação(2-6)

Nas Equações 2-4 e 2-5, R [u] é o conjunto de itens recomendados para o usuáriou que são realmente do interesse deste usuário, n é a cardinalidade do total de itensrecomendados pelo sistema para o usuário u e T [u] é o conjunto de todos os itens dosistema ainda não avaliados pelo usuário que são do interesse dele.

Quando o valor de n é grande, os usuários tendem a dar maior importância aosprimeiros itens da lista de recomendações. Dessa forma os erros cometidos nos primeirositens da lista são mais graves do que os demais. Para considerar essa situação, temos asmedidas de Top-N.

Entre as medidas de Top-N mais utilizadas segundo [11], podemos citar: (i) meia-vida (HL descrita na Equação 2-7)[15], o que pressupõe uma diminuição exponencial dointeresse dos usuários segundo a ordem em que os itens lhe são apresentados, dando maisimportância para o primeiro item da lista e praticamente ignora o último item da lista; e (ii)ganho acumulado de desconto (DCG descrita na Equação 2-8)[6], no qual a decadência

2.4 Trabalhos Relacionados 35

citada anteriormente deixa de ser exponencial e passa a ser logarítmica.

HL =1|U| ∑

u∈U

|R [u]|

∑i=1

max(M [u][R [u][i]]− p(u,R [u][i]),0)

2(i−1)/(α−1)(2-7)

DCGk =1|U| ∑

u∈U(M [u][1]+

|R [u]|

∑i=2

M [u][R [u][i]]log2(i)

) (2-8)

Nas equações 2-7 e 2-8, R [u] representa a lista de recomendação ordenada,M [u][R [u][i]] representa a avaliação verdadeira que o usuário u deu para o i-ésimo itemda lista de recomendação ordenada, p(u,R [u][i]) é a predição do sistema para o usuário u noi-ésimo item da lista de recomendação, α é o número do item na lista de tal forma que háuma chance de 50% de o usuário rever esse item.

2.4 Trabalhos Relacionados

Os dois principais objetivos dos sistemas de recomendação na literatura são:previsão de avaliações (Predições) e geração de listas recomendadas (Top-N). Nas duastarefas, acurácia e desempenho do tempo de execução são as principais preocupações.

Assim, a maioria dos estudos nesta área está relacionada com a melhoria depelo menos um destes dois pontos. Existem também alguns trabalhos que apenas aplicamtécnicas existentes em algum contexto para melhorar uma aplicação específica. Esta seçãoapresenta alguns trabalhos deste primeiro grupo, devido a este trabalho apresentar umalgoritmo para melhorar os dois pontos destacados no início desta seção.

Em [88] é demonstrada a importância da seleção de vizinhos na classe dosalgoritmos Baseados em Memória. Yu mostra que alguns usuários podem ser descartadosantes mesmo do processo de cálculo de similaridades, o qual é caro (exige muitoprocessamento do sistema), com o usuário-alvo. Esses usuários são descartados poralgumas heurísticas. Para isso, ele propõe um método estático que analisa a dependênciadas instâncias.

Existem estruturas de dados que permitem que nem todos os pares sejam compa-rados para se encontrar os mais semelhantes. Entretanto a maioria destas apresentam umcrescimento do uso de espaço exponencial, o que é um problema para grandes bases dedados. Em 2006, Beygelzimer et. al. [8] propõem uma estrutura denominada cover tree.Essa estrutura ameniza o problema do uso de espaço.

Entretanto essa estrutura não pode ser aplicada diretamente no problema de se-lecionar os vizinhos mais semelhantes em sistemas de recomendação baseados em me-mória, devido ao seguinte motivo: a estrutura apresenta algumas premissas de restriçõescomo a exigência de uma diferença de distância entre os pontos bem maior que as encon-


tradas com as medidas de similaridade utilizadas nos sistemas de recomendação baseadosem memória.

Existem, porém, alguns trabalhos na área de sistemas de recomendação queutilizam as idéias da cover tree. Em [13] é desenvolvida uma heurística baseada nasprioridades da cover tree. Entretanto, este trabalho não se concentra em resolver oproblema de acurácia ou tempo de execução, mas sim o problema de diversificação,isso é, impedir que os sistemas recomendem apenas top-sellers ou sempre os mesmos.Este é um problema bastante relevante para a área comercial. Neste sentido, de poda,fortalece a hipótese de que é possível descartar alguns pares sem a necessidade de calculara similaridade entre estes.

Cacheda et. al. [18] apresenta um estudo comparativo de vários algoritmos de fil-tragem colaborativa. Essas comparações incluem uma análise assintótica da performancedo tempo de execução, acurácia e cobertura. A Tabela 2.3 mostra uma análise assintóticados principais algoritmos da literatura. Esta tabela foi inspirada no trabalho de Cachedaet. al. [18]. Neste trabalho o algoritmo Item-based é tratado como sendo um algoritmobaseado em modelo, por poder ser pré-calculada a similaridade entre os itens de um sis-tema, porém, no presente trabalho esse algoritmo é considerado um algoritmo baseado emmemória, sendo realizado todos os cálculos de similaridade sob demanda, como ocorreno User-based.

Algoritmo Tempo de treinamento Tempo de prediçãoUser-based - O(mn)Item-based O(mn2) O(n)Similarity fusion O(n2m + m2n) O(mn)Personality dianosis O(m2n) O(n)Regression-based O(mn2) O(n)Slope one O(mn2) O(n)LSI/SVD O((m+n)3) O(1)RSVD O(mnk) O(1)RSVD2 O(mnk) O(1)NRSVD2 O(mnk) O(1)SVD++ O(mn2k) O(1)Integraded model O(mn2k) O(1)Cluster-based smoothing O(mnα + m2n) O(mn)Tendencies-based O(mn) O(1)

Tabela 2.3: Análise assintótica de algoritmos de filtragem colabo-rativa baseada em [18]. Na tabela m representa o nú-mero de usuários, n o número de itens, α é a quan-tidade de grupos formados e o k é a quantidade depropriedades selecionadas nos algoritmos SVDs.

Ainda em [18], Cacheda propõe um novo algoritmo para resolver os dois pro-blemas mencionados no início da seção, chamado de Tendencies-Based. Esse algoritmoparte da ideia de tendências, isto é, o cálculo da predição é realizado de acordo com astendências do item-alvo e do usuário-alvo. Para isso dois aspectos são analisados, se o


usuário-alvo costuma avaliar itens melhores do que a média dos outros usuários ou não, ese o item-alvo é melhor avaliado, em média, do que os outros itens ou não. Este algoritmomelhora significativamente o desempenho do tempo de execução, pois remove a fase decálculo de similaridade entre os vizinhos. No entanto, ele não apresenta um ganho deacurácia em vários níveis de esparsidade da matriz de avaliações.

Em [84] é apresentado um método de agrupamento (clustering) aplicado sobre amatriz de avaliações no contexto de filtragem colaborativa. Contudo, esse método exigeuma análise estática sobre a matriz, apresentando o mesmo problema que os algoritmosBaseados em Modelos. Portanto, apresenta um ganho na acurácia, entretanto o desempe-nho do tempo de execução é muito prejudicado, fazendo com que seu uso seja inviávelpara problemas reais em que a matriz de avaliações sofre mutações constantemente. Esteagrupamento proposto é aplicado entre os usuários.

Wei et. al. [87] apresentam um novo algoritmo de filtragem colaborativa baseadaem agrupamento. Nesse algoritmo, o método de agrupamento K-Means é aplicado pelasegmentação da matriz de avaliações original em K matrizes onde em cada submatriz aslinhas representam todos os usuários e as colunas representam itens que são similaresaos centroides da submatriz. Então, é aplicado uma variação do algoritmo User-based. Aseleção de vizinhos é realizada com base na semelhança global entre dois usuários, isto é,a soma da semelhança entre eles em cada um dos agrupamentos.

Esse novo algoritmo criado por Wei apresenta um ganho significativo de acu-rácia, contudo apresenta problemas relacionados aos desempenho desde a criação dosagrupamentos que exigem um alto custo computacional até a seleção dos vizinhos maissemelhantes que requer calcular a similaridade entre os usuários em cada agrupamento.Essa primeira etapa pode ser realizada offline, assim como os algoritmos Baseados emModelo fazem, porém para aplicações cuja matriz de avaliações é constantemente alte-rada em um curto intervalo de tempo, isso se torna inviável.

Uma abordagem recente usada para resolver problemas de desempenho do tempode execução é usar programação paralela (GPU) em algoritmos já existentes. Em [48], Liapresenta uma implementação em CUDA4 dos algoritmos User-Based e Randon-Walk.Em [60], Nadungodage apresenta uma implementação paralela do algoritmo Item-Based.O uso de GPU para execução desses algoritmos não melhora a acurácia, mas mostra umganho significativo em termos de tempo de execução.

Os trabalhos mais semelhantes ao proposto nesta dissertação são os que seguema linha de realizar adaptações no algoritmo Item-based, como os apresentados a seguir.Os trabalhos dessa linha visam alguma melhoria ou se usufruem do algoritmo Item-basedpara melhorar o tempo de execução ou acurácia.

4https://developer.nvidia.com/category/zone/cudazone


Mobasher et. al. [57] propõem o uso de ontologias para que o conhecimento dascaracterísticas dos itens possam melhorar a acurácia do algoritmo Item-based. Contudo,para isso é necessário uma nova fonte de dados para fornecer essas ontologias. Em geral,a única informação disponível é a matriz de avaliações. Esse trabalho obtém melhoresresultados, quando comparado ao Item-based tradicional, em termos de acurácia, devidoàs informações adicionais que o mesmo tem disponível sobre os itens.

Su em [80] utiliza a teoria dos conjuntos aplicada juntamente com o algoritmoItem-based para realizar as predições. São reportados resultados de melhora na acurácia,porém os resultados são reportados com a métrica ROC e a metodologia empregada nostestes não é clara.

Kim et. al. [42] introduz o conceito de confiança. Essa confiança funciona comouma espécie de medida de similaridade para a função de predição. A nova medida desimilaridade utilizada é apresentada pela Equação 2-9.

confiançaβ(i, j) =(β+1)sim(i, j)credibilidade( j)β2sim(i, j)+ credibilidade( j)

(2-9)

Na equação β é um parâmetro que varia de acordo com a base de dados epondera a importância entre a similaridade convencional e a função credibilidade. Essacredibilidade é calculada com base na matriz de erro E. Essa matriz de erro é formadapela diferença entre a predição do algoritmo Item-based tradicional e a avaliação real.

Este método consegue melhorar a acurácia e a robustez em relação aos algorit-mos tradicionais de User-based e Item-based. Entretanto o método requer uma fase detreinamento para a modelagem. Dessa forma, esse algoritmo não melhora o tempo deexecução.

Em [59], Mu propõe uma melhoria na fase de predição alterando a medidasimilaridade com o conceito de grau de hesitação. Neste trabalho, Mu apresenta trêstipos de grau de hesitação: i) baseado no desvio padrão (HDS), ii) baseado na média

(HDM) e iii) baseado na distância (HDD). Desta forma, é possível combinar esses grausde hesitações com qualquer medida de similaridade tradicional. A Equação 2-10 mostracomo essas combinações podem ser feitas. Na equação, o X pode ser o ‘S‘, ‘M‘ ou ‘D‘ decada um dos três tipo de hesitações, e sim(i, j) é uma função de similaridade genérica.

simHDX = sim(i, j)∗ (1−HDX iU( j)) (2-10)

Essa melhoria atinge um ganho significativo na acurácia usando o cossenoajustado como medida de similaridade em conjunto com a HDM. Esse ganho na acurácianão impacta o tempo de execução, nem positivamente nem negativamente.

CAPÍTULO 3Tipos de Filtragem Colaborativa

Neste capítulo serão apresentadas as duas classes dos sistemas de recomendaçãobaseados em filtragem colaborativa. Primeiramente é tratada a classe dos baseados emmodelo e por último os baseados em memória.

3.1 Sistemas baseados em modelo

Os sistemas baseados em modelo fazem um pré-processamento dos dados, issoé, da matriz de avaliações M , para produzir um modelo das interações entre usuários eitens. Esse pré-processamento é chamado de fase de modelagem ou fase de treino.

A fase de treino, em geral, apresenta um alto custo computacional. Dessa forma,essa fase não pode ser executada a todo momento. Porém, precisa ser executada, sejapara fazer recomendações para um usuário do sistema ou para todos. Por essa fase ser tãodemorada, ela é realizada offline1. Com o modelo concluído o sistema apenas o utilizapara gerar as recomendações para cada usuário.

Essa abordagem, em geral, apresentam bons resultados para os problemas ine-rentes aos sistemas de recomendação. Esse resultado é justificado por o modelo aprendidoser utilizado para fazer predições para qualquer usuário-item, funcionando como uma fór-mula matemática que recebe como parâmetro o usuário e o item.

Assim, utilizando essa abordagem, mesmo um usuário recém cadastrado nosistema pode receber recomendações, mesmo que equivocadamente. E um novo itemtambém pode ser recomendado.

Existem diversos trabalhos que apresentam modelos para sistemas de recomen-dação. As técnicas mais utilizadas são: redes bayesianas, agrupamentos, regressões line-

ares, redes neurais artificiais e modelos probabilísticos.Em [14] é proposto um modelo probabilísticos, no qual para predizer uma

avaliação ainda desconhecida se utiliza duas alternativas: modelo de agrupamento e

1Não é executada durante o período de recomendação. É feita de tempos em tempos, podendo ser feitainclusive em outra máquina

3.1 Sistemas baseados em modelo 40

redes bayesianas. No modelo de agrupamento os usuários são separados em grupos,então as predições para cada usuário são feitas de forma independente, dentro de seugrupo seguindo o modelo bayesiano. O número de grupos e os parâmetros do modelosão aprendidos a partir dos dados existentes. No modelo de redes bayesianas cada itemrepresenta um nó em uma rede Bayesiana, e os estados de cada nó correspondem aospossíveis valores de classificação para cada item. A estrutura da rede e as probabilidadescondicionais são aprendidos a partir dos dados existentes.

Foi desenvolvido em [10] um método de filtragem colaborativa baseado emmodelo utilizando um framework de machine learning. Neste framework são utilizadasvárias técnicas como redes neurais artificiais juntamente com técnicas algébricas, comodecomposição em valores singulares (Singular Value Decomposition - SVD).

Existem diversos outros algoritmos baseados em modelo na literatura [21, 27,62, 78, 84]. Esses algoritmos exploram o agrupamento de K-means, Gibbs sampling,processos de decisão de Markov, modelo de entropia máxima, entre outras técnicas.

Os algoritmos que vêm ganhando maior destaque na literatura são os queexploram a decomposição em valores singulares, como LSI/SVD [73], Regularized SVD

(RegSVD) e Improved RegSVD (RSVD2) [61], Integrated Neighbor-Based - SVD Model

[44]. Dentre esses, segundo [18], o algoritmo regularized SVD é o que apresenta melhoresresultados. O regularized SVD é apresentado com mais detalhes na próxima seção.

3.1.1 Regressão de decomposição em valores singulares (RegSVD)

Este modelo se tornou muito popular na área de sistemas de recomendaçãodevido seus bons resultados em termos de acurácia. Esta técnica foi introduzida nocontexto de sistemas de recomendação por Funk em [26] e implementada por Paterekem [61].

Neste modelo cada item é representado por um conjunto de avaliações de algunsdos usuários sobre o item. Da mesma forma, cada usuário é representado por um conjuntode valores que correspondem às suas avaliações dadas a alguns itens. Esses conjuntospossuem uma cardinalidade igual a K, onde este K é um parâmetro desse algoritmo.

A predição do item i para o usuário j, referida como pi j, é realizada pela fórmulada Equação 3-1. Nesta equação xi e y j são vetores K-dimensionais que representam,respectivamente, a afinidade de cada usuário e item com cada uma das K características.

pi j = xiT y j (3-1)

Os valores desses vetores são preenchidos na fase de treino, utilizando umavariação do algoritmo de decomposição em valores singulares. Nesta variação, os valoresdesconhecidos da matriz de entrada são ignorados. Isso simplifica o cálculo e torna o

3.2 Sistemas baseados em memória 41

algoritmo muito mais rápido. O algoritmo utiliza uma técnica para redução de gradientecom a intensão de minimizar a soma do quadrados resíduais.

Algoritmo 3.1: Construção do modelo RegSVD.

Entrada: Matriz de avaliações M [][], int maxIter, double LR, double Reg

1 int round← 0;

2 Inicia caracteristicas dos usuários e itens aleatoriamente [0,1];

3 int rateCount← numero de itens no sistema;

4 double prevErr← 99999;

5 double currErr← 9999;

6 enquanto (|prevErr− currErr| > 0.0001 && round < maxIter) faça7 double sum← 0.0;

8 para cada Usuário u no Sistema faça9 Array < Item > itens← Itens avaliados pelo usurio u;

10 para cada Item i em itens faça11 Array < double > f u← caracteristicas do usurio u;

12 Array < double > gi← caracteristicas do item i;

13 double err← ( f u∗gi)−M [u][i];

14 sum← |err|;15 para cada int s ENTRE 1 e K faça16 double f us← f u[s];

17 double gis← gi[s];

18 f u[s]← ( f us+LR∗ (err ∗gis−Reg∗ f us);

19 gi[s]← (gis+LR∗ (err ∗ f us−Reg∗Gis);

20 prevErr← currErr;

21 currErr← sum/rateCount;

22 round← round +1;

O Algoritmo 3.1 apresenta a forma para construção deste modelo. Os parâmetrosLR e Reg, são respectivamente a taxa de aprendizado e o regularizador. Os valores utiliza-dos nesses parâmetros afetam diretamente na qualidade do modelo. Outro parâmetro quepode afetar bastante a qualidade do modelo é o maxIter, que define o número máximo deiterações que o algoritmo pode executar mesmo sem atingir o limiar de erro aceitável.

3.2 Sistemas baseados em memória

Os sistemas baseados em memória, conhecidos na literatura também como siste-mas baseados em heurísticas ou baseados na vizinhança, diferente dos métodos baseados


em modelo, não requerem uma fase de treinamento. Ao invés disso, esses algoritmos uti-lizam diretamente a matriz de avaliações M para realizarem as suas predições. Este tipode abordagem utiliza a premissa de que semelhanças entre avaliações feitas no passadopodem se repetir no futuro. Por exemplo, se dois usuários avaliaram muitos dos itens deforma semelhante, eles tendem a avaliar os demais itens também de forma semelhante.Essa técnica ficou conhecida como “olhar sobre os ombros”, pois observa o passado parapredizer o futuro. A memória e o passado referidos acima, correspondem ao comporta-mento similar em relação às avaliações que já foram feitas no sistema. Há duas formas dese considerar similaridade:

• Similaridade entre usuários: considera como similares usuários que deram avalia-ções semelhantes a um conjunto comum de itens.• Similaridade entre itens: considera como similares itens que sofreram avaliações

semelhantes por um mesmo grupo de usuários.

Métodos baseados em memória que usam similaridade entre usuários são de-nominados métodos baseados em usuário (User-based methods) e métodos que utilizamsimilaridade de itens são denominados métodos baseados em itens (Item-based methods).

Ambos os métodos seguem o arcabouço geral descrito no Algoritmo 3.2 paracomputar uma predição p(ua, ia) da avaliação que um usuário ua ∈ U daria a um itemia ∈ I , sendo ia e ua tais que M [ua, ia] = ε. Ou seja, ua ainda não avaliou ia. Umusuário ua ∈ U para o qual se quer prever uma avaliação é denominado usuário-alvo.Analogamente, um item ia ∈ I para o qual se quer prever uma avaliação é denominadoitem-alvo.

Algoritmo 3.2: Algoritmos baseados em memória em alto nível.

Entrada: Matriz de avaliações M [][], usuário-alvo ua e item-alvo iaSaída: Predição

1 Calcular as similaridades;

2 Selecionar os vizinhos;

3 Realizar a predição com os vizinhos selecionados;

.A seguir, são apresentados alguns conceitos que serão utilizados nas seções

seguintes. Define-se Ui ⊆ U como o conjunto de usuários que avaliaram o item i, istoé, Ui = {u ∈ U|M [u, i] 6= ε}. Analogamente, Iu ⊆ I é o conjunto de itens avaliadospelo usuário u, sendo definido como Iu = {i ∈ I |M [u, i] 6= ε}. Define-se Ui,ia como oconjunto de usuários que avaliaram tanto o item i, como o item-alvo ia. Formalmente,Ui,ia = {u ∈ U|M [u, i] 6= ε∧M [u, ia] 6= ε}. O conjunto Iu,ua é formado por itens que


foram avaliados por um usuário u e também pelo usuário-alvo ua, isto é, Iu,ua = {i ∈I |M [u, i] 6= ε∧M [ua, i] 6= ε}.

Existe uma função de similaridade entre usuários simus(ux,uy) : U ×U → Rque produz um valor de similaridade dentro do conjunto de números reais para todo parde usuários ux,uy ∈ U. Analogamente, define-se a função de similaridade entre itens

simit(ix, iy) : I × I → R que associa um valor dentro do conjunto dos números reais paraa similaridade entre todo par de itens ix, iy ∈ I .

Na Seção 3.2.3 serão apresentadas as medidas de similaridades mais comuns emsistemas de recomendação que são utilizadas como funções de similaridade entre usuário(simus) ou como funções de similaridade entre itens (simit).

3.2.1 Métodos Baseados em Usuários

O algoritmo baseado em usuários foi um dos primeiros algoritmos de filtragemcolaborativa automático, isso é, que não requer intervenção humana para realizar asrecomendações. Foi proposto em 1994, por Resnick et. al. [67] como parte do sistemaGroupLens.

Esse algoritmo busca selecionar os usuários mais similares ao usuário-alvo eque avaliaram o item-alvo e utilizar as suas avaliações na predição. Seguindo o formatogeral do Algoritmo 3.2, o algoritmo baseado em usuários recebe como entrada a matrizde avaliações M , o usuário-alvo ua e o item-alvo ia. Como saída, o algoritmo retorna apredição de nota p(ua, ia) que o usuário-alvo ua daria para o item-alvo ia.

No algoritmo baseado em usuários, os três passos do Algoritmo 3.2 são redefini-dos do seguinte modo:

1. Calcular a similaridade simus(ua,u) entre o usuário-alvo ua e cada usuário u ∈Uia .2. Obter o conjunto dos k vizinhos mais próximos de ua, denotado por Vk(ua). Tal

conjunto é formado pelos k usuários que avaliaram ia e que possuem maior simila-ridade como o usuário alvo, computada, pela função de similaridade entre usuários.Formalmente, o conjunto Vk(ua)⊂Uia deve satisfaz as seguintes condições:

a) |Vk(ua)| ≤ k e,b) ∀ux ∈ Vk(ua)∧∀xy ∈Uia−Vk(ua), simus(ua,ux)≥ simus(ua,uy).

3. Calcular a previsão p(ua, ia) como resultado de alguma agregação das avaliaçõesdos usuários em V k(ua) dadas ao item ia.

A Figura 3.1 apresenta um exemplo do funcionamento do algoritmo. Neste exemplodeseja-se predizer a avaliação que seria dada ao item i1 pelo usuário u1. No primeiropasso, são calculados os valores da função de similaridades entre o usuário-alvo u1

e os demais usuários que avaliaram i1. Neste exemplo foi utilizada como função de


similaridade entre usuários a correlação de Pearson, a qual será explicada na Seção 3.2.3.O valor de similaridade é apresentado na lateral direita de cada linha (usuário) da matrizque possua alguma avaliação para o item-alvo ia.

No segundo passo do algoritmo são obtidos os k = 2 vizinhos mais próximos deu1, isto é, o conjunto V2(u1), que é formado pelos usuários u2 e u4, que correspondem àslinhas sombreadas da matriz de avaliações da Figura 3.1.

No terceiro e último passo do algoritmo, é utilizada a Equação 3-22 para calculara predição de avaliação p(u1, i1) da avaliação que o usuário u1 daria ao item i1. Nesteexemplo o valor da predição foi de 4,01.

Figura 3.1: Pequeno exemplo de uma instância do User-based.

3.2.2 Métodos Baseados em Itens

O primeiro algoritmo baseado em Itens foi proposto em 2001, por Linden et. al[50]. Ele utiliza a ideia de que as avaliações, aplicadas nos itens similares ao item-alvo,realizadas pelo próprio usuário-alvo são mais apropriadas para a predição da avaliação doitem-alvo do que as avaliações dos usuários similares ao item-alvo.

As entradas e saídas dos algoritmos baseados em itens são as mesmas queaparecem no Algoritmo 3.2, entretanto os três passos do referido Algoritmo são adaptadosdo seguinte modo:

1. Calcular a similaridade simit(ia, i) entre o item-alvo ia e cada item i ∈ Iua .2. Obter o conjunto dos k itens vizinhos mais próximos de ia, denotado por Vk(ia).

Formalmente, o conjunto Vk(ia)⊂ Iia deve satisfazer as seguintes condições:

a) |Vk(ia)| ≤ k e,b) ∀ix ∈ Vk(ia)∧∀iy ∈ Iua−Vk(ia), simit(ia, ix)≥ simit(ia, iy).

3. Calcular a predição p(ua, ia) como resultado de alguma agregação das avaliaçõesque o usuário-alvo ua deu aos itens em Vk(ia).

A Figura 3.2 apresenta um pequeno exemplo ilustrativo do funcionamento do algoritmo.Neste exemplo, deseja-se realizar a predição da avaliação que o usuário-alvo u1 daria aoitem-alvo i1. No primeiro passo são calculadas as similaridades entre o item-alvo i1 e os


demais itens em Iu1 . Neste exemplo utilizou-se também a correlação de Pearson comofunção de similaridade entre itens. O grau de similaridade é apresentado abaixo de cadacoluna (item) da matriz de avaliações M que possua alguma avaliação dada pelo usuário-alvo u1.

No segundo passo do algoritmo são selecionados os k vizinhos mais próximosdo item-alvo, isto é, Vk(i1) . Neste exemplo, k = 2. Logo, o conjunto V2(i1) é formadopelos itens i4 e i5.

No terceiro e último passo do algoritmo, são utilizadas as avaliações dadas pelosusuário u1 aos itens i4 e i5 (4 e 1) e os respectivos grau de similaridade (0,51 e 1,00) parapredizer a nota do item-alvo i1. Para isso é utilizada a Equação 3-21 a qual será explicadana Seção 3.2.4. O algoritmo produz como resultado o valor 2,01 que é o valor que dapredição p(u1, i1) para o valor da avaliação que o usuário-alvo u1 daria ao item-alvo ia.

Basicamente os métodos baseados em itens se diferem dos métodos baseados emusuários por compararem itens e não usuários. O processamento dos algoritmos é muitosemelhante, porém em aplicações práticas, os desempenhos dos dois tipos de métodospodem ser bem distintos entre si.

No caso de haver muito mais usuários do que itens, as colunas da matriz deavaliações M , que correspondem aos itens, tendem a ser menos esparsas do que as linhas.Neste caso, a tendência é que os itens sejam avaliados por alguns usuários, mas váriosusuários podem avaliar poucos itens. Nesse cenário, a comparação entre itens tende a sermais precisa do que a comparação entre usuários. Além disso, os algoritmos baseados emitens tendem a ser mais eficientes, pois o número de cálculos de similaridade são menores.Essa situação é a mais comum na prática e os sistemas de recomendação tendem a ter estacaracterística, à medida que novos usuários vão surgindo.

Se a situação for contrária, ou seja, há muito mais itens do que usuários (situaçãoque tende a ocorrer no início da operação de um sistema de recomendação) os algoritmosbaseados em usuário tendem a ter melhor eficácia e melhor eficiência, por motivosanálogos.

Figura 3.2: Pequeno exemplo de uma instância do Item-based.


3.2.3 Medidas de similaridade

Uma das etapas mais importantes para os algoritmos baseados em memória é aseleção de bons vizinhos. Essa parte afeta diretamente o tempo de execução, por ser aparte computacional mais cara desses algoritmos. Além do tempo de execução, a seleçãode bons vizinhos afeta também a acurácia, pois é o que define quais dados serão utilizadosna computação da predição.

Existem diversas equações que são utilizadas para calcular essa similaridade. Norestante dessa seção são apresentados os principais métodos utilizados para este fim.

Correlação de Pearson

Em estatística descritiva, o coeficiente de correlação de Pearson, também cha-mado de “ρ de Pearson”, mede o grau da correlação entre duas variáveis escalares. Paraos algoritmos baseados em memória, essas variáveis são as linhas ou colunas da matrizde avaliações.

A correlação de Pearson é muito indicada para variáveis discretas. A Equação3-2 é a forma do cálculo da correlação de Pearson para o algoritmo baseado em usuários.Enquanto a Equação 3-3 é utilizada no algoritmo baseado em itens.

wa,u =∑i∈Ia,u(M [a][i]−M [a][∗])(M [u][i]−M [u][∗])√

∑i∈Ia,u(M [a][i]−M [a][∗])2 ∑i∈Ia,u(M [u][i]−M [u][∗])2(3-2)

w(i, j) =∑a∈Ui, j (M [a][i]−M [∗][i])(M [a][ j]−M [∗][ j])√

∑a∈Ui, j (M [a][i]−M [∗][i])2 ∑a∈Ui, j (M [a][ j]−M [∗][ j])2(3-3)

Nas duas equações, M [u][i] representa a entrada da matriz de avaliação quecorresponde à avaliação dada por um usuário u a um item i. Na equação 3-2, wa,u

representa a similaridade entre o usuário a e o usuário u. Ia,u é o conjunto de itensavaliados tanto pelo usuário a quanto pelo usuário u. Os valores M [a][∗] e M [u][∗] são,respectivamente, a média das avaliações realizadas pelo usuário a e pelo usuário u.

Na equação 3-3, w(i, j) representa a similaridade entre o item i e o item j. Ui, j é oconjunto de usuários que avaliaram tanto o item i quanto pelo o item j. M [∗][i] e M [∗][ j]são, respectivamente, a média das avaliações dadas ao item i e ao item j.

Distância Euclidiana

A distância Euclidiana é uma métrica que baseia-se na distância entre os objetos(usuários ou itens). Esta ideia faz sentido quando se considera os objetos como sendopontos em um espaço de muitas dimensões, cujas coordenadas são valores de suasavaliações. Na distância Euclidiana, quanto menor o valor resultante mais similares são


os objetos. A Equação 3-4 demonstra a formalização matemática da métrica da distânciaEuclidiana [24] para calcular a distância entre dois usuários. A Equação 3-5 calcula adistância Euclidiana entre dois itens.

w(a,u) =√

∑i∈Ia,u

(M [a][i]−M [u][i])2 (3-4)

Na Equação 3-4 wa,u representa a similaridade entre o usuários a e o usuários u.Ia,u é o conjunto de itens avaliados tanto pelo usuário a quanto pelo usuário u.

Na Equação 3-5, w(i, j) representa a similaridade entre o item i e o item j. Ui, j é oconjunto de usuários que avaliaram tanto o item i quanto pelo o item j. M [a][i] e M [a][ j]

são, respectivamente, as avaliações do usuário a nos itens i e j.

w(i, j) =√

∑a∈Ui, j

(M [a][i]−M [a][ j])2 (3-5)

Medida dos Cossenos

A medida de similaridade dos cossenos é uma medida que considera as avalia-ções dos usuários a itens como vetores, isso é, um usuário é representado por um vetorno espaço dos itens e um item é representado por um vetor no espaço dos usuários. Cadaposição do vetor é uma avaliação de um usuário a um item.

Quanto menor é o ângulo formado entre dois vetores, mais semelhantes elessão. A Equação 3-6 formaliza matematicamente o cálculo para a medida de similaridadedo cosseno [75, 83, 2] para algoritmos baseados na semelhança entre usuários. Nestaequação wa,u representa a similaridade entre o usuário-alvo a e outro usuário u. Ia,u é oconjunto de itens avaliados tanto pelo usuário a quanto pelo usuário u. M [a][i] e M [u][i]

são, respectivamente, as avaliações dos usuários a e u em relação ao item i.

w(a,u) = cos(−→ra ,−→ru ) =

−→ra .−→ru

‖−→ra‖2×‖−→ru‖2

=∑i∈Ia,u M [a][i]M [u][i]√

∑i∈Ia,u M [a][i]2√

∑i∈Ia,u M [u][i]2(3-6)

A Equação 3-7 formaliza o mesmo cálculo para algoritmos baseados na seme-lhança entre itens. Nesta equação w(i, j) representa a similaridade entre o item i e o item j.Ui, j é o conjunto de usuários que avaliaram tanto o item i quanto pelo o item j. M [a][i] eM [a][ j] são, respectivamente, as avaliações dos usuários a nos itens i e j.

w(i, j) =∑a∈Ui, j M [a][i]M [a][ j]√

∑a∈Ui, j M [a][i]2√

∑a∈Ui, j M [a][ j]2(3-7)

Na medida dos cossenos, os valores de similaridade possíveis serão entre 0 e 1.Valores próximos de 1 indicam uma forte semelhança.


Medida dos Cosseno ajustado

A medida do cosseno ajustado é uma variante da “medida do cosseno”. Estamedida passou a ser utilizada nos sistemas de recomendação baseado em filtragemcolaborativa devido a Sarwar et. al. [74]. Foi mostrado que essa medida apresentaresultados melhores para o algoritmo Item-based tradicional usando média ponderadacomo função de predição. No cálculo simples do cosseno não é levado em consideraçãoa média dos vetores. E este é um problema que pode ser resolvido usando a medida docosseno ajustado, que subtrai o valor de cada posição do vetor pela média do mesmo.Dessa forma os valores resultantes passam a variar entre -1 e +1, assim como na correlaçãode Pearson.

A Equação 3-8 traz a formulação matemática para a função do cosseno ajustado[20] quando utilizado no algoritmo User-based. Nesta equação wa,u representa a similari-dade entre o usuário a e o usuário u. Ia,u é o conjunto de itens avaliados tanto pelo usuárioa quanto pelo usuário u. M [a][i] e M [u][i] são, respectivamente, as avaliações dos usuá-rios a e u no item i. A média das avaliações recebidas por um item i é representada porM [∗][i].

wa,u =∑i∈Ia,u

(M [a][i]−M [∗][i]

)(M [u][i]−M [∗][i]

)√

∑i∈Ia,u

(M [a][i]−M [∗][i]

)2√

∑i∈Ia,u

(M [u][i]−M [∗][i]

)2(3-8)

A Equação 3-9 traz a formulação para a mesma pedida, porém quando utilizadano algoritmo Item-based. Nesta equação w(i, j) representa a similaridade entre o item i eo item j. Ui, j é o conjunto de usuários que avaliaram tanto o item i quanto pelo o itemj. M [a][i] e M [a][ j] são, respectivamente, as avaliações dos usuários a nos itens i e j. Amédia das avaliações realizadas por um usuário a é representada por M [a][∗].

w(i, j) =∑a∈Ui, j

(M [a][i]−M [a][∗]

)(M [a][ j]−M [a][∗]

)√

∑a∈Ui, j

(M [a][i]−M [a][∗]

)2√

∑a∈Ui, j

(M [a][ j]−M [a][∗]

)2(3-9)

Correlação de Spearman

De acordo com os autores [12, 37], a correlação de Spearman é uma varianteda correlação de Pearson. Em vez de calcular a correlação com base nos valores dasavaliações originais, Spearman é calculada com base na posição relativa dos valores dasavaliações. O processo para o cálculo da correlação de Spearman é feito da seguinteforma: imagine que, para cada usuário, o valor da avaliação do seu item menos preferido é


trocado pelo valor 1. Então valor da avaliação do próximo item menos preferido é alteradopara 2, e assim por diante, até percorrer todos os itens avaliados pelo usuário. Em seguida,uma correlação de Pearson é calculado sobre os novos valores. Esta é a correlação deSpearman.

Tanimoto

O coeficiente Tanimoto é a razão entre o tamanho da intersecção, ou de sobre-posição, entre dois itens avaliados pelos usuários, com a união de itens avaliados pelousuário-alvo. Este valor também é conhecido como o coeficiente de Jaccard.

Dessa forma podemos definir esse coeficiente para o algoritmo User-based comoo número de itens que dois usuários (a e u) expressam alguma preferência (Ia,u), divididopelo número de itens que usuário-alvo expressa alguma preferência (Na). De acordo com[54], a métrica de Tanimoto é definida através da Equação 3-10.

wa,u =|Ia,u|Na

(3-10)

Nesta equação wa,u representa a similaridade entre o usuário a e o usuário u. Ia,u

é o conjunto de itens avaliados tanto pelo usuário a quanto pelo usuário u. Na representaa cardinalidade do conjunto de itens avaliados pelo usuário a. Analogamente a Equação3-11 formaliza o cálculo desse coeficiente para o algoritmo Item-based.

w(i, j) =|Ui, j|

Ni(3-11)

Nesta equação w(i, j) representa a similaridade entre o item i e o item j. Ui, j éo conjunto de usuários que avaliaram tanto o item i quanto o item j. E Ni representa acardinalidade do conjunto de usuários que avaliaram o item i.

Log-Likelihood

Log-Likelihood é uma medida de cálculo de similaridade que não leva emconsideração as avaliações realizadas. Esta medida de similaridade, segue uma sequênciade ações para calcular a similaridade. Supondo que o cálculo de similaridade seja entredois usuários, primeiramente é calculada a relação entre itens que foram avaliados pelosdois usuários. Em seguida é calculada a quantidade de itens avaliados por um usuário eque não foram avaliados pelo outro. E por fim é calculada a quantidade de itens que nãoforam avaliados por nenhum dos dois usuários [14, 53, 34].

Dessa forma, considere a matriz de contingência k2× 2 que relaciona os itensavaliados por dois usuários u1 e u2, seja:


• k[u1,u1] = a quantidade de itens que sofreram avaliação tanto do usuário 1 quantodo usuário 2 ( usuários para os quais se quer calcular a similaridade entre eles).• k[u1,u2] = a quantidade de itens avaliados pelo usuário 2, mas que não foram

avaliados pelo usuário 1.• k[u2,u1] = o número de itens avaliados pelo usuário 1, mas que não foram avaliados

por usuário 2.• k[u2,u2] = o número de itens avaliados ( por algum usuário) mas que não foram

avaliados por usuário 1 e não foram avaliados pelo usuário 2.

A razão correspondente ao log-likelihood entre o usuário 1 (u1) e o usuário 2(u2) é dada por:

RlogLikelihood(u1,u2) =

entropia(k[u1,u1],k[u1,u2],k[u2,u1],k[u2,u2])

−[entropia(k[u1,u1],k[u1,u2])+ entropia(k[u2,u1],k[u2,u2])

+entropia(k[u1,u1],k[u2,u1])+ entropia(k[u1,u2],k[u2,u2])]

(3-12)

Por sua vez, a entropia mencionada na Equação 3-12 é computada pela Equação3-13.

entropia(a1,a2, . . . ,an) = xLogx(n

∑i=1

ai)−n

∑i=0

xLogx(ai) (3-13)

A medida de similaridade entre os usuários u1 e u2 é dada por:

log− likelihood(u1,u2) = 1.0−1.0/(1.0+2∗Rloglikelihood(u1,u2)) (3-14)

Dessa forma, também é possível estabelecer a probabilidade de que um usuáriovisualize cada item através de uma função de decaimento exponencial demonstrada naEquação 3-15, onde:

• wua,uu é a correlação do usuário-alvo ua com um determinado usuário uu;• M [ua][ia] é a avaliação que o usuário-alvo ua deu para o item-alvo ia;• d é a classificação padrão (geralmente uma avaliação; não-comprometedora, ou

ligeiramente negativa);• α é a meia-vida. A meia-vida é o posto do item na lista, de tal forma que há uma

chance de 50% que o usuário irá visualizar esse item.

w(a,u) = ∑i

max(M [ua][ia]−d,0)2(i− j)/(α−1)

(3-15)


3.2.4 Métodos de Predição

Adomavicius et. al. [1], mostra que o terceiro passo dos algoritmos baseadosem memória, que corresponde ao cálculo da predição, é realizado com a agregação dasavaliações dos k vizinhos mais próximos. No caso dos métodos baseados em usuários apredição pode ser expressa de forma genérica pela Equação 3-16, onde agrus é algumaforma de agregação das avaliações dadas ao item-alvo ia pelos k vizinhos mais próximosdo usuário-alvo ua.

p(ua, ia) = agrus(M [u][ia]),u ∈ Vk(ua) (3-16)

No caso do método baseado em itens a predição pode ser expressa de forma genéricapela Equação 3-17, onde agrit é alguma forma de agregação das avaliações dadas pelousuário-alvo ua aos itens do conjunto de k itens vizinhos mais próximos do item-alvo ia.

p(ua, ia) = agrit(M [ua][i]), i ∈ Vk(ia) (3-17)

Adomavicius et. al. [1] e Desrosier et al. [41, Ch. 4], apresentam quatro opçõespara serem utilizadas como agregação agr nas Equações 3-16 e 3-17. Essas quatro opçõessão as mais utilizadas na literatura. A agregação mais trivial é a média aritmética simples.A Equação 3-18 mostra como essa agregação pode ser utilizada com métodos baseadosem usuário e a Equação 3-19 mostra aplicação da agregação no método baseado em itens.

p(ua, ia) =∑u∈Vk(ua) M [u][ia]

k(3-18)

p(ua, ia) =∑i∈Vk(ia)

M [ua][i]k

(3-19)

O problema da agregação por média aritmética é que esta agregação não considerao grau de similaridade com os vizinhos. Uma agregação alternativa é o uso de umamédia ponderada pelo valor da função de similaridade. A Equação 3-20 expressa amédia ponderada utilizada nos métodos baseados em usuário, enquanto a Equação 3-21apresenta a média ponderada utilizada nos métodos baseados em itens.

p(ua, ia) =∑u∈Vk(ua) M [u][ai]simus(ua,u)

∑u∈Vk(ua) simus(ua,u)(3-20)

p(ua, ia) =∑i∈Vk(ia)

M [ua][i]simit(ia,i)

∑i∈Vk(ia)simit(ia,i)

(3-21)

Em ambas as agregações apresentadas anteriormente as avaliações são consideradasdiretamente. Entretanto, o resultado das agregações pode ser muito distinto do perfilde avaliações do usuário-alvo ou do item-alvo. Uma forma de utilizar informação doperfil de comportamento das avaliações é incluir no cálculo da agregação a média das


avaliações dadas pelo usuário alvo, no caso dos métodos baseados em usuário, ou a médiadas avaliações dos itens, no caso de métodos baseados em itens. Essa nova agregação éexpressa nas Equações 3-22 e 3-23.

p(ua, ia) = M [ua][∗]+∑u∈Vk(ua) M [u][ia]simus(ua,u)


Na Equação 3-22 M [ua][∗] é a média das avaliações feitas pelo usuário-alvo ua

e na Equação 3-23 M [∗][ia] corresponde a média das avaliações dadas ao item-alvo ia.

p(ua, ia) = M [∗][ia]+∑i∈Vk(ia)

M [ua][i]simit(ia,i)


(3-23)

As Equações 3-23 e 3-22 não consideram o fato que usuários podem utilizarvalores diferentes para avaliar o mesmo nível de satisfação em relação a um item. Porexemplo, um usuário pode dar o valor máximo de avaliação para apenas poucos itens queele gosta, enquanto outro usuário, menos rigoroso, pode avaliar com o valor máximo todosos itens que ele aprova. Esse desnível entre valores de avaliação é geralmente resolvidoutilizando-se valores normalizados das notas em vez de usar os valores originais. Herloc-ker et. al. [33] propôs a normalização Z-score com essa finalidade. A Equação 3-24 mostraessa agregação adaptada para o método baseado em usuário e a Equação 3-25 apresentaa agregação adaptada para o o método basedo em item. Ambas levam em consideração avariância das notas das avaliações. Na Equação 3-24, σu corresponde à variância das ava-liações dadas pelo usuário u e na Equação 3-25, σi representa a variância das avaliaçõesrecebida pelo item i.

p(ua, ia) = M [ua][∗]+σua

∑u∈Vk(ua)

[(M [u][ia]−M [ua][∗]

σu

)]simus(ua,u)


p(ua, ia) = M [∗][ia]+σia

∑i∈Vk(ia)

[(M [ua][ia]−M [∗][ia]

σi

)]simit(ia,i)


(3-25)

CAPÍTULO 4Item-Based-ADP

O algoritmo Item-Based-ADP é um método de filtragem colaborativa baseadoem memória, mais expecificamente da classe dos algoritmos baseados na similaridadede itens 3.2.2. O Item-Based-ADP é uma melhoria do algoritmo Item-based tradicional.Foram introduzidas quatro adaptações para este propósito1. Essas adaptações melhoramo tempo de execução e a acurácia sem perder os benefícios dos métodos baseados emmemória, como a simplicidade e facilidade de se explicar as recomendações.

Para os sistemas de recomendação baseados em memória a seleção de bonsvizinhos é fundamental. Para isso é necessário o uso de uma medida de similaridadeadequada. Empiricamente, como apresentaremos no Capítulo 5, notamos que o uso docoeficiente de correlação de Pearson apresenta os melhores resultados para o algoritmobaseado em similaridade de itens (Item-based).

Entretanto, mesmo sendo a medida que apresentou os melhores resultados,a correlação de Pearson ainda apresenta fortes limitações. Existem casos onde doiselementos, representados por vetores, são muito diferentes e ainda assim apresentam umaforte correlação. A Tabela 4.1 apresenta um exemplo desse fenômeno. O Item 1 e o Item 2apresentam um coeficiente da correlação de Pearson igual a 1,0, embora semanticamenteapresentem avaliações bem diferentes pelos usuários do sistema. Já o Item 1 e o Item3 são bastante parecidos em termos de avaliações, porém apresentam um coeficiente dacorrelação de Pearson igual a 0,2.

Usuário 1 Usuário 2 Usuário 3 Usuário 4 Usuário 5 Usuário 6 Usuário 7 Usuário 8Item 1 4 4 4 5 5 5 5 5Item 2 1 1 1 2 2 2 2 2Item 3 4 4 4 5 5 5 5 2

Tabela 4.1: Exemplo para mostrar problema no uso do coeficienteda correlação de Pearson como medida de similari-dade.

O uso da correlação de Pearson como medida de similaridade faz com que ossistemas permitam a seleção de muitos vizinhos falso-positivos. O cálculo da similaridade

1O ADP vêem de ADaPtaçoes.

4.1 Fluxograma 54

além de impactar diretamente na acurácia das predições, é o passo do algoritmo quetem o maior custo computacional. Normalmente este cálculo precisa ser realizado entretodos os elementos. Por exemplo, no algoritmo baseado em itens é necessário calcular asimilaridade entre item-alvo ia e cada um dos outros itens do sistema que o usuário-alvotenha avaliado.

As adaptações propostas no algoritmo Item-Based-ADP são as seguintes:

1. Considerar um par de itens como possivelmente similares apenas quando a dife-rença entre as médias das avaliações dos dois itens for inferior a um limiar δ;

2. Selecionar apenas vizinhos que tiverem valor de similaridade superior a 50% dointervalo permitido pela medida de similaridade;

3. Normalizar os valores de similaridade;4. Possibilitar a repetição de informação quando a quantidade de vizinhos k não é

atingida.

No restante desse capítulo essas adaptações são melhores explicadas de duasformas diferentes, uma baseado em fluxograma e outra de forma algorítmica.

4.1 Fluxograma

Nesta seção é apresentado o fluxograma do novo método, Item-Based-ADP. AFigura 4.1 mostra este fluxograma. O algoritmo proposto neste trabalho tem como base oalgoritmo baseado em similaridade de itens, descrito na Seção 3.2.2. Nas seções seguintessão explicadas cada uma das etapas adicionadas pelo novo método.

Neste fluxograma os itens que estão no conjunto de treino são os possí-veis vizinhos do item-alvo ia para o usuário-alvo ua. Esse conjunto será chamado dePossib_Neighs. Inicialmente esse conjunto inicia com todos os itens que o usuário-alvojá avaliou, exceto o item-alvo. Formalmente Possib_Neighs = i ∈ Iua|i 6= ia. Os itens pre-sentes neste conjunto serão os itens que poderão ser utilizados para fazer a predição doitem-alvo.

ADP 1 - Considerar um par de itens como possivelmente similaresapenas quando a diferença entre as médias das avaliações dos doisitens for inferior a um limiar δ

A primeira adaptação consiste na introdução de uma etapa de filtragem antes docálculo de similaridade ser feito. Esta etapa de filtragem tem dois objetivos:

• Reduzir o número de itens no conjunto Possib_Neighs. Assim, reduzirá a quanti-dade de cálculos de similaridade a serem computados.

4.1 Fluxograma 55

Figura 4.1: Fluxograma do algoritmo Item-Based-ADP.

• Remover itens falso-positivos do conjunto Possib_Neighs.

Com base nos estudos, ficou evidente que o primeiro passo do algoritmo base-ados em itens, isto é, o cálculo da similaridade entre o item-alvo ia e os outros itens dosistema, corresponde ao ponto de gargalo para o processo como um todo. Na verdade,esse passo afeta não só a eficiência do algoritmo baseado em itens, mas também em suaacurácia.

As medidas mais utilizadas para computar as semelhanças são a correlação dePearson e o Coseno. Porém, estas duas medidas possuem a limitação na identificação dositens mais semelhantes com o item-alvo, apresentada na seção anterior. Assim, ambasas medidas tendem a produzir vizinhos próximos “falso-positivos”. Isto implica quealguns itens que não contribuem para a fase de predição positivamente estão incluídos noconjunto vizinhos mais próximos, devido à esta limitação das medidas de similaridade.Outras medidas foram apresentadas na Seção 3.2.3.

O cálculo da similaridade pode fazer com que os algoritmos baseados em memó-ria atinjam um alto custo computacional, uma vez que para selecionar os vizinhos maispróximos é preciso comparar a similaridade entre o usuário/item-alvo e os outros usuá-rios/itens na matriz de avaliações. Essas matrizes são, em geral, enormes e a computação

4.1 Fluxograma 56

é feita sob demanda. Desta forma, os algoritmos baseados em memória não são escalá-veis. Assim, o uso destes algoritmo podem se tornar inviáveis em grandes matrizes deavaliações.

A etapa de filtragem é baseada na seguinte ideia: dois itens que têm médiadas suas avaliações muito distintas são, provavelmente, muito diferentes para seremconsiderados vizinhos. Assim, introduzimos um limiar δ e calculamos o valor absolutoda diferença entre as médias das avaliações recebidas pelo item-alvo ia e as médias dasavaliações dos itens no conjunto Possib_Neighs. O filtro é definido pela Equação 4-1.

f iltro = |M [∗][ia]−M [∗][ j]| (4-1)

Onde M [∗][ j] é a média das avaliações do item j. O f iltro deve ser menorou igual ao limiar δ para que um item j seja mantido no conjunto Possib_Neighs. Porexemplo, assumindo δ igual a 0.5, calcula-se a medida de similaridade tradicional somentepara os itens que tiverem os valores do f iltro menor ou igual a 0.5.

O custo computacional deste primeiro filtro é quase irrelevante e pode reduzirdrasticamente o conjunto Possib_Neighs. Este conjunto tende a se reduzir conforme ovalor de δ vai diminuindo. Assim, o conjunto tende a ser muito menor do que o conjuntoinicial. Consequentemente, essa filtragem tende a reduzir drasticamente o número decálculos de similaridade.

ADP 2 - Selecionar apenas vizinhos que tiverem valor de similaridadesuperior a 50% do intervalo permitido pela medida de similaridade

A segunda melhoria proposta neste trabalho foi a seleção de vizinhos que apenasmostram uma semelhança maior que a metade possível. Em outras palavras, enquanto oalgoritmo está em fase de calcular a similaridade entre os itens do conjunto Possib_Neighs

e o item-alvo, os itens que mostram grau de similaridade menor do que ou igual a metadepermitida pela medida são descartados do conjunto.2 Sendo esta melhoria a segundaadaptação proposta.

Isso reduz ainda mais a cardinalidade do conjunto Possib_Neighs para melhorara eficiência da próxima etapa do algoritmo, que é a ordenação dos elementos do conjuntoPossib_Neighs, estabelecida pela ordem decrescente de similaridade. Na etapa de cálculoda predição da avaliação dada ao item-alvo ia para o usuário-alvo ua, usamos a Equação3-23.

2Utilizando como medida de similaridade a correlação de Pearson, onde os valores variam de [−1,1],todos os não positivos são descartados.

4.1 Fluxograma 57

ADP 3 - Normalizar os valores de similaridade

A terceira melhoria proposta foi uma normalização dos valores de similaridadeentre os itens que ainda estão no conjunto Possib_Neighs e o item-alvo ia.

Como pode ser visto na Equação 3-23, se o grau de similaridade entre os itens eo item-alvo for muito baixo (próximo de zero), estes itens vizinhos não adicionam muitovalor para a predição final 3. Quando isso acontece, a predição é feita, basicamente, com amédia das avaliações do item-alvo. Isso remove o senso de colaboração do algoritmo, poisnão utiliza as avaliações dos outros itens para gerar a predição para o item-alvo. Devido aisso, foi proposto um ajuste nos valores de similaridade. Nós adicionamos um valor α aograu de similaridade de cada item no conjunto Possib_Neighs. O valor de α é dado pelaEquação 4-2.

α = 1−Max(sim) (4-2)

Onde Max() é a função que retorna o valor máximo em um vetor, e sim é o vetorque contém o grau de similaridade dos itens do conjunto Possib_Neighs. Esse ajuste, forçao algoritmo a ser mais colaborativo. Isto constitui a terceira adaptação.

Antes de aplicar a equação de predição, é necessário selecionar os k itens maissimilares no conjunto Possib_Neighs. Em [18], foi demonstrado que um bom valor parak é entre 30 e 80, dependendo da coleção. Neste trabalho, o valor de k foi variado de 10 a120. Assim, o conjunto Possib_Neighs deve ter uma cardinalidade maior ou igual a k.

ADP 4 - Possibilitar a repetição de informação quando a quantidadede vizinhos k não é atingida

Devido aos dois filtros previamente aplicados (ADP 1 e ADP 2), é comum que ovalor da cardinalidade do conjunto Possib_Neighs seja inferior à k.

Para esses casos, foi proposta uma quarta e última melhoria. Seja C a cardinali-dade do conjunto Possib_Neighs. Os C/2 itens mais similares no conjunto são duplicados.

Com isso, a cardinalidade do conjunto pode ficar igual a 3C/2. Não é duplicadomais do que C/2 itens, pois caso todos sejam duplicados, o valor final da predição seriaigual ao valor obtido com apenas os C itens iniciais.

Com esse novo conjunto, já ordenado pela similaridade, se usa os k maissimilares. Dessa forma, os itens menos similares que estavam inicialmente no conjuntopodem ser substituídos pelas cópias dos mais similares, produzindo uma melhor acurácia.

3exceto quando o somatório de todas as similaridade produzem, também, um valor próximo de zero.Porém isso é uma exceção devido ao número de vizinhos selecionados

4.2 Algoritmo 58

Pode ocorrer que esta nova cardinalidade ainda seja inferior a k. Nesses casos seutiliza a informação dos 3C/2 itens do conjunto. Com esses dados é formado o conjuntoVk(ia). Finalmente, a previsão é calculada de acordo com a Equação 3-23.

4.2 Algoritmo

Nesta seção é apresentado o algoritmo para implementanção do Item-Based-ADP. Esse algoritmo é apresentado logo abaixo.

No algoritmo 4.1 a variável Possib_Neighs é uma matriz de duas colunas. Essaestrutura serve para armazenar os itens similares ao item-alvo para o qual queremosrealizar a predição de sua avaliação. Na primeira coluna é armazenado o item julgadocomo similar e na segunda coluna é armazenado o grau de similaridade que o itemapresenta em relação ao item-alvo. Na função ORDENA() é realizada uma ordenaçãoem função da similaridade, deixando os itens mais similares mais próximos da posição 0.

Quanto maior é o valor do δ mais dados são considerados como possíveissimilares, deixando mais próximo do algoritmo original.

O primeiro “para” (linha 4) é responsável pelas primeiras duas adaptaçõespropostas. Neste instante, o conjunto de vizinhos a ser utilizado na predição. Nestepreenchimento já é realizado um primeiro filtro usando o δ. Os itens que passam pelofiltro (linha 5), tem a sua similaridade calculada em relação ao item-alvo ia. O segundofiltro ocorre no segundo “if” (linha 7). Neste filtro, um item i só é considerado comovizinho de ia caso obtenha um grau de similaridade maior que 50% do total permitidopela função de similaridade utilizada. Neste algoritmo, estamos usando a correlação dePearson como medida de similaridade, essa medida aceita valores de [−1,+1], portanto,50% corresponde a 0.0.

O segundo “para” (linha 14) é responsável pela quarta adaptação proposta.Neste passo do algoritmo, caso não tenha sido possível selecionar k vizinhos, a metademais similar dos vizinhos são repetidos na estrutura Possib_Neighs. Isso faz com que oalgoritmo aumente a importância dos itens mais similares encontrados. Esse laço podeser interrompido antes de repetir todos os itens da metade mais similar caso o conjuntoPossib_Neighs atinja uma cardinalidade igual k.

4.2 Algoritmo 59

Algoritmo 4.1: Item-Based-ADP

Entrada: Matriz M [][], Item ia, Usuário ua, Número de vizinhos k, δ.Saída: Predição do sistema para a nota do usuário ua no item ia.

1 //[coluna 1: item similar] [coluna 2: grau de similaridade]2 Possib_Neighs[][2];3 iteracao← numSimilares← 0;4 para cada Item i ∈ Iua faça5 se |M [∗][ia]−M [∗][i]| <= δ então6 s← calculaSimilaridade(ia, i);7 se s > 0.0 então8 Possib_Neighs[numSimilares][0]← p;

Possib_Neighs[numSimilares][1]← s;numSimilares← numSimilares+1;

9 fim10 fim11 fim12 ORDENA(Possib_Neighs);13 lim← numSimilares/2;14 para j de 0 ATÉ lim && numSimilares < k faça15 Possib_Neighs[numSimilares][0]← Possib_Neighs[ j][0];

Possib_Neighs[numSimilares][1]← Possib_Neighs[ j][1];numSimilares← numSimilares+1;

16 fim17 acres← 1−Possib_Neighs[0][1];18 predicao←M [∗][ia];19 soma← somaPeso← 0;20 para j de 0 ATÉ k faça21 soma← soma+((M[ua][Possib_Neighs[ j][0]]−

M [∗][iPossib_Neighs[ j][0]])∗ (Possib_Neighs[ j][1]+acres));

22 somaPeso← somaPeso+(Possib_Neighs[ j][1]+acres);

23 fim24 Retorne predicao+(soma/somaPeso);

O cálculo da predição inicia-se na linha 17 do algoritmo, utilizando as infor-mações dos itens similares. O cálculo apresentado no algoritmo não é o mesmo cálculoutilizado na versão original do algoritmo baseado em itens similares (Item-based) [74].Em vez disso, é utilizado o cálculo da Equação 3-23. Esta equação apresenta melhoresresultados do que a equação tradicional. Além disso, é aplicada a terceira adaptação pro-

4.2 Algoritmo 60

posta (normalização do grau de similaridades), aplicando um acréscimo (variável “acres”)na similaridade de todos os itens utilizados como vizinhos. Esse acréscimo é calculado(linha 17) de tal forma que, quando adicionado a similaridade do item mais similar aoitem-alvo, atinja o maior grau de similaridade possível da medida de similaridade, nestecaso 1.0.

CAPÍTULO 5Experimentos

Neste capítulo é apresentada uma avaliação experimental do algoritmo Item-Based-ADP em duas coleções tradicionais usadas para avaliar algoritmos de recomenda-ção. São apresentados os resultados de acurácia e tempo de execução do método propostoalém de comparações com os algoritmos de base como o Item-based (apresentado na Se-ção 3.2.2), User-based (apresentado na Seção 3.2.1) e o melhor algoritmo no atual estadoda arte baseado em modelo, RegSVD (Apresentado na Seção 3.1.1).

Esse capítulo é estruturado da seguinte forma: Na Seção 5.1 são descritas asconfigurações dos experimentos, como a descrição de cada conjunto de teste, o ambienteonde foram executados os testes, a metodologia utilizada e as métricas utilizadas nosexperimentos.

Na Seção 5.2 são apresentados os resultados obtidos nos exeperimentos. Essesresultados são apresentados na sequência descrita pela metodologia apresentada na Seção5.1.3. Cada subseção desta seção retrata os resultados de um dos conjuntos de dados.

5.1 Configurações dos testes

5.1.1 Conjunto de dados

MovieLens_100k: Este conjunto de dados é provido pela MovieLens1. O sitefoi criado por GroupLens Research na Universidade de Minnesota. Ele contém 100,000avaliações em 1,682 videos (itens) de 943 usuários. Cada usuário avaliou pelo menos 20filmes, com avaliações variando de uma a cinco estrelas (cinco estrelas sendo a melhoravaliação e uma sendo a pior). A densidade de avaliações deste conjunto de dados é de6,30%.

Netflix_3m1k: Este conjunto de dados é provido pelo Netflix2. ele contém56,136 avaliações em 1,000 filmes (itens) de 4,427 usuários. As avaliações variam de

1http://www.movielens.org2http://www.netflixprize.com

5.1 Configurações dos testes 62

uma a cinco estrelas, cinco sendo a melhor e um sendo a pior. A densidade de avaliaçõesdeste conjunto de dados é de 1,27%.

5.1.2 Ambiente de execução

Experimentos foram executados em uma máquina virtual com dois v-CPUs,funcionando a 2.4GHz, com 8 GB RAM, com o sistema operacional Ubuntu 12.04 LTS.Essa máquina virtual opera em uma máquina servidora Dell PowerEdge M610 com doisprocessadores E5620 (quad core 2.40 GHz, com hyperthread), 96 GB RAM e com doisdiscos SSD, cada um contém 100GB.

5.1.3 Metodologia

Primeiramente foram realizados testes para definir os melhores parâmetros paraalgoritmo. Esses testes foram executados cinco vezes e os resultados reportados referem-se a média aritmética dessas execuções. Com os parâmetros já selecionados, foramexecutados os testes de comparação entre os algoritmos e os de significância estatística, osquais foram executados 100 vezes para dar garantias estatísticas da melhora de acuráciautilizando a métrica MAE.

Para realizar os testes de significância estatísticas foi utilizado o teste de Wilco-xon pareado [28]. Este é um teste de hipótese estatístico não-paramétrico utilizado paracomparar duas amostras pareadas relacionadas.

Foram testados e avaliados três algoritmos baseados em memória e um baseadoem modelo. Os algoritmos baseados em memória foram: o Item-based tradicional, tratadocomo IB, o User-based, tratado como UB e o nosso algoritmo Item-Based-ADP, tratadocomo IBA. O algoritmo baseado em modelo selecionado foi o regularized SVD, tratadocomo regSVD. Foram utilizadas as implementações disponíveis no toolkit PREA3 dosalgoritmos UB, IB e RegSVD. O algoritmo IBA também foi implementado com estetoolkit. Os parâmetros utilizados no regSVD foram os propostos pelo próprio PREA,assim como as implementações dos algoritmos IB e UB. O valor padrão utilizado parao δ no algoritmo IBA é de 0,8.

A fim de testar a capacidade de cada algoritmo para lidar com diferentes níveisde densidade da matriz de avaliações, realizamos diversas divisões das coleções em doisconjuntos, um conjunto de treino e um de teste. O tamanho do conjunto de teste foivariado, começando com 20% do tamanho do conjunto original e aumentando de 10%em 10% até atingir um valor de 90% . Essas porcentagens são denominadas test ratios

neste texto. Desta forma, foram testados oito test ratios diferentes.

3http://prea.gatech.edu

5.1 Configurações dos testes 63

Para cada divisão, foram escolhidos elementos (células valoradas) de formaaleatória da matriz de avaliações original, os quais são copiados para uma outra matriz deteste com a mesma cardinalidade, inicialmente vazia. Isso é feito até que a porcentagemda quantidade de elementos na matriz de teste atinja a porcentagem do test ratio. Oselementos restantes são copiados para a matriz de treino. A Figura 5.1 ilustra de formasimplificada esse processo, utilizando um test ratio de 40%. Em seguida, foram aplicadoscada um dos algoritmos avaliados usando essas matrizes de treino e teste.

Figura 5.1: Exemplo do processo de divisão da matriz de avalia-ções nas matrizes de teste e treino.

Para definir qual medida de similaridade utilizar em cada algoritmo baseado emmemória, foram testados as seguintes medidas: correlação de Pearson, Cosseno, Cossenoajustado e log-Likelihood. Esses testes foram executados sob a condição de 50 vizinhose um test ratio de 20%. Para dar o mesmo tratamento a cada algoritmo, a melhor medidapara cada um sob estas condições foi utilizado nos demais testes.

Ainda para os algoritmos baseados em memória, foram experimentadas varia-ções no número k de vizinhos. Este número foi variado na faixa de 10 a 120, tomando osvalores: 10, 30, 50, 80 e 120. Isso foi realizado para selecionar a melhor quantidade devizinhos para cada algoritmo com a medida de similaridade escolhida anteriormente.

Esse teste para selecionar a melhor quantidade de vizinhos foi executado com2 test ratios: 20% e 90%. O melhor valor de k para o test ratio de 20% é utilizado nos

5.2 Resultados 64

demais testes que forem executados com um test ratio menor ou igual a 50%. O melhorvalor de k para o test ratio de 90% é utilizado para os testes com test ratio maior que 50%.

Foram feitos experimentos para escolher o melhor valor para o parâmetro δ doalgoritmo IBA. Esses experimentos foram feitos utilizando-se dois test ratios: 20% e 90%.A estratégia do uso do δ foi a mesma usada na escolha do número de vizinhos k.

Na fase de predição, geralmente, os trabalhos adotam a Equação 3-21 parao algoritmo IB. Porém, utilizou-se a Equação 3-23, pois esta atinge um melhor nívelde acurácia, isso foi evidenciado nos resultados dos testes. Assim, a Equação 3-23 foiutilizada tanto para o algoritmo IB quanto para o IBA. Para o algoritmo UB foi utilizadaa Equação 3-22, visando uma melhor acurácia.

O algoritmo RegSVD é um algoritmo baseado em modelo e é considerado omais eficiênte preditor em [47]. Esse algoritmo foi incluído nos experimentos afim decomparar seu erro de predição com o erro do nosso algoritmo proposto IBA. Entretanto,não foi comparado o tempo de execução do regSVD com qualquer algoritmo baseadoem memória (incluíndo o IBA). Em vez de se considerar o tempo de execução dessealgoritmo, considerou-se o tempo de construção do modelo. Isso porque algoritmosbaseados em modelos e algoritmos baseados em memória seguem duas abordagens bemdistíntas.

Por fim, foi realizada uma análise sobre a melhora de cada adaptação propostano algoritmo IBA. Isso foi realizado utilizando os parâmetros selecionados pelos testesanteriores.

Dentre as diversas medidas de avaliação apresentadas na Seção 2.3, foramutilizas duas para medir a acurácia dos sistemas: MAE e RMSE. Essas são as métricasmais utilizadas na literatura para este propósito. A fim de medir a eficiência de cada umdos algoritmos analisados, registrou-se o tempo de execução (medido em segundos) decada algoritmo ao longo das predições nas avaliações do conjunto de teste. A seguir sãoreportados os resultados de cada conjunto de dados usando a metodologia e medidas deavaliações descritas neste capítulo.

5.2 Resultados

Nesta seção são apresentados os resultados de experimentos realizados nasduas coleções apresentadas na Seção 5.1.1. São reportados os resultados das avaliaçõesem termos de erro e eficiência para cada coleção individualmente. Primeiramente sãoapresentados os resultados para a coleção MovieLens_100k e depois para a coleçãoNetflix_3m1k.

5.2 Resultados 65

5.2.1 MovieLens_100k

Os primeiros experimentos foram conduzidos para definir os melhores parâme-tros a serem utilizados em cada algoritmo. Isso foi feito para atingirem uma melhor acu-rácia e um melhor tempo de execução. Os resultados são sempre reportados nas três mé-tricas: MAE, RMSE e tempo de execução.

Seleção da medida de similaridade

O gráfico da Figura 5.2 apresenta o MAE para os três algoritmos baseados emmemória utilizando quatro medidas de similaridade diferentes. O gráfico da Figura 5.3apresenta o RMSE para os três algoritmos com as quatros medidas de similaridade. Jáo gráfico da Figura 5.4 apresenda a métrica de tempo de execução dos três algoritmosutilizando cada uma das quatro medidas de similaridade.

Figura 5.2: MAE para diversas medidas de similaridade nos algo-ritmos User-based, Item-based e Item-Based-ADP.

Figura 5.3: RMSE para diversas medidas de similaridade nos al-goritmos User-based, Item-based e Item-Based-ADP.

Fica claro que o uso do cosseno ajustado é uma péssima escolha, pois requermuito mais tempo que qualquer outra medida de similaridade além de apresentar o

5.2 Resultados 66

Figura 5.4: Tempo de execução para diversas medidas de simila-ridade nos algoritmos User-based, Item-based e Item-Based-ADP.

maior erro tanto em termos de MAE quanto em termos de RMSE. As medidas desimilaridade mais atrativas foram o coeficiente de Pearson e a log-Likelihood em todosos três algoritmos. A primeira por produzir o melhor resultado em termos de acurácia e asegunda por apresentar o melhor tempo de execução.

Assim, foi selecionado, para os demais experimentos, as duas medidas de simi-laridade, verificando os resultados com cada uma delas.

Seleção do número de vizinhos

O próximo parâmetro a ser decidido é o número de vizinhos que cada algoritmoselecionará para calcular as predições. Para isso, os algoritmos foram testados nos doisníveis extremos de test ratios (0,2 e 0,9).

As Figuras 5.5 e 5.6 apresentam os gráficos de MAE para os algoritmos emcada nível de test ratio. As Figuras 5.7 e 5.8 apresentam os gráficos com os resultadosde RMSE em cada nível de test ratio. Por último, as Figuras 5.9 e 5.10 apresentam osgráficos do tempo de execução para os três algoritmos baseados em similaridade em cadanível de test ratio.

Os resultados sobre as métricas MAE e RMSE tiveram o mesmo comportamento,porém em escalas diferentes. Esse resultados evidenciam que para esse conjunto de dadosos três algoritmos apresentam melhores resultados, em termos de acurácia, utilizando 30vizinhos. Segundo os experimentos, este é o valor ótimo de k independe da esparsidadedo conjunto de dados. Analisando os resultados obtidos no test ratio de 0,9, percebe-seque a acurácia não se altera quando aumenta-se o número de vizinhos acima de 30. Issosignifica que neste test ratio não existem mais do que 30 possíveis vizinhos.

O tempo de execução praticamente não é afetado pela variação do k. Poiso k apenas define quantos vizinhos serão utilizados na fórmula de predição. Sendo

5.2 Resultados 67

Figura 5.5: MAE variando-se o número de vizinhos nos três al-goritmos baseados em memória com test ratio de 0,2,utilizando-se as duas medidas de similaridade previa-mente selecionadas.

Figura 5.6: MAE variando-se o número de vizinhos nos três al-goritmos baseados em memória com test ratio de 0,9,utilizando-se as duas medidas de similaridade previa-mente selecionadas.

Figura 5.7: RMSE variando-se o número de vizinhos nos três al-goritmos baseados em memória com test ratio de 0,2,utilizando-se as duas medidas de similaridade previa-mente selecionadas.

5.2 Resultados 68

Figura 5.8: RMSE variando-se o número de vizinhos nos três al-goritmo baseados em memória com test ratio de 0,9,utilizando-se as duas medidas de similaridade previa-mente selecionadas.

Figura 5.9: Tempo de execução variando-se o número de vizinhosnos tês algoritmos baseados em memória com test ra-tio de 0,2, utilizando-se as duas medidas de similari-dade previamente selecionadas.


5.2 Resultados 69

necessário ainda calcular a similaridade entre todos os possíveis vizinhos. O algoritmoque é mais afetado por essa variação do k é o IBA, devido a adaptação 2 (normalizaçãoda similaridade). Mesmo assim o melhor valor encontrado foi 30. Isso foi observadoindependente da medida de similaridade utilizada. Dessa forma, foi definido k igual a30 sendo o melhor valor de vizinhos.

Seleção do limiar Delta (δ)

O último parâmetro a ser definido se refere apenas ao método proposto (IBA),que é o δ aplicado na primeira adaptação proposta pelo algoritmo. Nesses experimentoso δ foi variado de 0.5 a 1.2 nos dois extremos de test ratio,20% e 90%, utilizando ambasas medidas de similaridade selecionadas anteriormente.

As Figuras 5.11, 5.12 e 5.13 mostram os gráficos das métricas MAE, RMSE etempo de execução respectivamente com test ratio igual a 0.2.

Figura 5.11: MAE variando-se o valor de δ no algoritmo IBA comtest ratio de 0,2.

Figura 5.12: RMSE variando-se o valor de δ no algoritmo IBA comtest ratio de 0,2.

5.2 Resultados 70

Figura 5.13: Tempo de execução variando-se o valor de δ no algo-ritmo IBA com test ratio de 0,2.

A partir desses resultados observa-se que o melhor δ neste test ratio é de 0,8para este conjunto de dados. Quanto menor o valor do δ mais dados são filtrados. Osresultados, em termos de acurácia, mostram que é interessante filtrar alguns dados, porémnão é interessante ser tão rígido nesse filtro. Foi definido então como valor ótimo 0,8.

Em termos de tempo de execução, como já esperado, quanto mais rígido é estefiltro, menor é o tempo de execução pois a similaridade é calculada em menos dados.

Analisando o δ em um ambiente de test ratio igual a 0,9 percebe-se que quantomaior o valor adotado, melhor é o nível de acurácia. Isso pode ser explicado pela naturalfalta de informação presente neste ambiente. Obviamente, quanto maior o valor de δ maioré o tempo de execução. As Figuras 5.14, 5.15 e 5.16 mostram os gráficos das métricasMAE, RMSE e tempo de execução respectivamente com test ratio igual a 0.9.


Com esta quantidade de dados, o tempo de execução é curto de toda forma, nãosendo o fator mais importante. Os gráficos apontam que quanto maior a valor adotadopara o δ melhor é a acurácia. Assim, adotou-se como parâmetro o valor de 1,2.

5.2 Resultados 71



Comparação dos algortimos

Para verificar o desempenho dos algoritmos em diversos níveis de densidade,foram conduzidos testes sob todos os test ratios (0,2 - 0,9). Esses testes foram executadosde forma que todos os algoritmos estivessem com os melhores parâmetros selecionadosnos testes anteriores.

A Tabela 5.1 reporta os resultados dos algoritmos utilizando-se como medida desimilaridade a medida que atinge melhor acurácia. Já a Tabela 5.2 reporta os resultadosdos algoritmos utilizando-se a medida de similaridade que dá prioridade ao ganho notempo de execução. Para esse conjunto de dados essas medidas são correlação de Pearsone log-Likelihood respectivamente para todos os algoritmos baseados em memória.

Nas Tabelas 5.1 e 5.2 o tempo de execução dos algoritmos baseados em memóriasão referentes ao tempo gasto nas predições enquanto o tempo de execução do algoritmoRegSVD se refere ao tempo de treinamento que ele tem, por ser baseado em modelo, istoé, o tempo de modelagem.

5.2 Resultados 72

Test Ratio0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

MA

E

UB 0.7290 0.7350 0.7444 0.7515 0.7640 0.7836 0.8204 0.9139

IB 0.7131 0.7207 0.7301 0.7381 0.7502 0.7711 0.8067 0.8901

IBA 0.7116 0.7188 0.7275 0.7345 0.7456 0.7610 0.7853 0.8595

RegSVD 0.7243 0.7328 0.7463 0.7571 0.7730 0.7979 0.8295 0.9038R

MSE

UB 0.9340 0.9424 0.9530 0.9618 0.9770 1.0021 1.0498 1.1649

IB 0.9108 0.9204 0.9322 0.9423 0.9575 0.9857 1.0352 1.1445

IBA 0.9104 0.9193 0.9299 0.9387 0.9505 0.9705 1.0048 1.1054

RegSVD 0.9144 0.9256 0.9425 0.9550 0.9746 1.0055 1.0469 1.1489

Tem

po

UB 38 33 29 24 20 16 11 5

IB 188 211 210 181 141 92 49 17

IBA 154 173 175 154 139 100 61 26

RegSVD 924 802 700 593 467 363 253 136

Tabela 5.1: Análise dos algoritmos variando-se o test ratiocom correlação de Pearson como medida de similari-dade.

Test Ratio0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

MA

E

UB 0.7401 0.7432 0.7496 0.7546 0.7616 0.7735 0.7960 0.8706

IB 0.7226 0.7282 0.7347 0.7407 0.7489 0.7633 0.7868 0.8602

IBA 0.7166 0.7220 0.7289 0.7351 0.7451 0.7609 0.7876 0.8603

RegSVD 0.7243 0.7328 0.7463 0.7571 0.7730 0.7979 0.8295 0.9038

RM

SE

UB 0.9457 0.9505 0.9574 0.9628 0.9711 0.9861 1.0164 1.1131

IB 0.9216 0.9289 0.9369 0.9442 0.9542 0.9735 1.0068 1.1058

IBA 0.9161 0.9232 0.9316 0.9397 0.9509 0.9720 1.0093 1.1071

RegSVD 0.9144 0.9256 0.9425 0.9550 0.9746 1.0055 1.0469 1.1489

Tem

po

UB 10 9 8 7 6 5 4 2

IB 47 53 52 46 37 26 16 8

IBA 39 45 45 41 38 29 21 13

RegSVD 924 802 700 593 467 363 253 136

Tabela 5.2: Análise dos algoritmos variando-se o test ratiocom log-Likelihood como medida de similaridade.

5.2 Resultados 73

Significância estatística

Observando-se os gráficos e tabelas apresentados nesta seção tem-se a impressãode que o algoritmo IBA tem uma acurácia melhor do que os demais algoritmos indepen-dente do test ratio. Entretanto o algoritmo se destaca mais em condições de test ratio

elevado (0,9), onde se tem poucos dados para ”treinar” o algoritmo e muitos dados aserem preditos.

Além disso, se comparado o tempo do IBA com o seu algoritmo de base (IB)é atingido uma redução de até 20%. Essa redução do tempo ocorre quando se tem maisdados para fazer o treinamento (test ratio igual a 0,2). Nesses casos é onde realmentefaz diferença o tempo, pois, quando se tem poucos dados de treinamento a execução énaturalmente rápida, sendo a acurácia mais importante.

Para comprovar esses ganhos, realizou-se testes de significância estatística. Foiutilizado o método de Wilcoxon. A significância estatística foi testada em três cenários:

1. Test ratio igual a 20%: Ambiente com muitos dados para treino, requerendo muitoesforço para realizar as predições. Entretanto, nesses ambientes os algoritmos têmum comportamento de acurácia muito parecido. Para esse ambiente é interessantemanter a acurácia reduzindo o tempo de execução.

2. Test ratio igual a 50%: Ambiente intermediário. É desejável que se tenha umamelhora tanto no tempo de execução quanto na acurácia.

3. Test ratio igual a 90%: Ambiente com poucos dados para treino. Nesse tipo deambiente, os algoritmos tendem a apresentar uma acurácia muito ruim, devido afalta de informação, porém conseguem realizar as predições de forma muito rápida.Assim, o tempo de execução nesses casos não é o fator mais importante e sim amelhora na acurácia, mesmo tendo um prejuízo no tempo de execução.

Estatisticamente o algoritmo IBA apresenta melhoras na acurácia em todos ostrês cenários. Para o primeiro cenário, foi obtido um V de Wilcoxon igual a 9,5 quandocomparado com o algoritmo IB e 0 quando comparado comparado com os algoritmos UBe RegSVD. O p− value foi menor que 2.2−16 para os três algoritmos. Para os demaiscenários foi obtido um V de Wilcoxon igual a 0 e o p− value menor que 2.2−16 paratodos os algoritmos.

Análise cada adaptação

Para concluir a análise sobre esse conjunto de dados foram conduzidos testespara mostrar a contribuição de cada adaptação proposta pelo algoritmo IBA. Os gráficosdas Figuras 5.17, 5.18 e 5.19 apresentam as influências de cada adaptação com test ratios

de 0,2, 0,5 e 0,9 nas métricas MAE, RMSE e tempo de execução respectivamente. Todosesses resultados utilizam a correlação de Pearson como medida de similaridade.

5.2 Resultados 74

Figura 5.17: Análise da influência de cada adaptação com testratio de 0,2, usando-se correlação de Pearson comomedida de similaridade.



5.2 Resultados 75

A influência de cada adaptação na acurácia varia de acordo com o test ratio. Asadaptações 2 e 4 influênciam bastante nos test ratios 0,2 e 0,5 enquanto para o test ratio

0,9 as adaptações que mais colaboram são as adaptações 1 e 3. Porém, usando todas asadaptações sempre se tem uma acurácia melhor do que usando cada uma individualmente,principalmente quando se tem um test ratio mais elevado (0,9).

A única adaptação que melhora o tempo de execução é a primeira, que aplicaum filtro antes da fase de cálculo de similaridades. As adaptações 2, 3 e 4 melhorama acurácia, porém criam uma sobrecarga de processamento aumentando o tempo deexecução. Para os test ratios 0,2 e 0,5 todas as adaptações em conjunto levam menostempo que o algoritmo utilizando apenas as adaptações 2, 3 ou 4 isoladamente, isso porqueo tempo ganho com a adaptação 1 compensa a sobrecarga de processamento adicionadopelas outras adaptações. No test ratio 0,9 esse comportamento muda. O ganho de tempo naadaptação 1 é muito pequeno. Isso é explicado pelo quantidade naturalmente reduzida noconjunto de dados, ficando assim apenas a sobrecarga adicionada pelas outras adaptações.

A Figura 5.20 faz uma análise na distribuição de erros de cada algoritmo em umaexecução com um test ratio igual a 0,1. Com esses gráficos nota-se que a distribuição detodos os algoritmos são muito semelhantes. Porém, é importante ressaltar que o únicoalgoritmo que não atinge um nenhum erro igual a 4 (maior erro possível) foi o IBA.

Figura 5.20: Análise da distribuição de erros para os algoritmos.

5.2.2 Netflix_3m1k

Os primeiros experimentos foram conduzidos para definir os melhores parâme-tros a serem utilizados em cada algoritmo. Isso foi feito para atingirem uma melhor acu-

5.2 Resultados 76

rácia e um melhor tempo de execução. Os resultados são sempre reportados nas três mé-tricas: MAE, RMSE e tempo de execução.

Seleção da medida de similaridade

O gráfico da Figura 5.21 apresenta o MAE para os três algoritmos baseados emmemória utilizando-se quatro medidas de similaridade diferentes. O gráfico da Figura5.22 apresenta o RMSE para os três algoritmos com as quatros medidas de similaridade.Já o gráfico da Figura 5.23 apresenda a métrica de tempo de execução dos três algoritmosutilizando cada uma das quatro medidas de similaridade.

Figura 5.21: MAE para diversas medidas de similaridade nos al-goritmos User-based, Item-based e Item-Based-ADP.

Figura 5.22: RMSE para diversas medidas de similaridade nos al-goritmos User-based, Item-based e Item-Based-ADP.

Assim como na coleção anterior (MovieLens_100k), o uso do cosseno ajustadoé uma péssima escolha para esta base de dados também, pois requer muito mais tempoque qualquer outra medida de similaridade além de apresentar o maior erro tanto emtermos de MAE quanto em termos de RMSE. As medidas de similaridade mais atrativaspara os algoritmos UB e IBA foram o cosseno e a log-Likelihood. A primeira por

5.2 Resultados 77

Figura 5.23: Tempo de execução para diversas medidas de simi-laridade nos algoritmos User-based, Item-based eItem-Based-ADP.

produzir o melhor resultado em termos de acurácia e a segunda por apresentar o melhortempo de execução. Já para o algoritmo IB as medidas mais atrativas foram as mesmasencontradas para a base de dados anterior, isso é, a correlação de Pearson e a log-Likelihood. A primeira por produzir o melhor resultado em termos de acurácia e a segundapor apresentar o melhor tempo de execução.

Assim, foi selecionado, para os demais experimentos, as duas medidas de simi-laridade mais apropriada para cada algoritmo, verificando os resultados com cada umadelas.

Seleção do número de vizinhos

O próximo parâmetro a ser decidido é o número de vizinhos que cada algoritmoselecionará para calcular as predições. Para isso, os algoritmos foram testados nos doisníveis extremos de test ratios (0,2 e 0,9).

As Figuras 5.24 e 5.25 apresentam os gráficos de MAE para os algoritmos emcada nível de test ratio. As Figuras 5.26 e 5.27 apresentam os gráficos com os resultadosde RMSE em cada nível de test ratio. Por último, as Figuras 5.28 e 5.29 apresentam osgráficos do tempo de execução para os três algoritmos baseados em similaridade em cadanível de test ratio.

Esses resultados evidenciam que para esse conjunto de dados os algoritmos IBe IBA apresentam melhores resultados, em termos de acurácia, utilizando 30 vizinhos,independente do nível de densidade do conjunto de teste.

É possível perceber que no test ratio igual a 0,2 se atinge um ponto mínimo nacurva dos gráficos. Isso fortalece a hipótese de que adicionar vizinhos demasiadamentenão é uma boa ideia, pois existem muitos falsos-positivos. Para o test ratio igual a 0,9encontramos um ponto de estabilização, evidenciando que neste ponto de esparsidade

5.2 Resultados 78

Figura 5.24: MAE variando-se o número de vizinhos nos três al-goritmos baseados em memória com test ratio de 0,2,utilizando-se as duas medidas de similaridade previ-amente selecionadas.

Figura 5.25: MAE variando-se o número de vizinhos nos três al-goritmos baseados em memória com test ratio de 0,9,utilizando-se as duas medidas de similaridade previ-amente selecionadas.

Figura 5.26: RMSE variando-se o número de vizinhos nos trêsalgoritmos baseados em memória com test ratio de0,2, utilizando-se as duas medidas de similaridadepreviamente selecionadas.

5.2 Resultados 79

Figura 5.27: RMSE variando-se o número de vizinhos nos trêsalgoritmo baseados em memória com test ratio de0,9, utilizando-se as duas medidas de similaridadepreviamente selecionadas.



5.2 Resultados 80

existem poucos vizinhos disponíveis, assim, os algoritmos sempre utilizam todos. Nesteambiente, os cálculos de similaridade são realizados apenas para ordenação dos vizinhos.

Para o algoritmo UB, o melhor número de vizinhos encontrado foi igual a50. Esse valor foi evidenciado tanto para o test ratio igual a 0,2 quanto 0,9. O pontomínimo no test ratio igual a 0,2 também foi encontrado. O ponto de estabilização não foiconfirmado, porém, a taxa de melhora foi quase mínima a partir de 50 vizinhos. Sendousado dessa forma o número de vizinhos igual a 50 em qualquer nível de test ratio.

O tempo de execução praticamente não é afetado pela variação do k. Pois o k

apenas define quantos vizinhos serão utilizados na fórmula de predição. Sendo necessárioainda calcular a similaridade entre todos os possíveis vizinhos.

Dessa forma, foi definido o melhor valor de vizinhos k como sendo 30 para osalgoritmos IB e IBA e igual a 50 para o algoritmo UB.

Seleção do limiar Delta (δ)

O último parâmetro a ser definido se refere apenas ao método proposto (IBA),que é o δ aplicado na primeira adaptação proposta pelo algoritmo. Nesses experimentos oδ foi variado de 0.5 a 1.2 nos dois extremos de test ratio,20% e 90%, utilizando-se ambasas medidas de similaridade selecionadas anteriormente.

As Figuras 5.30, 5.31 e 5.32 mostram os gráficos das métricas MAE, RMSE etempo de execução respectivamente com test ratio igual a 0.2.


A partir desses resultados observa-se que o melhor δ neste test ratio é de 0,9 paraeste conjunto de dados. Quanto menor o valor do δ mais dados são filtrados. Foi definidoentão como valor ótimo 0,9. A partir desse valor, o algoritmo já começa a descartar itensque não deveria, começando a piorar a acurácia.

Em termos de tempo de execução, como já esperado, quanto mais rígido é estefiltro, menor é o tempo de execução pois a similaridade é calculada em menos dados.

5.2 Resultados 81



Analisando o δ em um ambiente de test ratio igual a 0,9 percebe-se que quantomaior o valor adotado, melhor é o nível de acurácia. Isso pode ser explicado pela naturalfalta de informação presente neste ambiente. Obviamente, quanto maior o valor de δ maioré o tempo de execução. As Figuras 5.33, 5.34 e 5.35 mostram os gráficos das métricasMAE, RMSE e tempo de execução respectivamente com test ratio igual a 0.9.

Com esta quantidade de dados, o tempo de execução é curto de toda forma, nãosendo o fator mais importante. Os gráficos apontam que quanto maior a valor adotadopara o δ melhor é a acurácia. Assim, adotamos como parâmetro o valor de 1,2 visto que oaumento de tempo não é tão significativo.

Comparação dos algortimos

Para verificar o desempenho dos algoritmos em diversos níveis de densidade,foram conduzidos testes sob todos os test ratios (0,2 - 0,9). Esses testes foram executadosde forma que todos os algoritmos estivessem com os melhores parâmetros selecionadosnos testes anteriores.

5.2 Resultados 82




5.2 Resultados 83

Test Ratio0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

MA

E

UB 0.7290 0.7350 0.7444 0.7515 0.7640 0.7836 0.8204 0.9139

IB 0.7131 0.7207 0.7301 0.7381 0.7502 0.7711 0.8067 0.8901

IBA 0.7116 0.7188 0.7275 0.7345 0.7456 0.7610 0.7853 0.8595

RegSVD 0.7243 0.7328 0.7463 0.7571 0.7730 0.7979 0.8295 0.9038R

MSE

UB 0.9340 0.9424 0.9530 0.9618 0.9770 1.0021 1.0498 1.1649

IB 0.9108 0.9204 0.9322 0.9423 0.9575 0.9857 1.0352 1.1445

IBA 0.9104 0.9193 0.9299 0.9387 0.9505 0.9705 1.0048 1.1054

RegSVD 0.9144 0.9256 0.9425 0.9550 0.9746 1.0055 1.0469 1.1489

Tem

po

UB 38 33 29 24 20 16 11 5

IB 188 211 210 181 141 92 49 17

IBA 154 173 175 154 139 100 61 26

RegSVD 924 802 700 593 467 363 253 136

Tabela 5.3: Análise dos algoritmos variando-se o test ratiocom a medida de similaridade que mais favorece aacurácia.

Test Ratio0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

MA

E

UB 0.7401 0.7432 0.7496 0.7546 0.7616 0.7735 0.7960 0.8706

IB 0.7226 0.7282 0.7347 0.7407 0.7489 0.7633 0.7868 0.8602

IBA 0.7166 0.7220 0.7289 0.7351 0.7451 0.7609 0.7876 0.8603

RegSVD 0.7243 0.7328 0.7463 0.7571 0.7730 0.7979 0.8295 0.9038

RM

SE

UB 0.9457 0.9505 0.9574 0.9628 0.9711 0.9861 1.0164 1.1131

IB 0.9216 0.9289 0.9369 0.9442 0.9542 0.9735 1.0068 1.1058

IBA 0.9161 0.9232 0.9316 0.9397 0.9509 0.9720 1.0093 1.1071

RegSVD 0.9144 0.9256 0.9425 0.9550 0.9746 1.0055 1.0469 1.1489

Tem

po

UB 10 9 8 7 6 5 4 2

IB 47 53 52 46 37 26 16 8

IBA 39 45 45 41 38 29 21 13

RegSVD 924 802 700 593 467 363 253 136

Tabela 5.4: Análise dos algoritmos variando-se o test ratiocom log-Likelihood como medida de similaridade.

5.2 Resultados 84

A Tabela 5.3 reporta os resultados dos algoritmos utilizando-se como medida desimilaridade a medida que atinge melhor acurácia. Já a Tabela 5.4 reporta os resultadosdos algoritmos utilizando-se a medida de similaridade que dá prioridade ao ganho notempo de execução. Para esse conjunto de dados essas medidas são correlação de Pearsone log-Likelihood respectivamente para todos os algoritmos baseados em memória.

Nas Tabelas 5.3 e 5.4 o tempo de execução dos algoritmos baseados em memóriasão referentes ao tempo gasto nas predições enquanto o tempo de execução do algoritmoRegSVD se refere ao tempo de treinamento que ele tem, por ser baseado em modelo, istoé, o tempo de modelagem.

Significância estatística

Observando os gráficos e tabelas apresentados nesta seção tem-se a noção de queo algoritmo IBA tem uma acurácia melhor do que os demais algoritmos quando se temum nível de test ratio elevado.

Além disso, se comparado o tempo do IBA com o seu algoritmo de base (IB)tem-se uma redução de até 50%. Essa redução do tempo ocorre quando quando se temmais dados para fazer o treinamento (test ratio igual a 0,2). Nesses casos é onde realmentefaz diferença o tempo, pois, quando se tem poucos dados de treinamento a execução énaturalmente rápida, sendo a acurácia mais importante.

Para comprovar esses ganhos, foram realizados testes de significância estatística.Foi utilizado o método de Wilcoxon. A significância estatística foi testada em trêscenários:

1. Test ratio igual a 20%: Ambiente com muitos dados para treino, requerendo muitoesforço para realizar as predições. Entretanto, nesses ambientes os algoritmos têmum comportamento de acurácia muito parecido. Para esse ambiente é interessantemanter a acurácia reduzindo o tempo de execução.

2. Test ratio igual a 50%: Ambiente intermediário. É desejável que se tenha umamelhora tanto no tempo de execução quanto na acurácia.

3. Test ratio igual a 90%: Ambiente com poucos dados para treino. Nesse tipo deambiente, os algoritmos tendem a apresentar uma acurácia muito ruim, devido afalta de informação, porém conseguem realizar as predições de forma muito rápida.Assim, o tempo de execução nesses casos não é o fator mais importante e sim amelhora na acurácia, mesmo tendo um prejuízo no tempo de execução.

Estatisticamente o algoritmo IBA apresenta melhoras na acurácia nos dois últi-mos cenários. Para o primeiro cenário, foi obtido um V de Wilcoxon igual a 5050 quandocomparado com o algoritmo IB com um p− value igual a 1. Isso mostra que se compa-rado com a implementação padrão, o IBA não é melhor em termos de acurácia, porém,

5.2 Resultados 85

conseguimos uma melhora de pouco mais de 50% no tempo de execução, sem grandesperdas na acurácia. Já comparado com os algoritmos UB e RegSVD foi obtido um V deWilcoxon igual a 0 e um p− value menor que 2.2−16

Para o cenário 2, o algoritmo IBA já mostrou uma melhora na acurácia comsignificância estatística em relação aos outros três algoritmos. Comparado com o IBse obteve um V de Wilcoxon igual a 1682,5 e um p− value igual a 0,01905. Quandocomparado com os outros dois algoritmos (UB e RegSVD) se obtém um V de Wilcoxonigual a 0 e um p− value menor que 2.2−16 para ambos.

Por último, no terceiro cenário, o algoritmo IBA apresenta uma melhora naacurácia com significância estatística em relação a todos os algoritmos. Comparando-se com todos os outros três algoritmos, foi obtido um V de Wilcoxon igual a 0 e ump− value menor que 2.2−16

Análise cada adaptação

Para concluir a análise sobre esse conjunto de dados foram conduzidos testespara mostrar a contribuição de cada adaptação proposta pelo algoritmo IBA. Os gráficosdas Figuras 5.36, 5.37 e 5.38 apresentam as influências de cada adaptação com test ratios

de 0,2, 0,5 e 0,9 nas métricas MAE, RMSE e tempo de execução respectivamente. Todosesses resultados utilizam a correlação de Pearson como medida de similaridade.

Figura 5.36: Análise da influência de cada adaptação com testratio de 0,2, usando-se o cosseno como medida desimilaridade.

A influência de cada adaptação na acurácia varia de acordo com o test ratio. Asadaptações 2 e 4 influênciam bastante nos test ratios 0,2 e 0,5 enquanto para o test ratio 0,9as adaptações que mais colaboram são as adaptações 1 e 3. Para os test ratios 0,2 e 0,5 aadaptação 4 isoladamente apresenta melhor acurácia do que o uso de todas as adaptaçõesem conjunto. Entretanto, nesses test ratios a primeira adaptação é importante devido a

5.2 Resultados 86



quantidade de dados a serem computadas sem o uso da primeira adaptação. Isso justificao uso de todas as adaptações em conjunto, mesmo perdendo um pouco na acurácia.

A única adaptação que melhora o tempo de execução é a primeira, que aplicaum filtro antes da fase de cálculo de similaridades. As adaptações 2, 3 e 4 melhorama acurácia, porém criam uma sobrecarga de processamento aumentando o tempo deexecução. Para os test ratios 0,2 e 0,5 todas as adaptações em conjunto levam menostempo que o algoritmo utilizando apenas as adaptações 2, 3 ou 4 isoladamente, isso porqueo tempo ganho com a adaptação 1 compensa a sobrecarga de processamento adicionadopelas outras adaptações. No test ratio 0,9 esse comportamento muda. O ganho de tempo naadaptação 1 é muito pequeno. Isso é explicado pelo quantidade naturalmente reduzida noconjunto de dados, ficando assim apenas a sobrecarga adicionada pelas outras adaptações.

CAPÍTULO 6Conclusão e Trabalhos Futuros

Neste trabalho foi proposto uma melhoria no algoritmo de filtragem colaborativaItem-based, essa nova versão do algoritmo foi denomidada Item-Based-ADP.

O Item-Based-ADP foi desenvolvido com dois objetivos: i) obter uma melhoraem termos de acurácia em relação aos demais algoritmos baseados em memória semperder a sua simplicidade de entendimento e implementação, além de evitar a necessidadedo uso de mais informações, isso é, utilizando apenas a matriz de avaliações que é comumna maioria dos contextos. ii) Melhorar a performace do tempo de execução em relação aoalgoritmo Item-based tradicional.

Para avaliar o Item-Based-ADP foram realizados testes com as coleções maisutilizadas na literatura para realizar benchmarks, MovieLens e Netflix. Os testes foramrealizados sob as mais variadas condições de esparsidade. Os testes evidenciaram que osobjetivos almejados pelo algoritmo proposto foram alcançados com sucesso.

Na base de dados MovieLens ambos os objetivos foram alcançados indepen-dente da esparsidade analisada. Isso foi comprovado estatisticamente com os experimen-tos. Neste conjunto de dados o ganho no tempo de execução não foi tão drástico, devidoao tamanho da base. Entretanto, os ganhos em termos de acurácia foram bastante signifi-cativos, principalmente em ambientes muito esparsos.

Na base de dados Netflix o principal objetivo alcançado foi a melhora do tempode execução, atingindo uma melhora de quase 50%. Essa melhora é evidenciada devido aogrande volume de dados da base. Isso leva a acreditar que a melhora do tempo de execuçãofica cada vez mais acentuada de acordo com que o volume de dados vão aumentando,porém isso não foi concluído com os testes. Novos testes com bases ainda maioresprecisariam ser realizados futuramente para evidenciar isso. Nesta base, a melhora daacurácia só foi obtida em níveis mais esparsos (test ratio a partir de 0,5).

No método Item-Based-ADP foram propostas quatro adaptações em relaçãoao algoritmo Item-Based tradicional. Essas adaptações não geram grandes impactos nasimplicidade do algoritmo. Cada adaptação foi analisada isoladamente para demonstraro que cada uma traz de vantagem. Desta forma, o algoritmo pode ser observado emmódulos, sendo possível adapta-lo segundo a necessidade de cada aplicação.

88

A adaptação que mais causa impacto no tempo de execução é o filtro inicial nosdados, no momento de selecionar os k vizinhos mais semelhantes. Esta adaptação mostrouque muitos itens podem ser descartados dos possíveis vizinhos sem a necessidade docálculo da correlação de Pearson ou outro cálculo de similaridade, processo que requerum processamento demorado. Para esse filtro inicial fora utilizado um cálculo simplescom a média de avaliações que cada item apresenta.

Outras medidas podem ser utilizadas neste primeiro filtro, como mediana oudesvio padrão. Esse estudo será realizado em trabalhos futuros para tentar encontrar quala melhor medida para realizar esse filtro de forma que não aumente muito o tempo deexecução e que consiga eliminar o máximo de possíveis vizinhos falsos-positivos.

O método proposto ainda pode ser facilmente adaptado para a abordagem base-ada na similaridade de usuários (User-based). Esse estudo não foi realizado pelo fato deque o algoritmo baseado na similaridade de itens (Item-based) vir apresentando resultadossuperiores ao User-based naturalmente.

Referências Bibliográficas

[1] ADOMAVICIUS, G.; SANKARANARAYANAN, R.; SEN, S.; TUZHILIN, A. Incorporating

contextual information in recommender systems using a multidimensional

approach. ACM Transactions on Information Systems (TOIS), 23(1):103–145, 2005.

[2] ADOMAVICIUS, G.; TUZHILIN, A. Toward the next generation of recommender

systems: A survey of the state-of-the-art and possible extensions. Knowledge

and Data Engineering, IEEE Transactions on, 17(6):734–749, 2005.

[3] ANTUNES, P.; HERSKOVIC, V.; OCHOA, S. F.; PINO, J. A. Structuring dimensions

for collaborative systems evaluation. ACM Comput. Surv., 44(2):8:1–8:28, Mar.

2008.

[4] BAEZA-YATES, R.; RIBEIRO-NETO, B.; OTHERS. Modern information retrieval,

volume 463. ACM press New York, 1999.

[5] BALABANOVIC, M.; SHOHAM, Y. Fab: content-based, collaborative recommenda-

tion. Communications of the ACM, 40(3):66–72, 1997.

[6] BALTRUNAS, L.; MAKCINSKAS, T.; RICCI, F. Group recommendations with rank

aggregation and collaborative filtering. In: Proceedings of the Fourth ACM

Conference on Recommender Systems, RecSys ’10, p. 119–126, New York, NY,

USA, 2010. ACM.

[7] BELL, R. M.; KOREN, Y. Scalable collaborative filtering with jointly derived

neighborhood interpolation weights. In: Data Mining, 2007. ICDM 2007. Seventh

IEEE International Conference on, p. 43–52. IEEE, 2007.

[8] BEYGELZIMER, A.; KAKADE, S.; LANGFORD, J. Cover trees for nearest neighbor.

In: Proceedings of the 23rd international conference on Machine learning, p. 97–104.

ACM, 2006.

[9] BILLSUS, D.; BRUNK, C. A.; EVANS, C.; GLADISH, B.; PAZZANI, M. Adaptive

interfaces for ubiquitous web access. Communications of the ACM, 45(5):34–38,

2002.


[10] BILLSUS, D.; PAZZANI, M. J. Learning collaborative information filters. In: ICML,

volume 98, p. 46–54, 1998.

[11] BOBADILLA, J.; ORTEGA, F.; HERNANDO, A.; GUTIÉRREZ, A. Recommender

systems survey. Know.-Based Syst., 46:109–132, July 2013.

[12] BOBADILLA, J.; HERNANDO, A.; ORTEGA, F.; BERNAL, J. A framework for col-

laborative filtering recommender systems. Expert Systems with Applications,

38(12):14609–14623, Nov. 2011.

[13] BOIM, R.; MILO, T.; NOVGORODOV, S. Diversification and refinement in colla-

borative filtering recommender. In: Proceedings of the 20th ACM international

conference on Information and knowledge management, p. 739–744. ACM, 2011.

[14] BREESE, J. S.; HECKERMAN, D.; KADIE, C. Empirical analysis of predictive

algorithms for collaborative filtering. In: Proceedings of the Fourteenth conference

on Uncertainty in artificial intelligence, p. 43–52. Morgan Kaufmann Publishers Inc.,

1998.

[15] BREESE, J.; HECKERMAN, D.; KADIE, C. Empirical analysis of predictive algo-

rithms for collaborative filtering. Proceedings of the Fourteenth . . . , 1998.

[16] BRIDGE, D.; GÖKER, M. H.; MCGINTY, L.; SMYTH, B. Case-based recommender

systems. The Knowledge Engineering Review, 20(03):315–320, 2005.

[17] BURKE, R. Hybrid web recommender systems. In: The adaptive web, p. 377–408.

Springer, 2007.

[18] CACHEDA, F.; CARNEIRO, V.; FERNÁNDEZ, D.; FORMOSO, V. Comparison of colla-

borative filtering algorithms: Limitations of current techniques and proposals

for scalable, high-performance recommender systems. ACM Transactions on the

Web (TWEB), 5(1):2, 2011.

[19] CACHEDA, F.; CARNEIRO, V.; FERNÁNDEZ, D.; FORMOSO, V. Comparison of col-

laborative filtering algorithms: Limitations of current techniques and propo-

sals for scalable, high-performance recommender systems. ACM Trans. Web,

5(1):2:1–2:33, Feb. 2011.

[20] CHEN, D.-E. The collaborative filtering recommendation algorithm based on

bp neural networks. In: Intelligent Ubiquitous Computing and Education, 2009

International Symposium on, p. 234–236. IEEE, 2009.


[21] CHIEN, Y.-H.; GEORGE, E. I. A bayesian model for collaborative filtering. In:

Proceedings of the 7th International Workshop on Artificial Intelligence and Sta-

tistics. San Francisco: Morgan Kaufman Publishers,[http://uncertainty99. microsoft.

com/proceedings. htm], 1999.

[22] DE GEMMIS, M.; IAQUINTA, L.; LOPS, P.; MUSTO, C.; NARDUCCI, F.; SEMERARO, G.

Preference learning in recommender systems. PREFERENCE LEARNING, 41,

2009.

[23] DESHPANDE, M.; KARYPIS, G. Item-based top-n recommendation algorithms.

ACM Transactions on Information Systems (TOIS), 22(1):143–177, 2004.

[24] D.MANNING, C.; RAGHAVAN, P.; SCHUTZE, H. An Introduction to Information

Retrieval. Cambridge University Press, p. 581, 2009.

[25] FELFERNIG, A.; BURKE, R. Constraint-based recommender systems: technolo-

gies and research issues. In: Proceedings of the 10th international conference on

Electronic commerce, p. 3. ACM, 2008.

[26] FUNK, S. Netflix update: Try this at home. 2006.

[27] GETOOR, L.; SAHAMI, M. Using probabilistic relational models for collaborative

filtering. In: Workshop on Web Usage Analysis and User Profiling (WEBKDD’99).

Citeseer, 1999.

[28] GIBBONS, J. D.; CHAKRABORTI, S. Nonparametric statistical inference. Springer,

2011.

[29] GIFFORD, D. K.; BALDWIN, R. W.; BERLIN, S. T.; LUCASSEN, J. M. An architecture

for large scale information systems. In: ACM SIGOPS Operating Systems Review,

volume 19, p. 161–170. ACM, 1985.

[30] GOLDBERG, D.; NICHOLS, D.; OKI, B. M.; TERRY, D. Using collaborative filtering

to weave an information tapestry. Communications of the ACM, 35(12):61–70,

1992.

[31] GOLDBERG, K.; ROEDER, T.; GUPTA, D.; PERKINS, C. Eigentaste: A constant time

collaborative filtering algorithm. Information Retrieval, 4(2):133–151, 2001.

[32] GUNAWARDANA, A.; SHANI, G. A survey of accuracy evaluation metrics of

recommendation tasks. J. Mach. Learn. Res., 10:2935–2962, Dec. 2009.

[33] HERLOCKER, J.; KONSTAN, J. A.; RIEDL, J. An empirical analysis of design

choices in neighborhood-based collaborative filtering algorithms. Information

retrieval, 5(4):287–310, 2002.


[34] HERLOCKER, J. L.; KONSTAN, J. A.; RIEDL, J. Explaining collaborative filtering

recommendations. In: Proceedings of the 2000 ACM conference on Computer

supported cooperative work, p. 241–250. ACM, 2000.

[35] HERLOCKER, J. L.; KONSTAN, J. A.; TERVEEN, L. G.; RIEDL, J. T. Evaluating

collaborative filtering recommender systems. ACM Transactions on Information

Systems (TOIS), 22(1):5–53, 2004.

[36] HERLOCKER, J. L.; KONSTAN, J. A.; TERVEEN, L. G.; RIEDL, J. T. Evaluating

collaborative filtering recommender systems. ACM Trans. Inf. Syst., 22(1):5–53,

Jan. 2004.

[37] HERLOCKER, J. L. Understanding and improving automated collaborative filte-

ring systems. PhD thesis, University of Minnesota, 2000. AAI9983577.

[38] HERNÁNDEZ DEL OLMO, F.; GAUDIOSO, E. Evaluation of recommender systems:

A new approach. Expert Syst. Appl., 35(3):790–804, Oct. 2008.

[39] HILL, W.; STEAD, L.; ROSENSTEIN, M.; FURNAS, G. Recommending and evalua-

ting choices in a virtual community of use. In: Proceedings of the SIGCHI con-

ference on Human factors in computing systems, p. 194–201. ACM Press/Addison-

Wesley Publishing Co., 1995.

[40] HURLEY, N.; ZHANG, M. Novelty and diversity in top-n recommendation –

analysis and evaluation. ACM Trans. Internet Technol., 10(4):14:1–14:30, Mar.

2011.

[41] KANTOR, P. B.; ROKACH, L.; RICCI, F.; SHAPIRA, B. Recommender systems

handbook. Springer, 2011.

[42] KIM, H.-N.; JI, A.-T.; JO, G.-S. Enhanced prediction algorithm for item-based

collaborative filtering recommendation. In: E-Commerce and Web Technologies,

p. 41–50. Springer, 2006.

[43] KONSTAN, J. A.; MILLER, B. N.; MALTZ, D.; HERLOCKER, J. L.; GORDON, L. R.;

RIEDL, J. Grouplens: applying collaborative filtering to usenet news. Communi-

cations of the ACM, 40(3):77–87, 1997.

[44] KOREN, Y. Factorization meets the neighborhood: a multifaceted collaborative

filtering model. In: Proceedings of the 14th ACM SIGKDD international conference

on Knowledge discovery and data mining, p. 426–434. ACM, 2008.

[45] KRULWICH, B. Lifestyle finder: Intelligent user profiling using large-scale demo-

graphic data. AI magazine, 18(2):37, 1997.


[46] LAST.FM. Last.fm music recommendation service, Visualizado em 2014.

[47] LEE, J.; SUN, M.; LEBANON, G. A comparative study of collaborative filtering

algorithms. arXiv preprint arXiv:1205.3193, 2012.

[48] LI, R.; ZHANG, Y.; YU, H.; WANG, X.; WU, J.; WEI, B. A social network-aware top-

n recommender system using gpu. In: Proceedings of the 11th annual international

ACM/IEEE joint conference on Digital libraries, p. 287–296. ACM, 2011.

[49] LINDEN, G.; SMITH, B.; YORK, J. Amazon. com recommendations: Item-to-item

collaborative filtering. Internet Computing, IEEE, 7(1):76–80, 2003.

[50] LINDEN, G. D.; JACOBI, J. A.; BENSON, E. A. Collaborative recommendations

using item-to-item similarity mappings, July 24 2001. US Patent 6,266,649.

[51] LOPS, P.; DE GEMMIS, M.; SEMERARO, G. Content-based recommender systems:

State of the art and trends. In: Recommender Systems Handbook, p. 73–105.

Springer, 2011.

[52] LUTZ, E.; KLEIST-RETZOW, H. V.; HOERNIG, K. Mafia - an active mail-filter-agent

for an intelligent document processing support. ACM SIGOIS Bulletin, 11(4):16–

32, 1990.

[53] MACKAY, D. J. C. Information Theory, Inference & Learning Algorithms. Cam-

bridge University Press, New York, NY, USA, 2002.

[54] MARMANIS, H.; BABENKO, D. Algorithms of the intelligent web. Manning Publica-

tions Co., 2009.

[55] MILLER, B. N.; ALBERT, I.; LAM, S. K.; KONSTAN, J. A.; RIEDL, J. Movielens

unplugged: experiences with an occasionally connected recommender system.

In: Proceedings of the 8th international conference on Intelligent user interfaces, p.

263–266. ACM, 2003.

[56] MOBASHER, B.; DAI, H.; LUO, T.; NAKAGAWA, M. Discovery and evaluation of

aggregate usage profiles for web personalization. Data mining and knowledge

discovery, 6(1):61–82, 2002.

[57] MOBASHER, B.; JIN, X.; ZHOU, Y. Semantically enhanced collaborative filtering

on the web. In: Web Mining: From Web to Semantic Web, p. 57–76. Springer, 2004.

[58] MOONEY, R. J.; ROY, L. Content-based book recommending using learning for

text categorization. In: Proceedings of the fifth ACM conference on Digital libraries,

p. 195–204. ACM, 2000.


[59] MU, X.; CHEN, Y.; YANG, J.; JIANG, J. An improved similarity algorithm based

on hesitation degree for user-based collaborative filtering. In: Advances in

Computation and Intelligence, p. 261–271. Springer, 2010.

[60] NADUNGODAGE, C. H.; XIA, Y.; LEE, J. J.; LEE, M.; PARK, C. S. Gpu accelerated

item-based collaborative filtering for big-data applications. In: Big Data, 2013

IEEE International Conference on, p. 175–180. IEEE, 2013.

[61] PATEREK, A. Improving regularized singular value decomposition for collabo-

rative filtering. In: Proceedings of KDD cup and workshop, volume 2007, p. 5–8,

2007.

[62] PAVLOV, D.; PENNOCK, D. M. A maximum entropy approach to collaborative

filtering in dynamic, sparse, high-dimensional domains. In: NIPS, volume 2, p.

1441–1448, 2002.

[63] PAZZANI, M. J. A framework for collaborative, content-based and demographic

filtering. Artificial Intelligence Review, 13(5-6):393–408, 1999.

[64] PAZZANI, M. J.; BILLSUS, D. Content-based recommendation systems. In: The

adaptive web, p. 325–341. Springer, 2007.

[65] POLLOCK, S. A rule-based message filtering system. ACM Transactions on

Information Systems (TOIS), 6(3):232–254, 1988.

[66] PORCEL, C.; MORENO, J. M.; HERRERA-VIEDMA, E. A multi-disciplinar recom-

mender system to advice research resources in university digital libraries. Ex-

pert Systems with Applications, 36(10):12520–12528, 2009.

[67] RESNICK, P.; IACOVOU, N.; SUCHAK, M.; BERGSTROM, P.; RIEDL, J. Grouplens:

an open architecture for collaborative filtering of netnews. In: Proceedings of the

1994 ACM conference on Computer supported cooperative work, p. 175–186. ACM,

1994.

[68] RESNICK, P.; VARIAN, H. R. Recommender systems. Communications of the ACM,

40(3):56–58, 1997.

[69] RICCI, F.; CAVADA, D.; MIRZADEH, N.; VENTURINI, A. Case-based travel recom-

mendations. Destination Recommendation Systems: Behavioural Foundations and

Applications, p. 67–93, 2006.

[70] ROCCHIO, J. J. Relevance feedback in information retrieval. 1971.


[71] SALTON, G.; BUCKLEY, C. Term-weighting approaches in automatic text retrieval.

Information processing & management, 24(5):513–523, 1988.

[72] SALTON, G.; WONG, A.; YANG, C.-S. A vector space model for automatic

indexing. Communications of the ACM, 18(11):613–620, 1975.

[73] SARWAR, B.; KARYPIS, G.; KONSTAN, J.; RIEDL, J. Application of dimensionality

reduction in recommender system-a case study. Technical report, DTIC Docu-

ment, 2000.

[74] SARWAR, B.; KARYPIS, G.; KONSTAN, J.; RIEDL, J. Item-based collaborative

filtering recommendation algorithms. In: Proceedings of the 10th international

conference on World Wide Web, p. 285–295. ACM, 2001.

[75] SCHAFER, J. B.; FRANKOWSKI, D.; HERLOCKER, J.; SEN, S. The adaptive web. In:

Brusilovsky, P.; Kobsa, A.; Nejdl, W., editors, The Adaptive Web, chapter Collaborative

Filtering Recommender Systems, p. 291–324. Springer-Verlag, Berlin, Heidelberg,

2007.

[76] SCHAFER, J. B.; KONSTAN, J. A.; RIEDL, J. E-commerce recommendation ap-

plications. In: Applications of Data Mining to Electronic Commerce, p. 115–153.

Springer, 2001.

[77] SCHEIN, A. I.; POPESCUL, A.; UNGAR, L. H.; PENNOCK, D. M. Methods and

metrics for cold-start recommendations. In: Proceedings of the 25th Annual

International ACM SIGIR Conference on Research and Development in Information

Retrieval, SIGIR ’02, p. 253–260, New York, NY, USA, 2002. ACM.

[78] SHANI, G.; BRAFMAN, R. I.; HECKERMAN, D. An mdp-based recommender

system. In: Proceedings of the Eighteenth conference on Uncertainty in artificial

intelligence, p. 453–460. Morgan Kaufmann Publishers Inc., 2002.

[79] SHARDANAND, U.; MAES, P. Social information filtering: algorithms for automa-

ting “word of mouth”. In: Proceedings of the SIGCHI conference on Human factors

in computing systems, p. 210–217. ACM Press/Addison-Wesley Publishing Co., 1995.

[80] SU, P.; YE, H. An item based collaborative filtering recommendation algorithm

using rough set prediction. In: Artificial Intelligence, 2009. JCAI’09. International

Joint Conference on, p. 308–311. IEEE, 2009.

[81] SU, X.; KHOSHGOFTAAR, T. M. A survey of collaborative filtering techniques.

Advances in artificial intelligence, 2009:4, 2009.


[82] TERVEEN, L.; HILL, W.; AMENTO, B.; MCDONALD, D.; CRETER, J. Phoaks: A

system for sharing recommendations. Communications of the ACM, 40(3):59–62,

1997.

[83] TORRES, R. Personalização na Internet: Como Descobrir os Hábitos de

Consumo de Seus Clientes, Fidelizá-los e Aumentar o Lucro de Seu Negócio.

Novatec Editora, 2004.

[84] UNGAR, L. H.; FOSTER, D. P. Clustering methods for collaborative filtering. In:

AAAI Workshop on Recommendation Systems, número 1, 1998.

[85] VOZALIS, M.; MARGARITIS, K. G. Collaborative filtering enhanced by demo-

graphic correlation. In: AIAI Symposium on Professional Practice in AI, of the 18th

World Computer Congress, 2004.

[86] VOZALIS, M. G.; MARGARITIS, K. G. Using svd and demographic data for

the enhancement of generalized collaborative filtering. Information Sciences,

177(15):3017–3037, 2007.

[87] WEI, S.; YE, N.; ZHANG, S.; HUANG, X.; ZHU, J. Collaborative filtering recom-

mendation algorithm based on item clustering and global similarity. In: Business

Intelligence and Financial Engineering (BIFE), 2012 Fifth International Conference

on, p. 69–72. IEEE, 2012.

[88] YU, K.; XU, X.; ESTER, M.; KRIEGEL, H.-P. Selecting relevant instances for effici-

ent and accurate collaborative filtering. In: Proceedings of the tenth international

conference on Information and knowledge management, p. 239–246. ACM, 2001.

Documents

Item-Based-ADP: Análise e Melhoramento do Algoritmo de