决策树（design tree）是一种基本的分类与回归方法。 是if-then规则的集合或者定义在特征空间与类空间上的条件概率分布。
决策树模型与学习
决策树模型
if-then规则
由决策树的根结点到叶结点的每一条路径构建一条规则，路径上内部结点的特征对应规则的条件，叶结点的类对应规则的结论。
规则集合互斥且完备。
条件概率分布
决策树还表示给定特征条件下类的条件率分布，将特征空间划分为互不相交的单元，在每个单元定义一个类的概率分布。决策树表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。当某个单元的条件概率$P(Y=+1|X=c)>0.5$时，则归为正类。
决策树学习
本质上是从训练集归纳出分类规则——得到与训练集矛盾较小的决策树 或 由训练集估计条件概率模型。
选取最优决策树是NP完全问题，通常采用启发式方法近似求解。
特征选择
选取对训练数据具有分类能力的特征，特征选择的准则是信息增益or信息增益比。
信息增益
熵表示随机变量不确定性的度量：
条件熵$H(Y|X)$表示在已知随机变量X的条件下随机变量Y的不确定性：
信息增益表示得知特征X的信息使得Y的信息不确定性减少的程度——等价于训练集类与特征的互信息：
特征选择时计算每个特征的信息增益，选择最大的特征。
信息增益比
使用信息增益可能会偏向选择取值较多的特征。
决策树生成
ID3
在决策树各个结点上以信息增益为准则
ID3算法只有树的生成，没有剪枝，容易过拟合。
C4.5
C4.5与ID3算法相似，但用信息增益比来选择特征
决策树剪枝
从已生成的树熵裁掉一些子树/叶结点，回退到其根节点/父节点，简化分类树模型，避免过拟合。
剪枝通过极小化决策树损失函数实现，树T的叶结点个数为$|T|$，$t$是树$T$的叶结点，该叶节点上由$N_t$个样本点，其中k类点有$N_{tk}$个，$H_t(T)$为叶结点$t$的经验熵，$\alpha \ge 0$为参数，则损失函数为
剪枝即在$\alpha$确定时选择损失函数最小的模型——子树越大，训练集拟合效果越好，但复杂度也更高，损失函数是对两者的平衡。
剪枝算法
输入：生成算法产生的整个树$T$，参数$\alpha$
输出：修剪后的子树$T_a$
- 计算每个结点的经验熵
- 递归地从叶结点向上回缩
- 计算损失函数，变小则剪枝
CART算法
决策树生成是递归构建二叉决策树的过程。
CART生成
回归树
用平方误差最小化准则进行特征选择
分类树
分类树用基尼指数最小化准则进行特征选择。
基尼指数：分类问题中，有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼系数为$Gini(p) = \sum_{k=1}^Kp_k(1-p_k) = 1 - \sum_{k=1}^Kp_k^2$
K=2时，$Gini(p)=2p(1-p)$
如果样本集合D根据特征A是否取某一可能值a进行分割，即
则在特征A的条件下，集合D的基尼指数定义为：
$Gini(D)$表示集合D的不确定性，$Gini(D,A)$表示$A=a$分割后集合D的不确定性，基尼指数和熵的一半很接近。
CART剪枝
从生成算法产生的决策树$T_0$底端开始不断剪枝，直到根节点，形成一个子树序列${T_0,T_1,\cdots,T_n}$
从$T_0$开始剪枝，对其中每一内部结点，计算$g(t)=\frac {C(t)-C(T_t)} {|T_t|-1}$，表示剪枝后损失函数减小的程度（负数），将最小的$g(t)$对应的$T_t$减去，得到子树$T_1$，并置$\alpha_1=g(t)$，该子树就是$[\alpha_1,\alpha_2)$上的最优子树
交叉验证选择最优子树
