| 模型 | ID3 | C4.5 | CART |
|---|---|---|---|
| 结构 | 多叉树 | 多叉树 | 二叉树 |
| 特征选择 | 信息增益 | 信息增益率 | Gini系数/均方差 |
| 连续值处理 | 不支持 | 支持 | 支持 |
| 缺失值处理 | 不支持 | 支持 | 支持 |
| 剪枝 | 不支持 | 支持 | 支持 |
| 优点 | - | 1.相对于ID3来说，支持连续特征值，并且支持缺失值的处理 2.改进了信息增益趋向于选择特征值取值数量多的缺点 3.支持剪枝，避免了过拟合的缺点 |
1.使用基尼指数作为划分节点的标准，减少了信息增益和信息增益率中计算成本较高的对数运算耗时 2.既可以回归，又可以分类 3.二叉树效率比多叉树高 4.支持剪枝 5.能够处理连续特征和缺失值 |
| 缺点 | 1.信息增益偏向于取值较多的特征 2.不支持对连续值和缺失值的处理 3.无法剪枝 4.多叉树效率没有二叉树高 |
1.信息增益率计算时采用对数计算，计算成本较高，同时连续值还要排序 2.只能用于分类，不能回归 3.多叉树效率不如二叉树高 |
- |
-
三种基本决策树介绍：
-
ID3：
-
基本思想：从信息论中可以得知，信息熵越大，不确定性程度越高；如果能从某个样本集合中寻找到某种分裂集合的方式，使得集合中信息的不确定性减少的最多，那么就可以选用这种分类特征的方式作为结点分裂的方式。
-
如何分裂结点？采用信息增益作为衡量信息不确定性减少程度
- 信息熵的计算公式：给定样本集合D，求每种类别出现的概率，对其求和，主要看样本的标签y_true的不同取值
$$ H(D)= -\sum_{k=1}^K\frac{|C_k|}{D}log_2\frac{C_k}{D} $$ -
条件熵的计算公式：给定待划分的特征A，$D_i$表示D集合中特征A取第i个值的样本子集，主要看样本的特征A的不同取值 $$ H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i) $$
-
信息增益计算公式： $$ Gain(D, A) = H(D)-H(D|A) $$
-
-
C4.5：
-
基本思想：信息增益有个明显的问题就是它偏向于取特征数目更多的特征，C4.5在此基础上，除以该特征的信息熵；但是采用此方法带来的问题就是倾向于选择特征数量少的特征，因此这里采用了启发式方法，先从候选集找到信息增益高于平均值的特征，再从中选择信息增益率最高的。
-
信息增益率的计算公式： $$ Gain(D|A) = \frac{Gain(D, A)}{H_A(D)}\ H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2{\frac{|D_i|}{|D|}} $$
-
-
Cart：
-
基本思想：信息增益计算含有大量对数的计算，基尼指数在简化了模型计算的同时还保留了熵模型的优点。**基尼指数反应的是任意从数据集中抽取两个样本，其类别标记不一致的概率，**值在0-1之间。基尼指数作为熵的近似，可以看做是熵函数的泰勒展开。
-
基尼指数的计算公式： $$ Gini(D)=\sum_{k=1}^K\frac{|C_k|}{|D|}(1-\frac{|C_k|}{|D|})\ Gini(D|A)=\frac{|D_i|}{|D|}Gini(D_i) $$
-
-
-
(ID3和C4.5)决策树构建流程
- 给定样本特征集合X和决策标签集合Y
- 计算当前可以使用的各个特征的信息增益
- 选用信息增益最大的那个特征作为当前节点的的分支标准，并在特征集合中删除当前已经选中的特征
- 以该特征来进行划分，将该特征的不同取值作为该节点的多个分支节点（即多叉树）
- 重复上面三个步骤，直到划分到叶节点（若某个节点集合只有单一的特征或者全部是某一类标签，则为叶节点）
-
Cart树构建流程
- 给定样本集合X和决策集合Y
- 计算样本各个特征的特征值对应数据集D的基尼指数，选出最优的特征及其特征值进行划分
- 将集合分成按照最优分裂方式划分成两部分，得到两个分支
- 重复上面两个步骤直到达到停止条件
-
C4.5针对ID3的改进：
- 信息增益率改进信息增益
- 引入悲观剪枝作为后剪枝
- 连续特征离散化：假设连续值有m个取值，将其划分成m-1个区间进行分桶
- 特征值缺失的处理：
- 缺失值的特征如何计算信息增益率？假设原特征a的样本划分集合为D={$D_1,D_2,D_3$}，其中$D_3$为该特征缺失值的样本，那么先在去掉缺失值样本集合$D_3$得到子集$\hat{D}$={$D_1, D_2$}，在子集合上计算出该特征的信息增益率，然后乘上不是缺失值的样本在所有样本集合的占比。
- 缺失值样本应该划分到哪个节点里？上面针对特征a的非缺失值特征构建了分支决策，而缺失值去哪个分支都是有可能的，上面的分支决策生成的过程中，得到特征a的非缺失值样本构成的子集，子集中各中取值所占的比例P就是当前缺失值被划分到哪个分支的概率，因此缺失值都会以概率P被划分到某个分支。
- 划分好特征之后，待预测的样本含有缺失值，该如何处理？缺失值将遍历所有分支，并计算各个分支中预测正确的概率，以概率最高的为准。
-
Cart树对缺失值的处理：Cart树对缺失值的处理方式计算量过大，提升效果有限，后续集成模型很少用到这种处理方式。
-
Cart树对连续特征的处理：同C4.5的处理方法，先排序，然后划分成区间
-
Cart回归树构建流程：
- 与分类树过程类似，只是这里采用方差来衡量最优划分点
$$ min[min_{c_1}\sum_{x_i\in D_1}(y_i-c1)^2+min_{c_2}\sum_{x_i\in D_2}(y_i-c_2)^2] $$
-
Cart树输出结果的逻辑：
- 回归树：采用叶子结点的平均值或者中位数作为预测值
- 分类树：采用叶子节点中概率最大的类别作为预测值
-
Cart树的剪枝流程
- 目标函数：$C_{\alpha}(T_t)=C(T_t)+\alpha|T_t|$
- 其中，α为正则化参数，这和线性回归的正则化一样。$C(T_t)$为训练数据的预测误差，分类树是用基尼系数度量，回归树是均方差度量。$|T_t|$是子树T的叶子节点的数量。
- 当𝛼=0时，即没有正则化，原始的生成的CART树即为最优子树。当𝛼=∞时，即正则化强度达到最大，此时由原始的生成的CART树的根节点组成的单节点树为最优子树。 当然，这是两种极端情况。一般来说，𝛼越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。对于固定的𝛼，一定存在使损失函数𝐶𝛼(𝑇)最小的唯一子树。 由枝剪到根结点及不枝剪两种情况可得：$\alpha =\frac{C(T)-C(T_t)}{|T_t|-1}$ , C(T)为根结点误差
- 计算出每个子树是否剪枝的阈值𝛼
- 选择阈值𝛼集合中的最小值
- 分别针对不同的最小值𝛼所对应的剪枝后的最优子树做交叉验证
-
树模型为何不需要归一化?无论是分类树还是回归树，无论是连续变量还是离散变量，树模型一直想找的是最优切分点，不存在梯度导数等计算，数值缩放不影响分裂点位置，对树模型的结构不造成影响。
-
决策树的优缺点
优点：
- 缺失值不敏感，对特征的宽容程度高，可缺失可连续可离散
- 可解释性强
- 算法对数据没有强假设
- 可以解决线性及非线性问题
- 有特征选择等辅助功能
缺点：
- 处理关联性数据比较薄弱
- 正负量级有偏样本的样本效果较差
- 单棵树的拟合效果欠佳，容易过拟合
-
偏差与方差、噪声：
- 偏差：模型预测结果的期望与真实结果的差距，可以衡量模型与真实值之间的差距
- 方差：模型预测结果之间的关系，即预测结果的离散程度，可以衡量在不同训练集下我行之间的差异
- 噪声：噪声是模型无法解决的问题，数据的质量决定了学习的上限
-
bagging：
- 将数据集划分成多份，每一份数据训练一个基学习器，最后将所有基学习器预测的结果进行汇总，一般采用投票法
- 典型的代表就是Random Forest，Bagging的方式可以减少方差，也就是不同数据集对模型带来的影响
-
boosting
- 所有的基学习器都在同一份数据集上训练，不同的是，这些基学习器不是并行的而是串行的，后一个学习器在前一个学习器的基础上再继续学习提升
- 典型的代表就是AdaBoost和GBDT，Boosting的可以减少模型的偏差，每次朝真实值迭代提升
-
stacking
- 将数据集划分成多份，每一份数据训练一个基学习器，然后将这些基学习器的预测值输入到一个浅层的分类器中，让这个分类器预测最终的结果
- AdaBoost是一种Boosting方法
- 基本流程：
- 首先，是初始化训练数据的权值分布D1。假设有N个训练样本数据，则每一个训练样本最开始时，都被赋予相同的权值：w1=1/N。
- 然后，训练弱分类器hi。具体训练过程中是：如果某个训练样本点，被弱分类器hi准确地分类，那么在构造下一个训练集中，它对应的权值要减小；相反，如果某个训练样本点被错误分类，那么它的权值就应该增大。权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
- 最后，将各个训练得到的弱分类器组合成一个强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换而言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小
- 随机森林采用的基分类器是什么？Cart树
- 随机森林“随机”体现在哪里？
- 特征选择随机：决策树在产生节点的时候随机从M个特征中抽样m个特征
- 数据采样随机：有放回采样
- 随机森林生成过程
- 生成单棵决策树
- 随机选取样本
- 从M个输入特征里随机选择m个输入特征，然后从这m个输入特征里选择一个最好的进行分裂
- 不需要剪枝，直到该节点的所有训练样例都属于同一类
- 生成若干个决策树
- 生成单棵决策树
- 随机森林的损失函数：
- 分类树对应基尼系数
- 回归树对应均方差
- 随机森林优缺点：
- 在数据集上表现良好，相对于其他算法有较大的优势
- 易于并行化，在大数据集上有很大的优势；
- 能够处理高维度数据，不用做特征选择。
-
主要思想：GBDT 由三个概念组成：Regression Decision Tree（即 DT）、Gradient Boosting（即 GB），和 Shrinkage（一个重要演变）
- Regression Decision Tree：GBDT采用回归树作为基分类器
- Gradient Boosting：GBDT拟合的是前面一棵树的残差（损失函数为均方差函数的情况下）
- Shrinkage：Shinkage是一种优化避免GBDT陷入过拟合的方法，这个方法的本质是减小每一次迭代对于残差的收敛程度，认为每一次逼近少一些多次收敛的效果好于一次逼近很多，逼近次数较少的结果。具体的表现措施就是给我们的每一棵回归树的结果乘上一个类似于学习率的参数，通过增大回归树的个数来弥补。
-
主要步骤：参数M表示决策树的数量，$f_m(x_i)$表示训练m轮之后的整体
-
初始化：先创建一棵回归树$f_1(x)$，这里给定了训练数据集$X\in R^n, Y\in R$，首先遍历所有特征，遍历特征下所有取值，寻找最优切分点，分裂结点，左右子树的输出值分别是划分出的左右子集的平均值，依次计算知道生成一棵决策树。 $$ f_1(x)=\arg min_{c}\sum_{i=1}^NL(y_i, c) $$
-
迭代：GBDT的损失函数是一个与第k棵回归树有关的函数，将第k棵回归树的预测值看做待优化的变量，找出使得损失函数达到最小的参数，采用平方损失函数时就是拟合与前一棵树的残差
-
对于第2到第m棵回归树，计算每棵树的损失，并求出负梯度，对于平方损失函数来说，拟合的就是前面的残差 $$ r_{mi}=-[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}]{f(x)=f{m-1}(x)} $$
-
对于当前第m棵子树而言，我们需要遍历其所有可行的切分点和阈值，找到最优的预测值c及其参数，尽可能使其逼近残差 $$ c_{mj}=\arg min_{c} \sum_{x_i \in R_{mj}}L(y_i, f_{m-1}(x_i)+c) $$
-
-
对于GBDT来说，每棵树拟合前面一棵树的残差的同时也在调整树内部本身的阈值、最优切分点，因此每棵树都是相关联的
-
-
优点
- 可以自动进行特征组合，拟合非线性数据；
- 可以灵活处理各种类型的数据。
-
缺点
- 对异常点敏感。
-
XGBoost是GBDT的一种大规模并行实现
-
原理和GBDT差不多，针对GBDT主要做了以下改进
- 损失函数做了改进，加入了正则化项
- 梯度提升的时候引入了二阶导
- 决策树分裂时依赖于一二阶导
- 叶子结点预测值也依赖于一二阶导
-
损失函数：
- XGBoost的损失函数由两项组成，第一项是损失函数，第二项是正则化项
- 对于不同的问题，如：分类、回归等，XGBoost具有不同的损失函数和正则化项
-
回归问题：
-
当XGBoost选择基学习器为决策树时，其正则化项由两部分组成： $$ \Omega(f_m)=\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T\omega_j^2 $$ 即叶子结点个数和落在某个叶节点上的预测值的平方和
-
优化的目标就是每棵新加入的树要能够很好地拟合目标并且使得目标函数达到最小 $$ Cost=\sum_{i=1}^nl(\hat{y_i}, y_i)+\sum_{t=1}^k\Omega(f_t) $$
-
当正在拟合第i棵树的时候，前面的树参数不再发生变化，预测值都可以看做是常数，目标函数就等价于 $$ Cost=\sum_{i=1}^n(y_i-(\hat{y}i^{t-1}+f_t(x_i)))^2+\sum{t=1}^k\Omega(f_t) $$
-
将损失函数在x处泰勒展开(
$f(x+\Delta x)=f(x)+f'(x)\Delta x+\frac{1}{2}\Delta x^2$ )，记$g_i$为损失函数的一阶导，$h_i$为损失的二阶导 $$ Cost=\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i)]+\sum_{t=1}^k\Omega(f_t) $$ -
到目前为止，损失函数一直都是关于第i棵树的预测值的函数，对树模型做个变换，将损失函数变成关于叶子结点预测值的函数 $$ w_j=f_m(x_i)(x_i\in I_j) $$ 其中$I_j$表示第j个节点的划分区域，这样就能够把样本$x_i$映射到第j个叶子结点上去
-
把上式子中的$f_m(x_i)$替换成$w_j$，然后注意这里的$\sum_{i\in I_j}g_i$的含义是对叶节点取值相同的系数求和，最后对所有叶节点求和 $$ \begin{align} Cost &= g_1f_m(x_1)+g_2f_m(x_2)+...g_nf_m(x_n)+\frac{1}{2}h_1f^2_t(x_1)+\frac{1}{2}h_2f^2_t(x_2)+...+\frac{1}{2}h_nf^2_t(x_n)+\sum_{t=1}^k\Omega(f_t)\ &=\sum_{j=1}^T[(\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w_j^2]+\gamma T \end{align} $$
-
这样损失函数就成了关于叶节点预测值$w_j$的一元二次函数，可以直接求出其最优解，记$\sum_{i\in I_j}g_i=G_j,\sum_{i\in I_j}h_i=H_j$，含义是预测值相同叶节点： $$ w_j^*=-\frac{G_j}{H_j+\lambda} $$
-
将最优解$w_j^*$带入损失函数可得： $$ Cost=-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T $$
-
-
决策树特征选择：对于GBDT来说，新训练的一棵树特征选择的方案就是Cart树节点分裂的平方误差增益方案；而XGBoost则将分裂前后的损失增益作为评价条件。 $$ \begin{align} Score_{pre}&=-\frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}+\gamma\ Score_{after}&=-\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}]+2\gamma\ Gain&=Score_{after}-Score_{pre} \end{align} $$
- 最优切分贪心算法：
- 从深度为0的树开始，对每个叶节点枚举所有的可用特征；
- 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
- 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集
- 回到第 1 步，递归执行到满足特定条件为止
- 基于贪心算法的最优切分算法每次都需要枚举所有可能的分割方案，为了高效地枚举分割方案，可以枚举所有梯度即可
-
近似算法：针对贪心方法的改进，贪心算法可以得到最优解，但是当数据量太大的时候无法读入内存中计算，近似算法针对贪心算法的缺点做出了改进
- 该算法根据数据特征分布的分位数提出候选划分点，然后将连续特征映射到候选点划分的桶中，然后聚合统计信息找到所有区间的最佳分裂点
- XGBoost提出了两种选取候选切分点的策略：Local和Global两种
- Local策略是每次候选点划分前重新选取划分点
- Global策略是一棵树全局统一采用相同的划分点
- 直观上看Local需要更多的计算步骤，Global策略在候选点足够多时，效果能够逼近贪心策略
- 最优切分贪心算法：
-
加权分位数缩略图：上述近似算法分位数选取切分点算法中，分位数并非简单地按照样本个数分位，而是以二阶导数$h_i$进行加权
- 用二阶导加权的原因：在损失函数中，$h_i$可以看做样本的权重
-
稀疏感知算法：XGBoost对数据缺失时的分裂策略
- XGBoost在构建树时，只考虑了非缺失值的数据遍历，每个节点都增加了一个缺省的方向，当样本特征中含有缺失值时，可以被归类到最优的缺省方向。关于最优缺省方向的计算，只需要将计算将缺省样本归为左右分支之后的增益，选择增益最大的为最优缺省方向。
- 在构建树的过程中，XGBoost只对非缺失值的样本进行遍历，对特征值缺失的样本，无需遍历直接计算后分配到左右节点中。
-
工程实现：
- 并行化：
LightGBM是微软针对XGBoost在海量数据中遇到的问题进行的改进方案，主要有以下几种方案：
- 单边梯度抽样算法(GOSS)：GBDT中梯度可以反应样本的权重，梯度越小说明模型拟合得越好，单边梯度抽样算法利用这一信息进行抽样，能够减少大量梯度小的样本，只需要关注梯度大的样本，可以减少计算量
- 直方图算法：直方图算法的基本思想就是将连续的特征离散化为k个离散特征，构造一个直方图用于统计信息
- 直方图加速：在计算直方图时，如果已知父节点和其中一个叶节点的直方图，可以利用父节点的直方图与已知叶节点的直方图作差得到另一个叶节点的直方图
- 系数特征优化：只针对非零特征构建直方图
- 互斥特征捆绑算法：互斥特征捆绑算法的主要目的在于将互斥的特征进行绑定，从而减少特征数量
- 带深度限制的Leaf_wise算法：Leaf_wise的增长策略，减少了计算量，不过无法并行计算
- 类别特征最优分割
- GBDT原理
- XGBoost原理
- GBDT和XGBoost的区别？
- GBDT和Random Forest的异同点？
- 处理维度大且稀疏的特征，XGBoost和LR哪个更好一点？
- 为什么XGBoost在比赛上效果好？
- XGBoost分布式计算是计算什么？
- XGBoost如何加速计算？
- XGBoost预排序有什么作用？
- XGBoost如何处理缺失值？
- GBDT需不需要归一化？
- XGBoost与LightGBM的区别？
- XGBoost不同参数主要作用是什么？为了防止过拟合有哪些参数可以调节？
- XGBoost损失函数泰勒展开为什么不用三阶以及更高？
- LightGBM的直方图加速如何实现的？