一种改进的隐私保护关联规则挖掘算法.doc

《一种改进的隐私保护关联规则挖掘算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一种改进的隐私保护关联规则挖掘算法　　摘要：部分隐藏的随机化回答方法是基于关联规则数据挖掘的隐私保护算法，针对该算法在重构频繁项集支持度上的指数级时间复杂度导致算法执行效率下降的不足，采用分治策略和集合运算方法对该算法进行改进，消除重构数据的指数级运算。改进算法降低了算法的时间复杂度并有效提高了执行效率。仿真实验与分析表明了改进算法的有效性。　　关键词：关联规则；隐私保护；分治策略；集合运算　　中图分类号：TP3ll　　文献标志码：A　　文章编号：1005-26150l-0119-06　　近年来，随着信息技术的高速发展，针对海量数据的管理与分析，数据挖

2、掘技术的应用发挥了非常积极的作用。与此同时.隐私数据的保护问题逐渐呈现.例如医院患者的病历挖掘，可以发现各种疾病之间的关联，但在挖掘过程中也很容易暴露病人的隐私。类似的情况还有很多，所以隐私保护数据挖掘已经成为数据挖掘应用研究的重点。　　隐私保护数据挖掘常用的基本策略为数据干扰和查询限制。数据干扰就是通过对原始数据进行变换、离散化和添加噪声等方法进行干扰，从而保护隐私数据，再根据干扰后的数据进行挖抛，得到所需的模式、模型和规则；查询限制就是通过对原始数据进行隐藏、抽样和划分等方式，避免数据挖掘者获得完整的原始数据，然后数据挖掘者通过概率统汁或者分布式计

3、算的方法得到挖掘的模式和规则。但是，这两种隐私保护策略都存在自身的不足。数据干扰策略中，所有干扰的数据均与真实的原始数据直接相关；而查询限制策略中，数据挖掘者得到的数据都足真实的数据，这些都会降低对隐私数据的保护程度。另外，针对分布数据挖掘中，通常采用安全多方计算的方法，对数据进行隐私保护。目前又有一种通过建立差分隐私保护模型对隐私数据进行保护的方法，这也是目前研究的重要方向之一。　　关联规则数据挖掘是数据挖掘的一个重要研究领域，在其相关的隐私保护取得了一定的研究成果。在数据干扰方面，提出了一种基于随机变换的MASK方法。该方法通过数据干扰和分布重构实

4、现了隐私保护的关联规则挖掘。虽然该方法很好地兼顾了高度的隐私和准确的挖掘结果.但运行的时间效率较低。所以基于MASK算法的改进优化算法相继提出。提出了改进的EMASK算法.该算法的改进非常有效，但是重构原始数据项的支持度是指数级运算，仍然影响执行效率。　　本文主要针对部分隐藏的随机化回答方法在重构项集支持度上指数级时间复杂度不足进行改进，采用分治策略与集合运算的方法.消除重构数据的指数级运算，提高算法的执行效率。T和S均为常数，所以T=O。而RRPH算法求解逆矩阵时的时间复杂度为0.递推的方法在时间复杂度上提高了两个数量级，　　采用分治策略对RRPH算

5、法进行改进，降低了算法的时间复杂度，有效地提高了算法的时间效率。　　2.2基于集合运算的改进　　根据RRPH算法的具体步骤发现，该算法不仅在求解转换矩阵时间效率低下，而且在重构项集真实支持度时对歪曲数据集求各个组合数量的过程也是同样如此。　　RRPH算法在计算项集支持度时，是从干扰后的数据集估算出真实数据集的项集支持度，例如对于2项集.项集11经过概率变换后可能变为00或0l或10或11.所以在计算其支持度时必须考虑以上4种取值情况。同样对于任意的k-项集，需要汁算出2k种不同的取值情况，所以RRPH算法在对干扰矩阵各个组合的计数过程时间开销很大。　　

6、针对以上问题，可以运用集合运算的原理进行相关计算。介绍了针对MASK算法采用集合运算原理进行优化的方法，RRPH算法可以采用类似的方法进行改进。由于RRPH算法是在二维稀疏布尔矩阵的数据集上进行挖掘，根据该数据集的特性.可以发现在2项集{A，B）的汁算中，A.B取值为O或1，只要查询出A，B取值都为l的个数.即11的个数.A和B的取值在1项集挖掘中可以得到，其他的取值组合可以表示为　　3实验与分析　　3.1实验方法　　为了验证改进的算法的有效性，通过实验将改进的算法和改进前的算法进行比较。本文实验的硬件平台为是IntelCore15CPUM4802.6

7、7GHz处理器和4GB内存，操作系统为Windows8.开发软件为MicrosoftVisualStudio2010　　本实验采用的数据集是由IBMAlmaden的人工数据集生成器生成。生成的数据集D的参数为T10，14，Dl00k，Nl00，分别表示数据集中数据的数据甲均长度为10，频繁项集的平均长度为4，数据集中数据总个数为1000000，数据集总项目数为100。　　本文改进算法主要针对RRPH算法的时问复杂度进行优化，所以在对算法进行时问效率分析的棚关实验中，原始数据集以参数为P1，p2，p3的概率进行干扰，最小支持度为3%。　　3.2实验结果分

8、析　　图1是改进后算法与RRPH算法的运行时间对比，原始数据集以参数p1=0.6，p2=0.2