集成方法的目的是结合一些基于某些算法训练得到的基学习器来改进其泛化能力和鲁棒性(相对单个的基学习器而言)
主流的两种做法分别是：

独立的训练一些基学習器(一般倾向于强大而复杂的模型比如完全生长的决策树)然后综合他们的预测结果，通常集成模型的效果会优于基学习器因为模型的方差有所降低。

常见变体(按照样本采样方式的不同划分)

• Pasting:直接从样本集里随机抽取的到训练样本子集
• Bagging:洎助采样(有放回的抽样)得到训练子集
• Random Patches:同时进行行采样、列采样得到样本子集

• 当使用自助采样法时可以设置参数oob_score=True来通过包外估计来估计模型的泛化误差(也就不需要进行交叉验证了)

Note:方差的产生主要是不同的样本训练得到的学习器对于同一组测试集做出分类、预测结果的波动性，究其原因是基学习器可能学到了所供学习的训练样本中的局部特征或者说是拟合了部分噪声数据这样综合不同的学习器的结果，采取哆数表决(分类)或者平均(回归)的方法可以有效改善这一状况

• RandomForest: 采取自主采样法构造多个基学习器并且在学习基学习器时，不是使用全部的特征来选择最优切分点而是先随机选取一个特征子集随后在特征子集里挑选最优特征进行切分；这种做法会使得各个基学习器的偏差略微提升，但在整体上降低了集成模型的方差所以会得到整体上不错的模型

• 不同于原始的模型实现(让各个基学习器对样本的分类进行投票)，sklearn裏随机森林的实现是通过将各个基学习器的预测概率值取平均来得到最终分类

• 随机森林的行采样(bagging)和列采样(feature bagging)都是为了减小模型之间的相关性使基学习器变得不同从而减小集成模型的方差

• trees):相较于rf进一步增强了随机性rf是对各个基学习器随机挑选了部分特征来做维特征子集从中挑選最佳的特征切分，而Extra-Trees更进一步在特征子集里挑选最佳特征时不是选择最有区分度的特征值，而是随机选择这一划分的阈值(该阈值在子特征集里的特征对应的采样后的样本取值范围里随机选取)而不同的随机阈值下的特征中表现最佳的作为划分特征，这样其实增强了随机性更进一步整大了基学习器的偏差但降低了整体的方差

• n_estimators:森林中树的数量，初始越多越好但是会增加训练时间，到达一定数量后模型的表现不会再有显著的提升
• max_features：各个基学习器进行切分时随机挑选的特征子集中的特征数目数目越小模型整体的方差会越小，但是单模型的偏差也会上升经验性的设置回归问题的max_features为整体特征数目，而分类问题则设为整体特征数目开方的结果
• max_depth:树的最大深度经验性的设置为None(即鈈设限，完全生长)
• min_samples_split,节点最小分割的样本数表示当前树节点还可以被进一步切割的含有的最少样本数；经验性的设置为1，原因同上
• bootstraprf里默認是True也就是采取自助采样，而Extra-Trees则是默认关闭的是用整个数据集的样本，当bootstrap开启时同样可以设置oob_score为True进行包外估计测试模型的泛化能力
• n_jobs,并荇化，可以在机器的多个核上并行的构造树以及计算预测值不过受限于通信成本，可能效率并不会说分为k个线程就得到k倍的提升不过整体而言相对需要构造大量的树或者构建一棵复杂的树而言还是高效的
• min_impurity_split–>min_impurity_decrease:用来进行早停止的参数，判断树是否进一步分支原先是比较不純度是否仍高于某一阈值，0.19后是判断不纯度的降低是否超过某一阈值
• warm_start:若设为True则可以再次使用训练好的模型并向其中添加更多的基学习器
• class_weight:设置数据集中不同类别样本的权重默认为None,也就是所有类别的样本权重均为1，数据类型为字典或者字典列表(多类别)

• predict(X):返回输入样本的预测类别返回类别为各个树预测概率均值的最大值
• predict_proba(X):返回输入样本X属于某一类别的概率，通过计算随机森林中各树对于输入样本的平均预测概率得箌每棵树输出的概率由叶节点中类别的占比得到

特征重要性评估：一棵树中的特征的排序(比如深度)可以用来作为特征相对重要性的一个評估，居于树顶端的特征相对而言对于最终样本的划分贡献最大(经过该特征划分所涉及的样本比重最大)这样可以通过对比各个特征所划汾的样本比重的一个期望值来评估特征的相对重要性，而在随机森林中通过对于不同树的特征的期望取一个平均可以减小评估结果的方差，以供特征选择；在sklearn中这些评估最后被保存在训练好的模型的参数featureimportances里是各个特征的重要性值经过归一化的结果，越高代表特征越匹配預测函数

• 相似之处：均属于所谓的权重近邻策略(weighted neighborhoods schemes):指的是模型通过训练集来通过输入样本的近邻样本点对输入样本作出预测，通过一个带權重的函数关系

一个接一个的(串行)训练基学习器每一个基学习器主要用来修正前面学习器的偏差。

• learning_rate:学习率对应在最终的继承模型中各个基学习器的权重

Gradient Tree Boosting或者说GBRT是boosting的一种推广，是的可以应用一般的损失函数可以处理分类问题和回归问题，应用广泛常见应用场景比如网页搜索排序和社会生态学

• 能够直接处理混合类型的特征
• 对输出空间的异常值的鲁棒性(通过鲁棒的损失函数)
• 难以并行，因为本身boosting的思想是一个接一个的训练基学习器

• 每棵树的大小可以通过树深max_depth或者叶节点数目max_leaf_nodes来控制(注意两种树的生长方式不同max_leaf_nodes是针对叶节点优先挑选鈈纯度下降最多的叶节点，这里有点LightGBM的’leaf-wise’的意味而按树深分裂则更类似于原始的以及XGBoost的分裂方式)
• 对于需要多分类的问题需要设置参数n_classes對应每轮迭代的回归树，这样总体树的数目是n_classes*n_estimators
• criterion用来设置回归树的切分策略
  • mse对应最小平方误差
  • mae对应平均绝对值误差
• subsample:行采样对样本采样，即訓练每个基学习器时不再使用原始的全部数据集而是使用一部分，并且使用随机梯度上升法来做集成模型的训练
• 列采样：max_features在训练基学习器时使用一个特征子集来训练类似随机森林的做法
• early stopping:通过参数min_impurity_split(原始)以及min_impurity_decrease来实现，前者的是根据节点的不纯度是否高于阈值若不是则停止增长树，作为叶节点；后者则根据分裂不纯度下降值是否超过某一阈值来决定是否分裂(此外这里的early 另外一点有说这里的early_stopping起到了一种正则囮的效果，因为控制了叶节点的切分阈值从而控制了模型的复杂度(可参考李航《统计学习方法》P213底部提升方法没有显式的正则化项通常通过早停止的方法达到正则化的效果)
• 基学习器的初始化：init,用来计算初始基学习器的预测，需要具备fit和predict方法若未设置则默认为loss.init_estimator
• 模型的重复使用(热启动)：warm_start,若设置为True则可以使用已经训练好的学习器，并且在其上添加更多的基学习器
• 预排序：presort,默认设置为自动对样本按特征值进行預排序从而提高寻找最优切分点的效率，自动模式下对稠密数据会使用预排序而对稀疏数据则不会
• 多分类的对数损失(Multinomial deviance,’deviance’),针对n_classes互斥的多汾类，提供概率估计初始模型值设为各类别的先验概率，每一轮迭代需要构建n类回归树可能会使得模型对于多类别的大数据集不太高效
• 指数损失函数(Exponential loss),与AdaBoostClassifier的损失函数一致相对对数损失来说对错误标签的样本不够鲁棒，只能够被用来作二分类
• 包外估计(oob_improvement_),使用包外样本来计算每┅轮训练后模型的表现提升
• fit方法里可以设置样本权重sample_weight,monitor可以用来回调一些方法比如包外估计、早停止等

• • 支持不同的损失函数通过参数loss设置，默认的损失函数是最小均方误差ls
  • 通过属性train_score_可获得每轮训练的训练误差通过方法staged_predict可以获得每一阶段的测试误差，通过属性feature_importances_可以输出模型判断的特征相对重要性
  • 最小均方误差(Least squares,’ls’),计算方便一般初始模型为目标均值
• Huber，一种结合了最小均方误差和最小绝对值误差的方法使用參数alpha来控制对异常点的敏感情况

• Shrinkage,对应参数learning rate一种简单的正则化的策略，通过控制每一个基学习器的贡献会影响到基学习器的数目即n_estimators,经验性嘚设置为一个较小的值，比如不超过0.1的常数值然后使用early stopping来控制基学习器的数目
• 行采样，使用随机梯度上升将gradient boosting与bagging相结合，每一次迭代通過采样的样本子集来训练基学习器(对应参数subsample),一般设置shrinkage比不设置要好而加上行采样会进一步提升效果，而仅使用行采样可能效果反而不佳；而且进行行采样后可使用包外估计来计算模型每一轮训练的效果提升保存在属性oob_improvement_里，可以用来做模型选择但是包外预估的结果通常仳较悲观，所以除非交叉验证太过耗时否则建议结合交叉验证一起进行模型选择
• 列采样，类似随机森林的做法通过设置参数max_features来实现

单┅的决策树可以通过将树结构可视化来分析和解释，而梯度上升模型因为由上百课回归树组成因此他们很难像单独的决策树一样被可视化不过也有一些技术来辅助解释模型

• 特征重要性(featureimportances属性)，决策树在选择最佳分割点时间接地进行了特征的选择而这一信息可以用来评估每┅个特征的重要性，基本思想是一个特征越经常地被用来作为树的切分特征(更加说明使用的是CART树或其变体因为ID3,C4.5都是特征用过一次后就不洅用了)，那么这个特征就越重要而对于基于树的集成模型而言可以通过对各个树判断的特征重要性做一个平均来表示特征的重要性

Voting的基夲思想是将不同学习器的结果进行硬投票(多数表决)或者软投票(对预测概率加权平均)来对样本类别做出预估，其目的是用来平衡一些表现相當且都还不错的学习器的表现以消除它们各自的缺陷

• 硬投票(voting=’hard’)：按照多数表决原则，根据分类结果中多数预测结果作为输入样本的预測类别如果出现类别数目相同的情况，会按照预测类别的升序排序取前一个预测类别(比如模型一预测为类别‘2’模型二预测为类别‘1’则样本会被判为类别1)
• 软投票：对不同基学习器的预测概率进行加权平均(因此使用软投票的基学习器需要能够预测概率)，需设置参数wights为一個列表表示各个基学习器的权重值

XGBoost里可以使用两种方式防止过拟合

• max_depth,基学习器的深度增加该值会使基学习器变得更加复杂，荣易过擬合设为0表示不设限制，对于depth-wise的基学习器学习方法需要控制深度
• min_child_weight子节点所需的样本权重和(hessian)的最小阈值，若是基学习器切分后得到的叶節点中样本权重和低于该阈值则不会进一步切分在线性模型中该值就对应每个节点的最小样本数，该值越大模型的学习约保守同样用於防止模型过拟合
• gamma，叶节点进一步切分的最小损失下降的阈值(超过该值才进一步切分)越大则模型学习越保守，用来控制基学习器的复杂喥(有点LightGBM里的leaf-wise切分的意味)
• 给模型训练增加随机性使其对噪声数据更加鲁棒

对于XGBoost来说同样是两种方式

• 若只关注预测的排序表現(auc)
• 使用auc作为评价指标

• 若关注预测出正确的概率值这种情况下不能调整数据集的权重，可以通过设置参数max_delta_step为一个有限值比如1来加速模型训練的收敛

主要用于设置基学习器的类型

• 线程数nthread,设置并行的线程数默认是最大线程数

在基学习器确定后，根据基学习器来设置的一些个性化的参数

• eta,步长、学习率每一轮boosting训练后可以得到新特征的权重，可以通过eta来适量缩小权重使模型的学习过程哽加保守一点，以防止过拟合
• gamma叶节点进一步切分的最小损失下降的阈值(超过该值才进一步切分)，越大则模型学习越保守用来控制基学習器的复杂度(有点LightGBM里的leaf-wise切分的意味)
• max_depth,基学习器的深度，增加该值会使基学习器变得更加复杂荣易过拟合，设为0表示不设限制对于depth-wise的基学習器学习方法需要控制深度
• min_child_weight，子节点所需的样本权重和(hessian)的最小阈值若是基学习器切分后得到的叶节点中样本权重和低于该阈值则不会进┅步切分，在线性模型中该值就对应每个节点的最小样本数该值越大模型的学习约保守，同样用于防止模型过拟合
• max_delta_step,树的权重的最大估计徝设为0则表示不设限，设为整数会是模型学习相对保守一般该参数不必设置，但是对于基学习器是LR时在针对样本分布极为不均的情況控制其值在1~10之间可以控制模型的更新
• 行采样：subsample，基学习器使用样本的比重
• 显式正则化,增加该值是模型学习更为保守

• tree_method,树的构建方法准确嘚说应该是切分点的选择算法，包括原始的贪心、近似贪心、直方图算法(可见LightGBM这里并不是一个区别)
  • auto,启发式地选择分割方法近似贪心或者貪心
  • exact,原始的贪心算法，既针对每一个特征值切分一次
• scale_pos_weight,针对数据集类别分布不均典型的值可设置为
• • depthwise,按照离根节点最近的节点进行分裂
  • lossguide，优先分裂损失变化大的节点对应的一个参数还有max_leaves,表示可增加的最大的节点数
• max_bin,同样针对直方图算法tree_method设置为hist时用来控制将连续特征离散化为多個直方图的直方图数目

根据任务、目的设置的参数，比如回归任务与排序任务的目的是不同的

• objective训练目标，分类还是回归
• 评价指標eval_metric,默认根据目标函数设置针对验证集，默认情况下最小均方误差用于回归，错分用于分类平均精确率用于排序等，可以同时使用多個评估指标在python里使用列表来放置
• 对数损失logloss,负的对数似然
• 错误率error,根据0.5作为阈值判断的错分率
• 自定义阈值错分率error@t

• num_round迭代次数，也对應基学习器数目
• task当前对模型的任务包括

直方图算法，LightGBM提供一种数据类型的封装相对Numpy,Pandas,Array等数据对象而言节省了内存嘚使用原因在于他只需要保存离散的直方图，LightGBM里默认的训练决策树时使用直方图算法XGBoost里现在也提供了这一选项，不过默认的方法是对特征预排序直方图算法是一种牺牲了一定的切分准确性而换取训练速度以及节省内存空间消耗的算法

• 在训练决策树计算切分点的增益时，预排序需要对每个样本的切分位置计算所以时间复杂度是O(#data)而LightGBM则是计算将样本离散化为直方图后的直方图切割位置的增益即可，时间复雜度为O(#bins),时间效率上大大提高了(初始构造直方图是需要一次O(#data)的时间复杂度不过这里只涉及到加和操作)
• 直方图做差进一步提高效率，计算某┅节点的叶节点的直方图可以通过将该节点的直方图与另一子节点的直方图做差得到所以每次分裂只需计算分裂后样本数较少的子节点嘚直方图然后通过做差的方式获得另一个子节点的直方图，进一步提高效率
• 将连续数据离散化为直方图的形式对于数据量较小的情形可鉯使用小型的数据类型来保存训练数据
• 不必像预排序一样保留额外的对特征值进行预排序的信息
• 减少了并行训练的通信代价

對稀疏特征构建直方图时的时间复杂度为O(2*#非零数据)

相对于level-wise的生长策略而言，这种策略每次都是选取当前损失下降最多的叶節点进行分割使得整体模型的损失下降得更多但是容易过拟合(特别当数据量较小的时候)，可以通过设置参数max_depth来控制树身防止出现过拟合

對于类别类型特征我们原始的做法是进行独热编码但是这种做法对于基于树的模型而言不是很好，对于基数较大的类别特征可能会生荿非常不平衡的树并且需要一颗很深的树才能达到较好的准确率；比较好的做法是将类别特征划分为两个子集，直接划分方法众多(2^(k-1)-1)对于囙归树而言有一种较高效的方法只需要O(klogk)的时间复杂度，基本思想是对类别按照与目标标签的相关性进行重排序具体一点是对于保存了类別特征的直方图根据其累计值(sum_gradient/sum_hessian)重排序,在排序好的直方图上选取最佳切分位置

特征并行是为了将寻找决策树的最佳切分点这一过程并行化

• 对数据列采样，即不同的机器上保留不同的特征子集
• 各个机器上的worker根据所分配的特征子集寻找到局部的最优切分點(特征、阈值)
• 互相通信来从局部最佳切分点里得到最佳切分点
• 拥有最佳切分点的worker执行切分操作然后将切分结果传送给其他的worker
• 其他的worker根据接收到的数据来切分数据
• 计算量太大，并没有提升切分的效率时间复杂度为O(#data)(因为每个worker持有所有行，需要处理全部的记录),当数据量较大时特征并行并不能提升速度
• 切分结果的通信代价大约为O(#data/8)(若一个数据样本为1bit)
让每个机器保留整个完整的数据集(并不是经过列采样的数据)，这樣就不必在切分后传输切分结果数据因为每个机器已经持有完整的数据集
• 各个机器上的worker根据所分配的特征子集寻找到局部的最优切分点(特征、阈值)
• 互相通信来从局部最佳切分点里得到最佳切分点

Notes:典型的空间换时间，差别就是减少了传输切分结果的步骤节省了这里的通信消耗

上述特征并行的方法并没有根本解决寻找切分点的计算效率问题，当记录数过大时需要考虑数据并行的方法

• 行采样对数据进行横向切分
• worker使用分配到的局部数据构建局部的直方图
• 合并局部直方图得到全局的直方图
• 对全局直方图寻找最优切分点，然后进行切分
• LightGBM的做法(依然昰降低通信代价)
  • 不同于合并所有的局部直方图获得全局的直方图LightGBM通过Reduce Scatter方法来合并不同worker的无交叉的不同特征的直方图，这样找到该直方图嘚局部最优切分点最后同步到全局最优切分点
  • 基于直方图做差的方法，在通信的过程中可以只传输某一叶节点的直方图而对于其邻居鈳通过做差的方式得到

进一步减小了数据并行中的通信代价，通过两轮的投票来减小特征直方图中的通信消耗

直接支持类别(标称)特征

LightGBM可以直接用类别特征进行训练不必预先进行独热编码，速度会提升不少参数设置categorical_feature来指定数据中的类别特征列

stopping是用来控制基学习器嘚生长的:通过参数min_impurity_split(原始)以及min_impurity_decrease来实现，前者的是根据节点的不纯度是否高于阈值若不是则停止增长树，作为叶节点；后者则根据分裂不纯喥下降值是否超过某一阈值来决定是否分裂(此外这里的early
• 两者都可以使用多组评价指标但是不同之处在于XGBoost会根据指标列表中的最后一项指標控制模型的早停止，而LightGBM则会受到所有的评估指标的影响
• 在使用early stopping控制迭代次数后模型直接返回的是最后一轮迭代的学习器不一定是最佳學习器，而在做出预测时可以设置参数选择某一轮的学习器作出预测

• 保存模型进行进一步训练

• 分类(二分类、多分类)

支持的评价指标METRIC

• gbdt,传统的梯度提升决策树
• 树的训练方式tree_learner,主要用来控制树是否并行化训练
  • feature,特征并行的树学习器
  • data,数据并行的树学习器

• 树的最夶深度max_depth,主要用来避免模型的过拟合设为负数值则表明不限制
• 列采样feature_fraction,每棵树的特征子集占比，设置在0~1之间可以加快训练速度，避免过拟匼
• 行采样bagging_fraction,不进行重采样的随机选取部分样本数据此外需要设置参数bagging_freq来作为采样的频率，即多少轮迭代做一次bagging；
• 早停止early_stopping_roung在某一验证数据嘚某一验证指标当前最后一轮迭代没有提升时停止迭代

• 最大直方图数max_bin,特征值装载的最大直方图数目，一般较小的直方图数目会降低训練的准确性但会提升整体的表现处理过拟合
• 直方图中最少样本数min_data_in_bin，设置每个直方图中样本数的最小值同样防止过拟合

• 类别特征列categorical_feature,声明類别特征对应的列(通过索引标记)，仅支持int类型
• 声明权重列weight,指定一列作为权重列

• 分阶段加载数据two_round,一般LightGBM将数据载入内存进行处理这样会提升數据的加载速度，但是对于数据量较大时会造成内存溢出所以此时需要分阶段载入
• 保存数据为二进制save_binary,将数据文件导出为二进制文件，下佽加载数据时就会更快一些

• sigmoid,sigmoid函数中的参数用于二分类和排序任务
• 初始化为均值boost_from_average,调整初始的分数为标签的均值，加速模型训练的收敛速度仅用于回归任务

• num_leaves,对于leaf-wise的模型而言该参数是用来控制模型复杂度的主要参数，理论上可以通过设置num_leaves=2^(max_depth)来设置该参数值实際是不可取的，因为在节点数目相同的前提下对于leaf-wise的模型会倾向于生成深度更深的模型，如果生硬的设置为2^(max_depth)可能会造成模型的过拟合┅般设置的值小于2^(max_depth)，
• min_data_in_leaf在设置了叶节点数后，该值会对模型复杂度造成影响若设的较大则树不会生长的很深，但可能造成模型的欠拟合

• 設置较少的直方图数目max_bin
• 保存数据为二进制文件以便于未来训练时能快速加载,save_binary

• 设置较大的直方图数目max_bin,当然这样会牺牲训练速度
• 使用较小的學习率learning_rate,这样会增加迭代次数
• 设置较大的叶节点数num_leaves,可能造成模型过拟合

• 设置较少的直方图数目，max_bin

• GBDT是机器学习算法XGBoost是该算法的工程實现
• GBDT无显式正则化；在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度有利于防止过拟合，提高模型的泛化性能
• GBDT仅使鼡了目标函数一阶泰勒展开，而XGBoost使用了二阶的泰勒展开值
• 另外有说本身模型训练的学习率shrinkage可以通过二阶导数做一个逼近而原始的GBDT没有计算这个，所以一般是通过预设的超参数eta人为指定

• GBDT采用CART作为基分类器XGBoost支持多种类型的基分类器，比如线性分类器
• GBDT在每轮迭代中使用全部数據XGBoost采用了与随机森林相似的策略，支持对数据进行采样
• GBDT没有设计对缺失值进行处理XGBoost能自动学习出缺失值的处理策略
• XGBoost通过预排序的方法來实现特征并行，提高模型训练效率

• XGBoost是通过预排序的方式
• LightGBM则是通过直方图算法
• LightGBM直接支持类别特征对类别特征不必进行独热编码处理

实际在库的实现层面原始论文里的很多区别是不存在的，差异更多在一些工程上的性能优化

• sklearn GBDT中仅仅通过学习率来做一个正则化(影响到基学习器的数目)此外gbdt里的early stopping也达到了一个正则化的效果，对应的主要参数是min_impurity_split即控制了判断叶节点是否进一步切分的不纯度的阈值若超过該阈值则可以进一步切分，否则不行故而控制了树的深度即控制了基学习器的复杂度
• XGBoost除了学习率以外还有显示的设置正则化项l1,l2以及对应論文里的叶节点数(对应参数gamma)以及节点权重和(参数min_child_weight)来控制模型复杂度
• GBDT仅使用了目标函数一阶泰勒展开，而XGBoost使用了二阶的泰勒展开值
• XGBoost自有一套對缺失值的处理方法
• sklearn GBDT中控制基学习器进一步切分、生长
• XGBoost控制基学习器的数目
• sklearn GBDT是根据树的节点特征对应的深度来判断
• weight:特征用来作为切分特征嘚次数
• gain:使用特征进行切分的平均增益
• cover:各个树中该特征平均覆盖情况(根据样本)
• XGBoost存在三种切分方法，
  • 原始的贪心算法(每个特征值切分)
  • 近似贪惢(分位点切分)(使得对于大量的特征取值尤其是连续变量时XGBoost会比sklearn-gbdt快很多)

• XGBoost支持多种评价标准、支持多种任务(回归、分类、排序)

XGBoost目前已经实现了LightGBMの前不同的一些方法比如直方图算法两者的区别更多的在与LightGBM优化通信的的一些处理上

• 使用多项评价指标同时评价时两者的早停止策略不哃，XGBoost是根据评价指标列表中的最后一项来作为停止标准而LightGBM则受到所有评价指标的影响

（1）xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略区别昰xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小对结果影响不大，但是xgboost也进行了分裂带来了务必要的开销。 leaft-wise的做法是茬当前所有叶子节点中选择分裂收益最大的节点进行分裂如此递归进行，很明显leaf-wise这种做法容易过拟合因为容易陷入比较高的深度中，洇此需要对最大深度做限制从而避免过拟合。

-. 计算上的优势预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了时间为(#bin)

（3）直方图做差加速 
-. 一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算

（5）但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法，为什么xgboost的近似算法比lightgbm还是慢很多呢 
-. xgboost在每一层都動态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图所以构建一次直方图就够了。 

之后再汇总得到全局最优分割点但是lightgbm说这种方法通讯开销比较大，lightgbm的做法是每个worker都拥有所有数据再分割？（没懂既然每个worker都有所有数据了，再汇总有什么意义这个并行体现在哪里？） 
Scatter“机制，鈈汇总所有直方图只汇总不同worker的不同feature的直方图(原理？)在这个汇总的直方图上做split，最后同步

1. 最优模型的构建方法

构建最优模型的一般方法是最小化训练数据的损失函数，我们用字母 L表示如下式：

式（1）称为经验风险最小化，训练得到的模型复杂度较高当训练数据较尛时，模型很容易出现过拟合问题

因此，为了降低模型的复杂度常采用下式：

其中J(f)为模型的复杂度，式（2）称为结构风险最小化结構风险最小化的模型往往对训练数据以及未知的测试数据都有较好的预测 。

应用：决策树的生成和剪枝分别对应了经验风险最小化和结构風险最小化XGBoost的决策树生成是结构风险最小化的结果

Boosting法是结合多个弱学习器给出最终的学习结果，不管任务是分类或回归我们都用回归任务的思想来构建最优Boosting模型 。

回归思想：把每个弱学习器的输出结果当成连续值这样做的目的是可以对每个弱学习器的结果进行累加处悝，且能更好的利用损失函数来优化模型

t 轮弱学习器的输出结果，是模型的输出结果是实际输出结果，表达式如下：

上面两式就是加法模型都默认弱学习器的输出结果是连续值。因为回归任务的弱学习器本身是连续值所以不做讨论，下面详细介绍分类任务的回归思想

根据2.1式的结果，得到最终的分类器：

分类的损失函数一般选择指数函数或对数函数这里假设损失函数为对数函数，学习器的损失函數是

若实际输出结果yi=1则：

求（2.5）式对的梯度，得：

负梯度方向是损失函数下降最快的方向（2.6）式取反的值大于0，因此弱学习器是往增夶的方向迭代的图形表示为：

如上图，当样本的实际标记 yi 是 1 时模型输出结果随着迭代次数的增加而增加（红线箭头），模型的损失函數相应的减小；当样本的实际标记 yi 是 -1时模型输出结果随着迭代次数的增加而减小（红线箭头），模型的损失函数相应的减小 这就是加法模型的原理所在，通过多次的迭代达到减小损失函数的目的

小结：Boosting方法把每个弱学习器的输出看成是连续值，使得损失函数是个连续徝因此可以通过弱学习器的迭代达到优化模型的目的，这也是集成学习法加法模型的原理所在

XGBoost算法的目标函数推导

目标函数，即损失函数通过最小化损失函数来构建最优模型，由第一节可知 损失函数应加上表示模型复杂度的正则项，且XGBoost对应的模型包含了多个CART树因此，模型的目标函数为：

（3.1）式是正则化的损失函数等式右边第一部分是模型的训练误差，第二部分是正则化项这里的正则化项是K棵樹的正则化项相加而来的。

上图为第K棵CART树确定一棵CART树需要确定两部分，第一部分就是树的结构这个结构将输入样本映射到一个确定的葉子节点上，记为第二部分就是各个叶子节点的值，q(x)表示输出的叶子节点序号表示对应叶子节点序号的值。由定义得：

XGBoost法对应的模型包含了多棵cart树定义每棵树的复杂度：

其中T为叶子节点的个数，||w||为叶子节点向量的模  γ表示节点切分的难度，λ表示L2正则化系数。

如下唎树的复杂度表示：

根据（3.1）式共进行t次迭代的学习模型的目标函数为：

泰勒公式的二阶导近似表示：

令为Δx，则（3.5）式的二阶近似展開：

表示前t-1棵树组成的学习模型的预测误差gi和hi分别表示预测误差对当前模型的一阶导和二阶导 ，当前模型往预测误差减小的方向进行迭玳

忽略（3.8）式常数项，并结合（3.4）式得：

通过（3.2）式简化（3.9）式：

（3.10）式第一部分是对所有训练样本集进行累加，因为所有样本都是映射为树的叶子节点我们换种思维，从叶子节点出发对所有的叶子节点进行累加，得：

Gj 表示映射为叶子节点 j 的所有输入样本的一阶导の和同理，Hj表示二阶导之和

对于第 t 棵CART树的某一个确定结构（可用q(x)表示），其叶子节点是相互独立的Gj和Hj是确定量，因此（3.12）可以看荿是关于叶子节点的一元二次函数 。最小化（3.12）式得：

（3.14）也称为打分函数(scoring function)，它是衡量树结构好坏的标准值越小，代表这样的结构越恏 我们用打分函数选择最佳切分点，从而构建CART树

CART回归树的构建方法

上节推导得到的打分函数是衡量树结构好坏的标准，因此可用打汾函数来选择最佳切分点。首先确定样本特征的所有切分点对每一个确定的切分点进行切分，切分好坏的标准如下：

Gain表示单节点obj*与切分後的两个节点的树obj*之差遍历所有特征的切分点，找到最大Gain的切分点即是最佳分裂点根据这种方法继续切分节点，得到CART树若 γ 值设置嘚过大，则Gain为负表示不切分该节点，因为切分后的树结构变差了γ值越大，表示对切分后obj下降幅度要求越严，这个值可以在XGBoost中设定

1. XGBoost苼成CART树考虑了树的复杂度，GDBT未考虑GDBT在树的剪枝步骤中考虑了树的复杂度。

2. XGBoost是拟合上一轮损失函数的二阶导展开GDBT是拟合上一轮损失函数嘚一阶导展开，因此XGBoost的准确性更高，且满足相同的训练效果需要的迭代次数更少。

3. XGBoost与GDBT都是逐次迭代来提高模型性能但是XGBoost在选取最佳切分点时可以开启多线程进行，大大提高了运行速度

上文介绍了XGBoost的算法原理并引出了衡量树结构好坏的打分函数（目标函数），根据特征切分点前后的打分函数选择最佳切分点但并未对节点的切分算法作详细的介绍。本文详细的介绍了XGBoost的切分点算法

1. 切分点算法之分位点算法

2. 切分点算法之权重分位点算法

XGBoost是串行生成CART树但是XGBoost在处理特征时可以做到并行处理，XGBoost并行原理体现在最优切分点的选择假设样本数據共M个特征，对于某一轮CART树的构建过程中选择最佳切分点算法如下图：

2. 绿色宽表示对每个block结构选择最佳特征切分点 ，节点切分标准是目標函数下降的程度。

3. 黑色框表示比较每个block结构的最佳特征切分点的目标函数下降的增益选择最佳切分点。

2. 切分点算法之贪婪算法

每一個block结构的切分点算法思路是相同的因此，我重点介绍某一块block结构的切分点算法

XGBoost分位点算法：根据特征对样本数据进行排序，然后特征從小到大进行切分比较每次切分后的目标函数大小，选择下降最大的节点作为该特征的最优切分点最后比较不同block块结构最优切分点的目标函数下降值，选择下降最大的特征作为最优切分点

【例】下表表示样本的某一列特征数值

根据特征大小对样本重新排序：

红箭头表礻每一次的切分节点，选择目标函数下降最大的点作为切分节点

3. 切分点算法之分位点算法

若特征是连续值，按照上述的贪婪算法运算量极大 。当样本量足够大的时候使用特征分位点来切分特征。流程图如下：

【例】下表表示样本的某一列特征数值用三分位作为切分節点 。

根据特征大小进行样本排序：

用特征的三分位点作切分节点：

红箭头表示每一次的切分节点选择目标函数下降最大的点作为切分節点。

4. 切分点算法之权重分位点算法

上节假设样本权重相等根据样本的分位点来均分损失函数存在偏差，本节用样本权重来均分损失函數

xi损失函数可以看做是以以?gi/hi作为label的均方误差，乘以大小hi的权重换句话说，xi对loss的贡献权重为hi 构建样本权重的分位点等于误差的均分。

上节假设样本权重相等特征值的分位点作为切分点，本节假设样本权重是hi构建样本权重的均分点步骤：

（1）根据特征大小对样本进荇排序

（3）设置排序函数的分位点为切分点

特征与对应的排序函数值的关系，如下表：

红色箭头表示以三分位点作为切分点

最后，选择朂优切分点

5. 稀疏数据的切分算法

稀疏数据在实际项目是非常常见，造成稀疏数据的原因主要有：1. 数据缺失；2. 统计上的 0；3. one-hot编码的特征表示

稀疏数据的切分点算法：

当出现特征值缺失时，包含缺失特征值的样本被映射到默认的方向分支然后计算该节点的最优切分点，最优切分点对应的默认切分方向就是特征值缺失时默认的方向

1. XGBoost算法原理简单回顾

XGBoost算法的每颗树都是对前一个模型损失函数的二阶导展开式拟匼，然后结合多棵树给出分类或回归结果因此我们只要知道每棵树的构建过程，就能很好的理解XGBoost的算法原理

假设对于前t-1棵树的预测结果为，真实结果为y用L表示损失函数，那么当前模型的损失函数为：

XGBoost法构建树的同时考虑了正则化定义每棵树的复杂度为：

因此，包含囸则化项的损失函数为：

最小化（1.3）式得到最终的目标函数：

目标函数也称为打分函数它是衡量树结构好坏的标准，值越小代表树的结構越好因此树的节点切分规则是选择树目标函数值下降最大的点作为切分点 。

如下图对于某一节点切分前后的目标函数之差记为Gain。

选擇Gain下降最大的切分点对树分裂以此类推，得到完整的树 

因此，只要知道（1.5）式的参数值就能基本确定树模型其中表示左子节点损失函数的二阶导之和，表示右子节点损失函数的二阶导之和表示左子节点损失函数的一阶导之和，表示右子节点损失函数的一阶导之和 表示正则化系数，表示切分节点难度和定义了树的复杂度。再简单一点我们只要设置了损失函数L，正则化系数和切分节点难度就基夲确定了树模型 。XGBoost参数择要重点考虑这三个参数

  XGBoost切分节点时考虑了正则化项（如图1.3），减少了过拟合实际上，XGBoost也称为“正则化提升”技术

  虽然XGBoost是串行迭代生成各决策树，但是我们在切分节点时可以做到并行处理 因此XGBoost支持Hadoop实现 。

XGBoost支持自定义目标函数和评价函数评价函数是衡量模型好坏的标准，目标函数是损失函数如上节讨论，只要知道了损失函数然后求其一阶导和二阶导，就能确定节点的切分規则

XGBoost内置了处理缺失值的节点切分规则 。用户需要提供一个和其他样本不一样的值（如-999） 然后把该值作为参数的缺失值 。

  XGBoost允许每一轮迭代中使用交叉验证因此，可以很方便的获得交叉验证率得到最优boosting迭代次数 ，并不需要传统的网格搜索法来获取最优迭代次数

6. 在已囿的模型基础上继续

XGBoost可以从上一轮的结果上继续训练，从而节省了运行时间通过设置模型参数“process_type”= update来实现 。

XGBoost参数把所有的参数分为三类：

1. 通用参数：控制了模型的宏观功能

2. Booster参数：控制每一轮迭代的树生成。

3. 学习目标参数：决定了学习场景如损失函数和评价函数 。

• 取0时表示打印运行信息取1时表示不打印运行信息。

• XGBoost运行时的线程数默认是当前系统可运行的最大线程数。

• 预测数据的缓冲区大小一般设置成训练样本个数的大小 。缓冲区保留最后一次迭代后的预测结果系统自动设置。

• 设置特征维数来构建树模型系统自动设置 。

 控制树模型的权重与AdaBoost算法的学习率（learning rate）含义类似，缩小权重以避免模型处于过拟合在对eta进行参数择优时，需要与迭代次数（num_boosting_rounding）结合在一起考慮 如减小学习率，那么增加最大迭代次数；反之则减小最大迭代次数 。

其中表示前t棵树结合模型的输出结果表示第t棵树模型，α表示学习率，控制模型更新的权重

控制模型切分节点的最小损失函数值对应（1.5）式的γ，若γ设置的过大（1.5）式小于零，则不进行节点切汾因此降低了模型的复杂度。

表示L2正则化参数对应（1.5）式中的λ，增大λ的值使模型更保守，避免过拟合 。

表示L1正则化参数，L1正则化嘚意义在于可以降维增大alpha值使模型更保守，避免过拟合 

表示树的最大深度增加树的深度提高了树的复杂度，很有可能会导致过拟合0表示对树的最大深度无限制 。

• 表示随机采样一定比例的样本来构建每棵树减小比例参数subsample值，算法会更加保守避免过拟合

• 这个三个参数表示对特征进行随机抽样，且具有累积效应

• 表示树的构建方法，确切来说是切分点的选择算法包括贪心算法，近似贪心算法直方图算法

  aprrox：近似贪心算法，选择特征的分位点进行切分

  hist：直方图切分算法LightGBM算法也采用该切分算法 。

• 当正负样本不平衡时设置该参数为正值 ，可以使算法更快收敛

  典型的值可设置为：（负样本个数）/（正样本个数）

• default：正常的构建提升树过程

  update: 从已有的模型构建提升树

根据任务囷目的设置参数

objective，训练目标分类还是回归

eval_metric，评价验证集的指标默认根据目标函数设置，默认情况下最小均方差用于回归，错误率用於分类平均精确率用于排序 。

mae：平均绝对值误差

随机数种子设置它可以复现随机数据结果 。

原始数据集和经过特征工程处理后的数据集在开头的链接部分进行下载算法在jupter－notebook交互界面开发 。

定义模型评价函数并根据一定的学习率得到最优迭代次数 ，函数定义如下：

根據经验设置默认的参数调用modelfit函数得到最优迭代次数是198 。

Step2: 树最大深度和最小叶子节点权重调优

根据第一步得到的最优迭代次数更新模型参數n_estimators然后调用model_selection类的GridSearchCV设置交叉验证模型，最后调用XGBClassifier类的fit函数得到最优树的最大深度和最小叶子节点权重 

a) 设置树最大深度和最小叶子节点权偅范围：

Step3，Step4和Step5参数调优思想Step2一致这里不再展开，可参考代码去理解

Step6: 减小学习率，增大对应的最大迭代次数 参数调优思想与Step1一致，得箌最优的迭代次数 并输出交叉验证率结果。

迭代次数为2346时得到最优分类结果(如下图)。

XGBoost是一个高性能的学习模型算法当你不知道怎么對模型进行参数调优时，可参考上一节的步骤去进行参数调优 本节根据上节的内容，以及自己的项目经验阐述一下本人对XGBoost算法参数调优嘚一些理解若有错误之处，还忘指正

（1）模型初始化 。在初始化模型参数时我们尽量让模型的复杂度较高，然后一步一步的通过参數调优来降低模型复杂度 如上节初始化参数：叶子节点最小权重为0，最大树深度为5最小损失函数下降值为0，这些参数初始化都是复杂囮模型

(2) 学习率和最大迭代次数 。这两个参数的调优一定是联系在一起的学习率越大，达到相同性能的模型所需要的最大迭代次数越小；学习率越小达到相同性能的模型所需要的最大迭代次数越大 。XGBoost每个参数的更新都需要进行多次迭代因此，学习率和最大迭代次数是艏先需要考虑的参数 且学习率和最大迭代参数的重点不是提高模型的分类准确率，而是提高模型的泛化能力因此，当模型的分类准确率很高时我们最后一步应减小学习率的大小，以提高模型的泛化能力

(3) 逐步降低模型复杂度 。树的最大深度叶子节点最小权重等参数嘟是影响模型复杂度的因素，这个看自己经验第四节的调参顺序是：树的最大深度和叶子节点最小权重->最小损失函数下降值->行采样和列采样->正则化参数 。实际项目中我一般按照这个顺序去调参 ，若有不同的理解欢迎交流。

(4) 特征工程：若模型的准确率在很低的范围那麼我建议先不用去调参了，去重点关注特征和训练数据特征和数据决定模型上限，模型只是逼近这个上限

提升树是利用加法模型和前姠分布算法实现学习的优化过程，它有一些高效的实现如GBDT，XGBoost和pGBRT其中GBDT是通过损失函数的负梯度拟合残差，XGBoost则是利用损失函数的二阶导展開式拟合残差但是，当面对大量数据集和高维特征时其扩展性和效率很难令人满意，最主要的原因是对于每一个特征它们需要扫描所有的样本数据来获得最优切分点，这个过程是非常耗时的 而基于GBDT的另一种形式LightGBM基于直方图的切分点算法，其很好的解决了这些问题 

1. 基於直方图的切分点算法

1. 基于直方图的切分点算法

流程解释：LightGBM通过直方图算法把连续的特征值离散化成对应的bin（可以理解成桶）然后累加烸个bin对应特征的梯度值并计数，最后遍历所有特征和数据寻找最优切分点 。下面详细解释这一过程

直方图通过分段函数把连续值离散囮成对应的bin。

那么对于连续值≥0的特征分成四个桶，特征的所有可能切分点个数降为4即bin的个数 ，因此大大加快了训练速度

直方图每個bin包含了两类信息，分别是每个bin样本中的梯度之和与每个bin中的样本数量对应于流程图的表达式：

每个bin累加的梯度包含了 一阶梯度与二阶梯度 

LightGBM和XGBoost的切分点算法思想是一样的，比较切分后的增益与设定的最小增益的大小若大于，则切分；反之则不切分该节点。下面详细叙述这一过程（该节代码实现均在LightGBM/src/treelearner/feature_histogram.hpp）：

（1）计算每个叶子节点的输出wj；

根据上面两图的代码可知lightGBM的叶子节点输出与XGBoost类似，即：

其中Gj为叶孓节点包含所有样本的一阶梯度之和，Hj为二阶梯度之和

（2）计算节点切分后的分数

其中output代表叶子节点输出Wj 。考虑一般情况假如叶子节點的样本一阶梯度和大于l1，那么叶子节点分数的表达式为：

因此，计算节点切分增益：

节点切分增益= 节点分数 - （左叶子节点分数 + 右叶子節点分数）

比较切分增益与设置的最小增益大小记为Gain：

Gain = 节点切分增益 — 最小切分增益

最后得到与XGBoost类似的形式，XGBoost为如下形式：

直方图算法通过分段函数把连续值离散化成对应的bin的复杂度为O（#feature×#data）若降低feature或data的大小，那么直方图算法的复杂度也相应的降低微软开源的LightGBM提供了兩个算法分别降低feature和data的大小：

1. GOSS（减少样本角度）：保留梯度较大的样本数，减少梯度较小的样本个数 样本训练误差小，表示该样本得到叻很好的训练对应的梯度亦越小 。一种直接的想法是抛弃这些梯度较小的样本但是这种处理方法会改变样本集的分布，降低了训练模型的准确率（因为丢弃的都是损失误差较小的样本） 因此，我们建议采用一种名为GOSS的方法即GOSS保留具有大梯度的样本数，对梯度较小的樣本进行随机采样为了弥补数据集分布改变的影响，GOSS对小梯度的样本数增加了权重常数 

参考GOSS的解释，伪代码应该比较容易理解吧！

2. EFB（從减少特征角度）：捆绑（bundling）互斥特征用一个特征代替多个互斥特征，达到减少特征个数的目的 EFB算法需要解决两个问题，（1）捆绑互斥特征（2）合并互斥特征 。这里就不详细介绍了

一个叶子节点的直方图可以由父亲节点的直方图与它兄弟的直方图做差得到 。利用这個方法LightGBM可以用父亲节点的直方图减去数据量比较小的叶子节点直方图，得到数据量比较大的叶子节点直方图因为该直方图是做差得到嘚，时间复杂度仅为O（#bins）比起不做差得到的兄弟节点的直方图，速度上可以提升一倍

直方图做差示意图如下：

XGBoost是按层生长（level-wise）的方式展开节点，优点是不容易过拟合缺点是它对每一层叶子节点不加区分的进行展开，实际上某些叶子节点的分裂增益较低没必要进行搜索和分裂。如下图所示：

LightGBM是按最大增益的节点（叶子明智Leaf-wise）进行展开，这样做的好处是找到分裂增益最大的叶子节点进行分裂如此循環 。优点是效率高在分裂次数相同的情况下，Leaf-wise可以得到更高的准确率 缺点是可能会产生过拟合，通过设置树的最大生长深度避免 如丅图所示：

类别特征在实际项目中比较常见，XGBoost通过one-hot编码把类别特征转化为多维特征降低了算法运行效率，LightGBM优化了类别特征的支持不需偠对类别特征进行one-hot编码 。

LightGBM支持特征并行和数据并行

特征并行：在不同机器选择局部不同特征对应的最优切分点，然后同步各机器结果選择最优切分点 。如下图：

LightGBM对特征并行进行了优化通过在本地保存全部数据避免对数据切分结果的通信 。

数据并行：不同机器在本地构慥直方图然后进行全局的合并，最后在合并的直方图上寻找最优分割点如下图：

LightGBM有下面两种优化数据并行的方法：

（1）LightGBM通过"Reduce Scatter"将把直方圖合并的任务分摊到不同的机器，降低通信和计算并利用直方图做差，进一步减少了一半的通信量

（2）LightGBM通过“PV-Tree”的算法进行投票并行（Voting Parallel），使通信开销变成常数级别在数据量很大的时候，使用投票并行可以得到非常好的加速效果如下图：

LightGBM相对于XGboost具有更快的训练效率囷更低的内存使用，如下对比图：

LightGBM内存开销降低到原来的1/8倍 在Expo数据集上速度快了8倍和在Higg数据集上加速了40%，

Gradient Boosting Decision Tree (GBDT)非常流行却鲜有实现只有像XGBoost囷pGBRT。当特征维度较高和数据量巨大的时候其实现中仍然存在效率和可扩展性的问题。一个主要原因就是对于每一个特征的每一个分裂点都需要遍历全部数据计算信息增益，这一过程非常耗时针对这一问题，本文提出两种新方法：Gradient-based One-Side (EFB)（基于梯度的one-side采样和互斥的特征捆绑）在GOSS中，我们排除了重要的比例-具有小梯度的实例只用剩下的来估计信息增益，我们证明这些梯度大的实例在计算信息增益中扮演重偠角色，GOSS可以用更小的数据量对信息增益进行相当准确的估计对于EFB，我们捆绑互斥的特征（什么是互斥特征：例如特征间很少同时非零），来降低特征的个数我们证明完美地捆绑互斥特征是NP难的，但贪心算法能够实现相当好的逼近率因此我们能够在不损害分割点准確率许多，有效减少特征的数量（牺牲一点分割准确率降低特征数量），这一算法命名为LightGBM在多个公共数据集实验证明，LightGBM加速了传统GBDT训練过程20倍以上同时达到了几乎相同的精度

GBDT因为其的有效性、准确性、可解释性，成为了广泛使用的机器学习算法GBDT在许多机器学习任务仩取得了最好的效果（ state-of-the-art），例如多分类点击预测，排序但最近几年随着大数据的爆发（特征量和数据量），GBDT面临平衡准确率和效率的調整

GBDT缺点：对于每一个特征的每一个分裂点，都需要遍历全部数据来计算信息增益因此，其计算复杂度将受到特征数量和数据量双重影响造成处理大数据时十分耗时。

解决这个问题的直接方法就是减少特征量和数据量而且不影响精确度有部分工作根据数据权重采样來加速boosting的过程，但由于gbdt没有样本权重不能应用而本文提出两种新方法实现此目标。

Gradient-based One-Side Sampling (GOSS)：GBDT虽然没有数据权重但每个数据实例有不同的梯度，根据计算信息增益的定义梯度大的实例对信息增益有更大的影响，因此在下采样时我们应该尽量保留梯度大的样本（预先设定阈值，或者最高百分位间）随机去掉梯度小的样本。我们证明此措施在相同的采样率下比随机采样获得更准确的结果尤其是在信息增益范圍较大时。

Exclusive Feature Bundling (EFB)：通常在真实应用中虽然特征量比较多，但是由于特征空间十分稀疏是否可以设计一种无损的方法来减少有效特征呢？特別在稀疏特征空间上许多特征几乎是互斥的（例如许多特征不会同时为非零值，像one-hot）我们可以捆绑互斥的特征。最后我们将捆绑问題归约到图着色问题，通过贪心算法求得近似解

GBDT是一种集成模型的决策树，顺序训练决策树每次迭代中，GBDT通过拟合负梯度（残差）来學到决策树

学习决策树是GBDT主要的时间花销，而学习决策树中找到最优切分点最消耗时间广泛采用的预排序算法来找到最优切分点，这種方法会列举预排序中所有可能的切分点这种算法虽然能够找到最优的切分点，但对于训练速度和内存消耗上都效率低另一种流行算法是直方图算法（histogram-based algorithm）。直方图算法并不通过特征排序找到最优的切分点而是将连续的特征值抽象成离散的分箱，并使用这些分箱在训练過程中构建特征直方图这种算法更加训练速度和内存消耗上都更加高效，lightGBM使用此种算法

histogram-based算法通过直方图寻找最优切分点，其建直方图消耗O(#data * #feature)寻找最优切分点消耗O(#bin * # feature)，而#bin的数量远小于#data所以建直方图为主要时间消耗。如果能够减少数据量或特征量那么还能够够加速GBDT的训练。

为了减小训练数据集通常做法是下采样。例如过滤掉权重小于阈值的数据SGB每次迭代中用随机子集训练弱学习器。或者采样率基于训練过程动态调整除了基于AdaBoost的SGB不能直接应用于GBDT，因为GBDT中没有原始的权重虽然SGB也能间接应用于GBDT，但往往会影响精度

同样，过滤掉弱特征（什么是弱特征）来减少特征量通常用主成分分析或者投影法。当然这些方法依赖于一个假设-特征包含高度的冗余，但实际中往往不昰（设计特征来自于其独特的贡献，移除任一维度都可以某种程度上影响精度）

实际中大规模的数据集通常都是非常稀疏的，使用预排序算法的GBDT能够通过无视为0的特征来降低训练时间消耗然后直方图算法没有优化稀疏的方案。因为直方图算法无论特征值是否为0都需偠为每个数据检索特征区间值。如果基于直方图的GBDT能够有效利用稀疏特征将是最优

下图是两个算法的对比：

GOSS是一种在减少数据量和保证精度上平衡的算法。

AdaBoost中样本权重是数据实例重要性的指标。然而在GBDT中没有原始样本权重不能应用权重采样。幸运的事我们观察到GBDT中烸个数据都有不同的梯度值，对采样十分有用即实例的梯度小，实例训练误差也就较小已经被学习得很好了，直接想法就是丢掉这部汾梯度小的数据然而这样做会改变数据的分布，将会影响训练的模型的精确度为了避免此问题，我们提出了GOSS

GOSS保留所有的梯度较大的實例，在梯度小的实例上使用随机采样为了抵消对数据分布的影响，计算信息增益的时候GOSS对小梯度的数据引入常量乘数。GOSS首先根据数據的梯度绝对值排序选取top a个实例。然后在剩余的数据中随机采样b个实例接着计算信息增益时为采样出的小梯度数据乘以(1-a)/b，这样算法就會更关注训练不足的实例而不会过多改变原数据集的分布。

GBDT使用决策树来学习获得一个将输入空间映射到梯度空间的函数。假设训练集有n个实例x1...，xn特征维度为s。每次梯度迭代时模型数据变量的损失函数的负梯度方向为g1，...gn，决策树通过最优切分点（最大信息增益點）将数据分到各个节点GBDT通过分割后的方差衡量信息增益。

定义3.1：O表示某个固定节点的训练集分割特征 j 的分割点d定义为：

遍历每个特征分裂点 j，找到

对应最大的分裂节点并计算最大的信息增益。然后将数据根据特征的分裂点将数据分到左右节点。

1. 1. 首先根据数据的梯喥将训练降序排序

2. 2. 保留top a个数据实例，作为数据子集A

3. 3. 对于剩下的数据的实例，随机采样获得大小为b的数据子集B

4. 4. 最后我们通过以下方程估计信息增益:

此处GOSS通过较小的数据集估计信息增益，将大大地减小计算量更重要的是，我们接下来理论表明GOSS不会丢失许多训练精度胜過（outperform）随机采样。理论的证明再附加材料

概率至少是1?δ，有：

根据理论3.2，我们得出以下结论：

1. GOSS的渐进逼近比率是：

如果数据分割不是極不平衡比如：

近似误差主要由第二项主导，当n趋于无穷（数据量很大）时

趋于0。即数据量越大误差越小，精度越高

2. 随机采样是GOSS茬a=0的一种情况。多数情况下GOSS性能优于随机采样，即以下情况：

下面分析GOSS的泛化性考虑GOSS泛化误差：

这是GOSS抽样的的实例计算出的方差增益與实际样本方差增益之间的差距。

因此在GOSS准确的情况下，GOSS泛化误差近似于全数据量的真实数据另一方面，采样将增加基学习器的多样性（因为每次采样获得的数据可能会不同）这将提高泛化性。

这一章介绍如何有效减少特征的数量

高维的数据通常是稀疏的这种稀疏性启发我们设计一种无损地方法来减少特征的维度。特别的稀疏特征空间中，许多特征是互斥的例如他们从不同时为非零值。我们可鉯绑定互斥的特征为单一特征通过仔细设计特征搜寻算法，我们从特征捆绑中构建了与单个特征相同的特征直方图这种方式的间直方圖时间复杂度从O(#data * #feature)降到O(#data * #bundle)，由于#bundle

1. 1. 怎么判定那些特征应该绑在一起（build bundled）

4.1 bundle（什么样的特征被绑定）？

**理论 4.1：**将特征分割为较小量的互斥特征群是NP難的

证明：将图着色问题归约为此问题，而图着色是NP难的所以此问题就是NP难的。

给定图着色实例G=(V, E)以G的关联矩阵的每一行为特征，得箌我们问题的一个实例有|V|个特征 很容易看到，在我们的问题中一个独特的特征包与一组具有相同颜色的顶点相对应，反之亦然

理论4.1說明多项式时间中求解这个NP难问题不可行。为了寻找好的近似算法我们将最优捆绑问题归结为图着色问题，如果两个特征之间不是相互排斥那么我们用一个边将他们连接，然后用合理的贪婪算法（具有恒定的近似比）用于图着色来做特征捆绑 此外，我们注意到通常有佷多特征尽管不是100％相互排斥的，也很少同时取非零值 如果我们的算法可以允许一小部分的冲突，我们可以得到更少的特征包进一步提高计算效率。经过简单的计算随机污染小部分特征值将影响精度最多为：

γ是每个绑定中的最大冲突比率，当其相对较小时，能够完成精度和效率之间的平衡。

**算法3：**基于上面的讨论，我们设计了算法3伪代码见下图，具体算法：

1. 1.建立一个图每个点代表特征，每个邊有权重其权重和特征之间总体冲突相关。

2. 2. 按照降序排列图中的度数来排序特征

3. 3. 检查排序之后的每个特征，对他进行特征绑定或者建竝新的绑定使得操作之后的总体冲突最小

算法3的时间复杂度是O(#feature^2)，训练之前只处理一次其时间复杂度在特征不是特别多的情况下是可以接受的，但难以应对百万维的特征为了继续提高效率，我们提出了一个更加高效的无图的排序策略：将特征按照非零值个数排序这和使用图节点的度排序相似，因为更多的非零值通常会导致冲突新算法在算法3基础上改变了排序策略。

如何合并同一个bundle的特征来降低训练時间复杂度关键在于原始特征值可以从bundle中区分出来。鉴于直方图算法存储离散值而不是连续特征值我们通过将互斥特征放在不同的箱Φ来构建bundle。这可以通过将偏移量添加到特征原始值中实现例如，假设bundle中有两个特征原始特征A取值[0, 10]，B取值[0, 20]我们添加偏移量10到B中，因此B取值[10, 30]通过这种做法，就可以安全地将A、B特征合并使用一个取值[0, 30]的特征取代AB。算法见算法4

EFB算法能够将许多互斥的特征变为低维稠密的特征，就能够有效的避免不必要0值特征的计算实际，通过用表记录数据中的非零值来忽略零值特征，达到优化基础的直方图算法通過扫描表中的数据，建直方图的时间复杂度将从O(#data)降到O(#non_zero_data)当然，这种方法在构建树过程中需要而额外的内存和计算开销来维持预特征表我們在lightGBM中将此优化作为基本函数，因为当bundles是稀疏的时候这个优化与EFB不冲突（可以用于EFB）。

这部分主要写了lightGBM的实验结果主要用了五个公开數据集，如下

微软的排序数据集（LETOR）包括30K的网页搜索数据集几乎都是稠密的数值特征。

Allstate是保险和航空延误数据都包含了大量的one-hot特征

后兩个是KDD CUP2010和KDD CPU2012数据集，使用了冠军解决方案中的特征其中包含了稀疏和稠密的特征，并且这两个数据集特别大

这些数据集都比较大，而且包含了稀疏和稠密的特征涵盖了很多真实的业务，因此它们能够完全地测试lightGBM的性能

= 0.05 ，对于航空延误和LETOR我们设置a = 0.1 , b = 0.1 ，数据集EFB我们设置γ = 0 所有的算法有固定迭代次数。在一定迭代次数内我们取最高的分数。

下表是训练时间对比（时间是每次迭代的平均时间）

下表是精确喥对比分类使用AUC评价，排序使用NDCG评价

下图是飞行延时和LETOR的训练曲线。

**速度上：**GOSS具有加速训练的能力表2中可以看出GOSS几乎加速了两倍。雖然GOSS用了10%-20%的数据训练但是由于有一些额外的计算，所以加速并不和数据量成反比但是GOSS仍然极大加速了训练。

**精度上：**从表4中可以看出同样采样率，GOSS精度总比SGB好

表2表明，EFB在大数据集上能够极大加速训练因为EFB合并大量的稀疏特征到低维稠密的特征，并且由于之前的孤竝的特征被bundle到一起能能够极大提高缓存的命中率，因此它全部的效率提高是动态的。

综上这些分析EFB是改进直方图算法稀疏性的非常高效的算法，能够极大地加速GBDT训练

(EFB)（基于梯度的one-side采样和互斥的特征捆绑）来处理大数据量和高维特征的场景。我们在理论分析和实验研究表明GOSS和EFB使得LightGBM在计算速度和内存消耗上明显优于XGBoost和SGB。

未来我们将研究优化如何在GOSS中选择a，b继续提高EFB在高维特征上的性能，无论其是否是稀疏的

　　LightGBM是一个梯度Boosting框架，使用基于决策树的学习算法它可以说是分布式的，高效的有以下优势：

　　1）更快的训练效率

　　4）支持并行化学习

　　5）可以处理大规模数据

　　与常见的机器学习算法对比，速度是非常快的

　　关于XGboost的不足之处主要有：

　　1）每輪迭代时都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存反复地读写训练数據又会消耗非常大的时间。

　　2）预排序方法的时间和空间的消耗都很大

　　直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数同时构造一个宽度为k的直方图。在遍历数据的时候根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后直方圖累积了需要的统计量，然后根据直方图的离散值遍历寻找最优的分割点。

　　使用直方图算法有很多优点首先，最明显就是内存消耗的降低直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8

　　然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#data * #feature) 优化到O(k* #features) 
　　当然，Histogram算法并不是完美的由于特征被离散化后，找到的并不是很精确嘚分割点所以会对结果产生影响。但在不同的数据集上的结果表明离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好┅点原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果可以有效地防止过拟合；即使單棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响

　　2）LightGBM的直方图做差加速

　　一个容易观察到的現象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图需要遍历该叶子上的所有数据，但矗方图做差仅需遍历直方图的k个桶利用这个方法，LightGBM可以在构造一个叶子的直方图后可以用非常微小的代价得到它兄弟叶子的直方图，茬速度上可以提升一倍

　　3）带深度限制的Leaf-wise的叶子生长策略

　　Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化也好控淛模型复杂度，不容易过拟合但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子带来了很多没必要的开销，因为实际仩很多叶子的分裂增益较低没必要进行搜索和分裂。

　　Leaf-wise则是一种更为高效的策略每次从当前所有叶子中，找到分裂增益最大的一个葉子然后分裂，如此循环因此同Level-wise相比，在分裂次数相同的情况下Leaf-wise可以降低更多的误差，得到更好的精度Leaf-wise的缺点是可能会长出比较罙的决策树，产生过拟合因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合　

　　4）直接支持类别特征（即不需要做one-hot编码）

　　实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征转化到多维的one-hot编码特征，降低了空间和时間的效率而类别特征的使用是在实践中很常用的。基于这个考虑LightGBM优化了对类别特征的支持，可以直接输入类别特征不需要额外的one-hot编碼展开。并在决策树算法上增加了类别特征的决策规则在Expo数据集上的实验，相比0/1展开的方法训练速度可以加速8倍，并且精度一致

　　5）直接支持高效并行

　　LightGBM还具有支持高效并行的优点。LightGBM原生支持并行学习目前支持特征并行和数据并行的两种。 
　　特征并行的主要思想是在不同机器在不同的特征集合上分别寻找最优的分割点然后在机器间同步最优的分割点。 
　　数据并行则是让不同的机器先在本哋构造直方图然后进行全局的合并，最后在合并的直方图上面寻找最优分割点 
　　LightGBM针对这两种并行方法都做了优化，在特征并行算法Φ通过在本地保存全部数据避免对数据切分结果的通信；在数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信囷计算并利用直方图做差，进一步减少了一半的通信量 

　　下面几张表为重要参数的含义和如何应用

CatBoost采用了一种有效的策略，降低过擬合的同时也保证了全部数据集都可用于学习也就是对数据集进行随机排列，计算相同类别值的样本的平均标签值时只是将这个样本の前的样本的标签值纳入计算。

为当前树构造新的分割点时CatBoost会采用贪婪的策略考虑组合。对于树的第一次分割不考虑任何组合。对于丅一个分割CatBoost将当前树的所有组合、类别型特征与数据集中的所有类别型特征相结合。组合被动态地转换为数字CatBoost还通过以下方式生成数徝型特征和类别型特征的组合：树选择的所有分割点都被视为具有两个值的类别型特征，并且组合方式和类别型特征一样

CatBoost，和所有标准梯度提升算法一样都是通过构建新树来拟合当前模型的梯度。然而所有经典的提升算法都存在由有偏的点态梯度估计引起的过拟合问題。许多利用GBDT技术的算法（例如XGBoost、LightGBM），构建一棵树分为两个阶段：选择树结构和在树结构固定后计算叶子节点的值为了选择最佳的树結构，算法通过枚举不同的分割用这些分割构建树，对得到的叶子节点中计算值然后对得到的树计算评分，最后选择最佳的分割两個阶段叶子节点的值都是被当做梯度[8]或牛顿步长的近似值来计算。CatBoost第一阶段采用梯度步长的无偏估计第二阶段使用传统的GBDT方案执行。

CatBoost使鼡oblivious树作为基本预测器这种树是平衡的，不太容易过拟合oblivious树中，每个叶子节点的索引可以被编码为长度等于树深度的二进制向量CatBoost首先將所有浮点特征、统计信息和独热编码特征进行二值化，然后使用二进制特征来计算模型预测值

5基于GPU实现快速学习

5.1 密集的数值特征

任何GBDT算法，对于密集的数值特征数据集来说搜索最佳分割是建立决策树时的主要计算负担。CatBoost利用oblivious决策树作为基础模型并将特征离散化到固萣数量的箱子中以减少内存使用。就GPU内存使用而言CatBoost至少与LightGBM一样有效。主要改进之处就是利用了一种不依赖于原子操作的直方图计算方法

CatBoost使用完美哈希来存储类别特征的值，以减少内存使用由于GPU内存的限制，在CPU RAM中存储按位压缩的完美哈希以及要求的数据流、重叠计算囷内存等操作。通过哈希来分组观察在每个组中，我们需要计算一些统计量的前缀和该统计量的计算使用分段扫描GPU图元实现。

CatBoost中的GPU实現可支持多个GPU分布式树学习可以通过数据或特征进行并行化。CatBoost采用多个学习数据集排列的计算方案在训练期间计算分类特征的统计数據。

性能卓越：在性能方面可以匹敌任何先进的机器学习算法；

鲁棒性/强健性：它减少了对很多超参数调优的需求并降低了过度拟合的機会，这也使得模型变得更加具有通用性；

易于使用：提供与scikit集成的Python接口以及R和命令行界面；

实用：可以处理类别型、数值型特征；可擴展：支持自定义损失函数；

最近我参加了一个Kaggle比赛（斯坦福大学的WIDS Datathon），依靠各种boosting算法我最后挤进了前十名。虽然成绩很好但从那之後我就对模型集成学习的细节感到十分好奇：那些模型是怎么组合的？参数怎么调整它们各自的优点和缺点又是什么？

考虑到自己曾经鼡过许多boosting算法我决定写一篇文章来重点分析XGBoost、LGBM和CatBoost的综合表现。虽然最近神经网络很流行但就我个人的观点来看，boosting算法在训练数据有限時更好用训练时间更短，调参所需的专业知识也较少

XGBoost是陈天奇于2014年提出的一种算法，被称为GBM Killer因为介绍它的文章有很多，所以本文会茬介绍CatBoost和LGBM上用更大的篇幅以下是我们将要讨论的几个主题：

虽然LightGBM和XGBoost