模型的训练上，头条系大部分推荐产品采用实时训练。实时训练省资源并且反馈快，这对信息流产品非常重要。用户需要行为信息可以被模型快速捕捉并反馈至下一刷的推荐效果。我们线上目前基于storm集群实时处理样本数据，包括点击、展现、收藏、分享等动作类型。模型参数服务器是内部开发的一套高性能的系统，因为头条数据规模增长太快，类似的开源系统稳定性和性能无法满足，而我们自研的系统底层做了很多针对性的优化，提供了完善运维工具，更适配现有的业务场景。
目前，头条的推荐算法模型在世界范围内也是比较大的，包含几百亿原始特征和数十亿向量特征。整体的训练过程是线上服务器记录实时特征，导入到Kafka文件队列中，然后进一步导入Storm集群消费Kafka数据，客户端回传推荐的label构造训练样本，随后根据最新样本进行在线训练更新模型参数，最终线上模型得到更新。这个过程中主要的延迟在用户的动作反馈延时，因为文章推荐后用户不一定马上看，不考虑这部分时间，整个系统是几乎实时的。



今日头条推荐算法原理全文详解 今日头条 数据分析 产品经理 产品 好文分享 第7张
但因为头条目前的内容量非常大，加上小视频内容有千万级别，推荐系统不可能所有内容全部由模型预估。所以需要设计一些召回策略，每次推荐时从海量内容中筛选出千级别的内容库。召回策略最重要的要求是性能要极致，一般超时不能超过50毫秒。



今日头条推荐算法原理全文详解 今日头条 数据分析 产品经理 产品 好文分享 第8张
召回策略种类有很多，我们主要用的是倒排的思路。离线维护一个倒排，这个倒排的key可以是分类，topic，实体，来源等，排序考虑热度、新鲜度、动作等。线上召回可以迅速从倒排中根据用户兴趣标签对内容做截断，高效的从很大的内容库中筛选比较靠谱的一小部分内容。



今日头条推荐算法原理全文详解 今日头条 数据分析 产品经理 产品 好文分享 第9张
二、内容分析
内容分析包括文本分析，图片分析和视频分析。头条一开始主要做资讯，今天我们主要讲一下文本分析。文本分析在推荐系统中一个很重要的作用是用户兴趣建模。没有内容及文本标签，无法得到用户兴趣标签。举个例子，只有知道文章标签是互联网，用户看了互联网标签的文章，才能知道用户有互联网标签，其他关键词也一样。



今日头条推荐算法原理全文详解 今日头条 数据分析 产品经理 产品 好文分享 第10张
另一方面，文本内容的标签可以直接帮助推荐特征，比如魅族的内容可以推荐给关注魅族的用户，这是用户标签的匹配。如果某段时间推荐主频道效果不理想，出现推荐窄化，用户会发现到具体的频道推荐(如科技、体育、娱乐、军事等)中阅读后，再回主feed,推荐效果会更好。因为整个模型是打通的，子频道探索空间较小，更容易满足用户需求。只通过单一信道反馈提高推荐准确率难度会比较大，子频道做的好很重要。而这也需要好的内容分析。



今日头条推荐算法原理全文详解 今日头条 数据分析 产品经理 产品 好文分享 第11张
上图是今日头条的一个实际文本case。可以看到，这篇文章有分类、关键词、topic、实体词等文本特征。当然不是没有文本特征，推荐系统就不能工作，推荐系统最早期应用在Amazon,甚至沃尔玛时代就有，包括Netfilx做视频推荐也没有文本特征直接协同过滤推荐。但对资讯类产品而言，大部分是消费当天内容，没有文本特征新内容冷启动非常困难，协同类特征无法解决文章冷启动问题。

大家好，我是一名内容型产品经理，决定写这系列的文章是因为想记录下在日常工作中遇到的问题和学习到的知识，分享给大家希望可以多多交流。
最近越来越多的产品都有需要用到推荐算法，例如资讯类产品需要为用户在首页信息流推荐内容，社区类产品也需要为用户推荐感兴趣的东西。然而算法有很多种，不过无论怎样，都会需要计算两个物品/内容间的相似度，然后再做进一步处理，本系列文章为大家介绍在实际生产环境中一些常用到的简单推荐算法~
1. 利用余弦定理公式计算物品间的相似度
余弦相似度原理
用向量空间中的两个向量夹角的余弦值作为衡量两个个体间差异大小的度量，值越接近1，就说明夹角角度越接近0°，也就是两个向量越相似
用向量余弦公式简化为：
公式只是次要的哈哈哈哈，最重要的是下面的推导过程，下面为大家逐步逐步剖析公式是怎么推导过来的~
推导过程
向量a，b，夹角为θ：
作辅助线c：
余弦定理求cosθ：
如图，将这个模型放到二维坐标下：
那么构建出来的三角形三条边的边长分别为（勾股定理）：
把a,b,c代入余弦定理公式，计算过程如下：
由于：
所以：
上述公式是在二维坐标中进行推导的，如果拓展到n维坐标，这个公式会写成：
2. 实际运用
现在假设：
A用户喜欢a,b,d
B用户喜欢b,c,e
C用户喜欢c,d
D用户喜欢b,c,d
E用户喜欢a,d
建立物品-用户的倒排表，列出每个物品都被哪些用户喜欢，其中“1”表示喜欢，“2”表示不喜欢。
注意：这里的喜欢行为可以理解成是用户在产品上触发的交互，例如点击，评论，点赞，收藏等。
利用前面说到的余弦定理公式计算两个物品间的相似度
例如：将物品a和b分别看作是多维空间中的两个向量，则有：a（1,0,0,0,1）；b（1,1,0,1,0），所以物品a和物品b的相似度为：
3. 总结
至此，我们已经完成了利用余弦定理公式计算物品间的相似度。不过由于生产环境中的用户量和物品量都肯定不只有5个，当我们的数据量非常庞大时，这种计算方法就会显得非常吃力。所以我们整个推荐系统的架构不可能只由这一个算法构成，还需要诸如离线生成候选集，对候选集进行排序，规则干预，然后进行内容曝光之类的操作，不过这次的内容先到这里了，感兴趣的朋友可以在评论区留言，大家多多交流~

	

 
奇技指南
在海量的信息流中，通过精准的算法给用户推荐其感兴趣的内容，已经成为了一个产品吸引用户，获取收益的极其重要的方式。
本篇为算法系列文章，将为大家分享360的算法团队在实践中积累的算法知识及经验，欢迎大家交流分享~
Louvain算法是一种基于多层次优化Modularity的算法，具有快速、准确的优点，在效率和效果上都表现比较好，并且能够发现层次性的社区结构，被认为是性能最好的社区发现算法之一。
模块度
Louvain算法是一种基于图数据的社区发现算法。
原始论文为：
《Fast unfolding of communities in large networks》。
Louvain算法的优化目标为最大化整个数据的模块度，
模块度的计算如下：
其中m为图中边的总数量，k_i表示所有指向节点i的连边权重之和，k_j同理。A_{i,j} 表示节点i，j之间的连边权重。
有一点要搞清楚，模块度的概念不是Louvain算法发明的，而Louvain算法只是一种优化关系图模块度目标的一种实现而已。
Louvain算法的两步迭代设计
最开始，每个原始节点都看成一个独立的社区，社区内的连边权重为0
  
步骤1
算法扫描数据中的所有节点，针对每个节点遍历该节点的所有邻居节点，衡量把该节点加入其邻居节点所在的社区所带来的模块度的收益。并选择对应最大收益的邻居节点，加入其所在的社区。这一过程化重复进行指导每一个节点的社区归属都不在发生变化。
  
步骤2
对步骤1中形成的社区进行折叠，把每个社区折叠成一个单点，分别计算这些新生成的“社区点”之间的连边权重，以及社区内的所有点之间的连边权重之和。用于下一轮的步骤1。
该算法的最大优势就是速度很快，步骤1的每次迭代的时间复杂度为O(N)，N为输入数据中的边的数量。步骤2 的时间复杂度为O(M + N)， M为本轮迭代中点的个数。
算法实现
数据结构设计
算法数据结构的设计主要有两方面的考虑：
如何高效地存储图中的节点和节点之间的关系
如何在设计的数据结构上高效地扫描数据、进行算法迭代。
当前一些开源的算法实现主要通过hash表或set的结构来存储节点和节点之间的关系。
主要有两个缺点：
维护hash 或 集合结构本身就需要不少内存开销
遍历过程中需要不断地创建、销毁、清空对应的Hash 或 Set 结构，尤其是在遍历不同的节点的邻居节点以及社区这点时。
而且，在遍历过程中，结构对元素的访问也并不是严格O(1)的。
出于以上考虑，我们设计一种更高效的数据结构来存储图中的节点和边，避开使用复杂的数据结构，且在算法迭代过程中不申请多余的空间和空间的销毁操作，具体如下：
关于节点字段的说明：
count：社区内的节点个数
clsid：节点归属社区的代表节点ID
next：步骤1迭代中下一个属于同一个临时社区的节点
prev：步骤1迭代中上一个属于同一个临时社区的节点
first：属于同一个社区的，除代表节点外的第一个节点，该节点有步骤2 社区折叠的时候生成
kin：稳定社区内部节点之间的互相连接权重之和
kout：稳定社区外部，指向自己社区的权重之和
clskin：临时社区内部节点之间的互相连接权重之和
clstot：稳定社区所有内外部指向自己的连接权重之和
eindex：节点邻居链表的第一个指针，该链表下的所有left，都是本节点自己
关于边数据结构的字段就顾名思义即可。
基于上述结构设计，在给定了一个M个节点，N调边的图所需的空间为：60 * M + 24 * N.
例如：给定1000万给点，2000万边的数据，则需要空间约为：10000000 * 60 + 20000000 * 24 = 1080M.且整个迭代过程中内存环境维持不变。
迭代过程
1、假设我们最开始有5个点，互相之间存在一定的关系(至于什么关系，先不管)，如下：
2、假设在进过了步骤1的充分迭代之后发现节点2，应该加入到节点1所在的社区(最开始每个点都是一个社区，而自己就是这个社区的代表)，新的社区由节点1代表，如下：
此时节点3，4，5之间以及与节点1，2之间没有任何归属关系。
3、此时应该执行步骤2，将节点1，2组合成的新社区进行折叠，折叠之后的社区看成一个单点，用节点1来代表，如下：
此时数据中共有4个节点(或者说4个社区)，其中一个社区包含了两个节点，而社区3，4，5都只包含一个节点，即他们自己。
4、重新执行步骤1，对社区1，3，4，5进行扫描，假设在充分迭代之后节点5，4，3分别先后都加入了节点1所在的社区，如下：
5、进行步骤2，对新生成的社区进行折叠，新折叠而成的社区看成一个单点，由节点1代表，结构如下：
此时由于整个数据中只剩下1个社区，即由节点1代表的社区。
再进行步骤1时不会有任何一个节点的社区归属发生变化，此时也就不需要再执行步骤2，至此， 迭代结束。
代码实现及测试
一个基于上述结构设计的代码实现参见：
https://github.com/liuzhiqiangruc/dml/blob/master/cls/louvain.c
在一个实际的图(70万点，200万边)上进行测试，迭代到完全收敛所需时间为：1.77秒。
实际中往往不需要迭代到每一个点都不发生变化，或者整个图中有多少比例的节点不在发生变化就退出。
本篇为算法系列文章的第3篇，为大家分享了Louvain算法的原理及设计实现。
本文来自360视频信息流算法团队投稿，我们将每周为大家推送一篇算法相关的文章，欢迎大家一起交流学习。
相关推荐
深度残差网络的一波两折
浅谈 梯度下降法/Gradient descent
界世的你当不
只做你的肩膀
无
 360官方技术公众号 
技术干货|一手资讯|精彩活动
空·
点关注哦~

奇技指南
在海量的信息流中，通过精准的算法给用户推荐其感兴趣的内容，已经成为了一个产品吸引用户，获取收益的极其重要的方式。
本篇为算法系列文章，将为大家分享360的算法团队在实践中积累的算法知识及经验，欢迎大家交流分享~
Louvain算法是一种基于多层次优化Modularity的算法，具有快速、准确的优点，在效率和效果上都表现比较好，并且能够发现层次性的社区结构，被认为是性能最好的社区发现算法之一。
模块度
Louvain算法是一种基于图数据的社区发现算法。
原始论文为：
《Fast unfolding of communities in large networks》。
Louvain算法的优化目标为最大化整个数据的模块度，
模块度的计算如下：
其中m为图中边的总数量，k_i表示所有指向节点i的连边权重之和，k_j同理。A_{i,j} 表示节点i，j之间的连边权重。
有一点要搞清楚，模块度的概念不是Louvain算法发明的，而Louvain算法只是一种优化关系图模块度目标的一种实现而已。
Louvain算法的两步迭代设计
最开始，每个原始节点都看成一个独立的社区，社区内的连边权重为0
步骤1
算法扫描数据中的所有节点，针对每个节点遍历该节点的所有邻居节点，衡量把该节点加入其邻居节点所在的社区所带来的模块度的收益。并选择对应最大收益的邻居节点，加入其所在的社区。这一过程化重复进行指导每一个节点的社区归属都不在发生变化。
步骤2
对步骤1中形成的社区进行折叠，把每个社区折叠成一个单点，分别计算这些新生成的“社区点”之间的连边权重，以及社区内的所有点之间的连边权重之和。用于下一轮的步骤1。
该算法的最大优势就是速度很快，步骤1的每次迭代的时间复杂度为O(N)，N为输入数据中的边的数量。步骤2 的时间复杂度为O(M + N)， M为本轮迭代中点的个数。
算法实现
数据结构设计
算法数据结构的设计主要有两方面的考虑：
如何高效地存储图中的节点和节点之间的关系
如何在设计的数据结构上高效地扫描数据、进行算法迭代。
当前一些开源的算法实现主要通过hash表或set的结构来存储节点和节点之间的关系。
主要有两个缺点：
维护hash 或 集合结构本身就需要不少内存开销
遍历过程中需要不断地创建、销毁、清空对应的Hash 或 Set 结构，尤其是在遍历不同的节点的邻居节点以及社区这点时。
而且，在遍历过程中，结构对元素的访问也并不是严格O(1)的。
出于以上考虑，我们设计一种更高效的数据结构来存储图中的节点和边，避开使用复杂的数据结构，且在算法迭代过程中不申请多余的空间和空间的销毁操作，具体如下：
关于节点字段的说明：
count：社区内的节点个数
clsid：节点归属社区的代表节点ID
next：步骤1迭代中下一个属于同一个临时社区的节点
prev：步骤1迭代中上一个属于同一个临时社区的节点
first：属于同一个社区的，除代表节点外的第一个节点，该节点有步骤2 社区折叠的时候生成
kin：稳定社区内部节点之间的互相连接权重之和
kout：稳定社区外部，指向自己社区的权重之和
clskin：临时社区内部节点之间的互相连接权重之和
clstot：稳定社区所有内外部指向自己的连接权重之和
eindex：节点邻居链表的第一个指针，该链表下的所有left，都是本节点自己
关于边数据结构的字段就顾名思义即可。
基于上述结构设计，在给定了一个M个节点，N调边的图所需的空间为：60 * M + 24 * N.
例如：给定1000万给点，2000万边的数据，则需要空间约为：10000000 * 60 + 20000000 * 24 = 1080M.且整个迭代过程中内存环境维持不变。
迭代过程
1、假设我们最开始有5个点，互相之间存在一定的关系(至于什么关系，先不管)，如下：
2、假设在进过了步骤1的充分迭代之后发现节点2，应该加入到节点1所在的社区(最开始每个点都是一个社区，而自己就是这个社区的代表)，新的社区由节点1代表，如下：
此时节点3，4，5之间以及与节点1，2之间没有任何归属关系。
3、此时应该执行步骤2，将节点1，2组合成的新社区进行折叠，折叠之后的社区看成一个单点，用节点1来代表，如下：
此时数据中共有4个节点(或者说4个社区)，其中一个社区包含了两个节点，而社区3，4，5都只包含一个节点，即他们自己。
4、重新执行步骤1，对社区1，3，4，5进行扫描，假设在充分迭代之后节点5，4，3分别先后都加入了节点1所在的社区，如下：
5、进行步骤2，对新生成的社区进行折叠，新折叠而成的社区看成一个单点，由节点1代表，结构如下：
此时由于整个数据中只剩下1个社区，即由节点1代表的社区。
再进行步骤1时不会有任何一个节点的社区归属发生变化，此时也就不需要再执行步骤2，至此， 迭代结束。
代码实现及测试
一个基于上述结构设计的代码实现参见：
https://github.com/liuzhiqiangruc/dml/blob/master/cls/louvain.c
在一个实际的图(70万点，200万边)上进行测试，迭代到完全收敛所需时间为：1.77秒。
实际中往往不需要迭代到每一个点都不发生变化，或者整个图中有多少比例的节点不在发生变化就退出。
本篇为算法系列文章的第3篇，为大家分享了Louvain算法的原理及设计实现。
本文来自360视频信息流算法团队投稿，360技术原创文章，我们将每周为大家推送一篇算法相关的文章，欢迎大家一起交流学习。转载请务必注明出处及来源
关于360技术
360技术是360技术团队打造的技术分享公众号，每天推送技术干货内容
更多技术信息欢迎关注“360技术”微信公众号