1、决策树

1.1 线性回归

用于预测连续型数据，eg. 房价预测
linear_regression.ipynb
linear_regression.pdf

1.2 逻辑回归

用于预测离散变量（即用于分类），eg. 判断邮件是否为垃圾邮件的二分类问题
逻辑回归是在线性回归的基础上通过 sigmoid 函数将预测值映射到 0~1 的区间来代表二分类结果的概率
logistic_regression.ipynb
logistic_regression.pdf

1.3 决策树

决策树是 XGBoost 模型的基本构成单元

决策树是一种树形结构，可用于解决分类问题和回归问题。

• 每个非叶子节点表示一个特征 or 属性，可以看作 if-else 规则，将样本划分到不同的子节点
• 每个叶子节点代表预测结果（类别）
• 从根节点到叶子结点的路径代表判定规则

决策树的优点：

• 决策树具有天然的可解释性，可以简单直观地展示整个决策规则

1.3.1 构造决策树

• 决策树的训练目标：得到一种分类规则，使数据集中的所有样本都能被划分到正确地类别
• 决策树学习的损失函数：正则化的极大似然函数
• 从所有决策树中选出最优的决策树是 NP 完全问题，一般采用启发式算法近似求解（每一步都采用当前最优决策）

决策树生成过程分为三部分：

• 特征选择：如果特征很多，需要进行特征选择，选择出那些有分类能力的特征，作为决策树划分的特征
• 树的构造：首先为根节点选择一个最优特征对数据集进行划分，然后分别对其子节点进行最优划分，即每一步求局部最优解，直至该子集的所有样本都被正确的分类，生成对应的叶子节点
• 树的剪枝：为了提高决策树的泛化能力，需要进行剪枝

1.3.2 特征选择

特征选择：选择出那些有分类能力的特征，作为决策树划分的特征

• 特征选择的优点：
  • 简化模型，缩短模型训练时间
  • 避免维度灾难
  • 减少过拟合，提高模型泛化能力

如何衡量特征是否有分类能力？

• 不同的决策树算法（eg. ID3、C4.5、CART）有不同的方法（eg. 使用信息增益、信息增益比等）

ID3

ID3：根据最大信息增益的原则对数据集进行划分
SD3 算法流程：

1. 从根节点开始分裂
2. 节点分裂前，遍历所有被使用的特征，计算特征的信息增益
3. 选取信息增益最大的特征作为节点分裂的特征，并对该特征每个可能的取值生成一个子节点
4. 对子节点循环执行步骤 2、3，直至所有特征的信息增益均小于某阈值 or 没有特征可以选择

最终，对于每个叶子节点，将其中样本数量最多的类作为该节点的类标签

信息增益的计算：

• 信息熵：， 是事件 i 发生的概率
• 样本集合 D 的熵：， 是第 k 类的样本数量
• 条件熵：
• 用特征 A 对样本集合 D 划分为 m 个子集后的条件熵：
• 特征 A 的信息增益：
  • 表示用特征 A 对样本集合进行划分时不确定性的减少程度。差值越大代表不确定性降低越大，信息增益越大

ID3 的局限性：

• ID3 算法会偏向选择取值较多的特征（信息增益会更大），但不适用于极端情况下连续取值的特征选择
  • 解决方法：C4.5 算法

C4.5

C4.5 算法与 ID3 算法唯一的区别：采用信息增益比进行特征选择，解决了 ID3 算法不能处理连续取值特征的问题

信息增益比的计算：

• 数据集 D
• 特征 F 的信息增益：
• 数据集 D 以特征 F 作为随机变量的熵：，n 是特征 F 的取值个数
• 信息增益比：

CART

CART 采用的是二分递归的分裂的思想，因此生成的决策树是二叉树，生成决策树后还要进行剪枝（后剪枝）
CART 包含两种类型的决策树：

• 分类树：预测值是离散的，通常会将叶子节点中多数样本的类别作为该节点的预测类别
  • 采用基尼指数最小化进行特征选择
  • 对每个特征和每个切分点，计算分裂后两个子节点的基尼指数的和，选择和最小的作为最优特征和最优切分点
• 回归树：预测值是连续的，通常会将叶子节点中多数样本的平均值作为该节点的预测值
  • 采用平方误差最小化进行特征选择
  • 平方误差：
  • 对每个特征和每个切分点，计算分裂后两个子节点的平方误差的和，选择和最小的作为最优特征和最优切分点

CART 分类树的生成：采用基尼指数最小化进行最优特征选择、决定最优切分点
CART 分类树的生成步骤：

1. 从根节点开始分裂
2. 节点分裂之前，计算所有可能的特征及它们所有可能的切分点分裂后的基尼指数
3. 选出基尼指数最小的特征及其切分点作为最优特征和最优切分点。通过最优特征和最优切分点将节点分裂成两个子节点
4. 对新生成的子节点递归步骤 2、3，直至满足停止条件（基尼指数小于某阈值 or 节点样本数小于一定阈值 or 某节点的样本已全部属于某一种类别）
5. 生成分类树

   基尼指数

   • D 是样本集，K 是类别个数， 是类别为 k 的样本占所有样本的比值
   • 样本分布越集中，基尼指数越小
   • 对于二分类问题（CART 每次节点分裂都是二分类）：

1.3.3 决策树剪枝

剪枝的目的：修剪分裂前后预测误差变化不大的子树，降低树的复杂度，减少决策树的过拟合现象，增强模型的泛化能力

剪枝策略：

• 预剪枝：在决策树分裂过程中，在每个节点分裂前预先进行评估，若该节点分裂后不能提升决策树的泛化能力，则该节点不分裂
• 后剪枝：构造一棵完全决策树后，然后自底向上对非叶子节点进行评估，若将该非叶子节点剪枝有助于提升决策树模型的泛化能力，则减去该节点的子树，使其变为叶子节点

CART 算法采用后剪枝算法，剪枝过程：

1. 生成子树集合：对于生成的决策树，从底部开始由下往上依次进行剪枝，直到根节点。对于每一种剪枝情况都会产生一棵子树，由此可得到一个子树集合
2. 交叉验证选择最优子树：在测试集上使用交叉验证的方法对每棵子树进行验证，选择最优子树（分类树的评估指标为基尼指数，回归树的评估指标为平方误差）

但 XGBoost 在实现时并未完全按照上述剪枝过程，而是采用了简单、高效的剪枝方法：即判断当前节点的收益是否小于定义的最小收益，若比最小收益小，则进行剪枝

1.3.4 决策树实例：肿瘤分类

用决策树解决预测良性/恶性肿瘤的二分类问题

• 使用的是 scikit-learn 实现的决策树算法，采用的是优化的 CART 算法
  • 分类问题使用 DecisionTreeClassifier 类（本例使用的）
  • 回归问题使用 DecisionTreeRegressor 类

decision_tree.pdf

2、梯度提升 Gradient Boosting

Boosting 技术：将多个弱学习器通过一定的方法整合为一个强学习器

• AdaBoost：
  • 确定基分类器
  • 训练基分类器：
    • 初始化：为每个训练样本赋予一个初始权值
    • 每轮训练：
      • 对一个弱分类器 进行训练，提高预测错误样本的权值，降低预测正确样本的权值
      • 计算这个弱分类器的分类误差率 ，以此计算该弱分类器的权重
        • 分类误差越小，该弱分类器的权值越大
      • 进行下一轮训练
  • 合并基分类器：最终得到 m 个弱分类器，这些弱分类器加权投票得到最终的预测结果
• Gradient Boosting：
  • 与 AdaBoost 的区别：将损失函数梯度下降方向作为优化目标

梯度提升 Gradient Boosting：每一轮训练，计算当前模型损失函数的负梯度信息，将其作为残差来训练新加入的弱分类器，并将该弱分类器加到现有模型

Gradient Boosting 算法流程：
输入：训练集 ，损失函数 ，训练轮数 M 。
输出：最终模型 。
算法：

1. 通过常数初始化模型：。即通过训练一个常数使得所有样本的损失函数之和最小
2. 迭代训练 M 轮，设当前为第 m 轮：
   1. 计算之前模型损失函数的负梯度（伪残差）：
   2. 训练一个子模型 ，目标是拟合
   3. 通过线性搜索，计算梯度下降的最优步长 ，使得损失函数最小化：
   4. 更新模型：
3. 输出最终模型

2.1 缩减

缩减：

• 即，为每一轮训练的新模型增加一个类似于学习率的的缩减系数 ，用来减小每轮在梯度下降方向的步长
• 作用：使得每次沿梯度下降的方向走一小步，逐步逼近最优结果，而不是一步到位，这样可以有效地避免模型过拟合
• 较小的缩减系数 可以减少测试集的错误率，从而提高模型的泛化能力
• 但缩减系数 减小时，训练轮数 M 会增加，训练时间增加
• 策略：先选取较小的缩减系数 ，然后通过设定合适的停止条件停止训练，从而控制训练轮数 M

3、GBDT / Gradient Tree Boosting

梯度提升决策树 GBDT（也称 Gradient Tree Boosting）是 Gradient Boosting 的一种实现，以决策树作为子模型，通常是以 CART 作为子模型

• GB：融合的方法（训练方法）是梯度提升 Gradient Boosting
• DT：使用的弱分类器是决策树 Decision Tree（通常为 CART）
• 基本思想：根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中

GBDT / Gradient Tree Boosting 的优点：

• 预测阶段树与树之间可以并行化计算，计算速度快（但训练阶段需要串行）
• 在分布稠密的数据集上，泛化能力和表达能力都很好
• 采用决策树作为弱分类器使得 GBDT 模型具有较好的可解释性和鲁棒性，能够自动发现特征之间的高阶关系（可以有效挖掘特征及特征组合），并且也不需要对数据进行特殊的预处理，eg. 归一化等
• 能够达到较高的预测准确率

GBDT / Gradient Tree Boosting 的缺点：

• 在高维稀疏的数据集上，表现不如支持向量机 or 神经网络
• 在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显
• 训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度

GBDT / Gradient Tree Boosting 算法流程：

与 Gradient Boosting 的区别就是用树模型作为子模型，去拟合负梯度

输入：训练集 ，损失函数 ，训练轮数 M 。
输出：最终模型 。
算法：

1. 通过损失函数最小化来初始化模型：
2. 迭代训练 M 轮，设当前为第 m 轮：
   1. 计算之前模型损失函数的负梯度（伪残差）：
   2. 训练一个回归树取拟合目标值 ，树的终端区域（叶子节点）为
   3. 对 ，计算步长 ：
   4. 
3. 输出最终模型

4、XGBoost

XGBoost 树模型：

• 以 CART 作为子模型（训练时的树生成算法与 CART 算法一致，即通过节点分裂后与分裂前是否产生“增益”，来确定节点是否分裂，并通过参数控制树的深度。当一棵树生成完毕后，再对其进行剪枝，防止过拟合）
• 通过 Gradient Tree Boosting 实现多棵 CART 树的集成学习，第 m 轮生成的树会学习真实值和 m-1 轮模型的预测值的“残差”，是的模型预测结果逐步逼近真实值，得到最终模型。
• 多棵决策树共同决策，最后将所有树的结果累加起来作为最终的预测结果
• 是一种有监督学习算法，可以解决分类、回归等机器学习问题

4.1 XGBoost 模型定义

XGBoost 模型定义：

• 数据集样本 ， 是 m 维的特征向量， 是样本标签
• XGBoost 模型包含 K 棵决策树
• 是第 K 棵决策树
  • 决策树会对每个样本特征进行映射，使得每个样本落在该树的某个叶子节点上
  • 每个叶子节点均包含一个权重分数 ，作为落在此叶子节点的样本在本棵树的预测值
  • 计算样本在每棵树的预测值（即 ）之和，并将其作为样本的最终预测值

XGBoost 训练的目标函数：

• 第一项 为损失函数：用于评估模型预测值和真实值之间的损失 or 误差，该函数必须是可微分的凸函数
• 第二项 是 L2 正则化项：用来控制模型的复杂度，避免过拟合
  • 正则化项
    • 第一项 ：T 是决策树 的叶子节点个数
      • 通过叶子节点数及其系数控制树的复杂度，值越大则目标函数越大，从而抑制模型的复杂程度
    • 第二项 ： 是第 j 个叶子节点的预测值/权重
      • 正则化项，用于控制叶子节点的权重分数

4.2 XGBoost 中的 Gradient Tree Boosting

Gradient Tree Boosting：每轮训练计算目标函数的负梯度，子模型以负梯度作为目标值进行训练，从而保证模型优化的方向

XGBoost 在 Gradient Tree Boosting 的基础上做了优化，目标函数有所变化：

• 目标函数近似
• 最优目标函数和叶子权重

4.2.1 目标函数近似

对于 4.1 节的目标函数公式 ，需要找到一个最优的 使目标函数最优，但用传统的方法很难在欧氏空间中对这个目标函数进行优化，因此 XGBoost 采用了近似的方法来解决这个问题

第一步：改写目标公式
XGBoost将目标函数改写为：

• ：是第 s-1 轮训练时模型对样本 的预测值
• ：是第 s 轮训练的新子模型

第二步：引入泰勒公式来近似和简化目标函数

泰勒公式：如果函数曲线足够平滑，就可以通过某一点的各阶导数值构建一个多项式来近似表示函数在该点邻域的值

• 两阶泰勒展开式：

将第一步改写的 XGBoost 目标函数进行二阶泰勒展开（将 看作 x，将 看作 ）：

• 损失函数的一阶梯度统计：
• 损失函数的二阶梯度统计：
• 常数项 不影响优化结果，因此可以去掉

XGBoost 目标函数二阶泰勒展开 & 简化后：

• 前半部分损失函数的最外层求和公式的维度为样本，可理解为最终的目标函数值是所有样本各自的目标函数值求和

4.2.2 最优目标函数和叶子权重

4.2.1 节引入了泰勒公式来近似和简化 XGBoost 的目标函数：

• 后半部分（正则化项）的 是第 s 棵决策树的第 j 个叶子节点的权重
• 前半部分（损失函数）的 是一个子模型，实际上是一棵决策树（第 s 棵），每个样本必定会被划分到该决策树的某一叶子节点上。设 为落在叶子节点 j 上的的样本集，可以计算得到叶子节点 j 的分数 ，就是落在该节点上的样本的预测结果，因此可以用 来代替

因此，XGBoost 的目标函数可以改写为：

• 求和公式的维度为叶子节点，先求得每个叶子节点包含的所有样本在该棵树的目标函数值之和，再将所有叶子节点的值求和得到最终的目标函数值
• 可以看作自变量为 ，因变量为 的一元二次函数，根据一元二次函数的最后公式：
• 叶子节点 j 的最优权重 为：
  • 叶子权重不仅取决于一阶、二阶统计信息，还和 L2 正则化系数 λ 相关
  • L2 正则化的作用：缩小叶子节点权重，减少对整个预测结果的影响，从而防止过拟合
  • 

最优的目标函数值：

• 可以作为评价一个树模型的评分函数，评分越小，表明该树模型越好；反之，该树模型越差

• 每一轮训练中，只要对所有候选树模型分别计算评价得分，从中选出最优的即可
• 但候选树的个数是无穷的，不可能得到所有候选树的评价得分
• 因此，XGBoost 采用贪心算法来生成每一轮的决策树

XGBoost 采用贪心算法来生成每轮的决策树，即先从树的根节点开始，计算节点分裂后比分裂前目标函数值是否减少

• 设当前分裂节点为 j，其对目标函数的贡献
• 该节点分裂后，两个子节点的目标函数贡献
• 目标函数的变化值

每轮训练生成新的决策树时，在一个叶子节点的分裂过程中，计算所有特征及其切分点的目标函数的变化值 ，选取 最大的特征及其切分点作为最优特征和最优切分点，进行分裂

在生成一棵新的树后，XGBoost 会对其进行剪枝：

• 判断当前节点的收益是否小于定义的最小收益，若比最小收益小，则进行剪枝

剪枝完后，将新生成的树模型 加入到当前模型：

• 缩减系数 ：，类似于学习率，用来限制每棵树对模型的影响，使得模型优化过程中每次只前进一小步，逐步达到最优，有效避免过拟合

4.2.3 总结：XGBoost 中的 Gradient Tree Boosting

XGBoost 中的 Gradient Tree Boosting 算法的训练过程：（每轮训练增加一个新的树模型）

1. 每轮训练开始，首先计算梯度统计：
2. 根据贪心算法及梯度统计信息生成一棵完整树
   1. 节点分裂通过目标函数变化（减小）值（如下公式）进行评估，选择最优特征和最优切分点
   2. 最终树叶子节点的权重为
3. 将新生成的树模型 加入模型：

此外，XGBoost 还支持行采样和列采样：

• 行采样：对样本进行有放回的采样，即多次采样的集合中可能出现相同的样本。因此每棵树训练的样本都不是全部样本，从而避免过拟合
• 列采样：从 M 个特征中选取 m 个特征（m<<M），用于对采样后的数据建立模型进行训练，而非采用所有特征。
  • 列采样技能避免过拟合，也减少了计算量
  • 列采样比行采样更能有效避免模型过拟合

4.3 切分点查找算法

4.2.2 节中介绍，XGBoost 在每轮训练生成新的决策树模型时，首先计算所有特征在所有切分点分裂前后的 (即目标函数的减少值)，然后选取 最大的特征及其切分点作为最优特征和最优切分点，对叶子节点进行分裂

XGBoost 的切分点查找算法：

• 精确贪心算法
• 基于直方图的近似算法
• 快速直方图算法
• 加权分位数概要算法
• 稀疏感知切分点查找算法

4.3.1 精确贪心算法

精确贪心算法：每次节点分裂时，首先找到所有的候选特征及所有的候选切分点，一一求得其 ，选择 最大的特征及对应切分点作为最优特征和最优切分点，对节点进行分裂

• 是一种启发式算法，在节点分裂时只选取了当前最优的分裂策略，而非全局最优的分裂策略
• 优点：计算了所有特征、所有切分点的收益，并从中选择了最优的，从而保证模型能较好地拟合训练数据
• 缺点：当数据不能完全加载到内存时，精确贪心算法会变得非常低效
  • 解决方法：基于直方图的近似算法

精确贪心算法对一个节点进行分裂的计算过程：
输入：当前节点的样本集 , 特征维度
输出：最优分裂

1. 初始化分裂收益和梯度统计：
2. 对每个特征 ，执行以下步骤：
   1. 初始化左子节点的一阶梯度统计和二阶梯度统计：
   2. 对节点包含的所有样本在该特征下的取值进行排序，然后遍历每个取值 j
      1. 计算左子节点和右子节点的梯度统计：
      2. 计算最终分裂后的收益（目标函数减小值 ），选取收益最大的
3. 按照最大收益的特征及其分裂点对当前节点进行分裂

示例：

4.3.2 基于直方图的近似算法

当数据不能完全加载到内存时，精确贪心算法会变得非常低效，因此提出了基于直方图的近似算法来更有效地选择最优特征及切分点

基于直方图的近似算法的计算过程：

1. 对每个特征 ，按分位数对特征 k 进行分桶，得到一个候选切分点集
2. 对特征 k 的每个分桶 计算特征统计 ，得到直方图
3. 分别计算以候选切分点集中的每个切分点作为分裂点时的收益
4. 重复步骤 1-3，计算每个特征所有候选切分点对应的收益
5. 找到最大增益的特征及其候选切分点

示例：


候选切分点的构建策略有两种：

• 全局策略：在树构建的初始阶段对每一个特征确定一个候选切分点的集合，并在树每一层的节点分裂中均采用此集合计算收益，整个过程候选切分点集合不改变
• 本地策略：在每一次节点分裂时均重新确定候选切分点

4.3.3 快速直方图算法

快速直方图算法：是基于直方图的近似算法的优化，在多次迭代中重用之前的分桶，并以此为基础进行了一些优化：

• 数据预处理：将浮点数数据均匀映射为整形数据，提高运算效率，也能提高划分的质量
• 桶缓存：将桶进行缓存、复用，提高计算效率
• 直方图减法技巧：简化节点直方图的计算，直接取父节点和兄节点的差

4.3.4 稀疏感知切分点查找算法

XGBoost 处理稀疏数据的方法：给每棵树指定一个默认方向，即当特征值缺失时，该样本会被划分到默认方向的节点上

稀疏感知切分点查找算法：对数据进行学习，从而选择出默认方向
算法流程：
输入： 为当前节点样本集； 是特征 k 的样本集合，不含特征 k 的特征值缺失的样本； 是特征维度
输出：最大收益的节点分裂及默认方向

1. 初始化分裂收益和梯度统计：
2. 对每个特征
   1. 初始化左子节点的一阶梯度统计和二阶梯度统计，将缺失值划分到右子节点：
   2. 对该特征下的所有非缺失值进行排序，然后遍历每个取值 j
      1. 计算左子节点和右子节点的梯度统计：
      2. 计算最终分裂后收益，选取收益最大的：
   3. 初始化右子节点的一阶梯度统计和二阶梯度统计，将缺失值划分到左子节点：
   4. 对该特征下的所有非缺失值进行排序，然后遍历每个取值 j
      1. 计算左子节点和右子节点的梯度统计：
      2. 计算最终分裂后收益，选取收益最大的：
3. 选取最大收益的方向作为缺失值划分的默认方向

稀疏感知切分点查找算法的优点：

• 相较于不考虑稀疏数据的普通算法而言，稀疏感知切分点查找算法在每棵树的训练速度提高近 50 倍

4.4 XGBoost 超参数优化

4.4.1 XGBoost 参数

官方文档：XGBoost Parameters

XGBoost 中大部分参数的调整是偏差与方差的权衡。好的模型应该能平衡复杂度与泛化能力，从而达到一个最优的状态。

控制过拟合：

• 直接控制模型的复杂度：eg. 调整 max_depth、min_child_weight、gamma 等参数
• 增加模型随机性：有效避免噪声的干扰，eg. 调整 subsample、colsample_bytree 等参数
• 减小 eta 缩减步长，但需注意调大 num_round
• DART：引入 Dropout

不平衡数据集：

• 若仅关心预测样本的排序顺序（eg. AUC），可通过 scale_pos_weight 参数平衡正负样本权重，并用 AUC 进行评估
• 若比较关心预测值的准确性，这种情况下可能无法重新平衡数据集，可以尝试将 max_delta_step 设置为一个有助于模型收敛的有限值，eg. 1

4.4.2 XGBoost 超参数优化方法

使用 Wine Quality 数据集，预测葡萄酒的品质。简化为二分类问题， quality ≥ 6 的为高品质葡萄酒（1），quality < 6 的为低品质葡萄酒（0）

网格搜索调优

贝叶斯优化

5、实战：通过 XGBoost 实现广告分类器

互联网广告数据集： Internet Advertisements Data Set

• 总共包含 3279 张图片，其中 2820 张为正常网页内容，459 张为广告。每个样本包含 1558 个特征，其中包含 3 个连续特征，分别为 height、width 和 ratio，其他均为二值特征。另外，样本还有一个字段用于标明该样本是否为广告（ad.—广告，nonad.—非广告）

XGBoost_ADs_classifier.ipynb