开放科学(资源服务)标志码(OSID)：

0 概述

随着信息技术的快速发展，移动互联、社交网络、电子商务等热门应用收集了大量用户数据，这些数据常被用于研究人类行为、改善交通检测、进行位置感知推荐等方面，给人们的日常生活带来极大便利。然而，在大数据时代，数据挖掘和分析技术快速发展，用户的隐私数据很容易遭受攻击和泄露，用户的位置信息泄露会对个人隐私造成严重影响，因此，确保用户的位置隐私安全在数据统计分析中尤为重要。几乎所有的数据统计分析任务都依赖于对数据分布的理解，例如，在空间众包^[1]中，根据一定区域内的工人数量进行任务分配^[2]，通过记录用户位置^[3]呈现人群密度图，许多基于位置的应用程序利用用户的区域计数来优化实际问题。因此，在收集和发布用户位置数据时，如何有效地平衡数据隐私和数据可用性之间的关系成为目前亟待解决的难题^[4]。

DWORK^[5]提出一种差分隐私模型，为敌手在任意背景知识下的攻击提供有力保护，其为一种强健的隐私保护模型。传统的中心化差分隐私模型需要可信第三方数据收集中心来收集用户的原始数据，用户无法掌控自己的数据隐私，提高了个人隐私泄露风险，且互联网时代大众的隐私意识日益增强，用户可能不愿意与数据收集者共享私人数据，从而限制了差分隐私的应用。而本地差分隐私模型将数据隐私化的工作转移给每个用户，用户的信息经过自身设备的隐私处理后分享给其他人，避免在收集用户信息过程中第三方数据收集中心窃取或泄露用户隐私。谷歌、苹果、微软等公司已经基于本地差分隐私模型，在大规模数据域内对用户的私人数据进行了频率估计。

与中心化差分隐私模型相比，本地差分隐私模型具有强大的隐私保护性能，同时也会造成更大的误差。本地差分隐私下的非均匀空间数据发布存在如下挑战：在本地化设置中，数据收集者无法收集到用户的真实位置数据，传统方法将整个待发布位置区域均匀划分，而大规模位置空间划分值域通常较大，导致通信代价较高；对于非均匀空间位置数据，均匀划分方法导致数据采集误差较大，合适的数据空间划分方法能够有效提高发布数据查询结果的精度，在本地化差分隐私场景下，需要设计高效精确的自适应划分方法；在本地化设置中，差分隐私预算分割将产生极大的噪声误差，需要减少隐私预算分割，降低在本地差分隐私模型下采集数据的误差。

本文研究本地差分隐私模型下空间数据的采集和发布问题，提出一种空间数据分层自适应划分方法。分维度统计少量用户的扰动位置信息并结合KD-树划分思想初步划分位置空间，然后划分多层数据空间，在此过程中采用抽样技术对用户进行分组，利用分组用户统计结果所提供的先验知识，采取不同的划分粒度来对不同分布密度的数据空间进行高质量的空间划分。具体地，本文提出一种自适应树划分方法对位置空间进行多层划分，该方法以用户在不同节点的统计数为先验知识，通过阈值判断分割策略、重构树结构解决空间划分值域较大的问题。在本地化差分隐私条件下，分维度统计用户的扰动位置信息，利用少量用户的位置扰动信息估计空间区域密集程度，并结合KD-树划分思想初步划分位置空间，以降低位置空间划分值域和数据采集误差。针对本地差分隐私模型下由隐私预算分割造成的数据可用性低的问题，提出一种基于用户集合采样的层次划分方法，将用户随机分为多个不相交的子集，以有效解决隐私预算分配次数过多的问题并降低差分隐私噪声。

1 相关工作

隐私数据发布面临的主要挑战是如何设计一种差分隐私机制，在保护用户隐私的同时提高查询结果的准确性。位置空间数据^[6]是一组有序的数值，在差分隐私模型下处理位置空间数据需要将一个范围的值作为一个分类值，而分类粒度既取决于隐私参数，又取决于数据的分布，在这种方式下选择合适的分类粒度对于发布数据的精确度具有很大影响。在中心化差分隐私中，已经有很多国内外学者对隐私空间的划分做了突破性研究。

CORMODE等^[7]提出隐私空间划分(Private Spatial Decomposition，PSD)的概念，其基本思想是：基于空间索引结构将数据区域划分为互不相交的区块，其中，每个节点表示划分的区块范围，然后发布每个节点中的计数或频率。QARDAJI等^[8]提出基于网格的分区策略，该策略将数据区域均匀地划分为等宽的单元格，为每个单元格计数添加拉普拉斯噪声，这种划分没有考虑空间数据具体的分布情况。针对空间数据分布的不均匀性，文献[8]提出一种空间数据的自适应划分策略，其基本思想是：在稀疏区域进行粗粒度划分，在稠密区域进行细粒度划分，然后根据2种粒度的划分区块计数，响应范围查询计数。文献[9]根据完全四分树结构划分数据域，发布各层节点的信息和噪声计数来响应范围查询，但在偏斜的数据集中，其划分的节点不平衡，这对于查询回答而言效果并不理想。

划分数据区域通常分为数据独立和数据依赖2类方法，均匀网格划分和完全四分树划分方法属于数据独立的方法，划分区域不依赖于数据点的数量或分布，而在实际数据集应用中，数据可用性和效率并不理想，因此，学者们开始对数据依赖的划分方法进行研究。INAN等^[10]提出基于KD-树的数据依赖结构划分数据空间，但其需要利用指数机制^[11]保护每一层次的分割线，划分层次较高时隐私预算耗费很大。文献[12]提出一种基于稀疏向量技术的KD-树空间分割方法，该方法通过稀疏向量技术判断是否分割树节点，从而控制节点的噪音值。上述研究都是在有可信第三方数据收集中心的前提下，采用拉普拉斯机制对计数值进行扰动，无法在本地差分隐私模型中直接应用。

本地差分隐私常被用于解决统计分析任务中用户的隐私问题。Google^[13]提出的RAPPOR方法利用Bloom Filter技术和随机响应技术扰动数据，其为频数估计中的经典算法，已经被谷歌Chrome用于收集用户的使用数据，但其通信代价较大。KAIROUZ等^[14]提出的o-rappor方法应用哈希映射和分组技术，针对属性域没有先验知识的情况对用户隐私数据进行频数统计。BASSILY等^[15]提出的S-Hist方法针对分类型数据，使用柱状图列出数据中最频繁出现的项目及其频率估计数，这种方法基于随机矩阵投影技术从编码向量中随机选取一个比特，有效降低了通信代价。文献[16]利用随机响应方法解决分组无关问题模型存在的隐私泄露问题。文献[17]提出一种数值域离散化的方法，用于解决本地差分隐私下数据域密度估计问题，表明利用域的数值特性有利于平衡数据的实用性和隐私性。文献[18]提出本地差分隐私模型下的多维数据分类机制，其对数据的不同维度分别设置隐私预算，但是无法保证数据的可用性。

上述本地差分隐私模型下的频率估计方法多用于一维数据，目前对于二维空间数据的发布还存在不足。文献[19]提出一种室内定点采集人口统计数据的方法，用于估计室内区域的密度，但其应用范围较窄，且对于分布不均的数据集误差较大，难以适用于大规模区域数据的采集和发布。张啸剑等^[20]提出一种空间范围查询方法，首先采用四分树索引均匀划分网格，数据扰动过程采用层次随机抽样的方法，该方法能够有效降低通信代价，但无法根据数据集的分布自适应地划分区域。文献[5]基于随机映射矩阵提出PCE方法，用户可以根据自身需求进行个性化隐私设置，并统计不同区域中的用户数。霍峥等^[21]提出一种位置数据众包采集方法，其通过构造维诺图对路网空间进行分割，但该方法仍然是与数据分布无关的划分方法，空间范围查询精确性较低。

综上，在中心化差分隐私中通常根据真实数据集的分布情况来自适应划分数据空间，然而，在本地差分隐私场景下无法获得真实数据，因此，中心化差分隐私中的划分方式不能直接应用于本地差分隐私。目前，基于本地差分隐私的二维空间数据发布方法主要是在数据域上设置等宽的网格^[19]，或者在数据域上构造层次均匀的分区结构^[20]，这些方法无法针对偏斜和非均匀数据集进行划分，导致稀疏区域产生大量空节点，大幅增加了噪声误差，而稠密区域划分不充分，容易产生较大的均匀假设误差。为了解决上述问题，本文提出一种基于本地差分隐私的空间数据分层自适应划分算法KDG-HT，目的是使数据收集者能够估计输入数据的分布情况，从而确定合适的划分粒度。

2 相关定义与问题描述 2.1 本地差分隐私

传统的差分隐私技术假设存在一个受信任的数据收集者，负责收集用户的私人信息，并通过扰动算法发布信息。然而在实际中，很难找到让用户信任并愿意共享私人信息的数据收集中心，本地差分隐私不假设用户彼此之间存在任何信任，用户彼此间不通信，每个用户通过一个扰动算法独立发布自己的信息。

定义1(本地差分隐私^[13])    给定随机算法A及其输出域O，对于用户端的所有数据对$ {v}_{i} $和$ {v}_{j} $，随机算法A满足本地差分隐私当且仅当：

$ \frac{\mathrm{P}\mathrm{r}\left[A\right({v}_{i}=O\left)\right]}{\mathrm{P}\mathrm{r}\left[A\right({v}_{j}=O\left)\right]}\le {\mathrm{e}}^{\epsilon } $

(1)

其中：$ \epsilon $为隐私预算，$ \epsilon $值越小，算法对用户的隐私保护程度越高。式(1)表明，通过观测算法的输出无法判断输入值是$ {v}_{i} $还是$ {v}_{j} $。

随机响应技术^[22]是实现LDP的经典方法，它的主要思想是通过对敏感问题响应的不确定性来保护用户的隐私信息，即用户以p的概率翻转它来给出真实答案，以1-p的概率给出其他答案，用户不再需要信任任何中间数据收集者。例如，数据收集器要计算N个用户中吸烟者的比例，于是对N个用户提出问题：“你吸烟吗？”用户的回答有“是”和“否”2种，为了保护隐私，每个用户投掷一枚非均匀硬币，出现正面的概率是p，出现反面的概率是1-p，用户抛出硬币，若出现正面，则回答真实答案，否则，回答相反的答案。

定理1(序列组合性^[23])    给定数据集D和n个随机算法$ \left\{{A}_{1}, {A}_{2}, \cdots , {A}_{n}\right\} $，将满足$ {\epsilon }_{i} $-差分隐私的多个算法$ {A}_{i} $进行序列组合，从而满足$ \epsilon $-差分隐私，其中，$ \epsilon =\sum\limits_{i=1}^{n}{\epsilon }_{i} $。

定理2(并行组合性^[23])    将给定的数据集D划分为若干不相交的子集$ \left\{{D}_{1}, {D}_{2}, \cdots , {D}_{n}\right\} $，A为满足$ \mathrm{\epsilon } $-差分隐私的任一随机算法，则算法A在$ \left\{{D}_{1}, {D}_{2}, \cdots , {D}_{n}\right\} $上的系列操作满足$ \epsilon $-差分隐私。

本地差分隐私与中心化差分隐私都具有序列组合性和并行组合性^[23]。定理1序列组合性表明有一个算法序列同时作用在一个数据集上时，最终的差分隐私预算等于算法序列中所有算法的预算之和^[24]，AG方法以及大多数树结构等中心化差分隐私保护方法都应用了这一性质。并行组合性表明，在数据集的不相交子集上应用满足$ \epsilon $-差分隐私的算法，最终的差分隐私预算仍然为$ \epsilon $，本文正是利用这一性质对空间数据实现本地差分隐私保护。

2.2 KD-树空间分割

KD-树是在K维空间中对数据集进行分割的一种二叉树结构，通过指定划分维度$ {d}_{i} $和划分值v来确定一个K-1维的超平面，将多维空间划分为$ {d}_{i} $值小于v和$ {d}_{i} $值大于v的子空间。在KD-树的不同层，依次选择K个维度中的一个，本文利用KD-树将二维空间数据划分为稀疏区域和密集区域，根据每个维度的区间密度确定划分维度和划分值。假设X轴区间密度分布$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{x} $={$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{{x}_{1}} $=0.03，$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{{x}_{2}} $=0.80，$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{{x}_{3}} $=0.17}，Y轴区间密度分布$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{y} $={$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{{y}_{1}} $=0.1，$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{{y}_{2}} $=0.6，$ \mathrm{d}\mathrm{e}{\mathrm{n}}_{{y}_{3}} $=0.3}，稀疏区间包括$ \{{x}_{1}, {x}_{3}, {y}_{1}\} $。基于传统网格划分方法UG与基于KD-树划分的空间平面图如图 1所示，在采用KD-树进行划分时，避免了稀疏区域被过度划分，在大规模数据空间划分应用中能够有效降低值域。

3 基于用户分割的空间自适应划分算法 3.1 设计思想

本文在本地差分隐私模型的基础上，提出空间数据分层自适应划分方法KDG-HT，以对空间进行细粒度的划分，KDG-HT方法流程如图 2所示。首先，对位置空间进行粗粒度划分，基于本地差分隐私模型收集抽样数据，改进值域划分方式，利用位置数据分别从不同维度估计区域的用户位置分布情况，结合KD-树划分思想对区域进行粗粒度划分；然后，利用随机采样技术对用户分组，使其满足差分隐私的并行组合性，避免隐私预算分割造成过大的噪声误差；最后，在粗粒度空间划分的基础上，根据分组用户统计结果所提供的先验知识估计用户分布情况，对位置空间进行细粒度划分，得到满足本地差分隐私的空间数据统计结果。

中心化差分隐私模型下的空间数据发布通常采用隐私预算分割策略，例如，在基于树的空间索引技术中，依据定理1将隐私预算分别分配给空间索引的不同层次，实现差分隐私保护。然而本地差分隐私使用的随机应答机制对于隐私预算较为敏感，隐私预算分配到每个划分层次后所造成的噪声误差极大，因此，隐私预算分割策略在本地差分隐私中不适用。

由于用户随机分组不影响隐私性，因此本文依据定理2提出一种用户分割策略，将用户集合分为K组从而保持隐私预算不变。在用户分割策略中，存在2个方面的噪声影响：

1) 由于子数据集分布与总体分布可能不同，使得数据集划分引入抽样误差。

2) 每个划分层次的用户总计数减少，会放大噪声的影响。

由于抽样误差相比隐私预算分割所造成的噪声误差几乎可以忽略不计^[17]，同时可以通过KDG算法降低划分层次，控制由用户总计数减少所造成的噪声影响，因此本文算法采用的用户分割策略能够有效降低误差。

3.2 算法实现 3.2.1 基于密度的KD-树自适应划分算法KDG

KDG算法描述如算法1所示。

算法1    KDG算法

输入   数据集D，用户集合$ U\text{'} $的位置$ {l}_{i} $，隐私预算$ \epsilon $

输出   密度划分网格Grid

1.将区域X轴和Y轴分别分成m个、n个区间；

2.for $ {\mathrm{U}}_{\mathrm{j}} $ in $ \mathrm{U}\mathrm{\text{'}} $ do //收集者收集用户子集在当前树结构//中的扰动结果

3.判断用户$ {\mathrm{U}}_{\mathrm{j}} $的位置所属区间p；

4.将用户所在区间计数赋值为1，其余区间计数赋值为0；

5.生成向量$ {\mathrm{V}}_{\mathrm{x}}\in {\left\{\mathrm{0, 1}\right\}}^{\mathrm{m}}, {\mathrm{V}}_{\mathrm{y}}\in {\left\{\mathrm{0, 1}\right\}}^{\mathrm{n}} $；

6.$ {\mathrm{U}}_{\mathrm{j}} $发送$ {\mathrm{Z}}_{\mathrm{x}}\leftarrow \mathrm{L}\mathrm{R}\mathrm{R}\left({\mathrm{V}}_{\mathrm{x}}\right), {\mathrm{Z}}_{\mathrm{y}}\leftarrow \mathrm{L}\mathrm{R}\mathrm{R}\left({\mathrm{V}}_{\mathrm{y}}\right) $；//用户位置//扰动

7.end for

8.修正负计数；

9.$ \bf{S}\leftarrow \mathrm{\varnothing } $；//存放稀疏区间

10.if $ \mathrm{d}\mathrm{e}{\mathrm{n}}_{{\mathrm{X}}_{\mathrm{i}}} < \mathrm{\lambda }\times \mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{g}\mathrm{e} $ then//以X区间为例，区间密度$ //\mathrm{d}\mathrm{e}{\mathrm{n}}_{{\mathrm{X}}_{\mathrm{i}}}=\frac{\left|{\mathrm{l}}_{{\mathrm{X}}_{\mathrm{i}}}\right|}{\mathrm{\Delta }\mathrm{X}}，1\le \mathrm{i}\le \mathrm{m} $，$ \mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{g}\mathrm{e}=\frac{\left|{\mathrm{l}}_{\mathrm{X}}\right|}{\mathrm{m}} $

11.$ \mathrm{S}\leftarrow \mathrm{S}\cup \{{\mathrm{X}}_{\mathrm{i}}\} $；

12.while($ \mathrm{i} < \left|\mathrm{S}\right| $)

13.if $ \mathrm{r}\mathrm{g}\mathrm{d}\mathrm{d}({\mathrm{d}}_{\mathrm{i}}, {\mathrm{d}}_{\mathrm{i}+1}) < 1 $ then //1为设定参数

14.$ {\mathrm{d}}_{\mathrm{i}}\mathrm{、}{\mathrm{d}}_{\mathrm{i}+1} $区间合并；

15.网格划分

16.return Grid

KDG算法改进了值域划分方式，将区域分为m+n个区间，相比于传统的均匀网格将区域分为m×n个区块，能够大幅减少值域范围，从而降低位置数据采集造成的噪声误差。从X轴、Y轴2个维度分别划分区间，发送给随机采样的少量用户集合$ U\text{'} $，用户位置的不同维度数据在本地进行扰动后发送给收集方(步骤1~步骤7)，收集方分别统计X轴和Y轴2个维度各区间的频数，并对估计数进行修正(步骤8)。根据设定的横、纵坐标的密度阈值判断区间是否为稀疏区间，获取用户在X轴、Y轴的分布情况(步骤10~步骤11)。由于初步获取的用户分布情况并不准确，因此需要根据相邻稀疏区间的相对密度差rgdd重构密度区间(步骤12~步骤14)，$ \mathrm{r}\mathrm{g}\mathrm{d}\mathrm{d}({d}_{i}, {d}_{i+1})=\frac{‖\mathrm{r}\mathrm{a}\mathrm{t}{\mathrm{e}}_{i+1}-\mathrm{r}\mathrm{a}\mathrm{t}{\mathrm{e}}_{i}‖}{\mathrm{r}\mathrm{a}\mathrm{t}{\mathrm{e}}_{i+1}+\mathrm{r}\mathrm{a}\mathrm{t}{\mathrm{e}}_{i}} $，其中，$ \mathrm{r}\mathrm{a}\mathrm{t}{\mathrm{e}}_{i} $、$ \mathrm{r}\mathrm{a}\mathrm{t}{\mathrm{e}}_{i+1} $为相邻稀疏区间$ {d}_{i} $、$ {d}_{i+1} $的密度。以区间密度作为KD-树划分网格的依据(步骤15)，选择区域中密度最小的稀疏区间，如果区间一端恰好为当前待分割区域边界，则将稀疏区间所在区域标记为稀疏区域；否则，按照稀疏区间端点将区域分割为3个部分，稀疏区间所包含区域标记为稀疏区域。检查已划分的区块，若其中存在稀疏区间，且横坐标和纵坐标内都包含密集区间，则对区块继续划分，否则，停止划分并得到根据密度划分的网格Grid。

在密度自适应网格划分的基础上，仍需对稠密区域节点继续进行细粒度划分。MTR算法以当前划分节点的用户子集统计计数$ C\left({V}_{k}\right) $为依据，区分节点是否继续划分，对达到计数标准的节点按照四分树或二分树划分方法分裂稠密区域节点(步骤2~步骤5)，否则不再分割(步骤7)，经过多次重构后获得多叉树划分结果。

算法2    MTR算法

输入   T，节点统计值，隐私预算$ \epsilon $，分割计数标准$ \theta $

输出   $ \epsilon $-差分隐私树

1.for leaf node $ {\mathrm{V}}_{\mathrm{k}} $ in T do //节点分裂过程

2.if $ \mathrm{C}\left({\mathrm{V}}_{\mathrm{k}}\right) > $θ then

3.按照四分树分裂方法划分节点$ {\mathrm{V}}_{\mathrm{k}} $；

4.elif $ \mathrm{C}\left({\mathrm{V}}_{\mathrm{k}}\right) > \frac{{{{ \mathsf{θ} }}}}{2} $ then

5.按照二分树分裂方法划分节点$ {\mathrm{V}}_{\mathrm{k}} $；

6.else

7.复制$ {\mathrm{V}}_{\mathrm{k}} $；

8.end for

9.return T

3.2.2 LRR算法

在不同的划分层次统计不同的用户集合，用户根据当前划分层次节点进行编码，将扰动值发送给数据收集者，扰动过程中所采用的优化随机应答机制与文献[25]一致，如算法2所示。LRR算法描述如算法3所示。

算法3    LRR算法

输入   用户真实位置编码$ \boldsymbol{V} $

输出   用户扰动位置编码$ \boldsymbol{Z} $

1.$ \mathrm{Z}\leftarrow \mathrm{\varnothing } $(存放扰动值)

2.for w(V_k)in V do

3.if W(V_k)=1 then

4.$ \mathrm{P}\mathrm{r}[{\mathrm{Z}}_{\mathrm{k}}=1|\mathrm{W}\left({\mathrm{V}}_{\mathrm{k}}\right)]=\frac{1}{2}; $

5.else

6.$ \mathrm{P}\mathrm{r}[{\mathrm{Z}}_{\mathrm{k}}=0|\mathrm{W}\left({\mathrm{V}}_{\mathrm{k}}\right)]=\frac{1}{(1+\mathrm{e}\mathrm{x}\mathrm{p}(\mathrm{\epsilon }\left)\right)}; $

7.end if

8.end for

9.return $ \mathrm{Z} $

3.2.3 空间数据分层自适应划分算法KDG-HT

KDG-HT算法描述如算法4所示。

算法4    KDG-HT算法

输入   KDG-HT用户位置集合，隐私预算$ \epsilon $

输出   KDG-HT满足本地差分隐私的自适应树结构T

1.以概率$ \mathrm{\eta } $执行采样，获得用户集合$ \mathrm{U}\mathrm{\text{'}} $；

2.Grid < —KDG($ \mathrm{U}\mathrm{\text{'}} $)；//利用自适应密度算法KDG划分//Dom(D)的空间值域

3.将$ \mathrm{U}-\mathrm{U}\mathrm{\text{'}} $随机均分给(h+1)个用户子集$ \left\{{\mathrm{U}}^{0}, {\mathrm{U}}^{1}, \dots , {\mathrm{U}}^{\mathrm{h}}\right\} $；

4.for $ {\mathrm{h}}_{\mathrm{i}} $ in h+1 do

5.for $ {\mathrm{U}}_{\mathrm{j}}^{{\mathrm{h}}_{\mathrm{i}}} $ in $ {\mathrm{U}}^{{\mathrm{h}}_{\mathrm{i}}} $ do //收集者收集用户子集在当前树结构//中的扰动结果

6.用户$ {\mathrm{U}}_{\mathrm{j}}^{{\mathrm{h}}_{\mathrm{i}}} $遍历T来判断其位置所属路径p；

7.for leaf node $ {\mathrm{V}}_{\mathrm{k}} $ in T do //利用当前树结构的叶子节点//编码

8.if $ {\mathrm{V}}_{\mathrm{k}} $ in p then

9.$ \mathrm{w}\left({\mathrm{V}}_{\mathrm{k}}\right)\leftarrow 1 $；

10.else

11.$ \mathrm{w}\left({\mathrm{V}}_{\mathrm{k}}\right)\leftarrow 0 $；

12.end if

13.end for

14.生成一个向量$ \mathrm{V}\in {\left\{\mathrm{0, 1}\right\}}^{{\mathrm{h}}_{\mathrm{i}}} $；

15.$ {\mathrm{U}}_{\mathrm{j}}^{{\mathrm{h}}_{\mathrm{i}}} $发送$ \left({\mathrm{h}}_{\mathrm{i}}, \mathrm{Z}\right) $$ \leftarrow \mathrm{L}\mathrm{R}\mathrm{R}\left({\mathrm{V}}_{\mathrm{k}}\right) $；//扰动用户位置

16.for leaf node $ {\mathrm{V}}_{\mathrm{k}} $ in T do

17.$ \mathrm{C}\left({\mathrm{V}}_{\mathrm{k}}\right)\leftarrow \mathrm{C}\left({\mathrm{V}}_{\mathrm{k}}\right)+{\mathrm{Z}}_{\mathrm{k}} $；//聚集当前树叶子节点报告值，//$ {\mathrm{Z}}_{\mathrm{k}} $是向量$ \mathrm{Z} $中与节点$ {\mathrm{V}}_{\mathrm{k}} $对应的值

18.end for

19.if $ {\mathrm{h}}_{\mathrm{i}} < \mathrm{h} $ then

20.重构下一层树结构$ \leftarrow $MTR；//收集者根据用户子//集$ {\mathrm{U}}^{{\mathrm{h}}_{\mathrm{i}}} $中的统计值重构T

21.end for

22.return KDT

为了有效减少划分层次，保证大规模空间数据划分算法能够抽取充足的数据，KDG-HT算法利用基于KD-树的密度自适应划分方法KDG，获得第一层密度网格Grid(步骤1~步骤2)，将位置空间分为稀疏区域和密集区域，减少空区块的产生，避免大量空节点引入的噪声误差(本文中$ \eta $值设为5%)。然后将网格按照分割标准采用四叉树进行分割，预估树的最大高度h，本文基于文献[8]设定：

$ h=2\mathrm{l}\mathrm{o}{\mathrm{g}}_{4}^{}\left(\sqrt{\frac{\left|\mathrm{D}\mathrm{o}\mathrm{m}\left(D\text{'}\right)\right|\times \epsilon }{10}}\right) $

(2)

其中：值域$ \left|\mathrm{D}\mathrm{o}\mathrm{m}\left(D\text{'}\right)\right| $表示处于密集区域的最大网格区域。

树结构每进行一次划分，则获取用户子集在当前树结构叶子节点的分布情况，给下一层树结构划分提供总体分布先验知识(步骤5~步骤18)。收集者通过MTR算法重构树T，直到树结构被划分到最后一层(步骤19~步骤20)，最终数据收集者得到自适应划分的树结构KDT。

4 实验结果与分析 4.1 实验设置

本文实验环境为Windows7 3.40 GHz，8.0 GB，所有算法均采用Python实现，编程环境为Python3.6。实验采用2组真实的地理数据集Checkin和Landmark，Checkin数据集从基于位置的社交网站Gowalla获取，Landmark数据集是纽约市出租车2011年的乘车和下车地理坐标数据，实验中只取2组数据集的经纬度信息，2组数据集的具体统计信息和可视化结果分别见表 1和图 3。

利用上述2种数据集，参照文献[8]，本文采用相对误差RE来度量RAPPOR^[13]、UG^[19]、GT-R^[20]、KDG-HT算法的范围查询精度。设置3种大小不同的查询区域，针对每种类型的查询区域随机生成查询，计算相对误差的平均值。相对误差计算如式(3)所示：

$ \mathrm{R}\mathrm{E}\left(Q\right)=\frac{\left|\tilde{Q}\left(D\right)-Q\left(D\right)\right|}{\mathrm{m}\mathrm{a}\mathrm{x}\left\{Q\right(D), \rho \}} $

(3)

其中：$ Q\left(D\right) $表示查询原始数据集D的结果；$ \tilde{Q}\left(D\right) $表示数据集D扰动后的发布数据范围计数结果；$ \rho =0.001 $$ \times $$ \left|D\right| $，$ \left|D\right| $代表原始数据集大小。

本地差分隐私模型的噪音误差受隐私预算影响较大，KDG-HT算法提出用户分组的方法以避免隐私预算分割，同时也会引入额外噪声误差，细粒度查询所涉及的树节点较深，噪声误差更具对比性，因此，实验在上述2种数据集以及细粒度查询设置下计算噪声误差的估计值。相对误差由噪声误差与均匀假设误差构成，噪声误差的计算如式(4)所示：

$ \mathrm{NE}(Q)=\frac{|\tilde{Q}(D)-\bar{Q}(D)|}{\max \{\bar{Q}(D), \rho\}} $

(4)

其中：$ \stackrel{-}{Q}\left(D\right) $表示数据集D未经扰动的数据范围计数结果。

本文设置抽样概率为5%，隐私预算参数的取值为0.1、0.3、0.5。实验中查询范围分别覆盖Checkin和Landmark数据集的[5%，20%]、[20%，40%]、[40%，60%]，在每种查询范围内随机生成5 000次查询。

4.2 数据发布可用性度量 4.2.1 基于Checkin数据集的算法RE值比较

图 4所示为Checkin数据集下RAPPOR、UG、GT-R以及KDG-HT算法的RE值比较结果。由图 4(a)~图 4(c)可以看出，在固定查询范围时，ε由0.1变化到0.5，4种算法的查询精度随着ε增大而逐渐提高，KDG-HT的查询精度优于其他3种算法。当查询范围为[5%，20%]时，KDG-HT的查询精度相比其他3种算法效果显著，特别是在ε=0.3时，本文算法精度是GT-R算法的3倍。从图 4可以看出，查询范围从[5%，20%]变化到[40%，60%]且ε固定时，算法查询精度逐渐提高，这主要与查询区域和相交节点的重合比例($ \mathrm{s}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{e}\in \left[\mathrm{0, 1}\right] $)有关，均匀假设误差与scale呈反比，查询范围影响scale大小，查询范围过小会引起均匀假设误差较大。随着查询范围的增大，查询区域与相交节点的重合比例scale增大，均匀假设误差逐渐减小，从而提高了查询精度。本文算法能够针对性地自适应划分大规模数据空间，对于密集区域进行充分划分，有效降低了均匀假设误差，同时减少了稀疏区域空节点产生，降低了噪声误差，Checkin数据集中数据分布不均匀、偏斜程度较高的问题得到有效解决，因此，查询精度明显提升。

4.2.2 基于Landmark数据集的算法RE值比较

图 5所示为Landmark数据集下RAPPOR、UG、GT-R以及KDG-HT算法的RE值比较结果。由图 5(a)~图 5(c)可以看出，在固定查询范围时，ε由0.1变化到0.5，各个算法的查询精度随着ε的增大而逐渐提高，KDG-HT的查询精度优于其他3种算法，尤其当查询范围在[5%，20%]时，KDG-HT的查询精度比其他算法提高了一倍以上。4种算法的查询精度都随着查询范围的增大而提高，这种现象主要是由于查询范围增大后，所涵盖的节点面积增大，均匀假设误差降低，使得查询精度提高。由于Landmark数据集分布较为均匀，偏斜程度较低，均匀网格划分方法的精度已经达到较高水平，KDG-HT算法查询精度的提升空间较小，因此，其效果提升没有Checkin数据集中明显。

4.2.3 噪声误差影响程度比较

图 6所示为Checkin和Landmark数据集在[5%，20%]查询范围下RAPPOR、UG、GT-R以及KDG-HT算法的NE值比较结果。由图 6(a)可以看出，ε由0.1变化到0.6，各个算法的NE值随着ε的增大而逐渐降低，KDG-HT算法的NE值相比RAPPOR和UG算法降低了5倍以上。RAPPOR和UG算法采用传统的隐私预算分割策略，在本地差分隐私中，这种策略对噪声误差影响较大。GT-R算法和KDG-HT算法都利用隐私预算的并行组合性代替隐私预算分割策略，因此，都大幅降低了噪声误差。在ε值较小时，KDG-HT算法的NE值低于GT-R算法，这是由于KDG-HT算法根据数据集的分布情况进行空间划分，GT-R算法采用均匀划分方法，随着ε值的增大，噪声影响减小，因此，在ε值较大时，2种算法产生的噪音差异减小。在图 6(b)中，KDG-HT算法的NE值相比RAPPOR、UG算法有明显降低，但效果没有Checkin数据集中明显，这也是由于KDG-HT算法的多层空间划分方法在非均匀数据集上优势较为明显，而Landmark数据集中分布相对均匀，尤其在隐私预算较高时，KDG-HT与其他算法降低噪声误差的效果相近。由图 6可以看出，KDG-HT算法的噪声误差在2种数据集上都明显低于RAPPOR、UG算法，说明用户分割策略带来的噪声影响远小于隐私预算分割所造成的噪声，其能够有效降低噪声误差。

4.3 算法运行时间比较

表 2所示为不同ε取值下UG、RAPPOR、GT-R和KDG-HT算法在Checkin数据集下的执行时间，其中运行时间不包括数据读取以及查询时间。从表 2可以看出，本文KDG-HT算法具有较高的运行效率，这是由于算法中采用的用户分割方法能够在很大程度上降低通信代价，而GT-R算法中用户抽样层次方法也能达到类似的效果，因此，KDG-HT和GT-R都具有较高的运行效率。当ε值为0.1时，KDG-HT算法比GT-R算法的运行效率高0.14倍，当ε值为0.5时，KDG-HT算法比GT-R算法的运行效率高0.17倍，相较GT-R算法，本文算法的划分效率更高，主要原因是本文采用的密度自适应划分方法有效减少了划分层次。

在表 2中，随着ε的增大，UG、RAPPOR、GT-R算法运行时间增加，这是由于UG、RAPPOR、GT-R算法的划分粒度受隐私预算ε影响，ε越大，网格划分粒度越细，树结构层次越高，因此，算法运行时间增加。而本文KDG-HT算法对区域执行自适应划分方法，ε大小对其划分方式影响较小，因此，在不同隐私预算下本文算法的运行效率均较高且稳定。

5 结束语

本文针对本地差分隐私模型下大规模空间数据采集和发布过程中存在的空间划分问题，提出一种分层次自适应划分算法KDG-HT。该算法能够通过估计数据集的分布情况自适应划分空间，解决了本地差分隐私模型无法获取用户真实位置数据的问题，同时分层次划分方法和用户分割策略克服了非均匀大规模空间数据范围查询的噪声累积问题，有效平衡了均匀假设误差和噪声误差，使数据划分发布查询精度得到有效提高。在2个较具代表性的大规模数据集上的实验结果表明，KDG-HT算法查询精度优于UG、RAPPOR等算法。空间数据规模大且变化快，现有的静态空间分割方法无法适用于本地差分隐私模型下动态空间数据的采集和发布过程。本文KDG-HT算法能够在本地差分隐私模型下预估空间位置数据的分布情况。下一步考虑将本文算法与滑动窗口技术相结合，并应用于本地差分隐私模型下的动态环境隐私数据发布任务。