简单流行算法

Question

有很多建议的算法可以根据项目的年龄以及项目收到的投票,点击次数或购买次数来计算受欢迎程度.但是,我看到的更健壮的方法通常需要过于复杂的计算和多个存储的值,这会使数据库变得混乱.我一直在考虑一种非常简单的算法,它不需要存储任何变量(除了流行度值本身)并且只需要一个简单的计算.这简直太荒谬了:

(a * t) + ((1 - a) * p)

这里,p是存储在数据库中的流行度值,t是当前时间戳.首次创建项目时,必须初始化p.有两种可能的初始化方法:

1. 使用当前时间戳t初始化p
2. 使用数据库中所有p值的平均值初始化p

请注意,初始化方法(1)为最近添加的项目提供了优于历史项目的明显优势,从而添加了相关元素.另一方面,初始化方法(2)在与历史项目进行比较时将新项目视为等于.

假设您使用初始化方法(1)并使用当前时间戳初始化p.当项目收到第一次投票时,p成为创建时间和投票时间的平均值.因此,流行度值p仍表示有效时间戳(假设您舍入到最接近的整数),但它表示的实际时间是抽象的.

使用此方法,只需要一个简单的计算,并且只需要将一个值存储在数据库中(p).此方法还可以防止失控值,因为给定项目的受欢迎程度永远不会超过当前时间.

在1天 的时间内工作的算法示例:http://jsfiddle.net/q2UCn/
在1年时间内工作的算法示例:http://jsfiddle.net/tWU9y/

如果您希望投票以亚秒级间隔稳定地流入,那么您将需要使用微秒时间戳,例如PHP a函数.否则,标准UNIX时间戳将起作用,例如PHP t函数.

现在我的问题是:你看到这种方法有什么重大缺陷吗？

Answer 1

我认为这是一个非常好的方法,因为它简单.一个非常有趣的结果.

我做了一个快速的计算,发现这个算法似乎确实理解"流行度"的含义.问题在于它明显倾向于支持这样的近期投票:

想象一下,我们花时间将其分解为100到1000的离散时间戳值.假设在t = 100时A和B(两个项目)具有相同的P = 100.

    A gets voted 7 times on 200, 300, 400, 500, 600, 700 and 800
resulting on a final Pa(800) = 700 (aprox).

    B gets voted 4 times on 300, 500, 700 and 900 
resulting on a final Pb(900) = 712 (aprox).

当t = 1000时,A和B都会收到投票,所以:

Pa(1000) = 850 with 8 votes
Pb(1000) = 856 with 5 votes

为什么？因为该算法允许项目在收到最近的投票时快速击败历史领导者(即使该项目的总票数较少).

编辑包括模拟

OP创建了一个很好的小提琴,我改变了以获得以下结果:

http://jsfiddle.net/wBV2c/6/

Item A receives one vote each day from 1970 till 2012 (15339 votes)
Item B receives one vote each month from Jan to Jul 2012 (7 votes)

The result: B is more popular than A.

Answer 2

所提出的算法是一种很好的方法，并且是指数移动平均线的特例，其中 alpha=0.5：

p = alpha*p + (1-alpha)*t = 0.5*p + 0.5*t = (p+t)/2    //(for alpha = 0.5)

调整 alpha=0.5 的提议解决方案倾向于支持最近投票（如 daniloquio 指出）这一事实的一种方法是选择更高的 alpha 值（例如 0.9 或 0.99）。请注意，将此应用于 daniloquio 提出的测试用例是行不通的，因为当 alpha 增加时，算法需要更多的“时间”来稳定（因此数组应该更长，这在实际应用中通常是正确的）。

因此：

• 当 alpha=0.9 时，算法对最后 10 个值进行平均
• 对于 alpha=0.99，算法对大约最后 100 个值进行平均
• 对于 alpha=0.999，算法对最后 1000 个值进行大约平均
• ETC。