2.决策树（DecisionTree）-ID3、C4.5、CART⽐较
1. 前⾔
上⽂介绍了决策树原理和算法，并且涉及了ID3，C4.5，CART3个决策树算法。现在⼤部分都是⽤CART的分类树和回归树，这三个决策树算法是⼀个改进和补充的过程，⽐较它们之间的关系与区别，能够更好的理解决策时算法。
2. ID3算法
2.1 ID3原理
ID3算法就是⽤信息增益⼤⼩来判断当前节点应该⽤什么特征来构建决策树，⽤计算出的信息增益最⼤的特征来建⽴决策树的当前节点。算法具体过程看
2.2 ID3的不⾜洋葱可以炒鸡蛋吗
ID3算法虽然提出了新思路，但是还是有很多值得改进的地⽅。
什么空调1. ID3没有考虑连续特征，⽐如长度，密度都是连续值，⽆法在ID3运⽤。这⼤⼤限制了ID3的⽤途。
2. ID3采⽤信息增益⼤的特征优先建⽴决策树的节点。很快就被⼈发现，在相同条件下，取值⽐较多的特征⽐取值少的特征信息增益⼤。
⽐如⼀个变量有2个值，各为1/2，另⼀个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的⽐取2个值的信息增益⼤。如果校正这个问题呢？
3. ID3算法对于缺失值的情况没有做考虑
4. 没有考虑过拟合的问题
ID3 算法的作者昆兰基于上述不⾜，对ID3算法做了改进，这就是C4.5算法，也许你会问，为什么不叫ID4，ID5之类的名字呢?那是因为决策树太⽕爆，他的ID3⼀出来，别⼈⼆次创新，很快就占了ID4，ID5，所以他另辟蹊径，取名C4.0算法，后来的进化版为C4.5算法。下⾯我们就来聊下C4.5算法
3. C
4.5算法
3.1 C
4.5对ID3的改进
C4.5改进了上⾯ID3的4个问题，C4.5算法流程具体过程看
1. 对于ID3不能处理连续特征，C4.5的思路是将连续的特征离散化。⽐如m个样本的连续特征A有m个，从⼩到⼤排列为a1,a2,...,a m，则
C4.5取相邻两样本值的平均数，⼀共取得m−1个划分点，其中第i个划分点Ti表⽰为：T i=a i+a i+1
2。对于这m−1个点，分别计算以该
点作为⼆元分类点时的信息增益。选择信息增益最⼤的点作为该连续特征的⼆元离散分类点。⽐如取到的增益最⼤的点为a t，则⼩于a t 的值为类别1，⼤于a t的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后⾯还可以参与⼦节点的产⽣选择过程。
2. 对于ID3的第2个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引⼊⼀的变量I R(X,Y)，它是信息增益和特征熵的⽐
值。
I R(D,A)=I(A,D) H A(D)
3. 对于ID3的第3个缺失值处理的问题，主要需要解决的是两个问题，⼀是在样本某些特征缺失的情况下选择划分的属性，⼆是选定了划
看淡一切的网名
分属性，对于在该属性上缺失特征的样本的处理。
1. 对于第⼀个⼦问题，对于某⼀个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置⼀个权重（初始可以
占地协议都为1），然后划分数据，⼀部分是有特征值A的数据D1，另⼀部分是没有特征A的数据D2。然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值⼀起计算加权重后的信息增益⽐，最后乘上⼀个系数，这个系数是⽆特征A缺失的样本加权后所占加权总样本的⽐例。
2. 对于第⼆个⼦问题，可以将缺失特征的样本同时划分⼊所有的⼦节点，不过将该样本的权重按各个⼦节点样本的数量⽐例来分
配。⽐如缺失特征A的样本a之前权重1，特征A有3个特征值A1,A2,A3。3个特征值对应的⽆缺失A特征的样本个数为2,3,4.a同时划分⼊A1,A2,A3。对应权重调节为2/9,3/9, 4/9。
4. 对于ID3的第4个问题，C4.5引⼊了正则化系数进⾏剪枝。已经在上⼀篇⽂章中讨论过了。
3.2 C
4.5的不⾜
C4.5虽然改进或者改善了ID3算法的⼏个主要的问题，仍然有优化的空间。
1. 由于决策树算法⾮常容易过拟合，因此对于⽣成的决策树必须要进⾏剪枝。C4.5的剪枝⽅法是PEP 。PEP 的准确度⽐较⾼，但是依旧会存在以下的问题：婴儿急疹
1. PEP 算法实⽤的从从上⽽下的剪枝策略，这种剪枝会导致和预剪枝同样的问题，造成剪枝过度。
2. PEP 剪枝会出现剪枝失败的情况。
2. C4.5⽣成的是多叉树，即⼀个⽗节点可以有多个节点。很多时候，在计算机中⼆叉树模型会⽐多叉树运算效率⾼。如果采⽤⼆叉树，可以提⾼效率。
不忘初心的名言3. C
4.5只能⽤于分类，如果能将决策树⽤于回归的话可以扩⼤它的使⽤范围。
4. C4.5由于使⽤了熵模型，⾥⾯有⼤量的耗时的对数运算，如果是连续值还有⼤量的排序运算。如果能够加以模型简化可以减少运算强度但⼜不牺牲太多准确性的话，那就更好了。
4. CART 算法
4.1 CART 对C4.5的改进
大虾热量CART 算法在C4.5的基础上，对于C4.5中的出现的问题进⾏了改进。针对上⾯提到的C4.5中出现的4点问题，进⾏如下改进：
1. CART 使⽤了，对C4.5的剪枝⽅法进⾏了优化。
2. 针对C4.5的多叉树的问题，CART 改成了⼆叉树。CART 采⽤的是不停的⼆分，举个例⼦，CART 分类树会考虑把A 分成{A 1}和{A 2,A 3},{A 2}和{A 1,A 3},{A 3}和{A 1,A 2}三种情况，找到基尼系数最⼩的组合，⽐如{A 2}和{A 1,A 3}，然后建⽴⼆叉树节点，⼀个节点是{A 2}对应的样本，另⼀个节点是{A 1,A 3}对应的节点。同时，由于这次没有把特征A 的取值完全分开，后⾯我们还有机会在⼦节点继续选择到特征A 来划分{A 1}和{A 3}。这和ID3或者C4.5不同，在ID3或者C4.5的⼀棵⼦树中，离散特征只会参与⼀次节点的建⽴，⽽CART 中的离散特征会参与多次节点建⽴。
3. CART 可以分为CART 分类树和CART 回归树。CART 分类树和CART 回归树的算法⼤致相同，主要区别有下⾯两点：
1. 连续值的处理⽅法不同。
1. CART 分类树采⽤的是⽤基尼系数的⼤⼩来度量特征的各个划分点的优劣情况
2. CART 回归树的度量⽬标是，对于任意划分特征A ，对应的任意划分点s 两边划分成的数据集D1和D2，求出使D1和D2各⾃情感诉求
集合的均⽅差最⼩，同时D1和D2的均⽅差之和最⼩所对应的特征和特征值划分点。表达式为：
min A ,s min c 1∑x i ∈D 1(A ,s )(y i −c 1)2+min c 2∑x i ∈D 2(A ,s )(y i −c 2)22. 决策树建⽴后做预测的⽅式不同。
1. CART 分类树采⽤叶⼦节点⾥概率最⼤的类别作为当前节点的预测类别。
2. CART 回归树输出不是类别，它采⽤的是⽤最终叶⼦的均值或者中位数来预测输出结果。
4. CART 分类树使⽤了使⽤的是基尼系数的度量⽅式
CART 算法相⽐C4.5算法的分类⽅法，采⽤了简化的⼆叉树模型，同时特征选择采⽤了近似的基尼系数来简化计算。当然CART 树最⼤的好处是还可以做回归模型，这个C4.5没有。
4.2 CART 的不⾜
1. 应该⼤家有注意到，⽆论是ID3, C4.5还是CART，在做特征选择的时候都是选择最优的⼀个特征来做分类决策，但是⼤多数，分类决策不应该是由某⼀个特征决定的，⽽是应该由⼀组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某⼀个最优特征，⽽是选择最优的⼀个特征线性组合来做决策。这个算法的代表是OC1，这⾥不多介绍。
2. 如果样本发⽣⼀点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习⾥⾯的随机森林之类的⽅法解决。[]
Processing math: 100%
