什么是 XGBoost

XGBoost 是陈天奇等人开发的一个开源机器学习项目，高效地实现了 GBDT 算法并进行了算法和工程上的许多改进。XGBoost本质上还是一个GBDT(Gradient Boosting Decision Tree)，但是将速度和效率发挥到极致，所以叫 X (Extreme) GBoosted。

TREE BOOSTING IN A NUTSHELL

Regularized Learning Objective

给定一个数据集 D 中有 n 个样本，每个样本有 m 维特征。通过训练数据集 D，我们得到 K 棵树。这 K 棵树累加的值为我们的预测值。

其中fk(Xi)是样本Xi在第 k 棵树的叶子上的权值。因此我们也可以这样定义。

GBDT 通过经验函数最小化来确定预测函数的参数，XGBoost 在经验函数的基础上加上正则化项，其中Ω表示单棵树的正则化，正则化项表征了模型的复杂度，通过选择合适的参数限制模型复杂度，能够避免过拟合。

其中l是可导且凸的损失函数，用来衡量 ŷ 与 y 的相近程度，第二项 Ω 则是正则项，它包含了两个部分，第一个是 γT，这里的T表示叶子结点的数量，γ是超参(gamma 指定了节点分裂所需的最小损失函数下降值)，也就是说如果 γ 越大，那么我们的叶子结点数量就会越小。另外一部分则是L2正则项，通过对叶子结点的权重进行惩罚，使得不会存在权重过大的叶子结点防止过拟合。ω就表示叶子结点的权重。当Ω=0时，剩下的项就是 GBDT 的目标优化函数。

Gradient Tree Boosting

GBDT 通过梯度下降法优化目标函数，梯度下降法是一种启发式优化算法，有可能陷入局部最优解。它们的不同之处是 XGBoost 优化的是经泰勒展开后近似的目标函数，该损失函数的推导如下，设：^yit=y(t−1)+ft(Xi)
表示第 i 个实例在第 t 次迭代上的输出，第 t 次迭代的结果是产生第 t 颗树（boosting tree）。那么对第 t 颗树来说，其需要优化的目标函数将是如下：

对上式进行二阶泰勒展开得到如下的近似目标函数：

其中，gi、hi分别是损失函数在当前模型的一阶和二阶偏导（gradient statistics）。当前模型已知，也就是当前模型对训练数据的误差已知，l(yi−ˆy(t−1))为常量，对目标函数的优化没有影响，移除得到如下的目标函数：

定义叶子结点 j 上的实例集合为Ij=i|q(Xi)=j，对(3)进一步处理、展开可以得到(4)式

在(4)式中，目标函数对叶子结点权重求导，令导数=0，可以得到目标函数的解析最优解

将解析解带入(4)式可以得到目标函数最优值

观察到最优解叶子结点 j 的权重ω∗j其实是跟树的结构有关，换句话说就是训练数据集中有多少以及哪些数据分到叶子结点 j 上面有关，所以论文的后续大部分在讨论怎么确定树结构。论文是用(6)式作为scoring function来衡量树的好坏。树的生成主要是对于选定的 feature 怎么选择切分点，由于 CART 回归树采用二分法进行树生成，也就是对于选定的 feature 只选择一个切分点将数据分到切分点的两边，所以论文采用(7)式衡量切分点的增益。

Shrinkage and Columns Subsampling

除了以上提到了正则项以外，我们还有shrinkage与列采样技术来避免过拟合的出现。
所谓shrinkage就是在每个迭代中树中，对叶子结点乘以一个缩减权重eta。该操作的作用就是减少每颗树的影响力，留更多的空间给后来的树提升。
另一个技术则是采样的技术，有两种，一种是列采样(colsample_bytree和colsample_bylevel)，一种是行采样(subsample)。其中列采样的实现一般有两种方式，一种是按层随机 colsample_bylevel（一般来讲这种效果会好一点），另一种是建树前就随机选择特征 colsample_bytree。

按层随机 colsample_bylevel 的意思就是，每次分裂一个结点的时候，我们都要遍历所有的特征和分割点，从而确定最优的分割点，那么如果加入了列采样，我们会在对同一层内每个结点分裂之前，先随机选择一部分特征，于是我们只需要遍历这部分的特征，来确定最优的分割点。

建树前就随机选择特征 colsample_bytree 就表示我们在建树前就随机选择一部分特征，然后之后所有叶子结点的分裂都只使用这部分特征。

而行采样则是bagging的思想，每次只抽取部分的样本进行训练，而不使用全部的样本，从而增加树的多样性。

SPLIT FINDING ALGORITHMS

Basic Exact Greedy Algorithm

exact greedy algorithm是一种切分点查找算法，如 Algorithm 1 所示。该算法对于每一个 feature，试图枚举出所有可能的切分点，并计算在每一个切分点上的增益，从而选择增益最好的切分点。在 algorithm1 中要枚举出所有的可能的切分点，算法是首先对所有训练数据对 feature k 的取值进行排序，这样就能轻易地枚举出所有的切分点。

Approximate Algorithm

exact greedy algorithm 很强大，但当训练数据量太大以至于无法完全读进内存或者运行在分布式计算资源上，就有问题了。所以论文总结了一种approximate algorithm

针对 feature k 先是根据特征分布的percentile列出了 L 个待选切分点（candidate splitting point），切分点值的集合Sk，之后根据(7)式分别计算这些待选切分点的增益，选择增益最好的切分点。根据 feature k 大小不同——是在训练的一开始就对全部训练数据的 feature k 列出待选切分点还是对分到某个结点上的训练数据的 feature k，approximate algorithm 有两种变体——global、local.

Weight Quantile Sketch

加权分位数（weighted quantile）用于上述提到的待选切分点（percentile）的选择。具体来说，假设有数据集$Dk={(x{1k},h1),(x{2k},h2),···,(x{nk},h_n)}$，表示实例 1、2、…、n 的特征 k 的值和其二阶偏导，则有如(8)所示的rank function，根据该 rank function 选择待选切分点。加权的意思 rank function 是用二阶偏导计算，也就是给每个实例以权重，该权重是实例点的二阶偏导。(8)式 rank function 表示对于特征 k，小于 z 的实例占总数的比重，这里的总数根据 global 还是 local 而定。

根据需要选择的待选切分点数量1/ϵ，我们可以得到分位数Sk.

max_depth最大树深度：当树达到最大深度时则停止建立决策树。
min_child_weight: 最小的样本权重和，样本权重和就是∑hi，当样本权重和小于设定阈值时则停止建树。

∑ni=112hi(fi(Xi)−gi/hi)2+Ω(ft)+constant ，其中gi/hi表示 labels，hi表示样本权重。

Sparsity-aware Split Finding

在实际场景中，数据缺失很常见，如果某实例点的特征值缺失，上述算法无法将该实例点分到任一子结点。对此论文提出了稀疏感知的切分点查找算法。原理大概是对于特征值缺失的实例点，基于这个分裂的评分函数，分别将其分到左右子结点IL和IR两边计算两个评分，计算增益，选择增益最好的划分方式作为该特征缺失情况下的默认划分。

XGBoost 与 GBDT 有什么不同

除了算法上与传统的 GBDT 有一些不同外，XGBoost 还在工程实现上做了大量的优化。总的来说，两者之间的区别和联系可以总结成以下几个方面。

• GBDT是机器学习算法，XGBoost是该算法的工程实现；
• 在使用CART作为基分类器时，XGBoost 显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力；
• GBDT 在模型训练时只使用了代价函数的一阶导数信息，XGBoost 对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数，二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了。这种去耦合增加了 XGBoost 的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归；
• 传统的 GBDT 采用 CART 作为基分类器，XGBoost 支持多种类型的基分类器，比如线性分类器；
• 传统的 GBDT 在每轮迭代时使用全部的数据，XGBoost 则采用了与随机森林相似的策略，支持对数据进行采样；
• 传统的 GBDT 没有设计对缺失值进行处理，XGBoost 能够自动学习出缺失值的处理策略。

工程系统设计上的优化

• 利用列块进行并行计算；
• 缓存处理能力；
• 数据块以外的计算力提高。

XGBoost 重要参数

• booster：gbtree 和 gblinear。gbtree是采用树的结构来运行数据，而gblinear是基于线性模型。
• silent：静默模式，为1时模型运行不输出。
• nthread: 使用线程数，数值型，-1 为使用所有线程。

Booster 参数

控制每一步的 booster(tree/regression)。booster 参数一般可以调控模型的效果和计算代价。我们所说的调参，很这是大程度上都是在调整 booster 参数。

• n_estimator: 也作num_boosting_rounds，这是生成的最大树的数目，也是最大的迭代次数；
• learning_rate: 也作eta，系统默认值为0.3。每一步迭代的步长，太大了运行准确率不高，太小了运行速度慢。一般使用0.1左右；
• min_child_weight: 默认值 1，决定最小叶子节点样本权重和。这个值可以理解为H值，就是损失函数对y(t−1)的二阶导数和，那么如果损失函数是平方函数（回归问题），这个就是 1；如果是对数损失函数（分类问题），导数是 a(1-a)的形式，a 代表sigmoid函数，这样的话当 y 预测值非常大的时候，这个式子的值接近于 0，因此需要设定一个阈值，小于这个阈值就不分裂了。这个值代表所有样本二阶导数的和，和叶子得分不是一个事，如果是回归问题实际代表样本个数，如果是分类问题实际代表 a(1-a)所有样本计算值的加和。这个参数用于避免过拟合，当它的值较大时，可以避免模型学习到局部的特殊样本。举个栗子来说，对正负样本不均衡时的 0-1 分类而言，假设 h 在 0.01 附近，min_child_weight 为 1 意味着叶子节点中最少需要包含 100 个样本，实际是通过控制样本数来控制过拟合的。
• gamma：系统默认为 0,我们也常用 0。在节点分裂时，只有分裂后损失函数的值下降了，才会分裂这个节点。gamma 指定了节点分裂所需的最小损失函数下降值。 这个参数的值越大，算法越保守。因为 gamma 值越大的时候，损失函数下降更多才可以分裂节点。所以树生成的时候更不容易分裂节点。范围: [0,∞]；
• subsample：系统默认为 1。这个参数控制对于每棵树，随机采样的比例。减小这个参数的值，算法会更加保守，避免过拟合。但是，如果这个值设置得过小，它可能会导致欠拟合。 典型值：0.5-1，0.5 代表平均采样，防止过拟合. 范围: (0,1]，注意不可取 0；
• colsample_bytree：系统默认值为 1。我们一般设置成0.8左右。用来控制每棵随机采样的列数的占比(每一列是一个特征)。 典型值：0.5-1，范围: (0,1]；
• colsample_bylevel：默认为 1,我们也设置为 1。这个就相比于colsample_bytree更加细致了，它指的是每棵树每次节点分裂的时候列采样的比例；
• max_depth： 系统默认值为 6，我们常用 3-10 之间的数字。这个值为树的最大深度。这个值是用来控制过拟合的。max_depth 越大，模型学习的更加具体。设置为 0 代表没有限制，范围: [0,∞];
• max_leaf_nodes: 树上最大节点的数量，和上面的那个参数一样，如果定义了这个参数就会忽略掉 max_depth 参数，我们调优还是以 max_depth 为主吧；
• max_delta_step：默认 0,我们常用 0。这个参数限制了每棵树权重改变的最大步长，如果这个参数的值为 0,则意味着没有约束。如果他被赋予了某一个正值，则是这个算法更加保守。通常，这个参数我们不需要设置，但是当各类别的样本极不平衡的时候，这个参数对逻辑回归优化器是很有帮助的;
• lambda:也称 reg_lambda,默认值为 0。权重的L2正则化项(和 Ridge regression 类似)。这个参数是用来控制 XGBoost 的正则化部分的。这个参数在减少过拟合上很有帮助。
• alpha:也称 reg_alpha 默认为 0,权重的L1正则化项(和 Lasso regression 类似)。 可以应用在很高维度的情况下，使得算法的速度更快;
• scale_pos_weight：默认为 1，在各类别样本十分不平衡时，把这个参数设定为一个正值，可以使算法更快收敛。通常可以将其设置为负样本的数目与正样本数目的比值，sum(negative cases) / sum(positive cases) 。
• tree_method: [default=’auto’]有三个可选的值， {‘auto’, ‘exact’, ‘approx’} ，分别对应 贪心算法(小数据集)/近似算法(大数据集) 。

学习目标参数

控制训练目标的表现。我们对于问题的划分主要体现在学习目标参数上。比如我们要做分类还是回归，做二分类还是多分类，这都是目标参数所提供的。

• seed: (default=0)，这个叫随机数种子，这个参数就是为了可以使结果复现。

objective [缺省值=reg:linear]

• reg:linear – 线性回归
• reg:logistic – 逻辑回归
• binary:logistic – 二分类逻辑回归，输出为概率
• binary:logitraw – 二分类逻辑回归，输出的结果为 wTx
• count:poisson – 计数问题的 poisson 回归，输出结果为 poisson 分布。在 poisson 回归中，max_delta_step 的缺省值为 0.7 (used to safeguard optimization)
• multi:softmax – 设置 XGBoost 使用 softmax 目标函数做多分类，需要设置参数 num_class（类别个数）
• multi:softprob – 如同 softmax，但是输出结果为 ndata*nclass 的向量，其中的值是每个数据分为每个类的概率。

eval_metric [缺省值=通过目标函数选择]

• rmse: 均方根误差
• mae: 平均绝对值误差
• logloss: negative log-likelihood
• error: 二分类错误率。其值通过错误分类数目与全部分类数目比值得到。对于预测，预测值大于 0.5 被认为是正类，其它归为负类。 error@t: 不同的划分阈值可以通过 ‘t’进行设置
• merror: 多分类错误率，计算公式为(wrong cases)/(all cases)
• mlogloss: 多分类 log 损失
• auc: 曲线下的面积
• ndcg: Normalized Discounted Cumulative Gain
• map: 平均正确率