决策树cart

引：决策树是一种基本的分类和回归算法，思想非常简单，给出一个总体衡量复杂度的公式，然后在使用贪心算法，用局部最优来近似总体最优，并设置终止条件，最后通过剪枝避免过拟合。优点是模型具有可读性，分类速度快(二叉树)。

基本概念

熵(entropy)和基尼指数(Gini index)都是表示随机变量不确定性的度量（针对离散情况，因此是用于分类问题的度量）

熵(entropy)

设X是一个取有限个值的离散随机变量，其概率分布为

$p(X=x_i)=p_i$,i=1,2, … ,n

随机变量X的熵定义为：
H(X)=$-{\sum }_{i=1}^n{p}_{i}log(p_i)$（以e或2为底）

熵越大，随机变量的不确定性越大

当$p_i$趋近于0和趋近于1时,$p_{i}log(p_i)$趋近于0，说明这一项不能给变量增加不确定性，从定义可证
0$\le$ H(x) $\le$ logn (取$p_i=\frac{1}{n}$,$-{\sum }_{i=1}^{n}1/nlog(1/n)=logn$)

设有随机变量(X,Y),其联合概率分布为

$p(X=x_i，Y=y_i)=p_{ij}$, i=1,2, … ,n； j=1,2, … ,m

条件熵

H(Y|X)=${\sum }_{i=1}^n{p}_{i}H(Y|X=x_i)$（以e或2为底）

这里$p(X=x_i)=p_i=p(X=x_i)$

表示已知随机变量X的条件下随机变量Y的不确定性，准确定义为X给定条件下Y的条件概率分布的熵对X的数学期望

为什么要定义熵和条件熵？

在现实中，如果两个随机变量X和Y是相关的，即不独立的，那么从直观上，我们可以从其中一个随机变量的信息中或多或少的得到另一个随机变量的信息。知道的信息越多，相对的变量的不确定性也会降低。为了衡量我们知道信息的多少，我们需要熵的定义

另一方面，为了衡量我们可以从相关的变量的信息中得到我们关心的变量的信息多少，我们需要条件熵的定义，并且能够符合给定特征不确定性减少的性质，详细见下面的描述

信息增益(information gain)
表示得知特征X的信息而使得类Y的信息的不确定性减少的程度，就是训练数据中经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

g(D,A)=H(D)$-$H(D|A)

这里“经验”二字是指根据数据估计出来的，而理论上的熵与条件熵信息之差称为互信息(mutual information)

这里信息增益$\ge 0$,为什么？

详细证明点这里

有了信息增益$\ge 0$的保证后，于是我们可以比较特征告诉我们的信息多少，选择信息增益最大的特征

信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，于是我们可以使用信息增益比对这一问题进行校正（information gain ratio）
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

$H_A(D)=-{\sum }_{i=1}^n\frac{D_i}{D}lo{g}_2\frac{D_i}{D}$,n是特征A的个数
D和Di分别是训练集个数以及每个特征中的训练集个数

基尼指数(Gini index)

假设有K个类，样本点属于第k类的概率为$p_k$,则概率分布的基尼指数定义为

$Gini(p)={\sum }_{k=1}^K{p}_k(1-p_k)=1-{\sum }_{k=1}^K{p}_k^2$

基尼指数有着与熵类似的性质，并且给定特征条件下，集合的基尼指数定义为
$Gini(D,A)=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2)$

基尼指数同样表示集合D的不确定性，基尼指数越大，样本集合的不确定性也就越大

example

我们看下如何计算熵和信息增益

下面我们试着计算年龄特征对心脏病分类的信息增益

第三个等式计算的是心脏病分布的熵 ---- H(D)
第一和第二两个等式计算的是给定年龄区间下心脏病分布的熵 ----- H(D|Ai）
于是信息增益由第四个等式可得

于是我们可以遍历age，对给定的age，计算对应的信息增益，然后得到令信息增益最大的age值作为split

如上右图，age的split应该在age=55附近可以使信息增益最大
同理我们也可以得到用Gini index得到的最佳split

决策的可能个数

假如一个特征总共4种spilt(分类总数),那么一步能产生多少种distinct spilt(决策)？
答案是7种，如下图所示，分别是左右结点，对称为同一种决策

因此，如果所有特征的spilt总共有M个，则一步可以有$2^{M-1}-1$种决策

CART

CART分为回归树和分类树，承接上文，从分类树说起

分类树

CART一般选用的是Gini指数
我们已经知道怎么从根结点开始进行分类了，即对每一种特征计算最大信息增益的split，然后选择对应变量的split。因此，对子节点，我们只需要对子节点的数据做同样的步骤，直到终止条件。终止条件一般为子节点上数据个数小于阈值。
可见，决策树是一种贪心算法，每一步都是在求局部最优

我们可以得到原始的决策树T0

剪枝

剪枝是为了避免数据出现过拟合的情况，对生成的决策树进行内部结点删除

怎么剪？

这里我们需要权衡树的大小和准确率，如果我们让树生长旺盛，虽然在训练集上分类准确率高，但是由于可能过于符合训练数据的特点，导致在实际效果中表现不佳。而如果树太小，想必分类效果也不会好。

因此我们需要损失函数

$C_{\alpha }(T)=C(T)+\alpha |T|$
$C(T)$ 是misclassification rate（可以是Gini指数，反正是凸$\cap$函数），|T|是叶节点个数，$\alpha \ge 0$是参数，对固定的$\alpha$,我们要控制损失函数最小,那么我们要适当减小叶节点个数，但是misclassification rate不能太大，剪枝能减少叶节点个数，但也会使$C(T)$增大。

保留哪些结点？

从根结点开始，我们可以得到每一个内部结点进行split前后的misclassification rate，记为$C(t)$和$C(T_t)$，并且$C(t)$>$C(T_t)$（前面有提）。

那么从叶节点往上递归，我们可以计算$C(t)-C(T_t)$，若小于$\alpha$，则剪枝可使损失函数减少，于是叶节点往上的内部结点变成叶节点，直到没有能使损失函数减小的结点

一个快捷的方法是，Breiman等人证明，可以用递归的方法进行剪枝，依据是序列中的最优子树是嵌套的，详见《统计学习方法》p86

输入：CART算法生成的决策树T0
输出：最优决策树Tα
（1）设k=0,T=T0
（2）设α=+∞
（3）自下而上地对各个内部结点t计算C(Tt)，|Tt|以及

$g(t)=\frac{C(t)-C(T_t)}{\mid T_t\mid -1}$

$\alpha =min(\alpha ,g(t))$
α=min(α,α(t))
这里，Tt表示t为根结点的子树，C(Tt)是对训练数据的预测误差，|Tt|是Tt的叶结点个数。
（4）对α(t)=α的内部结点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T。
（5）设k=k+1,${\alpha }_k=\alpha$,$T_k=T$。
（6）如果Tk不是由根结点及两个叶结点构成的树，则回到步骤3；否则令Tk=Tn。
（7）采用交叉验证法在子树序列T0,T1,…,Tn中选取最优子树Tα

回归树

回归树是针对连续变量的预测，因此，最小均方误差代替Gini指数成为损失函数，分类树预测的估计值是叶节点中种类最多的，而回归树的估计值是叶节点上我们关心的响应变量的平均值