下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
一道决策树例题中概率分叉点上的数字不明白怎样得出来?（就是B上的5000是怎样得出来的?）
从末端反算回来的：4-1=5000
为您推荐：
其他类似问题
扫描下载二维码最近一段时间在上学习，里面有个assignment涉及到了决策树，所以参考了一些决策树方面的资料，现在将学习过程的笔记整理记录于此，作为备忘。
决策树（Decision Tree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
先看看下面的数据表格：
拥有房产（是/否）
婚姻情况（单身，已婚，离婚）
年收入（单位：千元）
无法偿还债务（是/否）
上表根据历史数据，记录已有的用户是否可以偿还债务，以及相关的信息。通过该数据，构建的决策树如下：
比如新来一个用户：无房产，单身，年收入55K，那么根据上面的决策树，可以预测他无法偿还债务（蓝色虚线路径）。从上面的决策树，还可以知道是否拥有房产可以很大的决定用户是否可以偿还债务，对借贷业务具有指导意义。
决策树构建的基本步骤如下：
1. 开始，所有记录看作一个节点
2. 遍历每个变量的每一种分割方式，找到最好的分割点
3. 分割成两个节点N1和N2
4. 对N1和N2分别继续执行2-3步，直到每个节点足够&纯&为止
决策树的变量可以有两种：
1） 数字型（Numeric）：变量类型是整数或浮点数，如前面例子中的&年收入&。用&&=&，&&&,&&&或&&=&作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。
2） 名称型（Nominal）：类似编程语言中的枚举类型，变量只能重有限的选项中选取，比如前面例子中的&婚姻情况&，只能是&单身&，&已婚&或&离婚&。使用&=&来分割。
如何评估分割点的好坏？如果一个分割点可以将当前的所有节点分为两类，使得每一类都很&纯&，也就是同一类的记录较多，那么就是一个好分割点。比如上面的例子，&拥有房产&，可以将记录分成了两类，&是&的节点全部都可以偿还债务，非常&纯&；&否&的节点，可以偿还贷款和无法偿还贷款的人都有，不是很&纯&，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。
前面讲到，决策树是根据&纯度&来构建的，如何量化纯度呢？这里介绍三种纯度计算方法。如果记录被分为n类，每一类的比例P(i)=第i类的数目/总数目。还是拿上面的例子，10个数据中可以偿还债务的记录比例为P(1) = 7/10 = 0.7，无法偿还的为P(2) = 3/10 = 0.3，N = 2。
Gini不纯度
熵（Entropy）
上面的三个公式均是值越大，表示越 &不纯&，越小表示越&纯&。三种公式只需要取一种即可，实践证明三种公司的选择对最终分类准确率的影响并不大，一般使用熵公式。
纯度差，也称为信息增益（Information Gain），公式如下：
其中，I代表不纯度（也就是上面三个公式的任意一种），K代表分割的节点数，一般K = 2。vj表示子节点中的记录数目。上面公式实际上就是当前节点的不纯度减去子节点不纯度的加权平均数，权重由子节点记录数与当前节点记录数的比例决定。
决策树的构建过程是一个递归的过程，所以需要确定停止条件，否则过程将不会结束。一种最直观的方式是当每个子节点只有一种类型的记录时停止，但是这样往往会使得树的节点过多，导致过拟合问题（Overfitting）。另一种可行的方法是当前节点中的记录数低于一个最小的阀值，那么就停止分割，将max(P(i))对应的分类作为当前叶节点的分类。
采用上面算法生成的决策树在事件中往往会导致过滤拟合。也就是该决策树对训练数据可以得到很低的错误率，但是运用到测试数据上却得到非常高的错误率。过渡拟合的原因有以下几点：
噪音数据：训练数据中存在噪音数据，决策树的某些节点有噪音数据作为分割标准，导致决策树无法代表真实数据。
缺少代表性数据：训练数据没有包含所有具有代表性的数据，导致某一类数据无法很好的匹配，这一点可以通过观察混淆矩阵（Confusion Matrix）分析得出。
多重比较（Mulitple Comparition）：举个列子，股票分析师预测股票涨或跌。假设分析师都是靠随机猜测，也就是他们正确的概率是0.5。每一个人预测10次，那么预测正确的次数在8次或8次以上的概率为 ，只有5%左右，比较低。但是如果50个分析师，每个人预测10次，选择至少一个人得到8次或以上的人作为代表，那么概率为 ，概率十分大，随着分析师人数的增加，概率无限接近1。但是，选出来的分析师其实是打酱油的，他对未来的预测不能做任何保证。上面这个例子就是多重比较。这一情况和决策树选取分割点类似，需要在每个变量的每一个值中选取一个作为分割的代表，所以选出一个噪音分割标准的概率是很大的。
优化方案1：修剪枝叶
决策树过渡拟合往往是因为太过&茂盛&，也就是节点过多，所以需要裁剪（Prune Tree）枝叶。裁剪枝叶的策略对决策树正确率的影响很大。主要有两种裁剪策略。
前置裁剪 在构建决策树的过程时，提前停止。那么，会将切分节点的条件设置的很苛刻，导致决策树很短小。结果就是决策树无法达到最优。实践证明这中策略无法得到较好的结果。
后置裁剪 决策树构建好后，然后才开始裁剪。采用两种方法：1）用单一叶节点代替整个子树，叶节点的分类采用子树中最主要的分类；2）将一个字数完全替代另外一颗子树。后置裁剪有个问题就是计算效率，有些节点计算后就被裁剪了，导致有点浪费。
优化方案2：K-Fold Cross Validation
首先计算出整体的决策树T，叶节点个数记作N，设i属于[1,N]。对每个i，使用方法计算决策树，并裁剪到i个节点，计算错误率，最后求出平均错误率。这样可以用具有最小错误率对应的i作为最终决策树的大小，对原始决策树进行裁剪，得到最优决策树。
优化方案3：Random Forest
是用训练数据随机的计算出许多决策树，形成了一个森林。然后用这个森林对未知数据进行预测，选取投票最多的分类。实践证明，此算法的错误率得到了经一步的降低。这种方法背后的原理可以用&三个臭皮匠定一个诸葛亮&这句谚语来概括。一颗树预测正确的概率可能不高，但是集体预测正确的概率却很高。
准确率估计
决策树T构建好后，需要估计预测准确率。直观说明，比如N条测试数据，X预测正确的记录数，那么可以估计acc = X/N为T的准确率。但是，这样不是很科学。因为我们是通过样本估计的准确率，很有可能存在偏差。所以，比较科学的方法是估计一个准确率的区间，这里就要用到统计学中的置信区间（）。
设T的准确率p是一个客观存在的值，X的概率分布为X ~ B(N,p)，即X遵循概率为p，次数为N的二项分布（Binomial Distribution），期望E(X) = N*p，方差Var(X) = N*p*(1-p)。由于当N很大时，二项分布可以近似有正太分布（Normal Distribution）计算，一般N会很大，所以X ~ N(np,n*p*(1-p))。可以算出，acc =&X/N的期望E(acc) = E(X/N) = E(X)/N = p，方差Var(acc) = Var(X/N) = Var(X) / N2 = p*(1-p) / N，所以acc ~ N(p,p*(1-p)/N)。这样，就可以通过正太分布的置信区间的计算方式计算执行区间了。
正太分布的置信区间求解如下：
1） 将acc标准化，即
2） 选择置信水平&= 95%，或其他值，这取决于你需要对这个区间有多自信。一般来说，&越大，区间越大。
3） 求出 &/2和1-&/2对应的标准正太分布的统计量 和 （均为常量）。然后解下面关于p的不等式。acc可以有样本估计得出。即可以得到关于p的执行区间
[1] 《数据挖掘导论》Chapter 4 Classification:Basic Concepts, Decision Trees, and Model Evaluation，Pang-Ning Tan & Micheal Steinbach & Vipin Kumar著
[2] Data Analyis, Lectures in Week 6,7 at Coursera
[3] 《集体智慧编程》Chapter 7 Modeling with Decision Tree，Toby Segaran著
[4] 《Head First Statistics》 Chapter 12 置信区间的构造, Dawn Griffiths 著
阅读(...) 评论() 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
决策树习题练习（答案）
下载积分：300
内容提示：决策树习题练习（答案）
文档格式：DOC|
浏览次数：2060|
上传日期： 18:51:20|
文档星级：
该用户还上传了这些文档
决策树习题练习（答案）
官方公共微信实习了一段时间，接触了一些数据挖掘、机器学习的算法，先记录下来方便以后的复习回顾：
一：决策树概念
　　决策树可以看做一个树状预测模型，它是由节点和有向边组成的层次结构。树中包含3中节点：根节点、内部节点、叶子节点。决策树只有一个根节点，是全体训练数据的集合。树中每个内部节点都是一个分裂问题：指定了对实例的某个属性的测试，它将到达该节点的样本按照某个特定的属性进行分割，并且该节点的每一个后继分支对应于该属性的一个可能值。每个叶子节点是带有分类标签的数据集合即为实例所属的分类。
　　决策树算法很多，例如：ID3、C4.5、CART等。这些算法均采用自上而下的贪婪算法，每个内部节点选择分类效果最好的属性来分裂节点，可以分成两个或者更多的子节点，继续此过程直到这棵决策树能够将全部的训练数据准确的分类，或所有属性都被用到为止。该算法的简化版本是在使用了全部样本的假设来构建决策树的。具体步骤如下：
　　（1）：假设T为训练样本集。
　　（2）：从属性集合Attributes中选择一个最能区别T中样本的属性。
　　（3）：创建一个树节点，它的值为所选择的属性。创建此节点的子节点，每个子链代表所选属性的一个唯一值（唯一区间），使用子链的值进一步将样本细分为子类。
　　&　　　对于每一个分支继续重复（2）（3）的过程，直到满足以下两个条件之一：
　　　　　　(a):所有属性已经被这条路径包括。
　　　　　　(b):与这个节点关联的所有训练样本都具有相同的目标属性（熵为0）。
　　下面借用《数据挖掘概念与技术》书中的一个列子来方便理解：
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　图1-1
　　图1-1是一个典型的决策树，它表示概念buys_computer,即它目的是预测顾客是否可能购买计算机。内部节点用矩形表示，叶子节点用椭圆表示。
　　为了对未知的样本分类，样本的属性值在决策树上测试。我们用一些训练样本构造了图1-1中的决策树，每个内部节点表示一个属性上的测试，每个叶子节点代表一个分类（buys_computer = yes, buys_computer = no ）.
二：决策树的适用情况
　　通常决策树学习最适合具有以下特征的问题：
　　（1）：实例是由&属性-值&对表示的。
　　（2）：目标函数具有离散的输出值。例如上面的yes和no
　　（3）：实例的所有属性都是离散值。如果是连续值或者离散值种类太多，可以把它分为不同的区间，例如上面的age分为了3个区间而不是每个独立的值为一个判断分支。
三：决策属性的选择
　　建树算法中属性的选择非常重要。属性选择方法很多种，例如信息增益（information gain）、信息增益比（information gain ratio）、Gini 指标（Gini Index）等方法。
　　ID3算法依据的是信息增益来选择属性,每次计算所有剩余候选属性的信息增益，然后根据信息增益最大的一个作为此次的分类属性。信息增益是用熵作为尺度，是衡量属性对训练数据分类能力的标准。
　　假设表3-1为图1-1中的训练样本集：共有14条数据，属性有：age、income、student、credit_rating,目标属性是：buys_computer
　　　　　　　　　　　　　　　　　　　　　　　　　　　　表3-1　　
下面根据表3-1和图1-1的例子来讲解某具体属性的信息增益的计算过程：
　　对于某个具体的属性A，它的信息增益计算表达式是：
　　（1）是对给定样本分类所需的期望信息，计算过程如下：
　　设S是s个训练样本的集合，S也就是对于表3-1中的数据，s = 14。假定类标号属性有m个不同值，定义m个不同类Ci（i=1,2,...m）.设si是类Ci中的样本数，对应表3-1和图1-1实例中m=2,其中 C1 = yes C2 = no s1 = 9 s2 = 5 。
　　其中pi是任意样本属于Ci的概率，pi = si/s .公式中的对数函数以2为底，因为信息用二进位编码。
　　　　在该实例中&　　　　
　　（2）是根据A划分子集的熵或期望值，计算过程如下：
　　　　设属性A有v个不同的值{a1,...av},对应实例中的数据，例如属性age，分为3个不同的值:
　　　　a1为&&=30
　　　　a2为&30..40
　　　　a3为&&40 ;
　　　　　　
　　　　属性A把训练样本集合S划分为v个子集{S1,...Sv};其中Sj包含训练样本集S中在属性A上有值aj的样本。Sij是子集Sj中属于类Ci的样本数。
　　　　其中充当第j个子集的权值，等于子集（即A值为aj）的样本总数除以S中的样本总数 即 Sj/S。
　　　　对于给定的子集Sj有
　　　　其中，Pij=Sij/Sj　　,是Sj中的样本属于Ci的概率。
　　　　该实例中：
　　　　　　　　
& & & & 因此属性age的信息增益为：Gain（age）= I（s1,s2） - E(age) = 0.246
　　　　类似的我们可以计算出Gain(income)=0.029 Gain(student)=0.151 Gain(credit_rating)=0.048.由于age在属性中具有最高信息增益，因此它被选作为第一个测试属性。
　　　　图1-1是最终生成的决策树。
四：决策树的剪枝
　　为了防止决策树和训练样本集的，需要对决策树进行剪枝。剪枝通常有事先剪枝法和事后剪枝法。
　　事先剪枝法： 是建树过程中判断当前节点是否需要继续划分的剪枝方法。通常是通过重要性检测判断是否停止分裂节点。
　 &事后剪枝法：&是让树充分生长之后，再判断是否将某些分支变成节点。常用方法是根据错误分裂率（或者决策树编码长度）进行决策树的事后修剪。
参考资料：机器学习& Mitchell T.M
　　　　　数据挖掘：概念与技术 第三版 &Jiawei Han &
阅读(...) 评论()下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
决策树上每个节点都有数字,是怎样算的
决策树(Decision Tree）是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法.由于这种决策分支画成图形很像一棵树的枝干,故称决策树.在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系.Entropy = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法使用熵.这一度量是基于信息学理论中熵的概念.
为您推荐：
其他类似问题
扫描下载二维码