轨迹数据隐私保护综述

顾贞，马春光，宋蕾，李菊雁

（1.哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001；2.黑龙江东方学院基础教学研究部，黑龙江哈尔滨150066；3.黑龙江大学数据科学与技术学院，黑龙江哈尔滨150080）

1 引言

近年来，随着智能设备以及定位技术的发展，研究人员会搜集到越来越多的运动物体的轨迹数据，对其进行分析挖掘可以为人们提供方便快捷的服务。例如，在城市路网规划中，可以合理规划城市交通避免产生交通拥堵，进而提高人们的生活质量[1～4]。然而，轨迹数据中含有大量的个人信息，如用户的家庭地址、单位地址、身体健康状况等，如果直接发布位置和轨迹数据，会导致人们的隐私泄露[5]。

位置轨迹隐私保护问题主要分两类：一类是离线模式下的位置轨迹隐私保护，由特定机构搜集轨迹数据进行分析和挖掘将有用信息提供给特定客户的使用，这要求在轨迹数据发布前对整条轨迹进行隐私处理，如文献[6～10]为针对离线模式下轨迹数据隐私保护方法的研究；另一类是在线位置轨迹隐私保护，如基于位置的服务，首先确定对象的实时位置，然后提供给对象相关的各类服务，如通过移动设备定位对象当前的地理位置，然后寻找其附近范围内的餐馆等查询服务，移动对象的实时轨迹数据要上传服务提供商，因此也面临隐私泄露的风险，基于位置服务的轨迹隐私保护是非常有意义的，如文献[11～16]为针对基于位置服务的轨迹隐私数据保护研究。

本文主要研究离线模式下的轨迹隐私保护技术，如图1所示。文中对现有的轨迹数据隐私保护方法进行了总结分析，总结优点和缺点，然后分析轨迹数据本身固有的统计分布特性，讨论了轨迹隐私保护技术中还需要深入解决的相关问题。

2 相关概念

（1）轨迹隐私[17]：轨迹隐私是指个体运行轨迹本身含有的敏感信息（如访问过的敏感位置），或者由运行轨迹推导出的其它个人信息（如家庭住址、工作地点、生活习惯、健康状况等）。

（2）轨迹数据集[17]：移动对象轨迹可表示为三维空间中的一条折线，记为其中表示轨迹在时刻的位置为，为轨迹的点数，轨迹数据集是轨迹的集合，记为轨迹数据库中轨迹的条数。

（3）轨迹k匿名集[17]：给定轨迹数据库，发布的轨迹数据库是的k-匿名版本，则需要满足两个条件。

（4）语义位置：语义位置是指真实环境中的具有语义的位置，移动对象访问或者停留的位置，如宾馆、商店、商场、医院、银行等。

3 轨迹隐私保护方法

3.1 基于抑制法的轨迹隐私保护

根据实际情况，有选择的抑制发布轨迹数据中的敏感或者频繁访问位置[18,19]或者整条轨迹[20]，此类方法实现简单、易导致信息丢失、数据的可用性有限。文献[21]中提出了基于扰动的轨迹隐私保护方法，即用出现频率最低的同类节点来代替存在隐私泄露风险的节点，从而实现对具有隐私泄露风险的节点的抑制，方法是基于数理统计的方法，在保持轨迹数据的内部结构和增加数据的可用性方面具有一定的优势。文献[20]提出两种基于轨迹频率的方案对轨迹数据进行匿名处理，第一种方案是根据情况抑制整条有问题的轨迹数据或向有问题的轨迹数据集中添加假数据；第二种方案是采用特定的轨迹局部抑制法对数据进行抑制处理。抑制法将轨迹中的敏感位置信息进行隐藏不发布，方法简单也有效，但是具有局限性：一是删除了原始轨迹的部分信息，导致数据挖掘受到影响；二是目前都是根据已知攻击模型选取抑制信息，当攻击模型不确定的时候，抑制法不适用。

3.2 基于假轨迹的轨迹隐私保护

假轨迹技术这种方法的原理是通过对原始轨迹中加入一定数量的虚假轨迹使得原始轨迹数据受到干扰，降低原始轨迹泄露的概率，这种方法实现比较简单，但是需要注意保证原轨迹数据的统计可用性，需要满足虚假轨迹的移动状态与真实轨迹相似[22]，虚假轨迹与真实轨迹之间有交叉。添加虚假轨迹的方法有随机生成法和旋转模式生成法。随机生成法是指在轨迹的起点和终点之间随机生成一条与原轨迹运行模式相似的虚假轨迹。旋转生成法是指以真实轨迹为基础，对原轨迹进行旋转，例如在文献[23]中提出通过真实轨迹的旋转得到备选的假轨迹集，然后根据隐私模型下的参数对备选集进行筛选。文献[24]将旋转模式与随机模式两种方法结合，提出了K交叉模式方法，即通过确定虚假轨迹和真实轨迹的k个交叉点，随机生成交叉点之间的轨迹。

文献[25]提出的方案主要包括两部分，真实轨迹旋转和虚假轨迹调整，首先在用户的真实轨迹上随机选择一个参考点，通过将用户的真实轨迹旋转不同角度，依次生成其他多条潜在虚假轨迹。由于生成的多条潜在虚假轨迹是用户真实轨迹旋转的产物，从而有效地保证了轨迹之间的相似性，考虑到背景信息对用户轨迹隐私保护的影响，在轨迹旋转的过程中，通过将选定旋转点进行基于背景信息的偏移，该方案能够在保证虚假轨迹与真实轨迹相似性的基础上有效地抵御拥有背景信息的攻击者的攻击。假轨迹方法需要注意的问题是，若生成的假轨迹不满足路网约束，不符合移动对象的运行模式，则假轨迹并不起到隐私保护的作用，反而造成用户的轨迹隐私泄露，所以要求假轨迹与用户的真实运动轨迹要尽量相似，如何模拟生成合适的假轨迹是人们一直探索的问题。

3.3 基于泛化方法的轨迹隐私保护

基于泛化方法的轨迹隐私保护最主流的方法是轨迹k匿名方法[6～9]，找相似的k条轨迹来构造匿名集合，使攻击者在没有其他背景知识的情况下识别用户身份的概率不超过泛化方法主要有三个步骤。

（1）轨迹预处理

这个阶段的主要任务是对所有具有相同开始和结束时间的轨迹进行分组，即将轨迹数据集中起始时间和结束时间相同的轨迹分为一个等价类。但是，由于实际应用中无法保证每条轨迹之间的采样置位点都是同一时刻，为了增加等价类中的轨迹数量，可进行部分轨迹的同步或修剪，保证轨迹在时间上的相似。

（2）构建轨迹k匿名集

通常都采用聚类方法构造轨迹k匿名集。对每一个等价类中的轨迹聚类形成k匿名集，研究者们尝试了不同的聚类方法，如贪婪聚类法、密度聚类、层次聚类等，在聚类过程中利用轨迹之间的距离[26～30]作为衡量轨迹之间相似性的度量，以此找出等价类中最相似的k条轨迹构成k匿名集。

（3）轨迹数据发布

经过上一步骤形成轨迹k匿名集后发布轨迹数据，文献[6]利用每一个采样时间点的位置均值形成代表轨迹进行发布，也可在匿名集中选择代表性轨迹进行发布，如文献[31,32]。

经典的轨迹k匿名隐私保护方法是文献[6]中利用定位系统等设备本身具有无法精确定位的特性提出的（）匿名模型，如图2所示，也称为NWA（Never Walk Alone，NWA）方法，算法利用贪心聚类算法形成轨迹k匿名集，如果在第一步轨迹预处理阶段构成的等价类中，轨迹位置的采样点构成的轨迹圆柱的半径小于提前设定的不确定性阈值，则自动构成匿名集。否则，将利用空间转换将 k条轨迹在每个时刻的位置点平移到轨迹圆柱体内构成轨迹k匿名集，由于运动轨迹自有的不确定性使得轨迹圆柱内k条轨迹变得不可区分，达到k匿名的效果。NWA方法在构造轨迹k匿名集的过程中，计算两条轨迹之间的距离利用欧式距离函数，要求任何两条轨迹的起始和终止时间必须相同，并且两个轨迹对应的采样点必须匹配，而现实中所研究的轨迹数据很少能满足这样的要求。所以，文献[33]提出W4M 方法，改进NWA方法，在轨迹聚类阶段不再使用欧式距离而是利用EDR（Edit Distance on Real sequences，EDR）[34]距离函数计算两条轨迹之间的距离，该方法能解决在轨迹数据集聚类的过程中轨迹长度不匹配的问题。

图2 轨迹不确定模型

以上方法利用了轨迹的不确定性，对轨迹数据泛化，但是这两种方法构造的匿名集都不是在路网约束环境下。例如，虽然两条轨迹的距离很近，但是却彼此不可到达。影响了后续对轨迹数据挖掘的效率，由于轨迹数据发布的最终目的是要挖掘轨迹信息为生产生活服务。因此，文献[31]将轨迹数据集的时间和空间进行泛化，利用对数距离（Log Cost Distance）作为判断轨迹的相似性的度量，然后随机选择各个匿名区域采样位置点进行轨迹重组，最终发布随机重组后的原子轨迹，进而提高发布轨迹数据的利用效率。泛化原子轨迹tr1、tr2、tr3的过程如图3所示：将tr1与tr2泛化为匿名轨迹tr*，将tr3与tr*泛化为匿名区域，从图3可以看出5个位置点匹配成功，舍弃不匹配的位置点。轨迹重构和发布如图4所示，泛化后的各个采样时刻的位置点进行随机重组，发布原子轨迹数据，这有利于对轨迹数据的分析挖掘。文献[35]针对动态轨迹数据发布问题提出了一种基于自适应聚类的动态轨迹释放方法，可以处理实时加入的轨迹数据，文中将轨迹进行分段处理，该方法共两步：第一步是生成轨迹中的代表区域，可以解决由于移动速度和采样频率不同而引起的采样时间不对齐的问题；第二步利用提出的适应度函数对第一步中产生的代表区域进行聚类产生泛化区域，每个泛化区域至少含有个位置点，两个泛化位置区域内的位置点之间随机组合，这样就使得每两个泛化的区域之间满足k匿名。

以上的研究方法忽略了路网限制，文献[36]提出基于前缀树的轨迹k匿名算法，利用前缀树对轨迹数据进行分类，然而这个方法有两方面问题：一是路径推理攻击问题，当攻击者具有一定的背景知识，容易和稀疏路径相关联进行路径推理攻击；二是构建前缀树需要轨迹具有相同的前缀，但是现实中却存在很多的轨迹不满足具有相同的前缀，这使得利用前缀树进行匿名的结果为空集。文献[37]提出了针对路径推理攻击的轨迹隐私保护方法，假设攻击者具有公开的路网信息，文中提出了C-Tree(Cluster-Tree)方法加速聚类过程，不仅保证发布的轨迹数据满足轨迹k匿名，并且保证轨迹匿名结果满足路网限制。文献[38]首次提出利用频繁路径模式的方法进行轨迹隐私保护，提出了在路网环境下基于频繁路径的隐私保护方法，将轨迹分成若干个路段，移除不频繁路段，提出新的算法寻找最频繁路径，构造k匿名集，选出组中与其余轨迹相似度最高的轨迹作为每组的代表轨迹进行发布，既满足了路网约束，也避免了路径推理攻击。

图3 轨迹tr1、tr2、tr3泛化过程

图4 轨迹重组过程

3.4 基于差分隐私的轨迹隐私保护

轨迹K匿隐私保护虽然是比较主流的方法，但是却容易招受到攻击。如文献[29]提出的二次聚类攻击，虽然文献中也提出了针对二次聚类攻击的改进方法匿名模型以及基于该模型的聚类杂交隐私保护轨迹数据发布方法，但是在数据的利用效率方面却不够理想。

近年来，出现了以差分隐私[39,40]技术为基础的轨迹数据发布方法，差分隐私由于其严谨的数学形式使其能够保证无条件隐私，即使攻击者有部分背景知识也无法进行推断攻击。

文献[41]首次提出利用差分隐私方法解决大规模的轨迹数据发布的隐私保护问题，文中利用前缀树的方式存储轨迹数据，且利用拉普拉斯噪声机制将树中除了根节点外的每个节点加入噪音数值，并且针对独立的噪音容易产生数据不一致现象，提出了利用前缀树自身的特点对噪音数值进行了一致性处理，该方法面对轨迹数据的计数和频繁模式查询。文献[42]首次提出以空间泛化为基础的差分隐私算法，第一步利用差分隐私的指数机制将同一时刻的距离较近的采样点位置合并；第二步利用差分隐私的拉普拉斯机制对轨迹数据添加噪声数值。该方法解决了当前大部分研究方法中要求轨迹必须具有相同的前缀这一要求。路网中的移动轨迹一般都具有时间相关性，如果忽略这些相关性，将会产生隐私泄露，文献[43]针对这一问题提出了基于 “位置集合”的差分隐私保护技术，并且提出了新的函数敏感度衡量方法以及有效地位置扰乱机制，通过对位置集合内的敏感位置进行隐藏达到隐私保护的目的。当忽略了轨迹隐私保护中多个用户位置点之间的相关性问题时，容易遭受大量的推理攻击，文献[44]提出了能够保护具有相关性的多个用户位置隐私的差分隐私方法，利用隐马尔科夫相似度量量化两个用户位置的相关性，然后设计满足差分隐私的拉布拉斯噪声机制发布轨迹数据。文献[45] 针对空间计数查询，提出两种满足差分隐私的轨迹数据发布方法：（1）在自由空间中，基于噪音四分树的方法，对每个区域中的移动对象计数值添加噪音，发布每个时刻的添加噪音后的数值；（2）在路网空间中，用R-树索引路网中的路段，对路段中的移动对象计数值添加噪音后发布。当在空间中进行计数查询时，上述两种方法比 k-匿名模型的隐私保护度更高，如表1所示是几种轨迹数据隐私保护方法的比较。

表1 几种轨迹数据隐私保护方法的比较

4 聚类分析方法

4.1 基于密度的聚类

密度聚类算法假定聚类结构能通过数据样本点分布的紧密程度确定，密集数据点被稀疏区域分割，其思想是只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中，每个数据点的影响可以用一个数学函数形式化建模，称该函数为影响函数。描述数据点在其邻域内的影响，数据空间的整体密度可以用所有数据点的影响函数建模，然后，簇可以通过识别密度吸引点数学确定，代表性算法是Dbscan算法[46]、Optics算法[47]和Denlue[48]算法。该聚类算法可以克服基于距离聚类只能发现类圆形的聚类缺点，可以发现任何形状的聚类，并且对噪声数据不敏感。

4.2 基于模型的聚类方法

每个簇都可以用参数概率分布数学描述，整个数据就是这些分布的混合，其中每个单独的分布通常称为成员分布。因此，可以使用m个概率分布的有限混合密度模型对数据进行聚类，其中每个分布代表一个簇，需要顾及概率分布的参数，使得分布最好地拟合数据，EM（期望最大化）算法是一种流行的迭代求精算法，可以用来求得参数的估计值。

比较常用的是高斯混合模型（GMM）聚类。假设每个簇的数据都符合高斯分布，所有数据点呈现的分布就是多个高斯分布叠加之后的结果，所以用m个高斯分布密度函数的线性组合对所要分类的数据进行拟合，理论上高斯混合模型可以拟合出任意类型的分布。如图5所示是由两个高斯分布组成的混合分布的例子，显然利用高斯混合分布聚成两类比较合适。

图5 高斯混合分布

4.3 基于频繁模式的聚类方法

频繁模式是频繁出现在数据集中的模式，如子序列或子结构，通过频繁模式挖掘可以发现数据之间有意义的关联和相关，发现频繁模式起着至关重要的作用，对于数据分类、聚类等数据挖掘任务有帮助。频繁模式聚类的思想是，发现的频繁模式也可能预示簇，基于频繁模式的聚类非常适用于高维数据。

5 未来展望

在大数据时代将会产生大量的轨迹数据，轨迹数据以离散的时间序列形式表示，是包含时间和空间信息的采样序列，并且轨迹数据随着采样间隔具有显著的差异，因此轨迹数据隐私保护将有很多挑战性的问题需要解决。

5.1 基于混合模型的轨迹聚类分析

轨迹隐私保护中经常需要对轨迹进行聚类分析，需要对轨迹进行相似性度量。目前，大多数研究都利用欧氏距离、麦哈顿距离等度量两条轨迹的相似性，因此在计算轨迹距离时就必须考虑轨迹采样点之间的整体性。然而，异频采样使得轨迹之间不是同构的，且采样点也不服从均匀分布，因此不得不插入采样点或者删除采样点使得两条轨迹的采样频率一致，舍弃采样点有可能将重要信息舍弃，使后续轨迹数据利用效率低，添加采样点也有可能将不需要被保护的位置添加进来，从而也使后续轨迹数据利用效率降低。

轨迹数据其自身具有统计规律性，数据服从一定的概率分布模式，传统的基于K-means聚类等方法没有充分考虑轨迹数据自身分布不均匀的特性，因此本文第四部分介绍的基于密度的聚类、基于混合模型的聚类都可以用来研究轨迹聚类分析。它们都是基于数据分布的统计学特征进行聚类分析的，在对轨迹数据聚类分析时，可以克服采样频率不一致的困难，遵从数据本身分布的统计特性。

5.2 基于频繁模式挖掘的轨迹聚类分析

差分隐私可以防御攻击者具有任意背景知识的攻击，但是移动对象的轨迹具有相关性。当数据存在相关性时，差分隐私并不能保证无条件隐私。文献[49]提出当数据具有相关性的时候，差分隐私不能保证无条件隐私。大数据环境下，面对大规模的轨迹数据，攻击者可以关联多数据源对匿名后的轨迹数据信息进行推理攻击。前面提到文献[38]首次提出利用频繁路径模式的方法研究轨迹隐私保护，避免了路径推理攻击，因此利用数据的频繁模式挖掘的方法研究轨迹数据的隐私保护问题也是值得研究的问题。

5.3 个性化隐私保护研究

当前很多研究均认为所研究的轨迹数据都具有相同的隐私需求，设立同样的隐私保护标准，但是轨迹数据是由不同的移动个体产生的，不同的场景和移动对象可能会有不同的隐私需求，虽然已经有研究者考虑个性化隐私保护方案。如文献[50]基于时间划分提出一种能满足用户差异性需求到轨迹隐私保护算法，建立隐私保护矩阵，根据不同轨迹不同时段不同地点设定不同的隐私保护参数，实现差异隐私保护，但是关于个性化隐私保护的研究还不多。因此，基于不同隐私需求的个性化隐私保护研究也使值得研究的问题。

5.4 基于语义位置的轨迹隐私保护研究

有时候不需要整条轨迹都进行隐私保护，只是部分敏感语义位置信息需要保护。文献[51]提出基于语义轨迹的隐私保护方法，运动轨迹中用户访问和停留的位置更容易暴露用户的隐私，轨迹中用户经过的位置可以不做隐私保护，这将会提高发布轨迹数据的可用性，所以在轨迹隐私保护问题中应该考虑轨迹数据中的语义特征和攻击者的不同背景，合理的处理敏感位置数据和非敏感位置数据，能够更好的平衡隐私保护力度和数据的发布质量也是值得研究的问题。

6 结束语

随着大数据时代的到来，以及定位设备的不断发展，轨迹数据将会越来越多，对轨迹数据进行统计分析，在给人们生活带来便捷的同时，也对人们的隐私信息造成了泄露的风险。虽然研究者们不断提出轨迹隐私保护的新方法，但是同时越来越多的攻击模式也将会被开发出来，所以需要不断的完善轨迹隐私保护方法。本文总结了已有轨迹隐私保护的方法，并且对其进行了分析和比较，结合轨迹数据的统计分布特性，对未来轨迹隐私保护的研究方向进行了讨论。总之，虽然研究者们对轨迹隐私保护已经做了很多的研究，但是仍有很多关键的问题需要更深入的研究和探索。