论文研究-增量式隐私保护数据挖掘研究.pdf

所需积分/C币:6 2019-07-22 20:01:25 1022KB .PDF
收藏 收藏
举报

描述了隐私保护数据挖掘技术研究进展。针对隐私保护关联规则挖掘算法EMASK计算效率较低,同时不适用于动态变化数据库等的问题,提出基于粒度计算的增量式隐私保护数据挖掘算法BIEMASK。该算法用粒度计算的思想对EMASK算法进行改进,利用增量式更新算法FUP解决增量式事务数据库频繁项集计算问题。在实现隐私保护的同时,减少了I/O操作的次数,降低空间开销,由此提高计算效率。结果证明,无论是固定增量集数据库还是可变增量集数据库处理中,BIEMASK相对于EMASK而言,效率时间都有较大幅度的提高。
2158· 计算机应用研究 第35卷 items support 对应位被表示成“1”,否则即为“0”。由于“1”或“O”是固定且 T ID items 0115 11 长度简短的数据串表示,所以可以利用位操作(and或or)的方 45得到 法来改进计数方式,提高了算法的效率 13 相对于其他粒度计算过程,这种计算方法不需要构造分辨 05135 15134 矩阵,既可以保证准确性不降低,同时又减少了O操作的次 0645 选出支持度=1004的项选出支持度≥5x04的项 数,降低空间开销,对效率有了较大程度的提高。 094 3.3 BIEMASK算法简介 本文提出的 BIEMASK是在 EMASK的基础之上,对 繁 EMASK进行改进,融入增量式数据挖掘的概念,是一种基于粒 旧数据库DB1项集 度计算的增量式的隐私保护式的数据频繁模式挖掘的算法。 在 BIEMASK算法中,本文采用了 Cheung等人1在增量 items dh support DR results 动作 式数据挖拆中所提到的性质和原则,设 support=s% 支持度相加(重新判断 (IDR+Idh 1), support =s% x I BI, support, =s%xIdbI, l 访问DB,待到支持度,然后判断 剪除 不满足 support= support+ support,并且判断属性集X是否频繁的模 支持度相加(重新判断) 式也与表1一致。 BIEMASK与增量式更新算法FLP相比较,它 5 6 支持度相加(一定满足) 方面多了一个隐私保护的过程,另一个方面它使用了粒度计 算技术,也即其计数的方式跟FUP及 EMASK都不一样。 增量后的频緊1-隽为1245 3.4 BIEMASK基本流程结构 图2增量过程实例示意图(1项 BIEMASK由于要使用到 Bitmap技术,所以与 EMASK算法 对丁两项以上的支持度计算与图2所示的原理类似,只是处理的区别就是需要将原始数据库文件转换成行列形式的Bt 要根据产生的频繁项集L1生成侯选项集C,通过访问d来mp规范化文作,并存储在内存或磁盘卜。为了实现隐私保护, 对其进行裁减以减少访问数据库DB的项集的个数,总而达到利用 EMASK算法处理方式,事先将数据库中数据进行扯曲,然 提高效率的目的。 后冉转换成 Bitmap文件。 BIEMASK算法大致过程如下 a)为了隐私保护,先把教据厍文件d进行扭曲,并转换成 3基于粒度计算的增量式频繁模式挖摒 Bitmap 文件 b)选出长度为1的候选项集C1。计算C1屮每个项集X 3.1增量式隐私保护数据挖掘 在db的支持度(通过 EMASK中提到的方法用以计算X的支 増量式隐私保护数据挖掘由于受到数据库中的项集规模持度X. support)。 庞大,增量式的更新给数据集遍历带来处理效率低下的问题, a)如果X在中满足最少支持度,并且在DB中也满足 所以提高计算效能直是该领域的研究热点。 最少支持度,那X为DB+b的频繁1-项集。如果在D中不满 itajai等人提出了基于增量式数据流的隐私保扩算足最少支持度,那么将X放入Cemp中,等待访问数据库 法,该算法无须对数据项集重新识别,而在于随机预测。采用 (b)如果X在如b中不满足最少支持度,接下来有两种可 的技术就是随机投影密钥矩阵,由于使用了矩阵的位置,而不能性:其一在DB中也不满足最少支持度,那X不为新数据库 是随札数木身,所以对数据的隐私保护以及计算性能都有很好DB+b的频繁1-项集;其二如果在DB中满足最少攴持度的 的体验。该方法采用了加密以及构建矩阵的过程,这两项工作要求,那么计算X. support+X. support,看它是否满是 suppor 产生的消耗将会降低整体计算效率。 tb的安求,是则频繁,否则不频繁。 Wang等人6提出的增量更新算法PM,在维护频繁 (c)遍历数据库数据DB,计算保存在 CLamp中的每个X 项集的过程中,当新的项集被添加到事务数据库中,利用先前的支持度X. support r,并计算X. support+X. support是否满足 的挖掘结果,可以减少遍历范围,达到提升效率的目的。该算 support;n的要求,满足则频繁,不满足则不频繁,将计算后得到 法可以解决增量数据带来的遍历消耗,但是事务数据库如果呈的频繁项集放入集合L屮。 现实时动态变化,算法反而增加了遍历的次数 c)按照上述内容,根据L41可以生成候选项集C。 Rajalakshmi等人1提出了一种频繁离散技术,来取代事务 d)计算C中的任意项x在d中的支持度。 数据库中的项集支持度。该技术提高了数据存储的性能,也能 )重复过程b)~d),直到C为空。 起到很好的隐私保护作用,但对频繁模式的数据挖掘,由丁忽略 f)最后得到的频繁集L就是长度为1,2,3,…,n的并且满 了对支持度的考虑,所以数据挖掘的有效性很难得到提升。 足最少支持度的频繁项集。 木文将从粒度计算角度出发,用位操仵的方法来实现支持 与 BEMASK中的过程相比,此过程需要访问DB中产生的 度的计算,既实现了隐私保护,同时又对信息挖掘的性能以及频繁项集文件,同时也要涉及到两个文件的访问问题。山于用 计算效率都能得到有效提高。 到两个文件,所以需要对两个文件都进行数据库文件到 Bitmap 3.2粒度计算 文件的转换。如果能在上次的运算之中保留其Bmap文件 粒度计算是近十余年来涌现出来的一种信息处理的计算范这样就可以减少一些转换的时间 式,它适合于模糊、不确定性、不精确、部分真实问题的求解1 为了更明白地闸明这个问题,文绘制了结构图3 粗糙集理沦认为,知识具有不确定性,而度量知识系统不确定性3.5 BIEMASK对原始数据库结果的特殊要求 的重妟方式就是知识粒度。因此,粒度计算作为一种现代科学 对原始数据库DB挖掘得到的频繁项集结果在增量式数 技术,被广泛应用于知识发现过程中,其核心思想岀现在很多的据挖掘中需要用到,但是由于在隐私保护数据挖掘中涉及到从 领域,如模糊集、粗糙集、区间分析、机器芓习以及数据挖掘等。扭曲后的攴持度近似求解原数据库支持度的问题。在此,夲文 常规的做法是从矩阵的视角提出知识粒度、分辨度和属性但由利用了 EMASK中所做优化,即利用AB=B-AB,AB=A-AB, 于空间与时间的消耗,也引起了不少的争议9 AB=1-A-B+AB的性质,因为A,B的支持度在求AB之前已 本文算法用Bmap来表示粒度,使用了数据的垂直 Bitmap经得到了,所以AB,AB,AB的支持度只需要计算就可以得到 形式。因此可以将关系数据表中的母个属性表示成一个但这需婁得到A,B在扭曲后数据库的支持度。对于DR中频 Bimp,而每条记录则拥有唯一的位移偏置,加入属性存在则繁项集的支持度已经在结果文件中得刭,但是如果要得到其在 第7期 程舒通,等:増量式隐私保护数据挖掘研究 2159 扭曲后数据库中的攴持度,按照以前 EMASK的算法,必须重 a) BIEMASK算法的效率在固定增量集数据库中,相对于 新访问数据库文件DB,这将又大大地降低效率。为了提高效 EMASK来说有很大幅度的提高。最小文持度越小时,BIE 率,本文对 EMASK算法进行了收动,在生成频繁项集的同时,MASK消耗的时间比 EMASK消耗的时间差距越大。主要原因 也记录了其在扭曲后数据中的支持度。利用这样的方法,减少是最小支持度越小,满足最小支持度条件的数据集就越多 ∫文件的访问次数,计算效率也会有大幅度的提高。 EMASK扫描数据库的花费乜增加,但是 BIEMASK算法由于把 distortion 数据经过了Bm岬处理,扫描数据库的时间消耗并不是很多。 new added distorted ds databasc(db) 这也间接证明, BIEMASK算法更适用于大型数据库的处理。 create Bitmap 20O gen C from LaI +EMASK HEMASK/BIEMASKI file(lb 10000 BIEMASK ad Bitmap C= XLL old datal get the support of 60004 (DB) distorted do for the 4000 cIstortion 2000 ort of ds for the distorted DB 0.2040.60.81.01.21.41.6 0.20.40.60.81.01.21.41.6 最小支持度 最小支持度 supportiX)≥db 图4 BIEMASK与 EMASK 图5 BIEMASK与 EMASK 在不同支持度下的 在不同支持度下的 时间消耗比较 执行时间对北 Bitmap 合 b)随着最小支持度的增大, BIEMASK相对于 EMASK的 read Bitmap 效率增幅不是特别的明显。十要是满足最小攴持度的数据集 ret the 否 变得越来越少,当数据集减少到一定程度时, EMASK算法和 distorted DB for the support(X) iTemset in cle BIEMASK算法效率就相当了。 NBI+Idly 表2 BIEMASK与 EMASK在不同支持度下运行的时间记录 增量扭扫参数杜m,、mm et the support of DB for the itemset in B+lebIy? pul X k 0. 11644 图3 BIEMASK总体结构 G254DC0KNK100.50.970.75 329 108 3.6 BIEMASK与 EMASK的算法时间复杂度比较 EMASK算法是对MAsK算法的一种改进,时间效率和空 间效率都得到了有效的提升。将真实的矩阵进行扭曲,由于使 第二部分实验采用了变化增量集数据库D254D10 OKNIK 用了概率为P和q的扰动,所以与MASK算法相比,其概率矩定支持度0.5%,增量事务条数分别为5k、5k、25k、75k、150k 阵可表示为 30Uk。表3为两种方法对相同的数据库,在不同增量集情况下 的运行时间对比。图6为两种算法处理不同的增量数据库,相 (1-P +k-i- 同支持度下的耗吋比较。图7为 BIEMASK对于 EMASK在不同 矩阵的阶数从MASK算法的2″下降到n-1求解矩阵的的增量集情况下的效率变化趋势。 时间复杂度由0(8)简化到O(n3) 表3 BIEMASK与 EMASK在不同增量集情况下的运行的时间记录 BⅠ EMASK算汏在扫描数摒库时,概率矩阵的阶数为2″,假 数据集增量扭扫参数支持度/% EMASK BIEMASK 设矩阵的维数为k,由于使用了Bmap粒度计算方式,一条属 p q 性对应着一个imap,形成了类似一维数组的结构,计算矩阵 的复杂度仅为O(k),由北可以提高计算效率。 D2514DICOKNIK 750.50.97 233 3.7 BIEMASK算法性能测试实验 3969 98 本文对算法的性能测试使用 Cygwin在CPU为 Intel(4 1.7GIl,内存为1G,操作系统为 Windows xp的电脑上运行 了 EMASK、 BIEMASK等程序。在C++程序与g2.95.3编 6000 ■EMAS CBIEMASK 50X0 晋 EMASK/BIEMASK 译器开发环境下实现了 BIEMASK算法。实验数据来源于IBM 叵40 数据生成器( IBM Almaden generator)生成。 在3000 为了验证 EMASK和 BIEMASK在同一增量集不同支持度 200E 1C0 及不同增量集情况下的效率对比情况,本文采用了两种不同增 量式数据库——固定增量集数据库G2514DI00KNIK和变化增 5152575150300 5152575150300 增量数据车人小 增量八 量集数据库D254D100KN1K,并将实验分成两部分: 图6 BIEMASK与 EMASK 图7 BIEMASK与 EMASK a)基丁固定增量集数据库G2514D10OKNK的不同支持 在不同增量集情况下的 在不同的增量集情况下的 度情况下 BIEMASK与 EMASK算法性能比较; 时间消耗比较 执行时间对比 b)基于变化增量集数据库D2514D100KN1K的同一支持 通过这一阶段的实验,可以得出如下的结论 度下 BIEMASK与 EMASK算法性能对比。 a)对于不同的增量,BIEⅥASK算法的效率相对于 EMASK 第一部分实验采用固定增量集数据库C25μ4υI0KNκ数来说有很大幅度的提高。并且随着增量集的増加,效果越来越 据集,增量事务条数分别为10k,表2为在不同攴持度明显。这主要是 EMASK所构建的概率矩阼扫描数据库所花 (0.25%、0.5%、0.75%、1.0%、1.25%、1.5%)情况下, EMASK费的时间增多,而使用 Bitmap的 BIEMASK算法在数据库项集 和 BIEMASK两种方法的时间对比。图4为与之配套的两种算增加时,也只是增加 Bitmap数量,处理 Bitmap数据所花费时间 法在不同支持度下的耗时对比图。图5为两种算法在不同支明显比处理矩阵要少得多。 持度下的执行时间对比图。 b)随着增量的加大, BIEMASK时间相对于 EMASK的 通过这一阶段的实验,可以得出如下的结论 时间比有所下降,但是时间比会趋向7左右(下转第2171页) 第7期 叶志斌,等:一种面向二进制的控刽流图混合恢复方法 2171 表1各方法比较实验结果数据 并节点分析及边、节点的可达性分析,简化了控制流图,提高了 方法 控制流图的精确性。 谢试用例文小 CFGCombineCFGStatie 由于二进制文件分析缺乏对程序数据结构的了解,在动态 node cdge time/s nodc cdge timc/s node cdge timc/3 分析控制流图坼节缺乏处理程序大循坏冋题的有效方法,导致 CADET00001781432160.725161234042118727714.565 7.348680.416561800.39253743.619 控制流图生成的效率还有一定局限性,难以面向大型程序的控 ais3 crackle8.65377048668910.18656783.475 制流图生成。 wyvern 851557256210.935200631893.285747517037370 参考文献 山于 DAPRA CGC给出的二进制挑战文作大多不包含源1朱殊,基于函致控制流图比对算法的二进制可执行程序相似性分 代码,所以无法知晓所测文件的代码行数,但从测试结果的[2]王明华,应凌云,冯登国,甚于异常控制流识别的渴洞利用攻击检 nxde和edge信息中可以推断出文件的大小,测试结果包括生 测方法[J].通信学报,2014,35(9):20-31 成的控制流图的节点数、边数以及进行控制流图分析所用的时13」AamS, Traore i, Sogukpinar I. Annotated control flow graph for meta 间。分析结果可得出如下结论:结合动静态分析的控制流图恢 morphic malware detection J]. Computer Journal, 2015, 58 复方法 CFGCombine与静态恢复方法 CFGStatic及动态恢复方 (10):268-2621 [4 Xu Liang, Sun Fangyi, Su Zhendong. Constructing precise control flow 法 CFGDynamic相比, CFGCombine的统计分析效率是 CFGSt graphs from binaries[R].[S.L.: University of California, 2009 ic0.55,是 CFGDynamic的12倍,并且从最后一个测试用例[51 Cadar c, Ganesh v, Pawlowski p m,eta.EXE: automatically genera 来看,当程序较为复杂或程序大小达到一定规模时, CFGCom ting inputs of death[ C]//Proe of ACM Conference on Computer and bine和 CFGStatic仍能以较快速度恢复控制流图,而 CFGDy Communications Security. New York: ACM Press, 2006: 243-257 namIc已经无法满足程序分析的需要;从精确度来看,C上GCom- L 6 Cadar C, Dunbar D, Engler D KLEE: unassisted and automatic gene ation of high-coverage tests for complex systems programs[ C//Proc hine所得的控制流图对 CFGSt atic恢复的控制流图进行」后续 of USENIX Symposium on Operating Systems Design and Implementa 分析处理,在合并了重叠节点和剔除了循环边和不可达边及节 tion. New york. ACM Press 2008. 209-224 点的情况下所得的控制流图更为精确,能为后续的分析提供 [7idAProhomepageeb/ol.(2012-02-27).htlp://www.hex-rays. 个更为精简的控制流图 coin/idapre [8』崔晨.回件代码控制流囡恢复技术研究[D].郑州:信息工程大 4结束语 学,2012 [9]陈火旺.程序设计语言编译原理[M].3版.北京:国防工业出版 社,2009:280-30 进制文件的安全性分析受到了越来越多的关注,面向二10 J ShoshitaishviliY, Wang ruoyu, Salls c,etl.SOK:( state of) the art of 进制文件的控制流图分析技术已经受到了相当程度的重视。 war: offensive techniques in binary analysis C//Proc of IEEE Sympo 由于二进制文件的分析本身固有的复杂性,导致面向二进制文 sium on Security and Privacy. Pisc J: IEEE Prese, 2016 件的控制流分析的精确度和效率提高难度较大。本文提出了 L 11 Cifuentes C, Van Emmerik M. Recovery of jump table case statements 在混合技术生成控制流图的方法,在静态生成控制流图的基础 from binary code[ J]. Science of Computer Programming, 2001 上,结合动态强制执行方法求解静态分析中无法解决的间接分[12]JmJ,Mry, Navas JA,a. Path-sensitive back ward slic 支跳转问题,在此基础上结合反向切片技术和局部符号执行技 C|//Proc of International Static Analysis Symposium. Berlin: Sprin 术,提高对问接跳转日的地址的求解,通过对控制流中的可合 geI,2012:231-247 (上接第2159页)(在最少支持度为05%的情况下 BEMASK相对 [J].计算初应用,2017,37(2):316-321 于EⅥA5K的时间比)。即增量式算法的有效性得到充分肯定。 [8]李洪成,吴平,陈燕. Mapreduce框架下支持差分隐私保护的 k- means聚关方法[J].通信学报,2016,37(2):124-130 4结束语 L 9 Doshi N A novel approach for cryptography technique on perturbed dala for distributed environment J. International Journal on Cryp 本文在高效隐私保护关联规则挖据算法上MASK的基础1 graphy and Information Security,2012.2(31:1010 云,石聪聪,余勇,等.保护隐私的分布式朴素贝叶斯挖掘[J] 上,为了提高处理当数据库变化(增加)时頫繁模式挖掘的效 应月科学学报,2017,35(1):1-10 率,利用Bm技术实现」增量式隐私保护数据挖掘B.「11景征骏,将国平,古春生一类基于安全多方计算的数据挖掘隐私保 MASK,主要利用二进制操作按位ad或or的方法来改进计数[12] Rizvi s i. Harita R. Maintaining data privacy in association rule 方式,解决了 EMASK运行效率低下的问题。通过实验可以得 mining[ C//Proc of the 28 th International Conference on Very Large 知,无论是可变最小支持度的定增量集数据库,还是固定最 DaLa bases. New york. acm Press 2002.682-G93 小支持度的变化增量集数据库处理屮, BIEMASK都较大程度 13 Agrawal S, Krishnan V, Haritsa J R. On addressing efficiency concerns in privacy-preserving mining[ C]//Proc of the 9th International Con 地湜高了挖掘频繁模式的效率。 ference on Database Systems for Advanced Applications. Berlin 参考文献: springer,2004:113-124 14 Cheung D W, Han Jiawei, Ng V T, ct aL. Maintenance of discovered [1 Verykios V S, Fovino I N, Provenza L P, et al. State-of-the-art in priva association rules in large databases: an incremental updating technique cy preserving data mining[ J. ACM SIGMOD Record, 2004, 33 [C]//Proc of the 12th International Conference on Data Engineering Washington DC: IEEE Computer Society, 1996: 106-114 [2」徐剪,秦小麟,杨一涛,等一种考虑属性权重的隐私保护数据发[15] Gitanjali J, nlumathi J, lyengar丶C.SN. a pristine cle;nc" ballistic 布方法[J]计算机研究与发展,2012,49(5):913-924 fruity strategize based approach for incremental data stream privacy [3]倪巍伟,张勇,黄茂峰,等,一和向量等价置隐私保护数据干扰 preserving data mining[ C]//Proe of Advance Computing Conference 方法J].软件学报,2012,23(12):3198-3208 Washington DC IEEE Computer Society, 2010: 410-415 [4 Seo S C, Kim T, Jang M. A privacy-preserving approach in content 16 Wang Jinlong, Xu Congfu, Pan Yunhe. An incremental algorithm for centric networking[ C]//Proc of the 11th Consumer Communications mining privacy-preserving frequent itemsets[ C]//Proc of International and Networking Conference. Washington DC, ieee communications Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE Societv,2014:866-871 Press,2009:1132-1137 [5] Chaabane A, Cristofaro E D, Kaafar M A, et al. Privacy in content-ori-[17 Rajalakshmi V, Mala GS A. An intensified appmach for privacy pre ented networking: threats and countermeasures[ J. ACM SIGCOMM servation in ineremental data mining[ c]// Proc of Advances in Com- Computer Communication Review, 2013, 43(3): 25-33 puting and Information Technology. Berlin: Springer, 2013: 347-355 [6] Islam m Z, Brankovic l. Privacy preserving data mining: a noise addi-[18]王磊,李天病.一种基于短阵的知识粒度计算方法[J]·模式识别 Based Systems, 2011, 24(8): 1214-1227 nique[]. Knowledge- ork using a novel clustering ted 与人工智能,2013,26(5):447453 「19]蒙祖强,周石泉.不一致決策系统中基于粒度计算的广义决策规 [7]李艳辉,刘浩,袁野,等.基于差分隐私的频繁序列模式挖掘算法 则获取方法研究[J].计算机科学,2012,39(1):198-20)2.

...展开详情
试读 5P 论文研究-增量式隐私保护数据挖掘研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    上传资源赚积分,得勋章
    最新推荐
    论文研究-增量式隐私保护数据挖掘研究.pdf 6积分/C币 立即下载
    1/5
    论文研究-增量式隐私保护数据挖掘研究.pdf第1页
    论文研究-增量式隐私保护数据挖掘研究.pdf第2页

    试读已结束,剩余3页未读...

    6积分/C币 立即下载 >