一、ItemBased CF [2001]

《Item-Based Collaborative Filtering Recommendation Algorithms》

1. 世界上信息量的增长速度远远超过我们处理信息的能力。我们都有体会：被每年出版的海量的新书、期刊文章和会议纪要所淹没的感觉。技术大大降低了发布（publishing）和分发（distributing）信息的障碍。现在是时候创造新的技术，从而可以帮助我们从所有可用信息中找到最有价值的信息。

   此类最有前途的技术之一是协同过滤（collaborative filtering）。协同过滤的工作原理是建立用户对 item 的偏好数据库。对于一个新用户，假设叫做 Neo，我们从数据库中匹配邻居，这些邻居是历史上与 Neo 有相似品味（taste）的其它用户。然后我们将邻居喜欢的 item 推荐给 Neo，因为 Neo 可能也会喜欢这些 item。协同过滤在研究和实践中都非常成功，在信息过滤应用和电商应用中都非常成功。然而，协同过滤推荐系统有两个基本挑战仍然未能克服：

   • 可扩展性（scalability）：这些算法能够实时搜索数以万计的潜在邻居，但是现代系统需要搜索数千万个潜在邻居。由于整体计算复杂度为 $O(m^2\times \overline{n})$$O(m^2\times \bar n)$ ，其中 $m$$m$ 为用户数量、 $\overline{n}$$\bar n$ 为平均每个用户评分的item 数量，因此随着用户规模的增加其计算复杂度难以忍受。

     此外，现有算法对于拥有大量历史行为的单个用户（individual user）也存在性能问题。例如，某些用户可能在成千上万个item 上有过行为，那么这批用户会拖慢每秒可以搜索的相似用户的数量（因为计算用户之间的相似度的计算复杂度为 $O(n)$$O(n)$ ，$n$$n$ 为用户评分的 item 数量），从而进一步降低了可扩展性。

   • 推荐质量（quality）：用户需要他们可以信任的推荐，从而帮助他们找到感兴趣的 item。对于质量较差的推荐，用户一般都是“用脚投票”，直接拒绝使用该推荐系统。

   某种程度上这两个挑战是相互冲突的：算法花在搜索邻居上的时间越少，它的可扩展性就越强、推荐质量也就越差。出于这个原因，同时处理这两个挑战很重要，这样的解决方案既有效又实用。 论文 《Item-Based Collaborative Filtering Recommendation Algorithms》 提出了 Item-Based CF 来同时解决这两个挑战。

   传统的协同过滤算法的瓶颈是在大量用户中搜索邻居，而 Item-Based 算法通过首先探索 item 之间的关系、而不是用户之间的关系来避免这个瓶颈。通过查找用户喜欢item 相似的其它 item 来获取对用户的推荐。 由于 item 之间的关系是相对静态（static）的， Item-Based 算法可以减少在线计算的数量，同时保持与 User-Based 算法相同的推荐质量。

   论文主要贡献：

   • 分析 Item-Based 的预测算法，并识别（ identification）实现其子任务的不同方法。

   • 形式化 item 相似度的预计算模型（ pre-computed model），从而提高 Item-Based 推荐的在线可扩展性。

   • 几种不同的 Item-Based 算法与经典的 User-Based 算法（最近邻）的实验效果比较。

2. 相关工作：这里我们简要介绍一些与协同过滤、推荐系统、数据挖掘、以及个性化相关的研究文献。

   • Tapestry 是基于协同过滤的推荐系统的最早实现之一。该系统依赖于来自紧密社区（close-knit community）（如办公室工作组）的人们的显式意见（ explicit opinion），其中每个用户都了解其它用户。但是大型社区的推荐系统不能依赖于每个用户都了解其它用户。

     后来，人们开发了几个基于评级（ratings-based）的自动推荐系统。

     • GroupLens 研究系统为 Usenet 新闻和电影提供了匿名协同过滤解决方案。

     • Ringo 和 Video Recommender 是分别生成音乐推荐和电影推荐的 email-based 系统和 web-based 系统。

   • ACM 的通讯特刊《Recommender Systems》介绍了许多不同的推荐系统。

   • 其他技术也已经应用于推荐系统，包括贝叶斯网络、聚类（clustering）、以及Horting。

     • 贝叶斯网络创建一个基于训练集的模型，每个节点都有一个决策树，边代表用户信息。该模型可以在几个小时或者几天内离线构建。生成的模型非常小，速度非常快，并且基本上与最近邻方法一样准确。

       贝叶斯网络被证明可能适用于用户偏好缓慢变化（相对于构建模型所需的时间）的环境，但是不适用于必须快速或频繁更新用户偏好模型的环境。

     • 聚类技术通过识别似乎具有相似偏好的用户组（user group）来工作。一旦创建了簇（cluster），就可以通过对该簇中其它用户的意见进行平均来对单个用户进行预测。

       某些聚类技术将每个用户划分到多个 cluster，然后预测时按照跨 cluster 取加权平均值，权重是参与这个 cluster 的程度。

       聚类技术通常比其它方法产生较少个性化的推荐，并且在某些情况下聚类的准确性比最近邻算法更差。然而，一旦聚类完成，性能就会非常好，因为必须分析的组的数量要小得多。

       聚类技术也可以作为 first step 来应用，用于在最近邻算法中缩小候选集、或者在多个推荐引擎之间分配最近邻计算。虽然将用户划分为 clusters 可能会损害 cluster 边缘附近用户的准确性或推荐，但是 pre-clustering 可能是准确性和吞吐量之间的一个值得的 trade-off 。

     • Horting 是一种 graph-based 技术，其中节点是用户、节点之间的边表示两个用户之间的相似程度。预测是通过游走到附近节点，然后结合附近用户的意见来产生的。

       Horting 和最近邻不同，因为它探索了graph 上的高阶关系而最近邻仅探索 graph 上的一阶关系（直接关系），从而探索最近邻算法中没有考虑的信息传递。在一项使用人工合成数据的研究中，Horting 产生了比最近邻更好的预测算法。

   • 《Recommender Systems in E-Commerce》 展示了电商中使用的推荐系统的详细分类和示例，以及它们如何提供一对一的个性化，同时可以捕获客户忠诚度（loyalty）。

   尽管这些系统在过去取得了成功，但是它们的广泛使用暴露了它们的一些局限性，例如数据集的稀疏性问题、与高维相关的问题等。

   • 推荐系统中的稀疏性问题已经在

     《Using Filtering Agents to Improve Prediction Quality in the GroupLens Research Collaborative Filtering System》 和 《Combining Collaborative Filtering With Personal Agents for Better Recommendations》 中得到解决。

   • 推荐系统中与高维相关的问题已经在 《Learning Collaborative Information Filters》 中讨论过，在 《Application of Dimensionality Reduction in Recommender System -- A Case Study》 中已经研究了应用降维技术解决这些问题。

   我们的工作探索了 Item-Based 推荐算法（一类新的推荐算法）能够在多大程度上解决这些问题。

1.1 模型

1.1.1 CF-Based 推荐系统

1. 推荐系统主要解决以下问题：通过为给定用户生成预测的可能性得分、或者 top-N 的推荐 item 列表，从而帮助用户找到他们想在电商网站上购买的 item 。

   可以使用不同的方法进行 item 推荐，例如基于用户的人口统计（demographics）、热门 item 、或者用户历史购买习惯。协同过滤（Collaborative Filtering: CF）是迄今为止最成功的推荐技术。基于 CF 的算法的基本思想是：根据其他志趣相投用户的意见提供 item 推荐或预测。用户的意见可以显式（explicitly）地从用户那里获取，也可以通过一些隐式（implicit）的手段获取。

2. 协同过滤处理 Overview：协同过滤算法的目标是根据用户历史偏好、或者其他志趣相投用户的意见，为目标用户推荐新 item 或者预测某个 item 的效用 （utility）。

   在典型的 CF 场景中，有一个 $m$$m$ 个用户的列表 $\mathcal{U}=\{u_1,u_2,\cdots ,u_m\}$$\mathcal U=\{u_1,u_2,\cdots,u_m\}$ 、以及一个包含 $n$$n$ 个 item 的列表 $\mathcal{I}=\{i_1,i_2,\cdots ,i_n\}$$\mathcal I=\{i_1,i_2,\cdots,i_n\}$ 。每个用户 $u_i$$u_i$ 都有一个 item 列表 ${\mathcal{I}}_{u_i}$$\mathcal I_{u_i}$ ，对该列表中的每个 item，用户 $u_i$$u_i$ 已经表达了他/她的意见（opinion）。 意见可以由用户显式给出（如位于某个数字区间的评级分数 rating score），也可以通过分析日志从购买记录中隐式地获取。注意，${\mathcal{I}}_{u_i}\subseteq \mathcal{I}$$\mathcal I_{u_i}\sube \mathcal I$，并且 ${\mathcal{I}}_{u_i}$$\mathcal I_{u_i}$ 可能是空集。

   给定目标用户 $u_a\in \mathcal{U}$$u_a\in \mathcal U$，协同过滤算法的任务是为 $u_a$$u_a$ 找到一个 item 偏好（item likeliness）。这种偏好有两种形式：

   • 预测：预测用户 $u_a$$u_a$ 对于item $i_j\notin {\mathcal{I}}_{u_a}$$i_j\notin \mathcal I_{u_a}$ 的评分 $P_{a,j}$$P_{a,j}$ 。

   • 推荐：为用户 $u_a$$u_a$ 推荐他/她可能最喜欢的由 $N$$N$ 个 item组成的列表 ${\mathcal{I}}_r\subset \mathcal{I}$$\mathcal I_r\sub \mathcal I$ 。注意，推荐列表必须位于目标用户尚未购买的 item 上，即 ${\mathcal{I}}_r\cap {\mathcal{I}}_{u_a}=\mathrm{\Phi }$$\mathcal I_r\cap\mathcal I_{u_a} = \Phi$ 。这被称作 Top-N 推荐。

   下图给出了协同过滤任务的示意图。CF 算法将整个 $m\times n$$m\times n$ 个user-item 数据表示为一个评分矩阵 $\mathbf{R}$$\mathbf R$ ，矩阵中的每一个元素 $r_{i,j}$$r_{i,j}$ 表示第 $i$$i$ 个user 在第 $j$$j$ 个 item 上的评分。每个评分在一定范围之内（如 1~5 ），也可以为 0 ，表示用户尚未对该 item 评分。

   

   协同过滤算法可以分为两类：

   • memory-based基于内存的（也称作 user-based）协同过滤：利用整个评分矩阵来生成预测。

     该算法采用统计技术来找出与目标用户最相似的一组用户（称作邻居），然后使用不同的组合方式来组合这些邻居的偏好，从而为目标用户生成推荐或 Top-N 推荐。因此该技术也被称为最近邻（nearest-neighbor）或者 UserBased CF 技术。

   • model-based 基于模型的（也称作 item-based）协同过滤：通过建立用户打分模型来提供item 推荐。

     这些方法首采用概率性的方法（probabilistic approach），然后根据给定用户在其它item 评分的条件下来预测未打分item 上的评分。模型构建过程由不同的机器学习算法执行，例如贝叶斯网络、聚类、以及基于规则（rule-based）的方法。

     • 贝叶斯网络模型为协同过滤问题形式化了概率模型。

     • 聚类模型将协同过滤视为分类问题，并通过将相同类别的相似用户聚类，并估计给定用户属于特定类别 $C$$C$ 的概率来工作，并由此计算评分的条件概率。

     • 基于规则的方法应用关联规则挖掘（association rule discovery）算法来发现共同购买（co-purchase）的 item 之间的关联，然后根据 item 之间的关联强度生成 item 推荐。

3. User-Based CF 的挑战：User-Based 协同过滤系统在过去非常成功，但是它们的广泛使用暴露了一些潜在的挑战，例如：

   • 稀疏性（Sparsity）：在实践中，许多商业推荐系统用于评估大型 item 集合（如 Amazon.com 推荐书籍、CDnow.com 推荐音乐专辑）。在这些系统中，即使是活跃用户购买的 item 也可能占比远低于 1% （200 万本书的 1% 是 2 万本书）。因此，基于最近邻算法的推荐系统，其推荐的准确性可能很差。

     注意：因为 user 的行为太稀疏，导致 user-to-user 的相似度不可置信。

   • 可扩展性（Scalability）：最近邻算法的计算复杂度随着用户数量和 item 数量的增长而增长。对于数以百万的用户和 item，运行现有算法的、典型的 web-based 推荐系统将面临严重的可扩展性问题。

   最近邻算法在大型稀疏数据集上的弱点促使我们探索替代的推荐系统算法。

   我们的第一种方法试图将半智能过滤代理 （semi-intelligent filtering agent）结合到推荐系统中来，从而弥合稀疏性。这些代理使用文法特征（syntactic feature）对每个 item 进行评估和打分。通过提供稠密的评分集合，它们有助于缓解覆盖度（ coverage）并提高推荐质量（quality）。然而，过滤代理解决方案并没有解决志趣相同、但是评分稀疏的用户之间关系不佳的根本问题。为了探索这一点，我们采用了一种算法方法，并使用潜在语义索引（Latent Semantic Indexing: LSI）来捕获降维空间中用户和 item 之间的相似度。

   在本文中我们研究了另一种技术，即 model-based 方法，来应对这些挑战，尤其是可扩展性挑战。这里的主要思想是分析 user-item 表示矩阵 （representation matrix）来识别不同 item 之间的关系，然后利用这些关系来计算目标 user-item pair 的预测分。这种方法背后的直觉是：用户有兴趣购买历史喜欢 item 类似的 item，并倾向于厌恶历史不喜欢 item 类似的 item。这些技术不需要在请求推荐时识别用户的相似用户，因此它们往往会更快地给出推荐。

   已经有很多不同的方案来计算 item 之间的关联，从概率性方法到更传统的 item-item 相关性。接下来我们将详细分析我们的方法。

1.1.2 Item-Based CF

3. 这里我们研究了一类 Item-Based 的推荐算法，用于对用户进行推荐预测。与前面讨论的 User-Based CF 算法不同，Item-Based 的方法查看目标用户历史评分 item 集合并计算它们与目标 item $i$$i$ 的相似度，然后选择 top-k 最相似的 item $\{i_1,i_2,\cdots ,i_k\}$$\{i_1,i_2,\cdots,i_k\}$。同时，top-k $item$$item$ 对应的相似度 $\{s_{i_1},s_{i_2},\cdots ,s_{i_k}\}$$\{s_{i_1},s_{i_2},\cdots,s_{i_k}\}$ 也被计算。

   一旦得到最相似的item 及其相似度，我们可以通过目标用户对这些相似item 已有评分的加权均值来执行预测。我们这里详细描述了这两个方面，即相似度计算和预测生成。

4. Item 相似度计算：Item-Based CF 最关键的步骤之一是如何计算 item 之间的相似度。计算item $i,j$$i,j$ 之间相似度的基本思想是：首先挑选既对 $i$$i$ 打分、又对 $j$$j$ 打分的用户 ${\mathcal{U}}_{i,j}$$\mathcal U_{i,j}$ ，然后基于这些用户的打分来计算相似度 $s_{i,j}$$s_{i,j}$ 。下图给出了这一过程，其中矩阵的行代表user、列代表 item 。

   

   其中有多种方法可以计算 item 之间的相似度，我们这里介绍三种方法，即基于余弦（cosine-based）的相似度、基于相关系数（correlation-based）的相似度、基于修正余弦（adjusted-cosine based）的相似度。

   • 基于余弦的相似度（cosine-based similarity）：两个 item 被认为是 $m$$m$ 维用户空间中的两个向量。它们之间的相似度是通过计算这两个向量之间夹角的余弦来衡量的。

     $$\text{sim}(i,j)=\cos ({\overrightarrow{\mathbf{r}}}_{\cdot ,i},{\overrightarrow{\mathbf{r}}}_{\cdot ,j})=\frac{\sum _{u\in {\mathcal{U}}_{i,j}}{r}_{u,i}\times r_{u,j}}{\sqrt{\sum _{u\in {\mathcal{U}}_{i,j}}{r}_{u,i}^2}\sqrt{\sum _{u\in {\mathcal{U}}_{i,j}}{r}_{u,j}^2}}$$

     其中 $r_{u,i}$$r_{u,i}$ 为用户 $u$$u$ 在 item $i$$i$ 上的评分。我们只考虑 ${\mathcal{U}}_{i,j}$$\mathcal U_{i,j}$ 。

   • 基于相关系数的相似度（correlation-based similarity）：两个 item 之间的相似度是通过计算 Pearson-r 相关系数 ${\text{corr}}_{i,j}$$\text{corr}_{i,j}$ 来衡量的。

     $$\text{sim}(i,j)=\frac{\sum _{u\in {\mathcal{U}}_{i,j}}(r_{u,i}-{\overline{r}}_i)(r_{u,j}-{\overline{r}}_j)}{\sqrt{\sum _{u\in {\mathcal{U}}_{i,j}}(r_{u,i}-{\overline{r}}_i{)}^2}\sqrt{\sum _{u\in {\mathcal{U}}_{i,j}}(r_{u,j}-{\overline{r}}_j{)}^2}}$$

     其中 ${\overline{r}}_i=\frac{\sum _{u\in {\mathbb{U}}_{i,j}}{r}_{u,i}}{|{\mathcal{U}}_{i,j}|}$$\bar r_i = \frac{\sum_{u\in \mathbb U_{i,j}}r_{u,i}}{|\mathcal U_{i,j}|}$ 为item $i$$i$ 在 ${\mathcal{U}}_{i,j}$$\mathcal U_{i,j}$ 上的打分均值。

     如果令 ${\overrightarrow{\mathbf{r}}}_{\cdot ,i}^{\ast }={\overrightarrow{\mathbf{r}}}_{\cdot ,i}-{\overline{r}}_i$$\mathbf{\vec r}^*_{\cdot,i} = \mathbf{\vec r}_{\cdot,i} - \bar r_i$ ，则上式等价于：$\text{sim}(i,j)=\cos ({\overrightarrow{\mathbf{r}}}_{\cdot ,i}^{\ast },{\overrightarrow{\mathbf{r}}}_{\cdot ,j}^{\ast })$$\text{sim}(i,j) = \cos\left(\mathbf{\vec r}^*_{\cdot,i},\mathbf{\vec r}^*_{\cdot,j}\right)$ 。

   • 基于修正余弦的相似度（adjusted-cosine similarity）：基于余弦的相似度有个缺陷：未考虑不同用户之间的打分差异。修正的余弦相似度通过从每个用户的打分中减去该用户的打分均值来修复这个问题：

     $$\text{sim}(i,j)=\frac{\sum _{u\in {\mathcal{U}}_{i,j}}(r_{u,i}-{\overline{r}}_u)(r_{u,j}-{\overline{r}}_u)}{\sqrt{\sum _{u\in {\mathcal{U}}_{i,j}}(r_{u,i}-{\overline{r}}_u{)}^2}\sqrt{\sum _{u\in {\mathcal{U}}_{i,j}}(r_{u,j}-{\overline{r}}_u{)}^2}}$$

     其中 ${\overline{r}}_u$$\bar r_u$ 是用户 $u$$u$ 在他/她所有打分item 上的打分均值。

     如果令 $r_{u,i}^{\ast }=r_{u,i}-{\overline{r}}_u$$r^*_{u,i} = r_{u,i} - \bar r_u$ ，则上式等价于：$\text{sim}(i,j)=\cos ({\overrightarrow{\mathbf{r}}}_{\cdot ,i}^{\ast },{\overrightarrow{\mathbf{r}}}_{\cdot ,j}^{\ast })$$\text{sim}(i,j) = \cos\left(\mathbf{\vec r}^*_{\cdot,i},\mathbf{\vec r}^*_{\cdot,j}\right)$ 。它和基于相关系数的相似度区别在于：后者仅考虑 item $i$$i$ 和 item $j$$j$ 的评分，而前者考虑了整个评分矩阵的评分。

5. 预测：协同过滤系统中最重要的一步是生成预测。一旦我们根据相似性得到了目标item $i$$i$ 最相似的一组item，则下一步是为用户执行打分预测。这里我们考虑两种技术：

   • 加权和（weighted sum）：该方法通过计算用户 $u$$u$ 对 item $i$$i$ 相似 item 给出的评分的加权和，从而计算用户 $u$$u$ 对 item $i$$i$ 的预测。加权的权重为 item $i$$i$ 和 $j$$j$ 之间的相似度 $s_{i,j}$$s_{i,j}$ 。

     使用下图中的概念，我们可以将预测 $P_{u,i}$$P_{u,i}$ 表示为：

     $$P_{u,i}=\frac{\sum _{j\in \text{all similar items}}{s}_{i,j}\times r_{u,j}}{\sum _{j\in \text{all similar items}}|s_{i,j}|}$$

     这种方式捕获了目标用户 $u$$u$ 对相似 item 的评分。加权的权重进行了归一化，从而确保预测打分在预定范围内。

     下图中，使用了 5 个相似的 item 来进行预测。

     

   • 回归（regression）：这种方式类似于加权和，但是不是直接使用相似item 的打分，而是基于回归模型来拟合的修正打分。

     实践中使用余弦相似度或者相关系数相似度可能导致两个向量相似度很高，但是实际上差距很远（夹角相同，长度差异较大）。这种情况下使用原始评分来计算，可能会导致预测不佳。

     回归方法的思想是：采用加权和相同的公式，但是不使用原始打分 $r_{u,j}$$r_{u,j}$ ，而是使用基于线性回归的近似值 $r_{u,j}^{\prime }$$r_{u,j}^\prime$ 。假设目标 item $i$$i$ 的打分向量为 ${\overrightarrow{\mathbf{r}}}_{\cdot ,i}$$\mathbf{\vec r}_{\cdot,i}$ ，相似 item $j$$j$ 的修正打分为：

     $${\overrightarrow{\mathbf{r}}}_{\cdot ,j}^{\prime }={\alpha }_{i,j}{\overrightarrow{\mathbf{r}}}_{\cdot ,i}+{\beta }_{i,j}$$

     然后根据 $\arg \underset{{\alpha }_{i,j},{\beta }_{i,j}}{min}||{\overrightarrow{\mathbf{r}}}_{\cdot ,j}^{\prime }-{\overrightarrow{\mathbf{r}}}_{\cdot ,j}|{|}^2$$\arg\min_{\alpha_{i,j},\beta_{i,j}}||\mathbf{\vec r}_{\cdot,j}^\prime- \mathbf{\vec r}_{\cdot,j}||^2$ 最小化来求解参数 ${\alpha }_{i,j},{\beta }_{i,j}$$\alpha_{i,j}, \beta_{i,j}$ 。最终有：

     $$P_{u,i}=\frac{\sum _{j\in \text{all similar items}}{s}_{i,j}\times r_{u,j}^{\prime }}{\sum _{j\in \text{all similar items}}|s_{i,j}|}$$

6. 性能分析：User-Based CF 中，邻域的生成过程，尤其时user-user 相似度计算步骤被证明是性能瓶颈，从而使得整个过程不适合实时推荐。在本文中，我们提出了一种 model-based 方法来预计算 item-item 相似度得分。相似度计算方案仍然是基于相关性的（如基于相关系数或者基于余弦），但是计算是在 item 空间上执行的。在典型的电子商务场景中，与经常变化的用户数量相比，item 数量相比之下更为静态（static）。item 的静态属性使得我们想到了预计算item 相似性的想法。

   预计算 item 相似度的一种可能方法是计算所有item 之间的相似度，然后执行快速查表从而检索到所需的相似度。这种方法虽然节省时间，但是对于 $n$$n$ 个 item 需要 $O(n^2)$$O(n^2)$ 的空间。事实上对于任何一个目标item，我们只需要一小部分最相似的 item 来预测，这使得我们找到了一种替代的 mode-based 方案。因此对于每个 item，我们仅计算 $k$$k$ 个最相似的 item，其中 $k\ll n$$k\ll n$ 。我们称 $k$$k$ 为模型大小。

   基于这个模型构建步骤，为目标用户 $u$$u$ 生成对目标 item $i$$i$ 的预测的工作原理如下。

   • 邻域生成过程：首先检索与目标 item $i$$i$ 对应的、预计算的 $l$$l$ 个最相似的 item。

     这里的 $l<k$$l \lt k$ 表示预测时使用的相似 item 数量，它不同于模型大小 $k$$k$ （表示预计算相似度的 item 数量）。

   • 预测生成过程：查看用户 $u$$u$ 购买了这 $l$$l$ 个 item 中的多少个，基于此交集使用 Item-Based CF预测算法。

   这里有质量和性能的权衡（quality-performance trade-off）：为了确保高质量，我们必须有较大的模型大小 $k$$k$ ，而这会导致推荐的可扩展性问题。在极端情况下我们可以将模型大小设置为 $n$$n$，这将确保与原始Item-Based CF完全相同的质量，但是具有很高的空间复杂度。然而，我们的替代方案确保我们保留最相似的 item，在生成预测时这些 item 对预测结果的贡献最大。因此，我们假设这种替代方案即使在 $k$$k$ 很小时也能够提供相当好的预测质量，从而提供良好的可扩展性。

   我们后续实验验证了我们的假设。具体而言，我们通过改变 $k$$k$ 值来验证模型大小对整个系统的质量和性能的影响。

7. 读者注：理论上也可以将 User-Based CF 拆分为两阶段：邻域生成 + 预测生成。考虑到用户行为非常稀疏，因此用户的任何新的行为对 user-user 相似度影响较大。因此user-user 相似度必须根据最近的用户行为在线实时计算。

   相对来说，用户的任何新的行为对 item-item 相似度影响较小，因此 item-item 相似度相对静态，可以离线计算。

   如：假设user-item 矩阵规模为 1000 万用户、100 万item。假设平均每个用户对 5 个 item 进行打分，则平均每个item 包含50 个用户。假设某个用户 $u$$u$ 刚刚对一个新的item $j$$j$ 进行打分，则它会影响所有涉及到u 的user-user 相似度，相似度波动范围大致为 20% ；它也会影响所有涉及到 $j$$j$ 的item-item 相似度，但是相似度波动范围大致为 2% 。因此相对而言，item-item 相似度要稳定得多。

   其本质是 user-item 矩阵的行比列更为稀疏。

1.2 实验

1. 数据集：我们使用MovieLens 数据集来评估Item-Based CF 的效果。MovieLens 是一个 web-based 的研究（research）推荐系统，于 1997 年秋季首次亮相。每周都有数百名用户访问 MovieLens 来评估和接受电影推荐。该网站现在拥有超过 43000 名用户，他们对 3500 多部电影进行评分。我们随机选择打分超过20 部电影的用户及其对应的电影评分，得到十万个打分，其中包括943 个用户、1682 部电影。即我们的 user-item 矩阵 $\mathbf{R}\in {\mathbb{R}}^{943\times 1682}$$\mathbf R\in \mathbb R^{943\times 1682}$ 。

   我们将数据集随机拆分为训练集和测试集，拆分比例为 $x$$x$ 。如， $x=0.8$$x=0.8$ 表示 80% 的训练集和 20% 的测试集。实验中我们还考虑了数据集的稀疏水平（ sparsity level）。给定一个矩阵，我们定义它的稀疏水平为：

   $$\text{sparsity-level}=1-\frac{{\text{num}}_{nz}}{{\text{num}}_{all}}$$

   其中 ${\text{num}}_{nz}$$\text{num}_{nz}$ 表示矩阵非零元素的总数，${\text{num}}_{all}$$\text{num}_{all}$ 表示矩阵所有元素的总数。我们数据集的稀疏水平为 $1-\frac{100000}{942\times 1682}=0.9369$$1-\frac{100000}{942\times 1682} = 0.9369$ 。

2. 评估指标：推荐系统用来评估推荐质量的指标主要可以分为两类：

   • 统计准确性指标（statistical accuracy metrics）：通过测试集上user-item 的真实打分和预测打分的对比，从而评估推荐的准确性。

     平均绝对误差 MAE 是其中应用广泛的指标。对每个真实打分和预测打分pair 对 $<p_i,q_i>$$<p_i,q_i>$ ，平均绝对误差为 $|p_i-q_i|$$|p_i-q_i|$ 。考虑所有的 $N$$N$ 组测试数据，则有：

     $$\text{MAE}=\frac{1}{N}\sum _{i=1}^N|p_i-q_i|$$

     MAE 越低则推荐质量越好。

     另外，均方误差（RMSE）、相关系数（Correlation）也是类似的统计意义上的准确率指标。

   • 决策支持准确性指标（decision support accuracy metrics）：评估推荐系统帮助用户筛选高质量item 的有效性。

     事实上给用户推荐item 之后，用户会在被推荐item 上给出反馈：推荐有效（用户感兴趣）还是推荐无效（用户不感兴趣）。因此这是一个典型的二元分类：有效推荐则为1、无效推荐则为 0 。我们认为用户打分在4.0 分及以上的 item 是有效推荐（5 分制），从而根据预测的二元标签和真实的二元标签得到precision、recall、auc 等指标。这种做法基于我们的观察：对于一个无效推荐的item，算法预测它是 1.5 分还是 2.5 分没有任何意义。

   实验中我们使用 MAE 来报告实验结果，因为它最常用并且最容易直观的解释。另外我们每次随机选择不同的训练集和测试集，重复进行10-fold 交叉验证并报告MAE 的均值。

3. baseline 模型：一个 User-Based CF 模型（基于 Pearson 最近邻算法 ），该模型召回全量的 user-user 相似度而不考虑计算代价。我们调优了该算法的超参数，从而得到最好的 Pearson 最近邻算法。

4. 实验配置：我们首先将数据集划分为训练集和测试集 。在开始对不同算法进行全面的实验评估之前，我们确定了不同算法对不同超参数的敏感性，并从敏感性实验中确定了这些超参数的最佳值，并且将这些最佳超参数用于剩余的实验。

   为了确定超参数敏感性，我们仅使用训练集，并将其进一步细分为 “训练--训练集” 和 “训练--验证集”，并对其进行实验。

   所有的实验都是使用 C 语言实现，在基于 linux 的 PC 上运行实验。PC 配置为 600M HZ 的 Intel Pentium III 处理器以及 2GM 内存。

5. 实验结果主要分为推荐质量结果和推荐性能结果两部分。为了得到较高的推荐质量，我们首先确定了一些超参数敏感性，包括：邻域大小 $l$$l$ 、训练集拆分比例 $x$$x$ 、不同的相似度度量。

6. 超参数敏感性：为了确定各种超参数的敏感性，我们仅关注训练集，并将原始的训练集进一步拆分为 “训练--训练集” 和 “训练--验证集”。

   • 相似度算法的影响：我们实现了三种不同的相似度算法，包括基础的余弦相似度、修正的余弦相似度、相关性相似度，并在我们的数据集上测试它们。对于每种相似度算法，我们基于加权和算法来生成预测。实验结果如下图所示，我们给出了验证集的 MAE 。可以看到：修正的余弦相似度效果最好，因为它的 MAE 明显更低。因此，在接下来的实验中我们选择修正的余弦相似度。

     

   • 训练集测试集拆分比例的影响：为了确定数据集密度的敏感性，我们以 0.1 的增量将 $x$$x$ 的值从 0.2 增加到 0.9 。我们分别使用两种预测生成技术：最简单的加权和，以及基于回归的加权和。实验结果如下图所示。

     可以看到：预测质量随着 $x$$x$ 的增加而得到提高。对于较小的 $x$$x$ ，基于回归加权和的方法更好；随着 $x$$x$ 的增加，基于简单加权和的方法反而更好。

     我们从曲线图中选择 $x=0.8$$x=0.8$ 作为后续实验的参数。

     

   • 邻域大小 $l$$l$ ：邻域大小 $l$$l$ 对预测质量有着显著的影响。 为了确定该参数的敏感性，我们针对不同 $l$$l$ 值得到了验证 MAE。我们分别使用两种预测生成技术：最简单的加权和，以及基于回归的加权和。实验结果如下图所示。

     可以看到：邻域大小 $l$$l$ 确实会影响预测的质量。但是这两种预测生成技术表现出不同的敏感性：当邻域大小从 10 增加到 30 时：

     • 简单加权和的方法的推荐质量一直得到改善，但是改善的速度逐渐降低，MAE 曲线趋于平缓。

     • 基于回归的加权和的方法推荐质量反而逐渐下降。

     我们选择 $l=30$$l=30$ 作为最佳邻域大小。

     注意：这里离线预计算 item-item 相似度时，保留全量的相似度（即模型大小 $k=n$$k=n$ ）。

     

7. 推荐质量：一旦获得了最佳超参数，我们将User-Based CF 和 Ite-Based CF 进行比较，我们也比较了非个性化算法（non-personalized）（如推最热门的），结果如下所示。

   可以看到：

   • 简单加权和的 Item-Based CF 在所有 $x$$x$ （邻域大小为30）、以及所有邻域尺寸（ $x=0.8$$x=0.8$ ）上的表现都最好。例如在 $x=0.5$$x=0.5$ （邻域大小为 30）时，User-Based CF 的测试 MAE = 0.755，而简单加权和 Item-Based CF 的测试 MAE = 0.749 ；而在邻域大小为 60 （$x=0.8$$x=0.8$） 时，User-Based CF 的测试 MAE = 0.732，而简单加权和 Item-Based CF 的测试 MAE = 0.726 。

   • 回归加权和的Item-Based CF 的表现比较有趣：它在非常小的 $x$$x$ 和非常小的邻域大小上战胜了其它两个算法。但是随着 $x$$x$ 的增加或者邻域尺寸的扩大，它的表现反而更差，甚至比 User-Based CF 效果都要差。

   • 我们还将我们的算法与朴素的非个性化算法进行了比较。

   我们从这些结果中得出两个结论：

   • 首先，简单加权和的Item-Based CF 算法在所有稀疏级别上都比 User-Based CF 算法提供更好的推荐质量。

   • 其次，回归加权和的Item-Based CF 算法在非常稀疏的数据集上表现更好，但是随着我们添加更多数据，推荐质量会下降。我们认为这是由于模型过拟合。

   

8. 推荐性能：在表明Item-Based CF 算法比 User-Based CF 算法提供更好的预测质量之后，我们将重点放在可扩展性问题上。如前所述，Item-Based 的相似度更加静态，并允许我们预计算 item 邻居。模型的这种预计算具有一定的性能优势。为了提高系统的可扩展性，我们研究了模型大小 $k$$k$ 的敏感性，然后研究了模型大小对响应时间和吞吐量的影响。

9. 推荐质量对模型大小 $k$$k$ 的敏感性：我们将相似度计算的 item 数量 $k$$k$ 从 25 增加到 200 ，增量为 25 。模型大小 $k$$k$ 意味着我们仅考虑 $k$$k$ 个最相似的 item 来构建模型，然后使用其中的 $l$$l$ 个用于预测生成过程，其中 $l<k$$l\lt k$ 。我们前面讨论的 $k$$k$ 等于全量的 item 。下图给出了不同 $x$$x$ 值在不同模型大小上的验证MAE 。另外我们还给出全量 $k$$k$ 的测试 MAE（虚线之后的最后一个点）。

   可以看到：

   • 随着 $k$$k$ 的增加，MAE 的值会改善，但是改善的效果逐渐降低。

   • 仅仅使用一小部分item 即可实现高准确性。在 $x=0.8$$x=0.8$ 时，我们保留 1.5% 的模型大小（$k=25$$k=25$ 时，验证 MAE=0.754 ）即可得到全尺寸模型（$k=n$$k=n$ 时，MAE=0.726 ）96% 的准确性；保留 3% 的模型大小（$k=50$$k=50$ 时，验证 MAE=0.738 ）即可得到全尺寸模型 98.3% 的准确率。

     这种模型大小敏感性具有重要的性能影响，这表明仅使用一小部分 item 来预计算 item 相似度很有效，并且仍然可以获得良好的预测质量。

     

10. 模型大小 $k$$k$ 对于运行时间和吞吐量的影响：我们记录测试集生成预测结果所需要的时间，注意不同的 $x$$x$ 拥有不同的测试集大小。

    可以看到：小尺寸模型和全尺寸模型的预测结果生成时间存在很大差异。

    • 当 $x=0.25$$x=0.25$ （测试集大小 7.5 万）$k=200$$k=200$ 的模型的运行时间为 2.002 秒，而全尺寸模型为 14.11 秒。

    • 当 $x=0.8$$x=0.8$ （测试集大小 2 万）$k=200$$k=200$ 的模型的运行时间为 1.292 秒，而全尺寸模型为 36.34 秒。

    

    由于不同 $x$$x$ 的测试集大小不同，因此我们根据吞吐量重新绘制了下图。可以看到：

    • 当 $x=0.3$$x=0.3$ 时，$k=100$$k=100$ 的模型1.487 秒完成 7 万个测试样本的打分，即 47361 个/秒，而全尺寸模型只有 4961 个/秒。

    • 当 $x=0.8$$x=0.8$ 时， $k=100$$k=100$ 的模型吞吐量为 21505 个/秒，全尺寸模型只有 550 个/秒。

    

11. 讨论：从 Item-Based CF 的试验评估中，我们得出了一些重要的观察：

    • 首先， Item-Based CF 比使用 User-Based CF 提供更好的预测质量。预测质量的提高在不同邻域大小 $l$$l$ 和训练集比例 $x$$x$ 上是一致的，但是改进并不显著。

    • 其次，item 邻域是相当静态的，可以预计算，这会导致非常高的在线性能。

    • 此外，model-based 方法可以只保留一小部分 item 并产生相当好的预估质量。我们的实验结果支持这一说法。因此， Item-Based CF 能够解决电商推荐系统中的两个最重要的挑战：预测质量和预测性能。