基于抑制和敏感属性多样性的轨迹发布算法

邓劲松，王传安，吴延敏

（1.安徽科技学院 信息与网络工程学院，安徽 凤阳 233100；2.蚌埠学院 数理学院，安徽 蚌埠 233030）

引言

近年来，随着无线定位技术和5G 技术的快速发展，越来越多的移动对象轨迹数据被服务提供商收集，其蕴含丰富时空信息促进了轨迹数据挖掘研究的发展。然而轨迹数据通常包含用户大量敏感信息，不恰当的轨迹数据发布将泄露用户隐私，威胁移动对象人身安全[1-2]。比如攻击者已获取到某用户地理社交网络部分签到数据，再结合数据挖掘方提供的地理社交网络完整数据集，将大概率推测出用户访问的其他位置信息[3]。因此，轨迹数据发布过程用户隐私保护成为国内外学者的关注重点。

当前，国内外学者在轨迹数据发布隐私保护算法研究上，基于假数据、抑制法和泛化法等方式取得大量研究成果[4-9]。然而高维轨迹数据发布存在记录关联攻击和属性关联攻击威胁，传统轨迹数据隐私保护算法不能有效应用于高维轨迹数据发布[10]，国内外学者对相关领域的研究取得大量研究成果：Chen 等人[11]基于KCL-隐私模型提出局部抑制和全局抑制相结合的隐私保护算法，保证了轨迹数据挖掘效果；Komishani 等人[12]考虑不同用户对个人轨迹隐私保护需求不同，提出一种支持敏感属性泛化和局部抑制的隐私保护算法，该算法基于轨迹隐私保护强度来获取违反序列集合，并通过对定长的关键子序列采用序列抑制和敏感属性泛化决策树来消除违反序列集合；Terroviti 等人[13]针对记录关联攻击问题上，提出基于全局抑制、局部抑制、轨迹分割和抑制与分割混合的四种匿名算法，并通过对比实验指出轨迹分割和抑制与分割混合的算法更能保证数据后续实用性；Al-Hussaeni 等人[14]重构前缀树顶点到根路径上的c(v)，提出添加Laplace 噪声的SafePath 差分隐私算法；陈等人[15]通过添加假轨迹或者抑制轨迹的预处理操作计算问题点收益得分，并依据单点收益得分提出对违反序列集合进行轨迹匿名处理的SPG 算法；Lin 等人[16]设计轨迹最大收益极限估计方法及剪枝策略，然后利用剪枝策略提出全局抑制和局部抑制结合的隐私保护算法；Li 等人[17]建立轨迹分类树，通过对叶子节点进行噪声处理来满足局部抑制效果的隐私保护算法。

目前现有高维轨迹数据隐私保护算法主要采用抑制技术来设计：通过对数据集可能存在隐私泄露的轨迹序列执行时空点抑制。然而属性关联攻击威胁是攻击者依据受害者部分轨迹序列推断用户敏感属性的隐私保护问题，如果对数据集采用时空点抑制处理，容易出现全局抑制情况，造成数据实用性损失率高，如果对数据集采用敏感属性泛化处理，容易出现敏感属性泛化严重现象，造成数据失真度明显。

因此，本文针对高维轨迹数据发布过程存在的隐私泄露问题，提出一种支持局部抑制和敏感属性局部多样性的隐私保护算法(TPP-SS,Trajectory Privacy-Preserving based on local Suppress and local diversity Sensitive attribute)。该算法对违反KCL-隐私模型的最小违反序列进行分类处理：对记录关联攻击的轨迹序列，设计消除时空点隐私泄露的权值函数，并迭代选择时空点进行局部抑制操作；对属性关联攻击的轨迹序列，迭代选择敏感属性推断率低的最小违反序列进行敏感属性局部l-多样性处理。通过充分实验，验证了本文匿名算法得到的匿名轨迹数据集实用性更高。

2 相关概念

2.1 轨迹模型

定义1(轨迹trajectory[18-19])轨迹是移动对象若干个位置信息按照时间排序得到的连续线段，形式化表示为：tr={loc1t1→loc2t2→…→locntn}，其中lociti(1≤i≤n)称为时空点(doublet)，表示用户在ti时刻所处位置信息是loci，(lociti→loci+1ti+1→…→locjtj)(1≤i≤j≤n)称为轨迹序列，|tr|称为轨迹长度，即轨迹包含不同时空点的个数。

定义2(轨迹数据trajectory data)由用户轨迹和敏感属性构成的集合称为轨迹数据，形式化表示为：tsi={oi,tri,si}，其中oi称为用户标识符，tri表示第i个用户轨迹，si表示用户敏感属性，其值可能是敏感值，也可能是非敏感值。

通常情况下，将若干个用户轨迹数据组成集合称为轨迹数据集，形式化表示为：TS={ts1,ts2,…tsn}。特别的，如果TS 包含不同时空点个数多，且各轨迹间重叠率低，则轨迹数据集被看成高维轨迹数据集。

定义3(KCL-隐私模型[10]) 假设K 为用户轨迹数据匿名个数，C 为用户轨迹数据敏感值推断概率，L 为用户轨迹数据被攻击者获取的最大轨迹序列长度，则高维轨迹数据集TS 满足KCL-隐私模型当且仅当∀0＜|q|≤L轨迹序列q和敏感值s满足：

(1)|TS(q)|≥K，即要求用户轨迹数据匿名个数最少K 个，其中TS(q)表示包含轨迹序列q的轨迹数据集合，|TS(q)|表示TS(q)中轨迹数据个数，且

(2)Conf(s|TS(q))=≤C(0＜C≤1)，即要求用户轨迹数据敏感值推断概率不超过C，其中TS(q∪s)表示同时包含轨迹序列q和敏感值s的轨迹数据集合，|TS(q∪s)|表示TS(q∪s)中轨迹数据个数。

通常情况下，将高维轨迹数据集TS 中最小违反序列(minimal violating sequence，简称mvs)[10]组成的集合称为最小违反序列集，记为MVS(TS)，形式化表示为：MVS(TS)={mvs1,mvs2,…,mvsn}。

2.2 轨迹抑制权重函数

对轨迹数据集进行隐私保护匿名处理，隐私保护强度的提升会造成数据实用性的损失。为均衡隐私保护强度和数据实用性，本文考虑轨迹序列q数据集挖掘价值:时空点个数和关联最大频繁序列(maximal frequent sequence，简称mfs)[20]个数，设计新的轨迹抑制权重函数：

给定时空点p和包含p的mvs，定义抑制操作消除mvs权值函数等式为：

该权重值越大，表明轨迹数据集匿名效果越优。其中priGainPer(p)表示抑制TS(mvs)中p后隐私保护提高率，infoLossPer(p)表示抑制TS(mvs)中p后数据实用性损失率，其计算公式分别如下：

其中mvsDel(p)表示抑制TS(mvs)中p后MVS(TS)变化量，|MVS(TS)|表示初始MVS(TS)中最小违反序列个数。

其中doubletDel(p)表示消除mvs需抑制p数量，|TS(p)|表示包含时空点p的轨迹数据个数，mfsDel(p)表示消除mvs造成MFS(TS)[21]变化量，|MFS(TS)|表示初始MFS(TS)中mfs总数。

3 隐私保护算法

3.1 TPP-SS 算法描述

本文对高维轨迹数据存在隐私泄露的轨迹序列进行匿名处理时，提出支持局部抑制和敏感属性局部多样性的匿名算法（TPP-SS），该算法主要分为两个子算法：1)对轨迹数据集违反KCL-隐私模型的最小违反序列分类；2）对分类后的最小违反序列分别进行时空点局部抑制和敏感属性局部l-多样性操作。具体如下：

3.1.1 最小违反序列分类

对高维轨迹数据发布进行匿名处理时，首先需要获取数据集存在记录关联攻击和属性关联攻击的最小违反序列，由于文献[10]已提出有效MVS 生成子算法，因此本文在给定敏感值集合S基础上，基于MVS 生成子算法设计MVSC 分类算法，伪代码如下：

算法1 首先调用MVS 生成子算法获取MVS(TS) (Line 2)，然后对集合MVS(TS)进行分类处理：给定mvs，如果|TS(mvs)|＜K，表明mvs存在记录关联攻击，需要进行时空点抑制处理，将其存储到seqMvs 集合(Line 6)，否则表明mvs 存在属性关联攻击，需要进行敏感属性局部l-多样性操作，将其存储到senMvs 集合(Line 8)。此外，算法1 为方便敏感属性局部l-多样性算法设计，总是将S 各敏感值s 的Conf(s|TS(mvs))存储于sen-MvsScore 集合(Line 9)。

3.1.2 敏感属性局部l-多样性算法

敏感属性局部l-多样性操作主要是对部分轨迹数据进行敏感属性的非敏感值添加操作，使得敏感属性信息存在多个，从而降低敏感值推断概率。算法2 给出本文敏感属性局部l-多样性操作算法。对给定mvs和敏感值s，算法2 首先获取TS(mvs)中包含敏感值的轨迹数据集合TS1，并对TS1进行预处理操作(Line 3-6)：记录TS1中每个轨迹数据tra包含mvs′个数，存入Count 集合；然后计算敏感属性的非敏感值添加个数add(Line 7)，主要依据两点：第一是根据senMvsScore 计算Conf(s|TS(mvs))满足KCL-隐私模型的非敏感值最少添加轨迹数据个数(见定理1)，第二是生成0 到10 之间随机数，使得敏感值推断概率动态变化；最后迭代从Count 中选择包含mvs′个数最多的轨迹数据进行敏感属性的非敏感值添加操作(Line 8-13)，直到添加数量达到add为止，该步骤遵循两个原则：一是本文敏感属性局部l-多样性选择2-多样性，因此每个操作轨迹数据tra添加一个非敏感值，二是打乱轨迹数据tra中原有敏感值和添加的非敏感值顺序。此外，算法2 额外的操作是存储非敏感值添加后轨迹数据tra′(Line 12)。算法2 伪代码如下：

定理1：对高维轨迹数据集进行敏感属性局部l-多样性操作后满足KCL-隐私模型。

证明：给定存在属性关联攻击的mvs和敏感值s，假设轨迹数据集|TS(mvs)|=m，|TS(mvs∪s)|=n，那么由KCL-隐私模型可知：|TS(mvs)|=m＞K和Conf(s|TS(mvs))＞C，即：

假设存在最小正整数t，使得从TS(mvs∪s)中选择t条轨迹数据进行敏感属性局部l-多样性匿名操作后，匿名轨迹数据集TS′满足KCL-隐私模型。

下面证明匿名TS′轨迹数据匿名个数满足KCL-隐私模型，考虑敏感属性局部l-多样性操作只会影响轨迹数据包含的敏感属性个数，因而TS′包含mvs轨迹数据个数不发生改变，即|TS′(mvs)|=m＞K恒成立，可得到：匿名TS′轨迹数据匿名个数满足KCL-隐私模型；

再证明匿名TS′敏感值推断概率满足KCL-隐私模型，因TS(mvs∪s)中有t条轨迹数据进行敏感属性局部l-多样性处理，使得TS′中这t条轨迹数据包含的敏感属性存在l个，其每条轨迹数据作为判断同时包含mvs和s的概率从1 降低到1/l，另外n-t条轨迹数据未进行处理，其在TS′中作为判断同时包含mvs和s概率仍为1，那么|TS′(mvs∪s)|=(n-t)*1+1/l*t中，可计算：

又因匿名TS′的Conf(s|(TS′(mvs))满足KCL-隐私模型，即:

那么(5)和(6)联立，可推出：

考虑l＞1，对(7)进行再化简，可得：

根据等式(4)可知：l(n-Cm)/(l-1)＞0。

所以能找到最小正整数t，即t=[l(n-Cm)/(l-1)](向上取整)，使得从TS(mvs∪s)中选择t条轨迹数据进行敏感属性局部l-多样性处理后，匿名TS′的Conf(s|(TS′(mvs))满足KCL-隐私模型，即匿名TS′敏感值推断概率符合KCL-隐私模型。假设成立。

综上所述：对高维轨迹数据集进行敏感属性局部l-多样性操作后满足KCL-隐私模型。

3.1.3 TPP-SS 算法

确定敏感属性局部l-多样性匿名操作算法后，考虑文献[11]提出KCL-Local 算法可以有效消除seqMvs，本文TPP-SS 算法在时空点局部抑制操作上，设计新的轨迹抑制权重函数(等式(1))，并基于该权重值调用KCL-Local 算法消除数据集seqMvs 集合，TPP-SS 算法具体伪代码如下：

算法3 首先根据算法1 获取数据集存在隐私泄露的mvs分类集合seqMvs 和senMvs，并记录senMvs 集合中各敏感值推断概率集合senMvsScore(Line 2)，然后调用算法2 对senMvsScore 进行如下操作(Line 3-10)：迭代选择senMvsScore 集合中最低推断概率mvs 进行敏感属性局部l-多样性操作，因为推断概率越低表明敏感值推断概率越接近C，非敏感值添加个数越少，轨迹数据集扰动越小，并依据opTra 集合对数据集和sen-MvsScore 进行更新操作(Line 6-9)，最后依据等式(1)对seqMvs 调用KCL-Local 算法进行时空点局部抑制处理(Line 11)。

3.2 复杂度分析

TPP-SS 算法时间复杂度主要由三部分组成。第一部分是对MVS 集合进行分类操作，这部分花费时间的操作是扫描数据集判断轨迹序列在最大轨迹长度限制下隐私泄露风险，由于轨迹数据集中轨迹序列候选集合上限为|d|L[10]，则算法1时间复杂度上限为O(|d|L|TS|)[10]，其中|d|为轨迹数据集维数，|TS|为高维轨迹数据集记录数；第二部分是敏感属性局部l-多样性操作。这部分花费时间操作是扫描数据集选择敏感属性局部l-多样性操作的轨迹数据集合，由于|senMvs|＜＜|d|L，极端情况下，每个最小违反序列扫描一次数据集，则算法2 时间复杂度上限是O(|d|L|TS|)；第三部分是计算时空点抑制得分，这部分花费时间的操作是判断时空点抑制方式，其算法时间复杂度上限是O(|d|L|TS|)[11]。综上所述，TPP-SS 算法的时间复杂度上限是O(|d|L|TS|)。

3.3 算法衡量标准

数据实用性是衡量轨迹数据集匿名效果的重要参数，考虑高维轨迹数据实用性衡量主要是时空点损失率和MFS 损失率[10]，本文将依据这两个标准来评价TPP-SS 算法：

(1)时空点损失率

时空点作为判断原始轨迹数据集各轨迹与匿名轨迹数据集对应轨迹相似度的重要参数，其损失率越低，表明原始轨迹数据集与匿名轨迹数据集相似度越大，用于后续数据挖掘效果越优。因此，时空点损失率DoubletLoss 计算公式如下：

其中 |tri|表示原始轨迹数据集中轨迹tri(1≤i≤|TS|)时空点个数，|tr′j|表示匿名轨迹数据集中轨迹tr′j(1≤j≤|TS′|)时空点个数。

(2)MFS 损失率

MFS 作为轨迹数据挖掘提供个性化推荐服务的重要依据，其损失率越低，表明原始轨迹数据集与匿名轨迹数据集的最大频繁序列越接近，将其作为个性化推荐服务参考依据越准确，推荐服务质量越高。因此，最大频繁序列损失率MFSLoss计算公式如下：

其中U(TS)和U(TS′)分别表示原轨迹数据集MFS 个数和匿名轨迹数据集MFS 个数。

4 实验

4.1 实验数据集

实验部分采用合成数据集MetraData[14]来测试TPP-SS 算法数据实用性。MetraData 数据集是一个模拟拥有65 个都市车站100000 个行人在60分钟内移动轨迹的合成数据集，其敏感属性包含四个属性值，且只有一个被当作敏感值。实验的硬件环境为：Intel(R)Core(TM) i5-4300U CPU @1.90GHz 2.5GHz,8GB 内存，操作系统为Microsoft Windows 7，算法使用JAVA 语言实现。

4.2 实验结果与分析

根据3.3 节提出的算法衡量标准，本文匿名算法敏感属性局部l-多样性选择敏感属性局部2-多样性，并将其与文献[10]提出基于全局抑制KCLGlobal 算法和文献[11]提出基于局部抑制KCLLocal 算法进行充分实验对比。图1-图3 展示三个算法在时空点损失率和MFS 损失率对比结果。

图1 vary.K（C=0.6,L=3,Support=800）

图2 Vary.C（K=30,L=3,MFS.Support=800）

图3 Vary.MFS.Support（K=30,L=3,C=0.6）

图1 是变化匿名参数K 的三个算法实验对比结果。从图1(a)-(b)可知：当固定参数C=0.6、L=3和MFS.Support=800 时，参数K 从20 递增到40，时空点损失率和MFS 损失率逐渐递增。这是因为参数K 递增，轨迹数据集存在隐私泄露的最小违反序列个数递增，时空点抑制个数递增，造成时空点损失率和MFS 损失率递增。相比于KCLLocal 算法，本文算法消除最小违反序列采用不同操作：对记录关联攻击保护上，设计抑制权重计算函数，对属性关联攻击保护上，敏感属性局部2-多样性有效降低了时空点被抑制个数，进而降低MFS 损失率；相比于KCL-Global 算法，局部抑制和敏感属性局部2-多样性操作更能有效保证数据集后续实用性。

图2 是在参数K=30，L=3，MFS.Support=800相同情况下，变化匿名参数C 的对比实验结果。从图2(a)-(b)可看出：TPP-SS 算法的时空点损失率和MFS 损失率始终优于KCL-Local 算法和KCL-Global 算法，且TPP-SS 算法的时空点损失率和MFS 损失率保持不变。这是因为TPP-SS 算法对存在属性关联攻击的最小违反序列采用敏感属性局部2-多样性操作，该操作主要是对敏感属性进行非敏感值添加，不影响数据集时空点和MFS 损失个数，故时空点损失率和MFS 损失率保持不变，而KCL-Local 算法和KCL-Global 算法在消除数据集属性关联攻击上，采用抑制时空点操作，且随着匿名参数C 递增，存在属性关联攻击的最小违反序列递减，因而时空点抑制个数递减，时空点损失率和MFS 损失率递减。

图3 展示参数MFS.Support 对MFS 损失的影响。从图3 得出：MFS 损失率随着参数MFS.Support 递增而递减。由于局部抑制比全局抑制有效降低时空点抑制个数，使得TPP-SS 算法和KCL-Local 算法在MFS 损失率上优于KCLGlobal 算法。随着MFS.Support 从200 增加到1000，数据集|MFS(TS)|个数逐渐降低，且MFS(TS)集合中最大频繁序列与轨迹关联性越来越强，使得时空点抑制操作对MFS 损失的影响变小，造成MFS 损失率降低。本文算法对时空点进行抑制操作时，将时空点损失率和MFS 损失率引入抑制权重函数设计中，有效降低了MFS 损失率。

5 总结

本文基于攻击者获取用户最大轨迹序列长度的实际假设，重点研究高维轨迹数据发布过程存在的隐私泄露问题，首先对数据集违反KCL-隐私模型的最小违反序列进行记录关联攻击和属性关联攻击分类，然后对不同类型的最小违反序列采用不同操作：若最小违反序列属于记录关联攻击，设计轨迹抑制权重函数，并依据该权值对数据集进行时空点局部抑制操作，否则对数据集进行敏感属性局部l-多样性操作，从而实现用户隐私的保护。实验结果验证TPP-SS 算法在时空点损失率和MFS 损失率上优于仅使用抑制操作的隐私保护算法。下一阶段的研究工作是对隐私保护后的匿名轨迹数据集进行数据挖掘研究，帮助服务提供商更好地为用户提供个性化推荐服务，同时尽可能实现推荐服务过程中的隐私保护。