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

摘要 决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次 序、无规则的事例中推理出决策树表示形式的分类规则，在机器学习、 数据挖掘、智能控制等人工智能领域有着相当重要的理论意义与实用价 值。 本文主要对决策树的生成算法进行了研究，并取得了一些有意义的 结论。 在决策树算法的分析与比较方面，文中对i d 3 算法和c 4 5 算法进 行了描述，并对他们的优缺点进行了分析和比较。i d 3 算法往往偏向于 取值较多的属性，不能处理连续数据，对噪声也较为敏感。c 4 5 算法 是对i d 3 算法的优化，可以对连续值属性进行处理，同时增加了对空值 数据的处理，但是c 4 5 更偏向于选择熵值最小的属性，而并不一定是 对分类贡献最大最重要的属性。 在测试属性的选择方面，文中首先分析了当利用条件属性对样本集 进行划分时，如何得到正确划分的支持程度，即条件属性对数据进行正 确决策的能力，根据这样的思想，定义了决策支持度的概念，并将相对 于决策属性利用条件属性能区分的元素对数在总的需要区分的元素对 数中所占的比值作为决策支持度的度量。利用决策支持度可以找到对正 确决策贡献最大的属性。以该度量为启发式信息，提出了一种基于决策 支持度的决策树生成算法，利用该算法得到的决策树规模较小，分类精 度较高。 在对不完备信息系统中缺值数据的处理方面，现有的决策树算法大 多都使用了猜测的技术，对缺失的值进行补值再建立分类模型，但是预 测的值却不定是正确的。因此我们在不改变缺失值的情况下，利用极 大相容块的技术定义了不完备决策表中条件属性对决策属性的决策支 持度，并用决策支持度去选择测试属性，使得在不完备系统中可以找到 对正确决策贡献最大的属性，同时提出了一种在不完备信息系统中生成 决策树的方法。 本文围绕基于决策树的分类方法，定义了决策支持度的概念，并分 别在完备的和不完备的信息系统中提出了决策树构造算法。对不完备的 信息系统利用极大相容块技术作了一些尝试性工作，今后还需进一步深 入研究。 关键词：决策树；信息熵；决策支持度；不完备信息系统；极大相容块 中图分类号：t p l 8 1 r e s e a r c ho nt h ec l a s s i f y i n ga l g o r i t h mb a s e do nd e c i s i o nt r e e g u a nx i a o q i a n g ( c o m p u t e rs o f t w a r e & t h e o r y ) d i r e c t e db yp r o f l i a n gj i y e a b s t r a c t l e a r n i n ga l g o r i t h mo f d e c i s i o nt r e eb a s e so nt h ei n s t a n c e s ，a n df o c u s e s o nd e d u c i n gc l a s s i f i c a t i o nr u l e sr e p r e s e n t e db yd e c i s i o nt r e ef r o mag r o u po f o u t - o f - o r d e ra n do u t - o f - r u l es a m p l e s a n dt h ed e c i s i o nt r e eh a ss i g n i f i c a n t t h e o r e t i c a la n dp r a c t i c a lv a l u ei nt h er e s e a r c hf i e l d so fa r t i f i c i a li n t e l l i g e n c e ， s u c ha sm a c h i n el e a r n i n g ，d a t am i n i n ga n di n t e l l i g e n tc o n t r 0 1 i nt h i sp a p e rt h ea l g o r i t h mo fb u i l d i n gd e c i s i o nt r e ei sd i s c u s s e da n d r e s e a r c h e d ，a n ds o m es i g n i f i c a n tc o n c l u s i o n sa r ea c h i e v e d f r o mt h ep o i n to fv i e wo fa n a l y z i n ga n dc o m p a r i s o no ft h ed e c i s i o n t r e ea l g o r i t h m s ，t h ec l a s s i c a la l g o r i t h m so f l d 3a n dc 4 5a r ed e s c r i p t e d ，t h e n t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft w oa l g o r i t h m sa r ea n a l y z e da n d c o m p a r e d t h ea l g o r i t h mo fi d 3u s u a l l yl e a n st os e l e c ta t t r i b u t e sw h i c h v a l u em u c hm o r e ，a n dc a n th a n d l ec o n t i n u o u sd a t a ，a n di ss e n s i t i v i t yt ot h e n o i s e t h ea l g o r i t h mo fc 4 5i sa no p t i m i z e do n eb a s e do nt h ei d 3 a l g o r i t h m i tc a np r o c e s st h ea t t r i b u t e sw h i c hh a v ec o n t i n u o u sv a l u ea n d e m p t yv a l u ed a t a w h e r e a st h ec 4 5a l g o r i t h mt e n d st os e l e c tt h ea t t r i b u t e w i t hm i n i m u me n t r o p yv a l u e ，n o tt h a tc o n t r i b u t e sm o s tt oc l a s s i f i c a t i o n a sf o rt h es e l e c t i o no ft e s ta t t r i b u t e ，w ea n a l y s e sh o wt oa c q u i r et h e s u p p o r td e g r e eo fc o r r e c tp a r t i t i o ni nt h ec a s eo f p a r t i t i o n i n gt h es a m p l ed a t a s e tw i t hc o n d i t i o na t t r i b u t e s a n dt h es u p p o r td e g r e ei st h ec a p a b i l i t yo f m a k i n gt h ec o r r e c td e c i s i o n sw i t ht h ec o n d i t i o na t t r i b u t e s b a s e do nt h ei d e a a f o r e m e n t i o n e d ，t h es u p p o r td e g r e eo ft h ed e c i s i o n si sd e f i n e da st h er a t i oo f t w on u m b e r so fp a i r s ，a n do n ei st h en u m b e ro fp a i r so fe l e m e n t sw h i c ha r e d i s t i n g u i s h a b l eu s i n gt h ec o n d i t i o na t t r i b u t e w i t hr e s p e c tt ot h ed e c i s i o n a t t r i b u t e ，t h eo t h e ri st h en u m b e ro fp a i r so fe l e m e n t sn e e d e dt ob e d i s t i n g u i s h e di nt h ew h o l ed a t as e t a n dt h ea t t r i b u t ec o n t r i b u t i n gm o s tt o t 1 1 ec o r r e c td e c i s i o nw i l lb ef o u n do u tw i t ht h es u p p o r td e g r e eo fd e c i s i o n w ep r o p o s ean o v e la l g o r i t h mo fb u i l d i n gd e c i s i o nt r e eb a s e d o nt h es u p p o r t d e g r c eo fd e c i s i o nw i t ht h i s m e a s u r e m e n ta sh e u r i s t i ci n f o r m a t i o n ，t h e a u t h o ra d v a n c e sas o r to fb u i l d i n gd e c i s i o nt r e ea r i t h m e t i cb a s e do nd e g r e e o fd e c i s i o nt r e e t h es i z eo ft h ed e c i s i o nt r e eg e n e r a t e db yt h ea l g o r i t h mi s s m a l l e r , a n dt h ea c c u r a c yo fc l a s s i f i c a t i o ni sh i g h e r w h e np r o c e s s i n gt i l ed a t aw i t hm i s s i n gv a l u ei n t h ei n c o m p l e t e i n f o r m a t i o ns y s t e m ，m o s to ft h ee x i s t i n gd e c i s i o nt r e ea l g o r i t h m su t i l i z et h e t e c h n o l o g yo fg u e s s i n g ，a n dr e f i l lt h em i s s i n g v a l u ed a t aa n dt h e nc o n s t r u c t t h ec l a s s i f i e rm o d e l ，w h i l et h ep r e d i c t i o nv a l u ei sn o ta l w a y sc o r r e c t s oi n t h ec a s eo fw i t h o u tc h a n g i n gt h em i s s i n gv a l u ed a t a ，w ed e f i n et h ec o n d i t i o n a t t r i b u t e ，ss u p p o r td e g r e eo f d e c i s i o nw i t hr e s p e c tt ot h ed e c i s i o na t t r i b u t ei n t h e i n c o m l c i l e t e i n f o r m a t i o ns y s t e mw i t ht h et e c h n o l o g y o fm a x i m a l c o n s i s t e n tb l o c k b yt h ec o n c e p to ft h es u p p o r td e g r e eo fd e c i s i o n ，t h e a t t r i b u t ec o n t r i b u t i n gm o s tt ot h ec o r r e c td e c i s i o nc a nb es e l e c t e d m o r e o v e r w ep r o p o s ea na l g o r i t h mo fg e n e r a t i n gd e c i s i o nt r e e i nt h ei n c o m p l e t e i n f o r m a t i o ns y s t e m b a s e do nt h ec l a s s i f i c a t i o na p p r o a c h e so fd e c i s i o nt r e e ，t h ec o n c e p to f s u p p o r td e g r e eo fd e c i s i o ni sd e f i n e d ，a n dt h ea l g o r i t h m s o fc o n s t r u c t i n g d e c i s i o nt r e ei nc o m p l e t ea n di n c o m p l e t ei n f o r m a t i o ns y s t e ma r ep r o p o s e d r e s d e c t i v e l v s o m ee x p l o r a t o r yw o r ko nu s i n gt h et e c h n o l o g yo fm a x i m a l c o n s i s t e n tb l o c ki nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mi sa c c o m p l i s h e da n d j ts t i 】1n e e d st od of u r t h e rr e s e a r c h k e y w o r d s ：d e c i s i o nt r e e ；i n f o r m a t i o ne n t r o p y ；s u p p o r td e g r e e o f d e c i s i o n ：i n c o m p l e t ei n f o r m a t i o ns y s t e m ；m a x i m a l c o n s i s t e n tb l o c k 第一章引言 第一章引言 1 1 选题背景和意义 随着计算机和信息时代的到来，人们收集、存储和访问的数据急剧增加，对这 些快速增长的海量数据进行分析和知识理解已经远远超出了人的能力。大量的数据 被描述为“数据丰富，但信息贫乏”“1 。数据库规模日益扩大，仅依靠数据库管理 系统的查询检索机制和统计分析方法，已经远远不能满足现实的需要。而大量激增 的数据中往往又隐藏着许多重要的信息，如果能把这些信息从数据库中提取出来， 就能为用户创造很多潜在的利润。因此，对大量历史数据进行分析处理，挖掘出有 用的知识就显得非常迫切。 传统的查询技术不能解决目前面临的信息爆炸问题，如何有效地管理，怎样才 能有效地利用数据库中数据，以及怎样才能发现其潜在的知识，这就需要有新的、 更为有效的手段来对各种数据源整理并进行挖掘，以发现新的知识并发挥这些数据 的潜能。8 0 年代末兴起的数据库中的知识发现( 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 ， k d d ) 及其核心技术数据挖掘( d a t a m i n i n g ) 正是在这样的应用需求下产生并 迅速发展起来的一门技术。 数据库中的知识发现是从数据库中识别出有效的、新颖的、潜在有用的，以及 最终可理解的模式的非平凡过程”1 。数据挖掘是知识发现的一个核心步骤。数据挖 掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数据挖掘是在没 有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先前未 知，有效和可实用三个特征。先前未知的信息是指该信息是预先未曾预料到的，即 数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知 识，挖掘出的信息越是出乎意料，就可能越有价值。 知识发现的过程可以粗略地分为三个阶段”1 ： l 、数据准备 数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。数据选取 的目的是确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ，它是根据用户的需 要从原始数据库中抽取的一组数据。数据预处理一般可能包括消除噪声、推导计算 缺值数据、消除重复记录、完成数据类型转换等。当数据开采的对象是数据仓库时， 一般来说，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是消减 数据维度或降维，即从初始特征中找出真正有用的特征以减少数据丌采时要考虑的 基子决策树的分类算法研究 特征或变量个数。 2 、数据挖掘阶段 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、分类、聚类、 关联规则或序列模式发现等。确定了挖掘任务后，就要决定用什么样的挖掘算法。 选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相 关的算法来挖掘；二是用户或实际运行系统的要求。完成了上述准备工作后，就可 以实施数据挖掘操作了。 3 、结果的解释和评价 数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或无关 的模式，这时需要将其剔除；也有可能模式不能满足用户要求，这时则需要整个发 现过程退回到发现阶段之前重新开始。另外，由于知识发现最终是面向人类用户的， 因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另- - , e e 表示。 目前知识发现和数据挖掘技术己经成为计算机界新的研究热点之一，引起数据 库、机器学习、统计等领域专家的广泛关注。数据挖掘的方法多种多样，包括分类、 预测、聚类、关联规则挖掘、序列模式挖掘等，其中分类问题是被广泛研究的课题 之一，在商业中应用最多。分类是指把数据项映射到一个事先定义的类中的学习过 程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类”1 。 分类学习的目标是构建一个分类模型。它在构造模型时需要知道训练集中每个样本 所属的类，因此是有指导的学习方法。分类研究在国外发展很快，己有很多成型的 算法和模型，而在国内发展相对滞后，因此，研究数据分类对数据挖掘技术有很大 的意义。 数据挖掘中广泛使用的分类方法有决策树、贝叶斯分类、规则推理、遗传算法 和神经网络等。其中决策树方法是一种较为通用并深入研究的分类函数逼近法。它 是一种常用于预测模型的算法，通过将大量数据有目的的分类，从中找到一些具有 价值的、潜在的信息。相对于其它分类方法，决策树算法应用最为广泛，其独特的 优点包括“： 1 、学习过程中使用者不需要了解很多背景知识，只要训练事例能够用属性一 结论的方式表达出来，就能用该算法进行学习； 2 、决策树的训练时间相对较少，其它的分类方法如神经网络，即使对小数据 集也要花费很多的训练时削； 3 、与神经网络或贝叶斯分类等其他分类模型相比，决策树的分类原理简单易 ， 第一章0苦 懂，很容易被使用人员理解和接受； 4 、决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式； 5 、可以将决策树中到达每个叶子结点的路径转换为i f t h e n 形式的分类规则， 这种形式更有利于理解； 但决策树方法也存在着缺点： 1 、随着数据复杂性的提高，其分支也增多，增加了管理上的困难； 2 、分类数据的预处理工作，不仅增加了算法的额外开销，而且降低了分类的 准确性； 3 、存在缺值处理问题； 目前，已有多种决策树算法，如c l s ，i d 3 ，c h a i d ，c 4 5 ，c a r t ，s l i q ， s p r i n t 等。各种决策树算法的主要区别在于测试属性的选择、决簧树的结构及剪 枝策略的不同。 1 2 国内外的研究现状 最早的决策树学习系统要追溯到h u n teb 于1 9 6 6 年研制的一个概念学习系统 ( c l s ：c o n c e p tl e a r n i n gs y s t e m 系统) ，该系统第一次提出使用决策树进行概念学 习，是许多决策树学习算法的基础。 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 ) 分类方法“3 是由b r e i m a nl ， f r i e d m a nj h 和o l s h e n r a 等人在1 9 8 4 年提出的一种决策树分类方法。这种方法选 择具有最小基尼指数值的属性作为测试属性，最终生成二叉树，然后利用重采样技 术进行误差估计和树剪枝( 基于最小代价复杂性) ，然后选择最优的作为最终构建的 决策树。这些算法均要求训练集全部或一部分在分类的过程中一直驻留在内存中。 1 9 8 6 年，q u i n l a njr 提出了i d 3 ( i t e r a t i v ed i c h o t o m i z e r3 ) 算法”1 ，在该算法中， 引入了信息论中熵的概念，利用分割前后的熵来计算信息增益，在决策树中各级结 点上选择属性，使得在每一非叶结点进行测试时，能获得关于被测试例子最大的类 别信息。该算法利用窗口技术逐步形成完整的决策树，因此其学习能力较强，适于 处理大规模的数据库问题，但该算法仍存在着一些缺点，如不能够处理连续属性， 计算信息增益时偏向于选择取值较多的属性等。针对这些问题，学者们提出了一系 列改进算法。 1 9 9 3 年q u i n l a nj r 提出了c 4 5 算法”3 ，该算法可以看作是i d 3 算法的一个扩 展，旨在克服i d 3 算法在应用中的不足，该算法采用信息增益作为属性的选择标准， 摧于决策树的分类算法研究 它继承了i d 3 算法的全部优点，同时解决了i d 3 算法偏向于取值较多的候选属性的 问题。 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 ) 分类方法。1 是m e h t am ，a g r a w a lr 和 r i s s a n e nj 等人在1 9 9 6 年提出的一种高速可伸缩的分类方法，它针对数据量远大于 内存容量的情况采用了类表和属性表两种数据结构，利用换入换出策略处理大数据 量。 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 k e s ) 分类方法”是由 s h a r e rj ，a g r a w a lr 和m e h t am 等人在1 9 9 6 年，继s l i q 分类方法后提出的一种规 模可变的、支持并行计算的分类方法。s p r i n t 分类方法最大的优点就是可以避免 内存空问的限制，利用多个并行处理器构造一个稳定的、分类准确率很高的决策树， 具有很好的可伸缩性，扩容性，但该算法因使用属性列表，使得存储代价大大增加， 并且结点分割处理的过程较为复杂，加大了系统的负担。 1 9 9 8 年，r a s t o g ir 等人提出一种将建树和树的调整阶段集成在一起的p u b l i c 算法1 ，该算法提出了结点代价的目标函数，其主要思想是在决策树建立阶段，计 算每个结点相关的目标函数值，估计该结点在将来调整阶段是否被删除。如果该结 点将被删除，则不对该结点进行扩张，否则，扩展该结点。从而建树和修剪阶段结 合成为一个阶段，而不是依次执行这两个阶段，提高了决策树的执行效率。 r a i n f o r e s t 分类方法“”是由g e h r k ej ，r a m a k r i s t m a nr 和g a n t iv 等人在1 9 9 8 年提出的一种针对大规模数据集，快速构造决策树的分类框架。r a i n f o r e s t 分类框 架的核心思想是根据每一次计算所能使用的内存空间，合理地调整每次计算所处理 的数据集的大小，使r a i n f o r e s t 框架内所使用的分类方法在每次计算的过程中，对 内存资源的利用率达到最大，在有限的资源下，用最少的时间完成决策树的构建。 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 还提出3 种不同的寻找连续属性的局部阈值的改进 策略。实验表明，在生成同样一棵决策树时，与c 4 5 相比e c 4 5 可将效率提高5 倍，但e c 4 5 占用内存比c 4 5 多“。 在特征属性选择的问题上，1 9 9 8 年刘小虎等学者在选择一个新属性时，并不仅 仅计算该属性引起的信息增益，而是同时考虑树的两层结点，即选择该属性后，继 续选择属性带来的信息增益“”；洪家荣等学者在分枝属性的选择上仍采用基于信息 增益率的方法，但在树的扩展过程中，采用属性聚类的方法进行分枝合并“等。 1 9 9 7 年苗夺谦等利用粗糙集理论中条件属性相对于决策属性的核，解决多变量 第一章引言 检验中属性的选择问题。另外，定义了两个等价关系相对泛化的概念，并将它用于 解决多变量检验的构造问题“”。2 0 0 4 年蒋芸等基于粗糙集的理论提出了加权平均粗 糙度的概念，将其作为选择分离属性的标准“，用该方法构造的决策树与传统的基 于信息熵方法构造的决策树相比较，复杂性低，且能有效提高分类效果。2 0 0 5 年黄 定轩等提出一类加权连续属性的多变量决策树构造方法“，首先利用粗集理呛和模 糊聚类理论确定连续多变量属性的选择问题，然后利用聚类中心算法建立等级标准 中心以解决连续变量的区间划分问题，其次将等价关系相对泛化的概念用于决策树 中多变量检验的构造。 吴菲，黄梯云于1 9 9 9 年采用遗传算法构造二元决策树“0 1 对数据进行特征识别， 根据识别的结果选择模型，并以趋势预测模型为例进行了验证：2 0 0 5 年张拮等提出 一种基于遗传算法的多重决策树组合分类方法”“，该算法与单个决策树相比，具有 更高的分类精度。 o l a r u c 于2 0 0 3 年提出了一种新的模糊决策树方法软决策树。软决策树 综合决策树的生成和修剪来决定其本身的结构，并利用重修和磨合来提高树的归纳 能力。软决策树比一般决策树的正确率要高。 目前决策树技术的主要研究方向有以下几点： 1 、决策树的精度 决策树的预测精度一直是研究的重点，判断各种决策树的生成算法和剪枝算法 的优劣，精度是最重要的衡量指标。构造多变量决策树是为了减小树的规模，其最 终目的是为了提高决策树的精度。如何提高决策树的预测精度是决策树方法的研究 方向之一。 2 、决策树技术与其他技术的结合 在知识发现中，不可能用一种方法处理所有的数据集，完成各种数据采掘任务， 需要研究同其它方法相结合的问题。并且，决策树方法本身也可以和其它方法结合， 现在已有人把决策树方法同神经网络技术、模糊集理论、遗传算法等相结合来进行 研究，结果不同程度地提高了处理效率和精度。多种方法的交叉结合也是决策树方 法研究的方向之一。 3 、寻找更好的简化决策树方法 简化决策树的研究工作主要有两个方面，一是对比各种不同的简化决策树方 法，分析它们各自的特性、优点和缺点。另外一个就是寻找更好的与传统方法不同 的简化决策树的方法，这一直是决策树技术研究的一个热点。 基于决策树的分类算法研究 4 、研究产生决策树的训l 练和检验数据的大小及特性与决策树特性之间的关系。 这类研究着眼于产生决策树的数据。训练数据的增加经常造成决策树大小的线 性增加，而这种增加并没有都带来决策树准确性的提高。一些专家认为，在产生决 策树前尽量减少数据量比在决策树产生后再简化决策树更加有效，这就是数据预处 理技术。 5 、不确定环境下决策树研究 实际的数据集中存在着一些缺值数据，最简单的方案是删除带有未知属性值的 例子或是将未知属性值用最常用的值代替，q u i n l a njr 提出的一种解决方案是依据 对象的其它属性值和类信息来预测未知属性的属性值。对缺值数据的处理一直是决 策树研究的热点。 6 、决策树技术的软件实现 将决策树技术软件化一直是决策树技术的方向之一。如何开发出功能更加强 大、使用更加方便、界面更加友好的软件以实现决策树技术，一直是大家努力的方 向。 1 3 本文结构 本文主要针对决策树分类算法的改进做了一些探索性的工作，本文的组织如 下： 第一章为引言部分，介绍了知识发现的基本概念，并对选题的意义、国内外的 研究现状等进行了综合论述。 第二章介绍了决策树的概念，并对决策树的典型算法进行了分析与比较。 第三章定义了决策支持度的概念，根据决策支持度提出了一种新的决策树生成 算法。 第四章将决策支持度概念扩展到不完备决策系统中，并得到了一种在不完备信 息系统中用决策树获取规则的方法。 最后，概括了本文的主要研究结果，说明本文工作的意义，指出有待进一步解 决的问题。 第二章决策树分类算法的分析与比较 第二章决策树分类算法的分析与比较 2 1 分类问题描述 分类在数据挖掘中是项非常重要的任务，目前在商业中应用最多。分类和聚 类不同，聚类是对给定的一组观察值建立类别，分类是已知现存的类别，要建立类 别的描述规则，并对新例的观察值判别归类。在机器学习中聚类被称为无监督学习， 分类被称为监督学习。“。 分类的目的是学会一个分类函数或分类模型( 分类器) 。该模型能把数据库中的 数据映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从历史 数据记录中自动推导出给定数据的推广描述，从而能对未来数据进行预测。 要构造分类器，需要有一个训练样本数据集( 训练集) 作为输入。训练集是一 条条数据记录组成的。每一条记录是一个由有关字段值组成的特征向量，我们把这 些字段称作属性，此外，训练集的每条记录还有一个特定的类标签与之对应，类标 签也就是训练集的类别标记。一个具体样本的形式可以表示为：( v iv ：，v 。；c ) ， 其中v ，表示字段值，c 表示类别。 一般来说分类分为两个步骤： 第一步，构建分类器，即建立一个模型，描述规定的数据类集或概念集。构造 的主要方法有决策树、贝叶斯网、神经网络等。 第二步，利用模型进行分类。 不同的分类器有不同的特点。有三种分类器评价或比较尺度： ( 1 ) 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型 分类任务，一般的方法是保持法和k 一交叉确认法。 ( 2 ) 计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘 中，由于操作对象是巨量的数据库，因此空间和时间的复杂度将是非常重要的问题。 ( 3 ) 模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎。 例如，采用规则表示的分类器构造法就更有用，而神经网络方法产生的结果就难以 理解。 分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺值，有的分布 稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。 目前普遍认为不存在某种方法能适合于各种特点的数据。 2 2 决策树算法概述 7 柴于决策树的分类算法硼究 2 2 1 决策树 决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则 的事例中推理出决策树表示形式的分类规则，通常用来形成分类器和预测模型，可 以对未知数据进行分类或预测、数据挖掘等。自2 0 世纪6 0 年代以来，决策树在分 类、预测、规则提取等领域有着广泛应用，特别是在q u i n l a njr 于1 9 8 6 年提出i d 3 算法以后，决策树方法在机器学习、知识发现领域得到了进一步应用及巨大的发展， 在人工智能领域有着相当重要的理论意义与实用价值。 一棵决策树的内部结点是属性或属性的集合，叶结点是所要学习划分的类，内 部结点的属性称为测试属性。用决策树进行分类分两步走：第一步是利用训练集建 立一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行 机器学习的过程。第二步是利用生成完毕的决策树模型对未知的数据样本进行分 类。使用决策树对未知的数据样本进行分类的时候，从根结点开始对该对象的属性 逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此时叶结点代表的类 即为该对象所处的类。 决策树分类方法首先要利用训练集建立决策树模型，然后根据这个决策树模型 对输入数据进行分类。其中，关键问题在于决策树的构建过程，这一过程包括建树 和剪枝两个步骤：第一个步骤为建树阶段。选取部分训练数据，按广度优先递归算 法建立决策树，直到每个叶子结点属于同一个类为止。第二个步骤为剪枝阶段。它 是用剩余的数据对生成的决策树进行检验，将不正确的问题进行调整，对决策树进 行剪枝和增加结点，直到建立一个正确的决策树。决策树的建树算法是通过递归过 程，最终得到一棵决策树，而剪枝则是为了降低噪声数据对分类正确率的影响。 2 22 决策树的生成过程 对一个分类问题或规则学习问题，决策树的生成是一个从上至下、分而治之的 过程，本质是贪心算法。从根结点开始，对每个非叶结点，找出其对应样本集中的 一个属性( 也称为测试属性) 对样本集进行测试，根据不同的测试结果将训练样本集 划分成若干个子样本集，每个子样本集构成个新叶结点，对新叶结点再重复上述 划分过程，这样不断循环，直至达到特定的终止条件。其中，测试属性的选择和如 何划分样本集是构建决策树的关键环节。不同的决策树算法在此使用的技术不尽相 同。 决策树采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根 据不同的属性值判断从该结点向下的分枝，在决策树的叶结点的一条路径就对应着 第二章决策树分类算法的分析与比较 一条合取规则，整棵决策树就对应着一组析取表达式规则。基于决策树的学习算法 的一个最大优点就是它在学习过程中不需要使用者了解很多的背景知识( 这也同时 是它最大的缺点) ，只要训练例子能够用属性一结论的方式表达出来，就能使用该 算法来学习。 2 23 决策树的剪枝技术 在决策树的学习算法当中，除去分类的正确性应当放在第一位给予考虑之外， 决策树的复杂程度是另外个需要考虑的重要因素。如果决策树构造的过于复杂， 那么对于用户来说这个决策树是难以理解的，将在很大程度上使得分类树的构造没 有意义。而且，决策树构造的越小，其存储所花的代价也越小，对它的某些操作相 对来说也就简单省时。所以应该在保证正确率的前提下尽量构造简单的决策树。 简化决策树的方法很多，剪枝是最常用的方法，它主要通过在训练过程中明确 地控制树的大小来简化决策树。当决策树创建时，由于受数据中的噪声和孤立点的 影响，许多分枝反映的是训练数据中的异常。剪枝方法也可以处理这种过分适应 ( 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 ) 两种方法。 l 、预剪枝( p r e - p r u n i n g ) 预剪枝就是在完全正确分类训练集之前，较早地停止树的生长。具体在什么时 候停止决策树的生长有多种不同的方法： ( 1 ) 一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生 长，这种停止标准在一定情况下能取得比较好的效果； ( 2 ) 到达此结点的实例具有相同的特征向量，而不必一定属于同一类，也可停 止生长。这种情况可以处理数据中的数据冲突问题； ( 3 ) 到达此结点的实例个数小于某一个阈值也可停止树的生长，其不足之处是 不能处理那些数量较小的特殊情况实例； ( 4 ) 更为普遍的做法是计算每次扩张对系统性能的增益，如果这个增益值小于 某个闽值则不进行扩展。如果在最好情况下的扩展增益都小于闽值，则即使有些叶 结点的实例集不属于同一类，算法也停止。 预剪枝有个缺点，即视野效果问题。也就是说在相同的标准下，也许当前的 扩展不能满足要求，但是更进一步的扩展能够满足要求。这将使得算法过早地停止 决策树的构造。后剪枝将克服这个缺点，也可通过其它方法( 如构造属性、前向搜 索等) 来克服。但是，由于预剪枝不必生成整棵决策树，且算法相对简单，效率很 9 基于决策树的分类算法研究 高，适合解决大规模问题，所以这种方法仍然得到广泛的应用。 2 、后剪枝( p o s t p r u n i n g ) 目前，后剪枝方法已经得到了广泛的讨论，并在实际中得到成功的应用。 ( 1 ) m c c p 归1 ( 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 ) b r i e m a nl 提出基于代价复杂度的剪枝策略，该方法首先从训练数据中生成一 系列增量式的子树，然后通过评价这些子树的错误率来选择一个最好的子树以取代 原决策树。用于c a r t 系统。 ( 2 ) p e p ( p e s s i m i s t i ce r r o rp r u n i n g ) 此方法是由q u i n l a nj r 在1 9 8 7 年提出的悲观剪枝法，首先q u i n l a nj r 发现当 用产生决策树的训练数据来检测错误率时，实际上对错误的估计过于乐观了，因此 他借用二项式分布中的连续修正对训练数据中的错误率加以修正，以得到更为符 合实际的错误率。显然，与修正前的错误率相比，修正后的错误率增加了不少，因 此认为它对错误率的看法是“悲观”的。 ( 3 ) m e p ( m i n i m u me r r o rp r u n i n g ) m e p 方法由n i b l e t t 和b r m k o 首先提出，该方法使用了拉普拉斯概率估计来提 高i d 3 方法在存在噪音数据问题中的性能。m e p 方法的基本思路是采用自底向上 的方式，对于树中每个非叶结点，首先计算该结点的误差e ，( ，) 。然后，计算该结 点每个分枝的误差e ，( 丁，) ，并且加权相加，权为每个分枝拥有的训练样本比例。如 果e ，( f ) 大于e ( r ) 。则保留该子树；否则，剪裁它。 ( 4 ) r e p ( r e d u c e de r r o rp r u n i n g ) 减小错误修剪法( r e d u c e de r r o rp r i m i n g ) 也是由q u i n l a njr 提出的，在此方法 中，检测决策树中非叶结点，当此结点被最佳的叶结点取代而产生的错误数目小于 或者等于之前未修剪的决策树的错误数目，则修剪成功；否则修剪失败，放弃修剪。 如果修剪成功则重复这一方法直至错误数目比前一决策树有所增加为止。 ( 6 ) m d l ( m i n i m u md e s c r i p t i o nl e n g t h ) m d l 剪枝方法是m e h t am ，r i s s m a e nj 和a g r a w a lr 等人在1 9 9 5 年提出的 一种决策树剪枝的方法，该方法将构造的决策树中所包含的信息量以二进制编码的 形式来表示，利用编码的长度代表决策树某一分枝的误分类率的大小，进而决定剪 枝与否，它的目的在于生成一棵描述长度最小的决策树。 2 2 4 决策树的性能评价 在决策树的学习算法当中，决策树的复杂度和分类精度是需要考虑的两个最重 第二章决策树分类算法的分析与比较 要的因素，下面是决策树的性能评价标准。3 。 1 、预测准确性：该指标描述分类模型准确预测新的或未知的数据类的能力。 预测准确性是决策人员最关心的问题，对于他们来说，之所以采用分类发现模型的 原因在于：分类发现模型可以在巨量数据中，按照用户的使用要求处理数据，对数 据进行分类，从中找寻有用信息。经分类发现模型处理后，从数据中得到的信息的 准确程度不同在很大程度上将会影响决策人员决策制定的准确性。 2 、描述的简洁性：这是针对分类发现模型对问题的描述方式以及该描述方式 的可理解水平提出的。分类发现模型的最终目的是方便决策人员的使用，所以，对 于决策人员来说，模型描述越简洁，也就越易于理解，同时也就越受欢迎。例如采 用规则表示的分类器构造法所提供的分类模型的描述方法就比较简洁、易于理解： 而神经网络方法产生的描述结果相对来说就难以理解，从而使其更进一步的广泛应 用受到限制。 3 、计算复杂性：计算复杂性依赖于具体的实现细节，在数据挖掘中，由于某 种操作对象是巨量的数据库，因此空间和时间的复杂性问题将是非常重要的一个环 节，将直接影响生成与使用模型的计算成本。 4 、模型强健性：强健性是对模型预测准确性的一个补充，是在存在噪声及数 据缺损的情况下，准确对未知其类的数据进行分类的能力。正如前面所提到的，数 据挖掘处理的对象是大量的数据，而这些数据又常常存在不完整的情况，数据缺损、 噪声数据以及冗余数据等情况是普遍存在的，在这种情况下，就要求所建立的模型 对这些情况有充分的适应能力。