本文主要是对项亮的推荐系统实践部分章节进行了一些总结，先从什么是推荐系统开始讲起，然后介绍了评测推荐系统的指标和方法，最后介绍了常见的推荐系统算法。

《推荐系统实践》封面

什么是推荐系统

随着信息技术和互联网的快速发展，人们逐渐从信息匮乏的时代走入了信息过载的时代。每天都有海量的信息被生产出来，用户如何从中找到自己感兴趣的内容变得越来越困难，内容生产者也在想方设法让自己生成的内容从海量信息中脱颖而出。为了解决信息过载的问题，历史上出现过的代表方案有分类目录和搜索引擎，这两者都要求用户明确知道自己需要的内容关键词。而推荐系统不需要用户提供明确的需求，而是通过分析用户的历史行为给用户的兴趣建模，从而主动给用户推荐能够满足它们兴趣的内容。推荐系统通过发掘用户的行为，找到用户的个性化需求，从而将长尾商品准确地推荐给需要它的用户，帮助用户发现那些他们感兴趣但很难发现的商品。

推荐系统的应用

在互联网的各类网站中都可以看到推荐系统的应用，尽管不同网站使用的技术不同，但总的来说几乎所有的推荐系统应用都是由前台的展示页面、后台的日志系统以及推荐算法系统构成。

• 电子商务：淘宝、京东、亚马逊
• 电影/视频：Netflix、YouTube、爱奇艺
• 音乐：Pandora、网易云音乐、豆瓣FM
• 社交网络：Facebook、Twitter、LinkedIn、新浪微博
• 个性化阅读：Digg、Flipboard、今日头条
• 基于位置的服务：Foursquare
• 个性化广告：Facebook Audience Network

推荐系统实验方法

在推荐系统中，主要有三种评测推荐效果的实验方法：离线实验、用户调查、在线实验。

推荐系统评测指标

• 用户满意度：用户的主观感受，主要通过用户调查的方式获得，也可以间接从用户行为统计中得到。
• 预测准确度：度量一个推荐系统或推荐算法预测用户行为的能力。评分预测的预测准确度一般通过计算测试集和训练集的均方根误差(RMSE)和平均绝对误差(MAE)得到。TopN推荐的预测准确度一般通过计算测试集和训练集的准确率(precison)和召回率(recall)得到。

令r_ui是用户u对物品i的实际评分，r^{^}_ui是推荐算法给出的预测评分，T是测试集，那么：
RMSE = sqrt(Σ_u,i∈T(r_ui-r^{^}_ui)² / |T|)
MAE = Σ_u,i∈T|r_ui-r^{^}_ui| / |T|

令R(u)是用户u在训练集上的推荐结果，T(u)是用户u在测试集上的行为结果，U是用户集合，那么：
Precision = Σ_u∈U|R(u) ∩ T(u)| / Σ_u∈U|R(u)|
Recall = Σ_u∈U|R(u) ∩ T(u)| / Σ_u∈U|T(u)|

• 覆盖率：描述一个推荐系统对物品长尾的发掘能力。

假设用户集合为U，物品集合为I，推荐系统给每个用户推荐一个长度为N的物品列表R(u)，那么：
Coverage = |∪_u∈UR(u)| / |I|

• 多样性：为了满足用户广泛的兴趣，推荐列表需要能够覆盖用户不同的兴趣领域。
• 新颖性：是指给用户推荐那些他们以前没听说过的商品。
• 惊喜度(serendipity)：如果推荐结果和用户的历史兴趣不相似，但却让用户觉得满意，那么就可以说推荐结果的惊喜度很高。
• 信任度：提高信任度的方法是给出合理的推荐解释。
• 实时性：推荐系统需要实时地更新推荐列表来满足用户新的行为变化，并且需要能够将新加入系统的物品推荐给用户。
• 健壮性(robust)：衡量一个推荐系统抗击作弊的能力。

在众多指标中，作者认为：对于可以离线优化的指标，应该在给定覆盖率、多样性、新颖性等限制条件下，尽量优化预测准确度。

常见推荐系统算法

推荐系统是联系用户和物品的媒介，而推荐联系用户和物品的方式主要有3种，如下图所示。

3种联系用户和物品的推荐系统

第一种方法，首先找到用户喜欢的物品，然后找到与这些物品相似的物品推荐给用户。基于这种方法可以给出如下的推荐解释：购买了该商品的用户也经常购买这些商品。这种方法通常被称为基于物品的协同过滤算法(item-based collaborative filtering)。
第二种方法，首先找到和用户有相似兴趣的其他用户，然后推荐这些其他用户喜欢的物品。这种方法通常被称为基于用户的协同过滤算法(user-based collaborative filtering)。
第三种方法，首先找到用户感兴趣的物品特征，然后推荐包含这些特征的物品。这种方法核心思想是通过隐含特征联系用户兴趣和物品，通常被称为隐语义模型算法(latent factor model)。

协同过滤算法

个性化推荐系统的一个重要算法是基于用户行为分析，学术界一般将这种类型的算法称为协同过滤算法(collaborative filtering)。

顾名思义，协同过滤就是指用户可以齐心协力，通过不断地和网站互动，使自己的推荐列表能够不断过滤掉自己不感兴趣的物品，从而越来越满足自己的需求。

基于物品的协同过滤算法

基于物品的协同过滤算法(以下简称ItemCF)，是目前业界应用最多的算法，最早由电子商务公司亚马逊提出。ItemCF算法给用户推荐那些和他们之前喜欢的物品相似的物品，它的主要步骤分为两步。

(1) 计算物品之间的相似度

(2) 根据物品的相似度和用户的历史行为给用户生成推荐列表

第一步计算相似度可用余弦相似度公式

令N(i)是喜欢物品i的用户集合，那么物品i和物品j的相似度可定义为：
w_ij = |N(i) ∩ N(j)| / sqrt(|N(i)||N(j)|)

第二步计算用户对物品的兴趣，如下公式的含义是：和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。

令p_uj为用户u对物品j的兴趣，w_ji是物品j和物品i的相似度，r_ui是用户u对物品i的兴趣（对于隐反馈数据集，如果用户u对物品i有过行为，可简单令r_ui=1），S(j,K)是和物品j最相似的K个物品的集合，那么：
p_uj = Σ_{i∈N(u)∩S(j,K)} w_jir_ui

最后选取该用户兴趣值最高的N的物品作为推荐列表。

基于用户的协同过滤算法

基于用户的协同过滤算法(以下简称UserCF)，是推荐系统中最古老的算法。UserCF算法先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而他没有听说过的物品推荐给他，它的主要步骤分为两步。

(1) 找到和目标用户兴趣相似的用户集合
(2) 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户

第一步计算用户的兴趣相似度可用余弦相似度公式

令N(u)是用户u曾经有过正反馈的物品集合，那么用户u和用户v的相似度可定义为：
w_uv = |N(u) ∩ N(v)| / sqrt(|N(u)||N(v)|)

第二步计算用户对物品的兴趣

令p_ui为用户u对物品i的兴趣，w_uv是用户u和用户v的相似度，r_vi是用户v对物品i的兴趣（对于隐反馈数据集，如果用户v对物品i有过行为，可简单令r_vi=1），S(u,K)是和用户u兴趣最相似的K个用户的集合，那么：
p_ui = Σ_{v∈N(i)∩S(u,K)} w_uvr_vi

最后选取该用户兴趣值最高的N的物品作为推荐列表。

隐语义模型

隐语义模型算法(以下简称LFM)，是最近几年推荐系统领域最为热门的研究话题。LFM算法的核心思想是通过隐含特征联系用户兴趣和物品，它的主要步骤分为三步。

(1) 对物品进行分类
(2) 确定用户对哪些类的物品感兴趣以及感兴趣的程度
(3) 对于给定的类，确定物品在这个类的权重，并且选择性地推荐给用户

关于如何给物品分类，一个简单方案是由编辑来手动分类，但这样存在很强的主观性和较大的工作量。为了解决这个困难，研究人员提出可以从用户数据出发，基于隐含语义分析技术(latent variable analysis)自动找到哪些类，然后进行个性化推荐。隐含语义分析技术有很多著名的模型和方法，比如pLSA、LDA、隐含类别模型、隐含主题模型、矩阵分解等。

LFM通过如下公式计算用户u对物品i的兴趣：
Preference_ui = Σ_k∈[1,K] p_u,kq_i,k
其中p_u,k度量了用户u的兴趣和第k个隐类的关系，而q_i,k度量了第k个隐类和物品i的关系。这两个参数的计算需要一点最优化理论或者机器学习的知识，这里不多作介绍。

三种算法的优缺点比较

• LFM是一种基于机器学习的算法，有较好的理论基础。ItemCF/UserCF是基于邻域的方法，更多的是一种基于统计的方法，没有学习过程。
• 假设有M个用户和N个物品，选取F个隐类。UserCF需要存储用户的相似度矩阵，存储空间是O(M*M)。ItemCF需要存储物品的相似度矩阵，存储空间是O(N*N)。LFM需要的存储空间是O(F*(M+N))。如果用户数很多，UserCF将会占据很大的内存。如果物品数很多，ItemCF将会占据很大的内存。LFM存储空间最少，这在M和N很大时可以很好地节省离线计算的内存。
• 假设有M个用户和N个物品和K条用户对物品的行为记录。那么，UserCF计算用户表的时间复杂度是O(N*(K/N)²)，而ItemCF计算物品表的时间复杂度是O(M*(K/M)²)。而对于LFM，如果用F个隐类，迭代S次，那么它的时间复杂度是O(K*F*S)。在一般情况下，LFM的时间复杂度要稍微高于UserCF和ItemCF，主要是因为该算法需要多次迭代。
• ItemCF算法支持很好的推荐解释，它可以利用用户的历史行为解释推荐结果，但LFM无法提供这样的解释。

总结

在互联网应用中可以看到大量推荐系统的应用，它主要解决了信息过载的问题，通过算法主动帮助用户找到自己感兴趣的内容。常见的推荐系统算法有三种，分别代表三种联系用户和物品的方式，它们是：基于物品的协同过滤算法(ItemCF)，基于用户的协同过滤算法(ItemCF)，隐语义模型算法(LFM)。三种方法各有优劣，需要根据实际场景选择合适的算法，通过不断优化指标找到最优算法。