基于个性化时空聚类的差分隐私轨迹保护模型

doi:10.3969/j.issn.1671-1122.2024.01.008

摘要/Abstract

摘要：

随着位置感知设备的普及，轨迹数据已广泛应用于现实生活。然而，轨迹数据通常与敏感标签相关联，不当地分享或发布这些数据可能会泄露用户的隐私，且不同数据的敏感程度互异。针对上述问题，文章提出了基于个性化时空聚类的差分隐私轨迹保护模型。首先，针对轨迹中海量时间数据与隐私保护的需要，文章提出模糊均值聚类算法（FCM算法）；其次，在空间分割的过程中，通过密度进行聚类，并实现个性化调整隐私预算分配的目的，从而提高数据效用；再次，在轨迹合成阶段，对比真实轨迹数据，选择更具代表性的轨迹；最后，在发布阶段，引入Laplace机制对轨迹数目进行隐私保护。为了验证文章所提出的模型在轨迹效用与隐私保护上的成果，将该模型与另外两种模型在4个阶段上进行了比较。实验结果表明，文章所提出的模型在数据效用方面提升15.45%，在相同隐私预算下，隐私保护强度提升至少35.62%。

关键词: 个性化预算分配, 差分隐私, 时空聚类, 轨迹隐私, 轨迹发布

Abstract:

With the proliferation of location-aware devices, trajectory data has found widespread applications in real-life scenarios. However, trajectory data is often associated with sensitive labels, and improperly sharing or disclosing such data can pose privacy threats to users, with varying levels of sensitivity among different datasets. To address this issue, a differential privacy trajectory protection model based on personalized spatiotemporal clustering was proposed. Firstly, in response to the vast amount of temporal data in trajectories and the need for privacy protection, the fuzzy clustering means algorithm (FCM) was proposed. Secondly, during the spatial segmentation process, clustering was performed based on density, and personalized adjustments were made to allocate privacy budgets, thereby enhancing data utility. In the trajectory synthesis phase, a comparison was made with real trajectory data to select trajectories that were more representative. Finally, the Laplace mechanism was introduced in the release phase to protect the privacy of trajectory counts. To validate the achievements of the model in terms of trajectory utility and privacy protection, comparisons were made with various models in four stages. The experimental results indicate a 15.45% improvement in data utility for the proposed model and, under the same privacy budget, enhances privacy protection strength by at least 35.62%.

Key words: personalized budget allocation, differential privacy, spatiotemporal clustering, trajectory privacy, trajectory publication

中图分类号:

TP309

尹春勇, 蒋奕阳. 基于个性化时空聚类的差分隐私轨迹保护模型[J]. 信息网络安全, 2024, 24(1): 80-92.

YIN Chunyong, JIANG Yiyang. Differential Privacy Trajectory Protection Model Based on Personalized Spatiotemporal Clustering[J]. Netinfo Security, 2024, 24(1): 80-92.

图/表 10

图1

表1

图2

图3

表2

图4

图5

图6

图7

图8

参考文献 32

[1]	ZHAO Xiaodong, PI Dechang, CHEN Junfu. Novel Trajectory Privacy-Preserving Method Based on Clustering Using Differential Privacy[J]. Expert Systems with Applications, 2020, 149: 3305-3317.
[2]	WU Lei, QIN Chengyi, XU Zihui, et al. TCPP: Achieving Privacy-Preserving Trajectory Correlation with Differential Privacy[J]. IEEE Transactions on Information Forensics and Security, 2023, 18: 4006-4020. doi: 10.1109/TIFS.2023.3290486 URL
[3]	GAZDAG A, LESTYAN S, REMELI M, et al. Privacy Pitfalls of Releasing In-Vehicle Network Data[EB/OL]. (2022-12-09) [2023-10-20]. https://doi.org/10.1016/j.vehcom.2022.100565.
[4]	MA Tinghuai, DENG Qian, RONG Huan, et al. A Privacy-Preserving Trajectory Data Synthesis Framework Based on Differential Privacy[EB/OL]. (2023-07-25) [2023-10-20]. https://doi.org/10.1016/j.jisa.2023.103550.
[5]	ZHAO Jia, GAO Ta, ZHANG Jiancheng. Method of Local Differential Privacy Method for High-Dimensional Data Based on Improved Bayesian Network[J]. Netinfo Security, 2023, 23(2): 19-25.
	赵佳, 高塔, 张建成. 基于改进贝叶斯网络的高维数据本地差分隐私方法[J]. 信息网络安全, 2023, 23(2): 19-25.
[6]	SWEENEY L. K-Anonymity: A Model for Protecting Privacy[J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570. doi: 10.1142/S0218488502001648 URL
[7]	SU Bing, HUANG Jiaxuan, MIAO Kelei, et al. K-Anonymity Privacy Protection Algorithm for Multi-Dimensional Data against Skewness and Similarity Attacks[J]. Sensors, 2023, 23(3): 56-68. doi: 10.3390/s23010056 URL
[8]	DWORK C. Differential Privacy[C]// Springer. Proccedings of the 33rd International Colloquium on Automata, Languages and Programming. Heirdelberg: Springer, 2006: 1-12.
[9]	DWORK C. Differential Privacy: A Survey of Results[C]// Springer. International Conference on Theory and Applications of Models of Computation. Heirdelberg: Springer, 2008: 1-19.
[10]	MCSHERRY F, TALWAR K. Mechanism Design via Differential Privacy[C]// IEEE. 48th Annual IEEE Symposium on Foundations of Computer Science. New York: IEEE, 2007: 94-103.
[11]	MCSHERRY F, MIRONOV I. Differentially Private Recommender Systems: Building Privacy into the Netflix Prize Contenders[C]// ACM. 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 627-636.
[12]	SUN Liping, BAO Shuting, CI Shang, et al. Differential Privacy-Preserving Density Peaks Clustering Based on Shared Near Neighbors Similarity[J]. IEEE Access, 2019, 7: 89427-89440. doi: 10.1109/ACCESS.2019.2927308
[13]	PARK J, LEE D H. Parallelly Running K-Nearest Neighbor Classification over Semantically Secure Encrypted Data in Outsourced Environments[J]. IEEE Access, 2020, 8: 64617-64633. doi: 10.1109/Access.6287639 URL
[14]	YAO Lin, CHEN Zhenyu, HU Haibo, et al. Privacy Preservation for Trajectory Publication Based on Differential Privacy[J]. ACM Transactions on Intelligent Systems and Technology, 2022, 13(3): 82-91.
[15]	GU Zhen, ZHANG Guoyin. Trajectory Data Publication Based on Differential Privacy[J]. International Journal of Information Security and Privacy (IJISP), 2023, 17(1): 1-15.
[16]	LIU Qi, YU Juan, HAN Jianmin, et al. Differentially Private and Utility-Aware Publication of Trajectory Data[EB/OL]. (2021-04-28) [2023-10-20]. https://doi.org/10.1016/j.eswa.2021.115120.
[17]	GENG Quan, KAIROUZ P, OH S, et al. The Staircase Mechanism in Differential Privacy[J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(7): 1176-1184. doi: 10.1109/JSTSP.2015.2425831 URL
[18]	CAI Sujin, LYU Xin, LI Xin, et al. A Trajectory Released Scheme for the Internet of Vehicles Based on Differential Privacy[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(9): 16534-16547. doi: 10.1109/TITS.2021.3130978 URL
[19]	LI Hongtao, WANG Yue, GUO Feng, et al. Differential Privacy Location Protection Method Based on the Markov Model[EB/OL]. (2021-07-01) [2023-10-20]. https://doi.org/10.1155/2021/4696455.
[20]	ZHANG Yaling, LIU Na, WANG Shangping. A Differential Privacy Protecting K-Means Clustering Algorithm Based on Contour Coefficients[J]. PLOS ONE, 2018, 13(11): 58-70.
[21]	DING Xiaofeng, YANG Wanlu, CHOO K K R, et al. Privacy Preserving Similarity Joins Using MapReduce[J]. Information Sciences, 2019, 493: 20-33. doi: 10.1016/j.ins.2019.03.035
[22]	GURSOY M E, LIU Ling, TRUEX S, et al. Differentially Private and Utility Preserving Publication of Trajectory Data[J]. IEEE Transactions on Mobile Computing, 2019, 18(10): 2315-2329. doi: 10.1109/TMC.7755 URL
[23]	CHEN Si, FU Anmin, SHEN Jian, et al. RNN-DP: A New Differential Privacy Scheme Base on Recurrent Neural Network for Dynamic Trajectory Privacy Protection[J]. Journal of Network and Computer Applications, 2020, 168: 1036-1048.
[24]	ZHANG Ziming, XU Xiaolong, XIAO Fu. LGAN-DP: A Novel Differential Private Publication Mechanism of Trajectory Data[J]. Future Generation Computer Systems-The International Journal of Escience, 2023, 141: 692-703.
[25]	LI Youru, ZHU Zhenfeng, KONG Deqiang, et al. EA-LSTM: Evolutionary Attention-Based LSTM for Time Series Prediction[J]. Knowledge-Based Systems, 2019, 181: 265-277.
[26]	CHENG Wenqing, WEN Ruxue, HUANG Haojun, et al. OPTDP: Towards Optimal Personalized Trajectory Differential Privacy for Trajectory Data Publishing[J]. Neurocomputing, 2022, 472: 201-211. doi: 10.1016/j.neucom.2021.04.137 URL
[27]	LI Jiachun, CHEN Guoqian. A Personalized Trajectory Privacy Protection Method[J]. Computers & Security, 2021, 108: 131-142.
[28]	Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. Heirdelberg: Springer Science & Business Media, 2013.
[29]	YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al. T-Drive: Driving Directions Based on Taxi Trajectories[C]// ACM. 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2010: 99-108.
[30]	YUAN Jing, ZHENG Yu, XIE Xing, et al. Driving with Knowledge from the Physical World[C]// ACM. 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2011: 316-324.
[31]	HUA Jingyu, GAO Yue, ZHONG Sheng. Differentially Private Publication of General Time-Serial Trajectory Data[C]// IEEE. 2015 IEEE Conference on Computer Communications. New York: IEEE, 2015: 549-557.
[32]	CHEN Si, FU Anmin, SU Mang, et al. Trajectory Privacy Protection Scheme Based on Differential Privacy[J]. Journal on Communications, 2021, 42(9): 54-64. doi: 10.11959/j.issn.1000-436x.2021168
	陈思, 付安民, 苏铓, 等. 基于差分隐私的轨迹隐私保护方案[J]. 通信学报, 2021, 42(9): 54-64. doi: 10.11959/j.issn.1000-436x.2021168

参数	含义
$\tilde{T}$	原始轨迹
D	时间概化后的数据集
DG	时空处理后的数据集
t	时刻
p	区域L中的分组数
P	分区中组的集合
tc	真实轨迹数量
la	Laplace噪声
rc	发布的轨迹数据集

新轨迹数据集	与新轨迹相似的原始轨迹	真实记录数	是否异常
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{21}}\to {{\tilde{l}}_{32}}$	${{T}_{2}},{{T}_{5}},{{T}_{7}}$	2	否
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{32}}$	${{T}_{7}}$	1	否
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{33}}$	—	0	是
${{\tilde{l}}_{12}}\to {{\tilde{l}}_{21}}\to {{\tilde{l}}_{33}}$	${{T}_{3}}$	2	否
${{\tilde{l}}_{11}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{31}}$	${{T}_{1}}$	2	否
${{\tilde{l}}_{11}}\to {{\tilde{l}}_{23}}\to {{\tilde{l}}_{32}}$	—	0	是
${{\tilde{l}}_{13}}\to {{\tilde{l}}_{22}}\to {{\tilde{l}}_{32}}$	${{T}_{4}},{{T}_{6}}$	4	否
${{\tilde{l}}_{11}}\to {{\tilde{l}}_{21}}\to {{\tilde{l}}_{33}}$	—	0	是