决策树（ID3、C4.5与CART）——从信息增益、信息增益率到基尼系数
⽬录
⼀、决策树
决策树是分类算法，属于有监督学习。决策树的⽣成过程就是if-else的过程。
决策树的⽣成有两个要点：
1、节点特征的选择
2、节点分裂值的选择。
⼆、区别
1、ID3与C4.5采⽤信息熵作为选择准则的基础（ID3采⽤信息增益率，C4.5采⽤信息增益率），CART选择基尼指数作为选择准则的基础（分类树采⽤基尼指数，回归树采⽤⽅差，⽤最⼩⼆乘法求解）。
2、ID3和C4.5只⽤于分类，CART可以⽤于分类与回归。其中I
3、ID3和C4.5可以是多叉树，CART是⼆叉树。
4、ID3只能使⽤离散特征，C4.5和CART可以处理连续特征。
5、ID3不能处理缺失值，C4.5可以处理缺失值。
三、ID3
ID3采⽤信息增益作为准则来划分属性。
1、信息熵与条件信息熵
信息熵（information entropy）⽤来衡量数据集的混乱程度（纯度），信息熵越⼤，则表明数据集的混乱程度越⼤。
数据集D的信息熵⽤如下公式表⽰，
其中，Ck表⽰属于第k类的个数，所有类别数量的总和为D的数量。
条件信息熵的公式如下：
2、信息增益（IG，information gain）
信息增益公式如下：
信息增益越⼤，则意味着采⽤该属性A划分节点获得的纯度提升更⼤。在每次划分中采⽤信息增益最⼤的划分。
信息增益偏好划分类别多的属性。例如某个属性是⾝份证号，则该属性每⼀个样本的值都不相同，条件信息熵为0，信息增益达到最⼤，但该属性的划分毫⽆意义，C4.5就是对划分准则的改进。
3、⽣成步骤
决策树的划分是⼀个递归过程。
（1）设置信息增益的阈值。
（2）选择信息增益最⼤的特征A。
（3）如果特征A的信息增益⼩于阈值A，则返回单节点树。采⽤投票发，该结点的类型为样本数量最多的类别。
（4）否则，按照特征A将节点划分为多颗⼦树，返回增加了⼦节点的节点。
（5）对各个⼦节点，递归调⽤上述步骤，直到达到停⽌标准（树的深度、信息增益阈值或者没有样本可划分）
四、C4.5
C4.5采⽤信息增益率作为划分标准。
1、信息增益率
信息增益率 = 信息增益 / 分裂熵
数据集D信息增益率的公式为：
其中，分裂熵H(D)的公式为：
当A的取值越多时，分裂熵越⼤，信息增益率越⼩，达到了惩罚的⽬的。
需要注意的是，增益率可能会对数⽬少的特征有所偏好，因此C4.5采⽤了启发式的⽅法：先从候选划分属性中出信息增益⾼于平均⽔平的属性，再从中选出信息增益率最⾼的。
2、连续特征
C4.5采⽤⼆分法处理连续特征，将连续特征进⾏排列，将连续两个值的中间值作为分裂节点，将⼩于该值和⼤于该值的样本分为两个类别，到信息增益最⼤的分裂点，本质上还是⽤的离散特征。
需注意的是，与离散属性不同，若当前节点划分属性为连续属性，该属性还可作为其后代节点的划分属性。
3、缺失值
（1）如何在属性值缺失的情况下划分属性
将数据集分成两部分：没有缺失值的部分、有缺失值的部分。对每个样本设置⼀个权重，将没有缺失值的部分按照占据总样本的⽐例计算信息增益率，并乘上所占⽐例。
二叉树公式（2）给定划分属性，若样本在该属性上缺失，如何对样本进⾏划分
若样本x在划分属性a上的取值未知，则将x同时划⼊所有⼦节点，且样本权值按所占⽐例和样本权值进⾏调整。直观地看，这就是让同⼀个样本以不同的概率划⼊到不同的⼦节点中。
4、正则化
C4.5引⼊了正则项进⾏了初步的过拟合处理。
5、总结
优点：
相⽐ID3，应⽤信息增益率进⾏特征选择
可以处理连续特征
可以处理缺失值
引⼊了正则化防⽌过拟合
缺点：
信息增益率采⽤熵的计算，⾥⾯有⼤量耗时的对数计算
多叉树的计算效率不如⼆叉树⾼
决策树模型容易过拟合，所以应该引⼊剪枝策略进⾏处理
五、CART
1、简介
CART的全称为Classification and Regression Tree，是最佳的决策树模型，sklear中的决策树也是应⽤的CART树。CART是⼆叉树模型
2、分类树
2.1、基尼指数
分类树采⽤了基尼指数作为类别选择的依据。基尼纯度越⼩，代表数据集的纯度越⾼，分类效果越好。
特征p的基尼值公式如下：
特别的，当特征只有两个类别时，基尼指数为：
对于特征A，若其将数据集分为D1和D2两部分，则其基尼指数为：
在候选集中，选择那个使得划分后基尼指数最⼩的属性作为最优的划分属性。
2.2、基尼指数与熵的关系
熵和基尼指数的关系如下图：
可以看出基尼指数近似于熵。
2.3、连续特征
与C4.5类似，采⽤连续特征离散化的思想。若特征A有k个取值，则有k-1个划分点，从这些划分点中选取基尼系数最⼩的划分点作为该特征的划分点。
2.4、离散特征
思想是将特征⼆分化，形成很多划分组合，在这些组合中到基尼指数最⼩的作为特征的划分标准。
2.5、⽣成步骤CART分类树⼤概⽣成步骤：
CART树和ID3⼀样，也是递归的过程。给定阈值、树的深度作为输⼊的超参数。
1、如果基尼系数⼩于给定的阈值，则返回决策树⼦树，当前节点停⽌递归。如果当前节点的样本数⼩于阈值或者没有特征，返回决策⼦树，停⽌递归。
2、计算当前节点的现有的各个特征的各个特征值对数据集D的基尼系数。选择基尼系数最⼩的特征A和对应的特征值a。将数据集划分为两部分D1和D2。
3、对左右的⼦节点递归调⽤上述步骤。
对于⽣成的决策树预测时，加⼊测试集的样本X落到了某个叶⼦节点，⽽节点⾥有多个训练样本。则对于A的类别预测采⽤这个叶⼦节点⾥概率最⼤的类别。（所以也可以输出概率）
3、回归树
3.1、⽅差
回归树采⽤⽅差，利⽤最⼩⼆乘法求解⽅差和的极⼩值。
对于特征j，到j所有的划分点s，s将数据集分为c1、c2两部分，出使得两部分的⽅差最⼩，同时整体⽅差最⼩的特征j以及划分点s。
其中yi为数据集的均值：
对于离散特征，采⽤均值或者中位数作为节点的输出结果。
3.2、CART剪枝
剪枝分为预剪枝和后剪枝，CART采⽤后剪枝。即先⽣成⼀颗决策树，然后产⽣所有剪枝后的CART树，使⽤交叉验证来检验各种减值后的效果，选择泛化能⼒最好的剪枝策略。

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