（计算机应用技术专业论文）基于rsa隐私保护的分布式关联规则挖掘方法研究.pdf

d i s c o l l e g eo f i n f o r m a t i o ns c i e n c ea n de n g i n e e r i n g g u i l i nu n i v e r s i t yo f t e c h n o l o g y m a r c h ，2 0 0 9t om a r c h ，2 0 10 研究生学位论文独创性声明和版权使用授权书 独创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人已 经发表或撰写过的研究成果，也不包含为获得其它教育机构的学位或证书而使用 过的材料。对论文的完成提供过帮助的有关人员已在论文中作了明确的说明并表 示谢意。 学位论文作者( 签字) ： 签字日期： 学位论文版权使用授权书 本学位论文作者完全了解( 学校) 有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的印刷本和电子版本，允许论文被查阅和借阅。 本人授权( 学校) 可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技 术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社 会公众提供信息服务。( 保密的学位论文在解密后适用本授权书) 本论文是否保密：是否如需保密，保密期限为： 学位论文作者签名： 签字日期：矽ld 年6 悯 导师签字： 7 ， 移一窆酽 月y 日 签字日期：毋缉月2 日 中文摘要 随着计算机网络与数据挖掘技术的飞速发展，海量数据的收集，知识“金块” 的挖掘变得越来越方便、快捷，这在商务决策、科学以及医学研究等各领域中发 挥着积极的作用。然而，在现实中数据挖掘不可回避的一个重要问题是隐私保护， 如顾客的购买喜好、病人的电子病情信息、银行卡客户的交易行为等极其敏感信 息将会泄露，这些问题的出现向数据共享和传统数据挖掘提出了挑战。在数据挖 掘过程中如何解决好隐私保护的问题，已经成为数据挖掘界的一个研究热点。 本文主要研究内容是基于r s a 隐私保护的分布式关联规则挖掘方法。传统隐 私保护的关联规则挖掘算法主要基于特定的集中式数据库设计，针对分布式环境 下的隐私保护关联规则挖掘尚不多见。目前，通常把分布式环境下的隐私保护关 联规则挖掘归结为安全多方计算问题，但需要付出高额的计算与通信代价。因此， 研究并设计高效隐私保护的分布式关联规则挖掘方法是本文研究的主要目标。 本文主要研究内容与创新点如下： 1 - 在深入分析经典a p r i o r i 算法基础上，针对a p r i o r i 算法瓶颈问题，设计一种 改进的关联规则挖掘算法基于事务相似矩阵的关联规则挖掘a r b s m 算法。 该算法是在压缩事务布尔矩阵基础上构建一个事务相似矩阵，跨越了从低向高逐 阶查找频繁项集的限制，有效地解决了a p r i o r i 算法由于逐层搜索的迭代产生大量 候选项集的问题。经实验验证该算法具有较好的准确性和效率性。 2 引入密码管理服务器( c m s ) 和数据挖掘服务器( d m s ) ，构建一个分布式 安全体系总体框架，并结合r s a 公钥加密和伪随机数生成器技术优势，在a r b s m 算法基础上，设计一种隐私保护的分布式关联规则挖掘p p d a r b s m 算法。理论 分析与实验结果表明，该算法具有较好的隐私性、准确性和效率性，但同时存在 一个明显瓶颈问题：存在大量指数运算，极大影响算法执行效率。 3 进一步优化c m s 和d m s 功能，构建一个改进的分布式安全体系总体框架， 并结合r s a 公钥加密和h e s 同态加密机制的优势，在a r b s m 算法基础上，采用 密码分级管理机制，设计一种基于r s a 隐私保护的分布式关联规则挖掘 p p d m a r b s m 算法。它有效地解决p p d a r b s m 算法的瓶颈问题，理论分析与 实验结果表明，该算法具有更好的隐私性、准确性和高效性。 关键字：r s a 公钥加密：h e s 同态加密机制；隐私保护：关联规则：数据挖掘； 分布式数据库 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r ka n dd a t am i n i n g ，t r e m e n d o u s a m o u n to fd a t ac o l l e c t i o na n d “g o l d e nn u g g e t s o fk n o w l e d g em i n i n gh a sb e c o m em o r e a n dm o r ec o n v e n i e n t t h e s eh a v ec o n t r i b u t e dg r e a t l yt ob u s i n e s ss t r a t e g i e s ，s c i e n t i f i c a n dm e d i c a lr e s e a r c h i nr e a l i t y , h o w e v e r ，p r i v a c y p r e s e r v i n gi nd a t am i n i n gi sa l l u n a v o i d a b l eq u e s t i o n s e n s i t i v ei n f o r m a t i o n ，s u c ha sc u s t o m e rb u y i n gh a b i t s ，e l e c t r o n i c m e d i c a lr e c o r d ，b a n k c a r dc l i e n t st r a n s a c t i o nb e h a v i o r ，w i l lb el e a k e d t h ee m e r g e n c eo f t h e s ep r o b l e m sb r i n g san e wc h a l l e n g et od a t as h a r i n ga n dt r a d i t i o n a ld a t am i n i n g i n t h ep r o c e s so fd a t am i n i n g ，h o wt or e s o l v et h ep r o b l e mo fp r i v a c y p r e s e r v i n gh a s b e c o m eah o tr e s e a r c ht o p i ci nd a t am i n i n gf i e l d t h i s p a p e ri sm a i n l ya b o u tt h er e s e a r c ho na p p r o a c h e sf o rp r i v a c yp r e s e r v i n g d i s t r i b u t e dm i n i n go fa s s o c i a t i o nr u l e sb a s e do nr s a t h et r a d i t i o n a la l g o r i t h md e s i g n o f p 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 em i m n gi sm a i n l yb a s e do nap a r t i c u l a rc e n t r a l i z e d d a t a b a s e i nd i s t r i b u t e de n v i r o n m e n t ，t h ea l g o r i t h mf o rp r i v a c yp r e s e r v i n ga s s o c i a t i o n r u l em i n i n gi sb e i n gs t i l lr a r e a tp r e s e n t ，p r i v a c yp r e s e r v i n gd i s t r i b u t e dm i n i n go f a s s o c i a t i o nr u l e st e n d st ob ea t t r i b u t e dt os e c u r em u l t i p a r t yc o m p u t a t i o np r o b l e m l i k e w i s e ，w en e e dt op a yf o rh i g hc o m m u n i c a t i o na n dc o m p u t a t i o n t h e r e f o r e ， r e s e a r c h i n g a n dd e s i g n i n ge f f i c i e n t a p p r o a c h e sf o rp r i v a c yp r e s e r v i n g d i s t r i b u t e d m i n i n go fa s s o c i a t i o nr u l e si st h em a i nt a r g e t so ft h i sp a p e r t h em a i nc o n t e n t sa n di n n o v a t i o n sf o rt h ep a p e rc a nb es u m m a r i z e da sf o l l o w s ： 1 b a s e do na n a l y s i so fc l a s s i ca p r i o r ia l g o r i t h m ，i nt h ep a p e ra i li m p r o v e d a s s o c i a t i o nr u l em i n i n ga l g o r i t h m ( a r b s m ) ，w h i c hi sb a s e do ns i m i l a r i t ym a t r i xo f t r a n s a c t i o n s ，i sd e s i g n e da i m i n ga tt h e b o t t l en e c k ”p r o b l e mi na p r i o r ia l g o r i t h m t h e a l g o r i t h mc o n s t r u c t ss i m i l a rm a t r i xo ft r a n s a c t i o n sb a s e do nt h ec o m p r e s s e db o o l e a n m a t r i c e so ft r a n s a c t i o n s ，o v e r c o m e st h el i m i t a t i o no ff i n d i n gf r e q u e n c yi t e m s e t sf r o m l o wo r d e rt oh i g ho r d e ra n dc a ne f f e c t i v e l ys o l v eal a r g en u m b e ro fc a n d i d a t ei t e m s p r o b l e m sg e n e r a t e db ys t e pb ys t e p i t e r a t i v es e a r c h t h e e x p e r i m e n t a l r e s u l t s d e m o n s t r a t et h a tt h ep r o p o s e da l g o r i t h mi sq u i t ea c c u r a t ea n de f f i c i e n t 2 ad i s t r i b u t i v e s e c u r i t yf r a m e w o r ki sc o n s t r u c t e db yi n t r o d u c i n gc r y p t o g r a m m a n a g e m e n ts e r v e r ( c m s ) a n dd a t am i n i n gs e r v e r ( d m s ) c o m b i n i n gt h ea d v a n t a g e s o fr s a p u b l i c k e ye n c r y p t i o na n dp s e u d o r a n d o mg e n e r a t o rt e c h n o l o g y , p p d a r b s m a l g o r i t h mi sd e s i g n e di nt h ep a p e rp p d a r b s mi sap r i v a c yp r e s e r v i n gd i s t r i b u t e d i i m i n i n gm e t h o do fa s s o c i a t i o nr u l e s ，b a s e do na r b s ma l g o r i t h m t h e o r e t i c a la n a l y s i s a n de x p e r i m e n t a lr e s u l t ss h o wt h a tp p d a r b s ma l g o r i t h mc a l la c h i e v ei m p r o v e m e n t s i nt e r m so fp r i v a c y , a c c u r a c y , a n de f f i c i e n c y b u ta tt h es a m et i m et h e r ei st h eo b v i o u s b o t t l e n e c kp r o b l e m t h eo b v i o u sb o t t l e n e c kp r o b l e mi st h a tt h e r ei st r e m e n d o u sa m o u n t o fe x p o n e n t i a lc o m p u t a t i o n t h ei m p l e m e n t a t i o no ft h ea l g o r i t h me f f i c i e n c yi sg r e a t l y a f f e c t e db yt h eb o t t l e n e c kp r o b l e m 3 a ni m p r o v e dd i s t r i b u t i v e s e c u r i t y f r a m e w o r ki sc o n s t r u c t e db yf u r t h e r o p t i m i z i n gt h e f u n c t i o no fc m sa n dd m s c o m b i n i n gt h e a d v a n t a g e so fr s a p u b l i c - k e yc r y p t o s y s t e ma n dh o m o m o r p h i ce n c r y p t i o ns c h e m e ，a n da d o p t i n gt h e l e v e l - t o l e v e la d m i n i s t r a t i o nm e c h a n i s mo fc r y p t o g r a m ，t h ep a p e rp r o p o s e sap r i v a c y p r e s e r v i n g d i s t r i b u t e d m i n i n ga l g o r i t h m o fa s s o c i a t i o nr u l e sb a s e do i la r b s m a l g o r i t h m ( p p d m a r b s m ) 。t h ea l g o r i t h mc a l le f f e c t i v e l y s o l v et h eb o t t l e n e c k p r o b l e mo fp p d a r b s ma l g o r i t h m t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o w t h a tp p d m a r b s ma l g o r i t h mc a l la c h i e v eb e a e ri m p r o v e m e n t si nt e r m so fp r i v a c y , a c c u r a c y , a n de f f i c i e n c y k e yw o r d s ：r s ap u b l i c k e ye n c r y p t i o n ；h e sh o m o m o r p h i ce n c r y p t i o ns c h e m e ； p r i v a c yp r e s e r v a t i o n ；a s s o c i a t i o nr u l e ；d a t am i n i n g ；d i s t r i b u t ed a t a b a s e 目录 中文摘要i a b s t r a c t i i 第1 章引言1 1 1 研究背景与意义1 1 2 国内外研究现状l 1 3 发展趋势3 1 4 本文主要研究内容3 1 5 章节安排4 第2 章关联规则挖掘5 2 1 基本概念5 2 2a p r i o f i 算法5 2 2 1a p r i o f i 算法描述5 2 2 2a p f i o f i 算法性能分析7 2 2 3a p f i o f i 算法的现有优化方法7 2 3 一种改进的关联规则挖掘算法的设计9 2 3 1 事务相似矩阵定义与性质9 2 3 2 基于事务相似矩阵的关联规则挖掘算法描述1 0 2 3 3 基于事务相似矩阵的关联规则挖掘算法实例1 l 2 3 4 算法分析与仿真实验1 3 2 4 关联规则挖掘的发展趋势1 5 2 5 本章小结1 7 第3 章隐私保护的关联规则挖掘1 8 3 1 隐私概念1 8 3 2 问题的提出1 8 3 3 隐私保护的关联规则挖掘方法1 9 3 3 1 随机数据干扰1 9 3 3 2 数据驴匿名2 l 3 3 3 基于数据加密2 3 3 4 隐私保护的关联规则挖掘算法评价标准2 7 3 5 本章小结2 8 第4 章基于r s a 隐私保护的分布式关联规则挖掘方法的研究2 9 4 1 问题描述 4 1 1 基本概念 4 1 2r s a 公钥密码算法 4 1 3h e s 同态加密机制 4 2 基于r s a 和伪随机数生成器技术的p p d a r b s m 算法的设计 4 2 1 总体架构 4 2 2p p d a r b s m 算法描述 4 2 3 算法评价与仿真实验 4 3 基于r s a 与h e s 同态加密的p p d m a r b s m 算法的设计 4 3 1 总体架构 4 3 2p p d m a r b s m 算法描述 4 3 3 算法评价与仿真实验 4 4 本章小结 第5 章总结与展望 5 1 总结 5 2 展望 致谢 参考文献 个人简介 攻读硕士学位期间发表的学术论文 攻读硕士学位期间参与的科研工作 v 2 9 2 9 3 0 3 0 3 1 3 1 3 2 3 3 3 5 3 5 3 6 3 7 3 9 4 0 4 0 4 1 4 2 4 3 4 7 4 8 4 9 第1 章引言 第1 章引言 1 1 研究背景与意义 数据库、网络和高性能处理器技术的高速发展，为海量数据的采集、管理与 分析提供了便利条件，使知识“金块 挖掘变得越来越方便、快捷。这在商务决 策、科学以及医学研究等各领域中发挥着积极重要的作用。但与此同时，也带来 了隐私保护的一系列问题。例如顾客的购买喜好、病人的电子病情信息、银行卡 客户的交易行为等极其敏感信息将会泄露，这直接危及个人的人格、尊严和隐私。 同时，由于全球经济的一体化，企业间合作和信息共享日益频繁，一方面给 企业团体降低了生产经营成本，给新市场开拓带来了极大便利；但另一方面对于 企业个体来说，其商业机密却遭到了严重威胁。从商业竞争的现实性角度考虑， 商业机密的泄漏无疑将严重影响企业的竞争优势，从而极大影响数据挖掘在经济 领域的广泛应用前景。 在保证私有的敏感信息不被泄漏的情况下，如何实现有效的知识发现? 近年 来已成为数据库和数据挖掘领域一个活跃的研究方向，随着这种需求不断上升， 不仅对数据共享和传统的数据挖掘提出严峻挑战，同时也为隐私保护的数据挖掘 发展创造成熟条件。在数据挖掘过程中如何解决好隐私保护的问题，已经成为数 据挖掘界的一个研究热点。 本文的研究意义就是：使得知识发现和隐私保护能共存，在保护数据拥有者 隐私的前提下，最大限度地发现知识，造福社会，不断开拓隐私保护在商务决策、 科学以及医学研究等各领域应用。 1 2 国内外研究现状 目前，隐私保护的数据挖掘方法大致可以从五个层面进行划分： ( 1 ) 根据隐私保护的对象可分为：一是敏感原始数据的隐藏，如身份证号码、 银行卡号、地址与健康状况等；二是敏感规则与知识的隐藏，即有效地保护数据 挖掘得到的敏感规则与知识，以防机密泄露和基于知识的恶意推理。 ( 2 ) 根据敏感原始数据隐藏的基本策略，可以分为随机数据干扰、数据k 一 匿名和基于数据加密。随机数据干扰就是通过数据变换、数据离散化和在数据中 增加“噪声”数据等方法对原始数据进行干扰，然后再针对经过干扰的数据进行 挖掘，最后得到所需的模式和规则：数据七咂名主要通过泛化和隐匿技术来实现 数据匿名化：基于数据加密常用于分柿式数据库，通常归结为安全多方计算问题。 第1 章引言 ( 3 ) 根据敏感规则与知识隐藏的基本策略，可以分为数据变换法、数据阻塞 法、数据重构法和数据抽样法。其中最常见的是数据变换法。 ( 4 ) 根据应用数据挖掘的算法，可以分为关联规则挖掘、分类挖掘和聚类挖 掘等隐私保护技术。 ( 5 ) 根据数据源分布的方式，可以分为集中式数据库隐私保护和分布式数据 库隐私保护。大多数传统数据挖掘方法基于集中式数据库，然而出于数据机密性 和隐私保护的考虑，隐私保护的数据挖掘的研究环境大都为分布式环境。 而分布式环境根据数据集的分布情况，又可以分为水平划分和垂直划分。水 平划分，即相同属性集的不同记录分布在不同的位置，即各站点的数据是同质的； 垂直划分，则是不同属性的值分布于不同位置，即各站点上的数据具有不同的特 征，是异质的。 下面介绍几个典型隐私保护的数据挖掘方法( 表1 1 ) ： 表1 1 典型隐私保护的数据挖掘方法 隐私保护数据分布数据挖掘隐私保护 作者文献题目 对象方式算法策略 集中式关联规则数据干扰 r i z v is j a s m c 卿j a t i o 眦nr u 1 e d 砒m ? i n i n 篁g 济y m k - a n o n y m i t y ： am o d e lf o r 关联规则 p r o t e c t i 矗gp r i v a c y 2 4 j 集中式 聚类 卜匿名 s w e e n e yl a c h i e v i n gk - a n o n y m i t yp r i v a c y 黑篡恐dusnnling：，pnerali洲ands u p p r e s s l o n r 敏感 p r i v a c y p r e s e r v i n g d i s t r i b u t e d 原始数据 水平分布关联规则 数据加密 k a n t a r c i o g l u m i n i n go fa s s o c i a t i o nr u l e so n m h o r i z o n t a l l yp a r t i t i o n e dd a t a 【5 1 】 p r i v a c yp r e s e r v i n ga s s o c i a t i o n 垂直分布关联规则 数据加密 v a i d y aj p a r t i t i o n e d 【a t a i 纠 c a l l y 部分隐藏 一种有效的隐私保护关联规则 集中式关联规则 随机化回 张鹏，等 答r r p h 挖掘方法【2 1 1 h i d i n g a s s o c i a t i o nr u l e sb v 集中式关联规则数据变换 d a s s e n ie u s i n gc o n f i d e n c ea n ds u p p o r c 【5 3 1 集中式关联规则数据重构 c h e n x an rjmew唑ofpreselvmrd a t as 1 1 a r m g 【5 p 孔y 敏感规则 u s i n g u n k n o w n st o p r e v e n t 与知识 集中式关联规则数据阻塞 s a y g i n y d i s c 西e r vo fa s s o c i a t i o nr u l e s 【5 6 1 h i d i n gc l a s s i f i c a t i o n r u l e s f o r 集中式分类数据重构n a t w i c h a ij d a t a s h a r i n g e r v a t i o n 1 3 3 1 w i t h p r i v a c y o r e s 隐私保护的数据挖掘己经成为数据挖掘研究中一个富有成果的领域，吸引越 来越多的密码学、统计学等相关学科的学者参与其中。近几年来，特别是有关敏 感原始数据隐藏的隐私保护数据挖掘在一些高水平国际会议如s i g m o d 、k d d 与 第1 章引言 i c d m 等中已发表大量优秀论文。 与国外相比，我国对于隐私保护的数据挖掘研究起步较晚，许多科研单位和 高等院校竞相开展了基础理论及其应用研究。到e 1 前为止，大都是基于特定的集 中式数据库设计，针对分布式环境下的隐私保护关联规则挖掘尚不多见。 1 3 发展趋势 数据挖掘从其一诞生，就带上了强烈的应用色彩，广泛渗透到金融、保险、 零售、医学、制造、运输各行业以及科学与工程研究等众多领域。在金融行业， 数据挖掘可以用来分析客户的信用状况，可以预测贷款偿还情况等；在商业领域， 数据挖掘所能解决的典型商业问题包括数据库营销、客户群体划分、背景分析、 交叉销售等市场分析行为；在生物医学领域，可以采用数据挖掘对d n a 序列进行 研究；在生产制造行业，数据挖掘可以应用在诊断机器故障、生产调度等方面。 同时，随之产生的隐私泄漏现象也屡见不鲜，引起人们对于信息共享与数据挖掘 的恐慌，从而使数据挖掘的隐私保护和信息安全问题成为当前数据挖掘领域的重 要紧迫性的研究课题。 目前，针对原始数据隐藏的隐私保护数据挖掘主要可以从三个方面进行研究： 随机数据干扰、数据后握名和基于数据加密。随机数据干扰是通过数据转换、离 散化或随机添加“噪声”数据等方法来隐藏原始数据，该方法主要用于集中式分 布的数据；数据k 握名主要通过泛化和隐匿技术来实现数据匿名化，但与随机数 据干扰不同在于它保持数据的真实性；基于数据加密的隐私保护常用于分布式数 据库，通常归结为安全多方计算问题，在基于密码学理论基础上实现每个参与者 只能接收到正确的数据挖掘结果，不能获取任何其它参与者输入的原始数据信息。 在现实中，大量数据集都是按地理位置分布于多个场所，又可能分属于不同 用户。因此，在分布式环境下，基于数据加密的隐私保护数据挖掘必将成为数据 挖掘界的一个研究热点。 1 4 本文主要研究内容 本文主要研究内容是基于r s a 隐私保护的分布式关联规则挖掘方法研究。具 体研究内容主要包括以下五个方面： ( 1 ) 深入分析经典a p r i o r i 挖掘算法，针对a p r i o r i 算法瓶颈问题，设计一种 改进的关联规则挖掘算法基于事务相似矩阵的关联规则挖掘a r b s m 算法。 该算法的设计目标是在压缩事务布尔矩阵的基础上构建一个事务相似矩阵，直接 查找高阶缸项频繁集，跨越了从低向高逐阶查找频繁项集的限制，有效地解决 第1 章引言 a p r i o r i 算法因逐层搜索的迭代产生大量频繁候选项集的瓶颈问题。 ( 2 ) 研究目前敏感数据的隐私保护策略，分析比较其优缺点。重点研究随机 数据干扰、数据k 握名和基于数据加密三种隐私保护策略，从安全需求与安全风 险分析出发，兼顾安全与效率，逐层展开隐私保护的分布式关联规则挖掘研究。 ( 3 ) 引入密码管理服务器( c m s ) 和数据挖掘服务器( d m s ) ，构建一个分 布式安全体系总体框架，并结合r s a 公钥加密和伪随机数生成器技术优势，在 a r b s m 算法基础上，设计一种基于r s a 隐私保护的分布式关联规则挖掘 p p d a r b s m 算法。 ( 4 ) 进一步优化c m s 和d m s 功能，构建一个改进的分布式安全体系总体框 架，并结合r s a 公钥加密和同态加密h e s 机制的优势，在a r b s m 算法基础上， 采用密码分级管理机制，设计一种基于r s a 隐私保护的分布式关联规则挖掘 p p d m 。a r b s m 算法。 ( 5 ) 归纳与总结隐私保护的分布式关联规则挖掘算法的三个关键性评价指 标，并对比各算法实验结果，作出各项性能分析与评价。 1 5 章节安排 本文的章节安排如下： 第1 章引言部分阐述了研究背景与意义，分析了国内外研究现状和发展趋势， 并明确了本文主要研究内容。 第2 章首先分析经典a p r i o r i 算法，针对a p r i o r i 算法瓶颈问题，设计一种改 进的关联规则挖掘算法基于事务相似矩阵的关联规则挖掘a r b s m 算法。然 后对a r b s m 算法进行性能分析并给出实验结果。最后介绍关联规则挖掘的三个 发展趋势与方向。 第3 章隐私保护的关联规则挖掘主要涉及两个层面：一是原始敏感数据的隐 藏。二是敏感规则与知识的隐藏。本章讨论第一层面隐私保护的关联规则挖掘方 法，主要围绕随机数据干扰、数据七握名和基于数据加密三个方面来探讨隐私保 护的关联规则挖掘方法。最后归纳出隐私保护的关联规则挖掘算法评价标准。 第4 章本章重点研究并设计高效的基于r s a 隐私保护的分布式关联规则挖 掘方法。首先构建一个分布式安全体系的总体框架，设计一种基于r s a 隐私保护 的分布式关联规则挖掘p p d a r b s m 算法，并给出算法描述、评价与实验结果。 然后构建一个改进的分布式安全体系总体框架，并结合r s a 公钥加密和同态加密 h e s 机制的优势，采用密码分级管理机制，设计一种基于r s a 隐私保护的分布式 关联规则挖掘p p d m a r b s m 算法，并给出算法描述、评价与实验结果。 第5 章对本文研究工作进行全面总结，并提出了三个后续研究方向。 4 第2 章关联规则挖掘 第2 章关联规则挖掘 关联规则概念最早是由a g r a w a l 等人于1 9 9 3 年提出k d d 研究中的一个重要 课题。关联规则挖掘是数据挖掘的重要研究领域，其目的就是要发现大型事务数 据库中项集间有趣的关联，从而帮助各类业界人士制定决策。关联规则挖掘的一 个典型引发性例子购物蓝分析，通过发现顾客放入“购物蓝中商品的关联， 帮助零售商分析顾客的购买喜好，从而有针对性地制定市场营销策略，提高销售 量。目前，关联规则挖掘已广泛应用于各个领域，例如：文本词频分析、股票事 务分析、金融服务、电子商务和网络入侵检测等。 2 1 基本概念 设卢 ，厶，k 是一组项的集合，任务相关的数据d 是数据库事务， 的集合，d ： 死，疋，瓦) ，其中每一个事务乃，且有一个标识符t i d 。设彳 是，中项的集合，如果a 互t ，则称事务r 包含彳。关联规则是形如ajb 的蕴含 式，其中ac i ，b c _ i ，并且彳t 7 庐。关联规则使用支持度与置信度这两个重要 概念来反映规则的有用性和确定性，即是 s u p p o r t ( a 功印以u 功 c o n f i d e n c e ( a 功印la ) 同时满足最小支持度阈值( r a i ns u p ) 和最小置信度阈值( m i nc o n f ) 的规则 称作强规则【l j 。 关联规则挖掘过程通常分为二步： ( 1 ) 求频繁项集。即找出支持度不低于预定最小支持度阈值的项集。 ( 2 ) 由频繁项集产生置信度不低于预定最小置信度阈值的关联规则。 2 2 a p r i o r i 算法 2 2 1 a p f i o f i 算法描述 a p r i o r i q 算法是一种最有影响力的经典布尔关联规则频繁项集的挖掘算法。它 使用一种称作逐层搜索的迭代方法，即驴项集用于搜索( n 1 ) 一项集。首先，找 出频繁卜项集的集合，该集合记作l ，用l 查找频繁2 一项集的集合三2 ，用厶查 找3 ，如此下去，直到不能找到频繁卜项集。 a p r i o r i 性质：频繁项集的所有的非空子集都必须也是频繁的。 在用l k - i 找l ( 七2 ) 过程中，利用a p r i o r i 性质压缩搜索空问，从而达到加 第2 章关联规则挖掘 速搜索频繁项集的目的，整个过程由连接步和剪枝步组成。 ( 1 ) 连接步 通过将三七- l 与自身连接产生候选k 项集的集合c t ，设，l 与如是“l 的项集，用 厶们表示厶中的第项，并假定事务和项集中的项是按字典顺序排列，即对于( k - i ) 项集己，则意味着将项排序后，使得，f 【1 】 t 1 2 】 k - 1 】。执行连接l k - i 司k l 操作，如果前( k - 2 ) 个项相同，则玩l 的元素是可连接的。例如，三七- l 的元素，i 与如是可连接，则满足( l 】- 2 1 ) a ( 1 1 1 2 1 = 1 2 1 2 ) a ( 1 l k 一2 】- 1 2 k - 2 ) a ( 1 l 陋l 】 r a i n _ s u p ) 6 第2 章关联规则挖掘 ) r e t u r n 仁k j 正t ： p r o c e d u r ea p r i o r i _ g e n 旺纠：f r e q u e n t ( k o1 ) 一i t e m s e t s ) f o re a c hi t e m s e ti i 三“i f o re a c hit e m s e ti i l , 1 i f ( ，l 1 】_ 1 2 1 ) a ( z l 2 】- t 2 1 2 1 ) ( h k - 2 = 1 2 k - 2 ) ( 舡1 11 2 ：j o i ns t e p ：g e n e r a t ec a n d i d a t e s i fh a s _ i n f r e q u e n t _ s u b s e t ( c ，三肛1 ) t h e n d e l e t ec ；p r u n es t e p ：r e m o v eu n f r u i t f u lc a n d i d a t e e l s ea d dct og ； ) r e t u r nq p r o c e d u r eh a s _ i n f r e q u e n t _ s u b s e t ( c ：c a n d i d a t ek - i t e m s e t ； l k - i ：f r e q u e n t ( k - 1 ) - i t e m s e t s ) u s ep r i o rk n o w l e d g e f o re a c h ( k - 1 ) 一s u b s e tso f c i f s l k - lt h e n r e t u r nt r u e ； r e t u r nf a l s e ； 2 2 2a p r i o d 算法性能分析 在经典a p r i o r i 算法中存在三个明显瓶颈问题： ( 1 ) a p r i o r i 算法采用了逐层搜索的迭代方法，从而导致只能逐阶由低向高搜 索频繁项集，尽管大多数情况只需要k 的高阶频繁项集，却也无法避免由搜索低 阶( 尤其三，) 频繁项集造成浪费大量计算机时间与空间资源。 ( 2 ) 在a p r i o r i 算法中，由l “l 生成厶分为二个步骤，首先要将l k - i 与自身连 接产生k 项候选集q ，然后再利用a p r i o r i 性质剪枝，但候选项集q 数量呈指数 型增长，无法避免庞大候选项集造成的巨大计算机时间与空间开销。 ( 3 ) 在a p r i o r i 算法中，对于任何一次k 循环，候选项集g 中每一个成员都 必须扫描一次数据库，来确定g 中每一个候选的计数，从而确定厶。显而易见， a p r i o d 算法需要反复扫描事务数据库d ，造成i o 负载过重。 2 2 3a p r i o d 算法的现有优化方法 为了能进一步提高a p r i o r i 算法的挖掘效率，许多学者在a p r i o r i 算法基础上， 提出了各种以a p r i o r i 算法为原型的变形或优化算法【1 1 。其大体上可分为二类：一 第2 章关联规则挖掘 类是利用候选项集产生频繁项集，如：基于散列技术、基于裁减多循环搜索、数 据集划分、抽样和动态项集计数等。另一类不候选直接产生频繁项集，如：频繁 模式增长。 ( 1 ) 基于散列技术 基于散列技术主要用于压缩k 项候选集c 七( 胁1 ) ，首先扫描数据库的每一个 事务瓦，由候选1 项集c l 产生频繁l 项集三l ，然后利用散列函数对每一个事务产 生2 项集，将它们映射到一个散列表结构不同的桶中，并增加相应的桶计数，当 散列表中相应的桶计数小于支持度阈值时，其2 项集不可能是频繁项集，可从。 中删除该2 项集。依此类推，可明显压缩k 项候选集g ，尤其对于候选2 项集q 。 ( 2 ) 基于裁减多循环搜索 以a p r i o r i t i d 算法为代表的基于裁减多循环搜索方法是利用a p r i o r i 性质，仅 在第一次扫描数据库时，用数据库d 计算l 项频繁项集支持度，其余各次扫描只 用上一次扫描生成的候选数据库d 来替代，越是高阶k 项频繁集，由于d 远远小 于d ，越突出其算法优势，明显减少i o 操作时间，大大提高算法执行效率。 ( 3 ) 数据集划分 数据集划分方法是使用划分技术扫描二次数据库，即可挖掘频繁项集。其操 作过程包括两步。第一步，将数据库d 中的事务分成聆个互不重叠的划分部分， 若数据库d 的事务最小支持度阈值为m i ns u p ，则每一划分的最小支持度计数为 m i ns u p 该划分所包含事务数。对于每一个划分，采用一种特殊的数据结构，扫 描一次数据库，找出该划分的所有局部频繁项集。第二步，由于数据库d 中任何 频繁项集必须是作为