第5章 决策树

决策树（decision tree）是一种基本的分类和回归方法，它可以任务是if-then规则（互斥且完备）的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题，得到的决策树是sub-optimal的。
决策树的生成对应于模型的局部选择局部最优，决策树的剪枝对应于模型的全局选择全局最优。

1. 特征选择

特征现在在于选取对训练数据具有分类能力的特征，通常特征选择的准则是信息增益或信息增益比。
熵
熵（entropy）是表示随机变量不确定性的度量：$H(X)=-\sum_i^N{p_i\log{p_i}},\ 0\le{H(p)\le\log{n}}$
条件熵（conditional entropy）表示在已知随机变量X的条件下随机变量Y的不确定性：$H(Y|X)=\sum_i^N{p_iH(Y|X=x_i)}$

信息增益（Information gain）表示得知特征X的信息而使得类Y的信息的确定性减少的程度：
$g(D,A)=H(D)-H(D|A)$
上式中$H(D)[empirical\ entropy]$表示对数据集D进行分类的不确定性，$H(D|A)[empirical\ comditional\ entropy]$表示在特征A给定的条件下对数据集D进行分类的不确定性。一般地，熵与条件熵的差称为互信息（mutual Information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益比（Information gain ratio）信息增益存在偏向于选择取值较多的特征，ratio可以避免此问题。
$g_R(D,A)=\frac{g(D,A)}{H_A(D)},\ H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|},\ n是特征A的取值个数$

2. 决策树的生成

ID3：核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。ID3相当于用极大似然法进行概率模型的选择。C4.5：改进ID3，并使用信息增益比。

3. 决策树的剪枝（pruning）

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。
设树$T$的叶结点个数为$|T|$，$t$是树$T$的叶结点，该结点有$N_t$个样本点，其中$k$类样本点有$N_{tk}$个，则决策树学习的损失函数可以定义为：
$C_\alpha(T)=\sum_t^{|T|}N_tH_t(T)+\alpha|T|=C(T)+\alpha|T|\ H_t(T)=-\sum_k\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}\C(T)=\sum_t^{|T|}{N_tH_t(T)=-\sum_t^{|T|}\sum_k^K{N_{tk}}\log\frac{N_{tk}}{N_t}}$
$C(T)$表示模型对训练数据的预测误差（模型与训练数据的拟合程度），$|T|$表示模型复杂度，$\alpha\ge0$控制两者间的影响。较大的$\alpha$促使选择较简单的模型，较小的$\alpha$促使选择较复杂的模型，$\alpha=0$意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。剪枝就是当$\alpha$确定时，选择损失函数最小的模型。损失函数的极小化等价于正则化的极大似然估计。

输入：生成算法产生的整个树$T$，参数$\alpha$
输出：修剪后的子树$T_{\alpha}$
1-计算每个结点的经验熵
2-递归地从树的叶结点向上回缩
3-根据回缩前B后A损失函数值$C_{\alpha}(T_A)\le C_{\alpha}(T_B)$，剪掉后损失减少则剪枝（重复）

4. CART算法

分类与回归树（CART）是在给定输入随机变量X条件下输出随机变量Y的条件概率分布。（左是右否的二叉树）

生成：基于训练数据集生成决策树，生成的树要尽量大。
剪枝：用验证集对已生成的树进行剪枝并选择最优子树，用损失函数最小作为剪枝的标准。

CART生成
回归树：平方误差最小化准则
分类树：基尼指数最小化准则

最小二乘回归树生成算法
输入： 训练数据集$D$
输出： 回归树$f(x)$
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉树：1-选择最优切分变量$j$与切分点$s$，求解$\min_{j,s}[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$遍历变量$j$对固定的切分变量$j$扫描切分点$s$选择使式达到最小值的对$(j,s)$。2-用选定的$(j,s)$划分区域并决定相应的输出值$R_1(j,s)={x|x^{(j)}\le s},\ \ R_2(j,s)={x|x^{(j)}\gt s},\ \ \hat{c}m=\frac{1}{N_m}\sum{x_i\in R_m(j,s)}y_i,x\in R_m$。3-重复1、2。4-将输入空间划分为$M$个区域$R_1,R_2,\cdots,R_M$生成决策树：$f(x)=\sum_m^M\hat{c}_mI(x\in R_m)$

基尼指数分类树生成算法
输入： 训练数据集$D$，停止计算的条件
输出： CART决策树
从根结点开始构建二叉树：1-设结点的训练数据集为$D$，计算现有特征对数据集的基尼指数$Gini(D)$。 根据特征$A=a$将数据集分成$D_1$和$D_2$计算基尼指数$Gini(D,A)$。2-在所有特征与切分点对$<A,a>$中选择基尼指数最小的作为最优特征与最优切分点，由此生成两个子结点。3-重复1，2，直到满足停止条件。4-生成CART树。

基尼指数：$K$类中样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数为：$Gini(p)=\sum_k^K{p_k(1-p_k)}=1-\sum_k^K{p_k^2}$。对于给定样本集合$D$，基尼指数为$Gini(D)=1-\sum_k^K(\frac{|C_k|}{|D|})^2$，对于在特征$A$条件下的集合$D$的基尼指数为$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$。基尼指数越大，样本集合的不确定性也越大（与熵类似）。
排列组合：排列$A_n^m=\frac{n!}{(n-m)!}$， 组合$C_n^m=\pmatrix{\begin{matrix}n\m\end{matrix}}=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}=C(n,m)=C(n,n-m)$
二项式定理：$(a+b)^n=\sum_i^nC_n^i a^{n-i}b^i$，$C_n^i$杨辉三角
伯努利分布：关于布尔变量$x\in{0,1}$的概率分布，其连续参数$p\in[0,1]$表示变量$x=1$的概率：$p(x)=p^x(1-p)^{1-x},E(x)=p,\sigma=p(1-p)$
二项分布：1-实验次数固定为$n$；2-每次事件只有两种可能；3-每次成功的概率固定为$p$；4-表示成功$x$次的概率：$p(x)=C_n^x p^x(1-p)^{n-x},E(x)=np,\sigma=\sqrt{np(1-p)}$
几何分布：0-与二项分类相似，唯一不同在于4-表示进行$x$次尝试，取得第一次成功的概率：$p(x)=(1-p)^{x-1}p,E(x)=1/p,\sigma=(1-p)/p^2$
``泊松分布：`1-事件独立；2-在任意相同的时间范围内，事件发生的概率相同；3-在某个时间范围内，发生某件事情$x$的概率：$p(x)=\frac{u^xe^{-u}}{x!},E(x)=\sigma=u\ [p=\frac{u}{n},p(x)=\lim_{n\rightarrow\infty}\pmatrix{\begin{matrix}n\m\end{matrix}}p^x(1-p)^{n-x}]即在p上的极限$

伯努利扔一次硬币；二项分布是多次伯努利；泊松分布是p很小的二项，即无数次扔硬币且正面概率极小；正态分布是n很大的二项，即无数次扔硬币且硬币完全相同。

CART剪枝

输入： CART算法完全生成的决策树$T_0$
输出： 最优决策树$T_\alpha$
1-设$k=0,T=T_0,\alpha=+\infty$
2-自下而上地对各内部结点$t$计算$C(T_t)$，$|T_t|$以及$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1},\alpha=\min(\alpha,g(t))$。以$|T_t|$为叶结点个数$t$为根节点的子树$T_t$，对训练数据的预测误差$C(T_t)$。
3-对$g(t)=\alpha$的内部结点$t$进行剪枝，并对叶结点以多数表决法决定其类，得到树$T$。
4-设$k=k+1,T_k=T,\alpha_k=\alpha$
5-如果$T_k$不是由根节点及两个叶结点构成的树，则回到1-$\alpha=+\infty$；否则令$T_k=T_n$
6-采用交叉验证法在子树序列$T_0,T_1,\cdots,T_n$中选取最优子树$T_{\alpha}$。