《推荐系统实践》笔记(续)

Yeolar   2013-10-06 16:05  

接前一篇,本文是后半部分。写笔记的过程中,又看了看网上推荐的其他书,可以接着看《推荐系统》、《Recommender Systems Handbook》这两本,还有《集体智慧编程》,是数据挖掘的编程实践类型的书,评价很高。

4 利用用户标签数据

除了上一篇中的基于用户和基于物品的推荐算法,还有一种通过一些特征联系用户和物品的形式。特征可能是物品的属性、隐语义向量和标签等。标签可以分为作者或专家打的标签和用户打的标签(UGC的标签)。UGC标签是联系用户和物品的一种重要方式,既表明了用户的兴趣,又描述了物品的语义。

UGC标签的应用在Web 2.0网站中很常见,如:Delicious、CiteULike、Last.fm、豆瓣、Hulu等。

4.1 用户打标签

因为标签的特点,它很适合用到推荐系统中。

标签和用户、物品类似,它的流行度分布也满足长尾分布。

用户打的标签有各种类型,总体来说,一些是和物品相关的标签,类似于关键词和分类;另一些是和用户相关的标签,比如用户的信息、看法、状态等。

4.2 基于标签的推荐

考虑到标签后,用户的标签行为数据可以表示为 \((u,i,b)\) ,表示用户 \(u\) 给物品 \(i\) 打了个标签 \(b\)

在设计推荐算法时,可以把标签近似于用户的反馈或物品的关键词来考虑。

对于评测指标,如果实际的标签可以视作为用户的正反馈,那么准确率和召回率中的 \(T(u)\) 表示测试集上用户打过标签的物品集合。物品的相似度可以用它们的标签向量的相似度来度量。

一个简单的想法是通过计算用户的标签向量和物品的标签向量来得到用户对物品的兴趣

\begin{equation*} p(u,i) = \sum_b N(u,b)N(i,b) \end{equation*}

上面的方法同样有热门标签和热门物品权重很大的问题,采用和IIF、IUF和TF-IDF类似的想法改进

\begin{equation*} p(u,i) = \sum_b \frac{N(u,b)}{\log(1+N_u(b))}\frac{N(i,b)}{\log(1+N_u(i))} \end{equation*}

\(N(u,b)\) 表示用户 \(u\) 打过标签 \(b\) 的次数, \(N(i,b)\) 表示物品 \(i\) 被打过标签 \(b\) 的次数, \(N_u(b)\) 表示用过标签 \(b\) 的用户数, \(N_u(i)\) 表示给物品 \(i\) 打过标签的用户数。

对于新用户或新物品,标签数会很少,为提高推荐的准确率,可能需要对标签集合做扩展。常用的扩展方法有话题模型等,作者介绍了一种基于邻域的方法:标签扩展也就是找到相似的标签,即计算标签的相似度,可以从数据中采用余弦公式计算标签的相似度。

使用标签的一个问题是不是所有标签都反映了用户的兴趣,另外将标签作为推荐解释也需要清理标签。常用的标签清理方法有:

  • 去除词频很高的停止词
  • 去除因词根不同造成的同义词
  • 去除因分隔符造成的同义词

这里也可以加入用户反馈的途径。

也可以利用图模型来做基于标签的个性化推荐。方法和二分图的推荐模型类似,不过这里需要用户、物品和标签三种顶点。同样可以用PersonalRank算法计算所有物品顶点相对于当前用户顶点在图上的相关性,排序得到推荐列表。

基于标签的推荐的最大好处是可以利用标签做推荐解释。一些网站还使用了标签云表示用户的兴趣分布,标签的尺寸越大,表示用户对这个标签相关的物品越感兴趣。

分析表明:

  • 用户对标签的兴趣能帮助用户理解为什么给他推荐某个物品
  • 物品与标签的相关度能帮助用户判定被推荐物品是否符合他的兴趣
  • 用户对标签的兴趣和物品与标签的相关度对于用户判定有同样的作用
  • 客观事实类标签比主观感受类标签作用更大

4.3 给用户推荐标签

标签系统会希望用户能够给物品打上优质的标签,这样有利于标签系统的良性循环。给用户推荐标签的好处是方便用户打标签,同时提高标签质量,减少同义词。

给用户推荐标签的方法可以是:给用户推荐物品 \(i\) 的最热门标签;给用户推荐他最常用的标签;或者前两种方法的结合。以最后一种为例:

\begin{equation*} p_{ui}(b) = \alpha\frac{w_{u,b}}{\max\limits_b w_{u,b}}+(1-\alpha)\frac{w_{i,b}}{\max\limits_b w_{i,b}} \end{equation*}

上面的方法同样有类似于冷启动的问题,解决的办法可以考虑用抽取关键词(没有标签)和关键词扩展(有标签但是很少)。

图模型同样可以用于标签推荐。在生成用户-物品-标签图后,可以用PersonalRank算法生成推荐结果。但这里和之前不同,可以重新定义顶点的启动概率为

\begin{equation*} r_{v} = \left\{\begin{array}{11} \alpha & v = v_u \\ 1-\alpha & v = v_i \\ 0 & others\end{array}\right. \end{equation*}

5 利用上下文信息

5.1 时间上下文

时间上下文表现在:用户的兴趣是变化的,物品是有生命周期的,季节效应。时效性强的物品,平均在线天数短。

考虑时间信息后,推荐系统就变为一个时变的系统,可以用 \((u,i,t)\) 表示用户 \(u\) 在时刻 \(t\) 对物品 \(i\) 的行为。

推荐系统的实时性要求:

  • 在每个用户访问推荐系统时,根据用户在此之前的行为实时计算推荐列表。
  • 推荐算法需要平衡考虑用户的近期行为和长期行为,保证对用户兴趣预测的延续性。

推荐系统的时间多样性为推荐结果的变化程度,时间多样性高能够提高用户满意度。

加入时间效应后,最简单的非个性化推荐算法是推荐最近最热门物品。给定时间 \(T\) ,物品最近的流行度 \(n_i(T)\) 定义为

\begin{equation*} n_i(T) = \sum_{(u,i,t),t<T}\frac{1}{1+\alpha(T-t)} \end{equation*}

5.1.1 时间上下文相关的ItemCF算法

根据时间效应,

  • 用户在相隔很短的时间内喜欢的物品具有更高的相似度;
  • 用户近期行为比很久以前的行为更能体现用户现在的兴趣。

由ItemCF算法,考虑到时间效应后(未使用IUF做修正)

\begin{equation*} w_{ij} = \frac{\sum_{u\in{N(i)\cap N(j)}} f(|t_{ui}-t_{uj}|)}{\sqrt{|N(i)||N(j)|}} \end{equation*}

\(f\) 为时间衰减函数,用户对物品 \(i\)\(j\) 产生行为的时间距离越远,则 \(f(|t_{ui}-t_{uj}|)\) 越小。取

\begin{equation*} f(\Delta) = \frac{1}{1+\alpha\Delta} \end{equation*}

calcItemSimilarity 第9行改为

1 w[i][j] = w[i].get(j, 0) + 1 / (1 + alpha * abs(items[i] - items[j]))

另外,类似地

\begin{equation*} p(u,i) = \sum_{j\in{S(i,K)\cap N(u)}} \frac{1}{1+\beta|t_0-t_{uj}|}w_{ij}r_{uj} \end{equation*}

其中 \(t_0\) 为当前时间, \(t_uj\) 越靠近 \(t_0\) ,和物品 \(j\) 相似的物品就会更受推荐。

5.1.2 时间上下文相关的UserCF算法

和ItemCF算法的思路类似,

  • 用户兴趣的相似度在间隔较短的时间较高;
  • 给用户推荐和他兴趣相似的用户最近喜欢的物品。

由UserCF算法,考虑时间效应后(未使用IIF做修正)

\begin{equation*} w_{uv} = \frac{\sum_{i\in{N(u)\cap N(v)}} \frac{1}{1+\alpha|t_{ui}-t_{vi}|}}{\sqrt{|N(u)||N(v)|}} \end{equation*}
\begin{equation*} p(u,i) = \sum_{v\in{S(u,K)\cap N(i)}} \frac{1}{1+\beta|t_0-t_{vi}|}w_{uv}r_{vi} \end{equation*}

5.2 地点上下文

不同地区的用户兴趣会不同,用户在不同的地方,兴趣也会变化。研究表明,用户具有兴趣本地化和活动本地化的特征。

可以从3种数据形式来分析地点上下文的影响:

  • (用户, 用户位置, 物品, 评分)
  • (用户, 物品, 物品位置, 评分)
  • (用户, 用户位置, 物品, 物品位置, 评分)

对于第一种,可以把用户按地理位置做树状划分,对每一级树节点生成推荐列表,最终对各级推荐结果加权(金字塔模型)。

对于第二种,可以先计算忽略物品位置的 \(p(u,i)\) ,然后减去物品位置对用户的代价。

实验表明,考虑了用户位置的算法要优于ItemCF算法。

7 推荐系统实例

作者基于他在Hulu使用的架构总结了基于物品的推荐的推荐系统架构。

推荐系统在网站中所处的位置如下图所示。用户行为存储系统将日志系统中的行为日志提取出并存储起来,推荐系统以这些行为日志为输入,把推荐结果提供给UI做展示。

/media/note/2013/10/06/recommend-system-2/fig1.png

推荐系统

用户行为数据可以分为匿名的如浏览、搜索等,非匿名的评论、购买等。按数据规模和是否需要实时存取,数据会被保存到缓存、数据库或者分布式文件系统中。

以基于特征的推荐系统为例,推荐系统一般要考虑多种特征,可以由多个推荐引擎组成,每个引擎负责一类特征或一种任务,推荐系统只需要将推荐引擎的结果合并、排序。这样做的好处是:

  • 可以方便地增加或删除推荐引擎,以不同的推荐引擎组合来决定推荐结果。
  • 可以实现推荐引擎级别的用户反馈。推荐引擎对应于推荐策略,不同的用户可能喜欢不同的推荐策略,通过分析,可以给不同的用户不同的推荐引擎权重。

下图是推荐引擎的架构,主要包括三部分:

  • 生成用户特征向量的部分
  • 将用户特征向量通过特征-物品矩阵转化为初始推荐列表的部分
  • 对初始推荐列表做过滤、排名的部分。
/media/note/2013/10/06/recommend-system-2/fig2.png

推荐引擎架构

  1. 生成用户特征向量

    用户特征可以分成用户注册时填写的人口统计学特征和从用户行为中计算得到的特征。特征向量由特征和它的权重组成。在利用用户行为计算特征向量时,需要考虑:

    • 用户行为的种类。有些行为比其他的行为更重要,一般用户付出代价越大的行为权重应该更高。
    • 用户行为产生的时间。一般地用户近期的行为权重应该更高。
    • 用户行为的次数。对同一物品可能有多次行为,对应的物品的特征权重应该更高。
    • 物品的热门程度。热门物品往往不能代表用户的个性,因此应该加重不热门物品的特征权重。
  2. 特征-物品相关推荐

    相关推荐使用的特征-物品相关表一般不止一个,不同的算法、不同的用户行为数据会有不同的相关表,系统会根据配置和权重叠加相关表,直接使用叠加后的相关表。

    如果需要在一个较小的候选物品集合中给用户推荐物品,可以考虑用候选物品集合先做过滤,避免热门度带来的影响。

  3. 过滤

    过滤模块会过滤掉:

    • 用户已经产生过行为的物品
    • 候选物品以外的物品
    • 某些质量很差的物品,比如以评分为依据
  4. 排名

    排名模块一般需要包括很多不同的子模块:

    • 新颖性:目的是给用户尽量推荐他不知道的、长尾中的物品。一般要对热门物品降权,对ItemCF算法,要对 \(w_{ij}\)\(r_{uj}\) 降权。
    • 多样性:很多时候需要增加多样性来提高覆盖率。可以通过分类,或者让推荐理由(来自特征)尽量不同。
    • 时间多样性:为了保证用户能看到不同的推荐结果。一方面要保证推荐系统的实时性;另外对于没有新行为的用户,也要记录他看到的推荐结果,并给这些物品降权。
    • 用户反馈:这是排名模块最重要的部分,主要通过分析用户之前和推荐结果的交互日志,预测用户会对什么样的推荐结果感兴趣。如果关注点是点击率,可以使用点击模型。

9 最后

Strand研究人员总结的10条设计推荐系统的经验:

  1. 确定你真的需要推荐系统
  2. 确定商业目标和用户满意度之间的关系
  3. 选择合适的开发人员
  4. 忘记冷启动的问题
  5. 平衡数据和算法之间的关系
  6. 找到相关物品容易,但如何展现给用户则很困难
  7. 不要浪费时间计算相似兴趣的用户,可以直接利用社会网络数据
  8. 需要不断提升算法的扩展性
  9. 选择合适的用户反馈方式
  10. 设计合理的评测系统,时刻关注推荐系统各方面的性能

http://www.yeolar.com/note/2013/10/06/recommend-system-2/

http://www.yeolar.com/note/2013/10/06/recommend-system-2/