（计算机应用技术专业论文）隐私保护的分布式数据挖掘系统.pdf

隐私保护的分布式数据挖掘系统 摘要 随着信息时代的到来和计算机网络技术的飞速发展，在分布式环 境下，如何进行有效的数据挖掘成为信息科学研究领域一个新的课题。 关联规则是数据挖掘研究领域的个重要问题，目前所面临的最大挑 战是计算效率和内存问题，解决的途径之一是开发高效的分布式算法。 因此本文主要从分布式的角度出发，针对关联规则的理论和方法进行 了深入研究。 本论文主要研究以下三个问题 数据量很大，不能一次载入内存。 数据的安全性和隐私性。很多时候客户只愿意提供从数据中学 习的结果而不是数据本身的细节。 数据是分布式存放的。 分布式数据挖掘的研究尚处于起步阶段，许多问题还有待于解决。 其中最重要的两个问题是分布式数据挖掘系统的结构和挖掘算法。 本论文在这两个方面进行了一些有意义的探索： 先提出了一种分布式数据挖掘系统模型，用来实现大容量的数据在 分布式存放情况下的数据挖掘。因为该系统模型只传送数据挖掘的中 间结果，所以大大减少了网络的数据传输量，并加强了数据的安全和 保密性。同时由于该系统模型采用c o r b a 接口编程技术，使得整个 系统模型不依赖于编程语言、计算平台等。 荆璺作者、写一瓣尚赢 匆全文公布 2 然后在这个原型系统模型的基础上，对分布式数据挖掘算法提出了 一些新的思想和好的实现方法。本论文中，主要考虑关联规则挖掘算 法，从两个不同的角度从理论上探讨了分布式或并行数据挖掘：( a ) 由 规则到规则：先由各个独立的站点生成各自的关联规则，再在这些关 联规则的基础上生成总的关联规则：( b ) 由数据到规则：由各个独立的 站点交换各自的中间结果来生成总的关联规则。然后针对第二种方法， 结合安全向量计算协议，提出了一种新的保持隐私的分布式关联规则 挖掘算法。 最后，本论文给出了结论，并概述了今后进一步研究的方向。 关键词：数据挖掘关联规则分布式隐私保护 p r i v a t e - p r e s e r v i n gd i s t r i b u t e d d a t am i n i n g s y s t e m a b s t r a c t w i t ht h e c o m i n g o fi n f o r m a t i o ne r aa n d r a p i dd e v e l o p m e n t o f c o m p u t e rn e t w o r kt e c h n o l o g y , h o wt om i n ee f f i c i e n t l yk n o w l e d g ef r o m d a t au n d e rd i s t r i b u t e de n v i r o n m e n tb e c o m e san e w t o p i ci ni n f o r m a t i o n s c i e n c er e s e a r c ha r e a s a s s o c i a t i o nr u l em i n i n gi sa l li m p o r t a n tt a s ko f d a t a m i n i n g a tp r e s e n tm a i nc h a l l e n g ei s i n e f f i c i e n c ya n dm e m o r yp o w e r d e v e l o p i n gd i s t r i b u t e dm i n i n ga l g o r i t h m s i sab e t t e rc h o i c e s o ，i nt h i s t h e s i s ，w ef o c u so n r e s e a r c ho nd i s t r i b u t e d m i n i n g a s s o c i a t i o n sr u l e s t h e f o l l o w i n g i so u rm a i nr e s e a r c hd i r e c t i o n s ： d a t ac a r lb et o o l a r g e t ob el o a d e di n t om e m o r ya to n c e d a t ac a nb ec o n f i d e n t i a l c u s t o m e r sa r ew i l l i n gt o p r o v i d eo n l yt h e a n a l y s i sr e s u l t f r o m d a t a ，n o t t h ed a t at h e m s e l v e s d a t ac a nb ed i s t r i b u t e d t h er e s e a r c ho fd i s t r i b u t e dd a t am i n i n gi sj u s ta ti t ss t a r t i n gs t a g e 。m a n y p r o b l e m sn e e dt o b es o l v e d a m o n gt h e m ，t h es y s t e ma r c h i t e c t u r ea n d a l g o r i t h m so f d i s t r i b u t e dd a t am i n i n ga r et h em o s ti m p o r t a n t t h i sp a p e r m a k e ss o m e i n t e r e s t i n ge x p l o r a t i o ni nt h e s e t w od i r e c t i o n s f i r s t l y , a d i s t r i b u t e dd a t a m i n i n gs y s t e m i s p r o p o s e d ，w h i c h m i n e s k n o w l e a g ef r o ml a r g ea m o u n t so f d i s t r i b u t e dd a t as e t s s i n c et h i ss y s t e m t r a n s f e r s o n l y t h ei n t e r m e d i a t er e s u l to fl o c a ld a t a m i n i n g ，i tg r e a t l y d e c r e a s e st h en e t w o r kt r a f ! f i ca n de n h a n c et h es e c u r i t ya n dp r i v a c yo f d a t a t h es y s t e mu s ec o r b a a st h ed i s t r i b u t e ds o f t w a r ee n g i n e ，s oi td o e sn o t d e p e n d o n a n yp a r t i c u l a rp r o g r a m m i n gl a n g u a g e s ，c o m p u t i n gp l a t f o r m s - t h e n ，s o m en e w i d e a sa n d g o o di m p l e m e n t a t i o nt e c h n i q u e sf o r d i s t r i b u t e d d a t am i n i n g a l g o r i t h m s a r ep r o p o s e db a s e do nt h i sp r o t o t y p es y s t e m i nt h i s p a p e r , w em a i n l y d i s c u s sa s s o c i a t i o n r u l e m i n i n g a n d i m p r o v e t h e c o n v e n t i o n a la l g o r i t h mi nt w od i f f e r e n tm e t h o d si no r d e rt oa d a p tt ot h e d i s t r i b u t e d p a r a l l e l d a t am i n i n g o n ei sf r o mr u l e st or u l e s ：a s s o c i a t i o n 4 r u l e sa r ef i r s t l ym i n e da tt h el o c a ls i t e s ，a n dt h e ng l o b a la s s o c i a t i o nr u l e s a r eg e n e r a t e df r o mt h e s el o c a lr u l e s 。t h e0 t h e ri sf r o md a t at or u l e s ：t h e l o c a ls i t e s e x c h a n g e t h e i ri n t e r m e d i a t ed a t a r e s u l t s ，a n d t h e n g l o b a l a s s o c i a t i o nr u l e sa r e g e n e r a t e d f r o mt h e s er e s u l t s i nt h i s p a p e r , w e p r o p o s e d an e w a l g o r i t h m su s i n g t h el a t t e rm e t h o d s w i t ht h en e w a l g o r i t h m s ，w e c a nd i s c o v e rf e q u e n ti t e ms e tw i t hm i n i m u m s u p p o r tl e v e l ， w i t h o u t r e v e a l i n g t h ei n f o r m a t i o no ft h ec u s t o m e r s a tl a s t w ed r a ws o m ec o n c l u s i o n sa n do u t l i n ed i r e c t i o n sf o rf u t u r ew o r k k e yw o r d s ：d a t a m 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 t e p r e s e r v i n g 5 第一章绪论 信息时代的到来和计算机网络技术的飞速发展，在分布式环境下，如何进行 有效的数据挖掘成为信息科学研究领域的一个新课题。本章主要介绍本文研究工 作的目的与意义，知识发现的基本概念，主要面临的问题以及知识发现的方法， 关联规则理论的基本思想、研究与发展概况，最后概述本文的组织和主要研究工 作。 1 1 概述 分布式数据挖掘的研究尚处于起步阶段，许多问题还有待于解决。其中最重 要的两个问题是分布式数据挖掘系统的结构和挖掘算法。 本论文在这两个方面进行了一些有意义的探索： 先提出了一种分布式数据挖掘系统模型，用来实现大容量的数据在分布式存 放情况下的数据挖掘。因为该系统模型只传送数据挖掘的中间结果，所以大大减 少了网络的数据传输量，并加强了数据的安全和保密性。 然后在这个原型系统模型的基础上，对分布式数据挖掘算法提出了一些新的 思想和好的实现方法。本论文中，主要考虑关联规则挖掘算法，从两个不同的角 度从理论上探讨了分布式或并行数据挖掘：( a ) 由规则到规则：先由各个独立的站 点生成各自的关联规则，再在这些关联规则的基础上生成总的关联规则：( b ) 由数 据到规则：由各个独立的站点交换各自的中间结果来生成总的关联规则。然后针 对第二种方法，结合安全向量计算协议，提出了一种新的保持隐私的分布式关联 规则挖掘算法。 最后，本论文给出了结论，并概述了今后进一步研究的方向。 1 2 论文的研究内容 分布式数据挖掘的研究尚处于起步阶段，还有许多公开问题需要解决。如数 据一致性、挖掘算法、隐私保护等。只有上述问题获得全面的突破，分布式数据 挖掘才能实用。因此，今后还需要投入许多研究力量。本文的研究工作就是在这 样的前提下，跟踪当前最新的研究动态和研究成果以及存在的问题，利用了数据 库和数据挖掘中成熟的技术，深入分析了关联规则挖掘的理论并结合自己的研究 成果提出了一种适合于分布式数据挖掘的体系结构。 本文研究的目标是开发一个能适用于物理或逻辑尚分布式存放的数据库系统 模型的数据采掘工具，作为数据仓库的重要工具，为决策提供支持。 具体工作有如下几个方面： 1 ) 设计了一种应用于分布式环境下数掘挖掘体系结构，主要针对垂直分括的 分布式事务数据库。 2 ) 对分布式环境下的关联规则挖掘做出了理论探讨，提出了一种保持各方 隐私数掘的方法：由各自的独立节点交换生成的中间结果来生成总的关 联规则。 3 ) 对本文所作的工作总结并提出一些结论，并就分布式数据挖掘系统的进一 步深入研究提出作者的思考和建议。 1 3 论文的组织形式 本论文系统的论述和分析了数据挖掘技术以及算法的思想，重点讨论了关联 规则数据挖掘，在此基础上通过扩展已有的理论并与成熟的算法相融合，提出了 一个可扩展的分布式数据挖掘体系结构和基于此的分布式数据挖掘算法。本论文 各章内容的安排如下： 第一章绪论 提出了本论文研究的核，t l , 内容，同时对文章所作的工作和文章的组织进行了 叙述。 第二章数据挖掘和分布式数据挖掘 介绍了数据挖掘的背景和研究现状，然后介绍了分布式数据挖掘主要需要研 究的问题以及目前的研究成果 第三章隐私保护的分布式数据挖掘系统 首先介绍了代理和d c o m 技术，然后在这两者的基础上提出了隐私保护的分 布式数据挖掘系统，该系统模型基于物理上或逻辑上分布式存储的大规模事务数 据库。 第四章关联规则概述 重点介绍了关联规则挖掘的基本概念、算法的基本思想以及产生和发展的概 况。然后给出了关联规则挖掘算法的分类以及相关算法，重点介绍了a p r i o r i 算法 的思想和实现的p s e u d o c o d e ，最后讨论了关联规则的分类和挖掘中的几个问题。 第五章分布式关联规则挖掘 对分布式关联规则挖掘做了理论上的探讨，并着重探讨了站点问交换数据过 程中，对本站点事务数据库数据的保护问题，采用了一种新的算法，达到了在分 布式数据挖掘过程中，私有数据库隐私保护的目的。 第六章总结和展望 对本文所作工作进行总结，提出了一些结论，并就分布式数据挖掘系统的进 一步深入研究提出作者的思考和建议。 9 2 1 引言 第二章数据挖掘和分布式数据挖掘 当今的世界正处于一个“数据爆炸”的时代。由于数据的长期积累，有些数据 库变得非常的庞大，目前数百万乃至上千万条记录的数据库已不罕见。随着i n t e m e t 的迅速发展，使大量的数据涌到人们面前，人们面对的问题不是缺少数据，而是 被数据淹没。在巨大的商业利益驱动下，一个新的研究领域一知识发现( k n o w l e d g e d i s c o v e r ) 应运而生，由于蕴藏知识的信息大多数存储于数据库中，数据库中的知 识发现( k n o w l e d g e d i s c o v e ri nd a t a b a s e ) ，又称数据挖掘( d a t a m i n i n g ) ，目前己成为 人工智能、统计数、数据库等领域研究的热点之一。 k d d 一词首次出现在1 9 8 9 年8 月举行的由美国人工智能协会组织的第1 1 届 国际人工智能联合学术会议上，标志着k d d 的正式诞生，此后有越来越多的研究 者投身其中。迄今为止，g h ( a a a i ) 主办的k d d 研讨会已经召开乐多次。1 9 9 7 年 亚太地区在新加坡组织了第一次规模较大的p a k d d 学术研讨会，以后每年此会议 都举行一次。此外，数据库、人工智能、信息处理、知识工程等领域的国际学术 刊物也纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g 会 刊率先在1 9 9 3 年出版了k d d 技术专刊。k d d 将智能技术与数据库相组合，不但 为决策者提供知识和策略，而且为投资者带来经济效益。最近纪念，为了处理数 据仓库( w a r e h o u s e ) 和i n t e r n e t 上浩如烟海的数据，i b m 、微软、g m 等大公司以及 n a s a 等机构竞相投入资金以推动k d d 的研究及开发实用化的数据挖掘系统。知 识发现已经成为当今计算机科学与技术研究的热点领域之一。 我国学者及时的开展了知识发现方面的研究工作，一些高等院校与科研机构也 开发了相应的知识发现原型系统。目前，在国内许多重要的学术会议如中国人工 智能联合学术会议、数据库学术会议、机器学习学术会议等也都将知识发现列为 重要的研究专题。 本文研究基于上述目的和背景，针对知识发现种的关联规则挖掘的理论和发 现进行了深入的研究，提出了高效安全的分布式挖掘算法。 2 1 i 数据挖掘概述 ( d a t am i n i n g ) ，也称作数据采掘、数据开采等。许多人把“数据挖掘” 和t 数据库中的知识发现“看作是等价的概念，在这种意义下，他们的定义是一 致的，一种比较公认的定义是f r a w l e y u ，p i a t e s t s k y s h a p i r o g 等人提出的：数据挖 掘，即数据中的知识发现，是一个在数据库中提取模式的过程，这些模式是有效 0 地、新颖的、有潜在使用价值和易于理解的。 2 1 2 数据挖掘过程 数据挖掘作为知识发现的过程，一般由三个主要的阶段组成：数据准备、数 据挖掘、以及结果的解释评估。知识的发现可以描述为这三个阶段的反复过程， 如图1 1 。 ( 1 ) 数据准备 数据准备又可以分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理( d a t a p r e p r o c e s s i n g ) 着f l 数据变换( d a t at r a n s f o r m a t i o n ) 。数据选取的目的是确定发现任务的 操作对象：即目标数据，他是根据用户的需要从原始数据库中抽取的一组数据。 数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完成数 据类型转换f 如把连续值数据转换为离散值数据，以便于符号归纳，或是把离散值 数据转换为连续值数据，以便于神经网络归纳) 等。当数据挖掘的对象是数据仓库 是，一般说来，数据预处理已经在生成数据仓库是完成了。数据变换的组要目的 是将数据转换称适合数据挖掘需要的形式，例如将文档信息转换成数值向量形式， 另外还包括数据维数的削减或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正 有用的特征以减少数据挖掘时要考虑的特征或变量个数。 图1 1 数据挖捌过程 ( 2 ) 数据准备 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、分类、聚 类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样 的挖掘算法。同样的任务可以选用不同的算法来实现。选择实现算法又两个考虑 因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘：二是 用户或实际运行系统的要求，有的用户可能希望获取描述型的、容易理解的知识f 采 用规则表示的挖掘算法显然要好于神经网络之类的方法) ，而有的用户或系统的目 的时获取预测准确度尽可能搞的预测型知识。 完成了上述准备工作后，就可以实施数据挖掘操作了。具体的数据挖掘方法 将在后面的章节中作较为详细的论述。需要指出的是，尽管数据挖掘算法是k d d 的核心，也是目前研究人员主要努力的方向，但要获得好的挖掘效果，必须对各 种挖掘算法的要求或前提假设有充分的理解。 o ) 结果解释评估 数据挖掘阶段发现的模式，经过用户或机器的评估，可能存在冗余或无关的 模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个发现 过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的 数据挖掘参数值，甚至换一种挖掘算法( 如当发现任务是分类时有多种分类方法， 不同的方法对不同的数据有不同的效果) 。另外，k d d 由于最终是面向用户的，因 此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示。 2 i 3 数据挖掘技术的分类 数据挖掘的研究融合了来自不同学科领域的技术和成果，使得目前的数据挖 掘技术和系统表现出多种多样的形式。对数据挖掘技术进行分类，可以帮助潜在 的用户区分不同的系统从而选择适合自己需求的种类。从不同的视角看，数据挖 掘技术有几种分类标准；根据发现知识的种类分类，根据挖掘的数据库的种类分 类和根据采用的技术分类。 根据发现知识的种类分类 根据发现的知识种类可分为：关联规则发现、分类或预测模型知识发现、数 据总结、数据聚类、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现 等。本文的研究主要涉及关联规则的发现，所以后续章节我们将对这一问题作详 细的介绍。 根据挖掘的数据库的种类分类 数据挖掘基于的数据库类型有：关系型、交易型、面向对象数据库、空间数 据库、时态数据库、文本数据源、多媒体数据库、异质数据库、遗留数据库，还 有基于数据仓库的数据挖掘系统，以及基于国际互联网或w e b 的数据挖掘系统等。 根据采用的技术分类 根据挖掘方法所采用的技术，可粗分为：统计分析、机器学习方法、模式识 别、面向数据库或数据仓库的技术、可视化技术和神经网络等。统计方法中，可 细分为：回归分析、判别分析、聚类分析( 系统聚类、动态聚类等) 、探索性分析 等。机器学习中，可细分为：归纳学习方法( 决策数、规则归纳等) 、基于范例的学 习、遗传算法等。数据库方法主要是多维数据分析和o l a p 方法，另外还有面向 属性的归纳方法。当然，个完善的数据挖掘系统通常采用多种技术，结合它们 的优点设计出有效的、集成的技术。 2 1 4 数据挖掘研究的主要问题 k d d 的研究仍处于初级阶段，还有很多的研究难题和面临的挑战，如数据的 巨量性、动态性、噪声、缺值和稀疏性，发现模式的可理解性、兴趣或价值度量， 应用系统的集成，用户的交互操作，知识的更新关联，负责数据库的处理等。 ( 1 ) 有效处理巨量和高维的数据 包含上百万条记录和数前兆字节甚至数兆兆字节的数据库已经司空见惯，另 外数据库关系所涉及的属性或变量数也达到成百上千的数量。这种数据的巨量和 高维性使得数据挖掘时模式的搜索空间异常巨大，同时还可能导致搜索出无意义 模式的机会增加。传统的技术已经难以适用，如常规的机器学习方法一般只能处 理不超过几于条记录或例子的数据集，为了解决这些问题，需要有高效的特别是 线性计算复杂度的算法、抽样方法、分布式挖掘技术、大规模并行处理技术、维 数削减方法等技术。 ( 2 ) 数据的动态变换和知识的更新维护 数据的动态变化常常会使得以前发现的模式不再有效，特别是数据库可能增 加、删除或改变变量。发生这些情况时则要求设计k d d 系统必须考虑知识的更新 维护，如怎样解决知识冲突，另外数据的动态性也提出了新的k d d 问题：趋势或 变化模式发现任务以及主动数据库挖掘研究。 ( 3 ) 改进用户的交互性和充分利用背景知识 目前很多k d d 工作的主要方向还是围绕在算法的效率上研究，大多数k d d 系统还没有充分考虑用户的参与而使得交互性较差。目前在可视化以及数据仓库 中的多维数据分析工具在这方面做的较好，但在其他k d d 方法中还有大量的工作 要做。k d d 系统与人工智能有密切的关系，背景知识或领域知识在智能化、自动 化的k d d 系统中势必扮演重要的角色，充分使用背景知识能使得在巨大的模式控 件中的搜索更为有效、有目的。 ( 4 ) 数据噪声与缺值 在商业数据库中噪声和缺值是- - e e 常见现象。如美国人口普查数据的错误率 就高达2 0 ，错误或噪声可能来自于数据录入的误操作或其他实际中不可避免的 因素。数据遗失有两种情况：一是某些字段上缺值，另一是数据库在设计阶段就 可能没有考虑某些重要属性或字段，而这些重要属性对于k d d 进行知识发现可能 很重要。 ( 5 ) 提高模式的可理解度 很多应用中要求发现的模式具有好的可理解性，从模式的表示角度看，目前 的方法包括可视化方法、图形表示、规则表示、自然语言生成等。 ( 6 ) 应用系统的集成 一个单独的k d d 发现系统如果不和具体的应用系统集成或结合，将毫无意 义，k d d 应该和数据库管理系统或m i s 、电子表单、实时传感数据采集系统，特 别是决策支持系统集成在一起。数据仓库上的o l a p 技术是一种典型的集成。 目前，人们正在把数据仓库的研究和数据挖掘的研究结台起来。数据仓库的 发展为数据挖掘开辟了更广阔的空间，数据仓库完成了对数据的收集、集成、存 储、管理等预处理工作，使得数据挖掘更专注于知识和规则的发现，充分发挥数 据挖掘技术的潜力，为决策提供更有力的支持。由于数据仓库所具有的新的特点， 给数据挖掘技术提出了更高的要求，数据仓库环境下的数据挖掘的理论和技术将 成为信息科学学术界新的研究热点。 ( 7 ) 处理负责的数据和数据库 目前k d d 的发掘对象，从数据库看，主要是面向关系型数据库：其他数据库 类型，如面向对象数据库、空间数据库特别是随着i n t e m e t 的迅速发展，w e b 上的 信息或知识发现也已得到重视。从数据看，k d d 处理的最多的还是数值数据。数 据库发展的一个趋势是各种类型数据的使用，特别是多媒体数据越来越多：这要 求相应的k d d 系统不但有处理数值数据的功能，还应能处理符号、文本、声音、 图形、图像，视频等类型数据。 f 8 1 私有数据的保护与数据安全性 什么情况下数据挖掘将会导致对私有数据造成侵犯和采用什么手段来防止敏 感信息的泄漏的研究也非常重要。本文在后面的章节中将会详细的阐述这一方面 的内容。 2 1 5 目前典型的数据挖掘系统 下面我们介绍三个典型的数据挖掘原型系统。 ( 1 ) d b m i n e r d b m i n e r 是加拿大s i m o nf r a s e r ( s f u ) 智能数据库研究所开发的商品化数据仓 库与知识发现集成系统。d b m i n e r 包含的功能比较全，能迅速高效地建立数据仓 库，并进一步从数掘中挖掘隐含于数据中的知识，辅助管理者进行决策。系统把 数据仓库、多维数据库和数据挖掘技术集成在一起，能发现七种任务类型：总结、 关联、分类、预测、比较、聚类、时序等。 d b m i n e r 实现了切片、切块、钻取等o l a p 操作，定义和实现了高效的数据 挖掘语言。同时还能提供直观的图形用户界面，可视化的数据浏览工具，和联机 事务分析( o l a p ) ；f 1 联机分析挖掘( o l a m ) 能j 3 。 但是它也存在缺陷，它的快速立方技术本质上是基于内存中的多维数据，因 而要求较大的内存。 ( 2 ) q u e s t i b ma l m a d e n 研究中心开发的q u e s t 系统是关联规则挖掘的开创性项目。除 了设计和实现了经典的a p r i o r i 关联规则算法外，q u e s t 系统还可以发现分类规则， 序贯模式和时间序列规则等。 ( 3 ) j a m j a m 是由c o l u m b i a 大学开发的一个分布式的、基于智能体的数据挖掘原型系 统，系统由若干个具有分类功能的移动智能体和具有集成功能的元学习智能体组 成。使用了一种我们称作可扩展的元学习方法。移动智能体能从局部站点的数据 集上挖掘潜在的、有意义的分类模式。元学习智能体能从多个站点上已获得的分 类模式中提炼出全局潜在的有用模式。它使用一种特殊的分布技术，允许派生模 型或分类智能体迁移到其他远程站点。它的目的是应用于金融信息系统中的防伪 和入侵检测。 2 1 6 关联规则的研究概况 关联规则的挖掘是数据挖掘领域研究的一个重要问题，对关联规则挖掘的研 究最先是由a g r a w a l 等人提出，产生的动力是希望从交易数据中发现顾客的购买 模式，一个典型的例子是“9 0 的顾客在购买面包时也会购买牛奶”。其直观的意 义是顾客在购买某些商品的时候有多大倾向会购买另外一些商品。关联规则的应 用主要包括顾客的购物分析、网页设计、商品广告邮寄、追加销售、仓储规划、 网络故障分析等。挖掘关联规则的挑战性来自两个方面，一是交易数据的总量十 分巨大，二是从上千种项目中可以组合产生的关联规则太多，是个指数爆炸问题。 r a g r a w a l 等人提出关联规则发现算法之后，该问题得到了国际众多研究者的 广泛研究，提出了许多形形色色的算法。而在另外一些研究中，关联规则的模型 被扩展或改进以适应某些特殊的需要，因此产生了许多变种问题。由此可见这个 问题在数据挖掘领域的重要地位。下面我们分串行算法和并行及分布式算法来分 布综述目前关联规则挖掘的研究情况及存在的问题，同时概述本文的研究工作。 ( 1 ) 串行算法的研究 自从关联规则挖掘问题由a g r a w a l 等人第一次提出后，引起了有关学术界的 广泛兴趣。关联规则的关键问题在于如何产生频繁项目集和他们的频度。算法 a p r i o r i 的提出是解决该问题的一个里程碑，它的核心技术奠定了所谓“层次算法” ( 1 e v e l - w i s ea l g o r i t h m s ) 的基础。随后提出的许多改进算法，例如d h p 算法，p a r t i t i o n 算法等，都遵循了a p r i o r i 算法层次产生候选集的方法，b r i n 等人设计的d i c 算法 提出了动态产生候选集的思想，突破了层次算法的框架，可以在更早的时刻产生 新的候选修建并且立刻开始计算这些候选集的频度。 ( 2 ) 关联规则扩展问题的研究 关联规则最初是在商品交易数据库环境下提出的，其动机是想发现顾客购买 物品时各种物品之间的关联关系。近年来人们提出了许多令人感兴趣的扩展和应 用。对经典的关联规则挖掘算法进行扩展和超越的工作主要包括： 定量( 数值) 关联规则挖掘 目前提出的挖掘数值属性关联规则的算法，大多数是将数值属性关联规则挖 掘问题转化为布尔型关联规则挖掘问题，即将数值属性的取值划分为多个区间， 每个区间看作一个属性：将类别属性的每一个类别当作一个属性，典型的离散化 方法有等值、聚类、可视化等方法。 广义多层关联规则发现 项目通常是分类的，利用项目间的层次关系能发现更有意义的规则。随着 o l a p 与数据仓库技术的日益成熟，项目的层次关系在大多数数据集中实际已参在 或能较容易建立。h a n 等人研究了基于属性归纳的数据挖掘算法，并提出了多层次 关联规则的串行挖掘算法。s r i k a n t 等人以及h a r t 等人讨论了泛化关联规则的挖掘 问题。本文将在后面的章节详细讨论分布式环境下的多层关联规则的发现问题。 基于约束的关联规则挖掘 基于约束的关联规则挖掘的主要目的是发现更有趣的、更实用的和更专门的 关联规则。这方面的研究主要有口约束的种类有：项包含约束、合取项数、属性的 值域、元组数及聚类运算约束等。出现的算法有多层元规则指导的关联规则挖掘， 单变量元规则指导的关联规则挖掘，直接的p 一谓词技术等。s r i k a n t 等人以及n g 等人讨论了项包含约束的关联规则挖掘问题( a s s o c i a t i o n r u l e sw i t hc o n s t r a i n t s ) 。 其他方向 除了以上常见的研究方向外。还有其他一些研究方向。如基于语占值的关联 规则发现，挖掘长模式和密集数据集，发现周期和日志关联规则，n 一维交易问的 关联规则挖掘，挖掘多维关联规则，关联规则的在线生成，文本数据中的关联规 则挖掘，积极和消极关联规则挖掘等。 f 3 ) 规则的有效性度量方法 仅利用最小可信度来判定规则的有效性具有一定的局限性，因此许多学者提 出了一些新的评价标准。这些工作主要包括：b r i n 等人提出的兴趣度( i n t e r e s t ) 和坚 信度( c o n v i c t i o n ) 两个概念，以及把事件依赖性的统计定义扩展到兴趣度的定义上 来的策略：a g g a r w a l 等人提出的聚集强度( c o l l e c t i v es t r e n g t h ) 概念，设想使用“大 于期望值”来发现有意义的关联规则。项集的聚集强度是【0 ，。】之间的一个数值， 其中0 表示完备的否定相关性，而值。表示完备的正相关性。 2 , 1 7 分布式数据挖掘的研究现状和难点 数据挖掘任务面向的是大规模的数据库或数据仓库，要处理的数据量通常非 常巨大，往往达到g b 甚至t b 数量级：业务的跨地域分布通常导致数据库跨地域 分布，多个数据库通常通过网络连接在一起，数据挖掘的任务有时要同时针对这 多个数据库：另外，有些数据挖掘任务本身的计算复杂度较高，需要计算机具有 强大的计算能力，所有这些，都对数据挖掘算法的并行化和分布化提出了要求。 有关关联规则挖掘的并行和分布式算法的研究，正是反映了这样种实际应用的 趋势。 我们认为分布式数据挖掘主要涉及的研究问题包括： 分布式数据挖掘的理论和基础问题，包含挖掘任务的分割，数据分布， 数据的一致性表示或维护等； 分布式挖掘算法的研究，例如将典型的各种串行挖掘算法分布化，其中 又涉及节点间的通讯、协作等众多问题； 分布式数据挖掘系统的体系结构问题的研究。系统的组织方式，工作方 式，各种体系结构的性能等； 多智能技术与分布式数据挖掘系统的集成，主要是将多智能已取得的一 些成果引入分布式数据挖掘系统中。研究在分布式数掘挖掘系统中各学 习智能体间的交互、协作、协商、认知、组织行为等： 不同挖掘对象( 数据集) 的分布挖掘问题，例如异构数据集，空间数据集 挖掘问题； 安全问题，关于各数据库的私隐数据保护问题，该问题将在后面讨论； 应用，在商业、科学、工程和医学等领域中的应用； 目前，大多数文献所提出的挖掘关联规则的分布式算法都是基于分布式多处 理器的并行模式。在这些系统中，数据库分布在每个处理器连接的本地磁盘上， 处理器之间通过互联网络通讯来协调他们之间的任务。基于这种模式所提出的关 联规则的并行算法主要着眼于下列三个问题：1 ) 减少通讯量：2 ) 修剪候选集：3 ) 把 候选集划分给分布的多个内存空间。这些算法需要通过反复扫描数据库来计算频 繁项目集，如果频繁项目集的长度是k ，则需要扫描数锯库至少k 次，这是这类算 法必须的开销。这类方法还需要同步机制来协调不同处理器之间的行动，即在扫 描数据库的每一编米尾，不同的处理器之间需要交换所考察的候选集在不同数据 库分区中发生的频度，这些算法可以看作是a p r i o r i 算法的并行版。 我们知道，寻找频繁项集的主要活动是计算候选集的频度，在内存分布的并 行系统中有两种途径来达到这个目的，一种是频度分布( c o u n td i s t r i b u t i o n ) ，另一 种是数据分别( d a t ad i s t r i b u t i o n ) 。频度分布的算法包括c d ( c o u n td i s t r i b u t i o n ) 和 p d m ( p a r a l l e td a t am i n i n 曲；采用数搌分布式的算法有d d ( d a t ad i s t r i b u t i o n l ， i d d 0 n t e l l i g e n td a t ad i s t r i b u t i o n ) 和h p a 。 在频度分布模式中，每个处理器都负责计算所有候选集在自己的数据库分区 中的局部频度，然后互相交换局部频度的信息，因而所有的处理器都能够收集到 候选集的全局频度，处理器就可以独立的计算法频繁集。因为在每次迭代中，处 理器需要记录所有候选集的局部频度，频度分布方法可能的问题是存储所有的候 选集需要的内存开销太大。算法c d 是频度分布模式的代表算法，它的实现平台是 i b ms p 2 ；p d m 算法是更加文献 1 0 】提出的哈希技术对c d 的改进算法：f p m ( f a s t p a r a r r e lm i n i n g ) 应用候选集修剪技术和全局修剪来减少每次迭代中候选集的数量。 在数据分布模式中，将候选集分布在不同的处理器上，从而缓和了候选集和 内存的矛盾，这时每个处理器只负责计算一部分候选集的全局频度。但是，为了 达到这个目的，在不同分区的交易必须传送给其他所有的处理器，与交互频度信 息比较，传送交易数据需要的通讯带宽要高的多，因此这种方法需要极快的网络 速度支持，而且数据库不可以十分巨大。 算法d d 是最早提出的数据分布式算法，也是在i b ms p 2 机器上实现的。在 d d 中候选集是用循环的方式在所有的处理器上平均分配，每个处理器将自己的数 据库分区传送给其它所有的处理器。算法i d d 是d d 的改进算法，它是在带有快 速网络连接的c r a yt 3 d 机器上实现，它根据候选集的首项目来分割候选集，因 此每个处理器只需处理交易中那些以相应项目为首的子集，减少了d e ) 算法中的 冗余计算，而且i d d 还采用了环结构来降低通讯的负担。h p a 应用哈希技术将候 选集分布到不同的处理器上，该算法不需要传送整个数据库分区，而用同样的哈 希方法将交易也分配到其他相应的处理器上，h p a 是在f u j i t s u a p l 0 0 0 d d v 并行系 统上实现的。 f h u 等设计了基于共享内存多处理器模型挖掘关联规则的自适应异步并行算 法a p m ( a d a p t i v e p a r a l l e lm i n i n g ) ，采用了自适应区间配置技术和虚拟分区修剪技 术，能有效的削弱共享内存系统的瓶颈效应对挖掘性能的影响 3 1 概述 第三章隐私保护的分布式数据挖掘系统 简单的说，数据挖掘就是从大量的数据中提取或挖掘知识。一般说来这些数 据都是存放在数据库中的，不过由于历史或其他的客观原因，在数据库设计的开 始阶段来不及重视的地域分散的特定需求，由于过分地集中又产生了不协调。随 着计算机技术的发展、新领域的涌现和实用化的发展，人们期望着符合现实需要 的、能处理分散地域的、具备数据挖掘特点的新的数据挖掘系统的出现。本章提 出了一个隐私保护的分布式数据挖掘系统。通过”数据挖掘系统+ 计算机网络+ 代 理”来实现分布式数据挖掘系统，即达到对数据挖掘系统的集中管理和数据的共 享，又能使地域的分散性被系统隐蔽起来。这种要求在现实中到处存在。如银行 和它的支行、办理处，连锁销售店的总店和子店等。 3 2 隐私保护的分布式数据挖掘系统 3 2 1 代理( a g e n t ) 技术 3 2 1 1 简介 a g e n t 技术说分布人工智能领域中发展起来的一种新型计算模型，具有高度智 能化、易于构造分布式系统、软件的复用性强等优点。 从应用的角度来看，智能代理就是自动执行用户委托的任务的计算实体，它 有着极其广泛的应用，象邮件过滤代理、信息获取代理、桌面自动代理等等，将 使w e b 站点、应用程序更加智能化和实用化。但对于很大一部分个人和企业来说， 真正的价值是将直接影响事务处理的效率。这就要求我们必须了解代理是如何工 作的，要了解代理中存在的限制和实现上的困难，也就是说，要从技术的角度来 理解和掌握智能代理。 从技术的角度来看，智能代理应当说由各种技术支撑着的，许多实用的应用 特性的集合，开发者正是使用这些应用特性来扩展应用的功能和价值，从而达到 应用能自动执行用户委托的任务的目的。 同图形用户接1 ：3 一样，智能代理中有几类关键的技术，虽然并不是每个智能 代理都必须使用所有的这些技术，但使用这些技术越多的代理或应用，将具有更 多的智能代理的特性一智能性( i n t e i i i g e n c e ) 和代理能力( a g e n c y ) 。智能性是指应用 系统使用推理、学习和其他技术来分析解释它已接触过的或刚提交给它的各种信 息和知识的能力。代理能力指a g e n t 能感知外界发生的消息，并根据自己所具有 的知识自动作出反应。 通常可以将这些关键技术归纳为四大类：机器( m a c h i n e r y ) 技术、内容( c o n t e n t ) 技术、访问( a c c e s s ) 技术和安全( s e c u r i t y ) 技术。 ( 1 )机器技术是构成智能的核心技术，而机器技术中的核心是推理机和学 习机，它们提供了智能代理所需的推理能力和学习能力 ( 2 )内容技术与机器技术是息息相关的，它是机器技术中推理机、学习机 等引擎运转的基础，因此，它同机器技术一样是影响着代理的智能性， 并且成为代理智能性高低的基础。内容是指机器用于推理和学习的数 据，但它不定就是知识，它主要包括属于结构化知识的规则、语法， 大量非机构化的通用知识和结构化的数据。 ( 3 )访问是指代理同它周围环境进行交互的程度。一个代理必须能够感知 其环境中发生的事件并且能够采取响应的动作。代理与它周围的环境 交互，可以分为代理应用之间的交互与代理和用户的交互。访问技术 与代理的代理能力有关，不同程度、不同类别的访问技术将决定代理 能力的不同，也将决定代理能力的高低。 f 4 )安全问题已经远远超出了代理的范围，但一个成功的代理将取决于