Uma introdução aos algoritmos de classificação vistos em agregadores de notícias sociais

Você já se perguntou como seus agregadores de notícias sociais favoritos, como Reddit ou Hacker News, classificam seus links? Eles usam alguns algoritmos de classificação simples para mostrar as histórias e comentários mais interessantes no topo. Então vamos ver como eles funcionam para que você possa começar a usá-los em seus próprios projetos.

Quente

ATUALIZAÇÃO : O hotalgoritmo do reddit mudou em 12 de janeiro de 2014. Escrevi um extenso artigo sobre o impacto dessa mudança em meu blog.

Este é o tipo de algoritmo usado para a página inicial. É muito mais simples do que você imagina. Ele calcula uma pontuação para cada item com base no número de votos e subtrai pontos com base na idade do item.

Uma versão simples desse algoritmo poderia ser assim:

score = upvotes - downvotes
score
= score + age_in_seconds # newer means a higher age which should net a higher score

Na prática, essa implementação não é realmente útil, então vamos dar uma olhada em como o Reddit faz isso :

cpdef double _hot(long ups, long downs, double date):
"""The hot formula. Should match the equivalent function in postgres."""
s
= score(ups, downs)
order
= log10(max(abs(s), 1))
if s > 0:
sign
= 1
elif s < 0:
sign
= -1
else:
sign
= 0
seconds
= date - 1134028003
return round(order + sign * seconds / 45000, 7)

cpdef
long score(long ups, long downs):
return ups - downs

Como você pode ver, o Reddit começa calculando uma ups - downspontuação simples que coloca em uma escala logarítmica. Por quê? Um link com pontuação de 5.000 é realmente muito melhor do que um com 4.000? Que tal 10 contra 30? Essa escala logarítmica reduz o impacto de votos adicionais, a menos que haja muito mais.

Em seguida, ele calcula um secondsvalor que é uma representação inteira da idade do link. De onde 1134028003vem isso? É o carimbo de data / hora UNIX para quinta-feira, 8 de dezembro de 2005 7:46:43 AM UTC, a data em que introduziram a classificação quente ao público.

Finalmente, ele divide esse secondsvalor por 45.000, que é 12,5 horas. Isso significa que a cada 12,5 horas anteriores à quinta-feira, 8 de dezembro de 2005, as novas histórias têm 1 ponto a mais do que as anteriores.

É isso para o algoritmo de classificação quente, se você quiser ver exatamente como a escala do log e a idade afetam as classificações, eu o encorajo a ler este artigo detalhado sobre algoritmos de classificação do Reddit .

Topo

O algoritmo de classificação superior simplesmente determina quais itens têm as pontuações mais altas, ele não discrimina a idade e sempre retornará o item com a pontuação mais alta. Isso pode parecer bom o suficiente para um agregador de notícias, mas depois de apenas alguns dias, você notaria que a lista nunca muda. Este algoritmo oferece uma tremenda vantagem para os itens mais antigos e para aqueles que obtiveram uma vantagem de pontuação inicial, criando um efeito de bola de neve e enterrando qualquer item que não teve a sorte de obter alguns votos positivos iniciais.

Melhor

Este é um pouco mais complicado. Ele é usado para mostrar os itens com maior probabilidade de interesse no topo. Como isso faz? Usando o cálculo de um intervalo de pontuação de confiança . Mais especificamente, o Reddit usa o intervalo de pontuação de Wilson . Basicamente, um intervalo de pontuação de confiança leva em consideração a quantidade de votos para determinar se a pontuação representa adequadamente o valor do item. O algoritmo é menos confiante sobre a pontuação de um item com apenas alguns votos do que um com centenas de votos. Dessa forma, um item com 3 votos positivos pode ser classificado pior do que um com 300 centenas de positivos e uma dúzia ou mais de negativos.

Não vou detalhar o algoritmo do Reddit aqui, pois não há [números mágicos] ( https://en.wikipedia.org/wiki/Magic_number_(programming#Unnamed_numerical_constants) .

Mais uma vez, para mais informações e para ver como as votações positivas , negativas e o número de votos afetam a classificação, leia o artigo de Amir Salihefendic sobre algoritmos do Reddit .

Novo

Os itens mais recentes aparecem primeiro, eu não acho que preciso me preocupar em explicar este.

Referências