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

哈尔滨工程大学硕士学位论文 摘要 数据挖掘是指从大型数据库或数据仓库中提取人们感兴趣的知识。随着 数据库技术和网络技术的发展，人们日益关心数据挖掘过程中隐私数据的安 全性问题。隐私保护的关联规则挖掘成为数据挖掘领域的一个新兴的研究方 向。 本文提出的po 伽a 算法以d m a 算法为基础，对其在存储空间、挖掘效率、 安全性方面作了相关的改进。首先，本文使用二进制压缩编码技术对数据库 中的所有事务集进行编码，降低了事务的存储空间，提高了挖掘算法的处理 速度。在数据挖据的效率方面，本文采用剪裁事务数据库的方法削减事务集 中非频繁的项目集，缩短了每个事务的长度。通过合并重复的事务减少了事 务集的扫描次数和存储空间，达到了提高数据挖掘效率、降低空间复杂度的 目的。在对数据的隐私保护方面，本文采用r s a 加密与同态加密相结合的加 密方案，该方案综合考虑了数据加密的安全性和加密算法的高效性，达到了 效率与安全的平衡。 其次，本文在关联规则的筛选方法进行相关的改进，提出了基于“提升 度”关联规则选取方法。最后，本文针对p _ o d m a 算法的特点，采用一种改进 的全局主站技术作为算法的实现架构。 关键词：分布式；关联规则；隐私保护；加密；数据挖掘 一 堕玺鎏三堡盔兰鎏圭兰垡鎏兰 a b s t r a c t d a t am i n i n gi sc o n s i d e r e dt oe x t r d e tt h ei n t e r e s t e dk n o w l e d g ef r o ml a r g e d a t a b a s e so rd a t aw a r e h o u s e s w i t ht h ed e v e l o p m e n to fd a t a b a s ea n dn e t w o r k t e c h n o l o g y , t h e r ei sg r o w i n gc o l l c e mf o rt h es e c u r i t yi s s u e so f p r i v a c yd a t ai nd a t a m i n i n gp r o c e s s p r i v a c y - p r e s e r v i n gd a t am i n i n go f a s s o c i a t i o nr u l e si nd i s t r i b u t e d d a t a b a s ei sb e c o m et h en e wd i r e c t i o ni 1 1d a t am i n i n gf i e l d t h ep _ o d m aa l g o r i t h mi sp r o p o s e di nt h i st h e s i st h a ti sb a s e do nt h ed m a a l g o r i t h ma n di m p r o v e s8 0 m ea s p e c t s ，s u c ha ss t o r a g es p a c e ，d a t am i n i n g e f f i c i e n c ya n ds e c u r i t y f i r s t l y , t h eb i n a r yc o d i n gt e c h n o l o g yi su s e dt oc o d ea l l t h et r a n s a c t i o ns e ti i lt h ed a t a b a s e t h es t o r a g es p a c eo f t r a n s a c t i o ni sl o w e r e da n d t h es p e e do fd a t am i n i n ga l g o r i t h mi si m p r o v e d i nt h ea s p e c t so fd a t am i n i n g e f f i c i e n c y , t h el e n g t ho ft r a n s a c t i o ni ss h o r t e n e db yp r u n i n gt h en o n - f r e q u e n t i t e m s e to ft r a n s a c t i o nd a t a b a s e 1 1 璩s c a nt i m ea n ds t o r a g es d a c eo ft r a n s a c t i o n i t e m s c ta r er e d u c e db ym e r g i n gt h ei t e r a t i o nt r a n s a c t i o n , w h i c hr e a c ht h eo b j e c to f a 。n p r o w 。n gt h ed a t am i n i n ge f f i c i e n c ya n dr e d u c i n gt h ec o m p l e x c yo f s p a c e i nt h e a s p e c to fd a t am i n i n gp r i v a c y - p r e s e r v i n g , t h es c h e m eo fc o m b i n i n gt h er s aa n d h e si sa d o p t e d , t h es e c u r i t yo fd a t ae n c r y p t i o na n dt h ee f f i c i e n c yo fe n c r y p t i o n a l g o r i t h ma c o n s i d e di nt h i ss c h e m e a n di t r e a c h e st h eb a l a n c eb e w e e n e f f i c i e n c ya n ds e c u r i t y s e c o n d l y , t h ef i l t e rm e t h o do fa s s o c i a t i o nr u l e si si m p r o v e da n dt h en e w f i l t e rm e t h o db a s e do n ”u p g r a d e ”i sp r o p o s e d f i n a l l y a c c o r d i n gt ot h ep r o p e r t y o fp o d m aa l g o r i t h m , t h eg o l b a lm a i ns i t et e e h n o l e g yi sa d o p t e dt or e a c ht h e f r a m e w o r ko f a l g o r i t h m k e y w o r d s ：d a t am i n i n g , a s s o c i a t i o nr u l e s ，d i s t r i b u t e d ，p r i v a c y - p r e s e r v i n g , e n c r y p t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献等的 引用已在文中指出，并与参考文献相对应。除文中已经注明 引用的内容外，本论文不包含任何其他个人或集体已经公开 发表的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 作者( 签字) 邀i 赵 日期：矽7 年p 月衫日 哈尔滨工程大学硕士学位论文 1 1 课题背景 第1 章绪论 关联规则数据挖掘是数据挖掘技术中非常重要且应用极为广泛的一种技 术，它在商业决策、检测异常模式等方面都有广泛的应用。所谓关联规则挖掘， 就是发现大量数据中项集之问有用的关联或相关联系，从而制定正确的商务 决策n ，。 近几年，由于网络技术的发展，企业之间的联系也越来越多的通过网络 来实现，这也促使了人们对网络安全隐私的重视，与此同时对一个企业进行 关联规则的挖掘也呈现出新的变化，主要有以下几点m ； ( 1 ) 挖掘对象规模的扩大：使用关联规则挖掘的企业规模在日益扩大， 它们大都有很多分支机构，而且各个分支机构自成一体，独立核算。 ( 2 ) 安全隐私变得越来越重要：在市场竞争中，即使是同一企业的各个 分支机构也可能是独立核算自负盈亏的，它们不允许自己的数据在数据挖掘 中产生泄漏，因而数据的安全和隐私保护对企业日益重要。 ( 3 ) 数据量越来越大：现在的企业数据都是海量数据库，而且要在网络 上传输，因而企业对于关联规则挖掘的效率以及减少网络带宽占用量极为关 心。 鉴于以上几点，传统的基于集中式数据库的关联规则挖掘技术已经不能 满足当前的需要，暴露出的缺陷主要有以下几点： ( 1 ) 现有的分布式关联规则挖掘算法对网络流量考虑很少且单个站点的 挖掘效率存在可改进之处。 ( 2 ) 对大规模数据的空间占有问题没有很好的处理，空间复杂度高。 ( 3 ) 数据直接在网络上传输没有考虑隐私保护。 这样设计出一套基于隐私保护的高效的分布式关联规则挖掘算法就显得 尤为重要，因为算法的好坏很大程度上决定了整个数据挖掘系统的成败。一 个好的分布式关联规则挖掘算法主要有以下三个主要特性： 哈尔滨工程大学硕士学位论文 ( 1 ) 准确：这是基本的要求，就是说算法得出的结果必须是准确的，是 满足用户需求的。现有的主要算法在这方面是可以满足要求的，但在最后挖 掘出的结果集的选取上还存在一些问题，所以本文设计一个算法对结果集进 行更准确的筛选。 ( 2 ) 高效：主要指算法执行的效率。由于算法是基于分布式数据库的， 所以在网络中互相之间传送数据量的多少很大程度上决定了算法的效率，因 而本文采用一个改进方法减少网络传输的通讯代价。 ( 3 ) 安全( p r i v a c y - p r e s e r v i n g ) ：在当今社会中，人们对安全的要求越来越 高，很多数据属于商业机密，不允许外传。这要求即使是同一个公司的分支 机构在关联规则的挖掘过程中也只能得到基于自身数据的关联规则以及整个 公司也就是总部的关联规则( 通过分布式数据库的关联规则挖掘算法得到) ， 丽不能够得到其它分支机构的关联规则，达到隐私保护的目韵m 。本文采用 数据加密的方法对隐私数据进行保护，达到安全和高效的平衡。 本论文立足于解决以上几个问题，着眼于现有算法的不足以及主要缺陷 进行改进，使分布式关联规则挖掘算法在数据的隐私保护和挖掘效率两方面 都能够得到较好的改善，最后提出基于提升度的关联规则选择标准，进一步 提升了关联规则的可靠性。 1 。2 国内外发展现状 数据库技术是计算机科学发展过程中的一个重要技术，它的发展和完善 带动了许多相关技术的发展，数据挖掘就是在数据库技术的迅速发展和数据 库管理系统的广泛应用的基础上发展和完善起来的。随着数据库容量的日益 扩大，人们考虑在这些大量的数据中是否存在一些未知的、有用的信息，数 据挖掘就是在这种需求的推动下产生的。数据挖掘技术结合了统计学、数据 库、机器学习、神经网络、模式识别、模糊数学等一系列技术。它与传统分 析工具的不同之处在于数据挖掘使用的是基于发现的方法。运用模式匹配和 其它算法找出数据之问的重要联系。数据挖掘使数据库技术进入了一个更高 级的发展阶段。 自从8 0 年代末出现数据挖掘技术以来，经过短短二十多年的发展，数据 2 哈尔滨工程大学硕士学位论文 挖掘技术已经发展为包括多个分支，采用多种技术的一门综合性学科。它广 泛应用于零售业的购物篮分析、金融风险预测、产品质量分析、通讯及医疗 服务、基因工程研究等许多领域。在数据挖掘的多个分支中，关联规则挖掘 是数据挖掘的一个重要研究方向，它是由a g r a w a l 、i m i e l i n s k i 和s w a m i 于1 9 9 3 年提出的m ，关联规则挖掘用于发现交易数据库中不同项目集之间的关系， 借此反映用户的购买模式。1 9 9 4 年，第一个关联规则挖掘算法a p r i o r i 算法正 式提出，该算法的提出标志着关联规则挖掘已经从一种设想发展到算法阶段。 但是，a p r i o r i 算法只是对关联规则挖掘思想的初步实现，该算法在挖掘效率、 f o 代价方面存在诸多不足。为此，许多研究人员针对a p r i o r i 算法的不足提出 了许多改进算法，主要有以下几种： ( 1 ) 采用散列技术减少候选项目集的d h p 算法； ( 2 ) 采用划分技术减少数据库扫描次数的p a r t i t i o n 改进算法； ( 3 ) 采用取样技术提高挖掘效率的改进算法： ( 4 ) 采用动态计算技术实现并行计算的改进算法； ( 5 ) 不生成候选集的f p 树频集算法； 随着网络技术和并行计算技术的快速发展，数据库被应用到网络和分布 式环境下，为了适应应用环境的变化，数据挖掘技术也进行了相应的改变， 传统的基于集中式环境下的数据挖掘技术己不再适应新的环境，因而产生了 分布式关联规则挖掘算法。根据应用环境的不同，现有的分布式关联规则挖 掘算法主要分为两类：一是在并行环境下，典型算法是算法p d m ( p a r a l l e ld a t a m i m n g ) 算法；另一类是在网络换境下，包括局域网和广域网，典型的算法为 频度分布算法c d ( c o u n td i s t r i b u t i o n ) 和d m a ( d i s t r i b u t e dm i n i n ga s s o c i a t e d r u l e s ) 算法。网络环境下的关联规则挖掘算法相对于集中式环境下的一个明显 区别是：在网络换境下对一个挖掘算法的评价指标更加广泛，除了挖掘算法 应具有较高的挖掘效率外，在网络中信息的通信量成为评价一个算法优劣的 重要标准。在上诉提到几种分布式关联规则挖掘算法中，挖掘效率较高，通 讯代价较少的是d m a 算法，该算法采用了候选集削减技术减少了挖掘过程中 的候选集，同时它的通讯复杂度为o ( 1 1 ) ，这相对于c d 算法的o ( n 2 ) 的通讯复杂 度有了较大幅度的改进。 鉴于在网络环境下传数据输的不安全，很多在网络上传输的数据会遭到 3 哈尔滨工程大学硕士学位论文 窃听、篡改等恶意操作，如果在网络环境中直接使用数据挖掘技术会导致隐 稻数据遭到泄露。而且现在的企业在进行数据挖掘的过程中希望自己分支机 构的数据相互保密，不会因为数据挖掘导致相互信息的公开，针对这种要求， a g r a w a l 和s r i k a n t 于2 0 0 0 年首先提出了对数据挖掘进行隐私保护的概念。 所谓隐私保护就是采用某种措施使数据挖掘过程中产生的频繁集、关联 规则等敏感数据不对外公开，保证数据挖掘过程的可靠性，避免由于信息的 泄露给参与挖掘的数据主体带来的损失。隐私保护技术从提出开始就受到广 泛的关注，因为它能解决目前数据挖掘领域比较棘手的安全性问题，但由于 该研究方向提出的时间不长，国内外对其进行的研究还不是非常多。就目前 来说，对数据挖掘进行隐私保护的主要措施有以下两点： ( 1 ) 在待挖掘的数据库中加入某些与实际数据不相关的干扰数据，由于 干扰数据的加入，破坏了原有数据的正确信息结构，从而破坏了原有数据的 正确性，使信息即使泄露也是无效数据。但是在数据挖掘过程中，通过某些 措施识别这些干扰数据，不会对数据挖掘的结果产生负面影响，从而达到了 隐私保护的目的。 ( 2 ) 对需要保密的数据在挖掘过程中进行加密。数据的加密保证了其在 网络上传输的安全性，从而保证了挖掘结果不产生泄露，目前对数据挖掘进 行加密的方法主要有安全多方计算、公钥加密等，每种加密方式都有其自身 的优缺点，并适合在某种环境下使用，如安全多方计算不适合站点频繁变化 的场合，而公钥加密的速度比较慢。 可见隐私保护的关联规则挖掘是当前数据挖掘领域一个新兴的研究方 向，它不但对于解决当前数据挖掘领域的问题具有一定的指导作用，而且是 计算机和网络技术发展的需要，具有一定的研究价值和实用价值。 1 3 本文所做的工作 本文所做的工作主要有以下几点： ( 1 ) 介绍了关联规则挖掘、分布式关联规则挖掘的基本理论及算法。 ( 2 ) 介绍了隐私保护数据挖掘的发展动向。 ( 3 ) 介绍了密码学的基本理论和目前流行的几种加密算法。 4 哈尔滨工程大学硕士学位论文 ( 4 ) 分析比较了现有分布式关联规则挖掘算法各自的优缺点。 ( 5 ) 介绍了目前通用的关联规则的评价标准及存在的问题，并提出了一 种改进的评价方法。 ( 6 ) 针对目前算法在挖掘效率和隐私保护方面的不足提出了一种基于隐 私保护的优化的分布式关联规则挖掘算法。 ( 7 ) 在以上算法改进的基础上构建一个基于隐私保护的分布式关联规则 挖掘的实现框架。 1 4 本文结构和组织 全文共分五章。具体的结构为： 第l 章绪论。 介绍本文的研究背景、意义、主要内容以及结构组织。 第2 章分布式关联规则挖掘算法概述。 阐述了关联规则挖掘和分布式关联规则挖掘中的一些基本理论和相关研 究，对目前比较有效的三种算法的优缺点进行了简要的分析，明确了算法改 进的方向，同时也对隐私保护关联规则挖掘做了简要的介绍。 第3 章密码学及加密算法概述。 介绍了密码编码学、安全多方计算理论和基于网络的加密算法。 第4 章po d m a 算法的设计及分析。 针对现有算法的缺陷提出po d m a 算法，算法分别在效率和安全性两 方面对现有算法进行了改进，并用实例说明算法的效果。在本章的最后，提 出了基于提升度的关联规则筛选算法，进一步提高了整个算法的准确性。 第5 章po d m a 算法的实现方案 介绍了分布式环境下数据挖据的两种实现方案，根据po d m a 算法的 特点采用改进的全局主站式实现方案作为算法的实现架构。 第2 章分布式关联规则挖掘算法概述 本章阐述了关联规则挖掘和分布式关联规则挖掘中的一些基本理论和相 关研究，总结了三种主流算法的优缺点，并对已有的隐私保护算法加以简要 的介绍，最后提出相关的改进思路。 2 1 数据挖掘 数据挖掘“1 又被称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) ，是指从大型数据库或数据仓库中提取人们感兴趣的知识。这些知 识是隐含的、事先未知的，潜在的有用信息，提取的知识一般可表示为概念 ( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式”。通 过数据挖掘可以达到提高市场决策能力、检测异常模式、在过去的经验基础 上预言未来趋势等目的。数据挖掘技术结合了多门学科的知识：它用数据库 管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的 知识。它涉及到多个领域，包括机器学习、模式识别、归纳推理、统计学、 数据库、数据可视化等。知识发现一般由三个主要阶段组成：数据准备、数据 挖掘、结果的解释评估m ，如图2 1 所示。 图2 1 数据挖掘的过程 数据准备通过数据选取、数据预处理和数据变换三个子过程来完成，经 过数据准备之后数据就变成比较适合挖掘的形式。数据挖掘是知识发现的关 6 哈尔滨工程大学硕士学位论文 键步骤，它采用某一种数据挖掘算法来发现关联规则、分类等。经过数据挖 掘得到的模式必须经过用户或机器的评估，因为有些模式是无意义的或无效 的，它可能满足不了用户的需求所以需要将其剔除。结果的解释评估保证了 挖掘出的模式能最大限度的满足用户的要求。数据挖掘所发现的知识最常见 的有以下四类：广义知识( o c n e r a j i z a t 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 ) 和预测型知识( p r e d i c t i o n ) 。数据挖掘技术的技术很多，根 据发现的知识种类可分为：关联规则发现、分类或预测模型知识发现、数据聚 类、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等“1 。 2 2 关联规则挖掘 2 2 1 关联规则挖掘概述 在数据挖掘领域，关联规则挖掘“”唷着广泛的应用背景，关联规则挖掘 是由i l a g r a w a l 等人提出来的。关联规则是描述数据库中数据项之间某种潜 在关系的规则，它己成为数据挖掘中一个非常重要的研究方向。关联规则挖 掘的对象一般是大型事务数据库，目的是发现大量数据中项集之间有趣的关 联或相关联系，最近几年已被业界所广泛研究。 关联规则挖掘的一个典型例子是购物篮分析。研究关联规则的目的是发 现交易数据库中不同商品( 项) 之间的联系，找出顾客购买行为模式。分析 的结果可以应用于商品货架布局、货物安排以及根据购买模式对货物进行分 类。关联规则还可以广泛应用于各个领域，既可以检验行业内长期形成的知 识模式，也能够发现隐藏的规律。有效的发现、理解、运用关联规则，是完 成数据挖掘任务的一个重要手段。 a g r a w a l 等于1 9 9 3 年首先提出挖掘顾客交易数据库中项集间的关联规则 问题，以后许多研究人员对关联规则的挖掘问题进行了大量的研究，他们的 工作包括对原有的算法进行优化，如引入随机采样、并行等思想，以提高挖 掘算法的效率，推广对关联规则的应用n 一，。 7 哈尔滨工程大学硕士学位论文 2 。2 。2 关联规则挖掘基本概念 1 9 9 3 年，r a g r a w a l 等人首次提出了关联规则的概念，其定义如下： 定义2 2 1 ：关联规则挖掘全体事务的集合记为d = “匕t k ，聃， 乜【- “幻拓知) ，k 称为事务( t r a n s a o t i o n ) 。i m ( m = j 2 痧称为项目 ( i t e m ) ，可以是购物篮中的物品，也可以是保险公司的顾客。 定义2 2 2 ：设i = i l , 6 , i j 晶) 是d 中全体项目组成的集合，i 的任何子 集x 称为d 中的项目集( i t e m s e t ) 。如果ixi = k ，则称集合x 为k 项目集 ( k - l t e m s e t ) ，设t 和x 分别为d 中的事务和项目集，如果x _ _ q t k ，则称事务 t 包含项目集x 。每一个事务都有一个唯一的标识符，称为t i d 。 定义2 2 3 ：事务集d 中包含项目集x 的事务的个数称为项目集x 的支 持数，记为o x ；项目集x 的支持度记为：s u p p o r t ( x ) = ( o 。ld1 ) + 1 0 0 其 中idi 是事务集d 的事务数，若s u p p o r t ( x ) 不小于用户指定的最小支持度 ( r a i n _ s u p p o r t ) ，则称x 为频繁项目集，也称为频集或大项目集，否则就称为 j # 频繁项目集，也称为非频集或小项目集。 关联规则是如下形式的逻辑蕴涵：a j b ，a c i ，b c i ，且a n b = o 。a 是关联规则的条件，b 是关联规则的结果。关联规则具有如下两个重要的属 性： 支持度：s - - - s u p p o r t ( a ：= b ) = p ( a u b ) ，为a 和b 这两个项集在事务集d 中同时出现的概率。即事务数据库d 中支持a u b 的事务数占整个事务数的 比例。其中最小支持度与事务数的乘积称为最小事务支持数。 置信度；e - - - v o n f i d e n c e ( a j b ) - p ( b l a ) ，即在出现项集a 的事务集d 中， 项集b 也同时出现的概率。 同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一 个事务集d ，挖掘关联规则问题就是产生支持度和置信度分别大于用户给定 的最小支持度和最小置信度的关联规则，也就是产生强规则的问题i o l | l l l m 。 2 2 3 关联规则挖掘算法概述 由关联规则的定义，可把关联规则挖掘分成两个阶段：一是基于最小支 8 哈尔滨工程大学硕士学位论文 持度采用某种挖掘算法获取频繁项集；二是在频繁项集上基于最小置信度产 生关联规则。产生频繁集是整个算法的关键，它决定了算法的效率。而第二 步虽然耗时相对较少，但一个好的评价标准对最后产生的关联规则的有效性 是非常重要的，所以有必要在挖掘出关联规则后再设计一个好的关联规则选 取算法，使挖掘结果更符合用户的要求。下文将对目前较为经典的几种关联 规则挖掘算法进行介绍。 1 经典的频集算法a p r i o r j a g r a w a l 等人于1 9 9 4 年提出了一个挖掘顾客交易数据库中项集问关联规 则的重要方法，其核心是基于两阶段频集思想的迭代算法。该关联规则属于 单维、单层、布尔关联规则。所有支持度大于最小支持度的项集称为频繁项 集。简称频集。 ( 1 ) 算法的基本思想 a p r i o r i 算法m 有一个重要性质，即频繁项集的所有非空子集也是频繁的。 它是基于如下的观察：如果项集x 不满足最小支持度阈值m i n ，则x_support 是非频繁的。如果a 添加到x ，则结果集( x u a ) 不可能比x 更频繁出现。 因此，x u a 也是非频繁的，即p ( x u a ) m m _ s u p o p t * 嘲硬 j 称x 为给定的最小支持度阈值，如果 为站点s l 上鹄局部频繁项目集。如果 x s u p m i n s u p p 。1 t + i d b l - - m i ns u p p 。r t + 艺i d b i ，则项集x 是全局频繁项目集。 h 一个规则x j y 的全局置信度为( x u y ) ，s u p x s u p 。本章以下把x s u p 称为全 局支持数，把x s u p 称为x 在站点s 的局部支持数。 哈尔滨工程大学硕士学位论文 ( 3 ) 设l 表示全局频繁项目集的集合；l k 表示全局频繁k 项目集的集合； l l 表示d b l 中所有的局部频繁项目集的集合；w 表示d b 中所有的l 【阶局 部频繁项集的集合，分布式环境下关联规则挖掘的目的就是找出所有的全局 频繁项目集，通过它们生成全局关联规则。 这样，基于分布式数据库的关联规则挖掘问题就被转化为寻找所有全局 频繁集的问题，也就是说找到所有全局支持度和全局置信度都高于全局最小 支持度和全局最小置信度的项目集，然后在这些频繁项目集上应用关联规则 的选取算法得出最终的关联规则。 2 3 2 定理及性质的描述 a p r i o r i 算法提出之后，很多人就考虑采取措施减少候选集的生成，也提 出了一些方法，如基于散列的技术就能大大压缩需要考察的k 一项目集。但是， 一味的通过候选集的削减来提升性能是有限的，还应从其它方面着手减少时 间上的开销。如可以考虑从事务集的角度进行改进，因为所有的候选集都需 要同事务集中的事务相比较。接下来对改进算法中所涉及的一些定理和性质 一”“进行阐述。 性质2 3 1 若x 是站点s 上的频繁项目集，则x 的所有子集在站点s 1 上也 是频繁的。 证明：这根据a p r i o r i 的性质显然可以得出。 性质2 3 2 若x 是全局频繁项目集，则必定存在一个站点s ( 1s i n ) ， 使得这个站点上项目集x 和它的所有子项集都是频繁项目集。 证明：使用反证法，假如不存在这样的站点s 1 使得这个站点上x 和它的 所有子集都是频繁项目集。则必有x s u p m i ns u p p o r t + i d l ，也必有 x s u p r a i n _ s u p p o r t + 羔i d b 2 i 。假设x 正， h坷 从而到羔x s u p l ，所有k 阶频繁项集k 的集合是集合 哈尔滨工程大学硕士学位论文 c 凰= uc h k 。的一个子集合。在这里，c h k = a p r i o r i _ g e n ( h l 。) 。因此。对 i 于k 阶大项集，c h k 是一个候选项集的集合。 因此在结论2 3 1 中每个脱：。是k i 的一个子集，c h k 中的候选项集的 数量通常比c k 中的要少。相对于直接在l k - l 上应用a p r i o r i _ g e n 算法产生的 候选项集的集合，这个候选项集的集合要小的多。 下面，本文以一个例子来证明结论2 3 1 的正确性。 例一：假定在一个分布式数据库d b 上有三个站点，分别为d b l ，d b 2 ， d b 3 。在第一次迭代之后，1 阶大项集的集合l l - a ，b ，c ，d ，e ，f ，g ， 其中a 、b ，c 在站点s 1 上是局部大项集，b 、c 、d 在s 2 上是局部大项集， e 、f 和g 在站点s 3 上是局部大项集。因此，皿；= a ，b ，c ) ，眦j = b ，c ，d ，z 垃；= e ，f ，g 。 按照结论2 3 1 ，在站点s 1 上的2 阶候选项集的集合等于c h ；，这里， 础：= a p f i o r i _ g e n ( 月z ；) = a b ，b c ，a c ，同样的，凹汪 b c ，c d ，b d ， c 日；= e f ，f o ，e g 。因此，二阶大项集的候选项集的集合是c h 2 - c h ：uc h ；uc h ：，而且它只有8 个候选项集。 然而，如果直接在l l 上运行a p r i o r i _ g e n ，则候选项集c 2 = a p r i o f i _ g e n ( l 1 ) 将有2 1 个候选项集，这表明结论一所描述的技术在削减候选项集上是非常有 效的。 定理2 3 2 对于眵l 的任何全局频繁k 项目集l k ，c h k l 为第i 个站点s 1 上的 k 二强项候选集，i = l ，2 n ，所有站点k 强项候选集的并集为c h k ，则必有 h 碰f 毛djc n k ，c 聊由a p 五翻吼算法产生，c h k i = a p r i o r ig e n ( h l k i t ) 。 舀 证明：在a p i r o r i 算法中，候选k 项目集c k 由a 研o f i _ g c n ( l k i ) 函数生成， 同样在站点s 1 上，也可以采用这种方法生成局部候选项目集c k ，但是由于l k 1 中包含了一些非全局频繁的项目集，因此，h t 生成的局部候选项目集c f 会比 较大。d m a 算法引入了“强项集”的概念，使得生成的候选项目集更小。在此 算法中，k - 强项候选集c h k j 可以用a p f i o f i _ g e n ( h lk 1 1 ) 函数生成。由性质2 3 5 可知，对于任何x ek ，总存在一个站点s ，使得x 的所有子集在站点s 上都是 哈尔滨工程大学硕士学位论文 强项集，因而，如果x l k ，则x h uh “，且uh l k uc h k j 。所以， 一 hh l 匿c 毛【- uc h k i = a p r i o r i _ g e n ( h l k - t ) ( 证毕) 。 一 2 3 3 现有分布式关联规则挖掘算法概述 分布式数据库的关联规则挖掘是随着网络计算和并行算法的发展而快速 发展起来的。目前人们对于基于分布式数据库的关联规则挖掘研究还不太多， 主要被分为两类：一是基于分布式多处理器的并行模式，该模式将数据库分 布在有独立处理器相连的本地磁盘上，处理器之间通过互联网络通讯来协调 它们之间的任务。这类方法还需要同步机制来协调不同处理器之间的行为， 即在每一遍扫描数据库的末尾，不同的处理器之间需要交换所考察的候选集 的支持数。典型的算法有：p d m ( p a r a l l e ld a t am i n i n g ) 算法。二是基于分布式 环境下( 如局域网，广域网) 的关联规则挖掘，典型的算法有：频度分布算 法c d ( c o u n td i s t r i b u t i o n ) 和d m a ( d i s t r i b u t e dm i n i i l ga s s o c i a t e dr u l e s ) 算 法，下面就以上提到的算法进行简要介绍。 。 1 c d 算法 c d 算法m 是将a p f i o f i 算法的思想应用在分布式数据库环境下，在每次 迭代中，它通过运行a p f i o f ig e n 函数生成每个站点的候选项集，然后每个站 点计算出本地所有候选集的支持数，广播给所有其它节点，最后得到所有节 点该次迭代的全局频繁集，进入下次迭代。 ( 1 ) 优点 c d 算法的交换模式比较简单，只需要交换各个站点间的支持数。 ( 2 ) 缺点 节点间信息传送量大，网络负载高，效率低。 挖掘过程中产生大量候选集，削减力度不够。 在交换支持数的过程中，分站点间有等待的过程，必须等待其它站点 产生各自的支持数，如果分站点的挖掘时间过长则等待的时间会更长。 没有关注安全性问题，每个节点的关联规则信息是公开的。 1 5 哈尔滨工程大学硕士学位论文 2 p d m 算法 p d m 算法n ”是将d h p 算法的思想应用在分布式数据库环境下，它是对 c d 算法的改进。每个站点通过与其它站点交换候选项集的支持数( 或者在 一些迭代过程中提到的数量) 来计算全局大项集。算法的主要思想是：每个 站点局部采用h a s h 技术，在每次迭代后通过交换h a s h 桶中计数值大于一个 给定阙值的项集来算出全局大项集。由于在交换过程中对需要交换的候选项 集进行了选择，因而减少候选项集的数量。 ( 1 ) 优点 由于采用了局部h a s h 技术，得到局部候选项集的效率有所提高。 由于削减了站点间传输的局都候选项集的数量，使得网络交换减少， 整个算法的效率有所提高。 ( 2 ) 缺点 网络的负载大。为了找到全局候选大项集，每个候选项集需要o ( n 2 ) 的代价来交换支持数，这造成节点间交换信息量过多。 候选项集的精简只在第二次迭代中来做，在其它迭代中候选项集的数 日仍可能会很大。 没有关注安全性问题，每个节点的关联规则信息是公开的。 3 。洲a 算法 ( 1 ) 算法概述 d m a 算法u 一是目前综合性能最好的一个算法，d m a 算法主要是基 于对前面算法的两个不足进行改进而提出的。它们是； c d 算法和p d m 算法在分布式环境下直接采用a p r i o r i _ g e n 函数来产 生候选项集的集合。d m a 算法采用了一个新的技术来产生相对于c d 算法和 p d m 算法更少的候选项集的集合。 在d m a 算法中，要决定一个候选项集是否是大项集，只需要o ( r 1 ) 的消息交换就能完成。 ( 2 ) 算法分析 候选项集的局部修剪 集合c h k 是比c k 小得多的候选强项集的集合。为了找到全局大项集， 1 6 哈尔滨工程大学硕士学位论文 各个站点应该进行支持数的交换。然而，由前文的性质及定理可知c h k 中的 一些候选集能够通过在支持数交换之前利用一些局部信息来削减，从而减少 局部候选项集的数量，提高了算法效率。 从上文提到的性质2 3 4 中可以看出，如果x 是k 阶全局频繁项集，必 然存在一个站点s 1 和项集x c h j ，使得x 在站点s 1 上是强项集。所以，x 在站点s 上一定是局部频繁项集。因此，一个站点s 能够在c 矾中削减掉那 些在站点s 1 上不是局部频繁项集的候选项集。尽量缩小候选集的大小，d m a 算法在每个站点s 上计算k 阶强项集，步骤如下： 候选项集的生成：基于在第k - 1 次迭代中找到的强项集的集合，生成 项集c 俄= a p r i o r ig e n ( 月z ；) 作为局部候选项集，通过这么做，每个站点实 际上负责生成它自己的候选项集，以计算它自己的频繁项集的集合。 局部扫描：在每个站点上，对于每个x c 矾，扫描局部数据库d b 来计算局部支持数x s u p 。 局部修剪：对于候选项集x c 矾，如果x 在站点s 1 上不是局部大 项，那么它就被修剪掉，剩余的候选项集保存在k 1 中。以上修剪只是将x 从站点s 上移去，而x 还可能是其它站点的候选项集。 夺支持数交换：每个站点将l k 发送到一个协作站点来计算该站点中所 有局部候选集的全局支持数，协作站点向其它主站点发送传送请求获得该站 点的局部候选集在其它主站点上的支持数。其它主站点将对应的候选集的支 持数发送到对应的协作站点产生所有的全局频繁集。 广播挖掘结果：各协作站点向所有主站点广播得到的k 阶全局频繁项 目集。 查找大项集所需交换信息机制的优化 在直接采用串行a p r i o r i 算法时，不但生成的候选项集的数量很大，而且 每个候选项集支持数交换的信息量也很大。这是因为每个候选项集是从所有 的站点广播出来的，因而每个候选项集的通信复杂度为o ( n 2 ) ，这里的n 是 站点的数量。而在d m a 算法中，候选项集x 在站点s 1 上是局部频繁项集， 每个候选集x 只需要o ( n ) 的通信复杂度就能得到项集x 的所有支持数。下 面就d m a 算法优缺点进行概括。 1 7 哈尔滨工程大学硕士学位论文 优点： 每次迭代过程中产生的候选项集数量比前两种算法更少。 每个候选集收集支持数只需要0 ( n ) 的通讯代价，优于前两种算法。 缺点： 对事务集未作处理，空间复杂度高，对重复事务要多次比较。 夺需要协作站点的辅助。 夺没有关注安全性问题，每个节点的关联规则信息是公开的。 2 3 4 现有分布式关联规则挖掘算法分析总结 通过上文对现有的c d 算法、p d m 算法和d m a 算法的分析，可以得出 它们存在的一些共性的缺点，主要有以下几点： 1 效率方面 ( 1 ) 局部候选项集的削减 在三种算法中c d 算法直接采用a p r i o r i 算法来产生局部候选项集，没有 采取特殊的削减措施；p d m 在c d 算法的基础上采用h a s h 技术来削减局部 候选项集的数量；d m a 算法在c d 算法的基础上，又提出了一些自己的定理 和推理，然后以这些理论为基础，采用了特殊的局部候选项集的剪裁策略： 对于每个候选项集x ec h i ，如果x 在站点s 4 上不是局部大项集，那么它就 被剪裁掉，剩余的候选项集保存在k 中以上的修剪只是单纯的对候选集 进行处理，虽然在后来的一些改进算法中提到对候选集的优化“”n ，但每次迭 代的事务集的数量却没有丝毫的变化，如果能对事务集进行相关的优化，使 每次迭代的事务集的数量都有所减少，那么对性能的提升将是巨大的，因为 每次迭代都要根据事务集计算支持数。 此外，在计算支持数及信息在网络中传播的过程中如果都是传送事务的 完整信息那么数据量将是非常巨大的，由于在数据挖掘的过程中并不关心事 务的具体内容，只希望得出关联规则之间的联系，所以可以考虑用某些方法 进行压缩以简化事务的表示，这样就能大大减少网络数据的传输量。 ( 2 ) 全局频繁项集的生成 通过在节点之间交换局部频繁项集的支持数得到全局支持数，然后生成 i 矗 哈尔滨工程大学硕士学位论文 全局频繁项集，这是当前普遍采用的方法m 。以上的几种算法也不例外，但 是在全局频繁集的生成方面改进不多，虽然后来也有一些针对上述缺点的算 法一，但它们提出的方案主要是针对并行环境下的数据挖掘，而对分布式环境 下的改进方案却较少，所以有必要提出一种算法在分布式环境下对挖掘效率 和通讯代价都有提升的算法。 2 安全性方面 上述三个算法都没有考虑安全性的要求，这是一个很大的缺陷，由于要 处理的是分布在很多独立数据库服务器上的数据一，而这些数据又相互独立 且自成一体，所以需要对处理的数据进行隐私保护，缺少安全保证的数据挖 掘算法在网络环境中的应用是不可靠的。 2 3 5 隐私保护在数据挖掘中的发展 隐私保护的概念由a g r a w a l 和s f i k a n t 于2 0 0 0 年首先提出。在2 0 世纪末， 网络技术的发展异常迅速，很多企业都把网络作为信息交换的重要手段，数 据挖掘也由传统的在集中式环境中的应用迁移到分布式环境和互联网环境 中。随着应用的深入，数据挖掘的安全问题就变得日益突出，针对基于分布 式数据挖掘中不提供对数据的隐私保护的现状以及数据的拥有者不希望自身 的数据对外界公开的要求提出了数据挖掘的隐私保护。 目前通用的对数据进行隐私保护的方法主要有以下两点：第一，通过在 原始数据库中加入一些随机的事务来混淆原始的数据1 4 - s t ，从而达到隐私保护 和减少相关的通讯代价的目的。因为在分布式数据挖掘中如果不加隐私保护， 某些别有用心的人可能会通过挖掘中获取的隐私数据进行非法的商业竞争， 如对医院病人数据的挖掘，一旦病人数据的泄漏，不但会侵害病人的隐私权 而且会让一些不法商人乘虚而入，通过在挖掘的过程中对原始数据加入混淆 信息就可以有效的避免这种情况的发生，而且通过对挖掘算法的改进，加入 的混淆信息不会对最终的挖掘结果产生影响。第二，则是采用某种加密算法 对中间的挖掘结果进行加密来达到数据的隐私保护。众所周知在网络环境中 最有效的保密方式就是对传输数据进行加密，一个好的加密算法能有效地防 止恶意的信息截获和篡改。现有的隐私保护户算法中有的采用安全多方计算 1 9 哈尔滨工程大学硕士学位论文 来达到隐私保护和通讯代价削减t ”，这种加密方法它具有安全性高的特点， 所以在某些场合得到广泛的应用，如电子投票，统计股票信息等。 但是，现有的隐私保护方法