关键词：

目录

• xgboost
  • CART(Classify and Regression Tree)
  • GBDT(Gradient Boosting Desicion Tree)
    • GB思想(Gradient Boosting)
    • DT树(Desicion Tree)
    • 横空出世的前向分步算法
    • GB再解释
    • GBDT
  • 大BOSS——xgboost
    • 训练xgboost
    • xgboost模型
    • 目标函数
    • 正则化项处理
    • 理论终章
    • 最终章-拨开云雾见月明
    • 多说一嘴

xgboost

xgboost是一个监督模型，它对应的模型就是一堆CART树，即由CART树组成的随机森林。预测的最终结果是由随机森林中的所有CART树的预测分数相加。
总而言之xgboost的想要解决的问题是通过前t-1棵的预测值加和我们是否能算出第t棵树的最优预测值？

CART(Classify and Regression Tree)

此处不多赘述，决策树一章会有较多描述。简而言之，CART就是既可以做分类又可以做回归的树。无论是做分类还是做回归他的叶节点(预测结果)都会有一个权重值(分数)，而不是一个确定的类别。不清楚CART树不影响你理解xgboost。

GBDT(Gradient Boosting Desicion Tree)

GB思想(Gradient Boosting)

GB通过迭代多棵树共同决策，并且每一棵树学的是之前所有树的预测值的总和与真实值之间的残差，残差值=真实值-之前所有树的结论和。例如nick的年龄是25岁，第一棵树预测年龄是12岁，相差13岁，即残差值为13；那么第二棵树我们把nick的年龄设置为13岁去学习，如果第二棵树真的能把nick分到13岁的叶子节点，那累加两棵树的预测值加和就是nick的真实年龄25岁；如果第二棵树的结论是10岁，仍存在3岁的残差，第三棵树nick的年龄就设置为3岁去学习，继续重复上述过程学习，不断逼近真实值……

DT树(Desicion Tree)

DT树称为回归树，它不是分类树，类似CART树

横空出世的前向分步算法

前向分步算法：每一颗树的预测值都和上一棵树有关系

# (T(x, heta_m))表示第m棵决策树预测的值；( heta_m)为第m棵决策树的参数；(M)表示决策树的总个数；(f_m(x))是第m棵决策树的预测值；(f_M(x))即所有预测数的预测值总和，即最终预测结果

(f_0(x)=0)

(f_1(x)=f_0(x)+T(x; heta_1))

(cdots)

(f_m(x)=f_m-1(x)+T(x, heta_m),m=1,2,cdots,M)

(f_M(x)=sum_m=1^MT(x; heta_m))

GB再解释

# (L)是关于( heta_m)的自定义代价函数，类似于线性回归的代价函数，即在已知真实值和预测值的情况下求最优回归系数( heta_m)；(haty_m)是第m棵决策树的预测值

(J( heta_m)=sum_m=1^NL(y_m,haty_m))

代入前向分步算法的结论(f_m(x)=f_m-1(x)+T(x, heta_m),m=1,2,cdots,M)

(J( heta_m)=sum_i=1^NL(y_m,f_m-1(x_i)+T(x_m; heta_m)))

由上述代价函数可以求出最优解( heta_M?)，即第m颗数的参数

我们假设(L)代价函数使用的是MSE(均方误差)：(L(y,haty)=(y-haty)^2)，既得

(L(y_m,f_m-1(x)+T(x; heta_m)))

(=(y-f_m-1(x)-T(x; heta_m))^2)

代入(r=y-f_m-1(x))(第m颗数和m-1棵树的残差值)得

((y-f_m-1(x)-T(x; heta_m))^2=(r-T(x; heta_m))^2)

GBDT

后记：暂时没时间解释GBDT，GBDT是一阶泰勒展开，xgboost是二阶泰勒展开，其中细节我下次会写一篇专门来介绍GBDT，但是上述的介绍需要看，因为GB和DT是GBDT的基础也是xgboost的基础。

# TODO 哈哈哈！

大BOSS——xgboost

训练xgboost

假设我们获取了xgboost的模型和它的目标函数，现在我们的任务就是最小化目标函数(J( heta))找到最佳的( heta)，但是这个参数是什么呢？xgboost由一堆CART树组成，因此这个参数很明显存在于每颗CART树中。但是CART树的参数又是什么呢？CART树如果被确定之后，子节点是可以丢掉的，剩下的只有每一个叶子节点以及每一个叶子节点上的分数，这就是CART树的参数即xgboost的参数，还是不清楚继续往下看。

xgboost模型

我们借鉴前向分步算法和GB的思想优化我们的M棵树，其中(haty_i^(t))表示第t棵树的预测值；(f_m(x_i))表示第m棵CART树在(x=x_i)的值，即这棵树对应的叶节点的值

(haty_i^(0)=0)

(haty_i^(1)=0+f_1(x_i)=haty_i^(0)+f_1(x_i))

(haty_i^(2)=0+f_1(x_i)+f_2(x_i)=haty_i^(1)+f_2(x_i))

(cdots)

(haty_i^(t)=sum_m=1^tf_m(x_i)=haty_i^(t-1)+f_t(x_i))

假设我们有M棵树，由此我们可以得到一个关于xgboost关于某个(y_i)的预测值(haty_i)的模型，即

(haty_i=sum_m=1^Mf_m(x_i))

目标函数

通过真实值和预测值以及xboost模型我们能得到一个目标函数，该目标函数假设存在一个(L)代价函数和一个正则项(sum_i=1^tOmega(f_k))(类似于线性回归的L1、L2正则化，之后会详细解释，此处是t棵树的正则化项加和)，现在假设我们有t棵树，n个训练样本，既得一个目标函数

(J( heta)=sum_i=1^nL(y_i^t,haty_i^(t)))+sum_i=1^tOmega(f_i))

如果我们假设(C)是t-1棵树的正则化项加和，并且代入xgboost的模型，得

(J( heta)=sum_i=1^nL(y_i^t,haty_i^(t-1)+f_t(x_i))+Omega(f_t)+C)

泰勒展开式:(f(x+Deltax)approxf(x)+f'(x)Deltax+frac12f''(x)Deltax^2)

假设(f(x)=haty_i^(t-1))

假设(Delta=f_t(x_i))

假设(gi=partial_haty_i^(t-1)L(y_i^t,haty_i^(t-1)))

假设(hi=partial_haty_i^(t-1)^2L(y_i^t,haty_i^(t-1)))

在这些假设的基础上，我们假设存在一个代价函数(L)，我们可以把(J( heta))泰勒二阶展开：

(J( heta)=sum_i=1^nL(y_i^t,haty_i^(t)))+sum_i=1^tOmega(f_i))

(=sum_i=1^nL(y_i^t,haty_i^(t-1)+f_t(x_i))+Omega(f_t)+C)

(=sum_i=1^n[L(y_i^t,haty_i^(t-1))+g_if_t(x_i)+frac12h_if_t^2(x_i)]+Omega(f_t)+C)

(y_i^t)和(haty_i^(t-1))已知，即(L(y_i^t,haty_i^(t-1)))是一个常数项(因为我们假设了这个代价函数(L)是已知的一个代价函数，可以是MSE，可以是MSA，可以是任何一个已知的代价函数)；(C)是前t-1棵树的正则化项加和，也是一个常数，这两个常数项对目标函数求最小值无意义，因此我们可以去掉，既得

(J( heta)=sum_i=1^n[g_if_t(x_i)+frac12h_if_t^2(x_i)]+Omega(f_t))

现在如果我们假设损失函数(L)使用的是MSE，那么上述式子会变成：

(J( heta)=sum_i=1^n(y_i^t-(haty_i^(t-1)+f_t(x_i)))^2+Omega(f_t)+C)

(=sum_i=1^n((y_i^t-haty_i^(t-1))-f_t(x_i))^2+Omega(f_t)+C)

(=sum_i=1^n[(y_i^t-haty_i^(t-1))^2-2(y_i^t-haty_i^(t-1))f_t(x_i)+f_t(x_i)^2]+Omega(f_t)+C)

去掉常数项可以得到

(J( heta)=sum_i=1^n[-2(y_i^t-haty_i^(t-1))f_t(x_i)+f_t(x_i)^2]+Omega(f_t))

如果你代入验证很明显可以发现我们使用泰勒展开式得到的式子是没有问题的

其实走到这里我们的xgboost已经算是完结了，是不是忘了我们在做什么，哈哈！我们在做的是通过前t-1棵的预测值加和我们是否能算出第t棵树的最优预测值

正则化项处理

如线性回归的正则化项一样，你可以使用L1正则化，你也可以使用L2正则化……你高兴就行。这里我就讲讲我对xgboost使用的正则化项。

正则化前我们先对CART树做处理

假设一棵树有T个叶子节点，这T个叶子节点组成了一个T维向量(w)，而(q(x))是一个映射，用来将样本映射成1到T的某个值，即(q(x))表示了CART树的结构，(w_q(x))表示了这棵树对样本x的预测值

(f_t(x)=w_q(x),winR^T,a:R^d ightarrow1,2,cdots,T)

由此我们可以假设xgboost的正则化项

(Omega(f_t)=gammaT+frac12lambdasum_j=1^Tw_j^2)

(gamma)和(lambda)是我们自定义的一个数(类似线性回归的学习率)，如果(gamma)越大，表示希望获得结构简单的树，因为(gamma)越大对叶子节点多的树惩罚更大；(lambda)越大也是如此。

至于选择这个正则化项的原因，自己百度"奥卡姆剃刀"，哈哈哈~

理论终章

这个时候我们有了泰勒二阶展开的目标函数，有了自定义的正则化项，我们可以把自定义的正则项代入目标函数中

(J( heta)=sum_i=1^n[g_if_t(x_i)+frac12h_if_t^2(x_i)]+gammaT+frac12lambdasum_j=1^Tw_j^2)

代入(f_t(x)=w_q(x))，得

(J( heta)=sum_i=1^n[g_iw_q(x_i)+frac12h_iw_q(x_i)^2]+gammaT+frac12lambdasum_j=1^Tw_j^2)

这个时候我们需要考虑，如果一个叶子节点上难道只会对应一个样本吗？很明显如果样本很多，一个叶子可能会对应多个样本。因此我们用(I_j)表示一个叶子节点上的所有样本，即(sum_iinI_j)对应一个叶子节点上所有样本的对应值的加和，我们需要计算的就是T个叶子节点上的样本预测值的加和，这也是为什么用(sum_j=1^T)开头的原因

(J( heta)=sum_j=1^T[(sum_iinI_jg_i)w_j+frac12(sum_iinI_jhi)w_j^2]+gammaT+frac12lambdasum_j=1^Tw_j^2)

(=sum_j=1^T[(sum_iinI_jg_i)w_j+frac12(sum_iinI_jhi+lambda)w_j^2]+gammaT)

假设(G_j=sum_iinI_jg_i)

假设(H_j=sum_iinI_jh_i)

(J( heta)=sum_j=1^T[G_jw_j+frac12(H_j+lambda)w_j^2]+gammaT)

通过上式我们可以对目标函数对(w)求偏导找到最优(w^*)

(fracpartialJ(f_t)partialw_J=G_j+(H_j+lambda)w_j==0Rightarroww_j^*=-fracG_jH_j+lambda)

回代最优(w^*)得

(J( heta)^*=-frac12sum_j=1^TfracG_j^2H_j+lambda+gammaT)

因为(J( heta)^*)的推导过程中只和(G_j)和(H_j)和有关，而它们又只和树的结构(q(x))有关，这表示(J( heta)^*)代表了这颗树的结构有多好，值越小，代表这样的结构越好。

最终章-拨开云雾见月明

现在我们假设我们有一家五口的数据，见下表

儿子	妈妈		爸爸	奶奶	爷爷
g1,h1	g2,h2		g3,h3	g4,h4	g5,h5

儿子+妈妈(G_L=g_1+g_2)

爸爸+奶奶+爷爷(G_R=g_3+g_4+g_5)

(J( heta)^*=-frac12sum_j=1^TfracG_j^2H_j+lambda+gammaT)

如果我们不对这5个样本分开，把数据代入(J( heta))，他们的目标值是(frac12frac(G_L+G_R)^2H_L+H_R+lambda)

如果我们把他们五个人按照年龄排列并从空格列分开，即该决策树会有两个叶子，一个叶子会有儿子+妈妈的分数；另一个叶子会有爸爸+奶奶+爷爷的分数

把数据代入(J( heta))目标值是(frac12[fracG_L^2H_L+lambda+fracG_R^2H_R+lambda])

由此可以计算Gain值

(Gain=frac12[fracG_L^2H_L+lambda+fracG_R^2H_R+lambda-frac(G_L+G_R)^2H_L+H_R+lambda]+gamma)

总结：该Gain值是单节点的目标值减去切分后的所有节点的目标值，Gain值如果是正的，并且Gain值越大，就越值得切分，然后不断重复上述过程；如果Gain值是负的，表明切分后目标值变大了。而(gamma)在这里控制目标值的下降幅度。（类似于信息增益，并且相比较传统的GBDT，xgboost使用了二阶泰勒展开，可以更快的在训练集上收敛），虽然xgboost需要计算每个样本的g和h值，但是xgboost使用了并行/多核运算，这都不是问题。

多说一嘴

其实聪明的同学已经发现了我们的( heta)这个参数完全可以看成(f_t)，它表示的是第t颗树的结构，也就可以看成我们的( heta)呀？不是吗？嘻嘻，你仔细思考下。当然(f_t?)也是我们自己定义的。哈哈。
最后多说一嘴，xgboost成型库已经很牛逼了，你只需要会调参就行了，看到这里也不会让你白看，你真的能看懂并理解，他人调参需要1000次，你可能10次就解决了。

不多说，此处需要掌声！！！

吴裕雄python机器学习——集成学习梯度提升决策树gradientboostingclassifier分类模型(代码片段)

importnumpyasnpimportmatplotlib.pyplotaspltfromsklearnimportdatasets,ensemblefromsklearn.model_selectionimporttrain_test_splitdefload_data_classification():‘‘‘加载用于分类问题的数据集‘‘‘#使用scikit-learn自带的digits数据 查看详情

吴裕雄python机器学习——集成学习梯度提升决策树gradientboostingregressor回归模型(代码片段)

importnumpyasnpimportmatplotlib.pyplotaspltfromsklearnimportdatasets,ensemblefromsklearn.model_selectionimporttrain_test_splitdefload_data_regression():‘‘‘加载用于回归问题的数据集‘‘‘#使用scikit-learn自带的一个糖尿病病人的数据集d 查看详情

spark2.0机器学习系列之6：gbdt（梯度提升决策树）gbdt与随机森林差异参数调试及scikit代码分析

概念梳理GBDT的别称　GBDT(GradientBoostDecisionTree),梯度提升决策树。   GBDT这个算法还有一些其他的名字，比如说MART(MultipleAdditiveRegressionTree)，GBRT(GradientBoostRegressionTree)，TreeNet等，其实它们都是一个东西（参考自wikipedia–G... 查看详情

机器学习--决策树

 基本流程:　　决策树:　　　　根结点:属性测试，包含样本全集　　　　内部结点:属性测试，根据属性测试的结果被划分到子结点中　　　　叶结点：决策结果　　划分选择:如何选择最优划分属性。目标是结点的"纯度"越... 查看详情

《机器学习实战》-决策树(代码片段)

目录决策树决策树简介决策树的构造信息增益划分数据集递归构建决策树在Python中使用Matplotlib注解绘制树形图Matplotlib注解构造注解树测试和存储分类器测试算法：使用决策树执行分类使用算法：决策树的存储示例：使用决策树... 查看详情

机器学习—adaboost和梯度提升树gbdt

1、Adaboost算法原理，优缺点：　　理论上任何学习器都可以用于Adaboost.但一般来说，使用最广泛的Adaboost弱学习器是决策树和神经网络。对于决策树，Adaboost分类用了CART分类树，而Adaboost回归用了CART回归树。　　Adaboost算法可以... 查看详情

机器学习_决策树(代码片段)

       查看详情

机器学习实战教程：决策树实战篇(代码片段)

一、前言上篇文章机器学习实战教程（二）：决策树基础篇_M_Q_T的博客-CSDN博客讲述了机器学习决策树的原理，以及如何选择最优特征作为分类特征。本篇文章将在此基础上进行介绍。主要包括：决策树构建决... 查看详情

机器学习之路--决策树(代码片段)

...使用不熟悉的数据集合，并从中提取一系列规则，在这些机器根据数据集创建规则是，就是机器学习的过程。二，相关知识1决 查看详情

机器学习——决策树(代码片段)

1、介绍决策树是一种依托决策而建立起来的一种树。在机器学习中，决策树是一种预测模型，代表的是一种对象属性与对象值之间的一种映射关系，每一个节点代表某个对象/分类，树中的每一个分叉路径代表某个可能的属性值... 查看详情

机器学习算法学习02：决策树的学习以及应用决策树解决cora数据集论文分类问题(代码片段)

机器学习算法学习02：决策树的学习以及应用决策树解决Cora数据集论文分类问题文章目录机器学习算法学习02：决策树的学习以及应用决策树解决Cora数据集论文分类问题1.前言2.算法分析2.1算法概述2.2算法优化3.算法代码3.... 查看详情

机器学习—决策树(代码片段)

一、原理部分：还是图片显示~  二、sklearn实现1、回归树importpandasaspdimportnumpyasnpimportmatplotlib.pyplotaspltimportmatplotlibasmplimportseabornassnsmpl.rcParams[‘font.sans-serif‘]=[u‘SimHei‘]mpl.rcParams[‘axe 查看详情

机器学习实战之一---简单讲解决策树(代码片段)

机器学习实战之一---简单讲解决策树https://blog.csdn.net/class_brick/article/details/78855510 前言：本文基于《机器学习实战》一书，采用python语言，对于机器学习当中的常用算法进行说明。  一、综述定义：首先来对决策树进... 查看详情

机器学习面试问答：决策树如何进行剪枝？剪枝的方法有哪些？

决策树如何进行剪枝？分为预剪枝和后剪枝。预剪枝的思想是在树中结点进行扩展之前，先计算当前的划分是否带来模型泛化能力的提升，如果不能，则不再继续生长子树。预剪枝对何时停止决策树的生长有几种... 查看详情

详解决策树-剪枝十分钟机器学习系列笔记

 决策树生成算法递归地产生决策树，直到不等你继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，模型结构过于复杂，即出现过拟合现象直接来看优秀的决策树一般要求... 查看详情

决策树代码《机器学习实战》

22:45:172017-08-09KNN算法简单有效，可以解决很多分类问题。但是无法给出数据的含义，就是一顿计算向量距离，然后分类。决策树就可以解决这个问题，分类之后能够知道是问什么被划分到一个类。用图形画出来就效果更好了，这... 查看详情

机器学习实战基础（二十八）：决策树概述(代码片段)

概述决策树是如何工作的 决策树（DecisionTree）是一种非参数的有监督学习方法，它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。决策树算法容易理解，适... 查看详情

机器学习回归决策树(代码片段)

回归决策树1.原理概述2.算法描述3.简单实例3.1实例计算过程3.2回归决策树和线性回归对比4.小结1.原理概述上篇文章已经讲到，关于数据类型，我们主要可以把其分为两类，连续型数据和离散型数据。在面对不同数据... 查看详情