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

Trajectory Anonymous Algorithm Based on k-Means++ against Similarity Attack

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

Abstract: Aiming at the problems of how to choose the center of cluster and trajectory privacy leakage caused by the high similarity between the anonymous centralized trajectories, we propose a trajectory anonymous algorithm to resist trajectory similarity attacks. In the preprocessing process, the algorithm adopts trajectory synchronization to reduce information loss. In clustering process, we use k-means++ algorithm to construct the anonymous collection; to prevent the privacy leakage caused by the high slope similarity of trajectories in the set, at least l trajectories with different slopes are required to satisfy trajectory k-anonymity, and the difference value of trajectory slope in each class is required to be at least σ. Experimental results show that the proposal can effectively resist trajectory similarity attacks, reduce information loss comparing to other trajectory anonymous algorithms, enhance the data of availability, and achieve better trajectory privacy protection.