https://zhuanlan.zhihu.com/p/158633779?utm_source=wechat_session&utm_medium=social&utm_oi=54629349982208
什么是决策树呢？决策树是一种监督学习方法，既可以用来处理分类问题也可以处理回归问题。
决策树的学习过程包括：特征选择、决策树生成、决策树剪枝 。
1.1 ID3算法
ID3使用信息增益作为特征选择的度量，使用自顶向下的贪心算法遍历决策树空间。具体的：
- 计算数据集合的信息熵，以及各个特征的条件熵。选择信息增益最大的作为本次划分节点。
- 删除上一步使用的特征，更新各个分支的数据集和特征集。
- 重复1，2步，知道子集包含单一特征，则为分支叶结点。
ID3使用信息增益作为特征选择的度量。那么什么是信息增益呢？信息增益表示得知特征 A 的信息而使得样本集合不确定性减少的程度。
信息增益 = 信息熵 - 条件熵：
如果信息增益越大，那么就是指分完之后的信息熵越小，那也就意味着分完之后的数据趋向于有序，而越有序的数据，意味着我们能更好地预测数据。
ID3优缺点
- ID3算法没有进行决策树剪枝，容易发生过拟合
- ID3算法没有给出处理连续数据的方法，只能处理离散特征
- ID3算法不能处理带有缺失值的数据集,需对数据集中的缺失值进行预处理
- 信息增益准则对可取值数目较多的特征有所偏好(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)
1.2 C4.5算法
C4.5主要是克服ID3使用信息增益进行特征划分对取值数据较多特征有偏好的缺点。使用信息增益率进行特征划分。
C4.5相比ID3进行的改进有如下4点：
- 引入剪枝策略，使用悲观剪枝策略进行后剪枝
- 使用信息增益率代替信息增益，作为特征划分标准
- 连续特征离散化
- 需要处理的样本或样本子集按照连续变量的大小从小到大进行排序
- 假设该属性对应的不同的属性值一共有N个,那么总共有N?1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成两类
- 缺失值处理
- 对于具有缺失值的特征，用没有缺失的样本子集所占比重来折算信息增益率，选择划分特征
- 选定该划分特征，对于缺失该特征值的样本，将样本以不同的概率划分到不同子节点
使用信息增益率，信息增益率表示如下：
Ha(D) 称为特a征 A 的固有值。
决策树剪枝的目的是为了防止过拟合。
C4.5采用后剪枝对决策树进行剪枝。具体方法为：
在决策树构造完成后，自底向上对非叶节点进行评估，如果将其换成叶节点能提升泛化性能，则将该子树换成叶节点。后剪枝决策树欠拟合风险很小，泛化性能往往优于预剪枝决策树。但训练时间会大很多。
C4.5优缺点
- C4.5只能用于分类
- C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。
- 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，算法低效。
1.3 CART算法
相比ID3和C4.5算法，CART算法使用二叉树简化决策树规模，提高生成决策树效率。
CART树在C4.5基础上进行了如下改进：
- CART使用二叉树来代替C4.5的多叉树，提高了生成决策树效率
- C4.5只能用于分类，CART树可用于分类和回归
- CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算
- CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中
- CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法
- ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征