轨迹数据发布中基于敏感语义位置的隐私保护算法

俞望年，宣占祥，马小明，岳威，左开中,2

（1.安徽师范大学计算机与信息学院，芜湖 241002；2.安徽师范大学网络与信息安全安徽省重点实验室，芜湖 241002）

0 引言

近年来，随着移动智能设备的普及和定位技术的发展，人们的海量轨迹数据被收集、存储、挖掘和分析[1-4]。然而轨迹数据含有大量的个人隐私信息，例如社会身份、家庭住址、身体健康状况、工作场所以及日常行程等，若不经处理直接发布轨迹数据，将会泄露个人隐私信息[5-6]。因此，如何保证发布的轨迹数据具有较高数据可用性的同时，保护用户的敏感隐私信息，已成为国内外学者关注的热点。

常用的轨迹隐私保护方法有K 匿名法[7-10]、假轨迹法[11-12]、抑制法[13-14]和差分隐私法[15-16]。文献[7]提出（K，δ）-隐私保护算法，利用轨迹数据不确定性进行轨迹聚类，对轨迹位置进行隐私保护。文献[8]利用网格技术对轨迹位置点进行空间泛化以满足K 匿名，进而将轨迹转换为连续网格序列。文献[9]认为并非轨迹上的所有采样位置都要进行匿名处理，通过停留位置提取算法获取轨迹数据中的停留位置，再利用网格划分技术和K 匿名构建匿名区域，进一步保护用户敏感隐私信息。文献[10]利用挖掘到的真实兴趣点数据，提出（K，L）-隐私模型，利用网格划分技术为停留位置构建匿名区域，使得匿名区域满足K 匿名和L 语义差异性。文献[11]通过计算虚假轨迹和真实轨迹的K 个交叉点，随机生成交叉点间轨迹。文献[12]随机选择轨迹采样位置点，将用户真实轨迹进行不同角度旋转生成潜在虚假轨迹。文献[13]通过对轨迹数据中的敏感或者频繁访问位置进行抑制处理，保护隐私信息。文献[14]提出一种基于单点收益的轨迹隐私保护方法，通过计算收益结果，在轨迹数据集中抑制位置或者添加假轨迹，减少信息损失率。文献[15]利用隐马尔科夫模型度量用户位置相关性，通过设计满足差分隐私的拉布拉斯噪声机制保护用户隐私信息。文献[16]利用四叉树和R树数据结构，提出两种满足差分隐私的轨迹数据发布方法。然而，这些方法存在信息损失率过大导致的数据可用性较低问题，同时没有充分考虑用户所处语义位置信息，存在语义推断攻击[17-18]，导致用户敏感隐私泄露。

基于此，本文提出一种基于敏感语义位置的轨迹数据隐私保护算法，通过对用户敏感的语义位置进行匿名处理，构建语义安全匿名区域，提高位置隐私保护程度，同时减少对非敏感语义位置的匿名处理，降低信息损失率，提高轨迹数据可用性。

1 预备知识

1.1 相关定义

定义1（语义位置）是指具有坐标、语义位置类型（如学校、商场等）和流行度等特征的位置，记为loc={address，type，（lon，lat），P（loc）}。其中：address 为语义地址；type 表示语义位置类型；（lon，lat）表示语义位置经纬度；P（loc）表示语义位置流行度。本文根据地理标签将语义位置类型分为10 种，如图1 所示。此外，语义位置是否敏感由用户定义，例如医院，部分患者认为是敏感的，医生则认为是非敏感的。

图1 语义位置地理标签分类

定义2（语义位置流行度）是指用户访问该语义位置的概率。 设 loc 是一个语义位置，U(loc)={u1,u2,…,um} 是访问过该语义位置的用户集合，并设nj是用户uj对loc 的访问次数，该语义位置被访问的总数记为因此该语义位置的流行度定义为P(loc)=2H(loc)，其中：它表示该语义位置的信息熵，即被用户访问的可能性。

图2 语义位置Voronoi图

定义3（语义位置Voronoi 图）是指以语义位置为生成元构建的Voronoi 图，如图2 所示。每个语义位置的 Voronoi 单 元 满 足Voronoi(loci)={x：d(x,loci)≤d(x,locj),loci≠locj}，其中：d（x，loci）表示 x 到语义位置 loci的欧式距离；x 表示任意位置。

定义4（语义轨迹）是指将原始轨迹上的采样位置按时间顺序语义化为移动对象停留位置序列，记为其中：表示第 i 个用户身份标识符，表示STi的第j 个停留位置。为了简便，系统会自动将停留位置转化为最近邻语义位置。

定义5（隐私需求）是指用户的隐私保护需求，记为PR={θ,senstype}，其中：θ表示用户定义的语义安全阈值；senstype 表示用户定义的敏感语义位置类型集。

定义6（匿名区域）是指一个用来隐藏用户语义位置的空间区域，记为CR={Voronoi(loc1),…,Voronoi(loci),...,Voronoi(locm)}，其中：ioVoronoi(loci)表示语义位置loci所处的Voronoi 单元。

定义7（θ-语义安全匿名区域）已知一个匿名区域CR 和一个用户u，CR 中属于u 的敏感语义位置用senslocsu表示，则匿名区域敏感语义位置总流行度记为POP（senslocsu），匿名区域语义位置总流行度记为POP（all），匿名区域语义安全程度用d（CR）表示：

若匿名区域的语义安全程度d(CR)≤u.PR.θ，我们就称CR 对用户u 来说是一个θ-语义安全匿名区域。

1.2 系统架构

本文系统架构如图3 所示。

图3 系统架构

该架构包括客户端、轨迹收据收集服务器、原始轨迹数据库、隐私保护算法服务器、可发布轨迹数据库4个组件。客户端负责记录用户轨迹数据，并将记录的轨迹数据发送给轨迹数据收集服务器，轨迹数据收集服务器接收客户端发送的轨迹数据，原始轨迹数据库存储轨迹数据收集服务器接收到的轨迹数据，隐私保护算法服务器对原始轨迹数据进行停留位置提取、匿名区域生成和轨迹匿名处理处理，匿名后的数据存储在可发布轨迹数据库中。

2 基于敏感语义位置的轨迹数据隐私保护算法

2.1 算法设计

本文充分考虑用户的隐私需求和轨迹数据可用性问题，提出一种基于敏感语义位置的轨迹数据隐私保护算法，主要思想如图4 所示。

图4 算法流程图

具体步骤如下：

（1）利用语义位置进行Voronoi 图划分。

（2）从原始轨迹的采样位置数据中提取用户停留位置。

（3）若停留位置处于非敏感语义位置的Voronoi 单元中，则不进行匿名处理；若处于敏感语义位置的Voronoi 单元中，则将该Voronoi 单元加入匿名区域，执行步骤（4）。

（4）遍历所有与匿名区域相邻近的语义位置，根据用户设置的敏感语义位置类型，优先添加流行度最大的非敏感语义位置，其次选择流行度最小的敏感语义位置。

（5）将该语义位置对应的Voronoi 单元加入匿名区域，若匿名区域语义安全程度满足用户设定的语义安全阈值，返回该匿名区域；否则，执行步骤（4）。

算法1 给出了基于敏感语义位置的轨迹数据隐私保护算法（Sensitive Semantic Location Privacy Protection Algorithm for Trajectory Data，SSLPP）的伪代码。首先将原始轨迹traj 转换为语义轨迹ST（第3 行），遍历ST 中的每一个停留的语义位置loc（第4 行），若处在敏感语义位置（第5 行），将该语义位置所在Voronoi 单元加入匿名区域（第6 行）；其次根据PR.senstype 添加匿名区域邻近Voronoi 单元，直至满足语义安全阈值（第7-16行），并用该匿名区域替换loc（第17 行）；然后扫描原始轨迹traj 中的每一个采样位置，将敏感的停留位置转换为ST 中的相应匿名区域，同时若有采样位置被ST 中的相应匿名区域覆盖，则使用该匿名区域替代采样位置，形成可安全发布的轨迹traj*，并将traj*放入轨迹数据库 D*（第 20-21 行）；最后返回 D*（第 23 行）。

算法1 基于敏感语义位置的轨迹隐私保护算法

输入：语义位置Voronoi 图、原始轨迹数据库D、隐私需求PR

输出：可发布的轨迹数据库D*

1）D*=∅ ；

2）For traj∈Ddo

3）转换为语义轨迹ST={loc1,loc2,...,locn}；

4）Forloc∈STdo

5） Ifloc.type∈PR.senstypethen

6）CR=GetVoronoi(loc)；∕∕获 取 loc 所 在 Voronoi单元

7） While（d(CR)>PR.θ）do

8）NSset=GetNSLinks(CR,PR.senstype)；∕∕记录非敏感语义位置

9）SNset=GetSNLinks(CR,PR.senstype)；∕∕记 录 敏感语义位置

10） IfNSset≠ ∅ then

11）loclink=SelectMaxpop(NSset)；∕∕选择流行度最大的语义位置

12） Else

13）loclink=SelectMinpop(SNset)；∕∕选择流行度最小的语义位置

14） End if

15）CR=CR⋃Voronoi(loclink)；

16） End while

17） 用 CR 替换 loc；

18）End if

19）End for

20）根据 ST 将 traj 转换为 traj*；

21）D*=D*⋃traj*；

22）End for

23）Return D*；

2.2 算法分析

在轨迹数据发布中，真正泄露用户隐私的是用户停留的语义位置。因此，SSLPP 算法在此基础上，考虑到用户对不同语义位置的访问具有差异性，利用真实数据计算各语义位置流行度。充分考虑用户的隐私需求，根据用户设置的敏感语义位置类型和语义安全阈值对停留的语义位置进行有选择的构建θ-语义安全匿名区域，保护用户敏感隐私信息。因为当用户处于敏感语义位置时，构建的匿名区域CR 至少还包含一个非敏感语义位置，这是因为若没有非敏感语义位置，CR的语义安全程度d（CR）=1，无法满足用户设置的θ阈值，因此增加攻击者推测用户敏感隐私信息的难度。

在轨迹数据可用性方面，SSLPP 算法使用信息损失率[19]来进行衡量，计算公式如下：

其中：ILAave表示停留位置转化为匿名区域后的平均信息损失率；n 表示轨迹条数，m 表示每条轨迹上的采样位置数，Asp 表示所有轨迹上的采样位置数，Area（Zone（Ti，Sampij））表示第i 条轨迹的第j 个采样位置所属的匿名区域面积。信息损失率越低，数据可用性越高；反之，数据可用性越差。由于SSLPP 算法仅针对用户敏感的停留位置进行隐私保护，减少匿名处理规模。因此，SSLPP 算法可以降低信息损失率，提高轨迹数据可用性。

3 实验及结果分析

3.1 实验设置

本文对比了文献[7]的（K，δ）算法、文献[9]的 Grid-Partition 算法和文献[10]的 SSAC 算法。其中：（K，δ）算法是对轨迹数据中的所有采样位置进行匿名处理，K 默认设置为 6，δ取值为 500，1000，1500，2000；GridPartition算法对轨迹数据中的停留位置进行K 匿名处理，K 默认设置为6；SSAC 算法对轨迹数据中的停留位置进行（K，L）匿名处理，K 默认设置为 6，L 默认设置为 3。

所有的匿名算法均用Java 实现，并运行在一台配置为 Intel Core i5-4200M CPU@2.5GHz，12GB 内存的Windows 10 计算机上。实验数据采用北京PoI（Point of Interest）数据[10]作为语义位置，敏感语义位置类型设置为{休闲娱乐，住宿，科教文化}，随机选取Geolife 数据[9]中 100 个用户的 10129 条轨迹，共计 16021938 个采样位置。经过停留位置提取算法[9]后得到27116 个停留位置，具体分布如图5 所示。表1 列出了实验参数具体信息。

表1 实验参数设置

图5 停留位置可视化

图6 θ值变动

3.2 实验结果分析

（1）θ值变动的影响

图6 描述θ值变动对信息损失率和运行时间的影响，其中语义位置数为50000，敏感语义位置类型为{休闲娱乐，住宿，科教文化}。由于（K，δ）算法、GridPartition 算法和SSAC 算法不考虑语义安全性，因此只对SSLPP 算法进行实验验证。

由图 6（a）可知，随着θ值的增加，SSLPP 算法的信息损失率不断降低，这是因为θ值增大，构建语义安全匿名区域需要添加的相邻语义位置越少，使得匿名区域面积相应减小，降低信息损失率。

由图 6（b）可知，随着θ值的增加，SSLPP 算法的执行时间不断减少，这是因为θ值增大，匿名区域扩展添加Voronoi 单元次数逐渐减少，降低算法执行时间。

（2）敏感语义位置类型数量的影响

图7 描述敏感语义位置类型数量的变动对信息损失率和运行时间的影响，其中语义位置数量为50000，θ值为0.6。

由图7（a）可知，随着敏感语义位置类型数量的增加，SSLPP 算法的信息损失率不断增加，但始终低于（K，δ）算法、GridPartition 算法和 SSAC 算法。这是因为敏感语义位置类型数量增多，SSLPP 算法需要匿名处理的停留位置增多，相应信息损失率逐渐增加。但GridPartition 算法和SSAC 算法对所有停留位置进行匿名处理区域；（K，δ）算法是对轨迹数据中的所有采样位置进行匿名处理，因此信息损失率始终高于SSLPP算法。

由图7（b）可知，随着敏感语义位置类型数量的增加，SSLPP 算法匿名时间不断增加，但始终低于（K，δ）算法、GridPartition 算法和 SSAC 算法。这是因为SSLPP 算法仅对停留的敏感语义位置进行匿名处理，减少匿名处理规模，减少算法运行时间。

（3）语义位置数量的影响

图8 描述语义位置数量的变动对信息损失率，其中敏感语义位置类型为{休闲娱乐，住宿，科教文化}，θ值为0.6。

由图8 可知，随着语义位置数量的增加，SSLPP 算法信息损失率不断降低，且始终低于（K，δ）算法、Grid-Partition 算法和SSAC 算法。这是因为语义位置数量越多，非敏感语义位置数量相应增加，使得扩展添加Voronoi 单元次数减少，缩减匿名区域面积，从而降低信息损失率。（K，δ）算法不考虑语义位置，因此信息损失率不受语义位置数量变化的影响。随着语义位置数量的增加，GridPartition 算法和SSAC 算法信息损失率不断降低，但降低幅度较小。

4 结语

本文针对利用轨迹数据进行数据挖掘的场景，提出一种基于敏感语义位置的轨迹隐私保护算法。该算法根据移动对象设置的敏感语义位置类型和语义安全阈值对停留位置进行泛化处理，不仅可以避免语义推断攻击，而且可以降低信息损失率，从而提高轨迹数据可用性和敏感隐私信息保护程度。

图7 敏感语义位置类型数量变动

图8 语义位置数量变动

然而，本文算法没有充分考虑城市交通路网和语义位置的时间维度。因此，下一阶段的研究可以结合城市路网和时间维度构建匿名区域，进一步增强隐私保护程度。