一、什么是决策树
所谓决策树，就是一个类似于流程图的树形结构，树内部的每一个节点代表的是对一个特征的测试，树的分支代表该特征的每一个测试结果，而树的每一个叶子节点代表一个类别。树的最高层是就是根节点。下图即为一个决策树的示意描述，内部节点用矩形表示，叶子节点用椭圆表示。
二、决策树的优缺点
1、优点
a) 计算简单，易于理解
b) 适应不同的数据类型（包括类别数据，数值数据，未归一化的和混合的数据）
c) 比较适合处理有缺失属性的样本
d) 通过分裂的顺序给数据特征赋不同的重要性
e) 能够处理不相关的特征
f) 在相对短的时间内能够对大型数据源做出可行且结果良好的结果
g) 决策树构成了其他算法的基础（如boosting和随机数）
2、缺点
a) 容易发生过拟合（随机森林可以很大程度上减少过拟合）；
b) 忽略了数据之间的相关性；
c) 对于那些，各类别样本数量不一致的数据，在决策树中，信息增益的结果偏向于那些具有更多数值的特征（只要使用了信息增益，都有这个特点，如RF）
三、算法的计算过程
第一步，特征选择：
特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
问题：根节点的选择该用哪个特征呢？即如何确定一个判断节点是最好的？
例如上面那个丈母娘是否满意女婿的决策树，有的丈母娘觉得年龄大自己女儿太多不行，有的觉得一定要买房才可以，所以判断的节点先后很重要，一系列下来才能做出自己的抉择。
答：熵、GINI系数
特征挑选方法——信息增益法：信息增益既可以用熵也可以用GINI系数来计算
选择具有最高信息增益的特征作为测试特征，利用该特征对节点样本进行划分子集，会使得各子集中不同类别样本的混合程度最低，在各子集中对样本划分所需的信息（熵）最少
信息增益=信息熵-条件熵，即信息增益代表了在一个条件下，信息复杂度（不确定性）减少的程度。如果选择一个特征后，信息增益最大（信息不确定性减少的程度最大），那么我们就选取这个特征。
举例：
可以求得随机变量X（嫁与不嫁）的信息熵为：
嫁的个数为6个，占1/2，那么信息熵为-1/2log1/2-1/2log1/2 = -log1/2=0.301
现在假如我知道了一个男生的身高信息。
身高有三个可能的取值{矮，中，高}
矮包括{1,2,3,5,6,11,12}，嫁的个数为1个，不嫁的个数为6个
中包括{8,9} ，嫁的个数为2个，不嫁的个数为0个
高包括{4,7,10}，嫁的个数为3个，不嫁的个数为0个
先回忆一下条件熵的公式如下：
我们先求出公式对应的:
H(Y|X = 矮) = -1/7log1/7-6/7log6/7=0.178
H(Y|X=中) = -1log1-0 = 0
H(Y|X=高） = -1log1-0=0
p(X = 矮) = 7/12,p(X =中) = 2/12,p(X=高) = 3/12
则可以得出条件熵为：
7/120.178+2/120+3/12*0 = 0.103
那么我们知道信息熵与条件熵相减就是我们的信息增益，为
0.301-0.103=0.198
所以我们可以得出我们在知道了身高这个信息之后，信息增益是0.198
以此类推，每个节点都可以算出他的信息增益，在全部算出之后对比，可以得出信息增益最大的节点是哪个，那么就可以选出接下来的节点了。
GINI系数同理，只是和熵的算法不一致，原理相同。
ps：上面举例的数据是离散型的，如果是连续型的数据，那么必须进行离散化哦
第二步，决策树生成：
根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。
步骤如下：
- 从根节点出发，根节点包括所有的训练样本。
- 一个节点（包括根节点），若节点内所有样本均属于同一类别，那么将该节点就成为叶节点，并将该节点标记为样本个数最多的类别。
- 否则利用采用信息增益法来选择用于对样本进行划分的特征，该特征即为测试特征，特征的每一个值都对应着从该节点产生的一个分支及被划分的一个子集。
- 递归上述划分子集及产生叶节点的过程，这样每一个子集都会产生一个决策（子）树，直到所有节点变成叶节点。
- 递归操作的停止条件就是：
（1）一个节点中所有的样本均为同一类别，那么产生叶节点
（2）没有特征可以用来对该节点样本进行划分。此时也强制产生叶节点，该节点的类别为样本个数最多的类别
（3）没有样本能满足剩余特征的取值，即对应的样本为空。此时也强制产生叶节点，该节点的类别为样本个数最多的类别
第三步，剪枝：
由于噪声等因素的影响，会使得样本某些特征的取值与样本自身的类别不相匹配的情况，基于这些数据生成的决策树的某些枝叶会产生一些错误；尤其是在决策树靠近枝叶的末端，由于样本变少，这种无关因素的干扰就会突显出来；由此产生的决策树可能存在过拟合的现象。树枝修剪就是通过统计学的方法删除不可靠的分支，使得整个决策树的分类速度和分类精度得到提高。
为什么要剪枝：决策树过拟合风险很大，理论上可以完全分得开数据
想象一下，如果树足够庞大，每个叶子节点不就一个数据了嘛
剪枝策略：预剪枝，后剪枝
树枝修剪包括预剪枝和后剪枝两种方法：
（1）预剪枝：边建立决策树边进行剪枝的操作（更实用）
在决策树生成分支的过程，除了要进行基础规则的判断外，还需要利用统计学的方法对即将分支的节点进行判断，比如统计χ2或统计信息增益，如果分支后使得子集的样本统计特性不满足规定的阈值，则停止分支；但是阈值如何选取才合理是比较困难的。
（2）后剪枝：当建立完决策树后来进行剪枝操作
在决策树充分生长后，修剪掉多余的分支。根据每个分支的分类错误率及每个分支的权重，计算该节点不修剪时预期分类错误率；对于每个非叶节点，计算该节点被修剪后的分类错误率，如果修剪后分类错误率变大，即放弃修剪；否则将该节点强制为叶节点，并标记类别。产生一系列修剪过的决策树候选之后，利用测试数据（未参与建模的数据）对各候选决策树的分类准确性进行评价，保留分类错误率最小的决策树。
四、基础算法
1、ID3
（1）简述
ID3算法是最早提出的一种决策树算法，ID3算法的核心是在决策树各个节点上应用信息增益准则来选择特征，递归的构建决策树。具体方法是：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点：再对子节点递归的调用以上方法，构建决策树：直到所有的特征信息增益均很小或没有特征可以选择为止。
（2）优点
a) 假设空间包含所有的决策树，搜索空间完整。
b) 健壮性好，不受噪声影响。
c) 可以训练缺少属性值的实例。
（3）缺点
a) ID3只考虑分类型的特征，没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
b) ID3算法对于缺失值没有进行考虑。
c) 没有考虑过拟合的问题。
d) ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。
e) 划分过程会由于子集规模过小而造成统计特征不充分而停止。
2、C4.5
（1）简述
C4.5算法与ID3算法决策树的生成过程相似，C4.5算法对ID3算法进行了改进。它是用信息增益率（比）来 选择特征。
（2）优点
a) C4.5是ID3的改进，采用信息增益率进行特征选择。
b) 为了处理连续值，C4.5采用单点离散化的思想，用信息增益率来进行连续值特征的属性值选择。
（3）缺点
a) C4.5时间耗费大
b) C4.5没解决回归问题
3、CART
（1）简述
使用CART（分类回归树）来解决回归问题，CART是一颗二叉树，哪怕某个特征有多类（年龄有青年，中年，老年），也是进行二分叉（青年一个叉，中年老年一个叉）再继续分下去。
而之后树相关的集成算法如随机森林，GDBT，XGBoost中的弱分类器用的都是CART。
关于分类问题，CART和ID3, C4.5的思想是一样的，用损失函数来划分特征，选择特征划分的属性值。只是ID3，C4.5用的是信息增益，CART用的是基尼指数。
（2）优点
a) 可以处理连续型属性
b) 将信息增益改为信息增益比，以解决偏向取值较多的属性的问题
（3）缺点
a) C4.5在ID3的基础上进行了改进，如选择信息增益率作为损失函数，采用单点离散化对连续型特征进行处理，但是不能处理回归问题。
b) CART对于分类问题选用基尼指数作为损失函数，对于回归问题使用平方误差作为损失函数，一个结点里的预测值采用的是这个结点里数据结果的平均数（比如房价）。
这三类算法都是贪心算法，找到的是局部最优分裂方法。
总结一个表：看该如何选择以上算法？
