22

概括

正如 Ted Jaspers 明智地指出的那样，我在 2012 年最初提案中描述的方法实际上是指数移动平均线的一个特例。这种方法的美妙之处在于它可以递归计算，这意味着您只需为每个对象存储一个流行度值，然后您可以在事件发生时递归地调整该值。无需记录每个事件。

这个单一的流行度值代表所有过去的事件（在所使用的数据类型的限制内），但随着新事件的考虑，旧事件的重要性开始呈指数级降低。该算法将适应不同的时间尺度并响应不同的流量. 每次发生事件时，可以使用以下公式计算新的流行度值：

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

  • a— 介于 0 和 1 之间的系数（值越高，旧事件的折扣越快）
  • t— 当前时间戳
  • p— 当前流行度值（例如存储在数据库中）

的合理值a将取决于您的应用程序。一个好的起点是，应该显着影响结果的事件数量a=2/(N+1)在哪里。N例如，在事件是页面浏览的低流量网站上，您可能会期望在几天内有数百次页面浏览。选择N=100( a≈0.02) 将是一个合理的选择。对于一个高流量的网站，您可能期望在几天内有数百万的页面浏览量，在这种情况下N=1000000( a≈0.000002) 会更合理。的值a可能需要随着时间的推移逐渐调整。

为了说明这个流行度算法是多么简单，这里有一个例子，它可以在 Craft CMS 中用 2 行 Twig 标记来实现：

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

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

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

原始提案

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

p = (p + t) / 2

这里，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/

如果您希望投票以亚秒级的间隔稳定流入，那么您将需要使用微秒时间戳，例如 PHPmicrotime()函数。否则，标准 UNIX 时间戳将起作用，例如 PHPtime()函数。

现在我的问题是：您认为这种方法有什么重大缺陷吗？

4

5 回答 5

10

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

我做了一组快速的计算，发现这个算法似乎确实理解了“流行”的含义。它的问题是它明显倾向于支持最近的投票，如下所示：

想象一下，我们将时间分解为从 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.

于 2012-06-20T21:28:00.080 回答
4

所提出的算法是一种很好的方法，并且是指数移动平均线的一个特例，其中 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 个值的平均值
  • 等等
于 2018-08-03T10:47:58.207 回答
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 票后相等。

于 2012-06-21T09:08:10.840 回答
1

缺陷在于，有 100 票的东西通常比最近只有一张票的东西更有意义。然而，想出运行良好的方案变体并不难。

于 2012-06-20T21:07:57.713 回答
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 一样最近，其次，文章的浏览次数也比文章 A 多。

于 2018-04-27T04:13:30.260 回答