# XGBoost * Xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）。 * xgboost在目标函数中显示的加上了正则化项，正则化项与树的叶子节点的数量T和叶子节点的值有关。 ## 1）定义结构函数 > 就是把决策树看作函数的一个抽象式子，给定x，返回其叶子节点的函数。T为叶子节点数。w为叶子节点输出 > > 定义q(x)：其能返回x索引的叶子节点序号； > > Wq(x)：返回x索引序号的索引值 > > 这个后面用到 > > $$\Omega$$为结构损失，这么定义是巧妙的，后面用到 $$ \begin{aligned} \&f\_t(x)=w\_{q(x)},w \in R^T,q:R^d \in { 1,2,...,T}\\ &\Omega(f\_t)=\gamma T+\frac{1}{2}\sum\_{j=1}^T w\_j^2\end{aligned} $$ 引用图： ![img](https://img-blog.csdnimg.cn/20190226112712193.png) ![](/files/-Lq7QTcDUkNwj9SKc-4a) ## 2）输出函数的叠加形式 > 就是一轮一轮的提升，累加，每次新的一轮都是在前面所有轮基础上改进的，这个看得懂吧？ $$ \begin{split}\hat{y}\_i^{(0)} &= 0\\\hat{y}\_i^{(1)} &= f\_1(x\_i) = \hat{y}\_i^{(0)} + f\_1(x\_i)\\\hat{y}\_i^{(2)} &= f\_1(x\_i) + f\_2(x\_i)= \hat{y}\_i^{(1)} + f\_2(x\_i)\\&\dots\\\hat{y}*i^{(t)} &= \sum*{k=1}^t f\_k(x\_i)= \hat{y}\_i^{(t-1)} + f\_t(x\_i)\end{split} $$ ## 3）第 t 轮的目标（损失）函数 > 两部分损失：（左）**经验损失**+（右）**结构损失** > > 等价于：**前t-1轮的经验损失**+**本轮的结构损失**+**前t-1轮的结构损失**（为常数，因为已经知道了） > > 训练n为样本数 $$ \begin{split}\text{Obj}^{(t)} & = \sum\_{i=1}^n l(y\_i, \hat{y}*i^{(t)}) + \sum*{i=1}^t\Omega(f\_i) \ & = \sum\_{i=1}^n l(y\_i, \hat{y}\_i^{(t-1)} + f\_t(x\_i)) + \Omega(f\_t) + constant\end{split} $$ > 其中预测损失函数，常用有： * 平方损失（用于回归）：$$L(\theta) = \sum\_i (y\_i-\hat{y}\_i)^2$$ * Logistic损失（用于分类）：$$L(\theta) = \sum\_i\[ y\_i\ln (1+e^{-\hat{y}\_i}) + (1-y\_i)\ln (1+e^{\hat{y}\_i})]$$ > 如果，我们考虑使用平方误差作为损失函数，公式可改写为： $$ \begin{split}\text{Obj}^{(t)} & = \sum\_{i=1}^n (y\_i - (\hat{y}*i^{(t-1)} + f\_t(x\_i)))^2 + \sum*{i=1}^t\Omega(f\_i) \ & = \sum\_{i=1}^n \[2(\hat{y}\_i^{(t-1)} - y\_i)f\_t(x\_i) + f\_t(x\_i)^2] + \Omega(f\_t) + constant\end{split} $$ **（重要开始了！！）** 我们可以采用如下的**泰勒展开近似来定义一个近似的目标函数**，方便我们进行这一步的计算： $$ f(x+\Delta x)\simeq f(x)+f^{'}(x)\Delta x+\frac{1}{2} f^{''}(x)\Delta x^2 $$ > 此时目标函数为： $$ \text{Obj}^{(t)} = \sum\_{i=1}^n \[l(y\_i, \hat{y}\_i^{(t-1)}) + g\_i f\_t(x\_i) + \frac{1}{2} h\_i f\_t^2(x\_i)] + \Omega(f\_t) + constant $$ > 其中缩写的是损失函数的1、2阶导数 $$ \begin{aligned} g\_i= \partial\_{\hat{y}\_i^{(t-1)}} l(y\_i, \hat{y}*i^{(t-1)})\\ h\_i = \partial*{\hat{y}\_i^{(t-1)}}^2 l(y\_i, \hat{y}\_i^{(t-1)}) \end{aligned} $$ > 如果移除掉常数项（就是前t-1轮的损失，以及结构），此时都是确定的，因此是常数了 > > 发现新目标函数有个明显的特点：它**只依赖于每个数据点的在误差函数上的一阶导数和二阶导数** ![\sum\_{i=1}^n \[g\_i f\_t(x\_i) + \frac{1}{2} h\_i f\_t^2(x\_i)\] + \Omega(f\_t)](http://www.zhihu.com/equation?tex=%5Csum_%7Bi%3D1%7D%5En+%5Bg_i+f_t%28x_i%29+%2B+%5Cfrac%7B1%7D%7B2%7D+h_i+f_t%5E2%28x_i%29%5D+%2B+%5COmega%28f_t%29) **把n个样本的累加，转为遍历所有叶子节点** > （因为样本都在叶子节点下面，遍历每个叶子、遍历每个叶子节点下面的多个样本，等价于遍历所有样本啊，$$w\_j$$为第j叶子节点输出） > > （记$$I\_j$$为叶子节点 j 内样本集合） > > （第二步：函数f变成结构wq，同时展开结构损失） > > （第三步：变成遍历T个节点） $$ \begin{aligned} Obj^{(t)} &\approx \sum\_{i=1}^n\[g\_if\_x(x\_i)+\frac{1}{2}+h\_if\_t^2(x\_i)]+\Omega(f\_t)\\ &=\sum\_{i=1}^n\[g\_i w\_{q\_{(x\_i)}}+\frac{1}{2}+h\_i w\_{q\_{(x\_i)}}^2]+\gamma T +\lambda \frac{1}{2} \sum\_{j=1}^Tw\_j^2\\ &=\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{aligned} $$ **把叶子节点内多个样本的1、2阶导数定义成一个各自的变量** > Gj为j叶子节点的1阶导数 > > Hj为j叶子节点的2阶导数 $$ G\_j=\sum\_{i \in I\_j}g\_i \space ,H\_j=\sum\_{i \in I\_j}h\_i $$ 则有： **这就是最终的损失函数** $$ \begin{aligned} Obj^{(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\\ &=\sum\_{j=1}^T\[G\_j w\_j+\frac{1}{2}(H\_j+\lambda)w\_j^2]+\gamma T \end{aligned} $$ ## 4）结构评价函数 对3）中的损失函数，j个叶子节点的输出wj偏导，求极小值： $$ \begin{aligned} &\frac{\partial (\sum\_{j=1}^T\[G\_j w\_j+\frac{1}{2}(H\_j+\lambda)w\_j^2]+\gamma T)}{\partial w\_j} \\ &=\frac{\partial \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}{\partial w\_j} \\ &=\sum\_{i \in I\_j}g\_i+(\sum\_{i \in Ij}h\_i+\lambda)w\_j\\ &=0\\ \&so:w\_j=-\frac{\sum\_{i \in I\_j}g\_i}{\sum\_{i \in Ij}h\_i+\lambda}=-\frac{G\_j}{H\_j+\lambda} \end{aligned} $$ 代入原函数，得到**只与结构q下面叶子节点（1、2阶导数）有关的函数**（什么东西？就是q(树结构)确定时，这个函数是确定的。问题是q不确定，所以后面转为反向计算其极小值时的最佳结构q，或者**根据这个求得的值评价这个结构q优劣**）类似于决策树寻找分裂时的不纯度指标，且计作新的$$L\_t(q)$$： $$ \begin{aligned} Obj^{(t)}=&\sum\_{j=1}^T\[G\_j w\_j+\frac{1}{2}(H\_j+\lambda)w\_j^2]+\gamma T\\ &=\sum\_{j=1}^T\[G\_j (-\frac{G\_j}{H\_j+\lambda})+\frac{1}{2}(H\_j+\lambda)(-\frac{G\_j}{H\_j+\lambda})^2]+\gamma T\\ as :L\_t(q)&=-\frac{1}{2}\sum\_{i=1}^T(\frac{G\_j}{H\_j+\lambda})+\gamma T\\ \end{aligned} $$ 假如结构q是这个样子，那么就能求出值了（认为是这个结构的分数。越小的时候这个结构越好） 不过这里不符合直觉，既然是分数，就越大越好吧，所有通常取个-1，变成相反的$$-L\_t(q)$$，记住，这里换了，此后评价按这个来，**分数越大的结构越好**。 下面5）开始讲例子 ## 5）最佳分裂办法 怎么分： > XGBoost是一层层往下分的 > > 最初只有根节点，1个叶子节点，包含整个的训练集样本 > > 好了，这个时候怎么分裂为二变成3个节点，两个叶子节点呢？ > > 这个过程清楚了，其它所有节点都这样递归下去就行了 先讲个例子： > 给定（你设定的）损失函，数就能计算出一二阶导数，进而代入可求得叶子节点的G、H > > 那么这个树q的分数就可以唯一确定了，计算$$-L\_t(q)$$即可 > > 如图T=6，叶子节点是8、9、5、6、10、11 > > 然后直接计算4）步中那个评价函数即可 ![](https://img-blog.csdnimg.cn/20190226123446478.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nNDI1Nzc2MDI0,size_16,color_FFFFFF,t_70) > 假设现在我们要对节点9进行分裂 > > 假设我们通过某指标划分，把9中的数据划分成左右2个部分9L/9R了，记为节点12,13（划分方式，怎么划分为两个数据集，[参考CART树](https://blog.csdn.net/jiang425776024/article/details/87644983)的划分方式） > > 如图T=7，叶子节点是8、12\13、5、6、10、11 ![img](https://img-blog.csdnimg.cn/20190226124033367.png) > 那么现在我要比较两个树的分数了，减法嘛，小学生都知道 > > 我们记减法后的结果为Gain > > > 显然这是个数Gain>0意味着划分后的结构分数更高，Gain=0意味着划分不划分都一样，Gain<0意味着划分后变差了 > > 请详细看最后那步的结果，最终两颗树分数的相减结果，只与划分点9有关 > > > 这也很符合常识，因为这两棵树仅仅在9那里有区别 > > > > 最后一步的第3项之所以能这样展开，是因为显然有这样的关系：$$set(9L)+set(9R)=set(9),H\_{9L}+H\_{9R}=H\_9,G\_{9L}^2+G\_{9R}^2=G\_{9}^2$$ ![img](https://img-blog.csdnimg.cn/20190226124750300.png) 这上面那个关系就是最终的分裂标准、类型决策树信息增益 $$\lambda$$**调参阀门** > 显然，Gain>=0）显然这也是个炼丹术。 > > 称呼这个$$\gamma$$为新加入叶子节点引入的复杂度代价 > > > （因为每次划分后节点数增1，而XGBoost的损失评估考虑进去了模型复杂度），**它的值越大，表示我们对切分后目标下降幅度要求越严**。 至此XGBoost的类似决策树的Gain证明、过程、意义已经说完（好多资料真的都不说的，看了也看不懂） **现在名正言顺的导出，很多资料没说以上那么多为什么的Gain** ​ 上面例子只是讲分裂9号叶子节点的，难道其它的不一样吗？ > 所有可以写成通用形式 > > > L、R表示分裂的那个点的下一层，左边、右边的样本集合 > > > > $$\frac{G\_L^2}{H\_L+\lambda}$$代表左子树分数，$$\frac{G\_R^2}{H\_R+\lambda}$$代表右子树分数，$$\frac{(G\_L+G\_R)^2}{H\_L+H\_R+\lambda}$$代表不分割时我们可以获得的分数 > > > > $$\gamma$$为新加入叶子节点引入的复杂度代价。 > > 显然： > > > 我们希望划分后的这个Gain越大越好，因为这样就意味着划分后在的树结构$$q\_{t+1}$$比$$q\_t$$更好 > > > > 通常节点划分后可能有很多个属性的很多个值的位置划分都能让这个分数Gain>0，显然，我们要取这些分数里面最大的，作为当前节点的划分 $$ Gain=\frac{1}{2}\[\frac{G\_L^2}{H\_L+\lambda}+\frac{G\_R^2}{H\_R+\lambda}-\frac{(G\_L+G\_R)^2}{H\_L+H\_R+\lambda}]-\lambda $$ （重点）这里需要提的是，显然这样**计算最佳划分的过程是可以并行的** > 节点j下所有样本xi的hi,gi可以**独立，并行**的算出来，得到Gj和Hj > > 扫描一遍时，遍历每个属性的每个属性值也只需要对改变的那一小部分左运算 > > > 离散属性时划分为：属于此属性的a值的集合（左集）、此属性非a值的集合（右集），类推 > > > > 连续的值划分为：把低于这个属性的a值的为一个集合（左集），大于等于此属性的a值的为一个集合（右集） > > 计算时只需要关注（左集）划入划出到（右集）的样本即可：划入GjL+=gi，划出GjL-=gi，最后GjR=Gj-GjL ## 分裂流程 ![](/files/-LqAJNRUO5FHSoXhcokV) 上面只是介绍最核心的一些原理，具体xgboost在实现时还做了许多优化： > 在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法：大致的思想是根据百分位法**列举几个可能成为分割点的候选者**，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。 > > xgboost考虑了训练数据为稀疏值的情况，可以为**缺失值或者指定的值指定分支的默认方向**，这能大大提升算法的效率，paper提到50倍。 > > **特征列排序后以块的形式存储在内存中**，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。 > > 按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。 > > xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。 使用教程： 全部参数介绍： ## 回归使用 ```python import numpy as np import xgboost as xgb from xgboost import plot_importance from matplotlib import pyplot as plt from mpl_toolkits.mplot3d import Axes3D from sklearn.model_selection import train_test_split fig = plt.figure() plt.rcParams['font.sans-serif'] = ['SimHei'] # 用来正常显示中文标签 plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号 ax = Axes3D(fig) # 构造X数据 X = np.random.randint(0, 7, (2000, 2)) # 构造y数据， y = 1 * x_0 + 2 * x_1 + 3，后面打印参数会发现，是一致的 y = np.dot(X, np.array([1, 2])) + 3 X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0) # 训练模型 model = xgb.XGBRegressor(max_depth=5, learning_rate=0.1, n_estimators=100, silent=True, objective='reg:linear') model.fit(X_train, y_train) # 对测试集进行预测 ans = model.predict(X_test) print(ans) ax.scatter(X_train[:, 0], X_train[:, 1], y_train, marker='o') ax.plot(X_test[:, 0], X_test[:, 1], ans) # 计算准确率 cnt1 = 0 cnt2 = 0 for i in range(len(y_test)): if abs(ans[i] - y_test[i])<0.1: cnt1 += 1 else: cnt2 += 1 print("Accuracy: %.2f %% " % (100 * cnt1 / (cnt1 + cnt2))) # 显示重要特征 plot_importance(model) plt.show() ``` ## 分类使用 ```python from sklearn.datasets import load_iris import xgboost as xgb from xgboost import plot_importance from matplotlib import pyplot as plt from sklearn.model_selection import train_test_split # read in the iris data iris = load_iris() X = iris.data y = iris.target X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0) # 训练模型 model = xgb.XGBClassifier(max_depth=5, learning_rate=0.1, n_estimators=160, silent=True, objective='reg:logistic') model.fit(X_train, y_train) # 对测试集进行预测 ans = model.predict(X_test) # 计算准确率 cnt1 = 0 cnt2 = 0 for i in range(len(y_test)): if ans[i] == y_test[i]: cnt1 += 1 else: cnt2 += 1 print("Accuracy: %.2f %% " % (100 * cnt1 / (cnt1 + cnt2))) # 显示重要特征 plot_importance(model) plt.show() ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/ml/ji-cheng/xgboost.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.