周志华西瓜书学习笔记（三）

决策树是一种基本的分类方法，根据数据的各种属性分类，如图就是一个决策树。

先介绍决策树中的概念：

根节点：就是树的最顶端，最开始的那个节点。在图中，“天气”就是一个根节点；

内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”

叶节点：就是树最底部的节点，也就是决策结果。

节点之间存在父子关系。比如根节点会有子节点，子节点会有自己的子子节点，但是到了叶节点就停止了，叶节点不存在子节点。

在这里插入图片描述

决策树通常有三个步骤：特征选择、决策树的生成、决策树的修剪。在特征选择中，我们其实有很多选择可以作为分类的依据，但问题是如何选取最好的那个值作为我们分类的依据。

ID3决策树

ID3决策树学习算法就是以信息增益为准则来选择划分属性，接下来先引出信息增益的定义：

信息熵：信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为 $p_k$ ，则D的信息熵定义为：

? $-\sum_{k=1}^{|y|}p_k·log_2p_k$

? 显然Ent(D)的值越小，则D的纯度越高。当所有样本都只属于某一类，样本中没有其他类别的数据时，此时信息熵最小；相反如果样本中的数据平均归属于每一类别，所有类别占的比例都相同时，此时信息熵最大。

信息增益：使用某种属性a来进行划分时所获得的的“纯度提升”

? $\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$

? $E n t (D)$ 是使用属性a进行分类之前的信息熵， $\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$ 是分类之后每一个子节点上的信息熵，按照子节点中分到的样本个数占父节点个数的比值进行加权汇总后得到的信息熵，二者的差就是信息增益。
构建方法：在所有的属性中，逐一作为分类标准，计算出各个属性的信息增益，选择有最大信息增益的属性作为分类标准。

不足ID3的信息增益准则对可取数值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，提出C4.5决策树

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}$ 。计算的是信息增益占属性a信息熵的比重，可以类似为“优化率”。
缺点：增益率准则对可取值数目较少的属性有所偏好。

因此C4.5的构造方法不是直接选择增益率最大的候选划分属性，而是先从划分属性中选出信息增益高于平均水平的属性，在从中选择增益率最高的。

CART决策树

基尼系数： $\sum_{k=1}^{|y|} \sum_{k'≠k}p_kp_k' = 1-\sum_{k=1}^{|y|}p_k^2$ ;

$Gini_index(D,a) = \sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$ 。属性a的基尼系数也可以根据下属子节点分类数量占总量的权重加权
构造方法：在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

剪枝处理

决策树很可能出现一个问题就是过拟合，而剪枝是决策树学习算法对付“过拟合”的主要手段。

决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(post-pruning)。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成-棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

连续值与缺失值

对连续值的情况，给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为 ${a^1,a^2...,a^n}$ 。基于划分点t可将D分为子集 $D_t^-$ 和 $D_t^+$ ，其中 $D_t^-$ 包含那些在属性a上取值不大于t的样本,而 $D_t^+$ 则包含那些在属性a上取值大于t的样本.显然，对相邻的属性取值 $a^i$ 与 $a^{i+1}$ 来说, t在区间[ $a^i$ ， $a^{i+1}$ )中取任意值所产生的划分结果相同。因此，对连续属性a，我们可考察包含n- 1个元素的候选划分点集合： $T_a = \{\frac{a^i+a^{i+1}}{2}|1≤i≤n-1\}$ 。然后就可以像考察离散属性值一样考察划分点。
对缺失值的情况，只需要将信息不缺失的数据先单独编成一个集合D’，将这个集合先分类，然后再将缺失的数据分配到每一个叶节点中，但是需要修改这些数据的权重。