（计算机应用技术专业论文）决策树分类器算法的研究.pdf

摘要 摘要 在数据挖掘和机器学习领域中分类是一项非常重要的基本任务。 它能对大量有关数据进行学习和分析，并建立相应问题领域中的分类 模型。该技术在科学、通讯、金融等领域均有着广泛的应用。决策树 分类方法作为分类知识发现的一种非常重要方法，它具有良好的可解 释性、分类速度快、分类性能优越，因此，研究决策树分类器算法逐 渐成为一个活跃的研究领域。 最为典型的决策树分类器学习算法是d 3 算法，它采用自顶向下 分而治之的策略，利用信息增益的标准选择分裂属性，能保证构造出 一棵简单的树。但是它只能处理枚举型属性，不能解决过适应问题。 c 4 5 算法很好地扩展了d 3 算法，它将分类领域从枚举型属性扩展到 连续值属性，同时采用剪枝策略很好地解决了过适应问题。目前它已 成为现在公认的性能较优的决策树分类器算法。懒惰式决策树也是一 种决策树分类器，它采取懒惰式学习策略，学习过程被推迟到分类一 个给定测试实例时才进行。它从概念上为每一个测试实例建立一棵最 优决策树。在小的数据集合上，它的分类精确度非常高。但是在某些 大的数据集合上，特别是属性数目非常多的数据集合上，它的分类速 度慢，内存消耗大。 本文在深入分析d 3 算法、c 4 5 算法、懒惰式决策树分类器算法、 朴素贝叶斯分类器算法等多种分类器算法的基础上，进一步提出了急 切式和懒惰式学习策略相结合的决策树分类模型、竞争选择分裂属性 的决策树分类模型、以及基于距离和权重的懒惰式分类模型等3 种新 的决策树分类器模型。本文将新的分类器算法与d 3 算法、c 4 5 算法、 朴素贝叶斯分类器算法进行了比较，通过大量实验验证了这些新算法 的有效性和实用性，它们可以应用于求解众多实际的数据挖掘问题。 关键词：数据挖掘；分类；决策树分类器：朴素贝叶斯；懒惰式决策 树； 北京交通大学硕士学位论文 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 fv e r yi m p o r t a n tb a s i ct a s k si nm ef i e l do fd a t a m i i l i n ga n dm a c h j n el e a m i n g i tc a nb eu s e dt oa i l a l y z ea 1 1 ds t u d yav a s t n u m b e ro fr e l a t e dd a t aa n de s t a b l i s hc l 嬲s i 聊n gm o d e i si nm a n ya r e a so f r e l a t e dp r o b l e m s t h ec l a s s i 矗c a t i o nt e c h l l i q u c sh a v ee x t e n s i v e 印p l i c a t i o n u s a g ei ns c i e n t i f i cr e s e a r c h ，c o m m u i l i c a t i o n ，f i n a l l c ea n do t h e rn e l d s a d e c i s i o n e ec l a s s m e ri sav e r yi m p o r t a i l tm o d e li nt l l ep r o c e s so f h o w l e d g ed i s c o v e g o o di m e r p r e t a b i l i 劬f 船tc l a s s i f i c a t i o ns p e e da 1 1 d e x c e l l c n tc l a s s i f i c a t i o np e r f b r m a n c eo fd e c i s i o n - 仃e em a k ei t 晷a d u a l l y b e c o m em er e s e a r c hf o c u si nt h ef i e l d so fd a t am i l l i n ga i l dm a c h i n e l e a m i n 吕 t h e m o s tc l a s s i c a ld e c i s i o n n el e 蛐 1 i n gs y s t e misd 3 ，w h i c hu s e 也ed i v i d e - a i l d - c o n q u e r 印p m a c ht od e c i s i o n 一仃它ei n d u c t i o nf r o mr o o tt o l e a v e s ，a 1 1 dc h o o s em es p l i 牡i n ga t 仃曲u t e sb yt h eg 咖r a t i o t h i sm e m o d c a ne n s u r ct oc o n s 眦tas i m p l e 仃e e b u tm 3c a i ln o th 觚d l en 啪e r i c a t t r i b u t e s ，o n l yn o m i n a la 船讪u t e s ni su s u 砒l yo v e r 虹t t e dt om e 仃a i n i n g d a t a b a s e s c 4 5 a l g o r i m m i s t l l ee x t e n s i o no fd 3 i te x t e n d sm e c l a s s i f i c a t i o na b i l i t y0 fi d 3 疗o mn o m i n a la t t r i b u t e st on u m e r i ca t t r i b u t e s i tw e l lr e s 0 1 v e st h ep m b l e ma b o u to v 础仕i n gb yp n l n i n gd e c i s i o n t r e e s n o wi th a sa h a d yb e e nh o w na sab e 戗e rd e c i s i o n - 仃c ec l a s s i 丘e r l a z y d e c i s i o n 打e e sa l s oc o 璐虮l c td e c i s i o n - t r e e s ，a d o p tl 配ya l g o r i t h m ，a 1 1 d d e l a ym el e 锄i n gp r o c e e d i n gu n t i la t e s ti n s t a i l c ei s 百v e n i tc o n c 印t l l a i l y c o n s 缸u c t s l eb e s t ”d e c i s i o n 一仃e ef o re a c ht e s ti n s t a n c e h 1s m a l l d a t 如a s e s ，i t sc l a s s i f i c a t i o na c c l l r a c yi sv e r y1 1 i 曲b u ti ns o m el a r g e r d a t a b a s e s ，i t ss l o wc l 船s m c a t i o ns p e e d ，l a r g es t o r ec o s t i n ga i l de a s i l y i n d u c e db yn o i s e sa 丘b c ti 招c l 嬲s i f i c a t i o np e r f o 舰a i l c e ，s p e c i a l l yi nm e 1 a 曙e rd 砒l b a s e st e s t e dw l l i c hh a v eag r e a td e a lo f 砒r f b u t e s b a s e do n 仕屺a l l a l y s i so fd 3a l g o 删撇，c 4 5a l g o r i t h i n ，1 a z y d e c i s i o n - t r sc l a s s i f i e r sa l g o r i 伽n ，a n dn a i v eb a y e sc l a s s i f i e r sa l g o r i t h r n ， t 1 1 r e en e wd e c i s i o n - t r e ec l a s s i f i e r sa r ep r e s e m e di nm i sp a p e r w h i c ha r ea d e c i s i o n t r e ec l a s s i f i c rh y b r i dm o d e lo fe a g e rs 仃n e g ya 1 1 dl a z ys 打a t e g y ，a 摘要 d e c i s i o n t r e ec l a s s m e rm o d e lo f c o m p e t i t i v e l ys e l e c t i n gs p l i t t i n ga t t r i b u t e s ， a i l da1 a z yd e c i s i o n t r e ec l a s s i 壬i e ro nb a s eo fw c i 星ma n dd i s t a l l c e i nm i s p 印e r ，w ea l s oc o m p a r et h en e wm o d e l sw i t hd 3a l g o r i t h r n ，c 4 5 a l g o r i m m ，1 a z yd e c i s i o n 一虹e e sc l a s s i f i e r s “g o 打c 1 1 m 趾dt h en a i v eb a y e s c l a s s i f i e r sa l 窖o r i t t l i i l ，a n de x t e n s i v ee x p e r i m e n t a lr e s u l t ss h o wt h e i r e f r c c t i v e n e s sa 1 1 du s a b i l i t yi np r a c t i c e t h e yc a nb eu s e dt os o l v ev a r i o u s p r a c t i c a ld a t am i i l i n gp r o b l e m s k e yw o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o n ，d e c i s i o n - t r ec l a s s i f i e r ，n a v e b a y e sc l a s s i f i i a z yd e c i s i o n 仃e ec l a s s i f i e r 独创性声明 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或、证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名：垄叠当 日期：一一，扫年 月占日 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名：塑坠辑 日期：盟年上月上 绪论 第1 章绪论 本章主要介绍本研究课题的学术背景、相关理论、以及本论文的 研究内容及其组织安排。 1 1 数据挖掘 1 1 1 数据挖掘的定义 数据挖掘，也称作数据采掘、数据开采等。许多人把“数据挖 掘”和“数据库中的知识发现”( 简称k d d ) 看作是等价的概念。一 种比较公认的定义是w j f r a w l e y 、g p i a t e t s k y - s h a p i m 等人提出的 数据挖掘的定义：数据挖掘就是从大型数据库的数据中提取出人们感 兴趣的知识；这些知识是隐含的、事先未知的，但潜在有用和易于理 解的信息；提取的知识可以表示为概念、规则、规律、模式等形式。 而更广义的说法是：数据挖掘意味着在一些事实或观察数据的集合中 寻找模式的决策支持过程【2 】。 通常，数据挖掘是建立在大量数据的基础之上。这些数据可以是 关系数据库中的数据，也可以是文本、图形和图像数据，甚至还可以 是分布在网络上的异构型数据 3 1 。数据挖掘在这些大量数据中提取到 的有用信息和知识可以被用于信息管理、查询优化、过程控制等，并 可以用它们对未来情况进行预测，以辅助决策者评估风险来做出正确 的决策。因此，数据挖掘把人们对数据的应用从低层次的简单查询， 提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚 了不同领域的研究者，尤其是数据库技术、人工智能技术、机器学习、 数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投 身到数据挖掘这一新兴的研究领域，形成新的技术热点【4 】。 北京交通大学硕士学位论文 1 1 2 数据挖掘常用技术 目前的数据挖掘常用技术【5 】有： 夯遗传算法：它基于生物进化的概念设计了一系列的过程来达 到优化的目的。这些过程有基因组合、交叉、变异和自然选 择等。为了应用遗传算法，需要把数据挖掘任务表达为一种 搜索问题，从而发挥遗传算法的优化搜索能力。 辫最近邻方法：这种技术通过k 个最与之相近的历史记录的组 合来辨别新的记录。有时也称这种技术为尽最近邻方法。这 种技术可以用在聚类、偏差分析等挖掘任务中。 警规则推导：该技术通过统计方法归纳，提取有价值的萨砌p n 规则。规则归纳的技术在数据挖掘中被广泛使用，例如关联 规则的挖掘，它从统计意义上对数据中的“如果那么”规则 进行寻找和推导。 静人工神经网络：由具有适应性的简单单元组成的广泛互连的 网络，它的组织能够模拟生物神经系统对真实世界所做出交 互反应。它从结构上模仿生物神经网络，是一种通过训练来 学习的非线性预测模型。可以完成分类、聚类、特征挖掘等 多种数据挖掘任务。较常用的人工神经网络模型有反向传播 网模型b p 、径向基函数神经网络r b f 和自组织特征映射神 经网络s o m 等。 赣粗糙集方法；在数据库中将行元素看成对象，将列元素看成 属性( 分为条件属性和决策属性) 。等价关系尺定义为不同对象 在某个或某几个属性上取值相同，满足等价关系的对象组成 的集合被称为等价关系r 的等价类。条件属性上的等价类e 与决策属性上的等价类y 之间的关系分三种情况：下近似、 上近似、无关。 静概念树方法：对数据库中的记录的属性字段按归类形式进行 抽象，建立起来的层次结构称为概念树。利用概念树提升的 2 绪论 方法可以大大减少和浓缩数据库中的记录。将多个属性字段 进行概念树提升，将得到高度概括的知识基表，再将其转化 成规则。一般采用概念树的方法对数据库进行预处理。 骖贝叶斯网络：贝叶斯网络是一个带有概率注释的有向无环图。 这种模型能表示变量之间的联合概率分布，分析变量之间的 相互关系，利用贝叶斯定理揭示的学习和同级推断功能，可 以实现预测、分类、聚类、因果分析等数据挖掘任务。贝叶 斯理论是处理不确定性信息的重要工具。作为一种基于概率 的不确定性推理方法，贝叶斯网络在处理不确定信息的智能 化系统中已得到了重要的应用，已成功地用于医疗诊断、统 计决策、专家系统等领域。这些成功的应用，充分体现了贝 叶斯网络技术是一种强有力的不确定性推理方法。 警决策树：这种技术用树形结构来表示决策集合。这些决策集 合通过对数据集的分类产生规则。其典型的应用是分类规则 的挖掘。建立决策树的过程可以递归地实现。首先选择最大 信息量的属性，建立决策树的根结点，然后再根据该属性的 不同取值建立树的分枝结点。这样就把整个数据集分成了几 个子集。在每个分枝子集中重复建树的下层结点和分枝的过 程，即可建立决策树。国际上最有影响和最早的决策树方法 是1 9 8 6 年j r o s s0 l l i i l l a i l 提出的d 3 方法，它处理越大的数 据分类的效果越好。在d 3 方法的基础上，后人又发展了各 种决策树方法，包括现在非常流行的c 4 5 算法、c 5 0 算法及 c h a d 算法等。有关决策树的内容将在下章进行详细说明。 其余的数据挖掘技术还有可视化、覆盖正例排斥反例方法、公式 发现、模糊论、归纳逻辑程序、统计分析等等。 1 1 3 数据挖掘功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖 掘任务一般可以分两类：预言性数据挖掘和描述性数据挖掘。预言性 数据挖掘是进行数据分析，建立一个或一组模型，并根据模型产生关 3 北京交通大学硕士学位论文 于数据的预测；描述性数据挖掘是以概要的方式对数据信息进行描 述，提供数据的一般性质【5 】。 数据挖掘功能以及它们可以发现的模式类型通常包括概念类描 述、关联分析、分类、预测、聚类、孤立点分析、演变分析等等。为 了适应不同的用户需求或不同的应用，数据挖掘系统通常需要挖掘多 种类型的模式 3 l 。 一关联分析：发现关联规则，这些规则展示属性一值频繁地在给 定数据集中一起出现的条件。关联分析广泛用于购物篮或事 务数据分析。 聚类分析：将不同的母体区隔为较具同构型的群组，换句话 说，其目的是将组与组之间的差异分辨出来，并对个别组内 的相似样本进行挑选。在聚类技术中，没有预先定义好的类 别和训练样本存在，所有纪录都根据彼此相似程度来加以归 类。比如，在市场营销调查前，先将顾客聚类，再来分析每 群顾客最喜欢哪一类促销，而不是对每个顾客都用相同的标 准规则来分析。 一概念，类描述：数据与类或概念相关联。用汇总的、简洁的、 精确的方式描述每个类和概念，这种描述称为概念类描述。 得到描述采取的方法通常是：数据特征化、数据区分和比较。 数据特征化是目标类数据的一般特征或者特征的汇总。数据 区分是将目标类对象的一般特征与一个或多个对比类对象的 一般特性进行比较。 孤立点分析：数据库中可能包含一些数据对象，它们与数据 的一般行为或者模型不一致。这些数据对象是孤立点。大部 分数据挖掘方法将孤立点视为噪声或异常丽丢弃。然而，在 一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那 些更有趣。孤立点数据分析称作孤立点挖掘。孤立点可以使 用统计试验检测。它假定一个数据分布或概率模型，并使用 距离度量，到其他聚类的距离很大的对象被视为孤立点。基 于偏差的方法通过考察一群对象主要特征上的差别识别孤立 4 点，而不是使用统计或距离度量。 演变分析：它描述行为随时间变化的对象的规律或趋势，并 对其建模。尽管这可能包括时间相关数据的特征化、区分、 关联、分类或者聚类，这类分析的不同特点包括时间序列数 据分析、序列或周期模式匹配和基于类似性的数据分析。 预测：根据对象属性过去的观察值来估计此属性未来的值。 比如，预测哪些顾客会在未来的半年内取消该公司的服务， 或是预测哪些电话用户会申请增值服务，如三方通话、语音 信箱等。 分类：根据训练集数据找到可以描述并区分数据类别的分类 模型，使之可以预测未知数据的类别。例如将信用卡申请人 分为低、中、高风险群，或是将顾客分到事先定义好的族群。 较普遍的分类方法有决策树、贝叶斯方法、k 近邻算法等。 有关分类的内容将在下节进行详细说明。 预言性数据挖掘分析主要采用的方法是分类。而描述性数据挖 掘分析主要采用孤立点分析、聚类等多种数据挖掘方法。其中分类、 预测为定向式数据挖掘，即有监督的数据挖掘，其目的是利用现有 的资料来建立模型，借此描述某一个特定变量；关联分析、聚类为 非定向式数据挖掘，即无监督的数据挖掘。在无监督式数据挖掘中， 并未特别标明某一个变量，其目的是在所有的变量中找出有可能存 在的关系5 1 。 1 2 分类 现实世界业务活动积累的数据中隐藏着许多可以为商业、科研决 策提供支持的知识。分类是一种数据分析形式，也是数据挖掘中一项 非常重要的任务，它可用于在数据中抽取出决策支持所用的知识，即 能在数据中抽取出描述重要数据集合或预测未来数据趋势的模型。在 数据挖掘中，分类的应用非常广泛。例如：银行部门可以建立一个分 类模型，对贷款的安全级别和风险类型进行分类预测；销售部门可以 5 北京交通大学硕士学位论文 在收集的客户资料上建立一个分类模型，来判断客户是潜在客户还是 忠实客户。 1 2 1 分类的概念 一般地，分类任务是依据某种分类模型，在具有类标的数据集合 上学习出一个分类函数，即通常所说的分类器。该函数能够给由属性 值序偶集所描述的待分类实例指派一个最适合的类标，从而可以应用 于数据分类和预测。分类的过程是：首先在一个作为输入的训练集合 上学会一个分类函数或构造出一个分类模型，然后利用它对数据集合 中没有类标的实例指派最适合的类标。训练集合是由一组数据实例构 成，每个实例是一个由有关字段组成的特征向量，这些字段被称为属 性，用于分类的属性被叫做类标，类标属性也就是训练集合的类别标 记。一个具体的实例形式可以表示为0 l 啦，口。，c ) ，其中啦( f _ 1 ， 2 ，n ) 表示属性4 f 字段值，c 表示类标。给定训练数据集合d = ， 娩， ，分类任务的目标是对数据集合d 进行分析，确定一个映 射函数， 1 ，爿2 ，4 。) 一c ，使得对任意的未知类别的实例x l = ( 口l ， n 2 ，) 可标以适当的类标c + 。 训练集合是构造分类器的基础。训练集合是包含一些属性的一个 数据库表格，其中的一个属性被指定为分类标签。标签属性的类型一 般要求是离散的，且标签属性的可能值的数目越少越好( 最好是两或 三个值) 。标签值的数目越少，构造出来的分类器的错误率越低。 分类用于预测数据对象的类别。如可以构造一个分类模型来对银 行贷款进行风险评估( 安全或危险) 。机器学习、专家系统、统计学 和神经生物学等领域的研究人员已经提出了许多具体的分类方法，如 贝叶斯方法、决策树【6 】、规则推导、人工神经网络、支持向量机、基 于实例的方法等。 1 2 2 分类器的学习策略 机器学习方法分为有监督的学习和无监督的学习有监督的学习 需要给出不同类别的实例作为训练实例，由这些训练实例得到类的描 6 绪论 述，然后给新的测试实例匹配类标无监督的学习是在给定实例集合 上，根据其内容，在无先验知识的条件下，将实例分成有意义的类其 中有监督的学习从学习过程的任务实施方式上可以分成两种极端的 情况，即急切式学习策略和懒惰式学习策略急切式学习策略在分类 器训练阶段就建立将待分类实例映射到其预测类标上的一个有清晰 假设的分类器学习的过程是在训练数据集合上建立分类器的过程， 它同分类过程是相分离的一般的决策树算法就是典型的代表而懒 惰式学习算法没有建立清晰的假设，分类过程就是利用训练集合将给 定实例与其类标匹配起来的过程，学习过程和学习结果的应用过程是 同时进行的 采用急切式学习策略的分类器，即对于给定的训练实例集合，在 训练阶段就建立好一个分类器，在分类阶段直接地使用该分类器来给 一个待分类实例分类。f 瑚m a n 等的t a n 分类器就是一种采用急切式 学习策略的分类器。 采用懒惰式学习策略的分类器，在训练阶段不建立一个清晰的假 设，而在分类阶段使用训练集合来将给定实例与其类标匹配起来，即 在分类时利用训练集合和测试实例建立分类规则为该测试实例来分 类。l b r 分类器就是采用了一种完全懒惰的学习方法：基于实例的分 类也采用了懒惰式学习策略。 一般来讲，对于同一种模型技术，急切式学习策略在效率上大大 优于懒惰式学习策略，而懒惰式学习策略在分类精确度上优于急切式 学习策略。 为了使分类器在能够在效率和分类精确度上都达到令人满意的 水平，可以对上述两种学习策略进行研究，对同一种分类模型找到一 个采用急切式学习策略和懒惰式学习策略的平衡点。这是分类器研究 的一个突破点，也是本文的研究点之一。 1 2 3 分类器算法 近年来随着数据挖掘技术在许多经济领域中广泛的应用，很多研 究人员建立并发展了较多机器学习与数据挖掘的理论体系，开发了许 多分类的实用方法，例如，朴素贝叶斯方法、贝叶斯网络、决策树6 1 、 7 北京交通大学硕士学位论文 决策表、神经网络、k 最邻近以及支持向量机等。尽管众所周知，这 些方法中没有一种分类方法在所有领域都是有效的，但是这些方法在 不同的领域中各自起到了非常重要的作用。 1 2 3 1 贝叶斯分类 贝叶斯分类 7 】是统计学分类方法。它们可以预测类成员关系的可能 性，如给定样本属于一个特定类的概率。贝叶斯分类基于贝叶斯定理。 大量的分类算法研究发现：一种称作朴素贝叶斯分类的简单贝叶斯分类 算法可以与决策树和神经网络分类算法相媲美。用于大型数据库，贝叶 斯分类也已表现出高准确率和高的分类速度。 贝叶斯分类方法具有坚实的数学理论基础和综合先验信息与数据 样本信息的能力，是当前机器学习和数据挖掘的研究热点之一。它基于 如下的假定，即待考查的量遵循某种概率分布，且可根据这些概率及已 观察到的数据进行推理，从而做出最优的决策。 贝叶斯推理对机器学习十分重要。贝叶斯推理为直接操作概率的 学习算法提供了基础，而且它也为其他算法的分析提供了理论框架， 为理解大多数的学习算法提供了一种有效的手段。贝叶斯学习同机器 学习研究相关，因为贝叶斯学习算法能够计算显式的假设概率，如朴 素贝叶斯分类器，它是解决相应学习问题的最有实际价值的方法之 一。 贝叶斯分类方法的特性包括： 壤观察到的每个训练实例可以增量式地降低或升高某假设的估 计概率。这提供了一种比其他算法更合理的学习途径。 瞧先验知识可以与观察数据一起决定假设的最终概率。在贝叶斯 学习中，先验知识的形式可以是每个候选假设的先验概率，也 可以是每个可能假设在可观察数据上的概率分布。 熊贝叶斯分类方法可允许假设做出不确定性的预测。 隧新的实例分类可由多个假设一起做出预测，以它们的概率为权 重。即使在贝叶斯分类方法计算复杂度较高时，它们仍可作为 一个最优的决策的标准衡量其他方法。 贝叶斯分类方法有如下局限性：第一，该方法需要概率的初始知 8 绪论 识。当这概率预先未知时，可以基于背景知识、预先准备好的数据以 及关于基准分布的假定来估计这些概率。第二，一般情况下确定贝叶 斯最优假设的计算代价比较大。 1 2 3 2 决策树分类 决策树分类是应用最多的分类方法之一。它是一种逼近离散函数 的方法，且对噪声数据有很好的健壮性，能够学习析取表达式。它采 用的基本算法是贪心算法，基于训练集合以自顶向下递归地各个击破 方式构造决策树，是一种有监督的学习方法。决策树分类器是从训练 集合中构造出决策树，决策树的叶结点是类名，中间结点是带有分支 的属性，每个分支对应该属性的某一可能取值。比较典型的决策树分 类器有d 3 和c 4 5 等。这些决策树分类器的具体算法我们将在第2 章决策树分类器模型当中会详细介绍。 尽管已经开发的种种决策树分类器有这样或那样不太一致的能力 和要求，通常决策树学习最适合具有以下特征的问题： i 实例由“属性值”对表示，它用一系列固定的属性和它们的 值来描述的。最简单的决策树学习中，每一个属性取少数的离 散的值。然而，扩展的算法也允许处理值域为实数的属性。 羹 目标函数具有离散的输出值，例如天气问题中的决策树给每个 实例赋予一个布尔型的分类。决策树方法很容易扩展到学习有 两个以上输出值的函数。一种更强有力的扩展算法允许学习具 有实数值输出的函数，尽管决策树在这种情况下的应用不太常 见。 可能需要析取的描述，如上面指出的，决策树很自然地代表了 析取表达式。 羹训练数据可以包含错误，决策树学习对错误有很好的健壮性， 无论是训练样例所属的分类错误还是描述这些样例的属性值 错误。 睫训练数据可以包含缺少属性值的实例，决策树学习甚至可以在 有未知属性值的训练样例中使用 9 北京交通大学硕士学位论文 已经发现很多实际的问题符合这些特征，所以决策树分类已经被 应用到很多问题中。例如根据疾病分类患者，根据起因分类设备故障， 根据拖欠支付的可能性分类贷款申请。对于这些问题，核心任务都是 要把样例分类到各可能的离散值对应的类别中，它们都是典型的分类 问题。 采用决策树生成的分类器，可以生成可以理解的规则，因而可解 释性非常好。而且决策树可以清晰地显示哪些属性比较重要，同时还 可以处理枚举型属性和数值型属性。决策树分类算法与其它类算法如 统计方法、神经网络等比较起来有如下优点： 一产生的规则易于理解。决策树的每个分支都对应一个分类规 则，因此决策树分类算法最终可以输出一个容易理解的规则 集。 一速度相对较快，其时间复杂度是0 ( n 3 ) ，这里月指训练数据集 合中样本的个数。 一准确率相对较高。 但是决策树技术本身也存在许多的不足之处，比如它的修剪策略 非常复杂，很难把握，而且特别费时，数值型属性比较难于处理。 1 2 3 3 基于实例的方法 已知一系列的训练样例，很多学习方法为目标函数建立起明确的 一般化描述；但与此不同，基于实例的学习方法【8 】只是简单地把训练 样例存储起来。从这些实例中泛化的工作被推迟到必须分类新的实例 时。每当分类器遇到一个新的测试实例，它分析这个新的实例与以前 存储的训练实例的关系，并据此把一个目标函数值赋给新实例。基于 实例的学习方法包括最近邻法和局部加权回归法，它们都假定实例可 以被表示为欧氏空间中的点。基于实例的学习方法还包括基于案例的 推理，它对实例采用更复杂的符号表示。基于实例的学习方法有时被 称为懒惰式学习法，因为它们把处理工作延迟到必须给测试实例分类 时。这种懒惰的学习方法有一个关键的优点，即它们不是在整个实例 空间上一次性地估计目标函数，而是针对每个待分类新实例做出局部 的和相异的估计。 l o 绪论 基于实例的学习方法中，最近邻法和局部加权回归法用于逼近实 值或离散目标函数，它们在概念上都很简明。对于这些算法，学习过 程只是简单地存储已知的训练数据。当遇到新的查询实例时，一系列 相似的实例被从存储器中取出，并用来分类新的查询实例。这些方法 与其他分类方法相比，一个关键差异是基于实例的方法可以为不同的 待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立 目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不 建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它 可用不太复杂的局部逼近描述时，这样做有显著的优势。 基于实例的方法也可以使用更复杂的符号表示法来描述实例。在 基于案例的学习中，实例即以这种方式表示，而且也按照这种方式来 确定邻近实例。基于案例的推理已经被应用到很多任务中，比如，在 咨询台上存储和复用过去的经验；根据以前的法律案件进行推理；通 过复用以前求解的问题的相关部分来解决复杂的调度问题。 基于实例方法的一个不足是，分类测试实例的开销可能很大。这 是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练实 例时。所以，如何有效地索引训练实例，以减少查询时所需计算是一 个重要的实践问题。此类方法的第二个不足是，当从存储器中检索相 似的训练实例时，它们一般考虑实例的所有属性。如果目标概念仅依 赖于属性中的几个时，那么真正最相似的实例之间很可能相距甚远。 基于实例方法是一种懒惰式分类方法，在分类精确度上有着较大的 优势，但在运行速度上有待提高。目前，许多研究都在对基于实例方 法的改进方面做了大量的工作，提出了一些新的高效的分类器。如 z i l i p e n gx i e 等提出了s 婚，e i b ef r a l l l 【等提出了l 0 c a l l y w e i 曲t e d 1 e 锄i n g 算法等。 1 3 本文的主要工作与组织安排 本文的主要工作是对决策树分类器进行研究，通过深入分析i d 3 算法、c 4 5 算法、懒惰式决策树分类器、朴素贝叶斯分类器等多种分 类器算法的基础上，提出新的算法或者改进算法，构造出新的决策树 分类模型，并通过实验验证了这些模型。主要研究工作在于： 北京交通大学硕士学位论文 隧通过分析了急切式学习策略下的一般决策树模型和懒惰式学 习策略下懒惰式决策树模型，吸取了这两种模型的长处，从 一种新的角度提出了一种新的分类模型一急切式和懒惰式学 习策略相结合的决策树分类模型s e m i l d t r e e 曝通过分析了信息增益和增益比率、g i n i 索引、基于 g 0 0 d m a n k n l s k a l 关联索引这三种选择分裂属性的标准，从一 种新的角度提出了一种新的改进经典决策树分类器c 4 5 算法 的方法一竞争选择分裂属性的决策树分类模型c s a 仃c e 。 蒸通过研究懒惰式决策树分类模型、基于实例的分类方法和最 近邻方法的特点，提出了一系列新的决策树分类模型一基于 距离和权重的懒惰式决策树分类模型d w l d m e e 。 本文的组织安排如下： 第1 章绪论。介绍本文研究内容的背景情况，包括数据挖掘与 分类，以及本文的主要工作与组织安排。 第2 章决策树分类器。首先介绍了决策树分类模型；然后介绍 了i d 3 算法、c 4 5 算法、懒惰式分类算法及当前的研究 现状；最后就文中分类器算法实现过程中的一些问题作 了探讨和说明。 第3 章急切式和懒惰式学习策略相结合的决策树分类模型。首 先分析了急切式学习策略下的一般决策树模型和懒惰 式学习策略下的懒惰式决策树模型：接着比较了这两种 模型的分类特点，并分析了这两种模型的结合点；最后 提出一种急切式和懒惰式学习策略相结合的决策树分 类模型s e m i l d t r ，并在实验数据的基础上分析了其分 类性能。 第4 章竞争选择分裂属性的决策树分类模型。首先分析了信息 增益和增益比率、g i n i 索引、基于g o o d m a n k m s k a l 关 联索引这三种选择分裂属性的标准；然后指出采用单一 分裂属性标准的不足；最后提出一种对c 4 5 算法新的改 进方法一竞争选择分裂属性的决策树分类模型c s a 吮e ， 并进行了对比实验。 第5 章基于距离和权重的懒惰式分类模型。首先分析了分类精 1 2 确度高而分类速度慢的懒惰式分类模型：接着分析了基 于实例的分类模型和最近邻方法，从中获得启示；最后 提出一系列新的基于距离和权重的懒惰式决策树分类 模型d w l d 慨e ，在实验结果上分析了其性能。 第6 章结束语。对全文进行了总结，并提出了课题下一步的研 究方向和目标。 1 3 北京交通大学硕士学位论文 第2 章决策树分类模型 2 1 决策树分类 决策树是一个类似于流程图的树形结构，其中每个内部节点表示 在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点 代表类或类分布。树的最顶层节点是根节点。 为了对未知的样本分类，样本的属性值在决策树上测试。路径由 根到存放该样本预测的叶节点。决策树容易转换成分类规则。 在决策树构造时，许多分枝可能反映的是训练数据的噪声或孤立 点。剪枝策略试图检测和剪去这种分枝，以提高在未知数据上分类的 准确性。决策树已经在医疗到博弈论和商务等应用领域得到了广泛使 用。决策树是一些商业规则归纳系统的基础。 2 1 1 i d 3 算法 决策树分类算法的一个典型代表就是i d 3 算法【9 j 。i d 3 算法是基 于信息论的方法。给定一个记录的集合，每个记录都有相同的结构， 并且每个记录是由若干个成对的属性值对组成。这些属性代表记录所 属的类别。i d 3 需要解决的问题是构造一个决策树，从而可以由非类 别的属性值正确地预测出类别属性的值。 i d 3 算法可以分为两个阶段，一是建立决策树阶段，一是利用决 策树给实例分类的阶段。在i d 3 算法建立决策树的过程中，可以递归 地进行：首先，选择一个属性作为根节点，并为每一个可能的属性值 生成一个分支这样，把实例集合划分成多个子集合，该属性的每一 个值划分为一个子集合。现在对每一个分支重复以上的过程，过程中 使用的实例集合是属于该分支的实例如果在一个节点的所有实例属 于相同的类，则停止扩展那一部分子树这样i d 3 的所建立的决策树 中每一个非叶子节点对应着一个非类别属性，与属性中具有最大信息 量的非类别属性相关联：每个叶节点代表从树根到叶节点之间的路径 1 4 决策树分类模型 所对应的记录所属的类别属性值。在i d 3 建立决策树的过程中，一个 重要的环节就是分裂属性的选择。选择分裂属性时i d 3 采用了信息增 益的标准。 一个属性的信息增益是由于使用这个属性分割实例而导致的期 望熵降低。例如，属性4 相对实例集合s 的信息增益g a m ( 跗) 定义为： 胛加 _ ) _ 1 1 f “固一，。磊( 椰斜1 1 1 f “瓯)f 2 - 1 1 v e p 驯甜( 10 1i z j l 信息熵的定义为：若给定的概率分布p = ( p l ，p 2 分布传递的信息量称为p 的信息熵，记为： i n f o ( 尸) = 一l o g ：( 只) l = 1 ，p n ) ，则由该 ( 2 2 ) 计算出各个非类别属性的信息增益后，由此来选择信息获得最大 的属性作为分裂属性来建立决策树。 理想的情况是当所有叶子节点是纯洁的时候过程结束即，他们 所包含的实例属于同一类然而，也许不可能达到这种状态，因为有 可能有一个实例集合，包含两个实例，有同样的属性集合，但属于不 同的类，谁也不能保证这种情况不发生，所以当数据不能继续划分时 就停止这样就会在运用分类器给实例分类时出现有未分实例的现 象。 上述过程是在i d 3 算法中建立决策树的过程，建立好决策树后就 可以利用些决策树给实例进行分类。分类过程是根据待分实例在所建 决策树中找到与其匹配的类属性值的过程。在程序设计中上也可以通 过递归来实现。 基于本文所述i d 3 的基本思想，i d 3 的具体算法是： f u n c t i o ni d 3 尺：一个非类别属性集合；c ：类别属性；一个训练集合。 返回一个决策树。 b e g i n i fs 为空，返回一个值为丢失值的单个节点； 1 5 北京交通大学硕士学位论文 i f s 是由其值均为相同类别属性值的记录组成，返回一个带有该 值的单个节点； i fr 为空，则返回一个单节点，其值为在s 的记录中找出的频 率最高的类别属性值； 将月中属性之间具有最大g a i l l ( d ，$ 值的属性赋给d ； 将属性d 的值赋给 嘻i 产1 ，2 ，脚) ； 将分别由对应于d 的值为碣的记录组成的s 的子集赋给弛j 产1 ，2 ，珊 ； 返回一棵树，其根标记为d ，树枝标记为函，如，幽； 再分别构造以下树： i d 3 僻- d ，c j l ) ，i d 3 僻 d ，c ，) ，i d 3 僻一 d ) ，c ，岛) ； e n d 2 1 2c 4 5 算法 c 4 5 算法嗍是一个里程碑式的决策树算法，是迄今为止在实践中 应用最为广泛的机器学习方法。它所采用的是分而治之策略。决策树 生成的难点主要有如何处理连续值属性，如何处理缺省值，如何修剪 决策树。j 4 8 是在w e k a 实验平台下它的具体实现程序。 1 分而治之构造决策树 c 4 5 构造决策树采取的方法是分而治之递归地构造：首先，计算 候选属性的信息熵比率和增益比率，选择一个最佳属性( 增益比率最 大) 作为根节点，并为每一个可能的属性值生成一个分支这样，把 实例集合划分成多个子集合( 大小为属性值的数目或者为2 ) ，该属性 的每一个值对应一个子集合现在对每一个分支重复以上的过程，过 程中使用的实例集合是属于那个分支的实例集合如果在一个节点的 所有实例属于相同的类或者小于叶子节点限制的最少的实例数，则停 止扩展那一部分子树 2 处理连续值属性 1 6 决策树分类模型 大多数真实数据集合都包含连续值属性。针对连续值属性c 4 5 采取的方法是二路分裂。c 4 5 按连续值属性值升序排列数据集合的实 例。顺序取两两连续值属性值的中点作为一个分裂点，可以把数据集 合分裂为两个子集合。如果连续值属性有聍个值，所以有胆1 个可以 作为分裂点的位置。依照这舯1 个分裂点可以计算出胛1 个信息熵值， 找出其中最大值。将小于并且最接近信息熵最大的分裂点值，且存在 于数据集合的属性值定为最终分裂点值。 采用枚举型属性和连续值属性作为分裂属性的不同之处，除了在 于连续值属性的分裂都是两路分裂，而枚举型属性的分裂是多路分裂 外，枚举型属性在决策树里从根到叶子的任一条路径上被作为分裂属 性只能是一次，而连续值属性可以被利用多次，只需要每次的分裂点 不同就可以。但是这样做导致生成的决策树的深度大为增加，可理解 性差，不易于理解。解决的办法是可以采取连续值属性多路分裂，但 是难于实现。也可以先调用离散化程序预处理连续值属性，然后再建 立决策树。 3 处理缺省值 在实际生活的数据集合里，属性值缺省的现象很常见。处理缺省 值的一个简单办法就是删除有缺省值的实例。但是含有缺省值的实例 通常提供了很多信息。有时候值缺省的属性在决策中不起作用，所以 在这种情况下它同其他没有缺省值的实例一样好。c 4 5 采取的方法是 当使用这个缺省属性作为分裂属性时，按照分裂分支下的训练实例数 的比例将有缺省值的实例分成一定比例的碎片。 4 选择最佳分裂属性 决策树分类器的核心问题是在树的每个节点上选取最佳分裂属 性。最佳的分裂属性应该是分类能力最好的属性。信息增益就是用来 形容给