一文入门推荐系统——推荐系统实践读书笔记

一文入门推荐系统——推荐系统实践读书笔记1.推荐系统1.1.什么是推荐系统1.2.推荐系统评测1.2.1.实验方法1.2.2.评判指标1.2.3.评判维度2.数据来源2.1.用户行为数据2.2.用户标签数据2.3.上下文信息2.3.1.时间上下文信息2.3.2.地点上下文信息2.4.社交网络数据3.通用推荐模型3.1.协同过滤推荐3.1.1.基于邻域的模型3.1.2.隐语义模型3.1.3.基于图的模型3.2.基于内容的推荐3.3.基于关联规则的推荐3.4.基于知识的

《推荐系统实践》读书笔记

1. 推荐系统

1.1. 什么是推荐系统

(1)推荐系统的定义
推荐系统(Recommendation System, RS)是一种自动联系用户和物品的工具,它能够帮助用户在信息过载的环境中发现令他们感兴趣的信息。它通常由前台的展示页面、后台的日志系统、推荐算法系统三个部分组成。

(2)为什么需要推荐系统
随着互联网上的数据越来越多,各大应用及平台坐拥海量信息,但用户却难以找到真正对自己有用的信息,用户面对庞大的数据变得毫无头绪。

目前有三大方法可以解决信息超载的问题:分类目录、搜索引擎和推荐系统:

  • 分类目录
    分类目录是将信息分门别类,从而方便用户根据类别进行查找。例如:优设导航百度更多 等门户网站。但分类目录只适合用在内容少而精的网站上,大多数分类目录网站只能涵盖少数热门信息,应用场景有限。
  • 搜索引擎
    用户通过在搜索引擎上输入关键字,查找自己需要的信息。例如:搜狗Bing 等搜索引擎。但是,用户必须主动提供准确的关键词,才可能找到需要的信息。
  • 推荐系统
    推荐系统通过分析用户的历史行为,对用户的兴趣进行建模,从而主动给用户推荐可能满足他们需求的信息,该方法能够很好的发掘长尾信息。

我们可以看到,推荐系统相对于分类目录和搜索引擎,在某些方面有着不可替代的优势。通常认为,当一个系统满足以下两个条件时,就可以考虑应用推荐系统:

  1. 存在信息过载(用户难以找到想要的内容);
  2. 用户大多数时候没有明确的需求。

1.2. 推荐系统评测

一个完整的推荐系统包括三个参与方:

  • 用户
  • 网站(平台,负责搭载推荐系统)
  • 内容提供方

在评测一个推荐系统时,需要考虑上述三方的利益,一个好的推荐系统是能够令三方共赢的系统。

1.2.1. 实验方法

一般来说,一个新的推荐算法最终上线,需要通过3个实验。

  • 首先,通过离线实验证明它在很多离线指标上优于现有的算法;
  • 其次,通过用户调查确定用户满意度不低于现有的算法;
  • 最后,通过在线AB测试确定它在特定的指标上优于现有的算法;

(1)离线实验 Offline Experiment
离线实验的方法的步骤如下:

  • 通过日志系统获得用户行为数据,并生成一个标准数据集;
  • 将数据集分成训练集和测试集;
  • 在训练集上训练用户兴趣模型,在测试集上进行预测;
  • 通过事先定义的离线指标,评测算法在测试集上的预测结果。

从以上步骤看出,离线实验的都是在标准数据集上完成的。这意味着,它不需要一个实际的系统作为支撑,只需要有一个模拟环境即可。

离线实验的优缺点:

优点 缺点
不需要有对实际系统的控制权 无法计算商业上关心的指标
不需要用户参与实验 离线实验的指标和商业指标存在差距
速度快,可以测试大量算法

(2)用户调查 User Study
用户调查由真实的用户在需要测试的推荐系统上完成某些任务。在他们完成这些任务时,观察和记录他们的行为,并让他们回答一些问题。最后通过分析他们的行为和答案,了解推荐系统的性能。

用户调查的优缺点:

优点 缺点
可以获得用户主观感受的指标 招募测试用户代价较大
风险低,出错后容易弥补 无法组织大规模的测试用户,统计意义不足
双盲实验设计困难,导致收集的测试指标无法在真实环境下重现

(3)在线实验 Online Experiment
在线实验是指将系统上线做AB测试,把它和旧算法进行比较。AB测试通过一定的规则将用户随机分成几组,对不同组的用户采用不同的算法,然后通过统计不同组的评测指标,比较不同算法的好坏。

AB测试的优缺点:

优点 缺点
可以准确地获得不同算法的实际性能指标和商业上关注的指标 周期较长,必须进行长期的实验才能得到可靠的结果

大型网站做AB测试,可能会因为不同团队同时进行各种测试对结果造成干扰,所以切分流量是AB测试中的关键。不同的测试层以及控制这些层的团队,需要从一个统一的流量入口获得自己AB测试的流量,而不同层之间的流量应该是正交的。关于分层实验和流量正交的知识可以参考这篇博客:黄一能:什么是科学的AB测试?谈谈分层实验和流量正交
在这里插入图片描述

1.2.2. 评判指标

评测指标用于评测推荐系统的性能,有些可以定量计算,如预测准确度、覆盖率、多样性、实时性;有些只能定性描述,如用户满意度、新颖性、惊喜度、信任度、健壮性和商业目标。

有了这些指标,就可以根据需要对推荐系统进行优化,通常的优化目标是在给定覆盖率、多样性、新颖性等限制条件下,尽量提高预测准确度。

离线实验 问卷调查 在线实验
用户满意度 ×
预测准确度 ×
覆盖率
多样性
新颖性
惊喜度 × ×

下面我们分别介绍一下这几种评测指标。

以下指标在博客:推荐系统评价指标及代码实现 中有较好的实现以及图表展示。

(1) 用户满意度
用户满意度是评测推荐系统的重要指标,无法离线计算,只能通过用户调查或者在线实验获得。

  • 调查问卷的设计需要考虑周全,用户才能针对特定问题给出准确的回答;
  • 在线系统中用户的满意度通过统计用户行为得到。一般情况,可以用用户点击率、停留时间、转化率等指标度量用户的满意度。

(2) 预测准确度

预测准确度是度量一个推荐系统或其中推荐算法预测用户行为的能力。 是推荐系统最重要的离线评测指标。大致可从“评分预测”和“Top-N推荐”两个方面进行评测。

评分预测
预测评分的准确度,衡量的是算法预测的评分与用户的实际评分的贴近程度,一般通过以下指标度量:

设测试集 T T T 中有用户 u u u 和物品 i i i,用 r u i r_{ui} rui 表示用户 u u u 对物品 i i i 的实际评分; r ^ u i \hat{r}_{ui} r^ui 表示推荐算法给出的预测评分。则

  • 平均绝对误差(MAE) M A E = ∑ ( u , i ) ∈ T ∣ r u i − r u i ′ ∣ ∣ T ∣ MAE=\frac{\sum_{(u,i)\in T}|r_{ui}-r_{ui}’|}{|T|} MAE=T(u,i)Truirui
# records[i] = [u,i,rui,pui] # rui是用户u对物品i的实际评分,pui是用户u对物品i的预测评分
def mae(records):
    """计算平均绝对误差"""
    return math.sqrt(sum([abs(rui-pui) for u,i,rui,pui in records])/len(records))
  • 均方根误差(RMSE) R M S E = ∑ ( u , i ) ∈ T ( r u i − r ^ u i ) 2 ∣ T ∣ RMSE=\sqrt{\frac{\sum_{(u,i)\in T}(r_{ui}-\hat{r}_{ui})^2}{|T|}} RMSE=T(u,i)T(ruir^ui)2
    一般而言,RMSE的误差会比MAE小
# records[i] = [u,i,rui,pui] # rui是用户u对物品i的实际评分,pui是用户u对物品i的预测评分
def rmse(records):
    """计算均方根误差"""
    return math.sqrt(sum([(rui-pui)*(rui-pui) for u,i,rui,pui in records])/len(records))

Top-N推荐
如果推荐服务会给用户提供个性化的推荐列表,那么这种推荐就叫做Top-N推荐。

Top-N推荐的预测准确率,一般通过3个指标度量:

R ( u ) R(u) R(u) 是根据用户在训练集上的行为提供给用户的推荐列表, T ( u ) T(u) T(u) 是用户在测试集上的实际行为列表。

  • 命中率 (Hits Ratio) H R = 1 ∣ U ∣ ∑ u ∈ U h i t s ( u ) HR=\frac{1}{|U|}\sum_{u\in U}hits(u) HR=U1uUhits(u)其中, h i t s ( i ) hits(i) hits(i)表示第 i i i个用户访问的值是否在推荐列表中,是则为1,否则为0; N N N表示用户的总数量。
  • 准确率(Precision) P r e c i s i o n = ∑ u ∈ U ∣ R ( u ) ∩ T ( u ) ∣ ∑ u ∈ U ∣ R ( u ) ∣ Precision=\frac{\sum_{u\in U}|R(u)\cap T(u)|}{\sum_{u\in U}|R(u)|} Precision=uUR(u)uUR(u)T(u)
  • 召回率(Recall) R e c a l l = ∑ u ∈ U ∣ R ( u ) ∩ T ( u ) ∣ ∑ u ∈ U ∣ T ( u ) ∣ Recall=\frac{\sum_{u\in U}|R(u)\cap T(u)|}{\sum_{u\in U}|T(u)|} Recall=uUT(u)uUR(u)T(u)
def HR_precision_recall(test, N):
    """ 计算命中率、准确率和召回率,这里是包括了推荐和计算HR、precision、recall两个步骤,注意取舍 test: 测试集 N: 推荐列表长度 """
    hit = 0
    n_recall = 0
    n_precision = 0
    n_user = 0

    for user, items in test.items():
        rank = Recommend(user, N) # 进行推荐
        hit += len(rank & itmes) # 计算hit数,即HR
        n_user += 1
        n_precision += N # 计算precision
        n_recall += len(items) # 计算recall
        
    return [hit/(1.*n_use), hit/(1.*n_precision, hit/(1.*n_recall))]

Top-N推荐由于其个性化特性突出,因此相对于评分预测更符合实际的应用需求。

(3) 覆盖率
覆盖率(Coverage)是描述一个推荐系统对物品长尾的发掘能力。覆盖率最简单的定义是:推荐系统能够推荐出来的物品占总物品集合的比例。

假设系统的用户集合为 U U U,总物品集合为 I I I,推荐系统给每个用户推荐一个长度为 N N N 的物品推荐列表 R ( u ) R(u) R(u),覆盖率公式表达为: C o v e r a g e = ⋃ u ∈ U R ( u ) ∣ I ∣ Coverage=\frac{\bigcup_{u\in U}R(u)}{|I|} Coverage=IuUR(u)

覆盖率是内容提供者关心的指标,覆盖率为100%的推荐系统可以将每个物品都至少推荐给一个用户。

除了利用推荐物品的占比来定义覆盖率,还可以通过研究物品在推荐列表中出现的次数分布来描述推荐系统的挖掘长尾的能力。如果分布比较平,说明推荐系统的覆盖率很高;如果分布陡峭,说明分布系统的覆盖率较低。

信息论和经济学中有两个著名指标,可以定义覆盖率:

  • 信息熵 H = − ∑ i = 1 n p ( i ) log ⁡ p ( i ) H=-\sum_{i=1}^{n}p(i)\log p(i) H=i=1np(i)logp(i)其中 p ( i ) p(i) p(i)是物品 i i i的流行度除以所有物品流行度之和;
  • 基尼系数(Gini Index) G = 1 n − 1 ∑ j = 1 n ( 2 j − n − 1 ) p ( i j ) G=\frac{1}{n-1}\sum_{j=1}^{n}(2j-n-1)p(i_j) G=n11j=1n(2jn1)p(ij)其中, i j i_j ij 是按照物品流行度 p p p 从小到大排序的物品列表中第 j j j 个物品。

基尼系数的计算原理:首先,我们将物品按照热门程度从低到高排列,那么下图中的黑色曲线表示最不热门的 x % x\% x% 物品的总流行度占系统的比例 y % y\% y% 。这条曲线肯定是在 y = x y=x y=x 曲线之下的,而且和 y = x y=x y=x 曲线相交在(0,0)和(1,1)。
在这里插入图片描述
S A S_A SA A A A 的面积, S B S_B SB B B B 的面积,那么基尼系数的形象定义就是 S A / ( S A + S B ) S_A/(S_A+S_B) SA/(SA+SB),从定义可知,基尼系数属于区间 [ 0 , 1 ] [0,1] [0,1]
如果系统的流行度很平均,那么 S A S_A SA 就会很小,从而基尼系数很小。如果系统物品流行度分配很不均匀,那么 S A S_A SA 就会很大,从而基尼系数也会很大。

from operator import itemgetter
def gini_index(p):
    """计算基尼系数 p是一个字典, 格式:{item_id1:pop1, item_id2:pop2, ...}, 即{物品1:流行度1, 物品2:流行度2, ...} """
    p_list = list(p.values())
    cum = np.cumsum(sorted(np.append(p_list, 0)))
    sum = cum[-1]
    x = np.array(range(len(cum))) / len(p_list)
    y = cum / sum
    B = np.trapz(y, x=x)
    A = 0.5 - B
    G = A / (A + B)
    return G

(4) 多样性
为了满足用户广泛的兴趣,推荐列表需要能够覆盖用户不同的兴趣领域,即需要具有多样性。

多样性描述了推荐列表中物品之间的不相似性。假设 s ( i , j ) ∈ [ 0 , 1 ] s(i,j)\in [0,1] s(i,j)[0,1] 定义了物品 i i i j j j 之间的相似度,那么用户 u u u的推荐列表 R ( u ) R(u) R(u) 的多样性定义如下: D i v e r s i t y = 1 − ∑ i , j ∈ R ( u ) , i ≠ j s ( i , j ) 1 2 ∣ R ( u ) ∣ ( ∣ R ( u ) ∣ − 1 ) Diversity=1-\frac{\sum_{i,j\in R(u),i\neq j}s(i,j)}{\frac{1}{2}|R(u)|(|R(u)|-1)} Diversity=121R(u)(R(u)1)i,jR(u),i=js(i,j)

推荐系统整体多样性可以定义为所有用户推荐列表多样性的均值: D i v e r s i t y = 1 ∣ U ∣ ∑ u ∈ U D i v e r s i t y ( R ( u ) ) Diversity=\frac{1}{|U|}\sum_{u\in U}Diversity(R(u)) Diversity=U1uUDiversity(R(u))

(5) 新颖性
新颖性也是影响用户体验的重要指标之一。它指的是向用户推荐非热门非流行物品的能力。评测新颖度最简单的方法是利用推荐结果的平均流行度,因为越不热门的物品,越可能让用户觉得新颖。

但是这种计算方法比较粗糙,因为不同用户不知道的东西是不同的,需要配合用户调查准确统计新颖度。

(6) 惊喜度
惊喜度与新颖度相关,它是指推荐结果和用户的历史兴趣不相似,但却让用户满意的程度。

(7) 信任度
信任度用于衡量用户对推荐系统的信任程度,这个指标的意义在于,如果用户信任推荐系统就会增多用户和推荐系统的交互。信任度目前只能通过问卷调查的方式来度量。

提高信任度的方式主要有两种:

  • 增加系统透明度
    即提供推荐解释,让用户了解推荐系统的运行机制。
  • 利用社交网络信息
    即利用用户的好友给用户做推荐。

(8) 实时性
许多物品具有很强的时效性,例如新闻、微博等,需要在时效期内推荐给用户,否则物品的价值就可能大打折扣。推荐系统的实时性包括两方面:

  • 实时更新推荐列表满足用户新的行为变化;
  • 将新加入系统的物品推荐给用户;

前者可以通过推荐列表的更新速率来控制和测评,后者可以通过计算推荐列表中有多大比例的物品是新加入物品来测评。

(9) 健壮性
任何能带来利益的算法系统都会被攻击,最典型的案例就是搜索引擎的作弊与反作弊斗争。推荐系统也不例外,健壮性衡量了推荐系统抗击作弊的能力。

2011年的推荐系统大会专门有一个推荐系统健壮性的教程,作者总结了很多作弊方法,最著名的是行为注入攻击(Profile Injection Attack)。就是注册很多账号,用这些账号同时购买某件商品A和自己的商品。此方法针对一种购物网站的推荐方法:“购买商品A的用户也经常购买的其他商品”。

一般会利用模拟攻击来评测算法的健壮性:

  • 给定一个数据集和算法,用算法给数据集中的用户生成推荐列表;
  • 用常用的攻击方法向数据集中注入噪声数据;
  • 利用算法在有噪声的数据集上再次生成推荐列表;
  • 通过比较攻击前后推荐列表的相似度评测算法的健壮性。

提高推荐系统健壮性的方法:

  • 选择健壮性高的算法;
  • 选择代价较高的用户行为,例如收费的用户行为(购物等)、限制用户权限(给用户分级);
  • 在使用数据前进行攻击检测,从而对数据进行清理。

(10) 商业目标
设计推荐系统时,需要考虑最终的商业目标。不同网站具有不同的商业目标,它与网站的盈利模式息息相关。

比如电子商务网站的目标可能是销售额,基于展示广告盈利的网站其商业目标可能是广告展示总数,基于点击广告盈利的网站其商业目标可能是广告点击总数。因此,设计推荐系统时需要考虑最终的商业目标,也就是说网站使用推荐系统的目的除了满足用户发现内容的需求,同时也需要利用推荐系统加快实现商业上的指标。

1.2.3. 评判维度

增加评测维度的目的,就是知道一个算法在什么情况下性能最好,这样可以为融合不同推荐算法取得最好的整体性能带来参考。

一般评测维度分3种:

  • 用户维度:主要包括用户的人口统计学信息、活跃度以及是不是新用户等;
  • 物品维度:包括物品的属性信息、流行度、平均分以及是不是新加入的物品等;
  • 时间维度:包括季节,是工作日还是周末,白天还是晚上等;

如果推荐系统的评测报告中包含了不同维度下的系统评测结果,就能帮我们全面了解系统性能,甚至找到一个看上去比较弱的算法的优势,或者发现一个看上去比较强的算法的缺点。

2. 数据来源

关于推荐系统常用的数据集,大家可以参考:RecBole Dataset ListLibRec DatasetRS and Personalization Datasets

2.1. 用户行为数据

基于用户行为数据获取数据也就是通过用户曾经进行过的行为来了解用户兴趣和需求。

用户行为数据一般存于网站的日志中,网站在运行过程中都产生大量原始日志(Raw Log),多种原始日志可以按照用户行为汇总成会话日志(Session Log),其中每个会话表示一次用户行为及其对应的服务。

下面给出一种用户行为的统一表示,可以作为数据库设计的参考:

字段 含义
user id 产生行为的用户的唯一标识
item id 产生行为的对象的唯一标识
behavior type 行为的种类(比如是购买还是浏览)
context 产生行为的上下文,包括时间和地点等
behavior weight 行为的权重(如果是观看视频的行为,那么这个权重可以是观看时长;如果是打分行为,这个权重可以是分数)
behavior content 行为的内容(如果是评论行为,那么就是评论的文本;如果是打标签的行为,就是标签)

用户行为在个性化推荐系统中一般分两种:

  • 显性反馈行为(Explicit Feedback)
    显性反馈行为包括用户明确表示对物品喜好的行为。例如用户评分、点赞之类的用户表态;
  • 隐性反馈行为(Implicit Feedback)
    隐性反馈行为指的是那些不能明确反应用户喜好的行为。最具代表性的隐性反馈行为就是页面浏览行为,用户进行浏览既可能是对该页面的内容感兴趣,也可能是误操作。

我们从几个不同方面来比较显性反馈数据和隐性反馈数据:

显性反馈数据 隐性反馈数据
用户兴趣 明确 不明确
数量 较少 庞大
存储 数据库 分布式文件系统
实时读取 实时 有延迟
正负反馈 都有 只有正反馈

下标列举了在各个领域的网站中这显性反馈数据和隐性反馈数据的例子:

显性反馈数据 隐性反馈数据
视频网站 用户对视频的评分 用户观看视频的日志、浏览视频页面的日志
电子商务网站 用户对商品的评分 购买日志、浏览日志
门户网站 用户对新闻的评分 阅读新闻的日志
音乐网站 用户对音乐/歌手/专辑的评分 听歌的日志

在很多时候我们并不使用统一结构表示所有行为,因为使用统一的结构会造成很大的空间浪费。一般来说,会用不同的数据集包含不同的行为,目前比较有代表性的数据集有下面几个:

  • 无上下文信息的隐性反馈数据集
    每一条行为记录仅仅包含用户ID和物品ID,Book-Crossing 就是这种类型的数据集;
  • 无上下文信息的显性反馈数据集
    每一条记录包含用户ID、物品ID和用户对物品的评分;
  • 有上下文信息的隐性反馈数据集
    每一条记录包含用户ID、物品ID和用户对物品产生行为的时间戳。Lastfm数据集 就是这种类型的数据集;
  • 有上下文信息的显性反馈数据集
    每一条记录包含用户ID、物品ID、用户对物品的评分和评分行为发生的时间戳。Netflix Prize 提供的就是这种类型的数据集。

2.2. 用户标签数据

标签是一种重要的特征表现方式,用户用标签来描述对物品的看法,可以说标签是联系用户和物品的纽带,也是反应用户兴趣的重要数据源。

根据给物品打标签的人的不同,标签应用一般分为两种:一种是让作者或者专家给物品打标签;另一种是让普通用户给物品打标签,也就是UGC(User Generated Content,用户生成的内容)的标签应用。

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

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

为了研究上面的两个问题,我们首先需要理解下面三个问题:

  • 用户为什么要打标签
    用户标注的动机一是便于上传者组织自己的信息,同时帮助其他用户找到信息;二是可以更好地组织内容,方便用户将来的查找,同时可以传达某些信息,比如照片的拍摄时间和地点等;
  • 用户是如何打标签的
    用户打标签的行为也具有长尾分布的特点,即只使用少数常用标签、只给少数热门物品打标签;
  • 用户打什么样的标签
    不同的系统有不同的标签系统,通常需要专家去定义一些标签给用户使用,否则用户很可能会给物品打上各种各样奇奇怪怪的标签。Delicious上的一种经典标签系统可以表示如下:
    1. 表明物品是什么。比如是一只鸟,就会有“鸟”这个词的标签;是豆瓣的首页,就有一个标签叫“豆瓣”;是乔布斯的首页,就会有个标签叫“乔布斯”。
    2. 表明物品的种类。比如表示一个网页类别的标签包括 article(文章)、blog(博客)、book(图书)等。
    3. 表明谁拥有物品。比如很多博客的标签中会包括博客的作者等信息。
    4. 表达用户的观点。比如用户认为网页很有趣,就会打上标签funny(有趣),认为很无聊,就会打上标签boring(无聊)。
    5. 用户相关的标签。比如 my favorite(我最喜欢的)、my comment(我的评论)等。
    6. 用户的任务。比如 to read(即将阅读)、job search(找工作)等。

2.3. 上下文信息

上下文信息是指用户访问推荐系统的时间、地点、心情等,对于提高推荐系统的推荐准确度是非常重要的。比如,一个卖衣服的推荐系统在冬天和夏天应该给用户推荐不同种类的服装。推荐系统不能因为用户在夏天喜欢过某件T恤,就在冬天也给该用户推荐类似的T恤。因此,准确了解用户的上下文信息,并将该信息应用于推荐算法是设计好的推荐系统的关键。

总的来说,一般在推荐系统中我们会主要利用用户的时间上下文信息和位置上下文信息。

2.3.1. 时间上下文信息

一般认为,时间信息对用户兴趣的影响表现在以下几个方面:

  • 用户兴趣变化
    用户兴趣变化是因为用户自身原因发生的变化。比如随着时间的推移,用户半年前喜欢看番剧,现在喜欢看文艺片。要准确预测用户现在的兴趣,就应该关注用户最近的行为,因为用户最近的行为最能体现他现在的兴趣。当然,考虑用户最近的兴趣只能针对渐变的用户兴趣,而对突变的用户兴趣很难起作用;
  • 物品生命周期
    当我们决定在某个时刻给某个用户推荐某个物品时,需要考虑该物品在该时刻是否已经过时了。典型的短生命周期物品有新闻、直播等;
  • 季节效应
    季节效应主要反映了时间本身对用户兴趣的影响。比如人们夏天吃冰淇淋,冬天吃火锅,夏天穿T恤,冬天穿棉衣,以及不同节假日的商品规律等等。

在给定时间信息后,推荐系统从一个静态系统变成了一个时变的系统,而用户行为数据也变成了时间序列。包含时间信息的用户行为数据集由一系列三元组构成,其中每个三元组 ( u , i , t ) (u,i,t) (u,i,t) 代表了用户 u u u 在时刻 t t t 对物品 i i i 产生过行为。在给定数据集后,通过统计如下信息研究系统的时间特性:

  • 数据集每天独立用户数的增长情况
    有些网站处于快速增长期,它们每天的独立用户数都在线性(甚至呈指数级)增加。而有些网站处于平稳期,每天的独立用户数都比较平稳。还有一些网站处于衰落期,每天的用户都在流失。在3种不同的系统中用户行为是不一样的;
  • 系统的物品变化情况
    比如新闻网站,每天都会出现大量新的新闻,而每条热门的新闻其时间周期都不会太长,今天热门的新闻也许明天就被人忘记了;
  • 用户访问情况
    有些网站用户来一次就永远不来了,有些网站用户每周来一次,而有些网站用户每天都来。为了度量这些特性,我们可以统计用户的平均活跃天数,同时也可以统计相隔 T T T天来系统的用户的重合度。

2.3.2. 地点上下文信息

除了时间,地点作为一种重要的空间特征,也是一种重要的上下文信息。不同地区的用户兴趣有所不同,用户到了不同的地方,兴趣也会有所不同。

用户兴趣和地点相关的特征主要有两个:

  • 兴趣本地化
    不同地方的用户兴趣存在着很大的差别,不同国家和地区用户的兴趣存在着一定的差异。
  • 活动本地化
    一个用户在一段时间内往往只能在附近的地区活动。因此,在基于位置的推荐中我们需要考虑推荐地点和用户当前地点的距离,不能给用户推荐太远的地方。

2.4. 社交网络数据

社交网络可以很好地模拟现实社会,在社交网络中的用户通常相互认识,这大大提高了推荐的信任度,同时也缓解了推荐系统冷启动的问题。

不过,社会化推荐有一些明显的缺点,其中最主要的就是很多时候并不一定能提高推荐算法的离线精度(准确率和召回率)。特别是在基于社交图谱数据的推荐系统中,因为用户的好友关系不是基于共同兴趣产生的,所以用户好友的兴趣往往和用户的兴趣并不一致。比如,我们和自己父母的兴趣往往就差别很大。

现在互联网上充斥着各种各样带有社交性质的网站。那么,从什么方面可以获得社交网络数据呢?一般来说,有如下渠道:

  • 电子邮件
    电子邮件其实也是一个社交网络,可以通过分析用户的联系人列表了解用户的好友信息,进一步通过研究两个用户之间的邮件往来频繁程度度量两个用户的熟悉程度。
  • 用户注册信息
    在注册时引导用户填写一些诸如公司、学校等信息,就样就可以知道哪些用户曾经在同一家公司工作过,哪些用户曾经在同一个学校学习过。
  • 用户的位置数据
    位置信息也是一种反映用户社交关系的数据。在同一地点的用户更容易有相似的兴趣,甚至这些用户相互之间就认识。
  • 论坛和讨论组
    每个群聊或小组都包含一些有相同兴趣的人。如果两个用户同时加入了很多相同的小组,我们可以认为这两个用户很可能互相了解或者具有相似的兴趣。如果两个用户在讨论组中曾经就某一个帖子共同进行过讨论,那就更加说明他们之间的熟悉程度或兴趣相似度很高。
  • 即时聊天工具
    和电子邮件系统一样,用户在即时聊天工具上也会有一个联系人列表,而且往往还会给联系人进行分组。通过这个列表和分组信息,我们就可以知道用户的社交网络关系,而通过统计用户之间聊天的频繁程度,可以度量出用户之间的熟悉程度。
  • 社交网站
    社交网站是研究用户关系的绝佳地点,例如Facebook中的绝大多数用户联系基于社交图谱:由人们之间的亲属关系、工作关系而形成;Twitter中的绝大多数用户联系基于兴趣图谱:通过人们之间的共同兴趣和信念形成。

社交网络定义了用户之间的联系,我们通常用图描述社交网络。一般来说,有3种不同的社交网络数据:

  • 双向确认的社交网络数据
    以Facebook和人人网为代表,用户之间形成好友关系需要通过双方的确认;
  • 单向关注的社交网络数据
    以Twitter和新浪微博为代表,用户A可以关注用户B,而不用得到用户B的允许;
  • 基于社区的社交网络数据
    用户之间并没有明确的关系,但同在一个社区。比如豆瓣小组,属于同一个小组可能代表了用户兴趣的相似性;

3. 通用推荐模型

3.1. 协同过滤推荐

3.1.1. 基于邻域的模型 UserCF & ItemCF

基于邻域的算法分为两大类,一类是基于用户的协同过滤算法,另一类是基于物品的协同过滤算法。

(1)基于用户的协同过滤算法 UserCF

在这里插入图片描述

在一个在线个性化推荐系统中,当一个用户A需要个性化推荐时,可以先找到和A有相似兴趣的其他用户,然后把那些用户喜欢的、而用户A没有关注过的物品推荐给A。这种方法称为基于用户的协同过滤算法(UserCF)。

基于用户的协同过滤算法主要包括两个步骤:

  • 找到和目标用户兴趣相似的用户集合
  • 找到这个集合中的用户喜欢的,且目标用户没有听说过的物品,推荐给目标用户

算法的关键是计算两个用户的兴趣相似度。协同过滤算法主要利用用户兴趣列表的相似度计算用户兴趣的相似度,给定用户 u u u v v v,令 N ( u ) N(u) N(u) 表示用户 u u u 曾经有过兴趣的物品集合, N ( v ) N(v) N(v) 表示用户 v v v 曾经有过兴趣的物品集合。

计算用户兴趣相似度的方法有3种:

  • Jaccard公式 w u v = ∣ N ( u ) ∩ N ( v ) ∣ ∣ N ( u ) ∪ N ( v ) ∣ w_{uv}=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|} wuv=N(u)N(v)N(u)N(v)
  • 余弦相似性 w u v = ∣ N ( u ) ∩ N ( v ) ∣ ∣ N ( u ) ∣ ∣ N ( v ) ∣ w_{uv}=\frac{|N(u)\cap N(v)|}{\sqrt{|N(u)||N(v)|}} wuv=N(u)∣∣N(v)
    N(u)N(v)
  • 改进的余弦相似性 w u v = ∑ i ∈ N ( u ) ∩ N ( v ) 1 log ⁡ ( 1 + ∣ N ( i ) ∣ ) ∣ N ( u ) ∣ ∣ N ( v ) ∣ w_{uv}=\frac{\sum_{i\in N(u)\cap N(v)}\frac{1}{\log(1+|N(i)|)}}{\sqrt{|N(u)||N(v)|}} wuv=N(u)∣∣N(v)
    iN(u)N(v)log(1+N(i))1
    其中 1 log ⁡ ( 1 + ∣ N ( i ) ∣ ) \frac{1}{\log(1+|N(i)|)} log(1+N(i))1降低了用户 u u u和用户 v v v的共同兴趣列表中热门物品对用户相似度的影响

得到了用户之间的兴趣相似度之后,就要将用户兴趣列表转换为“物品-用户”倒排表,即对每个物品建立一个喜欢它的用户的列表,以此来给用户推荐与他兴趣最相似的 K K K个用户喜欢的物品。如下的公式度量了UserCF算法中用户 u u u对物品 i i i的感兴趣程度: p ( u , i ) = ∑ v ∈ S ( u , K ) ∩ N ( i ) w u v r v i p(u,i)=\sum_{v\in S(u,K)\cap N(i)}w_{uv}r_{vi} p(u,i)=vS(u,K)N(i)wuvrvi其中 S ( u , K ) S(u,K) S(u,K)包含和用户 u u u兴趣最接近的 K K K个用户, N ( i ) N(i) N(i)是对物品 i i i有过行为的用户集合, w u v w_{uv} wuv是用户 u u u和用户 v v v的兴趣相似度, r v i r_{vi} rvi代表用户 v v v对物品 i i i的兴趣。一般情况下,如果使用的是单一行为的隐反馈数据,那所有的 r v i = 1 r_{vi}=1 rvi=1

例如用户 A A A B B B C C C D D D和物品 a a a b b b c c c d d d e e e有如下用户兴趣列表:

用户 兴趣物品列表
A A A a a a b b b d d d
B B B a a a c c c
C C C b b b e e e
D D D c c c d d d e e e

用余弦相似度计算用户兴趣相似度:
w A B = ∣ { a , b , d } ∩ { a , c } ∣ ∣ { a , b , d } ∣ ∣ { a , c } ∣ = 1 6 w_{AB}=\frac{|\{a,b,d\}\cap \{a,c\}|}{\sqrt{|\{a,b,d\}||\{a,c\}|}}=\frac{1}{\sqrt{6}} wAB={
a,b,d}∣∣{
a,c}

{
a,b,d}{
a,c}
=
6
1

w A C = ∣ { a , b , d } ∩ { b , e } ∣ ∣ { a , b , d } ∣ ∣ { b , e } ∣ = 1 6 w_{AC}=\frac{|\{a,b,d\}\cap \{b,e\}|}{\sqrt{|\{a,b,d\}||\{b,e\}|}}=\frac{1}{\sqrt{6}} wAC={
a,b,d}∣∣{
b,e}

{
a,b,d}{
b,e}
=
6
1

w A D = ∣ { a , b , d } ∩ { c , d , e } ∣ ∣ { a , b , d } ∣ ∣ { c , d , e } ∣ = 1 3 w_{AD}=\frac{|\{a,b,d\}\cap \{c,d,e\}|}{\sqrt{|\{a,b,d\}||\{c,d,e\}|}}=\frac{1}{3} wAD={
a,b,d}∣∣{
c,d,e}

{
a,b,d}{
c,d,e}
=
31

通过比较我们可以知道用户 A A A与用户 D D D的兴趣相似度最高,用户 B B B C C C次之。若我们设 K = 1 K=1 K=1则意味着从相似度最高的用户 D D D的兴趣列表中选取物品推荐给用户 A A A;若设 K = 2 K=2 K=2,则从用户 B D BD BD C D CD CD的兴趣列表中选择;若设 K = 3 K=3 K=3则从全部用户 B C D BCD BCD的兴趣列表中选择物品推荐给用户 A A A

这里我们设 K = 3 K=3 K=3,此时我们需要计算用户 A A A与用户 B C D BCD BCD兴趣列表中的物品(即, a a a b b b c c c d d d e e e)的感兴趣程度。首先建立“物品-用户”倒排表:

物品 喜欢该物品的用户
a a a A A A B B B
b b b A A A C C C
c c c B B B D D D
d d d A A A D D D
e e e C C C D D D

从倒排表我们可以轻松地找到不同物品关联的喜欢该物品的用户,这时我们就可以利用用户 A A A对其他用户的相似度来衡量用户A对这些物品的感兴趣程度了: p ( A , c ) = w A B + w A D = 0.7416 p(A,c)=w_{AB}+w_{AD}=0.7416 p(A,c)=wAB+wAD=0.7416

p ( A , e ) = w A C + w A D = 0.7416 p(A,e)=w_{AC}+w_{AD}=0.7416 p(A,e)=wAC+wAD=0.7416

根据计算结果,我们可以知道用户 A A A 对物品 c c c e e e 的兴趣一致,因此我们可以任意推荐他们其中一个,或者一起推荐给用户 A A A。需要注意的是我们没有计算 p ( A , a ) p(A,a) p(A,a) p ( A , b ) p(A,b) p(A,b) p ( A , d ) p(A,d) p(A,d),这是因为物品 a a a b b b d d d 已经在用户 A A A 的兴趣列表中了,所以没必要再推荐。

我在博客:推荐算法的Python实现——UserCF(基于用户的协同过滤) 中实现了 UserCF ,可以参考理解。

(2)基于物品的协同过滤算法 ItemCF
在这里插入图片描述

基于物品的协同过滤算法用于给用户推荐那些与他们之前喜欢的物品相似的物品。

ItemCF算法主要通过分析用户的行为记录来计算物品之间的相似度。该算法认为,物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品B。

基于物品的协同过滤算法主要分为两步:

  1. 计算物品之间的相似度;
  2. 根据物品的相似度和用户的历史行为给用户生成推荐列表。

我们给定物品 i i i j j j,设 N ( i ) N(i) N(i)为喜欢物品 i i i的用户数, N ( j ) N(j) N(j)为喜欢物品 j j j的用户数,则物品 i i i j j j的相似度可以表达为:

  • Jaccard公式 w i j = ∣ N ( i ) ∩ N ( j ) ∣ ∣ N ( i ) ∣ w_{ij}=\frac{|N(i)\cap N(j)|}{|N(i)|} wij=N(i)N(i)N(j)上述公式可以理解为喜欢物品 i i i 的用户中有多少比例的用户也喜欢物品 j j j
  • 余弦相似性 w i j = ∣ N ( i ) ∩ N ( j ) ∣ ∣ N ( i ) ∣ ∣ N ( j ) ∣ w_{ij}=\frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}} wij=N(i)∣∣N(j)
    N(i)N(j)
    该公式降低了热门物品会和很多物品相似的可能性,可以避免推荐出热门的物品。
  • 改进的余弦相似性 w i j = ∑ u ∈ N ( i ) ∩ N ( j ) 1 log ⁡ ( 1 + ∣ N ( u ) ∣ ) ∣ N ( i ) ∣ ∣ N ( j ) ∣ w_{ij}=\frac{\sum_{u\in N(i)\cap N(j)}\frac{1}{\log(1+|N(u)|)}}{\sqrt{|N(i)||N(j)|}} wij=N(i)∣∣N(j)
    uN(i)N(j)log(1+N(u))1
    其中 1 log ⁡ ( 1 + ∣ N ( i ) ∣ ) \frac{1}{\log(1+|N(i)|)} log(1+N(i))1对余弦相似性进行了修正,使得活跃用户对物品相似度的贡献大于不活跃的用户。

提一句,如果将ItemCF的相似度矩阵 w w w 按最大值归一化,可以提高推荐的准确率,归一化公式如下: w i j ′ = w i j max ⁡ j w i j w_{ij}’=\frac{w_{ij}}{\max_{j}w_{ij}} wij=maxjwijwij

在ItemCF中,两个物品之所以产生相似度是因为它们共同被很多用户喜欢,即每个用户都可以通过他们的历史兴趣列表给物品“贡献”相似度。也就是说,在得到物品之间的相似度后,我们可以建立一个“用户-物品”倒排表,即对每个用户建立一个包含他喜欢的物品的列表。

然后通过如下公式计算用户 u u u对一个物品 j j j的兴趣度: p u j = ∑ i ∈ N ( u ) ∩ S ( j , K ) w j i r u i p_{uj}=\sum_{i\in N(u)\cap S(j,K)}w_{ji}r_{ui} puj=iN(u)S(j,K)wjirui

这里 N ( u ) N(u) N(u)是用户喜欢的物品的集合, S ( j , K ) S(j,K) S(j,K)是和物品 j j j最相似的 K K K个物品的集合, w j i w_{ji} wji是物品 j j j i i i的相似度, r u i r_{ui} rui是用户 u u u对物品i的兴趣(如果用户 u u u对物品 i i i有过行为,即可令 r u i = 1 r_{ui}=1 rui=1)。该公式的含义是,与用户历史上感兴趣的物品越相似的物品,越有可能是用户感兴趣的物品。

ItemCF的推荐过程可以用如下例子来表示:
假设已知用户对两个物品 A 1 A_1 A1 A 2 A_2 A2的兴趣度分别为1.3、0.9,现有5个用户未曾见过的新物品,它们与物品 A 1 A_1 A1 A 2 A_2 A2的相似度可以表示为:

物品 与物品 A 1 A_1 A1的相似度 与物品 A 2 A_2 A2的相似度
B 1 B_1 B1 0.7 0
B 2 B_2 B2 0.4 0.5
B 3 B_3 B3 0 0.5
B 4 B_4 B4 0.6 0
B 5 B_5 B5 0 0.6

可得,用户对 B 1 B_1 B1 B 2 B_2 B2 B 3 B_3 B3 B 4 B_4 B4 B 5 B_5 B5的兴趣度分别为:
p u B 1 = 1.3 ∗ 0.7 = 0.91 p_{uB_1}=1.3*0.7=0.91 puB1=1.30.7=0.91

p u B 2 = 1.3 ∗ 0.4 + 0.9 ∗ 0.5 = 0.97 p_{uB_2}=1.3*0.4+0.9*0.5=0.97 puB2=1.30.4+0.90.5=0.97

p u B 3 = 0.9 ∗ 0.5 = 0.45 p_{uB_3}=0.9*0.5=0.45 puB3=0.90.5=0.45

p u B 4 = 1.3 ∗ 0.6 = 0.78 p_{uB_4}=1.3*0.6=0.78 puB4=1.30.6=0.78

p u B 5 = 0.9 ∗ 0.6 = 0.54 p_{uB_5}=0.9*0.6=0.54 puB5=0.90.6=0.54

由此我们可知,用户可能对物品 B 2 B_2 B2的兴趣度最高,应该向用户推荐物品 B 2 B_2 B2

我在博客:推荐算法的Python实现——ItemCF(基于物品的协同过滤) 中实现了 ItemCF ,可以参考理解。

(3)UserCF 与 ItemCF 的区别

特性 UserCF ItemCF
性能 适用于用户数少于物品数的场合,如果用户很多,计算用户相似度矩阵代价很大 适用于物品数少于用户数的场合,如果物品很多,计算物品相似度矩阵代价很大
领域 适用于时效性较强,用户个性化兴趣不太明显的领域 适用于长尾物品丰富,用户个性化需求强烈的领域
实时性 用户有新行为,不一定造成推荐结果的立即变化 用户有新行为,一定会导致推荐结果的实时变化
冷启动 无法给新用户和物品进行准确推荐 新用户只要对一个物品产生行为,就可以给他推荐和该物品相关的其他物品
推荐解释 很难提供令用户信服的推荐解释 可以利用用户的历史行为给用户做推荐解释

关于协同过滤算法(CF)的推荐效果,我们从流行度的角度来考虑。在movie-lens-1m数据集上,ICF的推荐效果更加分散,UCF的推荐效果更加集中,也就是ICF的平均流行度会低于UCF。

  • ICF
    下面两个图分别是(左)项目流行度与项目平均排名(Top-K)的关系;(右)项目流行度与其排名前50(Top-K)的概率。
    在这里插入图片描述
  • UCF
    下面两个图分别是(左)项目流行度与项目平均排名(Top-K)的关系;(右)项目流行度与其排名前50(Top-K)的概率。
    在这里插入图片描述

3.1.2. 隐语义模型 MF

LFM(Latent Factor Model)隐语义模型的核心思想是通过隐含特征(Latent Factor)联系用户兴趣和物品,它采取基于用户行为统计的自动聚类,让用户和物品的分类自动化。

LFM通过如下公式计算用户 u u u对物品i的兴趣: P r e f e r e n c e ( u , i ) = r u i = p u T q i = ∑ f = 1 F p u , k q i , k Preference(u,i)=r_{ui}=p_u^Tq_i=\sum_{f=1}^{F}p_{u,k}q_{i,k} Preference(u,i)=rui=puTqi=f=1Fpu,kqi,k

其中 , p u , k p_{u,k} pu,k度量了用户 u u u的兴趣和第 k k k个隐类的关系,而 q i , k q_{i,k} qi,k度量了物品 i i i和第 k k k个隐类之间的关系。

推荐系统的用户行为样本分为正样本(用户喜欢什么物品)和负样本(用户对什么物品不感兴趣)。经过对正负样本的采样,可以得到一个用户—物品集 K = { ( u , i ) } K=\{(u,i)\} K={(u,i)},其中如果 ( u , i ) (u,i) (u,i)是正样本,则有 r u i = 1 r_{ui}=1 rui=1,否则 r u i = 0 r_{ui}=0 rui=0,然后,通过随机梯度下降法优化如下的损失函数来找到最合适的参数 p p p q q q C = ∑ ( u , i ) ∈ K ( r u i − r ^ u i ) = ∑ ( u , i ) ∈ K ( r u i − ∑ k = 1 K p u , k q i , k ) + λ ∥ p u ∥ 2 + λ ∥ q i ∥ 2 C=\sum_{(u,i)\in K}(r_{ui}-\hat{r}_{ui})=\sum_{(u,i)\in K}\Bigl(r_{ui}-\sum_{k=1}^{K}p_{u,k}q_{i,k}\Bigr)+\lambda\Vert p_u\Vert^2+\lambda\Vert q_i\Vert^2 C=(u,i)K(ruir^ui)=(u,i)K(ruik=1Kpu,kqi,k)+λpu2+λqi2其中, λ ∥ p u ∥ 2 + λ ∥ q i ∥ 2 \lambda\Vert p_u\Vert^2+\lambda\Vert q_i\Vert^2 λpu2+λqi2是用来防止过拟合的正则化项, λ \lambda λ可以通过实验获得。

随机梯度下降法需要首先对参数 p u , k p_{u,k} pu,k q i , k q_{i,k} qi,k 分别求偏导数:
∂ C ∂ p u , k = − 2 q i , k + 2 λ p u , k \frac{\partial C}{\partial p_{u,k}}=-2q_{i,k}+2\lambda p_{u,k} pu,kC=2qi,k+2λpu,k

∂ C ∂ q i , k = − 2 p u , k + 2 λ q i , k \frac{\partial C}{\partial q_{i,k}}=-2p_{u,k}+2\lambda q_{i,k} qi,kC=2pu,k+2λqi,k

然后这两个参数沿着方向导数前进,得到如下递推公式:
p u , k = p u , k + α ( q i , k − λ p u , k ) p_{u,k}=p_{u,k}+\alpha(q_{i,k}-\lambda p_{u,k}) pu,k=pu,k+α(qi,kλpu,k)

q i , k = q i , k + α ( p u , k − λ q i , k ) q_{i,k}=q_{i,k}+\alpha(p_{u,k}-\lambda q_{i,k}) qi,k=qi,k+α(pu,kλqi,k)其中, α \alpha α指学习速率(Learning Rate),是一个可调参数。

矩阵分解算法(Matrix Factorization, MF)就是LFM的一种,现实中我们得到的是残缺的评分矩阵,可以通过分解评分矩阵,学习得到用户和物品的隐向量,也就是上面的用户矩阵 p u p_u pu和物品矩阵 q i q_i qi
在这里插入图片描述
我在博客:推荐算法的Python实现——MF(矩阵分解)推荐算法的Python实现——MF(矩阵分解) 基于TensorFlow 中实现了矩阵分解算法 ,可以参考理解。

LFM和基于邻域的方法区别大致如下:

特性 LFM 基于邻域
理论基础 基于机器学习,理论基础好,可以优化参数建立最优模型 基于统计的方法,没有学习过程
离线计算的空间复杂度 O ( F ∗ ( M + N ) ) O(F*(M+N)) O(F(M+N)),其中 F F F指隐类的个数, M M M指用户数, N N N指物品数 UserCF: O ( M ∗ M ) O(M*M) O(MM),ItemCF: O ( N ∗ N ) O(N*N) O(NN)。其中 M M M指用户数, N N N指物品数
离线计算的时间复杂度 O ( K ∗ F ∗ S ) O(K*F*S) O(KFS),其中 F F F指隐类的个数, S S S指迭代次数 UserCF: O ( N ∗ ( K / N ) 2 ) O(N*(K/N)^2) O(N(K/N)2),ItemCF: O ( M ∗ ( K / M ) 2 ) O(M*(K/M)^2) O(M(K/M)2)。其中 M M M指用户数, N N N指物品数, K K K指用户对物品行为记录的总数
在线实时推荐 不能实时推荐,不适用于物品数量庞大的系统 可以实时推荐
推荐解释 解释性不强 解释性好

3.1.3. 基于图的模型

用户对物品的行为很容易用二分图表示,已知用户行为数据是由一系列二元组组成的,其中每个二元组 ( u , i ) (u, i) (u,i)表示用户 u u u对物品 i i i产生过行为,这样的数据可以用二分图 G ( V , E ) G(V,E) G(V,E)表示,其中 V = V U ∪ V I V=V_U\cup V_I V=VUVI 由用户顶点集合 V U V_U VU和物品顶点集合 V I V_I VI组成。

对于数据集中的每一个二元组 ( u , i ) (u,i) (u,i),都有一套对应的边 e ( v u , v i ) e(v_u,v_i) e(vu,vi),其中 v u ∈ V U v_u\in V_U vuVU是用户 u u u对应的顶点, v i ∈ V I v_i\in V_I viVI是物品 i i i对应的顶点,如下表和图所示:

用户 兴趣物品列表
A A A a a a b b b d d d
B B B a a a c c c
C C C b b b e e e
D D D c c c d d d e e e

表示为二分图:

A

a

b

d

B

c

C

e

D

可以看到在上图中,圆形结点为一个分割,矩形结点为另一个分割。

要将个性化推荐算法放到二分图模型上,那么给用户 u u u推荐物品的任务就可以转化为度量用户顶点 v u v_u vu v u v_u vu没有边直接相连的物品节点在图上的相关性,相关性越高的物品在推荐列表中的权重就越高。

相关性高的一对顶点,一般具有以下特征:

  • 两个顶点之间有很多路径相连;
  • 链接两个顶点之间的路径长度都比较短;
  • 链接两个顶点之间的路径不会经过出度比较大的顶点。

基于上面3个主要因素,研究人员设计了很多计算图中顶点之间相关性的方法,这里讲解基于随机游走的PageRank和PersonalRank算法。

(1)PageRank算法

PageRank是用来衡量特定网页相对于搜索引擎中其他网页的重要性的算法,其计算结果作为Google搜索结果中网页排名的重要指标。

网页之间通过超链接相互连接,互联网上不计其数的网页就构成了一张超大的图。PageRank假设用户从所有网页中随机选择一个网页进行浏览,然后通过超链接在网页直接不断跳转。到达每个网页后,用户有两种选择:到此结束或者继续选择一个链接浏览。

设用户继续浏览的概率为 α \alpha α,用户以相等的概率在当前页面的所有超链接中随机选择一个继续浏览。当经过很多次这样的随机游走之后,每个网页被访问用户访问到的概率就会收敛到一个稳定值。

算法迭代关系式如下所示: P R ( v ) = 1 − α N + α ∑ v ′ ∈ i n ( v ) P R ( v ′ ) ∣ o u t ( v ′ ) ∣ PR(v)=\frac{1-\alpha}{N}+\alpha\sum_{v’\in in(v)}\frac{PR(v’)}{|out(v’)|} PR(v)=N1α+αvin(v)out(v)PR(v)

其中 P R ( v ) PR(v) PR(v)是网页 v v v被访问的概率(也就是重要性程度), α \alpha α是用户继续访问网页的概率, N N N是网页总数。 i n ( v ) in(v) in(v)表示指向网页 v v v的网页集合(入度), o u t ( v ′ ) out(v’) out(v)表示网页 v ′ v’ v指向的网页集合(出度)。

将网页替换为其他物品同理。

(2)PersonalRank算法

PersonalRank跟PageRank的区别只在于每一步概率的取值不一样,PersonalRank用 r v r_v rv替换了 1 / N 1/N 1/N,也就是说PersonalRank走到任意的下一个节点的概率服从均匀分布。

公式表达为: P R ( v ) = ( 1 − α ) r v + α ∑ v ′ ∈ i n ( v ) P R ( v ′ ) ∣ o u t ( v ′ ) ∣ PR(v)=(1-\alpha)r_v+\alpha\sum_{v’\in in(v)}\frac{PR(v’)}{|out(v’)|} PR(v)=(1α)rv+αvin(v)out(v)PR(v)其中 r v = { 1 , v = v u 0 , v ≠ v u r_v = \begin{cases} 1, & v=v_u \\ 0, & v\neq v_u \end{cases} rv={
1,0,v=vuv=vu
v u v_u vu是指用户 u u u对应的节点

为了PersonalRank的时间复杂度,可以从矩阵论出发重新设计算法。

M M M为用户物品二分图的转移概率矩阵,即: M ( v , v ′ ) = 1 ∣ o u t ( v ) ∣ M(v,v’)=\frac{1}{|out(v)|} M(v,v)=out(v)1那么,迭代公式可以转化为: r = ( 1 − α ) r v + α M T r = ( 1 − α ) ( 1 − α M T ) − 1 r v \begin{aligned} r & = (1-\alpha)r_v+\alpha M^Tr \\ & = (1-\alpha)(1-\alpha M^T)^{-1}r_v \\ \end{aligned} r=(1α)rv+αMTr=(1α)(1αMT)1rv

用PersonalRank算法对上面的示例中的用户 A A A进行推荐,可得如下结果:

用户 A A A 和物品 c c c e e e 没有边相连,但是用户 A A A 和物品 c c c 有三条长度为 3 3 3 的路径相连,用户 A A A 和物品 e e e 有两条长度为 3 3 3 的路径相连。那么,顶点 A A A e e e 之间的相关性就要高于顶点 A A A c c c,因而物品 e e e 在用户 A A A 的推荐列表中应该排在物品 c c c 之前。最终得出的推荐列表为 { c , e } \{c,e\} {
c,e}

用户 A A A与物品 c c c的路径:

A

a

b

d

B

c

C

e

D

A

a

b

d

B

c

C

e

D

A

a

b

d

B

c

C

e

D

用户 A A A与物品 e e e的路径:

A

a

b

d

B

c

C

e

D

A

a

b

d

B

c

C

e

D

3.2. 基于内容的推荐

基于内容推荐的原理是根据用户感兴趣的物品A,找到和A内容信息相近的物品B。内容信息是指用户和物品本身的内容特征,如用户的地理位置、性别、年龄,电影物品的导演、演员、发布时间等。比如用户喜欢看《神探夏洛克第一季》,那么就给他推荐《神探夏洛克第二季》。

基于内容推荐的优点如下:

  • 简单、有效,推荐结果直观,容易理解,不需要领域知识;
  • 不需要用户的历史数据,如对对象的评价等;
  • 没有物品冷启动的问题;
  • 没有稀疏问题;
  • 算法成熟,如数据挖掘、聚类分析等。

基于内容的推荐的缺点如下:

  • 特征提取能力有限
    比如图像、视频,没有有效的特征提取方法。即便是文本资源,特征提取也只能反应一部分内容,难以提取内容质量,会影响用户满意度。
  • 很难出现新的推荐结果
    根据用户兴趣的喜好进行推荐,很难出现惊喜。对于时间敏感的内容,如新闻,推荐内容基本相同,体验度较差。
  • 存在用户冷启动的问题
    当新用户出现时, 系统较难获得该用户的兴趣偏好,无法进行有效推荐。
  • 推荐对象内容分类方法需要的数据量较大

3.3. 基于关联规则的推荐

关联规则是反映一个事物与其他事物之间的相互依存性和关联性,常用于实体商店或在线电商的推荐系统:通过对顾客的购买记录数据库进行关联规则挖掘,最终目的是发现顾客群体的购买习惯的内在共性。

关联规则分析中的关键概念包括:支持度(Support)、置信度(Confidence)与提升度(Lift):

  • 支持度 Support
    支持度是两件商品 A A A B B B在总销售笔数 N N N中出现的概率,即 A A A B B B同时被购买的概率 S u p p o r t ( A ∩ B ) = F r e q ( A ∩ B ) N Support(A\cap B)=\frac{Freq(A\cap B)}{N} Support(AB)=NFreq(AB)

  • 置信度 Confidence
    置信度是购买 A A A后再购买 B B B的条件概率。简单来说就是交集部分 C C C A A A中比例,如果比例大说明购买 A A A的客户很大可能会购买 B B B商品 C o n f i d e n c e = F r e q ( A ∩ B ) F r e q ( A ) Confidence=\frac{Freq(A\cap B)}{Freq(A)} Confidence=Freq(A)Freq(AB)

  • 提升度 Lift
    提升度表示先购买A对购买B的概率的提升作用,用来判断规则是否有实际价值,即使用规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效,小于1则无效 L i f t = S u p p o r t ( A ∩ B ) S u p p o r t ( A ) ∗ S u p p o r t ( B ) Lift=\frac{Support(A\cap B)}{Support(A)*Support (B)} Lift=Support(A)Support(B)Support(AB)

例如在某电商平台上,可乐和薯片的关联规则的支持度是20%,购买可乐的支持度是3%,购买薯片的支持度是5%,则提升度为: L i f t = 0.2 0.03 ∗ 0.05 = 1.33 Lift=\frac{0.2}{0.03*0.05}=1.33 Lift=0.030.050.2=1.33这说明购买可乐对购买薯片有提升效果。

该提升效果的置信度为: C o n f i d e n c e = F r e q ( A ∩ B ) F r e q ( A ) = 0.2 N 0.03 N = 6.67 Confidence=\frac{Freq(A\cap B)}{Freq(A)}=\frac{0.2N}{0.03N}=6.67 Confidence=Freq(A)Freq(AB)=0.03N0.2N=6.67

3.4. 基于知识的推荐

基于知识的推荐(Knowledge-based Recommendation),主要应用于知识型的产品中,主要解决的问题是,为用户定制个性化的进阶路线图。

比如用户想学习钢琴,如果该用户是刚入门的小白,那最好从简单的谱子学起。但这样带来一个问题,由于用户的历史行为都在初级范围之内,根据兴趣偏好,推荐给用户的信息也都在初级范围,无法满足用户的进阶需求。

这个时候就需要基于知识的推荐。推荐系统知道用户现在所处的知识级别(用户知识),也知道学习钢琴所有的级别(产品知识),然后根据用户当前的情况为用户推荐合适的进阶信息。

精确的定义表达为:基于知识的推荐使用用户知识和产品知识, 通过推理什么产品能满足用户需求来产生推荐。这种推荐系统不依赖于用户评分等关于用户偏好的历史数据, 故其不存在冷启动方面的问题。基于知识的推荐系统响应用户的即时需求, 当用户偏好发生变化时不需要任何训练。

例如某论文针对海量习题带来的信息过载导致学习针对性不强、效率不高等问题,提出了基于知识点层次图的个性化习题推荐算法。

该算法首先根据课程知识点体系结构的特点,构建了表征知识点层次关系的权重图,该权重图有效反映知识点间的层次关系。然后,根据学生对知识点的掌握情况,在知识点层次图的基础上提出了一种个性化习题推荐算法。该算法通过更新学生-知识点失分率矩阵,获取学生掌握薄弱的知识点,以此实现习题推荐。

3.5. 基于标签的推荐

3.5.1. 基于标签推荐物品

拿到了用户标签行为数据之后,可以通过如下步骤设计一个推荐算法:

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

在第三步中,就是要找到用户所标记标签中有哪些物品是他最感兴趣的,可以通过以下兴趣公式计算:

  • 简单标签算法 p ( u , i ) = ∑ b n u , b n b , i p(u,i)=\sum_{b}n_{u,b}n_{b,i} p(u,i)=bnu,bnb,i其中, n u , b n_{u,b} nu,b是用户 u u u打过标签 b b b的次数, n b , i n_{b,i} nb,i是物品 i i i被打过标签 b b b的次数
  • TF-IDF标签算法 p ( u , i ) = ∑ b n u , b log ⁡ ( 1 + n b ( u ) ) n b , i p(u,i)=\sum_{b}\frac{n_{u,b}}{\log(1+n_b^{(u)})}n_{b,i} p(u,i)=blog(1+nb(u))nu,bnb,i其中, n b ( u ) n_b^{(u)} nb(u)记录了标签 b b b被多少个不同的用户使用过。这个公式可以给热门标签更小的权重,从而反应用户个性化的兴趣
  • 改进的TF-IDF标签算法 p ( u , i ) = ∑ b n u , b log ⁡ ( 1 + n b ( u ) ) n b , i log ⁡ ( 1 + n i ( u ) ) p(u,i)=\sum_{b}\frac{n_{u,b}}{\log(1+n_b^{(u)})}\frac{n_{b,i}}{\log(1+n_i^{(u)})} p(u,i)=blog(1+nb(u))nu,blog(1+ni(u))nb,i其中, n i ( u ) n_i^{(u)} ni(u)记录了物品 i i i被多少个不同的用户打过标签。这个公式可以给热门物品更小的权重,从而反应用户个性化的兴趣。

TF-IDF 公式(Term Frequency-Inverse Document Frequency, 词频-逆文件频率)是文本分析领域的著名公式,它用于计算词的权重: w i = T F ( e i ) log ⁡ ( I D F ( e i ) ) w_i=\frac{TF(e_i)}{\log(IDF(e_i))} wi=log(IDF(ei))TF(ei)其中, 词频 ( T F ) = e i 在文本中出现的次数 该文本中出现次数最多的词的出现次数 词频(TF)=\frac{e_i在文本中出现的次数}{该文本中出现次数最多的词的出现次数} 词频(TF)=该文本中出现次数最多的词的出现次数ei在文本中出现的次数 逆文档频率 ( I D F ) = log ⁡ ( 文本总数 包含该关键词的文本数 + 1 ) 逆文档频率(IDF)=\log(\frac{文本总数}{包含该关键词的文本数+1}) 逆文档频率(IDF)=log(包含该关键词的文本数+1文本总数)

众多的标签并不是一个个标签孤岛,实际上,大多数标签之间都有一定的联系,例如“强化学习”和“多臂老虎机算法”、“Q学习”三个不一样的标签相交于同一领域,为了衡量不同标签之间的相关性,我们这里介绍一种基于邻域的标签扩展方法,即对每个标签找到和它相似的标签,也就是计算标签之间的相似度。

如果认为同一个物品上的不同标签具有某种相似度,那么当两个标签同时出现在很多物品的标签集合中时,我们就可以认为这两个标签具有较大的相似度。对于标签 b b b,令 N ( b ) N(b) N(b)为被打上标签 b b b的物品的集合, n b , i n_{b,i} nb,i为给物品 i i i打上标签 b b b的用户数,我们可以通过如下余弦相似度公式计算标签 b b b和标签 b ′ b’ b的相似度: s i m ( b , b ′ ) = ∑ i ∈ N ( b ) ∩ N ( b ′ ) n b , i n b ′ , i ∑ i ∈ N ( b ) n b , i 2 ∑ i ∈ N ( b ′ ) n b ′ , i 2 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}} sim(b,b)=iN(b)nb,i2iN(b)nb,i2
iN(b)N(b)nb,inb,i
这样的话就可以让那些含义相同的标签相互关联起来。

同时我们必须注意到,不是所有标签都能反应用户的兴趣。比如,在一个视频网站中,用户可能对一个视频打了一个表示情绪的标签,比如“不好笑”,但我们不能因此认为用户对“不好笑”有兴趣。因此我们需要进行标签清理

标签清理的另一个重要意义在于将标签作为推荐解释。如果我们要把标签呈现给用户,将其作为给用户推荐某一个物品的解释,对标签的质量要求就很高。一般来说,标签清理有如下几种方法:

  • 去除词频很高的停止词
  • 去除因(词根、翻译、叫法)不同造成的同义词。
  • 去除因分隔符造成的同义词

此外,为了控制标签的质量,很多网站也采用了让用户进行反馈的思想,即让用户告诉系统某个标签是否合适。

为了得到更好的推荐效果,我们利用图模型做基于标签数据的个性化推荐,即基于图的标签推荐算法

该方法首先需要将用户打标签的行为表示到一张图上。在用户标签数据集上,有3种不同的元素,即用户、物品和标签,因此,我们需要定义3种不同的顶点,即用户顶点、物品顶点和标签顶点。这样就得到了一个表示用户 u u u给物品 i i i打了标签 b b b的用户标签行为 ( u , i , b ) (u,i,b) (u,i,b)

如下所示用户—物品—标签图包含3个用户( A A A B B B C C C)、3个物品( a a a b b b c c c)和3个标签( 1 1 1 2 2 2 3 3 3

在这里插入图片描述
对应的用户标签行为列表为:

用户 标签 物品
A A A 2 2 2 b b b
A A A 2 2 2 c c c
B B B 1 1 1 a a a
C C C 3 3 3 b b b

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

3.5.2. 给用户推荐标签

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

  • 方便用户输入标签
    让用户从键盘输入标签无疑会增加用户打标签的难度,这样很多用户不愿意给物品打标签,因此我们需要一个辅助工具来减小用户打标签的难度,从而提高用户打标签的参与度。
  • 提高标签质量
    同一个语义不同的用户可能用不同的词语来表示。这些同义词会使标签的词表变得很庞大,而且会使计算相似度不太准确。而使用推荐标签时,我们可以对词表进行选择,首先保证词表不出现太多的同义词,同时保证出现的词都是一些比较热门的、有代表性的词

用户 u u u给物品 i i i打标签时,我们有四种简单方法可以给用户推荐和物品 i i i相关的标签:

  • PopularTags
    给用户 u u u推荐整个系统里最热门的标签
  • ItemPopularTags
    给用户 u u u推荐物品 i i i上最热门的标签
  • UserPopularTags
    用户 u u u推荐他自己经常使用的标签
  • HybridPopularTags
    给用户推荐物品 i i i上最热门的标签,且他自己经常使用的标签,通过一个系数将两种方法的推荐结果进行线性加权,然后生成最终的推荐结果。

同样的,图模型也可以应用于标签推荐,在根据用户打标签的行为生成图之后,再利用PersonalRank算法进行排名。此时顶点的启动概率定义如下 r v ( k ) = { α , v ( k ) = v ( u ) 1 − α , v ( k ) = v ( i ) 0 , otherwise r_{v(k)} = \begin{cases} \alpha, & v(k)=v(u) \\ 1-\alpha, & v(k)=v(i) \\ 0,& \text{otherwise} \end{cases} rv(k)=

α,1α,0,v(k)=v(u)v(k)=v(i)otherwise

也就是说,只有用户 u u u和物品 i i i对应的顶点有非0的启动概率,而其他顶点的启动概率都为0。

3.6. 基于社交网络的推荐

3.6.1. 给用户推荐内容

社会化推荐受到很多网站的重视,因为其有如下优点:

  • 好友推荐可以增加推荐的信任度
    好友往往是用户最信任的。用户往往不一定信任计算机的智能,但会信任好朋友的推荐;
  • 社交网络可以缓解冷启动问题
    当一个新用户通过微博或者Facebook账号登录网站时,我们可以从社交网站中获取用户的好友列表,然后给用户推荐好友在网站上喜欢的物品。从而我们可以在没有用户行为记录时就给用户提供较高质量的推荐结果。

(1)基于邻域的社会化推荐算法

最简单算法是给用户推荐好友喜欢的物品集合,设用户 u u u 对物品 i i i 的兴趣 p u i p_{ui} pui,则有如下公式: p u i = ∑ v ∈ o u t ( u ) r v i p_{ui}=\sum_{v\in out(u)}r_{vi} pui=vout(u)rvi其中 o u t ( u ) out(u) out(u) 是用户 u u u 的好友集合,如果用户 v v v 喜欢物品 i i i,则 r v i = 1 r_{vi}=1 rvi=1,否则 r v i = 0 r_{vi}=0 rvi=0

不过显然的,不同的好友和用户 u u u的熟悉程度和兴趣相似度是不同的。因此,我们应该在推荐算法中应该考虑好友和用户的熟悉程度以及兴趣相似度: p u i = ∑ v ∈ o u t ( u ) w u v r v i p_{ui}=\sum_{v\in out(u)}w_{uv}r_{vi} pui=vout(u)wuvrvi其中 w u v w_{uv} wuv由两部分相似度构成,一部分是用户 u u u和用户 v v v的熟悉程度,另一部分是用户 u u u和用户 v v v的兴趣相似度,两者按照一定权重组合成 w u v w_{uv} wuv

用户 u u u 和用户 v v v 的熟悉程度(familiarity)描述了两个用户在现实社会中的熟悉程度,如果用户 u u u 和用户 v v v 很熟悉,那么一般来说他们应该有很多共同的好友: f a m i l i a r i t y = ∣ o u t ( u ) ∩ o u t ( v ) ∣ ∣ o u t ( u ) ∪ o u t ( v ) ∣ familiarity=\frac{|out(u)\cap out(v)|}{|out(u)\cup out(v)|} familiarity=out(u)out(v)out(u)out(v)

用户 u u u和用户 v v v的兴趣相似度(similarity)描述了两个用户喜欢的物品集合重合度: s i m i l a r i t y = ∣ N ( u ) ∩ N ( v ) ∣ ∣ N ( u ) ∪ N ( v ) ∣ similarity=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|} similarity=N(u)N(v)N(u)N(v)其中 N ( u ) N(u) N(u)是用户 u u u喜欢的物品集合

(2)基于图的社会化推荐算法
图模型的优点是可以将各种数据和关系都表示到图上去,应用到社交网站中,可以找出两种关系,一种是用户对物品的兴趣关系,一种是用户之间的社交网络关系。

用户的社交网络可以表示为社交网络图,用户对物品的行为可以表示为用户物品二分图,而这两种图可以结合成一个图,例如下图中的用户顶点(圆圈)和物品顶点(方块)
在这里插入图片描述
在定义完图中的顶点和边后,需要定义边的权重。其中用户和用户之间边的权重可以定义为用户之间相似度的 α \alpha α倍(包括熟悉程度和兴趣相似度),而用户和物品之间的权重可以定义为用户对物品喜欢程度的 β \beta β倍。之后就可以利用PersonalRank图排序算法给每个用户生成推荐结果。

在社交网络中,除了常见的、用户和用户之间直接的社交网络关系,还有一种关系,即两个用户属于同一个社群

为了表达这种社群关系,可以加入一种节点表示社群(下图最左边一列的节点),而如果用户属于某一社群,图中就有一条边联系用户对应的节点和社群对应的节点。在建立完图模型后,我们就可以通过前面提到的基于图的推荐算法(比如PersonalRank)给用户推荐物品。
在这里插入图片描述

(3)信息流推荐
在大多数社交软件中,我们都可以通过信息流看到好友最近的言论,但信息流里面夹杂了很多用户并不关心的信息。基于信息流的推荐就是进一步帮助用户从信息流中挑选有用的信息。

目前最流行的信息流推荐算法是Facebook的EdgeRank,该算法综合考虑了信息流中每个会话的时间、长度与用户兴趣的相似度,它的主要思想为:

将其他用户对当前用户信息流中的会话产生过行为的行为称为edge,而一条会话的权重定义为: ∑ edges  e u e w e d e \sum_{\text{edges } e}u_ew_ed_e edges euewede其中: u e u_e ue 指产生行为的用户和当前用户的相似度,这里的相似度主要是在社交网络图中的熟悉度; w e w_e we 指行为的权重,这里的行为包括创建、评论、like(喜欢)、打标签等。 d e d_e de 指时间衰减参数,越早的行为对权重的影响越低。

从上面的算法描述中可以得出看出在该算法中:如果一个会话被你熟悉的好友最近产生过重要的行为,它就会有比较高的权重。

3.6.2. 给用户推荐好友

好友推荐系统的目的是根据用户现有的好友、用户的行为记录给用户推荐新的好友,从而增加整个社交网络的稠密程度和社交网站用户的活跃度。好友推荐算法在社交网络上被称为链接预测(Link Prediction),主要包括以下几种场景:

(1)基于内容的匹配
可以给用户推荐和他们有相似内容属性的用户作为好友。下面给出了常用的内容属性:

  • 用户人口统计学属性,包括年龄、性别、职业、毕业学校和工作单位等
  • 用户的兴趣,包括用户喜欢的物品和发布过的言论等
  • 用户的位置信息,包括用户的住址、IP地址和邮编等

计算用户在上述内容信息上的相似度就可以找出相似的用户,然后相互推荐。

(2)基于共同兴趣的好友推荐
在Twitter和微博为代表的以兴趣图谱为主的社交网络中,用户往往不关心对于一个人是否在现实社会中认识,而只关心是否和他们有共同的兴趣爱好。因此,在这种网站中需要给用户推荐和他有共同兴趣的其他用户作为好友。

因此可以基于用户的利用协同过滤算法(UserCF)计算用户之间的兴趣相似度,其主要思想就是如果用户喜欢相同的信息和内容,则说明他们具有相似的兴趣。此外,也可以根据用户在社交网络中的发言提取用户的兴趣标签,来计算用户的兴趣相似度。

(3)基于社交网络图的好友推荐
基于好友的好友推荐算法可以用来给用户推荐他们在现实社会中互相熟悉,而在当前社交网络中没有联系的其他用户。

介绍3种基于社交网络的好友推荐算法:

  • 指出相似度 w o u t ( u , v ) = ∣ o u t ( u ) ∩ o u t ( v ) ∣ ∣ o u t ( u ) ∣ ∣ o u t ( v ) ∣ w_{out}(u,v)=\frac{|out(u)\cap out(v)|}{\sqrt{|out(u)||out(v)|}} wout(u,v)=out(u)∣∣out(v)
    out(u)out(v)
    其中 o u t ( u ) out(u) out(u)是在社交网络图中用户 u u u指向的其他好友的集合
  • 指入相似度 w i n ( u , v ) = ∣ i n ( u ) ∩ i n ( v ) ∣ ∣ i n ( u ) ∣ ∣ i n ( v ) ∣ w_{in}(u,v)=\frac{|in(u)\cap in(v)|}{\sqrt{|in(u)||in(v)|}} win(u,v)=in(u)∣∣in(v)
    in(u)in(v)
    其中 i n ( u ) in(u) in(u)是指在社交网络图中指向用户 u u u的其他好友的集合
  • 互指相似度 w o u t , i n ( u , v ) = ∣ o u t ( u ) ∩ i n ( v ) ∣ ∣ o u t ( u ) ∣ w_{out,in}(u,v)=\frac{|out(u)\cap in(v)|}{|out(u)|} wout,in(u,v)=out(u)out(u)in(v)这个相似度的含义是用户 u u u指向的用户中,有多大比例也指向了用户 v v v
  • 改进的互指相似度 w o u t , i n ( u , v ) = ∣ o u t ( u ) ∩ i n ( v ) ∣ ∣ o u t ( u ) ∣ ∣ i n ( v ) ∣ w_{out,in}(u,v)=\frac{|out(u)\cap in(v)|}{\sqrt{|out(u)||in(v)|}} wout,in(u,v)=out(u)∣∣in(v)
    out(u)in(v)
    这个公式考虑了指入的因素,可以避免出现网红被当做好友被推荐过来的现象。

4. 冷启动问题

推荐系统需要根据用户的历史行为和兴趣预测用户未来的行为和兴趣,因此大量的用户行为数据就成为推荐系统的重要组成部分和先决条件。因此很多在开始阶段就希望有个性化推荐应用的网站来说,如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统,就是冷启动(Cold Start)的问题。

冷启动主要分3类:

  • 用户冷启动
    用户冷启动主要解决如何给新用户做个性化推荐的问题。当新用户到来时,我们没有他的行为数据,所以也无法根据他的历史行为预测其兴趣,从而无法借此给他做个性化推荐。
  • 物品冷启动
    物品冷启动主要解决如何将新的物品推荐给可能对它感兴趣的用户这一问题。
  • 系统冷启动
    系统冷启动主要解决如何在一个新开发的网站上(物品信息远多于用户行为信息)设计个性化推荐系统,从而在网站刚发布时就让用户体验到个性化推荐服务这一问题。

对于这3类不同的冷启动问题,有不同的解决方案。一般来说,可以参考如下解决方案:

4.1. 利用用户注册信息

显而易见,利用用户的注册信息可以很好地缓解注册用户的冷启动问题。用户的注册信息分3种:

  • 人口统计学信息
    包括用户的年龄、性别、职业、民族、学历和居住地;
  • 用户兴趣的描述
    有一些网站会让用户用文字描述他们的兴趣;
  • 站外行为数据
    比如用户通过豆瓣、新浪微博的账号登录,就可以在得到用户同意的情况下获取用户在豆瓣或者新浪微博的一些行为数据和社交网络数据

基于注册信息的个性化推荐流程基本如下:

  1. 获取用户的注册信息
  2. 根据用户的注册信息对用户分类
  3. 给用户推荐他所属分类中用户喜欢的物品

如图所示新用户,资料显示他是一位28岁的男性,是一位物理学家。然后,查询3张离线计算好的相关表:

  • 性别-电视剧相关表。从中可以查询男性最喜欢的电视剧;
  • 年龄-电视剧相关表,从中可以查询到28岁用户最喜欢的电视剧;
  • 职业-电视剧相关表,可以查询到物理学家最喜欢的电视剧。

然后,我们可以将用这3张相关表查询出的电视剧列表按照一定权重相加,得到给用户的最终推荐列表。
在这里插入图片描述

基于用户注册信息的推荐算法其核心问题是计算每种特征的用户喜欢的物品。也就是说,对于每种特征 f f f,计算具有这种特征的用户对各个物品的兴趣程度 p ( f , i ) p(f,i) p(f,i)。有计算两种方法:

  • 物品 i i i 在具有 f f f 特征的用户中的热门程度 p ( f , i ) = ∣ N ( i ) ∩ U ( f ) ∣ p(f,i)=|N(i)\cap U(f)| p(f,i)=N(i)U(f)其中 N ( i ) N(i) N(i) 是喜欢物品 i i i 的用户集合, U ( f ) U(f) U(f) 是具有特征 f f f 的用户集合
  • 喜欢物品 i i i 的用户中具有特征 f f f 的比例 p ( f , i ) = ∣ N ( i ) ∩ U ( f ) ∣ ∣ N ( i ) ∣ + α p(f,i)=\frac{|N(i)\cap U(f)|}{|N(i)|+\alpha} p(f,i)=N(i)+αN(i)U(f)其中,参数 α \alpha α 用于解决数据稀疏问题。比如有一个物品只被1个用户喜欢过,而这个用户刚好就有特征 f f f,那么就有 p ( f , i ) = 1 p(f,i)=1 p(f,i)=1 。但是,这种情况并没有统计意义,因此我们为分母加上一个比较大的数,可以避免这样的物品产生比较大的权重。

通过 p ( f , i ) p(f,i) p(f,i)我们就可以知道什么样的用户适合推荐什么样的物品,从而可以进行粗粒度推荐,在一定程度上缓解冷启动问题。

4.2. 提供非个性化推荐启动用户需求

解决用户冷启动问题的另一个方法是在新用户第一次访问推荐系统时,不立即给用户展示推荐结果,而是给用户提供一些物品,让用户反馈他们对这些物品的兴趣,用这些反馈启动用户兴趣,然后根据用户兴趣给提供个性化推荐。

一般来说,能够用来启动用户兴趣的物品需要具有以下特点:

  • 比较热门
    如果要让用户对一个物品进行反馈,就需要选用用户知晓的物品;
  • 具有代表性和区分性
    启动用户兴趣的物品不能是大众化或老少皆宜的,因为这样的物品对用户的兴趣没有区分性。;
  • 具有多样性
    在冷启动时,我们不知道用户的兴趣,而用户兴趣的可能性非常多,为了匹配多样的兴趣,我们需要提供具有很高覆盖率的启动物品集合,这些物品能覆盖几乎所有主流的用户兴趣。

上面这些因素都是选择启动物品时需要考虑的,但如何设计一个选择启动物品集合的系统呢?首先,给定一群用户,可以用这群用户对物品评分的方差来度量这群用户兴趣的一致程度。如果方差很大,说明这一群用户的兴趣不太一致,反之则说明这群用户的兴趣比较一致。令 σ u ∈ U ′ \sigma_{u\in U’} σuU为用户集合 U ′ U’ U中所有评分的方差,可以通过如下方式度量一个物品的区分度 D ( i ) D(i) D(i) D ( i ) = σ u ∈ N + ( i ) + σ u ∈ N − ( i ) + σ u ∈ N ‾ ( i ) D(i)=\sigma_{u\in N^+(i)}+\sigma_{u\in N^-(i)}+\sigma_{u\in \overline N(i)} D(i)=σuN+(i)+σuN(i)+σuN(i)

其中, N + ( i ) N^+(i) N+(i)是喜欢物品 i i i的用户集合, N − ( i ) N^-(i) N(i)是不喜欢物品 i i i的用户集合, N ‾ ( i ) \overline N(i) N(i)是没有对物品 i i i评分的用户集合。

应用上述公式计算所有物品,就可以从中找到具有最高区分度的物品 i i i,然后将用户分成3类:喜欢该物品、不喜欢该物品、未评价该物品的用户。然后对每类用户再找到最具区分度的物品,然后将每一类用户又各自分为3类,如此反复组织成一颗树。

而在用户冷启动时,我们从根节点开始询问用户对该节点物品的看法,然后根据用户的选择将用户放到不同的分枝,直到进入最后的叶子节点,此时我们就已经对用户的兴趣有了比较清楚的了解,从而可以开始对用户进行比较准确地个性化推荐。

4.3. 利用物品内容信息

物品冷启动需要解决的问题是如何将新加入的物品推荐给对它感兴趣的用户。物品冷启动在新闻网站等时效性很强的网站中非常重要,因为那些网站中时时刻刻都有新加入的物品,而且每个物品必须能够在第一时间展现给用户,否则经过一段时间后,物品的价值就大大降低了。

一般来说,物品的内容可以通过向量空间模型表示,例如对于物品 d d d,由于物品的内容信息中通常包含一些关键词,所以该模型会将物品表示成一个关键词向量 d i = { ( e 1 , w 1 ) , ( e 2 , w 2 ) , . . . , ( e n , w n ) } d_i=\{(e_1,w_1),(e_2,w_2),…,(e_n,w_n)\} di={(e1,w1),(e2,w2),,(en,wn)}

其中, e i e_i ei 就是关键词, w i w_i wi 是关键词对应的权重。

在给定物品内容的关键词向量后,物品的内容相似度可以通过向量之间的余弦相似度计算: c s i j = d i ⋅ d j ∥ d i ∥ ∥ d j ∥ cs_{ij}=\frac{d_i\cdot d_j}{\sqrt{\Vert d_i\Vert\Vert d_j \Vert}} csij=di∥∥dj
didj
得到物品的相似度之后,就可以利用ItemCF算法的思想,给用户推荐和他历史上喜欢的物品内容相似的物品。

不过需要注意的是,如果内容信息不足,关键词很少或者不同,向量空间模型就很难计算出准确的相似度。例如有两篇论文,它们的标题分别是“推荐系统的动态特性”和“基于时间的协同过滤算法研究”,这两篇文章的研究方向是类似的,但是它们标题中没有一样的关键词。换句话说,这两篇文章的关键词虽然不同,但关键词所属的话题是相同的。

在这种情况下,首先需要知道文章的话题分布,然后才能准确地计算文章的相似度。如何建立文章、话题和关键词的关系是话题模型(Topic Model)研究的重点。一种成熟的话题模型是LDA(Latent Dirichlet Allocation)模型

该模型对一篇文档产生的过程进行了建模,它的基本思想是,一个人在写一篇文档的时候,会首先想这篇文章要讨论哪些话题,然后思考这些话题应该用什么词描述,从而最终用词写成一篇文章。因此,文章和词之间是通过话题联系的。

在使用LDA计算物品的内容相似度时,我们可以先计算出物品在话题上的分布,然后利用两个物品的话题分布计算物品的相似度。比如,如果两个物品的话题分布相似,则认为两个物品具有较高的相似度,反之则认为两个物品的相似度较低。计算话题分布的相似度可以利用KL散度: D K L ( p ∥ q ) = ∑ i p ( i ) ln ⁡ p ( i ) q ( i ) D_{KL}(p\Vert q)=\sum_{i}^{}p(i)\ln\frac{p(i)}{q(i)} DKL(pq)=ip(i)lnq(i)p(i)其中 i i i是指某个物品, p p p q q q是两个分布, D K L D_{KL} DKL越大说明分布的相似度越低。

4.4. 发挥专家的作用

为了在推荐系统建立时就让用户得到比较好的体验,很多系统都利用专家进行标注。例如让专家给电影进行标注,可以得到以下标注分类:

分类 描述
心情(Mood) 表示用户观看电影的心情,比如对于《功夫熊猫》观众会觉得很幽默,很兴奋
剧情(Plot) 包括电影剧情的标签
类别(Genres) 表示电影的类别,主要包括动画片、喜剧片、动作片等分类
时间(Time/Period) 电影故事发生的时间
地点(Place) 电影故事发生的地点
观众(Audience) 电影的主要观众群
获奖(Praise) 电影的获奖和评价情况
风格(Style) 功夫片、全明星阵容等
态度(Attitudes) 电影描述故事的态度
画面(Look) 电脑拍摄的画面技术,比如《功夫熊猫》是用电脑动画制作的
标记(Flag) 主要表示电影有没有暴力和色情内容

5. 推荐系统实例

5.1. 外围架构

推荐系统要发挥强大的作用,除了推荐系统本身,主要还依赖于两个条件——界面展示和用户行为数据,统称为外围架构。目前流行的推荐系统界面大致都包含如下共性:

  • 通过一定方式展示物品
    主要展示物品的标题、缩略图和介绍等
  • 提供了推荐理由
    向用户展示推荐理由可以增加用户对推荐结果的信任度
  • 提供渠道让用户进行反馈
    不断的反馈让推荐算法持续改善用户的个性化推荐体验

在这里插入图片描述

按照所收集用户行为数据的规模和是否需要实时存取,不同的行为数据将被存储在不同的媒介中。一般来说,需要实时存取的数据存储在数据库和缓存中,而大规模的非实时地存取数据存储在分布式文件系统(如HDFS)中。

5.2. 推荐系统架构

推荐系统联系用户和物品的方式主要有如下图所示的3种。
在这里插入图片描述

在第三种方法中,推荐系统需要为用户生成特征,然后对每个特征找到和特征相关的物品,从而最终生成用户的推荐列表。因而,推荐系统的核心任务就被拆解成两部分,一个是如何为给定用户生成特征,另一个是如何根据特征找到物品。

同时要考虑到,如果要在一个系统中把所有特征和任务都统筹考虑,那么系统将会非常复杂,而且很难通过配置文件方便地配置不同特征和任务的权重。因此,推荐系统需要由多个推荐引擎组成,每个推荐引擎负责一种任务,而推荐系统的任务只是将推荐引擎的结果按照一定权重或者优先级合并、排序然后返回,如下图:
在这里插入图片描述

这种做法有两个好处:

  • 方便增删引擎
    控制不同引擎对推荐结果的影响。
  • 可以实现推荐引擎级别的用户反馈
    每一个推荐引擎都代表了一种推荐策略,而不同的用户可能喜欢不同的推荐策略。

5.3. 推荐引擎架构

具体到每一种推荐引擎到架构,推荐引擎架构主要包括下图中到三部分:
在这里插入图片描述

  • 图中A部分负责从数据库或缓存中拿到用户行为数据,通过分析不同行为,生成当前用户的特征向量,如果使用非行为特征,就不需要行为提取和分析模块了,该模块的输出就是用户特征向量。
  • 图中B部分负责将用户的特征向量通过特征-物品相关矩阵转化为初始推荐物品列表。
  • 图中C部分负责对初始的推荐列表进行过滤、排名等处理,从而生成该引擎的最终推荐结果。

A部分输出的特征向量一般有两种类型,一种是用户的注册信息中可以提取出来的,主要包括用户的人口统计学特征。另一种特征则主要是从用户的行为中计算出来的。

一个特征向量由特征及其权重组成,在利用用户行为计算特征向量时需要考虑以下因素

  • 用户行为的种类
    在一个网站中,用户可以对物品产生很多不同种类的行为,不同行为对物品特征的权重产生到影响不同,大多时候很难确定什么行为更加重要,一般的标准就是用户付出代价越大的行为权重越高。
  • 用户行为产生的时间
    一般来说,用户近期的行为比较重要,而用户很久之前的行为相对比较次要。
  • 用户行为的次数
    有时用户对一个物品会产生很多次行为。因此用户对同一个物品的同一种行为发生的次数也反映了用户对物品的兴趣,行为次数多的物品对应的特征权重越高。
  • 物品的热门程度
    如果用户对一个很热门的物品产生了行为,反之,如果用户对一个不热门的物品产生了行为,就说明了用户的个性需求。

对于B部分到特征-物品相关推荐而言。在得到用户的特征向量后,可以根据事先训练好的相关表候选物品集合得到初始推荐列表

离线相关表存储在数据库中,其存储格式如下:

src_id dst_id weight
特征ID 物品ID 权重

候选物品集合用于保证推荐结果只包含候选物品集合中的物品,即进行筛选。另外,特征—物品相关推荐模块除了给用户返回物品推荐列表,还需要给推荐列表中的每个推荐结果产生一个解释列表,表明这个物品是因为哪些特征推荐出来的。

在得到初步的推荐列表后,接着按照产品需求对结果进行过滤,过滤掉那些不符合要求的物品。

候选物品集合与过滤都可以对推荐物品进行筛选,那么应该如何选用呢?
一般来说,如果可供推荐的物品较少,那么可以考虑候选物品集合的方法。但是如果可供推荐的物品非常多,那么可以考虑在初始推荐列表中加上过滤模块筛选掉一些不满足条件的物品。
它们最主要的区别在于候选物集合会影响初始推荐列表的生成,而过滤模块是在初始推荐列表上进行操作的。过滤模块可以对推荐结果进行比候选物集合更加精细的控制。

一般来说,过滤模块会过滤掉以下物品:

  • 用户已经产生过行为的物品
    因为推荐系统的目的是帮助用户发现物品,因此没必要给用户推荐他已经知道的物品;
  • 候选物品以外的物品
    候选物品集合一般有两个来源,一个是产品需求,另一个是用户的选择,过滤模块需要过滤掉不满足这两个条件的物品
  • 某些质量很差的物品
    为了提高用户的体验,推荐系统需要给用户推荐质量好的物品,那么对于一些绝大多数用户反馈都很差的物品,推荐系统需要过滤掉。

经过过滤后的推荐结果可以在进行排名,一般排名模块需要包括很多不同的子模块,例如:

  • 新颖性排名
    新颖性排名模块的目的是给用户尽量推荐他们不知道的、长尾中的物品。例如通过使用如下公式对推荐结果中热门的物品进行降权: p u i = p u i log ⁡ ( 1 + α ⋅ p o p u l a r i t y ( i ) ) p_{ui}=\frac{p_{ui}}{\log(1+\alpha\cdot popularity(i))} pui=log(1+αpopularity(i))pui此外,也可以引入内容相似度矩阵,因为内容相似度矩阵中与每个物品都相似的物品可以看作不热门物品;
  • 内容多样性
    一是可以将推荐结果按照某种物品的内容属性分成几类,然后在每个类中都选择该类中排名最高的物品进行组合;二是可以让推荐结果尽量来自不同的特征。
  • 时间多样性
    提高时间多样性最关键的地方在于保证推荐系统对用户行为响应的实时性;其次是要在用户没有新的行为时,保证推荐结果每天都有变化,一种实现方法是:记录用户曾经看过的推荐结果,然后对当前推荐结果中将已经看过的推荐结果进行降权。
  • 用户反馈
    用户反馈模块主要通过分析用户之前和推荐结果的交互日志,预测用户会对什么样的推荐结果比较感兴趣。

6. 全书代码实现

书中有很多关于推荐系统的算法片断,作者Magic-Bubble在他的github:RecommendSystemPractice 对全书的代码做了较好的总结,可以参考实现。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/38791.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注