正文

机器学习总结决策树id3，c4.5算法，cart算法

jackhehe  jackhehe  2023-01-14  801

关键词：

本文主要总结决策树中的ID3,C4.5和CART算法，各种算法的特点，并对比了各种算法的不同点。

决策树：是一种基本的分类和回归方法。在分类问题中，是基于特征对实例进行分类。既可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。

决策树模型：决策树由结点和有向边组成。结点一般有两种类型，一种是内部结点，一种是叶节点。内部结点一般表示一个特征，而叶节点表示一个类。当用决策树进行分类时，先从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到子结点。而子结点这时就对应着该特征的一个取值。如此递归对实例进行测试分配，直至达到叶结点，则该实例属于该叶节点的类。

决策树分类的主要算法有ID3，C4.5。回归算法为CART算法，该算法既可以分类也可以进行回归。

（一）特征选择与信息增益准则

特征选择在于选取对训练数据具有分类能力的特征，而且是分类能力越强越好，这样子就可以提高决策树的效率。如果利用一个特征进行分类，分类的结果与随机分类的结果没有差异，那么这个特征是没有分类能力的。那么用什么来判别一个特征的分类能力呢？那就是信息增益准则。

何为信息增益？首先，介绍信息论中熵的概念。

熵度量了随机变量的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵定义如下：

技术分享图片

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵为H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

技术分享图片

信息增益表示在已知特征X的情况下，而使得Y的信息的不确定性减少的程度。信息增益的定义式如下：

技术分享图片

g(D,A)表示特征A对训练集D的信息增益，其为集合D的经验熵H(D)与在特征A给定条件下D的经验条件熵H(D|A)之差。一般熵与条件熵之差，称为互信息。在决策树中，信息增益就等价于训练数据集中的类与特征的互信息。

具体信息增益的计算

（1）计算数据集D的经验熵H(D)

技术分享图片

(2)计算特征A对数据集D的经验条件熵H(D|A）：

技术分享图片

（3）计算信息增益

技术分享图片

（二）ID3算法

ID3算法以信息增益作为选择特征的准则

输入：训练数据集D，特征集A（可以从训练集中提取出来），阀值ε（用来实现提前终止）；

（1）若当前节点中所有实例属于同一类C_k，则该结点作为叶子节点，并将类别C_k作为该结点的输出类；

（2）若A为空，则将当前结点作为叶子节点，并将数据集中数量最多的类作为该结点输出类；

（3）否则，计算所有特征的信息增益，若此时最大的信息增益小于阀值ε，则将当前结点作为叶子节点，并将数据集中数量最多的类作为该结点输出类；

（4）若当前的最大信息增益大于阀值ε，则将最大信息增益对应的特征A作为最优划分特征对数据集进行划分，根据特征A的取值将数据集划分为若干个子结点；

（5）对第i个结点，以Di为训练集，以Ai为特征集（之前用过的特征从特征集中去除），递归的调用前面的1- 4 步。

ID3算法的缺点：

（1）ID3算法会偏向于选择类别较多的属性（形成分支较多会导致信息增益大）

（2）ID3算法没有考虑连续值，对与连续值的特征无法进行划分

（3） ID3算法对于缺失值的情况没有做考虑。

（4）ID3算法只有树的生成，容易产生过拟合。

（5）ID3算法采用贪心算法，每次划分都是考虑局部最优化，而局部最优化并不是全局最优化，通常需对其进行剪枝，而决策树剪枝是对模型进行整体优化。

（三）C4.5算法

C4.5算法与ID3算法相似，不过在生成树的过程中，采用信息增益比来作为选择特征的准则。

增益比：

其中为特征熵，n为特征取值的数目。

C4.5算法的训练过程与ID3相似，见ID3算法。

C4.5其实是针对ID3算法的不足改进后的算法，采用信息增益比，是为了解决ID3算法会偏向于选择类别多的属性的问题。而对于ID3算法不能对连续值进行划分的问题，C4.5采用连续值特征离散化的。此外，C4.5还从以下两方面考虑了缺失值的问题：一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。对于ID3存在的过拟合问题，C4.5采用了引进正则化系数，对决策树进行剪枝。

（四）CART算法

CART树既可以用于分类，也可以用于回归。CART树的生成过程同样包括特征选择，树的生成及剪枝。

与ID3，C4.5算法不同的是，首先，CART进行特征选择时，回归树用的平方误差最小化的准则，而对于分类树用基尼系数。对于平方误差好理解。主要介绍下分类时用的基尼系数，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。具体的，在分类问题中，假设有K个类别，第k个类别的概率为 $p_{k}$

如果是二类分类问题，计算就更加简单了，如果属于第一个样本输出的概率是p，则基尼系数的表达式为：

技术分享图片

简单明了的理解基尼系数那就是，从集合中随机选取两个样本，两个样本的类别不一致的概率，所以这概率越低，说明划分的集合的不纯度就越低。

对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为：

技术分享图片

基尼系数用于度量时，与熵之半，分类误差率的关系。可见，基尼系数和熵之半的曲线非常接近，都可以近似的代表分类误差率

技术分享图片

此外，CART树在生成过程中，生成的是二叉树。即CART树在生成过程中仅仅是对特征的值进行二分，而不是多分。

CART分类树建立的过程：

对于给定训练数据集D，从根结点开始递归的建立二叉决策树：

1）根据数据集D中每个特征A，以及其可能的取值a,按照取值的‘是‘和‘否’将数据集分成两部分，然后计算基尼系数。

2）在所有可能的特征A以及他们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征的与最优切分点。

依最优特征和最优切分点，将现结点生成两个子结点，将训练数据集依特征分配到两个子结点中。

3）递归的调用1）2）步骤，直至达到停止条件

停止条件有：结点中的样本数小于预定的阈值，或者样本集的基尼系数小于预定的阈值（此时基尼系数已经非常小，样本基本属于同一类），

或者结点样本中没有更多的特征。

CART回归树建立的过程：

首先说下分类树和回归树的区别吧，分类树样本输出的值为离散的类别值（如二分类输出的值为0和1），而回归树样本输出的是连续值。

在分类树中，采用基尼系数来对特征进行划分。而在CART回归树用的平方误差最小化准则，具体就是对于任意划分特征A，

对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时将D1和D2的均方差之和最小所对应的特征和特征值作为划分点。

表达式如下：

技术分享图片

其中， $c_{1}$

$c_{1}$

$c_{1}$

$c_{1}$

C_α(T)=C(T)+α|T|

其中T为任意子树，C（T）为对训练数据的预测误差（如基尼系数），|T|为叶结点的个数，α>=0为参数，C_α(T)为整体损失。

正则化项的加入能够起到剪枝的作用，从而降低了模型的复杂度。而α参数起到了平衡模型复杂度与训练数据拟合度的作用。

（五）总结

决策树的缺点

1）决策树算法属于贪心的算法，在生成树的过程中只考虑局部最优形成，而不考虑整体最优，所以生成的树容易产生过拟合，

（即对训练集的分类很正确，但是对未知的数据分类却没那么准确，泛化能力不强）。所以需要在决策树生成后对其进行剪枝，

也就是说简化模型的复杂度，一般通过加正则化项来进行剪枝。

2）决策树对训练数据的变化敏感，数据集变化，树就会发生变化；该缺点可以通过集成树来解决。譬如随机森林，随机森林的数据样本扰动。

3）决策树没有考虑变量之间相关性，每次筛选都只考虑一个变量（因此不需要归一化）

决策树的优点：

1）简单直观，模型解释性好

2）基本不需要预处理，不需要提前归一化，处理缺失值

3）使用决策树预测的代价是 $O (l o g_{2} m)$

$O (l o g_{2} m)$

机器学习——决策树（下）算法实现

Decisiontree在机器学习（5）——决策树（上）原理中介绍了决策树的生成和剪枝原理。介绍了CART,ID3，C4.5等算法的算法流程，其中CART算法可以实现回归和分类，是基于基尼不纯度实现的，这里并未实... 查看详情

02-24决策树总结

...算法比较二、决策树优缺点2.1优点2.2缺点更新、更全的《机器学习》的更新网站，更有python、go、数据结构与算法、爬虫、人工智能教学等着你：https://www.cnblogs.com/nickchen121/决策树总结一、ID3算法、C4.5算法和CART算法比较算法树... 查看详情

决策树系列算法总结（id3,c4.5,cart,randomforest,gbdt）

前言线性系列的算法（比如logisticregression，SVM；当然，它们不完全是线性的）的逻辑一般是求每个特征对最终分类结果的贡献权重。但是，这种线性组合并不总是有意义的。在这种情况下，如果不想使... 查看详情

机器学习-决策树算法（id3c4.5和cart）

文章目录简介划分依据ID3算法C4.5算法CART算法处理连续值剪枝应用示例前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。简介决策树（DecisionTree）是... 查看详情

决策树算法原理

...义了，不顾以后还是多像楼主学习）　　　决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。本文就对决策树算法原理做一个总结，... 查看详情

机器学习---算法---决策树

.../blog.csdn.net/qq_43208303/article/details/84837412 决策树是一种机器学习的方法。决策树的生成算法有ID3,C4.5和CART等。决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶... 查看详情

机器学习：决策树(decisiontree)--id3算法(代码片段)

决策树的主要算法构建决策树的关键：按照什么样的次序来选择变量（属性/特征）作为分类依据。根据不同的目标函数，建立决策树主要有以下三种算法ID3(J.RossQuinlan-1975)核心：信息熵，信息增益C4.5——ID... 查看详情

决策树与迭代决策树(转)

....5&CART4.RandomForest5.GBDT6.参考内容今天我们来谈一谈机器学习算法中的各种树形算法，包括ID3、C4.5、CART以及基于集成思想的树模型RandomForest和GBDT。本查看详情

机器学习笔记(代码片段)

机器学习笔记（四）文章目录机器学习笔记（四）线性判别分析多分类学习类别不平衡问题小总结决策树决策树的基本概念决策树的构造ID3算法C4.5算法CART算法线性判别分析线性判别分析（LinearDiscriminantAnalysis&... 查看详情

机器学习笔记(代码片段)

机器学习决策树分类原理(代码片段)

决策树分类原理1.熵1.1概念1.2案例2.决策树的划分依据2.1信息增益2.1.1概念2.1.2案例2.2信息增益率2.2.1概念2.2.2案例案例一案例二2.2.3为什么使用C4.5要好?2.3基尼值和基尼指数2.3.1概念2.3.2案例3.小结3.1常见决策树的启发函数比较3.1.1ID3... 查看详情

决策树算法cart和c4.5决策树有啥区别？各用于啥领域？

...选择测试属性。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，又出现了根据GINI系数来选择测试属性的决策树... 查看详情

决策树算法

　在决策树算法原理(上)这篇里，我们讲到了决策树里ID3算法，和ID3算法的改进版C4.5算法。对于C4.5算法，我们也提到了它的不足，比如模型是用较为复杂的熵来度量，使用了相对较为复杂的多叉树，只能处理分类不能处理回归... 查看详情

分类算法：决策树（c4.5）(转)

C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点： 1）用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来... 查看详情

机器学习决策树——id3和c4.5（理论+图解+公式推导）

查看详情

决策树(id3,c4.5,cart)原理以及实现(代码片段)

...代表所有数据集;叶子节点看做是判断所属的类别.决策树学习通常包括3个查看详情