Anais do XVIII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do III Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
24 e 25 de setembro de 2013
DESENVOLVIMENTO DE ALGORITMO HÍBRIDO PARA
SISTEMAS DE RECOMENDAÇÃO:
FILTRAGEM COLABORATIVA E ETIQUETAGEM SOCIAL
Ana Paula Sontachi de Oliveira
Faculdade de Engenharia de Computação
CEATEC
[email protected]
Resumo: Com a crescente expansão da Internet, o
volume de dados disponíveis aos usuários vem aumentando exponencialmente. Em um único dia é
gerada uma enorme quantidade de conteúdo, incluindo, imagens, artigos, blogs etc. Devido a este crescente aumento de dados disponíveis, torna-se difícil
ao usuário da rede localizar informação e recursos
de seu interesse. Sistemas de recomendação (SR)
baseados em filtragem colaborativa são uma alternativa para amenizar este problema. SR realizam recomendações de itens ao usuário, baseando-se no
seu perfil. Esse perfil é caracterizado geralmente
pelas avaliações (notas) que o usuário atribuiu aos
itens acessados. Entre as deficiências desta abordagem destaca-se a sua baixa precisão quando a matriz que armazena as avaliações dos usuários é esparsa ou quando novos usuários e itens são adicionados. Segundo a literatura, a utilização de etiquetas
(tags) associadas aos itens pelos usuários pode
aliviar esses problemas. O trabalho descrito neste
artigo focou a construção de um sistema que combina elementos de filtragem colaborativa com etiquetas
associadas aos itens a recomendar pela comunidade
de usuários. A partir de pesquisa bibliográfica foi
escolhida uma arquitetura de sistema baseada em
uma matriz tridimensional que contempla usuários,
itens e tags associadas aos itens pelos usuários.
Foram implementados e avaliados os módulos da
arquitetura proposta que permitem realizar quatro
das seis etapas previstas para fazer uma recomendação, utilizando dados reais provenientes do sistema delicious.
Palavras-chave: Algoritmos de filtragem colaborativa, sistemas de recomendação, etiquetagem social.
Área do Conhecimento: Ciências Exatas e da Terra
– Ciência da Computação.
1. INTRODUÇÃO
Os sistemas de recomendação (SR) vêm se tornando cada vez mais relevantes e é possível notar hoje
em dia seu uso em diversos sites da Web com o
Juan Manuel Adán Coello
Grupo de Pesquisa em Sistemas Inteligentes
CEATEC
[email protected]
objetivo de auxiliar os usuários a encontrar recursos
de interesse.
Muita informação deve ser levada em conta no desenvolvimento de um sistema de recomendação,
sendo as principais delas os perfis dos usuários e
dos itens. Os perfis de usuários podem ser traçados,
usando, por exemplo, suas preferências, informações geográficas (país, região onde vive, idade),
dentre outras. Quanto mais detalhado um perfil de
usuário for, mais fácil e eficiente será a recomendação. Da mesma forma, a descrição detalhada dos
itens é crucial para se obter bons resultados [1].
Para realizar uma recomendação para um usuário
alvo, além de se basear nas preferências desse usuário, SR também utilizam o perfil de usuários que são
semelhantes a ele, ou seja, um SR deve avaliar quão
parecido um usuário é com o outro. Uma vez que
usuários parecidos podem gostar das mesmas coisas, pode ser interessante formar uma vizinhança
(neighborhood) com esses usuários e realizar recomendações baseadas nas avaliações dos nos usuários que compõem a vizinhança.
O problema central de um sistema de recomendação
é, portanto, determinar uma nota que reflita o grau de
interesse que o usuário alvo teria em um item que
ele ainda não acessou. Se essa nota for elevada, o
item poderá ser recomendado ao usuário. Entendese item como qualquer objeto, concreto ou abstrato,
como uma página Web, um filme, um livro ou um
usuário a seguir no Twitter.
Tendo formado vizinhanças de usuários semelhantes, vários métodos podem ser usados para combinar as avaliações que esses usuários fizeram para
prever uma nota para itens ainda não acessados
pelo usuário alvo. O trabalho descrito neste artigo
teve como objetivo estudar o uso de algoritmos de
recomendação híbridos que utilizam filtragem colaborativa e etiquetagem social. O intuito é melhorar o
desempenho nas recomendações, principalmente
em situações em os dados são esparsos (há um
Anais do XVIII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do III Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
24 e 25 de setembro de 2013
número relativamente pequeno de avaliações, considerada a quantidade total de usuários e itens). A
arquitetura estudada e parcialmente implementada é
descrita em [2].
O restante deste artigo é organizado como se segue.
Na seção 2 e 3 são apresentados alguns conceitos
básicos sobre filtragem colaborativa e etiquetagem
social, respectivamente, necessários ao entendimento do restante do artigo. Na seção 4 apresenta-se a
arquitetura do sistema implementado. Finalmente, na
seção 5 são feitas algumas considerações finais.
2. FILTRAGEM COLABORATIVA
A Filtragem Colaborativa (FC) é baseada no fato de
que opiniões dos outros têm considerável influência
sobre a tomada de decisão das pessoas.
O objetivo central de um algoritmo de FC é prever o
valor que o usuário daria para um item que ainda não
foi avaliado por ele, utilizando avaliações de outros
usuários. Posteriormente o usuário poderá informar,
direta ou indiretamente, se gostou ou não da recomendação feita. Deste modo, com base nas notas
(ratings) atribuídas pelos usuários aos item, o sistema poderá prever as notas que outros usuários, que
não o acessaram, lhe atribuiriam.
A Filtragem Colaborativa é um dos métodos mais
utilizados em sistemas de recomendação, porém
possui algumas limitações. Como a quantidade de
dados de usuários e itens em sistemas Web frequentemente é muito grande, a matriz que armazena as
avaliações dos usuários para os itens, denominada
matriz usuário-item, tende a ser esparsa, ou seja a
ter uma quantidade relativamente pequena de avaliações. A quantidade relativamente baixa de itens
avaliados torna complicado o processo de encontrar
vizinhos confiáveis para realizar a recomendação.
Outra dificuldade deste tipo de sistema é lidar com
usuários que tenham preferências diferentes do padrão, isto pode diminuir a precisão das recomendações. Usuários novos no sistema, aqueles que acabaram de criar um perfil e não avaliaram nenhum
item, ou avaliaram poucos itens, assim como itens
novos que foram avaliados por poucos usuários,
dificultam a geração de recomendações de qualidade, este problema é chamado de o problema da partida a frio (cold start problem).
Nos esquemas de filtragem colaborativa, dois tipos
de abordagem foram desenvolvidos, filtragem colaborativa baseada em memória (também conhecida
como baseada em usuários ou em itens) e filtragem
colaborativa baseada em modelo. Filtragens baseadas em usuário utilizam a similaridade entre o usuário alvo e seus vizinhos para prever a nota que o
usuário alvo atribuiria a itens que ele não avaliou
anteriormente. No entanto, a grande dimensão de
uma matriz usuário-item pode tornar o processo de
identificação de vizinhanças e cálculo de avaliações
diretamente a partir dos dados disponíveis computacionalmente caro.
Para reduzir o tempo necessário para fazer recomendações, uma grande diversidade de algoritmos
de filtragem colaborativa baseada em modelo tem
sido desenvolvida. Algoritmos baseados em modelo
utilizam os dados disponíveis para criar um modelo
e, então, este modelo é usado para fazer previsões,
em lugar de usar os dados diretamente. Deste modo,
o tempo necessário para fazer uma previsão usando
um algoritmo baseado em modelo costuma ser muito
menor do que quando se usa um algoritmo baseado
em memória. Por outro lado, um algoritmo baseado
em modelo deve, antes de fazer as previsões,
aprender o modelo, o que pode ser um processo
complexo e demorado. Deve-se notar ainda que,
frequentemente, os algoritmos baseados em memória são mais precisos que os baseados em modelo.
Figura 1. Exemplo de matriz usuário-item em FC.
Na filtragem colaborativa baseada em memória destacam-se duas abordagens principais: a baseada em
usuários, que forma vizinhanças de usuários, e a
baseada em itens, que forma vizinhanças de itens.
Ambas as abordagens são ilustradas pela Figura 1.
Ao invés de calcular a similaridade entre usuários, a
filtragem colaborativa baseada em itens faz previsões a partir da similaridade entre itens.
Geralmente, os sistemas de recomendação seguem
duas etapas. A primeira delas é a formação da vizinhança, onde se incluem os usuários que possuem
preferências parecidas com as do usuário alvo, no
caso de filtragem colaborativa baseada em usuário,
ou o conjunto de itens que são similares ao item
alvo, no caso de filtragem colaborativa baseada em
itens.
Na segunda etapa, a partir da vizinhança encontrada, é feita a previsão de uma nota para o par usuário-item alvo.
3. ETIQUETAGEM SOCIAL
Etiquetagem social é a prática de permitir que os
usuários associem etiquetas (tags) aos itens, com o
Anais do XVIII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do III Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
24 e 25 de setembro de 2013
propósito de descrevê-los ou categorizá-los [3]. Em
algumas circunstâncias, como na Web, quando não
há alguém encarregado de classificar os itens de
informação disponíveis ou quando há muitos itens
para serem classificados por uma só pessoa, a etiquetagem social é uma das maneiras mais úteis para
categorizar ou indexar um conteúdo. Além disso,
tags são diretamente publicadas e examinadas na
Web e podem ser aplicadas a qualquer tipo de item,
como também a pessoas.
O uso de etiquetas é uma alternativa para melhorar o
desempenho de sistemas de recomendação, podendo reduzir os problemas decorrentes tanto de dados
esparsos como da partida a frio.
Diferentemente de um sistema de recomendação
baseado somente em usuários e itens, um sistema
que se baseia em tags leva em conta mais informações para fazer uma recomendação. A matriz que
antes continha somente usuários e itens, agora ganha uma nova dimensão com as tags, ou seja, se
torna uma matriz tridimensional. É possível visualizar
essa matriz tridimensional em três projeções bidimensionais: usuário-item, usuário-tag e tag-item. No
sistema descrito em [2] base deste trabalho, os itens
representam páginas na Web acessados pelos usuários. Neste caso, uma posição da matriz usuário-item
indica indicará se o usuário acessou ou não o item; a
matriz usuário-tag indica quantas vezes o usuário
utilizou uma determinada tag para marcar uma página; e a matriz tag-item informa quantas vezes uma
tag foi associada a um item pela comunidade de
usuários.
4. UM SISTEMA DE RECOMENDAÇÃO BASEADO
EM FILTRAGEM COLABORATIVA E
ETIQUETAGEM SOCIAL
A Figura 2 apresenta a arquitetura do sistema de
recomendação baseado em etiquetagem social objeto do trabalho descrito neste artigo.
O sistema contempla duas fases, a primeira de construção de um modelo de tags candidatas, é representada pelos passos de (1) a (5) na Figura 2. Nessa
fase são geradas as tags latentes de interesse dos
usuários. Na segunda fase, a partir das tags candidatas, serão escolhidos os itens a recomendar aos
usuários alvo usando um classificador.
As etapas (1), (2) e (3) envolvem a construção das
matrizes A, Q e R, que consistem de projeções da
matriz tridimensional mencionada na seção 3.
A matriz usuário-tag, A, de dimensão l x m, tem como objetivo informar a quantidade de vezes que uma
tag foi usada por um usuário. Em A, as linhas representam os usuários e as colunas representam as
tags. Au,t indica o número de itens que um usuário u
marcou com a tag t.
A Figura 3 ilustra uma matriz usuário-tag. Essa matriz mostra, por exemplo, que o usuário Usuário 2
utilizou a tag Tag1 para marcar três páginas da Web
e que que não utilizou nenhuma outra tag.
Figura 3. Exemplo de matriz A (usuário-tag).
A Matriz tag-item, Q, de dimensão m x n, indica
quantas vezes uma tag foi associada a um item pela
comunidade de usuários. As linhas de Q representam as tags e as colunas os itens. No exemplo mostrado na Figura 4, A tag Tag3 foi associada três vezes (por três usuários) ao item Item1.
Figura 4. Exemplo de matriz Q (tag-item).
Figura 2. Arquitetura de Sistema de Recomendação
Baseado em Etiquetagem Social
A matriz binária usuário-item, denominada de R, tem
dimensão l x n, suas linhas representa os usuários e
as colunas os itens. A posição Ru,i, é preenchida
com um 1 se o usuário u selecionou (ou marcou) o
item i, e com zero em caso contrário. A matriz da
Figura 5 indica, por exemplo, que o usuário Luiz
Anais do XVIII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do III Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
24 e 25 de setembro de 2013
acessou as páginas do Google e do Youtube, mas
não do Facebook e do Twitter.
Figura 5. Exemplo de matriz R (usuário-item)
A partir das matrizes A, Q e R, pode-se determinar
um conjunto de tags candidatas para um usuário
alvo. Para a produção deste conjunto de tags assume-se que o usuário alvo deverá gostar de tags que
foram usadas previamente por usuários semelhantes
a ele e por ele próprio. Determinadas essas tags
pode-se recomendar ao usuário alvo itens (páginas
da Web) com forte correlação com essas tags, mas
que ainda não foram acessados pelo usuário alvo.
O uso deste modelo reduz a dificuldade para tratar
com dados esparsos e com a partida a frio, pois
mesmo que um usuário não tenha associado um
determinado item, a vinculação deste item a tags
pelas quais o usuário mostra interesse, permite inferir que o usuário terá interesse também por esse item
(site).
A etapa (4) da Figura 1 é uma das mais importantes
para se realizar uma recomendação, ela consista da
construção da matriz D de dimensão l x l , que indica
o grau de similaridade entre cada par de usuários.
Isso pode ser feito usando a similaridade do cosseno, definida pela equação (1), que mostra como calcular a similaridade entre dois usuários u e v.
sim(u , v) = cos(u , v) =
∑ t∈T ( Au, t ⋅ iuft )( Av, t ⋅ iuft )
∑ t∈T ( Au, t ⋅ iuf t ) 2 ∑ t∈T ( Av, t ⋅ iuf t ) 2
(1)
Na equação (1), T é o conjunto de tags, Au,t é o número de vezes que o usuário u, marcou a tag t, e Av,t
o número de vezes que o usuário v, marcou a tag t,
informação obtida da matriz A; iuft é a frequência
inversa para a tag t cálculada como log( l / nt) onde l
é o número total de usuários no sistema e nt o número de usuários que utilizaram a tag t.
A equação (1) produz um valor que varia de 0 até 1,
de modo que quanto mais semelhante um usuário u
for de um usuário v, mais próximo de 1 será o valor
de sim(u,v).
A etapa (5) consiste em identificar as tags candidatas
para cada usuário, a partir dos usuários que lhes são
mais próximos. A partir das tags candidatas de cada
usuário, na etapa (6) são recomendados itens vinculados a essas tags que ainda não foram acessados
pelos usuários.
Das seis etapas previstas na arquitetura mostrada na
Figura 2, foram implementados os módulos responsáveis pelas quatro primeiras. Limitações de tempo
não permitiram implementar as duas restantes, que
ficam como recomendação para trabalhos futuros.
Para a construção das matrizes A, Q e R, ilustradas
pelas figuras 3, 4 e 5, foram utilizados dados reais,
obtidos do del.icio.us (https://delicious.com/), um
conhecido serviço de marcação social de páginas na
Web que permite a etiquetagem colaborativa (collaborative tagging). Os conjuntos de dados (datasets)
utilizados contêm informação sobre 1867 usuários,
69226 URLs (endereços de páginas e sítios na Web)
e 53388 tags. Os dados estão disponíveis no sítio
do “2nd International Workshop on nformation Heterogeneity and Fusion in Recommender Systems
1
“5th ACM
(HetRec 2011)” , evento integrante do
Conference on Recommender Systems (RecSys
2011)”.
Devido à grande quantidade de dados envolvidos, foi
utilizado um sistema gerenciador de banco de dados
para armazenar os dados, sem necessidade de que
todos fiquem residentes na memória.
2
Foi utilizado o PostgreSQL , um sistema de gerenciamento de banco de dados objeto-relacional aberto,
para armazenar os dados dos datasets bem como
todos os demais dados de importância em tempo de
execução.
Foram feitos testes para verificar se a similaridade
entre usuários estava coerente com o previsto e
constatou-se que todos os valores obtidos nos testes
estão de acordo com o esperado. Por exemplo, a
similaridade de um usuário consigo mesmo sempre é
1. Por outro lado, quando dois usuários não marcaram nenhum item em comum, a similaridade entre
eles é 0.
Todas as matrizes necessárias para produzir recomendações, assim como o algoritmo que realiza o
cálculo de similaridade, foram implementados e funcionam satisfatoriamente, segundo os testes realizados.
1
2
http://recsys.acm.org/2011
http://www.postgresql.org/
Anais do XVIII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do III Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
24 e 25 de setembro de 2013
5. CONCLUSÕES
O trabalho descrito neste artigo se propôs a estudar
e implementar um sistema para recomendação híbrido que combina filtragem colaborativa e etiquetagem
social. A arquitetura do sistema foi definida a partir
de um trabalho inicial de pesquisa bibliográfica, ela
está em uma matriz tridimensional que representa
usuários, itens a recomendar e tags associadas aos
itens pelos usuários. A partir dessa matriz, o sistema
elabora recomendações em seis etapas. As três
primeiras consistem em construir projeções bidimensionais da matriz usuário-item-tag. Na quarta etapa é
criada uma matriz que indica a similaridade entre
cada par de usuários. Na quinta etapa, estas quatro
matrizes são usadas para construir, para cada usuário, um conjunto de tags de sua preferência. Estas
tags são usadas, na etapa seis, para recomendar
aos usuários itens vinculados a essas tags, mas que
ainda não foram acessados pelo usuário e que, portanto, devem ser de seu interesse. Foram implementados os módulos necessários às quatro primeiras
etapas. Feito isso, deu-se início à busca por um conjunto de dados (dataset) que pudesse ser usado para
testá-lo. O dataset selecionado contém dados reais
de usuários, tags e itens obtidos do sistema delicious, um serviço disponível na Web para a marcação
social de páginas na Web que permite a etiquetagem
colaborativa. Os módulos implementados foram testados e depurados utilizando esses dados. Por limitações de tempo, não foi possível concluir a implementação das etapas cinco e seis, o que se recomenda que seja feito em trabalhos futuros.
REFERÊNCIAS
[1] Celma, Ò. (2010), The Recommendation Problem,
in Music Recommendation and Discovery,, Berlin
Heidelberg: Springer-Verlag, pp. 15–41.
[2] Kim, H. N. et al. (2010), Collaborative filtering
based on collaborative tagging for enhancing the
quality of recommendation, Electronic Commerce
Research and Applications, vol. 9, n. 1, pp. 73–
83.
[3] Golder, S. A. et al. (2006), Usage patterns of collaborative tagging systems. Journal of Information
Science, 32, 2, pp. 198–208.