day01-集成决策树模型

1、xgboost原理
1.1 xgboost原始论文
1.2 xgboost原始ppt介绍
1.3 xgboost基础
CART（classification and regression tree）：在给定随机变量X条件下输出Y条件的条件概率分布：
step1: 基于训练数据生成决策树，生成的决策树要尽量大；
step2: 用验证数据集对已经生成的树进行剪枝并选择最优子树，用损失函数最小作为剪枝的标准
分类树和回归树的区别
1） 分类树使用信息增益或者增益比划分节点，每个节点的类别情况投票决定测试样本的类别。
2）回归树使用最大均方差划分节点，每个节点样本的均值作为测试样本的回归预测值。
3）基尼系数，表示集合中被随机选中的一个样本被错误分类的概率，值越小被分错的概率越小。基尼系数 = 被选中的概率*被分错的概率。pk表示被选中的样本属于k类别的概率，则这个样本被分错的概率则为（1-pk），李航《统计学习方法-第一版》p69

基尼系数

回归树
最小二乘法回归树生成算法
输入：训练数据集D
输出：回归树f（x）
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个区域的输出值，构建二叉决策树。
（1）选择最优切分变量j与切分点s，求解

遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对（j，s）。
（2）用选定的对（j，s）划分区域并决定响应的输出值：

（3）继续对两个子区域用步骤（1），（2）直到满足停止条件。
（4）将输入空间划分为M个区域R1，R2，... ，Rm，生成决策树：

回归树示例


1.4 xgboost

单个决策树：

单个决策树
集成思想：
集成
线性回归：
线性回归
逻辑回归：

l（x） = 1 /（1+exp（-y））

目标函数：

xgboost模型是使用k个累加函数预测输出：

最小化正则化目标：

加法训练过程（从第一步开始优化，一直到最后一步）

累加目标函数：

使用泰勒展开式近似目标函数：
泰勒展开式：
泰勒展开式
定义：

目标函数转化：

推导：

定义：

进一步：

对wj求导：

最后：

示例：
示例
贪心不同树：
贪心不同树
2、lightgbm
优势
GBDT采用负梯度作为划分的指标（信息增益），xgboost则是利用二阶导数。

GBDT和xgboost计算信息增益需要扫描所有样本，从而找到最优划分点，面对大量数据或者特征维度很高时，效率和扩展性不好。
提高了速度：
1）压缩了数据的数量
2）压缩了数据的维度
3）降低了训练数据的量
特点：

特点