论文笔记《Item-Based Collaborative Filtering Recommendation Algorithms》

一、基本信息

论文题目：《Item-Based Collaborative Filtering Recommendation Algorithms》

发表期刊及年份：WWW 2001

二、摘要

近几年由于可获得信息的大量增长和访问网站的用户数大量增加，产生了一些重要的挑战：产生高质量的推荐、每秒为大量用户和物品实现实时推荐和在面临数据稀疏性的情况下如何实现快速收敛。在传统的协同过滤网络中，由于用户的增长而变得效果很差。为了解决这些问题，作者提出了基于物品的协同过滤算法。基于物品的协同过滤算法首先分析用户-物品矩阵去挖掘不同物品直接的关系，然后利用这些关系来为用户进行推荐。

在这篇论文中，作者分析了多种基于物品的协同过滤算法，研究了不同的计算物品相似性的方法（例如：物品-物品相关性、cosine相关性）和从这些相似物品中找出推荐物品的方法（例如：权重加和与回归）。最后，我们利用实验评估了我们的结果，并且将它与基础的k-nn算法进行比较。我们的实验表明，基于物品的算法较基于用户的算法性能有较大的提升，同时推荐的质量也比基于用户的算法强。

三、简介

协同过滤网络在实践和研究中都有十分重要的作用，但是还是有两个要克服的问题。

第一个问题就是要改善协同过滤网络的可扩展性。

第二个要改善的问题是改善推荐质量。用户肯定会对哪些推荐不准确的推荐系统产生反感。

在这篇论文中，作者提出了基于物品的协同过滤算法来进行解决这些问题。传统基于用户的协同过滤网络有一个瓶颈:需要在大量的用户中寻找潜在相关用户，我们使用基于物品的协同过滤网络绕过了这个瓶颈，先去寻找相关的物品集合，因为物品之间的关系是相对静态的。

1.相关工作

Tapestry是最早的一个基于协同过滤网络的推荐算法，它的推荐依赖于人们之间密切的关系（例如在一个办公室中，或者一个公司中），但是在一个大型的系统中，我们不能依靠每个人都有联系。后来，有人进行改进，研究出了基于打分的协同过滤网络。后来又有贝叶斯网络、聚类、Horting等方法。

贝叶斯网络通过在训练集上使用决策树构建一个模型，这个模型可以通过几小时或者几天来构建一个很小的模型，但是它的速度会特别快。贝叶斯网络适用于用户偏好变化较慢的情况，不适用于速度更新快的网络。

聚类方法通过证明某一个组的用户有相同的爱好，然后当进行预测时，把一个组的意见进行平均即可。聚类一旦完成，速度可能很快，但是聚类的时候可能处于边缘的一些用户可能出现不准确的情况。

Horting是一个基于图的方法。

Schafer等人曾经提出一个推荐系统，虽然取得了较大的成功，但是在广泛应用方面还是有很大的限制，比如说：数据集的稀疏性、高维性等等。

我们的工作可以将这些问题解决。

2.贡献

这篇论文主要有三个主要的贡献：

1.分析了基于物品的预测方法并且证明了不同的方法去实现这些子任务。

2.构建了一个计算物品相似度的预计算模型提高在线可扩展性。

3.从实验上比较了基于物品的推荐算法和经典的基于用户的算法。

四、协同过滤推荐网络

推荐系统的主要作用是产生一个预测分数或者是一系列Top-N物品集合。基于物品的协同过滤网络的基本思路是推荐物品或者基于其它相似人员的预测。

1.协同过滤网络概述

用户集合：U={u₁,u₂,…,u_m}，物品集合：I={i₁,i₂,…,i_n}，用户u_i感兴趣的集合为I_ui。

关于用户感兴趣的集合可以通过很多方式得到，比如用户的评价，用户的购买记录，分析时间日志，或者挖掘网络超链接等。

设定一个特定用户u_a∈U，模型的任务就是以下面的两种形式来发现物品的相似性：

• 预测

  预测的值是一个值P_a,j，用来表示用户对i_j∉I_ua这个物品的喜爱性。预测的值的范围与I_ua的范围应该是一致的（比如说：都是1-5）。

• 推荐物品

  是一个集合I_r，I_r∈I，是用户最喜欢的物品。注意，推荐物品集合是不在用户已购买的集合之内，也就是说I_r∩I_ua=∅，这也就是我们所说的Top-N推荐。
  

上图显示了协同过滤网络处理过程的的概要图。CF算法将整个mxn矩阵视为打分矩阵，A。每一个元素a_i,j代表第i个用户再第j个物品上的打分，他们都是同一个数字范围，0代表还没有打分。协同过滤算法一般可分为两类基于Memory（user-based）和基于Model（item-based）的算法。

基于Memory的协同过滤算法：这种方法利用整个的用户-物品数据进行预测。这些系统利用统计方法寻找与目标用户具有相似历史记录的用户。一旦这个群组的用户生成了，这些系统就会采用各种各样的方法来进行预测或者进行top-N物品推荐。

基于Model的协同过滤算法：这种方法首先对用户评价进行模型构建。这种方法采用一个概率的方法并且将协同过滤处理视为计算用户预测的一个期望值，将他的评价利用到其它物品上。模型的构造过程通过不同的算法来实现，比如贝叶斯网络，聚类和基于规则的方法。贝叶斯构造一个概率模型，聚类将协同过滤视为一个分类过程，将相似的用户分为同一个类，估算用户在一个类内的概率，然后利用条件概率来计算可能的评价。基于规则的方法是利用相关规则对一起购买的物品进行研究，然后根据物品的相关性强弱来生成物品推荐。

2.基于用户的协同过滤网络存在的问题

之前基于用户的协同过滤网络是非常成功的，但是他们的广泛应用缺受到了限制，主要原因如下：

• 稀疏性

  实际上，许多推荐系统是用来评价很大的物品集。即使用户买2000种书，那也不到总数的1%。因此，推荐系统不能为用户做出任何的推荐，最终导致推荐的准确率很低。

• 可扩展性

  紧邻算法伴随用户和物品的增长需要的计算力会快速增长。伴随数万用户和物品的增长，一个典型的基于web的推荐系统运行已存在的算法会遇到严重的扩展性问题。

此处省略一万字。主要是作者研究其它人对这两个问题的改进。

五、基于物品的协同过滤算法

基于物品的协同过滤网络研究目标用户评价过得物品并且计算这些物品与目标物品的相似性，然后选择出k个最相近的物品。一旦最相似的物品找到了，然后就可以通过平均目标用户在这些相似物品上的权重来计算prediction了。我们称之为相似性计算和prediction生成。

1.物品相似性计算

基于物品的协同过滤算法最重要的一步就是计算物品的相似性然后选出最相近的物品。两个物品i和j之间的相似度计算的基本思想是隔离对这两个项目都进行过评分的用户，然后应用相似度计算技术确定相似度s_i,j。图2指出了具体的计算方式。行代表用户，列代表物品。

此处的isolate这个单词按我的理解是挑选出这些进行计算的意思，一开始的时候以为把这些筛选掉，那么下面的图右方的解释相矛盾了。

图右边说明的意思：

物品与物品的相似性是通过研究同时打分的物品来的。在计算Item i和j的相似性s_i,j的时候，每一对都是来自不同的用户，在这个例子中他们是来自1，u还有m-1。

有很多方式来计算物品之间的相关性，下面叙述三种。

1.cosine相似性

在这个例子中，两个物品是在m维用户空间中的两个向量（结合图2就知道为什么是两个m维向量了）。图2两个向量中i与j的相似性sim(i,j)的计算方式如下：
sim ⁡ ( i , j ) = cos ⁡ ( i ⃗ , j ⃗ ) = i ⃗ ⋅ j ⃗ ∥ i ⃗ ∥ 2 ∗ ∥ j ⃗ ∥ 2 \operatorname{sim}(i, j)=\cos (\vec{i}, \vec{j})=\frac{\vec{i} \cdot \vec{j}}{\|\vec{i}\|_{2} *\|\vec{j}\|_{2}} sim(i,j)=cos(i ,j ​)=∥i ∥2​∗∥j ​∥2​i ⋅j ​​
其中“·”代表两个向量点乘的意思。

2.基于correlation相似性(皮尔逊相关性)

在计算之前我们必须选出（isolate）两个物品i和j都评价过的用户，然后利用这些用户进行下面的计算：
sim ⁡ ( i , j ) = ∑ u ∈ U ( R u , i − R ˉ i ) ( R u , j − R ˉ j ) ∑ u ∈ U ( R u , i − R ˉ i ) 2 ∑ u ∈ U ( R u , j − R ˉ j ) 2 \operatorname{sim}(i, j)=\frac{\sum_{u \in U}\left(R_{u, i}-\bar{R}_{i}\right)\left(R_{u, j}-\bar{R}_{j}\right)}{\sqrt{\sum_{u \in U}\left(R_{u, i}-\bar{R}_{i}\right)^{2}} \sqrt{\sum_{u \in U}\left(R_{u, j}-\bar{R}_{j}\right)^{2}}} sim(i,j)=∑u∈U​(Ru,i​−Rˉi​)2 ​∑u∈U​(Ru,j​−Rˉj​)2 ​∑u∈U​(Ru,i​−Rˉi​)(Ru,j​−Rˉj​)​
R_u,i代表的是用户u对物品i的评分， R i ˉ \bar{R_i} Ri​ˉ​代表物品i的平均得分。

3.改进的cosine相似性

基于用户的协同过滤网络和基于物品的协同过滤网络在计算相似性时一个主要的不同就是基于用户的协同过滤网络在矩阵中是按行来计算的，每一对代表不同用户的评价。使用cosine来进行相似性计算有很大的不足，不同用户的评价范围是不同的。经过改善的cosine相似性通过减去响应用户的平均值抵消掉了这部分的误差。相似性计算如下：
sim ⁡ ( i , j ) = ∑ u ∈ U ( R u , i − R ˉ u ) ( R u , j − R ˉ u ) ∑ u ∈ U ( R u , i − R ˉ u ) 2 ∑ u ∈ U ( R u , j − R ˉ u ) 2 \operatorname{sim}(i, j)=\frac{\sum_{u \in U}\left(R_{u, i}-\bar{R}_{u}\right)\left(R_{u, j}-\bar{R}_{u}\right)}{\sqrt{\sum_{u \in U}\left(R_{u, i}-\bar{R}_{u}\right)^{2}} \sqrt{\sum_{u \in U}\left(R_{u, j}-\bar{R}_{u}\right)^{2}}} sim(i,j)=∑u∈U​(Ru,i​−Rˉu​)2 ​∑u∈U​(Ru,j​−Rˉu​)2 ​∑u∈U​(Ru,i​−Rˉu​)(Ru,j​−Rˉu​)​
在这个公式中， R u ˉ \bar{R_u} Ru​ˉ​是第u个用户打分的平均值。

2.prediction计算

一旦我们基于设定的相似性标准挑选出了最相似的物品，下一步就是研究目标用户的打分然后获得prediction。作者提出了两种方法。

1.权重加和

为了计算用户u对物品i的prediction，这种方法计算用户u对于和i相似的产品打分的加和。每个打分通过物品i与j的相似性s_i,j来进行衡量。用P_u,i这个指标来进行衡量：
P u , i = ∑ all similar items,  N ( s i , N ∗ R u , N ) ∑ all similar items  , N ( ∣ s i , N ∣ ) P_{u, i}=\frac{\sum_{\text {all similar items, } \mathrm{N}}\left(s_{i, N} * R_{u, N}\right)}{\sum_{\text {all similar items }, \mathrm{N}}\left(\left|s_{i, N}\right|\right)} Pu,i​=∑all similar items ,N​(∣si,N​∣)∑all similar items, N​(si,N​∗Ru,N​)​
s_i,N表示物品i与N的相似度，R_u,N表示用户u对物品N的打分。这种方法尝试去观察用户是怎样给相似的物品打分。加权和由相似项之和缩放以确保预测在预定范围内。

2.回归

回归这种方法与权重加和不同的是它不是直接使用物品间的相似性，而是基于回归模型的打分的估计估计值。作者发现使用cosine或者correlation这两种度量方式有一些缺点：就是在两个向量距离很远的情况下，也可能有很大的相似性。使用这种所谓的相似物品可能会导致很差的预测效果。基本的思想与权重加和是一致的，就是不是用原生的打分数据，R_u,N，而是使用基于线性回归模型的R’_u,N。计算方法如下：
R N ′ ‾ = α R ˉ i + β + ϵ \overline{R_{N}^{\prime}}=\alpha \bar{R}_{i}+\beta+\epsilon RN′​​=αRˉi​+β+ϵ
其中参数α和β通过整个打分向量决定的。∈是回归模型的偏差。如何进行实现这个公式好像没有说。

3.性能含义

在基于用户的协同过滤算法中，用户-用户相似性计算是整个系统性能的瓶颈。解决他的一个办法就是使用基于模型的推荐算法。在这篇论文中作者提出了一个基于模型的计算法方法。相似性计算依然是基于关系的，但是计算是在物品的空间内。物品相对于用户来说是相对静态的，变化是相对较少的。对于物品j来说我们只计算他们最相近的k个物品，k是远远小于n（物品总数）的。我们称k为model size。

为了给用户u对于物品i做出prediction，我们的算法首先查询预先计算好的k个最相似的物品，然后看这些物品用户买了多少，基于这些考虑然后计算预测值。

六、实验评估

1.数据集

Movie Data

80%训练集，20%测试集。在数据集中也提出了稀疏度这个概念：1- nonzero entries total entries \frac{\text{nonzero entries}}{\text{total entries}} total entriesnonzero entries​，在这篇文章中，我们把这个数据集成为ML。

数据集地址：https://grouplens.org/datasets/movielens/

2.评价标准

统计准确性指标：这个指标通过比较数字的推荐分数与测试数据集中的实际用户打分来评估系统的准确性。MAE是一个常用的打分预测标准。MAE是一个推荐与用户实际具体分数的偏差。MAE的计算方法是首先把N个绝对值误差相加，然后取平均值。
M A E = ∑ i = 1 N ∣ p i − q i ∣ N M A E=\frac{\sum_{i=1}^{N}\left|p_{i}-q_{i}\right|}{N} MAE=N∑i=1N​∣pi​−qi​∣​
MAE的值越小，则推荐系统预测的值越准确。Root Mean Squared Error（RMSE）和Correlation也经常用作统计准确性指标。

决策支持准确性指标:这个指标评价了一个预测引擎在帮助人们选择物品时的有效性。这种度量标准架设预测过程是一个二元操作——物品是预测的对还是不对。基于这种考虑，如果用户仅仅选择4分或者以上的物品，那么2.5分和1.5分是一样的。最常用的决策支持准确性指标有：reversal rate，weighted errors 和ROC sensitivity。我们使用MAE作为我们的评估标准。

1.实验过程

实验步骤：首先把数据分为训练集和测试集。然后再开始整个数据集训练之前我们首先确定不同算法的敏感度，然后从敏感度曲线我们修正最优值。为了确定参数的值，我们仅仅使用训练集，进一步把训练集分为训练集和测试集。我们做了一个10段的交叉训练集，然后最后取MAE的平均值。

基于用户系统的基准：为了比较基于物品的协同过滤算法的性能，我们也把训练集输入一个应用了Pearson紧邻（用户-用户）的算法。我们实现了一个灵活的基于用户的协同过滤系统，经过调试，我们使用了最好的基于Pearson紧邻算法，并且把它配置了一个最优的配置，不用担心性能问题。

实验平台：我们是用c实现的，并且使用一个优化标志——06。

3.实验结果

我们的结果主要分为两部分——质量结果和性能结果。在评价质量结果的时候，我们首先确定了一些参数，这些参数包括邻居的数量，训练集和测试集的比例x的值，还有不同的度量标准的影像。在确定参数时我们使用训练集，并且进一步将训练集划分为训练集和测试集。

这个地方不是特别懂，为什么要将训练集进一步划分为训练集和测试集呢？懂了以后回来继续补充。

1）相似算法的效果

我们实现了三种不同的相似性算法，基于cosine，基于调整的cosine和correlation，并且利用他们在我们的数据集上进行训练。对于每个相似算法，我们都计算他们的邻居并且使用权重加和来生成预测，我们使用训练集进行训练，使用测试集来计算MAE。

下图显示了实验结果。从结果可以看出，为余弦相似度计算偏离用户平均值（也就是减去用户的平均值）具有明显的优势，因为在这种情况下，MAE明显较低。 因此，我们为其余的实验选择调整后的余弦相似度。

2）训练集/测试集比例敏感度

为了决定数据集密度的敏感性，我们进行了一系列的实验，x从0.2到0.9，每次增加0.1。对于每个比例x我们都使用两种预测方案——权重加和和回归。当x增加时，预测的效果也会增加。一开始，基于回归的方法笔记本的方法要好，但是当我们增加x时，基于回归的方法效果开始下降。最后我们选择了0.8作为作为我们一个后续实验的一个最优值。

3）neighborhood size实验

邻居数量在预测效果上具有重大的影响，为了决定这个参数，我们改变了要在实验中要改变的邻居数量并且计算了MAE。计算结果如图5所示。我们可以观察到邻居的数量可以影响到预测的质量。但是这两个方法显示出不同的敏感度。当我们把邻居数量从10提升到30的时候，item-item方法不断的改善，然后就趋于平坦。在另一方面，基于回归的方法显示出了下降的效果。考虑到两种情况，我么选择30作为我们邻居参数的最优化选择。

MAE越小，效果越好，上面翻译的上升，下降都是指的实验效果，而不是说得曲线的上升或者下降。

4）质量实验

一旦我们获得了参数的最优值，我们就比较了基于物品的方法和基于用户的基准的方法。实验结果如下图所示。从图中可以看出，在不同x的情况下，item-item的算法比基于用户的算法要好。基于回归的方法比较有趣，当x比较低，邻居数比较小的时候他的表现比其它两个要好，但是当我们增加邻居数使得数据集的密度上升的时候，它表现更差，甚至比基于用户的算法更差。

我们从实验中可以得到下面的结果。首先，基于物品的算法效果比基于用户的算法在任何稀疏程度上都好。其次，基于回归的算法在数据稀疏的时候效果比较好，但是当我们加入更多的数据的时候效果反而下降了。

5）性能结果

当看到基于物品的算法性能比基于用户的算法效果好的时候，我们把注意力放在可扩展性的问题上，正如以前讨论的那样，基于物品的相似性时相对比较静态的，这就让我们可以提前计算相似的物品。对于物品相似性进行提前计算肯定会提高性能表现。为了提高系统的扩展性，我们深入调查了模型数量和它在响应时间和吞吐量上的影响。

4.模型大小的敏感度

为了确定model size的影响，我们选择了不同的物品数量，从25到200，每次递增25。model size为l意味着我们仅仅考虑l个最相似的值用来模型构建，然后使用他们中的k个用来进行预测生成，k

从图中我们可以看出，当我们一开始提高model size的时候，MAE效果越来越好，但是逐渐就开始平缓。在图中最重要的是，我们即使使用很少的一点物品，也能实现较大的准确度。model size的敏感度有很重要的意义。从图中可以看出，仅仅使用很少的一部分物品进行提前计算物品相似性并且可以获得很好的效果。

1）model size的大小对吞吐量和运行时间的影响

假设在很小的model size上预测结果还可以，我们来关注吞吐量和运行时间。我们记录了在整个测试集上需要生成预测的时间，然后在不同的model size下把他们画出来。我们画出了在不同x值下面的运行时间。

5.讨论

从实验中，我们可以看到一些重要的结论。第一，基于物品的推荐算法效果比基于用户的推荐算法效果要好。推荐效果的改善与邻居数还有训练集测试集比例是一致的。然而，改进却不是特别大的。第二，物品间的关系是相对静止的，这就导致了其可以进行提前计算，提升了在线计算的性能。其次，由于它是基于模型的方法，这就决定了他可以在一小部分数据集上产生较好的效果。我们的实验支持这个结论。因此，基于物品的模式可以处理两类最重要的问题——预测的质量问题还有高性能问题。

七、结论

在这篇论文中我们提出并且从实验上评估了基于物品的推荐算法。我们的结果展示出这个方法有希望可以扩展到大数据集上并且产生高质量的推荐。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！