Boosted Tree

作者: Jakai | 来源:发表于2017-08-07 16:16 被阅读0次

Boosted Tree
机器学习技法笔记：11 Gradient Boosted Dec
xgboost slide（一）
Xgboost
xgboost原理
xgboost公式推导
经验| 来，教你们假装成算法行家（入门）
xgboost tree
2.27 boost
【每日经济学人】2019-04-27

作为一个非常有效的机器学习方法，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，可以将模型写成为：

图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))