统计学习方法--树模型

树模型

（上思维导图来自知乎：夕小瑶）

决策树算法主要包括决策树的生成与剪枝。

1 决策树生成

决策树可以从两个方面解释

• 看做是if-then规则的集合
• 把特征空间划分成互不相交的单元，每个单元定义一个条件概率分布。

决策树学习的本质是从训练数据集中归纳出一组分类规则，也可以看做是对特征空间划分类的条件概率分布。

首先，按照根据统计学习三要素来分析决策树学习的过程：

假设空间：对特征空间进行划分所有可能的决策树

损失函数：正则化的极大似然函数

优化方法：优化就是要在所有可能的的决策树中选择损失最小的树。在所有可能的决策树选择最优决策树是完全NP问题。所以决策树的学习一般使用启发式的方法近似求解。这样得到的决策树是次最优的。

决策树启发式学习方法：递归的选择最优特征，对特征空间不断的划分，也对应着决策树的构建。决策树的生成只考虑局部最优，决策树的剪枝考虑全局最优。决策树的生成主要有ID3，C4.5和CART算法。主要区别在于最优特征选择方法的不同。

1.1 ID3-信息增益

ID3算法使用信息增益来选择当前的最优特征。信息增益是用来衡量给定特征A后，随机变量熵下降的程度。用经验熵H(D)和给定特征A的条件经验熵H(D|A)之差来表示。
$gain(D,A)=H(D)-H(D|A)\\=H(D)-\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$gain(D,A)=H(D)−H(D∣A)=H(D)−i=1∑n​∣D∣∣Di​∣​H(Di​)
H(D)表示熵，用来衡量随机变量的不确定性。熵越大，不确定性越大。
$H(D)=-\sum_{k=1}^K\frac{|D_k|}{|D|}\mathop{log}\frac{|D_k|}{|D|}$H(D)=−k=1∑K​∣D∣∣Dk​∣​log∣D∣∣Dk​∣​

1.2 C4.5-信息增益比

ID3算法中的使用信息增益选择最优特征存在问题：信息增益倾向于选择取值较多的特征。C4.5算法使用信息增益比来解决这一问题，对特征的取值个数加上惩罚。

信息增益比等于给定特征A的信息增益与样本集关于特征A的熵的比值。
$g_{rate}=\frac{gain(D,A)}{H_A(D)}\\H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\mathop{log}\frac{|D_i|}{|D|}$grate​=HA​(D)gain(D,A)​HA​(D)=−i=1∑n​∣D∣∣Di​∣​log∣D∣∣Di​∣​
特征A的取值越多，样本集关于A的熵就越大。信息增益比就相当于在信息增益对特征取值个数增加了惩罚。

1.3 CART树

CART（classify and regression tree）是用于分类和回归的二叉树。回归树使用均方误差最小化准则，分类树用基尼指数最小化准则。递归的构建决策二叉树。

1.3.1 回归树

回归树使用均方误差。遍历所有的特征，以及该特征的取值作为切分变量和切分点。将划分后各叶节点的均值作为预测值。选择均方误差最小的划分变量和划分点对特征空间进行划分。递归进行以上过程，直到达到停止条件。

1.3.2 分类树

分类树使用基尼指数。
$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk2​
基尼指数表示对随机变量进行两次又放回的采样，这两次拿到的样本不属于同一类的概率。与熵一样，反映了随机变量的混乱程度。

2 决策树剪枝

决策树生成只考虑局部最优。通过不断对特征空间进行划分，来更好的拟合训练数据。这样做很容易过拟合。决策树的剪枝考虑全局最优。通过极小化带正则（代表整棵树的复杂度）的树整体损失对生成的决策树进行剪枝。
$L=\sum_{t=1}^TN_tH(D_t)+a|T|$L=t=1∑T​Nt​H(Dt​)+a∣T∣
其中T表示叶节点的个数。第一项表示树的整体损失（整棵树熵的期望），第二项表示树的复杂度。a是控制两者影响的比例。

根据剪枝时机的不同，可分为预剪枝和后剪枝。

• 预剪枝：在选择最优划分特征后，判断当前划分能否带来整体loss的下降，如不能，则停止迭代。
• 后剪枝：先生成一颗完整的树，然后自底向上判断合并子树能否带来整体的提升。

3 树的集成

树模型大多用于集成学习中，关于树集成的算法参见集成学习部分的介绍。

参考：

[1] 李航，统计学习方法