基于分治策略的 MASK 算法的改进.doc

《基于分治策略的 MASK 算法的改进.doc》由会员分享，可在线阅读，更多相关《基于分治策略的 MASK 算法的改进.doc（9页珍藏版）》请在三一办公上搜索。

1、精品论文基于分治策略的 MASK 算法的改进刘山，武振华 中国民航大学计算机学院，天津（300300） E-mail: wuzhenhua4978摘要：如何保护私有信息或敏感知识在挖掘过程中不被泄露，同时能得到较为准确的挖掘结果，目前已经成为数据挖掘研究中的一个很有意义的研究课题。本文在MASK算法的基础 上提出一种改进的保护输入隐私的MASK算法。相对于MASK算法，改进的MASK算法在保 证较好的输入数据隐私度和挖掘结果的准确度的同时，其运行效率也得到了明显提高。 关键词：隐私保护；MASK算法；分治策略；时间效率中图分类号：TP1. 引言随着信息技术,特别是网络技术数据存储技术和高性能处

2、理器技术的飞速发展,海量数据 的收集管理和分析变得越来越方便,知识发现和数据挖掘更是在一些深层次的应用中发挥了 积极的作用.但与此同时,也带来了隐私保护方面的诸多问题.例如,通过对医院病人的病历数 据进行挖掘,可以发现各种疾病之间的关联.所以,如何在数据挖掘过程中解决好隐私保护的 问题,目前已经成为数据挖掘界的一个研究热点1,2,3.Rizvi等提出了一种基于MASK算法的 隐私数据保护4,5,很好的解决了挖掘过程中隐私保持度和数据准确性的问题.可是算法运行 时间效率较差.Agrawal等在此基础上改进了MASK算法,称之为EMASK算法6,7,该算法通过 降低矩阵的维数,从而提高了算法的运行

3、时间效率.本文提出一种基于MASK算法的改进算法, 理论分析和实验结果均表明本文提出的改进的MASK算法运行时间效率较MASK有明显的 提高,同时隐私保持度和准确度和MASK算法相同.2. MASK 算法介绍MASK(Mining Associations with Secrecy Konstraints)算法由印度学者Rizvi提出.假定数据 集为超市购物篮数据,所挖掘的数据集可以看作由0和1组成的二维稀疏布尔矩阵,1表示购买 某件商品,0表示没有购买.为了保护输入数据集的隐私性,MASK算法采用概率歪曲的方法对原始数据集进行扰乱操作.一个0-1数据库元组可以看成一个随机向量 X = X i

4、 , X i =0或者1.- 9 -对 X i 进行歪曲操作得到Yi = X iXOR ri ,其中ri 是 ri 的补, ri 是满足伯努利分布的随机变量,分布律为 p(ri = 1) = p, p(ri = 0) = 1 p .由异或计算的特点可知随机向量 X 经过歪曲操作后,第 i 个分量 X i 保持原值的概率为 p ,取其相反值的概率为1- p ,如下表1所示.表1Xi概率变换过程Tab.1 The probability reconstruction of Xi概率riXiYip0111 p110p0001 p101TMASK算法所挖掘的数据集是真实数据集经过概率变换形成的,所以需

5、要重构项集的真D实支持度.设真实数据集对应的矩阵为 T , T 经过歪曲变换后得到的矩阵为 D ,歪曲概率为1p . T 的第 i 列中1的个数记为 c T,0的个数为 c0, D 中第 i 列中1的个数为 c1,0的个数为 c0 .由前面介绍的概率歪曲过程可知:TTDc1 p + c0 (1 p) = c1DTTDc0 p + c1所以 (1 p) = c0p1 p CT = M 1C D c D c T (1)其中 M = , C D = 1 , CT = 1 ,解此方程组即可由歪曲矩阵 D 估算出1 pp TD c 0 T c 0 真实矩阵1 项集的支持度 c1 .n -项集的真实支持度

6、计算方法跟单项集类似.方法如下: cD cT 2n 1 2n 1 CT = M 1C D ,其中 C D = M , CT = M (2)cD c 1 D 0 DT c1cT 0 ck 定义为 n -项集 k 的个数,其中 n -项集 k 的表示形式为 n 位二进制数,这 n 位二进制数对应的十进制值为 k . c T 的定义与 c D 相同. M 为 n 阶矩阵, M为真实 n 项集 j 概率kki , j 歪曲为 n 项集 i 的概率.解此方程组可得原始真实数据集中 n 项集的支持度 c D1,2对于2 项集, M表示项集10变化为01的概率,即为 p2 .2n 1.例如3. MASK 的

7、改进算法MASK算法的实现基于经典Apriori算法,即先产生频繁1-项集,再产生频繁 k 项集,最后生成强关联规则.与经典Apriori算法唯一的不同点是项集的计数问题.Apriori算法挖掘的对象是真实数据库,因此只需计算包括候选项集里所有项的元组的个数.例如对于一个表示为11的2 项集来说,只需要计算包含该2 项集里的所有项的元组的个数.改进的算法需要从歪曲后 的数据集估算原始真实数据集中项集的支持度,例如对于2 项集,原始项集11歪曲后会变为00、01、10、11中的一种.由真实项集支持度的计算方法可知只有考虑这四种变化情况才可以计算出真实2 项集的支持度.因此,通过歪曲数据集计算真实

8、数据库中 n 项集的支持度,需要考虑原始真实 n 项集经过歪曲变化后可能产生的 2n 种情况.MASK在估算 k -项集的真实支持度时需要计算公式(2),该公式的右边是阶数为 2n 的方阵 M 求逆后与列向量的乘积.随着候选项集 n 的增大方阵 M 的阶数以 2n 的速度在增长.在MASK算法中求解 M 1 的时间 复杂性为 O(n3 ) , 所以求 M 1 变得越来越耗时, 从而使得MASK 的时间效率下降很多. 在 XMASK算法中我们发现方阵 M 的特点进而将求解 M 1 转化为矩阵相乘的形式,经过计算发 现我们求 M 1 的时间复杂性为 O(n2 ) ,跟MASK求 M 1 的方法相比

9、降低了一个数量级,所以时间效率得到了明显提升.3.1 改进的 MASK 算法项集真实支持度的估计本文提出的XMASK算法估算项集真实支持度的方法跟MASK算法类似,但是时间效率 确提高了两个数量级.在前边已经介绍过,MASK估算 n -项集的真实支持度需要计算公式(1)和公式(2),仔细观察在此公式里的 M 1 阶数为 2n ,MASK算法处理此逆矩阵采用直接求逆的方法,即 M 1 = 1MM * ,其中 M * 为 M 的伴随矩阵, M 为 M 的行列式,为了得到 M * 需要计算 2n 2n 个 2n 1 阶行列式的值,因此,随着候选项集 n 的增大,这个计算所耗费的时间越来 越大,从而使

10、使MASK的算法的效率急剧下降.本文用下面的方法对 M 1 的计算进行优化.由公式(1)可知1-项集对应的 M 矩阵为2阶的,表示形式为: m00M =m01 = p1 p 2 m10m11 1 pp 由矩阵 M 的定义可知2-项集对应的 M 矩阵为4阶的,表示为:22 a0000a0001a0010a0011 pp(1 p)p(1 p)(1 p) 22M = a0100a0101a0110a0111 = p(1 p)p(1 p)p(1 p) 422 a1000a1001a1010a1011 p(1 p)(1 p)pp(1 p) 22 a1100a1101a1110a1111 (1 p)p(1

11、 p)p(1 p)p对 M 4 进行分块操作,结果如下:p2p(1 p)p(1 p)(1 p)2 M = p(1 p)p2(1 p)2p(1 p) M=M 01 422p(1 p)(1 p)pp(1 p)00 M10M11 (1 p)2p(1 p)p(1 p)p2其中,p2p(1 p) p1 p M= M= = p = pM0011 p(1 p)p21 pp 2 p(1 p)(1 p)2 p1 p M10 = M 01 = (1 p)2p(1 p) = (1 p) 1 pp = (1 p)M 2所以M = pM 2(1 p)M 2 4 (1 p)MpM223-项集对应的 M 矩阵为 8 阶的,

12、满足同样的规律,即M = pM 4(1 p)M 4 8 (1 p)MpM44依此类推,概率变换矩阵 M 具有如下的递推关系:M = pM k /2 (1 p)M k /2 ,其中 k = 2n , n = 1,2, .(3)k (1 p)M k /2 pM k / 2因此,只要已知 M 2 ,就可以递推地计算出 M k .1由于 M k 具有递推关系,我们尝试找出 M k式如下:的递推关系,首先把 M k 转化为矩阵相乘的形1M = pM k /2 (1 p)M k / 2 = pEk / 2(1 p)Ek /2 M k /2k 因此: (1 p)M k /2 pM k / 2 (1 p)Ek

13、 /2 1pEk /2 1M k /2 1M 1 = pEk /2 (1 p)Ek / 2 M k /2 M k / 2= pEk /2 (1 p)Ek /2 k (1 p)Ek / 2pEk /2 M k /2 M k /2 (1 p)Ek /2 pEk /2由分块对角矩阵的性质可知: M M 1 k /2 = k /2 MM 1其中,k /2 k /2 pE( p 1) EpE(1 p)E1 2 p 1k /2 2 p 1k /2 1pE( p 1)Ek /2 k / 2= =k /2 k / 2 (1 p)Ek /2 pEk / 2 p 1 EpE2 p 1 ( p 1)Ek /2 pE

14、k / 2 2 p 1k /2 2 p 1k /2 M所以1 M 1 pE( p 1)EM 1 =k /2 k /2 1 k / 2k2 p 1 11k /2 (4)( p 1)Ek /2pEk /2上式即为 M k 的逆矩阵 M k的地推关系.我们知道p1 p M 1 = p1 p =1pp 1M 2 = 1 pp ,21 pp 2 p 1 p 1p 当概率变换参数 p 为确定时, M 1 唯一确定.因此,我们可以利用 M 1 依次递推求得各阶22M.1k递推公式(4)的时间复杂度计算式表表示为T（k)= T ( k ) + S (k ) ,其中, k = 2n , n = 1,2,3, .

15、（5）2T（k ) = T (k / 2) + S (k ) = T (k / 4) + S (k / 2) + S (k )= . = T (2) + S (4) + LS (k / 2) + S (k )= T (2) + 2S (2) + 22 S (2) + L + 2n 1 (k / 2)= T (2) + S (2)(2 + 22 + L 2n 1 )2(1 2n1 )= T (2) + S (2) *1 2= T (2) + S (2)(2n 2)= T (2) + S (2)(k - 2)p1 p T (2) 为生成 M 2 所需要的时间, S (2) 为生成矩阵 1 pp 所

16、需要的时间,均为常数.所以T (k ) = O(k )(6)即使用递推关系求逆的时间复杂度为线性的,MASK 算法求逆的时间复杂度为 O(n3 ) ,我们的方法在时间性能上提高了 2 个数量级.3.2 完整的改进 MASK 挖掘算法前边已经提到 MASK 算法是基于经典的 Apriori 算法,这里改进的 MASK 算法也是基于 Apriori 算法,改进的 MASK 算法和 MASK 算法的相同点是在重构项集的真实支持度时需要 跟踪其所有子集.例如,对于 MASK 和改进的 MASK 算法,为了计算 2-项集的支持度,需要计算00、01、10、11 的计数,而 Apriori 只需要计算该

17、2-项集的计数.所以,在算法实现过程中需要 保留其每个子集的计数.支持度的重构在每一层的最后计算,下面是改进的 MASK 算法的实 现过程.算法:改进的MASK算法输入:经过概率歪曲的数据库 D ，歪曲参数 p ，最小支持度 min_ sup输出:经过重构的频繁项集1C1 =find _ candidate _ 1 itemsets(D);2Re construction(C1 , p, min_ sup)；/估算1-项集的真实支持度3L1 = c C1 | c.supr min_ sup); / supr 表示1-项集的估算支持度4for (k = 2; Lk 1 ; k + +)56Ck

18、= apriori _ gen(Lk 1 );7Re construction(Ck , p, q, min_ sup);8Lk = c Ck | c.supr min_ sup);910returnL = k Lk ;1procedureRe construction(Ck , p, min_ sup)23if (k = 1)4M 1=1pp 1;22 2 p 1 p 1p 65else1 M 1 pE( p 1)EM1k k =2 p 1k /2 M 1k /2 ( p 1)EpEk / 27for each itemset ci Ckk /2 k /2 k /2i r8c .s u pk

19、 1k k k 1- j= M -1 0 j * c. s u p ;j = 091procedure Apriori _ gen(Lk -1 : frequent (k -1) - itemsets)2for each itemset l1 Lk 13for each itemset l2 Lk 14if (l11 = l21) (l12 = l22) . (l1k 2 = l2k 2) (l1k 1 l2 ;6if has _ inf requent _ subset (c, Lk -1 ) then7delete c;8else add c to Ck ;910return Ck ;4.

20、 实验及结果分析评价 MASK 算法的性能有三个指标,即隐私保护度、准确度和运行时间效率.本文提出的 改进的 MASK 算法对 MASK 算法里的重要步骤估算 n -项集的真实支持度进行改进,显著提 高了估算 n -项集的真实支持度的时间效率,算法的其余部分与 MASK 算法完全一致,所以改 进的 MASK 算法与 MASK 算法具有相同的隐私保护度和准确度.本文分别实现了 MASK 算 法和改进的 MASK 算法,然后用实验数据验证改进的 MASK 算法的有效性和相对 MASK 算 法的高效性.4.1 实验环境与实验数据集本实验的硬件环境为联想笔记本电脑,配置为Pentium IV 1.74

21、GHz处理器和768M内存,操 作系统为Windows XP,所采用的开发工具为Visual C+ 6.0.实验采用的事务集由IBM Almaden generator自动生成.生成合成数据集的参数设置为T10I4D100KN0.02,分别表示所生成的事务集中事务的平均长度为10,频繁项集的平均长度为4,事务集总共有100000个事务,属性的总个数为20.4.2 实验结果首先比较MASK 算法和本文提出的改进的MASK 算法在计算概率变换矩阵 M 的逆M 1 的时间开销.概率变换矩阵 M 只与概率歪曲参数 p 有关,表2是当 p = 0.8 时两种算法计算 M 1 的时间对比.表2 p = 0

22、.8 时MASK和改进的MASK求 M 1 的时间对比M的阶数2223242526272829210MASK时间开销(秒)000.0160.3230.91410692-改进的MASK时间开销（秒）00.1400.2030.2660.3900.7032.67219.062305.125由表2可知,当概率变换矩阵 M 的阶数较小时,MASK算法求 M 1 的时间开销小于本文提出的算法,当 M 的阶数增大时,改进的MASK算法开始表现出非常好的优势.当 M 的阶数为 26 时,MASK算法的求逆时间不到本文提出的算法的3倍,当 M 的阶数为 27 时,MASK算法 的求逆时间急剧退化,是改进的MAS

23、K算法的15000多倍,当阶数继续增大时,MASK算法求逆已经失效,此时,本文提出的算法仍然表现出很好的效果,例如 M 的阶数为 210 时计算 M 1 只需要300多秒.这样的实验结果跟我们在前边对改进后的MASK算法时间复杂度的理论分析完全一致.5. 结束语本文首先介绍了印度学者 Rizvi 提出的 MASK 算法并分析了其时间效率低下的缺点，然 后提出了一种改进的 MASK 算法，该算法与 MASK 算法具有相同的隐私保护度和准确度， 但时间效率相对 MASK 算法得到了显著提高.理论分析和实验结果均表明改进后的 MASK 算 法具有非常好的时间效率.参考文献1 Verykios VS,

24、 Bertino E, Fovino IN, Provenza LP, Saygin Y, Theodoridis Y. State-of-the-Art in privacy preserving data mining.SIGMOD Record, 2004,33(1):5057.2 Han J, Kamber M. Data Mining: Concepts and Techniques. Beijing: China Machine Press, 2001 (in Chinese). 3 陈晓明,李军怀,彭军,刘海玲等.隐私保护数据挖掘算法综述J.计算机科学,2007,34(6):18

25、3-186.4 Rizvi S, Haritsa J R. Maintaining Data Privacy in Association Rule Mining C. Proc. of 28th Int. Conf. onVery Large Databases, 2002.5 D. Agrawal and C. Aggarwal, On the Design and Quanti_cation of Privacy Preserving Data MiningAl-gorithms, Proc. of 20th ACM Symp. on Principles of Database Sys

26、tems (PODS), May 2001.6 Agrawal R, Srikant R. Privacy-preserving Data Mining C. Proc. Of the ACM SIGMOD Conference onManagement of Data. ACM Press,2000-05: 439-450.7 Agrawal S, Krishnan V, Haritsa JR. On addressing efficiency concerns in privacy-preserving mining. In: Lee YJ, Li JZ, Whang KY,Lee D,

27、eds. Proc. of the 9th Intl Conf. on Database Systems for Advanced Applications. LNCS2973, Jeju Island: Springer-Verlag,2004. 113124.A improved MASK algorithm by using divide and conquer strategyLiu shan, Wu zhenhuaDepartment of Computer Science and Technology, Civil Aviation University of China, Tia

28、njin(300300)AbstractThere has been a meaningful research problem that how to protect privacy or sensitive informationfrom leaking during data mining process , meanwhile obtain accurate result .This paper presents a improved MASK algorithm. The improved MASK algorithm presented in this paper can simu

29、ltaneously meet satisfactory privacy and accuracy, while the runtime efficiency is advanced obviously compared with MASK algorithm.Keywords：Privacy-Preserve; MASK algorithm; divide and conquer strategy; runtime efficiency作者简介：刘山（1955-），男，河北乐亭人，教授，本科，主要研究方向为信息处理、算法分析与设计。 武振华（1984-），男，安徽合肥人，硕士生，主要研究方向信息处理、数据挖掘。