Data

24 nov, 2016

A implementação (apropriada) de um ranking de popularidade

Publicidade

Eu estava lendo um artigo publicado recentemente chamado “Ruby on Rails implementation of a ranking system using PostgreSQL window functions”, e para ser sincero o propósito do texto era apresentar a função “ntile” do PostgreSQL.

Mas, no processo, o autor cometeu o mesmo erro que eu já vi várias vezes.

Vamos assumir que você tenha um projeto com recursos que você quer listar por “popularidade”. Pode ser um site tipo o Reddit, onde as pessoas curtem ou negativam postagens ou comentários. Pode ser um comercio eletrônico, onde as pessoas curtem ou negativam os produtos.

Pode ser qualquer coisa onde as pessoas possam curtir ou negativar alguma coisa.

O maior erro é considerar um placar simples desta maneira:

popularity = positive_votes - negative_votes

Existe um artigo antigo intitulado “How Not To Sort By Average Rating” e eu o parafraseio:

“Por que está errado: Suponha que um item tenha 600 classificações positivas e 400 negativas: 60% positivas. Suponha que o item dois tenha 5.500 classificações positivas e 4.500 classificações negativas: 55% positivas. Esse algoritmo coloca o item 2 (pontuação: 1000, mas apenas 55% positivo) acima do item 1 (pontuação: 200, mas 60% positivo). ERRADO”.

Então você pode pensar: “Eu sei como resolver!”.

Score = average_rating = positive_votes / total_votes

Novamente, está errado e, novamente, parafraseio:

“Por que está errado: pontuação média funciona bem se você sempre tiver muitas avaliações. Mas suponha que o item 1 tem 2 classificações positivas e nenhuma negativa. Suponha que o item 2 tem 100 classificações positivas e 1 classificação negativa. Esse algoritmo coloca o item 2 (muitas classificações positivas) abaixo do item 1 (pouquíssimas classificações). ERRADO”.

Solução correta: limite inferior do intervalo de confiança  de Wilson Score para Bernoulli

E eu parafraseio novamente:

“Digamos que nós precisamos balancear a proporção de classificações positivas com a incerteza de um número muito baixo de observações. Felizmente, o cálculo para isso foi realizado em 1927 por Edwin B. Wilson. O que nós queremos perguntar é: dadas as estatísticas que tenho, existe uma chance de 95% de que a fração ‘real’ de classificações positivas é ao menos quanto? Wilson nos dá a resposta. Considerando somente classificações positivas e negativas (ex.: não for utilizada classificação de 1 – 5 estrelas), o limite inferior da proporção de classificações positivas é dado por:

rating-equation

Eu recomendo a leitura do artigo original mas vamos direto ao ponto. Se nós seguirmos o artigo original, cujo link coloquei no início deste texto, eu tenho uma postagem no blog de um simples app em Rails, mas, em vez de um campo visits_count, eu preciso adicionar os campos positive:integer e negative:integer e fazer a interface dos votos dos usuários.

E eu vou trocar a classe PostWithPopularityQuery pelo seguinte:

class PostWithPopularityQuery
  def self.call
    Post.find_by_sql ['SELECT id, title, body, positive, negative,
        ((positive + 1.9208) / (positive + negative) -
        1.96 * SQRT((positive * negative) / (positive + negative) + 0.9604) /
        (positive + negative)) / (1 + 3.8416 / (positive + negative))
        AS ci_lower_bound
      FROM posts 
      WHERE positive + negative > 0
      ORDER BY ci_lower_bound DESC']
  end
end

E é isto o que eu espero ver com um simples quadro no index.html.erb:

screen_shot

Eu iria ainda mais longe e recomendaria o ci_lower_bound para ser um campo flutuante na tabela e para ter um ActiveJob assíncrono para atualizar com um intervalo de tempo maior (a cada 5 minutos, por exemplo), e então a ação PostsController#index faria uma busca direta usando um SELECT na base ordenando diretamente em um campo indexado real ci_lower_bound DESC, sem realizar os cálculos em todas as pesquisas.

Agora, essa é a maneira correta implementar um sistema simples e ingênuo de ranqueamento de popularidade que realmente funciona corretamente.

E essa não é a única maneira de fazermos isso. Existem dúzias de boas discussões sobre algoritmos online. Cada serviço que dependa de conteúdo de popularidade tem refinado os algoritmos há anos. O Facebook utilizava um algoritmo chamado “EdgeRank” que se baseava em variáveis como afinidade, peso, tempo de decaimento, e parece que evoluiu muito e que agora calcula a popularidade utilizando mais de 100 mil variáveis!

Mas, independentemente do serviço online, eu posso assegurar que nenhuma ordenação por contador de visitas ou por média de votos contaria. Isso seria completamente errado.

***

Artigo traduzido com autorização do autor. Publicado originalmente em  http://www.akitaonrails.com/2016/10/31/ruby-on-rails-implementation-of-a-proper-ranking-popularity-system.