（计算机应用技术专业论文）敏感规则隐藏算法的研究.pdf

， 一 、- 一r c ：l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g r e s e a r c ho fh i d i n gs e n s i t i v er u l e s a l g o r i t h m c a n d i d a t e ：w r e ix i a o h u i s u p e r v i s o r ： a c a d e m i cd e g r e e a p p l i e df o r ： s p e c i a l i t y ： d a t eo fs u b m i s s i o n ： d a t eo fo r a le x a m i n a t i o n ： u n i v e r s i t y ： p r o f z h a n gj i a n p e i m a s t e ro fe n g i n e e r i n g c o m p u t e ra p p l i e dt e c h n o l o g y 2 8 t hd e c e m b e r , 2 0 0 9 1 5 t hm a r c h , 2 0 1 0 h a r b i ne n g i n e e r i n gu n i v e r s i t y 学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：委耻i 洗i 跟 日期：歹o ，d 年多月土日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可叼在授予学位1 2 个月后口解密 后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：瑰i 玩雌 日期： 多d o 年乡月姻 导师 多研0 哈尔滨工程大学硕士学位论文 摘要 敏感规则隐藏是隐私保护数据挖掘的一个重要分支，受到越来越多的研 究工作者的重视。敏感规则的隐藏应用非常广泛，主要应用于商业竞争与合 作、金融等领域。目前存在的敏感规则隐藏算法存在局限性，很多算法是根 据敏感规则的数量确定扫描数据库的次数，时间开销大。这些算法在对敏感 规则隐藏过程中，对数据库的影响较大，降低了处理后数据集的可用性。因 此为了在关联规则隐私保护的同时降低对原有数据集影响，需要一个能够力 求两者的平衡的敏感规则隐藏算法。 本文在分析和研究了国内外隐私保护的敏感规则隐藏技术的基础上，针 对采用数据阻塞方法的敏感规则隐藏算法扫描数据库次数多，时间开销大， 对数据集影响大的不足，进行改进，降低了对数据库的影响，提高了时间效 率。本文的要点主要有两个方面：首先，选用一种两遍扫描数据库的模型， 通过改进模型中的中间文件的结构和对中间文件的操作，为改进算法的实施 提供基础。其次针对现有数据阻塞方法隐藏敏感关联规则的算法存在的不足， 提出了一种改进的敏感规则隐藏算法。该算法分为三个方面：第一，在敏感 事务的选择上，以冲突度大小为选取指标，处理规则间有交集的情况。同时 防止对同一事务同一牺牲项的重复选择。减少对数据集的影响次数。第二， 在牺牲项的选择上，选择规则中包含的多个项目，对不同的支持事务分别轮 换选择其中的一个进行处理。第三，通过与模型中的中间文件的交互，第二 次扫描数据库后，即完成对数据库的清洗。实验结果和理论分析都验证了算 法的有效性和准确性及数据集可用性的提高。 关键词：隐私保护；敏感规则；安全边界；冲突度 哈尔滨t 程大学硕士学位论文 a b s t r a c t a sa ni m p o r t a n tb r a n c ho fp r i v a c y p r o t e c t i n gd a t am i n i n g ，s e n s i t i v er u l e s h i d i n gi sh i g h l yv a l u e db ym o r ea n dm o r er e s e a r c h e r s t h ea p p l i c a t i o no f s e n s i t i v er u l e sh i d i n ge n c o m p a s s e saw i d er a n g eo ff i e l d s ，m a i n l yi nb u s i n e s s c o m p e t i t i o n , c o o p e r a t i o na n df i n a n c e t h e r ea r es e v e r a ll i m i t a t i o n so ft h ee x i s t i n g a l g o r i t h m s ：m a n yo f t h e ms e tt h ef r e q u e n c yo fs c a n n i n gt h ed a t a b a s ea c c o r d i n gt o t h en u m b e ro fs e n s i t i v er u l e s ，w h i c hr e q u i r e sm u c ht i m es p e n d i n g o nt h eo t h e r h a n d , m a n ya l g o r i t h m sg r e a t l ya f f e c tt h ed a t a b a s ew h e nh i d i n gt h es e n s i t i v er u l e s ， r e d u c i n gt h ea v a i l a b i l i t yo fp r o c e s s e dd a t as i d e s t h e r e f o r e ，i t i sn e c e s s a r yt o d e v e l o pas e n s i t i v er u l e sh i d i n ga l g o r i t h mw h i c hr e a c h e dt oab a l a n c ep o i n t b e t w e e np r o t e c t i n gp r i v a c ya n dr e d u c i n gt h ei m p a c to ft h eo r i g i n a ld a t as i d e s b a s e do nt h es t u d ya n da n a l y s i so ft h ed o m e s t i ca n di n t e r n a t i o n a lt e c h n o l o g y o fh i d i n gs e n s i t i v er u l e s ，t h ea r t i c l ei m p r o v e st h ed e f e c t sb yr e d u c i n gt h ei m p a c t o ft h ed a t a b a s ea n di n c r e a s i n gt h et i m ee f f i c i e n c y t h e r ea r et w om a i np o i n t so f t h i sa r t i c l e ：f i r s t ，t of o r mt h eb a s i so ft h ei m p l e m e n t a t i o no ft h ei m p r o v e d a l g o r i t h m ，am o d e lw h i c hs c a n st h ed a t a b a s et w i c ei sc h o s e na n dt h es t r u c t u r ea s w e l la st h eo p e r a t i o no ft h ei n t e r m e d i a t ef i l e si si m p r o v e d s e c o n d ，a i m i n ga tt h e s h o r c o m i n g so f t h ee x i s t i n ga l g o r i t h mw h i c ha p p l i e st h ed a t ab l o c k i n gm e t h o d , a l li m p r o v e da l g o r i t h mf o rh i d i n gs e n s i t i v er u l e si sp r o p o s e d t h e r ea r et h r e e a s p e c t so ft h ea l g o r i t h m ：f i r s t l y , t h ec o n f l i c td e g r e ei sr e g a r d e da st h eb e n c h m a r k t os e l e c tt h es e n s i t i v em a r e m ，a n dt h e r ei so v e r l a pb e t w e e nt h ep r o c e s s i n gr u l e s m e a n w h i l e ，t h er e p e a t e ds e l e c t i n go ft h es a m et r a n s a c t i o na n di t e m sa r ep r e v e n t e d t or e d u c et h en u m b e ro fi m p a c to nt h ed a t as i d e s s e c o n d ，w h e ns e l e c t i n gt h e v i c t i mi t e m s ，m u l t i p l ei t e m sw i t h i nt h er u l ea r es e l e c t e da n dd i f f e r e n ts u p p o r t 哈尔滨t 程大学硕士学位论文 s e r v i c e sa l er o t a t e dr e s p e c t i v e l y , o n eo ft h e mi ss e l e c t e da n dp r o c e s s e d t h i r d l y , b yi n t e r a c t i n g 、) l r i t l lt h ei n t e r m e d i a t ef i l e si nt h em o d e l ，t h ed a t a b a s ei sc o m p l e t e l y p r o c e s s e d a f t e rs c a n n e dt w i c e a l lt h ee x p e r i m e n t a lr e s u l t sa n dt h e o r e t i c a l a n a l y s i sh a v ev e r i f i e dt h ev a l i d i t ya n da c c u r a c yo ft h ea l g o r i t h ma n dt h e i m p r o v e m e n to ft h ea v a i l a b i l i t yo ft h ed a t as i d e s k e yw o r d s ：p r i v a c yp r o t e c t i o n ；s e n s i t i v er u l e s ；s a f e t ym a r g i n ；c o n f l i c td e g r e e 哈尔滨t 程大学硕十学位论文 目录 第1 章绪论l 1 1 课题的研究背景及意义l ， 1 2 研究现状“2 1 3 研究内容与论文组织结构”5 第2 章隐私保护与敏感规则概述”7 2 1 隐私保护”7 2 1 1 隐私保护的内容7 2 1 2 隐私保护的类型8 2 2 数据库中敏感规则的隐藏1 0 2 2 1 敏感规则隐藏的定义l o 2 2 2 敏感规则隐藏的类型lo 2 3 本章小结- l l 第3 章敏感规则隐藏技术的研究1 2 3 1 敏感知识隐藏技术1 2 3 2 敏感规则隐藏方法1 3 3 2 1 数据变换一1 4 3 2 2 数据阻塞一15 3 3 敏感规则隐藏评价原则1 7 3 3 1 评价依据o ”1 7 3 3 2 评价指标一l8 3 3 3 其他评测因素一2 2 3 4 本章小结”2 3 第4 章敏感规则隐藏算法的研究2 4 4 1 问题的提出2 4 4 2 问题的定义”2 6 4 3 敏感规则隐藏的模型2 7 4 4 2 改进算法的伪码描述3 2 4 4 3 改进算法实例3 4 4 4 4 改进算法分析”3 6 4 5 本章小结3 7 第5 章实验结果与分析3 8 5 1 实验准备3 8 5 1 1 实验目的3 8 5 1 2 实验环境”3 8 5 1 3 实验数据3 9 5 2 实验评估指标3 9 5 3 仿真实验及结果分析一3 9 5 3 1 算法性能与安全边界值的关系3 9 5 3 2 算法性能与敏感模式比率的关系4 2 5 4 本章小结4 6 结论4 7 参考文献4 8 攻读硕士学位期间发表的论文和取得的科研成果5 4 致谢”5 5 哈尔滨t 程大学硕十学位论文 第1 章绪论 1 1 课题的研究背景及意义 当今时代的变迁日新月异，计算机和网络技术的迅猛发展使得人们使用 的数据信息量不断加大。因此很多敏感信息的交流和使用以及各商业合作伙 伴之间的资源共享，带来的信息交互，引起了越来越多人，对数据挖掘中保 护隐私和安全性问题的关注f l 】。隐私保护挖掘在数据挖掘中是一个新的研究 方向。目前现有的方法会引起隐私信息的外泄，这种信息的泄露，对于数据 库的使用和信息的安全会有很大的影响。因此，不得不从保护隐私的角度重 新考虑。隐私保护在数据挖掘中，敏感的原始数据信息是需要被保护的，并 且从中挖掘的敏感知识，也因其同样可能造成对他人隐私的暴露，而应当被 除去。因此对现有的数据应用特定的技术手段进行处理来避免敏感信息的外 泄，是隐私保护挖掘追求的目标圆。 很多企业得益于数据的共享带来的效率和效益，与此同时信息的共享也 会带来隐私信息和信息中含有的敏感知识被给竞争对手恶意的获得和使用的 安全隐患，对企业利益造成威胁。 这样的问题往往是在多个处于竞争关系的公司之间，合作进行关联规则 挖掘时需要共享彼此数据而带来的。与此同时，各竞争方都不愿意因自身的 战略性的模式、关键性信息之间的关联被挖掘出来而泄露给其他竞争对手。 这种安全利益上的隐患，促使各个公司在交流与共享信息资源之前，必须采 用合适的方法把这些敏感性的知识清除掉，经过过滤处理后再将数据库共享 使用。同时利用这种方法，也避免了别有用心的对手对自己的隐私信息的恶 意滥用和推理【3 】。 综上，数据的交换和共享与信息安全之间的此消彼长是造成敏感规则隐 藏问题产生的原因和背景。在这种背景下信息的交换和共享使用是在互相合 1 1 2 研究现状 伴随着互联网技术一同成长与发展的计算机处理能力和存储技术突飞猛 进，在搜集、发布和交换与共享的各种信息日渐增多的同时也对隐私问题提 出了挑战，在从大量的数据信息发现蕴含的有利知识并加以利用的同时，数 据挖掘也不可避免的造成了信息的滥用和隐私的外泄。r e z g u r 等于2 0 0 3 年指 出“随着计算机的普遍应用和互联网的出现，隐私变成了一个数字化问题”。 面对这样的情况，人们在提供信息资料的同时开始更多的关注隐私信息的泄 露问题【s 】。 a g r a w a l 于1 9 9 9 年曾指出隐私保护问题是数据挖掘技术发展的下一个方 向 6 1 。v a i d y a ，c l i f t o n 和k a n t a r c i o l u 于2 0 0 2 年定义隐私保护为“在未知数据值 的情况下，获得数据挖掘的结果”。他们对数据挖掘中隐私的具体内容的含义， 包括个体隐私( i n d i v i d u a lp r i v a c y ) 、联合隐私( c o r p o r a t i o np r i v a c y ) 和 规则限制( r e s u l t sr e s t r i c t i o n ) 等概念作出了定义川。自1 9 9 9 年敏感规则隐藏 的概念被定义和使用后，引起了更为广泛的关注，在i c d m ，c i k m ，p a k d d ， d a w a k 等国际会议以及t k d e ，u b i d m 等期刊上，呈现出了丰富的研究成 果嗍。 d a s s e n ie ，v e r y k i o sv s 等人首先提出了用增加规则左件支持度的方式来 降低规则置信度i 拘a l g o l a 算法，在选择事务时以包含项目最多为标准，期望 用这种方式，控制数据集中的信息的相异程度。随后又提出了相似的a l g o l b 算法，不同的是该算法在选择项目上对规则的右件更感兴趣，在事务的选择 上更倾向于含有整条规则的交易，选择策略上的不同是该算法选择了最短的 2 哈尔滨工程大学硕士学何论文 事务来减小对其它项集的影响。之后还提出的a l 9 0 2 a 、a l 9 0 2 b 和a l 9 0 2 c 算法 则是从支持规则的大项集入手，调整大项集中项的数量来控制支持度，过滤 规则。这组算法的特点是以最小支持度和最小置信度达到阈值为标准。缺点 是不能处理规则之间有交集的情况【。】。 o l i v e i r a 等人在前述算法的基础上，于2 0 0 2 年提出n a i v e 算法，给出了冲 突度的概念，这个算法保护的是数据集中出现次数多的项，牺牲冲突度高的 项的方式保持数据库中事务数目的稳定。随后提出的m i n f i a ( m i n i m u m f r e q u e n c yi t e ma l g o f i t h m ) 算法和m a x f i a ( m a x i m u mf r e q u e n c yi t e ma l g o f i t h m ) 算法改为选用冲突度最小的事务并分别选择支持度最小和最大的项作为候 选，希望以此缓解对事务集中项的影响。在这之后提出了一个利用敏感规则 分组的方式处理规则之间相交问题的i g a ( i t e mg r o u p i n ga l g o f i t h m ) 算法，结 合冲突度和公开度的引入，保证了非敏感规则的可用性。这组算法的特点是 通过公开度和冲突度的引入，能针对模式之间相交的情况做出反应，为以后 的研究工作提供了新的思路m 1 。 o l i v e i r a 等人在2 0 0 3 年又进一步提出了s w a ( s l i d i n gw i n d o wa l g o f i t h r n ) 算法，不同之处是一窗口的形式对事务进行扫描，选择出现频率高的数据项 和短作业减少信心的丢失。这个算法不比一次将数据全部读入内存，适合对 大规模数据库的处理t i l l 。 以上介绍的算法的共同特点，是都应用了启发式的策略处理过滤信息的 办法，近年来也出现了一些定量指标引导下是算法。s u nx 。y up s 提出了一 种项集格清洗的算法，该算法通过一个测度函数来估计每一步操作对项集边 界值的影响，以此来平衡对非敏感项集造成的影响。这种算法的缺点是计算 代价大。随后l e eg 等提出了3 种利用矩阵乘法处理布尔数据的清洗矩阵算 法，通过控制频繁二项集的在模式中的比率，分别采用了隐藏优先和非隐藏 优先及两种优先方式相结合的三种策略 t 2 1 。w a n ge t 等人在这种清洗矩阵的 基础上，提出了改进的算法，更新了过滤矩阵的构造，通过对频繁项集的二 项子集的隐藏避免向前推理【，】。 哈尔滨t 程大学硕十学位论文 在数据阻塞法隐藏规则方面，早在2 0 0 1 年js a y g i ny 等人提出了g i h ( g e n e r a t i n gi t e m s e t sh i d i n g ) 算法，这个算法是针对生成模式的项集，通过减 少其支持度范围的下边界，完成规则的隐藏，选择长度最短、支持度区间下 界最大的事务对其阻塞来降低对其他项集的不利影响【1 4 】。s a y g i ny 同时还提 出了c r 算法和c r 2 算法，都是通过降低置信度隐藏规则的，与g i h 算法不同 的是后两种算法更侧重规则的右件的处理。这些算法为今后的数据阻塞方式 隐藏规则打下了基础，之后的很多数据阻塞的方法都是在这些算法的基础上 改进的。h i n t o g l u 等人于2 0 0 5 年在s a y g i ny 提出算法的基础上提出了改进的 m c r 和m c r 2 算法，引入了量化的估算函数来计算每一步的信息损失来帮助 选择损失小的阻塞方式，这种方法的特点是在减小了新旧数据库差异的同时， 增加了使用评估函数计算的时间开销【t s 】。 在数据重构发隐藏规则方面，g u oy h 等人提出了反向频繁项集的挖掘方 法，借助启发式原则通过筛选后的频繁项集重构数据集的方式达到隐藏规则 的目的【旧 在算法的评价方面，面对众多的隐私保护的算法，如何评价和比较它们 的优劣，衡量它们的有效性成为必然的需要。v e r y k i o s ，b e r t i n o ，f o v i n o 等 在2 0 0 4 年提出了对各类隐私保护算法的评估标准：首先，需要考虑算法的性 能，即计算算法的执行时间和需要占用的空间；第二，需要关注算法的精度， 即算法在判断的准确程度、信息丢失的程度上和产生错误信息的数量上的评 估；第三，算法的过滤效果，即对原始数据库中隐含的敏感性知识的成功处 理的能力；第四，算法的适用性，即算法对不同的数据挖掘技术和具有不同 特点数据集的适应能力【- 7 l 。 算法的不同标准都有各自的针对性，因此也不可能存在一个算法即能满 足所有的评价标准，因此设计一套统一的标准给使用者选择适合自己的隐私 保护算法提供有力参照也很重要。 近年来，国内的专家学者虽然在隐私保护数据挖掘的研究开展较国外稍 晚，但在敏感规则隐藏方面，特别是针对某一具体的隐私保护算法进行研究 4 哈尔滨工程大学硕十学位论文 也取得了较大的成果。郭宏宇、童云海等人在研究了数据库中知识隐藏，做 出了综述性的总结【。】。张鹏等人提出了一种将数据干扰和查询限制相结合的 隐私保护挖掘算、法【博l 。此外还有许多学者正在以隐私保护为课题开展他们的 研究工作。 国内外数据库研究领域的专家学者虽然在隐私保护的敏感规则隐藏方面 已经取得了颇丰的成果，但同时也仍然存在着某些方面的不足之处，而人们 对数据库中敏感知识的安全性的需求也将会随着时代的变迁发生变化，对数 据准确性、可用性、适应性的要求越来越高。面对更高标准的需求和挑战， 需要研究者们拓宽思路、不断创新，研究更加完善和有效的保护隐私信息的 处理方法。 1 3 研究内容与论文组织结构 本论文的主要研究内容有以下几点： ( 1 ) 对数据库中的知识隐藏理论、方法进行研究，对数据挖掘中的敏感 关联规则隐藏理论进行深入的研究。 ( 2 ) 对各种敏感关联规则算法和技术进行了深入的研究。重点分析了现 有的算法的实现策略。 。 ( 3 ) 针对现有算法访问数据库次数过多和对原有数据集影响较大的不 足，给出基于数据阻塞方式的算法，给出其理论依据及实现步骤。该算法在 对事务数据库进行清洗时，能减少对数据库的访问次数，提高清洗算法的效 率。降低对数据集的影响。 ( 4 ) 用合成数据集进行实验，并分析实验结果。 本论文内容组织如下： 第l 章叙述研究背景、研究现状和研究意义，给出本文研究的主要内容。 第2 章概述数据挖掘、数据库中的敏感知识隐藏的基本概念。首先介绍 隐私保护的定义、过程、分类和应用。然后介绍数据库中知识隐藏定义、类 型。 5 哈尔滨下程大学硕十学位论文 第3 章介绍敏感规则隐藏技术。详细介绍各种分类标准下的敏感规则隐 藏方法的内容、过程及讨论现有的典型敏感关联规则隐藏算法，并对典型算 法进行分析。 第4 章详细介绍敏感关联规则的隐藏算法，重点讨论敏感关联规则隐藏 模型和数据阻塞方法，对算法进行了剖析，并对模型和算法进行改进，给出 了改进的模型和新的算法，然后用实例进行验证，说明新算法与现有算法相 比所具有的优势。 第5 章使用合成数据集，对算法进行性能测试，并将的测试结果进行对 比评估，并对实验结果进行了详细的分析。 6 哈尔滨t 程大学硕士学位论文 第2 章隐私保护与敏感规则概述 隐私保护中的敏感性规则的保护的基本概念和方法是研究数据数据库中 敏感规则隐藏技术的基础，本章将重点介绍隐私保护的基本内容、隐私保护 的类型、数据库中规则隐藏的基本概念、规则隐藏的类型，为后面的研究工 作奠定基础。 2 1 隐私保护 互联网技术的发展给人们的生活带来了越来越多的便捷，在通过互联网 日渐方便的收集、发布、传播各种信息的同时，但伴随着计算机处理能力和 存储技术的发展也带来了隐私问题，正如数据挖掘在我们从中找到可利用的 深层的信息的情况下，也容易造成信息的泄露和滥用。近年来，隐私保护问 题引起了人们更多的关注。 2 1 1 隐私保护的内容 一数据挖掘中的隐私包括个体隐私( i n d i v i d u a lp r i v a c y ) 、联合隐私 ( c o r p o r a t i o np r i v a c y ) 和规则限制( r e s u l t sr e s t r i c t i o n ) 等主要内容。 总的来说，个体隐私的保护就是要防止个人信息内容本身被外泄。首先， 个人隐私信息是指可以通过这些信息关联到具体人的相关信息；如根据一个 人的身份证号码或家庭住址和工作单位及配偶信息等等一项或多项属性取值 就可以具体的关联到某个人。因此对于个体数据本身的保护，就是要保证个 体的信息不能通过个别属性关联出具体的个体本身。达到这样的要求就保证 了个体信息的安全。在有些情况下，不仅仅要保护个体的隐私，还需要对个 体之间相互关系在一起的隐私进行保护。这种相互关联的隐私不再以个别的 7 哈尔滨工程大学硕士学位论文 数据为研究对象，而是以信息的整体为单位。就像一个人不会介意公开他的 生日、配偶、家庭住址等普通信息，但是会在意掌握所有的这些信息联合在 一起的整体而造成的危害个人财产的问题。同时大规模信息和多个体信息搜 集等等也都包含在联合隐私的研究范围之内。 此外，数据挖掘中发现的规则中包含了许多重要的信息，这些信息也同 样需要必要的保护手段。如某商场长期的重要客户的购物特征相关联的属性 等规则，这些知识如果被竞争对手的人恶意获得，将会严重影响今后的经济 效益和发展。 o l i v e i r a 等人于2 0 0 4 年提出了隐私保护要在保护隐私信息不被威胁的同 时好保证在数据上的数据挖掘工作保持正确的结果。并对数据挖掘领域的隐 私保护问题的研究内容进行了阐述 1 9 1 1 ( 1 ) 保护个体信息：个体隐私保护是保护与个体相关的，能够标志和匹 配出个体的相关特征和属性。概括的说，就是可以直接或间接的通过这些信 息找到相应个体的数据。于是，要对个体的信息进行保护，保证在含有个体 信息的数据集上应用数据挖掘算法时只能获得普遍性的知识而无法针对特定 的个体信息。 ( 2 ) 保护联合信息：对联合信息的保护实际上就是避免能够通过数据挖一 掘算法挖掘出的敏感性规则。这也是针对只保护个体信息的不足所作的进一 步补充【刎。 7 2 1 2 隐私保护的类型 1 、应用类别分类 根据应用类别的角度不同，隐私保护算法分为集中式和分布式两种类型。 集中式的主要特点是能把数据保存在一起，利用算法统一处理。分布式是和 集中式相对立的概念，分布式的数据可以分布在很大区域内。其中集中式的 隐私保护算法应用较为广泛，已经应用到各个领域中。相比之下，分布式类 8 哈尔滨丁程大学硕七学位论文 型的隐私保护算法应用较少，目前主要还处于理论研究中【：，】。 2 、技术方法分类 根据技术方法的不同，将隐私保护算法可以分为通过数据变形处理和数 据模糊处理两种方法处理的类型。为了达到隐藏敏感数据或规则效果，又不 改变原数据，采用了密码技术，对数据进行处理。经过处理后的数据就可以 达到隐藏的目的【2 2 】。 从目前研究情况看，大多数研究方向是如何修改数据，能够有效的进行 隐私保护。因为数据始终是要提供给用户使用的，而隐私保护的目的就在能 把敏感的数据和规则隐藏起来，让用户的使用过程中不接触敏感内容，从而 隐私安全得到了保障【矧。 3 、隐藏目标分类 根据需要隐藏的目标的不同分为两大类。一类目标是对数据的隐藏，这 类是指那些数据本身就带有隐私信息的需要被保护的原始数据，如身份证号 码、账号、地址以及工作单位等其他相同性质的数据，这些数据被保护起来 就要改变它们在原始数据库存在形态。另一类是规则隐藏，是指通过在数据 集上运行数据挖掘算法能够从中挖掘出的不希望泄露出去的敏感规则，需要 把这些规则筛选去除。在针对分布式数据库的隐私保护算法中，研究范围主 要集中于数据隐藏方面，甚至只涉及到对数据的隐藏，即多个数据源同时进 行应用时要保证独立性。相比之下规则隐藏在隐私保护中比数据隐藏在一个 更高层面上，这种通过保护敏感规则来对重要的原始数据进行保护，是隐私 保护种更为重要问题【2 4 】。 4 、适用范围分类 根据隐私保护算法适用的范围的不同，隐私保护算法分为对关联规则的 保护、对分类规则的保护和对聚类规则的保护以及序列模式的保护等等。关 联规则的保护针对关联规则，旨在寻找给定数据集中频繁同时出现的相互关 联的项目并根据挖掘出的结果，来对属性之间蕴含的重复发生的关联特征做 出推断的特点，防止敏感的关联规则被恶意的发现和使用。分类规则的保护 9 哈尔滨丁程大学硕士学位论文 是指防止泄露那些对数据库记录划分的敏感性规则。保护聚类信息是防止通 过对数据库的挖掘找到其中存在的能将数据对象划分成簇的聚类的依据【z s l 。 根据目前的研究成果来看，对隐私保护技术应用方面最多，而其他算法相比 之下较少。 2 2 数据库中敏感规则的隐藏 2 2 1 敏感规则隐藏的定义 在数据库中，敏感规则隐藏的定义，是通过特定的方法和技术策略，控 制使在原始数据库中能被挖掘出来的敏感规则在保护后无法被发现的过程。 举例来说就是，如果在原数据库中能够挖掘到敏感规则r ，而经过适当的隐 藏方法处理后产生的新数据库中无法通过数据挖掘算法找到规则r ，即完成 了规则隐藏。 2 2 2 敏感规则隐藏的类型 敏感规则隐藏的类型可以在知识内容的种类和隐藏方式两种层面上对敏 感规则的隐藏进行划分。 7 知识类型的不同要求应用不同的隐藏方法。从这个角度敏感规则隐藏被 分为对敏感关联规则、敏感的分类规则、对敏感的序列模式一级对敏感聚类 的隐藏方法等等。目前在关联规则的隐藏方面研究成果最多。从隐藏方式的 角度的不同，研究的技术主要由数据变换、数据阻塞、数据重构和数据抽样 等等几种方法组成。 ( 1 ) 数据变换 这种方法简言之就是改变数据库中数据项的数值。通过这种按特定选择 方式对支持敏感规则的敏感事务的项修改取值的方法，调整支持规则的事务 数量的下降，即降低规则的支持度，当支持度降低到规定的指标以内时即实 现隐藏。 1 0 哈尔滨t 程大学硕士学位论文 ( 2 ) 数据阻塞 这种方法中提到的阻塞，实际上是通过将原数据库中的若干个别项修改 为不确定的“? ”的方式，将数据库中存在的敏感性规则的支持度和置信度，从 一个单一的数值变化为一个有上下界的区间。通过对这个区间大小的要求来 隐藏规则。 ( 3 ) 数据重构法 这种不局限于原数据集的数据重构法是由c h e r t 等人提出【：，】的，比数据交 换和数据阻塞出现更晚的方法。方法的执行思想是利用了产生规则的频繁项 集重组数据集。首先借助于特定的技术方法过滤频繁模式，再以过滤之后的 频繁模式为基础，通过与数据变换和阻塞法改变原始数据集截然不同的，反 向重构一个数据集的方式，构造出一个新数据集，使新数据集中挖掘不出敏 感规则，来实现对敏感规则的隐藏。 2 3 本章小结 本章综述了隐私保护和敏感规则的相关研究工作。首先介绍了隐私保护 的基本概念，隐私保护的内容和隐私保护的类型。其次介绍了数据库中敏感 规则隐藏的概念和各种类型规则隐藏的定义。为后面的敏感规则隐藏技术的 研究做出了准备。 哈尔滨丁程大学硕十学位论文 第3 章敏感规则隐藏技术的研究 本章在对隐私保护与敏感规则隐藏理论深入分析研究的基础上，分别阐 述了敏感知识隐藏的技术、敏感知识隐藏的方法的操作手段和各种方法的原 理及步骤。通过对敏感规则隐藏的技术原理、实现方法以及敏感规则隐藏理 论基础的分析与研究，为后面隐藏敏感规则的模型的建立以及敏感规则隐藏 算法的研究提供理论基础。 3 1 敏感知识隐藏技术 在给定了数据挖掘使用的安全的阈值的情况下，通过数据挖掘算法可以 从数据库中挖掘出一组规则r ，假定在这组规则r 中，已经由数据库的拥有 者或使用者规定出了其中哪些规则是敏感的。那么规则隐藏算法的目的，即 为使那些敏感性的规则，不能被数据挖掘算法找到。同时做到尽可能的减少 对那些需要保留的非敏感性规则的影响，因而最大限度的保证数据较高的质 量和可用性。 为了处理隐藏规则问题，文献 1 4 d ps a y g i n 提出将项集的支持度减少到 最小支持度，也可以减少到最小支持度边界值以下。为了利用这种思想，可 以使用增加项和删除项的手段达到改变支持度和置信度的目的。还可以由用 “? ”取代原来的真实值以改变支持度和置信度由一个值变为一个不确定性的 区间来完成。 对敏感关联规则的保护算法包括两种类型：一种是利用减少项集的支持 度，另一种是利用减少置信度，以防止敏感规则被发现。参考支持度和置信 度的基本概念，对某一规则b _ c ，经过规则隐藏算法的过滤，存在如下不 等式【硼： 1 2 哈尔滨t 程大学硕十学位论文 s u p ( b _ c ) 三m s t 并且c o n f ( b - - - c ) m c t 其中m s t 表示最小支持度的安全值，m c t 表示最小置信度的安全值。为了 使不等式成立，要调整支持度到m s t 以下，置信度到m c t 以下。进而将规 则隐藏分为以下两种： ( 1 ) 调整支持度 。 如果采用的是通过调整规则的最小支持度来隐藏规则，对于数据集中的 条敏感规则，可以采用调整规则右件支持度的方法，一直到规则的支持度 降低到最小支持度m s t 以下。 如果采用的是通过调整生成规则的大项集的支持度来隐藏敏感规则，对 于数据集中的一条敏感规则，可以采用调整规则的大项集的支持度大小的方 法，一直到规则的支持度降低到最小支持度m s t 以下。 ( 2 ) 调整置信度 如果采用的是通过调整规则的置信度来实现隐藏规则，对于每一条敏感 规则，可以采用增加规则的左件支持度的方法，一直到规则的置信度调整到 最小置信度m c t 以下为止。 如果采用的是通过调整规则的大项集的支持度来隐藏敏感规则，对于每 一条敏感规则，可以采用调整规则的大项集的支持度的方法，待规则的支持 度降低到最小置信度m c t 以下规则隐藏完成。 敏感模式的保护是从生成敏感规则的频繁模式集合入手，从支持敏感模 式的事务集合中选择待处理的事务，从模式中包含的项集中选择待处理的项， 通过降低生成规则的模式集合中出现在规则中的项的支持度和置信度来避免 敏感知识被挖掘到。 3 2 敏感规则隐藏方法 本文在2 2 节中对各敏感规则方法的定义已经做出了概述，下面对具体 的隐藏方法加以说明。 哈尔滨工程大学硕十学位论文 3 2 1 数据变换 设用布尔矩阵将原始数据库表示出来，将事务数据库中的每个事务表示 为矩阵中的一行，根据布尔矩阵的特点，所以每一行的数据有“l ”和“0 ”两种。 分别表示矩阵中对应属性出现在事务中和矩阵中对应属性不出现在事务中， 那么数据变换的过程，就是通过将敏感事务在布尔矩阵内数值取反操作，修 改和过滤原有事务的属性，调整支持度和置信度，使其能够被控制在预定的 范围内。 假设规则a _ b 为敏感规则，规则的支持度，在包含它数据集中为0 8 ， 置信度为l ，如图3 1 所示，此时为了防止这条规则被挖掘到，选择数据集中 的第2 个、第4 个事务内属性b 的值取反，变换够规则b 的支持度调整 为0 4 ，置信度也调整到0 5 。此时如果已经低于支持度和置信度的安全值即 达到了隐藏规则a - - - , b 的效果，避免了其在新数据集内出现。这种数据变换 方式隐藏规则时有以下三个要点： ( 1 ) 针对待隐藏的敏感规则，确定将要处理的事务； ( 2 ) 在待选事务集中挑选出处理的事务和需要修改的项； ( 3 ) 修改选定的事务集中所对应的牺牲项； 原始数据集 abcd l1l0 ll01 o001 1l0l 1ll0 修改后数据集 abcd l1l0 4 尊 l 。0j 0l 000l 。 1 o ：l 1o 1l 0l 图3 1 数据变换法示意图 ， 1 4 哈尔滨t 程大学硕十学位论文 在对敏感规则进行清洗的过程中，在一个给定的数据集和确定的敏感规则集 上选择效果最佳的数据对象是一个n p 难题。面对这样的问题出现了以启发 式方法为主的很多算法。 由e d a s s e n i ，v s v e r y k i o s ，a k e l m a g a r m i d 等人在2 0 01 年提出的a l g o la 、 a l g o l b 、a l 9 0 2 a 、a l 9 0 2 b 及a l 9 0 2 c 算法，仅仅假设不同的模式内不存在交集 项，每次过滤操作只针对其中的一条规则，对在支持度、置信度的调整中， 要隐藏一条规则。就要扫描一次数据库，因此这些算法的时间开销很大，效 率不高。 由o l i v e i r a 等人提出的n a i v e r n 、m i n f i a 、m a ) 【f i a l 2 8 】、i g a r g j 、r ra 【3 0 】、 r a 、s w a 等算法【3 1 1 ，引入了冲入度，能够处理规则间有交集项的敏感规则集； 同时引入了公开度，控制要过滤的敏感事务在数量上的多少；引入倒排文件 和分组模式，加速了清洗过程。 此外，除了这些采用数据清洗变换的以启发式思想为基础的方法，还出 现了一些将能够定量控制隐藏的效果的通过定量评估逐渐引入的算法。主要 包括应用测度函数方法、整数规划的方法、应用过滤矩阵的数据转换法等等。 这几种算法的操作对象，都是针对敏感项集，而不是敏感关联规则来进行隐 藏的【蚓。 3 2 2 数据阻塞 设用二进制矩阵的形式表达原始数据集，那么数据阻塞法的执行办法是 通过用问号替换事务的某些属性来改变原始的数据信息，使支持度和置信度， 从一个固定的数值，变成一个不固定区间，当区间的边界达到要求时则完成 了规则的隐藏。 如图3 2 所示，假设a _ d 是包含在数据集中的敏感规则，拥有高达1 的置信度，此时在用问