推荐系统-传统算法

一、Tapestry[1992]

1. 在1992 年的论文《Using Collaborative Filtering to Weave An Information Tapestry》 中，论文提出了一个基于协同过滤collaborative filtering 的电子邮件过滤系统。

   Tapestry 是 Xerox Palo Alto 研究中心开发的实验邮件系统，其动机来自于电子邮件的日益使用，导致用户被大量的邮件所淹没。

   处理大量电邮的一种方法是提供邮件列表，这使得每个用户只能订阅他们感兴趣的那些列表。但是，特定用户感兴趣的文档集合很少能够完整的映射到现有的列表。

   更好的解决方式是为每个用户指定一个filter 过滤器，该过滤器将扫描所有的列表，然后在所有列表中选择用户感兴趣的文档。

   目前已经有一些邮件系统支持基于文档内容的过滤。 Tapestry 系统可以在基于内容的过滤之外，通过引入人们的行为来执行更有效的过滤，这种过滤被称作协同过滤 collaborative filtering 。

   协同过滤通过记录人们对于他/她所阅读文档的反应reaction来协同从而帮助彼此进行过滤，这种反应可能是文档特别有趣（或者特别无趣）。这些反应（通常也被称作注解 annotation ）可以由其它过滤器访问。

2. 下图给出了Tapestry 的整体架构：

   • Indexer：从电子邮件、Netnews 等外部来源读取文档，并将其添加到 Document Store 中。Indexer 负责将文档解析为一组索引字段从而方便在query 中使用。
   • Document store：为所有 Tapestry 文档提供长期存储，该存储仅支持追加。它还在存储的文档上维护索引，以便可以有效地执行对文档数据库的 query 。
   • Annotation store：为文档关联的注解提供长期存储，该存储也只支持追加。
   • Filterer：重复对文档集合运行用户指定的一组query，那些与query 匹配的文档将被返回。
   • Little box：将特定用户感兴趣的文档排队。每个用户都有一个 little box，它里面的文件由过滤器填充，并由用户的文件阅读器消费。
   • Remailer：通过电子邮件定期的将little box 的内容发送给用户。
   • Appraiser：对用户的文档进行个性化分类（如用户的 little box 中的文档）。该功能可以自动地对文档进行优先级排序和分类。
   • Reader~Browser：提供用于访问Tapestry 服务的用户界面，如添加/删除/编辑过滤器、检索新文档、显示文档等。

   

3. 在 Tapestry 系统中，用户需要显式指定协同的用户以及该用户的行为构建协同过滤器。在后续的演变过程中，协同过滤已经改进了这种方式，无需用户手动指定即可实现协同过滤。

二、GroupLens[1994]

1. 在1994 年的论文《GroupLens: An Open Architecture for Collaborative Filtering of Netnews》 进一步的发扬了这种UserBased 协同过滤的思想。

   GroupLens 是一个采用协同过滤的网络新闻过滤系统，它设计了一种机制来帮助用户筛选他/她感兴趣的新闻。GroupLens 基于一个朴素的思想：用户在过去的兴趣会延续到将来。

   GroupLens 利用了用户对文章的评分：

   • 首先计算不同用户的评分序列之间的相关性，从而得到用户兴趣之间的相似性。
   • 然后根据相似用户的评分来预测当前用户对于新文章的评分。

2. 给定评分矩阵：

   $$\mathbf R = \begin{array}{c|cccc} &\text{item}_1&\text{item}_2&\cdots &\text{item}_n\\ \hline \text{user}_1& r_{1,1}&r_{1,2}&\cdots&r_{1,n}\\ \text{user}_2& r_{2,1}&r_{2,2}&\cdots&r_{2,n}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \text{user}_m& r_{m,1}&r_{m,2}&\cdots&r_{m,n} \end{array}$$

   其中 $r_{i,j}$ 表示用户 $i$ 对于文章 $j$ 的评分，该评分可能是已知的，也可能是未知的（因为用户尚未阅读该文章）。当用户评分未知时，我们将其填充为 $r_{i,j} = 0$

   GroupLens 首先计算用户兴趣之间的相似性。给定用户 $u$ 和 $v$ ，定义他们共同评分的文章集合为：

   $$\mathbb I_{u,v} = \{j\mid r_{u,j}\gt 0\; \text{and}\; r_{v,j}\gt 0\}$$

   然后计算用户 $u,v$ 在这些共同评分文章上的均值、方差、以及协方差：

   $$\bar r_u = \frac{1}{|\mathbb I_{u,v}|}\sum_{j\in \mathbb I_{u,v}}r_{u,j},\quad \bar r_v = \frac{1}{|\mathbb I_{u,v}|}\sum_{j\in \mathbb I_{u,v}}r_{v,j}\\ \sigma_u = \sqrt{\sum_{j\in \mathbb I_{u,v}}(r_{u,j}-\bar r_u)^2},\quad \sigma_v = \sqrt{\sum_{j\in \mathbb I_{u,v}}(r_{v,j}-\bar r_v)^2}\\ \text{cov}(u,v) = \sum_{j\in \mathbb I_{u,v}}(r_{u,j}-\bar r_u)(r_{v,j}-\bar r_v)$$

   则用户 $u$ 和 $v$ 的兴趣相似性由二者评分集合的相关系数correlation coefficient定义为：

   $$s_{u,v} = \frac{\text{cov}(u,v)}{\sigma_u\sigma_v}$$

3. 当预测用户 $u$ 在未阅读文章 $j^*$ 上的评分时，我们首先找出在 $j^*$ 上存在评分的用户集合 $\mathbb U_{j^*}$：

   $$\mathbb U_{j^*} = \{i\mid r_{i,j^*}\gt 0\}$$

   然后我们基于用户 $u$ 和集合 $\mathbb U$ 中用户的相似性来预测：

   $$r_{u,j^*} = \bar r_u+\sum_{v\in \mathbb U_{j^*}}s_{u,v} \times (r_{v,j^*} - \bar r_v)$$

   评分 $r_{v,j^*}$ 不仅受到用户 $v$ 对文章 $j^*$ 的偏好的影响，还受到用户 $v$ 整体打分的影响。如，有的用户倾向于都打高分，有的用户倾向于都打低分。因此这里通过 $(r_{v,j^*} - \bar r_v)$ 来剔除整体性偏好的影响，得到文章 $j^*$ 的偏好。

三、ItemBased CF[2001]

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

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

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

     此外，现有算法对于拥有大量历史行为的单个用户individual user 也存在性能问题。例如，某些用户可能在成千上万个item 上有过行为，那么这批用户会拖慢每秒可以搜索的相似用户的数量（因为计算用户之间的相似度的计算复杂度为 $O(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 推荐算法（一类新的推荐算法）能够在多大程度上解决这些问题。

3.1 模型

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

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

   • 预测：预测用户 $u_a$ 对于item $i_j\notin \mathcal I_{u_a}$ 的评分 $P_{a,j}$ 。
   • 推荐：为用户 $u_a$ 推荐他/她可能最喜欢的由 $N$ 个 item组成的列表 $\mathcal I_r\sub \mathcal I$ 。注意，推荐列表必须位于目标用户尚未购买的 item 上，即 $\mathcal I_r\cap\mathcal I_{u_a} = \Phi$ 。这被称作 Top-N 推荐。

   下图给出了协同过滤任务的示意图。CF 算法将整个 $m\times n$ 个user-item 数据表示为一个评分矩阵 $\mathbf R$ ，矩阵中的每一个元素 $r_{i,j}$ 表示第 $i$ 个user 在第 $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$ 的概率来工作，并由此计算评分的条件概率。
     • 基于规则的方法应用关联规则挖掘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 相关性。接下来我们将详细分析我们的方法。

3.1.2 Item-Based CF

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

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

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

   

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

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

     $$\text{sim}(i,j) = \cos(\mathbf{\vec r}_{\cdot,i},\mathbf{\vec 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}$ 为用户 $u$ 在 item $i$ 上的评分。我们只考虑 $\mathcal U_{i,j}$ 。

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

     $$\text{sim}(i,j) = \frac{\sum_{u\in \mathcal U_{i,j}}(r_{u,i}-\bar r_i)(r_{u,j} - \bar r_j)}{\sqrt{\sum_{u\in \mathcal U_{i,j}}(r_{u,i} - \bar r_i)^2}\sqrt{\sum_{u\in \mathcal U_{i,j}}(r_{u,j}-\bar r_j)^2}}$$

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

     如果令 $\mathbf{\vec r}^*_{\cdot,i} = \mathbf{\vec r}_{\cdot,i} - \bar r_i$ ，则上式等价于：$\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}-\bar r_u)(r_{u,j} - \bar r_u)}{\sqrt{\sum_{u\in \mathcal U_{i,j}}(r_{u,i} - \bar r_u)^2}\sqrt{\sum_{u\in \mathcal U_{i,j}}(r_{u,j}-\bar r_u)^2}}$$

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

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

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

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

     使用下图中的概念，我们可以将预测 $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$ 对相似 item 的评分。加权的权重进行了归一化，从而确保预测打分在预定范围内。

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

     

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

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

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

     $$\mathbf{\vec r}_{\cdot,j}^\prime = \alpha_{i,j} \mathbf{\vec r}_{\cdot,i} + \beta_{i,j}$$

     然后根据 $\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}$ 。最终有：

     $$P_{u,i} = \frac{\sum_{j\in \text{all similar items}} s_{i,j}\times r^\prime_{u,j}}{\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$ 个 item 需要 $O(n^2)$ 的空间。事实上对于任何一个目标item，我们只需要一小部分最相似的 item 来预测，这使得我们找到了一种替代的 mode-based 方案。因此对于每个 item，我们仅计算 $k$ 个最相似的 item，其中 $k\ll n$ 。我们称 $k$ 为模型大小。

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

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

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

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

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

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

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

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

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

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

3.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}$ 。

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

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

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

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

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

     平均绝对误差 MAE 是其中应用广泛的指标。对每个真实打分和预测打分pair 对 $<p_i,q_i>$ ，平均绝对误差为 $|p_i-q_i|$ 。考虑所有的 $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$ 、训练集拆分比例 $x$ 、不同的相似度度量。

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

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

     

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

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

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

     

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

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

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

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

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

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

     

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

   可以看到：

   • 简单加权和的 Item-Based CF 在所有 $x$ （邻域大小为30）、以及所有邻域尺寸（ $x=0.8$ ）上的表现都最好。例如在 $x=0.5$ （邻域大小为 30）时，User-Based CF 的测试 MAE = 0.755，而简单加权和 Item-Based CF 的测试 MAE = 0.749 ；而在邻域大小为 60 （$x=0.8$） 时，User-Based CF 的测试 MAE = 0.732，而简单加权和 Item-Based CF 的测试 MAE = 0.726 。
   • 回归加权和的Item-Based CF 的表现比较有趣：它在非常小的 $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$ 的敏感性，然后研究了模型大小对响应时间和吞吐量的影响。

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

   可以看到：

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

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

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

     

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

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

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

    

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

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

    

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

    • 首先， Item-Based CF 比使用 User-Based CF 提供更好的预测质量。预测质量的提高在不同邻域大小 $l$ 和训练集比例 $x$ 上是一致的，但是改进并不显著。
    • 其次，item 邻域是相当静态的，可以预计算，这会导致非常高的在线性能。
    • 此外，model-based 方法可以只保留一小部分 item 并产生相当好的预估质量。我们的实验结果支持这一说法。因此， Item-Based CF 能够解决电商推荐系统中的两个最重要的挑战：预测质量和预测性能。

四、Amazon I-2-I CF[2003]

1. 推荐算法以其在电商网站上的使用而闻名，这些算法使用有关用户兴趣的输入来生成推荐 item 列表。许多应用程序仅使用用户购买/评分的 item 来表示他们的兴趣，但是也可以使用其它属性，如浏览过的 item、人口统计数据 demographic data 、主题兴趣、最喜欢的艺术家等。在 Amazon.com，我们使用推荐算法为每位用户个性化在线商城 online store 。商城根据用户兴趣发生了根本性的变化：向软件工程师展示编程书籍、向新妈妈展示婴儿玩具。结果，点击率 click-through rate: CTR 和转化率 conversion rate: CVR （它们是 web-based 广告和 email 广告的效果指标） 大大超过了 untargeted 内容（如 banner 广告和热门列表）的点击率和转化率。

   电商推荐算法通常在具有挑战性的环境中运行。如：

   • 大型零售商可能有海量数据，如数千万用户、数百万的 item 。
   • 许多应用程序要求在不超过半秒的时间内实时返回结果集合，同时仍然能够产生高质量的推荐。
   • 新用户的信息通常极其有限，仅仅只有极少数的购买/评分记录。
   • 老用户的信息通常较大大，可能具有数以千计的购买/评分记录。
   • 用户数据易变：每次交互都提供有价值的用户数据，算法必须立即响应新信息。

   解决推荐问题的常用方法有三种：传统的协同过滤traditional collaborative filtering 、聚类模型cluster model、search-based 方法。在论文 《Amazon.com Recommendations: Item-to-Item Collaborative Filtering》 中，我们提出了item-to-item collaborative filtering ，并与这些方法进行比较。与传统的协同过滤不同，我们的算法的在线计算与用户数量、item 数量无关。我们的算法实时生成推荐，可以扩展到海量数据集，并生成高质量的推荐。

4.1 三种推荐方法

1. 大多数推荐算法首先找到目标用户历史购买/评分 item 有重叠的一组用户（称作相似用户），然后算法聚合来自这些相似用户的历史购买/评分 item、剔除目标用户已购买/评分过的 item、并将剩余的 item 推荐给目标用户。这些算法的两个流行版本是协同过滤和聚类模型 cluster model 。

   其它的一些方法，包括 search-based 方法以及我们的 item-to-item 协同过滤方法，专注于寻找相似的 item 而不是相似的用户。对于用户购买/评分过的每个 item，这些方法都尝试找到相似的 item，然后聚合相似的 item 并进行推荐。

2. 传统 Collaborative Filtering: CF：传统的协同过滤算法将用户表示为一个 $N$ 维 item 空间的向量，其中 $N$ 为 item 数量。向量的分量对于购买过的或者正面评价的 item 是正数、对于负面评价的 item 是负数。为了打压最热门的 item，该算法通常将向量分量乘以逆频率inverse frequency （购买/评价该 item 的用户数量的倒数），从而使得冷门的 item 更具相关性。对于几乎所有用户来说，这个向量都非常稀疏。

   该算法根据目标用户最相似的几个用户生成推荐。它可以通过多种方式衡量两个用户 $A$ 和 $B$ 的相似度。一种常用的方法是余弦相似度：

   $$\text{sim}(A,B) = \cos\left(\mathbf{\vec A},\mathbf{\vec B}\right) = \frac{\mathbf{\vec A}\cdot \mathbf{\vec B}}{\|\mathbf{\vec A}\|\times \|\mathbf{\vec B}\|}$$

   一旦找到目标用户的相似用户，该算法使用各种方法从相似用户的 item 中选择推荐。一种常见的技术是根据相似用户购买的数量对每个 item 进行排序。

   为单个目标用户使用协同过滤生成推荐的计算成本很高。在最坏的情况下它是 $O(MN)$，其中 $M$ 是用户数量、$N$ 是 item 数量，因为它需要检查 $M$ 个用户、每个用户最多 $N$ 个 item 。然而，由于平均而言用户向量极其稀疏，因此算法的性能往往更接近 $O(M+N)$ 。

   • 扫描每个用户大约是 $O(M)$ 而不是 $O(MN)$，因为几乎所有用户向量都包含稀疏的 item（而不是 $O(N)$）。
   • 但是有些用户已经购买/评价了很大一部分 item，所以需要 $O(N)$ 处理时间。

   因此，该算法的最终性能约为 $O(M+N)$ 。即便如此，对于非常大的数据集，例如 1000 万或者更多的用户、100 万或者更多的 item ， 算法会遇到严重的性能和可扩展性问题。

   这里评估的是单个用户的推荐性能，如果是所有用户那么算法性能为 $O(M\times (M+N))$ 。

   可以通过减少数据规模来解决可扩展性问题。我们可以通过随机采样用户、或者丢弃购买量少的用户从而降低 $M$ ，也可以通过丢弃非常热门或者非常冷门的 item 从而降低 $N$ 。还可以通过基于 item 类别或者主题分类划分 item 空间，从而减少一定比例的 item 数量。诸如聚类或者 PCA 之类的降维技术可以将 $M$ 或者 $N$ 减少一个大的因子 factor 。

   不幸的是，所有这些降低数据规模的方法也以不同的方式降低了推荐质量。

   • 首先，如果算法仅检查了一小部分用户，那么所选择的相似用户与目标用户的相似度将有所下降（相比在全量用户中选择相似用户）。

     因为最相似的用户可能不在我们检查的一小部分用户中。

   • 其次，item 空间的划分使得推荐限制在特定类别或者主题的区域。

   • 第三，如果算法丢弃最热门或者最冷门的 item，那么这些 item 将永远不会被推荐到，只购买这些 item 的用户也将不会得到推荐。

   • 第四，应用于 item 空间的降维技术通过消除低频 item 往往也具有相同的效果（丢弃冷门 item ）。

   • 第五，应用于用户空间的降维技术有效地将相似的用户分组，正如我们前面所描述的（仅检查了一小部分用户），这种聚类也将降低推荐质量。

3. 聚类模型 Cluster Model ：为了找到与目标用户相似的用户，聚类模型将用户集合划分为许多部分 segment，并将任务视为分类问题。该算法的目标是将用户分配到包含最相似用户的 segment 。然后，它使用 segment 中用户的购买/评级来生成推荐。

   这些 segment 通常是使用聚类或其它无监督学习算法创建的，尽管有一些应用程序使用人工确定的 segment 。使用一种相似性度量，聚类算法将最相似的用户分组在一起从而形成 segment 。由于对大型数据集进行最佳聚类是不切实际的，因此大多数应用程序使用各种形式的贪心聚类生成。这些算法通常从一组初始 segment 集合开始，每个 segment 通常包含一个随机选择的用户。然后，算法反复将用户与现有的 segment 匹配，通常会根据规则创建新的 segment 或者合并现有的 segment 。对于非常大的数据集，尤其是那些高维特征的数据集，采样或降维也是必要的。

   一旦生成了 segment 之后，算法会计算目标用户与每个 segment 的相似度，然后选择相似度最高的 segment 并相应地对目标用户进行分类。一些算法将目标用户划分到多个 segment，并描述目标用户与每个 segment 的关系强度。

   cluster model 比协同过滤具有更好的在线可扩展性和性能，因为它们将目标用户与可控数量的 segment、而不是整个用户集合相比较。复杂且昂贵的聚类计算是离线运行的。

   但是这种方法推荐质量较差。cluster model 将众多用户分组到一个 segment 中，将一个目标用户与一个 segment 相匹配，然后将 segment 中所有用户都考虑为目标用户相似的用户，从而进行推荐。因为 cluster model 找到的相似用户并不是最相似的用户，因此它们产生的推荐不太相关。可以通过使用大量的细粒度 segment 来提高推荐质量，但是在线的 user-segment 分类将变得几乎与使用协同过滤查找相似用户一样昂贵。

4. 基于搜索search-based的方法：基于搜索或者基于内容的方法将推荐问题视为对相关 item 的搜索。给定用户购买/评分的 item，该算法构建一个搜索 query，从而查找同一作者、艺术家、导演、或者相似关键字或主题的其它热门 item。例如，如果用户购买教父 DVD 合集，那么系统可能会推荐其它犯罪剧、Marlon Brando 主演的其它作品、或者 Francis Ford Coppola 导演的其它电影。

   如果用户很少购买/评分，基于搜索的推荐算法的可扩展性和表现都很好。然而，对于购买量数以千计的用户而言，基于所有 item 进行 query 是不切实际的。该算法必须使用数据的子集或者 summary，从而降低质量。

   无论是哪种情况（用户购买量太少或者太多），推荐质量都相对较差。这些推荐通常要么太宽泛（例如，最畅销的戏剧 DVD 作品）、要么太狭隘（例如，同一作者的所有书籍）。推荐系统应该帮助用户找到和发现新的、相关的、和有趣的 item 。同一作者或者同一主题中的热门 item 无法实现该目标。

4.2 Item-to-Item CF

1. Amazon.com 在许多电子邮件营销 campaign 和大多数网站页面（包括高访问量的 Amazon.com 主页）中使用推荐作为一个定向营销工具 targeted marketing tool 。点击 Your Recommendations 链接会将用户引导至一个区域，在这个区域中用户可以根据item 类别、主题类型来过滤推荐，并且对推荐的 item 进行评分、对用户历史购买的item 进行评分，以及了解推荐item 的推荐原因。如下图所示。

   

   下图为我们的购物车推荐，它根据用户购物车中的item为用户提供推荐建议。它该功能类似于超市收银台中的冲动商品 impulse item，但是我们的冲动商品针对每个用户个性化定制。

   

   Amazon.com 广泛使用推荐算法来根据每个用户的兴趣个性化其网站。由于现有的推荐算法无法扩展到 Amazon.com 的数千万用户和数百万 item，因此我们开发了自己的算法，即item-to-item 协同过滤 。我们的算法可以扩展到海量数据并实时生成高质量的推荐。

   即使现代的深度神经网络模型在预测用户个性化兴趣方面的能力远远超越了传统协同过滤模型，但是传统协同过滤模型在可解释性方面更好，这有助于引导用户接受和信任推荐系统，从而得到更好的转化。

2. 工作原理：item-to-item 协同过滤不是将用户与相似用户进行匹配match，而是将用户购买/评分的每个item 与相似 item 进行匹配，然后将这些相似 item 组合到推荐列表中。

   为了确定目标 item 的最相似匹配，该算法通过查找用户共同购买的 item 来构建 similar-items table 。我们可以通过迭代所有 item，并为每对 item 计算相似度来构建 item-to-item 矩阵。然而，许多 item pair 没有共同的用户，因此该方法在计算时间和内存占用方面效率低下。以下迭代算法通过计算单个 item 与所有相关 item 之间的相似度，从而提供了更好的方法：

   xxxxxxxxxx
   4
   1
   遍历 item 集合，对集合中的每个 item i1 :
   2
       遍历购买/评分 i1 的用户集合，对集合中的每个用户 u:
   3
           遍历用户 u 购买/评分的 item 集合，对集合中的每个 item i2 ，记录 pair (i1,i2)
   4
       对每个 pair (i1,i2)，计算它们之间的相似度
   

   可以通过多种方式计算两个 item 之间的相似度，但是一种最常用的方法是使用我们之前描述的余弦相似度，其中每个向量对应于一个 item 而不是一个用户，向量的 $M$ 维对应于购买/评分了该 item 的用户。

   similar-items table 的这种离线计算非常耗时，最坏情况为 $O(N^2M)$ 。然而，在实践中它更接近 $O(NM)$ ，因为大多数用户的购买量很少。对购买热门 item 的用户进行采样（热门 item 列向量的元素进行采样）会进一步降低运行时间，而推荐质量几乎没有降低。

   给定一个 similar-items table ，该算法找到与目标用户的每个购买/评分相似的 item，聚合这些 item，然后推荐最热门或最相关的 item。这种计算非常快，仅取决于用户购买/评分的 item 数量。

3. 可扩展性：Amazon.com 拥有超过 2900 万用户和数百万个 item。几乎所有现有算法都是在小数据集上进行评估的。例如 MovieLens 数据集包含 35000 个用户和 3000 个 item，而 EachMovie 数据集包含 4000 个用户和 1600 个 item。对于非常大的数据集，可扩展的推荐算法必须离线执行最昂贵的计算。如前所述，现有方法存在不足：

   • 传统的协同过滤很少或者从不进行离线计算，其在线计算会随着用户数量和 item 数量而增加。该算法在大型数据集上是不切实际的，除非它使用降维、采样、或者划分 partitioning，而所有这些操作都会降低推荐质量。
   • cluster model 可以离线执行大部分计算，但是推荐质量相对较差。为了改进它，可以增加 segment 的数量，但是这又会使得 user-segment 分类变得代价昂贵。
   • search-based model 离线构建关键字、类别、作者的索引，但是无法提供有趣的、个性化的item 推荐。对于具有大量购买/评分的用户，该方法的可扩展性也很差。

   item-to-item 协同过滤的可扩展性和性能的关键在于它离线创建昂贵的 similar-items table 。该算法的在线部分（为用户的购买/评分 item 查找相似的 item）独立于 item 数量和用户数量，仅取决于用户购买/评分了多少个 item。因此，即使对于非常大的数据集，该算法也很快。由于该算法推荐高度相关的相似 item，所以推荐质量非常好。与传统的协同过滤不同，该算法在用户数据有限的情况下也表现良好，甚至可以基于少到两三个 item 来生成高质量的推荐。

五、Slope One Rating-Based CF[2005]

1. 基于评分的协同过滤RatingBased CF 方法是从其它用户的评分中预估目标用户如何对目标商品进行评分的过程。一个理想的 RatingBased CF 需要满足以下条件：

   • 易于实现和维度：算法的可解释性强，并且易于实现和维护。
   • 即时更新：添加新的评分之后，模型能够立即更新预测。
   • 高性能：在线推荐速度应该非常快速，这可能需要以内存为代价。
   • 数据需求低：能够为评分数量较少的目标用户提供高质量的推荐。
   • 合理的推荐准确性：和效果最好的推荐相比具有可比的推荐质量，其中推荐质量的小幅提升并不值得牺牲简单性 simplicity 和可扩展性 scalability 。

   为此，论文 《Slope One Predictors for Online Rating-Based Collaborative Filtering》 提出的 Slope One 算法满足上述五个目标。论文的目标并不是比较各种 CF 算法的准确性，而是证明 Slop One 算法可以同时满足这五个目标。相比之下，其它的一些 CF 方法追求其中的一部分目标而牺牲了另外一些目标。

   Slope One 算法的基本思想是：不同item 之间的流行度差异 popularity differential 。我们以 pair 对的方式来决定item $j$ 比item $i$ 要好多少，从而计算流行度差异。一种简单的计算方式是：用item $j$ 的评分减去item $i$ 的评分。反之，如果已知item $i$ 的评分，以及 $j$ 和 $i$ 的流行度差异，那么item $j$ 的评分就可以计算到。

   考虑下图中的两个用户 $A$ 和 $B$ 以及item $I$ 和 $J$ 。用户 $A$ 给item $I$ 评分 1 分、用户 $B$ 给item $I$ 评分 2分、用户 $A$ 给item $J$ 评分 1.5 分。我们观察到item $J$ 比item $I$ 的评分更高，差异在 1.5 - 1 = 0.5 分，因此我们预计用户 $B$ 将给item $J$ 的评分为 2 + 0.5 = 2.5 分。我们称 $B$ 为目标用户，item $J$ 为目标商品。

   

   对于每个未知的评分，在训练集中存在大量的这种差异，则我们可以取这些差异的均值。Slop One 算法提供了三种方式来选择差异，并最终得到单个预测结果。Slope One CF 的预测形式为 $f(x) = x + b$ ，其中 $b$ 为平均的流行度差异。

   论文的主要贡献是提出了一个 Slope One CF 算法，并证明它和 memory-based 算法相比具有几乎相同的准确性，同时更适合 CF 任务。

2. 相关工作：

   • MemoryBased CF 使用 u-2-u 相似性来执行预测，其中相似函数的选择决定了推荐的质量。其缺点包括：

     • 可扩展性scalability ：MemoryBased CF 依赖于的 u-2-u 相似性计算复杂度太高，而这些计算无法通过离线预计算。
     • 数据稀疏的敏感性 sensitivity ：为满足推荐的高质量，MemoryBased CF 要求最低数量的用户（如至少 100 个用户)、最低数量的评分（如至少 20 个评分）。

     本文中我们将 Slope One CF 和众所周知的 MemoryBased CF 算法 Pearson 进行对比。

   • 也有一些 ModelBased CF，如基于线性代数的方法（如SVD、PCA）、基于机器学习的方法（如贝叶斯方法）、基于神经网络的方法、基于聚类的方法。与MemoryBased CF 相比，ModelBased CF 在线计算的性能很高，但是它们具有昂贵的离线学习阶段或者离线更新阶段。当在线速度至关重要时，ModelBased CF 算法相比 MemoryBased CF 更可取。

   • 我们的 Slope One CF 的形式为：$f(x) = x + b$，其中 $b$ 为常数、$x$ 表示评分变量，因此该方法叫做 slope one 。对于任何 item pair 对，我们试图找到从一个 item 评分中预测另一个 item 评分的最佳函数 $f$ ，不同 item pair 的函数 $f$ 可能不同。

     • 在 《Item-based collaborative filtering recommender algorithms》 中，作者考虑了 item pair 之间的相关性，然后将用户评分的加权均值作为评分变量，其中权重为相关系数。

       在该论文的简单版本中，预估形式为 $f(x) = x$；在该论文的回归版本中，预估形式为 $f(x) = ax+b$ 。

     • 在论文 《A regression-based approach for scaling-up personalized recommender systems in e-commerce》 中，作者也使用了 $f(x) = ax+b$ 形式的预估。

     这两篇论文工作的一个自然扩展是考虑 $f(x) = ax^2 + b x+c$ 形式的预估。相反，本文中我们使用形式为 $f(x) = x + b$ 的预估。在 《A regression-based approach for scaling-up personalized recommender systems in e-commerce》 中观察到，即使他们使用基于回归的 $f(x) = ax+b$ 算法也没有导致相对 MemoryBased CF 算法的较大改进。因此，证明 $f(x) = x +b$ 形式的预估可以与 MemoryBased CF 算法竞争，这是本文的一个重要结果。

5.1 模型

1. 给定用户 $u$ ，定义他/她的评分 array 记作：

   $$\mathbf{\vec r}_u = (r_{u,1},r_{u,2},\cdots,r_{u,n})^T$$

   其中第 $i$ 个元素 $r_{u,i}$ 对应于item $i$ 的评分。由于存在大量的未评分item ，因此这个向量是不全的 incomplete 。

   定义用户 $u$ 评分的所有item 为 $\mathbb I_u$，用户 $u$ 的平均打分为 $\bar r_u$ ：

   $$\mathbb I_u = \{i\mid r_{u,i} \gt 0\}, \quad \bar r_u = \frac{1}{|\mathbb I_u|}\sum_{i\in \mathbb I_u}r_{u,i}$$

   定义训练集的所有评分 array 为 $\mathbb X$ ：$\mathbb X = \{\mathbf{\vec r}_u\mid u\in \mathbb U\}$ ，其中 $\mathbb U$ 为所有用户。

   定义 $\mathbb U_i$ 为包含item $i$ 的用户集合 ：$\mathbb U_{i} = \{u\mid u\in \mathbb U \;\text{and}\; r_{u,i} \gt 0\}$ 。定义同时包含item $i,j$ 的用户集合为：$\mathbb U_{i,j} = \{u\mid u\in \mathbb U \;\text{and}\; r_{u,i} \gt 0\;\text{and} \; r_{u,j}\gt 0\}$ 。定义用户 $u,v$ 共同评分的item 集合为： $\mathbb I_{ u,v}=\{i\mid i\in \mathbb I\;\text{and}\; r_{u,i}\gt 0\;\text{and} \; r_{v,i}\gt 0\}$ 。

   定义预测 $\mathbf{\vec p}_u = (p_{u,1},\cdots,p_{u,n})^T$ ，其中每个元素代表一个预测结果。

2. RatingBased CF 在线预测时， 首先提供一个评分 array （称作 query array）， 它包含用户的所有评分item ；模型返回一个预测array（称作 response array），其中包含用户尚未评分的item 及其预估的评分。

5.1.1 baseline

1. 最简单的 baseline 为 PER USER AVERAGE：

   $$p_{u,i} = \bar r_u,\quad i\notin \mathbb I_u$$

   即：预测用户的所有未评分item 的评分为该用户的评分均值。

2. 针对PER USER AVERAGE 的一种改进方式为 BIAS FROM MEAN（也被称作 NON PERSONNALIZED），其预测结果为：

   $$p_{u,i} = \bar r_u + \frac{1}{|\mathbb U_i|}\sum_{v \in \mathbb U_i}(r_{v,i} - \bar r_v),\quad i\notin \mathbb I_u$$

   它考虑了用户 $u$ 的评分均值，以及所有其它用户在该item 上的评分差异（其它用户在该 item 上的评分减去用户平均均值）。

3. 基于MemoryBased CF 的一个经典实现是 PEARSON 方案：

   $$p_{u,i} = \bar r_u + \frac{\sum_{v \in\mathbb U_i} \gamma(u,v)(r_{v,i} - \bar r_v)}{\sum_{v \in\mathbb U_i} |\gamma(u,v)|},\quad i\notin \mathbb I_u$$

   它在 BIAS FROM MEAN 的基础上考虑了用户 $u,v$ 之间的相似性。其中 $\gamma$ 为Pearson 相关系数，它刻画了用户之间的相似性：

   $$\text{corr}(u,v) = \frac{\sum_{i\in\mathbb I_{u,v}}(r_{u,i}- \bar r_u)(r_{v,i}- \bar r_v)}{\sqrt{\sum_{i\in \mathbb I_ {u,v}}(r_{u,i}- \bar r_u)^2\sum_{i\in\mathbb I_{u,v}}(r_{v,i} - \bar r_v)^2}}\\ \gamma(u,v) = \text{corr}(u,v)|\text{corr}(u,v)|^{\rho-1}$$

   其中 $\rho=2.5$ 为 Case Amplification 系数，它降低了数据中的噪音。

   • 如果相关系数很高，如 corr = 0.9，则经过 Case Amplification 之后它仍然很高：$0.9^{2.5} \simeq 0.8$ 。
   • 如果相关系数很低，如 corr = 0.1，则经过 Case Amplification 之后它可以忽略不计： $0.1^{2.5}\simeq 0.003$ 。

   尽管存在更准确的方法，但是 PEARSON 相关系数以及 Case Amplification 一起已经能够提供相当好的推荐质量。

4. 采用 adjusted cosine 相似度的 ItemBased CF ：给定item $i$ 和 $j$ ，定义相似度为：

   $$\text{sim}(i,j) = \frac{\sum_{u\in \mathbb U_{i,j}}(r_{u,i}-\bar r_u)(r_{u,j}-\bar r_u)}{\sum_{u\in \mathbb U_{i,j}}(r_{u,i}-\bar r_u)^2\sum_{u\in \mathbb U_{i,j}}(r_{u,j}-\bar r_u)^2}$$

   使用基于回归Regression 的预测为：

   $$p_{u,i} = \sum_{j\in \mathbb I_u} w_{i,j} (\alpha_{i,j}r_{u,j} + \beta_{i,j}),\quad i\notin \mathbb I_u\\ w_{i,j} = \frac{|\text{sim}(i,j)|}{\sum_{j^\prime\in \mathbb I_u} |\text{sim}(i,j^\prime)|}$$

   其中 $\alpha_{i,j},\beta_{i,j}$ 为回归系数，它根据最小化目标来求得：

   $$\arg\min_{\alpha_{i,j},\beta_{i,j}} \sum_{u\in \mathbb U_{i,j}} (\alpha_{i,j} r_{u,j} +\beta_{i,j} - r_{u,i})^2$$

5.1.2 Slope One

1. slope one 方法同时考虑了来自相同 item 的其它用户的评分（就像ItemBased CF ）、来自相同用户的其它 item 的评分（就像 MemoryBased CF），除此之外slope one 方法还依赖于既不是相同 item 、也不是相同用户的那些评分。因为这些评分数据都有助于我们进行预测。

   slope one 方法的大部分优势都来自于 ItemBased CF、MemoryBased CF 未考虑的数据。

2. 给定用户 $u,v$ ，我们寻找最佳的预测器 predictor 来从 $u$ 的评分中预测 $v$ 的评分。

   slope one 方法选择的 predictor 为斜率为1 的线性函数 $f(x) = x + b$ ，这就是名字 slope one 的由来。 具体而言，我们需要拟合方程：

   $$r_{v,i}^\prime = r_{u,i} + b ,\quad i\in \mathbb I_{u,v}$$

   我们通过最小化残差：

   $$\arg\min_b \sum_{i\in \mathbb I_{u,v}}(r_{v,i} - r^\prime_{v,i})^2$$

   通过残差的偏导数为0，我们得到：

   $$b = \frac{\sum_{i\in \mathbb I_{u,v}}(r_{v,i} - r_{u,i})}{|\mathbb I_{u,v}|}$$

   因此 $b$ 是用户 $u$ 和 $v$ 的评分差异的均值。

3. 类似地，我们可以通过利用item $i$ 的评分来预测item $j$ 的评分。同样的推导过程，我们有：

   $$b = \frac{\sum_{u\in \mathbb U_{i,j}}(r_{u,j} - r_{u,i})}{|\mathbb U_{i,j}|}$$

   给定训练集 $\mathbb X$，以及任意两个item $i,j$ ，我们定义item $i$ 到item $j$ 的平均偏移为：

   $$\text{dev}_{j,i} =\frac{1}{|\mathbb U_{i,j}|} \sum_{u\in \mathbb U_{i,j}} (r_{u,j} - r_{u,i})$$

   因此在给定 $r_{u,i}$ 的条件下，$r_{u,j}$ 的预测值为：

   $$r_{u,j}^\prime = \text{dev}_{j,i} + r_{u,i}$$

   考虑所有这样的 $r_{u,i}$，因此用户 $u$ 在 item $j$ 上的 predictor 定义为：

   $$p_{u,j} = \frac{1}{|\mathbb S_{u,j}|} \sum_{i\in \mathbb S_{u,j} } (\text{dev}_{j,i} + r_{u,i})$$

   其中 $\mathbb S_{u,j}=\{i\mid i\in \mathbb I_u\;\text{and}\;i\ne j\;\text{and}\; \mathbb U_{i,j} \ne \Phi\}$ ，即：用户 $u$ 同时评分的、且与 $j$ 有共同评分用户的item 的集合。

   当数据足够稠密，即几乎所有item pair 对之间都有评分时，有：$\mathbb S_{u,j} = \mathbb I_u$ 。考虑到：

   $$\frac{1}{|\mathbb S_{u,j}|}\sum_{i\in \mathbb S_{u,j}}r_{u,i}\simeq \frac{1}{|\mathbb I_{u}|}\sum_{i\in \mathbb I_{u}}r_{u,i} = \bar r_u$$

   因此有：

   $$p_{u,j} = \bar r_u + \frac {1}{|\mathbb I_u|}\sum_{i\in \mathbb I_u}\text{dev}_{j,i}$$

   可以看到：slope one 方法不依赖于用户对具体item 的评分，而依赖于用户的平均评分，以及用户对哪些item 进行评分。

4. slop one 方法的关键数据是item 之间的偏移矩阵：

   $$\mathbf E = \begin{bmatrix} 0&\text{dev}_{1,2}& \text{dev}_{1,3}& \cdots & \text{dev}_{1,n}\\ \text{dev}_{2,1}&0& \text{dev}_{2,3}& \cdots & \text{dev}_{2,n}\\ \vdots&\vdots&\vdots& \ddots & \vdots\\ \text{dev}_{n,1}&\text{dev}_{n,2}& \text{dev}_{n,3}& \cdots & 0 \end{bmatrix}$$

   其中 $E_{i,j} = - E_{j,i}$ 。

   偏移矩阵 $\mathbf E$ 可以预计算，并且当有新数据进来时实时更新。

5. ItemBased CF 中，我们需要根据相似商品的评分来给出结果。

   • 朴素版本的 predictor 可以视作 $f(x) = x$ 的加权聚合结果：

     $$p_{u,i} = \sum_{j\in \mathbb I_{u,i}}w_{i,j} \times r_{u,j}\\ w_{i,j} = \frac{s_{i,j}}{\sum_{j^\prime\in \mathbb I_{u,i}}s_{i,j^\prime}}$$

   • 基于回归的predictor 可以视为 $f(x) = \alpha x +\beta$ 的加权聚合结果：

     $$p_{u,i} = \sum_{j\in \mathbb I_{u,i}}w_{i,j} \times (\alpha_{i,j}\times r_{u,j}+\beta_{i,j}) \\ w_{i,j} = \frac{s_{i,j}}{\sum_{j^\prime\in \mathbb I_{u,i}}s_{i,j^\prime}}$$

   slope one 方法采用 $f(x) = x +b$ 的聚合结果，但是没有使用相似性进行加权：

   $$p_{u,i} = \bar r_u + \frac {1}{|\mathbb I_u|}\sum_{j\in \mathbb I_u}\text{dev}_{i,j}$$

   事实上可以进一步的扩展到 $f(x) = ax^2 + b x +c$ 的形式。

6. Weighted Slope One：slope one 方法的一个缺点是未考虑已经评分的数量。

   假设给定用户 A 对item J, K 的评分，我们需要预测用户 A 对item L 的评分。如果有 2000 个用户同时对item J,L 评分、有 20 个用户对item K,L 评分，则商品 J 相比商品 K 更适合作为商品 L 的 predictor。因为 $\text{dev}_{L,J}$ 比 $\text{dev}_{L,K}$ 更为置信。

   因此定义 Weighted Slope One 预测为：

   $$p_{u,j} = \frac{\sum_{i\in \mathbb S_{u,j} }(\text{dev}_{j,i} + r_{u,i})\times |\mathbb U_{i,j}|}{\sum_{i\in \mathbb S_{u,j} } |\mathbb U_{i,j}|}$$

   .

5.1.3 Bi-Polar Slope One

1. 给定一个0 到 10 的评分等级表，我们认为评分超过 5 分表示用户喜欢的item ，评分低于 5 分表示用户不喜欢的item 。如果用户的评分是均匀分布的，则阈值设置为 5 分没有问题。但是通常用户的评分不是均匀分布的，如 EachMovie 数据集中超过 70% 的评分都超过 5 分。

   考虑到用户评分的分布多种多样，如均匀分布、倾向于乐观的分布(均值超过5 分)、倾向于悲观的分布(均值低于 5 分)、双峰分布（同时偏向于两个极端）。为了自适应这些分布，我们不再设置固定的阈值，而是使用自适应的阈值：将喜欢/不喜欢阈值设定为用户评分的均值。对于一个用户而言：

   • 评分低于该用户所有评分均值的item 被视为用户不喜欢的item 。
   • 评分高于该用户所有评分均值的item 被视为用户喜欢的item 。

   这种方式可以确保我们能够为每个用户提供合理数量的喜欢/不喜欢item 。

2. Weighted Slope One 倾向于更加高频的评分模式，Bi-Polar Slope One 倾向于某种偏好的评分模式。

   Bi-Polar Slope One 方法将预测拆分为两个部分：

   • 从用户喜欢的item中使用 Weighted Slope One 得出一个预测。
   • 从用户不喜欢的item中使用 Weighted Slope One 得出另一个预测。

   然后合并这两部分的预测，即可得到 Bi-Polar Slope One 的预测。

3. Bi-Polar Slope One 方法从两个角度进行了改进：

   • 首先在item方面，仅考虑用户的两个喜欢item之间的评分偏差，或者两个不喜欢item之间的偏差。即对 $\mathbb S_{u,j}$ 进行限制。

     根据用户不喜欢的item去预估用户喜欢的item（或者反过来）没有意义。

   • 其次在用户方面，在计算item之间偏差时，我们仅仅考虑同时喜欢、或者同时不喜欢这两个item的用户。即对 $\text{dev}_{i,j}$ 进行限制。

   我们拆分每个用户的评分item集合为：

   $$\mathbb I_u^{like} = \{i\mid i \in \mathbb I \;\text{and}\; r_{u,i} \gt \bar r_u\}\\ \mathbb I_u^{dislike} = \{i\mid i \in \mathbb I \;\text{and}\; r_{u,i} \lt \bar r_u\}$$

   然后对于每对 `item pair 对 $(i,j)$ ，拆分它们的共同评分用户集合为：

   $$\mathbb U_{i,j}^{like} = \{u\mid i\in \mathbb I_u^{like} \;\text{and}\; j\in \mathbb I_u^{like}\}\\ \mathbb U_{i,j}^{dislike} = \{u\mid i\in \mathbb I_u^{dislike} \;\text{and}\; j\in \mathbb I_u^{dislike}\}$$

   我们计算偏差矩阵为：

   $$\text{dev}_{j,i}^{like} =\frac{1}{|\mathbb U_{i,j}^{like}|} \sum_{u\in \mathbb U_{i,j}^{like}} (r_{u,j} - r_{u,i})\\ \text{dev}_{j,i}^{dislike} =\frac{1}{|\mathbb U_{i,j}^{like}|} \sum_{u\in \mathbb U_{i,j}^{dislike}} (r_{u,j} - r_{u,i})$$

   最终我们的预测为：

   $$p_{u,j} = \frac{\sum_{i\in \mathbb S_{u,j}^{like} }(\text{dev}_{j,i}^{like} + r_{u,i})\times |\mathbb U_{i,j}^{like}|+ \sum_{i\in \mathbb S_{u,j}^{dislike} }(\text{dev}_{j,i}^{dislike} + r_{u,i})\times |\mathbb U_{i,j}^{dislike}|}{\sum_{i\in \mathbb S_{u,j}^{like} } |\mathbb U_{i,j}^{like}|+ \sum_{i\in \mathbb S_{u,j}^{dislike} } |\mathbb U_{i,j}^{dislike}|}$$

   其中 ：

   • 其中 $\mathbb S_{u,j}^{like}=\{i\mid i\in \mathbb I_u^{like}\;\text{and}\;i\ne j\;\text{and}\; \mathbb U^{like}_{i,j} \ne \Phi\}$ ，即：用户 $u$ 同时喜欢的、且与 $j$ 有共同喜欢用户的item的集合。
   • 其中 $\mathbb S_{u,j}^{dislike}=\{i\mid i\in \mathbb I_u^{dislike}\;\text{and}\;i\ne j\;\text{and}\; \mathbb U_{i,j}^{dislike} \ne \Phi\}$ ，即：用户 $u$ 同时不喜欢的、且与 $j$ 有共同不喜欢用户的item的集合。

4. Bi-Polar Slope One 将每个用户的item区分为喜欢、不喜欢，这相当于使得用户数量增加一倍。但是由于算法在计算过程中的限制（item方面的限制和用户方面的限制），这使得预测过程的计算量总体上得到降低。

   另外，由于用户数量翻倍、评分数量不变，这加剧了数据稀疏性。在数据更加稀疏的条件下Bi-Polar Slope One 还能够改善推荐质量，这似乎是违反直觉的。但是如果在预测过程中不去剔除无关的评分，其危害更大。

   Bi-Polar Slope One 无法从 “用户 A喜欢商品 K、用户 B不喜欢商品 K” 中预测任何结果，这也是符合直觉的。

5.2 实验

2. 评估指标：测试集上的预测的均方误差 MAE 。我们采用 All But One MAE。在计算 MAE 时，我们从测试集每个用户中随机隐藏一个评分，然后预估这个评分。

3. 数据集：

   • EachMovie 数据集：Compaq Research 提供的 EachMovie 数据集，评分等级从 0.0 到 1.0， 每 0.2 一个等级。
   • MovieLens 数据集：Minnesota 大学 Grouplens Research Group 提供的 Movielens 数据集，评分等级从 1 分到 5 分，每1 分一个等级。

   我们选择 5 万个用户作为训练集 $\mathbb X$ ，至少 10 万个用户作为测试集。当预测结果超出范围时，进行修正：EachMovie 预测结果超过 1.0 调整为 1.0 分， MovieLens 预测结果超过 5 调整为 5 分。

   由于 MovieLens 分值范围比 EachMovie 大 4 倍，因此 MovieLens 评估的 MAE 指标除以 4 从而得到可比的结果。

4. 实验结果如下表所示，可以看到：

   • Slope One 方法在所有 baseline 中表现最好，达到和 PEARSON 相匹配的准确率。这表明尽管 Slope One 具有理想的特点，它的准确率仍然可以得到保持。
   • 针对原始的 Slope One 的改进确实能够提高推荐的准确性。 Weighted Slope One 能够提高大约 1%， Bi-Polar Slope One 能够提高大约 3% 。

   

六、Bipartite Network Projection[2007]

1. 过去几年大量研究致力于理解复杂的网络。一类特殊的网络是二部网络 bipartite network，其中节点被分为两组 $\mathcal X,\mathcal Y$，并且只允许不同组中的节点之间存在连接，如下图 (a) 所示。许多系统自然地建模为二部网络，例如人类性别网络 human sexual network 由男性和女性组成、代谢网络 metabolic network 由化学物质和化学反应组成。有两种二部网络很重要，因为它们在社会、经济、以及信息系统中有特殊意义。

   • 一种是所谓的协同网络 collaboration network。这种网络的例子很多，包括共同撰写同一篇科学论文而联系起来的科学家、共同主演同一部电影而联系起来的演员等等。此外，协同网络的概念不一定局限于社会系统。

     尽管协同网络通常通过对参与者的 one-mode 投影来展示，但是它的完整表示是一个二部网络。

   • 另一种是所谓的意见网络 opinion network，其中用户集合user-set 中的节点和对象集合object set 中的节点相连。例如，听众和他们在音乐共享库收集的音乐建立联系、互联网用户和他们在书签网站中收集的 web url 建立联系、顾客和他们购买的书籍建立联系。

   最近，人们对分析和建模二部网络给予了很多关注。但是，为了方便直接表示一组特定节点之间的关系，通常采用 one-mode 投影来压缩二部网络。$\mathcal X$ 上的 one-mode 投影（简称 $\mathcal X$ 投影） 是指仅包含 $\mathcal X$ 节点的网络，当两个 $\mathcal X$ 节点至少存在一个共同的 $\mathcal Y$ 邻居节点时这两个 $\mathcal X$ 节点相连。下图 (b) 展示了 $\mathcal X$ 投影的结果网络、(c) 展示了 $\mathcal Y$ 投影的结果网络。

   

   最简单的方法是将二部网络投影到一个未加权的网络上，而不考虑协同collaboration 重复的频次。虽然可以从这个未加权的版本中定性地获得一些拓扑特性，但是信息的损失是显而易见的。例如，如果两位听众各自收集了 100 首以上的音乐，并且这两位听众仅共享了一首音乐，那么可以得出结论：这两位听众可能具有不同的音乐偏好。相反，如果这两位听众共享了接近 100 首音乐，那么这两位听众很可能具有非常相似的习惯。然而，在未加权的听众投影中，这两种情况具有完全相同的 graph representation 。

   由于 one-mode 投影总是比原始二部网络提供的信息更少，为了更好地反映网络的结构，必须使用二部图来量化投影图中的权重。一种直接的方法是直接通过相应 partnership 重复的次数来对边进行加权。如图 (b),(c) 所示，这个简单的规则可以获得 $\mathcal X$ 投影和 $\mathcal Y$ 投影的权重。这个加权网络比未加权网络提供更多信息，并且可以通过未加权图的标准技术进行分析，因为它的权重都是整数。然而，这种方法在定量上也是有偏的quantitatively biased 。

   Li 等人对科学协同网络进行了实证研究，并指出额外一篇合作论文的影响应该取决于两位作者之间的原始权重。例如，如果两位作者之间之前仅合作一篇论文，那么多一篇合作论文将比两位作者之前合作 100 篇论文的影响更大。通过将双曲正切函数引入简单的协同次数计数，可以考虑这种饱和效应saturation effect 。

   Newman 指出，与许多其他合作者一起出现在同一篇论文的两位作者，他们的平均相互了解程度低于作为论文唯二作者的两位作者。为了考虑这种影响，他引入了因子 $1/(n-1)$ 来削弱涉及多个参与者的合作的贡献，其中 $n$ 是参与者的数量。

   如何对边进行加权是 one-mode 投影及其使用的关键问题。然而，我们缺乏对这个问题的系统探索，迄今为止都还没有任何加权方法的坚实理论基础。

   • 例如，人们可能会问为什么使用双曲正切函数来解决饱和效应而不是其它大量潜在的候选函数的理论依据。
   • 此外，为了简单起见，加权邻接矩阵 $\mathbf W$ 总是设置为对称的，即 $w_{i,j} = w_{j,i}$ 。然而，在科学协同网络中，同一篇合作论文中不同的作者可能会分配不同的权重，可能是发表论文较少的作者给予更高的权重，亦或反之。因此，更自然的加权方法可能是非对称的。

   现有方法的另一个缺陷是：在 $\mathcal X$ 投影图中，如果 $\mathcal Y$ 顶点只有一个相连的 $\mathcal X$ 顶点，则这个连接关系会在投影过程中丢失。$\mathcal Y$ 投影图也有类似的问题，如 $x_8$ 仅仅和 $y_5$ 关联，这使得在 $\mathcal Y$ 的投影图中完全丢失了 $x_8$ 的信息。即二部网络中 degree 为 1 的边所包含的信息将在 one-mode 投影中丢失。 这种信息丢失在一些真实的意见网络中可能会很严重。例如在 user-web 网络 delicious 中，有相当一部分的 web 仅被收集一次，而相当一部分 user 仅收集了一个 web。因此，无论是用户投影还是 web 投影，都将浪费大量信息。

   与意见网络密切相关的一个核心问题是：如何抽取隐藏信息 hidden information 并进行个性化推荐。互联网和 World Wide Web 的指数级增长使得人们面临信息过载：用户面临太多数据和来源，无法找到与用户最相关的信息。信息过滤的一个里程碑是使用搜索引擎，然而它无法解决这个过载问题，因为它没有考虑个性化，因此对于习惯截然不同的用户返回了相同的结果。因此，如果用户的习惯和主流不同，那么用户很难在无数的搜索结果中找到自己喜欢的东西。迄今为止，有效过滤信息过载的最有潜力的方法是个性化推荐。也就是说，使用用户的个人信息（即该用户活动的历史轨迹）来揭示其习惯并在推荐中加以考虑。例如，Amazon.com 使用用户的购买历史来提供个性化推荐。如果你购买了统计物理学教科书，那么亚马逊可能会向你推荐一些其它统计物理学书籍。基于成熟的 WEB 2.0 技术，推荐系统经常用于 web-based 的电影共享（音乐共享、书籍共享等）系统、web-based 的销售系统、书签网站等。最近，受经济和社会意义的推动，高效推荐算法的设计成为从营销实践到数学分析、从工程科学到物理学界的共同焦点。

   在论文 《Bipartite network projection and personal recommendation》 中，作者提出了一种非对称（即 $w_{i,j}\ne w_{j,i}$）、允许自连接（即 $w_{i,i}\gt 0$）的加权方法。此外，作者提出的方法是沟通二部网络投影、个性化推荐双方的桥梁。数值模拟表明：论文的方法作为个性化推荐算法，其性能显著优于广泛使用的全局排序方法global ranking method: GBM 和协同过滤 collaborative filtering: CF 。

6.1 模型

6.1.1 加权投影图

1. 不失一般性，我们首先确定 $\mathcal X$ 加权投影图中边的权重。定义 $w_{i,j}$ 为：从顶点 $x_j$ 的角度看，顶点 $x_i$ 的重要性。 我们假设每个 $\mathcal X$ 类型的顶点都有一定数量的资源（如推荐强度 power ），因此 $w_{i,j}$ 表示顶点 $x_j$ 的资源需要分配给顶点 $x_i$ 的比例。通常 $w_{i,j} \ne w_{j,i}$ 。

   为得到 $w_{i,j}$ 的解析表达式，我们回归二部图。由于二部图本身是无权的，因此任意 $\mathcal X$ 类型顶点的资源应该平均分配给它的 $\mathcal Y$ 类型的邻居；同理，任意 $\mathcal Y$ 类型顶点的资源应该平均分配给它的 $\mathcal X$ 类型的邻居。如下图所示，我们最初为三个 $\mathcal X$ 类型的顶点初始分配了资源 $x,y,z$ 。则资源重新分配过程包含两个步骤：

   • 资源先从 $\mathcal X$ 类型的顶点流动到 $\mathcal Y$ 类型的顶点。
   • 然后资源从 $\mathcal Y$ 类型的顶点流回 $\mathcal X$ 类型的顶点。

   假设最后三个 $\mathcal X$ 类型的顶点最终分配到资源 $x^\prime,y^\prime,z^\prime$ ，则有：

   $$\begin{bmatrix} x^\prime\\ y^\prime\\ z^\prime \end{bmatrix} = \begin{bmatrix} \frac {11}{18} & \frac{1}{6}&\frac{5}{18}\\ \frac {1}{9} & \frac{5}{12}&\frac{5}{18}\\ \frac {5}{18} & \frac{5}{12}&\frac{4}{9}\\ \end{bmatrix}\begin{bmatrix} x \\ y\\ z \end{bmatrix}$$

   这个 3x3 的矩阵是按列归一化的，记作 $\mathbf W=\{w_{i,j}\}_{3\times 3}$ ，则第 $i$ 行第 $j$ 列元素 $w_{i,j}$ 表示 $x_j$ 的初始资源转移到 $x_i$ 的比例（占 $x_j$ 初始资源的比例）。根据前面的描述，这个矩阵就是我们需要的权重矩阵。

   

2. 现在考虑更通用的二部图 $G(X,Y,E)$，其中 $X=\{x_1,\cdots,x_n\}$ 为 $\mathcal X$ 类型的顶点， $Y=\{y_1,\cdots,y_m\}$ 为 $\mathcal Y$ 类型的顶点， $E$ 为二部图的边。我们定义二部图的邻接矩阵为：

   $$\mathbf A = \begin{bmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,m} \end{bmatrix}$$

   其中 $a_{i,l}$ 表示 $(x_i,y_l)$ 之间的邻接关系：

   $$a_{i,l} = \begin{cases} 1,& (x_i,y_l)\in E\\ 0,& (x_i,y_l)\notin E \end{cases}$$

   定义 $d_{x_i}$ 为顶点 $x_i$ 的度degree：$d_{x_i} = \sum_{l=1}^m a_{i,l}$ 。定义 $d_{y_l}$ 为顶点 $y_l$ 的度degree ：$d_{y_l} = \sum_{i=1}^n a_{i,l}$ 。

   假设 $\mathcal X$ 类型的顶点 $x_i$ 具有初始的资源 $f(x_i) \gt 0$ 。

   • 第一步：所有 $\mathcal X$ 的资源流入 $\mathcal Y$ 中，则 $y_l$ 的资源为：

     $$f(y_l) = \sum_{i=1}^n \frac{a_{i,l}}{d_{x_i}}\times f(x_i)$$

   • 第二步：所有 $\mathcal Y$ 的资源流入 $\mathcal X$ 中，则 $x_i$ 的资源为：

     $$f^\prime(x_i) = \sum_{l=1}^m \frac{a_{i,l}}{d_{y_l}}\times f(y_l) = \sum_{l=1}^m \frac{a_{i,l}}{d_{y_l}}\sum_{j=1}^n \frac{a_{j,l}}{d_{x_j}}\times f(x_j)\\ = \sum_{j=1}^n\left(\frac{1}{d_{x_j}}\sum_{l=1}^m\frac{a_{i,l} a_{j,l}}{d_{y_l}}\right)\times f(x_j)$$

   如果重写为：

   $$f^\prime(x_i) = \sum_{j=1}^n w_{i,j}f(x_j)$$

   则有：

   $$w_{i,j} = \frac{1}{d_{x_j}} \sum_{l=1}^m \frac{a_{i,l}a_{j,l}}{d_{y_l}}$$

   因此矩阵 $\mathbf W = \{w_{i,j}\}_{n\times n}$ 就是我们希望得到的 $\mathcal X$ 投影图的权重矩阵。因此 $\mathcal X$ 的资源重新分配过程可以重写为：

   $$\mathbf{\vec f}^\prime = \mathbf W \mathbf{\vec f}$$

   该算法可以看作是 PageRank 算法的推广，而这些算法本质上是基于消息传递机制。

3. 可以发现权重矩阵 $\mathbf W$ 的几个特点：

   • 权重矩阵是非对称的，且满足：

     $$\frac{w_{i,j}}{d_{x_i}} = \frac{w_{j,i}}{d_{x_j}}$$

     这符合我们的经验，如果某个科学家发表了很多论文，即他的 degree 很大，则单篇合作论文的权重相对较小。$w_{i,j}$ 代表 $x_j$ 资源转移到 $x_i$ 的比例，如果 $x_j$ 的degree 比较大，则它转移到 $x_i$ 的比例也会较低。

   • 权重矩阵对角线元素非零。这意味着：如果 $\mathcal Y$ 顶点只有一个相连的 $\mathcal X$ 顶点，则这个连接关系会在投影过程中得到保留。假设该顶点为 $y_s$ ，唯一与它相连的顶点为 $x_i$ ，则有：

     $$d_{y_s} = 1,\quad a_{j,s} = \begin{cases} 1,& j=i\\ 0,& j\ne i \end{cases}$$

     因此有：

     $$w_{i,i} = \frac{1}{d_{x_i}} \left(\frac{a^2_{i,1} }{d_{y_1}} + \cdots + \frac{a^2_{i,s} }{d_{y_s}} + \cdots \right)$$

     可以看到 $(x_i,y_s)$ 的连接关系被保留在 $w_{i,i}$ 中。

     事实上可以证明：权重矩阵对角线元素是每一列的最大元素，即 $w_{i,i}\ge w_{j,i}$ 。当且仅当 $x_i$ 的所有 $\mathcal Y$ 邻居都是 $x_j$ 的 $\mathcal Y$ 邻居的子集时，等式成立。这在论文协作网络上可以发现。如：学生的论文都是和他们的导师共同发表的，因此如果 $x_i$ 为学生、$x_j$ 为他/她的导师，则有 $\frac{w_{j,i}}{w_{i,i}}\le 1$ 。

     因此比例系数 $\frac{w_{j,i}}{w_{i,i}}$ 可以视为 $x_i$ 的研究相对于 $x_j$ 的独立性，这个比例越低则独立性越高。最终 $x_i$ 的独立性可以刻画为：

     $$I_i = \sum_{j=1}^n\left(\frac{w_{j,i}}{w_{i,i}}\right)^2$$

     注意：度量 $I_i$ 仅仅只是一个示例，它用于说明如何使用 $w_{i,i}$ 中包含的信息，并不能说明独立是好还是不好。

6.1.2 NetworkBased 推荐

1. 一个推荐系统包含用户集合 $\mathbb U = \{u_1,\cdots,u_m\}$ ，推荐对象object 集合 $\mathbb O=\{o_1,\cdots,o_n\}$ 。

   假设只存在用户到object 的边，则推荐系统可以描述为一个 $m\times n$ 的邻接矩阵 $\mathbf A=\{a_{i,j}\}$。

   我们假设意见网络是无权重的，即：如果 $u_i$ 收藏了 $o_j$，则 $a_{i,j}=1$ 。$a_{i,j} = 0$ 表示用户 $u_i$ 对 $o_j$ 尚未收藏。我们认为用户收藏了对象表明用户喜欢该对象。

   一个更复杂的情况是，用户不仅表示了喜欢的意向，还给出了喜欢的程度（以评分表示）。这两种情况密切相关，但是本文我们重点讨论前一种情况。

2. 定义 $d_{o_i}$ 为 object $o_i$ 的度 degree ，$d_{u_i}$ 为用户 $u_i$ 的度 degree 。

   • Global Ranking Method:GRM：将所有 object 按照 degree 降序排列，并推荐 degree 最高的top 对象，即推荐热门对象。

     尽管GRM 缺乏个性化导致推荐效果不尽人意，但是它简单直接并且节省资源，因此被广泛使用。如 “畅销新书“ 这类推荐都可以视为 GRM 。

   • MemoryBased CF：基于用户之间相似度的个性化推荐。

     给定用户 $u_i$ 和 $u_j$ ，他们的相似度定义为：

     $$\text{sim}_{i,j} = \frac{\mathbf{\vec u}_i\cdot \mathbf{\vec u}_j}{||\mathbf{\vec u}_i||\times ||\mathbf{\vec u}_j||}$$

     其中 $\mathbf{\vec u}_i = (a_{i,1},a_{i,2},\cdots,a_{i,n})^T$ 为以object 表示的用户向量，且 $a_{i,l}\in \{0,1 \}$（因为是无权图）。则有：

     $$\text{sim}_{i,j} = \frac{\sum_{l=1}^na_{i,l}\times a_{j,l}}{\sqrt{d_{u_i}\times d_{u_j}}}$$

     用户 $u_i$ 在object $o_l$ 上预测的得分为：

     $$p_{i,l} = \sum_{j=1,j\ne i}^m s_{i,j}\times a_{j,l}\\ s_{i,j} = \frac{\text{sim}_{i,j}}{\sum_{j^\prime=1,j^\prime\ne i}^m \text{sim}_{i,j^\prime}}$$

     有两个因素会影响 $p_{i,l}$：

     • 如果 $o_l$ 的 degree 很大，即非零的 $a_{j,l }$ 越多，则 $p_{i,l}$ 累加的项越多，结果越大。
     • 如果 $o_l$ 被更多的、与 $u_i$ 相似的用户喜欢，则对应的权重 $s_{i,j}$ 越大，则 $p_{i,l}$ 越大。

     前者重视全局信息（对象 $o_l$ 的度，对每个用户都是无差别的）、后者重视个性化信息（每个用户都不同）。

     对于任意用户 $u_i$ ，我们将所有非零 $p_{i,l}$ 且 $a_{i,l} = 0$ （$a_{i,l} = 0$ 表示用户尚未收藏的）的对象根据 $p_{i,l}$ 降序排列，然后推荐其中的 top K 对象。

3. 这里我们基于加权投影图提出了一种推荐算法，该算法是对二部图的加权方法的直接应用。

   • 首先对二部图进行 object 映射，得到的加权图定义为 $G_{\mathcal O}$ 。

   • 然后给定用户 $u_i$ ，我们获取用户已经收藏的object 集合为 $\mathbb O_{u_i}$ ，并在该集合的每个object 上放置一些资源。

     为简单起见，我们在 $G_{\mathcal O}$ 的每个顶点上初始化资源为：

     $$f(o_l) = a_{i,l}$$

     即：如果 $u_i$ 喜欢 $o_j$ ，则它初始化资源为单位1；否则初始化资源为 0 。

     注意：对于不同用户，$G_{\mathcal O}$ 的初始化配置是不同的，这是个性化的初始化。

   • 最终我们得到 $G_{\mathcal O}$ 中顶点的资源为：

     $$\mathbf{\vec f}^\prime = \mathbf W\mathbf{\vec f}$$

     因此有：

     $$f^\prime(o_l) = \sum_{k=1}^n w_{l,k}f(o_k) =\sum_{k=1}^n w_{l,k}\times a_{i,k}$$

     其中 $w_{l,k}$ 表示 $o_k$ 的资源分配到 $o_l$ 的比例。

     对于每个用户 $u_i$，我们将所有非零资源 $f^\prime(o_l)$ 、且 $a_{i,l} = 0$ （$a_{i,l} = 0$ 表示用户尚未收藏）的对象按照资源 $f^\prime(o_l)$ 降序排列，然后推荐其中的 top K 对象。

   由于不同用户的初始化配置不同，因此该分配方程需要重复执行 $m$ 次。写成矩阵的形式为：

   $$\mathbf F^\prime = \mathbf W \mathbf A^\top\in \mathbb R^{n\times m}$$

   其中 $\mathbf F^\prime$ 第 $i$ 列为用户 $u_i$ 在各 object 上的最终分配资源。

   这种方法我们称作基于网络的推断 NetworkBased Inference: NBI，因为它是基于加权映射网络 $G_{\mathcal O}$ 的。

   该方法是标签传播算法的推广，有两个区别：该方法仅传播两次，相比之下标签传播算法不停传播直到收敛；该方法除了邻接矩阵还有权重矩阵，相比之下标签传播算法仅使用邻接矩阵。

4. NBI 方法仅仅考虑用户喜欢的商品，而完全不考虑用户不喜欢的商品，这可能会丢失一些信息。NBI 方法的一个重要优点是：它不依赖于任何控制参数，因此不需要调参。

   另外，这里提出的 NBI 推荐算法只是一个粗糙的框架，很多细节尚未详细的探索。例如，顶点的初始配置可以采取更复杂的形式：

   $$f(o_l) = a_{i,l}\times d_{o_l}^\beta$$

   即它给不同degree 的顶点 $o_l$ 分配不同的资源，这可能会比原始的分配产生更好的推荐效果。

   也可以考虑动态的资源分配过程，这会导致类似于标签传播算法的迭代式推荐算法。虽然这样的算法需要更长的 CPU 时间，但是可以提供更准确的预测。

5. 定义 $\bar d_u$ 为用户的平均degree，$\bar d_o$ 为object 的平均 degree，则有：

   • MemoryBased CF 的平均计算复杂度为： $O(m^2\bar d_u + mn\bar d_o)$ 。

     • 第一项来自于用户之间的相似度计算：$m\times m$ 对用户、每对用户平均 $\bar d_u$ 个object。
     • 第二项来自于预测得分：每个用户平均需要使用 $\bar d_o$ 个相似用户（必须在目标object 上有收藏行为）根据相似度（计算复杂度为 $n$ ）的加权和，一共 $m$ 个用户。

     假设 $n\bar d_o = m\bar d_u$ （它就是二部图中边的数量），则整体计算复杂度为 $O(m^2 \bar d_u)$ 。

   • NBI 的计算复杂度为：$O(m\bar d_{u^2} + mn\bar d_u)$ ，其中 $\bar d_{u^2}$ 为用户 degree 分布的二阶矩（二阶矩为随机变量平方的期望）。第一项为权重矩阵的计算，第二项为最终资源分布的计算。很明显有 $\bar d_{u^2} \lt n\bar d_u$，因此计算复杂度为 $O(mn\bar d_u)$ 。

   在很多推荐系统中，用户数通常比object 数大得多，因此 NBI 运行速度比 MemoryBased CF 快得多。另外 NBI 存储权重矩阵需要 $O(n^2)$ 的空间，而 MemoryBased CF 存储相似度矩阵需要 $O(m^2)$ 的空间。因此 NBI 能够在准确性、时间复杂度、空间复杂度上超越 MemoryBased CF 。