基于差分隐私的个人轨迹信息保护机制

侯 尧，陶 洋，杨 理，熊 炼

重庆邮电大学 通信与信息工程学院，重庆400065

1 引言

随着智能手机的发展，获取用户位置提供相关服务的应用程序得到了快速发展。这些基于位置的应用程序其主要关注点之一是位置隐私[1-2]。要使用这些应用程序，用户必须将其位置提供给各自的服务提供商（或其他第三方）。这种位置泄露引起了严重的隐私问题，因为用户位置可能会受到攻击，使其接受不想要的基于位置的垃圾邮件、敲诈勒索，甚至是人身危险。

在过去的研究中，提出的大多数解决方案都是基于位置混淆，即泛化[3-4]（将轨迹上每个时刻的真实位置泛化到一个区域）、抑制[5-6]（根据真实位置所在区域的敏感程度有选择的抑制发布）或扰动[7-9]（对每个时刻的真实位置添加随机噪声生成扰乱位置）。大多数空间变换都依赖于语义上的隐私模型，比如k-匿名[10-11]，或是特定的不确定性模型，并且没有提供严格的隐私。为此，研究人员将广义的差分隐私概念引入了位置信息保护中，这是一个能够提供严格数学证明的隐私保护模型[12]。简单地来说，差分隐私意味着：一定距离内的任何两个位置进行扰动会产生相似的发布位置，因此攻击者无法知道用户的真实位置。

在本文中，给出了一种后置映射平面拉普拉斯机制。考虑一个具有敏感位置流的移动用户，该用户需要将位置提供给基于位置的应用程序（或其他第三方）。首先，根据每个位置设置的隐私级别生成扰动位置，再利用后置映射机制将生成的扰动位置映射到附近的位置，并使其服务质量损失最小。后置映射平面拉普拉斯机制可以在满足相同的隐私级别同时改善其平均服务质量。最后结合真实数据，对机制进行了仿真分析，证明了机制的服务质量损失低于平面拉普拉斯机制。

2 理论分析

2.1 差分隐私和空间不可区分

差分隐私[13]是统计数据库领域中的隐私概念。它的目标是在发布关于数据库的聚合信息时保护个人数据。差分隐私要求修改单个用户的数据对查询结果的影响可以忽略不计。空间不可区分的定义是基于广义的差分隐私，可以定义在任意一组位置集X 上，并配备一个度量d[14]。欧几里德距离度量d(x,x′)表示位置x和x′之间的可区分程度，距离小表示位置是不可区分的，距离大表示允许攻击者区分它们。

设Z 是提供给服务提供商的一组值，P(Z)表示Z 上的概率测量集。P(Z)上的乘法距离dP定义为：

机制被设计为概率函数K:X →P(Z)，在发布位置集Z 上分配每个真实位置x 的概率分布K(x)。差分隐私的广义变体，称为d-隐私，被定义为[4]：

定义1（d-隐私）机制K:X →P(Z)满足d-隐私，当且仅当：或等价于：

d 的选择不同产生的隐私概念也不同，并可以通过隐私参数ε 来缩放本文的度量。本文主要考虑位置隐私，在这种情况下，真实位置X 和发布位置Z 都是位置集合，K 是一种干扰机制。采用欧几里德距离度量d，得到的εd-隐私，称为ε-空间不可区分[12]。即当实际位置为x 时，与x 相距d(x,x′)的位置x′都发布位置z 的概率几乎相同，则这种机制提供了空间上的不可区分性。其中“几乎相同”表示概率的比率受exp(ε·d(x,x′)的约束，其中ε表示单位距离实现的不可区分的程度。两个位置越近，生成相同发布位置z 的概率应该越相似。通过K 机制，服务提供商无法准确推断用户的位置，但可以获得提供服务所需的近似信息。

从另外的角度来看，这个概念提供了用户在任意半径r 内的隐私，并具有与r 成正比的可区分性εr。因此，在较小的半径范围内，用户享有很强的隐私，而他的隐私会随着r 的增大而减小。此外，还可以灵活地在不同地点之间选择不同的度量标准，例如曼哈顿或基于地图的距离。文献[12]给出了两个特征结果，并详细地解释了空间不可区分。最后，通过在二维拉普拉斯分布中加入噪声来实现这一概念。在本文中，主要假设d 是欧几里德度量。

2.2 服务质量损失

实现位置隐私的常用方法是采用位置扰动机制，即概率函数K:X →P(Z)，其中X 是可能的位置集合，P(Z)表示Z 上的概率分布集合。K将位置x作为输入，并产生一个发布位置z，p(z|x)表示真实位置为x 发布位置z 的概率。

从用户的角度来看，希望量化由机制K 产生的服务质量损失（Service Quality Loss，SQL）。给出位置集X的先验概率P-和度量d，其P-可视为对用户的行为模型或攻击者获取的用户背景知识，d(x,z)表示真实位置x与发布位置z的质量损失度量，用于衡量发布z而不是x 时服务质量损失的程度。所以可以将服务质量损失定义为真实和发布位置之间的期望距离[15]，换句话说，服务提供商应该提供与其接收到的位置的准确性成比例的质量。故服务质量损失可以被定义为位置的先验概率和机制的条件概率的函数：

2.3 平面拉普拉斯机制

平面拉普拉斯机制是满足ε-空间不可区分的机制，这种机制是从以真实位置x 为中心的二维拉普拉斯分布中得出干扰位置。给定参数ε ∈R+，真实位置x ∈R2，在任意位置z ∈R2，机制的概率密度函数为：

其中，ε2/2π 是归一化因子。根据文献[12]中提出的将笛卡尔坐标系转换为极坐标系更方便计算上式，转换为极坐标后的形式为：

干扰位置z可以使用点(r,θ)来表示，r表示x与z之间的距离，θ是r与笛卡尔坐标系横坐标的夹角。根据文献[12]可推导出真实位置为x时满足“ε-空间不可区分”性质的干扰位置z的极坐标点(r,θ)的半径计算公式：

其中，W-1(x)函数表示朗伯W 函数的区间(-∞,-1)分支，ρ是服从[0，1]均匀分布的随机数。θ 是服从[0,2π]均匀分布的随机数。最后得出干扰位置z=x+(r·cos(θ),r·sin(θ))。

获得的位置z是对应于z周围的R2子集，由于R2具有对称性，故平面拉普拉斯机制采用欧几里德度量的服务质量损失与P-无关，对任意P-∈P(X)有SQL(K,P-)=2/ε。

3 发布机制

3.1 后置映射机制

显然，用户总是希望服务质量损失是最优的，即最小化服务质量损失，为此给出了一种后置映射的方法来达到目的。后置映射机制可以在满足相同的隐私级别同时改善其平均服务质量。空间不可区分要求x 附近的位置x′以相同的概率发布z，z 不必离x 很远。例如，靠近湖边的两个地点，使用平面拉普拉斯机制在所有方向上对称地增加噪声，则z 很有可能在湖中。现实中用户在湖中的概率很小，可以将其映射到湖的边缘，使其更接近真实位置。当然，如果用户确实在湖中，映射则会降低服务质量，但这种可能性很小，所以总体上可以改善服务质量。

给定机制K:X-P(Z)，真实位置为x，首先使用K 产生干扰位置z，然后使用后置映射函数M:Z →Z 将z 映射到新位置z*=M(z)，最后发布z*。

在Z ⊆Z 中，KM 发布观测位置的概率与K 发布观测位置的概率相同，则：

其中，M-1(Z)={z ∈Z:M(z)∈Z}。由此可以看出若K 满足εd-隐私，那么KM 也同样满足。

若后置映射M 对于所有其他后置映射M′有SQL(KM,P-)＜SQL(KM',P-)，则称M 为最优映射。可以通过后置映射实现其最优性，即选择出最小服务质量损失的位置z*。利用贝叶斯规则，将能从先验概率P-和机制K 得到后验概率P+∈P(x)，即：

若后置映射：

从上式易看出，对于所有z，z*∈Z

即：SQL(KM',P-)≥SQL(KM,P-) （11）

则式（11）为最优映射。

3.2 最优后置映射

后置映射第一步是计算后验，然后找到最小化服务质量损失的点z*∈Z。如果X，Z 是有限的，则可以使用公式（10）直接计算后置映射。

通过迭代所有Z 来找到最小化服务质量损失的点z*是不现实的，则可以通过仅考虑以z 为中心的某个圆Or(z)内的位置来近似映射，即用argmin z*∈Or(z)替代argmin z*∈Z。直观上来说，Or(z)包含的点越多（半径越大），服务质量损失越接近最小值，故其中半径r 可以选择为包含所有K(x)(Or(x))≥0.99 点圆的半径。

在许多情况下，用户希望能够灵活地将自己定位在平面上的任何位置，以及发布任意位置，因此可以将X，Z 看为完整的R2平面。此时Z 是连续的，则问题变得困难，因为即使在有界区域Or(z)中，仍然需要考虑许多不可忽略的点。

该情况下的首要问题是计算后验。虽然用户可能位于任何位置，但由于先验是过去访问服务的位置或兴趣点等一系列有限数据集构成的，所以可以假设能被构造的后验P+∈P(R2)也是有限的。尽管P+是有限的，但最小化服务质量损失的z*不一定是后验点中的位置，所以仍然有无数的z*候选者。

直观地，z*应该在有限后验P+之间的点，即在后验构成的凸包中。因此从几何角度来看，本文的问题转化为要在平面中找到一个点，该点到给定集合的加权距离最小，则该问题是位置理论中的韦伯问题。故对于欧几里德度量的情况，可以有效地构造最优z*。采用Weiszfeld算法解决，其迭代公式修改为：

用Weiszfeld(P+)表示其迭代结果，并可以设置一些停止条件（例如，当期望距离下降到ε 以下时，或者运行时间为1 s）。

经分析易知z*应该在有限后验P+构成的凸包中，且应该靠近质心附近，故为了更有效的计算，迭代公式中y0可以从质心开始，其质心的计算由公式（13）给出。

3.3 后置映射拉普拉斯机制

在R2平面上使用连续的先验概率是困难的，因此假设关于位置服务的先验概率信息采用以前使用的数据集形式提供，甚至以有关感兴趣点信息的形式提供。令Q ∈R2是一个可能性很大的有限位置集合，集合中每个q ∈Q 与权重w(q)＞0相关联。例如，Q 表示过去访问位置服务的位置集合，则w(q)表示该位置访问服务的用户数。或者Q 可以是与位置服务相关的兴趣点列表，其中w(q)表示捕获每个兴趣点的流行度。

给定平面拉普拉斯机制生成了干扰位置z，然后为了构造一个有限且合理的后验概率P+∈P(R2)，则需要将Q（可能非常大）限制在z周围的有限区域。本文设置r=C-1（0.99），其中C-1是平面拉普拉斯机制的半径累积分布函数的倒数，让Qr=Q ∩Or(z)。也就是说，平面拉普拉斯机制以99%的概率生成x 与r 之间的点，因此将z 重新映射到距z 不远的z*（即“附近位置”）是合理的。

注意，可以使用k-d 树的空间数据结构来地计算Qr。0.99阈值可用于转换效率以获得准确性，较小的值将导致较小的Qr，但可能导致最佳点位于区域之外。如果Q 密集，则可以使用预处理阶段来减小Qr的大小，将点合并为小群集，并将w(q)设置为群集的权重。

权重w(q)，q ∈Qr可以（在归一化之后）作为R2上的有限先验概率。采用贝叶斯定律（公式（9））和平面拉普拉斯的概率密度函数（公式（5））来计算先验概率，可以得出有限的后验P+：

最后，通过Weiszfeld(P+)计算后置映射的点z*。注意，实际上数据集Q 可能不够详细，无法为每个位置提供足够的信息。新用户可能在过去没有或很少有其他用户访问过的位置访问服务，此时认为映射的数据质量很低会降低用户的隐私，因此可以使用简单的启发式方法来评估数据的质量：如果Qr的大小（或者总重量）低于某个阈值qmin，那么就跳过重映射并直接报告z，整个机制发布数据的算法1如下所示。

算法1后置映射拉普拉斯机制

输入：x ∈R2，ε ＞0，qmin≥0，Q ⊂R2，w

输出：z*

1.通过平面拉普拉斯机制生成干扰位置z；

2.设r=C-1（0.99）；

3.计算Qr=Q ∩Or(z)；

4.if(|Qr|＜qmin)

5.z*=z；

6.else

7.通过公式（14）计算后验P+(x)；

8.z*=Weiszfeld(P+)；

9.end if；

10.return z*；

4 实验评估

对本文方法进行了实验评估。所有算法都在MATLAB上进行了测试，使用的是2.9 GHz英特尔i7 CPU和8 GB内存的PC 机。数据集使用Geolife 数据，Geolife 数据是通过182 位用户且超过三年时间所收集的真实数据。移动轨迹由一系列包含纬度、经度和时间戳的记录。提取了北京五环内的轨迹，证明了有效的后置映射可以不受感兴趣区域的任何限制。

为了保证所提出机制的可用性，将训练和评估数据分开。更准确地说，将整个位置数据集分成两个不重叠的部分。第一部分包含了大约80%用户的位置数据，作为训练集。在这一部分中，构造出了一个全局先验，作为访问该区域所有用户的个体先验概率的平均值，然后将其用于后置映射机制得到最优服务质量损失的位置。请注意，此后置映射是针对全局先验优化的，而不是针对特定用户的。

数据集的另一部分，包含其余20%用户的数据，被看作是评估机制的测试集。更准确地说，为至少20 个用户构造了一个用户专用的先验，并度量用户使用自己的先验时机制的服务质量损失。虽然机制只针对数据集训练部分的用户进行了训练，但是发现它们也为测试集的用户提供了较低的服务质量损失。

注意，分割是对用户执行的：训练数据集中没有测试用户的任何数据。这种非常保守的方法旨在模拟一个新用户的情况，对于这个新用户，除了关于整个服务的一般可用信息之外，没有其他任何信息。在这种情况下，改善服务质量损失是一个强有力的结果；显然，如果对用户自己的部分数据进行训练，结果可以得到进一步的大幅度改进。

所有的评估机制都是为了满足ε-空间不可区分而构造的，使用ε=l/r，其中r=0.1 km，且l 的范围为ln（1.4）到ln（2.6）。同时评估平面拉普拉斯机制本身和后置映射拉普拉斯机制。数据集Q 是由48 000 用户和超过5 MB的访问服务位置点组成的训练集。在访问服务位置点列表中，构造了一个k-d 树，可以快速构建Qr，为了避免单个用户对后验产生较大影响，取w(x)=1/u，其中u为该用户在Qr中的访问服务次数，并设置qmin=20。在实验评估中，尽管数据集很大，但每次映射只需要几毫秒。机制在12 000 用户的整个测试数据集中对这两种机制进行了实验评估。

图1 显示了不同l 值下各用户平均的服务质量损失。注意，平面拉普拉斯机制的平均服务质量损失总是相同的为2/ε。另一方面，使用后置映射时的平均服务质量损失取决于用户：由于映射是使用全局先验概率计算的，因此它可能并不总是能够提供改进。不过，虽然没有使用用户数据进行训练，但实验评价表明，大多数用户的服务质量损失有很大的改善。ln（1.4）的结果表明，后置映射拉普拉斯机制的平均服务质量损失为499 m，而平面拉普拉斯机制的平均服务质量损失为594.4 m，高出19%。

图1 隐私级别l对SQL的影响

图2 显示了图1 中l=ln（1.4）时的100 个时间戳测试数据，由图可以看出并不是所有用户的服务质量损失都能被改善，但是只有8.17%的用户服务质量损失有所增加，其中仅有1.27%的用户服务质量损失增加了10%（59.4 m）或更多。

图2 轨迹的SQL

5 结束语

在本文中，提出了一种后置映射平面拉普拉斯机制。考虑一个具有敏感位置流的移动用户，该用户需要将位置提供给基于位置的应用程序。首先，根据每个位置设置的隐私级别生成扰动位置，然后利用后置映射机制将生成的扰动位置映射到附近的位置，并使其服务质量损失最小。后置映射平面拉普拉斯机制可以在满足相同的隐私级别同时改善其平均服务质量。最后结合真实数据，对机制进行了仿真分析，结果显示机制的服务质量损失低于平面拉普拉斯机制。