基于序列格的隐私时序模式挖掘方法

doi:10.3969/j.issn.0372-2112.2020.01.019

电子学报 ›› 2020, Vol. 48 ›› Issue (1): 153-163.DOI: 10.3969/j.issn.0372-2112.2020.01.019

基于序列格的隐私时序模式挖掘方法

彭慧丽^1,2, 金凯忠¹, 付聪聪¹, 付楠¹, 张啸剑¹

1. 河南财经政法大学计算机与信息工程学院, 河南郑州 450002;
2. 河南广播电视大学信息工程学院, 河南郑州 450046

收稿日期:2018-10-18 修回日期:2019-05-23 出版日期:2020-01-25
- 通讯作者:
- 张啸剑
- 作者简介:
- 彭慧丽 女,1981年生于河南周口.主要研究方向为数据库、隐私保护.Email:phl81@163.com;金凯忠 男,1991年生于河南开封.河南财经政法大学硕士.主要研究方向为差分隐私、数据库.E-mail:kaizhong@huel.edu.cn;付聪聪 女,1995年生于河南商丘.硕士研究生.主要研究方向为差分隐私、图像处理.E-mail:congf@huel.edu.cn;付楠男,1988年生于河南开封.硕士研究生.主要研究方向为差分隐私、数据库.E-mail:funan@huel.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61502146，No.91646203，No.91746115，No.61772131，No.61702161）; 河南省自然科学基金 (No.162300410006）; 河南省科技攻关项目 (No.162102310411）; 河南省教育厅高等学校重点科研项目 (No.16A520002）; 河南省高等学校青年骨干教师培养计划 (No.2017GGJS084）; 河南财经政法大学青年拔尖人才资助计划

Private Time Series Pattern Mining with Sequential Lattice

PENG Hui-li^1,2, JIN Kai-zhong¹, FU Cong-cong¹, FU Nan¹, ZHANG Xiao-jian¹

1. School of Computer & Information Engineering, Henan University of Economics and Law, Zhengzhou, Henan 450002, China;
2. School of Information Engineering, Henan Radio & Television University, Zhengzhou, Henan 450046, China

Received:2018-10-18 Revised:2019-05-23 Online:2020-01-25 Published:2020-01-25
- Corresponding author:
- ZHANG Xiao-jian
- Supported by:
- National Natural Science Foundation of China (No.61502146, No.91646203, No.91746115, No.61772131, No.61702161); Natural Science Foundation of Henan Province, China (No.162300410006); Science and Technology Research and Development Program of Henan Province (No.162102310411); Key Science Research Program of Universities of Education Department of Henan Province (No.16A520002); Funding Project for Young Backbone Teachers of Universities in Henan Province (No.2017GGJS084); Funding Program for Youth Top-notch Talentsof Henan University of Economics and Law

摘要/Abstract

摘要： 基于差分隐私的时间序列模式挖掘方法中，序列的最大长度以及添加拉普拉斯噪声的多少直接制约着挖掘结果的可用性.针对现有时间序列模式挖掘方法全局敏感度过高、挖掘结果可用性较低的不足问题，提出了一种基于序列格的差分隐私下时间序列模式挖掘方法PrivTSM（Differentially Private Time Series Pattern Mining）.该方法首先利用最长路径的策略对原始数据库进行截断处理；在此基础上，采用表连接操作生成满足差分隐私的序列格；结合序列格结构本身的特性，合理分配隐私预算，提高输出模式的可用性.理论分析表明PrivTSM方法满足ε-差分隐私，基于真实数据库上实验结果表明，PrivTSM方法的准确率TPR（True Postive Rate）和平均相对误差ARE（Average Relative Error）明显优于N-gram和Prefix-Hybrid方法.

关键词: 差分隐私, 时间序列, 全局敏感度, 数据挖掘, 数据截断, 序列格

Abstract: Many methods of differentailly private time series pattern mining have been proposed, while in those methods, the length of sequence pattern and Laplace noise directly constrain the utility of the mining results. To address the questions caused by the global query sensitivity and lower utility of the existing works, an efficient method,called PrivTSM (differentially Private Time Series Pattern Mining) is proposed, which is based on sequence lattice for mining time series pattern with differential privacy. This method relies on the longest path strategy to truncate the original database; based on the truncated database, this method uses the table join operation to construct a differentially private sequence lattice. Furthermore, this method uses the property of the sequence lattice structure itself to allocate privacy budget reasonably and boost the accuracy of the noisy counts. PrivTSM satisfies ε-differential privacy through theoretical analysis. The experimental results on real datasets show that the accuracy (TPR) and average relative error (ARE) of the PrivTSM are better than those of the N-gram and Prefix-Hybrid algorithms.

Key words: differential privacy, time series, global sensitivity, data mining, data truncate, sequential lattice

中图分类号:

TP309.2

彭慧丽, 金凯忠, 付聪聪, 等. 基于序列格的隐私时序模式挖掘方法[J]. 电子学报, 2020, 48(1): 153-163.

PENG Hui-li, JIN Kai-zhong, FU Cong-cong, et al. Private Time Series Pattern Mining with Sequential Lattice[J]. Acta Electronica Sinica, 2020, 48(1): 153-163.

参考文献

[1] Dwork C.Differential privacy[A].Proceedings of the 33rd Int Colloquium on Automata,Languages and Programming[C].Berlin:Springer,2006.1-12.
[2] Dwork C.Lei J.Differential privacy and robust statistics[A]. Proceedings of the 41th Annual ACM Symp on Theory of Computing[C].New York:ACM,2009.371-380.
[3] Dwork C,McSherry F,Nissim K,Smith A.Calibrating noise to sensitivity in private data analysis[A].Proceedings of the 3th Theory of Cryptography Conference[C].Berlin:Springer,2006.363-385.
[4] Chen R,Fung B,Desai B C.Differentially private trajectory data publication[J].arXiv,2011,1(9):1112-2020
[5] Chen R,Mohammed N,Fung B C M,et al.Publishingset-valued data via differential privacy[A].Proceedings of the 37th Conference of Very Large Databases[C].New York:ACM,2011.1087-1098.
[6] Bonomi L,Xiong L.A two-phase algorithm for mining sequentialpatterns with differential privacy[A].Proceedings of the 22nd ACM International Conference on Information and Knowledge Management[C].New York:ACM,2013.269-278.
[7] Mohammed J Zaki.SPADE:An Efficient Algorithm for Mining Frequent Sequences[J].Machine Learning,2001,1(42):31-60.
[8] Chen R,Fung B,Desai B.C,et al.Differentially private transit data publication:a case study on the montreal transportation system[A]. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York:ACM,2012.213-221.
[9] Chen R,Gergely A,Claude C.Differentially private sequential data publication via variable-length n-grams[A].Proceedings of the 19th ACM Conf on Computer and Communications Security[C].New York:ACM,2012.638-649.
[10] Cheng X,S Su,S Xu,et al.Dp-apriori:A differentially private frequent itemset mining algorithm based on transaction splitting[J].Computers & Security,2015,50(1):74-90.
[11] Su S,Cheng X,et al.Differentially private frequent sequence mining via sampling-based candidate pruning[A].Proceedings of the 31st IEEE International Conference on Data Engineering[C].Washington,DC:IEEE Computer Society,2015.1035-1046.
[12] Hua Jingyu,Gao Yue,Zhong Sheng.Differentially private publication of general time-serial trajectory data[A].Proc of INFCOM[C].Piscataway,NJ:IEEE,2015.163-175.
[13] R Agrawal,R Srikant.Fast algorithms for mining association rules in large databases[J].Proceedings of the VLDB Endowment,1994,23(3):487-499.
[14] Zeng C,J F Naughton,J Y Cai.On differentially private frequent itemset mining[J].Proceedings of the VLDB Endowment,2012,6(1):25-36.
[15] 李杨,郝志峰,温雯,等.差分隐私保护k-means聚类方法研究[J].计算机科学,2013,40(3):287-290. Li Y,Hao Z,Wen W,et al.Research on differential privacy preserving k-means clustering[J].Computer Science,2013,40(3):287-290.(in Chinese)
[16] 张啸剑,王淼,孟小峰.差分隐私保护下一种精确挖掘top-k频繁模式方法[J].计算机研究与发展,2014,51(1):104-114. Zhang X,Wang M,Meng X.An accurate method for mining top-k frequent pattern under differential privacy[J].Journal of Computer Research and Development,2014,51(1):104-114.(in Chinese)
[17] 张啸剑,孟小峰.面向数据发布和分析的差分隐私保护研究综述[J].计算机学报,2014,37(4):927-949. Zhang X,Meng X.Differential privacy in data publication and analysis[J].Chinese Journal of Computers,2014,37(4):927-949.(in Chinese)
[18] McSherry F.Privacy integrated queries:an extensible platform for privacy-preserving data analysis[A].Proceedings of the 35th ACM SIGMOD Int Conf on Management of Data[C].New York:ACM,2009.19-30.
[19] Xiang Cheng,Sen Su,Shengzhi Xu,Li Xiong,et al.A two-phase algorithm for differentially private frequent subgraph mining[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(8):1411-1425.
[20] Chen R,Noman M.,B.C.M.Fung,et al.Publishing set-valued data via sifferential Privacy[J].PVLDB,2011,4(11):1087-1098.

基于序列格的隐私时序模式挖掘方法

Private Time Series Pattern Mining with Sequential Lattice

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	曾卓, 汪成亮, 马飞. 基于差分隐私的活动模式保护与时空轨迹发布方法[J]. 电子学报, 2023, 51(3): 552-563.
[2]	张轶, 翟盛华, 陶海红. 雨衰时间序列的混沌识别与预测[J]. 电子学报, 2023, 51(2): 365-371.
[3]	张少波, 原刘杰, 毛新军, 朱更明. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报, 2022, 50(9): 2181-2188.
[4]	沈鹏飞, 徐臻, 王英. 基于嵌套生成对抗学习的网络嵌入[J]. 电子学报, 2022, 50(9): 2155-2163.
[5]	康海燕, 冀源蕊. 基于本地化差分隐私的时序位置发布方案研究[J]. 电子学报, 2022, 50(9): 2222-2232.
[6]	孙晨峰, 吕卫民, 戴洪德, 张浩晨. 一种基于TimeGAN和OCSVM的多元退化设备小子样数据增广方法[J]. 电子学报, 2022, 50(11): 2678-2687.
[7]	王森, 王煜, 宁德军. 复杂软件系统健康状态智能感知与诊断模型[J]. 电子学报, 2021, 49(9): 1799-1808.
[8]	袁水莲, 皮德常, 胥萌. 基于差分隐私的轨迹隐私保护方法[J]. 电子学报, 2021, 49(7): 1266-1273.
[9]	金苍宏, 董腾然, 陈天翼, 吴明晖, 李国军, 周胜利. 融合序列分解与时空卷积的时序预测算法[J]. 电子学报, 2021, 49(2): 233-238.
[10]	罗远兴, 李志红, 梁兴, 李超, 胡凤城. 基于EMD‑LS的非平稳时间序列多重分形去趋势波动分析方法[J]. 电子学报, 2021, 49(12): 2323-2329.
[11]	吴玉佳, 李晶, 宋成芳, 常军. 基于高效用神经网络的文本分类方法[J]. 电子学报, 2020, 48(2): 279-284.
[12]	陈思, 付安民, 柯海峰, 苏铓, 孙怀江. MCDP:基于神经网络的多集群分布式差分隐私数据发布方法[J]. 电子学报, 2020, 48(12): 2297-2303.
[13]	方晨, 郭渊博, 王娜, 甄帅辉, 唐国栋. 基于生成对抗网络的差分隐私数据发布方法[J]. 电子学报, 2020, 48(10): 1983-1992.
[14]	刘露, 胡封晔, 牛亮, 彭涛. 异质网络中基于节点影响力的相似度度量方法[J]. 电子学报, 2019, 47(9): 1929-1936.
[15]	黄飞江, 陈演羽, 李廷会, 袁海波, 单庆晓. 基于灰色模型和混沌时间序列的卫星钟差预测算法[J]. 电子学报, 2019, 47(7): 1416-1424.