决策树算法算是一个很经典的算法了,既可以分类,也可以做回归,同时适合集成学习。
什么是决策树
一种对样本进行分类的树型结构,也可把它看成if-then
规则的集合。
树中的内部节点代表一个属性,该节点引出的分支表示这个属性的全部取值,叶节点表示最终的分类结果。从根节点到叶节点的每条路径便构成if-then
的一条规则,且具有互斥且完备的性质,即每一个样本均被且只被一条路径覆盖。
如何学习得到一颗决策树
决策树学习本质上是从训练数据上归纳出一种分类规则,使它与训练数据矛盾较小(即能对训练数据正确分类)的同时具有良好的泛化能力。(模型讲完,接下来就是策略与算法)
决策树学习的策略是以损失函数(通常是正则化的极大似然函数)为目标函数的最小化(同其他机器学习模型一致,区别就在于如何优化)。算法则采用启发式算法来近似求解最优化问题,主要分为三步:
- 特征选择
- 模型生成
- 决策树剪枝
具体讲解这三个步骤
决策树学习的算法是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使分割后的各个子集有一个最好分类的过程。这一过程就是划分特征空间,构建决策树的过程。
【如何选择最优特征】
直观上,如果一个特征具有更好的分类能力,即分割后各个子集中的样本尽可能属于同一类别,那么就更应该选择这个特征。特征分类能力的衡量有信息增益(ID3)
、信息增益比(C4.5)
、基尼系数(CART)
。
【对信息增益、信息增益比、基尼系数的了解】
1. 信息增益
由熵
引申而来。熵是表示随机变量不确定性(无序性)的度量,熵越大,随机变量的不确定性也越大。对于同一枚硬币,当抛正面、抛反面概率相等(概率分布为均匀分布)的情况下,此时不确性定最大,熵也最大。对有相同概率分布的不同随机变量来说,取值越多的随机变量熵越大。
随机变量$X$的熵的表达式如下:
其中n表示X的n种不同取值,而$p_i$表示X取值为i的概率。
而条件熵
是指在已知随机变量$X$的情况下,随机变量$Y$剩下的不确定性。计算方式为:经过X分割过后,各个分支节点的信息熵乘以一个权重的加权求和。这个权重是为了考虑到不同的分支节点所包含的样本数不同,具体公式为:
信息增益
表示的是:得知特征X的信息而使得分类Y信息的不确定性减少的程度。某个特征的信息增益比较大,就表示该特征分类能力也越大。特征A对数据集D的信息增益为:
2. 信息增益比
用信息增益
选择最优划分特征有一个问题:偏向于选择取值较多的特征,这就导致训练出来的树非常宽且深度不深,容易过拟合。所以这里我们使用信息增益比
,即把信息增益除以训练集$D$关于特征$A$的熵,公式表示为:
3. 基尼系数
无论是信息增益
还是增益率
都涉及到大量的对数运算,为了简化模型与运算量,我们使用基尼系数
作为替代。基尼系数表示模型的不纯度,基尼系数越小,则不纯度越低,特征的分类效果就越好。
假设样本$D$有K个类别,第K个类别的概率为$p_k$,则样本$D$的基尼系数为:
特别的,对于样本$D$,如果根据特征$A$的某个值a,把$D$分成$D1$和$D2$两部分,则在特征$A$的条件下,$D$的基尼系数表达式为:
【递归的终止条件是什么】
主要有3个终止条件:
- 当前训练子集被正确分类,即全属于同一类别,无需划分
- 可用特征为空,即特征全部用完
- 可用特征的信息增益或增益率小于某个阈值$\epsilon$
【为什么要剪枝,如何剪枝】
为防止过拟合,要把过于复杂的树进行剪枝,进行简化。剪枝以极小化决策树整体的损失函数来实现。要注意的是:决策树的生成是学习局部的模型,而决策树剪枝是学习整体的模型。
损失函数如下:
其中,$|T|$ 是树$T$ 的叶节点个数,$t$ 是其中一个叶节点,$N_t$ 是这个叶节点的样本个数,$H_t(T)$ 是这个叶节点的熵,$α|T|$ 表示对模型复杂度的惩罚项(正则化)。
我们再仔细看一看这个损失函数,$C(T)$ 不就是以熵来表示各个叶节点的分类误差(如果某叶节点下的样本属于同一类,那么效果最佳,熵为0),并把所有叶节点的误差相加来表示模型对训练样本的预测误差。
一般剪枝算法
给定一个$\alpha$ 后,通过不断剪枝来减小模型的整体损失。具体为:
- 计算每个节点的熵
- 递归地从叶节点向上回缩:假设一叶节点在回缩到父节点之前的损失函数值$>=$ 回缩之后的损失函数值,则该剪,即父节点变成新的叶节点
常用的 ID3/C4.5/CART 算法区别在哪里
【ID3】
- 使用
信息增益
选择最优划分特征,但会遇到问题:通常取值较多的特征信息增益大 - 未考虑过拟合问题,即没有剪枝
- 无法处理连续特征,大大限制的ID3的用途
- 没有考虑到数据缺失的情况
【C4.5】
C4.5算法在ID3的基础上改进了上述4个问题。
改进一:使用信息增益比
替代信息增益
。
改进二:引入了正则化系数进行初步的剪枝,防止过拟合
改进三:处理连续特征
解决思路是连续特征离散化,同时使用二分法。对特征$A$的m个不同取值从小到大排序为$a_1,a_2,…,a_m$, 不妨取每两个相邻节点的均值$T_i=\frac{a_i+a_{i+1}}{2}$作为划分点。对于这(m-1)个点,可像离散属性一样选取最优划分点。注意:若当前节点为连续属性,该属性还可参与后续的子节点产生过程。如先划分属性$A<=10$ ,后续还可继续划分属性$A<=5$。
改进四:处理缺失数据
这里需要解决两个问题:
- 如何在特征缺失的情况下选择划分属性
- 选定了划分属性之后,如何对样本进行划分
对于问题1,我们对在特征$A$ 上无缺失值的样本计算$A$ 特征对应的信息增益比,最后再乘以一个系数,这个系数是特征$A$ 无缺失的样本所占的比例。
对于问题2,将缺失特征的样本同时划入所有子节点,不过要乘以各个子节点所划入无缺失样本的比例。比如,特征A有3个特征值A1,A2,A3。3个特征值对应的无缺失A特征的样本个数为2,3,4。则缺失特征A的样本a同时划分入A1,A2,A3。对应权重调节为2/9,3/9, 4/9。
C4.5不足的地方:
- 使用了熵模型,涉及到大量的对数与排序运算,运算强度高
- 生成的是多叉树。若采用二叉树,可提高计算机运算效率
- 只能用于分类
- 剪枝算法有优化空间
【CART】
CART算法对C4.5算法的不足做出了改进。主要有CART分类树与CART回归树,下面先讲解分类树。
1. CART分类树的最优特征选择
使用基尼系数
选择最优特征,二次运算比对数运算简单的多
2. CART分类树对于离散特征处理的改进
对离散特征进行二分。如特征$A$有$a1,a2,a3$ 三种类别,ID3
与C4.5
的做法是建立一个三叉的节点,生成的多叉树。而CART
会考虑把$A$分成$\{a1\}$和$\{a2,a3\}$,$\{a2\}$和$\{a1,a3\}$ ,$\{a3\}$和$\{a1,a2\}$这三种情况,找基尼系数
最小的组合,比如$\{a1\}$和$\{a2,a3\}$,然后建立二叉树,后续还有机会在子节点上继续选择特征$A$划分$\{a2,a3\}$。
3. CART回归树
相比于CART分类树,不同的地方是:
最优特征选择与连续值处理方式不同。对于回归模型,使用平方误差的度量方式,寻找最优特征A与最优切分点s,使得切分过后的数据集D1与D2各自均方差最小,且D1与D2的均方差之和最小,具体为:
其中c1为D1数据集的样本输出均值,c2为D2数据集的样本输出均值。
最后预测方式不同。分类树是以叶节点里概率最大的类别作为预测类别,而回归树输出的是一个值,采用最终叶节点的均值来预测输出结果。
4. CART树算法的剪枝
相比与一般剪枝,其优势在于不用一开始确定$\alpha$值,而是在剪枝的同时找到最优$\alpha$值。剪枝过程主要分两步:
- 从原始决策树$T_0$底端开始不断剪枝,直到$T_0$的根节点,形成以子树序列$\{T_0,T_1,…,T_n\}$
- 通过在独立的验证集上进行交叉验证,从中选出最优子树(同时$\alpha$也是确定下来的)
剪枝思路
【三类算法小结】
算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 |
---|---|---|---|---|---|
ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 |
C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 |
CART | 分类,回归 | 二叉树 | 基尼系数,均方差 | 支持 | 支持 |
决策树算法小结
不纠结于ID3,C4.5还是CART,从整体上看决策树算法
【优点】
- 不用数据预处理,不用数据归一化,可以处理缺失数据
- 可同时处理离散型特征与连续性特征(许多算法两者并不能兼得)
- 决策树很直观,逻辑上好解释
【缺点】
- 容易过拟合,通常要设置节点最小样本数、限决策树深度来改进
- 启发式算法容易陷入局部最优,可通过集成方法改善
- 复杂的关系,决策树较难学习