常见决策树
模型 | ID3 | C4.5 | CART |
---|---|---|---|
结构 | 多叉树 | 多叉树 | 二叉树 |
特征选择 | 信息增益 | 信息增益率 | Gini系数/均方差 |
连续值处理 | 不支持 | 支持 | 支持 |
缺失值处理 | 不支持 | 支持 | 支持 |
枝剪 | 不支持 | 支持 | 支持 |
简述决策树构建过程
- 构建根节点,将所有训练数据都放在根节点
- 选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类
- 如果子集非空,或子集容量未小于最少数量,递归1,2步骤,直到所有训练数据子集都被正确分类或没有合适的特征为止
详述信息熵计算方法及存在问题
其中,D为数据全集,C为不同因变量类别k上的子集(传统意义上的y的种类)详述信息增益计算方法
条件信息熵:在特征A给定的条件下对数据集D分类的不确定性:
信息增益:知道特征A的信息而使类D的信息的不确定减少的程度(对称):I(D,A) = H(D)-H(D/A)
简而言之,就是在特征A下找到最合适的切分,使得在该切分下信息量的变换最大,更加稳定;但是这个有一个问题,对于类别天生较多的特征,模型更容易选中,因为特征类别较多,切分后的信息增益天生更大,更容易满足我们的原始假设详述信息增益率计算方法
在信息增益计算的基础不变的情况下得到的:I(D,A) = H(D)-H(D/A),同时还考虑了,用划分的子集数上的熵来平衡了分类数过多的问题。
信息增益率:解释Gini系数
Gini系数二分情况下:
对于决策树样本D来说,
对于样本D,如果根据特征A的某个值,把D分成D1和D2,则在特征A的条件下,D的基尼系数为:ID3存在的问题
缺点:
- 存在偏向于选择取值较多的特征问题
- 连续值不支持
- 缺失值不支持
-
C4.5相对于ID3的改进点
主动进行的连续的特征离散化
- 比如m个样本的连续特征A有m个,先set在order,再两两组合求中间值,以该值点作为划分的待选点
- 连续特征可以再后序特征划分中仍可继续参与计算
- 缺失问题优化
- 训练:用所有未缺失的样本,和之前一样,计算每个属性的信息增益,但是这里的信息增益需要乘以一个系数(未缺失样本/总样本)
- 预测:直接跳过该节点,并将此样本划入所有子节点,划分后乘以系数计算,系数为不缺失部分的样本分布
-
CART的连续特征改进点
分类情况下的变量特征选择
- 离散变量:二分划分
- 连续变量:和C4.5一致,如果当前节点为连续属性,则该属性后面依旧可以参与子节点的产生选择过程
-
CART分类树建立算法的具体流程
我们的算法从根节点开始,用训练集递归的建立CART树。
对于当前节点的数据集为D,如果样本个数小于阈值或者没有特征,则返回决策子树,当前节点停止递归
- 计算样本集D的基尼系数,如果基尼系数小于阈值,则返回决策树子树,当前节点停止递归
- 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数
- 在计算出来的各个特征的各个特征值对数据集D的基尼系数中,选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值,把数据集划分成两部分D1和D2,同时建立当前节点的左右节点,做节点的数据集D为D1,右节点的数据集D为D2
-
CART回归树建立算法的具体流程
其他部分都一样,在构建过程中遇到连续值的话,并不是利用C4.5中的中间值基尼系数的方式,而是采取了最小方差方法:
对于任意划分特征A,对应的任意划分点s两边划分成的数据集D1和D2,求出使D1和D2各自集合的均方差最小,同时D1和D2的均方差之和最小所对应的特征和特征值划分点,其中c1为D1的均值,c2为D2的均值:CART输出结果的逻辑?
回归树:利用最终叶子的均值或者中位数来作为输出结果
-
CART树算法的剪枝过程是怎么样的?
目标函数为:𝐶𝛼(𝑇𝑡)=𝐶(𝑇𝑡)+𝛼|𝑇𝑡|,其中,α为正则化参数,这和线性回归的正则化一样。𝐶(𝑇𝑡)为训练数据的预测误差,分类树是用基尼系数度量,回归树是均方差度量。|𝑇𝑡|是子树T的叶子节点的数量
当𝛼=0时,即没有正则化,原始的生成的CART树即为最优子树。当𝛼=∞时,即正则化强度达到最大,此时由原始的生成的CART树的根节点组成的单节点树为最优子树。当然,这是两种极端情况。一般来说,𝛼越大,则剪枝剪的越厉害,生成的最优子树相比原生决策树就越偏小。对于固定的𝛼,一定存在使损失函数𝐶𝛼(𝑇)最小的唯一子树。由枝剪到根结点及不枝剪两种情况可得:𝛼=(𝐶(𝑇)−𝐶(𝑇𝑡))/(|𝑇𝑡|−1) , C(T)为根结点误差 计算出每个子树是否剪枝的阈值𝛼
- 选择阈值𝛼集合中的最小值
-
树形结构为何不需要归一化?
无论是分类树还是回归树,无论是连续变量还是离散变量,树模型一直想找的是最优切分点,不存在梯度导数等计算,数值缩放不影响分裂点位置,对树模型的结构不造成影响。
决策树的优缺点
优点:
缺失值不敏感,对特征的宽容程度高,可缺失可连续可离散
- 可解释性强
- 算法对数据没有强假设
- 可以解决线性及非线性问题
- 有特征选择等辅助功能
缺点:
- 处理关联性数据比较薄弱
- 正负量级有偏样本的样本效果较差
- 单棵树的拟合效果欠佳,容易过拟合