北京哪家公司做网站好,红页网站如何做,网上课程网站,wordpress全自动采集决策树概述
决策树#xff08;decision tree#xff09;#xff1a;是一种基本的分类与回归方法#xff0c;下面提到的ID3、C4.5、CART主要讨论分类的决策树。
在分类问题中#xff0c;表示基于特征对实例进行分类的过程#xff0c;可以认为是if-then的集合#xff0c…决策树概述
决策树decision tree是一种基本的分类与回归方法下面提到的ID3、C4.5、CART主要讨论分类的决策树。
在分类问题中表示基于特征对实例进行分类的过程可以认为是if-then的集合也可以认为是定义在特征空间与类空间上的条件概率分布。 决策树通常有三个步骤
特征选择决策树的生成决策树的剪枝
决策树的优点和缺点
优点
决策树算法中学习简单的决策规则建立决策树模型的过程非常容易理解决策树模型可以可视化非常直观应用范围广可用于分类和回归而且非常容易做多类别的分类能够处理离散型和连续的样本特征训练极端样本对树模型的性能影响相对其他模型较小(不包括回归树)不平衡样本数据集也能取得好的表现CART树
缺点
很容易在训练数据中生成复杂的树结构造成过拟合overfitting。剪枝可以缓解过拟合的负作用常用方法是限制树的高度、叶子节点中的最少样本数量。学习一棵最优的决策树被认为是NP-Complete问题。实际中的决策树是基于启发式的贪心算法建立的这种算法不能保证建立全局最优的决策树。Random Forest 引入随机能缓解这个问题。
常用的决策树模型
决策树模型在监督学习中非常常见决策树是一个非常常见并且优秀的机器学习算法它易于理解、可解释性强其可作为分类算法也可用于回归模型。本文主要介绍常用的基本树包括 ID3、C4.5、CART。一般而言一棵“完全生长”的决策树包含特征划分、决策树构建、剪枝三个过程。
在介绍决策树之前我们先了解一下“纯度”的概念 决策树的构建是基于样本概率和纯度进行构建操作的判断数据集“纯”的指标有Gini指数、信息熵、不确定性、错误率、标准方差。他们的值越小说明越“纯”。并且他们有以下关系
信息熵可以理解为衡量不确定性的指标。 Gini指数可以理解为衡量错误率的指标。
下面开始介绍一下常用的三种算法ID3、C4.5、CART。
ID3算法
划分标准ID3选用使得信息增益最大纯度提升的那个特征作为决策节点来划分样本。
ID3算法的三个基本概念和通俗的理解 信息熵entropy 表示随机变量的不确定性。 条件熵(Conditional Entropy) 在一个条件下随机变量的不确定性。 信息增益Information Gain 信息增益信息熵 - 条件熵。表示在一个条件下信息不确定性减少的程度纯度提升。
ID3算法缺点
倾向于使用属性值多的特征来划分样本不能处理具有连续值的特征。不能处理特征具有缺失值的样本。ID3 没有剪枝策略容易过拟合。
由于上述缺点如今几乎没人再使用ID3但是信息增益的概念是重要的。
C4.5算法
划分标准C4.5算法选用使得信息增益率(gain ratio)最大的那个特征作为决策节点来划分样本。
因为ID3算法中选用信息增益来作为决策树的生成策略导致了生成过程中倾向于使用属性值多的特征来划分样本为了克服这一缺点。引进了信息增益率信息增益比的概念。
C4.5算法相对于ID3算法主要有以下几个改进:
用信息增益率来选择属性引入悲观剪枝策略进行后剪枝可以对连续数据进行离散化处理能够处理具有缺失值的样本。
CART算法
CART(classification and regression tree)分类回归树它既可以用来解决分类问题也可以用来解决回归问题。
划分标准使用使得gini系数最小的那个属性来划分样本。
基尼系数Gini不纯度表示在样本集合中一个随机选中的样本被分错的概率。
注意Gini系数越小表示集合中被选中的样本被分错的概率越小也就是说集合的纯度越高反之集合越不纯。当集合中所有样本只有一个类时基尼系数为0.
CART 在 C4.5 的基础上进行了很多提升
C4.5 为多叉树运算速度慢CART 为二叉树运算速度快C4.5 只能分类CART 既可以分类也可以回归CART 使用 Gini 系数作为变量的不纯度量减少了大量的对数运算CART 采用代理测试来估计缺失值而 C4.5 以不同概率划分到不同节点中CART 采用“基于代价复杂度剪枝CPP”方法进行剪枝而 C4.5 采用悲观剪枝PEP方法。
简单总结一下CART
CART与C4.5算法是非常相似的但是CART支持预测连续的值即回归。CART构建二叉树而C4.5则不一定。显然由于二叉树的原因使得CART5不会出现ID3的问题倾向于选择属性值多的属性来划分样本CART用训练集和交叉验证集不断地评估决策树的性能来修剪决策树从而使训练误差和测试误差达到一个很好地平衡点。此外CART 的一大优势在于无论训练数据集有多失衡它都可以将其子冻消除不需要建模人员采取其他操作。
通过前面的介绍我们知道了基本树ID3、C4.5、CART都是采用“纯度”来做特征选择。它们的思路都相近得到的模型性能也比较接近。
那么问题来了基尼指数与熵模型性能接近但到底与熵模型的差距有多大呢
我们知道 ln(x) -1 x o(x)所以 我们可以将基尼指数理解为熵模型的一阶泰勒展开下面放上一张很经典的图。
剪枝
剪枝是应该决策树过拟合的一种重要方法主要分为以下两种
预剪枝该策略就是在对一个节点进行划分前进行估计如果不能提升决策树泛化精度就停止划分将当前节点设置为叶节点。那么怎么测量泛化精度就是留出一部分训练数据当做测试集每次划分前比较划分前后的测试集预测精度。
简单来说预剪枝就是在完全正确分类训练集之前较早地停止树的生长。 具体在什么时候停止决策树的生长有多种不同的方法:
一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长。到达此结点的实例具有相同的特征向量而不必一定属于同一类 也可停止生长。到达此结点的实例个数小于某一个阈值也可停止树的生长。还有一种更为普遍的做法是计算每次扩张对系统性能的增益如果这个增益值小于某个阈值则不进行扩展。
预剪枝的优缺点
优点降低了过拟合风险降低了训练所需的时间。
缺点预剪枝是一种贪心操作可能有些划分暂时无法提升精度但是后续划分可以提升精度。故产生了欠拟合的风险。
后剪枝该策略是首先正常建立一个决策树然后对整个决策树进行剪枝。按照决策树的广度优先搜索的反序依次对内部节点进行剪枝如果将某以内部节点为根的子树换成一个叶节点可以提高泛化性能就进行剪枝。
优点降低过拟合风险降低欠拟合风险决策树效果提升比预剪枝强
缺点时间开销大得多
常用的后剪枝方法
REP-错误率降低剪枝PEP-悲观剪枝C4.5决策树CCP-代价复杂度剪枝(CART树)MEP-最小错误剪枝
回归树
CARTClassification and Regression Tree分类回归树从名字就可以看出其不仅可以用于分类也可以应用于回归。其回归树的建立算法上与分类树部分相似这里简单介绍下不同之处。
所谓回归树就是用树模型做回归问题每一片叶子都是一个预测值预测值一般是叶子节点所含训练集元素输出的均值。
划分标准使用标准差/方差小的那个特征属性来划分样本。
回归树对连续值的处理
对于连续值的处理CART 分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中我们使用常见的和方差度量方式对于任意划分特征 A对应的任意划分点 s 两边划分成的数据集D1 和D2 求出使D1 和 D2 各自集合的均方差最小同时 D1 和D2 的均方差之和最小所对应的特征和特征值划分点。表达式为 其中c1 为 D1 数据集的样本输出均值c2 为 D2数据集的样本输出均值。
回归树的预测方式
对于决策树建立后做预测的方式 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别它采用的是用最终叶子的均值或者中位数来预测输出结果。
总结 参考文献
https://blog.csdn.net/qq_43391414/article/details/109382789 https://zhuanlan.zhihu.com/p/85731206
