（计算机应用技术专业论文）基于移动agent的数据挖掘技术研究.pdf

1 重庆交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：董悉撤 日期：2 9 1 1 年年月i g 日 重庆交通大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权重庆交通大学可以将本学位论文的全部内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科 学技术信息研究所将本人学位论文收录到中国学位论文全文数据库，并进行 信息服务( 包括但不限于汇编、复制、发行、信息网络传播等) ，同时本人保留 在其他媒体发表论文的权利。 学位论文作者躲童惠敞 指剥币签名兹磷 日期：1 1 年斗月 f 9 日 日期：锄i f 年尹月日 本人同意将本学位论文提交至中国学术期刊( 光盘版) 电子杂志社c n k i 系 列数据库中全文发布，并按中国优秀博硕士学位论文全文数据库出版章程规 定享受相关权益。 学位论文作者签名：鼹孜 日期：2 0 1 1 年年月i g 日 燧名谨辟 同期：伽fi 年斗月扩日 摘要 计算机技术、网络技术、i n t e r n e t 技术的进步，带来了数据挖掘技术的迅速发 展。该技术主要是以从大量的、不完全的、有噪声的、模糊的、随机的数据集中 识别有效的、新颖的、潜在有用的、以及最终可理解的模式为目标，实现寻找模 式的决策支持。实际工程中，数据集大部分都按地理位置分布于多个场所，若把 这些数据重新收集到一个集中的地方( 如数据仓库) ，这要求有高的数据通讯网络， 并且会导致响应时间变长和数据私有性和安全性被破坏。分布式数据挖掘技术很 好地解决了以上的问题，在分布式数据挖掘系统下，用户、数据、硬件资源以及 挖掘需要的软件资源在物理上都可以使分布的。 为了提高分布式数据挖掘系统的通信效率、平台兼容性并解决数据传输等方 面存在的安全性问题，本论文围绕研究将移动a g e n t 技术应用到分布式数据挖掘 中，构建远程交互、平台无关、节约网络带宽且具有较高可维护性和灵活性的分 布式数据挖掘系统，以重庆交通大学研究生教育创新基金项目“网络工程系统亚 健康状态诊断及智能维护决策机制研究 为背景，对移动a g e n t 技术在分布式 数据挖掘方面的应用进行了深入的研究与讨论。论文主要研究成果包括： ( 1 ) 对移动a g e n t 做了深入的理解和掌握，深入分析了移动a g e n t 模型的特 征、系统结构等。剖析了其它一些分布式计算模型的优缺点，在此基础上提出了 一个基于移动a g e n t 的分布式数据挖掘模型。在分析影响分布式数据挖掘性能的 因素的基础上，建立了几种典型的分布式数据挖掘模型的通信代价模型。 ( 2 ) 利用移动a g e n t 平台a g l e t ，设计并实现一个基于a g l e t 的分布式数据挖 掘原型系统，该系统利用移动a g e n t 的移动性、反应性、自主性等特征，主控站 点派遣a g l e t 迁徙到远程站点去执行挖掘任务，并将局部挖掘结果返回主控站点。 只须移动的仅仅是a g l e t 本身少量的代码、局部挖掘结果和a g l e t 本身的状态，减 少了通信量。 ( 3 ) 在研究了关联规则挖掘理论和各种分布式关联规则挖掘算法的基础上， 对分布式关联规则挖掘算法f d m 算法进行了改进，得出了d d ma rb a 算法。 该算法中，由于移动a g e n t 的介入，彻底改变了分布式环境中各站点间的通信方 式，理论分析表明，a g l e t 只需两次往返于主控站点和目的主机之间( 两次往返的 a g l e t 是具有不同挖掘任务的a g l e t ) ，即可得到远程站点的局部挖掘结果，提高了 挖掘效率。对u c i 数据集，运用该算法进行实验，证明了d d ma rb a 算法的有 效性和较之a p r i o r 算法的挖掘效率的优势，特别是对于海量数据集来说，挖掘效 率优势愈加明显。 关键词：数据挖掘；移动a g e n t ；a g l e t 平台；数据库；关联规则 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , n e t w o r kt e c h n o l o g ya n di n t e m e t t e c h n o l o g y , t h et e c h n o l o g yo fd a t am i n i n gh a sd e v e l o p e dr a p i d l y t h i st e c h n o l o g yi s e n g a g e di ni d e n t i f y i n gt h em o d e w h i c hi sv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u la n du l t i m a t e l y c o m p r e h e n s i b l ef r o ml a r g e ，i n c o m p l e t e ，n o i s y , f u z z ya n ds t o c h a s t i c d a t as e t s ，a n d a c h i e v e sf i n d i n gd e c i s i o n - m a k i n gs u p p o r to fm o d e i np r a c t i c e ，m o s td a t as e t sd i s t r i b u t e g e o g r a p h i c a l l yi ns e v e r a ll o c a t i o n s ，t h e r e f o r e ，i ft h ed a t ai sp r o p o s e dt ob ec o l l e c t e di n o n ep l a c e ( s u c ha sd a t aw a r e h o u s e ) ，h i g h s p e e dc o m m u n i c a t i o nn e t w o r kw i l lb e r e q u i r e d ，a sar e s u l t ，t i m eo fr e s p o n s ew i l lb el o n g e ra n ds e c u r i t yw i l lb ed e s t r o y e d h o w e v e r , t e c h n o l o g yo fd i s t r i b u t e dd a t am i n i n gr e s o l v e st h ea b o v ep r o b l e m sw e l la n d i nd i s t r i b u t e dd a t am i n i n gs y s t e m ，c l i e n t ，d a t a ，h a r d w a r ea n ds o f t w a r en e e d e db yd a t a m i n i n gc a nb ed i s t r i b u t e dg e o g r a p h i c a l l y i no r d e rt oi m p r o v et h ec o m m u n i c a t i o ne f f i c i e n c ya n dp l a t f o r mc o m p a t i b i l i t yo f d i s t r i b u t e dd a t am i n i n ga n ds o l v et h es e c u r i t yp r o b l e m se x i s t i n gi nt h ef i e l d so fd a t a t r a n s m i s s i o ne t c ，t h ep a p e rr e s e a r c h e do nh o wt oa p p l yt h et e c h n o l o g yo fm o b i l ea g e n t i nd i s t r i b u t e dd a t am i n i n gt ob u i l dd i s t r i b u t e dd a t am i n i n gs y s t e mw h i c hi so fr e m o t e i n t e r a c t i o n ，p l a t f o r mi n d e p e n d e n c y , b a n d w i d t hs a v i n g ，h i g h e rm a i n t a i n a b i l i t y a n d f l e x i b i l i t y b a s e do n “d i a g n o s i so fs e m i - h e a l t hs t a t eo fn e t w o r ke n g i n e e r i n gs y s t e m a n ds t u d i e so ni n t e l l i g e n tm a i n t e n a n c ed e c i s i o n - m a k i n gm e c h a n i s m g r a n t e db y c h o n g q i n gj i a o t o n gu n i v e r s i t yg r a d u a t ee d u c a t i o ni n n o v a t i o nf u n d ( n o 0 9 0 4 ) ，t h e p a p e rr e s e a r c h e da n da n a l y z e d t h ea p p l i c a t i o no fm o b i l ea g e n ti nd i s t r i b u t e dd a t a m i n i n gi nd e p t h m a i na c h i e v e m e n t so f t h ep a p e ri n c l u d e ： ( 1 ) t e c h n o l o g yo fm o b i l ea g e n tw a sc o m p r e h e n d e da n dg r a s p e di nd e p t h ，a n d c h a r a c t e r sa n ds y s t e ms t r u c t u r ee t c o fm o b i l ea g e n tw e r ed e e p l ya n a l y z e dh e r e t h e m e r i t sa n dd r a w b a c k so fo t h e rd i s t r i b u t e dc o m p u t i n gm o d e l sw e r ea n a l y z e d ，a n do nt h i s b a s i s ，a d i s t r i b u t e dd a t a m i n i n gm o d e l b a s e do nm o b i l ea g e n tw a sp r o p o s e d f u r t h e r m o r e ，o nt h eb a s eo fa n a l y z i n gt h ef a c t o r sw h i c hi n f l u e n c em i n i n gc a p a b i l i t y , c o s tm o d e l so fs e v e r a lt y p i c a ld i s t r i b u t e dd a t am i n i n gm o d e l sw e r er e s e a r c h e d s y s t e m f r a m e w o r ko fa g l e tp l a t f o r m ( d e v e l o p m e n tp l a t f o r mo fm o b i l ea g e n t ) ，l i f ec y c l e b a s i c a c t i o no f a g l e ta n dc o m m u n i c a t i o nm e c h a n i s mb e t w e e na g l e t sw e r es t u d i e dh e r e ( 2 ) m a k i n gu s eo fa g l e t so fm o b i l ea g e n tp l a t f o r m ，ap r o t o t y p e o fd i s t r i b u t e dd a t a m i n i n gs y s t e mw a sd e s i g n e da n dr e a l i z e d ，i nw h i c h t h ec h a r a c t e r so fm o b i l ea g e n ts u c h a sm o b i l i t y , a u t o n o m ya n dr e a c t i v i t yw e r eu t i l i z e d ，t h ec o n t r o l l i n gs t a t i o nd i s p a t c h e d a g l e t st or e m o t es t a t i o n st oc a r r yo u tm i n i n gt a s k ，a n dr e t u r n e dp a r t i a lm i n i n gr e s u l t st o t h ec o n t r o l l i n gs t a t i o n i nt h es y s t e m ，o n l yas m a l l q u a n t i t yo fc o d e ，p a r t i a lm i n i n g r e s u l t sa n ds t a t eo fa g l e t sn e e d e dt o m o v e ，a n dc o n s e q u e n t l y , c o m m u n i c a t i o nt r a 硒c w e r ed e c r e a s e d ( 3 ) o nf o u n d a t i o no fs t u d yo nt h e o r yo fa s s o c i a t i v er u l e sm i n i n ga n da l g o r i t h m s o fd i s t r i b u t e da s s o c i a t i v er u l e sm i n i n g , a n i m p r o v e da l g o r i t h mo ff d mw a sp u t 南n v 砌： a l g o r i t h mo fd d m a r b a i nt h i sa l g o r i t h m ，b e c a u s eo fu s i n gm o b i l e a g e n t ， c o m 】m l l n l c 确0 nm o d ea m o n gs t a t i o n si nd i s t r i b u t e dc o n d i t i o n w a st h o r o u g h l yc h a n g e d a n dt h r o u g ht h e o r e t i c a la n a l y s i s ，p a r t i a l m i n i n gr e s u l t so fr a n o t es t a t i o n sc o u l db e o b t a i n e da f t e ra g l e t sm o v i n go u ta n dh o m et w i c eb e t w e e nt h ec o n t r o l l i n gs t a t i o na n d t a r g e ts t a t i o n ( t h ea g l e t sw h i c hm o v e do u ta n dh o m et w i c ew e r ed i f f e r e n ta g l a s b e a t i n gd i f f e r e n tm i n i n gt a s k s ) ，t h a tc o u l dg r e a t l yd e c r e a s ec o m j t l u n i c a t i o nc o s ta n d i n c r e a s em i n i n ge f f i c i e n c yt h e e x p e r i m e n to nd a t ai nu c id a t as e t st e s t i f i e dt h ev a l i d i t v o ft h ea l g o r i t h m ，a n ds u p e r i o r i t yo fm i n i n g e f f i c i e n c yo ft h i sa l g o r i t h mw o u l db en l o r e e v i d e n te s p e c i a l l yf o rt r e m e n d o u sa m o u n t so fd a t a k e yw o r d s ：d a t a m i n i n g ，m o b i l ea g e n t ，a g l e t ，d a t a b a s e ，a s s o c i a t i o nr u l e s 目录 第一章绪论1 1 1课题研究的背景和意义1 1 2分布式数据挖掘的研究现状? 2 1 3论文的研究内容3 1 4论文的创新点4 1 5论文的组织结构4 第二章数据挖掘理论和分布式数据挖掘理论6 2 1 数据挖掘原理6 2 1 1 数据挖掘基本概念6 2 1 2 数据挖掘流程7 2 1 3数据挖掘系统的体系结构8 2 1 4 数据挖掘研究面临的主要问题8 2 2 分布式数据挖掘原理9 2 2 1分布式数据挖掘的关键技术1 0 2 2 2 分布式数据挖掘算法原理1 0 2 2 3 分布式数据挖掘的研究现状1 0 2 3 本章小结1 1 第三章分布式数据挖掘系统1 2 3 1 移动a g e n t 概述1 2 3 1 1 移动a g e n t 定义：1 2 3 1 2 移动a g e n t 特征1 2 3 1 - 3 移动a g e n t 体系结构1 3 3 2分布式数据挖掘系统结构1 4 3 2 1c ii e n t s e r v e r 模型1 4 3 2 2 m u l t i - a g e n t s 模型1 5 3 2 3 移动a g e n t 模型1 6 3 3影响分布式数据挖掘性能的因素分析1 9 3 4分布式数据挖掘系统时间代价模型2 1 3 4 1c l i e n t s e r v e r 挖掘时间代价模型2 1 3 4 2 m u l t i - a g e n t s 挖掘时间代价模型2 2 3 4 3 移动a g e n t 挖掘时间代价模型2 2 3 5 本章小节2 4 第四章基于a g l e t 的分布式数据挖掘原型系统设计2 5 4 1a g l e t 移动a g e n t 平台2 5 4 1 1a g l e t 系统框架2 5 4 1 2a g l e t 生命周期及行为方式2 6 4 2原型系统分析与设计2 8 4 2 1原型系统总体分析和设计2 8 4 2 2 原型系统模块设计与实现3 0 4 2 3 原型系统中a g l e t s 任务实现方式分析3 4 4 2 4 原型系统中a g l e t 之间的通信分析3 4 4 2 5 系统工作过程分析3 6 4 3 本章小节3 6 第五章f d m 算法的改进算法一d d m a r _ b a 算法3 8 5 1 关联规则算法分析3 8 5 1 1基本概念3 8 5 1 2 对以往关联规则算法的分析3 9 5 2 d d m a r b a 算法4 1 5 2 d d m a r b a 算法的总体架构4 1 5 2 2d d ma rb a 算法描述4 l 5 2 3d d m _ a r b a 算法分析4 3 5 2 4 d d m a r b a 对f d m 的改进分析4 4 5 3 d d m a r 一队算法性能实验4 4 5 3 1实验数据集与预处理4 4 5 3 2 实验环境4 5 5 3 3 性能比较实验4 5 5 3 4 实验结果分析4 8 5 4 本章小节4 9 第六章工作总结和展望5 0 致谢5 1 参考文献5 2 攻读硕士学位期间发表的论著及取得的科研成果5 6 第一章绪论 第一章绪论 1 1 课题研究的背景和意义 近年来，随着计算机技术的进步、计算能力以及存储能力的同益提高，挖掘 数据集规模有了迅速的增长，而且这些数据集大部分都按地理位置分布于多个场 所。而现在的数据挖掘算法及模型主要采用集中式。即使在数据分布式存储的情 况下，也要求把这些数据重新收集到一个集中的地方( 如数据仓库) 。这会导致响 应时间变长和数据私有性和安全性被破坏，尤其当分布式数据不同构的时候更是 这样。虽然网络带宽在增加，但还是比不上数据增长的速度，结果导致通过有限 的网络带宽来移动大容量的数据，而且现有的集中式数据挖掘算法不适合于将来 大容量、分布式的数据分析应用。再者，随着分布式信息系统的广泛应用，感兴 趣的数据源在物理上往往是分布、异构和自治的。当前处理分布式数据挖掘最常 用的方法是从不同的数据源收集数据到一个中心数据仓库，然后对数据仓库进行 数据挖掘。然而，在分布式环境中，由于来自数据的自治、异构的限制，使得采 用中心数据仓库的策略在许多情况下是不适当的。且由于组织结构或运营方面的 限制，异构且分散的数据源中的信息通常不适合进行全盘复制或合并。此外，由 于数据的私有性和保密、系统的不兼容性等方面的原因，把所有的数据都综合到 一个集中式平台中也是不现实的。因此，随着分布式信息系统的广泛应用，分布 式数据挖掘已成为数据挖掘发展的基本趋势之一1 引。 分布式数据挖掘研究中，合理地选用分布式技术，更好地达到较少的分布式 计算通信代价、各个站点数据的隐私保护、软件的平台兼容等效果非常必要。所 采用的分布式技术将直接影响到分布式数据挖掘系统的效率、健壮性等关键评价 指标，因此建立一个科学合理的分布式数据挖掘系统，具有重要的科研、经济价 值。目前，就分布式数据挖掘使用的分布式技术可分为三大类：基于移动代理技术 的分布式数据挖掘、基于网格技术的分布式数据挖掘、基于r m i ( r e m o t em e t h o d i n v o c a t i o n ，远程方法调用) 、c o r b a ( c o m m o no b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e ， 公共对象请求代理体系结构) 等其它分布式技术的分布式数据挖掘h7 l 。 移动a g e n t 是一种软件实体，它可自主地在异构的网络上，按照一定的策略 移动，寻找合适的计算机资源、信息资源或软件资源，利用与这些资源处于同一 主机或网络的优势，就近处理或使用这些资源，代表用户完成特定的任务。移动 a g e n t 是分布式技术与a g e n t 技术将结合的产物，它除了具有智能a g e n t 的最基本 的特性如反应性、自主性、交互性外，移动性是其中一个重要特性协3 。在分布式数 2 第一章绪论 据挖掘系统中，移动a g e n t 具有的诸多特性，使得它能接受任务驱动自主迁移到 远程主机上执行挖掘任务，只须移动的仅仅是代理本身少量的代码，无需传送大 量的数据，具有节约网络带宽、支持离线计算、提供平台无关性等优点，从而提 高通信效率、改善系统性能。 本论文即是从这背景出发，旨在研究分布式数据挖掘理论和移动a g e n t 技术， 提出一个基于移动a g e n t 的分布式数据挖掘模型，并建立其通信代价模型，为评 价分布式数据挖掘系统的性能提供评价指标并为改进分布式关联规则挖掘算法提 供改进方向。研究a g l e t 的迁徙机制、基本行为以及通信机制等，设计并实现一个 基于a g l e t ( 即移动a g e n t ) 的分布式数据挖掘原型系统。研究了关联规则挖掘理 论和现有的关联规则挖掘算法，提出一种基于移动a g e n t 的分布式关联规则挖掘 算法：d d m 且b a 算法。本论文创造性地将移动a g e n t 技术应用于分布式数据 挖掘中，为分布式数据挖掘系统中网络数据传输代价问题提供了一个新颖、有效 的解决方案，同时也解决了分布式数据挖掘平台多样性的难题，快速、准确地获 得有价值的信息和服务，为用户提供重要的、未知的信息或知识，指导政府决策、 企业决策、获取更大的经济效益和社会效益。 1 2 分布式数据挖掘的研究现状 分布式数据挖掘的概念源于：用户、数据、硬件资源以及挖掘需要的软件资 源在物理上是分布的。分布式数据挖掘是近几年才提出的新的研究领域在分布式 数据挖掘中，计算机是分布的，且每个计算机独享自身的资源，机器之间通过消 息传递进行通讯。由于网络带宽的限制使得通过网络传输数据的代价十分昂贵， 而在分布式数据挖掘中必须通过网络进行数据交换，因此如何通过减少数据的传 输量来达到降低传输的代价问题，就成为制约分布式数据挖掘的主要瓶颈。为了 解决这一问题，学者们提出了两种办法。第一种是采用有效的分布式计算模型来 减少数据的传输量；第二种是运用有效的分布式数据挖掘算法来实现对问题的解 决。以下就分别对这两方面进行介绍。 现在，就分布式数据挖掘使用的分布式技术可分为三大类：基于移动a g e n t 技 术的分布式数据挖掘、基于网格技术的分布式数据挖掘、基于r m i 、c o r b a 等其 它分布式技术的分布式数据挖掘。基于网格技术的分布式数据挖掘是当前的一大 热门，网格不仅能很好的解决数据分布问题，也能很好的解决计算分布的问题。 不过基于网格技术分布式数据挖掘分布是重要的挖掘问题，也是尚未攻克的难题。 尚未见系统性的研究成果，尤其未见基于o g s a ( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ) 网格数据挖掘成果。较有影响的是，欧共体的网格环境下数据挖掘工具与服务的 研究项目，但截止2 0 0 5 年尚处在工具与接口的描述与论证阶段。此外，一个开源 第一章绪论 3 的数据挖掘工具w e k a ，其中的一个分支，目前也刚刚起步归1 。基于r m i 、c o r b a 等 其它分布式技术，如刘伟等基于c o r b a 的数据挖掘工具k d d d c ，刘鸥、李师 贤的基于数据挖掘和c o r b a 技术的i d s s ( i n t e l l i g e n td e c i s i o ns u p p o r ts y s t e m ) 模型 等们叫。这种分布式对象技术在一般应用领域特别是企业计算中获得了很大的成 功，其软件工程方面的优越性十分突出，然而，他们的缺陷也较严重，其中最大 的问题是远程构件间的通信必须经过应用前端，耗费了大量的带宽网络，资源利 用很不合理。而移动代理提供了一种全新的分布式计算模型，由于移动代理具有 节约网络带宽、提供实时的远程交互、增强应用健壮性、提供平台无关性等优点， 许多典型的分布式数据挖掘系统都使用了这种技术，如s t o l f o 的j a m ( j a v a a p p l i c a t i o nm a n a g e r ，j a v a 应用管理器) 系统、k a r g u p t a 的p a d m a ( p a r a l l e ld a t a m i n i n g a g e n t s ) 系统、c h a v e z 的c h a l l e n g e r 系统、k a r g u p t a 、p a r k 等人的c d m 系 统。移动代理的前景极其广阔，是分布式计算技术发展的主要方向n 2 | 。 当前，分布式数据挖掘是一个崭新的研究领域。基于各类分布式技术的数据 挖掘算法，可大致分为两种：数据分布而计算不分布的算法，数据和计算都分布 的算法。数据和计算都分布的算法，由于做到了真正意义上的分布式数据挖掘， 符合分布式数据挖掘的发展趋势。这类算法，国内，有张力飞等提出的利用网格 服务的分布式频繁模式挖掘算法1 ；李宏等提出的分布式约束性关联规则挖掘算 法：d m c a 算法和d m a i c 算法n 3 h 1 4 1 ；方英武等人提出的分布式数据挖掘计 算过程( d i s t r i b u t e dd a t am i n gc a l c u l a t i n gp r o c e s s ，d d c p ) 算法5 l ，利用了本地节点 动态有序集合枚举树生成方法来代替数据库，节省了本地空间的占用。国外， a g r a w a l 等人提出的c d ( c o u n td i s t r i b u t i o n ) 、d d ( d a t ad i s t r i b u t i o n ) 分布式关 联规则挖掘算法；c h u e n g 等人提出来的d m a 和f d m ( f a s td a t am i n i n g ) 分布式关 联规则挖掘算法；s c h u s t e r 等提出的高性能关联规则挖掘；m e t h a ，a g r a w a l ，r i s s a n c e 提出的s u q 并行决策树算法；以及i b m 研究人员在此基础上进行改进得到的 s p r i n t 并行决策树算法u 明1 1 9 1 。 1 3 论文的研究内容 本论文的主要内容是移动a g e n t 技术在分布式数据挖掘中的应用，针对基于 a g l e t 技术的分布式数据挖掘原型系统以及分布式关联规则挖掘算法进行研究。概 括起来，具体的研究内容如下： 研究基于移动a g e n t 的分布式计算模型以及其他一些分布式计算模型。并 在此基础上，把分布式计算技术应用到分布式数据挖掘中，分析影响分布式数据 挖掘性能的因素，分别建立几种基于不同分布式计算技术的分布式数据挖掘模型 的通信代价模型，确定分布式数据挖掘系统的性能提供评价指标。 4 第一章绪论 详细分析系统模块的功能和系统体系结构，设计并实现一个基于a g l e t ( 即 移动a g e n t ) 的分布式数据挖掘原型系统，分析系统中a g l e t s 任务实现方式和a g l e t 之间的通信方式。 在研究分布式关联规则挖掘原理与算法，以及a g l e t 的迁徙机制、a g l e t 的 基本行为、a g l e t 间的通信机制等基础上，对f d m 算法进行改进，得出基于a g l e t 的分布式关联规则挖掘算法d d ma rb a 。对u c i 公共数据集上的数据进行的实 验，证明d d ma rb a 算法的有效性。并通过性能比较试验，证明d d ma rb a 算法对比a p r i o r i 算法在挖掘效率方面的优势，特别是对于海量数据集来说，挖掘 效率优势愈加明显。 1 4 论文的创新点 作为移动a g e n t 技术，a g l e t s 可应用于电子商务个人助理、安全代理、分布 式信息检索等方面。本论文将a g l e t s 运用到分布式数据挖掘系统中，能够明显的 减少通信代价、提高挖掘效率，其系统性能较基于c l i e n t s e r v e r 和m u l t i a g e n t s 模 型的分御式数据挖掘系统都有极大的提高。 对f d m 算法进行改进，得出一种基于a g l e t s 的关联规则挖掘算法 d d ma rb a ，利用移动a g e n t 的移动性、自主性、反应性，理论分析表明，该 算法只需在分布式站点与主站点间往返两次就得到全局频繁项集。f d m 算法中， 各站点问依靠轮询站点技术( p o l l i n gs i t e ) ，统计各个局部频繁项集的全局支持度， 且必须等待其它站点传来局部频繁项集的支持度，当站点数量很大时，算法的时 间效率较低，而d d ma rb a 算法中，移动a g e n t 的介入，彻底改变了分布式环 境中各站点间的通信方式，a g l e t 间的通信次数和通信量都很少，且a g l e t 在各站 点上的挖掘是独立进行的，因此极大地提高了算法的挖掘效率。 1 5 论文的组织结构 本论文共分七章，具体安排如下： 第一章综述了论文的研究背景和意义，同时概述了数据挖掘的发展现状和 分布式数据挖掘算法的研究现状，简要的介绍了目前的几种分行式技术在分布式 数据挖掘应用方面的优缺点，并提出了本文的解决办法和创新点。 第二章概述了数据挖掘的概念，介绍了数据挖掘的流程、数据挖掘系统的 体系结构和数据挖掘的研究现状，并概述了分布式数据挖掘的挖掘原理、关键技 术和国内外研究现状。 第三章详细介绍了移动a g e n t 技术，分析了基于c s 、m u l t i a g e n t s 和移动 a g e n t 模型的分布式数据挖掘系统结构，以及影响分布式数据挖掘性能的因素，建 立了几种典型的分布式数据挖掘模型的通信代价模型。 第一章绪论 5 第四章简介了a g l e t s 的系统机构、生命周期、基本行为等，详尽描述了一 个基于a g l e t s 的分布式数据挖掘原型系统的设计与开发，并深入分析了该系统中 a g l e t s 任务实现方式、a g l e t 问的通信方式以及系统工作过程。 第五章简介了分布式关联规则挖掘概念，对以往的分布式关联规则挖掘算 法作了分析，重点结合a g l e t s 技术，对f d m 算法进行改进，得到d d ma rb a 算法。运用该算法，对u c i 公共数据集上的数据进行挖掘效率比较实验，证明该 算法的有效性。并通过性能比较试验，证明该算法对比a p r i o r i 算法在挖掘效率方 面的优势，特别是对于海量数据集来说，挖掘效率优势愈加明显。 第六章对论文工作进行全面总结，并对未来研究提出展望。 6 第二章数据挖掘理论和分布式数据挖掘理论 第二章数据挖掘理论和分布式数据挖掘理论 数据挖掘是近些年来随着人工智能和数据库技术的发展而出现的一门新兴技 术。数据挖掘是一门交叉性学科，它是从大量的数据中运用分类、关联性分析、 序列分析、群集分析、机器学习、知识发现及其他统计方法筛选出隐含的、可信 的、新颖的、有效的信息的高级处理过程。本章对本文用到的数据挖掘和分布式 数据挖掘原理做些简单的介绍。 2 1 数据挖掘原理 2 1 1 数据挖掘基本概念 数据挖掘就是从大量的、不完全的、有噪音的、模糊的、随机的数据集中识 别有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。它是一 门涉及面很广的交叉学科，包括数据库技术、统计学、机器学习、高性能计算、 模式识别、神经网络、数据可视化、信息检索、图象与信号处理和空间数据分析 等相关技术。数据挖掘的对象包含大量数据信息的各种类型数据库。如对象一关 系数据库，面向对象数据库等，文本数据数据源，多媒体数据库，多媒体数据库， 空间数据库，时态数据库，以及i n t e m e t 等类型数据或信息集均可作为数据挖掘的 对象心0 。 7 数据挖掘这样一门交叉学科，它把人们对数据的应用从低层次的简单查询提 升到从数据中挖掘知识，提供决策支持，其具体功能包括乜： 自动预测趋势和行为。数据挖掘自动在大型数据库中寻找预测性信息，从 而迅速直接由数据本身得出相应的结论。 关联分析。数据关联是数据库中存在的一类重要的，可以被发现的知识。 若两个或多个变量的取值之间存在某种规律，就称为关联。关联可以分为简单关 联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网，为某 些决策提供必要的支持。 聚类。数据库中的自己可以被划分为一系列有意义的子集，即聚类。聚类 增强了人们对客观事实的认识，是概念描述和偏差分析的先决条件。聚类技术主 要包括传统的模式识别和数学分类方法。 概念描述。概念描述就是对某类对象的内涵进行描述，并概括这类对象的 有关特征。概念描述分为特征描述和区别性描述。前者描述某类对象的共同特征， 后者描述对象之间的差别。 偏差检测。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的 差别。 第二章数据挖掘理论和分布式数据挖掘理论 7 2 1 2 数据挖掘流程 根据数据挖掘的定义，挖掘的过程是一个多阶段的过程，设计数据准备、模 式搜索、只是评价，以及反复的修改求精；该过程要求有一定程度的智能型、自 动性；所发现的模式对于新的数据仍保持有一定的可信度，并且应该是从前未知 的；同时也要求发现的知识对于将来的工作有实际效用，而且能被用户理解。因 此数据挖掘过程一般由三个主要的阶段组成：数据准备、数据开采、结果表述和 解释心刳。如图2 1 所示。 数据源 图2 1 数据挖掘流程 p i g 2 1t h ep r o c e s so fd a t am i n i n g 数据准备。数据准备是数据挖掘中的一个重要步骤，这个阶段又可分为三 个子步骤：数据集成、数据选择、数据预处理。数据集成是将多文件或多数据库 运行环境下的数据进行合并处理，解决语义模糊性、处理数据中的遗漏和清洗脏 数据等。数据选择的目的是辨别出需要分析的数据集合，缩小处理范围，提高数 据采掘的质量。数据预处理的目的是将数据转换成适合于数据挖掘的形式，并进 行一些必要的数据约简。 数据开采。这个阶段进行实际的挖掘操作，使用智能方法挖掘数据模式或 规律知识。包括有：要先决定如何产生假设( 即是让数据挖掘系统为用户产生假 8 第二章数据挖掘理论和分布式数据挖掘理论 设，还是用户自己对数据库中可能包含的知识提出假设) 、选择合适的挖掘工具、 发掘知识的操作和证实发现的知识等步骤。 结果表述和解释。根据最终用户的决策目的对提取的信息进行分析，把最 有价值的信息区别分出来，并且通过决策支持工具提交给决策者。因此，这一步 骤的任务不仅是把结果表达出来( 例如采用可视化的方法) ，还要对信息进行过滤 处理。如果不能令决策者满意，需要重复以上数据挖掘过程。 2 1 3 数据挖掘系统的体系结构 数据清 图2 2 数据挖掘系统的体系结构 f i g 2 2t h es t r u c t u r eo fd a t am i n i n gs y s t e m 数据挖掘系统的体系结构如图2 2 所示。特定的数据挖掘请求经“图形用户 界面”送到“数据挖掘引擎”， “数据挖掘引擎”通过“数据访问接口( d a t a a c c e s s a p i ) ”在某个特定的数据库或文件系统进行相应的挖掘处理后，再将最终的挖掘 结果反馈给“图形用户界面”，挖掘得到的知识经过评价后也可以存入知识库，为 以后的数据挖掘任务或者决策服务。系统中的“数据访问接e l ( d a t a a c c e s s a p i ) 可为o d b c 或a d o 接口；数据源可以是应用最为广泛的关系数据库，也可以是 一般的文件系统、w