工欲善其事，必先利其器。学习集成学习之前，必然要对他内部的弱学习器进行学习才能更好的理解集成学习。

决策树

决策树的结构

决策树学习的 3 个步骤

特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。

在特征选择中通常使用的准则是：信息增益。

决策树生成

选择好特征后，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。

决策树剪枝

剪枝的主要目的是对抗“过拟合”，通过主动去掉部分分支来降低过拟合的风险。

3 种典型的决策树算法

ID3

ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。ID3 是最早提出的决策树算法，他就是利用信息增益来选择特征的。

思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

  1. 初始化特征集合和数据集合；
  2. 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
  3. 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
  4. 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

信息熵是代表随机变量的复杂度（不确定度）通俗理解信息熵 - 知乎专栏

$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$

条件熵代表在某一个条件下，随机变量的复杂度（不确定度）通俗理解条件熵 - 知乎专栏。

$H(D|A) = \sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i) =- \sum_{i=1}^{n}\frac{|D_i|}{|D|}(\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|})$

而我们的信息增益恰好是：信息熵-条件熵。

$Gain(D,A)=H(D)-H(D|A)$

信息增益准则其实是对可取值数目较多的属性有所偏好！这样生成的决策树显然不具有泛化能力。于是我们就引入 了信息增益率来选择最优划分属性！

缺点
  1. ID3 没有剪枝策略，容易过拟合；
  2. 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
  3. 只能用于处理离散分布的特征；
  4. 没有考虑缺失值。

C4.5

他是 ID3 的改进版，他不是直接使用信息增益，而是引入“信息增益率”指标作为特征的选择依据。

  1. 引入悲观剪枝策略进行后剪枝；
  2. 引入信息增益率作为划分标准；
  3. 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
  4. 对于缺失值的处理可以分为两个子问题：
  5. 问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
  6. 问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
  7. 针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
  8. 针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

利用信息增益率可以克服信息增益的缺点，其公式为

$Gain_{ratio}(D,A)=\frac{Gain(D,A)}{H_A(D)} H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$

$H_A(D)$称为特征 A 的固有值。

但是在前面分析了，并不是很好，所以我们需要除以一个属性的固定值，这个值要求随着分成的类别数越大而越小。于是让它做了分母。这样可以避免信息增益的缺点。

那么信息增益率就是完美无瑕的吗？当然不是，有了这个分母之后，我们可以看到增益率准则其实对可取类别数目较 少的特征有所偏好！毕竟分母越小，整体越大。

于是C4.5算法不直接选择增益率最大的候选划分属性，候选划分属性中找出信息增益高于平均水平的属性（这样保证了大部分好的的特征），再从中选择增益率最高的（又保证了不会出现编号特征这种极端的情况）

剪枝策略

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

预剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

  • 节点内数据样本低于某一阈值；
  • 所有节点特征都已分裂；
  • 节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

后剪枝

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

缺点
  • 剪枝策略可以再优化；
  • C4.5 用的是多叉树，用二叉树效率更高；
  • C4.5 只能用于分类；
  • C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
  • C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

CART（Classification and Regression Tree）

CART 包含的基本过程有分裂，剪枝和树选择。

  • 分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
  • 剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
  • 树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

CART 在 C4.5 的基础上进行了很多提升。

  • C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
  • C4.5 只能分类，CART 既可以分类也可以回归；
  • CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
  • CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
  • CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。
划分标准

熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点。基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）正好相反。

​ $Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$

​ $p_k$ 是每个类别的概率

思想是最小化不不纯度，而不是最大化信息增益

缺失值处理

上文说到，模型对于缺失值的处理会分为两个子问题：

  1. 如何在特征值缺失的情况下进行划分特征的选择？

    CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据，在后续版本中，CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响（例如，如果一个特征在节点的 20% 的记录是缺失的，那么这个特征就会减少 20% 或者其他数值）。

  2. 选定该划分特征，模型对于缺失该特征值的样本该进行怎样处理？

    CART 算法的机制是为树的每个节点都找到代理分裂器，无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中，特征的分值必须超过默认规则的性能才有资格作为代理（即代理就是代替缺失值特征作为划分特征的特征），当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

剪枝策略

采用一种“基于代价复杂度的剪枝”方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。

类别不平衡

CART 的一大优势在于：无论训练数据集有多失衡，它都可以将其子冻消除不需要建模人员采取其他操作。

回归树

CART（Classification and Regression Tree，分类回归树），从名字就可以看出其不仅可以用于分类，也可以应用于回归。其回归树的建立算法上与分类树部分相似，这里简单介绍下不同之处。

对于连续值的处理，CART 分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中，我们使用常见的和方差度量方式，对于任意划分特征 A，对应的任意划分点 s 两边划分成的数据集$D_1$和$D_2$ ，求出使$D_1$和$D_2$各自集合的均方差最小，同时$D_1$和$D_2$的均方差之和最小所对应的特征和特征值划分点。表达式为：

$\min\limits_{a,s}\Bigg[\min\limits_{c_1}\sum\limits_{x_i \in D_1}(y_i - c_1)^2 + \min\limits_{c_2}\sum\limits_{x_i \in D_2}(y_i - c_2)^2\Bigg]$

其中，$C_1$为$D_1$数据集的样本输出均值，$C_2$ 为$D_2$数据集的样本输出均值。

预测方式

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

优点
  • 决策树易于理解和解释，可以可视化分析，容易提取出规则；
  • 可以同时处理标称型和数值型数据；
  • 比较适合处理有缺失属性的样本；
  • 能够处理不相关的特征；
  • 测试数据集时，运行速度比较快；
  • 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
缺点
  • 容易发生过拟合（随机森林可以很大程度上减少过拟合）；
  • 容易忽略数据集中属性的相互关联；
  • 对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向；信息增益准则对可取数目较多的属性有所偏好（典型代表ID3算法），而增益率准则（CART）则对可取数目较少的属性有所偏好，但CART进行属性划分时候不再简单地直接利用增益率尽心划分，而是采用一种启发式规则）（只要是使用了信息增益，都有这个缺点，如RF）。
  • ID3算法计算信息增益时结果偏向数值比较多的特征。

除了之前列出来的划分标准、剪枝策略、连续值确实值处理方式等之外，我再介绍一些其他差异：

  • 划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
  • 使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
  • 样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
  • 样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
  • 剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

简单集成技术

Hard Voting 分类器

​ 这是该技术最简单的例子，你可能已经熟练掌握。投票分类器通常用于分类问题。假设你已训练并将一些分类器(逻辑回 归分类器，SVM分类器，随机森林分类器等)与训练数据集进行了匹配。

​ 创建一个更好的分类器的简单方法是将每个分类器所做的预测集合起来，将选择的多数作为最终预测。基本上，我们可 以将其视为检索所有预测器的模式。

平均

​ 上述第一个例子主要用于分类问题。现在，我们来看一种用于回归问题的技术——平均。与Hard Voting类似，我们采用 不同的算法进行多次预测，取其平均值进行最终预测。

加权平均

​ 这种方法是指在求平均数时，根据模型对最终预测的重要性，给模型分配不同的权重。

高级集成技术 集成学习概况

样本选择

Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

样例权重

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

预测函数

Bagging：所有预测函数的权重相等。

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

并行计算

Bagging：各个预测函数可以并行生成

Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

Stacking

​ 这种技术也被称为堆栈泛化，它基于训练模型的思想，将执行我们之前看到的常规集合。

Bagging 与 Pasting

​ 另一种方法是对每个预测器（如树形判定分类法）采用相同的算法，然而，训练集的不同随机子集可以得到更全面的结 果。

​ Bagging核心思路

​ Bagging 的思路是所有基础模型都一致对待，每个基础模型手里都只有一票。然后使用民主投票的方式得到最终的结果。大部分情况下，经过 bagging 得到的结果方差（variance）更小。

Bagging训练过程

具体过程
  1. 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
  2. 每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
  3. 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

图解随机森林

构造随机森林的 4 个步骤
  1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。
  2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
  3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
  4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。
优点
  1. 它可以处理很高维度（特征很多）的数据，并且不用降维，无需做特征选择
  2. 它可以判断特征的重要程度
  3. 可以判断出不同特征之间的相互影响
  4. 不容易过拟合
  5. 训练速度比较快，容易做成并行方法
  6. 实现起来比较简单
  7. 对于不平衡的数据集来说，它可以平衡误差。
  8. 如果有很大一部分的特征遗失，仍可以维持准确度。
缺点
  1. 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。
  2. 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的

随机森林的 4 个应用方向

Boosting

​ 如果第一个模型和下一个模型(可能是所有模型)对一个数据点的预测都不正确，那么其结果的组合会提供更好的预测吗？这就是Boosting的作用所在。

​ Boosting也被称为Hypothesis Boosting，是指任何可以将学习能力弱者组合成学习能力强者的集成方法。这是一个连续的过程，每个模型都试图修正上一个模型的错误。

Boosting核心思路

​ Boosting 和 bagging 最本质的差别在于他对基础模型不是一致对待的，而是经过不停的考验和筛选来挑选出「精英」，然后给精英更多的投票权，表现不好的基础模型则给较少的投票权，然后综合所有人的投票得到最终结果。

​ 大部分情况下，经过 boosting 得到的结果偏差（bias）更小。

Boosting训练过程

具体过程
  1. 通过加法模型将基础模型进行线性的组合。
  2. 每一轮训练都提升那些错误率小的基础模型权重，同时减小错误率高的模型权重。
  3. 在每一轮改变训练数据的权值或概率分布，通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。
AdaBoost

Boosting是一种集合技术，试图从许多弱分类器中创建一个强分类器。这是通过从训练数据构建模型，然后创建第二个模型来尝试从第一个模型中纠正错误来完成的。添加模型直到完美预测训练集或添加最大数量的模型。

AdaBoost是第一个为二进制分类开发的真正成功的增强算法。这是理解助力的最佳起点。现代助推方法建立在AdaBoost上，最着名的是随机梯度增强机。

AdaBoost训练过程

AdaBoost用于短决策树。在创建第一个树之后，每个训练实例上的树的性能用于加权创建的下一个树应该关注每个训练实例的注意力。难以预测的训练数据被赋予更多权重，而易于预测的实例被赋予更少的权重。模型一个接一个地顺序创建，每个模型更新训练实例上的权重，这些权重影响序列中下一个树所执行的学习。构建完所有树之后，将对新数据进行预测，并根据训练数据的准确性对每棵树的性能进行加权。

因为通过算法如此关注纠正错误，所以必须删除带有异常值的干净数据。

AdaBoost优缺点

GBDT

Gradient Boosting是Boosting中的一大类算法，算法1描述了Gradient
Boosting算法的基本流程，在每一轮迭代中，首先计算出当前模型在所
有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合
并计算出该弱分类器的权重，最终实现对模型的更新。

优点
  1. 预测阶段的计算速度快，树与树之间可并行化计算。
  2. 在分布稠密的数据集上，泛化能力和表达能力都很好。
  3. 采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系，并且也不需 要对数据进行特殊的预处理如归一化等。
缺点
  1. GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络。
  2. GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理 数值特征时明显。
  3. 训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。
XGBoost

原始的GBDT算法基于经验损失函数的负梯度来构造新的决策树，只是在决策树构建完成后再进行剪枝。而XGBoost在决策树构建阶段就加入了正则项

XGBoost需要从所有的树结构中找出一个最优的树结构，这是一个NP-hard问题，因此在实际中通常采用贪心算法来构建一个次优的树结构，基本思想是从根节点开始，每次对一个叶子节点进行分裂，针对每一种可能的分裂，根据特定的准则选取最优的分裂。不同的决策树算法采用不同的准则，如ID3算法采用信息增益，C4.5算法为了克服信息增益中容易偏向取值较多的特征而采用信息增益比，CART算法使用基尼指数和平方误差，XGBoost也有特定的准则来选取最优分裂。

通过将预测值代入到损失函数中可求得损失函数的最小值

XGBoost采用最大化这个差值作为准则来进行决策树的构建，通过遍历所有特征的所有取值，寻找使得损失函数前后相差最大时对应的分裂方式。此外，由于损失函数前后存在差值一定为正的限制，此时γ 起到了一定的预剪枝效果。

XGBoost的并行方案
  1. XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
  2. 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。先通过直方图算法获得候选分割点的分布情况，然后根据候选分割点将连续的特征信息映射到不同的buckets中，并统计汇总信息。
GBDT和XGBoost对比
  1. GBDT是机器学习算法，XGBoost是该算法的工程实现。
  2. 在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
  3. GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
  4. 传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。
  5. 传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采样，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
  6. 传统的GBDT没有设计对缺失值进行处理，XGBoost可以自动学习出它的分裂方向。XGBoost对于缺失值能预先学习一个默认的分裂方向。
  7. Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
LightGBM

LightGBM是XGBoost的改进版，相比于前者，它添加了很多新的方法来改进模型，包括:并行方案、基于梯度的单边检测、排他性特征捆绑等。

LightGBM的特征并行方案

LightGBM并没有垂直的切分数据集，而是每个worker都有全量的训练数据，因此最优的特征分裂结果不需要传输到其他worker中，只需要将最优特征以及分裂点告诉其他worker，worker随后本地自己进行处理。处理过程如下：

  1. 每个worker在基于局部的特征集合找到最优分裂特征。
  2. workder间传输最优分裂信息，并得到全局最优分裂信息。
  3. 每个worker基于全局最优分裂信息，在本地进行数据分裂，生成决策树。
LightGBM的数据并行方案

当数据量很大时，特征并行算法还是受限于特征分裂效率。因此，当数据量大时，推荐使用数据并行算法。
算法步骤如下：

  1. LightGBM算法使用Reduce Scatter并行算子归并来自不同worker的不同特征子集的直方图，然后在局部归并的直方图中找到最优局部分裂信息，最终同步找到最优的分裂信息。
  2. 除此之外，LightGBM使用直方图减法加快训练速度。我们只需要对其中一个子节点进行数据传输，另一个子节点可以通过histogram subtraction得到。
  3. LightGBM可以将传输代价降低为O(0.5 * #feature * #bin)。
LightGBM和XGBoost对比
  1. XGBoost使用基于预排序的决策树算法，每遍历一个特征就需要计算一次特征的增益，时间复杂度为O(datafeature)。
    而LightGBM使用基于直方图的决策树算法，直方图的优化算法只需要计算K次，时间复杂度为O(K    feature)
  2. XGBoost使用按层生长(level-wise)的决策树生长策略，LightGBM则采用带有深度限制的按叶子节点(leaf-wise)算法。在分裂次数相同的情况下，leaf-wise可以降低更多的误差，得到更好的精度。leaf-wise的缺点在于会产生较深的决策树，产生过拟合。
  3. 支持类别特征，不需要进行独热编码处理
  4. 优化了特征并行和数据并行算法，除此之外还添加了投票并行方案
  5. 采用基于梯度的单边采样来保持数据分布，减少模型因数据分布发生变化而造成的模型精度下降
  6. 特征捆绑转化为图着色问题，减少特征数量
XGBoost和LightGBM中文情感分析代码

https://gitlab.com/GeorgeBlank/ensumble-classification