基于聚类杂交的隐私保护轨迹数据发布算法

摘要

Recently, privacy preserving trajectory data publishing has become a hot topic in data privacy preserving research fields. Most previous works on privacy preserving trajectory data publishing adopt clustering techniques. However, clustering based algorithms for trajectory data publishing only consider preserving the privacy of each single trajectory, ignoring the protection of the characteristics of trajectory clustering groups. Therefore, the publishing trajectory data by clustering are vulnerable to suffer re-clustering attacks, which is verified by theoretical analysis and simulated experiments. In order to avoid re-clustering attacks, a (k, δ, △)-anonymity model and a clustering hybrid based algorithm CH-TDP for privacy preserving trajectory data publishing are presented. The key idea of CH-TDP is to firstly hybridize between clustering groups, which are generated by the (k, d)-anonymity model and the related algorithms, and then adopt perturbation within each clustering group. The aim of CH-TDP is to avoid suffering re-clustering attacks effectively while assuring the data quality of the released trajectory data not less than a threshold A. CH-TDP and the traditional algorithms are compared and experimental results show that CH-TDP is effective and feasible.%传统关于轨迹数据发布的隐私保护研究大多采用聚类技术,其相关算法只关注每条轨迹的隐私保护,忽视对轨迹聚类组特征的保护.通过理论分析和实验验证发现,对采用聚类发布技术产生的轨迹数据进行二次聚类,可得到原始轨迹数据在发布之前的聚类组特征,从而可能导致隐私泄露.为了有效预防二次聚类攻击,提出一种(k,δ,△)-匿名模型和基于该模型的聚类杂交隐私保护轨迹数据发布算法CH-TDP,算法CH-TDP对采用(k,δ)-匿名模型及相关算法处理得到的聚类分组先进行组间杂交,而后再进行组内扰乱,其目标在防止出现二次聚类攻击的前提下,保证发布轨迹数据的质量不低于阈值△.实验对算法CH-TDP的可行性及有效性与同类算法进行比较分析,结果表明算法CH-TDP是有效可行的.