协同过滤的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上获取。