（计算机应用技术专业论文）基于证据理论的决策森林的研究.pdf

r i 、! 。, i bl _ 、 擘 独创性声明 1 1 1 1 l l l l l l i l l l l 1 1 1 1 1 吣 、t17 8 8 5 5 0 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 虢牌嗍雹：2 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：肾导师签名：二垒垂堕监日期：二! 址 、，r 心 摘要 摘要 模式分类算法是数据挖掘研究的一个热点和难点问题，相关算法在许多领 域被广泛应用。由于在许多工程实践中，分类精度是评价算法性能的重要指标。 所以，高性能的集成方法近年来受到研究人员的广泛关注，多分类器集成就是 其中一种提高分类精度的有力武器。多分类器能提高精度的潜在原因之一在于： 它能综合不同分类器的信息，避免单一分类器可能存在的片面性。那么，如何 有效“融合”不同分类器的信息就成为其最为重要的关键技术。 本论文主要采用证据理论的方法对多决策树进行集成。证据理论已被证明 在信息融合、目标识别、知识推理等领域有着广泛的应用前景。同时，它作为 一种推理方法，在解决不确定性问题中具有显著的特点。本文所提方法的基本 思路是：首先对决策树输出的信息进行不确定表征，即对输出证据的基本概率 分配进行赋值；然后，利用证据组合规则对多决策树进行集成。 本文的主要研究工作概括如下。 首先，分析了数据挖掘、数据挖掘的分类器决策树的基本理论和方法， 并建立随机决策树和随机森林的模型，为研究基于多分类器融合的分类算法打 下基础。 其次，对证据理论的相关内容进行了系统的研究，为研究多分类器的融合 方法提供理论支持。 最后，研究多分类器融合理论，利用证据理论对多决策树输出的信息进行 融合，建立基于证据理论的决策森林的模型，并在u c i 标准数据集上进行仿真 实验，结果表明此方法是有效的，它能有效提高分类器的精度和泛化能力。 本文的工作对于集成学习的研究具有一定的参考价值。 关键词数据挖掘；决策树；证据理论；多分类器融合 。 北京工业大学工学硕士学位论文 i l - 、 i 奎 a b s t r a c t a b s t r a c t p a t t e r nc l a s s i f i c a t i o na l g o r i t h mi st h ed i f f i c u l tp o i n ta n dh o t s p o ti nd a t am i n i n g r e s e a r c h ，a n di th a sb e e nw i d e l yu s e di nm a n yf i e l d s c l a s s i f i c a t i o na c c u r a c yi sa l l i m p o r t a n t i n d e xo fe v a l u a t i n ga l g o r i t h mp e r f o r m a n c e s o ，h i g hp e r f o r m a n c e i n t e g r a t i o nm e t h o dh a sd r a w nw i d ea t t e n t i o nb yr e s e a r c h e r sa n dm u l t i p l ec l a s s i f i e r c o m b i n a t i o ni sc o n s i d e da sf lp o w e r f u lw e a p o nt oi m p r o v ec l a s s i f i c a t i o na c c u r a c y m u l t i - c l a s s i f i e rc o m b i n a t i o nc a na v o i d i n gt h eu n i l a t e r a l i s mf o rs i n g l ec l a s s i f i e ra n d i n t e g r a t e dt h ei n f o r m a t i o no f d i f f e r e n tc l a s s i f i e r s t h e n ，h o wt oe f f e c t i v e l yf u s e t h e s ec l a s s i f i e r si st h ek e y n l ep a p e rp r o p o s e sam e t h o do fc o m b i n i n gm u l t i p l ed i c i s i o nt r e e sb a s e do n e v i d e n c et h e o r y t h et h e o r yo fe v i d e n c ei sak i n do fu n c e r t a i n t yr e a s o n i n g ，w h i c h h a sp e r f e c tp e r f o r m a n c ei ns o l v i n gt h ep r o b l e mo fu n c e r t a i n t y a n di ti sb e i n gw i d e l y u s e di nd a t af u s i o na n dt a r g e tr e c o g n i t i o na n ds oo n t h eb a s i ci d e ao ft h i sp a p e ri s t h a t ：f i r s t l y , m a k i n gu n c e r t a i nc h a r a c t e r i z a t i o nf o rd i c i s i o nt r e e so u t p u ti n f o r m a t i o n ， n a m e l ya s s i g n m e n tb a s i cp r o b a b i l i t ya s s i g n m e n tf o ro u t p u te v i d e n c e ；a n dt h e n i n t e g r a t i n gm u l t i p l ed i c i s i o n t r e e sb ym e a n se v i d e n c ec o m b i n a t i o nr u l e s t h em a i nw o r ka n da c h i e v e m e n t so ft h i sp a p e ra r es u m m a r i z e da sf o l l o w s f i r s t l y , i ta n a l y z e st h eb a s i ct h e o r yo fd a t am i n i n ga n dd i c i s i o nt r e e ，a n db u i l d m o d e lo fr a n d o md e c i s i o na n dr a n d o md e c i s i o nf o r e s t t h i si st h eb a s ef o rr e s e a r c h o nc l a s s i f i c a t i o na r i t h m e t i cb a s e do nm u l t i p l ec l a s s i f i e r sf u s i o n s e c o n d l y , s y s t e m a t i cr e s e a r c ho nt h et h e o r yo fe v i d e n c ef o rm u l t i p l ec l a s s i f i e r s f u s i o n f i n a l l y , f u s em u l t i p l ed i c i s i o n t r e e so u t p u ti n f o r m a t i o nb ym e a n se v i d e n c e t h e o r y , a n db u i l dm o d e l i n go fd i c i s i o nf o r e s tb a s e do ne v i d e n c et h e o r y , e x p e r i m e n ti s t e s t e do nu c is t a n d a r dd a t a b a s e ，t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e d m e t h o d sa r ee f f e c t i v e ，a n di tc a ni m p r o v et h ep r e c i s i o na n de x t e n da b i l i t yo fs i n g l e c l a s s i f i e r t h ep a p e rh a sc e r t a i nr e f e r e n c ev a l u ef o re n s e m b l el e a r n i n g k e y w o r d sd a t am i n i n g ；d e c i s i o nt r e e ；t h et h e o r yo fe v i d e n c e ；m u l t i p l ec l a s s i f i e r s f u s i o n i i i 北京工业大学工学硕士学位论文 i v ； 0 目录 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 课题的研究背景与意义：l 1 2 论文研究内容一2 1 3 论文的结构一2 第2 章决策树理论与算法研究3 2 1 决策树算法简介- ：3 2 2 研究现状8 2 2 1 国内外研究进展8 2 2 2 决策树研究面临的主要问题1 0 2 3 随机决策树1 1 2 3 1 随机决策树产生背景1 1 2 3 2 树的深度的选择1 2 2 3 3 树的个数的选择1 2 2 3 4 实验及结果15 2 4 随机森林15 2 4 1 随机森林的算法1 5 2 4 2 相关实验结果一1 7 2 5 本章小结18 第3 章证据理论的研究- 1 9 3 1 证据理论1 9 3 1 1 证据理论基础1 9 3 1 2 证据理论的基本概念1 9 3 1 3 证据理论的合成规则2 3 3 2 模糊证据理论的研究2 6 3 2 1 模糊子集的概念：2 6 3 2 2 模糊集合与普通集合的相互转化2 6 3 3 本章小结2 7 第4 章多分类器融合2 9 4 1 多分类器融合的基本原理2 9 4 1 1 多分类器融合的必要性2 9 4 1 2 多分类器融合的体系结构3 0 4 1 3 多分类器融合的分类31 4 2 排序层的分类器融合3 3 4 2 1 最高序号法3 4 北京工业大学工学硕士学位论文 4 2 2b o r d a 计数法3 4 4 3 度量层的分类器融合3 4 4 3 1 模糊积分法3 4 4 3 2 神经网络方法3 5 4 4 决策层的分类器融合3 5 4 4 1 多数投票法3 5 4 4 2 贝叶斯方法。3 6 4 4 3d e m p s t e r - s h a f e r 方法3 6 4 5 本章小结3 6 第5 章基于证据理论的决策森林的研究3 7 5 1 证据模型3 7 5 2 快速合成算法3 7 5 3 判别决策4 1 5 4 算法复杂度分析4 2 5 5 实验结果与分析4 2 5 5 1 数据集4 2 5 5 2 实验结果4 3 5 5 3 工作展望4 6 5 6 本章小结4 7 结 仑4 9 参考文献5 1 攻读硕士学位期间所发表的学术论文5 5 致 射5 7 第1 章绪论 第1 章绪论 、 1 1 课题的研究背景与意义 数据挖掘【l 叫指从大量的、有噪声的、不完全的、模糊的或随机的数据中， 提取隐含在其中的事先未知但又潜在有用的信息或知识的过程。，从这些数据中可 以挖掘出模型和数据间的关系，并用于预测。2 0 世纪8 0 年代后期，数据挖掘技 术逐步的发展起来。自此，对分类算法的研究便成为数据挖掘领域中的一个非常 活跃的研究内容。分类算法从样本数据集中能学习出准确描述并区分数据类或者 概念的模型。进一步，这些模型能根据新样本的属性值及其它约束条件将其划分 到某个数据类别中。经典的分类方法包括决策树分类法、神经网络分类法、基于 规则的分类法、朴素贝叶斯分类法等。 虽然现在关于分类问题的算法已有很多，并且有的还很成熟，但是如今面对 的都是海量数据，一些算法在时间效率、精确性等方面都存在一些问题。近年来， 研究者们将目光放在适用性强、精度更高的分类算、法【】的研究上。l i n 、l o h 等 在 6 中用实验的方法对各种分类算法进行了比较，研究表明，尚未发现一种分 类方法对所有的数据都优于其他的方法。1 9 6 9 年，b a t e s 和g r a n g e r 提出了将几 个模型“相加 能提高模型的精度和鲁棒性的方法。目前，这一思路已经被普遍 接受。钱学森教授也提出从定性到定量的综合集成方法【j 7 1 ，将各种方法有机地结 合起来，并非杂乱无章的拼凑。通过各种方法解决本领域的问题并且相互取长补 短，从而形成各种方法的协作。钱教授的这一思想也已经在各个领域得到广泛应 用。s u e n m 于1 9 9 0 年提出了集成多分类器的概念。此外，一些数据挖掘领域的 学者已开始将混合智能系统引入到该领域。比如：1 9 9 2 年，t o w d l 和s h a w l k 提 出了k b a n ( k n o w l e d g e b a s e da r t i f i c i a ln e u r a ln e t w o r k ) 模型。19 9 7 年， p u r u s h o t h a m a n 和k a r a y i a n n i s 提出了f u z z yf e e d f o r w a r dc o n n e c t i o n i s tn e t w o r k s 模型。2 0 0 4 年，王刚提出了r f c d e n n 模型9 1 。与传统的数据挖掘分类算法相 比，这些算法或模型在效率、鲁棒性方面都有了大幅提高，但是关于模型的整合 方面还有许多问题，比如模型的整体结构，算法的参数选择等等。特别是与数据 挖掘分类算法的结合仍有许多新的问题需要解决。 目前，从数据挖掘的研究热点来看，研究重点已不是提出概念和发现方法， 而是方法的系统应用和方法的创新。目前的研究注重的是多种发现策略和技术的 集成以及多学科之间的相互渗透。本课题对多决策树的集成进行了研究。决策树 学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中 推理出以决策树为表示形式的分类规则。这些分类规则往往被用来形成对未知数 北京工业大学工学硕士学位论文 据进行分类或预测的分类器或预测模型。决策树学习包括两个主要步骤。第一步， 从训练样本集中学习并精化出一棵决策树，建立决策树模型。这个过程实际上是 一个从数据中获取知识，进行机器学习的过程。这一步通常被细分为两个阶段： 建树和剪枝。第二步，使用决策树对新的数据进行分类，达到建立决策树模型进 行分类的目的。， 本论文研究的基本思路是：利用证据理论方法融合多个决策树提供的信息， 以减少基分类器的误差，获得对问题空间模型更加准确的表示，从而提高分类器 的分类准确度和提高学习系统的泛化能力。 1 2 论文研究内容 本文的研究主要围绕多决策树的组合和应用展开。研究内容集中在以下两个 方面。 首先，对决策树、证据理论的相关内容进行了系统的研究。主要体现在对决 策树算法、随机决策树算法和随机森林算法的研究及相关实验上。 其次，对融合理论进行了系统的研究，并对决策树的组合方法进行了研究和 设计。主要体现在提出了基于证据理论的决策森林的方法，建立算法模型，并在 u c i 标准数据集上验证了所提方法。 1 3 论文的结构 本文的结构如下。 第一章为绪论部分，阐述了课题的研究背景及意义。 第二章为决策树分类方法的研究部分。本章介绍了几种决策树分类方法，并 进行了相应的实验，详细研究了随机决策树和随机森林方法。 第三章对证据理论进行了阐述。结合模糊集，对模糊证据理论方法进行了分 析与讨论。 第四章对多分类器融合理论进行了系统的研究，为本文所提方法打下坚实的 基础。 第五章提出了基于证据理论的多决策树融合算法，并建立算法模型。分析及 仿真实验表明，该算法是行之有效的。 第六章是结论和展望部分。 第2 章决策树理论与算法研究 第2 章决策树理论与算法研究 数据挖掘的主要任务有：分类分析、聚类分析、关联分析、序列模式分析等， 其中，分类分析一直是数据挖掘研究的热点之一。分类问题分为：有监督、无监 督及半监督。本文仅针对有监督的分类问题展开。对有监督的分类算法而言，其 输入数据为带类标签的训练例集。每个训练例也称为一条记录。每条记录包含若 干个属性，属性的值构成训练例的特征向量。训练集的每条记录还有_ 个特定的 类标签与之对应。因此，一个训练例可表示为一个向量：“，v 2 ，v l ，屹；c ) 。其 中，v 表示训练例第j 个属性的值，c 表示训练例的类别。 分类算法通过“分析”训练例集中的数据表现出来的分布特性，为每一个类 找到一种准确的描述或者模型。由此生成的描述或模型( 以下称为分类器) 用来 对未知类别的样本进行类别预测。 、 2 1 决策树算法简介 决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规 则的事例中推理出以决策树为表示形式的分类规则。这些分类规则往往被用来对 未知数据进行分类或预测。它的特点有：它是学习离散值目标函数的近似表达的 方法，学习出的函数表示为决策树，但也可改写为易读的i f - t h e n 规则；实用性 强，许多著名的学习系统( i d 3 ，c 4 5 等) 皆基于此方法，并成功应用到许多实 际领域( 学习疾病的诊断，信贷风险的评价等) ；它能较好地抵抗噪音；它能学 习析取表达式；它搜索完全的假设空间；它的归纳偏向是小树优先于大树。基于 决策树的分类算法以其特有的优点广为人们采用。据统计，目前决策树算法利用 率高达1 9 。 决策树学习包括两个主要步骤。第一步，从训练样本集中学习并精化出一棵 决策树，建立决策树模型。这个过程实际上是一个从数据集中获取知识，进行机 器学习的过程。这一步通常又被细分为两个阶段：建树和剪枝。决策树剪枝阶段 的任务是对生成的决策树按照一定的方法进行剪枝。剪枝是一种克服训练样本集 数据噪声的基本技术，它能在确保精确程度的同时，提高可理解性。对树进行修 剪优化时要准确理解分类的特征描述和防止过多的噪声影响，从而达到更好的修 剪效果。第二步，使用决策树对新的数据进行分类，以达到建树的目的。 决策树的建树流程图如下图所示。其中，5 - 表示训练样本集，a 表示分类样 本集合，表示一个分类叶节点。 北京工业大学工学硕士学位论文 图2 - 1 决策树算法流程图 f i g u r e2 1d e c i s i o nt r e ea l g o t i t h m sf l o w c h a r t 在各种决策树分类的算法中，早期的有c l s 学习算法和c a r t 算法。最有 影响的是q u i n l a n 提出的i d 3 算法。在i d 3 算法的基础上，他又提出了c 4 5 算 法。为了适应处理大规模数据集的需要，后来又提出了若干改进的算法，如s l i q 算法、s p r i n t 算法、p u b l i c 算法等。下面，对主流的算法进行描述。 ( 1 ) c l s 算法 c l s ( c o n c e p tl e a r n i n gs y s t e m ) 学习算法【lo 】是h u n t e b 等人于1 9 6 6 年提出 的。h u n t e b 等人第一次提出用决策树进行概念学习。后来的许多决策树学习算 弟2 苹决策树理论与算法研究 法都可以看作是c l s 算法的改进与更新。 c l s 的主要思想是：从一个空的决策树出发，通过添加新的判定结点来改善 原来的决策树，直到该决策树能够正确的将各类别的训练例分开为止。它对决策 树的构造过程也就是假设特化的过程。c l s 可以看作是只带一个操作符的学习算 法，此操作符可以表示为：通过添加一个新的判定条件( 新的判定结点) ，特化 当前假设。c l s 算法递归调用这个操作符作用在每个叶结点来构造决策树。 ( 2 ) 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 s ) 分类算、法【1 1 】是由b r e i m a n l ， f r i e d m a n j h 和o l s h e n r a 等人于19 8 4 年提出的。这种算法选择具有最小g i n i 指标的属性作为测试属性，并采用一种二分递归分割的技术。这种技术将当前样 本集分为两个子样本集，使得生成的决策树的每一个非叶节点都有两个分枝。最 后生成的决策树是结构简洁的二叉树。c a r t 的剪枝使用了后剪枝法。剪枝算法 使用独立于训练样本集的测试样本集对子树的分类错误进行计算，找出分类错误 最小的子树作为最终的分类模型。若由于样本集中数目太少而不能分出独立的测 试样本集，则可以采用一种称为交叉验i i e ( c r o s sv a l i d a t i o n ) 的剪枝方法。该方法解 决了在小样本集上挖掘决策树由于没有独立测试样本集而造成的过度拟合问题。 ( 3 ) i d 3 算法 i d 3 ( i t e r a t i v ed i c h o t o m i z e r3 ) 算法【1 2 】是q u i n l a n 于1 9 8 6 年提出的。它是决策 树算法的代表。绝大数决策树算法都是在它的基础上加以改进而实现的。它采用 分治策略，在决策树各级结点上选择属性时，用信息增益作为属性的选择标准， 以便在每一个非叶子结点上进行测试时，能获得关于被测试记录最大的类别信 息。具体方法是：检测所有的属性，选择信息增益最大的属性作为决策树或决策 子树的根结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方 法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到 一棵决策树，它可以对新的样本进行分类。 属性的信息增益计算方法如下。设s 是j 个数据样本的集合，并假定类标号 属性具有m 个不同值，定义m 个不同类q o = 1 ，2 ，m ) 。设置是类c ：中的样本数， 对一个给定的样本分类所需的期望信息【1 2 】为： j ! ，( s l ，屯，s 。) = 一p i l b ( p i ) ( 2 - 1 ) i = l c 其中，b = 睾是任意样本属于e 的概率。注意，对数函数以2 为底，其原因 ) 是信息用二进制编码。设属性a 具有v 个不同值 a ia ：，吼) ，可以用属性a 将s 划分为y 个子集 置，是，鼠) ，其中s ，中的样本在属性a 上具有相同的值 北京工业大学工学硕士学位论文 a y ( j = 1 ，2 ，1 ，) 。设墨是子集q 中类g 的样本数。由a 划分成子集的熵1 2 1 或信 息期望为： e ( 彳) = 一摹 羔学( 勖，屯，j 叫) ( 2 - 2 ) 熵值越小，子集划分的纯度越高。对于给定的子集s ，的信息期望【1 2 】的公式 为： i ( s t ，岛，s m j ) = 一p i ，z b ( p , ，) ( 2 - 3 ) 其中珐，：高是s ，中样本属于g 的概率。在属性a 上分支获得的信息增益【1 2 】为： 。m 。 g a i n ( a ) = ，( 墨，最，瓯) - e ( a ) ( 2 - 4 ) i d 3 搜索的假设空间是所有可能的决策树的集合。i d 3 搜索目的是构造与训 练数据一致的一棵决策树( 即能够对训练例进行正确分类的一棵决策树) 。i d 3 的搜索策略是爬山法，在构造决策树时从简单到复杂，用信息赢取作为指导爬山 发的评价函数。i d 3 式的基本决策树学习算法有优点，也有缺点。优点为：其搜 索空间是完全的假设空间，目标函数必在搜索空间中，不存在无解的危险；全盘 使用训练数据，而不是象候选剪除算法一个一个地考虑训练例，这样做的优点是 可以利用全部训练例的统计性质进行决策，从而抵抗噪音( 个别例子中的错误数 据) ，可以很容易地修改i d 3 算法的终止条件，使之能够获得与训练数据不完全 一致的假设。缺点是：搜索中只维持一个解，不能象候选剪除算法那样返回所有 可能的与训练例集一致的假设，并优化地查询新例以获得收敛于目标函数的解； 其搜索无回溯，如同一般的无回溯爬山搜索一样，它可能收敛于局部最优解而丢 掉全局最优解，i d 3 沿着一条路选择的决策树可能没有在各个分支上搜索所遇到 的一些决策树好；因为不是一个一个地考虑训练例，不容易象候选剪除算法那样 使用新例步进式地改进决策树。对i d 3 算法的早期改进算法主要是i d 3 的增量版 i d 4 ，i d 5 及c 4 5 ，f a c t 和c h a i r 等算法。 ( 4 ) c 4 5 算法 c 4 5 算法【1 3 】是q u i n l a n j r 在1 9 9 3 年提出的，它是从i d 3 算法演变而来，继 承了i d 3 算法的优点，c 4 。5 算法引人了新的方法和功能。 用信息增益率的概念，克服了用信息增益选择属性时偏向多值属性的不 足； 在建树过程中进行剪枝，以避免树的过度拟合； 第2 章决策树理论与算法研究 能够对连续属性进行离散化处理； 可以处理具有缺失属性值的训练样本集； 能够对不完整数据进行处理； k 折交叉验证； 规则产生式。 c 4 5 算法降低了计算的复杂度，增强了计算的效率。它对于i d 3 算法的重 要改进是使用信息增益率来选择属性。采用信息增益率比i d 3 算法中采用信息增 益更好，主要是克服了i d 3 方法选择偏向取值多的属性。c 4 5 算法还针对连续 值属性的数据进行了处理，弥补了i d 3 算法只能处理离散值属性数据的缺陷。然 而c 4 5 算法在处理连续型测试属性中线性搜索阈值付出了很大代价。在2 0 0 2 年， s a l v a t o r er u g g i e r i 提出了c 4 5 的改进算法：e c 4 5 算法。e c 4 5 采用二分搜索取 代线性搜索，从而克服了这个缺点。但是它的缺点是占用内存比c 4 5 要多。 ( 5 ) s l i q 算法 上述算法由于要求训练样本集驻留内存，因此不适合处理大规模数据。为此， i b 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 ) 0 4 1 。它综合利用属性 表、类表和类直方图来建树。属性表含有两个字段：属性值和样本号。类表也含 有两个字段：样本类别和样本所属叶节点。类表的第k 条记录对应于训练样本集 中第詹个样本( 样本号为五) ，所以属性表和类表之间可以建立关联。类表可以 随时指示样本所属的划分，所以必须长驻内存。每个属性都有一张属性表，可以 驻留磁盘。类直方图附属在叶节点上，用来描述节点上某个属性的类别分布。描 述连续属性分布时，它由一组二元组 组成；描述离散属 性分布时，它由一组三元组 组成。 随着算法的执行，类直方图中的值会不断更新。s l i q 在建树阶段，对连续属性 采取预排序技术与广度优先相结合的策略生成树，对离散属性采取快速的求子集 算法确定划分条件。该算法能够处理比c 4 5 大得多的训练样本集，在一定范围 内具有良好的随着记录个数和属性个数增长的可伸缩性，s l i q 的运行速度更快， 生成的决策树更小，预测的精确度较高；对于大型训练样本集，s i l q 精确度更 高，优势更明显。然而它存在的主要缺点有：需要将类别列表存放于内存，而类 别列表的元组数与训练样本集的元组数是相同的，这就从一定程度上限制了可以 处理的数据集的大小；采用了预排序技术，而排序算法的复杂度并不是与记录个 数成线性关系，因此，使得s l i q 不可能达到随着记录数目增长实现线性可伸缩 性。 ( 6 ) s p r i n t 算法 s p r i n t ( s c a l a b l ep a r a l l e l i z a b l ei n d u c t i o no fd e c i s i o nt r e e s ) 算法1 1 5 j 是 北京工业大学工学硕十学位论文 s h a g e r j ，a g r a w a l r 和m a n i s h m 等人在1 9 9 6 年提出。它对s l i q 算法中必须在 内存中常驻一个类表的缺点进行了改进，提出了一种新的数据结构，完全取消了 对内存的限制，并且速度更快，可伸缩性更好。s p r i n t 分类方法最大的优点就 是可以避免内存空间的限制，利用多个并行处理器构造一个稳定的、分类准确率 更高的决策树，具有更好的可伸缩性，扩容性。但该算法因使用属性列表，使得 存储代价大大增加，并且结点分割处理的过程较为复杂，加大了系统的负担。 ( 7 )p u b l i c 算法 上述含有剪枝的算法都是分成两步进行，即先建树再剪枝。而r a s t o g i r 等 人在1 9 9 8 年提出的p u b l i c 算法【16 】将建树、剪枝结合到一步完成，在建树阶段 不生成会被剪枝的子树，因而大大提高了效率。p u b l i c 的建树基于s p r i n t 方 法、剪枝基于m d l ( 最小描述长度法) 原则。p u b l i c 采用低估策略来矫正过高 的代价估算来防止过度剪枝，即对将要扩展的叶节点计算编码代价的较低闭值， 而对于另两类叶节点( 剪枝形成的、不能被扩展的) ，估算方法不变。 ( 8 ) r a i n f o r e s t 算法 r a i n f o r e s t 分类方澍1 。7 】是由g e h r k e j ，r a m a k r i s h n a n r 和g a n t i v 等人在1 9 9 8 年提出的一种针对大规模数据集，快速构造决策树的分类框架。r a i n f o r e s t 分类 框架的核心思想是根据每一次计算所能使用的内存空间，合理地调整每次计算所 处理的数据集的大小，使r a i n f o r e s t 框架内所使用的分类方法在每次计算的过程 中，对内存资源的利用率达到最大，在有限的资源下，用最少的时间完成决策树 的构建。 ( 9 ) s u r p a s s 算法 s u r p a s s ( s c a l i n gu pr e c u r s i v ep a r t i t i o n i n gw i t hs u f f i c i e n ts t a t i s t i c s ) 算法【1 8 】 是由l ix i a o b a i 在2 0 0 5 年提出的一种处理数字数据的分类算法。s u r p a s s 把 线形判别式整合到决策树的回归分割过程中。建立决策树所需的信息被摘录到一 个充分统计的集合中，这个集合能以递增的方式，通过每次从存储空间中读取数 据的子集被收集起来，所以该算法能处理容量超过计算机内存的数据集。 2 2 研究现状 2 2 1 国内外研究进展 传统的决策树算法主要是针对小数据集的，大都要求训练集常驻内存，这使 得在处理数据挖掘任务时，传统决策树算法在可伸缩性、精度和效率方面受到了 很大的限制。而在实际的数据挖掘应用中我们面临的数据集往往是容量巨大的数 据库或者数据仓库，在构造决策树时需要将庞大的数据在主存和缓存中不停的导 8 第2 章决策树理论与算法研究 入导出，使得运算效率大大降低。针对以上问题，许多学者提出了处理大型数据 集的决策树算法。 在数据预处理方面，y o s h i m i t s uk u d o h 等人提出了一种新的基于信息增益比 ( 信息增益比在中用来进行节点属性的选择) 的数据概化方法i t a 和迭代i t a 。 在抽样方法方面，k h a l e da l s a b t i 等人【1 9 】提出了一种新的决策树分类器 c l o u d s ( c l a s s i f i c a t i o nf o rl a r g eo ro u t o fc o r ed a t a s e t s ) ，提供了两种确定数值型 属性最优分裂点的新方法s s ( s a m p l i n gt h es p l i t t i n gp o i n t s ) 和s s e ( s a m p l i n gt h e s p l i t t i n gp o i n t sw i t he s t i m a t i o n ) 。其中，s s 采用分位技术( q u a n t i l i n gt e c h n i q u e ) 将每一个数值型属性的取值范围分为若干个区间( 每一个区间包含的数据点基本 相等) ，计算每个区间两个端点的基尼指数，并将基尼指数最小的点作为最优分 裂点进行下一步的分枝。s s e 是s s 的改进算法。它利用s s 求出最小基尼指数， 并估计出每一个区间上基尼指数的下限。若区间的基尼指数下限小于最小基尼指 数，则将区间保留；否则删除，然后，对于那些被保留区间中的每一个点，计算 其基尼指数，取基尼指数最小的点为最优分裂点。s s e 的精度要高于s s ，但是 计算量也大。c l o u d s 通过一个“估计步”对数值型属性的所有取值进行抽样， 由此可以缩小寻找最优分裂点的搜索空间。与传统的决策树算法相比，c l o u d s 明显地降低了运算和i o 的复杂度，而且产生的决策树在精度和规模上也保持了 较高的质量。 在结合其他算法方面，z f u 提出一种智能决策树算法g a i t ，结合了遗传算 法、统计抽样和决策树算法，在一定程度上弥补了基于子集方法的缺陷。 决策树结合提升算法( b o o s t i n g ) 口o 】产生提升树也是近年来应用较广的方法。 最流行的提升算法是由f r e u n d 和s c h a p i r e 于1 9 9 7 年提出的a d a b o o s t m 1 。提升 的目的是连续对反复修改的数据应用弱分类算法，由此产生一个弱分类器序列， 然后合并这些弱分类器的加权和的输出，从而产生最终分类。 有一类方法研究的是由神经网络中得到所需要的决策树。这类方法解决了由 神经网络得到的知识难于被人们理解的缺点。 决策树存在着不稳定的缺点，即决策树带来了较大的变动。模糊集合的融通 性使人们利用模糊逻辑来解决决策树的这一缺点并取得了不错的效果。最近， c o l a r u 提出了一种新的模糊决策树方法一软决策树。软决策树综合决策树的生 成和修剪来决定其本身的结构，并利用重修( r e f i t t i n g ) j 1 磨合( b a c k f i t t i n g ) 来提高 树的归纳能力。软决策树比一般决策树的正确率要高。此外，m d o n g 等人提出 的基于前瞻( l o o k a h e a d ) 的模糊决策树也能够在得到较好的归纳特性的前提下 产生较小体积的决策树。 我国的相关研究人员在决策树分类算法改进上也取得了不少成就。在改进 i d 3 算法上，1 9 9 5 年洪家荣教授等提出一种新的基于概率的决策树归纳学习算法 北京工业大学工学硕十学位论文 p i d ，从示例学习最优化的角度对决策树归纳学习的优化原则进行分析，但在树 的扩展过程中，采用属性聚类的方法进行分枝合并，p i d 得到的决策树在树的规 模和分类精度上都优于i d 3 ；在特征属性选择的问题上，1 9 9 8 年刘小虎博士等学 者在选择一个新属性时，并不仅仅计算该属性引起的信息增益，而是同时考虑树 的两层结点，即选择该属性后，继续选择属性带来的信息增益；从构造机制的角 度，1 9 9 8 年肖勇和陈意云教授采用遗传算法构造决策树。1 9 9 9 年，吴菲和黄梯 云教授提出利用二元决策树实现模型选择，并采用遗传算法构造二元决策树并提 出了遗传算法基于二元决策树的模型选择方法，以趋势预测模型为例进行了验 证，获得了较好的效果；在简化决策树的规则学习问题上，1 9 9 8 年王军博士和 史忠植教授等在粗糙集理论中的约简概念的启发下提出了极小规则和极大规则 的概念及极小极大规则学习；在多变量模糊决策树的构造与研究问题上，1 9 9 7 年苗夺谦讲师和王饪研究员针对比较常见的多变量决策树，利用粗糙集理论中条 件属性相对于决策属性的核，解决多变量检验中属性的选择问题。 2 2 2 决策树研究面临的主要问题 1 可扩展性亟待提高 r a j ua d d a l 认为，算法具有良好的可扩展性是指算法具有处理大量的数据或 加速数据挖掘过程的能力。在大型数据集中，能从中快速而准确地发现隐藏于其 中的主要分类规则，即认为算法具有良好的可扩展性。数据挖掘面临的数据往往 是海量的，对实时性要求较高的决策场所，数据挖掘方法的主动性和快速性显得 日益重要。应用实时性技术、设计快速的算法、数据分割、主动关系数据库技术 和分布并行算法设计技术等现代计算机先进技术，是数据挖掘方法实用化的有效 途径。 2 适应多数据类型和容噪性 随着计算机网络和信息的社会化，数据挖掘的对象己不单是关系数据库模 型，而是分布、异构的多类型数据库，数据的非结构化程度、噪声等现象越来越 突出这也是决策树技术面临的困难问题。 3 递增性问题 数据挖掘出来的知识，只是相对于某一时间的某些数据，新的数据可能使发 现的新知识与原