基于差分隐私的轨迹模式挖掘算法

doi:10.11772/j.issn.1001-9081.2017.10.2938

计算机应用 ›› 2017, Vol. 37 ›› Issue (10): 2938-2945.DOI: 10.11772/j.issn.1001-9081.2017.10.2938

基于差分隐私的轨迹模式挖掘算法

金凯忠, 彭慧丽, 张啸剑

河南财经政法大学计算机与信息工程学院, 郑州 450002

收稿日期:2017-05-05 修回日期:2017-07-28 出版日期:2017-10-10 发布日期:2017-10-16
通讯作者: 张啸剑(1980-),男,河南周口人,副教授,博士,CCF会员,主要研究方向:差分隐私、数据库,E-mail:xjzhang82@ruc.edu.cn
作者简介:金凯忠(1991-),男,河南开封人,硕士研究生,主要研究方向:差分隐私、数据库;彭慧丽(1981-),女,河南周口人,讲师,硕士,主要研究方向:数据库、隐私保护;张啸剑(1980-),男,河南周口人,副教授,博士,CCF会员,主要研究方向:差分隐私、数据库.
基金资助:
国家自然科学基金资助项目（61502146，91646203）；河南省自然科学基金资助项目（162300410006）；河南省科技攻关项目（162102310411）；河南省教育厅高等学校重点科研项目（16A520002）；河南财经政法大学青年拔尖人才项目。

Trajectory pattern mining with differential privacy

JIN Kaizhong, PENG Huili, ZHANG Xiaojian

School of Computer & Information Engineering, Henan University of Economics and Law, Zhengzhou Henan 450002, China

Received:2017-05-05 Revised:2017-07-28 Online:2017-10-10 Published:2017-10-16
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61502146, 91646203), the Natural Science of Henan Province (162300410006), the Science and Technology Project of Henan Province (162102310411), the Key Scientific Research Projects of Education Department of Henan Province (16A520002), the Youth Top-notch Talent Project of Henan University of Economics and Law.

摘要/Abstract

摘要： 针对现有基于差分隐私的频繁轨迹模式挖掘算法全局敏感度过高、挖掘结果可用性较低的问题，提出一种基于前缀序列格和轨迹截断的差分隐私下频繁轨迹模式挖掘算法--LTPM。该算法首先利用自适应的方法获得最优截断长度，然后采用一种动态规划的策略对原始数据库进行截断处理，在此基础上，利用等价关系构建前缀序列格，并挖掘频繁轨迹模式。理论分析表明LTPM算法满足ε-差分隐私；实验结果表明，LTPM算法的准确率（TPR）和平均相对误差（ARE）明显优于N-gram和Prefix算法，能有效提高挖掘结果的可用性。

关键词: 差分隐私, 隐私保护, 频繁模式挖掘, 轨迹截断, 前缀序列格

Abstract: To address the problems of high global query sensitivity and low utility of mining results in the existing works, a Lattice-Trajectory Pattern Mining (LTPM) algorithm based on prefix sequence lattice and trajectory truncation was proposed for mining sequential patterns with differential privacy. An adaptive method was employed to obtain the optimal truncation length, and a dynamic programming strategy was used to truncate the original database. Based on the truncated database, the equivalent relation was used to construct the prefix sequence lattice for mining trajectory patterns. Theoretical analysis shows that LTPM satisfies ε-differential privacy. The experimental results show that the True Postive Rate (TPR) and Average Relative Error (ARE) of LTPM are better than those of N-gram and Prefix algorithms, which verifies that LTPM can effectively improve the utility of the mining results.

Key words: differential privacy, privacy protection, frequent pattern mining, trajectory truncation, prefix sequential lattice

中图分类号:

TP309.2

金凯忠, 彭慧丽, 张啸剑. 基于差分隐私的轨迹模式挖掘算法[J]. 计算机应用, 2017, 37(10): 2938-2945.

JIN Kaizhong, PENG Huili, ZHANG Xiaojian. Trajectory pattern mining with differential privacy[J]. Journal of Computer Applications, 2017, 37(10): 2938-2945.

参考文献

[1] DWORK C. Differential privacy [C]//ICALP 2006: Proceedings of the 33rd International Conference on Automata, Languages and Programming. Berlin: Springer, 2006: 1-12.
[2] DWORK C. LEI J. Differential privacy and robust statistics [C]//STOC 2009: Proceedings of the 41th Annual ACM Symp on Theory of Computing. New York: ACM, 2009: 371-380.
[3] DWORK C, McSHERRY F, NISSIM K, SMITH A. Calibrating noise to sensitivity in private data analysis [C]//TCC 2006: Proceedings of the 3th Theory of Cryptography Conference. Berlin: Springer, 2006: 363-385.
[4] McSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//FOCS 2007: Proceedings of the 54th IEEE Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 2007: 94-103.
[5] BHASKAR R, LAXMAN S, SMITH A, et al. Discovering frequent patterns in sensitive data[C]//KDD 2010: Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 503-512.
[6] LI N, QARDOJI W, SU D, et al. PrivBasis: frequent itemset mining with differential privacy[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1340-1351.
[7] ZENG C, NAUGHTON J F, CAI J-Y. On differentially private frequent itemset mining [J]. Proceedings of the VLDB Endowment, 2012, 6(1): 25-36.
[8] CHEN R, FUNG B, DESAI B C, et al. Differentially private transit data publication: a case study on the montreal transportation system [C]//KDD 2012: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 213-221.
[9] CHEN R, GERGELY A, CLAUDE C. Differentially private sequential data publication via variable-length n-grams[C]//CCS 2012: Proceedings of the 19th ACM Conference on Computer and Communications Security. New York: ACM, 2012: 638-649.
[10] CHENG X, SU S, XU S, et al. DP-Apriori: a differentially private frequent itemset mining algorithm based on transaction splitting[J]. Computers & Security, 2015, 50 (C): 74-90.
[11] XU S, SU S, CHENG X, et al. Differentially private frequent sequence mining via sampling-based candidate pruning[C]//ICDE 2015: Proceedings of the 31st IEEE International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2015: 1035-1046.
[12] CHEN R, MOHAMMED N, FUNG B C M, et al. Publishing set-valued data via differential privacy [EB/OL]. [2017-01-10]. http://www.vldb.org/pvldb/vol4/p1087-chen.pdf.
[13] YAN X, HAN J, AFSHAR R. CloSpan: mining closed sequential patterns in large datasets[C]//SDM 2003: Proceedings of the 2003 SIAM International Conference on Data Mining. Philadelphia, Pennsylvania, USA: SIAM, 2003: 166-177.
[14] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases [C]//VLDB 1994: Proceedings of the 20th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 1994: 487-499.
[15] McSHERRY F. Privacy integrated queries: an extensible platform for privacy-preserving data analysis [C]//SIGMOD 2009: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2009: 19-30.
[16] PEI J, HAN J, MORTAZAVI-ASL B, et al. PrefixSpan: mining sequential patterns by prefix-projected growth [C]//ICDE 2001: Proceedings of the 17th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2001: 215-224.
[17] 张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护研究综述[J]. 计算机学报, 2014, 37(4): 927-949. (ZHANG X J, MENG X F. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949.)
[18] 丁丽萍, 卢国庆. 面向频繁模式挖掘的差分隐私保护研究综述[J]. 通信学报, 2014, 35(10): 200-209. (DING L P, LU G Q. Survey of differential privacy in frequent pattern mining [J]. Journal on Communications, 2014, 35(10): 200-209.)
[19] 李艳辉, 刘浩, 袁野, 等. 基于差分隐私的频繁序列模式挖掘算法[J]. 计算机应用, 2017, 37(2): 316-321. (LI Y H, LIU H, YUAN Y, et al. Frequent sequence pattern mining with differential privacy[J]. Journal of Computer Applications, 2017, 37(2): 316-321.)
[20] 张啸剑, 王淼, 孟小峰. 差分隐私保护下一种精确挖掘top-k频繁模式方法[J]. 计算机研究与发展, 2014, 51(1): 104-114. (ZHANG X J, WANG M, MENG X F. An accurate method for mining top-k frequent pattern under differential privacy[J]. Journal of Computer Research and Development, 2014, 51(1): 104-114.)

基于差分隐私的轨迹模式挖掘算法

Trajectory pattern mining with differential privacy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[3]	秦静, 安雯, 季长清, 汪祖民. 无线体域网隐私保护机制研究综述[J]. 计算机应用, 2021, 41(4): 970-975.
[4]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.
[5]	张恩, 李会敏, 常键. 可验证的隐私保护k-means聚类方案[J]. 计算机应用, 2021, 41(2): 413-421.
[6]	陈锦宇, 刘兆伟. 基于改进投票证明共识协议的车联网系统[J]. 计算机应用, 2021, 41(1): 170-176.
[7]	马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.
[8]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[9]	金波, 张志勇, 赵婷. 基于差分隐私的社交网络位置近邻查询方法[J]. 计算机应用, 2020, 40(8): 2340-2344.
[10]	马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.
[11]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.
[12]	涂子璇, 刘树波, 熊星星, 赵晶, 蔡朝晖. 可穿戴设备的数值型流数据差分隐私均值发布[J]. 计算机应用, 2020, 40(6): 1692-1697.
[13]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[14]	拜亚萌, 满君丰, 张宏. 基于区块链的电子健康记录安全存储模型[J]. 计算机应用, 2020, 40(4): 961-965.
[15]	罗惠雯, 龙士工. 基于用户感兴趣区域的地理不可区分性的位置扰动算法[J]. 计算机应用, 2020, 40(3): 760-764.