1

用户在时间t访问我的网站，他们可能会或可能不会点击我关心的特定链接，如果他们这样做，我会记录他们点击该链接的事实，以及自t以来他们点击该链接的持续时间，称之为d .

我需要一个允许我创建这样的类的算法：

class ClickProbabilityEstimate {
    public void reportImpression(long id);
    public void reportClick(long id);

    public double estimateClickProbability(long id);
}

每个展示都有一个唯一的id，在报告点击时使用它来指示点击属于哪个展示。

我需要一种算法，该算法将根据自报告印象以来已经过去多少时间返回一个概率，即该印象将获得一次点击，具体取决于之前的点击所需的时间。很明显，如果仍然没有点击，那么这个概率会随着时间的推移而降低。

如有必要，我们可以设置一个上限，超过该上限我们认为点击概率为 0（例如，如果距离展示发生一小时，我们可以很确定不会有点击）。

该算法应该在空间和时间上都有效，并希望尽可能少地做出假设，同时保持优雅。易于实施也很好。有任何想法吗？

4

2 回答 2

2

假设您保留有关过去展示次数和点击次数的数据，这很容易：假设您有一次展示，并且距离该展示已经过去了d'时间。您可以将数据分为三组：

  1. 在不到d'内获得点击的展示次数
  2. 超过d'后获得点击的展示次数
  3. 从未获得点击的展示次数

显然，当前印象不在组 (1) 中，因此消除它。你想要它在组（2）中的概率，然后

P = N2 / (N2 + N3)

其中N2是第 2 组中的展示次数，对于N3.

就实际实现而言，我的第一个想法是保留一个有序的列表，其中包含确实收到点击的过去印象的时间d以及从未收到点击的印象数的计数，然后只进行二分搜索d'在该列表中。你找到的位置会给你N1，然后N2是列表的长度减去N1。

如果您不需要完美的粒度，您可以将过去的时间存储为直方图，即在每个元素中包含list[n]至少n但少于n+1几分钟后收到点击的展示次数的列表。（或秒，或任何您喜欢的时间间隔）在这种情况下，您可能希望将总点击次数保留为单独的变量，以便轻松计算N2.

（顺便说一下，这是我自己编的，不知道有没有针对这种事情的标准算法可能会更好）

于 2010-05-03T18:35:44.707 回答
0

我建议假设一个到达过程（每分钟点击次数）并尝试使用您现有的数据将分布拟合到该到达过程。我敢打赌，结果是负二项式，如果均值具有伽马分布，则当您具有具有非平稳均值的泊松到达过程时，您会得到。倒数（每次点击的分钟数）为您提供到达间隔过程的分布。不知道是否有为此命名的分布，但您可以创建一个经验分布。

希望这可以帮助。

于 2010-05-04T21:50:27.017 回答