协同过滤的R语言实现及改进

协同过滤算法是推荐系统最常用的算法之一,本文将介绍一种方法来使它可以在大型数据集上快速训练。

协同过滤算法(CF)是构建推荐系统时最常用的技术之一。它可以基于收集到的其他用户的偏好信息(协同)来自动地预测当前用户的兴趣点。协同过滤算法主要分为两种:基于记忆(memory-based)的协同过滤算法和基于模型(model-based)的协同过滤算法。一般来说,将两者融合可以获得预测准确度上的提升。

在本文中,我们将关注基于记忆的协同过滤算法并详细讨论其推导和集成的细节。我们将展示我们最近在改进经典协同过滤算法上的一些工作,使其可以在大规模数据集上实施并达到缩短训练时间的效果。我们的算法是用R语言实现的,但是它也可以被移植到其他语言上。

基于记忆的协同算法又可以分为下面两种:

  • 基于用户的协同过滤:如果想要预测用户U对物品I的评价,可以借助其他和U相似的用户的评价来进行预测。这么做的原因是我们认为相同品味的用户会对同一事物做出相似的评价。
  • 基于物品的协同过滤:如果想要预测用户U对物品I的评价,可以借助该用户对和物品I相似的物品的评价进行预测。这么做的原因是我们认为同一用户对相似事物做出的评价应当是接近的。

下面让我们从一个例子出发来观察基于用户的协同过滤是如何实现的。下面给出了计算评价r_{u,i}的公式,r_{u,i} 即用户u对物品i的评分。我们把和用户u相似的用户(用户之间的相似度信息通过一个矩阵维护,sim为相似度计算函数)的评价汇总在一起,从公式可以看出,用户间的相似度越大,其中一个用户对另一个用户评价的预测结果影响程度就越大。w为计算最终评分所需的归一化权重因子。

为了验证当前推荐系统的性能,我们需要在测试集上进行预测。为了更高的效率,计算会借助矩阵乘法完成,而不是通过循环的方式完成。下面的图片展示了矩阵计算的过程:

从左到右依次为 用户对物品的评分矩阵 用户相似度矩阵 预测结果矩阵

上图展示了预测用户U_2对物品I_3评分时的计算过程。为了计算预测结果,我们需要知道其他用户对I_3的评分(第一个矩阵中蓝色高亮的一行)以及其他用户与U_2的相似度(第二个矩阵中蓝色高亮的一列;注意这里我通过设置相似度矩阵对角线的元素为零来避免数据泄露)。到此,我们可以写出用户U_2对物品I_3评分的计算公式:

计算结果将被存储在第三个矩阵的蓝色单元当中。不过这里还没有进行归一化,为了得到最终的预测结果,我们还需要计算归一化因子w,计算公式已经在上面给出。

基于记忆的协同过滤的主要优点与它的可扩展性和性能密不可分。举例来说,如果这里有500,000个用户,那么我们需要计算所有用户对之间的相似度(最坏的情况需要计算1200亿个值)。显然这需要大量的内存和处理时间,下面我们将尝试用R语言(当然你也可以使用别的编程语言 : ) )对协同过滤算法进行一些改进从而解决这一问题。

我们将用R推荐系统中最常用的包之一——recommenderlab与我们的实现进行比较。这个比较是在4核i7,16G内存的小型电脑上完成的,使用的数据集是 MovieLens 100k, MovieLens 1m, MovieLens 10m。后面,你会看到我们的集成具有两大优势:

  1. 它的速度有显著的提升。
  2. 可以支持在庞大的数据集上构建推荐系统,当 recommenderlab 报出内存溢出的错误时,我们的实现仍然可以正常工作。

执行效率的提升

评分矩阵通常是一个庞大(有大量的用户和物品)的稀疏(每个用户往往只对少量的物品打分)矩阵。在R语言中,我们可以通过专门的数据结构来存储稀疏矩阵,缺失值不会被重复存储在内存当中。一般来说,有超过90%的值是缺失的,所以这种做法可以节省下大量的内存。我们的实现以及recommenderlab中都采用了矩阵的稀疏表示。

我们实现的基于用户的协同过滤主要包含以下步骤(基于物品的协同过滤也是如此):

  1. 导入评分矩阵
  2. 开发者决定是否对用户评分进行标准化。这一步通常会提高准确率。这是因为标准化可以移除用户评分的偏置,举例来说就是有些用户总是会打高分或者总是打低分。
  3. 计算用户之间的相似度。
  4. 使用KNN算法。(只保留k个最相似的用户,即在用户的评分预测计算中,相似度矩阵每列只保存最高的k个值)k值需要开发者手动指定。
  5. 计算预测值并进行反归一化得到最终的预测评分。

recommenderlab也使用了与上面相同的过程。但是我们在这些过程中引入了一些改进从而显著地提升了算法执行效率。其中主要的两个优化如下:

  1. 对大型稀疏矩阵的相似性计算进行了优化。具体方法可以参考Recommender Systems: Matrix Operations for Fast Calculation of Similarities
  2. 相似度矩阵的k近邻算法不是通过循环完成的,我们采用了更优的实现。首先,我们对相似度矩阵进行了分组(列拆分),然后在每组当中通过函数找到最高的k个值。这个函数已经在R 'data.table'包中被实现。依此,我们通过每组的信息得到了相似度矩阵中每列最大的k个值。

验证

我们通过以下步骤来讲我们的实现与recommenderlab进行比较:

  • 10折交叉验证。每次训练使用90%的数据来创建模型、计算相似度,10%的数据用来测试。任一用户和物品都被划分到了训练集或者测试集当中。
  • 中心归一化(Center Normalization),用户评分的平均值将从他的实际评分中扣除。
  • 余弦距离来计算相似度。
  • k:选取的近邻样本数为100,300以及样本总值。
  • rmse:算法的误差(root-mean-square error,均方根误差)
  • 执行时间 (exec time) :算法的执行时间,以秒为单位。

在100k MovieLens 数据集上的比较

该数据集包括943个用户和1682个电影(物品),100,000个评分。

基于用户的协同过滤
基于物品的协同过滤

在1M MovieLens 数据集上的比较

该数据集包括6040个用户和3706个电影(物品),100,000个评分。

基于用户的协同过滤
基于物品的协同过滤

可以看到我们的实现在运行速度上更快,精准度也更高(达到了更低的rmse)。其中我们最关注的方面——速度得到了显著的提升。

然而,速度只是经典实现中问题的一个方面。我们在上面提到过,协同过滤的另一个问题是空间占用,即当矩阵过于庞大时我们会面临内存不足的问题。在下一节中,我们将提出一个可行的方案来使传统的协同过滤算法可以被应用在庞大的数据集上。

在庞大的数据集上构建推荐算法

在下面的测试中,我们使用MovieLens 10m的数据集。但是正如上面提到的,我们测试的机器只有16GB的内存并且使用了十折的交叉验证。'recommenderlab'的实现在建立用户相似度矩阵的过程中就因为内存不足而退出了。

在我们的实现当中,我们通过对矩阵进行切分解决了这一问题。即我们不是一次性计算所有的预测值,而是一块一块完成的。下面给出基于用户的协同过滤的实现过程(基于物品的协同过滤同理):

  1. 取出用户评分矩阵的前N行。在下图图示中,我们提取了I_1:I_4部分的切片。
  2. 取出M个用户并计算他们与其他用户的相似度。在下图图示中,我们提取了U_1:U_2部分的切片。
  3. 根据公式计算第一步得到的矩阵和第二步得到的矩阵的乘积。结果为MxN的矩阵,矩阵的元素为归一化之前的预测结果。在图示中,计算结果为用户U_1:U_2对物品I_1:I_4的评分。
  4. 重复以上三步计算不同的MxN单元只到结果矩阵被填满。

在10M MovieLens 数据集上的结果

该数据集包括69,878个用户和10,677个电影(物品),10,000,054个评分。我们通过以下步骤来检验我们的算法:

  • 10折交叉验证
  • 中心归一化(Center Normalization)。
  • 余弦距离来计算相似度。
  • k:选取的近邻样本数为100,1000。
  • Chunk size:在算法当中每次取出的块的行列大小。具体的取值取决于你的硬件条件。

比较的结果可以从下面的表格找到,包含:

  • rmse:算法的误差(root-mean-square error)
  • 执行时间:算法的执行时间,以分钟为单位。
  • num predictions:协同过滤能够预测的结果数。通常来说,协同过滤不是一定能够得到预测结果的(比方说与之相似的用户也都还没有给该商品打分)
基于物品的协同过滤
基于用户的协同过滤

正如上图展示的结果所示,我们实现的算法完满地完成了任务。现在我们可以在16Gb内存配置的机器上构建推荐系统了。基于用户和基于物品的协同过滤分别耗费了10分钟和200分钟的时间,基于用户的协同过滤花费了更多的时间是因为数据集中有了更多的用户,这要求我们计算更多的相似度。

通过现在的实现,当我们需要为一个或者多个用户提供实时的推荐时,相似度的计算以及结果的预测将迅速很多,因为我们可以只选取少部分用户进行操作。在MovieLens 10m的数据集上,基于用户的协同过滤只需要一秒就可以对一个用户或者多个用户生成预测,但是基于物品的协同过滤则需要30s左右,这是因为我们需要更多的时间来计算相似度矩阵。这里还可以通过将相似度矩阵存储为模型,不再进行即时的训练从而达到线上预测效果的加速。这个算法实现的一个显著优点就是可扩展性,由于我们将原数据集切分为了不同块进行计算,所以可以进一步实现并行化。我们接下来的工作之一就是在分布式框架上实现并测试这一方法。

总结

在本文中,我们提出了一种新的方法来改进基于记忆的传统协同过滤实现。本文的代码可以从Github上获取。

本文的版权归 ArrayZoneYour 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

对比TensorFlow提升树与XGBoost:我们该使用怎样的梯度提升方法

选自Nicolo Blog 作者:Nicolò Valigi 机器之心编译 参与:蒋思源 几个月前,TensorFlow 发布了梯度提升方法的调用接口,即 Te...

3419
来自专栏ATYUN订阅号

DeepSense:用于时间序列移动传感数据处理的深度学习框架

DeepSense是在移动设备上运行的深度学习框架,它可以完成移动传感器(如运动传感器)数据集上的回归和分类任务。分类任务的第一个例子是异构人类活动识别(HHA...

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

【深度】Peacock:大规模主题模型及其在腾讯业务中的应用

如果用户最近搜索了“红酒木瓜汤”,那么应该展示什么样的广告呢?从字面上理解,可能应该返回酒水或者水果类广告。可是你知道吗?“红酒木瓜汤”其实是一个民间丰胸秘方。...

1.1K5
来自专栏灯塔大数据

原创译文 | 为网络新人而准备——七步理解深度学习

导读:上一期给大家介绍让你成为优秀数据科学家的42个步骤。深入掌握数据准备,机器学习,SQL数据科学等。今天我们从细节上来把握,七步进入深度学习(文末更多往期译...

3597
来自专栏腾讯大数据的专栏

腾讯深度学习平台亮相机器学习顶级会议ICML2014

引言:深度学习是近年机器学习领域的重大突破,有着广泛的应用前景。随着Google公开Google Brain计划,业界对深度学习的热情高涨。百度成立深度学习研究...

3049
来自专栏奇点大数据

谷歌大脑AutoML新进展:用进化算法发现神经网络架构

作者|谷歌大脑高级工程师 Esteban Real 编译|Debra 从 5 亿年前非常简单的蠕虫大脑到各种现代化结构,大脑经历了漫长的进化过程。如今,人类的大...

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

一文讲述如何将预测范式引入到机器学习模型中

本文构建了一个在视觉条件下以感官信息作为输入的预测模型。由于无法准确建立感官信息的运动方程,只能通过机器学习来完成。

47716
来自专栏新智元

谷歌大脑 Bengio:全新 Active Memory 模型提升机器翻译水平(附 NIPS 论文下载)

【新智元导读】Samy Bengio,刚刚创业的 Youshua Bengio的弟弟,昨天在 Arxiv 上发布了他与同事、Google Brain 研究人员 ...

38010
来自专栏IT技术精选文摘

一文讲述如何将预测范式引入到机器学习模型中

1106
来自专栏ATYUN订阅号

Ouster将相机与激光雷达融合,并更新了开源驱动程序

当Ouster三年前开始开发OS-1时,相机的深度学习研究超过了激光雷达研究。激光雷达数据具有令人难以置信的好处,丰富的空间信息和照明无法识别也能感应,但它缺乏...

7061

扫码关注云+社区

领取腾讯云代金券