论文学习：Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph

论文《Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph》发表于2008年，是相对比较早的一篇有关于YouTube推荐系统的文章。

1.简介

在最初的阶段，YouTube认为应该给用户推荐曾经观看过视频的同类视频，或者说拥有同一标签的视频。然而此时，YouTube的视频已是数千万量级，主要困难在于，尽管可以通过基于计算机视觉的技术可靠地推断出某些标签，但尚不存在任何令人满意的机制来对视频中的大部分内容进行标签；更为困难的是，YouTube视频中存在的标签通常很小，他们只捕获一小部分内容。解决该困难的核心方案有两部分：一是基于用户共同观看记录构建的图结构（Video Co-View Graph）；二是基于此数据结构的算法，被称为吸附算法（Adsorption Algorithm）。

2.共视图结构

共视信息为视频推荐提供了简单的基础。可以如下构建通常用作基于项目的协作过滤系统的基础的简单系统。假设用户U观看了两个视频J和K；从我们的共同观看统计数据中，我们知道看到视频J的许多其他用户也看到了视频L，M，N；类似地，对于视频K，我们知道许多其他用户看到了视频N，O，P，Q；因此，根据他对J和K的观看，我们可能推荐给U的视频可以简单地看作是两个共同视图集的集合：L，M，N，O，P，Q。为了对推荐进行排名，我们可以查看一个视频的浏览量（这将推荐流行视频）、每个视频的共同观看次数（这将推荐流行视频，考虑到用户所看到的内容），或者考虑每个视频被推荐给U的次数（注意，视频N被推荐了两次）等因素给出一个打分函数。

3.吸附算法

作者在本文中用大量篇幅讲述了吸附算法（Adsorption Algorithm ），该算法的目的就是为了解决视频标签的扩散，当我们有一个小的labeled数据集和一个很大的unlabeled数据集时，可以通做Adsorption将label从小的数据集推广到大数据集上。论文介绍了三个吸附算法，分别是通过均值的吸附，通过随机游走的吸附和通过线性系统的吸附。
吸附算法是基于 $G$ 图的，而这个图 $G=<V,E,\omega>$ 就是视频间的关联度图，公式中 $V$ 代表图中的节点，也就是一个个视频，注意节点会包含多个标签。 $E$ 代表节点间的连线，也就是视频之间是关联的。而 $\omega$ 代表边的权重，也就是视频之间的关联程度，文章中是用用户共同观看次数来表示这个权重，用户共同看过这两个视频的次数越多，这个权重越大。如果没有，则两个视频间没有关联，也就是没有边。
均值吸附：
均值吸附的算法流程如下：