GBDT,RandomForest(RF),Xgboost,LightGBM1.CART树损失函数参考上一章的算法过程：Step1：对于数据集D，遍历所有特征，根据Gini(D,A)找到A，用A除DStep2：重复步骤1，为每个节点寻找最好的特征，直到：1）节点样本数小于阈值2)Gini(D,A)小于阈值3)没有更多的特征值2。随机森林（bagging）初始化：决策树的数量n，每棵决策树k中每次拆分选择的特征数量，$k={\log_2}n$森林函数：$f(x)=\frac{1}{n}\sum\limits_i^n{{\varphi_i}(x)}$算法过程：Step1：从原始数据集中有放回抽取n次，每次m个样本Step2：$k={\log_2}n$，对每组m组数据训练CART树，特征是从原始特征中随机选择k块Setp3：每棵树分裂直到Stopcondition（参考CART树）3.AdaBoost（提升）AdaBoost是boosting的思想，弱学习者不断学习以获得强学习者。AdaBoost主要是增加误分类样本的权重，变化的是样本的权重。算法流程：输入：训练数据集$T=\{({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\}$输出：最终分类器$G(x)$1。初始化样本权重${D_0}=({w_{0,1}},{w_{0,2}},...,{w_{0,N}})$2。用${D_m}$的权重样本数据训练M个待训练树（学习者），得到一个分类器${G_m}(x)$，根据${G_m}(x)$计算分类误差：${e_m}=\sum\limits_{i=1}^N{{w_{mi}}}I({G_m}({x_i})\ne{y_i})$计算${G_m}(x)$:${\alpha_m}=\frac{1}{2}\log\frac{{1-{e_m}}}{{{e_m}}}$更新训练样本的权重：$$\begin{array}{l}{D_m}=({w_{m,1}},{w_{m,2}},...,{w_{m,N}})\\{w_{m,i}}=\frac{{{w_{m-1,i}}}}{{{z_m}}}\exp(-{\alpha_m}{y_i}{G_m}({x_i}))\end{array}$$构建最终分类器的线性组合：$$G(x)=sign(\sum\limits_{m=1}^M{{\alpha_m}{G_m}(x)})$$其中权重具有以下特征：${e_m}$较小，${\alpha_m}$较大${w_{m,i}}$的错误分类>${w_{m,i}}的正确分类$4.GBDT(GradientBoostDecisionTree)GradientBoostingTreeGBDT是一种基于回归树的学习器的算法，使用了Boosting的思想。GBDT的核心是每棵树学习之前所有树的残差。将当前模型中损失函数的负梯度值作为回归树的残差近似值。算法流程：输入：训练数据集$T=\{({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\}$Output:回归树$\widehatf(x)$1。初始化：${f_0}(x)=\mathop{\arg\min}\limits_c\sum\limits_{i=1}^N{L({y_i},c)}$2。对于设置M棵树m=1,2,...,M:对于i=1,2,...,N个样本，计算：${r_{mi}}=-{\left[{\frac{{\partialL({y_i},f({x_??i}))}}{{\partialf({x_??i})}}}\right]_{f(x)={f_{m-1}}(x)}}$对${r_{mi}}$拟合一棵回归树，得到第m棵树的最优节点面积${R_{mj}},j=1,2,...,。这个J是J个类别（分类树），叶子节点的个数，可以理解为y值的个数（回归树）求解最优j个区域（特征）的阈值，计算${C_{mj}}=\min\sum\limits_{{x_i}\in{R_{mj}}}{L({y_i},{f_{m-1}}({x_i})+c)}$更新${f_m}(x)={f_{m-1}}(x)+\sum\limits_{j=1}^J{{C_{mj}}I(x\in{R_{mj}})}$3。得到回归树：${f_m}(x)=\sum\limits_{m=1}^M{\sum\limits_{j=1}^J{{C_{mj}}I(x\in{R_{mj}})}}$这里需要说明一点，如果设置树的深度为5，每次分裂为2，则J=10个叶子节点。如果有J个叶子节点，就有J个判断条件。5、XgboostGBDT的升级版，从GBDT的上述算法流程可以看出，它是负梯度中的一阶导数，求解Cmj时是线性搜索。xgboost将Rmj和Cmj一起求解，并在loss函数中加入正则项的算法过程：输入：训练数据集$T=\{({x_1},{y_1}),({x_2},{y_2}),...,({x_N},{y_N})\}$输出：回归树$\widehatf(x)$1。初始化：${f_0}(x)=\mathop{\arg\min}\limits_c\sum\limits_{i=1}^N{L({y_i},c)}$2。设置M棵树m=1,2,...,M：对于i=1,2,...,N个样本，计算一阶导数和${G_t}=\sum\limits_{i=1}^N{{g_{ti}}}$和二阶导数${H_t}=\sum\limits_{i=1}^N{{h_{ti}}}$，其中：$$\begin{array}{l}{g_{ti}}=\frac{{\partialL({y_i},{f_{t-1}}({x_i}))}}{{\partial{f_{t-1}}({x_i})}},{h_{ti}}=\frac{{{\partial^2}L({y_i},{f_{t-1}}({x_i}))}}{{\partial{f_{t-1}}^2({x_i})}}\end{array}$$求解最优j=1,2,...,j区域（特征）和j区域阈值,根据${G_{tj}}=\sum\limits_{xi\in{R_{tj}}}^{}{{g_{ti}}},{H_{tj}}=\sum\limits_{xi\in{R_{tj}}}^{}{{h_{ti}}}$，求叶节点的最优解：${\omega_{tj}}=-\frac{{{G_{tj}}}}{{{H_{tj}}+\lambda}}$，这个区域的解和GBDT类似。对于k=1,2,...,K个特征，将每k个特征线性划分为不同的阈值进行线性搜索。初始化${\rm{score=0}},{G_L}=0,{G_R}=0$，对每个i样本，求左右树的一阶导数和二阶导数：$$\begin{array}{l}{G_L}={G_L}+{g_{ti}},{G_R}=G-{G_L}\\{H_L}={H_L}+{h_{ti}},{H_R}=H-{H_L}\end{array}$$计算$score=\max(score,\frac{1}{2}(\frac{{G_L^2}}{{{H_L}+\lambda}}+\frac{{G_R^2}}{{{H_R}+\lambda}}-\frac{{{{({G_L}+{G_R})}^2}}}{{{H_L}+{H_R}+\λ}})-\gamma)$3。根据最大分数进行拆分4.得到回归树：${f_m}(x)=\sum\limits_{m=1}^M{\sum\limits_{j=1}^J{{C_{mj}}I(x\in{R_{mj}})}}$参考https://ranmaosong.github.io/...6.LightGBM具体算法参考https://zhuanlan.zhihu.com/p/...优化点：特征直方图对不同值的分箱和深度限制的叶节点分裂。xgboost在分裂叶子节点时，不区分同一层的所有叶子节点，权重相同。这是不合适的，因为每个叶节点都有不同的分裂增益。Ligtgbm每层只找一个分裂增益最大的叶节点进行分裂。对每个样本执行权重加稀疏特征池化。这里比较一下GBDT和Xgboost的10个区别：GBDT是机器学习算法，Xgboost是工程实现Xgboost加入正则项防止过拟合Xgboost使用一阶和二阶泰勒展开损失函数Xgboost支持多基learnersXgboost对缺失值进行了处理。xgboost加入了Shrinkage（缩减），每棵树都乘以一个学习率，这样可以多学几轮。Xgboost支持叶节点分裂的并行操作。xgboost采用了??贪心算法，即每次拆分都是最大增益，而不是总的最小损失函数。Xgboost预先对特征进行排序。xgboost支持列采样，参考随机森林特征采样
