对应学习网址：
https://www.bilibili.com/video/BV1Ca4y1t7DS?from=search&seid=9769587546949536347
感谢原作者，春暖花开Abela
image.png
Tree Model
决策树
分类树
信息熵，衡量信息不确定性的指标
条件熵，H(X|Y=v)
信息增益：I(X,Y)=H(X)-H(X|Y)，表示在一个条件下，信息不确定性减少的程度
基尼指数，随机选中的样本被分错的概率
回归树
每个叶子都输出一个预测值
回归树的分支标准：标准方差
停止条件：变化系数小于阈值，叶子中样本数量小于阈值
集成学习
bagging
随机森林
随机森林=bagging+决策树
分类：众数，回归：均值
样本随机，特征随机
弱学习器独立，投票取结果
boosting
adaboost，gbdt，xgboost，lightgbm
adaboost
将关注点放在被错分的样本上，调整样本权值，预测时，采用加权投票的方法
构建m分类器时，同时更新当前弱分类器的融合权重，以及下一轮的样本的权值分布
gbdt
bdt：boosting decision tree
以CART决策树为基学习器的集成学习方法
第m棵树是对残差的拟合
Gradient Boosting Decision Tree
梯度提升+决策树
利用损失函数的负梯度拟合基学习器
残差就是梯度的相反数，所有GBDT中使用负梯度作为残差进行拟合
GBDT与提升树的区别是，残差使用梯度替代，而且每个基学习器有对应的参数权重
GBDT使用CART回归树，将空间划分为K个不相交的区域
GBDT用于分类仍然使用CART回归树，使用softmax进行概率映射
xgboost
简介
是GBDT的一种，也是加法和前向优化算法
目标函数
包含损失函数，和正则项
因为是决策树，而不是数值型的向量，不能使用梯度下降的算法进行优化
使用贪心算法，寻求局部最优解
泰勒展开
正则项：叶子数量，叶子节点输出分数W的平方和，相当于L2正则化
学习策略
采用贪心算法，每次尝试分裂一个叶节点，计算分裂后的增益，选择增益最大的。
Gain=左子树分数+右子树分数-分裂前分数-新叶节点复杂度
精确贪心算法：枚举所有特征和特征值
复杂度O(Hdlogn)，高
近似算法：根据分位数分桶
全局策略：学习每棵树前---局部策略：树节点分裂时
二阶梯度为权重的分位数算法
优化点
缺失值，全部划为左或者右
列采样：按层随机，按树随机
系统设计
block结构存储，预先排序
缓存优化
out of computation
实现
lightGBM
常用的GBDT工具包，微软开发，比xgboost快，主要在提速，分布式的GBDT
直方图算法
分桶bin，累积一阶&二阶&数量
右子=父-左子
直方图算法的改进
GOSS算法-样本
保留所有大梯度样本，对小梯度样本进行随机采样
Gradient-based One-Side Sampling
EFB算法-特征
将互斥特征合并，能够合并的特征为一个#bundle，从而降低特征维度
Exclusive feature bundling
树的生长策略
level-wise (xgboost，广度)
vs. Leaf-wise（lightgbm，深度）
系统设计
特征并行
数据并行
voting并行（数据并行的一种方式）
PV-Tree