一.决策树
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置。
二.ID3算法和CART算法
1.ID3算法
判断一个特征的分类性能可以利用信息增益，信息增益越大，从而纯度越高。所以ID3算法核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。
设X是一个取有限个值得离散随机变量，则X的熵（entropy）表示为：,其中。 而条件熵定义为， 特征A对于训练数据集D的信息增益定义为。
具体做法： (1) 从根节点开始，计算所有节点的信息增益，选择信息增益最大的特征作为结点的特征，由该特征对样本划分子结点； (2) 在对子结点递归地调用以上方法，构建决策树； (3) 直至所有特征的信息增益均很小或没有特征可以选择为止，得到决策树。 另外C4.5算法是ID3算法的改进，C4.5在生成的过程中，用信息增益比来选择特征。
信息增益比： 特征A对训练数据集D的信息增益比定义为信息增益与D关于A的值的熵之比，即
2.CART算法
分类与回归树(classification and regression tree, CART)模型是广泛使用的决策树学习方法，可分类可回归。
- 回归树的生成
在训练数据集D中，递归地将每个区域划分成两个子区域，并决定每个子区域的输出值。
(1) 选择最优切分变量和切分点(即这个切分变量的值取多少)，即求解：\
遍历所有变量，选择最小值的对。
(2) 用选定的对划分区域并决定相应的输出值：\
(3) 重复1，2直至满足停止条件；
(4) 将输入空间划分为M个区域，生成决策树：
- 分类树的生成 分类树用基尼指数选择最优特征和该特征的最优二值切分点。
基尼指数： 假设有K个分类，样本属于第k类的概率为, 则概率分布的基尼指数定义为：
$$Gini(p) = \sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2$$ 对于给定的样本集合D，基尼指数为，是D中属于第k类的样本子集。 对于样本集合D中，某特征A取定值后，将D分为后，集合D的基尼指数定义为:
$$Gini(D, A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$ 基尼指数越大，样本集合的不确定性也就越大。
具体生成算法：
(1) 1对于样本D，计算特征A取各个值得Gini指数；
(2) 在所有可能特征A以及它们所有可能的切分点中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点；
(3) 对两子结点递归调用(1)，(2)，直至满足停止条件；
(4) 生成CART决策树。
三.决策树的剪枝
决策树生成算法通过递归产生决策树，但这样往往会出现过拟合的情况。原因在于学习时过多考虑如何提高对训练数据集的分类正确，构造了过于复杂的树结构。所以定义决策树学习的损失函数：
其中C(T)为决策树对训练集的预测误差，表示决策树的复杂度，为考虑复杂度的超参数。
剪枝算法：
(1) 计算每个结点的经验熵；
(2) 递归从树的叶节点向上回缩，回缩到其父结点之前和之后的整体树为，若，则进行剪枝；
(3) 重复(2)，直至不能继续。
对于以上的剪枝算法，算法性能依赖于超参数。
Breiman等人证明：可以递归对树进行剪枝。将从小增大，，产生一系列区间， 在这些区间上有对应的最优子树序列
对于整体树内的任意内部结点t，损失函数为，以t为根结点的子树的损失函数是。
当，有相同的损失函数，而t的节点少，对进行剪枝。
所以得到CART剪枝算法如下：
(1) 设。
(2) 自上而下得计算各内部结点的以及。
(3) 自上而下地访问内部结点，如果有，进行剪枝，并对叶结点以多数表决来决定其类，得到树T。
(4) 设
(5) 如果T不是由根结点单独构成的树，则返回步骤(3)。
(6) 采用交叉验证法得到字数序列，从中选取最优子树。
