对应学习网址：
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