统计学习方法——4.决策树——XGBoost、LightGBM_lr 决策树 lightgbm xgboost公式推导

作者：IT小白 | 2024-07-14 08:15:26

踩

lr 决策树 lightgbm xgboost公式推导

一、介绍

1. XGBoost（极限梯度提升树，eXtreme Gradient Boosting）：

（1）XGB目标函数，一棵树的生成

XGB目标函数：
$X G B 目标函数 = 训练损失 + 正则项（树的复杂度）$
训练损失用于减小偏差，一般用平方损失函数或逻辑回归损失函数。
正则项为全部k棵树的复杂度进行求和作为正则化项，防止模型过拟合。
学习第t棵树：
XGBoost是一个加法模型，通过前一棵树(t-1棵树) + 第t棵树可对目标函数进行换算。
泰勒公式展开：
使用二阶泰勒展开公式继续对目标函数进行替代转换，过程中去掉所有常数项。
定义一棵树：
一棵树 = 叶子结点的权重向量 + 实例->叶子结点的映射关系q（即输入一个样本，其对应落到哪个叶子结点）
定义树的复杂度：
一棵树的复杂度 = 叶子结点的数量 + 叶子结点权重向量的L2范数
叶子结点归组：
将属于同一个叶子结点的所有样本划入到该结点的样本集合中。
据此，将其带入到根据泰勒展开式后的目标函数，继续进行推导换算。
树结构打分：
每个叶子结点的子式都达到最值点时，整个目标函数式Obj才达到最值点。使用一元二次函数的最值公式可以轻易求出每个叶子结点的权重及其此时达到最优的Obj的目标值。

（2）一棵树的生长细节

分裂一个结点：
贪心算法：对每个叶子结点尝试分裂；检测本次分裂是否会给损失函数带来增益，Gain>0 即目标函数下降了，那么就会考虑此次分裂的结果。
寻找最佳分裂点：
分裂一个结点时，会有多个候选分割点，需要寻找最佳分裂点：
- 遍历每个结点的每个特征；
- 对每个特征，按特征值大小将特征值排序；
- 线性扫描，找出每个特征的最佳分裂特征值；
- 在所有特征中找出最好的分裂点（分裂后增益最大的特征及特征值）
  使用贪心算法进行全局扫描，效率很低，所以提出一种加快寻找最佳分裂点的方案：
- 特征预排序+缓存： XGBoost在训练之前，预先对每个特征按照特征值大小进行排序，然后保存为block结构，后面的迭代中会重复地使用这个结构，使计算量大大减小。
- 分位点近似法： 对每个特征按照特征值排序后，采用类似分位点选取的方式，仅仅选出常数个特征值作为该特征的候选分割点，在寻找该特征的最佳分割点时，从候选分割点中选出最优的一个。
- 并行查找： 由于各个特性已预先存储为block结构，XGBoost支持利用多个线程并行地计算每个特征的最佳分割点，这不仅大大提升了结点的分裂速度，也极利于大规模训练集的适应性扩展。
停止生长：
树不可能无限生长下去，有一些限制条件：
1）引入的分裂使得Gain<0时放弃当前的分裂；
2）最大深度max_depth，达到最大深度时停止建树，树深容易过拟合；
3）引入一次分裂计算左右两个叶子结点的样本权重和，若任一一个叶子结点的样本权重低于某一个阈值也会放弃此次分裂。还有一个最小样本权重和，即一个叶子结点的样本数量太少也会放弃分裂，防止树分的太细。

2. LightGBM（轻量级梯度提升机，Light Gradient Boost Machine）：

LightGBM = XGBoost + Histogram(直方图加速算法) + GOSS(基于梯度的单边采样算法) + EFB(互斥特征捆绑算法)

Histogram： 减少候选分裂点的位置。
替换了XGBoost的预排序算法。直方图算法通过将连续特征值离散化到固定数量(如255个)的bins上；
直方图算法还能够作直方图差加速。当节点分裂成两个时，右边叶子节点的直方图等于其父节点的直方图减去左边叶子节点的直方图。
GOSS（基于梯度的单边采样算法，Gradient-based One-Side Sampling）： 减少样本的数量。
通过对样本采样的方法减少计算目标函数增益时的复杂度。
只对梯度绝对值较小的样本按照一定比例进行采样，而保留了梯度绝对值较大的样本。
由于目标函数增益主要来自于梯度绝对值较大的样本，因此这种方法在计算性能和计算精度之间取得了很好的平衡。
（1）根据样本点的梯度的绝对值进行降序排序；
（2）大梯度样本点的子集：对排序后的结果选取前a*100%;
（3）小梯度样本点的集合：对剩下的样本集合(1-a)100%，随机的选取b* (1-a)*100%个样本点;
（4）合并大、小梯度样本集合；
（5）将小梯度样本乘上一个权重系数 $\frac{1-a}{b}$ ；
（6）使用上述的样本训练学习一个新的分类器；
（7）重复（1）-（6）步骤直到设置的迭代次数或者收敛为止。
EFB（互斥特征绑定算法，Exclusive Feature Bundling ）： 减少特征的数量。
EFB可以有效减少用于构建直方图的特征数量，从而降低计算复杂度。
因为数据集中有大量稀疏特征，大部分稀疏特征都取值为0，只有少数取值为非0。
认为这些稀疏特征是互斥的，即它们不会同时取非0值，可以对某些特征的取值重新编码，将多个这样互斥的特征捆绑为一个新的特征

二、代码实现

XGBoost

`pip install xgboost`

`import xgboost as xgb`

`from xgboost.sklearn import XGBClassifier`

# coding=utf-8
import time
import numpy as np
import xgboost as xgb
from xgboost.sklearn import XGBClassifier   # sklearn xgboost

def loadData(fileName):
    '''
    加载文件
    :param fileName:要加载的文件路径
    :return: 数据集和标签集
    '''
    # 存放数据及标记
    dataArr = []
    labelArr = []
    # 读取文件
    fr = open(fileName)
    # 遍历文件中的每一行
    for line in fr.readlines():
        # 获取当前行，并按“，”切割成字段放入列表中
        # strip：去掉每行字符串首尾指定的字符（默认空格或换行符）
        # split：按照指定的字符将字符串切割成每个字段，返回列表形式
        curLine = line.strip().split(',')
        # 将每行中除标记外的数据放入数据集中（curLine[0]为标记信息）
        # 在放入的同时将原先字符串形式的数据转换为整型

        # 此外将数据进行了二值化处理，大于128的转换成1，小于的转换成0，方便后续计算
        # dataArr.append([int(int(num) > 128) for num in curLine[1:]])
        dataArr.append([int(num) for num in curLine[1:]])

        # 将标记信息放入标记集中
        # 放入的同时将标记转换为整型
        labelArr.append(int(curLine[0]))
    # 返回数据集和标记
    return np.mat(dataArr), np.ravel(labelArr)


def train_xgb_model(X_train, Y_train, is_sk=True):
    # 使用xgb原生接口
    if not is_sk:
        # 1. 设置XGBoost的参数
        params = {
            # 通用参数
            'booster': 'gbtree',            # 基学习器类型，包括树模型('gbtree')和线性模型('gblinear')
            'silent': 0,                    # 控制迭代日志是否输出，默认输出其值为0，设为1时静默模式开启，不会输出任何信息
            'nthread': 4,                   # 线程数，默认值为最大可能的线程数


            # booster参数（tree booster性能更改）
            'eta': 0.1,                     # 和Learning Rate相似，默认值为0.3.典型值为0.01-0.2
            'min_child_weight': 3,          # 最小样本权重和，避免过拟合。默认值为1
            'max_depth': 6,                 # 树的最大深度，避免过拟合。默认值为6，典型值为3-10.
            # 'max_leaf_nodes':             # 树的最大结点或叶子的数量
            'gamma': 0.1,                   # 在分裂时，结点分裂后所需的最小(gamma)损失函数下降值。默认为0
            # 'max_delta_step': 0,          # 限制每棵树权重改变的最大步长，这个参数一般不用设置，默认值为0
            'subsample': 0.7,               # 控制每棵树随机采样的比例，默认值为1，典型值为0.5-1
            'colsample_bytree': 0.7,        # 每棵树随机采样的特征数（列数）的占比
            'colsample_bylevel': 0.7,       # 每棵树的每一层的每一次分裂，随机采样的特征数（列数）的占比
            'lambda': 2,                    # 权重的L2正则化项，默认值为1
            'alpha': 2,                     # 权重的L1正则化项，默认值为1
            # 'scale_pos_weight': 1,        # 在各类样本十分不平衡时，把这个参数设定为一个正值，可以使算法更快收敛。


            # 学习目标参数（用来控制优化目标）
            'objective': 'multi:softmax',   # 目标任务是什么，分类还是回归。 multi:softmax 使用softmax的多分类器，返回预测的类别(不是概率); 回归任务设置为：'objective': 'reg:gamma';  binary:logistic 二分类的逻辑回归，返回预测的概率(不是类别)。
            'num_class': 10,                # 回归任务没有这个参数
            # 'eval_metric': 'rmse, mae, ...' # 使用的损失函数

            'seed': 1000,                   # 随机数种子，设置它可以复现随机数据的结果。
            }

        # plst = params.items()

        # 对训练集进行训练
        dtrain = xgb.DMatrix(X_train, Y_train)
        num_rounds = 500
        model = xgb.train(params, dtrain, num_rounds)

    # 使用sklearn接口
    else:
        model = XGBClassifier(
                              learning_rate=0.1,
                              gamma=0.1,
                              reg_alpha=2,
                              reg_lambda=2,
                              max_depth=6,
                              min_child_weight=6,
                              colsample_bytree=0.7,
                              colsample_bylevel=0.7,

                              verbosity=2)    # xgb.XGBClassifier() XGBoost分类模型
        model.fit(X_train, Y_train)

    return model



def model_test(xgb_model, X_test, Y_test, is_sk=True):
    if not is_sk:
        # 对测试集进行预测
        dtest = xgb.DMatrix(X_test)
        ans = xgb_model.predict(dtest)
        # 计算准确率
        cnt1 = 0
        cnt2 = 0
        for i in range(len(Y_test)):
            if ans[i] == Y_test[i]:
                cnt1 += 1
            else:
                cnt2 += 1
        accuracy = cnt1 / (cnt1 + cnt2)

    else:
        accuracy = xgb_model.score(X_test, Y_test)

    return accuracy


if __name__ == '__main__':
    # 开始时间
    start = time.time()

    # 获取训练集
    trainDataList, trainLabelList = loadData('../Mnist/mnist_train.csv')
    # 获取测试集
    testDataList, testLabelList = loadData('../Mnist/mnist_test.csv')

    DT_model = train_xgb_model(trainDataList, trainLabelList, is_sk=True)

    # 测试准确率
    print('start test')
    accur = model_test(DT_model, testDataList, testLabelList, is_sk=True)
    print('the accur is:', accur)

    # 结束时间
    end = time.time()
    print('time span:', end - start)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

LightGBM

`pip install lightgbm`

`import lightgbm as lgb`

`from lightgbm.sklearn import LGBMClassifier`

# coding=utf-8
import time
import numpy as np
from sklearn.metrics import accuracy_score
import lightgbm as lgb                # 原生接口
from lightgbm import LGBMClassifier   # sklearn 接口

def loadData(fileName):
    '''
    加载文件
    :param fileName:要加载的文件路径
    :return: 数据集和标签集
    '''
    # 存放数据及标记
    dataArr = []
    labelArr = []
    # 读取文件
    fr = open(fileName)
    # 遍历文件中的每一行
    for line in fr.readlines():
        # 获取当前行，并按“，”切割成字段放入列表中
        # strip：去掉每行字符串首尾指定的字符（默认空格或换行符）
        # split：按照指定的字符将字符串切割成每个字段，返回列表形式
        curLine = line.strip().split(',')
        # 将每行中除标记外的数据放入数据集中（curLine[0]为标记信息）
        # 在放入的同时将原先字符串形式的数据转换为整型

        # 此外将数据进行了二值化处理，大于128的转换成1，小于的转换成0，方便后续计算
        # dataArr.append([int(int(num) > 128) for num in curLine[1:]])
        dataArr.append([int(num) for num in curLine[1:]])

        # 将标记信息放入标记集中
        # 放入的同时将标记转换为整型
        labelArr.append(int(curLine[0]))
    # 返回数据集和标记
    return np.array(dataArr), np.ravel(labelArr)

def train_lgb_model(X_train, Y_train, is_sk=True):
    # 使用xgb原生接口
    if not is_sk:
        # 1. 设置XGBoost的参数
        params = {
            'learning_rate': 0.1,
            'lambda_l1': 0.1,
            'lambda_l2': 0.2,
            'max_depth': 4,
            'objective': 'multiclass',  # 目标函数
            'num_class': 10,
            }

        # 对训练集进行训练
        # 注意：X_train是numpy类型的数据的话，需为ndarray类型，如果使用的是np.mat则会出错。
        dtrain = lgb.Dataset(X_train, label=Y_train)

        num_rounds = 50
        model = lgb.train(params=params, train_set=dtrain, num_boost_round=num_rounds)

    # 使用sklearn接口
    else:
        model = LGBMClassifier(num_leaves=31, learning_rate=0.1, n_estimators=20)
        model.fit(X_train, Y_train)

    return model

def model_test(lgb_model, X_test, Y_test, is_sk=True):
    if not is_sk:
        # 对测试集进行预测
        y_pred = lgb_model.predict(X_test, num_iteration=lgb_model.best_iteration)   # 此处返回的是softmax类型的概率类别，shape=(num_samples, num_class)
        # 计算准确率
        accuracy = accuracy_score(Y_test, np.argmax(y_pred, axis=1))

    else:
        accuracy = lgb_model.score(X_test, Y_test)

    return accuracy

if __name__ == '__main__':
    # 开始时间
    start = time.time()

    # 获取训练集
    trainDataList, trainLabelList = loadData('../Mnist/mnist_train.csv')
    # 获取测试集
    testDataList, testLabelList = loadData('../Mnist/mnist_test.csv')

    DT_model = train_lgb_model(trainDataList, trainLabelList, is_sk=False)

    # 测试准确率
    print('start test')
    accur = model_test(DT_model, testDataList, testLabelList, is_sk=False)
    print('the accur is:', accur)

    # 结束时间
    end = time.time()
    print('time span:', end - start)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

ps：本博客仅供自己复习理解，不具其他人可参考，本博客参考了大量的优质资源，侵删。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/823923