广东工业大学学报 ›› 2021, Vol. 38 ›› Issue (01): 69-74.doi: 10.12052/gdutxb.200021

• 综合研究 • 上一篇    下一篇

DPLORE：一种差分隐私保护位置推荐算法

杨达森   

  1. 广东工业大学 计算机学院，广东 广州 510006
  • 收稿日期:2020-02-11 出版日期:2021-01-25 发布日期:2020-12-01
  • 作者简介:杨达森(1993-)，男，硕士研究生，主要研究方向为差分隐私保护、数据挖掘
  • 基金资助:
    国家自然科学基金资助项目(61876043)

DPLORE: A Location Recommendation Algorithm for Differential Privacy Protection

Yang Da-sen   

  1. School of Computers, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2020-02-11 Online:2021-01-25 Published:2020-12-01

HTML

PDF (PC)

2756

摘要： 人类移动中的顺序模式在地理社交网络服务的位置推荐中扮演了重要角色。现有的位置推荐系统必须访问用户的原始签到位置数据, 以挖掘其顺序模式, 然而这会泄露用户的位置隐私。针对该问题, 提出一种基于差分隐私保护的位置推荐算法(Differential Privacy Location Recommendation, DPLORE)。首先, 根据原始数据构建转移计数矩阵, 利用拉普拉斯机制向分解后的矩阵元素添加噪声, 使得算法满足差分隐私保护。接着, 在多阶马尔可夫链模型的基础上, 提出自适应权重的n-阶马尔可夫链模型, 利用用户的顺序模式来进行位置推荐。最后的实验表明, 本文设计的算法框架DPLORE的推荐结果准确率和召回率都优于现有的算法, 同时DPLORE在高推荐精度和严格的位置隐私保护之间达成良好的权衡。

关键词: 差分隐私, 拉普拉斯机制, 位置推荐, 马尔可夫链

Abstract: Sequential patterns in human beings movement play an important role in location recommendation of geosocial network services. The existing location recommendation system must access the user's original check-in location data in order to mine its sequence pattern, but this will disclose the user's location privacy. To solve this problem, a location recommendation algorithm based on differential privacy protection called DPLORE is proposed. Firstly, the transfer counting matrix is constructed based on the original data, and noise is added to the decomposed matrix elements by using Laplace mechanism, which makes the algorithm meet the differential privacy protection. Then, on the basis of Multi-Markov Chain model, an adaptive weight Nth-Markov Chain model, which uses the user's order pattern to recommend the location, is proposed. Finally, experiments show that the proposed algorithm framework DPLORE has better recommendation precision and recall rate than the existing algorithms, and DPLORE achieves a good trade-off between high recommendation precision and strict location privacy protection.

Key words: differential privacy, Laplace mechanism, location recommendation, Markov Chain

中图分类号: 

  • TP311
[1] YAO L N, SHENG Q Z, WANG X Z, et al. Collaborative location recommendation by integrating multi-dimennsional contextual information [J]. ACM Transactions on Internet Technology, 2018, 18(3): 1-24.
[2] CHO E, MYERS S. Friendship and mobility: user movement in location-based social networks [C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego: ACM, 2011: 1082-1090.
[3] GAO H J, TANG J L LIU H. GSCorr: Modeling geo-social correlations for new check-ins on location-based social networks [C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Maui: ACM, 2012: 1582-1586.
[4] ZHANG J D, CHOW C Y, LI Y H. LORE: exploiting sequential influence for location recommendations [C]//Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Dallas: ACM, 2014: 103-112.
[5] WANG J B, CAI Z P, LI Y S, et al. Protecting query privacy with differentially private k-anonymity in location-based services [J]. Personal and Ubiquitous Computing, 2018, 22(3): 453-469.
[6] GHASEMZADEH M, FUNG B C, CHEN R, et al. Anonymizing trajectory data for passenger flow analysis [J]. Transportation Research Part C Emerging Technologies, 2014, 39(1): 63-79.
[7] DWORK C. Differential privacy [C]//Proceedings of the 33rd International Conference on Automata, Languages and Programming－Volume Part II. Berlin: ICALP, 2006: 1-12.
[8] KELLARIS G, PAPADOPOULOS S. Practical differential privacy via grouping and smoothing [C]//Garda, The 39th International Conference on Very Large Data Bases: ACM, 2013: 301-312.
[9] DAY W Y, LI N H. Differentially private publishing of high-dimensional data using sensitivity control [C]//Proceedings of the 10th ACM Symposium on Information Computer and Communications Security. Singapore: ACM, 2015: 451-462.
[10] 鲜征征, 李启良, 黄晓宇. 基于差分隐私和SVD++的协同过滤算法[J]. 控制与决策, 2019, 34(01): 43-54.
XIAN Z Z, LI Q L, HUANG X Y. Collaborative filtering via SVD++ with differential privacy [J]. Control and Decision, 2019, 34(01): 43-54.
[11] NOULAS A, SCELLATO S. Mining user mobility features for next place prediction in location-based services [C]//2012 IEEE 12th International Conference on Data Mining. Brussels: IEEE, 2012: 1038-1043.
[12] ZHANG J D, CHOW C Y. IGeoRec: a personalized and efficient geographical location recommendation framework [J]. IEEE Transactions on Service Computing: IEEE, 2015, 8(5): 701-714.
[13] LU Z Y, WANG H. Personalized location recommendation by aggregating multiple recommenders in diversity [J]. Geoinformatica, 2017, 21(3): 459-484.
[14] CHAKRABORTY B, VERMA S, SINGH K P, et al. Differentially private location privacy preservation in wireless sensor networks [J]. Wireless Personal Communications: An International Journal, 2019, 104(1): 387-406.
[15] ZHANG Y, MAO Y L, ZHONG S, et al. Joint differentially private gale-shapley mechanisms for location privacy protection in mobile traffic offloading systems [J]. IEEE Journal on Selected Areas in Communications, 2016, 34(10): 2738-2749.
[16] LIU Z Q, WANG Y X. Fast differentially private matrix factorization [C]//Proceedings of the 9th ACM Conference on Recommender Systems. Vienna: ACM, 2015: 171-178.
[17] LI C, PALANISAMY B, JOSHI J. Differentially private trajectory analysis for points-of-interest recommendation [C]//2017 6th IEEE International Congress on BigData. Honolulu: IEEE, 2017: 1-8.
[18] WEI J H, LIN Y P, YAO X, et al. Differential privacy-based trajectory community recommendation in social network [J]. Journal of Parallel and Distributed Computing, 2019, 133(1): 136-148.
[1] 孙琳. 跳跃CKLS模型的MCMC估计与应用[J]. 广东工业大学学报, 2010, 27(2): 68-70.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发