（通信与信息系统专业论文）分布式环境下数据挖掘分类算法研究.pdf

摘要 分类规则的挖掘是数据挖掘研究领域的一个重要问题，而传统的 数据挖掘算法和模式主要采用集中式，这不仅要求有高速的数据通信 网络，还会导致响应时间延长以及使数据的私有性和安全性遭受破 坏，不适合分布式环境下的数据模式挖掘。因此本文主要从分布式的 角度出发，针对分类知识的理论和方法进行了深入研究，提出了有效 的挖掘算法。 本文首先提出了一种采用纵向划分数据集和同步更新哈希表技 术来建立异构分布式环境下分类决策树的算法d s p r i n t ，以及采用区 间分割和区间筛选技术的d s p r i n t 改进算法。d s p r i n t 算法采用属性 直方图的数据结构，将类别列表合并到每个属性列表当中，减少了需 要驻留于内存的数据量。d s p r i n t 算法还采用纵向划分数据集和同步 更新哈希表的策略，根据最小g i n i 值选出可以用来更新的哈希表项， 对其相应条目进行修改，利用哈希表来记录并控制各分站点的节点分 裂情况，具有较高的准确率。针对d s p r i n t 算法处理连续值属性效率 较低的缺点，还将d s p r i n t 算法进行了改进，采用区间评估和区间筛 选的思想，通过取样将连续值属性的值域划分成多个区间，估计在各 个区间上有无找到最佳分割点的可能，最后在可能找到最佳分割点的 区间中逐一搜索，有效地提高了算法的工作效率。对比实验表明，当 选取合适的区间数时改进算法和d s p r i n t 算法在分类准确率上相同； 另外，当分站点数目逐渐增多时，两种算法均可以获得较高、稳定的 准确率，且改进算法在处理连续值属性时的计算效率要比d s p r i n t 算 法更高。 另外，针对分布式环境中满足单调性约束条件的分类闯题，本文 将r p o t h a r s t 提出的建立单调性决策树的思想在分布式环境中进行 拓展，对d s p r i n t 算法进行补充，增加了修改规则u p d a t e ，将生成 的非单调性决策树修正为单调性。使无需随时增加各个分站点数据集 数目，仅插入少量数据项，通过分裂一些叶节点，增加少量分枝即可 实现决策树单调化。 本文进一步针对常规分布式数据挖掘系统存在的数据分块、结果 集成、安全性等问题，提出将移动代理技术和数据挖掘技术相结合， 利用m o b i l ea g e n t 的可移动性、分布并行性、异步性、资源优化等 特点，搭建适合大容量、分布式数据分析应用的数据挖掘系统平台， 运用移动代理技术完成分布式数据挖掘中适配器、数据挖掘代理、数 据库和用户问通信、程序调用和代码迁移。 关键词数据挖掘，分类规则，决策树，单调性约束，移动代理 a sa ni m p o r t a n tr e s e a r c ha r e ai nd a t am i n i n g ，t r a d i t i o n a la l g o r i t h m s a n dm o d e l so fc l a s s i f i c a t i o nw o r k b yr e g u l a r l yu p l o a d i n gm i s s i o nc r i t i c a l d a t ai nt h ew a r e h o u s ef o rs u b s e q u e n tc e n t r a l i z e dd a t am i n i n g p l i c a t i o n n i sc e n t r a l i z e da p p r o a c hi sf u n d a m e n t a l l yi n a p p r o p r i a t ef o rm o s to ft h e d i s t r i b u t e da n du b i q u i t o u sd a t am i n i n ga p p l i c a t i o n s n el o n gr e s p o n s e t i m e ，l a c ko fp r o p e ru s eo fd i s t r i b u t e dr e s o u r c e s ，a n dt h ef u n d a m e n t a l c h a r a c t e r i s t i c so fc e n t r a l i z e dd a t am i n i n ga l o g r i g h m sd on o tw o r kw e l li n d i s t r i b u t e de n v i r o n m e n t s s t a r t i n gb yd i s t r i b u t e dp o i n t so fv i e w , t h ep a p e r p r e s e n t st h o r o u g he x p l o r a t i o na n da n a l y s i so nc l a s s i f i c a t i o nk n o w l e d g e ， a n da d v a n c e ss u p e r i o rd i s t r i b u t e da l g o r i t h m s f i r s t l y , t h ep a p e rp r o p o s e sd s p r i n ta l g o r i t h mt h a ta d o p t st h e v e a i c a l y - - p a r t i t i o n i n g d a t a s e t s a n d s y n c h r o n o u s l y - - u p d a t i n g - h a s h - t a b l e t e c h n i q u e t ob u i l dd e c i s i o nt r e e si n h e t e r o g e n e o u s d i s t r i b u t e d e n v i r o n m e n t ，a n di t si m p r o v e da l g o r i t h mt h a ta d o p t si d e a so fs e c t i o n e s t i m a t i o na n ds e c t i o nf i l t r a t i o n i nd s p r i n t , t h ed a t as t r u c t u r eo f h i s t o g r a mi so f f e r e dt oc o m b i n ec l a s sl i s t si n t oe a c ha t t r i b u t el i s t 。w h i c h h e l p sr e d u c ed a t at of i t i nm e m o r y d s p r i n tf u r t h e ri n c r e a s e st h e a c c u r a c yo ft h ec l a s s i f i c a t i o nm o d e lb ya p p l y i n gh a s h t a b l et or e c o r da n d s u p e r v i s en o d e ss p l i a i n ga m o n gd i s t r i b u t e dd a t as i t e s n es t r a t e g yo f v e r t i c a l l yp a r t i t i o n i n gd a t a s e t sa n ds y n c h r o n o u s l yu p d a t i n gh a s h t a b l ea r e d e s i g n e dt oc h o o s eo u ta n dm o d i f yc o r r e s p o n d i n ge n t r i e si nh a s h t a b l e ， b a s e do nt h el o w e s tv a l u eo fg i n i a i m i n ga tt h ew e a k n e s st h a td s p r i n t s h o w sl o we 蚯c i e n e yi nd e a l i n gw i t hc o n t i n u o u sa t t r i b u t e s a ni m p r o v e d a l g o r i t h mi sd e v e l o p e db yi n t r o d u c i n gi d e a so fs e c t i o ne s t i m a t i o na n d s e c t i o nf i l t r a t i o n ，t h a ti st op a r t i t i o nv a l u ed o m a i n so fc o n t i n u o u s a t t r i b u t e sb ys a m p l i n g ，t h e ne s t i m a t et h ep r o b a b i l i 哆o ff i n d i n gt h eb e s t s p l i tp o i n ti ne a c hs e c t i o n ，a n dl a s ts e a r c hl i k e l ys e c t i o n so n eb yo n e u s i n gm e a s u r e m e n t sf r o ma c t u a li m p l e m e n t a t i o n so ft h e s ea l g o r i t h m s ，i t s h o w e dt h a td s p r i n ta l g o r i t h ma n di t si m p r o v e da l g o r i t h me x h i b i t a p p r o x i m a t e l ye q u a li nc l a s s i f i c a t i o na c c u r a c yw h e r ea p p r o p r i a t en u m b e r o fs e c t i o n si ss e l e c t e d m o r e o v e r , t h ea c c u r a c yi sh i g h e ra n di n v a r i a b l e w i t ht h ei n c r e a s e m e n to ft h en u m b e ro fd i s t r i b u t e ds i t e s e x p e r i m e n t s a l s os h o w e dt h a ti m p r o v e dd s p r i n t p e r f o r m sf a s t e rt h a nd s p r i n t s e c o n d l y , f o rc l a s s i f i c a t i o np r o b l e m sw i t hm o n o t o n i c i t yc o n s t r a i n t s i nd i s t r i b u t e dd a t am i n i n g ，t h ep a p e rs u g g e s t st oe x t e n dr p a t h a r s t s m e t h o do nb u i l d i n gm o n o t o n ed e c i s i o nt r e e st od i s t r i b u t e de n v i r o n m e n t a sac o m p l e m e n t a t i o no fd s p r i n t , t h ea l g o r i t h ma d d su p d a t er u l ei n ) s p r i n t t h u s ，an o n - m o n o t o n ed e c i s i o n t r e ec a nb er e p a i r e dt ob e m o n o t o n eo n l yb ya d d i n gc o m e re l e m e n t st ot h el e a v ea n dg r o w i n gaf e w m o r eb r a n c h e sw h e r en e c e s s a r y , w i t h o u tf r e q u e n t l yi n s e r t i n ge l e m e n t st o d a t a s e t si nd i s t r i b u t e dd a t as i t e s t h i r d l y , c o n s i d e r i n gp r o b l e m se x i s t i n gi nt r a d i t i o n a ld i s t r i b u t e d , d a t a m i n i n g , s u c ha sd a t af r a g m e n t a t i o n ，r e s u l t si n t e g r a t i o na n ds e c u r i t y t h e p a p e ra d d r e s s e sc o m b i n a t i o no ft h et e c h n i q u eo fm o b i l ea g e n t sa n dd a t a m i n i n g ，w h i c hm a k e si t f e a s i b l et oe s t a b l i s had a t am i n i n gs y s t e m a v a i l a b l ef o rd a t aa n a l y s i sa n da p p l i c a t i o no fh u g ea n dd i s t r i b u t e d d a t a b a s e s i nt h i sa p p r o a c h ，c o m m u n i c a t i o n sb e t w e e nf a c i l i t a t o r s ，d a t a m i n i n ga g e n t s ，d a t a b a s e s a n dr i s e r s ，p r o g r a m s r u n n i n ga n dc o d e s t r a n s f e r e n c ei sa b l et ob ef u l f i l l e dd u et om o b i l ea g e n t s m o b i l i t y , p a r a l l e l i z a b i l i t y , a s y n c h r o n ya n d r e s o u r c eo p t i m i z a t i o n k e y w o r d sd a t am i n i n g ，c l a s s i f i c a t i o nr u l e s ,， d e c i s i o nt r e e s ，m o n o t o n ec o n s t r a i n t s ， m o b i l ea g e n t ， 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：复翌日期：丝煎年垒月笪日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：霆宝导师签名盔l 日期：垫夔年华月卑日 硕士学位论文第一章绪论 1 1 引言 第一章绪论 当今的世界正处于一个“数据爆炸”的时代。由于数据的长期积累，有些数 据库变得非常庞大，目前数百万乃至上千万条记录的数据库已不罕见。随着 i n t e r n e t 的迅速发展，大量数据涌到人们面前，人们面对的问题不是缺少数据， 而是被数据淹没了，即所谓“人们被数据淹没，却饥饿于知识”。仅依靠传统的 统计分析工具和检索工具已经远远不够了在巨大的商业利益的驱动下，一个新 的研究领域知识发现应运而生。由于蕴藏知识的信息大多存储于数据库中， 数据库中的知识发现( 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 s ，i d ) ，又称数据挖 掘( d a t a m i n i n g ，咖) ，目前它已成为人工智能、统计学、数据库等领域研究的 热点之一 k d d 一词首次出现在1 9 8 9 年8 月举行的由美国人工智能协会( a m e r i c a n a s s o c i a t i o nf o ra r t i f i c i a li n t e l l i g e n c e ，简称a 从i ) 组织的第1 1 届人工 智能联合学术会议上，标志着k i ) d 的正式诞生。此后，有越来越多的研究者投身 其中。迄今为止，由a 从i 主办的k d d 研讨会已经召开了多次1 9 9 7 年亚太地区 在新加坡组织了第一次规模较大的p a k d d ( t h ep a c i f i c - a s i ac o n f e r e n c eo n k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 学术研讨会，以后每年此会议都举行一 次。a a a i 和u c a i 这两大系列会议均开设了k d d 专题。此外，数据库、人工智能、 信息处理、知识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊m 。 k d d 将智能技术与数据库相结合，不但为决策者提供知识和策略，而且为投资者 带来经济效益最近几年，为了处理数据仓库和i n t e r n e t 上浩如烟海的数据， i b m 、微软、g m 等大公司以及n a s a 等机构竞相投入资金以推动k d d 的研究及开 发实用化的数据挖掘系统。知识发现已经成为当今计算机科学与技术研究的热点 领域之一 我国学者及时地开展了知识发现方面的研究工作，一些高等院校与科研机构 也开放了相应的知识发现原型系统。目前，在国内许多重要的学术会议如中国人 工智能联合学术会议、数据库学术会议、机器学习学术会议等也都将知识发现列 为重要的研究专题。 数据挖掘所面临的最大挑战是计算效率问题。解决的途径之一是开发高效的 分布式算法或并行算法。有关分布式数据挖掘的研究目前还比较少，但自从1 9 9 8 硕士学位论文第一章绪论 年在k d d 的国际会议上作为专门的主题讨论以来，在以后的有关k d d 会议上，都 作为一个讨论的主要问题，相关的研究也越来越多。国内武大等目前也开展了这 方面的研究。 1 2 数据挖掘概述 2 0 世纪9 0 年代，人们逐渐认识到数据除了可以用于联机事务处理外，还有 战略计划的用途。2 l 世纪的商业竞争不仅取决于对市场的反应速度，还取决于 对本行业新知识的获取、积累和有效利用的能力，关键是对于数据仓库有效的数 据管理和交互式的数据分析能力。丙数据挖掘则是后者技术发展的颠峰。 ，2 1 数据挖掘的定义 数据挖掘( 瑚) ，也称作数据采掘、数据开采等。许多人把。数据挖掘”和 “数据库中的知识发现”看作是等价的概念，在这种意义下，它们的定义是一致 的。一种比较公认的定义是f r a w l e yu ，p i a t e s t s k y - s h a p i r og 等人提出的：数 据挖掘，即数据库中的知识发现( k d d ) ，是一个在数据中提取出有效的、新颖的、 有潜在实用价值和易于理解知识模式的高级过程四其中： 数据：是用来描述事物的信息集合，是进一步发现知识的原材料。 新颖：经过数据挖掘提取出的模式必须是新颖的模式是否新颖可以通过两 个途径来衡量：其一是通过对比当前得到的数据和以前的数据或期望得到的数据 之间的比较来判断该模式的新颖程度；其二是通过对比发现的模式与已有的模式 的关系来判断。， 潜在可用：即提取出的模式应该是有实际意义的。 易于理解：数据挖掘的一个目标就是将数据库中隐含的模式以容易被人理解 的形式表现出来，从而帮助人们更好地了辫数据库中所包含的信息。数据挖掘不 同于以往知识获取技术，它的特点之一是发现的知识是人们( 至少是领域专家) 易于理解的，如“i f t h e n ”的形式。因此数据挖掘也是一个人机交互、螺旋 上升的过程 模式：对于集合f 中的数据，可以用语言l 来描述其中数据的特性。表达式 e l e 所描述的数据是集合f 的一个子集f e 。只有当表达式e 比列举所有r 中元素的描述方法更为简单时，才可称之为模式” 高级过程：数据挖掘是对数据进行更深层处理的过程，而不是仅仅对数据进 行加减求和等简单运算或查询，因此说它是一个高级的过程。 2 硕士学位论文第一章绪论 1 2 2 数据挖掘技术的分类 数据挖掘的演变融合了来自不同学科领域的技术和成果，使得目前的数据挖 掘技术和系统表现出多样的形式。对数据挖掘技术进行分类，可以帮助潜在的用 户区分不同的系统从而选择适合自己需求的种类。从不同的视角看，数据挖掘技 术有几种分类标准：根据发现知识的种类分类，根据挖掘的数据库的种类分类和 根据采用的技术分类。 1 根据发现知识的种类分类 根据发现的知识种类可分为：关联规则发现、分类或预测模型知识发现、数 据总结、数据聚类、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现 等本文的研究重要涉及分类知识的发现，所以后续章节中将对这一问题作详细 介绍 2 根据挖掘的数据库的种类分类 数据挖掘基于的数据库类型有：关系型、交易型、面向对象数据库、空间数 据库、时态数据库、文本数据源、多媒体数据库、异质数据库、遗留数据库，还 有基于数据仓库的数据挖掘系统，以及基于国际互联网( w w w ) 或w e b 的数据挖 掘系统等 3 根据采用的技术分类 根据数据挖掘所采用的技术，可租分为：统计分析、机器学习方法、模式识 别、面向数据库或数据仓库的技术、可视化技术和神经网络等。统计方法中，可 细分为：回归分析、判别分析、聚类分析( 系统聚类、动态聚类等) 、探索性分 析等。机器学习中，可细分为：归纳学习方法( 决策树，规则归纳等) 、基于范 例学习、遗传算法等数据库方法主要是多维数据分析或联机分析处理方法，另 外还有面向属性的归纳方法。当然，一个完善的数据挖掘系统通常采用多种技术， 结合它们的优点设计出有效的、集成的技术 1 2 3 数据挖掘研究存在的主要问题 d m 的研究仍处于初级阶段，还有很多的研究难题和面临的挑战，如数据的 巨量性、动态性、噪声，缺值和稀疏性，发现模式的可理解性、兴趣或价值度量， 应用系统的集成，用户的交互操作，知识的更新管理，复杂数据库的处理等。 1 有效处理巨量和高维的数据 包含上百万条记录和数千兆字节甚至数兆兆字节的数据库已经司空见惯，另 外数据库关系表所涉及的属性或交量数也大到成百上千的数量。这种数据的巨量 和高维性使得数据挖掘时模式的搜索空间异常巨大，同时还可能导致搜索出无意 3 硕士学位论文 第一章绪论 义模式的机会增加。传统的技术已经难以适用，如常规的机器学习方法一般只能 处理不超过几千个记录或例子的数据集为了解决这些问题，需要有高效的特别 是线性计算复杂度的算法、抽样方法、分布式挖掘技术、大规模并行处理技术、 维数削减方法等技术 2 数据的动态变化和知识的更新维护 数据的动态变化常常使得以前发现的模式不再有效，特别是数据库可能增 加、删除或改变变量。发生这些情况时则要求设计删系统必须考虑知识的更新 维护，如怎样解决知识冲突。另外数据的动态性也提出了新的蹦问题：趋势或 变化模式发现任务以及主动数据库挖掘研究。 3 改迸用户的交互性和充分利用背景知识 目前很多叫工作的主要方向还是围绕在算法的效率上研究，大多数咖系统 还没有充分考虑用户的参与而使得交互性较差。目前在可视化以及数据仓库中的 多维数据分析工具在这方面做得较好，但在其他删方法中还有大量得工作要做。 k d d 系统与人工智能有密切的关系，背景知识或领域知识在智能化、自动化的k d d 系统中势必扮演重要的角色。充分使用背景知识使撂在巨大的模式空圊中的搜索 更为有效、有目的。 4 数据噪声与缺值 在商业数据库中噪声和缺值是一种常见现象。如美国人口普查数据的错误率 就高达2 0 ，错误或噪声可能来自于数据录入的误操作或其它实际中不可避免 的因素( 如民意调查的主观性) 。数据遗失有两类情况；一是某些字段上缺值， 另一是数据库在设计阶段就可能没有考虑某些重要属性或字段( 数据库并不是由 于附而存在的，它的设计有自己的考虑之处) ，而这些重要属性对于d m 进行知 识发现可能很重要。 。 5 ，提高模式的可理解度 很多应用中要求发现的模式具有好的可理解性。从模式的表示角度看，目前 的方法包括可视化方法、图形表示( 如贝叶斯概率依赖图、决策图) 、规则表示、 自然语言生成等。 6 应用系统的集成 一个单独的蹦发现系统如果不和具体的应用系统集成或结合，将毫无意义。 d m 应该和数据库管理系统或m i s 、电子表单，实时传感数据采集系统，特别是决 策支持系统集成在一起数据仓库上的o l a p 技术是一种典型的集成。 目前，人们正把数据仓库的研究和数据挖掘的研究结合起来。数据仓库的发 展为数据挖掘开辟了更广阔的空间，数据仓库完成了对数据的收集、集成、存储、 管理等预处理工作，使得数据挖掘更专注于知识和规则的发现，充分发挥数据挖 4 硕士学位论文 第一章绪论 掘技术的潜力，为决策提供更有力的支持。由于数据仓库所具有的新的特点，给 数据挖掘技术提出了更高的要求，数据仓库环境下的数据理论和技术将成为信息 科学学术界新的研究热点 7 处理复杂的数据和数据库 目前蹦的发掘对象，从数据库看，主要是面向关系型数据库( 也有交易数 据库) ；其他类型的数据库，如面向对象数据库、空间数据库、时态数据库、特 别是随着i n t e r n e t 的迅速发展，w e b 上的信息或知识发现也已得到重视。从数 据库看，d m 处理的最多的还是数值数据。数据库发展的一个趋势是各种类型数 据的使用，特别是多媒体数据越来越多，这要求相应的叫系统不但有处理数值 数据的功能，还应能处理符号、文本、声音、图形、图像、视频等类型数据 8 私有数据的保护与数据的安全性 什么情况下数据挖掘将会导致对私有数据造成侵犯和采用什么手段来防止 敏感信息的泄漏的研究也非常重要。 1 3 分布式数据挖掘概述 从结构上分，有两大类分布式系统：紧密耦合系统和松散耦合系统”。紧密 耦合系统主要是指多处理器的并行系统，即基于共享内存的多处理器并行模式或 有特殊的通信线路连接的分布式非共享的并行系统。在松散耦合系统中，每个 c p u 拥有独立的存储器，相互间通过通信线路来连接，也就是所说的局域网、广 域网、互联网等。松散耦合系统按照其数据的分布形式又可分为同构分布式系统 和异构分布式系统。实际上更常见的是异构分布式系统。 分布式数据挖掘的数据源是分布式数据库，或者是把集中式数据库按水平方 式或垂直方式划分( 如图1 - 1 所示) 倜哪后分布在不同站点的分布式数据集。在 水平划分情况下，各站点的数据是同构( 或同质) 的，即每个站点上的数据具有 相同的特征( 或属性) 集。在垂直划分情况下，各站点的数据是异构( 或异质) 的，即每个站点上的数据具有不同的特征( 或属性) 集。 ( a ) 同构分布式数据集异构分布式数据集 图1 - 1 分布式数据集 5 硕士学位论文第一章绪论 1 3 1 分布式数据挖掘的特点 分布式数据挖掘具有集中式数据挖掘的特性。同时，由于它的分布性，从而 具有了许多新的特点 1 全局挖掘和局部挖掘 和任何分布式系统一样，在分布式数据挖掘系统中，数据的物理位置可以是 分散的，单个节点的数据在逻辑上是一个整体。对于一个数据挖掘任务而言，如 果它是针对所有数据的，则称为全局挖掘；如果它是针对本地数据，则称为局部 挖掘。对于一个局部挖掘，它既可以独立于全局挖掘，也可以作为全局挖掘的一 部分；而对于一个全局挖掘，它既是一个不可分割的整体，也可以由若干局部挖 掘通过一定的方式组合在一起 ： 2 全局知识和局部知识 全局挖掘的结果，称为全局知识；局部挖掘的结果，称为局部知识。全局知 识并不是局部知识简单的合并，局部知识必须经过一定方式的组合和调整才能构 成全局知识。任何一部分局部知识的变化，都将影响到全局知识的变化。 3 挖掘部件的分布 这里的挖掘部件可以理解为一个挖掘算法。在分布式数据挖掘系统中，不但 数据、知识是分布存储的，各挖掘部件也可以分布它包括两种情况： ( 1 ) 各节点有独立完整的挖掘部件在这种情况下，各挖掘部件可以独立完 成挖掘任务，获得局部知识：也可以综合这些局部知识，获得全局知识。 ( 2 ) 各节点只存放部分挖掘部件，由它们可以构成一个完整的挖掘部件。这 种情况下，各节点的挖掘部件不能独立完成挖掘任务，必须相互配合，共同完成 全局知识的获取。 4 挖掘的透明性 对于一个全局挖掘过程而言，它涉及到分布在各节点的数据。而对于一个全 局用户来说，该过程应该是透明的。如果分布式数据挖掘系统是建立在分布式数 据库系统基础之上的，那么全局挖掘过程由分布式数据库中的全局概念模式支 持，挖掘的透明性是依靠分布式数据库实现的；如果分布式数据挖掘系统是建立 在多个数据库系统之上，即没有全局概念模式的支持，则它必须自己实现挖掘过 程的透明。对于无全局模式支持的情况，挖掘透明性是通过任务的分解和结果的 合并实现的。 5 ，并行化挖掘 在分布式系统中，数据挖掘算法效率与通信模型和数据的分布密切相关对 于不同的体系结构，必须采用不同的并行挖掘策略。目前的一些并行数据挖掘算 6 硕士学位论文第一章绪论 法大多是用于多处理器的紧耦合方式，对于松耦合方式，如在l a n 、m a n 等环境 下，由于带宽、传输延迟等网络参数的不同，这些并行数据挖掘算法并不适用 因此，在分布式环境中，应根据不同的通信模型，选择适当的数据挖掘算法。同 时，根据数据分布的不同，也应选择相应的并行化策略。 6 知识的增量式更新 当数据发生变化或挖掘时的参数发生变化，都需要更新挖掘结果。如果将挖 掘过程重新运行一边，代价无疑是非常昂贵的。通常的办法是，充分利用已有的 挖掘结果，只针对改变的部分数据或参数进行挖掘，然后调整修改已有的规则。 在分布式数据挖掘中，知识的更新主要是指对全局知识的更新，主要有两种方式： ( 1 ) 根据数据或参数的变化，直接对已有的全局知识进行增量式更新。 ( 2 ) 根据数据或参数的变化，先对局部知识进行增量式更新；然后，根据局 部知识的变化，调整更新全局知识。 、 7 数据的实时挖掘 分布式数据挖掘中，挖掘是分布在各节点进行的，相对预先收集数据在集中 处理的挖掘方式，功能的分布使分布式数据挖掘系统能适合动态的、变化较快的 数据的分析处理 1 3 2 分布式数据挖掘策略 分布式数据挖掘是以网络环境为基础，不同的网络环境对数据挖掘系统结 构、尤其是对数据挖掘的策略有很大影响。目前的一些并行挖掘均是以多处理器 为基础，这些方法并不完全适合于松耦合的分布式环境，如局域网和广域网。事 实上，在分布式环境下，数据挖掘的执行总与网络性能密切相关，对于不同的网 络模型，数据挖掘的过程应有所区别，以保证较高的挖掘效率 局域网、广域网和多处理器系统间有着明显的不同。相对来说，在多处理器 系统中所有事情总是同时发生的：当其中一个部件开始传输，其它部件几乎马上 就知道了，因此通信次数不会对算法效率造成影响。而对于局域网和广域网，则 有较长的传输延迟分布式挖掘的效率不仅取决于本地的执行效率，而且与传输 延迟有关。为减少传输延迟，分布式数据挖掘不仅要尽量减少通信量，而且传输 延迟较大时( 松耦合结构) ，应尽量减少通信次数。 在分布式环境下，影响数据挖掘执行的不仅仅是网络模型，数据的分布也对 挖掘策略有着重要影响。根据数据的集中或分散，可以采用两种策略，即任务并 行化方法和数据并行化方法 在任务并行化挖掘中，各处理器面对的是一个数据整体。挖掘任务被划分为 若干子任务分配给各处理器，各处理器根据全局数据独立获得各自的局部知识， 7 硕士学位论文第一章绪论 最后将各局部知识合并为全局知识。任务并行化挖掘的有点是各处理器独立完成 各自任务，减少通信量它的问题是如何平衡各处理器的负载。解决的办法是采 用多次分配任务，即任务的划分不是一次性的，而是每次根据计算的中间结果重 新分配任务，以使各处理器负载得到平衡。显然，这种办法所付出的代价是通信 开销。因此多次划分的方法较适合紧耦合的分布式系统。 在数据并行化方法中，全局数据被分为若干区域，各处理器有自己的局部数 据。根据不同的网络模型，可以采取两种方法：同步方式和异步方式在同步方 式中，各处理器必须同步以构造相同的模式，为达到这_ 目的，各处理器必须交 换信息同步挖掘。这种方法通信量大，单个处理器的开销较小，较适合紧耦合的 结构。在异步的方法中，各处理器根据本地数据集获得局部知识，然后归并各局 部知识以获得全局知识。在这种方式下，各处理器不必多次交换同步信息，通信 量小，适合松耦合结构。但在这种方式下，归并各局部知识时，会带来处理器的 额外开销。它的本地开销要比同步方式大。 总之不同的网络模型和数据分布决定了不同的分布式数据挖掘策略。 ， ， 1 4 课题的研究意义及研究现状 本课题来源于教育部科学技术研究重点项目( 项目编号n o 2 0 0 0 31 5 6 ) 作为一种重要的数据分析形式，分类知识挖掘的目的在于提取出描述重要数 据类的模型或预测未来的数据趋势，具有着极为广泛的应用背景。随着计算机及 通信网络的快速发展，分布式计算环境日益普遍。在互联网，企业内部互联网、 本地网和无线网等分布式环境中，都包括许多不同类型的含有大量数据和计算机 结点的分布式数据源。分析和监督这些分布式数据源就需要研究专门的分布式数 据挖掘技术。 7 而传统的数据挖掘算法和模式主要采用集中式，这不仅要求有高速的数据通 信网络，还会导致响应时间延长以及使数据的私有性和安全性遭受破坏。因此， 研究如何在不破坏原始数据的基础上对局部数据进行处理，开发高效、低通信代 价的分布式分类挖掘算法是现在的热点研究问题，具有十分重要的意义。 、 目前，分布式环境下分类算法的研究主要分为两个方向：一种是研究同构分 布式存储数据的，另一种是研究异构分布式存储数据的。对于同构分布式分类器， 一个很著名的分布式分类器是m e t a - l e a r n i n g 分类器。它主要实现了分布式数据 挖掘的两个主要特性：并行性和低通信代价。在这种方法中，局部数据节点使用 有监督学习规则来学习分类，将局部学习分类器生成的数据集成到啪t a 一级后， 再进行学习分类。在舱t a 一级的学习分类可以的递归进行下去，最终形成一个 m e t a - l e a r n i n g 分类器层次结构 8 硕士学位论文第一章绪论 对于异构分布式分类器，由于在分布的数据结点上的数据是异构的，因此从 局部挖掘结果中不能得到系统的全部信息。p r o v o s t 和b u c h a n a n 于1 9 9 5 年提出 了一种异构分布式数据的挖掘方法：通过将大问题分解为子问题来实现基于特性 空间的异构划分，但这种方法要求结点间必须具有相关性 还有一种使用整体思想进行异构数据分类的方法( k a g a nt u r n e r 和j o y d e e p g h o s h ，2 0 0 0 年) 。该方法使用次序统计值从各异构数据结点集成高变量模型， 即选择一个适当的次序统计值，在一定的规则指导下，对各分类器进行预测。尽 管这种方法比其他方法具有更好的鲁棒性，但仍然不能体现系统的整体特性。 k a r g u p t a 和他的同事提出了汇集型数据挖掘( c o l l e c t i v ed a t am i n i n g ， c 删) 体系结构c d m 适用于异构环境的数据分析和预测，融合了通信、机器学 习、统计学和分布式数据库的多种理论，使用正交基函数进行局部分析，解决通 常的局部数据分析方法不能正确构造全局数据模型所需要的局部模型的问题。 总得来说，分布式环境下( 尤其是异构分布式环境) 数据挖掘分类算法的研 究还属于一个比较新的研究课题。受内存和效率限制的问题，目前还没有一种公 认的算法在能够保证高效、低通信代价的基础上，对同构和异构分布式存储的数 据建立一个能够体现数据整体性能的分类预测模型。因此，如何设计出更好的适 合于联机决策应用的分布式数据挖掘分类算法成为目前乃至今后数据挖掘研究 工作非常重要的一个方面。 、 1 5 论文的主要工作 本文研究的主要内容是分类规则挖掘的理论和方法问题，主要从分布式角度 进行深入研究。研究的重要内容包括以下三个方面： 1 研究分布式环境中分类规则挖掘的有效算法：针对分布式环境，尤其是异 构数据集的分布特点，提出将具有强可伸缩性的s p r i n t 算法推广到分布式环境 中即d s p r i n t 算法该算法采用纵向划分数据集和同步更新哈希表的策略， 可以较准确且直观地构建异构环境中的分类决策树；进一步针对d s p r i n t 算法最 佳分割点的计算量大的缺点，提出了一种改进的快速寻找方法。该方法采用区间 评估、筛选和局部逐一搜索等策略，大幅度地缩小了搜索空间； 2 研究满足单调性约束条件的分布式决策树建立：针对单调性约束问题，在 d s p r i n t 算法的基础上进行补充，将p o t h a r s t 算法的修改规则进行修正，使仅 需要增加少量分枝，就可将非单调性决策树修正为单调性决策树； 3 从分布式数据挖掘系统着手，提出运用移动代理技术完成分布式数据挖掘 中适配器、数据挖掘代理、数据库和用户之间的通信、程序调用和代码迁移。 有关以上工作的详细论述将在本文的第二章到第五章的篇幅中给出。 9 硕士学位论文第一章绪论 1 6 论文的组织 本文首先在第二章对数据挖掘中分类知识的理论和主要算法作一个较全面 探讨： 第三章提出了一种采用纵向划分数据集和同步更新哈希表技术来建立异构 分布式环境下分类决策树的算法d s p r i n t d s p r i n t 算法采用属性直方图的数据 结构，将类别列表合并到每个属性列表当中，减少了需要驻留于内存的数据量。 算法还采用纵向划分数据集和同步更新哈希表的策略，根据最小g i n i 值选出可 以用来更新的哈希表项，对其相应条目进行修改，利用哈希表来记录并控制各分 站点的节点分裂情况，具有较高的准确率。钎对d s p r i n t 算法处理连续值属性效 率较低的缺点，本章还将d s p r i n t 算法进行了改进，采用区间评估和区间筛选的 思想，通过取样将连续值属性的值域划分成多个区间，估计在各个区问上有无找 到最佳分割点的可能，最后在可能找到最佳分割点的区间中逐一搜索，有效地提 高了算法的工作效率本章还将d s p r i n t 算法及其改进算法与s p r e a d 算法进行 了对比分析； 第四章将r p o t h a r s t 提出的建立单调性决策树的思想在分布式环境中进行 拓展，对上章的d s p r i n t 算法进行补充，使能够解决分布式环境中的满足单调性 约束条件的分类问题对于分布式存储的数据而言，不断地同步在各个分站点的 数据库中插入数据项，是难于实现的，因此本章提出将运用d s p r i n t 算法得到 的非单调性决策树进行修正，使无需随时增加各个分站点数据集数目，仅插入少 量数据项，通过分裂一些叶节点，增加少量分枝将决策树单调化。 第五章针对常规分布式数据挖掘系统存在的数据分块、结果集成，安全性等 问题，提出将移动代理技术和数据挖掘技术相结合，利用m o b i l ea g e n t 的可移 动性、分布并行性、异步性、资源优化等特点，搭建适合大容量、分布式数据分 析应用的数据挖掘系统平台，运用移动代理技术完成分布式数据挖掘中适配器、 数据挖掘代理、数据库和用户间通信、程序调用和代码迁移。 最后一章回顾了本文的主要工作，阐述了本文的刨新之处，指出了进一步研 究的方向。 硕士学位论文第二章分类知识的挖掘和评价 第二章分类知识的挖掘和评价 数据库内容丰富，蕴藏大量信息，可以用来作出智能的商务决策。分类知识 的挖掘是一种重要的数据分析形式，用于提取描述重要数据类的模型或预测未来 的数据趋势。 数据挖掘中的分类方法是将数据集按某个指定的属性划分，并给出分类规 则。由于训练集的类别是确定的，且类别未知的数据集是基于训练集进行分类的， 分类在机器学习中被称之为有监督学习。 2 1 分类知识的挖掘算法研究 分类技术在数据挖掘中是一项非常重要而且应用面极为广泛的技术。比如工 程问题诊断