220127_机器学习_决策树_入门

本文为决策树的入门自学笔记，主要参考了手头的学习资料，

还包括周志华老师的经典教材西瓜书、李航老师的《统计学习方法》。

个人觉得，两本书都是有的地方晦涩有的地方通俗，两者各有所长，可以综合学习。

仅为总结备忘之用，高手勿喷，侵权可删。

欢迎交流。

• 220127_机器学习_决策树_入门
  • 适用问题
  • 决策树的基本思路
  • 最优划分属性
    • 混杂度
      • 信息熵
      • 基尼指数(Gini)
    • 信息增益
  • 剪枝(pruning)
    • 预剪枝(prepruning)
    • 后剪枝(postpruning)
    • 剪枝之后的标签设定
  • 连续值的处理
  • 缺失值的处理

适用问题

适用决策树学习的经典目标问题：

• 带有非数值特征的分类问题；
• 离散特征；
• 属性之间没有相似度概念；
• 特征无序。

决策树的基本思路

决策树的基本思路是很自然的在模拟人做决策时的处理机制：

以二分问题为主，在面临一个问题要决策其“是”或“不是”时，会进行一系列 子决策。
例如，判断今天出门运动吗？
子决策1：今天有课吗？如果有课，不去；如果没课，进入子决策2
子决策2：今天天气如何？如果下雨，不去；如果阴天，去；如果，晴天，进入子决策3；
子决策3：今天温度如何？如果高温，不去；如果不高温，进入子决策4
……………………

这样的决策树由根节点、内部节点、叶节点构成。

• 叶节点：决策的结果，其他节点则对应一个属性的测试。
• 根节点：包含样本的全集的属性测试。
• 内部节点：非样本全集的属性测试。

西瓜书中，决策树学习的基本算法如下
(这里写的是定义TreeGenerate(D,A)函数，作用是拿到一个数据集含有样本，对应的属性集是A，生成其对应的叶节点与内部节点。对于内部节点，需要自己调用自己，继续生成该内部节点下的叶节点与内部节点，表现为一个递归算法。TreeGenerate函数可以生成一个决策树)：

伪代码line2-line4、line5-line7、line11-line12是递归出口。
line2-line4：（输出一致）当前样本已经属于同一类了，不需要接着划分。标记叶节点为C类节点。
line5-line7：（输入一致）属性集的数据都已被用为节点，无法分类。标记叶节点，规定为D中样本多的类。
　?　? 　? 或 属性集中还有未用属性但是这里的样本在未用属性上取值一样，无法分类。标记叶节点，规定为D中样本多的类。
line11-line12：当前属性分类下已经没有样本了，无法分类。标记叶节点，规定为D中样本多的类。

注意：line5-line7、line11-line12的本质是不同的。
　?　? 　前者是在本节点中的样本中取众数，是后验的；后者是在父节点中取众数，是先验的。

算法中涉及到了最优划分属性，参考之后的“信息熵”内容。

在构建决策树的时候，满足训练集的决策树可能有许多个，也可能没有（样本数据错误、特征不全面等原因）。我们要做的是找到一个“矛盾最小”的决策树。这是一种局部最优（因为树的判断流程没有回溯，只向下，每次生成树只考虑本层的信息熵增益，即使本层信息熵增益最大，但是几层一起的信息熵增益就未必了）。

还要求决策树拥有很好的泛化能力。在训练集上得到的树通常队训练集的拟合很好，但在测试集上表现平平，这就是通常会产生的过拟合的情况，这种情况需要进行“剪枝”操作。这需要我们考虑全局的最优性。

那么从上面的描述来看，需要解决的问题有这么几个：最优划分属性是什么？怎么生成最好的决策树？怎么进行剪枝？

决策树下，有ID3、C4.5、CART、随机森林、bagging、boosting、Adaboost、GBDT、xgboost等等诸多具体算法。

不同算法的细节当然不同，这里只介绍决策树的一些常见思路。

最优划分属性

混杂度

我们偏向于使用简洁的具有较少节点的树，希望用更少的节点更有效的分类。

我们希望在一个节点上，通过一个属性就能将样本确切的分类，那么这就是最优划分属性；如果一
个属性不能确切分类那么这个属性的划分性能就很差。

举例来说，比如判断一个人是不是大学本科生。
如果子决策的属性选为：“是否知道乘法口诀表”，在“知道”分支下的样本中，是与不是的人群仍然混杂在一起，我们认为信息不纯，分类效果很差；
如果如果子决策的属性选为“是否有大学本科生学生证”，那么在“有”的分支下的样本里，基本就全都是大学本科生，我们认为信息很纯，分类效果很好。

我们将这种信息的纯不纯，定义为 混杂度(impurity)。

信息熵

定义信息熵(information entropy)来形容这种混杂度（不同教材的符号不同，这里李航老师教材为主）：

信息熵的单位为(bit)。

当在进行二分类问题的时候，随机变量结果可以记为1与0，表现为一种伯努利试验。在这种情况下，信息熵与p的关系如下图:

我们规定，p=0时，\(plog_2p=0\) 。可从图中看出，当分类效果最好时，p=1或0，H(p)=0;当分类效果最差时，样本中的正例负例比例仍为1:1，H(p)=1。

计算举例如下：

多分类时，分类数与最大信息熵、取最大信息熵时的\(p_i\) 关系如下：

基尼指数(Gini)

基尼指数通常用于CART算法。这里简单介绍：

信息增益

信息增益(information gain)用来形容 在进行一次分类之后混杂度的下降情况。

定义信息增益：

其具体算法如下：

分别计算不同属性分类下的信息增益，选择信息增益最大时对应的属性 的作为最优划分属性。

举例如下：

以信息增益作为选择最优划分属性具有一个缺陷。
考虑一种极端情况,给出n个样本,对其进行1到n编号,并将这种编号作为一个属性,进行分类,那么信息增益极高,一次就能对训练集分类完成,但是对于未见样本,这样的决策树显然是不具备任何泛化能力的。
可见信息增益作为选择最优划分属性时，这种方法会偏向于分类类别多的情况。这时候，引入“信息增益比”，这里简单介绍：

\(H_A*(D)\)也被称作属性A的“固有值”，以信息增益比作为选择最优划分属性的依据，这就是C4.5的算法思路。

剪枝(pruning)

决策树分支过多，学习训练集效果太好，但是泛化能力差，这样就是过拟合。

剪枝操作直接减去某些内部节点的后续分支，将这样的内部节点变成叶节点。

采用预剪枝，就是当数据的分裂在统计意义上并不显著时，就停止生成树。
采用后剪枝，就是构建一棵完全树之后再进行剪枝。

预剪枝(prepruning)

预剪枝有如下几种思路：

1. 由于基于数据样本的决定会带来较大误差和泛化错误。
   所以，当到达一个节点的训练样本数小于训练集合的一个特定比例 (例如 5%)，无论混杂度或错误率是多少都不在继续生成树，直接作为叶节点。

2. 设定一个较小的阈值，如果信息熵增益小于这个阈值，就停止分裂。

3. （见西瓜书）在训练集中留出一部分作为验证集。
   在考虑是否继续在该节点下继续划分时，计算继续划分与不划分的树在验证集上的正确率，如果划分后正确率不上升就不继续划分。这种“贪心”的方法，会带来欠拟合的的风险。

后剪枝(postpruning)

1. 错误降低剪枝
   （见西瓜书）与预剪枝中的3思路类似。

在整个树生成完毕后，从后往前查看是否剪枝。如果剪枝之后的树在验证集上的表现没有得到提升，就不剪。这样的剪枝相比同思路下的预剪枝欠拟合风险更小，但是时间成本更高。

2. （先简单了解）将树转变成等价的的规则的集合。对每条规则剪枝，考察每一个规则前件((23条消息) 第八章 基于规则的分类_Coding Life-CSDN博客_基于规则的分类)，看看去除哪一个能提升验证集上的正确率。每条规则修改完之后，构成了新的规则的集合，将每条规则按照从高到低排序。现将样本代入正确率最高的规则进行判断，如果不行就代入正确率第二高的，以此类推。

剪枝之后的标签设定

1. 前文之中，剪枝后都用了样本中的众数作为标签

2. 也可以将样本中每种类别所占的比例当做概率，依据概率输出结果。

连续值的处理

主要思路是在离散数据中设立不同划分点，将连续数据划分为离散数据。

划分点的选择：

1. 大小相邻但是有不同决策值的数据的中点：