王小草【机器学习】笔记--提升之XGBoost工具的应用
笔记整理时间：日
整理者：王小草
欢迎关注：
王小草的FM喜马拉雅主播频道：搜索账号名“好吧我真的叫王草”
王小草的个人微信公众号：bigdataML
王小草的CSDN博客地址：
2016年的最后第三天，终于有阳光，连续一个月的咳嗽终于见好。
这是及其忙碌的一年，忙着适应从学校到社会的血腥，忙着在车水马龙的竞争里立足安身，忙着屈服于又抗争于的生活。
在整理“提升”算法的笔记时，我想每年的自己多像一个基函数，在梯度里不断塑造下一个更好的自己，直到实现目标函数最优才停止迭代。而生活不像函数，至少在百年之前，都不愿停止寻找更优。
1. XGBoost介绍
XGBoost的作者是华盛顿大学陈天奇。
XGBoost是使用梯度提升框架实现的高效，灵活，可移植的机器学习库。它的全称是eXtreme Gradient Boosting,是GDBT的一个C++实现。它将树的生成并行完成，从而提高学习速度。
一般而言，XGBoost的速度和性能优于sklearn.ensemble.GradientBoostingClassifer类。
XGBoost提供了python接口，它在机器学习的竞赛仲纷纷表现出来优异的成绩，其他学者封装了R和Julia等接口。
XGBoost的官网：
github上代码的地址：
2. Ubantu安装XGBoost
在各种系统上的安装官网上有详细介绍：
因为我平时学习与工作环境都是在ubantu上的，本文主要介绍ubantu系统安装XGBoost。
非常简单，就两个命令：
第一步：在github上把XGBoost工程克隆到本地计算机上，可以创建一个专门的目录，然后进入这个目录运行以下命令：
git clone --recursive https:
根据网络的好坏，下载需要一点点时间，我大概是花了5分钟。
第二步：进入工程，然后编译。
cd xgboost
编译的过程大概不到1分钟吧。
编译成功的画面：
我机子上有2个python版本，一个是安装anoconda中带着的python,一个是我自己下载python来单独安装的。我的系统默认的是后者，所以以上安装的XGBoost是安装在默认的python中的。
现在我打开pycharm,输入import xgboost as xgb,并没有红色波浪线的报错，表示可以成功使用了！
3.XGBoost实践
安装好了之后，我们来尝试着学习与使用这个工具。以下介绍一些从简到繁的案例。
3.1 官网get start小案例
官方文档分别给出了4中语言的小例子，这里只讲解python的。
样本数据说明：
读取的数据是工程里自带的数据，在工程目录下的/demo/data/文件夹下。打开数据文件，格式是这样的：
1 3:1 10:1 11:1 21:1 30:1 34:1 36:1 40:1 41:1 53:1 58:1 65:1 69:1 77:1 86:1 88:1 92:1 95:1 102:1 105:1 117:1 124:1
0 3:1 10:1 20:1 21:1 23:1 34:1 36:1 39:1 41:1 53:1 56:1 65:1 69:1 77:1 86:1 88:1 92:1 95:1 102:1 106:1 116:1 120:1
0 1:1 10:1 19:1 21:1 24:1 34:1 36:1 39:1 42:1 53:1 56:1 65:1 69:1 77:1 86:1 88:1 92:1 95:1 102:1 106:1 116:1 122:1
1 3:1 9:1 19:1 21:1 30:1 34:1 36:1 40:1 42:1 53:1 58:1 65:1 69:1 77:1 86:1 88:1 92:1 95:1 102:1 105:1 117:1 124:1
0 3:1 10:1 14:1 22:1 29:1 34:1 37:1 39:1 41:1 54:1 58:1 65:1 69:1 77:1 86:1 88:1 92:1 95:1 98:1 106:1 114:1 120:1
每一行是一个观测样本，第一列是label,后面的列都是特征，一个特征由特征的索引，冒号，特征值组成，列与列之间是用空格隔开的。
在某样本点中没有出现的特征索引，说明该处特征值维0，也就是说，整个数据是一个稀疏的矩阵，所以只存储不为0的数据。
数据读取说明：
直接将path传入xgb.DMtrix（）中，会将数据变成DMtrix的格式，这是一个XGBoost自己定义的数据格式（就像numpy中有ndarray, pandas中有dataframe数据格式一样）。这个格式会将第一列作为label,其余的作为features。
参数说明：
模型中可以传入一些列参数，在训练之前，先把这些参数以map的形式定义好。参数有很多，下面的例子中是最基本的。
每个参数的意义在代码中都有注释，再此不赘述。
import xgboost as xgb
dtrain = xgb.DMatrix('/home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.train')
dtest = xgb.DMatrix('/home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.test')
param = {'max_depth': 2,
'silent': 1,
'objective': 'binary:logistic'}
num_round = 2
watchlist = [(dtest, 'eval'), (dtrain, 'train')]
bst = xgb.train(param, dtrain, num_round, evals=watchlist)
preds = bst.predict(dtest)
y_hat = preds
y = dtest.get_label()
print y_hat
error_count = sum(y != (y_hat & 0.5))
error_rate = float(error_count) / len(y_hat)
print "样本总数：\t", len(y_hat)
print "错误数目：\t%4d" % error_count
print "错误率：\t%.2f%%" % (100 * error_rate)
来看看上面代码的输出：
[14:27:00]
matrix with 143286 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.train
[14:27:00]
matrix with 35442 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.test
[0] eval-error:0.042831 train-error:0.046522
[1] eval-error:0.021726 train-error:0.022263
[ 0... ...,
样本总数：
错误数目：
Process finished with exit code 0
3.2 自定义基函数与损失
在做提升的时候我们一般选取决策树这样的弱预测器来作为基函数，也可以使用逻辑回归。逻辑回归其实本身是一个强分类器，提升强分类器不一定会有更好的表现，但也具体问题具体分析。这个基函数f其实是可以根据实际需求来调整的，当然也可以自己构造。
下面的案例中我们不适用XGBboost自带的基函数，而是自己定义基函数，然后再传入模型中训练。
import xgboost as xgb
import numpy as np
def log_reg(y_hat, y):
p = 1.0 / (1.0 + np.exp(-y_hat))
g = p - y.get_label()
h = p * (1.0-p)
return g, h
def error(y_hat, y):
return 'error', float(sum(y.get_label() != (y_hat & 0.0))) / len(y_hat)
if __name__ == "__main__":
dtrain = xgb.DMatrix('/home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.train')
dtest = xgb.DMatrix('/home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.test')
param = {'max_depth': 2,
'silent': 1}
num_round = 2
watchlist = [(dtest, 'eval'), (dtrain, 'train')]
bst = xgb.train(param, dtrain, num_round, evals=watchlist, obj=log_reg, feval=error)
y_hat = bst.predict(dtest)
y = dtest.get_label()
print y_hat
error = sum(y != (y_hat & 0))
error_rate = float(error) / len(y_hat)
print '样本总数：\t', len(y_hat)
print '错误数目：\t%4d' % error
print '错误率：\t%.2f%%' % (100 * error_rate)
打印的结果：
[14:53:48]
matrix with 143286 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.train
[14:53:48]
matrix with 35442 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.test
[0] eval-error:0.042831 train-error:0.046522
[1] eval-error:0.021726 train-error:0.022263
[-1... ...,
样本总数：
错误数目：
Process finished with exit code 0
显然，模型并不可观，仍然有35个错误的样本点。于是我们需要去调整参数优化模型，比如，将迭代的次数改成3，其他的不变，输出的结果如下，错误率降低到了0.62%
[14:54:55]
matrix with 143286 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.train
[14:54:55]
matrix with 35442 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.test
[0] eval-error:0.042831 train-error:0.046522
[1] eval-error:0.021726 train-error:0.022263
[2] eval-error:0.006207 train-error:0.007063
[-1... ...,
3..8006072
样本总数：
错误数目：
Process finished with exit code 0
再比如，其他不变，只将最大深度max_depth改称3，结果如下，亮瞎眼睛，测试集的误差居然为0了！
[14:57:11]
matrix with 143286 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.train
[14:57:11]
matrix with 35442 entries loaded from /home/cc/PycharmProjects/xgboost/demo/data/agaricus.txt.test
[0] eval-error:0.016139 train-error:0.014433
[1] eval-error:0
train-error:0.001228
[-3... ...,
样本总数：
错误数目：
Process finished with exit code 0
3.3 softmax多分类问题
下面案例介绍一个用sofmax做多分类的问题。还是使用那个家喻户晓的iris数据集，通过一系列特征去预测花的种类，总共有3类。
看一眼数据集的格式是酱紫的，总共有5列，前4列是4个特征，最后一列是label。
可见这个Label是string类型，在输入的模型前，我们需要把它转换成数字作为标识。
5.1,3.5,1.4,0.2,Iris-setosa
4.9,3.0,1.4,0.2,Iris-setosa
7.0,3.2,4.7,1.4,Iris-versicolor
6.4,3.2,4.5,1.5,Iris-versicolor
6.3,3.3,6.0,2.5,Iris-virginica
5.8,2.7,5.1,1.9,Iris-virginica
完整代码：
自己写了一个方法iris_type，目的是将string类型的花名，转换成Float类型的数字标识。
与前面的案例不同，这次我们需要自己去分训练集与测试集，可直接调用方法train_test_split即可。
另外一点与以上案例不同的是系数中’silent’设置为0，表示打印出更多信息，在下面输出的结果中，后面的一大段信息就是这个导致的。
另外，案例中还调用了逻辑回归模型来做对比，发现正确率低于前者。
import xgboost as xgb
import numpy as np
from sklearn.cross_validation import train_test_split
def iris_type(s):
it = {'Iris-setosa': 0, 'Iris-versicolor': 1, 'Iris-virginica': 2}
return it[s]
if __name__ == "__main__":
path = "/home/cc/下载/深度学习笔记/提升/8.数据/4.iris.data"
data = np.loadtxt(path, dtype=float, delimiter=',', converters={4: iris_type})
x, y = np.split(data, (4, ), axis=1)
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=1, test_size=50)
train = xgb.DMatrix(x_train, label=y_train)
test = xgb.DMatrix(x_test, label=y_test)
watch_list = [(test, 'eval'), (train, 'train')]
param = {'max_depth': 3,
'silent': 0,
'objective': 'multi:softmax',
'num_class': 3}
num_round = 3
bsg = xgb.train(param, train, num_round, evals=watch_list)
y_hat = bsg.predict(test)
result = y_test.reshape(1, -1) == y_hat
print 'XGBoost正确率:\t', float(np.sum(result)) / len(y_hat)
print 'END.....\n'
lr = LogisticRegression(penalty='l2')
lr.fit(x_train, y_train.ravel())
y_hat2 = lr.predict(x_test)
result2 = y_test.reshape(1, -1) == y_hat2
print '逻辑回归正确率:\t', float(np.sum(result2)) / len(y_hat2)
print 'END.....\n'
输出的结果：
[0] eval-merror:0.02
train-merror:0.02
[1] eval-merror:0.02
train-merror:0.02
[2] eval-merror:0.04
train-merror:0.01
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 2 extra nodes, 0 pruned nodes, max_depth=1
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 8 extra nodes, 0 pruned nodes, max_depth=3
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 4 extra nodes, 0 pruned nodes, max_depth=2
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 2 extra nodes, 0 pruned nodes, max_depth=1
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 8 extra nodes, 0 pruned nodes, max_depth=3
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 6 extra nodes, 0 pruned nodes, max_depth=2
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 2 extra nodes, 0 pruned nodes, max_depth=1
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 6 extra nodes, 0 pruned nodes, max_depth=3
[15:57:15] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 8 extra nodes, 0 pruned nodes, max_depth=3
逻辑回归正确率:
更多案例请参看：
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？xgboost 算法原理
1、xgboost是什么
基础：GBDT
所属：boosting迭代型、树类算法。
适用范围：分类、回归
优点：速度快、效果好、能处理大规模数据、支持多种语言、支 持自定义损失函数等等。
缺点：发布时间短（2014），工业领域应用较少，待检验
2、基础知识，GBDT
xgboost是在GBDT的基础上对boosting算法进行的改进，内部决策树使用的是回归树，简单回顾GBDT如下：
回归树的分裂结点对于平方损失函数，拟合的就是残差；对于一般损失函数（梯度下降），拟合的就是残差的近似值，分裂结点划分时枚举所有特征的值，选取划分点。
最后预测的结果是每棵树的预测结果相加。
3、xgboost算法原理知识
3.1 定义树的复杂度
把树拆分成结构部分q和叶子权重部分w。
树的复杂度函数和样例：
定义树的结构和复杂度的原因很简单，这样就可以衡量模型的复杂度了啊，从而可以有效控制过拟合。
3.2 xgboost中的boosting tree模型
和传统的boosting tree模型一样，xgboost的提升模型也是采用的残差（或梯度负方向），不同的是分裂结点选取的时候不一定是最小平方损失。
3.3 对目标函数的改写
最终的目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。这么写的原因很明显，由于之前的目标函数求最优解的过程中只对平方损失函数时候方便求，对于其他的损失函数变得很复杂，通过二阶泰勒展开式的变换，这样求解其他损失函数变得可行了。很赞！
当定义了分裂候选集合的时候，可以进一步改目标函数。分裂结点的候选响集是很关键的一步，这是xgboost速度快的保证，怎么选出来这个集合，后面会介绍。
3.4 树结构的打分函数
Obj代表了当指定一个树的结构的时候，在目标上面最多减少多少。(structure score)
对于每一次尝试去对已有的叶子加入一个分割
这样就可以在建树的过程中动态的选择是否要添加一个结点。
假设要枚举所有x & a 这样的条件，对于某个特定的分割a，要计算a左边和右边的导数和。对于所有的a，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL、GR。然后用上面的公式计算每个分割方案的分数就可以了。
3.5 寻找分裂结点的候选集
1、暴力枚举
2、近似方法 ，近似方法通过特征的分布，按照百分比确定一组候选分裂点，通过遍历所有的候选分裂点来找到最佳分裂点。
两种策略：全局策略和局部策略。在全局策略中，对每一个特征确定一个全局的候选分裂点集合，就不再改变；而在局部策略中，每一次分裂 都要重选一次分裂点。前者需要较大的分裂集合，后者可以小一点。对比补充候选集策略与分裂点数目对模型的影响。 全局策略需要更细的分裂点才能和局部策略差不多
3、Weighted Quantile Sketch
陈天奇提出并从概率角度证明了一种带权重的分布式的Quantile Sketch。
4、xgboost的改进点总结
1、目标函数通过二阶泰勒展开式做近似
2、定义了树的复杂度，并应用到目标函数中
3、分裂结点处通过结构打分和分割损失动态生长
4、分裂结点的候选集合通过一种分布式Quantile Sketch得到
5、可以处理稀疏、缺失数据
6、可以通过特征的列采样防止过拟合
xgboost 有很多可调参数，具有极大的自定义灵活性。比如说：
（1）objective [ default=reg:linear ] 定义学习任务及相应的学习目标，可选的目标函数如下：
&reg:linear& &线性回归。
&reg:logistic& &逻辑回归。
&binary:logistic& &二分类的逻辑回归问题，输出为概率。
&multi:softmax& &处理多分类问题，同时需要设置参数num_class（类别个数）
（2）&eval_metric& The choices are listed below，评估指标:
&rmse&: root mean square error
&logloss&: negative log-likelihood
(3)max_depth [default=6] 数的最大深度。缺省值为6 ，取值范围为：[1,&]作者：陈天奇，毕业于上海交通大学ACM班，现就读于华盛顿大学，从事大规模机器学习研究。
注解：truth4sex
编者按：本文是对开源xgboost库理论层面的介绍，在陈天奇原文《梯度提升法和Boosted Tree》的基础上，做了如下注解：1）章节划分；2）注解和参考链接（以蓝色和红色字体标注）。备注：图片可点击查看清晰版。
应 @龙星镖局
兄邀请写这篇文章。作为一个非常有效的机器学习方法，Boosted Tree是数据挖掘和机器学习中最常用的算法之一。因为它效果好，对于输入要求不敏感，往往是从统计学家到数据科学家必备的工具之一，它同时也是kaggle比赛冠军选手最常用的工具。最后，因为它的效果好，计算复杂度不高，也在工业界中有大量的应用。
2. Boosted Tree的若干同义词
说到这里可能有人会问，为什么我没有听过这个名字。这是因为Boosted Tree有各种马甲，比如GBDT, GBRT (gradient boosted regression tree)，MART，LambdaMART也是一种boosted tree的变种。网上有很多介绍Boosted tree的资料，不过大部分都是基于Friedman的最早一篇文章Greedy Function Approximation: A Gradient Boosting Machine的翻译。个人觉得这不是最好最一般地介绍boosted tree的方式。而网上除了这个角度之外的介绍并不多。这篇文章是我个人对于boosted tree和gradient boosting 类算法的总结，其中很多材料来自于我TA UW机器学习时的一份讲义。
3. 有监督学习算法的逻辑组成
要讲boosted tree，要先从有监督学习讲起。在有监督学习里面有几个逻辑上的重要组成部件，初略地分可以分为：模型，参数 和 目标函数。
i. 模型和参数
模型指给定输入如何去预测 输出 。我们比较常见的模型如线性模型（包括线性回归和logistic regression）采用了线性叠加的方式进行预测 。其实这里的预测可以有不同的解释，比如我们可以用它来作为回归目标的输出，或者进行sigmoid 变换得到概率，或者作为排序的指标等。而一个线性模型根据的解释不同（以及设计对应的目标函数）用到回归，分类或排序等场景。参数指我们需要学习的东西，在线性模型中，参数指我们的线性系数。
ii. 目标函数：损失 + 正则
模型和参数本身指定了给定输入我们如何做预测，但是没有告诉我们如何去寻找一个比较好的参数，这个时候就需要目标函数登场了。一般的目标函数包含下面两项
常见的误差函数有 比如平方误差
，logistic误差函数（ ）等。而对于线性模型常见的正则化项有正则和正则。这样目标函数的设计来自于统计学习里面的一个重要概念叫做Bias-variance tradeoff。比较感性的理解，Bias可以理解为假设我们有无限多数据的时候，可以训练出最好的模型所拿到的误差。而Variance是因为我们只有有限数据，其中随机性带来的误差。目标中误差函数鼓励我们的模型尽量去拟合训练数据，这样相对来说最后的模型会有比较少的 bias。而正则化项则鼓励更加简单的模型。因为当模型简单之后，有限数据拟合出来结果的随机性比较小，不容易过拟合，使得最后模型的预测更加稳定。
iii. 优化算法
讲了这么多有监督学习的基本概念，为什么要讲这些呢？ 是因为这几部分包含了机器学习的主要成分，也是机器学习工具设计中划分模块比较有效的办法。其实这几部分之外，还有一个优化算法，就是给定目标函数之后怎么学的问题。之所以我没有讲优化算法，是因为这是大家往往比较熟悉的“机器学习的部分”。而有时候我们往往只知道“优化算法”，而没有仔细考虑目标函数的设计的问题，比较常见的例子如决策树的学习，大家知道的算法是每一步去优化gini entropy，然后剪枝，但是没有考虑到后面的目标是什么。
4. Boosted Tree
i. 基学习器：分类和回归树（CART）
话题回到boosted tree，我们也是从这几个方面开始讲，首先讲模型。Boosted tree 最基本的组成部分叫做回归树(regression tree)，也叫做CART。
上面就是一个CART的例子。CART会把输入根据输入的属性分配到各个叶子节点，而每个叶子节点上面都会对应一个实数分数。上面的例子是一个预测一个人是否会喜欢电脑游戏的 CART，你可以把叶子的分数理解为有多可能这个人喜欢电脑游戏。有人可能会问它和decision tree的关系，其实我们可以简单地把它理解为decision tree的一个扩展。从简单的类标到分数之后，我们可以做很多事情，如概率预测，排序。
ii. Tree Ensemble
一个CART往往过于简单无法有效地预测，因此一个更加强力的模型叫做tree ensemble。
在上面的例子中，我们用两棵树来进行预测。我们对于每个样本的预测结果就是每棵树预测分数的和。到这里，我们的模型就介绍完毕了。现在问题来了，我们常见的随机森林和boosted tree和tree ensemble有什么关系呢？如果你仔细的思考，你会发现RF和boosted tree的模型都是tree ensemble，只是构造（学习）模型参数的方法不同。第二个问题：在这个模型中的“参数”是什么。在tree ensemble中，参数对应了树的结构，以及每个叶子节点上面的预测分数。
最后一个问题当然是如何学习这些参数。在这一部分，答案可能千奇百怪，但是最标准的答案始终是一个：定义合理的目标函数，然后去尝试优化这个目标函数。在这里我要多说一句，因为决策树学习往往充满了heuristic。 如先优化吉尼系数，然后再剪枝啦，限制最大深度，等等。其实这些heuristic的背后往往隐含了一个目标函数，而理解目标函数本身也有利于我们设计学习算法，这个会在后面具体展开。
对于tree ensemble，我们可以比较严格的把我们的模型写成是：
其中每个是一个在函数空间()里面的函数，而对应了所有regression tree的集合。我们设计的目标函数也需要遵循前面的主要原则，包含两部分
iii. 模型学习：additive training
其中第一部分是训练误差，也就是大家相对比较熟悉的如平方误差, logistic loss等。而第二部分是每棵树的复杂度的和。这个在后面会继续讲到。因为现在我们的参数可以认为是在一个函数空间里面，我们不能采用传统的如SGD之类的算法来学习我们的模型，因此我们会采用一种叫做additive training的方式（另外，在我个人的理解里面，boosting就是指additive training的意思）。每一次保留原来的模型不变，加入一个新的函数$f$到我们的模型中。
现在还剩下一个问题，我们如何选择每一轮加入什么呢？答案是非常直接的，选取一个来使得我们的目标函数尽量最大地降低。
这个公式可能有些过于抽象，我们可以考虑当是平方误差的情况。这个时候我们的目标可以被写成下面这样的二次函数：
更加一般的，对于不是平方误差的情况，我们会采用如下的泰勒展开近似来定义一个近似的目标函数，方便我们进行这一步的计算。
当我们把常数项移除之后，我们会发现如下一个比较统一的目标函数。这一个目标函数有一个非常明显的特点，它只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。有人可能会问，这个材料似乎比我们之前学过的决策树学习难懂。为什么要花这么多力气来做推导呢？
因为这样做使得我们可以很清楚地理解整个目标是什么，并且一步一步推导出如何进行树的学习。这一个抽象的形式对于实现机器学习工具也是非常有帮助的。传统的GBDT可能大家可以理解如优化平法残差，但是这样一个形式包含可所有可以求导的目标函数。也就是说有了这个形式，我们写出来的代码可以用来求解包括回归，分类和排序的各种问题，正式的推导可以使得机器学习的工具更加一般。
iv. 树的复杂度
到目前为止我们讨论了目标函数中训练误差的部分。接下来我们讨论如何定义树的复杂度。我们先对于f的定义做一下细化，把树拆分成结构部分和叶子权重部分。下图是一个具体的例子。结构函数把输入映射到叶子的索引号上面去，而给定了每个索引号对应的叶子分数是什么。
当我们给定了如上定义之后，我们可以定义一棵树的复杂度如下。这个复杂度包含了一棵树里面节点的个数，以及每个树叶子节点上面输出分数的$L2$模平方。当然这不是唯一的一种定义方式，不过这一定义方式学习出的树效果一般都比较不错。下图还给出了复杂度计算的一个例子。
v. 关键步骤
接下来是最关键的一步，在这种新的定义下，我们可以把目标函数进行如下改写，其中I被定义为每个叶子上面样本集合
这一个目标包含了个相互独立的单变量二次函数。我们可以定义
那么这个目标函数可以进一步改写成如下的形式，假设我们已经知道树的结构，我们可以通过这个目标函数来求解出最好的，以及最好的对应的目标函数最大的增益
这两个的结果对应如下，左边是最好的，右边是这个对应的目标函数的值。到这里大家可能会觉得这个推导略复杂。其实这里只涉及到了如何求一个一维二次函数的最小值的问题。如果觉得没有理解不妨再仔细琢磨一下
vi. 打分函数计算举例
Obj代表了当我们指定一个树的结构的时候，我们在目标上面最多减少多少。我们可以把它叫做结构分数(structure score)。你可以认为这个就是类似吉尼系数一样更加一般的对于树结构进行打分的函数。下面是一个具体的打分函数计算的例子
vii. 枚举所有不同树结构的贪心法
所以我们的算法也很简单，我们不断地枚举不同树的结构，利用这个打分函数来寻找出一个最优结构的树，加入到我们的模型中，再重复这样的操作。不过枚举所有树结构这个操作不太可行，所以常用的方法是贪心法，每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算
对于每次扩展，我们还是要枚举所有可能的分割方案，如何高效地枚举所有的分割呢？我假设我们要枚举所有 <img src='http://www.52cs.org/wp-content/plugins/latex/cache/tex_06bbdb820ea7a26.gif' style='vertical-align: border: padding-bottom:2' class='tex' alt="x
这样的条件，对于某个特定的分割我们要计算左边和右边的导数和。
我们可以发现对于所有的，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和和。然后用上面的公式计算每个分割方案的分数就可以了。
观察这个目标函数，大家会发现第二个值得注意的事情就是引入分割不一定会使得情况变好，因为我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝， 当引入的分割带来的增益小于一个阀值的时候，我们可以剪掉这个分割。大家可以发现，当我们正式地推导目标的时候，像计算分数和剪枝这样的策略都会自然地出现，而不再是一种因为heuristic而进行的操作了。
讲到这里文章进入了尾声，虽然有些长，希望对大家有所帮助，这篇文章介绍了如何通过目标函数优化的方法比较严格地推导出boosted tree的学习。因为有这样一般的推导，得到的算法可以直接应用到回归，分类排序等各个应用场景中去。
5. 尾声：xgboost
这篇文章讲的所有推导和技术都指导了xgboost /dmlc/xgboost 的设计。xgboost是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包，比常见的工具包快10倍以上。在数据科学方面，有大量kaggle选手选用它进行数据挖掘比赛，其中包括两个以上kaggle比赛的夺冠方案。在工业界规模方面，xgboost的分布式版本有广泛的可移植性，支持在YARN, MPI, Sungrid Engine等各个平台上面运行，并且保留了单机并行版本的各种优化，使得它可以很好地解决于工业界规模的问题。有兴趣的同学可以尝试使用一下，也欢迎贡献代码。
-----------------------------
注解和链接：
: Multiple Additive Regression Trees, Jerry Friedman, KDD 2002 Innovation Award 创新奖 http://www.sigkdd.org/node/362
: Introduction to Boosted Trees, Tianqi Chen
, 2014 http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
: Principles of Data Mining, David Hand et al,2001. Chapter 1.5 Components of Data Mining Algorithms, 将数据挖掘算法解构为四个组件：1）模型结构（函数形式，如线性模型），2）评分函数（评估模型拟合数据的质量，如似然函数，误差平方和，误分类率），3）优化和搜索方法（评分函数的优化和模型参数的求解），4）数据管理策略（优化和搜索时对数据的高效访问）。
: 在概率统计中，参数估计量的评选标准有三：1）无偏性（参数估计量的均值等于参数的真实值），2）有效性（参数估计量的方差越小越好），3）一致性（当样本数从有限个逐渐增加到无穷多个时，参数估计量依概率收敛于参数真值）。《概率论与数理统计》，高祖新等，1999年，7.3节估计量的评选标准
: Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and regression trees. CRC press.
Breiman获KDD 2005 Innovation Award 创新奖
: F是泛函空间，或者叫假设空间；f是函数，或者叫假设。这里的ensemble一共有K个组件/基学习器，他们的组合方式是不带权重的累加。NOTE：【一般boosting里面（如AdaBoost）是有权重叠加 原因是那些权重自然地被吸收到叶子的weight里面去了。】 by Chen Tianqi
: Friedman等（ Friedman, J., Hastie, T., & Tibshirani, R. (2000). Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors). The annals of statistics, 28(2), 337-407. ）在2000年为boosting这种集成学习方法范式提供了一种统计解释，即加性逻辑斯蒂回归。但是他们不能完全解释AdaBoost算法的抗过拟合性。南大周志华等人（http://www.slideshare.net/hustwj/ccl2014-keynote）从统计学习理论的间隔分布出发，较完满的解决了这个问题。
: 这个思想即是AdaBoost等boosting算法的思想：串行生成一系列基学习器，使得当前基学习器都重点关注以前所有学习器犯错误的那些数据样本，如此达到提升的效果。
: 注意，这里的优化搜索变量是（即搜索当前的基学习器f），所以其他不关于的项都被吸纳到const中，如当前的误差损失
: 1). 分别作为要优化的变量的一次系数和二次系数
2). 误差函数对 求导时，即涉及到前个基学习器，因为他们决定了当前的预测结果
: 因为每个数据点落入且仅落入一个叶子节点，所以可以把个数据点按叶子成组，类似于合并同类项，两个数据点同类指的是落入相同的叶子，即这里的指示变量集
: 变量是，关于它的二次函数是：，该函数对变量求导并令其等于0，即得到的表达式。
转载请注明：《
Alexa Rank}