许多网站提供一些统计数据，比如“过去24小时最热门的话题”。例如，Topix.com在它的“新闻趋势”栏目中展示了这一点。在那里，你可以看到提及数量增长最快的话题。
我也想计算一个话题的“热度”。我该怎么做呢？算法应该减小总是热门的话题的权重。通常（几乎）没有人提及的话题应该是最热门的。
谷歌提供“热门趋势”，topix.com显示“热门话题”，fav.or.it显示“关键词趋势”- 所有这些服务都有一个共同点：它们只向您展示当前异常热门的即将到来的趋势。
像“布兰妮·斯皮尔斯”、“天气”或“帕丽斯·希尔顿”之类的术语不会出现在这些列表中，因为它们总是很热门和频繁。 这篇文章称之为“布兰妮·斯皮尔斯问题”。
我的问题是：你如何编写一个算法或使用现有的算法来解决这个问题？有了过去24小时搜索关键字列表，算法应该向你展示最热门的10个（例如）。
我知道，在上面的文章中，有某种算法的提到。 我试着用PHP编写它，但我不认为它会起作用。它只找到了多数派，是吗？
希望您能帮助我（编写示例代码将是很好的）。
z-score = ([current trend] - [average historic trends]) / [standard deviation of historic trends]
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
笔记
You can use this method with a sliding window (i.e. last 30 days) if you wish not to take to much history into account, which will make short term trends more pronounced and can cut down on the processing time.
You could also use a z-score for values such as change in views from one day to next day to locate the abnormal values for increasing/decreasing views per day. This is like using the slope or derivative of the views per day graph.
If you keep track of the current size of the population, the current total of the population, and the current total of x^2 of the population, you don't need to recalculate these values, only update them and hence you only need to keep these values for the history, not each data value. The following code demonstrates this.
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()
Using this method your work flow would be as follows. For each topic, tag, or page create a floating point field, for the total number of days, sum of views, and sum of views squared in your database. If you have historic data, initialize these fields using that data, otherwise initialize to zero. At the end of each day, calculate the z-score using the day's number of views against the historic data stored in the three database fields. The topics, tags, or pages, with the highest X z-scores are your X "hotest trends" of the day. Finally update each of the 3 fields with the day's value and repeat the process next day.
新增内容
如上所述，普通的z分数不考虑数据的顺序，因此对于序列[1, 1, 1, 1, 9, 9, 9, 9]中的观察值'1'或'9'，其z分数具有相同的大小。显然，在趋势发现中，最新的数据应该比旧的数据更有权重，因此我们希望'1'观察值具有比'9'观察值更大的幅度得分。为了实现这一点，我提出了一个浮动平均z分数。显然，这种方法并不能保证在统计学上是可靠的，但应该对趋势发现或类似问题有用。标准z分数和浮动平均z分数之间的主要区别在于使用浮动平均来计算平均人口值和平均人口值的平方。详见代码：
代码
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()
样例输入输出
>>> 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所指出的那样，如果给定一系列常数值，然后请求一个与其他值不同的观测值的z分数，则结果应该是非零值。事实上，返回的值应该是无穷大。因此我更改了这一行：
if self.std() == 0: return 0
至：
if self.std() == 0: return (obs - self.avg) * float("infinity")
if self.std() == 0: return obs - self.avg
Chad Birch 和 Adam Davis 是正确的，你需要向后查看以建立一个基准。从你的问题中可以看出，你只想查看过去 24 小时的数据，这样是不太可行的。
一种不必查询大量历史数据就能让你的数据有记忆的方法是使用指数移动平均。其优点是你可以每个时间段更新一次，然后清除所有旧数据，因此你只需要记住一个值。例如如果你的时间段是一天，那么你需要为每个主题维护一个“每日平均”属性，你可以通过以下方式实现：
a_n = a_(n-1)*b + c_n*(1-b)
当天数为n时，a_n为移动平均值，c_n是在第n天的点击次数，b是介于0和1之间的某个常数（越接近1，记忆时间越长）。这种方法的优点在于，在第n天结束时执行此更新后，可以清除c_n和a_(n-1)。
唯一的限制是它最初对您选择的a的初始值敏感。
编辑
如果希望可视化该方法，请取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相对较小，则会在原始输入上留下相当数量的权重。
如果你研究以上公式，你应该意识到其中一些用法：
我觉得前两个特性正是你正在寻找的。为了给你一个简单的实现的想法，这里有一个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
我想知道在这种情况下是否有可能使用普通的物理加速度公式？
v2-v1/t or dv/dt
v1，需要非常高的v2才能被认为是“趋势”。然而，可能有更好和更复杂的公式和算法来实现这一点。尽管如此，这是一个基本的工作示例。 - caw可能一个简单的主题频率渐变就可以起到作用——大的正渐变=快速增长的受欢迎程度。
最简单的方法是将每天的搜索次数分组，这样你就有了类似于：
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则不是。或者采用更复杂的渐变方式，考虑超过一天到下一天的趋势。
b/a而不是b-a，因为即使热门话题有微小的变化，也会导致巨大的绝对差异。 - DollarAkshay您可以使用对数似然比来比较当前日期与上个月或去年的数据。这在统计学上是合理的（假设您的事件不是正态分布的，这是从您的问题中可以推断出来的）。
只需按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就足够了。当然，在上面的示例中，您将创建一个包含今天所有查询的文档，以及一个包含去年所有查询的文档。