Prevendo curtidas: por dentro dos algoritmos de um mecanismo de recomendação simples

Um mecanismo de recomendação (às vezes chamado de sistema de recomendação) é uma ferramenta que permite que os desenvolvedores de algoritmos prevejam o que um usuário pode ou não gostar em uma lista de itens fornecidos. Os mecanismos de recomendação são uma alternativa bastante interessante aos campos de pesquisa, pois os mecanismos de recomendação ajudam os usuários a descobrir produtos ou conteúdos que, de outra forma, eles não encontrariam. Isso torna os mecanismos de recomendação uma grande parte de sites e serviços como Facebook, YouTube, Amazon e muito mais.

Os mecanismos de recomendação funcionam idealmente de duas maneiras. Ele pode contar com as propriedades dos itens que um usuário gosta, que são analisadas para determinar o que mais o usuário pode gostar; ou pode contar com os gostos e desgostos de outros usuários, que o mecanismo de recomendação usa para calcular um índice de similaridade entre os usuários e recomendar itens a eles de acordo. Também é possível combinar esses dois métodos para construir um mecanismo de recomendação muito mais robusto. No entanto, como todos os outros problemas relacionados à informação, é essencial escolher um algoritmo que seja adequado para o problema a ser abordado.

Neste tutorial, vamos orientá-lo no processo de construção de um mecanismo de recomendação colaborativo e baseado em memória. Esse mecanismo de recomendação recomendará filmes aos usuários com base no que eles gostam e não gostam e funcionará como o segundo exemplo mencionado anteriormente. Para este projeto, usaremos operações básicas de conjunto, um pouco de matemática e Node.js/CoffeeScript. Todo o código-fonte relevante para este tutorial pode ser encontrado aqui.

Conjuntos e equações

Antes de implementar um mecanismo de recomendação colaborativo baseado em memória, devemos primeiro entender a ideia central por trás de tal sistema. Para este motor, cada item e cada usuário nada mais são do que identificadores. Portanto, não levaremos em consideração nenhum outro atributo de um filme (por exemplo, elenco, diretor, gênero etc.) ao gerar recomendações. A semelhança entre dois usuários é representada usando um número decimal entre -1,0 e 1,0. Chamaremos esse número de índice de similaridade. Por fim, a possibilidade de um usuário gostar de um filme será representada usando outro número decimal entre -1,0 e 1,0. Agora que modelamos o mundo em torno desse sistema usando termos simples, podemos liberar um punhado de equações matemáticas elegantes para definir a relação entre esses identificadores e números.

Em nosso algoritmo de recomendação, manteremos vários conjuntos. Cada usuário terá dois conjuntos: um conjunto de filmes que o usuário gosta e um conjunto de filmes que o usuário não gosta. Cada filme também terá dois conjuntos associados a ele: um conjunto de usuários que gostou do filme e um conjunto de usuários que não gostou do filme. Durante as etapas em que as recomendações são geradas, vários conjuntos serão produzidos - principalmente uniões ou interseções dos outros conjuntos. Teremos também listas ordenadas de sugestões e usuários semelhantes para cada usuário.

Para calcular o índice de similaridade, usaremos uma variação da fórmula do índice de Jaccard. Originalmente conhecido como “coeficiente de comunidade” (cunhado por Paul Jaccard), a fórmula compara dois conjuntos e produz uma estatística decimal simples entre 0 e 1,0:

A fórmula envolve a divisão do número de elementos comuns em qualquer conjunto pelo número de todos os elementos (contados apenas uma vez) em ambos os conjuntos. O índice de Jaccard de dois conjuntos idênticos será sempre 1, enquanto o índice de Jaccard de dois conjuntos sem elementos comuns sempre resultará em 0. Agora que sabemos como comparar dois conjuntos, vamos pensar em uma estratégia que podemos usar para comparar dois conjuntos. Comercial. Conforme discutido anteriormente, os usuários, do ponto de vista do sistema, são três coisas: um identificador, um conjunto de filmes que gostaram e um conjunto de filmes que não gostaram. Se definissemos o índice de similaridade de nossos usuários com base apenas no conjunto de seus filmes favoritos, poderíamos usar diretamente a fórmula do índice Jaccard:

Aqui, U1 e U2 são os dois usuários que estamos comparando, e L1 e L2 são os conjuntos de filmes que U1 e U2 gostaram, respectivamente. Agora, se você pensar bem, dois usuários que gostam dos mesmos filmes são semelhantes, então dois usuários que não gostam dos mesmos filmes também devem ser semelhantes. É aqui que modificamos um pouco a equação:

Em vez de apenas considerar os gostos comuns no numerador da fórmula, agora adicionamos também o número de desgostos comuns. No denominador, pegamos o número de todos os itens que o usuário gostou ou não gostou. Agora que consideramos os gostos e desgostos de maneira independente, também devemos pensar no caso em que dois usuários são opostos polares em suas preferências. O índice de similaridade de dois usuários onde um gosta de um filme e o outro não gosta não deveria ser 0:

Essa é uma fórmula longa! Mas é simples, eu prometo. É semelhante à nossa fórmula anterior com uma pequena diferença no numerador. Agora estamos subtraindo o número de gostos e desgostos conflitantes dos dois usuários do número de gostos e desgostos comuns. Isso faz com que a fórmula do índice de similaridade tenha um intervalo de valores entre -1,0 e 1,0. Dois usuários com gostos idênticos terão um índice de similaridade de 1,0, enquanto dois usuários com gostos totalmente conflitantes em filmes terão um índice de similaridade de -1,0.

Agora que sabemos como comparar dois usuários com base em seu gosto por filmes, precisamos explorar mais uma fórmula antes de começarmos a implementar nosso algoritmo de mecanismo de recomendação caseiro:

Vamos quebrar essa equação um pouco. O que queremos dizer com P(U,M) é a possibilidade de um usuário U gostar do filme M . ZL e ZD são a soma dos índices de similaridade do usuário U com todos os usuários que gostaram ou não gostaram do filme M , respectivamente. |ML|+|MD| representa o número total de usuários que gostaram ou não gostaram do filme M . O resultado P(U,M) produz um número entre -1,0 e 1,0.

É sobre isso. Na próxima seção, podemos usar essas fórmulas para começar a implementar nosso mecanismo de recomendação colaborativo baseado em memória.

Criando o mecanismo de recomendação

Construiremos esse mecanismo de recomendação como um aplicativo Node.js muito simples. Também haverá muito pouco trabalho no front-end, principalmente algumas páginas e formulários HTML (usaremos o Bootstrap para tornar as páginas mais organizadas). No lado do servidor, usaremos CoffeeScript. A aplicação terá algumas rotas GET e POST. Apesar de termos a noção de usuários no aplicativo, não teremos nenhum mecanismo elaborado de registro/login. Para persistência, usaremos o pacote Bourne disponível via NPM, que permite que um aplicativo armazene dados em arquivos JSON simples e execute consultas básicas de banco de dados neles. Usaremos o Express.js para facilitar o processo de gerenciamento de rotas e manipuladores.

Neste ponto, se você é novo no desenvolvimento do Node.js, talvez queira clonar o repositório do GitHub para que seja mais fácil seguir este tutorial. Como em qualquer outro projeto Node.js, começaremos criando um arquivo package.json e instalando um conjunto de pacotes de dependência necessários para este projeto. Se você estiver usando o repositório clonado, o arquivo package.json já deve estar lá, de onde a instalação das dependências exigirá que você execute “$ npm install”. Isso instalará todos os pacotes listados dentro do arquivo package.json.

Os pacotes Node.js que precisamos para este projeto são:

• assíncrono
• bourne
• roteiro de café
• expressar
• jade
• sublinhar

Construiremos o mecanismo de recomendação dividindo todos os métodos relevantes em quatro classes CoffeeScript separadas, cada uma das quais armazenada em “lib/engine”: Engine, Rater, Similars e Suggestions. A classe Engine será responsável por fornecer uma API simples para o mecanismo de recomendação e vinculará as outras três classes. O Avaliador será responsável por rastrear gostos e desgostos (como duas instâncias separadas da classe Avaliador). Similares e Sugestões serão responsáveis ​​por determinar e rastrear usuários semelhantes e itens recomendados para os usuários, respectivamente.

Rastreamento de curtidas e não curtidas

Vamos começar com nossa classe de Conceitualizadores. Este é um simples:

 class Rater constructor: (@engine, @kind) -> add: (user, item, done) -> remove: (user, item, done) -> itemsByUser: (user, done) -> usersByItem: (item, done) ->

Conforme indicado anteriormente neste tutorial, teremos uma instância do Rater para curtidas e outra para desgostos. Para registrar que um usuário gostou de um item, vamos passá-lo para “Rater#add()”. Da mesma forma, para remover a classificação, vamos passá-la para “Rater#remove()”.

Como estamos usando o Bourne como uma solução de banco de dados sem servidor, armazenaremos essas classificações em um arquivo chamado “./db-#{@kind}.json”, onde kind é “likes” ou “dislikes”. Vamos abrir o banco de dados dentro do construtor da instância do Rater:

 constructor: (@engine, @kind) -> @db = new Bourne "./db-#{@kind}.json"

Isso tornará a adição de registros de classificação tão simples quanto chamar um método de banco de dados Bourne dentro de nosso método “Rater#add()”:

 @db.insert user: user, item: item, (err) =>

E é semelhante removê-los (“db.delete” em vez de “db.insert”). No entanto, antes de adicionar ou remover algo, devemos garantir que ele ainda não exista no banco de dados. Idealmente, com um banco de dados real, poderíamos ter feito isso como uma única operação. Com Bourne, temos que fazer uma verificação manual primeiro; e, uma vez feita a inserção ou exclusão, precisamos ter certeza de que recalculamos os índices de similaridade para esse usuário e, em seguida, geramos um conjunto de novas sugestões. Os métodos “Rater#add()” e “Rater#remove()” terão a seguinte aparência:

 add: (user, item, done) -> @db.find user: user, item: item, (err, res) => if res.length > 0 return done() @db.insert user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done remove: (user, item, done) -> @db.delete user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done

Por brevidade, vamos pular as partes em que verificamos os erros. Isso pode ser uma coisa razoável de se fazer em um artigo, mas não é uma desculpa para ignorar erros no código real.

Os outros dois métodos, “Rater#itemsByUser()” e “Rater#usersByItem()” desta classe envolverão fazer o que seus nomes implicam - procurar itens avaliados por um usuário e usuários que avaliaram um item, respectivamente. Por exemplo, quando o Rater é instanciado com kind = “likes” , “Rater#itemsByUser()” encontrará todos os itens que o usuário avaliou.

Encontrando usuários semelhantes

Passando para nossa próxima aula: Similares. Essa classe nos ajudará a calcular e acompanhar os índices de similaridade entre os usuários. Conforme discutido anteriormente, calcular a similaridade entre dois usuários envolve analisar os conjuntos de itens que eles gostam e não gostam. Para fazer isso, contaremos com as instâncias do Rater para buscar os conjuntos de itens relevantes e, em seguida, determinar o índice de similaridade para certos pares de usuários usando a fórmula do índice de similaridade.

Assim como nossa classe anterior, Rater, colocaremos tudo em um banco de dados Bourne chamado “./db-similars.json”, que abriremos no construtor do Rater. A classe terá um método “Similars#byUser()”, que nos permitirá procurar usuários semelhantes a um determinado usuário por meio de uma consulta simples ao banco de dados:

 @db.findOne user: user, (err, {others}) =>

No entanto, o método mais importante desta classe é “Similars#update()” que funciona pegando um usuário e computando uma lista de outros usuários que são semelhantes, e armazenando a lista no banco de dados, juntamente com seus índices de similaridade. Ele começa encontrando os gostos e desgostos do usuário:

 async.auto userLikes: (done) => @engine.likes.itemsByUser user, done userDislikes: (done) => @engine.dislikes.itemsByUser user, done , (err, {userLikes, userDislikes}) => items = _.flatten([userLikes, userDislikes])

Também encontramos todos os usuários que avaliaram esses itens:

 async.map items, (item, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.usersByItem item, done , done , (err, others) =>

Em seguida, para cada um desses outros usuários, calculamos o índice de similaridade e armazenamos tudo no banco de dados:

 async.map others, (other, done) => async.auto otherLikes: (done) => @engine.likes.itemsByUser other, done otherDislikes: (done) => @engine.dislikes.itemsByUser other, done , (err, {otherLikes, otherDislikes}) => done null, user: other similarity: (_.intersection(userLikes, otherLikes).length+_.intersection(userDislikes, otherDislikes).length-_.intersection(userLikes, otherDislikes).length-_.intersection(userDislikes, otherLikes).length) / _.union(userLikes, otherLikes, userDislikes, otherDislikes).length , (err, others) => @db.insert user: user others: others , done

Dentro do snippet acima, você notará que temos uma expressão de natureza idêntica à nossa fórmula de índice de similaridade, uma variante da fórmula de índice Jaccard.

Gerando Recomendações

Nossa próxima aula, Sugestões, é onde todas as previsões acontecem. Assim como a classe Similares, contamos com outro banco de dados Bourne chamado “./db-suggestions.json”, aberto dentro do construtor.

A classe terá um método “Suggestions#forUser()” para pesquisar sugestões computadas para o usuário fornecido:

 forUser: (user, done) -> @db.findOne user: user, (err, {suggestions}={suggestion: []}) -> done null, suggestions

O método que irá calcular esses resultados é “Sugestões#atualização()”. Este método, como “Similars#update()”, receberá um usuário como argumento. O método começa listando todos os usuários semelhantes a um determinado usuário e todos os itens que o usuário não avaliou:

 @engine.similars.byUser user, (err, others) => async.auto likes: (done) => @engine.likes.itemsByUser user, done dislikes: (done) => @engine.dislikes.itemsByUser user, done items: (done) => async.map others, (other, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.itemsByUser other.user, done , done , done , (err, {likes, dislikes, items}) => items = _.difference _.unique(_.flatten items), likes, dislikes

Assim que tivermos todos os outros usuários e os itens não classificados listados, podemos começar a computar um novo conjunto de recomendações removendo qualquer conjunto anterior de recomendações, iterando sobre cada item e computando a possibilidade de o usuário gostar com base nas informações disponíveis:

 @db.delete user: user, (err) => async.map items, (item, done) => async.auto likers: (done) => @engine.likes.usersByItem item, done dislikers: (done) => @engine.dislikes.usersByItem item, done , (err, {likers, dislikers}) => numerator = 0 for other in _.without _.flatten([likers, dislikers]), user other = _.findWhere(others, user: other) if other? numerator += other.similarity done null, item: item weight: numerator / _.union(likers, dislikers).length , (err, suggestions) =>

Feito isso, salvamos de volta no banco de dados:

 @db.insert user: user suggestions: suggestions , done

Expondo a API Library

Dentro da classe Engine, vinculamos tudo em uma estrutura semelhante à API para facilitar o acesso do mundo exterior:

 class Engine constructor: -> @likes = new Rater @, 'likes' @dislikes = new Rater @, 'dislikes' @similars = new Similars @ @suggestions = new Suggestions @

Uma vez que instanciamos um objeto Engine:

 e = new Engine

Podemos facilmente adicionar ou remover gostos e desgostos:

 e.likes.add user, item, (err) -> e.dislikes.add user, item, (err) ->

Também podemos começar a atualizar os índices e sugestões de similaridade do usuário:

 e.similars.update user, (err) -> e.suggestions.update user, (err) ->

Por fim, é importante exportar esta classe Engine (e todas as outras classes) de seus respectivos arquivos “.coffee”:

 module.exports = Engine

Em seguida, exporte o Engine do pacote criando um arquivo “index.coffee” com uma única linha:

 module.exports = require './engine'

Criando a interface do usuário

Para poder usar o algoritmo do mecanismo de recomendação neste tutorial, queremos fornecer uma interface de usuário simples pela web. Para fazer isso, geramos um aplicativo Express dentro do nosso arquivo “web.iced” e lidamos com algumas rotas:

 movies = require './data/movies.json' Engine = require './lib/engine' e = new Eengine app = express() app.set 'views', "#{__dirname}/views" app.set 'view engine', 'jade' app.route('/refresh') .post(({query}, res, next) -> async.series [ (done) => e.similars.update query.user, done (done) => e.suggestions.update query.user, done ], (err) => res.redirect "/?user=#{query.user}" ) app.route('/like') .post(({query}, res, next) -> if query.unset is 'yes' e.likes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.dislikes.remove query.user, query.movie, (err) => e.likes.add query.user, query.movie, (err) => if err? return next err res.redirect "/?user=#{query.user}" ) app.route('/dislike') .post(({query}, res, next) -> if query.unset is 'yes' e.dislikes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.likes.remove query.user, query.movie, (err) => e.dislikes.add query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" ) app.route('/') .get(({query}, res, next) -> async.auto likes: (done) => e.likes.itemsByUser query.user, done dislikes: (done) => e.dislikes.itemsByUser query.user, done suggestions: (done) => e.suggestions.forUser query.user, (err, suggestions) => done null, _.map _.sortBy(suggestions, (suggestion) -> -suggestion.weight), (suggestion) => _.findWhere movies, id: suggestion.item , (err, {likes, dislikes, suggestions}) => res.render 'index', movies: movies user: query.user likes: likes dislikes: dislikes suggestions: suggestions[...4] )

Dentro do aplicativo, lidamos com quatro rotas. A rota de índice “/” é onde servimos o HTML de front-end renderizando um modelo Jade. A geração do modelo requer uma lista de filmes, o nome de usuário do usuário atual, os gostos e desgostos do usuário e as quatro principais sugestões para o usuário. O código fonte do template Jade é deixado de fora do artigo, mas está disponível no repositório GitHub.

As rotas “/like” e “/dislike” são onde aceitamos solicitações POST para registrar os gostos e desgostos do usuário. Ambas as rotas adicionam uma classificação removendo primeiro qualquer classificação conflitante, se necessário. Por exemplo, um usuário que gosta de algo que não gostou anteriormente fará com que o manipulador remova primeiro a classificação de "não gostei". Essas rotas também permitem que o usuário "não goste" ou "não goste" de um item, se desejar.

Por fim, a rota “/refresh” permite que o usuário gere novamente seu conjunto de recomendações sob demanda. No entanto, esta ação é executada automaticamente sempre que o usuário faz alguma avaliação para um item.

Passeio de teste

Se você tentou implementar este aplicativo do zero seguindo este artigo, precisará executar uma última etapa antes de testá-lo. Você precisará criar um arquivo “.json” em “data/movies.json” e preenchê-lo com alguns dados do filme da seguinte forma:

 [ { "id": "1", "name": "Transformers: Age of Extinction", "thumb": { "url": "//upload.wikimedia.org/wikipedia/en/7/7f/Inception_ver3.jpg" } }, // … ]

Você pode querer copiar o disponível no repositório GitHub, que é pré-preenchido com um punhado de nomes de filmes e URLs de miniaturas.

Quando todo o código-fonte estiver pronto e conectado, iniciar o processo do servidor requer que o seguinte comando seja invocado:

 $ npm start

Supondo que tudo correu bem, você deve ver o seguinte texto aparecer no terminal:

 Listening on 5000

Como não implementamos nenhum sistema de autenticação de usuário verdadeiro, o aplicativo protótipo depende apenas de um nome de usuário escolhido após visitar “http://localhost:5000”. Depois que um nome de usuário for inserido e o formulário for enviado, você deverá ser direcionado para outra página com duas seções: “Filmes recomendados” e “Todos os filmes”. Como não temos o elemento mais importante de um mecanismo de recomendação colaborativo baseado em memória (dados), não poderemos recomendar nenhum filme para esse novo usuário.

Neste ponto, você deve abrir outra janela do navegador para “http://localhost:5000” e fazer login como um usuário diferente. Gostar e não gostar de alguns filmes como este segundo usuário. Retorne à janela do navegador do primeiro usuário e avalie alguns filmes também. Certifique-se de classificar pelo menos alguns filmes comuns para ambos os usuários. Você deve começar a ver as recomendações imediatamente.

Melhorias

Neste tutorial de algoritmo, o que construímos é um mecanismo de recomendação de protótipo. Certamente existem maneiras de melhorar esse mecanismo. Esta seção abordará brevemente algumas áreas onde melhorias são essenciais para que isso seja usado em larga escala. No entanto, nos casos em que escalabilidade, estabilidade e outras propriedades semelhantes são necessárias, você deve sempre recorrer ao uso de uma boa solução testada pelo tempo. Assim como o restante do artigo, a ideia aqui é fornecer algumas informações sobre como funciona um mecanismo de recomendação. Em vez de discutir as falhas óbvias do método atual (como condição de corrida em alguns dos métodos que implementamos), as melhorias serão discutidas em um nível superior.

Uma melhoria muito óbvia aqui é usar um banco de dados real, em vez de nossa solução baseada em arquivo. A solução baseada em arquivo pode funcionar bem em um protótipo em pequena escala, mas não é uma escolha razoável para uso real. Uma opção entre muitas é o Redis. O Redis é rápido e possui recursos especiais que são úteis ao lidar com estruturas de dados do tipo conjunto.

Outro problema que podemos simplesmente contornar é o fato de que estamos calculando novas recomendações toda vez que um usuário faz ou altera suas classificações para filmes. Em vez de fazer recálculos dinamicamente em tempo real, devemos enfileirar essas solicitações de atualização de recomendação para os usuários e realizá-las em segundo plano - talvez definindo um intervalo de atualização cronometrado.

Além dessas escolhas “técnicas”, existem também algumas escolhas estratégicas que podem ser feitas para melhorar as recomendações. À medida que o número de itens e usuários cresce, tornar-se-á cada vez mais caro (em termos de tempo e recursos do sistema) gerar recomendações. É possível tornar isso mais rápido escolhendo apenas um subconjunto de usuários para gerar recomendações, em vez de processar todo o banco de dados todas as vezes. Por exemplo, se este fosse um mecanismo de recomendação para restaurantes, você poderia limitar o conjunto de usuários semelhantes para conter apenas os usuários que moram na mesma cidade ou estado.

Outras melhorias podem envolver a adoção de uma abordagem híbrida, na qual as recomendações são geradas com base na filtragem colaborativa e na filtragem baseada em conteúdo. Isso seria especialmente bom com conteúdo como filmes, onde as propriedades do conteúdo são bem definidas. A Netflix, por exemplo, segue esse caminho, recomendando filmes com base nas atividades de outros usuários e nos atributos dos filmes.

Conclusão

Algoritmos de mecanismo de recomendação colaborativa baseados em memória podem ser uma coisa muito poderosa. O que experimentamos neste artigo pode ser primitivo, mas também é simples: simples de entender e simples de construir. Pode estar longe de ser perfeito, mas implementações robustas de mecanismos de recomendação, como o Recommendable, são construídas com base em ideias fundamentais semelhantes.

Como a maioria dos outros problemas de ciência da computação que envolvem muitos dados, obter recomendações corretas é muito sobre escolher o algoritmo certo e os atributos apropriados do conteúdo para trabalhar. Espero que este artigo tenha lhe dado um vislumbre do que acontece dentro de um mecanismo de recomendação colaborativo baseado em memória quando você o estiver usando.