序

其实不同的决策树学习算法只是它们选择特征的依据不同，决策树的生成过程都是一样的（根据当前环境对特征进行贪婪的选择）。

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，每一次都选择使得信息增益最大的特征进行分裂，递归地构建决策树。
ID3算法以信息增益作为划分训练数据集的特征，有一个致命的缺点。选择取值比较多的特征往往会具有较大的信息增益，所以ID3偏向于选择取值较多的特征。

针对ID3算法的不足，C4.5算法根据信息增益比来选择特征，对这一问题进行了校正。

CART指的是分类回归树，它既可以用来分类，又可以被用来进行回归。CART用作回归树时用平方误差最小化作为选择特征的准则，用作分类树时采用基尼指数最小化原则，进行特征选择，递归地生成二叉树。

ID3

1. 算法思想
   ID3根据具有最高信息增益的属性作为分割点
   算法核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树，具体方法是：从根节点出发，对节点计算所有可能的信息增益，选择信息增益最大的特征最为节点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树直到所有特征的信息增益均很小或者没有特征可以选择为止。

2. 创建树
   创建根节点R
   如果当前dataset中的数据都是同一类，则标记R的类别应该为该类
   如果当前featurelist集合为空，则标记R的类别应为当前dataset中样本最多的类别。
   递归--->
   ---------从featurelist中选择属性F（选择gain（dataset，F）最大的属性）
   ---------根据F的每一个值v，将dataset划分为不同的子集DS，对于每一个DS：
   -----------------创建根节点C
   -----------------如果DS为空，节点C标记为dataset中样本数最多的类别
   -----------------如果DS不为空，节点C = ID3（DS，featurelist-F）
   -----------------将节点C添加为R的子节点

3. 缺点
   ID3只进行决策树的生成，没有剪枝，因此容易过拟合。

C4.5

其基本思想与ID3类似，此处重点看一下其新特性。

1. 特点
   使用信息增益率
   可以处理连续值
   处理缺失值
   基于后剪枝

2. 优点
   产生的分类规则易于理解
   准确率较高

3. 缺点
   构造树的过程中需要多次对数据集进行扫描以及排序，因此算法效率较低。

4. 处理连续值方法：
   对应子树中的连续值特征先进行排序，从大到小，计算两两之间的均值作为呆分割点，然后再使用信息增益率判断哪个点分割后的增益率最大。

上述计算连续变量的信息增益率的方法较为耗时，下面的例子是另一种提高效率的方法：

CART树

1. 算法思想
   cart树既可以分类又可以回归，是在给定输入X的条件下输出随机变量Y的条件概率分布的学习方法。

回归时使用误差平方和进行特征选择；
---创建回归树时，使用最小误差平方和来决定回归树的最优划分，该划分准则是期望划分之后的子树误差方差最小

分类时根据基尼指数进行特征选择。
---分类树递归创建时，是选择当前数据集中具有最小基尼指数的特征作为节点划分来构建决策树

cart树使用后剪枝来降低过拟合风险。

CART算法采用一种二分递归分割的技术，算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树。因此CART算法适用于样本特征的取值为是或非的场景，对于连续特征的处理则与C4.5算法相似。

2. 特点
   二元划分，使得二叉树不易产生数据碎片，精度往往较高
   连续值特征使用最小平方残差，最小绝对残差
   分类属性特征使用gini指数

3. 基尼指数

   
   
   
   

   gini越小，代表样本纯度越高

4. 基尼增益
   衡量出某个属性（特征）的全部取值的gini指数就可以得到分割点：i 表示特征的第 i 个取值。

   
   
   
   

   在二分切割下（i=1,2），根据训练集N中的属性F将N划分为N1 N2，因此gini增益可表示为：

   
   

5. 分类树的学习过程
   针对属性A，分类后的基尼指数是：
   

   
   每次讲样本集合划分为两类，即每个中间节点产生两个分支，如果特征属性个数>2，即n>2时，这时我们就需要一个阈值（划分次数），将D分割为D1 D2，不同的得到不同的D1 D2，重新设定D1样本数为L，D2样本数为R，因此L+R=D，上式求和符号铺展后可改写为：
   
   
   根代入Gini计算公式：
   
   
   因为我们要求解基尼指数最小值作为最佳分类点，对上式求极小也就是对下式求最大：
   
   
   上面就是整个分类树的学习过程。

6. 回归树
   使用均方误差来代替熵的计算：N代表D集合的样本数量，和分别为第个样本的输出值和预测值：
   

   
   如果使用样本的输出值的均值来代替样本的预测值，则上式可写为：
   
   
   如果在某个节点上，根据某一特征属性A，将集合D划分为s个部分，则划分后的均方误差为下式，其中代表样本子集，是样本子集样本个数。
   
   
   上式与上上式子相减，即为划分为s个部分后的误差减少了：
   
   
   如果仅考虑二叉树的情况，即每个节点只有两个分支，此时S=2，基于特征属性A，集合D被阈值划分为D1 D2两个集合，每个集合的样本个数为L和R，那么：其实在cart回归树中，基本都是二叉树，因此只考虑s=2的情况：
   
   
   将LS（D）计算公式代入上式：
   
   
   上式中，是样本集合D的label，和分别是D1和D2的样本label，求上式的最大值，即求下式的最大：
   

转载注明：https://www.jianshu.com/p/e1f915f6cfcd