推荐系统的目的是联系用户的兴趣和物品这种联系需要依赖于不同的媒介。GroupLens在文章中认为目前流行的推荐系统基本上通过三种方式来联系用户兴趣和物品如图1所示，苐一种方式是通过用户喜欢过的物品：可以给用户推荐与他喜欢过的物品相似的物品这就是前面提到的基于物品的算法（item-based）。第二种方式是通过和用户兴趣相似的其他用户：可以给用户推荐那些和他们兴趣爱好相似的其他用户喜欢的物品这也是前面提到的基于用户的算法（user-based）。除了这两种方法第三个也是最重要的方式是通过一些特征（feature）来联系用户和物品，可以给用户推荐那些具有用户喜欢的特征的粅品这里的特征有不同的表现方式，比如可以表现为物品的属性集合（比如对于图书属性集合就包括了作者、出版社、主题和关键词等），也可以表现为隐语义向量（latent
Model）学习得到在本章中，我们将讨论一种重要的特征表现方式：标签
图1 推荐系统联系用户和物品的几種途径
根据维基百科的定义，标签是一种无层次化结构的、用来描述信息的关键词因此，标签可以用来准确地描述物品的语义根据给粅品打标签的人的不同，标签应用一般分为两种第一种是让作者或者编辑给物品打标签，而另一种是让普通用户给物品打标签也就是UGC嘚标签应用。表1列出了这两种不同的标签系统的代表网站在本章中，我们主要讨论UGC的标签应用研究用户给物品打标签的行为，以及如哬通过分析这种行为给用户进行个性化推荐
表1 两种不同的标签系统的代表网站
UGC的标签系统是一种很重要的表示用户兴趣和物品语义的方式。当一个用户对一个物品打上一个标签后这个标签一方面描述了用户的兴趣，另一方面也表示了物品的语义从而将用户和物品联系叻起来。
UGC标签系统是很多Web 2.0网站的必要组成部分本节将讨论使用UGC标签系统的代表网站：UGC标签系统的鼻祖美味书签（Delicious）、论文书签网站CiteULike、音乐网站Lastfm、视频网站Hulu、书和电影评论网站豆瓣等。下面将分别介绍这些应用
美味书签（Delicous）是标签系统里的开山鼻祖了，它允许用户给互联网上的每个网页打上标签从而通过标签的方式重新组织整个互联网。图2是Delicious中被用户打上recommender
system标签最多的网页这些网页反应了用户心目中和推荐系统最相关的网页。图3是Delicious中“豆瓣电台”这个网页被用户打的最多的标签可以看到这些标签确实准确地描述了豆瓣电台。
图3 Delicious中“豆瓣电台”网页被用户打的最多的标签
CiteULike是一个著名的论文书签网站它允许研究人员提交或者收藏他们感兴趣的论文，給论文打标签从而帮助用户更好地发现和自己研究领域相关的优秀论文。我们知道研究人员搜索自己研究领域值得参考的论文是很费時费力的工作，而CiteULike通过群体智能让每个研究人员对自己了解的论文进行标记，从而帮助用户更好更快地发现自己感兴趣的论文图4展示叻CiteULike中一篇被用户打的标签最多的有关推荐系统评测的文章，可以发现最多的两个标签是collaborative-filtering（协同过滤）和evaluate（评测），确实比较准确地反应叻这篇论文的主要内容
Lastfm是一家著名的音乐网站，它通过分析用户的听歌行为来预测用户对音乐的兴趣从而给用户推荐个性化的音乐。莋为多媒体音乐不像文本那样可以很容易地分析它的内容信息。为了在不进行复杂的音频分析的情况下获得音乐的内容信息Lastfm引用了标簽系统，让用户用标签标记音乐和歌手图5展示了披头士乐队在Lastfm中的标签云（tag
cloud）。从这个标签云可以看到披头士应该是一个英国的传统搖滚乐队，流行于上世纪60年代
图5 Lastfm中披头士乐队的标签云
豆瓣是中国著名的评论和社交网站，同时也是中国个性化推荐邻域的领军企业之┅豆瓣在个性化推荐领域进行了广泛的尝试，标签系统也是他们尝试的领域之一他们允许用户对图书和电影进行标签，从而获得图书囷电影的内容信息并用这种信息来改善他们的推荐效果。图7展示了《数据挖掘导论》在豆瓣被用户标记的情况如图7所示，最多的几个標签分别是：数据挖掘、计算机、计算机科学、数据分析、IT数据分析这些标签准确地反应了这本书的内容信息。
图6 豆瓣读书中《数据挖掘导论》一书的常用标签
Hulu是美国著名的视频网站视频作为一种最为复杂的多媒体，获取它的内容信息是最困难的因此，Hulu也引入了用户標签系统来让用户对电视剧和电影进行标记图7展示了美剧《豪斯医生》的常用标签，可以看到Hulu对标签做了分类，并展示了每一类最热門的标签从类型（genre）看，豪斯医生是一部医学片（medical
drama）；从时间看这部剧开始于2004年；从人物看，这部美剧的主演是hugh laurie他在剧中饰演的人粅是greg house。
图7 Hulu中《豪斯医生》的常用标签
从前面的各种应用可以看到标签系统在各种各样的网站中（音乐、视频和社交等）都得到了广泛的應用。标签系统的最大优势在于可以发挥群体的智能获得物品内容信息的比较准确的关键词描述，而准确的内容信息是提升个性化推荐系统的重要资源
标签行为作为一种重要的用户行为，蕴含了很多反映用户兴趣的信息因此深入研究用户的标签行为可以很好地指导个性化推荐系统提升自己的推荐质量。同时标签作为一种重要的内容表示方式，比传统的内容属性表示更能反应用户对物品的看法并且表示形式非常简单，便于很多算法处理
标签系统中的推荐问题主要有以下两个。
如何在用户给物品打标签时给用户推荐适合于该物品的標签（tag recommendation）
为了研究上面的两个问题，我们首先需要解答下面三个问题
用户为什么要打标签（Why）？
用户怎么打标签（How）
用户打什么样嘚标签（What）？
在设计基于Tag的个性化推荐系统之前我们需要深入了解用户的标注行为，知道用户为什么要标注用户怎么标注，只有深刻哋了解用户的行为我们才能基于这个行为给用户设计出令他们满意的个性化推荐系统。
Ames研究图片分享网站中用户标注的动机问题他将鼡户标注的动机***成两个维度。首先是社会维度有些用户标注是为了给内容的上传者使用的，而有些用户标注是为了给广大用户使用嘚令一个维度是功能维度，有些标注是为了更好地组织内容方便用户将来的查找，而另一些标注是为了传达某种信息比如照片的拍攝时间和地点等。
在互联网中尽管每个用户的行为看起来是随机的，但其实这些表面随机的行为的背后蕴含着很多规律在这一节中，峩们通过研究美味书签的数据集来发现用户标注行为中的一些统计规律。
德国的研究人员公布过一个很庞大的美味书签的数据集该数據集包含了2003年9月到2007年12月美味书签用户4.2亿条标签行为记录。本节选用该数据集2007年一整年的数据进行分析对该数据集的统计特性进行研究。
夲节将统计数据集的以下信息
用户标签行为随时间演化的曲线。
用户相隔一段时间兴趣变化的情况
[*具体统计结果待书正式出版时公布*]**
鼡户在看到一个物品时，我们最希望他打的标签是能够准确描述物品内容属性的关键词但用户往往不是按照我们的想法去操作，而是可能会给物品打上各种各样奇怪的标签
Scott A. Golder 总结了美味书签上的标签，将它们分为如下的几类
表明物品是什么：比如是一只鸟，就会有“鸟”这个词的标签；是豆瓣的首页就有一个标签叫“豆瓣”；是乔布斯的首页，就会有个标签叫“乔布斯”
表明物品的种类：比如在美菋书签中，表示一个网页的类别的标签包括 article（文章）、 blog（博客）、 book（图书）等
表明谁拥有物品 ：比如很多博客的标签中会包括博客的作鍺等信息。
表达用户的观点：比如用户认为网页很有趣就会有funny（有趣）的标签，认为很无聊就会打上boring（无聊）的标签。
用户相关的标簽：有些标签比如 my favorite（我最喜欢的）、my comment（我的评论）等。
用户的任务：比如 to read（即将阅读）、 job search（找工作）等
很多不同的网站也设计了自己嘚标签分类系统，比如Hulu对视频的标签就做了分类
图8是著名的美剧《豪斯医生》的标签。可以看到Hulu将电视剧的标签分成了几类。
类型（Genre）：主要表示这个电视剧的类别比如《豪斯医生》是属于医学剧情片（medical
时间（Time）：主要包括电视剧发布的时间，有时也包括电视剧中事件发生的时间比如是二战期间，或者是上世纪90年代
人物（People）：主要包括电视剧的导演、演员和剧中重要人物等。
地点（Place）：剧情发生嘚地点或者是视频拍摄的地点等。
语言（Language）：这部电视剧使用的语言
奖项（Awards）：这部电视剧获得的相关奖项。
其他（Details）：包含了不能歸类到上面各类的其他所有标签
图8 著名美剧《豪斯医生》在视频网站Hulu上的标签分类
用户用标签来描述自己对物品的看法，因此标签成為了联系用户和物品的纽带。因此标签数据是反应用户兴趣的重要数据源，而如何利用用户的标签数据来提高用户个性化推荐结果的质量是推荐系统研究的重要问题。
在如何利用标签数据的问题上豆瓣无疑是这方面的代表。豆瓣将标签系统融入到他们的整个产品线中下面以豆瓣读书为例进行介绍。首先在每本书的页面上，都提供了一个叫做“豆瓣成员常用标签”的应用它给出了这本书上用户最瑺打的标签。同时在用户希望给书做评价时，豆瓣也会让用户给图书打标签最后，在最终的个性化推荐结果里豆瓣利用标签将用户嘚推荐结果做了聚类，显示了不同标签下用户的推荐结果从而增加了推荐的多样性和可解释性。
一个用户标签行为的数据集一般由一个彡元组的集合表示其中记录(u, i, b) 表示用户u给物品i打上了标签b。当然用户的真实的标签行为数据远远比三元组表示的要复杂，比如用户标签嘚时间、用户的属性数据、物品的属性数据等但是，在本章中为了集中讨论标签数据，我们只考虑上面定义的三元组形式的数据即鼡户的每一次标签行为都用一个三元组(用户,物品,标签)来表示。
在下面的各节中我们将利用Delicious的数据集，讨论如何利用用户标签数据进行个性化推荐的各种算法
我们将Delicious的数据集按照9：1随机分成训练集R和测试集T。这里分割的键值是用户和物品不包括标签，也就是说用户对粅品的多个标签记录要么都被分进训练集，要么都被分进测试集
在分完数据集后，我们将通过学习训练集中的用户标签数据来预测测試集上用户会给什么物品打标签。对于用户u令R(u)是给用户u的长度为N的推荐列表，里面包含着我们认为用户会打标签的物品而另T(u)是测试集Φ用户u实际上打过标签的物品集合。然后我们利用准确率/召回率（Precision/Recall）来评测个性化推荐算法的准确率：
如果用Python实现上面的两个指标，我們可以通过如下的代码：
同时为了全面评测个性化推荐的性能，我们同时评测了推荐结果的覆盖度（Coverage）、多样性（Diversity）和新颖度
覆盖度峩们通过如下的公式和代码计算：
关于多样性，我们在第1章中讨论过多样性的定义取决于相似度的定义。在本章中我们用物品的标签姠量的余弦相似度来度量物品之间的相似度。对于每个物品iitemtags[i]存储了物品i的标签向量，其中itemtags[i][b]是物品i上标签b被打的次数那么物品i和j的余弦楿似度可以通过如下的程序计算：
在得到物品之间的相似度度量后，我们通过如下的公式来计算一个推荐列表的多样性：
如果用程序实现代码如下：
而推荐系统的多样性定义为所有用户的推荐列表的多样性的平均值。
至于推荐结果的新颖性这里我们简单地用推荐结果的岼均热门程度（AveragePopularity）来度量。对于物品i定义它的热门度item_pop(i)为给这个物品打过标签的用户数。而对推荐系统我们定义它的新颖度如下：
如果鼡程序实现，代码如下：
当拿到了用户标签行为数据时大家都可以想到一个最简单的算法来给用户推荐个性化的物品。这个算法的描述洳下所示
统计每个用户最常用的标签。
对于每个标签统计被打过这个标签的次数最多的物品。
对于一个用户首先找到他常用的标签，然后对于这些常用标签找到具有这些标签的最热门的物品，推荐给这个用户
如果用公式描述上面的算法，那么用户u对物品i的兴趣可鉯用如下的公式度量：
这里B(u)是用户u打过的标签集合，B(i)是物品i被打过的标签集合, 是用户u打过标签b的次数 是物品i被打过标签b的次数。本章鼡SimpleTagBased来标记这个算法
在Python中，我们用 records 来存储标签数据的三元组其中
统计出usertags和tagitems之后，可以通过如下程序对用户进行个性化推荐：
我们在Delicious数据集上对上面的算法进行评测结果如表2所示。
表2 简单的基于标签的推荐算法在Delicious数据集上的评测结果
我们再来回顾一下上面提出的简单算法该算法通过如下公式预测用户u对物品i的兴趣：
仔细研究上面的公式，可以发现上面的公式有很多缺点下面我们将逐条分析该算法的缺點，并提出改进意见
如果我们从概率论的角度出发，认为用户u喜欢物品i的概率取决于u曾经打过的标签那么我们会得到如下的概率公式：
这个公式和SimpleTagBased算法的公式相比，对参数做了归一化而且他的解释也是从概率的角度出发，更加明确本章用NormTagBased来代表这个算法。表3给出了SimpleTagBased算法和NormTagBased算法在各种指标上的实验结果的比较
如表3所示，经过归一化之后的NormTagBased算法无论在召回率/准确率还是在覆盖度、多样性和热门程度等指标上，均优于SimpleTagBased算法因此，NormTagBased算法是对SimpleTagBased的算法的一个有效的改进
在前面的算法中，用户兴趣和物品的联系是通过B(u)∩B(i)中的标签建立的泹是，如果这个用户是新用户或者物品是新物品，那么这个集合（B(u)∩B(i)）中的标签数量会很少为了提高推荐的准确率，我们可能要对标簽集合做扩展比如用户曾经用过“推荐系统”这个标签，我们可以将这个标签的相似标签也加入到用户标签集合中比如“个性化”，“协同过滤”等标签
为了说明数据稀疏性对性能的影响，我们将用户按照打过的标签数分成两组第一组用户打过10次以下的标签，而第②组用户打过超过10次标签我们分别统计这两组用户的推荐结果的准确率和召回率，结果如表4所示
表4 不同活跃度的用户的召回率/准确率對比
[具体实验结果待正式发表时公布]
进行标签扩展有很多方法，其中著名的有话题模型（Topic Model）不过这里我们遵循简单的原则，只介绍一种基于邻域的方法
标签扩展的本质是对每个标签找到和它相似的标签，也就是计算标签之间的相似度最简单的相似度可以是同义词。如果我们有一个同义词词典就可以根据这个词典来进行标签扩展。如果没有这个词典我们还是可以从数据中统计出标签的相似度。
如果認为同一个物品上的不同标签具有某种相似度的话那么如果两个标签同时出现在很多物品的标签集合中，就可以认为这两个标签具有较夶的相似度对于标签b，令N(b)为有标签b的物品的集合n_(b,i)为给物品i打上标签b的用户数，可以通过如下的余弦相似度公式计算标签b和标签b'的相似喥：
[具体实验结果待正式发表时公布]
不是所有的标签都能反应用户的兴趣比如，在一个视频网站中用户可能对一个视频赋予了一个表礻情绪的标签，比如“不好笑”（no funny）但我们不能因此认为用户对“不好笑”有兴趣，并且给用户推荐其他具有“不好笑”这个标签的视頻相反，如果用户对视频打过“成龙”这个标签我们可以据此认为用户对成龙的电影感兴趣，从而给用户推荐成龙其他的电影同时，标签系统里经常出现词形不同、词义相同的标签比如recommender system和recommendation engine就是两个同义词。
标签清理的另一个重要意义在于用标签作为推荐解释如果峩们要把标签呈现给用户，作为给用户推荐某一个物品的解释时对标签的质量要求就很高。首先这些标签不能包含没有意义的停止词戓者表示情绪的词，其次这些推荐解释里不能包含很多相同意义的词语
本章我们使用的标签清理的方法有以下几种。
去除词频很高的停圵词
[具体实验结果待正式发表时公布]
为了控制标签的质量，很多网站也采用了让用户反馈的思想即让用户来告诉系统某个标签是否合適。MovieLens在他们的实验系统中就采用了这种方法关于这方面的研究可以参考GroupLens的Shilad同学的博士论文 。此外电影推荐网站Jinni也采用了这种方式（如圖9所示）。当然Jinni不属于UGC的标签系统，它给电影的标签是专家赋予的因此它让用户对标签反馈其实是想融合专家和广大用户的知识。
图9 Jinni尣许用户对编辑给的标签进行反馈
前面讨论的简单算法很容易懂也容易实现，但缺点是不够系统化和理论化因此，在这一节中我们主要讨论如何利用图模型来做基于标签数据的个性化推荐。
首先我们需要将用户的标签行为表示到一个图上。我们知道图是由顶点、邊和边上的权重组成的。而在用户标签数据集上有三种不同的元素：用户、物品和标签。因此我们需要定义三种不同的顶点：用户顶點、物品顶点和标签顶点。然后如果我们得到一个表示用户u给物品i打了标签b的用户标签行为(u,i,b)，那么最自然的想法就是在图中增加三条邊，首先在用户u对应的顶点v(u)和物品i对应的顶点v(i)之间需要增加一条边（如果这两个顶点已经有边相连那么就应该将边的权重加1），同理茬v(u)和v(b)之间需要增加一条边， v(i)和v(b)之间也需要边相连接
图10是一个简单的用户-物品-标签图的例子。
图10 一个简单的用户-物品-标签图的例子
通过用戶标签行为构造出图之后为用户u推荐物品的问题就转化为计算图上所有物品节点相对于用户节点v(u)的相关度排名的问题。图上的排名算法佷多其中最著名的就是PageRank算法。
PageRank算法最初是用来对互联网上的网页进行排名的算法网页通过超级链接形成了图。PageRank假设用户从所有网页里隨机挑出一个网页然后开始通过超级链接进行网上冲浪。到达每个网页后用户首先会以d的概率继续冲浪，而在冲浪时用户会以同等嘚概率在当前网页的所有超级链接中随机挑选一个进入下一个网页。那么在这种模拟下，最终每个网页都会有一个被用户访问到的稳定概率而这个概率就是网页的排名。
PageRank算法通过如下的迭代关系式来计算网页的权重：
其中PR(i)是网页i的排名d是用户每次继续冲浪的概率，N是所有网页的总数in(i)是指向网页i的所有网页的集合，out(j)是网页j链向的网页的集合
下面我们举一个简单的例子来说明PageRank算法，我们用图11所示的例孓来演示一下PageRank的迭代过程
(2)根据前面的迭代关系式有
(3)继续按照前面的迭代关系式，有
我们可以按照上面的步骤一步步迭代下去最终得到所有顶点的PageRank排名。
但是从上面的描述可以看到，PageRank只是计算了所有顶点的全局排名并不能用来计算一个顶点相对于另一个顶点的相关度排名。因此很多研究人员对PageRank做出了修改，其中一个著名的修改就是TopicRank算法
PageRank算法认为，用户每次都是从所有顶点中以相同的概率随机挑选┅个顶点然后开始随机游走，而且在每次随机游走经过每个顶点时都会有1 - d的概率停止游走。那么如果我们要计算所有点相对于某一個顶点的相关度排名，我们可以假设用户每次都从某一个顶点v出发然后在每次随机游走经过每个顶点时都以1-d的概率停止游走，从v重新开始 那么，最终每个顶点被访问的概率就是这些顶点和v的相关度排名
PageRank可以用来给图中的顶点进行全局的排名，但它无法用来给每个用户個性化的对所有物品排序为了解决个性化排名的问题，斯坦福大学的Haveliwala提出了TopicRank的算法 这个算法可以用来做个性化排序，因此本文将其称為PersonalRankPersonalRank的迭代公式如下：
可以看到，PersonalRank和PageRank的区别在于用ri代替了1/N也就是说，从不同的点重新开始的概率不同了那么，假设如果我们要计算所囿顶点和顶点k的相关度排名我们可以定义如下：
然后利用上面的迭代公式，就可以计算出所有顶点相对于k的相关度排名我们将这里的稱为顶点i的启动概率。
回到给用户推荐物品这个问题上来在我们构造出用户-物品-标签的图之后，如果我们要给用户u做推荐我们可以令頂点v(u)的启动概率为1，而其他顶点的启动概率为0然后用上面的迭代公式来计算所有物品对应的顶点相对于v(u)的排名。
下面两段Python代码给出了如哬从用户行为记录集合tagging_records中构建图以及如何在图上给用户进行推荐。
这里d是前面提到的继续随机游走的概率，K是迭代的次数在上面从某一个用户节点开始随机游走时，迭代K步最多可以走到离该用户节点距离为K之内的所有顶点而其他顶点的权重为0。
在传统的PersonalRank中我们需偠迭代很多次，直到所有顶点的权重都稳定了为止但是，如果我们为每个用户做推荐都需要在全图上进行迭代，直到全图的所有顶点嘚权重都收敛这样的时间复杂度太大了。因此我们在实际的应用中一般只迭代比较少的次数。
在介绍了圖模型后我们可以用图模型来重新看待前面提到的简单的算法。在那个算法中用户对物品的兴趣通过如下的公式计算：
这个公式认为鼡户对物品的兴趣通过标签来传递，因此这个公式可以通过一个比前面简单的图来建模（记为SimpleTagGraph）给定用户标签行为记录(u,i,b)，SimpleTagGraph会增加两条有姠边一条由用户节点v(u)指向标签节点v(b)，另一条由标签节点v(b)指向物品节点v(i)
图12就是一个简单的SimpleGraph的例子。在构建了SimpleGraph后利用前面的PersonalRank算法，令K = 1僦是我们前面提出的简单推荐算法。
[相关实验：发表时公布
A. 迭代次数K对精度的影响
B. 边权重的定义对精度的影响
基于标签的推荐的最大好处昰可以利用标签来做推荐解释这方面的代表性应用是豆瓣的个性化推荐系统。图13展示了豆瓣读书的个性化推荐界面
图13 豆瓣读书的个性囮推荐应用“豆瓣猜”的界面
如图13所示，豆瓣读书推荐结果包括两个部分上面是一个标签云，表示用户的兴趣分布标签的尺寸越大，表示用户对这个标签相关的图书越感兴趣比如图13显示了我在豆瓣的阅读兴趣，从上方的标签云可以看到豆瓣认为我对“编程”、“机器学习”、“软件开发”感兴趣，这是因为我看了很多IT技术方面的图书豆瓣认为我对“东野圭吾”感兴趣，是因为我看了好几本他的侦探小说同时因为我对人文学科比较感兴趣，所以豆瓣认为我对“传记”、“文化”比较感兴趣单击每一个标签云中的标签，都可以在標签云下方得到和这个标签相关的图书推荐比如图13就是机器学习相关的图书推荐。
豆瓣这样组织推荐结果页面有很多好处首先这样提高了推荐结果的多样性。我们知道一个用户的兴趣在长时间内是很广泛的，但在某一天又比较具体因此，我们如果想在某一天击中用戶当天的兴趣是非常困难的。而豆瓣通过标签云展示了用户的所有兴趣，然后让用户自己根据他今天的兴趣选择相关的标签得到推薦结果，从而极大地提高了推荐结果的多样性使得推荐结果更容易满足用户多样的兴趣。
同时标签云也提供了推荐解释的作用。用户通过这个界面可以知道豆瓣给自己推荐的每一本书都是基于它认为自己对某个标签感兴趣而对于每个标签，用户总能通过回忆自己之前嘚行为来知道自己是否真的对这个标签感兴趣
我们知道，要让用户直接觉得推荐结果是有道理的是很困难的。而豆瓣将推荐结果的可解释性拆分成了两个部分首先让用户觉得标签云是有道理的，然后让用户觉得从某个标签推荐出某本书也是有道理的因为生成让用户覺得有道理的标签云比生成让用户觉得有道理的推荐图书更加简单，标签和书的关系就更容易让用户觉得有道理从而让用户最终觉得推薦出来的书也是很有道理的。