编程知识 cdmana.com

Ensemble Learning Algorithm

5.1 集成学习算法简介

学习目标

  • 了解什么是集成学习
  • 了解集成学习中的boosting和bagging

1 什么是集成学习

An investor wants to invest in a companyA,But he doesn't yet know its performance.So he wanted someone to give him advice,See if the company's stock price has grown every year6%以上.

image-20221115142535157

集成学习通过建立几个模型来解决单一预测问题.它的工作原理是生成多个分类器/模型,Make their own predictions.这些预测最后结合成组合预测,因此优于任何一个单分类的做出预测.

2 Integrated learning in life

1.Buy something and ask others to recommend it

2.Singing contest voting

每个人的视角不同、经历不同、The reasons behind the decisions given are different

3 复习:机器学习的两个核心任务

  • 任务一:如何优化训练数据 —> 主要用于解决欠拟合问题
  • 任务二:如何提升泛化性能 —> 主要用于解决过拟合问题

4 集成学习中boosting和Bagging

image-20221115142551735

  • **Bagging中每个训练集互不相关,也就是每个基分类器互不相关,而Boosting中训练集要在上一轮的结果上进行调整,也使得其不能并行计算

    **

  • Bagging中预测函数是均匀平等的,但在Boosting中预测函数是加权的

从算法来看,BaggingThe focus is on voting combinations of multiple base models,Each base model is relatively complex,Bagging可以降低方差;而BoostingThe strategy adopted is to reduce the bias of the previous round in each learning pass.

5 小结

  • 什么是集成学习【了解】
    • 通过建立几个模型来解决单一预测问题
  • 机器学习两个核心任务【知道】
    • 1.解决欠拟合问题
      • 弱弱组合变强
      • boosting
    • 2.解决过拟合问题
      • 互相遏制变壮
      • Bagging

5.2 Bagging和随机森林

学习目标

  • 知道Bagging集成原理
  • 知道随机森林构造过程
  • Know what an out-of-contract estimate is
  • 知道RandomForestClassifier的使用
  • 了解bagging集成的优点

1 Bagging集成原理

Bagging

Bagging是bootstrap aggregating的简写.先说一下bootstrap,bootstrap也称为自助法,它是一种有放回的抽样方法.

在Bagging方法中,利用bootstrap方法从整体数据集中采取有放回抽样得到N个数据集,在每个数据集上学习出一个模型,最后的预测结果利用N个模型的输出得到,具体地:分类问题采用N个模型预测投票的方式,回归问题采用N个模型预测平均的方式.

例:

目标:把下面的圈和方块进行分类

image-20200108152443987

实现过程:

  1. 采样不同数据集

image-20200108152710919

2)训练分类器

image-20200108152854195

3)平权投票,获取最终结果

image-20200108152954050

4)主要实现过程小结

image-20200108153048505

2 bagging经典算法:随机森林

在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定.

随机森林= Bagging +决策树

image-20200108153323748

例如, 如果你训练了5个树, 其中有4个树的结果是True, 1个树的结果是False, 那么最终投票结果就是True

随机森林够造过程中的关键步骤(M表示特征数目):

1)Assume that the training set has a total of N个样本,一次随机选出一个样本,有放回的抽样,重复N次(There will be duplicate samples)

2) 随机去选出m个特征, m <<M,建立决策树

(These two methods are used to generate different decision trees using the same data)

3 包外估计 (Out-of-Bag Estimate)

在随机森林构造过程中,如果进行有放回的抽样,我们会发现,总是有一部分样本我们选不到.

  • 这部分数据,占整体数据的比重有多大呢?
  • 这部分数据有什么用呢?

3.1 包外估计的定义

No data selected,称之为 Out-of-bag(OOB)数据,当数据足够多,The probability of out-of-package data is :

img

N为样本个数,1/NThe probability of being selected for the sample,

由于基分类器是构建在训练样本的自助抽样集上的,只有约 63.2% 原样本集出现在中,而剩余的 36.8% 的数据作为包外数据,可以用于基分类器的验证集.

经验证,包外估计是对集成分类器泛化误差的无偏估计.

oob_score
对于单棵用采样集训练完成的决策树Ti,用袋外数据运行后会产生一个oob_score ,对每一棵决策树都重复上述操作,最终会得到T个oob_score,把这T和oob_score平均,最终得到的就是整个随机森林的oob_score

3 随机森林api介绍

  • sklearn.ensemble.RandomForestClassifier(n_estimators=10, criterion=’gini’, max_depth=None, bootstrap=True, random_state=None, min_samples_split=2)

    • n_estimators:integer,optional(default = 10)森林里的树木数量120,200,300,500,800,1200

      • 在利用最大投票数或平均值来预测之前,你想要建立子树的数量.
    • Criterion:string,可选(default =“gini”)

      • 分割特征的测量方法
    • max_depth:integer或None,可选(默认=无)

      • 树的最大深度 5,8,15,25,30
    • max_features="auto”,每个决策树的最大特征数量

      • If “auto”, then max_features=sqrt(n_features).
      • If “sqrt”, then max_features=sqrt(n_features)(same as “auto”).
      • If “log2”, then max_features=log2(n_features).
      • If None, then max_features=n_features.
    • bootstrap:boolean,optional(default = True)

      • 是否在构建树时使用放回抽样
    • min_samples_split 内部节点再划分所需最小样本数

      • 这个值限制了子树继续划分的条件,如果某节点的样本数少于min_samples_split,则不会继续再尝试选择最优特征来进行划分,默认是2.
      • 如果样本量不大,不需要管这个值.如果样本量数量级非常大,则推荐增大这个值.
    • min_samples_leaf 叶子节点的最小样本数

      • 这个值限制了叶子节点最少的样本数,如果某叶子节点数目小于样本数,则会和兄弟节点一起被剪枝, 默认是1.

      • 叶是决策树的末端节点. 较小的叶子使模型更容易捕捉训练数据中的噪声.

      • 一般来说,我更偏向于将最小叶子节点数目设置为大于50.

    • min_impurity_split: 节点划分最小不纯度

      • 这个值限制了决策树的增长,如果某节点的不纯度(基于基尼系数,均方差)小于这个阈值,则该节点不再生成子节点.即为叶子节点 .

      • 一般不推荐改动默认值1e-7.

  • 上面决策树参数中最重要的包括

    • 最大特征数max_features,
    • 最大深度max_depth,
    • 内部节点再划分所需最小样本数min_samples_split
    • 叶子节点最少样本数min_samples_leaf.

4 随机森林预测案例

  • 实例化随机森林
# 随机森林去进行预测
rf = RandomForestClassifier()
  • 定义超参数的选择列表
param = {
    "n_estimators": [120,200,300,500,800,1200], "max_depth": [5, 8, 15, 25, 30]}
  • 使用GridSearchCV进行网格搜索
# 超参数调优
gc = GridSearchCV(rf, param_grid=param, cv=2)

gc.fit(x_train, y_train)

print("随机森林预测的准确率为:", gc.score(x_test, y_test))

注意

  • 随机森林的建立过程
  • 树的深度、树的个数等需要进行超参数调优

所有代码

import pandas as pd
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.tree import DecisionTreeClassifier


# 1、获取数据
titan = pd.read_csv("./data/titanic.txt")
#2.数据基本处理
#2.1 确定特征值,目标值
x = titan[["pclass", "age", "sex"]]
y = titan["survived"]
#2.2 缺失值处理
x['age'].fillna(x['age'].mean(), inplace=True)
#2.3 数据集划分
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=22)
#3.特征工程(字典特征抽取)
# 对于x转换成字典数据x.to_dict(orient="records"),orient:指定把dataframe的数据转换成什么格式
# records格式:[{"pclass": "1st", "age": 29.00, "sex": "female"}, {}]

transfer = DictVectorizer(sparse=False)

x_train = transfer.fit_transform(x_train.to_dict(orient="records"))
x_test = transfer.transform(x_test.to_dict(orient="records"))


# 4.机器学习(随机森林)
# 4.1实例化随机森林
rf = RandomForestClassifier()
#dt = DecisionTreeClassifier()
# 4.2 定义超参数的选择列表
param = {"n_estimators": [60,80,100,120], "max_depth": [3,5,7]}
#param = { "max_depth": [3,5,7]}
# 4.3 使用GridSearchCV进行网格搜索
from sklearn.model_selection import GridSearchCV
gc = GridSearchCV(rf, param_grid=param, cv=5)
#gc = GridSearchCV(dt, param_grid=param, cv=5)
# 4.4模型训练
gc.fit(x_train, y_train)
# 5.模型评估

print("随机森林预测的准确率为:", gc.score(x_test, y_test))

5 bagging集成优点

Bagging + 决策树/线性回归/逻辑回归/深度学习… = bagging集成学习方法

最常用的方法是 Bagging + 决策树,即随机森林.

经过上面方式组成的集成学习方法:

  1. Improve generalization accuracy
  2. 简单, 方便, 通用

6 小结

  • bagging集成过程【知道】
    • 1.采样 — 从所有样本里面,采样一部分
    • 2.学习 — 训练弱学习器
    • 3.集成 — 使用平权投票
  • 随机森林介绍【知道】
    • 随机森林定义
      • 随机森林 = Bagging + 决策树
    • 流程:
      • 1.随机选取m条数据
      • 2.随机选取k个特征
      • 3.训练决策树
      • 4.重复1-3
      • 5.对上面的若决策树进行平权投票
    • 注意:
      • 1.随机选取样本,且是有放回的抽取
      • 2.选取特征的时候吗,选择m<<M
      • M是所有的特征数
    • 包外估计
      • 如果进行有放回的对数据集抽样,会发现,总是有一部分样本选不到;
    • api
      • sklearn.ensemble.RandomForestClassifier()
  • Bagging + 决策树/线性回归/逻辑回归/深度学习… = bagging集成学习方法【了解】
  • bagging的优点【了解】
    • 1.均可在原有算法上提高约2%左右的泛化正确率
    • 2.简单, 方便, 通用

5.3 otto案例介绍 – Otto Group Product Classification Challenge

1.背景介绍

奥托集团是世界上最大的电子商务公司之一,在20多个国家设有子公司.该公司每天都在世界各地销售数百万种产品,所以对其产品根据性能合理的分类非常重要.

不过,在实际工作中,工作人员发现,许多相同的产品得到了不同的分类.本案例要求,你对奥拓集团的产品进行正确的分类.尽可能的提供分类的准确性.

链接:https://www.kaggle.com/c/otto-group-product-classification-challenge/overview

2nd iteration

2.数据集介绍

  • 本案例中,数据集包含大约200,000种产品的93个特征.
  • 其目的是建立一个能够区分otto公司主要产品类别的预测模型.
  • 所有产品共被分成九个类别(例如时装,电子产品等).

image-20191104201012543

  • id - 产品id
  • feat_1, feat_2, …, feat_93 - 产品的各个特征
  • target - 产品被划分的类别

3.评分标准

本案例中,最后结果使用多分类对数损失进行评估.

具体公式: image-20191104203315266

上公式中,

  • i表示样本,j表示类别.Pij代表第i个样本属于类别j的概率,
  • 如果第isamples really belong to the classj,则yij等于1,否则为0.
  • 根据上公式,Suppose you classify all test samples correctly,所有pij都是1,那每个log(pij)都是0,最终的logloss也是0.
  • 假如第1samples would have belonged to1类别的,But the class probabilities you give itpij=0.1,那loglosswill add uplog(0.1)这一项.We know this term is negative,而且pij越小,负得越多,如果pij=0,will be infinite.This causes this situation:You assigned the wrong one,logloss就是无穷.这当然不合理,为了避免这一情况,We do the following for very small values:

image-20191104203941475

  • That is to say, the minimum will not be less than 10^-15.

5.4 Boosting

学习目标

  • 知道boosting集成原理和实现过程
  • 知道bagging和boosting集成的区别
  • 知道AdaBoost集成原理

1 什么是boosting

image-20190214160534929

随着学习的积累从弱到强

简而言之:每新加入一个弱学习器,整体能力就会得到提升

代表算法:Adaboost,GBDT

2 实现过程:

1.训练第一个学习器

image-20200109093930261

2.调整数据分布

image-20200109094017202

3.训练第二个学习器

image-20200109094048990

4.再次调整数据分布

image-20200109094214835

5.依次训练学习器,调整数据分布

image-20200109094305835

6.整体过程实现

image-20200109094429509

3 bagging集成与boosting集成的区别:

  • 区别一:数据方面
    • Bagging:对数据进行采样训练;
    • Boosting:根据前一轮学习结果调整数据的重要性.
  • 区别二:投票方面
    • Bagging:所有学习器平权投票;
    • Boosting:对学习器进行加权投票.
  • 区别三:学习顺序
    • Bagging的学习是并行的,每个学习器没有依赖关系;
    • Boosting学习是串行,学习有先后顺序.
  • 区别四:主要作用
    • Bagging主要用于提高泛化性能(解决过拟合,也可以说降低方差)
    • Boosting主要用于提高训练精度 (解决欠拟合,也可以说降低偏差)

image-20200109094753644

4 AdaBoost介绍

4.1 构造过程细节:

  • 步骤一:初始化训练数据权重相等,训练第一个学习器.

    • 该假设每个训练样本在基分类器的学习中作用相同,这一假设可以保证第一步能够在原始数据上学习基本分类器 H 1 ( x ) H_1(x) H1(x)

  • 步骤二:AdaBoost反复学习基本分类器,在每一轮m=1,2,…,M顺次的执行下列操作:

    • (a) 在权值分布为 D t D_t Dt的训练数据上,确定基分类器,(At the beginning, the weight of each data is 1/N,N为数据的个数);

    • (b) Computes the learner in the training data错误率,h为预测值,y为真实值:

      ε t = P ( h t ( x t ) ≠ y t ) \varepsilon _t = P(h_t(x_t)\neq y_t) εt=P(ht(xt)=yt)

    • (c) Compute the learner's 投票权重(This coefficient is the coefficient of this classifier when used in the final classifier ensemble.):

      α t = 1 2 l n ( 1 − ε t ε t ) \alpha _t=\frac{1}{2}ln(\frac{1-\varepsilon _t}{\varepsilon _t}) αt=21ln(εt1εt)

    • (d) 根据投票权重,对Training data reweighting D t D_t Dt是第tThe weight distribution of each data round), Z t Z_t Zt为归一化系数,公式为
      ∑ t D t ( x ) ∗ { e − α t , 预 测 值 = 真 实 值 e α t , 预 测 值 ≠ 真 实 值 \sum_t D_t(x)* \begin{cases} e^{-\alpha_t} ,预测值=真实值 \\ e^{\alpha_t} ,预测值\not=真实值\\ \end{cases} tDt(x){ eαt,=eαt,=

    • image-20191108183556749

      • 将下一轮学习器的注意力集中在错误数据上

    • 重复执行a到d步,m次;

  • 步骤三:对m个学习器进行加权投票

    image-20191108171049147

4.2 关键点剖析(The algorithm requires that the correct rate of the base classifier be greater than 0.5,It works well for binary classification)

如何确认投票权重?

如何调整数据分布?

image-20200109094524632

4.3 案例:

给定下面这张训练数据表所示的数据,假设弱分类器由xv产生,其阈值v使该分类器在训练数据集上的分类误差率最低,试用Adaboost算法学习一个强分类器.

image-20191108172411859

问题解答:

步骤一:初始化训练数据权重相等,训练第一个学习器:

D 1 = ( w 11 , w 12 , . . . , w 110 , ) D_1=(w_{11},w_{12},...,w_{110},) D1=(w11,w12,...,w110,)

w 1 i = 0.1 , i = 1 , 2 , . . . , 10 w_{1i}=0.1, i=1,2,...,10 w1i=0.1,i=1,2,...,10

步骤二:AdaBoost反复学习基本分类器,在每一轮m=1,2,…,M顺次的执行下列操作:

当m=1的时候:

(a)在权值分布为D_1的训练数据上,阈值v取2.5时分类误差率最低,(The depth used here is 1的决策树)故基本分类器为:

6,7,8被分错

image-20191108183638434

(b)Computes the learner in the training data错误率 ε 1 = P ( h 1 ( x 1 ) ≠ y 1 ) = 0.3 \varepsilon _1 = P(h_1(x_1)\neq y_1)=0.3 ε1=P(h1(x1)=y1)=0.3

(c)Compute the learner's 投票权重 α 1 = 1 2 l n ( 1 − ε 1 ε 1 ) = 0.4236 \alpha _1=\frac{1}{2}ln(\frac{1-\varepsilon _1}{\varepsilon _1})=0.4236 α1=21ln(ε11ε1)=0.4236

(d)根据投票权重,对Training data reweighting:

D 2 = ( w 21 , w 22 , . . . , w 210 , ) D_2=(w_{21},w_{22},...,w_{210},) D2=(w21,w22,...,w210,)

According to the following formula,Calculate individual weight valuesimage-20191108183556749

经计算得,D_2的值为:

D 2 = ( 0.07143 , 0.07143 , 0.07143 , 0.07143 , 0.07143 , 0.07143 , 0.16667 , 0.16667 , 0.16667 , 0.07143 ) D_2=(0.07143,0.07143,0.07143,0.07143,0.07143, 0.07143,0.16667,0.16667,0.16667,0.07143) D2=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)

计算过程:

image-20191108184941435

H 1 ( x ) = s i g n [ 0.4236 h 1 ( x ) ] H_1(x)=sign[0.4236h_1(x)] H1(x)=sign[0.4236h1(x)],(sign函数为符号函数,大于等于0,为1,小于0为-1.)

分类器H_1(x)在训练数据集上有3个误分类点.

当m=2的时候:

(a)在权值分布为D_2的训练数据上,阈值v取8.5时分类误差率最低,故基本分类器为:

3,4,5被分错

image-20191108185644858

(b)Computes the learner in the training data错误率 ε 2 = P ( h 2 ( x 2 ) ≠ y 2 ) = 0.2143 \varepsilon _2 = P(h_2(x_2)\neq y_2)=0.2143 ε2=P(h2(x2)=y2)=0.2143

(c)Compute the learner's 投票权重 α 2 = 1 2 l n ( 1 − ε 2 ε 2 ) = 0.6496 \alpha _2=\frac{1}{2}ln(\frac{1-\varepsilon _2}{\varepsilon _2})=0.6496 α2=21ln(ε21ε2)=0.6496

(d)根据投票权重,对Training data reweighting:

经计算得,D_3D3的值为:

D 3 = ( 0.0455 , 0.0455 , 0.0455 , 0.1667 , 0.1667 , 0.1667 , 0.1060 , 0.1060 , 0.1060 , 0.0455 ) D_3=(0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.1667, 0.1060, 0.1060, 0.1060,0.0455) D3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)

H 2 ( x ) = s i g n [ 0.4236 h 1 ( x ) + 0.6496 h 2 ( x ) ] H_2(x)=sign[0.4236h_1(x)+0.6496h_2(x)] H2(x)=sign[0.4236h1(x)+0.6496h2(x)]

分类器H_2(x)在训练数据集上有3个误分类点.

当m=3的时候:

(a)在权值分布为D_3的训练数据上,阈值v取5.5时分类误差率最低,故基本分类器为:

image-20191108190148376

(b)Computes the learner in the training data错误率 ε 3 = 0.1820 \varepsilon _3 = 0.1820 ε3=0.1820

(c)Compute the learner's 投票权重 α 3 = 0.7514 \alpha _3=0.7514 α3=0.7514

(d)根据投票权重,对Training data reweighting:

经计算得,D_4D4的值为:

D 4 = ( 0.125 , 0.125 , 0.125 , 0.102 , 0.102 , 0.102 , 0.065 , 0.065 , 0.065 , 0.125 ) D_4=(0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125) D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)

H 3 ( x ) = s i g n [ 0.4236 h 1 ( x ) + 0.6496 h 2 ( x ) + 0.7514 h 3 ( x ) ] H_3(x)=sign[0.4236h_1(x)+0.6496h_2(x)+0.7514h_3(x)] H3(x)=sign[0.4236h1(x)+0.6496h2(x)+0.7514h3(x)]

分类器H_3(x)H3(x)The number of misclassified points on the training data set is 0.

步骤三:对m个学习器进行加权投票,获取最终分类器

H 3 ( x ) = s i g n [ 0.4236 h 1 ( x ) + 0.6496 h 2 ( x ) + 0.7514 h 3 ( x ) ] H_3(x)=sign[0.4236h_1(x)+0.6496h_2(x)+0.7514h_3(x)] H3(x)=sign[0.4236h1(x)+0.6496h2(x)+0.7514h3(x)]

4.4 api介绍

  • from sklearn.ensemble import AdaBoostClassifier
    • api链接:https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html#sklearn.ensemble.AdaBoostClassifier
    • class sklearn.ensemble.AdaBoostClassifier(base_estimator=None, n_estimators=50,random_state=None
      • base_estimator:基分类器,The default depth used is 1的决策树.
      • n_estimators:The number of base classifiers
      • random_state:随机种子

4.5 使用

from sklearn.ensemble import AdaBoostClassifier
import numpy as np
X = np.array([0,1,2,3,4,5,6,7,8,9]).reshape(-1,1)
y = np.array([1,1,1,-1,-1,-1,1,1,1,-1])
clf = AdaBoostClassifier(random_state=0)
clf.fit(X, y)

clf.predict([[0]])

clf.score(X, y)

5 小结

  • 什么是Boosting 【知道】
    • 随着学习的积累从弱到强
    • 代表算法:Adaboost,GBDT,XGBoost,LightGBM
  • bagging和boosting的区别【知道】
    • 区别一:数据方面
      • Bagging:对数据进行采样训练;
      • Boosting:根据前一轮学习结果调整数据的重要性.
    • 区别二:投票方面
      • Bagging:所有学习器平权投票;
      • Boosting:对学习器进行加权投票.
    • 区别三:学习顺序
      • Bagging的学习是并行的,每个学习器没有依赖关系;
      • Boosting学习是串行,学习有先后顺序.
    • 区别四:主要作用
      • Bagging主要用于提高泛化性能(解决过拟合,也可以说降低方差)
      • Boosting主要用于提高训练精度 (解决欠拟合,也可以说降低偏差)
  • AdaBoost构造过程【知道】
    • 步骤一:初始化训练数据权重相等,训练第一个学习器;
    • 步骤二:AdaBoost反复学习基本分类器;
    • 步骤三:对m个学习器进行加权投票

5.5 GBDT介绍

学习目标

  • 知道GBDT的算法原理

GBDT 的全称是 Gradient Boosting Decision Tree,梯度提升树,在传统机器学习算法中,GBDT算的上TOP3的算法.想要理解GBDT的真正意义,那就必须理解GBDT中的Gradient BoostingDecision Tree分别是什么?

1 Decision Tree:CART回归树

首先,GBDT使用的决策树是CART回归树,无论是处理回归问题还是二分类以及多分类,GBDT使用的决策树通通都是都是CART回归树.

  • 为什么不用CART分类树呢?
    • 因为GBDT每次迭代要拟合的是梯度值,是连续值所以要用回归树.

对于回归树算法来说最重要的是寻找最佳的划分点,那么回归树中的可划分点包含了所有特征的所有可取的值.

在分类树中最佳划分点的判别标准是熵或者基尼系数,都是用纯度来衡量的,但是在回归树中的样本标签是连续数值,所以再使用熵之类的指标不再合适,取而代之的是平方误差,它能很好的评判拟合程度.

1.1 回归树生成算法(复习)

  • 输入:训练数据集D:
  • 输出:回归树f(x).
  • 在训练数据集所在的输入空间中,递归的将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树:
    • (1)选择最优切分特征j与切分点s,使平方误差最小
    • (2)用选定的对(j,s)划分区域并决定相应的输出值,That is, the average value of the leaf nodes:
    • (3)继续对两个子区域调用步骤(1)和(2),直至满足停止条件.

2 Gradient Boosting: 拟合负梯度

梯度提升树(Grandient Boosting)是提升树(Boosting Tree)的一种改进算法,所以在讲梯度提升树之前先来说一下提升树.

先来个通俗理解:假如有个人30岁,我们首先用20岁去拟合,发现损失有10岁,这时我们用6岁去拟合剩下的损失,发现差距还有4岁,第三轮我们用3岁拟合剩下的差距,差距就只有一岁了.如果我们的迭代轮数还没有完,可以继续迭代下面,每一轮迭代,拟合的岁数误差都会减小.最后将每次拟合的岁数加起来便是模型输出的结果.

提升树算法:

  • (1)初始化f_0(x)=0
  • (2)对m=1,2,…,M
    • (a)计算残差 r m i = y i − f m − 1 ( x ) , i = 1 , 2 , , , , , , , N r_{mi}=y_i-f_{m-1}(x),i=1,2,,,,,,,N rmi=yifm1(x),i=1,2,,,,,,,N
    • (b)拟合残差r_{mi}学习一个回归树,得到h_m(x)
    • (c)更新 f m ( x ) = f m − 1 + h m ( x ) f_m(x) = f_{m-1}+h_m(x) fm(x)=fm1+hm(x)
  • (3)得到回归问题提升树 f M ( x ) = ∑ m = 1 M h m ( x ) f_M(x)=\sum_{m=1}^Mh_m(x) fM(x)=m=1Mhm(x)

上面伪代码中的残差是什么?

在提升树算法中,

  • 假设我们前一轮迭代得到的强学习器是:f_{t-1}(x)
  • 损失函数是:L(y,f_{t-1}(x))
  • 我们本轮迭代的目标是找到一个弱学习器:h_t(x)
  • 最小化让本轮的损失: L ( y , f t ( x ) ) = L ( y , f t − 1 ( x ) + h t ( x ) ) L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x)) L(y,ft(x))=L(y,ft1(x)+ht(x))
  • 当采用平方损失函数时:

image-20191202174621354

  • 这里, r = y − f t − 1 ( x ) r=y-f_{t-1}(x) r=yft1(x)是t-1Residuals of the moment model(residual),也是tThe value to which the moment model is fitted.
  • 所以,对于提升树来说只需要简单地拟合当前模型的残差(即,找一个模型h_t(x),make its value equal to r).

回到我们上面讲的那个通俗易懂的例子中,第一次迭代的残差是10岁,第二 次残差4岁,


当损失函数是平方损失和指数损失函数时,It is very simple to optimize each step of the boosted tree,但是对于一般损失函数而言,往往每一步优化起来不那么容易.

针对这一问题,Friedman提出了梯度提升树算法,这是利用最速下降的近似方法,其关The key is to use the negative gradient of the loss function as an approximation to the residual in the boosted tree algorithm.

那么负梯度长什么样呢?

  • 第t轮的第i个样本的损失函数的负梯度为:

image-20191202175049374

  • 此时不同的损失函数将会得到不同的负梯度,如果选择平方损失:

image-20191202175132318

  • 负梯度为:

image-20191202175216931

此时我们发现GBDT的负梯度就是残差,所以说对于回归问题,我们要拟合的就是残差.

那么对于分类问题呢?

  • 二分类和多分类的损失函数都是logloss.

本文以回归问题为例进行讲解.

3 GBDT算法原理

上面两节分别将Decision Tree和Gradient Boosting介绍完了,下面将这两部分组合在一起就是我们的GBDT了.


GBDT算法:

  • (1)初始化弱学习器:

    • f_0=C
      • (Cis the average of all data)
  • (2)对m=1,2,…,M有:

    • (a)对每个样本i=1,2,…,N,计算负梯度,When using squared loss,Negative gradients are residuals,即
      • r = y − f m − 1 r = y-f_{m-1} r=yfm1
    • (b)将上步得到的残差作为样本新的真实值,训练一个决策树.
    • (c)更新强学习器:
      • f(m) = f(m-1)+h(m)
  • (3)得到最终学习器 !

    • f(m)=f(0)+h(1)+…+h(m)

4 实例介绍

4.1 数据介绍

根据如下数据,Predict the height of the last sample.

编号年龄(岁)体重(kg)身高(m)(标签值)
05201.1
17301.3
221701.7
330601.8
4(要预测的)2565

4.2 模型训练

4.2.1 设置参数:

  • 学习率:learning_rate=0.1
  • 迭代次数:n_trees=5
  • 树的深度:max_depth=2

4.2.2 开始训练

1.初始化弱学习器:

image-20191202193701842

损失函数为平方损失,因为平方损失函数是一个凸函数,直接求导,The reciprocal equals zero,得到c.

image-20191202193805971

令导数等于0

image-20191202205150158

所以初始化时,c取值为所有训练样本标签值的均值.

c=(1.1+1.3+1.7+1.8)/4=1.475,

At this point the initial learner is obtainedf_0(x):

f_0(x)=c=1.475

2.对迭代轮数m=1,2,…,M:

由于我们设置了迭代次数:n_trees=5,这里的M=5.

计算负梯度,根据上文损失函数为平方损失时,负梯度就是残差,再直白一点就是 y与上一轮得到的学习器f_{m-1}的差值:

image-20191202205540031

The residuals are listed in the table below:

编号真实值f_{0} (x)残差
01.11.475-0.375
11.31.475-0.175
21.71.4750.225
31.81.4750.325

此时将残差作为样本的真实值来训练弱学习器h_{1} (x),即下表数据

编号年龄(岁)体重(kg)标签值
0520-0.375
1730-0.175
221700.225
330600.325

接着,Find the best split node for a regression tree,遍历每个特征的每个可能取值.

from age characteristics5开始,to weight characteristics60结束,分别计算分裂后两组数据的平方损失(Square Error),

例如:以年龄21为划分节点,将小于21The samples of are divided into left nodes,大于等于21的样本划分为右节点.左节点包括x_0, x_1 ,右节点包括样本x_2,x_3

S E l = 0.02 , S E r = 0.005 , S E s u m = 0.025 SE_l = 0.02,SE_r=0.005,SE_{sum}=0.025 SEl=0.02,SEr=0.005,SEsum=0.025

S E l = [ − 0.375 − ( − 0.275 ) ] 2 + [ − 0.175 − ( − 0.275 ) ] 2 = 0.02 SE_l = [-0.375-(-0.275)]^2+[-0.175-(-0.275)]^2 = 0.02 SEl=[0.375(0.275)]2+[0.175(0.275)]2=0.02

S E r = [ 0.225 − 0.275 ] 2 + [ 0.325 − 0.275 ] 2 = 0.005 SE_r = [0.225-0.275]^2+[0.325-0.275]^2 = 0.005 SEr=[0.2250.275]2+[0.3250.275]2=0.005

All possible divisions are shown in the table below:

划分点Samples smaller than the cutoff pointSamples greater than or equal to the split pointSE_lSE_rSE_{sum}
年龄5/0,1,2,300.3270.327
年龄701,2,300.140.14
年龄210,12,30.020.0050.025
年龄300,1,230.18700.187
体重20/0,1,2,300.3270.327
体重3001,2,300.140.14
体重600,12,30.020.0050.025
体重700,1,320.2600.26

以上划分点是的总平方损失最小为0.025有两个划分点:年龄21和体重60,所以随机选一个作为划分点,这里我们选 年龄21 现在我们的第一棵树长这个样子:

image-20191202212643723

我们设置的参数中树的深度max_depth=2,现在树的深度只有1,需要再进行一次划分,这次划分要对左右两个节点分别进行划分:


对于左节点,只含有0,1两个样本,According to the table below we choose年龄7划分

划分点Samples smaller than the cutoff pointSamples greater than or equal to the split pointSE_lSE_rSE_{sum}
年龄5/0,100.020.02
年龄701000
体重20/0,100.020.02
体重3001000

对于右节点,只含有2,3两个样本,According to the table below we choose年龄30划分(也可以选体重70

划分点Samples smaller than the cutoff pointSamples greater than or equal to the split pointSE_lSElSE_rSErSE_{sum}SEsum
年龄21/2,300.0050.005
年龄3023000
体重60/2,300.0050.005
体重7032000

现在我们的第一棵树长这个样子:

image-20191202215005125

此时我们的树深度满足了设置,还需要做一件事情,Calculate the predicted value of each leaf node.

The tree looks like this now:即 h 1 ( x ) h_1(x) h1(x)

image-20191202215443281

此时可更新强学习器,需要用到参数学习率:learning_rate=0.1,用lr表示.

f 1 ( x ) = f 0 ( x ) + h 1 ( x ) f_1(x) = f_0(x)+h_1(x) f1(x)=f0(x)+h1(x)

为什么要用学习率呢?这是Shrinkage的思想,如果每次都全部加上(学习率为1)很容易一步学到位导致过拟合.

重复此步骤,直到 m>5 结束,最后生成5棵树. image-20191202215941986

3.得到最后的强学习器:

f 1 ( x ) = f 0 ( x ) + h 1 ( x ) + h 2 ( x ) + h 3 ( x ) + h 4 ( x ) + h 5 ( x ) f_1(x) = f_0(x)+h_1(x)+h_2(x)+h_3(x)+h_4(x)+h_5(x) f1(x)=f0(x)+h1(x)+h2(x)+h3(x)+h4(x)+h5(x)

4.预测样本(样本4For the test sample):
  • f_0(x)=1.475
  • 在f_1(x)中,样本4的年龄为25,大于划分节点21岁,又小于30岁,所以被预测为0.2250;
  • 在f_2(x)中,样本4的…此处省略…所以被预测为0.2025;
  • 在f_3(x)中,样本4的…此处省略…所以被预测为0.1823;
  • 在f_4(x)中,样本4的…此处省略…所以被预测为0.1640;
  • 在f_5(x)中,样本4的…此处省略…所以被预测为0.1476.

最终预测结果:

f ( x ) = 1.475 + 0.1 ∗ ( 0.225 + 0.2025 + 0.1823 + 0.164 + 0.1476 ) = 1.56714 f(x)=1.475+0.1\ast(0.225+0.2025+0.1823+0.164+0.1476)=1.56714 f(x)=1.475+0.1(0.225+0.2025+0.1823+0.164+0.1476)=1.56714

5 代码

案例一:

from sklearn.ensemble import GradientBoostingRegressor
import numpy as np
X = np.array([[5,20],[7,30],[21,70],[30,60]])
y = np.array([1.1,1.3,1.7,1.8])
clf = GradientBoostingRegressor(learning_rate=0.1,n_estimators=5,max_depth=2,random_state=0)
clf.fit(X, y)
clf.predict([[25,65]])

案例二:

from sklearn.ensemble import GradientBoostingRegressor
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_boston
boston = load_boston()
X = pd.DataFrame(boston.data, columns=boston.feature_names)
y = pd.Series(boston.target)
X_train, X_test, y_train, y_test = train_test_split(X, y)
regressor = GradientBoostingRegressor(
    max_depth=2,
    n_estimators=3,
    learning_rate=1.0
)
regressor.fit(X_train, y_train)
y_pred = regressor.predict(X_test)
y_pred

.225+0.2025+0.1823+0.164+0.1476)=1.56714$

5 代码

案例一:

from sklearn.ensemble import GradientBoostingRegressor
import numpy as np
X = np.array([[5,20],[7,30],[21,70],[30,60]])
y = np.array([1.1,1.3,1.7,1.8])
clf = GradientBoostingRegressor(learning_rate=0.1,n_estimators=5,max_depth=2,random_state=0)
clf.fit(X, y)
clf.predict([[25,65]])

案例二:

from sklearn.ensemble import GradientBoostingRegressor
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_boston
boston = load_boston()
X = pd.DataFrame(boston.data, columns=boston.feature_names)
y = pd.Series(boston.target)
X_train, X_test, y_train, y_test = train_test_split(X, y)
regressor = GradientBoostingRegressor(
    max_depth=2,
    n_estimators=3,
    learning_rate=1.0
)
regressor.fit(X_train, y_train)
y_pred = regressor.predict(X_test)
y_pred

版权声明
本文为[Her han rain Chen]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/328/202211242127010324.html

Scroll to Top