西瓜书4-决策树

从西瓜书和统计学习方法中学习了决策树的相关知识，同时在网上查找了树的知识点，最重要的是二叉树和树3种的遍历方式

树的知识
决策树
剪枝问题

树

树一种抽象类型数据，用来模拟具有树状结构性质的数据集合。它是由多个有限节点组成一个层次关系的集合。特点：

每个节点有0个或者多个子节点
没有父节点的节点称之为根节点
每个非根节点有且只有一个根节点

术语

节点的度：一个节点含有的子树的个数称为该节点的度
树的度：最大的节点的度称之为数的度
叶节点或终端节点：度为零的节点
父节点：含有子节点的节点上级
子节点：一个节点还有的子树的根节点称为该节点的子节点
兄弟节点：具有相同父节点的节点
节点的层次：根节点为第一层，其子节点为第二层，类推
树的高度或者深度：节点最大层次
堂兄弟节点：父节点在同一层次的节点
森林：由多个树互不相交的树的集合称为森林

二叉树

每个节点最多只有两个子节点：左子树和右子树，性质：

第$i$层上最多$2^{(i-1)}$个节点
深度为$k$的二叉数最多有$2^k-1$个节点
具有$n$个节点的完全二叉树的深度必为$log2(n+1)$
叶结点数为$N_0$，深度为2的节点总数为$N_2$，则$N_0=N_2+1$

树的遍历

深度遍历的三种遍历顺序：

在子节点中，必须先左后右

前序遍历：根—>左—>右
中序遍历：左—>根—>右
后序遍历：左—>右—>根

树的种类

无序树：任意节点的子节点之间没有任何的顺序关系，称之为无序树，也叫自由树
有序树：子节点之间由顺序关系
二叉树：每个节点最多含有两个子树的树
完全二叉树：若一棵树的深度为d，除去第d层外，其他各层的节点数目达到了最大值，且第d层所有节点从左向右连续紧密的排列的二叉树
满二叉树：所有层的节点数达到了最大数
平衡二叉树：当且仅当任何节点之间的两颗子树的高度差不大于1的二叉树
排序二叉树：二叉搜索树，二叉查找树，性质：任何节点左边的数比节点上的数小，右边比节点上的数大
霍夫曼树：用于信息编码
$B$树/$B^+$树：在MySQL的索引中使用

决策树

决策树介绍

决策树是基于树结构进行决策的，其目的是产生一颗泛化能力强，即处理未见示例能力强的决策树，它是一种有监督分类模型

一颗决策树包含：

一个根节点
若干个内部节点
若干个叶节点；叶节点对应于决策结果

决策树学习

决策树学习的本质上是从训练数据集上归纳出一组分类规则，通过训练数据集估计条件概率模型。

决策树学习的损失函数通常是正则化的极大似然函数。

决策树基本算法

决策树的生成是一个递归过程
重点是第8行：最优属性的选择；分支节点所包含的样本尽可能的是属于一个类别，节点的“纯度”要高

ID.3

信息增益

ID.3算法是基于信息增益来选择最优划分属性。信息增益的计算基于信息熵 information entropy（样本集合纯度的指标）。

假设数据集$D$中第$k$类样本占的比例是$p_k(k=1,2,…,K)$，则$D$的信息熵定义为：
$$
Ent(D)=-\sum^K_{k=1} p_klog_2{p_k}
$$
比如：某个事件发生的结果有3种情形，出现的概率分别是：

结果1	结果2	结果3
$\frac{1}{3}$	$\frac{1}{2}$	$\frac{1}{6}$

信息熵的计算如下：

$$Ent=-(\frac{1}{3}log_2\frac{1}{3}+\frac{1}{2}log_2\frac{1}{2}+\frac{1}{6}log_2\frac{1}{6})$$

信息熵越小，数据集$X$的纯度越大

假设数据集中离散属性$a$共有$V$个可能的取值${a^1,…,aV}$。使用属性$a$对整个数据集进行划分，会产生V个分支节点；

第$v$个节点包含数据集合$D$在属性$a$上取值为$a^{v$的样本，记为$D}v$；节点的权重为$\frac{|D^v|}{|D|}$，样本数越多的分支节点，其影响越大

基于属性$a$对数据集的信息增益表示为
$$
Gain(D,a)=Ent(D)-\sum^{V_{v=1}\frac{|D}v|}{|D|}Ent(D^v)
$$
上面的式子：表示的是以属性$a$划分前和划分后的信息熵差值，信息增益越大越好

具体过程

从根节点开始，对所有节点计算所有可能的特征的信息增益
选择信息增益最大的特征作为节点的特征，由特征的不同取值建立子结点
再对子结点调用上述方法，递归地创建决策树（步骤2中使用的属性特征不再重复使用）

缺点

ID3算法的缺点是：偏向于取值较多的属性进行分割

C4.5

介绍

为了解决ID3算法的缺点，引入了C4.5

C4.5使用的是信息增益率作为划分属性的准则，定义为：
$$
GainRatio(D,a)=\frac{Gain(D,a)}{IV(a)}
$$
其中
$$
IV(a)=-\sum^{V_{v=1}\frac{|D}v|}{|D|}log_2\frac{|D^v|}{|D|}
$$
上式中的$IV(a)$称之为属性$a$的“固有值”。属性$a$的可能取值越多，“固有值”越大。

C4.5选择属性的依据

不是选择增益率最大的，可能对数目较少的属性有所偏好
从候选属性中找出信息增益率高于平均水平的属性
步骤2的基础上，选择增益率最高的
使用过后的属性在下次进行划分的时候，不再考虑
如果在某次划分的过程中，有多个属性的信息增益是相同的，任取其中一个。
对于连续值属性，可取值数目不再有限，采用离散化技术（如二分法）进行处理。
1. 将属性值从小到大排序，然后选择中间值作为分割点
2. 数值比它小的点被划分到左子树，数值不小于它的点被分到右子树，计算分割的信息增益率，选择信息增益率最大的属性值进行分割。

CART

基尼系数Gini

CART决策树采用的Gini基尼系数来划分属性。采用的是二元切分法，每次将数据分成两份，分别进入左右两边的子树中。在整个树中

每个非叶子节点都有两个孩子
CART中叶子节点比非叶子节点多1
选取基尼系数作为划分标准，每次迭代都会降低基尼系数。

对于全部数据集$D$的纯度使用基尼系数来度量：
$$
\begin{align}
Gini(D)
& =\sum^{{|Y|}_{k=1}\sum_{k} \neq k}p_kp_{k^} \
& = 1-\sum^{{|Y|}_{k=1}p_k}2
\end{align}
$$
基于某个属性$a$的基尼系数可表示为
$$
Gini(D|a)=\sum ^{V_{v=1}\frac{D}v}{D}Gini(D^v)
$$

Gini系数特点

反应从数据集中随机抽取两个样本，类别标志不一样的概率
基尼系数越小越好，数据的纯度越高
选择使得划分后基尼系数最小的属性作为最优划分属性

实例demo

在demo中主要是讲解如何计算信息熵，信息增益，信息增益率，基尼系数。数据样本取自西瓜书

信息熵

在整个样本中的正反例为8：9，信息熵为：

$$
Ent(D)=-(\frac{8}{17}log_2 \frac{8}{17}+\frac{9}{17}log_2 \frac{9}{17})=0.998
$$

选择以属性“色泽seze”为例，有青绿、乌黑、浅白3种取值方案$D_1,D_2,D_3$，分别占比为6：6：5，每个子集数据中占比为（3：3）：（4：2）：（1：4），那么3个子节点的信息熵分别为：

$$
Ent(D_1)=-(\frac{3}{6}log_2\frac{3}{6}+\frac{3}{6}log_2\frac{3}{6})=1.000
$$

$$
Ent(D_2)=-(\frac{4}{6}log_2\frac{4}{6}+\frac{2}{6}log_2\frac{2}{6})=0.918
$$

$$
Ent(D_1)=-(\frac{1}{5}log_2\frac{1}{5}+\frac{4}{5}log_2\frac{4}{5})=0.722
$$

信息增益

根据上面的计算，得到基于色泽属性的信息增益为
$$
\begin{align}
Gain(D,seze)
& =Ent(D)-Ent(D)-\sum^{3_{v=1}\frac{|D}v|}{|D|}Ent(D^v) \
& = 0.998-\frac{6}{17}*1.00+\frac{6}{17}*0.918+\frac{5}{17}*0.722 \
& = 0.109
\end{align}
$$
同理，可以得到基于其他属性的信息增益，不再累述。

信息增益率

还是以上面的色泽属性为例，基于色泽属性的信息增益已经计算出来：
$$
Gain(D,seze)=0.109
$$

属性色泽中有3种结果，对应比例为6：6：5，固有值$IV(a)$为
$$
\begin{align}
IV(a)
& =-\sum^{V_{v=1}\frac{|D}v|}{|D|}log_2\frac{|D^v|}{|D|} \
& = -(\frac{6}{17}log_2 \frac{6}{17}+\frac{6}{17}log_2 \frac{6}{17}+\frac{5}{17}log_2 \frac{5}{17}) \
& = 1.580

\end{align}
$$
那么，基于属性色泽的基尼系数为
$$
Gain_ratio=\frac{0.109}{1.580}
$$

几种常见算法比较

决策树算法	算法描述
ID3	在各级节点上，使用信息增益作为属性的选择标准只适用于离散的描述属性依赖于选择特征数目较多的属性特征单变量决策树，特征之间的关系不会考虑
C4.5	使用的是信息增益率作为属性的选择标准可以同时处理离散和连续的属性描述
CART	使用的是基尼系数作为属性的选择标准非参数的分类和回归算法构建的一定是二叉树终节点是连续变量，属于回归树终节点是离散变量，属于分类树

剪枝处理

剪枝由来

剪枝pruning主要是为了处理决策树中的过拟合问题。在决策树中

为了尽可能正确分类训练样本，结点划分过程不断重复，造成树的分支过多
每个属性都被详细地加以考虑，决策树的树叶节点所覆盖的训练样本都是“纯”的
从而使得训练样本学的太好了，把训练集的某些特点当做所有数据的一般性质，但是对于测试集中的数据表现并没有那么好，从而造成了过拟合overfitting

剪枝算法

CART剪枝算法分为两步：

从算法生成的决策树$T_0$底端开始不断地进行剪枝，直到根节点，形成一个子树序列${T_0,T_1,…,T_n}$
通过交叉验证法在独立地验证数据集上对上面的子树序列进行测试，选出最优子树

剪枝分类

预剪枝-preprunning

预剪枝就是及早地停止树的增长，在决策树生长的过程就进行剪枝操作。

常见的做法是设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支，终止树的增长。实际效果并不好。

特点

在决策树生成的过程中，对每个节点划分前先进行预估
如果当前节点的划分不能提高泛化能力，停止划分
直接将当前节点划分叶子节点

通过西瓜书的例子来讲解

采用留出法，将数据分成训练集和验证集（通过双横线区分）

这是没有经过任何剪枝得到的决策树（采用的是信息增益准则）

由于是预剪枝，需要判断这个划分是否进行，即：是否提高泛化能力。

划分前：把该节点标记为叶节点，其类别标记为训练样例数最多的类型（例子中有两个：是和否都是5个），假设我们标记为好瓜，选择“是”。

用表中的验证集进行评估，{4,5,8}被正确分类，那么不进行划分的正确率是$\frac{3}{7}=42.9%$

划分后：针对上面的训练集数据，计算出所有特征的信息增益，具体过程如下：

从计算结果中，可以看出来色泽和脐部的信息增益值是最大的，从中任意选择一个脐部当做根节点，会产生3个分支（因为脐部有3个不同的属性：凹陷，稍凹，平坦）：

当使用脐部属性划分之后，下面的234号节点中包含的编号分别为{1,2,3,14}，{6,7,15,17}，{10,16}，分别被标记成“好瓜”，“好瓜”，“坏瓜”，验证集中{4,5,8,11,12}被正确分类，正确率是$\frac{5}{7}=71.4%$。

于是采用脐部属性进行划分。

后剪枝-postprunning

剪枝过程

先生成一颗完整的决策树
从下往上对非叶节点进行考察：如果将该节点对应的子树替换为叶节点能够提高泛化性能，则替换为叶节点
叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识

上面的栗子中，不进行划分的验证集精度为$42.9%$。

后剪枝首先考虑的是节点6，将节点6替换为叶子节点，替换后的节点包含{7,15}的训练样本，因为在属性纹理的区分之下，他们俩个被正确分类。于是将该节点的类别标记为“好瓜”（正负样本数量相同，随便标记）。验证集的精提高至$57.1%$，实施剪枝策略。