基于k-means++的抗相似性攻击轨迹匿名算法

针对聚类中心的选择问题以及轨迹匿名集中轨迹间的相似性过高而泄露轨迹隐私的问题，提出基于k-means++的抗轨迹相似性攻击的轨迹()k l, ,δ -匿名算法。轨迹预处理的过程中，通过构造同步轨迹来减少信息损失；构建匿名集和时，本文采用k-means++算法来构建匿名集合，并且用()l,δ -约束来限制轨迹匿名集合间的相似性构建包含k条轨迹的匿名集合。实验结果表明，该算法能够较好地构建匿名集合，能够有效抵制轨迹相似性攻击，相比其它算法减少了轨迹信息的损失，同时增强了轨迹数据可利用性，更好地实现了轨迹隐私保护。

随着全球定位系统的发展， 基于位置服务[1] (LBS, location based services)的应用越来越广泛， 人们通过这些应用可以发现最近的酒店、超市和医院等， 它们正在改变着信息时代人们的生活[2] [3]。

LBS 服务过程中会产生大量包含用户的会见、位置信息的数据。人们可以通过对这些数据进行分析、挖掘，得到大量可用信息以帮助决策者实施相关政策，例如通过分析某个区域内用户的轨迹信息，可以发现用户曾经或者未来感兴趣的位置， 在这些位置建立相应的商场， 广场等， 帮助投资者实现盈利的最大化。

然而， 分析这些轨迹数据，也可以推断出用户的一些日常轨迹、身体情况等隐私信息，如果这些个人隐私信息被泄露，会对用户造成极大的威胁[4] [5] [6] [7] [8]。因此对用户轨迹隐私信息保护技术的研究，已经成为信息安全领域研究的重要内容之一。

在轨迹数据隐私保护过程中，轨迹的相似性是轨迹聚类和匿名化的重要因素。然而，如果匿名集合内的k 条轨迹的太过相近，即它们在很长一段时间内经过同一个敏感区域，或者完全重合，那么也会泄露轨迹隐私信息的情况。文献[7]提出构建的轨迹k-匿名集和要具有一定的差异性，以此来降低轨迹隐私信息泄露的风险，它通过采用最小边界矩形MBR (Minimum Bounding Rectangle)大于一个给定阈值的方式来保证轨迹间的差异性。文献[8]首次用轨迹间夹角和距离构造轨迹图的边权的方法，文献[9]又在其基础之上设计了一种基于图划分的个性化隐私保护方法， 利用轨迹距离和轨迹夹角度量来构造轨迹间边权， 将构建轨迹k-匿名集和转化为轨迹k-子图的划分问题。Abul 等人[10]提出NWA (never walk alone)方法， 该方法提出了一个基于共定位的(), k δ -匿名模型，首相将轨迹集合划分为互不相交的子集，其次利用聚类算法形成轨迹k-匿名集合；Cai 等人[11]提出了一种以用户为中心的轨迹隐私保护方法以防止轨迹攻击。

他们引入位置语义多样性以最大化轨迹隐私，攻击和防御问题被转化为贝叶斯Stackelberg 方式以进行定量分析。对轨迹发布数据的隐私保护研究领域，已有大量学者进行了研究[12] [13] [14]。

这些隐私保护方法一定程度保护了轨迹隐私，但是均未考虑轨迹因相似而泄露轨迹信息的情况，另外，在轨迹聚类中心的选取上较为不合理，因此本文提出了基于k-means++的轨迹(), , k l δ -匿名算法。本