caw*_*caw 173 tags algorithm information-retrieval
许多网站都提供了一些统计数据,例如"过去24小时内最热门的话题".例如,Topix.com在其"新闻趋势"部分中显示了这一点.在那里,您可以看到增长最多的主题.
我也想为一个主题计算这样一个"嗡嗡声".我怎么能这样做？该算法应该对总是少热的主题进行加权.通常(几乎)没有人提到的主题应该是最热门的主题.
Google提供"热门趋势",topix.com显示"热门话题",fav.or.it显示"关键字趋势" - 所有这些服务都有一个共同点:它们只显示即将出现的异常热门趋势.
像"布兰妮斯皮尔斯","天气"或"帕丽斯·希尔顿"这样的词语不会出现在这些列表中,因为它们总是热门而且频繁.这篇文章称之为"布兰妮斯皮尔斯问题".
我的问题:如何编写算法代码或使用现有算法来解决此问题？如果列表中包含在过去24小时内搜索到的关键字,则该算法应显示10个(例如)最热门的关键字.
我知道,在上面的文章中,提到了某种算法.我试图用PHP编写它,但我认为它不会起作用.它只是找到了大多数,不是吗？
我希望你能帮助我(编码例子会很棒).
Nix*_*xuz 96
这个问题需要一个z分数或标准分数,这将考虑到其他人提到的历史平均值,但也考虑了这些历史数据的标准差,使其比仅使用平均值更加稳健.
在您的情况下,z分数通过以下公式计算,其中趋势将是诸如视图/日之类的速率.
z-score = ([current trend] - [average historic trends]) / [standard deviation of historic trends]
当使用z分数时,z分数越高或越低,趋势越异常,因此例如如果z分数高度正,那么趋势异常上升,而如果它是高度负数则异常下降.因此,一旦计算出所有候选趋势的z得分,最高的10个z得分将与最不正常增加的z得分相关.
有关z分数的更多信息,请参阅维基百科.
码
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得分和浮动平均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()
样本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
Ada*_*vis 93
您需要一种测量主题速度的算法 - 或者换句话说,如果您绘制图形,则需要以令人难以置信的速率显示那些正在上升的那些.
这是趋势线的第一个导数,并不难将其作为整体计算的加权因子.
规范化
您需要做的一项技术是规范化所有数据.对于您正在关注的每个主题,请保留一个定义该主题基线的非常低通过滤镜.现在,关于该主题的每个数据点都应该被标准化 - 减去它的基线,你将使你的所有主题都接近0,并且线上方和下方都有尖峰.您可能希望将信号除以其基线幅度,这将使信号达到1.0左右 - 这不仅使所有信号彼此一致(使基线标准化),而且还使峰值标准化.英国穗状花序的大小将比其他人的穗状花序大,但这并不意味着你应该注意它 - 相对于她的基线,穗可能非常小.
派生
一旦你对所有内容进行了标准化,找出每个主题的斜率.连续两个点,并衡量差异.正差异呈上升趋势,负差异呈下降趋势.然后,您可以比较规范化的差异,并找出哪些主题与其他主题相比在人气上上升 - 每个主题都适合其自身的"正常",这可能是与其他主题不同的顺序.
这真是问题的第一步.您需要使用更多高级技术(主要是上述与其他算法的组合,加权以满足您的需求),但它应该足以让您入门.
关于这篇文章
这篇文章是关于主题趋势的,但它不是关于如何计算什么是热点,什么不是,它是关于如何处理这样的算法必须在Lycos和谷歌这样的地方处理的大量信息.为每个主题提供一个计数器所需的空间和时间,并在搜索每个主题的计数器时查找每个主题的计数器是巨大的.本文是关于尝试此类任务时遇到的挑战.它确实提到了布兰妮效应,但它没有谈论如何克服它.
正如Nixuz指出的那样,这也被称为Z或标准分数.
Dav*_*ger 17
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_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是过去24小时内每小时的当前"速度"？
这更像是一个问题,而不是一个答案,但似乎它可能只是起作用.任何加速度最高的内容都将成为热门话题......
我相信这可能无法解决布兰妮斯皮尔斯问题:-)
我认为他们需要注意的关键词是"异常".为了确定什么时候出现"异常",你必须知道什么是正常的.也就是说,您将需要历史数据,您可以对其进行平均以找出特定查询的正常速率.您可能希望从平均计算中排除异常天数,但同样需要具有足够的数据,以便您知道要排除的天数.
从那里,你必须设置一个阈值(这需要实验,我敢肯定),如果某些事情超出阈值,比起正常情况下搜索量增加50%,你可以认为它是一个"趋势".或者,如果您希望能够找到您提到的"Top X Trendiest",那么您只需要按照他们的正常速度离开(百分比)的顺序.
例如,假设您的历史数据告诉您Britney Spears通常会获得100,000次搜索,而Paris Hilton通常会获得50,000次搜索.如果你有一天他们的搜索量比正常情况多10,000,你应该考虑巴黎比布兰妮"更热",因为她的搜索量比正常情况增加了20%,而布兰妮只有10%.
上帝,我简直不敢相信我刚刚写了一段比较布兰妮斯皮尔斯和帕丽斯希尔顿的"热情".你对我做了什么？
一个简单的主题频率梯度可能会起作用-大的正梯度=迅速普及。
最简单的方法是对每天的搜索量进行分类，因此
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则不会。或者更复杂的渐变，其中要考虑到一天到第二天之间的趋势。
| 归档时间： |
|
| 查看次数： |
53220 次 |
| 最近记录： |