推荐算法之协同过滤

推荐算法在个性化领域有着广泛的应用,粗略统计,所涉及到的学科包括人工智能、机器学习、认知科学、信息抽取、数据挖掘、预测理论、近似理论,甚至是管理科学、市场营销和心理学。所使用的算法除了传统的协同过滤,还包括图模型(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 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

视频 | 给正在读论文的你:如何高效阅读文献?

原标题:How to Read a Research Paper 翻译 | 王飞 J叔 字幕 | 凡江 整理 | 林尤添 无论是对于机器学习,密码...

26910
来自专栏PPV课数据科学社区

五类受自然启发的AI算法

摘要: 本文主要讲解了受自然启发的五类AI算法以及各自的实际用例:神经网络、遗传算法、群集集体智慧、强化学习、人体免疫。 ? 搜索/寻路算法 搜索算法...

3074
来自专栏PaddlePaddle

GITCHAT系列1:深度学习第一课

近几年深度学习的概念非常火,我们很幸运赶上并见证了这一波大潮的兴起。记得2012年之前提及深度学习,大部分人并不熟悉,而之后一段时间里,也有些人仍旧持怀疑的态度...

35411
来自专栏新智元

FPGA 超越 GPU,问鼎下一代深度学习主引擎

【新智元导读】英特尔加速器架构实验室的Eriko Nurvitadhi 博士以最新的 GPU 为参照,对两代 Intel FPGA 上新兴的DNN算法进行了评估...

3215
来自专栏机器之心

专访 | 分子科学中的机器学习:不会燎原的星星之火?

机器之心原创 作者:邱陆陆 继计算机视觉、语音识别、自然语言处理之后,谁是下一个迎来深度学习的浪潮冲击的领域?聚集了世界上最聪明头脑的自然科学领域会不会「首当其...

2736
来自专栏AI科技大本营的专栏

CCAI | 如何能既便宜又快速地获取大数据?这位微软研究员设计了两个模型,帮你省钱省时间

美国微软雷德蒙研究院首席研究员周登勇 文/CSDN贾维娣 7 月 22 - 23 日,在中国科学技术协会、中国科学院的指导下,由中国人工智能学会、阿里巴巴集团 ...

3216
来自专栏新智元

【迁移学习】 6张图像vs13000张图像,超越2013 Kaggle猫狗识别竞赛领先水平

【新智元导读】2013年,Kaggle举办过一个很受欢迎的猫狗识别竞赛(Dogs vs. Cats),比赛内容是识别图像中的是猫还是狗。当时获胜的准确率是82....

2708
来自专栏理论坞

1分钟了解定律、效应到底是什么

定律是为实践和事实所证明,反映事物在一定条件下发展变化的客观规律的论断。定律是一种理论模型,它用以描述特定情况、特定尺度下的现实世界,在其它尺度下可能会失效或者...

962
来自专栏机器之心

学界 | 伯克利吴翼&FAIR田渊栋等人提出强化学习环境Hourse3D

2605
来自专栏大数据挖掘DT机器学习

如何利用数据做排行榜?

8月15日上海交通大学世界一流大学研究中心发布2015年“世界大学学术排名”。今年,哈佛大学蝉联榜首,剑桥大学排名第2,第3-5名依次是牛津大学、麻省理工学...

3174

扫码关注云+社区