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

A Clustering Hybrid Based Algorithm for Privacy Preserving Trajectory Data Publishing

作　　者：吴英杰[1,2,3] 唐庆明[1] 倪巍伟[2] 孙志挥[2] 廖尚斌[1] 

机构地区：[1]福州大学数学与计算机科学学院,福州350108 [2]东南大学计算机科学与工程学院,南京211189 [3]福州大学网络系统信息安全福建省高校重点实验室,福州350108

出　　处：《计算机研究与发展》2013年第3期578-593,共16页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61003057);福建省自然科学基金项目(2010J01330);福州大学科技发展基金项目(2012-XQ-27)

摘　　要：传统关于轨迹数据发布的隐私保护研究大多采用聚类技术,其相关算法只关注每条轨迹的隐私保护,忽视对轨迹聚类组特征的保护.通过理论分析和实验验证发现,对采用聚类发布技术产生的轨迹数据进行二次聚类,可得到原始轨迹数据在发布之前的聚类组特征,从而可能导致隐私泄露.为了有效预防二次聚类攻击,提出一种(k,δ,Δ)-匿名模型和基于该模型的聚类杂交隐私保护轨迹数据发布算法CH-TDP,算法CH-TDP对采用(k,δ)-匿名模型及相关算法处理得到的聚类分组先进行组间杂交,而后再进行组内扰乱,其目标在防止出现二次聚类攻击的前提下,保证发布轨迹数据的质量不低于阈值Δ.实验对算法CH-TDP的可行性及有效性与同类算法进行比较分析,结果表明算法CH-TDP是有效可行的.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 （κ,δ,△）-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 （κ, δ）-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.

关 键 词：隐私保护 轨迹数据发布 二次聚类攻击 聚类 杂交 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]