代码：https://download.csdn.net/download/qq_38735017/87427483
本文的主要研究内容如下：
分析了在推荐系统中加入差分隐私的重要性和必要性，介绍了推荐系统隐私保护的研究背景和目前国内外推荐系统、差分隐私技术以及二者结合产物的研究现状。
推荐系统概述。介绍推荐系统的主要分类方法和对于协同过滤推荐算法的研究；介绍了协同过滤算法的主要步骤：收集用户偏好、找到相似的用户或者物品、计算并推荐。
差分隐私概述。分析了差分隐私的概念和该模型相对于传统安全模型的优势，研究了差分隐私的性质和常用的实现机制。
基于差分隐私的协同过滤推荐系统的设计、实现与测试。基于前面的理论知识，设计了一个使用基于用户的协同过滤的推荐系统,其中相似度采用两种方法计算，并使用差分隐私将推荐结果进行加密。然后将设计出来的系统应用于 MovieLens 的两个不同规模的数据集上进行实验比较和分析，通过测试，找到可以相对较好地平衡推荐结果准确度和隐私保护程度的隐私预算。
第二章 基础知识
推荐系统
推荐系统概述
推荐系统(RS)是一种向目标用户建议可能感兴趣物品的软件工具和技术。推荐系统的建议可用于多种决策过程，如购买什么物品、听什么音乐以及在网上浏览什么新闻等。推荐系统中的“物品”指系统向用户所推荐内容的总称。某个推荐系统通常专注于一个特定类型的物品(如 CD 或新闻)，因此它的设计、图形用户界面以及用于生成推荐结果的核心技术都是为特定类型的物品提供有用且有效的建议而定制的。
推荐系统主要服务于缺乏经验和能力的用户，他们通常无法从大量可供选择的物品中选取感兴趣的物品，如无法从某网站中选取感兴趣的商品。推荐系统中一个典型的例子是图书推荐，系统可以帮助用户挑选一木可能感兴趣的书来读。知名网站亚马逊中，系统采用个性化推荐技术为每个客户进行推荐。通常所说的推存具有个性化，即不同的用户或用户组所接收的建议是不同的。当然也存在非个性化推荐，但它们大都非常简单，通常出现在报纸或杂志上。最简单的个性化推荐是提供一个排序好的物品列表。通过该排序列表，系统试图根据用户的偏好和某些约束条件来预测最合适的产品或服务。为了完成上述计算任务，推荐系统通常需要收集用户的喜好信息，这种喜好信息或是显式的，如物品的评分信息，或通过解释用户的行为做出推断所得。
图 2.1 推荐系统模型
推荐系统最初起源于一个相当简单的现象：人们在做日常工作和决策时总是依赖于他人提供的建议。例如，要选择读本书时，通常依靠朋友的推荐；雇主依靠推荐信做招募的决定；当选择观看影片时，人们倾向于阅读并且依赖影评家在报纸上所写的影评。
为了模拟上述行为，推荐系统通过算法将社区用户的建议推荐给一个活跃用户。系统向用户所推存的物品是相似用户喜欢的。这种方法称为协同过滤，它的理论依据是：如果活跃用户的历史评分信息与某些用户有相似之处，那么由这些相似用户所得出的推荐结果应与该活跃用户相关，且这些推荐结果也是该活跃用户所感兴趣的。
（还有推荐系统的种类没有加进去）
协同过滤推荐算法
协同过滤(colaboratile fitering)。这种方法是找到与用户有相同品味的用户，然后将相似用户过去喜欢的物品推荐给该用户，两用户之间的品位相似性是通过计算用户历史评分记录的相似性所得。协同过滤被认为是推荐系统中最流行和最广泛实现的技术。
设计这种模型的主要挑战是底层评分矩阵是稀疏的。例如在某个用户可以具体给出评分表达自己喜爱程度的 APP 中，大多数用户可能只看了浩如烟海的众多影片中的一小部分，因此评分大多是未知的。
由于已知评分常常是与用户和物品密切相关的，因此协同过滤法的基本思想是由已知评分估计未知评分。例如，有两个用户分别叫 Alice 和 Bob，他们具有相似品味。当两人都给出具体评分时，给出的评分应当是十分相似的，这种相似度可以被底层算法检测出来。在这种情况下，对某个物品，两人中如果仅有一人做出了评分，另一个人的评分可能与该评分十分接近。多数协同过滤模型着重于借助物品之间或是用户之间内在的关联性做出预测，还有些模型两者都考虑了。更进一步，部分模型采用经过仔细设计的优化算法来创建训练模型。然后这个模型被用来估计矩阵中缺失的值。有两种方法在协同过滤算法中经常用到：基于记忆的方法以及基于模型的方法。
基于记忆的方法：基于记忆的方法也被称为基于近邻的协同过滤算法。这是最早的协同过滤算法之一，其中用户—物品组合的评分是在“近邻”的基础上进行预测。这些“近邻”可以用以下两种方式之一来定义：
1.基于用户的协同过滤。其基本思想为：给用户推荐和他兴趣相似的用户感兴趣的物品。当需要为一个用户 A 进行推荐时，首先，找到和 A 兴趣相似的用户集合，用 U 表示，然后，把集合 U 中用户感兴趣而 A 没有听说过，即未进行过操作的物品推荐给 A。算法分为两个步骤：首先计算用户之间的相似度，选取最相似的 N 个用户，然后根据相似度计算用户评分。
用户相似度的计算是基于用户的协同过滤算法的重要内容，主要可以通过余弦相似度、Pearson 系数等方式进行计算。
假设：u 和 v 是两名用户，Iμ就是 u 看过的电影的集合，Iv是 v 对看过的电影的集合，ruk是用户 u 对电影 k 的评分，rvk同理，是对于某一用户所有打过分的电影所求出的平均分，则用户 u 和 v 之间的相似度可以通过如下方式计算：
余弦相似度：
Pearson 系数：
得到用户相似度后，可以根据如下公式计算用户评分：
其中r(μ，i)代表用户 u 对物品 i 的评分，S(μ)为与用户 u 最相似的 N 个用户，N(i)为对物品 i 进行过操作的用户集合，Wμv为用户 u 与用户 v 的相似度，rvi为用户 v 对物品 i 的评分。
基于用户的协同过滤的推荐结果反映了用户所在的一个兴趣群体中的热门物品，更加社会化但缺乏个性化，能够满足物品的时效性，在新闻推荐领域能够发挥很大的作用。用户的兴趣在一段时间内是相对固定的，因此用户相似度矩阵不会实时进行更新，存在新用户的冷启动问题。
图 2.2 基于用户的协同过滤推荐系统模型
基于物品的协同过滤。该算法的基本思想为：给用户推荐和他们以前喜欢的物品相似的物品，这里所说的相似并非从物品的内容角度出发，而是基于一种假设：喜欢物品 A 的用户大多也喜欢物品 B 代表着物品 A 和物品 B 相似。基于物品的协同过滤算法能够为推荐结果做出合理的解释，比如电子商务网站中的“购买该物品的用户还购买了…”。基于物品的协同过滤的计算步骤和基于用户的协同过滤大致相同：首先，计算物品相似度，选出最相似的 N 个物品，然后根据相似度计算用户评分。
基于物品的协同过滤的推荐结果更加个性化，反映了用户的个人兴趣，对挖掘长尾物品有很大帮助，被广泛应用于电子商务系统。在物品数较多时，物品相似度计算效率较差，因此通常以一定的时间间隔离线进行计算，然后将物品相似度数据缓存在内存中，这样一来，便可以根据用户的新行为实时向用户做出推荐。但基于物品的协同过滤同样存在新用户冷启动问题。
图 2.3 基于物品的协同过滤推荐系统模型
基于记忆的方法的优点在于容易实现，并且其生成的推荐易于解释。然而，基于记忆的方法并不适用于稀疏的评分矩阵。例如，它很难找到与 Bob 足够相似并且评价过《Gladiator》的用户，这种情况下很难准确地预测 Bob 对《Gladiator》的评分。换句话说，这种方法缺少对评分预测的全面覆盖。但如果只需要预测出 top-k 个最相似的物品，覆盖面不全也没关系。
基于模型的方法：在基于模型的方法中会用到机器学习和数据挖掘技术。这是因为模型的参数需要通过一一个优化框架学习得到。基于模型的方法包括决策树、基于规则的模型、贝叶斯方法和潜在因子模型。包括潜在因子模型在内的许多方法，即使对稀疏的评分矩阵也能有较高的覆盖率。
基于记忆的协同过滤算法很简洁，但却是启发式的，并不适用于所有环境。基于模型的方法与基于记忆的方法之间的区别有点人为因素，因为基于记忆的方法实际上可以被认为是基于相似性的方法。由于 Netflix 大奖赛的影响，潜在因子模型近几年得到了推广，实际上，在不完整数据集上与其相似的算法很早就被提出了。最近的研究表明，一些基于记忆和基于模型的方法的结合体能提供非常准确的结果。
- 要实现协同过滤，需要进行如下几个步骤：
- 收集用户偏好
- 找到相似的用户或者物品
- 计算并推荐
收集用户偏好是指从用户的行为和偏好中发现规律，并基于此进行推荐，所以如何收集用户的偏好信息成为系统推荐效果最基础的决定因素。用户有很多种方式向系统提供自己的偏好信息，比如：评分，投票，转发，保存书签，购买，点击流，页面停留时间等等。以上的用户行为都是通用的，在实际推荐引擎设计中可以自己多添加一些特定的用户行为，并用它们表示用户对物品的喜好程度。通常情况下，在一个推荐系统中，用户行为都会多于一种，那么如何组合这些不同的用户行为呢？基本上有如下两种方式：
- 将不同的行为分组。一般可以分为查看和购买，然后基于不同的用户行为，计算不同用户或者物品的相似度。类似于亚马逊给出的“购买了该书的人还购买了”，“查看了该书的人还查看了”等等。
- 不同行为产生的用户喜好对它们进行加权。对不同行为产生的用户喜好进行加权，然后求出用户对物品的总体喜好。
当收集好用户的行为数据后，还要对数据进行预处理，最核心的工作就是减噪和归一化。减噪是指因为用户数据在使用过程中可能存在大量噪音和误操作，所以需要过滤掉这些噪音。归一化是指不同行为数据的取值相差可能很大，例如用户的查看数据肯定比购买数据大得多。通过归一化，才能使数据更加准确。
通过上述步骤的处理，就得到了一张二维表，其中一维是用户列表，另一维是物品列表，值是用户对物品的喜好。还是以电影推荐为例，如下表：
表 2.1 不同用户对电影的评分
然后是找到相似的用户或者物品。对用户的行为分析得到用户的喜好后，可以根据用户的喜好计算相似用户和物品，然后可以基于计算结果进行推荐。在计算用户之间的相似度时，是将一个用户对所有物品的偏好作为一个向量，而在计算物品之间的相似度时，是将所有用户对某个物品的偏好作为一个向量。求出相似度后，接下来可以求相似邻居了。
接下来是计算并推荐。在上一步求相似邻居的时候，通常是求出 TOP-k 邻居，然后根据邻居的相似度权重以及他们对物品的偏好，对当前用户没有评分的未涉及物品生成一个预测评分，并通过对这个预测评分从高到低排序，得到一个物品列表，然后推荐列表中的前几个物品。表 2.2 和表 2.3 就是在电影推荐系统中，对一个用户进行推荐之后，利用 Pearson 系数计算得出的 TOP-k 邻居和对被推荐用户未看过部分电影的预测评分。
表 2.2 被推荐用户的 TOP-5 邻居
表 2.3 对某个用户得出的推荐结果
协同过滤算法的相关问题
协同过滤与基于内容的过滤相比，优势就是可以在根据各个用户的历史信息推荐项目，跟项目本身的内容属性无关。尽管协同过滤技术取得了一定成功，但仍然存在一些问题：
- 冷启动问题：在产品刚刚上线、新用户到来的时候，如果没有用户在应用上的行为数据，也无法预测其兴趣爱好。另外，当新商品上架也会遇到冷启动的问题，没有收集到任何一个用户对其浏览，点击或者购买的行为，也无从对商品进行推荐。
- 数据稀疏性问题：当用户仅对数据库中可用的项目中的一小部分进行评分时，就会导致这种问题。
- 可扩展性问题：这是与推荐算法相关的另一个问题，因为计算通常随着用户和项目的数量线性增长。当数据集的量有限时，推荐技术是有效可行的，但当数据集的量增加时，生成推荐的量就不太好。在这种情况下，用于解决可扩展性问题和加速推荐生成的方法会基于降维技术，例如奇异值分解（SVD）。
差分隐私
差分隐私是一种基于该理论的隐私模型——某个计算的输出不应该让任何输入数据推测出来。为了达到这个目标，必须保证所有计算结果的概率分布不会因为在输入当中加入或者删除任何特别的记录而发生显著变化。举个例子，假设现在有一个数据库可以查到有多少人单身。刚开始的时候查询发现，2 个人单身；现在张三跑去登记了自己婚姻状况，这个时候再一查，发现有 3 个人单身，所以得出张三就是单身。现在如果我们不想让攻击者知道张三是否处于单身，就要用差分隐私来保护他的信息。
差分隐私的数学概念为：设有一个随机算法 A，Range（A）为 A 所有可能的输出构成的集合。对于任意两个邻近数据集D和D'以及 Range（A）的任何子集 t，若算法 A 满足：
则称算法 A 提供了ε —差分隐私保护，其中，参数ε称为隐私保护预算，Pr 表示发生某一事件的概率。一般而言，ε越小，隐私保护程度越好。
差分隐私为缓解通过推荐系统的输出来推测用户隐私数据的风险提供了手段。一个实现差分隐私常用的方法是通过拉普拉斯(Laplace)机制，对服从拉普拉斯分布的噪声数据进行仔细调整并将其加人到计算当中，而加入噪声的多少就取决于敏感度和隐私预算的取值。这些噪声屏蔽了在某条记录中任何变化对计算结果所造成的影响。
Laplace 分布是统计学中的概念，是一种连续的概率分布。如果随机变量的概率密度函数分布为：
, 均为常数
图 2.4 Laplace 概率密度函数
那么它就是拉普拉斯分布。其中， 是位置参数，λ是尺度参数。在实现的时候一般把μ设为 0，λ由
得到。ε是差分隐私的隐私预算。
则称为敏感度。在差分隐私中，总共有两种敏感度：全局敏感度和局部敏感度。本文中所实现系统只用到了全局敏感度，故只介绍前者。它代表的意思是对于两个相邻数据集D,D'，一个查询函数
最大的变化范围。其数学公式为：
表示函数f在数据集D上的查询结果。矩阵范数和下标 1 一起代表相邻数据集D和D'的所有查询结果之差的最大值，即这两个数据集查询结果之差最大是 1。
对原始数据加入服从拉普拉斯分布的噪声，则称为引入了拉普拉斯机制。拉普拉斯机制的定义是给定查询函数
满足：
其中
表示最终的一个确定的查询结果
加上一个不确定的随机噪声
得到的最终结果，
是独立同分布的变量，为
)。则该机制满足ε— 差分隐私，证明过程如下：
假设
表示
的 pdf（probability density function），
表示
的 pdf，则对于某个输出
，我们有
在刚才使用差分攻击成功获得张三是单身的例子里，本来两次查询结果是确定的 2 个单身和 3 个单身，现在加入拉普拉斯噪声后，确定的结果变成了两个随机变量，在多次查询之后，将查询结果进行统计，统计结果为期望分别为 2 和 3 拉普拉斯分布，如下图所示。现在，如果张三不在数据库的话，得到结果可能是 2.5；张三在的话，得到的结果也可能是 2.5；两个数据集查询得到某一个结果的概率很接近，以至于我们根本分不清这个结果来自于哪一个数据集。这样攻击者就没有办法在单次查询中得到具体的数值，就有效防止了个人的隐私泄露。
图 2.5 加入噪声之后的查询结果（多次）
还有一种机制是指数机制。指数机制与拉普拉斯机制不同，前者是简单地对输出的数值结果加入噪声实现差分隐私。而对于非数值型数据而言，它的输出是一组离散数据
中的元素。
指数机制整体的思想就是，当接收到一个查询之后，不是确定性地输出一个
结果，而是以一定的概率值返回结果，从而实现差分隐私。而这个概率值则是由打分函数确定，得分高的输出概率高，得分低的输出概率低。
差分隐私具有两个最重要的优点：
- 严格定义了攻击者的背景知识：除了某一条记录，攻击者知晓原数据中的所有信息——这样的攻击者几乎是最强大的，而差分隐私在这种情况下依然能有效保护隐私信息；
- 差分隐私拥有严谨的统计学模型，极大地方便了数学工具的使用以及定量分析和证明。
正是由于差分隐私的诸多优势，使其一出现便迅速取代了之前的隐私模型，成为隐私研究的核心，并引起理论计算机科学、数据库与数据挖掘、机器学习等多个领域的关注。
但差分隐私并不完美，也有一些缺点。最主要的就是由于对于背景知识的假设过于强，需要在查询结果中加入大量的随机化，导致数据的可用性急剧下降。特别对于那些复杂的查询，有时候随机化结果几乎掩盖了真实结果。这也是导致目前应用不多的一个原因。为了平衡数据可用性和隐私保护，有时候人们采用较为松弛的高斯机制来代替拉普拉斯机制。
小结
本章介绍了与作品相关的背景知识。首先对推荐系统进行概述，介绍了其概念和功能，然后介绍了推荐系统的常用实现方法——协同过滤算法，主要及分析并介绍了基于用户的协同过滤推荐系统的实现原理和主要步骤。然后介绍了本文的另一主题——差分隐私。对其定义、概念和实现机制进行了介绍，最后分析了差分隐私的优缺点。
第三章 基于差分隐私保护的协同过滤推荐系统
对于推荐系统的攻击方式
在文献[1]中，作者等人可以结合辅助信息推断出用户的历史评分和行为。辅助信息的定义是：对于任意用户
，他的历史信息为
，则定义其辅助信息为可以背攻击者所获得到的历史信息子集
。辅助信息的的常见获取方式有以下三种：
- 许多网站会直接将用户对某些商品的评分和评价进行公开，有部分网站还会询问用户是否对外公开自己的交易记录；
- 用户有时候自己会在某些 A 网站上泄露有关于自己的隐私信息。这个时候在使用 A 的账号第三方登录 B 网站时，B 网站有时候会拉取该用户在 A 网站的数据；
- 现实生活中，用户的一些行为习惯和部分信息会在社交聚会中被泄露。
基于掌握的辅助信息，文献[2]中的一个算法可以推断用户的非辅助信息部分。
