机器学习算法推导&实现18——集成模型系列之GBDT1
前几篇文章，我们介绍并实现了几种主流的决策树算法，从本文开始我们将陆续介绍一些集成算法，首先要介绍的就是GBDT(Gradient Boosting Decision Tree)梯度提升树算法。GBDT算法虽在21世纪初就被提出，但至今仍是机器学习领域最炙手可热的算法之一，且在2014年之后大佬们在GBDT的基础上提出了XGBoost, LightGBM, CatBoost等改进Boosting算法，因此GBDT作为集成算法的核心内容，我们的文章将一步步抽丝剥茧地介绍并实现它。
泰勒展开
GBDT又叫梯度提升树算法，说到梯度（Gradient）相信大家并不陌生，最常用到的便是梯度下降优化算法，而梯度下降又由泰勒展开推导而来。我们先简单回顾下泰勒展开：
[*]泰勒展开的基本形式：
泰勒展开的基本形式
[*]一阶泰勒展开：
一阶泰勒展开
梯度下降
在机器学习任务中，需要最小化损失函数L，函数最小化时的模型参数就是我们要求解的，其中梯度下降常用来求解这种无约束最优化问题，我们来看下推导过程：
[*]函数模型参数的迭代公式设置如下：
参数迭代公式
[*]对损失函数L进行一阶泰勒展开：
参数迭代的一介泰勒展开
[*]我们的目标是最小化损失函数L，所以我们要第t次迭代的损失函数值小于第t-1次迭代的损失函数值，那我们可令：
[*]代入模型参数的迭代公式，可得：
梯度下降迭代公式
由此我们得到了参数空间中梯度下降法的公式。
函数空间
在参数空间中，我们知道参数更新的方向是负梯度方向，最终的参数值是由每次迭代的参数增量累加而来，即：
推广到函数空间，有以下推导：
函数空间梯度下降法迭代的推导过程
可以得到结论：最终函数（模型）由每次迭代的函数增量累加而来，其中 https://www.zhihu.com/equation?tex=f_0 为模型初始函数。
函数空间的函数构成公式
GBDT通用形式
GBDT也是一种Boosting算法，其基分类器常采用CART树来进行拟合。其模型F定义为加法模型：
我们可以通过最小化以下损失函数来求解最优模型：
GBDT的最小化损失函数
当损失函数是平方损失和指数损失函数时，每一步优化是简单的，但对于一般损失函数，很难直接优化得到树的参数，因此另辟蹊径的Freidman提出了梯度提升的算法，类似于函数空间的优化方法，利用拟合损失函数的负梯度作为残差的近似值，拟合一棵树模型。算法的原理如下：
梯度提升算法详解
不同的损失函数，算法的求解过程和内容会有部分不同，下面我们先来看看平方损失函数的情况。
平方损失函数
当损失函数为平方损失函数时，损失函数的负梯度实际就是残差，如下所示：
LS的负梯度
那么我们新生成的每棵树相当于就是拟合当前的残差函数。
既是如此，以平方损失为损失函数的提升回归树（GBRT）在算法上就可以简化很多：
LS损失函数的算法详解
Python实现
基于LS损失函数的GBRT树，其逻辑并不复杂，但是我们需要把梯度提升树整个算法的框架搭好，以便我们后续往里继续填充，还是花了一些时间，包括改造整个CART决策树的代码，以便我们在拟合梯度提升树的时候更加便捷。具体如下：
[*]首先，我们写了梯度提升树的基础树类，后续无论是回归或者分类都可以在这个基础类上进行改造。在基础树类中，目前仅将训练的步骤写好。
class BaseGradientBoosting():
def __init__(self, loss, learning_rate, n_estimators,
criterion, max_depth, min_samples_leaf, min_criterion_value=0.0001):
# 模型参数
self.loss = loss
self.learning_rate = learning_rate
self.n_estimators = n_estimators
# 单颗树参数
self.criterion = criterion
self.max_depth = max_depth
self.min_samples_leaf = min_samples_leaf
self.min_criterion_value = min_criterion_value
def fit(self, X, y):
# 创建模型
self.trees_ = []
# 分配相应的损失函数
loss_function = LOSS_FUNCTIONS
self.loss_function_ = loss_function()
# 初始化预测值为0
y_prediction = np.zeros(y.shape)
for i in range(self.n_estimators):
y_prediction_copy = y_prediction.copy()
# 逐棵树进行训练
tree = self._fit_step(X, y, y_prediction_copy)
self.trees_.append(tree)
# 根据训练结果更新最新的预测函数
y_prediction = y_prediction_copy + self.learning_rate*self.trees_.predict(X)
print(f'第{i}棵树的Loss：', self.loss_function_(y, y_prediction))
return
def _fit_step(self, X, y, y_prediction):
# 1. 计算负梯度
residual = self.loss_function_.negative_gradient(y, y_prediction)
# 生成树
tree = DecisionTreeRegression(self.criterion, self.max_depth, self.min_samples_leaf, self.min_criterion_value)
# 2. 拟合树
tree.fit(X, residual)
# 计算每个样本的叶子结点
terminal_samples_nodeid = tree.apply(X)
# 3. 更新更新叶子结点区域的值
self.loss_function_.update_terminal_regions(tree, terminal_samples_nodeid, X, y, y_prediction)
return tree
def predict(self, X):
pass
[*]其次，将回归树类添加好，基本可以套用基础类，只要改几个参数就行。值得一提的是，作为基学习器的CART树，我们默认其划分准则为MSE，另外还有其他参数的默认值。
# 梯度回归树
class GBRegressionTree(BaseGradientBoosting):
def __init__(self, loss='ls', learning_rate=0.1, n_estimators=100,
criterion='mse', max_depth=3, min_samples_leaf=1, min_criterion_value=0.0001):
super(GBRegressionTree, self).__init__(loss, learning_rate, n_estimators,
criterion, max_depth, min_samples_leaf, min_criterion_value)
[*]然后，比较重要的就是拟合中用到的损失函数。目前只写了平方差（LS）损失函数。其中用到的有计算损失值、计算负梯度，因为LS不涉及叶子结点值的更新，所以叶子节点区域值的更新方法为空。
class LeastSquaresError(object):
"""Loss function for least squares (LS) estimation."""
def __init__(self):
pass
def __call__(self, y, y_prediction):
"""Compute the least square loss."""
return np.mean((y - y_prediction.ravel()) ** 2)
def negative_gradient(self, y, y_prediction):
"""Compute the negative gradient."""
return y - y_prediction.ravel()
def update_terminal_regions(self, tree, terminal_samples_nodeid, X, y, y_prediction):
pass
def _update_terminal_node(self, tree, terminal_nodes, terminal_leaf, X, y, y_prediction):
"""LS no need to update terminal regions"""
pass
[*]最后，就是把我们的基学习器进行了修改，内容较多，这里仅展示最重要的部分。包括训练方法、预测方法、判断样本属于哪个叶子结点的方法。
# 回归树
class DecisionTreeRegression(BaseTree):
def __init__(self, criterion, max_depth, min_samples_leaf, min_criterion_value=0.0001):
"""
回归树的方法类
Parameters
----------
criterion : String
分类树的准则，可选"mse", "mae"，默认"mse".
max_depth : Int
最大树深
min_samples_leaf : Int
叶子结点最小样本数量
min_criterion_value : Float
指标停止划分的最小值.
Returns
-------
None.
"""
super(DecisionTreeRegression, self).__init__(criterion, max_depth, min_samples_leaf, min_criterion_value)
self._tree_predict_method = ANALYSE_TREE['regressor']
def fit(self, X, y, is_categorical:list=[]):
# 计算结点值的函数，用均值来表示
self._calculate_nodevalue_method = calculate_mean
# 计算指标值的函数
self._calculate_criterion_method = CAL_CRITERION
# 搜索最优分裂特征和分裂点的函数
self._search_feature_method = SEARCH_FEATURE
# 拆分数据集的函数
self._split_dataset_method = SPLIT_DATA
# 训练
super(DecisionTreeRegression, self).fit(X, y, is_categorical)
return
def predict(self, X):
res = np.zeros(X.shape)
X_index = np.arange(X.shape)
self._tree_predict_method(X, self.tree, X_index, res, self.is_categorical, 'value')
return res
def apply(self, X):
res = np.zeros(X.shape)
X_index = np.arange(X.shape)
self._tree_predict_method(X, self.tree, X_index, res, self.is_categorical, 'node_id')
return res我用波士顿房价的数据进行了拟合，来看下拟合的结果。可以看出来前几棵树的Loss下降特别快，这也符合我们的预期。
if __name__ == "__main__":
# 回归树测试
## 波士顿房价数据训练
from sklearn.datasets import load_boston
X, y = load_boston(True)
gbrt = GBRegressionTree()
gbrt.fit(X, y)
GBRT拟合过程的LOSS变化
以上就是本次集成模型系列之GBDT1的全部内容，谢谢阅读。
代码下载：
https://github.com/shoucangjia1qu/ML_gzh/tree/master/Ensemble
*本文知识点参考了Friedman的《Greedy Function Approximation : A Gradient Boosting Machine》一文。
往期回顾
嗷大豆的数据工厂：机器学习算法推导&实现17——树模型系列之CART算法2
嗷大豆的数据工厂：机器学习算法推导&实现16——树模型系列之CART算法1
嗷大豆的数据工厂：机器学习算法推导&实现15——树模型系列之C4.5算法
嗷大豆的数据工厂：机器学习算法推导&实现14——树模型系列之ID3算法
嗷大豆的数据工厂：机器学习算法推导&实现13——EM算法以及高斯混合聚类模型
嗷大豆的数据工厂：机器学习算法推导&实现12——半朴素贝叶斯分类算法2
嗷大豆的数据工厂：机器学习算法推导&实现11——半朴素贝叶斯分类算法
嗷大豆的数据工厂：机器学习算法推导&实现10——朴素贝叶斯分类算法（补充版）
嗷大豆的数据工厂：机器学习算法推导&手写实现09——朴素贝叶斯分类算法
学无止境，欢迎关注笔者公众号（嗷大豆的数据工厂），互相学习。
页:
[1]