这是好瓜吗？

(资料图片仅供参考)

西瓜问题的一棵决策树

以上述二分类问题为例，我们对“这是好瓜吗？”这类问题进行决策时，通常会进行一系列判断或“子决策”。决策树（decision tree）就是基于树结构进行决策的，一棵树一般包含一个根节点、若干个内部节点和若干个叶节点，每一条从根结点（对最终分类结果贡献最大的属性）到叶子结点（最终分类结果）的路径都代表一条决策的规则。

决策树通常包含三个步骤： 特征选择、决策树生成和决策树剪枝。

01

特征选择

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

熵、条件熵、信息增益、信息增益率

在明确“熵”的概念之前，我们需要知道信息的定义，如果待分类的事物可能划分在多个分类之中，则符号x i 的信息定义为 ：

（1）熵(entropy)： 集合信息的度量方式称为香农熵或者简称为熵，这个名字来源于信息论之父克劳德·香农。熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。

其中p(x i )是选择该分类的概率。通过上式，我们可以得到所有类别的信息。为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：

其中n是分类的数目。熵越大，随机变量的不确定性就越大。

（2） 条件熵(conditional entropy) ：H(Y|X)表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。条件熵 H(Y|X)定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望：

这里，P i =P（X=x i ），i=1,2,…,n

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。经验条件熵就是在某一条件约束下的经验熵。

（3）信息增 益（information gain）： 信息增益代表了在一个条件下，信息复杂度（不确定性）减少的程度。它的计算方法为：信息增益= 熵 - 条件熵。

信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

总结上述的三个知识点：

熵：表示随机变量的不确定性。

条件熵：在一个条件下，随机变量的不确定性。

信息增益：熵 - 条件熵。表示在一个条件下，信息不确定性减少的程度。

如果选择一个特征后，信息增益最大（信息不确定性减少的程度最大），那么我们就选取这个特征。

02

决策树生成

常见的决策树算法有ID3，C4.5和CART（classification and regression tree），CART的分类效果一般要优于其他决策树。

ID3算法

ID3算法的核心是根据信息增益来选择进行划分的特征，然后递归地构建决策树。ID3是较原始的一个算法，没有剪枝。ID3算法的缺陷如下：

变量偏好多枚举值： ID3更偏好优先分叉枚举值多的变量。因为ID3用信息增益评估分叉质量，该评估函数会更偏好枚举值多的变量。

ID3容易过拟合。

ID3不支持连续变量。

不支持数据有缺失值。

C4.5算法

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入 信息增益率 来作为分类标准。因为使用信息增益的这一分类标准会优先侧重于分类数目较多的这一特征。但是与此同时，引入信息增益率会偏向于分类数目较少的特征，所以我们在实际使用过程中，一般是结合两种方式，一种是首先以信息增益到达某一阈值进行刷选一些特征，之后我们再会采用信息增益率来筛选。

信息增益率 （gain ratio）

实际上，信息增益会偏好于取值数目较多的属性，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法使用增益率来选择最优划分属性。它的计算方法为：信息增益率=信息增益/条件的信息熵。

信息增益率的定义：特征A对训练数据集D的信息增益比ｇ Ｒ (D,A）定义为其信息增益ｇ(D,A）与训练数据集D关于特征A的值的熵H A （Ｄ）之比，即

其中， ，ｎ是特征A取值的个数。

使用信息增益率并不是直接选择最大的特征，而是先在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

CART算法

在ID3算法中,用“熵”来度量数据集随机性的程度。在CART中我们把这种随机性的程度称为“杂度”（impurity，也称为“不纯度”），并且用 基尼指数 来衡量它。

基尼指数（Gini index）定义

在CART算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本都是一个类时，基尼不纯度为零。分类问题中，假设有K个类，样本点属于第ｋ类的概率为ｐ ｋ ，则概率分布的基尼指数 定义为：

对于二分类问题，若样本点属于第１类的概率是ｐ，则概率分布的基尼指数为:

对于给定的样本集合D，其基尼指数为:

这里Ｃ ｋ 是D中属于第ｋ类的样本子集，K是样本的个数。

特征选择过程

若样本集合 D根据特征 A是否取某一可能值 a被分割成 D 1 和 D 2 两部分，即

，

则在特征A的条件下，集合D的基尼指数定义为：

基尼指数 Gini（D）表示集合D的不确定性，基尼指数Gini（D，A）表示经 A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性也就越大。

剪枝过程

CART采用的办法是 后剪枝法 ，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。也就是说，CART树的剪枝算法可以概括为两步，第一步是从原始决策树生成各种剪枝效果的决策树，第二步是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

熵VS基尼指数

比起基尼系数，信息熵对不纯度更加敏感，对不纯度的惩罚更强。但是在实际使用中，信息熵和基尼系数的效果基本相同。信息熵的计算比基尼系数缓慢一些，因为基尼系数的计算不涉及对数。另外，因为信息熵对不纯度更加敏感，所以信息熵作为指标时，决策树的生长会更加“精细”。因此对于高维数据或者噪音很多的数据，信息熵很容易过拟合，基尼系数在这种情况下效果往往比较好。

ID3、C4.5、CART三者之间的区别是什么?

1.划分标准

ID3 使用信息增益偏向特征值多的特征；

C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征；

CART 使用基尼指数克服C4.5 需要求对数的巨大计算量，偏向于特征值较多的特征。

2.使用场景

ID3和 C4.5都只能用于分类问题；CART可以用于分类和回归问题。

ID3和C4.5 是多叉树，速度较慢；CART 是二叉树，计算速度很快。

3.样本数据

ID3只能处理离散数据且缺失值敏感，C4.5和CART可以处理连续性数据且有多种方式处理缺失值;

从样本量考虑的话，小样本建议C4.5、大样本建议CART；

C4.5处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而CART本身是一种大样本的统计方法，小样本处理下泛化误差较大。

4.样本特征

ID3和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征;

5.剪枝策略

ID3 没有剪枝策略;

C4.5 是通过悲观剪枝策略来修正树的准确性;

CART是通过代价复杂度剪枝。

04

基于决策树的集成学习算法

集成学习模型是机器学习非常重要的一部分。其思想是使用一系列的弱学习器（或成为基础模型）进行学习，并将弱学习器的结果进行整合，从而获得比单个学习器更好的学习效果的一种机器学习方式。 集成学习有两种常见的算法： Bagging和 Boosting。

Bagging： 个体学习器间不存在强依赖关系、可同时生成的并行化方法。

Boosting： 个体学习器间存在强依赖关系、必须串行生成的序列化方法。

Bagging算法的典型机器学习模型为 随机森林 。

Boosting算法的典型机器学习模型为 Adaboost、GBDT、XGBoost和 LightGBM等 。

随机森林（RF）

随机森林算法是一种并行式集成学习方法。相较于决策树而言，随机森林在决策树的训练中引入随机属性的选择。

随机森林算法的 主要步骤 是：

从样本集中用Bootstrap随机选取n个样本，并从所有属性中随机选取K个属性，选择最佳分割属性作为节点建立分类器（CART，SVM等）。重复以上m次，即建立了m个分类器，并通过投票表决结果，决定数据属于哪一类。

随机性 主要体现在以下两个方面:

（1）数据的随机性选取。对原数据集采用bootstrap sample method(自助法采样，有放回)，m个样本数据集，m次随机采样得到采样集，如此操作N次, 则有N个含m训练样本的采样集，这样可以训练N个基学习器，再结合得到最终学习器。

（2）待选特征的随机选取。从K个特征中随机选择k个特征，每次分裂时，从k个特征中选取最优的。引入的随机性, 使得RF的泛化能力提升，不易陷入过拟合，且抗噪能力强。

注: RF 分类效果 （error rate）与 两个因素 有关

1）任意两棵树的相关性: 相关性越大, 误差越大

2）每棵树的分类能力: 分类能力越大, 误差越小

关键点: 如何选取k值？

减小特征选择个数k，树的分类能力和任两棵树相关性都会降低。

关键点： 如何选择最优的m（特征个数） ？

要解决这个问题主要依据计算袋外错误率oob error（out-of-bag error）。

随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。

在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第k棵树的oob（out-of-bag）样本。

而这样的采样特点就允许我们进行oob估计，它的计算方式如下： （note：以样本为单位）

1）对每个样本，计算它作为oob样本的树对它的分类情况（约1/3的树）；

2）然后以简单多数投票作为该样本的分类结果；

3）最后用误分个数占样本总数的比率作为随机森林的oob误分率。

oob误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。

与决策树的主要区别

决策树总是存在过度拟合的空间；随机森林算法通过使用多棵树来避免和防止过拟合。

决策树需要低计算量，从而减少了实现时间并且精度低；随机森林会消耗更多的计算量。生成和分析的过程非常耗时。

自适应提升算法（Adaboost）

不同于RF，AdaBoost基于前一棵基础决策树对样本点设置不同的权重，如果在前一棵基础决策树中将某样本点预测错误，就会增大该样本点的权重，否则相应降低样本点的权重，进而再构建下一棵基础决策树，更加关注权重大的样本点。 如果将所有训练样本点带入损失函数中，一定存在一个最佳的权重和决策树，使得损失函数尽量最大化地降低。主要降低模型偏差。

关键词： 加法模型+指数损失函数+前向分布算法

AdaBoost运行的 主要步骤 是：

（１）训练数据集中的每个样本，并赋予其中一个权重，这些权重构成一个向量D，一开始，这些权重都初始化成相等的值。

（２）首先在训练数据集训练出一个弱分类器，并计算该分类器的错误率。

（３）然后在同一数据集上再次训练弱分类器。在第二次训练分类器中，将会重新调整每个样本的权重，其中第一次分类正确样本的权重会降低，第一次分类错误的样本的权重会提高。

为了从所有弱分类器中得到最终结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些权重的值都是基于每个分类器的错误率而计算的。其中错误率的定义为： ε = 未 正 确 分 类 的 样 本 数 目 / 所 有 样 本 数 目，而alpha的计算公式为：

计算出alphas的值之后就可以对权重向量D进行更新，以使得那些正确分类的样本的权重降低，而那些错分的样本的权重升高。D的计算方法如下：

如果某个样本被正确分类，那么该样本的权重更改为：

如果某个样本被错分，那么该样本的权重更改为：

在计算出D之后，AdaBoost又开始进行下一轮迭代。AdaBoost算法会不断地重复训练和调整权重过程，直到训练出错误率为0或者弱分类器的数目达到用户指定的值为止。

梯度提升决策树（GBDT）

常用的GBDT、XGBoost和LightGBM算法(或工具)都是基于梯度提升机的算法思想。 梯度提升决策树GBDT是一种基于集成思想的决策树模型。

关键词：加法模型+负梯度拟合+CART算法+前向分布算法

负梯度拟合即利用损失函数的负梯度来拟合残差的近似值。

GBDT分类和回归时的基学习器都是CART回归树，因为是拟合残差的。

GBDT和Adaboost一样可以用前向分布算法来描述，不同之处在于Adaboost算法每次拟合基学习器时，输入的样本数据是不一样的（每一轮迭代时的样本权重不一致），因为Adaboost旨在重点关注上一轮分类错误的样本。GBDT算法在每一步迭代时是输出的值不一样，本轮要拟合的输出值是之前的加法模型的预测值和真实值的差值（模型的残差，也称为损失）。

GBDT算法运行的主要步骤：

（１）算法每次迭代生成一颗新的决策树

（２）在每次迭代开始之前，计算损失函数在每个训练样本点的一阶导数和二阶导数

（３）通过贪心策略生成新的决策树，并计算每个叶节点对应的预测值

（４）计算每个叶节点对应的预测值 ，并将新生成的决策树添加到模型中。

GBDT算法提供了众多的可选择的损失函数，通过选择不同的损失函数可以用来处理分类、回归问题，比如用对数似然损失函数就可以处理分类问题。常用的损失函数有：

1）对于分类问题可以选用指数损失函数、对数损失函数。

2）对于回归问题可以选用均方差损失函数、绝对损失函数。

3）另外还有huber损失函数和分位数损失函数，也是用于回归问题，可以增加回归问题的健壮性，可以减少异常点对损失函数的影响。

GBDT算法优点：

预测精度高；

适合低维数据；

能处理非线性数据；

可以灵活处理各种类型的数据，包括连续值和离散值；

相对于SVM来说，较少的调参可以达到较好的预测效果；

使用健壮的损失函数时，模型鲁棒性非常强，受异常值影响小。比如 Huber损失函数和Quantile损失函数。

GBDT算法缺点：

由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行；

串行化方法，难以并行训练数据；

如果数据维度较高时会加大算法的计算复杂度。

极端梯度提升算法（XGBoost）

XGBoost 本质上还是一个GBDT，但是力争把速度和效率发挥到极致，XGBoost和 GBDT 两者都是 boosting 方法，除了工程实现、解决问题上的一些差异外，最大的不同就是 目标函数的定义 。 xgboost的目标函数如下：

其中正则项控制着模型的复杂度，包括了叶子节点数目T和leaf score的L2模的平方：

XGBoost 与 GBDT有何不同？

XGBoost 对 GBDT进行了一系列优化，比如目标函数加入正则项、损失函数进行了二阶泰勒展开、支持并行、默认缺失值处理等，再可拓展性和训练速度上都有巨大提升，但其核心思想没有大的变化。

XGBoost为什么快?

（１） 分块并行 :在每次寻找最佳分裂点时都需要对特征的值进行排序极为耗时。而XGBoost 在训练之前根据特征对数据进行排序，然后保存到块（block）结构中，并在每个块结构中都采用了稀疏矩阵存储格式（CSC）进行存储。这种块结构存储的特征之间相互独立，方便计算机进行并行计算。后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点，可以大大减小计算量。

（２） block 处理优化 （“核外”块计算）：当数据量过大时无法将数据全部加载到内存中，只能先将无法加载到内存中的数据暂存到硬盘中，直到需要时再进行加载计算，而这种操作必然涉及到因内存与硬盘速度不同而造成的资源浪费和性能瓶颈。为了解决这个问题，XGBoost 独立一个线程专门用于从硬盘读入数据，以实现处理数据和读入数据同时进行。此外，XGBoost 还用了两种方法来降低硬盘读写的开销：块压缩：对 Block 进行按列压缩，并在读取时进行解压；块拆分：将每个块存储到不同的磁盘中，从多个磁盘读取可以增加吞吐量。block 处理优化的步骤如下：block预先放入内存；block按列进行解压缩；将block划分到不同硬盘来提高吞吐。

（３） 候选分位点 :即每个特征采用常数个分位点作为候选分割点。在对节点进行分裂时需要选择增益最大的特征作为分裂，这使各个特征的增益计算可以同时进行，这也是 Xgboost 能够实现分布式或者多线程计算的原因。XGBoost则采取了一种trade off，近似地找到best split，即一种weighted quantile sketch算法。既然样本数量太大，我们可不可以按比例来选择，从n个样本中抽取k个样本来进行计算，取k个样本中的最优值作为split value，这样就大大减少了运算数量。这就是k分位点选取的思想，即quantile sketch。

（４） CPU cache 命中优化 :块结构的设计可以减少节点分裂时的计算量，但特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续，从而造成缓存命中率低，影响到算法的效率。为了解决缓存命中率低的问题，XGBoost 提出了缓存访问优化算法：为每个线程分配一个连续的缓存区（buffer），读取每个block中样本的梯度信息并存入连续的buffer中，这样就是实现了非连续空间到连续空间的转换，提高了算法效率。

XGBoost使用二阶泰勒展开的目的和优势?

XGBoost使用了一阶和二阶偏导，二阶导数有利于梯度下降的更快更准。可以在不选定损失函数具体形式的情况下，仅仅依靠输入数据的值就可以进行叶子分裂优化计算，本质上也就把损失函数的选取和模型算法优化/参数选择分开了，这种去耦合增加了XGBoost的适用性，使得它按需选取损失函数，可以用于分类也可以用于回归。

XGBoost中如何处理过拟合的情况?

（１）目标函数中增加正则项: 使用叶子节点的数目和叶子节点权重的模的平方，控制树的复杂度。

（２）设置目标函数的增益阈值: 如果分裂后目标函数的增益小于该阈值，则不分裂。

（３）设置最小样本权重和的阈值: 当引入一次分裂后，重新计算新生成的左右两个叶子节点的样本权重和。如果任一个叶子节点的样本权重低于某个阈值 (最小样本权重和)，也会放弃此次分裂。

（４）设置树的最大深度: 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的节点，进行剪枝。

（５）调参:

第一类参数:用于直接控制模型的复杂度。包括max_depthmin_child_weight，gamma 等参数;

第二类参数:用于增加随机性，从而使得模型在训练时对于噪音不敏感包括subsample，colsample_bytree;

还有就是直接减小learning rate但需要同时增加estimator 参数。

XGBoost如何处理缺失值?

（１）在特征k上寻找最佳划分点时，不会对该列特征缺失的样本进行遍历，而只对该列特征值为无缺失的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找划分点的时间开销。

（２）在逻辑实现上，为了保证完备性，会将该特征值缺失的样本分别分配到左叶子节点和右叶子节点，两种情形都计算一遍后，选择分裂后增益最大的那个方向 ，作为预测时特征值缺失样本的默认分支方向。

（３）如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。

XGBoost为什么可以并行训练?

这里讲的并行训练不是说每棵树可以并行训练，而是特征维度是并行的。 XGBoost本质上还是采用Boosting思想，每棵树训练前需要等前面的树训练完成才能开始训练；在训练之前，每个特征按特征值对样本进行预排序，并存储为block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

XGBoost如何处理 不平衡数据 ?

如果采用AUC来评估模型的性能，可以通过设置scale_pos_weight来平衡正负样本的权重。例如，当正负样本比例为1:10时scale_pos_weight可以取10。还可以通过上采样、下采样、SMOTE算法或者自定义代价函数的方式解决正负样本不平衡的问题。在不能重新平衡数据集(会破坏数据的真实分布)的情况下，应该设置max_delta_step为一个有限数字来帮助收敛(基模型为LR时有效)。

XGBoost如何选择最佳分裂点?

训练前预先将特征对特征值进行排序，存储为block结构，以便在节点分裂时可以重复使用；

采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点，根据每次分裂后产生的增益，最终选择增益最大的那个特征的特征值作为最佳分裂点；

XGBoost使用直方图近似算法，对特征排序后仅选择常数个候选分裂位置作为候选分裂点，极大提升了结点分裂时的计算效率。

XGBoost如何评价特征的重要性?

常用的三种方法来评判模型中特征的重要程度:

freq : 频率是表示特定特征在模型树中发生分裂的相对次数的百分比；

gain :增益意味着相应的特征通过对模型中的每个树采取每个特征的贡献而计算出的模型的相对贡献。与其他特征相比，此度量值的较高值意味着它对于生成预测更为重要；

cover : 覆盖度量指的是与此功能相关的观测的相对数量。例如，如果您有100个观察值，4个特征和3棵树，并且假设特征1分别用于决定树1，树2和树3中10个，5个和2个观察值的叶节点；那么该度量将计算此功能的覆盖范围为个观测值。这将针对所有4项功能进行计算，并将以17个百分比表示所有功能的覆盖指标。

XGBoost的优点

精度更高： 传统GBDT在优化时只用到一阶导数信息，XGBoost 则对损失函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。XGBoost 还支持自定义损失函数，只要函数可一阶和二阶求导。对损失函数进行了 二阶泰勒展开 ，增加了精度；

灵活性更强 ：传统GBDT以CART作为 基分类器 ，XGBoost 的基分类器不仅支持CART决策树，还支持线性分类器，因此更加灵活;

正则化： XGBoost在目标函数里加入了 正则项 ，用于控制模型的复杂度。相当于预剪枝，使学习出的模型更加简单，能够 防止过拟合 。

列抽样： XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。

缺失值处理 ： 对于特征值有缺失的样本，XGBoost采用的稀疏感知算法可以自动学习出它的分裂方向。

可并行的近似算法： XGBoost提出了一种可并行的近似算法，用于高效地生成候选的分割点。注意不是树维度的并行，而是特征维度的并行。XGBoost 预先对每个特征值排好序，存储为快结构，分裂节点时，可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。

XGBoost的缺点:

虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍 需要遍历数据集 ；

预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于 消耗 了两倍的 内存 。

LightGBM

LightGBM是一个开源的梯度提升框架，由微软公司在2017年推出。从 LightGBM名字我们可以看出其是轻量级 (Light)的梯度提升机(GBM)，其相对 XGBoost 具有训练速度快、内存占用低的特点。为解决GBDT训练速度慢，内存占用大的缺点，LightGBM 是提出了一下几点解决方案：

基于Histogram（直方图）的决策树算法

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

单边梯度采样 (GOSS)

互斥特征捆绑 (EFB)

直接支持类别特征(Categorical Feature)

支持高效并行

Cache命中率优化

1.基于Histogram的决策树算法

直方图算法的基本思想是将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。

优点:

内存占用更小 : 相比XGB不需要额外存储预排序，且只保存特征离散化后的值(整型)

计算代价更小 : 相比XGB不需要遍历一个特征值就需要计算一次分裂的增益，只需要计算k次(k为箱子的个数)

直方图做差加速 :构建叶节点的直方图时，可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量，在速度上可以提升一倍。

注意: XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。

２.带深度限制的leaf-wise算法

lightGBM使用了带深度限制的按叶子生长leaf-wise算法，抛弃了XGBoost使用的按层生长level-wise算法。

XGBoost使用的按层生长策略要求遍历数据的时候分裂同一层的数据，但它不加以区分地对待同一层的叶子，是一种低效的算法。因为一些叶子的分裂增益低，没必要进行搜索和分裂，从而带来很多不必要的计算开销。 而lightGBM采用的leaf-wise增长策略，该策略从每次当前所有的叶子中，找出分裂增益最大的叶子，然后进行分裂，如此循环。

Leaf-wise的 优点 是:在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度;

Leaf-wise的 缺点 是: 可能会长出比较深的决策树，产生过拟合。因此，LightGBM会在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

3.单边梯度采样算法(GOSS)

GOSS算法从减少样本的角度出发，排除大部分小梯度的样本，仅用剩下的样本计算信息增益，它是一种在减少数据量和保证精度上平衡的算法。其主要思想是通过对样本采样的方法来减少计算目标函数增益时候的复杂度。

用GOSS的方法来选择训练集，梯度大的样本会直接被保留，用于下一颗树的训练，梯度较小的样本通过采样的方式来决定是否进入到下一轮的训练样本中。为了不改变数据的总体分布，GOSS对要进行分裂的特征按照绝对值大小进行排序，选取最大的a个数据，在剩下梯度小的数据中选取b个，这b个数据乘以权重(1-a)/b，最后使用这a+b个数据计算信息增益。

4.互斥特征捆绑算法（EFB）

在稀疏特征空间中，许多特征都是互斥的，也就是他们几乎不同时取非0值，可以把这些互斥特征捆绑到一起形成一个特征，然后基于这些特征来构建直方图。

将哪些特征绑定在一起？ LightGBM的EFB算法将“如何判断哪里特征应该放在一个Bundle中”的 问题转化为图着色的问题来求解，将所有的特征视为图的各个顶点，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点 (特征)。另外，算法可以允许一小部分的冲突，我们可以得到更少的绑定特征，进一步提高计算效率。

如何绑定？ 绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值可以在bundle中识别，考虑到 histogram-based算法将连续的值保存为离散的bins，我们可以使得不同特征的值分到bundle中的不同bins中，这可以通过在特征值中加一个偏置常量来解决，为了把特征绑为一捆，我们常常在特征值中加一个偏置常量来解决。如A特征的值为[0,10),B特征的原始取值区间为[0，20)，那我们在B特征值上加一个偏置10，B特征就变成了[10，30)这样绑定后的取值范围就变成了[0，30)，可以放心捆绑了。

在许多应用场景下，数据集中会有大量的稀疏特征，这些稀疏特征大部分样本都取值为0，只有少数样本取值非0。通常可以认为这些稀疏特征是互斥的，即它们几乎不会同时取非零值。

利用这种特性，可以通过对某些特征的取值重新编码，将多个这样互斥的特征捆绑成为一个新的特征。有趣的是，对于类别特征，如果转换成onehot编码，则这些onehot编码后的多个特征相互之间是互斥的，从而可以被捆绑成为一个特征。因此，对于指定为类别特征的特征，LightGBM可以直接将每个类别取值和一个bin关联，从而自动地处理它们。而无需预处理成onehot编码多此一举。

5.直接支持类别特征(Categorical Feature)

因为大多数机器学习的工具都不支持类别特征，所以需要one-hot编码，转到多维的0/1特征，从而降低时间和空间的效率。而且这还会带来样本切分不平衡的问题，因为只有少量样本是1，大量样本都是0，切分的增益很差，通俗地讲就是切分和不切分都一样。还有个问题就是影响决策树的学习，独热编码会把数据切到很多零碎的空间上。所以lightGBM增加了对类别特征的支持，用 many-vs-many 的方式来切分。

many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。假设某维特征有k个类别，则有2^(k-1)-1种可能,时间复杂度为 (2^k)，在枚举分割点之前，先把直方图按照每个类别对应的label均值进行排序；然后按照排序的结果依次枚举最优分割点。

6.支持高效并行

LightGBM提供以下并行学习算法的优化：特征并行、数据并行、投票并行。

特征并行： 传统的特征并行方法的缺点是需要告知每台机器最终划分结果，增加了额外的复杂度（因为对数据进行垂直划分，每台机器所含数据不同，划分结果需要通过通信告知）。 LightGBM 则不进行数据垂直划分，每台机器都有训练集完整数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

数据并行： 传统的数据并行策略主要为水平划分数据，然后本地构建直方图并整合成全局直方图，最后在全局直方图中找出最佳划分点。缺点仍然是通讯开销过大，LightGBM 采用分散规约（Reduce scatter）的方式将直方图整合的任务分摊到不同机器上，从而降低通信代价，并通过直方图做差进一步降低不同机器间的通信。

投票并行： 针对数据量特别大、特征也特别多的情况下，可以采用投票并行。投票并行主要针对数据并行时数据合并的通信代价比较大的瓶颈进行优化，其通过投票的方式只合并部分特征的直方图从而达到降低通信量的目的。 大致步骤为两步：本地找出 Top K 特征，并基于投票筛选出可能是最优分割点的特征；合并时只合并每个机器选出来的特征。

7.Cache优化

lightGBM通过相同的方式获得梯度（XGBoost通过不同的特征会有不同的方式获得梯度），所以只需要对梯度进行排序即可实现连续访问，大大提高了缓存命中率。其次，lightGBM不需要储存索引，降低了储存的消耗，而且也不存在Cache miss的情况。

05

决策树模型的应用场景

本案例依托电信运营商流失用户的基本信息以及使用行为构建分析模型，用于分析其他用户数据，从中找出潜在流失用户。 用户是否流失，这是一个二分类问题，可以选择构建决策树、梯度提升树模型，比较不同模型效果，选取最优模型。具体步骤包括：数据准备、数据预处理、特征选取、模型构建、模型评估、模型比较。

模型构建界面

模型评估与预测界面

模型的对比界面

06

总结：决策树的优缺点

决策树的优点

便于理解和解释，便于可视化分析；

能够处理数值型数据和分类数据，其他的技术通常只能用来专门分析某一种的变量类型的数据集；

对缺失值不敏感，

比较适合处理有缺失属性的样本；

可以处理不相关特征数据；

能够处理多输出的问题；

效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

决策树的缺点

非常不稳定，受数据的噪音影响——改进方案：集成学习

复杂的树会造成过拟合——改进方案：剪枝

在处理特征关联性比较强的数据时表现得不是太好。

对于各类别样本数量不一致的数据，信息增益的结果偏向于那些具有更多数值的特征。