许多网站提供一些统计数据,如“过去24小时内最热门的话题”。例如,Topix.com在其“新闻趋势”部分显示了这一点。在那里,你可以看到被提及次数增长最快的话题。

我也想为一个主题计算这样的“嗡嗡声”。我怎么能这样做呢?算法应该对热点较少的话题进行加权。通常(几乎)没有人提及的话题应该是最热门的话题。

谷歌提供“热门趋势”,topix.com显示“热门话题”,fav.or.it显示“关键字趋势”——所有这些服务都有一个共同点:他们只向你展示当前异常热门的即将到来的趋势。

像“布兰妮·斯皮尔斯”、“天气”或“帕丽斯·希尔顿”这样的词不会出现在这些榜单中,因为它们总是热门且频繁。这篇文章称之为“小甜甜布兰妮问题”。

我的问题是:如何编写算法或使用现有算法来解决这个问题?有一个在过去24小时内搜索的关键字列表,算法应该向您显示10个(例如)最热门的关键字。

我知道,在上面的文章中,提到了某种算法。我试着在PHP中编码,但我不认为它会工作。它只是找到了大多数人,不是吗?

我希望你能帮助我(代码示例将是伟大的)。


当前回答

我想知道在这种情况下是否有可能使用常规的物理加速度公式?

v2-v1/t or dv/dt

我们可以认为v1是每小时的初始点赞/投票/评论数,v2是过去24小时内每小时的当前“速度”?

这更像是一个问题,而不是一个答案,但似乎它可能会起作用。任何加速最快的内容都将成为热门话题……

我相信这并不能解决布兰妮的问题:-)

其他回答

也许一个简单的话题频率梯度就能起作用——大的正梯度=快速增长的受欢迎程度。

最简单的方法是将每天的搜索次数归位,这样你就有了

searches = [ 10, 7, 14, 8, 9, 12, 55, 104, 100 ]

然后看看它每天有多少变化:

hot_factor = [ b-a for a, b in zip(searches[:-1], searches[1:]) ]
# hot_factor is [ -3, 7, -6, 1, 3, 43, 49, -4 ]

只要应用某种阈值,那么那些增加了> 50的日子就被认为是“热”的。如果你愿意,你也可以让它变得更复杂。不是绝对差异,而是相对差异,所以从100到150被认为是热的,但从1000到1050不是。或者是考虑到不止一天的趋势的更复杂的梯度。

通常情况下,“嗡嗡声”是通过某种形式的指数/对数衰减机制计算出来的。有关Hacker News、Reddit和其他网站如何简单处理这个问题的概述,请参阅这篇文章。

这并没有完全解决总是受欢迎的事情。你要找的似乎是谷歌的“热门趋势”功能。为此,您可以将当前值除以历史值,然后减去低于某个噪声阈值的值。

如果你只是看推文或状态信息来获取你的主题,你会遇到很多噪音。即使你删除了所有的停止词。获得更好的主题候选子集的一种方法是只关注共享URL的推文/消息,并从这些网页的标题中获得关键字。并且确保你也应用了POS标记来获得名词+名词短语。

网页的标题通常更具有描述性,包含描述页面内容的单词。此外,分享网页通常与分享突发新闻相关(例如,如果像迈克尔·杰克逊这样的名人去世了,你会有很多人分享关于他去世的文章)。

我做过实验,只从标题中选取热门关键词,然后在所有状态信息中计算这些关键词的总数,它们确实消除了很多干扰。如果你这样做,你不需要一个复杂的算法,只是做一个简单的关键字频率排序,你已经完成了一半。

查德·伯奇和亚当·戴维斯的观点是正确的,你必须回顾过去,建立一个基线。你的问题,从措辞上看,表明你只想查看过去24小时的数据,这并不完全正确。

为数据提供一些内存而不必查询大量历史数据的一种方法是使用指数移动平均。这样做的好处是,您可以每个周期更新一次,然后刷新所有旧数据,因此您只需要记住一个值。所以如果你的周期是一天,你必须为每个主题维护一个“每日平均”属性,你可以通过:

a_n = a_(n-1)*b + c_n*(1-b)

其中a_n是第n天的移动平均值,b是0到1之间的某个常数(越接近1,内存越长),c_n是第n天的点击次数。美妙的是,如果你在第n天结束时执行更新,你可以刷新c_n和a_(n-1)。

需要注意的是,初始时它对a的初始值很敏感。

EDIT

如果这有助于可视化这个方法,取n = 5, a_0 = 1, b = .9。

假设新的值是5,0,0,1,4:

a_0 = 1
c_1 = 5 : a_1 = .9*1 + .1*5 = 1.4
c_2 = 0 : a_2 = .9*1.4 + .1*0 = 1.26
c_3 = 0 : a_3 = .9*1.26 + .1*0 = 1.134
c_4 = 1 : a_4 = .9*1.134 + .1*1 = 1.1206
c_5 = 4 : a_5 = .9*1.1206 + .1*5 = 1.40854

看起来不太像平均值,不是吗?请注意,即使我们的下一个输入是5,该值仍然接近1。这是怎么呢如果你展开计算,你会得到:

a_n = (1-b)*c_n + (1-b)*b*c_(n-1) + (1-b)*b^2*c_(n-2) + ... + (leftover weight)*a_0

我说的剩余重量是什么意思?在任何平均值中,所有的权重都必须加为1。如果n是无穷大,那么。可以一直延续下去,那么所有权值的和都是1。但如果n相对较小,原始输入就会有相当大的权重。

如果你研究了上面的公式,你应该意识到关于这个用法的一些事情:

所有数据永远都对平均值有所贡献。实际上,有一个点的贡献是非常非常小的。 最近的值比旧值贡献更大。 b越高,新值越不重要,旧值越重要。然而,b越高,就需要越多的数据来冲淡a的初值。

我认为前两个特点正是你要找的。为了给你一个简单的想法,这是一个python实现(减去所有的数据库交互):

>>> class EMA(object):
...  def __init__(self, base, decay):
...   self.val = base
...   self.decay = decay
...   print self.val
...  def update(self, value):
...   self.val = self.val*self.decay + (1-self.decay)*value
...   print self.val
... 
>>> a = EMA(1, .9)
1
>>> a.update(10)
1.9
>>> a.update(10)
2.71
>>> a.update(10)
3.439
>>> a.update(10)
4.0951
>>> a.update(10)
4.68559
>>> a.update(10)
5.217031
>>> a.update(10)
5.6953279
>>> a.update(10)
6.12579511
>>> a.update(10)
6.513215599
>>> a.update(10)
6.8618940391
>>> a.update(10)
7.17570463519

您可以使用对数概率比来比较当前日期与上个月或去年。这在统计上是合理的(假设你的事件不是正态分布,这是从你的问题中假设的)。

只需按logLR排序所有的术语,并选择前10名。

public static void main(String... args) {
    TermBag today = ...
    TermBag lastYear = ...
    for (String each: today.allTerms()) {
        System.out.println(logLikelihoodRatio(today, lastYear, each) + "\t" + each);
    }
} 

public static double logLikelihoodRatio(TermBag t1, TermBag t2, String term) {
    double k1 = t1.occurrences(term); 
    double k2 = t2.occurrences(term); 
    double n1 = t1.size(); 
    double n2 = t2.size(); 
    double p1 = k1 / n1;
    double p2 = k2 / n2;
    double p = (k1 + k2) / (n1 + n2);
    double logLR = 2*(logL(p1,k1,n1) + logL(p2,k2,n2) - logL(p,k1,n1) - logL(p,k2,n2));
    if (p1 < p2) logLR *= -1;
    return logLR;
}

private static double logL(double p, double k, double n) {
    return (k == 0 ? 0 : k * Math.log(p)) + ((n - k) == 0 ? 0 : (n - k) * Math.log(1 - p));
}

PS, TermBag是单词的无序集合。为每个文档创建一袋术语。数一下单词的出现次数。然后,occurrences方法返回给定单词的出现次数,size方法返回单词的总数。最好以某种方式规范化单词,通常toLowerCase就足够了。当然,在上面的示例中,您将创建一个包含当前所有查询的文档,以及一个包含去年所有查询的文档。