基于BCU-Tree与字典的高效用挖掘快速脱敏算法

doi:10.11772/j.issn.1001-9081.2021122161

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (2): 413-422.DOI: 10.11772/j.issn.1001-9081.2021122161

• 数据科学与技术 • 上一篇

基于BCU-Tree与字典的高效用挖掘快速脱敏算法

尹春勇(), 李荧

南京信息工程大学计算机与软件学院，南京 210044

收稿日期:2021-12-27 修回日期:2022-02-19 接受日期:2022-02-23 发布日期:2022-05-16 出版日期:2023-02-10
通讯作者: 尹春勇
作者简介:李荧（1995—），女，江苏淮安人，硕士研究生，主要研究方向：数据挖掘、隐私保护。
基金资助:
国家自然科学基金资助项目(61772282)

Fast sanitization algorithm based on BCU-Tree and dictionary for high-utility mining

Chunyong YIN(), Ying LI

School of Computer and Software，Nanjing University of Information Science and Technology，Nanjing Jiangsu 210044，China

Received:2021-12-27 Revised:2022-02-19 Accepted:2022-02-23 Online:2022-05-16 Published:2023-02-10
Contact: Chunyong YIN
About author:LI Ying， born in 1995， M. S. candidate. Her research interests include data mining， privacy preserving.
Supported by:
National Natural Science Foundation of China(61772282)

摘要/Abstract

摘要：

针对隐私保护效用挖掘（PPUM）中脱敏时间长、计算复杂度高，以及算法副作用大等问题，提出一种基于BCU-Tree和字典（BCUTD）的高效用挖掘快速脱敏算法。该算法提出了一种新的树结构BCU-Tree来存储敏感项信息，基于按位运算符编码模型降低树的构建时间并减小搜索空间。采用字典表存储树结构中的所有节点，修改敏感项时只需访问字典表，最终达到数据库脱敏目的。在4个不同的数据集上进行的实验中，BCUTD算法在脱敏时间和副作用上的表现要明显优于经典的优先隐藏高效用项（HHUIF）算法、最大敏感效用-最大项效用（MSU-MAU）算法和使用树与表结构的快速扰动（FPUTT）算法。实验结果表明，BCUTD算法能够有效减少脱敏时间，降低算法副作用以及计算复杂度。

关键词: 敏感信息, 高效用挖掘, 隐私保护, 字典, 位图编码

Abstract:

Privacy Preserving Utility Mining （PPUM） has problems of long sanitization time， high computational complexity， and high side effect. To solve these problems， a fast sanitization algorithm based on BCU-Tree and Dictionary （BCUTD） for high-utility mining was proposed. In the algorithm， a new tree structure called BCU-Tree was presented to store sensitive item information， and based on the bitwise operator coding model， the tree construction time and search space were reduced. The dictionary table was used to store all nodes in the tree structure， and only the dictionary table needed to be accessed when the sensitive item was modified. Finally， the sanitization process was completed. In the experiments on four different datasets， BCUTD algorithm has better performance on sanitization time and high side effect than Hiding High Utility Item First （HHUIF）， Maximum Sensitive Utility-MAximum item Utility （MSU-MAU）， and Fast Perturbation Using Tree and Table structures （FPUTT）. Experimental results show that BCUTD algorithm can effectively speed up the sanitization process， reduce the side effect and computational complexity of the algorithm.

Key words: sensitive information, high-utility mining, privacy preserving, dictionary, bitmap code

中图分类号:

TP309.2

尹春勇, 李荧. 基于BCU-Tree与字典的高效用挖掘快速脱敏算法[J]. 计算机应用, 2023, 43(2): 413-422.

Chunyong YIN, Ying LI. Fast sanitization algorithm based on BCU-Tree and dictionary for high-utility mining[J]. Journal of Computer Applications, 2023, 43(2): 413-422.

图/表 17

参考文献 44

1	CHEN M S， HAN J W， YU P S. Data mining： an overview from a database perspective［J］. IEEE Transactions on Knowledge and Data Engineering， 1996， 8（6）： 866-883. 10.1109/69.553155
2	HAN J W， PEI J， YIN Y W， et al. Mining frequent patterns without candidate generation： a frequent-pattern tree approach［J］. Data Mining and Knowledge Discovery， 2004， 8（1）： 53-87. 10.1023/b:dami.0000005258.31418.83
3	TELIKANI A， GANDOMI A H， SHAHBAHRAMI A. A survey of evolutionary computation for association rule mining［J］. Information Sciences， 2020， 524： 318-352. 10.1016/j.ins.2020.02.073
4	QIN J W， WANG J Y， LI Q Y， et al. Differentially private frequent episode mining over event streams［J］. Engineering Applications of Artificial Intelligence， 2022， 110： No.104681. 10.1016/j.engappai.2022.104681
5	WU Y X， ZHU C R， LI Y， et al. NetNCSP： nonoverlapping closed sequential pattern mining［J］. Knowledge-Based Systems， 2020， 196： No.105812. 10.1016/j.knosys.2020.105812
6	SRIVASTAVA G， LIN J C W， PIROUZ M， et al. A pre-large weighted-fusion system of sensed high-utility patterns［J］. IEEE Sensors Journal， 2021， 21（14）： 15626-15634. 10.1109/jsen.2020.2991045
7	SONG W， HUANG C M. Mining high average-utility itemsets based on particle swarm optimization［J］. Data Science and Pattern Recognition， 2020， 4（2）： 19-32.
8	YAO H， HAMILTON H J， GENG L Q. A unified framework for utility-based measures for mining itemsets［C］// Proceedings of the 2nd Workshop on Utility-Based Data Mining Held in Conjunction with the KDD Conference. New York： ACM， 2006：28-37.
9	GENG L Q， HAMILTON H J. Interestingness measures for data mining： a survey［J］. ACM Computing Surveys， 2006， 38（3）： No.9-es. 10.1145/1132960.1132963
10	TAN P N， KUMAR V， SRIVASTAVA J. Selecting the right objective measure for association analysis［J］. Information Systems， 2004， 29（4）： 293-313. 10.1016/S0306-4379(03)00072-3
11	McGARRY K. A survey of interestingness measures for knowledge discovery［J］. The Knowledge Engineering Review， 2005， 20（1）： 39-61. 10.1017/s0269888905000408
12	HILDERMAN R J， HAMILTON H J. Measuring the interestingness of discovered knowledge： a principled approach［J］. Intelligent Data Analysis， 2003， 7（4）： 347-382. 10.3233/ida-2003-7406
13	SILBERSCHATZ A， TUZHILIN A. On subjective measures of interestingness in knowledge discovery［C］// Proceedings of the First International Conference on Knowledge Discovery and Data Mining. Menlo Park， CA： AAAI Press， 1995：275-281.
14	DE BIE T. Maximum entropy models and subjective interestingness： an application to tiles in binary databases［J］. Data Mining and Knowledge Discovery， 2011， 23（3）： 407-446. 10.1007/s10618-010-0209-3
15	YAO H， HAMILTON H J. Mining itemset utilities from transaction databases［J］. Data and Knowledge Engineering， 2006， 59（3）： 603-626. 10.1016/j.datak.2005.10.004
16	冯登国，张敏，李昊. 大数据安全与隐私保护［J］. 计算机学报， 2014， 37（1）： 246-258.
	FENG D G， ZHANG M， LI H. Big data security and privacy protection［J］. Chinese Journal of Computers， 2014， 37（1）： 246-258.
17	BERTINO E， LIN D， JIANG W. A survey of quantification of privacy preserving data mining algorithms［M］// AGGARWAL C C， YU P S. Privacy-Preserving Data Mining： Models and Algorithms. Boston： Springer， 2008： 183-205. 10.1007/978-0-387-70992-5_8
18	张啸剑，孟小峰. 面向数据发布和分析的差分隐私保护［J］. 计算机学报， 2014， 37（4）： 927-949. 10.3724/SP.J.1016.2014.00927
	ZHANG X J， MENG X F. Differential privacy in data publication and analysis［J］. Chinese Journal of Computers， 2014， 37（4）： 927-949. 10.3724/SP.J.1016.2014.00927
19	SLIJEPČEVIĆ D， HENZL M， DANIEL KLAUSNER L， et al. k-Anonymity in practice： how generalisation and suppression affect machine learning classifiers［J］. Computers and Security， 2021， 111： No.102488. 10.1016/j.cose.2021.102488
20	LIU J， TIAN Y， ZHOU Y， et al. Privacy preserving distributed data mining based on secure multi-party computation［J］. Computer Communications， 2020， 153： 208-216. 10.1016/j.comcom.2020.02.014
21	YEH J S， HSU P C. HHUIF and MSICF： novel algorithms for privacy preserving utility mining［J］. Expert Systems with Applications， 2010， 37（7）： 4779-4786. 10.1016/j.eswa.2009.12.038
22	LIN J C W， GAN W S， FOURNIER-VIGER P， et al. Fast algorithms for mining high-utility itemsets with various discount strategies［J］. Advanced Engineering Informatics， 2016， 30（2）： 109-126. 10.1016/j.aei.2016.02.003
23	YUN U， KIM J. A fast perturbation algorithm using tree structure for privacy preserving utility mining［J］. Expert Systems with Applications， 2015， 42（3）： 1149-1165. 10.1016/j.eswa.2014.08.037
24	LIU X， CHEN G L， WEN S T， et al. An improved sanitization algorithm in privacy-preserving utility mining［J］. Mathematical Problems in Engineering， 2020， 2020： No.7489045. 10.1155/2020/7489045
25	LIU X， WEN S T， ZUO W L. Effective sanitization approaches to protect sensitive knowledge in high-utility itemset mining［J］. Applied Intelligence， 2020， 50（1）： 169-191. 10.1007/s10489-019-01524-2
26	JANGRA S， TOSHNIWAL D. Efficient algorithms for victim item selection in privacy-preserving utility mining［J］. Future Generation Computer Systems， 2022， 128： 219-234. 10.1016/j.future.2021.10.008
27	SHEN Y D， ZHANG Z， YANG Q. Objective-oriented utility-based association mining［C］// Proceedings of the 2002 IEEE International Conference on Data Mining. Piscataway： IEEE， 2002：426-433. 10.1109/icdm.2002.1183878
28	HU J Y， MOJSILOVIC A. High-utility pattern mining： a method for discovery of high-utility item sets［J］. Pattern Recognition， 2007， 40（11）： 3317-3324. 10.1016/j.patcog.2007.02.003
29	AHMED C F， TANBEER S K， JEONG B S， et al. Efficient tree structures for high utility pattern mining in incremental databases［J］. IEEE Transactions on Knowledge and Data Engineering， 2009， 21（12）： 1708-1721. 10.1109/tkde.2009.46
30	WU J M T， LIN J C W， TAMRAKAR A. High-utility itemset mining with effective pruning strategies［J］. ACM Transactions on Knowledge Discovery from Data， 2019， 13（6）： No.58. 10.1145/3363571
31	KRISHNAMOORTHY S. Pruning strategies for mining high utility itemsets［J］. Expert Systems with Applications， 2015， 42（5）： 2371-2381. 10.1016/j.eswa.2014.11.001
32	ZIDA S， FOURNIER-VIGER P， LIN J C W， et al. EFIM： a highly efficient algorithm for high-utility itemset mining［C］// Proceedings of the 2015 Mexican International Conference on Artificial Intelligence， LNCS 9413. Cham： Springer， 2015：530-546.
33	GAN W S， LIN J C W， FOURNIER-VIGER P， et al. HUOPM： high-utility occupancy pattern mining［J］. IEEE Transactions on Cybernetics， 2020， 50（3）： 1195-1208. 10.1109/tcyb.2019.2896267
34	WU J M T， SRIVASTAVA G， WEI M， et al. Fuzzy high-utility pattern mining in parallel and distributed Hadoop framework［J］. Information Sciences， 2021， 553： 31-48. 10.1016/j.ins.2020.12.004
35	LI S X， MU N K， LE J Q， et al. A novel algorithm for privacy preserving utility mining based on integer linear programming［J］. Engineering Applications of Artificial Intelligence， 2019， 81： 300-312. 10.1016/j.engappai.2018.12.006
36	DINH T， QUANG M N， LE B. A novel approach for hiding high utility sequential patterns［C］// Proceedings of Proceedings of the 6th International Symposium on Information and Communication Technology. New York： ACM， 2015：121-128. 10.1145/2833258.2833271
37	QUANG M N， HUYNH U， DINH T， et al. An approach to decrease execution time and difference for hiding high utility sequential patterns［C］// Proceedings of the 2016 International Symposium on Integrated Uncertainty in Knowledge Modelling and Decision Making， LNCS 9978. Cham： Springer， 2016：435-446.
38	LE B， DINH D T， HUYNH V N， et al. An efficient algorithm for Hiding High Utility Sequential Patterns［J］. International Journal of Approximate Reasoning， 2018， 95： 77-92. 10.1016/j.ijar.2018.01.005
39	ARYABARZAN N， MINAEI-BIDGOLI B， TESHNEHLAB M. negFIN： an efficient algorithm for fast mining frequent itemsets［J］. Expert Systems with Applications， 2018， 105： 129-143. 10.1016/j.eswa.2018.03.041
40	LIN J C W， WU T Y， FOURNIER-VIGER P， et al. Fast algorithms for hiding sensitive high-utility itemsets in privacy-preserving utility mining［J］. Engineering Applications of Artificial Intelligence， 2016， 55： 269-284. 10.1016/j.engappai.2016.07.003
41	DUONG Q H， FOURNIER-VIGER P， RAMAMPIARO H， et al. Efficient high utility itemset mining using buffered utility-lists［J］. Applied Intelligence， 2018， 48（7）： 1859-1877. 10.1007/s10489-017-1057-2
42	GE Z Q， SONG Z H， DING S X， et al. Data mining and analytics in the process industry： the role of machine learning［J］. IEEE Access， 2017， 5： 20590-20616. 10.1109/access.2017.2756872
43	TASSA T. Secure mining of association rules in horizontally distributed databases［J］. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（4）： 970-983. 10.1109/tkde.2013.41
44	LIN J C W， LIU Q K， FOURNIER-VIGER P， et al. A sanitization approach for hiding sensitive itemsets based on particle swarm optimization［J］. Engineering Applications of Artificial Intelligence， 2016， 53： 1-18. 10.1016/j.engappai.2016.03.007

TID	事务（项，内部效用）	tu（T_i ）
T₁	（C， 7），（D， 1），（E， 1）	15
T₂	（A， 1），（C， 2），（E， 2）	11
T₃	（B， 6），（C， 4），（D， 3），（E， 7）	54
T₄	（B， 5），（C， 3），（D， 9）	72
T₅	（A， 3），（C， 10），（D， 3）	43
T₆	（C， 5），（E， 9）	23
T₇	（A， 6），（C， 9），（D， 2），（E， 5）	61
T₈	（A， 1），（B， 6），（C， 2），（D， 5），（E， 3）	61

TID	事务（项，内部效用）	tu（T_i ）
T₁	（C， 7），（D， 1），（E， 1）	15
T₂	（A， 1），（C， 2），（E， 2）	11
T₃	（B， 6），（C， 4），（D， 3），（E， 7）	54
T₄	（B， 5），（C， 3），（D， 9）	72
T₅	（A， 3），（C， 10），（D， 3）	43
T₆	（C， 5），（E， 9）	23
T₇	（A， 6），（C， 9），（D， 2），（E， 5）	61
T₈	（A， 1），（B， 6），（C， 2），（D， 5），（E， 3）	61

项集	效用	项集	效用	项集	效用
｛ACD｝	131	｛BD｝	153	｛CDE｝	120
｛ACDE｝	104	｛BDE｝	104	｛D｝	138
｛AD｝	110	｛BCDE｝	110
｛BCD｝	162	｛CD｝	173

项集	效用	项集	效用	项集	效用
｛ACD｝	131	｛BD｝	153	｛CDE｝	120
｛ACDE｝	104	｛BDE｝	104	｛D｝	138
｛AD｝	110	｛BCDE｝	110
｛BCD｝	162	｛CD｝	173

敏感项集（SI）	TIDs
｛CD｝	T₁，T₃，T₄，T₅，T₇，T₈
｛BD｝	T₃，T₄，T₈
｛ACD｝	T₅，T₇，T₈

基于BCU-Tree与字典的高效用挖掘快速脱敏算法

Fast sanitization algorithm based on BCU-Tree and dictionary for high-utility mining

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 44

相关文章 15

编辑推荐

Metrics

TID	项	排列后的项和效用
T₁	（C，7），（D，1）	（C，7），（D，6）
T₃	（B，6），（C，4），（D，3）	（B，18），（C，4），（D，18），
T₄	（B，5），（C，3），（D，9）	（B，15），（C，3），（D，54）
T₅	（A，3），（C，10），（D，3）	（A，15），（C，10），（D，18）
T₇	（A，6），（C，9），（D，2）	（A，30），（C，9），（D，12）
T₈	（A，1），（B，6），（C，2），（D， 5）	（B，18），（A，5），（C，2），（D，30）

数据集	事务数量	项数量	平均长度	密度/%
foodmart	4 141	1 559	4.42	0.28
retail	88 162	16 470	1 030.00	6.25
t20i6d100k	99 922	893	24.77	2.77
t25i10d10k	9 976	929	24.77	2.67

[1]	黄诚, 赵倩锐. 基于语言模型词嵌入和注意力机制的敏感信息检测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2009-2014.
[2]	王颖洁, 朱久祺, 汪祖民, 白凤波, 弓箭. 自然语言处理在文本情感分析领域应用综述[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1011-1020.
[3]	吴静雯, 殷新春, 宁建廷. 车载自组网中可撤销的聚合签名认证方案[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 911-920.
[4]	钟洋, 毕仁万, 颜西山, 应作斌, 熊金波. 支持隐私保护训练的高效同态神经网络[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3792-3800.
[5]	赵乐, 张恩, 秦磊勇, 李功丽. 基于区块链的多方隐私保护k-means聚类方案[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3801-3812.
[6]	梁天恺, 曾碧, 陈光. 联邦学习综述：概念、技术、应用与挑战[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3651-3662.
[7]	张国鹏, 陈学斌, 王豪石, 翟冉, 马征. 面向本地差分隐私的K-Prototypes聚类方法[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3813-3821.
[8]	孙睿, 李超, 王伟, 童恩栋, 王健, 刘吉强. 基于区块链的联邦学习研究进展[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3413-3420.
[9]	韩佳良, 韩宇栋, 刘譞哲, 赵耀帅, 冯迪. 基于云‒端融合的个性化推荐服务系统[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3506-3512.
[10]	朱栋, 殷新春, 宁建廷. 车联网中具有强隐私保护的无证书签名方案[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3091-3101.
[11]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[12]	张永斌, 常文欣, 孙连山, 张航. 基于字典的域名生成算法生成域名的检测方法[J]. 计算机应用, 2021, 41(9): 2609-2614.
[13]	裴春阳, 樊宽刚, 马政. 基于边缘保留分解和改进稀疏表示的医学图像融合[J]. 计算机应用, 2021, 41(7): 2092-2099.
[14]	秦静, 安雯, 季长清, 汪祖民. 无线体域网隐私保护机制研究综述[J]. 计算机应用, 2021, 41(4): 970-975.
[15]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.

项	外部效用	项	外部效用
A	5	D	6
B	3	E	2
C	1

项	外部效用	项	外部效用
A	5	D	6
B	3	E	2
C	1

项	次数	项	次数
D	6	A	3
C	6	B	3

项	次数	项	次数
D	6	A	3
C	6	B	3