Xgboost
1.简述原理+算法推导
2.分裂节点算法
3.防止过拟合
4.连续值与缺失值处理
5.优缺点
6.参数调节
7. Xgboost与gbdt的区别
1.简述原理：gbdt的改进
在GBDT算法的基础（拟合残差）上给代价函数加一个正则化项，对目标函数进行二阶泰勒近似。然后，采用精确或近似方法贪心搜索出得分最高的切分点(维度+值)，进行下一步切分并扩展叶节点
具体：不断地添加树，不断地进行特征分裂来生长一棵树，每添加一个树，其实是学习一个新函数，去拟合上次预测的残差。当训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值
算法推导（树结构确定后，如何求得每个叶子结点的分数）
2.分裂节点算法
（如何确定树结构，即每次特征分裂怎么寻找最佳特征，怎么寻找最佳分裂点）
基于空间切分去构造一颗决策树是一个NP难题，我们不可能去遍历所有树结构，所以xgboost使用了和CART回归树一样的思想，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是使用（下面算法推导中的）目标函数值作为评价函数，分裂后的目标函数值比单子叶子节点的目标函数的增益大则分裂。同时为了限制树生长过深，还加了个阈值，只有当增益大于该阈值才进行分裂。同时可以设置树的最大深度、当样本权重和小于设定阈值时停止生长去防止过拟合。
3.Xgboost防止过拟合的方法
1）Shrinkage（一般更好）
在每次迭代中对树的每个叶子结点的分数乘一个缩减权重η，这可使每一棵树的影响力不会太大，留下更大的空间给后面生成的树去优化模型。
2）Column Subsampling
类似于RF的选取部分特征进行建树。分为按层随机采样，随机选择特征
按层随机采样：在对同一层内每个结点分裂之前，先随机选择一部分特征，然后只需要遍历这部分的特征，来确定最优的分割点。
随机选择特征：建树前随机选择一部分特征然后分裂就只遍历这些特征。
4.连续值与缺失值处理
连续值处理
对于连续型特征值，当样本数量非常大，该特征取值过多时，遍历所有取值会花费很多时间，且容易过拟合。因此XGBoost思想是对特征进行分桶，即找到l个划分点，将位于相邻分位点之间的样本分在一个桶中。在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分. 从算法伪代码中该流程还可以分为两种，全局的近似是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部近似就是在具体的某一次分裂节点的过程中采用近似算法
缺失值处理（稀疏数据）
当样本的第i个特征值缺失时，无法利用该特征进行划分时，XGBoost的思想是将该样本分别划分到左右节点，然后计算其增益，哪个大就划分到哪边。
5.优缺点
优点
1.使用许多策略去防止过拟合，如：正则化项、Shrinkage and Column Subsampling等。
2. 目标函数优化利用了损失函数关于待求函数的二阶导数
3.支持并行化，这是XGBoost的闪光点，虽然树与树之间是串行关系，但是同层级节点可并行。具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行。训练速度快。
4.添加了对稀疏数据的处理。
5.交叉验证，early stop，当预测结果已经很好的时候可以提前停止建树，加快训练速度。
6.支持设置样本权重，该权重体现在一阶导数g和二阶导数h，通过调整权重可以去更加关注一些样本
缺点：训练耗时长，内存占用比较大；预排序方法的时间和空间消耗都很大
6.可调参数：
xgboost 有很多可调参数，具有极大的自定义灵活性。比如说：
objective [ default=reg:linear ] 定义学习任务及相应的学习目标，可选的目标函数如下：
“reg:linear” –线性回归。
“reg:logistic” –逻辑回归。
“binary:logistic” –二分类的逻辑回归问题，输出为概率。
“multi:softmax” –处理多分类问题，同时需要设置参数num_class（类别个数）
’eval_metric’ The choices are listed below，评估指标:
“rmse”: root mean square error
“logloss”: negative log-likelihood
max_depth [default=6] 数的最大深度。缺省值为6 ，取值范围为：[1,∞]
7.特点/与GBDT区别
简述：加正则化；二阶泰勒展开；可处理稀疏、缺失数据；支持线性分类器；引进特征子采样；节点分裂标准，用近贪心算法寻找最佳分割点;支持并行处理 ;权重衰减；有效利用磁盘；
方差-方差权衡；可并行的近似直方图算法
加正则化；二阶泰勒展开；可处理稀疏、缺失数据（自动找到要分裂的方向）；除CART基分类器外，支持线性分类器；引进特征子采样（类似RF），降低过拟合、减少计算；xgboost是用是经过优化推导后的作为分裂标准，用近贪心算法寻找最佳分割点，加速、减小内存消耗；支持并行处理（不是在模型上的并行，是在特征上的并行，将特征列排序后以block的形式存储在内存中,在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能,其次在进行节点分裂时，计算每个特征的增益,最终选择增益最大的那个特征去做分割,那么各个特征的增益计算就可以开多线程进行）方差-方差权衡;可并行的近似直方图算法
1.正则化项
xgboost在代价函数中加入了正则项，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性
XGBoost生成CART树考虑了树的复杂度，GDBT未考虑，GDBT在树的剪枝步骤中考虑了树的复杂度。
2.损失函数
xgboost的损失函数是用泰勒展式二项逼近，GBDT中是一阶导数。XGBoost是拟合上一轮损失函数的二阶导展开，GDBT是拟合上一轮损失函数的一阶导展开，因此，XGBoost的准确性更高，且满足相同的训练效果，需要的迭代次数更少。
3.对缺失值的处理
对特征的值有缺失的样本，xgboost可自动学习出它的分裂方向。xgboost考虑了训练数据为稀疏值的情况，可为缺失值/指定的值指定分支的默认方向，这能大大提升算法的效率。
4.xgboost支持线性分类器。
传统的GBDT以CART树作为基学习器，xgboost还支持线性分类器，这个时候xgboost相当于L1和L2正则化的LR（分类）或者线性回归（回归）；
5. xgboost支持列抽样（特征子采样）
xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
6.节点分裂标准
GBDT是用的基尼系数，xgboost是经过优化推导后的
7. 用近贪心算法寻找最佳分割点
可并行的近似直方图算法。树节点在进行分裂时，需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。xgboost实现了一种近似的算法。大致思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
8. xgboost工具支持并行
xgboost的并行不是tree粒度的并行，xgboost的并行是在特征粒度上的。特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。
9. xgboost的权重衰减shrinkage（缩减）
相当于学习速率（XGBoost中的eta），XGBoost进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间（GBDT也有学习速率）；
10.数据量大内存不够时有效利用磁盘
xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。
11方差-方差权衡：
XGBoost在目标函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出分数的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性。
12可并行的近似直方图算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点
Xgboost问题
1.为什么xgboost要用泰勒展开，优势在哪？
1）xgboost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准.
2）用泰勒展开取得函数做自变量的二阶导数形式, 可在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加xgboost的适用性, 让xgboost可以按需选取损失函数, 可用于分类, 也可用于回归。
2.xgboost如何寻找最优特征？有无放回？
寻找最优特征：xgboost在训练的过程中给出各特征的增益评分，最大增益的特征会被选出来作为分裂依据, 从而记忆了每个特征对在模型训练时的重要性 -- 从根到叶子中间节点涉及某特征的次数作为该特征重要性排序
无放回，因为是boosting，每轮计算样本不重复
3. xgboost怎么给特征评分？
在训练的过程中，通过Gini指数选择分离点的特征，一个特征被选中的次数越多，那么该特征评分越高。
4. 观察增益gain, gamma越大gain越小, lamda越大, gain可能小也可能大.
寻找分割点标准：gain最大化
传统方法：贪心算法
Xgboost：近似方法（根据百分位法列举几个可能成为分割点的候选者，然后从候选者中计算Gain按最大值找出最佳的分割点）
Gain计算公式：
第一项是假设分割的左孩子的权重分数, 第二项为右孩子, 第三项为不分割总体分数, 最后一项为引入一个节点的复杂度损失。
lamda为叶子权重平方和的系数，默认1，权重的L2正则化项(和Ridge regression类似)。 这个参数是用来控制XGBoost的正则化部分的。虽然大部分数据科学家很少用到这个参数，但是这个参数在减少过拟合上还是可以挖掘出更多用处的。
Alpha，默认1，权重的L1正则化项(和Lasso regression类似)，可应用在很高维度的情况下，使得算法的速度更快。
gamma为在树的叶节点进一步分裂所需的最小损失减少量，默认0，在节点分裂时，只有分裂后损失函数的值下降了，才会分裂这个节点。Gamma指定了节点分裂所需的最小损失函数下降值。 这个参数的值越大，算法越保守。
5. xgboost怎么并行的？Boosting不是一种串行的结构吗?
简介：XGBoost工具支持并行。不是tree粒度的并行，而是在特征粒度上的并行
可并行的近似直方图算法。xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。