（计算机应用技术专业论文）关联规则挖掘中隐私保护技术研究.pdf

独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果，也不包 含为获得江苏大学或其他教育机构的学位或证书而使用过的材料。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：d ，超 2 驴1 1 年月ile l 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致，允许论文被查阅和借阅，同时授 权中国科学技术信息研究所将本论文编入中国学位论文全文数据 库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂志社将 本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查 询。论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密 学位论文作者签名：咨i 、起 工u1 1 年6 月l1 日 紫涉 2 u l f 年芗月f 2 日 江苏大学硕士学位论文 摘要 关联规则挖掘是从大量数据集中挖掘出潜在的知识，这就可能把涉及到个人 隐私的信息挖掘出来，从而产生了隐私保护下的关联规则挖掘。因而，如何在关 联规则挖掘的过程巾解决好隐私保护己成为数据挖掘研究领域中的一个迫切需 要解决的关键问题。虽然传统的隐私保护技术在一些领域己经得到了一定程度的 认可，但是随着时代的进步和科学技术的不断发展，人们对隐私保护对象以及隐 私保护技术提出了更高的要求，这意味着需要研究新的隐私保护方法来满足人们 的这些需求，因此，本项目的研究具有重要的理论意义和广泛的应用前景。 论文介绍了关联规则挖掘中隐私保护的国内外研究现状和基本知识，重点对 数据库中的隐私数据保护和敏感规则的保护问题进行了研究，提出了一种基于数 据交换技术的隐私数据保护方法，提高了隐私数据的隐私性和对变换后的数据库 进行规则提取的有效性。根据遗传算法的思想和特点，提出了一种基于遗传算法 的敏感规则隐私保护算法，不仅能够有效将全部敏感规则隐藏起来，而且对数据 库产生的副作用较小。 论文的主要研究成果包括以下几个方面： l 、介绍了关联规则挖掘中隐私保护的相关知识，对典型的隐私保护算法进 行了分析介绍。 2 、提出了一种基于数据交换技术的隐私数据保护算法a p p d a r m ，给出了 算法的思想和流程，并通过实验对该方法进行验证。实验结果表明a p p d a r m 方法能够有效保护数据库中的隐私数据，并提高了对修改后的数据库进行规则提 取的有效性。 3 、结合遗传算法思想，提出了一种基于遗传算法的敏感规则隐私保护算法 g a s r p ，给出了算法的流程和具体的操作过程。通过实验验证，算法g a s r p 不 仅能够有效将敏感规则进行隐藏，而且对非敏感规则丢失以及虚假规则的产生影 响者b 较爿、。 4 、以a p p d a r m 算法和g a s r p 算法为基础，使用c + + 语言，设计并实现 了一个基于隐私保护的关联规则挖掘原型系统。 关键字：关联规则挖掘，隐私保护，隐私数据，敏感规则，遗传算法 江苏大学硕士学位论文 ab s t r a c t t h ek n o w l e d g ew h i c hi sp o t e n t i a la n dh i d d e nb e h i n dl o t so fd a t ac a nb em i n e di n m e a n so fa s s o c i a t i o nr o l em i n i n ga n dp a r to ft h ek n o w l e d g em a yi n f r i n g ep e r s o n a l p r i v a c y , t h e np r i v a c yr e s e r v i n gi na s s o c i a t i o nr u l em i n i n gi ss t u d i e d t h e r e f o r e ，h o w t oe f f e c t i v e l yp r o t e c tu s e r s p r i v a c yw h i l em i n i n ga s s o c i a t i o nr u l e sb e c o m e sah o t i s s u ei nd a t am i n i n g t h o u g ht r a d i t i o n a lp r i v a c yp r e s e r v i n gt e c h n i q u eh a sb e e n r e c o g n i z e dt oac e r t a i nd e g r e ei ns o m ef i e l d s ，h o w e v e r p e o p l ep u tf o r w a r d t h eh i g h e r r e q u i r e m e n t st o w a r d st h ep r i v a c yp r e s e r v i n go b j e c ta n dp r i v a c yp r e s e r v i n gt e c h n i q u e t h i si m p l i e st h a ti tn e e d st od e v e l o pn e wp r i v a c yp r e s e r v i n ga p p r o a c h e st om e e tt h e d e m a n d so f p e o p l ew i t ht h ep r o g r e s so ft h et i m e sa n dt h ed e v e l o p m e n to f s c i e n c ea n d t e c h n o l o g y t h e r e f o r e ，t h er e s e a r c ho nt h ec o r r e s p o n d i n gp r o j e c th a sg r e a tt h e o r e t i c a l s i g n i f i c a n c ea n dw i d e s p r e a da p p l i c a t i o np r o s p e c t t h i sp a p e rc o m p r e h e n s i v e l yr e v i e w sa b r o a da n dd o m e s t i cr e s e a r c hs t a t u sa n d b a s i ck n o w l e d g eo fp r i v a t ep r o t e c t i o ni na s s o c i a t i o nr u l em i n i n g t h ee m p h a s i si s p l a c e do nt h ep r o t e c t i o n o fp r i v a t ed a t aa n ds e n s i t i v er u l e so ft h ed a t a b a s e ，a n d p r o p o s e dap r i v a c yd a t ap r o t e c t i o nm e t h o db a s e do nd a t ae x c h a n g et e c h n o l o g y , w h i c h r a i s e dt h ep r i v a c yo fp r i v a t ed a t aa n dt h ee f f e c t i v e n e s so fe x t r a c t i n gr u l e so nt h e m o d i f i e dd a t a b a s e a c c o r d i n gt ot h ec h a r a c t e r i s t i c sa n dt h o u g h t so fg e n e t i ca l g o r i t h m ， w ep r o p o s e das e n s i t i v er u l e sp r o t e c t i o na l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m ，w h i c h c a ne f f e c t i v e l yh i d es e n s i t i v er u l e sw i t hl i t t l es i d ee f f e c t s t h em a i na c h i e v e m e n t sa b o u tt h i sp a p e ra r ed e s c r i b e da sf o l l o w s ： 1 p r e s e n tr e l a t e dk n o w l e d g eo fp r i v a c yp r e s e r v i n gi na s s o c i a t i o nr u l em i n i n g ， a n da n a l y s i st h et y p i c a lp r i v a c yp r e s e r v i n ga l g o r i t h m s 2 an e wp r i v a c yd a t ap r e s e r v i n ga l g o r i t h mc a l l e da p p d a r m ，w h i c hi sb a s e do n d a t a - e x c h a n g et e c h n o l o g y , i sp u tf o r w a r d m e a n w h i l e ，t h ec o r r e s p o n d i n gt h o u g h ta n d p r o c e s so ft h ea l g o r i t h mi si l l u s t r a t e d e x p e r i m e n ti sc o n d u c t e di no r d e rt ov a l i d a t et h e p e r f o r m a n c eo ft h ep r o p o s e dm e t h o d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o dc a n e f f e c t i v e l yp r o t e c tt h ep r i v a t ed a t ai nd a t a b a s e ，a n dr e d u c et h e e f f e c t i v e n e s so f e x t r a c t i n gr u l e si nt h em o d i f i e dd a t a b a s e 1 1 1 江苏大学硕士学位论文 3 w ep r o p o s e dan e ws e n s i t i v er u l e sp r i v a c y p r e s e r v i n ga l g o r i t h mc a l l e d g a s r p , w h i c hi sb a s e do ng e n e t i ca l g o r i t h m ，a n dt h ep r o c e s sa n dc o n c r e t eo p e r a t i n g o ft h ea l g o r i t h mi sg i v e n t h r o u g ht h ee x p e r i m e n t ，w ek n o wt h ea l g o r i t h mc a nn o t o n l ye f f e c t i v e l yh i d es e n s i t i v er u l e sb u th a v es m a l l e ri m p a c t so nn o n s e n s i t i v er u l e s a n df a l s er u l e s 4 b a s e do nt h ea p p d a r ma l g o r i t h ma n dg a s r pa l g o r i t h m w i t ht h ec + + l a n g u a g e ，d e s i g na n di m p l e m e n t a t i o no fap r o t o t y p es y s t e mf o r a s s o c i a t i o nr u l e m i n i n gb a s e do np r i v a c yp r e s e r v i n g k e yw o r d s ：a s s o c i a t i o nr u l e sm i n i n g ，p r i v a c yp r e s e r v i n g ，p r i v a c y d a t a ， s e n s i t i v er u l e s ，g e n e t i ca l g o r i t h m i v 江苏大学硕士学位论文 目 第一章绪论1 1 1 研究背景及意义一l 1 2 国内外研究现状1 1 2 1 关联规则挖掘中隐私数据保护的国内外研究现状2 1 2 2 关联规则挖掘中敏感规则保护的国内外研究现状3 1 3 本文的研究内容6 1 4 本文结构6 第二章关联规则隐私保护及遗传算法概述8 2 1 关联规则相关知识8 2 1 1 基本概念8 2 1 2 关联规则的分类9 2 1 3 关联规则挖掘1 0 2 2 关联规则隐私保护j 10 2 2 1 关联规则挖掘中隐私数据的保护1 0 2 2 2 关联规则挖掘中敏感规则的保护1 1 2 3 关联规则挖掘中隐私保护算法1 2 2 3 1 关联规则挖掘中隐私数据保护算法1 2 2 3 2 关联规则挖掘中敏感规则保护算法1 3 2 4 遗传算法基础：1 6 2 4 1 遗传算法的基本思想1 6 2 4 2 遗传算法的基本流程1 7 2 4 3 遗传算法的特征18 2 4 4 遗传算法中的常用技术1 9 2 5 小结一2 3 第三章基于数据交换的隐私数据的保护算法2 4 3 1a p p d a r m 算法的基本思想2 4 3 1 1 算法的提出一2 4 3 1 2a p p d a r m 算法流程2 5 3 2a p p d a r m 算法的具体过程2 6 3 2 1 数据库d 。的确定2 6 3 2 2 数据库d m 的确定2 8 3 3a p p d a r m 算法描述2 9 3 4 算法分析31 江苏大学硕士学位论文 3 4 1 实验环境j 3 2 3 4 2 实验结果分析3 2 3 5 本章小结3 4 第四章基于遗传算法的敏感规则保护研究3 5 4 1g a s r p 算法的基本思想3 5 4 2g a s r p 算法的基本过程3 6 4 3 具体算法描述3 8 4 4 参数的设计4 0 4 5 算法性能评价4 0 4 5 1 效能评价标准4 1 4 5 2 实验及结果分析4 2 4 6 本章小结4 6 第五章基于隐私保护的关联规则挖掘系统4 7 5 1 系统模型介绍：4 7 5 2 系统设计思想及结构4 8 5 3 系统实现关键点4 8 5 3 1 数据预处理4 9 5 3 2 隐私数据的处理4 9 5 3 3 隐藏敏感规则的数据预处理5 0 5 4p p a r m 挖掘系统的实现5 0 5 4 1 系统开发环境5 0 5 4 2 系统运行环境5 0 5 4 3 系统运行51 5 5 小结5 4 第六章总结与展望5 5 6 1 本文工作总结5 5 6 2 进一步研究工作5 5 参考文献5 7 致谢6 1 附录一：读研期间发表和录用论文目录6 2 l l 江苏大学硕士学位论文 第一章绪论 1 1 研究背景及意义 随着网络、数据库存储以及高性能处理器等技术的飞速发展，数据库中存储 的数据呈爆炸式增长，导致出现了“数据爆炸，知识贫乏”的现象。在此背景下， 强有力数据分析工具的需求推动了数据挖掘技术的产生和发展。数据挖掘中的关 联规则挖掘反映了一个事件和其他事件之间依赖或关联的知识，例如：通过对医 院病人的病例数据进行挖掘，可以发现各种疾病之间的关联，对数据库中数据的 分析在帮助政府、商业界人士做出决策以及提供社会福利等方面都有着十分重要 的作用。 任何事情都有其两面性，关联规则挖掘也不例外，在关联规则挖掘产生巨大 财富的同时，随之产生的就是隐私保护方面的诸多问题。在使用一般方法进行规 则挖掘时，不可避免地暴露数据库中的数据，从而造成在数据的采集过程中，人 们由于担心个人隐私被泄露而拒绝提供涉及到自己隐私的任何信息1 1 2 】。那么， 数据采集机构或数据使用者采集到的数据往往和真实的数据之间存在很大的差 异甚至无法完成数据采集，如果在这些数据上进行相应的数据挖掘工作，那么所 得到的结果必然是不准确的甚至是完全错误的。然而，可喜的是人们并没有因噎 废食，在数据挖掘能够提供益处的面前，只要数据采集机构或使用者采取有效措 施来保证个人的隐私，绝大部分数据拥有者还是愿意提供自己的隐私数据，隐私 保护程度的高低将直接关系到是否能够获得足够真实的数据，从而影响到挖掘结 果的可靠实用性。因而，如何在关联规则挖掘的过程中解决好隐私保护己成为关 联规则挖掘研究领域中的一个迫切需要解决的关键问题，隐私保护关联规则挖掘 技术的研究具有十分重要的理论意义和广泛的应用前景。 1 2 国内外研究现状 关联规则挖掘中的隐私被划分为两类：一类是原始数据本身具有的，由于传 统的关联规则挖掘技术是在未经过加密的原始数据上进行的，也就是说必须将含 有个人或者企业隐私的原始数据交给数据挖掘者才能挖掘出有用的知识，如个人 1 江苏大学硕士学位论文 工资、银行账号等信息，我们将这些数据称为隐私数据。另一类是数据库中所隐 含的规则，将这些规则定义为敏感规则，对敏感规则的不法使用可能会威胁到数 据拥有者的权益。那么，关联规则挖掘中隐私保护是所要解决的问题是如何修改 原始数据库和关联规则挖掘算法，确保原始数据库中的隐私数据和敏感规则能够 得到有效保护或隐藏，同时在修改后的数据库中非敏感关联规则仍然有效，且不 会挖掘出虚假或幽灵规则。 1 2 1 关联规则挖掘中隐私数据保护的国内外研究现状 随着关联规则挖掘的广泛应用和随之而来的隐私泄露问题，隐私保护成为了 一个重要而富有挑战性的课题。自从隐私保护问题提出之后，产生了很多隐私保 护算法。对于数据库中的隐私数据的保护，2 0 0 2 年，r i z v is j 等人提出了一种基 于随机变换的隐私数据保护方法m a s k ，该方法通过数据干扰和分布重构实现了 关联规则挖掘中隐私数据的保护，并在随机化参数的设置和支持度的计数方法等 方面进行了优化【3 】。该算法采用将各笔交易随机化处理的方法来对原始数据进行 隐藏，方法是删除每笔交易中一些已有的项目，同时再加入一些原本在该交易中 未出现的项目。v a i d y a js 等人提出了一种采用在交易事务中增加干扰项的方法来 保护隐私数据的方洲4 1 ，不同于文献【1 】的做法，在文献 4 d d 不会删除交易中的 项目，因此在变化后的数据库中频繁项集的支持度不会低于原来的最小支持度， 数据挖掘者可以通过关联规则挖掘算法来重构频繁项目集，进而可以将隐私数据 项挖掘出来了，所以其隐私性不够高。e v f i m i e v s k i a 等人提出了“部分支持度” 的概念以及相应的计算方法，对项目集的支持度进行估算，进而实现了关联规则 挖掘中隐私数据的保护【5 】。但这些方法都是利用了统计学中的沃纳模型，不仅由于 变换后的所有数据均与真实的原始数据直接相关，使得对隐私数据的保护程度并 不理想，而且随机化参数的选择也都受到限制，必须偏离0 5 ，同时该方法也不能用 来处理长记录，而且每个k 一项集都需要指数级的计算，时间代价较高。 2 0 0 6 年，张鹏等人又提出了基于部分隐藏的随机化回答方法r r p h t 6 1 ，该方 法将数据干扰和查询限制两种策略相结合，算法是在挖掘之前对原始数据同时进 行变换和隐藏，对随机参数的选择也没有任何限制，并给出了一种简单而又高效 的频繁项目集生成算法，从而实现了关联规则挖掘中隐私数据的保护。 由此可见，对于隐私数据的保护问题，目前常用的方法是是采取数据干扰技 2 江苏大学硕士学位论文 术0 1 ，即通过数据变换或在数据中增加噪声等方法来对原始数据进行干扰，关 联规则挖掘是在干扰后的数据集上进行的，因而，该种方法很有可能影响到关联 规则挖掘结果的可用性和有效性，即有可能挖掘出一些原始数据库中本来不存在 的且有误导作用的规则，丢失一些原始数据库中存在的且非常有用的规则，从而 失取了数据挖掘本身的价值。其实，隐私数据是相对的，是与载体相关联的，更 换了或脱离了载体，数据就有可能失去其物理意义或敏感性。如何在不精确访问 原始数据集的条件下，尽量的准确地发现其巾的频繁项集，用于产生支持度与置 信度不低于用于给定阂值的关联规则。因此，通过交换记录之间的项目来实现隐 私数据项保护的方法具有较高的学术价值和广泛的应用前景。本文中的算法将首 先进行记录之问项目交换技术的研究，一方面实现隐私数据的有效保护，另一方 面确保关联规则挖掘结果的有效可行性。 1 2 2 关联规则挖掘中敏感规则保护的国内外研究现状 对于关联规则挖掘中的敏感规则保护问题，a l g o l a l l 、a l g o l b l l 、a l 9 0 2 a ! 。、 a l 9 0 2 b | 12 1 、a l 9 0 2 c 1 1 2 1 、n a i v e l l3 1 、m i n f i a 13 1 m a x f i a l l 3 1 、i g a l l 引、r r a 。4 1 、r a t l4 1 、 等启发式算法先后被提出。算法a l g o r i t h m l a 通过增加敏感关联规则左件的支持 度来降低其置信度，直至其置信度小于最小置信度阂值。算法a l g o r i t h m l b 通过 降低敏感关联规则右件的支持度来降低其支持度或置信度，直至其支持度小于最 小支持度阈值或置信度小于最小置信度阈值。算法a l g o r i t h m 2 a 、a l g o r i t h m 2 b 、 a l g o r i t h m 2 c 均是通过降低生成敏感关联规则的频繁项目集的支持度来隐藏敏感 关联规则，直至频繁项目集的支持度小于最小支持度阂值。文献i l3 】引入了冲突 度的概念来降低支持度，可以隐藏有交集项的敏感规则。 s a y g i nv 等人提出了一种基于不确定性的敏感关联规则隐藏方法，该方法将 敏感关联规则的支持度或置信度落入了一个不确定区间，从而达到隐藏的目的， 如：算法g i h l l5 1 、c r 15 1 、m c r l l 6 1 、i s l l l7 1 、d s r l l 7 】等。算法g i h 通过降低生成 敏感关联规则的频繁项目集的支持度区间下界来隐藏敏感关联规则。算法c r 通 过降低生成敏感规则的频繁项目集的支持度来降低关联规则的阈值区间下界，从 而达到隐藏敏感关联规则的目的。a g r a w a lr 等人在文献【1 8 】中提出了一种基于 随机变换的隐私保护关联规则挖掘方法，该方法通过数据干扰和分布重构来实现 隐私保护的关联规则挖掘。郭宇红等人在文献【1 9 】中提出的一种基于f p t r e e 的 3 江苏大学硕士学位论文 反向频繁项目集挖掘方法，借助于设计良好的启发式规则，从频繁项目集中快速 找到一个近似满足频繁项目集约束的f p t r e e ，然后由f p t r e e 快速生成满足目标 约束的数据库，理想情况下，目标数据库中将不再包含敏感关联规则，有效保护 了敏感关联规则。 由此可见，自从m a t a l l a h 等人首次提出隐私保护关联规则挖掘以来，在敏 感关联规则保护方面已取得了一些重要研究成果。纵观这些研究成果所采用的方 法，我们可以将其分为四类：数据抽样法、数据重构法、数据扰乱法和数据阻塞 法。数据抽样法是统计学经常使用的一种技术，抽样样本的代表性和广泛性永远 是一个难以解决的问题。对于基于数据重构法的敏感关联规则保护而言，一方面 它仍缺乏十分有效的反向频繁项目集挖掘算法，另一方面，该方法难以解决有关 原始数据及敏感关联规则的更新问题。因而，数据扰乱法和数据阻塞法是隐私保 护关联规则挖掘研究中的两类主要方法，该两类方法的执行过程包括：数据 库表示形式的改变，将原数据库中的每条记录转换成二进制标记形式的记录，生 成二进制标记形式的数据库；待修改敏感记录以及待修改牺牲项的确定，并 进行相应变换，数据变换法是将待修改敏感记录中的待修改牺牲项所对应的位值 取反，即原来为1 则改为o ，原来为o 则改为1 ，数据阻塞法则将其变成“? ”，? 表示0 或l ；非敏感关联规则的挖掘，将修改后的二进制标记形式数据库置 换成一个新的结果数据库，在该结果数据库上进行关联规则的挖掘。其中，第 步是重点，也是难点，即待修改敏感记录及待修改牺牲项的确定是隐私保护关联 规则挖掘技术研究中的难点和重点。对于待修改敏感记录的确定问题，目前所采 用的方法有：随机轮转法。采取随机轮转的方式来选择待修改敏感记录，如 算法a l g o r i t h m 2 c 等；最短优先法。每次选择最短的敏感记录作为待修改敏 感记录，如算法a l g o r i t h m 2 a 、a l g o r i t h m 2 b 等；冲突度最小优先法。每次选 择冲突度最小的敏感记录作为待修改敏感记录，如算法n a i v e 、m i n f i a 、m a x f i a 等；冲突度最大优先法。每次选择冲突度最大的敏感记录作为待修改敏感记 录，如算法i g a 、r a 、r r a 等。对于待修改牺牲项的确定问题，大致可以有以 下几种方法：随机轮转法。采取随机轮转的方式来选择待修改牺牲项，如算 法a l g o r i t h m 2 c 、r r a 、r a 等；支持度最低首项优先法。每次选择支持度最 低子集中的第一个项目作为待修改牺牲项，如算法a l g o f i t h m 2 a 等；支持度 4 江苏大学硕士学位论文 最高优先法。每次选择支持度最高的项目作为待修改牺牲项，如算法 a l g o r i t h m 2 b 、m a x f i a 等；全部删除法。每次选择待修改敏感记录所包含的 所有项目作为待修改牺牲项f 1 集，一次全部删除这些项目集，如算法n a i v e 等； 支持度最低优先法。每次选择待修改敏感关联规则所包含的支持度最小的项 目作为待修改牺牲项集，如算法m i n f i a 等。 上述这些方法都是基于启发式思想的数据变换方法，其优点是操作简单，每 次的计算代价小，只需根据启发式规则直接选择待修改敏感记录和待修改牺牲项 即可，其缺点是算法在定性规则而非定量指标的引导下进行的，关联规则隐藏或 保护的实际效果只有等算法执行完后才能得以验证和确认。为此，2 0 0 4 年， d a s s e n i e 最先提出了通过降低敏感规则的支持度和置信度来达到隐藏敏感规则 目的方法1 1 2 1 ，其优点是操作简单，每次的计算代价小，其缺点是算法在定性规 则而非定量指标的引导下进行的。针对于此，l e eg ，w a n ge t 等人提出了基于清 洗矩阵的数据转换法1 2 0 2 n ，s u nx 等人提出了基于项集格边界的贪心算法【2 2 1 ， m e n o ns ，v e r y k i o sv s 等人提出了用于隐藏敏感项集的全局最优化方法【2 3 , 2 4 j ，这些 方法将定量评估引入到算法的执行过程中，定义测度函数并通过计算测度函数的 值来估算当前状态下删除一个项目对非敏感频繁项集边界的影响，算法选取对边 界影响最小的敏感记录和项目进行清洗，以保证非敏感频繁项集尽可能小地受 到影响，确保结果数据库中非敏感频繁项目集的数量和相对频繁度得到最大程度 的保留。对于算法中测度函数值的计算问题，他们所采用的方法是枚举法，即 首先一个一个的求出候选待修改敏感记录及候选待修改牺牲项的测度函数值， 然后取出他们中的最小值。一般情况下，候选待修改敏感记录和候选待修改牺牲 项的规模十分巨大，可想而知，其运算量也非常巨大，有时甚至无法完成相 应的计算工作。其实，计算所有测度函数值的最终目的是寻找候选待修改敏 感记录以及候选待修改牺牲项中测度函数值最小的那个组合，即求出其最优解。 对这类复杂的问题，人们已经意识到应把主要精力放在寻求其满意解上， 而遗传算法是寻求这种满意解的最佳工具之一。遗传算法应用于优化问题时， 是一个启发式随机搜索过程，与其它的启发式算法比较，遗传算法不仅在搜索空 间上具有很好的全局搜索能力，而且能充分利用己获得的解空间信息逼迫当前局 部最优解。 江苏大学硕士学位论文 目前遗传算法在关联规则挖掘中的应用主要是集中在对关联规则的提取方 面1 2 5 2 7 1 ，已提出了一些基于遗传算法的关联规则挖掘方法，如：a r m a g a l 2 8 1 、 f - a p a c s l 2 9 1 、d m a r g 3 0 1 等，算法将遗传算法与关联规则挖掘算法相结合，提 取感兴趣的规则并且对规则进行优化、预测。但是将遗传算法应用到关联规则挖 掘中敏感规则保护方法方面的研究还较少。m o h a m m a dn a d e r id e h k o r d i 等人在文 献【3 2 l 中提出了一种基于遗传算法的敏感规则隐藏算法，文中提出了四种适应度 策略来对数据库中的敏感规则进行隐藏。 1 3 本文的研究内容 本文主要研究关联规则挖掘中的隐私保护问题，分别对数据库中隐私数据的 保护和敏感规则的隐藏进行研究，并提出了改进方案，并根据研究结果设计并实 现了关联规则隐私保护数据挖掘原型系统，具体研究内容包括： 1 、介绍了关联规则挖掘中隐私保护的相关知识。对典型的隐私保护算法进 行了分析介绍。 2 、深入分析了关联规则挖掘中典型的隐私数据隐藏算法，针对现有隐私数 据保护方法很有可能影响到关联规则挖掘结果的可用性和有效性等问题，提出了 一种基于数据交换技术的隐私数据保护算法a p p d a r m ，并给出了相应的数据交 换实现方法，实验证明该方法是可行有效的。 3 、针对现有敏感规则隐藏算法中的问题，结合遗传算法思想，提出了一种 基于遗传算法的敏感规则隐私保护算法g a s r p ，给出了算法的流程和具体的操 作过程。通过实验验证g a s r p 不仅能够有效将敏感规则进行隐藏，而且对非敏 感规则丢失以及虚假规则的产生影响都较小。 4 、以提出的a p p d a r m 算法和g a s r p 算法为基础，使用c + + 语言，设计 并实现了一个基于隐私保护的关联规则挖掘原型系统。 1 4 本文结构 本文共分五章，各章节具体安排如下： 第一章绪论 阐述所选课题的研究背景及意义，分析了关联规则挖掘中隐私保护技术的国 6 江苏大学硕士学位论文 内外研究现状，总结了本文的主要研究工作。 第二章关联规则隐私保护及遗传算法概述 介绍关联规则隐私保护的基本知识及隐私保护算法思想，着重介绍了当前流 行的隐私数据保护以及敏感规则保护的算法，并对这些算法进行了简要的分析， 同时还介绍了遗传算法的相关知识。 第三章关联规则挖掘中隐私数据的保护方法 在对现有关联规则巾隐私数据保护算法研究的基础上，针对现有方法很有可 能影响到关联规则挖掘结果的可用性和有效性等问题，提出了一种基于数据交换 技术的隐私数据保护算法a p p d a r m ，详细介绍了a p p d a r m 算法的思想和流 程。 第四章基于遗传算法的关联规则隐私保护研究 将关联规则隐藏算法与遗传算法相结合，提出了一种有效的基于遗传算法的 。关联规则隐私保护算法，该算法通过对适应度函数的有效设计，对交叉算子、变 异算子等参数的有效选择，来达到对敏感规则进行有效隐藏的目的，并详细描述 了算法流程以及相关参数的没定。 第五章关联规则隐私保护挖掘系统设计与实现 对隐私保护的关联规则挖掘系统在实现中的关键点和难点进行了分析，重点 介绍了原始数据库的预处理和隐藏敏感规则的数据预处理过程，给出了两个子系 统的详细设计思想，并给出了系统的运行情况。 第六章总结与展望 总结本文的研究工作，根据自己的研究成果和体会，确定下一步研究工作的 重点及方法。 7 江苏大学硕士学位论文 第二章关联规则隐私保护及遗传算法概述 本章首先介绍关联规则挖掘和关联规则挖掘中隐私保护的基本知识，然后阐 述了几种主流的关联规则挖掘中隐私数据保护和敏感规则保护算法，最后介绍了 遗传算法的基本思想、特性、参数设置等知识。 2 1 关联规则相关知识 关联规则挖掘是数据挖掘中最活跃的研究方向之一，它是由r a k e s h a g r a w a l 等人首先提出的一个重要的k d d 研究课题1 3 ，它反应了大量数据中项目之间有 趣的关联或相关联系。关联规则的数据挖掘在商业等领域的成功应用，使它成为 数据挖掘中最成熟、最主要、最活跃的研究内容。 关联规则挖掘中的一个比较经典例子是购物篮分析，通过关联规则挖掘算法 来对客户的事务执行购物篮分析，可以知道哪些是热销产品，以及某一特定产品 与另一产品一起被购买的可能性有多大。随着大量数据不停地被收集和存储，决 策者对从数据库中挖掘关联规则越来越感兴趣。发现这样的规则可以帮助他们进 行商务决策制定，如改变产品的布局来增加销售、目录分析、库存管理，以及根 据顾客购买模式对用户进行分类。 2 1 1 基本概念 设i = i l ，i 2 ，i m ) 是由r n 个不同项目组成的集合，d 是交易或事务数据库， 其中每一个交易或事务t 是i 中一组项目的集合，即t c _ i 。每一个交易或事务t 都与一个唯一的标识符t 1 d 相联。对于项目集x i ，如果x c _ t ，则交易或事务 t 支持x 。如果x 中有k 个项目，则又称x 为k 项目集，或x 的长度为k 。 关联规则是指形如x _ y 的数据隐含关系，其中x c _ i ，y c _ i ，且x n y 。 定义2 1 ：项目集x 的支持数( 度) 。事务数据库d 中支持项目集x 的事务数 称为项目集x 的支持数，记为c o u n t ( x ) 。设事务数据库d 中总的事务数为l d i ， 则项目集x 的支持度为：c o u n t ( x ) i d i ，记为s u p ( x ) 。 8 江苏大学硕士学位论文 定义2 2 ：d 是事务数据库，x 是一个项集。如果项集x 在事务数据库d 中 支持度不小于用户指定的最小支持度( m i n s u p ) ，则称项集x 为一个大项集或者频 繁项目集：否则称项集x 小项集或者为非频繁项目集。 定理2 1 ：设x 、y 是数据集d 中的项目集： ( 1 ) 若x c y ，则s u p ( x ) s u 【p ( 1 i r ) 。 ( 2 ) 若x y ，如果x 是非频繁项目集，则y 也是非频繁项目集。 ( 3 ) 若x y ，如果y 是频繁项目集，则x 也是频繁项目集。 定义2 3 ：关联规则x _ y 的支持数( 度) 。事务数据库d 中支持项目集x u y 的事务数称为关联规则x y 的支持数，记为c o u n t ( x - - - ，y ) 。x _ y 的支持度为： c o u n t ( x - , y ) i d i ，记为s u p ( x - * y ) 。 定义2 4 ：关联规则x y 的置信度。关联规则x _ y 的置信度定义为： c o u n t ( x - - - y ) c o u n t ( x ) ，记为c o n f ( x - - * y ) 。 为了挖掘出有意义的关联规则，一般需要给定两个阂值：最小支持度( m i n s u p ) 和最小置信度( m i n c o n f ) 。前者表示了一组数据集在统计意义上所需满足的最低要 求，后者反映了用户对关联规则的最低置信度。 2 1 2 关联规则的分类 我们将关联规则按不同的情况进行分类f 3 3 l ： ( 1 ) 按照规则中处理的变量类别 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型 关联规则处理的值都是离散的、种类化得，它显示的是这些变量之间的关系；而 数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处 理，将其进行动态的分割，或者直接对数据进行处理，当然数值型关联规则中也 可以包含种类变量。 ( 2 ) 按照规则中数据的抽象层次 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单 层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的；而在多层的关联规则中，对数据的多层性以及进行了充分的考虑。 ( 3 ) 按照规则中涉及到的数据维 9 江苏大学硕士学位论文 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单 维的关联规则中，我们只涉及到数据的一个维，即处理单个属性中的一些关系， 如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维，即 处理各个属性之间的某些关系。 2 1 3 关联规则挖掘 关联规则挖掘的任务是：在给定的交易或事务数据库d 中，发现d 中所有 的频繁关联规则。所谓频繁关联规则是指其支持度、置信度分别不低于用户给定 的最小支持度和最小置信度阈值的项目集。 通常，关联规则挖掘的过程可以分为以下两步： 第l 步：从事务数据库d 中找出所有频繁项目集，所谓频繁项目集是指其 支持度不小于用户给定的最小支持度阈值m i n s u p 的项目集，或其支持数不小于 用户给定的最小支持数阈值m i n c o u n t 的项目集； 第2 步：根据第1 步发现的频繁项集，产生置信度不低于用户指定的最小置 信度阈值的关联规则。 可以看出，第2 步是在第l 步结果的基础上进行的，而与原始数据库d 无 关，所以在关联规则挖掘中隐私的保护的关键是第一步。 2 2 关联规则隐私保护 2 2 1 关联规则挖掘中隐私数据的保护 隐私数据是指数据库拥有者不愿公开的项目，又称隐私数据项，如银行数据 库中客户的个人信息、商业数据库中顾客的喜好和收入等。关联规则挖掘中隐私 数据的保护问题是指通过一定的