基于噪音前缀树的轨迹数据发布隐私保护算法研究

石秀金，徐嘉敏，王 锐，张姝俪

（东华大学计算机科学与技术学院，上海201620）

0 引 言

随着定位技术的快速发展和广泛应用，越来越多的轨迹数据被产生、发布、采集和分析。如车载定位系统，带GPS的移动设备以及位置传感器等，这些设备在提高人们生活质量的同时也产生了大量的轨迹数据，其中可能包含车辆、身份以及实时位置等诸多数据，然而这些内容都含有个人敏感信息，直接发布会给个人隐私造成威胁。因此，对轨迹数据发布的隐私保护具有重要的研究意义。

在轨迹数据的发布中，最简单的方式是删除轨迹上的准标识符属性［1］，如个人基本信息，但却不能全面保护移动对象的轨迹隐私。k-匿名模型［2-3］能够在一定程度上保护轨迹隐私，但是该模型具有容易受到新型攻击、系统开销大等缺陷，因此随着数据的大量收集，这种模型并不能有效保证轨迹信息。

文献［4］中证明采用差分隐私保护模型，使用合理数量的噪音保护位置数据中的敏感信息，而且还能保证数据的可用性。差分隐私方法提供了严格的隐私模型来保护空间信息中的敏感数据，同时能够保证发布数据的实用性，也并不关心攻击者拥有的背景知识，该模型向查询或者分析结果中添加一定量的噪音来达到隐私保护的效果。差分隐私模型可以应用于数据发布、数据挖掘、个性化推荐等诸多领域。

对于轨迹数据的发布，已有不少研究者考虑到用差分隐私模型来实现轨迹数据发布的隐私保护。2012年，Chen等人［5］提出一种基于噪音前缀树的交通数据发布隐私保护方式，并通过实验证明这种方式可以应用于轨迹数据发布的隐私保护研究领域。文献［6］提出基于差分隐私保护的轨迹序列非交互式合成方式，然而这种方式局限于短距离内的轨迹数据隐私保护，在更大规模的空间区域和实际情况中是无效的。2012年，Chen等人［7］又提出通过n-gram思想解决短距离问题，然而这种方式导致了轨迹序列的丢失。

在综合上文研究成果后，本文提出了一种基于噪音前缀树的轨迹数据隐私保护算法。该算法分3步，可描述为：首先将轨迹数据离散化后通过聚类分析获得具有某些特定性质的特征点（本文称为锚点），对锚点进行隐私保护后构建参考系；然后基于该参考系对原始轨迹进行校准，并用校准轨迹构造噪音前缀树；最后根据拉普拉斯机制向叶子节点中添加噪音，形成用于发布的数据版本。该算法在一定程度上解决了空间限制以及序列丢失等问题。

1 问题描述

轨迹数据是一组从实际路线中提取的位置有界和时间有序的序列，可以表示为：tj＝｛(x1，y1，t1)，(x2，y2，t2)，…， (xn，yn，tn) ｝。 其中， (xi，yi，ti)（1 ≤i≤n） 表示移动对象在ti时刻的位置为（xi，yi） ，也称为采样位置或采样点，ti则称为采样时间。若忽略具体采集到某个位置点的时间，而是在指定的时间段内按照时间序列进行排序，同时以p1表示(x1，y1)代表的位置点，则轨迹tj可以表示为tj＝｛p1，p2，…，pn｝。其中pi∈P，P表示一定区域内站点位置的集合，｜P｜表示站点位置的数量且i≤｜P｜。

例如，假设p1(x1，y1)表示某小区，p2(x2，y2)表示某地铁站，p3(x3，y3)表示某商场，p4(x4，y4)表示某学校，p5(x5，y5)表示某条路的第二个交叉路口，那么轨迹tj＝｛(x1，y1，t1)，(x2，y2，t2)，(x3，y3，t3)， (x1，y1，t4)｝表示：t1～t4时间段内，车辆A从小区出发，先到达地铁站，然后到达商场，最后在t6时刻回到小区。也可以表示为：在t1～t4时间段内，tj＝｛p1，p2，p3，p1｝。

在指定时间内，如以一周为期限，每次采样的时长为2 h，每周分别在周一和周三上午10：00～12：00进行采样，该车辆可能有不止一条轨迹数据产生，用ITq＝［tj1，tj2，…，tjk］表示该车在一周内产生的轨迹数据。该周内共产生的轨迹数据集为T＝［IT1，IT2，…，ITm］。 研究得到的由全部轨迹组成的一般的轨迹数据集可见表1。

考虑到后续的研究需要，这里关于文中涉及到的基础概念理论将展开探讨论述如下。

定义1 锚点空间域中相对稳定的特征位置点，其变化不大。如基于道路分析提取到的交叉点、转折点，基于轨迹数据中的位置进行聚类分析提取到的质心等。锚点用ai表示，数量上小于该数据集的位置总数｜P｜，锚点组成的集合称为锚点集A，用来构建参考系。

表1 轨迹数据集Tab.1 Trajectory data set

定义2 轨迹校准基于由集合A构成的参考系，校准过程就是将原始轨迹tj＝［p1，p2，… ，pn］转换为t＇j＝［a1，a2，…，am］。 其中，ai∈A， 1 ≤i≤m，m可以等于n。 称t＇j是tj的校准轨迹。

定义 3 差分隐私［4，8-10］给定数据集D和D＇，且D和D＇之间最多相差一条记录，即｜DΔD＇｜≤1。 给定一个隐私算法A，Range（A） 表示A的取值范围，若算法A在数据集D和D＇上任意输出结果O（O∈Range（A））满足下列不等式，则A满足如下的ε-差分隐私：

其中，概率Pr［·］表示隐私的披露风险，由算法A的随机性控制；隐私预算参数ε表示算法A所能提供的隐私保护程度。ε越大，隐私保护程度越低，反之，隐私保护程度越高。

由式（1）可以看出，差分隐私保护模型是基于2个只有一条记录的不同数据集进行数据失真处理的，结果是保证即使攻击者知道大量的背景知识也无法准确判断该记录是否在表中。

研究可知，差分隐私的组合特性［11］可分为2种，对其可做阐释解析如下。

（1）顺序组合。给定数据集D以及一组关于D的差分隐私A1（D），A2（D），…，Am（D），分别满足ε-差分隐私，且任意2个算法的随机过程相互独立，则这些算法组合起来的算法满足差分隐私。

（2）并行组合。A1（D），A2（D），…，Am（D）， 分别表示输入集为D1，D2，…，Dm的一系列满足ε-差分隐私算法，且任意2个算法的随机过程相互独立。则这些算法组合起来的算法满足ε-差分隐私。

定义4 噪音前缀树［12］序列数据集T的前缀树PT是三元组PT＝（V，E，Root），其中V是标记位置的节点集合，每个节点对应于T中唯一的前缀；E是边的集合，表示节点之间的转换；Root∈V是PT的虚根。

定理1 拉普拉斯机制［12］拉普拉斯噪音实质上是一组满足拉普拉斯分布的随机值，其原理是向原始数据及统计分析结果中添加服从拉普拉斯lap（b）的噪音，实现加入噪音后的查询结果满足差分隐私约束效果。文献［8］提出拉普拉斯机制，则需要输入数据集D，函数f和隐私参数α。 所添加的噪声符合概率密度函数的拉普拉斯分布，其中λ由全局灵敏度f和预期隐私参数α确定。

定义5 地理相似性［13］给定2条轨迹t1＝［p11，p12，……，p1n］和t2＝p21，p22，……，p2m， 地理相似性表示为：

定义6 召回率基于点场景的召回率用于衡量位置点的隐私保护级别，满足如下公式：

其中，CT是基于NDBSCAN算法得到的扰动锚点的集合；IST是扰动点与原始位置点之间的距离小于初始阈值的点。召回率越大，则认为数据的可用性越大。

基于轨迹场景的召回率用于衡量对轨迹数据的隐私保护级别，满足如下公式：

其中，IST是被重新识别的轨迹，CT是基于Final Private Trajectory Release算法得到的发布数据集合。召回率越高，则认为数据的实用性越大。

定义7 全局敏感性［4］对于任意一个函数f：D→Rd，函数f的全局敏感性为：

其中，D和D‘之间最多相差一条记录；R表示所映射的实数空间；d表示函数f的查询维度；p表示度量Δf使用的Lp距离，通常用L1来度量。

2 算法及性能分析

传统基于差分隐私的轨迹数据发布算法中，基于可变长度n-gram的SD算法通过噪声合成的方法改进轨迹数据发布的隐私保护效率，然而n-gram模型只是简单地将所有序列切割成至少Imax长度的序列构建树，对长距离轨迹会丢失一定的信息。本文的主要目的旨在提出一种基于差分隐私保护机制的轨迹数据发布算法以解决上述局限性。

该算法可分为2个阶段，对此则分述如下。

（1）在第一阶段，为了从大量的轨迹位置点中提取具有一定特征的锚点构建参考系，本文在DBSCAN算法［14］的基础上进行改进和丰富，提出NDBSCAN算法。NDBSCAN算法将全部数据点分为核心点（半径r内含有超过阈值τ的点）和非核心点。通过邻域查询不断寻找当前点的种子点，并用新种子扩展同一类别的集群，直到全部的种子点用完，得到全部的特征点，再为其添加拉普拉斯噪音。

（2）在第二阶段，主要任务是使用上述扰动锚点对原始轨迹进行校准，得到校准轨迹。而后基于差分隐私框架构造噪音前缀树，在树的叶子节点添加拉普拉斯噪音形成最终的发布版本。然而噪音的大量添加使得发布的数据实用性降低，为了添加更少的噪音，该算法通过滤波器来减少空节点的数量。算法的主要思想是：从虚拟根开始，逐级分析每一层高度上的节点，通过估计当前节点的子树高度来分配隐私预算并计算滤波器在该节点的截止值。对于添加噪音后能达到截止值的非空节点，将其添加到前缀树中生成最终发布版本。

这2个阶段都需要添加拉普拉斯噪音。第一阶段通过基于先验知识的阈值进行控制；第二阶段提出一种自适应算法解决构建前缀树过程中的噪音计数问题。

2.1 算法基本思想

本文算法首先是基于道路分析提取轨迹数据中的交叉点，转折点，对轨迹数据离散化得到的位置点进行基于密度的聚类算法分析（NDBSCAN）提取轨迹关键点，由交叉点、转折点和轨迹关键点组成特征点集，本文称为锚点集。出于隐私性考虑，本文将对锚点集中的特征点进行隐私保护操作，为其添加一定量的拉普拉斯噪音。在位置点获得隐私保证的基础上，基于扰动锚点校准原始轨迹。通过对原始轨迹进行校准，去除冗余位置点，在不影响原始轨迹大致走向的前提下缩短了长度，得到校准轨迹。基于校准轨迹构建前缀树，从而降低了前缀树构造过程中的计算量和算法复杂度。

然后，基于校准轨迹构造噪音前缀树，该树从根节点到每一个叶子节点的路径表示一条轨迹数据。本文基于一种自适应剪枝方案处理构建前缀树的过程中产生的空节点，以提高效率和效用。对于空节点，本文采取的一种解决方案是另外存储，算法结束时再做统一处理，对于非空节点，为其添加拉普拉斯噪声并计算噪音计数，对于大于阈值的节点，将其添加到树中，否则将其标记为叶子节点。通过自适应剪枝方案减少了前缀树构建过程中的计算量，提升了算法性能。

2.2 算法描述

轨迹数据发布是从轨迹位置点中提取锚点，而后基于该锚点校准原始轨迹后构建噪音前缀树生成发布版本。用于提取锚点的NDBSCAN算法和构建噪音前缀树的FPTR算法分别详见如下代码设计。

算法1 NDBSCAN算法

输入：轨迹tj上全部位置点的集合P；存储每个集群的结果RL；存储种子点的队列SD；邻域查询RQ的半径r；核心点的阈值τ；存储全部锚点的集合M＝｛｝；M中的一组位置点集Mcj；锚点的计数CT；锚点的噪音计数CT＇

输出：扰动锚点集

Construct R-Tree index overP

FOR each pointpinP，do

IFP［i］.clustered＝falseTHEN

SD.add（P）；

RL.add（P）；

whileSDis not null do

Points P′＝SD.pop（）；

Points P′＝RQ（P′，r）；

FORi＝0 to｜P′｜do

IFP′［i］.clustered＝falseand collect withP′directly

RL.add（P′［i］）；

SD.add（P′［i］）；

end

end

end

IF｜RL｜≥τTHEN

M.add（RL）；

FOR each pointP″inRLdo

P″.clustered＝true

end

end

RL.clear（）

end

FORj＝1 to｜M｜do

CT′＝｜Mcj｜+lap（σct）；

IF CT′＞γthen

CC′＝NoisyLap（σj）（CCj）

End

分析可知，NDBSCAN算法是从轨迹tj的全部位置点集合的某一点P开始，若判断P为核心点，则将与P同类别的点即都归并作为P的邻域点，而且将这些点作为种子点进行下一轮考察，不断扩展种子点所在的类直至找到完整类。重复以上步骤直至寻找到其它类，则算法结束。对算法获取的锚点集添加拉普拉斯噪音形成扰动锚点集。

算法2 Final Private Trajectory Release算法

输入：校准后的轨迹数据集CT，全部的隐私预算ε，初始阈值θ，轨迹的最大长度xmax

输出：噪音前缀树PT

Initialize a prefix treePTwith a virtual root

FORi＝0；i＜xmax；i++do

FORj＝0；j＜｜nds｜；j++do

IFnds［j］.flagisfalse

tr（nds［j］）.height＝EstimateHeight（）；

ε［i］［j］＝PBD（tr（nds［j］）.height）；

θ［i］［j］＝Threshold（ε［i］［j］）；

nodes［pcn］＝All possible children of nds［j］；

FORk＝0 to｜pcn｜do

Count＝c（pcn［k］）；

IFNoisyCount≥θthen

NoisyCount＝c＇(pcn[k])

NoisyCount≥θthen

Add pcn［k］intoPT；

else

pcn［k］.flag＝true；

end

else

Node［empty］.push（pcn［n］）；

Node［empty＇］＝ThresholdSampling（empty＇）；

end

end

Form＝0 to｜empty＇｜do

NoisyCount＝c＇（empty＇［m］）；

IFNoisyCount≥θthen

Add empty＇［m］intoPT；

elseempty＇［m］.flag＝＆；

empty＇［m］.flag＝＆；

end

end

end

End

分析可知，FinalPrivateTrajectoryRelease（FPT）算法是在文献［7］中提出的噪音树构建算法的基础上加以改进的，该算法能够自适应剪枝以减少噪音的添加。该算法的输入是校准轨迹数据集CT、隐私预算ε、初始阈值θ和轨迹的最大长度xmax。 首先，初始化前缀树PT并创建虚拟根节点，构建噪音树是找到所有序列，直到计数大于阈值而长度小于xmax，迭代生成树中每个层级的节点并对每个节点进行判断：如果该节点不是叶子节点，则估计该节点子树的高度并基于自适应隐私预算分配算法计算该节点应被分配的ε值。 此外，找到该节点的所有可能子节点，同时计算在数据集CT中从根节点到该节点轨迹前缀的频率。在此过程中，为了处理大量空节点造成的冗余现象，本文提出一种自适应剪枝方案处理空节点和非空节点的潜在子节点。对于计数非0的非空节点，通过拉普拉斯噪音添加到实数中来计算噪音计数，对于噪声计数大于阈值的节点添加到噪音前缀树中，否则该节点被标记为叶节点；对于计数为0的空节点，则将其专门存储起来，不会添加到噪音前缀树中，这样在一定程度上就减少了构造噪音前缀树的计算量。如果噪音前缀树的高度达到nmax或者没有可添加的节点时，遍历过程即停止，其噪音计数无法超过阈值，或者节点所在高度的层级隐私预算消耗完。

2.3 算法性能分析

这里有2个连续的步骤，分别是：隐私参考系统和隐私轨迹发布。本文首先证明这2个连续步骤生成的发布结果分别满足ε-差分隐私，再通过差分隐私的组成属性证明该算法满足ε-差分隐私。其中，εpr用于隐私参考系统，并且εpg用于隐私轨迹发布。

对于第一阶段，又分为计数扰动εct和质心扰动εcc。 在此，εpr＝εct+εcc， 计数灵敏度，即为max(NUMindividual(points))，质心灵敏度即为max(distance(pi，pj))／2。 因此， 通过将函数的随机噪声添加到每个聚类计数，将Laplace函数的随机噪声添加到每个聚类质心使得算法1满足 (εct+εcc)-差分隐私。

对于第二阶段，令lmax为原始轨迹数据集T中的最长序列，因此，增加或者去除一个单独轨迹(T＇)最多影响lmax条根到叶子节点的序列，记为SE(lmax)，即Δf＝lmax。 定义噪音性强轨迹的功能函数M(T)，那么在噪音前缀树PT中至少有个节点，记为X，分配给nd∈X的隐私预算是εnd。采用拉普拉斯噪声机制，可以表示为：

3 实验分析

为了验证算法的隐私性和实用性，本文通过大量实验来评估FPT算法的性能。本文的实验分为2部分。第一部分：验证锚点集和发布轨迹的隐私性；第二部分：验证发布轨迹数据的实用性。实验环境为：Inter（R）Core（TM）i5-2450M CPU＠ 2.50 GHz，8 Gb内存，Win7操作系统，编程环境为 MyEclipse。实验数据集为 Gowalla和 Brightkite上的签到数据［11］，测试数据集由 Thomas Brinkhoff路网移动节点数据生成器生成。

3.1 隐私性验证

从清洗过的数据集中分别随机选择8 000个轨迹，其中位置点的总数是252 448，最大轨迹长度是192，平均轨迹长度为13。 设置不同的ε＝0.01、0.1、0.5、1.0、1.5， 设 置 聚 类 算 法 的 初 始 阈 值 为 半 径0.01 km内至少包含50个特征点。每组实验进行10次，并以平均值作为该组实验的最终结果。

实验中，设置欧氏距离阈值为100 m，隐私预算ε＝0.01、0.1、0.5、1.0、1.5 时，对 2 个数据集分别基于本文算法提取的锚点以及发布轨迹的召回率对比如图1所示。其中，横坐标表示隐私预算，纵坐标表示召回率。

图1 经过本文算法处理后数据的召回率Fig.1 Data recall rate of this algorithm

图1 表示数据集基于本文算法发布的锚点以及数据在给定阈值的前提下所能达到的召回率。分析图1可知，随着ε变大，锚点的召回率和发布轨迹的召回率都呈现增加的趋势。这是由于ε越大，隐私保护程度越低，添加的拉普拉斯噪音越少，锚点和轨迹的可识别率越高，因此召回率随之增加。反之，ε越小，隐私保护程度越高，可识别的锚点和轨迹越少，相应的召回率越低。从实验结果来看，即使在弱隐私保护级别下，攻击者无法重新识别的敏感位置百分比超过86%，无法重新识别的轨迹百分比超过89%，证明了本文算法的隐私性。

3.2 实用性验证

为了评估数据的实用性，本文基于2个数据集针对隐私保护后发布的数据进行KNN查询以及频繁序列模式挖掘，并与文献［7］中提出的直接构建噪音前缀树实现轨迹数据隐私保护的算法进行对比分析。本文采用欧式距离（ED）以及实序列编辑距离（EDR）进行计算，欧氏距离用于评估具有相同长度轨迹相似性，实序列编辑距离的目的则是匹配每个可能的位置对（pi，pj）来计算使得t1和t2等效所需的最小编辑数。其中，pi∈原始轨迹数据集，pj∈校验轨迹数据集。 当pi，pj匹配时，编辑距离为0，否则为1。从数据集中随机选择500个随机轨迹执行KNN查询实验对比如图2（a）、（b）所示。其中，横坐标表示隐私预算，纵坐标表示频繁模式挖掘的距离。

图2 不同隐私保护水平下的相对误差Fig.2 Relative error at different levels of privacy protection

从实验结果可以看出，一般的隐私保护机制在较强的隐私保护支持下，数据的实用性降低，而本文提出的数据发布算法可以在数据隐私性相同的情况下保持相对较高的数据实用性。

4 结束语

在差分隐私保护下，本文提出了隐私轨迹校准和发布系统，解决了基于噪音前缀树的轨迹数据发布问题，基本上弥补了历史算法中存在的距离局限性以及序列丢失等问题。此方法通过建立噪音增强的前缀树来实现带有隐私保证的嘈杂校准轨迹发布解决方案，可扩展到大型地理空间领域，能够有效保护轨迹数据中的个人隐私信息，提高数据的利用率。然而，当数据集增加到一定限度后隐私预算必定会被耗尽，并且随着数据集的增加，所添加的噪音也会加大，从而影响发布数据的实用性。因此，该算法对动态轨迹数据发布的隐私保护仍不能完全适用。今后的研究方向将集中在如下2个方面：一是如何在不影响数据隐私性和实用性的前提下进一步减小算法的计算量；二是如何在差分隐私保护下实现数据的增量更新。