决策树

1. 基本流程

决策树是基于树的结构来进行决策的，例如例如我们要对“这是好瓜吗”这样的问题来进行决策，通常会进行一系列的判断：我们先看“它是什么颜色?”，如果是“青绿色”，则我们再看“它的根蒂是什么形态?”，如果是“蜷缩”，我们再判断“它敲起来是什么声音?”，最后，我们得出最终决策：这是个好瓜。这个决策过程如下图所示：

从根结点到每个叶结点的路径对应了一个判定测试序

决策树学习的基本流程如下：

2. 划分选择

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高.

2.1 信息增益

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

则D的信息熵定义为：

其中

表示一共有多少类

Ent(D)的值越小，则D的纯度越高

一般而言，信息增益越大，意味着使用属性a来划分所获得的“纯度提升”越大，因此，可用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益来进行属性划分的。

以如下图为例：

显然

=2.在决策树学习开始时，根节点包含D中所有的样本，其中正例p1=8/17，反例p2=9/17，可计算出根节点的信息熵为：

然后，我们需要计算各个属性的信息增益，以属性”色泽“为例，它有”青绿“，”乌黑“，”浅白“，可按此分为3个子集，色泽为”青绿“的D1包含编号1，4, 6, 10, 13, 17，其中正例p1=3/6，反例p2=3/6；

色泽为”乌黑“的D2包含编号2，3，7，8，9，15，其中正例p1=4/6，反例p2=2/6；D3包含编号5，11，12，14，16，其中正例p1=1/5，反例p2=4/5.

可计算出用”色泽“划分所得到的3个分支结点的信息熵为：

于是，可以计算出属性”色泽“的信息增益为：

类似，可计算出其他属性的信息增益：

显然，属性”纹理“的信息增益最大，于是它被选做了划分属性，之后的操作类似与上面就不在阐述。

2.2 增益率

略过

2.3 基尼指数

CART决策树使用基尼指数来选择划分属性。数据D的纯度可用基尼值来度量：

Gin i(P )反映了从数据集D 中随机抽取两个样本，其类别标记不一致的概率.因此,Gini(D)越小，则数据集D 的纯度越高.

属性a的基尼指数定义为：

因此我们在选择属性时，因选择使得基尼指数最小的属性作为最优划分属性

可参考b站视频https://www.bilibili.com/video/BV1T7411b7DG

进行更好理解

3. 剪枝处理

剪枝是决策树应对过拟合的手段，有时决策树分支过多，这时就可能把一些训练集自身的特点当作所有数据都具备的一般性质而导致过拟合。

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

可参考b站视频https://www.bilibili.com/video/BV1KL4y157uJ

4. 缺失值处理

在属性数目较多的情况下，往往会有大量样本出现缺失值.如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费。因此，有必要考虑利用有缺失属性值的训练样例来进行学习.

基于上述定义，我们可用将信息增益推广为