第4章利用用户标签数据

GroupLens在一篇文章中(文章名是“Tagsplanations : Explaining Recommendations using Tags”)表示目前流行的推荐系统基本上通过3种方式联系用户兴趣和物品。

基于物品的算法 比如UserCF
基于用户的算法 比如ItemCF
基于特征的算法 比如隐语义模型

推荐系统联系用户和物品的几种途径

本章将讨论一种重要的特征表现方式——标签。
根据维基百科的定义(参见http://en.wikipedia.org/wiki/Tag_(metadata) )，标签是一种无层次化结构的、用来描述信息的关键词，它可以用来描述物品的语义。根据给物品打标签的人的不同，标签应用一般分为两种：一种是让作者或者专家给物品打标签；另一种是让普通用户给物品打标签，也就是UGC(User Generated Content，用户生成的内容)的标签应用。UGC的标签系统是一种表示用户兴趣和物品语义的重要方式。当一个用户对一个物品打上一个标签，这个标签一方面描述了用户的兴趣，另一方面则表示了物品的语义，从而将用户和物品联系了起来。本章主要讨论UGC的标签应用，研究用户给物品打标签的行为，探讨如何通过分析这种行为给用户进行个性化推荐。

4.1 UGC标签系统的代表应用

4.1.1 Delicious

Delicious允许用户给互联网上的每个网页打标签，从而通过标签重新组织整个互联网。

4.1.2 CiteULike

CiteULike是一个著名的论文书签网站，它允许研究人员提交或者收藏自己感兴趣的论文并且给论文打标签，从而帮助用户更好地发现和自己研究领域相关的优秀论文。

4.1.3 Last.fm

Last.fm在前面已经介绍过，是一家著名的音乐网站，它通过分析用户的听歌行为预测用户对音乐的兴趣，从而给用户推荐个性化的音乐。

4.1.4 豆瓣

豆瓣允许用户对图书和电影打标签，借此获得图书和电影的内容信息和语义，并用这种信息改善推荐效果。

4.1.5 Hulu

Hulu是美国著名的视频网站。视频作为一种最为复杂的多媒体，获取它的内容信息是最困难的，因此Hulu也引入了用户标签系统来让用户对电视剧和电影进行标记。

总结以上标签系统的各种应用，标签系统的最大优势在于可以发挥群体的智能，获得对物品内容信息比较准确的关键词描述，而准确的内容信息是提升个性化推荐系统性能的重要资源。

关于标签系统的作用， GroupLen的Shilads Wieland Sen在MoveLens电影推荐系统上做了更为深入的、基于问卷调查的研究。在博士论文(博士论文为“Nurturing Tagging Communities”)中，他探讨了标签系统的不同作用，以及每种作用能够影响多大的人群，如下所示。

表达标签系统帮助我表达对物品的看法。（30%的用户同意。）
组织打标签帮助我组织我喜欢的电影。（23%的用户同意。）
学习打标签帮助我增加对电影的了解。（27%的用户同意。）
发现标签系统使我更容易发现喜欢的电影。（19%的用户同意。）
决策标签系统帮助我判定是否看某一部电影。（14%的用户同意。）

上面的研究表明，标签系统确实能够帮助用户发现可能喜欢的电影。

4.2 标签系统中的推荐问题

标签系统中的推荐问题主要有以下两个。

如何利用用户打标签的行为为其推荐物品（基于标签的推荐）？
如何在用户给物品打标签时为其推荐适合该物品的标签（标签推荐）？

为了研究上面的问题，首先需要解答下面3个问题。

用户为什么要打标签？
用户怎么打标签？
用户打什么样的标签？

4.2.1 用户为什么进行标注

Morgan Ames研究图片分享网站中用户标注的动机问题，并从两个维度进行探讨(参见Morgan Ames和 Mor Naaman的“Why we tag: motivations for annotation in mobile and online media”（ CHI 2007，2007）)。首先是社会维度，有些用户标注是给内容上传者使用的（便于上传者组织自己的信息），而有些用户标注是给广大用户使用的（便于帮助其他用户找到信息）。另一个维度是功能维度，有些标注用于更好地组织内容，方便用户将来的查找，而另一些标注用于传达某种信息，比如照片的拍摄时间和地点等。

4.2.2 用户如何打标签

该节通过研究Delicious数据集总结用户标注行为中的一些统计规律，即标签的流行度分布同用户活跃度、物品流行度分布一致都遵循长尾分布(Power Law分布)，实验具体过程见书。

4.2.3 用户打什么样的标签

用户在对物品打标签时，可能并非如我们希望地提供能够准确描述物品内容属性的关键词，而是各种奇怪的标签。

Delicious上的标签分类

Scott A. Golder 总结了Delicious上的标签，将它们分为如下几类。

表明物体是什么
表明物品的种类
表明谁拥有物品
表达用户的观点
用户相关的标签
用户的任务

Hulu上的标签分类

类型(Genre) 主要表示这个电视剧的类别。
时间(Time) 主要包括电视剧的发布的时间，有时也包括电视剧中事件发生的时间。
人物(People) 主要包括电视剧的导演、演员和剧中重要人物等。
地点(Place) 剧情发生的地点，或者视频拍摄的地点等。
语言(Language) 这部电视剧使用的语言。
奖项(Awards) 这部电视剧获得的相关奖项。
其他(Details) 包含不能归类到上面各类中的其他所有标签。

4.3 基于标签的推荐系统

一个用户标签行为的数据集一般由一个三元组的集合表示，其中记录$(u, i, b)$表示用户$u$给物品$i$打上了标签$b$。当然，用户的真实标签行为数据远远比三元组表示的要复杂，比如用户打标签的时间、用户的属性数据、物品的属性数据等。但是本章为了集中讨论标签数据，只考虑上面定义的三元组形式的数据，即用户的每一次打标签行为都用一个三元组（用户、物品、标签）表示。

本章将采用两个不同的数据集评测基于标签的物品推荐算法。一个是Delicious数据集，另一个是CiteULike数据集。Delicious数据集中包含用户对网页的标签记录。它每一行由4部分组成，即时间、用户ID、网页URL、标签。CiteULike数据集包含用户对论文的标签记录，它每行也由4部分组成，即物品ID、用户ID、时间、标签。

4.3.1 实验设置

本节将数据集随机分成10份。这里分割的键值是用户和物品，不包括标签。也就是说，用户对物品的多个标签记录要么都被分进训练集，要么都被分进测试集，不会一部分在训练集，另一部分在测试集中。然后，我们挑选1份作为测试集，剩下的9份作为训练集，通过学习训练集中的用户标签数据预测测试集上用户会给什么物品打标签。对于用户$u$，令$R(u)$为给用户$u$的长度为$N$的推荐列表，里面包含我们认为用户会打标签的物品。令$T(u)$是测试集中用户$u$实际上打过标签的物品集合。然后，利用准确率(precision)和召回率(recall)评测个性化推荐算法的精度。
将上面的实验进行10次，每次选择不同的测试集，然后将每次实验的准确率和召回率的平均值作为最终的评测结果。

为了全面评测个性化推荐的性能，实验同时评测了推荐结果的覆盖率(coverage)、多样性(diversity)和新颖度。

关于多样性，在第1章中讨论过，多样性的定义取决于相似度的定义。在本章中，实验用物品标签向量的余弦相似度度量物品之间的相似度。对于每个物品$i$，item_tags[i]存储了物品$i$的标签向量，其中item_tags[i][b]是对物品$i$打标签$b$的次数，那么物品$i$和$j$的余弦相似度可以通过如下程序计算。

def CosineSim(item_tags, i, j):
    ret = 0 
    for b,wib in item_tags[i].items():
        if b in item_tags[j]:
            ret += wib * item_tags[j][b] 
    ni = 0 
    nj = 0 
    for b, w in item_tags[i].items():
        ni += w * w 
    for b, w in item_tags[j].items():
        nj += w * w 
    if ret == 0:
        return 0 
    return ret / math.sqrt(ni * nj)

在得到物品之间的相似度度量后，通过如下公式计算一个推荐列表的多样性。
$$
Diversity = 1 - \frac {\sum_{i \in R(u)} \sum_{j \in R(u),j \neq i} \text{Sim(item_tags[i],item_tags[j])}}
{\begin{pmatrix}
\vert R(u) \vert \\
2 \\
\end{pmatrix}}
$$

如果用程序实现，代码如下：

def Diversity(item_tags, recommend_items):
    ret = 0 
    n = 0 
    for i in recommend_items.keys():
        for j in recommend_items.keys():
            if i == j:
                continue 
            ret += CosineSim(item_tags, i, j) 
            n += 1 
    return ret / (n * 1.0)

推荐系统的多样性为所有用户推荐列表多样性的平均值。

至于推荐结果的新颖性，可以简单地用推荐结果的平均热门程度(AveragePopularity)度量。对于物品$i$，定义它的流行度item_pop(i)为给这个物品打过标签的用户数。而对推荐系统，定义它的平均热门度如下：
$$
Average Popularity = \frac {\sum_u \sum_{i \in R(u)} \log(1 + \text{item_pop(i))}}{\sum_u \sum_{i \in R(u)}1}
$$

4.3.2 一个最简单的算法

拿到了用户标签行为数据后，最简单的个性化推荐算法描述如下：

统计每个用户最常用的标签
对于每个标签，统计被打过这个标签次数最多的物品。
对于一个用户，首先找到他常用的标签，然后找到具有这些标签的最热门物品推荐给这个用户。

对于上面的算法，用户 $u$ 对物品 $i$ 的兴趣公式如下：
$$
p(u,i) = \sum_b n_{u,b}n_{b,i}
$$

$B(u)$是用户$u$打过的标签集合，$B(i)$是物品$i$被打过的标签集合，$n_{u,b}$是用户$u$打过标签$b$的次数，$n_{b,i}$是物品$i$被打过标签$b$的次数。本章用SimpleTagBased标记这个算法。

在Python中，遵循如下规定：

用records存储标签数据的三元组，其中records[i] = [user, item, tag]；
用user_tags存储$n_{u,b}$，其中user_tags[u][b] = $n_{u,b}$；
用tags_items存储$n_{b,i}$，其中tags_item[b][i] = $n_{b,i}$ ；

如下程序可以从records中统计出user_tags和tag_items:

def InitStat(records):
    user_tags = dict() 
    tag_items = dict() 
    user_items = dict() 
    for user, item, tag in records.items():
        addValueToMat(user_tags, user, tag, 1)
        addValueToMat(tag_items, tag, item, 1)
    addValueToMat(user_items, user, item, 1)

统计出user_tags和tag_items之后，可以通过如下程序对用户进行个性化推荐：

def Recommend(user):
    recommend_items = dict() 
    tagged_items = user_items[user] 
    for tag, wut in user_tags[user].items():
        for item, wti in tag_items[tag].items():
            #if items have been tagged, do not recommend them 
            if item in tagged_items:
                continue 
            if item not in recommend_items: 
                recommend_items[item] = wut * wti 
            else:
                recommend_items[item] += wut * wti 
    return recommend_items

4.3.3 算法的改进

1.TF-IDF

前面这个公式倾向于给热门标签对应的热门物品很大的权重，因此会造成推荐热门的物品给用户，从而降低推荐结果的新颖性。另外，这个公式利用用户的标签向量对用户兴趣建模，其中每个标签都是用户使用过的标签，而标签的权重是用户使用该标签的次数。这种建模方法的缺点是给热门标签过大的权重，从而不能反应用户个性化的兴趣。这里我们可以借鉴TF-IDF的思想，对这一公式进行改进：
$$
p(u,i) = \sum_b \frac{n_{u,b}}{\log(1+ n_b^{(u)})} n_{b,i}
$$
$n_b^{(u)}$记录了标签$b$被多少个不同的用户使用过。这个算法记为TagBasedTFIDF。
通过TagBasedTFIDF在Delicious和CiteULike两个数据集上的离线实验结果，可知该算法在所有指标上相比SimpleTagBased算法都有提高。

同理，也可以借鉴TF-IDF的思想对热门物品进行惩罚，从而得到如下公式：
$$
p(u,i) = \sum_b \frac{n_{u,b}}{\log(1+n_b^{(u)})}\frac{n_{b,i}}{\log(1+n_i^{(u)})}
$$
$n_i^{(u)}$记录了物品$i$被多少个不同的用户打过标签。这个算法记为TagBasedTFIDF++。
同样通过离线实验证明和TagBasedTFIDF算法相比，除了多样性有所下降，其他指标都有明显提高。这一结果表明，适当惩罚热门标签和热门物品，在增进推荐结果个性化的同时并不会降低推荐结果的离线精度。

2.数据稀疏性

对于新用户或者新物品，$B(u) \cap B(i)$中的标签数量会很少。为了提高推荐的准确率，可能要对标签集合做扩展。
进行标签扩展有很多方法，其中常用的有话题模型(topic model)，不过这里遵循简单的原则介绍一种基于邻域的方法。
标签扩展的本质是对每个标签找到和它相似的标签，也就是计算标签之间的相似度。最简单的相似度可以是同义词。如果有一个同义词词典，就可以根据这个词典进行标签扩展。如果没有这个词典，可以从数据中统计出标签的相似度。
如果认为同一个物品上的不同标签具有某种相似度，那么当两个标签同时出现在很多物品的标签集合中时，就可以认为这两个标签具有较大的相似度。对于标签$b$，令$N(b)$为有标签$b$的物品的集合，$n_{b,i}$为给物品$i$打上标签$b$的用户数，可以通过如下余弦相似度公式计算标签$b$和标签$b’$的相似度：
$$
sim(b,b’) = \frac{\sum_{i \in N(b) \cap N(b’)} n_{b,i} n_{b’,i}}{\sqrt{\sum_{i \in N(b)}n_{b,i}^2 \sum_{i \in N(b’)} n_{b’,i}^2} }
$$
实验表明，进行标签扩展确实能够提高基于标签的物品推荐的准确率和召回率，但可能会稍微降低推荐结果的覆盖率和新颖度。

3.标签清理

不是所有标签都能反应用户的兴趣。同时，标签系统里经常出现词形不同、词义相同的标签。

标签清理的另一个重要意义在于将标签作为推荐解释。如果要把标签呈现给用户，将其作为给用户推荐某一个物品的解释，对标签的质量要求就很高。首先，这些标签不能包含没有意义的停止词或者表示情绪的词，其次这些推荐解释里不能包含很多意义相同的词语。

一般来说有如下标签清理方法：

去除词频很高的停止词；
去除因词根不同造成的同义词，比如recommender system和recommendation system；
去除因分隔符造成的同义词，比如collaborative_filtering和collaborative-filtering；

为了控制标签的质量，很多网站也采用了让用户进行反馈的思想，即让用户告诉系统某个标签是否合适。MovieLens在实验系统中就采用了这种方法。关于这方面的研究可以参考GroupLens 的Shilad Wieland Sen同学的博士论文(参见Shilad Wieland Sen的“ Nurturing Tagging Communities”) 。

4.3.4 基于图的推荐算法

前面讨论的简单算法很容易懂，也容易实现，但缺点是不够系统化和理论化。因此考虑利用图模型做基于标签数据的个性化推荐。

首先，需要将用户打标签的行为表示到一张图上。图是由顶点、边和边上的权重组成的。而在用户标签数据集上，有3种不同的元素，即用户、物品和标签。因此，需要定义3种不同的顶点，即用户顶点、物品顶点和标签顶点。然后，如果我们得到一个表示用户$u$给物品$i$打了标签$b$的用户标签行为$(u,i,b)$，那么最自然的想法就是在图中增加3条边，首先需要在用户u对应的顶点$v(u)$和物品i对应的顶点$v(i)$之间增加一条边（如果这两个顶点已经有边相连，那么就应该将边的权重加1），同理，在$v(u)$和$v(b)$之间需要增加一条边，$v(i)$和$v(b)$之间也需要边相连接。

在定义出用户—物品—标签图后，可以用第2章提到的PersonalRank算法计算所有物品节点相对于当前用户节点在图上的相关性，然后按照相关性从大到小的排序，给用户推荐排名最高的$N$个物品。

用图模型解释前面的简单算法

基于图模型重新思考前面的简单算法。

在那个算法中，用户对物品的兴趣公式如下：
$$
P(i|u) = \sum_b P(i|b)P(b|u)
$$
这个公式假定用户对物品的兴趣通过标签传递，因此这个公式可以通过一个比本节前面介绍的图更简单的图建模（记为SimpleTagGraph）。给定用户标签行为记录$(u,i,b)$，SimpleTagGraph会增加两条有向边，一条由用户节点$v(u)$指向标签节点$v(b)$，另一条由标签节点$v(b)$指向物品节点$v(i)$。从这个定义可以看到，SimpleTagGraph相对于前面提到用户—物品—标签图少了用户节点和物品节点之间的边。
在构建了SimpleTagGraph后，利用前面的PersonalRank算法，令$K = 1$，并给出不同边权重的定义，就等价于前面提出的简单推荐算法。

4.3.5 基于标签的推荐解释

书中这部分首先介绍了豆瓣基于标签的推荐系统，其中豆瓣将推荐结果的可解释性拆分成两部分这个方法值得借鉴，详细内容见书。

GroupLens的研究人员Jesse Vig对基于标签的解释进行了深入研究(参见Jesse Vig、 Shilad Wieland Sen和 John Riedl的“Tagsplanations: Explaining Recommendations Using Tags”（ACM 2009 Article，2009）)。和4.3.2节提出的算法类似，Jesse Vig将用户和物品之间的关系变成了用户对标签的兴趣(tag preference)和标签与物品的相关度(tag relevance)，然后作者用同一种推荐算法给用户推荐物品，但设计了4种标签解释的展示界面。

RelSort 对推荐物品做解释时使用的是用户以前使用过且物品上有的标签，给出了用户对标签的兴趣和标签与物品的相关度，但标签按照和物品的相关度排序。
PreSort 对推荐物品做解释时使用的是用户以前使用过且物品上有的标签，给出了用户对标签的兴趣和标签与物品的相关度，但标签按照用户的兴趣程度排序。
RelOnly 对推荐物品做解释时使用的是用户以前使用过且物品上有的标签，给出了标签与物品的相关度，且标签按照和物品的相关度排序。
PreOnly 对推荐物品做解释时使用的是用户以前使用过且物品上有的标签，给出了用户对标签的兴趣程度，且标签按照用户的兴趣程度排序。

然后，作者对用户设计了3种调查问卷。首先是关于推荐解释的调查问卷，作者问了如下3个问题：

推荐解释帮助我理解这部电影为什么会被推荐给我：对于这个问题用户认为 RelSort> PrefOnly>=PrefSort>RelOnly。
推荐解释帮助我判定是否喜欢推荐的电影：对于这个问题用户认为 RelSort>PrefSort> PrefOnly>RelOnly。
推荐解释帮助我判定观看这部电影是否符合我现在的兴趣：对于这个问题用户认为RelSort>PrefSort>RelOnly >PrefOnly。

然后，作者调查了用户对不同类型标签的看法。作者将标签分为主观类（比如对电影的看法）和客观类（比如对电影内容的描述）。作者对每种类型的标签同样问了上面3个问题。

这个标签帮助我理解这部电影为什么会被推荐给我：用户认为客观类标签优于主观类标签。
这个标签帮助我判定是否喜欢推荐的电影：用户认为客观类标签优于主观类标签。
这个标签帮助我判定观看这部电影是否符合我现在的兴趣：用户认为客观类标签优于主观类标签。

从上面的结果可以发现，客观事实类的标签优于主观感受类标签。
最后，作者询问了用户对4种不同推荐解释界面的总体满意度，结果显示PrefOnly > RelSort > PrefSort > RelOnly。

总结问卷调查的结果，作者得出了以下结论：

用户对标签的兴趣对帮助用户理解为什么给他推荐某个物品更有帮助；
用户对标签的兴趣和物品标签相关度对于帮助用户判定自己是否喜欢被推荐物品具有同样的作用；
物品标签相关度对于帮助用户判定被推荐物品是否符合他当前的兴趣更有帮助；
客观事实类标签相比主观感受类标签对用户更有作用。

4.4 给用户推荐标签

4.4.1 为什么要给用户推荐标签

一般认为，给用户推荐标签有以下好处。

方便用户输入标签 从键盘输入标签会增加用户打标签的难度，推荐标签则可以降低难度，从而提高用户打标签的参与度。
提高标签质量 同一个语义不同的用户可能用不同的词语来表示。这些同义词会使标签的词表变得很庞大，而且会使计算相似度不太准确。而使用推荐标签时，可以对词表进行选择，首先保证词表不出现太多的同义词，同时保证出现的词都是一些比较热门的、有代表性的词。

4.4.2 如何给用户推荐标签

推荐标签的方法中比较简单的有4种。
第0种方法(最简单的方法)就是给用户$u$推荐整个系统里最热门的标签（这里将这个算法称为PopularTags）
令tags[b]为标签$b$的热门程度，算法的实验方法如下：

1 2	def RecommendPopularTags(user,item, tags, N): return sorted(tags.items(), key=itemgetter(1), reverse=True)[0:N]

第1种方法就是给用户$u$推荐物品$i$上最热门的标签（这里将这个算法称为ItemPopularTags）。
令item_tags[i][b]为物品$i$被打上标签$b$的次数，这个算法的实现具体如下所示：

1 2	def RecommendItemPopularTags(user,item, item_tags, N): return sorted(item_tags[item].items(), key=itemgetter(1), reverse=True)[0:N]

第2种方法是给用户$u$推荐他自己经常使用的标签（这里将这个算法称为UserPopularTags）。
令user_tags[u][b]为用户$u$使用标签$b$的次数，这个算法的实现如下所示：

1 2	def RecommendUserPopularTags(user,item, user_tags, N): return sorted(user_tags[user].items(), key=itemgetter(1), reverse=True)[0:N]

第3种算法是前面两种的融合（这里记为HybridPopularTags），该方法通过一个系数(线性融合系数)将上面的推荐结果线性加权，然后生成最终的推荐结果。这个算法的实现代码如下：

def RecommendHybridPopularTags(user,item, user_tags, item_tags, alpha, N):
    max_user_tag_weight = max(user_tags[user].values()) 
    for tag, weight in user_tags[user].items():
        ret[tag] = (1 – alpha) * weight / max_user_tag_weight

    max_item_tag_weight = max(item_tags[item].values()) 
    for tag, weight in item_tags[item].items():
        if tag not in ret:
            ret[tag] = alpha * weight / max_item_tag_weight
        else:
            ret[tag] += alpha * weight / max_item_tag_weight 	
    return sorted(ret[user].items(), key=itemgetter(1), reverse=True)[0:N]

注意在上面的实现中，在将两个列表线性相加时都将两个列表按最大值做了归一化，这样的好处是便于控制两个列表对最终结果的影响，而不至于因为物品非常热门而淹没用户对推荐结果的影响，或者因为用户非常活跃而淹没物品对推荐结果的影响。

4.4.3 实验设置

和前面的实验一样，用同样的方法将数据集按照9∶1分成训练集和测试集，然后通过训练集学习用户标注的模型。需要注意的是，这里切分数据集不再是以user、item为主键，而是以user、item、tag为主键。为了更好的理解如何切分数据集，请参考下面的Python代码：

def SplitData(records, train, test):
    for user,item, tag in records:
        if random.randint(1,10) == 1: 
            test.append([user,item,tag])
        else: 
            train.append([user,item,tag]) 
    return [train, test]

对于测试集中的每一个用户物品对$(u,i)$，我们都可以推荐$N$个标签给用户$u$作参考。令$R(u,i)$为给用户$u$推荐的应该在物品$i$上打的标签集合，令$T(u,i)$为用户$u$实际给物品$i$打的标签的集合，然后可以利用准确率和召回率评测标签推荐的精度。

实验结果表明，ItemPopularTags具有最好的准确率和召回率。
在$α$=0.8($\alpha$是线性融合稀疏)的时候，HybridPopularTags取得了最好的准确度。而且这个精度超过了单独的ItemPopularTags和UserPopularTags算法的精度。考虑到近70%的精度已经很高了，因此很多应用在给用户推荐标签时会直接给出用户最常用的标签，以及物品最经常被打的标签。

不过，前面提到的基于统计用户常用标签和物品常用标签的算法有一个缺点，就是对新用户或者不热门的物品很难有推荐结果。解决这一问题有两个思路。
第一个思路是从物品的内容数据中抽取关键词作为标签。这方面的研究很多，特别是在上下文广告领域(参见Wen-tau Yih、Joshua Goodman和 Vitor R. Carvalho的“Finding Advertising Keywords on Web Pages”（ACM 2006 Article，2006）)。本书3.4节也介绍了生成关键词向量的一些方法。
第二个思路是针对有结果，但结果不太多的情况。可以做一些关键词扩展，加入一些与现有结果相关的标签。实现标签扩展的关键就是计算标签之间的相似度。关于这一点， 4.3.3节已经进行了深入探讨。

4.4.4 基于图的标签推荐算法

图模型同样可以用于标签推荐。在根据用户打标签的行为生成图之后，可以利用PersonalRank算法进行排名。但这次遇到的问题和之前不同。这次的问题是，当用户$u$遇到物品$i$时，会给物品$i$打什么样的标签。因此，可以重新定义顶点的启动概率，如下所示：
$$
r_{v(k)} =
\begin{cases}
\alpha & {(v(k)= v(u))} \\
1 - \alpha & (v(k) = v(i)) \\
0 & \text{(其他)}
\end{cases}
$$
只有用户$u$和物品$i$对应的顶点有非0的启动概率，而其他顶点的启动概率都为0。在上面的定义中，$v(u)$和$v(i)$的启动概率并不相同，$v(u)$的启动概率是$\alpha$，而$v(i)$的启动概率是$1-\alpha$。参数$\alpha$可以通过离线实验选择。

4.5 扩展阅读

本章主要讨论了UGC标签在推荐系统中的应用。标签作为描述语义的重要媒介，无论是对于描述用户兴趣还是表示物品的内容都有很重要的意义。标签在推荐系统中的应用主要集中在两个问题上，一个是如何利用用户打标签的行为给用户推荐物品，另一个是如何给用户推荐标签。本章在深入分析用户标签行为的基础上对这两个问题进行了深入探讨。

关于标签的问题，最近几年在学术界获得了广泛关注。ECML/PKDD在2008年曾经推出过基于标签的推荐系统比赛(1)。在这些研究中涌现了很多新的方法，比如张量分解(2)(tensor factorization)、基于LDA的算法(3)、基于图的算法(4)等。不过这些算法很多具有较高的复杂度，在实际系统中应用起来还有很多实际的困难需要解决。
GroupLens的研究人员给MovieLens系统做了很多标签方面的工作。Shilad Sen在论文(5)中研究了如何利用标签联系用户和物品并给用户进行个性化电影推荐。Jesse Vig在论文(6)中研究了如何利用标签进行推荐解释，他将用户和物品之间的关系转化为用户对标签的兴趣（tag preference）以及标签和物品的相关度（tag relevance）两种因素。同时他们研究了如何对标签进行清理(7)，以及如何选择合适的标签进行解释。

(1):比赛介绍见 http://www.kde.cs.uni-kassel.de/ws/rsdc08/program.html。
(2):参见Panagiotis Symeonidis、Alexandros Nanopoulos和Yannis Manolopoulos的“Tag recommendations based on tensor dimensionality reduction”（ACM 2008 Article，2008）。
(3):参见Ralf Krestel、 Peter Fankhauser和Wolfgang Nejdl的“Latent dirichlet allocation for tag recommendation”（ACM 2009 Article，2009）。
(4):参见Andreas Hotho、 Robert Jäschke、 Christoph Schmitz和Gerd Stumme的“Folkrank: A ranking algorithm for folksonomies”（Proc. FGIR 2006，2006）。
(5):参见Shilad Wieland Sen、 Jesse Vig和John Riedl的“Tagommenders: Connecting Users to Items through Tags”（ACM 2009 Article，2009）。
(6):参见Jesse Vig、Shilad Wieland Sen和John Riedl的“Tagsplanations: Explaining Recommendations Using Tags”（ACM 2009 Article，2009）。
(7):参见Shilad Wieland Sen、F. Maxwell Harper、Adam LaPitz和John Riedl的“The quest for quality tags”（ACM 2007 Article，2007）。

第4章 利用用户标签数据