集成学习算法——Xgboost算法

量子计算9 · 发表于 2022-2-21 15:13

Xgboost是boosting集成学习算法中的王牌算法，是基于GBDT改进而来的，两者本质上都是利用了Boosting算法中拟合残差的思想。
作为对GBDT算法的高效实现，XGBoost算法在以下两方面进行了优化。·

算法本身的优化：XGBoost算法的损失函数，除了本身的损失，还加上了正则化部分，可以防止过拟合，泛化能力更强。XGBoost算法的损失函数是对误差部分做二阶泰勒展开，相较于GBDT算法的损失函数只对误差部分做负梯度（一阶泰勒）展开，更加准确。
算法运行效率的优化：对每个弱学习器，如决策树建立的过程做并行选择，找到合适的子节点分裂特征和特征值，从而提升运行效率。

Xgboost通过依次建立K棵分类回归树，使得预测结果尽量接近真实值并且具有尽量大的泛化能力，故其模型为：

$\begin{alignat}{} \tilde{y}_{i}=\sum_{k=1}^{K}{f_{k}(x_{i})}\\ \tilde{y}_{i}^{t}=\sum_{k=1}^{K}{f_{k}(x_{i})}=\tilde{y}_{i}^{t-1}+f_{t}(x_{i}) \end{alignat}\\$
目标函数推导：
其目标函数：

$obj=\sum_{i=1}^{n}l(y_i,\tilde{y_i}^t)+\sum_{i=1}^{t}\Omega(f_i)$ ，其中i表示第i个样本；L为预测误差，误差越小越好；Ω为各树的复杂度函数，越小复杂度越低，泛化能力越强。在传统的 GBDT 中，是没有正则化项 Ω 的。
若使用均方误差 (MSE) 作为损失函数，则目标变为：

$obj^t=\sum_{i=1}^{n}(y_i-(\tilde{y_i}^{t-1}+f_t(x_i)))^2+\sum_{i=1}^{t}\Omega(f_i)=\sum_{i=1}^{n}[2(\tilde{y_i}^{t-1}-y_i)f_t(x_i)+f_t(x_i)^2]+\Omega(f_t)+constant$
令：

$g_i=\partial_{\tilde{y_i}^{t-1}}l(y_i,\tilde{y_i}^{t-1})\\ h_i=\partial_{\tilde{y_i}^{t-1}}^2l(y_i,\tilde{y_i}^{t-1})$
对损失函数进行泰勒二阶展开：

$obj^t=\sum_{i=1}^{n}[l(y_i,\tilde{y_i}^{t-1})+g_if_t(x_i)+\frac{1}{2}h_if_t(x_i)^2]+\Omega(f_t)+constant$
删除所有常量，则目标函数为：

$obj^t=\sum_{i=1}^{n}[g_if_t(x_i)+\frac{1}{2}h_if_t(x_i)^2]+\Omega(f_t)$
单棵决策树可表示为：

$f_t(x)=w_{q(x)}，w\in R^T，q:R^d\rightarrow{\left\{ 1,2,···,T \right\}}$ ，其中w为叶子节点的得分值,q(x)为样本x对应的叶子节点,T为此数的叶子结点个数。
定义树复杂度为：

$\Omega(f)=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}{w_j^2}$
代入目标函数：

$obj^t\approx\sum_{i=1}^{n}[g_iw_{q(x_i)}+\frac{1}{2}h_iw_{q(x_i)}^2]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}{w_j^2}=\sum_{j=1}^{T}[(\sum_{i\in I_j}{g_i})w_{j}+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w_{j}^2]+\gamma T$
令：

$G_j=\sum_{i\in I_j}{g_i}\\ H_j=\sum_{i\in I_j}h_i$
则目标函数为：

$obj^t=\sum_{j=1}^{T}[G_jw_{j}+\frac{1}{2}(H_j+\lambda)w_{j}^2]+\gamma T$

树分裂：
现实中常使用贪心法，遍历每个特征的每个取值，计算分裂前后的增益，并选择增益最大的进行分裂。XGBoost则提出了一种新的增益计算方法，若已经确定了树的结构，则对目标函数obj求极值得：

$w_j^*=-\frac{G_j}{H_j+\lambda}$
将其代入损失函数，则得到打分函数：

$obj^*=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T$
Obj越小，表示此数结构越好。

分裂前后的增益定义为：

$Gain=\frac{1}{2}\left[ \frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda} -\frac{(G_L^2+G_R^2)^2}{H_L+H_R+\lambda}\right]-\gamma$
注：

Gain 越大说明越值得分裂。
γ 是一个超参数，一是对叶结点数目进行控制，二是分裂前后 Gain 增大的阈值，其目的限制树的规模防止过拟合。

决策树建立过程：

贪心法，遍历一个叶结点上的所有候选特征和取值，分别计算 Gain，选择 Gain 最大的候选特征和取值分裂。
对连续值特征进行划分通常比较困难，因为连续值特征往往取值众多。通常的做法是先按特征取值对样本排序，再按顺序计算增益选择划分点。在训练之前，预先按特征取值对样本进行排序，然后保存为block结构，采用CSC格式存储，每一列(一个特征列)均升序存放，大大减小计算量。由于已经预先排过序，所以在树分裂算法中，通过一次线性扫描 (linear scan) 就能找出一个特征的最优分裂点。
数据量非常大难以被全部加载进内存时或者在分布式环境下时，上文的树分裂算法将不再适用，因而提出了近似分裂算法，不仅解决了这个问题，也同时能提升训练速度。

优点：

支持线性分类器
支持自定义损失函数，只要损失函数二阶可导。
引入稀疏感知算法用于并行树学习，对于特征的值有缺失的样本，可以自动学习出它的分裂方向。
正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。
为了防止过拟合，XGBoost还引入了缩减(shrinkage)和列抽样（column subsampling），通过在每一步的boosting中引入缩减系数，降低每个树和叶子对结果的影响；列采样是借鉴随机森林中的思想，根据反馈，列采样有时甚至比行抽样效果更好，同时，通过列采样能加速计算。

语法：

class xgboost.XGBClassifier(*, objective=&#39;binary:logistic&#39;, use_label_encoder=True, **kwargs)
class xgboost.XGBRegressor(*, objective=&#39;reg:squarederror&#39;, **kwargs)

参数：

max_depth：弱学习器决策树的最大深度，默认为3。
n_estimators：弱学习器的个数，或者说弱学习器的最大迭代次数，默认为100。
learning_rate：学习率，又称为每个弱学习器的权重缩减系数，取值范围为（0，1]，取值较小意味着要达到一定的学习效果，需要更多迭代次数和更多弱学习器，默认取0.1。通常用n_estimators和learning_rate一起决定算法的拟合效果，所以这两个参数要一起调优。
objective：在回归中取值为&#39;reg:linear&#39;；在二分类问题中一般取值为&#39;binary:logistic&#39;，在多分类问题中一般取值为&#39;multi:softmax&#39;。
booster：[default=gbtree]，选择基分类器，取值范围{gbtree, gblinear, dart}
min_child_weight：[default=1]，是每个叶子里面 h 的和至少是多少，对正负样本不均衡时的 0-1 分类而言，假设 h 在 0.01 附近，min_child_weight 为 1 意味着叶子节点中最少需要包含 100 个样本。这个参数非常影响结果，控制叶子节点中二阶导的和的最小值，该参数值越小，越容易 overfitting。
max_depth：[default=6]，每颗树的最大深度，树高越深，越容易过拟合。
max_leaf_nodes:最大叶结点数，与max_depth作用有点重合。
gamma：[default=0]，后剪枝时，用于控制是否后剪枝的参数。即在数的叶子节点进一步划分时所需的最小损失的减少值。
max_delta_step：[default=0]，每棵树权重改变的最大步长，如果取0表示没有约束，如果取正值则使得更新步骤更加保守。可以防止做太大的更新步子，使更新更加平缓。
subsample：[default=1]，样本随机采样比例，取值小于1表示通过不放回抽样使用部分样本，值太小会造成欠拟合，取1表示使用所有样本。
colsample_bytree：[default=1]，列采样，对每棵树的生成用的特征进行列采样。一般设置为： 0.5-1
lambda：[default=1]，控制模型复杂度的权重值的L2正则化项参数，参数越大，模型越不容易过拟合。
alpha：[default=0]，控制模型复杂程度的权重值的 L1 正则项参数，参数值越大，模型越不容易过拟合。
scale_pos_weight：[default=1]，在类别样本不平衡的情况下有助于快速收敛。

例：
from sklearn.datasets import load_iris
from xgboost import XGBClassifier
from sklearn.model_selection import train_test_split

iris = load_iris()
X = iris.data
y = iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=12)

clf = XGBClassifier(n_estimators=3, learning_rate=0.01, use_label_encoder=False, eval_metric=&#39;merror&#39;)
model = clf.fit(X_train, y_train)
pre = model.predict(X_test)

acc1 = 0
acc2 = 0
for i in range(len(y_test)):
>>if pre == y_test:
>>>>acc1 += 1
>>else:
>>>>acc2 += 1

print(&#34;Accuracy: %.2f %% &#34; % (100 * acc1 / (acc1 + acc2)))

		自动登录	找回密码
密码			立即注册