作为一个非常有效的机器学习方法，Boosted Tree是数据挖掘和机器学习中最常用的算法之一。因为它效果好，对于输入要求不敏感，往往是从统计学家到数据科学家必备的工具之一，它同时也是Kaggle比赛冠军选手最常用的工具。Boosted Tree有各种马甲，比如GBDT（Gradient Boosting Decision Tree）, GBRT（Gradient Boosting Regression Tree）以及MART(Multiple Additive Regression Tree)。很多介绍Boosted tree的资料都是源于Friedman的较早的一篇文章[1]。

1. 分类和回归树（CART）

图 1. CART示意图

上面就是一个CART的例子。CART会把输入根据输入的属性分配到各个叶子节点，而每个叶子节点上面都会对应一个实数分数。问题：预测一个人是否会喜欢电脑游戏。可以把叶子的分数理解为这个人喜欢电脑游戏的可能性。CART可以理解为是decision tree的一个扩展。从简单的类标到分数之后，似乎能做更多的事情了（例如概率预测或是排序）。

2. Tree ensemble

同样类比Random Forest的思想，当一棵树解决不了问题时，可以将几棵树联起来。

图2. Tree ensemble示意图

图2的例子中，我们用两棵树来进行预测。我们对于每个样本的预测结果就是每棵树预测分数的和。我们常见的随机森林和boosted tree和tree ensemble有什么关系呢？它们都是ensemble，只是构造模型参数的方法不同。

3. 模型学习

模型中的参数是什么?在tree ensemble中，参数对应了树的结构，以及每个叶子节点上面的预测分数。同样需要先定义合理的目标函数(一般会包括loss function 以及 regularizer )，然后尝试优化目标函数。对于tree ensemble，可以将模型写成为：

其中每个fk对应了一棵regression tree。

采用一种叫做additive training的方式（实际上boosting含义就是指additive training）。如每一次保留原来的模型不变，加入一个新的函数fk到我们的模型中。

图3. Additive training示意图

3.1 目标函数的定义

在图3中，如何选择每一轮加入什么样的fk呢？可以选取一个fk来使得我们的目标函数最大化的降低 。目标函数包括损失函数和正则化项。

图4. 目标函数的构成

目标函数 = 损失函数 + 正则项

目标函数

图5. 近似目标函数

3.2 树的复杂度

树的复杂度就是目标函数中的正则化项。将树拆分成结构部分q 和叶子权重部分 w 。图6是一个具体的例子。结构函数q把输入映射到叶子的索引号上面去，而w给定了每个索引号对应的叶子分数是什么，使得fk成为一种条件函数。

图6. q与w定义示意图

定义一棵树的复杂度，考虑复杂度包含了一棵树节点的个数T，以及每个树叶子节点上面输出分数w，如图7所示。

图7. 树的复杂度定义

3.3 目标函数的最终形式
将正则项代入到目标函数中，确定目标函数的最终形式为

图8. 目标函数最小值推导

现在剩下最后一个问题就是树的结构划分。通过不断地枚举不同树的结构，比较目标函数值来寻找一个最优结构的树。暴力枚举的时间开销太大，同decision tree一样采用贪心算法，每一次尝试对已有的叶子加入一个分割。这样，对于一个分割方案，我们可以获得的增益可以由如下所示。

图9. 划分后的Gain示意图

图10.叶子节点划分示意图.png

4.xgboost

xgboost是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包，比常见的工具包快10倍以上。在数据科学方面，有大量kaggle选手选用它进行数据挖掘比赛，其中包括两个以上kaggle比赛的夺冠方案。在工业界规模方面，xgboost的分布式版本有广泛的可移植性，支持在YARN, MPI, Sungrid Engine等各个平台上面运行，并且保留了单机并行版本的各种优化，使得它可以很好地解决于工业界规模的问题。XGBoost 所应用的算法就是 gradient boosting decision tree，既可以用于分类也可以用于回归问题中。

应用案例：

先来用 Xgboost 做一个简单的二分类问题，以下面这个数据为例，来判断病人是否会在 5 年内患病，这个数据前 8 列是自变量，最后一列是预测值为 0 或 1。
数据描述：
https://archive.ics.uci.edu/ml/datasets/Pima+Indians+Diabetes
下载数据集，并保存为 “pima-indians-diabetes.csv“ 文件：
https://archive.ics.uci.edu/ml/machine-learning-databases/pima-indians-diabetes/pima-indians-diabetes.data

• 基础应用

#引入 xgboost 等包
from numpy import loadtxt
from xgboost import XGBClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
#分出变量和标签
dataset = loadtxt('pima-indians-diabetes.csv', delimiter=",")
X = dataset[:,0:8]
Y = dataset[:,8]
#将数据划分为训练集（67%）和测试集（33%）
seed = 7
test_size = 0.33
X_train, X_test, y_train, y_test = train_test_split(X, Y, test_size=test_size, random_state=seed)
#xgboost 有封装好的分类器和回归器，可以直接用 XGBClassifier 建立模型
model = XGBClassifier()
model.fit(X_train, y_train)
#xgboost 的结果是样本分类的概率值
y_pred = model.predict(X_test)
predictions = [round(value) for value in y_pred]
accuracy = accuracy_score(y_test, predictions)
print("Accuracy: %.2f%%" % (accuracy * 100.0))

• 输出特征重要度
  gradient boosting可以给出训练好的模型的特征重要性，可以提供feature selection。仅需要需要引入：from xgboost import plot_importance和前面的代码相比，就是在 fit 后面加入两行画出特征的重要性

plot_importance(model)
pyplot.show()

5. 学习资源

Tianqi Chen 的讲座：
https://www.youtube.com/watch?v=Vly8xGnNiWs&feature=youtu.be
讲义：
https://speakerdeck.com/datasciencela/tianqi-chen-xgboost-overview-and-latest-news-la-meetup-talk
入门教程：
https://xgboost.readthedocs.io/en/latest/
安装教程：
http://xgboost.readthedocs.io/en/latest/build.html
应用示例：
https://github.com/dmlc/xgboost/tree/master/demo
最好的资源当然就是项目的 Github 主页：
https://github.com/dmlc/xgboost

6. 参考文献

【1】http://machinelearningmastery.com/develop-first-xgboost-model-python-scikit-learn/
【2】https://www.zhihu.com/question/37683881
【3】Friedman J H. Greedy Function Approximation: A Gradient Boosting Machine[J]. Annals of Statistics, 2001, 29(5): 1189-1232
【4】http://www.jianshu.com/p/7e0e2d66b3d4
【5】https://xgboost.readthedocs.io/en/latest/