实现轨迹km-匿名的最小变形度算法

郭 会，韩建民，鲁剑锋，彭 浩，郑路倩

（浙江师范大学数理与信息工程学院，浙江金华321004）

实现轨迹km-匿名的最小变形度算法

郭 会，韩建民，鲁剑锋，彭 浩，郑路倩

（浙江师范大学数理与信息工程学院，浙江金华321004）

km-匿名可以抵制长度为m的背景知识攻击，然而现有的匿名化算法在泛化处理时，优先选择支持度最小的位置点进行处理，未考虑泛化造成的变形度。随着m值的增大，轨迹变形度会变大。针对该问题，提出2种匿名化算法：最小变形度贪心算法和基于先验原则的最小变形度贪心算法，2种算法优先选择变形度最小的位置点进行泛化，使得泛化所造成的变形度更小，并给出匿名轨迹可用性度量方法，对数据可用性和算法效率进行分析。实验结果表明，与现有的匿名化算法相比，2种算法均可生成可用性更高的匿名轨迹。

隐私保护；km-匿名；轨迹；背景知识攻击；点泛化变形度

1 概述

时空背景知识攻击是匿名轨迹的主要攻击形式。所谓时空背景知识攻击是指攻击者基于拥有的移动对象的部分时空信息，在发布的轨迹数据库中推断出该移动对象的轨迹信息。针对时空背景知识攻击，目前常用的匿名模型是轨迹k-匿名［1-3］，其思想是使轨迹数据库中任意一条轨迹至少与其他k-1条轨迹无法区分，这样即使攻击者拥有用户轨迹全部的时空背景知识，能够在发布轨迹数据库中推导出该用户的真实轨迹的概率也不超过1/k，从而保护了用户隐私［4-6］。然而轨迹k-匿名要求k条轨迹所有时空点都不可区分，约束过强，匿名化过程会造成较大的信息损失。实际中，攻击者拥有轨迹的全部时空知识是相当困难的，通常攻击者只拥有了用户的部分时空背景知识，匿名轨迹只要能够抵制部分时空背景知识攻击就可以了。基于该思想，文献［7］提出了km-匿名模型，该匿名模型要求匿名轨迹数据库中，对于每个长度不大于m的子轨迹，都存在至少k条轨迹包含这样的子轨迹。文献［7］也提出了基于距离的泛化算法，然而该算法只考虑点的支持度，忽略了点泛化对整个轨迹数据库可用性的影响。为此，本文提出实现km-匿名模型的最小变形度的匿名化算法。

2 定义与符号

定义1（泛化区域） 设li，li+1，…，lv均为轨迹数据库中的位置点，由2个或2个以上位置点所组成的区域称为这些位置点的泛化区域，用｛li，li+1，…，lv｝表示。

定义2（位置集） 位置集是指轨迹数据库中所有的移动对象所经过的位置点（或泛化区域）的集合，用L表示。

定义3（轨迹） 移动对象的轨迹是指移动对象按照时间顺序所经过的位置点（或泛化区域）的有序序列，用t=（l1，l2，…，ln）表示。其中，li∈L，L为位置集。

定义4（子轨迹）移动对象的子轨迹是指移动对象按照时间顺序所经过的位置点（或泛化区域）的有序序列的任一子序列，设s为轨迹t的子轨迹，s=（li，li+1，…，lv），t=（l1，l2，…，ln），则。

子轨迹中位置点（或泛化区域）的顺序应该与轨迹中位置点（或泛化区域）的顺序一致。例如，轨迹（a，e）是轨迹（d，a，c，e）的一个子轨迹。

定义5（子轨迹支持度） 设T为一轨迹数据库，s为任一子轨迹，子轨迹s的支持度是指T中所包含子轨迹s的轨迹数，用sup（s，T）表示。例如，表1轨迹数据库中sup（（a，e），T）=3。

表1 原始轨迹数据库

定义6（位置点泛化平均距离） 设｛li，li+1，…，lv｝为一泛化区域，l为其中一个原始位置点，则l与泛化区域｛li，li+1，…，lv｝之间的泛化距离Dloc（l，｛li，li+1，…，lv｝）定义为l与｛li，li+1，…，lv｝中每个位置点的欧氏距离的平均值，见式（1）。

例如，表1为原始轨迹数据库，图1为表1中各个位置点的物理坐标，当位置点a，b泛化成｛a，b｝区域时，那么有Dloc（a，｛a，b｝）=（0+1）/2=0.5，Dloc（b，｛a，b｝）=（1+0）/2=0.5。

图1 位置点的物理坐标

定义7（点泛化变形度） 轨迹数据库中所有的位置点l泛化为｛li，li+1，…，lv｝区域后，整个数据库由该位置点泛化所造成的变形度Distortionp（l，｛li，li+1，…，lv｝）定义为式（2）。

例如，当表1轨迹数据库中所有的位置点a，b泛化为｛a，b｝时，Distortionp（a，｛a，b｝）=3×0.5= 1.5，Distortionp（b，｛a，b｝）=2×0.5=1。

定义8（轨迹数据库变形度） 轨迹数据库T中所有不满足匿名约束的位置点l都泛化成区域｛li，li+1，…，lv｝后，生成的匿名轨迹数据库T′与原始轨迹数据库T之间的变形度DistortionT（T，T′）定义为式（3）。

例如，当表1轨迹数据库T中所有位置点a，b都泛化成｛a，b｝区域时，匿名轨迹数据库T′与轨迹数据库T变形度DistortionT（T，T′）=1.5+1=2.5。

定义9（轨迹km-匿名） 设T为一轨迹数据库，若其中任一长度不大于m的子轨迹s的支持度均不小于k，即∀s，，都有sup（s，T）≥k，则称T是轨迹km-匿名的。

例如，表1轨迹数据库满足21-匿名，但是它不满足22-匿名，因为sup（（d，a），T）=1＜2。

为了实现轨迹km-匿名，需要把轨迹数据库T中不满足km-匿名的位置点跟其他位置点（或泛化区域）泛化，构成较大的泛化区域，使泛化后的匿名轨迹数据库满足km-匿名。为提高匿名轨迹数据的可用性，泛化过程要使轨迹数据库变形度尽可能小。

3 轨迹匿名算法

3.1 GREANON算法

GREANON算法基于贪心的思想，首先找出所有不满足km-匿名约束的子轨迹，即找出所有长度不大于m且支持度小于k的子轨迹。计算出这些子轨迹中所有位置点与其他位置点（或泛化区域）泛化将产生的轨迹数据库变形度，选择形变度最小的泛化，新的泛化区域替换轨迹数据库中所有出现在新的泛化区域的位置点。重复上述过程，直到所有的长度不大于m的子轨迹都满足km-匿名约束条件。具体描述见算法1。

算法1 GREANON算法

输入 数据集T，参数k和m

输出 km-匿名数据集T′

3.2 ACGREANON算法

ACGREANON算法是GREANON算法的改进，它在贪心算法的基础上，结合文献［7］的先验原则。首先找出所有不满足km-匿名约束的子轨迹并计算其支持度，然后在不满足km-匿名约束的子轨迹中找出支持度最小的子轨迹，并找出该子轨迹中支持度最小的位置点（或泛化区域），计算该支持度最小的位置点（或泛化区域）跟其他位置点（或泛化区域）泛化后将产生的轨迹数据库的变形度，选择其中变形度最小的泛化，并用该泛化区域替换轨迹数据库中所有出现在该泛化区域的位置点。重复上述泛化过程，直到所有长度不大于m的子轨迹都满足km-匿名约束条件。具体描述见算法2。

算法2 ACGREANON算法

输入 数据集T，参数k和m

输出 km-匿名数据集T′

例如，表2为表1中所有不同位置点的支持度。表3为子轨迹长度为2且支持度小于2的子轨迹，由表2、表3可知，原始轨迹数据库满足21-匿名，但不满足22-匿名（sup（d，a）=1）。以表1原始轨迹数据库为实例，分别用GREANON算法和ACGREANON算法实现22-匿名。

表2 单个位置点的支持度

表3 不满足22-匿名的子轨迹支持度

GREANON算法首先计算表3中所有位置点跟其他位置点泛化后将产生轨迹数据库的变形度，并找到其中使得轨迹数据库变形度最小的两位置点l1，l2。通过计算可知l1=a，l2=b时轨迹数据库变形度最小，此时Distortionp（a，｛a，b｝）=3×（1/2）= 1.5，Distortionp（b，｛a，b｝）=2×（1/2）=1，DistortionT（T，T1′）=1.5+1=2.5。用泛化区域｛a，b｝替换T，s中所有位置点a，b，得到表4轨迹数据库T1′。表4轨迹数据库还不满足22-匿名，需要进一步泛化，重复上述过程，通过计算此时当l1=c，l2=d，轨迹数据库变形度最小，DistortionT（T，T1′）=2.5+ 2+2.5=7，用泛化区域｛c，d｝替换T1′，s中所有位置点c，d，得到表5轨迹数据库T1″，轨迹数据库T1″满足22-匿名。

表4 匿名轨迹数据库T1′

表5 匿名轨迹数据库T1″

用ACGREANON算法，实现k=2，m=2匿名。首先计算表3中子轨迹的支持度，找到支持度最小的子轨迹，然后计算支持度最小的子轨迹中位置点的支持度，并找出其中最小支持度的位置点l1，此时l1=b，然后计算b与其他位置点泛化后轨迹变形度，找出其中与b泛化产生轨迹变形度最小的位置点l2。通过计算，此时l2=a，DistortionT（T，T2′）=1.5+ 1=2.5，用泛化区域｛b，a｝替换轨迹数据库T，s中所有的位置点a，b得到表6数据库T2′。T2′还不满足22-匿名，需重复上述泛化过程，通过计算此时l1=c，l2=d时轨迹变形度最小，DistortionT（T，T2″）= 2.5+2+2.5=7，用泛化区域｛c，d｝更新T2′，s中所有的c，d，得表7轨迹数据库T2″，轨迹数据库T2″满足22-匿名。

表6 匿名轨迹数据库T2′

表7 匿名轨迹数据库T2″

GREANON算法和ACGREANON算法的思想一样，步骤类似，两算法具有相同的时间复杂度。算法中for为外循环，设位置集为L，那么不同的位置点（或泛化区域）数为，需要迭代的最大值为m。因为sup（s，T′）＜k的子轨迹数量跟k，m相关，为了便于度量，用p（m，k，T）表示子轨迹长度为m且sup（s，T′）＜k的一个概率，那么for外循环的时间复杂度为O（p（m，k，T）×m）。其中，w hile为内循环，最坏的情况下时间复杂度为O（m），所以整个程序的算法时间复杂度为O（m×p（m，k，T）×m），一般m的值比较小时，m×p（m，k，T）的值比较小，所以算法时间复杂度近似于O（m）。

4 匿名轨迹的评估模型

匿名轨迹的质量一般从2个方面进行评估，即匿名轨迹的安全性和可用性。

对于km-匿名的轨迹数据库，其安全性一般可通过参数k和m来评估。m越大，攻击者所具有的时空背景知识越多，km-匿名越安全，当m等于轨迹的长度时，此时的km-匿名就相当于k-匿名。k值越大攻击者推导出用户的轨迹概率（1/k）越小，匿名轨迹数据越安全。

数据可用性可从以下2方面来评估，即发布原始位置点的数量（ON）［7］和轨迹数据库平均变形度（D）进行度量。

定义10（发布原始位置点的数量） 发布原始位置点的数量是指轨迹数据库匿名过程中不需要被泛化的位置点的数量，用ON表示，见式（4）：

对于匿名轨迹数据库而言，ON值越大，匿名轨迹数据库保留了越多原始轨迹数据库的信息，数据的可用性越好。

定义11（轨迹数据库平均变形度） 轨迹数据库平均变形度是指数据库T与匿名数据库T′之间变形度的平均值，用D表示，见式（5）：

轨迹数据库平均变形度D反映了原始轨迹数据库与匿名轨迹数据库之间的差异，轨迹数据库平均变形度越小说明匿名数据库的可用性越好。

5 实验结果与分析

5.1 实验环境及参数配置

实验运行环境为：3.0 GHz Intel Pentium（R）Dual-Core P7350处理器，2 GB内存，W indow s XP操作系统，算法采用C++实现，实验轨迹数据由Brinkhoff［8］合成器合成，很多研究工作［9-11］都采用Brinkhoff合成器合成轨迹数据库。合成轨迹所选的地理位置是Oldenburg City。实验采用文献［7］中的方法对轨迹进行初始化。首先将轨迹数据规范在103×103的网格中，然后把网格均匀地划分为100个不同的网格区域，移动对象以一定的顺序经过不同的网格区域，其中每个网格区域的中心坐标代表经过该网格区域的位置点的坐标，实验中轨迹数据库的平均长度为4.94，共100个位置点和18 143条轨迹。实验将所本文所提出的ACGREANON算法和ACGREANO算法跟文献［7］提出的SEQANON算法进行了比较。

5.2 数据的可用性分析

图2 原始位置的点数量1

图3 轨迹数据库平均变形度1

由图2、图3可看出3种匿名算法生成的匿名轨迹数据库中ON值都随k值的增加而减小，D值随k值增加而增加。因为随着k值的增加，不满足km-匿名的位置点增加，需要被泛化的位置点数量增加，所以数据的可用性变差。

图4 原始位置点的数量2

图5 轨迹数据库平均变形度2

由图4、图5可以看出，3种匿名算法生成的匿名轨迹数据库中ON值随m值的增加而减小，D值随m值增加而增加，因为随着m值的增加，不满足km-匿名的位置点增加，需要被泛化的位置点数量增加，所以数据的可用性变差。

图6 原始位置的点数量3

图7 轨迹数据库平均变形度3

从图2～图7可以看出，随着k和m值的增大，GREANON，ACGREANON算法总体上比SEQANON算法生成的匿名轨迹数据库T′具有更高的数据可用性。这是因为GREANON，ACGREANON算法采用贪心思想每一次泛化都考虑了位置点（或泛化区域）泛化对整个轨迹数据形变度的影响，贪心算法能够使得每一步都具有一个最优的效果。而SEQANON算法采用的是先验原则的思想，每一次泛化考虑sup值最小的位置点（或泛化区域）泛化，准确定位泛化点，避免了算法的盲目性，但是sup值最小的位置点（或泛化区域）泛化并不能保证整个数据库的变形度最小。

5.3 算法效率分析

由图8～图10可知，随着k，m，|T|的增大运行时间呈上升的趋势，且GREANON算法总体上比ACGREANON算法和SEQANON算法运行时间更短。而ACGREANON算法和SEQANON算法运行时间相近。因为ACGREANON，GREANON都基于先验原则思想，需要反复计算位置点（或泛化区域）的支持度。

图8 运行时间1

图9 运行时间2

图10 运行时间3

6 结束语

本文针对部分时空背景知识的轨迹攻击，提出基于点泛化变形度的轨迹变形度的度量方法，设计了2个实现km-匿名模型的最小轨迹变形度匿名化算法：GREANON算法和ACGREANON算法，实验结果表明本文提出的GREANON算法和ACGREANON算法相对现有算法SEQANON在实现km-匿名时能产生可用性更高的匿名轨迹。

下一步将开展对于具有敏感属性的轨迹保护方法的研究；另外，本文所实现的km-匿名模型只能抵制身份链接攻击，需要研究对于其他类型攻击的保护模型。

［1］ Abul O，Bonchi F，Nanni M.Never Walk A lone：Uncertainty for Anonymity in Moving Objects Databases［C］// Proceedings of the 24th International Conference on Data Engineering.Washington D.C.，USA：IEEE Computing Society，2008：720-733.

［2］ Abul O，Bonchi F，Nanni M.Anonymization of Moving Objects Databases by Clustering and Perturbation［J］. Information Systems，2010，35（8）：884-910.

［3］ Mohammed N，Fung B C M，Debbabi M.Walking in the Crowd：Anonymizing Trajectory Data for Pattern Analysis［C］//Proceedings of the 18th ACM Conference on Information and Know ledge Management.Hong Kong，China：Association for Computing Machinery，2009：1441-1444.

［4］ Nergiz M E，A tzori M，Saygin Y.Towards Trajectory Anonymization：A Generalization-based Approach［J］. Transactions on Data Privacy，2009，2（1）：47-75.

［5］ M ohamm ed N，Chen Rui，Fung B C，et al.Privacypreserving Trajectory Data Publishing by Local Suppression［J］.Information Science，2013，231（1）：83-97.

［6］ M onreale A，Andrienko G，Andrienko N，et al.Movement Data Anonym ity Through Generalization［J］. Transactions on Data Privacy，2010，3（2）：91-121.

［7］ Poulis G，Skiadopoulos S，Loukides G，et al.Distancebased km-anonymization of Trajectory Data［C］//Proceedings of the 14th International Conference on Mobile Data Management.Milan，Italy：［s.n.］，2013：57-62.

［8］ 霍 峥，孟小峰.轨迹隐私保护技术研究［J］.计算机学报，2011，34（10）：1829-1830.

［9］ Brinkhoff T.A Framework for Generating Network-based Moving Objects［J］.Geo Informatica，2002，6（2）：153-180.

［10］ Yarovoy R，Bonchi F，Lakshmanan L V S，et al.Anonymizing Moving Objects：How to Hide a Mob in a Crowd？［C］//Proceedings of the 12th International Conference on Extending Database Technology.Saint Petersburg，Russia：［s.n.］，2009：72-83.

［11］ 赵 婧，张 渊，李 兴，等.基于轨迹频率抑制的轨迹隐私保护方法［J］计算机学报，2014，37（10）：2096-2106.

编辑 顾逸斐

Minimum Distortion Degree Algorithm of Trajectory km-anonymity Implementation

GUO Hui，HAN Jianm in，LU Jianfeng，PENG Hao，ZHENG Luqian
（College of Mathematics Physics and Information Engineering，Zhejiang Normal University，Jinhua 321004，China）

km-anonymity can resist background know ledge attacks of m-length subjectory.However，the existing anonymized algorithms select them inimum support point，not them inimum distortion point to generalize.Therefore，w ith increasing of m，the distortion of the trajectory tends to be larger.To address the problem，this paper proposes two kinds of anonym ized algorithms：one is them inimum distortion greedy anonym ized algorithm，the other is them inimum distortion greedy anonymized algorithm with apriori principles.These two algorithms both take consideration of the effect of the generalizing distortion，and choose the minimum distortion point to generalize，which can cause less distortion.It also proposes a method to measure the anonymous trajectory utility.It analyses the data availability and algorithm efficiency. Experimental results show that the proposed algorithm s can generate anonymous trajectory with higher trajectory utility than existing anonymized algorithm s.

privacy preservation；km-anonymity；trajectory；background know ledge attack；point generalized distortion degree

郭 会，韩建民，鲁剑锋，等.实现轨迹km-匿名的最小变形度算法［J］.计算机工程，2015，41（11）：180-185，201.

英文引用格式：Guo Hui，Han Jianm in，Lu Jianfeng，et al.Minimum Distortion Degree Algorithm of Trajectory km-anonym ity Implementation［J］.Computer Engineering，2015，41（11）：180-185，201.

1000-3428（2015）11-0180-06

A

TP301.6

10.3969/j.issn.1000-3428.2015.11.031

国家自然科学基金资助项目（61170108，61402418）；教育部人文社科研究基金资助项目（12YJCZH142）；浙江省自然科学基金资助项目（LQ13F020007）；上海市信息安全综合管理技术研究重点实验室开放基金资助项目（AGK2013003）。

郭 会（1990-），女，硕士研究生，主研方向：信息安全，隐私保护；韩建民，教授、博士；鲁剑锋、彭 浩，副教授、博士；郑路倩，硕士研究生。

2014-10-13

2014-12-18 E-m ail：hanjm@zjnu.cn