推荐算法之协同过滤

推荐算法在个性化领域有着广泛的应用,粗略统计,所涉及到的学科包括人工智能、机器学习、认知科学、信息抽取、数据挖掘、预测理论、近似理论,甚至是管理科学、市场营销和心理学。所使用的算法除了传统的协同过滤,还包括图模型(Graph Model)、矩阵分解(Matrix Factorization)、奇异值分解(SVD,SingularValue Decomposition)、链接分析(Link Analysis)、回归分析(Regression Analysis),以及机器学习领域各种分类和学习算法。常见的推荐算法分类如表1:

表1 推荐算法分类

推荐算法应用数据分析技术,找出用户最可能喜欢的东西推荐给用户,现在很多电子商务网站都有这个应用。目前用的比较多、比较成熟的推荐算法是协同过滤(Collaborative Filtering,简称CF)推荐算法,CF算法分为两大类,一类为基于memory的(Memory-based),另一类为基于Model的(Model-based),User-based和Item-based算法均属于Memory-based类型。CF的基本思想是根据用户之前的喜好以及其他兴趣相近的用户的选择来给用户推荐物品。

如图1所示,在CF中,用m×n的矩阵表示用户对物品的喜好情况,一般用打分表示用户对物品的喜好程度,分数越高表示越喜欢这个物品,0表示没有买过该物品。图中行表示一个用户,列表示一个物品,Uij表示用户i对物品j的打分情况。CF分为两个过程,一个为预测过程,另一个为推荐过程。预测过程是预测用户对没有购买过的物品的可能打分值,推荐是根据预测阶段的结果推荐用户最可能喜欢的一个或Top-N个物品。

基于用户(User-based)的协同过滤推荐算法原理和实现

基于用户的协同过滤推荐算法是最早诞生的,原理也较为简单。该算法1992年提出并用于邮件过滤系统,两年后1994年被GroupLens用于新闻过滤。一直到2000年,该算法都是推荐系统领域最著名的算法。

基本思想

俗话说“物以类聚、人以群分”,拿看电影这个例子来说,如果你喜欢《蝙蝠侠》、《碟中谍》、《星际穿越》、《源代码》等电影,另外有个人也都喜欢这些电影,而且他还喜欢《钢铁侠》,则很有可能你也喜欢《钢铁侠》这部电影。

所以说,当一个用户 A 需要个性化推荐时,可以先找到和他兴趣相似的用户群体 G,然后把 G 喜欢的、并且 A 没有听说过的物品推荐给 A,这就是基于用户的系统过滤算法。

原理

(1)找到与目标用户兴趣相似的用户集合;(2)找到这个集合中用户喜欢的、并且目标用户没有听说过的物品推荐给目标用户。

1. 发现兴趣相似的用户

通常用Jaccard公式或者余弦相似度计算两个用户之间的相似度。设 N(u) 为用户 u 喜欢的物品集合,N(v) 为用户 v 喜欢的物品集合,那么 u 和 v 的相似度是多少呢:

Jaccard公式:

wuv 代表用户 u 与 v 之间的兴趣相似度,N(u)表示用户 u 曾经喜欢过的物品集合, N(v) 表示用户 v 曾经喜欢过的物品集合。

余弦相似度:

脑补一下数学知识:

两个向量间的余弦值可以很容易地通过使用欧几里得点积和量级公式推导:

鉴于两个向量的属性, A 和B的余弦相似性θ用一个点积形式来表示其大小,如下所示:

产生的相似性范围从-1到1:-1意味着两个向量指向的方向正好截然相反,1表示它们的指向是完全相同的,0通常表示它们之间是独立的,而在这之间的值则表示中度的相似性或相异性。 对于文本匹配,属性向量A 和B 通常是文档中的词频向量。余弦相似性,可以被看作是一个规范比较文件长度的方法。 在信息检索的情况下,由于一个词的频率(TF-IDF权)不能为负数,所以这两个文档的余弦相似性范围从0到1。并且,两个词的频率向量之间的角度不能大于90°。

假设目前共有4个用户: A、B、C、D;共有5个物品:a、b、c、d、e。用户与物品的关系(用户喜欢物品)如下图所示:

如何一下子计算所有用户之间的相似度呢?为计算方便,通常首先需要建立“物品—用户”的倒排表,如下图所示:

然后对于每个物品,喜欢他的用户,两两之间相同物品加1。例如喜欢物品 a 的用户有 A 和 B,那么在矩阵中他们两两加1。如下图所示:

计算用户两两之间的相似度,上面的矩阵仅仅代表的是公式的分子部分。以余弦相似度为例,对上图进行进一步计算:

到此,计算用户相似度就大功告成,可以很直观的找到与目标用户兴趣较相似的用户。

2. 推荐物品

首先需要从矩阵中找出与目标用户 u 最相似的 K 个用户,用集合 S(u, K) 表示,将 S 中用户喜欢的物品全部提取出来,并去除 u 已经喜欢的物品。对于每个候选物品i,用户 u 对它感兴趣的程度用如下公式计算:

其中rvi 表示用户 v 对i的喜欢程度,在本例中都是为 1,在一些需要用户给予评分的推荐系统中,则要代入用户评分。

举个例子,假设我们要给 A 推荐物品,选取 K = 3 个相似用户,相似用户则是:B、C、D,那么他们喜欢过并且 A 没有喜欢过的物品有:c、e,那么分别计算 p(A, c) 和 p(A, e):

看样子用户 A 对 c 和 e 的喜欢程度可能是一样的,在真实的推荐系统中,只要按得分排序,取前几个物品就可以了。

整个过程可以用一张图简单的如下:

优点

以使用者的角度来推荐的协同过滤系统有下列优点:

  1. 能够过滤机器难以自动内容分析的资讯,如艺术品,音乐等。
  2. 共用其他人的经验,避免了内容分析的不完全或不精确,并且能够基于一些复杂的,难以表述的概念(如资讯品质、个人品味)进行过滤。
  3. 有推荐新资讯的能力。可以发现内容上完全不相似的资讯,使用者对推荐资讯的内容事先是预料不到的。可以发现使用者潜在的但自己尚未发现的兴趣偏好。
  4. 推荐个性化、自动化程度高。能够有效的利用其他相似使用者的回馈资讯。加快个性化学习的速度。

缺点

虽然协同过滤作为一推荐机制有其相当的应用,但协同过滤仍有许多的问题需要解决。比如一些非常流行的商品可能很多人都喜欢,这种商品推荐给你就没什么意义了,所以计算的时候需要对这种商品加一个权重或者把这种商品完全去掉也行。再有,对于一些通用的东西,比如买书的时候的工具书,如现代汉语词典,新华字典神马的,通用性太强了,推荐也没什么必要了。这些都是推荐系统的脏数据,如何去掉脏数据,这是数据预处理的时候事情了,这里就不多说了。整体而言,最典型的问题有

  1. 新使用者问题(New User Problem) 系统开始时推荐品质较差
  2. 新项目问题(New Item Problem) 品质取决于历史资料集
  3. 稀疏性问题(Sparsity)
  4. 系统延伸性问题(Scalability)。

基于物品(Item-based)的协同过滤推荐算法原理和实现

item based collaborative filtering称为基于物品的协同过滤算法,简称Item CF,是目前业界应用最广的算法。该算法给用户推荐那些和他们之前喜欢的物品相似的物品。比如,该算法会因为你购买过《数据挖掘导论》而给你推荐《机器学习》。

原理

ItemCF主要分为两步:(1)计算物品之间的相似度;(2)根据物品的相似度和用户的历史行为给用户生成推荐列表。

1物品的相似度

Item-based算法首选计算物品之间的相似度,计算相似度的方法有以下几种:

  1. 基于余弦(Cosine-based)的相似度计算,通过计算两个向量之间的夹角余弦值来计算物品之间的相似性,公式如下:

其中分子为两个向量的内积,即两个向量相同位置的数字相乘。

  1. 基于关联(Correlation-based)的相似度计算,计算两个向量之间的Pearson-r关联度,公式如下:

其中R(u,i)表示用户u对物品i的打分,Ri表示第i个物品打分的平均值。

  1. 调整的余弦(Adjusted Cosine)相似度计算,由于基于余弦的相似度计算没有考虑不同用户的打分情况,可能有的用户偏向于给高分,而有的用户偏向于给低分,该方法通过减去用户打分的平均值消除不同用户打分习惯的影响,公式如下:

其中

表示用户u打分的平均值。

2预测值计算

根据之前算好的物品之间的相似度,接下来对用户未打分的物品进行预测,有两种预测方法:

  1. 加权求和。 用过对用户u已打分的物品的分数进行加权求和,权值为各个物品与物品i的相似度,然后对所有物品相似度的和求平均,计算得到用户u对物品i打分,公式如下:

其中

为物品i与物品N的相似度,

为用户u对物品N的打分。

2.回归。

和上面加权求和的方法类似,但回归的方法不直接使用相似物品N的打分值

,因为用余弦法或Pearson关联法计算相似度时存在一个误区,即两个打分向量可能相距比较远(欧氏距离),但有可能有很高的相似度。因为不同用户的打分习惯不同,有的偏向打高分,有的偏向打低分。如果两个用户都喜欢一样的物品,因为打分习惯不同,他们的欧式距离可能比较远,但他们应该有较高的相似度。在这种情况下用户原始的相似物品的打分值进行计算会造成糟糕的预测结果。通过用线性回归的方式重新估算一个新的

值,运用上面同样的方法进行预测。重新计算

的方法如下:

其中物品N是物品i的相似物品,

通过对物品N和i的打分向量进行线性回归计算得到,

为回归模型的误差。具体怎么进行线性回归文章里面没有说明,需要查阅另外的相关文献

下图给出一个item CF的例子。用户user喜欢《C++Primer中文版》和《编程之美》两本书。然后item CF会为这两本书分别找到和它们最相似的3本书,然后根据公式的定义计算用户对每本书的感兴趣程度。

适用场景

Item CF算法,适用于item的更新不频繁,数量相对稳定且item数明显小于用户数的场景。在电影,小说等产品的推荐中,Item CF是常用的方法。亚马逊,Netflix,YouTube的推荐算法的基础都是该算法。

Item CF对应的推荐子策略为item CF,需要使用方提供用户的pvlog和物品的相关内容。目前子策略在recsys-s中未实现,不能定制。

优点

  1. 可以发现用户潜在的但自己尚未发现的兴趣爱好
  2. 有效的进行长尾挖掘
  3. 利用用户的历史行为给用户做推荐解释,使用户比较信服

缺点

  1. 依赖于用户行为,存在冷启动问题和稀疏性问题

UserCF和ItemCF的区别和应用

UserCF算法的特点

  1. 用户较少的场合,否则用户相似度矩阵计算代价很大
  2. 适合时效性较强,用户个性化兴趣不太明显的领域
  3. 对新用户不友好,对新物品友好,因为用户相似度矩阵不能实时计算
  4. 很难提供令用户信服的推荐解释

ItemCF算法的特点

  1. 适用于物品数明显小于用户数的场合,否则物品相似度矩阵计算代价很大
  2. 适合长尾物品丰富,用户个性化需求强的领域
  3. 对新用户友好,对新物品不友好,因为物品相似度矩阵不需要很强的实时性
  4. 利用用户历史行为做推荐解释,比较令用户信服

因此,可以看出UserCF适用于物品增长很快,实时性较高的场合,比如新闻推荐。而在图书、电子商务和电影领域,比如京东、天猫、优酷中,ItemCF则能极大地发挥优势。在这些网站中,用户的兴趣是比较固定和持久的,而且这些网站的物品更新速度不会特别快,一天一更新是在忍受范围内的。

参考文献

项亮 《推荐系统实践》

https://en.wikipedia.org/wiki/Collaborative_filtering

http://recsys.baidu.com/recsys/doc?tpl=index&doc=collaborativePer

http://www.cnblogs.com/technology/p/4467895.html

本文仅代表作者观点,不代表腾

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

刘建银的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

2016:深度学习统治人工智能?附深度学习十大顶级框架

2015 年结束了,是时候看看 2016 年的技术趋势,尤其是关于深度学习方面。新智元在 2015 年底发过一篇文章《深度学习会让机器学习工程师失业吗?》,引起...

3496
来自专栏机器人网

一图了解人工智能之机器学习学习路径

1. 引言 也许你和这个叫『机器学习』的家伙一点也不熟,但是你举起iphone手机拍照的时候,早已习惯它帮你框出人脸;也自然而然点开今日头条推给你的新闻;也习惯...

43913
来自专栏AI科技评论

学界 | Michael I.Jordan:AI 时代变革,源于应用场景中的优化算法

AI 科技评论按:8 月 9 日,为期两周的 2018 国际数学家大会(ICM)在里约热内卢完美谢幕,来自全球一百多个国家的 3000 多位数学家出席了本次盛会...

931
来自专栏新智元

MIT 对抗学习和无监督学习最新进展:机器学会创作视频,预测人类行为

【新智元导读】LeCun曾在演讲中提到,2016年深度学习领域最让他兴奋的技术莫过于对抗学习,而无监督学习一直都是人工智能研究者孜孜追求的“终极目标”之一。MI...

38610
来自专栏机器之心

专栏 | 情感计算是人机交互核心?谈深度学习在情感分析中的应用

竹间智能专栏 作者:竹间智能自然语言与深度学习小组 除自然语言理解(NLU)外,情感计算(Affective Computing)也成为近年来 AI 领域热门的...

3115
来自专栏AI科技评论

干货 | 重温五条 AI 基础规律

AI 科技评论按:如果每个人都有足够的时间和热诚,并乐意去大学拿个 AI 学位,那你大概就不会读到这篇博客了。 虽说 AI 的工作方式挺神秘的,但在处理技术问题...

742
来自专栏专知

【下载】面向机器智能的TensorFlow实践书籍和代码

【导读】自2015年11月TensorFlow第一个开源版本发布以来,它便迅速跻身于最激动人心的机器学习库的行列,并在科研、产品和教育等领域正在得到日益广泛的应...

4048
来自专栏新智元

微软研究院最新论文:机器具备连续图像叙事能力

【新智元导读】微软团队 NAACL 2016 论文,描述微软“连续图像叙事数据库”(SIND),也是首个用于连续视觉-语言转换的数据集,能逐步将独立图像转变为连...

3506
来自专栏新智元

【干货】微软童欣:黑科技!机器学习打造全新3D图形技术

【新智元导读】微软亚洲研究院AI大咖童欣在中国科技大学进行题为《数据驱动方法在图形学中的应用》的前沿演讲,解释了如何通过数据驱动的方法来处理图形学问题,以及最新...

3485
来自专栏新智元

Karpathy更新深度学习开源框架排名:TensorFlow第一,PyTorch第二

上周,Keras作者、谷歌研究科学家François Chollet晒出一张图,他使用Google Search Index,展示了过去三个月,ArXiv上提到...

41710

扫码关注云+社区