（管理科学与工程专业论文）保护隐私的分布式关联规则挖掘研究.pdf

中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： 墨擘：茎一 诚年冬r 中田科学技术人学坝l 。学位论义 摘要 数据挖掘一赢是数据库研究、开发和应用中最活跃的分支之一。无论在研究领域还是商 业应用，数据挖掘都取得了可喜的成果。而关联规则挖掘在数据挖掘技术中占有很重要的地 位，其在商务决策的制定方面很有应用前景。 目前很多火企业都有分支机构，各个分支机构义都臼成一体。一方面，这些分支机构希 望j 。泛地收集信息，并从中挖拥山有川的知识利模式米指导其更盘，地发展。另一方面冈为 关联规贝0 挖掘揭示的是不容易发现的模式或各种知识，如果不止确使朋。就可能会对隐私和 信息安全构成威胁。冈此关联规则挖掘要面临的两个重要问题就是在分布环境卜的挖掘和挖 掘过程中的隐私保护。针对前一个问题，现今已开发出一些分布式挖掘算法；而后一问题目 前还没有得剑很好的解决。成为今后的研究热点问题。 本文分析了现有分布式关联规则挖掘算法的优缺点，对现有算法在效率和安全性两方面 进行了改进，引用密码学中的不经意传输协议，设计了一套安全高效的分布式关联规则挖掘 算法町一p p d m ，以保证此过程中安全地交换统计信息而不涉及具体隐私细节，从而更好地满 足现代企业和商务发展的隐私性需求。 文章最后，没计仿真实验将0 t p p d m 算法与另外两种代表性的分布式犬联规则挖掘算法 ( f d m 快速算法萃| lc p p d m 加密算法) 进行了比较。实验结果表明本文算法有较女f 的安全性， 高效性平适川性。 关键词：数据挖掘，隐私保护，分布式关联规则挖掘，不经意传输 第l 页共4 4 页 中罔科学技术人学坝 j 学位论上 a b s t r a c t d a 协m i n i n gi sa l w a y so n eo ft h em o s ta c t i v eb r a n c h e si nd a t a b a l s er e s e a r c h i n g ，d e v e i o p i n ga n d a p p l i c a t i o n w h e t h e ri nt h ea r e ao fr e s e a r c ha n dc o m m e r c i a l 印p i i c a t i o n s ，d a t am i n i n ga l lg e t g r a t i f m n gr e s u l t s a n dt h e 硒s o c i a t i o nr u i em i n i n gw h i c hh a st h e 印p l i c a t i o nf o r e g r o u n di nm a k i n g b u s i n e s sd e c i s i o nt a k e sa ni m p o n a n tp l a c ei nt h ed a t am i n i n gt e c h n o l o 酣 c u r 托n t l y m a n yb i gc o m p a n i e sh a v eb r a n c h e s ，a n de a c hb r a n c hs t a n d sf o ras e p a r a t eo n e o n t h eo i eh a n d t h e s eb r a n c h e sw a n tt oc o l l e c tal o to fi n f b 九t 1 a t i o nc og e tu s e f u ik n o w i e d g ea n d m o d e i sw h i c hc a ng u i d et h e mt od e v e i o pb e t t er o nt h eo t h e rh a n d ，w h a ta s s o c i a t i o nr u l em i n i n g s h o w si st h a ln o te a s i i yf b u n dm o d e la n da i lk i n d so f k n o w i e d g e 1 f i th a sb e e nu s e di n c o r r e c c l y ， t h i sc 叫i dp o s eat h r e a il op r i v a c ya n di n f - o 丌n a t i o ns e c u r i t y t h e r e f o r et h et w oi m p o r t a n tq u e s t i o n s w h i c ha s s o c i a t i o nr u l em i n i n gs h o uj df - a c ea r em i n i n gu n d e rd i s t r i b u t e de n v i r o n m e n ta n dp r v a c y p r e s e r v i n gi nl h em i n i n gp r o c e s s t - ot h en r s tq u e s t i o n ，s o m ed i s t r i b u t e dm i n i n ga l g o r i t h m sh a v e b e e nd e v e l o p e dn o w ；a n dt ot h es e c o n do n e ，w h j c hh a sn o tb e e ns o l v e dw e l lb yn o w ，w ii lb e c o m e ah o ti s s u ei nf u t u r er e s e a r c h o nt h eb a l s i sr e v i e w i n ge x i s i i n gd i s t m u t e d 鼬s o c ia i i o n1 1 j l em i n i n ga i g o r i t h ma n dd o i n g i m p r o v e m e n ti ne n l c i e n c ya n ds a f e t yt o t h ee x i s t i n ga l g o r i t h m ，q u o t i n gt h eo b l i v i o u st r a n s f - e r p r o t o c o l i n c r y p t o g r a p h y t h i sp a p e rd e s i g n s as e to fs a f ea n dh i g h l ye f n c i e n td i s t r i b u t e d a s s o c i a l i o nr u l em i n i n ga i g o r i t h m ( o t p p d m ) ，w h i c hc a ne x c h a n g es t a t i s t i c si n f o m a t i o nw i t h o u t i n v o l v i n go fs p e c i n cd e t a i l s t h i s w o r kw i i ls a t i s f yf u r t h e rp r i v a c y r e q u i r e m e n t s o fm o d e m e n t e r p r i s e sa n db u s i n e s sd e v e l o p m e n t i nt h = ee n d ，w ec o m p a r e do t _ p p d mw i t ho t h e rt w or e p r e s e n t a t i v ed i s t r i b u t e d d a t am i n ；n g a l g o r i t h m sf d m a n dc e ri nt h es y n t h e t i cs i m u l a t i o n ，a n dt h er e s u i t ss h o wt h a tc h ea l g o r i t h mi n i h i sp a p e ri ss a f e r m o r ee f 艳c t i v ea n da p p li c a b l e k e y w o r d s ：d a t am i n i n g ，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 da s s o c i a t i o nr u l em i n i n g ，o b i i v i o u s t r a n s f 研p r o i o c o i 第2 负共4 4 页 中国科学技术大学硕l j 学位论义 第一章绪论 1 1 课题研究的背景 关联规则挖掘是数据挖掘技术中非常重要平有应川前景的一种技术。所谓关联规则挖 掘，就是从人量数据中发现项集之间的有剧的关联或相关联系，或从人鼍事务记录中发现有 用的关联关系，可以帮助企业决策者制定商务决策。 近年来，由于社会的发展以及人们对于隐私安全的重视，对于关联规则挖掘技术的要 求越来越高，主要表现为： ( 1 ) 企业规模的扩大。使用关联规则挖掘的企业规模扩人，犬多都有很多分支机构， 而各个分支机构义白成一体构成的水平分布数据库。 ( 2 ) 隐私安全变得越来越重要。 ( 3 ) 数据蕈越米越人而对丁关联规则挖拥 的效率要求越来越高。 鉴丁以上几点传统的基丁集中式数据库的犬联规则挖掘技术已经不能满足需要逐渐 地暴露出它白身的缺陷，主要表现为以卜三点： ( 1 ) 对丁有很多分支节点的数据库，如果把数据都集中在一个中心服务器上进行挖掘， 网络的传输负载会很大。 ( 2 ) 相对于分别在各个分支节点的挖掘来说，集中挖掘的效率显然很低。 ( 3 ) 数据都集中在一地的集中挖掘对于数据隐私保护很不利。 因此，设计出一套安全高效的分布式关联规则挖掘算法就尤为重要。它很人程度上决 定着整套关联规贝0 挖拥系统的成效。一套盯的分布式关联规! 1 1 0 挖掘算法土要有以卜主要特 征： ( 1 ) 准确：这是基本的要求，就是说算法得山的结果必须是准确的。 ( 2 ) 高效：土要是指算法执行的效率，由丁算法是基丁分布式数据库的所以在网络 中互相之间传送的数据量的多少就很人程度上决定了算法的效率，相互传送的数据量越少就 能使算法越高效。 ( 3 ) 安全：基于安全上的考虑，算法要阻止各站点间直接共享数据和关于数据的规则 信息，要求各个分支机构在关联规则挖掘的过程中只能得到基于自身数据得到的关联规则以 及总体的关联规则，而不能够得剑其他分支机构臼身的关联规则，从而使得每个分支机构自 身的关联规则对外是保密的。即使传递的信息泄露出玄，也不能仅从该信息推知企业的内部 具体情况，包括具体的本地规则，项集的支持度等，以免其他分支机构利川这些信息搞一些 第5 页共4 4 页 中国科学技术人学硕j ：学位论义 不正当竞争等行为。 本课题就是在这样的背景卜产生的，着眼丁现有算法的不足，设计出一套水平分布的 笑联规9 1 l j 挖捌算法，并使该算法在数据隐私保护葶l 运行效率甄方面锝剑提高。 1 2 本文所做的工作 本文土要做了以卜i ：作 ( 1 ) 阐述了分布式犬联规则挖掘算法的理论 简要介纠了数据挖掘及犬联规则挖掘的基本概念，着重阐述了分布式关联规则挖掘的概 念及有关理论，并对现有的分布式关联规则挖掘算法作了详细的分析。 ( 2 ) 介绍了目前常用的保护隐私的方法 对现有数据挖掘应j j 中采用的技术和各种隐私保护算法分别作了详细的分析，介幺f 各自 的原理，分析其优点剐缺点，前指出其各臼不同的适川范同。 ( 3 ) 设计一套保护隐私的分布式艾联规则挖掘算法 本文设计了一套保护隐私的分布式大联规则挖掘算法，保证了较女，的远行效率，安全地 产生最终的计算结果。经过实验比对，与现有同类隐私保护方法相比，新算法表现出了较高 的安全性和运行效率。 1 3 本文结构 本文在绪论部分介绍了本课题的研究背景以及本文所做的工作。第二章介绍了数据挖 掘、关联规则挖掘以及分布式关联规则挖掘的概念、理论并列举了目前较流行的分布式荚 联规则挖掘算法，分析了它们的优缺点。第三章主要阐述现今分布式关联规则挖掘中保护隐 私常用卉勺一些方法，研究比较其原理，优缺点笛一些相关问题。第四章提出了一套新的算法 可以高效安全地得剑结果，井通过仿真实验对比分析了各种同类解决方法的效率和效果。第 五章为本文作最斤的总结，提出将来的i ：作。 1 4 本章小结 本章介幺f 了课题产生的研究背景，强凋了本文的意义。提出了本文所做的土要【：作，并 对论文的结构安排进行了简要的说明。 第6 贝共4 4 畎 中国科学技术大学硕十学位论文 第二章分布式关联规则挖掘概述 2 1 数据挖掘简介 我们处住一个信息爆炸的人时代，计算机处理能力、存储技术以及互联网络的发展极人 地提高了信息的数字化处理程度。据估计每隔二十个月信息量就会增加一倍。就如待开疆 的金矿一样，快速增k 的数据背后隐藏着许多“金子”知识，人f i j 希望通过对积累的数 据进行更高层次的分析，找出数据内部一些潜在的关系和规则，通过将“未知”变为“可知”， 将数据变为真止的财富。如银行的信用忙中心期望能够从人量的交易数据中找出优质客户的 行为特征和消费模式，以帮助寻找潜在客户、刺激客户消费并创造更多的交叉销售的机会。 再如银行的信贷管理部门。如何通过分析信贷历史纪录，来帮助设计贷款产品、指导市场营 销和贷款的发放，以降低不良贷款率和降低银行风险是他们面临的一个重大难题。这样的需 求数不胜数，涵盖了社会的方方面面。 人类的发展是一个提山问题、解决问题，并反复循环的过稃。面对上面的挑战，j 人j ： 程技术人员提山了数据挖掘技术以解决上述问题。数据挖掘义被称为数据库中的知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。可以理解为是从人餐的、不完全的、有噪声的、模 糊的和随机的实际应坩数据中，提取隐含其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过科。而从商业的角度来看，其又可以描述为按企业既定业务目标，对大量的 企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化 的先进有效的方法。数据挖掘可以达到提高市场决策能力，检验异常模式，在过去的经验基 础上预言未来趋势等的目的。在最近几年利已被数据库界所广泛研究，并在多个实际领域得 到应用。数据挖掘所发现的知识最常见的有以下四类：，“义知识( g e n e r a l i z a c i o n ) 、关联 知识( a s s o c i a t i o n ) 、分类知识( c l a s s i f i c a t i o n c l u s t e r i n g ) 利预测型知识( p r e d i c t i o n ) ， 可以看出天联规则( a s s o c i a t i o nr u l e s ) 的挖掘是其中1 卜常重要的一个研究课题。 2 2 关联规则挖掘 2 2 1 关联规则挖掘概述 在数据挖掘领域，关联规则的挖掘有着厂泛的应埘背景。关联规则的挖掘是由 r a g r a w a l 等人提出来的。关联规则是描述数据库中数据项之间某种潜在关系的规则，它己 成为数据挖掘中非常重要的一个方向。关联规则挖掘的对象一般是人型事务数据库心3 。 关联规则挖掘就是发现大量数据中项集之间有趣的关联或相关联系，它是数据挖掘中的 一个重要的课题，最近几年已被业界所广泛研究。 第7 贞共4 4 贝 中周科学技术人学f 吹i 学位论文 关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助予发现交易数据库中不 同商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影 响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。 a g r a w a l 等丁1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后 诸多的研究人员对大联规舆u 的挖掘问题进行了人繁的研究。他f f j 的1 作包括对原有的算法进 行优化，如引入随机采样、并行的思想等，以提高算法挖掘规! j ! i j 的效率，对天联规则的应用 进行推j | 引”。 2 2 z 关联规则挖掘基本概念 在1 9 9 3 年，r a g r a w a l 等人首次提出了j 关联规则的概念。其一般定义如f ： 设，= f 1 ，f 2 ，。，) 是项集，其中& ( k - l ，2 ，m ) 可以是购物篮中的物品，也可以 是保险公司的顾客。设任务相关的数据d 是事务集，其中每个事务t 是项集，使得t l 。 设a 是一个项集，且a t 。 关联规则是如一卜形式的逻辑蕴涵：aj b ac i ，bc i 且an b = 囝。芙联规则 具有如卜两个重要的属性： 支持度：尸( 彳u b ) ，即a 和b 运两个项集往事务集d 中同时出现的概率。 可行度：尸( 彳fb ) ，即在出现项集a 的事务集d 中，项集b 也同时出现的概率。 同时满足最小支持皮阈值和最小置信度阈值的规则称为强规则。给定一个事务集d ，挖 掘关联规则问题就是产生支持度和可信度分别人于用户给定的最小支持度和最小可信度的 关联规则，也就是产生强规则问题。 2 2 3 关联规则挖掘算法概述 由关联规则的定义，可以把关联规则挖掘分成两个阶段：一是基丁最小支持度获取频繁 项集：_ 二是佐频繁项集上基丁- 最小可信度产生芙联规则。在完成第一步后，第二步可以很自 然地得到结果。所以，关联规则的算法侧重讨论如何快速地实现第一步。 以下对当今最经典也最流行的儿种天联规则挖掘算法进行介2 f o 2 2 3 1 经典的频繁集算法a p r i o r i a f a w a l 等丁1 9 9 4 年提山了一个挖掘顾客交易数据库中项集间的关联规则的重要方法， 其核心是基r 两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联 规则。所有支持度大于最小支持度的项集称为频繁项集，简称频集他。 l 、算法的基本思想 第8 贞共4 4 炙 中国科学技术人学颂i j 学位论义 p r i o r i 算法利用频繁项集的性质：频繁项集的子集也必是频繁的。利用这个性质，虽 可减少部分候选项集，但对于大规模的数据库，这远远不够：同时，该算法还有另一个很大 的开销，就是要多次扫描数据库。 首先找出所有的频集，这些项集出现的频繁性至少平预定义的最小支持度一样。然后由 频集产生强大联规则，这些规则必须满足最小支持度和最小可信度。 挖掘天联规则的总体性能由第一步决定，第二步相对容易实现。 2 、a p r i o r i 核心算法分析 为了生成所有频集，使川了递推的方法。其核心思想简要描述为：首先产生频繁卜项 集厶然斤是频繁2 一项集厶，直到有某个r 值使得t 为空，这时算法停l 卜。这里在第k 次 循环中，过程先产生候选k 项集的集合g ，g 中的每一个项集是对两个只有一个项不同的 属于厶一l 的频集做一个( k 2 ) 阶的连接来产生的。g 中的项集是用来产生频集的候选项集， 最后的频集厶必须是q 的一个子集。g 中的每个元素需在交易数据库中进行验证来决定 其是否加入厶，这里的验证过稃式算法性能的一个瓶颈。这个方法要求多次扫描可能很人 的交易数据库。即如果频集最多包含l o 个项，那么就需要扫描交易数据库l o 遍，这需要很 大的i ，o 负载。 可能产生人量的候选集，以及可能需要重复扫描数据库，是a p r i or j 算法的两人缺点。 a p r i o r i 算法利川频繁项集的性质：频繁项集集合的子集也必须是频繁的。利用这个性 质，虽可减少部分候选项集，但对于大规模的数据库，这远远是不够的；同时，该算法还有 另外一个很大的开销，就是要多次扫描数据库。 a p r or 算法有如下特点： ( 1 ) a p r i o r i 算法需多次扫描数据库。所以，其改进的一个方向是减少数据库扫描的次数。 ( 2 ) ap r or i 算法产生人颦的候选项集，这些频繁项集的存储手l l 计数的开销很人。所以 其改进的另一个方向是减少候选项集的个数。 ( 3 ) ap r i o r 算法主要操作是支持数计数可采川一些技巧米改进支持数计数。 针对a p r i o r i 算法的上述特点，对a p r i o r i 算法有以卜儿个方向的改进。 对于减少数据库扫描次数这个改进方向，提山了d i c ( d y f l a m i cit e m s e tc o u n t i n g ) 算 法，以减少扫描次数，这里利用频繁项集性质：一个k 一项频繁项集的所有k l 阶子项集都 是频繁项集。 第9 负共4 4 页 中冈f ： 学技术人学倾i j 学位论文 另外可以把数据库分成小块，然后逐次调入内存，第一遍扫描时，根据支持度在每个子 块上的分配，对每个子块应用a p r i o r i 算法；第二遍扫描。着眼丁全局频繁项集的搜索。每 个全局频繁项集必在子块上是频繁的，根据这个性质，第二遍只在第一遍扫描所得频繁项集 的结果中进行搜索。但该算法在最小支持度较小时，效果不好。 另一种改进是利用抽样。它不是将算法直接作用于整个数据库，而是作j i ! j 丁数据库的样 本。然后扫描整个数据库，以确定样本上的频繁项集是否在整体上也频繁。在有些情况卜j ， 该方法作j j 丁抽样数据库时，不能产生所有候选项集。 在减少候选项集的这个方向上，提出了d h p 算法，它是一个基丁哈希修剪技术的算法。 特别在产生候选2 一项集时。其数目比以前的方法少了很多，不过其中哈希函数的有效选取 是一个难点。 2 2 3 2f p 一树频集算法 针对a p r i o r i 算法的剧有缺陷，j h a n 等提出了不产生候选挖掘频繁项集的方法f p 一 树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频繁项集压缩成 一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息，然后再将f p t r e e 分化成一些 条件苦。每个库雨i 一个长度为1 的频繁项集相犬，然后雨对这些条什库分别进行挖掘。当原 始数据鼙很人的时候，也可以结合划分的方法，侵得一个f p t r e e 可以放入土存中。实验表 明，f p g r o w t h 对不同艮度的规则都有很好的适庶性，同时住效率上较之a p r i o r i 算法有巨 人的提高。 2 2 3 3其他挖掘算法 自从提出a p r i o r i 算法之后，许多研究学者在此算法的基础上，就如何减少扫描次数以 及在内存一定的情况下，如何减少读取数据库的i o 次数上进行了深入的研究。 d i p 算法“”是a p r i o r i 算法的扩展，其主要思想使采用了h a s h 技术，在生成厶的同时， 对每一个事务也生成其包含的所有2 阶项集，并通过计算将这些项集放剑散列表的某个存储 队列当中，最终如果存储队列的计数器数值小丁最小支持数，那么此队列中的2 阶项集就不 会成为频繁j 页集，利川这种方法可以使生成的候选集数荜显并减少。在d h p 算法中，散列 函数直接影响候选项集在散列表中的计数效率，换句话说散列表的人小直接影响算法运行 的效率。d h p 算法的缺点之一是存放项集计数值的散列树与存放候选项集的敞列表之间存 在内存争刖的问题，而且d h p 算法中使用的散夕| j 算法本身也有冲突处理问题，即不同的候 选项集映射剑散列表中的地址相同时如何处理的问题。d h p 算法中没置了散列桶，将产生 第1 0 页共4 4 贞 中因科学投术人学顺i 学位论义 冲突的候选项集放入桶中前增加对应的桶计数，但是当桶计数人丁最小支持度闽值时还需另 外判断其中的每个候选项集是否满足最小支持度闽值。 p a r t i t i o n 算法f 5 j 将数据库分成若干部分，先分别找出每一个部分的频繁项集的集合 然后将这些局部频繁项集集合在一起，对数据库进行扫描，计算并得到最终的频繁项集。由 于数据库分成了若干个部分，而每一部分能在内存中高效处理，冈此整个算法只需要扫描数 据库两次，人人降低了i o 所需要的时间。 动态数据项集二算法( d i c ) 允许候选数据项集在循环的任一点开始计算，直剑卜次循 环的同一点，由丁d l c 算法的动态特征，它适用丁并行化雨i 增苗开采。 2 3分布式关联规则挖掘概述 人们对丁集中式关联规则挖掘技术已经进行了很多研究，而且提出了很多算法。但是， 对于基于分布式数据库上的关联规则挖掘还是很少有人研究，而考虑到通信负载等的问题， 在分布式环境下应用集中式关联规则挖掘算法效率是很差的。所以，专门设计分布式关联规 则挖掘算法是非常有必要的这里就对分布式关联规则挖掘技术进 亍概述性的介绍。 2 。3 1问题描述 上面讨论过的基丁集中式数据库的关联规则挖掘问题能够扩展到分布式环境。 假定一个人即事务数据辛d b 分布在n 个站点：s ，s 2 ，r 上，把分布在这些站 点上的局部数据库表示为 d b ，d b 2 ，d b ” ，其中d b = d b u 伽2u ud 。 其中d b 。殴置在s 上( 1 i n ) 。在下面，本文将以s 来代表站点i 。 下面试一些概念的说明： ( 1 )d 和d ：总数据库d b 和局部数据库d b 的大小。 ( 2 ) x s u p 和x s u p ：对于一个给定的项集x ，二者分别为项集x 在d b 和伽。中 的支持数( 其中。如果s u p 7 个事务包含x ，那么项集x 在站点上的局部支持数为 x s u p ：x 的全局支持数为x ，s u p = x s u p 。如果x s u p s l d b j _ s d b ，那 ，= l，= l 么一个项集x 是全局频繁的。一个规则x j y 的全局可信皮为 uj ，) s u p s u p ) 。本 章以下把x s u p 称为全局支持度，把x s u p 称为住x 在站点s 的局部支持度。 第1 l 页共4 4 页 中闰科学技术人学坝l 学位论文 ( 3 ) 对丁一个给定的最小支持皮s 。如果x ，s u p s d ，那么x 即为全局频繁项集 如果工s u p s d 。，相戍的x 在站点s 上是局部频繁项集。 ( 4 ) l 表示d b 中所有全局频繁项集的集合，厶表示l 中所有的k 阶全局频繁项集 的集合，表示嬲中所有的局部频繁项集的集合，三f ( 女) 表示脚中所有的j ( 阶局部频繁 项集的集合，局部频繁项集厶l f ) 的集合包括所有在站点s 上局部频繁k 阶项集。 基丁个分布式数据库d b 的天联规则挖掘问题就能够被转化为寻找所有的全局频繁 项集的问题，也就是说找剑所有全局支持度和全局可信皮都高丁全局最小支持度平全局最小 可信度的规则。分布式犬联规则挖捌的目标是对丁k 1 ，找纠集合厶，计算出这些项集的 支持度帚f 可信度然后根据这些项集得出关联规则，而这些芙联规则是根据给定的最小支持 度和可信度计算出来的。 2 3 2 定理描述 在讨论怎样产生一个相对较小的候选项集的集合之前，让我们首先来看一个有趣和有用 的观点。人们已经发现由a p r i o r i 算法生成候选项集的集合中有许多候选项集在搜索频繁项 集的过群中是不需要的。实际上，在每个局部站点上都存住一个自然而且1 f 常有效的方法来 生成它臼己的候选项集集合。所以，根据前面所述，每个站点只需要除去一些不需要的候选 项集，然厉住经过削减后的候选项集集合中寻找频繁项集即可。通过以上技术。我1 i j 就能够 在各个局部战点上对丁局部数据库进行有效的并行分割。 以下，本文借鉴了 6 中的儿个定理平i j 结论米描述利说明以上的观点。 定理一：如果一个项集x 在站点s 上是频繁项集，那么它的所有子项集在战点s 。上也 是局部频繁的。 证明：这是依据局部频繁项集的定义得出的。 定理二：如果一个项集x 是全局频繁的。那么就存在一个站点s 7 ( i i s n ) ，在这个 站点上x 和它的所有子项集都是局部频繁项集。 证明：如果对- r - 1 ，n x s up j s d7 那么x s u p l ，所有k 阶频繁项集厶的集合是集合c 以的一个子集。 证明：由定理五和上面的讨论得出。 因此在结论一中每个爿：幺一l 是厶一i 的一个子集，c 日t 中的候选项集的数量通常比在 c 以中产生的要少。 可以看出相对丁直接在厶上廊h ja p r i o r i - g e n 算法产生的候选项集的集合，这个候选项 集的集合要小得多了。 2 4现有分布式关联规则挖掘算法概述 2 4 1分布式关联规则挖掘算法概述 目前人彳j 对丁分布式关联规则挖掘研究得不太多，现有被证明比较有效的有二种算法， 它们分别是p d m 、c d 和f d m ，卜面分别简略介绍一下。 l 、p d m 算法 p d m 算法是d h p 算法思想在分布式数据库环境下的戍用，每个站点通过与其他站点 交换它们的候选项集的支持数来计算出全局频繁项集的集合，由丁采用了h a s f l 技术，所有 的站点必须j 橘h a l s h 结果，而这就引起了庞人数晕的信息交换，所以p d m 算法采j i = j 了 种技术来减少交换的信息的数苗，这就匙住所有的h a s h 桶中间，只有那些桶中计数人丁 个给定阂值的桶中的项集可以来进彳了交换这样就不是所有的项集都进行交换了，从而减少 了信息交换的数链。其中每个站点都要住每次迭代斤向其他站点j 播臼己的信息。总的来说， 算法的主要思想趋每个站点局部采心h a s h 技术，在每次迭代后通过交换那些桶中计数人 于一个给定阂值的h a s h 桶中的项集来算山全局的频繁项集，而其中对丁交换的候选项集进 行了选择以减少候选项集的数量。 优点： ( 1 ) 由r 采用了局部h a s h 技术，局部得到候选项集的效率有所提高。 ( 2 ) 由下削减了站点间传输的局部候选项集数量，使得网络交换减少，整个算法效率 有所提高。 缺点： ( 1 ) 为了找刨全局候选频繁项集的集合。每个候选项集需要d ( 行2 ) 的代价米交换支持 第1 4 灭共4 4 贞 中固科学技术人学颂。j j 学位论文 数，这就造成1 r 点间交换信息苗过多，从而使得网络的负载太人。 ( 2 ) 候选项集的精简只在第二次迭代中米做在其他迭代中候选项集的数目可能会很 大。 ( 3 ) 没有笑注安全性问题，每个：竹点的关联规则信息是公开的。 2 、c d 算法【7 j c d 算法是a p r i or i 算法思想在分布式数据库环境下的麻刚，在每次迭代中，它通过在 先前迭代中发现的频繁项集集合中运行a 州o r i g e n 函数来在每个站点产生候选项集集合。 每个站点然后计算出本地所有候选集的支持数，广播给所有其他站点，最后所有：肖点都能够 为那次迭代找到全局频繁项集，进入下次迭代。 优点： ( 1 ) c d 算法的交换模式比较简单。 缺点： ( i ) 1 ，点间交换信息拦过多，网络负载过人效率降低。 【2 ) 候选项集数可能过多，削减得不够。 ( 3 ) 没有关注安全性问题，每个：符点的关联规则信息是公开的。 3 、f d m 算法8 】 f m a 算法是目前综合性能比较好的一个算法，f d m 算法主要是基丁之前算法的两个特 性来进行改进而提l 山的。它们是： ( 1 ) a p r i o r i 算法和d h p 算法都是通过在前一次迭代过程中发现的频繁项集的集 合上应川a p r i o r i g e n 函数米产生候选项集的集合的。c d 算法雨jp d m 算法在分布式环境卜 也采h | 了同样的技术米产生候选项集的集合。f d m 算法采刚了一个新的技术米产生相对较 少的候选项集的集合。 ( 2 ) 在f d m 算法中，要决定一个候选项集十分是频繁项集，只需要o ( n ) 的消 息需要进行支持数交换。 优点： ( 1 )每次迭代过程中产生的候选项集数量比前两种算法更少。 ( 2 ) 只需要o ( n ) 来进行支持率交换生成频繁项集。 缺点： ( 1 ) 候选项集的数量相比丁要求的数茧来说还是比较多，还是可以减少的。 ( 2 ) 没有关注安全性问题每个1 r 点的天联规则信息是公开的。 第l5 炙共4 4 炙 中国科学技术火学硕士学位论义 2 4 2 现有分布式关联规则挖掘算法的分析 通过以上对二种现有的分布式犬联规抛0 挖瘌算法的介纠，可以看出现在人f j 在这个技术 领域上的研究还不成熟，有很多需要改进和天注的地方。 现有的被证明比较有效的= 种算法p d m 、c d 和f d m ，通过上面对它f f j 所作的介2 “和 优缺点分析，可以总结山它们的一些共性缺点，如卜： l 、高效性方面 ( 】) 局部候选项集的削减 三种算法中有两种算法采用技术来削减局部候选项集的数鼙。c o 算法直接采用 a p r i o n 算法产生局部候选项集，没有采取特殊的削减措施；p d m 在c d 算法的基础上采用 h a s h 技术来削减局部候选项集的数量；f d m 算法在c d 算法的基础上，义提出了一些总结 的定理和推理。然后以这些理论为基础，采刚了特殊的局部候选项集的修剪策略：对丁每个 候选项集集合中的候选项集x c 何，如果x 在站点s 7 上不是局部频繁项，那么它就被修 剪掉，剩余的候选项集保存在厶( 女l 中。以上修剪只是将) ( 从站点s 上移玄，x 还可能是 其他站点的候选项集。 但是基丁目前的情况爿说，局部候选项集的数量还是过多，这一重要缺陷使得分布式关 联规则挖掘算法的效率要想提高非常l i j 难，这样进一步的修剪局部候选项集就成为今后需要 改进的主要方向和切入点。 ( 2 ) 生成全局频繁项 通过在各个。节点之间交换局部候选频繁项集的局部至成都来搜集到的候选频繁项集的 全局支持皮，然后得到全局频繁项集，这是三种算法统一采川的方法，但是住由局部频繁项 集生成全局频繁项集的过程中它们都没有采川任何措施米提高效率，而实际上，如果在头儿 次迭代过程中进 于全局候选项集的削减，那么箅法的效率会得剑进一步的提高。 2 、安全性方面 在当今社会中，人们对安全的要求越来越高，很多数据以及由数据得出的一些知识属丁 商业机密，是不允许外传的，也叫做数据隐私保护，专有名词为p r i v a c y - p r e s e r v i n g 。 具体到现在所讨论的分布式关联规则挖掘算法，由丁要处理的是分布在很多独立数据库 服务器上的数据，而每个分支机构所管理的数据又都是自成一体的，也就是独立的，所以基 于安全上的考虑，就要求每个分支机构在关联规则挖掘的过程中只能够得剑基丁自身数据得 到的关联规则以及总规则，而不能够得剑其他分支机构的白身夫联规则，从而使得每个分支 第1 6 哽共4 4 负 中国科学技术大学硕1 j 学位论文 机构自身的关联规则对外是保密的，以免其他分支机构利用这些信息搞一些不正当竞争等行 为。 需要注意的是，现有的土要算法在安全性方面犬注的很少，基丁现有的土要算法，各个 分支机构无法做剑对臼身天联规则的隐私保密，这是一个很人的缺陷。近年来很多学者认识 到这个问题的严重性，设计了一些基丁隐私保护的分布式挖掘算法这些算法将住卜一节中 进行介绍。 2 5本章小结 本章首先简略介绍了数据挖掘和关联规则挖掘的基本知识，在介绍了现有的经典流行的 基于集中式数据库的关联规则挖掘算法之后，详细地介绍了分布式关联规则挖掘理论。本章 介绍了目前较流行的三种分布式关联规则挖掘算法：p d m 、c d 和f d m 。另外本章对丁每种算 法都进行了优缺点的分析。 第1 7 贝共4 4 。贝 中国科学技术人学硕f 。学位论义 第三章数据挖掘中的隐私保护方法概述 本章主要介绍目前在分布式数据挖掘中经常使用的一些保护隐私的方法，并对这些方 法的基本思想、应异j i 范围、优缺点作一个概括的说明。 3 1集中式数据挖掘的隐私保护方法 一般米说，在集中式环境中考虑隐私保护问题多| ，采川的是变更数据方法，而且经过 这种变更后的数据可以在集合水平上重构其分布特征。变更数据的方法主要是通过修改需要 公开的原始数据库，并且发布修改后的数据库米实现合理的隐私保护等级。数据变换的方法 主要包括以卜儿种 9 1 ：隐藏、阻隔、聚合、互换和抽样。 3 1 1 启发式方法 有鉴于选择性数据变换和清理是n p h a r d 问题，人们开发了许多启发式方法来解决复 杂度的问题其适刚丁诸如，分类、关联规则和聚类等数据挖掘技术当中。 3 1 1 i 关联规则隐藏 m i k ej a i a l i a h 等人在【1 0 】中提出为了在大联规则挖掘中隐藏敏感频繁项集的最优化数 据清理是一个n p h a r d 问题。他们的l ：作可以贝体描述如卜：令s 表示数据源，月代表可 以从s 中挖捌出的一组重要规则且令忍表示尺中的一个规则子集。问题可以转化为，我 l j 如何通过将s 转换为s ，在只发布s 前提7 卜仍然可以挖掘出 r 嘞) 。研究人员这里提山了基 于数据隐藏的变换方法，具体地说，该过程是将选定的l 值和o 值集合进行改变使得敏感规 则的支持度小丁某个阈值，该闽值使得发布数据集合效用最大化。这里的效用可以通过被隐 藏的非敏感规则数量来衡量( 数据变换的副作用) 。 随后在【1 l 】中e l e n ad a s s e n i 等人将敏感频繁项集的数据清理扩展到了对丁敏感规则的 处理。其方法是通过隐藏频繁多项集或者是使得敏感规则的置信度小丁- 用户臼定义的闽值来 防j 卜敏感规则通过推理而获得。在文献【1 2 】中，研究人员在前人的基础上着眼丁隐私和信息 披露之间的平衡，试图将偶然的1 f 敏感规则隐藏平| f 数据变换对交易记录的影响控制剑最小。 3 1 1 2 关联规则阻隔 在关联规则挖掘中使孀较多的方法就是龃隔，即用问号米替换数据项的某个属性值i j 3 j 。 这种将实际值川未知值替换而不是放置一个伪值的方法1 r 常适合某些如医学等方面的具体 应用。在文献【1 4 】中，y u c e is a y g i n 等人将阻隔方法引入了关联规_ ! i ! 发掘。由r 加入了问号 这个新值，关联规则的支持度和置信度计数的定义都需要做些改变：最小置信度和支持度 第1 8 贸共4 4 页 中因科学技术人学坝 学位论文 将变为最小置信和支持区间。在这种前提下，认为只要某个敏感规则的支持度和置信度低于 对应区间的中值，则该规则的私密性没有被侵犯。关于该方法中规则的重构效率细节可以参 考文献【1 5 】。 3 1 1 3 分类规则阻隔 人们注意剑在分类规则挖掘的框架中，数据库管理员从保护隐私的角度出发必须阻隔分 类标签值1 1 6 。这项f ：作的土要内容之就是要确定获得的私密性是否值得所损火的数据功 能性。具体一点的做法就是，改定一个参数口，0 伊i ，并放置在傲阻隔的数值位置上。该 参数代表属性取某可能值的概率，接着计算初始熵值和阻隔后的信息熵值并将它们两者的差 与决策树产生的规则的置信度减少相比较，从而判断增加的安全性是否值得付出数据效用减 小的代价。 3 1 2 重构方法 近年来研究人员提出了系列通过扰动数据和在集合水平上重构数据分布来保持隐私 的挖掘技术方法。以下文中我们列举了几种并加以介绍。 3 1 2 1 数字型数据重构 从个体记录已被搅动的训练样本中构造分类决策树的问题可以参考文献【1 7 】，鉴丁精确 估计单个数据记录的原始值是不太可能的，该文献中r a g r a w a f 等人提出了可以精确倩计 原始数据值分布的重构方法。通过使川重构的分布，可以建立分类判别器，其精度可以与直 接从原始数据得来的判别器相媲美。研究人员考虑了两种思路来扭曲属性值，种是离散化 方法；另一种是值变形方法。同时对丁原始分布的重构，使用了贝叶斯方法并提出了二个建 立精确决策树的算法。这些算法使用的都是重构的数据分布。 在另一篇文献中，d a g r a w a i 等人对基于贝叶斯的重构方法使用最大划望法( e m ， e x p e c t a t i o nm a x i m i z a t i o n ) 进行了改进：同时证明了e m 算法收敛丁搅动数据原始分布的最人 似然估计f 体l 。e m 算法在使用于海餐数据时，其对丁原始数据集合可以提供更住的鲁棒估计 ( r o b u s te s t i m a r e ) 。同时研究中还表明，当挖捌者通过累积重构分布可以获得更多知识的时候。 文献f 2 5 】中的隐私性估计实际要更加低一些。 3 1 2 2二元，分类数据重构 前人对丁分类和二元数据的研究集中在关联规则的背景卜【1 9 2 0 1 。尽管使川全局随机化处 理可以保护隐私并重新获得关联规则，但是挖掘所得的规则可以用来窥探隐私漏洞。为了规 避此类风险，研