结合四叉树划分的差分隐私位置发布算法

王 辉，廉芳芳，申自浩

(河南理工大学 计算机科学与技术学院，河南 焦作 454002)

1 引 言

近年来，基于位置的服务(Location-based Service，LBS)给人们带来了极大的便利，但是随着互联网、移动终端和定位技术的不断发展，通过社交网络平台进行交流的用户迅速增长，导致社交网络积累用户行为的数据库不断扩大，其中包括了用户的敏感信息，比如家庭住址、身份证号等，这些敏感信息一旦被不法分子获取，那么会对用户的利益构成极大的威胁[1].例如，2018年5月，美国软件公司AgentRun意外暴露了成千上万保单持有人的个人敏感信息，而究其原因是因为一个未加密的Amazon S3储存桶，该储存桶包含了大量的缓存数据，涉及数千名不同保险公司的个人敏感信息，包括类似Cigna和SafeCom-Insurance这样的大型保险公司的客户，遭泄露的信息包括保险单文件、健康和医疗信息、各种证件的扫描件以及一些财务数据，而一些文件除了显示收入范围、种族和婚姻情况以外，甚至还附有空白的银行支票，使得用户的财产安全遭到了严重威胁.因此，如何使用户在确保敏感信息不被泄露的同时，正常使用社交网络平台是当前亟待解决的问题.

传统的位置隐私保护技术大多基于k-匿名[2-5]、l-多样性[6]和t-紧密型[7]，但其忽略了攻击者对已知背景知识的掌握以及人口分布密度等的影响，从而不能充分保护LBS隐私安全.针对此问题，本文提出一种基于差分隐私[8-10]的位置发布算法，该算法使得数据集的计算结果对元素的变化不敏感，并将因为数据集的加入而导致的隐私泄露风险控制在可接受的范围中，从而为用户提供更好的位置服务.本文在位置点数量、位置点稀疏程度等方面进行实验分析，证明本算法在隐私预算相同的前提下，有效的提高了对位置隐私的保护程度.

本文各个章节安排如下：第2节主要介绍常见的位置隐私保护算法；第3节对差分隐私相关问题进行定义；第4节提出了一种基于四叉树划分的差分隐私位置发布算法；第5节阐述实验评估的结果；最后总结全文并展望未来相关研究工作.

2 相关工作

差分隐私[11，12]应用随机算法对真实位置添加噪声，生成的发布位置被验证是有效的.目前差分隐私的研究主要分为设计满足差分隐私的算法和减少差分隐私噪声量.Li等人[13]针对用户个性化偏好，提出了基于个性化的算法来构建用户兴趣区，但是利用该算法构建的用户兴趣区的隐私保护程度偏低；Yan等人[14]提出了一种基于差分隐私和关联规则的用户需求隐私保护框架，这些算法加强了对用户隐私的保护，但是却忽略用户区内位置差异对隐私保护的影响.Li等人[15]利用分类树及其算法将数据进行融合，实现了数据的分级化，但是该方法需要合理分配差分隐私预算，不仅会增加算法的运行时间，且当隐私预算分配不合理时，会导致查询误差的增加；Qardaji等人[16]通过迭代算法往树中添加噪声，虽然降低了查询误差，但是忽略了一些层次不满足一致性约束的情况；Huo等人[17]针对若干种空间索引结构设计了满足差分隐私的算法，但是没有考虑对空间结构中噪声的注入量.

针对上述算法的相关缺陷，本文提出了一种基于用户兴趣区的位置差分隐私发布算法DPLIP，该算法在兴趣区中发布位置时，通过结合四叉树的特性既考虑位置点数量对噪声添加量的影响，也考虑位置点稀疏程度对噪声添加量的影响.

3 问题定义

差分隐私的基本思想是对原始数据、原始数据上的函数以及查询结果所构成的数据集中添加干扰噪声来达到隐私保护的目的.差分隐私算法通常是在相邻数据集概念的基础上完成的，该算法能够保证对相邻数据集进行插入或删除一条记录的操作后，其产生同一结果的概率的比值接近于1.

定义1.相邻数据集.给定两个数据集A和B，其中A={ai：i=1，2，…，n}，B={bi：i=1，2，…，n}，当A和B满足结构相同，有且仅有一条数据不相同时，则称A和B为相邻数据集，如式(1)所示.

A∪B={a1，a2，…ai，…，an，bi}，i=1，2，…，n

(1)

定义2.ε-差分隐私.给定相邻数据集A和B，q是A和B上的随机查询算法，算法q在数据集A和B上任意输出的结果为Z，若满足式(2)，则称算法q满足ε-差分隐私.

(2)

其中，ε表示单位距离的隐私预算，表示隐私保护程度，且其越小越说明隐私保护程度越高.当ε→0时，隐私保护程度越高，说明两个数据集的输出结果越接近.

定义3.位置敏感度.假设任意函数q，其输入为数据集A和B，输出为d维实数向量，对于任意数据集A和B，有：

Δq=maxA，B‖q(A)-q(B)‖

(3)

Δq表示函数q的位置敏感度，表示加躁后对数据查询的影响.q(A)-q(B)表示q(A)和q(B)之间的曼哈顿距离.注意，敏感度与数据集无关，只和查询结果相关.

本文在对区域划分方面采用的是基于四叉树的划分方法，区域划分的程度取决于以下函数的相对权重值.

定义4.权重函数.在四叉树中，假设每个节点表示为e(key，parent)，该节点的父节点表示为parent(Key，Sub)，则该节点的权重表示如下：

(4)

其中，key表示每个节点的权，即所在区域的位置点数 量；Key表示父节点的权，即父节点所在区域的位置点的数量.

对兴趣区进行划分后，需要在每个区域中添加噪声以达到对真实位置的扰乱效果，在选择扰乱算法时引入距离函数这个概念，定义如下：

定义5.距离函数.假设二维平面上的n个位置对象K=oi(xi，yi)：i=1，2，…，n，则任意两点之间的距离可表示为：

(5)

其中，o1·x表示点o1的横坐标o1·y，点o1的纵坐标；o2·x点o2的横坐标，o2·y点o2的纵坐标.

4 位置差分隐私发布算法

4.1 独立扰乱发布算法

Laplace机制是实现差分隐私保护最基础的噪声机制之一，该机制向返回结果中添加服从Laplace分布的随机噪声，使得结果满足差分隐私，适合于对数值型数据的保护.

定理1.Laplace扰动[18].对于数据集A上任意函数q，若算法D的输出结果满足式(6)，则算法D满足ε-差分隐私.

(6)

其中，Lap(Δq/ε)d表示添加的Laplace噪声，噪声变量与位置敏感度成正比，与隐私预算ε成反比.

在二维空间中，不可直接使用上述公式添加噪声，本文给出了在单个位置的情况下，为满足ε-差分隐私需要添加噪声的概率函数.

假设真实位置集合为A，当添加噪音后的扰乱位置集合B中的元素满足式(7)，则满足ε-差分隐私.

(7)

其中，Pr[D(a)=b]表示真实位置a添加噪音后的位置是b的概率.当ε一定时，从式(7)可看出，Pr[D(a)=b]只与a和b之间的距离有关，并且Pr[D(a)=b]随着两者距离的增大而减小.

为了简化表示，可以采用极坐标函数来实现，表示如下：

(8)

其中dist(a，b)表示a和b之间的距离，α表示a在极坐标下和极轴之间的夹角.

为了方便求解，将公式(8)分解到距离dist(a，b)和角度α上得到公式如下：

(9)

(10)

根据以上公式可以对真实位置集合A中通过添加噪音并生成随机的扰乱位置集合B，以此达到位置隐私保护的目的，其中B{bi=ai+[dist(a，b)cosα，diat(a，b)sinα]}.

独立扰乱算法是对真实位置A中每个位置分别添加Laplace噪声，该算法满足ε-差分隐私，其隐私保护程度是每个位置的隐私保护预算之和.当真实位置数量较少，且真实位置之间相距较远时，本节提出的加躁算法效果比较理想，但其隐私保护程度会随着集合中位置数量的增加而降低，且满足ε-地理不可区分性[19]，即距离真实位置越近的扰乱位置越容易被发布.当真实位置距离较近且过多时，隐私程度会降低.

4.2 质心扰乱发布算法

本节通过对多边形模型的质心添加噪声的方法来解决上述问题，该模型的思想是：首先将受保护的点与其周边符合要求的点组成多边形，其次利用质心公式计算出其质心坐标，最后利用独立扰乱算法的方式对其添加噪声.

假设某用户的轨迹图中位置集合F表示受保护的位置点，位置集合A表示用户历史位置点的二维信息，将位置集合A中用户访问次数大于m的点加入到待定集合H中.

针对这些位置点，根据算法用受保护的点fi(xi，yi)(i=1，2，…，n)和从待定集合H随机选取的点hi(xi，yi)(i=1，2，…，n)构成多边形，并计算出其质心，质心I(x，y)的计算公式如式(11)所示.图1以三角形为例.

图1 构建三角形求解质心

(11)

在构造多边形时，假设以受保护点fi(xi，yi)(i=1，2，…，n)为圆心，以R为半径画圆，构造多边形的位置点应该落在圆中.需要注意的是R的值不宜过小，否则生成的多边形的范围过小，起不到模糊真实位置的作用.R值也不宜过大，否则会降低隐私保护程度.故需要设置Rmax和Rmin，则:

Rmax≤R≤Rmin

(12)

根据上文所讲的方法，求得受保护位置点的集合H所对应的质心集合M，然后再通过Laplace算法对每个质点添加噪音，将所得结果加入数据库C中.

4.3 位置差分隐私发布算法DPLIP

假设用户兴趣区是以r为边长的正方形.当通过扰乱算法D生成的扰乱位置b在用户兴趣区内时，则将b添加到数据库C中；当通过扰乱算法D生成的扰乱位置b不在用户兴趣区内时，则使用映射函数将b投影到兴趣区上，并将投影所得的点添加到数据库C中.

某一时刻，已知先验概率P(t)-(a)和扰乱算法D，求解其后验概率P(t)+(a).根据贝叶斯公式有：

(13)

则映射函数F表示如下：

(14)

基于用户背景知识可知，在用户兴趣区中，用户不是单一的在某个区域活动.当用户频繁访问的位置点相距不近或者数量不多时，使用独立扰乱算法的隐私保护程度较高；但是当访问的位置点相距较近或者数量过多时，使用质心扰乱算法优于独立扰乱算法.针对上述问题，本节提出了一种结合四叉树划分的差分隐私位置发布算法，该算法通过引入相对权重阈值δ和稀疏程度阈值ϑ，将独立扰乱算法和质心扰乱算法有效的结合在一起，从而加强对位置隐私的保护.

四叉树的思想是将地理空间递归划分为不同层次的树结构.它将已知范围的空间等分成4个相等的子空间，如此递归下去，直到树的层次达到一定深度或者满足某种要求后停止分割，如图2(a)所示.传统方法使用的是完全四叉树，虽然其易于实现差分隐私分析，但是当时位置分布不均衡时，该方法会因为四叉树高度过大造成大量的空节点的产生，导致总体注入过多噪声.本文设计一种依据相对权重的四叉树分裂方法，有效的减少了噪声的注入.

图2 基于四叉树权重的区域划分方法

第1步.根据定义4可以计算出。叉树中各个节点的权重；

由于对区域的每次划分所生成的孩子节点的下标和其父节点的下标都有关联，故对节点下标情况做以下定义：状态i表示所求节点对应的父节点的下标；状态ij表示状态为i的节点的子节点的下标，其中j=1，2，3，4.

第2步.计算每个区域相对兴趣区的权重，计算如下：

W[e]=wij[e]×W[parent]，1≤j≤4

(13)

其中，wij[e]表示所求区域的权重.

第3步.将第2步计算结果和δ进行比较，结果如下：

(16)

其中，Divide表示区域划分，True表示继续划分，False表示停止划分，δ表示相对权重的阈值，当δ=1/6时，区域划分情况如图2(b)所示.

这就证明了满足ESCA2的最优分配方法应该将剩余资源优先分给指标(s-Ai(s))/pi最大的部门即Rdam(s)法.注意到指标(s-Ai(s))/pi满足Ax.7，所以时不变永久性离散资源分配的最优方法是Rdam(s)法.

第4步.以此类推，直到整个兴趣区不能再被划分为止

接下来的关键问题就是如何为每个区域选择合适的扰乱算法.设V1=v1t：i=1，2，…，m，则该区域稀疏程度计算如下：

(17)

(18)

根据上述推导公式，可以计算出整个区域划分情况.针对每个区域真实位置点分布情况，利用式(18)计算出其稀疏程度Si(i=1，2，…，n)，将其与稀疏程度阈值ϑ进行比较，当前者小时，使用独立扰乱算法，否则使用质心扰乱算法，从而使加躁后产生的扰乱误差尽可能降低.

下面给出位置差分隐私发布算法DPLIP的主要流程.

1)建立以r为边长的正方形作为用户兴趣区；

2)根据四叉树思想将用户兴趣区划分为若干个小区域，通过权重阈值δ来控制四叉树分裂情况.

3)由式(17)和式(18)计算每个区域所对应的稀疏程度Si(i=1，2，…，n)，将其与稀疏程度阈值ϑ进行比较，根据比较结果来进行扰乱算法选择，将计算出的扰乱位置放入数据库C中；

4)对于落到兴趣区外的扰乱位置，利用式(14)将其映射到兴趣区中，并将映射结果添加到数据库C中；

5)将真实位置A添加到数据库C中，然后从数据库C中随机挑选若干位置点作为发布位置Z.

结合四叉树划分的差分隐私发布算法的整体算法如下：

算法.位置差分隐私发布算法DPLIP

输入：真实位置集合A，兴趣区边长r，t时刻前非兴趣区的先验概率P(t)-，差分隐私预算ε，Rmax，Rmin，相对权重阈值δ，稀疏程度阈值ϑ

输出：发布位置Z

1. nshoCount=Initialize()；

2. fornshoCount>δ；

3. Recursion(e)；//迭代划分区域

4. end for

5. 计算Si；//式(18)

6. ifSi>ϑ THEN

7. D=Choose(0)；//0表示独立扰乱算法

8. else：

9. D=Choose(1)；//1表示质心扰乱算法

10. C_in=Disturbed(D)；

11. P(t)+=ChooseLoc(P(t)-)；//式(15)

12. C_out←CalRelease(P(t)+)；

13. C←(C_in∪C_out∪A)；

14. Z=RandomChoose(C)；

15. return Z；

4.4 误差分析

独立扰乱算法总误差为每个真实位置添加的噪声之和.假设每个位置消耗的隐私预算为ε，那么每个位置添加的噪声的期望是E[dist(a，b)]i(i=1，2，…，n)，则：

(19)

由式(19)可知，独立扰乱算法的总误差是：

(20)

质心扰乱算法的总误差除了考虑对质心添加噪音时造成的误差，还要考虑真实位置和所求质心之间的误差.假设每个位置消耗的隐私预算为ε，但实际上每个位置消耗的隐私预算为ε′/n，则对质心添加的误差为Es[dist(a，b)]=2/n2ε，1≤s≤m，那么质心扰乱算法的总误差是：

(21)

DPLIP算法是一种根据相对权重阈值δ和稀疏程度阈值ϑ将独立扰乱算法和质心扰乱算法结合在一起的算法，故总误差是：

(22)

5 实验与分析

将结合四叉树划分的差分隐私位置发布算法(DPLIP)、不规则线段树的差分隐私位置保护方法(ISTDP)[20]以及对提高差分隐私查询精度有代表性的哈尔小波零树压缩算法(EH-WT-DP)[21]进行对比实验.针对相同隐私预算的条件下，主要从位置稀疏程度以及位置点数量等方面评估算法查询的准确性以及算法运行效率.

5.1 实验设置

DPLIP算法均采用MATLAB实现，实验环境是8.00GB RAM的Windows7操作系统和3.60GHzCPU.本章实验采用的数据集是landmark和storage真实数据集，其中前者是infochimps大数据网站提供的美国48个大州的地理坐标组成的地标，约880k个数据点；后者是美国存储设施位置数据，数据点较稀疏，大约1万个数据点.

5.2 不同位置稀疏程度下查询误差的变化

实验设定ε=1，稀疏程度取1-13，针对不同位置稀疏程度的landmark数据集和storage数据集，测试DPLIP、ISTDP以及EHWT-DP共3种算法查询误差的对比，实验结果如图3所示.

图3 不同位置稀疏程度下的误差

由图3(a)可以看出，EHWT-DP算法的总误差最大，位置可用性最低，即位置安全性最低，这是因为EHWT-DP受位置稀疏程度影响较大；ISTDP算法的总误差波动幅度不大，基本上呈现缓慢增长的趋势，其位置可用性最好，这是因为该算法在隐私预算相同时，基本上不受位置稀疏程度的影响，因此其查询精度更佳，误差最小且波动幅度不大；本文的DPLIP算法介于两个算法之间，并接近ISTDP算法的表现，这是因为该算法结合了独立扰乱发布算法和质心扰乱发布算法，所以会受到位置稀疏程度的影响，所以位置可用性略低于ISTDP算法.图3(b)在landmark数据集上显示类似的结果.同时，3种算法在storage数据集上的表现优于landmark数据集上的表现，原因是storage的数据分布较密集，landmark的数据分布较稀疏，故前者的总误差小于后者.

5.3 不同位置点数量下查询误差的变化

除了位置稀疏程度对3种算法有影响以外，位置点数量也是影响误差的重要因素，本文通过实验分析位置点数量对3种算法总误差的影响.实验设定ε=1，稀疏程度为2，实验结果如图4所示.

图4 不同位置点数量下的误差

从图4(a)中可以看出随着位置点的增加，3种算法的总误差也随之增加，其中，EHWT-DP算法的增幅最大，原因是该算法的单个位置点的查询误差较大，因此随着位置点的增加，总误差会呈线性增长；DPLIP算法和ISTDP算法由于单个位置的查询误差较小，故总误差的增长幅度较小于EHWT-DP算法，同时由于本文的DPLIP算法中引入了质心扰乱发布算法，减少了噪声的注入量，故该算法较优于ISTDP算法.图4(b)在landmark数据集上显示相似的结果.

5.4 算法运行效率的比较

该实验在storage数据集和landmark数据集中进行，实验设定n=200，稀疏程度为2，对比DPLIP算法、EHWT-DP算法和ISTDP算法的运行时间，结果如图5所示.

图5 算法运行时间

从图5中可以看出，DPLIP算法和ISTDP算法的运行时间相近，这是因为这两种算法是基于树形结构的改进，仅和位置集合n相关，区域的网格划分是在离线环境下进行的，所以运行时间较EHWT-DP算法少.DPLIP算法的运行效率并没有比ISTDP算法的运行效率有明显提高，但是对比EHWT-DP算法则提高很多.

6 总 结

本文提出的基于用户兴趣区的差分隐私保护算法的核心是在传统的位置扰乱的基础上，引入相对权重阈值和稀疏程度阈值，并提出一种基于用户兴趣区的位置差分隐私发布算法以及相应的算法DPLIP.该算法首先利用四叉树的思想对用户兴趣区进行划分；然后对划分后的区域进行稀疏程度判断；最后根据稀疏程度进行扰乱算法选择.该算法相较于传统的算法，既考虑位置点数量的大小对发布位置产生的影响，又考虑位置点稀疏程度对位置发布造成的影响，本文设计的算法有效的减少了添加噪声后的扰乱位置与真实位置之间的总误差.

对实验结果进行分析与比较后，证明了在相同隐私预算的条件下，有效的减少了噪声的添加量，从而保证用户的隐私信息不被泄露.今后的研究中可继续对DPLIP算法进行优化，以减少算法的运行时间和扰乱位置发布的可用性，更好地应用到位置发布服务中.