基于影响度的隐私保护关联规则挖掘算法 徐龙琴1，刘双印1,2 (1. 广东海洋大学信息学院，广东 湛江 524025；2. 中国农业大学信息与电气工程学院，北京 100083) 摘 要：将T检验思想引入隐私保护数据挖掘算法，提出基于影响度的隐私保护关联规则挖掘算法。将影响度作为关联规则生成准则，以减少冗余规则和不相关规则，提高挖掘效率；通过调整事务间敏感关联规则的项目，实现敏感规则隐藏。实验结果表明，该算法能使规则损失率和增加率降低到6%以下。 关键词关键词：：隐私保护；关联规则；影响度；数据挖掘；敏感规则
Privacy Preserving Association Rule Mining Algorithm Based on Influence Measure
XU Long-qin1, LIU Shuang-yin1,2 (1. College of Information, Guangdong Ocean University, Zhanjiang 524025, China; 2. College of Information and Electrical Engineering, China Agricultural University, Beijing 100083, China)
【Abstract】This paper introduces the idea of T-testing into privacy preserving data mining algorithms, proposes privacy preserving association rule mining algorithm based on influence measure. Considering influence measure as association rules generated as a criterion is to reduce the redundant rules and irrelevant rules so as to improve the efficiency of mining. Sensitive rules can be hided by adjusting the transaction association rules between the sensitive rule hiding sensitive items to achieve. Experimental results shows that, the algorithm makes the rules for side effects such as loss rate and the rate of decrease to as low as 6%. 【Key words】privacy preserving; association rule; influence measure; data mining; sensitive rule
DOI: 10.3969/j.issn.1000-3428.2011.11.020
计 算 机 工 程 Computer Engineering 第37卷 第11期
Vol.37 No.11 2011年6月
June 2011
·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)11—0059—03 文献标识码文献标识码：：A 中图分类号中图分类号：：TP182
1 概述 随着网络技术、计算机存储技术的快速发展，浩瀚的数据收集存储变得更加便捷，出现了数据爆炸而知识匮乏的被动局面。关联规则数据挖掘可以从海量数据中抽取、分析并挖掘出隐藏的、用户感兴趣的规则、规律和模式，能有效解决上述困境，并在辅助决策预测、异常模式检测、欺诈行为发现、科学探索及医学研究等诸领域发挥积极作用，但同时也给隐私数据和信息安全带来严重的威胁。 例如，通过挖掘医院患者病历数据可发现不同疾病间潜藏的关联，制定更有针对性的治疗方案，但也造成患者隐私不同程度的泄露，使患者经常遭受婴儿用品厂商、婚姻中介商、医药保健公司等外界的“骚扰”。此外超市消费记录、网站购物偏好、个人或公司的信贷记录等信息中的关联关系也容易使个人或公司的隐私遭到侵害。 为此，隐私保护关联规则数据挖掘成为当前研究的热点，有关专家学者相继提出了许多解决的方法和对策[1-6]，但这些方法都以Apriori算法和支持度-置信度框架生成关联规则，没考虑规则项目间相关度，产生了许多冗余、不相关的规则，不仅影响挖掘效率，还严重影响非敏感规则的支持度。 针对上述不足，本文提出一种新的隐私保护关联规则挖掘算法，可减少冗余规则的产生，提高挖掘效率和敏感规则隐私保护的综合性能。
2 研究研究背景背景 针对关联规则数据挖掘引起隐私泄漏问题，文献[1]提出了敏感规则、数据清理等概念，在尽可能不影响其他规则重
要性前提下，降低给定规则重要性，实现关联规则挖掘隐私保护。文献[2]使用“未知”值替换敏感数据，方法实现简单，但仅适用于少量项目值的挖掘。文献[3]使用删除项目方法，将含有许多后件的某项或多项删除，虽易实现，但当有许多规则存在时，作为后件的项目也常在其他规则中作为前件，如将该项目删除，易造成其他有效规则被误删除。文献[4]提出了SWA算法，通过删除包含敏感规则集部分项集方法，降低敏感规则支持度以隐藏敏感规则，该算法效率较高，适宜处理大规模的数据库。文献[5]将数据干扰和查询限制相结合，提出数据随机处理的隐私保护策略，有效实现了隐私保护的关联规则挖掘。文献[6]通过增减事务方法，降低敏感规则的支持度，实现敏感规则隐藏，但删除强相关事务，存在原数据库基本特征被修改，非敏感项目丢失等问题。文献[7]采用添加和删除项目相结合的方法，实现敏感知识隐藏，并通过选择最佳移动项候选事务减少非敏感事务的丢失率。 以上算法都是以传统的数据挖掘Apriori算法和支持度-置信度框架为基础，生成关联规则，所挖掘到的强关联规则中并不都是用户感兴趣的敏感规则，造成规则中存在大量冗
基金项目基金项目：：国家星火计划基金资助项目(2007EA780068)；广东省 自然科学基金资助项目(7010116)；广东省科技计划基金资助项目(2010B020315025)；湛江市科技计划基金资助项目(2010C3113011) 作者简介作者简介：：徐龙琴(1977－)，女，讲师、硕士、CCF会员，主研方向：数据库安全，智能信息系统，人工智能；刘双印，副教授、 博士研究生、CCF会员 收稿日期收稿日期：：2011-01-29 E-mail：xlqlw@126.com 60 计 算 机 工 程 2011年6月5日 余不相关的规则，影响用户对规则的选择和挖掘效率，表1所示的实例说明了利用该框架生成规则时存在的不足。因篇幅所限，本文只列举部分数据和讨论若干长度为2的项目集，并假定支持度minSupp=0.25，置信度minConf=0.45。 表1 网上交易网上交易事务数据库事务数据库 事务号 项目集(Items) t1 A, B, C, D, J, Q t2 B, H, K, M, D, U … … t10 A, B, H, J, K, U 由表1计算可知：A⇒J和C⇒B的支持度和置信度都分别为0.4和1，大于设定的阈值，按以往惯例则认为都是有效的关联规则。但发现不管C是否出现，B总出现，显然C⇒B不是有效的关联规则。另外，U⇒M的支持度和置信度分别为0.3和0.6，大于设定的阈值，通常认为也应该为有效的规则，但计算得到P(U∪M)=P(U)P(M)，从数理统计角度讲它们是不相关的。此外对表1采用数据变换法、数据阻塞法降低支持度，实现规则隐藏，但对非敏感规则支持度影响很大，存在规则丢失和虚假规则增生等缺陷。 为减少对非敏感规则的影响，提高挖掘效率，本文提出了一种基于影响度的隐私保护关联规则挖掘方法，把影响度作为关联规则生成的衡量准则，可大大减少不相关规则和冗余规则，加快挖掘速度；同时引入最佳候选移动项，在保证非敏感项影响最小前提下更新事务集，降低敏感规则的支持度和置信度，实现敏感规则隐藏。 3 基于影响度的隐私保护关联规则挖掘算法 鉴于传统挖掘算法存在挖掘效率低等不足，本文将数理统计中检验样本差异显著性的重要统计工具T检验的思想引入到隐私保护关联规则挖掘中，采用T检验来分析规则X⇒Y的Confidence(X⇒Y)与期望置信度P(Y)之间的差异，作为关联规则生成衡量准则。即根据关联规则影响度大小，在生成关联规则的过程中将差异不显著的规则直接过滤掉，可有效减少冗余的和不相关的规则的产生，提高关联规则的挖掘 效率。 3.1 相关概念 3.1.1 关联规则挖掘 假定项目集为I={i1, i2,…, im}，事务数据库DB={t1, t2,…, tn}，其中，ti为一个事务，∀ti⊆I，即每个事务ti所包含的项集都是I的子集。关联规则形式化表示为X⇒Y，其中，X⊆I，Y⊆I且X∩Y=∅[8]。关联规则的强度可用支持度Support和置信度Confidence度量。计算表达式如下： Support(X⇒Y)=|X∪Y|/|DB|≥minSupp (1) Confidence(X⇒Y)=|X∪Y|/|X|≥minConf (2) 其中，minConf为最小置信度；minSupp为最小支持度。为了隐藏挖掘出的敏感规则，由以上表达式可知，通过减少项目X和Y同时出现的频率，降低支持度Support和置信度Confidence，即可达到敏感规则隐藏的目的。 3.1.2 关联规则影响度 关联规则的影响度用来表征规则的前项和后项的相关程度，influence(X⇒Y)计算表达式定义如下： 定义1 ()()()()(1())ConfidenceXYPYinfluenceXYPYPYn⇒−⇒=− (3) 若influence (X⇒Y)>tα(n)，即P(Y|X)与P(Y)之间的差异较大，则表明Y的出现受X的影响较大，规则X⇒Y是敏感的和需要保护的。tα(n)为样本容量为n的T分布显著水平为α
的下临界值，称为最小影响度。根据概率统计的需要及n值较大，tα(n)常用正态分布下显著水平为α=0.05下的临界值u
α
替代，即tα(n)≈u0.05=1.96。
基于T检验影响度的生成关联衡量准则将关联规则分为
4类： (1)不相关规则 如Confidence(X⇒Y)= P(Y)，即P(X∪Y)= P(X)P(Y)，则项集X和项集Y构成的X⇒Y为不相关规则，包含不相关规则的事务，称为不相关事务。 (2)冗余规则 若(Support(X⇒Y)≥minSupp)∧(P(Y)≥Confidence(X⇒Y)≥minConf)成立，则称X⇒Y为冗余规则，该冗余规则在挖掘的过程予以删除，以提高效率。 (3)弱关联规则：若(Support(X⇒Y)≥minSupp)∧(Confidence (X⇒Y)≥minConf)∧(0成立，则称X⇒Y为弱关联规则，包含弱关联规则X⇒Y的事务，称为弱相关事务。 (4)强关联规则 若(Support(X⇒Y)≥minSupp)∧(P(Y)≥Confidence(X⇒Y)≥minConf)∧(influence(X⇒Y)>t0.05(n)≈u0.05= 1.96)成立，则称
