差分隐私下满足一致性的轨迹流量发布方法 张双越 蔡剑平 田丰 吴振强 陕西师范大学计算机科学学院 福州大学数学与计算机科学学院 摘 要： 搭载 GPS 设备的车辆在运行过程中产生大量轨迹信息, 对轨迹流量信息的统计与发布有利于改善路网结构、实现智能交通。但是直接发布轨迹流量可能导致用户隐私的泄露, 而目前缺乏严格的可证明的轨迹流量隐私保护发布方法。为此, 本文提出了一种基于路网的差分隐私轨迹流量发布方法。该方法分两步:首先根据轨迹数据统计各个路段的流量值并添加差分隐私噪声;随后针对流量图的一致性特性提出后置调节算法, 使得调节后的流量图不仅重新满足一致性特性, 而且还极大地减少了发布误差。在真实路网上的实验表明, 该方法具有处理大规模路网流量的能力, 且经过后置调节算法的优化, 发布误差减小了约 13%。关键词： 轨迹流量; 差分隐私; 一致性调节; 路网约束; 作者简介：张双越 (1990-) , 女, 河北人, 陕西师范大学计算机科学学院硕士研究生, 主要研究领域为差分隐私。作者简介：蔡剑平 (1990-) , 男, 福建漳州人, 2016 年获福州大学数学与计算机科学学院硕士学位, 主要研究领域为差分隐私。作者简介：田丰 (1987-) , 男, 陕西人, 2015 年获西安交通大学博士学位, 目前为陕西师范大学讲师, 主要研究领域为位置隐私保护, 隐私保护的数据挖掘。作者简介：TIAN Feng was born in which 1987.He received the Ph.D.degree from XiAn Jiaotong University in 2015.He is a lecturer at Shaanxi Normal University.His research interests include location privacy protection, privacy protection in data mining.基金：国家自然科学基金Trajectory Flow Releasing Method with Consistency Constraint under Differential PrivacyZHANG Shuangyue CAI Jianping TIAN Feng WU Zhenqiang College of Computer Science, Shaanxi Normal University; College of Mathematics and Computer Science, Fuzhou University; Abstract： Vehicles carrying GPS equipment created large trajectory information.Analyzing and publishing trajectory data flow statistics based on road network is beneficial to the improvement of network structure and the realization of Intelligent Transportation.However, the direct release of trajectory traffic can lead to the disclosure of user privacy, and there is lack of a rigorous and provable privacy method to release traffic flow in road networks.Therefore, this paper presents a differential privacy trajectory flow releasing method.The method is divided into two steps: firstly, the flow value of each section is statistically calculated and the difference privacy noise is added, then the post adjustment algorithm is put forward for the consistency characteristic of the flow graph, so that the adjusted flow graph not only satisfies the consistency characteristic, but also greatly reduces the publishing error.The experiment on the real road network shows that the method has the ability to deal with large-scale network traffic, and after the optimization of the post adjustment algorithm, the release error is reduced by about 13%.Keyword： trajectory flow; differential privacy; consistency adjustment; road network constraints; 1 引言随着移动互联网和 GPS 定位技术的发展, 移动对象不断上传的位置信息形成了轨迹大数据。根据轨迹数据所含的丰富时空信息可以挖掘分析出许多人类行为模式和交通演化规律1。在路网交通背景下, 对车辆轨迹数据中各个统计指标的发布可为道路管理及应急规划提供有力支持。例如, 发布轨迹流量指标的统计信息可反映出每条路段的拥堵程度以及流量特征, 这对于用户出行, 交通指挥, 乃至路网结构调整及整个路网的承载能力和可靠性的提高都有重要的现实意义和应用价值2,3。然而, 轨迹数据中隐含了用户的出行习惯、行为模式等隐私信息4,5。因此, 直接发布轨迹流量值可能造成用户隐私泄露。例如, 假设攻击者掌握了某个特定时段内除目标用户之外其他用户的轨迹信息, 则他再结合所发布的轨迹流量数据即可追踪出目标用户在该时段内的轨迹。为了保护用户隐私, 常用的轨迹发布隐私保护方法主要有假数据法6,7、泛化法、抑制法, 这些方法通常通过变换或剔除轨迹中的敏感信息来保护轨迹数据的发布。但是, 这些方法对攻击者拥有的背景知识敏感, 容易受到背景知识攻击。当攻击者掌握了较多的背景信息时, 用户的隐私就难以保障且缺乏严格的数学证明。2006 年 Dwork 等人针对统计数据库的隐私泄露问题提出了差分隐私模型16, 该模型保证了攻击者在任何知识背景下都无法准确地从所发布的数据中获得隐私信息且具有严格的概率分布不可区分性证明, 引起了广大研究者的兴趣。2011 年起, 差分隐私模型被应用到轨迹发布隐私保护中, 并取得了一系列成果。但是, 已有的工作专注于发布经过差分隐私保护的整个轨迹数据集, 对路网环境下的轨迹流量发布缺乏考虑。本文在路网约束下结合差分隐私在保护统计信息领域的优势提出轨迹流量发布算法, 并对该算法进行一致性优化, 提高了发布结果的可用性和发布效率。Fig.1 Vehicle Trajectory From A City Block 图 1 某城市街区及该街区的车辆轨迹 下载原图本文将路网结构抽象为有向图, 有向图中的边连接两个相邻的路口, 同时将轨迹数据相应地处理为形如图 1 (b) 所示的有序序列, 对这些轨迹数据进行统计即可得到路网中各个路段的轨迹流量。以北京天安门东边的某街区为例, 图 1 (a) 为该街区的真实道路地图, 图 1 (b) 为该地图上的车辆轨迹数据样例, 经统计得到的轨迹流量图如图 2 (a) 所示。图 2 (a) 中节点和边分别对应图 1 (a) 中的各个路口和街道, 边上的权值代表了相应路段的轨迹流量。接下来, 在差分隐私机制下, 向图 2 (a) 中的边权值添加符合拉普拉斯分布的噪声以保护用户隐私。添加噪声后的流量图如图 2 (b) 所示。不难发现, 由于拉普拉斯噪声的引入导致了某些路口出入流量不一致的问题。如 B 路口所示 (非起止路口) , 添加噪音扰动前车辆驶入该路口的次数等于驶出该路口的次数, 如图 2 (a) 都为 3;添加噪音扰动后, 该路口的驶入车次为 4, 驶出车次为 3。这显然与实际情况不符。深入研究发现, 不一致问题不仅导致发布结果不符合实际, 同时也增大了发布误差。为此, 本文提出了一种一致性调节方案来解决上述问题。Fig.2 Traffic Flow Before and After Protection 图 2 保护前后的轨迹流量图 下载原图Fig.2 Traffic Flow Before and After Protection 图 2 保护前后的轨迹流量图 下载原图对于差分隐私领域的不一致性问题已有学者进行了研究25。例如, Hay26等人对直方图发布中的不一致性问题提出了后置处理方案。然而由于研究目标不同, 该方案无法直接应用于解决本文中的不一致问题。因此, 本文在参考Hay26思路的基础上提出了一种新的后置调节算法。经过大量的理论分析以及实验表明, 本文所提后置处理算法不仅能有效地解决上述不一致问题, 还在合理的时间内对发布结果的精度有了明显提升。综上所述, 本文完成了以下工作:1) 将实际城市路网抽象成有向图模型, 并向图中引入一个辅助的虚拟节点。利用该虚拟节点形式化表现了流量图中的不一致性问题。2) 结合拉普拉斯机制提出差分隐私流量图生成算法。3) 在 2) 的基础上提出一致性调节算法。该算法在严格的理论分析和公式推导下有效地解决了一致性问题, 并提升了发布精度。4) 在真实路网上对本文所提算法进行实验验证, 结果表明一致性调节算法减小了约 13%的发布误差且具有处理大规模数据的能力。2 相关工作为了解决轨迹数据发布过程中的隐私泄露问题, 文献17首次引入了差分隐私机制。该文献利用原始轨迹数据的特性构建噪音前缀树, 并向前缀树节点的计数值中添加拉普拉斯噪声保证用户的轨迹隐私。然而随着前缀树规模的增大, 树中的节点将呈指数增长, 导致落入每个分支的轨迹数量急剧减少, 严重降低了数据可用性。随后文献18通过 n-gram 模型实现了可变长度的轨迹数据集发布, 在一定程度上改善了文献17的不足。但是, 文献17, 18都基于一个共同的假设, 即原始数据中存在大量的共同前缀, 这在现实中很难满足。文献20利用指数机制对轨迹数据进行聚类操作, 去除了轨迹数据中存在共同前缀的假设条件。文献23提出一种有界噪音泛化算法, 减小了信息损失和平均轨迹合并时间。然而, 以上文献都是发布经过差分隐私保护的整个轨迹数据集。文献24提出 l-轨迹差分隐私保护模型, 实时发布无限轨迹流上不同位置的用户统计值。然而却鲜有文献考虑路网约束下的轨迹统计值发布。文献27指出当发布大量用户位置的聚合信息时, 差分隐私能提供较好的隐私保障。因此本文就以保护路网中的轨迹流量统计值作为切入点展开研究工作。差分隐私中常见的优化方法主要分为基于数据压缩转换的前置优化算法以及基于规划策略的后置优化算法26。Hay26等人利用区间树的一致性问题对直方图统计发布进行优化就是一种典型的后置优化算法, 该算法利用最优估计理论不仅解决了区间树的不一致性问题同时还有效地提升了发布数据的可用性。在该理论的启发下, 本文提出了一种新的优化模型, 有效解决了轨迹流量发布过程中的不一致问题