Um mecanismo de recomendação (às vezes referido como um sistema de recomendação) é uma ferramenta que permite desenvolvedores de algoritmos prever o que um usuário pode ou não gostar em uma lista de determinados itens. Os mecanismos de recomendação são uma alternativa muito interessante aos campos de pesquisa, pois os mecanismos de recomendação ajudam os usuários a descobrir produtos ou conteúdo 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 o que outros usuários gostam e não gostam, 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 é adequado para o problema sendo endereçado.

Neste tutorial, vamos orientá-lo no processo de construção de um mecanismo de recomendação que seja colaborativo e baseado em memória. Este 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 antes. Para este projeto, usaremos operações de conjunto básicas, 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 baseado em memória colaborativa, 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 nenhum outro atributo de um filme (por exemplo, o elenco, o diretor, o gênero, etc.) em consideração ao gerar recomendações. A similaridade entre dois usuários é representada por 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 por outro número decimal entre -1,0 e 1,0. Agora que modelamos o mundo em torno desse sistema usando termos simples, podemos lançar um punhado de elegantes equações matemáticas 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 fases em que as recomendações são geradas, uma série de conjuntos serão produzidos - principalmente uniões ou interseções dos outros conjuntos. Também teremos 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. Conhecida originalmente como “coeficiente de comunauté” (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 Jaccard de dois conjuntos idênticos sempre será 1, enquanto o índice Jaccard de dois conjuntos sem elementos comuns sempre renderá 0. Agora que sabemos como comparar dois conjuntos, vamos pensar em uma estratégia que podemos usar para comparar dois Comercial. Conforme discutido anteriormente, os usuários, do ponto de vista do sistema, são três coisas: um identificador, um conjunto de filmes favoritos e um conjunto de filmes não favoritos. Se definíssemos 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 sobre isso, 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 o número de gostos comuns também. 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 os desgostos de uma forma independente, devemos pensar também no caso em que dois usuários são opostos em suas preferências. O índice de semelhança de dois usuários em que um gosta de um filme e o outro não deve 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 para 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, temos que 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 gostando 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 baseado em memória colaborativa.

Construindo 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 HTML e formulários (usaremos o Bootstrap para fazer as páginas parecerem organizadas). No lado do servidor, usaremos CoffeeScript. O aplicativo terá algumas rotas GET e POST. Mesmo que tenhamos 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 Express.js para facilitar o processo de gerenciamento de rotas e manipuladores.

Neste ponto, se você é novo em Desenvolvimento Node.js , você pode querer clonar o Repositório GitHub para que seja mais fácil seguir este tutorial. Como com qualquer outro projeto Node.js, começaremos por criar um arquivo package.json e instalar 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 de que precisamos para este projeto são:

• assíncrono
• Bourne
• roteiro de café
• expressar
• jade
• sublinhado

Construiremos o mecanismo de recomendação dividindo todos os métodos relevantes em quatro classes CoffeeScript separadas, cada uma delas 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 de avaliador). Similares e sugestões serão responsáveis ​​por determinar e rastrear usuários semelhantes e itens recomendados para os usuários, respectivamente.

Acompanhar gostos e não gostos

Vamos primeiro começar com nossa classe Avaliadores. Este é 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 de Rater para curtir e outra para não gostar. Para registrar que um usuário gosta de um item, vamos passá-los para “Avaliador # add ()”. Da mesma forma, para remover a classificação, iremos repassá-los para “Avaliador # remove ()”.

Como estamos usando Bourne como uma solução de banco de dados sem servidor, armazenaremos essas classificações em um arquivo denominado “./db-#{@kind}.json”, em que kind é “curtir” ou “não gostar”. Vamos abrir o banco de dados dentro do construtor da instância 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 a removê-los (“db.delete” em vez de “db.insert”). No entanto, antes de adicionar ou remover algo, devemos garantir que 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 que a inserção ou exclusão é feita, precisamos ter certeza de recalcular os índices de similaridade para este usuário e, em seguida, gerar um conjunto de novas sugestões. Os métodos “Rater # add ()” e “Rater # remove ()” serão semelhantes a este:

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

Para resumir, ignoraremos as partes em que verificamos se há erros. Isso pode ser uma coisa razoável a 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 Rater é instanciado com kind = “likes”, “Rater # itemsByUser ()” encontrará todos os itens que o usuário classificou.

Encontrar usuários semelhantes

Seguindo para nossa próxima aula: Similares. Esta classe nos ajudará a calcular e controlar os índices de similaridade entre os usuários. Conforme discutido antes, calcular a similaridade entre dois usuários envolve a análise dos conjuntos de itens de que eles gostam e não gostam. Para fazer isso, contaremos com as instâncias de 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 denominado “./db-similars.json”, que abriremos no construtor de Rater. A classe terá um método “Similars # byUser ()”, que nos permitirá pesquisar usuários semelhantes a um determinado usuário através de uma consulta simples no banco de dados:

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

No entanto, o método mais importante dessa 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, junto com seus índices de similaridade. Ele começa encontrando o que o usuário gosta e não gosta:

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

No 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 de Jaccard.

Gerando Recomendações

Nossa próxima aula, Sugestões, é onde todas as previsões acontecem. Assim como a classe Similars, contamos com outro banco de dados Bourne denominado “./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 calculará esses resultados é “Suggestions # update ()”. Este método, como “Similars # update ()”, tomará um usuário como argumento. O método começa listando todos os usuários semelhantes ao usuário fornecido e todos os itens que o usuário não classificou:

@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 em 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, nós o salvamos de volta no banco de dados:

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

Expondo a Biblioteca API

Dentro da classe Engine, reunimos tudo em uma estrutura simples semelhante a uma API para facilitar o acesso do mundo externo:

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

Depois de instanciar um objeto Engine:

e = new Engine

Podemos adicionar ou remover facilmente gostos e não gostos:

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 semelhança do usuário:

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

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

module.exports = Engine

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

module.exports = require './engine'

Criação da interface do usuário

Para poder usar o algoritmo do mecanismo de recomendação neste tutorial, queremos fornecer uma interface de usuário simples na web. Para fazer isso, criamos um aplicativo Express dentro de nosso arquivo “web.iced” e tratamos de 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 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 não gostos do usuário e as quatro principais sugestões para o usuário. O código-fonte do modelo Jade foi 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 não gostos 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 anteriormente não gostava fará com que o manipulador remova a classificação de 'não gostar' primeiro. Essas rotas também permitem que o usuário “não goste” ou “não goste” de um item, se desejar.

Finalmente, a rota “/ refresh” permite ao usuário regenerar seu conjunto de recomendações sob demanda. No entanto, essa ação é executada automaticamente sempre que o usuário faz qualquer classificação para um item.

Passeio de teste

Se você tentou implementar este aplicativo do zero seguindo este artigo, você 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 como:

[ { '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.

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

$ npm start

Partindo do princípio de que tudo correu bem, deverá 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 se baseia apenas em um nome de usuário escolhido após visitar “http: // localhost: 5000”. Assim que um nome de usuário for inserido e o formulário for enviado, você será levado 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 (dados) baseado em memória colaborativa, não poderemos recomendar nenhum filme a esse novo usuário.

Nesse ponto, você deve abrir outra janela do navegador em “http: // localhost: 5000” e fazer login como um usuário diferente lá. 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 avaliar pelo menos alguns filmes comuns para ambos os usuários. Você deve começar a ver 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 este motor. Esta seção abordará brevemente algumas áreas onde as melhorias são essenciais para que isso seja usado em grande escala. No entanto, nos casos em que escalabilidade, estabilidade e outras propriedades são necessárias, você deve sempre recorrer ao uso de uma boa solução testada pelo tempo. Como no restante do artigo, a ideia aqui é fornecer alguns insights 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 arquivos. 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. Redis é rápido e tem capacidades especiais que são úteis ao lidar com estruturas de dados semelhantes a conjuntos.

Outro problema que podemos simplesmente contornar é o fato de que estamos calculando novas recomendações cada vez que um usuário faz ou altera suas avaliações para filmes. Em vez de fazer recálculos dinâmicos em tempo real, devemos enfileirar essas solicitações de atualização de recomendação para os usuários e executá-las nos bastidores - talvez definindo um intervalo de atualização cronometrado.

Além dessas escolhas “técnicas”, também existem algumas escolhas estratégicas que podem ser feitas para melhorar as recomendações. Conforme o número de itens e usuários aumenta, será 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 esse fosse um mecanismo de recomendação para restaurantes, você poderia limitar o conjunto de usuários semelhante para conter apenas os usuários que moram na mesma cidade ou estado.

Outras melhorias podem envolver uma abordagem híbrida, onde 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

Os 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 Recommendable, são construídas sobre ideias fundamentais semelhantes.

Como a maioria dos outros problemas de ciência da computação que envolvem muitos dados, obter recomendações corretas tem muito a ver com escolhendo o algoritmo certo e atributos apropriados do conteúdo para trabalhar. Espero que este artigo tenha dado uma ideia do que acontece dentro de um mecanismo de recomendação baseado em memória colaborativa quando você o está usando.