基于差分隐私技术的地理网络位置建议外文翻译资料

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

基于差分隐私技术的地理网络位置建议

Jia-Dong Zhang Dept. of Computer Science City University of Hong Kong

Gabriel Ghinita Dept. of Computer Science University of Massachusetts Boston

Chi-Yin Chow Dept. of Computer Science City University of Hong Kong

摘要：跟踪标记位置的社交媒体在塑造个人行为方面有着越来越重要的作用。在位置建议的帮助下，用户可以了解符合他们选择意向的事件、产品或者感兴趣的地方。用户的位置和运动模式可从诸如Foursquare（一家基于用户地理位置信息（LBS）的手机服务网站）、公共交通日志或交通监测系统等地理网络定位系统获得。然而,开放的位置移动数据存在严重的隐私问题，比如所访问地点的历史记录会泄露一些用户比较敏感的细节隐私，包括用户的健康状况,个人生活方式等等。在本文中，我们将在差分隐私技术的帮助下研究一种安全的位置数据建议机制。我们还确定必须了考虑的主要因素以提高位置准确性。大量真实数据集的实验结果表明,选择精确的差分隐私技术可以获得满意的位置推荐结果。

一、简介

最新一代的移动设备允许用户参与基于位置的社交网络(LBSNs)和其他以带有地理标签的媒体为重要组成部分的应用程序。通过许多因素可以确定用户的基本取向状况,如年龄、性别、教育水平[1]。除了这些因素,在位置建议中，用户的运动模式变得越来越重要，因为与其他事件或者其他用户之间的地理位置关系是一个重要的决定因素。位置建议可以在不同的粒度水平被执行。例如,一个位置的推荐系统可能考虑GPS系统提供的用户的确切坐标,或者只是粗粒度的地区, 如城市街区,或邮编区域。获得高质量的建议另一个重要方面是运动历史记录的长度大小。一些早期的研究[2],[3],[4],[5]认为,用户的当前位置就足以确定一个恰当的位置建议。获得高质量的位置建议需要分析一个用户大量的不同的轨迹数据。这样越来越多的轨迹库可以运用,由于各种基于位置的应用程序收集的轨迹跟踪,如基于位置的社会网络的登记历史, 使用磁性的公交运营商日志访问令牌,或交通监控系统。

一些现有技术存在地址位置隐私威胁。在文献[10]中的加密方法是合适的,当用户需要私下从数据集检索一个特定的项目,例如近邻查询。然而,位置建议需要一套更广泛的操作确定运动模式。除此之外，加密方法是非常耗费资源的计算。其他技术使用特别保护的定义:在K-anonymity[6],[7],[8]的情况下,每个发布位置必须区别其他Kminus;1位置。这种类型的转换快速而简单,但它最近被证实[11],[12],它不提供保护的背景知识。

差分隐私技术[11][12]提供正式保护去抵挡拥有背景知识的敌方。差分隐私只允许统计查询数据,并将噪声添加到每个应答来实现保护。敌方不能获得某个人是否包含在数据集的显著概率。在位置数据的上下文中，这转化为是否可以在数据集中找到某一特定轨迹的隐私信息。然而,敌方仍然有可能获取轨迹信息的聚合信息，这可能是旅游模式挖掘等足够的任务。

我们根据差分隐私技术使用已处理过的安全数据集研究位置建议。我们的重点是考虑用户在几个连续的运动历史观察的位置建议,这种方法提供了更高的精度。我们研究两种方法:第一个方法用单个图像的多维笛卡儿积空间中的一点代表运动历史。而第二个索引和清理在一个层次结构中位置的直接序列。

我们通过实验评估历史长度的影响，隐私的预算和推荐准确性的数据密度。实验结果表明，仔细处理数据集有可能获得高质量的位置建议。据我们所知，这是第一份研究表明了在位置建议的上下文中应用差分隐私技术的可行性。

总之，我们的成果是：（1）我们第一次使用基于差分隐私保护技术的轨迹数据集研究这个问题；（2）我们为差分隐私保护技术的位置建议考虑了两种技术，对历史长度,数据密度和数据倾斜提供积极地交换；（3）我们为位置建议显示差分隐私技术的可行性，执行一个广泛的实验评价，并强调两者之间的相对权衡考虑替代方法。

本文第二部分介绍了背景信息。第三部分介绍了研究私人位置建议的机制。第四部分包含实验评估结果，第五部分的相关工作。第六部分主要为结论与未来研究方向。

二、背景

我们的工作从两个不同的领域将概念和技术结合在一起,即位置的建议和差分隐私。我们在II-A部分审查关于位置的建议的背景信息。紧随其后，在II-B部分进行一个初级的关于差分隐私的介绍。

A位置建议

基于位置的社交网络如Foursquare,Gowalla和Facebook，吸引了数百万的用户。基于位置的社交网络让用户在访问特定感兴趣的位置分享他们的经验，例如、餐厅、博物馆等。在访问一个位置时,一个用户执行一个虚拟的签入操作，让别人知道他或她的当前位置。附加功能可以提供基于签到，如确定用户的社会地位或基于他们的访问一个特定的位置的次数和频率而对客户进行奖励。为进一步提高用户体验和社会互动，根据其他用户的(积极的)经验当访问的地点，这样的系统可提供的功能位置建议，用户可接受建议并决定去哪些地方参观。这个功能是通过用户签到记录和咨询的历史来实现的。基于人体运动序列模式,最近的研究提出基于一阶马尔可夫链的位置建议的技术来自轨迹。一阶马尔可夫链是用来表示“无记忆”过程，通过位置序列的签到，即从一个位置到另一个地方的转换概率，从而模拟序列模式。

定义1(位置序列)：一个用户的位置是一组序列签到地点，这些地点是越来越多的的用户在入住时间所在的地点。一个位置序列定义为。

定义2（一阶马尔可夫链）：所给的一个用户的位置序列：一阶马尔可夫链用最后一次访问的位置来预测用户访问的下一个位置：

其中是所有用户位置序列的集合所有构成的子序列的数量。

为了提高位置建议的质量,我们推广了一阶马尔可夫链的高阶马尔可夫链的位置建议。

定义3（m阶马尔可夫链）：所给的用户访问的位置序列m阶马尔可夫链根据最新m访问位置，估计用户的下一个位置的可能性。形式上：

为了提供位置推荐，推荐系统将会按照可能性返回前k个位置 。在方程2中，基本任务是计算一定位置序列的次数，这些子序列发生在收集所有用户的位置序列。II-B节中我们将讨论，提供一个接口，用于私人回答，统计查询的目标是差分隐私,即后者保护隐私的理想候选位置的建议。

B.差分隐私

差分隐私被介绍给地址脆弱的易受背景知识的攻击的句法限制模型。这是一个语义模型,认为一个人应该最小化的风险披露,来自个人的参与数据集。差分隐私在统计的背景下制定总查询数据库。在空间数据库中,这可以归结为回答范围统计查询等，如“找到位置的数量封闭的地区”。虽然在理论上没有限制范围查询的形状,在实践中矩形是典型的查询方式。

用户和数据库之间的交互关系以转化的形式表现出来。形式上，

定义4（转化）：让成为一系列的统计查询，并用指示在数据集中回答的查询结果。转化式为：

，即完成了在数据集T中的查询。

如果不可分辨性条件被满足，则转化关系满足差分隐私。量化预期的隐私的参数：

定义5（不可分辨性条件）：考虑统计数据库产生mu;记录的查询，，并且让 gt;0为一个任意小实常数,记录mu;满足不可分辨性条件，如果每组数据集,,∣∣=∣∣，,只有个不同一记录

换句话说,攻击者不能获得重要的概率,是否记录查询设置在,能得的回答。要达到无法分辨，查分隐私要求随机噪声被添加到每个查询的结果。噪声的大小取决于隐私参数,设置查询的灵敏度,定义如下：

定义6（敏感度[11]）：假设有两个数据集,,∣∣=∣∣，,只有个不同一记录，敏感度的查询设置是测量

下面的定理为满足差分隐私[11]的数据发布提供了充分条件:

定理1：使为一组由一个统计数据库查询的应答，和表示中的敏感度。然后参数差分隐私可以通过增加每个查询结果随机噪声X。，X是独立的随机变量，从平均0级拉普拉斯分布绘制。执行差分隐私的一个基本操作是确定的灵敏度。在[11]中所示，是独立的数据集T。然而,对于任意的查询集,[17]所示,计算灵敏度是困难的。然而,灵敏度(或其近似)在计数查询中可以有效地计算:

1. 如果查询无重叠的范围，=2。
2. 如果查询有重叠的范围,那么2-近似的是由重叠的查询的最大数量的数据空间中同一点。

三、隐私位置的建议

可以从各种来源产生的位置数据中看出，如LBSN用户签到生成的位置数据，交通监视系统，地理标记介质等的记录。图1显示出预想结构，其中轨迹数据是在可信任仓库收集并根据差分隐私净化。对手可以从系统中获得了一系列建议，以暴露个人的入住图案的目的。该净化层的存在可以防止此类攻击。

我们考虑净化两种方法。首先（第三节-A）我们表示每个序列作为多维空间中的一个点，并申请隐私空间分解[12]净化技术。下一页（第三节-B）我们研究使用正克消毒技术，它可以直接处理顺序数据[18]。对于这种二元性的理由是，前一种方法可能短期入住历史表现良好，而后者更适合较长的历史。

1. 笛卡尔乘积入住的历史再现

我们代表每个位置序列由集中的所有入住的地点的笛卡尔乘积给出的空间多维点。入住位置是表示为唯一标签的离散对象，如“星巴克在百老汇和”。假设总共有八种可能签入的位置，，和用户三个入住序列：lt;gt;，lt;gt;，lt;gt;，lt;gt;。图2显示了序列如何在空间中表示。在这种情况下，为了便于说明，我们认为每个序列最多有两个位置。在一般情况下，表示空间是，其中是最大序列长度。

笛卡尔乘积表示可以让我们应用净化技术，专门为私人空间分解（PSD）设计的[12]提出。PSD构建的数据集的顶部嘈杂空间树索引结构，并发布这些索引中的内容。无论spacepartitioning或数据分区索引都可以使用。该索引建立完全基于从差异专用接口收到的嘈杂COUNT查询。该数据集是递归分裂，节点在树的所有级别的最小边界矩形（MBR）与他们的吵闹数目一起公布。

其中一个重要方面是隐私的预算分配。树索引有多个级别，和节点的空间范围涵盖了其同级范围的跨度。因此，存在出版计数之间的重叠。根据在第II-B所讨论的灵敏度特性，重叠需要也可以添加到每个查询答案更多的噪声。为了最大限度地减少重叠，PSD分解仅允许不引起相同的树层次内重叠，但只有在不同的层次索引的结构。它导致了在数据空间的每个点由恰好节点覆盖，或者等价，查询，其中是树索引高度。与由树高度所限定的重叠量，在PSD中使用的组查询的灵敏度建设等于，根据第二节-B。

如果是级的预算，则：

然而，并非所有的水平必须被授予隐私预算的相等部分。给定一个全球隐私预算约束，

一个挑战是在回答查询时，如何选择，以尽量减少精度误差。分配的选择取决于所用的结构的类型。此外，精度由树高的影响，随着越来越多的水平将在同一预算金额竞争。因此，为了决定分割停止状态，即在该高度停止延伸树是重要的。

根据[12]，给定一个随机矩形查询在数据空间域，一个封闭形式，平均的情况下，可配制用于索引节点的数目相交查询。另外，用表示在等级节点的相应编号以最大限度地贡献自己的计数到查询结果（即其范围完全被查询范围封闭）。所以，

为四叉树索引类型[19]，它在[12]中示出了

并且由求和树的整个高度

同样，对于KD树[19]，另一种流行的索引结构，。解决约束优化问题最大限度地减少了预期答疑错误受制于可用的最高预算。几何预算分配在树级别的选择被证明是最好的选择。即分配给树级预算应设置为：

与数据无关的分解：四叉树。

对于数据无关的分解，索引的结构不依赖于数据集。例如，在四树木[19]的情况下，每个分割递归当前分区的坐标上执行的中间。分区是总是正方形，并在树的相同深度的所有节点对应于相同的尺寸（因此，相同的面积或体积）的数据空间分区。因此，无关于数据的信息通过公布的树结构的结构被公开，因为它是完全独立于数据的。利用重叠导致分区。如果一个人认为每个索引分区是一个叶节点,作为查询的一部分的元素集,那么所有同级元素树重叠,导致常数敏感性较低价值2。这显然是一个理想的属性的索引。

在采用空间,利用由递归地将空间划分为两个子空间使用(dminus;1)维超平面。在二维空间中,对应于每一步选择一条线和分区空间基于这条线,直到满足特定的需求。在三维空间中,而不是线条,飞机是用来分割空间。选择分割超平面的启发式方法依赖于应用领域和停止条件。

每个分割发生在一个轴正交的超平面。轴是根据在其上被分裂的树节点的深度选择。具体地，如果节点n的深度表示为，分割超平面正交于轴部的,将空间分为两个相等的两半。让为整个利用索引查询一些数据集。由于分区区段的建立基于属性域,相当于一组计数的查询，每个叶子节点的程度。请注意，无论和?的分布，查询区域将是不相交的。因此,的敏感性是2级树的每一层。

基于数据分解：kd树

视数据索引的过程获得差分隐私版本的空间数据集则更为复杂,因为不仅个人计数器，而且树的结构在每个索引节点必须得到保护。一些额外的措施,如保护每个索引分裂的结果决定是必要的。

对于kd树[19],分割算法递归划分空间的中值在一个空间维度。而计算实际的值,则是使用差分隐私的指数机制[20]所决定的噪声。具体来说,数据集的每个元素分配一个绩效得分根据实际的距离值,和一个随机算法,选择一个元素根据这些绩效评分是用来选择一个添加了噪声的虚拟中值。 剩余内容已隐藏，支付完成后下载完整资料

资料编号：[30447]，资料为PDF文档或Word文档，PDF文档可免费转换为Word