ID3的基本思想和算法分析

1、第1章决策树方法在数据仓库和数据挖掘的应用中，分类是一种非常重要的方法分类的概念是在已有数据的基础上学会一个分类函数或构造出一个分类模型（即我们通常所说的分类器(Classifier）该函数或模型能够把数据库中的数据纪录映射到给定类别中的某一个，从而可以应用于数据预测分类的主要算法有：贝叶斯算法、决策树算法（如ID3、C4.5等）、规则推导、人工神经网络、最近邻算法、支持向量机等等这些算法在许多现实数据集合上可以做比较精确的数据预测，为人们的生活、生产、学习、研究提供了有效的途径其中决策树算法具有良好的可解释性，在实践中的应用最为广泛决策树分类算法的一个典型代表就是ID3算法1.1 概述1.1

2、.1 学习的相关概念分类是在一个作为输入的训练集合上学会一个分类函数或构造出一个分类模型，即我们通常所说的分类器(Classifier)，然后利用它对数据集合中没有类标的实例指派最适合的类标。分类是在一个作为输入的训练集合上学会一个分类函数或构造出一个分类模型，即我们通常所说的分类器(Classifier)，然后利用它对数据集合中没有类标的实例指派最适合的类标分类用于预测数据对象的类别如可以构造一个分类模型来对银行贷款进行风险评估（安全或危险）机器学习、专家系统、统计学和神经生物学等领域的研究人员已经提出了许多具体的分类方法，如贝叶斯方法、决策树、规则推导、人工神经网络、支持向量机、基于实例的

3、方法等训练集合是由一组数据实例构成，每个实例是一个由有关字段组成的特征向量，这些字段被称为属性（Attribute），用于分类的属性被叫做类标，类标属性也就是训练集合的类别标记一个具体的实例形式可以表示为(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示属性字段值，c 表示类标给定训练数据集合D=x1, x2 , , xn, 分类任务的目标是对数据集合D进行分析，确定一个映射函数f: (A1, A2, , An)C ，使得对任意的未知类别的实例xi=(a1, a2 , , an)可标以适当的类标*训练集合是构造分类器的基础训练集合是包含一些属性的一个数据库表格，其

4、中的一个属性被制定为分类标签标签属性的类型一般要求是离散的，且标签属性的可能值的数目越少越好（最好是两或三个值）标签值的数目越少，构造出来的分类器的错误率越低训练集合是由一组数据实例构成，每个实例是一个由有关字段组成的特征向量，这些字段被称为属性（Attribute），用于分类的属性被叫做类标，类标属性也就是训练集合的类别标记。一个具体的实例形式可以表示为(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示属性字段值，c 表示类标。给定训练数据集合D=x1, x2 , , xn，分类任务的目标是对数据集合D进行分析，确定一个映射函数f: (A1, A2, , An)

5、C ，使得对任意的未知类别的实例xi=(a1, a2 , , an)可标以适当的类标*。监督学习和非监督学习的区别机器学习方法分为有监督的学习和无监督的学习有监督的学习需要给出不同类别的实例作为训练实例，由这些训练实例得到类的描述，然后给新的测试实例匹配类标无监督的学习是在给定实例集合上，根据其内容，在无先验知识的条件下，将实例分成有意义的类其中有监督的学习从学习过程的任务实施方式上可以分成两种极端的情况，即急切式学习策略和懒惰式学习策略急切式学习策略在分类器训练阶段就建立将待分类实例映射到其预测类标上的一个有清晰假设的分类器学习的过程是在训练数据集合上建立分类器的过程，它同分类过程是相分离的

6、一般的决策树算法就是典型的代表而懒惰式学习算法没有建立清晰的假设，分类过程就是利用训练集合将给定实例与其类标匹配起来的过程，学习过程和学习结果的应用过程是同时进行的采用急切式学习策略的分类器，即对于给定的训练实例集合，在训练阶段就建立好一个分类器，在分类阶段直接地使用该分类器来给一个待分类实例分类Fridman等的TAN分类器就是一种采用急切式学习策略的分类器采用懒惰式学习策略的分类器，在训练阶段不建立一个清晰的假设，而在分类阶段使用训练集合来将给定实例与其类标匹配起来，即在分类时利用训练集合和测试实例建立分类规则为该测试实例来分类LBR分类器就是采用了一种完全懒惰的学习方法；基于实例的分类也

7、采用了懒惰式学习策略一般来讲，对于同一种模型技术，急切式学习策略在效率上大大优于懒惰式学习策略，而懒惰式学习策略在分类精确度上优于急切式学习策略为了使分类器在能够在效率和分类精确度上都达到令人满意的水平，可以对上述两种学习策略进行研究，对同一种分类模型找到一个采用急切式学习策略和懒惰式学习策略的平衡点这是分类器研究的一个突破点，也是本文的研究点之一分类的概念分类是在一个作为输入的训练集合上学会一个分类函数或构造出一个分类模型，即我们通常所说的分类器(Classifier)，然后利用它对数据集合中没有类标的实例指派最适合的类标训练集合是由一组数据实例构成，每个实例是一个由有关字段组成的特征向量，

8、这些字段被称为属性（Attribute），用于分类的属性被叫做类标，类标属性也就是训练集合的类别标记一个具体的实例形式可以表示为(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示属性字段值，c 表示类标给定训练数据集合D=x1, x2 , , xn，分类任务的目标是对数据集合D进行分析，确定一个映射函数f: (A1, A2, , An)C ，使得对任意的未知类别的实例xi=(a1, a2 , , an)可标以适当的类标*18训练集合是构造分类器的基础训练集合是包含一些属性的一个数据库表格，其中的一个属性被制定为分类标签标签属性的类型一般要求是离散的，且标签属性的可

9、能值的数目越少越好（最好是两或三个值）标签值的数目越少，构造出来的分类器的错误率越低分类用于预测数据对象的类别如可以构造一个分类模型来对银行贷款进行风险评估（安全或危险）机器学习、专家系统、统计学和神经生物学等领域的研究人员已经提出了许多具体的分类方法，如贝叶斯方法、决策树、规则推导、人工神经网络、支持向量机、基于实例的方法等1.1.2 监督学习机器学习方法分为有监督的学习和无监督的学习有监督的学习需要给出不同类别的实例作为训练实例，由这些训练实例得到类的描述，然后给新的测试实例匹配类标无监督的学习是在给定实例集合上，根据其内容，在无先验知识的条件下，将实例分成有意义的类其中有监督的学习从学习

10、过程的任务实施方式上可以分成两种极端的情况，即急切式学习策略和懒惰式学习策略急切式学习策略在分类器训练阶段就建立将待分类实例映射到其预测类标上的一个有清晰假设的分类器学习的过程是在训练数据集合上建立分类器的过程，它同分类过程是相分离的一般的决策树算法就是典型的代表而懒惰式学习算法没有建立清晰的假设，分类过程就是利用训练集合将给定实例与其类标匹配起来的过程，学习过程和学习结果的应用过程是同时进行的采用急切式学习策略的分类器，即对于给定的训练实例集合，在训练阶段就建立好一个分类器，在分类阶段直接地使用该分类器来给一个待分类实例分类Fridman等的TAN分类器就是一种采用急切式学习策略的分类器采用

11、懒惰式学习策略的分类器，在训练阶段不建立一个清晰的假设，而在分类阶段使用训练集合来将给定实例与其类标匹配起来，即在分类时利用训练集合和测试实例建立分类规则为该测试实例来分类LBR分类器就是采用了一种完全懒惰的学习方法；基于实例的分类也采用了懒惰式学习策略一般来讲，对于同一种模型技术，急切式学习策略在效率上大大优于懒惰式学习策略，而懒惰式学习策略在分类精确度上优于急切式学习策略为了使分类器在能够在效率和分类精确度上都达到令人满意的水平，可以对上述两种学习策略进行研究，对同一种分类模型找到一个采用急切式学习策略和懒惰式学习策略的平衡点这是分类器研究的一个突破点，也是本文的研究点之一应用变量类型和术

12、语的相关规定得到学习问题规范的数学表达-统计学习基础第二章1.1.3 学习问题实例介绍可在以后发现实际应用例子时再写这部分。股票数据分析、临床数据诊断应用、垃圾邮件的判别-相关论文在金融方面，银行和金融机构往往持有大量的关于客户的，各种服务的以及交易事务的数据，并且这些数据通常比较完整，可靠和高质量，这大大方便了系统化的数据分析和数据挖掘在银行中，数据挖掘被用来建模，预测，识别伪造信用卡，估计风险，进行趋势分析，效益分析，顾客分析等在此领域运用数据挖掘，可以进行贷款偿付预测和客户信用政策分析，以调整贷款发放政策，降低经营风险信用卡公司可以应用数据挖掘中的关联规则来识别欺诈比如银行想知道顾客源在

13、什么样的优惠后可以来开新账户，什么条件下顾客可能会注销已有的账户例如，我们想预测信用卡欺诈行为，可以通过计算机算法分析信用卡用户的购买习惯，从而认识客户的模式，并分辨出偏离模式的信用卡盗用行为使用上面的模型和方法，该学习的过程首先需要有一个训练阶段，提供正反两面方面的偏离例子用挖掘程序来训练训练之后，算法应能推导出合法交易的定义，并能预测一个新的交易是合法的还是非法的智能数据挖掘利用了广泛的高质量的机器学习算法，它能够在应付大量数据的同时，又保证理想的响应时间，使得市场分析，风险预测，欺诈管理，客户关系管理和竞争优势分析等应用成为可以在医疗领域中，成堆的电子数据可能已放在那儿很多年了，比如病人

14、，症状，发病时间，发病频率以及当时的用药种类，剂量，住院时间等在药物实验中，可能有很多种不同的组合，每种若加以实验，则成本太大，决策树方法可以被用来大减少实验次数这种方法已被许多大的制药公司所采用生物医学的大量研究大都集中在DNA数据的分析上人类大约有105个基因，几乎是不计其数因此，数据挖掘成为DNA分析中的强力工具，如：对DNA序列间的相似搜索和比较；应用关联分析对同时出现的基因序列的识别；应用路径分析发现在疾病不同阶段的致病基因等电信业已经迅速从单纯的提供市话和长途服务变为综合电信服务，如语音，传真，移动电话，电子邮件，互联网接入服务电信市场的竞争也变得越来越激烈和全方位化利用数据挖掘来

15、帮助理解商业行为，对电信数据的多维分析，检测非典型的使用模式以寻找潜在的盗用者，分析用户一系列的电信服务使用模式来改进服务，根据地域分布疏密性找出最急需建立网点的位置，确定电信模式，捕捉盗用待业，更好的利用资源和提高服务质量是非常必要的借助数据挖掘，可以减少很多损失，保住顾客1.2 信息论基础主要把所涉及的信息论进行较系统介绍，注意要举例说明。为了寻找对样本进行分类的最优方法，我们要做的工作就是使对一个样本分类时需要问的问题最少（即树的深度最小）因此，我们需要某种函数据来衡量哪些问题将提供最为平衡的划分，信息增益就是这样的函数之一1.2.1信息和熵的概念那么信息熵的定义为：设是训练样本集，它包

16、含n 个类别的样本，这些类别分别用C1, C2, ,Cn, 表示，若给定的概率分布Pi=（P1, P2, Pn ）表示Ci的概率，则由该分布传递的信息量称为P的信息熵，记为：属性A相对实例集合S的信息增益gain(S,A)定义为：1.2.2 信息增益的概念与其他度量方式信息增益用来衡量熵的期望减少值，因此使用属性A相对实例集合S进行的划分获得的信息增益gain(S, A)定义为：gain(S, A)是指因为知道属性A的值后导致的熵的期望压缩gain(S, A)越大，说明选择测试属性A对分类提供的信息越多因为熵越小代表节点越纯，按照信息增益的定义，信息增益越大，熵的减小量也越大，节点就趋向于更纯

17、因此，可以对每个属性按照它们的信息增益大小排序，获得最大信息增益的属性被选择为分支属性1.2.3 杂度函数及相关概念数据挖掘原理与算法、信息论相关书籍！1.3 决策树算法1.3.1 决策树基本算法概述决策树算法是一种常用的数据挖掘算法，它是从机器学习领域中逐渐发展起来的一种分类函数逼近方法决策树学习的基本算法是贪心算法，采用自顶向下的递归方式构造决策树目前利用决策树进行数据分类的方法已经被深入地研究，并且形成了许多决策树算法决策树算法的分类模型是一棵有向无环树，除了根节点以外，决策树的每个节点有且仅有一个父节点每个叶节点对应一个类标号，它的值就是使用决策树对未知样本分类的类标号的值每个内部节点

18、都对应一个分支方案，它包括用于节点分裂的属性和分支的判断规则q训练样本的属性分为数值属性和分类属性，数值属性的取值范围是一个连续的区间，比如实数集；而分类属性的取值范围则是离散值的集合，比如属性性别的取值范围就是集合男，女如果属性是数值属性，那么q的形式是S是的取值范围（）的子集在数学上可以对决策树分类器作如下表述：给定样本集，其中的样本属性c个类别，用i表示中属于第i类的样本集定义一个指标集1, 2数学公式之中数字与标点符号要使用英文“半角”标点符号（随后加空格）。, , c和一个的非空子集的集合1, 2, b我们可以令当ii时，ii一个广义决策规则f就是到的一个映射（记为f：）若f把第i类

19、的某个样本映射到包含i的那个子集Ik中，则识别正确设Q（, ）是由样本集和指标集所形成的所有可能的映射的集合，则Q（, ）可表示为由（ai, i）所组成的集合，元素（ai, i）称为一个节点，ai是该节点上表征这种映射的参数，ii1, i2, 是该节点上指标集i的非空子集的集合令ni和nj是T（, ）的两个元素，其中、若则称ni为nj的父节点，或称nj为ni的子节点设Q（, ，）是节点的有限集，且nB中没有一个元素是n的父节点，则称n是的根节点当Q（, ，）满足下列条件时，它就是一个决策树分类器(1)中有一个并且只有一个根节点(2)设ni和nj是中的两个不同元素，则(3)对于每一个iI，中存在

20、一个节点且中有一个元素是i（与它对应的n的子节点叫叶节点，又称终止节点）1.3.2 决策树生成算法概述通用的自顶向下构建决策树的算法决策树的深度优先构建算法输入：节点，训练数据集，分支指标输出：以节点为根节点的基于数据集，分支指标的决策树Procedure make_tree(N, D, SI) 初始化根节点在中计算，求解节点的分支方案；If(节点满足分支条件)选择最好的分支方案将分为1，2；创建的子节点1，2；make_tree(N1, D1, SI)make_tree(N, D, SI)endifend1.3.3 决策树修剪算法介绍在树的构建阶级生成的决策树依赖于训练样本，因此它可能存在对

21、训练样本的过度适应问题例如，训练样本中的噪声数据和统计波动可能会使决策树产生不必要的分支，从而导致在使用决策树模型对观察样本实施分类时出错为了避免这种错误，需要对决策树进行修剪，除去不必要的分支给定一个假设空间H，假设hH，如果存在假设hH，在训练样本集上h的分类错误率比h小，但在整个样本空间上h的分类错误率比h小，则称假设h过度适应训练样本集剪枝用于解决过度适应的问题剪枝的原则包括：（）奥卡姆剃刀原则如无必要，勿增实体即在与观察相容的情况下，就当选择最简单的一个；（）决策树越小就越容易理解，其存储与传输的代价也就越小；（）决策树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点

22、的假设的样本个数就越少，可能导致决策树在测试集上的分类错误率越大但决策树过小也会导致错误率较大，因此，需要在树的大小与正确之间寻找均衡点常用的剪枝技术有预剪枝（pre-pruning）和后剪枝（post-pruning）两种预剪枝技术限制决策树的过度生长（如CHAID ID3家族的ID3 C4.5算法等），后剪枝技术则是待决策树生成后再进行剪枝（如CART算法等）预剪枝：最直接的预剪枝方法是事先限定决策树的最大生长高度，使决策树不能过度生长这种停止标准一般能够取得比较好的效果不过指定树高度的方法要求用户对数据的取值分布有较为清晰的把握，而且需对参数值进行反复尝试，否则无法给出一个较为合理的树高

23、度阈值更普遍的作法是采用统计意义下的2检验，信息增益等度量，评价每次节点分裂对系统性能的增益如果节点分裂的增益值小于预先给定的阈值，则不对该节点进行扩展如果在最好的扩展增益都小于阈值，即使有些节点的样本不属于同一类，算法也可以终止选取阈值是困难的，阈值较高可能导致决策树过于简化，而阈值较低可能对决策树的化简不够充分预剪枝存在的视野效果的问题在相同的标准下，当前的扩展不满足标准，但进一步的扩展有可能满足标准采用预剪枝的算法有可能过早地停止决策树的构造，但由于不必生成完整的决策树，算法的效率很高，适合应用于大规模问题后剪枝：后剪枝技术允许决策树过度生长，然后根据一定的规则，剪去决策树中那些不具有一

24、般代表性的叶节点或分支后剪枝算法有自上而下的和自下而上的两种剪枝策略自下而上的算法首先从最底层的内节点开始剪枝，剪去满足一定条件的内节点，在生成的新决策上递归调用这个算法，直到没有要可以剪枝的节点为止自上而下的算法是从根节点开始向下逐个考虑节点的剪枝问题，只要节点满足剪枝的条件就进行剪枝决策树修剪的基本算法：Prune_tee（节点）If（节点为叶节点）返回C(t)+1minCost1=prune_tree(N1)minCost2=prune_tree(N2)minCostN=minC(t)+1， Csplit(N)+1+minCost1+minCost2；if(minCostN= =C(t)

25、+1)将的子节点和从决策树中修剪掉；返回minCostN在算法中，t为属于节点的所有训练样本，C(t)和Csplit(N)分别为将作为叶节点和内部节点本构建决策树的代价，算法的基本思想就是要使构建决策树的总代价最小计算C(t)的公式为其中，n 为t 中样本的个数，k 为t 中样本的类别数，ni为t 中属于类i 的样本数计算Csplit(N)要分为两种情况：（）当节点的分支属性为连续属性时，Csplit(N)log2a+log2(v-1)（）当节点的分支属性为离散属性时，Csplit(N)log2a+log2(2 v-2)其中，a 为决策树中用于节点分裂的属性的个数，v是分支属性可能取值的个数目

26、前，决策树修剪策略主要有三种：代价复杂度修剪（cost-complexity pruning），悲观修剪（pressimistic pruning）和基于最小描述长度（minimum description length, MDL）原理的修剪悲观修剪是非曲直uinlan在1987年提出的，该方法将所有的样本用于树的构建和修剪，但是这种方法产生的树太大，并且有时候精度不高代价复杂修剪使用了独立的样本用于修剪，这种策略适用于训练样本比较多的情况在训练样本数目较少的情况下，需要将所有的样本既用于树的构建，又用于树的修剪，基于MDL原理的修剪是使用较多并且效果较好的方法基于MDL原理的决策树算法有两个

27、部分：一是决定数据编码代价和模型编码代价的编码模式，包括数据编码和模型编码；二是比较各个子树，确定是否剪枝的算法MDL修剪过程是一个自底向上的递归过程修剪算法：Pruning_the_tree(t) If t is a leaf node then Return cleaf=1; /cleaf is the cost of a leaf node Else Let cleaf be errors plus 1; /see option(1) If the split attribute is a numeric attribute Ltest=1 Else Count the number o

28、f such tests used in the tree (say n); Ltest=log2(n); Cboth=1+ltest+pruning_the_tree(t.leftchild)+pruning_the_tree(t.rightchild); If cleaf<cboth Prune cboth children of ts, and convert t into a leaf; Return cleaf; Else Return cboth1.4 决策树ID3每个大节与小节之间要有一段文字说明本大节打算讲述的内容（与写作安排或意义）等。1.4.1 ID3的基本概念和相关

29、信息论定义在数据仓库和数据挖掘的应用中，分类是一种非常重要的方法分类的概念是在已有数据的基础上学会一个分类函数或构造出一个分类模型，即我们通常所说的分类器(Classifier）该函数或模型能够把数据库中的数据纪录映射到给定类别中的某一个，从而可以应用于数据预测分类的主要算法有：贝叶斯算法、决策树算法（如ID3、C4.5等）、规则推导、人工神经网络、最近邻算法、支持向量机等等这些算法在许多现实数据集合上可以做比较精确的数据预测，为人们的生活、生产、学习、研究提供了有效的途径其中决策树算法具有良好的可解释性，在实践中的应用最为广泛决策树分类算法的一个典型代表就是ID3算法ID3算法是基于信息论（

30、Information Theory）的方法给定一个记录的集合，每个记录都有相同的结构，并且每个记录是由若干个成对的属性值组成的这些属性代表记录所属的类别ID3需要解决的问题是构造一个决策树，从而可以由非类别的属性值正确地预测出类别属性的值ID3算法可以分为两个阶段，一是建立决策树阶段，一是利用决策树给实例分类的阶段在ID3算法建立决策树的过程中，可以递归地进行：首先，选择一个属性作为根节点，并为每一个可能的属性值生成一个分支这样，把实例集合划分成多个子集合，该属性的每一个值划分为一个子集合现在对每一个分支重复以上的过程，过程中使用的实例集合是属于该分支的实例如果在一个节点的所有实例属于相同的

31、类，则停止扩展那一部分子树这样ID3的所建立的决策树中每一个非叶子节点对应着一个非类别属性，与属性中具有最大信息量的非类别属性相关联；每个叶节点代表从树根到叶节点之间的路径所对应的记录所属的类别属性值在ID3建立决策树的过程中，一个重要的环节就是分裂属性的选择选择分裂属性时ID3中采用了信息增益的标准1.4.2 ID3算法基于ID3的基本思想，ID3的具体算法是：Function ID3R：一个非类别属性集合；C：类别属性；S：一个训练集返回一个决策树BeginIf S为空，返回一个值为丢失值的单个节点；If S是由其值均为相同类别属性值的记录组成，返回一个带有该值的单个节点；If R为空，则

32、返回一个单节点，其值为在S的记录中找出的频率最高的类别属性值；将R中属性之间具有最大gain(D,S)值的属性赋给D；将属性D的值赋给djj=1,2,m;将分别由对应于D的值为dj的记录组成的S的子集赋给sjj=1,2,m ;返回一棵树，其根标记为D，树枝标记为d1,d2,dm;再分别构造以下树：ID3（R-D,C,S1）,ID3（R-D,C,S2）,ID3（R-D,C,S1）;End ID31.4.3一个实例的具体分析下面就以有关天气问题的数据为例仔细介绍一下信息增益的概念和最佳分裂属性的选择过程有关天气问题的数据如表一所示：outlook(类型)temperature(温度)humidit

33、y(湿度)windy(风)play(玩)sunnyhothighFalsenosunnyhothighTruenoovercasthothighFalseyesrainymildhighFalseyesrainycoolnormalFalseyesrainycoolnormalTruenoovercastcoolnormalTrueyessunnymildhighFalsenosunnycoolnormalFalseyesrainymildnormalFalseyessunnymildnormalTrueyesovercastmildhighTrueyesovercasthotnormalFa

34、lseyesrainymildhighTrueno一个属性的信息增益是由于使用这个属性分割实例而导致的期望熵降低例如，属性A相对实例集合S的信息增益Gain(S,A)定义为：对表一中的各非类别属性计算信息增益的过程如下：1计算总的信息熵信息熵的定义为：若给定的概率分布P=（P1,P2,Pn），则由该分布传递的信息量称为P的信息熵，记为：在没有建立决策树之前，训练实例集合包括9个yes和5个no节点，相应总的信息熵为info(9, 5) = 0.940 bits2计算以outlook属性为根节点的树分裂后各个节点的平均信息熵如图以outlook属性为根节点建立的树为：编号与名称（所有）考虑一下每

35、个节点的实例数目，我们计算一下他们的平均信息值；第一个和第三个节点有5个实例，第二个节点有4个，第三个节点有5个：info(2, 3, 4, 0, 3, 2) = (5 / 14) ×0.971 + (4 / 14) × 0 + (5 / 14) × 0.971 = 0.693 bits3计算属性outlook的信息获得gain(outlook) = info(9, 5) - info(2, 3, 4, 0, 3, 2) = 0.940 - 0.693 = 0.247 bits，4重复上述步骤，得到temperature、humidity和windy的信息获得分别

36、为：gain(temperature) = 0.029 bitsgain(humidity) = 0.152 bitsgain(windy) = 0.048 bits，计算出各个非类别属性的信息获得后，我们由此来选择信息获得最大的属性作为分裂属性，由上述计算结果可以看出属性outlook的信息获得最大，则选择其作为分裂属性来建立决策树然后我们继续递归下去，图二表明当outlook = sunny时，可能在节点产生一个更深的分支很明显，还依照outlook（观看）属性来划分下一层分支得不到任何新的东西，所以只考虑其它三个属性他们各自的信息获得值是gain(temperature) = 0.571

37、 bitsgain(humidity) = 0.971 bitsgain(windy) = 0.020 bits，所以我们选择humidity（湿度）作为这个点的划分属性，没有必要作进一步的划分了，这个分支结束继续用同样的方法得到图三的weather（天气）数据的决策树理想的情况是当所有叶子节点是纯洁的时候过程结束即，他们所包含的实例属于同一类然而，也许不可能达到这种状态，因为有可能有一个实例集合，包含两个实例，有同样的属性集合，但属于不同的类，谁也不能保证这种情况不发生，所以当数据不能继续划分时就停止这样就会在运用分类器给实例分类时出现有未分实例的现象上述过程是在ID3算法中建立决策树的过程

38、，建立好决策树后就可以利用些决策树给实例进行分类分类过程是根据待分实例在所建决策树中找到与其匹配的类属性值的过程在程序设计中上也可以通过递归来实现下面以实例（sunny，hot，high，False）为例说明一下其分类过程：待分实例的在根节点outlook属性上的值为sunny，所以沿outlook=sunny路径，将实例分到以humidity属性为根节点的子树上待分实例的在当前根节点humidity属性上的值为high，而 humidity=high路径对应的节点为叶子节点，此叶子节点对应的类属性值为no，因为已到叶子节点所以待分实例的类属性值就为no1.4.4 ID3算法的不足及决策树学习

39、中常见问题（偏置、过度拟合、连续值属性和确实属性的处理）-机器学习1.5 决策树学习的改进算法C4.5类似于ID3基本思想和算法分析C4.5算法是一个里程碑式的决策树算法，是迄今为止在实践中应用最为广泛的机器学习方法。它所采用的是分而治之策略其构造决策树的核心思想是贪心算法，它采用自上而下递归地各个击破方式构造决策树。决策树生成的难点主要有如何处理连续值属性，如何处理缺省值，如何修剪决策树。J48是在weka实验平台下它的具体实现程序1.5 实用的决策树学习算法C C4.5算法的工作流程首先介绍算法，然后再说明各种特定问题。C4.5算法构造决策树的核心思想是贪心算法，它采用自上

40、而下递归地各个击破方式构造决策树。开始时，所有的属性都在根结点，这些属性都是种类字段（如果是连续的，将其离散化），所有记录用所选属性递归的进行分裂，属性的选择是基于一个统计的度量，然后把这个过程递归到每个子树，当一个结点上的数据都是属于同一个类别或者没有属性可以再用于对数据进行分裂时停止分裂。决策树生成之后，对树剪枝以处理过分适应（Over-fitting）的问题。（以下文字的标题有待确定）C4.5分类器使用最大信息增益来选择连续型属性的阈值，它使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。设是s个数据样本的集合，假定类标属性有m个不同值，定义了m个不同类ci

41、 ( i=1, 2， , m )设Si是类ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出其中Pi是任意样本属于Ci概率，并用Si/S估计设连续值属性A的阈值为a，可以用阈值a将S划分为2个子集：S1=样本|属性值A的取值 a，S2=样本|属性值A的取值 a。设Sij是子集Sj中类Ci的样本数。根据由a划分成子集合的熵或期望信息由下式给出对于给定的子集Sj(j=1, 2)其中，Pij=Sij/Sj是Sj中的样本属于类Ci的概率。则属性在阈值a上的信息增益为 换言之，gain(A)由于知道属性A的阈值a而导致的熵期望压缩。在现实数据集合里，属性值缺损的现象很常见。处理缺损值的一个简单

42、办法就是删除有缺损值的实例。另外一种方法是用一个简单值代替缺损属性值。C4.5算法保留有缺损值的实例，采取的方法是：当使用这个属性值有缺损的属性时，按照分裂分支下的训练实例数的比率将有缺损值的实例分成一定比率的碎片23, 25。分而治之构造决策树C4.5构造决策树采取的方法是分而治之递归地构造：首先，计算候选属性的信息熵比率和增益比率，选择一个最佳属性（增益比率最大）作为根节点，并为每一个可能的属性值生成一个分支这样，把实例集合划分成多个子集合（大小为属性值的数目或者为2），该属性的每一个值对应一个子集合现在对每一个分支重复以上的过程，过程中使用的实例集合是属于那个分支的实例集合如果在一个节点

43、的所有实例属于相同的类或者小于叶子节点限制的最少的实例数，则停止扩展那一部分子树处理连续值属性（有例子可以单独作为一小节。）大多数真实数据集合都包含连续值属性。针对连续值属性C4.5采取的方法是二路分裂。C4.5按连续值属性值升序排列数据集合的实例。顺序取两两连续值属性值的中点作为一个分裂点，可以把数据集合分裂为两个子集合。如果连续值属性有n个值，所以有n-1个可以作为分裂点的位置。依照这n-1个分裂点可以计算出n-1个信息熵值，找出其中最大值。将小于并且最接近信息熵最大的分裂点值，且存在于数据集合的属性值定为最终分裂点值。例如：包含连续值属性的天气数据集合（ weather.arff）如表当

44、温度(temperature) 属性作为分裂属性考虑时，C4.5首先按温度(temperature) 属性值升序排列数据集合的实例。温度(temperature) 属性值和类属性(play)值的对应关系如下表：646568697071727580818385YesNoYesYesYesNoNoYesYesNoNoYesYesNo温度(temperature) 属性有12个值，所以有11个可以作为分裂点的位置(例如：以值71和值72的中值作为分裂的分水岭，则可以按>71.5和<71.5将天气数据集合分裂为两个子集合)。依照这11个分裂点可以计算出11个信息熵值，找出其中最大值。假定求

45、出的最大信息熵的分裂点为71.5，J48仍然将小于并且最接近71.5，且存在于数据集合的属性值71定为分裂点值采用枚举型属性和连续值属性作为分裂属性的不同之处，除了在于连续值属性的分裂都是两路分裂，而枚举型属性的分裂是多路分裂外，枚举型属性在决策树里从根到叶子的任一条路径上被作为分裂属性只能是一次，而连续值属性可以被利用多次，只需要每次的分裂点不同就可以。但是这样做导致生成的决策树的深度大为增加，可理解性差，不易于理解。解决的办法是可以采取连续值属性多路分裂，但是难于实现。也可以先调用离散化程序预处理连续值属性，然后再建立决策树。选择最佳分裂属性决策树分类器的核心问题是在树的每个节点上选取最佳

46、分裂属性。最佳的分裂属性应该是分类能力最好的属性。信息增益就是用来形容给定的属性区分训练实例的能力。J48就是利用信息增益在增长树的每一步中选取最佳分裂属性。一个属性的信息增益是由于使用这个属性分割实例而导致的期望熵降低。J48算法计算每一个候选属性的信息增益，接着计算增益比率，然后选择增益比率最高的那个属性作为最佳分裂属性。例如：一个属性的信息增益是由于使用这个属性分割实例而导致的期望熵降低。例如，属性A相对实例集合S的信息增益Gain(S,A)定义为：例如，属性outlook相对与天气数据集合的信息增益Gain(S,outlook)为：SunnyRainyOvercast Yes 2226

47、No123634512J48算法计算每一个候选属性的信息增益，接着计算增益比率SplitInfo(S,outlook)是信息量。1.5.1 处理修改小节编号。未知值的训练样本、处理缺省值的方式处理缺省值（可以考虑加一个例题C4.5.doc）没有处理未知值的训练样本在实际生活的数据集合里，属性值缺省的现象很常见。处理缺省值的一个简单办法就是删除有缺省值的实例。但是含有缺省值的实例通常提供了很多信息。有时候值缺省的属性在决策中不起作用，所以在这种情况下它同其他没有缺省值的实例一样好。C4.5采取的方法是当使用这个缺省属性作为分裂属性时，按照分裂分支下的训练实例数的比例将有缺省值的实例分成一定比例的

48、碎片。1.5.3 实基于的最好不要提及weka!所以就有适当修改下面所使用的数据结构的名字，并且在使用之前加以说明。一个实例的具体分析有关天气问题的数据如表所示：（该实例有待修改完善）Outlook(类型)temperature(温度)humidity(湿度)windy(风)play(玩)Sunny8585FALSENoSunny8090TRUENoOvercast8386FALSEYesRainy7096FALSEYesRainy6880FALSEYesRainy6570TRUENoOvercast6465TRUEYesSunny7295FALSENoSunny6970FALSEYesRai

49、ny7580FALSEYesSunny7570TRUEYesOvercast7290TRUEYesOvercast8175FALSEYesRainy7191TRUENo一计算Outlook属性的分裂信息熵增益以及增益率：currentMGain()=0.24674981977443902currentModel0.gainRatio()=0.15642756242117511计算temperature属性的分裂信息熵增益以及增益率：currentMGain()=-0.18108904235959222currentModel1.gainRatio()=0

50、.0计算humidity属性的分裂信息熵增益以及增益率：currentMGain()=-0.04868985021320138currentModel2.gainRatio()=0.0计算windy属性的分裂信息熵增益以及增益率：currentMGain()=0.04812703040826933currentModel3.gainRatio()=0.048848615511520685选择信息上增益率最大的作为分裂节点，因此这次选择的是属性下标签为0的属性作为分裂节点，也就是上表所示的outlook属性作为分裂节点二其中选择最佳分裂节点后的数据集为：说

51、明：localInstances0为outlook=sunny，localInstances为outlook=overcast，localInstances2为outlook=rainylocalInstances0=sunny,75,70,TRUE,yessunny,69,70,FALSE,yessunny,85,85,FALSE,nosunny,80,90,TRUE,nosunny,72,95,FALSE,nolocalInstances1=overcast,64,65,TRUE,yesovercast,81,75,FALSE,yesovercast,83,86,FALSE,yesover

52、cast,72,90,TRUE,yeslocalInstances2=rainy,65,70,TRUE,norainy,75,80,FALSE,yesrainy,68,80,FALSE,yes,rainy,71,91,TRUE,norainy,70,96,FALSE,yes如图以outlook属性为根节点建立的树为：然后依次在此基础上继续向下递归分裂数据构造决策树：outlook=sunny在localInstances0上构建决策树的过程及其相应的输出结果：（outlook=sunny）Outlook属性的分裂信息熵增益以及增益率：currentMGain()=0.0cu

53、rrentModel0.gainRatio()=0.0temperature属性的分裂信息熵增益以及增益率：currentMGain()=0.21997309402197512currentModel1.gainRatio()=0.22655436360850295humidity属性的分裂信息熵增益以及增益率：currentMGain()=0.7709505944546688currentModel2.gainRatio()=0.7940162958421904windy属性的分裂信息熵增益以及增益率：currentMGain()=

54、0.019973094021975158currentModel3.gainRatio()=0.020570659450693245要选择信息上增益率最大的作为分裂节点，因此这次选择的是属性下标签为2的属性作为分裂节点，也就是上表所示的humidity属性作为分裂节点；此时将数据集分成两份：localInstances0（humidity<=70）和localInstances1 （humidity>=70）(采用二路分裂的方法，上面讲过)localInstances0=sunny,75,70,TRUE,yessunny,69,70,FALSE,yeslocalInstances1=sunny,85,85,FALSE,nosun