最近看 Recommender System 的时候对豆瓣一位推荐算法工程师中一篇关于YouTube的博文感兴趣，就把这两篇文章翻来看了下，08年的十页论文求精求细，算法和实验都很详细，10年的四页论文则更注重从系统的角度简介了一下。我就对算法进行了简单总结，如有不妥请指正：
首先是 Shumeet 等人08年提出的 Random Walks through the view graph 算法，文章在引言提出了相关视图（Co-View Graph）的概念，相关视图（Co-View Graph）由视频节点（vertex）、节点之间的边以及标签等构成，节点之间的边是通过用户行为决定的，比如用户同时观看这两个视频。吸收算法（Adsoption Algorithm）是论文的算法基础，本质上是利用节点上的边将节点进行分类的一种算法。文章中具体谈到了以吸收算法为基础的三种算法：
Adsorption via Avergaing
算法描述如下：
Input: G = ( V,E,w ) , L , 
repeat
for each 
do:
Let 
end-for
Normalize 
to have unit 
norm
until covergence
Output: Distributions { 
}
这里 
和 分别代表无标签节点和有标签节点，L 代表标签，w 代表节点之间的边，整个算发就是对每个节点进行标签聚合，节点 v 的聚合方式就是通过将所有和 v 之间有边 w(u,v) 的节点 u 的标签聚合起来 直到整个算法收敛，这里收敛可以通过取阈值的方式。
Adsorption via Random Walks
Random walks 翻译为中文可以叫做“随机游走”吧，用随机数学的概念来说就是在非常短的时间内状态的该变量为1，它以一个节点 v 为起点开始游走，每游走一步将新的一步的节点加入到集合中，直到没有新的节点可加入为止，算法的好处在于计算量比上一种少，随机性也较好。
Adsorption via Linear Systems：
算法如下：
Input: G= ( V , E , w )
Let n:=|V|
Define the linear system of equations in 
variables 
, for 
：
算法的核心就是计算节点到节点之间的权重 ，每个节点的权重之和为 1，且计算u点到v点得权重方法是通过计算u点通过所有点到达v点权重的线性组合。算法的好处就是能够很好的处理节点标签的更新以及节点的变化。
接着谈谈10年由 James Davidson 等人的 4 页论文，文章短小意赅。首先是 YouTube 视频面临的主要挑战主要有两点：没有足够的元数据和用户交互相对较短和嘈杂。推荐算法为用户不仅提供离散而且与用户相关的视频，也提供些最新的视频，这种推荐是根据用户的个人行为来决定的。输入数据包括视频数据和用户交互数据，用户交互的数据包括隐形和显性数据，如为视频评分，留言，观看多长时间等。数据处理第一步是关联视频：即为视频 
生成一个相关视频的集合 
，这样用户在看视频 v 时用其做种子生成相关视频，采用的是关联规则挖掘技术，定义视频 和 
关联分数为：
表示连续看了 和 的（从哪到哪没关系） 
是考虑了这两个视频和候选视频“全局欢迎度”的归一化函数，最简单的一个方式就是： 
，接着根据视频的关联分数排列 个关联视频。接着是产生推荐候选视频：还是根据得到的关联视频 生成第一个相关视频集合：
S 是种子集合（我理解可以是用户所有看过的视频），将 S 中所有的节点 通过上面的关联算法生成 集合的集合 
为第一个相关视频集合，并用递归的方式形成第 N 个视频集合：
我们定义了 
那么我们的推荐应该把 S 剔除，得到最终的推荐视频集合：
因为视频分支多，即使只有少量的种子也会有大量的推荐，最后就是排名了，这可以参考三个要素：视频质量、用户的喜好、多样化，最终将这三个参数通过线性组合的方式得到排序的分。
下面是我对 YouTube 视频推荐算法分类的看法，如果不妥请指正：首先我认为两篇论文阐述的 YouTube 视频推荐算法应该都是基于关联规则的推荐算法（Association Rule-based Recommnendation），08年算法核心是吸收算法（Adsorption Algorithm），简单来说就是把用户 u 和用户 v 看过的视频关联起来，10年的算法核心是 
关联系数。所以YouTube 视频推荐算法不应该是 item-based CF 算法，我理解的 CF 算法核心应该具有 user-item 的矩阵，至于是 user-based 还是 item-based 就取决于对矩阵行列的分析。
