面向隐私保护的频繁项集挖掘算法

doi:10.3969/j.issn.1671-1122.2019.04.009

信息网络安全 ›› 2019, Vol. 19 ›› Issue (4): 73-81.doi: 10.3969/j.issn.1671-1122.2019.04.009

面向隐私保护的频繁项集挖掘算法

蒋辰^1,²(), 杨庚^1,², 白云璐^1,³, 马君梅⁴

1. 南京邮电大学计算机学院,江苏南京 210023
2. 江苏省大数据安全与智能处理重点实验室,江苏南京 210023
3. 南京中医药大学信息技术学院,江苏南京 210023
4. 31436部队,辽宁沈阳 110805

收稿日期:2018-12-05 出版日期:2019-04-10 发布日期:2020-05-11
作者简介:
作者简介：蒋辰（1995—）,男,江苏,硕士研究生,主要研究方向为网络与信息安全、隐私保护;杨庚（1961—）,男,江苏,教授,博士,主要研究方向为物联网安全、隐私保护、云计算与安全;白云璐（1988—）,女,内蒙古,讲师,博士,主要研究方向为网络与信息安全、隐私保护;马君梅（1978—）,女,辽宁,硕士,主要研究方向为通信网络管理、计算机通信、计算机网络管理。
基金资助:
国家自然科学基金[61572263, 61502251];江苏省自然科学基金面上项目[BK20161516]

Frequent Itemsets Mining Algorithm for Privacy Protection

Chen JIANG^1,²(), Geng YANG^1,², Yunlu BAI^1,³, Junmei MA⁴

1. College of Computer Science and Software, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023, China
2. Jiangsu Key Laboratory of Bigdata Security Intelligent Processing, Nanjing Jiangsu 210023, China
3. College of Information Engineering, Nanjing University of Chinese Medicine, Nanjing Jiangsu 210023, China
4. Unit 31436 of PLA, Shenyang Liaoning 110805, China

Received:2018-12-05 Online:2019-04-10 Published:2020-05-11

摘要/Abstract

摘要：

目前已有多种满足ε-差分隐私的频繁项集挖掘算法,但这些算法在处理高维数据集时难以兼顾安全性和效用性。针对该问题,文章提出一种面向隐私保护的频繁项集挖掘算法——TrunSuper。该算法先对事务数据集进行截断以降维,将事务中的项按支持度从大到小进行排序,剔除支持度较小的项,从而降低发布的频繁项集的支持度误差。文章证明了该算法在满足ε-差分隐私的同时具有较好的可用性,且在真实数据集上验证了算法的优越性。

关键词: 频繁项集挖掘, 差分隐私, 事务截断, 拉普拉斯机制

Abstract:

A variety of differentially private FIM algorithms have been proposed. However, current solutions for this problem cannot well balance privacy and data utility over large-scale data. This paper proposes a new differentially private FIM algorithm(TrunSuper). This algorithm truncates the transaction datasets to reduce the dimension, and sorts the items in decreasing order, then eliminates the items with less support. In this way, it can reduce the information loss of the frequent itemsets. This paper also theoretically proves that TrunSuper can produce reasonably accurate results while satisfying differential privacy. Experiments on several real datasets shows that TrunSuper performs better than other previous solutions.

Key words: frequent itemsets mining, differential privacy, transaction truncating, Laplace mechanism

中图分类号:

TP309

蒋辰, 杨庚, 白云璐, 马君梅. 面向隐私保护的频繁项集挖掘算法[J]. 信息网络安全, 2019, 19(4): 73-81.

Chen JIANG, Geng YANG, Yunlu BAI, Junmei MA. Frequent Itemsets Mining Algorithm for Privacy Protection[J]. Netinfo Security, 2019, 19(4): 73-81.

图/表 5

表1

表2

图1

图2

图3

参考文献 17

[1]	GUAN Lei, HU Guangjun, WANG Zhuan.Research on Network Security Situational Awareness Technology Based on Big Data[J]. Netinfo Security, 2016, 16(9): 45-50.
	管磊,胡光俊,王专.基于大数据的网络安全态势感知技术研究[J].信息网络安全,2016,16(9):45-50.
[2]	BLUM A, LIGETT K, ROTH A.A Learning Theory Approach to Non-interactive Database Privacy[J]. Journal of the ACM, 2013, 60(2): 1-25.
[3]	DWORK C.Differential Privacy[C]//Springer. International Colloquium on Automata, Languages, and Programming, July 10-14, 2006, Venice, Italy. Heidelberg: Springer, 2006: 1-12.
[4]	FANG Yuejian, ZHU Jinzhong, ZHOU Wen, et al.A Survey on Data Mining Privacy Protection Algorithms[J]. Netinfo Security, 2017, 17(2): 6-11.
	方跃坚,朱锦钟,周文,等.数据挖掘隐私保护算法研究综述[J].信息网络安全,2017,17(2):6-11.
[5]	XUN Yaling, ZHANG Jifu, QIN Xiao, et al.FiDoop-DP: Data Partitioning in Frequent Itemset Mining on Hadoop Clusters[J]. IEEE Transactions on Parallel & Distributed Systems, 2017, 28(1): 101-114.
[6]	WANG Ning, XIAO Xiaokui, YANG Yin, et al.PrivSuper: A Superset-first Approach to Frequent Itemset Mining under Differential Privacy[C]//IEEE. IEEE 3rd International Conference on Data Engineering, April 19-22, 2017, San Diego, CA, USA. New Jersey: IEEE, 2017: 809-820.
[7]	BHASKAR R, LAXMAN S, THAKURTA A.Discovering Frequent Patterns in Sensitive Data[C]//ACM. 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 25-28, 2010, Washington, DC, USA. New York: ACM, 2010: 503-512.
[8]	LI Ninghui, QARDAJI W, SU Dong, et al.PrivBasis: Frequent Itemset Mining with Differential Privacy[J]. VLDB Endowment, 2012, 5(11): 1340-1351.
[9]	ZENG Chen, NAUGHTON J F, CAI Jinyi.On Differentially Private Frequent ItemsetMining[J]. VLDB Endowment, 2012, 6(1): 25-36.
[10]	DWORK C, MCSHERRY F, NISSIM K, et al.Calibrating Noise to Sensitivity in Private Data Analysis[J]. VLDB Endowment, 2006, 7(8): 637-648.
[11]	MCSHERRY F.Mechanism Design via Differential Privacy[C]//IEEE. The 48th Annual IEEE Symposium on Foundations of Computer Science, October 21-23, 2007, Washington, DC, USA. New Jersey: IEEE, 2007: 94-103.
[12]	GHORBANI M, ABESSI M.A New Methodology for Mining Frequent Itemsets on Temporal Data[J]. IEEE Transactions on Engineering Management, 2017, 64(4): 566-573.
[13]	GAN Wenyong, WU Yingjie, SUN Lan, et al.Frequent Pattern Mining with Differential Privacy Based on Transaction Truncation[J]. Journal of Chinese Computer Systems, 2015, 36(11): 2583-2587.
	甘文勇,吴英杰,孙岚,等.基于事务截断的差分隐私频繁模式挖掘算法[J].小型微型计算机系统,2015,36(11):2583-2587.
[14]	ZHANG Xiaojian, WANG Miao, MENG Xiaofeng.An Accurate Method for Mining Top-k Frequent Pattern Under Differential Privacy[J]. Journal of Computer Research and Development, 2014, 51(1): 104-114.
	张啸剑,王淼,孟小峰.差分隐私保护下一种精确挖掘top-k频繁模式方法[J].计算机研究与发展,2014,51(1):104-114.
[15]	SU Sen, XU Shengzhi, CHENG Xiang, et al.Differentially Private Frequent Itemset Mining via Transaction Splitting[J]. IEEE Transactions on Knowledge & Data Engineering, 2015, 27(7): 1875-1891.
[16]	CHENG Xiang, SU Sen, XU Shengxiang, et al. DP-Apriori: A Differentially Private Frequent Itemset Mining Algorithm Based on Transaction Splitting[EB/OL]. , 2018-9-10.
[17]	DING Liping, LU Guoqing.Survey of Differential Privacy in Frequent Pattern Mining[J]. Journal on Communications, 2014, 35(10): 200-209.

B₁={a,b,c}				B₂={d,e,f}
¬a	¬b	¬c	3	¬d	¬e	¬f	5
¬a	¬b	c	0	¬d	¬e	f	1
¬a	b	¬c	1	¬d	e	¬f	0
¬a	b	c	0	¬d	e	f	0
a	¬b	¬c	1	d	¬e	¬f	1
a	¬b	c	1	d	¬e	f	0
a	b	¬c	1	d	e	¬f	1
a	b	c	1	d	e	f	0

数据集	Size	\|I\|	avg\|t\|
retail	63883	16470	10.3
pumsb	16280	2088	50.5
BMS2	77512	3340	5.0
accidents	30216	334	33.9

面向隐私保护的频繁项集挖掘算法

Frequent Itemsets Mining Algorithm for Privacy Protection

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 17

相关文章 2

编辑推荐

Metrics

本文评价

B₁={a,b,c}				B₂={d,e,f}
¬a	¬b	¬c	3	¬d	¬e	¬f	5
¬a	¬b	c	0	¬d	¬e	f	1
¬a	b	¬c	1	¬d	e	¬f	0
¬a	b	c	0	¬d	e	f	0
a	¬b	¬c	1	d	¬e	¬f	1
a	¬b	c	1	d	¬e	f	0
a	b	¬c	1	d	e	¬f	1
a	b	c	1	d	e	f	0

[1]	彭长根, 赵园园, 樊玫玫. 基于最大信息系数的主成分分析差分隐私数据发布算法[J]. 信息网络安全, 2020, 20(2): 37-48.
[2]	傅彦铭, 李振铎. 基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究[J]. 信息网络安全, 2019, 19(2): 43-52.

B₁={a,b,c}				B₂={d,e,f}
¬a	¬b	¬c	3	¬d	¬e	¬f	5
¬a	¬b	c	0	¬d	¬e	f	1
¬a	b	¬c	1	¬d	e	¬f	0
¬a	b	c	0	¬d	e	f	0
a	¬b	¬c	1	d	¬e	¬f	1
a	¬b	c	1	d	¬e	f	0
a	b	¬c	1	d	e	¬f	1
a	b	c	1	d	e	f	0

B₁={a,b,c}				B₂={d,e,f}
¬a	¬b	¬c	3	¬d	¬e	¬f	5
¬a	¬b	c	0	¬d	¬e	f	1
¬a	b	¬c	1	¬d	e	¬f	0
¬a	b	c	0	¬d	e	f	0
a	¬b	¬c	1	d	¬e	¬f	1
a	¬b	c	1	d	¬e	f	0
a	b	¬c	1	d	e	¬f	1
a	b	c	1	d	e	f	0