决策树（4）总结

发表于 更新于 分类于 ， ， 阅读次数： 本文字数： 4.2k 阅读时长 ≈ 8 分钟

决策树——ID3、C4.5、CART

决策树是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。

算法 ID3（分类） C4.5（分类） CART（分类和回归）
思想 奥卡姆剃刀：越是小型的决策树越优于大的决策树;ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间。 C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。 CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。CART 包含的基本过程有分裂，剪枝和树选择。
划分标准 信息增益 = 类别熵 - 特征类别熵 类别熵：\(H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}\) 特征类别熵：\(H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)\) 先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。 Gini 系数作为变量的不纯度量，减少了大量的对数运算；\(G i n i(D)=\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|}\left(1-\frac{\left|C_{k}\right|}{|D|}\right)\)
剪枝策略 无 悲观剪枝策略 基于代价复杂度剪枝
数据差异 离散数据且缺失值敏感 离散、连续特征离散化；【排序+离散化】 连续型、离散型
连续值处理 无 排序并取相邻两样本值的平均数。 排序并取相邻两样本值的平均数。CART 分类树【基尼系数】。回归树【和方差度量】。
缺失值处理 无 1、有缺失值特征，用没有缺失的样本子集所占比重来折算；2、将样本同时划分到所有子节点 代理测试来估计缺失值
类别不平衡 无 无 先验机制：其作用相当于对数据自动重加权，对类别进行均衡。
缺点 1、ID3 没有剪枝策略，容易过拟合；2、信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1； 3、只能用于处理离散分布的特征； 没有考虑缺失值。 1、多叉树。2、只能用于分类。3、熵模型拥有大量耗时的对数运算，连续值还有排序运算。4、驻留于内存的数据集。 熵模型拥有大量耗时的对数运算，连续值还有排序运算。
  • 划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
  • 使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
  • 样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
  • 样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
  • 剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

一、决策树Q&A

1.1 介绍决策树ID2、C4.5、CART, 3种决策树及其区别和适应场景？

1.2 决策树处理连续值的方法?

ID3 只能离散型。C4.5 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；

CART分类树：离散化+基尼指数，

CART回归树：均方差之和度量方式 \[ \min _{a, s}\left[\min _{c_1} \sum_{x_i \in D_1}\left(y_i-c_1\right)^2+\min _{c_2} \sum_{x_i \in D_2}\left(y_i-c_2\right)^2\right] \]

1.3 决策树处理缺失值的方式？

ID3、c4.5、cart、rf到底是如何处理缺失值的？

1.3.1 在特征值缺失的情况下进行划分特征的选择？

ID3 没有缺失值处理；

C4.5：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；

CART：初期：分裂特征评估时只能使用在该特征上没有缺失值的那部分数据；后续：CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响。

1.3.2 选定该划分特征，对于缺失该特征值的样本如何处理？

ID3 没有缺失值处理；

C4.5：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

CART：sklearn中的cart的实现是没有对缺失值做任何处理的，也就是说sklearn的cart无法处理存在缺失值的特征。

1.4 决策树如何剪枝？

  • 预剪枝：在树的生成过程中，提前停止生长。简单，适合解决大规模问题。
    • 深度
    • 节点样本数
    • 对测试集准确率的提升过小
  • 后剪枝：生成一颗完全生长的二叉树，从低向上剪枝，将子树删除用叶子节点代替。【类别：多数投票】常见的剪枝方法：错误率降低剪枝（REP）、悲观剪枝（PEP）、代价复杂度剪枝（CCP）、最小误差剪枝（MEP）等。

代价复杂度剪枝（CCP）【CART树】

从完整子树 \(T0\) 开始， 通过在 \(Ti\) 子树序列中裁剪真实误差最小【考虑叶子节点的个数】的子树，得到 \(Ti+1\)。

image-20220321203204744【剪枝之后的误差 - 剪枝前的误差 / 叶子节点数 - 1】

每次误差增加率最小的节点，得到一系列的子树，从中选择效果最好的【独立剪枝数据集】和【K折交叉验证】

1.5 决策树特征选择？特征重要性判断？

XGBoost：

  • 该特征在所有树中被用作分割样本的特征的总次数。

  • 该特征在其出现过的所有树中产生的平均增益。

  • 该特征在其出现过的所有树中的平均覆盖范围。

    注意：覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。

1.6 SVM、LR、决策树的对比？

逻辑回归，决策树，支持向量机 选择方案: https://cloud.tencent.com/developer/article/1435642

广义线性模型？

sigmod、softmax

为什么逻辑回归的连续值也需要离散化？

为什么逻辑回归要用交叉熵？

交叉熵和KL散度（相对熵）和GAN的损失函数的区别？

算法 LR 逻辑回归 SVM 决策树
场景 逻辑回归 = 线性回归 + Sigmoid 函数（非线形）【分类问题】【参数模型】【统计方法】 【分类问题】【几何方法】【非参数模型】 【分类问题】【回归问题】【非参数模型】
思想 思路：先拟合决策边界(不局限于线性，还可以是多项式)，再建立这个边界与分类的概率联系，从而得到了二分类情况下的概率。细节：通过非线性映射减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重； 思想：SVM 想要的就是找到各类样本点到超平面的距离最远，也就是找到最大间隔超平面。 思想：用启发算法来度量特征选择，选择特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间。
关键样本 所有样本（通过非线性映射，大大减小了离分类平面较远的点的权重） 支持向量（超平面到距离最近的不同标记样本集合） 所有样本【非缺失特征值】
目标函数 \(y=\frac{1}{1+e^{-\left(w^{T} x+b\right)}}\) 【极大似然函数】 \(\min \frac{1}{2}\|w\|^2\) Gini 系数作为变量的不纯度量，减少了大量的对数运算；\(G i n i(D)=\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|}\left(1-\frac{\left|C_{k}\right|}{|D|}\right)\)
损失函数 【交叉熵损失】 HingeLoss【合页损失函数】\(\sum_{i=1}^N\left[1-y_i\left(w \cdot x_i+b\right)\right]_{+}+\left.\lambda||w\right|^2\)\([z]_{+}=\left\{\begin{array}{l}z, z>0 \\ 0 . z \leq 0\end{array}\right.\)
决策面 线性可分 非线性
连续值处理 离散化 离线化
输出 类别的概率 类别 类别、回归
过拟合 正则化 \ 预剪枝和后剪枝
优势 本质其实是为了模型参数服从某一分布；1、对观测样本的概率值输出 2、实现简单高效3、多重共线性的问题可以通过L2正则化来应对。 4、大量的工业界解决方案5、支持online learning 1、可以处理高维特征 2、使用核函数轻松应对非线的性特征空间 3、分类面不依赖于所有数据4、关重要的关键样本 1、直观的决策过程 2、能够处理非线性特征 3、考虑了特征相关性
劣势 1、特征空间太大时表现不太好 2、对于大量的分类变量无能为力 3、对于非线性特征需要做特征变换 4、依赖所有的样本数据 1、对于大量的观测样本，效率会很低 2、找到一个“合适”的核函数还是很tricky的 1、极易过拟合 2、无法输出score，只能给出直接的分类结果

1.7 多重共线性问题

多重共线性问题就是指一个解释变量的变化引起另一个解释变量地变化。多重共线性是使用线性回归算法时经常要面对的一个问题。在其他算法中，例如决策树或者朴素贝叶斯，前者的建模过程时逐渐递进，每次都只有一个变量参与，这种机制含有抗多重共线性干扰的功能；后者假设变量之间是相互独立的。但对于回归算法来说，都要同时考虑多个预测因子，因此多重共线性不可避免。

  • PCA等降维方法。因为在原始特征空间中变量之间相关性大，很容易想到通过降低维度的形式来去除这种共线性。
  • 正则化。使用岭回归（L2）或者lasso回归（L1）或者elasticnet回归（L1+L2）
  • 逐步回归法