上一章主要描述了ID3算法的的原理，它是以信息熵为度量，用于决策树节点的属性选择，每次优选信息量最多的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0，此时每个叶子节点对应的实例集中的实例属于同一类。理想的决策树有三种：1.叶子节点数最少2.叶子加点深度最小3.叶子节点数最少且叶子节点深度最小。在实际的操作中还会设计到ID3算法的收敛，过度拟合等问题下面依次进行描述1.ID算法收敛2.过度拟合问题1.ID3算法的收敛当ID3确定根节点以及后续节点之后，因此当算法满足以下条件该分支的既可以结束1.该群数据的每一个数据都已经归类到同一类别中2.该群数据已经没有办法找到新的属性进行节点分割3.该群数据已经没有任何尚未处理的数据。2.过度拟合问题原因：造成多度拟合的潜在原因主要以下两个方面1.噪声导致的过度拟合比如错误的分类，或者属性值。2.缺乏代表性样本所导致的过度拟合方法：1.预剪枝通过提前停止树的构建而对树剪枝，一旦停止，节点就是树叶，该树叶持有子集元祖最频繁的类。停止决策树生长最简单的方法有：1.定义一个高度，当决策树达到该高度时就停止决策树的生长2.达到某个节点的实例具有相同的特征向量，及时这些实例不属于同一类，也可以停止决策树的生长。这个方法对于处理数据的数据冲突问题比较有效。3.定义一个阈值，当达到某个节点的实例个数小于阈值时就可以停止决策树的生长4.定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。2.后剪枝方法后剪枝（postpruning）：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。以上可以理解为后剪枝的基本思想，其中后剪枝方法主要有以下几个方法：Reduced-Error Pruning(REP,错误率降低剪枝）Pesimistic-Error Pruning(PEP,悲观错误剪枝）Cost-Complexity Pruning（CCP，代价复杂度剪枝)EBP(Error-Based
Pruning)（基于错误的剪枝）以下分别进行说明：1.REPREP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：1：删除以此结点为根的子树2：使其成为叶子结点3：赋予该结点关联的训练数据的最常见分类4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。REP是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。这是因为一些不会再测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过如果训练集较小，通常不考虑采用REP算法。尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。2.PEP悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。对于一颗叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一颗子树，它有L个叶子节点，那么该子树的误判率估计为：这样的话，我们可以看到一颗子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在的标准误差内。对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过统计出来），那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和标准差：把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率e为(E+0.5)/N，因此叶子节点的误判次数均值为使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝：这个条件就是剪枝的标准。当然并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。话不多说，上例子：在上述例子中T8种的类1可以认为是识别错误的T4这课子树的估计错误为5，T4子树的最后叶子节点为3个上述是悲观错误剪枝。悲观剪枝的准确度比较高，但是依旧会存在以下的问题：1.PeP算法实用的从从上而下的剪枝策略，这种剪枝会导致和预剪枝同样的问题，造成剪枝过度。2.Pep剪枝会出现剪枝失败的情况。d代价复杂度剪枝：该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数α，其中，代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，α则表示剪枝后树的复杂度降低程度与代价间的关系，定义为:其中，|N1|：子树Tt中的叶节点数；R（t）：结点t的错误代价，计算公式为R（t）=r（t）*p（t），r（t）为结点t的错分样本率，p（t）为落入结点t的样本占所有样本的比例；R（Tt）：子树Tt错误代价，计算公式为R（Tt）=∑R(i)，i为子树Tt的叶节点。CCP剪枝算法分为两个步骤：1.对于完全决策树T的每个非叶结点计算α值，循环剪掉具有最小α值的子树，直到剩下根节点。在该步可得到一系列的剪枝树｛T0，T1，T2......Tm｝,其中T0为原有的完全决策树，Tm为根结点，Ti+1为对Ti进行剪枝的结果；2.从子树序列中，根据真实的误差估计选择最佳决策树。上例子：EBP：o第一步：计算叶节点的错分样本率估计的置信区间上限Uo第二步：计算叶节点的预测错分样本数–叶节点的预测错分样本数=到达该叶节点的样本数*该叶节点的预测错分样本率Uo第三步：判断是否剪枝及如何剪枝–分别计算三种预测错分样本数：o计算子树t的所有叶节点预测错分样本数之和，记为E1o计算子树t被剪枝以叶节点代替时的预测错分样本数，记为E2o计算子树t的最大分枝的预测错分样本数，记为E3–比较E1，E2，E3，如下：oE1最小时，不剪枝oE2最小时，进行剪枝，以一个叶节点代替toE3最小时，采用“嫁接”(grafting)策略，即用这个最大分枝代替t其算法的具体过程可以参考附件以下是几种剪枝的方法的比较：REPPEPCCP剪枝方式自底向上自顶向下自底向上计算复杂度0(n)o(n)o(n2)误差估计剪枝集上误差估计使用连续纠正标准误差附件列表&
阅读(...) 评论()证明:在非空的二叉树中，满结点的个数+1=叶子个数_百度知道
证明:在非空的二叉树中，满结点的个数+1=叶子个数
我有更好的答案
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数(n2)之和：
n=no+n1+n2 (式子1)　
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2　　树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)　　由式子1和式子2得到：
no=n2+1即叶子节点个数 = 满结点个数 + 1
问你一个问题
证明，高度为k的二项树恰有2∧k个结点
采纳率：96%
来自团队：
为您推荐：
其他类似问题
二叉树的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
二叉排序树的定义是： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； （4）没有键值相等的节点。
从上图分析可知（1）最大节点必定在右子树中（2）最大节点必定在右子树中的某个右孩子上
然而这某个右孩子并不一定是叶子节点。然而这某个右孩子并不一定是叶子节点。然而这某个右孩子并不一定是叶子节点。
反例如图。以上。
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
肯定不是啊！好好看查找树定义，如果根节点的右子树有左子树，但是没有右子树，那么最大值就不是叶子节点了
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
所以最大值肯定出现在这个搜索树的最右边的右孩子上，但是它不一定是叶子节点
同步到新浪微博
分享到微博？
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。设一颗完全二叉树叶子结点数为K,最后一层结点数大于2,则该二叉树高度为多少?_百度知道
设一颗完全二叉树叶子结点数为K,最后一层结点数大于2,则该二叉树高度为多少?
设一颗完全二叉树叶子结点数为K,最后一层结点数大于1,则该二叉树高度为多少?
我有更好的答案
完全二叉树叶子结点数为k,因此度为2的结点个数为k - 1度为1的结点个数可能为1，也可能为0因此该完全二叉树中结点总数为2k 或者2k - 1原则上说，该完全二叉树的高度为：下取整(log2(2k)) + 1或者下取整(log2(2k-1)) +1如果不加限制，这两个高度可能会相差1考虑到最后一层结点数大于1，此时这两个数相等
采纳率：75%
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。以下试题来自：
问答题简答题一棵树有3度节点100个，2度节点200个，该树有叶子节点多少个，该树可以有多少个度为1的节点？
N.0=n2+2n3+1
=200+2*100+1
为您推荐的考试题库
您可能感兴趣的试卷
你可能感兴趣的试题
GFEDCBJIKHA
2.填空题 03.填空题 04.填空题 O（n）5.填空题 sq->rear=（sq->rear+1）%m