转载:/p/319e4933c5ba
对于推荐系统,本文总结内容,如下图所示:
推荐系统.png
文章很长,你可以跳着看你感兴趣的部分。
一、什么是推荐系统
1. 为什么需要推荐系统
结论是,为了解决互联网时代下的信息超载问题。
看个数据:
据IDC《数字宇宙》的研究报告表明, 年全球新建和复制的信息量将超过40ZB,是的12倍;中国的数据量在超过8ZB,比增长22倍。
单位换算是这样的:
1ZB = 1024 EB;
1EB = 1024 PB;
1PB = 1024 TB;
1TB = 1024 GB;
1GB = 1024 MB;
即便坐拥海量信息,用户却无法找到真正对自己有用的,可见效率之低。
从前,人们是这样解决信息超载问题的:
现实中,我有个东西想买(有明确目的)
小便利店 --> 凭经验浏览所有货架;大型超市 --> 借助分类指示牌;
不知道买啥(没有明确目的)
空间大,随便逛
引申到互联网,有明确目的时
电商网站 --> 搜索引擎,信息检索;
没有明确目的时
巴掌大的地儿,靠个性化推荐
信息超载,不是互联网独有的,在现实生活也会存在这样的问题,毕竟人的大脑同时能够处理的信息只有4-7个,我们面对的问题从来没有变过,区别在于当下的情况,所处的环境。
正如《大数据时代》中作者所言,这仅仅是一个开始,人们与世界的交流方式,从原来对因果关系的渴求,转变为现在对相关关系的发现和使用上。
2. 搜索引擎与推荐系统
众所周知,解决信息过载问题,最有代表性的解决方案是【分类目录】和【搜索引擎】,这两种解决方案分别催生了互联网领域的两家著名公司--雅虎和谷歌。
搜索引擎
分类目录,是将著名网站分门别类,从而方便用户根据类别查找公司。
但随着互联网规模不断扩大,分类目录网站只能涵盖少数热门网站,已无法满足用户需求。因此,搜索引擎诞生了。
搜索引擎,用户通过输入关键字,查找自己需要的信息。
但是,用户必须主动提供准确的关键词,才能找到信息。所以用户的其他需求,比如用户无法找到准确描述自己需求的关键词时,搜索引擎就无能为力了。
推荐系统,和搜索引擎一样,是一种帮助用户快速发展有用信息的工具。通过分析用户的历史行为,给用户的兴趣建模,从而主动给用户推荐能够满足他们兴趣和需求的信息。
并且,推荐系统能够很好的发掘物品的长尾,挑战传统的2/8原则(80%的销售额来自20%的热门品牌)。
从技术角度来看,搜索引擎和推荐系统的区别在于:
1)搜索引擎,注重搜索结果之间的关系和排序;
2)推荐系统,需要研究用户的兴趣模型,利用社交网络的信息进行个性化的计算;
3)搜索引擎,由用户主导,需要输入关键词,自行选择结果。如果结果不满意,需要修改关键词,再次搜索;
4)推荐系统,由系统主导,根据用户的浏览顺序,引导用户发现自己感兴趣的信息;
3. 推荐系统的定义
推荐系统通过发掘用户的行为,找到用户的个性化需求,从而将长尾物品准确推荐给需要它的用户,帮助用户找到他们感兴趣但很难发现的物品。
高质量的推荐系统会使用户对系统产生依赖,因此,推荐系统不仅能为用户提供个性化服务,还能与用户建立长期稳定的关系,提高用户忠诚度,防止用户流失。
二、推荐系统评测
如何判定什么是好的推荐系统?这是评测需要解决的首要问题。
一般推荐系统的参与方有3个:
用户物品提供商推荐系统提供网站
因此,评测一个推荐系统时,需要考虑3方的利益,一个好的推荐系统是能够令三方共赢的系统。
推荐系统评测,总结图如下:
推荐系统评测.png
1. 实验方法
获得评测指标的实验方法,通常分3种:
离线实验(offline experiment)用户调查(user study)在线实验(online experiment)
我们分别介绍3种实验方法的优缺点。
1)离线实验
离线实验的方法的步骤如下:
a)通过日志系统获得用户行为数据,并按照一定格式生成一个标准的数据集;
b)将数据集按照一定的规则分成训练集和测试集;
c)在训练集上训练用户兴趣模型,在测试集上进行预测;
d)通过事先定义的离线指标,评测算法在测试集上的预测结果。
从以上步骤看出,离线实验的都是在数据集上完成的。意味着,它不需要一个实际的系统作为支撑,只需要有一个从日志中提取的数据集即可。
离线实验的优点是:
不需要有对实际系统的控制权;不需要用户参与实践;速度快,可以测试大量算法;
缺点是:
数据集的稀疏性限制了适用范围,例如一个数据集中没有包含某用户的历史行为,则无法评价对该用户的推荐结果;评价结果的客观性,无法得到用户主观性的评价;难以找到离线评价指标和在线真实反馈(如 点击率、转化率、点击深度、购买客单价、购买商 品类别等)之间的关联关系;
2)用户调查
用户调查需要一些真实的用户,让他们在需要测试的推荐系统上完成一些任务。在他们完成任务时,需要观察和记录用户的行为,并让他们回答一些问题。
最后,我们通过分析他们的行为和答案,了解测试系统的性能。
用户调查的优点是:
可以获得用户主观感受的指标,出错后容易弥补;
缺点是:
招募测试用户代价较大;无法组织大规模的测试用户,统计意义不足;
3)在线实验
在完成离线实验和用户调查之后,可以将系统上线做AB测试,将它和旧算法进行比较。
在线实验最常用的评测算法是【A/B测试】,它通过一定的规则将用户随机分成几组,对不同组的用户采用不同的算法,然后通过统计不同组的评测指标,比较不同算法的好坏。
它的核心思想是:
a) 多个方案并行测试;
b) 每个方案只有一个变量不同;
c) 以某种规则优胜劣汰。
其中第2点暗示了A/B 测试的应用范围:A/B测试必须是单变量。
对于推荐系统的评价中,唯一变量就是--推荐算法。
有个很棒的网站,,里面有很多通过实际AB测试提高网站用户满意度的例子。
AB测试的优点是:
可以公平获得不同算法实际在线时的性能指标,包括商业上关注的指标;
缺点是:
周期较长,必须进行长期的实验才能得到可靠的结果;
大型网站做AB测试,可能会因为不同团队同时进行各种测试对结果造成干扰,所以切分流量是AB测试中的关键。
不同的层以及控制这些层的团队,需要从一个统一的地方获得自己AB测试的流量,而不同层之间的流量应该是正交的。
AB测试系统.png
4)总结
一般来说,一个新的推荐算法最终上线,需要完成上述的3个实验。
首先,通过离线实验证明它在很多离线指标上优于现有的算法;其次,通过用户调查确定用户满意度不低于现有的算法;最后,通过在线AB测试确定它在我们关心的指标上优于现有的算法;
2. 评测指标
评测指标用于评测推荐系统的性能,有些可以定量计算,有些只能定性描述。
1)用户满意度
用户满意度是评测推荐系统的重要指标,无法离线计算,只能通过用户调查或者在线实验获得。
调查问卷,需要考虑到用户各方面的感受,用户才能针对问题给出准确的回答。
在线系统中,用户满意度通过统计用户行为得到。比如用户如果购买了推荐的商品,就表示他们在一定程度上满意,可以用购买率度量用户满意度。
一般情况,我们可以用用户点击率、停留时间、转化率等指标度量用户的满意度。
2)预测准确度
预测准确度,度量的是推荐系统预测用户行为的能力。 是推荐系统最重要的离线评测指标。
大部分的关于推荐系统评测指标的研究,都是针对预测准确度的。因为该指标可以通过离线实验计算,方便了学术界的研究人员。
由于离线的推荐算法有不同的研究方向,准确度指标也不同,根据研究方向,可分为:预测评分准确度和TopN推荐。
a)预测评分准确度
预测评分的准确度,衡量的是算法预测的评分与用户的实际评分的贴近程度。
这针对于一些需要用户给物品评分的网站。
预测评分的准确度指标,一般通过以下指标计算:
平均绝对误差(MAE)
MAE.png
MAE因其计算简单、通俗易懂得到了广泛的应用。但MAE指标也有一定的局限性,因为对MAE指标贡献比较大的往往是那种很难预测准确的低分商品。
所以即便推荐系统A的MAE值低于系统B,很可能只是由于系统A更擅长预测这部分低分商品的评分,即系统A比系统B能更好的区分用户非常讨厌和一般讨厌的商品,显然这样区分的意义不大。
均方根误差(RMSE)
RMSE.png
Netflix认为RMSE加大了对预测不准的用户物品评分的惩罚(平方项的惩罚),因而对系统的评测更加苛刻。
研究表明,如果评分系统是基于整数建立的(即用户给的评分都是整数),那么对预测结果取整数会降低MAE的误差。
b)TopN推荐
网站提供推荐服务时,一般是给用户一个个性化的推荐列表,这种推荐叫做TopN推荐。
TopN推荐的预测准确率,一般通过2个指标度量:
准确率(precision)
召回率(recall)
R(u)是根据用户在训练集上的行为给用户做出的推荐列表,T(u)是用户在测试集上的行为列表。
TopN推荐更符合实际的应用需求,比如预测用户是否会看一部电影,比预测用户看了电影之后会给它什么评分更重要。
3)覆盖率
覆盖率(coverage)是描述一个推荐系统对物品长尾的发掘能力。
最简单的定义是,推荐系统推荐出来的物品占总物品的比例。
假设系统的用户集合为U,推荐系统给每个用户推荐一个长度为N的物品列表R(u),覆盖率公式为:
覆盖率是内容提供者关心的指标,覆盖率为100%的推荐系统可以将每个物品都推荐给至少一个用户。
除了推荐物品的占比,还可以通过研究物品在推荐列表中出现的次数分布,更好的描述推荐系统的挖掘长尾的能力。
如果分布比较平,说明推荐系统的覆盖率很高;如果分布陡峭,说明分布系统的覆盖率较低。
信息论和经济学中有两个著名指标,可以定义覆盖率:
信息熵
p(i)是物品i的流行度除以所有物品流行度之和。
基尼系数(Gini Index)
p(ij)是按照物品流行度p()从小到大排序的物品列表中第j个物品。
评测马太效应
马太效应,是指强者越强,弱者越弱的效应。推荐系统的初衷是希望消除马太效应,使得各物品都能被展示给对它们感兴趣的人群。
但是,很多研究表明,现在的主流推荐算法(协同过滤)是具有马太效应的。评测推荐系统是否具有马太效应可以使用基尼系数。
如,G1是从初始用户行为中计算出的物品流行度的基尼系数,G2是从推荐列表中计算出的物品流行度的基尼系数,那么如果G1<G2,就说明推荐算法具有马太效应。
4)多样性
为了满足用户广泛的兴趣,推荐列表需要能够覆盖用户不同兴趣的领域,即需要具有多样性。
多样性描述了推荐列表中物品两两之间的不相似性。假设s(i,j)在[0,1]区间定义了物品i和j之间的相似度,那么用户u的推荐列表R(u)的多样性定义如下:
推荐系统整体多样性可以定义为所有用户推荐列表多样性的平均值:
5)新颖性
新颖性也是影响用户体验的重要指标之一。它指的是向用户推荐非热门非流行物品的能力。
评测新颖度最简单的方法,是利用推荐结果的平均流行度,因为越不热门的物品,越可能让用户觉得新颖。
此计算比较粗糙,需要配合用户调查准确统计新颖度。
6)惊喜度
推荐结果和用户的历史兴趣不相似,但却让用户满意,这样就是惊喜度很高。
目前惊喜度还没有公认的指标定义方式,最近几年研究的人很多,深入研究可以参考一些论文。
7)信任度
如果用户信任推荐系统,就会增加用户和推荐系统的交互。
提高信任度的方式有两种:
增加系统透明度
提供推荐解释,让用户了解推荐系统的运行机制。
利用社交网络,通过好友信息给用户做推荐
通过好友进行推荐解释
度量信任度的方式,只能通过问卷调查。
8)实时性
推荐系统的实时性,包括两方面:
实时更新推荐列表满足用户新的行为变化;将新加入系统的物品推荐给用户;
9)健壮性
任何能带来利益的算法系统都会被攻击,最典型的案例就是搜索引擎的作弊与反作弊斗争。
健壮性(robust,鲁棒性)衡量了推荐系统抗击作弊的能力。
的推荐系统大会专门有一个推荐系统健壮性的教程,作者总结了很多作弊方法,最著名的是行为注入攻击(profile injection attack)。
就是注册很多账号,用这些账号同时购买A和自己的商品。此方法针对亚马逊的一种推荐方法,“购买商品A的用户也经常购买的其他商品”。
评测算法的健壮性,主要利用模拟攻击:
a)给定一个数据集和算法,用算法给数据集中的用户生成推荐列表;
b)用常用的攻击方法向数据集中注入噪声数据;
c)利用算法在有噪声的数据集上再次生成推荐列表;
d)通过比较攻击前后推荐列表的相似度评测算法的健壮性。
提高系统健壮性的方法:
选择健壮性高的算法;选择代价较高的用户行为,如购买行为比浏览行为代价高;在使用数据前,进行攻击检测,从而对数据进行清理。
10)商业目标
设计推荐系统时,需要考虑最终的商业目标。不同网站具有不同的商业目标,它与网站的盈利模式息息相关。
总结:
作者认为,对于可以离线优化的指标,在给定覆盖率、多样性、新颖性等限制条件下,应尽量优化预测准确度。
3. 评测维度
增加评测维度的目的,就是知道一个算法在什么情况下性能最好。
一般评测维度分3种:
用户维度
主要包括用户的人口统计学信息、活跃度以及是不是新用户等;物品维度
包括物品的属性信息、流行度、平均分以及是不是新加入的物品等;时间维度
包括季节,是工作日还是周末,白天还是晚上等;
如果推荐系统的评测报告中,包含了不同维度下的系统评测指标,就能帮我们全面了解系统性能。
三、推荐算法通用模型
1. 推荐算法通用模型
推荐系统有3个重要的模块:
用户建模模块推荐对象建模模块推荐算法模块
通用的推荐系统模型流程如图,技术一点的描述过程如下:
a)推荐系统通过用户行为,建立用户模型;
b)通过物品的信息,建立推荐对象模型;
c)通过用户兴趣匹配物品的特征信息,再经过推荐算法计算筛选,找到用户可能感兴趣的推荐对象,然后推荐给用户。
用户建模模块
建立用户模型之前,需要考虑下面几个问题:
(1)模型的输入数据有哪些,如何获取模型的输入数据。
(2)如何考虑用户的兴趣及需求的变化。
(3)建模的对象是谁。
(4)如何建模。
(5)模型的输出是什么。
获取用户信息就是解决模型输入数据的问题,输入数据主要有以下几种:
(1)用户属性:人口统计学信息;
(2)用户手动输入的信息:包括用户在搜索引擎中输入的关键词,用户反馈的信息,对推荐对象的喜好程度等;
(3)用户的浏览行为和浏览内容:包括浏览次数、频率、停留时间等,浏览页面时的操作(收藏、保存、复制等)等。服务器端保存的日志也能较好地记录用户的浏览行为和内容。
(4)推荐对象的属性特征:不同的推荐对象,用户建模的输入数据也不同。网页等推荐对象通常考虑对象的内容和用户之间的相似性,而产品等推荐对象通常考虑用户对产品的评价。
为提高推荐质量,推荐对象的相关的属性也要考虑进去,比如除网页内容以外,还要考虑网页的发布人、时间等。
产品类的对象还要考虑产品的品牌、价格、出售时间等。
获取模型输入数据的方式有显式获取、隐式获取和启发式获取三种方式。
用户模型的建模方法主要有遗传算法、基于机器学习的 方法,例如 TF-IDF、自动聚类、贝叶斯分类器、决策树归纳和神经网络方法等。
推荐对象建模
考虑以下几个问题:
(1)提取推荐对象的什么特征,如何提取,提取的特征用于什么目的。
(2)对象的特征描述和用户文件描述之间有关联。
(3)提取到的每个对象特征对推荐结果会有什么影响。
(4)对象的特征描述文件能否自动更新。
2. 算法模块
目前主要的推荐算法,如下图所示。
推荐算法是整个推荐系统中最核心的部分,在很大程度上决定了推荐系统类型和性能的优劣。
四、推荐算法详述
1)基于内容的推荐
原理是基于用户感兴趣的物品A,找到和A内容信息相近的物品B。
利用用户和物品本身的内容特征,如用户的地理位置、性别、年龄,电影物品的导演、演员、发布时间等。
比如你喜欢看《怪奇物语I》,系统会给你推荐《怪奇物语II》。
所以提取推荐对象的特征,是内容推荐算法的关键。但是对于多媒体内容,如视频、音乐,很难找到它们之间的特性关联性。
基于内容的推荐的优点如下:
(1) 简单、有效,推荐结果直观,容易理解,不需要领域知识。
(2) 不需要用户的历史数据,如对对象的评价等。
(3) 没有关于新推荐对象出现的冷启动问题。
(4) 没有稀疏问题。
(5) 算法成熟,如数据挖掘、聚类分析等。
基于内容的推荐的缺点如下:
(1) 受到了推荐对象特征提取能力的限制。
比如图像、视频,没有有效的特征提取方法。即便是文本资源,特征提取也只能反应一部分内容,难以提取内容质量,会影响用户满意度。
(2) 很难出现新的推荐结果。
根据用户兴趣的喜好进行推荐,很难出现惊喜。对于时间敏感的内容,如新闻,推荐内容基本相同,体验度较差。
(3)存在新用户出现时的冷启动问题。
当新用户出现时, 系统较难获得该用户的兴趣偏好,无法进行有效推荐。
(4) 推荐对象内容分类方法需要的数据量较大。
2)协同过滤算法
仅仅基于用户行为数据设计的推荐算法,称为协同过滤算法。此方法主要根据用户对物品的历史行为,寻找用户或物品的近邻集合,以此计算用户对物品的偏好。
主要的算法分3种,最广泛应用的是基于领域的方法:
a) 基于领域的模型算法
主要包含两种算法:
i) 基于用户的协同过滤算法(UserCF)
这种算法给用户推荐和他兴趣相似的其他用户喜欢的物品。
算法步骤:
(1) 找到和目标用户兴趣相似的用户集合;
(2) 找到这个集合中的用户喜欢的,且目标用户没有听说过的物品,推荐给目标用户。
算法的关键是计算两个用户的兴趣相似度。协同过滤计算用户兴趣相似度是利用用户行为的相似度。
UserCF
计算用户相似度的方法有3种: 余弦相似性相关相似性(皮尔森系数相关)修正的余弦相似性
计算用户兴趣相似度时,要避免热门物品自带马太效应的影响。换句话说,两个用户对冷门物品采取过同样行为,更能说明他们的兴趣相似。
缺点: 用户数目越大,计算用户兴趣相似度越复杂,时间、空间复杂度的增长和用户数的增长近似于平方关系。解释性不强
ii) 基于物品的协同过滤算法(ItemCF)
这种算法给用户推荐和他之前喜欢的物品相似的物品。
该算法是目前业界应用最多的算法,如亚马逊、Netflix、YouTube,都是以该算法为基础。
ItemCF 与 基于内容的推荐算法的区别
基于内容的推荐算法,计算的是物品内容属性之间的相似度。如,电影的导演是不是同一个人;ItemCF是通过用户的行为计算物品之间的相似度。如,物品A、B具有很大相似度,是因为喜欢物品A的用户也大都喜欢物品B。
算法步骤:
(1) 根据用户的历史行为,计算物品之间的相似度;
(2) 根据物品的相似度和用户的历史行为给用户生成推荐列表。
两个物品产生相似度,是因为它们共同被很多用户喜欢,也就是说,每个用户都可以通过它们的历史兴趣列表给物品“贡献”相似度。
ItemCF
用户活跃度对物品相似度的影响
IUF(Inverse User Frequence),用户活跃度对数的倒数的参数。
论文提出的观点是,活跃用户对物品相似度的贡献应该小于不活跃的用户。用IUF修正物品相似度的计算。
物品相似度的归一化
研究表明,将ItemCF的相似度矩阵按最大值归一,可以提高推荐的准确率。
UserCF 与 ItemCF 的优缺点
b) 隐语义模型算法
LFM(latent factor model)隐语义模型是最近几年推荐系统领域最热门的话题,它的核心思想是通过隐含特征联系用户兴趣和物品。
i)隐语义模型解决了什么问题
比如,用户A的兴趣列表里,有关于侦探小说、科普图书和计算机技术图书。用户B的兴趣列表集中在数学和机器学习方面。
如何给用户A和B推荐图书?
除了UserCF与ItemCF,还可以对书和物品的兴趣进行分类。对于某个用户,首先得到他的兴趣分类,然后从分类中挑选他可能喜欢的物品。
基于兴趣分类的方法,大概需要解决的问题:
如何给物品进行分类?如何确定用户对哪类物品感兴趣,以及感兴趣程度?对于一个给定的分类,选择哪些属于这个类的物品推荐给用户,以及如何确定这些物品在一个类中的权重?
人工编辑分类存在的问题:
编辑的意见不能代表各种用户的意见。编辑很难控制分类的粒度。编辑很难给一个物品多个分类。编辑很难给出多维度的分类。编辑很难决定一个物品在某一个分类的权重。
隐语义分析技术解决了上述5个问题:
用户的行为代表了用户对物品分类的看法。比如,如果两个物品被很多用户同时喜欢,这个两个物品很可能属于同一类。隐语义技术允许我们指定最终的分类数目,分类数越多,分类粒度越细。隐语义技术可以计算出物品属于每个类的权重,因为每个物品不是硬性地被分到一个类目中。隐语义技术给出的每个分类都不是一个维度,它根据用户的共同兴趣计算得出。隐语义技术可以通过统计用户行为决定物品在每个类中的权重,如果喜欢某个类的用户都会喜欢某个物品,那么这个物品在这个类中的权重就可能较高。
隐语义技术有很多著名的模型和方法,其中耳熟能详的名词有pLSA、LDA、隐含类别模型、隐含主题模型、矩阵分解。这些技术和方法在本质上是相同的,都可以用于个性化推荐系统。
ii)LFM算法详解
LFM公式
推荐系统的用户行为分为显性反馈和隐性反馈,LFM在显性反馈数据(评分数据)上解决评分预测问题达到了很好的精度。
对于隐性反馈数据,这种数据集的特点是,只有正样本(用户喜欢什么物品),没有负样本(用户对什么物品不感兴趣)。
在隐性反馈数据集上应用LFM解决TopN推荐,第一个关键问题是如何给每个用户生成负样本。
对于这个问题,Rong Pan在文章中做了很多探讨,对比了如下几种方法: 1)对于一个用户,用他所有没有过行为的物品作为负样本。2)对于一个用户,从他没有过行为的物品中均匀采样出一些物品作为负样本。3)对于一个用户,从他没有过行为的物品中采样出一些物品作为负样本,但采样时,保证每个用户的正负样本数目相当。4)对于一个用户,从他没有过行为的物品中采样出一些物品作为负样本,但采样时,偏重采样不热门的物品。
对于1),它的明显缺点是负样本太多,正负样本数目相差悬殊,因而计算复杂度很高,最终结果的精度也很差。另外三种方法的效果,作者表示,3)> 2)> 4)。
对负样本的采样还应该遵循以下原则: 对每个用户,要保证负样本的平衡(数目相似)对每个用户采样负样本时,要选取那些很热门,而用户却没有行为的物品。
通过离线实验对比LFM在TopN推荐中的性能,在LFM中,有4个重要参数:
隐特征的个数F;学习速率alpha;正则化参数lambda;负样本/正样本比例ratio;
实验表明,ratio参数对LFM的性能影响最大。
iii)基于LMF的实际系统的例子
雅虎的研究人员公布过一个使用LFM进行雅虎首页个性化设计的方案。
LFM的缺点是,很难实现实时的推荐。
经典的LFM模型每次训练时,需要扫描所有用户的行为记录,这样才能计算出用户隐类向量和物品隐类向量。所以一般每天只训练一次。
雅虎的解决方案是:
利用新闻链接的内容属性(关键词、类别等)得到链接的内容特征向量;实时收集用户对链接的行为,并用这些数据得到链接的隐特征向量;利用公式预测用户是否会单击链接。
iiii)LFM和基于领域的方法区别
总结如下图:
c) 基于图的模型
用户行为很容易用二分图表示,因此很多图的算法都可以用到推荐系统中。也可以把基于领域的模型看做是基于图的模型的简单形式。
i)用户行为数据的二分图表示
基于图的模型(graph-based model)是推荐系统中的重要内容,其基本思想是将用户行为数据表示为一系列的二元组。
每一个二元组(u,i)代表用户u对物品 i 产生过行为,这样便可以将这个数据集表示为一个二分图。
下图是一个简单的用户物品二分图模型,其中圆形节点代表用户,方形节点代表物品,圆形节点和方形节点之间的边代表用户对物品的行为。比如图中用户节点A和物品节点a、b、d相连,说明用户A对物品a、b、d产生过行为。
ii)基于图的推荐算法
基于用户行为二分图,给用户u推荐物品,可以转化为计算用户顶点u和与所有物品顶点之间的相关性,然后取与用户没有直接边相连的物品,按照相关性的高低生成推荐列表。
其实,这是一个图上的排名问题,最著名的就是Google的pageRank算法。
度量图中两个顶点之间相关性,一般取决于3个因素:
两个顶点之间的路径数;两个顶点之间的路径长度;两个顶点之间的路径经过的顶点;
相关性高的两个顶点,一般具有以下特征:
两个顶点之间有很多路径相连;链接两个顶点之间的路径长度都比较短;链接两个顶点之间的路径不会经过出度比较大的顶点。
iii)PageRank算法简介
PageRank是Larry Page 和 Sergey Brin设计的,用来衡量特定网页相对于搜索引擎中其他网页的重要性的算法,其计算结果作为Google搜索结果中网页排名的重要指标。
网页之间通过超链接相互连接,互联网上不计其数的网页就构成了一张超大的图。
PageRank假设用户从所有网页中随机选择一个网页进行浏览,然后通过超链接在网页直接不断跳转。到达每个网页后,用户有两种选择:到此结束或者继续选择一个链接浏览。
算法令用户继续浏览的概率为d,用户以相等的概率在当前页面的所有超链接中随机选择一个继续浏览。
这是一个随机游走的过程。
当经过很多次这样的游走之后,每个网页被访问用户访问到的概率就会收敛到一个稳定值。这个概率就是网页的重要性指标,被用于网页排名。算法迭代关系式如下所示:
上式中PR(i)是网页i的访问概率(也就是重要度),d是用户继续访问网页的概率,N是网页总数。in(i)表示指向网页i的网页集合,out(j)表示网页j指向的网页集合。
iiii)PersonalRank算法简介
对于推荐系统,我们需要计算的是物品节点相对于某一个用户节点u的相关性。
Standford的Haveliwala于2002年在他《Topic-sensitive pagerank》一文中提出了PersonalRank算法,该算法能够为用户个性化的对所有物品进行排序。它的迭代公式如下:
我们发现PersonalRank跟PageRank的区别只是用ri替换了1/N,也就是说从不同点开始的概率不同。
我们重新描述一下算法的过程:
假设要给用户u进行个性化推荐,可以从用户u对应的节点Vu开始在用户物品二分图上进行随机游走。
游走到任何一个节点时,首先按照概率α决定是继续游走,还是停止这次游走并从Vu节点开始重新游走。如果决定继续游走,那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。
这样,经过很多次随机游走后,每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。
缺点
PersonalRank每次都需要在全图迭代,所以时间复杂度非常高。
解决办法是, 减少迭代次数,在收敛前停止。会影响精度,但影响不大。从矩阵论出发,重新设计算法。
3)基于关联规则的推荐
主要用于购物车分析。
(以下内容摘自网络)
关联规则是反映一个事物与其他事物之间的相互依存性和关联性,常用于实体商店或在线电商的推荐系统:通过对顾客的购买记录数据库进行关联规则挖掘,最终目的是发现顾客群体的购买习惯的内在共性。
例如购买产品A的同时也连带购买产品B的概率,根据挖掘结果,调整货架的布局陈列、设计促销组合方案,实现销量的提升,最经典的应用案例莫过于<啤酒和尿布>。
关联规则分析中的关键概念包括:支持度(Support)、置信度(Confidence)与提升度(Lift)。首先,我们简单温故下这3个关键指标~
1、支持度 (Support):支持度是两件商品(A∩B)在总销售笔数(N)中出现的概率,即A与B同时被购买的概率。类似于中学学的交集,需要原始同时满足条件。
公式:
例子说明:
比如某超市有100w笔销售,顾客购买可乐又购买薯片有20w笔,顾客购买可乐又购买面包有10w笔,那可乐和薯片的关联规则的支持度是20%,可乐和面包的支持度是10%。
2、置信度 (Confidence):置信度是购买A后再购买B的条件概率。简单来说就是交集部分C在A中比例,如果比例大说明购买A的客户很大期望会购买B商品。
公式:
例子说明:
某超市可乐购买次数40w笔,购买可乐又购买了薯片是30w笔,顾客购买可乐又购买面包有10w笔,则购买可乐又会购买薯片的置信度是75%,购买可乐又购买面包的置信度是25%,这说明买可乐也会买薯片的关联性比面包强,营销上可以做一些组合策略销售。
3、提升度 (Lift):提升度表示先购买A对购买B的概率的提升作用,用来判断规则是否有实际价值,即使用规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效,小于1则无效。
公式:
例子说明:
可乐和薯片的关联规则的支持度是20%,购买可乐的支持度是3%,购买薯片的支持度是5%,则提升度是1.33>1, A-B规则对于商品B有提升效果。
4)基于知识推荐
基于知识的推荐(Knowledge-based Recommendation),主要应用于知识型的产品中,主要解决的问题是,为你量身定制升级打怪的进阶路线图。
比如你想学习钢琴,如果你是刚入门的小白,那你最好从简单的谱子学起。但这样带来一个问题,是因为你的历史行为都在初级范围之内,根据兴趣偏好,推荐给你的信息也都在初级范围。无法满足你的升级需求。
这个时候就需要基于知识的推荐。推荐系统知道你现在所处的知识级别(用户知识),也知道学习钢琴所有的级别(产品知识),然后根据你现在的情况为你推荐适合你进阶的信息。
以上为个人理解,百度百科的解释为:
使用用户知识和产品知识, 通过推理什么产品能满足用户需求来产生推荐。这种推荐系统不依赖于用户评分等关于用户偏好的历史数据, 故其不存在冷启动方面的问题。基于知识的推荐系统响应用户的即时需求, 当用户偏好发生变化时不需要任何训练。
举例:
针对海量习题带来的信息过载导致学习针对性不强、效率不高等问题,提出了基于知识点层次图的个性化习题推荐算法(A Personalized Exercises Recommendation Algorithm based on Knowledge Hierarchical Graph,ReKHG)。
首先,借鉴课程知识点体系结构的特点,构建了表征知识点层次关系的权重图,该权重图有效反映知识点间的层次关系。
然后,根据学生对知识点的掌握情况,在知识点层次图的基础上提出了一种个性化习题推荐算法。该算法通过更新学生-知识点失分率矩阵,获取学生掌握薄弱的知识点,以此实现习题推荐。
ps:以上举例来自于某论文,没有用于实际案例中。关于知识推荐,没有找到太多实际案例,国外的论文论述的比较多一些。
5)混合推荐
每个算法都不是完美的,因此实际应用中,可以混合使用各种推荐算法,各取所长。
五、推荐算法数据来源
1. 利用用户行为信息
用户行为数据一般存于日志中。
用户行为可以分为:显性反馈行为和隐性反馈行为。
互联网上的很多数据分布满足一种称为Power Law的分布,称为长尾分布。
2. 利用用户标签数据
推荐系统联系用户和物品的几种途径
推荐系统的目的是联系用户的兴趣和物品,这种联系需要依赖不同的媒介。目前流行的有3种方式:物品、用户、特征。
前两种我们都很熟悉,特征有不同的表现形式,可以是物品的属性集合,可以是隐语义向量,这里我们用标签表示。
标签分两类 让作者或者专家给物品打标签让普通用户给物品打标签,即UGC标签应用,既描述了用户的兴趣又将表达了物品的语义。
以豆瓣为例,打标签作为一种用户重要的行为,蕴含了丰富的用户兴趣信息。
标签推荐系统算法
统计每个用户最常用的标签对于每个标签,统计被打过这个标签次数最多的物品对于一个用户,首先找到他常用的标签,然后找到具有这些标签的最热门物品推荐给这个用户
算法改进:
TF-IDF,降低热门标签的权重,使推荐结果更准确数据稀疏性:对于新用户或者新物品来说,其标签数量可能过少,需要对标签进行扩展,即对每个标签找到和它相似的标签,也就是计算标签相似度。(拓展方法--话题模型)标签清理:清理掉同义词、无义词,方便做出推荐解释
给用户推荐标签
推荐的好处
方便用户输入标签提高标签质量
推荐方法
推荐系统中最热门的标签(PopularTags)推荐物品最热门的标签(Item PopularTags)推荐用户经常使用的标签(User PopularTags)前面两种融合(Hybrid PopularTags)
冷启动物品的推荐方法
从物品的内容数据中抽取关键词作为标签根据仅有的标签做拓展
3. 利用上下文信息
用户所处的上下文,包括用户访问推荐系统的时间、地点、心情等,有助于提高推荐系统的性能。
比如,用户夏天喜欢过的T恤,冬天再推荐就不合适了。
用户在中关村,打开美食推荐,如果给的结果是国贸是不合适了。
1) 时间上下文信息
时间对用户兴趣的影响:
用户兴趣是变化的物品也是有生命周期的季节效应
推荐系统的实时性
用户兴趣是不断变化的,其变化体现在用户不断增加的新行为中。一个实时的推荐系统需要能够实时响应用户新的行为,让推荐列表不断变化,从而满足用户不断变化的兴趣。
实现推荐系统的实时性除了对用户行为的存取有实时性要求,还要求推荐算法本身具有实时性,而推荐算法本身的实时性意味着:
实时推荐系统不能每天都给所有用户离线计算推荐结果,然后在线展示昨天计算出来的结果。所以,要求在每个用户访问推荐系统时,都根据用户这个时间点前的行为实时计算推荐列表推荐算法需要平衡考虑用户的近期行为和长期行为,即要让推荐列表反应出用户近期行为所体现的兴趣变化,又不能让推荐列表完全受用户近期行为的影响,要保证推荐列表对用户兴趣预测的延续性。
推荐算法的时间多样性
推荐系统每天推荐结果的变化程度被定义为推荐系统的时间多样性。时间多样性高的推荐系统中用户会经常看到不同的推荐结果。
提高推荐结果的时间多样性需要分两步解决:
首先,需要保证推荐系统能够在用户有了新的行为后及时调整推荐结果,使推荐结果满足用户最近的兴趣;其次,需要保证推荐系统在用户没有新的行为时也能经常变化一下结果,具有一定的时间多样性
如果用户没有行为,推荐思路:
在生成推荐结果时加入一定的随机性。比如从推荐列表前20个结果中随机挑选10个结果展示给用户,或者按照推荐物品的权重采样10个结果展示给用户。记录用户每天看到的推荐结果,然后在每天给用户进行推荐时,对他前几天看到过很多次的推荐结果进行适当地降权。每天给用户使用不同的推荐算法。可以设计很多推荐算法,比如协同过滤算法、内容过滤算法等,然后在每天用户访问推荐系统时随机挑选一种算法给他进行推荐。
协同过滤算法可以利用时间信息提高预测的准确度。
时间上下文相关的ItemCF算法
物品相似度
用户在相隔很短的时间内喜欢的物品具有更高相似度。在线推荐
用户近期的行为比用户很久之前的行为,更能体现用户现在的兴趣。
时间上下文相关的UserCF算法
用户兴趣相似度
如果两个用户【同时】喜欢相同的物品,则他们有更大的兴趣相似度。相似兴趣用户的最近行为
给用户推荐和他兴趣相似的用户最近喜欢的物品。
2)地点上下文信息
用户兴趣和地点相关的两种特征: 兴趣本地化,不同地方的用户兴趣存在着很大的差别,不同国家和地区用户的兴趣存在着一定的差异性。活动本地化,一个用户往往在附近的地区活动。因此,在基于位置的推荐中我们需要考虑推荐地点和用户当前地点的距离,不能给用户推荐太远的地方。
4. 利用社交网络数据
获取社交网络数据的途径
电子邮件用户注册信息用户位置数据论坛和讨论组即时聊天工具社交网站 Facebook中的绝大多数用户联系基于社交图谱:由于人们之间的亲属关系、工作关系而形成;Twitter中的绝大多数用户联系基于兴趣图谱:通过人们之间的共同兴趣和信念形成;
社交网络数据的分类
双向确认的社交网络数据,以Facebook和人人网为代表,用户之间形成好友关系需要通过双方的确认;单向关注的社交网络数据,以Twitter和新浪微博为代表,用户A可以关注用户B,而不用得到用户B的允许;基于社区的社交网络数据,用户之间并没有明确的关系,但是这种数据包含了用户属于不同社区的数据。比如豆瓣小组,属于同一个小组可能代表了用户兴趣的相似性;
社会化推荐的优点
好友推荐可以增加推荐的信任度社交网络可以解决冷启动问题
六、冷启动问题
1)冷启动主要分3类:
用户冷启动
一个新用户,没有任何历史行为数据,怎么做推荐。物品冷启动
一个新上线的物品,没有用户对它产生过行为,怎么推荐给感兴趣的用户。系统冷启动
一个新开发的网站,没有用户数据,怎么做个性化推荐。
2)解决方案:
提供非个性化推荐,如热门排行。等有了数据之后再推荐。利用用户注册信息,做粗粒度的个性化。利用用户的社交网络账号,导入用户的好友,推荐好友喜欢的物品。用户初次登录时,对一些物品进行反馈,根据这些信息做个性化。对于新上线的物品,利用内容信息,推荐给喜欢类似物品的用户。系统冷启动,可以引入外部资源,如专家知识,建立起物品的相关度。
3)冷启动,启动用户兴趣的物品需要具有以下特点:
比较热门具有代表性和区分性启动物品集合需要有多样性
4)选择启动物品集合的系统
如何设计一个选择启动物品集合的系统?Nadav Golbandi在论文中提出用一个决策树解决。
首先,给定一群用户,用这群用户对物品评分的方差度量这群用户兴趣的一致程度。如果方差很小,说明这一群用户的兴趣不太一致,也就是物品具有比较大的区分度,反之则说明这群用户的兴趣比较一致。
再根据用户的评分方差计算物品的区分度。
也就是说,对于物品i,将用户分为3类--喜欢物品i的用户,不喜欢物品i的用户和不知道物品i的用户。如果这3类用户集合内的用户对其他的物品兴趣很不一致,说明物品i具有较高的区分度。
算法首先从所有用户中找到具有最高区分度的物品i,然后将用户分成3类。然后在每类用户中再找到最具区分度的物品,然后将每一类用户又各自分为3类,也就是将总用户分为9类,然后继续这样下去,最终可以通过对一系列物品的看法将用户进行分类。
在冷启动时,从根节点开始询问用户对该节点物品的看法,然后根据用户的选择将用户放到不同的分枝,直到进入最后的叶子节点,此时对用户的兴趣有了比较清楚的了解,从而可以开始对用户进行比较准确地个性化推荐。
5)利用物品的内容信息
就是基于内容的推荐,很适合解决物品冷启动问题。
物品冷启动对诸如新闻网站等时效性很强的网站的推荐非常重要,因为那些网站中时时刻刻都有新加入的物品,而且每个物品必须能够在第一时间展现给用户,否则经过一段时间后,物品的价值就大大降低了。
一般来说,物品的内容可以通过向量空间模型表示,该模型会将物品表示成一个关键词向量。
如果物品的内容是诸如导演、演员等实体,可以直接将实体作为关键词。
如果内容是文本,需要引入自然语言的技术抽取关键词。如何建立文章、话题和关键词的关系是话题模型研究的重点,代表性的话题模型有LDA。
LDA有3种元素,文档、话题、词语。详细内容可参考相关论文。
向量空间模型的优点是简单,缺点是丢失了一些信息,比如关键词之间的关系信息。
七、推荐系统实例
推荐系统和其他系统之间的关系
3种联系用户和物品的推荐系统
3)推荐系统架构
推荐系统需要由多个推荐引擎组成,每个推荐引擎负责一类特性和一种任务,推荐系统的任务是将推荐引擎的结果按照一定权重或者优先级合并,排序然后返回。如下图:
推荐系统架构图
优点: 方便增加或删除引擎,控制不同引擎对推荐结果的影响。可以实现推荐引擎级别的用户反馈。对不同用户给出不同引擎组合权重。
4)推荐引擎架构
推荐引擎架构主要包括三部分: 图中A部分负责从数据库或缓存中拿到用户行为数据,通过分析不同行为,生成当前用户的特征向量,如果使用非行为特征,就不需要行为提取和分析模块了,该模块的输出就是用户特征向量。图中B部分负责将用户的特征向量通过特征-物品相关矩阵转化为初始推荐物品列表。图中C部分负责对初始的推荐列表进行过滤、排名等处理,从而生成该引擎的最终推荐结果。
推荐引擎架构图
生成用户特性向量
用户行为的种类用户行为产生的时间用户行为的次数物品的热门程度
过滤模块过滤掉以下物品
用户已经产生过行为的物品候选物品以外的物品(不符合用户筛选条件的物品)某些质量很差的物品
以上,就是所有内容的总结。内容主要来自于《推荐系统实践》,以及相关论文、博客。
《推荐系统实践》中提到的papaer总结:
/review/5514664/
参考论文:
/RjXktmC
/RjXkiFP
/qingqingpiaoguo/article/details/60882309
/question/27141495/answer/161027882
作者:rui_liu
链接:/p/319e4933c5ba
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。