推荐算法之协同过滤

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

相关文章

来自专栏企鹅号快讯

IBM Watson提出人机推理网络HuMaINs,结合人机两者优势

选自arXiv 机器之心编译 参与:刘晓坤、黄小天 人机交互可以用机器的优势弥补人类决策的非理性缺陷。近日,IBM Watson 研究中心联合多家研究机构提出了...

1949
来自专栏BestSDK

今日头条公布算法:解密“垃圾信息”是如何诞生的

“算法分发并非是把所有决策都交给机器,我们会不断纠偏,设计、监督并管理算法模型。”曹欢欢希望这次分享能让更多的人理解算法,并共同参与到算法模型的制定中来。此外,...

3488
来自专栏CDA数据分析师

优质数据科学课程推荐:总结篇

原作者   David Venturi 编译 CDA 编译团队 本文为  CDA 数据分析师原创作品,转载需授权 一年以前,我还只是一个没有任何编程经验的技术宅...

2168
来自专栏新智元

开源深度学习工具 Kur,不用写代码就能设计、训练和评估 DL 模型

Deepgram 是 YC 投资的一家初创公司,其业务是使用机器学习分析企业的音频数据。近日该公司开源了内部的深度学习工具 Kur(https://github...

3297
来自专栏量子位

机器学习到底能替人干哪些工作?《科学》列出了8条评估标准

唐旭 编译整理 量子位 出品 | 公众号 QbitAI ? 对于AI会取代哪些人类工作的猜测,也许可以暂时停一停了。 最近,两位来自MIT和CMU的研究者在一篇...

4048
来自专栏ATYUN订阅号

密歇根大学研究者致力于用AI实时识别验证ID证件

密歇根大学的研究人员开发了一种基于深度学习的系统,该系统执行实时面部识别并根据相应的护照和政府颁发的身份证件验证照片。该方法有助于执法机构防范欺诈行为,可以作为...

1034
来自专栏CSDN技术头条

在人工智能和大数据产品的开发中,有哪些需要特别注意的点?

人工智能是近年来科技发展的重要方向,大数据的采集、挖掘、应用的技术越来越受到瞩目。在人工智能和大数据产品的开发过程中,有哪些特别需要注意的要点?人工智能领域的算...

1867
来自专栏携程技术中心

干货 | 助理来也胡一川:深度学习在智能助理中的应用

作者简介 胡一川,来也联合创始人和CTO。来也专注于智能对话技术,让每个人拥有助理。此前,胡一川联合创立了影视推荐引擎"今晚看啥"并被百度收购,后加入百度任资深...

3677
来自专栏人工智能

如何用机器学习满足产品需求

关于机器学习有太多的文章介绍了,如果还对机器学习一知半解的可以参考一下其他文章,我的其他文章中也有简单介绍了机器学习。本文主要介绍机器学习的应用以及我们如何使用...

1921
来自专栏IT派

推荐|不知道这些AI知识,千万别说你是AI圈的!

摘要: 为什么人工智能,机器学习突然之间成了热门话题,变成IT领域,甚至其他领域的人们都在讨论的热点?也许文章的作者会给你一点这方面的思考。 最近,我有幸与人...

3936

扫码关注云+社区