大家好，我是机器学习小白毛同学，今天本篇文章来和大家一起学习一下决策树的原理部分

其实和大家一样，我最不喜欢看的，就是算法原理部分，因为这一部分充满了公式、符号

可是，“小白”想要变“怪兽”教程魔方就不可能绕过变量名这一部分

不过毛同学再写文章的时候会尽量用易懂的话语，具体的例子来让原理不那么难懂

写的不合适的算法工程师地方，多多包涵啦

本文目录：

1.1 决策树是如何工作的

1.2 构建决策树

1.2.1 ID3算法构建决策树

1.2.2 简单实例

1.2.3 ID3的局限性

1.3 C4.5算法 &a教程的意思mp;教程之家提取码 CART算法

1.3.1 修改局部最优化条件

1.3.教程英语2 连续变量处理手段

1.1 决策树是如何工作的

决策树（Decision Tree）是一种索引符号非参数的有监督学习方法，它能够从一索引系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，

以解决分类和回归问题。决策树算法容易理解，适用各种数据，在解决各种问题时都有良好表现，尤其是以树模型为核心的各索引超出了数组界限什么意思种集成算法，在各个行业和领域都有广泛的应用。

上面的话是不是似懂非懂的？没关系，我们再进一步解释。

决策树算法的本质是一种图结构。

它好比就是一个很乖巧的“秘书”。

我们只要不断问他问题，我们就能得到我们想要的答案。

如果说上面的解释，你还是不懂。

那就放弃吧（狗头）

那我们来看个具体的例子吧

比如说，来看看下面这组数据集

​

这张表格很的意思很清晰，我就不再说明了，我们要做的是根据这些数据，来将动物分类。

那么决策树是如何来完成这项工作的呢，它会给我们画一张图：

​

有了这教程之家张图，我们就能知道索引超出了数组界限什么意思某种位置分类的动物到底是属于哪一类。比如豪猪。教程之家教学视频

下面我们开始问问题了：

它的体温是冷血还是恒温？ 恒温

它是否是胎生？ 是

那么根据图我们可知，豪猪是哺乳动物。

那么有的同学就会蹦起来抛出一个问题：那么多属性，你怎么不问，你为什么偏偏要问这几个属性？你怎么算法导论不问它是不是有腿呢？

这就是决策树要解决的问题了

决策书就是要算法的时间复杂度取决于在众多的属性中选取较重要的前几个属性来建立树

那么该算法是如何来选属性的呢？别急，后面我们会分析清楚变量与函数的！

上图中的最初的问题所在的地方叫做根节点，在得到结论前的每一个问题都是中间节点，而得到的每一个结论（动物的类别）都叫做叶子节点。

根节点	没有进边，有出边。包含最初的，针对特征的提问。
中间节点	既有进边也有出边，进边只有一条，出边可以有很多条。都是针对特征的提问。
叶子节点	有进边，没有出边，每个叶子节点都是一个类别标签。
子节点和父节点	在两个相连的节点中，更接近根节点的是父节点，另-个是子节点。

读到这里，相信你对决策树已经有了一定的了解，那么我们先做一个小总结吧：

那么决策树要解决的核心问题是什么呢？

（1）如何从数据表中找出最佳节点和最佳分枝?

（2）如何让决策树停止生长，防止过拟合?

几乎所有决策树有关的模型调整方法，都围绕这两个问题展开。

1.2 构建决策树

接下来算法的有穷性是指我们来说说如何根据已有变量名的数据集来建立有效的决策树。

显然，任意一个数据集上的所有特征都可以被拿来分枝，特征上的任意节点又可以自由索引失效组合

所以一个数据集上可以发展出非常非常多棵决策树，其数量可达指数级。

在这些树中，肯定有一颗最好的，这个最好索引图的树叫做 “全局最优树” 。

全局最优	经过组合形成的，整体来说分类效教程果最好的变量名的命名规则模型
局部最优	每一次分枝的时候都向着更好的分类效果分枝，但无法教程的意思确认如此生成的索引超出矩阵维度树在全局上是否是最优索引是什么意思的

要在这么多棵决算法导论策树中去一次性找到分类效果最佳的那一棵是不可能的算法是指什么

如果通过排列组合来进行筛选，计算量过于 大而且低效，因此我们不会这样做。

相对的，机器学习研究者们开发了一些有效的算法，能够在合理的时间内构造出 具有一定准确率的次最优决策树。

这些算法基本都执行”贪心策略“，即通过局部的最优来达到我们相信是最接近全局 最优的结果。

贪心算法	通过实现局部最优来达到接近全局最优结果的算法，所有的树模型都是这样的算法。

最典型的算法是指什么决策树算法是Hunt算法，该算法是由Hunt等人提出的最早的决策树算法。

现代，Hunt算法是许多决策树算 法的基础，算法的有穷性是指包括ID3、C4.5和CART等。

Hunt算法诞算法的时间复杂度取决于生时间较早，且基础理论并非特别完善，此处以应用较广、理论 基础较为完善的ID3算法的基本原理开始，讨论如何利用局部最优化方法来创建决策模型。

1.2.1ID3****算法构建决策树

ID3算法原型见于J.R Quinlan的博士教程论文，是基础理论较为完善，使用较为广变量名的命名规则泛的决策教程英语树模型

在此基础上J.R Quinlan进行优化后，陆续推出了C4.5和C5.0决策树算法

后二者算法的五个特性现已称为当前最流行的决策树算法，我们先变量与函数从ID3 开始讲起，再讨论如何从ID3逐渐优化至C4.5

为了要将表格转化为-棵树，决策树需要找出最佳节点和最佳的分枝方法，而衡量这个“最佳”的指标叫做不纯度”。

不纯度基于叶子节点来计算的，所以树中的每个节点都会有一个不纯度，并且子节点的不纯度一定是低于父节点的，也就是说，在同一棵决策树上，叶子节点的不纯度-定是最低的。

不纯度	决策树的每个叶子节点中都会包含一组数据，在这组数据中索引符号，如果有某一类标签占有较大的比例，我们就说叶子 节点“纯”，分枝分得算法的有穷性是指好。某一类标签占的比例越大，叶子就越纯，不纯度就越低，分枝就越好。 如果没有哪机器学习一类标签的比例很大，各类标签都相对平均，则说叶子节变量英语点”不纯“，分枝不好，不纯度高。

如果说上面的表格，你还是不能理解，那么我们进一步来解释

分类型决策树在叶子节点上的决策规则是少数服从多数

在一个叶子节点索引超出矩阵维度上，如果某一类标签所占的比例较大，那所索引页是哪一页有教程的意思进入这个叶子节点的样本都回被认为是这一类别。

距离来说，如果9算法导论0%根据规则进入叶子节点的样本都是类别0（叶子比较纯），那新进入叶子节点的测试样本的类别也很有可能是0。

但是，如果51%的样本是0，49%的样本是1（极端情况算法的五个特性），叶子节点还是会被认为是O类叶子节点，但此时此变量泵刻进入这个叶子的测试样本点几乎有一半的可能性应该是类别1。

从数学上来说，类分布为（0，100%）的结点具有零不纯性，而均衡分布（变量名50%，50%）的结点具有最高的不纯性。

如果变量叶子本身教程视频怎么制作方法不纯，那测试样本就很有可能被判断错误，相对的叶子越纯，那样本被判断错误的可能性就越小。

​

​

通常来说，不纯度越低，决策树对训练集的拟合越好。

现在使用的决策树算法在分枝方法上的核心大多是围绕在对变量之间的关系某 个不纯度相关指标的最优化上。

若我们定义t代表决策树的某节点，​是t节点所对应的数据集，设​表示给定结 点t中属于类别 的样本所占的比例，这个比例越高，则代表叶子越纯。

那么我们如何来计算不纯度呢教程拼音？

注教程拼音意了，我要开始放公式了，相信我，静下来，认真读，一定可以看懂的！

对算法是指什么于节点不纯度的计算和表示方法因决策树模型而异变量与函数，但不管不纯度的度量方法如何，都是由误差率衍生而来，其计 算公式如下：

​

误差率越低，则纯度越高。由此还衍生出了其他两个常用指标，一个是ID3中Information gain（信息增益） 的计算 方法索引图可用Entropy推导，即最为人熟知的信息教程熵，又叫做香农熵，其计教程视频怎么制作方法算公式如下：

​

其中 表示叶子节点上标签类别的个数，c-1 表示标签的索引。注意在这里，是从第0类标签开始计算，所以最后的 标签类别应该是总共c个标签，c-1为最后一个标签的索引。在计算Entropy时设定索引页是哪一页​ 。

另一个指标则是Gini （基尼）指数，主要用于CART决策树的纯度判定中，其计算公式如下：

​

上面的公式读完后，算法我们来看一个例子：

​

能够看出，索引的作用三种方法本质上都相同教程视频怎么制作方法，在类分布均衡时（即算法工程师当p=0.5时）达到最大值，而当所有记录都属于同一个类时 （p等于1或0）达到最小值。

换而言之，在纯度较高时三个指数均较低，而当纯度较低时变量与函数，三个指数都比算法导论较大，且可 以计算得出，熵在0-1区间内分布，而Gini变量指数和分类误索引的作用差均算法的空间复杂度是指在0-0.5区间内分布，三个指数随某变量占比增加而变化 的曲线如下所示：

​

决策树最终的优化目标是使得叶节点的总不纯度最低，即对应衡量不纯度的指标最低。

I教程之家教学视频D3采用信息熵来衡量不纯度，此处就先以信息熵为例进行讨论。

ID3最优条件是算法叶节点的总信息熵最小，因此ID3决 策树在决定是否对某节点进行切分的时候，会尽可能索引超出了数组界限什么意思选取使得该节点对教程之家教学视频应的子节点信息熵最小的特征进行切分。

换而 言之，就是要求父节点信息熵和子节点总信息熵之差要最大。对于ID3而言变量名，二者之差就是信息增益，即Informa算法工程师tion gain。索引失效

但这里需要注意，一个父节点下可能有多个子节点，而每个子节索引失效点又有自己的信息熵，所以父节点信息熵和子节点信 息熵之差，应该是父节点的信息熵 – 所有子节变量的定义点信息熵的加权平均。

其中，权重是使用单个叶子节点上所占的样本量 比上父节点上的总样本量来确定的一个权重。

​

而父节点和子节点的不纯度下降数可由下述公式进行计算：

​

I(.)是给定结点的不纯性度量（即是基尼系数或者信息上），N是父结点上的样本数，k是这一层上子节点的个数， N(vj) 是与子结点vj相关联的样本个算法的特征数。

决算法导论策树算变量值法通常选择最大化增益 的测试条件，因为对任何分枝过程来说， I(parent)都是一个不变的值（因为此时父节点已经存在并且不可修改）

所以最大化增益等价于最小化子结点的不纯 性衡量的加权平均。索引页是哪一页最后，当选择算法设计与分析熵（entropy）作为公式的不纯性度量时，熵的教程之家差就是所谓信息增益 （Information gain） i索引页是哪一页nfo。

看完这两个公示，我们再看个例子吧变量泵！

1.2.2简单实例

假设现在有如下数据集，是一个消费者个人属性和信用评分数据，标签是”是否会发生购买电脑行为“

仍然是个而分 类问题，在此数据集之上我们使用ID3构建决教程策树模型，并提取有效的分类规则。

​

首先计算原始数据集的信息熵，我们可设置树模型中每个节点信息熵的表示方变量之间的关系法，首先对于根节点而言，信息熵可用 I（s1，s2）索引是什么意思来表示，其中s下标1和2代表两个分类变量是什么意思水平，s1和s2则代表分类水平下的对应样本个数，其计算公式如下所示∶

​

即在不进行任何切分前，总信息熵为0.940。

然后我们依次选取各特征来尝试进索引是什么意思行切分，并计算切分完成后的子节点 信息熵是多少。

首先选取age列进行切分，age是三分类的离散变量，因此若用age对根节点进行切分，将有三个分 支，每个分支分别对应一个age的取值，分支所指向的子节点为对应的切分后的数教程英文翻译据集：

​

然后我们计算算法是指什么子节点的信息熵：

​

即对于age属性而言，在根节点上切分一次之后子节点的信息熵为0.694，由此我们可计算a变量名的命名规则ge的信息增益，即局部最 优化判别指标：

​

以索引失效的几种情况此类推，我们还能计算其他几个特征的信息增益，最终计算结果如下

Gain(income) = 0.029，Gain(student) = 0.15，Gain(credit_rating) = 0.048，

很明显，第一次切分过程将采用索引失效的几种情况age字 段进行切分：

​

age=”<=30″数据集 :

​算法设计与分析

age=”>40″数据集:

​

第一次切分完成后，分成了三个数据集，其中age=“31…40″分类指标所指向的数据集纯度为1，因此不用再进行切 分

而其他两个数据集算法的有穷性是指则需要进一步进行切分，对于age=”<=30″的数据集而言使用student特教程魔方征进行切分后子节点纯 度就将为1

而age=”>40″算法的时间复杂度取决于的数据集则可采用credit_rating字段进行切分。最终ID3决策树模型如下所示：

​

总的来说，决策树模型是一个典型的贪心模型，总目标是一个全局算法是指什么最优解，即一整套合理的分类规则使得最终叶节点 的纯度最高

但全局算法分析的目的是最优解在随特征增加而呈现算法的空间复杂度是指指数级增加的搜索空间内很难高效获取，因此我们退而求其次，考虑 采用局部最优来一步步推导结果——只要保证信息增益最大

我们就能得到次最优的模型。当然，局部最优不一定等 于全局最优，接下来我们就ID3可能存在的一些问题及改进方向进算法的时间复杂度取决于行一些讨论。

1.2.3 ID3的局限性

ID3局限主要源于局部最优化条件，即信息增益的计算方法，其局限性主要有算法的有穷性是指以下几点：

（1）分支度越高（分类水平越多）的离散变量往往子节点的总信息熵会更小，ID3是索引超出矩阵维度按照某一列进行切分，有一些列 的教程之家分类可能不会对我需要的结果有足够好的指示。

极限情况下取ID作为切分字段，每个分类的纯度都是100%， 因算法导论此这样教程之家提取码的分类方式是没有效益的。

（2）不能直接处理连续型变量，若要使用ID3处理连续型变量，则首先需要对连续变量进行离散化 。

（3）对缺失值较为敏感，使用ID3算法的有穷性是指之前需要提前对缺失值进行处理。

（4）没有剪枝的设置，容易导致过拟合，即在训练集上表现很好，测试集上表现很差。

过拟合	模型在训练集上表现教程拼音很好，在测试集上表现很糟糕，学习能力很强但是学得太过精细了
欠拟合	模型在训练集和测试集上都表现糟糕，学习能力算法分析的目的是不足

关于剪枝和过拟合相关问题，我们会在最后进行详细讨论，此处先讨论其他局限性如何解决。对于ID3的诸多优化措 施，最终也构成了C4.5算法的核心内容。

1.3 C4.5算法&CART算法

1.3.1修改局部最优教程拼音化条件

在C4.5中，首先通过引入分支度（IV：Information Value）（在《数据挖掘导论》一书中被称为划分信息度）的概 念，来对信息增益的计算方法进行修正

简而言之，就算法设计与分析是在信息增益计算方索引超出矩阵维度法的子节点总信息熵的计算方法中添加了 随着分类变量水平的惩罚项。

而分支度的计算公式仍然是基于熵的算法，只是将信息熵计算公式中索引是什么意思的教程视频怎么制作方法 ​(即某类别 样例占总样例数)改成了​，即某子节点的总样本数占父节点总样本数的比例

这其实就是我们加权求算法分析的目的是和时的 ”权重“ 。

这样的一个分支度指标，让我们在切分的时候，变量自动避免那些分类水平太多，信息熵减小过快的特征影响模 型，减少过拟合情况。IV计算公式如下：

​

其中算法的五个特性，i表示父节点的第i个子节点，vi表示第i个子节算法导论点样例数，​表示第i个子节点拥有样例数占父节点总样例数的比例。

很明显，Information Value可作为惩罚项带入子节点的信算法的空间复杂度是指息熵计算中。可以变量名简单计算得出，当取ID字段作为切分字段时，Information Val算法的有穷性是指ue值为log2k。

所以V值会随着叶子节点上样本量的变小而逐渐变大，这就是说一个特征中如果标签分类太多，每个叶子上的Information Value值就会非常大。

最索引页是哪一页终，在C4.5中，使用之前的信息增益除以分支度作为选取切分字段的参考指标，该指标被算法称作Gain Ratio（获利比 例，或增益算法导论率），计算公式如下：

​

增益比例算法的特征是我们决定对哪一列进行分枝的标准，我们分枝的是数字最大的那一列，本质是信息增益最大，分支度又较 小的教程之家提取码列（也就是纯度提升很快，但又不是靠着把类别分特别细来提升的那些特征）。

Information索引失效的几种情况 Value越大，即某一列的分类水平越 多，Gain ratio实现的惩罚比例越大。变量值当然，我们还是希望GR越大越好。

​

然后我们可利用GR代替Information Gain重算法是指什么新计算1.2.3的实例

例如计算a索引失效ge字段的G教程画画R，由于根据age字段切分 后，3个分支分别有5个、4个和5个样例数据，因此age的IV指标计算过程如下：

​

进而可计算age列的GR：

​

然后可进一步计算其他各字段的GR值，并选取GR值最大的字段进行切分。

1.3.2 连续变量处理手段

在C4.5中，同样还增加了针对连续变量的处理手段。如果输入特征字段是连续型变量，则有下列步骤：

1. 算法首先会对这一列数进行从小到大的排序

2. 选取相算法的有穷性是指邻的两个数的中间数作为切分数据集的备选点，若一个连续变量有N个值，则在C4.5教程英文翻译的处理过程中将产生

N-1个备选切分点，并且每个切分点都代表着一种二叉树的切分方案，例如：

​

这里需要注意索引的是，此时针对连续变量的处理并非是将其转化为一个拥有N-1个分类水平的分类变量，而是将其转化 成了N-1个二索引分方案

而在进行下一次的切分过程中，这N-1个方案都要单独带入考虑，其中每一个切算法的特征分方案和一个 离散变量的地位均相同（一个离散变量就是一个单独的多路切分方案）。

例如有如下数据集，数据集中只有两个字 段，第一行代表年龄，是特征变量，第二行代表性别，是目标字段，则对年龄这一连续变量的切分方案如图所示：

​

从上述论述能够看出，在对于包含连续变量的数据集进行树索引的优缺点模型构建的过程中要消耗更变量与函数多的运算资源。

但于此同时， 我们也会发现，当连续变量的某中间点参与到决策树的二分过程中，往往代表该点对于最终分类结果算法工程师有较大影响

这 也为我们连算法是指什么续变量的算法的五个特性分箱压缩提供了指导性意见，例如上述案例，若要对a算法的特征ge列进行压缩，则可考虑使用36.5索引页是哪一页对其进 行分箱

则分箱结果对于性别这一目标字段仍然具有较好的分类效果，这也是决策树的最常见用途之一，也是最重要 的模型指导分箱的方法。

现在被大量使用的是C4.5的改进CART树，CART变量名的命名规则树本质其实和C4.5区别不大，只不过CART树所教程有的层都是二叉树， 也就是每层只有两个分枝。

让我们用CART树来走过一遍C4.5的流程。假设年龄是特征，性别是标签：

1. 首先将年龄从小算法设计与分析到大依此进行排列

2. 然后计算俩俩相邻的年龄的均值

3. 按均值所在的点，对连续性变量进行二分（变成数字形式的，第一类是变量是什么意思>均值，第二类是<均值）， 二分得到的 点叫做决策树的“ 树桩”。

这是说，对于一个含有n个记录的连续性变量来说教程的意思，就会存在n-1个潜在切分点，这n-1 个潜在切分点的获益比例都都会被计算。算法是指什么

4. 找每种二分切分方案的获益比例，获益比例最大的切分点，就是切点。

5. 切完之后，计算加权信息熵，计算信息增益，引入分支度，可以计算出增益比例了。

需要注意的是，这种切分方法，每次切分之后，并没有消费掉一列，只消费掉了一个备选点。

在我们原本的切分方法 中，ID3每次切分就会消费掉一整个列

但实际上，我们可以只关注每次分类的时候，对信息熵的减少贡献最多的那 个分类。

按我们的例子变量是什么意思来说，我们在分类age的时候，最关注的是3140岁的那一个分类，我们完全可以实现， 3140一类，其他算一变量类

然后我们再对“其他”这个类别进行相似的二分类。这就是CART的核心原理，大量地减少了 计算的量。

对于KNN算法变量名，我们有一个假设：就是每一个特征对于我们的推断的重要性是一样变量泵的。

这也是KNN最大的缺陷。而 决策树天生就认为每个特征对于推断的重要性不是一样的

而CART索引的优缺点则是进一步认为，每个特征下的每个分类对于推 断的重要性也不是一样的。

到这里，决策树的基本流程其实可以简单概括如下：

​

直到没有更多的特征可用，或整体的不纯度指标已经最优，决算法的五个特性策树就会停止生长。

写在后面：

本文参考教程：菜菜的sk-learn课程

如有写的不合适，亦或是不精确的地方，望读者多包涵