algorithm - 简单普及算法

Question

概要

正如Ted Jaspers明智地指出的那样，我在2012年的原始提案中描述的方法实际上是exponential moving average的特例。这种方法的优点在于可以递归计算，这意味着您只需要为每个对象存储一个流行度值，然后可以在事件发生时递归地调整该值。无需记录每个事件。

这个单一的流行度值表示所有过去的事件(在所使用的数据类型的限制内)，但是随着新事件的加入，较旧的事件对指数的影响减小。此算法将适应不同的时间范围，并响应变化的流量。每次发生事件时，都可以使用以下公式计算新的流行度值:
(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) %}

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

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

原始提案

有很多 suggested algorithms可以根据商品的年龄以及商品获得的投票，点击或购买的数量来计算受欢迎程度。但是，我见过的更健壮的方法通常需要过于复杂的计算和多个存储的值，这会使数据库困惑。我一直在考虑一种非常简单的算法，不需要存储任何变量(流行度值本身除外)，并且只需要一个简单的计算即可。这很简单:

p = (p + t) / 2

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

用当前时间戳初始化 p t

用数据库

中所有 p 值的平均值初始化 p

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

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

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

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

如果您希望投票能在不到一秒的时间间隔内稳定流入，那么您将需要使用微秒级的时间戳，例如PHP microtime()函数。否则，将使用标准的UNIX时间戳，例如PHP time()函数。

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

Answer 1

提出的算法是一种很好的方法，并且是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)

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

从而:

对于alpha = 0.9的

，该算法平均平均最后10个值

(对于alpha = 0.99)，该算法平均平均最后100个值

对于alpha = 0.999的

，该算法平均平均最后1000个值

等