本文来讲述一下机器学习中常见的一个基础分类与回归算法——决策树。
决策树算法虽然常见，但是通常并不是单独使用，我们通常把多个决策树组合在一起组成新的分类器去使用，如随机森林（RF）、GBDT算法等。
决策树的概念
通常情况下我们用到的决策树都是在分类模型中，本文我们也只讨论分类问题。
先来看一下决策树的定义：分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点和有向边组成，节点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
简单的用我们都理解的if-then来说一下，决策树可以看做是一个if-then规则的集合，if用来表示属性（特征），then用来表示分类结果。决策树的结构如下图所示：
信息增益
理解了决策树的概念和基本结构，再来说一下决策树的构造，但是在构造决策树之前，根据树形结构我们考虑在进行分类的时候哪个特征起到了更重要的作用，这样的特征我们是不是应该把它放在更重要的位置呢，又要怎样去确定一个特征是否重要呢？这个时候信息增益就起到了很大的作用。
我们先来一步步的说一下信息增益。
熵
熵一字通常出现在信息论和概率统计中，熵通常用来度量随机变量的不确定性。
设X是一个取有限个值得离散随机变量，其概率分布为：
则随机变量X的熵为：
（通常式子中的log会以2为底或者以e为底）
根据上式我们可以看到式子中并没有涉及到X的取值，而是涉及到了X的分布，所以我们可以认为熵只和X的分布有关，是和X的取值无关的，所以我们也可以把熵的式子定义成：
对于伯努利分布来说，H(p)随概率P的变化如下图所示：
根据图像可以知道，当P=0和P=1时，H(p)=0，随机变量完全没有不确定性，而当P=0.5时，H(p)=1,随机变量的不确定性最大。举个例子来说就是当我们抛一个两面都一样的硬币时，可以得到的结果是确定的，而抛正常的硬币时，是完全随机的，也就是不确定性很大，此时熵也是最大的。
条件熵
条件熵H(Y|X)表示的是在已知随机变量X的情况下，随机变量Y的不确定性，条件熵的定义如下：
信息增益
信息增益表示得知X的信息而使得类Y的信息不确定性减少的程度。
定义：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：
g(D,A)=H(D)−H(D|A)g(D,A)=H(D)−H(D|A)
通常情况下我们把熵和条件熵的差称作为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。
特征选择：
对训练数据集D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。
分类决策树的生成
在决策树的生成算法中有常用的ID3和C4.5算法，下面我们来依次介绍一下两种算法。
ID3
上一节中我们了解了信息增益，ID3算法就是用信息增益来选择特征，递归构建决策树。
主要方法：
从根节点开始，对节点计算所有可能特征的信息增益，选择信息增益最大的特征作为节点的特征，并且由该特征取不同的值来建立子节点，再对子节点递归调用上述方法来构建决策树，知道所有的信息增益都变得很小或者没有特征可以选择的时候，得到最终的决策树。
算法步骤如下：
输入：训练数据集D，特征集A，阈值ε；
输出：决策树T.
Step1：若D中所有实例属于同一类CkCk，则T为单结点树，并将类CkCk作为该节点的类标记，返回T；
Step2：若A=Ø，则T为单结点树，并将D中实例数最大的类CkCk作为该节点的类标记，返回T；
Step3：否则，2.1.1（3）计算A中个特征对D的信息增益，选择信息增益最大的特征AgAg；
Step4：如果AgAg的信息增益小于阈值ε，则T为单节点树，并将D中实例数最大的类CkCk作为该节点的类标记，返回T
Step5：否则，对AgAg的每一种可能值aiai，依Ag=aiAg=ai将D分割为若干非空子集DiDi，将DiDi中实例数最大的类作为标记，构建子结点，由结点及其子树构成树T，返回T；
Step6：对第i个子节点，以DiDi为训练集，以A−{Ag}A−{Ag}为特征集合，递归调用Step1~step5，得到子树TiTi，返回TiTi；
C4.5
C4.5的算法整个流程都和ID3算法相同，他们之间的区别就在于C4.5把ID3算法中使用的信息增益用信息增益比来代替了。
信息增益比
我们知道信息增益会偏向取值较多的特征，使用信息增益比可以对这一问题进行校正。
定义：特征A对训练数据集D的信息增益比GainRatio(D,A)定义为其信息增益Gain(D,A)与训练数据集D的经验熵H(D)之比：
分类与回归树（CART）
CART同样是一种生成决策树的算法，CART同样由特征选择，树的生成及剪枝组成，既可以用于分类也可以用于回归。
CART是在给定输入随机变量X的条件下输出随机变量Y的条件概率分布的学习方法。
上节中讲到的ID3和C4.5算法采用了信息增益和信息增益比作为特征选择的方法，在CART中，对回归树用平方误差最小化准则，对分类树使用基尼指数（Gini index）最小化准则进行特征选择。
Gini指数
Gini指数描述的是数据的纯度，与信息熵含义类似。
（Ck是D中属于第K类的样本子集，K是类的个数）
CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类，与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切分成两份，分别进入左右子树，特征A的基尼指数为：
CART算法
输入：训练数据集D，停止计算的条件
输出：CART决策树
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉树：
Step1：设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点A=a的测试为“是”或“否”将D分割为D1和D2两部分，利用上式Gini(D,A)来计算A=a时的基尼指数。
Step2：在所有可能的特征A以及他们所有可能的切分点a中，选择基尼指数最小的特征及其对应可能的切分点作为最有特征与最优切分点。依最优特征与最有切分点，从现结点生成两个子节点，将训练数据集依特征分配到两个子节点中去。
Step3：对两个子结点递归地调用Step1、Step2，直至满足条件。
Step4：生成CART决策树
算法停止计算的条件是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或者没有更多特征。
决策树的优化
当我们把所有的特征都放入决策树中的时候，树的模型会显得很大，同时也大概率的会造成过拟合现象的产生，为了避免该现象的发生，我们需要对决策树进行剪枝。
决策树的剪枝通常有两种方法：预剪枝和后剪枝。
预剪枝
预剪枝的核心思想是在树中节点进行扩展之前，先计算当前的划分是否能够带来模型泛化能力的提升，如果不能则不再继续生长子树。
预剪枝对于何时停止决策树的生长有如下的几种方法：
（1）当树达到一定深度的时候，停止树的生长。
（2）当达到前节点的样本数量小于某个阈值的时候，停止树的生长。
（3）计算每次分裂对测试集的准确度的提升，当小于某个阈值的守，不在继续扩展。
后剪枝
后剪枝的思想是让算法生成一颗完全生长的决策树，然后从最上层计算是否剪枝，剪枝过程将子树删除，用一个叶子节点代替，该节点的类别同样按照多数投票的原则进行判断。
常见的后剪枝的方法包括：错误率降低剪枝，悲观剪枝，代价复杂度剪枝，最小误差剪枝，CVP，OPP等，这些方法各有利弊，这里不再一一介绍。
决策树的优缺点
优点：计算复杂度不高，输出结果易于理解，对于中间值的缺失不敏感，可以处理不相关特征数据。
缺点：容易产生过拟合的问题。
适合的数据类型：数值型和标称型。
