本文仅作网络笔记用，不定时完善。
决策树根据输出的不同，分为回归树和分类树，但两种树的学习过程并无特别大的不同，都是分为两步：
- 决策树生成
- 决策树剪枝
1、特征选择方法
- 熵：随机变量X的熵被定义为：
其中p(x)=Pr(X=x)是X的密度函数。熵度量了随机变量X的不确定性程度，如8种均匀可能需要log28=3个字节来存储。
- 联合熵 和 条件熵：
两个随机变量的联合熵被定义为：
条件熵被定义为：
另外可以证明：
- 信息增益(互信息)：互信息是一个随机变量包含另一个随机变量信息量的度量，也是在给定另一随机变量知识的条件下，原随机变量不确定度的缩减量。
注意到互信息(信息增益)关于X和Y是对称的，即H(X)-H(X|Y)=H(Y)-H(Y|X)。而且它与相对熵存在如下等价关系：
但是信息增益倾向于选择取值较多的特征，比如：有10个样本，特征A有10个取值，每个取值有一个样本，这时分支节点的纯度达到最大，相应的信息增益最大，利用信息增益对特征进行选择，结果更可能选择这样的特征A。但这样的特征无法对新样本进行有效的预测。
- 信息增益比：
需要注意的是，增益率对可取值较少的特征有偏好，所以C4.5算法并不是直接选择增益率最大的特征进行划分，而是先从候选属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。
- 基尼指数（Gini impurity）
要注意这里的GINI不纯度(并不是GINI系数)，它可以看作是熵的一种近似：
因为当p(x)趋近于1时有
还有一个优势就是计算简单，不用特殊考虑p(x)=0的情况。在CART树中，属性a的GINI指数定义为：
MSE(适合回归树)
MAE(mean absolute error)
2、决策树生成
对于一颗决策树，我们在生成每个节点时，要自动决策三件事：
- 选择哪个特征用于分枝
- 特征的划分点（用于二叉树）
- 树的拓扑（形状）
在回归树中，令
则每一步是一个最小化问题：
3、决策树剪枝
根据”偏差-方差分解定理“，模型的泛化误差可以分解为偏差、方差和噪声之和。决策树在生成的时候完全照顾到了偏差，所以在剪枝阶段我们要认真考虑模型的偏差。
- 损失函数
损失函数要兼顾预测误差和模型复杂度（节点个数）
设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有N_t个样本点，其中k类的样本点有$N_{tk}$个，H_t(T)为叶结点t上的经验熵，alpha >=0为参数，则决策树学习的损失函数可以定义为：
其中经验熵为
上述讲的是C4.5决策树，对于CART分类树中的任意子树，我们有：
其中C(T)是子树的预测误差，|T|是子树叶结点个数。
CART分类树的剪枝主要考虑三点：
- 1、树的大小|T|，叶子节点个数
- 2、基于训练数据的预测误差
- 3、基于测试数据的预测误差
对于第1和第2点，我们可以自下而上找到一个最优的子节点使得剪枝后损失函数得到最大的改善（有优化的计算方法），此时也对应着一个alpha，然后剪枝得到一颗子树。不断迭代上述过程，理论上会直接结束于原决策树的根结点，但我们又不知道在这个中间怎么去停止，于是便有了第三点。具体方法如下：
