塞进裤子ヾ(≧O≦)〃嗷~

0%

决策树

决策树

Decisison Tree

一种监督学习方法。

每个叶子结点都是一个类别标签。

决策树算法的核心是要解决两个问题:

1.如何从数据表中找出最佳属性进行分裂?

2.如何让决策树停止生长,防止过拟合?

为了要将数据转化为一棵树,决策树需要找出最佳属性的分枝方法,对分类树来说,衡量这个“最佳”的指标叫做熵。熵越小,效果越好。

熵是基于节点来计算的,树中的每个结点都会有一个熵。

属性选择方法

1.信息增益 ID3

按信息增益分类决策树的流程

计算原始数据的信息熵,
按每个特征划分数据集,计算划分数据集后的信息熵,计算其信息增益。
根据信息增益,选择信息增益最大的特征进行分类。

reference:https://www.cnblogs.com/fengfenggirl/p/classsify_decision_tree.html

2.增益比率 C4.5

gain ratio

见书面笔记

3.基尼系数/基尼指数 CART

gini impurity / gini index

见书面笔记

剪枝

剪枝(pruning)的目的是为了避免决策树过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本,不停地对结点进行划分,因此这会导致整棵树的分支过多,也就导致了过拟合。

决策树的剪枝策略最基本的有两种:预剪枝(pre-pruning)和后剪枝(post-pruning):

  • 预剪枝(pre-pruning):预剪枝就是在构造决策树的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来决策树模型泛华性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。
  • 后剪枝(post-pruning):后剪枝就是先把整颗决策树构造完毕,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛华性能的提升,则把该子树替换为叶结点。

预剪枝

Eg:

用ID3构造决策树,计算每个特征的信息增益,得色泽脐部的信息增益最大,所以从这两个中随机挑选一个,这里选择脐部来对数据集进行划分,这会产生三个分支(凹陷,稍凹,平坦)。

但是因为是预剪枝,所以要判断是否应该进行这个划分,判断的标准就是看划分前后的泛化性能是否有提升,也就是如果划分后泛化性能有提升,则划分;否则,不划分。

下面来看看是否要用脐部进行划分,划分前:所有样本都在根节点,把该结点标记为叶结点,其类别标记为训练集中样本数量最多的类别,这里好和坏的个数二者一样,随机标记为好瓜(对新样本就预测为好瓜),然后用验证集对其性能评估,可以看出样本{4,5,8}被正确分类,其他被错误分类,因此精度为3/7。

按脐部划分后的的决策树为

凹陷的瓜有1,2,3,14,其中好瓜3个,坏瓜1个,所以对新样本只要是凹陷就预测为好瓜。

验证集上4,5,8,11,12分类正确,则验证集在这颗决策树上的精度为:5/7 >3/7。因此,用 脐部 进行划分。

接下来,决策树算法对结点 (2) 进行划分,再次使用信息增益挑选出值最大的那个特征,这里我就不算了,计算方法和上面类似,信息增益值最大的那个特征是“色泽”,则使用“色泽”划分,但到底该不该划分这个结点,还是要用验证集进行计算,

划分前,根据上一步划分结果凹陷和稍凹预测为好瓜,平坦预测为坏瓜,在验证集上4,5,8,11.12分类正确,划分前精度为5/7;

按色泽划分后,

4,8,11,12分类正确,精度为:4/7=0.571<5/7,因此,预剪枝策略将禁止划分结点 (2) 。

对于结点 (3) 最优的属性为“根蒂”,划分后验证集精度仍为71.4%,因此这个划分不能提升验证集精度,所以预剪枝将禁止结点 (3) 划分。对于结点 (4) ,其所含训练样本已属于同一类,所以不再进行划分。
所以基于预剪枝策略生成的最终的决策树为:

由图可知,预剪枝使得很多分支没有展开,这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销和测试时间。但是,有些分支虽当前不能提升泛化性。甚至可能导致泛化性暂时降低,但在其基础上进行后续划分却有可能导致显著提高,因此预剪枝的这种贪心本质,给决策树带来了欠拟合的风险。

Re:

https://blog.csdn.net/u012328159/article/details/79285214 (有些数值计算错了,先看评论。)

https://blog.csdn.net/zfan520/article/details/82454814

后剪枝

​ 首先构造完整的决策树,允许树过度拟合训练数据,然后对那些置信度不够的结点子树用叶子结点来代替,该叶子的类标号用该结点子树中最频繁的类标记。相比于先剪枝,这种方法更常用,正是因为在先剪枝方法中精确地估计何时停止树增长很困难

常见后剪枝方法:

Reduced-Error Pruning(REP,错误率降低剪枝)

Pesimistic-Error Pruning(PEP,悲观错误剪枝)

Cost-Complexity Pruning(CCP,代价复杂度剪枝)

MEP,CVP,OPP

REP后剪枝例子:

https://blog.csdn.net/u012328159/article/details/79285214

https://blog.csdn.net/zfan520/article/details/82454814

CCP后剪枝例子:

A、B表示训练集的两类,节点的类别标号为该节点中类别较多的那个类

具体见葫芦书P69

if help:小手一抖点个广告 or 大手一挥资助一下