（计算机软件与理论专业论文）基于决策树的分布式分类算法研究.pdf

郑州大学硕士学位论文 摘要 我们现在生活在一个网络化的新时代，通信、计算机和网络技术正改变着整 个人类和社会。目前大多数分类算法适用于集中式环境，当伴随着大量的数据集、 用户和系统上的地理分布时，把地理上分布的数据集集中到集中式的站点上会引 起巨大的网络传输代价。因此，如何充分利用地理上分布的数据资源，结合各种 不同的分类技术来完成高性能的分布式分类任务，就成为必然的事情。 虽然分布式分类算法是近几年才提出的新的研究领域，但由于其诱人的应用 前景，目前已有相当数量的研究人员投入到对该领域的研究当中，并取得了一定 的成果。j e r z y 等人提出了知识发现中分布式挖掘技术方面的研究，提出了他们 对基于决策树的分布式分类算法的研究成果。利用a g e n t s 和m e d i a t o r 之间的同 步协作机制来完成，m e d i a t o r 负责各个a g e n t 之间的通信。各个a g e n t 通过 m e d i a t o r 进行协商、合作和行为规范，来完成基于分布式条件下的分类任务。 对决策树算法的评价有两个标准：第一，生成的决策树是否比较简化；第二， 分类的精度是否达到一定标准。在基于决策树的分布式分类算法中，关键的问题 就是对决策树的局部结果集成的方法。其目的是在确保精确度的同时，提高可理 解性。我们研究发现对决策树的局部结果集成的方法大致有两种：一种是在产生 局部决策树后，先得到局部规则，然后进行局部规则结果的修剪措施，得到全局 结果。另一种就是产生局部决策树后，先进行局部决策树的集成，然后进行剪枝 措施，得到全局决策树，从而得到全局结果。 实验证明，基于决策树的分布式分类算法是有效的，一定程度上解决了对决 策树局部结果的集成这个问题。 关键字 分布式分类，决策树，a g e n t ，集成 郑州大学硕上学位论文 a b s t r a c t w ea r en o w l i v i n gi nag r e a tn e w e r ao f n e t w o r k c o m m u n i c a t i o n s 、c o m p u t e ra n d n e t w o r ka r ec h a n g i n go u rh u m a nb e i n g sa n ds o c i e t y n o w a d a y s ，m o s tc l a s s i f i c a t i o n a l g o r i t h m sc a t e rt oac e n t r a l i z e de n v i r o n m e n t a sm o s td a t as e t s 、u s e r sa n dm o d e m o r g a n i z a t i o n sa r eg e o g r a p h i c a l l yd i s t r i b u t e d ，a n dm e r g i n gd a t as e t sf r o md i f f e r e n t s i t e si n t oac e n t r a l i z e ds i t ew i l li n c u rh u g en e t w o r kc o m m u n i c a t i o nc o s t s t h e r e f o r ei t i sn e c e s s a r yt om a k eg o o du s eo fg e o g r a p h i c a l l yd i s t r i b u t e dd a t as e t sa n dc o m b i n e d i f f e r e n tc l a s s i f i c a t i o nt e c h n o l o g i e sf o ri m p l e m e n t i n gh i g h - p e r f o r m a n c ed i s t r i b u t e d k n o w l e d g ed i s c o v e r ys y s t e m s a l t h o u g hd i s t r i b u t e dc l a s s i f i c a t i o na l g o r i t h m si san e wr e s e a r c hd o m a i n ，al o to f p e o p l ef o c u st h e i rm i n do nt h er e s e a r c ha n dg e tal o to fa c a d e m i cs u c c e s s j e r z ye ta l g i v et h e i rr e s e a r c ho nd i s t r i b u t e dc l a s s i f i c a t i o na l g o r i t h ma n dg e tal o to fg o o dr e s u l t s a g e n t s ，i nac o l l a b o r a t i v ef a s h i o n ，g e n e r a t ep a r t i a lt r e e sa n dc o m m u n i c a t et h e t e m p o r a r yr e s u l t st ot h em e d i a t o r d i s t r i b u t e dc l a s s i f i c a t i o ni sa c c o m p l i s h e dv i aa s y n c h r o n i z e dc o l l a b o r a t i o no f a g e n t sa sw e l la sam e d i a t o rc o m p o n e n t t h em e d i a t o r c o m p o n e n tf a c i l i t a t e dt h ec o m m u n i c a t i o na m o n ga g e n t s t h ep r o c e s si st e r m i n a t e d w h e naf i n a lt r e ei si n d u c e d t h e r ea r et w op e r f o r m a n c ee v a l u a t i o n st oad e c i s i o nt r e e ：c o n c i s i o na n d p r e c i s i o n i nt h ed i s t r i b u t e dc l a s s i f i c a t i o n a l g o r i t h mb a s e do nd e c i s i o nt r e e ，t h ei m p o r t a n t p r o b l e mi st h et a s ko fa c q u i r i n ga ni n t e g r a t e dd e c i s i o nm o d e lf r o md i s t r i b u t e dd a t a s e t s t h e r ea r et w om a i ns t r a t e g i e si nt h ei n t e g r a t i o no fl o c a ld e c i s i o nt r e e o n ei s i n t e g r a t i n gt h el o c a lr u l e st oe s t a b l i s hf i n a lr e s u l t sa f t e rt h el o c a ld e c i s i o nt r e ei sm a d e t h eo t h e ri si n t e g r a t i n gt h el o c a ld e c i s i o nt r e e st og e tt h ew h o l ed e c i s i o nt r e ea f t e rt h e l o c a ld e c i s i o nt r e e sa r em a d e ，t h e nt h ef i n a lr e s u l t si sg o t i tw a sp r o v e dt h a tt h es e c o n dt e c h n i q u ec o u l da c q u i r eab e t t e rf i n a lr e s u l t i no u r e x p e r i m e n t ，t h ei n t e g r a t e dd e c i s i o nm o d e lf r o mt h el o c a ld e c i s i o nt r e es h o w sh i g h p e r f o r m a n c e k e yw o r d s ：d i s t r i b u t e dc l a s s i f i c a t i o n ，d e c i s i o nt r e e ，a g e n t ，i n t e g r a t i o n i i 郑重声明 、尹 7 8 2 9 7 8 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽 窃、抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此 产生的一切法律责任和法律后果，特此郑重声明。 学位论文作者：王振牮 伽蛑月z 日 郑卅大学硕士学位论文 第一章绪论 随着网络技术的普及和深化，以及人们获取数据手段的多样化，人类所拥有 的数据急剧增加。如何更好的利用和共享现有的网络系统资源、发挥网络系统的 整体效率，在巨大的地理分布的数据集中提取描述重要数据类的模型或预测未来 的数据趋势，已经成为人们关注和探讨的重要问题，而要解决这个问题的一个重 要的技术就是分布式分类技术。 高性能的分布式分类算法，可以工作在非常大的分布式数据集上并提供有效 的决策信息。随着大量的数据集、用户和系统上的地理分布，结合各种不同的技 术来完成高性能的分布式的知识发现任务，就成为必然的事情。因此在商业领域 和科学研究领域都迫切要求发展一种新的技术，该技术能够从地理分布的数据集 中建立预测模型，以便能够使用模型预测类标记未知的对象类，将海量数据转换 成信息和知识i j 】，为决策和科学发现提供有力的支持。 1 1 分布式数据挖掘产生的原因 近几年来，数据挖掘的研究有了很大进展，在分布式数据库环境中进行数据 挖掘的研究显得尤为突出。分布式数据挖掘【2 1 ( d d m ) ，就是使用分布式计算， 从分布式数据库中发现知识的过程。人们越来越重视面向分布式数据库的数据挖 掘的研究，其主要原因是： ( 1 ) 数据挖掘的对象是快速增长的海量数据，而在现实环境中，绝大部分的 大型数据库都是以分布式的形式存在。因此，充分利用分布式的数据资源，进行 知识协同处理，提出新的分布式数据挖掘系统的体系结构是非常必要的。 ( 2 ) 在数据挖掘系统中，经常需要处理来自不同站点的数据库中的数据，使 得数据挖掘系统必须具有分布式数据挖掘的能力，同时也需要我们根据分布式数 据挖掘的特点设计出新的分布式数据挖掘算法。 ( 3 ) 随着w e b 技术的巨大成功及网络技术的飞速发展，w e b 已成为全球范围 内访问各种资源的存取平台。网络中的数据在以几何级数的速度增长。如何充分 利用i n t e m e t 中的资源，对分布式的数据进行数据挖掘也开始成为人们考虑的问 题。 郑州人学硕十学位论文 我们现在生活在一个网络化的时代，通信、计算机和网络技术正改变着整个 人类和社会。目前巨量信息的问题就等同于信息缺乏，在巨大的数据仓库中的知 识发现能够找到有趣的、隐藏的知识和模式，并以一种容易理解的方式把它们提 供出来，以利于信息决策。在分布式环境1 3 】中，人们积累的数据越来越多，激增 的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以 便更好地利用这些数据。因此分布式数据挖掘开始引起人们的关注。 1 2 分布式数据挖掘系统的特点 由于分布式数据库通常处于种分散的状态，给分布式数据挖掘造成了很大 的困难。分布式数据挖掘系统应该具有以下的特点： ( 1 ) 结果有效 由于分布式数据挖掘系统工作在地理分布的数据集上，而目前大多数分类算 法适用于集中式环境，因此，必须对分布式数据挖掘的局部结果进行必不可少的 集成，得到合理有效的全局结果。 ( 2 ) 协作控制 为了方便地实现分布式数据挖掘，一个用于全局协调控制的站点是必须的。 在不存在全局控制站点情况下，整个系统的通讯控制非常复杂。为了得到全局知 识，所有的站点将进行大量的通讯开销，比起使用全局控制站点的系统来说开销 和难度都要大得多。因此，引入全局协调控制站点可以有效、方便的进行同步协 作处理。 ( 3 ) 扩展方便 由于数据挖掘理论和算法研究的快速发展，新的知识形式、新的数据挖掘算 法不断出现。为了能够保证分布式数据挖掘系统的持续可用，分布式数据挖掘系 统应设计成容易扩展的开放式系统。当出现新的算法、新的知识形式时，系统能 够通过自身的扩展性功能加入这些新的知识形式、新的算法，而无须对系统进行 重新构造或编写。 ( 4 ) 灵活挖掘 分布式数据挖掘系统可以灵活的响应用户的各种数据挖掘要求，按照用户的 要求进行数据挖掘，以满足不同用户的需要。 郑卅l 大学硕士学位论文 f 5 1 移动挖掘 在有些数据挖掘算法中，需要挖掘算法顺序访问各个站点中的数据集，那么， 分布式数据挖掘系统必须可以支持挖掘算法的移动性。也就是说，当一个算法在 一个站点上完成了在本站点的数据挖掘任务之后，还可以移动到其它站点上继续 进行挖掘。 ( 6 1 知识共享 在各个站点间进行分布式数据挖掘时必须采用可以被理解的知识形式。一是 因为分布式数据挖掘一般包含面向知识的挖掘，为实现协同挖掘必须采取能够理 解相同的知识表示方式。二是因为各个站点上的用户可能需要访问其它站点上的 知识，这也需要有一种通用的知识表示方式。 ( 7 ) 平台无关 由于在分布式系统中存在着平台的异构、操作系统的异构、数据库系统的异 构，因此分布式数据挖掘系统必须完成在各种平台的数据挖掘任务。 ( 8 ) 安全保证 在分布式系统中进行数据挖掘需要考虑的一个问题就是安全性的保证。般 来说有三个方面的安全性考虑：一是数据存取的权限控制；二是知识存取、传送 的安全；三是挖掘任务的设置权限，即什么角色可以发起什么样的数据挖掘任务。 除以上显著的几个特点以外，在设计一个分布式数据挖掘系统时，还需要考 虑许多其它些问题，比如，挖掘出来的知识如何有效的表示，与用户的交互以 及处理各站点间负载的均衡问题等等。 1 3 几种重要的分布式技术 从历史和技术的角度来看比较重要的分布式技术有以下四种：d c e 4 巧1 ( d i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ) ；c o m t 6 协c o m ( c o m p o n e n to b j e c t m o d e l d i s t r i b u t e d c o m p o n e n tm o d e l ) ：c o r b a 7 i c e m r n o no b j e c tb r o k e r a r c h i t e c t u r e ) ；w e bs e r v i c e 。在这四种分布式技术中，存在着两大主流技术标准， 它们是o m g 的c o r b a 和m i c r o s o f t 的d c o m 模型。 ( 1 ) d c e 罔( d i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ) d c e 是一个分布式计算环境，几个相互独立的系统可以通过它共享数据、 郑州大学硕士学位论文 处理器、应用设备，使得跨系统操作起来就像在一个单独的系统上一样。这些独 立的系统可以来自不同的厂商；可以运行着不同的操作系统；它们可以是微型机、 小型机甚至是超级计算机；它们所在的网络，可以是一个局域网，也可以是一个 全球性的广域网络。 ( 2 ) c o m d c o m ( c o m p o n e n to b j e c tm o d e l ，d i s t r i b u t e dc o m p o n e n tm o d e l ) 组件对象模型c o m d c o m 是一套基于m i c r o s o f tw i n d o w s 平台的组件对象 接口标准。遵循这套标准的对象称之为w i n d o w s 组件对象，所有的w i n d o w s 组 件对象在系统中共存并且以客户服务器的模式充分的相互作用，从而完成各种 复杂的功能。 进程内组件通讯 进程类组件通讯中，客户直接调用服务组件的接口，利用服务组件的功能， 如图示。 臣皂 图1 1 进程内组件通讯 本地进程外组件通讯 通过利用操作系统支持的跨进程通信方法。c o m 提供了组件对象的进程透 明特性，使得客户程序和组件程序完全屏蔽了底层的跨进程通信细节，它把客户 中的调用截取过来，经过转换，传递到组件进程中，由组件对象负责处理，如图 示。 图1 2 本地进程外组件通讯 分布式组件对象模型( d c o m ) d c o m 是m i c r o s o f t 为适应分布式计算的发展由c o m 拓展而来，它支持不 同计算机上组件对象与客户程序或者组件对象间的互相通讯。d c o m 使用与开 放软件基金会( o s f ) 的远程过程调用( r p c ) 兼容的r p c 机制，使处于网络 4 郑州大学硕士学位论文 上不同节点的构件对象得以相互作用，并保证网络的透明性和通信的自动化，使 编程者感觉所有构件对象都在本地一样。 c 1 i e n t 图l 3 分布式组件对象通讯 如上图2 3 所示，客户和组件分别运行在不同的机器上，d c o m 只是简单地 把本地跨进程通讯用一个网络协议传输过程传递，客户代码和组件对象都感觉不 到中间发生的过程，只是中间数据传递的路线更长一些。 ( 3 ) c o r b a 9 1 ( c o m m o no b j e c tb r o k ea r c h i t e c t u r e ) c o r b a 技术规范是由o m g 制定的，对象管理组( o b j e c tm a n a g e m e m g r o u p o m g ) 是一个非盈利性协作组织，它是在1 9 8 9 年由1 3 家公司创建的， 至今已拥有超过8 0 0 名成员。o m g 的中心任务是为分布式计算环境中的对象技 术设立一个体系结构和一组规范，主要目标是使基于对象的软件成员在分布异构 环境中可重用，可移植和可互操作。 ( 4 ) w e bs e r v i c e w 曲服务1 0 1 技术组件是套开放的规范，它们要么是现有的因特网标准， 要么是被广泛接受并正在通过正常步骤成为标准的规范。组件的基本部分包含 h t t p 、x m l 、s o a p 、w s d l 、u d d l 以及w s f l 。 w e b 是指由企业发布的完成其特别的在线应用服务，其他公司或应用软件能 够通过i n t e m e t 来访问并使用这项在线服务。w e b 服务使用s o a ( 面向服务的架 构，s e r v i c e o r i e n t a r c h i t e c t u r e ) 架构。该架构突出强调了任何系统都有的两个重 要的方面，即三种角色和三种操作。其中角色指的是不同类型的实体，而操作指 的是为了使w e b 服务工作，这些实体所完成的功能。如图示。 邦州大学硕士学位论文 ， 服务注册表 聋拽j 、一 发布 7 、? 厂= 。j i = 二、1 绑定 向务提供者、 服务消费者 _ 苦旅荔籀毳| 图1 4 w e b 服务架构 由于分布式数据库的发展，原来的集中式数据挖掘系统不能满足分布式数据 挖掘的需要，因而分布式数据挖掘系统的研究成为数据挖掘领域新的研究热点。 许多人开始了对基于软构件的分布式计算环境的新型分布式数据挖掘体系的研 究。 1 4 分布式数据挖掘的研究现状 随着计算机处理各种数据问题能力的提高，人类解决各种科学和工程问题的 能力也大大提高。然而，人类社会的发展将导致计算机面临的问题越来越难，社 会的发展对计算机处理数据问题能力提高的要求是无止境的，这就需要不断提高 计算机处理数据问题的能力。因此，人们一方面在不断提高计算机的硬件性能和 软件性能，另外在如何利用分布式环境，解决数据挖掘中的数据处理问题也都取 得了较大的进展。 对于大型的数据处理问题，传统的方法是依赖于大型高性能计算机。随着分 布式计算环境的发展人们已经提出了很多种方案。在分布式的应用中，比较典型 的有日本筑波大学研究的o p e nc f l p “l 系统，该系统是建立在c o r b a 技术之上 的，c o r b a 虽然已经在各种平台上得到了实现，然而实际情况是建立在这些协 议之上的任何解决方案都依赖于单一厂商的实现。另外，还有o p e n m a t h ， m u l t i p r o t o c o l 与i a m c 等系统方案。 虽然分布式数据挖掘是近几年才提出的新的研究领域，但由于其诱人的应用 前景，目前已有相当数量的研究人员投人到对该领域的研究当中并且取得了一定 的成果。早期对分布式数据挖掘1 2 d 钔的研究工作主要集中在水平划分的分布式数 据库，其中，最为突出的发展是多代理技术，这是提高分布式数据挖掘效率的有 效手段，许多典型的分布式数据挖掘系统 1 5 - 1 6 l 都使用了这种软件代理技术，如 s t o l f o 的j a m 系统、k a r g u p t a 的p a d m a 系统、c h a v e z 的c o a l l e n g e r 系统。后 6 郑州大学硕十学位论文 来，针对垂直划分的分布式数据库，k a r g u p t a 、p a r k 等人又提出了汇集型数据挖 掘系统( c d m ) 。如何设计出一个分布式数据挖掘系统的体系结构，真正能支持各 种分布式数据挖掘算法、真正实现平台无关性是目前乃至今后的分布式数据挖掘 研究工作的非常重要的一个方面。 j e r z yb a l a 和a 1w i l l i a m s 等人，在信息科学的第七届联合会议上，提出了题 为a p p l i c a t i o n so f d i s t r i b u t e dm i n i n gt e c h n i q u e sf o rk n o w l e d g ed i s c o v e r y 的研究， 提出了他们关于基于决策树的分布式分类算法【1 7 1 的研究成果。j e r z y 等提出【1 8 1 的 基于决策树的分布式分类算法中，经由a g e n t s 和m e d i a t o r 之间的同步协作机制 来完成，m e d i a t o r 负责各个a g e n t 之间的通信。分布式数据挖掘的结果通过树的 归纳算法以一系列的规则集来表示。该算法中，以一种反复迭代的方式，找到最 佳的分类属性，利用这个属性特征来划分数据。各个a g e n t 通过协商、合作和行 为规范的方式，产生出局部子树，并且把局部结果传达给各个a g e n t 。 1 5 本文的工作 随着大量的数据集、用户和系统上的地理分布，结合各种不同的技术来完成 高性能的分布式的知识发现任务，就成为必然的事情。目前的许多决策支持和知 识发现工具，在集中式环境下具有很好的性能，但是在分布式情况下却存在着许 多问题。所以为了充分利用分布式的数据，人们提出了分布式数据挖掘的概念， 它是近几年才提出的新的研究领域，目前对它的研究还不太完善，还存在许多尚 待解决的问题。 分布式分类算法是一个具有挑战性的课题，对于基于决策树的分布式分类算 法的研究来说，存在着一系列的等待我们去解决，或者说去更好的解决的问题： 能否加快属性的选择，比如数据集属性的选择对最终结果的影响问题；以及局部 结果的集成问题等等。 j e r z yb a l a ，a iw i l l i a m s 等人在信息科学的第七届联合会议上，提出了题为 a p p l i c a t i o n so fd i s t r i b u t e dm i m n gt e c h n i q u e sf o rk n o w l e d g ed i s c o v e r y 的研究成 果，提出了他们关于基于决策树的分布式分类算法的研究内容。 j e r z y 等人提出的该基于决策树的分布式分类算法中，经由a g e n t s 和 m e d i a t o r 之间的同步协作机制来完成，m e d i a t o r 负责各个a g e n t 之间的通信。分 7 郑州火学硕士学位论文 布式数据集的分类结果通过树的归纳算法以一系列规则集来表示。该算法中，以 一种反复迭代的方式，找到最佳的分类属性，利用这个属性特征来划分数据。各 个a g e n t 通过协商、合作和行为规范的方式，产生出局部子树，并且把局部结果 传达给各个a g e n t 。 首先，本文考虑到在j e r z y 的基于决策树的分布式分类算法中，生成局部结 果时，所用到的决策树算法中的核心问题就是选取在树的每个节点要测试的属性 1 9 1 ，传统的属性选择是基于信息增益度量，本文引入了简化的信息增益作为属 性选择的度量，它一定程度上提高了算法执行的效率。 其次，决策树l 是对分类问题进行深入分析的一种方法。我们进一步研究 发现在基于决策树的分布式分类算法中，按基于决策树的分布式分类算法生成的 各个局部决策树往往复杂而庞大，令用户难以理解。 在实际问题研究中，我们对决策树算法的评价有两个标准：第一，生成的决 策树是否比较简化；第二，分类的精度是否达到一定标准。为满足这两个标准的 衡量要求，使得我们在重分类精确性的同时，也要加强决策树的进一步简化的研 究。所以另外一个引起关注的问题就是局部分类结果的集成问题。考虑集成的目 的在于确保精确程度的同时，来提高可理解性。这两个目标不定是矛盾的，可 能有种方法能同时提高精确度和可理解性。 在基于决策树的分布式分类算法中，针对以上的不足，我们经过深入研究发 现对决策树的局部结果集成的方法大致有两种： 1 ) 在产生局部决策树后，先得到局部规则，然后进行局部规则结果的集成， 进行修剪措施，得到全局规则，即规则后集成 2 ) 就是产生局部决策树后，先进行局部决策树的集成，得到全局决策树， 再经过“错误率降低修剪”的方法，即局部决策树集成，从而得到全局 结果。 在这两种方法中，存在着一个共同的处理策略，那就是在集成的时候，先允 许过度拟合，再使用验证集合考虑采用“错误率降低修剪”来提高全局结果的精 确度和可理解性。实验证明，我们所研究的第二种集成方法，先进行局部决策树 的集成，通过对错误率降低修剪的方法，再得到全局规则，一定程度上解决了在 基于决策树的分布式分类算法中，对决策树的局部结果集成这个问题。 8 郑州大学硕士学位论文 1 6 本文的结构安排 本文结构安排如下： 第一章简要介绍了分布式数据挖掘技术出现的原因、特点、研究现状以及 本文的工作和结构安排； 第二章介绍了分类的有关概念、分类的过程、分类算法的比较标准以及分 类的基本技术； 第三章详细介绍了决策树分类算法的思想、工作过程以及决策树学习算法 的发展过程中各个阶段的决策树算法； 第四章针对基于决策树的分布式分类算法，重点研究了d m t k d 算法，分 析基于决策树的分类算法所要解决的难点、关键点，并给出了解决 算法的实施方案； 第五章通过具体的实验给出了解决基于决策树的分布式分类算法中的局部 结果的集成的算法，并给出了实验结果： 第六章对本文总结，提出了下一步需要进行的工作。 9 郑州大学硕士学位论文 第二章分类 分类是数据挖掘的一个重要问题。数据库内容丰富，蕴涵大量信息，可以用 来做出智能的商务决策。分类是一种数据分析形式，可以用于从数据库中提耿重 要数据类的模型或预测未来的发展趋势。它是指在数据库的各个对象中找出共同 特性，并按照分类模型把它们进行分类。学习模型通常用分类规则、决策树或数 学公式的形式提供。分类的结果可以为以后的数据样本进行分类，也能对数据库 的内容提供更好的理解。 2 1 分类的概念 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是 利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预 测。 分类是数据挖掘的一种非常重要的方法。它在已有数据的基础上产生一个分 类函数或构造出一个分类模型( 即我们通常所说的分类器( c l a s s i f i e r ) ) 。该函数 或模型能够把数据库中的数据记录映射到给定类别中的某一个，从而可以应用于 数据预测。要构造分类器，需要有一个训练样本数据集作为输入。训练集( t r a i n i n g s e t ) 由一组数据库记录或元组构成，每个记录是一个由有关字段值组成的特征向 量，我们把这些字段称做属性( a t t r i b u t e ) ，把用于分类的属性叫做标签( l a b e l ) ， 标签属性也就是训练集的类别标记。一个具体样本的形式可以表示为( v 】，v 2 v 。；c ) ，其中v ，表示字段值，c 表示类别。 训练集是构造分类器的基础，它是包含一些属性的一个数据库表格，其中的 一个属性被制定为目标属性。目标属性的类型必须是离散的，且目标属性可能值 的数目越少越好( 最好是两或三个值) 。目标属性的数目越少，构造出来的分类 器的错误率越低。 从训练集中自动地构造出分类器的算法叫做生成器( i n d u c e r ) 。在生成分类器 后，可以利用它来对数据集中不包含目标属性的记录进行分类，标签属性的值也 可以用分类器来预测。 1 0 郑州大学硕士学位论文 2 2 分类的过程 分类是一种有指导的学习方法，它反映同类事务共同性质的特征性知识和不 同事务之间的差异性特征知识。分类过程可以被分为两步【l 】： ( 1 ) 建立一个模型，描述预定的数据类或概念集。通过分析由属性描述的 数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个称作类标号 的属性确定。对于分类，数据元组也称作样本、实例或对象。为建立模型而被分 析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，并随机 的由样本群选取。 学习模型通常用分类规则、决策树或数学公式的形式提供。例如，给定一个 顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度( 如优或相当好) 来识别顾客。该规则可以用来为以后的数据样本分类，也能对数据库的内容提供 更好的理解。 ( 2 ) 使用模型进行分类。首先评估模型( 分类算法) 的预测准确率。保持 方法是一种使用类标号样本测试集的简单方法。这些样本随机选取，并独立于训 练样本。对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。 被模型正确分类的测试样本的百分比就是模型在给定测试集上的准确率。注意， 如果模型的准确率根据训练数据集评估，评估可能是乐观的，因为学习模型倾向 于过分适合数据( 即，它可能并入训练数据中某些异常，这些异常不出现在总体 样本群中) 。因此使用测试集来评估分类算法的准确率。如果认为模型的准确率 可以接受，就可以用它对类标号未知的数据元组或对象进行分类。 分类具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选择购物等。 2 。3 分类前准各 分类前可以对数据使用下面的预处理，以便提高分类和预测过程的准确性、 有效性和可伸缩性。 ( 1 ) 数据清理：是旨在消除或减少数据噪声( 例如使用平滑技术) 和处理 空缺值( 例如，用该属性最常出现的值，或者根据统计，用最可能的值替换空缺 值) 的数据预处理。尽管大部分分类算法都有处理噪声和空缺值的机制，但该步 骤有助于减少学习时的混乱。 郑州大学硕士学位论文 ( 2 ) 相关性分析：数据中许多属性可能与分类任务不相关。例如，记录银 行贷款申请是星期几提出的数据可能与申请的成功不相关。此外，有些属性可能 是冗余的。因此，可以进行相关分析，删除学习过程中不相关的或冗余的属性。 在机器学习，这一过程称为特征选择。包含这些属性将减慢和可能误导学习步骤。 理想情况下，用在相关分析上的时间，加上从“压缩的”特征子集上学习的时间， 应当少于由原来的数据集合上学习所花的时问。因此，这种分析可以帮助提高分 类的有效性和可伸缩性。 ( 3 ) 数据变换：数据可以概化到较高层概念。概念分层可以用于此目的。 对于连续值属性，这一步非常有用。例如，属性i n c o m e 的数值可以概化为离散 的区间，如l o w ，m e d i u m 和h i g h 。类似地，标称值，如s t r e e t ，可以概化到高层概 念，如c i t y 。由于概化压缩了原来的训练数据，学习时的输入输出操作将减少。 ( 4 ) 规范化【l 】：数据也可以规范化，特别是在学习阶段使用神经网络或涉 及距离度量的方法时。规范化涉及将给定属性的所有值按比例缩放，使得它们落 入较小的指定区问，如一1 0 到1 o ，或o 0 到1 0 。例如，在使用距离度量的方法 时，这可以防止具有较大初始域的属性( 如i n c o m e ) 相对于具有较小初始域的 属性( 如二进位属性) 权重过大。 2 4 分类算法的比较标准 常用的分类算法的比较和评估标准有如下几点： ( 1 ) 预测的准确率：这涉及模型正确的预测新的或先前未见过的数据的类 标号的能力。 ( 2 ) 速度：这涉及产生和使用模型的计算花费。 ( 3 ) 强壮性：这涉及给定噪音数据或具有空缺值的数据，模型正确预测的 能力。 ( 4 ) 可规模性：这涉及给定大量数据，有效地构造模型地能力。 ( 5 ) 可解释性：这涉及学习模型提供的理解和洞察的层次。 此外，还有计算复杂度和模型描述的简洁度。计算复杂度依赖于具体的实现 细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此时间和空 间的复杂度将是非常重要的问题。对于描述型的分类任务，模型描述越简洁越受 郑州大学硕士学位论文 欢迎。例如，采用规则表示的分类器构造法就更有用，而神经网络方法产生的结 果就难以理解。 目前，已有许多关于不同分类算法的比较，并且该问题仍然是一个研究课题。 尚未发现有一种算法对所有数据都优于其它方法。如准确性、训练时间、强壮性、 可解释性和可规模性必须考虑，并且可能涉及折衷，使得寻求更好的方法进一步 复杂化。试验研究表明，许多算法的准确性非常类似，其差别是统计不明显的， 而训练时间可能显著不同。一般地，大部分神经网络和涉及样条的统计分类与大 部分决策树方法相比，趋向于计算量大。并且分类的效果一般和数据的特点有关： 有的数据噪声大，有的缺少值，有的分布稀疏，有的字段或属性问相关性强，有 的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适 合于各种特点的数据。 2 5 分类器的准确度评估方法 2 5 1 影响分类器错误率的因素 ( 1 ) 训练集的记录数量。生成器要利用训练集进行学习，因而训练集越大， 分类器也就越可靠。然而，训练集越大，生成器构造分类器的时间也就越长。错 误率改善情况随训练集规模的增大而降低。 ( 2 ) 属性的数目。更多的属性数目对于生成器而言意味着要计算更多的组 合，使得生成器难度增大，需要的时间也更长。有时随机的关系会将生成器引入 歧途，结果可能构造出不够准确的分类器( 这在技术上被称为过分拟合) 。因此， 如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。 ( 3 ) 属性中的信息。有时生成器不能从属性中获取足够的信息来正确、低 错误率的预测标签( 如试图根据某人眼睛的颜色来决定他的收入) 。加入其他的 属性( 如职业、每周工作小时数和年龄) ，可以降低错误率。 ( 4 ) 待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布， 那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类 器，那么试图用它来对包含许多运动用车辆的记录进行分类可能没多大用途，因 为数据属性值的分布可能是有很大差别的。 郑州人学硕士学位论文 2 5 2 分类器的错误率的评估方法 有两种方法可以用于对分类器的错误率进行评估，它们都假定待预测记录和 训练集取白同样的样本分布。 ( 1 ) 保留方法( h o l d o u t ) ：记录集中的一部分( 通常是2 3 ) 作为训练集，保 留剩余的部分用作测试集。生成器使用2 3 的数据来构造分类器，然后使用这个 分类器来对测试集进行分类，得出的错误率就是评估错误率。 虽然这种方法速度快，但由于仅使用2 3 的数据来构造分类器，因此它没有 充分利用所有的数据来进行学习。如果使用所有的数据，那么可能构造出更精确 的分类器。 ( 2 ) 交叉纠错方法( c r o s sv a l i d a t i o n ) ：数据集被分成k 个没有交叉数据的子 集，所有子集的大小大致相同。生成器训练和测试k 次；每一次，生成器使用去 除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有得 到的错误率的平均值作为评估错误率。 交叉纠错法可以被重复多次( 0 ，对于一个f 次k 分的交叉纠错法，扩f 个分 类器被构造并被评估，这意味着交叉纠错法的时间是分类器构造时间的舻f 倍。 增加重复的次数意味着运行时间的增长和错误率评估的改善。我们可以对k 的 值进行调整，将它减少到3 或5 ，这样可以缩短运行时间。然而，减小训练集有 可能使评估产生更大的偏差。 通常h o l d o u t 评估方法被用在最初试验性的场合，或者多于5 0 0 0 条记录的 数据集；交叉纠错法被用于建立最终的分类器，或者很小的数据集。 2 6 分类的基本技术 由于分类技术在不同领域的广泛应用，统计学、机器学习、神经网络等领域 的研究者提出了很多分类方法。现有的分类技术主要有：基于决策树的分类、贝 叶斯分类、基于案例的推理、基于源自关联规则挖掘概念分类、神经网络、遗传 算法、模糊集和粗糙集方法等。下面介绍一些常用的分类技术。 ( 1 ) 基于决策树的分类 决策树归纳算法f 2 1 1 在统计学、机器学习和数据挖掘领域都有广泛的应用。 决策树分类算法以树形结构表示分类结果，树根节点代表整个数据集台空闯，每 郑州大学硕_ 上学位论文 个分支节点是对一个属性的测试，该测试将数据集集合空间分割成两个或多个 块，而每个叶子节点代表一个类。由根结点到叶节点的路径描述了各种分类规则。 ( 2 ) 贝叶斯分类 贝叶斯分类是统计学分类方法，它基于贝叶斯纠定理，使用后验概率预测 类成员关系的可能性，如给定样本属于某特定类的概率。尽管朴素贝叶斯分类 算法很简单，但是在许多应用领域取得了巨大的成功，分类准确度可以与决策树 和神经网络等复杂的算法媲美。应用于大型数据库，贝叶斯【2 3 】方法表现出了高 准确度与高速度。当条件独立性假设成立时，朴素贝叶斯分类是最精确的，然而 朴素贝叶斯分类算法的条件独立性假设在现实数据集上通常是不成立的。 ( 3 ) 源于关联规则的分类 关联规则挖掘是数据挖掘研究的一个重要的、高度活跃的领域。最近，数据 挖掘技术业已将关联规则【2 4 1 挖掘用于分类问题，如基于关联规则2 5 1 的分类 ( c l a s s i f i c a t i o nb a s e d o n a s s o c i a t i o n ，c b a ) 算法、c m a r 算法( c l a s s i f i c a t i o nb a s e d o nm u l t i p i e a s s o c i a t i o nr u l e s c m ar ) 、c p a r 算法。 ( 4 ) 神经网络分类 神经网络最早是由心理学家和神经生物学家提出的，旨在寻求开发和测试神 经的计算模拟。神经网络口6 1 是一组相互连接的输z 输出单元，每个连接都与一 个权值相连。在学习阶段，通过调整神经网络的权，使网络能够正确预测输入样 本的类标号来学习。 ( 5 ) k - 最临近分类 最临近分类是基于类比的学习。训练样本用维数值属性描述，每个样本 代表维空间的一个点，所有训练样本都被存放在维模式空间中。给定一个 未知样本，尽最临近分类法搜索模式空间，找出最接近未知样本的k 个训练样 本。 ( 6 ) 基于e p 的分类算法 1 9 9 9 年，d o n g 和工f 提出了一种新的知识模式，即显露模式( e m e r g i n g p a t t e r n ，e p ) 口7 1 ，这种模式能够捕获不同类之间的差异和取值倾向。由于e p 具 有很好的区分性能，因此很适合用来指导分类。 其他的分类算法还有很多如：支撑向量机、遗传算法、粗糙集算法、基于案 例的推理等多种类型的分类算法。这些算法都具有自身的优点和不足，但是都在 邦州大学硕士学位论文 一定的应用领域取得了成功。不存在某一类型或是某一个算法在所有的数据集上 的分类准确度、训练时间、强壮性、可规模化、可解释性等方面性能都优于其他 类型的算法。实际应用中最好的解决方案常常是各方面性能要求的折中。因此， 评价一个算法的优劣常常是结合具体的应用背景和领域要求。 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据类或概念的模 型( 或函数) ，以便能够使用模型预测类标记未知的对象类。分类可以用来预测 数据对象的类标记。然而，在某些应用中，人们可能希望预测某些空缺的或不知 道的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预测 ( p r e d i c