基于物品的协调过滤算法

基于物品的协同过滤(item-based collaborative filtering)算法是目前业界应用最多的算法。无论是亚马逊网,还是Netflix、 Hulu、 YouTube,其推荐算法的基础都是该算法。本节将从基础的算法开始介绍,然后提出算法的改进方法,并通过实际数据集评测该算法。

1. 基础算法

基于用户的协同过滤算法在一些网站(如Digg)中得到了应用,但该算法有一些缺点。首先,随着网站的用户数目越来越大,计算用户兴趣相似度矩阵将越来越困难,其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。其次,基于用户的协同过滤很难对推荐结果作出解释。因此,著名的电子商务公司亚马逊提出了另一个算法——基于物品的协同过滤算法。

基于物品的协同过滤算法 (简称ItemCF)给用户推荐那些和他们之前喜欢的物品相似的物品。

比如,该算法会因为你购买过《数据挖掘导论》而给你推荐《机器学习》 。不过, ItemCF算法并不利用物品的内容属性计算物品之间的相似度,它主要通过分析用户的行为记录计算物品之间的相似度。该算法认为,物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品B。图2-9展示了亚马逊在iPhone商品界面上提供的与iPhone相关的商品,而相关商品都是购买iPhone的用户也经常购买的其他商品。

基于物品的协同过滤算法可以利用用户的历史行为给推荐结果提供推荐解释,比如给用户推荐《天龙八部》的解释可以是因为用户之前喜欢《射雕英雄传》。如2-10所示, Hulu在个性化视频推荐利用ItemCF给每个推荐结果提供了一个推荐解释,而用于解释的视频都是用户之前观看或

者收藏过的视频。

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

(1) 计算物品之间的相似度。

(2) 根据物品的相似度和用户的历史行为给用户生成推荐列表。

图2-9上亚马逊显示相关物品推荐时的标题是“ Customers Who Bought This Item Also Bought”(购买了该商品的用户也经常购买的其他商品)。从这句话的定义出发,我们可以用下面的公式定义物品的相似度:

这个公式惩罚了物品j的权重,因此减轻了热门物品会和很多物品相似的可能性。 从上面的定义可以看到,在协同过滤中两个物品产生相似度是因为它们共同被很多用户喜欢,也就是说每个用户都可以通过他们的历史兴趣列表给物品“贡献”相似度。这里面蕴涵着一个假设,就是每个用户的兴趣都局限在某几个方面,因此如果两个物品属于一个用户的兴趣列表,那么这两个物品可能就属于有限的几个领域,而如果两个物品属于很多用户的兴趣列表,那么它们就可能属于同一个领域,因而有很大的相似度。

和UserCF算法类似,用ItemCF算法计算物品相似度时也可以首先建立用户—物品倒排表(即对每个用户建立一个包含他喜欢的物品的列表),然后对于每个用户,将他物品列表中的物品两两在共现矩阵C中加1。详细代码如下所示:

图2-11是一个根据上面的程序计算物品相似度的简单例子。图中最左边是输入的用户行为记录,每一行代表一个用户感兴趣的物品集合。然后,对于每个物品集合,我们将里面的物品两两加一,得到一个矩阵。最终将这些矩阵相加得到上面的C矩阵。其中C[i][j]记录了同时喜欢物品i和物品j的用户数。最后,将C矩阵归一化可以得到物品之间的余弦相似度矩阵W。

表2-7展示了在MovieLens数据集上利用上面的程序计算电影之间相似度的结果。如表中结果所示,尽管在计算过程中没有利用任何内容属性,但利用ItemCF计算的结果却是可以从内容上看出某种相似度的。一般来说,同系列的电影、同主角的电影、同风格的电影、同国家和地区的电影会有比较大的相似度。

图2-12是一个基于物品推荐的简单例子。该例子中,用户喜欢《C++ Primer中文版》和《编程之美》两本书。然后ItemCF会为这两本书分别找出和它们最相似的3本书,然后根据公式的定义计算用户对每本书的感兴趣程度。比如, ItemCF给用户推荐 《算法导论》 ,是因为这本书和《 C++Primer中文版》相似,相似度为0.4,而且这本书也和《编程之美》相似,相似度是0.5。考虑到用户对《C++ Primer中文版》的兴趣度是1.3,对《编程之美》的兴趣度是0.9,那么用户对《算法导论》的兴趣度就是1.3 × 0.4 + 0.9×0.5 = 0.97。

从这个例子可以看到, ItemCF的一个优势就是可以提供推荐解释,即利用用户历史上喜欢的物品为现在的推荐结果进行解释。如下代码实现了带解释的ItemCF算法:

表2-8列出了在MovieLens数据集上ItemCF算法离线实验的各项性能指标的评测结果。该表包括算法在不同K值下的性能。根据表2-8中的数据我们可以得出如下结论。

精度(准确率和召回率) 可以看到ItemCF推荐结果的精度也是不和K成正相关或者负相关的,因此选择合适的K对获得最高精度是非常重要的。

流行度 和UserCF(基于用户的协同过滤推荐)不同,参数K对ItemCF推荐结果流行度的影响也不是完全正相关的。

随着K的增加,结果流行度会逐渐提高,但当K增加到一定程度,流行度就不会再有明显

变化。

覆盖率 K增加会降低系统的覆盖率。

2. 用户活跃度对物品相似度的影响

从前面的讨论可以看到,在协同过滤中两个物品产生相似度是因为它们共同出现在很多用户的兴趣列表中。换句话说,每个用户的兴趣列表都对物品的相似度产生贡献。那么,是不是每个用户的贡献都相同呢?

假设有这么一个用户,他是开书店的,并且买了当当网上80%的书准备用来自己卖。那么,他的购物车里包含当当网80%的书。假设当当网有100万本书,也就是说他买了80万本。从前面对ItemCF的讨论可以看到,这意味着因为存在这么一个用户,有80万本书两两之间就产生了相似度,也就是说,内存里即将诞生一个80万乘80万的稠密矩阵。

另外可以看到,这个用户虽然活跃,但是买这些书并非都是出于自身的兴趣,而且这些书覆盖了当当网图书的很多领域,所以这个用户对于他所购买书的两两相似度的贡献应该远远小于一个只买了十几本自己喜欢的书的文学青年。

John S. Breese在论文中提出了一个称为IUF(Inverse User Frequence),即用户活跃度对数的倒数的参数,他也认为活跃用户对物品相似度的贡献应该小于不活跃的用户,他提出应该增加IUF参数来修正物品相似度的计算公式:

当然,上面的公式只是对活跃用户做了一种软性的惩罚,但对于很多过于活跃的用户,比如上面那位买了当当网80%图书的用户,为了避免相似度矩阵过于稠密,我们在实际计算中一般直接忽略他的兴趣列表,而不将其纳入到相似度计算的数据集中。

本书将上面的算法记为ItemCF-IUF,下面我们用离线实验评测这个算法。在这里我们不再考虑参数K的影响,而是将K选为在前面实验中取得最优准确率和召回率的值10。

如表2-9所示, ItemCF-IUF在准确率和召回率两个指标上和ItemCF相近,但ItemCF-IUF明显提高了推荐结果的覆盖率,降低了推荐结果的流行度。从这个意义上说, ItemCF-IUF确实改进了ItemCF的综合性能。

个电影网站中,有两种电影——纪录片和动画片。那么, ItemCF算出来的相似度一般是纪录片和纪录片的相似度或者动画片和动画片的相似度大于纪录片和动画片的相似度。

但是纪录片之间的相似度和动画片之间的相似度却不一定相同。假设物品分为两类——A和B, A类物品之间的相似度为0.5, B类物品之间的相似度为0.6,而A类物品和B类物品之间的相似度是0.2。在这种情况下,如果一个用户喜欢了5个A类物品和5个B类物品,用ItemCF给他进行推荐,推荐的就都是B类物品,因为B类物品之间的相似度大。但如果归一化之后, A类物品之间的相似度变成了1, B类物品之间的相似度也是1,那么这种情况下,用户如果喜欢5个A类物品和5个B类物品,那么他的推荐列表中A类物品和B类物品的数目也应该是大致相等的。从这个例子可以看出,相似度的归一化可以提高推荐的多样性。

那么,对于两个不同的类,什么样的类其类内物品之间的相似度高,什么样的类其类内物品相似度低呢?一般来说,热门的类其类内物品相似度一般比较大。如果不进行归一化,就会推荐比较热门的类里面的物品,而这些物品也是比较热门的。因此,推荐的覆盖率就比较低。相反,如果进行相似度的归一化,则可以提高推荐系统的覆盖率。

表2-10对比了ItemCF算法和ItemCF-Norm算法的离线实验性能。从实验结果可以看到,归一化确实能提高ItemCF的性能,其中各项指标都有了比较明显的提高。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-07-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

【科技】豹变猫?实时场景转变?NVIDIA多模式图像转换技术都能实现

改变美洲豹身上的斑点似乎是个很有趣的想法,而这个想法也并非天方夜谭。通过NVIDIA新的加速GPU深度学习技术,无论是图片还是视频,甚至是实体美洲豹,都能使其变...

722
来自专栏新智元

《科学》封面论文作者力作:搭建像人一样思考和学习的机器(附论文下载)

【新智元导读】纽约大学的B. Lake、MIT的J. Tenenbaum等人2015年底在《科学》刊发封面论文,描述“看一眼便能学会写字”的计算机。Lake、T...

3187
来自专栏镁客网

这款由记忆电阻设计的新型硬件计算系统,加速神经网络训练的同时还可预测下一步输出 | 黑科技

1020
来自专栏SIGAI学习与实践平台

非算法类人工智能从业者须知的十件事

AI大潮汹涌,吸引了越来越多的人才进入来添砖加瓦。而其中,除去核心的算法工程师、科学家外,催生了大量相关的从业人员。而无论你是销售,产品,设计,甚至是协作的AP...

802
来自专栏量子位

AI计算力6年增长30万倍,远超摩尔定律 | OpenAI分析报告

为了感受这个速度,OpenAI发布了一份分析报告,说的是2012年开始,AI训练所用的计算量呈现指数增长,平均每3.43个月便会翻倍。

663
来自专栏AI科技评论

NLP应该如何学、如何教?斯坦福大学大牛Dan Jurafsky教授专访

AI 科技评论按:自然语言处理是一个高度跨学科的领域,包含了语言学、计算机科学、统计学等等许多传统学科的内容。在课堂中,自然语言处理的教师者们要根据课程长度、学...

472
来自专栏AI科技评论

业界 | 更善于自动抓拍「有趣」瞬间:谷歌 Clips AI 拍照新技术

尽管深度学习已经在近期取得了一些进步,但在其在自动摄影方面依旧面临着一项极具挑战的难题:相机能够自动抓拍到精彩的瞬间吗?

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

结课 | Fast.ai 最实战深度学习在线课程 Lesson7

AI100 每周二推出的 Fast.ai 深度学习在线课程很受同学们的欢迎。本课程由 Jeremy Howard 教授开设,共8节。目的是让大家在不需要深入研究...

2737
来自专栏计算机视觉战队

未来人工智能之人脸领域技术

部分来源于《机器人大讲堂》和《2017年中国人脸识别未来发展路径、市场需求、市场发展空间预测》 ? 近年来由于深度学习爆炸式的发展,已经带动了整个行业的发展。...

2995
来自专栏AI科技评论

专访FPGA 2017最佳论文得主深鉴科技: 深度学习的最大瓶颈是带宽问题而非计算

AI科技评论按:近日,深鉴科技的 ESE 语音识别引擎的论文在 FPGA 2017 获得了唯一的最佳论文 ESE: Efficient Speech Recog...

3009

扫码关注云+社区