提升树
首先要明确一点，xgboost 是基于提升树的。
什么是提升树，简单说，就是一个模型表现不好，我继续按照原来模型表现不好的那部分训练第二个模型，依次类推。
来几个形象的比喻就是：
做题的时候，第一个人做一遍得到一个分数，第二个人去做第一个人做错的题目，第三个人去做第二个人做错的题目，以此类推，不停的去拟合从而可以使整张试卷分数可以得到100分（极端情况）。
把这个比喻替换到模型来说，就是真实值为100，第一个模型预测为90，差10分，第二个模型以10为目标值去训练并预测，预测值为7，差三分，第三个模型以3为目标值去训练并预测，以此类推。
1.0 xgboost学习路径
我们xgboost的学习路径可以按照下面四个步骤来：
(1)构造原始目标函数问题：
xgboost目标函数包含损失函数和基于树的复杂度的正则项；
(2)泰勒展开问题：
原始目标函数直接优化比较难，如何使用泰勒二阶展开进行近似；
(3)树参数化问题：
假设弱学习器为树模型，如何将树参数化，并入到目标函数中；这一步的核心就是要明白我们模型优化的核心就是优化参数，没有参数怎么训练样本，怎么对新样本进行预测呢？
(4)如何优化化简之后的目标函数问题：
优化泰勒展开并模型参数化之后的的目标函数，主要包含两个部分：
如何求得叶子节点权重
如何进行树模型特征分割
1.1 目标函数
1.1.0 原始目标函数
目标函数，可以分为两个部分，一部分是损失函数，一部分是正则（用于控制模型的复杂度）。
xgboost属于一种前向迭代的模型，会训练多棵树。
对于第t颗树，第i个样本的，模型的预测值是这样的：
进一步，我们可以得到我们的原始目标函数，如下：
从这个目标函数我们需要掌握的细节是，前后部分是两个维度的问题
两个累加的变量是不同的:
(1)一个是i，i这边代表的是样本数量，也就是对每个样本我们都会做一个损失的计算，这个损失是第t个树的预测值和真实值之间的差值计算（具体如何度量损失视情况而定）。
(2)另一个是累加变量是j，代表的是树的数量，也就是我们每个树的复杂度进行累加。
需要注意的是我们这里具体的损失函数是没有给出定义的，所以它可以是树模型，也可以是线性模型。
1.1.1 简单化简损失函数
正如上面所说，Xgboost是前向迭代，我们的重点在于第t个树，所以涉及到前t-1个树变量或者说参数我们是可以看做常数的。
所以我们的损失函数进一步可以化为如下，其中一个变化是我们对正则项进行了拆分，变成可前t-1项，和第t项：
基于此，在不改变目标函数精读的情况下，我们已经做了最大的简化，最核心的点就是我们认为前t-1个树已经训练好了，所以涉及到的参数和变量我们当成了常数。
接下来，我们使用泰勒级数，对目标函数近似展开。
1.2 泰勒公式对目标函数近似展开
使用泰勒公式进行近似展开的核心目标是就是对目标函数进行化简，将常数项抽离出来。
基本泰勒公式展开如下：
损失函数展开公式细节推导如下：
所以原有公式进行泰勒公式二阶展开，结果为:
进而我们可以得到目标函数展开公式为如下：
还是那句话，我们可以使用任意一个损失函数，这里没有定式。
上述中树的表达我们都是使用函数f(x)来表示，本质上模型的优化求解是在求参数，所以我们需要对树模型参数化才可以进行进一步的优化。
1.3 树的参数化
树的参数化有两个，一个是对树模型参数化，一个是对树的复杂度参数化。
1.3.0 树模型参数化-如何定义一个树
主要是定义三个部分：
（1）每棵树每个叶子节点的值(或者说每个叶子节点的权重)w：这是一个向量，因为每个树有很多叶子节点
（2）样本到叶子节节点的映射关系q：(大白话就是告诉每个样本落在当前这个树的哪一个叶子节点上)
（3）叶子节点样本归属集合I：就是告诉每个叶子节点包含哪些样本
1.3.1 树复杂度的参数化-如何定义树的复杂度
定义树的复杂度主要是从两个部分出发：
（1）每个树的叶子节点的个数（叶子节点个数越少模型越简单）
（2）叶子节点的权重值w（值越小模型越简单）
对于第二点，我们可以想一下L正则不就是想稀疏化权重，从而使模型变得简单吗，其实本质是一样的。
我们树的复杂度如下：
进而我们可以对树进行了参数化，带入到目标函数我们可以得到如下：
随后我们做如下定义：
叶子节点 j 所包含的样本的一阶导数累加之和为：
叶子节点 j 所包含的样本的二阶导数累加之和为：
进而我们可以进一步化简为：
针对这个目标函数，我们对Xgboost优有面临两个问题：
第一就是如何求得wj：这一步其实很简单，直接使用目标函数对wj求导就可以。
还有一个就是如何做到特征的分裂，接下来我们详细聊一下如何去做。
1.4寻找树的形状-特征分裂
首先明确一点，我们增益使用的是基于当前特征分裂点前后，目标函数的差值。
我们当然是希望，使用这个分裂点，目标函数降低的越多越好。
1.4.1 贪心算法
本质上是做两次循环，第一个是是针对每个特征的每个分割点做一次循环，计算收益，从而选择此特征的最佳分割点。分裂收益使用的是分裂之后的目标函数的变化差值。
第二个循环是对样本所有特征的循环，从中挑选出收益最大的特征。
简单说就是首先找到基于每个特征找到收益最大的分割点，然后基于所有特征找到收益最大的特征。
然后在这所有的循环中，挑出增益最大的那个分割点。
1.4.5 近似算法-分位数候选点
对于每个特征，不去暴力搜索每个值，而是使用分位点
（1）根据样本数量选择三分位点或者四分位点等等；
（2）或者根据二阶导数（也就是梯度）作为权重进行划分
也就是说原来是某个特征的所有取值是候选点，现在是某个特征的分位点作为候选点。
1.5.工程实现细节
1.5.1 特征分裂并行寻找
寻找特征分隔点需要对特征值进行排序，这个很耗时间。我们可以在训练之前先按照特征对样本数据进行排序，并分别保存在不同的块结构中。每个块都有一个按照某个特征排好序的特征加对应的一阶二阶导数。
对于不同的特征的特征划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益
1.5.2 缓存访问
特征是排好序，但是通过索引获取一阶二阶导数值是不连续的，造成cpu缓存命中率低；xgboost解决办法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就连续了；
同时通过设置合理的分块的大小，充分利用了CPU缓存进行读取加速（cache-aware access）。使得数据读取的速度更快。另外，通过将分块进行压缩（block compressoin）并存储到硬盘上，并且通过将分块分区到多个硬盘上实现了更大的IO。
1.5.3 xgboost特征的重要性是如何评估的
（1）weight ：该特征在所有树中被用作分割样本的特征的总次数。
（2）gain ：该特征在其出现过的所有树中产生的平均增益（我自己的理解就是目标函数减少值总和的平均值，这里也可以使用增益之和）。
（3）cover ：该特征在其出现过的所有树中的平均覆盖范围。
这里有一个细节需要注意，就是节点分割的时候，之前用过的特征在当前节点也是可以使用的，所以weight才是有意义的。
1.6 与GBDT相比，Xgboost的优化点：
（1）算法本身的优化：首先GBDT只支持决策树，Xgboost除了支持决策树，可以支持多种弱学习器，可以是默认的gbtree, 也就是CART决策树，还可以是线性弱学习器gblinear以及DART；其次GBDT损失函数化简的时候进行的是一阶泰勒公式的展开，而Xgboost使用的是二阶泰勒公式的展示。还有一点是Xgboost的目标函数加上了正则项，这个正则项是对树复杂度的控制，防止过拟合。
（2）可以处理缺失值。尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向
（3）运行效率：并行化，单个弱学习器最耗时的就是决策树的分裂过程，对于不同特征的特征分裂点，可以使用多线程并行选择。这里想提一下，我自己理解，这里应该针对的是每个节点，而不是每个弱学习器。这里其实我当时深究了一下，有点混乱。为什么是针对每个节点呢？因为我每个节点也有很多特征，所以在每个节点上，我并行（多线程）除了多个特征，每个线程都在做寻找增益最大的分割点。还有需要注意的一点是Xgboost在并行处理之前，会提前把样本按照特征大小排好序，默认都放在右子树，然后递归的从小到大拿出一个个的样本放到左子树，然后计算对基于此时的分割点的增益的大小，然后记录并更新最大的增益分割点。
import numpy as npfrom cart import TreeNode, BinaryDecisionTreefrom sklearn.model_selection import train_test_splitfrom sklearn.metrics import accuracy_scorefrom utils import cat_label_convert
### XGBoost单棵树类class XGBoost_Single_Tree(BinaryDecisionTree): # 结点分裂方法 def node_split(self, y): # 中间特征所在列 feature = int(np.shape(y)[1]/2) # 左子树为真实值，右子树为预测值 y_true, y_pred = y[:, :feature], y[:, feature:] return y_true, y_pred
# 信息增益计算方法 def gain(self, y, y_pred): # 梯度计算 Gradient = np.power((y * self.loss.gradient(y, y_pred)).sum(), 2) # Hessian矩阵计算 Hessian = self.loss.hess(y, y_pred).sum() return 0.5 * (Gradient / Hessian)
# 树分裂增益计算 # 式(12.28) def gain_xgb(self, y, y1, y2): # 结点分裂 y_true, y_pred = self.node_split(y) y1, y1_pred = self.node_split(y1) y2, y2_pred = self.node_split(y2) true_gain = self.gain(y1, y1_pred) false_gain = self.gain(y2, y2_pred) gain = self.gain(y_true, y_pred) return true_gain + false_gain - gain
# 计算叶子结点最优权重 def leaf_weight(self, y): y_true, y_pred = self.node_split(y) # 梯度计算 gradient = np.sum(y_true * self.loss.gradient(y_true, y_pred), axis=0) # hessian矩阵计算 hessian = np.sum(self.loss.hess(y_true, y_pred), axis=0) # 叶子结点得分 leaf_weight = gradient / hessian return leaf_weight
# 树拟合方法 def fit(self, X, y): self.impurity_calculation = self.gain_xgb self._leaf_value_calculation = self.leaf_weight super(XGBoost_Single_Tree, self).fit(X, y)
### 分类损失函数定义# 定义Sigmoid类class Sigmoid: def __call__(self, x): return 1 / (1 + np.exp(-x))
def gradient(self, x): return self.__call__(x) * (1 - self.__call__(x))
# 定义Logit损失class LogisticLoss: def __init__(self): sigmoid = Sigmoid() self._func = sigmoid self._grad = sigmoid.gradient
# 定义损失函数形式 def loss(self, y, y_pred): y_pred = np.clip(y_pred, 1e-15, 1 - 1e-15) p = self._func(y_pred) return y * np.log(p) + (1 - y) * np.log(1 - p)
# 定义一阶梯度 def gradient(self, y, y_pred): p = self._func(y_pred) return -(y - p)
# 定义二阶梯度 def hess(self, y, y_pred): p = self._func(y_pred) return p * (1 - p)
### XGBoost定义class XGBoost: def __init__(self, n_estimators=300, learning_rate=0.001, min_samples_split=2, min_gini_impurity=999, max_depth=2): # 树的棵树 self.n_estimators = n_estimators # 学习率 self.learning_rate = learning_rate # 结点分裂最小样本数 self.min_samples_split = min_samples_split # 结点最小基尼不纯度 self.min_gini_impurity = min_gini_impurity # 树最大深度 self.max_depth = max_depth # 用于分类的对数损失 # 回归任务可定义平方损失 # self.loss = SquaresLoss() self.loss = LogisticLoss() # 初始化分类树列表 self.trees = [] # 遍历构造每一棵决策树 for _ in range(n_estimators): tree = XGBoost_Single_Tree( min_samples_split=self.min_samples_split, min_gini_impurity=self.min_gini_impurity, max_depth=self.max_depth, loss=self.loss) self.trees.append(tree)
# xgboost拟合方法 def fit(self, X, y): y = cat_label_convert(y) y_pred = np.zeros(np.shape(y)) # 拟合每一棵树后进行结果累加 for i in range(self.n_estimators): tree = self.trees[i] y_true_pred = np.concatenate((y, y_pred), axis=1) tree.fit(X, y_true_pred) iter_pred = tree.predict(X) y_pred -= np.multiply(self.learning_rate, iter_pred)
# xgboost预测方法 def predict(self, X): y_pred = None # 遍历预测 for tree in self.trees: iter_pred = tree.predict(X) if y_pred is None: y_pred = np.zeros_like(iter_pred) y_pred -= np.multiply(self.learning_rate, iter_pred) y_pred = np.exp(y_pred) / np.sum(np.exp(y_pred), axis=1, keepdims=True) # 将概率预测转换为标签 y_pred = np.argmax(y_pred, axis=1) return y_pred
from sklearn import datasets# 导入鸢尾花数据集data = datasets.load_iris()# 获取输入输出X, y = data.data, data.target# 数据集划分X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=43) # 创建xgboost分类器clf = XGBoost()# 模型拟合clf.fit(X_train, y_train)# 模型预测y_pred = clf.predict(X_test)# 准确率评估accuracy = accuracy_score(y_test, y_pred)print ('Accuracy: ', accuracy)
3.1 分类器
from xgboost import XGBClassifier
XGBClassifier(base_score=0.5, booster='gbtree', colsample_bylevel=1, colsample_bynode=1, colsample_bytree=1, gamma=0, learning_rate=0.1, max_delta_step=0, max_depth=3, min_child_weight=1, missing=None, n_estimators=100, n_jobs=1, nthread=None, objective='binary:logistic', random_state=0, reg_alpha=0, reg_lambda=1, scale_pos_weight=1, seed=None, silent=None, subsample=1, verbosity=1)
#样例xgboost from sklearn.datasets import make_hastie_10_2from xgboost import XGBClassifierx, y = make_hastie_10_2(random_state=0)x_train, x_test = x[:2000], x[2000:]y_train, y_test = y[:2000], y[2000:]model = XGBClassifier() # 载入模型（模型命名为model)model.fit(x_train,y_train) # 训练模型（训练集）y_pred = model.predict(x_test) # 模型预测（测试集），y_pred为预测结果print(y_pred)
learning_rate：
含义：学习率，控制每次迭代更新权重时的步长，默认0.3。
调参：值越小，训练越慢。
典型值为0.01-0.2。
objective 目标函数：
回归任务
reg:linear (默认)
reg:logistic
二分类：
binary:logistic 概率
binary：logitraw 类别
多分类
multi：softmax num_class=n 返回类别
multi：softprob num_class=n 返回概率
rank:pairwise
eval_metric：
回归任务(默认rmse)
rmse--均方根误差
mae--平均绝对误差
分类任务(默认error)
auc--roc曲线下面积
error--错误率（二分类）
merror--错误率（多分类）
logloss--负对数似然函数（二分类）
mlogloss--负对数似然函数（多分类）
gamma：
惩罚项系数，指定节点分裂所需的最小损失函数下降值。
调参：
alpha：
L1正则化系数，默认为1
lambda：
L2正则化系数，默认为1
3.4 xgboost 调参思路
（1）选择较高的学习率(learning_rate)，例如0.1，这样可以减少迭代用时。
（2）然对 max_depth , min_child_weight , gamma , subsample, colsample_bytree
这些参数进行调整。这些参数的合适候选值为：
max_depth：[3, 5, 6, 7, 9, 12, 15, 17, 25]
min_child_weight：[1, 3, 5, 7]
gamma：[0, 0.05 ~ 0.1, 0.3, 0.5, 0.7, 0.9, 1]
subsample：[0.6, 0.7, 0.8, 0.9, 1]
colsample_bytree：[0.6, 0.7, 0.8, 0.9, 1]
（3）调整正则化参数 lambda , alpha，这些参数的合适候选值为：
alpha：[0, 0.01~0.1, 1]
lambda ：[0, 0.1, 0.5, 1]
（4）降低学习率，继续调整参数：
学习率(learning_rate)合适候选值为：[0.01, 0.015, 0.025, 0.05, 0.1]
