206

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

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

Google 提供“Hot Trends”,topix.com 显示“Hot Topics”,fav.or.it 显示“Keyword Trends”——所有这些服务都有一个共同点:它们只向您展示当前异常热门的即将到来的趋势。

诸如“Britney Spears”、“weather”或“Paris Hilton”之类的词不会出现在这些列表中,因为它们总是热门且频繁出现。这篇文章称之为“布兰妮斯皮尔斯问题”。

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

我知道,在上面的文章中,提到了某种算法。我试图用 PHP 对其进行编码,但我认为它不会起作用。它只是找到大多数,不是吗?

我希望你能帮助我(编码示例会很棒)。

4

11 回答 11

114

这个问题需要一个 z 分数或标准分数,它会考虑到历史平均值,正如其他人提到的那样,还要考虑这个历史数据的标准偏差,使其比仅使用平均值更稳健。

在您的情况下,z 分数是通过以下公式计算的,其中趋势将是诸如观看次数/天之类的比率。

z-score = ([current trend] - [average historic trends]) / [standard deviation of historic trends]

当使用z-score时,z-score越高或越低,趋势越异常,例如,如果z-score为高正则趋势异常上升,而如果z-score为高负则异常下降. 因此,一旦您计算了所有候选趋势的 z 分数,最高的 10 个 z 分数将与最异常增加的 z 分数相关。

有关 z 分数的更多信息,请参阅Wikipedia

代码

from math import sqrt

def zscore(obs, pop):
    # Size of population.
    number = float(len(pop))
    # Average population value.
    avg = sum(pop) / number
    # Standard deviation of population.
    std = sqrt(sum(((c - avg) ** 2) for c in pop) / number)
    # Zscore Calculation.
    return (obs - avg) / std

样本输出

>>> zscore(12, [2, 4, 4, 4, 5, 5, 7, 9])
3.5
>>> zscore(20, [21, 22, 19, 18, 17, 22, 20, 20])
0.0739221270955
>>> zscore(20, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1])
1.00303599234
>>> zscore(2, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1])
-0.922793112954
>>> zscore(9, [1, 2, 0, 3, 1, 3, 1, 2, 9, 8, 7, 10, 9, 5, 2, 4, 1, 1, 0])
1.65291949506

笔记

  • 如果您不想考虑太多历史记录,您可以将此方法与滑动窗口(即过去 30 天)一起使用,这将使短期趋势更加明显,并可以减少处理时间。

  • 您还可以使用 z 分数来表示从一天到第二天的观看次数变化等值,以定位每天增加/减少观看次数的异常值。这就像使用每日视图的斜率或导数一样。

  • 如果您跟踪人口的当前规模、人口的当前总数以及人口的当前总数 x^2,则无需重新计算这些值,只需更新它们,因此您只需将这些值保留为历史记录,而不是每个数据值。下面的代码演示了这一点。

      from math import sqrt
    
      class zscore:
          def __init__(self, pop = []):
              self.number = float(len(pop))
              self.total = sum(pop)
              self.sqrTotal = sum(x ** 2 for x in pop)
          def update(self, value):
              self.number += 1.0
              self.total += value
              self.sqrTotal += value ** 2
          def avg(self):
              return self.total / self.number
          def std(self):
              return sqrt((self.sqrTotal / self.number) - self.avg() ** 2)
          def score(self, obs):
              return (obs - self.avg()) / self.std()
    
  • 使用这种方法,您的工作流程将如下所示。为每个主题、标签或页面创建一个浮点字段,用于显示数据库中的总天数、查看次数总和以及查看次数平方和。如果您有历史数据,请使用该数据初始化这些字段,否则初始化为零。在每天结束时,使用当天的查看次数与存储在三个数据库字段中的历史数据计算 z 分数。具有最高 X z 分数的主题、标签或页面是您当天的 X 个“最热门趋势”。最后用当天的值更新 3 个字段中的每一个,并在第二天重复该过程。

新增内容

上面讨论的正常 z 分数不考虑数据的顺序,因此观察“1”或“9”的 z 分数与序列 [1, 1, 1, 1 , 9, 9, 9, 9]。显然,对于趋势发现,最新数据应该比旧数据具有更大的权重,因此我们希望“1”观察值比“9”观察值具有更大的量值分数。为了实现这一点,我提出了一个浮动平均 z 分数。应该清楚的是,这种方法不能保证在统计上是合理的,但应该对趋势发现或类似方法有用。标准 z-score 和浮动平均 z-score 的主要区别在于使用浮动平均数来计算平均人口值和平均人口值的平方。详情见代码:

代码

class fazscore:
    def __init__(self, decay, pop = []):
        self.sqrAvg = self.avg = 0
        # The rate at which the historic data's effect will diminish.
        self.decay = decay
        for x in pop: self.update(x)
    def update(self, value):
        # Set initial averages to the first value in the sequence.
        if self.avg == 0 and self.sqrAvg == 0:
            self.avg = float(value)
            self.sqrAvg = float((value ** 2))
        # Calculate the average of the rest of the values using a 
        # floating average.
        else:
            self.avg = self.avg * self.decay + value * (1 - self.decay)
            self.sqrAvg = self.sqrAvg * self.decay + (value ** 2) * (1 - self.decay)
        return self
    def std(self):
        # Somewhat ad-hoc standard deviation calculation.
        return sqrt(self.sqrAvg - self.avg ** 2)
    def score(self, obs):
        if self.std() == 0: return (obs - self.avg) * float("infinity")
        else: return (obs - self.avg) / self.std()

示例 IO

>>> fazscore(0.8, [1, 1, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9]).score(1)
-1.67770595327
>>> fazscore(0.8, [1, 1, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9]).score(9)
0.596052006642
>>> fazscore(0.9, [2, 4, 4, 4, 5, 5, 7, 9]).score(12)
3.46442230724
>>> fazscore(0.9, [2, 4, 4, 4, 5, 5, 7, 9]).score(22)
7.7773245459
>>> fazscore(0.9, [21, 22, 19, 18, 17, 22, 20, 20]).score(20)
-0.24633160155
>>> fazscore(0.9, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1]).score(20)
1.1069362749
>>> fazscore(0.9, [21, 22, 19, 18, 17, 22, 20, 20, 1, 2, 3, 1, 2, 1, 0, 1]).score(2)
-0.786764452966
>>> fazscore(0.9, [1, 2, 0, 3, 1, 3, 1, 2, 9, 8, 7, 10, 9, 5, 2, 4, 1, 1, 0]).score(9)
1.82262469243
>>> fazscore(0.8, [40] * 200).score(1)
-inf

更新

正如 David Kemp 正确指出的那样,如果给定一系列常数值,然后请求与其他值不同的观察值的 zscore,则结果可能应该是非零的。实际上返回的值应该是无穷大。所以我改变了这条线,

if self.std() == 0: return 0

至:

if self.std() == 0: return (obs - self.avg) * float("infinity")

此更改反映在 fazscore 解决方案代码中。如果不想处理无限值,则可接受的解决方案是将行改为:

if self.std() == 0: return obs - self.avg
于 2009-05-05T19:22:20.503 回答
93

你需要一个算法来衡量一个话题的速度——或者换句话说,如果你用图表来展示那些以惊人的速度上升的话题。

这是趋势线的一阶导数,不难作为整体计算的加权因子。

标准化

您需要做的一项技术是规范化所有数据。对于您关注的每个主题,保留一个定义该主题基线的低通滤波器。现在,关于该主题的每个数据点都应该被标准化 - 减去它的基线,你会得到所有主题接近 0,在线上方和下方都有峰值。相反,您可能希望将信号除以其基线幅度,这将使信号达到 1.0 左右 - 这不仅使所有信号彼此一致(使基线标准化),而且使尖峰标准化。布兰妮的尖峰将比其他人的尖峰大几个数量级,但这并不意味着你应该注意它 - 相对于她的基线,尖峰可能非常小。

派生

将所有内容标准化后,找出每个主题的斜率。取两个连续的点,并测量差异。正差呈上升趋势,负差呈下降趋势。然后,您可以比较归一化的差异,并找出与其他主题相比,哪些主题的受欢迎程度正在上升——每个主题都根据自己的“正常”进行缩放,这可能与其他主题的数量级不同。

这确实是解决问题的第一步。您需要使用更高级的技术(主要是上述技术与其他算法的组合,加权以满足您的需求),但这应该足以让您入门。

关于文章

这篇文章是关于话题趋势的,但不是关于如何计算什么是热门和什么不是,而是关于如何处理这种算法必须在 Lycos 和 Google 等地方处理的大量信息。为每个主题提供一个计数器所需的空间和时间,并在对其进行搜索时找到每个主题的计数器是巨大的。本文是关于尝试此类任务时面临的挑战。它确实提到了布兰妮效应,但没有谈到如何克服它。

正如Nixuz 指出的那样,这也称为 Z 或标准分数

于 2009-05-05T18:45:42.480 回答
18

Chad Birch 和 Adam Davis 是正确的,因为你必须向后看才能建立基线。如您所说,您的问题表明您只想查看过去 24 小时内的数据,而这并不完全可行。

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

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

哪里a_n是当天的移动平均n线,b 是介于 0 和 1 之间的某个常数(越接近 1,内存越长)并且c_n是当天的点击次数n。美妙之处在于,如果您在一天结束时执行此更新n,您可以刷新c_na_(n-1).

需要注意的是,它最初会对您选择的初始值敏感a

编辑

如果它有助于可视化这种方法,请采用n = 5a_0 = 1b = .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

看起来不是很像平均水平吗?请注意该值如何保持接近 1,即使我们的下一个输入是 5。发生了什么?如果你扩展数学,你会得到什么:

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 相对较小,则剩下的权重很大在原始输入上。

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

  1. 所有数据都永远对平均值有所贡献。实际上,有一点贡献是非常非常小的。
  2. 最近的价值观比旧价值观的贡献更大。
  3. 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
于 2009-05-05T19:34:51.830 回答
9

通常使用某种形式的指数/对数衰减机制来计算“嗡嗡声”。有关 Hacker News、Reddit 和其他人如何以简单的方式处理此问题的概述,请参阅这篇文章

这并没有完全解决总是流行的事情。您正在寻找的内容似乎类似于 Google 的“热门趋势”功能。为此,您可以将当前值除以历史值,然后减去低于某个噪声阈值的值。

于 2009-04-30T13:28:17.417 回答
8

我认为他们需要注意的关键词是“异常”。为了确定什么时候“异常”,你必须知道什么是正常的。也就是说,您将需要历史数据,您可以对其进行平均以找出特定查询的正常速率。您可能希望从平均计算中排除异常天数,但这需要已经有足够的数据,以便您知道要排除哪些天数。

从那里开始,您必须设置一个阈值(我敢肯定,这需要进行实验),如果超出阈值,例如比正常搜索次数多 50%,您可以将其视为“趋势”。或者,如果您希望能够像您提到的那样找到“Top X Trendiest”,您只需要按照它们与正常价格相差多远(按百分比)排序即可。

例如,假设您的历史数据告诉您,布兰妮斯皮尔斯通常会获得 100,000 次搜索,而帕丽斯·希尔顿通常会获得 50,000 次搜索。如果有一天他们俩的搜索量都比平时多 10,000 次,那么您应该认为巴黎比布兰妮“更热”,因为她的搜索量比平时增加了 20%,而布兰妮的搜索量仅增加了 10%。

天哪,我简直不敢相信我刚刚写了一段比较布兰妮斯皮尔斯和帕丽斯希尔顿的“辣度”。你对我做了什么?

于 2009-05-05T18:49:02.110 回答
7

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

v2-v1/t or dv/dt

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

这更像是一个问题而不是一个答案,但似乎它可能只是工作。任何具有最高加速度的内容都将成为热门话题……

我相信这可能无法解决布兰妮斯皮尔斯的问题:-)

于 2013-05-27T04:48:28.830 回答
5

可能一个简单的主题频率梯度会起作用——大的正梯度=受欢迎程度迅速增长。

最简单的方法是对每天搜索的数量进行分类,所以你有类似的东西

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 不是。或更复杂的梯度,它考虑了不止一天到下一天的趋势。

于 2009-04-24T20:41:56.957 回答
4

我曾参与过一个项目,我的目标是从实时 Twitter 流中找到热门话题,并对热门话题进行情感分析(找出热门话题是否正面/负面谈论)。我使用 Storm 来处理 Twitter 流。

我已将我的报告发布为博客:http ://sayrohan.blogspot.com/2013/06/finding-trending-topics-and-trending.html

我使用 Total Count 和 Z-Score 进行排名。

我使用的方法有点通用,在讨论部分中,我提到了我们如何为非 Twitter 应用程序扩展系统。

希望信息有所帮助。

于 2013-06-06T03:52:16.683 回答
3

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

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

我进行了实验,我只从标题中获取热门关键字,然后在所有状态消息中获取这些关键字的总数,它们肯定会消除很多噪音。如果你这样做,你不需要复杂的算法,只需对关键字频率进行简单的排序,你就成功了。

于 2013-08-14T01:39:17.280 回答
2

您可以使用 log-likelihood-ratio 将当前日期与上个月或上一年进行比较。这在统计上是合理的(鉴于您的事件不是正态分布的,这是从您的问题中假设的)。

只需按 logLR 对所有术语进行排序,然后选择前十名。

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就足够了。当然,在上面的示例中,您将创建一个包含今天所有查询的文档,以及一个包含去年所有查询的文档。

于 2009-05-04T19:03:04.643 回答
0

这个想法是跟踪这些事情,并在它们与自己的基线相比显着跳跃时注意。

因此,对于超过某个阈值的查询,跟踪每个查询,当它变为其历史值的某个值(例如几乎翻倍)时,这是一个新的热门趋势。

于 2009-05-05T18:45:40.327 回答