（计算机应用技术专业论文）基于决策树分类算法的噪声容错性研究.pdf

南京i l i l l l f ! 人学顾 ：研究生学位论义摘要 摘要 数据分类是一种重要的数据挖掘技术，常用的数据分类方法有决策树归纳分类、贝叶 斯分类、神经网络分类和k 最邻近分类等，采用的理论及算法有决策树( d e c i s i o nt r e e ) 、粗 糙集( r o u g hs e t ) 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 在占 专宁o i d 3 ( i n t e r a c t i v ed i c h o t o m y3 ，简称i d 3 ) 算法以信息熵作为属性选择的标准，是经典的 决策树算法，但该算法没有考虑噪声数据的影响，使得算法的抗噪声能力比较差。针对上 述的不足，本文分别结合粗糙集理论、人工神经网络对i d 3 算法作了改进研究，主要内容 包括： 首先，对决策树、可变精度粗糙集理论进行了系统的研究，分析了变精度粗糙集中分 类质量与分类正确率的关系。考虑到可变精度粗糙集理论在处理噪声数据方面具有较强的 抑制能力，以及实际应用中常关心的分类质量问题，提出了基于分类质量的变精度i d 3 算 法。 与此同时，结合粗糙集理论中属性约简算法可以在不影响分类能力的前提下对数据集 进行简化的特性，本文还提出了变精度的属性约简算法。 其次，考虑到神经网络具有鲁棒性、自适应性和高度容错性等特点，并且在利用粗糙 集理论知识构建决策树算法的属性选择标准启发下，提出了基于样条权函数神经网络的决 策树生成算法。 随后，分别对基于分类质量的变精度i d 3 算法及基于样条权函数神经网络的决策树算 法构建了分类器，用u c i 数据库中的多个数据集作为测试数据进行了实验，实验结果表明 改进后的决策树生成算法在抑制噪声方面要优于改进前的1 1 3 3 算法，其实用性更好。 最后，本文提出将决策树分类思想应用到城市道路建设中去，为城市现有道路的养护 及新道路的规划起到辅助参考作用。 关键字：i d 3 算法，分类正确率，分类质量，属性约简，样条权函数神经网络 南京邮l 【1 人学顾：i ：研究生学位论文 a b s t r a c t a b s t r a c t c l a s s i f i c a t i o ni so n eo ft h em o s ti m p o r t a n tt e c h n o l o g i e si nd a t am i n i n gw h i c hi n c l u d e s d e c i s i o nt r e em e t h o d s ，b a y e s i a nm e t h o d s ，n e u r a ln e t w o r km e t h o d s ，k n e a r e s ta l g o r i t h m t h e m o s tp o p u l a rt h e o r i e sa n da l g o r i t h m sa r ed e c i s i o nt r e e ，r o u g hs e t ，a r t i f i c i a ln e u r a ln e t w o r k ， g e n e t i ca l g o r i t h m sa n ds oo n i d 3a l g o r i t h mi sac l a s s i f y i n ga l g o r i t h mi nd e c i s i o nt r e em e t h o d s ，w h i c ht a k e si n f o r m a t i o n e n t r o p y a ss t a n d a r df o rc h o o s i n gs p l i t t i n ga t t r i b u t e s b e c a u s eo fn o tc o n s i d e r i n gt h ei n f l u e n c eo f n o i s e ，t h ea l g o r i t h m sa b i l i t yt oa n t i - i n t e r f e r e n c ei sw e a k t h es t u d i e si sg i v e nb yi n t e g r a t e i n gi t w i t hr o u g hs e ta n dn e u r a ln e t w o r k ，t h em a i nc o n t e n t so fp a p e ra r el i s t e da sf o l l o w ： i nt h ef i r s t ，ar e s e a r c hw a sm a d eb a s e do nd e c i s i o nt r e e ，r o u g hs e t st h e o r ya n dt h e r e l a t i o n s h i pa n a l y z e db e t w e e nq u a l i t yo fc l a s s i f i c a t i o n a n dt h ec o r r e c tc l a s s i f i c a t i o nr a t e b e c a u s ev a r i a b l ep r e c i s i o nr o u g hs e tc o u l dr e s t r a i nn o i s ev e r yw e l la n dt h eq u a l i t yo f c l a s s i f i c a t i o ni st h em o s tc o n c e r n e df a c t o ri np r a c t i c a la p p l i c a t i o n s ，an e wa l g o r i t h mn a m e d v a r i a b l ep r e c i s i o ni d 3a l g o r i t h mb a s e do nq u a l i t yo fc l a s s i f i c a t i o ni sp u tf o r w a r di nt h i sp a p e r a l s ob e c a u s ea t t r i b u t er e d u c t i o nn o to n l yr e d u c e sr e d u n d a n tc o n t r i b u t i o n sb u ta l s oh a st h es a m e p r e c i s i o no fc l a s s i f y i n g ，t h ea l g o r i t h mo fa t t r i b u t er e d u c t i o nb a s e do nv a r i a b l ep r e c i s i o ni s p r o p o s e d a tt h es a m et i m et h ed a t a s e ti sr e d u c e du s i n gt h ea l g o r i t h m t h es e c o n d ，b e c a u s en e u r a ln e t w o r kh a sm a n yc h a r a c t e r i s t i c sl i k er o b u s t n e s s ，a d a p t a b i l i t y a n df a u l tt o l e r a n c ea n de n l i g h t e n e db yu s i n gr o u g hs e tt og e tt h es p l i t t i n ga t t r i b u t e sc r i t e r i a , d e c i s i o nt r e ea l g o r i t h mb a s e do ns p l i n ew e i g h tf u n c t i o nn e u r a ln e t w o r kw a sg i v e n i nt h ea f t e r , c l a s s i f i e r sw e r ed e s i g n e d ，m o r e o v e r , t h ee x p e r i m e n tw h i c hd a t af r o mu c ii s g i v e ni no r d e rt op r o v et h ep e r f o r m a n c eo ft h ea l g o r i t h m sp r o p o s e d ，a n dt h er e s u l ti n d i c a t e st h a t t h et w oi m p r o v e da l g o r i t h m sa r es u p e r i o rt h a ni d 3i nr e s i s t i n gn o i s e ，a n di th a sb e t t e r p r a c t i c a b i l i t yt h a nb e f o r e f i n a l l y ，a ni d e at h a ta p p l i e sd e c i s i o nt r e em e t h o dt oc l a s s i f yc i t yr o a d s i sb r o u g h tf o r w a r di n o r d e rt oh e l pc u r r e n tr o a d s m a i n t e n a n c ea n dt h ep r o g r a m m i n go fn e wr o a d s k e y w o r d s ：i d 3a l g o r i t h m ，c o r r e c tc l a s s i f i c a t i o nr a t e ，q u a l i t yo fc l a s s i f i c a t i o n ，a t t r i b u t e s r e d u c t i o n ，s p l i n ew e i g h tf u n c t i o nn e u r a ln e t w o r k i l 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：枉蠢笪 日期： q 罩：上l & 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：柱莛皇导师签名：三咝一日期：皇墨：! 墨 南京邮i u 人学硕i ：研究生学位论文第一帝绪论 1 1 论文的研究背景及意义 第一章绪论 在如今的信息化社会里，随处可见的“数据大海”几乎成为所有行业的共同特点，面 对如此众多并时时急增的数据，很多行业已经意识到数据挖掘技术的重要性，并且很多企 业已使用数据挖掘技术在浩瀚的数据海中去探索隐藏其后更为宝贵的信息。“数据挖掘” 在很多领域已经不再是个陌生的名词。 数据挖掘是从大型数据库或数据仓库中发现并提取隐藏在其中的信息的一种技术，目 的是帮助决策者寻找数据间潜在的关联，发现被忽略的要素，这些信息对预测趋势和决策 行为是十分有用的，并且已经在医学、金融、开采、生产等许多领域得到了越来越广泛的 应用。 分类是根据分类模型按照属性值对数据集合进行分类，是数据挖掘的一个重要的应 用，其目标是挖掘分类规则。可以用于从数据库中提取重要数据类或预测未来的数据趋势， 即在数据库的各个对象中找出共同特性，并按照分类模型把它们进行分类。所以，研究发 展各种分类技术，为数据库中的数据开发有效的分类方法是非常必要的。 决策树是数据挖掘中的常用技术，由于其分类速度快，精度高，规则易理解等特点， 应用很广泛，并且有关围绕决策树技术的研究也颇受关注。但现实中，数据都会有大量不 一致、不确定性，无处不见噪声的存在，而粗糙集( r o u g hs e t ，简记r s ) 理论【l 】的出现从 新的角度认识知识，把知识和分类紧密联系起来，提供了更符合人类认知的数学工具【2 1 。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，简记a n n ) t 3 】在分类方法中是一种先进的人工智 能技术，它不仅可以避开建立复杂的数学模型和进行繁琐的数学推理，而且十分适合处理 非线性和含噪声的数据，尤其是对那些以模糊、不完整、不严密的知识或数据为特征的处 理问题。数据挖掘工具要面对的正是一些有噪音的、杂乱的、非线性的数据，处理这些问 题正是神经网络的优势。当前，决策树、粗糙集理论、神经网络分类技术的应用得到了快 速的发展，但决策树技术分类速度快，精度高，易理解的特点是神经网络技术无法比拟的； 而在处理噪声、不完整数据的优势，决策树又无法与粗糙集、神经网络相比较。如何在决 策树技术分类精度高、易理解的优势上，充分利用粗糙集或神经网络处理噪声数据的特点， 进一步完善决策树分类方法，丌拓决策树分类的实际应用，是我们面临的一个新的课题。 此外，鉴于当前交通问题是我国乃至世界各国的大问题，频繁的道路修筑、改造在一 南京邮l u 人学坝i j 研究生学位论义第一章绪论 定程度上缓解了一时的交通压力，但症结不仅于此。面对当前下设地铁，上建高架的道路 建设，面对一直以来的交通压力，已修筑道路的效能发挥到何种程度，即将新增道路又能 发挥多大作用，怎样能更大程度的缓解交通压力，方便人们的生活，数据挖掘在此方面的 应用也是一个需要探究的问题。 1 2 研究现状 决策树的算法很多，最为经典且最具有反响的是1 9 8 6 年j r o s sq u i n l a n 提出的决策 树归纳算法i d 3 算法【4 】。同时，围绕此算法的各种研究倍受青睐，出现了该算法与其 它算法相结合的优化算法及研究：决策树技术与进化算法相结合【5 】，使决策树系统具有较 好的抗噪声能力，同时进化算法容易在并行计算机上运行；决策树技术与多智能体的结合， 用于机器人足球控制6 】；基于多维可视化下的交互式的决策树构造【刀，在决策树构造阶段 加入了专家知识，便于用户更深地理解产生决策树的数据及最终产生的决策树；此外，在 增强抗噪声能力上，还有与粗糙集理论的结合研究，与神经网络的结合研究【8 】等。 z i a r k ow 提出的可变精度粗糙集( v a r i a b l ep r e c i s i o nr o u g hs e t ，简记v p r s ) 模型【9 1 允 许一定的分类错误存在，并给出了错误率低于预先给定值的分类策略，对数据不一致性有 一定的容忍度，有利于解决属性间无函数或不确定关系的数据分类问题。i d 3 算法与粗糙 集的结合研究，有助于发挥两者的长处，弥补对方的不足，对i d 3 算法起到优化的效果。 构造最优决策树是决策树学习算法研究的主要方向，然而已证明这是一个n p 难度问 题】。本质上，构造决策树的过程就是选择非叶节点属性的过程，因此，不同的属性选 择标准构成了不同的决策树学习算法，从而出现了采用粗糙集的思想方法来构造属性选择 标准的决策树技术与粗糙集理论结合研究，具体有： 以粗糙集中条件属性对决策属性的重要性作为属性选择的依据【l o 】【l l 】；以粗糙集中属 性的核属性作为属性选择的标准【1 2 】【13 1 ，即首先考虑核属性中的组合作分裂属性，当核属 性的最大组合不能区分条件属性时，则采用传统决策树分类算法；以粗糙集中属性的边界 区域作为属性选择的标准【2 】【14 1 ，等等。 此外，由于i d 3 算法存在很多不足，l g 女n ：抗噪声能力差，属性的重复选择等，因 此，出现了采用粗糙集理论思想优化i d 3 算法的结合研究。 在运用决策树算法之前，引入粗糙集理论，对条件属性进行约简 1 5 】【1 6 】【17 1 ，搜索重要 属性，减少算法的工作量；将粗糙集思想引入到剪枝算法中【1 8 】，更有效的控制决策树的 生长规模；将变精度粗糙集的思想引入决策树算法中【1 9 】【2 0 1 ，改善决策树算法对噪声数据 2 南京邮i u 人学坝i ：研究生学位论义第一币绪论 敏感的不足；利用变精度粗集思想优化决策树的规则提取【2 l 】【2 2 1 ，等等。 此外，考虑到人工神经网络方法具有强大的学习能力、并行处理、自适应性和容错性 等特点，是决策树所必需的；而决策树所具有的较强的知识表达能力、易于分析推理的特 性、容易理解的规则导出等也是神经网络所不具备的，利用两者结合的方法，融合二者的 优势，一些学者提出了更加优化的神经网络方法：s e t h i 2 3 】提出了“熵网络”的概念，借 助于前馈网络与分类决策树在功能上的等价性，利用决策树来确定神经网络的结构，包括 隐层数、隐单元数等；d e f f u a n t 2 4 提出了与构造决策树相似的方法来添加网络中的神经元； s a n g e r ( 2 5 】探讨了根据输入和待逼近的函数来构造树结构的自适应神经网络的方法，用于高 维空间函数逼近，一旦网络状态固定后学习算法不会陷入局部极小；k u b a t 2 6 】则利用决策 树对r b f 网络的参数进行初始化，定义样本空间中相对纯区域，使该区域可用于确定基 函数。 1 3 本文的主要内容和成果 决策树技术已相对成熟，但目前对决策树的研究仍然备受关注，研究方向包括决策树 的修剪2 7 1 、模糊决策树算法【2 8 】、决策树算法和其他挖掘方法的结合【2 9 】等方面。 i d 3 算法是决策树中的经典算法，由于i d 3 算法的不足，围绕该算法展开的各种改进 算法也层出不穷。然而，对算法研究的最终目的是去解决实际问题，i d 3 算法对噪声数据 敏感的不足，严重阻碍了算法的实际应用。针对上面的问题，本文在i d 3 算法的基础上 提出了改进优化方案。不仅考虑到现实数据中存在噪声数据，通过引入分类正确率风又 称变精度阈值) ，增强算法的容错能力，而且针对不同的分类问题充分考虑用户对分类结 果的不同要求，选择合适的值，即卢值根据实际问题的要求来确定，而不再是通过多次 尝试或根据经验的方式来定，该优化方法弥补了i d 3 容错能力差的不足，同时更符合实 际的要求。此外，本文还借鉴了神经网络的思想，研究了神经网络与决策树相结合的方法， 给出了基于样条权函数神经网络【3 0 】的决策树算法。 出于对某市路段的改造建设重铺地下隧道的思考：该道路的修建时间不长，迫于 交通压力不得不对其开挖，再建隧道。先不考虑道路改建后对交通压力的缓解程度，就道 路修建时间之短、运营效果不理想，现又改造而造成的人力、物力、财力的损失，以及短 时间内，同条道路的两次大型改建给人们的出行带来的不便，给整个区的交通带来的压力 等等也是很值得深思的问题，同时给城市道路的建设也提出了问题：如何使得修建的道路 能最少的改造? 如何使修建的道路能发挥其最大效能，真正起到了缓解交通压力的初衷? 南京f l | i j il 1 人学坝i j 研究生学位论义第一章绪论 鉴于上述问题，本文提出了将决策树技术引入到城市道路路况跟踪中去。通过对已有道路 的运营情况的统计分类，掌握城市道路运营的概况，对需要缓解交通压力的路段及对道路 的维护、修整工作都能给出整体上的辅助决策作用，从而尽力避免道路的重复建设及修建 道路效能发挥不理想的情况。 本文首先介绍了决策树的含义，然后对变精度粗糙集思想、神经网络技术作了详细的 说明及分析，分别结合变精度粗糙集思想、神经网络技术提出了优化算法。而后，以u c i 中的多个数据集为实验数据对优化算法进行了测试，说明优化算法在噪声容错能力方面明 显优于i d 3 算法。最后，给出了基于分类质量的变精度i d 3 算法的实际应用，对城市道 路路况进行跟踪分类，希望在城市道路的规划建设决策方面提供参考信息。 1 4 本文的组织结构 本文的论文结构共分为六章： 第一章讲述课题背景、研究现状及本文的主要内容。 第二章讲述了决策树分类算法。首先介绍了决策树的基本知识、构建及剪枝；然后 对决策树的经典算法一i d 3 算法进行了详细阐述及分析。 第三章讲述了变精度粗糙集理论。首先讲述了变精度粗糙集的理论基础及粗糙集属 性约简的各种方法；重点讲述了将变精度粗糙集思想引入到决策树构建中的i d 3 改进算 法；针对变精度i d 3 算法存在的阈值难确定的问题，提出将满足分类质量要求的值 确定算法应用到变精度i d 3 算法中从而给出了基于分类质量的变精度i d 3 算法。此外， 结合变精度思想，给出了基于变精度的属性约简算法。 第四章给出了决策树与神经网络相结合的基于样条权函数神经网络的决策树算 法。简单阐述了神经网络及样条权函数神经网络，随后给出了基于样条权函数神经网络的 决策树算法，并举例说明算法的具体流程。 第五章实验及分析。以u c i 数据库中的数据集作为实验数据，对基于分类质量的变 精度i d 3 算法、样条权函数神经网络的决策树算法进行了实验，并对实验结果作了分析、 说明，验证了优化后的算法具有噪声容错能力。 第六章算法应用。提出将基于分类质量的变精度i d 3 算法应用到城市道路运营跟踪 中，同时进行了仿真实验。 第七章总结与展望。对本文进行的工作进行了分析与总结，并提出了下一步的研究 方向。 4 南京邮电大学硕士研究生学位论文第二章决策树算法的分析与研究 第二章决策树算法的分析研究 分类是数据挖掘中应用及其广泛的重要技术之一，通过对数据进行分析，然后利用从 数据中得到的特征信息为每个类别建立精确的描述或模型，这种分类描述可进一步用于对 数据库中的数据进行分类或建立分类规则。最为典型的分类方法是基于决策树的分类方 法。 2 1 决策树概述 决策树是一种直观的知识表示方法，主要用于概念学习及归纳推理。由于决策树导出 的决策规则简单而且易于理解，目前已被作为一种重要的机器学习方法被广泛使用。 决策树的学习过程就是决策树的构造过程，树中内部节点代表对某条件属性的一次测 试，一条边代表一个测试结果，叶子节点代表某个类或类的分布，最上面的是根节点。在 具体的分类问题中，我们对生成的决策树从根节点开始，一直向下判定，当到达一个叶子 节点时，一个决策( 即分类规则) 便形成了。此外，决策树可以很方便地转化为分类规则， 是一种非常直观的分类模式的表示形式。 图2 1 城市道路运营情况分类树 图2 1 是一棵决策树，给出了某城市现有道路的运营情况( 未剪枝) 。在对城市道路实 际运营情况的分类中，将道路的运营状况作为分析预测的目标即预测属性( 或称挖掘属 性) ；候选属性( 或称为条件属性) 由道路的等级，排水情况，车流量，堵车程度组成。图 5 南京邮l 【l 大学颁i ：研究生学位论文第二章决策树算法的分析i 州i 究 2 1 中椭圆表示内部节点即条件属性，圆表示叶子节点即类别( 道路运营很好为a ；一般为 b ；稍差为c ，需要关注；很差为d ，需采取措施) 。树中九个叶子节点代表九条规则，如 规则1 ：如果道路堵车程度= 无a n d 道路排水情况= 好则道路的运营情况= 很好，说明道 路的建设很成功，不存在交通压力。 2 2 决策树算法构成 决策树算法是以实例为基础的归纳学习算法，通常用来形成分类器和产生预测模型， 可以对未知数据进行预处理、分类、预测或挖掘等。决策树算法通常由两部分构成：树的 生成和树的剪枝。建树算法通过递归过程最终得到一棵决策树；剪枝是为了降低噪声数据 对分类正确率的影响，对树中的分枝作修剪。 2 2 1 决策树的生成 对一个分类或规则学习问题，决策树的生成是一个从上至下、分而治之的过程，它的 生成算法本质上是一个贪心算法。从根节点开始，对每个非叶节点，找出对应样本集中的 一个属性( 也称为测试属性) 对样本集进行测试，根据不同的测试结果将训练样本集划分成 若干个子样本集，每个子样本集构成一个新叶节点，对新叶节点再重复上述划分过程，这 样不断循环，直至达到特定的终止条件。形成的决策树中，内部节点是属性或属性的集合， 叶节点是所要学习划分的类。其中，测试属性的选择及如何划分样本集是构建决策树的关 键环节，不同的决策树算法在此使用的技术也不尽相同。 决策树生成算法如下： 输入：节点n ，数据集d ，分割方法( s p l i t t i n gs e l e c t i o nm e t h o d ) s s m 输出：以节点n 为根节点的基于数据集d 、分割算法s s m 的决策树 p r o c e d u r eb u i l d t r e e b e g i n 初始化树的根节点； 在d 中计算s s m 来求解节点n 的分割标准( s p l i t t i n gc r i t e r i o n ) ； i f ( 节点n 满足分割条件) 选择最好的效果将d 分为d i ，d 2 ； 创建节点n 的子节点n l 、n 2 ； b u i l d t r e e ( n i ，dl ，s s m ) ； 6 南京邮电人学颀j ：研究生学位论义第一二章决策树算法的分析j 研究 e n d b u i l d t r e e ( n 2 ，d 2 ，s s m ) ； e n di f 2 2 2 决策树的剪枝 如果决策树构造的过于复杂，那么对于用户来说这个决策树是难以理解的，将在很大 程度上使得分类树的构造没有意义；而决策树构造的越小，其存储所花的代价越小，对它 的某些操作相对来说也就越简单省时。因此，应该在保证正确率的前提下尽量构造简单的 决策树。简化决策树的方法很多，剪枝是最常用的一种，主要通过在训练过程中明确控制 树的大小来简化决策树。此外，当决策树创建时，由于数据中噪声和孤立点的影响，许多 分枝反映的是训练数据中的异常，剪枝方法也可以处理这种过分适应( o v e r - f i t t i n g ) 数据问 题。 决策树修剪的方法总体上可分为两类：一类是在建树过程中修剪( p r e p r u n i n g ) ，方法 是在决策树完全建立前终止生长，以避免过度匹配问题的出现；另一类是在建树后修剪 ( p o s t p r u n i n g ) ，其基本思想是首先完全建成整棵决策树，在建树过程中允许过度匹配现象 的出现，然后对决策树进行修剪，来消除过度匹配的问题。使用前一种方法往往会丧失一 些有用的结论，而这些结论往往在决策树完全建成以后才会被发现，而且，在确定何时终 止决策树生长时遇到很大的问题，所以目前使用最多的是后剪枝方法。 后修剪算法分为两类：一类是首先生成一组决策树然后从中选择最佳决策树，这类算 法以最小代价复杂性修剪算法( m i n i m a lc o s t - c o m p l e x i t yp r u n i n g ) 3 q 为代表；一类是直接 对原来的决策树进行修剪，这类算法以减少分类错误修剪算法( r e d u c e de r r o rp r u n i n g ) 3 2 1 、 基于决策树大小的悲观修剪算法( p e s s i m i s t i cp r u n i n g ) 3 3 1 和m d l 修剪算法 3 4 1 为代表。此外， 还有基于错误的修剪算法( e r r o rb a s e dp r u n i n g ，e b p ) t 3 5 】和最小误差修剪算法( m i n i m a l e r r o r p r u n i n g ，m e p ) 3 5 1 等算法。下面分别介绍以上几种算法的优缺点。 最小代价复杂性算法。定义了代价复杂性函数，作为决策树修剪效果时的度量函数。 若修剪后的代价复杂性参数的值降低，则修剪掉该节点，否则保留该节点。修剪算法效果 不错，但是计算量很大，复杂度参数的选取也很大程度上依赖于使用者的经验。 1 、减少分类错误修剪算法。该算法利用决策树对测试样本集分类效果作为决策树修 剪效果的度量函数，其具体的修剪过程如下：对于每一个节点，对该节点样本进行类别统 计，将该节点修剪为叶子节点，节点的类别取为该节点大多数样本所属的类，然后利用测 南京邮i 【1 人学顾l ：研究生学位论文 第一二章决策树算法的分析j 研究 试样本集合判断修剪后的分类效果，并和修剪以前作比较，如果分类效果增高，则修剪掉 该节点，否则不修剪。这种修剪方法的效果很好，修剪后规则数明显下降而对测试样本的 分类准确率有所上升，一定程度上解决了决策树的过度适合的问题，经典算法c 4 5 采用的 就是这种修剪方法。 2 、基于决策树大小的悲观修剪算法。该修剪算法利用决策树的子树对训练数据的误 差去估计该决策子树的真实误差，当修剪掉一个节点引起的误差的变化在统计意义上不重 要时，就修剪掉该节点和它下面的决策树分支。算法的优点是只需要遍历一次决策树，算 法效率比较高，而且不需要测试数据集；不足是如果算法中的参数取值过大，对决策树的 修剪会过多，反而使得决策树的分类效果下降。 3 、基于错误的修剪算法。该算法是对悲观修剪算法一通过估计节点修剪前后，出 现分类错误可能性的大小来决定是否对节点进行修剪，修改了剪枝规则的改进算法。 4 、最小误差修剪算法。类似与悲观修剪算法，不同的是对分类误差可能性的评价准 则不同。有两种估计方法：拉普拉斯估计( l a p l a c ee s t i m a t e ) 和历估计( m e s t i m a t e ) 。拉普拉 斯估计，假定所有的k 类都有同样的先验概率，而这往往是和实际情况不相符的，利用这 种估计方法修剪，其修剪的程度依赖于样本类别的多少。m 估计，考虑了样本所属不同类 别的先验概率；对样本类别总数不敏感；另外，不同的m 可以得到不同的决策树，m 的取值 取决于对训练样本的置信程度( c o n f i d e n c e ) ，如果样本中噪声很低，则选择小的取值，否则 选择高的取值。 5 、m d l 修剪算法。在利用训练样本建立的所有决策树中，可以用最少的比特数编码 的决策树是最好的决策树。算法就是将初始建成的决策树修剪为可以被最少比特数编码的 决策树。m d l 修剪算法得到的决策树非常简单，但是相应的分类准确率也不高，存在过度 修剪的现象。 综合以上考虑，本文在后续的实验中，采用减少分类错误修剪算法对通过i d 3 算法生 成的决策树作剪枝，以减少噪声数据的影响，以此来和本文提出的基于分类质量的变精度 1 7 1 3 3 算法作比较。 2 3 决策树的性能评价 在决策树的学习算法中，决策树的复杂度和分类精度是需要考虑的两个最重要因素， 下面是决策树的性能评价标准3 6 1 ： 1 、预测准确度：描述分类模型准确预测新的或未知的数掘类的能力； 塑翌型! 垦奎兰竺主丝! ! 竺兰竺丝圣 墨= 兰堡要型墨竺型丝塑兰竺塾 2 、描述的简洁性：模型描述越简洁，也就越易于理解，同时也就越受欢迎； 3 、计算复杂性：当操作对象是巨量的数据库时，空间和时间的复杂性问题将是非常 重要的一个环节，将直接影响生成与使用模型的计算成本； 4 、模型强健性：存在噪声及数据缺损的情况下，准确对求知其类的数据进行分类的 能力； 5 、处理规模性：处理规模性是指在巨量数据的情况下构造模型的能力以及构造分类 模型的精确度。 2 4i d 3 算法及其改进算法 2 4 1i d 3 算法概述 i d 3 算法【4 1 是决策树算法的代表，绝大多数决策树算法都是在它的基础上加以改进而实 现的。本文主要讨论i d 3 算法，论文的工作也是围绕i d 3 算法展开的。 根据信息论知识表明：系统的不确定性越小，信息的传递就越充分。q u i n l a n 将信息论 引入到了决策树算法中，提出了基于信息熵的决策树学习算法一i d 3 算法。i d 3 算法采用 信息增益作为属性划分样本集的不确定性标准，即算法在每个非叶节点选择信息增益最大 的属性作为测试属性。 i d 3 算法原理如下： 设s 是s 个样本的集合，假定类别属性具有m 个不同值，定义m 个不同类c ( f = 1 ，m ) 。 设s ，是类c ，中的样本数。对一个给定的样本集，总的信息熵值由公式2 1 给出： l ( s l ，s 2 ，s 。) = 一p fl 0 9 2 ( p ，) ( 2 1 ) 其中p 。是任意样本属于c i 的概率，并用s ，s 估计。 设属性彳具有1 ，个不同值，属性彳将洌分为外子集确，最，乱) ，其中q 包含s 中这样 一些样本，它们枷上具有口，值。如果选择么作为测试属性，则这些子集就是从代表样本集 s 的节点生长出来的新的叶子节点。设& 是子集一中类别为e 的样本数，则根据么划分样 本的信息熵由公式2 2 给出： 南京i | | l ；l 【1 人学颂i ：研究生学位论文第二帝决策树算法的分析u o f 究 刚) = 喜型字岛( s | j , s 2 j , , s m j ) ( 2 2 ) 其中“s l y , s 2 j , , s , j ) _ 一善p 0 l o g zp f ；p u2 尚是s j 中类为e 的样本的概率。最 后，属性4 划分样本集踞所得的信息增益值有公式2 3 给出。 g a i n ( a ) = i ( s l ，最，鼠，) 一日( 4 ) ( 2 3 ) i d 3 算法选择使g a i n ( a ) 具有最大值的属性作为该节点的扩展属性( 测试属性) ，对于决 策树的每个节点使用这条原则直到决策树建立完毕( 每个节点中的样本都属于同一类或者 所有的分类属性都用完) 。可以看出，决策树算法是自上而下、分而治之的，只要选好属 性选择的准则，决策树就可以很快建成。 i d 3 算法的描述如下： t 代表当前训练样本集，当前的候选属性集用ta t t r il i s t 表示，候选属性集中的所有属 性皆为离散型，连续值属性必须事先经过预处理转化为离散型。 算法：g e n e r a t ed e c i s i o nt r e e 由给定的训练集产生一棵决策树 输入：训练集t ，属性集合ta t t r il i s t 输出：一棵决策树 1 ) 创建根节点n ； 2 ) 如果t 都属于同一类c ，则返回n 为叶节点，标记为类c ； 3 ) 如果a t t r il i s t 为空，则返回n 为叶节点，标记n 为t 中出现最多的类； 4 ) 对于a t t r il i s t 中的每个属性，计算信息增益g a i n ； 5 ) n 的测试属性t e s ta t t r i 为ta t t r il i s t 中具有最高g a i n 值的属性； 6 ) 对于t e s ta t t r i 的不同取值： f 由节点n 长出一个新叶子节点； i f 新叶节点对应的样本子集t 为空， 不再分裂此子节点，将其标记为t 中出现最多的类； e l s e 在该叶节点上执行 g e n e r a t e _ d e c i s i o n _ t r e e ( t ，t _ a t t r i _ l i s t ) ，继续对它分裂。 ) l o 南京邮i 【1 人学硕i ：t 0 d t 生学位论文 第二章决策树算法的分析j 研究 2 4 2i d 3 算法的研究现状 i d 3 算法的不足： ( 1 ) i d 3 算法偏向于选择属性值较多的属性，而属性值较多的属性不总是最优的属性。 ( 2 ) 学习简单的逻辑表达能力较差。 ( 3 ) 算法对噪声数据敏感。 ( 4 ) i d 3 算法对于增量式学习任务来说，由于不能增量地接受训练例，这使得每增加 一次实例都必须抛弃原有的决策树，重新构造新的决策树，造成极大的开销。 ( 5 ) 注意力集中在属性的选择上，而最近有研究者认为属性选择对决策树的精度影响 不大，这一问题至今仍无定论。 针对i d 3 算法存在的不足，研究者提出了各种不同的解决方法：通过将属性和值组 合起来作为新的属性来考虑，解决了i d 3 算法的偏向选择具有较多属性值属性的不足； 通过对属性计算两次信息增益来选择测试属性，使i d 3 算法增强了学习简单逻辑表达能 力；通过引入粗糙集神经网络思想，增强i d 3 算法抗噪声的能力；等等。总结起来，主 要集中在如下几个方向： ( 1 ) 扩充决策树属性的取值范围及改进选择分离属性的选择； ( 2 ) 提高决策树构造效率，削减数据库遍历次数，减少i o 操作； ( 3 ) 优化决策树，简化决策树输出； ( 4 ) 扩充决策树，形成决策图； ( 5 ) 决策树算法与智能算法、技术的结合，如：遗传算法、神经网络技术。 将决策树算法应用到实际中去解决实际问题是算法研究的最终目的，考虑到现实中的 数据存在大量不一致、不确定性，算法在实际的应用中必然要具有抗干扰的能力。变精度 粗糙集通过设置阈值参数( 分类正确率，0 5 l - p 的边界域： 引忪：( z ) = u 石e ( p ) ) ( 3 3 ) l - , 8 p ( z l x i ) p 当胪1 时，v p r s 就是原始( 或经典) 的粗糙集模型，因此r s 模型是v p r s 模型的一个特例。 在相同的条件下，随都的减小，边界区域也逐渐减小即不确定区域降低了，可见v p r s 对 噪声有一定的容错能力。 对于任意口c ，如果p o s y ( z ) = p o s p c _ ( z ) ，则可以认为口是冗余属性，称 c = c 一 a ) 为c 的一个约简。 2 、近似分类质量 定义2 设尸c ，( o 5 ，1 】，分类质量y 卢( p ，d ) 定义为 c a r d ( u 石e ( p ) ) ) 九只d ) - 鼍施r ( 3 4 ) 式中y p ( p , d ) 仅依赖瑚，近似分类质量度量了论域中给定某_ 卢值时，可能正确的 分类知识在现有知识中的百分比。 在考虑分类正确, f l ( o 5 哪1 ) 存在的情况下，依据近似分类质量的标准对属性进行约 简。 定义3 条件属性帙于决策属性d 的近似约简应满足 y ( p ，d ) = y 卢( r e d ( c ，d ) ，d )( 3 5 ) 1 4 南京邮【1 人学顾i j 研究生学位论义第三章皋于分类质量的变精度1 d 3 算法 r e d ( c ，d ) 是条件属性c 对决策属性d 的一个近似约简，即r e d ( c ，d ) 中条件属性的等价 类与未约简前条件属性的等价类一致，从r e d ( c ，d ) 中去掉任何一个属性，都将使上式不成 立，显然，用近似约简进行归类与用整个条件属性集归类在数目上能够保持相同。 3 、属性重要性 定义4q = cud ，c s b 条件属性集，d 为决策属性集，a c ，( 0 5 ，l 】，属性口关 于d 的重要性定义为 s g f ( a ，c ，d ) = y 卢( c ，d ) 一y p ( c 一 口) ，d ) ( 3 6 ) 其中，y ，( c 一 口 ，d ) 表示在c 中缺少属性口后的分类质量，s g f ( a ，c ，d ) 0 ，1 表示c 中缺少属性口后，导致不能被准确分类的对象在系统中所占的比例，若等于0 表示属性a 关 于d 可省略，反之不可省略。 设属性口对分类的影响为y ，( 口，d ) ，若存在两个属性的重要性相同，则可利用公式( 3 7 ) 来加以区分。 s g f ( a ，c ，d ) = t p ( c ，d ) 一y p ( c 一 口) ，d ) + y a ( 口，d )( 3 7 ) 4 、条件属性c 相对于决策属性d 的核定义 若条件属性集rsc ，r 中每一个属性c c 都是相对于决策属性集d 是必要的，则称尺 是相对于d 独立的。如果月相对于d 独立的，g e o s 岩( d ) = p o s 口c ( d ) ，则称尺是c 中相对于 d 的约简，记为r e d d ( c ) ，所有这样约简的交集称为条件属性c 相对于决策属性d 的核，记 为 c o r e d ( c ) = f l r e d d ( c )( 3 8 ) 5 、属性约简 现实中的数据大多存在数据不一致，噪声，冗余等情况，离理想数据差距很大，因此， 属性约简是在运用分类算法之前对数据预处理的重要一步，该步骤中数据处理的精度将影 响到后续建树阶段的工作量，但在去除冗余属性后并不会影响原有的分类效果。 当前的属性约简算法有： 1 、典型的属性约简方法：p a w l a k 教授提出的特征约简与值的约简概念的最小约简 基于属性重要性的约简方法【3 8 】。 根据每个属性的重要程度来对属性进行约简。利用这个算法，采用一定的搜索策略可 l5 阿京邮【1 人学帧j j 研生学位论义 第三币暴十分类质量的变精度i d 3 算法 得到所有可能的约简结果，然后从中选择一个较好的方案。不幸的是要得到所有可能的约 简结果会产生组合爆炸，用于