（计算机软件与理论专业论文）基于粗糙集的决策树算法研究与改进.pdf

哈尔滨工程大学硕士学位论文 摘要 数据挖掘是指在数据中发现模式、知识或数据间的关系。分类挖掘是数 据挖掘中最活跃、最成熟的研究方向，分类算法又是其中涉及到的关键技术。 在各种分类算法中，决策树方法有更易被用户理解、更适合大训练数据集以 及不需要处理训练数据集以外的信息等优点，已经得到广泛的研究和应用。 但基于信息论的传统的决策树技术也存在缺点：偏向于选择属性值较多的属 性、对样本质量依赖性强和被限制在每个结点上只检验单个属性等。 为此，本文把粗糙集技术应用到决策树算法中。粗糙集是研究不精确、 不确定知识的工具，具有很强的知识获取能力。在研究的过程中，发现以粗 糙集为基础的区分价值属性选择判据优于传统的信息熵，可以降低决策树的 规模，但是需要两两比较所有对象，时间性能不好。据此，本文提出了h 重要和l 重要两个概念，减少了比较次数，降低了时间开销。为了进一步降 低树的规模，克服单变量决策树没有综合考虑属性间的联系等不足，本文用 多变量构造算法结合h 重要和l 重要两个概念重新构造决策树。以h 重要 集合中的部分属性作为初始的检验属性，对基于区分价值的决策树算法进行 了进一步的改进。 最后，利用实验对改进的基于区分价值的决策树算法和基于区分价值的 多变量决策树算法进行对比分析。实验结果表明，前者降低了算法的时间开 销，但是却并没有牺牲决策树分类的准确性，而后者构造的决策树在规模上 得到了进一步的缩减，也就是构造了更为简单的决策树，也不失分类的准确 性。 关键词：决策树；粗糙集；区分价值；h 重要；l 重要 哈尔滨丁程大学硕士学位论文 叠i 宣；罩葺葺i 宣昌i 暑皇l _ _ | 圈昌嗣一1 瞄i 每i i 嗣i _ 薯宣皇_ | 嗣昌置_ 岛宣暑i 宣盲薯葺置_ a b s t r a c t d a t am i n i n gi sam e t h o du s e dt of i n dm o d e ，k n o w l e d g eo rr e l a t i o n s h i p b e t w e e nd a t a c l a s s i f i e dd a t am i n i n gi st h em o s ta c t i v e ，m o s tm a t u r er e s e a r c h d i r l ；c t i o no fd a t am i n i n g ，a n dc l a s s i f i c a t i o na l g o r i t h mi sa r li m p o r t a n tt e c h n o l o g y 1 1 1a l lc l a s s i f i c a t i o na l g o r i t h m s ，d e c i s i o nt r e em e t h o dh a sm a n ya d v a n t a g e s ，s u c h a sc a l lb ee a s i l yc o m p r e h e n d e db yh u m a n s ，s u i t e df o rl a r g et r a i n i n gs e ta n dd on o t r e q u i r ea d d i t i o n a li n f o r m a t i o nb e s i d e st h a ta l r e a d ye x i s t e di nt r a i n i n gd a t a , a n d h a sb e e nw i d e l ys t u d i e da n du s e d i n f o r m a t i o nt h e o r yb a s e dt r a d i t i o n a ld e c i s i o n t r e eh a sm a n yd i s a d v a n t a g e s ，s u c ha sp r e f e r r i n gt oc h o o s et h ea t t r i b u t ew h i c hh a s m o r ev a l u e s ，h a ss t r o n gd e p e n d e n c ew i t ht r a i n i n gs e tq u a l i t y , a n di sr e s t r i c t e dt o c h e e ks i n g l ea t t r i b u t ei ne a c hn o d e t h e r e f o r e ，i nt h i st h e s i s ，r o u g hs e tt e c h n i q u ei si n t r o d u c e d r o u g hs e ti st h e t o o lu s e dt os t u d yi m p r e c i s ea n d u n c e r t a i nk n o w l e d g e ，a n dh a sas t r o n g k n o w l e d g ea c q u i s i t i o nc a p a c i t y d u r i n gt h es t u d y , r o u g h s e tb a s e da t t r i b u t e c h o o s i n g c r i t e r i o nd i s c e r n v a l u ei s f o u n dt h a ti ti sm u c hb e t t e rt h a nt h e t r a d i t i o n a lo n e ，t h ed i m e n s i o no fd e c i s i o nt r e ec a nb er e d u c e d ，b u ti t h a st o c o m p a r ea l lo b j e c t s ，s oh a sah i g h e rt i m ec o m p l e x i t y a c c o r d i n g l y , i nt h i st h e s i s ， h i m p i o r t a n ta n dl i m p o r t a n tc o n c e p t sa l eu s e dt or e d u c et i m ec o m p l e x i t y f o r r e d u c i n gt h ed i m e n s i o no fd e c i s i o nt r e ef u r t h e r , o v e r c o m i n gt h ed i s a d v a n t a g eo f s i n g l ev a r i a b l ed e c i s i o nt r e e ，s u c ha sd on o tc o n s i d e rt h er e l a t i o no na t t r i b u t e s ，a n d m u l t i v a r i a b l ea l g o r i t h ma n dh i m p o r t a n t ，l i m p o r t a n tc o n c e p t s a r eu s e dt o r e b u i l dd e c i s i o nt r e e p a r to fa t t r i b u t ei nh - i m p o r t a n ts e ti sc h o o s e da so r i g i n a l c h e c k i n ga t t r i b u t e ，a n dt h en e w a l g o r i t h mi si m p r o v e dm u c h f u r t h e r f i n a l l y , t h ee x p e r i m e n ti sp e r f o r m e dw i t hi m p r o v e dd i s c e r nv a l u eb a s e d d e c i s i o nt r e ea n dd i s c e mv a l u eb a s e dm u l t i - v a r i a b l ed e c i s i o nt r e ea l g o r i t h m f o rc o m p a r i n ga n da n a l y s i s t h er e s u l to ft h ee x p e r i m e n ts h o w st h a tt h ef i r s t a l g o r i t h mm e n t i o n e db e f o r eh a sl o w e rt i m ec o m p l e x i t y , a n di t ls t i l l h a st h es a m e 哈尔滨工程大学硕士学位论文 j j 目胃皇i i i 宣；宣m i m lm i 暑i 置；叠暑暑i 叠暑宣i i i i 宣暑 v e r a c i t yo fd e c i s i o nt r e ec l a s s i f i c a t i o n , a n dt h es e c o n da l g o r i t h mh a st h es m a l l e r d i m e n s i o n ，j u s ta st h es i m p l e rd e c i s i o nt r e e ，a n dt h ev e r a c i t yo fc l a s s i f i c a t i o ni s a l m o s tt h es a m e k e y w o r d s ：d e c i s i o nt r e e ；r o u g hs e t ；d i s c e r nv a l u e ；h i m p o r t a n t ；l - i m p o r t a n t 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均己在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：柔窭 日期：珈多年1 月z 口日 哈尔滨工程大学硕士学位论文 1 1 课题背景 第1 章绪论 随着计算机技术的发展，各行各业都开始采用计算机及相应的信息技术 进行管理和运营，这使得企业生成、收集、存贮和处理数据的能力大大提高， 数据量与日俱增。企业数据实际上是企业的经验积累，当其积累到一定程度 时，必然会反映出规律性的东西；对企业来说，企业拥有的数据本身就相当 于一个宝库。在这样的背景下，人们迫切需要新一代的计算技术和工具来开 采数据库中蕴藏的宝藏，使其成为有用的知识，指导企业的技术决策和经营 决策，使企业在竞争中立于不败之地。从另外一个角度，上世纪9 0 年代以来， 计算机以及信息技术的飞速发展，涌现出许多新兴技术和新的概念，如性能 更高的计算机、因特网( i n t e m e t ) 、操作系统、数据仓库( d a t a w a r e h o u s e ) 和神经网络等等。在市场需求和技术力量这两个因素都具备的环境下，数据 挖掘技术( 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 ，k d d ) 数据库知识发现的概念 和技术就应运而生了。 数据挖掘( d a t am i n i n g ) 旨在从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用的信 息和知识。还有很多和这一术语相近似的术语，如从数据库中发现知识、数 据分析、数据融合( d a t af u s i o n ) 以及决策支持等。目前对数据挖掘的研究 主要集中在分类、聚类、关联规则挖掘、序列模式发现、异常和趋势发现等 方面，其中分类挖掘在商业等领域中的成功应用使它成为数据挖掘中最活跃、 最成熟的研究方向，分类算法是数据挖掘中最重要的技术之一，是数据挖掘 中的一个重要课题。分类技术有很多，如决策树、贝叶斯网络、神经网络、 遗传算法和k - 最近邻分类等。决策树学习方法是目前重点研究的方向。 哈尔滨工程大学硕士学位论文 1 2 国内外研究历史与现状 决策树研究历史与现状 决策树起源于概念学习系统( c o n c e p tl e a r n i n gs y s t e m ，c l s ) ，其思路 是找出最有分辨力的属性，把数据库划分为许多子集( 对应树的一个分枝) ， 构成一个分枝过程，然后对每一个子集递归调用分枝过程，直到所有子集包 含同一类型的数据，最后得到的决策树能对新的例子进行分类。c l s 的不足 是它处理的学习问题不能太大。 q u i n l a n 于1 9 8 6 年提出基于信息熵的下降速度作为选取测试属性的i d 3 算法”1 。针对i d 3 偏向于选择属性值较多的不足，, q u i n l a n 于1 9 9 3 年提出了 c 4 5 算法。该算法采用了信息增益率作为属性的选择标准，它继承了i d 3 算 法的全部优点并对其进行了改进。c 4 5 可分成两个阶段：首先，根据信息熵 最大的标准选择某个属性对训练数据集进行划分，递归调用直到每个划分中 的所有例子属于同一个类；然后，要对建立的树进行剪枝，即剪去建立在噪 音数据之上的分支悟”。c 4 5 关键的地方为用于决策的属性的选择策略，同样 使用i d 3 的计算熵的方法。但是计算信息熵率的时间复杂度相对来说比较高， 同时信息熵会造成不合适划分，如出现频率较高的属性和仅有单值的属性更 有可能被选为决策属性。 i b ma l m a d e n 研究中心开发出的s l i q 分类方法和j o h ns h a r e r 提出的 s p r i n t 算法使用了不同的数据机构，具有良好的并行性和可伸缩性，解决 了i d 3 的不能处理不精确信息的问题，还有不能应用于大数据量的情况。 k m i c h e l i n e 等人提出了m e dg e n 算法。它在c 4 5 算法的思想上增加了 建立决策树前的数据压缩处理。采用属性归约方法和阈值控制简化了决策树 的建立过程，省去了决策树建立后的剪枝和优化过程，提高了效率。 此外，b r i e m a a 等人提出了c a r t 方法，它生成的是一棵二叉树，具有 一较高的分类效率。 国内对决策树算法的研究： 洪家荣等在分枝属性的选择上仍采用基于信息增益率的方法，但在树的 2 哈尔滨工程大学硕士学位论文 宣暑宣i 眚皇宣宣置暑| 置昌一i i | 皇i i 昌宣 扩展过程中，采用基于条件概率的属性聚类的方法合并树的分枝- s ，。 。刘小虎、李生等学者在选择一个新属性时，并不仅仅计算该属性引起的 信息增益，而是同时考虑树的两层节点，即选择该属性后继续选择该属性带 来的信息增益阳，。 钟鸣、陈文伟等为克服训练样例中正、反例的比例对互信息的影响，提 出了i b l e 算法，该算法每次分枝时选一组重要属性作为决策树的节点，预 测结果好于i d 3 算法盯一。 苗夺谦等结合了粗糙集技术，解决了多变量检验中属性的选择问题。考 虑了条件属性之间的关系，定义了两个等价关系相对泛化的概念，并将它用 于解决多变量检验的构造问题。 1 2 2 粗糙集研究历史与现状 粗糙集，( r o u g hs e t ) 理论是一种研究不精确、不确定性知识的工具， 由波兰科学家z p a w l a k 在1 9 8 2 年首先提出。粗糙集理论是离散数据推理的 一种新方法。集合论是粗糙集的数学基础。粗糙集理论作为一种处理不完备 信息的有力工具，它可以不需要任何辅助信息，如统计学中的概率分布、模 糊集理论中的隶属度等，仅依据数据本身提供的信息就能够在保留关键信息 的前提下，对数据进行化简并求得知识的最小表达，从而建立决策规则，发 现给定的数据集中隐含的知识。 z i a r k o 教授在1 9 9 3 年提出了可变精度粗糙集( v p r s ) 模型。使粗糙集 可以处理一些分类是不明确的、对象不是已知的情况。 r i c h a r dj e n s e n 等在模糊粗糙集模型的基础上提出了基于蚁群殖民地最 优化的特征选择机制以解决寻找最小特征集的问题憎1 。 米据生、吴伟志提出了基于可变精度粗糙集模型的知识约简方法，并给 出了基于v p r s 的夕下分布约简及上分布约简的概念及等价定义“州，从而 拓展了传统粗糙集理论的模型。 菅利荣、达庆利根据可变精度粗糙集理论提出了利用嵌套的等价关系集 构造基于不同置信阈值、不同级别分类质量y 的分层知识粒度及其相应的 算法，。 3 哈尔滨工程大学硕+ 学位论文 于达仁等人针对粗糙集理论应用于电厂与电力系统数据挖掘中存在的连 续属性离散化问题，提出了基于模糊聚类的离散化方法l t ”。 张建军等人提出了基于决策表属性重要性的连续属性离散化算法“”，该 算法可以大大地减少计算量，提高数据离散化的精度。 1 3 分类综述 1 3 1 分类的定义 分类是一类重要的数据挖掘问题，也是数据挖掘领域的热点之一。 分类是在已有数据的基础上得到一个分类函数或构造出一个分类模型， 即通常所说的分类器( c l a s s i f i e r ) 。该函数或模型能够把数据库中的数据纪录 映射到给定类别中的某一个，从而可以应用于数据预测。要构造分类器，需 要有一个训练数据集作为输入。训练数据集( t r a i n i n gd a t as e t ) 由一组数据 库纪录或元组构成，每个纪录是一个由有关字段值组成的特征向量，这些字 段称做属性( a t t r i b u t e ) ，把用于分类的属性叫做标签( l a b e l ) ，标签属性也 就是训练数据集的类别标记。用一个具体的样本形式可以表示为( k ，k ， k ；c ) ，其中表示字段值，c 表示类别“”。 训练数据集是构造分类器的基础。训练数据集是包含一些属性的一个数 据库表，其中的一个属性被制定为分类标签。标签属性的类型必须是离散的， 且标签属性的可能值的数目越少越好( 最好是两或三个值) 。标签值的数目越 少，构造出来的分类器的错误率越低。 分类是一个两步过程：首先，在已知训练数据集上，根据属性特征，为 每一种类别找到一个合理的描述或模型，即分类规则，其次根据规则对新数 据进行分类。所以，分类又称为有指导的学习。 1 3 2 分类的主要算法 对于分类问题，现在已经有不同的领域的几种算法柬实现。根据不同领 域的不同技术主要有：决策树算法、贝叶斯分类算法、神经网络分类算法、 4 哈尔滨工程大学硕士学位论文 一i 一一 一i ei,i i i 薯暑暑宣置l 遗传算法和粗糙集分类算法“。 1 决策树算法 决策树也称为判定树。在决策树方法中，首先从训练数据集中构造决策 树，这是一种有指导的学习方法。该方法先根据训练数据集数据形成决策树。 如果该树不能对所有对象给出正确的分类，那么选择一些特殊数据加入到训 练数据集中，重复该过程直到形成正确的决策集。决策树代表着决策集的树 形结构。最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性， 该分枝对应该属性的某一可能值。本质上决策树是通过一系列规则对数据进 行分类的过程。 2 贝叶斯分类算法 贝叶斯分类是统计学分类方法，可以预测类成员关系的可能性，如给定 样本属于一个特定类的概率。贝叶斯分类假设一个属性值对给定类的影响独 立于其他属性值，即属性值条件相互独立，在属性间不存在依赖关系。与其 他分类算法相比，贝叶斯分类具有较小的出错率。 3 神经网络分类算法 神经网络是模拟人脑结构的数据模型，因此，神经网络是一个具有自我 学习能力的系统。神经网络是大量神经元的集体行为，并不是各单元行为的 简单相加，而表现出一般复杂非线性动态系统的特性。神经网络允许定性和 定量信号的数据融合，可以处理环境信息复杂、知识背景不清楚和推理规则 不明确的问题。 4 遗传算法 遗传算法是一个迭代过程。在每次迭代过程中都保留一组候选解。按其 解得优劣进行排序，并按某种指标从中选出一些解，利用一些遗传算子对其 进行运算，产生新一代的一组候选解，重复此过程，直至满足某种收敛条件。 遗传算法在优化计算和分类机器学习有着显著的作用。 5 粗糙集 粗糙集理论在数据中发现分类规则的基本思想就是将数据对象根据属性 的不同属性值分成相应的子集，然后对条件属性划分的子集与结论属性划分 的子集进行一系列的集合的上下近似运算，以生成各子类的判定规则。 哈尔滨工程大学硕士学位论文 1 4 研究内容及论文结构 本论文的主要研究内容有以下几点： ( 1 ) 对数据分类中的决策树技术和粗糙集合理论进行深入的研究。 ( 2 ) 对各种基于粗糙集的决策树进行了深入的研究。重点分析了谢志鹏 等人提出的基于粗糙集合理论的决策树生成算法。该算法已经被证明是优于 i d 3 算法的，而且避免了信息熵偏向选择属性值较多等不足。 ( 3 ) 针对基于区分价值的决策树算法时间开销过高的不足，提出了h 重要和l 重要的概念，降低了开销；接着提出了采用多变量方法构造决策树 的算法，在不改变分类准确性的前提下对其构造的决策树规模进行了更进一 步的改进。 ( 4 ) 给出一个实例( 气象模型数据) 对改进前后的算法进行了对比分析。 ( 5 ) 用u c i 数据库的3 个数据集进行实验，并比较分析了实验结果。 本论文内容组织结构如下： 第l 章分析了课题的研究背景以及国内外研究现状，并阐述了课题研究 的主要内容和论文的组织结构。 。 第2 章研究了决策树构建、剪枝技术以及现有的一些决策树构建算法。 第3 章研究了粗糙集相关的概念，并研究了粗糙集的化简方法。 第4 章研究了现有的基于明确区和区分价值的决策树算法，在现有的算 法基础上提出了新的想法，阐述了具体的改进方案。 第5 章通过具体实验来验证改进方案的优越性。 6 哈尔滨工程大学硕士学位论文 第2 章决策树方法 决策树算法是一种常用的数据挖掘算法，它是从机器学习领域中逐渐发 展起来的一种分类函数逼近方法。决策树学习的基本算法是贪心算法，采用 自顶向下的递归方式构造决策树。h u n t 等人于1 9 6 6 年提出的c l s 是最早的 决策树算法，以后的许多决策树算法都是对c l s 算法的改进或是由c l s 衍 生而来“m 。 2 1 决策树构建 先介绍通用的构建决策树算法： 输入：节点n ，训练数据集s ，分裂指标“圳( s p l i t t i n gi n d e x ，s 1 ) 输出：以节点n 为根的决策树 0 0 b e g i nm a k i n g _ t r e 宅( n ，s ，s i ) 0 1用数据集s 初始化根节点n ； 0 2在s 中对每个属性计算s i ，求解节点n 的分支方案； 0 3i f ( 节点n 满足分支条件) 0 4 选择最好的分支方案将s 分为s i 、s 2 ； 0 5 创建n 的子节点n 1 、n 2 ； 0 6 m a k i n g _ t r e e ( n i ，s 1 ，s i ) t 0 7 m a k i n g _ t r o 巳( n 2 ，s 2 ，s i ) ： 0 8e n d i f 0 9e n d 计算分裂指标是决策树构建算法的关键。不同的决策树算法采用不同的 分裂指标，比如i d 3 、c 4 5 使用的是信息增益，而c a r t 算法、s l i q 算法和 s p r i n t 算法使用g i n i 系数。 决策树算法的时间代价主要集中在树的构建阶段，因为对训练数据集的 多次遍历和扫描都在树的构建阶段进行，而在树的修剪阶段不用再次扫描数 7 哈尔滨工程大学硕士学位论文 据集，只用周游决策树。 2 2 决策树修剪 在树的构建阶段生成的决策树依赖于训练数据集，因此它可能存在对训 练数据集过度适应的问题。例如，训练数据集中的噪声数据和统计波动可能 会使决策树产生不必要的分支，从而导致在使用决策树模型对观察样本进行 分类时出错。其次，不同的决策树建树策略以及不同的分裂指标的选择也会 造成决策树生成时决策树过于庞大、决策树叶子结点过多等问题。为了避免 这些错误，需要对决策树进行修剪，除去过细的或不必要的分支。 2 2 1 剪枝方法 常见的剪枝方法有预剪枝和后剪枝两种“”。 1 预剪枝 预剪枝技术限制决策树的过度生长( 如c h a i d ，i d 3 家族的i d 3 、c 4 5 算法等) 。最直接的预剪枝方法是事先限制决策树的最大生长高度，使决策树 不能过度生长。这种停止标准一般能够取得比较好的效果。不过指定树高度 的方法要求用户对数据的取值分布有较为清晰的把握，而且需对参数值进行 反复尝试，否则无法给出一个较为合理的树高度阈值。更普遍的做法是采用 统计意义下的x 2 检验、信息增益等度量，评估每次节点分裂对系统性能的增 益。如果节点分裂的增益值小于预先给定的阈值，则不对该节点进行扩展。 如果在最好的情况下的扩展增益都小于阈值，即使有些节点的样本不属于同 一类，算法也可以终止。选取阈值是困难的，阈值较高可能导致决策树过于 简化，而较低可能对树的化简不够充分。 2 后剪枝 后剪枝技术是待决策树生成后再进行剪枝( 如c a r t 算法) 。后剪枝技 术允许决策树过度生长，然后根据一定的规则，剪去决策树中那些不具有一 般代表性的叶节点或分支。 后剪枝算法有自上而下和自下而上的两种剪枝策略。白下而上的算法首 2 哈尔滨工程大学硕士学位论文 先从最底层的内节点开始剪枝，剪去满足一定条件的内节点，在生成的新决 策树上递归调用这个算法，直到没有可以剪枝的节点为止。自上而下的算法 是从根节点开始向下逐个考虑节点的剪枝问题，只要节点满足剪枝的条件就 进行剪枝。 2 2 2 剪枝策略 目前，决策树修剪主要集中在后剪枝上，主要的策略有：代价复杂度剪 枝( c o s t c o m p l e x i t yp r u n i n g ，c c p ) 、基于错误的剪枝( e r r o r - b a s e dp r t m i n g ， e b p ) 、最小错误剪枝( m i n i m u me r r o rp r u n i n g ，m e p ) 和悲观错误剪枝 ( p e s s i m i s t i ce r r o rp r u n i n g ，p e p ) 11 9 1 。 1 c c p 剪枝 c c p 剪枝在c a r t 系统中应用。主要包括了两个步骤：( 1 ) 从初始决策 树开始根据参数生成一个节点数目递减的子树序列( 瓦，z ) ；( 2 ) 从生 成的子树序列中选择最佳决策树。 树丁的复杂度参数口可用下面的公式计算： 丝2 二墨婴 ( 2 1 ) i 工( ? ：) l _ 1 其中，r ( t ) 为在节点，的子树被裁剪后节点f 的误差；r ( 正) 为在节点t 的子树 没被裁剪时子树的误差；i 三( z ) i 为子树z 的叶子数。从瓦减去具有最小口值 的节点就得到z 。重复上述过程便生成了子树序列。 第二步是从子树序列中选取“最优 子树作为最终的分类模型。主要的 方法有重替代评估、测试样本评估和交叉验证评估。该剪枝策略的主要缺点 是时间复杂度高，生成的树过小，正确率较低。 2 p e p 剪枝 q u i n l a n 提出的p e p 剪枝策略是通过比较剪枝前后的错分样本数来判断 是否剪枝的。p e p 不需要独立的数据集来进行剪枝，所以容易产生错分样 本率，i ( ，) 的偏差，因此p e p 方法对误差估计引入了连续校正( c o n t i n u i t y c o r r e c t i o n ) 。在p e p 中，如果 e t ( f ) 5 e ( z ) + 。咒( p ( z ) ) ( 2 - 2 ) 9 哈尔滨工程大学硕七学位论文 成立，则z 应被裁剪。式( 2 2 ) 中p ( ，) = p ( f ) + 】，p ( z ) = p ( f ) + 等。其 中：p ( f ) 为节点f 处误差；f 为覆盖互的叶子；r 为子树z 的叶子数；n ( t ) 为 在节点t 处训练样本的数。 p e p 自顶向下遍历决策树，当内部节点满足式( 2 2 ) 时就进行剪枝。p e p 的收敛速度较快，最坏情况需要遍历每个节点。 3 m e p 剪枝 m e p 方法帔用了拉普拉斯概率估计来提高i d 3 方法在存在噪音数据中 的性能。m e p 方法自底向上，对每个非叶节点，首先计算误差e ( f ) ：然后 计算该节点每个分枝的误差e ( z ) ，并加权。如果e o ) v 两种情况，v 称作局部阈值。要确定彳的局部阈值， 首先对r 中a 属性值已知的样本进行快速排序，依次考察排序后的每对相邻 值的中间值，以及对应的划分条件a ，和彳 1 ，。假定样本中彳有七个不同 取值，则存在k 1 个中间值v ，分别对应k 1 个可能的信息增益率r a t i o v 。若 r a t i o v 。值最大，则v 就是彳的局部阈值，r a t i o v 就是a 的信息增益率。 生成决策树是c 4 5 算法的第一阶段，生成决策树后，c 4 5 算法采取剪 枝技术来纠正过度适合问题，即剪去树中不能提高预测准确率的分支。c 4 5 算法采用e b p 剪枝算法对决策树进行剪枝。 c 4 5 在很多方面比i d 3 更优越，但是也存在以下的一些不足之处：( 1 ) c 4 5 仍然采用信息熵原理，因此生成的决策树仍然是多叉树，不够简洁：( 2 ) 没有考虑属性间的联系，是一个单变量的决策树系统；( 3 ) 局部阈值的扫描 降低了算法的效率；( 4 ) 仅考虑决策树的错误率，未考虑树的节点、深度， 而树的节点个数代表了树的规模，树的平均深度对应着决策树的分类预测速 度。 哈尔滨工程大学硕士学位论文 3 c a r t 算法 c a r t 算法( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e ) 采用二分递归分割的技 术，每次都会将当前样本集分割为两个子样本集，使得决策树的每个非叶节 点都会有两个分枝。c a r t 选择具有最小g i n i 系数l 值的属性作为测试属性， g i n i 值越小，样本的不纯度的减小量越高，划分效果越好。 打 设样本集t 中包含珂个类，则g i n i ( t ) = 1 一p 2 ，其中p ，是t 中包含类 万。 。 的概率。若将丁划分为两个子集正和乃，则 7 ii 下l g i n i ( t i ，互) = 等g i n i ( t i ) + 割g i n i ( t z ) l i1 f 对候选属性集中的每一个属性，c a r t 算法计算在该属性上每种可能划 分的g i n i 系数，找到g i n i 系数最小的划分作为该属性上的最佳划分，然后比 较所有候选属性上最佳划分的西i l i 系数，选择最小划分g i n i 系数的属性作为 最后的测试属性。 c a r t 算法也是先建树后剪枝，但在具体实现上不同。由于二叉树可以 限制决策树的宽度，精确度往往比多叉树高。c a r t 算法采用二分递归划分， 在分支节点上进行布尔测试，判断条件为真的划归左分支，否则划归右分支， 最终形成一棵二叉决策树。对于连续属性彳，判断as v 是否成立( 同c 4 5 算法) ；对于离散属性彳，判断a s 是否成立，其中s 是属性a 所有取值的 子集，可用贪心算法或穷举法确定。 c a r t 算法在满足下述条件之一时停止建树：i j ：( 1 ) 所有叶节点中的样 本数为l 或者样本属于同一类；( 2 ) 决策树高度到达用户设置的阈值。 c a r t 算法在剪枝阶段采用代价复杂性剪枝策略，产生一个节点数目递减的 子树序列。采用该策略是基于以下两点：( 1 ) 复杂决策树对训练数据集有很 高的分类精度，但是当它应用于测试样本时，分类精度并不高；( 2 ) 理解和 解释具有大量叶节点的决策树是一个复杂的过程。决策树复杂度与分类精确 度之间的关系如图2 1 所示。图2 1 说明当决策树复杂度超过一定程度后，随 着复杂度的提高，测试集的分类精确度反而会降低。因此，建立的决策树不 宜太复杂，需进行剪枝。该剪枝算法依赖于复杂度参数t ；t ，它定义为每增加 一个叶节点所提高的代价复杂度。当增加一个节点引起的分类精确度变化量 l3 哈尔滨工程大学硕士学位论文 小于树复杂度变化的口倍时，则须剪去该节点。故建立一棵即能精确分类又 不过度适合的决策树的关键是求一个取值合适的1 2 值。 o 图2 1决策树复杂度和分类精确度之间的关系 c a r t 采用交叉验证法“7 来求解最优树。k 次迭代交叉验证评估首先将训 练数据集s 尽量平均地划分为k 份，分别表示为s ，s ，令s p ) = s s ，v l v k ，对s 和每一个s p 使用决策树的构建算法生成一系列最大树乙。和 硭：，对每一个a 值，令丁( 口) 和丁p ( 口) 分别表示瓦瓠和砭：的代价复杂度最小 的子树，然后将每一个丁p ( 口) 应用于s 一设s ，中类，的样本被误分为类f 的 样本个数为孵，那么类j 被误分为类f 的样本总数为： = 心 于是，丁( 口) 的交叉验证评估为： 犬“【丁( 口) 】- 吉c ( ilj ) n f ，。 t ， c a r t 算法的优点是它将模型的验证和通用树的发现嵌在了算法中。 c a r t 算法是这样实现该目标的：它先生成一棵复杂的树，再根据交叉验证 和测试数据集验证的结果对树进行剪枝，从而得到最优通用树。该树是根据 剪枝后不同版本的树在测试数据集上的性能得到的。使用交叉验证可以防止 过度拟合的问题，得到最适合未来数据的树。c a r t 算法对缺少数据的情况 也是比较健壮的。c a r t 算法的不足是不能对磁盘上的数据分类，也就是说 1 4 哈尔滨工程大学硕士学位论文 i t 它要求训练数据集驻留内存，不适合处理大规模数据。 4 s liq 算法 i d 3 、c 4 5 等算法适合处理规模较小的、可以全部放入内存的训练数据 集，但是当训练数据集大到不能一次全部放入内存时，这些算法的效率则会 明显降低。为了使算法不仅能够对内存中的数据进行分类，还能够将驻留在 磁盘上的数据集分类，提高算法的可伸缩性，使之适应大规模训练数据集的 处理，需要对传统的算法进行改进。一种处理方法是：首先将训练数据集划 分成若干子集，使得每一个子集都能完全放入主存，然后对每个子集分别构 造一棵决策树，再将这些树综合，得到最终决策树模型。该方法与传统算法 相比，减少了运行时间，但会降低决策树的分类准确率。 为此，i b m 研究人员提出了一种快速的、可伸缩的、适合处理大规模数 据的决策树分类算法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 算法要进行数据的预处理，对所有样本的每个数值属性进行预排 序。其过程如下：分解训练数据集，对附加在样本上的类标号建立一个类表， 包括两个字段：类标号和指向决策树叶节点的索引。对样本的每个属性建立 一个属性表，也包括两个字段：属性值和指向类表表项的索引。第i 类表表 项对应于第f 个训练数据集。类直方图附属在叶节点上，用来描述节点上某 个属性的类别分布。描述连续属性分布时，它由一组二元组 组成；描述离散属性分布时，它由一组三元组 组成。随着算法的执行，类直方图中的值不断更新。 s l i q 算法每次只需对一个属性表进行操作，其余的属性表可以暂时写回磁 盘，需要时再调回内存，因此内存里只需要存储类表和一个属性表，这样就 可以处理在磁盘上的数据集。 s l i q 算法在建树阶段，采用g i n i 系数值作为划分的标准。具体步骤n 引 如下： ( 1 ) 建立类表和各个属性表，并且进行预排序，即对每个连续属性的属 性表进行独立排序，以避免在每个节点都要给连续属性值重新排序： ( 2 ) 如果每个叶节点中的样本都能归成一类，则算法停止：否则转( 3 ) ； ( 3 ) 利用属性表寻找拥有最小g i n i 值的划分作为最佳划分方案。算法一 次只处理一张属性表( 假设对应于属性a ) ，从上往下每读一条记录，就根据 1 5 哈尔滨工程大学硕士学位论文 样本号关联到类表的相关记录，找到样本所在的叶节点，从而更新叶节点上 的类直方图，若彳是连续的，则还要根据a 的当前取值 ，计算对应于a v 的 g i n i 值；若彳是离散的，则在扫描完a 属性表后，用贪心算法或穷举法计算 最佳的s 。当扫描结束时，就可确定在各叶节点上依据属性彳进行划分的最 佳方案，各叶节点上的划分方案不一定相同。同理，当扫描完所有属性表时， 可确定当前树中所有叶节点的最佳划分； ( 4 ) 根据( 3 ) 步得到的最佳方案划分节点，判断为真的样本划归左孩 子节点，否则划归右孩子节点。这样，( 3 ) ( 4 ) 两步就构成了广度优先的生 成树策略； ( 5 ) 更新类表中的第二项，使之指向样本划分后所在的叶节点； ( 6 ) 转( 2 ) 。 s l i q 算法采取基于m d l ( 最小描述长度) 原则进行剪枝，即根据