基于簇和阈值区间的高效关联规则隐藏算法
牛新征1 王崇屹1 叶志佳1 佘 堃2
【摘 要】摘 要 关联规则隐藏是隐私保护数据挖掘(privacy-preserving data mining, PPDM)的一种重要方法.针对当前的关联规则隐藏算法直接操作事务数据、I/O开销较大的缺陷,提出一种基于FP-tree快速关联规则隐藏的算法FP-DSRRC.算法首先对FP-tree的结构进行改进,增设事务编号索引并建立双向遍历结构,进而利用改进的FP-tree对事务信息进行快速处理,避免了遍历原始数据集产生的大量I/O时间;然后通过建立和维护事务索引表实现对敏感项的快速查找,并基于分簇策略对关联规则处理,以簇为单位进行敏感规则消除,同时采用规则支持度和置信度阈值区间的思想,减少了关联规则隐藏处理对原始数据集的影响;最后通过实验测试证明:相较于传统关联规则隐藏算法,FP-DSRRC算法在保证生成的数据集质量的同时,减少了50%~70%的算法执行时间,并在大规模真实数据集上有较好的可用性. 【期刊名称】计算机研究与发展 【年(卷),期】2017(054)012 【总页数】12
【关键词】关键词 隐私保护;关联规则隐藏;频繁模式树; 敏感规则; 数据清洗
(xinzhengniu@uestc.edu.cn)
随着关联规则技术的逐渐成熟以及大数据云计算的不断发展,通过关联规则能挖掘出的信息越来越多,其中可能包含了用户的敏感数据和隐私信息[1].因此,Agrawal等人[2]在2000年提出的隐私保护数据挖掘(privacy-preserving
data mining, PPDM)成为数据挖掘领域的研究重点,而关联规则隐藏作为解决数据挖掘中隐私问题的一项关键技术也引起了国内外学者的重视.
关联规则挖掘最初由Agrawal[3]在1993年提出,其目的是为了挖掘事务数据库中各项集存在的价值关联,为相关决策提供依据.对于一些包含敏感关联规则的数据,在发布数据前修改原始数据集,从而达到隐藏敏感规则的目的,这个过程就是关联规则隐藏.
1 相关工作
当前关联规则隐藏技术大致可分为6种[4]:基于启发式的方法(heuristic approach)、基于边界的方法(border approach)、基于重构的方法(reconstruction approach)、基于加密的方法(cryptographic approach)、精确方法(exact approach)和基于混合的方法(hybrid techniques approach). 启发式方法主要采用数据失真技术和数据阻塞技术,通过向原始事务数据库中添加噪声数据或将原敏感项集的某些属性删除,以达到降低敏感规则支持度或置信度的目的.在基于启发式的关联规则隐藏算法中,文献[5]提出基于频繁项集相交点阵(intersection lattice)的关联规则隐藏算法(heuristic for confidence and support reduction based on intersection lattice, HCSRIL),算法首先确定对原始数据库影响最小的敏感规则,并求解最小的待修改事务数,在消除敏感规则的同时保留频繁项集,通过以上步骤尽量降低修改敏感规则对原始数据库产生的影响;文献[6]提出一种基于数据失真技术的关联规则隐藏算法(cuckoo optimization algorithm for the sensitive association rules hiding, COA4ARH),该算法分别构造了3个适应度函数用于优化隐藏方案的选择,并利用迁移函数避免陷入局部最优.
在利用减少敏感规则右项支持度的启发式算法中,文献[7]提出了DSRRC(decrease support of R.H.S item of rule clusters)算法,算法首次利用分簇和划分敏感度的思想进行关联规则隐藏,尽可能地减少算法执行对原事务数据集产生的影响,但是DSRRC算法需要对数据集进行多次排序且不能消除有多个右项的关联规则,为了解决这个问题,文献[8]提出了2个新算法:ADSRRC(advanced DSRRC)算法和RRLR(remove and reinsert L.H.S. of rule)算法,克服了这些问题.ADSRRC也是基于相同右项对敏感规则分簇,通过计算事务数据的敏感度并将其降序排序,消除对算法执行结果的影响,而RRLR算法能处理具有多个右项的规则的能力;文献[9]提出的MDSRRC(modified DSRRC)算法通过每次删除敏感度最高的敏感项保证修改后的事务数据集的质量,启发式算法通常需要向原始数据库中添加噪声或删除某些属性,当敏感规则较多时对原始数据改动较大,同时在基于数据阻塞的方法中,由于项集的某些属性被删除,后续可能无法计算其支持度和置信度. 基于边界的方法以贪心方式选择对边界影响最小的数据清洗策略,文献[10]提出一种基于阻塞的关联规则隐藏算法(border rule based blocking algorithm, BRBA).该算法基于边界规则筛选合适的事务数据进行清洗,通过安全边界策略(safety margin)降低所有敏感规则的支持度或置信度,最小化敏感规则隐藏对其他非敏感规则的影响.
基于精确方法的思想是把数据清洗当成一种原子操作,这类算法可以使消除敏感规则后的数据库没有任何影响,但是需要多次选择、比较,相比启发式算法时间开销巨大.文献[11]提出的关联规则隐藏算法无需修改频繁项集支持度,而是提出一个代表规则(representative rule, RR)的概念.通过运用代表规则,算