XGBoost（eXtremeGradientBoosting）的核心是决策树的提升方法，属于集成学习。以下部分分别介绍决策树、决策树集成和Xgboost。1.决策树决策树决策树是一种常见的监督学习方法，可以用来处理分类和回归问题。分类问题（离散值）：西瓜甜不甜？回归问题（连续值）：房价是多少？顾名思义，就是构建一个树状的决策流程。树中的每个节点都选择一个特定的特征来对样本做出决定。特征树的构建主要分为三个步骤：特征选择、决策树构建和剪枝。其中，根据特征选择方法的不同，分为三个主要算法：ID3、C4.5、CART。ID3基于信息增益进行特征选择：分为特征A前后训练集数据的信息熵。通过选择特征A最大化信息增益：但是由于特征值不平衡的问题（例如性别只有男性和女性，年龄可以分为很多类别），ID3算法更倾向于选择取值更多的特征。CART（ClassificationAndRegressionTree）根据基尼系数进行特征选择。在分类问题中：通过将熵值的计算（对数运算）转化为基尼系数的计算（平方运算），大大降低了计算复杂度。对于回归树，CART可以处理回归树问题，其优化目标如下：即通过特征j和分割点s将数据集分成两组，并使各自样本的方差最小在两个集合中（c1，c2分别是集合样本的均值）。总的来说，决策树是一种基于特征的if-then决策过程，高效且易于理解。但它对训练样本的依赖性很强，容易生成复杂的树结构，造成过拟合等问题。如果你想学习一个最优决策树，它被认为是一个NP-Complete问题。实际的决策树是基于启发式贪心算法建立的，不能保证建立全局最优的决策树。2.决策树集成TreeEnsemble集成学习（ensemblelearning）通过构建和组合多个学习器来完成学习任务。这里我们主要关注Bagging和Boosting。2.1BaggingBagging（bootstrapaggregating）是基于Bootstraping重采样方法（samplingwithreplacement），独立训练生成k个模型，综合这k个模型的输出得到最终结果（分类问题可以使用voting，回归问题可以使用mean).Bootstraping通常能够覆盖63.2%的数据样本。它可以并行执行，这样可以防止模型对训练数据过于敏感，降低模型的方差。Bagging和决策树的结合产生了随机森林（RandomForest）。与Bagging方法唯一不同的是，RandomForest在特征选择之前使用特征采样（一般使用四个特征），减少了强分类属性对模型的影响，使不同的模型更加独立。2.2Boosting在Boosting方法中，数据集不变，改变样本的权重，使得后面的模型更关注前面模型误分类的样本，需要串行执行。具体可以分为以下几类：AdaBoosting（自适应提升）。AdaBoosting在Boosting的基础上，根据每轮迭代中加权样本的错误率，为每个模型分配相应的权重。迭代过程中模型权值和样本权值的更新方法如下：,为第i+1轮第j个样本的权值，用于正则化权值。GradientBoosting通常用于回归树。上一轮模型的预测值与真实值的残差作为下一轮的输入，表示第i个样本和第m轮的残差，分别为真实值和预测值，分别。GBDT（GradientBoostingDecisionTree），对于下一轮的输入（残差），根据不同的损失函数，提供不同的计算方式。当损失函数为平方差时，残差与GB一致。通过添加学习率的概念，可以调整对错误分类数据的关注。Xgboost是本文的主角。这里先和GBDT做个对比，再详细说明：在正则化项中加入了树模型的复杂度，避免过拟合，所以泛化性能会比GBDT好。损失函数使用泰勒展开展开，同时使用一阶导数和二阶导数，可以加快优化速度。而GBDT只支持CART作为基分类器，也支持线性分类器。使用线性分类器时，可以使用L1和L2正则化。引入了特征子采样，如RandomForest，它减少了过拟合和计算。在寻找最佳分割点时，考虑到传统贪心算法效率低下，采用近似贪心算法来加速和减少内存消耗。此外，它还考虑了对稀疏数据集和缺失值的处理，对于特征值缺失的样本，XGBoost仍然可以自动找到分裂的方向。XGBoost支持并行处理。XGBoost的并行不是模型上的并行，而是特征上的并行。特征列被排序后以块的形式存储在内存中，这种结构在后续的迭代中被复用。该块还使并行化成为可能。其次，在进行节点分裂时，计算每个特征的增益，最后选择增益最大的特征进行分裂。然后，每个特征的增益计算可以在多个线程中进行。3.Xgboost对应论文。这里分三部分介绍Xgboost：Xgboost模型、分割点的搜索、算法的并行实现。3.1.3Shrinkage和ColumnSubsamplingShrinkage（收缩）可以像GBDT一样设置学习率，减少每棵树的影响，让后面有更多的学习空间。在实际应用中，一般将学习率设小一些，然后迭代次数设大一些。ColumnSubsampling（列采样）是RandomForest中的特征采样方式，让每棵树尽可能独立。3.2寻找分裂点SplitFinding为了找到特征的最优分裂点，需要遍历特征的所有值，得到所有可能的分裂点。然后带入目标函数进行计算，将最优目标函数值对应的分割点作为特征的分割点。但是在回归问题中，特征是连续的，候选分割点很多，因此需要大量的时间和内存来寻找最优的分割点。3.2.1近似算法Xgboost采用近似的方法对排序后的特征进行分割，分割之间只形成候选分割点，大大减少了候选分割点的数量。其算法和效果如下图所示。分割点的近似搜索方法分为全局和局部最优分割和近似分割比较。eps=epsilon，表示按照eps比例划分数据集。这里的一个重要问题是根据什么标准生成候选分割点。在Xgboost中，不是简单的等分，而是根据二阶导数进行加权划分。.3.2.2Sparsity-awareSplitFinding对于稀疏数据的情况，如：1.数据缺失值；2.大量0值；3.执行one-hot编码。Xgboost提供了相应的算法来给稀疏数据一个默认值。该方法的核心是对节点左侧或右侧的所有缺失样本进行划分，选择增益最大的划分方式作为默认划分。3.3系统设计SystemDesign3.3.1ColumnBlockforParallelLearning树构建过程中最耗时的是样本的排序。为了减少排序时间，排序信息使用Block结构存储：Block中的数据以稀疏格式存储CSCBlock对Block中的特征进行排序（不对缺失值进行排序）Block中的特征还需要存储指向样本的索引，这样就可以根据特征值取梯度。一个或多个特征的值存储在一个块中。可以看出在建树之前只需要排序一次，后面分裂节点的时候可以直接根据索引获取梯度信息。在Exact贪心算法中，整个数据集存储在一个Block中。这样就改变了原来的复杂度，Exact贪心算法省去了每一步的排序开销。在近似算法中，使用了多个块，每个块对应于原始数据的一个子集。不同的块可以在不同的机器上计算。这种方法对局部策略特别有效，因为局部策略在每次分支时都会重新生成候选分裂点。块结构还有其他优点。数据存储在列中，并且可以同时访问所有列。很容易实现用于查找分裂点的并行算法。另外，也方便实现后面要讲的出局分计算。但缺点是空间消耗成倍增加。3.3.2Cache-awareAccess使用Block结构的一个缺点是，在获取梯度时，是通过索引获取的，获取这些梯度的顺序是按照特征大小的顺序。这样会导致内存访问不连续，可能会导致CPUcache缓存命中率低，从而影响算法效率。因此，对于精确的贪心算法，使用缓存预取。具体来说，给每个线程分配一个连续的缓冲区，读取梯度信息存入缓冲区（这样就实现了非连续到连续的转换），然后对梯度信息进行统计。这种方法在训练样本数量较多时特别有用，如下图所示：在近似算法中，合理设置Block的大小。将块的大小定义为块中的最大样本数。设置合适的尺寸非常重要。太大容易导致命中率低，太小容易导致并行化效率低下。经过实验，发现2^16更好。3.3.3核外计算的块当数据量太大，主存放不下时，为了能够进行核外计算，将数据分成多个块存储在磁盘上.计算时，使用独立线程将Block提前放入主存，这样就可以边计算边读取和压缩磁盘块。貌似是用近几年性能优秀的LZ4压缩算法按列压缩。是时候使用另一个线程来解压了。对于行索引，只保存第一个索引值，然后用16位整数保存与块第一个索引的差值。BlockSharding，将数据划分到不同的硬盘中以提高磁盘吞吐量
