集成学习：XGBoost算法目标函数推导

XGBoost全名叫(eXtreme Gradient Boosting)极端梯度提升，GBDT(gradient boosting decision tree)的改进

XGBoost的核心算法思想：
1、不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数f(x)，去拟合上次预测的残差。
2、当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数
3、最后只需要将每棵树对应的分数加起来就是该样本的预测值。

关于XGBoost算法目标函数推导如下：

Xgboost与GBDT二者的不同与共同点：
1、GBDT是机器学习算法，XGBoost是该算法的工程实现
2、在使用CART作为基分类器时，XGBoost显示的加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力【在AdaBoost与GBDT中也有正则化，只不过是以系数的形式出现】
3、GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数
4、传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器
5、传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据的采样
6、传统的GBDT没有设计对缺失值的处理，XGBoost能够自动学习出缺失值的处理策略
7、在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，XGBoost 实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。同时当分裂时遇到一个负损失时，GBM 会停止分裂。XGBoost 会一直分裂到指定的最大深度(max_depth)，然后回过头来剪枝。如果某个节点之后不再有正值，它会去除这个分裂。这种做法的优点，当一个负损失（如-2）后面有个正损失（如+10）的时候，就显现出来了。GBM 会在-2处停下来，因为它遇到了一个负值。但是 XGBoost 会继续分裂，然后发现这两个分裂综合起来会得到+8，因此会保留这两个分裂。
8、XGBoost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

正则项的目的：是通过控制基学习器的复杂度来防止过拟合