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

摘要 摘要 数据挖掘研究如何从大量数据中发现潜在模式及趋势，在科学研究、医学研究及商 业等领域，正得到越来越广泛的应用，具有很大的发展潜力。由于数据挖掘是发现数据 中不容易发现的模式和规律，如果干4 用不当，可能对隐私和信息安全构成威胁。因此， 如何在保证隐私的情况下挖掘出有用的信息是近年来数据挖掘领域研究的热点之一。 本文首先结合数据分布方式、隐私保护目标和隐私保护技术和隐私保护的对象等 多个角度，对当前流行的隐私保护关联规则挖掘方法进行了深入浅出的分析和介绍。 其次，论文主要针对隐私保护关联规则挖掘提出相关的两个算法： ( 1 ) 从隐私保护对象为原始数据集的角度出发，总结r i z v i d 提出的的m a s k 算法优 缺点的基础上，提出了一个基于多参数随机扰动的布尔规则挖掘算法d m a s k 。该 算法同m a s k 算法相比，能够按照用户对隐私关注不同设置不同的扰动参数，从 而降低了隐私泄露的可能性。通过合理的参数设置同时满足挖掘结果的准确度 和隐私保护度。另外，我们利用集合原理对算法实行优化，并且严格控制数据集 密度的变化，消除了由于扰动引起的额外计算，从而大大提高程序运行效率。 我们分别在人工数据集( i b ms y n t h e t i cd a t a s e t ) 和实际数据集 ( b m s w e b v i e w 一1 ) 运行该算法，实验结果表明d m a s k 算法在运行时间上比 a p r i o r 减慢少于5 倍，同时能够保证隐私保护度在7 0 以上，挖掘结果的准确度 在9 0 以上。 ( 2 ) 从隐私保护对象为敏感模式的角度出发，针对0 1 i v e r i r a 提出的s w a 算法中容 易因推导而产生隐私泄露的不足，提出了一个新颖算法r w a 。首先根据敏感模式 和非敏感模式之间的关系建立扰动矩阵，设置矩阵中合适的值，并将原事务数 据集与扰动矩阵相乘，生成一个能够阻止向前推导攻击扰动数据集。另外，我 们使用不同的扰动参数来避免敏感规则被恢复以及降低非敏感规则被隐藏的机 率，更能避免入侵者向前推导所引起的隐私泄露。最后我们利用实验方法，通过 与s w a 算法在敏感模式的隐藏、非敏感规则的丢失以及运行时间等多个性能指 标上进行比较，结果表明我们所提出的算法相对于s w a 具有良好的性能同时具 有更安全的保护 关键词：数据挖掘关联规则隐私保护敏感模式随机扰动 频繁模式 扰动矩阵支持度置信度 江南大学硕士学位论文 a b s t r a c t d a t ai i l i n i n gt e c h n o l o g yh a se m e 唱e da sam e a n so fe x a c t i n gp o t e n t i a lp a t t e m so r k n o w l e d g e 行o ml a 唱eq u a i l t i t i e so fd a t aa n di sb e c o i i l i n gw i d e l yu s e di nm a n yf i e l d s ，s u c ha s s c i e m i f i cr e s e a r c h ，m e d i c a lr e s e a r c ha i l db u s i n e s s h o w e v e r ，d a t a1 1 1 i n i n gw i t hi t sn a t u r et o e m c i e n t l y d i s c o v e rv a l u a b l e ， n o n o b v i o u sp a n e m sa n dm l e s 行o mm a s s i v ed a t a ，i s p a n i c u l a l l yv u l n e m b l et or i l i s u s eo ra b u s e 蹦v a c yp r e s e r v i n gi nd a t ai i l i n i n gh a sb e e n c o n s i d e r e dav i t a lf a c t o ra sf o rh o wt oo b t a i ng l o b a l l yv a l i dd a t ar n i n i n gr e s u l t sw i m o u t r e v e a l i n ga i l yu i l n e c e s s a r yi n f o 衄a t i o no ft l l es i t e s t h e r e f o r e ，p r i v a c ya n ds e c l l r i t yh a s b e c o m em ef o c u so f m a l l yd a t ai i l i i l i n gr e s e a r c h e s t h e p a p e rf i r s ti n 廿o d u c e sa n da 1 1 a l y z e ss o m et y p i c a lp r i v a c yp r e s e r v i n ga s s o c i a t i o nr u l e s a l g o r i t l l m sf 而md 破ad i s 埘b u t i o n ，d a t am o d i f i c a t i o n ，h i d i n go b j e c t sa n dp r i v a c yp r e s e r v i n g t e c l l n o l o g yd i m e n s i o n s t h e n ，t l l ep a g e rp r e s e m st w oa l g o r i t h m sa b o u tp r i v a c yp r e s e r v i n g a s s o c i a t i o nr u l e si i l i l l i n g ( 1 ) t & k i n gp r e s e r v i n gp r i v a c yo ft | l ed a t am i i l i n gt a 唱e ta sm eo n g i n a ld a t a s e ta n d s u m m a d z i n gm ea d v a n t a g ea n dd i s a d v a n t a g eo fr i z v i d sm a s k ，t h ep a p e ri n t r o d u c e s ab o o l e 柚r u l em i n i n ga l g o r i t h m d m a s k ，w h i c hi sb a s e do nm u l t i f a c t o rr a n d o m p e n u r b a t i o n c o m p a r e dw i t l lm a s k ，d m a s k c a np m v i d ec o r r e s p o n d i n gs e t t i n g so f p e r t u r b a t i o nf a c t o r sa c c o r d i n gt ou s e r sr e q u i r e m e n t so fp r i v a c yt h e r e f o r e ，i tr e d u c e s t h ep o s s i b i l i t yo f b r e a c h i n gp r i v a c ym e a i l w h i l e ，w i t hp m p e rf a c t o r s ，t h ea c c l l r a c ya n d p r i v a c yp r e s e “i n ga r eb o m a c h i e v e d i na d d m o n ，b yu s i n gs e tt l l e o r y ，w ec a i lo p t i i i l i z e t l e a 1 9 0 r i t h m ， c o n d lt h ev a r i a t i o no fd a t a s e td e n s i ty ，a n de l i m i n a t er e d u n d a i l t c o u n t i n go v e r h e a dc a u s e db yt h ep e r t u r b a t i o n a sar e s u l t ，t h ee f f i c i e n c yo fe x e c u t i o n i si m p m v e ds i g n i f i c a n t l y a l g o r i t h md m a s kh a sb e e ne x e c u t e di ni b ms y i l t h e t i c d a t a s e ta n db m s w e b e w 一1d a t a s e t c o 埘【p a r e dw i t ha p o r i o r ，d m a s kh a sl e s s t h a n4t i m e se x e c u t i o nt i m e m e a n w h i l e ，i tc a ng u a r a n t e e7 0 + o f p r i v a c yp r e s e r v i n g a n d9 0 + o f a c c u r a c y ( 2 ) t a b n gp r i v a c yp r e s e r v i n go ft h eo w n e ro ft h eo r i g i n a ld a t a s e ta st h es e n s i t i v ep a t t e m s a i l d r e s p o n d i n g t of o 九a r d h f e r e n c ea t t a c kd r a w b a c ko ft h es w aa l g o r i t h m p r e s e n t e db y0 l i v e r i m ，m ep a p e ri n t r o d u c e san e wa l g o r i t l l i n f i r s t l y b a s e d0 nt h e r e l a t i o n s h i pb e t w e e ns e n s i t i v ep a t t e 丌l sa n dn o n s e n s i t i v ep a t t e m s ，ap e r c u r b a t i o n m a 砸xi s e s t a b l i s h e d t h e n ， b ys e t t i n g t l l ee n t r i e st o a p p m p r i a t e v a l u e sa n d m u l t i p l y i n gt h eo r i g i n a lt r a l l s a c t i o nd a t a s e tw i t ht h ep e r t u r b a t i o nm a t r i x ，ap e r n l r b e d d a t a s e tw h i c hc a np r e v e n tf o n v a r d i n f e r e n c ea t t a c ki sc r e a t e d m o r e o v e r ，w eu t i l i z e s o m ed i 能r e n tp e n u r b a t i o nf a c t o r st oa v o i dt h er e c o v e r yo fs e n s i t i v ep a t t e m s ，a 1 1 dt o r e d u c et h ep m b a b i l i t yo fh i d i n gn o n s e n s i t i v ep a t t e m s f i n a u y ，b ye x p e r i m e n t ，w e i i a b s b r a c t c o m p a r eo u ra l g o 订m mw i ms w a i nt e 珊so fs o m ep e r f b n n a n c em e 砸c ss u c ha s h i d i n gn o n s e n s i t i v e ，1 0 s so fn o n s e n s i t i v ep a t t e m sa n dm n n i n gt i m e ns h o w st i l a to i l r a l g o r i t h mp m v i d e ss a f e rp r o t e c t i o n sm a i ls w a k e yw o r d s ： d a t a r n i n i n g ，a s s o c i a t i o nr u l e ，p r i v a c yp r e s e r v i n g ，s e n s i t i v ep a t t e m ， r 柚d o m 【yp e 咖r b a t i o n ，s u p p o r t ，c o n f i d e n c e ，p e r t u r b a t i o n m a t r i x i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： f 乱 1 日期：p c 年，月w 日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：杠导师签名：。 日期：卜b年f 月”日 第一章引言 第一章引言 在本文中，我们讨论数据挖掘中保持隐私性的问题。随着数据库技术和网络技术 的发展，各行各业都积累了大量有用数据，如何从这些数据中提取出对决策有价值的知 识，成为当务之急。数据挖掘作为一个强有力的数据分析工具，可以发现重要的数据模 式，在商务决策、科学和医学研究等领域做出了巨大的贡献，具有广泛的应用前景。但 是，因为数据挖掘揭示不容易发现的模式或知识，如果不正确使用的话，可能对隐私和 信息安全构成威胁。因此如何保护私有信息或敏感信息在挖掘过程中不被泄露就成为数 据挖掘研究中的一个很有意义的研究课题。 1 1 数据挖掘概述 数据挖掘是二十世纪9 0 年代兴起的一项新技术，是人工智能，数据库和统计理论 的结合技术，涉及机器学习、统计学、模式识别、数据可视化和专家系统等领域。随着 信息技术的发展，快速增长的海量数据收集、存放在大型和大量数据库中。但是，人们 分析数据和从中提取有用信息的能力还远远跟不上数据的爆炸式增长，从而造成了“数 据丰富，但信息贫乏”的局面。在这种情形下，人工智能，数据库和统计理论的结合和 发展，促成了知识发现( k d d ) 这一新技术的诞生。1 9 8 9 年8 月，在美国召开的第1 l 届国 际人工智能联合会议的专题讨论会上，首次提出了k d d 的概念。1 9 9 5 年，美国计算机学 会( a c m ) 会议上提出了数据挖掘( d a t am i n i n g ) 的概念。现在多数人认为数据挖掘是知识 发现过程中的关键步骤，从而不加区分地使用知识发现和数据挖掘这两个术语。 数据挖掘是一门研究从大量的数据中提取隐含的、未知的、对决策有潜在价值的知 识和规则的学科。数据挖掘任务一般可以分为描述和预测两类。描述性任务用来刻画所 挖掘数据的一般特性。预测性任务在当前数据上进行推断，以进行预测。数据挖掘技术 一般包括关联分析、分类和预测、聚类分析、孤立点分析、演变分析及w e b 文本挖掘方 法等几个方面。数据挖掘的目的是从数据中找出有意义的模式。模式可以是一组规则， 聚类，决策树，依赖网络或其他方式表示的知识。 一般来说，一个典型的数据挖掘过程可以分成四个阶段，即数据预处理，建模，模 型评估及模型应用。数据预处理阶段主要包括数据的理解，属性选择，连续属性离散化， 数据中的噪声及丢失值处理，实例选择等。建模包括学习算法的选择，算法参数的确定 等。模型评估进行模型的训练和测试，对得到的模型进行评价。前三个阶段是循环往复 的过程。直到得到用户满意的模型为止。在得到满意的模型后，就可以运用此模型对新 数据进行解释。数据挖掘过程是交互的和领域相关的，需要用户特别是相关领域专家的 参与。 江南大学硕士学位论文 1 2 信息隐私权的发展 任何事情都有其两面性，数据挖掘领域也不例外，在挖掘数据产生财富的同时，随 之产生的就是隐私泄露的问题。“隐私权”最早在1 8 9 0 年1 2 月美国人沃伦和布兰代斯 所写的隐私权中被正式定义，“隐私权”界定为“生活的权利”和“不受干扰的权 利”。他们两入认为，隐私权本质上是一种个人对其自身事务是否公开给他人的权力， 保护个人的隐私权就是保障个人的“思想、情绪及感受”不受他人打扰的权力，保护自 己人格不受侵犯的权力。到2 0 世纪6 0 年代，隐私权的观念逐渐为美国法律界所熟悉， 但隐私权的内容为何，却始终未见有明确的界定。1 9 6 0 年，w i l l i a ml p r o s s e r 教授 在加州法律评论上发表了隐私一文，试图就隐私权的内容做一归纳。根据他的 整理，法律上的隐私权侵害应包含四种侵权行为，这四种类型的侵害包括：对他人私生 活隐私权的侵害：公开他人的姓名、肖像或揭发其他不愿为他人所知悉的私人信息：使他 人处于人为误鼹情况：基于商业上的目的，侵犯他人人格。 由于计算机处理能力、存储技术以及互联网络的发展，使得电子化数据急剧增长， 这样传统上对隐私权保障的思考，就必须转向以“数据保护”为重心的思路上，于是就 出现了“信息隐私权”的概念，以应对信息时代隐私权所受到的冲击。如由于工作、生 活、学习的关系，人们要在政府、学校、银行、医院、警察、司法机关、工作单位等地 方留下个人资料和信息，这些资料都被存入了计算机，彼此传递运用，只要键入身份证 号码后，就可将一个人所有资料一览无遗，而这些都与人格、尊严、隐私有着密切的关 系。国外已经发生了多起由于个人信息泄密，而造成个人账号被冒用的例子，以及由于 个人电话号码被一些机构出卖，而遭到一些中介、盈利机构频频骚扰的例子，所以说信 息时代的隐私权保护要比传统的隐私权保护重要的多。信息隐私权保护的客体可分为以 下四个方面。 1 ) 个人属性的隐私权：如一个人的姓名、身份、肖像、声音等，由于其直接涉及个人领 域的第一层次，可谓是“直接”的个人属性，为隐私权保护的首要对象。 2 ) 个人资料的隐私权：当个人属性被抽象成文字的描述或记录，如个人的消费习惯、病 历、宗教信仰、财务资料、工作、犯罪前科等记录，若其涉及的客体为一个人，则这 种资料即含有高度的个人特性而常能辨识该个人的本体，可以说“间接”的个人属性 也应以隐私权加以保护。 3 ) 通信内容的隐私权：个人的思想与感情，原本存于内心之中，别人不可能知道：当与外 界通过电子通信媒介如网络、电子邮件沟通时，即充分暴露于他人的窥探之下，所以 通信内容应加以保护，以保护个人人格的完整发展。 4 ) 匿名的隐私权：匿名发表在历史上一直都扮演着重要的角色，这种方式可以保障人们 愿意对于社会制度提出一些批评。这种匿名权利的适度许可，可以鼓励个人的参与 感，并保护其自由创造力空间：而就群体而言，也常能由此获利，真知直谏的结果， 第一章引言 是推动社会的整体进步。 1 3 数据挖掘中的隐私问题 前面我们已经讨论数据挖掘领域也存在隐私泄露的问题，在数据挖掘领域，隐私被 划分为两类：一类隐私是原始数据本身具有的。由于传统的数据挖掘技术是基于未加密 过的原始数据来进行的，也就是说必须将包含个人企业隐私的原始数据交给数据挖掘 者才能挖掘出有用的知识，如个人的家庭电话、银行账号、财产状况、信用等级等信息， 这些信息一旦泄露的活，极可能会对个人的生活产生不良影响。另一类隐私是原始数据 所隐含的知识，如某公司优质客户的行为特征等规则，这些知识如果被别有用心的人非 法获得，将会严重影响企业的核心竞争力。 在这种情况下，人们会不会由于担心隐私被泄露而拒绝提供任何信息资料呢? 为了 了解人们对隐私保护的态度，1 9 9 9 年对网上用户作了一个调查 1 3 ，结果表明：在响应 者中，1 7 的网上用户是正统的隐私保护主义者，他们即使在采取保护隐私的措施下也 不愿意提供自己的真实信息：5 6 的网上用户是实用主义者，在采取保护隐私的措施下， 他们提供真实信息的可能性大大提高：其余的2 7 的网上用户虽然也考虑隐私，但还是愿 意提供自己的真实信息。 该调查说明，人们并没有因噎废食，在数据挖掘能够提供的益处面前，只要数据采 集者采取措施保证个人的隐私，大部份人还是愿意参与调查并提供自己的隐私数据。同 时也说明保护隐私程度的高低将直接关系到是否能够收集到足够真实的信息，从而关系 到挖掘出来的信息是否可靠有用。 在1 9 9 5 年召开的第一届k d d 上，隐私保护的数据挖掘就成为了一个专门的研究主 题。1 9 9 9 年r a k e s ha g r a w a l 在k d d 9 9 上作了一场精彩的主题演讲“。 将隐私保护的数据挖掘作为未来的研究重点之一。自此以后，隐私保护的数据挖掘越来 越得到人们的重视，迅速成为近年来数据挖掘领域研究的热点之一。各种新方法和新技 术层出不穷，v a s s i l i o ss v e r y k i o s 在文献。“，从数据分布方式、数据修改方法、数 据挖掘算法、隐私保护的对象和隐私保护技术五个角度对现有的一些隐私保护数据挖掘 算法作了一个归纳。 1 ) 数据分布方式：有的是研究集中式数据，有的是研究分布式数据。分布式又分为水 平分布和垂直分布两种，水平分布指数据按记录分布在不同的站点，垂直分布指数 据按属性分布在不同的站点。 2 ) 数据修改方法： a ) 按不可倒推的方法修改数据为一个新值： b ) 用“? ”来替代存在的值，以保护敏感数据和规则； c ) 合并或抽象详细数据为更高层次的数据； d ) 对数据进行抽样； 江南大学硕士学位论文 3 ) 数据挖掘算法：适用于不同知识的挖掘算法，如分类、关联规则、聚类等； 4 ) 隐私保护的对象二即隐藏原始数据或其隐含的规则。规则比原始数据的层次要高， 通过保护敏感规则，同样可以保护重要的原始数据： 5 ) 隐私保护技术：即修改数据所采用的技术。 a ) 启发式技术：通过仅仅修改特定值、而非全部值来减少挖掘效果的失真； b ) 密码技术：采用密码学技术来进行数据加密，如多方安全计算： c ) 重构技术：从变换后的数据中恢复原有数据的分布： v a s s i l i o ss v e r y k i o s 同时也提出了对各类隐私保护算法的评估标准： 1 ) 性能：计算开销，以及分布式环境下的通讯开销； 2 ) 算法精度：与非隐私保护的同类算法相比，其判断精度、丢失比率和误生成比率 3 ) 隐私保护程度：防止原始数据或其隐含的知识被推导出的程度； 4 ) 通用程度：适应各种数据挖掘技术的程度； 1 4 论文完成的主要工作 本论文主要说明了作者在隐私保护数据挖掘方面的研究，本文的主要内容如下： 对目前该领域的研究现状从隐私保护对象的角度和采用的技术进行了分类，同时对 于隐私保护的关联规则从数据分布方式的角度进行了深入的介绍和分析。 论文从隐私保护对象为原始数据集的角度出发，提出了一种多参数随机扰动的布尔 规则挖掘的算法：首先介绍了典型的m a s k 算法，并提出了隐私保护的衡量标准，在此 基础上详细介绍了多参数随机扰动算法，其中包括多参数的扰动过程和挖掘过程，以及 如何优化算法。最后在人工数据集和实际数据集上分别实施d m a s k 算法，对实验结果 进行数据分析，得出相应的结论。 从隐私保护对象为敏感模式的角度出发，针对o l i v e r i r a 提出的s w a 算法中容易因 推导而产生隐私泄露的不足，提出了一个新颖的r w a 算法。首先根据敏感模式和非敏感 模式之间的关系建立扰动矩阵，将数据集与矩阵相乘即可得到扰动后的数据集。我们的 研究重点是如何使得扰动后的数据集可以隐藏敏感规则，更能避免入侵者向前推导所引 起的隐私泄露。另外，我们提出了通过设置不同的扰动参数来避免敏感规则被推导的可 能性以及降低非敏感规则被隐藏的机率。最后我们利用实验方法，通过与s w a 算法在敏 感模式的隐藏、非敏感规则的丢失以及运行时间等多个性能指标上进行比较分析。 1 5 论文的组织形式 本文按如下方式进行组织： 第一章介绍了当前隐私保护关联规则挖掘的研究背景及其研究现状。 第二章介绍了隐私保护数据挖掘综述。 第一章引言 第三章是针对m a s k 算法，总结其不足，提出了多参数随机扰动的布尔规则挖掘算 法d m a s k 。详细分析了扰动过程和重构过程。最后在人工数据集和实际数据集上分别实 施d m a s k 算法，对实验结果进行数据分析，得出相应的结论。 第四章是针s w a 算法中容易因推导而产生隐私泄露的不足，提出了一个新颖的r w a 算法。分别介绍了扰动矩阵的设置以及如何通过矩阵相乘来获得扰动后的数据集，并将 实验结果在多个性能同先前算法进行比较分析。 第五章是全文的总结及介绍了未来的一些研究工作。 江南大学硕士学位论文 第二章隐私保护关联规则挖掘算法综述 2 1关联规则数据挖掘算法 a g m w a l 等在1 9 9 3 年首次提出了关联规则挖掘的概念及问题描述和算法a i s 【2 1 ，关 联规则挖掘问题是在分析零售业事务数据库时提出的，现在的发展己经大大超出了原先 的应用范围，其深度和广度都有了很大的提高，但是关联规则的形式化的描述是有其通 用意义的，本节即采取这种形式化的描述方法。 关联规则挖掘的形式化描述： 设i = i l ，k ，i 。 由m 个不同的项目组成的集合，称为项集。给定集合d = t l ，2 ，t 。l 称为事务数据库，其中i 称为一个事务，是项集i 中一组项目组成的，即tc ，。每一个 事务拥有唯一的t d ，称为事务标识符。设x 中包含k 个项目，则x 称为k 一项集， 对于事务t d ，如果x t 称t 包含项集x 。关联规则就是形如x j y 的蕴涵式，其中 x 和y 是项集且x n y = 。 定义2 1 项集x 的支持度s u p p ( x ) 是包含x 的事务t 在事务数据库d 中出现的次数 同d 中事务总和的比率，即 s u p p o n ( x ) - 警等等型 ( 2 1 ) 定义2 2 规则r ：x jy 的置信度定义为在条件x 成立时成立的条件概率： c 。n f i e n c e c x = ，y ，= 兰! ! ：；5 ；i j 2 一 c2 2 ， s u p p o n i j 定义2 3 规则r ：m y 的支持度定义为： s u p p o r t ( r ) 2s u p p o r t ( xuy ) 定义2 - 4 大项集是指支持度超过用户定义的最小支持度1 1 1 i n s u p 的非空项集。 记为l k 代表长度为k 的大项集的集合，即： l k ：f x i ； x p k s u p p o r t ( x ) m i n s u p 则所有的大项集表示为：上= y i ：1 ，k k 其中k 是最长大项集的长度。 由以上定义可知： 性质2 1 设x 是大项集，z 是项集，如果z x ，则z 也是大项集。 性质2 2 设x 是小项集，z 是项集，如果z 2x ，则z 也是小项集。 性质2 3如果x 、z 是项集且z x ，则s u p p o r t ( z ) 兰s u p p o n ( x ) 。 ( 2 3 ) 第二章隐私保护关联规则挖掘算法综述 关联规则挖掘问题就是在事务数据库d 中找出具有用户给定的最小支持度1 1 1 i n s u p 和最小置信度m i i l c o n f 的关联规则。 关联规则的发现可以分解为两个子问题： 1 找出存在于事务数据库中的所有大项集。项集i 的支持度。s u p p o r t ( i ) r i l i ns u p ， 则称x 为大项集或者称为频繁项集。 2 利用大项集生成关联规则。对每个大项集a 若b ca ，b 且 ! ! 旦! 壁! 型m i n c o n f s u p p o r t ( b ) 其中典型的a 叫o r i 算法利用了项集的性质2 1 和性质2 2 ，裁减方法利用了性质 2 2 ，算法中假定每个事务中的项按照字母顺序排列，事务的格式为 ， 设k 项集用数据g 【k 表示示，则以上假设描述为：g 【1 】 m ，则设置j = m ； 2 ) 从t j 中随机均匀地选择j 个项，放入t ，中； 3 ) 对其它项( 包括t 。剩余部分) ，随机地以正面为p 。，反面为l p 。的概率抛硬币，将 那些结果为正面的项加入中r ； 设t 是总数为n 的交易集合，a 是一个项集，则定义a 的交集为f 的局部支持度 。p p m ) ：坐型掣。 v 假设随机运算符是保持交易和项不变的，设一个长度为m 的交易t ，以及一个长 度为 k 的项集a， t 被随机化为 t ， 定义 p ：( f 斗f 。) = p 【z j f 】- p 【# ( f n a ) = 门l ：f n a = f 】这里的f ，f 。都是 o ，l ，k l 中的整 数。对于“s e l e c t - a s i z e ”随机运算符 p ：( f 。f ) = 尸。旧 再假设t 中所有的n 条交易长度都为m ，则对一个长度为k 的项集a ，随机向量 + j j ，s s ：是一个( k + 1 ) 个独立的多项式分布的随机向量的和，这里s ，= s u p p j ( 以) 它的期望值e ( s j ，s ：，s ：) 7 = p + ( s o ，s ，5 。) 7 = p + ( s 。，s 、，s 4 ) r ，这里p 是一个 ( k + 1 ) 4 ( k + 1 ) 的矩阵p ，= p 【f 寸f 。 。 它的协方差c 。v ( s j ，s - s ：) 72 亩+ 荟5 c d 【2 】，这里每个d f 】是一个( k + 1 ) ( k + 1 ) 的矩 阵，d f l 爿= p f f 专】+ 艿。一p f f 】p f 一力；当i = j 时艿。等于l ，其它情况等于o ；s ，代 表s u p p j ( a ) 。 设s = ( s j ，s ，s ：) 7 ，s = ( ，s ，s x ) 7 ，则e s = p + s ( 2 5 ) 幽 删 江南大学硕士学位论文 值 设q ：p ，则j = q + e i = e q * i 这样就得到了根据随机化后的局部支持度计算出来的原始局部支持度的无偏差估计 s 耵，= q + s ( 2 6 ) 故c d v i = c 0 v ( q “= q ( c 0 v 硝q 7 = 专耄s 。q 。【f 】q 7 ( 2 4 ) 用s 来表示s 。的第k 个坐标，用s 来估计s ，用q 【f 一，】来表示q 。，则 s = s j + q 【卜f 】 该公式可以用来恢复项集的支持计数。 ( 2 7 ) 2 2 2 数据水平分布下的隐私保护 m k a n t a r c i o g i u 在文献 2 4 中提出一个从水平分割的数据中挖掘全局关联规则的隐 私保护算法，这里的数据水平分布指数据按照记录分布在多个站点，也就是说每个站 点拥有部分记录，各个站点相互之间不必知道对方的记录就可以挖掘出全局关联规则。 算法通过两个阶段找出全局频繁项集。假设d b 中的记录事务水平分布在n 个站 点，即s ，s ：，s n ，相应的成员数据库分别为d b 。，d b 2 ，d b 。， d b = d b u d 鼠u u d 曰。，且工。表示所有全局频繁k 一项集的集合，用l l i ( k ) 表示 站点s i 的所有局部频繁k 一项集的集合，用l l e i ( k ) 表示站点及的所有加密后的局部频 繁k 项集的集合，用g ( k ) = “女) n l l ( t ) 表示既是站点s i 的局部频繁k 一项集又是全 局频繁k 项集的集合，用c g ，( 女) 表示基于吼，( ) 产生的候选k 一项集的集合，f 表示伪 项集的集合。 第一个阶段，在各个分布站点之间，使用交换加密技术加密和交换局部频繁项集， 得到所有站点的局部频繁项集的合集。具体步骤如下： 1 )每个站点加密自己的局部频繁项集l l i ( k ) ，得到l l e i ( k ) ，并且随机地从f 中选 择若干伪项集，加密后加入l l e i ( k ) ，使ll l e i ( k ) = lc g i ( k ) i ： 2 )执行n 轮循环，每个站点将l l e i ( k ) 送给其下一个站点，并将每一轮收到的其它 站点的加密过的项集再次加密，再将它们发送到其下一个站点。最后的结果是每 一个站点都获得了被所有站点加密过的下一个站点的l l i ( k ) ： 3 ) 交换加密技术的特性e 。( e 。( 妇m 5 哪) = e ( 。( 妇s “) ) ，这些项集会被送到 第二章隐私保护关联规则挖掘算法综述 一个公共站点去删掉重复的项集，这里e 表示加密操作，k 。、k 。表示加密密钥： 4 )每个站点用自己的密钥对上面得到的项集开始解密，然后将解密后的项集送给其 n 下一个站点。最后一个站点将解密后的项集ij l l 。( ) 广播给其他站点。 j = l 第二个阶段，在不泄露各个站点项集支持计数的条件下，得到项集的全局支持计数， 找出全局频繁项集。具体步骤如下： 1 )对第一阶段中得到的集合中的每一个候选项集，第一个站点先计算该项集在自 己站点的局部支持计数( r c n t l ) 与最小支持计数阀值( s i d b ) 之间的差，然后加 上一个随机产生数r ，两者的和传给第二个站点： 2 )第二个站点再计算该项集在自己站点的局部支持计数( r c n 白) 与最小支持计数 阀值( s id b 。i ) 之间的差，然后加上第一个站点传过来的值，两者的和传给第三个 站点：依此类推，穷尽所有的分布站点，直到最终值被传回第一个站点： 3 )在第一个站点，比较该值与r 的大小，如果该值大于或等于r ，则表明该候选项 集是全局频繁项集。 2 2 3 数据垂直分布下的隐私保护 j v a i d y a 在文献【3 5 】中提出一个从垂直分割的数据中挖掘全局关联规则的隐私保护 算法，算法通过安全地计算代表子项集的标量积的方法来得到项集的支持计数。这里仍 将数据库记录视作一个固定长度的“1 ”和“o ”序列，例如购物篮数据库，每一个属性 代表一种商品( 项) ，每一行代表一个客户的购物记录，用一个固定长度的“1 ”和“0 ”， 序列来表示( “1 ”代表购买了该种商品，“0 ”代表没有购买该种商品) 。数据垂直分布 指数据按照属性分布在两个站点，各个站点不需要知道对方站点的属性值就可以挖掘全 局关联规则。 设数据库t 共有n 条记录，对于一个k 一项集，站点a 对应其p 个属性8 l ，8 p ，a ，1 ，a l p 一p 表示其第i 条记录在这些属性上的值，x 表示一个n 维的矢量，第i 维p 的值= 丌n 扩， j - 而站点b 有其剩余的q 个属性b l ，b q ，b n ，b i q ，表示其第i 条记录在这些属性上 口 的值，l r 表示一个n 维的矢量，第i 维的值y = 兀6 f ，k = p + q ，则通过计算标量积可以 j _ n 得到k _ 项集的支持计数x 1 ，= y x 。y ，从而可以找到全局频繁项集和关联规则。 百 上面的方法，为了计算x 和y 的标量积，必须向站点a 公布y 或向站点b 公布x ， 这就违反了隐私保护的原则，接下来j a i d e e p d y a 提出了一种不向对方公布自己的向 量情况下的计算标量积的方法( s c a l a rp r o d u c tp r o t o c 0 1 ) 来解决该问题： 1 )假设有一个n n 的系数矩阵c ，站点a 产生随机数r 。，r 。，然后送下 ! 堕奎堂堡主堂垡笙茎 列矢量i 给b ： 2 ) 站点b 计算s = x y ，产生随机数砭碍，然后将下列n 个值送给站点a ： 3 ) 站点a 对s 作如下变换： s = + y 。 扛i + 尺】+ ( c + ) 1 + c 2 ，f4 ) ，z + + c 州+ y 。+ q ) + r 。，+ ( c l ，。，+ y 1 + c 2 ，。，4 y 2 + + c 。，4 y 。+ r ：) + 尺。，+ l + ( c l n h 1 ) 半y 1 + c 2 n ，+ 1 ) + y 2 + + c “。，+ 1 14 y 。+ 尺i ) + r 。，4 ( c 1 2 。，) 8 岁1 + c 2 ，z 。，+ y 2 + + 巳，2 。，4 _ y 。+ 月i ) + r ( 卜1 ) h ，+ l4 ( c l 耵一胪。，+ i ) 丰yj + c “r - 1 ) ，+ l + y 2 十+ c ( 卜胪“。，+ l + y 。+ 尺：) + r 。+ ( c + y l + c 2 ，。4 y 2 十+ c 。+ y 。+ 尺：) 一( 月i + 吃+ 一十b ，) + r 一( 尺。，+ l + 尺。，+ 2 + + 尺2 。，) + 尺： 一( r ( 卜1 ) 。，+ l + r ( 卜1 ) 。，+ 2 + 一+ r ) + 尺： 因为站点a 已经知道随机数r - ，r 。的值，并且已经收到站点b 送来的s 和上 式中n 个r 。，r 。的系数值，所以可以计算得到： 扎印= r l4 ( c l l4 y l + c 2 ，l + y 2 + c 川2 y 。+ r f ) 第二章隐私保护关联规则挖掘算法综述 + r ，+ ( c 1 。，4 y l + c 2 。，木) ，2 + c 。，n ，+ y 。+ r 1 ) + 尺。，“4 ( c l ( 。，+ 1 ) 4 ) ，1 + c 2 期，+ 1 ) 4 y 2 + c 。，+ 1 y 。+ r i ) + r 2 。，+ ( c 1 ，2 。，+ ) ，l + c 2 ，2 n ，+ y 2 + c 。，2 。，4 ) ，。+ r 2 ) + r ( 卜l m ，+ l 。( c l ( r - 矿。，+ 18 ) ，l + c 2 如_ ”h ，+ 1 ) + y 2 + c “，_ 1 ) h ，“。) ，。+ r ：) + r 。+ ( c l ，4 y l + c 2 。4 y 2 + c 。+ y 。+ r ) 站点 a 将t e m p的值及 r 个，彰的系数( r l + r 2 + + r n r ) ，( 尺( ，一1 ) 。，+ l + r ( ，一1 ) 。，+ 2 + r 。) ) 给站点b ： 4 ) 因为站点b 已经知道随机数r 0 r ：的值，并且已经收到站点a 送来的t e m p 的值 及r 个尺江r ：的系数，故可以最后计算出s = t + y 。的值。 f = l 2 3 敏感规则的隐私保护 给定最小支持度和最小置信度阀值，从数据库中抽取出一组规则r ，假定规则集r 中哪些规则是敏感的由领域专家决定。规则隐藏算法的目的是使得敏感性规则对关联规 则挖掘算法不可见，同时尽可能少地影响留下的非敏感性规则，以便尽可能高地保持数 据质量。 为了隐藏规则a j b ，s a y g i n 【3 2 】提出把项集a b 的支持度降低到最小支持度阈值m s t 以下，或者可以把置信度降低到最小置信度阈值m c t 以下。这可以由用“? ”取代原 真实值以增加支持度和置信度的不确定性( 支持度和置信度区问长度) 来完成。 1 ) 如果采用的是通过降低支持度来隐藏规则a b ，那么唯一的办法就是对a b 中的项 用“? ”取代l ，从而使a jb 的最小支持度降低，并且在某个点以后低于m s t ， 而最大支持度将保持不变。 2 ) 如果是通过降低置信度来隐藏规则a = b ，我们可以把1 和o 都用”? ”代替。aj b 的置信度区间是【l i n c o n f ( a j b ) ；m a x c o n f ( a b ) ，目标是降低1 1 1 i n c o n f ( a j b ) ， 直至低于m c t 。最小置信度公式1 1 1 i n c o n “a b ) ) = 1 1 1 i n s u p ( a b ) m a x s u p ( a )