Instagram的热门趋势发现算法_语言 & 开发_谢丽

Python 还能承担下一个时代的发展重任吗？Mojo 语言的横空出世对 AI 研发生态有什么影响？了解详情 



 写点什么

不久前，照片分享应用 Instagram 推出了搜索与浏览功能。浏览页面上的热门标签和地点是社区中一些最受欢迎的内容，而其背后是一个每天可以解析 7000 多万张新增图片的系统。近日，Instagram 技术博客介绍了支撑该系统的热门趋势发现算法。

直观地讲，热门标签是一个比平时用得多的标签，而这种情况是由那个时刻发生的特定事件所导致。比如，在 Instagram 撰写那篇博文时，#equality 就是一个热门标签，即当时有许多人用它分享图片：

趋势识别

通过标签热度变化可以识别趋势。Instagram 认为，一个良好的趋势要具备三个要素：

流行度——社区中要有许多人对该趋势感兴趣
新颖性——该趋势是关于一些新东西
时效性——该趋势是在真实事件发生时出现在 Instagram 上的

识别趋势需要量化当前观察到的活动（分享照片和视频的数量）与预期活动的差异。如果前者高于后者，就可以确定某个趋势。比如上文提到的标签#equality，通常每个小时只有几张照片及视频用到它。但从太平洋时间上午 7 点开始，有数以千计的人用它分享内容。就是说，活动多于预期，标签#equality 代表一种趋势。

对于每个标签和地点，他们会记录过去七天中每五分钟内有多少媒质在分享时用到了它，该数量表示为C(h, t)，即标签 h 在时间点 t 的计数（也就是，在 t-5 到 t 时段里以 h 作为标签的帖子数量）。由于该计数在不同的标签或不同的时点之间差别很大，所以将其规范化为在时点 t 观察到 h 的概率P(h, t)。此外，他们还构建了一个模型，用于计算预期数量C’(h, t)，并得出预期概率P’(h, t)。现在，就可以使用一种常见的概率差异度量方法“KL 散度（ KL divergence ）”计算实际概率与预期概率的差异，公式如下：

复制代码

 S(h, t) = P(h, t) * ln(P(h, t)/P’(h, t))

其中，P(h, t)可以体现流行度，P(h, t)/P’(h, t)可以体现新颖性，而 t 则体现出时效性。

趋势预测

预测是指根据过去的观察计算预期基准概率。在这个过程中，需要权衡准确性与计算的时空复杂度。通常，准确性会与时空复杂度呈一定的正比关系。他们测试了不同的可选方案，包括取上周同一时间的计数、回归模型、神经网络。最终，他们选择使用上周测量值中的最大概率，这有如下好处：

容易计算，内存需求相对较低
可以抑制具有高方差的非趋势
可以快速识别新兴的趋势

这里有两点需要说明一下。一是，由于大多数标签在五分钟内的计数都非常小，甚至为 0，所以他们在计算旧的计数时以小时为单位，而且他们会查看几个小时的数据，以最小化随机使用高峰的干扰。二是，如果某个标签过去没有出现过，那么他们会将该标签在那个时间窗口内的计数置为 3，依据是大多数标签在一个小时出现次数都不超过 3。

趋势排列

这一步是根据 KL 散度值S(h, t)排列标签。他们发现，部分趋势消失地很快，但实际上仍然有人对其感兴趣。为了解决这个问题，他们引入了指数衰减函数，用它定义趋势的生存期。 S(h, tmax)=SM(h)表示标签 h 在时点 tmax 时取得最大 KL 散度值，则其指数衰减值为：

复制代码

 Sd(h, t) = SM(h) * (½)^((t - tmax)/half-life)

其中，衰减参数“半衰期（half-life）”为 2 小时，是指SM(h)每过两个小时就会减半。

趋势聚合

通常，人们会用多个标签描述同一事件，当一个事件热门时，描述该事件的多个标签都会成为趋势。因此，需要将这些概念上相同的标签聚合成一个趋势。这有两个方面的工作：一是识别出谈论同一事件的标签，二是找出最能代表该事件的标签。对于第一项，他们通过以下维度计算标签相似度：

共现率——在最近的媒质中，一个标签同其它标签一起出现的次数。
编辑距离——同一标签的不同拼写（或错别字），通过 Levenshtein 距离来计算。
主题分布——描述同一事件、但拼写不同（如#gocavs、#gowarriors）的标签不大可能一起出现。他们将标题中的标签通过一个内部工具分类到一组预定义的主题中。然后计算每个标签的主题分布，并使用 TF-IDF 将其标准化。

趋势聚合过程即是根据每一对趋势标签的相似度将它们分组。

系统设计

他们将趋势发现后台设计成一个有四个节点的流处理应用程序，如下图所示：