简单的流行度算法

Question

简单的流行度算法

22

摘要

正如Ted Jaspers所指出的那样，我在2012年原始提案中描述的方法实际上是指数移动平均线的一种特殊情况。这种方法的美妙之处在于它可以进行递归计算，这意味着您只需要为每个对象存储一个单独的受欢迎度值，然后当事件发生时可以递归地调整此值。不需要记录每个事件。

这个单一的受欢迎度值代表了所有过去的事件（在使用的数据类型的限制范围内），但随着新事件的加入，旧事件的影响会呈指数级下降。这个算法将适应不同的时间尺度，并对不同的流量变化做出反应。每次发生事件时，可以使用以下公式计算新的受欢迎度值：

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

a — 系数介于0和1之间（较高的值更快地减少旧事件的影响）
t — 当前时间戳
p — 当前的受欢迎度值（例如存储在数据库中）

Reasonable values for a will depend on your application. A good starting place is a=2/(N+1), where N is the number of events that should significantly affect the outcome. For example, on a low-traffic website where the event is a page view, you might expect hundreds of page views over a period of a few days. Choosing N=100 (a≈0.02) would be a reasonable choice. For a high-traffic website, you might expect millions of page views over a period of a few days, in which case N=1000000 (a≈0.000002) would be more reasonable. The value for a will likely need to be gradually adjusted over time.

为了说明这个流行度算法的简单性，以下是在Craft CMS中实现它的两行Twig标记的示例：

{% set popularity = (0.02 * date().timestamp) + (0.98 * entry.popularity) %}
{% do entry.setFieldValue("popularity", popularity) %}

请注意，为了计算流行度，无需创建新的数据库表或存储无尽的事件记录。

需要记住的一个警告是指数移动平均值具有自旋间隔，因此在值可以被认为准确之前需要进行几次递归。这意味着初始条件很重要。例如，如果使用当前时间戳初始化新项目的流行度，则该项目立即成为整个集合中最受欢迎的项目，然后最终定居到更准确的位置。如果您想推广新内容，这可能是可取的。或者，您可能希望内容从底部开始工作，在这种情况下，您可以使用应用程序首次启动的时间戳来初始化它。您还可以通过使用数据库中所有流行度值的平均值来初始化值，从而使其从中间开始。

原始提案

有很多建议的算法可以根据物品的年龄和物品接收到的投票、点击或购买数量来计算受欢迎程度。然而，我见过的更强大的方法通常需要过于复杂的计算和多个存储的值，这会使数据库变得混乱。我一直在思考一种极其简单的算法，它不需要存储任何变量（除了受欢迎度值本身）并且只需要一个简单的计算。它非常简单：

p = (p + t) / 2

在这里，p是存储在数据库中的受欢迎度值，t是当前时间戳。当一个物品被创建时，必须初始化p。有两种可能的初始化方法：

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

请注意，初始化方法（1）使最近添加的项目比历史项目具有明显优势，从而增加了一种相关性元素。另一方面，初始化方法（2）将新项目视为与历史项目相等。

假设您使用初始化方法（1），并使用当前时间戳初始化p。当该项收到第一个投票时，p成为创建时间和投票时间的平均值。因此，流行度值p仍表示有效的时间戳（假设四舍五入到最近的整数），但它所代表的实际时间是抽象的。

使用此方法，只需要进行一次简单的计算，并且数据库中只需要存储一个值（p）。该方法还可以防止运行值，因为给定项的流行度永远不能超过当前时间。

算法在1天内工作的示例：http://jsfiddle.net/q2UCn/ 算法在1年内工作的示例：http://jsfiddle.net/tWU9y/ 如果您希望投票以每秒的子级间隔稳定流入，则需要使用微秒时间戳，例如PHP的microtime()函数。否则，标准的UNIX时间戳将起作用，例如PHP的time()函数。

现在我的问题是：您是否认为这种方法存在任何主要缺陷？

- David Jones

2

如果您允许用户“取消点赞”，这不仅需要将p存储在数据库中。您还必须存储每个点赞的记录。否则，用户可以一遍又一遍地点赞、取消点赞、再点赞、再取消点赞，以膨胀他们的投票数。正如您所说，您只想在物品收到第一张选票时更改其p。这意味着您需要跟踪所有选票。 - Al Sweigart

@AlSweigart 很好的观点。这个算法可能只适用于单向投票系统（例如，页面浏览是正向“投票”中的一个）。它可能与双向投票系统不太兼容。 - David Jones

5个回答

4

这个提议的算法是一个不错的方法，它是指数移动平均的特殊情况（Exponential Moving Average），其中alpha=0.5：

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

一种调整建议方案 α=0.5 偏向于最近投票的方法（正如 daniloquio 所指出的）是选择更高的 α 值（例如 0.9 或 0.99）。需要注意的是，将其应用于 daniloquio 提出的测试用例是无效的，因为当 α 增加时，算法需要更多的“时间”来稳定（所以数组应该更长，在实际应用中通常是这样的）。

因此：

对于 α=0.9，算法平均大约最后10个值
对于 α=0.99，算法平均大约最后100个值
对于 α=0.999，算法平均大约最后1000个值
等等。

- Ted Jaspers

非常棒的回答！不过，文章中说“更高的α会更快地折扣旧观察结果”，所以你描述的方式不应该是相反的吗？ - David Jones

3

我看到一个问题，只有最后的约24票才起作用。

p_i+1 = (p + t) / 2

我们需要两个选票

p2 = (p1 + t2) / 2 = ((p0 + t1) /2 + t2 ) / 2 = p0/4 + t1/4 + t2/2

将其扩展到32个投票，得到如下结果:

p32 = t*2^-32 + t0*2^-32 + t1*2^-31 + t2*2^-30 + ... + t31*2^-1

针对有符号的32位数值，t0不会影响结果。因为t0被2^32除后，对p32没有任何贡献。

如果我们有两个项目A和B（无论差异有多大），如果它们都获得了相同的32票，它们将具有相同的受欢迎程度。因此，您的历史只到32票。如果最后32票相同，2032和32票之间没有区别。

如果差异小于一天，则在17票后它们将相等。

- Ishtar

1

这是不正确的。我在这里证明你是错的: http://jsfiddle.net/q2UCn/。这是你上面概述的确切分析的实际计算（A项在与B项接收17票的同一天接受了217票）。我还对1年内的25个投票进行了此分析（http://jsfiddle.net/tWU9y/），得出了类似的结果。 - David Jones

哎呀，你说得对。我没有正确地解释结果。已经修复了。 - Ishtar

伊斯塔尔：没错。如果两个项目在完全相同的时间内都收到32票，那么四舍五入将导致它们的受欢迎度值相同。这里有证据：http://jsfiddle.net/c4RVr/。然而，除非投票以亚秒间隔稳定流入，否则发生这种情况的概率是*极其*小的。在这种情况下，您可以简单地使用微秒时间戳（例如PHP的`microtime()`函数）。这解决了问题。这取决于您期望的流量有多大。 - David Jones

@danielfaraday - 即使只有一个项目，在32个投票后，所有历史记录都会丢失。您只跟踪最后32个投票。这是否是一个问题取决于您。如果您使用微秒（或说64位），则需要更多的投票来清除历史记录，但是，比起第32个最后一次投票之前的所有投票，几秒钟后进行投票的影响更大。 - Ishtar

@danielfaraday - 不客气 :). 这里有一个测试 http://jsfiddle.net/cyC7R/，包括一个不太流行的项目和一个极其流行的项目，在一年内都会获得32个随机投票。它们之间的差异会逐渐消失，你可以尝试给A“toc”或B 0，这并不重要。只有最后几个才算！ - Ishtar

2

漏洞在于，通常情况下，拥有100个投票的东西比只有一个最近投票的东西更有意义。然而，很容易想出你的方案的变体，可以达到合理的效果。

- btilly

但是最近1次投票的时间戳不会被直接采用。相反，它将与一个更早的投票进行平均化。这可能会导致该项排名低于具有100个投票的项（除非所有100个投票都发生在很长时间之前）。 - David Jones

此外，如果这100个投票确实发生在很久以前，那么基于时间的流行度定义将要求拥有100个投票的项目排名低于最近1个投票的项目。 - David Jones

+1 对于最后一句话，我同意你的观点，假设一些奇怪但不频繁的结果是可以接受的。 - daniloquio

假设物品A在1912年被创建，并每年获得一票，直到2012年（总共100票）。为了让物品B在最后一秒钟以仅1票的优势击败物品A，它必须最近才被创建，例如2009年！这相当于97年后！这是证明：http://jsfiddle.net/wBV2c/。因此，您的评论是无效的。即使一个只有1票的物品最近获得了那1票，拥有100票的物品*仍然*会有更高的受欢迎度值。这实际上证明了这个简单算法的强大之处。 - David Jones

0

我认为上述讨论的逻辑不会起作用。 p_i+1= (p_i + t) /2

文章A在时间戳上被查看：70、80、90，受欢迎程度（文章A）：82.5

文章B在时间戳上被查看：50、60、70、80、90，受欢迎程度（文章B）：80.625

在这种情况下，文章B的受欢迎程度应该更高。首先，文章B最近被查看，其次，它也比文章A被查看的次数更多。

- RAJIV MITTAL

1

在你的例子中，你会期望A和B的受欢迎程度在t → ∞时相等，这正是发生的事情。然而，鉴于初始条件是文章A比文章B更新，文章A将始终略微领先于文章B。正如讨论的那样，该算法偏向于新内容而不是旧内容。我认为这实际上很好地代表了现实生活中的情况——与旧文章相比，新文章往往更相关，因此在其他所有条件相等的情况下，新文章应该获胜。请记住，该算法的目标不是成为最好的，而是最简单的。 - David Jones

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- daniloquio · Accepted Answer

我认为这是一种非常简单易懂的方法，非常有趣的结果。

我进行了快速计算，并发现这个算法似乎理解了“流行度”的含义。它的问题在于，它明显倾向于支持最近的投票，例如：

假设我们将时间分成从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

为什么呢？因为这个算法可以让一项在总票数上排名较低的内容，只要它获得了最近的投票，就可以迅速超过历史领先者。

编辑包括模拟

原作者创建了一个不错的fiddle，我进行了更改并得到以下结果：

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)

结果：B比A更受欢迎。