（计算机应用技术专业论文）示例学习的决策树算法研究.pdf

摘要 决策树分类学习算法是使用最广泛、实用性很强的归纳推理方法之一，在 机器学习、数据挖掘等人工智能领域有相当重要的理论意义与实用价值。 在各种决策树学习算法当中，最有影响力的是采用信息熵的下降速度作为 选择测试属性的标准的i d 3 算法。但是i d 3 算法存在学习简单逻辑表达式的能 力较差、偏向属性取值数目较多等缺陷。论文企图在i d 3 的基础上，针对其中 的一些不足加以改进。 本文首先介绍了示例学习的扩张矩阵理论与决策树学习的最优化问题、i d 3 算法的信息论原理与实现以及c 4 5 算法的剪枝原理。然后钊对i d 3 学习逻辑表 达式方面的不足，提出了一种对i d 3 学习到的决策树进行简化的算法基于 蕴含规则的决策树简化算法( d t s a b o i r ，简记为b o i r ) ，b o i r 以i d 3 算法构 造的决策树为基础，先序遍历由i d 3 构造出来的决策树的各个节点，并对其子 树进行比较，如果各子树的根属性都相同而且存在某些相应的分支对于各子树 完全相同，则改变决策树中相应属性的层次关系并把相同的分支分别合并起 来。 本文实现了b o i r 对逻辑表达式的学习，并利用f a m n 家族数据集对该简 化算法进行了测试，实验所取得的数据验证了该算法的有效性。 关键字：示例学习、决策树、信息熵、简化决策树、子树比较、分支合并 _ _ 一- _ _ 一 a b s t r a c t d e c i s i o nt r e ec l a s s i f i c a t i o nl e a r n i n ga l g o r i t h mi so n eo f t h e m o s tw i d e l yu s e da n d v e r yp r a c t i c a l i n d u c t i v ei n f e r e n c em e t h o d s i ti so fm u c ht h e o r e t i c a la n dp r a c t i c a l s i g n i f i c a n c ei nt h ea r t i f i c i a li n t e l l i g e n c ek i n g d o ms u c ha sm a c h i n el e a r n i n ga n d d a t a m i n i n g i nt h em a n yd e c i s i o nt r e el e a r n i n ga l g o r i t h m s ，t h em o s ti n f l u e n t i a lo n ei st h ei d 3 ， w h i c ht a k e st h ed e s c e n d i n gv e l o c i t yo ft h ei n f o r m a t i o ne n t r o p ya s t e s ta t t r i b u t e s e l e c t i o nc r i t e r i o nh o w e v e r , a si sw e l lk n o w n ，i d 3h a st h es h o r t a g es u c ha sl e a r n i n g l o g i c a le x p r e s s i o n sa n dl e a n i n gt ot h ea t t r i b u t ew h i c h t a k e sm o r ev a l u e s b a s eo ni d 3 a l g o r i t h m ，t h i s t h e s i sa t t e m p t st oi m p o v eo i ll e a r n i n gl o g i c a le x p r e s s i o n s w ef i r s ti n t r o d u c ee x t e n s i v em a t r i xt h e o r yi nl e a r n i n gf r o me x a m p l e sa n dt h e o p t i m i z a t i o np r o b l e mi nd e c i s i o nt r e el e a r n i n g ，t h ei n f o r m a t i o nt h e o r yp r i n c i p l ea n d t h ei m p l e m e n t a t i o no fi d 3a l g o r i t h ma n dt h ep r u n i n gp r i n c i p l eo fc 4 5a l g o r i t h m t h e n ，a i m i n ga tt h ei d 3 sd e f e c to nl e a r n i n gl o g i c a le x p r e s s i o n s ，w ep u l lf o r w a r da d e c i s i o nt r e es i m p l i f i c a t i o na l g o r i t h mb a s e do ni n c l u s i o nr u l e ( d t s a - b o i r ，a b b r ， b o i r 、t os i m p l i f yt h ed e c i s i o nt r e ec o n s t r u c t e dw i t l li i ) 3 b o i rt r a v e r s e se a c hn o d e o f t h ei d 3d e c i s i o nt r e ei np r e o r d e r ，c o m p a r e si t ss u b t r e e sa n d ，i f t h er o o ta t t r i b u t e s o fe a c hs u b t r e ea r et h es a m ea n ds o m e c o r r e s p o n d i n gb r a n c h e so f a l lt h es u b t r e e sa r e i d e n t i c a l ，c h a n g e st h eh i e r a r c h i c a lr e l a t i o n s h i po f t h ec o r r e l a t i v ea t t r i b u t e si nt h e d e c i s i o nt r e ea n dm e r g e st h ei d e n t i c a lb r a n c h e s r e s p e c t i v e l y t h i st h e s i si m p l e m e n t st h ea l g o r i t h mb o i rf o rl e a r n i n gl o g i c a le x p r e s s i o n sa n d t e s t sb o i rw i t t ls o m ed a t a s e t si nt h ef a m nf a m i l y , a n dt h ed a t ag o tf r o mt h e e x p e r i m e n t v a l i d a t e st h ev a l i d i t yo f t h ea l g o r i t h m k e yw o r d s ：l e a r n i n gf r o me x a m p l e s ，d e c i s i o nt r e e ，i n f o r m a t i o n e n t r o p y , s i m p l i f y i n g d e c i s i o nt r e e ，s u b t r e ec o m p a r i s o n ，m e r g i n gb r a n c h e s i l 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕 士学位论文质量要求。 答辩委员会签名 主席：辱铭似生就缛琴旋 委员： 导师： 孚：戡 r ， 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特, b i j d h 以标注和致谢的地方外，论文中不包含其他人己经发表或撰写过的研究成 果，也不包含为获得合肥工业大学或其他教育机构的学位或证降而使用过的材料。 与我一同一 ：作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名 签字日期：曲尹年加手日 学位论文版权使用授权书 本学位论文作者完全了解金魍王些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权合肥上业 大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者繇踟 签字日期：加f 年g 月子日 学位论文作者毕业后去向 t 作单位： 通讯地址： 导师虢乎欺多 签字日期：2 舻( f 年6 月廖目 电话 邮编 致谢 论文是在我的导师史斌宁研究员的悉心指导下完成的。值此论文完成之 际，谨向我的导师史老师表示最真诚的感谢。史老师在我的近三年硕士期间， 对我的学习和生活给予了无微不至的关怀和帮助。他对论文的丌题、修改直至 定稿一直给予精心地指导，并提出了大量的宝贵意见。论文的字里行间无不浸 透了史老师的心血。史老师诲人不倦，对事业兢兢业业，令人敬佩。 在此我还要真诚地感谢能源所的苏建徽老师和张国荣老师，没有他们对实 验室的安排，论文是无法完成的。 我还要感谢姜卯生、刘吴钰、路强等同学在学习上的帮助，使得我的论文 能够顺利的完成。 真诚地感谢计算机学院的王浩老师、胡学钢老师、王新生老师和徐静老师 等所有老师，没有他们的辛勤工作，我也无法完成论文。 感谢所有关心过我，帮助过我的老师和同学。 感谢参考文献中的所有作者的辛勤的工作。 献给我的父亲、母亲、姐姐和哥哥。 i l l 第一章绪论 决策树分类学习算法是使用最广泛、并且是非常实用的归纳推理方法之 一，在机器学习、数据挖掘、智能控制等人工智能领域有着相当重要的理论意 义与实用价值。完成分类任务的方法有决策树方法、神经网络方法、统计学方 法( 如贝叶斯方法等) 等，其中决策树方法以其速度快、精度高、生成的模式简 单等优点，在数据挖掘中受到许多研究者和软件公司的关注，如s g i 、s a s 等 公司在己推出的数据挖掘系统中，首选的方法就是决策树方法。 在决策树学习算法中，最有影响力的是q u i n l a n 提出的i d 3 算法剃。但由于 其在学习简单逻辑表达式方面的能力较差而受到很多攻击【2 5 ，3 “。本文从逻辑蕴 含的角度，构造并实现一种对决策树进行二次简化的算法b o i r ，力图弥补已 有算法( 在实验中以i d 3 为例) 在学习逻辑表达式方面的不足。论文还通过在实 验中采用f a m n 家族数据集来验证该算法的有效性。 1 1 决策树归纳学习的相关知识背景 11 1 机器学习 自上个世纪八十年代以来，机器学习作为人工智能的途径，在人工智能界 引起了广泛的兴趣。特别是近些年来，机器学习领域的研究工作发展很快，它 已成为人工智能的重要研究方向之一。 学习是智能的基本特征，但究竟什么是学习，目前还没有一个统一的定 义。多数学者认为学习是以组织化的知识出发，然后变得更为组织化。s i m o n 认为，如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。这 个说法的要点是：首先，学习是一个过程；其二，学习是对一个系统而言，这 个系统比较复杂，可以是一台计算机，也可以是计算系统，甚至是包括人的人 机计算系统：其三，学习改进系统性能，但未限制这种“改进”的方法。显 然，s i m o n 对学习的这个说法是思辨的，对计算机科学家来说，这还远远不 够，计算机科学家更关心对不同系统实现机器学习的过程，以及改变性能的效 果。图1 1 给出了一个简单的学习系统的模型。 图1 1 一个简单的学习系统模型 从普遍的观点来看，学习一般被认为是获取一种显式的知识的过程。更进 一步的看法则是把学习看作建立理论、形成假设和进行归纳推理的过程。不论 哪一种学习过程，它都与环境和知识库密切相关。 模型中的四个部分构成了学习系统的基本组成环节。环境可以是系统的工 作对象，也可以包括工作对象或客体所处的外界条件。知识库的内容用来理解 环境提供的信息并进行推理，通过学习系统它将得到扩充和改善。环境和知识 库共同构成以某种知识表示形式表达的信息描述体，分别代表外界信息的来源 和系统拥有的知识( 包括信息的结果) 。 学习元素和执行元素代表两个过程：学习元素对环境所提供的信息进行处 理，以便改善知识库中的显式知识；执行元素利用知识库的信息来完成某种任 务，然后把完成任务过程中所获得的一些信息反馈给学习环节，以指导进一步 的学习。学习元素的目的是要改善执行元素的行为，因此执行元素的复杂程 度、反馈作用和透明性等都会对学习元素产生重要影响。 1 、机器学习研究的发展 机器学习研究的主要发展过程大致可分为三个阶段【2 圳： 第一阶段是从1 9 6 0 年左右开始，主要目标是研制各类自组织和自适应系 统，它们能够修改自身以适应它们的环境。如果给系统一组刺激、一个反馈 源，以及修改它们自身组织的足够自由度，那么它们将改变自身以成为最优的 组织。这类系统所采用的主要方法是不断修改系统的控制参数以改进它的执行 能力，不涉及面向具体任务的知识，其理论基础是早在四十年代就开始研究的 神经网络模型。各种神经计算机的模拟被研制和检测，其中最著名的是 r o s e n b l a t t 的感知机【2 们，它是从m p 模型出发，具体地说，就是将扩展为多个神 经元的m p 模型作为优化算法的数学基函数。不过大多数想产生某些复杂智能 系统的企图都失败了。这个阶段的研究工作导致模式识别学科的诞生，同时形 成了机器学习的一种重要方法一一判别函数法。s a m u e l 的下棋程序就是使用这 种方法的杰出代表。 第二阶段是从7 0 年代开始一直到8 0 年代中期，这一阶段的主要目标是模 拟人在概念上的学习过程，机器的内部表示采用逻辑结构或图结构，系统学习 表示高级知识的符号描述，并能提出关于所学概念的各种假设。研究者们也逐 渐认识到学习是复杂而困难的过程，因此，不能期望学习系统可以从没有任何 知识开始，学到高深的概念。这种观点导致研究人员一方面深入探讨简单的学 习问题，另一方面则把大量的领域知识并入学习系统之中。人工智能的研究者 根据认知心理学的原理研究各种机器学习的方法，以符号运算为基础的机器学 习代替了以统计为基础的机器学习，成为人工智能研究的主流。在这个时期， 从学习的机制来说，主要是归纳机器学习，其中有代表性的学习算法有 m i c h a l s k i 的a q l l 1 2 与q u i n l a n 的i d 3 【1 6 1 。同时，使用不同学习机制的研究层 出不穷a 在8 0 年代中期，基于解释的学( e x p l a n a t i o n b a s e dl e a r n i n g ) 与类比学 习也引起人们极大的兴趣。特别是与类比学习原理相近的基于范例的学习( c a s e - b a s e dl e a r n i n g ) ，解决实际问题的能力较强。这些研究丰富了机器学习的研究。 第三阶段是机器学习蓬勃发展的阶段，大约从七f 年代中期开始。研究领 域从学习单个概念扩展到学习多个概念，同时，研究者开始考虑各种形式的学 习方法。学习过程一般都以大规模知识库作为背景，产生的学习系统和各种应 用系统紧密结合起来，在实际应用中发挥了重要的作用。这个阶段主要的学习 方法有神经网络学习【9 1 、支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) t 2 引、遗传算 法i ，j 、强化学习方法。 2 、常用的机器学习方法州 ( 1 ) 统计方法 统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。科学 的规律性一般总是隐藏得比较深，最初总是从其数量表现上通过统计分析看出 一些线索，然后提出一定的假说或学说，作进步深入的理论研究。当理论研 究提出定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然 现象或专门安排的实验所得资料，是否与理论相符、在多大程度上相符、偏离 可能是朝哪个方向等等问题，都需要用统计分析的方法。与统计学有关的机器 学习方法有： ( a ) 传统方法 统计学在解决机器学习问题中起着基础性的作用。传统的统计学所研究的 是渐近理论，即当样本趋向于无穷大时的统计性质。统计方法主要考虑测试预 想的假设是否与数据模型拟合。它依赖于显式的基本概率模型。统计方法处理 过程可以分为三个阶段：( i ) 搜集数据，包括采样和实验设计：( i i ) 分析数据， 包括建模、知识发现和可视化；( i i i ) 进行推理，包括预测和分类。 常用的统计方法有回归分析、判别分析、聚类分析和探索性分析。 ( b ) 模糊集 模糊集是表示和处理不确定性数据的重要方法。模糊集不仅可以处理不完 全数据、噪声或不精确数据，而且在开发数据的不确定性模型方面是有用的， 能提供比传统方法更灵巧、更平滑的性能。 ( c ) 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 建立在计算学习理论的结构风险 最小化原则之上。其主要思想是针对两类分类问题，在高维空间中寻找一个超 平面作为两类的分割，以保证最小的分类错误率。 ( d ) 粗糙集 粗糙集( r o u g hs e t ) 理论是由z d z i s k e wp a w l a k 在1 9 8 2 年提出。它是一种新的 数学工具，用于处理含糊性和不确定性，在数据挖掘中发挥重要作用。粗糙集 是由集合的下近似、上近似来定义的。下近似中的每一个成员都是该集合的确 定成员，而不是上近似中的成员肯定不是该集合的成员。粗糙集的上近似是下 近似和边界区的并集。边界区的成员可能是该集合中的成员，但不是确定的成 员。可以认为粗糙集是具有三值隶属函数的模糊集，即是、不是、也许。与模 糊集一样，它是一种处理数据不确定性的数学工具，常与规则归纳、分类和聚 类方法结合起来使用，很少单独使用。 ( 2 ) 规则归纳 规则反映数据项中某些属性或数据集中某些数据项之间的统计相关性。a q 算法是有名的规则归纳算法。关联规则一般形式为x ， x ： x 。jy c ，s ， 表示r ax ， j ： z 。可以预测y ，其可信度为s 。近年来提出了许多关联规 则算法。 ( 3 1 决策树 决策树的每一个非终节点表示所考虑的数据项的测试或决策。一个确定分 技的选择取决于测试的结果。为了对数据集分类，从根节点开始，根据判定自 顶向下，趋向终节点或叶节点。当到达终节点时，则决策树生成。决策树也可 以解释为特定形式的规则集，以规则的层次组织为特征。 ( 4 1 范例推理 范例推理是直接使用过去的经验或解法来求解给定的问题。范例常常是一 种已经遇到过并且有解法的具体问题。当给定一个特定问题，范例推理就检索 范例库，寻找相似的范例。如果存在相似的范例，它们的解法就可以用来求解 新的问题。该新问题被加到范例库以便将来参考。目前将范例推理与最近邻 原理( n e a r e s tn e i g h b o r ) 、格子机( 1 a t t i c em a c h i n e ) 相结合。 ( s ) 贝叶斯信念网络 贝叶斯信念网络是概率分布的图表示。贝叶斯信念网络特别是一种直接的 非循环的图，节点表示属性变量，边表示属性变量之间的概率依赖关系。与每 个节点相关的是条件概率分布，描述该节点与它父节点之间的关系。 ( 6 ) 科学发现 科学发现是在实验环境下发现科学定律。在s i m o n 著名的b a c o n 系统 中，核心算法基本上由两种操作构成。第一种操作叫做双变量拟合，判定一对 量之间的关系。第二种操作是合并多对关系到一个方程中。 ( 7 ) 遗传算法 遗传算法是按照自然进化原理提出的一种优化策略。在求解过程中，通过 最好解的选择和彼此组合，则可以期望解的集合将会愈来愈好。在数据挖掘 中，遗传算法用来形成变量问依赖关系假设。 分类是数据挖掘中的一个重要课题，目前在商业上应用最多，主要用于预 测和决策。分类的目的是提出一个分类函数或分类模型( 也常称作分类器) ，该 模型能把数据库中的数据项映射到给定类别中的某一个。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据 库记录或元组构成，每个元组是一个由有关字段( y - 称属性或特征) 值组成的特 征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可为样本向 量：( v 1 ，v 2 ，v n ；c ) 。在这里v i 表示字段值，c 表示类别。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计 方法包括贝叶斯法和非参数法( 近邻学习或基于范例的学习) ，对应的知识表示 则为判别函数和原型事例。机器学习方法包括决策树法和规则归纳法，前者对 应的表示为决策树或判别树，后者则一般为产生式规则。神经网络方法主要是 b p 算法，其模型表示是前向反馈神经网络模型，b p 算法本质上是一种非线性 判别函数。另外粗糙集方法也可以用于分类，其知识表示是产生式规则。 数据分类( d a t ac l a s s i f i c a t i o n ) 是一个两步过程，如图1 2 。第一步，建立一个 模型，描述预定的数据类集或概念集，通过分析由属性描述的数据库元组来构 造模型。假定每个元组属于一个预定义的类，由一个称作类标号属。l 牛( c l a s sl a b e l a t t r i b u t e ) 的属性确定。对于分类，数据元组也称作样本、实例或对象。为建立 模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练 样本，并随机地由样本群选取。由于提供了每个训练样本的类标号，该步也称 作有指导的学习( 即模型的学习在被告知每个训练样本属于哪个类的“指导”下 进行) 。它不同于无指导的学习( 或聚类) ，那里每个训练样本的类标号是未知 的，要学习的类集合或数量也可能事先不知道。 通常，学习模型用分类规则、决策树或数学公式的形式提供。例如，给定 一个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度优良或相 当好来识别顾客，如图1 2 a 。这些规则可以用来为以后的数据样本分类，也能 对数据库的内容提供更好的理解。 第二步，如图1 2 b ，使用模型进行分类。首先评估模型( 分类法) 的预测准 确率。后面3 4 节将介绍评估准确率的多种方法。保持( h o l d o u t ) 方法是一种使用 类标号样本测试集的简单方法。这些样本随机选取，并独立于训练样本。模型 在给定测试集上的准确率是正确被模型分类的测试样本百分比。对于每个测试 样本，将己知的类标号与该样本的学习模型类预测比分类的测试样本的百分 比a 对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。如 果模型的准确率根据训练数据集评估，评估可能是乐观的，因为学习模型倾向 于过分拟合数据( 即，它可能并入训练数据中某些特别的异常，这些异常不出现 在总体样本群中1 。 图1 2 数据分类过程：a ) 学习：用分类算法分析训练数据( 这里，类标号属性是 信誉度，学习模式或分类法以分类规则形式提供) b ) 分类：测试数据用于评估 分类规则的准确率( 如果准确率是可以接受的，则规则可用于新的数据元组分类) 不同的分类器有不同的特点。有三种分类器评价或比较尺度：( 1 ) 预测准确 度；( 2 ) 计算复杂度；( 3 ) 模型描述的简洁度。预测准确度是用得最多的一种比较 尺度，特别是对于预测型分类任务，目前公认的方法是1 0 遍分层交叉验证法。 计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象 是巨量的数据库，因此空间和对间的复杂度是非常重要的问题。对于描述型的 分类任务，模型描述越简洁越受欢迎。例如，采用规则表示的分类器构造法就 更有用，而神经网络方法产生的结果就难以理解。 另外，分类的效果一般与数据的特点有关：有的数据噪声大，有的缺值， 有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续 值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。 1 1 3 归纳学习 归纳学习是符号学习中研究得最为广泛的一种方法。它着眼于从一组无次 6 序、无规则的事例中，找出蕴涵规律，事例一般是基于属性理论的，由特定的 属性值得到问题的某个结论。给定关于某个概念的一系列已知的正例和反例， 其任务是从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立 新的规则，发现新的理论。它的一般的操作是泛化( g e n e r a l i z a t i o n ) 和特化 ( s p e c i a l i z a t i o n ) 。泛化用来扩展一假设的语义信息，以使其能够包含更多的正 例，应用于更多的情况。特化是泛化的相反操作，用于限制概念描述的应用范 围。单个概念的归纳学习的一个通用定义是： ( 1 ) 给定由全体实例组成的一个实例空间，每个实例具有某些属性。 ( 2 ) 给定一个描述语言，该语言的描述能力包括每一个实例( 通过描述该实 例的属性来实现) 及描述某些实例集，称为概念。 ( 3 ) 每次学习时，由实例空间抽出某些实例，称这些实例构成的集合为正 例集。再由实例空间抽出另外一些实例，称这些实例为反例集。 ( 4 ) 如果能够在有限步内找到一个概念a ，它完全包含正例集，并且与反 例集的交集为空，则a 就是所要学习的单个概念，学习成功：否则，学习失 败。 ( 5 ) 如果存在一个确定的算法，使得对于任意给定的正例集和反例集，学 习都是成功的，则称该实例空间在该语言表示下是可学习的。 在学习中可能在有限步内并不能只找到一个单一的概念与所有的正例和反 例相一致，所找到的可能是一个概念的集合，那么我们就必须从这个概念的集 合当中选取一个概念作为我们所要学习的概念。如何在这个概念集中选取单个 概念，就需要我们的一定的先验知识。这个先验知识就是所谓的偏置( b i a s ) 。所 谓偏置是指学习中除去正例和反例之外所有影响假设生成与选择的因素。每个 学习算法当中都包含偏置。例如在表示方面，用什么语言来表达假设，用什么 语言来表达实例、用什么方法在不同的表达方法之间转换，在假设形成过程当 中，用什么方法形成假设、假设形成之后如何对它进行修改、如何对噪音与丢 失的数据进行处理等等方面都可以叫做偏置。并且因为假设空间过大，偏置能 够减小搜索空间，没有任何偏置的学习算法是不可行的。有两种偏置，一种是 绝对偏置( a b s o l u t eb i a s ) ，它是将假设局限在假设空间的一个小的子集：另外一 种是选择偏置( p r e f e r e n c eb i a s ) ，它是在一组假设中选择一个。 1 1 4 决策树 决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无 规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递归方 式，在决策树的内部节点进行属性值的比较( 选择子) 并根据不同的属性值判断 从该节点向下的分支，在决策树的叶节点得到结论。所以从根到叶节点的一条 路径就对应着一条合取规则( 公式) ，整棵决策树就对应着一组表达式规则。基 于决策树的学习算法的一个最大的优点就是它在学习过程中不需要使用者了解 很多的背景知识( 这同时也是它最大的缺点) ，只要训练例子能够用属性一结论 式的方式表达出来，就能使用该算法来学习。 一棵决策树的内部节点是属性或属性的集合，叶节点是所要学习划分的 类，内部节点的属性称为测试属性。当经过一批训练实例集的训练产生一棵决 策树时，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树 对实例进行分类的时候，由树根开始对该对象的属性逐渐测试其值，并且顺着 分支向下走，直至到达某个叶节点，此叶节点代表的类即为该对象所处的类。 决策树的构建是一种自上而下、分而治之的归纳过程，本质是贪心算法。 从根节点开始，对每个非叶节点，找出其对应样本集中的一个属性( 亦称测试属 性) 对样本集进行测试，根据不同的测试结果将训练样本集划分成若干个子样本 集，每个子样本集构成一个新叶节点，对新叶节点再重复上述划分过程，这样 不断循环，直至达到特定的终止条件。其中，测试属性的选择和如何划分样本 集是构建决策树的关键环节。不同的决策树算法在此使用的技术不尽相同。 在实际应用中，由于训练样本集的规模一般较大，相应生成的决策树的分 枝和层数也较多，另外，训练样本集中存在的异常和噪声也会导致一些异常分 枝的产生，这就需要对生成好的决策树进行剪枝。剪枝按其实施的时间可分为 预剪枝和后剪枝。预剪枝是在决策树的构建过程中对每一个预生成分枝的节点 进行判断，若可能生成异常分枝，则停止此分枝的生成，即将此预生成的分枝 剪去；后剪枝则是待决策树完全生成后运用特定的剪枝算法对整棵树进行修 剪。有的树剪枝的过程同时也是对决策树分类准确率的检测过程- 树剪枝的目的 是生成一棵分类准确率较高而规模相对较小，即分枝和层数较少的决策树。 本文将在第三章中对典型的决策树算法i d 3 作了详细的阐述，并介绍其改 进算法c 4 5 的剪枝策略。 1 2 决策树构造算法概述 决策树归纳学习算法是多种学习算法中最简单却最成功、最广泛应用的方 法之一。在各种决策树学习算法当中，最早、最有影响力的是q u i n l a n 于1 9 7 9 年在h u n t 的概念学习系统c l s ( c o n c e p tl e a r n i n gs y s t e m ) f 6 】基础上发展提出来的 以信息熵的下降速度作为选择测试属性的标准的i d 3 算法【m 】。i d 3 算法是基于 信息熵的决策树分类方法，根据属性集的取值选择实例的类别，它以信息熵作 为目标评价函数，采用自顶向下不可返回的策略，搜索全部空间的一部分，它 确保决策树建立最简单，每次所做的测试数据最少。 i d 3 算法构造的决策树平均深度最小，分类速度较快。但i d 3 算法也存在 自身的缺陷i l 7 ”，3 ”，自i d 3 出现以后，研究人员围绕该算法展开了大量的研 究，提出了许多富有成效的改进、优化算法。其工作主要集中在如下几个方 面：1 ) 扩充决策树属性的取值范围及改进选择分离属性的选择；2 ) 提高决策树 的构造效率，削减数据库遍历次数，减少i o 操作：3 ) 优化决策树，简化决策 树输出；4 ) 扩充决策树，形成决策图；5 ) 将遗传算法、神经网络技术引入决策 树算法。 q u i n l a n 于1 9 9 3 年提出的c 4 5 算法副是对i d 3 算法的改进，该算法继承了 i d 3 的全部优点，它是一种归纳学习算法，先从所有的事例中选取一部分构造 决策树，再用的剩下的事例测试决策树并对它进行调整。它不仅可以处理连续 值类型的属性，还可以对属性的取值集合进行等价类划分，划分在同一类的属 性值判断时走向同一分支。但c 4 5 难以获得全局的最优解。 肖勇等人针对c 4 5 的不足，提出了利用遗传算法来构造决策树的方法1 4 。 利用遗传算法构造决策树的过程，就是利用遗传算法从上一代决策树群体经过 遗传算子的操作产生下一代群体演化直到满足终止条件。该算法构造出的决策 树在正确性、节点数和平均深度等方面均比c 4 5 有所提高，但这种遗传算法搜 索过程比较费时。 f u k u d a 等人提出用二维分离标准构造决策树的算法翻，该算法产生的决策 树有较高的分类精度，但是，该算法未考虑训练集规模的变化，并且，所构造 的决策树没有采用一维分离标准构造的决策树直观。 在决策树学习领域中，数据库容量通常比可用主存大得多。由大型数据库 构造决策树的早期策略包括对连续属性离散化，在每个节点上对数据选样。然 而，这些做法仍然假定训练集可以放在主存。一种替代的方法是：首先，将样 本划分成子集，使得每个子集可以放在内存；然后，由每个子集构造一棵决策 树；最后，输出的分类法将由每个子集得到的分类法在一起。尽管该方法可以 用于大数据集的分类，其分类的准确性不如一次使用所有的数据方法高。 现在已有了一些决策树方法，它们强调可伸缩性。由非常大的训练集进行 决策树归纳的算法包括s l i q i l o l 和s p r i n t l 2 2 】；它们都能处理分类属性和连续值 属性。这两种算法都使用了预排序技术，对非常太而不能放入内存的数据集进 行预排序。当s l i q 和s p r i n t 处理的驻留磁盘的数据太大，不能一次装入内 存时，s l i q 的可伸缩性受限于它所使用的常驻内存了数据结构。s p r i n t 消除 了所有的限制，但仍然需要使用与训练集大小成比例的散列树。随着训练集的 增长，这可能变得代价昂贵。 而g e h r k ej 等人提出了一种可伸缩的基于大型数据集上快速构造决策树的 框架“雨林”( r a i n f o r e s t ) pj ，该方法适合于有大量可用的内存的情况( 因算法本 身需要占用一定量的内存空间) ，它根据可用主存空间的大小，按照比例扩充决 策树，能应用于任意的决策树归纳算法，且性能有较大的改善。它能较好地适 应训练集规模的变化。据称，“雨林”的速度超过s p r i n t 。 以i d 3 为代表的决策树构造算法都把研究的重点放在属性的选择上，而洪 9 家荣等人从事例学习最优化的角度分析了决策树归纳学习的优化原则，提出了 一种新的基于概率的决策树构造算法p i d l 3 5 】，它在树的扩展过程中，利用值聚 类来进行分支合并，以减少决策树的叶子数目，改变了i d 3 只是试图减少树的 深度的现状。该算法在决策树的规模和精度上优于i d 3 ，但在训练速度上比 i d 3 稍慢，并且其产生的决策树上的某些属性可能重复使用。 上述各种算法的决策树调整阶段是在决策树建树阶段完成后进行的，实践 中大量的节点在调整阶段被删除，即它们浪费了大量时间去建立将被删除的节 点及调整处理。对此，r a s t o g i 等人提出了一种将建树和树的调整阶段集成在一 起的p u b l i c 算法【2 ”，其思想是在决策树建立阶段，计算每个节点相关的目标 函数值，估计该节点在将来调整阶段是否被删除。如果该节点将被删除，则不 对该节点进行扩张，否则，扩展该节点。p u b l i c 算法由于不需要对即将删除 的节点进行扩张，减少了大量i 0 操作，节省运行空间，提高决策树的构造效 率。 另外，也有人将粗糙集合方法或神经网络方法应用到决策树分类上。赵卫 东等人将粗糙集理论应用于决策树的构造过程，提出了一种利用粗糙集合理论 对决策树进行优化的算法】；苗夺谦等人提出了采用粗糙集构造多变量决策树 的方法口”。神经网络是目前公认的高精度分类器，张朝晖等人提出了利用神经 网络学习发现分类规则的方法【4 到。周志华等人提出了一种构造性混合决策树学 习方法c h d t 4 6 1 ，该方法用符号学习来进行定性分析，用神经网络学习进行后 续的定量分析，在一定程度上模拟了人类的思维过程。 13 本文的主要内容 i d 3 归纳学习算法往往偏向于选择属性取值较多的属性，而属性值较多的 属性却不总是最优的属性。受到更多攻击的是i d 3 学习简单的逻辑表达式的能 力较差。 本论文针对i d 3 学习逻辑表达式方面的不足，根据逻辑蕴含的规则，提出 了- 4 十对i d 3 学习到的决策树进行简化的算法b 0 1 r 。b o i r 以i d 3 算法构造的 决策树为基础，先序遍历由i d 3 构造出来的决策树的各个节点，并对其子树进 行比较，如果各子树的根属性都相同而且存在某些相应的分支对于各子树完全 相同，则改变决策树中相应属性的层次关系并把相同的分支分别合并起来。对 于逻辑表达式的学习，b o i r 弥补了i d 3 的不足，能够得n t e , 较理想的效果， 使决策树大大简化。运用b o i r ，不仅可以减少节点数目，而且树的深度变的 更小。论文实现了b o i r 算法并利用f a m n 家族数据集( 适合于对逻辑表达的学 习能力进行测试的数据集) 对b o i r 进行t n 试，实验结果表明b o i r 学习到的 结果逼近理想的概念。 14 本文的组织 本文首先介绍决策树的相关知识，示例学习的基本理论及决策树优化的目 标、然后系统地介绍经典的i d 3 算法及其优化算法c 4 5 ，最后提出了一种基于 逻辑蕴含规则的决策树简化算法。全文的具体组织如下： 第一章绪论。介绍了与本文研究有关的背景知识、决策树的构造方法概 述、主要研究内容以及全文的组织。 第二章示例学习的理论基础与决策树学习的最优化。介绍了示例学习的 概念，示例学习的理论基础扩张矩阵理论，并结合此理论介绍了决策树归 纳学习中的最优化问题。 第三章i d 3 算法研究与c 4 5 算法简介。主要研究i d 3 算法，介绍i d 3 的 理论背景、基本原理、算法描述并按照建树的规则，通过使用i d 3 算法学习得 到一裸决策树。同时对i d 3 算法的优缺点进行综合评价，简单介绍c 4 5 算法， 最后还给出决策树准确率的判定方法与判定参数。 第四章决策树简化方法研究。首先对决策树简化方法作概述，然后重点 针对i d 3 学习逻辑表达方面的缺陷，提出并实现一种基于逻辑蕴含规则的决策 树简化算法b o i r ，最后以f a m n 家族数据集对该算法进行测试并进行综合评 价。 第五章结束语。对本文的工作进行总结，并对决策树的简化进行展望。 第二章示例学习的理论基础与决策树学习的最优化 2 1 示例学习 学习是人类获得智慧的基本途径，机器学习是使任何计算机系统具有智能 的主要手段。示例学习( 1 e a r n i n gf r o me x a m p l e s ) 是机器学习较为成熟的重要分 支。示例学习是从某一概念的已知的正例集合和反例集合中归纳产生出描述所 有正例并排除所有反例的该概念的一般规则。因此，示例学习也称作概念获取 f c o n c e p ta c q u i s i t i o n ) 。由于知识获取己公认为专家系统发展的瓶颈问题，示例学 习获得更加广泛的重视和深八的研究。在理论研究方面，一些学习问题的计算 复杂性得到了分析和证明，例如，洪家荣证明了示例学习中的一些问题是n p 难题【8 】，并且提出了示例学习的扩张矩阵理论( e x t e n s i o nm a t r i xt h e o r y ) p 。在 学习算法研究方面，一些示例学习系统相继问世，其中当前在国际上最有影响 的系统有q u i n l a n 的c 4 5 【1 8 1 及洪家荣的a q l 5 5 j 5 1 。 按照知识表示形式示例学习主要分为两大类：产生式规则表示形式和决策 树表示形式。学习系统a q l 5 是产生式规则归纳的代表，其特点是分类精度 高，知识表达能力强，适合于专家系统的知识自动获取，因而在专家系统领域 引起更大的关注。但是，a q l 5 的训练速度慢，算法复杂不易推广。另外， a q l 5 的星算法只是局部贪婪算法，因此不仅效率低，而且得到的公式也不优 化。i d 3 【l7 l 是决策树归纳的代表，它的优点是训练和分类的速度都很快，适应 大规模的学习问题：缺点是分类精度低，知识表达能力不强。 2 2 扩张矩阵理论的基本概念3 4 设e = d lx d 。是n 维有穷向量空间，其中d ，是有穷离散符号集，为e 的第f 个属性斗的值域。e 中的元素e = ( q ，v 。) 叫做例子，其中v 。p 。设 j d e 和n e 是e 的两个子集，为区分起见，分别叫做正例集和反例集。 定义1 选择子( s e l e c t o r ) 是形如k ，= a ，】或n ，b ，】的关系语句，其中 m ，d ，】，【曰，sd s 】并且规定i x ，b ，】= i x = d ，一b j 】a 公式( 或项) 或复合是 一个选择子或几个选择予的合取范式( c n f ，c o n j u n c t i v en o r m a lf o r m 、，即 。 i x ，= a ， ，其中j 1 ， ；规则是公式的析取式，即l ，其中l ，为公 式。一个例子p = ( ”l ，- ，v 。) 满足选择子 x ，= a j 】( 或【x ，b j 】) 当且仅当1 ：，是4 中的元素( 或v j 不是目中的元素) ，即v ，a ，( 或v ，仨b j ) ：p 满足一个公式当且 仅当它满足该公式的每一个选择子：e 满足一条规则当且仅当e 满足该规则的 至少一个公式。 例子满足选择子( 公式、规则) 也称作选择子( 公式、规则) 覆盖该例子。 定义2 选择子( 公式、规则) 在反例e 背景下覆盖正例e + 当且仅当它覆盖该 _ _ f 例而不覆盖该反例：选择子( 公式、规则) 在反例集n e 背景下覆盖一正例，当 且仅当它在n e 中的每一个反例背景下覆盖该正例；一条规则叫做正例集 p e 在 反例集n e 背景下的一个覆盖当且仅当船中的任何一个工f 例都在反例集背景下 被该规则中的一个公式所覆盖。 由此可以看出，示例学习就是寻求在反例集背景下覆盖正例集的规则。 定理1 已知一正例p + = ( v ? ，v ：) ，反例集n e = e