本文参考: <<统计学习方法>>
决策树算法时很多优秀的集成算法的基础,包括RF,GBDT,提升树(Boosting Tree)等
说明
- 决策树(DT)是一种基本的分类和回归方法
- 分类问题中可以理解为if-then规则的集合
- 分类问题中也可以理解为定义在特征空间->类空间上的条件概率分布
- 分类问题中使用的是ID3和C4.5
- ID3 基于 最大化信息增益 来选择特征
- C4.5基于 最大化信息增益比 来选择特征
- 回归问题使用的是分类与回归树(Classification And Regression Tree, CART)
- 分类树: 基于 最小化基尼(Gini Index)指数 来选择特征
- 回归树: 基于 最小化平方误差 来选择特征
- 关于树模型的复杂度可以用下面的方式评估, 统计学习方法中CART选择使用树的节点总数来评估树的复杂度
- 叶子节点的数量
- 节点总数
- 树的深度
树模型的优缺点
优点
- 可解释性强
- 可处理混合类型特征(?)
- 具体伸缩不变性(不用归一化特征,LR模型需要归一化特征)
- 有特征组合的作用
- 可自然地处理缺失值(神经网络不能处理缺失值)
- 对异常点鲁棒
- 有特征选择作用
- 可扩展性强，容易并行
缺点
- 缺乏平滑性(回归预测时输出值只能 输出有限的若干种数值)
- 不适合处理高维稀疏数据
- 数据稀疏时
- 比如某个数据集有10000个样本
- 某个特征只有10个样本存在值，其他样本都不存在值
- 决策树：
- 这样的话树容易将当前特征选中作为分类特征，这种划分可能在训练集上看起来很好，但测试集中表现可能不太好(这里不是简单的缺失值，而是数据很稀疏，这里需要进一步的理解[待更新])
- LR等线性模型：
- 因为现在的模型普遍都会带着正则项，而LR等线性模型的正则项是对权重的惩罚，也就是特征对应的权重一旦过大，惩罚就会很大，进一步压缩权重的值，使他不至于过大，而树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种 case，树只需要一个节点就可以完美分割9990和10个样本，惩罚项极其之小.
- 数据稀疏时
决策树训练的三个步骤
特征选择
信息增益
- 对数据集D的经验熵:\(H(D)=-\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log_{2}\frac{|C_{k}|}{|D|}\)
- 对特征A对数据集D的经验条件熵:\(H(D|A)=\sum_{n=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i})=-\sum_{n=1}^{n}\frac{|D_{i}|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}log_{2}\frac{|D_{ik}|}{|D_{i}|}\), n为特征A的取值个数
信息增益比
- 特征A对训练数据D的信息增益比:\(g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)}\)
- 其中\(H_{A}=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}\), n为特征A的取值个数
基尼指数
- 对于分布\(p=(p_{1},…,p_{k})\)的基尼指数:\(Gini(p)=\sum_{k=1}^{K}p_{k}(1-p_{k})=1-\sum_{k=1}^{K}p_{k}^{2}\)
- 对样本集合D,基尼指数为:\(Gini(p)=1-\sum_{k=1}^{K}\left(\frac{|C_{k}|}{|D|}\right)^{2}\)
- 在特征A的条件下,集合D的基尼指数:\(Gini(D,A)=\frac{|C_{1}|}{|D|}Gini(D_{1})+\frac{|C_{2}|}{|D|}Gini(D_{2})\)
- 我们将集合D根据特征A分为两类:
- 是否取特征A的某个值,其中\(A=a\)的是\(D_{1}\),\(A\neq a\)的是\(D_{2}\)
决策树的生成
ID3
- 基于最大化信息增益来选择特征
- 选取所有信息增益最大的特征作为当前结点的特征
- 对取值数目较多的属性有所偏好
- 只有分类树,没有回归树
- ID3相当于用极大似然法对模型进行选择(问题:如何理解?)
C4.5
- 基于最大化信息增益比来选择特征
- 选取信息增益比最大的特征作为当前结点的特征
- 由于使用最大的信息增益比特征可能对取值数目少的特征属性有所偏好,所以C4.5算法一般不会直接选信息增益比最大的,而是
- 先从候选区属性中找出信息增益高于平均水平的
- 再从筛选结果中寻找信息增益比最大的
- 由于使用最大的信息增益比特征可能对取值数目少的特征属性有所偏好,所以C4.5算法一般不会直接选信息增益比最大的,而是
- 处理连续型特征时使用二分法(bi-partition)
- 只有分类树,没有回归树
CART
- CART的决策树是二叉树
- 分类树: 基于最小化基尼指数来选择特征
- 输出变量为离散变量
- 基于基尼指数选取所有可能的特征A和所有可能的切分点a中,选择基尼指数最小的特征和切分点为最优特征和最优且分点
- 回归树: 基于最小化平方误差来选择特征
- CART回归树一般称为最小二乘回归树(因为目标函数的优化是最小化误差的平方和实现的)
- 输出变量为连续变量
- 选取时选择最优划分变量(特征)j和最优切分点s,然后按照变量j的划分点s将结点分为两个结点,大于s的为第一个结点,小于s的为第二个结点
- 一点说明:
- *<<统计学习方法>>*中:
- 回归树的特征默认是连续变量,选取划分点s时使用的是连续变量的各种中间值作为候选值,大于s的分为一个结点,小于s的分为一个结点
- 分类树的特征默认是离散变量,选取划分点a时使用的是离散变量的值作为候选值,等于a的分为一个结点,不等于a的分为另一个结点
- 但是实际上无论时分类树还是回归树,CART都可以用相同手段处理连续值
- *<<统计学习方法>>*中:
剪枝
- 剪枝的核心思想:
- 就是加入考虑树的复杂度考量(决策树的生成时仅仅是考虑到信息增益和信息增益比,没有考量树的复杂度)
- 树的深度越深,树越复杂
- 整体上再考虑树变得更简单的同时保证分类误差较小
- 就是加入考虑树的复杂度考量(决策树的生成时仅仅是考虑到信息增益和信息增益比,没有考量树的复杂度)
预剪枝
- 预剪枝发生在决策树生成过程中
- 在每个节点划分前先进行估计
- 若当前节点划分不能带来决策树准确率提升,则停止划分
- 在<<统计学习方法>>中未提到这个方法,只讲了一种简单的后剪枝算法
- 时间复杂度小,欠拟合风险大
后剪枝
- 后剪枝发生在决策树生成后
- 自底向上的对非叶子节点进行考察(注意千万不可从根节点开始自顶向下的剪枝,可能失去整体最优的决策树)
- 若将该节点换成叶子节点能带来决策树准确率提升,则将该节点替换为叶子节点
- 时间复杂度大,欠拟合风险小
常见的后剪枝方法
各种方法各有优劣,关注不同的优化角度
- REP 错误率降低剪枝(Reduced Error Pruning)
- PEP 悲观剪枝(Pessimistic Error Pruning)
- CCP 代价复杂度剪枝(Cost Complexity Pruning), 详细过程参考CPP剪枝算法描述
- MEP 最小误差剪枝(Minimum Error Pruning)
- CVP (Critical Value Pruning)
- OPP (Optimal Pruning)
ID3和C4.5的剪枝
CART的剪枝
CART使用的是CCP剪枝
- 对任意的子树,我们可以定义子树的损失
- \(C_{a}(T)=C(T)+\alpha|T|\)
- 子树的损失 = 子树的预测误差 + \(\alpha\) * 子树的节点数
- 对于回归树和分类树,子树的预测误差定义不一样,前者是误差的平方和,后者是基尼指数
- 可以证明对于给定的Alpha,一定存在某个损失最小的子树,也就是我们要的最优子树
- 现实中实现时可以使用递归的方法实现
CCP剪枝算法描述
CPP剪枝也是一种后剪枝算法
修正：统计学习方法CART算法第六步中应该跳到第二步，而不是第三步
- 1：计算所有节点对应的\(\alpha\)值: \(\alpha=\frac{C(t)-C(T_{t})}{|T_{t}|-1}\)
- \(C(t)\)是以t节点单一节点为树时单一节点树的损失函数
- \(C(T_{t})\)是以t节点为根节点的子树时整棵子树的损失函数
- \(|T_{t}|\)是以t节点为根节点的子树时整棵子树的节点数量
- 2：对当前\(\alpha\)值最小的节点t剪枝，并存储中间结果的\(\alpha\)值和剪枝后的树结构
- 当\(\alpha\)确定时，存在唯一的最小子树\(T_{\alpha}\)使损失函数\(C_{\alpha}(T)\)最小
- 3：选取当前树为剪枝后的树，跳转到第1步，直到剪枝到只有三个节点的树时截止
- 4：截止后得到节点数量从大到小的多个子树\(T_{\alpha_{0}}, T_{\alpha_{1}},…,T_{\alpha_{n}}\). (其中\(T_{\alpha_{i}}\)也就对应着第i个\(\alpha\)值\(\alpha_{i}\))
- 5：用交叉验证法对\(\alpha\)的值进行选择(CART算法执行时\(\alpha\)类似超参数，整个算法学习的过程类似于用交叉验证法确定超参数的过程，\(\alpha\)的值确定了，对应的决策树也就确定了！)
关于连续特征
统计学习方法
- 在<<统计学习方法>>中回归树的特征默认是连续变量,分类树的特征默认是离散变量
机器学习 周志华
- 在<<机器学习>>中提到连续特征的一种解决方案:
- 把该连续特征所有出现的取值排序
- 取临近两两之间的平均值作为划分点
- 像处理离散的点一样,使用信息增益最大化,信息增益率最大化,或者是基尼指数最小化实现对应的划分选择
个人总结
- 处理连续型变量(特征的能力)
- ID3 不能处理连续型特征
- 因为连续型特征往往使得每一个样本该特征取值都不一样,造成该特征对数据集D的经验条件熵为0?
- 使得ID3算法趋向于选择这个特征?
- C4.5 能处理连续型特征
- 将数据排序后找到类别不同的分割线作为切分点
- 根据切分点把连续属性二分类装换为布尔类型
- 可多次使用连续属性分类
- CART 能处理连续型特征
- 实际对连续型特征的处理与C4.5一样
- 由于CART树构建时每次都会对特征进行二值化分,所以可以很好的适用与连续型变量
- ID3 不能处理连续型特征
一些总结
- 算法ID3生成可能是多叉树,而CART一定是二叉树，*<<统计学习方法>>*中二者生成相同的数是巧合，除了不同评价方式的特征选择结果一样以外，还需要被选中的特征都是二值的！
- ID3相当于用极大似然法对模型进行选择
一种很好的理解思路
ID3
- ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点
ID3的缺点:
- ID3不能处理连续特征
- ID3对取值较多的特征有着偏好在相同条件下，取值比较多的特征比取值少的特征信息增益大
- ID3不能处理缺失值
- 没有考虑过拟合的问题(问题: ID3没有剪枝吗?)
C4.5
- C4.5可以看成是对ID3进行改进
C4.5对ID3的改进
对于ID3不能处理连续特征，C4.5的思路是将连续的特征离散化.
- 样本(m个样本)按照特征的取值排列后取相邻样本的平均值作为划分点(m-1个划分点),分别计算以每个划分点作为二元分类时的信息增益. 最终选择信息增益高的(问题:这里是C4.5,为什么不是使用信息增益比而是信息增益来作为区分?)
- C4.5选择连续特征作为分类特征时,只分两类,但是后面(其他层结点)可以使用该特征分类,也就是说连续特征在C4.5中可以多次使用,但每次只分为两部分
对于ID3信息增益最大指标会造成偏向于取值较多的特征的问题. C4.5使用信息增益比来解决问题
对于ID3不能处理缺失值的问题,C4.5主要解决两个问题
- 1) 如何在属性值缺失条件下进行属性选择
- 没有缺失值的属性,正常处理
- 每个属性A有缺失值:
- 对该特征进行划分时仅仅考虑在属性A上没有缺失的部分数据,有缺失的数据不考虑.
- 无缺失的数据计算收益时需要乘以一个权重(无缺失的样本总数/样本总数)
- 相当于信息增益适当缩小
- 2) 给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分
- 在A属性没有缺失值的样本,正常划分
- 在A属性有缺失值的样本:
- 给每个样本引入权重,初始值都为1
- 同一个样本按照不同概率划入到不同的结点(当前叶节点)中去(概率是当前结点中样本数量/无缺失样本总数)
- 1) 如何在属性值缺失条件下进行属性选择
对于没有考虑过拟合的问题:
- C4.5引入了正则化系数剪枝(问题: ID3没有剪枝吗?)
C4.5的缺点
- [这个问题存疑,没有任何书籍显示C4.5的剪枝策略是PEP,<<统计学习方法>>中只是简单的介绍了后剪枝]C4.5的剪枝方法时PEP,PEP准确度高,但是存在下面两个子问题:
- 1) PEP使用由上而下的剪枝策略,会导致与预先剪枝相同的问题,造成过度剪枝
- 2) 会造成剪枝失败的情况
- C4.5生成多叉树,计算机中很多时候多叉树运算效率不如二叉树来的高
- C4.5只能用于分类
- C4.5需要进行大量的对数运算(计算熵)
CART
- 可以理解为对C4.5进一步的改进
CART对C4.5的改进
- CART使用CPP代价复杂度剪枝算法
- 详细过程参考CCP剪枝算法描述
- CART使用二叉树只生成二叉树,即使是离散特征
- CART对连续特征的处理与C4.5完全相同
- CART对离散特征也是二分类且也是可以多次使用同一特征(ID3与C4.5中离散特征只能使用一次,且是多分叉)
- 所以CART是一颗二叉树
- CART可有分类树和回归树两种
- 回归树的目标函数的优化是: 最小化误差的平方和
- 分类树以概率最大的类别作为叶节点的类别
- 回归树以中位数或者均值作为预测结果
- CART使用基尼指数作为结点混乱度的度量指标
- 避免了对数计算(与熵比较)
ID3,C4.5,CART的缺点
- 每次之全责一个最优特征作为分类决策,而实际中其实可能需要多个特征一起决策
- 解决方案: 多变量决策树(每次选择多个特征一起决策)
- 单个特征决策可以看成是直线
- 多个特征决策可以看成是斜线
- 解决方案: 多变量决策树(每次选择多个特征一起决策)
- 样本改变一点点都会造成树的结构改变很大
- 解决方案: 随机森林等集成学习方法