基于关联规则混合算法并行化的隐私保护方法研究

王卓伟

摘 要：随着大数据时代的发展，移动通信技术与定位技术、互联网技术等在工作生活中的应用越来越多，享受科技带来便利的同时，隐私安全问题也不容忽视。文中提出了将关联规则中基于划分的技术、随机扰动与重构技术结合起来，从而实现隐私保护的目的。该方法可以确保在原始数据安全的情况下进行其他数据的挖掘操作，而该算法并行化后，其算法执行的时间复杂度也会大大降低。

关键词：隐私保护；关联规则；并行化；数据挖掘

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2016）07-00-02

0 引 言

随着时代与科技的发展，互联网与人们日常工作和生活的关系已经密不可分。用户通过提供详细的个人信息来获取更精准的结果，更快的获得利益，同时这也增加了个人或企业隐私泄漏的可能性。近年来，隐私泄漏的事件频繁发生，如美国有史以来最大的医疗机构泄漏事件；国内社保系统漏洞曝光；国家旅游局系统漏洞导致系统沦陷；12306网站用户信息泄漏等。这些事件都导致大量的私人或企业的敏感信息泄漏，如果这些信息被不法分子利用，将会造成财产等方面的巨大损失，因此必须采取一定的措施来防止隐私信息的泄漏。但最好的方法是政府加强相应的监管，制定配套的政策，在提高隐私保护技术的同时也应提高个人对隐私保护的意识。隐私保护技术是其中重要的一环，也是如今研究的热点问题。对此，本文采取关联规则中基于划分的技术对原始数据中敏感规则的挖掘，利用随机扰动与重构技术隐藏挖掘出来的敏感规则，之后在Hadoop分布式环境中并行化整个算法，以提高算法的执行效率。

1 基于关联规则混合算法的并行化概述

首先采用Savasere等人所设计的基于划分的算法挖掘事务项目中的敏感规则，并采取相关方法对其冗余规则进行过滤，得到敏感规则集合。随后采用随机扰动与重构技术对敏感规则集合中的数据加入特定的高斯分布数列生成伪列以进行干扰[1，2]，若干扰后敏感规则隐藏则能达到公开度的要求，过程结束；否则对干扰后的数据进行重构处理，再次利用已知分布生成伪列的方法对敏感规则进行处理，并判断处理后敏感规则是否能够达到公开度的要求。最后对整个算法在Hadoop环境中进行并行化处理，提高算法执行效率。

1.1 相关概念

1.1.1 关联规则挖掘

关联规则实际上反映的是一个事件与其他事件之间的依赖或关联。假定项目集为I={i1，i2，…，in}，事务数据库为D={t1，t2，…，tm}，其中每个事务t所包含的项均是项目集I的子集。一个关联规则定义为X=>Y，其中X，Y均是项目集I的子集，并且X，Y无交集。X，Y分别称为规则的左右件。关联规则的强度可以用支持度Support和置信度Confidence衡量。支持度与置信度表示见式（1）、式（2）所示：

Support（X=>Y）=|X∪Y|/|D| （1）

Confidence（X=>Y）=|X∪Y|/|X| （2）

挖掘敏感规则不仅仅依靠支持度、置信度，还有最小支持度阈值、最小置信度阈值。本文引入了提升度lift来过滤无趣和冗余的规则，见式（3）：

lift（X=>Y）= Confidence（X=>Y）/Support（Y） （3）

在支持度与置信度均分别大于最小支持度与置信度的前提下，利用支持度、置信度、提升度关联衡量准则将关联规则分为3类：

（1）不相关规则

如lift（X=>Y）的值等于1，则X，Y相互独立不相关。

（2）冗余规则

若lift（X=>Y）的值小于1，则X的出现对Y是负相关的，属于冗余规则，需要剔除。

（3）敏感规则

若lift（X=>Y）的值大于1，则X的出现对Y是正相关的，属于敏感规则，需要在下一过程进行保护。

1.1.2 阈值设定

为了使挖掘的结果更为精确，使用自适应支持度、置信度阈值与固定相结合的方法[3]。首先设置一个最小支持度、置信度下界b，其中，最小支持度下确界的确定需要结合数据集合的特征，根据实际经验设立。需要考虑的因素有数据集合的大小、特征、历史多期规则的最小支持度等。

首先对数据库进行扫描，对每项出现的次数进行统计，得到Count（oi），计算每个属性出现的百分比P（i）=Count（oi）/|O|；观察规则X=>Y中的项集，如果min（P（i））>b，则最小支持度、置信度阈值等于min（P（i））；若min（P（i））

1.2 Hadoop并行化概述

Hadoop是由Apache基金会于2005年开发的分布式系统基础架构，可运行于大规模集群上的分布式并行编程框架，核心设计主要包括Map_Reduce和HDFS。本文主要利用Map_Reduce框架对算法实现并行化处理。

Map_Reduce框架的核心步骤分为Map和Reduce。当提交一个计算机作业时，首先将计算机任务分成若干个Map任务，然后分配到不同节点执行，每个Map任务处理输入数据的一部分，当Map任务完成后，会生成一些中间文件，这些文件将作为Reduce任务的输入数据，经Reduce处理后输出最终结果。Map_Reduce任务处理流程如图1所示。

2 算法设计

2.1 算法设计思想

在敏感规则挖掘中利用提升度、支持度与置信度作为衡量标准来寻找敏感规则和过滤冗余规则；在挖掘出敏感规则后利用符合特定高斯分布的伪列对敏感规则进行扰动，来降低敏感规则的置信度与支持度，从而降低其敏感规则间的关联性；根据扰动得出新集合中敏感规则的支持度、置信度来判断是否执行重构过程，若支持度与置信度大于阈值，则执行重构，否则输出扰动后的集合，视为敏感规则得到隐藏。

2.2 算法设计方法

输入为经过数据清洗及预处理的事务集DB。根据自适应支持度、置信度阈值与固定相结合的方法将事务集的最小支持度阈值、最小置信度阈值分别设置为minSup、minConf。

输出为达到公开度的事务集D2。

（1）为事务集DB创建一个数据库集D，按逻辑将该数据库集D划分为n个不重叠的分区。设分区中有一个分区为A，其中的事务数为m，此时A分区中的最小支持度阈值为minSup*m。

（2）扫描数据库，找出每个分区大于该分区最小支持阈值的项集，即为该分区的频繁项集。

（3）组合各分区的局部频繁项集形成候选项集，并再次根据自适应支持度、置信度阈值与固定相结合的方法对最小支持度阈值、最小置信度阈值分别设置为Smin、Cmin；然后计算候选项集中的支持度、置信度与提升度lift。

（4）根据计算出来的支持度、置信度与支持度阈值置信度阈值进行比较，结合提升度lift的值与1比较的结果来寻找敏感规则和过滤无趣规则。设最终找出的敏感规则集合为D1。

（5）假设敏感规则集合D1服从未知分布X（x1，x2，…，xn）；利用符合均值为0且标准方差为σ的高斯分布生成伪列Y（y1，y2，…，yn），并向伪列Y中注入相关的干扰信息。

（6）利用伪列Y对敏感规则集合D1进行扰动，得到新的敏感规则集合D2（x1+y1，x2+y2，…，xn+yn）。计算集合D2中原敏感规则的支持度与置信度并与（4）中的最小支持度阈值（Smin）、最小置信度阈值（Cmin）相比较。

（7）利用已知分布伪列Y与D2对敏感规则集合D2（x1+y1，x2+y2，…，xn+yn）用贝叶斯公式计算原分布X的后验累计分布函数，再次对X求平均得到X的累计分布函数，接着对其求导，依次类推，当求导后的前次与后次的差值小于预设阈值时，即认为得到敏感规则D1中的原始分布X。

（8）输出最终关联规则隐藏好的集合D2。算法开始运行时，会按步骤依次执行，当（6）中支持度与置信度大于阈值时，则会执行（7），即对原始分布进行重构，然后重新执行（5）生成新的伪列，并再次运行到（6）时，且当其中的支持度、执行度小于阈值时，可直接执行（8）。

3 结 语

本文提出了一种关联规则混合算法对隐私保护问题进行了阐述，通过并行化提高了算法的时间复杂度。随着时代的发展，各种隐私保护的方法推陈出新，相关政策出台，人们隐私保护的意识逐步提高，隐私泄漏问题会不断减少，但这并不意味着人们可以减轻对隐私保护的重视程度，隐私保护的研究也需要不断提高，最大限度地减少隐私泄漏带来的损失。

参考文献

[1]汤琳，何丰.隐私保护的数据挖掘方法的研究[J].计算机技术与发展，2011，21（4）：156-159.

[2]周水庚，李丰，陶宇飞，等.面向数据库应用的隐私保护研究综述[J].计算机学报，2009，32（5）：847-861.

[3]王玮.基于概念格的关联规则挖掘及变化模式研究[D].济南：山东大学，2012.

[4] Jiawei Han.数据挖掘概念与技术[M].北京：机械工业出版社，2001.

[5]徐龙琴，刘双印.基于影响度的隐私保护关联规则挖掘算法[J].计算机工程，2011，37（11）：59-61.

[6]马进，李锋，李建华.分布式数据挖掘中基于扰乱的隐私保护方法[J].浙江大学学报，2010，44（2）：276-282.

[7]鲍钰，黄国兴.基于Web日志的隐私保护关联规则挖掘方法[J].计算机科学，2009，36（8）：220-223.