Concrete Logo
Hamburger button

Sistemas de recomendações

  • Blog
  • 17 de Janeiro de 2012
Share

[fblike]

 

Texto começando com estes versos parece que será sobre algo semelhante ao tema do livro Paradoxo das escolhas do psicólogo e professor americano Barry Schwartz. Aliás vale muito a pena ver seu vídeo no TED.

Quem pensou assim não errou por muito. Se hoje em dia é difícil escolher, então deve ser importante conseguir boas recomendações.

Qual câmara devo comprar?
Qual filme devo alugar?
Qual livro ler?
Quem o Luca deve convidar para dividir uma pizza que tenha um gosto mais parecido com o dele?

Recomendações

A gente pode tentar vários meios:

  • – Perguntar aos amigos;
  • – consultar a Internet;
  • – seguir a multidão;
  • – contratar um especialista: melhor aplicação financeira, tratamento médico, obra de engenharia, chamar o vizinho para instalar o Office, ops… melhor parar porque neste caso nós somos os vizinhos…

A maioria já usou um sistema de recomendação na Internet. Um sistema assim tem que saber um pouco de cada usuário e elaborar um perfil. Para coletar preferências, se pode perguntar explicitamente ao visitante ou deduzir informações de forma implicita monitorando o seu comportamento. O bom é adotar as duas alternativas com os comportamentos, opiniões e gostos possibilitando formar comunidades de usuários. Sistemas assim são às vezes ditos como baseados em comunidades ou colaborativos.

Como começou

Tudo começou em 1992 com o sistema Tapestry de David Godberg do centro de pesquisas da XEROX. O objetivo era permitir que pessoas fizessem anotações em documentos do tipo Like/Dislike e usar esta informação para filtrar documentos para outras passoas. Foi quando surgiu a idéia e a terminologia de filtros colaborativos. Ver Using collaborative filtering to weave an information tapestry ou A Tour Through Tapestry.

O que usaram

Outros sistemas foram pesquisados nesta mesma linha de filtros colaborativos. Eles identificavam outros usuários com gostos similares pelas menores distâncias entre as suas notas de avaliação (ou entre as médias ponderadas das distâncias). Usaram um algoritmo chamado k-nearest neighbor ou k-NN, descrito inicialmente nos anos 50 mas que só a partir dos anos 60 começou a ser usado em computação. Este algoritmo simples se comprovou tão bom para filtros colaborativos ou recomendações, que virou o padrão “ouro” contra o qual todos os demais eram comparados. O uso de médias ponderadas serve para considerar que alguns atributos sejam mais importantes do que outros.

Onde quero chegar

Os amigos leitores mais assíduos já reconheceram que todo este blá, blá, blá de introdução tem a ver com a discussão do Testinho 2 que justamente tratava de recomendação e em cuja solução, quase todo mundo pensou no conceito de distância para medir similaridades.

O testinho 2 é um caso típico de filtro colaborativo puro que é justamente o tipo em que se parte de uma avaliação por notas. Se a recomendação fosse feita com análises dos comportamentos de navegação, a partir das análises das compras passadas ou uma mistura de todos, a melhor abordagem de solução poderia ser diferente da k-NN.

Recomendação ou filtragem colaborativa pura

Este tipo de algoritmo normalmente funciona pesquisando um grupo de pessoas e encontrando um subconjunto com gostos semelhantes ao seu. Quando os dados aparecem em uma matriz com notas, temos o caso mais simples de recomendações. É o primeiro abordado no excelente livro Programming Collective Intelligence de Toby Segaran. Veio de lá a idéia do testinho 2.

Idéia básica da abordagem k-NN

Dada uma tabela com notas de cada indivíduo, identificar outros (peers ou nearest neighbors) com preferências similares.

Modos usuais de identificar preferências similares

1- Escala de distância euclidiana

Imaginem um sistema de eixos em um espaço n-dimensional em que cada eixo corresponde a um item de preferências e cada nota é um ponto neste eixo. Exatamente como explicou o Edward Ribeiro em seu comentário.

O cálculo da distância se faz de modo similar a como se calcula a distância entre dois pontos no plano ou no espaço: pega a diferença entre os dois pontos em cada eixo, eleva ao quadrado, soma e extrai a raiz quadrada da soma. A distância euclidiana entre os pontos  e , num espaço euclidiano n-dimensional, é definida como dist =

Talvez por ser engenheiro e ter trabalhado muito com computação gráfica, este me parece o método mais intuitivo. Porém nas respostas teve gente que intuiu diferente e achei muito bom.

Vamos usar a fórmula acima com os pontos da tabela de notas das pizzas do testinho 2 para calcular as distâncias para o Luca:

Renato 2.4495 0.290
Marcelo 4.2426 0.191
Lenon 4.1231 0.195
Renata 4.3589 0.187
Washington 5.3852 0.157
Tino 4.5826 0.179

O número na terceira coluna corresponde a normalização 1/(1+dist) sugerida no livro Programming Collective Intelligence. Na área de Data Mining, Machine Learning, Web Mining e afins, é comum a normalização dos resultados para facilitar as comparações.

Pelas distâncias calculadas, vemos que Renato tem gosto para pizza mais próximo ao de Luca.

Nas respostas ao testinho 2 tivemos 3 respostas usando o método da distância euclidiana: Willian Gouveia (Clojure), Edward Ribeiro (Java), Fábio Miranda (python)  e Bruno Politano (JavaScript)

2 – Escala de correlação de Pearson

Correlação é uma técnica para investigar a relação entre 2 variáveis. Exemplo: idade e pressão sanguínea. O coeficiente de correlação de Pearson (r) é uma medida da força de associação entre 2 variáveis.

Para tentar imaginar o que pode ser força de associação, imagine um gráfico com uma das variáveis no eixo X e a outra no eixo Y. Quanto mais perto estão os pontos plotados de uma linha reta, maior a força da associação.

Correlação negativa indica que uma variável cresce enquanto outra decresce e positiva quando ambas crescem. O gráfico do centro é de um caso em que as variáveis não tem a mínima relação, não se correlacionam. Quanto mais perto de 1 o coeficiente, melhor as variáveis se relacionam.

O cálculo do coeficiente para 2 váriáveis x e y, se faz com a fórmula r =

onde   e   são os valores medidos de ambas as variáveis e

são as médias aritméticas de ambas as variáveis.

Nas respostas o Daniel Romero (Ruby) e o Andrei Formiga (R) optaram pela correlação de Pearson para achar minhas afinidades.

Como gosto muito de R para estatística, vou usar o código do prof Andrei para montar a tabela com os coeficientes de Pearson:

Renato 0.633
Marcelo -0.069
Lenon 0.350
Renata 0.114
Washington -0.630
Tino 0.117

De novo vemos que o Renato se correlaciona melhor comigo na hora de pedir a pizza.

O coeficiente de correlação de Pearson costuma oferecer melhores resultados em situações onde as avaliações estão predominantemente de um dos lados.

3- Outros algoritmos

Não vou me estender muito sobre os outros modos que são muitos. A similaridade do cosseno é um deles e é o único que vale uma citação especial. Mas aí vai um link com diversos algoritmos de similaridade programados em Java: IR Math with Java : Similarity Measures.

Demais respostas ao testinho 2

Aconteceu uma coisa bem legal nas respostas ao teste. Uma delas se baseou na intuição pura sem usar os meios usuais dos livros. Sim, é claro que admiro o estudo, adoro estudar e se fosse eu, iria direto em busca de teoria antes de responder algo novo. Mas não posso deixar de aplaudir quem consegue uma resposta boa adequada ao problema usando seus próprios caminhos. Foi o que fez o Daniel Faria Gomes (Java). Ele simplesmente achou a diferença numérica entre as notas. Deu certo, pelo menos neste caso.

E o André Fonseca mostrou o caminho certo mas faltou mostrar o código

 

Apesar da boa surpresa das respostas usando R e JavaScript, senti falta de Scala e PHP. O livro Programming Collective Intelligence realmente é ótimo. Seus exemplos usam Python. Mas muita gente já resolveu os exemplos em outras linguagens. O negócio é partir para uma busca no Github ou no Google Code.

Comparando algoritmos

Para fazer comparações baseadas em usuários, o livro Recommender Systems: An Introduction, cita um estudo empírico de 1999 em An Algorithmic Framework for Performing Collaborative Filtering, que aponta o coeficiente de correlação de Pearson como sendo o melhor. Mas há muitos casos em que o melhor é usar a similaridade do cosseno.

Comparar algoritmos nessa área mostra que é difícil obter ganhos consideráveis aumentando a complexidade dos cáculos. A prova da dificuldade foi o prêmio oferecido em 2006 pela Netflix para quem conseguisse melhorar o algoritmo de recomendação deles em mais ou menos 10%. Ver regulamento e a solução vencedora. O time de três pesquisadores da AT&T conseguiu uma melhoria de 8.43%. A Netflix repetiu o concurso mais três vezes com o nome de Netflix Progress Prize. Os mesmos pesquisadores da AT&T repetiram o sucesso do primeiro concurso.

Considerações finais

No enunciado pedi que experimentassem alterar as notas e o único que fez foi o Bruno Politano. Ele simulou uma situação, em que aparentemente os gostos de Luca e Renato estão mais próximos, porém as fórmulas indicam que a similaridade de gostos está entre Luca e Marcelo. Isto mostra o quanto de cuidado é preciso. Fica o alerta.

O que falamos aqui não está longe do que a Amazon mostrou em 2003 quando divulgou como fazia suas recomendações em Recommendations: Item-to-Item Collaborative Filtering. E já tinha 29 milhões de usuários e milhões de produtos. Eles usaram o método de medir a similaridade pelo cosseno.

É claro que é preciso bastante esperteza no jeito de armazenar os dados. Um dos primeiros artigos a abordar este tema ainda em 2000 foi Application of dimensionality reduction in recommender systems – a case study de Badrul Sarwar, que aliás é citado no artigo da Amazon.

 

E então? Ficou o gostinho de incluir no seu e-commerce facilidades de recomendações dos produtos?

Comentários e sugestões de novos testes são bem-vindos!