（计算机系统结构专业论文）基于globus的决策树分类系统研究与实现.pdf

重庆大学硕士学位论文中文摘要 摘要 随着信息化程度的提高，在人类社会的各个领域聚集了大量甚至是海量的数 据，数据挖掘就是要从这些数据中提取有用的信息，从上世纪8 0 年代末以来人们 对数据挖掘模型、算法、系统进行了大量的研究，并取得了一定的成果，为了提 高算法的效率，并行和分布式数据挖掘一直是研究的重点，但面临很多挑战，比 如：数据的海量、异构、分布、计算密集；知识表达形式不够丰富；挖掘工具和 环境缺乏等，网格技术的出现在一定程度上为解决这些问题提供了帮助。 c a n n a t a r om a r i o 提出下一代网格的研究应主要致力于为用户提供知识服务。 近年来，关于在网格上提供知识服务渐渐成为了研究的热点，并取得了很多重要成 果，这些项目着重于在网格上实现知识发现服务的整体架构，而对利用网格服务 来实现并行分布式数据挖掘算法很少提及，要在网格上进行知识发现，就不得不 涉及到数据挖掘的算法，目前对可并行性算法利用网格服务来实现研究比较少。 针对这种情况，论文采用网格系统中间件实现工具包g l o b u st o o l k i tv e r s i o n4 按 照网格服务的方式实现并行决策树分类算法s p r i n t 。采用该方式有以下优点： ( 1 ) 扩展性好，因为采用网格服务的方式实现，只须将算法相关的网格服务部署在 参与计算的网格节点，增加参与计算的新节点较容易；( 2 ) 可复用，使用标准的网 格服务，能很好的被其他网格应用集成；( 3 ) 充分利用网格资源，s p r i n t 算法固 有的可并行性，在网格上实现该算法可以充分利用虚拟组织内的网格节点的计算 能力，提高基于网格的知识发现服务速率。 论文首先对数据挖掘相关概念及决策树分类算法进行介绍，详细分析了论文 将要以网格服务的方式实现的并行决策树分类算法s p r i n t 。 随后，论文对网格及网格计算相关内容进行简要介绍，对目前主流的几种网 格体系结构进行了详细分析，并对其中的五层沙漏结构和开放网格服务架构的优 缺点进行了比较，并简要介绍分析了基于o g s a 按照w s r f 规范实现的网格中间 件工具包g t 4 的各个功能部件。 最后，采用g t 4 ，按照网格服务的方式设计实现并行分布式决策树分类算法 s p r i n t ，安装网格中间件g t 4 ，组建了一个虚拟局域网格环境，通过数据集实 例论证了论文提出的实现方式的有效性和可行性。 关键词：数据挖掘，决策树，s p r i n t ，g l o b u s ，网格服务 重庆大学硕士学位论文 英文摘要 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n f o r m a t i o n a lp o p u l a r i z a t i o n , t h e r el t t l eal o to fd a t a a s s e m b l e di nv a r i o u sf i e l d so fo u rs o c i e t y d a t a - m i n i n gi st h em e t h o do fp i c k i n gu p e f f i c i e n ti n f o r m a t i o nf i o mt h e s ed a t a $ i n e o8 0 so f l a s tc e n t u r y , p e o p l eh a v ec a r r i e do u t p l e n t yo fr e s e a r c h e sa b o u td a t a - m i n i n gm o d e l s ，a l g o r i t h m s ，a n dd a t a - m i n i n gs y s t e m s a n dt os o m ee x t e n t , t h e yh a v eg o ts o m ea c h i e v e m e n t h o w c v e i , i no r d e rt oi m p r o v e t h ee t f i c i e n e yo fa l g o r i t h m , p a r a l l e la n dd i s t r i b u t i o n a ld a t a - m i n i n g , w h i c ha r ea l w a y s r e g a r d e da st h er e s e a r c hi m p o r t a n c e , 躺c o n f r o n t e dw i t hm a n yc h a l l e n g e s , s u c ha s d a t a sa b u n d a n c e , t h e i rs t r u c t u r a ld i ：f f e r c n c e ，t h e i rd i s t r i b u f i o n , t h e i re a l e u l a t i v o d e n s e n e s s ，s i m p l ek n o w l e d g ef o r m u l a , a n dl a c k i n go fm i n i n gi n s l a t t m e n t s a n d e n v i r o n m e n t t os 0 1 1 1 ee x t e n t , t h ee m e r g e n c eo f 鲥dt e c h n i q u eo f f e r sg r e a th e l pt o s o l v et h e s ep r o b l e m s a c c o r d i n gt oc a n n a t a r om a r i o ，t h er c s c a r e l ao ft h en e x tg e n e r a t i o no f 鲥ds h o u l d b ed e v o t e dt oc o l l s i m l e r si nk n o w l e d g es e l v i c l 嚣i nr e c e n ty e a r s i tg r a d u a n yb e c o 邮 h o t , a n dp e o p l eh a v ea l r e a d yg o tm a n ya c h i e v e m e n t s t h e s ep r o j e c t sh a v ee m p h a s i z e d r e a l i z i n gt h ew h o l es t r u c t u r eo fk n o w l e d g ed i s c o v e r i n gs e r v i c e s ，b u th a r d l yh a v e m e n t i o n e du s i n gg r i c tt or e a l i z et h ec a l e t d a t i o no f p a r a l l e ld i s t r i b u t i o n a ld a t a - m i n i n g i n o r d e rt o g e tk n o w l e d g eo n 鲥d a l g o r i t h m sh a v et ob ei n v o l v e d n e v e r t h e l e s s ， n o w a d a y sr e s e a r c h e so nt h eu s eo fg r i ds e r v i c e st or e a l i z ep a r a l l e lc a l c u l a t i o n1 1 1 eq u i t e f e w a i m e da tt h i sp h e n o m o n , u s i n gg l o b u st o o l k i tv e r s i o n4t or e a l i z es p r i n ti n t h ef o r mo fg r i ds e r v i c e sh a sb e e np r o p o s e d t h i sk i n do fs o l u t i o nh a ss e v e r a l a d v a n t a g e s ：( 1 ) i ti sm o r ee x t e n s i b l e ，b e c a u s ei to n l yr e q u i r e sd i s p o s i n ge a l e u l a t i v e r e l a t i v e 面df l e i v i c , l 器o nt h en o d e sw l a i e ht a k ep a r ti nt h ec a l c u l a t i o n i ti sm u c he a s i e r t oa d ds i m i l a rn 钾n o d e s ；( 2 ) i tc a nb er e u s e d ，b e c a u s es t a n d a r d 鲥ds c r v i c l 皓锄b e w e l l - u s e db yo t h e r 鲥d ；( 3 ) i ti sa b l et ot a k ef u l la d v a n t a g eo fi n t e m e tg e s o u r c , 髑, ， b e c a u s es p r i n ta l g o r i t h mi si n n a t e l yp a r a l l e l r e a l i z i n gt h i sa l g o r i t h mo ng r i dc m s u t t i e i e n t l ym a k eu s eo ft h ec a l c u l a t i n ga b i l i t yo fn o d e si n s i d et h ev i r t u a lf r a m e w o r k , a n dt h e np r o m o t et h es p e e do f k n o w l e d g ed i s c o v e r i n gs e r v i c e sb a s e d0 1 1g r i d f i r s t , c o n c e p t sa b o u td a t a - m i n i n ga n ds p r i n ta l g o r i t h mh a v e b e e ni n t r o d u c e d , a n dt h em e t h o do f r e a l i z i n gs p r i n ti nt h ef o r mo f 班ds e r v i c e sh a sb e e na n a l y z e di n d e t a i l t h e n , r e l a t i v eo o n c 印t so f 鲥da n d 酣dc o m p u t i n ga 托s i m p l yi n t r o d u c e d a l s o ， 重庆大学硕士学位论文英文摘要 s e v e r a lp o p u l a ra n ds y s t e m sh a v eb e e np a r t i c u l a r l ya n a l y z e d , t h ea d v a n t a g e sa n d d i s a d v a n t a g e so ff i v e - l a y e rs a n d # a s s s t r u c t u r ew i t ht h a to fo p o l lg 五ds 盯v i a r c h i t e c t u r eh a v eb e e nc o n t r a s t e d ，a n dt h e ne a c hf u n c t i o n a lc o m p o n e n t so f g t 4w h i c h i sr e a l i z e do nt h es t a n d a r do fw s r fa n di sb a s e do no g s ah a v eb e e nb r i e f l y i n t r o d u c e d a tl a s t ，t h em e t h o do f u s i n gg t 4t or e a l i z es p r i n t a l g o r i t h mi nt h ef o r mo f g r i d s f f l n i 嘲h a sb e e no f f e r e d b yi n s t a l l i n gg t 4 ，al o c a lv i r t u a lo r g a n i z a t i o ng a d e n v i r o n m e n th a sb e e nf o r m e d f u r t h e r m o r e ，v i ad a t aa n de x a m p l e s ，t h ev a l i d i t ya n d f e a s i b i l i t yo f t h i sm e t h o dh a v e b e e nd e m o n s t r a t e d k e y w o r d s ：d a t am i n i n g , d e c i s i o nt r e e , s p r i n t , g l o b u s ，g r i ds e r v i c e i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：方蒙乞 签字日期： 劫刁年6 月牛e t 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：方丧皇 签字日期：沙0 7 年b 月1 4 e t 翮签名膨峒 签字日期：矽刁年i f 月垆日 重庆大学硕士学位论文 1 绪论 l绪论 1 1 论文的研究背景 时光飞逝，社会在一天天的进步，各行各业都在不断向前发展。自1 9 4 6 年第 一台计算机发明以来，人类在信息世界前进的脚步一刻都未停止过，i n t e l 创始人 摩尔曾经提出过著名的摩尔定律：每1 8 个月芯片的速度提高一倍，价格下降一 半”。随着社会信息化程度的提高，人们面临的信息越来越多，在很多领域聚集 了大量甚至是海量的数据和信息；此外，自上世纪9 0 年代以来，随着i n t e r n e t 的 出现和发展，人们可以跨时空地进行数据共享和协同工作，互联网络上的数据成 指数式的增长。这些领域数据和i n t e r n e t 数据的爆炸式增长，出现了“数据爆炸、 知识贫乏现象，奈斯伯特o o h nn a i s b e t t ) 发出了 w ea r ed r o w n i n gi ni n f o r m a t i o n ，b u t s t a r v i n gf o rk n o w l e d g e ( 人类正被数据淹没，却饥渴于知识) 这样的惊呼。大量信息 在带来方便的同时也带来了很多问题：第一是信息过量，难以消化；第二是信息 真假难以辨识；第三是信息安全难以保证；第四是信息形式不一致，难以统一处 理。如何才能不被信息淹没，提高信息利用率? ”，数据挖掘技术d m ( d b t am i n i l l g ) 和知识发现k d d ( k n o w l e d g ed i s c o v e r y f i o md a t a b a s e s ) 应运而生。 从上世纪8 0 年代末以来，人们对数据挖掘模型、算法、系统进行了大量研究， 并在实际中取得了很好的成果。为了提高算法效率，并行与分布式挖掘一直是研 究的重点。 但数据挖掘还是面临很大的挑战，主要体现在以下一些方面： i 、数据是海量的 数据挖掘处理的数据规模从g b 级上升到t b 级，甚至上升到p b 级，数据规 模已远远超过传统统计分析的数据量。 2 、数据是分布的 由于数据规模太大，数据不可能在一个节点存储，而是物理分布在不同的节 点上。特别是像在天文、金融等一些领域，数据天然就是物理分布的，一个节点 是无法完整存储这些数据的。 3 、计算密集型 很多数据挖掘算法是计算密集型的，需要强大的计算能力支持。一些挖掘算 法的时间复杂度是多项式时间的，而另一些却是n p 的，如关联规则挖掘问题就是 一个n p 问题，这类问题需要极强的计算能力支持。 4 、异构数据源 数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如 重庆大学硕士学位论文 1 绪论 文本、图形、图像数据、多媒体数据库、h t m l 数据、x m l 数据等。 5 、知识表达形式不丰富 数据中含有非常丰富的知识，但受限于现有的知识表达模式，很多知识无法 从数据中得到提取。 6 、数据挖掘工具与环境缺乏 目前，虽然已有很多数据挖掘工具，但这些工具基本上无法支持数据分布、 数据异构的数据挖掘应用。 因此，如何解决数据挖掘所面临的这些问题，特别是分布式异构海量数据的 挖掘，传统的基于分布式系统、集群系统的数据挖掘方法系统都无能为力，而正 在蓬勃发展的、被誉为第三代i n t e r n e t 基础的网格技术正好满足这种需要。 网格概念源于电力网格。网格【l 】被定义为在动态变化的、拥有多个部门、或团 体的复杂虚拟组织内，能提供灵活的、安全的协同资源共享或问题求解的计算环 境。人们普遍认为，基于t c p i p 的传统互联网络解决了设备的互连，w w w 解决 的i n t e m e t 上网页的互连，网格将解决i n t c m e t 上计算资源、存储资源、通信资源、 软件资源、信息资源、知识资源的互连。网格被誉为第三代i n t e r a c t 的基本架构， 网格突破了计算能力的限制、存储能力的限制、资源分布的限制、资源共享方式 的限制，其适用于计算密集型、数据密集型应用。各国都已投入巨资对网格进行 研究。如美国的n a s ai p g ( i n f o r m a t i o np o w e ro r i d ) 网格、t c r a g r i d 、国家技术网格 ( n t g ) 、全球信息网格g i g ( g l o b a li n f o r m a t i o nc m d ) ，欧洲的数据网格d a t ag r i d ， 英国国家网格u k n g ( u k n a t i o n a l g r i d ) 。日本的n i n f , 中国的c h i n a g r i d 、v e g a g r i d 等，发达国家的各类网格计划已达1 8 0 项之多。 网格计算技术是解决复杂海量、分布数据的访问、存储、组织和管理的一种 有效技术。未来的科学计算、商务活动、信息服务等都将以数据为中心，数据已 成为科学、经济、社会等领域的重要资源。在网格计算环境下，许多科学与工程 计算问题，如航天活动、生物计算、数字地球等，以及大型跨国企业、远程医疗合 作、商务活动、政务管理等将产生大量海量数据。要分析和挖掘这些广域分布的 海量数据，以获取新的知识、规律和决策支持信息，传统的数据挖掘模式和技术是 无法胜任的。建立在网格基础上的数据挖掘结合网格计算的思想及其技术的优点， 能够对物理上广域分布的海量数据进行高效的处理、分析和挖掘，将会给科学研 究领域、经济领域和社会生活带来新的发现和巨大价值。 1 2 国内外研究现状 1 9 9 2 年，l a r r ys m a r r 在c a s a f 2 1 计划中首次提出网格计算的概念，它为人们 产生更大的计算能力提供了另外一种思路，但更为重要的是，它提出了一个计算 2 重庆大学硕士学位论文1 绪论 机网络应该实现的美好目标：使人们象使用电一样方便地使用任何可以通过网络 连接到的资源，包括计算资源、数据资源、软件资源、各种数字设备、高端仪器 等。 目前，各个国家都在进行网格计算的研究。美国政府在网格研究方面投入了 巨大的人力和物力，正规划建立一个全球大网格( g l o b a lg r e a tg r i d ) 3 1 ，预计2 0 2 0 年完成。英国政府投入大约1 亿英镑规划建立英国国家网格 3 1 。各r r 厂商也积 极投入网格计算的研究开发。s u n 公司发起了g r i de n g i n e 4 j ：贞目，并贡献了 5 0 0 。0 0 0 行代码。m m 公司正在研制能被多家科研单位和众多科学家同时使用的超 级计算网格t e r a g r i d t 5 1 ，其设计运算速度为每秒1 3 6 万亿次，比著名的超级计算 机深蓝侠1 0 0 0 倍。除此以外，网格技术在企业的应用日益增多。1 6 】制药企业辉 瑞( p 也曲、波音公司、福特公司等大型企业都开始进行网格的试验，尝试用网格 进行复杂的仿真和设计。爱立信、日立、宝马公司等已经开始构造内部网格。在 我国，从1 9 9 9 年底到2 0 0 1 年初，中科院计算所联合国内十几家科研单位共同承 担了国家8 6 3 重点项目一国家高性能计算环境 ( n a t i o n a lh i r 曲p e r f o r m a n c e c o m p u t i n ge n v i r o n m e n t 简称n h p c e ) t 。7 】的研发任务。该项目的目标是建立一个计 算资源广域分布、支持异构特性的计算网格示范系统，它把我国的8 个高性能计 算中心通过i n t e m e t 连接起来，进行统一的资源管理、信息管理和用户管理，并 在此基础上开发了多个需要高性能计算能力的网格应用系统，取得了一系列研究 成果。目前，中科院计算所正在进行织女星网格系统哺】的研究，已在局域网环境建 立了原型系统，进行了试验。 数据挖掘与网格的结合研究正成为数据挖掘研究的一个热点。目前的研究主 要体现在以下几个方面： l 、网格环境下的数据管理、数据集成、数据服务研究；提出了数据网格、信 息网格等框架； 2 、网格环境下的知识发现框架，提出了基于数据网格、信息网格，利用数据 挖掘思想来构建知识网格k - g r i d ( k n o w l e d g eg r i d ) 9 的思想、方法和框架； 3 、网格环境下，基于本体论( o n t o l o g y ) 的数据挖掘、知识发现的体系、方法。 m a r i oc a n n m m _ o 等提出了网格环境下的基于本体论( 1 0 】的数据挖掘方法 d a m o n 1 1 】【1 2 1 ，在d a m o n 中采用d a m l + o i l 来描述网格环境下的数据挖掘任 务，并给出了分类决策树描述实例； 4 、网格环境下，数据挖掘算法的调度策略。s o r l a n d o 等人对网格环境下的数 据挖掘任务调度1 1 3 】进行了研究； 5 、网格环境下，分类、聚类、规则等挖掘算法的研究。w e id u 等【1 4 】利用 d a t a c u t t e r 进行了网格环境下基于k - 均值的聚类研究；g a g a na g r a w a l 等进行了网 3 重庆大学硕士学位论文1 绪论 格环境下的关联规则、分类、聚类算法等的研究；美国芝加哥大学的s v e t l o z 棚r n e s t o r o v 等进行了网格环境下基于数据仓库的关联规则挖掘；s h u - t z ut s a i t l 5 等 对网格环境下的分类决策树构件进行了研究； 6 、网格环境下的数据挖掘应用。m o 璐t a f ag 1 m o m 等人对生物信息的网格数 据挖掘【1 6 】进行了研究；美国明尼苏达州大学的v i p mk u m a r 等人开展了基于网格 数据挖掘的入侵检测研究、基于网格的气候数据挖掘研究；e - s c i e n c e 的i n m a 项 目对分布于英国e p c c 和澳大利亚c t m m 大学的财务数据进行了网格数据挖掘研 究参加的学校有英国的u e m s ( u n i v e f s i t yo fe d i n b u r g hs c h 0 0 1 ) 大学、 l u m n ( l a n c a s t e ru n i v e r s i t ym a n a g e m e n ts c h 0 0 1 ) 大学，以及位于澳大利亚的c r e t i n 大学； 7 、网格环境下的数据挖掘系统实现。在n a s a 的i p g ( i n f o r m a t i o np o w e rg r i d ) 数据挖掘网格旧中，开展了一个名为a d a m 的数据挖掘系统研究；p a u ld o n a c h y 等 在e - s c i e n c e 网格项目中开展了g e d d m ( c r d d - b a s e de s c i e n c ed i s t r i b u t e dd a t a m i n i n g ) ”1 数据挖掘系统研究；t m s l o a n 等在e - s c i e n c e 数据网格的f i r s t d i 菩墙1 项 目中进行了网格数据挖掘研究。 1 - 3 主要研究内容 论文的主要目标是利用网格计算技术构建一个并行分布式数据挖掘决策树分 类算法网格服务系统，实验论证该网格服务的技术可实现性。考虑到时间和客观 条件等各方面因素，拟定了论文的研究内容如下： l 、数据分类是数据挖掘中的一种分析方法。数据分类的方法很多，其中决策 树分类以其特有的优点得到了最为广泛的应用f 2 0 】：决策树分类的速度快：决策树 模型简单，便于理解，能方便地转换为s q l 语句来实现；相对于其它方法而言， 决策树分类可以得到较高的精确度。传统的分类方法在处理海量数据时会出现性 能下降或精度降低的问题。m m 研究人员提出了决策树分类算法s p r i n t ( s c a l a b l e p a r a l l e l i z a b l ci n d u c t i o no f d e c i s i o nt r e e s ) t 2 1 1 ，该算法的优点是：训练样本量不受内 存限制；具有优秀的伸缩性、加速性、扩容性；并行实现容易、效率高。论文首 先对s p r i n t 算法的流程进行详细的分析。 2 、正如计算机体系结构是一个软件系统的基础一样，网格计算体系结构是一 个网格应用系统的基础。网格计算的体系结构在以g l o b u s 研究小组为首的网格研 究人员的努力下不断发展。不同的网格计算体系结构适合于不同类型的应用，因此， 需要对各种主流的网格计算体系结构进行比较分析，挑选出较适合于并行分布式 数据挖掘这样类型的应用的网格计算体系结构。 3 、在选定一个合适的网格计算体系结构后，基于对应的网格中问件设计并行 4 重庆大学硕士学位论文1 绪论 分布式数据挖掘决策树分类算法s p r i n t 网格服务系统。 ( 1 ) 按照高灵活性、高扩展性、高适用性原则详细设计系统总体结构、工作流 程，定义各个组成部分之间的数据交换机制和通信机制。 ( 2 ) 详细设计各个组成部分的结构，必需的功能接口和服务接口，描述各个组 成部分的工作流程。 4 、通过安装网格中间件g l o b u st o o l k i tv e r s i o n4 构建一个虚拟网格环境，从 而搭建一个实验环境，用以测试和验证所设计s p r i n t 算法网格服务系统以及各 个部件的可实现性和有效性。 5 、使用e c l i p i 开发工具和网格中间件g l o b u st o o l k i tv e r s i o n4 对并行分布 式数据挖掘决策树分类算法s p r i n t 网格服务的各个组成部件进行原型实现，即 实现所定义的各个组成部分的必需的功能接口和服务接口，实现各个组成部分之 间的通信机制和数据交换机制。最后通过数据集生成决策树来测试和验证设计的 可行性和有效性。 1 4 本章小结 本章首先分析了论文研究的背景，阐述了数据挖掘的发展过程，通过近二十 年发展，数据挖掘面临很多挑战，从而需要引入新的技术来解决数据挖掘应用中 碰到的问题。自1 9 9 2 年网格计算首次提出以来，网格计算得到了长足的发展，网 格计算正从高端科学或工程应用进入到工业、商业和日常生活应用中。说明了将 网格计算引入到数据挖掘中的意义，将提高人们分析、处理数据的能力，从而对 其它科学研究领域的发展给予一些帮助。通过对大量文献的阅读、分析、整理， 描述了国内外网格计算应用的研究现状，特别是网格计算在数据挖掘方面的研究 现状，最后给出了本文的主要研究工作、研究目标以及期望达到的最终成果。 5 重庆大学硕士学位论文2 决策树分类算法s p r i n t 分析 2 决策树分类算法s p r i n t 分析 2 1 数据挖掘及决策树分类算法介绍 2 1 1 数据挖掘 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的知识的过程。 它是一个融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。 数据挖掘被认为是知识发现( k n o w l e d g ed i s c o v e r yf r o md a t a b a s e ) 过程中的个特 定步骤，而知识发现是从数据中发现有用知识的整个过程，数据挖掘是k d d 的核 心。 数据挖掘技术能从数据仓库中自动分析数据，进行归纳性推理，从中发掘出 潜在的模式，或产生联想，建立新的业务模型，这是一个高级的处理过程。高级 的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成 一种螺旋式上升过程。 数据挖掘算法的好坏将直接影响到所发现知识的好坏。数据挖掘的任务是从 数据中发现模式。模式是一个用语言l 来表示的一个表达式e ，它可用来描述数 据集f 中数据的特性，e 所描述的数据是集合f 的一个子集f e 。e 作为一个模式 要求它比列举数据子集f e 中所有元素的描述方法简单。模式有多种分类，按功能 划分其任务一般可分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的 一般特性，预测性挖掘任务在当前的数据上进行推断，以进行预测。在实际应用 中，往往根据模式的实际应用细分为以下几种：分类模式、回归模式、时间序列 模式、聚类模式、关联模式、序列模式。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用 最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识，因 为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模式的 产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据作为 样本，用另一部分数据来校验、验证模式。聚类模式、关联模式、序列模式则是 非监督知识，因为在模式建立前其结果是未知的，模式的产生不受任何监督。 2 1 2 决策树分类算法 2 12 1 分类算法概述 数据分类( c l a s s i f i c a t i o n ) 是数据挖掘的一个重要内容，在统计学、机器学习、 神经网络和专家系统中得到了较早的研究，数据分类实际上就是从数据库对象中 发现共性，并将数据对象分成不同几类的一个过程，分两步： 6 重庆大学硕士学位论文 2 决策树分类算法s p r i n t 分析 第一步，建立一个模型，描述预定的数据类集或概念集。通过分析由属性描 述的数据库元组来构造模型。输入数据，或称训练集( t r a i n i n gs e t ) ，是一条条的数 据库记录( r e c o r d ) 组成的。每一条记录包含若干条属性( a t t r i b u t e ) ，组成一个特征向 量。训练集的每条记录还有一个特定的类标签( c l a s sl a b e l ) 与之对应。该类标签是 系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：( v i ， v 2 ，v n ；c ) 。在这里v i 表示字段值，c 表示类别。这一步的目标是对训练数据进 行分析，使用数据的某些特征属性，给出每个类的准确描述。 第二步，使用建好的模型进行分类。首先评估模型，预测准确率，如果认为 模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。 分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为 每一个类找到一种准确的描述或者模型，这种描述常常用谓词表示。由此生成的 类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未 知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定。我 们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个 类的知识。 2 1 2 2 决策树分类算法 决策树( d e c i s i o nt r e e ) 2 0 】是运用于分类的一种树结构。其中的每个内部节点 ( 砷黜ln o d e ) 代表对某个属性的一次测试，一条边代表一个测试结果，叶子( 1 e a 0 代表某个类( c l a s s ) 或者类的分布( c l a s sd i s t r i b u t i o n ) 。最上面的节点是根结点。图2 1 给出了一个商业上使用的决策树的例子。它表示了一个关心电子厂品的用户是否 会购买p c 的知识，用它可以预测某条记录( 某个人) 的购买意向。 图2 1 一棵决策树例子 f i g 2 1a d e c i s i o nt r e ed c m o 这棵决策树对“买计算机”的销售记录进行分类。指出一个电子产品消费者是否 会购买一台计算机。每个内部节点( 方形框) 代表对某个属性的一次检测。每片叶子 ( 椭圆框) 代表一个类( b u y s _ c o m p u t e r i z e s 或者b u y s _ c o m p u 蜘o ) 。这个例子中， 7 重庆大学硕士学位论文2 决策树分类算法s p r i n t 分析 样本向量如下：( a g e , s t u d e n t , c r e d i tr a t i n g ；b u y s _ c o m p u t e r s ) ，被预测数据的格式为 ( a g e ，s t u d e n t , c r e d i l r a t i n g ) 。输入新的被预测的纪录，可以预测该记录隶属于哪个 类。 用决策树进行分类分两步走。第一步是利用训练集建立并精化一棵决策树，建 立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。 第二步是利用生成完毕的决策树对输入数据进行分类。对输入的纪录，从根节点 依次测试记录的属性值，直到到达某个叶子节点，从而找到该记录所在的类。 问题的关键是建立一棵决策树。这个过程通常分为两个阶段：建树( t r e e b u i l d i n g ) 和剪枝( t r e ep r u n i n g ) 。建树是一个递归的过程，最终将得到一棵树。剪枝 是目的是降低由于训练集存在噪声而产生的起伏。 2 2s p i u n t 算法分析 决策树分类算法在早期比较著名的有c 4 5 1 2 2 、c a r 一2 3 1 等，为了解决训练样 本集增大从而不能全部放入主存时分类算法效率的问题，m m 研究人员在1 9 9 6 年 提出了s l i q ( s u p e r v i s e dl e a r n i n gi nq u e s t ) 肼】算法，由于使用了新的数据结构， s l i q 可以并行化，但s l i q 算法的类表需要常驻内存，而类表会随着训练样本集 的增大而增大，因此s l i q 算法仍然不能摆脱主存容量的限制。为此，m m 研究人 员又提出了可伸缩并行的决策树算法( s c a l a b l ep a a a a a a a a a l 垦a u e l i z a b l ei n d u c t i o no fd e c i s i o n t r e e s ) 阱】。s p r i n t 对s l i q 的数据结构进行改进，下面将对该算法做详细分析： 构造决策树的基本策略是采用贪心方法，以自项向下递归、各个击破的方式 生成树。生成一棵决策树一般包含建树阶段和剪枝阶段。s p r i n t 采用 m d l ( m i n i m u md e s c r i p t i o nl e n g t h ；最4 , 描述长度原则) 【2 5 1 剪枝。 创建树算法如下： 输入：训练样本集s 输出：一棵决策树 i f ( s 满足某个中止条件) t h e nr e t u r n ； f o r ( i = l ；f s 中属性的个数；升+ ) ( 计算并评估每个候选属性的各个候选分割点( 分割子集) 的分割指数；) 找出最佳分割点( 分割子集) 并据此将s 划分为研和& ； m a k ed e c i s i o nt r e e ( s 1 ) ； m a k ed e c i s i o nt r e e ( $ 2 ) ) 算法中，集合文研、岛分别代表树中的节点，其中函、& 是s 的两个分枝节 点。最后形成的决策树是一棵二叉树。算法的终止条件一般有三种情况：( 1 泌中 的所有训练样本都属于同一个类，则将此节点作为一个叶子节点，并以该类标记 重庆大学硕士学位论文2 决策树分类算法s p r i n t 分析 该节点；( 2 ) 没有属性可以用做测试属性；( 3 ) 训练样本的数量太少( 少于用户提供的 某个阈值) 。后两种情况通常以训练样本中占优势的类标记该叶子节点。 s p r i n t 算法采用g i n ii n d e x 作为节点的分割指标，有关g i n ii n d e x 的计算方法 如下： 假设一个训练集s 有r 条记录，它们分别属于m 个不同的类，则集合s 的分 割指数g i n i 定义如下： g i n i 固2 1 。拜 ( 2 1 ) 其中既是类i 在s 中出现的相对频率。如果集合j 按照某个划分点被划分成曲 和& ，则划分后的g i n i 按下式计算： g i n i 印i i t = 譬g i n i ( s j ) + 譬+ g i n i ( 黝 ( 2 2 ) 其中一、n l 、n 2 分别为文研、岛的记录数。g m i 枇( s ) 越小，表明分割规则越 好。使得g i n i 础 最小的划分是最好的划分。 对于不同类型的属性，s p r i n t 采用了不同的处理方法计算g i n ii n d e x ： ( 1 ) 离散属性。设某属性有m 个互不相同的取值，分割的实质是将m 个值分成 两个集合，共有2 ”种可能划分方法。在m 较小时，采用穷举方法，计算每一种分 割的g i n i 值；当膨较大时，采用贪心方法寻找最小g i n i 值，即先将一个集合c 置 为空集，另一个集合d 包含所有的值，然后反复地从d 中选取一个值，移至c 中， 直到没有合适的值可移为止。选择移动的值应满足条件：移动后导致g i n i 值减少 并且与移动其它值相比其g i n i 值是最小的。 ( 2 ) 数值型属性( 亦称为连续属性) 。某属性的候选分割点为按该属性值排序后相 邻属性值的中点。设属性彳的某个中点值为v ，可以先将训练集分成a v 两 个部分，然后计算各个候选分割点的g i n i 值。若某属性有k 个互不相同的取值， 则有k - 1 个候选分割点。 为了加快速度，避免在每一个树节点的处理上都进行排序，s p r i n t 采用了 预先排序技术。当确定了分割属性和分割规则后，读取分割属性的列表，并将其 划分为两个子集。 s p r i n t 算法采用m d l ( m i n i m u md e s c r i p t i o nl e n g t h ；最小描述长度1 原则剪枝： m d l ( m i n i m u md e s c r i p t i o nl e n g t h ) 的目标是生成一棵描述长度最小的决策树。 m d l 原理认为：最好的编码模型是描述数据代价最小的模型。如果模型m 对数据 集d 进行编码，那么描述代价： c o s t ( m ，d ) = c o s t ( di 蛐+ c o s t ( m ) ( 2 3 ) 其中，c o s t ( mid ) 表示用模型m 对数据d 编码的编码代价，单位b i t s ，c o s t ( m ) 表示描述模型本身所需的编码长度。 9 重庆大学硕士学位论文2 决策树分类算法s p r i n t 分析 2 2 1s p r i n t 算法数据结构 2 2 1 1 属性表( a t t r i b u t el i s t ) 如图2 2 所示，s p r i n t 算法使用属性列表数据