机器学习总结（⼋）决策树ID3，C4.5算法，CART算法
本⽂主要总结决策树中的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个类别的概率为pk, 则基尼系数的表达式为：
如果是⼆类分类问题，计算就更加简单了，如果属于第⼀个样本输出的概率是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的均⽅差之和最⼩所对应的特征和特征值作为划分点。
表达式如下：
其中，c1为D1数据集的样本输出均值，c2为D2数据集的样本输出均值
1）对于数据集D，通过平⽅误差准则（上⾯式⼦），选择最优的切分变量和切分点；
2）⽤选定的最优切分变量和切分点划定两个⼦区域区域，并输出该区域数据集样本的均值。
3）继续对两个⼦区域进⾏调⽤步骤1）和2），直⾄满⾜停⽌条件
4）最后将样本空间划分成M个区域，即M个叶结点，以及M个与叶结点对应的输出值。
CART树的剪枝
CART树的剪枝就是加⼊先验的过程，其损失函数如下：
Cα(T)=C(T)+α|T|
其中T为任意⼦树，C（T）为对训练数据的预测误差（如基尼系数），|T|为叶结点的个数，α>=0为参数，Cα(T)为整体损失。
正则化项的加⼊能够起到剪枝的作⽤，从⽽降低了模型的复杂度。⽽α参数起到了平衡模型复杂度与训练数据拟合度的作⽤。
（五）总结
决策树的缺点
1）决策树算法属于贪⼼的算法，在⽣成树的过程中只考虑局部最优形成，⽽不考虑整体最优，所以⽣成的树容易产⽣过拟合，
（即对训练集的分类很正确，但是对未知的数据分类却没那么准确，泛化能⼒不强）。所以需要在决策树⽣成后对其进⾏剪枝，
也就是说简化模型的复杂度，⼀般通过加正则化项来进⾏剪枝。
2）决策树对训练数据的变化敏感，数据集变化，树就会发⽣变化；该缺点可以通过集成树来解决。譬如随机森林，随机森林的数据样本扰动。
3）决策树没有考虑变量之间相关性，每次筛选都只考虑⼀个变量（因此不需要归⼀化）
决策树的优点：
1）简单直观，模型解释性好
2）基本不需要预处理，不需要提前归⼀化，处理缺失值
3）使⽤决策树预测的代价是O(log2m)。 m为样本数
4）既可以处理离散值也可以处理连续值
5）对于异常点的容错能⼒好，健壮性⾼
6）可以处理多维度输出的分类问题

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。