决策树的理解：

1.2 分类树 信息熵：用来衡量不确定性的指标，不确定性是一个事件出现不同结果的可能性，计算公式如下

条件熵：在给定随记变量Y的条件下，随机变量X的不确定性

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

1.2.2 基尼指数 基尼指数：在样本集合中一个随机选中的样本被分错的概率 注意：Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯；当集合中所有样本为一个类时，基尼指数为0 计算方法：

CART树是一个二叉树，对于一个具有多个取值（超过2个）的特征，需要计算以每个取值作为划分点，对样本D划分之后子集的纯度Gini(D, Ai)，然后从所有可能划分的Gini(D,Ai)中找出Gini指数最小的划分，这个划分的划分点，就是使用特征A对样本集合D进行划分的最佳划分点

1.3回归树 回归树：用树模型做回归问题，每一片叶子都输出一个预测值，预测值一般是叶子节点所含训练集元素输出的均值 回归树的分支标准：标准方差 回归树使用某一特征将原集合分为多个子集，用标准方差衡量子集中的元素是否相近，越小表示越相近

2.1 集成学习简介 集成学习：通过构建并组合多个学习器来完成学习任务的算法，集成学习常用的有两类： Bagging：基学习器之间无强依赖关系，可同时生成并行化方法 Boosting：基学习器之间存在强烈的依赖关系，必须串行生成基分类器的方法 Boosting：将弱学习器提升为强学习器的过程，通过反复学习得到一系列的弱分类器（决策树和逻辑回归），组合这些弱分类器得到一个强学习器；boosting算法要涉及两个部分，即加法模型和前向分布算法 加法模型：强分类器由一系列弱分类器线性相加而成，一般组合形式为

前向分步：在训练过程中，下一轮迭代产生的分类器是在上一轮基础上训练得到的，即

2.2 随机森林 随机森林=bagging+决策树 同时训练多个决策树，预测时综合考虑多个结果进行预测，如取多个节点的均值（回归），或者是众数（分类） 优势：

随机性体现在两点：

注意：随机森林不但数据随机选，特征也是随机选

2.3 Adaboost • Adaboost的思想是将关注点放在被错误分类的样本上，减小上一轮被正确分类的样本权值，提高被错误分类的样本权值 • Adaboost采用加权投票的方法，分类误差小的弱分类器的权重大，而分类误差大的弱分类器的权重小

2.4.1 BDT 提升树（boosting decision tree）:提升树是以cart决策树为基学习器的集成学习方法

第一个训练集是随机选取的数据，后面两个的训练集都是预测值和真实值的残差作为训练集

2.4.2 GBDT GBDT: Gradient boosting decision tree,即梯度上升决策树，可理解为梯度提升+决策树；利用最速下降的近似方法，利用损失函数的负梯度拟合基学习器。 注意： BDT和GBDT的核心都是拟合残差，即第二个及以上的弱学习器都是训练残差; 只是GBDT里是用负梯度来当做残差进行拟合 计算权重的时候就是用前面的学习器预测结果+当前的预测去拟合真实值y，然后去学习一个alpha，这个alpha就是新的弱学习器的权重。

GBDT是用梯度提升的决策树(cart), CART树回归将空间划分为K个不相交的区域，并确定每个区域的输出ck，表达式为 GBDT对于分类问题，是用softmax去进行的映射 2.5 XGBoost Xgboost是GBDT的一种，也是加法模型和前向优化算法 在监督学习中，可以为模型，参数，目标函数和学习方法： • 模型：给定输入x后预测输出y的方法，如回归，分类和排序等 • 参数：模型中的参数，比如线性回归中的权重和偏置 • 目标函数：即损失函数，包含正则化项 • 学习方法：给定目标函数后求解模型和参数的方法，如梯度下降法，数学推导等 这四方面的内容指导着xgboost系统的设计 Xgboost的模型形式 通过目标函数来完成xgboost的模型构建 第t个弱分类器的预测结果等于前面第t-1次弱分类器的结果加上损失函数(残差)

Xgboost中衡量树的复杂度依赖于两个指标：一个是叶子节点的个数，另一个是叶子节点输出分数w的平方和 当数据量很大时，精确贪心算法会很慢，因此需要引入近似算法。近似算法采用了一种分桶的算法，即先将原始样本n划分为l个桶，然后将样本放到对应的桶中，再对每个桶的G，H进行累加，最后在候选切分点集合上进行精确贪心算法。这种方式类似于先找到多个初始解，再从多个初始解的附近开始找精确解。 何时选取切分点？两种方法： • 全局策略：学习每棵树前，提出候选的切分点，当切分点数足够多时，和精确的贪心算法性能相当 • 局部策略：树节点分裂时，重新提出候选切分点，切分点个数不需要那么多，性能与精确贪心算法相差不多 设置步长的目的是为了防止过拟合 树结构的确定——列采样（对于特征的采样） 列抽样技术：一种是按层随机，另一种是按树随机（构建树前就随机选择特征） • 按层随机方式：在每次分裂一个节点的时候，对同一层内的每个节点分裂前，先随机选择一部分特征，这时候只需要遍历一部分特征，来确定最后分割点 • 按树随机方式：即构建树结构前就随机选择特征，之后所有叶子节点的分裂都只采用这部分特征

2.5.4 系统设计——分块并行 在建树的过程中，最耗时的是找最优的切分点(这个可以用近似贪心算法解决)，而这个过程中，最耗时的部分是将数据排序；为了减少排序的时间，提出Block结构存储数据 • Block中的数据以稀疏格式CSC进行存储 • Block中的特征进行排序（不对缺失值排序） • Block中特征还需存储指向样本的索引，这样才能根据特征的值来取梯度 • 一个block中存储一个或多个特征的值

2.6 lightGBM lightGBM是一款常用的GBDT工具包，速度比XGBOOST快，精度也还可以，他的设计理念是： • 单个机器在不牺牲速度的情况下，尽可能使用上更多的数据 • 多机并行的时候，通信的代价尽可能地低，并且在计算上可做到线性加速 因此其使用分布的GBDT，选择了基于直方图的决策树算法 2.6.1 直方图算法 Xgboost中的精确贪心算法： • 对每个特征都按照特征值进行排序 • 在每个排好序的特征都寻找最优切分点 • 用最优切分点进行切分 优点是比较精确，缺点是空间消耗比较大，时间开销大和对内存不友好，使用直方图算法进行划分点的查找可以克服这些缺点

直方图算法：把连续的浮点特征值离散化为k个整数（也就是分桶bins的思想），比如[0,0.1]->0， [0.1,0.3]->1；并根据特征所在的bin对其进行梯度累加和个数统计，然后根据直方图，寻找最优的切分点 如何分桶bins？数值型特征和类别特征采用的方法是不同的 • 数值型特征

2.6.2 直方图算法改进-GOSS算法 样本梯度越小，样本训练误差越小，表示样本已训练的很好，因此在lightGBM中采用了one-side采样方式来适配：GOSS（gradient-based one-side sampling）采样策略，它保留所有大梯度样本，对小梯度样本进行随机抽样。 原始直方图算法下，在第j个特征，值为d处进行分裂带来的增益为：

2.6.2 直方图算法改进——EFB算法 高维数据通常是稀疏的，且许多特征互斥（即两个或多个特征不会同时为非0），lightGBM根据这一特点提出了EFB（exclusive feature bundling）算法将互斥特征进行合并，能合并的特征为一个#bundle，从而将特征的维度降下来，相应的，构建histogram所耗费的时间复杂度也从O(#data*#feature)变为O(#data*#bundle), 其中#feature>>#bundle；但是该方法有两大难点：  哪些特征可以合并为一个bundle？ ———Greedy bundle  如何将特征合并为bundle，实现降维？——merge exclusive features 2.6.3 树的生长策略 在XGBoost中，树按层生长，同一层的所有节点都做分裂，最后剪枝，它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

这种剪枝策略的**好处是可以进行多线程的并行化，且不容易发生过拟合**；缺点是同一层的叶子节点分裂增益可能已经比较低了，没必要再进行分裂，导致对生成树不是最优的，换句话说，它的生长效率没有那么高

LightGBM的生长策略是leaf-wise，以降低模型损失最大化为目的，对当前所有叶子节点中切分增益最大的leaf节点进行切分；leaf-wise的缺点是会生成比较深的决策树，为了防止过拟合，可在模型参数中设置决策树的深度。 它的好处是生长的树是最优的，不好的地方是它的树生长的深度比较大，可能会造成过拟合，因此在参数中需要设定树的最大深度。

2.6.3 系统设计 LightGBM具有支持高效并行的特点，原生支持并行学习，目前支持：  特征并行  数据并行  Voting并行（数据并行的一种）

2.6.4 系统设计——特征并行 特征并行是并行化决策树中寻找最优切分点的过程。特征并行是将对特征进行划分，每个worker找到局部的最佳切分点，使用点对点通信找到全局的最佳切分点。  传统算法： 不同的worker存储不同的特征集，在找到全局的最佳划分点后，具有该划分点的worker进行节点分裂，然后广播切分后的左右子树数据结果，其他worker收到结果后也进行划分  LightGBM中的算法： 每个worker中保存了所有的特征集，在找到全局最佳划分点后每个worker可自行进行划分，不再进行广播划分结果，减小了网络通信量，但存储代价变高。

2.6.4 系统设计——数据并行 数据并行目标是并行化整个决策学习的过程，每个worker拥有部分数据和全部的特征，独立的构建局部直方图，合并后得到全局的直方图，在全局直方图中寻找最优切分点进行分裂 2.6.4 系统设计——voting parallel lightGBM采用一种称为PV-Tree的算法进行投票并行（voting parallel），其实这本质上是一种数据并行；PV-Tree和普通的决策树差不多，只是在寻找最优切分点上有所不同。 每个worker拥有部分数据，独自构建直方图并找到top-k最优的划分特征，中心worker聚合得到最优的2k个全局划分特征，再向每个worker收集top-2k特征的直方图，并进行合并得到最优划分，广播给所有worker进行本地划分。

2.6.5 lightGBM实践 使用xgboost设置树的深度，在lightGBM中是叶子节点的个数： 提高训练速度的方法：  Bagging(data sub-sampling)  Feature sub-sampling  Use categorical feature directly  Save data file to binary file to speed up data loading in feature learning  Use parallel learning 提高精度的方法：  Small learning_rate with large num_iterations  Large num_leave(may over-fitting)  Cross validation  Bigger training data  Try DART – use drop out during the training