作业3

一、XGB
XGBoost是2014年2月诞生，由中国的陈天奇提出。XGBoost实现的是一种通用的Tree Boosting算法。 xgboost即能解决分类问题，也能解决回归问题。
二、CART树
Classification And Regression Trees，分类回归树。该算法既可以用于分类还可以用于回归，因此非常值得学习。利用python构建并显示CART树，代码会保持足够的灵活性以便能用于多个问题当中。接着，利用CART算法构建回归树并使用树剪枝（目的防止树的过拟合）。CART是十分著名且广泛记载的树构建算法，它使用二元切分来处理连续型变量。
三、算法原理
XGB原理是，首先使用训练集和样本真值（即标准答案）训练一棵树，然后使用这棵树预测训练集，得到每个样本的预测值，由于预测值与真值存在偏差，所以二者相减可以得到“残差”。接下来训练第二棵树，此时不再使用真值，而是使用残差作为标准答案。两棵树训练完成后，可以再次得到每个样本的残差，然后进一步训练第三棵树，以此类推。树的总棵数可以人为指定，也可以监控某些指标（例如验证集上的误差）来停止训练。
CART树原理：CART假设决策树是二叉树，内部结点特征的值分为“是”和“否”。所以某个属性（特征）若是取值超过2个，则必然有一个分支结点在该属性上的取值超过一个。与ID3树不同的是，上层使用过的属性，在下层依然可以使用，只是属性的取值集合变少了而已。分支时需要考虑所有可能的属性选择与所有可能取值作为切分点。而ID3只需要考虑属性选择，因为分支数量等于取值数量，所以不必考虑切分点。
分类树的生成：
输入：训练集，停止计算的条件
输出：CART决策树
1. 对每个特征A，对其每个可能的取值a，根据样本点对A<=aA<=a的测试为“是”和“否”分为两个子集D1D1和D2D2，计算A<=aA<=a时的gini指数
2. 在所有可能的特征及所有切分点中，找到gini指数最小的特征及切分点，据此最终分成两个子集D1D1和D2D2
3. 递归调用1和2，直至满足停止条件
4. 计算叶子节点的所属类别。
停止计算的条件常用的有节点的样本数量小于预定阈值，或者节点的gini指数小于预定阈值（表示节点已经很纯了）。
四、损失函数
XGB对损失函数进行二阶泰勒展开。
传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

五、分裂结点算法
exact greedy algorithm 贪心算法获取最优切分点
六、正则化
规则化参数是防止模型过分的拟合训练数据。
xgboost在代价函数里加入了正则项，用于控制模型的复杂度。

正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

七、对缺失值处理
无需处理缺失值
八、优缺点
xgBoosting在传统Boosting的基础上，利用cpu的多线程，引入正则化项，加入剪纸，控制了模型的复杂度。
与GBDT相比，xgBoosting有以下进步：
1）GBDT以传统CART作为基分类器，而xgBoosting支持线性分类器，相当于引入L1和L2正则化项的逻辑回归（分类问题）和线性回归（回归问题）；
2）GBDT在优化时只用到一阶导数，xgBoosting对代价函数做了二阶Talor展开，引入了一阶导数和二阶导数；
3）当样本存在缺失值是，xgBoosting能自动学习分裂方向；
4）xgBoosting借鉴RF的做法，支持列抽样，这样不仅能防止过拟合，还能降低计算；
5）xgBoosting的代价函数引入正则化项，控制了模型的复杂度，正则化项包含全部叶子节点的个数，每个叶子节点输出的score的L2模的平方和。从贝叶斯方差角度考虑，正则项降低了模型的方差，防止模型过拟合；
6）xgBoosting在每次迭代之后，为叶子结点分配学习速率，降低每棵树的权重，减少每棵树的影响，为后面提供更好的学习空间；
7）xgBoosting工具支持并行,但并不是tree粒度上的，而是特征粒度，决策树最耗时的步骤是对特征的值排序，xgBoosting在迭代之前，先进行预排序，存为block结构，每次迭代，重复使用该结构，降低了模型的计算；block结构也为模型提供了并行可能，在进行结点的分裂时，计算每个特征的增益，选增益最大的特征进行下一步分裂，那么各个特征的增益可以开多线程进行；
8）可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，这种贪心法异常耗时，这时引进近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂；
然而，与LightGBM相比，又表现出了明显的不足：
1）xgBoosting采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低；
2）xgBoosting采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销；LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合，因此引入了一个阈值进行限制，防止过拟合.
九、应用场景
分类、回归均可使用。不同的机器学习模型适用于不同类型的任务。深度神经网络通过对时空位置建模，能够很好地捕获图像、语音、文本等高维数据。而基于树模型的XGBoost则能很好地处理表格数据，同时还拥有一些深度神经网络所没有的特性（如：模型的可解释性、输入数据的不变性、更易于调参等）

参考：https://blog.csdn.net/PbGc396Dwxjb77F2je/article/details/78786959
https://blog.csdn.net/zhiling2/article/details/53998003
https://blog.csdn.net/u013363120/article/details/80195471
https://blog.csdn.net/github_38414650/article/details/76061893