基于物品的协调过滤算法

基于物品的协同过滤(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 条评论
登录 后参与评论

相关文章

来自专栏我和未来有约会

[Silverlight动画]转向行为 - 介绍

转向行为(steering behaviors)这一术语,指的是一系列使对象行动起来像似长有智商的算法。这些行为都归于人工智能或人工生命一类,是让对象呈现出拥有...

1655
来自专栏老九学堂

为什么每个程序员都需要学习算法?

懂算法的程序员 ? 不懂算法的程序员 ? 算法的力量 算法是计算机科学领域最重要的基石之一,但却受到了一些程序员的冷落。 许多小伙伴看到一些公司在招聘时要求的...

3498
来自专栏机器之心

业界 | 微软提出基于程序图简化程序分析,直接从源代码中学习

1463
来自专栏CDA数据分析师

R语言的好与坏丨讲座中字视频丨附讲座PDF

R是一种用于分析数据的领域特定语言。为什么数据分析需要自己的领域特定语言(DSL) ? R语言擅长些什么,不擅长什么?开发人员该如何利用R语言的优势并减轻其弱点...

2099
来自专栏ACM算法日常

芯片测试(分治)- 例题

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成...

632
来自专栏专知

TensorFlow 日常更新:加入 AutoGraph,简化构图流程

【导读】谷歌发布了一个新的 TensorFlow 工具「AutoGraph」,旨在快速将Python 代码转化到TensorFlow体系里。目前测试来看,这一工...

922
来自专栏数据派THU

独家 | 带你入门比Python更高效的Numpy(附代码)

向量化技巧对于数据科学家来说是相当熟知的,并且常用于编程中,以加速整体数据转换,其中简单的数学变化通过可迭代对象(例如列表)执行。未受到重视的是,把有一定规模的...

823
来自专栏数据结构与算法

1316 文化之旅 2012年NOIP全国联赛普及组

1316 文化之旅 2012年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 ...

3337
来自专栏云时之间

NLP系列学习:CRF条件随机场(1)

大家好,今天让我们来看看条件随机场,条件随机场是一项大内容,在中文分词里广泛应用,因为我们在之前的文章里将概率图模型和基本的形式语言知识有所了解,当我们现在再去...

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

基于物品的协同过滤算法:理论说明,代码实现及应用

0.一些碎碎念 从4月中旬开始,被导师赶到北京的郊区搬砖去了,根本就没有时间学习看书,这个时候才知道之前的生活是多么的幸福:每天看自己想看的书,然后实践一下,最...

3359

扫描关注云+社区