Recomendação de páginas utilizando dados de amigos do Facebook

VN:RO [1.9.11_1134]
quinta-feira, 22 d dezembro d 2011
Por Wilson Leão Neto

Disclaimer: Este artigo tem caráter introdutório. Assim, se você já tiver um conhecimento do assunto, poderá apenas escaneá-lo.  Opiniões do que seria interessante ter como prioridade para abordagem em próximos artigos ou comentários sobre qual conteúdo ficou dúbio ou falho serão bem-vindos.

Você já ouviu falar de sistema de recomendação? Já teve a curiosidade de saber como funciona? Pois, então, prossiga na leitura. Em especial, abordarei o tema utilizando terminologias e dados da rede social Facebook.

Introdução

Você já ouviu falar de sistema de recomendação? Já teve a curiosidade de saber como funciona? Pois, então, prossiga na leitura. Em especial, abordarei o tema utilizando terminologias e dados da rede social Facebook.

Por quê? O Facebook é uma rede social gigantesca e, provavelmente, quase todos os seus amigos possuem uma conta lá.

Alguns sistemas, por exemplo o GiveEmThis.com, propõem a utilização dos dados dos seus amigos para auxiliar a tarefa da compra de presentes. Podemos também citar a Amazon, a qual possui iniciativa que utiliza dados sociais do Facebook para personalização de recomendações (notícia no mashable). Hoje em dia, fala-se muito sobre sistemas de recomendação e, acredito, que você não deva passar um dia sem receber algum tipo de informação de algum sistema do gênero.

No decorrer do artigo, apresentarei, de maneira geral, os conceitos e formas para o entendimento e desenvolvimento de um simples sistema de recomendação de páginas (likes) utilizando os dados dos seus amigos do Facebook. Por simples, quero dizer não serão abordadas formas de como lidar com o fato de os dados serem esparsos; nem com o fato de estarmos mexendo com um grafo, por exemplo, podemos coletar dados do amigo do amigo do amigo; nem mesmo com fato de estarmos em um contexto social (laços de amizade). Nos restringiremos, assim, aos nossos amigos imediatos, ok? Se você entendeu pouco ou nada deste último parágrafo, não tem problema. Se tiver curiosidade, mande um e-mail. Além do mais, neste primeiro artigo, não entrarei em detalhes de como coletar os dados.

Recomendação de páginas (no exemplo, página da banda AC/DC) utilizando likes de amigos

Para quem não conhece a mecânica do Facebook: através dele é possível gostar de páginas, por exemplo, um usuário pode gostar (like) da página de uma banda de rock. Porém, não há a opção negativa, ou seja, não gostar de alguma página explicitamente (dislike). Estes likes criam links entre os usuários e as páginas e podem ser utilizados para tarefas interessantes (além da tratada aqui), por exemplo, para segmentação de mercado. Na nova versão do OpenGraph (que atualmente está em Beta) do Facebook , é possível executar “ações” que ligam usuários às páginas (e outros objetos), por exemplo, a Ana comprou o CD do ACDC. Mas isso é tema para artigo futuro.

Filtragem Colaborativa

Imagine, agora, uma situação em que você esteja conversando com um amigo. Você sabe que ele gosta de seriados, filmes e bandas com as quais você também se identifica, ou seja, os seus gostos são similares. Nesta conversa, ele recomenda um filme que ele gosta, mas que você não conhece. Assim, por conhecer os gostos dele, você fica curioso em assistir ao filme. Este processo se repete diariamente em nossas vidas. Agora imagine o caso em que, ao invés de um amigo, estamos lidando com um grupo de amigos, cujos gostos são conhecidos, alguns mais similares e outros menos. Como poderemos filtrar recomendações destes amigos?

De maneira geral, para um simples sistema de recomendação que lide com objetos e usuários, os laços de amizade não importam. Neste artigo, também iremos ignorar os laços de amizade. Mas adianto que podemos desenvolver sistemas que exploram estes laços para obtenção de melhores recomendações personalizadas.

Podemos abordar o problema com uma técnica que é conhecida, na literatura, por filtragem colaborativa baseada em usuários (tradução livre do inglês user-based collaborative filtering). O termo ilustra o fato de vários usuários estarem colaborando para que o sistema filtre uma recomendação para você. Neste caso, para filtrar recomendações, o sistema explora a similaridade entre usuários utilizando as ligações entre estes e os objetos. Existe, também, o caso em que a filtragem é baseada nos objetos (item-based collaborative filtering), no qual, o sistema explora a similaridade entre os objetos utilizando as ligações entre usuários e objetos. Detalhes, vantagens e desvantagens das duas abordagens podem ser explorados em outro artigo.

Definição do problema e modelagem dos dados

Na definição do problema, temos como objetivo desenvolver um recomendador de gostos (possíveis novas ligações entre você e uma página recomendada) baseado em gostos de outros usuários (ligações já existentes). A partir do Facebook, podemos obter dados dos usuários (você e amigos), das páginas e das ligações entre eles.

Esses dados podem ser representados em uma matriz, na qual as linhas representam os usuários e as colunas representam os objetos. Nas células da matriz, 1 indica que o usuário (linha) desta célula gosta do objeto (coluna), e 0 indica que o usuário não conhece o objeto ou que não gosta deste (discutiremos isto novamente).

Matriz de Dados - exemplo com 5 usuários e 5 páginas, os testes foram feitos com 5 usuários e 250 páginas

Cálculo de similaridades

Agora, o recomendador deve quantificar as similaridades entre você e seus amigos. Por exemplo, imagine que você goste de 5 páginas, sua amiga Ana goste de 10, que vocês gostem de 3 em comum (interseção) e que, juntando todas as páginas que você e Ana gostem, temos 12 páginas (união). Podemos expressar a similaridade entre vocês dois pela razão entre o total de páginas em comum pelo total de páginas juntas, ou seja, a quantificação da similaridade seria de 3/12 (0.25). Se você conhece notação de conjuntos, fica como exercício traduzir o para ela.

Existem diversas formas de calcular a similaridade entre duas entidades. No caso, o coeficiente descrito é conhecido por coeficiente de similaridade de Jaccard. Podemos, por exemplo, calcular esse coeficiente utilizando distância euclidiana, correlação de Pearson, entre outras formas.

Gerando recomendações

Agora que temos uma maneira de quantificar as similaridades entre você e os seus amigos. Podemos, por curiosidade, obter uma lista dos amigos do usuário Alvo (usuário de testes) ordenada pelo coeficiente de similaridade utilizado. O usuário criado para os testes deste artigo possui 4 amigos (visualizar matriz de dados).

 

Lista de amigos ordenados pelo coeficiente de similaridade (neste caso, coeficiente de Jaccard)

Observe os valores dos coeficientes. O valor final está no invervalo [0,1]. Os valores são baixos pois o total de elementos do conjunto de gostos derivados da união de duas pessoas é muito grande. O total de páginas que gostamos pode ser pouco comparado ao total existente (a matriz resultante da representação dos dados é esparsa). Por exemplo, Bob pode gostar de 206 páginas, enquanto você gosta de apenas 6, todas em comum com Bob. Então, o valor da similaridade calculado será baixo, mas como estamos calculando os valores em relação a você, o valor será alto para você. Para Bob, talvez este valor seja baixo mesmo, ou seja, talvez exista uma amiga Carla que goste de 30 objetos em comum com Bob, enquanto você gosta de apenas 6 (repare que o apenas é relativo). O zero do coeficiente indica que não há gostos em comum.

Podemos, de imediato, dar uma olhada nos gostos do amigo que ficou em primeiro lugar e escolher aleatoriamente algo que não conhecemos. Mas, o recomendador pode fazer melhor. O resultado final pode ser obtido utilizando-se uma média ponderada das páginas que ainda não conhecemos utilizando os coeficientes de similaridade dos nossos amigos como pesos. Os valores obtidos podem ser interpretados como a probabilidade de nós gostarmos do objeto em questão.

Exemplo de cálculo da média ponderada para o usuário Alvo e página JovemNerd. Notações: sim(W,Z) representa o coeficiente de similaridade entre W e Z; Like(X, Y), expressa se X gosta da página Y.

Para efetuar a média ponderada, utilizaremos tantos os 0s quanto os 1s associados a uma página. No like do Facebook, a escala encontrada é limitada, 0 ou 1, e nela, o valor de 0 não significa o contrário do valor 1, ou seja, 1 significa que gostamos, mas 0 pode significar que não conhecemos ou que não gostamos da página. Mesmo assim, o recomendador pode utilizar os 0s para amortizar a recomendação final.

Imagine que sua amiga Ana goste de uma página, que a similaridade entre vocês seja 0,1, que seu amigo Bob não goste desta página e que a similaridade entre vocês seja 0,8. Se não levarmos em consideração o 0 do Bob na média ponderada, o recomendador retornará 1 para a página em questão. Na verdade, o recomendador retornará 1 para todas as página que algum amigo seu goste e que você não conheça, pense um pouco. Se levarmos em consideração o 0 do Bob, que é muito similar a você, o recomendador amortizará o valor e retornará 0,1/0,9, aproximadamente 0,11, um valor baixo que expressa o fato de que se a Ana gosta e vocês não são tão similares, talvez você não goste mesmo.

Para a conta final, o recomendador calcula os coeficientes de similaridade entre você e seus amigos e armazena os valores. Então, para todos os 0s da sua linha na matriz (páginas que você não conheça), o recomendador realiza a média ponderada dos seus amigos: soma as similaridades dos amigos que gostam da página, divide pela soma total das similaridades e armazena onde encontrou o 0. Ao final, teremos valores inferidos pelo recomendador que expressam, baseando-se nos dados dos seus amigos, a probabilidade de vocês gostar das páginas que estavam com 0s.

 

As 5 primeiras páginas recomendadas.

Cálculo para a página JovemNerd

Considerações

A abordagem que utilizamos é simples o bastante para que possamos entender os conceitos envolvidos e o que acontece por debaixo dos panos. Por ser simples, não recomendo a implementação desta abordagem em produção. Ela possui alguns problemas.

A abordagem não é escalável. Imagine que o seu sistema possua 100 usuários com 300 amigos cada, assim, o recomendador terá que fazer as contas explicadas usuário por usuário e terá que fazer novamente assim que houver alguma mudança.

O recomendador pode ser alvo fácil de ataques. Imagine que criemos um usuário David, fazemos amizade com o usuário que queremos atacar e fazemos com que David goste de todas as páginas que o nosso usuário alvo goste, assim, o coeficiente de similaridade será alto. Em seguida, David é programado para gostar de uma página que temos interesse que o usuário alvo goste. Pronto, o recomendador colocará esta página em uma posição alta na lista dada a similaridade entre os dois usuários.

O que acontece com usuários que não gostaram de nada ainda? Todos os coeficientes de similaridades serão nulos pois não possuem gostos em comum com ninguém. Na literatura, este problema é conhecido como the cold start problem.

Além do mais, o recomendador em questão possui baixa serendipidade (do inglês serendipity), talvez até nula, e, assim, caminharíamos aos poucos para um monoculturalismo. Nos próximos artigos poderemos entrar em detalhes de soluções que lidem com esses problemas.

VN:F [1.9.11_1134]
Rating: 5.0/5 (4 votes cast)
Recomendação de páginas utilizando dados de amigos do Facebook, 5.0 out of 5 based on 4 ratings
Related Posts with Thumbnails

Tags: , ,

Deixe um Comentário

Spam Protection by WP-SpamFree

Get Adobe Flash playerPlugin by wpburn.com wordpress themes