概念：
- 决策树是一个树状结构（二叉树或非二叉树），并且以树状结构表示数据的分类结果
- 决策树是先构建树状模型，然后进行决策。
- 决策树最常用于分类问题和回归两个方向。
- 分类问题：将现有的数据分成若干类，对于新的数据，我们根据所分的类进行划分。
- 回归问题：将现有数据拟合成一条函数，根据所拟合的函数来预测新的数据。
- 决策树的分类：
在决策树中，也有回归树和分类树的概念。在二者区别上，回归树是采用最大均方误差来划分节点，并且每个节点样本的均值作为测试样本的回归预测值；而分类树是采用信息增益或者是信息增益比来划分节点，每个节点样本的类别情况投票决定测试样本的类别。**我们可以看到，这两者的区别主要在于划分方式与工作模式。**回归树采用最大均方误差这种对数据精确处理的方式，输出连续变量，可以更好地给我们的数据进行预测；而分类树使用一个非常宽泛的信息增益这个变量，更好的从整体把握这个数据集的分类。
- 决策树的组成：
- 根节点。决策过程从根节点开始。
- 非叶子节点。包含了中间结果值。
- 叶子节点。最终结果值，每一个叶子节点都是唯一的一个类别值或决策值。
- 分支。每个分支代表这个特征属性在某个值域上的输出。
决策树学习步骤：
- 特征选择：选择特征的标准是找出局部最优的特征，判断一个特征对于当前数据集的分类效果，也就是按照这个特征进行分类后，数据集是否更加有序（不同分类的数据应该被尽量隔开）
- 决策树生成：决策树生成包含ID3算法和C4.5算法两种，具体后面介绍
- ID3：信息增益（有什么问题）。
- C4.5：信息增益率（解决ID3问题，考虑自身熵）。
- 备注：1. CART：使用GINI系数来当作衡量标准
- 备注：2. GINI系数：和熵的衡量标准类似，计算方式不同
- 决策树的修剪：决策树生成算法对于训练集是很准确的，但是这样会出现过拟合，所以需要通过剪枝（简化过程）来提高泛化能力。
一、特征选择
- 问题：根节点的选择该用哪个特征呢？接下来呢？如何切分呢？
- 想象一下：我们的目标应该是根节点就像一个老大似的能更好的切分数据（分类的效果更好），根节点下面的节点自然就是二当家了。
- 目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。
衡量标准——信息熵
信息熵：在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵（entropy）的概念，并给出了计算信息熵的数学公式：
公式：
x代表了集合中各个分类的概率，其中log2为取以2为底的对数。当不确定性越大时，信息熵也就越高。
条件熵：H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的期望。
eg :
假设有 2 个集合：
- 集合 1：5 个男生，1 个女生。
- 集合 2：3 个男生，3 个女生。
将男生看做类别 1，女生看做是类别 2。在集合一种类别 1 的概率是 1/6，类别 2 的概率为 5/6，所以可以算出信息熵为：
在集合二中，类别 1 和类别 2 的概率都是 0.5，所以信息熵为：
可以看到，信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低。
信息增益：特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information）,决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益比：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比：
信息增益比是在信息增益的基础上再除以一个总的熵，具体优点会在C4.5算法中介绍。
二、决策树生成
构造树的原则：
随树深度增加，节点的熵迅速降低。熵降低的速度越快越好，这样就有望得到一颗高度最矮的树。
- ID3算法
- ID3算法就是在生成树的时候，计算所有备选特征的信息增益，然后再选择下一个节点是哪个特征。
H(D)的结果即信息增益直接影响我们选择的哪个特征来作为节点进行切分数据，需要设置一个阈值e,当信息增益小于这个阈值的时候停止循环。下面是完整算法：
ID3： 输入：训练数据集D,特征集A，阈值e； 输出 : 决策树T 1、 若D中国所有实例属于同一类Ck，则T为单结点树，并将Ck作为该结点的类标记，返回T； 2、 若A=空集，则T为单结点树，并将D中的实例数最大的类Ck作为该结点的类标记，返回T； 3、 否则，计算A中各特征对D的信息增益，（具体怎么计算请看我前一条关于决策树基础的博客）选择信息增益最大的特征Ag； a) 如果Ag的信息增益小于阈值e，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T； b) 否则，对Ag的每一个可能值ai；依Ag=ai将D分割为若干非空子集Di；将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T； 4、 对第i个子结点，以Di为训练集，以A-{Ag}为特征集，递归调用（1）~（5），得到子树Ti，返回Ti。
缺点：ID3算法存在一个问题，就是偏向于多值属性。例如，如果存在唯一标识ID，会导致信息增益最大，则ID3会选择它作为根节点（分裂属性）。这样虽然使得划分充分纯净，但是ID只是一个标识符号，与特征毫无关联。
- C4.5
C4.5选择具有最大信息增益比的特征作为节点划分数据，其具体应用与ID3类似。能处理连续型的属性，首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各分类点Gini值大小。
缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据，即在计算增益时，仅考虑具有属性值地记录。
注意考虑评价函数，希望越小越好，类似损失函数。
三、剪枝： 预剪枝，后剪枝
我们之前说过，构造树地原则要求尽可能地构造一棵高度最矮地树。如果决策树过高过大，意味着树有大量的分支，并且意味着叶子节点被划分的纯度非常地高，最终所有地节点熵值累加近似或等于0，但是这并不能说明决策树构造的好。
因为树越高，他考虑的样本也就越多，并将每个样本包含更加少量的数据（有的样本数据甚至只有一条数据），假设树中有一个错误数据，树被划分地太碎，错误数据就有可能被单独划分到一个样本中，这样模型就会学习到错误点，也叫噪音点。并且对当前样本数据分类准确，但是泛化能力低。
解决方法：预剪枝，后剪枝。
剪枝就是为了解决过拟合现象，通过剪枝提高泛化能力。剪枝地思路也非常简单，就是在决策树对训练数据的预测误差和树复杂度之间找一个平衡。
预剪枝：边建立决策树边进行剪枝操作（更加实用）。限制深度，叶子节点个数、叶子节点样本数，信息增益量等。
后剪枝：当建立玩决策树后来进行剪枝操作，通过一定的标准（叶子节点越多，损失越大）
