第4章 决策树

西瓜书 机器学习

---

1.几个概念

信息熵

当前样本集合D中第K类样本所占的比例为$p_k$,k=1,2,3...,N，信息熵表示成：

$$Ent(D)=-\sum_{k=1}^{N}p_klog_{2}p_k$$
信息熵越小，表示样本集合的纯度越高（即样本的混杂度越低，越不需要更多的划分）

信息增益

利用属性a对样本集D进行划分前后的信息熵之差，叫做信息增益，表示如下：

$$Gain(D, a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$$
其中，V是属性a取值的个数，利用a对样本集进行划分，产生V个分支结点。第v个分支结点包含了所有取值为$a^v$的样本，记作$D^v$。不同的分支包含的样本数不同，分支结点的权重用样本所占的比例表示。
信息增益的意义在于：描述使用某一属性来划分所获得的“纯度的提升”，信息增益越大，纯度提升越高。
ID3决策树算法，以信息增益为准则选取划分属性。但其对取值数目较多的属性有锁偏好，容易造成同一深度，树的分支很多，决策树的泛华能力弱。

增益率

C4.5决策树算法采用增益率来选取最优划分的属性。基本思想：从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。

$$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$
$$IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$$
其中IV(a)是属性a的intrinsic value固有值，取值数目越多，固有值越大。因此增益率准则对可取值数目较少的属性有所偏好。

基尼指数

CART树使用“基尼指数”选择最优划分属性。

$$Gini(D)=1-\sum_{k=1}^{N}{p^2_k}$$
基尼值反映了从数据集D中随机抽取两个样本，类别标记不一致的概率。Gini越小，纯度越高。
基尼指数定义如下：
$$Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$

2.剪枝

作用：防止“过拟合”
“剪”的判决：剪枝后能否对模型性能进行提升。

方法：

• 预剪枝（生成过程中，可能会造成欠拟合）；
• 后剪枝（生成后，自底向上，泛化能力优于预剪枝，但时间开销大）

3.连续与缺失值处理

连续值处理

策略：二分法对连续属性进行划分，划分阈值取属性所有取值从小到达排列后两两的均值。
特点：当前结点划分属性为连续型，该属性仍可作为后代结点的划分属性，划分阈值可变。

缺失值处理

现实数据中，经常能碰到缺失值，遇到这类情况，一般的做法是进行缺失值的填充（用均值、0、1，或者对缺失属性根据未缺失的样本构建一个预测模型，对缺失值进行预测）。
在决策树算法中，可以不对这些缺失值进行填充处理，但需要解决如下问题：

• 有缺失值的情况下，如何选择最优划分属性？
• 给定划分属性，样本在属性上值缺失，如何对样本进行划分？

针对问题1，可仅利用未缺失该属性值的样本计算信息增益，判断属性的优劣；
针对问题2，将有缺失值的样本划入所有的子结点，样本权重调整为各个子结点样本集样本数占父结点的比例。

C4.5决策树算法利用了以上方案。因此，如果分类模型是C4.5，可以不对缺失值进行填充处理。

4.多变量决策树

把每个属性看做坐标空间的一个坐标轴，d个属性描述的样本对应着d维空间的一个点，而分类就是在坐标空间中找不同样本的分类边界。

上图决策树的分类边界每一段都与坐标轴平行，使得结果有好的可解释性。
如果样本的属性很多，此时的分类边界不再是简单的平行坐标轴的平面。

在多变量决策树中，非叶节点不再是某个属性，而是属性的线性组合，学习的过程是建立一个合适的线性分类器。

总结：对书中的西瓜例子求解信息增益的过程跟着算了一遍，比较容易弄懂决策树学习的过程。虽然平时因为有sklearn和其他的包，封装了决策树的学习过程，也不会实际去求解，但对原理的理解还是很有用的。特别是后面缺失值的处理，才知道决策树是可以有含有缺失值的样本。